1.绪论

知识框架

🥬数据结构 - 图1

1.1时间复杂度

一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为O(n)，它是该算法问题规模 n 的函数，时间复杂度主要分析O(n)的数量级。

1.2空间复杂度

算法的空间复杂度S(n)定义为该算法所消耗的存储空间，他是问题规模n的函数。

1.3数据的逻辑结构

逻辑结构指的是数据元素之间逻辑关系，与数据的存储结构无关，是独立于计算机的。
🥬数据结构 - 图2

1.4数据的存储结构

数据的存储结构是指数据的逻辑结构在计算机中的存储方式。又称物理结构。主要包括以下四种：顺序存储、链式存储、索引存储、散列存储。优缺点如下：

存储结构 优点 缺点
顺序结构 随机存取、每个元素占用最小的存储空间 只能使用相邻的一块存储单元，因此可能产生较多的外部碎片
链式结构 无碎片现象，能充分利用所有存储单元 每个元素因存储指针占用额外的存储空间，且只能实现顺序存放
索引结构 检索速度快 附加的索引表额外占用存储空间，索引表需要随数据改变修改，因而会花费较多的时间。
散列存储 检索，增加和删除结点的操作都很快 若散列函数不好，则可能出现元素存储单元的冲突，因而增加时间和空间的开销

2.线性表

2.1知识框架

线性表是一种连续或间断存储的数组，这里的连续和间断是针对物理内存空间中线性表元素之间是否连续，其中连续数组对应内置数组的表现方式，间断数组对应的是指针的实现方式，即链表实现。
🥬数据结构 - 图3

2.2线性表的基本操作

  1. InitList(&L)：初始化列表
  2. DestroyList(&L)：销毁
  4. ListInsert(&L,i,e)：插入操作
  5. ListDelete(&L,i,&e)：删除操作
  7. LocateElem(L,e)：按值查找
  8. GetElem(L,i)：按位查找
  10. Length(L)：求表长
  11. PrintList(L)：输出操作
  12. Empty(L)：判空操作

2.3线性表的顺序表示

顺序表的特点： 1.逻辑相邻、物理相邻； 2.可以随机存取，即在O(1)的时间内找到第i个元素； 3.存储密度高，每个节点只存储数据元素； 4.通常用数组来描述。 5.插入和删除操作需要移动大量元素。 6.拓展容量不方便，即便采用动态分配的方式，拓展长度的时间复杂度也比较高； 注意：线性表的位序从1开始，数组的元素下标从0开始

2.3.1静态分配

  1. #include<stdio.h>
  3. //静态分配
  4. #define Maxsize 50
  5. typedef struct{
  6.     int data[MaxSize];
  7.     int length;
  8. }SqList;
  10. void InitList(SqList &L)//静态初始化
  11. {
  12.     for(int i=0;i<MaxSize;i++)
  13.         L.data[i]=0;
  14.     L.length=0;
  15. }
  16. bool ListInsert(SqList &L,int index,int element)
  17. {   //位置是从1到n
  18.     /*时间复杂度：
  19.     最好情况：O(1)
  20.     最坏情况：O(n)
  21.     平均情况：O(n)
  22.     */
  23.     if(L.length==MaxSize) return false;
  24.     if(index<1 || index>L.length+1) return false;
  25.     for(int i=length;i>=index;i--)
  26.         L.data[i]=L.data[i-1];//第index个元素及之后的元素后移
  27.     L.data[index-1]=element;
  28.     L.lenght++;
  29.     return true
  30. }
  31. bool ListDelet(SeqList &L,int index,int &element)
  32. {    //时间复杂度同插入操作
  33.     if(index<1 || index>L.length+1) return false;
  34.     element=L.data[index-1];//要被删除的元素
  35.     for(int i=index;i<L.length;i++)
  36.         L.data[i-1]=L.data[i];
  37.     L.lenght--;
  38.     return true;
  39. }
  41. int GetElem(SeqList L,int index)
  42. {    //按位查找
  43.     //时间复杂度：O(1)
  44.     return L.data[i-1];
  45. }
  47. int LocateElem(SeqList L,int element)
  48. {
  49.     //按值查找
  50.     //时间复杂度：O(n)
  51.     for(int i=0;i<L.length;i++)
  52.         if(element==L.data[i])
  53.             return i+1;
  54.     return 0;
  55. }
  57. int main()
  58. {
  59.     SqList L;//声明一个顺序表
  60.     InitList(L);//初始化一个顺序表
  61.     bool isSuccess=ListInsert(L,3,3);//在3这个位置插入3
  62.     int element=-1;
  63.     if(ListDelete(L,3,e))
  64.         printf("已删除第3个元素，删除元素的值为：%d\n",element);
  65.     else
  66.         printf("位序index不合法，删除失败\n");
  67.     int SearchElem=GetElem(L,3);
  68.     return 0;
  69. }

