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

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

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

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

4、数会以保存小数点后两位数字的形式输出；假设指数输入时为小数，那么输出时会自动截取其整数局部。程序所能到达的功能：程序可以对输入的序列紊乱的多项式进展加工，使之按照降幂排列，之后对两多项式进展加法运算包括系数为负的加法，最后输出最终的多项式。测试数正确数据：专业资料整理WORD格式输入： 2*X3+2*X6+2*X7+2*X8+2*X10和-专业资料整理WORD格式3*X10+4*X8+2*X7+3*X5+3*X3输出： 7.00*X2+8.00*X1+2.00错误数据：专业资料整理WORD格式输入： -8*X1.5+4*X2和3*X2+12*X1.6输出： 7.00*X2+4.00*X1专业资

5、料整理WORD格式2概要设计1存储构造：struct nodefloat coef;int expo;struct node *next;chainLink;函数主体局部，利用头指针进展链表操作，利用display 进展打印出屏幕，利用order 函数对其进展降幂排序，当两个多项式已经创立完毕时，利用add 函数进展两个多项式相加。2顺序存储构造抽象数据类型为构造体数组：struct polyfloat coef;int exp;专业资料整理WORD格式函数主体局部，会引用指针进展参数传递，在函数主体局部定义了3义其所对应的指针，利用用户输入，利用print 函数将其打印出来，再用排列，做完两

6、个构造体数组后，接着利用add 函数将两个多项式相加。个构造体数组同时定sort 函数将其降序专业资料整理WORD格式3详细设计（ 1存储构造：构造体定义：struct node专业资料整理WORD格式int coef;/ 系数专业资料整理WORD格式int exp;/ 指数专业资料整理WORD格式struct node * next;/指针域chainLink;/ 创立 chainLink 的 node 结点对象值得注意的是，与顺序存储构造不同的是，内部还定义了指针域功能函数介绍：专业资料整理WORD格式struct node *create()/ 定义建立多项式函数，并返回链表头指针专业资

7、料整理WORD格式专业资料整理WORD格式struct node *h = NULL, *q, *p;/定义构造体头指针h，标记指针p 和q， p 是创造新节点专业资料整理WORD格式的标记指针， q 是链表的指针；int i = 1, N;cout N;p = 0;/ 指针初始化；q = 0;/ 本地指针初始化；n;/ 定义多项式的项数N 及标记数i专业资料整理WORD格式for (; i = N; i+)专业资料整理WORD格式p = (struct node *)malloc(sizeof(chainLink);cout 请输入第 i (*p).coef;cout 请输入第 i (*p)

8、.exp;if (i = 1) h = p; q = p; else/ 为一个新节点分配空间/ 建立头节点专业资料整理WORD格式q-next = p;q = p;专业资料整理WORD格式q-next = NULL;/p,qp-next = NULL;return h;都成为新链表的尾指针；专业资料整理WORD格式PS：值得注意的是， 我在里面P，q 指针均使其值为0，是让其为空指针，对其进展初始化，在 visual studio 2021版中，如果不进展初始化，会被报错。打印函数 display:void display(struct node*h)专业资料整理WORD格式struct no

9、de *p;p = h;while (p != NULL)/ 定义标记指针，输出链表专业资料整理WORD格式if (p-coef = 0)struct node *d;d = h;while (d-next != p)d = d-next;d-next = p-next;p = p-next;/ 删去系数为0 的节点；else专业资料整理WORD格式if (p-coefexp = 0) cout (*p).coef +;else cout ( (*p).coef ) *X (*p).exp exp = 0) cout (*p).coef exp!=0&p-exp!=1)cout (*p).co

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

11、格式专业资料整理WORD格式t-next = q;h1 = t;continue;if (p = NULL&t-exp exp) q-next = t; / 应插入表尾的情况 while (p != NULL)专业资料整理WORD格式if (t-expp-exp)q-next = t;t-next = p;break;elseq = q-next;p = p-next;if (p = NULL) q-next = t;专业资料整理WORD格式return h1;/ 新链表即为按降幂顺序排好的链表，返回其头指针专业资料整理WORD格式专业资料整理WORD格式Order 函数其实是利用了相加函数a

