数据结构课程报告

姓名：周涛

学号：201313040322

问题描述与功能设计

本程序要求能够实现从键盘键入两个多项式的系数、指数相关数据后，能够进行多项式输出、多项式相加、多项式相减的运算。

数据结构与算法

多项式的逻辑结构：视为线性表

p(x)=3x14-8x8+6x2+2

数据元素 (coef,exp)

表示多项式项 coef·X^exp ，coef是该项的系数，exp是变元X的指数。

算法

多项式的输入与建立

调用CreatePolyn（）函数建立链表，将多项式每一项的系数与指数作为链表一个结点的数据，按照指示输入每一项的系数与指数时，将调用Insert（）函数，将输入的结点信息按指数降序排列的方式插入到之前建立的链表中，并合并同类项。依次输入、建立一元多项式pa和pb。如下图。

多项式的输出

调用PrintPolyn（）函数将多项式链表中的结点数据按照一元多项式的格式(如：6x^5+3x^3+7x+3)输出到屏幕上。

两个多项式的加法

调用AddPolyn（）函数直接对两个多项式的链表的结点成员的系数与指数按照数学中多项式相加的原则进行操作。其中要调用compare（）函数对两个多项式的指数或是项数进行比较。相加所得的多项式存放到新建的第三个多项式中。再对第三个多项式输出即可。

两个多项式的减法

调用SubtractPolyn（）函数对两个多项式减法运算。首先对要减的多项式的系数求反，接着调用AddPolyn（）函数对处理后的多项式相加即两个多项式的相减。所得的多项式存放到新建的第三个多项式中，再对第三个多项式输出即可。

函数定义

为了程序功能的顺利实现，在本程序中定义了如下函数：

函数名功能

Insert() 链表结点数据的插入与排序

CreatePolyn() 链表头结点的创建

DestroyPolyn() 链表的销毁

PrintPolyn() 链表数据的多项式形象化输出

Compare() 两个多项式的指数或是项数进行比较

AddPolyn() 两个多项式的加法

SubtractPolyn() 两个多项式的减法

desktop() 程序界面的实现

编码

链表建立的函数,该函数在多项式信息输入时按照指数降序排列建立链表，并在出现同类项时合并。

void Insert(Polyn p,Polyn h)

