实验二线性表及其应用

1、姓名学号实验项目线性表及其应用（III）实验内容采用链式存储结构，两个项目选择一个项目完成：1编制一个演示集合的并、交和差运算的程序。（具体要求见题集第80页1.3）2一元稀疏多项式的计算。要求实现多项式存储、输出显示、相加、相减、相乘。（具体要求见题集第81页1.5）算法设计与程序实现：算法分析本次实验的目的是理解和掌握线性表链式存储结构的用法。根据多项式的加法运算法则和乘法运算法则进行多项式的运算。程序设计流程图如下所示：1.多项式加法运算程序流程 本函数的基本思想是先对两个链表中非空的部分进行指数比较，当指数不等时，将指数小的数据复制到新开辟结点中，指数大的结点继续与下一个结点比较，当指

2、数相等时，将两个结点系数合并，判断系数是否为零，若为零则不开辟新结点，否则开辟新结点复制数据。 2.多项式乘法运算程序流程图: 本函数的基本思想是将用两层循环分别遍历链表，用Pa的任一项乘以Pb的每一项，将乘积结果通过后续函数合并化简。 3.多项式链表排序流程图： 本函数的基本思想是运用选择排序算法，首先通过外层循环确定一个位置，即内层循环起始位置，然后用一个指针p遍历链表，并通过一个指针s指向内层循环中数据最小的结点，最后用内层循环结束后的指针s与内层循环起始指针比较，不等则交换，从而实现排序。核心程序 此程序中用到的自己编写的头文件以在下面给出，而头文件的说明则在主函数中文件包含部分的注释

3、处，核心程序如下：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 数据结构实验 实验二：线性表及其应用（）

4、"); /设置标题system("color F1"); /设置控制台窗口的背景色和前景色system("date /T"); /输出当前的日期printf("请输入多项式P1(x)的项数：");scanf_s("%d",&m);GreatPolynomial_L(P1,m); /根据输入数据创建一个多项式的单链表P1SortPolynomial_L(P1); /对多项式按照指数大小排序printf("P1(x)：");PrintPolynomial_L(P1); /打印多项式

5、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)：");Prin

6、tPolynomial_L(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)：");Pr

7、intPolynomial_L(P3);DiffPolynomial_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); /销毁多项式链表P2 DestroyPolynomia

8、l_L(P3); /销毁多项式链表P3return 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 structfloat coef; /系数int expn; /指数

9、PElemType; /多项式指数、系数结构类型typedef struct PNodePElemType data; /多项式结点数据struct PNode * next; /多项式结点指针PNode,*Polynomial; /多项式链表结构体类型及指针结构类型3.头文件”DataStructure_LinearList.h”中部分函数定义如下：#include <stdio.h>#include <malloc.h>#include "ADT.h"/* 功 能 函 数 声 明 区*/* -链 表- */Status GreatPolynomi

10、al_L(Polynomial &P, int m); /输入m项系数与指数,建立链表PStatus InitPolynomial_L(Polynomial &P); /初始化多项式结构变量Status DestroyPolynomial_L(Polynomial &P); /销毁多项式链表Pint CompareExpn_L(PElemType Ea, PElemType Eb); /比较多项式的指数Status PrintPolynomial_L(Polynomial &P); /打印输出一元多项式PStatus UnitePolynomial_L(Poly

11、nomial &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的相加运

12、算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)* 函数功能：完成多项式指数按照从小到大顺序排序* 入口参数：

13、多项式结构体指针类型的引用&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; /

14、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 &

15、amp;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->ne

16、xt->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, Polyno

17、mial &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)ma

18、lloc(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) /判断系数是否为0pa = pa->next; /pa和pb指针均后移pb = pb->next;elsepc-&g

19、t;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->dat

20、a.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 = (Pol

21、ynomial)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和

22、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的每一项乘以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;