实验二指导书.doc

实验二：栈和队列的实现及应用 实验任务书一、实验目的及要求(1).掌握栈、队列的定义、特性和ADT及其实现（顺序栈和链栈）；(2).掌握栈和队列的基本运算，如入栈(队列)、出栈(队列)等，熟悉操作的实现方法。(3).通过具体的应用实例，充分利用栈的后进先出特性，进一步熟悉和掌握栈在实际应用中的运用。二、实验内容（必选是每个同学必完成）(1).栈的顺序存储结构及实现；（ 必选）(2).栈的链接存储结构及实现；（ 必选） (3).链队列定义与实现。（ 必选）(4).循环队列存储结构及实现。（ 必选）(5).栈和队列应用：1）数制的转换问题；（必选） 2）应用栈判断一个表达式的括号是否匹配；（选做）3）表达式求解。（选做）4）打印杨辉三角（选做）三、实验准备(1) 计算机设备；(2) 程序调试环境的准备，如Devc+环境；(3) 实验内容的算法分析与代码设计与分析准备。四、实验背景知识1. 栈：栈是一种后进先出的线性结构，插入和删除都在表的一端进行，通常称这一端为栈顶，另一端为栈底，即插入的元素只能成为表尾元素，每次只能删除后插入的元素。利用栈的顺序存储表示实现堆栈的基本操作，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。一个较合理的做法是：先为栈分配一个基本容量。栈的链式存储是用一个链表表示栈，头指针指向栈顶元素，入栈与出栈均在表头进行，所以对栈的操作转换成对一个限制在表头操作的链表操作。2.队列：队列的实现方法类似于堆栈，不同的是队列是一种先进先出的线性表，利用循环队列实现队列的顺序表示的各种基本操作，需要两个分别指示队头和队尾的指针。注意队列判断空与判断满的方法。栈的应用：1）数制的转换问题：根据数制转换实现的思想（十进制数转换成N进制），辗转对数据对N进行求余，按余数从后向前排列即为结果。后求的余数先排列，符合栈的LIFO特点。2）括号匹配： 根据匹配的原则，后出现的右括号应与离它最近的左括号是一对，所以每次检测一对括号是否正确是时：是当出现右括号时，看最后出现的左括号是否与它是一对，如果是一对，继续向右扫描，一直到表达式结束（成功）或有一对不匹配（失败）时结束。3）算术表达式： 算术表达式求值是栈应用的一个典型例子。首先要了解算术四则运算的规则，比较运算符之间的优先级别。算法的基本思想为：首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；依次读入表达式中的每个字符，判断是数还是运算符，进行判断。实现策略是结合课本中将一个表达式转换成后缀式的算法与求后缀表达式值的算法的思想。即从运算符栈输出字符ch到后缀式的运算改成DoOperator(ch)。4）打印杨辉三角 第i行共有i个元素，第一个和最后一个是1，其余i-2个元素是利用第 i-1行元素求得，前面元素先求先被下一行元素利用求下一行元素，符合先进先出特点，利用队列实现，求第i行元素时要同时打印第i-1行元素。见书上代码。5、 设计与实现1栈的有关操作（1）栈的ADT见课本76见 ADT Stack 数据：零个或多个元素的线性序列(a0,a1,.an-1)，其最大允许长度为MaxSize。运算： void Initstack(S); void Clear(S); bool Isempty(S); bool Isfull(S); void Push(s,x); void Pop(s,x); Elemtype gettop(s); / ADT Stack （2）顺序栈的定义及相关操作的实现1）顺序栈类型的定义#define MAXSIZE 10typedef struct Elemtype *elem;/ 或Elemtype elemMAXSIZE;int top;Seqstack;2）顺序栈基本函数的声明void Initstack(Seqstack &s);void Clear(Seqstack &s);bool Isempty(Seqstack s);bool Isfull(Seqstack s);void Push(Seqstack &s,Elemtype e);void Pop(Seqstack &s,Elemtype &e);void Gettop(Seqstack s,Elemtype &e);void Input(Seqstack &s);/调用Push函数实现void Output(Seqstack s); /将栈内元素从栈底到栈顶依次输出3）顺序栈基本函数的定义（见课本P78-P79）将下面自己完成void Initstack(Seqstack &s) void Clear(Seqstack &s)bool Isempty(Seqstack s)bool Isfull(Seqstack s)void Push(Seqstack &s,Elemtype e)void Pop(Seqstack &s,Elemtype &e)void Gettop(Seqstack s,Elemtype &e)void Input(Seqstack &s)/调用Push函数实现void Output(Seqstack s) /将栈内元素从栈底到栈顶依次输出4）主函数定义 （建议用菜单驱动程序）int main 定义一个顺序栈 依次调用基本函数测试5）测试数据及测试结果/将栈的输入、输出、取栈顶元素、判断栈空/满的截图给出参考界面：（3）链栈的定义及相关操作的实现/请同学参考顺序栈的定义、实现及测试主程序完成链栈的定义、实现及测试主程序完成1）5）部分2队列的有关操作（1）队列的ADT ADT Queue 数据：零个或多个元素的线性序列(a0,a1,.an-1)，其最大允许长度为MaxSize。运算：void Initqueue(Seqqueue &Q);void Clear(Seqqueue &Q);bool Isempty(Seqqueue Q);bool Isfull(Seqqueue Q);void Enqueue(Seqqueue &Q,Elemtype e);void Delqueue(Seqqueue &Q,Elemtype &e);void Gethead(Seqqueue Q,Elemtype &e); ADT Queue （2） 顺序队列的定义及相关操作的实现/请同学参考顺序栈的定义、实现及测试主程序完成顺序队列的定义、实现及测试主程序完成1）5）部分参考界面如下。（3）链队列的定义及相关操作的实现/请同学参考顺序栈的定义、实现及测试主程序完成链队列的定义、实现及测试主程序完成1）5）部分3栈和队列的应用：示例：利用栈实现判断一个串是否为回文：#include #include #include using namespace std;bool huiwen(char *str);int main(int argc, char *argv) char str80; coutstr; if(huiwen(str) coutstr is huiwen!n; else coutstrisnt huiwen!n; system(PAUSE); return 0;bool huiwen(char *str) stack s; int len=strlen(str),i; i=0; while(ilen) /str所有字符入栈 s.push(stri); i+; i=0; while(!s.empty() /从栈顶到栈底所有元素依次与str各个字符比较是否相等，即str首尾元素比较 if(stri=s.top() s.pop();i+; else return false ; return tr