数据结构课程设计一元多项式计算器.docx

数据结构课程设计一元多项式计算器.docx

《数据结构课程设计一元多项式计算器.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计一元多项式计算器.docx（16页珍藏版）》请在冰点文库上搜索。

数据结构课程设计一元多项式计算器

实习1、一元稀疏多项式计算器

一、需求分析

1.问题描述

设计一个一元稀疏多项式简单计算器。

2.基本要求

一元稀疏多项式简单计算器的基本功能是：

（1）输入并建立多项式。

（2）输出多项式，输出形式为整数序列：

n,c1,e1,c2,e2,········,cn,en，其中n是多项式的项数，ci,ei分别是第i项的系数和指数，序列按指数降序排列。

（3）多项式a和b想加，建立多项式a+b。

（4）多项式a和b想减，建立多项式a-b。

3.测试数据

（1）（2x+5x8-3.1x11）+（7-5x8+11x9）=（-3.1x11+11x9+2x+7）

（2）（6x-3-x+4.4x2-1.2x9）-（-6x-3+5.4x2-x2+7.8x15）=（-7.8x15-1.2x9+12x-3-x）

（3）（1+x+x2+x3+x4+x5）+（-x3-x4）=（1+x+x2+x5）

（4）（x+x3）+（-x-x3）=0

（5）（x+x100）+（x100+x200）=（x+2x100+x200）

（6）（x+x2+x3）+0=（x+x2+x3）

（7）互换测试数据的前后两个多项式。

4.实现提示

用带表头结点的单链表存储多项式。

二、概要设计

为实现上述程序功能，应用带头结点的单链表存储多项式。

为此需要一个抽象数据类型：

一元多项式。

1.抽象数据类型一元多项式定义为：

ATDPloynomial{

数据对象：

D={ai|ai∈Termset,i=1,2,3···，m,m≥0Termset中的每个元素包含一个表示系数的实数和表示指数的整数}

数据关系：

R1={ai-1,ai∈D,且ai-1中的指数

基本操作：

Insert（p,h）

初始条件：

h已存在。

操作结果：

插入p项。

CreateLinklist（head,m）

操作结果：

建立一个头指针为head、项数为m的一元多项式。

DestroyLinklist（p）

初始条件：

一元多项式p已存在。

操作结果：

销毁一元多项式p。

PrintLinklist（P）

初始条件：

一元多项式p已存在。

操作结果：

输出一元多项式p。

Compare（a,b）

初始条件：

项a,b已存在。

操作结果：

比较a,b中x的指数的大小。

AddLinklist（pa,pb）

初始条件：

一元多项式pa,pb已存在。

操作结果：

完成一元多项式pa,pb的相加运算。

SubtractionLinklist（Sa,Sb）

初始条件：

一元多项式Sa,Sb已存在。

操作结果：

完成一元多项式Sa,Sb的相减运算。

}ATDPloynomial

三、详细设计（源代码）

（使用C语言）

#include

#include

#definemaxlen10

#definelarge999

typedefstructLinklistomial

{

floatcoef;

intexpn;

structLinklistomial*next;

}Linklistomial,*Linklist;//结点类型，指针类型

voidInsert（Linklistp,Linklisth）

{//h已存在插入p项

if（p->coef==0）

free（p）;//系数为0的话释放结点

else

{

Linklistq1,q2;

q1=h;

q2=h->next;

while（q2&&p->expnexpn）

{//查找插入位置

q1=q2;

q2=q2->next;

}

if（q2&&p->expn==q2->expn）

{//将指数相同相合并

q2->coef+=p->coef;

free（p）;

if（!

q2->coef）

{//系数为0的话释放结点

q1->next=q2->next;

free（q2）;

}

}

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

p->next=q2;

q1->next=p;}

}

}

LinklistCreateLinklist（Linklisthead,intm）

{//建立一个头指针为head、项数为m的一元多项式

inti;

Linklistp;

p=head=（Linklist）malloc（sizeof（structLinklistomial））;

head->next=NULL;

for（i=0;i

{

p=（Linklist）malloc（sizeof（structLinklistomial））;//建立新结点以接收数据

printf（"请输入第%d项的系数与指数:

",i+1）;

scanf（"%f%d",&p->coef,&p->expn）;

Insert（p,head）;//调用Insert函数插入结点

}

returnhead;

}

voidDestroyLinklist（Linklistp）

{//销毁多项式p

LinklistD1,D2;

D1=p;

while（D1）

{

D2=D1->next;

free（D1）;

D1=D2;

}

}

voidPrintLinklist（LinklistP）

{//输出一元多项式p

Linklistq=P->next;

intflag=1;//项数计数器

if（!

q）

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

putchar（'0'）;

printf（"\n"）;

return;

}

