《数据结构一元多项式加法器课程设计.doc》由会员分享，可在线阅读，更多相关《数据结构一元多项式加法器课程设计.doc（21页珍藏版）》请在三一办公上搜索。
1、数 据 结 构 课 程 设 计 报 告 一元多项式加法器专业: 班 级: 学 号: 姓 名: 指导老师: 目录1.序言31.1关于数据结构31.2数据结构课程设计的目的32 需求分析42.1题目要求42.2题目分析43 概要设计53.1总体解决方案53.2总体功能流程图64 详细设计与实现64.1系统主要函数组成64.2基本函数实现流程75 代码与解析126 调试与操作说明186.1操作说明186.2调试结果19总 结20参 考 文 献201.序 言1.1关于数据结构数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁。该课程的先行课程是计算机基础、程序设计语言、离散数
2、学等，后续课程有操作系统、编译原理、数据库原理、软件工程等。 通过本门课程的学习，我们应该能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力，而且该课程的研究方法对我们学生在校和离校后的学习和工作，也有着重要的意义。数据结构是计算机科学与技术专业的一门核心专业基础课程，在该专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解
3、此数学模型的算法，再进行编程调试，最后获得问题的解答。基于此原因，我们开设了数据结构课程设计。针对数据结构课程的特点，着眼于培养我们的实践能力。实习课程是为了加强编程能力的培养，鼓励学生使用新兴的编程语言。相信通过数据结构课程实践，无论是理论知识，还是实践动手能力，同学们都会有不同程度上的提高。1.2数据结构课程设计的目的通过课程设计题目的练习，强化学生对所学知识的掌握及对问题分析和任务定义的理解，对每到题目作出了相应的逻辑分析和数据结构的选择，通过对任务的分析，为操作对象定义相应的数据结构，以过程化程序设计的思想方法为原则划分各个模块，定义数据的抽象数据类型。分模块对题目进行设计，强化学生对
4、C语言的掌握和对数据结构的选择及掌握。通过程序的编译掌握对程序的调试方法及思想，并且让学生学会使用一些编程技巧。促使学生养成良好的编程习惯， 以及让学生对书本上的知识进行了实践。算法与数据结构这门课是计算机科学中一门综合性的专业基础课。它不仅是计算机学科的核心课程，而且已成为其它理工专业的热门选修课。它又是操作系统、编译原理、数据库原理、算法分析、人工智能、图象处理等专业课程的前导课。具有承上启下的作用。数据结构的研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有着密切的关系。计算机科学各领域及有关的应用软件都要用到数据结构。该课程的目的就是介绍一些最常用的数据结构，阐明数据结构内在
5、的逻辑关系，讨论它们在计算机中的存储表示，并结合各种典型应用说明它们在进行各种运算时的动态性质及实际的执行算法。2. 需求分析2.1题目要求一元多项式加法器【问题描述】 设计一个一元多项式加法器。【基本要求】(1) 输入并建立多项式；(2)两个多项式相加；(3)输出多项式：n, c1, e1, c2, e2, cn , en, 其中，n是多项式项数，ci和ei分别是第 i 项的系数和指数，序列按指数降序排列。(4)计算多项式在x处的值；(5)求多项式的导函数。2.2题目分析在数学上，一个一元多项式Pn(x)可按降幂写成：Pn(x)=a0+a1 x+a2 x2 +an xn-1 .它由n+1个系
6、数惟一确定，因此，在计算机里，它可用一个线性表P来表示：Pn=(a0,a1,a2,an)每一项的指数i隐含在其系数ai的序号里。题中只要求我们求两个多项式的加法，求值，求导和输入输出功能，只要掌握其规律，运用单链表的基本操作就能有效解决。3.概要设计3.1总体解决方案1、任务思路与方法1) 定义线性表的动态分配顺序存储结构;2) 建立多项式存储结构，定义指针*next利用链表实现队列的构造;3) 每次输入一项的系数和指数，可以输出构造的一元多项式;4) 要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为系数coef指数expn指
7、针域next运用尾插法建立两条单链表，以单链表polyn p和polyn h分别表示两个一元多项式a和b，a+b的求和运算等同于单链表的插入问题（将单链表polyn p中的结点插入到单链表polyn h中），因此“和多项式”中的结点无须另生成。2.相关算法： 1）元素类型、结点类型和指针类型：typedef struct Polynomial float coef; /系数 int expn; /指数 struct Polynomial *next;*Polyn,Polynomial;2）建立一个头指针为head、项数为m的一元多项式, 建立新结点以接收数据, 调用Insert函数插入结点:
8、Polyn CreatePolyn(Polyn head,int m) int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial); head-next=NULL; for(i=0;icoef,&p-expn); Insert(p,head); return head;3.2总体功能流程图求一元多项式的加法（a+b）求一元多项式的导函数 开 始输入多项式根据输入创建一元多项式并开始存储输出一元多项式并输入X的值，求一元多项式的值 结 束4. 详细设计与实现4.1系统的主要函数组成1.main()函数main函数用来实现提示使用者
9、输入、显示功能列表、调用其他运算函数实现运算功能。在main()函数中，定义m、n用来保存两个多项式的项数，pa、pb、pc、pd、pf定义程序所需链表的头指针。在程序开始要求输入两个多项式的项数，随后根据项数创建两个链表以保存多项式，再显示出功能列表后通过if语句来实现功能的选择，从而对整个程序流程进行控制。2. Polyn CreatePolyn(Polyn head,int m)该函数功能是创建新的多项式链表。int m保存的多项式的项数，使用for语句，控制输入多项式的每一项。当创建的链表长度为m时，将不再提示用户继续输入多项式的系数和指数。在该函数中要用到分配空间的函数malloc(
10、)为新建链表分配空间。3. void DestroyPolyn(Polyn p)该函数的功能是销毁掉创建的两个链表，释放内存。以辅助退出程序。4. void Insert(Polyn p,Polyn h)该函数功能：将新的节点p插入到现有链表的后面，并确保多项式的指数exp是升序。将s节点插入到head所指向的链表。在该函数的操作中，要注意指针是如何移动的。5. Polyn AddPolyn(Polyn pa,Polyn pb)该函数功能：实现两个多项式pa、pb相加，并将计算结果存储于新建立的pc中，它的原理是将指数相同的单项式相加，系数相加后为0，则pa、pb的指针都后移。在加法计算中要求
11、pa,与pb的幂次序都是升序，否则可能得到错误的结果。该函数调用了int compare(Polyn a,Polyn b)的结果，用来判断多项式在同一指数下a、b是否有为系数为0。同样也使用了malloc()关键字，为新链表创建空间。6. int compare(Polyn a,Polyn b)该函数功能：判断两个多项式在同一指数下是否有其中一个为系数为0。用来辅助加法和乘法运算。7. void PrintPolyn(Polyn P)该函数功能：显示多项式链表。在该函数中较复杂的是如何控制链表的输出，尤其是第一项的输出，同时还有符号的控制。在输出第一项时要判断是不是常数项，若是，则不要输出字符
12、x。8. float ValuePolyn(Polyn pa,float x)该函数功能：求多项式在x处的值，对于指数小于0和大于0的多项式采用不同的算法，最后再把多项式的和输出。9. Polyn Derivation(Polyn head)该函数功能：对多项式求导，对指数和系数分别采用不同的算法，再把结点重新插入一个新的链表。4.2基本函数实现流程1.输出多项式 假设指针p指向多项式的第一项 P所指指数为0，则直接输出系数 p所指指数为1，如果系数即不为1，也不为0，则直接输出系数；如果系数为-1，则输出系数“-”，最后输出“x” p所指指数即不为0，也不为1，如果系数为-1，则输出“-x”
13、和指数，如果系数为1，则输出“x”和指数，否则输出系数、“x”及指数 流程图如下图：开始! NULLp-expn若系数即不为1,也不为0,则直接输出系数;若系数为-1,则输出系数“-”,最后输出“x”01default直接输出系数若系数为-1,则输出“-x”和指数,若系数为1则输出“x”和指数,否则输出系数、“x”及指数输出“+”1P系数0?p-expn01default直接输出系数若系数为-1,则输出“-x”和指数,若系数为1则输出“x”和指数,否则输出系数、“x”及指数若系数即不为1,也不为0,则直接输出系数;若系数为-1,则输出系数“-”,最后输出“x”! NULL0NULL返回out结
14、束p=p-next2.多项式相加根据一元多项式相加的运算规则：对于两个一元多项式中指数相同的项，对应的系数相加，若之和不为零，则构成“和多项式”中的一项；对于两个一元多项式中指数不相同的项，则将指数小的添加到“和的多项式”中去，最后将还没结束的多项式插入到和的多项式中去。开始流程图如下图：a=pa-nextb=pb-nextc=pc-nexta&b指数相同的项，对应的系数相加，若之和不为零，则构成“和多项式”中的一项指数不相同的项，则将指数小的添加到“和的多项式”中将还没结束的多项式插入到和的多项式中结束3.多项式求值 假设指针p指向多项式的第一项，sum2代表整个多项式的值（开始赋值为0），
15、sum1代表一项的值（开始赋值为1） 每一项求法：指数为n，则x连乘n次，得到sum1,然后再用sum1乘系数最后将每一项加到sum2中。流程图如下图：p=pa-next开始sum1=每一项的值sum2+=sum1p=p-next返回sum2结束NULL! NULLsum1=1p4.多项式求导 假设p指向多项式A 如果该多项式为常数，则p指向下一项 否则系数=系数*指数，指数=指数-1 将产生的新的项插入到新的多项式B中，p指向下一项流程图如下图：开始Term *p,*q,*xp=head-nextpLp=p-next结束NULL! NULL0系数=系数*指数,指数=指数-1将产生的新的项插入
16、到新的多项式B中,p指向下一项1p-expn=o5. 代码与解析#include#includetypedef struct Polynomial float coef; int expn; struct Polynomial *next;*Polyn,Polynomial; /Polyn为结点指针类型/*插入多项式中的因子*/void Insert(Polyn p,Polyn h) if(p-coef=0) free(p); /系数为0的话释放结点 else Polyn q1,q2; q1=h;q2=h-next; while(q2&p-expnexpn) /查找插入位置 q1=q2; q2
17、=q2-next; if(q2&p-expn=q2-expn) /将指数相同相合并 q2-coef+=p-coef; 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)/建立一个头指针为head、项数为m的一元多项式 int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial); h
18、ead-next=NULL; for(i=0;icoef,&p-expn); Insert(p,head); /调用Insert函数插入结点 return head;/CreatePolyn/*删除多项式*/void DestroyPolyn(Polyn 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) /若多项式为空，输
19、出0 putchar(0); printf(n); return; while (q) if(q-coef0&flag!=1) putchar(+); /系数大于0且不是第一项 if(q-coef!=1&q-coef!=-1)/系数非1或-1的普通情况 printf(%g,q-coef); if(q-expn=1) putchar(X); else if(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-exp
20、n); 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);/PrintPolynint compare(Polyn a,Polyn b) if(a&b) if(!b|a-expnb-expn) return 1; else if(!a|a-expnexpn) return -1; else return 0; else if(!a&b) return -1;/a多项式已空，但b多项式非空 e
21、lse 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 Polynomial);/建立头结点 hc-next=NULL; headc=hc; while(qa|qb) qc=(Polyn)malloc(sizeof(struct Polynomial); switch(compare
22、(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时，释放该结点
23、 /while return headc;/AddPolyn/*求多项式在X处的值*/float ValuePolyn(Polyn pa,float x)/求多项式a在X处的值Polyn p;int i;float t;float sum=0; for(p=pa-next;p;p=p-next) t=1; for(i=p-expn;i!=0;) if(icoef*t; return sum; /*多项式求导函数*/Polyn Derivation(Polyn head) /求解并建立导函数多项式，并返回其头指针 Polyn q=head-next,p1,p2,hd; hd=p1=(Polyn)
24、malloc(sizeof(struct Polynomial);/建立头结点 hd-next=NULL; while(q) if(q-expn!=0) /该项不是常数项时 p2=(Polyn)malloc(sizeof(struct Polynomial); p2-coef=q-coef*q-expn; p2-expn=q-expn-1; p2-next=p1-next; /连接结点 p1-next=p2; p1=p2; q=q-next; return hd;/*主函数*/int main() int m,n,flag=0; float x,y; Polyn pa=0,pb=0,pc,pd
25、;/定义各式的头指针，pa与pb在使用前付初值NULL /输出菜单 printf(欢迎使用一元多项式加法器n); printf(*n); printf(操作提示：nt1.输入多项式a和bnt2.输出多项式a和bnt3.输出多项式a+bnt4.输出多项式a在x处的值nt5.输出多项式a的导函数n); printf(t6.退出n*n); for(;flag=0) printf(执行操作(输入16)：); scanf(%d,&flag); if(flag=1) printf(请输入a的项数:); scanf(%d,&m); pa=CreatePolyn(pa,m);/建立多项式a printf(请输
26、入b的项数:); scanf(%d,&n); pb=CreatePolyn(pb,n);/建立多项式b if(flag=2) printf(多项式a：);PrintPolyn(pa); printf(多项式b：);PrintPolyn(pb);continue; if(flag=3) pc=AddPolyn(pa,pb); printf(输出多项式a+b：);PrintPolyn(pc); DestroyPolyn(pc);continue; if(flag=4) printf(请输入X的值： ); scanf(%f,&x); printf(所求多项式值为：%.3fn,ValuePolyn(p
27、a,x); continue; if(flag=5) pd=Derivation(pa); printf(多项式a的导函数为：); PrintPolyn(pd); DestroyPolyn(pd); continue; if(flag=6) break; if(flag6) printf(Error!n);continue; /for DestroyPolyn(pa); DestroyPolyn(pb); return 0;6 调试与操作说明6.1操作说明1. 先选择功能，输入（16），2. 输入1，输出两个多项式a与b 。3. 输入2，输出两个多项式a与b 。3.输入3，输出多项式a+b 。
28、4.输入4，输出多项式a在x处的值 。5.输入5，输出多项式a的导函数。6.输入6，退出 。根据提示逐个输入即可。6.2调试结果由上述一系列操作之后得到的运行解过下图所示：由上述一系列操作之后得到的结果的输出格式完全按照题目要求输出，结果也完全符合一元多项式的加法、求值、求导过程后的结果一致，可见整个系统的流程和算法是正确的，因此本系统有一定的可行性。总结通过这次课程设计练习，使我更深刻地理解了C语言的精髓-指针的使用。完成整个程序设计后对指针掌握的更加熟练。同时通过直接对链表的操作，加深了对数据结构的理解和认识。并在完成课程设计的过程作主动查阅了相关资料，学到了不少课本上没有的技术知识。经过
29、这次课程设计，我深刻认识到算法在程序设计中的重要性，一个完整的程序总是由若干个函数构成的，这些相应的函数体现了算法的基本思想。编程是一件枯燥乏味工作，但是只要认真钻研，我们会从中学到很多在课本上学不到或者无法在课堂上掌握的知识，同时也能从中感受到编程的乐趣。兴趣是可以培养的，只要坚持下去，面对困难我们总能够找到解决问题的方法。在实际的上机操作过程中，不仅是让我们了解数据结构的理论知识，更重要的是培养解决实际问题的能力，所以相信通过此次实习可以提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础。另外也需要提出的是在这次程序设计的过程中，非常感谢老师对我们的耐心指导。老师在教学过程中表现出来的对学术专研一丝不苟的精神让我非常有收获。同样也是老师的严格要求才使得小组成员能够顺利的完成任务。参 考 文 献1.朱若愚.数据结构M.北京: 电子工业出版社, 2004.1:44-552.严蔚敏,吴伟民.数据结构(C语言版)M. 北京:清华大学出版社, 2007.4：39-433.赵文静. 数据结构与算法M. 北京:科学出版社，2005.8：41-654.刘大有.数据结构M. 北京：高等教育出版社, 2001.3：39-48
