数据结构

数据结构是计算机存储、组织数据的方式，是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

本文将系统的对数据结构所涉及的知识进行梳理，以最简单易懂的语言帮助你构建属于自己的知识体系。

一、线性表

1. 顺序表

(1) 静态存储

大小不可变，在定义声明时即固定大小。

// 静态存储
typedef struct {                 
    int date[10];         
    int length;         // 当前元素个数
} SqLsit;

(2) 动态存储

可根据需求通过 malloc 函数声明大小，free() 函数释放。

// 动态存储
typedef struct {                 
    int *date;         
    int length, MaxSize;     //当前个数和最大容量
} SeqList;

// 动态分配  
SeqList L;
L.date = (int *) malloc (sizeof(int) * 10);   

2. 链表

(1) 单链表

typedef struct LNode { 
    int date;       //值域
    struct LNode *next;     //指针域
} LNode, *LinkList;

(2) 双链表

typedef struct LNode {
    int date;       //值域
    struct LNode *prior, *next;     //前驱，后继
} LNode, *LinkList;

3. 广义表

(1) 定义

• 子表：嵌套于广义表中的表。
• 原子：广义表中的单个元素。
• 长度：原子个数 + 子表个数。
• 深度：广义表嵌套层级。

(2) 基本操作

• 取表头：取出表中的第一个元素，结果可能是单个原子，也可能是广义表。
• 取表尾：去除第一个元素之后剩余部分，结果一定是广义表。

4. 区别

(1) 线性表

• 物理相邻，逻辑也相邻(在内存中分配了一块连续区域用于存储数据)。
• 满足随机存储(即根据下标可以直接定位到对应元素)。
• 插入删除需要移动大量元素。

(2) 链表

• 逻辑相邻，物理不相邻(通过指针相连)。
• 满足顺序存储(一个连一个)。
• 插入删除更方便，无需移动大量数据。
• 查找元素效率低，需要从首节点遍历寻找。

二、栈及应用

1. 定义

• 栈空： top = -1 。
• 栈满： top = MaxSize - 1 。
• 单向通道，先进后出。

// 顺序栈
typedef struct {                 
    int date[10];         
    int top;     //栈顶
} SqStack;

// 链栈
typedef struct LinkNode {                 
    int *date;         
    struct LinkNode *top;     //栈顶
} *LiStack;

2. 基本操作

(1) 顺序栈

• 出栈: 先出栈再减 1 ， values = S.data[S.top--] 。
• 进栈: 先加 1 再进栈， values = S.data[++S.top] 。

(2) 链栈

• 初始化栈: InitStack(&S) 。
• 判定栈是否为空: StackEmpty(S) 。
• 进栈(链栈): Push(&S, x) 。
• 出栈(链栈): Pop(&S, &x) 。
• 读取栈顶元素: GetTop(s, &x) 。
• 销毁栈: DestroyStack(&S) 。

3. 中缀表达式

• 声明一个栈操作数栈和运算符栈。
• 遇到操作数，加入操作数栈。
• 遇到运算符或界限符，弹出操作数栈顶两位元素，进行运算后重新入栈。

4. 中缀转后缀

