软考：软件设计师 — 13.数据结构

十三. 数据结构

数据结构部分也可参考文章：Java数据结构知识点 — 5种常见数据结构

1. 线性结构

（1）线性表

顺序表

线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。数组的内存是连续、静态分配的，即在使用数组之前需要分配固定大小的空间。

读操作：直接找到对应位置，时间复杂度为 O(1)。
查询操作：最少查 1 个，最多查 n 个，平均查 $\frac{n+1}{2}$ 个。
插入操作：最少后移 0 个（插在末尾），最多后移 n 个（插在开头），平均后移 $\frac{n+1}{2}$ 个。
删除操作：最少前移 0 个（删末尾），最多前移 n-1 个（删开头），平均前移 $\frac{n-1}{2}$ 个。

链表

线性表的链式存储是用通过指针链接起来的结点来存储数据元素。链表的内存是不连续的，前一个元素存储地址的下一个地址中存储的不一定是下一个元素。链表通过一个指向下一个元素地址的引用将链表中的所有元素串起来。

结点的基本结构：

链表的每个结点实际上是一个结构体变量，有若干成员组成，包括数据部分和指针变量。

struct node{int data;          // 结点的数据域struct node *link; // 结点的指针域
}

链表的基本结构：

尾结点：最后一个有效结点。
首结点：第一个有效结点。
头结点：第一个有效结点之前的那个结点，存放链表首地址。
头指针：指向头结点的指针变量。
尾指针：指向尾结点的指针变量。

链表的特点：

n 个结点离散分布，彼此通过指针相联系。
除头结点和尾结点外，每个结点只有一个前驱结点和一个后继结点。头结点没有前驱结点，尾结点没有后继结点。
头结点并不存放有效数据，只存放链表首地址。其头结点的数据类型和首结点类型一样。
加头结点的目的是方便对链表的操作，比如在链表头部进行结点的删除、插入。

链表的分类：

根据链表中指针域的设置方式，链表可分为：单链表、循环链表、双向链表。

单链表的插入与删除操作：

p 所指结点后插入新元素结点（s 所指结点）

① s -> link = p -> link;

② p -> link = s;

删除 p 所指结点的后继结点

① q = p -> link;

② p -> link = p -> link -> link;

③ free(q);

删除 p 所指结点

① p -> data = p -> link -> data;

② q = p -> link;

③ p -> link = p -> link -> link;

④ free(q);

这种方式比较灵活，是将 p 结点的数值域用下一个结点的数值域覆盖，这样就不存在 p 结点了，然后删除下一个结点即可，也相当于变相删除了 p 结点。

双向链表的插入与删除操作：

插入 q 所指向的结点

① s -> front = p -> front;

② p -> front -> link = s;

③ s -> link = p;

④ p -> front = s;

删除结点 p 指向的结点

① p -> front -> link = p -> link;

② p -> link -> front = p -> front;

③ free(p);

顺序存储与链式存储对比

性能类别	具体项目	顺序存储	链式存储
空间性能	存储密度	=1，更优	<1
空间性能	容量分配	事先确定	动态改变，更优
时间性能	查找	O(n)	O(n)
	读	O(1)，更优	O(n)，最好情况为 1，最坏情况为 n
	插入	O(n)，最好情况为 0，最坏情况为 n	O(1)，更优
	删除	O(n)	O(1)，更优

例题：

设有一个包含 n 个元素的有序线性表。在等概率情况下删除其中一个元素，若采用顺序存储结构，则平均需要移动（）个元素；若采用单链表存储，则平均需要移动（）个元素。

A.1 B.(n-1)/2 C.longn D.n

A.0 B.1 C.(n-1)/2 D.n/2

解析：

删除元素，顺序表平均前移 $\frac{n-1}{2}$ 个元素，链式表不需要移动元素，只需删除结点指针即可，因此选 BA。

（2）队列与栈

栈

栈按照 “后进先出” 的原则操作。在栈顶进行入栈和出栈。

队列

队列按照 “先进先出” 的原则操作。在队尾入队，队头出队。常与循环单链表结合使用，不需要遍历。

一种比较特殊的队列是循环队列

