济南铁道职业技术学院 专升本辅导教材 数据结构

4．5 若按从左到右的顺序依次读人已知序列{a，b，c，d，e，f，g1中的元素，然后结合堆栈操作，能得

到下列序列中的哪些序列(每个元素进栈一次，下列序列表示出栈的次序)? {d，e，c，f，b，g，a} {f，e，g，d，a，c，b}

{e，f，d，g，b，c，a} {c，d，b，e，f，a，g}

4．6 设有编号1，2，3，4的四辆列车，顺序进入一个栈式结构的站台，请写出这四辆列车开出车站的

所有可能的顺序。

4．7 设STACK[M]为n(n>2)个堆栈共享。各栈栈顶指针为top[n]，分别指出各栈栈顶元素的位置；栈底

指针为bot[n+1]，分别指出各栈栈底元素的位置。初始时， bop[i]=bot[i]=i*ROUND(M／n—0．5) (i=1，2，....，n)

其中，ROUND()为四舍五人取整函数。请写一算法，该算法向任意指定的第i个堆栈插入一个新的元

素x。仅当M个空间全部占用时才产生溢出，并报告相应信息(1≤i≤n)。

4．8 设中缀表达式E存放于字符数组中，并以@作为结束标志。请写出判断一个中缀表达式E中左、右

圆括号是否配对的算法。

4．9 写出将中缀表达#(a+b)／c-d#变换为后缀表达式的过程中，每读到一个单词时堆栈的状态(#为中缀表

达式的左、右分界符)。

4．10 已知Ackerman函数定义如下：

(1)写出递归算法；

(2)利用堆栈写出非递归算法；

