精华内容
下载资源
问答
  • 数据结构与算法必知基础知识
    千次阅读 多人点赞
    2021-01-06 22:58:12

    原创公众号:bigsai
    文章已收录在 全网都在关注的数据结构与算法学习仓库 欢迎star

    前言

    数据结构与算法是程序员内功体现的重要标准之一,且数据结构也应用在各个方面,业界更有程序=数据结构+算法这个等式存在。各个中间件开发者,架构师他们都在努力的优化中间件、项目结构以及算法提高运行效率和降低内存占用,在这里数据结构起到相当重要的作用。此外数据结构也蕴含一些面向对象的思想,故学好掌握数据结构对逻辑思维处理抽象能力有很大提升。

    为什么学习数据结构与算法?如果你还是学生,那么这门课程是必修的,考研基本也是必考科目。工作在内卷严重的大厂中找工作数据结构与算法也是面试、笔试必备的非常重要的考察点。如果工作了数据结构和算法也是内功提升一个非常重要的体现,对于程序员来说,想要得到满意的结果,数据结构与算法是必备功力!

    数据结构

    image-20201108002732048

    概念

    数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。

    简言之,数据结构是一系列的存储结构按照一定

    更多相关内容
  • 数据结构与算法学习笔记

    万次阅读 多人点赞 2018-09-25 13:55:49
    本文是王争老师的《算法与数据结构之美》的学习笔记,详细内容请看王争的专栏。有不懂的地方指出来,我做修改。 数据结构与算法思维导图 数据结构指的是“一组数据的存储结构”,算法指的是“操作数据的一组...

    本文是王争老师的《算法与数据结构之美》的学习笔记,详细内容请看王争的专栏 。有不懂的地方指出来,我做修改。

    数据结构与算法思维导图

    数据结构指的是“一组数据的存储结构”,算法指的是“操作数据的一组方法”。
    数据结构是为算法服务的,算法是要作用再特定的数据结构上的。

    最常用的数据结构预算法:

    • 数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Tire树
    • 算法: 递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法

    1  算法的复杂度

    1.1大O复杂度表示法

     公式:

    T(n)表示代码执行的时间; n表示数据规模的大小; f(n) 表示每行代码执行的次数总和。因为这是一个公式, 所以用f(n)来表示。公式中的O,表示代码的执行时间T(n)与f(n)表达式成正比。

          所以,第一个例子中的T(n) = O(2n+2),第二个例子中的T(m) = 0(2n2 +2n+3)。这就是大O时间复杂度表示法。大O时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度。

          当n很大时,你可以把它想象成10000、100000。 而公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略。我们只需要记录一个最大量级就可以了,如果用大O表示法表示刚讲的那两段代码的时间复杂度,就可以记为: T(n) = O(n); T(n)= 0(n2)。
     

    1.2.复杂度分析法则

    1)单段代码看高频:比如循环。
    2)多段代码取最大:比如一段代码中有单循环和多重循环,那么取多重循环的复杂度。
    3)嵌套代码求乘积:比如递归、多重循环等
    4)多个规模求加法:比如方法有两个参数控制两个循环的次数,那么这时就取二者复杂度相加。

    1.3 时间复杂度分析

    • 只关注循环执行次数最多的一段代码
    • 加法法则:总复杂度等于量级最大的那段代码的复杂度
    • 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

    1.4 几种常见时间复杂度实例分析

    多项式阶:随着数据规模的增长,算法的执行时间和空间占用,按照多项式的比例增长。包括,
    O(1)(常数阶)、O(logn)(对数阶)、O(n)(线性阶)、O(nlogn)(线性对数阶)、O(n^2)(平方阶)、O(n^3)(立方阶)
    非多项式阶:随着数据规模的增长,算法的执行时间和空间占用暴增,这类算法性能极差。包括,
    O(2^n)(指数阶)、O(n!)(阶乘阶)

    • O(1) :

    常量级时间复杂度,只要代码的执行时间不随 n 的增大而增长,这样代码的时间复杂度我们都记作 O(1)。

    • O(logn)、O(nlogn)
    i=1;
    while(i<=n) {
        i = i*2;
    }

    x=log2n,所以,这段代码的时间复杂度就是 O(log2n)

    • O(m+n)、O(m*n)

       int cal(int m, int n) {
          int sum_1=0;
          int i=1;
          for(;i<m;++i){
             sum_1 = sum_1 + i;
          }
          int sum_2 = 0;
          int j=1;
          for (;j<n;++j){
             sum_2 = sum_2 + j;
          }
          return sum_1 + sum_2;
       }

    从代码中可以看出,m和n是表示两个数据规模。我们无法事先评估m和n谁的量级大,所以我们在表示复杂度的时候,就不能简单地利用加法法则,省略掉其中一个。所以,上面代码的时间复 杂度就是0(m+n)。

    针对这种情况,原来的加法法则就不正确了,我们需要将加法规则改为: T1(m) + T2(m) = O(f(m) + g(n))。但是乘法法则继续有效: T1(m)*T2(n) = O(f(m) * f(n))。

    1.5 空间复杂度分析

    表示算法的存储空间与数据规模之间的增长关系。

    void print(int n) {
        inti=0;
        int[] a = new int[n];
        for (i; i <n; ++i) {
            a[i] =i* i;
        }
        for(i=n-1;i>=0;--i){
            print out a[i]
        }
    }

    跟时间复杂度分析一样,我们可以看到,第2行代码中,我们申请了一个空间存储变量i,但是它是常最阶的,跟数据规模n没有关系,所以我们可以忽略。第3行申请了一个大小为n的int类型数组,除此之外,剩下的代码都没有占用更多的空间,所以整段代码的空间复杂度就是O(n)。

    我们常见的空间复杂度就是O(1)、O(n)、 O(n2), 像O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且,空间复杂度分析比时间复杂度分析要简单很多。所以,对于空间复杂度,掌握刚我说的这些内容已经足够了。

    1.6 复杂度增长趋势图:

    最好情况时间复杂度、最坏时间复杂度、平均情況时间复杂度、均摊时间复杂度。

    一、复杂度分析的4个概念
    1.最坏情况时间复杂度:代码在最坏情况下执行的时间复杂度。
    2.最好情况时间复杂度:代码在最理想情况下执行的时间复杂度。
    3.平均时间复杂度:代码在所有情况下执行的次数的加权平均值。
    4.均摊时间复杂度:在代码执行的所有复杂度情况中绝大部分是低级别的复杂度,个别情况是高级别复杂度且发生具有时序关系时,可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

    二、为什么要引入这4个概念?
    1.同一段代码在不同情况下时间复杂度会出现量级差异,为了更全面,更准确的描述代码的时间复杂度,所以引入这4个概念。
    2.代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下,是不需要区别分析它们的。

    三、如何分析平均、均摊时间复杂度?
    1.平均时间复杂度
    代码在不同情况下复杂度出现量级差别,则用代码所有可能情况下执行次数的加权平均值表示。
    2.均摊时间复杂度
    两个条件满足时使用:1)代码在绝大多数情况下是低级别复杂度,只有极少数情况是高级别复杂度;2)低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。

    1、数组

    线性表:   线性表就是数据排成像一条线一样的结构.每个现行表上的数据最多只有前和后两个方向.常见的线性表结构:数组,链表、队列、栈等。

    什么是数组:

    1.  数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据
    2.  连续的内存空间和相同类型的数据(随机访问的前提)。
    3. 优点:两限制使得具有随机访问的特性缺点:删除,插入数据效率低。
    4. 对内存空间要求高,需要一块连续的内存空间。
    • 数组怎么根据下标随机访问的?

    通过寻址公式:a[i]_address = base_address + i * data_type_size
    其中data_type_size表示数组中每个元素的大小,base_address 是首元素地址,i数组下标。

    为何数组插入和删除低效:

    插入:
    若有一元素想往int[n]的第k个位置插入数据,需要在k-n的位置往后移。
    最好情况时间复杂度 O(1)

    如果数组中的数据不是有序的,也就是无规律的情况下,可以直接把第k个位置上的数据移到最后,然后将插入的数据直接放在第k个位置上。

    最坏情况复杂度为O(n)


    平均负责度为O(n)

    2. 低效的插入和删除
    1) 插入:从最好O(1) 最坏O(n) 平均O(n)
    2) 插入:数组若无序,插入新的元素时,可以将第K个位置元素移动到数组末尾,把心的元素,插入到第k个位置,此处复杂度为O(1)。
    3) 删除:从最好O(1) 最坏O(n) 平均O(n)
    4) 多次删除集中在一起,提高删除效率
    记录下已经被删除的数据,每次的删除操作并不是搬移数据,只是记录数据已经被删除,当数组没有更多的存储空间时,再触发一次真正的删除操作。即JVM标记清除垃圾回收算法。

    2、链表

    • 什么是链表

    1.和数组一样,链表也是一种线性表。
    2.从内存结构来看,链表的内存结构是不连续的内存空间,是将一组零散的内存块串联起来,从而进行数据存储的数据结构。
    3.链表中的每一个内存块被称为节点Node。节点除了存储数据外,还需记录链上下一个节点的地址,即后继指针next。

    • 链表的特点

    1.插入、删除数据效率高O(1)级别(只需更改指针指向即可),随机访问效率低O(n)级别(需要从链头至链尾进行遍历)。


    2.和数组相比,内存空间消耗更大,因为每个存储数据的节点都需要额外的空间存储后继指针。

    • 常用链表

    1.单链表


    1)每个节点只包含一个指针,即后继指针。
    2)单链表有两个特殊的节点,即首节点和尾节点。为什么特殊?用首节点地址表示整条链表,尾节点的后继指针指向空地址null。
    3)性能特点:插入和删除节点的时间复杂度为O(1),查找的时间复杂度为O(n)。

    2.循环链表


    1)除了尾节点的后继指针指向首节点的地址外均与单链表一致。
    2)适用于存储有循环特点的数据,比如约瑟夫问题。

    3.双向链表


    1)节点除了存储数据外,还有两个指针分别指向前一个节点地址(前驱指针prev)和下一个节点地址(后继指针next)。
    2)首节点的前驱指针prev和尾节点的后继指针均指向空地址。
    3)性能特点:
    和单链表相比,存储相同的数据,需要消耗更多的存储空间。
    插入、删除操作比单链表效率更高O(1)级别。以删除操作为例,删除操作分为2种情况:给定数据值删除对应节点和给定节点地址删除节点。对于前一种情况,单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除,时间复杂度为O(n)。对于第二种情况,要进行删除操作必须找到前驱节点,单链表需要从头到尾进行遍历直到p->next = q,时间复杂度为O(n),而双向链表可以直接找到前驱节点,时间复杂度为O(1)。
    对于一个有序链表,双向链表的按值查询效率要比单链表高一些。因为我们可以记录上次查找的位置p,每一次查询时,根据要查找的值与p的大小关系,决定是往前还是往后查找,所以平均只需要查找一半的数据。

    4.双向循环链表:

    首节点的前驱指针指向尾节点,尾节点的后继指针指向首节点。

    • 选择数组还是链表?

    1.插入、删除和随机访问的时间复杂度
    数组:插入、删除的时间复杂度是O(n),随机访问的时间复杂度是O(1)。
    链表:插入、删除的时间复杂度是O(1),随机访问的时间复杂端是O(n)。

    2.数组缺点
    1)若申请内存空间很大,比如100M,但若内存空间没有100M的连续空间时,则会申请失败,尽管内存可用空间超过100M。
    2)大小固定,若存储空间不足,需进行扩容,一旦扩容就要进行数据复制,而这时非常费时的。
    3.链表缺点
    1)内存空间消耗更大,因为需要额外的空间存储指针信息。
    2)对链表进行频繁的插入和删除操作,会导致频繁的内存申请和释放,容易造成内存碎片,如果是Java语言,还可能会造成频繁的GC(自动垃圾回收器)操作。
    4.如何选择?
    数组简单易用,在实现上使用连续的内存空间,可以借助CPU的缓冲机制预读数组中的数据,所以访问效率更高,而链表在内存中并不是连续存储,所以对CPU缓存不友好,没办法预读。
    如果代码对内存的使用非常苛刻,那数组就更适合。

    • 应用

    1.如何分别用链表和数组实现LRU缓冲淘汰策略?
    1)什么是缓存?
    缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非广泛的应用,比如常见的CPU缓存、数据库缓存、浏览器缓存等等。
    2)为什么使用缓存?即缓存的特点
    缓存的大小是有限的,当缓存被用满时,哪些数据应该被清理出去,哪些数据应该被保留?就需要用到缓存淘汰策略。
    3)什么是缓存淘汰策略?
    指的是当缓存被用满时清理数据的优先顺序。
    4)有哪些缓存淘汰策略?
    常见的3种包括先进先出策略FIFO(First In,First Out)、最少使用策略LFU(Least Frenquently Used)、最近最少使用策略LRU(Least Recently Used)。
    5)链表实现LRU缓存淘汰策略
    当访问的数据没有存储在缓存的链表中时,直接将数据插入链表表头,时间复杂度为O(1);当访问的数据存在于存储的链表中时,将该数据对应的节点,插入到链表表头,时间复杂度为O(n)。如果缓存被占满,则从链表尾部的数据开始清理,时间复杂度为O(1)。
    6)数组实现LRU缓存淘汰策略
    方式一:首位置保存最新访问数据,末尾位置优先清理
    当访问的数据未存在于缓存的数组中时,直接将数据插入数组第一个元素位置,此时数组所有元素需要向后移动1个位置,时间复杂度为O(n);当访问的数据存在于缓存的数组中时,查找到数据并将其插入数组的第一个位置,此时亦需移动数组元素,时间复杂度为O(n)。缓存用满时,则清理掉末尾的数据,时间复杂度为O(1)。
    方式二:首位置优先清理,末尾位置保存最新访问数据
    当访问的数据未存在于缓存的数组中时,直接将数据添加进数组作为当前最有一个元素时间复杂度为O(1);当访问的数据存在于缓存的数组中时,查找到数据并将其插入当前数组最后一个元素的位置,此时亦需移动数组元素,时间复杂度为O(n)。缓存用满时,则清理掉数组首位置的元素,且剩余数组元素需整体前移一位,时间复杂度为O(n)。(优化:清理的时候可以考虑一次性清理一定数量,从而降低清理次数,提高性能。)
    2.如何通过单链表实现“判断某个字符串是否为水仙花字符串”?(比如 上海自来水来自海上)
    1)前提:字符串以单个字符的形式存储在单链表中。
    2)遍历链表,判断字符个数是否为奇数,若为偶数,则不是。
    3)将链表中的字符倒序存储一份在另一个链表中。
    4)同步遍历2个链表,比较对应的字符是否相等,若相等,则是水仙花字串,否则,不是。
    六、设计思想
    时空替换思想:“用空间换时间” 与 “用时间换空间”
    当内存空间充足的时候,如果我们更加追求代码的执行速度,我们就可以选择空间复杂度相对较高,时间复杂度小相对较低的算法和数据结构,缓存就是空间换时间的例子。如果内存比较紧缺,比如代码跑在手机或者单片机上,这时,就要反过来用时间换空间的思路。

    3、队列

    什么是队列:

    队列是一种受限的线性表数据结构,只支持两个操作:入栈push()和出栈pop0,队列跟非常相似,支持的操作也 ,很有限,最基本的操作也是两个:入队enqueue(),放一个数据到队列尾部;出队dequeue0),从队列头部取一个元素。

    特点:

    1 . 队列跟栈一样,也是一种抽象的数据结构。

    2. 具有先进先出的特性,支持在队尾插入元素,在队头删除元素。

    实现:

    队列可以用数组来实现,也可以用链表来实现。

    用数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列。

    基于数组的队列:

    实现思路:

    实现队列需要两个指针:一个是head指针,指向队头;一个是tail指针,指向队尾。你可以结合下面这幅图来理解。当a,b,c,d依次入队之后,队列中的head指针指向下标为0的位置, tail指针指向下标为4的位置。

    当我们调用两次出队操作之后,队列中head指针指向下标为2的位置, tail指针仍然指向下标为4的位置.

    随着不停地进行入队、出队操作, head和tail都会持续往后移动。当tail移 . ,动到最右边,即使数组中还有空闲空间,也无法继续往队列中添加数据了。这个问题该如何解决呢?

    在出队时可以不用搬移数据。如果没有空闲空间了,我们只需要在入队时,再集中触 ,发一次数据的搬移操作。

    当队列的tail指针移动到数组的最右边后,如果有新的数据入队,我们可以将 head到tail之间的数据,整体搬移到数组中0到tail-head的位置。

    基于链表的实现: 

    需要两个指针: head指针和tail指针,它们分别指向链表的第一个结,点和最后一个结点。

    如图所示,入队时, tail->next= new node, tail = tail->next:出队时, head = head->next.

    循环队列:

    我们刚才用数组来实现队列的时候,在tail==n时,会有数据搬移操作,这样入队操作性能就会受到影响。那有没有办法能够避免数据搬移呢?我们来看看循环队列的解决思路。循环队列,顾名思义,它长得像一个环。原本数组是有头有尾的,是一条直线。现在我们把首尾相,连,板成了一个环。我画了一张图,你可以直观地感受一下。

    我们可以看到,图中这个队列的大小为8,当前head-4, tail-7,当有一个新的元素a入队时, .我们放入下标为7的位置。但这个时候,我们并不把tail更新为8,而是将其在环中后移一位,到下标为0的位置。当再有一个元素b入队时,我们将b放入下标为0的位置,然后tail加1更新为1,所以,在a, b依次入队之后,循环队列中的元素就变成了下面的样子:

    队列为空的判断条件是head == tail,但队列满的判断条件就稍微有点复杂了。我画了一张队列满的图,你可以看一下,试着总结一下规律,

    就像我图中画的队满的情况, tail=3, head-4, n=8,所以总结一下规律就是: (3+1)%8-4,多画几张队满的图,你就会发现,当队满时, (tail+1)%n=head..你有没有发现,当队列满时,图中的tail指向的位置实际上是没有存储数据的。所以,循环队列会浪费一个数组的存储空间。

    解决浪费一个存储空间的思路:定义一个记录队列大小的值size,当这个值与数组大小相等时,表示队列已满,当tail达到最底时,size不等于数组大小时,tail就指向数组第一个位置。当出队时,size—,入队时size++

    阻塞队列和并发队列(应用比较广泛)

    阻塞队列其实就是在队列基础上增加了阻塞操作。

    简单来说,就是在队列为空的时候,从队头取数 , 据会被阻塞。因为此时还没有数据可取,直到队列中有了数据才能返回;如果队列已经满了,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回。

    你应该已经发现了,上述的定义就是一个"生产者-消费者模型" !是的,我们可以使用阻塞队列,轻松实现一个"生产者-消费者模型" !这种基干阴寒队列实现的"生产者-消费者模型" ,可以有效地协调生产和消费的速度。当"生产 , 者"生产数据的速度过快, "消费者"来不及消费时,存储数据的队列很快就会满了。这个时候,生产者就阻塞等待,直到"消费者"消费了数据, "生产者"才会被唤醒继续"生产而且不仅如此,基于阻塞队列,我们还可以通过协调"生产者"和"消费者"的个数,来提高数据,的处理效率。比如前面的例子,我们可以多配置几个"消费者" ,来应对一个"生产者"

    小结:

    队列最大的特点就是先进先出,主要的两个操作是入队和出队。

    它既可以用数组来实现,也可以用链表来实现。用数组实现的叫顺序队列,用链表实现的叫链式队列。

    长在数组实现队列的时候,会有数据搬移操作,要想解决数据搬移的问题,我们就,需要像环一样的循环队列。要想写出没有bug的循环队列实现代码,关键要确定好队空和队满的,判定条件。

    阻塞队列、并发队列,底层都还是队列这种数据结构,只不过在之上附加了很多其他功能。阻塞队列就是入队、出队操作可以阴寒,并发队列就是队列的操作多线程安全。

    4、递归算法

    一、什么是递归?

    1.递归是一种非常高效、简洁的编码技巧,一种应用非常广泛的算法,比如DFS深度优先搜索、前中后序二叉树遍历等都是使用递归。
    2.方法或函数调用自身的方式称为递归调用,调用称为递,返回称为归。
    3.基本上,所有的递归问题都可以用递推公式来表示,比如
    f(n) = f(n-1) + 1; 
    f(n) = f(n-1) + f(n-2);
    f(n)=n*f(n-1);

    二、为什么使用递归?递归的优缺点?

    1.优点:代码的表达力很强,写起来简洁。
    2.缺点:空间复杂度高、有堆栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题。

    三、什么样的问题可以用递归解决呢?

    一个问题只要同时满足以下3个条件,就可以用递归来解决:
    1.问题的解可以分解为几个子问题的解。何为子问题?就是数据规模更小的问题。
    2.问题与子问题,除了数据规模不同,求解思路完全一样
    3.存在递归终止条件

    四、如何实现递归?

    1.递归代码编写
    写递归代码的关键就是找到如何将大问题分解为小问题的规律,并且基于此写出递推公式,然后再推敲终止条件,最后将递推公式和终止条件翻译成代码。
    2.递归代码理解
    对于递归代码,若试图想清楚整个递和归的过程,实际上是进入了一个思维误区。
    那该如何理解递归代码呢?如果一个问题A可以分解为若干个子问题B、C、D,你可以假设子问题B、C、D已经解决。而且,你只需要思考问题A与子问题B、C、D两层之间的关系即可,不需要一层层往下思考子问题与子子问题,子子问题与子子子问题之间的关系。屏蔽掉递归细节,这样子理解起来就简单多了。
    因此,理解递归代码,就把它抽象成一个递推公式,不用想一层层的调用关系,不要试图用人脑去分解递归的每个步骤。

    递归的关键是终止条件
    五、递归常见问题及解决方案

    1.警惕堆栈溢出:可以声明一个全局变量来控制递归的深度,从而避免堆栈溢出。
    2.警惕重复计算:通过某种数据结构来保存已经求解过的值,从而避免重复计算。

    六、如何将递归改写为非递归代码?

    笼统的讲,所有的递归代码都可以改写为迭代循环的非递归写法。如何做?抽象出递推公式、初始值和边界条件,然后用迭代循环实现。

    5、排序



    一、排序方法与复杂度归类
    (1)几种最经典、最常用的排序方法:冒泡排序、插入排序、选择排序、快速排序、归并排序、计数排序、基数排序、桶排序。
    (2)复杂度归类
    冒泡排序、插入排序、选择排序 O(n^2)
    快速排序、归并排序 O(nlogn)
    计数排序、基数排序、桶排序 O(n)

    二、如何分析一个“排序算法”?
    <1>算法的执行效率
    1. 最好、最坏、平均情况时间复杂度。
    2. 时间复杂度的系数、常数和低阶。
    3. 比较次数,交换(或移动)次数。
    <2>排序算法的稳定性
    1. 稳定性概念:如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。
    2. 稳定性重要性:可针对对象的多种属性进行有优先级的排序。
    3. 举例:给电商交易系统中的“订单”排序,按照金额大小对订单数据排序,对于相同金额的订单以下单时间早晚排序。用稳定排序算法可简洁地解决。先按照下单时间给订单排序,排序完成后用稳定排序算法按照订单金额重新排序。
    <3>排序算法的内存损耗
    原地排序算法:特指空间复杂度是O(1)的排序算法。

    常见的排序算法:


    冒泡排序


    冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求,如果不满足就让它俩互换。

    代码:

      public int[] bubbleSort(int[] a) {
            int n = a.length;
            if (n<=1) {
                return a;
            }
            for (int i = 0; i < n; i++) {
                //提前退出冒泡循环的标志
                boolean flag = false;
                for (int j = 0; j < n-i-1; j++) {
                    if (a[j]>a[j+1]) {//
                        int temp = a[j];
                        a[j] = a[j+1];
                        a[j+1] = temp;
    
                        flag = true;//表示有数据交换
                    }
                    if (!flag) {
                        break; //没有数据交换(说明已排好序无需再进行冒泡),提前退出
                    }
                }
            }
            return a;
        }


    四、插入排序


    插入排序将数组数据分成已排序区间和未排序区间。初始已排序区间只有一个元素,即数组第一个元素。在未排序区间取出一个元素插入到已排序区间的合适位置,直到未排序区间为空。

    代码:

        public int[] insertionSort(int[] a) {
    		int n = a.length;
    		if (n<=1) return a;
    		
    		for (int i = 1; i < n; i++) {
    			int value = a[i];
    			int j = i-1;
    			for (; j >=0; j--) {
    				if (a[j] > value) {
    					a[j+1] = a[j];//移动数据
    				}else {
    					break;
    				}
    			}
    			a[j+1] = value;//插入数据
    		}
    		
    		return a;
    	}


    五、选择排序


    选择排序将数组分成已排序区间和未排序区间。初始已排序区间为空。每次从未排序区间中选出最小的元素插入已排序区间的末尾,直到未排序区间为空。
    代码:

    public int[] selectionSort(int[] a) {
    		int n = a.length;
    		
    		for (int i = 0; i < a.length - 1; i++) {
    			for (int j = i+1; j < a.length; j++) {
    				//交换
    				if (a[i] > a[j]) {
    					int temp = a[i];
    					a[i] = a[j];
    					a[j] = temp;
    				}
    			}
    		}
    		
    		return a;
    	}

    六、归并排序

    如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。

     实现思路:

    merge-sort(p...r)表示,给下标从p到r之间的数组排序。我们将这个排序问题转化为了两个子问 ,题, merge_sort(p...q)和merge-sort(q+1..r),其中下标q等于p和r的中间位置,也就是, (p+r)/2,当下标从p到q和从q+1到r这两个子数组都排好序之后,我们再将两个有序的子数组合并在一起,这样下标从p到r之间的数据就也排好序了。

    代码:

     // 归并排序算法, a是数组,n表示数组大小
      public static void mergeSort(int[] a, int n) {
        mergeSortInternally(a, 0, n-1);
      }
    
      // 递归调用函数
      private static void mergeSortInternally(int[] a, int p, int r) {
        // 递归终止条件
        if (p >= r) return;
    
        // 取p到r之间的中间位置q
        int q = (p+r)/2;
        // 分治递归
        mergeSortInternally(a, p, q);
        mergeSortInternally(a, q+1, r);
    
        // 将A[p...q]和A[q+1...r]合并为A[p...r]
        merge(a, p, q, r);
      }
    
      private static void merge(int[] a, int p, int q, int r) {
        int i = p;
        int j = q+1;
        int k = 0; // 初始化变量i, j, k
        int[] tmp = new int[r-p+1]; // 申请一个大小跟a[p...r]一样的临时数组
       
        // 1 排序
        while (i<=q && j<=r) {
          if (a[i] <= a[j]) {
            tmp[k++] = a[i++]; // i++等于i:=i+1
          } else {
            tmp[k++] = a[j++];
          }
        }
    
        // 2 判断哪个子数组中有剩余的数据
        int start = i;
        int end = q;
        if (j <= r) {
          start = j;
          end = r;
        }
    
        // 3 将剩余的数据拷贝到临时数组tmp
        while (start <= end) {
          tmp[k++] = a[start++];
        }
    
        // 4 将tmp中的数组拷贝回a[p...r]
        for (i = 0; i <= r-p; ++i) {
          a[p+i] = tmp[i];
        }
      }
    

    merge是这样执行的:

    代码分析:

    七、快速排序

    快排的思想:    如果要排序数组中下标从p到r之间的一组数据,我们选择p到r之间的任意一个数据作为pivot (分区点) 。我们遍历p到r之间的数据,将小于pivot的放到左边,将大于pivot的放到右边,将pivot放到中间。经过这一步骤之后,数组p到r之间的数据就被分成了三个部分,前面p到q-1之间都是小于pivot的,中间是pivot,后面的q+1到r之间是大于pivot的。

    快排利用的分而治之的思想

    八、线性排序:

    时间复杂度O(n)

    我们把时间复杂度是线性的排序算法叫作线性排序(Linear sort)常见的线性算法有: 桶排序、计数排序、基数排序

    特点:

    非基于比较的排序算法 

    桶排序

    桶排序,顾名思义,会用到“桶" ,核心思想是将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行排序。桶内排完序之后,再把每个桶里的数据按照顺序依次取出,组成的序列就是有序的了。

    对排序的数据要求苛刻:

    1, 要排序的数据需要很容易就能划分成m个桶,并且,桶与桶之间有着天然的大小顺序。

    2 ,数据在各个桶之间的分布是比较均匀的。

    3 ,桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中,数据量比较大,内存有限,无法将数据全部加载到内存中。

    计数排序

    计数排序只能用在数据范围不大的场景中,如果数据范围k比要排序的数据n大很多,就不适合用计数排序了。

    计数排序只能给非负整数排序,如果要排序的数据是其他类型的,要将其在不改变相对大小的情况下,转化为非负整数。

    代码:

     // 计数排序,a是数组,n是数组大小。假设数组中存储的都是非负整数。
      public static void countingSort(int[] a) {
    	int n = a.length;
        if (n <= 1) return;
    
        // 查找数组中数据的范围
        int max = a[0];
        for (int i = 1; i < n; ++i) {
          if (max < a[i]) {
            max = a[i];
          }
        }
    
        // 申请一个计数数组c,下标大小[0,max]
        int[] c = new int[max + 1];
        for (int i = 0; i < max + 1; ++i) {
          c[i] = 0;
        }
    
        // 计算每个元素的个数,放入c中
        for (int i = 0; i < n; ++i) {
          c[a[i]]++;
        }
    
        // 依次累加
        for (int i = 1; i < max + 1; ++i) {
          c[i] = c[i-1] + c[i];
        }
    
        // 临时数组r,存储排序之后的结果
        int[] r = new int[n];
        // 计算排序的关键步骤了,有点难理解
        for (int i = n - 1; i >= 0; --i) {
          int index = c[a[i]]-1;
          r[index] = a[i];
          c[a[i]]--;
        }
    
        // 将结果拷贝会a数组
        for (int i = 0; i < n; ++i) {
          a[i] = r[i];
        }
      }

    散列表

    什么是散列表:

    散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。

    原理:

    散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是0(1)的特性。我们通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时,我们用同样的散列函数,将键值转化数组标标,从对应的数组下标的位置取数据。

    散列函数的设计要求:

    1. 散列函数计算得到的散列值是一个非负整数;.
    2. 如果key1 = key2,那hash(key1) == hash(key2);
    3. 如果key1 != key2,那hash(key1)  !=  hash(key2),

    散列函数的设计不能太复杂,散列函数生成值要尽可能随机并且均匀分布

    如果不符合3 那么就出现了散列冲突,散列冲突是无法避免的

    解决散列冲突的方法有两种: 

    开放寻址法(open addressing)和链表法(chaining)

    开放寻址法:如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入。

    装在因子:  散列表中一定比例的空闲槽位。公式: 散列表的装载因子 = 填入表中的元素个数 / 散列表的长度

    装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降。

    链表法:

    链表法是一种更加常用的散列冲突解决办法,相比开放寻址法,它要简单很多。我们来看这个图,在散列表中,每个"桶(bucket) "或者"槽(slot) "会对应一条链表,所有散列值相同的元素我们都放到相同槽位对应的链表中。

    展开全文
  • 一篇文章讲清python开发必懂的8种数据结构

    千次阅读 多人点赞 2021-08-05 09:08:57
    知道哪个数据结构最适合当前的解决方案将提高程序的性能,并减少开发所需的时间。出于这个原因,大多数顶级公司都要求对数据结构有很深的理解,并在编码面试中对其进行深入的考察。 下面是我们今天要讲的内容: 什么...

    image.png
    在解决现实世界的编码问题时,雇主和招聘人员都在寻找运行时和资源效率。

    知道哪个数据结构最适合当前的解决方案将提高程序的性能,并减少开发所需的时间。出于这个原因,大多数顶级公司都要求对数据结构有很深的理解,并在编码面试中对其进行深入的考察。

    下面是我们今天要讲的内容:

    • 什么是数据结构?
    • 在Python中数组
    • 队列在Python中
    • 栈在Python中
    • Python中的链表
    • Python中的循环链表
    • Python种的树
    • Python中的哈希表
    • 接下来学什么

    什么是数据结构?

    数据结构是用于存储和组织数据的代码结构,使修改、导航和访问信息变得更加容易。数据结构决定了如何收集数据、我们可以实现的功能以及数据之间的关系。
    数据结构几乎用于计算机科学和编程的所有领域,从操作系统到前端开发,再到机器学习。
    数据结构有助于:

    • 管理和利用大型数据集
    • 从数据库中快速搜索特定数据
    • 在数据点之间建立清晰的分层或关系连接
    • 简化并加快数据处理

    数据结构是高效、真实解决问题的重要构建模块。数据结构是经过验证和优化的工具,为您提供了一个简单的框架来组织您的程序。毕竟,你没有必要每次都重新制作轮子 (或结构)。

    每个数据结构都有一个最适合解决的任务或情况。Python有4个内置的数据结构、列表、字典、元组和集合。这些内置数据结构带有默认方法和幕后优化,使其易于使用。

    • List:类似数组的结构,允许将一组相同类型的可变对象保存为变量。
    • 元组:元组是不可变的列表,意味着元素不能被更改。它是用圆括号声明的,而不是方括号。
    • Set:集合是无序的集合,这意味着元素是没有索引的,并且没有集合序列。它们用花括号声明。
    • 字典(dict):类似于其他语言中的hashmap或哈希表,字典是键/值对的集合。用空花括号初始化空字典,并用冒号分隔的键和值填充。所有键都是唯一的、不可变的对象。

    现在,让我们看看如何使用这些结构来创建面试官想要的所有高级结构。

    Arrays (Lists) in Python

    Python没有内置数组类型,但您可以为所有相同的任务使用列表。数组是以相同名称保存的相同类型的值的集合。
    数组中的每个值都被称为“元素”,索引表示其位置。您可以通过使用所需元素的索引调用数组名称来访问特定的元素。您还可以使用len()方法获取数组的长度。

    image.png

    不像Java这样的编程语言在声明后有静态数组,Python的数组在添加/减去元素时自动伸缩。

    例如,可以使用append()方法在现有数组的末尾添加一个额外的元素,而不是声明一个新数组。

    这使得Python数组特别易于使用和动态适应。

    cars = ["Toyota", "Tesla", "Hyundai"]
    print(len(cars))
    cars.append("Honda")
    cars.pop(1)
    for x in cars:
      print(x)
    

    优势:

    • 创建和使用数据序列简单
    • 自动缩放以满足不断变化的尺寸要求
    • 用于创建更复杂的数据结构

    缺点:

    • 未针对科学数据进行优化 (与NumPy的数组不同)
    • 只能操作列表的最右边

    应用:

    • 相关值或对象的共享存储,即myDogs
    • 通过循环访问
    • 数据结构的集合,例如元组列表

    Python中的常见数组面试问题

    • 从列表中删除偶数整数
    • 合并两个排序列表
    • 在列表中找到最小值
    • 最大总和子列表
    • 打印所有元素

    Python中的队列

    队列是一种线性数据结构,以 “先进先出” (FIFO) 顺序存储数据。与数组不同,您不能按索引访问元素,而只能提取下一个最旧的元素。这使得它非常适合订单敏感任务,如在线订单处理或语音邮件存储。
    你可以把在杂货店排队; 收银员不会选择下一个结账的人,而是会处理排队时间最长的人。

    image.png

    我们可以使用带有append()和pop()方法的Python列表来实现队列。然而,这是低效的,因为当您向开始添加新元素时,列表必须按一个索引移动所有元素。

    相反,最好的做法是使用Python的collections模块中的deque类。deque对追加和弹出操作进行了优化。deque实现还允许创建双端队列,该队列可以通过popleft()和popright()方法访问队列的两端。

    from collections import deque
    # Initializing a queue
    q = deque()
    # Adding elements to a queue
    q.append('a')
    q.append('b')
    q.append('c')
    print("Initial queue")
    print(q)
    # Removing elements from a queue
    print("\nElements dequeued from the queue")
    print(q.popleft())
    print(q.popleft())
    print(q.popleft())
    print("\nQueue after removing elements")
    print(q)
    # Uncommenting q.popleft()
    # will raise an IndexError
    # as queue is now empty
    

    优点:

    • 按时间顺序自动处理数据
    • 根据数据量大小自动缩放
    • deque类的时间效率高

    缺点:

    • 只能访问两端的数据

    应用程序:

    • 打印机或CPU核心等共享资源的操作
    • 作为批处理系统的临时存储
    • 为同等重要的任务提供一个简单的默认顺序

    Python中的常见队列面试问题

    • 反转队列的前k个元素
    • 使用链表实现队列
    • 使用队列实现堆栈

    Python中的栈

    栈是一种连续的数据结构,充当队列的后进先出(LIFO)版本。插入到堆栈中的最后一个元素被认为是堆栈的顶部,并且是唯一可访问的元素。要访问中间元素,必须首先删除足够多的元素,使所需的元素位于堆栈顶部。

    许多开发者将堆栈想象成一堆餐盘;你可以把盘子加到或移到盘子堆的顶部,但必须移动整个盘子堆才能把一个放在底部。

    image.png

    添加元素称为push,删除元素称为pop。你可以在Python中使用内置的列表结构来实现栈。对于列表实现,推操作使用append()方法,弹出操作使用pop()。

    stack = []
    # append() function to push
    # element in the stack
    stack.append('a')
    stack.append('b')
    stack.append('c')
    print('Initial stack')
    print(stack)
    # pop() function to pop
    # element from stack in 
    # LIFO order
    print('\nElements popped from stack:')
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())
    print('\nStack after elements are popped:')
    print(stack)
    # uncommenting print(stack.pop())  
    # will cause an IndexError 
    # as the stack is now empty
    

    优势:

    • 提供应用程序无法实现的后进先出数据管理:
    • 自动缩放和对象清理
    • 简单可靠的数据存储系统

    缺点:

    • 堆栈内存有限
    • 堆栈上的对象太多会导致堆栈溢出错误

    应用:

    • 用于开发高吞吐量的系统
    • 内存管理系统首先使用堆栈来处理最近的请求
    • 对括号匹配等问题有帮助

    Python中的常见堆面试问题

    • 使用栈实现队列
    • 使用栈计算后缀表达式
    • 使用栈获取下一个最大元素
    • 使用栈创建min() 函数

    Python中的链表

    链表是数据的顺序集合,使用每个数据节点上的关系指针链接到列表中的下一个节点。

    与数组不同,链表在列表中没有目标位置。相反,它们基于节点串联起来。

    链表中的第一个节点称为头节点,最后一个节点称为尾节点,其中尾节点的next指向为null。

    image.png

    链表可以是单链,也可以是双链,这取决于每个节点是只有一个指向下一个节点的指针,还是还有一个指向前一个节点的指针。

    你可以把链表想象成一条链;单个链接只与相邻的链接有一个连接,但所有链接一起形成一个更大的结构。

    Python没有链表的内置实现,因此需要实现一个Node类来保存数据值和一个或多个指针。

    class Node:
        def __init__(self, dataval=None):
            self.dataval = dataval
            self.nextval = None
    class SLinkedList:
        def __init__(self):
            self.headval = None
    list1 = SLinkedList()
    list1.headval = Node("Mon")
    e2 = Node("Tue")
    e3 = Node("Wed")
    # Link first Node to second node
    list1.headval.nextval = e2
    # Link second Node to third node
    e2.nextval = e3
    

    优势:

    • 新元素插入和删除更高效
    • 比数组更易于重组
    • 高级数据结构 (如图形或树)都是基于链表的

    缺点:

    • 每个数据点的指针存储增加了内存使用量
    • 必须始终从头节点遍历链表以查找特定元素

    应用:

    • 高级数据结构的构建块
    • 需要频繁添加和删除数据的解决方案

    Python中的常见链表面试问题

    • 打印给定链表的中间元素
    • 从已排序的链表中删除重复元素
    • 检查单链接列表是否为回文
    • 合并K排序链表
    • 查找两个链表的交点

    Python中的循环链表

    标准链表的主要缺点是,您总是必须从Head节点开始。循环链表通过将Tail节点的空指针替换为指向Head节点的指针来解决这个问题。当遍历时,程序将跟随指针,直到到达它开始的节点。

    image.png
    这种设置的优点是,您可以从任何节点开始遍历整个列表。它还允许您通过设置结构中所需的循环次数来使用链表作为一个可循环结构。循环链表对于长时间循环的进程非常有用,比如操作系统中的CPU分配。

    优点:

    • 可以从任何节点开始遍历整个列表
    • 使链表更适合循环结构

    缺点:

    • 如果没有空标记,将更难找到列表的Head和Tail节点

    应用:

    • 定期循环解决方案,如CPU调度

    Python中常见的循环链表面试问题

    • 在链表中检测循环
    • 反转循环链表
    • 给定大小的组中的反向圆形链表

    Python中的树形结构

    树是另一种基于关系的数据结构,专门用于表示层次结构。与链表一样,它们也被Node对象填充,Node对象包含一个数据值和一个或多个指针,用于定义其与直接节点的关系。

    每棵树都有一个根节点,所有其他节点都从根节点分支出来。根节点包含指向它正下方所有元素的指针,这些元素被称为它的子节点。这些子节点可以有它们自己的子节点。二叉树的节点不能有两个以上的子节点。

    在同一层上的任何节点都称为同级节点。没有连接子节点的节点称为叶节点。

    image.png

    二叉树最常见的应用是二叉搜索树。二叉搜索树擅长于搜索大量的数据集合,因为时间复杂度取决于树的深度而不是节点的数量。

    二叉搜索树有四个严格的规则:

    • 左子树只包含元素小于根的节点。
    • 右子树只包含元素大于根的节点。
    • 左右子树也必须是二叉搜索树。他们必须以树的“根”来遵循上述规则。
    • 不能有重复的节点,即不能有两个节点具有相同的值。
    lass Node:
        def __init__(self, data):
            self.left = None
            self.right = None
            self.data = data
        def insert(self, data):
    # Compare the new value with the parent node
            if self.data:
                if data < self.data:
                    if self.left is None:
                        self.left = Node(data)
                    else:
                        self.left.insert(data)
                elif data > self.data:
                    if self.right is None:
                        self.right = Node(data)
                    else:
                        self.right.insert(data)
            else:
                self.data = data
    # Print the tree
        def PrintTree(self):
            if self.left:
                self.left.PrintTree()
            print( self.data),
            if self.right:
                self.right.PrintTree()
    # Use the insert method to add nodes
    root = Node(12)
    root.insert(6)
    root.insert(14)
    root.insert(3)
    root.PrintTree()
    

    优点:

    • 用于表示层次关系
    • 动态大小,规模巨大
    • 快速插入和删除操作
    • 在二叉搜索树中,插入的节点被立即排序。
    • 二叉搜索树的搜索效率高;长度只有O(高度)。

    缺点:

    • 修改或“平衡”树或从已知位置检索元素的时间开销为O(logn)
    • 子节点在父节点上没有信息,并且很难向后遍历
    • 仅适用于排序的列表。未排序的数据退化为线性搜索。

    应用:

    • 非常适合存储分层数据,如文件位置

    Python中的常见树面试问题

    • 检查两棵二叉树是否相同
    • 实现一个二叉树的层次顺序遍历
    • 打印二叉搜索树的周长
    • 对路径上的所有节点求和
    • 连接二叉树的所有兄弟

    python中的图

    图是一种数据结构,用于表示数据顶点(图的节点)之间关系的可视化。将顶点连接在一起的链接称为边。

    边定义了哪些顶点被连接,但没有指明它们之间的流向。每个顶点与其他顶点都有连接,这些连接以逗号分隔的列表形式保存在顶点上。

    image.png

    还有一种特殊的图叫做有向图,它定义了关系的方向,类似于链表。在建模单向关系或类似流程图的结构时,有向图很有帮助。

    image.png

    它们主要用于以代码形式传达可视化的网络结构网络。这些结构可以为许多不同类型的关系建模,比如层次结构、分支结构,或者只是一个无序的关系网络。图形的通用性和直观性使它们成为数据科学的宠儿。
    当以纯文本形式编写时,图具有顶点和边的列表:

    V = {a, b, c, d, e}
    E = {ab, ac, bd, cd, de}
    

    在Python中,图的最佳实现方式是使用字典,每个顶点的名称作为键,边列表作为值。

    # Create the dictionary with graph elements
    graph = { "a" : ["b","c"],
                     "b" : ["a", "d"],
                     "c" : ["a", "d"],
                      "d" : ["e"],
                      "e" : ["d"]
             }
    # Print the graph          
    print(graph)
    

    优点:

    • 通过代码快速传达视觉信息
    • 可用于建模广泛的现实世界问题
    • 语法学习简单

    缺点:

    • 在大型图中很难理解顶点链接
    • 从图表中解析数据的时间昂贵

    应用:

    • 非常适合网络或类似网络的结构建模
    • 曾为Facebook等社交网站建模

    Python中的常见图形面试问题

    • 在有向图中检测周期
    • 在有向图中找到一个“母顶点”
    • 计算无向图中的边数
    • 检查两个顶点之间是否存在路径
    • 求两个顶点之间的最短路径

    Python中的哈希表

    哈希表是一种复杂的数据结构,能够存储大量信息并有效检索特定元素。
    此数据结构使用键/值对,其中键是所需元素的名称,值是存储在该名称下的数据。

    image.png

    每个输入键都要经过一个哈希函数,该函数将其从初始形式转换为一个整数值,称为哈希。哈希函数必须始终从相同的输入产生相同的哈希,必须快速计算,并产生固定长度的值。Python包含一个内置的hash()函数,可以加速实现。

    然后,该表使用散列来查找所需值(称为存储桶)的一般位置。然后,程序只需要在这个子组中搜索所需的值,而不必搜索整个数据池。

    除了这个通用框架之外,根据应用程序的不同,哈希表也可能非常不同。有些可能允许来自不同数据类型的键,而有些可能有不同的设置桶或不同的散列函数。

    下面是一个Python代码中的哈希表示例:

    import pprint
    class Hashtable:
        def __init__(self, elements):
            self.bucket_size = len(elements)
            self.buckets = [[] for i in range(self.bucket_size)]
            self._assign_buckets(elements)
        def _assign_buckets(self, elements):
            for key, value in elements: #calculates the hash of each key
                hashed_value = hash(key)
                index = hashed_value % self.bucket_size # positions the element in the bucket using hash
                self.buckets[index].append((key, value)) #adds a tuple in the bucket
        def get_value(self, input_key):
            hashed_value = hash(input_key)
            index = hashed_value % self.bucket_size
            bucket = self.buckets[index]
            for key, value in bucket:
                if key == input_key:
                    return(value)
            return None
        def __str__(self):
            return pprint.pformat(self.buckets) # pformat returns a printable representation of the object
    if __name__ == "__main__":
         capitals = [
            ('France', 'Paris'),
            ('United States', 'Washington D.C.'),
            ('Italy', 'Rome'),
            ('Canada', 'Ottawa')
        ]
    hashtable = Hashtable(capitals)
    print(hashtable)
    print(f"The capital of Italy is {hashtable.get_value('Italy')}"
    

    优点:

    • 可以将任何形式的键隐藏为整数索引
    • 对于大型数据集非常有效
    • 搜索效率高
    • 每次搜索的步骤数不变,添加或删除元素的效率不变
    • 在Python 3中进一步优化

    缺点:

    • 哈希值必须是唯一的,两个键转换为相同的哈希值会导致冲突错误
    • 碰撞错误需要对哈希函数进行全面修改
    • 对于初学者来说很难构建

    应用程序:

    • 用于频繁查询的大型数据库
    • 根据关键字检索的系统

    Python中常见的哈希表面试问题

    • 从头开始构建哈希表(不含内置函数)
    • 找出两个加起来是k的数
    • 为冲突处理实现开放寻址
    • 使用哈希表检测列表是否循环

    _学习愉快!

    展开全文
  • 数据结构是计算机存储、组织数据的方式。一种好的数据结构可以带来更高的运行或者存储效率。数据在内存中是呈线性排列的,但是我们可以使用指针等道具,构造出类似“树形”的复杂结构。下面介绍八个常见的数据结构

    相似文章推荐:


    零. 总览

    数据结构是计算机存储、组织数据的方式。一种好的数据结构可以带来更高的运行或者存储效率。数据在内存中是呈线性排列的,但是我们可以使用指针等道具,构造出类似“树形”的复杂结构。下面介绍八个常见的数据结构。
    在这里插入图片描述

    一. 数组

    数组是一种线性结构,而且在物理内存中也占据着一块连续空间。

    • 优点:访问数据简单。
    • 缺点:添加和删除数据比较耗时间。
    • 使用场景:频繁查询,对存储空间要求不大,很少增加和删除的情况。

    数据访问:由于数据是存储在连续空间内,所以每个数据的内存地址都是通过数据小标算出,所以可以直接访问目标数据。(这叫做“随机访问”)。比如下方,可以直接使用a[2]访问Red。
    在这里插入图片描述
    数据添加:数据添加需要移动其他数据。首先增加足够的空间,然后把已有的数据一个个移开。
    在这里插入图片描述
    在这里插入图片描述
    数据删除:反过来,如果想要输出数据Green,也是一样挨个把数据往反方向移动。
    在这里插入图片描述
    在这里插入图片描述

    二. 链表

    链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,每个元素包含两个结点,一个是存储元素的数据域 (内存空间),另一个是指向下一个结点地址的指针域。

    • 优点:数据添加和删除方便
    • 缺点:访问比较耗费时间
    • 适用场景:数据量较小,需要频繁增加,删除操作的场景

    数组和链表数据结构对比列表如下:
    在这里插入图片描述

    数据访问:因为数据都是分散存储的,所以想要访问数据,只能从第一个数据开始,顺着指针的指向逐一往下访问。
    在这里插入图片描述

    数据添加:将Blue的指针指向的位置变成Green,然后再把Green的指针指向Yellow。
    在这里插入图片描述
    数据删除:只要改变指针的指向就可以了,比如删除Yellow,只需把Green指针指向的位置从Yellow编程Red即可。

    虽然Yellow本身还存储在内存中,但是不管从哪里都无法访问这个数据,所以也就没有特意去删除它的必要了。今后需要用到Yellow所在的存储空间时,只要用新数据覆盖掉就可以了。
    在这里插入图片描述

    三. 栈

    栈也是一种数据呈线性排列的数据结构,不过在这种结构中,我们只能访问最新添加的数
    据。从栈顶放入元素的操作叫入栈,取出元素叫出栈。

    特点:后进先出(Last In First Out,简称LIFO)

    在这里插入图片描述
    在这里插入图片描述

    四. 队列

    队列中的添加和删除数据的操作分别是在两端进行的。队列可以在一端添加元素,在另一端取出元素,也就是:先进先出(First In First Out,简称FIFO)
    在这里插入图片描述
    在这里插入图片描述

    五. 哈希表

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

    一般来说,我们可以把键当作数据的标识符,把值当作数据的内容。
    在这里插入图片描述

    • 数据存储

    假设我们需要存储5个元素,首先使用哈希函数(Hash)计算Joe的键,也就是字符串"Joe"的哈希值,得到4928,然后将哈希值除以数组长度5(mod运算),求得其余数。因此,我们将Joe的数据存进数组的3号箱子中。
    在这里插入图片描述

    • 冲突

    如果两个哈希值取余的结果相同,我们称这种情况为“冲突”。假设Nell键的哈希值为6276,mod 5的结果为1。但此时1号箱已经存储了Sue的数据,可使用链表在已有的数据的后面继续存储新的数据。
    在这里插入图片描述

    • 查询

    假设最终的哈希表为:
    在这里插入图片描述
    如果要查找Ally的性别,首先算出Alley键的哈希值,然后对它进行mod运算。最终结果为3。
    在这里插入图片描述
    然而3号箱中数据的键是Joe而不是Ally。此时便需要对Joe所在的链表进行线性查找。找到了键为Ally的数据。取出其对应的值,便知道了Ally的性别为女(F)。
    在这里插入图片描述

    • 特点

    可以利用哈希函数快速访问到数组的目标数据。如果发生哈希冲突,就使用链表进行存储。

    如果数组的空间太小,使用哈希表的时候就容易发生冲突,线性查找的使用频率也会更高;反过来,如果数组的空间太大,就会出现很多空箱子,造成内存的浪费。因此,给数组设定合适的空间非常重要。

    在存储数据的过程中,如果发生冲突,可以利用链表在已有数据的后面插入新数据来解决冲突。这种方法被称为“链地址法”。除了链地址法以外,还有几种解决冲突的方法。其中,应用较为广泛的是“开放地址法”。

    六. 堆

    堆是一种图的树形结构,被用于实现“优先队列”(priority queues)。优先队列是一种数据结构,可以自由添加数据,但取出数据时要从最小值开始按顺序取出。在堆的树形结构中,各个顶点被称为“结点”(node),数据就存储在这些结点中。堆有下列特点:

    • 每个节点最多有两个子节点
    • 排列顺序必须从上到下,同一行从左到右
    • 堆中某个节点的值总是不大于或不小于其父节点的值;
    • 存放数据时,一般会把新数据放在最下面一行靠左的位置。如果最下面一行没有多余空间时,就再往下另起一行,并把数据添加到这一行的最左端。

    堆的性质:

    • 堆是一个完全二叉树
    • 堆中某个结点的值总是不大于或不小于其父结点的值;
    • 将根结点最大的堆叫做最大堆或大根堆,根结点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
    • 一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树
    • 一棵深度为 k k k且有 2 k − 1 2^k - 1 2k1个结点的二叉树称为满二叉树。也就是说除了叶子节点都有2个子节点,且所有的叶子节点都在同一层。

    在这里插入图片描述

    七. 树

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

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

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

    • 每个结点最多有两颗子结点
    • 左子树和右子树是有顺序的,次序不能颠倒
    • 即使某结点只有一个子树,也要区分左右子树

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

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

    八. 图

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

    无向图:
    在这里插入图片描述
    有向图:
    在这里插入图片描述


    参考:《我的第一本算法书》

    展开全文
  • 《算法和数据结构》题海战术篇

    万次阅读 多人点赞 2021-07-15 06:13:43
    刷了 3333 题 算法题 后的一点点经验总结 —— 题不是这么刷的!
  • 图解数据结构与算法

    万人学习 2020-07-27 10:56:16
    这部分恰好又不是突击能够解决的知识储备,所以很有必要系统地学习一下数据结构和算法了 【推荐您学习这门课程的原因】 1、图解数据结构与算法:拒绝抽象枯燥的学习,本课程采用动画演示的形式,让您在动画中掌握...
  • 数据结构基础概念篇

    万次阅读 多人点赞 2017-11-14 13:44:24
    数据结构一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。数据:所有能被输入到计算机中,且能...
  • 图解!24张图彻底弄懂九大常见数据结构

    万次阅读 多人点赞 2020-05-24 22:23:36
    数据结构想必大家都不会陌生,对于一个成熟的程序员而言,熟悉和掌握数据结构和算法也是基本功之一。数据结构本身其实不过是数据按照特点关系进行存储或者组织的集合,特殊的结构在不同的应用场景中往往会带来不...
  • 根据此书所做随笔笔记。 一、绪论 1.1、数据机构的研究内容 ...由于数据必须在计算机中处理,因此不能局限于数据本身的数学问题的研究,还必须考虑数据的物理结构,即数据在计算机中的存储结构。 1.
  • 数据结构与算法三十题,弄懂这些面试就够了!

    万次阅读 多人点赞 2019-02-01 08:30:28
    由于数据结构用来以有组织的形式存储数据,而且数据是计算机科学中最重要的实体,因此数据结构的真正价值显而易见。 无论你解决什么问题,你都必须以这种或那种方式处理数据比如员工的工资,股票价格,购物清单,...
  • 数据结构面试经典问题汇总

    万次阅读 多人点赞 2020-05-26 16:23:13
    数据结构面试经典问题汇总参考资源:基础深入补充: 参考资源: 基础 数据结构常见面试题 深入 数据结构面试题(三) 数据结构面试必问 数据结构算法常见面试考题 补充: 1.数组和链表的区别,请详细解释。 从逻辑...
  • Redis之基本数据类型及其数据结构

    万次阅读 多人点赞 2020-06-18 16:55:39
    redisObject数据结构 redisObject 是 Redis 类型系统的核心, 数据库中的每个键、值,以及 Redis 本身处理的参数, 都表示为这种数据类型。 /* * Redis 对象 */ typedef struct redisObject { // 类型 unsigned...
  • 11 Redis 节省内存的数据结构

    万次阅读 2021-12-05 19:31:09
    11 Redis 节省内存的数据结构前言一、String 类型内存开销大的原因二、计算 String 类型的内存使用量三、节省内存的数据结构四、集合类型保存单值的键值对五、二级编码方法中采用的 ID 长度规则总结 前言 需求:开发...
  • 学习数据数据结构的意义

    千次阅读 2018-12-31 14:09:05
    什么是数据结构,为什么要学习数据结构数据结构是否是一门纯数学课程?它在专业课程体系中起什么样的作用?我们要怎么才能学好数据结构?… 相信同学们在刚开始《数据结构》这门课的学习时,心里有着类似前面几个...
  • 数据结构学习心得

    千次阅读 多人点赞 2018-12-31 14:09:19
    要学好数据结构,有数据结构学习网才行! 首先,恭喜您发现了这个网站:一个神奇的学习数据结构的网站! 其次,感谢您打开这个网页阅读这篇文章,实在太感谢啦! 再次,正在激动中......哽咽了。还是让我先来...
  • 最近在学习数据结构,有必要对自己这两天的学习做一个总结,今天就来总结下,数据结构的逻辑结构 按照分类标准的不同,我们把数据结构分为逻辑机构和存储结构,今天主要讲解逻辑结构 逻辑结构:是指数据对象中的...
  • 数据结构在实际应用中非常常见,现在各种算法基本都牵涉...因此,数据在计算机存储空间的存放,决不是胡乱的,这就要求我们选择一种好的方式来存储数据,而这也是数据结构的核心内容。 数据存储 一直以来大家面对的数据
  • 数据结构与算法书籍推荐

    万次阅读 多人点赞 2019-03-16 18:49:31
    学习数据结构与算法,还是很有必要看几本相关的书籍,但根据不同基础的人,合适看的书也不一样,因此,针对不同层次、不同语言的人,推荐几本市面上口碑不错的书。 1. 入门级 针对刚入门的同学,建议不要急着去看...
  • 以下数据结构中不属于线性数据结构的是(C) A:线性表 B:队列 C:二叉树 D:栈 解释: 线性结构定义: 如果一个非空的数据结构满足下列两个条件:1、有且只有一个根节点;2、每一个节点最多有一个前驱,也最多有一...
  • 算法 + 数据结构 = 程序
  • 南通大学822数据结构
  • 为什么要学数据结构

    万次阅读 多人点赞 2019-11-19 09:45:23
    一、前言 在可视化化程序设计的今天,借助于...1) 能够熟练地选择和设计各种数据结构和算法 2) 至少要能够熟练地掌握一门程序设计语言 3) 熟知所涉及的相关应用领域的知识 其中,后两个条件比较容易实现,而第一个...
  • 数据结构1

    千次阅读 2018-04-01 20:56:40
    2-1被计算机加工的数据元素不是孤立的,它们彼此之间一般存在某种关系,通常把数据元素之间的这种关系称为 (B)规则结构集合运算2-2以下关于数据结构的说法中错误的是(A )。 数据结构相同,对应的存储结构也相同...
  • Redis的五种数据结构的底层实现原理

    万次阅读 2021-01-31 02:49:22
    Redis的五种数据结构的底层实现原理: 1、String底层实现方式:动态字符串sds 或者 long; 2、Hash底层实现方式:压缩列表ziplist 或者 字典dict; 3、List在Redis3.2之前的底层实现方式:压缩列表ziplist 或者 双向...
  • 常用八大数据结构总结及应用场景-附示例截图

    千次阅读 多人点赞 2020-08-03 21:32:42
    什么是数据结构? 官方解释:数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及他们之间的关系和操作等相关问题的学科。 大白话:数据结构就是把数据元素按照一定的关系组织起来的集合,用来组成和...
  • ... 数据结构(C语言版 第2版)课后习题答案 严蔚敏 等 编著,仅供参考,还是自己认真做了再看 ...(1)在数据结构中,从逻辑上可以把数据结构分成( C )。 A.动态结构和静态结构 B.紧凑...
  • 数据结构:图结构的实现

    万次阅读 多人点赞 2018-02-07 19:44:45
    图是一种很重要的数据结构,不解释。
  • 如何正确学习数据结构、算法这门课?

    千次阅读 多人点赞 2019-09-05 09:29:48
    你是否曾跟我一样,因为看不懂数据结构和算法,而一度怀疑是自己太笨?实际上,很多人在第一次接触这门课时,都会有这种感觉,觉得数据结构和算法很抽象,晦涩难懂,宛如天书。正是这个原因,让很多初学者对这门课...
  • 算法与数据结构入门必看(通俗易懂)

    千次阅读 多人点赞 2019-10-01 19:27:40
    算法与数据结构开篇 你真的会数据结构吗? 公司开发一个客服电话系统,小菜需要完成客户排队模块的开发,经过三次修改: 第一次:小菜使用了数据库设计了一张客户排队表,并且设置了一个自动增长的整型id字段,来...
  • 半边数据结构讲解

    万次阅读 多人点赞 2017-11-15 19:16:40
    在介绍半边数据结构之前,必须先要科普一下计算机图形学中,模型的几何表达。 对于一般的几何模型,在计算机图形学上早已有相关的数学模型来表达,而且这些表达已经标准化了。 例如对于机械行业的CAD来说,模型...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,188,633
精华内容 475,453
关键字:

下面哪个不是数据结构

数据结构 订阅