12. 【解答】

2027 · OCR 辅助 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照

## 12. 【解答】

1）算法的基本设计思想：算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素 Num。然后重新计数，确认 Num 是否是主元素。

算法可分为以下两步：

① 选取候选的主元素。依次扫描所给数组中的每个整数，将第一个遇到的整数 Num 保存到 c 中，记录 Num 的出现次数为 1；若遇到的下一个整数仍等于 Num，则计数加 1，否则计数减 1；当计数减到 0 时，将遇到的下一个整数保存到 c 中，计数重新记为 1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。

② 判断 $c$ 中元素是否是真正的主元素。再次扫描该数组，统计 $c$ 中元素出现的次数，若大于 $n/2$，则为主元素；否则，序列中不存在主元素。

2）算法实现如下：

int Majority(int A[], int n) {
int i, c, count = 1; //c用来保存候选主元素，count用来计数
c = A[0]; //设置A[0]为候选主元素
for (i = 1; i < n; i++) //查找候选主元素
if (A[i] == c)
count++; //对A中的候选主元素计数
else
if (count > 0) //处理不是候选主元素的情况
count--;
else{ //更换候选主元素，重新计数
c = A[i];
count = 1;
}
if (count > 0)
for (i = count = 0; i < n; i++) //统计候选主元素的实际出现次数
if (A[i] == c)
count++;
if (count > n/2) return c; //确认候选主元素
else return -1; //不存在主元素
}


3）实现的程序的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

## 说明

本题若采用先排好序再统计的方法[时间复杂度为 $O(n \log_2 n)$]，则只要解答正确，最高就可拿11分。即使是写出 $O(n^2)$ 的算法，最高也能拿10分，因此，对于统考算法题，花费大量时间去思考最优解法是得不偿失的。本算法的方法非常典型，需要牢固掌握。

## 13. 【解答】

1）算法的基本设计思想：

<!-- page: 41 -->

第2章 线性表
29

要求在时间上尽可能高效，因此采用空间换时间的办法。分配一个用于标记的数组B[n]，用来记录A中是否出现了1～n中的正整数，B[0]对应正整数1，B[n-1]对应正整数n，初始化B中全部为0。A中含有n个整数，因此可能返回的值是1～n+1，当A中n个数恰好为1～n时返回n+1。当数组A中出现了小于或等于0或大于n的值时，会导致1～n中出现空余位置，返回结果必然在1～n中，因此对于A中出现了小于或等于0或大于n的值，可以不采取任何操作。

经过以上分析可以得出算法流程：从A[0]开始遍历A，若 $0 &lt; \mathrm{A}[i] &lt; = n$，则令B[A[i]-1]=1：否则不做操作。对A遍历结束后，开始遍历数组B，若能查找到第一个满足B[i]==0的下标i，返回i+1即为结果，此时说明A中未出现的最小正整数在1和n之间。若B[i]全部不为0，返回i+1（跳出循环时i=n，i+1等于n+1），此时说明A中未出现的最小正整数是n+1。

2）算法实现：

int findMissMin(int A[], int n)
{
int i, *B;           //标记数组
B = (int *)malloc(sizeof(int) * n); //分配空间
memset(B, 0, sizeof(int) * n);   //赋初值为 0
for (i=0; i&amp;lt;n; i++)
if (A[i] &amp;gt; 0 &amp;amp;&amp;amp; A[i] &amp;lt;= n)   //若 A[i] 的值介于 1~n，则标记数组 B
B[A[i]-1]=1;
for (i=0; i&amp;lt;n; i++)
if (B[i]==0) break;
return i+1;              //返回结果
}


3）时间复杂度：遍历A一次，遍历B一次，两次循环内操作步骤为 $O(1)$ 量级，因此时间复杂度为 $O(n)$。空间复杂度：额外分配了B[n]，空间复杂度为 $O(n)$。

## 14. 【解答】

分析。由 $D = |a - b| + |b - c| + |c - a| \geqslant 0$，有如下结论。

① 当 $a = b = c$ 时，距离最小。

② 其余情况。不失一般性，假设 $a \leqslant b \leqslant c$，观察下面的数轴：

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

$$
L _ {1} = | a - b |, \quad L _ {2} = | b - c |, \quad L _ {3} = | c - a |
$$

$$
D = | a - b | + | b - c | + | c - a | \geqslant 0 = L _ {1} + L _ {2} + L _ {3} = 2 L _ {3}
$$

由 $D$ 的表达式可知，事实上决定 $D$ 大小的关键是 $a$ 和 $c$ 之间的距离，于是问题就可以简化为每次固定 $c$ 找一个 $a$，使得 $L_{3} = |c - a|$ 最小。

