《数据结构---栈和队列概要》由会员分享，可在线阅读，更多相关《数据结构---栈和队列概要（18页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告实验二：栈和队列专 业： 班 级： 姓 名： 学 号： 指导教师： 日 期： 2015. 实验二 栈和队列1、 实验目的： （1）掌握栈、队列的思想及其存储实现。 （2）掌握栈、队列的常见算法的程序实现。 （3）明确栈、队列均是特殊的线性表。2、 试验内容： 以下实验，1和2为必做内容，3和4选做一个。1栈的实现及应用（1）采用链式存储实现栈的初始化、入栈、出栈操作。（2）采用顺序存储实现栈的初始化、入栈、出栈操作。（3）设表达式以字符形式已存入数组En中，#为表达式的结束符，试写出判断表达式中括号（、）、是否配对的C语言描述算法。 （4）在主函数中设计一个简单的菜单，分别测试
2、上述算法。#include #include #include #define STACK_INIT_MAXSIZE 100#define STACKINCREAMENT 10using namespace std;typedef struct SNode1 int data; struct SNode1 *next;LNode1;typedef struct LNode1 *top; int length;Stack1;void InitStack1(Stack1 &S) S.top=NULL; S.length=0;void push1(Stack1 &S,int e) LNode1 *p
3、; p=(LNode1*)malloc(sizeof(LNode1); if(!p) exit(0); p-data=e; p-next=S.top; S.top=p; +S.length;bool pop1(Stack1 &S) if(!S.top) return false; else S.top=S.top-next; -S.length; return true; void PrintStack1(Stack1 &S) while(S.top) coutdata ; pop1(S); typedef struct int *top; int *base; int stacksize;S
4、tack;void InitStack(Stack &S) S.base=new intSTACK_INIT_MAXSIZE; if(!S.base)exit(0); S.stacksize=STACK_INIT_MAXSIZE; S.top=S.base; int n; cout请输入数据以0结束n&n!=0) *S.top+=n;void push(Stack &S,int e) if(S.top-S.base=S.stacksize) S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(int); if(!S
5、.base) exit(0); else S.top=S.base+S.stacksize; S.stacksize+=STACKINCREAMENT; *S.top+=e; void pop(Stack &S) if(S.top!=S.base) cout出栈元素为：*-S.topc=e; p-next=S.top; S.top=p; +S.length;bool pop3(Stack3 &S) if(!S.top) return false; else S.top=S.top-next; -S.length; return true; void PrintStack3(Stack3 &S)
6、 while(S.top) coutc ; pop3(S); void mainmenu() cout1.采用链式存储实现栈的初始化、入栈、出栈操作n; cout2.采用顺序存储实现栈的初始化、入栈、出栈操作n; cout3.设表达式以字符形式已存入数组En中，#为表达式的结束符，n; couti; if(i=1) couta&a!=0) push1(S1,a); PrintStack1(S1); coutendl; else if(i=2) InitStack(S2); pop(S2); int num; coutnum; push(S2,num); pop(S2); else cout请输
7、入表达式，以#结束：c&c!=#) if(c=(|c=) push3(S3,c); else flag=1; if(S3.length=0) cout不配对c=(&c=)|(S3.top-c=&c=) pop3(S3); else cout不配对n; return 0; if(flag=1&S3.length=0) cout配对endl; return 0;2. 队列的实现（1）采用链式存储实现队列的初始化、入队、出队操作。（2）采用顺序存储实现循环队列的初始化、入队、出队操作。 （3）在主函数中设计一个简单的菜单，分别测试上述算法。#include #include #define MAXQ
8、SIZE 100using namespace std;typedef struct QNode int data; struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr Front; QueuePtr Rear; int length;Queue;void InitQueue(Queue &Q) Q.Front=Q.Rear=new QNode; if(!Q.Front) exit(1); Q.Front-next=NULL; Q.length=0;void DestroyQueue(Queue &Q) while(Q.Front) Q.Rear=Q.Front-next; free(Q.Front); Q.Front=Q.Rear; void EnQueue(Queue &Q,int e) QueuePtr p; p=(QueuePtr )malloc(sizeof(QNode); if(!p) exit(1); p-
