考研数据结构——顺序表代码题

顺序表代码题

题目一

设计一个高效算法，将顺序表 $L$ 的所有元素逆置，要求算法的空间复杂度为 $O(1)$。

算法思路

1. 检查空表：首先检查顺序表是否为空，如果为空则输出提示信息并返回错误代码。
2. 双指针法：使用两个指针 left 和 right，分别指向顺序表的首尾元素。通过不断交换这两个指针所指向的元素，直到所有元素被逆置。
3. 异或交换：使用异或操作来交换元素的值，以避免使用额外的空间，保持空间复杂度为 $O(1)$。
4. 结束条件：当 left 大于或等于 right 时，逆置操作完成。

实现代码

// 逆置顺序表的函数
int inverse(SqList *L) {// 检查顺序表是否为空if (L->length == 0) {printf("顺序表为空！");return -1; // 返回错误代码}int left = 0;            // 左指针，指向顺序表的起始位置int right = L->length - 1; // 右指针，指向顺序表的结束位置// 进行元素的交换while (left < right) {// 使用异或操作交换元素L->data[left] = L->data[left] ^ L->data[right]; // 第一步异或L->data[right] = L->data[left] ^ L->data[right]; // 第二步恢复右指针的值L->data[left] = L->data[left] ^ L->data[right]; // 第三步恢复左指针的值left++;  // 左指针向右移动right--; // 右指针向左移动}return 1; // 返回成功代码
}

复杂度分析

• 时间复杂度： $O(n)$，其中 $n$ 是顺序表的长度。每个元素都需要被访问一次。
• 空间复杂度： $O(1)$。算法只使用了常量级的额外空间（指针和几个变量），满足空间复杂度的要求。

题目二

对长度为 $n$ 的顺序表 $L$，编写一个时间复杂度为 $O(n)$、空间复杂度为 $O(1)$ 的算法，该算法删除线性表中所有值为 $x$ 的数据元素。

算法思路

1. 检查空表：首先检查顺序表是否为空。如果为空，则输出提示信息并返回错误代码。
2. 遍历顺序表：使用一个循环遍历顺序表中的每个元素。
3. 覆盖操作：对于每个元素，如果它的值不等于 $x$，则将该元素移到前面，使用一个 index 指针来记录新顺序表的有效元素位置。
4. 更新长度：遍历完成后，更新顺序表的长度为有效元素的数量。

实现代码

// 删除顺序表中所有值为x的元素的函数
int deletX(SqList *L, int x) {// 检查顺序表是否为空if (L->length == 0) {printf("顺序表为空！\n");return -1; // 返回错误代码}int index = 0; // 用于指向新顺序表的索引// 遍历顺序表中的每个元素for (int i = 0; i < L->length; i++) {// 如果当前元素不等于x，则将其移到新顺序表的位置if (L->data[i] != x) {L->data[index++] = L->data[i]; // 覆盖原有元素}}L->length = index; // 更新顺序表长度为有效元素的数量return index; // 返回删除后顺序表的长度
}

复杂度分析

• 时间复杂度： $O(n)$，其中 $n$ 是顺序表的长度。算法遍历了所有元素一次。
• 空间复杂度： $O(1)$。算法只使用了常量级的额外空间（指针和一个变量），符合空间复杂度的要求。

题目三

从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。

算法思路

1. 检查空表：首先检查顺序表是否为空。如果为空，则输出提示信息并返回错误代码。
2. 双指针法：使用两个指针 i 和 j。i 是慢指针，指向新顺序表的有效元素位置，j 是快指针，用于遍历整个顺序表。
3. 比较元素：从第二个元素开始（j 从 1 开始），比较当前元素和慢指针指向的元素。如果它们不相同，则表示找到了一个新的不同元素，将慢指针向前移动并更新该位置的值。
4. 更新长度：遍历结束后，更新顺序表的长度为有效元素的数量。

实现代码

