《数据结构实验一一元多项式相加》由会员分享，可在线阅读，更多相关《数据结构实验一一元多项式相加（9页珍藏版）》请在金锄头文库上搜索。
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. 实验程序代码及运行结果：#includestdafx.h#include#include#include#include#defineNULL 0typedefstruct NODEfloatcoef;/ 系 | 数 oyintexpn;/ 指? 数oystructNODE *
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);/* 创?建? 链?表 a*/NODE *Creat( int n)NODE *current, *previous, *head;int i;head = (NODE *)malloc(sizeof (NOD
5、E); /* 创?建?头 a?结点?*/previous = head;for (i = 0; i coef, ¤t-expn); previous-next = current;previous = current;previous-next = NULL;return head;/* 一?元a多 项?式o?的?想?加?，?总1体?考?虑?，?可|分?qa的?指?数oy比 qb小?， ?或等于? 2pb( 如?果?系|数oy相加?等于?20和a不?等 于?20), 或 大?于?2pb里?面?由?|InsertBefore 和aDelfirst 两?个?小?模?块|组|成|一?部?
6、分 ?*/NODE *AddPolyn(NODE *head1, NODE *head2)NODE *ha, *hb, *qa, *qb;int a, b;float sum;ha = head1;/*ha 和ahb指?向 头 a?结点?*/hb = head2;qa = ha-next;/*qa 和aqb指?向 头a? 结点 ?的?下?一?个?结点?*/qb = hb-next;while (qa & qb)a = qa-expn;b = qb-expn;switch (compare(a, b) /*qa 和aqb均非?空?*/case -1 :/*qa-expn expn*/ha = q
7、a;qa = qa-next; break ;case 0 :sum = qa-coef + qb-coef;if (sum != 0.0) qa-coef = sum; ha = qa; elsefree(Delfirst(ha, qa);/* 系| 数 oy的?和a*/* 如?果?不?是 o?0.0*/* 改?变?系| 数oy*/ free(Delfirst(hb, qb); qa = ha-next; qb = hb-next;break ;/*qb 释oa放?后?要a重?新?赋3值| */case 1 : Delfirst(hb, qb); InsertBefore(ha, qb);
8、qb = hb-next; ha = ha-next;break ;if (qb) ha-next = qb;/* 如?果 ?qa- expn qb - expn*/* 把?qb插?入?到?ha下?一?个?结点?之?前 ?*/* 插?入?剩o?余? 的?pb*/free(head2);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
9、);/* 插?入?结点?,引y入?结点?p,可|以?让?p插?入 ?到?p2和ap1之?间?*/ void InsertBefore(NODE *p1, NODE *p2)NODE *p;p = p1-next;p1-next = p2;p2-next = p;/* 打? 印?,为a了?美观?程?序 分?开a打?印?*/ void print(NODE *head)NODE *current;current = head-next;while (current-next != NULL)printf( %0.f * x%d + , current-coef, current-expn); cu
10、rrent = current - next;printf( %0.f * x%d , current-coef, current-expn);/system ( ?pause);int main()NODE *head1, *head2, *head3;int n1, n2;printf( 请?输o?入?你?需要a的?多项?式o?的?项?数oy n1 : ); scanf( %d, &n1);head1 = Creat(n1);printf( 第2一?个?多项?式o?的?显?示o? : n ); print(head1);printf( n 请?输o?入?你?需要a的?多项?式o?的?项?数
11、oy n2 : ); scanf( %d, &n2);head2 = Creat(n2);printf( n 第2二t 个?多项?式o?的?显?示o? : n ); print(head2);head3 = AddPolyn(head1, head2);printf( n 合?并?后?的?多项?式o?的?显?示o? : n ); print(head3);printf( n );运行结果：实验数据 1 如图：输入一个四次二项式 X3+2X4 ，一个五次二项式 X4+2X5 ， 输出如图：实验数据 2 如图：输入一个五次四项式 X2+X3+X4+X5 ，还有一个五次五项 式 1+X+X3+2X4
12、+2X5 输出如图所示实 验 数 据 3 如 图 ： 输 入 一 个 七 次 三 项 式 1+2x5+3X7 ， 还 有 一 个 五 次 四 项 式 1+2X2+3X4+4X5, 输出如图：6.实验总结本来我对编程很没有信心， 做这样一个课程设计感觉有点吃力， 虽然有些人 觉得很简单，但是我还是坚持做下来了，我不断的看书，翻阅资料，询问同学， 上网搜索，总算有模有样地把这个程序编的能运行了。其次，这次编程是我更多地理解掌握了线性链表的逻辑机构和物理特性。 对 学过的知识有了很好的巩固。 困难还是很多的， 比如初次运行的时候， 好几十个 错误，当时真的感到非常崩溃。幸亏我没有放弃，才最终完成。长舒一口气。最后，通过这次编程， 不仅仅考察了我对知识的掌握， 更重要的是锻炼了我 的思维能力和耐心，在最困难的时候没有放弃，今天才能如此舒心。
