C语言实现集合合并、排序和查找 - 附带详细代码示例

需求描述

针对两个包含无序数据元素（可能存在重复元素）的集合，我们需要实现以下功能：

1. 集合合并: 将两个集合合并成一个新的集合，并去除重复元素。2. 排序: 对合并后的集合进行排序。3. 查找: 在排序后的集合中查找指定元素。

代码实现c#include <stdio.h>#include <stdbool.h>

#define MAX_SIZE 100

// 定义顺序表的结构体typedef struct { int data[MAX_SIZE]; int length;} SeqList;

// 初始化顺序表void init(SeqList* list) { list->length = 0;}

// 在顺序表中查找元素的索引int findElement(SeqList* list, int element) { for (int i = 0; i < list->length; i++) { if (list->data[i] == element) { return i; } } return -1; // 若未找到，返回-1}

// 在顺序表中插入元素void insertElement(SeqList* list, int element) { if (list->length == MAX_SIZE) { printf('顺序表已满，无法插入元素！ '); return; }

int index = findElement(list, element);    if (index != -1) {        //printf('元素已存在，无法重复插入！

'); //取消输出提示 return; }

list->data[list->length] = element;    list->length++;}

// 删除顺序表中指定区间内的元素void deleteRange(SeqList* list, int start, int end) { if (start < 0 || end >= list->length || start > end) { printf('无效的区间！ '); return; }

for (int i = start; i <= end; i++) {        for (int j = i + 1; j < list->length; j++) {            list->data[j - 1] = list->data[j];        }        list->length--;    }}

// 移除顺序表中的重复元素void unique(SeqList* list) { for (int i = 0; i < list->length; i++) { for (int j = i + 1; j < list->length; j++) { if (list->data[i] == list->data[j]) { deleteRange(list, j, j); j--; // 删除元素后，需要对当前索引进行调整 } } }}

// 冒泡排序void bubbleSort(int arr[], int length) { for (int i = 0; i < length - 1; i++) { for (int j = 0; j < length - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } }}

// 归并排序void merge(int arr[], int left, int mid, int right) { int i, j, k; int n1 = mid - left + 1; int n2 = right - mid;

int L[n1], R[n2];

for (i = 0; i < n1; i++)        L[i] = arr[left + i];    for (j = 0; j < n2; j++)        R[j] = arr[mid + 1 + j];

i = 0;    j = 0;    k = left;

while (i < n1 && j < n2) {        if (L[i] <= R[j]) {            arr[k] = L[i];            i++;        } else {            arr[k] = R[j];            j++;        }        k++;    }

while (i < n1) {        arr[k] = L[i];        i++;        k++;    }

while (j < n2) {        arr[k] = R[j];        j++;        k++;    }}

void mergeSort(int arr[], int left, int right) { if (left < right) { int mid = left + (right - left) / 2;

    mergeSort(arr, left, mid);        mergeSort(arr, mid + 1, right);

    merge(arr, left, mid, right);    }}

// 折半查找int binarySearch(int arr[], int left, int right, int element) { if (right >= left) { int mid = left + (right - left) / 2;

    if (arr[mid] == element)            return mid;

    if (arr[mid] > element)            return binarySearch(arr, left, mid - 1, element);

    return binarySearch(arr, mid + 1, right, element);    }

return -1; // 若未找到，返回-1}

int main() { SeqList list1, list2; init(&list1); init(&list2);

// 输入两个无序集合的数据元素    insertElement(&list1, 5);    insertElement(&list1, 2);    insertElement(&list1, 9);    insertElement(&list1, 2);    insertElement(&list1, 7);

insertElement(&list2, 4);    insertElement(&list2, 1);    insertElement(&list2, 6);    insertElement(&list2, 9);    insertElement(&list2, 4);

// 合并两个集合，并去除重复元素    for (int i = 0; i < list2.length; i++) {        insertElement(&list1, list2.data[i]);    }    unique(&list1);

// 输出合并后的顺序表    printf('合并后的顺序表：');    for (int i = 0; i < list1.length; i++) {        printf('%d ', list1.data[i]);    }    printf('

');

// 对合并后的顺序表进行排序    //bubbleSort(list1.data, list1.length);  //冒泡排序测试    mergeSort(list1.data, 0, list1.length - 1); //归并排序测试

// 输出排序后的顺序表    printf('排序后的顺序表：');    for (int i = 0; i < list1.length; i++) {        printf('%d ', list1.data[i]);    }    printf('

');

// 在排序后的顺序表中查找元素7    int index = binarySearch(list1.data, 0, list1.length - 1, 7);    if (index != -1) {        printf('元素7在排序后的顺序表中的索引为：%d

', index); } else { printf('元素7不在排序后的顺序表中。 '); }

return 0;}

代码说明

1. 顺序表: 我们使用结构体 SeqList 来表示顺序表，其中 data 数组存储元素，length 表示顺序表中元素的个数。2. 基本操作: 代码中实现了顺序表的初始化、查找元素、插入元素、删除区间和去重等基本操作函数。3. 排序算法: 代码中实现了冒泡排序和归并排序两种算法，你可以根据需要选择使用。4. 查找算法: 代码中实现了折半查找算法，需要在排序后的顺序表上进行查找。5. 主程序: 主程序中定义了两个示例集合，并演示了如何调用上述函数完成集合合并、排序和查找等操作。

测试用例

在主程序中，我们定义了两个示例集合：

• 集合1: {5, 2, 9, 2, 7}* 集合2: {4, 1, 6, 9, 4}

程序运行后，会输出以下结果：

合并后的顺序表：5 2 9 7 4 1 6 排序后的顺序表：1 2 4 5 6 7 9 元素7在排序后的顺序表中的索引为：5

总结

本文介绍了如何使用C语言实现集合合并、排序和查找等操作，并提供了详细的代码示例和测试用例。希望本文能帮助你更好地理解和应用数据结构与算法的相关知识。