精华内容
下载资源
问答
  • 顺序表的类实现 #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;
    }
    
    展开全文
  •  假设有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示,即线性表中的数据元素即为集合中的成员。设计算法,用函数unionList(List LA, List LB, List &LC )函数实现该算法,一个新的集合C=A∪B,即将两个集合的...

      本文点评一位学生对基于线性表存储集合,然后对集合进行求并运算的错解,供学习者参考。

    【项目 - 求集合并集】
      假设有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示,即线性表中的数据元素即为集合中的成员。设计算法,用函数unionList(List LA, List LB, List &LC )函数实现该算法,求一个新的集合C=A∪B,即将两个集合的并集放在线性表LC中。

    提示:
    (1)除了实现unnionList函数外,还需要在main函数中设计代码,调用unionList进行测试和演示;
    (2)可以充分利用前面建好的算法库[点击…],在程序头部直接加 #include<list.h>即可(工程中最普遍的方法,建议采纳);
    (3)也可以将实现算法中需要的线性表的基本运算对应的函数,与自己设计的所有程序放在同一个文件中。

    点这儿…】可以看课程中提供参考解答。

    【错解】

    #include <stdio.h>
    #include "list.h"
    
    void unionList(SqList *LA, SqList *LB, SqList *&LC)
    {
        int e;
        int lena=LA->length;
        LC = LA;
        for (int i = 0; i <LA->length; i++)
        {
            if (LA->data[i] != LB->data[i])
            {
                ListInsert(LC, lena++, LB->data[i]);
            }
        }
        DispList(LC);
    }
    
    int main()
    {
        SqList *la, *lb, *lc;
        ElemType x[2] = {1,2};
        ElemType y[2] = {1,4,3}; //原文中只有{1,4},为更好地反映问题,我增加1个元素3
        ElemType z[4];
        CreateList(la, x, 2);
        CreateList(lb, y, 3);
        CreateList(lc, z, 4);
        unionList(la, lb, lc);
        return 0;
    }

    【我的点评】
      阅读代码知道,第8行LC=LA,意即从此LC指向的也就是LA指向的线性表了。对照题目要求,合并后的LC应该是一个新的线性表,此处处理不合要求。
      若不考虑这一要求,LC=LA后,合并的结果就保存在LA(也是LC)中了。在内存访问的机制中,这是合法的。(这儿和内存管理中的什么堆区、栈区之类的没有关系。内存管理机制对于计算机类的学生很重要,但一般入门级阶段并不讲。)合法仅是在合乎语法要求的层面,事实上,LC原先指向的空间从此没有由任何变量指向,也没有被释放,成了“游离”的垃圾。  
      接下来的讨论,我们就以合并后的结果保存到LA中为起点。
      第9-15行的处理,可以看出学生在算法设计时没有理清头绪。LA(LC)中已经是并集中的第一部分元素了,接下来,应该是“将LB中有,但LA没有的元素,加到LC中”(严格讲,“LB中的元素”指LB指针指向的线性表代表的集合中的元素,LA、LC同),代码没有体现出这层意思。为了完成这一任务,要考察LB中的每个元素,最外层的循环,应该针对的是LB,而不是LA。
      故算法框架应该是:

        for (i = 0; i <LB->length; i++)
        {
            //若LB集合中的第i个元素不在原LA集合中,则将LB中的第i个元素加入到LC中
        }

      如何知道“LB集合中的第i个元素不在原LA集合中”?这需要和LA集合中的元素逐个比较的!于是这里需要针对“原LA集合”构造一个循环,以便逐个比较。显然,11-14行的一个分支结构,仅完成“LA和LB相同序号的元素是否相等”,是不足以考察LA中的每一个元素的。于是上面是算法框架拓展为:

        for (i = 0; i <LB->length; i++)
        {
            for (j = 0; j <lena; j++)  
                //若LB->data[i] == LA->data[j]退出循环
            //循环中未出现相等的情形,则说明LB->data[i]未在LA中出现过,要将LB->data[i]加入
    
        }

      于是,尽可能在原错误程序基础上修改,且合并后的结果LC实际就是LA的情况下,得到的完整代码为:

    #include <stdio.h>
    #include "list.h"
    
    void unionList(SqList *LA, SqList *LB, SqList *&LC)
    {
        int i,j;
        int lena,lenc;
        lena=lenc=LA->length; //lena是原LA长度,lenc代表合并后的长度
        LC = LA;  //LC和LA将指同一个集合
        for (i = 0; i < LB->length; i++)
        {
            for (j = 0; j <lena; j++)
                if(LB->data[i] == LA->data[j])
                    break;
            if(j>=lena)  //退出前面的循环是因为全找过了找不着,即在原LA中不存在
            {
                ListInsert(LC, ++lenc, LB->data[i]);
            }
        }
    }
    
    int main()
    {
        SqList *la, *lb, *lc;
        ElemType x[2] = {1,2};
        ElemType y[3] = {1,4,3}; //原文中只有{1,4},为更好地反映问题,我增加1个元素3
        //ElemType z[4];
        CreateList(la, x, 2);
        CreateList(lb, y, 3);
        //CreateList(lc, z, 4);
        unionList(la, lb, lc);
        DispList(lc);
        return 0;
    }

      需要强调的是,for (j = 0; j <lena; j++)中的lena是“原LA”的长度,不能用LA->length代替,因为在LA、LC混用的情况下,LA->length随着插入,是动态变化着的。
      在原参考解答中,“插入LB中每一个元素”只用了一重循环,但要知道,实现if (!LocateElem(LA,e))的内部,“藏”对LA指向的每一个元素的扫描,是内含一层循环的,到算法库[点击…]中考察基本操作的实现可以验证这一说法。这种写法看起来更简单,也道出了我们应该用基本运算为单位进行思考的必要性。这是在学习数据结构中,应该养成的习惯。这是工程中用到的思维,代码写得出,还要写得好。
      在上面的解答中,我将DispList(LC);放到main函数中了。unionList只管合并,不管别的任何事情。这是软件工程中“高内聚”的要求——一个模块尽可能只完成单一的工作。“显示结果”是“求并”以后做的工作,两者是“平级”的,不要将显示作为合并的一部分。
      还有,新代码中的27和30(在原代码中也有)没有必要,这样创建了线性表,却在合并时直接将LC和LA共用空间了,何必呢,反倒使一块空间彻底成了垃圾。
      在初学者的学习中,一定要争取自己写出来。可以参考一切可以用到的资料启发自己,给出自己的解答。写出这样的错解,也是好的成果,中间的思考、尝试过程是我们真正要的东西。这个过程价值连城。当自己已经经过一定的思考之后,再看一些相对规范的解法(例如本文中的参考解答),也是很必要的。观摩、阅读是学习方法。如果能在观摩中品到其味道,再去仿制一份,也便极好。

    展开全文
  • 浙大PTA求集合交集

    2020-04-17 10:15:07
    整数集合A与整数集合B的交集。 输入格式: 输入有三行: 第一行是A和B的元素个数m和n; 第二行是集合A的m个元素; 第三行是集合A的n个元素。 输出格式: 输出交集的所有元素(按照在A集合出现的顺序输出,最后一个...

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

    输入格式:
    输入有三行: 第一行是A和B的元素个数m和n; 第二行是集合A的m个元素; 第三行是集合A的n个元素。

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

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

    3 4
    10 9 2
    9 10 8 0

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

    10 9

    ac代码:

    #include <iostream>
    
    using namespace std;
    typedef struct LNode * List;
    struct LNode{
        int Data;
        struct LNode * Next;
    };
    
    List ReadList(int n);
    List Intersection(List L1, List L2);
    void PrintList(List L);
    
    int main()
    {
        List L1, L2, L;
        int e1, e2;
        scanf("%d%d", &e1, &e2);
        L1 = ReadList(e1);
        L2 = ReadList(e2);
        L = Intersection(L1, L2);
        PrintList(L);
        return 0;
    }
    
    List ReadList(int n)
    {
        List L, head, s;
        L = (List)malloc(sizeof(struct LNode));
        head = L;
        for(int i = 1; i <= n; i++){
            int e;
            scanf("%d", &e);
            s = (List)malloc(sizeof(struct LNode));
            s->Data = e;
            s->Next = NULL;
            L->Next = s;
            L = L->Next;
        }
        L = head->Next;
        free(head);
        return L;
    }
    List Intersection(List L1, List L2)
    {
        List L, t1, t2, s, head;
        t1 = L1, t2 = L2;
        L = (List)malloc(sizeof(struct LNode));
        L->Next = NULL;
        head = L;
        while(t1){
            t2 = L2;
            while(t2){
                if(t2->Data == t1->Data){
                    s = (List)malloc(sizeof(struct LNode));
                    s->Data = t1->Data;
                    s->Next = NULL;
                    L->Next = s;
                    L = L ->Next;
                    break;
                }
                t2 = t2->Next;
            }
            t1 = t1->Next;
        }
        L = head->Next;
        free(head);
        return L;
    }
    void PrintList(List L)
    {
        if(L == NULL)
            printf("\n");
        else{
            printf("%d", L->Data);
            L = L->Next;
            while(L){
                printf(" %d", L->Data);
                L = L->Next;
            }
        }
    }
    
    
    展开全文
  • 数据结构——链表集合交集

    千次阅读 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() { // 创建单循环链表,...

    个人博客网站:https://www.liuzhi.org.cn/ 

    #include <stdio.h>
    #include <malloc.h>
    
    typedef struct Node {
        int data;
        struct Node *next;
    }LNode,*LinkList;
    
    LNode *CreateList() { // 创建单循环链表,返回链表头
        LNode *head,*p;
        int i,n;
        scanf("%d",&n);
        head = p = (LNode *)malloc(sizeof(LNode)); // 专用头结点
        head->data = 0;
        for(i = 0; i < n; ++i) {
            p->next = (LNode *)malloc(sizeof(LNode));
            scanf("%d",&p->next->data);
            p = p->next;
        }
        p->next = head;
        return head;
    }
    
    LNode *MutualAgg(LNode *A,LNode *B) {  // A∩B
        LNode *C,*pa,*pb,*pc,*qc;
        C = pc = (LNode *)malloc(sizeof(LNode));
        pc->data = 0;
        pa = A->next;
        pb = B;
        while(pa != A) {
            pb = B->next;
            while(pb != B) {
                if(pb->data == pa->data) {
                    qc = (LNode *)malloc(sizeof(LNode));
                    qc->data = pb->data;
                    pc->next = qc;
                    pc = qc;
                }
                pb = pb->next;
            }
            pa = pa->next;
        }
        pc->next = C;
        return C;
    }
    
    
    
    void PrintList(LNode *head) {
        LNode *p = head->next;
        while(p != head) {
       
            printf("%d ",p->data);
    
            p = p->next;
        }
    }
    
    int main() {
        LNode *A,*B,*C,*D,*E;
        A = CreateList();
        B = CreateList();
        C = MutualAgg(A,B);
        PrintList(C);
        printf("\n\n");
        return 0;
    }
    

    展开全文
  • //1:集合交集(链表)。 #include #include struct node {  int data;  struct node* next; };    void push(struct node **head_ref, int new_data); //添加数据元素声明  bool isPresent(st
  • 1.放入集合中自定义的类通常需要重载==和 2.集合存储指定类型的键,且不允许有重复的键 3.STL set类迭代器按照递增顺序遍历元素 4.集合的应用:埃拉托斯特尼筛法--找出小于等于n的所有素数  *从整数m=2(m...
  • 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-5 求集合交集 (20 分)

    千次阅读 2019-05-22 08:09:13
    整数集合A与整数集合B的交集。 输入格式: 输入有三行: 第一行是A和B的元素个数m和n; 第二行是集合A的m个元素; 第三行是集合A的n个元素。 输出格式: 输出交集的所有元素(按照在A集合出现的顺序输出,最后一...
  • JavaScript数据结构-集合

    千次阅读 2016-11-06 15:41:57
    集合(set)是一种包含不同元素的数据结构集合中的元素称为成员。集合具有两个重要特性: (1)集合中的成员是无序的 (2)集合中不允许相同成员存在 当想创建一个数据结构,用来保存一些独一无二的元素时,...
  • 数据结构实践——顺序表 两集合交集
  • 简介 动机 Cardinality Filters SCF - Single Cardinality Filter ...参考资料简介介绍一个新的数据结构“Cardinality Filter”来快速计算一组交集的大小上限。且期望的时间复杂度为O(|A|+|B|w\frac{|A| + |B|}{w}
  • 在ES6里已经引入了集合数据结构概念——Set类。 分类:常见的有空集,并集,交集,差集。 应用场景:1)数据去重;2)用于存储一些独一无二的数据。 js实现一个集合 集合的特性类似于JavaScript数据类型里的...
  • 单链表集合求交集

    千次阅读 2016-04-02 10:10:06
    单链表实现集合求交集
  • 数据结构求集合并集

    千次阅读 2017-10-22 17:01:14
    (1)设计一个算法两个集合A和B的并集运算,要求不破坏原有的单链表A和B. (2)假设集合中的元素递增排列,设计一个高效算法两个集合A和B的并集运算,要求不破坏原有的单链表A和B。 #include #include ...
  • 给定两个递增的整数集合A和B,分别用链表表示集合A和B,出A和B的交集,并存放在A中。要求空间复杂度为O(1)。 输入 多组数据,每组数据有三行,第一行为序列A和B的长度n和m,第二行为序列A的n个元素,第三行为序列B...
  • 序列的交集(链表) 问题描述 : 使用带头结点的单链表编程: 有两个序列,分别表示两个集合它们的交集并输出。 输入说明 : 第一行输入序列A的信息: 第一个整数n(0<=n<=100),表示共有n个元素,其后有n...
  •  假设有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示,即线性表中的数据元素即为集合中的成员。设计算法,用函数unionList(List LA, List LB, List &LC )函数实现该算法,一个新的集合C=A∪B,即将两个集合的...
  • C数据结构——链表求交集与并集

    千次阅读 2017-03-29 22:54:08
    //接上面复制链表,将不是交集里含有的数据写入,类似链表插入 while (p2) { while (p3)//此循环用于遍历交集,判断p2指向的存储单元的存储值是否在交集中出现 { if (p2->data == p3->data) break;//...
  • 给定两个递增的整数集合A和B,分别用链表表示集合A和B,出A和B的交集,并存放在A中。要求空间复杂度为O(1)。 输入 多组数据,每组数据有三行,第一行为序列A和B的长度n和m,第二行为序列A的n个元素,第三行为...
  • 数据结构之不相交集

    2018-07-09 00:13:02
    不相交集(并查集)是解决等价问题的一种有效数据结构。这种数据结构实现起来简单,每个例程只需要几行代码,而且可以使用一个简单的数组实现。 等价关系 若对于每一对元素(a,b),a,b属于集合S,aRb或为true或为...
  • 简单说一说数据结构——集合

    千次阅读 2017-03-23 16:37:30
    迄今为止,我们已经学习了数组(列表)、栈、队列和链表(及其变种)等顺序数据结构。...ECMAScript6也实现了集合这种数据结构——Set类。而我们用ECMAScript5来实现。也可以为看Set时做铺垫。首先,集合Set类的骨架
  • 通过该实验,让学生复习巩固C语言中的循环结构、循环控制条件、分支结构和数组/链表、函数的调用等有关内容,体会到用数组存储集合时,需要记录集合元素的个数,否则输出结果会出现数据越界现象。 (2)实验内容 ...
  • C语言利用链表求集合交集

    千次阅读 2018-12-12 12:36:04
     假设元素依值递增有序排列的线性表A和B分别表示两个集合(即同一表中的元素值各不相同),现要求另辟空间构成一个线性表C,其元素为A和B中元素的交集,且表C中的元素也依值递增有序排列。 输入A和B集合中的元素;...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 49,460
精华内容 19,784
关键字:

数据结构求集合的交集

数据结构 订阅