第一章 绪论

数据结构定义、数据逻辑结构的分类、两类物理存储方式及特点、时间复杂度的计算。

1.数据结构定义

数据结构(Data structure)： 相互之间存在一种或多种特定关系的数据元素的集合。

程序=算法+数据结构

2.数据逻辑结构的分类

集合：结构中的数据元素除了同属于一种类型外，别无其它关系。

线性结构：结构中的数据元素之间存在一对一的关系

树型结构：结构中的数据元素之间存在一对多的关系。

图状结构或网状结构：结构中的数据元素之间存在多对多的关系。

3.两类物理存储方式及特点

顺序存储结构（顺序映像）：逻辑相邻的元素物理存储位置相邻；
链式存储结构（非顺序映像）：逻辑相邻的元素物理存储位置无关。

4.时间复杂度的计算

时间度量方法：
语句执行的频度（次数）
是问题规模的函数

image-20211223175619281

补充：

image-20211223174920624

第二章 线性表

线性表的定义、非空循环单链表的特点；顺序表中插入、删除操作移动元素的个数；单链表的插入与删除操作时间复杂度计算，双向循环链表插入结点操作。

1.线性表的定义

定义： 0个或多个数据元素组成的有限序列。
L=（a1,..., ai-1, ai, ai+1, ..., an）

2.顺序表中插入、删除操作移动元素的个数

插入移动元素：n-i+1个元素的后移

删除移动元素：n-i 个元素的前移

补充：

删除元素的算法 算法时间主要耗费在移动元素的操作上

假设删除元素的位置是随机等概率的，即概率为 1/n，则平均移动次数（期望值）为：(n-1)/2

3.非空循环单链表的特点

从任意结点开始，可以找到表中其他结点。

4.单链表的插入与删除操作时间复杂度计算

均不需移动元素，时间复杂度为O(1)

5.双向循环链表插入结点操作

image-20211223205327768

第三章 栈和队列

栈和队列的逻辑特性，顺序栈的出栈、入栈，栈的常见应用，循环顺序队列出队和入队操作时队首队尾指针变化，循环顺序队列如何判队空、判队满、求队中元素个数。

1.栈和队列的逻辑特性

栈(stack)：只允许在序列一端进行操作的线性结构类型

栈的操作特点：后进先出

队列(queue)：只允许在序列两端进行操作的线性结构类型

队列的特点：先进先出

栈和队列统称为“操作受限”的线性结构

2.顺序栈的出栈、入栈

image-20211223212017576

image-20211223212032631

补充：

image-20211223211207398

InitStack：初始化空栈
Push：进栈／入栈
Pop：出栈／弹栈
GetTop：读栈顶元素
StackEmpty ：判断栈是否为空
StackLength：返回栈的长度

3.栈的常见应用

image-20211223212214232

4.循环顺序队列出队和入队操作时队首队尾指针变化

//循环队列入队：

int EnQueue(SqQueue &sq,int x)//入队
{
    if((sq.rear+1)%MaxSize==sq.front)//判断队满
    {
            return 0;
    }
    sq.rear = (sq.rear+1)%MaxSize;//就相当于往上偏离了一个位置满了就会到初始的位置，因为模除循环
    sq.data[sq.rear] = x;//把值写入
    return 1;
}
//循环队列出队：

int DeQueue(SqQueue &sq,int *x)
{
    if(sq.rear==sq.front){//判断队空
            return 0;
    }
    sq.front = (sq.front+1)%MaxSize;//就相当于往下偏离了一个位置满了就会到初始的位置因为模除
    *x =sq.data[sq.front];
    return 1;
}

5.循环顺序队列如何判队空、判队满

font：队头

rear：队尾

Q.rear == Q.front 认为队空

(Q.rear+1)% Q.maxSize == Q.front 则认为队满 //因为是循环队列

6.求队中元素个数

if(Q.rear>Q.front)
    length = Q.rear – Q.front;
else//如果rear大于maxsize即到了新的循环
    length = Q.maxSize + Q.rear – Q.front;

第四章 串

串的定义，空串和空格串的区别，了解串的模式识别算法。

