数据结构--C语言链表实现集合的（并，交，差）运算！

Love The Way You Lie 2022-12-12 04:57 156阅读 0赞

## 姗姗来迟的链表。 ##

**老规矩，上效果图：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VfdF9lX3Jfbl9pX3RfeQ_size_16_color_FFFFFF_t_70_pic_center]  
**要求：**  
从程序完善性上考虑，集合元素输入时，要有检查元素重复的功能，每个集合中不允许有重复的元素。集合可以用数组也可以用链表存储。  
实现交、并、差运算时，分别把代码写成函数的形式，即实现交运算的函数，实现并运算的函数，实现差运算的函数，在主函数中分别调用三个函数。  
使用菜单形式对应各个操作，应允许用户反复查看结果，想结束程序时，输入负数结束，使其编成一个完整的小软件。菜单参考示例如下：  
1—输入集合A和B  
2—求集合A交B  
3—求集合A并B  
4—求集合A-B  
退出，输入一个负数！  
**验收/测试用例：**  
输入： A=\{1,2,3,4,5\}  
B=\{3,4,5,6,7\}  
要注意输入的过程中，每输入一个元素都要检查输入的这个元素是否和前面的元素重复，如果重复，要求用户重新输入当前元素。  
验收测试时要测试这种重复的情况。  
输出 A交B=\{3， 4， 5\}  
A并B=\{1，2，3，4，5，6，7\}  
A-B=\{1, 2\}  
**代码如下：**