12、dd：3 个头指针，具体操作看代码即可，其实很容易懂。专业资料整理WORD格式struct node *add(struct node *h1, struct node *h2)/ 定义加法函数，并返回结果的链表的头指针专业资料整理WORD格式struct node *p, *q, *head, *r;/ 定义构造体头指针head和标记指针p,q,r专业资料整理WORD格式p = h1;q = h2;专业资料整理WORD格式head = (struct node *)malloc(sizeof(chainLink); / 为结果多项式分配头指针 if (p-exp = q-exp) head

13、= 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-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 =

14、 q-next; r = r-next;if (p = NULL&q = NULL) r-next = NULL;专业资料整理WORD格式elseif (p = NULL) r-next = q;if (q = NULL) r-next = p;return head;add 函数大局部其实和教师PPT 思路差不多。 比较两个多项式中指数大小，然后分别对其余两个进展操作。（ 2 顺序存储构造构造体定义：struct polyfloat coef;int exp;/ 构造体数组定义主函数构造体数组的创立以及导引指针的创立：poly p50, *po=p;poly p150, *po1=p1;po

15、ly 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;elsecout (*s)i.coef *X (*s)i.exp+;/ 输出数组主函数中调用print 函数的具体形式：print(&po, n1);sort 函数的代码：void sort(struct poly *s, int n)专业资料整理WORD格式int i,

16、temp1, j;float temp2;/ 定义数组中的循环标记数据/ 定义单精度型标记temp2i 与j，和整型标记temp1专业资料整理WORD格式for (i = 0; in - 1; i+)for (j = i + 1; j(*s)i.exp)temp1 = (*s)j.exp;专业资料整理WORD格式(*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

17、)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(*s2)p.coef = (*s1)j.coef;(*s2)p.exp = (*s1)j.exp;j+;if (i = n1 | j = n2)p+;break;if (i = n1)for (;

18、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 +;专业资料整理WORD格式else cout (*s2)m.coef *X (*s2)m.exp 0)if (*s2)m.exp = 0)cout (*s2)m.coef +;else /prin

