本文目录：
 

 
 
数据结构分类
1、数组
2、栈
3、队列
4、链表
5、树
6、散列表
7、堆
8、图
 
 
 
数据结构分类
 
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。 
 常用的数据结构有：数组，栈，链表，队列，树，图，堆，散列表等，如图所示： 
  
 每一种数据结构都有着独特的数据存储方式，下面为大家介绍它们的结构和优缺点。
 
1、数组
 
数组是可以再内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为 1。
 
int[] data = new int[100]；data[0]  = 1;
 
优点： 
 1、按照索引查询元素速度快 
 2、按照索引遍历数组方便
 
缺点： 
 1、数组的大小固定后就无法扩容了 
 2、数组只能存储一种类型的数据 
 3、添加，删除的操作慢，因为要移动其他的元素。
 
适用场景： 
 频繁查询，对存储空间要求不大，很少增加和删除的情况。
 
2、栈
 
栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。 
  
 栈的结构就像一个集装箱，越先放进去的东西越晚才能拿出来，所以，栈常应用于实现递归功能方面的场景，例如斐波那契数列。
 
3、队列
 
队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。从一端放入元素的操作称为入队，取出元素为出队，示例图如下： 
  
 使用场景：因为队列先进先出的特点，在多线程阻塞队列管理中非常适用。
 
4、链表
 
链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。 
  
 链表的优点： 
 链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素； 
 添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；
 
缺点： 
 因为含有大量的指针域，占用空间较大； 
 查找元素需要遍历链表来查找，非常耗时。
 
适用场景： 
 数据量较小，需要频繁增加，删除操作的场景
 
5、树
 
树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
 
每个节点有零个或多个子节点； 
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树；
 
在日常的应用中，我们讨论和用的更多的是树的其中一种结构，就是二叉树。 
  
 二叉树是树的特殊一种，具有如下特点：
 
1、每个结点最多有两颗子树，结点的度最大为2。 
 2、左子树和右子树是有顺序的，次序不能颠倒。 
 3、即使某结点只有一个子树，也要区分左右子树。 
 
二叉树是一种比较有用的折中方案，它添加，删除元素都很快，并且在查找方面也有很多的算法优化，所以，二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常有用。
 
扩展： 
 二叉树有很多扩展的数据结构，包括平衡二叉树、红黑树、B+树等，这些数据结构二叉树的基础上衍生了很多的功能，在实际应用中广泛用到，例如mysql的数据库索引结构用的就是B+树，还有HashMap的底层源码中用到了红黑树。这些二叉树的功能强大，但算法上比较复杂，想学习的话还是需要花时间去深入的。
 
6、散列表
 
散列表，也叫哈希表，是根据关键码和值 (key和value) 直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。
 
记录的存储位置=f(key) 
 
这里的对应关系 f 成为散列函数，又称为哈希 (hash函数)，而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里，这种存储空间可以充分利用数组的查找优势来查找元素，所以查找的速度很快。
 
哈希表在应用中也是比较常见的，就如Java中有些集合类就是借鉴了哈希原理构造的，例如HashMap，HashTable等，利用hash表的优势，对于集合的查找元素时非常方便的，然而，因为哈希表是基于数组衍生的数据结构，在添加删除元素方面是比较慢的，所以很多时候需要用到一种数组链表来做，也就是拉链法。拉链法是数组结合链表的一种结构，较早前的hashMap底层的存储就是采用这种结构，直到jdk1.8之后才换成了数组加红黑树的结构，其示例图如下： 
  
 从图中可以看出，左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。 
 
哈希表的应用场景很多，当然也有很多问题要考虑，比如哈希冲突的问题，如果处理的不好会浪费大量的时间，导致应用崩溃。
 
7、堆
 
堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有以下的性质：
 
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
 
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
 
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。 
 (ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)，满足前者的表达式的成为小顶堆，满足后者表达式的为大顶堆，这两者的结构图可以用完全二叉树排列出来，示例图如下： 
  
 因为堆有序的特点，一般用来做数组中的排序，称为堆排序。
 
8、图
 
图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。 
 
按照顶点指向的方向可分为无向图和有向图： 
  
  
 图是一种比较复杂的数据结构，在存储数据上有着比较复杂和高效的算法，分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构，这里不做展开，读者有兴趣可以自己学习深入。

 
系列文章
 
第一章：基础知识
 
第二章：线性表
 
第三章：栈和队列 
 
第四章：字符串和数组
 

目录
 
基础
 
c/c++ 代码优化及常见错误
 
    c语言位运算的妙用-程序优化
 
