数据结构实验报告[4]

云南大学数据结构实验报告第四次实验学号：姓名：一、实验目的⒈复习线性表的逻辑结构，存储结构及基本操作；⒉掌握顺序表和（带头结点）单链表；⒊了解有序表。二、实验内容⒈（必做题）假设有序表中数据元素类型是整型，请采用顺序表或（带头结点）单链表实现：⑴OrderInsert(&L,e,int(*compare)())//根据有序判定函数compare，在有序表L的适当位置插入元素e；⑵利用OrderInsert()构造有序表；⑶OrderMerge(&La,&Lb,&Lc,int(*compare)())//根据有序判定函数compare，将两个有序表La和Lb归并为一个有序表Lc。⒉（选做题）请采用（带头结点）单链表实现：⑴升幂多项式的构造，即各个结点存储各项系数与指数，并且链表按指数升序有序；约定系数不能等于0，指数不能小于0）⑵两个升幂多项式的相加。三、算法描述（采用自然语言描述）⒈⑴分别插入第一个链表和第二个链表的数据；⑵根据有序判定函数compare，将两个有序表La和Lb归并为一个有序表。⑶输出归并后的有序表。四、详细设计（画出程序流程图）五、程序代码（给出必要注释）1.#includestdio.h#includestdlib.htypedefstructLNode{intdate;structLNode*next;}LNode,*Link;//----------线性表的单链表存储结构typedefstructLinkList{Linkhead;//指向线性链表中的头结点intlen;//指示链表中数据元素的个数}LinkList;intcompare(LinkList*L,inte){intLc=0;Linkp;p=L-head;p=p-next;while(p!=NULL){if(ep-date)开始输入数据输出归并后的有序表结束将两个有序表归并为一个有序表{p=p-next;Lc++;}elsereturnLc;}returnLc;}//-------有序判定函数comparevoidOrderInsert(LinkList*L,inte,int(*compare)()){Linktemp,p,q;intLc,i;temp=(Link)malloc(sizeof(LNode));temp-date=e;p=q=L-head;p=p-next;Lc=(*compare)(L,e);if(Lc==L-len){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-len;}//-----利用OrderInsert()构造有序表；根据有序判定函数compare，在有序表L的适当位置插入元素e；voidOrderMerge(LinkList*La,LinkList*Lb,int(*compare)()){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-len){while(p-next!=NULL){p=p-next;}p-next=temp;temp-next=NULL;}else{for(i=0;iLc;i++){p=p-next;}temp-next=p-next;p-next=temp;}q=q-next;++Lb-len;}}//根据有序判定函数compare，将两个有序表La和Lb归并为一个有序表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)-len=0;}returnNewList;}voidInsert(LinkList*NewList){inta,i;charc;printf(在第1个表中插入数据，以空格和回车为间隔，输入“.”对下个表插入数据\n);for(i=0;i2;i++){while(1){scanf(%d,&a);c=getchar();if(c=='.'){if(i2-2)printf(在第%d个表中插入数据，以空格和回车为间隔，输入“.”对下个表插入数据\n,i+2);elseif(i==2-2)printf(在第%d个表中插入数据，以空格和回车为间隔，输入“.”结束输入。\n,i+2);break;}else{OrderInsert((NewList+i),a,compare);}}}}voidShow(LinkList*L){Linkp;p=L-head-next;while(p!=NULL){printf(%d\t,p-date);p=p-next;}}voidDisplay(LinkList*NewList,void(*Show)()){printf(所有有序表如下：\n);printf(第一个有序表为：);(*Show)(NewList+0);printf(\n);printf(第二个有序表为：);(*Show)(NewList+1);printf(\n);printf(归并后有序表为：\n);(*Show)(NewList+2);}intmain(){LinkList*NewList=NULL;inti;printf(\t开始插入数据！\n数据与“.”不要输入在同一行！\n);NewList=Initialize(NewList);Insert(NewList);for(i=0;i2;i++){OrderMerge(NewList+i,NewList+2,compare);}Display(NewList,Show);return0;}六、测试和结果（给出测试用例以及测试结果）1.七、用户手册（告诉用户如何使用程序）⒈打开并运行程序，根据提示输入数据。数据与“.”不要输入在同一行。