2.3.2动态分配

  1. #include<stdio.h>
  2. #include<stdlib.h>//malloc函数
  4. //动态分配
  5. #define InitSize 100
  6. typedef struct{
  7.     Elemtype *data;
  8.     int MaxSize,length;
  9. }SeqList;
  11. void InitList(SqList &L)//静态初始化
  12. {
  13.     L.data=(Eletype *)malloc(InitSize*sizeof(Eletype));
  14.     L.length=0;
  15.     L.MaxSize=InitSize;
  16. }
  18. void IncreaseSize(SeqList &L,int len)
  19. {
  20.     int *p=L.data;
  21.     L.data=(int *)malloc((L.MaxSize+len)*sizeof(Eletype));
  22.     for(int i=0;i<L.length;i++)
  23.         L.data[i]=p[i];//将数据复制倒新区域
  24.     L.MaxSize=L.MaxSize+len;
  25.     free(p);//释放申请的p空间
  26. }
  28. int main()
  29. {
  30.     SqList L;//声明一个顺序表
  31.     InitList(L);//初始化一个顺序表
  32.     IncreaseSize(L,5);
  33.     return 0;
  34. }

2.4线性表的链式表示

单链表的特点： 1.不要求大量的连续空间，改变容量方便 2.不可随机存取，要消耗一定空间存放指针

  1. #include<stdio.h>
  2. #include<stdlib.h>
  4. typedef struct LNode{
  5.     int data;
  6.     struct LNode *next;
  7. }LNode,*LinkList;
  9. int main()
  10. {
  11.     return 0;
  12. }

2.5顺序表和链表的比较

顺序表 链表
存取（读写）方式 顺序存取、随机存取 顺序存取
逻辑结构与物理结构 逻辑相邻、物理相邻 逻辑相邻，物理不一定相邻
查找、插入和删除操作 对于按值查找，无序的时间复杂度为O(n)，有序则为O(log2n)。
对于按位查找，时间复杂度为O(1)。
顺序表的插入、删除操作平均需要移动半个表长的元素。		 对于按值查找，时间复杂度为O(n)。
对于按位查找，链表的平均时间复杂度为O(n)。
链表的插入、删除操作，只需修改相关节点的指针域，由于链表的每个结点都带有指针域，故而存储密度不够大。
空间分配 静态存储分配情形下，一旦存储空间满了，就不能扩充。动态存储分配虽然存储空间可以扩充，但是操作效率低（malloc）。 结点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活、高效。

常见问题：
头指针和头结点的区别？
答案：
头指针是指向第一个结点存储位置的指针，具有标识作用，头指针是链表的必要元素，无论链表是否为空，头指针都在。
头结点是放在第一个元素节点之前，便于在第一个元素结点之前进行插入和删除操作，头结点不是链表的必须元素，可有可无，头结点的数据域也可以不存储任何信息。

3.栈、队列和数组

栈和队列是一种线性表。两种实现方式，一种是用内置数组实现，一种是以链表实现。
对于进入队列的元素按“先进先出”的规则，在表头进行删除，在表尾进行插入。由于队列要进行频繁的插入和删除，一般为了高效，选择用定长数组来存储队列元素，在对队列进行操作之前，要判断队列是否为空或者是否已满。如果想要动态长度也可以用链表来存储队列。需要记住队头和队尾指针的地址。
对于插入到栈的元素按“先进后出”的规则，插入和删除操作都在栈顶进行。与队列类似，一般用定长数组存储栈元素。由于进栈和出栈都是在栈顶进行，因此要有一个size变量来记录当前栈的大小。
🥬数据结构 - 图4
常见问题：如何区分循环队列是空还是满？
答案：
方法一：牺牲一个单元来区分队列是空还是满，这个时候Q.rear==Q.front才是队满的标志。
方法二：类型中增设表示元素个数的数据成员。这样，队空的条件为Q.size==0,队满的条件为Q.size==MaxSize。

4.串

串是零个或多个字符组成的有限序列。如S=’iPhone 11 Pro Max?’。模式匹配为串的常见考点，算法包括朴素模式匹配算法、KMP算法。

