C++实现简易的集合运算

简介: C++实现简易的集合运算



一、概要设计

用户可以自行输入数据创建集合(这里设置为整型),并可以选择不同的功能进行不同的集合运算(交集,并集,差集,相对补)。

二、详细设计

1.大致版图

#define type int
struct List{
  List *next;
  type data;
};

3.函数

void swap(List *&m1,List *&m2){
  //使m1的内容换成m2的内容 
  //应该先吧m1清空 
  List *r1 = m1->next;
  while(r1!=NULL){
    List *temp = r1;
    r1=r1->next;
    delete temp;
  }
  //接下来把m2的内容换到m1中去
  r1 = m1;
  r1->next = NULL;
  List *temp;
  List *r2 = m2->next;
  while(r2!=NULL){
    temp = new List;
    temp->data = r2->data;
    r1->next = temp;
    temp->next = NULL;
    r1 = temp;
    r2 = r2->next;
  } 
}

这是交换两个链表的函数。因为在求并交集的时候,我设计的函数会对原链表的值进行改动,会影响后序操作的结果。所以,在用户输入集合之后,就立即新建一个链表存储输入的链表,在每次运算前,都调用此函数交换链表的值。

void createList(List *&m){
  cout<<"您正在创建一个集合!"<<endl<<"请先输入元素,以空格分开各元素(如果您输入相同的数字,则该数字会默认只出现一次):"<<endl;
  int n;
  vector<int>v;
  while(cin>>n){
    bool has=false;
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++){
      if(n==*it){
        has = true;
        break;
      }
    }
    if(!has){
      v.push_back(n);
    }
    if(cin.get()=='\n'){
      break;
    }
  }
  List *p;
  List *r = m;
  for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
    p = new List;
    p->data = *it;
    r->next = p;
    p->next = NULL;
    r=p;
  }
  cout<<"创建成功!"<<endl;
}

用户输入值的函数。集合中的元素都是不一样的,所以每次当用户输入一个值,我们都遍历存储值的向量,查找有没有这个数。如果有,则跳过,如果没有,则插入。输入数字以空格分开,以回车表示输入完毕。

List * add(List *&m1,List *&m2){   //求并集 
  List *p1;
  List *p2 = m2;
  while(p2->next!=NULL){
    p2=p2->next;
  }
  List *r2 = m2->next;
  List *r1 = m1->next;
  //对于r1的元素,都遍历r2一遍,如果没有,则加到后面。如果有则不处理 
  while(r1!=NULL){
    bool has = false;
    r2 = m2->next;
    while(r2!=NULL){
      if(r2->data==r1->data){
        has = true;
        break;
      }
      r2=r2->next;
    }
    if(r2==NULL){
      //说明没有这个元素
      p1 = new List;
      p1->data = r1->data;
      p2->next = p1;
      p1->next = NULL;
      p2=p1;
    }
    r1=r1->next;
  }
  return m2;
}

求并集。思路:对于r1的元素,都遍历r2一遍,如果没有,则加到后面。如果有则不处理

List * sub(List *&m1,List *&m2){  //求交集 
  //求出2个链表中的相同的元素,m1/\m2即m1-相同; m2/\m1即m2-相同
  List *p1,*p2,*r1,*r2,*p3,*r3;
  List *m3 = new List;
  m3->next = NULL;
  r3 = m3;
  r1 = m1->next;
  while(r1!=NULL){
    r2 = m2->next;
    bool has = false;
    while(r2!=NULL){
      if(r2->data==r1->data){
        has = true;
        break;
      }
      r2=r2->next;
    }
    if(has){
      //说明有这个元素 ,则加到临时链表中去 
      //在加入之前应该先判断一下是不是有这个元素
      p1 = m3->next;   //p1做临时指针 
      has = false;
      while(p1!=NULL){
        if(p1->data==r1->data){
          //说明有这个元素,说明不需要加进去
          has = true; 
          break;
        }
        p1=p1->next;
      }
      //判断完毕
      if(!has){
        p3 = new List;
        p3->data = r2->data;
        r3->next = p3;
        p3->next = NULL;  
        r3 = p3;
      }
    }
    r1=r1->next;
  }
  return m3; 
}

这个函数是求并集。思路:新建一个临时链表m3。对于m1中每个元素,都遍历m2中的每个元素,并判断是否相同,如果相同,则说明属于交集中的一部分,用m3来存储,使用尾插法插到链表末尾。这样,两个链表中的相同的元素都存储在m3中。最后返回m3(即交集)

