一元稀疏多项式计算器实现(完整实现版-详细源码).doc

1.5一元稀疏多项式计算器
实习报告
一、 需求分析
1．输入并建立多项式；　　
2．输出多项式，输出形式为整数序列：n，c1，e1，c2，e2，……，cn，en，其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；　　　
3．多项式a和b相加，建立多项式a＋b；　
4．多项式a和b相减，建立多项式a—b；　　　
5．多项式a和b相乘，建立多项式a×b；　　　
6．计算多项式在x处的值；　
7．求多项式P的导函数P'；
8.多项式的输出形式为类数学表达式；
9.做出计算器的仿真界面；
10. 测试数据：　　　
（1） (2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7)　
（2） (6x^-3-x+4.4x^2-1.2x^9+1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^15 )　
=(-7.8x^15-1.2x^9+12x^-3-x);　
（3）(1+x+x^2+x^3+x^4+x^5)+(-x^3-x^4)=(1+x+x^2+x^5);　
（4）(x+x^3)+(-x-x^3)=0　　
（5）(x+x^100)+(x^100+x^200)=(x+2x^100+x^200)　
（6）(x+x^2+x^3)+0=x+x^2+x^3　　
（7）互换上述测试数据中的前后两个多项式
二、 概要设计
1. 链表的抽象数据类型定义为：
ADT LinkList{
数据对象：D＝{ ai | ai∈ElemSet, i=1,2,...,n, n≥0 }
数据关系：R1＝{ <ai-1, ai>|ai-1, ai∈D, i=2,...,n }
基本操作：
InitList(&L)
操作结果：构造一个空的线性表L。
DestroyList(&L)
初始条件：线性表L已存在。
操作结果：销毁线性表L。
ClearList(*L)
初始条件：线性表L已存在。
操作结果：将线性表L重置为空表。
LocateElem(L, e, cmp())
初始条件：线性表L已存在，compare()是元素判定函数。
操作结果：返回L中第1个与e满足关系cmp()的元素的位序。 若这样的元素不存在，则返回值为0。
SetCurElem(&p, e)
初始条件：线性表L已存在，且非空。
操作结果：用元数e更新p所指结点中元数的值。
GetCurElem(p)
初始条件：线性表L已存在，且非空。
操作结果：返回p所指结点中数据元数的值。
InsFirst (&L, h, s)
初始条件：线性表L已存在，h结点在L中。
操作结果：在L的s所指结点插入在h结点之后，L的长度加1。 DelFirst (&L, h, q)
初始条件：线性表L已存在且非空，q结点在L中且不是尾结点
操作结果：删除链表L中的h结点之后的结点q，L的长度减1。
MakeNode(&p, e)
操作结果：创建了一个结点p，其data部分为e。
FreeNode(&p)
初始条件：结点p存在且非空。
操作结果：释放结点p空间。
Append(LinkList &L,Link s)
初始条件：线性表L已存在。
操作结果：s及s以后的结点链接到了原L之后，L的长度增加链上的结点数。
ListEmpty(L)
初始条件：线性表L已存在。
操作结果：若线性链表L为空表，则返回TRUE,否则返回FALSE。
GetHead(L)
初始条件：线性表L已存在。
操作结果：返回线性链表L中头结点的位置。
NextPos(L, p)
初始条件：线性表L已存在。
操作结果：返回p所指结点的直接后继的位置，若没后继，则返回NULL。
int cmp(a, b)
初始条件：存在两个元数。
操作结果：比较a，b的数值，分别返回-1，0，1。
} ADT LinkList
2.一元多项式的抽象数据类型定义为：
ADT Polynomial{
数据对象：D＝{ ai | ai∈TermSet, i=1,2,...,m, m≥0
TermSet中的每个元素包含一个表示系数的实数和表示指数的整数}
数据关系：R1＝{ <ai-1, ai>|ai-1, ai∈D, 且ai-1中的指数值<ai中的指数值，i=2，……，n}
基本操作：
CreatPolyn（&P，m）
操作结果：输入m项的系数和指数，建立一元多项式P。
DestroyPolyn（&P）
初始条件：一元多项式P已存在。
操作结果：销毁一元多项式P。
AddPolyn（&Pa，&Pb）
初始条件：一元多项式Pa和Pb已存在。
操作结果：完成多项式相加运算，即：Pa=Pa+Pb，并销毁一元多项式Pb。
SubtractPolyn(&Pa,&Pb)
初始条件：一元多项式Pa和Pb已存在。
操作结果：完成多项式相减运算，即：Pa=Pa-Pb，并销毁一元多项式Pb。
MultiplyPolyn(&Pa,&Pb)
初始条件：一元多项式Pa和Pb已存在。
操作结果：完成多项式相乘运算，即：Pa=Pa×Pb，并销毁一元多项式Pb。DerivPolyn(&Pa)
初始条件：一元多项式Pa已存在。
操作结果：多项式求导。
CalPolyn(Pa , x)
初始条件：一元多项式Pa已存在。
操作结果：求多项式在x处的值。
PrintPolyn(p, m)
初始条件：一元多项式p已存在，且已知多项式项数。
操作结果：打印输出一元多项式p的项数、系数和指数。
Expression(p, m)
初始条件：一元多项式p已存在，且已知多项式项数。
操作结果：打印输出一元多项式的类数学表达式。
SortPolyn(&p)
初始条件：一元多项式p已存在。
操作结果：对多项式p进行排序
}ADT Polynomial
3.本程序包含4个模块：
(1)主程序模块：
int main(){
初始化；
接受命令；
while（命令！=推出）{
处理命令；
接受命令；
}
return 0;
}
(2)一元多项式单元模块——实现一元多项式的抽象数据类型；
（3）链表单元模块——实现链表的抽象数据类型；
(4)结点结构单元模块——定义链表的节点结构。
各模块之间的调用关系如下：
主程序模块 一元多项式单元模块 链表单元模块
结点结构单元模块
三、 详细设计
1.设计好的数据类型：　
typedef struct{ //项的表示，多项式的项作为Linklist的数据元素　　　
float coef; //系数　
int expn; //指数　
} term, ElemType;//两个类名：term用于本ADT，ElemType为Linklist的数据对象名　

