“数据结构”读书笔记(树、图、查找与排序).doc

1“数据结构”读书笔记（树、图、查找与排序）借此抛砖引玉，希望同学 们自己做得更好！第 5 章 树结构1. 树：是 n（n≥0）个结点的有限集 TT 为空时称空树，否则满足：1）有且仅有一个特定的称为根的结点；2）其余结点可分为 m 个互不相交的子集，每个子集本身是一棵树，并称为根的子树2. 树的表示方法：1）树形表示法；2）嵌套集合表示法；3）凹入表表示法；4）广义表表示法；3. 一个结点拥有的子树数称为该结点的度；一棵树的度是指树中结点最大的度数；4. 度为零的结点称叶子或终端结点；度不为零的结点称分支结点或非终端结点；5. 根结点称开始结点，根结点外的分支结点称内部结点；6. 树中某结点的子树的根称为该结点的孩子；该结点称为孩子的双亲；7. 树中存在一个结点序列 K1，K2 ，… Kn，使 Ki 为 Ki+1 的双亲，则称该结点序列为 K1 到Kn 的路径或道路；8. 树中结点 K 到 Ks 间存在一条路径，则称 K 是 Ks 的祖先，Ks 是 K 的子孙；9. 结点的层数从根算起，若根的层数为 1，则其余结点层数是其双亲结点层数加 1；双亲在同一层的结点互为堂兄弟；树中结点最大层数称为树的高度或深度；10. 树中每个结点的各个子树从左到右有次序的称有序树，否则称无序树；11. 森林是 m 棵互不相交的树的集合。

12. 二叉树：是 n 个结点的有限集，它或为空集，或由一个根结点及两棵互不相交的、分别称为该根的左子树和右子树的二叉树组成13. 二叉树不是树的特殊情况，这是两种不同的数据结构；它与无序树和度为 2 的有序树不同14. 二叉树的性质：1）二叉树第 i 层上的结点数最多为 2^（i-1）；2）深度为 k 的二叉树至多有 2^k-1 个结点；3）在任意二叉树中，叶子数为 n0，度为 2 的结点数为 n2，则 n0=n2+1；15. 满二叉树是一棵深度为 k 的且有 2^k-1 个结点的二叉树；16. 完全二叉树是至多在最下两层上结点的度数可以小于 2，并且最下层的结点集中在该层最左的位置的二叉树；17. 具有 N 个结点的完全二叉树的深度为 log2N 取整加 1；18. 二叉树的存储结构2（1）顺序存储结构：把一棵有 n 个结点的完全二叉树，从树根起自上而下、从左到右对所有结点编号，然后依次存储在一个向量 b[0～n] 中，b[1～n] 存放结点，b[0] 存放结点总数各个结点编号间的关系：1） i=1 是根结点； i>1 则双亲结点是 i/2 取整；2） 左孩子是 2i， 右孩子是 2i+1；（要小于 n）3） i>（n/2 取整）的结点是叶子；4） 奇数没有右兄弟，左兄弟是 i-1；5） 偶数没有左兄弟，右兄弟是 i+1；（2）链式存储结构结点的结构为：lchild|data|rchild ；相应的类型说明：typedef char data；typedef struct node{datatype data；structnode *lchild，*rchild；}bintnode；typedef bintnode *bintree；19. 在二叉树中所有类型为 bintnode 的结点和一个指向开始结点的 bintree 类型的头指针构成二叉树的链式存储结构称二叉链表。

20. 二叉链表由根指针唯一确定在 n 个结点的二叉链表中有 2n 个指针域，其中 n+1 个为空21. 二叉树的遍历方式有：前序遍历、中序遍历、后序遍历时间复杂度为 O（n）22. 线索二叉树：利用二叉链表中的 n+1 个空指针域存放指向某种遍历次序下的前趋和后继结点的指针，这种指针称线索加线索的二叉链表称线索链表相应二叉树称线索二叉树23. 线索链表结点结构：lchild|ltag|data|rtag|rchild；ltag=0，lchild 是指向左孩子的指针；ltag=1，lchild 是指向前趋的线索；rtag=0，rchild 是指向右孩子的指针；rtag=1，rchild 是指向后继的线索；24. 查找*p 在指定次序下的前趋和后继结点算法的时间复杂度为 O（h）线索对查找前序前趋和后序后继帮助不大25. 遍历线索二叉树时间复杂度为 O（n）26. 树、森林与二叉树的转换（1）树、森林与二叉树的转换1）树与二叉树的转换：1}所有兄弟间连线； 2}保留与长子的连线，去除其它连线该二叉树的根结点的右子树必为空2）森林与二叉树的转换：1}将所有树转换成二叉树；2}将所有树根连线。

