数据结构 顺序栈 链栈 循环队列 链队列 hrbedu

1、第三章实验报告实验名称：数据结构第三章实验实验类型：验证性学号姓名：红领巾1. 问题描述（1）顺序栈l 顺序栈的C语言描述l 基本运算的算法置空栈、判栈空、进栈、出栈、读栈顶、输出栈、判栈满（2）链栈l 链栈的C语言描述l 基本运算的算法置空栈、判栈空、进栈、出栈、读栈顶（3）循环队列l 循环队列的C语言描述l 基本运算的算法置空队、判队空、进队、出队、读队头元素、输出循环队列（4）链队列l 链队列的C语言描述l 基本运算的算法置空队、判队空、进队、出队、读队头元素2. 数据结构设计（1）顺序栈要实现顺序栈操作，我们需要一个栈顶指针一个栈底指针，以及说明当前已经分配的存储空间（即当前可使用的最

2、大容量），因此结构中需要定义这三个部分typedef struct char *base; char *top; int stacksize;Sq;（2）链栈对于链栈，每一个人节点需要有data域和next域，分别储存数据以及指向下一个节点，下一个节点也应该是拥有这两个域，所以用到嵌套定义来定义节点的数据结构typedef struct nodechar data;struct node *next;node;（3）循环队列对于循环队列，需要有头尾指针指向队列头元素和尾元素的下一个位置，所以我们定义front，rear指针，为了说明动态分配的存储空间，我们定义了base，这就是循环队列的存储结

3、构typedef struct int *base; int front; int rear;SqQueue;（4）链队列根据要求可知，我们运用单链队列即可实现所需要的功能，对于单链队列，我们需要两个指针作为队头队尾指针从而实现队列的操作，所以定义front，rear。对于每一个节点都有data和next域来存储数据和指向下一个节点，所以进行这种节点定义。typedef struct QNode int data;QNode *next;QNode,*QPtr;typedef struct QlinkQPtr front; QPtr rear;Qlink;3. 算法设计（1） 顺序栈系统规定的

4、功能设计的算法有：置空栈、判栈空、进栈、出栈、读栈顶、输出栈、判栈满1） 初始化和建立顺序栈S1:定义数据结构类型typedef struct char *base; char *top; int stacksize;Sq/定义结构体，其中包含栈顶、栈尾指针和存储空间S2：初始化这个顺序栈int InitSq(Sq&S) S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(Sq); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; /申请

5、存储空间，并且将栈顶栈尾元素指在一个位置，构造空栈S3：从键盘输入一串字符，根据这些字符构造顺序栈Sq create(Sq &S)InitSq(S);printf("请输入你的栈");char str100;gets(str);/得到字符int n=strlen(str);for(int i=0;i<n;i+)Push(S,stri);/调用Push函数将每个字符入栈return S; 2）置空栈编写子函数Clear，使其可以实现置空栈功能int Clear(Sq&S)while(S.top!=S.base)char e;Pop(S,e);return

6、 OK; 在主函数里调用Clear子函数，就能达到置空栈的功能3） 判栈空S1：编写判断栈空的子函数Empty，使其实现判栈空功能int Empty(Sq S)if(S.top=S.base)return OK;else return ERROR;S2：在主函数调用时根据子函数返回值判断输出内容if(Empty(S) printf("Emptyn");else printf("NotEmpty");4） 进栈S1：从客户端得到所要入栈的元素printf("进栈元素是:");scanf("%c",&x);S2

7、：编写子函数Push，使其可以实现将元素入栈功能int Push(Sq&S,char e)if(S.top-S.base>=S.stacksize) S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char);if(!S.base) exit (OVERFLOW);S.top=S.base+S.stacksize;/调整指针S.stacksize+=STACKINCREMENT;/增大空间*S.top+=e;return OK;5） 出栈S1：编写子函数GetTop，使其可以得到栈顶元素，从而确定要

8、删去的元素是什么，并且返回这个元素int GetTop(Sq S,char &e)if(S.top=S.base) return ERROR;e=*(S.top-1);return e;S2：编写子函数Pop，删除栈顶元素int Pop(Sq&S,char e)if(S.top=S.base)return ERROR;e=*-S.top;return e;S3：编写子函数Print，让这个函数可以输出栈里每一个元素来输出出栈后的栈里元素int Print(Sq S) char *p,*q; p=S.top; q=S.base; if(p=q) return ERROR; whi