c/c++进制转换方法汇总（含全部代码）
 
     二进制数-北邮2012研究生复试
 
C++ string的简单使用
 
C++ 类型转换（内置类型,string、char*、const char*等）
 
质因子分解
 
除树和图外的数据结构可以使用STL: C++ STL的使用
 
数据结构
 
线性表
 
顺序表
 
        循环左移（2010联考真题）
 
单链表
 
        单链表相邻结点逆置(2019北邮考研真题)
 
栈
 
顺序栈
 
链栈
 
队列
 
循环队列
 
链队
 
树
 
二叉树
 
二叉查找（排序）树的插入，创建，查找，删除
 
二叉查找树-插入结点，返回父节点（2012北邮机试）
 
二叉树-已知前序遍历和中序遍历，求后序遍历
 
哈夫曼树-创建，编码，解码，带权路径长度（含全部代码）
 
树-双亲表示法（含全部代码）
 
       统计结点个数（双亲表示法）-北邮2013研究生复试
 
图
 
无向图-基本操作函数（建立，宽度遍历，深度遍历，邻接矩阵表示）
 
图-迪杰斯特拉（Dijkstra）算法详解（含全部代码）
 
图-贝尔曼福特（Bellman-Ford）算法详解（含全部代码）（北邮考研不考）
 
图-弗洛伊德（FloydWarshall）算法详解（含全部代码）
 
图-最小生成树(Prim)算法详解（含全部代码）
 
图-最小生成树(Kruskal)算法详解（含全部代码）
 
图-完美匹配-匈牙利算法（Hungarian method Edmonds）详解（含全部代码）
 
图-欧拉图(欧拉环游/回路、欧拉迹/通路、Hierholzer算法、Fleury算法)
 
查找
 
二分查找
 
折半查找某数X在数组中出现的次数（2019北邮考研真题）
 
KMP算法next与nextval手算
 
排序
 
简单选择排序
 
直接插入排序
 
冒泡排序
 
快速排序
 
排序算法比较
 
常见算法思想
 
双指针
 
双指针算法详解（快慢指针、对撞指针、滑动窗口）
 
递归
 
递归-简单背包问题（修剪递归树，含全部代码）
 
递归-深度优先搜索（模板、回溯、剪枝、记忆化）
 
递推
 
并查集（Disjoint Set）详解+例题
 
分治
 
分治-最大子数组（算法导论P39）
 
动态规划
 
动态规划-最大子数组
 
动态规划-最长平衡子串（2018北邮机试真题）
 
动态规划-简单背包问题
 
动态规划-0/1背包问题
 
动态规划-0/1背包优化
 
动态规划-完全背包
 
动态规划-完全背包优化
 
动态规划-多重背包
 
数论
 
素数筛选-埃氏筛法与欧拉筛法
 
北邮机试真题
 
2019北邮计算机院机试真题
 
特殊数-2017北邮机试真题
 
最值问题-北邮OJ88
 
字符串转换-北邮OJ90
 
反转单词-北邮OJ103
 
912星球的研究生-北邮OJ104
 
中位数-北邮2014研究生复试
 
内存分配-北邮OJ277
 
丁神去谷歌-北邮OJ416
 
丁神又去谷歌（0/1背包）-北邮OJ417
 
算法可视化
 
 

重大消息:本专栏出对应的实战专栏啦（OJ网站题目分类，分难度整理笔记（leetcode、牛客网）），欢迎查看、评论、分享更优秀思路。(2020-08-28更新)
 
 
基础
 
c/c++ 代码优化及常见错误
 
    c语言位运算的妙用-程序优化
 
c/c++进制转换方法汇总（含全部代码）
 
     二进制数-北邮2012研究生复试
 
C++ string的简单使用
 
C++ 类型转换（内置类型,string、char*、const char*等）
 
质因子分解
 
除树和图外的数据结构可以使用STL: C++ STL的使用
 
 
数据结构
 
 
线性表
 
顺序表
 
        循环左移（2010联考真题）
 
单链表
 
        单链表相邻结点逆置(2019北邮考研真题)
 
 
栈
 
顺序栈
 
链栈
 
 
队列
 
循环队列
 
链队
 
 
树
 
二叉树
 
二叉查找（排序）树的插入，创建，查找，删除
 
二叉查找树-插入结点，返回父节点（2012北邮机试）
 
二叉树-已知前序遍历和中序遍历，求后序遍历
 
哈夫曼树-创建，编码，解码，带权路径长度（含全部代码）
 