2）二叉树与树、森林的转换是以上的逆过程27. 树的存储结构：使用链表结构（1）双亲链表表示法：为每个结点设置一个 parent 指针，就可唯一表示任何一棵树Data|parent3（2）孩子链表表示法：为每个结点设置一个 firstchild 指针，指向孩子链表头指针，链表中存放孩子结点序号Data|firstchild3）孩子兄弟链表表示法：附 加 两 个 指 向 左 孩 子 和 右 兄 弟 的 指 针 Leftmostchild|data|rightsibling28. 树和森林的遍历：前序遍历一棵树等价于前序遍历对应二叉树；后序遍历等价于中序遍历对应二叉树29. 最优二叉树（哈夫曼树）：树的路径长度是从树根到每一结点的路径长度之和将树中的结点赋予实数称为结点的权30. 结点的带权路径是该结点的路径长度与权的乘积树的带权路径长度又称树的代价，是所有叶子的带权路径长度之和31. 带权路径长度最小的二叉树称最优二叉树（哈夫曼树）32. 具有 2n-1 个结点其中有 n 个叶子，并且没有度为 1 的分支结点的树称为严格二叉树33. 哈夫曼编码34. 对字符集编码时，要求字符集中任一字符的编码都不是其它字符的编码前缀，这种编码称前缀码。

35. 符出现频度与码长乘积之和称文件总长；字符出现概率与码长乘积之和称平均码长；36. 使文件总长或平均码长最小的前缀码称最优前缀码37. 利用哈夫曼树求最优前缀码，左为 0，右为 1编码平均码长最小；没有叶子是其它叶子的祖先，不可能出现重复前缀第 6 章 图结构1. 图：图 G 是由顶点集 V 和边集 E 组成，顶点集是有穷非空集，边集是有穷集；2. G 中每条边都有方向称有向图；有向边称弧；边的始点称弧尾；边的终点称弧头；G 中每条边都没有方向的称无向图3. 顶点 n 与边数 e 的关系：无向图的边数 e 介于 0～n（n-1 ）/2 之间，有 n（n-1 ）/2 条边的称无向完全图；有向图的边数 e 介于 0～n（n-1）之间，有 n（n-1 ）条边的称有向完全图；4. 无向图中顶点的度是关联与顶点的边数；有向图中顶点的度是入度与出度的和所有图均满足：所有顶点的度数和的一半为边数5. 图 G（V，E），如 V’是 V 的子集，E’是 E 的子集，且 E’中关联的顶点均在 V’中，则G’（V’，E’）是 G 的子图6. 在有向图中，从顶点出发都有路径到达其它顶点的图称有根图；7. 在无向图中，任意两个顶点都有路径连通称连通图；极大连通子图称连通分量；8. 在有向图中，任意顺序两个顶点都有路径连通称强连通图；极大连通子图称强连通分量；9. 将图中每条边赋上权，则称带权图为网络。

410. 图的存储结构：（1）邻接矩阵表示法：邻接矩阵是表示顶点间相邻关系的矩阵n 个顶点就是 n 阶方阵无向图是对称矩阵；有向图行是出度，列是入度2）邻接表表示法：对图中所有顶点，把与该顶点相邻接的顶点组成一个单链表，称为邻接表，adjvex|next，如要保存顶点信息加入 data；对所有顶点设立头结点，vertex|firstedge，并顺序存储在一个向量中；vertex 保存顶点信息，firstedge 保存邻接表头指针11. 邻接矩阵表示法与邻接表表示法的比较：1）邻接矩阵是唯一的，邻接表不唯一；2）存储稀疏图用邻接表，存储稠密图用邻接矩阵；3）求无向图顶点的度都容易，求有向图顶点的度邻接矩阵较方便；4）判断是否是图中的边，邻接矩阵容易，邻接表最坏时间为 O（n）；5）求边数 e，邻接矩阵耗时为 O（n^2），与 e 无关，邻接表的耗时为 O（e+n）；12. 图的遍历：（1）图的深度优先遍历：类似与树的前序遍历按访问顶点次序得到的序列称 DFS 序列对邻接表表示的图深度遍历称 DFS，时间复杂度为 O（n+e）； 对邻接矩阵表示的图深度遍历称 DFSM，时间复杂度为 O（n^2）；（2）图的广度优先遍历：类似与树的层次遍历。

