数据结构报告一元多项式.docx
《数据结构报告一元多项式.docx》由会员分享，可在线阅读，更多相关《数据结构报告一元多项式.docx（20页珍藏版）》请在冰点文库上搜索。
数据结构报告一元多项式
数据结构
课程设计报告
主题：
实现一元多项式抽象数据类型
学号：
20091003768
班级：
计科四班
姓名：
熊金莲
指导老师：
郭艳
内容概要
（1）题目要求
（2）实现该一元多项式抽象数据类型的要点
（3）函数模块及各函数可实现的功能简介
（4）具体的源代码
（5）使用说明
（6）实验心得
一：
题目要求如下：
1．构造一个空的多项式
2．多项式插入新的一项
3．多项式合并同类项
4．多项式加法
5．多项式乘法
6．打印多项式
7．计算多项式的值
二：
构思要点
以链表形式创建两个多项式a与b，a与b的加法与乘法用到链式结构的操作。
因为系数coef设置为浮点类型，指数expn设置为整形，所以构思是输入多项式的系数和指数时，以00为输入结束标志，并设置这一判断语句。
在插入函数中，寻找多项式适当的插入位置，可以实现多项式的升序排列，同时也在该插入函数中实现多项式合并同类项的功能。
为实现多项式相加相乘定义了相加函数及相乘函数，实现a与b的相加相乘时直接调用。
还有就是定义输出函数，打印各多项式。
再者计算多项式的值时，先输入x的值，带入多项式计算即可。
在主函数中使用switch语句，在此为了让本一元多项式功能步步展示，省去了各个case后的break语句。
三：
各函数模块
1）/*第一,二部分构造一个空的多项式并用链表插入法创建多项式*/
voidInsertlinklist（linklistp,linklistq）/*第一部分链表插入*/
{
if（p->coef==0）free（p）;//系数为0则该项为空释放结点空间
else
{
linklistq1,q2;
q1=q;q2=q->next;
while（q2&&p->expn>q2->expn）{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）;}//系数为0则该项为空释放结点空间
}
else{p->next=q2;q1->next=p;}//指数异于其他项指数时将结点插入
}
}
linklistCreatelinklist（linklisthead）/*第二部分创建链表*/
{
linklistp;intn;floatm;
p=head=（linklist）malloc（sizeof（structlnode））;
p->next=NULL;
scanf（"%f%d",&m,&n）;
while（m!
=0||n!
=0）//当输入为00时结束输入
{
p=（linklist）malloc（sizeof（structlnode））;
p->coef=m;p->expn=n;
Insertlinklist（p,head）;/*调用第一部分函数*/
scanf（"%f%d",&m,&n）;
}
returnhead;
}
2）/*第二部分销毁链表*/
voidDestroylinklist（linklistp）
{
linklistq1=p->next,q2=q1->next;
while（q2）{free（q1）;q1=q2;q2=q2->next;}
}
3）/*第三部分打印链表*/
voidPrintlinklist（linklistp）
{
linklistq=p->next;intc=1;
if（!
q）{putchar（'0'）;printf（"\n"）;return;}
while（q）
{
if（q->coef>0&&c!
=1）putchar（'+'）;
if（q->coef!
=1&&q->coef!
=-1）
{
printf（"%f",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'）;
elseprintf（"x^%d",q->expn）;
}
elseif（q->coef==-1）
{
if（!
q->expn）putchar（'-1'）;
elseif（q->expn==1）printf（"-x"）;
elseprintf（"-x^%d",q->expn）;
}
}
q=q->next;
c++;//项数自加1
}
printf（"\n"）;
}
4）/*第四部分多项式非空判断*/
intComparelinklist（linklista,linklistb）
{
if（a&&b）
{
if（a->expn>b->expn||!
b）return-1;
elseif（!
a||a->expnexpn）return1;
elsereturn0;
}
elseif（!
a&&b）return-1;//多项式a为空b不为空
elsereturn1;//多项式不a为空b为空
}
5）/*第五部分多项式相加*/
linklistAddlinklist（linklistpa,linklistpb）
{
linklisthead,x,y,qa=pa->next,qb=pb->next;
x=（linklist）malloc（sizeof（structlnode））;
x->next=NULL;
head=x;
while（qa||qb）
{
y=（linklist）malloc（sizeof（structlnode））;
switch（Comparelinklist（qa,qb））
{
case-1:
{
y->coef=qb->coef;
y->expn=qb->expn;
qb=qb->next;
break;
}
case0:
{
y->coef=qa->coef+qb->coef;
y->expn=qa->expn;
qa=qa->next;
qb=qb->next;
break;
}
case1:
{
y->coef=qa->coef;
y->expn=qa->expn;
qa=qa->next;
break;
}
}
if（y->coef!
=0）
{
y->next=x->next;
x->next=y;
x=y;
}
elsefree（y）;
}
returnhead;
}
6）/*第六部分多项式相乘*/
linklistMultiplylinklist（linklistpa,linklistpb）
{
linklistqa=pa->next,qb=pb->next,w,v;
w=（linklist）malloc（sizeof（structlnode））;
w->next=NULL;
for（;qa;qa=qa->next）
{
for（qb=pb->next;qb;qb=qb->next）
{
v=（linklist）malloc（sizeof（structlnode））;
v->coef=qa->coef*qb->coef;
v->expn=qa->expn+qb->expn;
Insertlinklist（v,w）;//调用Insertlinklist函数合并指数相同的项
}
}
returnw;
}
7）/*第七部分多项式赋值*/
intValuelinklist（linklisthead,intx）
{
intsum=0,i,j;linklistp;
for（p=head->next;p;p=p->next）
{
j=1;
for（i=p->expn;i!
=0;）
{if（i<0）{j/=x;i++;}
else{j*=x;i--;}
}
sum+=int（p->coef）*j;
}
returnsum;
}
8）/*将多项式每一项都定义为结构体类型分别有系数指数和指向下一个结构体的指针*/
typedefstructlnode
{
floatcoef;
intexpn;
structlnode*next;
}lnode,*linklist;
四：
具体的源代码
工程分多项式Linklist.h及多项式.cpp两部分
/*多项式LinkList*/
voidInsertlinklist（linklistp,linklistq）/*第一部分链表插入*/
{
if（p->coef==0）free（p）;//系数为0则该项为空释放结点空间
else
{
linklistq1,q2;
q1=q;q2=q->next;
while（q2&&p->expn>q2->expn）{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）;}//系数为0则该项为空释放结点空间
}
else{p->next=q2;q1->next=p;}//指数异于其他项指数时将结点插入
}
}
linklistCreatelinklist（linklisthead）/*第二部分创建链表*/
{
linklistp;intn;floatm;
p=head=（linklist）malloc（sizeof（structlnode））;
p->next=NULL;
scanf（"%f%d",&m,&n）;
while（m!
=0||n!
=0）//当输入为00时结束输入
{
p=（linklist）malloc（sizeof（structlnode））;
p->coef=m;p->expn=n;
Insertlinklist（p,head）;/*调用第一部分函数*/
scanf（"%f%d",&m,&n）;
}
returnhead;
}
voidDestroylinklist（linklistp）/*第三部分销毁链表*/
{
linklistq1=p->next,q2=q1->next;
while（q2）{free（q1）;q1=q2;q2=q2->next;}
}
voidPrintlinklist（linklistp）/*第四部分打印链表*/
{
linklistq=p->next;intc=1;
if（!
q）{putchar（'0'）;printf（"\n"）;return;}
while（q）
{
if（q->coef>0&&c!
=1）putchar（'+'）;
if（q->coef!
=1&&q->coef!
=-1）
{
printf（"%f",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'）;
elseprintf（"x^%d",q->expn）;
}
elseif（q->coef==-1）
{
if（!
q->expn）putchar（'-1'）;
elseif（q->expn==1）printf（"-x"）;
elseprintf（"-x^%d",q->expn）;
}
}
q=q->next;
c++;//项数自加1
}
printf（"\n"）;
}
intComparelinklist（linklista,linklistb）/*第五部分链表非空判断*/
{
if（a&&b）
{
if（a->expn>b->expn||!
b）return-1;
elseif（!
a||a->expnexpn）return1;
elsereturn0;
}
elseif（!
a&&b）return-1;//多项式a为空b不为空
elsereturn1;//多项式不a为空b为空
}
linklistAddlinklist（linklistpa,linklistpb）/*第六部分多项式相加*/
{
linklisthead,x,y,qa=pa->next,qb=pb->next;
x=（linklist）malloc（sizeof（structlnode））;
x->next=NULL;
head=x;
while（qa||qb）
{
y=（linklist）malloc（sizeof（structlnode））;
switch（Comparelinklist（qa,qb））
{
case-1:
{
y->coef=qb->coef;
y->expn=qb->expn;
qb=qb->next;
break;
}
case0:
{
y->coef=qa->coef+qb->coef;
y->expn=qa->expn;
qa=qa->next;
qb=qb->next;
break;
}
case1:
{
y->coef=qa->coef;
y->expn=qa->expn;
qa=qa->next;
break;
}
}
if（y->coef!
=0）
{
y->next=x->next;
x->next=y;
x=y;
}
elsefree（y）;
}
returnhead;
}
linklistMultiplylinklist（linklistpa,linklistpb）/*第七部分多项式相乘*/
{
linklistqa=pa->next,qb=pb->next,w,v;
w=（linklist）malloc（sizeof（structlnode））;
w->next=NULL;
for（;qa;qa=qa->next）
{
for（qb=pb->next;qb;qb=qb->next）
{
v=（linklist）malloc（sizeof（structlnode））;
v->coef=qa->coef*qb->coef;
v->expn=qa->expn+qb->expn;
Insertlinklist（v,w）;//调用Insertlinklist函数合并指数相同的项
}
}
returnw;
}
intValuelinklist（linklisthead,intx）/*第八部分多项式带值函数*/
{
intsum=0,i,j;linklistp;
for（p=head->next;p;p=p->next）
{
j=1;
for（i=p->expn;i!
=0;）
{if（i<0）{j/=x;i++;}
else{j*=x;i--;}
}
sum+=int（p->coef）*j;
}
returnsum;
}
#include
#include
#include
typedefstructlnode
{
floatcoef;
intexpn;
structlnode*next;
}lnode,*linklist;//将多项式每一项都定义为结构体类型分别有系数指数和指向下一个结构体的指针
typedeflinklistploynominal;
#include"多项式LinkList.h"
voidmain（）
{
inta=1,x;
charc;
linklistpa=0,pb=0,pc;
printf（"功能如下：
\n"）;
printf（"1:
输入多项式a:
\n"）;//该一元多项式所能实现的所有的功能
printf（"2:
输入多项式b:
\n"）;
printf（"3:
输出多项式a:
\n"）;
printf（"4:
输出多项式b:
\n"）;
printf（"5:
代入x的值计算a:
\n"）;
printf（"6:
代入x的值计算b:
\n"）;
printf（"7:
输出a+b:
\n"）;
printf（"8:
输出a*b:
\n"）;
printf（"9:
退出程序\n"）;
printf（"从操作1开始执行,请输入1:
"）;
while（a）
{
scanf（"%c",&c）;
switch（c）//本swith语句中并未写break语句目的是让程序从功能1到9依次执行下去
{
case'1':
{
printf（"请以00为结束标志输入多项式a各项系数与指数:
"）;
pa=Createlinklist（pa）;/*调用第二部分函数创建链表pa*/
}
case'2':
{
printf（"请以00为结束标志输入多项式b各项系数与指数:
"）;
pb=Createlinklist（pb）;/*调用第二部分函数创建链表pb*/
}
case'3':
{
printf（"多项式a为：
"）;
Printlinklist（pa）;/*调用第四部分函数打印多项式a*/
}
case'4':
{
printf（"多项式b为：
"）;
Printlinklist（pb）;/*调用第四部分函数打印多项式b*/
}
case'5':
{
printf（"请输入x给多项式a赋值：
"）;
scanf（"%d",&x）;
printf（"x=%d时，a=%d\n",x,Valuelinklist（pa,x））;/*调用第八部分函数求多项式a的值*/
}
case'6':
{
printf（"请输入x给多项式b赋值：
"）;
scanf（"%d",&x）;
printf（"x=%d时，b=%d\n",x,Valuelinklist（pb,x））;/*调用第八部分函数求多项式b的值*/
}
case'7':
{
pc=Addlinklist（pa,pb）;/*调用第六部分函数实现多项式相加*/
printf（"a+b="）;
Printlinklist（pc）;/*调用第四部分函数打印a+b和的多项式*/
printf（"请输入x给a+b和的多项式赋值：
"）;
scanf（"%d",&x）;
printf（"x=%d时，a+b=%d\n",x,Valuelinklist（pc,x））;/*调用第八部分函数求多项式a-b的值*/
}
case'8':
{
pc=Multiplylinklist（pa,pb）;/*调用第七部分函数实现多项式相乘*/
printf（"a*b="）;
Printlinklist（pc）;/*调用第四部分函数打印a*b积的多项式*/
printf（"请输入x给a*b和的多项式赋值：
"）;
scanf（"%d",&x）;
printf（"x=%d时，a*b=%d\n",x,Valuelinklist（pc,x））;/*调用第八部分函数求多项式a*b的值*/
}
case'9':
{
printf（"程序结束!
!
!
"）;/*调用第三部分函数销毁链表*/
Destroylinklist（pa）;
Destroylinklist（pb）;
a=0;
}
default:
printf（"\n此选择无效，请重新选择"）;
}
}
}
五：
使用说明
新建工程，将两个部分分别插入适当位置，sourcefiles里插入cpp文件，headerfiles里插入.h文件。
运行操作按输出提示输入即可。
输出如下
六：
实验心得
构造一个空的多项式，运用尾插法，将新申请的结点接到最后，用while语句实现输入00时停止输入。
多项式相乘时将多项式系数coef相乘，将指数expn相加，并调用InsertLinklist实现多项式的合并。
本次课程设计我掌握了建立链表和删除链表的方法，懂得了用链表方式实现多项式加法与乘法的方法。
同时深切感受到耐心与毅力是调试程序时的必备素质。
升级会员 