精华内容
下载资源
问答
  • 数据结构分类及八种常见数据结构

    千次阅读 2020-05-09 11:04:00
    数据结构分类 数据的逻辑结构 1.集合:数据结构中的元素之间除了“同属一个集合” 的相互关系外,别无其他关系; 2.线性结构:数据结构中的元素存在一对一的相互关系; 3.树形结构:数据结构中的元素存在一对多的...

    一.数据结构分类
    数据的逻辑结构
    1.集合:数据结构中的元素之间除了“同属一个集合” 的相互关系外,别无其他关系;
    2.线性结构:数据结构中的元素存在一对一的相互关系;
    3.树形结构:数据结构中的元素存在一对多的相互关系;
    4.图形结构:数据结构中的元素存在多对多的相互关系。

    数据的存储结构:
    顺序存储结构:数据元素在内存中的物理存储顺序与他们的逻辑顺序相同
    链式存储结构:使用若干地址分散的存储单元存储数据元素,逻辑上相邻的数据元素在物理位置上不一定相邻,数据元素之间的关系需要采用附加信息特别指定。c语言采用指针,Java采用引用指定。

    线性结构和非线性结构两类
    线性结构:最多只有一个直接前趋结点(第一个没有)和一个直接后继结点。栈、队列和串等都属于线性结构
    非线性结构:可能有多个直接前趋结点和多个直接后继结点,数组、广义表、树结构和图

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

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

    int[] data = new int[100];data[0] = 1;
    1
    2
    优点:
    1、按照索引查询元素速度快
    2、按照索引遍历数组方便

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

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

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

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

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

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

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

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

    每个节点有零个或多个子节点;
    没有父节点的节点称为根节点;
    每一个非根节点有且只有一个父节点;
    除了根节点外,每个子节点可以分为多个不相交的子树;
    在日常的应用中,我们讨论和用的更多的是树的其中一种结构,就是二叉树。
    在这里插入图片描述
    二叉树是树的特殊一种,具有如下特点:

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

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

    红黑树,是在JDK1.8之后在HashMap中数据结构的升级
    一种树结构如 98(节点:存贮着key,value)
    78 125
    51 89 118 169

    右边值大于中间值,中间值大于左边值,当条件查询查询key为125的值时,如果不加索引那么将进行6次磁盘I/O,如果添加索引将只要进行2次磁盘I/O.
    查询流程: 直接从key为98的值根元素开始查询(1次磁盘I/O),发现125大于98向右边查询找到125(2次磁盘I/O).
    不足:但如果数据量太大树的高度还是很高

    BTree(mysql)
    与红黑树一样但是在其每个节点中存储着多个key,value,当查询某条数据时会将这个节点所有的key,value都读取到内存中RAM,在RAM在找出对应的key(RAM中处理的非常快,时间可以忽略不计)
    78 118
    51 89 98 125 169
    78和118为一个节点,51为一个节点,89和98为一个节点,125和169为一个节点.
    当查询169时只有2次磁盘I/O,第一次磁盘I/O找到78个118,第二次磁盘I/O找到125和169这个节点,然后将这个节点读取到内存中处理.

    B+Tree
    B+Tree是BTree的改进版在节点与节点之间多了一个指针,只在树叶(树末梢)有value但这个value将不再是地址指针而是直接存放数据,上一个节点的key将遗留到下一个节点中.目的为了便于范围查询,如查询>98的记录,没有这个指针,需要重新从根节点找,没有这个遗留的节点,因为一次磁盘I/O不能读取太多数据
    78 118 (只有key)
    51 ->78 89 98 ->118 125 169 (都有key,data)

    存储引擎针对与表,一个数据库可以有两个不同存储引擎的表
    MyISAM (BTree)
    数据库文件下,data下的表文件夹中
    frm文件:存储的是建表结构,即查看表对象中的内容,create… 主外键
    MYD(MyISAM Data)文件:存储的是表中的数据
    MYI(MyISAM Index)文件:存储的是表中的key和数据地址指针(即BTree)
    当在数据库中查询时,如果发现有磁盘中有MYI文件(即添加了索引),会在索引中找到对应的节点,根据value的值(地址指针),去MYD文件中找到对应的地址

    InnoDB (B+Tree)
    数据库文件下,data下的表文件夹中
    frm文件:存储的是建表结构,即查看表对象中的内容,create… 主外键
    idb文件(index data):存储的是key和数据(B+Tree)

    非聚集索引,将索引与数据分开,即用MYI和MYD分开(MyISAM)
    聚集索引,将索引与数据结合在一起,即使用idb文件把索引与数据结合(InnoDB)

    mysql读取数据流程:cpu->RAM>磁盘
    页/4K(4*1024B(字节)) 一次磁盘I/O只能读取正数页,一次性不能读取太多数据,所以一个节点不能存放太多数据
    查看mysql文件页大小:show global status like ‘Innodb_page_size’ (官方默认16K)

    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组成。其中,为了与树形结构加以区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。

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

    原文链接:https://blog.csdn.net/yeyazhishang/article/details/82353846

    展开全文
  • 常见数据结构与算法整理总结(上)

    千次阅读 多人点赞 2016-09-24 20:18:31
    数据结构是以某种形式将数据组织在一起的...为了便于描述,文中涉及到的代码部分都是用Java语言编写的,其实Java本身对常见的几种数据结构,线性表、栈、队列等都提供了较好的实现,就是我们经常用到的Java集合框架。

    数据结构是以某种形式将数据组织在一起的集合,它不仅存储数据,还支持访问和处理数据的操作。算法是为求解一个问题需要遵循的、被清楚指定的简单指令的集合。下面是自己整理的常用数据结构与算法相关内容,如有错误,欢迎指出。

    为了便于描述,文中涉及到的代码部分都是用Java语言编写的,其实Java本身对常见的几种数据结构,线性表、栈、队列等都提供了较好的实现,就是我们经常用到的Java集合框架。

    一、线性表  
       1.数组实现  
       2.链表 二、栈与队列 三、树与二叉树  
       1.树  
       2.二叉树基本概念  
       3.二叉查找树  
       4.平衡二叉树  
       5.红黑树 四、图 五、总结


    一、线性表


    线性表是最常用且最简单的一种数据结构,它是n个数据元素的有限序列。

    实现线性表的方式一般有两种,一种是使用数组存储线性表的元素,即用一组连续的存储单元依次存储线性表的数据元素。另一种是使用链表存储线性表的元素,即用一组任意的存储单元存储线性表的数据元素(存储单元可以是连续的,也可以是不连续的)。

    数组实现

    数组是一种大小固定的数据结构,对线性表的所有操作都可以通过数组来实现。虽然数组一旦创建之后,它的大小就无法改变了,但是当数组不能再存储线性表中的新元素时,我们可以创建一个新的大的数组来替换当前数组。这样就可以使用数组实现动态的数据结构。

    • 代码1 创建一个更大的数组来替换当前数组


    int[] oldArray = new int[10];


    int[] newArray = new int[20];


    for (int i = 0; i < oldArray.length; i++) {

        newArray[i] = oldArray[i];

    }


    // 也可以使用System.arraycopy方法来实现数组间的复制        

    // System.arraycopy(oldArray, 0, newArray, 0, oldArray.length);


    oldArray = newArray;


    • 代码2 在数组位置index上添加元素e


    //oldArray 表示当前存储元素的数组

    //size 表示当前元素个数

    public void add(int index, int e) {


        if (index > size || index < 0) {

            System.out.println("位置不合法...");

        }


        //如果数组已经满了 就扩容

        if (size >= oldArray.length) {

            // 扩容函数可参考代码1

        }


        for (int i = size - 1; i >= index; i--) {

            oldArray[i + 1] = oldArray[i];

        }


        //将数组elementData从位置index的所有元素往后移一位

        // System.arraycopy(oldArray, index, oldArray, index + 1,size - index);


        oldArray[index] = e;


        size++;

    }


    上面简单写出了数组实现线性表的两个典型函数,具体我们可以参考Java里面的ArrayList集合类的源码。数组实现的线性表优点在于可以通过下标来访问或者修改元素,比较高效,主要缺点在于插入和删除的花费开销较大,比如当在第一个位置前插入一个元素,那么首先要把所有的元素往后移动一个位置。为了提高在任意位置添加或者删除元素的效率,可以采用链式结构来实现线性表。

    链表

    链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点组成,这些节点不必在内存中相连。每个节点由数据部分Data和链部分Next,Next指向下一个节点,这样当添加或者删除时,只需要改变相关节点的Next的指向,效率很高。



    单链表的结构


    下面主要用代码来展示链表的一些基本操作,需要注意的是,这里主要是以单链表为例,暂时不考虑双链表和循环链表。

    • 代码3 链表的节点

    class Node<E> {


        E item;    Node<E> next;    //构造函数    Node(E element) {

           this.item = element;

           this.next = null;

       }

    }


    • 代码4 定义好节点后,使用前一般是对头节点和尾节点进行初始化

    //头节点和尾节点都为空 链表为空

    Node<E> head = null;

    Node<E> tail = null;


    • 代码5 空链表创建一个新节点

    //创建一个新的节点 并让head指向此节点

    head = new Node("nodedata1");


    //让尾节点也指向此节点

    tail = head;


    • 代码6 链表追加一个节点

    //创建新节点 同时和最后一个节点连接起来

    tail.next = new Node("node1data2");


    //尾节点指向新的节点

    tail = tail.next;


    • 代码7 顺序遍历链表

    Node<String> current = head;

    while (current != null) {

        System.out.println(current.item);

        current = current.next;

    }


    • 代码8 倒序遍历链表

    static void printListRev(Node<String> head) {

    //倒序遍历链表主要用了递归的思想

        if (head != null) {

            printListRev(head.next);

            System.out.println(head.item);

        }

    }


    • 代码 单链表反转

    //单链表反转 主要是逐一改变两个节点间的链接关系来完成

    static Node<String> revList(Node<String> head) {


        if (head == null) {

            return null;

        }


        Node<String> nodeResult = null;


        Node<String> nodePre = null;

        Node<String> current = head;


        while (current != null) {


            Node<String> nodeNext = current.next;


            if (nodeNext == null) {

                nodeResult = current;

            }


            current.next = nodePre;

            nodePre = current;

            current = nodeNext;

        }


        return nodeResult;

    }


    上面的几段代码主要展示了链表的几个基本操作,还有很多像获取指定元素,移除元素等操作大家可以自己完成,写这些代码的时候一定要理清节点之间关系,这样才不容易出错。

    链表的实现还有其它的方式,常见的有循环单链表,双向链表,循环双向链表。 循环单链表 主要是链表的最后一个节点指向第一个节点,整体构成一个链环。 双向链表 主要是节点中包含两个指针部分,一个指向前驱元,一个指向后继元,JDK中LinkedList集合类的实现就是双向链表。 循环双向链表 是最后一个节点指向第一个节点。

    二、栈与队列


    栈和队列也是比较常见的数据结构,它们是比较特殊的线性表,因为对于栈来说,访问、插入和删除元素只能在栈顶进行,对于队列来说,元素只能从队列尾插入,从队列头访问和删除。

    栈是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫作栈顶,对栈的基本操作有push(进栈)和pop(出栈),前者相当于插入,后者相当于删除最后一个元素。栈有时又叫作LIFO(Last In First Out)表,即后进先出。


    栈的模型


    下面我们看一道经典题目,加深对栈的理解。


    关于栈的一道经典题目


    上图中的答案是C,其中的原理可以好好想一想。

    因为栈也是一个表,所以任何实现表的方法都能实现栈。我们打开JDK中的类Stack的源码,可以看到它就是继承类Vector的。当然,Stack是Java2前的容器类,现在我们可以使用LinkedList来进行栈的所有操作。

    队列

    队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。


    队列示意图


    我们可以使用链表来实现队列,下面代码简单展示了利用LinkedList来实现队列类。

    • 代码9 简单实现队列类

    public class MyQueue<E> {


        private LinkedList<E> list = new LinkedList<>();


        // 入队

        public void enqueue(E e) {

            list.addLast(e);

        }


        // 出队

        public E dequeue() {

            return list.removeFirst();

        }

    }


    普通的队列是一种先进先出的数据结构,而优先队列中,元素都被赋予优先级。当访问元素的时候,具有最高优先级的元素最先被删除。优先队列在生活中的应用还是比较多的,比如医院的急症室为病人赋予优先级,具有最高优先级的病人最先得到治疗。在Java集合框架中,类PriorityQueue就是优先队列的实现类,具体大家可以去阅读源码。

    三、树与二叉树


    树型结构是一类非常重要的非线性数据结构,其中以树和二叉树最为常用。在介绍二叉树之前,我们先简单了解一下树的相关内容。

    树 是由n(n>=1)个有限节点组成一个具有层次关系的集合。它具有以下特点:每个节点有零个或多个子节点;没有父节点的节点称为 根 节点;每一个非根节点有且只有一个父节点 ;除了根节点外,每个子节点可以分为多个不相交的子树。


    树的结构


    二叉树基本概念

    • 定义

    二叉树是每个节点最多有两棵子树的树结构。通常子树被称作“左子树”和“右子树”。二叉树常被用于实现二叉查找树和二叉堆。

    • 相关性质

    二叉树的每个结点至多只有2棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。

    二叉树的第i层至多有2^(i-1)个结点;深度为k的二叉树至多有2^k-1个结点。

    一棵深度为k,且有2^k-1个节点的二叉树称之为 满二叉树 

    深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称之为 完全二叉树 



    • 三种遍历方法

    在二叉树的一些应用中,常常要求在树中查找具有某种特征的节点,或者对树中全部节点进行某种处理,这就涉及到二叉树的遍历。二叉树主要是由3个基本单元组成,根节点、左子树和右子树。如果限定先左后右,那么根据这三个部分遍历的顺序不同,可以分为先序遍历、中序遍历和后续遍历三种。

    (1) 先序遍历 若二叉树为空,则空操作,否则先访问根节点,再先序遍历左子树,最后先序遍历右子树。 (2) 中序遍历 若二叉树为空,则空操作,否则先中序遍历左子树,再访问根节点,最后中序遍历右子树。(3) 后序遍历 若二叉树为空,则空操作,否则先后序遍历左子树访问根节点,再后序遍历右子树,最后访问根节点。


    给定二叉树写出三种遍历结果


    • 树和二叉树的区别

    (1) 二叉树每个节点最多有2个子节点,树则无限制。 (2) 二叉树中节点的子树分为左子树和右子树,即使某节点只有一棵子树,也要指明该子树是左子树还是右子树,即二叉树是有序的。 (3) 树决不能为空,它至少有一个节点,而一棵二叉树可以是空的。

    上面我们主要对二叉树的相关概念进行了介绍,下面我们将从二叉查找树开始,介绍二叉树的几种常见类型,同时将之前的理论部分用代码实现出来。

    二叉查找树

    • 定义

    二叉查找树就是二叉排序树,也叫二叉搜索树。二叉查找树或者是一棵空树,或者是具有下列性质的二叉树: (1) 若左子树不空,则左子树上所有结点的值均小于它的根结点的值;(2) 若右子树不空,则右子树上所有结点的值均大于它的根结点的值;(3) 左、右子树也分别为二叉排序树;(4) 没有键值相等的结点。


    典型的二叉查找树的构建过程


    • 性能分析

    对于二叉查找树来说,当给定值相同但顺序不同时,所构建的二叉查找树形态是不同的,下面看一个例子。


    不同形态平衡二叉树的ASL不同


    可以看到,含有n个节点的二叉查找树的平均查找长度和树的形态有关。最坏情况下,当先后插入的关键字有序时,构成的二叉查找树蜕变为单支树,树的深度为n,其平均查找长度(n+1)/2(和顺序查找相同),最好的情况是二叉查找树的形态和折半查找的判定树相同,其平均查找长度和log2(n)成正比。平均情况下,二叉查找树的平均查找长度和logn是等数量级的,所以为了获得更好的性能,通常在二叉查找树的构建过程需要进行“平衡化处理”,之后我们将介绍平衡二叉树和红黑树,这些均可以使查找树的高度为O(log(n))。

    • 代码10 二叉树的节点

    class TreeNode<E> {


        E element;

        TreeNode<E> left;

        TreeNode<E> right;    public TreeNode(E e) {

            element = e;

        }

    }


    二叉查找树的三种遍历都可以直接用递归的方法来实现:

    • 代码12 先序遍历

    protected void preorder(TreeNode<E> root) {    if (root == null)        return;


        System.out.println(root.element + " ");


        preorder(root.left);


        preorder(root.right);

    }


    • 代码13 中序遍历

    protected void inorder(TreeNode<E> root) {    if (root == null)        return;


        inorder(root.left);


        System.out.println(root.element + " ");


        inorder(root.right);

    }


    • 代码14 后序遍历

    protected void postorder(TreeNode<E> root) {


        if (root == null)

            return;


        postorder(root.left);


        postorder(root.right);


        System.out.println(root.element + " ");

    }


    • 代码15 二叉查找树的简单实现

    /**

     * @author JackalTsc

     */public class MyBinSearchTree<E extends Comparable<E>> {


        // 根

        private TreeNode<E> root;    

        

        // 默认构造函数

        public MyBinSearchTree() {

        }  


         // 二叉查找树的搜索

        public boolean search(E e) {      


             TreeNode<E> current = root;      


             while (current != null) {          


                 if (e.compareTo(current.element) < 0) {

                    current = current.left;

                } else if (e.compareTo(current.element) > 0) {

                    current = current.right;

                } else {                return true;

                }

            }      


             return false;

        }    

    // 二叉查找树的插入

        public boolean insert(E e) {      


             // 如果之前是空二叉树 插入的元素就作为根节点

            if (root == null) {

                root = createNewNode(e);

            } else {          

                 // 否则就从根节点开始遍历 直到找到合适的父节点

                TreeNode<E> parent = null;          

                TreeNode<E> current = root;          

                while (current != null) {              

                     if (e.compareTo(current.element) < 0) {

                        parent = current;

                        current = current.left;

                    } else if (e.compareTo(current.element) > 0) {

                        parent = current;

                        current = current.right;

                    } else {                    return false;

                    }

                }          

                 // 插入

                if (e.compareTo(parent.element) < 0) {

                    parent.left = createNewNode(e);

                } else {

                    parent.right = createNewNode(e);

                }

            }        return true;

        }    


        // 创建新的节点

        protected TreeNode<E> createNewNode(E e) {        return new TreeNode(e);

        }


    }// 二叉树的节点

    class TreeNode<E extends Comparable<E>> {


        E element;    TreeNode<E> left;    TreeNode<E> right;


        public TreeNode(E e) {

            element = e;

        }

    }


    上面的代码15主要展示了一个自己实现的简单的二叉查找树,其中包括了几个常见的操作,当然更多的操作还是需要大家自己去完成。因为在二叉查找树中删除节点的操作比较复杂,所以下面我详细介绍一下这里。

    • 二叉查找树中删除节点分析

    要在二叉查找树中删除一个元素,首先需要定位包含该元素的节点,以及它的父节点。假设current指向二叉查找树中包含该元素的节点,而parent指向current节点的父节点,current节点可能是parent节点的左孩子,也可能是右孩子。这里需要考虑两种情况:

    1.ent节点没有左孩子,那么只需要将patent节点和current节点的右孩子相连。


    2.rrent节点有一个左孩子,假设rightMost指向包含current节点的左子树中最大元素的节点,而parentOfRightMost指向rightMost节点的父节点。那么先使用rightMost节点中的元素值替换current节点中的元素值,将parentOfRightMost节点和rightMost节点的左孩子相连,然后删除rightMost节点。

    // 二叉搜索树删除节点

        public boolean delete(E e) {


            TreeNode<E> parent = null;

            TreeNode<E> current = root;


            // 找到要删除的节点的位置

            while (current != null) {

                if (e.compareTo(current.element) < 0) {

                    parent = current;

                    current = current.left;

                } else if (e.compareTo(current.element) > 0) {

                    parent = current;

                    current = current.right;

                } else {

                    break;

                }

            }


            // 没找到要删除的节点

            if (current == null) {

                return false;

            }


            // 考虑第一种情况

            if (current.left == null) {

                if (parent == null) {

                    root = current.right;

                } else {

                    if (e.compareTo(parent.element) < 0) {

                        parent.left = current.right;

                    } else {

                        parent.right = current.right;

                    }

                }

            } else { // 考虑第二种情况

                TreeNode<E> parentOfRightMost = current;

                TreeNode<E> rightMost = current.left;

                // 找到左子树中最大的元素节点

                while (rightMost.right != null) {

                    parentOfRightMost = rightMost;

                    rightMost = rightMost.right;

                }


                // 替换

                current.element = rightMost.element;


                // parentOfRightMost和rightMost左孩子相连

                if (parentOfRightMost.right == rightMost) {

                    parentOfRightMost.right = rightMost.left;

                } else {

                    parentOfRightMost.left = rightMost.left;

                }

            }


            return true;

        }




    平衡二叉树

    平衡二叉树又称AVL树,它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。


    平衡二叉树


    AVL树是最先发明的自平衡二叉查找树算法。在AVL中任何节点的两个儿子子树的高度最大差别为1,所以它也被称为高度平衡树,n个结点的AVL树最大深度约1.44log2n。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

    红黑树

    红黑树是平衡二叉树的一种,它保证在最坏情况下基本动态集合操作的事件复杂度为O(log n)。红黑树和平衡二叉树区别如下:(1) 红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下,保证每次插入最多只需要三次旋转就能达到平衡,实现起来也更为简单。(2) 平衡二叉树追求绝对平衡,条件比较苛刻,实现起来比较麻烦,每次插入新节点之后需要旋转的次数不能预知。

    四、图


    图是一种较线性表和树更为复杂的数据结构,在线性表中,数据元素之间仅有线性关系,在树形结构中,数据元素之间有着明显的层次关系,而在图形结构中,节点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。图的应用相当广泛,特别是近年来的迅速发展,已经渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。

    五、总结


    到这里,关于常见的数据结构的整理就结束了,断断续续大概花了两天时间写完,在总结的过程中,通过查阅相关资料,结合书本内容,收获还是很大的,在下一篇博客中将会介绍常用数据结构与算法整理总结(下)之算法篇,欢迎大家关注。

    转载自:简书

    文章地址:http://www.jianshu.com/p/230e6fde9c75

    作者:尘语凡心


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

    万次阅读 多人点赞 2018-09-05 18:23:28
    数据结构分类 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。 常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示: 每一种数据结构都...

    本文目录:

    数据结构分类

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

    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组成。其中,为了与树形结构加以区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。

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

    展开全文
  • 常见数据结构优缺点

    千次阅读 2018-12-02 22:23:53
    通用数据结构: 1.数组 分类: 无序数组,有序数组 特点: 一般针对数据量较小且数据可预知的情况,创建时指定大小,不利于扩展;在内存中预留一块连续的区域,内存空置率高利用率较低;无序数组插入较快,...

    通用数据结构:
    加粗样式

    1.数组
    分类:
    无序数组,有序数组
    特点:
    一般针对数据量较小且数据可预知的情况,创建时指定大小,不利于扩展;在内存中预留一块连续的区域,内存空置率高利用率较低;无序数组插入较快,有序数组查询较快,利用下标访问,随机访问性强。
    优点:
    查询速度快
    随机访问性强,遍历数组方便
    缺点:
    内存固定,扩展性差
    数组要预留空间,内存利用率低
    插入删除速度慢
    只能存储一种类型的数据

    2.链表的特点:
    分类:
    单链表、双向链表以及循环链表
    特点:
    创建时不指定大小,内存大小随数据量变化;内存的存储位置可以在任何地方,不要求连续,可扩展性强;每一个数据保存邻近的数据的地址,遍历需要从根节点开始,没有随机访问性,查找效率低;增加删除比较随意,效率高。
    优点:
    插入删除速度快
    内存利用率高,不浪费内存
    存储的数据类型相对灵活
    大小不固定,扩展性强
    缺点:
    查询速度慢
    只能从根节点开始查找,不具备随机访问性

    3.二叉查找树
    分类:
    平衡二叉树,非平衡二叉树
    特点:
    结合数组和链表的优点,适合数据量较大的情况,具有一定顺序,左子节点值较小,右子节点值较大;查找时从根节点开始,不具备随机访问性,但相比较而言查询速度快,增删速度快,对于遍历一定范围内的数据比较方便。非平衡二叉树简单,但对于部分数据查询增删效率较低,甚至会退化成链表。
    优点:
    查询增删速度快
    存储的数据类型相对灵活
    不指定内存大小,内存利用率较高
    缺点:
    只能从根节点开始查询,不具备随机访问性
    对于部分数据,给平衡二叉树的效率会向链表结构靠拢

    4.平衡树
    实现:
    AVL树、红黑树、2-3树等
    特点:
    改善了二叉搜索树的缺点,实现起来稍微复杂,平衡树结构会产生了额外消费,但查询及增删效率均比较高
    优点:
    查询速度较快
    增删速度较快
    存储的数据类型相对灵活
    不指定内存大小,内存利用率较高
    缺点:
    实现起来复杂
    会产生一定的额外消费

    5.哈希表
    实现方式:
    开放地址法、链地址法
    优点:
    插入删除速度最快
    缺点:
    基于数组,创建后扩展性差
    弱序,查找速度慢
    基于哈希映射,会有冲突产生,并形成数据聚集
    需预留内存,内存利用率不高

    通用数据存储结构的速度
    在这里插入图片描述

    参考资料 《java数据机构和算法》

    展开全文
  • 常见数据结构有哪些?

    千次阅读 2020-06-09 19:01:16
    1.一共八大数据结构分类 1.数组 2.队列 3.链表 i.单链表 ii.双向链表 iii.循环链表 4.树 5.散列表 6.堆 7.栈 8.图 辅助理解 1、详细说下几个数据结构 数组 简单 栈 先进后出 队列 先进先出 链表 ...
  • 最近在学习数据结构,有必要对自己这两天的学习做一个总结,今天就来总结下,数据结构的逻辑结构 按照分类标准的不同,我们把数据结构分为逻辑机构和存储结构,今天主要讲解逻辑结构 逻辑结构:是指数据对象中的...
  • 上次在面试时被面试官问到学了哪些数据结构,那时简单答了栈、队列/(ㄒoㄒ)/~~其它就都想不起来了,今天有空整理了一下几种常见数据结构,原来我们学过的数据结构有这么多~ 首先,先来回顾下C语言中常见的基本数据...
  • 数据结构在实际应用中非常常见,现在各种算法基本都牵涉到数据结构,因此,掌握数据结构算是软件工程师的必备技能。 一、什么是数据结构 数据结构,直白地理解,就是研究数据的存储方式。 我们知道,数据存储只有一...
  • 数据结构--链表概念及常见链表结构

    千次阅读 多人点赞 2020-12-17 00:09:25
    链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 链表的结构由以下8种: 1、不带头单向循环结构 2、不带头单向非循环结构 3、不带头双向循环结构 4、不...
  • 数据类型数据结构的区别

    千次阅读 2020-07-27 18:01:50
    数据结构是指按一定的逻辑结构组成的一批数据,使用某种存储结构将这批数据存储于计算机中,并在这些数据上定义了一个运算集合。 1. 逻辑结构 常见的数据的逻辑结构:线性结构、树形结构和图形结构。 2. 存储结构 ...
  • 八大数据结构常见面试题

    千次阅读 2020-12-01 21:39:16
    几乎所有的问题都需要面试者对数据结构有深刻的理解。无论你是初入职场的新兵(刚从大学或者编程培训班毕业),还是拥有几十年经验的职场老鸟。 即便是对于一些非常基础的工作来说,学习数据结构也是必须的。那么,...
  • 数据结构:八种数据结构大全!

    千次阅读 多人点赞 2021-07-29 12:36:10
    数据结构 1.1 数据结构概述 数据结构是计算机存储、组织数据的方式;通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构的优良将直接影响着我们程序的性能;常用的数据结构有:数组(Array)...
  • 图解!24张图彻底弄懂九大常见数据结构

    万次阅读 多人点赞 2020-05-24 22:23:36
    数据结构想必大家都不会陌生,对于一个成熟的程序员而言,熟悉和掌握数据结构和算法也是基本功之一。数据结构本身其实不过是数据按照特点关系进行存储或者组织的集合,特殊的结构在不同的应用场景中往往会带来不...
  • 常见抽象数据类型

    千次阅读 2019-03-27 15:48:25
    结构:栈顶、栈底 特点:后进先出。从栈顶压入栈,从栈顶压出栈 二、队列 1、队列 结构:队头、队尾 特点:先进先出。从队尾入队列,从队头出队列 2、双端队列 结构:队头、队尾 特点:队头队尾均可入队/出队 3、...
  • PHP常见的几种数据结构

    千次阅读 2019-09-25 14:12:38
    PHP常见的几种数据结构 1 数组 数组(Array)是一种线性表的数据结构,它用一段连续的内存空间,来存储具有相同类型的值。但是由于在PHP的底层定义中,数组是通过散列表实现的,所以这段定义并不适用。PHP的数组可以...
  • 数据结构结构类型

    千次阅读 2018-08-30 09:12:46
    偶然看到了专门用来处理关系结构的图数据库,根据其介绍了解到其原理是数据结构的图结构。而令人尴尬的是,说道图结构的特点,算法,我竟然完全没有了一点印象。大学学习的这门课程已经还给了老师。书到用时方恨少啊...
  • 前言:阅读 redis设计与实现 一书的记录。未完待续。。。redis我们都知道有5种数据类型,分别是...每种数据类型都有着2种以上的数据结构实现,在不同状态下会进行数据结构的转换。现在来看看这6种数据结构是什么吧...
  • 常见数据结构及其特征

    千次阅读 2017-03-23 15:39:21
    常见数据结构有stack、heap、list、linkedlist、doubly-linked-list、queue、array(vector)等
  • java中常见的几种数据结构

    千次阅读 2019-05-20 20:50:57
    数据结构相对于算法来说简直是屈指可数,常见数据结构也就那几种,很容易掌握,但算法可以有成千上万,要想全部掌握基本上很难,我们常说的数据结构和算法是指数据结构和算法的结合,如果对算法感兴趣的也可以关注...
  • Java常见的8种数据结构

    万次阅读 多人点赞 2020-09-18 16:41:54
    这 8 种数据结构有什么区别呢? ①、数组 优点: 按照索引查询元素的速度很快; 按照索引遍历数组也很方便。 缺点: 数组的大小在创建后就确定了,无法扩容; 数组只能存储一种类型的数据; ...
  • 常见数据结构应用场景

    千次阅读 2018-10-06 19:52:58
    通用数据结构 可以简单的按照速度将通用数据结构划分为:数组和链表(最慢),树(较快),哈希表(最快)。增、删、改、查是四大常见操作,不过其实可以浓缩为两个操作:增和查。删除操作和和修改操作都是建立在...
  • 我对八种常见数据结构的理解

    万次阅读 2021-11-22 15:55:35
    还有朋友可能不太理解什么是数据结构,就像喝水,你总是喝到最上面的一层,我称之为“水的栈”这便是一种结构 顾名思义数据结构,便是数据的结构,数据结构并不是什么很高深的东西 起初数据结构并没有一门专门的...
  • 数据结构算法常见面试考题

    万次阅读 多人点赞 2018-11-08 09:29:44
    数据结构上几种树集中的讨论一下: 1.AVLtree 定义:最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)...
  • 面试中常见数据结构

    万次阅读 2018-07-26 10:08:20
    上次在面试时被面试官问到学了哪些数据结构,那时简单答了栈、队列/(ㄒoㄒ)/~~其它就都想不起来了,今天有空整理了一下几种常见数据结构,原来我们学过的数据结构有这么多~   首先,先来回顾下C语言中常见的...
  • Java基本类型数据结构

    千次阅读 2018-07-20 13:52:09
    基本类型 精度丢失和溢出: 精度丢失一般发生在浮点型存储数值或类型强制转换的时候。我们知道计算机存储数值实际存储的是二进制,举个粟子 double r1 = 1 - 0.99; double r2 = 2 - 0.99 result的值是0....
  • 数据结构与算法常见笔试题

    万次阅读 多人点赞 2017-09-10 11:03:57
    1.数据结构与算法常见笔试题   第一章 数据结构与算法 一.算法的基本概念 计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。 1.算法的基本特征:可行性,确定性,有穷性,拥有足够的情报。 2....
  • Redis 五种常见数据结构:zset

    千次阅读 2019-02-19 17:20:22
    Redis 五种常见数据结构:zset
  • 四种基本数据结构

    千次阅读 2019-03-18 09:29:46
    集合结构:该结构数据元素间的关系是“属于同一个集合”; 线性结构:该结构数据元素之间存在一对一的关系; 树形结构:该结构数据元素之间存在一对多的关系; 图形结构:该结构数据元素之间存在多对多的...
  • 面试中常见数据结构与算法

    万次阅读 多人点赞 2018-04-09 15:53:58
    给定一数组,其大小为8个元素,数组内的数据无序。 6 3 5 7 0 4 1 2 冒泡排序:两两比较,将两者较少的升上去,第一次比较空间为0-(N-1)直到最后一轮比较空间为0-1 public class bubbleSort { public static ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 594,517
精华内容 237,806
关键字:

常见数据结构类型

数据结构 订阅