队空条件：head = tail
队满条件：（tail + 1）% size = head
队列长度：（tail - head + size）% size

tail 指向最后一个元素的后一个位置，因此实际是空余一个位置。

例题1：

对于一个长度为 n(n>1) 且元素互异的序列，令其所有元素依次通过一个初始为空的栈后，再通过一个初始为空的队列。假设队列和栈的容量都足够大，且只要栈非空就可以进行出栈操作，只要队列非空就可以进行出队操作，以下叙述中，正确的是（）。

A.出队序列和出栈序列一定互为逆序。

B.出队序列和出栈序列一定相同。

C.入栈序列和入队序列一定相同。

D.入栈序列和入队序列一定互为逆序。

解析1：

由题干可知，出栈序列和入队序列一定是相同的，因为出栈后必入队，只要栈和队列都非空，而入队和出队次序相同，队列先进先出，所以出队序列和出栈序列相同。B 正确，A 错误。而入栈序列是未知的，因为可能存在某个元素 a 先进栈然后出栈，然后又有两个元素 b c 依次进栈，此时出栈的顺序就变成了 c b，所以入队序列也就不相同也不互逆，因此 CD 错误。

例题2：

队列的特点是先进先出，若用循环单链表表示队列，则（）。

A.入队列和出队列操作都不需要遍历链表。

B.入队列和出队列操作都需要遍历链表。

C.入队列操作需要遍历链表而出队列不需要。

D.入队列操作不需要遍历链表而出队列需要。

解析2：

入队在队尾，出队在对头，所以不需要遍历链表。选项 A 正确。

例题3：

若元素以 a，b，c，d，e 的顺序进入一个初始为空的栈中，每个元素进栈、出栈各 1 次，要求出栈的第一个元素为 d，则合法的出栈序列共有（）种。

A.4 B.5 C.6 D.24

解析3：

出栈的第一个元素要求为 d，那么在 d 前面一定是 c，b，a，因为栈是后进先出，e 还没有进栈。d 第一个出栈，然后看剩余的元素 c b a 和 e 的排列方式，e 可以在 c 之前，也可以在 c b 之间，或 b a 之间，或 a 之后，因此出栈序列共 4 种。选 A。

例题4：

双端队列是指在队列的两个端口都可以加入和删除元素，如下图所示。现在要求元素进队和出队都必须在同一端口，即从 A 端进队的元素必须从 A 端出、从 B 端进队的元素必须从 B 端出，则对于 4 个元素的序列 a、b、c、d，若要求前两个元素（a、b）从 A 端口按次序全部进入队列，后两个元素（c、d）从 B 端口按次序全部进入队列，则不可能得到的出队序列是（）。

A.d、a、b、c B.d、c、b、a C.b、a、d、c D.b、d、c、a

解析4：

可以想象成有一条线将队列从中间隔开，一端是 A，一端是 B，而每端是栈，a、b 元素进入 A 端后，b 元素不出来，a 元素也无法出来，同理，B 端也是，d 元素不出来，c 元素也出不来。所以只有 A 选项错误，d 元素先出，然后要么下一个元素要么是 c 出来，要么是 b 出来，而 a 无法出来。

（3）串

串是仅有字符构成的有限序列，是一种线性表。一般记为 S = ' $a_{1}a_{2}\cdots a_{n}$ '，其中，S 是串名，单引号括起来的字符序列是串值。

串的几个基本概念：

空串：长度为零，不包含任何字符。
空格串：由一个或多个空格组成的串。虽然空格是一个空白字符，但它也是一个字符，在计算串长度时要将其计算在内。
字串：由串中任意长度的连续字符构成的序列称为子串（2 的 n 次方，n 为单个字符个数）。含有子串的串称为主串。子串在主串中的位置是指子串首次出现时，该子串的第一个字符在主串中的位置。空串是任意串的子串。
子序列：一个串的子序列是将这个串中的一些字符提取出来得到一个新串，并且不改变它们的相对位置关系。也就是说，假设一个串是 abbc，那么 ab、ac都是它的子序列。
串比较：两个串比较大小时以字符的 ASCII 码值作为依据。实质上，比较操作从两个的第一个字符开始进行，字符的码值大者所在的串为大；若其中一个串先结束，则以串长较大者为大。
串相等：指两个串长度相等且对应序号的字符也相同。

