数据结构实验报告

1数据结构实验报告第四次实验学号：20141060106姓名：叶佳伟一、实验目的1、复习线性表、栈、队列的逻辑结构、存储结构及基本操作；2、掌握顺序表、（带头结点）单链表、顺序栈、链队列；3、了解有顺表、链栈、循环队列。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）StatusInitStack(&S)//构造空栈S；（2）StatusPush(&S,e)//元素e入栈S；（3）StatusPop(&S,&e)//栈S出栈，元素为e。3、（必做题）假设队列中数据元素类型是字符型，请采用链队列实现队列的以下基本操作：（1）StatusInitQueue(&Q)//构造空队列Q；（2）StatusEnQueue(&Q,e)//元素e入队列Q；（3）StatusDeQueue(&Q,&e)//队列Q出队列，元素为e。三、算法描述（采用自然语言描述）⒈⑴分别插入第一个链表和第二个链表的数据；⑵根据有序判定函数compare，将两个有序表La和Lb归并为个有序表。⑶输出归并后的有序表。2.⑴构造一个栈的结构体⑵利用函数initstack构造空栈⑶Push函数将元素依次存储到栈里⑷利用pop函数输出栈顶元素23.⑴构造Queueptr的结构体⑵构造一个队列的结构体⑶利用函数InitQueue构造空队列⑷EnQueue函数将元素依次存储到栈里⑸利用DeQueue函数输出栈顶元素四、详细设计（画出程序流程图）五、程序代码（给出必要注释）第一题：#includestdio.h#includestdlib.htypedefstructLNode{intdate;structLNode*next;}LNode,*Link;typedefstructLinkList{Linkhead;intlen;}LinkList;3intcompare(LinkList*L,inte){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)()){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;}voidOrderMerge(LinkList*La,LinkList*Lb,int(*compare)()){inti,Lc=0;Linktemp,p,q;q=La-head-next;while(q!=NULL)4{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;}}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=='.')5{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(第一个有序表为：\n);(*Show)(NewList+0);printf(\n);printf(第二个有序表为：\n);(*Show)(NewList+1);printf(\n);printf(归并后有序表为\n);(*Show)(NewList+2);}intmain(){LinkList*NewList=NULL;inti;printf(\t开始插入数据\n);NewList=Initialize(NewList);Insert(NewList);for(i=0;i2;i++){OrderMerge(NewList+i,NewList+2,compare);}6Display(NewList,Show);return0;第二题：#includestdio.h#includestdlib.h#includemalloc.h#defineM50typedefstruct//定义一个栈结构{inttop;intarray[M];}Stack;voidInit(Stack*s);//初始化栈的函数voidPush(Stack*s,intdata);//进行压栈操作的函数voidTraverse(Stack*s);//遍历栈函数charPop(Stack*s);//进行出栈操作的栈函数voidClear(Stack*s);//清空栈的函数intmain(){Stacks;//定义一个栈inti;intnum;chardata;//临时保存用户输入的数据charre_num;//保存pop函数的返回值Init(&s);printf(你想输入几个数据:);scanf(%d,&num);for(i=0;inum;i++){printf(第%d个字符:,i+1);scanf(%s,&data);Push(&s,data);}Traverse(&s);//调用遍历函数printf(你想去掉几个字符:);scanf(%d,&num);printf(你去掉的字符是:);for(i=0;inum;i++){re_num=Pop(&s);//调用Pop函数，并把返回至赋给re.numprintf(%c,re_num);}printf(看看删除后还有啥:);Traverse(&s);7printf(\n);Clear(&s);//调用清空栈函数printf(遍历下看看栈空没\n);Traverse(&s);printf(\n);return0;}voidInit(Stack*s)//进行栈的初始化函数{s-top=-1;}voidPush(Stack*s,intdata)/*进栈*/{if(s-top=M-1)return;/*full*/s-top++;s-array[s-top]=data;}voidTraverse(Stack*s)//遍历栈的函数{inti;for(i=0;i=s-top;i++)printf(%2c,s-array[i]);}charPop(Stack*s)//进行出栈操作函数{charx;x=s-array[s-top];s-top--;returnx;}voidClear(Stack*s)//清空栈的函数{s-top=-1;}第三题：#includestdio.h#includestdlib.htypedefvoidStatus;8typedefintQElemType;#defineSTACK_INIT_SIZE10//初始容量#defineSTACKINCREMENT5//容量增量typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;StatusInitQueue(LinkQueue&Q){//构造一个空对列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(-1);Q.front-next=NULL;}StatusEnQueue(LinkQueue&Q,QElemTypee){//插入元素e为对列Q的新元素QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));if(!p)printf(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;}StatusDeQueue(LinkQueue&Q,QElemTypee){//若对列不空，用e返回其值，并返回OK//否则返回ERRORQueuePtrp;if(Q.front==Q.rear)printf(ERROR);p=Q.front-next;e=p-data;printf(对列中的队头元素为:%d\n,e);Q.front-next=p-next;if(Q.rear==p)Q.rear=Q.front;free(p);9}main(){LinkQueueQ;intn,i;QElemTypee;InitQueue(Q);printf(请输入队列中要入队列的元素个数:\n);scanf(%d,&n);for(i=0;in;i++){printf(队列里的第%d个元素为:,i+1);scanf(%d,&e);EnQueue(Q,e);}printf(\n);DeQueue(Q,e);}六、测试和结果（给出测试用例以及测试结果）第二题：：第三题：10七、用户手册（告诉用户如何使用程序）