精华内容
下载资源
问答
  • 常见的数据结构的基本形式
    千次阅读
    2020-12-03 18:18:16

    数据结构的基本操作

    对于任何数据结构,其基本操作无非遍历 + 访问,再具体一点就是:增删查改。

    数据结构种类很多,但它们存在的目的都是在不同的应用场景,尽可能高效地增删查改。话说这不就是数据结构的使命么?

    如何遍历 + 访问?我们仍然从最高层来看,各种数据结构的遍历 + 访问无非两种形式:线性的和非线性的。

    线性就是 for/while 迭代为代表,非线性就是递归为代表。再具体一步,无非以下几种框架:

    数组遍历框架,典型的线性迭代结构:

    void traverse(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            // 迭代访问 arr[i]
        }
    }

    链表遍历框架,兼具迭代和递归结构:

    /* 基本的单链表节点 */
    class ListNode {
        int val;
        ListNode next;
    }
    
    void traverse(ListNode head) {
        for (ListNode p = head; p != null; p = p.next) {
            // 迭代访问 p.val
        }
    }
    
    void traverse(ListNode head) {
        // 递归访问 head.val
        traverse(head.next);
    }

    二叉树遍历框架,典型的非线性递归遍历结构:

    /* 基本的二叉树节点 */
    class TreeNode {
        int val;
        TreeNode left, right;
    }
    
    void traverse(TreeNode root) {
        traverse(root.left);
        traverse(root.right);
    }

    你看二叉树的递归遍历方式和链表的递归遍历方式,相似不?再看看二叉树结构和单链表结构,相似不?如果再多几条叉,N 叉树你会不会遍历?

    二叉树框架可以扩展为 N 叉树的遍历框架:

    /* 基本的 N 叉树节点 */
    class TreeNode {
        int val;
        TreeNode[] children;
    }
    
    void traverse(TreeNode root) {
        for (TreeNode child : root.children)
            traverse(child);
    }

    N 叉树的遍历又可以扩展为图的遍历,因为图就是好几 N 叉棵树的结合体。你说图是可能出现环的?这个很好办,用个布尔数组 visited 做标记就行了,这里就不写代码了。

    所谓框架,就是套路。不管增删查改,这些代码都是永远无法脱离的结构,你可以把这个结构作为大纲,根据具体问题在框架上添加代码就行了。

    例题

    LeetCode 124 题,难度 Hard,让你求二叉树中最大路径和,主要代码如下:

    int ans = INT_MIN;
    int oneSideMax(TreeNode* root) {
        if (root == nullptr) return 0;
        int left = max(0, oneSideMax(root->left));
        int right = max(0, oneSideMax(root->right));
        ans = max(ans, left + right + root->val);
        return max(left, right) + root->val;
    }

    这就是个后序遍历

    LeetCode 105 题,难度 Medium,让你根据前序遍历和中序遍历的结果还原一棵二叉树,很经典的问题吧,主要代码如下:

    TreeNode buildTree(int[] preorder, int preStart, int preEnd, 
        int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inMap) {
    
        if(preStart > preEnd || inStart > inEnd) return null;
    
        TreeNode root = new TreeNode(preorder[preStart]);
        int inRoot = inMap.get(root.val);
        int numsLeft = inRoot - inStart;
    
        root.left = buildTree(preorder, preStart + 1, preStart + numsLeft, 
                              inorder, inStart, inRoot - 1, inMap);
        root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd, 
                              inorder, inRoot + 1, inEnd, inMap);
        return root;
    }

    不要看这个函数的参数很多,只是为了控制数组索引而已,本质上该算法也就是一个前序遍历

    LeetCode 99 题,难度 Hard,恢复一棵 BST,主要代码如下:

    void traverse(TreeNode* node) {
        if (!node) return;
        traverse(node->left);
        if (node->val < prev->val) {
            s = (s == NULL) ? prev : s;
            t = node;
        }
        prev = node;
        traverse(node->right);
    }

    这就是个中序遍历。

    对于一个理解二叉树的人来说,刷一道二叉树的题目花不了多长时间。那么如果你对刷题无从下手或者有畏惧心理,不妨从二叉树下手,前 10 道也许有点难受;结合框架再做 20 道,也许你就有点自己的理解了;刷完整个专题,再去做什么回溯动规分治专题,你就会发现只要涉及递归的问题,都是树的问题

    动态规划凑零钱问题,暴力解法就是遍历一棵 N 叉树:

    def coinChange(coins: List[int], amount: int):
    
        def dp(n):
            if n == 0: return 0
            if n < 0: return -1
    
            res = float('INF')
            for coin in coins:
                subproblem = dp(n - coin)
                # 子问题无解,跳过
                if subproblem == -1: continue
                res = min(res, 1 + subproblem)
            return res if res != float('INF') else -1
    
        return dp(amount)

    这么多代码看不懂咋办?直接提取出框架,就能看出核心思路了:

    # 不过是一个 N 叉树的遍历问题而已
    def dp(n):
        for coin in coins:
            dp(n - coin)

    其实很多动态规划问题就是在遍历一棵树,你如果对树的遍历操作烂熟于心,起码知道怎么把思路转化成代码,也知道如何提取别人解法的核心思路。

    回溯算法就是个 N 叉树的前后序遍历问题,没有例外。

    比如 N 皇后问题吧,主要代码如下:

    void backtrack(int[] nums, LinkedList<Integer> track) {
        if (track.size() == nums.length) {
            res.add(new LinkedList(track));
            return;
        }
    
        for (int i = 0; i < nums.length; i++) {
            if (track.contains(nums[i]))
                continue;
            track.add(nums[i]);
            // 进入下一层决策树
            backtrack(nums, track);
            track.removeLast();
        }
    
    /* 提取出 N 叉树遍历框架 */
    void backtrack(int[] nums, LinkedList<Integer> track) {
        for (int i = 0; i < nums.length; i++) {
            backtrack(nums, track);
    }

    N 叉树的遍历框架,找出来了。

    数据结构的基本存储方式就是链式和顺序两种,基本操作就是增删查改,遍历方式无非迭代和递归。

    更多相关内容
  • 一、问题描述 运用二叉链表实现二叉树的基本操作,包括:创建二叉树的存储结构、复制...1、构造二叉树的二叉链表数据结构。 2、实现二叉树的创建、复制、计算二叉树的深度、先根序序列、中根序序列、后根序序列等操作。
  • (1) 用户能够向文本格式化系统中输入文本格式化的基本信息,包括页长,页宽,左空白,头长,脚长和起始页号,并保存格式化后的文本; (2) 在单词之间实现多余空格的压缩,多个空格合并为一个空格; (3) 实现一个完整...
  • 数据结构基本操作 1.数据结构与算法常见概念: 2.数据结构: 2.1线性结构: 基本概念 数组 字符串 队列 栈 链表 2.2树形结构 基本概念 二叉树的递归遍历 二叉树的非递归遍历 ...


    总结《大话数据结构》和《C++Primer》,文后附《大话数据结构》和《C++Primer》第五版下载链接,本文相关代码均由C++编写。

     

    1.数据结构与算法常见概念:

    数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。
    数据元素:是组成数据的,有一定意义的基本单位,在计算机中通常作为整体处理,也被称为记录。
    数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。
    数据结构的逻辑结构:数据对象中数据元素之间的相互关系,分为线性结构、树形结构、图形结构以及集合结构。
    数据结构的物理结构:数据的逻辑结构在计算机中的存储形式,分为顺序存储和链式存储(不连续存储)。

    算法:解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。
    算法五个基本特性:输入、输出、有穷性、确定性和可行性。
    算法时间复杂度O(n):常数阶、线性阶、平方阶、对数阶、立方阶、nlogn阶、指数阶。
    耗时排序:O(1)<O(logn)<O(n)<O(nlgn)<O(x2x^{2}x2)<O(x3x^{3}x3)<O(2n2^{n}2n)<O(n!)<O(nnn^{n}nn)

    2.数据结构:

    2.1线性结构:

    基本概念

    线性结构:数据元素之间是一对一的关系。
    在这里插入图片描述
    线性表:零个或多个数据元素的有限序列。
    区分数组长度与线性表的长度
            数组长度是指存放线性表的存储空间的长度,存储分配后这个值是不变的。
            线性表的长度是线性表中数据元素的个数,随着线性表的插入与删除,这个值是在变换的。
    在这里插入图片描述线性表的顺序存储:用一段连续的存储单元依次存储线性表的数据元素。(通常使用一维数组实现顺序存储结构)
    线性表的链式存储:除了存储本身的信息之外,还需存储一个指示后继的信息。
    顺序存储的插入步骤:
            a.线性表长度大于等于数组长度,抛出异常
            b.插入位置不合适,抛出异常(判断插入位置与0和最大值的大小)
            c.从最后一个元素开始向前变量,将它们都向后移动一位
            d.将要插入的元素填入指定位置
            e.表长加一
    顺序存储的删除步骤:
            a.线性表是否为空
            b.删除位置不合适,抛出异常(判断插入位置与0和最大值的大小)
            c.取出删除元素
            d.从删除元素的位置遍历到最后一个元素位置,将它们前移一位
            e.表长减一
    链式存储的插入与删除在链表中介绍
    顺序存储和链式存储使用场景:如果频繁使用查找,很少进行插入和删除,易采用顺序存储。如果需要频繁插入和删除,易采用链式存储。

    数组

    数组及基本操作

    字符串

    字符串及基本操作

    队列

    队列及基本操作

    栈及基本操作

    链表

    链表及基本操作

    2.2树形结构

    基本概念

    树形结构:数据元素之间存在一对多的层次关系
    在这里插入图片描述
    :结点拥有的子树数
    叶结点/终端结点:度为0的结点
    树的度:树内各结点的度的最大值
    在这里插入图片描述
    结点间关系图
    在这里插入图片描述
    树的深度/高度:树中结点的最大层次
    在这里插入图片描述
    二叉树:是N(N>=0)个结点的有限集合,该集合或为空集(空二叉树),或者由一个根结点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
    在这里插入图片描述
    满二叉树:所有分支结点都存在左子树和右子树,并且所有非叶子节点都在同一层上
    在这里插入图片描述
    完全二叉树:对一棵具有n个结点的二叉树按层序编号,如果编号i(1<= i <= n)的结点与同样深度的满二叉树中的编号i 的结点在二叉树的位置完全相同,则这棵二叉树称为完全二叉树
    在这里插入图片描述
    二叉树的特点

    1. 每个结点最多只有两颗子树
    2. 左右子树是有顺序的
    3. 即使某结点只有一颗子树,也要区分是右子树还是左子树

    二叉树的性质

    1. 在二叉树的第i层上至多有2i−12^{i-1}2i−1个结点(i>=1)
    2. 深度为k的二叉树至多有2k2^{k}2k-1个结点(k>=1)
    3. 对任何一棵二叉树T,如果其终端结点数为n0n_{0}n0​,此二叉树至多有2k2^{k}2k-1个结点
    4. 具有n个结点的完全二叉树的深度为[log2log_{2}log2​n]+1([x]表示不大于x的最大整数)
    5. n个结点的完全二叉树按层序编号(参考上图),对任意一个结点i有:
      a. 如果i=1,则i是二叉树的根,如果i>1,其双亲是[i/2]
      b. 如果2i>n,则结点i无左孩子
      c. 如果2i+1>n,则结点i无右孩子(否则其右孩子为2i+1)

    二叉树的递归遍历

    二叉树的遍历(递归)

    二叉树的非递归遍历

    未完待续……

    2.3图形结构

    图形结构:数据元素的多对多的关系
    在这里插入图片描述

    2.4集合结构

    集合结构:数据元素除了同属于一个集合外,它们之间没有其他关系。
    在这里插入图片描述

    3.资源链接

    《大话数据结构》+《C++Primer》PDF百度云盘链接
    提取码:6a7b

    展开全文
  • 数据结构基本概念.doc

    2022-07-11 16:38:42
    数据结构基本概念 数据:计算机程序所加工处理的描述客观事物的符号表示。 数据元素:数据的基本单位,是数据集合中的一个个体,在计算机程序中通常作为一个整 体进行考虑和处理。数据元素可由一个或若干个数据项所...
  • 例如: (a1,a2,…an) 2 线性结构和非线性结构 数据结构:线性结构和非线性结构 线性表: 线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限...
  • 数据结构基本概念(1)全文共3页,当前为第1页。数据结构基本概念(1)全文共3页,当前为第1页。数据结构基本概念 数据结构基本概念(1)全文共3页,当前为第1页。 数据结构基本概念(1)全文共3页,当前为第1页。 数据:...
  • 本文实例讲述了Python基本数据结构之字典类型dict用法。分享给大家供大家参考,具体如下: 词典类型 dict 字典由键(key)和对应值(value)成对组成。字典也被称作关联数组或哈希表。 dict 赋值 dict 整体放在花括号{}...
  • 3. 基本数据结构1

    2022-08-04 13:01:05
    如第一章所述,在面向对象语言Python中,实现栈这种抽象数据类型的选择是新建类。栈的操作以方法的形式实现。此外,为实现作为元素容的栈,充分用Python本身提
  • 格式 数据结构基本英语词汇 数据抽象?dataabstraction 数据元素?dataelement 数据对象?dataobject 数据项?dataitem 数据类型?datatype 抽象数据类型?abstractdatatype 逻辑结构?logicalstructure 物理结构?...
  • tri-mesh三角形网格数据结构,包括基本操作。 使用它来创建,编辑和计算3D模型。 示例网格工具功能m三网格包含基本操作的三角形网格数据结构。 使用它来创建,编辑和计算3D模型。 示例网格工具功能主要结构Mesh实现...
  • Redis的5种基本数据结构

    千次阅读 2021-10-30 09:45:31
    String数据类型是Redis中最基本数据类型,是key-value的对应形式,redis中的string可以包含任何类型的数据,数字,字符串,图片等等 使用:get 、 set 、 del 、 incr、 decr 等 适用场景:缓存: 经典使用场景,把...

    一、String类型
    String数据类型是Redis中最基本的数据类型,是key-value的对应形式,redis中的string可以包含任何类型的数据,数字,字符串,图片等等

    在这里插入图片描述
    使用:get 、 set 、 del 、 incr、 decr 等
    适用场景:缓存: 经典使用场景,把常用信息,字符串,图片或者视频等信息放到redis中,redis作为缓存层,mysql做持久化层,降低mysql的读写压力。
    二、Hash类型
    本身是一个HashMap,一种键值对的形式,field对应value
    在这里插入图片描述
    使用:所有hash的命令都是 h 开头的 hget 、hset 、 hdel 等
    使用场景:做缓存: 能直观,相比string更节省空间,的维护缓存信息,如用户信息,视频信息等。
    三、链表(List)
    Redis使用双端队列实现了链表,左右都可以插入删除

    使用场景:例如微博的时间轴,有人发布微博,用lpush加入时间轴,展示新的列表信息。
    四、Set 集合
    集合类型也是用来保存多个字符串的元素,但和列表不同的是集合中 1. 不允许有重复的元素,2.集合中的元素是无序的,不能通过索引下标获取元素,3.支持集合间的操作,可以取多个集合取交集、并集、差集。
    在这里插入图片描述
    使用场景:
    1.给用户添加标签,或者用户给消息添加标签,这样有同一标签或者类似标签的可以给推荐关注的事或者关注的人。
    2.点赞,或点踩,收藏等,可以放到set中实现
    五、zset有序集合(底层的实现是跳跃,跳跃表是有序单链表的一种改进,其查询、插入、删除也是O(logN)的时间复杂度。)
    有序集合和集合类似,保留了集合不能有重复成员的特性,区别是,有序集合中的元素是可以排序的,它给每个元素设置一个分数,作为排序的依据。
    在这里插入图片描述
    使用场景:排行榜,例如微博各种分类的排行榜,小说等按照不同类型(浏览量,收藏数量等)的排行榜.

    展开全文
  • 九大常见数据结构

    千次阅读 多人点赞 2020-10-16 14:44:54
    数据结构想必大家都不会陌生,...数据结构种类繁多,本文将通过图解的方式对常用数据结构进行理论上的介绍和讲解,以方便大家掌握常用数据结构基本知识。 1、数组 数组可以说是最基本常见数据结构。数组

    数据结构想必大家都不会陌生,对于一个成熟的程序员而言,熟悉和掌握数据结构和算法也是基本功之一。数据结构本身其实不过是数据按照特点关系进行存储或者组织的集合,特殊的结构在不同的应用场景中往往会带来不一样的处理效率。

    常用的数据结构可根据数据访问的特点分为线性结构和非线性结构。线性结构包括常见的链表、栈、队列等,非线性结构包括树、图等。数据结构种类繁多,本文将通过图解的方式对常用的数据结构进行理论上的介绍和讲解,以方便大家掌握常用数据结构的基本知识。

    1、数组

    数组可以说是最基本最常见的数据结构。数组一般用来存储相同类型的数据,可通过数组名和下标进行数据的访问和更新。数组中元素的存储是按照先后顺序进行的,同时在内存中也是按照这个顺序进行连续存放。数组相邻元素之间的内存地址的间隔一般就是数组数据类型的大小。

     2、链表

    链表相较于数组,除了数据域,还增加了指针域用于构建链式的存储数据。链表中每一个节点都包含此节点的数据和指向下一节点地址的指针。由于是通过指针进行下一个数据元素的查找和访问,使得链表的自由度更高。

    这表现在对节点进行增加和删除时,只需要对上一节点的指针地址进行修改,而无需变动其它的节点。不过事物皆有两极,指针带来高自由度的同时,自然会牺牲数据查找的效率和多余空间的使用。

    一般常见的是有头有尾的单链表,对指针域进行反向链接,还可以形成双向链表或者循环链表。

    链表和数组对比

    链表和数组在实际的使用过程中需要根据自身的优劣势进行选择。链表和数组的异同点也是面试中高频的考察点之一。这里对单链表和数组的区别进行了对比和总结。

     3、跳表

    从上面的对比中可以看出,链表虽然通过增加指针域提升了自由度,但是却导致数据的查询效率恶化。特别是当链表长度很长的时候,对数据的查询还得从头依次查询,这样的效率会更低。跳表的产生就是为了解决链表过长的问题,通过增加链表的多级索引来加快原始链表的查询效率。这样的方式可以让查询的时间复杂度从O(n)提升至O(logn)。

    跳表通过增加的多级索引能够实现高效的动态插入和删除,其效率和红黑树和平衡二叉树不相上下。目前redis和levelDB都有用到跳表。

    从上图可以看出,索引级的指针域除了指向下一个索引位置的指针,还有一个down指针指向低一级的链表位置,这样才能实现跳跃查询的目的。

     4、栈

    栈是一种比较简单的数据结构,常用一句话描述其特性,后进先出。栈本身是一个线性表,但是在这个表中只有一个口子允许数据的进出。这种模式可以参考腔肠动物...即进食和排泄都用一个口...

    栈的常用操作包括入栈push和出栈pop,对应于数据的压入和压出。还有访问栈顶数据、判断栈是否为空和判断栈的大小等。由于栈后进先出的特性,常可以作为数据操作的临时容器,对数据的顺序进行调控,与其它数据结构相结合可获得许多灵活的处理。

     5、队列

    队列是栈的兄弟结构,与栈的后进先出相对应,队列是一种先进先出的数据结构。顾名思义,队列的数据存储是如同排队一般,先存入的数据先被压出。常与栈一同配合,可发挥最大的实力。

     6、树

    树作为一种树状的数据结构,其数据节点之间的关系也如大树一样,将有限个节点根据不同层次关系进行排列,从而形成数据与数据之间的父子关系。常见的树的表示形式更接近“倒挂的树”,因为它将根朝上,叶朝下。

    树的数据存储在结点中,每个结点有零个或者多个子结点。没有父结点的结点在最顶端,成为根节点;没有非根结点有且只有一个父节点;每个非根节点又可以分为多个不相交的子树。

    这意味着树是具备层次关系的,父子关系清晰,家庭血缘关系明朗;这也是树与图之间最主要的区别。

    别看树好像很高级,其实可看作是链表的高配版。树的实现就是对链表的指针域进行了扩充,增加了多个地址指向子结点。同时将“链表”竖起来,从而凸显了结点之间的层次关系,更便于分析和理解。

    树可以衍生出许多的结构,若将指针域设置为双指针,那么即可形成最常见的二叉树,即每个结点最多有两个子树的树结构。二叉树根据结点的排列和数量还可进一度划分为完全二叉树、满二叉树、平衡二叉树、红黑树等。

    完全二叉树:除了最后一层结点,其它层的结点数都达到了最大值;同时最后一层的结点都是按照从左到右依次排布。

    满二叉树:除了最后一层,其它层的结点都有两个子结点。

    平衡二叉树

    平衡二叉树又被称为AVL树,它是一棵二叉排序树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

    二叉排序树:是一棵空树,或者:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉排序树。

    树的高度:结点层次的最大值

    平衡因子:左子树高度 - 右子树高度

    二叉排序树意味着二叉树中的数据是排好序的,顺序为左结点<根节点<右结点,这表明二叉排序树的中序遍历结果是有序的。(还不懂二叉树四种遍历方式[前序遍历、中序遍历、后序遍历、层序遍历]的同学赶紧补习!)

    平衡二叉树的产生是为了解决二叉排序树在插入时发生线性排列的现象。由于二叉排序树本身为有序,当插入一个有序程度十分高的序列时,生成的二叉排序树会持续在某个方向的字数上插入数据,导致最终的二叉排序树会退化为链表,从而使得二叉树的查询和插入效率恶化。

    平衡二叉树的出现能够解决上述问题,但是在构造平衡二叉树时,却需要采用不同的调整方式,使得二叉树在插入数据后保持平衡。主要的四种调整方式有LL(左旋)、RR(右旋)、LR(先左旋再右旋)、RL(先右旋再左旋)。这里先给大家介绍下简单的单旋转操作,左旋和右旋。LR和RL本质上只是LL和RR的组合。

    在插入一个结点后应该沿搜索路径将路径上的结点平衡因子进行修改,当平衡因子大于1时,就需要进行平衡化处理。从发生不平衡的结点起,沿刚才回溯的路径取直接下两层的结点,如果这三个结点在一条直线上,则采用单旋转进行平衡化,如果这三个结点位于一条折线上,则采用双旋转进行平衡化。

    左旋:S为当前需要左旋的结点,E为当前结点的父节点。

    左旋的操作可以用一句话简单表示:将当前结点S的左孩子旋转为当前结点父结点E的右孩子,同时将父结点E旋转为当前结点S的左孩子。可用动画表示:

     右旋:S为当前需要左旋的结点,E为当前结点的父节点。右单旋是左单旋的镜像旋转。

    左旋的操作同样可以用一句话简单表示:将当前结点S的左孩子E的右孩子旋转为当前结点S的左孩子,同时将当前结点S旋转为左孩子E的右孩子。可用动画表示:

    红黑树

    平衡二叉树(AVL)为了追求高度平衡,需要通过平衡处理使得左右子树的高度差必须小于等于1。高度平衡带来的好处是能够提供更高的搜索效率,其最坏的查找时间复杂度都是O(logN)。但是由于需要维持这份高度平衡,所付出的代价就是当对树种结点进行插入和删除时,需要经过多次旋转实现复衡。这导致AVL的插入和删除效率并不高。

    为了解决这样的问题,能不能找一种结构能够兼顾搜索和插入删除的效率呢?这时候红黑树便申请出战了。

    红黑树具有五个特性:

    1. 每个结点要么是红的要么是黑的。

    2. 根结点是黑的。

    3. 每个叶结点(叶结点即指树尾端NIL指针或NULL结点)都是黑的。

    4. 如果一个结点是红的,那么它的两个儿子都是黑的。

    5. 对于任意结点而言,其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

     黑树通过将结点进行红黑着色,使得原本高度平衡的树结构被稍微打乱,平衡程度降低。红黑树不追求完全平衡,只要求达到部分平衡。这是一种折中的方案,大大提高了结点删除和插入的效率。C++中的STL就常用到红黑树作为底层的数据结构。

    红黑树VS平衡二叉树

    除了上面所提及的树结构,还有许多广泛应用在数据库、磁盘存储等场景下的树结构。比如B树、B+树等。这里就先不介绍了诶,下次在讲述相关存储原理的时候将会着重介绍。(其实是因为懒)

    7、堆

    了解完二叉树,再来理解堆就不是什么难事了。堆通常是一个可以被看做一棵树的数组对象。堆的具体实现一般不通过指针域,而是通过构建一个一维数组与二叉树的父子结点进行对应,因此堆总是一颗完全二叉树。

    对于任意一个父节点的序号n来说(这里n从0算),它的子节点的序号一定是2n+1,2n+2,因此可以直接用数组来表示一个堆。

    不仅如此,堆还有一个性质:堆中某个节点的值总是不大于或不小于其父节点的值。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。 

    堆常用来实现优先队列,在面试中经常考的问题都是与排序有关,比如堆排序、topK问题等。由于堆的根节点是序列中最大或者最小值,因而可以在建堆以及重建堆的过程中,筛选出数据序列中的极值,从而达到排序或者挑选topK值的目的。 

     8、散列表

    散列表也叫哈希表,是一种通过键值对直接访问数据的机构。在初中,我们就学过一种能够将一个x值通过一个函数获得对应的一个y值的操作,叫做映射。散列表的实现原理正是映射的原理,通过设定的一个关键字和一个映射函数,就可以直接获得访问数据的地址,实现O(1)的数据访问效率。在映射的过程中,事先设定的函数就是一个映射表,也可以称作散列函数或者哈希函数。

    散列表的实现最关键的就是散列函数的定义和选择。一般常用的有以下几种散列函数:

    直接寻址法:取关键字或关键字的某个线性函数值为散列地址。

    数字分析法:通过对数据的分析,发现数据中冲突较少的部分,并构造散列地址。例如同学们的学号,通常同一届学生的学号,其中前面的部分差别不太大,所以用后面的部分来构造散列地址。

    平方取中:当无法确定关键字里哪几位的分布相对比较均匀时,可以先求出关键字的平方值,然后按需要取平方值的中间几位作为散列地址。这是因为:计算平方之后的中间几位和关键字中的每一位都相关,所以不同的关键字会以较高的概率产生不同的散列地址。

    取随机数法:使用一个随机函数,取关键字的随机值作为散列地址,这种方式通常用于关键字长度不同的场合。

    除留取余法:取关键字被某个不大于散列表的表长 n 的数 m 除后所得的余数 p 为散列地址。这种方式也可以在用过其他方法后再使用。该函数对 m 的选择很重要,一般取素数或者直接用 n。

    确定好散列函数之后,通过某个key值的确会得到一个唯一的value地址。但是却会出现一些特殊情况。即通过不同的key值可能会访问到同一个地址,这个现象称之为冲突。

    冲突在发生之后,当在对不同的key值进行操作时会使得造成相同地址的数据发生覆盖或者丢失,是非常危险的。所以在设计散列表往往还需要采用冲突解决的办法。

    常用的冲突处理方式有很多,常用的包括以下几种:

    开放地址法(也叫开放寻址法):实际上就是当需要存储值时,对Key哈希之后,发现这个地址已经有值了,这时该怎么办?不能放在这个地址,不然之前的映射会被覆盖。这时对计算出来的地址进行一个探测再哈希,比如往后移动一个地址,如果没人占用,就用这个地址。如果超过最大长度,则可以对总长度取余。这里移动的地址是产生冲突时的增列序量。

    再哈希法:在产生冲突之后,使用关键字的其他部分继续计算地址,如果还是有冲突,则继续使用其他部分再计算地址。这种方式的缺点是时间增加了。

    链地址法:链地址法其实就是对Key通过哈希之后落在同一个地址上的值,做一个链表。其实在很多高级语言的实现当中,也是使用这种方式处理冲突的。

    公共溢出区:这种方式是建立一个公共溢出区,当地址存在冲突时,把新的地址放在公共溢出区里。

    目前比较常用的冲突解决方法是链地址法,一般可以通过数组和链表的结合达到冲突数据缓存的目的。

    左侧数组的每个成员包括一个指针,指向一个链表的头。每发生一个冲突的数据,就将该数据作为链表的节点链接到链表尾部。这样一来,就可以保证冲突的数据能够区分并顺利访问。

    考虑到链表过长造成的问题,还可以使用红黑树替换链表进行冲突数据的处理操作,来提高散列表的查询稳定性。

     9、图

    图相较于上文的几个结构可能接触的不多,但是在实际的应用场景中却经常出现。比方说交通中的线路图,常见的思维导图都可以看作是图的具体表现形式。

    图结构一般包括顶点和边,顶点通常用圆圈来表示,边就是这些圆圈之间的连线。边还可以根据顶点之间的关系设置不同的权重,默认权重相同皆为1。此外根据边的方向性,还可将图分为有向图和无向图。

    图结构用抽象的图线来表示十分简单,顶点和边之间的关系非常清晰明了。但是在具体的代码实现中,为了将各个顶点和边的关系存储下来,却不是一件易事。 

    邻接矩阵

    目前常用的图存储方式为邻接矩阵,通过所有顶点的二维矩阵来存储两个顶点之间是否相连,或者存储两顶点间的边权重。

    无向图的邻接矩阵是一个对称矩阵,是因为边不具有方向性,若能从此顶点能够到达彼顶点,那么彼顶点自然也能够达到此顶点。此外,由于顶点本身与本身相连没有意义,所以在邻接矩阵中对角线上皆为0。

    有向图由于边具有方向性,因此彼此顶点之间并不能相互达到,所以其邻接矩阵的对称性不再。

    用邻接矩阵可以直接从二维关系中获得任意两个顶点的关系,可直接判断是否相连。但是在对矩阵进行存储时,却需要完整的一个二维数组。若图中顶点数过多,会导致二维数组的大小剧增,从而占用大量的内存空间。

    而根据实际情况可以分析得,图中的顶点并不是任意两个顶点间都会相连,不是都需要对其边上权重进行存储。那么存储的邻接矩阵实际上会存在大量的0。虽然可以通过稀疏表示等方式对稀疏性高的矩阵进行关键信息的存储,但是却增加了图存储的复杂性。

    因此,为了解决上述问题,一种可以只存储相连顶点关系的邻接表应运而生。

    邻接表

    在邻接表中,图的每一个顶点都是一个链表的头节点,其后连接着该顶点能够直接达到的相邻顶点。相较于无向图,有向图的情况更为复杂,因此这里采用有向图进行实例分析。

     

    邻接表中,每一个顶点都对应着一条链表,链表中存储的是顶点能够达到的相邻顶点。存储的顺序可以按照顶点的编号顺序进行。比如上图中对于顶点B来说,其通过有向边可以到达顶点A和顶点E,那么其对应的邻接表中的顺序即B->A->E,其它顶点亦如此。

    通过邻接表可以获得从某个顶点出发能够到达的顶点,从而省去了对不相连顶点的存储空间。然而,这还不够。对于有向图而言,图中有效信息除了从顶点“指出去”的信息,还包括从别的顶点“指进来”的信息。这里的“指出去”和“指进来”可以用出度和入度来表示。

    入度:有向图的某个顶点作为终点的次数和。

    出度:有向图的某个顶点作为起点的次数和。

    由此看出,在对有向图进行表示时,邻接表只能求出图的出度,而无法求出入度。这个问题很好解决,那就是增加一个表用来存储能够到达某个顶点的相邻顶点。这个表称作逆邻接表。

    逆邻接表

    逆邻接表与邻接表结构类似,只不过图的顶点链接着能够到达该顶点的相邻顶点。也就是说,邻接表时顺着图中的箭头寻找相邻顶点,而逆邻接表时逆着图中的箭头寻找相邻顶点。

    邻接表和逆邻接表的共同使用下,就能够把一个完整的有向图结构进行表示。可以发现,邻接表和逆邻接表实际上有一部分数据时重合的,因此可以将两个表合二为一,从而得到了所谓的十字链表。

    十字链表

    十字链表似乎很简单,只需要通过相同的顶点分别链向以该顶点为终点和起点的相邻顶点即可。

    但这并不是最优的表示方式。虽然这样的方式共用了中间的顶点存储空间,但是邻接表和逆邻接表的链表节点中重复出现的顶点并没有得到重复利用,反而是进行了再次存储。因此,上图的表示方式还可以进行进一步优化。

    十字链表优化后,可通过扩展的顶点结构和边结构来进行正逆邻接表的存储:(下面的弧头可看作是边的箭头那端,弧尾可看作是边的圆点那端)

    data:用于存储该顶点中的数据;

    firstin指针:用于连接以当前顶点为弧头的其他顶点构成的链表,即从别的顶点指进来的顶点;

    firstout指针:用于连接以当前顶点为弧尾的其他顶点构成的链表,即从该顶点指出去的顶点;

    边结构通过存储两个顶点来确定一条边,同时通过分别代表这两个顶点的指针来与相邻顶点进行链接:

    tailvex:用于存储作为弧尾的顶点的编号;

    headvex:用于存储作为弧头的顶点的编号;

    headlink 指针:用于链接下一个存储作为弧头的顶点的节点;

    taillink 指针:用于链接下一个存储作为弧尾的顶点的节点;

    以上图为例子,对于顶点A而言,其作为起点能够到达顶点E。因此在邻接表中顶点A要通过边AE(即边04)指向顶点E,顶点A的firstout指针需要指向边04的tailvex。同时,从B出发能够到达A,所以在逆邻接表中顶点A要通过边AB(即边10)指向B,顶点A的firstin指针需要指向边10的弧头,即headlink指针。依次类推。

    十字链表采用了一种看起来比较繁乱的方式对边的方向性进行了表示,能够在尽可能降低存储空间的情况下增加指针保留顶点之间的方向性。具体的操作可能一时间不好弄懂,建议多看几次上图,弄清指针指向的意义,明白正向和逆向邻接表的表示。

    10  总结

    数据结构博大精深,没有高等数学的讳莫如深,也没有量子力学的玄乎其神,但是其在计算机科学的各个领域都具有强大的力量。本文试图采用图解的方式对九种数据结构进行理论上的介绍,但是其实这都是不够的。

    即便是简单的数组、栈、队列等结构,在实际使用以及底层实现上都会有许多优化设计以及使用技巧,这意味着还需要真正把它们灵活的用起来,才能够算是真正意义上的熟悉和精通。但是本文可以作为常见数据结构的一个总结,当你对某些结构有些淡忘的时候,不妨重新回来看看。

     

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • 四种基本数据结构

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

    千次阅读 2021-12-15 13:53:48
    Java中常见数据结构 一、 8种数据结构 Java中有8种常见数据结构 哈希表(Hash) 队列(Queue) 树(Tree) 堆(Heap) 数组(Array) 栈(Stock) 链表(Linked List) 图(Graph) 哈希表(Hash) 哈希表也叫散列表,是一种可以...
  • 数据库中的基本数据结构

    千次阅读 2021-09-16 21:03:24
    MySQL索引定义:索引(Index) 是帮助MySQL高效获取数据的数据结构。 提取句子主干, 就可以得到索引的本质: 索引是数据结构。 大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构 数据结构具体...
  • 数据结构基本概念一、基本概念和术语1、数据2、数据元素3、数据对象4、数据类型5、数据结构二、数据结构三要素1、数据的逻辑结构2、数据的存储结构3、数据的运算三、习题 一、基本概念和术语 1、数据 数据是信息...
  • 这里主要介绍Python的4种基本数据结构:列表、字典、元组、集合。 格式如下: 列表:list = [val1,val2,val3,val4],用中括号; 字典:dict = {key1:val1,key2:val2},大括号,且每个元素是带有冒号的key与val的对应...
  • 1.2 基本概念和术语 一数据与数据结构 数据: 所有能输入到计算机中且能被计算机程序处理 的符号的总称 是计算机操作的对象的总称 是计算机处理的信息的某种特定的符号表示形式 数据元素 是数据集合中的一个个体是...
  • 数据结构分类及八种常见数据结构

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

    千次阅读 2021-04-16 19:31:03
    一、数据结构基本概念 (一)、数据 数据:数据是信息的载体,是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。 (二)、数据元素、数据...
  • 数据结构是程序设计的必修知识,它是程序设计的基本功,并且在企业面试、日常工作、研究生入学考试中都占有重要的地位。不同于其他课程,本课程从单链表出发,手把手的全代码实现了栈与队列,树、图(包括数组和链表...
  • 主要介绍了Python实现基本数据结构中队列的操作方法,结合实例形式演示了Python针对数据结构中队列的初始化、插入、删除、判断队列满及队列空等相关操作技巧,需要的朋友可以参考下
  • 数据结构基本概念【图文详解】

    千次阅读 2018-09-14 21:58:01
    1.1数据结构: 计算机科学是一门研究数据表示和数据处理的科学,在利用计算机进行数据处理时,实际需要处理的数据元素一般有很多。要提高数据处理效率,节省存储空间,如何组织数据就成了关键问题。而数据结构用来...
  • 数据结构基本概念 数据计算机程序所加工处理的描述客观事物的符号表示 数据元素数据的基本单位是数据集合中的一个个体,在计算机程序中通常作为一个整体进行考虑和处理数据元素可由一个或若干个数据项所组成 数据项是...
  • java常用数据结构有哪些

    千次阅读 2022-03-31 14:04:18
    Java常见数据结构 这 8 种数据结构有什么区别呢? ①、数组 优点: 按照索引查询元素的速度很快; 按照索引遍历数组也很方便。 缺点: 数组的大小在创建后就确定了,无法扩容; 数组只能存储一.
  • 数据结构可以从两个方面分析:逻辑结构与物理结构(存储结构)。 其中逻辑结构指的是数据的组织方式,物理结构指的是数据在内存上的存储方式。 逻辑结构分为四种类型:集合结构,线性结构,树形结构,图形结构。 ...
  • 主要介绍了JavaScript数据结构与算法之基本排序算法定义与效率比较,结合实例形式详细总结分析了javascript排序算法中的冒泡、选择、插入等排序算法原理与操作技巧,需要的朋友可以参考下
  • 王道数据结构学习笔记

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,204,742
精华内容 481,896
热门标签
关键字:

常见的数据结构的基本形式

数据结构 订阅