while（q）

{

if（q->coef>0&&flag!

=1）putchar（'+'）;//系数大于0且不是第一项

if（q->coef!

=1&&q->coef!

=-1）

{//系数非1或-1的普通情况

printf（"%g",q->coef）;

if（q->expn==1）putchar（'X'）;

elseif（q->expn）printf（"X^%d",q->expn）;

}

else

{

if（q->coef==1）

{

if（!

q->expn）

putchar（'1'）;

elseif（q->expn==1）

putchar（'X'）;

else

printf（"X^%d",q->expn）;

}

if（q->coef==-1）

{

if（!

q->expn）

printf（"-1"）;

elseif（q->expn==1）

printf（"-X"）;

else

printf（"-X^%d",q->expn）;

}

}

q=q->next;

flag++;

}

printf（"\n"）;

}

intCompare（Linklista,Linklistb）

{//比较a,b中x的指数的大小

if（a&&b）

{

if（!

b||a->expn>b->expn）

return1;

elseif（!

a||a->expnexpn）

return-1;

else

return0;

}

elseif（!

a&&b）//a多项式已空，但b多项式非空

return-1;

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

return1;

}

LinklistAddLinklist（Linklistpa,Linklistpb）

{//求解并建立多项式a+b，返回其头指针

Linklistqa=pa->next;

Linklistqb=pb->next;

Linklistheadc,hc,qc;

hc=（Linklist）malloc（sizeof（structLinklistomial））;//建立头结点

hc->next=NULL;

headc=hc;

while（qa||qb）

{

qc=（Linklist）malloc（sizeof（structLinklistomial））;

switch（Compare（qa,qb））

{

case1:

{

qc->coef=qa->coef;

qc->expn=qa->expn;

qa=qa->next;

break;

}

case0:

{

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

qc->expn=qa->expn;

qa=qa->next;

qb=qb->next;

break;

}

case-1:

{

qc->coef=qb->coef;

qc->expn=qb->expn;

qb=qb->next;

break;

}

}

if（qc->coef!

=0）

{

qc->next=hc->next;

hc->next=qc;

hc=qc;

}

else

free（qc）;//当相加系数为0时，释放该结点

}

returnheadc;

}

LinklistSubtractionLinklist（LinklistSa,LinklistSb）

{//求解并建立多项式a-b，返回其头指针

LinklistCb=Sb->next;

while（Cb）

{

Cb->coef=（-1）*Cb->coef;

Cb=Cb->next;

}

returnAddLinklist（Sa,Sb）;

}

intmain（）

{

intm,n,a=1;

charflag;

Linklistpa=0,pb=0,pc;

printf（"欢迎使用一元多项式加法器\n\n"）;//输出菜单

printf（"*******************************************************\n"）;

printf（"*一元多项式简单运算器*\n"）;

printf（"**\n"）;

printf（"*A:

输入多项式aB:

输入多项式b*\n"）;

printf（"**\n"）;

printf（"*C:

输出多项式aD:

输出多项式b*\n"）;

printf（"**\n"）;

printf（"*E:

输出a+bF:

输出a-b*\n"）;

printf（"**\n"）;

printf（"*G:

使用完毕！

*\n"）;

printf（"*******************************************************\n"）;

while（a）

{

printf（"\n请选择操作：

"）;

scanf（"%c",&flag）;//空格符号一定要注意

switch（flag）

{

case'A':

case'a':

{

printf（"下面进行多项式a的输入：

\n"）;

printf（"请输入a的项数:

"）;

scanf（"%d",&m）;

pa=CreateLinklist（pa,m）;//建立多项式a

break;

}

case'B':

case'b':

{

printf（"下面进行多项式b的输入：

\n"）;

printf（"请输入b的项数:

"）;

scanf（"%d",&n）;

pb=CreateLinklist（pb,n）;//建立多项式b

break;

}

case'C':

case'c':

{

printf（"\n多项式a="）;

PrintLinklist（pa）;

break;

}

case'D':

case'd':

{

printf（"\n多项式b="）;

PrintLinklist（pb）;

break;

}

case'E':

case'e':

{

pc=AddLinklist（pa,pb）;

printf（"\na+b="）;

PrintLinklist（pc）;

break;

}

case'F':

case'f':

{

pc=SubtractionLinklist（pa,pb）;

printf（"\na-b="）;

PrintLinklist（pc）;

break;

}

case'G':

case'g':

{

DestroyLinklist（pa）;

DestroyLinklist（pb）;

a=0;

printf（"\n欢迎下次使用！

\n"）;

break;

}

default:

printf（"\n您的选择错误，请重新选择!

\n"）;

}

}

return0;

}

四、调试分析

编译环境为CodeBlocks。