{

if(p->coe==0) delete p; //当前结点的coe成员等于0的时候删除当前结点

else{

Polyn q1,q2;

q1=h;q2=h->next;

while(q2&&p->exp<q2->exp) //查找插入位置

{

q1=q2;

q2=q2->next;

}

if(q2&&p->exp==q2->exp) //将指数相同相合并

{

q2->coe+=p->coe;

delete p;

if(!q2->coe)

{

q1->next=q2->next;

delete q2;

}

else//指数为新时将结点插入

{

p->next=q2;

q1->next=p;

}

链表信息按照多项式形式输出。

void PrintPolyn(Polyn P){

Polyn q=P->next;

int flag=1; //项数计数器

if(!q)

{ //若多项式为空，输出0

cout<<"0";

cout<<endl;

return;

}

while (q)

{

if(q->coe>0&&flag!=1) cout<<"+"; //系数大于0且不是第一项时就输出+

if(q->coe!=1&&q->coe!=-1) //系数非1或-1的普通情况

{

cout<<q->coe;

if(q->exp==1) cout<<"X";//当前结点exp为1时

else if(q->exp) cout<<"X^"<<q->exp;

}

else

{

if(q->coe==1) 系数为1的特殊情况

{

if(!q->exp) cout<<"1";//指数不存在

else if(q->exp==1) cout<<"X";/指数等于一

else cout<<"X^"<<q->exp;

}

if(q->coe==-1) 系数为-1的特殊情况情况

{

if(!q->exp) cout<<"-1"; //指数不存在

else if(q->exp==1) cout<<"-X"; //指数等于一

else cout<<"-X^"<<q->exp;

}

q=q->next; //当前指针指向下一结点

flag++;//项序数自加1

}

cout<<endl;

}

两个多项式的加法。

int compare(Polyn a,Polyn b)//对两个多项式的系数或项数进行比较

{

if(a&&b) {//两个多项式都存在

if(!b||a->exp>b->exp) return 1;当b多项式不存在或者a多项式的指数大于b的的时候，返回1

else if(!a||a->exp<b->exp) return -1; 当a多项式不存在或者b多项式的指数大于a的的时候，返回-1

else return 0;//其他情况返回0

}

else if(!a&&b) return -1; //a多项式已空，但b多项式非空

else return 1; //b多项式已空，但a多项式非空

}

Polyn AddPolyn(Polyn pa,Polyn pb)

{

Polyn qa=pa->next;

Polyn qb=pb->next;

Polyn headc,hc,qc;

hc=new Polynomial;//建立一个新的结点

hc->next=NULL;

headc=hc;

while(qa||qb){

qc=new Polynomial;//新建一个结点

switch(compare(qa,qb)){//调用compare函数对两个多项式进行比较

case 1:// a多项式的指数大于b的

{

qc->coe=qa->coe;

qc->exp=qa->exp;

qa=qa->next;

break;

}

case 0://有同类项则合并

{

qc->coe=qa->coe+qb->coe;

qc->exp=qa->exp;

qa=qa->next;

qb=qb->next;

break;

}

case -1: a多项式的指数小于b的

{

qc->coe=qb->coe;

qc->exp=qb->exp;

qb=qb->next;

break;

}

if(qc->coe!=0){ //当相加系数不为0时

qc->next=hc->next;

hc->next=qc;

hc=qc;

}

else delete qc; //当相加系数为0时，释放该结点

}

return headc;

}

两个多项式的减法。两个多项式的减法是建立在加法的的基础上，对要减的多项式的系数求反，接着调用AddPolyn（）函数对处理后的多项式相加即两个多项式的相减

Polyn SubtractPolyn(Polyn pa,Polyn pb)

{

Polyn h=pb;

Polyn p=pb->next;//新建一个结点作为pb的后继结点

Polyn pd;

while(p)//当结点存在时，对所有coe数据求反

{

p->coe*=-1;

p=p->next;

}

pd=AddPolyn(pa,h);//调用加法函数

for(p=h->next;p;p=p->next) //恢复pb的系数

p->coe*=-1;

return pd;

}

测试及结果

测试的数据：

(1) A+B A= 3x¹⁴-8x⁸+6x²+2 B=2x¹⁰+4x⁸+-6x²

(2) A-B A=11x¹⁴+3x¹⁰+2x⁸+10x⁶+5 B=2x¹⁴+3x⁸+5x⁶+7

思考

通过这个一元多项市的设计,熟悉了数据结构中数据之间的存储,

自己的程序还有一些bug，一些数据的限制还不够完善，对于乘法的设计也没有完成，，，

在程序做完一组数据后，若要重新输入多项市的参数，只能退出后在进入，返回没有实现，本来想有一个goto的，没搞好。

返回搞好了，但是测试图没有重新弄。

还有就是数据测试的事例还太少，一些边际的数据还没测试。

下次努力更好。

附录源代码

#include<iostream>

#include <stdlib.h>

#include <math.h>

using namespace std;

typedef struct Polynomial{

int coe;

int exp;

struct Polynomial *next;

}*Polyn,Polynomial;

void Insert(Polyn p,Polyn h)//在多项式信息输入时按照指数降序排列建立链表，实现同类项时合并。

{

if(p->coe==0) delete p;

else{

Polyn q1,q2;

q1=h;q2=h->next;

while(q2&&p->exp<q2->exp)

{

q1=q2;

q2=q2->next;

}

if(q2&&p->exp==q2->exp)

{

q2->coe+=p->coe;

delete p;

if(!q2->coe)

{

q1->next=q2->next;

delete q2;

}

else

{

p->next=q2;

q1->next=p;

}

Polyn CreatePolyn(Polyn head,int m)// 链表头结点的创建

{

int i;

Polyn p;

p=head=new Polynomial;

head->next=NULL;

for(i=0;i<m;i++){

p=new Polynomial;;

cout<<"请输入第"<<i+1<<"项的系数:";

cin>>p->coe;

cout<<" 指数:";

cin>>p->exp;

Insert(p,head);

}

return head;

}

void DestroyPolyn(Polyn p)// 链表的销毁

{

Polyn t;

while(p!=NULL)

{

t=p;

p=p->next;

delete t;

}

void PrintPolyn(Polyn P)// 链表数据的多项式输出

{

Polyn q=P->next;

int flag=1;

if(!q)

{

cout<<"0";

cout<<endl;

return;

}

while (q)

{

if(q->coe>0&&flag!=1) cout<<"+";

if(q->coe!=1&&q->coe!=-1)

{

cout<<q->coe;

if(q->exp==1) cout<<"X";

else if(q->exp) cout<<"X^"<<q->exp;

}

else

{

if(q->coe==1)

{

if(!q->exp) cout<<"1";

else if(q->exp==1) cout<<"X";

else cout<<"X^"<<q->exp;

}

if(q->coe==-1)

{

if(!q->exp) cout<<"-1";

else if(q->exp==1) cout<<"-X";

else cout<<"-X^"<<q->exp;

}

q=q->next;

flag++;

}

cout<<endl;

}

int compare(Polyn a,Polyn b)//两个多项式的指数,项数进行比较

{

if(a&&b)

{

if(!b||a->exp>b->exp) return 1;

else if(!a||a->exp<b->exp) return -1;

else return 0;

}

else if(!a&&b) return -1;

else return 1;

}

Polyn AddPolyn(Polyn pa,Polyn pb)//两个多项式的加法

{

Polyn qa=pa->next;

Polyn qb=pb->next;

Polyn headc,hc,qc;

hc=new Polynomial;

hc->next=NULL;

headc=hc;

while(qa||qb)

{

qc=new Polynomial;

switch(compare(qa,qb))

{

case 1:

{

qc->coe=qa->coe;

qc->exp=qa->exp;

qa=qa->next;

break;

}

case 0:

{

qc->coe=qa->coe+qb->coe;

qc->exp=qa->exp;

qa=qa->next;

qb=qb->next;

break;

}

case -1:

{

qc->coe=qb->coe;

qc->exp=qb->exp;

qb=qb->next;

break;

}

if(qc->coe!=0)

{

qc->next=hc->next;

hc->next=qc;

hc=qc;

}

else delete qc;

}

return headc;

}

Polyn SubtractPolyn(Polyn pa,Polyn pb)//两个多项式的减法

{

Polyn h=pb;

Polyn p=pb->next;

Polyn pd;

while(p)

{

p->coe*=-1;

p=p->next;

}

pd=AddPolyn(pa,h);

for(p=h->next;p;p=p->next)

p->coe*=-1;

return pd;

}

void desktop()

{

system("cls");

cout<<" 一元多项式的计算"<<endl;

cout<<"**********************************************"<<endl;

cout<<"** 1.输出多项式a和b **"<<endl;

cout<<"** 2.建立多项式a+b **"<<endl;

cout<<"** 3.建立多项式a-b **"<<endl;

cout<<"** 4.返回重新输入参数 **"<<endl;

cout<<"**********************************************"<<endl;

cout<<"执行操作:";

}

int main()

{

int m,n;

float x,result;

char key;

Polyn pa,pb,pc,pd,pf;

r1:

cout<<"欢迎"<<endl;

cout<<"请输入多项式A的项数:";

cin>>m;

pa=CreatePolyn(pa,m);

cout<<endl;

cout<<"请输入多项式B的项数:";

cin>>n;

pb=CreatePolyn(pb,n);

system("pause");

system("cls");

while(key)

{

desktop();

cin>>key;

switch (key)

{

case'1':

cout<<"多项式a：";

PrintPolyn(pa);

cout<<"多项式b：";

PrintPolyn(pb);

break;

case'2':

pc=AddPolyn(pa,pb);

cout<<"多项式a：";

PrintPolyn(pa);

cout<<"多项式b：";

PrintPolyn(pb);

cout<<"多项式a+b：";

PrintPolyn(pc);

DestroyPolyn(pc);

break;

case'3':

pd=SubtractPolyn(pa,pb);

cout<<"多项式a：";

PrintPolyn(pa);

cout<<"多项式b：";

PrintPolyn(pb);

cout<<"多项式a-b：";

PrintPolyn(pd);

DestroyPolyn(pd);

break;

case'4':

DestroyPolyn(pa);

DestroyPolyn(pb);

system("cls");

goto r1;

break;

default:

cout<<"Error!!!"<<endl;

}

cout<<endl<<endl;

system("pause");

}

相关推荐