数据结构---栈和队列.doc

数据结构实验报告 实验二：栈和队列 专 业： 班 级： 姓 名： 学 号： 指导教师： 日 期： 2015.  实验二 栈和队列 实验目的： （1）掌握栈、队列的思想及其存储实现。 （2）掌握栈、队列的常见算法的程序实现。 （3）明确栈、队列均是特殊的线性表。 试验内容： 以下实验，1和2为必做内容，3和4选做一个。 1．栈的实现及应用 （1）采用链式存储实现栈的初始化、入栈、出栈操作。 （2）采用顺序存储实现栈的初始化、入栈、出栈操作。 （3）设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号‘（’、‘）’、‘[’、‘]’是否配对的C语言描述算法。 （4）在主函数中设计一个简单的菜单，分别测试上述算法。 #include iostream #include stdlib.h #include malloc.h #define STACK_INIT_MAXSIZE 100 #define STACKINCREAMENT 10 using 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; 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) { coutS.top-data ; pop1(S); } } typedef struct { int *top; int *base; int stacksize; }Stack; void InitStack(Stack S) { S.base=new int[STACK_INIT_MAXSIZE]; if(!S.base)exit(0); S.stacksize=STACK_INIT_MAXSIZE; S.top=S.base; int n; cout请输入数据以0结束endl; while(cinnn!=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.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.topendl;; } typedef struct SNode { char c; struct SNode *next; }LNode; typedef