1）算法的基本设计思想：

① 使用 $D_{\min}$ 记录所有已处理的三元组的最小距离，初值为一个足够大的整数。

② 集合 $S_{1}$、$S_{2}$ 和 $S_{3}$ 分别保存在数组 $A$、$B$、$C$ 中。数组的下标变量 $i = j = k = 0$，当 $i < |S_{1}|$、$j < |S_{2}|$ 且 $k < |S_{3}|$ 时（$|S|$ 表示集合 $S$ 中的元素个数），循环执行下面的步骤 a）～c）。

a）计算 $(A[i], B[j], C[k])$ 的距离 $D$：（计算 $D$）

b）若 $D < D_{\min}$，则 $D_{\min} = D$：（更新 $D$）

c）将 $A[i]$、$B[j]$、$C[k]$ 中的最小值的下标 $+1$：（对照分析：最小值为 $a$，最大值为 $c$，这里 $c$ 不变而更新 $a$，试图寻找更小的距离 $D$）

③ 输出 $D_{\min}$，结束。

<!-- page: 42 -->

2027年数据结构考研复习指导

2）算法实现：
#define INT_MAX 0x7ffffff
int abs_(int a) { //计算绝对值
if (a &amp;lt; 0) return -a;
else return a;
}
bool xls_min(int a, int b, int c) { //a 是否是三个数中的最小值
if (a &amp;lt;= b &amp;amp;&amp;amp; a &amp;lt;= c) return true;
return false;
}
int findMinofTrip(int A[], int n, int B[], int m, int C[], int p) {
//D_min 用于记录三元组的最小距离，初值赋为 INT_MAX
int i = 0, j = 0, k = 0, D_min = INT_MAX, D;
while (i &amp;lt; n &amp;amp;&amp;amp; j &amp;lt; m &amp;amp;&amp;amp; k &amp;lt; p &amp;amp;&amp;amp; D_min &amp;gt; 0) {
D = abs_(A[i] - B[j]) + abs_(B[j] - C[k]) + abs_(C[k] - A[i]); //计算 D
if (D &amp;lt; D_min) D_min = D; //更新 D
if (xls_min(A[i], B[j], C[k])) i++; //更新 a
else if (xls_min(B[j], C[k], A[i])) j++;
else k++;
}
return D_min;
}


3）设 $n = (|S_1| + |S_2| + |S_3|)$，时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

## 15. 【解答】

1）算法的基本设计思想：

从后向前扫描一趟数组 A，对每个 $A[i](0 \leqslant i \leqslant n - 1)$，分别找到从 $A[n - 1]$ 到 $A[i]$ 中的最大值 Max 和最小值 Min，然后分以下情况进行处理：① 若 $A[i] \geqslant 0$，则 $A[i]$ 与 Max 相乘；② 若 $A[i] &lt; 0$，则 $A[i]$ 与 Min 相乘。相乘的结果保存在 $\text{res}[i]$ 中。

2）算法实现：

void calMulMax(int A[], int res[], int n)
{
int i, Max, Min;
Max = Min = A[n - 1]
for (i = n - 1; i &amp;gt;= 0; i--) //从后向前扫描一趟数组 A
{
if (A[i] &amp;gt; Max) Max = A[i];
else if (A[i] &amp;lt; Min) Min = A[i];
if (A[i] &amp;gt;= 0) res[i] = A[i] * Max; //根据 A[i] 的正负性分别处理
else res[i] = A[i] * Min;
}
}


3）算法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

## 2.3 线性表的链式表示

顺序表支持随机存取任意元素，但插入和删除操作需要移动大量元素，效率较低。相比之下，链式存储的线性表不要求地址连续的存储单元，即逻辑上相邻的元素在物理位置上是可以不相邻的；它通过指针建立元素之间的逻辑关系，因此插入或删除操作无须移动元素，而只需修改相关指针，效率较高。然而，这样做的代价是失去了顺序表的随机存取能力，只能从头开始顺序访问。

<!-- page: 43 -->

第2章 线性表
31

## 2.3.1 单链表的定义

**常用语言** ⊞ 单链表的应用（2009、2012、2013、2015、2016、2019）

线性表的链式存储也称单链表。它通过一组任意的存储单元（不要求地址连续）来存储线性表中的数据元素。为了建立数据元素之间的线性关系，每个链表结点除了存放元素自身的信息外，还需额外设置一个指向其后继结点的指针。单链表的结点结构如图2.3所示，其中data为数据域，用于存放数据元素；next为指针域，用于存放其后继结点的地址。