19、tf( %.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，算不上特别多，该有的功能也考虑到了。2顺序存储构造在设计过程中， 发现如果不采用指针参数传递构造体数组，而是对单个多项式进展单个功能操作， 即对于每一个多项式都会用同功能的函数，只

20、不过不同名称来实现，这样造成代码冗长，我试过写出了 286 行的代码，但 visual studio2021无法编译如此冗长的代码，所以我决定使用指针导向进展优化， 优化后的代码行数是 162 行，少了 100 多行， 实现功能也比之前多了一些。虽然没法像我第一次写那 286 行的代码可以实现动态创立构造体数组， 但我认为，这 162 行的代码的构造体数组 50 个大小，理应足够计算，如果要更大，建议修改代码中创立构造体数组大小的尺寸。总体来说，还算不错，知识经过一个寒假忘得七零八落，感觉我还没有完全掌握这类知识，等有时间重新将自己进展优化，也希望教师给予指导。5用户使用说明（ 1存储构造：按

21、照提示一步步来即可；举例：请输入第一个多项式：请输入多项式的项数：3请输入第一项的系数：专业资料整理WORD格式2专业资料整理WORD格式请输入第一项的指数：2请输入第二项的系数：3请输入第二项的指数：5请输入第三项的系数：3请输入第三项的指数：1类似如上操作，到时大局部会在屏幕显示。2顺序存储构造按照提示一步步来即可；举例：请您输入第一个构造体数组的项数不超过50 项：2请您输入第二个构造体数组的项数不超过50 项：2现在是输入第一个多项式请输入第 1项系数：2请输入第 1项指数：2请输入第 2项系数：3请输入第 2项指数：3现在是输入第二个多项式：请输入第 1 项系数：3请输入第 1 项指

22、数：3请输入第 2 项系数：4请输入第 2 项指数：4接着屏幕便会显示出来。6测试结果专业资料整理WORD格式1存储构造：专业资料整理WORD格式专业资料整理WORD格式2顺序存储构造7附录专业资料整理WORD格式1存储构造：专业资料整理WORD格式#includeusing namespace std;struct node专业资料整理WORD格式int coef;/ 系数int exp;/ 指数struct node * next;/指针域chainLink;/ 创立 chainLink 的 nodestruct node *create()结点对象/ 定义建立多项式函数，并返回链表头指针

23、专业资料整理WORD格式struct node *h = NULL, *q, *p;/定义构造体头指针h，标记指针p 和q， p 是创造新节点专业资料整理WORD格式的标记指针， q 是链表的指针；int i = 1, N;cout N;p = 0;/ 指针初始化；q = 0;/ 本地指针初始化；for (; i = N; i+)n;/ 定义多项式的项数N 及标记数i专业资料整理WORD格式p = (struct node *)malloc(sizeof(chainLink);cout 请输入第 i (*p).coef;cout 请输入第 i (*p).exp;if (i = 1) h = p

24、; q = p; else/ 为一个新节点分配空间/ 建立头节点专业资料整理WORD格式q-next = p;q = p;专业资料整理WORD格式q-next = NULL;/p,qp-next = NULL;return h;都成为新链表的尾指针；专业资料整理WORD格式void display(struct node*h)专业资料整理WORD格式struct node *p;p = h;while (p != NULL)/ 定义标记指针，输出链表专业资料整理WORD格式if (p-coef = 0)专业资料整理WORD格式struct node *d;d = h;while (d-next

25、 != p)d = d-next;d-next = p-next;p = p-next;/ 删去系数为0 的节点；else专业资料整理WORD格式if (p-coefexp = 0) cout (*p).coef +;else cout ( (*p).coef ) *X (*p).exp exp = 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)/ 将原来的链表建立成待排序链表/

26、截断第一个原链表中的节点专业资料整理WORD格式q = h1;p = q-next;t = h2;h2 = h2-next;/ 从待排序链表中选出一个节点准备插入到新链表中/ 移动待排序链表的头指针，便于进展下一次挑选专业资料整理WORD格式t-next = NULL;if (t-expq-exp)/ 应插入头指针之前的情况t-next = q;h1 = 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;els

27、eq = q-next;p = p-next;if (p = NULL) q-next = t;专业资料整理WORD格式return h1;/ 新链表即为按降幂顺序排好的链表，返回其头指针专业资料整理WORD格式struct node *add(struct node *h1, struct node *h2)/ 定义加法函数，并返回结果的链表的专业资料整理WORD格式头指针专业资料整理WORD格式struct node *p, *q, *head, *r;/ 定义构造体头指针head 和标记指针p = h1;q = h2;head = (struct node *)malloc(sizeof

28、(chainLink);/ 为结果多项式分配头指针if (p-exp = q-exp) head = h1; p = p-next; p,q,r专业资料整理WORD格式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-exp) r-next = p; p = p-next; else专业资料整理WORD格式if (p-expexp) r-ne

29、xt = 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 n请输入第一个多项式：n;h1 = create();/ 创造第一个线性链表；cout n您输

30、入的第一个多项式为：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);/ 利用加函数将多项式相加；cout n 第一个多项式和第二个多项式相加后：n;display(h

31、3);system(pause);return 0;2顺序存储构造专业资料整理WORD格式#include 专业资料整理WORD格式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 n)for (int i = 0;

32、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)专业资料整理WORD格式int i, temp1, j;float temp2;/ 定义数组中的循环标记数据/ 定义单精度型标记temp2i 与j，和整型标记temp1专业资料整理WORD格式for (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;专业资料整理WORD格式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