第一章 绪论

本章重点：数据结构相关名词术语的含义。难点：时间复杂度的估算。

数据：是客观事物的符号表示。能被输入到计算机中被程序处理的符号的总称。
数据元素：也称顶点，结点或记录。数据的基本单位。
数据项：最小单位。

数据对象：性质相同的数据元素集合。
数据结构：带结构的相同性质数据元素集合。结构是一种或多种关系。

以上不知道怎么背，随便过过吧。

逻辑结构=数据元素+关系。
四类基本结构：

• 线性结构：一对一，如线性表，栈和队列，字符串，数组，广义表
• 树结构：一对多
• 图/网状结构：多对多
• 集合结构。

后三个是非线性结构。（即四类中除了线性结构的）

两种存储结构：顺序存储（数组），链式存储（结构体和指针）。
差别：
顺序存储：相邻位置表示元素逻辑关系。
链式存储：指针信息表示元素逻辑关系。

算法：
五特性：有穷，确定，可行，输入，输出。
优劣标准：正确性，可读性，健壮性，高效性。

时间复杂度：一般是最深层循环内的语句频度。

两个没什么用的表：（？）

第二章 线性表

重难点：顺序表和链表。

概念：非空的线性表或线性结构是一个有限数据元素的有序集合。
特点：存在唯一一个第一个，最后一个数据元素；每个数据元素只有一个前驱（除第一个）和后继（除最后一个）。
存储：连续地址。是随机存储结构。

线性表
线性表的一些操作：
GetElem:
i是位置。注意特判范围。第1个存在0号位，故取值要i-1；

if(i<1||i>=L.length) return ERROR;
e=L.elem[i-1];

LocateElem:存在就返回位序，不存在就返回0；
地址从0开始，位序从1开始。故return i+1;

for(int i=0;i<L.length;i++)
{	
	if(L.elem[i]==e) return i+1;
}
return 0;

线性表查找的算法时间效率：(n+1)/2;

InSert操作：
i的合法范围：1~L.length+1;
还要判断线性表是否满了：

if(L.length==MAXSIZE) return 0;

线性表插入移动的期望值：n/2;

Delete操作：
判断范围：i的合法范围：1~L.length；

if(i<1||i>L.length) return 0;

线性表删除移动的期望值：(n-1)/2;

线性表操作	移动期望值
查找	(n+1)/2
插入	n/2
删除	(n-1)/2

链表
特点：结点位置任意，逻辑上相邻元素在物理上不一定相邻。
是顺序存取的结构。

这里的单链表都是带头结点的。

尾插法：

循环链表：
最后一个结点的指针域又指回头结点的链表。

双向链表：
插入删除都可以画这种图，就很容易知道指针的赋值变化了。

单链表总结和与线性表的比较

第三章 栈和队列

栈Stack，先进后出（像是电梯了），插入删除的一端为栈顶Top，另一端为底Bottom；

顺序栈
是利用顺序存储结构实现的栈，指针top指示栈顶在顺序栈的位置。

base为存储空间基地址，S.top-S.base 是栈中元素的个数，类似Length。
栈为空时：S.topS.base;
栈满时：S.top-S.baseMAXSIZE;
顺序栈，top在最高元素的上一个，base位置是最低元素，故取栈顶元素要取top-1的：

链栈
**没必要加头结点。**栈顶指针就是链表头指针。

关于阶乘的递归


队列
先进先出。头是front,尾是rear；

在非空队列中，头指针始终指向队头元素的位置（实位以在），尾指针指向队尾元素的下一个元素（虚位以待）。
队列为空时：Q.frontQ.rear;
初始化时都为0；
加入一个元素，Q.rear++;删去一个元素时，Q.front++;
队长：Q.rear-Q.front;
存在假上溢现象。
(Q.base是基地址)

循环队列
队长：(Q.rear-Q.front+MAXSIZE)%MAXSIZE;
队满：Q.front(Q.rear+1)%MAXSIZE;

循环队列入队更新方式：

if((Q.rear+1)%MAXSIZE==Q.front) return ERROE;//满
Q.base[Q.rear]=e;//因为是虚位以待的
Q.rear=(Q.rear+1)%MAXSIZE;

出队：

if(Q.rear==Q.front) return ERROR;//空
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXSIZE;

第五章 树和二叉树

重点：二叉树的遍历及其应用。

不特别说明，讨论的都是无序树。
树的层数：如图，4层。

二叉树
五种基本形态：

二叉树的五个性质