树-双亲表示法（含全部代码）
 
       统计结点个数（双亲表示法）-北邮2013研究生复试
 
 
图
 
无向图-基本操作函数（建立，宽度遍历，深度遍历，邻接矩阵表示）
 
图-迪杰斯特拉（Dijkstra）算法详解（含全部代码）
 
图-贝尔曼福特（Bellman-Ford）算法详解（含全部代码）（北邮考研不考）
 
图-弗洛伊德（FloydWarshall）算法详解（含全部代码）
 
图-最小生成树(Prim)算法详解（含全部代码）
 
图-最小生成树(Kruskal)算法详解（含全部代码）
 
图-完美匹配-匈牙利算法（Hungarian method Edmonds）详解（含全部代码）
 
图-欧拉图(欧拉环游/回路、欧拉迹/通路、Hierholzer算法、Fleury算法)
 
 
查找
 
二分查找
 
折半查找某数X在数组中出现的次数（2019北邮考研真题）
 
KMP算法next与nextval手算
 
 
排序
 
简单选择排序
 
直接插入排序
 
冒泡排序
 
快速排序
 
排序算法比较
 
 
常见算法思想
 
 
双指针
 
双指针算法详解（快慢指针、对撞指针、滑动窗口）
 
 
递归
 
递归-简单背包问题（修剪递归树，含全部代码）
 
递归-深度优先搜索（模板、回溯、剪枝、记忆化）
 
 
递推
 
 
并查集（Disjoint Set）详解+例题
 
 
贪心
 
 
分治
 
分治-最大子数组（算法导论P39）
 
 
动态规划
 
动态规划-最大子数组
 
动态规划-最长平衡子串（2018北邮机试真题）
 
动态规划-简单背包问题
 
动态规划-0/1背包问题
 
动态规划-0/1背包优化
 
动态规划-完全背包
 
动态规划-完全背包优化
 
动态规划-多重背包
 
 
数论
 
素数筛选-埃氏筛法与欧拉筛法
 
 
北邮机试真题
 
2019北邮计算机院机试真题
 
特殊数-2017北邮机试真题
 
最值问题-北邮OJ88
 
字符串转换-北邮OJ90
 
反转单词-北邮OJ103
 
912星球的研究生-北邮OJ104
 
中位数-北邮2014研究生复试
 
内存分配-北邮OJ277
 
丁神去谷歌-北邮OJ416
 
丁神又去谷歌（0/1背包）-北邮OJ417
 
算法可视化
 
algorithm visualizer
 
github上的一个开源项目，可视化学算法，使用的是js，包含的算法比较全面
 
本人b站账号:lady_killer9
 
有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。如果您感觉有所收获，自愿打赏，可选择支付宝18833895206（小于），您的支持是我不断更新的动力。

整理的算法模板合集： ACM模板
 
 


 
目录
 
$Forword$
C语言版
数据结构（C语言版 第2版严蔚敏版）完整课后习题答案汇总
数据结构（C语言版） 第 一 章 绪论 知识梳理 + 作业习题详解
数据结构（C语言版） 第 二 章 线性表 知识梳理 + 作业习题详解
数据结构（C语言版） 第 三 章 栈与队列 知识梳理 + 作业习题详解
数据结构（C语言版） 第 四 章 串、数组和广义表 知识梳理 + 作业习题详解
数据结构（C语言版） 第 五 章 树与二叉树 知识梳理 + 作业习题详解
数据结构（C语言版） 第 六 章 图 知识梳理 + 习题详解
数据结构（C语言版） 第 八 章 排序 知识梳理 + 习题详解
  
C++版
【数据结构】——线性表
【数据结构】单调栈和单调队列 详解+例题剖析
【树和二叉树】(四种遍历，建树)详解+二叉排序树（包含图像和相关习题）
【堆，大根堆，小根堆，优先队列】 详解
【图论】图，实现图（三种方式），二分图 详解
【数论/图论】树的计数，prufer（Prüfer）编码，Cayley公式及相应例题
【最短路合集】（Dijkstra、SPFA、Floyd以及路径还原模板）
【图论】最小生成树算法（prim和kruskal详解及对比）
【并查集】
【树状数组】
【线段树】 从入门到进阶（超清晰，简单易懂）
【可持久化线段树 （主席树）】
 

 
$Forword$
 
