实验二指导书

《实验二指导书》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验二：栈和队列的实现及应用实验任务书一、实验目的及要求(1).掌握栈、队列的定义、特性和ADT及其实现（顺序栈和链栈）；(2).掌握栈和队列的基本运算，如入栈(队列)、出栈(队列)等，熟悉操作的实现方法。(3).通过具体的应用实例，充分利用栈的后进先出特性，进一步熟悉和掌握栈在实际应用中的运用。二、实验内容（必选是每个同学必完成）(1).栈的顺序存储结构及实现；（必选）(2).栈的链接存储结构及实现；（必选）(3).链队列定义与实现。（必选）(4).循环队列存储结构及实现。（必选）(5).栈和队列应用：1）数制的转换问题

2、；（必选）2）应用栈判断一个表达式的括号是否匹配；（选做）3）表达式求解。（选做）4）打印杨辉三角（选做）三、实验准备(1)计算机设备；(2)程序调试环境的准备，如Devc++环境；(3)实验内容的算法分析与代码设计与分析准备。四、实验背景知识1.栈：栈是一种后进先出的线性结构，插入和删除都在表的一端进行，通常称这一端为栈顶，另一端为栈底，即插入的元素只能成为表尾元素，每次只能删除后插入的元素。利用栈的顺序存储表示实现堆栈的基本操作，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素

3、在顺序栈中的位置。一个较合理的做法是：先为栈分配一个基本容量。栈的链式存储是用一个链表表示栈，头指针指向栈顶元素，入栈与出栈均在表头进行，所以对栈的操作转换成对一个限制在表头操作的链表操作。2.队列：队列的实现方法类似于堆栈，不同的是队列是一种先进先出的线性表，利用循环队列实现队列的顺序表示的各种基本操作，需要两个分别指示队头和队尾的指针。注意队列判断空与判断满的方法。栈的应用：1）数制的转换问题：根据数制转换实现的思想（十进制数转换成N进制），辗转对数据对N进行求余，按余数从后向前排列即为结果。后求的余数先排列，符合栈的

4、LIFO特点。2）括号匹配：根据匹配的原则，后出现的右括号应与离它最近的左括号是一对，所以每次检测一对括号是否正确是时：是当出现右括号时，看最后出现的左括号是否与它是一对，如果是一对，继续向右扫描，一直到表达式结束（成功）或有一对不匹配（失败）时结束。3）算术表达式：算术表达式求值是栈应用的一个典型例子。首先要了解算术四则运算的规则，比较运算符之间的优先级别。算法的基本思想为：首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；依次读入表达式中的每个字符，判断是数还是运算符，进行判断。实现策略是结合课本中将一个表

5、达式转换成后缀式的算法与求后缀表达式值的算法的思想。即从运算符栈输出字符ch到后缀式的运算改成DoOperator(ch)。4）打印杨辉三角第i行共有i个元素，第一个和最后一个是1，其余i-2个元素是利用第i-1行元素求得，前面元素先求先被下一行元素利用求下一行元素，符合先进先出特点，利用队列实现，求第i行元素时要同时打印第i-1行元素。见书上代码。五、设计与实现1．栈的有关操作（1）栈的ADT见课本76见ADTStack{数据：零个或多个元素的线性序列(a0,a1,...an-1)，其最大允许长度为MaxSize。运算：

6、voidInitstack(S);voidClear(S);boolIsempty(S);boolIsfull(S);voidPush(s,x);voidPop(s,x);Elemtypegettop(s);}//ADTStack（2）顺序栈的定义及相关操作的实现1）顺序栈类型的定义#defineMAXSIZE10typedefstruct{Elemtype*elem;//或Elemtypeelem[MAXSIZE];inttop;}Seqstack;2）顺序栈基本函数的声明voidInitstack(Seqstack&s

7、);voidClear(Seqstack&s);boolIsempty(Seqstacks);boolIsfull(Seqstacks);voidPush(Seqstack&s,Elemtypee);voidPop(Seqstack&s,Elemtype&e);voidGettop(Seqstacks,Elemtype&e);voidInput(Seqstack&s);//调用Push函数实现voidOutput(Seqstacks);//将栈内元素从栈底到栈顶依次输出3）顺序栈基本函数的定义（见课本P78-P79）将下面

8、……自己完成voidInitstack(Seqstack&s){……}voidClear(Seqstack&s){……}boolIsempty(Seqstacks){……}boolIsfull(Seqstacks){……}voidPush(Seqstack&s,Elemtypee){……}voidPop