一元多项式相加数据结构实验一-1307班谭淇蔚

1、中南大学数据结构与算法课程实验实验报告题 目 实验一 线性表的操作 学生姓名 谭淇蔚 学生学号 3901130721 专业班级 软件工程1307班 完成日期 2014年3月31日星期一 实验一 线性表的操作（一元多项式相加）1. 需求分析 我们使用计算机处理的对象之间通常存在着的是一种最简单的线性关系，这类数学模型可称为线性的数据结构。而数据存储结构有两种：顺序存储结构和链式存储结构。线性表是最常用且最简单的一种数据结构。所以我们做的是实验一-线性表的操作。实验的目的是掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算以及熟练运用掌握的线性表的操作

2、，实现一元n次多项式的加法运算。学习实现一元n次多项式的加法是符号多项式的操作，是表处理的典型用例，需要注意的是：顺序存储结构指的是用数组方法，使用数组方法实现时，在插入和删除的方面，数组不如链表灵活，方法复杂，删除其中一个需要将其后的数组元素改变位置，使其数组保持原有的顺序结构，在查找方面较链表简单，只需要知道其下标就可以知道。链接存储结构指的是用链表方法,值得注意的是，删除和插入较为灵活，不需要变动大多数元素，但是查找过程相对于数组这种顺序存储结构来说较为复杂，耗时巨大。我们要学习的是通过对两种方法基本操作的掌握来做到实现一元n次多项式的相加减。 我们程序的任务是：能进行简单的线性表操作（

3、插入、删除、查找）以及线性表合并等运算。能通过这些基本操作实现一元多项式相加。明确规定：输入的形式：按照提示（比如：“请您输入第一个结构体数组的项数（不超过50项）：”、“请您输入第二个结构体数组的项数（不超过50项）：”、“请输入第n项的系数”、“请输入第n项的指数”等等），先输入多项式的项数，之后顺次输入每一项的系数与指数。输入值的范围：项数没有要求，但不能过于巨大；系数取为float型数据，指数取为int型数据，输出的形式：按照提示（比如：“您输入的第一个多项式为：”、“您输入的第二个多项式为：”等等），会输出原输入的多项式和经过排序和合并之后的降幂型多项式。同时，系数会以保留小数点后两

4、位数字的形式输出；若指数输入时为小数，则输出时会自动截取其整数部分。程序所能达到的功能：程序可以对输入的序列紊乱的多项式进行加工，使之按照降幂排列，之后对两多项式进行加法运算（包括系数为负的加法），最后输出最终的多项式。测试数正确数据：输入：2*X3+2*X6+2*X7+2*X8+2*X10 和 - 3*X10+4*X8+2*X7+3*X5+3*X3输出：7.00*X2+8.00*X1+2.00错误数据：输入：-8*X1.5+4*X2 和 3*X2+12*X1.6输出：7.00*X2+4.00*X12概要设计（1）链接存储结构：struct node float coef; int expo;

5、 struct node *next;chainLink;函数主体部分，利用头指针进行链表操作，利用display进行打印出屏幕，利用order函数对其进行降幂排序，当两个多项式已经创建完毕时，利用add函数进行两个多项式相加。（2）顺序存储结构抽象数据类型为结构体数组：struct polyfloat coef;int exp;函数主体部分，会引用指针进行参数传递，在函数主体部分定义了3个结构体数组同时定义其所对应的指针，利用用户输入，利用print函数将其打印出来，再用sort函数将其降序排列，做完两个结构体数组后，接着利用add函数将两个多项式相加。3详细设计（1）链接存储结构：结构体定

6、义：struct nodeint coef; /系数 int exp; /指数 struct node * next;/指针域chainLink;/创建chainLink的node结点对象（值得注意的是，与顺序存储结构不同的是，内部还定义了指针域）功能函数介绍：struct node *create() /定义建立多项式函数，并返回链表头指针struct node *h = NULL, *q, *p;/定义结构体头指针h，标记指针p和q，p是创造新节点的标记指针，q是链接链表的指针；int i = 1, N; /定义多项式的项数N及标记数icout N;p = 0;/指针初始化；q = 0;/