准备开一个新坑，关于数据结构的这两天我们学校的数据结构课开课了，也都知道数据结构非常重要，虽然我已经把数据结构都给学完了，但是我学的还是非常浅的，只涉及到C++实现以及STL等对于ACM竞赛有用的东西，更多的是应用，基础的概念有些还是掌握的不是很熟练，以及我们开的课是用C语言版 的，而我更多的是用C++和python，所以我决定在数据结构学习之余，把课本上的一些重难点和各种C语言实现的代码整理一下发到博客里，根据我们学校的进度来更新（我也不是很想花太多的时间去完成这一项工程，毕竟我还要刷题和完成我的另外一个大项目算法竞赛学习笔记 和 ACM模板 （模板先暂时搁置，现在主要把《算法竞赛进阶指南刷一遍》）的，没有太多的时间）。
 
C语言版
 
应该是每一章一个博客，顺便在每篇博客的最后放一些PAT上坑爹的知识点类的题，估计期末就是只考这个，最讨厌这种要死记硬背的东西了，哪有算法题有意思。
 
数据结构（C语言版 第2版严蔚敏版）完整课后习题答案汇总
 
非官方答案：
 
 
 
数据结构（C语言版 第2版严蔚敏版）完整课后习题答案汇总
 
 
官方答案：
 
 
 
数据结构（C语言版）课后习题全套完整答案及详解 （答案由李冬梅老师撰写）
 
 
数据结构（C语言版） 第 一 章 绪论 知识梳理 + 作业习题详解
 
博客链接：
 
 
 
数据结构（C语言版） 第 一 章 绪论 知识梳理 + 作业习题详解
 
 
数据结构（C语言版） 第 二 章 线性表 知识梳理 + 作业习题详解
 
博客链接：
 
 
 
数据结构（C语言版） 第 二 章 线性表知识梳理 + 作业习题详解
 
 
数据结构（C语言版） 第 三 章 栈与队列 知识梳理 + 作业习题详解
 
博客链接：
 
 
 
数据结构（C语言版） 第 三 章 栈与队列 知识梳理 + 作业习题详解
 
 
数据结构（C语言版） 第 四 章 串、数组和广义表 知识梳理 + 作业习题详解
 
博客链接：
 
 
 
数据结构（C语言版） 第 四 章 串、数组和广义表 知识梳理 + 作业习题详详解
 
 
数据结构（C语言版） 第 五 章 树与二叉树 知识梳理 + 作业习题详解
 
博客链接：
 
 
 
数据结构（C语言版） 第 五 章 树与二叉树 知识梳理 + 作业习题详解
 
 
 
数据结构（C语言版） 第 六 章 图 知识梳理 + 习题详解
 
博客链接：
 
 
 
数据结构（C语言版） 第 六 章 图 知识梳理 + 习题详解
 
 
数据结构（C语言版） 第 八 章 排序 知识梳理 + 习题详解
 
博客链接：
 
 
 
数据结构（C语言版） 第 八 章 排序 知识梳理 + 习题详解
 
 
C++版
 
【数据结构】——线性表
 
 
 
【数据结构】——线性表
 
 
 
【数据结构】单调栈和单调队列 详解+例题剖析
 
 
 
【数据结构】单调栈和单调队列详解+例题剖析
 
 
 
【树和二叉树】(四种遍历，建树)详解+二叉排序树（包含图像和相关习题）
 
 
 
【树和二叉树】(四种遍历，建树)详解+二叉排序树（包含图像和相关习题）
 
 
 
【堆，大根堆，小根堆，优先队列】 详解
 
 
 
【堆，大根堆，小根堆，优先队列】详解
 
 
 
【图论】图，实现图（三种方式），二分图 详解
 
 
 
【图论】图，实现图（三种方式），二分图详解
 
 
 
【数论/图论】树的计数，prufer（Prüfer）编码，Cayley公式及相应例题
 
 
 
【数论/图论】树的计数，prufer（Prüfer）编码，Cayley公式及相应例题
 
 
 
【最短路合集】（Dijkstra、SPFA、Floyd以及路径还原模板）
 
 
 
最短路合集（Dijkstra、SPFA、Floyd以及路径还原模板）
 
 
 
【图论】最小生成树算法（prim和kruskal详解及对比）
 
 
 
【图论】最小生成树算法（prim和kruskal详解及对比）
 
 
 
【并查集】
 
 
 
【并查集】
 
 
 
【树状数组】
 
 
 
【树状数组】
 
 
 
【线段树】 从入门到进阶（超清晰，简单易懂）
 
 
 
【线段树】 从入门到进阶（超清晰，简单易懂）
 
 
 
【可持久化线段树 （主席树）】
 
 
 
【可持久化线段树（主席树）】
 
 
 
注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