精华内容
下载资源
问答
  • 不相交集合的数据结构

    千次阅读 2015-06-06 00:15:09
    不相交集合的数据结构本来想着来实现基于贪婪思想的Kruskal算法—–最小生成树的算法之一。 却发现当我们合并集合时里面还涉及到一个判断“环”的问题,继而有了本篇博文:不相交集合的数据结构

    不相交集合的数据结构

    本来想着来实现基于贪婪思想的Kruskal算法—–最小生成树的算法之一。
    却发现当我们合并集合时里面还涉及到一个判断“环”的问题,继而有了本篇博文:不相交集合的数据结构。
    关于不相交集合的数据结构,这里作一个简单的介绍,更多的可看这里

    • 第一:我们假设我们有n个不相交的集合{Si},i=1~n;其中每个集合中都有一个“代表元素”(这个“代表元素”你可以理解为我们班级中的“班长”,对外“班长”就代表了我们整个班级);
    • 第二:不相交的集合的数据结构,要支持UNION(x,y)操作:将包含x和y的两个动态集合(Si和Sj)合并成一个新的集合,即完成两个集合的合并,然后为这个新的集合选取一个“代表元素”,虽然UNION的很多实现都是直接选取Si或者是Sj的“代表元素”继续作为合并后集合的“代表元素”,但是你也可以选择集合中的其他元素作为代表元素。
    • 第三 、不相交的集合的数据结构,支持FIND-SET(x)操作:返回x所在集合的代表元素。

    不相交集合数据结构有一些应用,例如:确定无向图的连通分量,以及图中是否有环。
    下面我们用java来实现判断一个图中是否有环,判断是否有环的思想可以看这里

    第一步:我们定义了一个边的类,如下

    package org.wrh.algorithmdemo;
    //边的类
    public class Edge {
        /*
         * 边的始点
         * */
        private int src;
        /*
         * 边的终点
         * */
        private int dest;
    
        public Edge(int src, int dest) {
            super();
            this.src = src;
            this.dest = dest;
        }
        public int getSrc() {
            return src;
        }
        public void setSrc(int src) {
            this.src = src;
        }
        public int getDest() {
            return dest;
        }
        public void setDest(int dest) {
            this.dest = dest;
        }
    
    
    
    }
    
    

    第二步:我们定义的一个图的类,如下

    package org.wrh.algorithmdemo;
    
    import java.util.List;
    
    //图的类
    public class Graph {
        /*
         * 图中的顶点的个数
         * */
        private int vertices_number;
        /*
         * 图中的边的个数
         * */
        private int edges_number;
        /*
         * 图中边对象的引用集合
         * */
        private List<Edge> edge;
        //下面为构造函数和属性的get、set方法
        public Graph(int vertices_number, int edges_number) {
            super();
            this.vertices_number = vertices_number;
            this.edges_number = edges_number;
        }
        public int getVertices_number() {
            return vertices_number;
        }
        public void setVertices_number(int vertices_number) {
            this.vertices_number = vertices_number;
        }
        public int getEdges_number() {
            return edges_number;
        }
        public void setEdges_number(int edges_number) {
            this.edges_number = edges_number;
        }
        public List<Edge> getEdge() {
            return edge;
        }
        public void setEdge(List<Edge> edge) {
            this.edge = edge;
        }
    
    
    
    }
    

    第三步:主函数类,如下

    package org.wrh.algorithmdemo;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class DisjuntSetCircle {
    
    
        public static void main(String[] args) {
            /*
             * 给定边的数量和顶点的数量
             * */
            int vertices_num=4;
            int edges_num=4;
            /*
             * new一个Graph对象,
             * */
            Graph graph=new Graph(vertices_num,edges_num);
            /*
             * 新建edges_num个Edge对象,构造一个List对象
             * */
            List<Edge> edge=new ArrayList<Edge>();
            edge.add(new Edge(0,1));
            edge.add(new Edge(1,2));
            edge.add(new Edge(2,3));
            edge.add(new Edge(3,0));
            /*
             * 将边加载到图中
             * */
            graph.setEdge(edge);//这样就构成了一个4个顶点4条边的图
            /*
             *定义parent数组来记录每个顶点属于那个集合的"代表元素";
             * 例如:我们的学生管理系统一般会记录我们的"班长"是谁一样
             * 
             * */
            int parent []=new int[vertices_num];
            /*
             * 首先我们将这些集合的代表元素初始化为 -1,表示他们都是单个元素的集合
             * */
            for(int i=0;i<parent.length;i++){
                parent[i]=-1;
    
            }
            /*
             * 下面来判断这个图中是否有环
             * */
            if(isCycle(graph,parent)){
                System.out.println("此图有环");
            }
            else{
                System.out.println("此图没有环");
            }
    
    
        }
    
        private static boolean isCycle(Graph graph,int[] parent) {
        /*
         *获取边的数量
         */
            int num=graph.getEdge().size();
            int src_represent;//用来表示边的起始点的"代表元素"
            int dest_represent;//用来表示边的终点的"代表元素"
            for(int i=0;i<num;i++){
                int src=graph.getEdge().get(i).getSrc();//得到边的起始点
                int dest=graph.getEdge().get(i).getDest();//得到边的终点
                src_represent=find(parent,src);//得到起点所属集合的代表元素
                dest_represent=find(parent,dest);//同上
                if(src_represent==dest_represent){//说明,边的两个顶点已经出现在了集合中,加上此边之后,构成"环"
                    return true;
                }
                else{//否则,合并
                    union(parent,src_represent,dest_represent);
    
                }
    
    
            }
            return false;
        }
        /*
         * 合并两个不相交的集合
         * */
        private static void union(int[] parent, int src, int dest) {
            /*
             * 由于两者是两个集合的不同的"代表元素",因此将其中的的“代表元素”改为另外一个即可完成合并
             * */
            parent[src]=dest;
        }
    
        /*
         * 用来寻找顶点X所在集合的"代表元素"
         * */
        private static int find(int[] parent, int x) {
            /*
             * 首先判断顶点x的"代表元素是不是等于-1",若等于-1,则说明,其自身就是"代表元素";
             * 若不等于-1,则说明此点在某个集合中并且不是代表元素,我们需找到他的代表元素的标号,即我们需要向上查找
             * */
            if(parent[x]==-1){
                return x;
    
            }
            return find(parent,parent[x]);
        }
    
    
    
    }
    

    上面的代码中注释写的比较详细,这里就不在解释,相信大家都能够看懂

    总结

    • 这篇博文是关于“环”的检测的思想还是挺简单的,主要是为我们后面最小生成树算法的java实现做准备的,关于最小生成树的java实现,我最近将会完成。

    关于”环”的检测的C语言实现和不相交集合的数据结构的知识可看这里,在此,对geeksforgeeks表示感谢,在这里,我学习到了很多知识。

    展开全文
  •  不相交集合的数据结构保持一组动态集合,每个集合通常有一个代表(也是该集合的成员),用以标识该集合。显然,由于这组动态集合是不相交的,那么集合代表(标识)自然也是独一无二的。对于不相交集合,我们希望其...

    不相交集合的定义和操作

        不相交集合的数据结构保持一组动态集合,每个集合通常有一个代表(也是该集合的成员),用以标识该集合。显然,由于这组动态集合是不相交的,那么集合代表(标识)自然也是独一无二的。对于不相交集合,我们希望其能够支持以下操作:

        1、MAKE-SET(x):创建一个集合,只含有一个元素x,那么该集合的代表自然就是x;

        2、FIND-SET(x):返回元素x所在的集合,即该集合的标识(代表);

        3、UNION(x,y):合并x和y分别所属的集合,合并后的集合的代表是x(或者y)所属集合的代表。


    不相交集合的链表表示

        这个不讨论了,比较简单。


    习题21.1-3

       2|E|,|V| - k

    习题 21.2-4

       时间O(n),UNION操作每次都是将长度为1的链表链到较长链表上的,指针修改时间均为O(1)。

    习题 21.2-5

       回顾单链表的链接。我们只需要将较短的集合链表链到较长集合链表的头结点的下一位置,即所谓头插法。


    不相交集合森林

        我们直接给出源代码,算法较简单,就不说了。采用了按秩(此处秩是指节点高度的一个上界,并不是节点数量)合并和路径压缩。

    #include<iostream>
    #include<vector>
    
    using namespace std;
    
    class UFS
    {//默认从1开始
    private:
    	vector<size_t> parent;
    	vector<size_t> rank;
    public:
    	explicit UFS(size_t size) :parent(size + 1), rank(size + 1){}
    	void makeSet(size_t i)
    	{
    		parent[i] = i;
    		rank[i] = 0;
    	}
    	void Union(size_t x, size_t y)
    	{
    		size_t left = findSet(x), right = findSet(y);
    		if (rank[left] < rank[right])
    			parent[left] = right;
    		else
    		{
    			parent[right] = left;
    			if (rank[left] == rank[right])
    				++rank[left];
    		}
    	}
    	size_t findSet(size_t x)
    	{
    		if (x == parent[x]) return x;
    		parent[x] = findSet(parent[x]);
    		return parent[x];
    	}
    };

    习题 21.3-2

    size_t findSet(size_t x)
    	{
    		size_t p = x;
    		while (p != parent[p])
    			p = parent[p];
    		while (x != p)
    		{
    			size_t y = parent[x];
    			parent[x] = p;
    			x = y;
    		}
    		return parent[x];
    	}

    习题 21.3-3

        1、首先进行n此的MAKE-SET,创建n个只含有一个元素的集合;

        2、接着进行n-1次的UNION操作,那么可以得到一棵树,由于采用按秩合并,那么该树的高度为O(lgn),以上两步的时间为O(n);

        3、最后,再进行m-2n+1次的FIND-SET操作,每次的时间为O(lgn),假设操作足够多,至少m>=3n,那么至少得有n-1次FIND-SET操作,又n<=m/3,所以操作总时间为O(mlgn)。


    习题 21.3-4

        采用记账方法,可得时间为O(m)。

        1、对每个MAKE-SET操作赋予两块钱的报酬,一块钱支付创建集合的花销,另外一块钱存着,留作后用;

        2、对每个LINK操作赋予一块钱的报酬,刚好用于支付该操作的代价;

        3、同样的,对于每个FIND-SET操作,我们也只赋予一块钱支付;若只采用路径压缩,在递归调用中,对于每一个节点,最多有一次被重新设置parent,这时候我们用之前存着的一块钱来支付代价,刚好足够。

       由于每个操作的代价最多为2,那么m个操作序列,最多的总代价也就是2m,因此总时间为O(m)。另外,上述分析中,我们只采用了路径压缩,没有采用按秩合并。


    思考题21-1

       (a)E1~E6分别为:4,3,2,6,8,1.

       (b)采用循环不变式:对第i次迭代,即数字i,前面的1,2...i-1均找到了所处的集合j',并当j<m+1时,都已经正确的设置了extracted[j']和将集合j'往后合并了,若等于m+1,则不处理;现在对于i,依然如此执行。

        初始:i为1,前面没有数字,成立;

        保持:确定数字i处于集合j,算法3~6行,若j<m+1,则j不可能会是已经被设置的,因为每次集合合并都会往后合并,那么设置extracted[j] = i,并且找到下一个集合将j合并过去;若j = m+1,则不作处理,因为没有第m+1次extraction。

        终止:i = n + 1.根据循环不变式可知:i之前,也就是1~n均已找到所属集合j(可能为m+1),并正确设置了extracted(除了为m+1时),由此证明该算法正确。

        (c)对于诸insert集合用一个链表链起来,集合j被合并,则将其删除。

          1、确定i属于哪个集合,采用FIND-SET;

          2、取得下一个可用集合,用链表的next域;

          3、合并则使用UNION;

        在此之前的MAKE-SET最多n次,那么UNION最多n-1次,根据循环,还有n次FIND-SET,那么时间显然为O(na(n))。



    思考题 21-3 Tarjan的脱机最小公共祖先算法





    
    展开全文
  • 不相交集合,即集合内元素无...导论中给出了链表和有根树两类数据结构来支持不相交集合的操作。 1、不相交集合的基本定义 不相交集合数据结构保持一组不相交的动态集合S={S1, S2,…, Sk}。每个集合通过一个代表来识

    不相交集合,即集合内元素无交集。在一些具体应用中,需将n个不同的元素分成一组不相交的集合。不相交集合的两个重要操作,找出给定元素所属的集合和合并两个集合。为支持不相交集合的操作,需要设计和维护数据结构来满足。导论中给出了链表和有根树两类数据结构来支持不相交集合的操作。

    1、不相交集合的基本定义

    不相交集合数据结构保持一组不相交的动态集合S={S1, S2,…, Sk}。每个集合通过一个代表来识别,代表即集合中的某个成员。选择代表成员视乎具体应用,如选择最小元素。

    集合中的每一个元素是由一个对象表示的。设x表示一个对象,支持以下操作:

    1)Make-set(x):建立一个新的集合,其唯一成员就是x。各集合是不相交的,所以x没有在其他集合中出现过;

    2)Union(x,y):将包含x和y的动态集合(Sx和Sy)合并成一个新的集合(并集SxUSy),当然Sx和Sy是不相交的。

    3)Find-set(x):返回一个指针,指向包含x的唯一集合的代表。

    分析不相交集合数据结构运行时间,主要考察两个参数:

    1)Make-set操作的次数n;

    2)执行Make-set、Union、Find-set操作的总次数m,其中Union操作至多为n-1,因包含Make-set操作,所以m>=n。

    2、不相交集合的一个应用

    不相交集合数据结构的应用之一:用于确定一个无向图中连通子图的个数。算法上,首先将每个定点v置于各自的集合中,即执行Make-set操作;接着,对每一条边(u,v)进行合并,即Union操作,当然包含u和v的集合是不相交的,对每条边处理后,两个顶点在同一连通子图中的,其对应对象也在同一个集合中;最后,通过Find-set操作好处顶点是否在同一连通子图中。

    3、不相交集合链表数据结构

    每一个集合用一个链表表示,链表作为不相交集合的数据结构,其每一个对象都包含一个集合成员、一个指向包含下一个集合成员的对象的指针、指向代表的指针;而每个链表都包含head指针和tail指针,head指向链表的代表,tail指向链表中最后的对象。链表中对象以任何次序出现,确保第一个对象就是所在集合的代表即可。

    用链表实现不相交集合数据结构,Make-set和Find-set操作都只需O(1)时间。按照上面定义的n和m参数,执行Union操作(作用于n个对象上,包含m个操作序列)的运行时间是,一个操作的平摊时间是

    我对导论中的链表设计有点疑问,为什么每个对象指向代表的指针,不改为指向下一个对象的指针呢?这样在合并操作时,只要更改一个链表头尾指针,链表中每个对象不用更新。是否有其他因素考虑,比如别的操作性能更好,但暂时没理解到。

    对于Union合并操作,还给出一种加权合并启发式策略,就是把较短的表拼接到较长的表。因为Union操作时,要拼接的链表,每个对象都要更新其指向代表对象的指针,这更新就和链表的长度成线性关系,所以短的链表去拼接,时间有优势。应用加权启发式策略,m个操作序列只需要O(m+nlgn)时间。

    问题是:如何识别出较短长度的链表?

    4、不相交集合有根树数据结构

    用有根树表示集合,树中的每个结点都包含集合的一个成员,每棵树表示一个集合,群树构成森林。每棵树的根就是链表的代表,并且指向自己作为父结点。Make-set创建一个颗仅包含一个结点的树。Find-set是沿着父结点指针一直找下去,直至找到树根为止,查找路径上访问过的所有结点构成了查找路径(find path),这里不明白的是,如果有分叉,顺着父结点查找如何找到呢?Union操作使一颗树的根指向另一个树的根。

    通过两种启发式策略来改进运行时间:

    1)按秩合并:和链表中的加权合并思路一致,将较少结点的树的根指向包含较多结点的树的根。具有较小秩的根在Union操作中药指向具有较大秩的根。

    2)路径压缩:在Find-set操作中,使查找路径上的每个结点都指向根节点。这个好理解,就是n个元素的集合,1个根,其他n-1个都是子女,互相构成兄弟,只有2层深度树。

    当同时使用按秩合并和路径压缩时,最坏情况运行时间为,其中是一个增长极其缓慢的函数,在任意可想象的不相交集合数据结构应用中

    对作用于n个元素上的m个不相交集合操作,联合使用按秩合并和路径压缩启发式的运行时间是界。导论中证明了是增长极其缓慢的函数。

    证明的界是用平摊分析中的势方法,证明是增长极快函数的逆函数。有趣的是这个增长尽快的函数。计算机算法基础,之所以离不开数学,就在于任何算法的合理性(时间界运行性能)都需要数学的证明,当然设计算法(或说是模型)也需要数学基础,否则就是无根之萍。

    每种算法,每种数据结构,都尤其特定应用场合,所以在实际应用中,改良甚至创新都是必要的,但都要基于扎实的数学理论基础。一种算法、一种数据结构,可以说是一种模型,是一种在应用中归纳升华出来的一种理论,可以应用于同类场合。当然关乎到数学基本问题,比如集合论对计算机理论的支持。
    展开全文
  • 用于不相交集合的数据结构 总结:这一章讲了并查集的相关概念,以及主要的MAKE-SET, UNION, FIND-SET操作,并给出了并查集的链表表示和森林表示方式。 1. 不相交集合上的操作 不相交集合数据结构保持一组不...

     用于不相交集合的数据结构

    总结:这一章讲了并查集的相关概念,以及主要的MAKE-SET, UNION, FIND-SET操作,并给出了并查集的链表表示和森林表示方式。

    1.    不相交集合上的操作

    不相交集合数据结构保持一组不相交的动态集合,每个集合通过一个代表来标识,代表即集合中的某个成员。

    一些操作:

    MAKE-SET(x): 建立一个新的集合,其唯一成员为x。

    UNION(x,y): 将包含x和y的动态集合合并为一个新的集合。

    FIND-SET(x): 返回一个指针,指向包含x的集合的代表。

    应用:例如,确定一个无向图中连通子图的个数。

    2.    不相交集合的链表表示

    每一个集合用一个链表表示。每个链表中的第一个对象作为它所在集合的代表。

    每一个对象的结构:

    1)集合成员

    2)指向包含下一个集合成员的对象的指针

    3)指向代表的指针

    每个链表都包含head指针和tail指针,head指向链表的代表,tail指向链表中最后的对象。

    MAKE-SET(x): O(1),创建新链表,其仅有对象为x

    FIND-SET(x): O(1),返回x指向代表的指针

    UNION(x,y): 将x所在的链表拼接到y所在链表的表尾。注意,对于原先x所在链表中的每一个对象,都需要更新其指向代表的指针。

    加权合并启发式策略:设每个表还包括了表的长度,合并时,总是把较短的表拼到较长的表上。

    使用加权合并策略,对m个MAKE-SET, UNION和FIND-SET操作所构成的序列(其中n个MAKE-SET操作,因此UNION操作的次数至多为n-1),花费的总时间为O(m+nlgn)。

    3.    不相交集合森林

    利用有根树来表示集合,每棵树表示一个集合。树中的每个成员仅指向其父节点,树的根的父节点仍是自己,且树的根即集合的代表。

    启发式策略:

    1)按秩合并

    合并时,使包含较少结点的树的根指向包含较多结点的树的根。秩,结点高度的上界。因此,即,具有较小秩的根在UNION操作中要指向具有较大秩的根。

    2)路径压缩

    在FIND-SET操作中,使查找路径上的每个结点都直接指向根节点。

    设rank[x]表示结点的秩,即x的高度的上界,p[x]表示x的父节点

    伪代码

    MAKE-SET(x)

    p[x] <- x

    rank[x] <- 0

    伪代码

    UNION(x,y)

    LINK(FIND-SET(x),FIND-SET(y))

    伪代码

    LINK(x,y)

    if rank[x] > rank[y]

          then p[y] <- x

          else p[x] <- y

                if rank[x]=rank[y]

                     then rank[y] <- rank[y]+1

    伪代码

    FIND-SET(x)

    if x!=p[x]

          then p[x] <- FIND-SET(p[x])

    return p[x]

    FIND-SET采用了两趟方法:一趟沿查找路径上升,直至找到根;第二趟沿查找路径下降,以便更新每个结点,使之直接指向根。

    分析:当同时采用按秩合并和路径压缩时,对m个MAKE-SET, UNION, FIND-SET的操作序列,总的运行时间可看作与m成线性关系。

    附录:

    1. typedef struct _node 
    2.     _node* parent; 
    3.     int rank; 
    4. }node; 
    5.  
    6. node *s[5000]; 
    7.  
    8. void makeSet(int x) 
    9.     s[x]=new node; 
    10.     s[x]->rank=0; 
    11.     s[x]->parent=s[x]; 
    12.  
    13. node* findSet(node* s) 
    14.     if(s!=s->parent) 
    15.     { 
    16.         s->parent=findSet(s->parent); 
    17.     } 
    18.     return s->parent; 
    19.  
    20. void link(node *s1, node *s2) 
    21.     if(s1==s2) 
    22.         return; 
    23.     if(s1->rank > s2->rank) 
    24.         s2->parent=s1; 
    25.     else 
    26.     { 
    27.         s1->parent=s2; 
    28.         if(s1->rank==s2->rank) 
    29.             s2->rank++; 
    30.     } 
    31.  
    32. void _union(node *s1, node *s2) 
    33.     link(findSet(s1),findSet(s2)); 

    展开全文
  • 不相交集合数据结构的概念和操作:  不相交集合数据结构(disjoing-set data structure)保持一组不相交动态集合S={S1,S2,S3,……Sk}。每个集合通过一个代表来识别,代表即集合某个成员。 不相交集合数据...
  • 不相交集合数据结构的概念和操作:  不相交集合数据结构(disjoing-set data structure)保持一组不相交动态集合S={S1,S2,S3,……Sk}。每个集合通过一个代表来识别,代表即集合某个成员。 我们希望不...
  • 第二十一章用于不相交集合的数据结构总结:这一章讲了并查集的相关概念,以及主要的MAKE-SET, UNION, FIND-SET操作,并给出了并查集的链表表示和森林表示方式。1. 不相交集合上的操作不相交集合数据结构保持一组不...
  • 一、队列队列接口指出,可以在头部删除,在尾部插入。收集对象时候按照先进先出...循环数组是一个有界集合,即容量有限。如果程序中要收集对象数量没有上限,就最好使用链表来实现。二、双端队列双端队列可以让...
  • 并查集保持一组不相交动态集合S={S1, S2, ..., SK}.每个集合通过一个代表来表示,代表即集合某个成员。 并查集精髓(即它三种操作): 集合每一个元素是由一个对象表示,设x表示一个对象 MAKE-SET...
  • 不相交集合(Disjoint-set )数据结构保持一组不相交动态集合S={S(1),S(2),...,S(k)}.每个集合通过一个代表(representative)来识别,即集合某个成员。设x表示一个对象,不相交集合支持操作: MAKE-SET(x):...
  • java集合数据结构深入解读

    千次阅读 2015-12-26 18:54:35
    Java集合在java的世界中是非常重要的一部分,主要集合包括List列表,Set集合,Map映射还有...集合的数据结构主要有集合、链表、队列、栈、数组、映射等 一、数组: Vector 1)、线程安全的,通过加锁的方式实现 2)
  • List集合&数据结构

    千次阅读 2020-06-16 14:09:21
    1.1集合的体系结构 集合类的特点 提供一种存储空间可变的存储模型,存储的数据容量可以随时发生改变 集合类的体系 1.2Collection集合概述和基本使用 Collection集合概述 是单例集合的顶层接口,他表示一组对象,...
  • 数据结构:八大数据结构分类

    万次阅读 多人点赞 2018-09-05 18:23:28
    常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示: 每一种数据结构都有着独特的数据存储方式,下面为大家介绍它们的结构和优缺点。 1、数组 数组是可以再内存中连续存储多个元素的...
  • Swift中的集合数据结构

    千次阅读 2015-09-15 08:27:54
    假设你有一个需要处理许多数据应用。你会把收据放在哪儿?...在那种情况下,你将会需要一种基本的集合数据结构。幸运是,这篇教程就是关于那个主题。下面是这篇教程构成: 你将会复习什么是数据
  • List集合存储数据的结构

    千次阅读 2018-12-05 22:43:10
    数据存储常用结构有:堆栈、队列、数组、链表。 1、堆栈 堆栈,采用该结构的集合,对元素存取有如下特点: 1.先进后出(即,存进去元素,要在它后面元素依次取出后,才能取出该元素)。 例如,子弹压...
  • Python set(集合)数据结构

    千次阅读 2018-12-25 16:34:41
    set(集合)是⼀个⾮常有⽤的数据结构。它与列表(list)的⾏为类似,区别在于set不能 包含重复的值。 这在很多情况下⾮常有⽤。例如你可能想检查列表中是否包含重复的元素,你有两个选 择,第⼀个需要使⽤for循环,就像...
  • 数据结构集合

    千次阅读 2014-02-11 13:27:09
    直接存储结构优点是:向数据结构中添加元素是很高效,只要直接放在数据末尾第一个空位上就可以了。它缺点是:向集合插入元素将会变得低效,它需要给插入元素腾出位置并顺序移动后面元素。
  • 集合这个概念应该大家在学习数学的时候都...集合就是一种包含着不同元素的数据结构,即在集合结构里,每一个元素都是独一无二的,互不相同,同时所有数据都是无序的。 如图中的每个圆圈就代表一个集合集合中存储着相
  • set(集合)数据结构

    千次阅读 2017-07-03 15:53:29
    (集合)是一个非常有用的数据结构。它与列表list的行为类似,区别在于set不能包含重复的值。 some_list = ['a', 'b', 'c', 'd', 'b', 'a', 'n', 'n'] duplicates = set([x for x in some_list if some_list.count(x)...
  • JavaScript数据结构-集合

    千次阅读 2016-11-06 15:41:57
    集合(set)是一种包含不同元素的数据结构集合中的元素称为成员。集合具有两个重要特性: (1)集合中的成员是无序的 (2)集合中不允许相同成员存在 当想创建一个数据结构,用来保存一些独一无二的元素时,...
  • 题目:设计并实现一个集合数据结构Set。一个集合中没有重复元素,支持下列运算: boolean add(E o) 如果 set 中尚未存在指定元素o,则添加此元素。 boolean addAll(Set c) 如果 set 中没有指定集合c中...
  • 有序集合zset内部数据结构分析

    千次阅读 2019-03-04 18:10:39
    有序集合zset在内部可以使用压缩列表ziplist或者跳跃表skiplist来实现。 压缩列表 如果使用压缩列表ziplist来实现,则键和分值紧凑相邻保存在压缩列表...集合每个元素键和分值都少于64个字节; 即在集合元素较...
  • 常用集合的底层数据结构

    千次阅读 2017-08-27 15:40:28
    1.2 要求掌握6个具体实现类 List: ArrayList, LinkedList Set: HashSet, TreeSet Map: HashMap, TreeMap   【面试】增加两个实现类:Vector, HashTable 题1: ArrayList和Vector区别? 题2:HashMap和
  • Java集合数据结构

    千次阅读 2015-08-03 07:21:26
    Set集合集合元素是不能重复。元素是没有顺序。所以它不能基于位置访问元素。TreeSet和HashSet是它实现类。 List集合集合元素是可以重复。元素是有顺序。所以它可以基于位置访问元素。ArrayList和...
  • 常用集合的底层数据结构和实现-Map

    千次阅读 2016-03-03 13:20:41
     常见的底层数据结构:在java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的(当然也不能绝对的说,但至少在java中现有的所以集合都是...
  • 集合中常用数据结构总结

    千次阅读 2019-04-28 20:17:49
    常见的和集合相关的数据结构有: 数组, 栈, 队列,链表,哈希表, 二叉树 下面简单总结一下个数据结构特点: 1. 数组 ArrayList(public class ArrayList extends AbstractList implements List, RandomAccess, ...
  • 集合的底层数据结构原理决定了集合的一些特性,在这里对这几种数据结构特点简答介绍下,这几种数据结构也是最常见数据结构
  • 数据结构-集合

    千次阅读 2019-05-06 17:21:36
    假设利用两个线性表LA和LB分别表示两个集合A和B(即:线性表中的数据元素即为集合中的成员),现要求一个新的集合A=A∪B。这就要求对线性表做如下操作:扩大线性表LA,将存在于线性表LB中而不存在于线性表LA中的数据...
  • Java 数据结构集合

    千次阅读 2018-11-15 23:01:22
    List 集合是线性数据结构的主要实现,List 集合的遍历结果是稳定的。该体系最常用的是 ArrayList 和 LinkedList。 ArrayList 是容量可以改变的非线程安全集合。内部实现使用数组进行存储,集合扩容时会创建更大的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 72,165
精华内容 28,866
关键字:

集合的数据结构

数据结构 订阅