出队算法如下：

⑵ 设顺序栈S中有2n个元素，从栈顶到栈底的元素依次为a2n，a2n-1，…，a1，要求通过一个循环队列重新排列栈中元素，使得从栈顶到栈底的元素依次为a2n，a2n-2，…，a2，a2n-1，a2n-3，…，a1，请设计算法实现该操作，要求空间复杂度和时间复杂度均为O(n)。 【解答】操作步骤为： ① 将所有元素出栈并入队；

② 依次将队列元素出队，如果是偶数结点，则再入队，如果是奇数结点，则入栈；

③ 将奇数结点出栈并入队； ④ 将偶数结点出队并入栈； ⑤ 将所有元素出栈并入队； ⑥ 将所有元素出队并入栈即为所求。

⑶ 用顺序存储结构存储串S，编写算法删除S中第 i个字符开始的连续j个字符。

【解答】先判断串S中要删除的内容是否存在，若存在，则将第i+j-1之后的字符前移j个位置。算法如下：

⑷ 对于采用顺序存储结构的串S，编写一个函数删除其值等于ch的所有字符。

【解答】从后向前删除值为ch的所有元素，这样所有移动的元素中没有值为ch的元素，能减少移动元素的次数，提高算法的效率。算法如下：

⑸ 对串的模式匹配KMP算法设计求模式滑动位置的next函数。 【解答】参见3.2.5

学习自测及答案

1．在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，当出栈时，top的变化为（ ）。 A 不变 B top=0; C top=top-1; D top=top+1; 【解答】C

2．一个栈的入栈序列是a, b, c, d, e，则栈的不可能的出栈序列是（ ）。 A edcba B cdeba C debca D abcde 【解答】C

3．从栈顶指针为top的链栈中删除一个结点，用x保存被删除结点的值，则执行（ ）。

A x=top; top=top->next; B x=top->data;

C top=top->next; x=top->data; D x=top->data; top=top->next; 【解答】D

4．设元素1, 2, 3, P, A依次经过一个栈，进栈次序为123PA，在栈的输出序列中，有哪些序列可作为C++程序设计语言的变量名。 【解答】PA321, P3A21, P32A1, P321A, AP321

5.设S=\，其长度为（ ）。 【解答】15

6．对于栈和队列，无论它们采用顺序存储结构还是链接存储结构，进行插入和删除操作的时间复杂度都是（ ）。 【解答】Ｏ(1)

7．如果进栈序列为A、B、C、D，则可能的出栈序列是什么？

答：共14种，分别是：ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA 8．简述队列和栈这两种数据结构的相同点和不同点。

【解答】相同点：它们都是插入和删除操作的位置受限制的线性表。

不同点：栈是限定仅在表尾进行插入和删除的线性表，是后进先出的线性表，而

队列是限定在表的一端进行插入，在另一端进行删除的线性表，是先进先出的线性表。

9. 利用两个栈S1和S2模拟一个队列，如何利用栈的运算实现队列的插入和删除操作，请简述算法思想。

【解答】利用两个栈S1和S2模拟一个队列，当需要向队列中插入一个元素时，用S1来存放已输入的元素，即通过向栈S1执行入栈操作来实现；当需要从队列中删除元素时，则将S1中元素全部送入到S2中，再从S2中删除栈顶元素，最后再将S2中元素全部送入到S1中；判断队空的条件是：栈S1和S2同时为空。

10. 设计算法把一个十进制整数转换为二至九进制之间的任一进制数输出。 【解答】算法基于原理：N=(N div d)×d + N mod d （div为整除运算，mod为求余运算）。

11．假设一个算术表达式中可以包含三种括号：圆括号“（”和“）”，方括号“[”和“]”以及花括号“{”和“}”，且这三种括号可按任意的次序嵌套使用。编写算法判断给定表达式中所含括号是否配对出现。 【解答】假设表达式已存入字符数组A[n]中，具体算法如下：

第 4 章 广义线性表——多维数组和广义表 课后习题讲解

1. 填空

⑴ 数组通常只有两种运算：（ ）和（ ），这决定了数组通常采用（ ）结构来实现存储。

【解答】存取，修改，顺序存储

【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。

⑵ 二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是（ ）。 【解答】1140

【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。

⑶ 设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（ ）。 【解答】d+41

【分析】元素A[8][5]的前面共存储了(1+2+…+8)+5=41个元素。