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

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

2、eof(PN ode)pc = Pcpa = NULL ?一 = Y比较多项式系数CompareExpn L(pa-data, p b-data)p a-data.coef + pb-data.coef = 0:pb = NULL ?ic-data.coef = pa- data.coef + p b-data.coef odata.expn 二 pa- data.expnonext =Polyn omial)malloc(sizeof( PNode)pc = pc-nextpc-next =(Polyn omial)malloc(sizeof(P Node)pc = pc-n extpc-n

3、 ext =(Polyno mial)malloc(sizeo f(P Node)pc = pc-n ext1Vp c-data.coef = pa-p c-data.coef = pb-data.coefdata.coefp c-data.ex pn 二 pa-p c-data.ex pn 二 pb-data.ex pndata.ex pnpa = pa-n ext pb = pb-n extpa = pa-n extpb = pb-n extpc-n ext =NULL本函数的基本思想是先对两个链表中非空的部分进行指数比较，当指数不等时,将指数小的数据复制到新开辟结点中，指数大的结点继续与

4、下一个结点比较，当指数相等时，将两个结点系数合并，判断系数是否为零，若为零则不开辟新结点，否则开辟新结点复制数据。2.多项式乘法运算程序流程图（ 开始）用Pa的任一项乘以Pb的每本函数的基本思想是将用两层循环分别遍历链表, 项，将乘积结果通过后续函数合并化简。3. 多项式链表排序流程图：开始p = P-n ext十j -WP-next != NULL ?coef_tem p = p-data.coef expn _tem p = p-data.ex pn_ -s=q-data.ex pn data.coef = s-data.coef p-data.ex pn = s-data.ex pn s

5、-data.coef = coef_tem p s-data.ex pn =ex pn_tem pp = p-n ext本函数的基本思想是运用选择排序算法，首先通过外层循环确定一个位置，即内层循环起始位置，然后用一个指针P遍历链表，并通过一个指针 s指向内层循环中数据最小的结点，最后用内层循环结束后的指针s与内层循环起始指针比较，不等则交换，从而实现排序。此程序中用到的自己编写的头文件以在下面给出，而头文件的说明则在主函数中 文件包含部分的注释处，核心程序如下：1.主函数如下：#in elude stdafx.h/标准输入输岀函数头文件#in clude#in clude#in clude声明

6、int main()wi ndows.hADT.hcmd窗口设置函数头文件DataStructure LinearList.h/数据结构中相关结构体类型定义及相关数据类型定义/数据结构第二章线性表中相关函数的定义及Polynomial P1,P2,P3; int m;system( title数据结构实验实验二：线性表及其应用(m) );/设置标题system( color F1);/设置控制台窗口的背景色和前景色system( date /T);printf(请输入多项式P1(x)的项数：/输岀当前的日期1);scanf_s( %d,&m);Great Poly no mial_L( P1,

7、m);Sort Poly no mial L( P1);/根据输入数据创建一个多项式的单链表/对多项式按照指数大小排序printf( P 1(x):);PrintP oly no mial_L( P1);printf(请输入多项式P2(x)的项数：/打印多项式P1(x)的表达式 );scanf s( %d,&m);Great Poly no mial_L( P2,m);/根据输入数据创建一个多项式的单链表Sort Poly nomial L( P2);/对多项式按照指数大小排序printf(P2(x):);PrintP oly no mial_L( P2);AddPolyno mial L(

8、P1,P2,P 3);/多项式P1(x)和P2(x)相加printf(*1多项式加法 P 1(x) + P2(x):);PrintP oly no mial L( P3);Destroy Poly no mial L( P3);/销毁加法运算生成的多项式P3P1P2/多项式P1(x)和P2(x)相减Sub Polyno mial_L( P1,P2,P 3);printf( *2 多项式减法 P1(x) - P2(x):);PrintP oly no mial_L( P3);Destroy Poly no mial_L( P3);Multi Poly no mial L( P1, P2, P3)

9、;/销毁减法运算生成的多项式P3/多项式P1(x)和P2(x)相乘 printf( *3 多项式乘法 P1(x) * P2(x):);PrintP oly no mial_L( P3);/对多项式P1求微分printf( *4 多项式微分 dP 1(x)/dx:);/对多项式P2求积分PrintP oly no mial_L( P1); In tegral Poly no mial L( P2);printf( *5 多项式积分 IntP2(x),x:);PrintPolynomial L(P2);Destroy Poly no mial_L( P1);/销毁多项式链表P1Destroy Po

10、ly no mial_L( P2);/销毁多项式链表p2Destroy Poly no mial L(P 3);/销毁多项式链表P3Diff Poly no mial L( P1);return 0;r2.头文件ADT.h”的部分程序如下:#ifndefADT_H_#defi neADT H/*常量和数据类型预定义*/函数结果状态代码#defi neTRUE1#defi neFALSE0#defi neOK1#defi neERROR0/*#defi neINFEASIBLE -1#defi neOVERFLOW -2*/*数据结构类型定义*/*线丿性表 */*/*多项式存储结构类型定义-*/

11、typedef structfloat coef;/系数int expn;/指数P ElemT ype/多项式指数、系数结构类型typedef struct PNodeP ElemT yp edata;/多项式结点数据structPN ode* next;/多项式结点指针PNode* Polynomial ;/多项式链表结构体类型及指针结构类型3.头文件DataStructure_LinearList.h中部分函数定义如下：#i nclude #i nclude #i nclude ADT.h/*功能函数声明区*/*链表*/Status Great Poly no mial_L(P oly n

12、omial &P, int m);/ 输入 n项系数与指数，建立链表 P/初始化多项式结构变量Status DestroyPolynomial_L(Polynomial &P);/销毁多项式链表Pint CompareExpn L(PElemTypeEa, PElemTypeEb);/比较多项式的指数Status PrintPolynomial L(Polynomial &P);/打印输岀一元多项式PStatus In it Pol yno mial L(P oly nomial &P);Status Uni te Poly no mial_L(P oly no mial &P);Status

13、 Sort Poly no mial_L(P oly no mial &P);Status DiffPolynomial L(Polynomial &P);Status In tegral Poly no mial L(P oly no mial &P);/合并多项式P中的同类项/实现指数按照从小到大排序/实现多项式P的微分运算/实现多项式P的积分运算Status Add Poly no mial_L(_Polynomial &Pa,_Polynomial &Pb,_Polynomial &Pc);/ 完成I多项式Pa和Pb的相加运算Status Sub Poly nomial_L( P ol

14、y nomial &Pa, P oly no mial &Pb, P oly nomial &P c);/ 完成多项式Pa和Pb的相减运算Status Multi Poly no mial_L(P oly no mial &Pa, Poly nomial &Pb, P oly no mial &P c); / 完成多项式Pa和Pb的相乘运算/*功能函数定义区*/F* 函数原型：Status Sort Poly nomial L( Poly nomial &P)*函数功能：完成多项式指数按照从小到大顺序排序*入口参数：多项式结构体指针类型的引用&P*岀口参数：返回函数结果状态*/-Status

15、Sort Poly nomial_L( P oly nomial &P)Polynomial p,q,s;float coef te mp;int expn temp;for (p =Pnext; p-next != NULL p = p-next)/遍历整个链表s = p;)for (q = p-next; q; q = q-next) if (q-data.expn data.expn)/从p指针的下一结点开始遍历链表s = q;/s指针指向P结点及其之后链表中数据最小的结点if (s 匸 P)/将S结点与P结点交换数据coef_te mp = p-data.coef; expn_temp

16、 = p-data.ex pn; p-data.coef = s-data.coef; p-data.ex pn = s-data.ex pn; s-data.coef = coef_te mp; s-data.ex pn = expn_temp; return OK /Sort Polyno mial L/* 函数原型： Status UnitePolynomial L(Polynomial &P)*函数功能：合并多项式P中的同类项*入口参数：多项式结构体指针类型的引用&P*/*岀口参数：返回函数结果状态*/Status UnitePolynomial_L(Polynomial &P)Pol

17、ynomial p, q;for (p = Pnext; p-next !=NULL p = p-next)if (p-data.expn = p-next-data.expn)q = p-n ext;p-data.coef += p-n ext-data.coef; p-n ext = q-n ext;free(q);Treturn OK /UnitePolyno mial L/判断是否为同类项/保存下一结点，便于系数相加后释放/同类项系数相加* 函数原型：Status Add Polynomial_L(Polynomial &Pa, Polynomial &Pb, Polynomial &

18、Pc)*函数功能：完成多项式Pa和Pb的相加运算入口参数：多项式结构体指针类型的引用&P a,&Pb岀口参数：返回函数结果状态Status Add Polynomial_L( Polynomial &Pa, Polynomial &Pb, Poly nomial &Pc)Polynomial pa, pb, pc; pa = Pa-n ext;pb = Pthn ext;Pc = ( Polynomial )malloc( sizeof ( PNog); if (! Pc)return OVERFLOWpc = Pc;while (pa & pb)switch (CompareExpn L(p

19、a-data, pb-data)/判断指数的大小关系case -1:pa指向的结点指数小于pb指向结点的指数pc-next = (Polynomial )malloc( sizeof ( PNode);制指数较小的结点数据到新结点pc = pc-n ext;P c-data.coef = p a-data.coef; p c-data.ex pn = p a-data.ex pn;开辟新结点，复pa = pa-n ext; break;case 0:/较小指数结点后移，与上一指数较大结点再次比较/指数相等if (pa-data.coef + pb-data.coef = 0)/判断系数是否为0

20、pa = pa-n ext;pb = pb-n ext;lipa和pb指针均后移I else丄pc-next = ( Polynomial )malloc( sizeof ( PNode); 开辟新结点 pc = pc-n ext;p c-data.coef = p a-data.coef + p b-data.coef;p c-data.ex pn = p a-data.ex pn;pa = pa-n ext;pb = pb-n ext;ybreak;case 1:/pa指向的结点指数大于pb指向结点的指数pc-next = ( Polynomial )malloc( sizeof ( PN

21、ode); pc = pc-n ext;p c-data.coef = p b-data.coef;p c-data.ex pn = p b-data.ex pn; pb = pb-n ext; | break;while (pa)/复制Pa剩余结点数据:pc-next = ( Polynomial )malloc( sizeof ( PNode)；pc = pc-n ext;p c-data.coef = p a-data.coef;p c-data.ex pn = p a-data.ex pn; pa = pa-n ext;lwhile (pb)/复制Pt剩余结点数据pc-next = (

22、 Polynomial )malloc( sizeof ( PNode)；pc = pc-n ext;p c-data.coef = p b-data.coef; p c-data.ex pn = p b-data.ex pn;pb = pb-n ext;Ipc-n ext = NULL/Pc尾结点指针置空/*/遍历链表Pa,Pa的每一项乘以PbP c-data.coef = p a-data.coef * p b-data.coef;/系数相乘p c-data.ex pn = p a-data.ex pn + p b-data.ex pn;/指数相加pc = pc-n ext;pb = pb

23、-n ext;pa = pa-n ext;/pa指针后移pb = Pbn ext;p c- next =NULL/pb指针重置/尾结点指针置空Sort Poly no mial_L( Pc);/对相乘得到的多项式Pc按指数排序UniteP ol yno mial_L( Pc); return OK | /Mult iP ol yno mial L/合并同类项Pcreturn OK /Add Poly nomial_L* 函数原型：Status Mult iP oly nomial_L( Poly nomial &Pa, Poly no mial &Pb, P ol yno mial &Pcy*

24、函数功能：完成多项式Pa和Pb的相乘运算*入口参数：多项式结构体指针类型的引用&Pa,&Pb*岀口参数：返回函数结果状态Status MultiPolynomial_L(Polynomial &Pa Polynomial &Pb Polynomial &Pc)Polynomial pa, pb, pc;pa = Pa-n ext;pb = Pbhn ext;Pc = ( Polynomial )malloc( sizeof ( PNode);if (! Pc)return OVERFLOWpc = Pc;while (pa)while (pb) /遍历Pb,Pa的一项乘Pb的每一项pc-next = (Polynomial )malloc( sizeof ( PNod)；siBlG/ll/H叙愛顶 311 -t 1 -13 2 eWS ； m, r -仁aeh* dt旳炸 歯緘旗切g蒯4 SBiWi: “K(ki Fx? - 2,*-!J4.ea l.eftfTrLaSxTm 参:麻就哺 ?1 * ?I 叭时=3.00X*