C语言实现有序表交集和并集操作

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

// 定义有序表结构体 struct SortedList { int* elements; int length; };

// 初始化有序表 struct SortedList* initSortedList(int* arr, int length) { struct SortedList* list = (struct SortedList*)malloc(sizeof(struct SortedList)); list->length = length; list->elements = (int*)malloc(length * sizeof(int)); for (int i = 0; i < length; i++) { list->elements[i] = arr[i]; } return list; }

// 打印有序表 void printSortedList(struct SortedList* list) { for (int i = 0; i < list->length; i++) { printf("%d ", list->elements[i]); } printf("\n"); }

// 有序表交集 struct SortedList* intersect(struct SortedList* list1, struct SortedList* list2) { struct SortedList* result = (struct SortedList*)malloc(sizeof(struct SortedList)); result->length = 0; result->elements = (int*)malloc(list1->length * sizeof(int));

int i = 0, j = 0, k = 0;
while (i < list1->length && j < list2->length) {
    if (list1->elements[i] == list2->elements[j]) {
        result->elements[k++] = list1->elements[i];
        i++;
        j++;
        result->length++;
    }
    else if (list1->elements[i] < list2->elements[j]) {
        i++;
    }
    else {
        j++;
    }
}

return result;

}

// 有序表并集 struct SortedList* unionSet(struct SortedList* list1, struct SortedList* list2) { struct SortedList* result = (struct SortedList*)malloc(sizeof(struct SortedList)); result->length = 0; result->elements = (int*)malloc((list1->length + list2->length) * sizeof(int));

int i = 0, j = 0, k = 0;
while (i < list1->length && j < list2->length) {
    if (list1->elements[i] == list2->elements[j]) {
        result->elements[k++] = list1->elements[i++];
        j++;
        result->length++;
    }
    else if (list1->elements[i] < list2->elements[j]) {
        result->elements[k++] = list1->elements[i++];
        result->length++;
    }
    else {
        result->elements[k++] = list2->elements[j++];
        result->length++;
    }
}

while (i < list1->length) {
    result->elements[k++] = list1->elements[i++];
    result->length++;
}

while (j < list2->length) {
    result->elements[k++] = list2->elements[j++];
    result->length++;
}

return result;

}

int main() { int arr1[] = {1, 3, 5, 7, 9}; int arr2[] = {2, 4, 5, 6, 8}; struct SortedList* list1 = initSortedList(arr1, 5); struct SortedList* list2 = initSortedList(arr2, 5);

printf("有序表1：");
printSortedList(list1);
printf("有序表2：");
printSortedList(list2);

struct SortedList* intersectList = intersect(list1, list2);
printf("交集：");
printSortedList(intersectList);

struct SortedList* unionList = unionSet(list1, list2);
printf("并集：");
printSortedList(unionList);

free(list1->elements);
free(list1);
free(list2->elements);
free(list2);
free(intersectList->elements);
free(intersectList);
free(unionList->elements);
free(unionList);

return 0;

}