数据结构实验报告59464

1、!-数据结构实验报告第四次实验学号：20141060106姓名：叶佳伟一、实验目的1、复习线性表、2、掌握顺序表、3、了解有顺表、栈、队列的逻辑结构、存储结构及基本操作；(带头结点)单链表、顺序栈、链队列；3、了解有顺表、链栈、循环队列。链栈、循环队列。二、实验内容1、(必做题)假设有序表中数据元素类型是整型，请采用顺序表或(带头结点)单链表实 现：(1) Orderl nsert(&L, e, i nt (*co mp are)(a, b)/序表L的适当位置插入元素e;(2) Orderlnput(&L, int (*compare)(a, b)/序插入函数Orderinse

2、rt，构造有序表L;(3) OrderMerge(&La, &Lb, &Lc, int (*compare)()/两个有序表La和Lb归并为一个有序表Lc。根据有序判定函数compare，在有根据有序判定函数com pare,并利用有根据有序判定函数 comp are,将2、(必做题)假设栈中数据元素类型是字符型，请采用顺序栈实现栈的以下基本操作:1)2)3)Status In itStack (&S) /Status P ush(&S, e) /Status Pop(&S, &e) /构造空栈S; 元素e入栈S; 栈S出栈，元素为e。3

3、、(2)(3)元素为(必做题)假设队列中数据元素类型是字符型,1)请采用链队列实现队列的以下基本操作:Status Ini tQueue(&Q) /Status En Queue(&Q e) /Status DeQueue (&Q, & e) / e。构造空队列Q元素e入队列队列Q出队列,Q;三、算法描述(采用自然语言描述)1分别插入第一个链表和第二个链表的数据；根据有序判定函数 compare,将两个有序表 La和 Lb归并为个有序表。输出归并后的有序表。2.构造一个栈的结构体利用函数initstack构造空栈Push函数将元素依次存储到栈里 利用pop函数输

4、出栈顶元素3.构造Queueptr的结构体构造一个队列的结构体利用函数InitQueue构造空队列EnQueue函数将元素依次存储到栈里 利用DeQueue函数输出栈顶元素四、详细设计五、程序代码（给出必要注释）第一题：#include <stdio.h>#in elude <stdlib.h>typ edef struct LNodeint date;struct LNode *n ext; LNode,*Li nk;typ edef struct Lin kList Link head;int len; Lin kList;（画出程序流程图） int compare