1.串的定义

串是由零个或多个字符组成的有限序列，一般记为 s=‘a1a2…an’ (n≥0)

相关概念：
串的长度：串中字符的个数；
空串：长度为0的串；
空格串：由若干空格组成的串；
子串：串中任意个连续的字符组成的子序列称为该串的子串，该串称为子串的主串；
位置：字符在序列中的序号称为该字符在串中的位置。

2.空串和空格串的区别

空串：长度为0的串；
空格串：由若干空格组成的串；

3.了解串的模式识别算法

BF算法（又称古典的、经典的、朴素的、穷举的）
KMP算法（特点：速度快）

BF算法

若n为主串长度，m为子串长度，最坏情况下的比较次数：

(n-m+1)*m
若m<<n，则算法复杂度O(n*m)

int  Index(Sstring S,Sstring T,int pos){
    i=pos;   j=1;
   while (i<=S[ 0 ] && j <=T[ 0 ]){ //s0t0表示的应该是字符串的长度
       if ( S[ i ]==T[ j ]) 
               {++i;
             ++j;}
       else  //检测到不同的字符就退回
               {i=i-j+2;
              j=1;}
   }
  
   if ( j>T[ 0 ])   return   i－T[0];
   else return 0;
}

第五章 数组和广义表

数组和广义表的定义，二维数组按行（列）优先地址的计算；上三角矩阵按列（行）优先存放地址的计算；广义表的定义及求表头、表尾操作。

1.数组和广义表的定义

数组：

编程语言中的数组
是一组同型数据的顺序存储结构；
数据结构中的数组
是一个逻辑概念；

一维数组：同型元素为数据元素的线性表；
多维数组：同型线性表为数据元素的线性表。

广义表：

广义表（列表）： n (>=0)个表元素组成的有限序列，记作LS = (a1, a2, …, an)

ai的两种形态：广义表(子表)、数据元素(原子)。

2.二维数组按行（列）优先地址的计算

以行序为主序：

LOC(i,j)=LOC(0,0)+(n*i+j)*L
0<=i<=m-1, 0<=j<=n-1

以列序为主序：

LOC(i,j)=LOC(0,0)+(j*m+i)*L
0<=i<=m-1, 0<=j<=n-1;

3.上三角矩阵按列（行）优先存放地址的计算

image-20211223230037019

4.广义表的定义及求表头，表尾操作

广义表（列表）： n ( >= 0 )个表元素组成的有限序列， 记作LS = (a1, a2, …, an)
ai的两种形态：广义表(子表)、数据元素(原子)。

广义表表头是元素或广义表，不用加括号

广义表表尾只能是广义表，必须加括号

第六章 树和二叉树

树和二叉树的定义、结点的度、树的度、树的高度（深度）、完全二叉树、满二叉树的概念；二叉树的五个性质；二叉树的先序、中序、后序遍历，普通树结点个数、度、和分支数的关系；树和二叉树、森林和二叉树之间的转换及其遍历方法的对应关系；二叉链表存储线索二叉树的空指针个数，线索二叉树中序遍历方法，Huffman树的特点、构造方法、利用Huffman树求Huffman编码的方法。

1.树和二叉树

树：一对多的关系，顶层只有一个元素，各分支不相交

二叉树：

二叉树是n（n≥0）个结点（元素和向下的分支）构成的集合，它或为空树（n = 0），或为非空树T：
（1）有且仅有一个根（root）结点/顶层结点
（2）其余结点被划分为最多两个互不相交的子集L和R
（3）L和R也是一棵二叉树，分别称为左子树和右子树；左右子树也可以是空树

二叉树是有序树！

结点度：结点拥有子结点的数量

树的度：树的度指其中结点的度最大值。

结点的层次: 从根结点开始定义，根为第1层，根的孩子为第2层，如此计数，直到该结点为止。

树的高度（深度）：树中结点的最大层次

完全二叉树：每个结点的编号和满二叉树中编号为 1 至 n 的结点一一对应，称该树为完全二叉树。

image-20211224140922356

完全二叉树叶子节点的个数：n0 = ⌊（n+1）/2⌋ （向下取整）

