数据结构-基于链式表实现一元多项式的加减乘运算课程设计-实验报告

1、数 据 结 构 课 程 设 计 设计题目：基于链式表实现一元多项式的加减乘运算 课题名称基于链式表实现一元多项式的加减乘运算 院 系年级专业 成 绩 课题设计 目的与 设计意义 1、课题设计目的：通过多项式运算程序设计（用 C 语言实 现） ，使我们进一步掌握和利用 C 语言进行结构化程序设计的能力； 进一步理解和运用结构化程设计的思想和方法；初步掌握开发一个 小型系统程序设计的基本方法；学会调试一个较长程序的基本方法； 学会利用流程图或 N-S 图表示算法；以及掌握书写课程设计开发文 档的能力（书写课程设计报告） 。总之，通过本课程设计加深对C 语言及数据结构课程所学知识的理解，进一步巩固

2、C 语言语 法规则，在程序中体现出算法的思想，提高程序的运行效率。学会 编制结构清晰、风格良好、数据结构适当的语言程序，从而具备 解决综合性实际问题的能力。 2、课题设计意义：通过这次课程设计练习，使我更深刻 地理解了语言的精髓-指针的使用。完成整个程序设计有， 对指针掌握的更加熟练。 同时通过直接对链表的操作，加深了对数据结构的理解和认识。 并在完成课程设计的过程作主动查阅了相关资料，学到了不少课本 上没有的技术知识。 经过这次课程设计，我深刻认识到算法在程序设计中的重要性， 一个完整的程序总是由若干个函数构成的，这些相应的函数体现了 算法的基本思想。 另外也需要提出的是在这次程序设计的过程

3、中，非常感谢老师 对我的耐心指导。老师在教学过程中表现出来的对学术专研一丝不 苟的精神让我非常有收获。同样也是老师的严格要求才使得我能够 顺利的完成任务。 指导教师： 年 月 日 目目 录录 问题分析问题分析 1 1 .1 1 1.1 问题描述 .1 1.2 问题的数学模型 .1 1.3 构造数据结构 .1 2 2 系统分析系统分析.2 2 2.1 可行性研究 .2 2.2 系统结构与主要功能模块 .2 3 3 系统设计系统设计.4 4 3.1 系统设计目的与要求 .4 3.2 系统设计内容 .4 3.3 功能算法描述与数据结构说明 .4 4 4 系统实现系统实现.7 7 5 5 调试及运行结

4、果调试及运行结果.1111 6 6 收获和体会收获和体会.1212 附录附录.1313 问题分析问题分析 1 1 1.1 问题描述 设计一个 n 元多项式程序，并完成多项式的乘法运算。从实际的角度出发， 这里设计的程序是基于一元 n 次多项式的数学模型。 1.2 问题的数学模型 在数学上，一个一元多项式 Pn(x)可按升幂写成：Pn(x)=a 0+a1 x+a2 x2 +an xn-1 .它由 n+1 个系数惟一确定，因此，在计算机里，它可用一个线 性表 P 来表示：Pn=(a0,a1,a2,an)每一项的指数 i 隐含在其系数 ai 的序号里。 多项式的乘法规则：多次运用单项式与多项式相乘的

5、法则得到的计算时 (a+b)(m+n)，先把(m+n)看成一个单项式，(a+b) 是一个多项式，运用单项式与 多项式相乘的法则，得到(a+b)(m+n)=a(m+n)+b(m+n),然后再次运用单项式与多 项式相乘的法则。 1.3 构造数据结构 通过分析多项式的特征，不难看出多项式是由单项式构成的，而每个单项 式都具有系数和指数，当系数为 0 时，该项就失去了意义，在计算机内要表示 一个多项式，至少以下数据信息：系数信息、指数信息和指向下一个单项式的 指针。通过指针，我们就可以把多个单项式连接起来，形式一个多项式，需要 说明的是从广义的角度讲，单项式也是一个多项式。基于以上的分析，我们定 义多

6、项式的数据结构为如下结构体形式： typedef struct Polynomial float coef;/系数 int expn;/指数 struct Polynomial *next;/指向下一个结点 *Polyn,Polynomial; /Polyn 为结点指针类型 2 系统分析 2.1 可行性研究 该程序主要从技术的角度来分析可行性。技术上的可行性研究主要分析技 术条件能否顺利完成开发工作，硬、软件能否满足开发者的需要等。该系统采 用了 Windows XP 操作系统结合 Visual C+ 6.0,TC 2.0 等软件开发平台已成熟可 行。硬件方面，科技飞速发展的今天，硬件更新的速