7、本地指针初始化；for (; i = N; i+)p = (struct node *)malloc(sizeof(chainLink); /为一个新节点分配空间cout 请输入第 i (*p).coef;cout 请输入第 i (*p).exp;if (i = 1) h = p; q = p; /建立头节点elseq-next = p;q = p;q-next = NULL;/p,q都成为新链表的尾指针；p-next = NULL;return h;PS：值得注意的是，我在里面P，q指针均使其值为0，是让其为空指针，对其进行初始化，在visual studio 2013版中，如果不进行初始化

8、，会被报错。打印函数display:void display(struct node *h)struct node *p; /定义标记指针，输出链表p = h;while (p != NULL)if (p-coef = 0)struct node *d;d = h;while (d-next != p)d = d-next;d-next = p-next;p = p-next;/删去系数为0的节点；elseif (p-coefexp = 0) cout (*p).coef +;else cout ( (*p).coef ) *X (*p).exp exp = 0) cout (*p).coef

9、 exp!=0&p-exp!=1)cout (*p).coef *X (*p).exp +;else cout (*p).coef next;cout next; /将原来的链表建立成待排序链表h1-next = NULL; /截断第一个原链表中的节点while (h2 != NULL)q = h1;p = q-next;t = h2; /从待排序链表中选出一个节点准备插入到新链表中h2 = h2-next; /移动待排序链表的头指针，便于进行下一次挑选t-next = NULL;if (t-expq-exp) /应插入头指针之前的情况t-next = q;h1 = t;continue;if

10、 (p = NULL&t-exp exp) q-next = t; /应插入表尾的情况while (p != NULL)if (t-expp-exp)q-next = t;t-next = p;break;elseq = q-next;p = p-next;if (p = NULL) q-next = t;return h1; /新链表即为按降幂顺序排好的链表，返回其头指针Order函数其实是利用了3个头指针，具体操作看代码即可，其实很容易懂。 相加函数add：struct node *add(struct node *h1, struct node *h2) /定义加法函数，并返回结果的链表

11、的头指针struct node *p, *q, *head, *r; /定义结构体头指针head和标记指针p,q,rp = h1;q = h2;head = (struct node *)malloc(sizeof(chainLink); /为结果多项式分配头指针if (p-exp = q-exp) head = h1; p = p-next; elseif (p-expexp) head = h2; q = q-next; else p-coef = p-coef + q-coef; head = p; p = p-next; q = q-next; r = head;while (p !=

12、 NULL&q != NULL)if (p-expq-exp) r-next = p; p = p-next; elseif (p-expexp) r-next = q; q = q-next; else p-coef = p-coef + q-coef; r-next = p; p = p-next; q = q-next; r = r-next;if (p = NULL&q = NULL) r-next = NULL;elseif (p = NULL) r-next = q;if (q = NULL) r-next = p;return head;add函数大部分其实和老师PPT思路差不多

13、。比较两个多项式中指数大小，然后分别对其余两个进行操作。（2）顺序存储结构结构体定义：struct polyfloat coef;int exp;/结构体数组定义主函数结构体数组的创建以及导引指针的创建：poly p50, *po=p;poly p150, *po1=p1;poly p2100, *po2=p2;/定义三个结构体数组，用于存放多项式,定义三个指针变量；print函数以及参数调用代码：void print(struct poly *s, int n)for (int i = 0; i n; i+)if (i = n - 1)cout (*s)i.coef *X (*s)i.exp

14、;elsecout (*s)i.coef *X (*s)i.exp+;/输出数组主函数中调用print函数的具体形式：print(&po, n1);sort函数的代码：void sort(struct poly *s, int n)int i, temp1, j; /定义数组中的循环标记数据i与j，和整型标记temp1float temp2; /定义单精度型标记temp2for (i = 0; in - 1; i+)for (j = i + 1; j(*s)i.exp)temp1 = (*s)j.exp;(*s)j.exp = (*s)i.exp;(*s)i.exp = temp1;temp2

15、 = (*s)j.coef;(*s)j.coef = (*s)i.coef;(*s)i.coef = temp2;for (i = 0; in - 1; i+)if (*s)i.exp = (*s)i + 1.exp)(*s)i + 1.coef = (*s)i.coef + (*s)i + 1.coef;if (i = n - 2)(*s)i.coef = (*s)i + 1.coef;(*s)i + 1.coef = 0;elsefor (j = i; j(*s1)j.exp)(*s2)p.coef = (*s)i.coef;(*s2)p.exp = (*s)i.exp;i+;else(*

16、s2)p.coef = (*s1)j.coef;(*s2)p.exp = (*s1)j.exp;j+;if (i = n1 | j = n2)p+;break;if (i = n1)for (; jn2; j+)(*s2)p.coef = (*s1)j.coef;(*s2)p.exp = (*s1)j.exp;p+;elsefor (; in1; i+)(*s2)p.coef = (*s)i.coef;(*s2)p.exp = (*s)i.exp;p+;for (m = 0; mp; m+)if (*s2)m.coef0)if (*s2)m.exp = 0)cout (*s2)m.coef +