List * mul(List *&m1,List *&m2){   //求对称差 
  //求出2个链表中的相同的元素,m1/\m2即m1-相同; m2/\m1即m2-相同
  List *p1,*p2,*r1,*r2,*p3,*r3;
  List *m3 = new List;
  m3->next = NULL;
  r3 = m3;
  r1 = m1->next;
  while(r1!=NULL){
    r2 = m2->next;
    bool has = false;
    while(r2!=NULL){
      if(r2->data==r1->data){
        has = true;
        break;
      }
      r2=r2->next;
    }
    if(has){
      //说明有这个元素 ,则加到临时链表中去 
      //在加入之前应该先判断一下是不是有这个元素
      p1 = m3->next;   //p1做临时指针 
      has = false;
      while(p1!=NULL){
        if(p1->data==r1->data){
          //说明有这个元素,说明不需要加进去
          has = true; 
          break;
        }
        p1=p1->next;
      }
      //判断完毕
      if(!has){
        p3 = new List;
        p3->data = r2->data;
        r3->next = p3;
        p3->next = NULL;  
        r3 = p3;
      }
    }
    r1=r1->next;
  }
  //交集已经求出来了,即m3 
  //对于m3中的每个元素,都遍历m1,如果有,则删除这个元素;如果没有,则无需处理
  //应该加入一个前指针和一个后指针
  r3 = m3->next;
  while(r3!=NULL){
    List *pre = m1;
    r1 = m1->next;
    bool has = false;
    while(r1!=NULL){
      if(r1->data==r3->data){
        has = true;
        break;
      }
      pre=pre->next;
      r1=pre->next;
    }
    if(has){
      //如果有,就删除 
      List *temp = r1;
      r1 = r1->next;
      pre->next = r1;
      delete temp;  
    }
    else{
      //如果没有,则不处理 
    }
    r3=r3->next;
  }
  return m1;
}

函数前半部分是求链表m1、m2的交集(参照前面sub()函数),这样,求得两个链表(即集合)的交集后,将集合中的和交集元素相同的元素除去。为了达到这个目的,对于m3中的每个元素,都遍历m1,查看是否相同。如果相同,则删除后此元素。注意:因为此处用到了删除,所以在开始遍历时,应该准备两个指针,pre和r,pre始终指向r的前一个元素。

List * div(List *&m1,List *&m2,List *&m11,List *&m21){
  swap(m1,m11);
  swap(m2,m21);
  List *m3 = new List;
  m3->next = NULL;
  m3 = mul(m1,m2);
  List *m31 = new List;
  m31->next = NULL;
  swap(m31,m3);
  swap(m1,m11);
  swap(m2,m21);
  List *m4 = new List;
  m4->next = NULL;
  List *m41 = new List;
  m41->next=NULL;
  m4 = mul(m2,m1);
  swap(m41,m4);
  List *m5 = add(m31,m41);
  return m5;
}

