实验链表实验报告.docVIP

一元多项式表达和相加 实验报告 一、 实验内容和目的 实验目的：掌握单链表的建立、合并和遍历操作 实验内容：1. 单链表的建立（创建一个一元多项式） 2. 单链表的遍历（一元多项式的输出、一元多项式的项数统计） 3. 单链表的合并（一元多项式的加减运算） 二、 实验原理 基本原理：使用单链表储存一元多项式的指数和系数信息。每个结点含有两个数据域，分别用于存放每一项的指数和系数；一个指针域用于存放下一个结点的指针。一个完整的链表表示一个一元多项式。 单链表的建立： 为了后续操作的方便，本实验中创建的单链表是按指数倒序排序的。 例：创建一元多项式： 18x12+17x9+9x6+5x3+6x2+19x 为了更好说明建立的过程，输入的过程并非按照指数降序的顺序输入。 实际的输入如下： 步骤一：把最先输入的数据作为链表的第一个结点 步骤二：用第二个数据创建一个新的结点，如果新结点指数大于某个结点，则新的结点插在该结点的前面；否则跟后面一个再比较（源码中p和q指针向链表后移动）；如果新的结点比前面的每一个结点都要小（即q指向链表最后一个结点），则插在链表的末尾端。 下图为新结点中指数比前面每个结点的指数都要小 如果发现新结点的指数大于链表中某个特定结点时（图中红色数字表示操作顺序） 不断重复上述步骤，直到所有的数据都储存到单链表中。 单链表的合并（即本例中的一元多项式的加减法）： 根据上述的链表创建算法，创建好的链表都具有按指数大小降序的特点。为了确保合并以后的单链表也具有此特点，因此合并的过程中，同样会边合并，边比较大小，从而确保合并的结果仍然具有此特性。 例：多项式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指向的结点插入到新的链表之中。具体步骤如图 如果Pa指向的结点指数等于Pb指向的结点指数，则先把两者指向结点指数相加，储存到Pa指向结点中。移动Pa，Pb指针，释放原来Pb指向的结点。具体步骤如图 一直重复上述操作，当其中一个链表结点已经全部插入到新的链表中时，则把另外一个链表剩下的所有结点插入到链表之中（即只需要把剩下的结点接起来）。具体步骤如图 当完成上述的操作，把Pa指针指向新链表的指向新的链表头。把旧的两个链表头释放掉。 一元多项式的减法，实际上也是一元多项式的加法。程序对于一元多项式的减法处理如下，A和B是两个多项式，A-B = A+(-B)，也就是说，把作为减数的多项式中每一项的系数变成其相反数，然后将两个多项式进行加法运算。 三、 程序流程图 四、 实验结果 4.1 程序主菜单 4.2 创建多项式 4.3 一元多项式的加法操作 4.4 一元多项式的减法操作 4.5 求一元多项式系数操作 五、 操作说明 1. 主菜单中的1（创建一元多项式）2（输出一元多项式） 5（求一元多项式操作）三个选项操作的对象是同一个一元多项式，因此，要使用输出和求项数功能之前，需要选择1（创建一元多项式）创建多项式。 2. 多项式的加减操作的操作对象是两个新的多项式，操作结束以后，进行加减运算的多项式和结果多项式均不会保存。 3. 在多项式的加减运算过程中，只要其中一个多项式的创建出现问题，整个加减法运算操作就会终止。 六、 附录：代码 #include stdio.h #include stdlib.h #define OK 0 #define ERROR 1 typedef struct LNode { int exp; // 指数 float coef; // 系数 struct LNode *next; // 指针域 } LNode; /* 基本操作的实现*/ // 向链表中插入一个新的结点（插入过程中保持指数降序排序） // hNode 头结点 // nNode 要插入的新结点 int InsertLNode(LNode *hNode, LNode *nNode) { LNode *p, *q; // 如果链表为空表，则把元素放在链表第一个位置 if (hNode-next == NULL) { hNode-next = nNode; } else { p = hNode; q = hNode-next; while