按访问顶点次序得到的序列称 BFS 序列对邻接表表示的图广度遍历称 BFS，时间复杂度为 O（n+e）； 对邻接矩阵表示的图广度遍历称 BFSM，时间复杂度为 O（ n^2）；13. 将没有回路的连通图定义为树称自由树14. 生成树：连通图 G 的一个子图若是一棵包含 G 中所有顶点的树，该子图称生成树有 DFS 生成树和 BFS 生成树，BFS 生成树的高度最小非连通图生成的是森林15. 最小生成树：将权最小的生成树称最小生成树是无向图的算法）（1）普里姆算法：1）确定顶点 S、初始化候选边集 T[0～n-2]；formvex|tovex|length2）选权值最小的 T 与第 1 条记录交换；3）从 T[1]中将 tovex 取出替换以下记录的 fromvex 计算权；若权小则替换，否则不变；4）选权值最小的 T 与第 2 条记录交换；5）从 T[2]中将 tovex 取出替换以下记录的 fromvex 计算权；若权小则替换，否则不变；6）重复 n-1 次初始化时间是 O（n），选轻边的循环执行 n-1-k 次，调整轻边的循环执行 n-2-k；算法的时间复杂度为 O（n^2），适合于稠密图。

2）克鲁斯卡尔算法：1）初始化确定顶点集和空边集；对原边集按权值递增顺序排序；2）取第 1 条边，判断边的 2 个顶点是不同的树，加入空边集，否则删除；3）重复 e 次对边的排序时间是 O（elog2e）；初始化时间为 O（n）；执行时间是 O（log2e）；算法的时间复杂度为 O（elog2e），适合于稀疏图16. 路径的开始顶点称源点，路径的最后一个顶点称终点；517. 单源最短路径问题：已知有向带权图，求从某个源点出发到其余各个顶点的最短路径；18. 单目标最短路径问题：将图中每条边反向，转换为单源最短路径问题；19. 单顶点对间最短路径问题：以分别对不同顶点转换为单源最短路径问题；20. 所有顶点对间最短路径问题：分别对图中不同顶点对转换为单源最短路径问题；21. 迪杰斯特拉算法：1）初始化顶点集 S，路径权集 D，前趋集 P；2）设置 S[s]为真，D[s]为 0；3）选取 D 最小的顶点加入顶点集；4）计算非顶点集中顶点的路径权集；5）重复 3）n-1 次算法的时间复杂度为 O（n^2）22. 拓扑排序：对一个有向无环图进行拓扑排序，是将图中所有顶点排成一个线性序列，满足弧尾在弧头之前。

这样的线性序列称拓扑序列1）无前趋的顶点优先：总是选择入度为 0 的结点输出并删除该顶点的所有边设置各个顶点入度时间是 O（ n+e），设置栈或队列的时间是 O（n），算法时间复杂度为 O（n+e）2）无后继的顶点优先：总是选择出度为 0 的结点输出并删除该顶点的所有边设置各个顶点出度时间是 O（ n+e），设置栈或队列的时间是 O（n），算法时间复杂度为 O（n+e）求得的是逆拓扑序列第 7 章 查找查找是以线性结构和非线性结构为基础，重点掌握查找的思想和方法1. 查找的同时对表做修改操作（如插入或删除）则相应的表称之为动态查找表，否则称之为静态查找表2. 衡量一个查找算法次序优劣的标准是在查找过程中对关键字需要执行的平均比较次数（即平均查找长度 ASL）.3. 线性表上进行查找的方法主要有三种：顺序查找、二分查找和分块查找。