精华内容
下载资源
问答
  • 数据结构求集合的交集
    2022-01-04 11:08:27

    求整数集合A与整数集合B的交集。

    输入格式:

    输入有三行:

    第一行是A和B的元素个数m和n(m,n <=100);

    第二行是集合A的m个元素;

    第三行是集合B的n个元素。

    输出格式:

    输出交集的所有元素(按照在A集合出现的顺序输出,最后一个输出后面没有空格)。 若交集为空,输出“NULL”。

    输入样例:

    在这里给出一组输入。例如:

    3 4
    10 9 2
    9 10 8 0

    输出样例:

    在这里给出相应的输出。例如:

    10 9

     

    #include <iostream>
    #include <stdlib.h>
    using namespace std;
    
    typedef struct{
    	int *data;
    	int length;
    }sqlist;
    
    sqlist sqlist_creat(int size)
    {
    	sqlist a;
    	a.data=(int*)malloc(sizeof(int)*size);
    	a.length=size;
    	return a;
    }
    
    void sqlist_free(sqlist *L)
    {
    	free(L->data);
    	L->data=NULL;
    	L->length=0;
    }
    
    void intersection(sqlist *A,sqlist *B) //最笨的方法求交集 
    {
    	for(int i=0;i<A->length;i++)
    	{
    		for(int j=0;j<B->length;j++)
    		{
    			if(A->data[i]==B->data[j])
    			{
    				cout<<A->data[i]<<" ";  //结尾空格未做处理 
    				break;
    			}
    		}
    	}
    }
    
    int main()
    {
    	int m,n;
    	int x;
    	sqlist A,B;
    
    	cin>>m>>n; //初始化数据 
    	A=sqlist_creat(m);
    	B=sqlist_creat(n);
    	
    	for(int i=0;i<m;i++)
    	{
    		cin>>x;
    		A.data[i]=x;
    	} 
    	
    	for(int i=0;i<n;i++)
    	{
    		cin>>x;
    		B.data[i]=x;
    	}
    	
    	intersection(&A,&B); //求交集 
    	
    	sqlist_free(&A);
    	sqlist_free(&B);
    	
    	return 0;
    }

    更多相关内容
  • 顺序表的类实现 #include <iostream> using namespace std; const int DefaultSize = 100; class SeqList { protected: int* data;//指向动态内存分配数组的指针 int maxSize;//动态内存分配数组的大小... {

    顺序表的类实现

    #include <iostream>
    
    
    using namespace std;
    const int DefaultSize = 100;
    
    class SeqList
    {
    protected:
        int* data;//指向动态内存分配数组的指针
        int maxSize;//动态内存分配数组的大小
        int last;//标识顺序表中最后一个元素的位置
    public:
        SeqList(int sz = DefaultSize)
        {
            if (sz > 0)
            {
                maxSize = sz;
                data = new int[maxSize];
                last = -1;
                if (data == NULL)
                {
                    cerr << "存储分配错误" << endl;
                    exit(1);
                }
            }
    
        }//构造函数
        ~SeqList()
        {
            last = -1;
            maxSize = 0;
            delete[]data;
            data = NULL;
        }//析构函数
        int getData(int i)const;  
        int Length() const;//返回顺序表中元素的个数
        int Search(int& x) const;//在顺序表中搜索x
        bool GetData(int i, int& x) const;//获取顺序表中第i个位置的元素
        bool Remove(int i, int& x);//删除顺序表第i个位置的元素
        friend istream& operator>>(istream& in, SeqList& L)//输入运算符重载
        {
            int i;
    
            for (i = 0; i < L.last; i++)
            {
                in >> L.data[i];
            }
            return in;
    
        }
        friend ostream& operator<<(ostream& out, const SeqList& L)
        {
            int i;
            for (i = 0; i < L.last; i++)
            {
                out << L.data[i];
            }
            return out;
            //逆置顺序表中的元素
        };
    
        void input(int newSize);
        void output();
    };
    
    
    int SeqList::getData(int i)const
    {
        return data[i];
    }
    int SeqList::Length() const
    {
        return last + 1;
    
    }
    int SeqList::Search(int& x)const
    {
        int i;
        for (i = 0; i <= last; i++)
            if (data[i] == x)
                return i + 1;
        return 0;
    }
    
    bool SeqList::GetData(int i, int& x) const
    {
        if (i <= 0 && i >= last + 1)
            return false;
        x = data[i - 1];
        if (data[i - 1] == x)
            return true;
        else
            return false;
    
    }
    bool SeqList::Remove(int i, int& x)//移除顺序表
    {
        if (last == -1)
            return false;
        if (i < 1 || i > last + 1)
            return false;
        x = data[i - 1];
        for (int j = i; j <= last; j++)
            data[j - 1] = data[j];
        last--;
        return true;
    }
    
    
    void SeqList::input(int newSize)//初始化顺序表
    {
        int i;
        if (newSize <= 0 || newSize >= maxSize)
            exit(0);
    
        last = newSize - 1;
    
        for (i = 0; i <= last; i++)
            cin >> data[i];
    }
    void SeqList::output()//输出顺序表
    {
        int i;
        if (last <= 0)
            exit(0);
        for (i = 0; i <= last - 1; i++)
        {
            cout << data[i] << " ";
        }
        cout << data[i];
    }
    
    

    主函数实现

    int main()
    {
        SeqList a, b;
        int sizeA, sizeB;
    
        cin >> sizeA;
        cin >> sizeB;
    
        a.input(sizeA);
        b.input(sizeB);//初始化a和b
    
        int m = a.Length();
        int i = 1, k, x = 0;
    
        while (i <= m)
        {
            a.GetData(i, x);
            k = b.Search(x);
            if (k == 0)
            {
                a.Remove(i, x);
                m--;
            }
            else
                i++;
        }
        a.output();
        return 0;
    }
    
    展开全文
  • //1:集合交集(链表)。 #include <stdio.h> #include <stdlib.h> struct node { int data; struct node* next; }; void push(struct node **head_ref, int new_data); //添加数...


    //1:求两集合的交集(链表)。
    #include <stdio.h>  
    #include <stdlib.h>  
    struct node  
    {  
        int data;  
        struct node* next;  
    }; 
     
    void push(struct node **head_ref, int new_data); //添加数据元素声明 
    
    
    bool isPresent(struct node *head, int data); //判断是否存在函数声明
    
    
    /* struct node *getUnion(struct node *head1, struct node *head2)//求并集函数
    {  
        struct node *result = NULL;  
        struct node *t1 = head1, *t2 = head2;  
        while(t1 != NULL)  
        {  
            push(&result, t1->data);  
            t1 = t1->next;  
        }  
        while(t2 != NULL)  
        {  
            if(!isPresent(result, t2->data))  
                push(&result, t2->data);  
            t2 = t2->next;  
        }  
      
        return result;  
    } */ 
    
    
    struct node *getIntersection(struct node *head1, struct node *head2)  //求交集函数
    {  
        struct node *result = NULL;   
        struct node *t1 = head1;  
        while( t1 != NULL )  
        {  
            if(isPresent(head2, t1->data))  
                push(&result, t1->data);  
            t1 = t1->next;  
        }  
      
        return result;  
    }  
    void push(struct node**head_ref, int new_data)  //添加数据成员函数
    { 
        struct node* new_node = (struct node*)malloc(sizeof(struct node));  
        new_node->data = new_data;  
        new_node->next = (*head_ref);  
        (*head_ref) = new_node;  
    }    
    void printList(struct node *node)  //输出链表函数
    {  
        while( node != NULL )  
        {  
            printf("%d ", node->data);  
            node = node->next;  
        }  
    }  
    bool isPresent(struct node *head, int data)  //判断是否存在
    {  
        struct node *t = head;  
        while(t != NULL)  
        {  
            if( t->data == data )  
                return 1;  
            t = t->next;  
        }  
        return 0;  
    }  
    int main()  
    {  
       struct node* head1 = NULL;  
        struct node* head2 = NULL;  
        struct node* intersecn = NULL;  
        push (&head1, 20);//链表一添加数据元素  
        push (&head1, 4);  
        push (&head1, 15);  
        push (&head1, 10);    
        push (&head2, 10); //链表二添加数据元素 
        push (&head2, 2);  
        push (&head2, 4);  
        push (&head2, 8);  
    intersecn = getIntersection (head1, head2);//取交集元素  
    printf ("\n 链表一为 \n");  
        printList (head1);  
    printf ("\n 链表二为\n");  
        printList (head2);  
    printf ("\n 求交集后 \n");  
        printList (intersecn); 
        printf("\n");   
        return 0;  
    }


    /*时间复杂度:在这个程序中,链表的并和交操作的时间复杂度都是O(mn),m是链表1的元素个数,n是链表2的元素个素。


    方法2(使用归并排序):
            使用这个方法,求2个链表的并集和交集的操作非常相似。首先,将对2个链表进行排序,然后遍历2个链表,得到2个了表
    的交集和并集。
    下面是具体实现步骤:
    用归并排序对第1个链表进行排序,这个操作的时间复杂度为O(mLogm).
    用归并排序堆第2个链表进行排序,这个操作的时间复杂度为O(nLogn).
    线性遍历2个有序的链表,得到2个链表的交集和并集。这个操作的时间复杂度为O(m+n).[这步类似于求有序数组的交集和并集,后
    者之前已经实现过,点击这里查看详细]
    这个方法的时间复杂度是O(mLogm+ nLogn),优于第一种方法。


    方法3(hash法):
    Union(list1, list2)
            首先初始化结果链表为NULL,创建一个空的hash表,遍历两个链表,将链表中的元素插入到hash表,插入元素的时候同时
    检查hash表中时候是否已经存在该元素,如果hash表中不存在该元素,则同时将该元素插入到结果链表中,如果hash表中
    已经存在,则忽略该元素,继续遍历下一个元素。
    InterSection(list1, list2)
            首先初始化结果链表为NULL,创建一个空的hash表,遍历list1,将list1中的每一个元素都插入到hash表中。然后遍历
    list2,对于list2中的元素,如果已经存在于hash表中,则将该元素插入到结果链表,如果不存在与hash表中,则忽略
    该元素,继续遍历下一个元素。
            这个方法的效率取决与hash表的实现技术,一般情况下,这个方法都比上面两种要好。*/

    转载于:https://www.cnblogs.com/zhuhengjie/p/5966950.html

    展开全文
  • 因此在学习集合这种数据结构时,倍感亲切。 集合的基本性质有一条: 集合中元素是不重复的。因为这种性质,所以我们选用了对象来作为集合的容器,而非数组。 虽然数组也能做到所有不重复,但终究过于繁琐,不如集合。...
  • PTA 7-2 求集合交集 (20 分)

    千次阅读 2019-10-01 18:57:55
    PTA 7-2 求集合交集 (20 分) #include <iostream> #include <cassert> #include <cstdlib> #include <ctime> using namespace std; typedef int T; const int defaultSize = 100; class ...

    PTA 7-2 求集合交集 (20 分)

    #include <iostream>
    #include <cassert>
    #include <cstdlib>
    #include <ctime>
    using namespace std;
    typedef  int T;
    const int defaultSize = 100;
    class SeqList
    {
    private:
          T* data;//指向动态内存分配数组的指针
          int maxSize;//动态内存分配数组的大小
          int last;//标识顺序表中最后一个元素的位置
          void Resize(int newSize)
          {
              maxSize=newSize;
          }
    public:
          SeqList(int sz=defaultSize)//构造函数
          {
                 last=sz-1;
                 data=new T[sz];
                 maxSize=defaultSize;
          }
          SeqList(const SeqList& L)//拷贝构造函数
          {
                maxSize=L.maxSize;
                last=L.last;
                for(int i=0;i<last;i++)
                {
                    data[i]=L.data[i];
                }
          }
          SeqList& operator=(const SeqList& L)//赋值运算符函数
          {
              maxSize=L.maxSize;
                last=L.last;
                for(int i=0;i<last;i++)
                {
                    data[i]=L.data[i];
                }
                return *this;
          }
          ~SeqList()//析构函数
          {
              delete []data;
              last=0;
          }
          virtual int Size() const//返回顺序表的容量
          {
              return maxSize;
          }
          virtual int Length() const//返回顺序表中元素的个数
          {
              return last+1;
          }
          virtual int Search(T & x) const//在顺序表中搜索x
          {
              for(int i=0;i<=last;i++)
              {
                  if(data[i]==x)
                  {
                      return i+1;
                  }
              }
              return 0;
          }
          virtual int Locate(int i) const//检验顺序表中是否存在第i个元素
          {
              if(i>last+1)
                return false;
              return true;
          }
          virtual bool GetData(int i, T& x) const//获取顺序表中第i个位置的元素
          {
              if(Locate(i-1))
              {
                  x=data[i-1];
                  return true;
              }
                return false;
          }
          virtual void SetData(int i, T& x)//将顺序表中第i个位置的元素赋值为x
          {
              if(Locate(i-1))
              {
                  data[i-1]=x;
              }
          }
          virtual bool IsEmpty() const//顺序表是否为空
          {
              return last==0;
          }
          virtual bool IsFull() const//顺序表是否为满
          {
              return last==maxSize;
          }
          virtual bool Insert(int i, const T& x) //在顺序表的第i个元素的位置插入x
          {
              if(i<=last+2)
              {
                  int j;
                   for( j=last+1;j>=i;j--)
                   {
                       data[j]=data[j-1];
                   }
                   data[j]=x;
                   last++;
                   return true;
              }
              return false;
          }
          virtual bool Remove(int i, T&x) //删除顺序表第i个位置的元素
          {
              if(Locate(i))
              {
                  for(int j=i-1;j<last;j++)
                  {
                      data[j]=data[j+1];
                  }
                  last--;
                  return true;
              }
              return false;
          }
          virtual void Sort() //对顺序表中元素进行排序
          {
              for(int i=0;i<last;i++)
              {
                  for(int j=i;j<=last;j++)
                  {
                      if(data[i]>data[j])
                      {
                          T temp;
                          temp=data[i];
                          data[i]=data[j];
                          data[j]=temp;
                      }
                  }
              }
          }
          friend istream& operator>>(istream& in, SeqList & L)//输入运算符重载
          {
              int i;
              for(i=0;i<=L.last;i++)
              {
                  in>>L.data[i];
              }
              return in;
          }
          friend ostream& operator<<(ostream& out, const SeqList& L)//输出运算符重载
          {
              int i;
              for(i=0;i<=L.last;i++)
              {
                  if(i==L.last)
                  {
                      out<<L.data[i];
                  }
                  else
                  out<<L.data[i]<<" ";
              }
              return out;
          }
     /*     void Reverse ()//逆置顺序表中的元素
          {
              for(int i=0;i<=last/2;i++)
              {
                  int temp;
                  temp=data[i];
                  data[i]=data[last-i];
                  data[last-i]=temp;
              }
          }*/
    };
    int main()
    {
          int a1,a2,*a,c=0;
          int num=(a1>a2)?a1:a2;
          a=new int[num];
          cin>>a1>>a2;
          SeqList sList1(a1),sList2(a2);
          cin>>sList1;
          cin>>sList2;
          for(int i=0;i<a1;i++)
          {
              int x;
              sList1.GetData(i+1,x);
              if(sList2.Search(x))
              {
                  a[c++]=x;
              }
          }
          for(int i=0;i<c;i++)
          {
              if(i==c-1){cout<<a[i]<<endl;}
              else cout<<a[i]<<" ";
          }
    }
    展开全文
  • 数据结构——链表集合交集

    千次阅读 2018-09-19 17:48:48
    个人博客网站:https://www.liuzhi.org.cn/ #include <stdio.h> #include <malloc.h> typedef struct Node { int data; struct Node *next;...LNode *CreateList() { // 创建单循环链表,...
  • 总源代码在最后 双向链表: ...链表集合类 template<typename T> class ListSet { public: ListSet() ; ListSet(const ListSet<T>& Set); ~ListSet(); int getlength()const ;
  • SCAU 数据结构 2 求交集

    千次阅读 2022-04-04 11:45:48
    用顺序表表示集合集合元素为整型数据,设计一个算法实现两个集合求交集运算。 输入格式 第一行:集合A和集合B的元素个数n,m 第二行:集合A的n个元素 第三行:集合B的m个元素 输出格式 输出:第一行:集合A,B...
  • 浙大PTA求集合交集

    千次阅读 2020-04-17 10:15:07
    整数集合A与整数集合B的交集。 输入格式: 输入有三行: 第一行是A和B的元素个数m和n; 第二行是集合A的m个元素; 第三行是集合A的n个元素。 输出格式: 输出交集的所有元素(按照在A集合出现的顺序输出,最后一个...
  • 给定两个递增的整数集合A和B,分别用链表表示集合A和B,出A和B的交集,并存放在A中。要求空间复杂度为O(1)。 输入 多组数据,每组数据有三行,第一行为序列A和B的长度n和m,第二行为序列A的n个元素,第三行为序列B...
  • C数据结构——链表求交集与并集

    千次阅读 多人点赞 2017-03-29 22:54:08
    //接上面复制链表,将不是交集里含有的数据写入,类似链表插入 while (p2) { while (p3)//此循环用于遍历交集,判断p2指向的存储单元的存储值是否在交集中出现 { if (p2->data == p3->data) break;//...
  • 主要介绍了JS中的算法与数据结构集合(Set),结合实例形式详细分析了javascript中集合的概念、原理、定义及相关操作技巧,需要的朋友可以参考下
  • 【单链表的初始化、表长、取值、查找、遍历、后插法(尾插法)创建、合并(并集、交集)】实验报告+完整代码
  • PTA 7-5 求集合交集 (20 分)

    千次阅读 2019-05-22 08:09:13
    整数集合A与整数集合B的交集。 输入格式: 输入有三行: 第一行是A和B的元素个数m和n; 第二行是集合A的m个元素; 第三行是集合A的n个元素。 输出格式: 输出交集的所有元素(按照在A集合出现的顺序输出,最后一...
  •   (递增有序)顺序表表示集合A、B,实现以下操作:    C=A∩B,C=A∪B,C=A∖BC=A \cap B,C=A \cup B,C=A \setminus BC=A∩B,C=A∪B,C=A∖B A=A∩B,A=A∪B,A=A∖BA=A \cap B,A=A \cup B,A=A \...
  • 2个集合交集

    2014-05-26 18:49:03
    另外并集时,由于哈希表的值(VALUE)部分不需要用到,所以这个数据结构也可以更换为 哈希集(HashSet)。 转载请注明出处。 VB中HashTable 2012-08-20 14:43:21| 分类: asp.net|举报|字号 订阅 首先定义一个...
  •  假设有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示,即线性表中的数据元素即为集合中的成员。设计算法,用函数unionList(List LA, List LB, List &LC )函数实现该算法,一个新的集合C=A∪B,即将两个集合的...
  • 集合的并交和差运算 实习报告 题目编制一个演示集合的并交和差运算的程序 班级信管08-2 姓名顾先 学号0801051409 完成日期2010.5.20 一需求分析 1.本演示程序中集合的元素限制在小写字母a-z之间集合的大小不限制集合...
  • 如果需要求两个集合之间的交集: 1. 并查集 2. 排序+双指针
  • 问题: 两个集合,分别含有一定数量的元素,如何快速得到两个集合的交集和差集? 举例: 给定两个集合List<String> list1和List<String>...3.方法:实现两个集合交集的方法 &
  • 这是我的第二篇博文,也是我数据结构系列的第二个算法。 我计划,我的数据结构系列,不仅仅包括算法的实现,后续还会整理一些数据结构的具体概念、定义和一些经典数据结构算法的思想等,可以帮助我自己巩固复习的...
  • 数据结构 集合运算

    2011-11-19 21:07:11
    数据结构集合运算,C语言开发,界面友好。。
  • 整数集合A与整数集合B的交集。 输入格式: 输入有三行: 第一行是A和B的元素个数m和n(m,n <=100); 第二行是集合A的m个元素; 第三行是集合A的n个元素。 输出格式: 输出交集的所有元素(按照在A集合...
  • 输入:第一行为集合A,第二行为集合B 输出:A交B #include<iostream> using namespace std; typedef int ElemType; struct Node { ElemType data; Node* next; }; class LinkList { private: Node* Head;...
  • 数据结构实践——顺序表 两集合交集
  • 用这一个案例,认识下什么是抽象数据结构,如何用抽象数据结构
  • 序列的交集(链表) 问题描述 : 使用带头结点的单链表编程: 有两个序列,分别表示两个集合它们的交集并输出。 输入说明 : 第一行输入序列A的信息: 第一个整数n(0<=n<=100),表示共有n个元素,其后有n...
  • Python中有一种内置类型叫做集合,它是一个非常有用的数据类型,它与列表的行为类似,唯一区别在于集合(set)是一个无序的不重复的元素序列。 类似:1,2,3,4,1,2,3 = 1,2,3,4 (1)集合的创建: 1). 使用大括号{ ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 61,242
精华内容 24,496
关键字:

数据结构求集合的交集

数据结构 订阅