线性表的综合应用

闽江学院电子系

实验报告学生姓名：曹韦［班级:I学号：3142731课程：数据结构与算法一、实验题目：线性表的综合应用二、实验地点：计算机软件与网络实验室-实验楼A210三、实验目的：1.掌握顺序表和链表的概念，学会对问题进行分析，选择恰当的逻辑结构和物理结构；加深对顺序表和链表的理解，培养解决实际问题的编程能力。四、实验内容：实现一元稀疏多项式的表示及基本操作（建立，销毁，输出，加法，减法，求项数等操作）；一元多项式一定要包含系数项和指数项的描述，对一元多项式的基本运算，可应用两个有序链表合并的思想进行。五、实验环境（使用的软硬件）：利用VisualC++集成开发环境进行本实验操作。六、实验步骤及操作：“建立多项式算法”操作结果：输入m项的系数和指数，建立一个一元多项式P“销毁多项式算法”初始条件：一元多项式P已存在；操作结果：销毁一元多项式P“输出多项式算法”初始条件：一元多项式P已存在；操作结果：打印一元多项式P“多项式加法算法”初始条件：两个多项式的Pa，Pb已存在；操作结果：Pa=Pa+Pb，并销毁Pb“多项式减法算法”初始条件：两个多项式的Pa，Pb已存在；操作结果：Pa=Pa-Pb，并销毁Pb“求多项式项数的算法”初始条件：一元多项式P已存在；操作结果：返回P中的项数；七、实验结果：程序如下：#include<stdio.h>#include<stdlib.h>typedefstructnode(floatcoef;intexpn;structnode*next;}LinkList;//建立多项式算法LinkList*GreatePloyn()(LinkList*p,*head,*r;floata;intn;head=(LinkList*)malloc(sizeof(LinkList));head->next=NULL;r=head;printf("PleaseInputOnePloyn:\n");scanf("%f”,&a);while(a!=0){scanf("%d”,&n);p=(LinkList*)malloc(sizeof(LinkList));p->coef=a;p->expn=n;p->next=NULL;r->next=p;r=r->next;scanf("%f”,&a);returnhead;…式算法voidDestroyPloyn(LinkList*L){LinkList*p,*r;p=L->next;while(p!=NULL){r=p->next;free(p);p=r;free(L);…式算法voidPrintPloyn(LinkList*L){LinkList*p;p=L->next;while(p!=NULL){printf("%6.2fX%d",p->coef,p->expn);p=p->next;if(p!=NULL)printf("+");}printf("\n");}〃多项式加法voidAddPloyn(LinkList*A,LinkList*B){LinkList*p,*q,*s,*r;floatt;p=A->next;q=B->next;s=A;B->next=NULL;while((p!=NULL)&&(q!=NULL)){if(p->expn>q->expn){r=q->next;q->next=p;s->next=q;s=q;q=r;}elseif(p->expn<q->expn){s=p;p=p->next;}else{t=p->coef+q->coef;if(t!=0){p->coef=t;s=p;}else{s->next=p->next;free(p);}p=s->next;r=q;q=q->next;free(r);}}if(q!=NULL)s->next=q;DestroyPloyn(B);}〃多项式减法算法voidSubstract(LinkList*A,LinkList*B)(LinkList*p,*q,*s,*r;floatt;p=A->next;q=B->next;s=A;B->next=NULL;while(p&&q)(if(p->expn>q->expn){r=q->next;q->next=p;~q=r;elseif(p->expn<q->expn){s=p;p=p->next;}else{t=p->coef-q->coef;if(t!=0){p->coef=t;s=p;}else{s->next=p->next;free(p);}p=s->next;r=q;…free(r);if(q!=NULL){s->next=q;while(q){q->coef=-q->coef;q=q->next;}}口…；//求多项式项数的算法intPloynLength(LinkList*L){LinkList*p;intn=0;p=L->next;while(p)}„「顾n;//主函数voidmain(){LinkList*P1,*P2;charch;printf("PleaseInputYouWant:");scanf("%c”,&ch);P1=GreatePloyn();P2=GreatePloyn();printf("P1=");PrintPloyn(P1);printf("P2=");PrintPloyn(P2);switch(ch)(case'+':AddPloyn(P1,P2);break;case'-':Substract(P1,P2);break;case'*':break;default:printf("ERROR!!!\n");}printf("ThisPloynLengthis:%d\n”,PloynLength(P1));switch(ch)(case'+':printf("P1+P2=");break;case'-':printf("P1-P2=");break;case'*':break;default:printf("ERROR!!!\n");}PrintPloyn(P1);}测试数据为：(2x+5x8-3.1x11)+(7-5x8+11x9)(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)(x+x2+x3)+0(x+x3)-(-x-x3)程序测试：说明：以系数项为0作为建立一元多项式的结束标志，’\n’代表键盘上的回车编译程序，无显示错误。继续运行Configuration:3.18-Win32DebugCompiling...3.18.c3.18.obj-Qerror(s),Quarning(s)输入：1)+2)2侦1’\n’5’\n’8’\n’-3.1’\n’11’\n’0’\n’7’\n’0’\n’5’\n’8’\n’11’\n’9’\n’0’\n’

(3)输出:-3-00X0+-1.00X1+4.40X2+-1.20X9-3-00X0+5.40M2+7.80X156.O0K1+P2