满二叉树：每层都“充满”了结点

image-20211224140932232

2.二叉树的五个性质

1）在二叉树的第i层上至多有2i-1个结点(i>=1)

2）深度为k的二叉树至多有2k-1个结点。

3）对于任意一棵二叉树，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0 = n2+1

4）具有n个结点的完全二叉树的深度为└log2n┘+1（向下取整）

5）对于含n个结点的完全二叉树中编号为i（1≤i≤n）的结点：

（1） 对于i>1的每个结点，其双亲的编号为 i/2 ；
（2）对于2i<=n的每个结点，其左孩子的编号为2i，否则没有左孩子；
（3）对于2i+1<=n的每个结点，其右孩子的编号为2i+1，否则没有右孩子。

3.二叉树的先序、中序、后序遍历

先序遍历(DLR)：先访问根结点，再先序遍历左子树，最后先序遍历右子树
中序遍历(LDR)：先中序遍历左子树，再访问根结点，最后中序遍历右子树
后序遍历(LRD)：先后序遍历左子树，再后序遍历右子树，最后访问根结点

4.普通树结点个数、度、和分支数的关系

树的总分叉数=结点总度数

结点数=分叉数+1

叶子数为结点度数为0的结点（没有子结点）

1.设树T的度为4，其中度为1，2，3，4的节点个数分别为4，2，1，1，则T中的叶子数为？

解：

叶子的度数为0；那么设叶子数为x，则此树的总分叉数为1x4+2x2+3x1+4x1=15；此树的节点个数为16(此处涉及到一个公式;节点数=分叉数+1，由图形便可以观察出来)。又根据题目可以知道顶点数目还可以列出一个式子：4+2+1+1+x便可以得到等式：4+2+1+1+x=16；x=8为叶子数。

5.树和二叉树、森林和二叉树之间的转换及其遍历方法的对应关系

树与二叉树间的转换：第一个孩子作为左孩子，第一个右兄弟作为右孩子。

image-20211224161704896

森林与二叉树的转换：每棵树的树根当作兄弟，第一棵树的根作为转换二叉树的根

第一个孩子作为左孩子，第一个右兄弟作为右孩子。

image-20211224162644800

树的遍历：

先根遍历：根、（先根遍历）每棵子树
后根遍历：（后根遍历）每棵子树、根

将树转化为二叉树后：
树的先根遍历可借用二叉树的先序遍历算法实现;
树的后根遍历可借用二叉树的中序遍历算法实现。

森林的遍历

image-20211224163513614

image-20211224163537029

森林的先序遍历即为其对应的二叉树的先序遍历
森林的中序遍历即为其对应的二叉树的中序遍历

6.二叉链表存储线索二叉树的空指针个数

二叉树所有空指针的个数为n+1是众所周知的事(n为二叉树结点个数)

7.线索二叉树中序遍历方法

中序线索化思路
1、先线索化左子树
2、找到线索化的起始点—当前节点的左节点为空 node.getLeft() == null
3、然后把当前节点右指针指向前驱结点
4、在处理后继结点，并把前驱结点的右指针设置为当前节点
5、最后把当前节点设置为前驱结点
6、线索化右子树
中序线索化遍历思路
1、 先找到线索化的起始点
2、输出当前节点信息
3、然后寻找当前结点的后继结点，并输出

8.Huffman树的特点、构造方法、利用Huffman树求Huffman编码的方法

特点：

具有n个叶子结点的二叉树中，带权路径长度最小的二叉树，也称为最优二叉树。

Huffman树特点：没有单分支结点
总结点数=2xn-1
根权值=叶子权值和

构造赫夫曼树：

①两棵树合并时，总是合并森林中根结点权值最小的两棵；②每构造一次，F中少一棵树；③n个权值经过n-1次构造完成。

综合规则1和规则2，以报文中n个字符作为叶子结点构造赫夫曼树后进行编码，得到的编码称为赫夫曼编码（最优前缀编码）。
编码过程：（1）构造赫夫曼树；（2）为赫夫曼树中的每个分支进行编码，左分支为“0”，右分支为“1”，（3）从根出发，到达每个叶子结点所经过的路径上的编码组合，作为该叶子结点的编码序列。