typedef struct LNode {//结点类型　
ElemType data;　　
struct LNode *next;　　　
} *Link, *Position;　　

typedef struct{//链表类型　　
Link head,tail; //分别指向线性链表中的头结点和最后一个结点　　　
int len; //指示线性链表中数据个数　　
} LinkList;　　
typedef LinkList polynomial;//基于带头结点的线性链表定义的多项式数据类型　　

2.基于链表、结点的操作(部分伪码如下)　　　
// 分配由p指向值为e的结点,并返回OK,若分配失败,则返回ERROR。　　　
Status MakeNode(Link &p, ElemType e);

//释放p所指结点　
void FreeNode(Link &p);　　

//构造一个空的线性链表L　　
Status InitList(LinkList &L);　　
{
L.head=L.tail=(Link)malloc(sizeof(LNode));
L.len=0;
L.head->next=L.tail->next=NULL;
return OK;
}

// 返回线性表L中头结点的位置。　　
Position GetHead(LinkList &L);　

//已知p指向线性链表L中的一个结点，返回p所指结点的直接后驱的位置　　
//若无后继，返回NULL　
Position Nextpos(LinkList &L,Link p);　　　

//已知p指向线性表L中的一个结点,返回p所指结点中数据元素的值。　　　
ElemType GetCurElem(Link p);　　　

//已知p指向线性链表L中的一个结点,用e更新p所指结点中数据元素的值。　
Status SetCurElem(Link &p,float e);　　　

//已知h指向线性链表的某个结点,将q所指的结点插入在h之后。　
Status InsFirst(Link h,Link q);　
{
s->next=h->next;
h->next=s;
L.len++;
if(!s->next)
L.tail=s;
return OK;
}　

