《综合实验 多项式的相加》由会员分享，可在线阅读，更多相关《综合实验 多项式的相加（7页珍藏版）》请在金锄头文库上搜索。
1、两个多项式相加实验报告两个多项式相加实验报告班级 ：1101 计算机 姓名： 学号： 日期：主要实验内容：主要实验内容：根据所学的数据结构中线性结构（线性表）的逻辑特性和物理特性及相关算 法，应用于求解一个具体的实际问题-两个多项式相加一、一、运行环境运行环境 ：visual C+二、二、需求分析需求分析 (1)掌握线性结构的逻辑特性和物理特性 (2)掌握线性结构的各种相关算法 (3)掌握将算法转换成程序的方法和步骤 (4)掌握采用线性结构解决实际问题。三、三、概要设计概要设计1、抽象数据类型一元多项式的定义如下： ADT Polynomial 数据对象：D ai | ai TermSet,
2、i=1,2,.,m, m0TermSet 中的每个元素包含一个表示系数的实数和表示指数的整数 数据关系：R1 |ai-1 ,aiD, i=2,.,n， 且 ai-1中的指数值ai中的指数值 基本操作： CreatPolynCreatPolyn ( ( / 用带表头结点的有序链表表示多项式结点的数据元素类型定义为: typedeftypedef structstruct / 项的表示 floatfloat coef; / 系数 intint expn; / 指数 term, ElemType; 四、四、详细设计详细设计线性表的应用-多项式相加问题 多项式的相加操作是线性表处理的典型例子。在数学上
3、，一个多项式可写成下列形式： P（x）=anxn+an-1x n-1+ +a1x+a0 (其中 ai 为 xi 的非零系数) 在多项式相加时，至少有两个或两个以上的多项式同时并存，而且在实现运算的过程中所产生的中间 多项式和结果多项式的项数和次数都是难以预料的。因此计算机实现时，可采用单链表来表示。多项 式中的每一项为单链表中的一个结点，每个结点包含三个域：系数域、指数域和指针域，其形式如下：现在设有两个多项式： A(x)=12+3x2+5x3+8x4 B(x)=5+6x5 它们的链表结构见图 2-5-1。图 2-5-1 多项式的单链表结构多项式相加的运算规则为：两个多项式中所有指数相同的项，
4、对应系数相加，若和不为零，则构成 “和多项式”中的一项；所有指数不同的项均复制到“和多项式”中。实现时，可采用另建多项式的 方法，也可采用把一个多项式归并到另一个多项式中去的方法。这里介绍后一种方法。 下面是一个完整的 C 程序，包含三个算法：PolyAdd、Creat_Linkst 和 Print_Linkst。 核心算法 PolyAdd 是把分别由 pa 和 pb 所指的两个多项式相加，结果为 pa 所指的多项式。相 加时，首先设两个指针变量 qa 和 qb 分别从多项式的首项开始扫描(见图 2-5-1)，比较 qa 和 qb 所指结 点指数域的值，可能出现下列三种情况之一： （1）qa-
5、exp 大于 qb-exp,则 qa 继续向后扫描。 （2）qa-exp 等于 qb-exp,则将其系数相加。若相加结果不为零，将结果放入 qa-coef 中，并删除 qb 所指结点，否则同时删除 qa 和 qb 所指结点。然后 qa、qb 继续向后扫描。 （3）qa-exp 小于 qb-exp,则将 qb 所指结点插入 qa 所指结点之前，然后 qa、qb 继续向后扫描。 扫描过程一直进行到 qa 或 qb 有一个为空为止，然后将有剩余结点的链表接在结果链表上。所得 pa 指向的链表即为两个多项式之和。 算法 Creat_Linkst 是建立表示多项式的单链表。建立链表的过程是一个动态生成的
6、过程，即从 “空表”的初始状态起，依次输入数据元素，每输入一个就生成一个新结点并插入到表尾。为了方便 新结点的插入，算法中设置一个指针 pre 使其始终指向当前链表的表尾结点，初始指向 pa(见图 2-5-1)。流程图：五、五、测试数据及结果：测试数据及结果：六、六、源程序（带注释）源程序（带注释）#include #include struct list/* 节点结构声明 */ int power;/* 多项式中变量的幂 */ int coeff;/* 多项式中变量的系数 */ struct list *next; ; typedef struct list node; typedef no
7、de *poly; void printPoly(poly head) poly pointer;/* 临时指针变量 */ pointer = head; while (pointer != NULL)/* 打印各节点 */ printf(“%d,%d “,pointer-coeff,pointer-power); pointer = pointer-next; printf(“n“); poly createPoly(poly head)/* 从键盘输入一个多项式的项数和各项的幂和系数 */ poly newNode;/* 临时节点 */ poly pointer; int n,i; int
8、 coeffTemp,powerTemp;/* 临时变量 */ head = (poly) malloc(sizeof(node);/* 内存配置 */ if (head = NULL) printf(“Memory allocate Failure!n“);/* 内存配置失败 */ else printf(“请输入要创建的多项式的项数：n“); scanf(“%d“, if (n = 0) return NULL; printf(“请按 x 降幂依次输入各项的系数和幂：n“); scanf(“%d%d“,/* 输入多项式一项的系数和幂 */ head-coeff = coeffTemp;/*
9、 定义首节点 */ head-power = powerTemp; head-next = NULL; pointer = head; for (i = 1;i coeff = coeffTemp; newNode-power = powerTemp; newNode-next = NULL; pointer-next = newNode;/* 将新定义的节点连接到原链表的表尾 */ pointer = newNode;/* pointer 指针后移 */ printPoly(head); return head; void freeList(poly head) poly pointer;/
10、* 临时指针变量 */ while (head != NULL) pointer = head; head = head-next; free(pointer); poly addPoly(poly head1,poly head2) poly pointer1,pointer2,pointer,newNode,head;/* 临时指针变量 */ pointer1 = head1; pointer2 = head2; head = (poly) malloc(sizeof(node); pointer = head; while (pointer1 != NULL) | (pointer2 !
11、= NULL) / if (pointer1 !=NULL newNode-power = pointer1-power; newNode-coeff = pointer1-coeff; newNode-next = NULL; pointer-next = newNode; pointer = newNode; pointer1 = pointer1-next; if (pointer1 !=NULL newNode-power = pointer2-power; newNode-coeff = pointer2-coeff; newNode-next = NULL; pointer-nex
12、t = newNode; pointer = newNode; /* 指向存储结果的链表的指针后移 */ pointer2 = pointer2-next; if (pointer1 !=NULL newNode-power = pointer1-power; newNode-coeff = pointer1-coeff + pointer2-coeff; newNode-next = NULL; pointer-next = newNode; pointer = newNode;/* 指向存储结果的链表的指针后移 */pointer1 = pointer1-next; pointer2 =
13、pointer2-next; if (pointer1 = NULL newNode-power = pointer2-power; newNode-coeff = pointer2-coeff; newNode-next = NULL; pointer-next = newNode; pointer = newNode;/* 指向存储结果的链表的指针后移 */pointer2 = pointer2-next; if (pointer2 = NULL newNode-power = pointer1-power; newNode-coeff = pointer1-coeff; newNode-
14、next = NULL; pointer-next = newNode; pointer = newNode; pointer1 = pointer1-next; pointer = head; head = head-next; free(pointer); return (head); void main() poly p,q,r;/* 定义三个代表多项式的链表 */ printf(“这是多项式 p:n“);/* 创建多项式 p */ p= createPoly(p); printf(“这是多项式 q:n“);/* 创建多项式 q */ q= createPoly(q); r = (poly) malloc(sizeof(node); printf(“这是多项式 p 与多项式 q 的和 r:n“); r = addPoly(p,q);/* 将多项式 p 和多项式 q 的和赋值给 r */ printPoly(r); freeList(p);/* 释放程序中使用过的链表所占用的空间 */ freeList(q); freeList(r);
