数据结构C语言一元稀疏多项式计算器Word下载.docx
《数据结构C语言一元稀疏多项式计算器Word下载.docx》由会员分享，可在线阅读，更多相关《数据结构C语言一元稀疏多项式计算器Word下载.docx（17页珍藏版）》请在冰点文库上搜索。
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}
根本操作：
CreatLinkList（&
p,m）
操作结果：
输入m项的系数和指数，建立一元多项式p。
DestoryLinkList（&
p）
初始条件：
一元多项式p已存在。
销毁一元多项式p.
PrintLinkList（p）
打印输出一元多项式p.
AddLinkList〔&
pa,&
pb〕
一元多项式pa和pb已存在。
完成多项式的相加运算，即：
pa=pa+pb,并销毁一元多项式pb.
SubtractLinkList（&
pb）
完成多项式的想减运算，即：
pa=pa-pb,并销毁一元多项式pb.
}ADTLinkList
2.2本程序包括个模块：
1〕主程序模块：
Voidmain〔〕{
初始化；
输出菜单；
While〔1〕{
承受命令；
处理命令；
}〔循环一直为真直至承受退出命令〕；
2〕单链表单元模块——实现单链表的抽象数据类型；
3〕结点构造单元模块——定义单链表的结点构造。
三、详细设计
3.1元素类型、结点类型和指针类型
typedefintStatus;
typedefintElemType;
typedefstructLNode{
float
coef;
//系数
ElemType
expn;
//指数
struct
LNode*next;
}LNode,*LinkList;
StatusMakeNode（LinkList&
p,LinkListhead）
{//分配由p指向下一个多项式的头结点head、后继为空的结点，并返回TRUE，
//假设分配失败，那么返回FALSE
p=（LinkList）malloc（sizeof（structLNode））;
if（!
p）returnfalse;
p=head;
p->
next=null;
returnture;
voidFreeNode（LinkList&
{//释放p所指结点
free（q1）;
q1=q2;
q2=q2->
next;
}
3.2单链表的根本操作设置如下：
voidInsert（LinkListp,LinkListh）；
//将节点p插入到多项式链表h
LinkListCreateLinkList（LinkListhead,intm）;
//建立一个头指针为head、项数为m的一元多项式,并返回该多项式的头结点；
//假设分配空间失败，那么返回FALSE
voidDestroyLinkList（LinkListp）;
//销毁多项式p
voidPrintLinkList（LinkListP）;
//输出构造的一元多项式P
Statuspare（LinkLista,LinkListb）
//节点进展比拟:
a的指数>
b的指数
return1;
a的指数==b的指数
return0;
a的指数<
b的指数
return-1.
LinkListAddLinkList（LinkListpa,LinkListpb）
//求解并建立多项式a+b，返回其头指针
LinkListSubtractLinkList（LinkListpa,LinkListpb）
//求解并建立多项式a-b，返回其头指针
其中局部操作的伪码如下：
LinkListCreateLinkList（LinkListhead,intm）
{
p=head=（LinkList）malloc（sizeof（structLNode））;
head->
next=NULL;
for（i=0;
i<
m;
i++）
p=（LinkList）malloc（sizeof（structLNode））;
//建立新结点以接收数据
printf（"
请输入第%d项的系数与指数:
"
i+1）;
scanf（"
%f%d"
&
coef,&
expn）;
Insert（p,head）;
//调用Insert函数插入结点
returnhead;
}//CreateLinkList
Statuspare（LinkLista,LinkListb）{
if（a&
&
b）{
if（!
b||a->
b->
expn）return1;
elseif（!
a||a->
expn）return-1;
elsereturn0;
a&
b）return-1;
//a多项式已空，但b多项式非空
elsereturn1;
//b多项式已空，但a多项式非空
}//pare
floatValueLinkList（LinkListhead,intx）{
//输入x值，计算并返回多项式的值
for（p=head->
p;
p=p->
next）{
t=1;
for（i=p->
expn;
i!
=0;
）
//i为指数的系数pow（x,i）
{if（i<
0）{t/=x;
i++;
}
//指数小于0，进展除法
else{t*=x;
i--;
}//指数大于0，进展乘法
sum+=p->
coef*t;
}returnsum;
}//ValueLinkList
LinkListMultiplyLinkList（LinkListpa,LinkListpb）{//求解并建立多项式a*b，返回其头指针
LinkListqa=pa->
LinkListqb=pb->
hf=（LinkList）malloc（sizeof（structLNode））;
//建立头结点
hf->
for（;
qa;
qa=qa->
next）
{for（qb=pb->
qb;
qb=qb->
next）
{pf=（LinkList）malloc（sizeof（structLNode））;
pf->
coef=qa->
coef*qb->
coef;
expn=qa->
expn+qb->
Insert（pf,hf）;
}//调用Insert函数以合并指数一样的项
}returnhf;
}//MultiplyLinkList
3.3主函数和其他函数的伪码算法
voidmain（）{//主函数
Initiation（）;
//多项式初始化
Printmand（）;
//输出菜单
while
（1）{
//循环一直为真知道选择j||J即退出命令时，程序退出
\n请选择操作：
）;
%c"
flag）;
Interpter（flag）;
//具体的操作命令
}}
//main
voidInitiation（）
请输入a的项数:
%d"
m）;
pa=CreateLinkList（pa,m）;
//建立多项式a
请输入b的项数:
n）;
pb=CreateLinkList（pb,n）;
//建立多项式b
printf（"
多项式已创立\n"
}//Initiation
voidPrintmand（）{
//输出菜单
显示键入命令的提示信息；
Printf〔’A’,’B’,’C’,’D’,’E’〕;
}//Printmand
voidInterpter（charflag）{
switch（flag）
{case'
A'
:
case'
a'
{PrintLinkList（pa）;
break;
case'
B'
b'
{PrintLinkList（pb）;
case'
C'
case'
c'
{AddLinkList（pa,pb）;
PrintLinkList（pc）;
D'
d'
{SubtractLinkList（pa,pb））;
PrintLinkList（pc）;
E'
e'
{DestroyLinkList（pa）;
DestroyLinkList（pb）;
exit（0）;
default:
\n
您的选择错误，请重新选择!
\n"
}//Interpter
函数说明：
Printmand（）;
//输出菜单
Interpter（）;
PrintLinkList（）;
//打印多项式（降序输出）
AddLinkList（）;
//两个多项式相加
SubtractLinkList（）;
//两个多项式相减
DestroyLinkList（）;
//销毁多项式
pare（）;
//两个节点比拟
CreateLinkList（）;
//创立多项式
Insert（）;
//将节点插入多项式中
四、源程序
#include<
stdio.h>
malloc.h>
stdlib.h>
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
#defineOVERFLOW-2
floatcoef;
ElemTypeexpn;
structLNode*next;
/*全局节点初始化多项式节点为空*/
staticLinkListpa=NULL;
staticLinkListpb=NULL;
staticLinkListpc=NULL;
/*将节点p插入到多项式链表h*/
voidInsert（LinkListp,LinkListh）{
if（p->
coef==0）free（p）;
//系数为0的话释放结点
else{LinkListq1,q2;
q1=h;
q2=h->
while（q2&
q2->
expn）{//查找插入位置
}
if（q2&
expn==q2->
expn）{//将指数一样相合并
q2->
coef+=p->
free（p）;
coef）{//系数为0的话释放结点
q1->
next=q2->
free（q2）;
else{//指数为新时将结点插入
p->
next=q2;
next=p;
//创立一元多项式
LinkListCreateLinkList（LinkListhead,intm）{//建立一个头指针为head、项数为m的一元多项式
inti;
LinkListp;
{
voidDestroyLinkList（LinkListp）{
//销毁多项式p
LinkListq1,q2;
q1=p->
q2=q1->
while（q1->
{free（q1）;
voidPrintLinkList（LinkListP）{
LinkListq=P->
intflag=1;
//项数计数器
q）
{//假设多项式为空，输出0
putchar（'
0'
return;
}
while（q）
if（q->
coef>
0&
flag!
=1）putchar（'
+'
//系数大于0且不是第一项
coef!
=1&
=-1）
{//系数非1或-1的普通情况
%g"
q->
coef）;
expn==1）putchar（'
X'
elseif（q->
expn）printf（"
X^%d"
else
coef==1）
expn）putchar（'
1'
elseprintf（"
coef==-1）
-1"
expn==1）printf（"
-X"
-X^%d"
q=q->
flag++;
//节点进展比拟
//a的指数>
b的指数return1
//a的指数==b的指数return0
//a的指数<
b的指数return-1
b）
{if（!
LinkListAddLinkList（LinkListpa,LinkListpb）{//求解并建立多项式a+b，返回其头指针
LinkListheadc,hc,qc;
hc=（LinkList）malloc（sizeof（structLNode））;
hc->
headc=hc;
while（qa||qb）{
qc=（LinkList）malloc（sizeof（structLNode））;
switch（pare（qa,qb））{
case1:
qc->
qa=qa->
case0:
{
coef+qb->
qb=qb->
case-1:
coef=qb->
expn=qb->
if（qc->
=0）
{qc->
next=hc->
next=qc;
hc=qc;
elsefree（qc）;
//当相加系数为0时，释放该结点
returnheadc;
LinkListSubtractLinkList（LinkListpa,LinkListpb）{//求解并建立多项式a-b，返回其头指针
LinkListh=pb;
LinkListp=pb->
LinkListpd;
while（p）{//将pb的系数取反
coef*=-1;
p=p->
pd=AddLinkList（pa,h）;
for（p=h->
next）//恢复pb的系数
returnpd;
//多项式初始化
intm,n;
voidPrintmand（）
A:
输出多项式aB:
输出多项式b\n"
C:
输出a+bD:
输出a-b\n"
E:
退出程序\n"
voidInterpter（charflag）
intx;
switch（flag）
{printf（"
\n多项式a="
PrintLinkList（pa）;
{printf（"
\n多项式b="
PrintLinkList（pb）;
{pc=AddLinkList（pa,pb）;
\na+b="
{pc=SubtractLinkList（pa,pb）;
\na-b="
\n感使用此程序！
DestroyLinkList（pa）;
exit（0）;
}//强制程序退出
default:
\n您的选择错误，请重新选择!
}
voidmain（）
charflag;
Initiation（）;
while
（1）{//循环一直为真知道选择j||J即退出命令时，程序退出
//空格符号一定要注意
}
五、运行结果
升级会员 