- 绪论
- 数据结构的分类
- 数据结构研究的内容
- 算法的重要特性
- 算法的设计要求
- 题目汇总
- 线性表
- 栈和队列
- 栈
- 队列
- 题目
- 树
- 二叉树
- 二叉树的遍历
- 线索二叉树
- 线索二叉树的查找
- 查找
- 静态查找表
- 顺序查找
- 二分查找（折半查找）
- 分块查找
- 动态查找表
- 二叉排序树
- 删除操作
- 平衡二叉树
- 哈希表
- 1、开放地址法
- 2、链地址法
- 排序
- 按数据元素之间的关系分：线性结构和非线性结构。‘
- 按逻辑结构分：集合结构，线性结构，树型结构，图型结构。
- 按存储方式分：顺序存储、链式存储、索引存储结构、散列存储结构。
逻辑结构、存储结构和操作。
算法的重要特性有穷性、确定性、可行性、输入、输出。
算法的设计要求正确性、可读性、健壮性、效率与低存储量要求。
题目汇总- 二元组 Date = (D,S) : D 表示 数据元素的有限集 ，S 表示D上的关系的有限集。
- 数据元素相互之间的关系称为 ：结构。
- 非线性结构是元素之间存在一种 ： 多对多关系。
- 算法分析的目的是：分析算法的效率以求改进。
- 计算机算法指的是：解决问题的有限运算序列。
- 在顺序表中插入和删除一个结点平均移动多少个结点：在等概率情况下，顺序表中插入一个结点需要平均移动n/2个结点。删除一个结点需要平均移动（n-1）/2个结点。
原因：1、当对n个元素进行插入操作时，有n+1个位置可以进行插入，如下所示（“.”代表可以插入的位置）。
.1.2.3.4. －－ .n.
在每个位置插入时需要移动的元素个数分别为n,n-1,n-2…,1,0，所以，总共需要移动的元素个数为(1+2+3+4+…+n)=n*(n+1)/2。
故平均需要移动的元素个数为n*(n+1)/2(n+1)=n/2;
2、当对N个元素进行删除操作时，有N个位置可以删除。
1,2,3,4…n
每个位置需要移动的元素个数分别为n-1,n-2,n-3…1,0个。所以平均需要移动的元素个数为(n-1)n/2n=(n-1)/2个。 - 任意单元的地址： a i = a 1 + ( i − 1 ) d a_i = a_1 + (i - 1) d ai=a1+(i−1)d
- 在一个长度为n的顺序表中，在第i个元素之前插入一个元素 ，需要向后移动：n - i + 1 个元素。原因：第i个元素之前那么后边元素为i~n ，那么n - i 得到的是是i后边的元素个数，因此加上i ， 故为 n - i + 1 。
- t指向最后一个元素的意思是，t就是最后一个元素的指针，切记。
- 在一个长度为n的顺序表中，删除第i个元素 ，需要向前移动：n - i 个元素。原因：第i个元素之前那么后边元素为i+1~n ，那么n - (i + 1 ) 得到的是是i+1后边的元素个数，因此加上i+1这个元素 ， 故为 n - (i + 1 ) + 1 = n - i 。
- 对于顺序表，设base 为栈底指针，top为栈顶指针，则判断栈空的条件是：base == top ，栈中元素个数 top - base.(当栈顶指针指向当前栈顶元素)
- 当栈顶指针指向当前栈顶元素，那么插入（进栈）操作是 ：top++ , base[top] = val, 退栈操作是：top--; 当栈顶指针指向栈顶元素的下一个位置，那么 进栈操作是base[top] = val , top++ , 退栈操作是 top--。感觉没啥用，不过就是这样。。。
- 在循环队列中，队空标志为front == rear , 队满标志为：(reat + 1 ) % m == front ; 当 rear >= front 时 ，队列长度为 rear - front , 反之 为 (rear + m - front) % m
- 带头结点的链队列Q ， 判定队列中只有一个元素的条件是：Q.front - > next = Q.rear
- 顺序队列 ，对于一个一维数组 ，有两种实现方法，一种是 front 与 rear 最初同时指向一个位置（一般是0） 即rear 指向的是队尾下一个元素的位置， 那么 进队操作是 ：q[rear] = val , rear++ , 出队操作是：if(front < rear) front ++ 对空操作是 ：rear == front; 另一种实现方式是 front = 0 ,rear = - 1 ; 即rear 指向的是队尾元素的位置. 进队操作：q[++rear] = val , 出队操作是：if( front <= rear) front++
- 对于链式队列 ， 起初 front 和 rear 指针同时指向一个起始地址 ， 入队操作：p->data = val , p->next = NULL , Q.rear->next = p ; Q.rear = p; 所以 rear 指针指向的是队尾元素的位置 ， 判断对空操作：Q.rear == Q.front
- 空间大小为n 的循环队列 ，执行出队操作后，front = (front+1) % n
- 对于完全二叉树，如果节点个数为奇数，那么就不存在度为1的节点。当节点个数为偶数的时候，当且仅当存在一个度为1的节点。
- 二叉树的第k层最多有 2 k − 1 2^{k-1} 2k−1 个节点。因为第1层即根节点有 2 0 2^{0} 20 ，而下一层最多是上一层的两倍。
- 高度为k的二叉树最多有 2 k − 1 2^{k} - 1 2k−1个节点。依次为 2 0 、 2 1 . . . . 2 k 这 是 一 个 首 项 为 1 公 比 为 2 ， 项 数 为 k 的 等 比 数 列 2^0 、2^1 .... 2^k 这是一个首项为1 公比为2，项数为k的等比数列 20、21....2k这是一个首项为1公比为2，项数为k的等比数列
- 对于任意一颗二叉树， n 2 为 度 为 2 的 节 点 ， n 1 为 度 为 1 的 节 点 ， n 0 为 度 为 0 得 节 点 （ 即 叶 子 ） n_2 为度为2的节点 ， n_1 为度为1的节点 ， n_0 为度为0得节点（即叶子） n2为度为2的节点，n1为度为1的节点，n0为度为0得节点（即叶子） 那么有如下关系： n 0 = n 2 + 1 n_0 = n_2 + 1 n0=n2+1。
- 具有n个节点的完全二叉树，数的高度 ：
k
=
⌊
log
2
n
⌋
+
1
k = lfloor log_{2}{n} rfloor+1
k=⌊log2n⌋+1。因为完全二叉树有一个性质是高度为k的树，那么k-1 层往上是满二叉树。那么 k-1 层以上包括k-1 层的节点个数为
2
k
−
1
−
1
2^{k-1} - 1
2k−1−1 ，那么有节点个数n ，
2
k
−
1
−
1
<
n
<
=
2
k
−
1
2^{k-1} - 1 < n <= 2^{k} - 1
2k−1−1
- 对于节点个数为n的完全二叉树，编号为i 的节点 ，如果 2i > n ,那么节点i无左孩子，如果 2i +1 > n , 那么节点i无右孩子。
二叉树的各种遍历方法
先序：根、左、右
中序：左、根、右
后序：左、右、根
- 有二叉树的先序、中序 或者 后序、中序 的结果才可以唯一确定一颗树。因为先序和后序的作用是得到根节点的位置，而中序是确定节点的左右次序。
给定二叉树先序和中序画出二叉树
先序数列：ABDGHCEFI
中序数列：GDHBAECIF
先序序列的第一个值为根节点：A为根节点
再到中序数列中找到根节点，以根节点A为界分为左右两部分，左：GDHB、右：ECIF
在先序序列找到与中序数列左右部分对应的序列部分，左：BDGH、右：CEFI，可得到左边结点为B，右边结点为C
分别对左子树和右子树进行上述操作，左子树（先序：CEFI，中序：ECFI）以C为界限分为 左：E、右：IF，因为先序序列F在I前所以F在I上一层，因为中序数列I在F前面，所以I在左分支；右子树（先序：BDGH，中序：GDHB）以B为界限分为左：GDH，因为先序中D在第一个，所以D为第一个结点针对（先序：DGH，中序：GDH）重复上述方法可得：
由上面后序的节点排布得知，后序和中序与其类似，只不过是最后一个节点是根节点。
二叉树的基本操作
线索二叉树- 对于用二叉链存储的二叉树，如果有n个节点，那么 会有 n + 1 个空指针。由 n = n 0 + n 1 + n 2 与 n 0 = n 2 + 1 得 到 n = 2 n 0 + n 1 + 1 n = n_0 + n_1 + n_2 与 n_0 = n_2 + 1得到 n = 2n_0+n_1+1 n=n0+n1+n2与n0=n2+1得到n=2n0+n1+1，那么由一个度为0的节点会有两个空指针，度为1的有一个空指针。所以上式 将1往左移即得到结果： n + 1 = 2 n 2 + n 1 n + 1 = 2n_2 + n_1 n+1=2n2+n1
线索二叉树的查找何为线索二叉树呢? 就是在原来二叉树的基础上，如果左孩子为空，那么就将这个左孩子指向该节点的前驱，同理 右孩子是指向该节点的后继。**那么什么叫节点的前驱和后继呢？**我们的线索二叉树分为前序线索二叉树，中序线索二叉树和后序线索二叉树。顾名思义，一个节点的前驱和后继就是按照遍历的方式，得到一个遍历的序列，在这个序列里边再该节点前边的节点就是其前驱，后边即后驱。
- 在中序线索二叉树中查找给定节点的前驱节点
分为两种情况考虑。
1、如何该节点的左标志为1，即无左孩子，那么其左指针域指向的节点便是它的前驱节点。
2、如何该节点的左标志为0，即有左孩子，那么它的前驱节点则沿着左子树的右指针链（左子树的右孩子）向下寻找，直到找到一个没有右孩子的节点为止，即此时右标志为1的节点就是我们要找的前驱节点。即左子树中“最右下”的节点。
- 在中序线索二叉树中查找给定节点的前驱节点
与查找前驱类似，也是有两种情况，第一组太简单一般不会考。第二种情况，类比与前驱，右子树中“最左下”的节点。
这里可能有人会问为什么只讲了，中序呢？难道只考中序的查找嘛？
对的，对于这一类问题只会考中序线索二叉树。原因是查找先序前驱和后继节点和后序前驱和后继节点常常要用到该定节点的双亲节点才能找到，而线索二叉树中的节点没有指向其双亲节点的指针。
讨论的是从后往前查找的方式。
- 查找第i个元素 需要比较 n − i + 1 n - i +1 n−i+1次，则查找成功的平均查找长度为 A S L s s = 1 n ∑ i = 1 n ( n − i + 1 ) = n + 1 2 ASL_{ss} = frac{1}{n} sum_{i=1}^n (n - i +1) = frac{n + 1}{2} ASLss=n1∑i=1n(n−i+1)=2n+1
折半查找成功或失败的平均查找长度
分块查找 动态查找表 二叉排序树二叉排序树的介绍
二叉排序树为一颗二叉树，或者为空，或者满足如下条件：
- 如果它的左子树不为空，那么左子树上的所有结点的值均小于它的根结点的.值
- 如果它的右子树不为空，那么右子树上的左右结点的值均大于它的根结点的值
- 根结点的左子树和右子树又是二叉排序树。
二叉排序树通常采用二叉链表作为存储结构。中序遍历二叉排序树便可得到一个有序递增序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即是对无序序列进行排序的过程。
- 对于一个给定的二叉搜索树，平均查找长度：这和折半查找的平均查找长度的计算是一样的，可以参考上面的方法。
删除分为三种情况。
- 删除结点为叶子结点（左右子树均为NULL），所以我们可以直接删除该结点，如下图所示：
- **删除结点只有左子树或者右子树。**此时只需要让其左子树或者右子树直接替代删除结点的位置，称为删除结点的双亲的孩子，就可以了，如下图所示：
- **当要删除的那个结点，其左右子树都存在的情况下，**则要在中序遍历中将该节点（p）的前驱节点（s）的值替代该节（p）的值再删除s节点。即从从左子树中找出一个最大的值那个结点来替换我们需要删除的结点，因为对于二叉排序树中序遍历得到的是一个递增的序列那么在p节点的前驱即时其左子树中的最大值，即如下图所示：
平衡二叉树的构造
哈希表重点考察的是在解决冲突这块。因此我们重点讲解这里。
一般来说有两种类型的解决方法：
1、开放地址法散列地址的计算公式是：
H
i
=
(
H
(
k
e
y
)
+
d
i
)
)
m
o
d
m
(
i
=
1
,
2
,
.
.
.
,
k
(
k
<
=
m
−
1
)
)
H_i = (H(key) + d_i)) modquad m (i = 1,2,...,k ( k <= m-1))
Hi=(H(key)+di))modm(i=1,2,...,k(k<=m−1))
其中H（key）为哈希函数；m为散列表的长度 ；
d
i
d_i
di为第i次探测时的增量序列。
d
i
可
以
有
下
列
3
种
取
法
d_i可以有下列3种取法
di可以有下列3种取法，下面只介绍常考的两种。
- 线性探测再散列
d i = 1 , 2 , . . , m − 1 d_i = 1,2,..,m-1 di=1,2,..,m−1它是从发生冲突的d单元起，依次探查下一个单元，直到碰到一个空闲单元为止。 - 二次探测再散列
d i = 1 2 , − 1 2 , 2 2 , − 2 2 . . . . ( + − ) k 2 ( k < = m / 2 ) d_i = 1^2, - 1^2 , 2^2,-2^2 .... (+-) k^2 (k<=m/2) di=12,−12,22,−22....(+−)k2(k<=m/2) ,当发生冲突时，在表的左右进行跳跃探测。