|  data | next  |
| --- | --- |

图2.3 单链表的结点结构

单链表结点类型的定义如下：

typedef struct LNode{ //定义单链表结点类型
ElemType data; //数据域
struct LNode *next; //指针域
}LNode, *LinkList;


单链表避免了顺序表对连续内存空间的依赖，但每个结点需要额外存储一个指针，带来了一定的存储开销。同时，由于其元素离散地分布在内存中，单链表是一种非随机存取的存储结构，即无法直接定位到表中的某个特定结点，查找时要从表头开始依次遍历。

通常使用头指针L（或head等）来标识一个单链表，该指针指向链表的起始位置。当头指针为NULL时，表示链表为空。此外，为了简化操作，在单链表的第一个数据结点之前常附加一个特殊的结点，称为头结点。头结点的数据域一般不存放有效数据（但可用于记录表长等信息）。在带头结点的单链表中，头指针L指向头结点，而头结点的next指向第一个数据结点，如图2.4(a)所示。在不带头结点的单链表中，头指针L直接指向第一个数据结点，如图2.4(b)所示。无论哪种形式，表尾结点的指针域为NULL（图中用“^”表示）。

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

图2.4 带头结点和不带头结点的单链表

头指针与头结点的关系：头指针始终指向链表的第一个结点（无论带不带头结点），而头结点仅存在于带头结点的链表中，它是链表的第一个结点，其数据域通常不存储实际数据。

引入头结点后，可带来以下两个主要优点：

① 操作统一性：第一个数据结点的位置存储在头结点的指针域中，因此在链表首部进行插入、删除等操作时，与其他位置的操作逻辑一致，无须特殊处理。
② 空表与非空表处理统一：无论链表是否为空，头指针始终是一个非空指针（指向头结点），而空表仅表现为头结点的 next 为 NULL，从而避免了对空表的单独判断。

## 2.3.2 单链表上基本操作的实现

带头结点单链表在操作实现上更为简便。如无特殊说明，本节算法均默认链表带头结点。

### 1. 单链表的初始化

带头结点与不带头结点的单链表在初始化时有所不同。带头结点的单链表初始化时，需创建一个头结点，并令头指针L指向该头结点，其next指针初始化为NULL。

