1数据结构-实验报告一(线性表的基本操作)

PAGEPAGE7数据结构实验报告实验内容实验一线性表的基本操作及其应用专业信息与计算科学班级1301学号33姓名蒋丰沛指导教师刘长松2015年4月22日实验基本格式一、实验目的二、实验内容和要求三、源代码四、测试结果五、心得体会实验一线性表的基本操作及其应用一、实验目的1、帮助读者复习C++语言程序设计中的知识。2、熟悉线性表的逻辑结构。3、熟悉线性表的基本运算在两种存储结构上的实现。4、掌握顺序表的存储结构形式及其描述和基本运算的实现。5、熟练掌握动态链表结构及有关算法的设计二、实验内容求两个多项式的相加运算[问题描述]用单链表存储一元多项式，并实现两个多项式的相加运算。[基本要求]（1）本程序需要基于线性表的基本操作来实现一元多项式的加法，也可以用数组实现。；（2）两个多项式都有键盘输入相应的系数和指数[测试数据]由学生任意指定。三、源代码//文件名:exp2-7.cpp#include<stdio.h>#include<malloc.h>#defineMAX20 //多项式最多项数typedefstruct //定义存放多项式的数组类型{ doublecoef; //系数 intexp; //指数}PolyArray[MAX];typedefstructpnode //定义单链表结点类型{ doublecoef; //系数 intexp; //指数 structpnode*next;}PolyNode;voidDispPoly(PolyNode*L) //输出多项式{ boolfirst=true; //first为true表示是第一项 PolyNode*p=L->next; while(p!=NULL) { if(first) first=false; elseif(p->coef>0) printf("+"); if(p->exp==0) printf("%g",p->coef); elseif(p->exp==1) printf("%gx",p->coef); else printf("%gx^%d",p->coef,p->exp); p=p->next; } printf("\n");}voidDestroyList(PolyNode*&L) //销毁单链表{ PolyNode*p=L,*q=p->next; while(q!=NULL) { free(p); p=q; q=p->next; } free(p);}voidCreateListR(PolyNode*&L,PolyArraya,intn)//尾插法建表{ PolyNode*s,*r;inti; L=(PolyNode*)malloc(sizeof(PolyNode)); //创建头结点 L->next=NULL; r=L; //r始终指向终端结点,开始时指向头结点 for(i=0;i<n;i++) { s=(PolyNode*)malloc(sizeof(PolyNode));//创建新结点 s->coef=a[i].coef; s->exp=a[i].exp; r->next=s; //将*s插入*r之后 r=s; } r->next=NULL; //终端结点next域置为NULL}voidSort(PolyNode*&head) //按exp域递减排序{ PolyNode*p=head->next,*q,*r; if(p!=NULL) //若原单链表中有一个或以上的数据结点 { r=p->next; //r保存*p结点后继结点的指针 p->next=NULL; //构造只含一个数据结点的有序表 p=r; while(p!=NULL) { r=p->next; //r保存*p结点后继结点的指针 q=head; while(q->next!=NULL&&q->next->exp>p->exp) q=q->next; //在有序表中找插入*p的前驱结点*q p->next=q->next; //将*p插入到*q之后 q->next=p; p=r; } }}voidAdd(PolyNode*ha,PolyNode*hb,PolyNode*&hc)//求两有序集合的并{ PolyNode*pa=ha->next,*pb=hb->next,*s,*tc; doublec; hc=(PolyNode*)malloc(sizeof(PolyNode)); //创建头结点 tc=hc; while(pa!=NULL&&pb!=NULL) { if(pa->exp>pb->exp) { s=(PolyNode*)malloc(sizeof(PolyNode)); //复制结点 s->exp=pa->exp;s->coef=pa->coef; tc->next=s;tc=s; pa=pa->next; } elseif(pa->exp<pb->exp) { s=(PolyNode*)malloc(sizeof(PolyNode)); //复制结点 s->exp=pb->exp;s->coef=pb->coef; tc->next=s;tc=s; pb=pb->next; } else //pa->exp=pb->exp { c=pa->coef+pb->coef; if(c!=0) //系数之和不为0时创建新结点 { s=(PolyNode*)malloc(sizeof(PolyNode)); //复制结点 s->exp=pa->exp;s->coef=c; tc->next=s;tc=s; } pa=pa->next; pb=pb->next; } } if(pb!=NULL)pa=pb; //复制余下的结点 while(pa!=NULL) { s=(PolyNode*)malloc(sizeof(PolyNode)); //复制结点 s->exp=pa->exp;s->coef=pa->coef; tc->next=s;tc=s; pa=pa->next; } tc->next=NULL;}voidmain(){ PolyNode*ha,*hb,*hc; PolyArraya={{1.2,0},{2.5,1},{3.2,3},{-2.5,5}}; PolyArrayb={{-1.2,0},{2.5,1},{3.2,3},{2.5,5},{5.4,10}}; CreateListR(ha,a,4); CreateListR(hb,b,5); printf("原多项式A:");DispPoly(ha); printf("原多项式B:");DispPoly(hb); Sort(ha); Sort(hb); printf("有序多项式A:");DispPoly(ha); printf("有序多项式B:");DispPoly(hb); Add