数据结构作业 线性表栈和队列及其应用.docx
- 文档编号:10899519
- 上传时间:2023-05-28
- 格式:DOCX
- 页数:20
- 大小:129.85KB
数据结构作业 线性表栈和队列及其应用.docx
《数据结构作业 线性表栈和队列及其应用.docx》由会员分享,可在线阅读,更多相关《数据结构作业 线性表栈和队列及其应用.docx(20页珍藏版)》请在冰点文库上搜索。
数据结构作业线性表栈和队列及其应用
数据结构
学院:
姓名:
班级:
学号:
实习一线性表、栈和队列及其应用
题目:
一元稀疏多项式的加法运算实习时间:
2012.3.25
一.需求分析
1.设计要求:
设计一个实现一元稀疏多项式相加运算的演示程序。
基本要求:
(1)输入并建立两个多项式;
(2)多项式a与b相加,建立和多项式c;
(3)输出多项式a,b,c。
输出格式:
比如多项式a为:
A(x)=c1xe1+c2xe2+…+cmxem,其中,ci和ei分别为第i项的系数和指数,且各项按指数的升幂排列,即0≤e1<e2<…<em。
多项式b,c类似输出。
2.测试数据:
(1)(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5)
(2)(x+x100)+(x100+x200)=(x+2x100+x200)
(3)(2x+5x8-3x11)+(7-5x8+11x9)=(7+2x+11x9-3x11)
二.设计
1.设计思想
(1)存储结构
1).用带头结点的单链表存储多项式。
2).三个多项式链表中都只存储非零系数项。
若多项式a与b中指数相等的两项相加后,系数为零,则在和多项式c中不存储该指数项。
(2)主要算法基本思想
输入项数j,建立循环,建立空结点存入多项式系数和指数后再插入链表中。
在插入时要把多项式中的各项进行比较,并按升幂排列,建立多项式存储列表。
在多项式加法运算过程中,将多项式a先存入多项式c中,c中多项式仍按升幂排列,再将b中系数与指数存入,存入的方法是:
指数比较寻找插入结点,指数相等时,进行系数相加;指数不等时,建立一个空结点,存入b的系数与指数载插入c中合适位置。
输出时按c链表的顺序输出就行了。
2.设计表示
(1)函数调用关系图
main→add
(2)函数接口规格说明
typedefstructNode
{floatm;//系数
intn;//指数
structNode*next;
}LinkList;
voidListInsert(LinkList*head,countL)//链表插入
voidAdd(LinkList*a,LinkList*b,LinkList*c)//加法
3.实现注释(即各项功能的实现程度)
1)建立单链表存储多项式。
2)通过j的值确定链表长度,输入各项的系数和指数可以存储在单链表的相应结点。
3)输入a和b后可以调用add函数,实现a+b=c,并输出a,b,c的值
4.详细设计
(1)链表插入
voidListInsert(LinkList*head,countL)
{
LinkList*p,*q;
p=head;
while(p->next!
=NULL)
{
if(p->next->n>L.n)
break;
p=p->next;
}
if((q=(LinkList*)malloc(sizeof(LinkList)))==NULL)
exit(0);
q->m=L.m;
q->n=L.n;
q->next=p->next;
p->next=q;
}
intprint(LinkList*head)
{
LinkList*p;
p=head->next;
if(p==NULL)//多项式为零直接输出
{
printf("0\n");
exit(0);
}
while(p->m==1&&p->n>0)//指数不为零时系数为1时的输出
{
printf("x^%d",p->n);
p=p->next;
if(p==NULL)
return0;
elseprintf("+");
}
while(p->next)
{
printf("%gx^%d",p->m,p->n);
p=p->next;
if(p->m>0)
printf("+");
}
printf("%gx^%d",p->m,p->n);
return1;
}
voidAdd(LinkList*a,LinkList*b,LinkList*c)//多项式加法
{
LinkList*p,*q,*s,*k;
s=c;
p=a->next;
while(p!
=NULL)
{
if((q=(LinkList*)malloc(sizeof(LinkList)))==NULL)
exit(0);
q->m=p->m;
q->n=p->n;
q->next=NULL;
c->next=q;
c=c->next;
p=p->next;
}
c=s;
p=b->next;
while(p!
=NULL)
{
while((c->next!
=NULL)&&(p->n)>((c->next)->n))
{
c=c->next;
}
if(c->next==NULL)
{
if((q=(LinkList*)malloc(sizeof(LinkList)))==NULL)
exit(0);
q->m=p->m;
q->n=p->n;
q->next=c->next;
c->next=q;
}
elseif(p->n==c->next->n)//系数相加
{
s=c;
c=c->next;
c->m=c->m+p->m;
if(c->m==0)
{
k=c;
c=s;
c->next=c->next->next;
free(k);
}
}
elseif(p->n>c->n&&c->next!
=NULL)
{
if((q=(LinkList*)malloc(sizeof(LinkList)))==NULL)
exit(0);
q->m=p->m;
q->n=p->n;
q->next=c->next;
c->next=q;
}
p=p->next;
}
}
(2)多项式相加实现
voidAdd(LinkList*a,LinkList*b,LinkList*c)//多项式加法
{
LinkList*p,*q,*s,*k;
s=c;
p=a->next;
while(p!
=NULL)//a存入c
{
if((q=(LinkList*)malloc(sizeof(LinkList)))==NULL)
exit(0);
q->m=p->m;
q->n=p->n;
q->next=NULL;
c->next=q;
c=c->next;
p=p->next;
}
c=s;
p=b->next;
while(p!
=NULL)//b存入c
{
while((c->next!
=NULL)&&(p->n)>((c->next)->n))
{
c=c->next;
}
if(c->next==NULL)
{
if((q=(LinkList*)malloc(sizeof(LinkList)))==NULL)
exit(0);
q->m=p->m;
q->n=p->n;
q->next=c->next;
c->next=q;
}
elseif(p->n==c->next->n)//系数相加
{
s=c;
c=c->next;
c->m=c->m+p->m;
if(c->m==0)
{
k=c;
c=s;
c->next=c->next->next;
free(k);
}
}
elseif(p->n>c->n&&c->next!
=NULL)
{
if((q=(LinkList*)malloc(sizeof(LinkList)))==NULL)
exit(0);
q->m=p->m;
q->n=p->n;
q->next=c->next;
c->next=q;
}
p=p->next;
}
}
3.主函数
voidmain()
{
LinkList*a,*b,*c;
countL;
inti,j;
ListInitiate(&a);
ListInitiate(&b);
ListInitiate(&c);
printf("请输入多项式a的项数:
");
scanf("%d",&j);
for(i=0;i { printf("请输入多项式a的第%d项系数: ",i+1); scanf("%g",&L.m); printf("请输入多项式a的第%d项指数: ",i+1); scanf("%d",&L.n); ListInsert(a,L); } printf("请输入多项式b的项数: "); scanf("%d",&j); for(i=0;i { printf("请输入多项式b的第%d项系数: ",i+1); scanf("%g",&L.m); printf("请输入多项式b的第%d项指数: ",i+1); scanf("%d",&L.n); ListInsert(b,L); } Add(a,b,c); printf("多项式a为: \n"); print(a);printf("\n"); printf("多项式b为: \n"); print(b);printf("\n"); printf("由上述a、b多项式,a+b=c为: \n"); print(c); printf("\n"); } 三.调试分析 1.调试中遇到的问题及解决 运行中发现程序只能运行一次,若输入新的a和b就要必须重新运行程序。 改进: 在main函数最后面加一个returnmain(),这样就解决了上述问题,可以连续运行程序了。 2.对设计和编码的回顾讨论和分析 把a存放在c中,用这种方法把a和b相加的结果放入c中。 3.改进设想 程序只能运行一次,若在main函数最后面加了一个returnmain(),这样就可以连续运行程序了。 4.经验和体会等。 这次上机实习是第一次上机实习,第一次将书本上的知识运用到上机实践中,感觉很困难,课下又通过查阅资料和学习了很多程序,学习知识和实践上机设计程序差别很大,自己感觉还需要更多地进行实践练习,才能更好地对知识进行运用。 这次上机对于我来说最大的收获就是对课本上的知识更加的理解了,更加重视实践环节的训练,相信以后通过多次的练习,我可以很好的完成题目的设计。 四.用户手册(即使用说明) 本程序是一个实现一元稀疏多项式相加运算的演示程序。 按照提示依次输入两个多项式各项的系数和指数,程序将进行多项式加法运算,并输出运算结果。 使用方法 1.运行程序。 2.按提示依次输入 3.每次输入完成按enter键确定。 4.全部输入完成后系统会自动算出多项式c,同时输出多项式a、b、c的值。 五.运行结果 (1)(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5) (2)(x+x100)+(x100+x200)=(x+2x100+x200) (3)(2x+5x8-3x11)+(7-5x8+11x9)=(7+2x+11x9-3x11) 六.源程序清单 #include #include #include typedefstruct { floatm; intn; }count; typedefstructNode { floatm;//系数 intn;//指数 structNode*next; }LinkList; voidListInitiate(LinkList**head)//链表初始化 { if((*head=(LinkList*)malloc(sizeof(LinkList)))==NULL) exit(0); (*head)->next=NULL; } voidListInsert(LinkList*head,countL)//链表插入操作 { LinkList*p,*q; p=head; while(p->next! =NULL)//从指数由小到大排序的角度寻找插入结点 { if(p->next->n>L.n) break; p=p->next; } if((q=(LinkList*)malloc(sizeof(LinkList)))==NULL) exit(0); q->m=L.m; q->n=L.n; q->next=p->next; p->next=q; } intprint(LinkList*head)//输出 { LinkList*p; p=head->next; if(p==NULL)//多项式为零时直接输出 { printf("0\n"); exit(0); } while(p->m==1&&p->n>0)//指数不为零时系数为1时的输出 { printf("x^%d",p->n); p=p->next; if(p==NULL) return0; elseprintf("+"); } while(p->next) { printf("%gx^%d",p->m,p->n); p=p->next; if(p->m>0) printf("+"); } printf("%gx^%d",p->m,p->n); return1; } voidAdd(LinkList*a,LinkList*b,LinkList*c)//实现多项式加法 { LinkList*p,*q,*s,*k; s=c; p=a->next; while(p! =NULL)//先将a存入c中 { if((q=(LinkList*)malloc(sizeof(LinkList)))==NULL) exit(0); q->m=p->m; q->n=p->n; q->next=NULL; c->next=q; c=c->next; p=p->next; } c=s; p=b->next; while(p! =NULL)//将b存入c中 { while((c->next! =NULL)&&(p->n)>((c->next)->n))//寻找插入结点 { c=c->next; } if(c->next==NULL)//从最后插入 { if((q=(LinkList*)malloc(sizeof(LinkList)))==NULL) exit(0); q->m=p->m; q->n=p->n; q->next=c->next; c->next=q; } elseif(p->n==c->next->n)//指数相等时系数相加 { s=c; c=c->next; c->m=c->m+p->m; if(c->m==0) { k=c; c=s; c->next=c->next->next; free(k); } } elseif(p->n>c->n&&c->next! =NULL) { if((q=(LinkList*)malloc(sizeof(LinkList)))==NULL) exit(0); q->m=p->m; q->n=p->n; q->next=c->next; c->next=q; } p=p->next; } } voidmain()//主函数 { LinkList*a,*b,*c; countL; inti,j; ListInitiate(&a); ListInitiate(&b); ListInitiate(&c); printf("请输入a的项数: "); scanf("%d",&j); for(i=0;i { printf("请输入a的第%d项系数: ",i+1); scanf("%g",&L.m); printf("请输入a的第%d项指数: ",i+1); scanf("%d",&L.n); ListInsert(a,L); } printf("请输入b的项数: "); scanf("%d",&j); for(i=0;i { printf("请输入b的第%d项系数: ",i+1); scanf("%g",&L.m); printf("请输入b的第%d项指数: ",i+1); scanf("%d",&L.n); ListInsert(b,L); } Add(a,b,c); printf("多项式a为: \n"); print(a);printf("\n"); printf("多项式b为: \n"); print(b);printf("\n"); printf("多项式a+b=c为: \n"); print(c); printf("\n"); }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构作业 线性表栈和队列及其应用 数据结构 作业 线性 队列 及其 应用