《39n元多项式相乘》由会员分享，可在线阅读，更多相关《39n元多项式相乘（18页珍藏版）》请在金锄头文库上搜索。
1、1数据结构课程设计报告设计题目：n 元多项式乘法学 号： 姓 名： 指导教师： 专 业： 班 级： 学年学期： 起止时间： 哈尔滨师范大学计算机科学与信息工程学院2多项式运算的算法分析和设计一、 具体任务功能：完成两个 n 元多项式作乘法，给出明确的等式形式。 分步实施：1) 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数； 2) 完成最低要求：建立一个文件，实现两个一元二次多项式作乘法。 3) 进一步要求：实现三元二次多项式的乘法。二、 概要设计定义单链表的抽象数据类型：ADT LinkList数据对象：D=ai|aiElemSet,i=1,2,3,，n=0数据关系：R=|ai
2、,ai+1 D/-线性表的单链表基本操作-/ LinkList InitList(void); 构造一个空的线性表 void DestroyList(LinkList *L);初始条件：线性表 L 已存在。 操作结果：销毁线性表 L。 LinkList MakeEmpty(LinkList L)初始条件：线性表 L 已存在。 操作结果：将线性表 L 重置为空表。 int IsEmpty(LinkList L);初始条件：线性表 L 已存在。 操作结果：判断线性表是否为空表。 int ListLength(LinkList L);初始条件：线性表 L 已存在。 操作结果：返回线性表 L 结点的个
3、数。 LNode IsLast(LinkList L);初始条件：线性表 L 已存在。 操作结果：返回线性表 L 的最后一个结点（尾结点）。 LNode NewLNode(ElemType X);构造一个数据域为 X 的新结点 LNode FindPrefious(ElemType X, LinkList L);初始条件：线性表 L 已存在。 操作结果：在线性表 L 中寻找值为 X 的结点，若找到则返回该结点的前驱，否则返回 NULL。 void ListDelete(LNode Pre);初始条件：线性表 L 中结点 P 已找到。 操作结果：删除该结点。 链 表 的 结 点 结 构 :dat
4、anext data 域 -存 放 结 点 值 的 数 据 域next 域 -存 放 结 点 的 直 接 后 继 的 地 址 （ 位 置 ） 的 指 针 域 （ 链 域 ）3此 题 定 义 系 数 和 指 数 结 构 如 下 ：020406080100第 一 季 度 第 三 季 度东 部西 部北 部coef exp next/-线性表的单链表存储结构 -/Typedef struct LnodeElemType data;/结点的数据域Struct Lnode *next;/结点的指针域Lnode, *LinkList;/-基本操作-/InitArray(&A, n, bound1, ., b
5、oundn)操作结果：若维数 n 和各维长度合法则构造相应数组 A。DestroyArray(&A)初始条件：数组 A 已经存在。操作结果：销毁数组 A。Value(A, &e, index1, ., indexn)初始条件：A 是 n 维数组， e 为元素变量， n 个下标值。操作结果：若各下标不超界，则 e 赋值为所指定的 A 的元素值，并返回 OK。Assign(&A, e, index1, ., indexn)初始条件：A 是 n 维数组， e 为元素变量，n 个下标值。操作结果：若下标不超界，则将 e 的值赋给 A 中指定下标的元素。 ADT Array 三、详细设计单链表在 C 语
6、言中是一种非常常见的结构，而在 C+中的实现却又有不同，在一些地方更简单，更严密。同时，由于 C+的一些特点，使它具有 C 语言所不具有的“安全化”，所以本程序用 C+。有了链表特定的数据类型 Mulpoly，接下来就需要建立这个链表。这里我们自定义一个构造函数 CreatePoly 来构造链表。首先定义一个 CreatePoly 型的指针变量 head 作为头结点，存储多项式的信息（项数） ，为 head 分配存储空间建立一个头结点并为其数据域赋值，分配存储空间用 c+语言中的 malloc 来实现；这时输入多项式的项数 num，把它赋值给head 的 coef 域，exp 域赋值为 1，此
7、时再定义一个 CreatePoly 型的指针变量 r 指向 head 头结点。还要用类似的算法建立多项式的其它结点，剩余节点的插入用一个 while 循环来实现，while 循环中的控制变量 i 从大于 0 的数 n 开始递增，直到到达 num，此时 while 循环结束。While 循环的循环体由两部分组成，第一部分是为指针变量 s 分配存储空间和为其数据域赋值，分配存储空间同样用 c+语言中的 malloc 来实现；第二部分是节点的指针域转换过程，将 r 的指针域指向新生成的结点 s，相当于将生成结点依次用指针连接，然后将最后一个结点的指针域设置为 NULL，具体代码如下：4MulPoly
8、 *CreatePoly()MulPoly *head,*r,*s;int m,n,num,i=1;head=(MulPoly *)malloc(sizeof(MulPoly);coutnum;head-coef=num;head-exp=1;r=head;while(inm;s-exp=m;s-coef=n;r-next=s;r=s;i+;r-next=null;return(head); 在处理多项式相乘的问题时，定义一个 PolyMulti 函数实现，需要再建立一个 MulPoly型的链表存储相乘之后的链表，定义结果链表的系数等于链表 P1 的系数乘以链表 P2 的系数：(p-coef)
9、=(p1-coef)*(p2-coef) 结果链表的指数等于链表 P1 的指数乘以链表 P2 的指数：(p-exp)=(p1-exp)+(p2-exp)。在整理之后可能出现零结点，那么就需要进行判断和删除操作同时释放零结点，这些操作是通过一个 while 循环来完成。具体代码如下：while(p!=q)s=q;q=q-next;s-next=q-next;free(q); 还需要定义一个输出函数，在主函数中调用输出两个多项式相乘后的结果。程序的最终都是由主函数来实现。在主函数中通过对一些自定义函数的调用实现具体的操作。在此主函数调用了一个构建链表的函数 CreatePoly、一个删除空结点的函
10、数 Delete 和输出函数Print。在主函数的开始需要定义三个 MulPoly 型指针变量，分别用来存储调用 CreatePoly函数和 PolyMulti 函数生成的链表和结果链表。在构建链表之前要给节点分配存储空间，5s=(MulPoly *)malloc(sizeof(MulPoly);这条语句便可完成此操作。此条语句运用了 c+语言库函数中的 malloc 函数，这个函数的作用是在内存的动态存储区中分配一个长度为sizeof(MulPoly)的内存空间。调用构建链表函数 CreatePoly 后链表 Pl 便构建完成。接下来需要执行 m=PolyMulti(p,q);语句，这条语句
11、的目的是把多项式 P1 和 P2 相乘的结果多项式存储在链表 m 当中，然后执行 Print(m);语句显示输出。主函数的程序框架如下：int main()MulPoly *p,*q,*m;p=CreatePoly();q=CreatePoly();m=PolyMulti(p,q);Merge_Same(m);Print(m);system(pause); 四、调试分析程序的调试是程序顺利完成中非常关键的一步。通过程序的调试分析可以解决程序的运行错误也可以对程序的性能进行分析。这个多项式运算问题研究的程序最重要的就是看输出的链表是否正确，是否带有空结点，合并是否完全。决定程序成功与否的第一步是
12、定义的 PolyMulti 函数操作是否正确。如果这一步中出现错误，那么接下来的操作可以说是错上加错。在调试的时候可以在程序中加入删除、释放空结点操作，此操作便是由 Delete函数完成的，若输出的多项式没有空结点说明函数正确，可以继续向下进行。接下来就是相乘后的合并同类项，控制此操作的关键是一个 Merge_Same 函数，调用 Delete 函数是决定成功与否的关键。可以先在本上写出两个正确的简单的多项式，使其具有相加后出现空结点的特点，然后变换循环变量的范围，当输出吻合时则说明操作正确。各个关键部分都已检查完毕，剩下的就是对程序的进一步细心的完善直到满足要求。下面我们分析一下程序的性能。
13、在主函数中，首先调用的是构造单链表函数CreatePoly，在这个函数中需要通过一个 for 循环为每个结点分配存储空间，变换节点的next 域，时间复杂度为 O（n ） 。接下来执行一个双重 for 循环，在内部的 for 循环中是对结点的相加、相乘操作，因为是按着指针的方向就可以对结点进行相加、相乘操作，所以每个结点的操作都需要 m 次，共 n 个结点，则需要 mn 次操作，时间复杂度为 O（n n） 。五、测试结果下面我们测试 P1=2x1+3x2+4x3;P2=1x3+4x0;P=P1*P2=(2x1+3x2+4x3)*( 1x3+4x0)=2x4+8x1+3x5+12x2+4x6+1
14、6x36测试结果如图 5-1：图 5-1 运行结果测试 P1=8*x1+9*x0+7*x2+6*x3;P2=0*x0+1*x3+5*x2P=P1*P2=(8*x1+9*x0+7*x2+6*x3)*( 0*x0+1*x3+5*x2)测试结果如图 5-2：图 5-2 运行结果测试 P1=4.00x3+5.00x2+6.00x1+7.00;P2=1.00x2+3.00x1+6.00P=P1*P2=(4.00x3+5.00x2+6.00x1+7.00)*( 1.00x2+3.00x1+6.00)7数组测试结果：六、附录/*程序源代码：*/单链表表示#include #include #include #include#define null 0using namespace std;typedef struct term /项的表示，多项式的项作为 LinkList 的数据元素 float coef; /系数 int expn; /指数 struct term *next; term; int Empty(term *L)if(L-next!=null)return 1;return 0;8term *Create