image-20211224220747233

第七章 图

图的定义、结点度的计算。无向图的连通分量的概念，图的深度和广度优先遍历方法；图(或网)的存储（邻接表、邻接矩阵）方法及特点；最小生成树的概念及求法，拓扑排序和关键路径求法。

image-20211224223803425

1.图的定义、结点度的计算

图：Graph=(V,E)
V：顶点(数据元素)的有穷非空集合；
E：边（关系）的有穷集合。
图中任意两个顶点间都可能有关系，是一个多对多的结构。

2.无向图的连通分量的概念

首先要清楚什么是无向图，在图的结构中每两个点之间最多只有一条线，这条线即代表了由a指向b，也代表了由b指向a，连通分量的概念：

image-20211224223335259

在上图中连通分量就是4.所以说连通分量就是在图中非连通子图的数量。

连通图的连通分量只有1个

n个顶点的无向图连通分量最多n个，最少1个

3.图的深度和广度优先遍历方法

https://www.cnblogs.com/nr-zhang/p/11236369.html

深度遍历：一条路走到头，再回退的过程中遇到分叉再走进去

广度遍历：先找出所有跟开始节点间隔0层的结点，再找出所有跟开始结点间隔一层的结点....

空间复杂度相同，都是O(n)(借用了堆栈或队列）

时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。

4.图(或网)的存储（邻接表、邻接矩阵）方法及特点

邻接表存储法：

使用一维数组存储顶点信息；
对每个顶点vi 建立一个单链表，把与vi相关联的边链接起来；
将单链表的头指针与对应的顶点vi一起存储。

image-20211224230325817

包含e条边的无向图的邻接表中有 2e个边结点。

包含e条边的有向图的邻接表中有 e 个边结点

image-20211224230501312

数组表示法（邻接矩阵表示法）:
一维数组存储顶点信息、 二维数组存储边/弧的信息

image-20211224225115905

第i个顶点的出度=第i行元素之和
第i个顶点的入度=第i列元素之和
第i个顶点的度=出度 + 入度

无向图的邻接矩阵是对称的；
顶点i 的度＝第 i 行（或第i列）元素之和

完全图的邻接矩阵：对角元素为0，其余1

image-20211224225800362

5.最小生成树的概念及求法

生成树：一次遍历过程中访问的顶点和访问时经过的边构成的集合

普里姆(Prim)算法

image-20211224232647734

Prim算法的时间复杂度为O(n^2)，与图中的边数无关，故十分适合于稠密图

克鲁斯卡尔(Kruskal)算法

1)首先将边按照权重由小到大排序，记录边两侧的节点信息

2)再从上到下依次将边回填入图中

3)每进行一次回填，就检测图中是否有成环部分，若有则跳过这条边

4)当图中边的总个数等于总结点个数-1时，完成最小二叉树的构建

T(n) = O(nlog2n),适用于边少的稀疏图

6.拓扑排序和关键路径求法

拓扑排序：

在AOV网络中选一个没有直接前驱（入度为0）的顶点, 并输出之;
从图中删去该顶点, 同时删去由它出发的所有弧;
重复以上两步, 直到：全部顶点均输出

注意：

排序结束后若还有未输出的顶点：拓扑排序失败
拓扑排序失败的AOV网络中必定存在回路/环。

关键路径：

https://www.bilibili.com/video/BV1kK4y1W7Zu

源点：开头的点

汇点：结尾的点

image-20211225005328761

8D31908829925F731712275E7C14C97E

关键路径可能不止有一条

第九章 查找

顺序表查找的平均查找长度，二分（折半）查找的过程及查找失败时的比较次数，动态查找和静态查找的概念，二叉排序树的平均查找长度、平衡二叉树的定义及构造，哈希表的构造（除留余数法）、解决冲突的方法（线性探测再散列法、二次探测再散列法），哈希查找的查找成功时平均查找长度(ASL)的计算。

1.顺序表查找的平均查找长度

