新编数据结构习题与解析(第2版)

本书内容包括概论、线性表、栈和队列、串、数组和稀疏矩阵、树和二叉树、图、查找和排序，附录中给出书中部分算法清单、全国计算机专业数据结构联考大纲、部分练习题的参考答案

章绪论
1．1知识点1： 数据结构的基本概念
1．1．1要点归纳
1．1．2例题解析
1．2知识点2： 算法和算法分析
1．2．1要点归纳
1．2．2例题解析
第2章线性表
2．1知识点1： 线性表的基本概念
2．1．1要点归纳
2．1．2例题解析
2．2知识点2： 顺序表的算法
2．2．1要点归纳
2．2．2例题解析
2．3知识点3： 单链表的算法
2．3．1要点归纳
2．3．2例题解析
2．4知识点4： 双链表的算法
2．4．1要点归纳
2．4．2例题解析
2．5知识点5： 循环链表的算法
2．5．1要点归纳
2．5．2例题解析
第3章栈和递归
3.1知识点1： 栈的基本概念
3.1.1要点归纳
3.1.2例题解析
3.2知识点2： 顺序栈的算法
3.2.1要点归纳
3.2.2例题解析
3.3知识点3： 链栈的算法
3.3.1要点归纳
3.3.2例题解析
3.4知识点4： 递归
3.4.1要点归纳
3.4.2例题解析
第4章队列
4.1知识点1： 队列的基本概念
4.1.1要点归纳
4.1.2例题解析
4.2知识点2： 顺序队的算法
4.2.1要点归纳
4.2.2例题解析
4.3知识点3： 链队的算法
4.3.1要点归纳
4.3.2例题解析
第5章串
5．1知识点1： 串的基本概念
5．1．1要点归纳
5．1．2例题解析
5．2知识点2： 顺序串的算法
5．2．1要点归纳
5．2．2例题解析
5．3知识点3： 链串的算法
5．3．1要点归纳
5．3．2例题解析
5．4知识点4： 模式匹配的算法
5．4．1要点归纳
5．4．2例题解析
第6章数组和稀疏矩阵
6．1知识点1： 数组和特殊矩阵
6．1．1要点归纳
6．1．2例题解析
6．2知识点2： 稀疏矩阵
6．2．1要点归纳
6．2．2例题解析
第7章树和二叉树
7．1知识点1： 树的基本概念
7．1．1要点归纳
7．1．2例题解析
7．2知识点2： 二叉树的基本概念
7．2．1要点归纳
7．2．2例题解析
7．3知识点3： 二叉树的算法
7．3．1要点归纳
7．3．2例题解析
7．4知识点4： 线索二叉树
7．4．1要点归纳
7．4．2例题解析
7．5知识点5： 哈夫曼树
7．5．1要点归纳
7．5．2例题解析
7．6知识点6： 树算法设计
7．6．1要点归纳
7．6．2例题解析
第8章广义表
8.1知识点1： 广义表的基本概念
8.1.1要点归纳
8.1.2例题解析
8.2知识点2： 广义表的算法设计
8.2.1要点归纳
8.2.2例题解析
第9章图
9.1知识点1： 图的基本概念
9.1.1要点归纳
9.1.2例题解析
9.2知识点2： 图的遍历算法
9.2.1要点归纳
9.2.2例题解析
9.3知识点3： 最小生成树
9.3.1要点归纳
9.3.2例题解析
9.4知识点4： 最短路径
9.4.1要点归纳
9.4.2例题解析
9.5知识点5： AOV网和拓扑排序
9.5.1要点归纳
9.5.2例题解析
9.6知识点6： AOE网与关键路径
9.6.1要点归纳
9.6.2例题解析
0章查找
10．1知识点1： 线性表的查找
10．1．1要点归纳
10．1．2例题解析
10．2知识点2： 树表的查找
10．2．1要点归纳
10．2．2例题解析
10．3知识点3： 哈希表的查找
10．3．1要点归纳
10．3．2例题解析
1章内排序
11.1知识点1： 插入排序算法
11.1.1要点归纳
11.1.2例题解析
11.2知识点2： 选择排序算法
11.2.1要点归纳
11.2.2例题解析
11.3知识点3： 交换排序算法
11.3.1要点归纳
11.3.2例题解析
11.4知识点4： 归并排序算法
11.4.1要点归纳
11.4.2例题解析
11.5知识点5： 基数排序算法
11.5.1要点归纳
11.5.2例题解析
2章外排序和文件
12.1知识点1： 外排序
12.1.1要点归纳
12.1.2例题解析
12.2知识点2： 文件
12.2.1要点归纳
12.2.2例题解析
附录A四份重点大学本科“数据结构”科目考试试题
试题1
试题1参考答案
试题2
试题2参考答案
试题3
试题3参考答案
试题4
试题4参考答案
附录B2012―2018年全国计算机专业硕士学位研究生入学考试数据结构
部分试题视频讲解
附录C书中视频对应二维码汇总表

    第3章栈和递归
     视频讲解
     视频讲解
     基本知识点栈和递归的定义、栈的特点及其与线性表的异同，顺序栈和链栈的组织方法，栈满、栈空的判断方法及其描述。
     重点在顺序栈和链栈上基本运算的实现算法，递归算法设计，利用栈实现递归算法到非递归算法的转换。
     难点递归算法设计，灵活运用栈设计复杂的算法，利用栈实现递归算法到非递归算法的转换。
     3.1知识点1： 栈的基本概念
     3.1.1要点归纳
     1. 栈的定义
     栈是一种只能在一端进行插入或删除操作的线性表，表中允许进行插入、删除操作的一端称为栈顶。栈顶的当前位置是动态的，栈顶的当前位置由一个称为栈顶指针的位置指示器来指示。表的另一端称为栈底。当栈中没有数据元素时，称为空栈。栈的插入操作通常称为进栈或入栈，栈的删除操作通常称为退栈或出栈。如图3.1所示为元素进栈和退栈操作，可见栈底端保持不变，栈很好经常发生变化。
     图3.1元素进栈和退栈操作
     注意： 栈中元素之间的逻辑关系也是线性关系，只是插入和删除运算不同于线性表。
     2. 栈的特点
     栈的主要特点是“后进先出”，即后进栈的元素先出栈。栈也称为后进先出表。
     3. 栈的基本运算
     栈的基本运算如下。
     (1) InitStack(&st)： 初始化栈，构造一个空栈st。
     (2) StackEmpty(st)： 判断栈是否为空，若栈st为空，则返回真； 否则返回假。
     (3) Push(&st，x)： 进栈。将元素x插入栈st中作为栈顶元素。
     (4) Pop(&st，&x)： 出栈。从栈st中退出栈顶元素，并将其值赋给x。
     (5) GetTop(st，&x)： 取栈顶元素。返回当前的栈顶元素，并将其值赋给x。
     4. 栈的存储结构
     栈有两种主要的存储结构，即顺序栈和链栈。前者采用顺序存储结构表示栈，后者采用链式存储结构表示栈，它们之间的区别与第2章介绍的顺序表和链表类似。
     3.1.2例题解析
     1. 单项选择题
     【例3？1？1】一个栈的进栈序列是a、b、c、d、e，则栈不可能输出的序列是。
     A. edcbaB. decbaC. dceabD. abcde
     答： 栈的特点是优选后出。选项A，a、b、c、d、e进栈，e、d、c、b、a出栈； 选项B，a、b、c、d进栈，d出栈，e进栈，e出栈，c、b、a依次出栈； 选项C，a、b、c、d进栈，d出栈，c出栈，e进栈，e出栈，此时栈中从栈底到栈顶为a、b，不可能a先出栈，所以C是不可能的输出序列； 选项D，a进栈，a出栈，b进栈，b出栈，c进栈，c出栈，d进栈，d出栈，e进栈，e出栈。本题答案为C。
     【例3？1？2】已知一个栈的进栈序列是（1，2，3，…，n），其输出序列的个元素是i(1≤i≤n)，则第j(1≤j≤n)个出栈元素是。
     A. iB. n-iC. j-i+1D. 不确定
     答： 根据栈的特点，输出序列的个元素是i，无法确定第j个出栈的元素。本题答案为D。
     【例3？1？3】已知一个栈的进栈序列是（1，2，3，…，n），其输出序列是p1，p2，…，pn，若p1=n，则pi的值为。
     A. iB. n-iC. n-i+1D. 不确定
     答： 当p1=n时，输出序列是专享的，元素依次为n、n-1、…、3、2、1，则p2=n-1，p3=n-2，…，pn=1，可推断出pi=n-i+1，所以本题答案为C。
     说明： n(n>1)个不同元素经过一个栈的出栈序列是不专享的，有1n+1Cn2n个出栈序列。但这n个元素连续进栈产生的出栈序列是专享的，此时的出栈序列恰好是进栈序列的反序。
     【例3？1？4】设n个元素的进栈序列是（p1，p2，p3，…，pn），其输出序列是（1，2，3，…，n），若pn=1，则pi(1≤i≤n-1)的值是。
     A. n-i+1B. n-iC. iD. 有多种可能
     答： 当pn=1时，进栈序列是（p1，p2，p3，…，1），由输出序列可知，p1，p2，p3，…，pn依次进栈，然后依次出栈，即pn-1=2，pn-2=3，…，p1=n，也就是说pi=n-i+1，所以本题答案为A。
     说明： 当出栈序列的个元素为进栈序列的很后一个元素时，进栈出栈的操作是专享的。
     【例3？1？5】设n个元素进栈序列是（1，2，3，…，n），其输出序列是（p1，p2，…，pn），若p1=3，则p2的值为。
     A. 一定是2B. 一定是1C. 不可能是1D. 以上都不对
     答： 当p1=3时，说明1、2、3优选栈，3立即出栈，此时栈的状态如图3.2所示，这时2可出栈，也可能让4进栈后再出栈，也可以让4进栈、5进栈后再出栈，……，所以p2可能是2，也可能是4、……或n，但一定不能是1，所以本题答案为C。
     【例3？1？6】设n个元素的进栈序列是（p1，p2，p3，…，pn），其输出序列是（1，2，3，…，n），若p3=1，则p1的值。
     A. 可能是2B. 一定是2C. 不可能是2D. 不可能是3
     答： 当p3=1时，进栈序列是（p1，p2，1，…），由输出序列可知，p1、p2、p3都进栈，p3出栈，如图3.3所示，此后紧跟着出栈的一个元素就是2，而p1不可能紧跟着p3出栈，因为栈中前面有p2，因此p1不可能是2，所以本题答案为C。
     图3.2元素3出栈后的情况
     图3.3元素p3出栈后的情况
     【例3？1？7】设n个元素进栈序列是（p1，p2，p3，…，pn），其输出序列是（1，2，3，…，n），若p3=3，则p1的值。
     A. 可能是2B. 一定是2C. 不可能是1D. 一定是1
     答： 当p3=3时，进栈序列是（p1，p2，3，…），由输出序列可知，只有以下两种情况。
     (1) p1进栈后出栈，p2进栈后出栈，即p1=1，p2=2，p3进栈后出栈，这种情况下p1=1。
     图3.4p1、p2产生1、2的出栈序列
     (2) p1、p2都进栈后都出栈，即p2=1，p1=2，然后p3进栈再出栈，这种情况下p1=2。
     实际上本题就是由进栈序列p1、p2产生出栈序列1、2，如图3.4所示，所以p1可能是1，也可能是2。所以本题答案为A。
     【例3？1？8】设有5个元素的进栈序列是（a，b，c，d，e），其输出序列是（c，e，d，b，a），则该栈的容量至少是。
     A. 1B. 2C.3D. 4
     答： 进栈序列是（a，b，c，d，e），输出序列是（c，e，d，b，a）的操作依次是a进、b进、c进、c出、d进、e进、e出、d出、b出及a出，所以栈中的很多元素为4个。本题答案为D。
     2. 填空题
     【例3？1？9】一个栈的输入序列是12345，输出序列为12345，其进栈出栈的操作为。
     答： 1进栈，1出栈，2进栈，2出栈，3进栈，3出栈，4进栈，4出栈，5进栈，5出栈。
     【例3？1？10】进栈序列是1，2，…，n，则可能的出栈序列有种。
     答： 1n+1Cn2n。
     提示： 以下三类问题的答案是相同的： (1)求1~n为进栈序列的出栈序列个数； (2)求由n个不相同元素构成的不同形态的二叉树个数； (3)求n个不相同元素的先序序列构成不同形态的二叉树个数。
     3. 判断题
     【例3？1？11】判断以下叙述的正确性。
     (1) 栈底元素是不能删除的元素。
     (2) 顺序栈中元素值的大小是有序的。
     (3) n个不同元素通过一个栈，它们的出栈顺序和进栈顺序一定正好相反。
     (4) 栈顶元素和栈底元素有可能是同一个元素。
     (5) 若用s［0，m-1］表示顺序栈的存储空间，则对栈的进栈、出栈操作很多只能进行m次。
     (6) 栈是一种对进栈、出栈操作总次数做了的线性表。
     (7) 栈是一种对进栈、出栈操作的次序做了的线性表。
     (8) 对顺序栈进行进栈、出栈操作，不涉及元素的前、后移动问题。
     (9) 空栈没有栈顶指针。
     答： (1) 错误。当栈中只有一个元素时，这个元素也称栈底元素，它可以删除(出栈)。
     (2) 错误。顺序栈是指用顺序存储结构实现的栈，其中的元素不一定是有序的。
     (3) 错误。例如进栈序列为123，出栈的序列可以是132。
     (4) 正确。当栈中只有一个元素时就是这种情况。
     (5) 错误。可以进行任意多次的进栈、出栈操作，但栈中很多只有m个元素。
     (6) 错误。可以进行任意多次的进栈、出栈操作。
     (7) 错误。只要栈不满就可以进行进栈操作，只要栈不空就可以进行出栈操作，并不规定进栈、出栈操作的次序。
     (8) 正确。
     (9) 错误。空栈是指栈中没有元素，但一定要有栈顶指针。
     【例3？1？12】判断以下叙述的正确性。
     (1) 栈是一种特殊的线性表，其特殊之处在于其存储结构比较特殊。
     (2) 栈和线性表是两种不同的数据结构，它们的数据元素的逻辑关系也不同。
     (3) 空栈是指栈中元素没有赋值。
     (4) 栈在算法设计中用于保存临时数据，这些数据具有优选后出的特点。
     (5) 有n个不同的元素通过一个栈，产生的所有出栈序列恰好构成这n个元素的全排列。
     (6) n个元素依次连续进栈后，它们的出栈顺序一定与进栈顺序相反。
     答： (1) 错误。栈是一种特殊的线性表，其特殊之处是插入和删除操作只能在线性表两端进行。
     (2) 错误。栈和线性表是两种不同的数据结构，但它们的数据元素的逻辑关系都是线性关系。
     (3) 错误。空栈是指栈中没有元素。
     (4) 正确。
     (5) 错误。
     (6) 正确。
     4. 简答题
     【例3？1？13】输入序列abc通过一个栈后产生的全部输出序列有哪些？
     答： 利用栈的“后进先出”的特点，有如下几种情况。
     ？ a进，a出，b进，b出，c进，c出，产生输出序列abc。
     ？ a进，a出，b进，c进，c出，b出，产生输出序列acb。
     ？ a进，b进，b出，a出，c进，c出，产生输出序列bac。
     ？ a进，b进，b出，c进，c出，a出，产生输出序列bca。
     ？ a进，b进，c进，c出，b出，a出，产生输出序列cba。
     ？ 不可能产生输出序列cab。
     【例3？1？14】有5个元素，其进栈次序为a、b、c、d、e，在各种可能的出栈次序中，以元素c、d优选出栈(即c个且d第二个出栈)的次序有哪几个？
     答： 可能的次序有cdbae、cdeba、cdbea。
     【例3？1？15】设输入元素为1、2、3、P和A，进栈序列为123PA，元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为不错语言的变量名？
     答： 不错语言变量名的定义规则是以字母开头的字母数字串。进栈次序为123PA，以A优选出栈的序列为AP321，以P优选出栈的序列为P321A、P32A1、P3A21、PA321。所以可以作为不错语言的变量名的序列为AP321、P321A、P32A1、P3A21和PA321。
     【例3？1？16】设有一个数列的输入顺序为123456，若采用栈结构，并以S和X分别表示进栈和出栈操作，试求通过进栈和出栈操作得到的合法序列。
     (1) 能否得到输出序列325641？
     (2) 能否得到输出序列154623？
     答： (1) 能得到输出序列325641，其操作序列为SSSXXSSXSXXX。
     (2) 不能得到输出序列154623。执行SXSSSSXXSX，得到输出序列1546后，栈中元素从栈顶到栈底为32，不能让2先出栈，所以得不到输出序列154623。
     视频讲解
     【例3？1？17】证明： 初始输入序列为1，2，…，n，利用一个栈得到输出序列（p1，p2，…，pn）（(p1，p2，…，pn）是（1，2，…，n）的一种排列）的充分必要条件是不存在这样的i、j、k满足i     证明：
     【充分条件】如果不存在这样的i、j、k满足i     其他所有输出序列是存在的：
     …，1，…，2，…，3，…(…，pj，…，pk，…，pi，…)
     …，1，…，3，…，2，…(…，pj，…，pi，…，pk，…)
     …，2，…，1，…，3，…(…，pk，…，pj，…，pi，…)
     …，2，…，3，…，1，…(…，pk，…，pi，…，pj，…)
     …，3，…，2，…，1，…(…，pi，…，pk，…，pj，…)
     所有这些输出序列均满足优选后出或者后进先出的特点，所以构成一个栈。
     【必要条件】假设初始输入序列是1，2，…，n，通过一个栈得到输出序列(p1，p2，…，pn)，且存在这样的i、j、k满足i     【例3？1？18】假设以S和X分别表示进栈和出栈操作，则初态和终态为栈空的进栈和出栈的操作序列，可以表示为仅由S和X组成的序列。称可以实现的栈操作序列为合法序列(例如SSXX为合法序列，SXXS为非法序列)。试给出区分给定序列为合法序列或非法序列的一般准则，并证明： 对同一输入序列的两个不同的合法序列不可能得到相同的输出序列。
     答： 合法的栈操作序列必须满足以下两个条件。
     (1) 在操作序列的任何前缀(从开始到任何一个操作时刻)中，S的个数不得少于X的个数。
     (2) 整个操作序列中S和X的个数相等。
     要求证明： 对同一输入序列a1a2…an的两个合法操作序列p=p1p2…pj-1pj…p2n、q=q1q2…qj-1qj…q2n，不可能得到相同的输出序列。
     证明： 因为p≠q，所以一定存在一个j(1≤j≤2n，设合法的栈操作序列的长度为2n)，使得p1p2…pj-1=q1q2…qj-1，而pj≠qj，假设操作子序列p1p2…pj-1已将a1a2…ai-1进栈且将其中某些元素出栈，而aiai＋1…an尚未进栈。
     因为p和q都是合法栈操作序列，且pj≠qj，所以pj和qj中必有一个为S操作，另一个为X操作(不失一般性，不妨设pj为S操作，qj为X操作)，而且栈不必为空(不然就不能进行X操作)。设栈顶元素为af(1≤f≤i)。因此对于操作序列p来说，在其对应的输出序列中ai必靠前于af(因为pj为S操作，它使ai进栈，而af已在栈中)，对于操作序列q来说，在其对应的输出元素序列中，af必靠前于ai(因为qj为X操作，它使af出栈而ai尚未进栈)，所以p和q必定对应不同的输出序列。
     【例3？1？19】有一个字符串序列3*-y-a/y↑2，试利用栈给出将其改变为3y-*ay2↑/-的操作步骤。可用S代表进栈操作，用X代表出栈操作，例如，abc变为bca，则操作步骤为SSXSXX。 答： 上述转换的过程如表3.1所示，进出栈的操作步骤为SXSSSXXXSSXSSXSSXXXX。
     表3.1利用栈转换字符串的过程
     输 入 序 列操作操作符输 出 序 列
     3*-y-a/y↑23进栈S
     3出栈X3
     *-y-a/y↑2*进栈S
     -y-a/y↑2-进栈S
     y-a/y↑2y进栈S
     y出栈X3y
     -出栈X3y-
     *出栈X3y-*
     -a/y↑2-进栈S
     a/y↑2a进栈S
     a出栈X3y-*a
     /y↑2/进栈S
     y↑2y进栈S
     y出栈X3y-*ay
     ↑2↑进栈S
     22进栈S
     2出栈X3y-*ay2
     ↑出栈X3y-*ay2↑
     续表
     输 入 序 列操作操作符输 出 序 列
     /出栈X3y-*ay2↑/
     -出栈X3y-*ay2↑/-
     3.2知识点2： 顺序栈的算法
     3.2.1要点归纳
     1. 顺序栈的定义
     图3.5顺序栈的结构示意图
     顺序栈就是采用顺序存储结构存储的栈，即分配一块连续的存储区域存放栈中元素，并用一个变量作为栈顶指针指向当前的栈顶元素。顺序栈的结构示意图如图3.5所示。
     假设栈的元素个数优选不超过正整数MaxSize，所有元素都具有同一数据类型，即ElemType，则可用如下方式来定义栈类型SqStack。
     typedef struct
     {ElemType data［MaxSize］;//存放栈中元素
     int top; //栈顶指针
     } SqStack; //声明顺序栈类型
     构成顺序栈st的几个要素如下。
     ？ 栈空条件： st.top==-1
     ？ 栈满条件： st.top==MaxSize-1
     ？ 元素x进栈操作： st.top++； st.data［st.top］=x；
     ？ 出栈x操作： x=st.data［st.top］； st.top--； 说明： 顺序栈栈顶指针top的初值(栈空时栈顶指针的值)通常设为-1，有的教科书设为0，无论设置为哪个初值都需考虑充分利用data数组空间和栈的操作特点。
     2. 顺序栈的基本运算算法
     1) 初始化栈
     将栈顶指针置为-1，对应算法如下。
     void InitStack(SqStack &st) //初始化栈运算
     {
     st.top=-1;
     }
     2) 判断栈是否为空
     栈st为空时返回1，否则返回0，对应算法如下：
     int StackEmpty(SqStack st) //判断栈是否为空运算
     {
     return(st.top==-1);
     }
     3) 进栈
     在栈不满的条件下，先将栈顶指针增1，然后在该位置上插入元素x，对应算法如下。
     int Push(SqStack &st,ElemType x) //进栈运算
     {if (st.top==MaxSize-1) //栈满的情况，即栈上溢出
     return 0;
     st.top++;
     st.data［st.top］=x;
     return 1;
     }
     4) 出栈
     在栈不为空的条件下，先将栈顶元素赋给x，然后将栈顶指针减1，对应算法如下。
     int Pop(SqStack &st,ElemType &x) //出栈运算
     {if (st.top==-1) //栈为空的情况，即栈下溢出
     return 0;
     x=st.data［st.top］; //取栈顶元素
     st.top--;
     return 1;
     }
     5) 取栈顶元素
     在栈不为空的条件下，返回当前的栈顶元素，并将其值赋给x，对应算法如下。
     int GetTop(SqStack &st,ElemType &x)//取栈顶运算
     {if (st.top==-1) //栈为空的情况，即栈下溢出
     return 0;
     x=st.data［st.top］; //取栈顶元素
     return 1;
     }
     说明： 用一个数组a［0..MaxSize-1］表示栈时，由于栈元素是向一端伸长的，因此总是将数组的一端如data［0］或者data［MaxSize-1］端作为栈底，另一端作为栈顶，不能将中间位置作为栈底。
     3. 共享栈
     顺序栈采用一个数组存放栈中的元素，如果需要用到两个相同类型的栈，这时若为它们各自开辟一个数组空间，极有可能出现这样的情况： 一个栈已满，再进栈就溢出了，而另一个栈还有很多存储空间空闲。
     解决这个问题的方法是将两个栈合起来，如图3.6所示，用一个数组来实现这两个栈，称为共享栈。由于一个数组(大小为MaxSize)有两个端点，两个栈有两个栈底，所以在设计共享栈时，可让一个栈的栈底为数组的始端，即下标为0处，另一个栈的栈底为数组的末端，即下标为MaxSize-1，这样在两个栈中进栈元素时，可以实现两端点向中间延伸。
     图3.6共享栈
     共享栈的几个要素如下。
     ？ 栈空条件： 栈1空为top1==-1； 栈2空为top2==MaxSize
     ？ 栈满条件： top1==top2-1或者top1+1==top2
     ？ 元素x进栈操作： 进栈1操作为top1++； data［top1］=x;，进栈2操作为top2--； data［top2］=x;
     ？ 出栈x操作： 出栈1操作为x=data［top1］； top--;，出栈2操作为x=data［top2］； top++;
     在上述设置中，data数组表示共享栈的存储空间，top1和top2分别为两个栈的栈顶指针，这样该共享栈可通过data、top1和top2来标识，通常将它们设计为如下结构体类型。
     typedef struct
     {ElemType data［MaxSize］;
     int top1,top2;
     } DStack; //声明共享栈类型
     在实现共享栈的各种算法时，需增加一个形参i，指出是对哪个栈进行操作，如i=1表示对栈1进行操作，i=2表示对栈2进行操作。
     4. 求算术表达式的值
     假设算术表达式是只包含+、-、*、/、正整数和括号的合法数学表达式，称为简单算术表达式。求算术表达式值的过程是先将算术表达式转换成后缀表达式(亦称逆波兰表达式)，然后对该后缀表达式求值。
     视频讲解 1) 将算术表达式exp转换成后缀表达式postexp
     在转换过程中采用一个运算符栈op，其结构设计如下。
     struct
     {char data［MaxSize］; //存放运算符
     int top; //栈顶指针
     } op; //声明运算符栈
     将中缀表达式exp转换为后缀表达式postexp的过程如图3.7所示。
     图3.7算术表达式转换为后缀表达式的过程
     例如将表达式(56-20)/(4+2)转换成后缀表达式，过程如表3.2所示。
     表3.2表达式(56-20)/(4+2)转换成后缀表达式的过程
     exp操 作 过 程oppostexp
     (56-20)/(4+2)遇到ch为(，将此括号进栈op(
     56-20)/(4+2)遇到ch为数字，将56存入postexp中，并插入一个字符#(56#
     -20)/(4+2)遇到ch为-，由于op中(之前没有字符，则直接将ch进栈op中(-56#
     20)/(4+2)遇到ch为数字，将20#存入数组exp中(-56#20#
     )/(4+2)遇到ch为)，将栈op中(之前的字符依次出栈并存入postexp中，然后将(删除56#20#-
     /(4+2)遇到ch为/，将ch进栈op中/56#20#-
     (4+2)遇到ch为(，将此括号进栈op中/(56#20#-
     4+2)遇到ch为数字，将4#存入数组postexp中/(56#20#-4#
     +2)遇到ch为+，由于op栈顶运算符为(，所以直接将ch进栈op中/(+56#20#-4#
     2)遇到ch为数字，将2#存入postexp中/(+56#20#-4#2#
     )遇到ch为)，将栈op中(之前的字符依次出栈并存放到postexp中，然后将(出栈/56#20#-4#2#+
     str扫描完毕，则将栈op中的所有运算符依次弹出并存放到postexp中，得到后缀表达式56#20#-4#2#+/
     对于简单算术表达式exp，在考虑运算符优先级后，转换成后缀表达式postexp的trans()算法如下。
     void trans(char exp［］,char postexp［］) //将算术表达式exp转换为后缀表达式postexp
     {char ch;
     int i=0,j=0; //i作为exp的下标,j作为postexp的下标
     op.top=-1;
     ch=exp［i］;i++;
     while (ch!='＼0') //exp表达式未扫描完时循环
     {switch(ch) {
     case '(': //判定为左括号
     op.top++;op.data［op.top］=ch;
     break;
     case ')': //判定为右括号
     while (op.data［op.top］!='(')
     {postexp［j］=op.data［op.top］;j++;
     op.top--;
     }
     op.top--;
     break;
     case '+': //为+或-时,其优先级不大于栈顶任何运算符的优先级,直到（
     case '-':
     while (op.top!=-1 && op.data［op.top］!='(')
     {postexp［j］=op.data［op.top］; j++;
     op.top--;
     }
     op.top++;op.data［op.top］=ch;
     break;
     case '*': //为*或/时,其优先级不大于栈顶为*或/的优先级,直到（
     case '/':
     while (op.top!=-1 && op.data［op.top］!='('
     && (op.data［op.top］=='*' || op.data［op.top］=='/'))
     {postexp［j］=op.data［op.top］;j++;
     op.top--;
     }
     op.top++;op.data［op.top］=ch;
     break;
     case ' ':break; //过滤掉空格
     default:
     while (ch>='0' && ch<='9')//判定为数字
     {postexp［j］=ch;j++;
     ch=exp［i］;i++;
     }
     i--;
     postexp［j］='#'; j++; //用#标识一个数值串结束
     }
     ch=exp［i］;i++;
     }
     while (op.top!=-1) //此时exp扫描完毕,栈不空时出栈并存放到postexp中 {postexp［j］=op.data［op.top］; j++;
     op.top--;
     }
     postexp［j］='＼0'; //给postexp表达式添加结束标识
     }
     求解方法提示
     将中缀表达式转换成后缀表达式的另外一种方法是手工加除括号，其过程为先根据中缀表达式的求值次序加上括号，将右括号用相应的运算符替换，再删除所有左括号。
     例如将中缀表达式5+2*(1+6)-8/2转换成后缀表达式的过程： 手工判断该表达式的计算过程，先计算2*(1+6)，加上括号变为5+(2*(1+6))-8/2； 再计算8/2，加上括号变为5+(2*(1+6))-(8/2)； 接着进行加法运算，加上括号变为(5+(2*(1+6)))-(8/2)，很后进行减法运算，加上括号变为((5+(2*(1+6)))-(8/2))。运算符和右括号的对应关系如图3.8所示，将右括号用对应的运算符替换，变为((5 (2 (1 6+*+(8 2/-，很后除掉所有左括号，即得到后缀表达式为5 2 1 6+*+8 2/-。
     图3.8运算符和右括号的对应关系
     注意： 本方法需要人工判断表达式的执行顺序(即加括号)，所以无法用程序实现。
     2) 后缀表达式postexp求值
     在计算后缀表达式值的过程中需使用一个数值栈st，其结构设计如下。
     struct
     {double data［MaxSize］;//存放数值
     int top; //栈顶指针
     } st;
     后缀表达式求值过程如图3.9所示。
     图3.9后缀表达式求值过程
     例如对于后缀表达式56#20#-4#2#+/的求值，过程如表3.3所示。
     表3.3后缀表达式“56#20#-4#2#+/”的求值过程
     postexp操 作 过 程st
     56#20#-4#2#+/遇到56#，将56进栈56
     20#-4#2#+/遇到20#，将20进栈56,20
     -4#2#+/遇到-，出栈两次，将56-20=36进栈36
     4#2#+/遇到4#，将4进栈36,4
     2#+/遇到2#，将2进栈36,4,2
     +/遇到+，出栈两次，将4+2=6进栈36,6
     /遇到/，出栈两次，将36/6=6进栈6
     postexp扫描完毕，算法结束，栈顶的元素6即为所求
     根据上述计算原理得到的算法如下。
     double compvalue(char postexp［］)//计算后缀表达式postexp的值
     {double d; char ch;
     int i=0; //i作为postexp的下标
     st.top=-1;
     ch=postexp［i］;i++;
     while (ch!='＼0') //postexp字符串未扫描完时循环
     {switch (ch)
     {
     case '+':st.data［st.top-1］=st.data［st.top-1］+st.data［st.top］;
     st.top--;break;
     case '-':st.data［st.top-1］=st.data［st.top-1］-st.data［st.top］;
     st.top--;break;
     case '*':st.data［st.top-1］=st.data［st.top-1］*st.data［st.top］;
     st.top--;break;
     case '/':
     if (st.data［st.top］!=0)
     st.data［st.top-1］=st.data［st.top-1］/st.data［st.top］;
     else
     {printf("＼n＼t除零错误!＼n");
     exit(0); //异常退出