一元多项式相加数据结构实验一-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*x1学习文档仅供参考2概要设计1链接存储结构：struct nodef

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

6、式相加。3详细设计1链接存储结构：结构体定义：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

7、及标记数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,q 都成为新链表的尾指针；p-next = null;return h;ps ：值得注意的是， 我在里面p，q 指针均使其值为

8、0，是让其为空指针，对其进行初始化，在 visual studio 2013 版中，如果不进行初始化，会被报错。打印函数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 c

9、out ( (*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)q = h1;p = q-next;t = h2; / 从待排序链表中选出一个节点准备插入到新链表中h2 = h2-next; / 移动待排序链表的头指针，便于进行下一次挑选t-next = n

10、ull;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;elseq = q-next;p = p-next;if (p = null) q-next = t;return h1; / 新链表即为按降幂顺序排好的链表，返回其头指针order 函数其实是利用了3 个头指针，具体操作看代码即可，其实很容易

11、懂。相加函数add：struct node *add(struct node *h1, struct node *h2) / 定义加法函数，并返回结果的链表的头指针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

12、 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 = q-next; r = r-next;if (p = null&q = null) r-next = nul

13、l;学习文档仅供参考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;poly p2100, *po2=p2;/定义三个结构体数组，用于存放多项式,定义三个指针变量；print 函数以及参数调用代码：

14、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)int i, temp1, j; / 定义数组中的循环标记数据i 与 j，和整型标记temp1float temp2; / 定义单精度型标记temp2for

15、 (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 = (

16、*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 (; jn2; j+)(*s2)p.coef = (*s1)j.coef;(*s2)p.exp = (*s1)j.exp;p+;elsefor (; in1; i+)(*s2

17、)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 +;学习文档仅供参考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 函

18、数在主函数中的调用：add(&po, &po1, &po2, n1, n2);4调试分析1链接存储结构：设计过程， 注意指针保护，如果一步不小心，容易造成头指针消失，所以需要指针来保护头指针，至于其他方面倒是没有什么问题。总的来说，代码长度170，算不上特别多，该有的功能也考虑到了。2顺序存储结构在设计过程中， 发现如果不采用指针参数传递结构体数组，而是对单个多项式进行单个功能操作， 即对于每一个多项式都会用同功能的函数，只不过不同名称来实现，这样造成代码冗长，我试过写出了286 行的代码，但visual studio2013 无法编译如此冗长的代码，所以我决定使用指针

19、导向进行优化，优化后的代码行数是162 行，少了 100 多行， 实现功能也比之前多了一些。虽然没法像我第一次写那286 行的代码可以实现动态创建结构体数组，但我认为，这 162 行的代码的结构体数组50 个大小，理应足够计算，如果要更大，建议修改代码中创建结构体数组大小的尺寸。总体来说，还算不错，知识经过一个寒假忘得七零八落，感觉我还没有完全掌握这类知识，等有时间重新将自己进行优化，也希望老师给予指导。5用户使用说明1链接存储结构：按照提示一步步来即可；举例：请输入第一个多项式：请输入多项式的项数：3请输入第一项的系数：2学习文档仅供参考请输入第一项的指数：2请输入第二项的系数：3请输入第二

20、项的指数：5请输入第三项的系数：3请输入第三项的指数：1类似如上操作，到时大部分会在屏幕显示。2顺序存储结构按照提示一步步来即可；举例：请您输入第一个结构体数组的项数不超过50 项 ：2请您输入第二个结构体数组的项数不超过50 项 ：2现在是输入第一个多项式请输入第 1 项系数：2请输入第 1 项指数：2请输入第 2 项系数：3请输入第 2 项指数：3现在是输入第二个多项式：请输入第 1 项系数：3请输入第 1 项指数：3请输入第 2 项系数：4请输入第 2 项指数：4接着屏幕便会显示出来。6测试结果1链接存储结构：学习文档仅供参考学习文档仅供参考2顺序存储结构7附录1链接存储结构：学习文档仅

21、供参考#include using namespace std;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;/ 指针初始化；

22、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,q 都成为新链表的尾指针；p-next = null;return h;void display(struct node *h)struct node *p; / 定义标记指针，输出链表p =

23、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 exp!=0&p-exp!=1)cout (*p).coef *x (*p).exp +;else cout (*p).coe

24、f 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 (p = null&t-exp exp) q-next = t; / 应插入表尾的情况whi

25、le (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, *head, *r; / 定义结构体头指针head 和标记指针p,q,rp = h1;q = h2;head = (struct

26、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-exp) r-next = p; p = p-next; else学习文档仅供参考if (p-expexp)

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

28、；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);/ 利用加函数将多项式相加；cout n 第一个多项式和第二个多项式相

29、加后：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 n)for (int i = 0; i

30、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 = 0;elsefor (j = i; j(*s1)j.exp)