bool InitList(LinkList &L) { //带头结点的单链表初始化

<!-- page: 44 -->

2027年数据结构考研复习指导

```javascript
L=(LNode*)malloc(sizeof(LNode)); //创建头结点①
L->next=NULL; //头结点之后暂无数据结点
return true;


不带头结点的单链表初始化时，只需将头指针L初始化为NULL。

bool InitList(LinkList &L) { //不带头结点的单链表初始化
L=NULL;
return true;
}


**注意**

设 p 为指向链表结点的结构体指针，则*p 表示该结点本身。可通过 p->data 或 (*p).data 访问其数据域，二者完全等价。成员运算符（.）左侧应为结构体变量，指向运算符（->）左侧应为结构体指针。例如，p->next->data 等价于 (*(*p).next).data，表示当前结点后继结点的数据。

## 2. 求表长操作

求表长是指统计单链表中数据结点的个数（不包括头结点）。从第一个数据结点开始依次遍历，为此需要设置一个计数变量，每访问一个结点，其值加1，直到遇到NULL。

int Length(LinkList L) {
int len = 0; //计数变量，初始为0
LNode *p = L;
while (p->next != NULL) {
p = p->next;
len++;
}
return len;
}


求表长操作的时间复杂度为 $O(n)$。

另外，需要注意的是，由于表长不包含头结点，带头结点与不带头结点的实现细节略有不同。

## 3. 按序号查找结点

从单链表的第一个数据结点开始，沿 next 指针逐个查找，返回第 i 个结点的指针；若 i 超出表长，则返回 NULL。

LNode *GetElem(LinkList L, int i) {
LNode *p = L; //指针p指向当前扫描结点
int j = 0; //j记录当前位序，头结点为第0个结点
while (p != NULL && j < i) { //循环找到第i个结点
p = p->next;
j++;
}
return p; //返回第i个结点的指针或NULL
}


按序号查找操作的时间复杂度为 $O(n)$。

## 4. 按值查找表结点

从单链表的第一个数据结点开始，依次比较各结点的数据域，若等于给定值 e，则返回该结点指针；否则返回 NULL。

LNode *LocateElem(LinkList L, ElemType e) {
LNode *p = L->next;
while (p != NULL && p->data != e) //从第一个结点开始查找数据域为e的结点
}


① 执行 s = (LNode*)malloc(sizeof(LNode)) 的作用是由系统生成一个 LNode 型结点，并将该结点的起始位置赋给指针变量 s。

<!-- page: 45 -->

第2章 线性表
33

p=p-&amp;gt;next;
return p; //找到后返回该结点指针，否则返回NULL
}


按值查找操作的时间复杂度为 $O(n)$。

## 5. 插入结点操作

**考点图15** ⇒ 单链表插入操作的过程（2016、2024）

将值为 e 的新结点插入到第 i 个位置（成为新的第 i 个数据结点）。先检查 i 的合法性，然后找到第 i-1 个结点（前驱），再在其后插入新结点。假设找到的第 i-1 个结点为*p，然后令新结点*s 的 next 指向*p 的后继，再令*p 的 next 指向*s，如图 2.5 所示。

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

图 2.5 单链表的插入操作

bool ListInsert(LinkList &L,int i,ElemType e){
LNode *p=L; //p 指向当前扫描结点
int j=0; //j 记录当前位序，头结点为第 0 个结点
while(p!=NULL&&j<i-1){ //循环找到第 i-1 个结点
p=p->next;
j++;
}
if(p==NULL) //i 值不合法
return false;
LNode *s=(LNode*)malloc(sizeof(LNode));
s->data=e;
s->next=p->next; //图 2.5 中操作步骤①
p->next=s; //图 2.5 中操作步骤②
return true;
}


步骤①和②的顺序不可颠倒。若先执行 p->next=s，则原后继地址丢失，导致 s->next=p->next 实际变为 s->next=s，形成自环。该操作的时间复杂度为 $O(n)$，主要开销在于查找前驱结点。若已知某结点指针，则在其后插入新结点的时间复杂度为 $O(1)$。注意，当插入位置 i=1 时，不带头结点的单链表需要更新头指针 L 指向新首结点，而带头结点的则无须特殊处理。

扩展：对某个结点进行前插操作。

前插操作是指在某结点前插入一个新结点，与后插操作相反。任何前插操作均可转化为后插操作：只需从头结点开始顺序查找其前驱，时间复杂度为 $O(n)$。若对给定结点进行前插，则还可采用另一种技巧（适用于数据可复制的情况）：将新结点*s 插入目标结点*p 之后，再交换*p 与*s 的数据域。这种技巧逻辑上等效于前插，且时间复杂度为 $O(1)$。主要代码片段如下：

s->next=p->next; //修改指针域，不能颠倒
p->next=s;
temp=p->data; //交换数据域部分
p->data=s->data;
s->data=temp;


## 6. 删除结点操作

删除单链表的第 i 个数据结点。先检查 i 的合法性，然后找到第 i-1 个结点（前驱），再删

<!-- page: 46 -->

2027年数据结构考研复习指导

除其后继结点，并释放内存。假设找到的第i-1个结点为 $^*p$，其后继为被删结点 $^*q$，先将 $^*p$ 的next指向 $^*q$ 的后继结点，然后释放 $^*q$ 的存储空间，如图2.6所示。

原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。

图2.6 单链表结点的删除

bool ListDelete(LinkList &L,int i,ElemType &e){
LNode *p=L; //指针p指向当前扫描到的结点
int j=0; //记录当前结点的位序，头结点是第0个结点
while(p->next!=NULL&&j<i-1){ //循环找到第i-1个结点
p=p->next;
j++;
}
if(p->next==NULL||j>i-1) //i值不合法
return false;
LNode *q=p->next; //令q指向被删除结点
e=q->data; //用e返回元素的值
p->next=q->next; //将*q结点从链中“断开”
free(q); //释放结点的存储空间
return true;
}


类似于插入操作，该操作的主要耗时也在查找操作上，时间复杂度为 $O(n)$。

当链表不带头结点时，需判断被删结点是否为首结点，若是，则要做特殊处理，将头指针L指向新的首结点。当链表带头结点时，删除首结点和删除其他结点的操作是相同的。

扩展：删除给定结点 $^*p$ 。

常规方法需要从头遍历找到 $^*p$ 的前驱，时间复杂度为 $O(n)$。若允许修改结点内容，则可采用一种 $O(1)$ 的技巧：将 $^*p$ 的后继结点的数据复制到 $^*p$ 中，然后删除其后继结点。该方法的局限性在于不能用于删除尾结点（因其无后继）。主要代码片段如下：

```c
LNode *q=p->next; //令q指向*p的后继结点
p->data=p->next->data; //用后继结点的数据域覆盖
p->next=q->next; //将*q结点从链中“断开”
free(q); //释放后继结点的存储空间
```