第七章：数据结构与算法
1、数组
考点：①数组存储地址的换算②二维数组行存储和列存储的区别。
一位数组：a[n]
存储地址的计算： a[i] 的存储地址：a + i*len
len:每一位数组占用的空间的字节数 , i: 数组下标 n:数组长度
二维数组：a[m][n]
行存储 a[i][j] : a+(i*n+j)*len
列存储 a[i][j] : a+(j*m+i)*len
例子：已知 5行5列的二维数组 a 中各个元素占2个字节，求元素 a[2][3] 按行优先存储的存储地址？
a + (2*5+3)*2 = a+26
2、稀疏矩阵
考点：算出稀疏矩阵某一元素对应一维数组的下标
思路：代入法
A00 = M[1] 排除 BC
A11 = M[3] 排除 D
将A00 和 A11 带入到选项中，依次进行排除
3、数据结构的定义
3.1 数据结构的概念
计算机存储、组织数据的方式。
3.2 数据逻辑结构
非线性结构：
数：不能形成回路
图：能够形成环路
3.3 线性表的定义
1、概念： a1,a2,a3....an
2、常见线性表的存储结构爱：
顺序存储结构：顺序表，一维数组
链式存储结构：链表
3.3.1 链表的基本操作
链表的删除和插入，涉及到指针位置指向的切换
每个元素都会有想对应的指针指向
链式存储的存储空间并不是连续的，可能是随机的，所以需要指针进行关联。
3.3.2 顺序存储与链式存储对比
3.3.3 队列与栈
队列：类似于排队
栈：类似于粮仓
循环队列：防止对空和队满的情况下 头和尾的指针都相同，让循环队列少存储一个，使得 (tail+1)%size = head = 0 ，就意味着队列存储满了
例子：
元素按照 a b c 的次序入栈，请仓鼠写出所有可能的出栈序列
c b a
a b c
b a c
例子2 ： D
4、广义表
例子1：
长度：3
深度：2 嵌套的次数
例子2：
tail(LS1) = ((b,c),(d.e))
head(LS1)=(b,c)
head(LS1)=(b)
5、树与二叉树
5.1、特殊的二叉树
5.2、二叉树的特征
5.3、遍历二叉树
前序遍历：
根 、左 、右
1、2、4、5、7、8 、3、6
中序遍历：
左、根、右
后续遍历：
左、右、根
层次遍历： 1 2 3 4 5 6 7 8
中序遍历： 4 2 7 8 5 1 3 6
后续遍历： 4 8 7 6 2 6 3 1
5.4、反向构造二叉树
由谦虚序列：ABHFDECG；中序HBEDFAGC 构造二叉树
5.5、树转换二叉树
方式一：结点法分析法
孩子节点——左子树结点
兄弟结点——右孩子节点
方式二：连线法
将兄弟结点连接起来，子节点只保留最左结点
5.5、查找二叉树
二叉排序树
左孩子小于根
右孩子大于根
5.6、最优二叉树(哈夫曼树)
基本概念：
树的路径长度
权
带权的路径长度
树的带权路径长度（树的代价）：所有子节点的权*路径长度之和。
树的路径长度越短，越优。
计算树的带权路径长度：
左边：2*2+4*3+8*3+1*1=41
右边：4*2+1*3+2*3+8*1=25
为什么计算树的带权路径长度的计算只是用叶子节点的权，因为只有叶子节点是初始节点， 非叶子节点都是初始节点构造出来的。
例子：构造哈夫曼树
假设有一组权值为 5、29、7、8、14、23、3、11，请构造哈夫曼树
5.7、线索二叉树
5.8、平衡二叉树
定义：
任意节点的左右子树深度相差不超过1
每节点的平衡度只能为-1、0、1
平衡度：左子树长度 - 右子树长度
例子：
对数列：{ 1、5、7、9、8、39、}
6、图
6.1、图的基本概念
完全图：
在无向图中，若每对顶点之间都有一条边相连，则称该图为完全图
在有向图中，若每对顶点之间都有二条有向边相互连接，则称该图为完全图。
6.2、图的存储
6.2.1 邻接矩阵
邻接矩阵：用一个n阶方阵来存放图中各个节点的关联信息，其矩阵元素Rij定义为：
1 若顶点i到顶点j有邻接边
Rij = { }
0 若顶点i到顶点j无邻接边
注：矩阵是可折叠的，所以允许只存储上三角或者下三角。
6.2.2 邻接表
首先把每个顶点的邻接顶点用链表表示出来，然后用一个一维数组来顺序存储上面每个链表的头指针。
6.3、图的遍历
6.4、拓扑排序
路线解析：
1、头：0 ，先执行0 ，执行后将 0-2 和 0-1 的先去掉
2、头 ： 2 或者 1 ，然后从 2或者1 开始执行。
6.5、图的最小生成树
节点数位：6
最小生成树节点为：6-1=5，其中这5点的连线不能形成回路。
6.5.1、普里姆算法
选取任意节点作为起始点
A为起始点
1、A-B 100 、A-C 400 、A-E 200 、A-F 250 最短为 :A-B 100
起始点变为 A B
2、B-C 400、B-F 300、A-C 400 、 A-F 250 、A-E：200，最短：A-E
起始节点变为 A B E
3、B-C 400 、B-F 300 、A-C 400、A-F 250、 E-F 400
最短为：A-F
起始点 A B F
4、B-C 400、F-C 400 、F-D 200
最短：F-D 200
5、B-C 400、D-C 300
最短：D-C 300
6.5.2、克鲁斯卡算法
每次选择最短的边
1、最短边：100
2、最短边：200
3、最短边：250
4、最短边：300
选择DC而不寻找BF是因为 BD会造成回路。
7、算法基础
7.1、算法的特性
7.2、算法的复杂度
7.3、查找
7.3.1、顺序查找
概念：将待查找的关键字为key的元素从头到尾与表中元素进行比较，如果中间存在关键字为key的 元素，则返回成功，否则，则查找失败。
顺序查找的时间复杂度是 O（n）
7.3.2、二分查找法
例子：
注意点：
1、用当前下标比较后，再次比较不会再用次下标，或左移或者右移一位进行比较
2、取中间值是（起点下标+终点下标）/ 2 的值取整
折半查找在查找成功时关键字的比较次数最多是：[log2 n] + 1 次数
时间复杂度为 O(log2n)
7.3.3、散列表
基本概念：已知关键子集合U，最大关键字为m，设计一个函数Hash，它以关键字的自变量，关键字的存储地址为因变量，将关键字映射到一个有限的、地址连续的区间 T[ 0…n-1] (n<<m) 中，这个区间就叫散列表，散列查找中使用的转换函数称之为散列函数。
散列表冲突解决方案：线性探测法、伪随机数发
7.3.3.1、散列表冲突解决方案：线性探测法
7.3.3.2、散列表冲突解决方案：伪随机数发
7.4 排序——重点
概念：
稳定与不稳定排序
对于相同值得排序，排序和排序的先后顺序不受影响，叫稳定排序，受影响则为不稳定排序
内排序与外排序
使用内存进行排序为内排序，使用外部存储进行排序则为外排序
分类：
7.4.1 直接插入排序
7.4.2 希尔排序
属于插入排序的一种。
7.4.3 直接选择排序
例子：
7.4.4 堆排序
概念:
总结：
小顶堆：子节点总比父节点大
大顶堆：子节点总比父节点小
基本思想：
例子1：
例子2：堆调整
对初始堆调整后，将顶点元素输出，同时将最后一个子节点替换到顶节点，并将堆进行调整，随后又输出顶节点，重复以上动作，就能达到排序输出的功能。
7.4.5 冒泡排序
概念：
通过相邻元素之间的比较和交换，将排序码较小的元素逐渐从底部移向顶部。由于整个排序的过程就像水底的气泡一样逐渐向上冒，因此称之为冒泡算法。
7.4.6 快速排序
例子：
7.4.7 归并排序
7.4.8 基数排序
概念：基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。
基数排序不是基于关键字比较的排序方法，它适合于元素很多而关键字很少的序列。
基数的选择和关键字的分解是根据关键字的类型来决定的，例如关键字是十进制数，则按个位、十位来分解。