17、;else cout (*s2)m.coef *X (*s2)m.exp 0)if (*s2)m.exp = 0)cout (*s2)m.coef +;else /printf( %.2f*X%d +, dxs2m.coef, dxs2m.exp);cout (*s2)m.coef *X (*s2)m.exp +;cout b b n;add函数在主函数中的调用：add(&po, &po1, &po2, n1, n2);4调试分析（1）链接存储结构：设计过程，注意指针保护，如果一步不小心，容易造成头指针消失，所以需要指针来保护头指针，至于其他方面倒是没有什么问题。总的来说，代码长度170，算不

18、上特别多，该有的功能也考虑到了。（2）顺序存储结构在设计过程中，发现如果不采用指针参数传递结构体数组，而是对单个多项式进行单个功能操作，即对于每一个多项式都会用同功能的函数，只不过不同名称来实现，这样造成代码冗长，我试过写出了286行的代码，但visual studio2013无法编译如此冗长的代码，所以我决定使用指针导向进行优化，优化后的代码行数是162行，少了100多行，实现功能也比之前多了一些。虽然没法像我第一次写那286行的代码可以实现动态创建结构体数组，但我认为，这162行的代码的结构体数组50个大小，理应足够计算，如果要更大，建议修改代码中创建结构体数组大小的尺寸。总体来说，还算不

19、错，知识经过一个寒假忘得七零八落，感觉我还没有完全掌握这类知识，等有时间重新将自己进行优化，也希望老师给予指导。5用户使用说明（1）链接存储结构：按照提示一步步来即可；举例：请输入第一个多项式：请输入多项式的项数：3请输入第一项的系数：2请输入第一项的指数：2请输入第二项的系数：3请输入第二项的指数：5请输入第三项的系数：3请输入第三项的指数：1类似如上操作，到时大部分会在屏幕显示。（2）顺序存储结构按照提示一步步来即可；举例：请您输入第一个结构体数组的项数（不超过50项）：2请您输入第二个结构体数组的项数（不超过50项）：2现在是输入第一个多项式请输入第1项系数：2请输入第1项指数：2请输入

20、第2项系数：3请输入第2项指数：3现在是输入第二个多项式：请输入第1项系数：3请输入第1项指数：3请输入第2项系数：4请输入第2项指数：4接着屏幕便会显示出来。6测试结果（1）链接存储结构：（2）顺序存储结构7附录（1）链接存储结构：#include using namespace std;struct nodeint coef; /系数 int exp; /指数 struct node * next;/指针域chainLink;/创建chainLink的node结点对象struct node *create() /定义建立多项式函数，并返回链表头指针struct node *h = NULL

