实验要求

求两个集合LA和LB(用单链表表示)的并和交集
要求：在实验二的基础上，使用单链表表示集合。编写两个算法（求交算法和求并算法），并输出最终的结果。
测试用例：集合A为{3，4，1，6}，集合A为{2，3，6，7}，
交集为{3，6}
并集为{1，2，3，4，6，7}
交作业时间：4月16日

实验代码

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. /**
  5.  * 求两个集合LA和LB(用单链表表示)的并和交集
  6.  */
  9. /* 单链表的存储结构 */
  10. typedef struct LNode {
  11.     int data; //数据域
  12.     struct LNode *next; //指针域
  13. }Lnode, *LinkList; //LinkList为指向结构体LNode的指针类型
  16. /* 初始化链表 */
  17. void InitList(LinkList &L) {
  18.     L = new LNode;
  19.     L->next = NULL;
  20. }
  22. /* 创建：后插 */
  23. void CreateList_R(LinkList &L, int n) {
  24.     cout << "请输入" << n << "个数字"<< "\n";
  25.     InitList(L);
  26.     // 定义一个在下面循环用来一直操作所加元素的结点p来指向头结点L
  27.     LinkList p = L;
  28.     for (int i = 0; i < n;i++) {
  29.         LinkList q = new Lnode;
  30.         q->next = NULL;
  31.         cin >> q->data;
  32.         p->next = q;
  33.         p = q; //为了下一次
  34.     }
  35. }
  37. /* 打印 */
  38. void TraverseList(LinkList & L){
  39.         LinkList p = new LNode;
  40.         p = L->next;
  41.         cout << "此链表打印的结果为："<< "\n";
  42.         while (p != NULL)
  43.         {
  44.             cout << p->data << " ";
  45.             p = p->next;
  46.         }
  47.         cout << "\n";
  48. }
  50. /* 排序单链表 */
  51. void sort(LinkList &L) {
  53. }
  55. /* jiao算法 */
  56. void jiao(LinkList &A,LinkList &B) {
  57.     // 用双循环得出共有的元素并输出
  58.     LinkList p;
  59.     InitList(p);
  60.     A = A->next;
  61.     B = B->next;
  62.     while (A != NULL ) {
  63.         LinkList copy_b = B;
  64.         while(copy_b != NULL) {
  65.             if (A->data == copy_b->data) {
  66.                 LinkList temp = new Lnode;
  67.                 temp->data = copy_b->data;
  68.                 temp->next = p->next;
  69.                 p->next = temp;
  70.                 break;
  71.             } else {
  72.                 copy_b = copy_b->next;
  73.             }
  74.         }
  75.         A = A->next;
  76.     }
  78.     while(p->next != NULL) {
  79.         cout << p->next->data << " ";
  80.         p = p->next;
  81.     }
  82. }
  85. /* bing算法 */
  86. void bing(LinkList &A,LinkList &B) {
  87.     LinkList p = A;
  88.     LinkList s = B;
  90.     A = A->next;
  91.     B = B->next;
  92.     while (A != NULL ) {
  93.         LinkList copy_b = B;
  94.         while(copy_b != NULL) {
  95.             if (A->data == copy_b->data) {
  96.                 // cout << A->data << "\n";
  97.                 // 在p链里面删除A->data值
  98.                 LinkList q = p;
  99.                 while(q->next != NULL) {
  100.                     if (q->next->data == A->data) {
  101.                         q->next = q->next->next;
  102.                         break;
  103.                     } else {
  104.                         q = q->next;
  105.                     }
  106.                 }
  107.                 break;
  108.             } else {
  109.                 copy_b = copy_b->next;
  110.             }
  111.         }
  112.         A = A->next;
  113.     }
  114.     // 将p链表连接到s链表上
  115.     LinkList result = p;
  116.     while (p != NULL) {
  117.         if (p->next == NULL) {
  118.             p->next = s->next;
  119.             break;
  120.         }
  121.         p = p->next;
  122.     }
  123.     while(result->next != NULL) {
  124.         cout << result->next->data << " ";
  125.         result = result->next;
  126.     }
  127. }
  129. int main() {
  130.     LinkList list_A;
  131.     LinkList list_B;
  132.     InitList(list_A);
  133.     InitList(list_B);
  134.     CreateList_R(list_A, 6);
  135.     CreateList_R(list_B, 6);
  136.     LinkList list_C = list_A;
  137.     LinkList list_D = list_B;
  138.     cout <<"A、B交集的值为：";
  139.     jiao(list_A, list_B);
  140.     cout <<"\n"<<"A、B并集的值为：";
  141.     bing(list_C, list_D);
  142. }