多项式加法的链表设计与实现

1、精选优质文档-倾情为你奉上实验名称实验二 多项式加法的链表设计与实现实验方案实验成绩实验日期2012-03-26实 验 室信息系统设计与仿真室I实验操作实验台号班级姓名实验结果 一、 实验目的1、掌握链表的灵活运用；2、学习链表初始化和建立一个新的链表；3、知道怎样去实现链表删除结点操作与插入结点；4、理解链表的基本操作（包括数据域数据的相加）并能灵活运用。二、 实验任务1、设计一个一元多项式的简单计算器，其基本功能有：输入并建立多项式；输出多项式；多项式相加。可利用单链表实现之。2、运用单链表来存储多项式，并且结果链表要用原来的链表空间。用C语言编程实现实验任务要求。三、 实验设计方案1 用

2、单链表存储多项式的结点结构体设计typedef struct polynode /*用单链表存储多项式的结点结构*/ int coef; /*多项式的系数*/ int exp; /*指数*/ struct polynode *next; /*next是struct polynode类型中的一个成员，它又指向struct polynode类型的数据，以此建立链表*/node;/*若定为node,*list;，意即node*与list同为结构指针类型*/2 自定义函数设计node *first =0;int xs=1,zs;while(1)printf(请输入第%d项系数：n,i);scanf(%

3、d,&xs);if(xs=0) break; printf(请输入第%d项指数：n,i);scanf(%d,&zs);p1=(node*)malloc(sizeof(node);p1-coef=xs;p1-exp=zs;p1-next=first1;first1=p1;i+;（2）多项式加法思路：以多项式1为基准，依次取出多项式2中的每一项与多项式1进行指数比较，生成和多项式的结点。（3）输出和多项式p=first;if(p!=NULL) /显示第1项printf(%dX%d,p-coef,p-exp);p=p-next; while(p!=NULL)if(p-zhishu0) /符号位pri

4、ntf(+);printf(%d,p-coef); /系数printf(X%d,p-exp);p=p-next;printf(n);（4）依照上述思路，请重点思考如何编程完成多项式加法程序； 进一步，考虑链表依指数大小升序排列，考虑如何编程实现两个有序多项式链表的加法。3 主函数设计void main()Ploy *pa, *pb;freopen(in.txt,r,stdin);pa=input(); /读入多项式1/output(pa); /输出和多项式pb=input(); /读入多项式2/output(pb); /输出和多项式pa=add(pa,pb); /两个多项式相加output(p

5、a); /输出和多项式四、 测试1、测试数据2、测试结果五、 总结与讨论（可针对实验设计谈体会、谈改进、谈设想，展示你的概括、归纳和创新思维能力，看重的不是你的对与错，而是鼓励你思考和创造！） 附：程序模块的源代码源代码：# include # include # include # include #define LEN sizeof(node)typedef struct polynode /*用单链表存储多项式的结点结构*/ int coef; /*多项式的系数*/ int exp; /*指数*/ struct polynode *next; /*next是struct polynode

6、类型中的一个成员，它又指向struct polynode类型的数据，以此建立链表*/node;/*若定为node,*list;，意即node*与list同为结构指针类型*/node * create(void) /*指针函数，返回指针类型；用尾插法建立一元多项式的链表的函数*/ node *h,*r,*s; int c,e; h=(node *)malloc(LEN); /*建立多项式的头结点，为头结点分配存储空间*/ r=h; /*r指针始终动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/ printf(coef:); scanf(%d,&c); /*输入系数*/ printf(

7、exp: ); scanf(%d,&e); /*输入指针*/ while(c!=0) /*输入系数为0时，表示多项式的输入结束*/ s=(node *)malloc(LEN); /*申请新结点*/ s-coef=c; /*申请新结点后赋值*/ s-exp=e; /*申请新结点后赋值*/ r-next=s; /*做尾插，插入新结点*/ r=s; /*r始终指向单链表的表尾*/ printf(coef:); scanf(%d,&c); printf(exp: ); scanf(%d,&e); r-next=NULL; /*将表的最后一个结点的next置NULL，以示表结束*/ return(h);

8、void polyadd(node *polya, node *polyb)/*一元多项式相加函数，用于将两个多项式相加，然后将和多项式 存放在多项式polya中，并将多项式ployb删除*/ node *p,*q,*pre,*temp; int sum; p=polya-next;/*令p和q分别指向polya和polyb多项式链表中的第一个结点*/ q=polyb-next; pre=polya; /*位置指针，指向和多项式polya*/ while(p!=NULL&q!=NULL) /*当两个多项式均未扫描结束时，执行以下操作*/ if(p-expq-exp) /*若p指向的多项式指数大

9、于q指的指数*/ /*q结点不动，将p结点加入到和多项式中*/ /补充代码. else if(p-exp=q-exp) /*若指数相等，则相应的系数相加*/ sum=p-coef+q-coef; if(sum!=0) /*将p结点加入到和多项式中,删除结点q*/ p-coef=sum; pre-next=p;pre=pre-next;p=p-next; temp=q;q=q-next;free(temp); else /*如果系数和为零，则删除结点p与q，并将指针指向下一个结点*/ /补充代码. else /*若p指数小于q指数*/ /*p结点不动，将q结点加入到和多项式中*/ /补充代码.

10、if(p!=NULL) /*多项式A中还有剩余，则将剩余的结点加入到和多项式中*/ pre-next=p; else /*否则将B的结点加入到和多项式中*/ pre-next=q;void print(node * p) /*输出函数，打印出一元多项式*/ while(p-next!=NULL) p=p-next; printf( %d*x%d,p-coef,p-exp); printf(n );void main() /*主函数*/ node * polya,* polyb; printf(Please input the ploya include coef & exp:n); polya

11、=create(); /*调用建立链表函数，创建多项式A*/ print(polya); printf(Please input the ployb include coef & exp:n); polyb=create(); /*调用建立链表函数，创建多项式B*/ print(polyb); printf(Sum of the poly is:n); polyadd(polya,polyb); /*调用一元多项式相加函数*/ print(polya); /*调用输出函数，打印结果*/ printf(n);void polyadd(node *polya, node *polyb)/*一元多项

12、式相加函数，用于将两个多项式相加，然后将和多项式 存放在多项式polya中，并将多项式ployb删除*/ node *p,*q,*pre,*temp; int sum; p=polya-next;/*令p和q分别指向polya和polyb多项式链表中的第一个结点*/ q=polyb-next; pre=polya; /*位置指针，指向和多项式polya*/ while(p!=NULL&q!=NULL) /*当两个多项式均未扫描结束时，执行以下操作*/ if(p-expq-exp) /*若p指向的多项式指数大于q指的指数*/ /*q结点不动，将p结点加入到和多项式中*/ /补充代码. pre-next=p; else if(p-exp=q-exp) /*若指数相等，则相应的系数相加*/ sum=p-coef+q-coef; if(sum!=0) /*将p结点加入到和多项式中,删除结点q*/ p-coef=sum; pre-next=p;pre=pre-next;p=p-next; temp=q;q=q-next;free(temp); else /*如果系数和为零，则删除结点p与q，并将指针指向下一个结点*/ /补充代码. pre-next=p-next; free(p); p=pr