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

1、电子信息工程学院 2013 级数据结构实验报告姓名 学号实验项目线性表及其应用（III）实验内容采用链式存储结构，两个项目选择一个项目完成：1编制一个演示集合的并、交和差运算的程序。 （具体要求见题集第 80 页 1.3）2一元稀疏多项式的计算。要求实现多项式存储、输出显示、相加、相减、相乘。（具体要求见题集第 81 页 1.5）算法设计与程序实现：算法分析本次实验的目的是理解和掌握线性表链式存储结构的用法。根据多项式的加法运算法则和乘法运算法则进行多项式的运算。程序设计流程图如下所示：1.多项式加法运算程序流程电子信息工程学院 2013 级数据结构实验报告开 始pa = Pa-nextpb

2、= Pb-nextPc= (Polynomial)malloc(sizeof(PNode)pc = Pc pa int m;system(“title 数据结构实验 实验二：线性表及其应用（） “); /设置标题system(“color F1“); /设置控制台窗口的背景色和前景色system(“date /T“); /输出当前的日期printf(“请输入多项式P1(x)的项数：“);scanf_s(“%d“,GreatPolynomial_L(P1,m); /根据输入数据创建一个多项式的单链表P1SortPolynomial_L(P1); /对多项式按照指数大小排序printf(“P1(x

3、)：“);PrintPolynomial_L(P1); /打印多项式P1(x)的表达式printf(“请输入多项式P2(x)的项数：“);scanf_s(“%d“, 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(

4、P3);DestroyPolynomial_L(P3); /销毁加法运算生成的多项式P3SubPolynomial_L(P1,P2,P3); /多项式P1(x)和P2(x)相减printf(“*2 多项式减法 P1(x) - P2(x)：“);PrintPolynomial_L(P3);DestroyPolynomial_L(P3); /销毁减法运算生成的多项式P3MultiPolynomial_L(P1,P2,P3); /多项式P1(x)和P2(x)相乘printf(“*3 多项式乘法 P1(x) * P2(x)：“);PrintPolynomial_L(P3);DiffPolynomial

5、_L(P1); /对多项式P1求微分printf(“*4 多项式微分 dP1(x)/dx：“);PrintPolynomial_L(P1);IntegralPolynomial_L(P2); /对多项式P2求积分printf(“*5 多项式积分 IntP2(x),x：“);PrintPolynomial_L(P2);DestroyPolynomial_L(P1); /销毁多项式链表P1DestroyPolynomial_L(P2); /销毁多项式链表P2DestroyPolynomial_L(P3); /销毁多项式链表P3return 0; 2.头文件”ADT.h ”的部分程序如下：#ifnd

6、ef ADT_H_#define ADT_H_电子信息工程学院 2013 级数据结构实验报告/* 常 量 和 数 据 类 型 预 定 义*/* -函数结果状态代码- */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/* 数 据 结 构 类 型 定 义*/*线 性 表*/* -多项式存储结构类型定义- */typedef structfloat coef; /系数int expn; /指数PElemType; /多项式指数、系数结构类型typedef

7、 struct PNodePElemType data; /多项式结点数据struct PNode * next; /多项式结点指针PNode,*Polynomial; /多项式链表结构体类型及指针结构类型3.头文件”DataStructure_LinearList.h” 中部分函数定义如下：#include #include #include “ADT.h“/* 功 能 函 数 声 明 区*/* -链 表- */Status GreatPolynomial_L(Polynomial /输入m项系数与指数,建立链表PStatus InitPolynomial_L(Polynomial /初始化

8、多项式结构变量Status DestroyPolynomial_L(Polynomial /销毁多项式链表Pint CompareExpn_L(PElemType Ea, PElemType Eb); /比较多项式的指数Status PrintPolynomial_L(Polynomial /打印输出一元多项式PStatus UnitePolynomial_L(Polynomial /合并多项式P中的同类项Status SortPolynomial_L(Polynomial /实现指数按照从小到大排序Status DiffPolynomial_L(Polynomial /实现多项式P的微分运算

9、电子信息工程学院 2013 级数据结构实验报告Status IntegralPolynomial_L(Polynomial /实现多项式P的积分运算Status AddPolynomial_L(Polynomial /完成多项式Pa和Pb的相加运算Status SubPolynomial_L(Polynomial /完成多项式Pa和Pb的相减运算Status MultiPolynomial_L(Polynomial /完成多项式Pa和Pb的相乘运算/* 功 能 函 数 定 义 区*/* 函数原型：Status SortPolynomial_L(Polynomial float coef_tem

10、p;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 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.ex

11、pn;s-data.coef = coef_temp;s-data.expn = expn_temp;return OK; /SortPolynomial_L/* 函数原型：Status UnitePolynomial_L(Polynomial 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;f

12、ree(q);return OK; /UnitePolynomial_L/* 函数原型：Status AddPolynomial_L(Polynomial pa = Pa-next;pb = Pb-next;Pc = (Polynomial)malloc(sizeof(PNode);if (!Pc)return OVERFLOW;pc = Pc;while (pa /开辟新结点，复制指数较小的结点数据到新结点pc = pc-next;pc-data.coef = pa-data.coef;电子信息工程学院 2013 级数据结构实验报告pc-data.expn = pa-data.expn;pa

13、 = pa-next; /较小指数结点后移，与上一指数较大结点再次比较break;case 0: /指数相等if (pa-data.coef + pb-data.coef = 0) /判断系数是否为0pa = pa-next; /pa和pb指针均后移pb = pb-next;elsepc-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-nex

14、t;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.exp

15、n;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;电子信息工程学院 2013 级数据结构实验报告pc-next = NULL; /Pc尾结点指针置空 return OK; /AddPolynomial_L/* 函数原型：Status MultiPolynomial_L(Polynomial pa = Pa-next;pb =

16、 Pb-next;Pc = (Polynomial)malloc(sizeof(PNode);if (!Pc)return OVERFLOW;pc = Pc;while (pa) /遍历链表Pa,Pa的每一项乘以Pbwhile (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); /合并同类项Pcreturn OK; /MultiPolynomial_L