实验二栈和队列模拟包含源码.doc

实验二 栈和队列的模拟操作一、实验目的1、理解栈和队列的特点2、掌握栈的顺序和链式存储结构及基本操作（初始化、判空、取栈顶元素、进栈、出栈）3、掌握队列的顺序和链式存储结构以及基本操作（初始化、判空、取栈顶元素、入队、出队）4、理解栈与递归的实现及队列的应用二、实验内容1、括号匹配的检验1.1问题描述：编写一个程序，检查一个表达式中的花括号、方括号和圆括号是否配对（利用栈实现）。输入：一个括号序列，例如：( ( ) ( ) )或者 ( ( ) ) 输出：匹配括号对或者不匹配的结果（优先配对的顺序），例如( ) ( ) ( ) 括号序列匹配 或者 ( ) ( ) 括号序列不匹配1.2 具体操作的函数模块功能说明：（1）栈的存储结构（顺序存储结构）typedef struct SElemType *base;SElemType *top;int stacksize;SqStack;/顺序栈（2）初始化一个空栈函数：void InitStack(SqStack *S)（3）入栈函数：void Push(SqStack *S, SelemType x)/插入x为新的栈顶元素（4）出栈函数：ElemType Pop(SqStack *S) /若栈不空，则删除栈的栈顶元素，用e返回其值，并返回OK，否则返回ERROR（5）匹配检验：括号匹配的方法，就是对给定的字符串依次检验：若是左括号，入栈；若是右括号，出栈一个左括号判断是否与之匹配；是其他字符，不检验。检验到字符串尾，还要检查栈是否为空。只有栈空，整个字符串才是括号匹配的。函数：void check(SqStack S,char *p);/对于*p指向的字符串序列，输出其中匹配的括号对（6）主函数中实现输入和输出功能SqStack S; /定义一个顺序栈char chMAXNUM;/声明一个存储表达式的数组1.3实验步骤：1.3.1 程序头文件及宏定义等#include#include#define MAXNUM 15#define INIT_SIZE 50#define INCREMENT 20#define TRUE 1#define FALSE 0typedef char ElemType ;/*定义顺序栈的存储结构*/typedef struct ElemType *base;ElemType *top;int stacksize;SqStack;/顺序栈源程序主函数如下：/*实现表达式中括号匹配的检验*/void main()/*函数声明*/void InitStack(SqStack *S);void Push(SqStack *S,ElemType e);ElemType Pop(SqStack *S);int StackEmpty(SqStack S);void check(SqStack S,char *p);SqStack S; char chMAXNUM;InitStack(&S);printf(请输入表达式:n); gets(ch); /输入要检验的表达式check(S,ch);/调用括号匹配检验函数基本操作函数定义部分：（补充完整）1.4 运行结果：图2.1括号匹配检验演示 2、队列的各种基本操作2.1问题描述：编写一个程序实现顺序队列的基本操作，并在此基础上设计一个主程序，完成如下功能：初始化队列、建立队列、判空、取队头元素、入队、出队运算。2.2具体操作的函数模块功能说明：（1）顺序队列的存储结构typedef struct Elemtype queueMAXNUM;/MAXNUM为最大队列长度int front;/队头指针int rear;/队尾指针，若队列不空，指向队列尾元素的下一个位置SqQueue;/顺序队列（2）初始化队列函数 ：Status InitQueue(SqQueue *Q)/实现队列的初始化（3）入队列函数 Status EnQueue(SqQueue *Q，QElemtype x)/插入元素x为Q的新的队尾元素（4）出队列函数 Status DeQueue(SqQueue *Q)/若队列不空，则删除队列的队头元素，用e返回其值，并返回OK，否则返回ERROR(5)判空函数：Status Empty(SqQueue *Q) /判断队列是否为空(6)取队头元素函数：Status GetHead(SqQueue *Q) /若队列不空，用e返回队列的队头元素，并返回OK，否则返回ERROR（7）建立一个顺序队列函数：void Creat_SqQueue(SqQueue *Q)（8）宏定义和头文件等#include #include #include #define MAXNUM 100typedef int ElemType;typedef int Status;2.3实验步骤：源程序主函数如下：2.4运行结果：图2.2 队列的基本操作演示 三、问题讨论 1、解释顺序队列中的三种溢出现象：“下溢”、“真上溢”、“假上溢”2、栈的两种存储结构在判别栈空与栈满时，所依据的条件有何不同？四、实验心得（此页以后的内容不包含在实验报告内）附：程序源代码一/*功能：括号匹配的检验问题描述：编写一个程序，检查一个表达式中的花括号、方括号和圆括号是否配对（利用栈实现）。函数说明：（1）栈的存储结构（顺序存储结构）typedef struct SElemType *base;SElemType *top;int stacksize;SqStack;/顺序栈（2）初始化一个空栈函数：void InitStack(SqStack *S)（3）入栈函数：void Push(SqStack *S, SelemType e)/插入e为新的栈顶元素（4）出栈/若栈不空，则删除栈的栈顶元素，用e返回其值，并返回OK，否则返回FALSE函数：char Pop(SqStack *S, SelemType &e) （5）匹配检验函数：void check(SqStack *S,char *str);/对于字符串序列str，输出其中匹配的括号对*/#include#include#define MAXNUM 15#define INIT_SIZE 50#define INCREMENT 20#define TRUE 1#define FALSE 0typedef char ElemType ;/*定义顺序栈的存储结构*/typedef struct ElemType *base;ElemType *top;int stacksize;SqStack;/顺序栈/*初始化顺序栈*/void InitStack(SqStack *S)S-base = (ElemType *)malloc(INIT_SIZE*sizeof(ElemType);/初始申请分配50个数据元素大小的空间if(!S-base) /存储分配失败printf(Eorror);S-stacksize = INIT_SIZE;S-top = S-base;/*入栈*/ void Push(SqStack *S,ElemType x)if(S-top - S-base) stacksize)*S-top = x;S-top+;elseprintf(Overflow!n);/*出栈*/ElemType Pop(SqStack *S)ElemType e;if(S-top!=S-base)-(S-top);e = *(S-top);/printf(以前的栈顶数据元素%d出栈操作后已经被删除n,e);return e;elseprintf(Underflow!n);return FALSE;/*判空*/int StackEmpty(SqStack S) if(S.top = S.base) return TRUE; else return FALSE; /StackEmpty /*括号匹配检验*/void check(SqStack S,char *p) while(*p)switch(*p) case (: /左小括号入栈Push(&S,*p);p+;break; case : /左中括号入栈Push(&S,*p); p+;break; case :/左大括号入栈Push(&S,*p);p+; /指向下一个字符break;case ): /判断右小括号与栈顶元素是否匹配if(!StackEmpty(S)/Pop(&S,e);/if(*p=)&e!=(|*p=)&e!=()if(Pop(&S)!= ()/栈顶元素不是左小括号，则不匹配，printf(左右小括号不配对n);exit(FALSE);else printf( )n);p+;break;else printf(缺乏左小括号n);exit(FALSE);case :/判断右中括号与栈顶元素是否匹配if(!StackEmpty(S) /Pop(&S,e);/if(*p=)&e!=(|*p=&e!=)if(Pop(&S)!=) printf(左右中括号不配对n);exit(FALSE); elsep+;printf( n);break;else printf(缺乏左中括号n);exit(FALSE);case :/判断右大括号与栈顶元素是否匹配if(!StackEmpty(S) /Pop(&S,e);if(Pop(&S)!=) printf(左右大括号不配对n);exit(FALSE); elsep+;printf( n);break;else printf(缺乏左大括号n);exit(FALSE);default: p+;if(StackEmpty(S)printf(括号序列匹配n);else printf(括号序列不匹配，缺乏左括号n); /*实现表达式中括号匹配的检验*/void main()void InitStack(SqStack *S);void Push(SqStack *S,ElemType e);ElemType Pop(SqStack *S); int StackEmpty(SqStack S);void check(SqStack S,char *p);SqStack S; char chMAXNUM;InitStack(&S);printf(请输入表达式:n); gets(ch); /输入要检验的表达式check(S,ch);/调用括号匹配检验函数程序源代码二：程序源代码二：/*程序实现顺序队列的基本操作，并在此基础上设计一个主程序，完成如下功能：初始化队列、建立队列、判空、取队头元素、入队、出队运算。具体操作的函数模块功能说明：（1）顺序队列的存储结构typedef struct Elemtype queueMAXNUM;/MAXNUM为最大队列长度int front;/队头指针int rear;/队尾指针，若队列不空，指向队列尾元素的下一个位置SqQueue;/顺序队列（2）初始化队列函数 ：Status InitQueue(SqQueue *Q)/实现队列的初始化（3）入队列函数 Status EnQueue(SqQueue *Q，QElemtype x)/插入元素x为Q的新的队尾元素（4）出队列函数 Status DeQueue(SqQueue *Q)/若队列不空，则删除队列的队头元素，用e返回其值，并返回OK，否则返回ERROR(5)判空函数：Status Empty(SqQueue *Q) /判断队列是否为空(6)取队头元素函数：Status GetHead(SqQueue *Q) /若队列不空，用e返回队列的队头元素，并返回OK，否则返回ERROR（7）建立一个顺序队列函数：void Creat_SqQueue(SqQueue *Q) */#include #include #define MAXNUM 100#define Elemtype int#define TRUE 1#define FALSE 0typedef structElemtype queueMAXNUM; int front; int rear;SqQueue; /*队列初始化*/int InitQueue(SqQueue *Q) if(!Q)return FALSE;Q-front=-1;Q-rear=-1;return TRUE; /*入队*/int EnQueue(SqQueue *Q, Elemtype x) if(Q-rear=MAXNUM-1) return FALSE;Q-rear+;Q-queueQ-rear=x;return TRUE;/*出队*/Elemtype DeQueue(SqQueue *Q)Elemtype x;if (Q-front=Q-rear) return FALSE;x=Q-queue+Q-front;return x;/*判断队列是否为空*/int Empty(SqQueue *Q)if(Q-front=Q-rear)return TRUE;return FALSE; /*取队头元素*/int GetHead(SqQueue *Q)if (Q-front=Q-rear) return 0; return(Q-queueQ-front+1); /*遍历队列*/void display(SqQueue *Q)int s;s=Q-front;if (Q-front=Q-rear)printf(队列空!n);elseprintf(n顺序队列依次为：);while(srear)s=s+1;printf(%d queues);printf(n); printf(顺序队列的队尾元素所在位置:rear=%dn,Q-rear); printf(顺序队列的队头元素所在位置:front=%dn,Q-front);/*建立顺序队列*/void Creat_SqQueue(SqQueue *Q)int n,i,m;printf(请输入将要入顺序队列的长度:n); scanf(%d,&n); printf(n请依次输入入顺序队列的元素值:n);for (i=0;in;i+) scanf(%d,&m);EnQueue(Q,m);void main() SqQueue *head; int x,y,z,select; head=(SqQueue*)malloc(siz