目录

求解一般集合的并集问题

 顺序有序表的合并

 链式有序表的合并

求解一般集合的并集问题

求解集合的并集可以使用线性表来实现。可以将每个集合看作一个线性表，然后将它们合并成一个新的线性表。
假设有两个集合 A 和 B，它们分别表示为线性表 AList 和 BList。要求它们的并集 C，可以按照以下步骤进行操作：

• 创建一个空线性表 CList，用于存放并集。
• 将 AList 中的所有元素依次插入到 CList 中，确保不重复。
• 将 BList 中的所有元素依次插入到 CList 中，确保不重复。
• 输出 CList 中的所有元素，即为集合 A 和 B 的并集。
   

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100// 线性表结构体定义
typedef struct {int data[MAX_SIZE];  // 线性表数据int length;          // 线性表长度
} List;// 初始化线性表
void initList(List* list) {list->length = 0;
}// 向线性表中插入元素
void insertList(List* list, int value) {if (list->length >= MAX_SIZE) {printf("Error: list is full.\\n");return;}for (int i = 0; i < list->length; i++) {if (list->data[i] == value) {return;  // 已存在相同元素，不需要插入}}list->data[list->length] = value;list->length++;
}// 求解两个集合的并集
void unionSet(List* AList, List* BList, List* CList) {initList(CList);// 将 AList 中的所有元素插入到 CList 中for (int i = 0; i < AList->length; i++) {insertList(CList, AList->data[i]);}// 将 BList 中的所有元素插入到 CList 中for (int i = 0; i < BList->length; i++) {insertList(CList, BList->data[i]);}
}int main() {List AList, BList, CList;// 初始化集合 AinitList(&AList);insertList(&AList, 1);insertList(&AList, 2);insertList(&AList, 3);insertList(&AList, 4);insertList(&AList, 5);// 初始化集合 BinitList(&BList);insertList(&BList, 4);insertList(&BList, 5);insertList(&BList, 6);insertList(&BList, 7);insertList(&BList, 8);// 求解并集unionSet(&AList, &BList, &CList);// 输出并集printf("Union set: ");for (int i = 0; i < CList.length; i++) {printf("%d ", CList.data[i]);}
}

 顺序有序表的合并

顺序有序表的合并可以使用类似于归并排序的思想，将两个有序表合并成一个有序表。

假设有两个有序表 A 和 B，它们的长度分别为 m 和 n，我们要将它们合并成一个新的有序表 C，长度为 m+n。
具体的实现过程可以按照以下步骤进行：

• 定义三个指针，分别指向 AList、BList和 CList 的初始位置
• 比较 AList和 BList 的元素的大小，将较小值放入 CList 中
• 将剩余的元素依次放入 CList 中
• 合并完成，返回 CList
   

#include<stdio.h>
#include<stdlib.h>#define MaxSize 100typedef struct {int data[MaxSize];int length;
}SqList;void initSqlist(SqList* list){//初始化顺序有序表 list->length=0;
}void insertSqList(SqList* list,int value){//向顺序有序表中插入元素 if(list->length>=MaxSize){printf("Error: list is full.\\n");return;}int i;for(i=0;i<list->length;i++){if(list->data[i]==value){break;//找到第一个大于等于 value 的元素位置 }}//将后面的元素后移for(int j=list->length;j>i;j--){list->data[j]=list->data[j-1];} list->data[i]=value;list->length++;
}//合并两个有序表
void MergeSqList(SqList* AList,SqList* BList,SqList *CList) {initSqlist(CList);int i=0,j=0;while(i<AList->length&&j<BList->length){//依次摘取两表中值较小的结点插入到CList的最后 if(AList->data[i]<=BList->data[j]){insertSqList(CList,AList->data[i]);i++;}else{insertSqList(CList,BList->data[j]);j++;}}while(i<AList->length){//BList已达表尾，依次将AList的剩余元素插入CList的最后 insertSqList(CList,AList->data[i]);i++;}while(j<BList->length){//AList已达表尾，依次将BList的剩余元素插入CList的最后 insertSqList(CList,BList->data[j]);j++;}	
}
int main() {SqList AList,BList,CList;initSqlist(&AList);insertSqList(&AList,1);insertSqList(&AList,3);insertSqList(&AList,4);insertSqList(&AList,6);insertSqList(&AList,7);initSqlist(&BList);insertSqList(&BList,2);insertSqList(&BList,5);insertSqList(&AList,8);insertSqList(&AList,9);insertSqList(&AList,10);MergeSqList(&AList,&BList,&CList);printf("Merged list: ");for (int i = 0; i < CList.length; i++) {printf("%d ", CList.data[i]);}return 0;
}

 链式有序表的合并

链式有序表的合并可以分为以下步骤：

• 创建一个新的链式有序表，用于存储合并后的数据。
• 分别从两个有序表的头部开始遍历，比较两个表中当前节点的大小，将较小的节点插入到新表的尾部。
• 如果两个表中某一个表已经遍历完了，则将另一个表中剩余的节点插入到新表的尾部。
• 最后，新表中就是合并后的有序数据。
• 具体实现时需要注意链表的操作，包括链表的遍历、节点的插入和删除等，同时还需要考虑如何实现两个表的合并操作。

  #include<stdio.h>
  #include<stdlib.h>// 定义链表节点
  typedef struct ListNode {int data;  // 节点数据struct ListNode *next;  // 指向下一个节点的指针
  } ListNode;// 创建新节点
  ListNode *new_node(int data) {ListNode *node = (ListNode *)malloc(sizeof(ListNode));  // 分配内存node->data = data;node->next = NULL;return node;
  }// 插入新节点
  void insert_node(ListNode head, int data) {ListNode *node = new_node(data);  // 创建新节点ListNode *curr = *head;if (*head == NULL || data < (*head)->data) {  // 如果链表为空或者插入的数据比头节点小，将新节点设为头节点node->next = *head;*head = node;}else {  // 否则找到合适的位置插入while (curr->next != NULL && curr->next->data < data) {curr = curr->next;}node->next = curr->next;curr->next = node;}
  }// 合并链表
  ListNode *merge_lists(ListNode *list1, ListNode *list2) {ListNode *merged = NULL;  // 合并后的链表while (list1 != NULL && list2 != NULL) {  // 遍历两个链表if (list1->data < list2->data) {  // 将较小的节点插入到合并链表中insert_node(&merged, list1->data);list1 = list1->next;}else {insert_node(&merged, list2->data);list2 = list2->next;}}// 将剩余的节点插入到合并链表中while (list1 != NULL) {insert_node(&merged, list1->data);list1 = list1->next;}while (list2 != NULL) {insert_node(&merged, list2->data);list2 = list2->next;}return merged;  // 返回合并后的链表
  }// 输出链表
  void print_list(ListNode *head) {ListNode *curr = head;while (curr != NULL) {printf("%d ", curr->data);curr = curr->next;}printf("\\n");
  }// 主函数
  int main() {// 创建两个有序链表ListNode *list1 = NULL;ListNode *list2 = NULL;insert_node(&list1, 1);insert_node(&list1, 3);insert_node(&list1, 5);insert_node(&list2, 2);insert_node(&list2, 4);insert_node(&list2, 6);// 合并链表ListNode *merged = merge_lists(list1, list2);// 输出合并后的链表printf("Merged list: ");print_list(merged);return 0;
  }
  

  我们首先定义了一个链表节点结构体ListNode，它包括两个成员变量：data和next。其中，data表示节点的数据，next是指向下一个节点的指针。

  接下来我们实现了new_node函数，用于创建新节点。这个函数会动态分配内存，并将节点的data设置为给定值，next设置为NULL，然后返回指向新节点的指针。

  我们还实现了insert_node函数，用于向有序链表中插入新节点。这个函数接受两个参数：一个指向链表头节点的指针head和待插入节点的数据data。如果链表为空，或者待插入节点的数据小于头节点的数据，那么我们将新节点作为头节点；否则，我们遍历链表，找到合适的位置插入新节点。

  接着，我们实现了merge_lists函数，用于合并两个有序链表。这个函数接受两个参数：待合并的两个链表list1和list2。我们通过遍历两个链表，将较小的节点插入到合并链表中。最后，我们再将剩余的节点插入到合并链表中，并返回合并后的链表。

  最后，我们定义了print_list函数，用于输出链表中的元素。它接受一个指向链表头节点的指针head，然后遍历链表，输出每个节点的数据。

  在主函数中，我们创建了两个有序链表，并将它们合并成一个有序链表。然后我们输出合并后的链表。