数据结构刷题笔记

这篇具有很好参考价值的文章主要介绍了数据结构刷题笔记。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

数据结构刷题笔记

一、绪论

  1. 通常从四个方面评价算法的质量:可读性正确性健壮性高效性
  2. 某算法时间复杂度为O(n*n),说明算法执行时间与n *n成正比,其中n是问题规模
  3. 逻辑结构主要从数据元素之间的相邻关系考虑。用B=(D,R)表示,其中B表示一种逻辑数据结构,D是数据元素的集合,R是所有关系的集合
  4. 若某元素没有前驱节点,称其为开始元素,若没有后继节点,称其为终端元素
  5. 逻辑结构的类型:集合线性结构树形结构图形结构
  6. 存储结构的类型:顺序存储结构链式存储结构索引存储结构哈希(或散列)存储结构
  7. 数据运算包括功能描述和功能实现

二、线性表

  1. 线性表是一个元素个数大于等于0的有限序列
  2. 双向链表搜索指定元素从两个方向搜索和从一个方向搜索的时间复杂度相同(遍历一个节点所需时间不变)
  3. 带头结点的单链表为空的判断条件:Head->next = nullptr
  4. 带头结点的循环单链表为空的判断条件:Head->next = Head
  5. 无论是链表还是数组,若使用new或malloc创建则统一存入堆中,若作为局部变量则存入栈中
  6. 链表插入或删除任意元素的时间复杂度也为O(n),因为需要遍历链表找到所指定的位置
  7. 从一个具有n个节点的单链表中查找指定节点,平均比较次数为 (n+1)/2
  8. 在对单链表进行头插法时,注意单链表有头指针还是头结点
  9. 链表中的“已知节点”指的是可以直接调用其指针的节点

三、栈和队列

  1. 栈和队列的共同点:只允许在端点处插入和删除元素
  2. 栈和队列都是线性表
  3. 用链式存储结构存储的队列,在插入新节点时可能要同时修改队首和队尾的指针(循环队列)
  4. 顺序循环队列Q[0:n-1]中,队列头指针为F,队尾指针为R,则循环队列中元素的个数是(R-F+n)%n
  5. 不是每一种数据结构都有查找功能(比如栈和队列)
  6. 链栈中不含不存储数据的头结点,栈顶指针直接指向第一个元素所在节点
  7. hanoi的搬运次数:2 * hanoi (n-1) + 1 且 hanoi(1) = 1
  8. 用链式存储方式存储的队列,在进行出队运算时删除尾指针所指节点,在进行入队操作时使用头插法
  9. 用链式存储方式存储的队列,如果没有头结点,则在进行出队操作时可能需要同时修改头指针和尾指针,因为当没有虚拟头结点的链表中仅有一个节点时,头指针和尾指针同时指向该节点

四、串

  1. void strcpy(dest, model) 有两个参数,是两个指向char数组首地址的指针,前为目标后为模板,函数执行复制操作
  2. 使用strlen可得到字符串中包括空格和标点符号在内的字符数。
  3. 使用sizeof运算符,得到的数会更大,因为它会把字符串末尾不可见的空字符\0也计算在内。
  4. 子串定义:串中任意个连续的字符组成的子序列
  5. 子序列定义:子序列则不要求连续,即可以是离散截取的,但字符之间的相对位置关系不变
  6. KMP算法时间复杂度为O(m+n)

五、数组和稀疏矩阵

  1. 存取数组元素 != 插入,数组存取元素的时间复杂度为O(1)
  2. 数组中元素的起始地址 = 上一元素地址的结束
  3. 数组的首地址 = 数组中首个元素的起始地址 = a[0][0] 或 a[1][1]
  4. 对称矩阵一般存下三角(看题中具体问哪一部分的元素位置)
  5. 稀疏矩阵的压缩存储方法有:十字链表、三元组

六、递归

  1. 递归先序遍历一个节点为n,深度为d的二叉树,需要栈空间的大小为O(d)

七、树和二叉树

  1. 树的高度等于树中最深节点的深度
  2. 树的深度等于树的高度
  3. 节点的深度等于节点的层次,根节点在第一层

八、图

  1. 拓扑图:即有向无环图,因为拓扑排序中每个顶点只出现一次,而且对于图中的任何一条边,起点必须在终点之前。
  2. dfs和bfs一般默认为优先选择序号较的节点
  3. 图的dfs类似于二叉树的先序遍历,bfs类似于二叉树的层序遍历
  4. 最小生成树不唯一(图中有权值相同的边),最小生成树的代价唯一
  5. 对一个强连通图调用一次广度优先遍历算法便可访问所有的顶点
  6. 连通: 若节点i,j之间存在路径,则称两节点连通,连通这一概念仅在有向图中出现
  7. 连通图:无向图中任意两个节点间均连通,则称该图为连通图
  8. 强连通图:有向图中任意两个节点之间均存在路径,则称该图是强连通图
  9. Prim算法:用于从指定节点开始生成一个最小生成树,适用于稠密图
  10. Kruskal算法:用于生成一个最小生成树,不需要指定初始节点,适用于稀疏图
  11. 关键路径并不唯一,当有多条关键路径存在时,其中一条关键路径上的关键活动时间缩短,只能导致本条关键路径变成非关键路径,而无法缩短整个工期
  12. p(p > 2) 个顶点 p 条边的连通图中至少有3个生成树,因为该图中必有一环,环的边数最小为3,最大为p,生成子树的过程就是拆环的过程
  13. 带权有向图中有权值相同的边,最小生成树也可能唯一
  14. 无向图和有向图的总度和均为偶数,入度和与出度和可能为奇数

