数据结构课程设计-多元多项式的操作.docx

数
据
结
构
课
程
设
计
姓名：杨文杰
班级：2013130301
专业：计算机科学与技术
学号：201313030123

实验报告——5.3
1. 实验题目：多元多项式的操作。
2. 问题描述：
（1）实现多元多项式的求函数值、求偏导函数和加法运算。
（2）稀疏多元多项式采用广义表存储；
（3）输入要求：输入多元多项式的变元个数，各项按（系数，指数）对输入，可按任意顺序输入各项，相同指数项可以多次输入，由程序合并同类项，以（0，0，…，0）结束输入，建立该多项式的广义表存储结构；
例如：输入为
3 //变元个数为3
3 2 1 3 //3x2yz3
-4 1 0 5 //-4xz5
2 2 0 3 //2 xyz3
0 0 0 0
（4）输出要求：按多项式的形式输出，如上面输入的多项式输出为：(2x+3x^2)yz^3-4xz^5；
（5）求多元多项式的函数值：从键盘输入各个变元的当前值；
（6）求多元多项式的偏导函数，仍然采用广义表存储，并输出；
（7）多元多项式的加、减、乘法运算。
3.概要设计
（1）存储结构的选择：由于是多元稀疏多项式的基本运算，用顺序表存储浪费存储空间，故采用广义表表示稀疏多项式。用广义表存储多元多项式P(x1,x2,..,xn)，实为按变元xn的升幂顺序建立一个带头结点的有序链表，链表中的每个节点结构有两种：（1，exp，hp，tp），其中1表示表结点，即xn的系数是一个多项式，hp指向其系数多项式的链表（也是一个与xn的有序表同构的链表），tp指向xn的下一幂次项的结点；（0，coef，exp，tp），0表示原子结点，即xn的exp幂次项的系数是常数。

（2）多项式的结点抽象数据类型：
ADT PNode{
数据对象：D={ai|ai∈TermSet,i=1,2,3,…,n,n≥0，TermSet中的每个元素是多项式的一项（系数，指数）}
数据关系：R={<ai-1,ai,>|ai-1,ai∈D,i=2,3,4,…,n，且ai-1的指数小于ai 的指数，即按指数递增}
基本操作：
PNode(P);
构造一个节点P。
PNode(const PNode &pa);
通过Pa构造节点P。
PNode & operator=(const PNode &pa);
运算符重载
ClearNode();
清除节点P
实现多项式的乘法：La*=Lb，并将Lb置空。
}ADT PNode;

（3）存放系数指数对的结构体定义：
struct Term{
double coef;
系数。
int expn[MAXVAR+1];
指数。
}struct Term;

（4）多元多项式的广义表的ADT定义：
ADT PList{
数据对象：D={ai|i=2,3,…,n,n≥0;ai∈D0 或者属于某个广义表，D0是某个数据对象}
数据关系：R={<ai-1,ai,>|ai-1,ai∈D,i=2,3,4,…,n}
基本操作：

InitPList(&LS);
建立空的广义表LS。
GreatePList(&LS);
建立广义表LS。
DestroyPList(&LS);
销毁广义表LS。
CopyPList(&LS,L);
由广义表L复制到广义表LS。
PListEmpty(LS);
判断广义表LS是否是空表。
GetHead(LS);
取广义表LS的表头。
InsertInOrder(PNode * &p,PNode *pb);
将pb头结点后各项插入到p中使P仍递增有序并合并同类项。
PList &operator =(const PList &L);
重载辅赋值运算符。
PList &operator +=(PList &L);
重载复合赋值运算符。
PList &operator -=(PList &Lb);
重载复合赋值运算符:La-=Lb。
PList &operator *=(double a);
重载复合赋值运算符:La*=Lb。
void Derivative();
求偏导函数。
void Display(PNode *p)const;
输出多项式。
double Value(PNode *p,double *value);
求多项式在x处的值
} ADT GList

4． 详细设计
（1）广义表结点类：
class PNode //多项式的广义表结点类
{
friend class PList; //将广义表类说明为友元类
public:
int tag; //标志域，原子结点tag=0，表结点tag=1
int exp; //指数域
PNode *tp; //指向相同层的下一个链接点
union{double coef; //原子结点使用coef域存放字符
PNode *hp;}; //表结点使用hp指针指向下层单链表的第一个结点
PNode():tag(1),tp(NULL),hp(NULL){}; //构造函数
PNode(const PNode &pa);
PNode(int t,int ex):tag(t),exp(ex),tp(NULL),hp(NULL){};
PNode & operator=(const PNode &pa); //运算符重载
void ClearNode();
};
（2）广义表类
class PList //多元多项式的广义表类
{
friend PList & operator +(PList &La,PList &Lb); //重载加法运算
friend PList & operator -(PList &La,PList &Lb); //重载减法运算
friend PList & operator *(PList &La,double a); //重载乘法运算
private:
PNode *head; //表头指针
void CreateTerm(PNode * &h,Term x,int n); //根据x创建不带头结点的广义表
void InsertInOrder(PNode * &p,PNode *pb); //pb头结点后各项有序插入到p中
void CopyPList(PNode *L,PNode * &T); //由广义表L复制得到T递归函数
public:
PList(int x=0){head=new PNode;head->tag=1;head->exp=x;};//构造函数
PList(const PList &L){head=L.head;}; //拷贝构造函数
PList &operator =(const PList &L);
PList &operator +=(PList &L); //重载复合赋值运算符
PList &operator -=(PList &Lb); //重载复合赋值运算符:La-=Lb
PList &operator *=(double a); //重载复合赋值运算符:La*=Lb
void MUL(PNode *p,double a);
double Value(PNode *p,double *value);
void Derivative(); //求偏导函数
void Display(PNode *p)const; //输出多项式
PNode *Head(){return head;}
void CreatePList();
bool IsEmpty(){return !head->hp;}
};

5.调试分析