// 从有序顺序表中删除重复元素的函数
int removeDuplicates(SqList *L) {// 检查顺序表是否为空if (L->length == 0) {printf("顺序表为空！\n");return -1; // 返回错误代码}int i = 0; // 初始化慢指针，指向新顺序表的位置for (int j = 1; j < L->length; j++) { // 快指针从1开始// 当发现不同元素时if (L->data[j] != L->data[i]) {i++; // 移动慢指针L->data[i] = L->data[j]; // 复制新元素到新位置}}L->length = i + 1; // 更新顺序表的长度为有效元素的数量return 0; // 返回0表示操作成功
}

复杂度分析

• 时间复杂度： $O(n)$，其中 $n$ 是顺序表的长度。算法只需遍历一次顺序表。
• 空间复杂度： $O(1)$。算法只使用了常量级的额外空间（指针和变量），满足空间复杂度的要求。

题目四

将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。

算法思路

1. 内存分配：首先为新的顺序表 $L3$ 分配内存，并初始化其长度为 0。
2. 双指针法：使用两个指针 $i$ 和 $j$ 分别指向两个输入顺序表 $L1$ 和 $L2$ 的当前元素。同时使用指针 $k$ 来指向新顺序表 $L3$ 的当前位置。
3. 合并过程：
   • 在 $L1$ 和 $L2$ 中遍历元素，比较当前元素的大小，将较小的元素插入新顺序表 $L3$ 中，并移动相应的指针。
   • 当一个顺序表的所有元素都已处理完，直接将另一个顺序表中剩余的元素复制到新顺序表中。
4. 返回结果：最后，返回合并后的新顺序表 $L3$。

实现代码

// 合并两个有序顺序表的函数
SqList* mergeList(SqList *L1, SqList *L2) {// 为新的顺序表分配内存SqList *L3 = (SqList *)malloc(sizeof(SqList));L3->data = (int *)malloc((L1->length + L2->length) * sizeof(int)); // 为数据数组分配内存L3->length = 0; // 初始化新顺序表的长度int i = 0, j = 0, k = 0; // 初始化指针// 合并两个顺序表，直到其中一个表的元素处理完while (i < L1->length && j < L2->length) {if (L1->data[i] <= L2->data[j]) {L3->data[k++] = L1->data[i++]; // 将L1的当前元素插入新表} else {L3->data[k++] = L2->data[j++]; // 将L2的当前元素插入新表}}// 将L1中剩余的元素复制到新表while (i < L1->length) {L3->data[k++] = L1->data[i++];}// 将L2中剩余的元素复制到新表while (j < L2->length) {L3->data[k++] = L2->data[j++];}L3->length = k; // 设置新顺序表的长度return L3; // 返回新合并的顺序表
}

复杂度分析

• 时间复杂度：$O(n+m)$，其中是顺序表 $n$ 的长度，$m$ 是顺序表 $L2$ 的长度。算法需要遍历两个顺序表的所有元素。
• 空间复杂度：$O(n+m)$。需要额外的空间来存储合并后的顺序表 $L3$，其长度为 $n+m$。

题目五

已知在一维数组 $A[m+n]$中依次存放两个线性表$(a_1,a_2,a_3,\dots ,a_m)$和$(b_1,b_2,b_3,\dots ,b_n)$，编写一个函数将数组中两个顺序表的位置互换。

算法思路

1. 反转函数：编写一个反转的辅助函数 reverse，该函数可以反转数组中指定范围的元素。
2. 交换位置：通过三次反转操作实现两个线性表的互换：
   • 首先，反转第一个线性表（从索引 0 到 $m-1$）。
   • 然后，反转第二个线性表（从索引 $m$ 到 $m+n-1$）。
   • 最后，反转整个数组（从索引 0 到 $m+n-1$），从而实现两个线性表的位置互换。

实现代码

