实验四 栈与队列.doc

实验四 栈与队列 姓名 王艳青 学号 520713130135 日期 2009.12.9 实验题目 栈与队列 实验内容 1．采用链式存储实现栈的初始化、入栈、出栈操作。 2．采用顺序存储实现栈的初始化、入栈、出栈操作。 3．采用链式存储实现队列的初始化、入队、出队操作。 4．采用顺序存储实现循环队列的初始化、入队、出队操作。 5．在主函数中设计一个简单的菜单，分别测试上述算法。 *6．综合训练:1)利用栈实现表达式求值算法。 2)利用栈实现迷宫求解。 实验说明 1．基本要求：实现算法1、3或算法2、4即可。 2．类型定义 顺序栈示例 #define MAX 100 //栈的最大值 typedef　struct {ElemType *base； int top； }SqStack； 顺序队列示例 #define MAX 100 //队列的最大长度 typedef　struct {ElemType *base； int front，rear； }SqQueue； 3．算法6的每个子功能尽可能写成函数形式。 注意问题 1．重点理解栈、队列的算法思想，能够根据实际情况选择合适的存储结构。 2．注意算法6的各个函数之间值的传递情况。 3．栈、队列的算法是后续实验的基础（广义表、树、图、查找、排序等）。 实验源代码 头文件 #pragma once #define WIN32_LEAN_AND_MEAN // 从Windows 头中排除极少使用的资料 #include stdio.h #include tchar.h 栈文件 include string #include iostream using namespace std; typedef int DataType; struct SeqStack // 顺序栈类型定义 { int MAXNUM; // 栈中最大元素个数 int t; // t MAXNUM，指示栈顶位置，而不是元素个数 DataType *s; }; typedef struct SeqStack *PSeqStack; // 顺序栈类型的指针类型 // 算法题：创建一个空栈 PSeqStack createEmptyStack_seq(int m); // 算法题：判断栈是否为空 int isEmptyStack_seq(PSeqStack pastack); // 进栈(在栈中压入一个元素x) void push_seq(PSeqStack pastack, DataType x); // 出栈(删除栈顶元素) void pop_seq(PSeqStack pastack); // 取栈顶元素(当pastack所指的栈不为空时，求栈顶元素的值) DataType top_seq(PSeqStack pastack); struct Node; // 单链表结点 typedef struct Node *PNode; // 指向结点的指针类型 struct Node // 单链表结点定义 { DataType info; PNode link; }; struct LinkStack // 链接栈类型定义 { PNode top; // 指向栈顶结点 }; typedef struct LinkStack *PLinkStack; // 链接栈类型的指针类型 // 创建一个空链栈 PLinkStack createEmptyStack_link(void); // 判断单链形式栈是否为空栈 int isEmptyStack_link(PLinkStack plstack); // 进栈(在栈中压入一个元素) void push_link(PLinkStack plstack, DataType x); // 出栈 void pop_link(PLinkStack plstack); // 取栈顶元素 DataType top_link(PLinkStack plstack); struct SeqQueue // 顺序队列类型定义 { int MAXNUM; // 队列中最大元素个数 int f, r; DataType *q; }; typedef SeqQueue *PSeqQueue; // 顺序队列类型的指针类型 // 创建一个空队列 PSeqQueue createEmptyQueue_seq(int