# 数据结构-Data Structure
2020-6-18更新
## **🎺写在前面的话**
0. **计算机考研的朋友们加油!**
1. **欢迎Star分享一波， 祝你们都可以上岸！** ✨
2. 王道考研数据结构,书籍部分代码及算法题C++语言实现(但大部分使用C的库函数)
3. 为了方便起见代码编写以**c语言风格为主**，不涉及面向对象程序设计，并仅仅使用了一些简单的c++stl的简单数据结构，**对基础薄弱者友好**👬
4. 此仓库目的：学习和理解算法题，辅助考研，时间有限，故代码命名及注释未按代码规范，请见谅
5. 由于此仓库并不是工程文件夹，故代码中可能有一些小的错误，欢迎pull request指正，dalao勿喷
6. readme中可能部分公式无法解析 推荐使用**Typora**
7. 欢迎大家一起敲代码！
8. **有问题可以提出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
《数据结构》经典算法代码.zip
需积分: 0 143 浏览量
2023-12-30
10:46:08
上传
评论
收藏 74KB ZIP 举报
《数据结构》经典算法代码.zip （98个子文件） 
meiyangyangchiroubang 
CMakeLists.txt 173B 图 
BFS_AdjMatrix.cpp 1KB BFS_Min_Distance.cpp 1KB DFS_Matrix.cpp 870B DijkstraAlgorithm.cpp 1KB 考研算法真题 2018算法题.cpp 2KB 2013算法题.cpp 2KB 2011算法题.cpp 3KB 2010算法题.cpp 1KB 2014算法题.cpp 1KB LICENSE 11KB 常用算法数据结构 堆.cpp 1KB 字符串处理 十进制转二进制.cpp 239B 查找 KMP.cpp 1KB 折半查找.cpp 1KB 折半查找递归版.cpp 596B 线性表 课后算法习题.c 7KB 数据结构公式总结.md 445B 经典算法练习题 二叉搜索树的第k个结点.cpp 775B L26二叉搜索树与双向链表.cpp 901B L22从上往下打印二叉树.cpp 945B L19顺时针打印矩阵.cpp 1KB 数组中只出现一次的数字.cpp 416B 巧妙两数相加.cpp 542B L06旋转数组中最小的元素.cpp 576B 默写-快速排序.cpp 893B L17树的子结构.cpp 1KB L15反转链表.cpp 836B 机器人的运动范围.cpp 1KB L20包含min函数的栈.cpp 694B L18二叉树的镜像.cpp 547B L12数值的整数次方.cpp 532B 巧妙计算1加到n.cpp 513B 按层打印二叉树.cpp 1018B 序列化二叉树.cpp 1KB L30连续数组的最大和.cpp 2KB 统计一个数字在排序数组中出现的次数.cpp 576B L08跳台阶.cpp 350B L34第一个只出现一次的字符.cpp 341B L03从尾到头打印链表.cpp 764B 和为S的连续正数序列.cpp 686B L11二进制中1的个数.cpp 485B 构建数组乘积.cpp 507B 和为S的两个数字.cpp 798B 二叉树的深度.cpp 600B L14链表中倒数第k个结点.cpp 850B 翻转单词顺序序列.cpp 810B L09变态跳台阶.cpp 125B L28数组中出现次数超过一半的数字.cpp 833B 二叉树的下一个结点.cpp 1KB L24二叉树中和为某一值的路径.cpp 1KB L13调整数组顺序使得奇数在偶数前面.cpp 937B L07斐波那契数列.cpp 601B 对称的二叉树.cpp 2KB L25复杂链表的复制.cpp 2KB 字符流中第一个不重复的字符.cpp 860B L29最小的K个数.cpp 1KB L31从1到n中1出现的次数.cpp 917B L27字符串的排列.cpp 1KB L23二叉搜索树的后续遍历序列.cpp 997B L21栈的压入弹出序列.cpp 1KB L04重建二叉树.cpp 2KB 判断是否是平衡二叉树.cpp 820B 孩子们的游戏.cpp 1KB 删除链表中重复的结点.cpp 813B 按照之字型打印二叉树.cpp 1KB 左旋转字符串.cpp 365B L05两个栈实现一个队列.cpp 468B L02替换空格.cpp 420B L10矩形覆盖.cpp 274B 链表中环的入口结点.cpp 1KB L01二维数组中的查找.cpp 561B L35数组中的逆序对.cpp 1KB 数据流中的中位数.cpp 1KB L32把数组排列成最小的数.cpp 422B 两个链表的第一个公共结点.cpp 544B 矩阵中的路径.cpp 1KB L33丑数.cpp 824B L16合并两个排序的链表.cpp 1008B 树 判断是否为平衡二叉树的算法.cpp 2KB TreeTraverse.cpp 5KB 平衡二叉树.cpp 2KB 给定高度求平衡二叉树结点个数.cpp 295B 求二叉树的高度.cpp 1KB .gitignore 39B README.md 4KB 排序 第k小的数字.cpp 1KB 所有奇数移动到偶数前的算法.cpp 1KB 堆排序.cpp 2KB 插入排序.cpp 467B 希尔排序.cpp 1KB 双向冒泡排序.cpp 1KB 快速排序.cpp 992B 归并2.cpp 1009B 选择排序.cpp 673B 冒泡排序.cpp 661B 快速排序-非递归版.cpp 1KB 归并排序.cpp 2KB资源评论
