数据结构实验1.3： 有序顺序表的归并

---

一，问题描述

编程实现将两个顺序存储的有序线性表归并为一个线性表，归并后的线性表仍然有序，要求同样的数据元素只出现一次。

二，基本要求

1. 设计创建有序顺序表的算法（可采用有序直接插入法）；
2. 设计有序顺序表的归并算法；
3. 设计输出顺序表全部元素的算法；
4. 编写求解归并问题的完整程序，设计好测试用例；
5. 上机调试、测试，记录测试结果，对测试结果进行分析。

三，算法分析

由于两个线性表中的元素呈有序排列，在进行合并的时候，依次比较，哪个线性表的元素值小，就先将这个元素复制到新的线性表中，若两个元素相等，则复制一个即可，这样一直到其中的一个线性表结束，然后将剩余的线性表复制到新的线性表中即可。这种基于双指针的归并策略具有较高的时间效率。假设两个有序线性表的长度分别为 m 和 n，在最坏情况下，需要进行 m + n - 1 次比较操作，因此时间复杂度为 O (m + n)。空间复杂度方面，由于需要创建一个新的线性表来存储归并结果，其大小最大为 m + n，所以空间复杂度也为 O (m + n)。同时，在归并过程中额外的操作主要是元素的比较、复制以及指针的移动，这些操作的时间开销相对固定，不会随着数据规模的增加而显著增加，使得该算法在处理大规模有序数据的归并时具有较好的性能表现。

四，示例代码

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int length;
} SqList;// 创建有序顺序表（有序直接插入法）
void CreateOrderedSqList(SqList *L, int arr[], int n) {L->length = 0;for (int i = 0; i < n; i++) {int j = L->length - 1;while (j >= 0 && L->data[j] > arr[i]) {L->data[j + 1] = L->data[j];j--;}L->data[j + 1] = arr[i];L->length++;}
}// 有序顺序表的归并算法
void MergeOrderedSqList(SqList L1, SqList L2, SqList *L3) {int i = 0, j = 0, k = 0;L3->length = 0;while (i < L1.length && j < L2.length) {if (L1.data[i] < L2.data[j]) {if (L3->length == 0 || L1.data[i] != L3->data[L3->length - 1]) {L3->data[L3->length++] = L1.data[i];}i++;} else if (L1.data[i] > L2.data[j]) {if (L3->length == 0 || L2.data[j] != L3->data[L3->length - 1]) {L3->data[L3->length++] = L2.data[j];}j++;} else {if (L3->length == 0 || L1.data[i] != L3->data[L3->length - 1]) {L3->data[L3->length++] = L1.data[i];}i++;j++;}}while (i < L1.length) {if (L3->length == 0 || L1.data[i] != L3->data[L3->length - 1]) {L3->data[L3->length++] = L1.data[i];}i++;}while (j < L2.length) {if (L3->length == 0 || L2.data[j] != L3->data[L3->length - 1]) {L3->data[L3->length++] = L2.data[j];}j++;}
}// 输出顺序表全部元素的算法
void PrintSqList(SqList L) {for (int i = 0; i < L.length; i++) {printf("%d ", L.data[i]);}printf("\n");
}int main() {int arr1[] = {1, 3, 5, 7, 9};int arr2[] = {2, 4, 6, 7, 8, 10};SqList L1, L2, L3;CreateOrderedSqList(&L1, arr1, sizeof(arr1) / sizeof(arr1[0]));CreateOrderedSqList(&L2, arr2, sizeof(arr2) / sizeof(arr2[0]));printf("顺序表L1: ");PrintSqList(L1);printf("顺序表L2: ");PrintSqList(L2);MergeOrderedSqList(L1, L2, &L3);printf("归并后的顺序表L3: ");PrintSqList(L3);return 0;
}

五，运行效果