实验二-线性表及其应用(III).docx

资源描述

电子信息工程学院2013级《数据结构》实验报告姓名学号实验项目线性表及其应用（III）实验内容采用链式存储结构，两个项目选择一个项目完成： 1．编制一个演示集合的并、交和差运算的程序。（具体要求见题集第80页1.3） 2．一元稀疏多项式的计算。要求实现多项式存储、输出显示、相加、相减、相乘。（具体要求见题集第81页1.5）算法设计与程序实现：算法分析本次实验的目的是理解和掌握线性表链式存储结构的用法。根据多项式的加法运算法则和乘法运算法则进行多项式的运算。程序设计流程图如下所示： 1.多项式加法运算程序流程本函数的基本思想是先对两个链表中非空的部分进行指数比较，当指数不等时，将指数小的数据复制到新开辟结点中，指数大的结点继续与下一个结点比较，当指数相等时，将两个结点系数合并，判断系数是否为零，若为零则不开辟新结点，否则开辟新结点复制数据。 2.多项式乘法运算程序流程图: 本函数的基本思想是将用两层循环分别遍历链表，用Pa的任一项乘以Pb的每一项，将乘积结果通过后续函数合并化简。 3.多项式链表排序流程图：本函数的基本思想是运用选择排序算法，首先通过外层循环确定一个位置，即内层循环起始位置，然后用一个指针p遍历链表，并通过一个指针s指向内层循环中数据最小的结点，最后用内层循环结束后的指针s与内层循环起始指针比较，不等则交换，从而实现排序。核心程序此程序中用到的自己编写的头文件以在下面给出，而头文件的说明则在主函数中文件包含部分的注释处，核心程序如下： 1.主函数如下： #include "stdafx.h" //标准输入输出函数头文件 #include "windows.h" //cmd窗口设置函数头文件 #include "ADT.h" //数据结构中相关结构体类型定义及相关数据类型定义 #include "DataStructure_LinearList.h" //数据结构第二章线性表中相关函数的定义及声明 int main() { Polynomial P1,P2,P3; int m; system("title 数据结构实验实验二：线性表及其应用（Ⅲ） "); //设置标题 system("color F1"); //设置控制台窗口的背景色和前景色 system("date /T"); //输出当前的日期 printf("请输入多项式P1(x)的项数："); scanf_s("%d",&m); GreatPolynomial_L(P1,m); //根据输入数据创建一个多项式的单链表P1 SortPolynomial_L(P1); //对多项式按照指数大小排序 printf("P1(x)："); PrintPolynomial_L(P1); //打印多项式P1(x)的表达式 printf("请输入多项式P2(x)的项数："); scanf_s("%d",&m); GreatPolynomial_L(P2,m); //根据输入数据创建一个多项式的单链表P2 SortPolynomial_L(P2); //对多项式按照指数大小排序 printf("P2(x)："); PrintPolynomial_L(P2); AddPolynomial_L(P1,P2,P3); //多项式P1(x)和P2(x)相加 printf("*1 多项式加法 P1(x) + P2(x)："); PrintPolynomial_L(P3); DestroyPolynomial_L(P3); //销毁加法运算生成的多项式P3 SubPolynomial_L(P1,P2,P3); //多项式P1(x)和P2(x)相减 printf("*2 多项式减法 P1(x) - P2(x)："); PrintPolynomial_L(P3); DestroyPolynomial_L(P3); //销毁减法运算生成的多项式P3 MultiPolynomial_L(P1,P2,P3); //多项式P1(x)和P2(x)相乘 printf("*3 多项式乘法 P1(x) * P2(x)："); PrintPolynomial_L(P3); DiffPolynomial_L(P1); //对多项式P1求微分 printf("*4 多项式微分 d[P1(x)]/dx："); PrintPolynomial_L(P1); IntegralPolynomial_L(P2); //对多项式P2求积分 printf("*5 多项式积分 Int[P2(x),x]："); PrintPolynomial_L(P2); DestroyPolynomial_L(P1); //销毁多项式链表P1 DestroyPolynomial_L(P2); //销毁多项式链表P2 DestroyPolynomial_L(P3); //销毁多项式链表P3 return 0; } 2.头文件”ADT.h”的部分程序如下： #ifndef ADT_H_ #define ADT_H_ /************************************************************ * 常量和数据类型预定义 ************************************************************/ /* ------函数结果状态代码------ */ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 /************************************************************ * 数据结构类型定义 ************************************************************/ /************************线性表*************************/ /* ------多项式存储结构类型定义------ */ typedef struct { float coef; //系数 int expn; //指数 }PElemType; //多项式指数、系数结构类型 typedef struct PNode { PElemType data; //多项式结点数据 struct PNode * next; //多项式结点指针 }PNode,*Polynomial; //多项式链表结构体类型及指针结构类型 3.头文件”DataStructure_LinearList.h”中部分函数定义如下： #include <stdio.h> #include <malloc.h> #include "ADT.h" /************************************************************ * 功能函数声明区 ************************************************************/ /* ------链表------ */ Status GreatPolynomial_L(Polynomial &P, int m); //输入m项系数与指数,建立链表P Status InitPolynomial_L(Polynomial &P); //初始化多项式结构变量 Status DestroyPolynomial_L(Polynomial &P); //销毁多项式链表P int CompareExpn_L(PElemType Ea, PElemType Eb); //比较多项式的指数 Status PrintPolynomial_L(Polynomial &P); //打印输出一元多项式P Status UnitePolynomial_L(Polynomial &P); //合并多项式P中的同类项 Status SortPolynomial_L(Polynomial &P); //实现指数按照从小到大排序 Status DiffPolynomial_L(Polynomial &P); //实现多项式P的微分运算 Status IntegralPolynomial_L(Polynomial &P); //实现多项式P的积分运算 Status AddPolynomial_L(Polynomial &Pa, Polynomial &Pb, Polynomial &Pc); //完成多项式Pa和Pb的相加运算 Status SubPolynomial_L(Polynomial &Pa, Polynomial &Pb, Polynomial &Pc); //完成多项式Pa和Pb的相减运算 Status MultiPolynomial_L(Polynomial &Pa, Polynomial &Pb, Polynomial &Pc);//完成多项式Pa和Pb的相乘运算 /************************************************************ * 功能函数定义区 ************************************************************/ /* * 函数原型：Status SortPolynomial_L(Polynomial &P) * 函数功能：完成多项式指数按照从小到大顺序排序 * 入口参数：多项式结构体指针类型的引用&P * 出口参数：返回函数结果状态 */ Status SortPolynomial_L(Polynomial &P) { Polynomial p,q,s; float coef_temp; int expn_temp; for (p = P->next; p->next != NULL; p = p->next) //遍历整个链表 { s = p; for (q = p->next; q; q = q->next) //从p指针的下一结点开始遍历链表 if (q->data.expn < s->data.expn) s = q; //s指针指向p结点及其之后链表中数据最小的结点 if (s != p) //将s结点与p结点交换数据 { coef_temp = p->data.coef; expn_temp = p->data.expn; p->data.coef = s->data.coef; p->data.expn = s->data.expn; s->data.coef = coef_temp; s->data.expn = expn_temp; } } return OK; } //SortPolynomial_L /* * 函数原型：Status UnitePolynomial_L(Polynomial &P) * 函数功能：合并多项式P中的同类项 * 入口参数：多项式结构体指针类型的引用&P * 出口参数：返回函数结果状态 */ Status UnitePolynomial_L(Polynomial &P) { Polynomial p, q; for (p = P->next; p->next != NULL; p = p->next) { if (p->data.expn == p->next->data.expn) //判断是否为同类项 { q = p->next; //保存下一结点，便于系数相加后释放 p->data.coef += p->next->data.coef; //同类项系数相加 p->next = q->next; free(q); } } return OK; } //UnitePolynomial_L /* * 函数原型：Status AddPolynomial_L(Polynomial &Pa, Polynomial &Pb, Polynomial &Pc) * 函数功能：完成多项式Pa和Pb的相加运算 * 入口参数：多项式结构体指针类型的引用&Pa,&Pb * 出口参数：返回函数结果状态 */ Status AddPolynomial_L(Polynomial &Pa, Polynomial &Pb, Polynomial &Pc) { Polynomial pa, pb, pc; pa = Pa->next; pb = Pb->next; Pc = (Polynomial)malloc(sizeof(PNode)); if (!Pc) return OVERFLOW; pc = Pc; while (pa && pb) { switch (CompareExpn_L(pa->data, pb->data)) //判断指数的大小关系 { case -1: //pa指向的结点指数小于pb指向结点的指数 pc->next = (Polynomial)malloc(sizeof(PNode)); //开辟新结点，复制指数较小的结点数据到新结点 pc = pc->next; pc->data.coef = pa->data.coef; pc->data.expn = pa->data.expn; pa = pa->next; //较小指数结点后移，与上一指数较大结点再次比较 break; case 0: //指数相等 if (pa->data.coef + pb->data.coef == 0) //判断系数是否为0 { pa = pa->next; //pa和pb指针均后移 pb = pb->next; } else { pc->next = (Polynomial)malloc(sizeof(PNode)); //开辟新结点 pc = pc->next; pc->data.coef = pa->data.coef + pb->data.coef; pc->data.expn = pa->data.expn; pa = pa->next; pb = pb->next; } break; case 1: //pa指向的结点指数大于pb指向结点的指数 pc->next = (Polynomial)malloc(sizeof(PNode)); pc = pc->next; pc->data.coef = pb->data.coef; pc->data.expn = pb->data.expn; pb = pb->next; break; } } while (pa) //复制Pa剩余结点数据 { pc->next = (Polynomial)malloc(sizeof(PNode)); pc = pc->next; pc->data.coef = pa->data.coef; pc->data.expn = pa->data.expn; pa = pa->next; } while (pb) //复制Pb剩余结点数据 { pc->next = (Polynomial)malloc(sizeof(PNode)); pc = pc->next; pc->data.coef = pb->data.coef; pc->data.expn = pb->data.expn; pb = pb->next; } pc->next = NULL; //Pc尾结点指针置空 return OK; } //AddPolynomial_L /* * 函数原型：Status MultiPolynomial_L(Polynomial &Pa, Polynomial &Pb, Polynomial &Pc) * 函数功能：完成多项式Pa和Pb的相乘运算 * 入口参数：多项式结构体指针类型的引用&Pa,&Pb * 出口参数：返回函数结果状态 */ Status MultiPolynomial_L(Polynomial &Pa, Polynomial &Pb, Polynomial &Pc) { Polynomial pa, pb, pc; pa = Pa->next; pb = Pb->next; Pc = (Polynomial)malloc(sizeof(PNode)); if (!Pc) return OVERFLOW; pc = Pc; while (pa) //遍历链表Pa,Pa的每一项乘以Pb { while (pb) //遍历Pb,Pa的一项乘Pb的每一项 { pc->next = (Polynomial)malloc(sizeof(PNode)); pc = pc->next; pc->data.coef = pa->data.coef * pb->data.coef; //系数相乘 pc->data.expn = pa->data.expn + pb->data.expn; //指数相加 pb = pb->next; } pa = pa->next; //pa指针后移 pb = Pb->next; //pb指针重置 } pc->next = NULL; //尾结点指针置空 SortPolynomial_L(Pc); //对相乘得到的多项式Pc按指数排序 UnitePolynomial_L(Pc); //合并同类项Pc return OK; } //MultiPolynomial_L 运行结果实验结果分析：从以上实验运行结果来说，程序可以实现实验要求的基本内容。实验总结 1、通过此次实验，我学会了链表建立、插入、删除、修改等基本操作，加深了对指针、结构体的了解，对c语言有了更进一步的认识。在大量运用指针的过程中当然避免不了使用的指针发生指向错误导致程序崩溃，但通过长时间的单步调试观察，最终解决了指针指向未知区域发生错误的问题。由于教材上是逆序建立链表，尾指针的指针域在初始化时就被置空了，所以就不必注意这个问题，由于本实验的程序中建立链表都采用顺序建立，所以一开始也没注意，从而造成了错误。从中我学到的就是链表尾结点的指针域一定要置成NULL，否则就会发生错误。 2、此次实验我遇到的难点，不是多项式的加、减或乘运算，而是对链表数据的排序，开始想通过起泡法直接排序，但发现排序时需要前后两个结点的数据进行比较，不管采用何种循环判断都不能实现，要么发生指针指向错误，要么就是不能对所以的数据进行比较，最后经交换得到启发，故最后实现了链表的排序。 3、在此次实验中我发现了一个问题，在多项式加法运算时，其中的一个判断条件 (!pb || pa->data.expn > pb->data.expn)会发生指针指向错误，即当pb=NULL时，会对或逻辑运算符后的条件进行判断，但根据标准C中逻辑或的判断原则，只要前一条件为真，后面条件不判断的原则，该函数又是正确的，多次单步调试都是这个问题，在网上搜索也没有解决，不知道是什么原因。

展开阅读全文