Repository files navigation

数据结构-Data Structure

2020-6-18更新

🎺写在前面的话

  • 计算机考研的朋友们加油!
  • 欢迎Star分享一波, 祝你们都可以上岸!
  • 王道考研数据结构,书籍部分代码及算法题C++语言实现(但大部分使用C的库函数)
  • 为了方便起见代码编写以 c语言风格为主 ,不涉及面向对象程序设计,并仅仅使用了一些简单的c++stl的简单数据结构, 对基础薄弱者友好 👬
  • 此仓库目的:学习和理解算法题,辅助考研,时间有限,故代码命名及注释未按代码规范,请见谅
  • 由于此仓库并不是工程文件夹,故代码中可能有一些小的错误,欢迎pull request指正,dalao勿喷
  • readme中可能部分公式无法解析 推荐使用 Typora
  • 欢迎大家一起敲代码!
  • 有问题可以提出ISSUE 看到了就会回复
  • 本仓库中的文件几乎每个 .cpp 均有main函数,每个文件可以单独运行

    使用方法1(推荐)

    在线阅读,学习代码思想,手写

    使用方法2(推荐)

  • 下载 or clone代码
  • 挑选需要的代码
  • 复制出来,在IDE( 推荐Clion、Dev )运行
  • 使用方法3

    导入Clion工程,手动更改Makefile

    使用方法4

    大佬qing自行研究😊

    本章是考试重点容易出算法大题

    2019 9 14 课后算法题更新到7道,对于2020王道数据结构第18页

    链表的直接插入排序 2019 9 18

  • 括号匹配(搞定)
  • 用栈实现递归式的非递归代码P90
  • 🌲的考察在于各种树的特点,以及树的遍历算法

  • 求二叉树的高度

    平衡二叉树

  • 判断一棵树是否为平衡二叉树 (2019-9-6)
  • 2019 7 28 新增DFS
  • 2019 7 31 新增BFS
  • 最小生成树问题

  • kruskal
  • 最短路径问题

  • Dijkstra
  • Floyd-Warshall
  • KMP算法

  • get_next
  • next_val
  • 递归版本已经完成
  • 非递归版本待更新
  • 从i/2开始—>1
  • 堆的删除仅针对于根结点,每次删除时将根结点与最后一个元素交换然后自顶向下调整堆
  • 插入时查找堆的末尾(即数组最后)然后自上而下的调整堆
  • 建立堆的时间复杂度$O(n)$
  • 调整堆的时间复杂度 $O(log_2n)$
  • 判断一个堆是大顶堆的算法
  • 2019 9 18更新完成
  • 奇偶顺序排序 ✅
  • 找到第k小的数 ✅
  • 上面两个算法有异曲同工之处 注意结合快排理解

  • 双向冒泡排序 ✅
  • 个人题解,思路和答案一致,由于我的实现可以包含的数据范围更广,故空间复杂度略有不同,本人算法掌握不是很好,如有错误,欢迎指正。

  • 2019 10 12 日更新完毕
  • 个人题解,正常人比较容易想到的算法,思路和2018差不多

    空间复杂度未达到最优(考试中时间紧迫 不宜猛怼算法题最优解)平时练习可以体会最优解的思路,最优解请参考王道

  • 2019 10 14日更新完毕
  • 未学习最优解
  • 其余的自己学习算法思想即可,王道书的代码很好

    计算WPL使用递归算法,10 行左右解决问题 ,特别好理解和记忆,超好用。

    强烈推荐。王道上的算法我没看(代码看着就长,估计既不容易写对,有不好理解),自认为考试的时候我写不出来那种。

    经典算法练习题

    习题集为 剑指offer 共67道题

    练习地址➡️ https://www.nowcoder.com/ta/coding-interviews