• 声明一个栈用于存放界限符 ( ) 和运算符 + - * / 。
• 遇到操作数，直接加入后缀表达式。
• 遇到 ( 直接入栈, 遇到 ) 则依次弹出栈内运算符并加入后缀表达式，直到弹出 ( 为止， ( 不加入后缀表达式。
• 遇到运算符，依次弹出栈中优先级 高于或等于 当前运算符的所有运算符，并加入后缀表达式，若碰到“(”或栈空则停止，之后再把当前运算符入栈。

三、队列及应用

1. 定义

• 队空：front = rear = 0 。
• 双向通道，一边只能进，一边只能出，先进先出。

// 顺序队列
typedef struct {                 
    int date[10];         
    int front, rear;     //队头和队尾
} SqQueue;

// 链队
typedef struct {                 
    int date;         
    struct LinkNode *next;     
} LinkNode;

typedef struct {        
    LinkNode *front, *rear;     //队头和队尾
} *LiQueue;

2. 基本操作

(1) 顺序队列

• 出队：values = Q.data[Q.front--] 。
• 入队：values = Q.data[Q.rear++] 。

(2) 链队

• InitQueue(&Q) ：初始化队列，构造一个 空队列Q 。
• QueueEmpty(Q) ：判队列空，若 队列Q 为空返回 true ，否则返回 false 。
• EnQueue(&Q, x) ：入队，若 队列Q 未满，将 x 加入，使之成为新的队尾。
• DeQueue (&Q, &X) ：出队，若 队列Q 非空，删除队头元素并用 x 返回。
• GetHead(Q, &X) ：读队头元素，若 队列Q 非空，则将队头元素赋值给 x 。

四、矩阵压缩

1. 对称矩阵

• 矩阵元素关于对角线对称，只需存储上(下)三角和对角线元素即可。
• 从上至下元素个数依次递增，构成等差数列，利用等差求和公式求和即可。

S = [(a1 + an)*n]/d   //d：公差； n：一共多少项 

• 需要注意数组下标通常从 0 开始。

2. 三角矩阵

• 矩阵上三角或下三角值为 0 ，只需存储上三角或下三角即可。
• 计算方法同对称矩阵。

3. 三对角矩阵

只有对角线和其相邻元素有值。

4. 稀疏矩阵

稀疏矩阵通常指 0 元素个数远多于非 0 元素，采用三元组或十字链表法记录。

// 三元组
struct V {
    int i;      //行号
    int j;      //列号
    int k;      //元素值
}

五、串模式匹配

1. 定义

// 静态存储
typedef struct {                 
    char ch[10];         
    int length;     //串的长度
} SString;

// 动态存储
typedef struct {                 
    char *ch;         
    int length;     //串的长度
} HString;

六、树及应用

1. 介绍

(1) 性质

• 树的结点数 = 所有结点度数 + 1 = 边数 - 1。
• 度为 M 的树结点数 = 度为 0 的结点个数 + … + 度为 M 的结点个数。
• 度为 M 的树第 h 层最多有 M^(h-1) 个结点。
• 高度为 h 的 M 又树最多有 [M^(h-1)]/[m-1] 个结点。

(2) 定义

孩子表示法：左孩子存孩子，右孩子存兄弟。

//孩子表示法
typedef struct CSNode {                 
    int date;         
    struct CSNode *firstchild, *nextsibling;  
} CSNode, *CSTree;

//双亲表示法
typedef struct {                 
    int date;         
    int parent;     
} PTNode;
typedef struct {        
    PTNode nodes[10];     //队头和队尾
    int n;
} PTress;

2. 二叉树

(1) 性质

• 非空二又树叶子结点数 = 度为 2 的结点数 + 1。
• 非空二又树第 K 层最多有 2^(k-1) 个结点。
• 高度为 h 的二叉树最多有 2^h - 1 个结点。
• n 个结点的完全二叉树高度： log2[n + 1] 。

(2) 定义

// 顺序存储
struct TreeNode {                 
    int date;         
    bool isEmpty;       //结点是否空
} T[10];

// 链式存储
typedef struct BitNode {                 
    int date;         
    struct BitNode *lchild, *rchild;  
} BitNode, *BitTree;

3. 哈弗曼树

• 将所有结点按权升序排列(从小到大排)。
• 取两个权最小构成一个二叉树，计算其父结点权值。
• 若父结点权同时大于剩余未加入中的两个结点权值，则将之后两个结点作为新叶子构造树，和当前根的孩子同级。
• 若只有小于父结点,则作为父结点的兄弟结点。

七、图及应用

1. 定义

// 邻接矩阵
typedef struct {                 
    int date[10];         
    int edge[i][j]; 
    int vexNum, arcNum;     //顶点数和边数 
} MGraph;

// 邻接表
typedef struct ArcNode {     //边表结点                 
    int adjvex;         
    struct ArcNode *next;
} ArcNode;
typedef struct VNode {       //顶点           
    int data;                
    VNode *first; 
} VNode, AdjList[MaxVexNum];
typedef struct { 
    AdjList vertices;
    int vexNum, arcNum;     //顶点数和边数
} ALGraph;

2. 最小生成树

(1) 普里姆算法

每次将代价最小(边权值最小)的结点纳入生成树，从一个结点出发不断往下走，不断纳入新结点。

(2) 克鲁斯卡尔算法

每次选取权最小的一条边，让其两边结点相连，忽略已行连通的结点。

3. 最短路径

(1) 迪杰斯特拉算法

适用于求解单源最短路径(即一个顶点到其它顶点的最短路径)，求解思路如下：

• 定义三个数组. final[size] ：标记各结点是否找到最短路径； dist[size] ：当前顶点到相邻顶点长度； path[size] ：各结点前驱，初始为 -1 。
• 每轮循环从 final[i]=false 开始，且 dist[i] 值最小的开始，令其 final[i]=true 。
• 计算与 i 相连顶点 j 的 dist 值: dist[j]= dist[i] + i到j的权 ，若新得到 dist 值更小，则替换旧值，并将其相应 path 值改为 i ，反之则不变。
• 重复上述步骤直至所有结点 final 值为真。

4. 拓扑排序

(1) 拓扑排序

• 图必须为有向无环图。
• 步骤：选择一个 无前驱 结点输出，删除以该顶点为起点的有向边，不断重复即可。

(2) 逆拓扑排序

• 图必须为有向无环图。
• 步骤：选择一个 无后继 结点输出，删除以该顶点为终点的有向边，不断重复即可。

5. 关键路径

(1) 顶点最早开始时间

• 源点出发，按 拓扑序列 求每个顶点最早发生时间 Ve 。
• Ve 若存在多条路经，则选取总权值最大的那条。
• 最后一个顶点的 Ve 即键路径长度。

(2) 顶点最晚开始时间

• 汇点出发，按 逆拓扑序列 求每个顶点最晚发生时间 Vl 。
• Vl = 后继顶点最晚发生时间 - 活动边的值。
• Vl 若存在多条路径, 则选取权值最小的那条。

(3) 活动最早开始时间

• e = 该弧的 起点 (弧尾) 最早 发生时间 Ve 。

(4) 活动最早开始时间

• l = 该弧的 终点 (弧头) 最晚 发生时间 - 该弧的值。

(5) 关键路径

• 每个差额为 0 的顶点即为关键路径， 差额 = l - e

八、查找算法

1. 二分查找

• 定义两个头尾游标，分别指向每次循环的高低位： low, high 。
• 定义 mid 变量，取值为每次头尾游标下标和的 1/2 。
• 将待查找元素值 target 和 mid 相比，若大于mid，则 low = mid + 1 ，若小于mid，则 high = mid - 1 。
• low, high, mid 重合即索要查找元素，若不是则查找失败。

2. 分块查找

• 建立对应索引表(存放块内的最大值和块的起始下标)。
• 将查找的元素和索引表的每个块的最大值进行比较。
• 若直到遇到块的最大值大于查找的元素值，则进入块内进行查询。
• 最理想效率： n 个元素分为 根号n 块.

九、排序算法

1. 插入排序

(1) 简单插入排序

// 最开始子表中存放一个元素，即数组中第一个(不算哨兵)
void InsertSort_1(int A[], int n){
    for(int i = 2 ; i <= n ; i++){
        A[0] = A[i];    //将待插元素放置到哨兵位置
        // 如果插入元素比表尾大则跳出，当前元素变为表尾元素
        if(A[i] < A[i-1]){ 
            // 从子表表尾往前扫描，把大于插入元素的元素后移
            for(int j = i-1 ; A[0] <= A[j] ; j--){      
                A[j+1] = A[j];
            }
        }
        A[j+1] = A[0];
    }
}

(2) 折半插入排序

实现逻辑和简单插入一致，在查找元素时使用折半查找进行。

void InsertSort_2(int A[], int n){
    int i, j, low, high, mid;
    for(int i = 2 ; i <= n ; i++){
        A[0] = A[i];    // 将待插元素放置到哨兵位置
            
        low = 1; 
        high = i - 1;
        while(low <= high){
            mid = (low + high)/2;
            if(A[mid] > A[0]){
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
           
        // 把大于插入元素的元素后移
        for(int j = i-1 ; j >= high+1 ; j--){      
            A[j+1] = A[j];
        }
        A[hign+1] = A[0];
    }
}

(1) 希尔排序

• 将整个表按某特定增量 d 划为 k 个子表。
• 相隔为 d 的元素为同一子表，即：[i，i+d, ..., i+nd] 。
• 对每个子表各进行一次插入排序。
• 不断缩增量 d 的值，如 d1=n/2, d2=d1/2 , 重复上述步骤直到 d=1 。

2. 交换排序

(1) 冒泡排序

void BubbleSort(int A[], int n){
    int temp;
    for(int i = 0; i < n-1; i++){
        // 每次循环从后往前，将最小的不断前移
        for(int j = n-1; j > i; j--){
            if(A[j-1] > A[j]){
                temp = A[j];
                A[j] = A[j-1];
                A[j-1] = temp;
            }
        }
    }
}

(2) 快速排序

• 选择一个元素作为枢轴，确定它最终位置(即左边元素都小于它.右边都大于它)。
• 取 low 指头， high 指尾，两个指针依次向中间扫。
• low 为枢轴，定义临时变量存枢轴，让表中枢袖位置空出来。
• low 空: high-1 ; high 空: low+1 (空的那端动)。
• 小于枢轴放到 low ，大于放 high ，枢轴在 low high 重合。
• 每一轮之后枢轴都比其左端元素小，比右端元素比大。
• 重复上述步骤。

void quickSort(ElemType Arr[], int low, int high) {
    if (low < high) {
        // 将表 Arr[low, high] 划分为满足上述条件的两个子表
        int pivotPos = partition (Arr, low, high);  //划分

        // 依次对两个子表进行递归排序
        quickSort(Arr, low, pivotPos - 1) ;
        quickSort(Arr, pivotPos + 1, high) ;
    }
}

int partition (ElemType Arr[],int low, int high) { 
    // 将表中第一个元素设为枢轴，对表进行划分
    ElemType pivot = Arr[low]; 

    while (low < high) {
        while (low < high && Arr[high] >= pivot) {
            --high;
        }
        // 将比枢轴小的元素移动到左端
        Arr[low] = Arr[high];

        while (low < high && Arr[low] <= pivot) {
            ++low;
        }
        // 将比枢轴大的元素移动到右端
        Arr[high] = Arr[low];
    }

    //枢轴元素存放到最终位置
    Arr[low] = pivot;
    return low;
}

3. 选择排序

(1) 简单选择排序

void SelectSort(int A[], int n){
    for(int i = 0; i < n-1; i++){
        int min = i;        // 记录最小元素
        for(int j= i+1; j < n; j++){
            if(A[min] > A[j]){
                min = j;    // 更新最小元素位置
            }
        }
        if(min != i){
            temp = A[j];
            A[j] = A[min];
            A[min] = temp;
        }
    }
}

(2) 堆排序

• 小根堆：任意子树中根的值永远 <= 左右孩子值。
• 大根堆：任意子树中根的值永远 >= 左右孩子值。

(3) 堆的建立

• 依次检查非终端结点 i < n/2。
• 若其不满足同时大于左右孩子,则和子孩子中更大交换。
• 交换后子中树不满足条件,重复1，2步骤。

(4) 堆的插入

• 小根堆：新元素放表尾 叶结点, 不断上升。
• 大根堆：新元素放表头 根结点, 不断下坠。

(5) 堆的删除

• 把堆底元素移到删除位置。
• 重新调整为大(小)根堆。

4. 归并排序

归并排序即将两个有序的顺序表进行排序处理，分别定义两个扫描指针便利两张表进行比较。

---

参考书籍： 《数据结构-严蔚敏》