/WangDao-DataStructure

《数据结构》经典算法代码

Primary LanguageC++Apache License 2.0Apache-2.0

数据结构-Data Structure

2020-6-18更新

🎺写在前面的话

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

使用指南

本仓库中的文件几乎每个.cpp均有main函数,每个文件可以单独运行

使用方法1(推荐)

在线阅读,学习代码**,手写

使用方法2(推荐)

  1. 下载 or clone代码
  2. 挑选需要的代码
  3. 复制出来,在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

最小生成树问题

  • Prim
  • kruskal

最短路径问题

  • Dijkstra
  • Floyd-Warshall

拓扑排序

查找

KMP算法

  • get_next
  • next_val
  • kmp

排序算法

快速排序

  • 递归版本已经完成
  • 非递归版本待更新

堆排序

  • 堆排序
    • 堆的建立
      • 从i/2开始—>1
    • 堆的删除
      • 堆的删除仅针对于根结点,每次删除时将根结点与最后一个元素交换然后自顶向下调整堆
    • 堆的插入
      • 插入时查找堆的末尾(即数组最后)然后自上而下的调整堆
    • 建立堆的时间复杂度$O(n)$
    • 调整堆的时间复杂度 $O(log_2n)$
  • 判断一个堆是大顶堆的算法

归并排序

  • 已经更新

希尔排序

  • 2019 9 18更新完成

课后习题

  • 奇偶顺序排序 ✅
  • 找到第k小的数 ✅

上面两个算法有异曲同工之处 注意结合快排理解

  • 双向冒泡排序 ✅

真题

2018

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

  • 2019 10 12 日更新完毕

2013

个人题解,正常人比较容易想到的算法,思路和2018差不多

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

  • 2019 10 14日更新完毕
  • 未学习最优解

2014

其余的自己学习算法**即可,王道书的代码很好

个人题解

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

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

经典算法练习题

习题集为剑指offer共67道题

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