4.1朴素模式匹配算法

匹配思想：从主串的第一个字符起，与子串的每一个字符比较，相等则继续比较；不等则从主串的下一个位置起，继续和子串的每一个字符开始比较，直到最后看是否匹配成功。比如主串为”goegoogleglgoogegoogle”,子串为”google”。
算法最坏时间复杂度=O(mn)，最好时间复杂度O(n)。

4.2KMP算法

匹配思想：KMP算法从分析模式本身的结构入手，如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀，那么就可以将模式向后滑动到与这些相等字符对齐的位置，主串i指针无需回溯，并继续从该位置进行比较。而模式向后滑动位数的计算仅与模式本身结构有关，与主串无关。
image.png
image.png
image.png
最好时间复杂度=O(n)。通常，没有指出最坏或者最好的情况下，默认为最坏。

5.树与二叉树

树是非线性结构，其元素之间有明显的层次关系。在树的结构中，每个结点都只有一个前驱为父结点，没有前驱结点为树的根节点，简称为树的根；每个结点可以有多个后继称为结点的子结点，没有后继的结点称为叶子结点。
二叉树是树另一种树形结构，其特点是每个结点至多有两颗子树，并且二叉树的子树有左右之分。
常见考点为二叉树的遍历、线索二叉树、树的存储。

5.1二叉树的遍历

类型 思想
先序遍历（根左右） 二叉树为空：不用操作
二叉树非空：访问根结点—>先序遍历左子树—>先序遍历右子树
中序遍历（左根右） 二叉树为空：不用操作
二叉树非空：中序遍历左子树—>访问根结点—>中序遍历右子树
后序遍历（左右根） 二叉树为空：不用操作
二叉树非空：后续遍历左子树—>后续遍历右子树—>访问根结点
层序遍历 初始化一个辅助队列—>根结点入队—>若队列非空，则队头结点出队，访问该结点，依次将其左右孩子插入队尾（如果有的话）—>重复以上操作直至队列为空。

5.2线索二叉树

对于n个结点的二叉树，在二叉链存储结构中有 n+1 个空链域，利用这些空链域存放某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。

5.3树的存储

树的存储方式包括三种：双亲表示法、孩子表示法、孩子兄弟表示法。
双亲表示法采用一种连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示双亲结点在数组中的位置。
image.png
孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时n个结点就有n个孩子链表（叶子结点的孩子链表为空表）。
image.png
孩子兄弟表示法又称二叉树表示法，即以二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容：结点值、指向结点每一个孩子结点的指针，及指向结点下一个兄弟结点的指针（沿此域可以找到结点的所有兄弟结点）。
image.png

6.图

图是由顶点的有穷非空集合的顶点之间边的集合组成，通常表示为：G(V,E)。其中G表示为一个图，V和图G中顶点的集合，E为图G的边的集合。
常见考点为图的遍历，包括两种：深度优先搜索、广度优先搜索。

6.1深度优先搜索（DFS）

深度优先搜索（Depth First Search-DFS）遍历类似树的先序遍历，是树的先序遍历的推广。
设初始状态时图中的所有顶点未被访问，则：

  1. 从图中某个顶点 vi 出发，访问 vi ；然后找到 vi 的一个邻接顶点 vi1 ；
  2. 从 vi1 出发，深度优先搜索访问和 vi1 相邻且未被访问的所有顶点；
  3. 转到 a ，直到和 vi 相邻的所有顶点都被访问为止；

  4. 继续选取图中未被访问的顶点 vj 作为起始顶点，转到 a ，直到图中所有顶点都被访问为止。

    6.2广度优先搜索（BFS）

    广度优先搜索（Breadth First Search-BFS）遍历类似树的按层次遍历的过程。
    设初始状态时图中所有的顶点都没有被访问。

  5. 从图中某个顶点出发，访问 vi ；

  6. 访问 vi 的所有相邻且未被访问的所有顶点 vi1, vi2, …, vim；
  7. 以 vi1, vi2, …, vim的次序，以 vij(1<=j<=m)依次作为 vi ，跳转到 a ；

  8. 继续选取图中未被访问的顶点 vk 作为起始顶点，转到 a ，直到图中所有的顶点都被访问为止。

    7.查找

    查找的过程是将给定的K值与文件中各记录的关键词比较。用比较次数的平均值评估算的的优劣，即平均查找长度（ASL）。显然，ASL值越小，时间效率越高。

    7.1查找的分类

  9. 静态查找法：顺序查找、这般查找、分块查找

  10. 动态查找法：二叉排序法、平衡二叉树、红黑树、B树、键树
  11. 哈希表

    7.2常见查找算法

  1. 顺序查找

