实验二-链表-实验报告.docx

《实验二-链表-实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一元多项式表达和相加实验报告一、实验内容和目的实验目的：掌握单链表的建立、合并和遍历操作实验内容：1.单链表的建立（创建一个一元多项式）2.单链表的遍历（一元多项式的输出、一元多项式的项数统计）3.单链表的合并（一元多项式的加减运算）二、实验原理基本原理：使用单链表储存一元多项式的指数和系数信息。每个结点含有两个数据域，分别用于存放每一项的指数和系数；一个指针域用于存放下一个结点的指针。一个完整的链表表示一个一元多项式。单链表的建立：为了后续操作的方便，本实验中创建的单链表是按指数倒序排序的。例：创建一元多项式：18x12+17x

2、9+9x6+5x3+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指向结点指

4、数大于Pb指向结点的指数，把Pa指向的结点插入到新的链表之中。具体步骤如图如果Pa指向结点指数小于Pb指向结点的指数，则把Pb指向的结点插入到新的链表之中。具体步骤如图如果Pa指向的结点指数等于Pb指向的结点指数，则先把两者指向结点指数相加，储存到Pa指向结点中。移动Pa，Pb指针，释放原来Pb指向的结点。具体步骤如图一直重复上述操作，当其中一个链表结点已经全部插入到新的链表中时，则把另外一个链表剩下的所有结点插入到链表之中（即只需要把剩下的结点接起来）。具体步骤如图当完成上述的操作，把Pa指针指向新链表的指向新的链表头。把旧的两

5、个链表头释放掉。一元多项式的减法，实际上也是一元多项式的加法。程序对于一元多项式的减法处理如下，A和B是两个多项式，A-B=A+(-B)，也就是说，把作为减数的多项式中每一项的系数变成其相反数，然后将两个多项式进行加法运算。一、程序流程图一、实验结果4.1程序主菜单4.2创建多项式4.3一元多项式的加法操作4.4一元多项式的减法操作4.5求一元多项式系数操作一、操作说明1.主菜单中的1（创建一元多项式）2（输出一元多项式）5（求一元多项式操作）三个选项操作的对象是同一个一元多项式，因此，要使用输出和求项数功能之前，需要选择1（创建

6、一元多项式）创建多项式。2.多项式的加减操作的操作对象是两个新的多项式，操作结束以后，进行加减运算的多项式和结果多项式均不会保存。3.在多项式的加减运算过程中，只要其中一个多项式的创建出现问题，整个加减法运算操作就会终止。二、附录：代码#include#include#defineOK0#defineERROR1typedefstructLNode{intexp;//指数floatcoef;//系数structLNode*next;//指针域}LNode;/*基本操作的实现*///向链表中插入

7、一个新的结点（插入过程中保持指数降序排序）//hNode头结点//nNode要插入的新结点intInsertLNode(LNode*hNode,LNode*nNode){LNode*p,*q;//如果链表为空表，则把元素放在链表第一个位置if(hNode->next==NULL){hNode->next=nNode;}else{p=hNode;q=hNode->next;while(q!=NULL){//如果新的结点指数比q结点的指数大，则该结点插在q结点的前面if(nNode->exp>q->exp){nNode->next=q

8、;p->next=nNode;break;}//如果新的结点指数与q的指数相等，指数相加，不插入结点if(nNode->exp==q->exp){q->coef=nNode->coef+q->coef;free(nNode);break;}//如果