ASLs(n)=(1+2+ ... +n)/n =(n+1)/2

查找不成功时的平均查找长度：ASLf =n+1

平均查找长度为：

image-20211225091100505

2.二分（折半）查找的过程及查找失败时的比较次数

设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为待查找值
初始时，令low=1,high=n
计算mid=|(low+high)/2|向下取整
让k与mid指向的记录比较
若k==R[mid].key，查找成功
若k<R[mid].key，则high=mid-1
若k>R[mid].key，则low=mid+1
重复1、2步,直到low>high，查找失败

查找成功的情况下最多比较几次？

h = |log2 n | + 1

查找成功时的平均查找长度：

image-20211225091643380

查找失败时的比较次数：

|log2n|+1

3.动态查找和静态查找的概念

静态查找就是我们平时概念中的查找，是“真正的查找”。之所以说静态查找是真正的查找，因为在静态查找过程中仅仅是执行“查找”的操作，即：（1）查看某特定的关键字是否在表中（判断性查找）；（2）检索某特定关键字数据元素的各种属性（检索性查找）。这两种操作都只是获取已经存在的一个表中的数据信息，不对表的数据元素和结构进行任何改变，这就是所谓的静态查找。

动态查找

看到上面静态查找的概念，动态查找就很好理解了，个人总觉得动态查找不像是“查找”，更像是一个对表进行“创建、扩充、修改、删除”的过程。动态查找的过程中对表的操作会多两个动作：（1）首先也有一个“判断性查找”的过程，如果某特定的关键字在表中不存在，则按照一定的规则将其插入表中；（2）如果已经存在，则可以对其执行删除操作。动态查找的过程虽然只是多了“插入”和“删除”的操作，但是在对具体的表执行这两种操作时，往往并不是那么简单。

4.二叉排序树的平均查找长度

平均查找长度和二叉排序树的形态有关：
最好：log2(n+1)（形态匀称，与二分查找的判定树相似）
最坏: （n+1)/2（单支树）

5.平衡二叉树的定义及构造

建立形态均匀的二叉排序树：让二叉排序树左右子树差不多高

结点的平衡因子：左、右子树高度差；
平衡二叉树：所有结点的平衡因子绝对值≤1的二叉排序树，即二叉排序树中每个结点的平衡因子只可能为：-1、0、1。

按照二叉排序树的规则进行结点的插入，新插入的结点平衡因子为0；
每插入一个结点后，从插入位置开始往上，重新计算其祖先的平衡因子；
当某个结点“失衡”后，根据旋转法则进行调整。

**LL平衡旋转
RR平衡旋转
LR平衡旋转
RL平衡旋转**

6.哈希表的构造（除留余数法）

H(key) = key % p ， (p≤m)
m：映射地址区间长度——哈希表长
%: 求余操作
p：不大于m的整数，p一般取接近m的质数或不包含小于20的质因子的合数

image-20211225125404391

7.解决冲突的方法（线性探测再散列法、二次探测再散列法）

image-20211225130305761

image-20211225130324448

8.哈希查找的查找成功时平均查找长度(ASL)的计算

平均查找长度ASL取决于：
　　哈希函数
　　处理冲突的方法
　　哈希表的装填因子

image-20211225130700837

image-20211225131002109

第十章 排序

排序的分类，冒泡排序、直接插入排序、堆排序、希尔排序、简单选择排序、快速排序的排序过程；堆排序的适用情况；各类排序算法的稳定性及时间和空间复杂度。

https://blog.csdn.net/weixin_60954394/article/details/121431922

1.排序的分类

插入排序
交换排序
选择排序
归并排序
基数排序

image-20211225131435830

2.冒泡排序

基本思想

从待排序列的首元素开始，从前往后依次进行比较，

若大于则交换，将其继续与后面元素比较，直到被放至正确位置。

否则迭代至与其比较的元素，重复上面的步骤。

动图演示

img

代码实现

void Swap(int* px, int* py)
{
    int tmp = *px;
    *px = *py;
    *py = tmp;
}
 
