数据结构课程设计报告一元多项式的计算Word格式.docx
《数据结构课程设计报告一元多项式的计算Word格式.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计报告一元多项式的计算Word格式.docx(18页珍藏版)》请在冰点文库上搜索。
基本操作:
InitList(&L)
//操作结果:
构造一个空的线性表
CreatPolyn(&
L)
//操作结果:
构造一个以单连表存储的多项试
DispPolyn(L)
显示多项试
Polyn(&
pa,&
pb)
显示两个多项试相加,相减的结果
}ADTList
2.本程序包含模块:
typedefstructLNode//定义单链表
{
}LNode,*LinkList;
voidInitList(LinkList&
L)//定义一个空表
{}
voidCreatPolyn(LinkList&
L)//用单链表定义一个多项式
voidDispPolyn(LinkListL)//显示输入的多项式
voidPolyn(LinkList&
pa,LinkList&
{}
voidmain()
{
//定义一个单连表;
cout<
<
endl<
"
*****************欢迎来到一元多项式计算程序
***************"
endl;
LNode*L1,*L2;
Polyn(L1,L2);
}
2.1加,减操作模块——实现加减操作
各模块之间的调用关系如下:
主程序模块
加法操作模块减法操作模块
基本算法:
1、输入输出
(1)功能:
将要进行运算的多项式输入输出。
(2)数据流入:
要输入的多项式的系数与指数。
(3)数据流出:
合并同类项后的多项式。
(4)程序流程图:
多项式输入流程图如图1所示。
(5)测试要点:
输入的多项式是否正确,若输入错误则重新输入
图表1
2、多项式的加法
将两多项式相加。
输入函数。
多项式相加后的结果。
多项式的加法流程图如图2所示。
两多项式是否为空,为空则提示重新输入,否则,进行运算。
图表2
3、多项式的减法
将两多项式相减。
调用输入函数。
多项式相减后的结果。
多项式的减法流程图如图3所示。
四.详细设计
1.根据题目要求采用单连表存储结构
typedefstructLNode//定义单链表
{
voidInitList(LinkList&
voidDispPolyn(LinkListL)//显示输入的多项式
{}
voidPolyn(LinkList&
2.主函数main
voidmain()
Polyn(L1,L2);
}
2.函数的调用关系层次结构
多项式Polyn用单链表定义多项式CreatPolyn定义一个空表InitList显示输入的多项式DispPolyn
}
五.调试分析
采用单连表形式按照指数降序排列建立并输出多项式;
在相加,相减的过程中如果指数相同就执行系数相加,相减,否则就把大的项直接写入。
完成两个多项式的相加、相减;
将从新得到的单连表结果输出;
该算法的时间复杂度为两个多项式的项式之和
六:
调试结果
1.测试的数据及结果
2.算法的时间复杂度及改进
算法的时间复杂度:
一元多项式的加法运算的时间复杂度为O(m+n),减法运算的时间复杂度为O(m-n),其中m,n分别表示二个一元多项式的项数。
问题和改进思想:
在设计该算法时,出现了一些问题,例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针出现了数据重复输出或是输出系统缺省值,不能实现算法。
实现加法时该链表并没有向通常那样通过建立第三个链表来存放运算结果,而是再度利用了链表之一来进行节点的比较插入删除等操作。
为了使输入数据按指数降序排列,可在数据的输入后先做一个节点的排序函数,通过对链表排序后再进行之后加减运算。
七.心得体会:
一元多项式计算是一个的单链表的运用,通过这个程序可以测我们以前的学习情况,看看我们是否对单链表真正的理解。
一元多项式计算器的基本功能定为:
(1)建立多项式
(2)输出多项式
(3)两个多项式相加,建立并输出和多项式
(4)两个多项式相减,建立并输出差多项式能够按照指数降序排列建立并输出多项式;
能够完成两个多项式的相加、相减,并将结果输出;
结束语:
时间过的很快,在不知不觉中,课程设计也接近了尾声.说起课程设计,我认为最重要的就是做好设计的预习,并且认真的去复习以前的知识和查各种资料同时认真的研究老师给的题目,老师对题目的讲解要一丝不苟的去听去想,因为只有都明白了,做起设计来才会有底,有信心。
课程设计是一门培养学生综合运用所学知识,发现,提出,分析和解决实际问题的学科,它能充分锻炼我们的动手能力,时我们实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程。
我想这次不只是一次简单的课程设计,更体现了数据结构算法和生活的紧密联系。
生活中也存在许多与数据结构有关联的事情,它让人不得不深思,这一个学期的学习,这两年来的大学学习生涯,自己究竟学会了什么,掌握了多少,我也不清楚,我以前也疯狂的玩过,现在才知道自己时多么的缺乏知识,大多数问题自己不能解决,感觉将来自己是否能胜任以后作编译人员的职位。
我想大家都心里都有很多的感触。
对于自己,我想我已经认识到了自己的不足,在今后的学习过程中,我一定以最好的心态去对待,以最好的面貌来迎接大三的软件专业课程,并且经常上机调试,坚持理论与实践相结合。
相信自己将会有很大的进步。
附录详细设计
#include<
stdio.h>
malloc.h>
typedefstructPolynomial{
floatcoef;
intexpn;
structPolynomial*next;
}*Polyn,Polynomial;
//Polyn为结点指针类型
voidInsert(Polynp,Polynh){
if(p->
coef==0)free(p);
//系数为0的话释放结点
else{
Polynq1,q2;
q1=h;
q2=h->
next;
while(q2&
&
p->
expn<
q2->
expn){//查找插入位置
q1=q2;
q2=q2->
}
if(q2&
expn==q2->
expn){//将指数相同相合并
q2->
coef+=p->
coef;
free(p);
if(!
coef){//系数为0的话释放结点
q1->
next=q2->
free(q2);
else{//指数为新时将结点插入
p->
next=q2;
next=p;
}//Insert
PolynCreatePolyn(Polynhead,intm){//建立一个头指针为head、项数为m的一元多项式
inti;
Polynp;
p=head=(Polyn)malloc(sizeof(structPolynomial));
head->
next=NULL;
for(i=0;
i<
m;
i++){
p=(Polyn)malloc(sizeof(structPolynomial));
//建立新结点以接收数据
printf("
请输入第%d项的系数与指数:
i+1);
scanf("
%f%d"
&
coef,&
expn);
Insert(p,head);
//调用Insert函数插入结点
returnhead;
}//CreatePolyn
voidDestroyPolyn(Polynp){//销毁多项式p
q1=p->
q2=q1->
while(q1->
next){
free(q1);
//指针后移
voidPrintPolyn(PolynP){
Polynq=P->
intflag=1;
//项数计数器
q){//若多项式为空,输出0
putchar('
0'
);
\n"
return;
while(q){
if(q->
coef>
0&
flag!
=1)putchar('
+'
//系数大于0且不是第一项
coef!
=1&
q->
=-1){//系数非1或-1的普通情况
%g"
q->
coef);
expn==1)putchar('
X'
elseif(q->
expn)printf("
X^%d"
coef==1){
expn)putchar('
1'
elseprintf("
coef==-1){
-1"
expn==1)printf("
-X"
-X^%d"
q=q->
flag++;
}//while
}//PrintPolyn
intcompare(Polyna,Polynb){
if(a&
b){
b||a->
expn>
b->
expn)return1;
elseif(!
a||a->
expn)return-1;
elsereturn0;
a&
b)return-1;
//a多项式已空,但b多项式非空
elsereturn1;
//b多项式已空,但a多项式非空
}//compare
PolynAddPolyn(Polynpa,Polynpb){//求解并建立多项式a+b,返回其头指针
Polynqa=pa->
Polynqb=pb->
Polynheadc,hc,qc;
hc=(Polyn)malloc(sizeof(structPolynomial));
//建立头结点
hc->
headc=hc;
while(qa||qb){
qc=(Polyn)malloc(sizeof(structPolynomial));
switch(compare(qa,qb)){
case1:
qc->
coef=qa->
expn=qa->
expn;
qa=qa->
break;
case0:
{
coef+qb->
qb=qb->
case-1:
coef=qb->
expn=qb->
}//switch
if(qc->
=0){
next=hc->
next=qc;
hc=qc;
elsefree(qc);
//当相加系数为0时,释放该结点
returnheadc;
}//AddPolyn
PolynSubtractPolyn(Polynpa,Polynpb){//求解并建立多项式a+b,返回其头指针
Polynh=pb;
Polynp=pb->
Polynpd;
while(p){//将pb的系数取反
coef*=-1;
p=p->
pd=AddPolyn(pa,h);
for(p=h->
p;
p=p->
next)//恢复pb的系数
returnpd;
}//SubtractPolyn
intmain(){
intm,n,flag=0;
floatx;
Polynpa=0,pb=0,pc,pd,pe,pf;
//定义各式的头指针,pa与pb在使用前付初值NULL
请输入a的项数:
%d"
m);
pa=CreatePolyn(pa,m);
//建立多项式a
请输入b的项数:
n);
pb=CreatePolyn(pb,n);
//输出菜单
**********************************************\n"
操作提示:
\n\t1.输出多项式a和b\n\t2.建立多项式a+b\n\t3.建立多项式a-b\n"
\t4.退出\n**********************************************\n"
for(;
;
flag=0){
执行操作:
flag);
if(flag==1){
多项式a:
PrintPolyn(pa);
多项式b:
PrintPolyn(pb);
continue;
if(flag==2){
pc=AddPolyn(pa,pb);
多项式a+b:
PrintPolyn(pc);
DestroyPolyn(pc);
if(flag==3){
pd=SubtractPolyn(pa,pb);
多项式a-b:
PrintPolyn(pd);
DestroyPolyn(pd);
if(flag==4)break;
if(flag<
1||flag>
4)printf("
Error\n"
}//for
DestroyPolyn(pa);
DestroyPolyn(pb);
return0;