(3)根据非递归算法，求出A(：K(2，1)的值。

4．12 已知求两个正整数m和n的最大公约数的过程可以表达为如下递归函数：

请写出求解该递归函数的非递归算法。m MOD n表示m对n取模。 4．13 假设以数组Q[M]存放循环队列的元素，同时设置变量rear与qlen分别指示循环队列中队尾元素的位置和队列中元素的个数。请给出此循环队列的队满条件，并写出相应的进队与出队算法(在出队算法中要求返回队头元素)。

4．14 编写一非递归算法，对于给定的十进制整数n，打印出对应的r进制整数(2≤r≤16，r<>10)。

栈和队列 历年试题

1．栈和队列都是（ ） A．限制存取位置的线性结构 C．链式存储的线性结构

B．顺序存储的线性结构

D．限制存取位置的非线性结构

2．若数组s[0..n-1]为两个栈s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为（ ）

A．1和n+1 B．1和n/2 C．－1和n D．－1和n+1

3.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为( ) A.4 B.5 C.6 D.7

4．假设元素只能按a,b,c,d的顺序依次进栈，且得到的出栈序列中的第一个元素为c，则可能得到的出栈序列为________________，不可能得到的出栈序列为________________。

第 21 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

5．在栈的顺序实现中，若栈不满，则进栈操作可以用下列算法片断实现： _____________； sq -> data[sq -> top]=x；

6．链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的_____________。 7．如图所示，设输入元素的顺序是A，B，C，D，通过栈的变换，在输出端可得到各种排列。若输出序列的第一个元素为D，则输出序列为_______________。

8．队列中允许进行删除的一端为________________。 9.假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，

得到的输出序列为________。 10、设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，

则顺序栈的容量至少应为多少？

11．如图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，求出在栈的输入端所有可

能的输入序列。（5分）

第四章 数组补充内容

3．3．2 对角矩阵的压缩存储

所谓对角矩阵是指矩阵中的所有非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线上和直接在主对角线上、下方对称的若干条对角线上的元素之外，其余元素均为零。

下面给出的矩阵B就是一个对角矩阵(确切地说是一个三对角矩阵，这里，我们仅以三对角矩阵为例子)。

三对角矩阵一共有3n—2个非零元素。我们可以按照某个原则(或者以行序为主序的分配方式，或者以列序为主序的分配方式，或者按照对角线的顺序进行分配)将对角矩阵B的所有非零元素压缩存储到一个一维数组LTB[3n—2]中。这里，不妨仍然以行序为主序的分配方式对B进行压缩存储，当B中任一非零元素Bij与LTB[k]之间存在着如下一一对应关系k=2*i+j-3时，则有Bij=LTB[k]。称LTB[3n—2]为对角

第 22 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

矩阵B的压缩存储，如下图所示。

上面讨论的几种特殊矩阵中，非零元素的分布都具有明显的规律，因而都可以被压缩 存储到一个一维数组中，并且能够确定这些矩阵的每一个元素(或非零元素)在一维数组 中的位置。但是，对于那些非零元素在矩阵中的分布没有规律的特殊矩阵(如稀疏矩阵)， 则需要寻求其他的方法来解决压缩存储问题。 3．5 稀疏矩阵的十字链表表示

上一节讨论了用三元组表的形式来存储一个稀疏矩阵的方法。但是，在实际应用中，当稀疏矩阵中非零元素的位置或者个数经常发生变化时，使用三元组表就不太方便了。

本节将介绍稀疏矩阵的另一种表示方法，即十字链表表示。

如何用链表形式来表示一个稀疏矩阵呢?方法之一就是将所有非零元素以行序为主序方式(当然也可以以列序为主序方式)采用循环链表链接起来。链结点的构造由四个域组成：

其中i,j分别表示某一个非零元素所在的行号与列号；value表示该非零元素的值； link域用来指向下一个非零元素所在的链结点，它是一个指针。另外，再设置一个链表头结点，其构造如下：

其中，m，n分别表示稀疏矩阵的行数与列数；t为稀疏矩阵非零元素的总个数；link域用来指向第一个非零元素对应的链结点。

例如，对于如下一个稀疏矩阵：

若采用行序为主序方式(每行又按列的先后顺序)依次将所有非零元素链接起来，则得到如图3．4所示的一个带有头结点的循环链表。

这种表示方法最明显的一个缺点就是，当要访问某行某列的一个非零元素时，必须从链表的最前面那个链结点开始进行搜索，其效率之低可想而知。

一个能提高访问效率的方法就是采用十字链表表示。这种方法为稀疏矩阵的每一行设置一个单独的行循环链表，同样也为每一列设置一个单独的列循环链表。这样，稀疏矩阵中的每一个非零元素同时包含在两个链表中，即包含在它所在的行链表与所在的列链表中，也就是这两个链表的交汇处。

对于一个mXn的稀疏矩阵，分别建立m个行的循环链表与n个列的循环链表，每个非零元素用一个链结点来存储。链结点的结构可以设计为

第 23 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

其中，rOW，c01，value分别表示某非零元素所在的行号、列号和相应的元素值；down与right分别称为向下指针与向右指针，它们分别用来链接同一列中的与同一行中的某非零元素结点。也就是说，稀疏矩阵中同一行的所有非零元素是通过right指针链接成一个行链表，同一列中的所有非零元素是通过down指针链接成一个列链表。而对每一个非零元素而言，它既是某个行链表中的一个链结点，同时又是某个列链表中的一个链结点，这个非零元素好比处在一个十字路口，故称这种链表表示为十字链表表示法。 作为链表，应该用某种方式能访问表中的第一个结点，为此，对于m个行链表，分别设置m个行链表表头结点。表头结点的构造与链表中其他链结点一样，只是令row与凹1域的值均为0，right域指向相应行链表的第一个链结点。同理，对于n个列链表，分别设置n个列链表表头结点。头结点结构也同其他链结点一样，只是令rOW与c01的值均为0，down域指向相应列链表的第一个链结点。另外，通过value域把所有这些表头链结点也链接成一个循环链表。 十字链表中的链结点类型可以描述如下： typedefstructnode{ int row,col； union{

ElemType val； struct node'ptr； 1value；

struct node 1 right，'down；

1 CNode，xCrossLink； ／‘定义十字链表结点类型x／

从m个行链表的表头结点与n个列链表的表头结点的设置情况看到，行链表的头结点只用了right域作为指针，而列链表的头结点只用了down域与 value域，其他域没有使用。因此，可以设想原来的(m+n)个头结点实际上可以合并成 MAX(m，n)。为此，再设置一个结点作为头结点链表的头结点，不妨称之为总头结点，其结构如下所示： m t n Link

其中，m，n分别为稀疏矩阵的行数与列数；t为非零元素的总个数；1ink指向头结点链表的第一个头结点。

总头结点的类型可以如下描述： typedefstruct{

int m，n，t,nil； CrossLink x link；

}HNode,*HLink； ／x定义十字链表总头结点类型x／ ‘

综上所述，若给出一个稀疏矩阵B如下，则它的十字链表表示如图3．5所示。

第 24 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

下面给出创建一个具有m行n列、有t个非零元素的稀疏矩阵的十字链表的算法。 稀疏矩阵用三元组表的形式作为输入。首先输入稀疏矩阵的行数、列数以及非零元素总个数(m，n，t)，然后依次读入个三元组。算法中用到了一个辅助数组hdnode [MAX(m，n)]。其中，hdnode[i]用来分别存放第i列(也是第i行)链表的头结点的指针 (1≤i≤MAX(m，n))。 #defineMaxNl00 HLinkMREAD() {

HLinkHEAD，p，last，hdnode[MaxN]； iht m,n t，k，i，Current_row， int rrow,ccol，val；

scanf(\％d％d％\，&n，&n，&t)； ／x读入矩阵的行、列和非零元素的个数‘／ if(t<=0)

return NULL； k=(m>n)?m：n；

第 25 页 共 63 页