5、 (Lin kList *L,i nt e) int Lc=0;Li nk p;p=L->head;p=p->n ext;while( p!=NULL)if(e >p->date)p=p->n ext; Lc+;elsereturn Lc;return Lc; void OrderI nsert (Lin kList *L,i nt e,i nt (*co mp are)() Link tem p,p,q;int Lc,i;temp=(Lin k)malloc(sizeof(LNode);temp->date=e;p=q=L->head;p=p->

6、;n ext;Lc=(*com pare)(L,e);if(Lc=L->le n)while(q-> next!=NULL)q=q->n ext;q->n ext=te mp;temp->n ext=NULL;elsefor(i=0; i<Lc; i+)p=p->n ext;q=q->n ext;q->n ext=te mp ;te mp->n ext =p;+L->le n; void OrderMerge (Lin kList *La,L in kList *Lb,i nt (*co mp are)() int i,Lc=0

7、;Li nk tem p,p,q;q=La->head->n ext;while(q!=NULL)p=Lb->head;temp=(Li nk)malloc(sizeof(LNode); temp->date=q->date;Lc=(*com pare)(Lb,q->date); if(Lc=Lb->le n)while( p-> next!=NULL)p=p->n ext;p->n ext=te mp;temp->n ext=NULL;elsefor(i=0; i<Lc; i+)p=p->n ext;temp-&g

8、t;n ext =p->n ext;p->n ext=te mp;q=q->n ext;+Lb->le n;Lin kList *I nitialize (Li nkList *NewList)int i;Li nk temp;NewList=(Li nkList *)malloc(2+1)*sizeof(Li nkList); for(i=0; i<2+1; i+)temp=(Lin k)malloc(sizeof(LNode);temp->date=O;temp->n ext=NULL;(NewList+i)->head=te mp;(New

9、List+i)->le n=0;return NewList; void In sert (Li nkList *NewList)int a,i;char c;printf(”在第1个表中插入数据，以空格和回车为间隔， 输入”.”对下个表插入数据n");for(i=0; i<2; i+)while(1)sca nf("%d",&a);c=getchar();if(c='.')if(i<2-2).”对下个表插入数据.”结束输出n",i+2);printf(”在第%d个表中插入数据，以空格和回车为间隔，输入”n&qu

10、ot;,i+2);else if(i=2-2)prin tf("在第d(表中插入数据，以空格和回车为间隔，输入”break;elseOrderI nsert(NewList+i),a,co mp are); void Show (Li nkList *L) Li nk p;p=L->head->n ext; while( p!=NULL) prin tf("%dt", p->date); p=p->n ext;void Dis play (Lin kList *NewList,void (*Show)() prin tf("所有有

11、序表如下prin tf("第一个有序表为：(*Show)(NewList+0);prin tf("n");prin tf("第二个有序表为：(*Show)(NewList+1);prin tf("n");prin tf("归并后有序表为(*Show)(NewList+2);n");n");n");n");int mai n()Li nkList *NewList=NULL;int i;printf("t开始插入数据n");NewList=I nitialize(Ne

12、wList);In sert(NewList);for(i=0; i<2; i+)OrderMerge (NewList+i,NewList+2,com pare);Dis play(NewList,Show); return 0;第二题：#inelude <stdio.h>#i nclude <stdlib.h>#in elude <malloc.h>#defi ne M 50typ edef struct/ int top; int arrayM;Stack;void In it(Stack *s);/void P ush(Stack *s,i n

13、t data); void Traverse(Stack *s); char Pop (Stack *s); void Clear(Stack *s); int mai n() Stack s;int i;int num; char data; char re_num;Init(& s);printf(”你想输入几个数据scan f("%d", &n um);for (i=0;i< nu m;i+)printf(”第4个字符:",i+1);sca nf("%s", &data);P ush(&s,data)

14、;Traverse(&s);/prin tf("你想去掉几个字符：”)；scan f("%d", &n um);printf("你去掉的字符是:");for (i=0;i< nu m;i+)re_num = Pop(&s); prin tf("%c ",re_ nu m);prin tf("看看删除后还有啥：”)；Traverse(&s);/定义一个栈结构/初始化栈的函数进行压栈操作的函数 遍历栈函数进行出栈操作的栈函数 清空栈的函数定义一个栈临时保存用户输入的数据保存pop函

15、数的返回值调用遍历函数调用Pop函数，并把返回至赋给re.numprin tf("n");调用清空栈函数Clear( &s);/printf(”遍历下看看栈空没n");Traverse(&s);prin tf("n");return 0;void In it(Stack *s)/ s->to p=-1;进行栈的初始化函数void P ush(Stack *s,i nt data) /* 进栈*/if (s->to p>=M-1)return;/*full*/ s->t op+;s->arrays-&

16、gt;t op=data;void Traverse(Stack *s)/int i;for(i=0;i<=s->t op ;i+)prin tf("%2c",s->arrayi); char Pop (Stack *s)/char x;x=s->arrays->t op; s->to p-;return x;遍历栈的函数进行出栈操作函数void Clear(Stack *s)/s->t op=-1;清空栈的函数第三题:#in clude<stdio.h>#in clude<stdlib.h>typ edef

17、 void Status;typ edef int QEIemT ype;#defi ne STACK_INIT_SIZE 10/ 初始容量#define STACKINCREMENT 5/ 容量增量typ edef struct QNodeQEIemT ype data; struct QNode *n ext;QNode,*Queue Ptr;typ edef structQueue Ptr fron t;/队头指针Queue Ptr rear;/队尾指针Lin kQueue;Status Ini tQueue(Li nkQueue & Q)/构造一个空对列 QQ.fro nt=Q

18、.rear=(Queue Ptr)malloc(sizeof(QNode);if(!Q.fro nt) exit(-1);Q.fro nt-> next=NULL;Status En Queue(L in kQueue & Q,QElemT ype e)/插入元素e为对列Q的新元素Queue Ptr p;p=(Queue Ptr)malloc(sizeof(QNode);if(! p) prin tf("OVERFLOW");p->data=e; p->n ext=NULL;Q.rear- >n ext =p;Q.rear= p;Status DeQueue(L in kQueue & Q,QElemT ype e)/若对列不空，用e返回其值，并返回 OK/否则返回ERRORQueue Ptr p;if(Q.fro nt=Q.rear) prin tf("ERROR");p=Q.fr ont->n ext;e=p->data;printf(”对列中的队头元素为:%dn",e)