精华内容
下载资源
问答
  • java 中几种常用数据结构

    千次阅读 2017-10-17 09:25:13
    中)java中有几种常用数据结构,主要分为Collection和map两个主要接口(接口只提供方法,并不提供实现),而程序中最终使用的数据结构是继承自这些接口的数据结构类。其主要的关系(继承关系): (----详细...

    JAVA中常用的数据结构(java.util. 中)

    java中有几种常用的数据结构,主要分为Collection和map两个主要接口(接口只提供方法,并不提供实现),而程序中最终使用的数据结构是继承自这些接口的数据结构类。其主要的关系(继承关系)有:  (----详细参见java api文档!)

    Collection---->Collections                                                                                                          Map----->SortedMap------>TreeMap

    Collection---->List----->(Vector \ ArryList \ LinkedList)                                                          Map------>HashMap

    Collection---->Set------>(HashSet \ LinkedHashSet \ SortedSet)

    --------------Collection----------------

    1、Collections

        API----This class consists exclusively of static methods that operate on or return collections. It contains polymorphic algorithms that operate on collections, "wrappers", which return a new collection backed by a specified collection, and a few other odds and ends.

    The methods of this class all throw a NullPointerException if the collections or class objects provided to them are null. 

    2、List

        API----This class consists exclusively of static methods that operate on or return collections. It contains polymorphic algorithms that operate on collections, "wrappers", which return a new collection backed by a specified collection, and a few other odds and ends.

    The methods of this class all throw a NullPointerException if the collections or class objects provided to them are null. 

    List是有序的Collection,使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引(元素在List中的位置,类似于数组下 >标)来访问List中的元素,这类似于Java的数组。

    3、Vector

         API----The Vector class implements a growable array of objects. Like an array, it contains components that can be accessed using an integer index. However, the size of aVector can grow or shrink as needed to accommodate adding and removing items after theVector has been created. 

    基于数组(Array)的List,其实就是封装了数组所不具备的一些功能方便我们使用,所以它难易避免数组的限制,同时性能也不可能超越数组。所以,在可能的情况下,我们要多运用数组。另外很重要的一点就是Vector是线程同步的(sychronized)的,这也是Vector和ArrayList 的一个的重要区别。 

    4、ArrayList

         API----Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)

    同Vector一样是一个基于数组上的链表,但是不同的是ArrayList不是同步的。所以在性能上要比Vector好一些,但是当运行到多线程环境中时,可需要自己在管理线程的同步问题。

    5、LinkedList

         API----Linked list implementation of the List interface. Implements all optional list operations, and permits all elements (including null). In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or double-ended queue

    LinkedList不同于前面两种List,它不是基于数组的,所以不受数组性能的限制。 
    它每一个节点(Node)都包含两方面的内容: 
    1.节点本身的数据(data); 
    2.下一个节点的信息(nextNode)。 
    所以当对LinkedList做添加,删除动作的时候就不用像基于数组的ArrayList一样,必须进行大量的数据移动。只要更改nextNode的相关信息就可以实现了,这是LinkedList的优势。

    List总结:

    • 所有的List中只能容纳单个不同类型的对象组成的表,而不是Key-Value键值对。例如:[ tom,1,c ]
    • 所有的List中可以有相同的元素,例如Vector中可以有 [ tom,koo,too,koo ]
    • 所有的List中可以有null元素,例如[ tom,null,1 ]
         基于Array的List(Vector,ArrayList)适合查询,而LinkedList 适合添加,删除操作

    6、Set(接口)

         API-----A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction. 
    Set是不包含重复元素的Collection

    7、HashSet

       API-----This class implements theSet interface, backed by a hash table (actually aHashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits thenull element. 

    虽然Set同List都实现了Collection接口,但是他们的实现方式却大不一样。List基本上都是以Array为基础。但是Set则是在 HashMap的基础上来实现的,这个就是Set和List的根本区别。HashSet的存储方式是把HashMap中的Key作为Set的对应存储项。看看 HashSet的add(Object obj)方法的实现就可以一目了然了。

    8、LinkedHashSet

        API----Linked list implementation of the List interface. Implements all optional list operations, and permits all elements (includingnull). In addition to implementing theList interface, theLinkedList class provides uniformly named methods toget, remove andinsert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack,queue, ordouble-ended queue
    HashSet的一个子类,一个链表。

    9、SortedSet

       API---ASet that further provides atotal ordering on its elements. The elements are ordered using theirnatural ordering, or by aComparator typically provided at sorted set creation time. The set's iterator will traverse the set in ascending element order. Several additional operations are provided to take advantage of the ordering. (This interface is the set analogue ofSortedMap.)  

    有序的Set,通过SortedMap来实现的。

    Set总结:

    (1)Set实现的基础是Map(HashMap)(2)Set中的元素是不能重复的,如果使用add(Object obj)方法添加已经存在的对象,则会覆盖前面的对象

    -------------Map-----------------

    Map 是一种把键对象和值对象进行关联的容器,而一个值对象又可以是一个Map,依次类推,这样就可形成一个多级映射。对于键对象来说,像Set一样,一个 Map容器中的键对象不允许重复,这是为了保持查找结果的一致性;如果有两个键对象一样,那你想得到那个键对象所对应的值对象时就有问题了,可能你得到的并不是你想的那个值对象,结果会造成混乱,所以键的唯一性很重要,也是符合集合的性质的。当然在使用过程中,某个键所对应的值对象可能会发生变化,这时会按照最后一次修改的值对象与键对应。对于值对象则没有唯一性的要求,你可以将任意多个键都映射到一个值对象上,这不会发生任何问题(不过对你的使用却可能会造成不便,你不知道你得到的到底是那一个键所对应的值对象)。

    1、HashMap

       API----Hash table based implementation of theMap interface. This implementation provides all of the optional map operations, and permitsnull values and the null key. (The HashMap class is roughly equivalent toHashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.  

    2、TreeMap

       API----A Red-Black tree basedNavigableMap implementation. The map is sorted according to thenatural ordering of its keys, or by aComparator provided at map creation time, depending on which constructor is used. 
    TreeMap则是对键按序存放,因此它便有一些扩展的方法,比如firstKey(),lastKey()等,你还可以从TreeMap中指定一个范围以取得其子Map。 
    键和值的关联很简单,用put(Object key,Object value)方法即可将一个键与一个值对象相关联。用get(Object key)可得到与此key对象所对应的值对象。 

    ------------说明-----------

    一、几个常用类的区别 
    1.ArrayList: 元素单个,效率高,多用于查询 
    2.Vector: 元素单个,线程安全,多用于查询 
    3.LinkedList:元素单个,多用于插入和删除 
    4.HashMap: 元素成对,元素可为空 
    5.HashTable: 元素成对,线程安全,元素不可为空 
    二、Vector、ArrayList和LinkedList 
    大多数情况下,从性能上来说ArrayList最好,但是当集合内的元素需要频繁插入、删除时LinkedList会有比较好的表现,但是它们三个性能都比不上数组,另外Vector是线程同步的。所以: 
    如果能用数组的时候(元素类型固定,数组长度固定),请尽量使用数组来代替List; 
    如果没有频繁的删除插入操作,又不用考虑多线程问题,优先选择ArrayList; 
    如果在多线程条件下使用,可以考虑Vector; 
    如果需要频繁地删除插入,LinkedList就有了用武之地; 
    如果你什么都不知道,用ArrayList没错。 
    三、Collections和Arrays 
    在 Java集合类框架里有两个类叫做Collections(注意,不是Collection!)和Arrays,这是JCF里面功能强大的工具,但初学者往往会忽视。按JCF文档的说法,这两个类提供了封装器实现(Wrapper Implementations)、数据结构算法和数组相关的应用。 
    想必大家不会忘记上面谈到的“折半查找”、“排序”等经典算法吧,Collections类提供了丰富的静态方法帮助我们轻松完成这些在数据结构课上烦人的工作: 
    binarySearch:折半查找。 
    sort:排序,这里是一种类似于快速排序的方法,效率仍然是O(n * log n),但却是一种稳定的排序方法。 
    reverse:将线性表进行逆序操作,这个可是从前数据结构的经典考题哦! 
    rotate:以某个元素为轴心将线性表“旋转”。 
    swap:交换一个线性表中两个元素的位置。 
    …… 
    Collections还有一个重要功能就是“封装器”(Wrapper),它提供了一些方法可以把一个集合转换成一个特殊的集合,如下: 
    unmodifiableXXX:转换成只读集合,这里XXX代表六种基本集合接口:Collection、List、Map、Set、SortedMap和SortedSet。如果你对只读集合进行插入删除操作,将会抛出UnsupportedOperationException异常。 
    synchronizedXXX:转换成同步集合。 
    singleton:创建一个仅有一个元素的集合,这里singleton生成的是单元素Set, 
    singletonList和singletonMap分别生成单元素的List和Map。 
    空集:由Collections的静态属性EMPTY_SET、EMPTY_LIST和EMPTY_MAP表示。 


    展开全文
  • 数据结构大致包含以下几种存储结构: 线性表,还可细分为顺序表、链表、栈和队列; 树结构,包括普通树,二叉树,线索二叉树等; 图存储结构; 线性表 线性表结构存储的数据往往是可以依次排列的,就像小朋友手拉手...

    数据结构大致包含以下几种存储结构:
    线性表,还可细分为顺序表、链表、栈和队列;
    树结构,包括普通树,二叉树,线索二叉树等;
    图存储结构;
    线性表
    线性表结构存储的数据往往是可以依次排列的,就像小朋友手拉手,每位学生的前面和后面都仅有一个小朋友和他拉手,具备这种“一对一”关系的数据就可以使用线性表来存储。

    例如,存储类似 {1,3,5,7,9} 这样的数据时,各元素依次排列,每个元素的前面和后边有且仅有一个元素与之相邻(除首元素和尾元素),因此可以使用线性表存储。

    线性表并不是一种具体的存储结构,它包含顺序存储结构和链式存储结构,是顺序表和链表的统称。
    顺序表
    顺序表,简单地理解,就是常用的数组,只是换了个名字而已,例如使用顺序表存储 {1,3,5,7,9},如图 1 所示:

    顺序表结构
    图 1 顺序表结构
    由于顺序表结构的底层实现借助的就是数组,因此对于初学者来说,可以把顺序表完全等价为数组,但实则不是这样。数据结构是研究数据存储方式的一门学科,它囊括的都是各种存储结构,而数组只是各种编程语言中的基本数据类型,并不属于数据结构的范畴。
    在这里插入图顺序表结构片描述
    顺序表结构
    链表
    我们知道,使用顺序表(底层实现靠数组)时,需要提前申请一定大小的存储空间,这块存储空间的物理地址是连续的,如图 1 所示。

    链表则完全不同,使用链表存储数据时,是随用随申请,因此数据的存储位置是相互分离的,换句话说,数据的存储位置是随机的。

    为了给各个数据块建立“依次排列”的关系,链表给各数据块增设一个指针,每个数据块的指针都指向下一个数据块(最后一个数据块的指针指向 NULL),就如同一个个小学生都伸手去拉住下一个小学生的手,这样,看似毫无关系的数据块就建立了“依次排列”的关系,也就形成了链表,如图 2 所示:

    链表结构
    图 2 链表结构
    在这里插入图片描述

    栈和队列
    栈和队列隶属于线性表,是特殊的线性表,因为它们对线性表中元素的进出做了明确的要求。

    栈中的元素只能从线性表的一端进出(另一端封死),且要遵循“先入后出”的原则,即先进栈的元素后出栈。

    栈结构示意图
    图 3 栈结构示意图
    在这里插入图片描述

    栈结构如图 3 所示,像一个木桶,栈中含有 3 个元素,分别是 A、B 和 C,从在栈中的状态可以看出 A 最先进的栈,然后 B 进栈,最后 C 进栈。根据“先进后出”的原则,3 个元素出栈的顺序应该是:C 最先出栈,然后 B 出栈,最后才是 A 出栈。

    队列中的元素只能从线性表的一端进,从另一端出,且要遵循“先入先出”的特点,即先进队列的元素也要先出队列。

    队列结构示意图
    图 4 队列结构示意图

    队列结构如图 4 所示,队列中有 3 个元素,分别是 A、B 和 C,从在队列中的状态可以看出是 A 先进队列,然后 B 进,最后 C 进。根据“先进先出”的原则,3 个元素出队列的顺序应该是 A 最先出队列,然后 B 出,最后 C 出。
    树存储结构
    树存储结构适合存储具有“一对多”关系的数据。

    树存储结构示意图
    图 5 树存储结构示意图
    在这里插入图片描述

    如图 5 所示,其中张平只有一个父亲,但他却有两(多)个孩子,这就是“一对多”的关系,满足这种关系的数据可以使用树存储结构。
    图存储结构
    图存储结构适合存储具有“多对多”关系的数据。

    图存储结构示意图
    图 6 图存储结构示意图

    如图 6 所示,从 V1 可以到达 V2、V3、V4,同样,从 V2、V3、V4 也可以到达 V1,这就是“多对多”的关系,满足这种关系的数据可以使用图存储结构。

    展开全文
  • 数据结构在实际应用中非常常见,现在各种算法基本都牵涉...因此,数据在计算机存储空间的存放,决不是胡乱的,这就要求我们选择一好的方式来存储数据,而这也是数据结构的核心内容。 数据存储 一直以来大家面对的数据

    数据结构在实际应用中非常常见,现在各种算法基本都牵涉到数据结构,因此,掌握数据结构算是软件工程师的必备技能。

    一、什么是数据结构

    数据结构,直白地理解,就是研究数据的存储方式。

    我们知道,数据存储只有一个目的,即为了方便后期对数据的再利用,就如同我们使用数组存储 {1,2,3,4,5} 是为了后期取得它们的加和值,无缘由的数据存储行为是对存储空间的不负责任。

    因此,数据在计算机存储空间的存放,决不是胡乱的,这就要求我们选择一种好的方式来存储数据,而这也是数据结构的核心内容。

    数据存储

    一直以来大家面对的数据存储,都是类似存储 1、 2、{a,b,c}、 这样的问题,解决方式无疑是用变量或者数组对数据进行存储,即:

    int a=1;int b=2;char str[3]={'a','b','c'};char *data="http://www.strongerhuang.com";
    

    但是,如果要存储这样一组数据:{张亮,张平,张华,张群,张晶,张磊},数据之间具有这样的关系:张亮是张平、张华和张群的父亲,同时张平还是张晶和张磊的父亲,数据之间的关系如图 1 所示:

    在这里插入图片描述
    对于存储之间具有复杂关系的数据,如果还是用变量或数组来存储(比如用数组存储 {“张亮”,“张平”,“张华”,“张群”,“张晶”,“张磊”} ),数据存储是没有问题,但是无法体现数据之间的逻辑关系,后期根本无法使用,显然不明智。

    针对此类数据,数据结构中提供有专门的树结构来存储这类数据。

    再比如,导航无疑是出游旅行的必备神器,在我们程序员眼中,无论是哪款导航软件,其导航功能的实现都需要大量地图数据的支持。很明显,这些数据绝不是使用变量或数组进行存储的,那样对于数据的使用简直是个悲剧。

    针对此类数据,数据结构提供了图存储结构,专门用于存储这类数据。

    其实做为一个学习者,有一个学习的氛围跟一个交流圈子特别重要这里我推荐一个C语言C++交流群1075673198,不管你是小白还是转行人士欢迎入驻,大家一起交流成长。

    二、数据结构存储分类

    大致包含以下几种存储结构:

    • 线性表,还可细分为顺序表、链表、栈和队列;

    • 树结构,包括普通树,二叉树,线索二叉树等;

    • 图存储结构;

    三、线性表

    线性表结构存储的数据往往是可以依次排列的,就像小朋友手拉手,每位学生的前面和后面都仅有一个小朋友和他拉手,具备这种“一对一”关系的数据就可以使用线性表来存储。

    例如,存储类似 {1,3,5,7,9} 这样的数据时,各元素依次排列,每个元素的前面和后边有且仅有一个元素与之相邻(除首元素和尾元素),因此可以使用线性表存储。

    线性表并不是一种具体的存储结构,它包含顺序存储结构和链式存储结构,是顺序表和链表的统称。

    其实做为一个学习者,有一个学习的氛围跟一个交流圈子特别重要这里我推荐一个C语言C++交流群1075673198,不管你是小白还是转行人士欢迎入驻,大家一起交流成长。

    1.顺序表

    顺序表,简单地理解,就是常用的数组,只是换了个名字而已,例如使用顺序表存储 {1,3,5,7,9},如图所示:

    由于顺序表结构的底层实现借助的就是数组,因此对于初学者来说,可以把顺序表完全等价为数组,但实则不是这样。数据结构是研究数据存储方式的一门学科,它囊括的都是各种存储结构,而数组只是各种编程语言中的基本数据类型,并不属于数据结构的范畴。

    2.链表

    我们知道,使用顺序表(底层实现靠数组)时,需要提前申请一定大小的存储空间,这块存储空间的物理地址是连续的,如图 1 所示。

    链表则完全不同,使用链表存储数据时,是随用随申请,因此数据的存储位置是相互分离的,换句话说,数据的存储位置是随机的。

    为了给各个数据块建立“依次排列”的关系,链表给各数据块增设一个指针,每个数据块的指针都指向下一个数据块(最后一个数据块的指针指向 NULL),就如同一个个小学生都伸手去拉住下一个小学生的手,这样,看似毫无关系的数据块就建立了“依次排列”的关系,也就形成了链表,如图所示:

    3.栈和队列

    栈和队列隶属于线性表,是特殊的线性表,因为它们对线性表中元素的进出做了明确的要求。 栈中的元素只能从线性表的一端进出(另一端封死),且要遵循“先入后出”的原则,即先进栈的元素后出栈。

    栈结构如上图所示,像一个木桶,栈中含有 3 个元素,分别是 A、B 和 C,从在栈中的状态可以看出 A 最先进的栈,然后 B 进栈,最后 C 进栈。根据“先进后出”的原则,3 个元素出栈的顺序应该是:C 最先出栈,然后 B 出栈,最后才是 A 出栈。

    队列中的元素只能从线性表的一端进,从另一端出,且要遵循“先入先出”的特点,即先进队列的元素也要先出队列。

    队列结构如上图所示,队列中有 3 个元素,分别是 A、B 和 C,从在队列中的状态可以看出是 A 先进队列,然后 B 进,最后 C 进。根据“先进先出”的原则,3 个元素出队列的顺序应该是 A 最先出队列,然后 B 出,最后 C 出。

    四、树存储结构

    树存储结构适合存储具有“一对多”关系的数据。

    如上图所示,其中张平只有一个父亲,但他却有两(多)个孩子,这就是“一对多”的关系,满足这种关系的数据可以使用树存储结构。

    五、图存储结构

    图存储结构适合存储具有“多对多”关系的数据。

    如上所示,从 V1 可以到达 V2、V3、V4,同样,从 V2、V3、V4 也可以到达 V1,这就是“多对多”的关系,满足这种关系的数据可以使用图存储结构。

    展开全文
  • 数据结构:八大数据结构分类

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

    本文目录:

    数据结构分类

    数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。
    常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示:
    这里写图片描述
    每一种数据结构都有着独特的数据存储方式,下面为大家介绍它们的结构和优缺点。

    1、数组

    数组是可以再内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为 1。

    int[] data = new int[100];data[0]  = 1;
    

    优点:
    1、按照索引查询元素速度快
    2、按照索引遍历数组方便

    缺点:
    1、数组的大小固定后就无法扩容了
    2、数组只能存储一种类型的数据
    3、添加,删除的操作慢,因为要移动其他的元素。

    适用场景:
    频繁查询,对存储空间要求不大,很少增加和删除的情况。

    2、栈

    栈是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作。 栈的特点是:先进后出,或者说是后进先出,从栈顶放入元素的操作叫入栈,取出元素叫出栈。
    这里写图片描述
    栈的结构就像一个集装箱,越先放进去的东西越晚才能拿出来,所以,栈常应用于实现递归功能方面的场景,例如斐波那契数列。

    3、队列

    队列与栈一样,也是一种线性表,不同的是,队列可以在一端添加元素,在另一端取出元素,也就是:先进先出。从一端放入元素的操作称为入队,取出元素为出队,示例图如下:
    这里写图片描述
    使用场景:因为队列先进先出的特点,在多线程阻塞队列管理中非常适用。

    4、链表

    链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,每个元素包含两个结点,一个是存储元素的数据域 (内存空间),另一个是指向下一个结点地址的指针域。根据指针的指向,链表能形成不同的结构,例如单链表,双向链表,循环链表等。
    这里写图片描述
    链表的优点:
    链表是很常用的一种数据结构,不需要初始化容量,可以任意加减元素;
    添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可,所以添加,删除很快;

    缺点:
    因为含有大量的指针域,占用空间较大;
    查找元素需要遍历链表来查找,非常耗时。

    适用场景:
    数据量较小,需要频繁增加,删除操作的场景

    5、树

    是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

    • 每个节点有零个或多个子节点;
    • 没有父节点的节点称为根节点;
    • 每一个非根节点有且只有一个父节点;
    • 除了根节点外,每个子节点可以分为多个不相交的子树;

    在日常的应用中,我们讨论和用的更多的是树的其中一种结构,就是二叉树
    这里写图片描述
    二叉树是树的特殊一种,具有如下特点:

    1、每个结点最多有两颗子树,结点的度最大为2。
    2、左子树和右子树是有顺序的,次序不能颠倒。
    3、即使某结点只有一个子树,也要区分左右子树。

    二叉树是一种比较有用的折中方案,它添加,删除元素都很快,并且在查找方面也有很多的算法优化,所以,二叉树既有链表的好处,也有数组的好处,是两者的优化方案,在处理大批量的动态数据方面非常有用。

    扩展:
    二叉树有很多扩展的数据结构,包括平衡二叉树、红黑树、B+树等,这些数据结构二叉树的基础上衍生了很多的功能,在实际应用中广泛用到,例如mysql的数据库索引结构用的就是B+树,还有HashMap的底层源码中用到了红黑树。这些二叉树的功能强大,但算法上比较复杂,想学习的话还是需要花时间去深入的。

    6、散列表

    散列表,也叫哈希表,是根据关键码和值 (key和value) 直接进行访问的数据结构,通过key和value来映射到集合中的一个位置,这样就可以很快找到集合中的对应元素。

    记录的存储位置=f(key)

    这里的对应关系 f 成为散列函数,又称为哈希 (hash函数),而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里,这种存储空间可以充分利用数组的查找优势来查找元素,所以查找的速度很快。

    哈希表在应用中也是比较常见的,就如Java中有些集合类就是借鉴了哈希原理构造的,例如HashMap,HashTable等,利用hash表的优势,对于集合的查找元素时非常方便的,然而,因为哈希表是基于数组衍生的数据结构,在添加删除元素方面是比较慢的,所以很多时候需要用到一种数组链表来做,也就是拉链法。拉链法是数组结合链表的一种结构,较早前的hashMap底层的存储就是采用这种结构,直到jdk1.8之后才换成了数组加红黑树的结构,其示例图如下:
    这里写图片描述
    从图中可以看出,左边很明显是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。

    哈希表的应用场景很多,当然也有很多问题要考虑,比如哈希冲突的问题,如果处理的不好会浪费大量的时间,导致应用崩溃。

    7、堆

    堆是一种比较特殊的数据结构,可以被看做一棵树的数组对象,具有以下的性质:

    • 堆中某个节点的值总是不大于或不小于其父节点的值;

    • 堆总是一棵完全二叉树。

    将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

    堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆。
    (ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2),满足前者的表达式的成为小顶堆,满足后者表达式的为大顶堆,这两者的结构图可以用完全二叉树排列出来,示例图如下:
    这里写图片描述
    因为堆有序的特点,一般用来做数组中的排序,称为堆排序。

    8、图

    图是由结点的有穷集合V和边的集合E组成。其中,为了与树形结构加以区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。

    按照顶点指向的方向可分为无向图和有向图:
    这里写图片描述
    这里写图片描述
    图是一种比较复杂的数据结构,在存储数据上有着比较复杂和高效的算法,分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构,这里不做展开,读者有兴趣可以自己学习深入。

    展开全文
  • 什么是数据结构

    千次阅读 2019-06-19 20:25:39
    数据结构是指相互之间存在一或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。 定义 名词定义 数据结构是指...
  • java中常见的几种数据结构

    千次阅读 2019-05-20 20:50:57
    数据结构相对于算法来说简直是屈指可数,常见的数据结构也就那几种,很容易掌握,但算法可以成千上万,要想全部掌握基本上很难,我们常说的数据结构和算法是指数据结构和算法的结合,如果对算法感兴趣的也可以关注...
  • 通过上节我们知道,数据结构是学习数据存储方式的一门学科,那么,数据存储方式几种呢?本节将对数据结构的学习内容做一个简要的总结。 数据结构大致包含以下几种存储结构: 线性表,还可细分为顺序表、链表、栈...
  • 1,树型结构是一类重要的非线性数据结构,其中以树和二叉树最为常用,直观看来,树是以分支关系定义的层次结构。 2,树(Tree) 是 n (n &gt;= 0)个 结点的有限集。在任意一棵非空树中。 (1)且仅一个...
  • 常用数据结构有哪些

    千次阅读 2018-12-07 13:27:18
    我们根据存储方式可将数据结构大概分成图1所示以下几种:  图1 (1)线性数据结构:元素之间一般存在元素之间存在一对一关系,是最常用的一类数据结构,典型的:数组、栈、队列和线性表。 (2)树形结构:结点...
  • Redis中常用种数据结构

    万次阅读 2018-06-04 21:04:41
    Redis是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、...这就是redis中五基本的数据类型和相关命令,更多干货和资料请直接联系我,也可以加群710520381,邀请码:柳猫,欢迎大家共同讨论
  • 那么,到底几种基本结构呢? 1,集合:集合中的每一个数据元素都是相互独立的,这跟数学里的集合是一致的。(还记得数学里集合的三要素呢,无序性,互异性,确定性) 2,线性结构数据之间是一对一的关系...
  • 数据结构几种存储方式

    万次阅读 2016-03-25 15:41:56
    在计算机中,数据的存储结构可以采用如下四方法来实现。 1、顺序存储方式:顺序存储方式就是在一块连续的存储区域一个接着一个的存放数据。顺序存储方式把逻辑上相邻的节点存储在物理位置撒花姑娘相邻的存储单元...
  • 常用数据结构-几种特殊的二叉树

    万次阅读 多人点赞 2012-05-01 22:48:25
    插入:分以下几种情况进行相应的处理:  ①如果相同键值的结点已在查找二叉树中,则不再插入;  ②如果查找二叉树为空树,则以新结点为查找二叉树;  ③将要插入结点的键值与插入后的父结点的键值...
  • 基本数据结构

    千次阅读 2019-03-18 09:29:46
    通常下列四类基本的结构: 集合结构:该结构数据元素间的关系是“属于同一个集合”; 线性结构:该结构数据元素之间存在一对一的关系; 树形结构:该结构数据元素之间存在一对多的关系; 图形结构:该...
  • 几种常见树形数据结构小结

    千次阅读 2017-07-13 20:52:02
    最近新学习了很多厉害的数据结构,在大佬们的熏陶之下,也感悟了很多,对大佬们的实力也了更加深厚的了解(先膜一番orz,换个姿势zto,再来一次owz)左偏树左偏树又名可并堆,多被用来对一些需要合并的一个集合体...
  • 常用八大数据结构总结及应用场景-附示例截图

    千次阅读 多人点赞 2020-08-03 21:32:42
    什么是数据结构? 官方解释:数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及他们之间的关系和操作等相关问题的学科。 大白话:数据结构就是把数据元素按照一定的关系组织起来的集合,用来组成和...
  • java常用几种数据结构,堆栈,队列,数组,链表,哈希表
  • 基本的数据结构有哪些

    千次阅读 2019-09-03 11:01:06
    图的存储结构: 1,邻接矩阵(数组表达) 2,邻接表和十字链表,链表表达,主要表达向图 3,邻接 表,链表,无向图 最小生成树: prim(普里姆算法) kruskal(克鲁斯卡尔算法) 形成闭环就抛弃 队列: ...
  • 数据结构数据结构常用的树

    万次阅读 多人点赞 2016-07-31 21:29:17
    声明:本文汇总了数据结构中一些常用的树,主要内容来自《数据结构(严蔚敏版)》和《算法导论》这两本教材。本文主要归纳出数据结构中常见的树的概念与简单的性质,并未给出具体的操作,如插入、删除、查找等。1、...
  • 几种常见的数据结构的java实现

    千次阅读 2016-04-06 15:23:28
    下面分别介绍这几种数据结构的实现方式: 1)栈 Stack 栈可以用数组实现也可以用列表实现,两种方式均top变量来标识栈顶,maxSize来标识栈的最大容量,栈的常见方法为push pop peek isEmpty isFull(通过top
  • 数据结构常用算法

    万次阅读 多人点赞 2015-10-02 14:04:00
    1. 常见数据结构 人们进行程序设计时通常关注两个重要问题,一是如何将待处理的数据存储到计算机内存中,即数据表示;二是设计算法操作这些数据,即数据处理。数据表示的本质是数据结构设计,数据处理的本质是算法...
  • 本文比较了用于数据准备的几种方法,它们分别是提取-变换-加载批处理(ETL)、流式获取和数据整理。本文还讨论了数据准备如何与可视化分析相关联,以及不同用户角色(如数据科学家或业务分析人员)应如何共同构建...
  • 3Python数据结构,11创建方法,这个总结,超赞!
  • C#常用数据结构

    万次阅读 多人点赞 2019-02-22 16:10:16
    U3D面试的时候,面试官经常会问到C#数据结构的问题。
  • 总结——STL 常用数据结构及用法

    千次阅读 2017-07-26 08:57:27
    C++中的STL(Standard Template Library),即标准模板库,中包含了很多编程时常用数据结构,省去了自己临时写的麻烦,这里就来总结一下。如果错误或写的不好的地方还请多指正。 首先稍微介绍下iterator(迭代器)...
  • ① 集合 集合中任何两个数据元素之间都没有逻辑关系,组织形式松散. ② 线性结构 线性结构中的 结点...集合:结构中的数据元素之间除了同属于一类型外,别无其它关系 线性结构结构中的数据元素之间存在一对一的...
  • 1.Numpy常用数据结构

    万次阅读 2020-02-07 17:22:29
    1.python中 numpy 和pandas主流的工具 2.Numpy中的向量化运算使得数据...1.Numpy中常用的数据结构是ndarray格式(避免下for循环 效率低) 2.使用array函数创建,语法格式为array(列表或元组) 3.可以使用其他...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 555,731
精华内容 222,292
热门标签
关键字:

常用的数据结构有几种

数据结构 订阅