void BubbleSort(int* a, int n)
{
    for (int j = 0; j < n; j++)
    {
        for (int i = 0; i < n - j - 1; i++)
        {
            if (a[i] > a[i + 1])
            {
                Swap(&a[i], &a[i + 1]);
            }
        }
    }

3.直接插入排序

基本思想

每次从一个有序序列开始，将待排元素与有序序列中的元素从后往前逐个比较，

若有序序列中的元素大于待排元素，则将较大的元素往后覆盖；

否则，将待排元素插入其前面，并结束此轮比较。

动图演示

img

代码实现

void InsertSort(int* a, int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int end = i;
        int x = a[end + 1];
        while (end >= 0)
        {
            if (a[end] > x)
            {
                a[end + 1] = a[end];
                end--;
            }
            else
                break;
        }
        a[end + 1] = x;
    }
}

4.堆排序

利用堆完成排序的时间复杂度：T(n) = O(nlog2n)

从第n/2个元素起，至第一个元素止，进行反复筛选

1.建大顶堆结束后，将堆顶元素与堆中最后一个元素互换；
2.“删除最后一个元素”后，对新的根结点进行筛选，得到新的堆，新堆的堆顶即为次大值；
3.重复上面的两步，直到排序完成。

5.希尔排序

基本思想
先选定一个整数作为 gap ,将待排序列以 gap 为间隔分成 gap 组，

先对每组进行直接插入排序，

然后再适当缩小 gap ,重复上述步骤。

当 gap = 1 时，此时序列已经进行了多次预排序，接近有序。

这时再对序列进行直接插入排序，就能达到优化的效果。

图示

img

void ShellSort(int* a, int n)
{
    //多次预排序(gap > 1) + 直接插入( gap == 1)
    int gap = n;
    while (gap > 1)
    {
        //使gap最后一次一定能到1
        gap = gap / 3 + 1;
        //多组一起排
        for (int i = 0; i < n - gap; ++i)
        {
            int end = i;
            int x = a[end + gap];
            while (end >= 0)
            {
                if (a[end] > x)
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                    break;
            }
            a[end + gap] = x;
        }
    }
}

6.简单选择排序

基本思想

每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始(末尾)位置，直到全部待排序的数据元素排完 。

动图演示

以每次选出最小值为例

img

void Swap(int* px, int* py)
{
    int tmp = *px;
    *px = *py;
    *py = tmp;
}
 
void SelectSort(int* a, int n)
{
    int begin = 0;
    while (begin < n - 1)
    {
        int mini = begin;
        for (int i = begin; i < n; i++)
        {
            if (a[i] < a[mini])
                mini = i;
        }
        Swap(&a[begin], &a[mini]);
        ++begin;
    }
}

7.快速排序

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

void QuickSort(int* a, int left, int right)
{
    if (left >= right)
        return;
 
    //先将选定的基准值排好
    int keyi = Partion(a, left, right);
 
    //再通过递归排序其左右子序列
    QuickSort(a, left, keyi - 1);
    QuickSort(a, keyi + 1, right);
}

Partion函数分析
Partion函数在这里的作用是：

将选定的基准值排到正确位置，并将待排序列分成比基准值小的左子序列，比基准值大的右子序列。

将区间按照基准值划分为左右两半部分的常见方式有：

基本思想：

选择待排序列的最左值的下标为基准值所指下标，当区间左下标小于区间右下标时，先从右开始找比基准值小的值，找到后再从左开始找比基准值大的值，都找到后，将左右下标对应的值交换，然后从右开始重复上述步骤，直到左右下标相等。当左右下标相等时，将下标所指向的值与基准值互换。

动图演示：

img

int Partion(int* a, int left, int right)
{
    int keyi = left;
    while (left < right)
    {
        //右边先走，找小
        while (left < right && a[right] >= a[keyi])
        {
            --right;
        }
        //左边走，找大
        while (left < right && a[left] <= a[keyi])
        {
            ++left;
        }
        Swap(&a[left], &a[right]);
    }
    Swap(&a[keyi], &a[left]);
    return left;
}

8.各类排序算法的稳定性及时间和空间复杂度

img

最后修改：2021 年 12 月 31 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