C语言顺序表合并算法实现 - 有序插入与合并操作 - 常规

C语言顺序表合并算法实现 - 有序插入与合并操作

本文将使用 C 语言实现顺序表合并算法，通过有序插入构建两个有序表，并利用比较函数进行有序合并，最后打印合并后的结果。

1. 代码实现

#include <stdio.h>
#include <stdlib.h>

// 定义顺序表结构体
typedef struct {
    int* data;       // 数据指针
    int length;      // 当前长度
    int maxSize;     // 最大容量
} SeqList;

// 初始化顺序表
void initList(SeqList* L, int maxSize) {
    L->data = (int*)malloc(maxSize * sizeof(int));
    L->length = 0;
    L->maxSize = maxSize;
}

// 比较函数，用于判断元素大小
int compare(int a, int b) {
    if (a < b) {
        return -1;
    } else if (a > b) {
        return 1;
    } else {
        return 0;
    }
}

// 有序插入元素
void orderInsert(SeqList* L, int data, int (*compare)(int, int)) {
    int i = L->length - 1;
    while (i >= 0 && compare(L->data[i], data) > 0) {
        L->data[i + 1] = L->data[i];
        i--;
    }
    L->data[i + 1] = data;
    L->length++;
}

// 构造有序表
void orderInput(SeqList* L, int (*compare)(int, int)) {
    int data;
    printf('请输入要插入的元素（-1表示结束输入）：\n');
    while (1) {
        scanf('%d', &data);
        if (data == -1) {
            break;
        }
        orderInsert(L, data, compare);
    }
}

// 合并两个有序表
void orderMerge(SeqList* La, SeqList* Lb, SeqList* Lc, int (*compare)(int, int)) {
    int i = 0, j = 0, k = 0;
    while (i < La->length && j < Lb->length) {
        if (compare(La->data[i], Lb->data[j]) <= 0) {
            Lc->data[k] = La->data[i];
            i++;
        } else {
            Lc->data[k] = Lb->data[j];
            j++;
        }
        k++;
    }
    while (i < La->length) {
        Lc->data[k] = La->data[i];
        i++;
        k++;
    }
    while (j < Lb->length) {
        Lc->data[k] = Lb->data[j];
        j++;
        k++;
    }
    Lc->length = k;
}

// 打印顺序表
void printList(SeqList L) {
    printf('顺序表的结果为：\n');
    for (int i = 0; i < L.length; i++) {
        printf('%d ', L.data[i]);
    }
    printf('\n');
}

int main() {
    SeqList La, Lb, Lc;
    int maxSize;

    printf('请输入顺序表的最大容量：');
    scanf('%d', &maxSize);

    initList(&La, maxSize);
    initList(&Lb, maxSize);
    initList(&Lc, maxSize * 2);

    printf('构造有序表La：\n');
    orderInput(&La, compare);

    printf('构造有序表Lb：\n');
    orderInput(&Lb, compare);

    printf('有序表La：');
    printList(La);

    printf('有序表Lb：');
    printList(Lb);

    orderMerge(&La, &Lb, &Lc, compare);

    printf('合并后的有序表Lc：');
    printList(Lc);

    free(La.data);
    free(Lb.data);
    free(Lc.data);

    return 0;
}

2. 代码解释

结构体定义： SeqList 结构体用于表示顺序表，包含数据指针 data、当前长度 length 和最大容量 maxSize。
初始化顺序表： initList 函数用于初始化顺序表，分配内存空间并设置初始长度和最大容量。
比较函数： compare 函数用于比较两个元素的大小，返回 -1 表示第一个元素小于第二个元素，返回 1 表示第一个元素大于第二个元素，返回 0 表示两个元素相等。
有序插入元素： orderInsert 函数用于将一个元素有序插入到顺序表中。首先从后往前遍历顺序表，找到第一个比插入元素小的元素，将该元素及后面的元素往后移动一位，最后将插入元素插入到空出的位置。
构造有序表： orderInput 函数用于从键盘输入元素，并调用 orderInsert 函数将元素有序插入到顺序表中，直到输入 -1 结束。
合并两个有序表： orderMerge 函数用于将两个有序表合并成一个新的有序表。首先分别从两个有序表的开头开始比较，将较小的元素放入新的有序表中，并移动相应指针，直到其中一个有序表遍历完成。最后将剩余的元素加入到新的有序表中。
打印顺序表： printList 函数用于打印顺序表的元素。
主函数： main 函数用于测试上述函数，首先初始化三个顺序表，然后分别从键盘输入元素构造两个有序表，最后合并两个有序表并打印结果。

3. 流程图

┌─────────────┐
│    开始    │
└───────┬─────┘
        │
        ▼
┌─────────────┐
│ 初始化顺序表  │
└───────┬─────┘
        │
        ▼
┌─────────────┐
│   构造有序表  │
└───────┬─────┘
        │
        ▼
┌─────────────┐
│   打印顺序表  │
└───────┬─────┘
        │
        ▼
┌─────────────┐
│ 合并有序表   │
└───────┬─────┘
        │
        ▼
┌─────────────┐
│   打印合并后表  │
└───────┬─────┘
        │
        ▼
┌─────────────┐
│    结束    │
└─────────────┘

4. 总结

本文介绍了使用 C 语言实现顺序表合并算法的方法，并通过代码示例和流程图进行了说明。希望本文能够帮助读者理解顺序表的合并算法，并将其应用到实际开发中。

5. 参考资料