7.链表(LinkedList)
7.1 定义
7.2 链表实现图
7.3 约瑟夫环问题
7.4 如何快读找到一个链表的中间结点？（快慢指针遍历法）
7.5 链表的应用场景
7.6 链表与数组的对比
8. 树
8.1 树的基本概念
8.2 树的特点
8.3 树中的常用术语
8.4 树的分类
7.链表(LinkedList)
7.1 定义
链表是一种在物理存储单元上非连接，非顺序的存储结构。链表由一系列节点组成，每个节点包括两个部分：一个是存储数据的数据域，另一个是存储下一个节点地址的指针域
7.2 链表实现图
7.3 约瑟夫环问题
n个人围成一个圆圈，第K个人从1开始顺时针报数，报到第m个人，令其出列，然后再从下一个人开始从1顺时针报数，报到第m个人，再令其出列。求出出列顺序
7.4 如何快读找到一个链表的中间结点？（快慢指针遍历法）
普通方法:循环单链表,确定单链表的长度,然后循环长度1/2确定中间节点.
缺点: 需要遍历 L+L/2 次 ,算法难度 O(L+L/2)=O(3L/2)
快慢指针遍历法：A指针每次移动1个节点，B指针每次移动2个节点。当B到达end的时候，A的位置即为中点
优点: 需要遍历 L/2 次, 算法复杂度O(L/2)
7.5 链表的应用场景
单链表
1.删除时，只适合删除第一个元素
2.添加时，只添加到第一个元素后面或者第一个元素前面
3.属于单向迭代器，只能前进/后退，查找效率极差，不适合大量查询
这种典型的应用场合是各类缓冲池和栈的实现
双向链表
1.删除时，可以删除任意元素，而只需要极小的开销
2.添加时，当直到他的前一个或者后一个位置的元素时，只需要极小的开销
3.属于单向迭代器，可以前进和后退，但是同样需要遍历，效率跟单向链表一样，不适合大量查询
这种典型的应用场合是各种不需要排序的数据列表管理
7.6 链表与数组的对比
链表与数组最大的区别之一就是链表内存空间不连续，不可以随机访问。
数组连续空间更利于CPU缓存；链表可充分利用内存碎片
8. 树
8.1 树的基本概念
由n（n>=1）个有限结点组成⼀个具有层次关系的集合。把它叫做“树”是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。
8.2 树的特点
①每个节点有零个或多个⼦节点；
②没有⽗节点的节点称为根节点；
③每⼀个非根节点有且只有⼀个
⽗节点；
④除了根节点外，每个⼦节点可以分为多个不相交的⼦树；
8.3 树中的常用术语
①路径：顺着节点的边从⼀个节点⾛到另⼀个节点，所经过的节点的顺序排列就称为“路径”。
②根：树
顶端的节点称为根。⼀棵树只有⼀个根，如果要把⼀个节点和边的集合称为树，那么从根到其他任何⼀
个节点都必须有且只有⼀条
③父节点：若⼀个节点含有⼦节点，则这个节点称为其⼦节点的⽗节点；
④子节点：⼀个节点含有的⼦树的根节点称为该节点的⼦节点；
⑤兄弟节点：具有相同⽗节点的节点互称为兄弟节点；
⑥叶节点：没
有子节点的节点称为叶节点，也叫叶⼦节点，
⑦⼦树：每个节点都可以作为⼦树的根，它和它所有的⼦节点、⼦节点的⼦节点等都包含在⼦树中。
⑧节点的层次：
从根开始定义，根为第1层，根的⼦节点为第2层，以此类推。
⑨深度：对于任意节点n,n的深度为从
根到n的唯⼀路径⻓，根的深度为0；
⑩⾼度：对于任意节点n,n的⾼度为从n到⼀⽚树叶的最⻓路径
⻓，所有树叶的⾼度为0；
8.4 树的分类
按照类型来分：
1. ⽆序树：树中任意节点的⼦结点之间没有顺序关系，这种树称为⽆序树,也称为⾃由树;
2. 有序树：树中任意节点的⼦结点之间有顺序关系，这种树称为有序树；
3. ⼆叉树：每个节点最多含有两个⼦树的树称为⼆叉树；
4. 完全⼆叉树：最后一层叶子结点都靠左对齐。
5. 满⼆叉树：只要有子结点，就必然是有两个
6. 霍夫曼树：带权路径最短的⼆叉树称为哈夫曼树或最优⼆叉树；
按算法上来分：
⼆叉查找树（⼆叉排序树）、平衡⼆叉树（AVL树）、红⿊树、B-树、B+树、字典树（trie树）、后缀树、⼴义后缀树。
网友评论