21、, *q, *p;/定义结构体头指针h，标记指针p和q，p是创造新节点的标记指针，q是链接链表的指针；int i = 1, N; /定义多项式的项数N及标记数icout N;p = 0;/指针初始化；q = 0;/本地指针初始化；for (; i = N; i+)p = (struct node *)malloc(sizeof(chainLink); /为一个新节点分配空间cout 请输入第 i (*p).coef;cout 请输入第 i (*p).exp;if (i = 1) h = p; q = p; /建立头节点elseq-next = p;q = p;q-next = NULL;/p,

22、q都成为新链表的尾指针；p-next = NULL;return h;void display(struct node *h)struct node *p; /定义标记指针，输出链表p = h;while (p != NULL)if (p-coef = 0)struct node *d;d = h;while (d-next != p)d = d-next;d-next = p-next;p = p-next;/删去系数为0的节点；elseif (p-coefexp = 0) cout (*p).coef +;else cout ( (*p).coef ) *X (*p).exp exp =

23、0) cout (*p).coef exp!=0&p-exp!=1)cout (*p).coef *X (*p).exp +;else cout (*p).coef next;cout next; /将原来的链表建立成待排序链表h1-next = NULL; /截断第一个原链表中的节点while (h2 != NULL)q = h1;p = q-next;t = h2; /从待排序链表中选出一个节点准备插入到新链表中h2 = h2-next; /移动待排序链表的头指针，便于进行下一次挑选t-next = NULL;if (t-expq-exp) /应插入头指针之前的情况t-next = q;h

24、1 = t;continue;if (p = NULL&t-exp exp) q-next = t; /应插入表尾的情况while (p != NULL)if (t-expp-exp)q-next = t;t-next = p;break;elseq = q-next;p = p-next;if (p = NULL) q-next = t;return h1; /新链表即为按降幂顺序排好的链表，返回其头指针struct node *add(struct node *h1, struct node *h2) /定义加法函数，并返回结果的链表的头指针struct node *p, *q, *hea

25、d, *r; /定义结构体头指针head和标记指针p,q,rp = h1;q = h2;head = (struct node *)malloc(sizeof(chainLink); /为结果多项式分配头指针if (p-exp = q-exp) head = h1; p = p-next; elseif (p-expexp) head = h2; q = q-next; else p-coef = p-coef + q-coef; head = p; p = p-next; q = q-next; r = head;while (p != NULL&q != NULL)if (p-expq-e

26、xp) r-next = p; p = p-next; elseif (p-expexp) r-next = q; q = q-next; else p-coef = p-coef + q-coef; r-next = p; p = p-next; q = q-next; r = r-next;if (p = NULL&q = NULL) r-next = NULL;elseif (p = NULL) r-next = q;if (q = NULL) r-next = p;return head;int main()struct node *h1, *h2, *h3;/定义3个头指针；cout

27、 n请输入第一个多项式：n;h1 = create();/创造第一个线性链表；cout n您输入的第一个多项式为：n;display(h1);/把多项式显示出来；h1 = order(h1);cout n降幂排列后的第一个多项式为：n;display(h1);cout n;cout n请输入第二个多项式：n;h2 = create();/创造第二个线性链表；cout n您输入的第二个多项式为：n;display(h2);/把多项式显示出来；h2 = order(h2);cout n降幂排列后的第二个多项式为：n;display(h2);cout n;h3 = add(h1, h2);/利用加函

28、数将多项式相加；cout n第一个多项式和第二个多项式相加后：n;display(h3);system(pause);return 0;（2）顺序存储结构#include using namespace std;struct polyfloat coef;int exp;/结构体数组定义void defStruct(struct poly *s,int n)int i = 0;for (; i n; i+)cout 请输入第 i + 1 (*s)i.coef;cout 请输入第 i + 1 (*s)i.exp;/初始化顺序结构体数组void print(struct poly *s, int

29、n)for (int i = 0; i n; i+)if (i = n - 1)cout (*s)i.coef *X (*s)i.exp;elsecout (*s)i.coef *X (*s)i.exp+;/输出数组void sort(struct poly *s, int n)int i, temp1, j; /定义数组中的循环标记数据i与j，和整型标记temp1float temp2; /定义单精度型标记temp2for (i = 0; in - 1; i+)for (j = i + 1; j(*s)i.exp)temp1 = (*s)j.exp;(*s)j.exp = (*s)i.exp;(*s)i.exp = temp1;temp2 = (*s)j.coef;(*s)j.coef = (*s)i.coef;(*s)i.coef = temp2;for (i = 0; in - 1; i+)if (*s)i.exp = (*s)i + 1.exp)(*s)i + 1.coef = (*s)i.coef + (*s)i + 1.coef;if (i = n - 2)(*s)i.coef = (*s)i + 1.coef;(*s)i + 1.coef =