实验二-链表-实验报告(共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 <stdio.h>#include <stdlib.h>#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

7、(hNode->next = NULL)hNode->next = 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->

8、;coef;free(nNode);break;/ 如果新的结点指数比q 的指数小/ 如果q 是最后一个结点，直接插入在q 的后面/ 如果q 不是最后一个结点，则q 指针往后移动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

9、*Pa, LNode *Pb)LNode *head, *q, *tmp;/ 用于储存新创建的多项式LNode *recycle;/ 用于指数相等系数相加后结点的释放LNode *PtrB;/ 用于合并完成后链表头结点的释放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 (P

10、a->exp > Pb->exp)/ 把Pa 指向的结点插入到新的链表之中tmp = Pa;Pa = Pa->next;tmp->next = NULL;q->next = tmp;q = q->next;continue;/ 如果Pa 所指向结点的指数等于Pb 所指向结点的指数if (Pa->exp = Pb->exp)/ 先把Pa 指向结点和Pb 指向结点的系数相加，并储存到Pa 指向的结点/ 再把Pa 指向的结点插入到新的链表之中tmp = Pa;tmp->coef = tmp->coef + Pb->coef;re

11、cycle = Pb;Pa = Pa->next;Pb = Pb->next;free(recycle);tmp->next = NULL;q->next = tmp;q = q->next;continue;/ 如果Pa 所指向结点的指数小于Pb 所指向结点的指数if (Pa->exp < Pb->exp)/ 把Pb 指向的结点插入到新的链表tmp = Pb;Pb = Pb->next;tmp->next = NULL;q->next = tmp;q = q->next;continue;/ 如果其中一个链表已经遍历完毕

12、，把链表剩下的所有结点插入到新的链表之中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 = Pb->next; p != NULL; p = p->next)p->coef = -(p-

13、>coef);AddPolyn(Pa, Pb);/* 具体功能的实现*/int CreatePolynomial(LNode *hNode)int i, n, exp;float coef;LNode *node;printf("请输入多项式的项数：");/ 如果输入的不是整数if ( scanf("%d", &n) = 0 )printf("无效输入.n");return ERROR;/ 清空上述操作中未读入的数值。防止对后面的操作产生影响fflush(stdin);printf("即将创建一个项数为%d 的

14、多项式n", n);printf("输入的格式为：先系数后指数，两者之间使用英文逗号间隔n");for ( i = 1; i <= n; i+ )printf("请输入第%d 项的系数和指数：", i);/ 防止不正确输入导致的死循环fflush(stdin);/ 操作前检查输入的有效性/ 如果输入的数据无效则要求重新输入if ( scanf("%f,%d", &coef, &exp) = 2)node = (LNode *)malloc(sizeof(LNode);if (!node)printf(&

15、quot;内存分配失败！n");system("pause");return ERROR;/ 向新结点赋值node->exp = exp;node->coef = coef;node->next = NULL;/ 把新结点插入到链表之中InsertLNode(hNode, node);elseprintf("输入无效，请重新输入。n");i-;if (i = n + 1)return OK;elsereturn ERROR;void PrintPolynomial(LNode *head)LNode *p = head->

16、;next;int i = 0;/ 用于控制加号输出while (p != NULL)/ 如果系数不为0，输出该项if (p->coef != 0)/ 根据参数的正负输出加减号if (i+ != 0 && p->coef > 0)putchar('+');printf("%.2fx%d", p->coef, p->exp);/ 防止系数为0 的前一项的指数被覆盖if (p->next && p->next->coef = 0)printf(" ");elsep

17、rintf("b");/ 覆盖前面的加号p = p->next;printf("n");/ 遍历并输出整数序列void ListTravel(LNode *head)int n = 0;LNode *p;/ 先对多项式的项数进行统计for ( p = head->next; p != NULL; p = p->next )n+;/ 输出项数printf("%d, ", n);/ 通过链表的遍历实现整数序列中的指数和系数部分for ( p = head->next; p != NULL; p = p->ne

18、xt )printf("%.2f, %d, ", p->coef, p->exp);void ListCount(LNode *head)LNode *p;int i = 0;/ 每发现一个非空结点，i 加一for (p = head->next; p != NULL; p = p->next) i+;printf("n 该一元多项式有%d 项nn", i);system("pause");/ 创建两个一元多项式并相加void CreateAndPlus()LNode *La, *Lb;/ 为两个新的链表分配内

19、存空间La = (LNode *)malloc(sizeof(LNode);Lb = (LNode *)malloc(sizeof(LNode);La->next = NULL;Lb->next = NULL;/ 清屏system("cls");printf("n现在创建第一个一元多项式nn");if (CreatePolynomial(La) = ERROR)printf("创建多项式时出现错误，即将返回主菜单.n");system("pause");return;PrintPolynomial(La

20、);printf("n现在创建第二个一元多项式nn");if (CreatePolynomial(Lb) = ERROR)printf("创建多项式时出现错误，即将返回主菜单.n");system("pause");return;PrintPolynomial(Lb);printf("n求和结果：n");AddPolyn(La, Lb);PrintPolynomial(La);system("pause");void CreateAndSubtract()LNode *La, *Lb;/ 为两个

21、新的链表分配内存空间La = (LNode *)malloc(sizeof(LNode);Lb = (LNode *)malloc(sizeof(LNode);La->next = NULL;Lb->next = NULL;/ 清屏system("cls");printf("n现在创建第一个一元多项式nn");if (CreatePolynomial(La) = ERROR)printf("创建多项式时出现错误，即将返回主菜单.n");system("pause");return;PrintPolyno

22、mial(La);printf("n现在创建第二个一元多项式nn");if (CreatePolynomial(Lb) = ERROR)printf("创建多项式时出现错误，即将返回主菜单.n");system("pause");return;PrintPolynomial(Lb);printf("n两个多项式相减以后的结果：n");SubtractPolyn(La, Lb);PrintPolynomial(La);system("pause");int main(void)LNode *hea

23、d = (LNode *)malloc(sizeof(LNode);char ch = '0'if (!head)printf("链表头指针内存分配失败！n");system("pause");return ERROR;head->next = NULL;while (1)/ 解决闪屏或者不能接受用户输入的问题fflush(stdin);system("cls");printf("nn");printf(" 单链表的应用演示程序n");printf(" 一元多项式

24、的表示及相加n");printf("n");printf(" 1. 创建一个一元多项式并输出n");printf(" 2. 遍历单链表并输出整数序列n");printf(" 3. 创建两个一元多项式并相加n");printf(" 4. 创建两个一元多项式并相减n");printf(" 5. 求一个一元多项式中的项数n");printf("n");printf(" Q. 退出程序n");printf("nn");printf(" 请选择：");scanf("%c", &ch);switch (ch)case '1':system("cls");/ 如果链表已经创建，则需要重新分配空间/ 并释放原有的空间if (h