数据结构实验2多.docx
- 文档编号:16277766
- 上传时间:2023-07-12
- 格式:DOCX
- 页数:9
- 大小:94.02KB
数据结构实验2多.docx
《数据结构实验2多.docx》由会员分享,可在线阅读,更多相关《数据结构实验2多.docx(9页珍藏版)》请在冰点文库上搜索。
数据结构实验2多
数据结构-实验2-多项式求和
1、实验目的
(1)掌握线性表的顺序存储结构和链式存储结构;
(2)掌握线性表插入、删除等基本运算;
(3)掌握线性表的典型运用——多项式求和。
2、实验内容
编程实现多项式的求和运算:
(1)顺序存储结构的实现
例如,已知:
f(x)=8x^6+5x^5-10x^4+32x^2-x+10,g(x)=7x^5+10x^4-20x^3-10x^2+x,
求和结果:
f(x)+g(x)=8x^6+12x^5-20x^3+22x^2+10。
顺序表的定义类型如下:
#defineMAXLEN100
typedefstruct
{intdata[MAXLEN];
Intlast;
}SeqList;
(2)链式存储结构的实现
例如,已知:
f(x)=100x^100+5x^50-30x^10+10,g(x)=150x^90-5x^50+40x^20-20x^10+3x,
求和结果:
f(x)+g(x)=100x^100+150x^90+40x^20-10x^10+3x+10。
3、实验要求
(1)利用C(C++)语言完成程序设计。
(2)上机调试通过实验程序。
(3)输入数据,检验程序运行结果。
(4)给出具体的算法分析,包括时间复杂度和空间复杂度等。
(5)撰写实验报告(把输入实验数据及运行结果用抓图的形式粘贴到实验报告上)。
4、实验步骤与源程序
实验步骤
我先从具体的问题中抽象出适当的数学模型,然后设计出相应的算法,对于用顺序存储结构实现多项式求和而言,需要设计3个main函数调用的子函数,分别实现创建多项式,多项式相加和显示多项式;对于用链式存储结构实现多项式求和,也同样需要3个这样的子函数,最后,编写程序,并调试程序,得出实验结果。
源代码
顺序存储结构:
#include
#defineMAXLEN100
typedefstruct
{intdata[MAXLEN];
intlast;
}SeqList;
voidadd_List(SeqListA,SeqListB,SeqList*C)
{inti;
C->last=A.last>B.last?
A.last:
B.last;
for(i=0;i<=C->last;i++)
C->data[i]=A.data[i]+B.data[i];
}
voidshow_list(SeqListC)
{inti;
for(i=C.last;i>=1;i--)
if(C.data[i])
printf("\(%dx^%d\)+",C.data[i],i);
printf("\(%dx^%d\)\n",C.data[0],0);
}
voidcreate_list(SeqList*D)
{intn,i;
printf("\t\t请输入多项式X的最高次数:
");
scanf("%d",&n);
for(intk=99;k>=0;k--)
D->data[k]=0;
printf("\t\t请输入多项式X的次数由大到小输入系数,缺少项用0补齐\n");
for(i=n;i>=0;i--)
{printf("\t\t输入X^%d项的系数:
",i);
scanf("%d",&D->data[i]);
}
D->last=n;
}
voidmain()
{SeqListA,B,C;
printf("\t\t创建多项式f(x):
\n");
create_list(&A);
printf("\t\tf(x)=");
show_list(A);
printf("\t\t创建多项式g(x):
\n");
create_list(&B);
printf("\t\tg(x)=");
show_list(B);
printf("\t\t多项式f(x)和g(x)的和:
");
add_List(A,B,&C);
printf("\n\t\tf(x)+g(x)=");
show_list(C);
}
链式存储结构:
#include
#include
#include
typedefstructlinknode
{
floatcoef;
intexpn;
structlinknode*next;
}Node;
voidcreate_link_list(Node*L)
{Node*p,*q;
intn=1;
floatx=1;
q=L;
printf("\n请按多项式指数由大到小输入系数和指数:
\n");
printf("提示:
系数和指数间用空格间隔,每组数据之间用回车间隔(系数和指数为0时结束输入)\n");
while(fabs(x)>0.000001)
{scanf("%f%d",&x,&n);
if(fabs(x)>0.00001)
{p=(Node*)malloc(sizeof(Node));
p->coef=x;
p->expn=n;
p->next=NULL;
q->next=p;
q=p;
}
}
}
voidshow_link_list(Node*L)
{
Node*p;
p=L->next;
while(p&&p->next)
{printf("\(%.1fx^%d\)+",p->coef,p->expn);
p=p->next;
}
printf("\(%.1fx^%d\)",p->coef,p->expn);
printf("\n");
}
voidmergelist(Node*La,Node*Lb,Node*Lc)//多项式合并
{Node*pa,*pb,*pc;
Node*q1,*q2;
Lc=La;
pc=Lc;
pa=La->next;
pb=Lb->next;
while(pa&&pb)
if(pa->expn>pb->expn)
{pc->next=pa;pc=pa;pa=pa->next;}
elseif(pa->expn
{pc->next=pb;pc=pb;pb=pb->next;}
elseif(fabs(pa->coef+pb->coef)<0.000001)
{q1=pa;
q2=pb;
pa=pa->next;
pb=pb->next;
free(q1);
free(q2);
}
else{q1=pb;pa->coef=pa->coef+pb->coef;
pc->next=pa;
pc=pa;
pa=pa->next;
pb=pb->next;
free(q1);
}
if(pa)
pc->next=pa;
else
pc->next=pb;
}
voidmain()
{
Node*LA,*LB,*LC;
LA=(Node*)malloc(sizeof(Node));
LA->next=NULL;
LB=(Node*)malloc(sizeof(Node));
LB->next=NULL;
LC=LA;
create_link_list(LA);
printf("f(x)=");
show_link_list(LA);
create_link_list(LB);
printf("g(x)=");
show_link_list(LB);
mergelist(LA,LB,LC);
printf("\nf(x)+g(x)=");
show_link_list(LC);
}
5、测试数据与实验结果(可以抓图粘贴)
顺序存储结构的实现调试结果如图所示:
链式存储结构的实现调试结果如图所示:
6、结果分析与实验体会
本次实验是参考了范例程序,经过自己的改写,从而实现要求。
先做简单的输出,一步步的再做其它格式的设置。
而且,在具体操作中我对顺序存储结构和链式存储结构的优点和缺点有了更深刻的体会,顺序存储结构的算法较为简单,但是在输入的过程中有很大的局限性,必须从大到小依次且连续的输入多项式次数,所以,它只适合最高次数较小的多项式求和,而链式存储结构设计的算法则更灵活,输入时,不需要次数在数值上连续,所以,它更具有普遍性、实用性。
再从算法效率的角度来评价,顺序存储结构在做次数大小跨度大的多项式求和时,会浪费很多的存储空间,而链式存储结构则可以充分利用,不会浪费,即其空间复杂度较小。
最后,我想说,通过调试程序,我不光学会编程了的基本步骤、基本算法,也使自己更有耐心去做好每一件事情。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验
![提示](https://static.bingdoc.com/images/bang_tan.gif)