数据结构-C语言描述(第三版)第3章堆栈和队列.ppt

习 题 3 3－1 设A、B、C、D、E五个元素依次进栈(进栈后可立即出栈)，问能否得到下列序列。若能得到，则给出相应的Push和Pop序列；若不能，则说明理由。 (1) A, B, C, D, E； (2) A, C, E, B, D； (3) C, A, B, D, E； (4) E, D, C, B, A。 3－2 函数void PrintStack(Stack s)的功能是打印栈中全部元素，请在顺序和链接两种表示下分别实现之。 3－3 写一个函数，利用栈运算读入一行文本，并以相反的次序输出。 3－4 一维数组A中保存由字母(变量)、运算符(+、－、*、/ )和圆括号组成的算术表达式，圆括号允许嵌套。请编写函数，检查表达式中的括号是否配对。 3－5 为了充分利用空间，将两个栈共同存储在长度为n的一维数组中，共享数组空间。设计两个栈共享一维数组的存储表示方式，画出示意图。 3－6 给出定义习题3－5中的双栈的结构类型Dstack，并实现ADT 3－1中定义的各栈运算，允许在各栈运算定义中，增加用以指明当前对双栈中哪一个栈进行操作的参数。 3－7 编写一个主函数，由用户输入10个数，将所有的偶数压入第一个栈，所有的奇数压入第二个栈。 3－8 在单链表存储表示下，实现ADT 3－1 中定义的所有运算。编写一个主函数，执行下列操作序列：Push(s, a); 、Push(s, d); 、PrintStack(s); 、Pop(s); 、PrintStack(s); 。 3－9 函数void PrintQueue(Queue q)的功能是按照从队头到队尾的次序打印队列中的全部元素。请在循环队列结构上实现之。 3－10 请在单链表存储表示下，实现ADT 3－2中定义的所有队列运算，并在该链式结构上实现函数void PrintQueue(Queue q)。 3－11 请使用图2－12所示的带表头结点的单循环链表实现ADT 3－2，要求只使用一个指向队头的指针，不设队尾指针，并要求Append和Serve运算的时间复杂度均为O(1)。 3－12 写出下列表达式的前缀和后缀形式。 (1) (a+b)*c+d/(e+f)； (2) (a+b)*(c*d+e)－a*c。 3－13 利用栈将下列表达式转换为后缀形式，画出栈中元素的变化过程及中间结果。 (1) b*(d－c)+a； (2) a+b*(c－d)－e/f。 3－14 利用栈计算下列后缀表达式的值，画出栈中元素的变化过程，并指出栈中最多时有几个元素。 (1) 5 3 2 * 3 + 3 / +； (2) 1 2 3 - 4 +－5 1－* 3 * 。 3－15 设计一个递归函数，对长度为n的一维整数数组A，进行下列运算： (1) 求数组A的最大整数； (2) 求数组A中n个整数的平均值。 3－16 设计一个递归函数，在长度为n的一维数组A中查找指定元素x。若x在A中，则返回x在A中的下标，否则返回－1。 3－17 将本章3.5节的测试队列运算的菜单驱动方式的测试程序补充完整，并使用此程序测试队列运算。如果用于测试链式队列，此程序是否需要修改？若需要的话，应作何修改？ 3－18 根据本章3.5节中介绍的菜单驱动测试程序的设计方法，编写用于测试堆栈运算(顺序栈和链式栈)的菜单驱动方式的测试程序。 　　3－19 程序设计题。设计一个计算器程序，它可以重复接收用户输入的中缀算术表达式，给出计算结果。中缀表达式只允许一位十进制数为操作数以及加、减、乘、除四种运算符，还允许包括嵌套的圆括号。计算器程序先将中缀表达式转换成后缀表达式，然后计算后缀表达式的值，并向用户返回计算结果。 ＃号作为后缀表达式结束标记。需要提请注意的是本算法对后缀表达式没有错误检测功能，算法要求数组exp中存放的后缀表达式必须是合法的。主函数main引起后缀表达式求值算法Eval的执行。程序中使用了Clear（s）的函数调用，这意味着在表达式计算应用中，还需要增加一个栈运算void Clear（Stack * s），用于清除栈中元素。 程序3－5 后缀表达式求值 void DoOpe