1、在二叉树第i层上至多有2^(i-1)个结点；
2、深度为k的二叉树上至多含2^k-1个结点；
3、对任何一颗二叉树，若他有a个叶子节点，b个度为2的结点，则a=b+1;
（即，叶子结点=2的结点+1；）
4、有n个结点的完全二叉树的深度为log2n+1；

其中除了3都可以画图简单验证，5感觉是废话

遍历二叉树
遍历：对数据结构中的每个元素都访问一次且只访问一次。

遍历的四种方法：
层次遍历：从上到下，从左到右
ABECFDGHK

以下三个演示来自：数据结构——二叉树先序、中序、后序及层次四种遍历（C语言版）

先序遍历：根->左->右

中序遍历：左->根->右
树上的结点都掉下来了

后序遍历：左->右->根

重要结论
若二叉树中的各结点的值均不同，则任意一颗二叉树的先、中、后序序列是唯一的。
先+中 或 后+中 可以唯一确定二叉树。

哈夫曼树
最优树，一类带权路径长度的最短树。

从这里学习WPL的计算方法：权值*路径长度（或者说这一层的层数） 之和。
易得：大的要近，小的要远，这样WPL就会最小。

一个哈夫曼树的生成：
W={5,6,2,7,9};
先排序：W={2,5,6,7,9};
W={6,7,7,9};
W={7,13,9};

编码的两种形式
等长：易于译码。但长度长。
不等长：不易于译码，但长度短。

哈夫曼树是不等长的二进制编码，也是最优前缀编码。

如：
W={43,14,29,14};
左0右1：

哈夫曼编码树中，若叶子结点个数为n，则总结点为2n-1。

第六章 图

重点：图的两种存储结构和构造算法，不同存储结构的特点和使用场合。
图的两种遍历算法：DFS，BFS。

图分为有向图和无向图。
有向完全图：n(n-1)
无向完全图：n(n-1)/2
稀疏图：边的个数小于nlog2n;
度：出度+入度（有向图）；
简单路径：序列中顶点不重复出现的路径。
简单回路：除第一个和最后一个相同，其他不重复。
连通图：任意两个顶点之间联通。

强连通图：有向图中任意两个顶点之间都存在一条有向路径。
否则，它的各个极大强连通子图称为它的强连通分量。

邻接矩阵
无向图的邻接矩阵为对称矩阵；
其实就是在有边的地方放1：

特点：

• 无向图的邻接矩阵对称，可压缩存储。这样，n个顶点的无向图需要的存储空间为n(n+1)/2;
• 便于计算各个顶点的度。顶点i的度为第i行元素为1的个数。

有向图的邻接矩阵：也是有边的地方1

特点：

• n个顶点需要存储空间为n^2;
• 便于计算各顶点的度：第i行1的个数是i的出度；列——入度。

网的邻接矩阵
有边就放权值，否则为无穷大。

邻接矩阵的缺点

• 不便于增删结点
• 不便于统计边的数目，要扫描整个矩阵，时间复杂度为O(n^2)
• 对稀疏图很浪费空间

邻接表
连接的是出度，一般（地址）从小到大。

无向图：

特点：

• 无向图中，每条边在邻接表中出现2次
• 空间复杂度O(n+2e)，若是稀疏图，省空间
• 不唯一，因为链入顺序任意
• i的度为第i单链表中的结点数

有向图：

特点：

• 有向图中，一条弧在邻接表只出现一次；
• 空间复杂度O(n+e)
• i的度为第i单链表中的结点数

逆邻接表
连的是入度。

画网络

地址	权值	下一个指针

邻接表特点

• 便于增删
• 便于统计边的数目，扫描整个表即可，时间复杂度O(n+e)
• 不便于判断顶点之间是否有边
• 不便于计算各个顶点的度
• 通常，稠密图——邻接矩阵；稀疏图——邻接表

图的遍历：DFS和BFS

DFS：
访问顶点，若它的邻接点未被访问，则从它出发进行深搜：

求DFS：
别拉太下，答案要出来啦！

效率分析：
邻接矩阵O(n^2);适合稠密图。
邻接表O(n+e);稀疏图。

BFS：
用队列实现的一层层的，广度优先搜索。
从V0出发，依次访问V0的所有未被访问的邻接点，之后按它们被访问的先后次序访问它们的邻接点。

例题：




注意这里67都是3后的！

14325

效率分析：
邻接矩阵O(n^2);
邻接表O(n+e);

DFS VS BFS

• 空间复杂度相同，O(n)；
• 时间复杂度与存储结构（邻接矩阵/邻接表）有关，与路径无关。

