数据结构实验报告4

1数据结构实验报告——实验4学号：姓名：得分：______________一、实验目的1、复习线性表的逻辑结构、存储结构及基本操作；2、掌握顺序表和（带头结点）单链表；3、了解有序表。二、实验内容1、（必做题）假设有序表中数据元素类型是整型，请采用顺序表或（带头结点）单链表实现：（1）OrderInsert(&L,e,int(*compare)(a,b))//根据有序判定函数compare，在有序表L的适当位置插入元素e；（2）OrderInput(&L,int(*compare)(a,b))//根据有序判定函数compare，并利用有序插入函数OrderInsert，构造有序表L；（3）OrderMerge(&La,&Lb,&Lc,int(*compare)())//根据有序判定函数compare，将两个有序表La和Lb归并为一个有序表Lc。2、（必做题）请实现：（1）升幂多项式的构造，升幂多项式是指多项式的各项按指数升序有序，约定系数不能等于0，指数不能小于0；（2）两个升幂多项式的相加。三、算法描述（采用自然语言描述）1.创建带头节点的链表，输入两个有序表数据LaLb归并两个有序表得有序表Lc输出三个有序表输入需插入数据e将e插入有序表Lc输出插入e后的Lc2.创建链表按指数升序输入多项式得序数和指数输出多项式按指数升序输入第二个多项式得序数和指数两个多项式相加输出第二个多项式和两个多项式得和四、详细设计（画出程序流程图）21.2.创建带头节点的链表输入两个有序表数据LaLb开始归并两个有序表得有序表Lc输出三个有序表输入需插入数据e将e插入有序表Lc输出插入e后的Lc结束创建链表按指数升序输入多项式得序数和指数开始输出多项式按指数升序输入第二个多项式得序数和指数两个多项式相加输出第二个多项式和两个多项式的和结束3五、程序代码（给出必要注释）1.#includestdio.h#includemalloc.htypedefstructLNode{intdate;structLNode*next;}LNode,*Link;typedefstructLinkList{Linkhead;//头结点intlenth;//链表中数据元素的个数}LinkList;intcompare(LinkList*L,inte)//有序判定函数compare{intLc=0;Linkp;p=L-head;p=p-next;while(p!=NULL){if(ep-date){p=p-next;Lc++;}elsereturnLc;}returnLc;}voidOrderInsert(LinkList*L,inte,int(*compare)())//根据有序判定函数compare，在有序表L的适当位置插入元素e；{Linktemp,p,q;intLc,i;temp=(Link)malloc(sizeof(LNode));temp-date=e;p=q=L-head;4p=p-next;Lc=(*compare)(L,e);if(Lc==L-lenth){while(q-next!=NULL){q=q-next;}q-next=temp;temp-next=NULL;}else{for(i=0;iLc;i++){p=p-next;q=q-next;}q-next=temp;temp-next=p;}++L-lenth;}voidOrderMerge(LinkList*La,LinkList*Lb,int(*compare)())//根据有序判定函数compare,将两个有序表La和Lb归并为一个有序表{inti,Lc=0;Linktemp,p,q;q=La-head-next;while(q!=NULL){p=Lb-head;temp=(Link)malloc(sizeof(LNode));temp-date=q-date;Lc=(*compare)(Lb,q-date);if(Lc==Lb-lenth){while(p-next!=NULL){p=p-next;}p-next=temp;temp-next=NULL;5}else{for(i=0;iLc;i++){p=p-next;}temp-next=p-next;p-next=temp;}q=q-next;++Lb-lenth;}}LinkList*Initialize(LinkList*NewList){inti;Linktemp;NewList=(LinkList*)malloc((2+1)*sizeof(LinkList));for(i=0;i2+1;i++){temp=(Link)malloc(sizeof(LNode));temp-date=0;temp-next=NULL;(NewList+i)-head=temp;(NewList+i)-lenth=0;}returnNewList;}voidInsert(LinkList*NewList){inta,i;charc;printf(在第1个表中插入数据,输入“N”再对下个表插入数据\n);for(i=0;i2;i++){while(1){scanf(%d,&a);c=getchar();if(c=='N'){6if(i2-2)printf(在第%d个表中插入数据,输入“N”再对下个表插入数据\n,i+2);elseif(i==2-2)printf(在第%d个表中插入数据,输入“N”结束。\n,i+2);break;}else{OrderInsert((NewList+i),a,compare);}}}}voidShow(LinkList*L)//输出有序表{Linkp;p=L-head-next;while(p!=NULL){printf(%d,p-date);p=p-next;}}voidvisit(LinkList*NewList,void(*Show)()){printf(有序表如下:\n);printf(第一个有序表为:\n);(*Show)(NewList+0);printf(\n);printf(第二个有序表为:\n);(*Show)(NewList+1);printf(\n);printf(归并后有序表为:\n);(*Show)(NewList+2);printf(\n);}intmain(){LinkList*NewList=NULL;LinkList*L;inti,e;7printf(请按要求输入数据\n);NewList=Initialize(NewList);Insert(NewList);for(i=0;i2;i++){OrderMerge(NewList+i,NewList+2,compare);}visit(NewList,Show);L=NewList;printf(\n请输入将要插入的e:\n);scanf(%d,&e);OrderInsert((NewList+i),e,compare);printf(对归并后有序表插入e后得\n);Show(NewList+2);return0;}2.#includestdio.h#includemalloc.htypedefstructnode{intxi;intzi;structnode*next;}Node;Node*Creat()//用链表储存多项式的序数与指数{Node*head,*p,*q;intor,in;head=(Node*)malloc(sizeof(Node));head-next=NULL;q=head;printf(请输入多项式的序数与指数\n（注意：按照指数升序输入，系数不能等于0且指数不能小于0，序数与指数用空格隔开,并以00结束输入）\n);scanf(%d%d,&or,&in);while(or){p=(Node*)malloc(sizeof(Node));p-xi=or;p-zi=in;p-next=q-next;8q-next=p;q=p;scanf(%d%d,&or,&in);}returnhead;}voidvisit(Node*head)//输出多项式{Node*p=head-next;while(p){printf(%dX^%d+,p-xi,p-zi);p=p-next;}printf(NULL\n\n);}Node*Add(Node*head1,Node*head2)//多项式相加{Node*p,*head,*p1,*p2;intsum;head=(Node*)malloc(sizeof(Node));p=head;p1=head1-next;p2=head2-next;while(p1&&p2)//当两多项式都存在时{if(p1-zi==p2-zi)//如果指数相等{sum=p1-xi+p2-xi;if(sum){p1-xi=sum;p-next=p1;p=p1;}p1=p1-next;p2=p2-next;}else//指数不相等分两种情况{if(p1-zip2-zi){9p-next=p1;p=p1;p1=p1-next;}else{p-next=p2;p=p2;p2=p2-next;}}}if(p1)p-next=p1;//将1中剩余结点接到和链表中因为最终只剩下一段链表多项式elsep-next=p2;//将2中剩余结点接到和链表中这段链的链头接到目标链表就可以了returnhead;}intmain(){printf(请输入第一个多项式\n);Node*head,*p1,*p2;p1=Creat();printf(多项式为:\n);visit(p1);printf(请输入第二个多项式\n);p2=Creat();printf(多项式为:\n);visit(p2);head=Add(p1,p2);printf(\n多项式相加后得：\n);visit(head);return0;}六、测试和结果（给出测试用例，并给出测试结果）1.102.七、用户手册（告诉用户如何使用程序，使用注意事项等）1.按照要求输入