求对称差在求出了交集后就很容易求出。我们先求出两个集合的交集(用sub()函数,之后再求集合m1(即链表m1)与交集的差集m4(用mul()函数);之后再求出集合m2(即链表m2)与交集的差集m5(用mul()函数)。最后再求出m4与m5的并集(用add()函数)即可。

void sort(List *&m){
  List *r = m->next;  //相当于保存数据链表结点 
  m->next=NULL;       //m结点重新开始 
  List *r2 = m;       //方便尾插的哨兵指针 
  List *p1 = r;     //p1作为 
  bool moveP1 = false;
  while(p1!=NULL){
    int min = p1->data;
    List *pre;
    List *p2=p1->next;
    while(p2!=NULL){
      if(min>p2->data){
        min = p2->data;
      }
      p2=p2->next;
    }
    if(p1->data==min){
      List *temp = p1;
      p1=p1->next;
      delete temp;
      
      moveP1 = true;
      
    }
    else{
      pre = p1;
      p2 = pre->next;
      bool is = false;
      while(p2!=NULL){
        if(p2->data==min){
          is = true;
          break;
        }
        pre=pre->next;
        p2 = pre->next;
      }
      if(is){
        List *temp = p2;
        p2=p2->next;
        pre->next = p2;
        delete temp;
      }
    }
    List *p3 = new List;
    p3->data=min;
    r2->next = p3;
    p3->next = NULL;
    r2=p3;
  }
}

排序函数。不另外创建头结点进行排序。原理:代码写的不是很清楚。遍历整个数据链表,找到最小值,删除此结点,另外创建结点存储最小值,插入到原头节点之后。涉及到删除操作,所以需要一个pre指针和一个p指针(一前一后)。

void disp(List *&m){
  sort(m);  
  List *r = m->next;
  if(r==NULL){
    cout<<"为空!"<<endl;
    return ;
  }
  while(r!=NULL){
    cout<<r->data<<" ";
    r=r->next;
  }
  cout<<endl;
}

简单的输出函数,只不过在开头加入了排序函数。

int main(){
  List *m1 = new List;
  List *m2 = new List;
  m1->next = NULL;
  m2->next  = NULL;
  
  List *m11 = new List;
  List *m21 = new List;
  m11->next = NULL;
  m21->next  = NULL;
  
  List *Add = new List;  //并集 
  List *Sub = new List;  //交集 
  List *Mul = new List;  //对称差 
  List *Div = new List;  //相对补
  
  cout<<"目前是求集合各运算界面,您需要输入两个集合:"<<endl;
  createList(m1);
  createList(m2);
  swap(m11,m1);
  swap(m21,m2);
  
  int select;
  do{
    cout<<"您可以选择以下操作:1.求并集  2.求交集  3.求差集(a-b)  4.求差集(b-1)  5.求相对差集  6.查看输入1集合  0.退出"<<endl<<"选择相应操作的序号来进行:"<<endl;
    while (!(cin >>select)){
      cin.clear();
      while (cin.get() != '\n'){
        continue;
      }//跳过错误输入
      cout << "请输入一个数字:"<<endl;
    }
    switch(select){
      case 1:{
        swap(m1,m11);
        swap(m2,m21);
        Add = add(m1,m2);
        cout<<"并集如下:"<<endl;
        disp(Add);
        break;
      }
      case 2:{
        swap(m1,m11);
        swap(m2,m21);
        Sub = sub(m1,m2);
        cout<<"交集如下:"<<endl;
        disp(Sub);
        break;
      }
      case 3:{
        swap(m1,m11);
        swap(m2,m21);
        Mul = mul(m1,m2);
        cout<<"差集如下:"<<endl;
        disp(Mul);
        break;
      }
      case 4:{
        swap(m1,m11);
        swap(m2,m21);
        Mul = mul(m2,m1);
        cout<<"差集如下:"<<endl;
        disp(Mul);
        break;
      }
      case 5:{
        swap(m1,m11);
        swap(m2,m21);
        Div = div(m1,m2,m11,m21);
        cout<<"相对差集如下:"<<endl;
        disp(Div);
        break;
      } 
      case 6:{
        cout<<"您输入的集合如下:"<<endl;
        disp(m1);
        disp(m2);
        break;
      } 
      case 0:{
        cout<<"退出成功!"<<endl;
        return 0;
      }
      default:{
        
        break;
      }
    }
  }
  while(select!=0);
  return 0;
}

主函数。提供人机交互界面。

三、总结

整体简单,如果是第一次写,个人感觉很锻炼逻辑能力。

.cpp文件下载:

链接: https://pan.baidu.com/s/1bXTwtepmZ1TpLweyE989Ow 提取码: k3bg 复制这段内容后打开百度网盘手机App,操作更方便哦

目录
打赏
0
0
0
0
14
分享
相关文章
|
1月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
1月前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
43 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【C++核心】特殊的元素集合-数组与字符串详解
这篇文章详细讲解了C++中数组和字符串的基本概念、操作和应用,包括一维数组、二维数组的定义和使用,以及C风格字符串和C++字符串类的对比。
116 4
|
1月前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
48 12
|
1月前
|
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
46 9
【C++数据结构——线性表】求集合的并、交和差运算(头歌实践教学平台习题)【合集】
本任务要求编写程序求两个集合的并集、交集和差集。主要内容包括: 1. **单链表表示集合**:使用单链表存储集合元素,确保元素唯一且无序。 2. **求并集**:遍历两个集合,将所有不同元素加入新链表。 3. **求交集**:遍历集合A,检查元素是否在集合B中存在,若存在则加入结果链表。 4. **求差集**:遍历集合A,检查元素是否不在集合B中,若满足条件则加入结果链表。 通过C++代码实现上述操作,并提供测试用例验证结果。测试输入为两个集合的元素,输出为有序集合A、B,以及它们的并集、交集和差集。 示例测试输入: ``` a c e f a b d e h i ``` 预期输出:
42 7
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
40 5
【C++数据结构——线性表】顺序表的基本运算(头歌实践教学平台习题)【合集】
本文档介绍了线性表的基本运算任务,涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法,并提供了测试说明和通关代码。 主要内容包括: - **任务描述**:实现顺序表的基本运算。 - **相关知识**:介绍线性表的基本概念及操作,如初始化、销毁、判定是否为空表等。 - **具体操作**:详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法,并附有代码示例。 - **测试说明**:提供测试输入和预期输出,确保代码正确性。 - **通关代码**:给出完整的C++代码实现,帮助完成任务。 文档
41 5
C++中集合的使用
C++中集合的使用
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等