最小生成树

prim算法：
取图中任意一个顶点作为生成树的根，之后往生成树上添加新顶点w。在添加的顶点w和已经在生成树上的顶点v之间必定存在一条边，且该边的权值在所有连通vw的边中最小。
称为加点法。

克鲁斯卡尔算法：
为了使生成树上的边的权值之和达到最小，则应使生成树中的每一条边的权值尽可能地小。
从最小的边开始。给边排序，从小到大，找每一个没放入的点存在的最短边放入即可。
如：

两种算法的比较：

记法：克鲁斯卡尔是后学的，所以肯定时间更快…

最短路径：迪杰斯特拉
按照各条最短路径长度递增的次序产生最短路径。

图解
所以一开始的点是随便选的（源点），算出的路径是目标点到源点的距离
时间复杂度是O(n^2);

第七章 查找

重难点：

• 顺序表或有序表表示静态查找表时的查找方法、二叉排序树的查找方法。
• 二叉排序树的查找方法、散列表的查找方法
• 各种表示方法的适用点和适用场合。

查找表：由同一类型的记录构成的集合。

• 静态查找表：查询或检索
• 动态查找表：查询、检索、插入或删除

关键字：用以标识一个记录。可识别唯一记录的是主关键字。
如身份证号是主关键字，姓名是次关键字。

线性表的查找

1. 顺序查找
2. 折半查找

顺序查找：从头找

int Search(int a[],int e)
{
	for(int i=1;i<=length;i++)
	{
		if(a[i]==e) return i;
	}
	return 0;
}

优化过后的从尾巴找：0号位是要查找的数，如果return 0那就是没找到了。

int Search_(int a[],int e)
{
	a[0]=e;
	for(int i=length;a[i]!=e;i--){}
	return i;
}

时间复杂度O(n);
平均查找长度：(n+1)/2;

折半查找
就是二分。线性表要有序且有限。
跳出循环的条件是：找到了（a[mid]==e）或范围缩小到0也没找到.故循环条件是while**(l<=r)**；

//范围从1~n；假设是从小到大排列
int l=1,r=n,mid=(l+r)/2;
while(l<=r)
{
	if(a[mid]==e) return mid;
	else if(a[mid]>e) r=mid-1;
	else l=mid+1;

	mid=(l+r)/2;
}

折半查找的判定树深度和含有n个结点的完全二叉树深度相同。
平均查找长度和时间复杂度：

树表的查找：二叉排序树
特性：若左子树不空，则左子树上所有结点小于根节点；右子树上所有结点大于根节点；

二叉排序树的插入算法：

• 查找不成功时进行。
• 若二叉排序树为空树，则新插入的结点为新的根节点；否则为新叶子结点。
  
  插入算法时间复杂度O(log2n);

二叉排序树创建算法：
第一个就是根，之后小在左，大在右

算法时间复杂度O(nlog2n);

二叉排序树删除算法：

1. 删叶子结点
2. 删只有左/右的根节点
3. 删既有左又有右的根节点

好像不太重要，因为搜不到复习资料，别问我原理我也不知道skr

二叉排序树的查找
平均查找长度与树的形态有关。
最好log2n;(很对称的)
最坏(n+1)/2;

散列表的查找

散列表：就是哈希表~~，好像也是stl的map~~

查找的效率：取决于给定值进行比较的关键字个数。
平均查找长度：关于关键字个数的函数，不为0且随n增大而增大。
（很好理解，因为n变多，冲突就多了）

散列函数和散列地址：位置p和关键字key满足p=H（key），H——函数，p——地址。

冲突与同义词：
存在key1!=key2&&H(key1)==H(key2)，
即关键字不同地址相同，这样就产生了冲突。
这两个关键字叫做同义词

对数字的关键字的构造方法：

1. 数字分析法
2. 平方取中法
3. 折叠法
4. 除留余数法

数字分析法
事先知道关键字集合，且关键字位数相同。从中提取分布均匀的若干位或它们的组合作为散列表的地址。

123号位分布不均匀，4567分布均匀。

平方取中法
若关键字的所有各位分布都不均匀，则可取关键字的平方值中间的若干位做散列表的地址。
取平方的目的是扩大差别。

折叠法
关键字位数特别多，难直接从关键字中找到取值分散的几位。
方法：移位叠加，边界叠加。

除留余数法
假设表长m，选择一个p使p<=m，且p为素数或p不含20以下的质因子。
余数是：
H(key)=key%p;