把待查关键字key放入哨兵位置（i=0），再从后往前依次把表中元素和key比较，如果返回值为0则查找失败，表中没有这个key值，如果返回值为元素的位置 i(i!=0) 则查找成功。时间效率为O(n)。

  1. 折半查找

要求查找表为顺序存储结构且有序，若关键字在表中，则返回关键字的位置，若关键字不在表中时停止查找的典型标志是：查找范围的上届<=查找范围的下届。

  1. 分块查找

先把查找表分为若干子表，要求每个子表的元素都要比他后面的子表的元素小，也就是保证块间是有序的（但是子表内不一定是有序的），把各个子表的最大关键字构成一张索引表，表中还包含各个子表的起始地址。

  1. 二叉排序树

二叉排序树的定义为：一棵空树，或者是一颗具有如下特点的树：如果该树有左子树，那么左子树的所有结点值小于根的值；如果该树有右子树，那么右子树的所有结点值都大于根的值；其左右子树也分别符合二叉排序树的定义，这也是动态查找和静态查找的区别，静态查找不能进行动态插入。

  1. 平衡二叉树

平衡二叉树又称为AVL树，它或者是一颗空树或者是具有以下特点：它的左子树和右子树的高度差绝对值不能大于1，且它的左右子树也都是平衡二叉树。
如果在一个平衡二叉树中插入一个结点可能造成失衡，这时就要进行树结构的调整，即平衡旋转。包括四种情况：

  1. 在左子树的左子树上插入结点时向右进行单向旋转；
  2. 在右子树的右子树上插入结点时向左进行单向旋转；
  3. 在左子树的右子树上插入结点时向左旋转再向右旋转；
  4. 在右子树的左子树上插入结点时向右旋转再向左旋转。
    1. 红黑树

红黑树时平衡查找树的改进。红黑树的思想是对2-3查找树进行编码，尤其是对2-3查找树中的3-nodes结点添加额外信息。红黑树中将结点之间的链接分为两种不同类型，红色链接，它用来链接两个2-nodes结点来表示一个3-nodes结点。黑色链接用来链接普通的2-3结点。特别的，使用红色链接的两个2-nodes来表示一个3-nodes结点，并且向左倾斜，即一个2-nodes是另一个2-nodes的左子结点。

8.排序

排序就是一系列数据按照某个关键字（例如：销量、价格），进行递增或者递减的顺序排列起来。

8.1排序的分类

按照排序过程中所依据的原则的不同可以分类为：

  1. 插入排序：直接插入排序、希尔排序
  2. 交换排序：冒泡排序、快速排序
  3. 选择排序：简单选择排序、堆排序
  4. 归并排序
  5. 基数排序

    8.2排序算法的比较

    | 类别 | 排序方法 | 时间复杂度 | | | 空间复杂度 | 稳定性 | | —- | —- | —- | —- | —- | —- | —- | | | | 平均情况 | 最好情况 | 最坏情况 | 辅助存储 | | | 插入排序 | 直接插入 | O(n2) | O(n) | O(n2) | O(1) | 稳定 | | | Shell排序 | O(n1.5) | O(n) | O(n2) | O(1) | 不稳定 | | 选择排序 | 直接选择 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 | | | 堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 | | 交换排序 | 冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 | | | 快速排序 | O(nlog2n) | O(nlog2n) | O(n2) | O(nlog2n) | 不稳定 | | 归并排序 | | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 | | 基数排序 | | O(d(r+n)) | O(d(r+n)) | O(d(r+n)) | O(r) | 稳定 | | 注意：基数排序的复杂度中，r代表关键字的基数，d代表长度，n代表关键字的个数。 | | | | | | |

从平均情况看：堆排序、归并排序、快速排序胜过希尔排序。
从最好情况看：冒泡排序和直接插入排序更胜一筹。
从最差情况看：堆排序和归并排序胜过快速排序。
虽然直接插入排序和冒泡排序速度比较慢，但是当初始序列整体有序和局部有序时，这两种算法的效率比较高。当初始序列整体或局部有序时，快速排序算法效率会下降。当排序序列较小且不要求稳定时，直接排序效率比较好；要求稳定时，冒泡排序效率比较好。