实验2 栈和队列.docVIP

山东工商学院 《数据结构》实验指导及报告书 2012 / 2013 学年 第 1 学期 姓 名： 学 号： 班 级 指导教师： 信电学院 2012、11、20 实验二 栈和队列 一、实验目的 1、掌握栈的结构特性及其入栈，出栈操作； 2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。 二、实验预习 说明以下概念 1、顺序栈：即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。top为栈顶指针，其初值指向栈底，top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减1，因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。 2、链栈：栈的链式表示，采用链式存储结构。 3、循环队列：环状的队列空间。比顺序队列的优势所在是可以继续在队尾插入新的元素，不会因数组越界而导致程序代码被破坏。 4、链队：用链表表示的队列。 三、实验内容和要求 1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列1 2 3 4 5 e，运行结果如下所示。 #includestdio.h #includemalloc.h #define ERROR 0 #define OK 1 #define STACK_INT_SIZE 10 /*存储空间初始分配量*/ #define STACKINCREMENT 5 /*存储空间分配增量*/ typedef int ElemType; /*定义元素的类型*/ typedef struct{ ElemType *base; ElemType *top; int stacksize; /*当前已分配的存储空间*/ }SqStack; int InitStack(SqStack *S); /*构造空栈*/ int push(SqStack *S,ElemType e); /*入栈*/ int Pop(SqStack *S,ElemType *e); /*出栈*/ int CreateStack(SqStack *S); /*创建栈*/ void PrintStack(SqStack *S); /*出栈并输出栈中元素*/ int InitStack(SqStack *S){ S-base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType)); if(!S-base) return ERROR; S-top=S-base; S-stacksize=STACK_INT_SIZE; return OK; }/*InitStack*/ int Push(SqStack *S,ElemType e){ if (S-top-S-base=S-stacksize) { //当前存储空间已满，需增加容量: S-base=(ElemType *) realloc( S-base, (S-stacksize+STACKINCREMENT) * sizeof(ElemType) ); S-top=S-base+S-stacksize; S-stacksize+=STACKINCREMENT; } *S-top++=e; //压入数据元素e，top+1 return 1; }/*Push*/ int Pop(SqStack *S,ElemType *e){ if (S-top!=S-base) { *e=*--S-top; return 1; } else return 0; }/*Pop*/ int CreateStack(SqStack *S){ int e; if(InitStack(S)) printf(Init Success!\n); else{ printf(Init Fail!\n); return ERROR; } printf(input data:(Terminated by inputing a character)\n); while(scanf(%d,e)) Push(S,e); return OK; }/*CreateStack*/ void PrintStack(SqStack *S){ ElemT