数据结构栈与队列报告.doc

栈和队列上机实习 1、实验目的： （1）熟练掌握栈的逻辑结构和操作规则，能在相应的实际问题中正确选用该结构。 （2）熟练掌握栈的2种存储结构实现方法（顺序栈和链栈），两种存储结构和基本运算的实 现算法，注意栈空盒满的判断条件及它们的描述方法。 （3）熟练掌握队列的逻辑结构和操作规范，能在相应的实际问题中正确选用该结构。 （4）掌握循环队列与链队列两种存储结构的实现，熟练掌握各种队列基本运算的实现。 2、实验要求： （1）顺序栈的插入、删除，栈顶数据元素的读取。 （2）链栈的插入、删除，栈顶数据元素的读取。 （3）循环队列的插入、删除。 （4）链队列的插入、删除。 实验内容: 栈 （1）抽象数据类型定义 typedef struct { ElemType data[MaxSize]; //栈的空间大小为MaxSize int top; //设置栈顶指针 }SqStack; //栈的结构定义 在本次实验中，首先建立一个空栈，进入主程序后首先初始化栈为其分配空间，然后进入菜单选择界面，通过不同的数字输入，实现入栈，出栈，读取栈顶元素，显示栈的所有元素，栈的长度，释放栈等操作。 （2）存储结构定义及算法思想 在栈结构体的定义中，typedef int Typeelem 为整型，存储结构（入栈）如下： cina; s-top++; //在入栈是首先将栈顶指针向上加1 s-data[s-top]=a; //与数组赋值一样，直接赋值 //其他存储与此类似，都是直接赋值与数组的某一位 退栈函数模块： void Pop(SqStack * s){ //对指针的引用 if(s-top ==-1){ cout栈是空栈，不能退栈endl; //首先判断是否为空栈，若为空，则退出 return ; } cout退栈的元素为：s-data[s-top]endl; //显示退栈元素 s-top--; //栈顶元素减1，指向实际栈的最上面 } 显示栈所有元素函数模块： void DispStack (SqStack *s) { //从栈顶到栈底顺序显示所有元素 int i; cout栈的元素分别为：endl; for(i=s-top;i=0;i--){ couts-data[i] ; //同过循环实现实现从栈顶元素到栈底元素的遍历以输出 } coutendl; } 栈结构的入栈和退栈是两个相反的过程，先进后出，入栈是先让栈顶指针加1,指向未被赋值位置，然后进行赋值，退栈是先取出退栈元素，然后栈顶元素减1，指向推展后的实际栈顶。诸如读取栈顶元素，显示栈的元素，读取栈的长度，都是用过对栈顶指针实现相关操作。 实验结果与分析 循环队列 抽象数据类型定义 typedef struct { ElemType elem[Maxqsize]; //循环队列的长度为MaxSize int front,rear; //设置队列的头指针和尾指针 }SqQueue; //循环队列的结构体定义 在本次实验中，首先建立一个空队列，进入主程序后首先初始化队列为其分配空间，然后进入菜单选择界面，通过不同的数字输入，实现入队，出队，显示队列的所有元素，队列的长度，释放队列等操作。 （2）存储结构定义及算法思想 在队列结构体的定义中，typedef int Typeelem 为整型，存储（入队）结构如下： q-rear=(q-rear+1)%Maxqsize; //尾指针加1 q-elem[q-rear]=a; //将入队元素装到新的空尾部 在此队列的存储结构的实现：先让队尾指针进1，再将新的元素加入到队尾指针所指示的位置，因此，队尾指针指示实际的队尾位置，队头指针指示实际队头的前一位置，要想退出队头元素，必须先让队头指针进1，才能取出队头元素。 退队函数模块如下： void deQueue(SqQueue *q){ //对指针的引