//已知h指向线性链表的头结点,删除线性链表第一个指结点并以q返回　　
Status DelFirst(Link h,Link &q);　　　

//若线性链表L为空,则返回TRUE,否则返回FALSE。　
Status ListEmpty(LinkList L);　　　
{
if(L.head==L.tail==NULL)
return TRUE;
else return FALSE;
}

//将指针s所指的一连串结点连接在线性表L的最后一个结点之后,并改变链表L的尾指针指向新的尾结点。　
Status Append(polynomial &L,Link s);　　
{
i=0;
q=s;
while(s) {//找到新的tail，计数s长度
p=s;
s=s->next;
i++;
}
L.tail->next=q;
L.tail=p;
L.len+=i;
return OK;
}

//判断已知链表中，是否存在相同的元素e，若存在返回TURE，且q指示L中第一个与e相同的结点元素；　　　
//否则返回FALSE,并q指示L中第一个稍大于e的元素的直接前驱的位置　　　
Status LocateElem(LinkList L,ElemType e,Position &q);　　　
{
p=L.head;
while(p->next) {
s=p;
p=p->next;
m=p->data;
if(cmp(e,m )==0) {
q=p;
return TRUE;
}

}
q=p;
return FALSE;
}

//整表删除
void ClearList(LinkList &L);　　
{
if(L.head!=L.tail) {
p=q=L.head->next;
L.head->next=NULL;
while(p!=L.tail) {
p=q->next;
free(q);
q=p;
}
free(q);
L.tail=L.head;
L.len=0;
}
return OK;
}

//依a的指数值<（或=）(或>）b的指数数值，分别返回-1，0，+1　　
int cmp(term a, term b) ;　　　
{
if(a.expn<b.expn)
return -1;
if(a.expn==b.expn)
return 0;
if(a.expn>b.expn)
return 1;
}

3.基于多项式的操作（部分伪码如下）
//输入m项的系数和指数，建立表示一元多项式的有序链表P　
void CreatPolyn(polynomial &p,int m);
{
InitList(p);
h=GetHead(p);
e.coef=0.0;
e.expn=-1;
SetCurElem(h,e);
for(int i=1;i<=m;i++){
cout<<"请输入第"<<i<<"项的系数和指数（按指数降序）：";
cin>>e.coef>>e.expn; cout<<endl;
if(!LocateElem(p,e,q))//当前链表中不存在该指数项
if(MakeNode(s,e)) InsFirst(p,q,s);//生成节点并插入链表
else return;
else {
q->data.coef+=e.coef;
++c;
}
}
m=m-c;
}
//销毁一元多项式P　
void DestroyPolyn(polynomial &p);　
{
while(p.head ->next!=NULL) {
k=p.head;
p.head =p.head ->next;
free(k);
}
free(&p);
}

//打印输出一元多项式P　　　
void PrintPolyn(polynomial p);
{
ha=GetHead(p);
cout<<m<<', ';
for(int i=1;i<=m;i++) {
qa=NextPos(p,ha);
e=GetCurElem(qa);
cout<<e.coef<<','<<e.expn<<', ';
ha=qa;
}
cout<<endl;
}

//打印输出一元多项式的类数学表达式
void Expression(polynomial p,int m);　　　　