p是小于表长，不要混成小于关键字

实际造表时，采用何种构造散列函数的方法通常考虑：

1. 散列表长度
2. 关键字长度
3. 关键字分布情况
4. 计算散列函数需要的时间
5. 记录的查找频率

总原则：使发生冲突可能性最低

处理冲突的方法
翻译：为产生冲突的地址寻找下一个散列地址

1. 开放地址法
2. 链地址法

开放地址法：
若产生冲突就按某种方式寻找下一个地址。
下一个地址的散列公式：Hi(key)=(H(key)+di)%m;

三种方法：
线性探测、二次探测、伪随机探测。
线性探测：冲突的地方+1，+2，+3…+m-1；
优点：只要散列表没满，保证能找到空位置存放。
缺点：会发生二次聚集（堆积）现象。如+1后把原本在+1的位置占了，+1的只能到+2了。

二次：+1，-1，+4，-4，+9，-9…
二次和伪随机的优点：避免二次聚集。缺点：不一定能找到不发生冲突的地址。

链地址法：
看图就知道了

优点：
无聚集现象；适合表长不确定的情况。

解决散列表查找的ASL平均查找长度的因素：

1. 选用的散列函数
2. 处理冲突的方法
3. 饱和程度，即装填因子：α=记录数/表长度

装填因子越大，装的越满，冲突可能性越大，ASL越大。

假设散列函数是均匀的，则ASL只取决于解决冲突的方法和装填因子。

开放地址法的装填因子必<1，不能接近1，大概在0.75；
链地址的装填因子可>1;

总结
散列表的ASL是α的函数。
用散列表查找时，不管n多大，总可以选择适当的α使ASL在某范围内。

第八章 排序

重点：
快速排序，堆排序，归并排序。

内部排序是一个逐步扩大记录有序序列长度的过程。

排序算法效率评论指标：

1. 时间效率（比较与移动次数）
2. 空间效率（辅助空间的大小）
3. 稳定性（AB关键字相等，排序后AB的次序不变则稳定）

直接插入排序
是插入类排序。
步骤：

1. 在r[1…r-1]中顺序查找r[i]的插入位置使r[i…j].key<=r[i].key<=r[j+1…i+1].key
2. 将r[j+1…i+1]中所有记录向后移
3. 将r[i]插入（复制）到r[j+1]的位置上
   有序的范围：1到r-1，r是待插入的

时间复杂度O(n^2);
空间复杂度O(1);
是稳定排序，适用于链式，更适用于基本有序的情况。
无序且n大时不适合。

冒泡排序
是交换类。

动图源自：这里

大致的循环：是1和2比，再2和3，3和4…每一趟确定的是最大的。

for(int i=1;i<=n-1;i++)
	for(int j=i;j<=n-1;j++)
	{
		//j和j+1的比较
	}

特点：
稳定，可用于链式，移动次数多。

第一趟确定最大的，第二趟确定第二大的…以此类推，大泡泡会沉底

快速排序
交换类。
动图来自：这里：以下动图均来自这里

如：
枢纽是：49—27—76；
逻辑大概是：第一次枢纽是第一个数，第二次是第一堆的第一个数，第三次是第二堆的第一个数

简述：枢纽暂放杂r[0]中，比枢纽小的移到枢纽前，大的后。

做了个小视频，是上面例子的快排示范，但是放不下orz

快排时间复杂度O(nlog2n)
空间复杂度：最好O(log2n),最坏O(n)

不稳定。要用在顺序结构。适合记录无序，n较大的情况。

简单选择排序
选择类，即选出一个关键字最大/小的记录，并移到法定位置。

例子：
这里选的是无序中最小的放入有序中。


时间复杂度O(n^2);
空间复杂度O(1);
不稳定。可顺序可链式结构。
移动记录次数较少，比直接插入快。

堆排序

堆排序是利用堆的特性对记录序列进行调整堆的排序方法。

动图：

时间复杂度O(nlog2n);
空间复杂度O(1);
不稳定。只可顺序。
适用于n较大或TOPN问题。

归并排序
将两个或以上有序子序列归并为一个有序序列。

代码：若要从小到大：小的就往下放并移动指针，直到有一条到结尾，另一条直接接上：

举个例子：两两比较！

时间复杂度：O(nlog2n)
空间复杂度：O(n);
稳定，可链式。
要额外空间！

排序的综合比较
选择何种排序方式考虑原则：

1. 待排记录个数n
2. 记录本身大小
3. 关键字分布情况
4. 稳定性要求

红框框要考。