// 反转顺序表指定范围的函数
void reverse(SqList *L, int left, int right) {while (left < right) {// 交换左右指针所指向的元素int temp = L->data[left];L->data[left] = L->data[right];L->data[right] = temp;left++;right--;}
}// 互换两个线性表的位置的函数
SqList* tranList(SqList *L3, int m, int n) {reverse(L3, 0, m - 1);         // 反转第一个线性表reverse(L3, m, m + n - 1);     // 反转第二个线性表reverse(L3, 0, m + n - 1);     // 反转整个数组return L3;                     // 返回互换后的顺序表
}

复杂度分析

• 时间复杂度：$O(m+n)$，其中 $m$ 和 $n$ 分别是两个线性表的长度。反转操作需要遍历每个元素。
• 空间复杂度： $O(1)$。算法只使用了常量级的额外空间（指针和变量），符合空间复杂度的要求。

题目六

已知一个整数序列 $A=(a_0,a_1,\dots ,a_{n-1})$ ，其中 $0\le a_i<n$ 。若存在 $a_{p_1}=a_{p_2}=\dots =a_{p_m}=x$ 且 $m>\frac{n}{2}$ （ $0\le p_k<n,1<k\le m$ ），则称 $x$ 为 $A$ 的主元素。例如， $A=(0,5,5,3,5,7,5,5)$ ，则 5 为主元素；又如 $A=(0,5,5,3,5,1,5,7)$ ，则 $A$ 中没有主元素。假设 $A$ 中的 $n$ 个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出 $A$ 的主元素。若存在主元素，则输出该元素；否则输出 -1。

要求：

1. 给出算法的基本设计思想。

2. 根据设计思想，用 C 语言描述算法，关键之处给出注释。

3. 说明你所设计算法的时间复杂度和空间复杂度。

算法思路

要在数组中找到主元素，可以使用摩尔投票算法。这个算法的核心思想是利用候选者的性质和计数的逻辑来确定可能的主元素，具体步骤如下：

1. 候选者确定：遍历数组，使用一个计数器维护当前候选主元素的数量。当计数器为零时，选择当前元素作为新的候选主元素，并将计数器重置为1。如果当前元素等于候选主元素，则计数器加一；否则，计数器减一。

2. 验证候选者：遍历数组，统计候选主元素出现的次数，检查其是否满足主元素的条件（出现次数大于 n/2）。

实现代码

int findMajorityElement(int arr[], int n) {int candidate = -1; // 初始化候选主元素int count = 0;      // 初始化计数器// 第一遍扫描，找出候选主元素for (int i = 0; i < n; i++) {if (count == 0) { // 如果计数器为0，更新候选者candidate = arr[i];count = 1; // 重置计数器} else if (arr[i] == candidate) {count++; // 计数器增加} else {count--; // 计数器减少}}// 第二遍扫描，验证候选主元素count = 0; // 重置计数器for (int i = 0; i < n; i++) {if (arr[i] == candidate) {count++; // 统计候选者出现的次数}}// 检查候选者是否是主元素if (count > n / 2) {return candidate; // 返回主元素} else {return -1; // 没有主元素}
}

复杂度分析

• 时间复杂度：
  • 第一次遍历数组寻找候选主元素的时间复杂度为 ( O(n) )。
  • 第二次遍历数组验证候选主元素的时间复杂度也为 ( O(n) )。
  • 总时间复杂度为 ( O(n) )。
• 空间复杂度：
  • 使用了常量空间来存储候选者和计数器，因此空间复杂度为 ( O(1) )。

摩尔投票算法详解

第一遍扫描的原理

利用候选者与计数器的组合来找出可能的主元素。

1. 候选者的选择

• 初始化：

  • 使用一个变量 candidate 来存储当前的候选主元素。
  • 使用一个计数器 count 来记录候选主元素的出现次数。

• 遍历数组：

  • 从数组的第一个元素开始，逐个检查每个元素。

2. 计数器的更新

• 如果 count 为 0：

  • 这意味着没有当前的候选主元素，因此将当前元素设置为候选者，并将 count 设为 1。

• 如果当前元素等于候选者：

  • 计数器 count 加一，表示该元素的出现次数增加。

• 如果当前元素不等于候选者：

  • 计数器 count 减一，表示遇到不同元素，候选者的支持度减小。

3. 为何有效

• 抵消作用：
  • 当计数器减至零时，意味着候选者的出现次数已经被其他不同元素的出现次数抵消。此时，你可以选择下一个元素作为新的候选者。
  • 通过这种方式，最终能够选出一个可能的主元素，即使数组中存在其他元素。

4. 结束时的候选者

• 在遍历完成后，candidate 可能是一个主元素或不可靠的元素。为了确认其是否真的为主元素，需要进行第二遍扫描。

示例

考虑数组 A = {1, 2, 1, 1, 3, 1}：

1. 初始化 candidate = 0 和 count = 0。
2. 遍历数组：
   • 遇到 1，设置 candidate = 1 和 count = 1。
   • 遇到 2，count 减少到 0，重新设置 candidate = 2 和 count = 1。
   • 遇到 1，增加 count，此时 candidate = 1，count 增加到 2。
   • 遇到 1，增加 count，此时 count = 3。
   • 遇到 3，count 减少到 2。

最终，candidate 是 1，在后续验证中发现它的出现次数确实超过了 n/2，所以它是主元素。

第二遍扫描的原因

第一篇扫描中可能会出现误判，可能导致误判的情况主要发生在第一遍扫描中选择候选主元素的逻辑上。以下是一些具体的情况，说明何时可能导致误判：

1. 多个元素出现频率相近

如果数组中有多个元素的出现频率相近，其中没有任何元素的出现次数超过 n/2，但算法可能会错误地选择一个候选者。

示例：
考虑数组 A = {1, 1, 2, 2, 3, 3, 4}：

• 在第一次扫描中，元素 1 和 2 会互相抵消，最终可能导致选择 3 或者 4 作为候选者（具体取决于扫描顺序）。
• 但实际上，所有元素都没有超过 n/2 的出现次数。

2. 边界条件

在数组长度较小的情况下，例如当 n 为偶数时，数组中元素出现的频率可能导致算法无法准确地选出主元素。

示例：
考虑数组 A = {1, 1, 2, 2}：

• 这里 1 和 2 都只出现了 2 次，所以即使算法选择了 1 作为候选者，也无法满足主元素的条件。

3. 无主元素的情况

如果数组中根本就没有主元素，但由于计数器的逻辑，可能在最后返回一个看似有效的候选者。

示例：
考虑数组 A = {5, 6, 7, 5, 6}：

• 5 出现 2 次，6 出现 2 次，7 出现 1 次。最终可能会选出 5 或 6，但没有任何元素满足主元素条件。

题目七

定义三元组 $(a,b,c)$（$a,b,c$ 均为正数）的距离 $D=|a-b|+|b-c|+|c-a|$。给定三个非空整数集合 $S_1,S_2,S_3$，按升序分别存储在三个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组 $(a,b,c)$（$a\in S_1,b\in S_2,c\in S_3$）中的最小距离。例如， S 1 = { − 1 , 0 , 9 } ， S 2 = { − 25 , − 10 , 10 , 11 } ， S 3 = { 2 , 9 , 17 , 30 , 41 } S_1 = \{-1, 0, 9\}，S_2 = \{-25, -10, 10, 11\}，S_3 = \{2, 9, 17, 30, 41\} S1​={−1,0,9}，S2​={−25,−10,10,11}，S3​={2,9,17,30,41} 则最小距离为 $2$，相应的三元组为 $(9,10,9)$。

要求：

1. 给出算法的基本设计思想；
2. 根据设计思想，采用 C 语言描述算法，关键之处给出注释；
3. 说明你所设计算法的时间复杂度和空间复杂度。

算法思想

为了找到所有可能的三元组 $(a,b,c)$（其中 $a\in S_1$，$b\in S_2$，$c\in S_3$）中使距离 $D=|a-b|+|b-c|+|c-a|$ 最小的那个，我们可以利用数组已按升序排列的特性，设计一个高效的算法。具体思路如下：

• 使用三指针法：

  • 初始化三个指针 $i,j,k$，分别指向数组 $S_1$，$S_2$，$S_3$ 的起始位置。

• 迭代寻找最小距离：

  • 在每一步中，计算当前指针所指元素组成的三元组 ($S_1[i],S_2[j],S_3[k]$) 的距离 $D$。

  • 记录当前最小距离 $D_{\text{min}}$ 及其对应的三元组。

  • 为了尽可能缩小距离 $D$，移动当前值最小的那个指针，以尝试找到更接近其他两个值的元素。

• 算法终止条件：

• 当任一指针遍历完其数组时，算法结束。此时已找到最小距离及其对应的三元组。

算法的核心思想：

• 利用升序排列：因为数组是升序的，我们可以通过移动指向最小值的指针，使其增大，从而可能减小与其他两个值的差距。

• 减少不必要的计算：通过智能地移动指针，避免了穷举所有可能的三元组，时间复杂度从 $O(n_1{n}_2{n}_3)$ 降低到 $O(n_1+n_2+n_3)$。

实现代码

// 计算并输出最小距离和对应的三元组
void findMinDistance(int S1[], int n1, int S2[], int n2, int S3[], int n3) {int i = 0, j = 0, k = 0;int minDistance = INT_MAX; // 初始化最小距离为最大整数int a_min = 0, b_min = 0, c_min = 0; // 用于存储最小距离对应的三元组// 当任一数组遍历完毕时，结束循环while (i < n1 && j < n2 && k < n3) {int a = S1[i];int b = S2[j];int c = S3[k];// 计算当前三元组的距离int currentDistance = abs(a - b) + abs(b - c) + abs(c - a);// 如果当前距离小于已记录的最小距离，则更新最小距离和对应的三元组if (currentDistance < minDistance) {minDistance = currentDistance;a_min = a;b_min = b;c_min = c;}// 移动指向最小值的指针，以期望找到更小的距离if (a <= b && a <= c) {i++; // 移动指针 i} else if (b <= a && b <= c) {j++; // 移动指针 j} else {k++; // 移动指针 k}}// 输出结果printf("最小距离为 %d\n", minDistance);printf("对应的三元组为 (%d, %d, %d)\n", a_min, b_min, c_min);
}

代码注释与说明：

• 变量初始化：

  • i, j, k：分别为数组 S1, S2, S3 的指针，初始为 0。

  • minDistance：记录当前找到的最小距离，初始为最大整数 INT_MAX。

  • a_min, b_min, c_min：记录最小距离对应的三元组。

• 主要循环：

  • 条件：当 i < n1 && j < n2 && k < n3，即任一数组未遍历完。

  • 计算当前三元组：取当前指针所指的元素 a, b, c。

  • 计算距离：使用公式 D = |a - b| + |b - c| + |c - a|。

  • 更新最小值：如果当前距离小于已记录的最小距离，则更新 minDistance 和对应的三元组。

• 指针移动策略：

  • 比较 a, b, c 的大小，移动值最小的那个指针。

  • 理由：增大最小值可能减少与其他两个值的差距，从而减小总距离。

• 结束条件：

  • 当任一指针遍历完整个数组，无法再找到新的三元组，算法结束。

• 输出结果：

  • 打印最小距离和对应的三元组。

复杂度分析

时间复杂度：

• 在每次循环中，至少有一个指针（i, j, k）会增加 1。

• 每个指针最多移动到其数组的末尾，最多进行 n1 + n2 + n3 次操作。

• 因此，算法的时间复杂度为 $O(n_1 + n_2 + n_3) $。

空间复杂度：

• 除了输入的数组外，只使用了常数级别的额外空间来存储指针和临时变量。

• 因此，算法的空间复杂度为 $O(1)$。