//完成多项式的相加运算，即：Pa=Pa+Pb，并销毁一元多项式Pb　
void AddPolyn(polynomial &Pa ,polynomial &Pb);　
{
ha = GetHead(Pa);
hb = GetHead(Pb);//ha和hb分别指向pa和pb的头节点
qa = NextPos(Pa, ha);
qb = NextPos(Pb, hb);

while (qa&&qb) {//qa，qb均非空
a = GetCurElem(qa);
b = GetCurElem(qb);
switch (cmp(a, b)){//a和b为两表比较元数
case -1: //a的指数小于b的指数
DelFirst(Pb, hb, qb);
InsFirst(Pa, ha, qb);
qb = NextPos(Pb, hb);
ha = NextPos(Pa, ha);
break;
case 0: //a的指数等于b的指数
a.coef = a.coef + b.coef;
if (a.coef != 0.0) { //修改多项式Pa中当前结点的系数
SetCurElem(qa, a);
ha = qa;
}
else { //删除多项式Pa中当前结点
DelFirst(Pa, ha, qa);
FreeNode(qa);
}
DelFirst(Pb, hb, qb);
FreeNode(qb);
qb=NextPos(Pb,hb);
qa=NextPos(Pa,ha);
break;
case 1: //a的指数大于b的指数
ha = qa;
qa = NextPos(Pa, qa);
break;
}
}
if (!ListEmpty(Pb)) Append(Pa, qb);//链接Pb中剩余结点
FreeNode(hb);//释放Pb的结点
}

//完成多项式的相减运算，即：Pa=Pa-Pb，并销毁一元多项式Pb　　
void SubtractPolyn(polynomial &Pa ,polynomial &Pb);　

//完成多项式的相减运算，即：Pa=Pa×Pb，并销毁一元多项式Pb　　
void MultiplyPolyn(polynomial &Pa ,polynomial &Pb);　　　
{
InitList(Pc);
qa=GetHead(Pa);
qa=qa->next;
hc=GetHead(Pc);
while(qa) {
a=GetCurElem(qa);
qb=GetHead(Pb);
qb=qb->next;
while(qb) {
b=GetCurElem(qb);
c.coef=a.coef*b.coef;
c.expn=a.expn+b.expn;
MakeNode(qc,c);
InsFirst(Pc,hc,qc);
hc=NextPos(Pc,hc);
qc=NextPos(Pc,qc);
qb=qb->next;
}
qa=qa->next;
}
DestroyPolyn(Pb);
ClearList(Pa);
Pa.head=Pc.head;
Pa.tail=Pc.tail;
Pa.len=Pc.len;
}

//计算多项式在x处的值　
double Evaluation(double x, polynomial p);　　

//计算多项式P的导函数P'　　　
void Derivative( polynomial &p );
{
InitList(Pb);
qa=GetHead(Pa);
qa=qa->next;
hb=GetHead(Pb);
while(qa) {
a=GetCurElem(qa);
b.coef=a.coef*a.expn;
b.expn=a.expn-1;
MakeNode(qb,b);
InsFirst(Pb,hb,qb);
hb=NextPos(Pb,hb);
qb=NextPos(Pb,qb);
qa=qa->next;
}
qb=NULL;
ClearList(Pa);
Pa.head=Pb.head;
Pa.tail=Pb.tail;
Pa.len=Pb.len;
}

4.主函数和其他函数的伪码算法
int main()
{
Initialization();
ReadCommand(cmd);
while (cmd != 'q' && cmd != 'Q')
{
Interpret(cmd);
display();
ReadCommand(cmd);
}
return 0;
}

void Initialization()
{
pre_cmd = ' ';
cmd = ' ';
InitList(La);
InitList(Lb);
}

void display()
{
system("cls"); //清屏
在屏幕上方显示操作命令清单：CreatePolynomial_a ->1 CreatePolynomial_b ->2 a+b ->' a-b –>'' a*b ->* Derivation of a ->d Calculate a in x ->c Quit ->q
在屏幕下方显示操作命令提示框：
Enter a operation code(1,2,+,_,*,c,d OR q): ";
}

void ReadCommand(char &cmd)
{
//读入操作命令符
显示检入操作命令符的提示信息；
do
{
display();
cin >> cmd;
} while (!strchr(cmdsets, cmd));
}

