实验二-链表-实验报告(共17页).docx
《实验二-链表-实验报告(共17页).docx》由会员分享,可在线阅读,更多相关《实验二-链表-实验报告(共17页).docx(17页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上一元多项式表达和相加 实验报告 一、 实验内容和目的实验目的:掌握单链表的建立、合并和遍历操作实验内容:1. 单链表的建立(创建一个一元多项式) 2. 单链表的遍历(一元多项式的输出、一元多项式的项数统计) 3. 单链表的合并(一元多项式的加减运算)二、 实验原理基本原理:使用单链表储存一元多项式的指数和系数信息。每个结点含有两个数据域,分别用于存放每一项的指数和系数;一个指针域用于存放下一个结点的指针。一个完整的链表表示一个一元多项式。单链表的建立: 为了后续操作的方便,本实验中创建的单链表是按指数倒序排序的。 例:创建一元多项式:18x12+17x9+9x6+5x
2、3+6x2+19x 为了更好说明建立的过程,输入的过程并非按照指数降序的顺序输入。实际的输入如下:步骤一:把最先输入的数据作为链表的第一个结点步骤二:用第二个数据创建一个新的结点,如果新结点指数大于某个结点,则新的结点插在该结点的前面;否则跟后面一个再比较(源码中p和q指针向链表后移动);如果新的结点比前面的每一个结点都要小(即q指向链表最后一个结点),则插在链表的末尾端。下图为新结点中指数比前面每个结点的指数都要小如果发现新结点的指数大于链表中某个特定结点时(图中红色数字表示操作顺序) 不断重复上述步骤,直到所有的数据都储存到单链表中。单链表的合并(即本例中的一元多项式的加减法):根据上述的
3、链表创建算法,创建好的链表都具有按指数大小降序的特点。为了确保合并以后的单链表也具有此特点,因此合并的过程中,同样会边合并,边比较大小,从而确保合并的结果仍然具有此特性。例:多项式P1为:18x17+9x8+4x2+3x多项式P2为:12x12+7x8+4x3多项式运算P1+P2的结果为:18x17+12x12+16x8+4x3+4x2+3x从上述的链表创建算法可以创建出两个对应的链表先利用两个指针,Pa和Pb,分别指向两个多项式的结点。如果Pa指向结点指数大于Pb指向结点的指数,把Pa指向的结点插入到新的链表之中。具体步骤如图如果Pa指向结点指数小于Pb指向结点的指数,则把Pb指向的结点插入
4、到新的链表之中。具体步骤如图如果Pa指向的结点指数等于Pb指向的结点指数,则先把两者指向结点指数相加,储存到Pa指向结点中。移动Pa,Pb指针,释放原来Pb指向的结点。具体步骤如图一直重复上述操作,当其中一个链表结点已经全部插入到新的链表中时,则把另外一个链表剩下的所有结点插入到链表之中(即只需要把剩下的结点接起来)。具体步骤如图当完成上述的操作,把Pa指针指向新链表的指向新的链表头。把旧的两个链表头释放掉。 一元多项式的减法,实际上也是一元多项式的加法。程序对于一元多项式的减法处理如下,A和B是两个多项式,A-B = A+(-B),也就是说,把作为减数的多项式中每一项的系数变成其相反数,然后
5、将两个多项式进行加法运算。三、 程序流程图四、 实验结果4.1 程序主菜单4.2 创建多项式4.3 一元多项式的加法操作4.4 一元多项式的减法操作4.5 求一元多项式系数操作五、 操作说明1. 主菜单中的1(创建一元多项式)2(输出一元多项式) 5(求一元多项式操作)三个选项操作的对象是同一个一元多项式,因此,要使用输出和求项数功能之前,需要选择1(创建一元多项式)创建多项式。2. 多项式的加减操作的操作对象是两个新的多项式,操作结束以后,进行加减运算的多项式和结果多项式均不会保存。3. 在多项式的加减运算过程中,只要其中一个多项式的创建出现问题,整个加减法运算操作就会终止。六、 附录:代码
6、#include #include #define OK 0#define ERROR 1typedef struct LNodeint exp;/ 指数float coef;/ 系数struct LNode *next;/ 指针域 LNode;/* 基本操作的实现*/ 向链表中插入一个新的结点(插入过程中保持指数降序排序)/ hNode头结点/ nNode要插入的新结点int InsertLNode(LNode *hNode, LNode *nNode)LNode *p, *q;/ 如果链表为空表,则把元素放在链表第一个位置if (hNode-next = NULL)hNode-next =
7、 nNode;elsep = hNode;q = hNode-next;while (q != NULL)/ 如果新的结点指数比q 结点的指数大,则该结点插在q 结点的前面if (nNode-exp q-exp)nNode-next = q;p-next = nNode;break;/ 如果新的结点指数与q 的指数相等,指数相加,不插入结点if (nNode-exp = q-exp)q-coef = nNode-coef + q-coef;free(nNode);break;/ 如果新的结点指数比q 的指数小/ 如果q 是最后一个结点,直接插入在q 的后面/ 如果q 不是最后一个结点,则q 指
8、针往后移动if (q-next = NULL)nNode-next = q-next;q-next = nNode;break;else p = p-next;q = q-next;return OK;/ 两个多项式的相加操作/ 因为相加过程中,会根据指数的大小,一边运算一般排序/ 因此,要求传入的Pa 和Pb 都是按指数降序排序的一元多项式void AddPolyn(LNode *Pa, LNode *Pb)LNode *head, *q, *tmp;/ 用于储存新创建的多项式LNode *recycle;/ 用于指数相等系数相加后结点的释放LNode *PtrB;/ 用于合并完成后链表头结
9、点的释放head = (LNode *)malloc(sizeof(LNode *);head-next = NULL;q = head;PtrB = Pb;Pa = Pa-next;Pb = Pb-next;/ 如果Pa 和Pb 指针不同时为空while (Pa & Pb)/ 如果Pa 所指向结点的指数大于Pb 所指向结点的指数if (Pa-exp Pb-exp)/ 把Pa 指向的结点插入到新的链表之中tmp = Pa;Pa = Pa-next;tmp-next = NULL;q-next = tmp;q = q-next;continue;/ 如果Pa 所指向结点的指数等于Pb 所指向结点
10、的指数if (Pa-exp = Pb-exp)/ 先把Pa 指向结点和Pb 指向结点的系数相加,并储存到Pa 指向的结点/ 再把Pa 指向的结点插入到新的链表之中tmp = Pa;tmp-coef = tmp-coef + Pb-coef;recycle = Pb;Pa = Pa-next;Pb = Pb-next;free(recycle);tmp-next = NULL;q-next = tmp;q = q-next;continue;/ 如果Pa 所指向结点的指数小于Pb 所指向结点的指数if (Pa-exp exp)/ 把Pb 指向的结点插入到新的链表tmp = Pb;Pb = Pb-
11、next;tmp-next = NULL;q-next = tmp;q = q-next;continue;/ 如果其中一个链表已经遍历完毕,把链表剩下的所有结点插入到新的链表之中if (Pa)q-next = Pa;if (Pb)q-next = Pb;PtrB-next = NULL;/ 释放旧的链表头结点free(PtrB);/ 把新的链表头结点赋到Pa Pa = head;/ 对两个一元多项式进行相减操作/ A - B = A + (-B)void SubtractPolyn(LNode *Pa, LNode *Pb)LNode *p;/ 把Lb 中每项的系数变成其相反数for (p
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 链表 报告 17
限制150内