9、le(p!=q) printf("%cn",*(p-1); p-; return OK;6） 读栈顶调用函数GetTop，读到栈顶元素，并且输出这个元素GetTop(S,a);printf("%cn",a)7）输出栈调用函数Print，输出栈里每一个元素8）判栈满S1：编写函数T，使其可以实现判栈满功能int T(Sq S) if(S.top-S.base>=S.stacksize) return OK; else return ERROR;S2：根据返回值，确定输出内容if(T(S)printf("Yn");else prin

10、tf("Nn");9） 选择功能S1：弹出提示，得到键盘处根据提示所输入的字符printf("选择你想要的功能n");printf("1置空栈n2判断栈空n3进栈n4出栈n5读栈顶n6输出栈n7判栈满n");printf("选择你想要的功能n");scanf("%d",&m);S2：用switch分析得到的m，根据不同的m进入不同的case，调用不同的函数switch(m)case 1:Clear(S);printf("Emptyn");break;case 2:if

11、(Empty(S) printf("Emptyn"); else printf("NotEmpty"); break;case 3:printf("进栈元素是:");scanf("%c",&x);Push(S,x);Print(S);break;case 4:GetTop(S,a);Pop(S,a);Print(S);break;case 5:GetTop(S,a);printf("%cn",a);break;case 6:Print(S);break;case 7:if(T(S)pri

12、ntf("Yn"); else printf("Nn");break;（2） 链栈系统规定的功能设计的算法有：置空栈、判栈空、进栈、出栈、读栈顶1）定义节点，初始化链栈，创建链栈S1：定义节点typedef struct nodechar data;struct node *next;node;/节点的定义S2:初始化链栈int Init(node* &h)h->next=NULL;return OK;/建立一个空栈S3：编写子函数Set，使其根据键盘端的输入，创建链栈int Set(node* &h)int i; printf(&

13、quot;请输入你的栈");char str100;gets(str);/得到字符串int n=strlen(str); for(i=0;i<n;i+)Push(h,stri);/将每一个字符入栈return OK;2） 置空栈编写子函数Clear，使其可以实现置空栈功能int Clear(node* &h)h->next=NULL;return OK;在主函数里调用Clear子函数，就能达到置空栈的功能3） 判栈空S1：编写判断栈空的子函数Empty，使其实现判栈空功能int Empty(node* &h)if(h->next=NULL) retu

14、rn OK;else return FALSE;S2：在主函数调用时根据子函数返回值判断输出内容if(Empty(h) printf("Emptyn");else printf("NotEmpty");break;if(Empty(S) printf("Emptyn");else printf("NotEmpty");4） 进栈S1：从客户端得到所要入栈的元素printf("进栈元素是:");scanf("%c",&x);S2：编写子函数Push，使其可以实现将元素入

15、栈功能int Push(node* &h,char x)node *s;s=(node*)malloc(sizeof(node);s->data=x;s->next=h;h=s;return OK;5） 出栈S1：编写子函数Pop，删除栈顶元素int Pop(node* &h)char x;x=h->data;node *p;p=(node*)malloc(sizeof(node);p=h;h=h->next;free(p);return OK;S2：编写子函数Gethead，使其可以得到栈顶元素，从而得到新的栈顶元素来确认成功int Gethead(n

16、ode* &h,char a)if(h->next=NULL)return FALSE ;a=h->data;printf("head:%cn",a); return OK;6） 读栈顶调用Gethead函数即可完成功能7） 选择需要的功能用switch分析得到的m，根据不同的m进入不同的case，调用不同的函数printf("选择你想要的功能n");scanf("%d",&m);getchar();switch(m)case 1:Clear(h);printf("Emptyn");br

17、eak;case 2:if(Empty(h) printf("Emptyn");else printf("NotEmpty");break;case 3:printf("进栈元素是:");scanf("%c",&x);Push(h,x);break;case 4:Pop(h);Gethead(h,a);break;case 5:Gethead(h,a);break;（3） 循环队列系统规定的功能设计的算法有：置空队、判队空、进队、出队、读队头元素、输出1） 初始化和建立队列S1：定义结构体typedef s

18、truct int *base; int front; int rear;SqQueue;S2：初始化队列int Init(SqQueue &Q) Q.base=(int *)malloc(MAXQSIZE*sizeof(int); if(!Q.base)return (OVERFLOW); Q.front=Q.rear=0; return OK;S3：建立循环队列int Set(SqQueue &Q)int i;Init(Q);char str100;printf("请输入队列:n");gets(str);int n=strlen(str);for(i=0

19、;i<n;i+)En(Q,stri);return OK;2）置空队编写子函数Clear，使其可以实现置空队功能int Clear(SqQueue &Q) if(Q.rear=Q.front)return OK; Q.rear=Q.front; return OK;在主函数里调用Clear子函数，就能达到置空队的功能3） 判队空S1：编写判断栈空的子函数Empty，使其实现判队空功能int Empty(SqQueue &Q) if(Q.rear=Q.front)return OK; else return FALSE;S2：在主函数调用时根据队中指针位置判断输出内容if(

20、Q.front=Q.rear)printf("empty");else printf("notempty");4） 进队S1：从客户端得到所要入队的元素printf("进队元素是:");scanf("%c",&x);S2：编写子函数En，使其可以实现将元素入栈功能int En(SqQueue &Q,char e) if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR; Q.baseQ.rear=e; Q.rear=(Q.rear+1)%MAXQSIZE; return

21、 OK;5） 出队S1：编写子函数De，删除队头元素int Pop(node* &h)char x;x=h->data;node *p;p=(node*)malloc(sizeof(node);p=h;h=h->next;free(p);return OK;S2：编写子函数Gethead，使其可以得到队头元素，从而得到新的队头元素来确认成功int Gethead(node* &h,char a)if(h->next=NULL)return FALSE ;a=h->data;printf("head:%cn",a); return OK

22、;6） 读队头元素调用Gethead函数即可实现7） 输出队中元素编写子函数Print，使其可以输出队中每一个元素int Print(SqQueue Q) if(Q.rear=Q.front)return ERROR; int a,b; a=Q.front; b=Q.rear; while(a!=b) (printf("%cn",Q.basea); a=(a+1)%MAXQSIZE; return OK;8）选择需要的功能用switch分析得到的m，根据不同的m进入不同的case，调用不同的函数printf("选择你需要的功能n"); printf(&q

23、uot;1置空队n2判队空n3进队n4出队n5读队头元素n6输出循环队列n");while(1)printf("选择你想要的功能n");scanf("%d",&m);switch(m)case 1:Clear(Q);printf("empty");break;case 2:if(Q.front=Q.rear)printf("empty");else printf("notempty");break;case 3:printf("你要入队的元素n");getc

24、har();scanf("%c",&x);En(Q,x);break;case 4:if(!Empty(Q)De(Q,e);Gethead(Q,a);printf("新队列头元素:");printf("%c",a);else printf("队列已空");break;case 5:Gethead(Q,a);printf("新队列头元素:");printf("%c",a);break;case 6:Print(Q);（4） 链队列系统规定的功能设计的算法有：置空队、判队

25、空、进队、出队、读队头元素1） 初始化和建立队列S1：定义结构体typedef struct QNodeint data;QNode *next;QNode,*QPtr;typedef struct Qlink QPtr front; QPtr rear;Qlink;/定义单链队列的链式存储结构S2:初始化int Initqueue(Qlink &Q) Q.front=Q.rear=(QPtr)malloc(sizeof(QNode); if(!Q.front)exit(OVERFLOW); Q.front->next=NULL; return OK;/构造空队列 S3：建立队列

26、 Qlink Setqueue(Qlink &Q) int i; Initqueue(Q); QPtr p; printf("请输入你的队列");char str100;gets(str);int n=strlen(str); for(i=0;i<n;i+) p=(QPtr)malloc(sizeof(QNode); p->data=stri; p->next=NULL; Q.rear->next=p; Q.rear=p; return Q;2） 置空队编写子函数Clear，使其可以实现置空队功能int Clear(Qlink &Q)

27、Q.front=Q.rear; return OK;3） 判队空S1：编写判断栈空的子函数Empty，使其实现判队空功能int Empty(Qlink &Q) if(Q.front=Q.rear) return TRUE; else return FALSE;S2：在主函数调用时根据队中指针位置判断输出内容if(Q.front=Q.rear)printf("empty");else printf("notempty");4） 进队S1：从客户端得到所要入队的元素printf("入队元素是:");scanf("%c&q

28、uot;,&x);S2：编写子函数En，使其可以实现将元素入栈功能int En(Qlink &Q,char e) QPtr p; p=(QPtr)malloc(sizeof(QNode); if(!p)exit(OVERFLOW); p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p;free(p); return OK;5） 出队S1：编写子函数De，删除队头元素int De(Qlink &Q,char &e)if(Q.front=Q.rear)return FALSE; QPtr p; p=Q

29、.front->next; Q.front->next=p->next;e=p->data; free(p); return OK;S2：编写子函数Gethead，使其可以得到队头元素，从而得到新的队头元素来确认成功int Gethead(Qlink Q,char &n) if(Q.front=Q.rear)return FALSE; n=Q.front->next->data; return OK;6）读队头元素调用函数Gethead就可以达到功能7） 功能选择用switch分析得到的m，根据不同的m进入不同的case，调用不同的函数printf(

30、"选择你需要的功能n"); printf("1置空队n2判队空n3进队n4出队n5读队头元素n");while(1)printf("选择你想要的功能n");scanf("%d",&m);switch(m)case 1:Clear(Q);printf("empty");break;case 2:if(Q.front=Q.rear)printf("empty");else printf("notempty");break;case 3:printf(&

31、quot;你要入队的元素n");getchar();scanf("%c",&x);En(Q,x);break;case 4:if(!Empty(Q)De(Q,e);Gethead(Q,a);printf("新队列头元素:");printf("%c",a);else printf("队列已空");break;case 5:Gethead(Q,a);printf("新队列头元素:");printf("%c",a);break;4.界面设计对这四个实验，每一个都提

32、示要求先输入字符串，之后弹出功能菜单，提示输入相应数字进行选择，进行完每一个功能后程序并不退出，直接进行下一次功能选择，顺序栈界面见图1，链栈界面见图2，循环队列见图3，链队列见图4（图1）（图2）（图3）（图4）5. 运行、测试与分析1）运行程序，按照提示输入字符串，弹出功能菜单，顺序栈如图5.1 ，链栈如图5.2，循环队列如图5.3，链队列如图5.4 （图5.1） （图5.2） （图5.3） （图5.4）2） 选择功能顺序栈：本次测试功能选择顺序为：输入字符串，判栈空，进栈，出栈，读栈顶，输出栈，判栈满，置空栈，判栈空，具体结果见下图如图6.1链栈：本次测试功能选择顺序为：输入字符串，判断

33、栈空，进栈，读栈顶，出栈，读栈顶，置空栈，判断栈空，具体结果见下图如图6.2循环队列：本次测试功能选择顺序为：输入字符串，判断队空，进队，读队头，输出循环队列，出队，读队头，置空队，判断队空，具体结果见下图如图6.3 链队列：本次测试的功能选择则顺序为：输入字符串，判队空，进队，读队头，出队，读队头，置空队，判队空，具体结果见下图如图6.4 （图6.1） （图6.2） （图6.3） （图6.4）6. 实验收获及思考（1）每次只能进行一次功能选择解决方法：在主函数前加入while(1)，就可以让程序一直运行（2）不能把相应的链或队列进行按照任意的次序进行功能选择解决办法：运用switch语句，可

34、以随意选择功能（3） 每次出栈（队）后不能判断出栈是否成功解决办法：在出栈后输出新的栈头元素或者输出栈或队中全部元素收获思考：（1） 了解了队列和栈的数据结构，通过比较分析，知道了栈和队列的相似点和不同点，加深了对基础知识的印象。（2） 学习到了在栈和队列中如何实现入队（栈），出队（栈），以及读取队头（栈顶元素），置空队（栈），判队（栈）空和输出队（栈）中全部元素的功能。（3） 复习了C语言，C+的相关知识，进一步熟悉了编程，养成了编程的好习惯。7. 附录（1） 顺序栈#include <string.h>#include <stdlib.h>#include <

35、stdio.h>#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 1#define ERROR 0#define OVERFLOW -1#define N 100typedef struct char *base; char *top; int stacksize;Sq;int InitSq(Sq&S) S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(Sq); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize

36、=STACK_INIT_SIZE; return OK; int Push(Sq&S,char e)if(S.top-S.base>=S.stacksize)S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char);if(!S.base) exit (OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Sq create(Sq &S)InitSq(S);printf("

37、;请输入你的栈");char str100;gets(str);int n=strlen(str);for(int i=0;i<n;i+)Push(S,stri);return S;int GetTop(Sq S,char &e)if(S.top=S.base) return ERROR;e=*(S.top-1);return e;int Pop(Sq&S,char e)if(S.top=S.base)return ERROR;e=*-S.top;return e;int Clear(Sq&S)while(S.top!=S.base)char e;Pop

38、(S,e);return OK;int Empty(Sq S)if(S.top=S.base)return OK;else return ERROR;int Print(Sq S) char *p,*q; p=S.top; q=S.base; if(p=q) return ERROR; while(p!=q) printf("%cn",*(p-1); p-; return OK;int T(Sq S) if(S.top-S.base>=S.stacksize) return OK; else return ERROR;int main() Sq S;create(S)

39、;int m;char a,x;printf("选择你想要的功能n");printf("1置空栈n2判断栈空n3进栈n4出栈n5读栈顶n6输出栈n7判栈满n");while(1)printf("选择你想要的功能n");scanf("%d",&m);getchar();switch(m)case 1:Clear(S);printf("Emptyn");break;case 2:if(Empty(S) printf("Emptyn"); else printf("

40、;NotEmpty"); break;case 3:printf("进栈元素是:");scanf("%c",&x);Push(S,x);Print(S);break;case 4:GetTop(S,a);Pop(S,a);Print(S);break;case 5:GetTop(S,a);printf("%cn",a);break;case 6:Print(S);break;case 7:if(T(S)printf("Yn"); else printf("Nn");break;

41、return OK;（2） 链栈#include<iostream>#include<string.h>#include<stdlib.h>#include<malloc.h>#define OK 1#define ERROR 0 #define TRUE 1#define FALSE 0typedef struct nodechar data;struct node *next;node;int Init(node* &h)h->next=NULL;return OK;int Empty(node* &h)if(h->

42、;next=NULL) return OK;else return FALSE;int Push(node* &h,char x)node *s;s=(node*)malloc(sizeof(node);s->data=x;s->next=h;h=s;return OK;int Pop(node* &h)char x;x=h->data;node *p;p=(node*)malloc(sizeof(node);p=h;h=h->next;free(p);return OK;int Gethead(node* &h,char a)if(h->

43、next=NULL)return FALSE ;a=h->data;printf("head:%cn",a); return OK;int Set(node* &h)int i; /Init(h); printf("请输入你的栈");char str100;gets(str);int n=strlen(str); for(i=0;i<n;i+)Push(h,stri);return OK;int Clear(node* &h)h->next=NULL;return OK;int main() node *h;h=(nod

44、e*)malloc(sizeof(node);Init(h);Set(h);int m;char a,x;printf("选择你想要的功能n");printf("1置空栈n2判断栈空n3进栈n4出栈n5读栈顶n");while(1)printf("选择你想要的功能n");scanf("%d",&m);getchar();switch(m)case 1:Clear(h);printf("Emptyn");break;case 2:if(Empty(h) printf("Empty

45、n");else printf("NotEmpty");break;case 3:printf("进栈元素是:");scanf("%c",&x);Push(h,x);break;case 4:Pop(h);Gethead(h,a);break;case 5:Gethead(h,a);break;return OK;（3） 循环队列#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<string.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define MAXQSIZE 100typedef struct int *base; int front; int rear;SqQueue;int Init(SqQueue &Q) Q.base=(int *)malloc(MAXQSIZE*sizeof(int); if(!Q.base)return (OVERFLOW