#include <stdio.h>
    #include <stdlib.h>
    #define ERROR -1 
    //创建结构体 
    typedef struct Node{ 
     int data;    
     struct Node *next;   //指向下一个指针 
    }Node,*Link;   //typedef 起别名 ，结尾有分号 
    /* //上面的同这个 struct node{ int data; struct node *next; //指向下一个指针 }; typedef struct Node Node; //为 struct Node类型起别名Node typedef struct Node *Link; //为struct Node 指针类型起别名Link */
    
    //菜单 
    void show (){     
     printf("\t\t--------------集合运算--------------\n");
     printf("\n");
     printf("\t\t\t 1---输入集合A和B\n");
     printf("\t\t\t 2---求集合A交B\n");
     printf("\t\t\t 3---求集合A并B\n");
     printf("\t\t\t 4---求集合A-B\n");
     printf("\t\t\t 退出，输入一个负数！");
     printf("\n");
     printf("\t\t------------------------------------\n");
     printf("\n");
    }
    
    //创建空链表 
    Link list(Link l){ 
     Link head=(Link)malloc(sizeof(Node));         //创建头节点 
     if(head==NULL){           //如果头节点未空 
      return 0;
     }
     l=head;
     l->next =NULL;         //把头节点指针置空，就像把一条直线变成射线 
     return l;
    }
    
    //录入数据，头插法，新的数据指针指向头节点的指针 
    Link input(Link l,int n){ 
     Link p;
     int i;
     printf("请输入元素\n");
     for(i=1;i<=n;i++){ 
      p=(Link)malloc(sizeof(Node));       //开辟新节点，及分配空间 
      if(p!=NULL){               //节点开辟成功 
       scanf("%d",&p->data);   
       p->next=l->next;     //头插 
       l->next=p;
      }else{ 
       return 0;
      }
     }
     printf("集合输入完成\n");
     return l;
    } 
    
    //输出,遍历 
    Link output(Link l){ 
     Link p;
     if(l->next==NULL){ 
      printf("该链表是空链表\n");
     }else{ 
      for(p=l->next;p!=NULL;p=p->next){ 
       printf("%d\t",p->data);
      }
     // printf("\n");
     }
    }
    
    //清空链表
    void clear(Link l){ 
     Link p,q;
     p=l->next;
     if(!p){ 
      return;
     }
     while(p!=NULL){ 
      q=p;
      p=p->next;
      free(q);     //释放节点空间 
     }
     l->next=NULL;       //将l链表的next指针域置空 
     printf("This part is over\n");
    } 
    
    //并集 先清空c，再用a与c比较，b与c比较，将没有的数据全插入
    Link hand(Link La,Link Lb,Link Lc){ 
     Link r,s,p,q;
     p=La->next;
     while (p){ 
      q=(Link)malloc(sizeof(Node));       //生成新的节点 
      q->data=p->data;
      q->next=Lc->next;             //1.将c的指针赋给q 
      Lc->next=q;                   //2.再使c的指针指向q（ 头插法 ）
      p=p->next;                    //用p遍历a链表 
     }
     /* //方法2：尾插法插a p=La->next; r=Lc; //将头指针地址赋给r，不能直接用Lc操作，防止丢失头指针地址 while(p!=NULL){ s=(Link)malloc(sizeof(Node)); s=p; r->next=s; //将r的指针指向s r=s; //再将s的地址赋给r } r->next=NULL; */
     p=Lb->next;
     while(p){ 
      q=La->next;
      while(q && (q->data!=p->data)){     //查重 
       q=q->next;
      }
      if(!q){           //若遍历完c都没有重复元素 
       r=(Link)malloc(sizeof(Node));
       r->data=p->data;  
       r->next=Lc->next;  
       Lc->next=r;  
      }
      p=p->next;
     } 
    }
    
    //交集,各步骤类似于并集 
    void combine(Link La,Link Lb,Link Ld){ 
     Link p,q,r;
     p=La->next;
     while(p!=NULL){ 
      q=Lb->next;
      while(q!=NULL){ 
       if(p->data==q->data){        //判断a表和b表元素是否相等，若相等，这赋值给c表 
        r=(Link)malloc(sizeof(Node));
        r=p;
        r->next=Ld->next;
        Ld->next=r;
       }
       q=q->next;
      }
      p=p->next;  
     }
    }
    
    //差集
    Link reduce(Link La,Link Lb,Link Le){ 
     Link p,q,r;
     p=La->next;
     while(p){ 
      q=Lb->next;
      while(q && (q->data!=p->data)){ 
       q=q->next;
      }
      if (!q){ 
       r=(Link)malloc(sizeof(Node));
       r->data=p->data;
       r->next=Le->next;
       Le->next=r;
      }
      p=p->next;
     }
    }
    
    int main(){ 
     int x,y,i,choice;
     Link La,Lb,Lc,Ld,Le;
     //初始化
     La=list(La);
     Lb=list(Lb);
     Lc=list(Lc);
     Ld=list(Ld);
     Le=list(Le); 
     //菜单 
     while(1){ 
      show();
      printf("请输出要选择的功能：\n");
      scanf("%d",&choice);
      if(choice<0){ 
       clear(La);
       clear(Lb);
       clear(Lc);
       clear(Ld);
       clear(Le);
       printf("已退出\n");
       return 0;
      }
      switch(choice){ 
       case 1:
        printf("请输入A集合中元素个数\n");
        scanf("%d",&x);
        printf("请输入B集合中元素个数\n");
        scanf("%d",&y);
        input(La,x);
        input(Lb,y);
        printf("A={"); 
        output(La);
        printf("}");
        printf("B={"); 
        output(Lb);
        printf("}");
        printf("请按回车继续！\n");
        getchar();
        getchar();
        system("cls");
        break;
       case 2:
        hand(La,Lb,Lc);
        printf("A并B={");
        output(Lc); 
        printf("}");
        printf("请按回车继续！\n");
        getchar();
        getchar();
        system("cls");
        break;
       case 3:
        combine(La,Lb,Ld);
        printf("A交B={");
        output(Lc); 
        printf("}");
        printf("请按回车继续！\n");
        getchar();
        getchar();
        system("cls");
        break;
       case 4:
        reduce(La,Lb,Le);
        printf("A-B={");
        output(Lc); 
        printf("}");
        printf("请按回车继续！\n");
        getchar();
        getchar();
        system("cls");
        break;
       default:
        printf("输入有误！\n");
        printf("请按回车继续！\n");
        getchar();
        getchar();
        system("cls");
        break;
      }
     }
     return 0;
    }

**小结**  
一不小心就鸽了这么旧，哈哈哈。  
用数组实现集合的（交，并，差）链接  
[https://blog.csdn.net/e\_t\_e\_r\_n\_i\_t\_y/article/details/108800898][https_blog.csdn.net_e_t_e_r_n_i_t_y_article_details_108800898]  
都是我自己写的，感兴趣的可以看一下！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VfdF9lX3Jfbl9pX3RfeQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/e01004b622c9467eabf2c84a66571fe7.png
[https_blog.csdn.net_e_t_e_r_n_i_t_y_article_details_108800898]: https://blog.csdn.net/e_t_e_r_n_i_t_y/article/details/108800898