数据结构习题集答案（C版）严蔚敏

【数据结构习题集答案（C版）严蔚敏】主要涵盖了数据结构中的栈与队列的相关知识。栈是一种后进先出（LIFO）的数据结构，而队列则是先进先出（FIFO）的数据结构。以下是这些知识点的详细解释： ### 双向栈（BDStacktype） 双向栈在结构上包含两个栈底，一个称为低端栈，另一个称为高端栈，它们共享同一个存储空间。定义如下： ```c typedef struct{ Elemtype *base[2]; Elemtype *top[2]; } BDStacktype; ``` `base[0]` 和 `base[1]` 分别指向低端栈和高端栈的底部，`top[0]` 和 `top[1]` 分别指向当前栈顶。 ### 初始化双向栈（Init_Stack） ```c Status Init_Stack(BDStacktype &tws, int m) ``` 这个函数用于初始化一个大小为 m 的双向栈。它首先分配连续的存储空间，并将低端栈和高端栈的栈底和栈顶指针设置好。 ### 入栈（push） ```c Status push(BDStacktype &tws, int i, Elemtype x) ``` 函数 `push` 用于将元素 x 入栈。参数 i 用于指定入栈的位置，0 表示低端栈，1 表示高端栈。栈满的条件是 `tws.top[0] > tws.top[1]`。入栈操作根据 i 的值分别对低端栈和高端栈进行操作。 ### 出栈（pop） ```c Status pop(BDStacktype &tws, int i, Elemtype &x) ``` 函数 `pop` 用于从栈中弹出元素。同样，i 参数用于指定出栈的位置，0 或 1 分别对应低端栈和高端栈。出栈时检查栈是否为空，然后更新栈顶指针并返回出栈元素。 ### 栈的应用实例 - **3.16 火车座位排列（Train_arrange）** 这个函数将输入的火车座位字符串 `train` 中的 'H'（硬席）存入栈中，将 'S'（软席）保留在前面。最后将栈中的 'H' 排列在 'S' 之后，实现硬席在后的顺序。 - **3.17 判断逆串（IsReverse）** 此函数通过栈来判断输入的字符串中 ' &' 前后部分是否为逆序。不允许在 ' &' 前出现 '@' 字符，如果 ' &' 后的字符序列与 ' &' 前的逆序相同，则返回 1，否则返回 0。 - **3.18 小括号匹配测试（Bracket_Test）** 这个函数用于检查一个字符串中的小括号 '(' 和 ')' 是否匹配。通过计数器 `count` 记录未关闭的小括号数量，如果计数器在过程中变为负数或最终不为零，则返回错误。 - **3.19 三种括号匹配测试（AllBrackets_Test）** 这个函数扩展了括号匹配的功能，不仅包括小括号，还包括方括号 '[' 和 ']' 以及大括号 '{' 和 '}'。同样使用栈来检查括号匹配，不同类型的括号需要对应匹配。如果遇到无法匹配的括号，返回错误。 这些习题展示了栈在实际问题中的应用，如处理顺序、判断字符串特性以及检查括号匹配等。通过这些习题，可以加深对栈这一数据结构的理解和运用。