1、数据结构实验报告实验一：一元多项式相加姓 名： 周 成 学 号： 13083511 专 业： 软件工程 任 课 教 师： 马慧珠 2013 年 12 月 01 日1.实验名称：一元多项式相加2.实验目的: 如何使用 C 语言实现链表的说明、创建以及结点的插入和删除等操作。3.实验要求：对一元多项式能实现输入、输出，以及两个一元多项式相加及结果显示。4.实验内容：一元多项式的表示在计算机内用链表来实现，同时为了节省存储空间，只存储其中非零的项，链表中的每个节点存放多项式的系数非零项。它包含三个域，分别存放多项式的系数，指数，以及指向下一个项的指针。根据一元多项式相加的运算规则：对于两个一元多项式
2、中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项，对于两个一元多项式中所有指数不相同的项，则分别复抄到“和多项式”中去。核心算法 PolyAdd 是把分别由 pa 和 pb 所指的两个多项式相加，结果为pa 所指的多项式。运算规则如下：相加时，首先设两个指针变量 qa 和 qb分别从多项式的首项开始扫描，比较 qa 和 qb 所指结点指数域的值，可能出现下列三种情况之一：（1）qa-exp 大于 qb-exp,则 qa 继续向后扫描。（2）qa-exp 等于 qb-exp,则将其系数相加。若相加结果不为零，将结果放入 qa-coef 中，并删除 qb 所指结点，否则同
3、时删除 qa 和 qb 所指结点。然后 qa、qb 继续向后扫描。（3）qa-exp 小于 qb-exp,则将 qb 所指结点插入 qa 所指结点之前，然后qa、qb 继续向后扫描。扫描过程一直进行到 qa 或 qb 有一个为空为止，然后将有剩余结点的链表接在结果表上。所得 pa 指向的链表即为两个多项式之和。5.实验程序代码及运行结果：#include “stdafx.h“#include #include #include #include #define NULL 0typedef struct NODEfloat coef; /系数yint expn; /指?数ystruct NODE
4、 *next; NODE;NODE *Creat(int n);void print(NODE *head);NODE *AddPolyn(NODE *head1, NODE *head2);NODE *Delfirst(NODE *head, NODE *q);void InsertBefore(NODE *p1, NODE *p2);int compare(int a, int b);/*创建链表*/NODE *Creat(int n)NODE *current, *previous, *head;int i;head = (NODE *)malloc(sizeof(NODE); /*创建
5、头结点?*/previous = head;for(i = 0; i coef, previous-next = current;previous = current; previous-next = NULL;return head;/*一?元a多项?式?的?想?加，?总体?考?虑?，?可分?qa的?指?数y比qb小?，?或等于pb(如?果?系数y相加等于0和不?等于0),或大于pb里?面?由InsertBefore和Delfirst两?个?小?模块组成一?部?分?*/NODE *AddPolyn(NODE *head1, NODE *head2)NODE *ha, *hb, *qa, *q
6、b;int a, b;float sum;ha = head1; /*ha和hb指?向头结点?*/hb = head2;qa = ha-next; /*qa和qb指?向头结点?的?下?一?个?结点?*/qb = hb-next;while(qa b = qb-expn;switch(compare(a, b) case -1 : /*qa-expn expn*/ha = qa;qa = qa-next;break;case 0 :sum = qa-coef + qb-coef; /*系数y的?和*/if(sum != 0.0) /*如?果?不?是?0.0*/qa-coef = sum; /*改
7、?变?系数y*/ ha = qa; else free(Delfirst(ha, qa); free(Delfirst(hb, qb);qa = ha-next; qb = hb-next; /*qb释放?后要a重?新?赋3值*/break;case 1 : /*如?果?qa- expn qb - expn*/ Delfirst(hb, qb);InsertBefore(ha, qb); /*把?qb插?入?到?ha下?一?个?结点?之?前*/qb = hb-next;ha = ha-next;break;if(qb)ha-next = qb; /*插?入?剩余的?pb*/free(head2
8、);return head1;/*比较?*/int compare(int a, int b)if(a b)return 1;elsereturn 0;/*删?除y结点?q*/NODE *Delfirst(NODE *p1, NODE *q)p1 - next = q - next;return (q);/*插?入?结点?,引y入?结点?p,可以?让?p插?入?到?p2和p1之?间?*/void InsertBefore(NODE *p1, NODE *p2)NODE *p;p = p1-next;p1-next = p2;p2-next = p;/*打印?,为a了?美观?程序分?开a打印?*
9、/void print(NODE *head)NODE *current;current = head-next;while(current-next != NULL)printf(“%0.f * x%d + “, current-coef, current-expn);current = current - next;printf(“%0.f * x%d“, current-coef, current-expn);/system（“pause“);int main()NODE *head1, *head2, *head3;int n1, n2;printf(“请?输?入?你?需要a的?多项?
10、式?的?项?数y n1 : “);scanf(“%d“, head1 = Creat(n1);printf(“第一?个?多项?式?的?显?示? : n“);print(head1);printf(“n请?输?入?你?需要a的?多项?式?的?项?数y n2 : “);scanf(“%d“, head2 = Creat(n2);printf(“n第二t个?多项?式?的?显?示? : n“);print(head2);head3 = AddPolyn(head1, head2);printf(“n合?并后的?多项?式?的?显?示? : n“);print(head3);printf(“n“);运行结
11、果：实验数据 1 如图：输入一个四次二项式 X3+2X4，一个五次二项式X4+2X5，输出如图：实验数据 2 如图：输入一个五次四项式 X2+X3+X4+X5，还有一个五次五项式 1+X+X3+2X4+2X5 输出如图所示实验数据 3 如图：输入一个七次三项式 1+2x5+3X7，还有一个五次四项式1+2X2+3X4+4X5,输出如图：6.实验总结本来我对编程很没有信心，做这样一个课程设计感觉有点吃力，虽然有些人觉得很简单，但是我还是坚持做下来了，我不断的看书，翻阅资料，询问同学，上网搜索，总算有模有样地把这个程序编的能运行了。其次，这次编程是我更多地理解掌握了线性链表的逻辑机构和物理特性。对学过的知识有了很好的巩固。困难还是很多的，比如初次运行的时候，好几十个错误，当时真的感到非常崩溃。幸亏我没有放弃，才最终完成。长舒一口气。最后，通过这次编程，不仅仅考察了我对知识的掌握，更重要的是锻炼了我的思维能力和耐心，在最困难的时候没有放弃，今天才能如此舒心。