九、查找

  1. 中序遍历二叉有序树可得递增有序序列
  2. hash函数可以把字符串等任意长度的输入映射成固定长度的整数,也就是哈希值,不同的信息产生相同的哈希值叫哈希冲突
  3. Hash碰撞的解决办法:
    • 双重散列(使用一个散列函数计算初始位置,使用另一个散列函数计算步长)
    • 多重散列(使用一个散列函数计算初始位置,使用其余多个散列函数同时计算出多个可能的地址,然后选择其中空余的地址存入数据)
    • 拉链法(也称链地址法,哈希表中包含若干槽,每一个槽都是一个链表(不包含数据)的头节点)
    • 线性探测
    • 二次探测(使用二次方程确定步长)
  4. 哈希表(Hash Table)是一种根据关键字直接访问内存存储位置的数据结构
  5. 哈希查找次数 != 哈希探测次数 哈希查找次数还包含对计算所得初始位置的查找,而哈希探测次数只包含在发生哈希冲突后重新探测的次数
  6. 哈希查找次数:指将数据进行比较的总次数,在拉链法中头结点不存储数据,故不计入查找次数
  7. 红黑树查找的时间会比AVL树慢一点,因为最大高度为2logn,添加和删除操作比AVL树要快一些,因为红黑树是黑节点平衡的二叉树,所有不平衡必然在三次旋转以内解决。
  8. 红黑树和AVL树的查找、删除、插入操作的时间复杂度均为O(logn)
  9. 分块查找中若线性表一共有N个元素,则每一个块内最佳节点个数为N1/2,此时平均查找长度为N1/2+1
  10. 折半查找在最坏情况下的查找次数为[logn] + 1,注意logn向下取整

文章来源地址https://www.toymoban.com/news/detail-824677.html

到了这里,关于数据结构刷题笔记的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构学习笔记——图的遍历算法(深度优先搜索和广度优先搜索)

    图的遍历指从图中某一顶点出发(任意一个顶点都可以作为访问的起始顶点),按照某种遍历方法,对图中所有的顶点访问一次且只访问一次。图与树不一样,其中一个顶点可能与多个顶点相连,所以需记录已访问过的顶点,当访问一个顶点后,考虑如何选取下一个要访问的

    2024年02月05日
    浏览(50)
  • 数据结构与算法之美学习笔记:48 | B+树:MySQL数据库索引是如何实现的?

    本节课程思维导图: 作为一个软件开发工程师,你对数据库肯定再熟悉不过了。作为主流的数据存储系统,它在我们的业务开发中,有着举足轻重的地位。在工作中,为了加速数据库中数据的查找速度,我们常用的处理思路是,对表中数据创建索引。那你是否思考过,数据库

    2024年01月16日
    浏览(76)
  • java数据结构与算法刷题-----LeetCode283. 移动零

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 双指针,用right和left两个指针,将非0元素,全部按顺序换到数组前面。left指向左边非0元素应该插入的位置,right找到非

    2024年01月21日
    浏览(47)
  • java数据结构与算法刷题-----LeetCode566. 重塑矩阵

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 代码:时间复杂度O(r*c).除题目要求外,算法本身没有需要额外空间,空间复杂度O(1) 从0开始算,一个3列n行矩阵中,每行就有3个元

    2024年01月21日
    浏览(43)
  • java数据结构与算法刷题-----LeetCode287. 寻找重复数

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 弗洛伊德判圈法,也就是快慢指针判圈法(龟兔赛跑算法),此算法分为两个步骤 判断是否有环,并得到快慢指针相遇

    2024年01月24日
    浏览(38)
  • java数据结构与算法刷题-----LeetCode766. 托普利茨矩阵

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 这道题只要换一种理解方式,瞬间就会变的很简单。 题目描述是每个元素左上和右下对角线元素都相同。但是,我们发

    2024年01月25日
    浏览(45)
  • java数据结构与算法刷题-----LeetCode667. 优美的排列 II

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 题目要求我们返回一个数组长度为n的数组,必须含有1~n的所有数,并且从左到右,相邻的元素依次相减,它们的差,必

    2024年01月25日
    浏览(48)
  • java数据结构与算法刷题-----LeetCode240. 搜索二维矩阵 II

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 法一:把整个数组遍历一遍,时间复杂度O(m*n) 法二:每一行用二分搜索,那么时间复杂度就是O(m * l o g 2 n log_2{n} l o g

    2024年01月22日
    浏览(56)
  • 数据结构与算法之美学习笔记:42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?

    本节课程思维导图: 利用 Trie 树,可以实现搜索引擎的提示功能,这样可以节省用户输入搜索的时间。实际上,搜索引擎在用户体验方面的优化还有很多,比如你可能经常会用的拼写纠错功能。 当你在搜索框中,一不小心输错单词时,搜索引擎会非常智能地检

    2024年02月03日
    浏览(57)
  • java数据结构与算法刷题-----LeetCode209. 长度最小的子数组

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 代码:时间复杂度O(n).空间复杂度O(1)

    2024年01月21日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包