精华内容
下载资源
问答
  • 数据结构面试经典问题汇总
    万次阅读 多人点赞
    2020-05-26 16:23:13

    数据结构面试经典问题汇总

    参考资源

    基础

    1. 数据结构常见面试题

    深入

    1. 数据结构面试题(三)
    2. 数据结构面试必问
    3. 数据结构算法常见面试考题

    补充

    1.数组和链表的区别,请详细解释。
    从逻辑结构来看:
    a) 数组必须事先定义固定的长度(元素个数),不能适应数据动态地增减的情况。当数据增加时,可能超出原先定义的元素个数;当数据减少时,造成内存浪费;数组可以根据下标直接存取。
    b) 链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据项。(数组中插入、删除数据项时,需要移动其它数据项,非常繁琐)链表必须根据next指针找到下一个元素
    从内存存储来看:
    a) (静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小
    b) 链表从堆中分配空间, 自由度大但是申请管理比较麻烦
    从上面的比较可以看出,如果需要快速访问数据,很少或不插入和删除元素,就应该用数组;相反, 如果需要经常插入和删除元素就需要用链表数据结构了。

    2.排序算法有哪些?< C语言总共有多少种排序法>
    排序算法有很多,每种算法有不同的时间和空间复杂度,效率也有差别,那么针对使用上也有不同的场合。原则上说,数据结构是一门领域,跟语言没有绝对的联系,很多时候同样的算法可以用很多种语言实现。下面列一些常见的算法:插入排序,冒泡排序,选择排序,快速排序,堆排序,归并排序,基数排序,希尔排序等。

    3.怎么理解哈希表,哈希表是什么
    摘自百度:散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数

    4.请写出以下算法的时间复杂度
    冒泡排序法 插入排序法 堆排序法 二叉树排序法
    O(n^2) O(n^2) O(nlog2 n) 最差O(n2)平均O(nlog2n)
    快速排序法 希尔排序法
    最差O(n2)平均O(n
    log2n) O(nlog n)不稳定

    5.数据结构,二叉树的相关知识,开销量,为何使用二叉树等。
    在计算机科学中,二叉树是每个结点最多有两个子树的有序树。通常根的子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。
    文件系统和数据库系统一般都采用树(特别是B树)的数据结构数据,主要为排序和检索的效率。二叉树是一种最基本最典型的排序树,用于教学和研究树的特性,本身很少在实际中进行应用,因为缺点太明显了(看看教科书怎么说的)。就像冒泡排序一样,虽然因为效率问题并不实用,单不失一种教学例子的好手段。

    6.怎么判断链表是否有环?
    两个指针分别按照固定步长行走,P1一次走1布,P2一次走2布,如果链表有环,P1和P2会有相遇的时刻。(追击问题解法)

    7、简述快速排序过程
    1)选择一个基准元素,通常选择第一个元素或者最后一个元素,
    2)通过一趟排序将待排序的记录分割成独立的两部分,其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大。
    3)此时基准元素在其排好序后的正确位置
    4)然后分别对这两部分记录用同样的方法继续进行排序,直到整个序列有序。

    8、各类排序算法对比
    时间复杂度来说:
    (1)平方阶(O(n2))排序
      各类简单排序:直接插入、直接选择和冒泡排序;
    (2)线性对数阶(O(nlog2n))排序
      快速排序、堆排序和归并排序;
    说明:
    当原表有序或基本有序时,直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数,时间复杂度可降至O(n);
    而快速排序则相反,当原表基本有序时,将蜕化为冒泡排序,时间复杂度提高为O(n2);
    原表是否有序,对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。
    稳定性:
    排序算法的稳定性:若待排序的序列中,存在多个具有相同关键字的记录,经过排序,这些记录的相对次序保持不变,则称该算法是稳定的;若经排序后,记录的相对次序发生了改变,则称该算法是不稳定的。
    稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序
    不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序

    9、选择排序算法准则:
    设待排序元素的个数为n.
    1)当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。
    2)当n较大,内存空间允许,且要求稳定性:归并排序
    3)当n较小,可采用直接插入或直接选择排序。
    直接插入排序:当元素分布有序,直接插入排序将大大减少比较次数和移动记录的次数。
    直接选择排序 :元素分布有序,如果不要求稳定性,选择直接选择排序

    10、用循环比递归效率高吗?
    递归和循环两者完全可以互换。不能完全决定性地说循环地效率比递归的效率高。
    递归算法:
    优点:代码简洁、清晰,并且容易验证正确性。
    缺点:它的运行需要较多次数的函数调用,如果调用层数比较深,需要增加额外的堆栈处理(还有可能出现堆栈溢出的情况),比如参数传递需要压栈等操作,会对执行效率有一定影响。但是,对于某些问题,如果不使用递归,那将是极端难看的代码。在编译器优化后,对于多次调用的函数处理会有非常好的效率优化,效率未必低于循环。
    循环算法:
    优点:速度快,结构简单。
    缺点:并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话,最好使用循环。
    解决哈希冲突的方法
    哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。
    1) 线性探测法
    2) 平方探测法
    3) 伪随机序列法
    4) 拉链法

    11、KMP算法:
    在一个字符串中查找是否包含目标的匹配字符串。其主要思想是每趟比较过程让子串先后滑动一个合适的位置。当发生不匹配的情况时,不是右移一位,而是移动(当前匹配的长度– 当前匹配子串的部分匹配值)位。

    更多相关内容
  • 计算机考研复试面试常问问题 数据结构篇(下)

    万次阅读 多人点赞 2020-04-25 19:16:23
    计算机考研复试面试常问问题 数据结构篇(下) 使用前需知(拒绝白嫖,如果对你有帮助,你只需点个赞就行): 注意:有人在闲鱼上盗卖我的资料,而且还有很多同学买了,请各位擦亮双眼,我是整理出来免费分享给大家...

    计算机考研复试面试常问问题 数据结构篇(下)

    使用前需知(拒绝白嫖,如果对你有帮助,你只需点个赞就行):

    注意:有人在闲鱼上盗卖我的资料,而且还有很多同学买了,请各位擦亮双眼,我是整理出来免费分享给大家的!
    

    大家请多点赞和评论,这样后面的同学更容易百度到,不至于被人盗卖,我就不加水印影响大家使用了!

    第一次整理,度不好控制,有不好的地方希望大家理解,后面可能会改进,造福今年之后的同学们!
    

    需要pdf直接打印版,可在公众号"程序员宝藏"回复复试上岸获取(会持续更新)

    在复习过程中,我用心查阅并整理了在考研复试面试中可能问到的大部分问题,并分点整理了答案,可以直接理解背诵并加上自己的语言润色!极力推荐打印下来看,效率更高!

    声明:一些边边角角的没有收集,毕竟是考研面试,不是笔试,这样也能减轻大家的负担!

    此系列一共有8篇:编程语言篇**|数据结构篇|操作系统篇|组成原理篇|计算机网络篇|数据库篇|软件工程篇|计算机专业英语篇**(还未全部完成,敬请期待,你们的支持和关注是我最大的动力!)

    个人整理,不可用于商业用途,转载请注明出处。

    需要408电子书2021版,可在公众号"程序员宝藏"回复408电子书获取

    需要408初试视频2021版,可在公众号"程序员宝藏"回复408视频获取

    需要复试机试视频,可在公众号"程序员宝藏"回复机试必过获取

    加油,大家都可以上岸!!!让我们一起努力!!!


    第五章、树与二叉树


    快速唤起记忆知识框架:


    19.树与二叉树的相关概念?

    是非线性结构,其元素之间有明显的层次关系。在树的结构中,每个节点都只有一个前件称为父节点,没有前件的节点为树的根节点,简称为树的根;每个节点可以有多个后件成为节点的子节点,没有后件的节点称为叶子节点。

    在树的结构中,一个节点所拥有的子节点个数称为该节点的度,树中最大的节点的度为树的度,树的最大的层次称为树的深度

    二叉树:二叉树是另一种树形结构,其特点是每个结点至多只有两棵子树,并且二叉树的子树有左右之分,其次序不能任意颠倒。与树相似,二叉树也以递归的形式定义。二叉树是n (n >=0) 个结点的有限集合:

    1)或者为空二叉树,即n=0 。
    2)或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

    二叉树是有序树,若将其左、右子树颠倒,则成为另一棵不同的二叉树。即使树中结点只有
    一棵子树,也要区分它是左子树还是右子树

    满二叉树:满二叉树是指除了最后一层外其他节点均有两颗子树。

    完全二叉树:完全二叉树是指除了最后一层外,其他任何一层的节点数均达到最大值,且最后一层也只是在最右侧缺少节点

    二叉树的存储:二叉树可以用链式存储结构来存储,满二叉树和完全二叉树可以用顺序存储结构来存储

    二叉树的遍历:二叉树有先序遍历(根左右),中序遍历(左根右)和后续遍历(左右根);还有层次遍历,需要借助一个队列。

    三种遍历算法中,递归遍历左、右子树的顺序都是固定的,只是访问根结点的顺序不同。不管采用哪种遍历算法,每个结点都访问一次且仅访问一次,故时间复杂度都是O(n) 。在递归遍历
    中,递归工作栈的栈深恰好为树的深度,所以在最坏情况下,二叉树是有n 个结点且深度为n 的单支树,遍历算法的空间复杂度为O(n) 。


    20.如何由遍历序列构造一棵二叉树?

    1)由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树。

    在先序遍历序列中,第一个结点一定是二叉树的根结点;而在中序遍历中,根结点必然将中
    序序列分割成两个子序列,前一个子序列是根结点的左子树的中序序列,后一个子序列是根结点的右子树的中序序列。根据这两个子序列,在先序序列中找到对应的左子序列和右子序列。在先序序列中,左子序列的第一个结点是左子树的根结点,右子序列的第一个结点是右子树的根结点。如此递归地进行下去,便能唯一地确定这棵二叉树。

    2)由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树。
    因为后序序列的最后一个结点就如同先序序列的第一个结点,可以将中序序列分割成两个子
    序列,然后采用类似的方法递归地进行划分,进而得到一棵二叉树。

    3)由二叉树的层序序列和中序序列也可以唯一地确定一棵二叉树。需要注意的是,若只知道二叉树的先序序列和后序序列,则无法唯一确定一棵二叉树。


    21.线索二叉树的概念?

    对于n个结点的二叉树,在二叉链存储结构中有n+1个空链域,利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针,这些指针称为线索,加上线索的二叉树称为线索二叉树。

    这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同,线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

    **注意:**线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题,解决了二叉链表找左、右孩子困难的问题。

    二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构,使每个结点都有了唯一前驱和后继(第一个结点无前驱,最后一个结点无后继)。对于二叉树的一个结点,查找其左右子女是方便的,其前驱后继只有在遍历中得到。为了容易找到前驱和后继,有两种方法。一是在结点结构中增加向前和向后的指针,这种方法增加了存储开销,不可取;二是利用二叉树的空链指针。


    22.树的存储结构?

    1.双亲表示法:

    这种存储方式采用一组连续空间来存储每个结点,同时在每个结点中增设一个伪指针,指示
    其双亲结点在数组中的位置。

    该存储结构利用了每个结点(根结点除外)只有唯一双亲的性质,可以很快得到每个结点的
    双亲结点,但求结点的孩子时需要遍历整个结构。

    2.孩子表示法:

    孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构,此时n 个结点
    就有n 个孩子链表(叶子结点的孩子链表为空表),这种存储方式寻找子女的操作非常直接,而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。

    3.孩子兄弟表示法:

    孩子兄弟表示法又称二叉树表示法,即以二叉链表作为树的存储结构。孩子兄弟表示法使每
    个结点包括三部分内容:结点值、指向结点第一个孩子结点的指针,及指向结点下一个兄弟结点的指针(沿此域可以找到结点的所有兄弟结点)

    这种存储表示法比较灵活,其最大的优点是可以方便地实现树转换为二叉树的操作,易于查
    找结点的孩子等,但缺点是从当前结点查找其双亲结点比较麻烦。若为每个结点增设一个parent域指向其父结点,则查找结点的父结点也很方便。


    23.二叉排序树

    1.二叉排序树的定义
    二叉排序树(也称二叉查找树)或者是一棵空树,或者是具有下列特性的二叉树:

    1. 若左子树非空,则左子树上所有结点的值均小于根结点的值。
    2. 若右子树非空,则右子树上所有结点的值均大于根结点的值。
    3. 左、右子树也分别是一棵二叉排序树。
      根据二叉排序树的定义,左子树结点值<根结点值<右子树结点值,所以对二叉排序树进行中序遍历,可以得到一个递增的有序序列。

    2.二叉排序树的查找:

    二叉排序树的查找是从根节点开始的,延某个分支逐层向下比较的过程。若二叉树非空,先将给定值与根结点的关键字比较,若相等,则查找成功;若不等,如果小于根结点的关键字,则在根结点的左子树上查找,否则在根的右子树上查找。这显然是一个递归的过程。


    24.平衡二叉树

    为避免树的高度增长过快,降低二叉排序树的性能,规定在插入和删除二叉树结点时,要保证任意结点的左、右子树高度差的绝对值不超过1, 将这样的二叉树称为平衡二叉树(Balanced Binary Tree), 简称平衡树。定义结点左子树与右子树的高度差为该结点的平衡因子,则平衡二叉树结点的平衡因子的值只可能是-1 、0 或1 。因此,平衡二叉树可定义为或者是一棵空
    树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子
    树的高度差的绝对值不超过1 。


    25.哈夫曼树和哈夫曼编码:

    2.哈夫曼树的构造

    给定n 个权值分别为W1,W2…, Wn 的结点,构造哈夫曼树的算法描述如下:

    1. 将这n 个结点分别作为n 棵仅含一个结点的二叉树,构成森林F 。
    2. 构造一个新结点,从F 中选取两棵根结点权值最小的树作为新结点的左、右子树,并且将新结点的权值置为左、右子树上根结点的权值之和。
    3. 从F 中删除刚才选出的两棵树,同时将新得到的树加入F 中。
    4. 重复步骤2) 和3)'直至F 中只剩下一棵树为止。

    从上述构造过程中可以看出哈夫曼树具有如下特点:

    1. 每个初始结点最终都成为叶结点,且权值越小的结点到根结点的路径长度越大。
    2. 构造过程中共新建了n — 1 个结点(双分支结点),因此哈夫曼树的结点总数为2n -1 。
    3. 每次构造都选择2 棵树作为新结点的孩子,因此哈夫曼树中不存在度为1 的结点。

    3.哈夫曼编码:

    在数据通信中,若对每个字符用相等长度的二进制位表示,称这种编码方式为固定长度编码。
    若允许对不同字符用不等长的二进制位表示,则这种编码方式称为可变长度编码。可变长度编码比固定长度编码要好得多,其特点是对频率高的字符赋以短编码,而对频率较低的字符则赋以较长一些的编码,从而可以使字符的平均编码长度减短,起到压缩数据的效果。哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。若没有一个编码是另一个编码的前缀,则称这样的编码为前缀编码

    由哈夫曼树得到哈夫曼编码是很自然的过程。首先,将每个出现的字符当作一个独立的结点,
    其权值为它出现的频度(或次数),构造出对应的哈夫曼树。显然,所有字符结点都出现在叶结点中。我们可将字符的编码解释为从根至该字符的路径上边标记的序列,其中边标记为0 表示“转向左孩子”,标记为1 表示“转向右孩子“。


    第六章、图


    快速唤起记忆知识框架:


    26.图的一些相关定义

    这个比较基础,忘了的自己去看看把,学过离散的应该比较熟悉。

    27.图的存储结构:

    1.邻接矩阵法:

    所谓邻接矩阵存储,是指用一个一维数组存储图中顶点的信息,用一个二维数组存储图中边
    的信息(即各顶点之间的邻接关系),存储顶点之间邻接关系的二维数组称为邻接矩阵。有向图、无向图和网对应的邻接矩阵实例图如下:

    适合稠密图。

    2.邻接表法:

    当一个图为稀疏图时,使用邻接矩阵法显然要浪费大量的存储空间,而图的邻接表法结合了
    顺序存储和链式存储方法,大大减少了这种不必要的浪费。所谓邻接表,是指对图G 中的每个顶点V建立一个单链表,第i个单链表中的结点表示依附于顶点v, 的边(对于有向图则是以顶点v, 为尾的弧),这个单链表就称为顶点vi 的边表(对于有向图则称为出边表)。边表的头指针和顶点的数据信息采用顺序存储(称为顶点表),所以在邻接表中存在两种结点:顶点表结点和边表结点。

    3.十字链表法:

    十字链表法是有向图的一种链式存储结构。在十字链表中,对应于有向图中的每条弧有一个结点,对应于每个顶点也有一个结点。

    4.邻接多重表:

    邻接多重表是无向图的另一种链式存储结构。
    在邻接表中,容易求得顶点和边的各种信息,但在邻接表中求两个顶点之间是否存在边而对
    边执行删除等操作时,需要分别在两个顶点的边表中遍历,效率较低。与十字链表类似,在邻接多重表中,每条边用一个结点表示,每个顶点也用一个结点表示。


    28.图的遍历(代码请自己写)

    图的遍历是指从图中的某一顶点出发,按照某种搜索方法沿着图中的边对图中的所有顶点访
    问一次且仅访问一次。注意到树是一种特殊的图,所以树的遍历实际上也可视为一种特殊的图的遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。图的遍历比树的遍历要复杂得多,因为图的任一顶点都可能和其余的顶点相邻接,所以在访问某个顶点后,可能沿着某条路径搜索又回到该顶点上。为避免同一顶点被访问多次,在遍历图的过程中,必须记下每个已访问过的顶点,为此可以设一个辅助数组visited[] 来标记顶点是否被访问过。图的遍历算法主要有两种:广度优先搜索和深度优先搜索。

    1.广度优先搜索(Breadth-First-Search, BFS):

    类似于二叉树的层序遍历算法。基本思想是:首先访问起始顶点V, 接着由V出发,依次访问V 的各个未访问过的邻接顶点W1, W2,… Wn, 然后依次访问W1, W2,…, Wn 的所有未被访问过的邻接顶点;再从这些访问过的顶点出发,访问它们所有未被访问过的邻接顶点,直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作为初始点,重复上述过程。Dijkstra源最短路径算法和Prim 最小生成树算法也应用了类似的思想。

    2.深度优先搜索(Depth-First-Search, DFS):

    它的基本思想如下:首先访问图中某一起始顶点V, 然后由v 出发,访问与v 邻接且未被访问的任一顶点W1, 再访问与W1邻接且未被访问的任一顶点W2……重复上述过程。当不能再继续向下访问时,依次退回到最近被访问的顶点,若它还有邻接顶点未被访问过,则从该点开始继续上述搜索过程,直至图中所有顶点均被访问过为止。


    29.最小生成树和最短路径:

    这四个算法请自己去翻书或百度,这是图的比较经典的应用。

    迪杰斯特拉(dijkstra)算法:迪杰斯特拉算法是经典的单源最短路径算法,用于求某一顶点到其他顶点的最短路径,它的特点是以起始点为中心层层向外扩展,直到扩展的终点为止,迪杰斯特拉算法要求边的权值不能为负权。

    弗洛伊德(Floyd)算法:弗洛伊德算法是经典的求任意顶点之间的最短路径,其边的权值可为负权,该算法的时间复杂度为O(N3),空间复杂度为O(N2)。

    普里姆(prim)算法:用来求最小生成树,其基本思想为:从联通网络N={V,E}中某一顶点u0出发,选择与他关联的最小权值的边,将其顶点加入到顶点集S中,此后就从一个顶点在S集中,另一个顶点不在S集中的所有顶点中选择出权值最小的边,把对应顶点加入到S集中,直到所有的顶点都加入到S集中为止。

    克鲁斯卡尔(kruskal)算法:用来求最小生成树,其基本思想为:设有一个有N个顶点的联通网络N={V,E},初试时建立一个只有N个顶点,没有边的非连通图T,T中每个顶点都看作是一个联通分支,从边集E中选择出权值最小的边且该边的两个端点不在一个联通分支中,则把该边加入到T中,否则就再从新选择一条权值最小的边,直到所有的顶点都在一个联通分支中为止。

    30.关键路径:

    AOE和AOV偏理解以及手动模拟,也自己去看吧。


    第七章、查找


    快速唤起记忆知识框架:


    31.对各种查找方法的概括?

    查找分为静态查找表和动态查找表;静态查找表包括:顺序查找、折半查找、分块查找;动态查找包括:二叉排序树和平衡二叉树。

    (1)顺序查找:把待查关键字key放入哨兵位置(i=0),再从后往前依次把表中元素和key比较,如果返回值为0则查找失败,表中没有这个key值,如果返回值为元素的位置i(i!=0)则查找成功,设置哨兵的位置是为了加快执行速度。他的时间效率为O(n),其特点是:结构简单,对顺序结构和连式结构都适用,但是查找效率太低。

    (2)折半查找:要求查找表为顺序存储结构并且有序,若关键字在表中则返回关键字的位置,若关键字不在表中时停止查找的典型标志是:查找范围的上界<=查找范围的下界。

    (3)分块查找:先把查找表分为若干子表,要求每个子表的元素都要比他后面的子表的元素小,也就是保证块间是有序的(但是子表内不一定有序),把各子表中的最大关键字构成一张索引表,表中还包含各子表的起始地址。他的特点是:块间有序,块内无序,查找时块间进行索引查找,块内进行顺序查找。

    (4)二叉排序树:二叉排序树的定义为:或者是一棵空树,或者是一棵具有如下特点的树:如果该树有左子树,则其左子树的所有节点值小于根的值;若该树有右子树,则其右子树的所有节点值均大于根的值;其左右子树也分别为二叉排序树。在查找时可以进行动态的插入,插入节点要符合二叉排序树的定义,这也是动态查找和静态查找的区别,静态查找不能进行动态插入。

    (5)平衡二叉树:平衡二叉树又称为AVL树,它或者是一棵空树或者具有如下特点:他的左子树和右子树的高度差的绝对值不能大于1,且他的左右子树也都是平衡二叉树。

    平衡因子:是指左子树的高度减去右子树的高度,它的值只能为1,0,-1

    如果再一个平衡二叉树中插入一个节点可能造成失衡,这时就要进行树结构的调整,即平衡旋转。包括4中情况:在左子树的左子树上插入节点时向右进行单向旋转;在右子树的右子树上插入节点时向左进行单向旋转;在左子树的右子树插入节点时先向左旋转再向右旋转;在右子树的左子树插入节点时先向右旋转再向左旋转。

    32.B树和B+树:

    1.B 树,又称多路平衡查找树, B 树中所有结点的孩子个数的最大值称为B 树的阶,通常用m
    表示。一棵m 阶B 树或为空树,或为满足如下特性的m 叉树:

    1. 树中每个结点至多有m 棵子树,即至多含有m-1 个关键字。
    2. 若根结点不是终端结点,则至少有两棵子树。
    3. 除根结点外的所有非叶结点至少有「m/2] 棵子树,即至少含有「m/2]- 1 个关键字。
    4. 所有的叶结点都出现在同一层次上,并且不带信息(可以视为外部结点或类似千折半查找判定树的查找失败结点,实际上这些结点不存在,指向这些结点的指针为空)。

    B 树是所有结点的平衡因子均等于0 的多路平衡查找树。

    2.B+树是应数据库所需而出现的一种B 树的变形树。

    一棵m 阶的B+树需满足下列条件:

    1. 每个分支结点最多有m 棵子树(孩子结点)。
    2. 非叶根结点至少有两棵子树,其他每个分支结点至少有「m/2]棵子树。
    3. 结点的子树个数与关键字个数相等。
    4. 所有叶结点包含全部关键字及指向相应记录的指针,叶结点中将关键字按大小顺序排列,
      并且相邻叶结点按大小顺序相互链接起来。
    5. 所有分支结点(可视为索引的索引)中仅包含它的各个子结点(即下一级的索引块)中
      关键字的最大值及指向其子结点的指针。

    m 阶的B+树与m 阶的B 树的主要差异如下:

    1. 在B+树中,具有n 个关键字的结点只含有n 棵子树,即每个关键字对应一棵子树;而在
      B 树中,具有n 个关键字的结点含有n+1棵子树。
    2. 在B+树中,每个结点(非根内部结点)的关键字个数n 的范围是「m/2]<=n<= m (根结点:
      1<=n<=m); 在B 树中,每个结点(非根内部结点)的关键字个数n 的范围是「m/2]-1<=n<=
      m-1 。
    3. 在B+树中,叶结点包含信息,所有非叶结点仅起索引作用,非叶结点中的每个索引项只
      含有对应子树的最大关键字和指向该子树的指针,不含有该关键字对应记录的存储地址。
    4. 在B+树中,叶结点包含了全部关键字,即在非叶结点中出现的关键字也会出现在叶结点
      中;而在B 树中,叶结点包含的关键字和其他结点包含的关键字是不重复的。

    32.哈希表的概念、哈希函数的构造方法、哈希冲突的解决办法?

    哈希表又称为散列表,是根据关键字码的值直接进行访问的数据结构,即它通过把关键码的值映射到表中的一个位置以加快查找速度,其中映射函数叫做散列函数,存放记录的数组叫做散列表。

    哈希函数的构造方法包括:直接定址法,除留余数法,数字分析法,平方取中法,折叠法,随机数法

    (1)直接定址法:取关键字的某个线性函数值作为散列地址,H(key)=a*key+b。

    (2)除留余数法:取关键字对p取余的值作为散列地址,其中p<m,即H(key)=key%p (p<m)。

    (3)数字分析法:当关键字的位数大于地址的位数,对关键字的各位分布进行分析,选出分布均匀的任意几位作为散列的地址,适用于所有关键字都已知的情况。

    (4)平方取中法:对关键字求平方,再取结果中的中间几位作为散列地址。

    (5)折叠法:将关键字分为位数相同的几部分,然后取这几部分的叠加和作为散列地址。适用于关键字位数较多,且关键字中每一位上数字分布大致均匀。

    (6)随机数法:选择一个随机函数,把关键字的随机函数值作为散列地址。适合于关键字的长度不相同时。

    哈希冲突的解决方法包括:开放定址法和拉链法,当冲突发生时,使用某种探测技术形成一个探测序列,然后沿此序列逐个单单元查找,直到找到该关键字或者碰到一个开放的地址为止,探测到开放的地址表明该表中没有此关键字,若要插入,则探测到开放地址时可将新节点插入该地址单元。其中开放定址法包括:线性探查法,二次探查法,双重散列法

    (1)线性探查法:基本思想,探查时从地址d开始,首先探查T[d],在探查T[d+1]…直到查到T[m-1],此后循环到T[0],T[1]…直到探测到T[d-1]为止。

    (2)二次探查法:基本思想,探查时从地址d开始,首先探查T[d],再探查T[d+12],T[d+22]…等,直到探查到有空余地址或者探查到T[d-1]为止,缺点是无法探查到整个散列空间。

    (3)双重散列法:基本思想,使用两个散列函数来确定地址,探查时从地址d开始,首先探查T[d],再探查T[d+h1(d)],T[d+2*h1(d)]…

    链接法:将所有关键字为同义词的节点链接在同一个单链表中,若选定的散列表长度为m,则可将散列表定义为一个由m个头指针组成的指针数组,凡是散列地址为i的节点均插入到头指针为i的单链表中。


    第八章、排序


    快速唤起记忆知识框架:


    33.对各种内部排序的概括与总结?

    排序:是指把一个任意元素的序列排列成一个按关键字key有序的序列。内部排序包括:插入排序、选择排序、交换排序、归并排序、基数排序。其中插入排序包括:直接插入排序、折半插入排序、希尔排序;选择排序包括:简单选择排序,堆排序;交换排序包括:冒泡排序、快速排序。

    (1)直接插入排序(稳定):基本思想为:将序列分为有序部分和无序部分,从无序部分依次选择元素与有序部分比较找到合适的位置,将原来的元素往后移,将元素插入到相应位置上。时间复杂度为:O(n^2),空间复杂度为O(1)

    (2)折半插入排序(稳定):基本思想为:设置三个变量low high mid,令mid=(low+high)/2,若a[mid]>key,则令high=mid-1,否则令low=mid+1,直到low>high时停止循环,对序列中的每个元素做以上处理,找到合适位置将其他元素后移进行插入。他的比较次数为O(nlog2n),但是因为要后移,因此时间复杂度为O(n^2),空间复杂度为O(1)。 优点是:比较次数大大减少。

    (3)希尔排序(不稳定):基本思想为:先将序列分为若干个子序列,对各子序列进行直接插入排序,等到序列基本有序时再对整个序列进行一次直接插入排序。优点是:让关键字值小的元素能够很快移动到前面,且序列基本有序时进行直接插入排序时间效率会提升很多,空间复杂度为O(1)。

    (4)简单选择排序(不稳定):基本思想为:将序列分为2部分,每经过一趟就在无序部分找到一个最小值然后与无序部分的第一个元素交换位置。优点是:实现起来特别简单,缺点是:每一趟只能确定一个元素的位置,时间效率低。时间复杂度为O(n^2),空间复杂度为O(1)。

    (5)堆排序(不稳定):设有一个任意序列,k1,k2,…,kn,当满足下面特点时称之为堆:让此序列排列成完全二叉树,该树具有以下特点,该树中任意节点均大于或小于其左右孩子,此树的根节点为最大值或者最小值。优点是:对大文件效率明显提高,但对小文件效率不明显。时间复杂度为O(nlog2n),空间复杂度为O(1)。

    (6)冒泡排序(稳定):基本思路为:每一趟都将元素进行两两比较,并且按照“前小后大”的规则进行交换。优点是:每一趟不仅能找到一个最大的元素放到序列后面,而且还把其他元素理顺,如果下一趟排序没有发生交换则可以提前结束排序。时间复杂度为O(n^2),空间复杂度为O(1)。

    (7)快速排序(不稳定):基本思路为:在序列中任意选择一个元素作为中心,比它大的元素一律向后移动,比它小的元素一律向前移动,形成左右两个子序列,再把子序列按上述操作进行调整,直到所有的子序列中都只有一个元素时序列即为有序。优点是:每一趟不仅能确定一个元素,时间效率较高。时间复杂度为O(nlog2n),空间复杂度为O(log2n).

    (8)归并排序(稳定):基本思想为:把两个或者两个以上的有序表合并成一个新的有序表。时间复杂度为O(nlogn),空间复杂度和待排序的元素个数相同。

    (9)基数排序:时间复杂度为:对于n个记录进行链式基数排序的时间复杂度为O(d(n+rd)),其中每一趟分配的时间复杂度为O(n),回收的时间复杂度为O(rd)。

    各种排序的总结表格如下:

    直接插入排序、冒泡排序和简单选择排序是基本的排序方法,它们主要用于元素个数n不是很大(n < 10000) 的情形。

    对于中等规模的元素序列(n <=1000), 希尔排序是一种很好的选择。

    对于元素个数n 很大的情况,可以采用快排、堆排序、归并排序或基数排序,其中快排和堆排序都是不稳定的,而归并排序和基数排序是稳定的排序算法。

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

    相似文章推荐:


    零. 总览

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

    一. 数组

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

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

    数据访问:由于数据是存储在连续空间内,所以每个数据的内存地址都是通过数据小标算出,所以可以直接访问目标数据。(这叫做“随机访问”)。比如下方,可以直接使用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-29 12:36:10
    数据结构 1.1 数据结构概述 数据结构是计算机存储、组织数据的方式;通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构的优良将直接影响着我们程序的性能;常用的数据结构有:数组(Array)...

    数据结构

    1.1 数据结构概述

    数据结构是计算机存储、组织数据的方式;通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构的优良将直接影响着我们程序的性能;常用的数据结构有:数组(Array)、栈(Stack)、队列(Queue)、链表(Linked List)、树(Tree)、图(Graph)、堆(Heap)、散列表(Hash)等;

    在这里插入图片描述

    1.2 数据结构的分类

    1.2.1 排列方式

    1)集合

    集合:数据结构中的元素之间除了“同属一个集合” 的相互关系外,别无其他关系;

    在这里插入图片描述

    2)线性结构

    线性结构:数据结构中的元素存在一对一的相互关系;

    在这里插入图片描述

    3)树形结构

    树形结构:数据结构中的元素存在一对多的相互关系;

    在这里插入图片描述

    4)图形结构

    图形结构:数据结构中的元素存在多对多的相互关系;

    在这里插入图片描述

    1.2.2 逻辑结构

    数据结构按逻辑上划分为线性结构非线性结构

    • 线性结构有且仅有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前驱和一个直接后继。

    典型的线性表有:链表、栈和队列。它们共同的特点就是数据之间的线性关系,除了头结点和尾结点之外,每个结点都有唯一的前驱和唯一的后继,也就是所谓的一对一的关系。

    • 非线性结构:对应于线性结构,非线性结构也就是每个结点可以有不止一个直接前驱和直接后继。常见的非线性结构包括:树、图等。

    1.3 数据结构的实现

    1.2.1 数组

    • 数组(Array):数组是有序元素的序列,在内存中的分配是连续的,数组会为存储的元素都分配一个下标(索引),此下标是一个自增连续的,访问数组中的元素通过下标进行访问;数组下标从0开始访问;

    • 数组的优点是:查询速度快;

    在这里插入图片描述

    • 数组的缺点是:删除增加、删除慢;由于数组为每个元素都分配了索引且索引是自增连续的,因此一但删除或者新增了某个元素时需要调整后面的所有元素的索引;

    新增一个元素40到3索引下标位置:

    在这里插入图片描述

    删除2索引元素:

    在这里插入图片描述

    总结:数组查询快,增删慢,适用于频繁查询,增删较少的情况;

    1.2.2 链表

    • 链表(Linked List):链表是由一系列节点Node(也可称元素)组成,数据元素的逻辑顺序是通过链表的指针地址实现,通常情况下,每个节点包含两个部分,一个用于存储元素的内存地址,名叫数据域,另一个则指向下一个相邻节点地址的指针,名叫指针域;根据链表的指向不同可分为单向链表、双向链表、循环链表等;我们本章介绍的是单向链表,也是所有链表中最常见、最简单的链表;

    链表的节点(Node):

    在这里插入图片描述

    完整的链表:

    在这里插入图片描述

    • 链表的优点:新增节点、删除节点快;

    在链表中新增一个元素:

    在这里插入图片描述

    在单向链表中,新增一个元素最多只会影响上一个节点,比在数组中的新增效率要高的多;

    在链表中删除一个元素:

    在这里插入图片描述

    • 链表的缺点:
      • 1)查询速度慢,查询从头部开始一直查询到尾部,如果元素刚好是在最尾部那么查询效率势必非常低;
      • 2)链表像对于数组多了一个指针域的开销,内存相对占用会比较大;

    总结:数据量较小,需要频繁增加,删除操作的场景,查询操作相对较少;

    1.2.3 栈

    • 栈(Stack):是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作。 栈的特点是:先进后出从栈顶放入元素的操作叫入栈(压栈),取出元素叫出栈(弹栈)。

    入栈操作:

    在这里插入图片描述

    出栈操作:

    在这里插入图片描述

    栈的特点:先进后出,Java中的栈内存就是一个栈的数据结构,先调用的方法要等到后调用的方法结束才会弹栈(出栈);

    1.2.4 队列

    • 队列(Queue):队列与栈一样,也是一种线性表,其限制是仅允许在表的一端进行插入,而在表的另一端进行删除。队列的特点是先进先出,从一端放入元素的操作称为入队,取出元素为出队;

    在这里插入图片描述

    队列的特点:先进先出;

    1.2.5 树

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

    • 1)每个节点有0个或多个子节点;
    • 2)没有父节点的节点称为根节点;
    • 3)每一个非根节点有且只有一个父节点;
    • 4)除了根节点外,每个子节点可以分为多个不相交的子树;
    • 5)右子树永远比左子树大,读取顺序从左到右;

    树的分类有非常多种,平衡二叉树(AVL)、红黑树RBL(R-B Tree)、B树(B-Tree)、B+树(B+Tree)等,但最早都是由二叉树演变过去的;

    二叉树的特点:每个结点最多有两颗子树

    在这里插入图片描述

    1.2.6 堆

    • 堆(Heap):堆可以看做是一颗用数组实现的二叉树,所以它没有使用父指针或者子指针。堆根据“堆属性”来排序,“堆属性”决定了树中节点的位置。

    在这里插入图片描述

    堆的特性:如果一个结点的位置为k,则它的父结点的位置为[k/2],而它的两个子结点的位置则分别为2k和2k+1。这样,在不使用指针的情况下,我们也可以通过计算数组的索引在树中上下移动:从arr[k]向上一层,就令k等于k/2,向下一层就令k等于2k或2k+1。

    堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆;

    (ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1)满足前者的表达式的成为小顶堆(小根堆),满足后者表达式的为大顶堆(大根堆),很明显我们上面画的堆数据结构是一个大根堆;

    大小根堆数据结构图:

    在这里插入图片描述

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

    1.2.7 散列表

    • 散列表(Hash),也叫哈希表,是根据键和值 (key和value) 直接进行访问的数据结构,通过key和value来映射到集合中的一个位置,这样就可以很快找到集合中的对应元素。它利用数组支持按照下标访问的特性,所以散列表其实是数组的一种扩展,由数组演化而来。

    散列表首先需要根据key来计算数据存储的位置,也就是数组索引的下标;

    • HashValue=hash(key)

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

    在这里插入图片描述

    在散列表中,左边是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。

    1.2.8 图

    • 图(Graph):图是一系列顶点(元素)的集合,这些顶点通过一系列边连接起来组成图这种数据结构。顶点用圆圈表示,边就是这些圆圈之间的连线。顶点之间通过边连接。

    图分为有向图和无向图:

    • 有向图:边不仅连接两个顶点,并且具有方向;
    • 无向图:边仅仅连接两个顶点,没有其他含义;

    在这里插入图片描述

    例如,我们可以把图这种数据结构看做是一张地图:

    地图中的城市我们看做是顶点,高铁线路看做是边;很显然,我们的地图是一种无向图,以长沙到上海为例,经过的城市有长沙、南昌、杭州、上海等地;那么从上海也可以按照原有的路线进行返回;

    在这里插入图片描述

    实现了图这种数据结构之后我们可以在此数据结构上做一些复杂的算法计算,如广度优先搜索算法、深度优先搜索算法等;

    • 广度搜索:搜索到一个顶点时,先将此顶点的所有子顶点全部搜索完毕,再进行下一个子顶点的子顶点搜索;

    在这里插入图片描述

    例如上图:以武汉为例进行广度搜索,

    1)首先搜索合肥、南昌、长沙等城市;

    2)通过合肥搜索到南京;

    3)再通过南昌搜索到杭州、福州,

    4)最终通过南京搜索到上海;完成图的遍历搜索;

    不通过南京搜索到杭州是因为已经通过南昌搜索到杭州了,不需要再次搜索;

    • 深度搜索:搜索到一个顶点时,先将此顶点某个子顶点搜索到底部(子顶点的子顶点的子顶点…),然后回到上一级,继续搜索第二个子顶点一直搜索到底部;

    在这里插入图片描述

    例如上图:以武汉为例进行深度搜索,

    1)首先搜索合肥、南京、上海等城市;

    2)回到武汉,进行第二子顶点的搜索,搜索南昌、杭州等地;

    3)回到南昌,搜索福州;

    4)回到武汉,搜索长沙;

    图是一种比较复杂的数据结构,在存储数据上有着比较复杂和高效的算法,分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构。我们本次了解到这里即可;

    记得点赞!!!

    展开全文
  • 计算机考研复试面试常问问题 数据结构篇(上)

    万次阅读 多人点赞 2020-04-23 17:21:14
    计算机考研复试面试常问问题 数据结构篇(上) 使用前需知(拒绝白嫖,如果对你有帮助,你只需点个赞就行): 需要pdf直接打印版,可在公众号"程序员宝藏"回复复试上岸获取(会持续更新) 在复习过程中,我用心...
  • 数据结构与算法必知基础知识

    千次阅读 多人点赞 2021-01-06 22:58:12
    数据结构与算法是程序员内功体现的重要标准之一,且数据结构也应用在各个方面,业界更有程序=数据结构+算法这个等式存在。各个中间件开发者,架构师他们都在努力的优化中间件、项目结构以及算法提高运行效率和降低...
  • 数据结构知识整理

    万次阅读 多人点赞 2018-07-30 18:50:47
    1.数据结构:是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等的学科。 2.数据结构涵盖的内容: 3.基本概念和术语: 数据:对客观事物的符号表示,在计算机科学中是指所有能...
  • 数据结构面试题以及答案整理

    千次阅读 多人点赞 2021-07-17 15:31:34
    一、什么是数据结构数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。结构包括逻辑结构和物理结构。 数据的逻辑结构包括4种 (1)集合:数据元素之间除了有...
  • 常用八大数据结构总结及应用场景-附示例截图

    千次阅读 多人点赞 2020-08-03 21:32:42
    官方解释:数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及他们之间的关系和操作等相关问题的学科。 大白话:数据结构就是把数据元素按照一定的关系组织起来的集合,用来组成和存储数据。 逻辑...
  • 数据结构基础概念篇

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

    千次阅读 多人点赞 2018-07-12 17:09:00
    转载请标明出处: ...本文出自:【openXu的博客】 1、什么是数据结构   数据结构主要学习用计算机实现数据组织和数据处理的方法;...  一个好的程序无非是选择一个合理的数据结构和好的算法,而好的算法...
  • 数据结构数据结构三要素

    千次阅读 2020-07-01 13:45:24
    典型数据结构与其逻辑结构的对应关系如下: 对于线性表、集合、树、图这四种典型数据结构,他们分别有以下特点: 集合结构:数据元素之间只存在 “同属于一个集合”的关系。 线性结构:数据元素之间只存在“一...
  • 数据结构与算法中的经典算法

    万次阅读 多人点赞 2018-07-19 21:47:12
    数据结构与算法之经典算法 常见数据结构与算法整理总结(上) 常见数据结构与算法整理总结(下) 二、针对性参考 1) 排序 数据结构与算法之经典排序 2)二叉树 数据结构与算法之二叉树+遍历+哈夫曼树 ...
  • 数据结构算法常见面试考题

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

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

    万次阅读 2017-09-28 11:39:19
    队列和栈作为一种最简单最基本的常用数据结构,可以说在许多方面都应用广泛。在程序运行时,他们可以保存程序运行路径中各个点的信息,以便用于回溯操作或其他需要访问已经访问过的节点信息的操作。这里对队列的特点...
  • Java数据结构与算法入门

    万次阅读 多人点赞 2018-04-29 11:53:50
    第一部分:Java数据结构要理解Java数据结构,必须能清楚何为数据结构数据结构:Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些数据之间有一定的关系。而各数据元素之间的相互关系,又...
  • C++实现字典数据结构

    千次阅读 2019-09-23 20:33:36
    本文使用C++构建了一个字典数据结构,未使用STL,实现了一个学生成绩录入系统,进而实现了字典数据对象的如下功能: 新建一个字典; 检查字典非空; 得到字典的数据长度; 插入一个数对; 按学生姓名删除对应的字典...
  • 算法 + 数据结构 = 程序
  • 《算法和数据结构》LeetCode 篇

    千次阅读 多人点赞 2021-12-20 05:34:43
    《画解数据结构》堆 3)线段树   线段树用到了分治思想,典型问题是区间最值。属于较难内容,面试考点也较少。建议刷 10 题掌握其思想。 4)AVL 树 和 红黑树   平衡二叉树主要有 红黑树 和 AVL 树。STL 中的...
  • 本书主教材按照面向对象程序设计的思想,根据作者多年的教学积累,系统地介绍各类数据结构的功能、表示和实现,对比各类数据结构适用的应用环境;结合实际问题展示算法设计的一般性模式与方法、算法实现的主流技巧,...
  • 数据结构PDF下载

    万次阅读 2019-03-04 09:55:20
    数据结构 算法实现及解析 C语言[第二版] 高一凡 pdf文字版http://qunying.jb51.net:81/201303/books/sjjg_sfszjjx_jb51net.rar 大话数据结构 中文 PDF清晰扫描版 完整版 [36M]...C# 语言描述 数据结构 pdf版ht...
  • 数据结构——数据结构的三大结构

    千次阅读 2019-09-02 22:53:14
    数据结构研究变量的管理方式,算法研究解决特定问题的方法。 数据结构分三个层次:逻辑结构(抽象层)、物理结构(结构层)、运算结构(实现层)。 1.1 数据结构的逻辑结构 逻辑结构指人对数据之间关系的...
  • 我叫《数据结构与算法》,是计算机世界的四大基石之一。 想来我应该是惹人怜爱的吧(认真脸),因为我仿佛听到了无数个初入计算机世界的同学的呐喊声(????)。 我作为一门简单学科,看到有很多的在半途弃我而去,我...
  • 数据结构数据结构描述

    千次阅读 2019-05-10 22:49:12
    典型数据结构 集合:其数据元素之间没有需要关注的明确关系,之是把一组数据元素包装成为一个整体。 序列:其数据元素之间有一种明确的先后关系(是有顺序的)。序列结构及其变形如下,其特点是每个元素最多只有...
  • 常见数据结构应用场景

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

    千次阅读 多人点赞 2019-08-20 11:06:18
    树是一种结合了另外两种数据结构的优点的结构 一种是顺序表,树结构的查询速度和有序数组一样快 一种是链表,树结构的插入数据和删除数据速度和链表一样快 在树的操作中,大量运用了递归的原理 1.二叉树的...
  • 常见数据结构与算法整理总结(上)

    万次阅读 多人点赞 2018-08-06 18:23:14
    数据结构是以某种形式将数据组织在一起的集合,它不仅存储数据,还支持访问和处理数据的操作。算法是为求解一个问题需要遵循的、被清楚指定的简单指令的集合。下面是自己整理的常用数据结构与算法相关内容,如有错误...
  • 数据结构-栈(Stack)

    万次阅读 2019-11-14 17:55:34
    栈是一种后进先出的数据结构(Last In First Out–LIFO),在计算机的世界里,栈拥有着不可思议的作用。 二、栈的应用 2.1 在word或者其他编辑器中,当我们输入一些文本内容的时候,就用到了栈。(举例:”沉迷学习...
  • 数据结构:栈和队列(Stack & Queue)【详解】

    万次阅读 多人点赞 2021-02-18 19:52:33
    栈和队列知识框架 栈 一、栈的基本概念 1、栈的定义 ...栈又称为先进先出(Last In First Out)的线性表,简称LIFO结构 2、栈的基本操作 InitStack(&S):初始化一个空栈S。 StackEmpty(S):

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 493,831
精华内容 197,532
关键字:

数据结构典型问题

数据结构 订阅