实验要求：在实验二的基础上，使用单链表表示集合，编写三个算法（求交算法、求并算法、集合求差），并输出最终的结果。
例如：
集合A为（3、4、1、6），集合B为（2、3、6、7）
交集为：（3、6）
并集为：（1、2、3、4、6、7）
差集为：（1、4）
（注意：差集C=A-B,即属于A但不属于B的素的集合）

#include<iostream> using namespace std; #define ElemType char typedef struct LNode // 定义结构体 { 
    ElemType data; // 结点的数据域 struct LNode* next; // 结点的指针域 }LNode, * LinkList; // LNode定义头指针，*LinkList定义其他结点的指针变量 void InitList(LinkList& L) // 初始化链表 { 
    L = new LNode; // 生成新结点作为头结点，并使头指针L指向头结点 L->next = NULL; // 将头结点的指针域置空 } void ListInsertLast(LinkList& L) // 尾插法 { 
    LinkList p = L; while (p->next != NULL) // 将指针p遍历到链表结束 { 
    p = p->next; } cout << "请输入你要插入的素（输入0退出）：" << endl; ElemType x; while (1) { 
    cin >> x; if (x == '0') // 判断是否结束尾插 break; LNode* s = new LNode; // 创建一个新结点 // 将新结点插入链表结尾 s->data = x; s->next = NULL; p->next = s; p = s; } } void ListInsert(LinkList& L, int i, ElemType e) // 在链表中第 i 个位置插入一个数据素 e { 
    LinkList p = L; // 创建一个临时指针 int j = 0; while (p->next != NULL && (j < i - 1)) // 遍历链表，使指针p指向插入位置前结点 { 
    p = p->next; j++; } LNode* s = new LNode; // 创建一个新结点 s->data = e; // 将新结点插入相应位置 s->next = p->next; p->next = s; } void OutPutAll(LinkList& L) // 输出链表L中所有素 { 
    LinkList p = L->next; // 跳过头结点，使p指向链表的第一个素 cout << "中的素如下：" << endl; while (p != NULL) // 遍历输出 { 
    cout << p->data << "\t"; p = p->next; } cout << endl; } void OutLength(LinkList& L) // 输出链表L的长度 { 
    LinkList p = L->next; // 跳过头结点，使p指向链表的第一个素 int i = 0; while (p != NULL) // 遍历计数 { 
    i++; p = p->next; } cout << "该链表的长度为：" << i << endl; // 输出线性表长度 } void IfNull(LinkList& L) // 判断线性表是否为空 { 
    if (L->next == NULL) cout << "该线性表为空！" << endl; else cout << "该线性表不为空！" << endl; } void OutPut(LinkList& L, int i) // 输出链表L的第i位素 { 
    int j = 0; LinkList p = L->next; // 跳过头结点，使p指向链表的第一个素 while (1) { 
    if (p == NULL) // 若遍历过程中始终没有找到该素 则输出“该线性表长度不够” { 
    cout << "该线性表长度不够！" << endl; return; } if (j == i - 1) // 若在遍历完成前找到该素 则输出 { 
    cout << "第" << i << "个素为：" << p->data << endl; return; } p = p->next; j++; } } void LocateElem(LinkList& L, ElemType e) // 输出链表L中某素的位置 { 
    LinkList p = L->next; // 跳过头结点，使p指向链表的第一个素 int i = 1; while (p != NULL) // 遍历链表 { 
    if (p->data == e) // 查找到对应素 并输出其位置 { 
    cout << "素 " << e << " 在第" << i << "位。" << endl; return; } p = p->next; i++; } cout << "未查到素" << e << endl; // 若未查到 则输出 "未查到素" } void Delete(LinkList& L, int i) // 删除单链表 L 中的第 i 个素  { 
    LinkList p = L; // 使p指向头结点 int j = 0; while (p != NULL) // 遍历链表 { 
    if (j == i - 1) // 遍历到要删除的素的位置时 删除对应素并跳出函数 { 
    p->next = p->next->next; return; } p = p->next; j++; } cout << "该线性表长度不够！" << endl; // 若始终没有遍历到 则输出 "该线性表长度不够！" } void unSortList(LinkList& L) // 单链表“原地”逆转 { 
    LinkList p1, p2; // 定义两个结构体指针 p1 = L->next; L->next = NULL; while (p1 != NULL) // 不断断开结点 插入头结点与第一个数据素之间 { 
    p2 = p1->next; p1->next = L->next; L->next = p1; p1 = p2; } } void ShowList() // 菜单展示 { 
    cout << "*" << endl; cout << " --------功能选项-------- " << endl; cout << " 1.采用尾插法连续插入素 " << endl; cout << " 2.输出单链表 " << endl; cout << " 3.输出单链表长度 " << endl; cout << " 4.判断单链表是否为空 " << endl; cout << " 5.输出单链表的第 i 个素 " << endl; cout << " 6.输出某素的位置 " << endl; cout << " 7.插入素 " << endl; cout << " 8.删除单链表中的第 i 个素 " << endl; cout << " 9.单链表“原地”逆转 " << endl; cout << " 0.结束程序 " << endl; cout << "*" << endl; cout << " --------新增选项-------- " << endl; cout << " 10.求交集（求交算法） " << endl; cout << " 11.求并集（求并算法） " << endl; cout << " 12.求差集（集合求差） " << endl; cout << "*" << endl; cout << " >> 请输入您的选项:" << endl; cout << " >> "; } // // 实验三 新增函数  void Merge_jiao(LinkList& La, LinkList& Lb) // 求交集算法 { 
    LinkList pa = La; // 为La创建一个临时指针 LinkList pb; // 为Lb创建一个临时指针 LinkList p; // 临时指针 用于释放空间 while (pa->next != NULL) // 遍历链表La 始终使用指针的下一个数据 { 
    int t = 1; // 作为判断是否重复的依据  // 0 -> 重复  // 1 -> 不重复  pb = Lb->next; while (pb != NULL) { 
    if (pa->next->data == pb->data) { 
    t = 0; // 记录 并跳出  break; } pb = pb->next; } if (t == 1) { 
    p = pa->next; pa->next = pa->next->next; // 不重复则删去  delete p; } else pa = pa->next; // 重复则保留  } cout << "集合A与集合B的交集"; OutPutAll(La); // 输出交集集合  } void Merge_bing(LinkList& La, LinkList& Lb) // 求并集算法 { 
    LinkList pa = La; // 为La创建一个临时指针 LinkList pb; // 为Lb创建一个临时指针 LinkList p; // 临时指针 用于释放空间 while (pa->next != NULL) // 遍历链表La 始终使用指针的下一个数据 { 
    pb = Lb; while (pb->next != NULL) { 
    if (pa->next->data == pb->next->data) { 
    p = pb->next; pb->next = pb->next->next; // 对集合B中的素进行修改  delete p; } else pb = pb->next; } pa = pa->next; } pa->next = Lb->next; // 将集合A与集合B连接  cout << "集合A与集合B的并集"; OutPutAll(La); // 输出并集  } void Merge_cha(LinkList& La, LinkList& Lb) // 求差集算法 { 
    LinkList pa = La; // 为La创建一个临时指针 LinkList pb; // 为Lb创建一个临时指针 LinkList p; // 临时指针 用于释放空间 while (pa->next != NULL) // 遍历链表La 始终使用指针的下一个数据 { 
    int t = 1; // 记录是否重复  pb = Lb->next; while (pb != NULL) { 
    if (pa->next->data == pb->data) { 
    t = 0; //重复  break; } pb = pb->next; } if (t == 0) // 若重复 则删去 { 
    p = pa->next; pa->next = pa->next->next; delete p; } else // 否则保留  pa = pa->next; } cout << "集合A与集合B的差集"; OutPutAll(La); // 输出差集  } void achieve() { 
    LNode* L; // 创建一个头指针 LNode* La, * Lb; // 为求交、并、差集构造两个头指针 // 1、初始化单链表 InitList(L); // 为头指针创建一个头结点，并使头指针指向该头结点 int i; // 临时存储位置 int select; // 存储选项 ElemType e; // 临时存储数据素 while (1) { 
    ShowList(); cin >> select; if (select == 0) break; switch (select) { 
    case 1: // 2、一次采用尾插法插入a、b、c、d、e素 ListInsertLast(L); cout << "插入后的链表"; OutPutAll(L); break; case 2: // 3、输出单链表 OutPutAll(L); break; case 3: // 4、输出单链表长度 OutLength(L); break; case 4: // 5、判断单链表是否为空 IfNull(L); break; case 5: // 6、输出单链表的第3个素 cout << "请输入i："; cin >> i; OutPut(L, i); break; case 6: // 7、输出素d的位置 cout << "请输入要查找的素："; cin >> e; LocateElem(L, e); break; case 7: // 8、在第4个素位置上插入f素 cout << "请输入要插入的位置："; cin >> i; cout << "请输入要插入的素："; cin >> e; ListInsert(L, i, e); // 9、输出插入后的单链表 cout << "插入后的链表"; OutPutAll(L); break; case 8: // 10、删除单链表中的第2个素 cout << "请输入i："; cin >> i; Delete(L, i); // 11、输出删除后的单链表 cout << "删除后的链表"; OutPutAll(L); break; case 9: // 12、单链表“原地”逆转，要求算法空间复杂度为O（1） unSortList(L); cout << "逆序后的链表"; OutPutAll(L); break; case 10: // 求交集 InitList(La); // 将La初始化 InitList(Lb); // 将La初始化 cout << "下面为对集合A的操作：" << endl; ListInsertLast(La); // A中储存素 cout << "下面为对集合B的操作：" << endl; ListInsertLast(Lb); // B中储存素 Merge_jiao(La, Lb); // 求集合A与B的交集 并输出 delete La; delete Lb; break; case 11: // 求并集 InitList(La); // 将La初始化 InitList(Lb); // 将La初始化 cout << "下面为对集合A的操作：" << endl; ListInsertLast(La); // A中储存素 cout << "下面为对集合B的操作：" << endl; ListInsertLast(Lb); // B中储存素 Merge_bing(La, Lb); // 求集合A与B的并集 并输出 delete La; delete Lb; break; case 12: // 求差集 InitList(La); // 将La初始化 InitList(Lb); // 将La初始化 cout << "下面为对集合A的操作：" << endl; ListInsertLast(La); // A中储存素 cout << "下面为对集合B的操作：" << endl; ListInsertLast(Lb); // B中储存素 Merge_cha(La, Lb); // 求集合A与B的差集 并输出 delete La; delete Lb; break; default: cout << "请输入正确的选项！" << endl; } system("pause"); // 暂停操作 system("cls"); // 清屏操作 } } int main() { 
    achieve(); // 实现函数 return 0; }