数据结构学习（C++）——树（总结）

要害字 数据结构 C++ 树 才刚开了个头，就要说再见了——在树这里，除了二叉树，别的都还没有讲。为什么可以总结了呢？因为前面已经涉及到了树的两个基本用途，而假如再讲B＋、

才刚开了个头，就要说再见了——在树这里，除了二叉树，别的都还没有讲。为什么可以总结了呢？因为前面已经涉及到了树的两个基本用途，而如果再讲B＋、B－，就不能不提到搜索，如果是胜者树就不能不提到排序。为此

数据结构学习（C++）——图【4】（最短路径） happycock（原作） 要害字 数据结构 最短路径 最短路径恐怕是图的各种算法中最能吸引初学者眼球的了——在地

以上就是现在的教科书里面，图的全部内容了。写完之后，茫茫然，不知道学完之后有什么用……就像我在开篇写的，图的应用太广泛了，以至于现在觉得图“没什么用”——很奇怪的逻辑，只有仔细体味才能觉察到写教科书的

看到这个标题，有些人一定松了一口气——这小子可算白话完了，当然了，你要是略有惋惜之情，我真是受宠若惊。但不论你怎么想，写到这里只是告一段落，并没有完，后面还有很大一部分呢，比如树、图、查找、排序——这

在开始写这些文章之前，我曾经有个想法，能不能以单链表为基础，完成所有的线性链式结构？实践证明，是可以的，就像你看到的这样。我做这个尝试的起因是，看不惯现在教科书凌乱的结构：罗列了一大堆ADT或者是te

相信每个人都曾感受过找东西的痛苦，大多数人也感受过计算机参与资料管理后所带来的便捷，而学过编程的也曾为了某个问题（比如实现“如果不存在则加入”这样的算法描述——排列组合算法的初级阶段）而实现过查找。在

栈的应用很广泛，原书只讲解了表达式求值，那我也就只写这些。其实，栈的最大的用途是解决回溯问题，这也包含了消解递归；而当你用栈解决回溯问题成了习惯的时候，你就很少想到用递归了，比如迷宫求解。

树型查找 折半查找所需要的，有序的、可以随机存取的、顺序结构的限制，导致了排序的额外负担（如果是逐个添加，主要的负担是移动数据，此时是折半插入排序）。通过观察折半查找的过程，发现实际上mid是从判定

【4】选择排序 基本思想是：每次选出第i小的记录，放在第i个位置（i的起点是0，按此说法，第0小的记录实际上就是最小的，有点别扭，不管这么多了）。当i＝N－1时就排完了。 直接选择排序 直选排