7、度越来越快，容量越来越 大，可靠性越来越高，其硬件平台也比较能满足此系统的需要。此外，还有经 济可行性，用户使用可行性，法律可行性等可行性研究，这里从简省去。 2.2 系统结构与主要功能模块 从实现多项式式运算过程的角度来分析，至少需要这样一些子功能模块。 如： 1. 多项式创建功能； 2. 多项式运算功能； 3. 操作界面显示功能； 4. 销毁多项式的功能； 5. 多项式复制功能等。 系统的整体流程和主要功能模块如图 2-1 所示 开始 输入选择 显示 加法 显示功能表 输入 pa 系数、指数 退出 输入 pb 系数、指数 减法 乘法 i=m i=m im icoef=0) free(p);

8、 /系数为 0 的话释放结点 else/如果系数不为 0 Polyn q1,q2; q1=h;q2=h-next; while(q2 q2=q2-next; if(q2 free(p); if(!q2-coef) /系数为 0 的话释放结点 q1-next=q2-next; free(q2); else /指数为新时将结点插入 p-next=q2; q1-next=p; /Insert 3. Polyn AddPolyn(Polyn pa,Polyn pb) 该函数有两个参数，其类型均为 polyn，分别表示要相加的两个不同的多项式。其计算的结果存放在新建的 pc 所指向的链表中。函数中调用了

9、 int compare(Polyn a,Polyn b)的结果。下面是实 现加法的关键代码： Polyn AddPolyn(Polyn pa,Polyn pb)/求解并建立多项式 a+b，返回其头指 针 Polyn qa=pa-next; Polyn qb=pb-next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial);/建立头结点 hc-next=NULL; headc=hc; while(qa|qb) qc=(Polyn)malloc(sizeof(struct Polynomial); switch(comp

10、are(qa,qb) case 1: qc-coef=qa-coef; qc-expn=qa-expn; qa=qa-next; break; case 0: qc-coef=qa-coef+qb-coef; qc-expn=qa-expn; qa=qa-next; qb=qb-next; break; case -1: qc-coef=qb-coef; qc-expn=qb-expn; qb=qb-next; break; /switch if(qc-coef!=0) qc-next=hc-next; hc-next=qc; hc=qc; else free(qc);/当相加系数为 0 时，

11、释放该结点 /while return headc; /AddPolyn int compare(Polyn a,Polyn b) if(a else if(!a|a-expnexpn) return -1; else return 0; else if(!a/a 多项式已空，但 b 多项式非空 else return 1;/b 多项式已空，但 a 多项式非空 /compare 4. Polyn MultiplyPolyn(Polyn pa,Polyn pb) 该函数同加法一样，拥有相同的 参数并且同样将新建立的链表 pf 的指针返回，用来实现输出乘法结果。下面给 出关键代码： Polyn M

12、ultiplyPolyn(Polyn pa,Polyn pb) Polyn hf,pf; Polyn qa=pa-next; Polyn qb=pb-next; hf=(Polyn)malloc(sizeof(struct Polynomial);/建立头结点 hf-next=NULL; for(;qa;qa=qa-next) for(qb=pb-next;qb;qb=qb-next) pf=(Polyn)malloc(sizeof(struct Polynomial); pf-coef=qa-coef*qb-coef; pf-expn=qa-expn+qb-expn; Insert(pf,h

13、f);/调用 Insert 函数以合并指数相同的项 return hf; /MultiplyPolyn 5. 其它函数的介绍请参见附录中详细代码. 5 调试及运行结果 该程序在 VC6.0 中调试通过，没有错误和警告，运行结果经过检验为正确。 以下图 5-1 即为该程序运行结果效果图。图中采用的是计算多项式 4x5+2x2+3x 和 x10+7x2 的加减乘三种运算进行演示： 算法调试，运行结果图 输入两个多项式的每 一项值 提示功能选择 进行三则运算的结果 6 收获和体会 通过这次课程设计练习，使我更深刻地理解了语言的精髓-指针的使 用。完成整个程序设计有，对指针掌握的更加熟练。 同时通过直

14、接对链表的操作，加深了对数据结构的理解和认识。并在完成 课程设计的过程作主动查阅了相关资料，学到了不少课本上没有的技术知识。 经过这次课程设计，我深刻认识到算法在程序设计中的重要性，一个完整 的程序总是由若干个函数构成的，这些相应的函数体现了算法的基本思想。 编程是一件枯燥乏味工作，但是只要认真专研，我们会从中学到很多在课 本上学不到或者无法在课堂上掌握的知识，同时也能从中感受到编程的乐趣。 兴趣是可以培养的，只要坚持下去，面对困难我们总能够找到解决问题的方法。 计算多项式的加、减、乘法运算-该程序虽然不是很大，这次还是由几 位同学合作才完成这一任务。在这个小组中我是组长，通过分工与合作，使我

15、 充分认识到在项目团队开发过程中合作的重要性，也更加理解了沟通协作能力 在软件开发行业中的重要性。 另外也需要提出的是在这次程序设计的过程中，非常感谢老师对我们的耐 心指导。老师在教学过程中表现出来的对学术专研一丝不苟的精神让我非常有 收获。同样也是老师的严格要求才使得小组成员能够顺利的完成任务。 附录 #include #include /*/ typedef struct Polynomial float coef;/系数 int expn;/指数 struct Polynomial *next;/指向下一个结点 *Polyn,Polynomial; /Polyn 为结点指针类型 /*/

16、void Insert(Polyn p,Polyn h) if(p-coef=0) free(p); /系数为 0 的话释放结点 else/如果系数不为 0 Polyn q1,q2; q1=h;q2=h-next; while(q2 q2=q2-next; if(q2 free(p); if(!q2-coef) /系数为 0 的话释放结点 q1-next=q2-next; free(q2); else /指数为新时将结点插入 p-next=q2; q1-next=p; /Insert /*以下函数实现建立一个多项式*/ Polyn CreatePolyn(Polyn head,int m)/建

17、立一个头指针为 head、项数为 m 的一元 多项式 /在主程序初始时，先输入的多项式中的项数 m、n 在这里为 m。主程序中 的 pa、pb 在此为 head int i;/用来计数 Polyn p;/定义一个 p 链表 p=head=(Polyn)malloc(sizeof(struct Polynomial); head-next=NULL; for(i=0;icoef, Insert(p,head); /调用 Insert 函数插入结点 return head; /CreatePolyn /*以下函数实现多项式的销毁*/ void DestroyPolyn(Polyn p)/销毁多项式

18、 p Polyn q1,q2; q1=p-next; q2=q1-next; while(q1-next) free(q1); q1=q2;/指针后移 q2=q2-next; /*以下函数实现显示输出多项式* */ void PrintPolyn(Polyn P) Polyn q=P-next; int flag=1;/项数计数器 if(!q) /若多项式为空，输出 0 putchar(0); printf(n); return; while (q) if(q-coef0 /系数大于 0 且不是第一项 if(q-coef!=1 if(q-expn=1) putchar(X); else if(

19、q-expn) printf(X%d,q-expn); else if(q-coef=1) if(!q-expn) putchar(1); else if(q-expn=1) putchar(X); else printf(X%d,q-expn); if(q-coef=-1) if(!q-expn) printf(-1); else if(q-expn=1) printf(-X); else printf(-X%d,q-expn); q=q-next; flag+; /while printf(n); /PrintPolyn /*在下面的辅助乘法和加法运算*/ int compare(Poly

20、n a,Polyn b) if(a else if(!a|a-expnexpn) return -1; else return 0; else if(!a/a 多项式已空，但 b 多项式非空 else return 1;/b 多项式已空，但 a 多项式非空 /compare /*以下函数实现加法*/ Polyn AddPolyn(Polyn pa,Polyn pb)/求解并建立多项式 a+b，返回其头指针 Polyn qa=pa-next; Polyn qb=pb-next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomia

21、l);/建立头结点 hc-next=NULL; headc=hc; while(qa|qb) qc=(Polyn)malloc(sizeof(struct Polynomial); switch(compare(qa,qb) case 1: qc-coef=qa-coef; qc-expn=qa-expn; qa=qa-next; break; case 0: qc-coef=qa-coef+qb-coef; qc-expn=qa-expn; qa=qa-next; qb=qb-next; break; case -1: qc-coef=qb-coef; qc-expn=qb-expn; qb

22、=qb-next; break; /switch if(qc-coef!=0) qc-next=hc-next; hc-next=qc; hc=qc; else free(qc);/当相加系数为 0 时，释放该结点 /while return headc; /AddPolyn /*以下函数实现减法*/ Polyn SubtractPolyn(Polyn pa,Polyn pb)/求解并建立多项式 a+b，返回其头指针 Polyn h=pb; Polyn p=pb-next; Polyn pd; while(p) /将 pb 的系数取反 p-coef*=-1; p=p-next; pd=AddP

23、olyn(pa,h); for(p=h-next;p;p=p-next) /恢复 pb 的系数 p-coef*=-1; return pd; /SubtractPolyn /*以下函数实现乘法*/ Polyn MultiplyPolyn(Polyn pa,Polyn pb)/求解并建立多项式 a*b，返回其头指针 (该函数实现乘法) Polyn hf,pf; Polyn qa=pa-next; Polyn qb=pb-next; hf=(Polyn)malloc(sizeof(struct Polynomial);/建立头结点 hf-next=NULL; for(;qa;qa=qa-next)

24、 for(qb=pb-next;qb;qb=qb-next) pf=(Polyn)malloc(sizeof(struct Polynomial); pf-coef=qa-coef*qb-coef; pf-expn=qa-expn+qb-expn; Insert(pf,hf);/调用 Insert 函数以合并指数相同的项 return hf; /MultiplyPolyn /*主函数实现显示与功能选择*/ int main() int m,n,flag=0;/m、n 为分别为 a、b 两个多项式的项数 Polyn pa=0,pb=0,pc,pd,pf;/定义各式的头指针，pa 与 pb 在使用前付初值 NULL /pc 头指针所在的多项式用在加法