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