串的基本操作：

赋值操作 StrAssign(s,t)：将串 s 的值赋给串 t。
连接操作 Concat(s,t)：将串 t 接续在串 s 的尾部，形成一个新的串。
求串长 StrLength(s)：返回串 s 的长度。
串比较 StrCompare(s,t)：比较两个串的大小。返回值 -1、0 和 1 分别表示 s<t、s=t 和 s>t 三种情况。
求子串 SubString(s,start,len)：返回串 S 中从 start 开始的、长度为 len 的字符序列。

串的存储：

顺序存储：用一组地址连续的存储单元来存储串值的字符序列。
链式存储：用链表存储串中的字符，，每个结点中可以存储一个字符，也可以存储多个。

串的模式匹配：

子串的定位操作通常称为串的模式匹配。（子串也称为模式串）

朴素的模式匹配算法（布鲁特-福斯算法）：其基本思想是从主串的第一个字符起与模式串的第一个字符比较，若相等，则继续逐一对字符进行后续的比较，否则从主串第二个字符起与模式串的第一个字符重新比较，直到模式串中每个字符依次与主串中一个连续的字符序列相等时为止，此时称为匹配成功。如果不能在主串中找到与模式串相同的子串，则匹配失败。
改进的模式匹配算法（KMP算法）：其改进之处在于，每当匹配过程中出现相比较的字符不相等时，不需要回退到主串的字符位置指针，而是利用已经得到的部分匹配结果将模式串向右滑动尽可能远的距离，再继续进行比较。

在 KMP 算法中，依据模式串的 next 函数值实现子串的滑动。若令 next[j] = k，则 next[j] 表示当模式串中的 $p_{j}$ 与主串中相应字符不相等时，令模式串的 $p_{next[j]]}$ 与主串的相应字符进行比较。（j = next[j]）

next 函数定义如下：

需要掌握 next 函数值的求取，并且可能出题老师给出的 next 函数定义不同，但本质计算过程相同。其中，第二条是指有多个 k 值时，选择最大的那个。

例题1：

在字符串的 KMP 模式匹配算法中，需先求解模式串的 next 函数值，其定义如上图所示，j 表示模式串中字符的序号（从 1 开始）。若模式串 p 为 'abaac'，则其 next 函数值为（）。

A.01234 B.01122 C.01211 D.01111

解析1：

j	1	2	3	4	5
模式串	a	b	a	a	c
next[j]	0	1	1	2	2

当 j = 1 时，next[j] = 0；当 j = 2 时，即 1<k<2，不存在整数 k ，因此是其它情况，next[j] = 1；当 j = 3 时，即 1<k<3，因此 k = 2，此时需要判断表达式 'p1p2…pk-1' = 'pj-k+1 pj-k+2…pj-1' 是否满足条件，即 p1p2…pk-1 = p1 = a，pj-k+1pj-k+2…pj-1 = p2 = b，a ≠ b，所以不满足条件，是其它情况，next[j] = 1；当 j = 4 时，即 1<k<4，因此 k = 2 或 3，当 k = 2 时，表达式为 p1 = p3，为真（a = a），当 k = 3 时，表达式为 p1p2 = p2p3，为假（ab ≠ ba），所以当 j = 4 时，k = 2；同理，继续推断 j = 5，即 1<k<5，k = 2 或 3 或 4，当 k = 2 时，表达式为 p1 = p4，满足条件，当 k = 3 时，表达式为 p1p2 = p3p4，为假，不满足条件，当 k = 4 时，表达式为 p1p2p3 = p2p3p4，为假，不满足条件，因此 next[j] 的值为 2。所以 next 函数值为 01122，选 B。

例题2：

设 S 是一个长度为 n 的非空字符串，其中的字符各不相同，则其互异的非平凡子串（非空且不同于 S 本身）个数为（）。

A.2n-1 B. $n^{2}$ C.n(n+1)/2 D.(n+2)(n-1)/2