数据结构实验报告(共6页).doc
精选优质文档-倾情为你奉上云南大学数据结构实验报告第 四 次实验学号：姓名： 一、实验目的 复习线性表的逻辑结构，存储结构及基本操作；掌握顺序表和（带头结点）单链表；了解有序表。二、实验内容 （必做题）假设有序表中数据元素类型是整型，请采用顺序表或（带头结点）单链表实现： 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.#include <stdio.h>#include <stdlib.h>typedef struct LNodeint date; struct LNode *next; LNode,*Link;/-线性表的单链表存储结构typedef struct LinkListLink head;/指向线性链表中的头结点 int len;/指示链表中数据元素的个数 LinkList;int compare (LinkList *L,int e)int Lc=0; Link p; p=L->head; p=p->next; while(p!=NULL)if(e>p->date)p=p->next; Lc+; else return Lc; return Lc;/-有序判定函数comparevoid OrderInsert (LinkList *L,int e,int (*compare)()Link temp,p,q; int Lc,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;elsefor(i=0; i<Lc; i+)p=p->next;q=q->next; q->next=temp;temp->next=p; +L->len;/-利用OrderInsert()构造有序表；根据有序判定函数compare，在有序表L的适当位置插入元素e；void OrderMerge (LinkList *La,LinkList *Lb,int (*compare)()int i,Lc=0; Link temp,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;elsefor(i=0; i<Lc; i+)p=p->next; temp->next=p->next; p->next=temp; q=q->next; +Lb->len;/根据有序判定函数compare，将两个有序表La和Lb归并为一个有序表LinkList *Initialize (LinkList *NewList)int i; Link temp; NewList=(LinkList *)malloc(2+1)*sizeof(LinkList); for(i=0; i<2+1; i+)temp=(Link)malloc(sizeof(LNode); temp->date=0; temp->next=NULL; (NewList+i)->head=temp; (NewList+i)->len=0;return NewList;void Insert (LinkList *NewList)int a,i; char c; printf("在第1个表中插入数据，以空格和回车为间隔，输入“.”对下个表插入数据n"); for(i=0; i<2; i+)while(1)scanf("%d",&a);c=getchar();if(c='.')if(i<2-2)printf("在第%d个表中插入数据，以空格和回车为间隔，输入“.”对下个表插入数据n",i+2);else if(i=2-2)printf("在第%d个表中插入数据，以空格和回车为间隔，输入“.”结束输入。n",i+2);break;elseOrderInsert(NewList+i),a,compare);void Show (LinkList *L)Link p; p=L->head->next; while(p!=NULL)printf("%dt",p->date); p=p->next;void Display (LinkList *NewList,void (*Show)()printf("所有有序表如下：n"); printf("第一个有序表为："); (*Show)(NewList+0); printf("n"); printf("第二个有序表为："); (*Show)(NewList+1); printf("n"); printf("归并后有序表为：n"); (*Show)(NewList+2);int main()LinkList *NewList=NULL; int i; printf("t开始插入数据！n数据与“.”不要输入在同一行！n"); NewList=Initialize(NewList); Insert(NewList); for(i=0; i<2; i+)OrderMerge (NewList+i,NewList+2,compare); Display(NewList,Show); return 0;六、测试和结果（给出测试用例以及测试结果）1.七、用户手册（告诉用户如何使用程序）打开并运行程序，根据提示输入数据。数据与“.”不要输入在同一行。专心-专注-专业
