数据结构上机实习报告.doc

数据结构上机实习报告实验题目：一元多项式班级：193121姓名：邹冠宏学号：20121002758指导老师：郭艳完成日期：2013/9/30一 问题分析1. 问题描述设计一个n元多项式程序，并完成多项式的加法，乘法运算。从实际的角度出发，这里设计的程序是基于一元n次多项式的数学模型。2、 功能需求1)构造一个空的多项式。2)多项式插入新的一项。3）计算多项式的值。4）打印多项式。5）多项式合并同类项。6）多项式加法。7）多项式乘法。8)多项式减法二、概要设计 1问题分析在数学上，一个一元多项式Pn(x)可按升幂写成：Pn(x)=a 0+a1 x+a2 x2 +an xn-1 .它由n+1个系数惟一确定，因此，在计算机里，它可用一个线性表P来表示：Pn=(a0,a1,a2,an)每一项的指数i隐含在其系数ai的序号里。2数据模型设计一个单链表模型，动态分配空间，刻意随时插入新的一项多项式加法规则：两个具有相同指数的项合并，系数为0时把这一项省去，也就是删除了这一节点。多项式的乘法规则：多次运用单项式与多项式相乘的法则得到的计算时(a+b)(c+d)，把(c+d)看成一个单项式，(a+b) 是一个多项式，运用单项式与多项式相乘的法则，得到(a+b)(c+d)=a(c+d)+b(c+d),然后再次运用单项式与多项式相乘的法则。3 构造数据结构通过分析多项式的特征，不难看出多项式是由单项式构成的，而每个单项式都具有系数和指数，当系数为0时，该项就失去了意义，在计算机内要表示一个多项式，至少以下数据信息：系数信息、指数信息和指向下一个单项式的指针。通过指针，我们就可以把多个单项式连接起来，形式一个多项式，基于以上的分析，我们定义多项式的数据结构为如下结构体形式：typedef struct Polynomial float coef;/系数 int expn;/指数 struct Polynomial *next;/指向下一个结点*Polyn,Polynomial; /Polyn为结点指针类型三、详细设计 1一元多项式运算程序具有以下基本功能：1）界面输出，提示如何输入数据。要求先输入多项式的项数。2）创建多项式。接收输入的数据，并保存到链表中。3）显示程序的功能表，允许使用者选择运算类型。4）打印多项式。5）实现加法运算。7）实现乘法运算。6）清除内存内容，销毁创建的链表，退出程序。2功能算法描述与数据结构说明该多项式程序除了main()函数外，主要有以下函数：Polyn CreatePolyn(Polyn head,int m)void Insert(Polyn p,Polyn h)void PrintPolyn(Polyn P)int compare(Polyn a,Polyn b)Polyn AddPolyn(Polyn pa,Polyn pb)Polyn MultiplyPolyn(Polyn pa,Polyn pb)void DestroyPolyn(Polyn p)void CountPolyn(Polyn P,int k)3. 主要功能函数的详细设计1）.main（）函数main函数是用来实现提示使用者输入、显示功能列表、调用其他运算函数实现运算功能。在main（）函数中，定义m、n用来保存两个多项式的项数，pa、pb、pc、pd、pf定义程序所需链表的头指针。在程序开始要求输入两个多项式的项数，随后根据项数创建两个链表以保存多项式，再显示出功能列表后通过输入数字来选择来实现功能的选择，从而达到对整个程序流程进行控制。2）. Polyn CreatePolyn(Polyn head,int m)该函数功能是创建新的多项式链表。int m保存的多项式的项数，使用for语句，控制输入多项式的每一项。若创建的链表长度为m时，将不再提示用户继续输入多项式的系数和指数。因为是从0项开始计算的。在该函数中要用到分配空间的函数malloc()为新建链表分配空间。而空间的长度要用sizeof（）。3）. void Insert(Polyn p,Polyn h)该函数功能：将新的节点p插入到现有链表的后面，并确保多项式的指数exp是升序。将s节点插入到head所指向的链表。在该函数的操作中，要注意指针是如何移动的。对插入的位置要分情况讨论。在头，中，尾三处的插入。4）. int compare(Polyn a,Polyn b)该函数功能：判断两个多项式在同一指数下是否有其中一个为系数为0。根据不同情况来讨论多项式的指数，用来辅助加法和乘法运算。5）. Polyn AddPolyn(Polyn pa,Polyn pb)该函数功能：实现两个多项式pa、pb相加，并将计算结果存储于新建立的pc中，它的原理是将指数相同的单项式相加，系数相加后为0，则pa、pb的指针都后移。在加法计算中要求pa,与pb的幂次序都是升序，否则可能得到错误的结果。该函数调用了int compare(Polyn a,Polyn b)的结果，用来判断多项式在同一指数下a、b是否有为系数为0。同样也使用了malloc()关键字，为新链表创建分配空间。6）. void PrintPolyn(Polyn P)该函数功能：显示多项式链表。在该函数中较复杂的是如何控制链表的输出，尤其是第一项的输出，同时还有符号的控制。在输出第一项时要判断是不是常数项，若是，则不要输出字符x。还有对系数的正负的判断，若是正就输出+，负则直接输出。7）. Polyn MultiplyPolyn(Polyn pa,Polyn pb)函数功能：实现两个多项式相乘，F(X) * H(x) 。计算时运用单项式与多项式相乘的法则，然后再次运用单项式与多项式相乘的法则。对得到多项式进行合并。8）Polyn CountPolyn(Polyn p,int x) 此函数是用来输出多项式的计算结果，要给x赋值，当*next=Null时结束运算，输出结果9）. void DestroyPolyn(Polyn p)该函数的功能是销毁掉创建的两个链表，释放内存。以辅助退出程序。有利于空间空域，如果不释放没用的内存空间的话，内存会被占用，最后导致内存不足，甚至系统崩溃。4各函数的详细设计该程序实现了多项式的创建、多项式的加法、乘法运算以及多项式的清除。为完成这些功能，必须用到一些辅助函数。下面讨论一些重要函数具体实现过程及其参数的含义：1）. Polyn CreatePolyn(Polyn head,int m)该函数的两个参数，head表示为创建的链表的头指针，m表示为链表的长度，即多项式的项数。定义int i计数，当inext=NULL; for(i=0;icoef,&p-expn); Insert(p,head); /调用Insert函数插入结点 return head;/CreatePolyn2). void Insert(Polyn p,Polyn h) 该函数具有两个参数，用来实现链表的顺序排列和合并相同的项。以下是实现插入的关键代码： 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&p-expnexpn) /查找插入位置 q1=q2; q2=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; /Insert3). int compare(Polyn a,Polyn b)此函数是用来比较两个多项式之间的系数大小。 int 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多项式非空 else return 1;/b多项式已空，但a多项式非空/compare4）. Polyn AddPolyn(Polyn pa,Polyn pb) 该函数有两个参数，其类型均为polyn，分别表示要相加的两个不同的多项式。其计算的结果存放在新建的pc所指向的链表中。函数中调用了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(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=qb-next; break; /switch if(qc-coef!=0) qc-next=hc-next; hc-next=qc; hc=qc; else free(qc);/当相加系数为0时，释放该结点 /while return headc;/AddPolyn5）. Polyn MultiplyPolyn(Polyn pa,Polyn pb) 该函数同加法一样，拥有相同的参数并且同样将新建立的链表pf的指针返回，用来实现输出乘法结果。下面给出关键代码：Polyn MultiplyPolyn(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,hf);/调用Insert函数以合并指数相同的项 return hf;/MultiplyPolyn6）. void PrintPolyn(Polyn P)从升序依次输出多项式，void PrintPolyn(Polyn P) Polyn q=P-next; int flag=1;/项数计数器 if(!q) /若多项式为空，输出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-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);/PrintPolyn7）void CountPolyn(Polyn p)float num=0;int x;int i;float k=1;Polyn q=p-next;printf(输入你对x赋的值);scanf(%d,&x);printf(a);if(q=NULL)return;while (q!=NULL)k=k*(q-coef);for(i=0;iexpn);i+)k=k*x;num=num+k;q=q-next;return num;四程序调试1界面显示2功能测试五收获和体会通过这次课程设计练习，我更深刻地理解了语言的精髓-指针的使用。完成整个程序设计有，对指针掌握的更加熟练。同时通过直接对链表的操作，加深了对数据结构的理解和认识。并在完成课程设计的过程作主动查阅了相关资料，学到了不少课本上没有的技术知识。编程是一件枯燥乏味工作，但是只要认真专研，我们会从中学到很多在课本上学不到或者无法在课堂上掌握的知识，同时也能从中感受到编程的乐趣。兴趣是可以培养的，只要坚持下去，面对困难我们总能够找到解决问题的方法。计算多项式的加、乘法运算和计算结果。该程序虽然不是很大，这次我还是由请教了几位同学和参考了网上的类似的题目另外也需要提出的是在这次程序设计的过程中，非常感谢老师对我们的耐心指导。老师在教学过程中表现出来的对学术专研一丝不苟的精神让我非常有收获。六附录#include#include/*/typedef 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/如果系数不为0 Polyn q1,q2; q1=h;q2=h-next; while(q2&p-expnexpn) /查找插入位置 q1=q2; q2=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的一元多项式/在主程序初始时，先输入的多项式中的项数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,&p-expn); Insert(p,head); /调用Insert函数插入结点 return head;/CreatePolyn/*以下函数实现多项式的销毁*/void DestroyPolyn(Polyn p)/销毁多项式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&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-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(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多项式非空 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 Polynomial);/建立头结点 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=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=AddPolyn(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) 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;/MultiplyPolynvoid CountPolyn(Polyn p)/实现多项式的计算float num=0;int x;int i;float k=1;Polyn q=p-next;printf(输入你对x赋的值);scanf(%d,&x);printf(a);if(q=NULL)return;while (q!=NULL)k=k*(q-coef);for(i=0;iexpn);i+)k=k*x;num=num+k;q=q-next;return num;/*主函数实现显示与功能选择*/int main() int m,