void Interpret(char cmd)
{ //解释执行操作命令cmd
switch (cmd)
{
case '1':
ClearList(La);
cout << "请输入第一个一元多项式的项数";
cin >> n; cout << endl;
CreatPolyn(La, n);//输入多项式
SortPolyn(La);
break;
case '2':
ClearList(Lb);
cout << endl << "请输入第二个一元多项式的项数";
cin >> m; cout << endl;
CreatPolyn(Lb, m);//输入多项式
SortPolyn(Lb);
break;
case '+':
cout << endl << "两多项式相加的结果：";
AddPolyn(La, Lb);
PrintPolyn(La, La.len);
Expression(La,La.len);
getchar();
getchar();
break;
case '-':
cout << endl << "两多项式相减的结果：";
SubtractPolyn(La, Lb);
PrintPolyn(La, La.len);
Expression(La,La.len);
getchar();
getchar();
break;
case '*':
cout << endl << "两多项式相乘的结果：";
MultiplyPolyn(La, Lb);
PrintPolyn(La, La.len);
Expression(La,La.len);
getchar();
getchar();
break;
case 'c':
case 'C':
cout << "请输入x的值" << endl;
cin >> x;
cout << "多项式a在" << x << "处的值为" << CalPolyn(La, x);
getchar();
getchar();
break;
case 'd':
case 'D':
DerivPolyn(La);
cout << "求导结果为";
PrintPolyn(La, La.len);
Expression(La,La.len);
getchar();
getchar();
default:
cout << "输入错误" << endl;
}
}
5.函数的调用关系图反映了演示程序的层次结构

四、 调试分析
1. 一开始写求导部分代码时没有考虑常数项求导变零的情况，结果输出后常数项以系数为0指数为-1的形式输出，不符合规范。调试后加入if判断语句让常数项求导之后的结果不显示出来。
2. 加减法操作出现多项式Pb若有几项的指数比Pa中任一项都小，则那几项在运算过后被漏掉的现象。调试后发现在把Pb剩余结点链接到Pa时出了问题，把Pb的数据链上去了之后没有把Pb的长度减掉，而且Pb的头指针也不见了，所以后面读取的时候会出错。修改了小函数Append以及加减法部分代码之后，解决了这个问题。
3. 类数学表达式输出时会出现“1x”以及“x^1”现象。通过加上if语句区别处理后解决的问题。
4. 本程序的模块划分比较合理，且尽可能将指针的操作封装在结点和链表两个模块中，致使链表模块的调试比较顺利。
5. 算法的时空分析
（1） 由于链表采用带头结点的单链表，并增设尾指针和表的长度两个标识，各种操作的算法时间复杂度比较合理。InitList,ListEmpty等函数都是O(1)，Append，LocateElem及确定链表中间结点的位置等则是O（n）的，n为链表长度。
（2） 基于单链表实现的一元多项式的各种运算和操作的时间复杂度：
加法：O(max{Pa.len,Pb.len})
减法：O(max{Pa.len,Pb.len})
乘法：O(Pa.len*Pb.len)
求导：O(n)
求x处的值：O(n)
输出类数学表达式：O(n) n为链表长度。
6.本实习作业采用数据抽象的程序设计方法，讲程序划分为四个层次的结构：主程序模块、一元多项式单元模块、链表单元模块、结点结构单元模块，使得设计时思路清晰，实现时调试顺利，各模块具有较好的可重用性，确实得到了一次良好的程序设计训练。
五、 用户手册
1. 本程序的运行环境为DOS操作系统，执行文件为：POLYNOMIAL.exe。
2. 进入演示程序后即显示文本方式的用户界面：
操作提示信息
显示多项式
键入操作命令符
操作命令清单

3. 进入“构造多项式a（CreatePolynomial_a）”和构造多项式b（CreatePolynomial_b）”的命令后，即提示键入多项式项数、系数、指数，结束符为“回车符”。
4. 接受其他命令后即执行相应运算和显示相应结果。
六、 测试结果

七、 附录
源程序文件名清单：
Base.h //宏定义说明
LNode.h //链表实现单元
Polynomial.h //一元多项式实现单元
main.cpp //主程序