C++链表实现数据集合归并算法

1. 概述

本文介绍如何使用 C++ 语言中的链表数据结构实现数据集合的归并算法。归并算法是将两个或多个有序的数据集合合并成一个新的有序数据集合的算法，是计算机科学中一种常用的排序算法。

2. 代码实现c++#include<stdio.h>#include<stdlib.h>#includeusing namespace std;

// 定义链表节点结构体typedef struct lianbiao { int n; lianbiao *next; int i;} lian, *liandi;

// 初始化链表void IniList(liandi &s) { s = new lian; s->next = NULL; s->i = 0;}

// 向链表尾部插入节点void put(liandi &s, int x) { liandi p; if (s->i == 0) { s->n = x; s->i = 1; } else { p = new lian; p->n = x; p->next = s; s = p; s->i = 1; }}

// 获取链表中指定位置的元素值int out(liandi &s, int &x, int i) { int j; liandi p; p = s; for (j = 1; j < i; j++) { p = p->next; } if (p == NULL) return 0; x = p->n; return 1;}

// 打印链表void Print(liandi s) { cout << 'The current List is:' << endl; for (int i = 0; s != NULL; i++) { cout << s->n; if (s->next != NULL) { cout << ','; } s = s->next; } cout << endl;}

// 在链表指定位置插入节点void charu(liandi &s, int x, int i) { liandi p, q; p = new lian; p->n = x; if (i == 1) { p->next = s; s = p; } else { p->next = NULL; q = s; for (int j = 1; j < i - 1; j++) { q = q->next; } p->next = q->next; q->next = p; }}

int main() { int n, x, a = 0, b = 0; liandi l1, l2; IniList(l1); IniList(l2);

// 输入数据表1的元素个数    cin >> n;    if (n == 0) { // 处理特殊情况：数据表1为空        cin >> n;         for (int i = 0; i < n; i++) {            cin >> x;            put(l2, x);        }        Print(l2);        return 0;    }

// 输入数据表1的元素值    for (int i = 0; i < n; i++) {        cin >> x;        put(l1, x);    }

// 输入数据表2的元素个数    cin >> n;    if (n == 0) { // 处理特殊情况：数据表2为空        Print(l1);        return 0;    }

// 输入数据表2的元素值    for (int i = 0; i < n; i++) {        cin >> x;        put(l2, x);    }

// 归并两个链表    int i = 1;    int j = 1;    while (out(l2, b, j)) {        out(l1, a, i);        if (b < a || !out(l1, a, i)) {            charu(l1, b, i);            j++;        } else {            i++;        }    }

// 打印归并后的链表    Print(l1);    system('pause');    return 0;}

3. 运行情况及分析

3.1 测试数据

测试数据1：

数据表1元素个数：3* 数据表1元素值（逆序）：22 21 19* 数据表2元素个数：4* 数据表2元素值（逆序）：92 91 31 2

测试数据2：

数据表1元素个数：5* 数据表1元素值（逆序）：10 8 6 4 2* 数据表2元素个数：4* 数据表2元素值（逆序）：9 7 5 3

3.2 运行结果

测试数据1运行结果：

The current List is:2,19,21,22,31,91,92

测试数据2运行结果：

The current List is:2,3,4,5,6,7,8,9,10

3.3 分析讨论

该代码通过链式存储结构实现了数据集合的归并问题。实验中，首先根据输入的数据表1元素个数创建并初始化链表l1；然后按逆序将数据表1的元素值插入到链表l1中；接着根据输入的数据表2元素个数创建并初始化链表l2；再按逆序将数据表2的元素值插入到链表l2中。

然后利用 out 函数从链表 l1 和 l2 中依次取出元素，并通过 charu 函数将较小的元素插入到链表 l1 中的正确位置。具体实现中，使用两个变量 a 和 b 分别存储链表 l1 和 l2 中取出的元素值。通过比较 b 和 a 的大小，决定是否需要插入 b 到 l1 中，并通过 i 和 j 控制插入位置的变化。

最后，通过 Print 函数遍历并输出归并后的链表 l1 的元素值，即合并后的结果。

根据测试数据和运行结果，可以看到合并后的元素值按照从小到大的顺序排列，并且没有重复的元素。因此，可以得出结论该代码能够正确实现数据集合的归并问题。

4. 总结

本文介绍了如何使用 C++ 链表实现数据集合的归并算法，并提供了详细的代码示例、测试数据、运行结果和分析讨论。通过学习本文，读者可以了解归并算法的基本思想，并能够使用 C++ 语言实现该算法。