39_n元多项式相乘.doc

数据结构
课程设计报告
设计题目:n元多项式乘法
学号:
姓名:
指导教师:
专业:
班级:
学年学期:
起止时间:
哈尔滨师范大学
计算机科学与信息工程学院
多项式运算的算法分析和设计
具体任务
功能:完成两个n元多项式作乘法,给出明确的等式形式。
分步实施:1). 初步完成总体设计,搭好框架,确定人机对话的界面,确定函数个数;
2). 完成最低要求:建立一个文件,实现两个一元二次多项式作乘法。
3). 进一步要求:实现三元二次多项式的乘法。
概要设计
定义单链表的抽象数据类型:
ADT LinkList{
数据对象:D={ai|ai∈ElemSet,i=1,2,3,…,n>=0}
数据关系:R={<ai,ai+1>|ai,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结点的个数。
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已找到。操作结果:删除该结点。
链表的结点结构:
┌──┬──┐
│data│next│
└──┴──┘
data域--存放结点值的数据域
next域--存放结点的直接后继的地址(位置)的指针域(链域)
此题定义系数和指数结构如下:
coef
exp
next
//------------------------------------------线性表的单链表存储结构-----------------------------------//
Typedef struct Lnode{
ElemType data;//结点的数据域
Struct Lnode *next;//结点的指针域
}Lnode, *LinkList;
//----------------------基本操作---------------------------------------------------------------------------//
InitArray(&A, n, bound1, ..., boundn)
操作结果:若维数 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语言中是一种非常常见的结构,而在C++中的实现却又有不同,在一些地方更简单,更严密。同时,由于C++的一些特点,使它具有C语言所不具有的“安全化”,所以本程序用C++。
有了链表特定的数据类型Mulpoly,接下来就需要建立这个链表。这里我们自定义一个构造函数CreatePoly来构造链表。首先定义一个CreatePoly型的指针变量head作为头结点,存储多项式的信息(项数),为head分配存储空间建立一个头结点并