数据结构与算法速通

1. 数组

1. 数组的内存地址计算公式：f(index) = BaseAddress + DataTypeSize * Index

   首地址 + 内存单个元素占用的内存大小 * 索引

搜索值

int search(int arr[],int length,int key){
    for(int i = 0;i < length;i++){
        if(arr[i] == key){
            return i;
        }
    }
    return -1;
}

1. 时间复杂度：
   1. 最好：首位，O(1)
   2. 末尾/不在数组中O(n)

插入

#include <stdio.h>
#define Max_SIZE 100

int main(){
    int arr[Max_SIZE] = {1,5,10,7,31};
    int length = 5;
    int element = 52;
    int pos = 2;

    for(int i = length;i > pos; i--){
        arr[i] = arr[i-1];
    }

    arr[pos] = element;
    length = length + 1;
}

1. 时间复杂度：
   1. 最好：末位，O(1)
   2. 最坏：首位O(n)
   3. 平均：O(n)

删除

int rm(int arr[], int length, int key){
    int index = search(arr,length,key);
    if(index == -1) return -1;

    for(int i = index;i < length;i++){
        aerr[i] = arr[i+1];
    }

    length = length-1;
    return index;
}

1. 时间复杂度：
   1. 最好：末位O(1)
   2. 最坏：首位O(n)

单链表

struct LNode{
    int data; // 数据域
    struct LNode *next; // 指针域
};

头插法

void insert(int e){
    struct LNode *newNode = (LNode *)malloc(sizeof(struct LNode));

    newNode->data = e;
    newNode->next = head;
    
    head = newNode;
}

时间复杂度：O(1)

尾插法

void insertL(int e){
    struct LNode *newNode = (LNode *)malloc(sizeof(struct LNode));

    newNode->data = e;
    newNode->next = NULL;

    if(head == NULL){
        head = newNode;
    }else{
        struct LNode *last = head;
        while(last->next != NULL){
            last = last->next;
        }
        last->next = newNode;
    }
}

时间复杂度：最好O(1) 最坏O(n)

删除

bool deleteN(struct LNode **head, int key){
    struct LNode *temp;

    if((*head)->data == key){
        temp = *head;
        *head = (*head)->next;
        free(temp);
        return true;
    }else{
        struct LNode *pre = *head;
        while(pre->next != NULL){
            if(pre->next->data == key){
                temp = pre->next;
                pre->next = pre->next->next;
                free(temp);
                return true;
            }else{
                pre = pre->next;
            }
        }return false;
    }
}

时间复杂度：最好O(1) 最坏O(n) 主要是遍历查找

搜索

struct LNode *searchN(struct LNode *head,int key){
    struct LNode *temp = head;
    while(temp != NULL){
        if(temp->data == key) return temp;
        temp = temp->next;
    }
    return NULL;
}

时间复杂度：最好O(1) 最坏O(n)

带头单链表

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode;

头节点一般不被当作链表元素
头节点的数据域不存储链表的数据
不用判断头指针是否为空，便于头指针和非空指针的统一处理
其它方法实现参照前文

双链表

typedef struct DNode{
    DNode *prior;
    DNode *next;
    int data;
}DNode;

头插法

bool insertH(DNode *head, int e){
    DNode *newNode = (DNode*)malloc(sizeof(DNode));
    newNode->data = e;

    newNode->next = head->next;
    newNode->prior = head;
    if(head->next != NULL){
        head->next->prior = newNode;
    }
    head->next = newNode;
    return true;
}

时间复杂度O(1)

尾插法

void insertL(DNode *head, int e){
    DNode *newNode = (DNode*)malloc(sizeof(DNode));
    newNode->data = e;

    DNode *last = head;
    while(last->next != NULL){
        last=last->next;
    }
    last->next = newNode;
    newNode->prior = last;
    newNode->next = NULL;
}

时间复杂度O(n)

栈

1. 先进后出
2. 插入和删除只能在栈顶操作
3. 入栈和出栈：O(1)

// 数组实现
#define size 3
int stack[size];
int top = -1; // 栈顶指针

void push(int e){
    if(top == size-1){
        cout << "Failed...Aready FULL!" << endl;
        return;
    }
    top = top + 1;
    stack[top] = e;
}

void pop(){
    if(top == -1){
        cout << "Failed...Already EMPTY!" << endl;
        return;
    }
    top = top - 1;
}

队列

1. 先进先出
2. 时间复杂度O(1)

#define size 3
int quene[size];
int front = 0; // 头
int rear = 0; // 尾

void in(int val){
    if(rear == size){
        cout << "Aready FULL!" << endl;
    }else{
        quene[rear] = val;
        rear++;
    }
}

void qDelete(){
    if(front == rear){
        cout << "Already EMPTY!" << endl;
    }else{
        front++;
    }
}

树

1. 每个结点可以有0/多个子结点
2. 叶子结点：无子结点
3. 一个节点的子结点个数：该节点的度
4. 树中所有结点中度数最大的度：该树的度
5. 层次：结点在树中的相对位置
   1. 第一层：根结点
   2. 第二层：根结点的子结点
      ······
6. 双亲在同一层：堂兄弟结点
7. 深度：从树的根结点开始，达到指定结点的层数
8. 高度：从该结点出发，到离它最远的叶子结点的层数
9. 树的高度和深度：树最大的层数

二叉树

1. 每个结点最多有两个子结点：左子结点、右子结点
2. 形态：
   1. 单结点树：只包含一个结点(只有一个根结点)
   2. 空二叉树：没有任何结点(根结点为空)
   3. 左斜树：只有左子结点，没有右子结点
   4. 右斜树：只有右子结点，没有左子结点
   5. 满二叉树：叶子节点无左右子结点，其余节点均有左右子结点
   6. 完全二叉树：除最后一层叶子结点可以为空，其余结点必须填满，叶子结点尽可能靠左排列(叶子结点允许缺失)
3. 存入数组之后的下标：
   1. i > 1时，结点i的双亲下标为i/2，向下取整
   2. 2*i <= n时，结点i的左孩子下标为2i,否则无左孩子
   3. 2*i + 1 <= n时，结点i的右孩子下标为2i+1,否则无右孩子

     A
    / \
  B     C
 / \   / \
D   E F   G

  A B C D E F G
0 1 2 3 4 5 6 7

4. 使用数组存储树：
   1. 结点的位置与数组的索引之间有明确的映射关系(完全二叉树的结构设计)
   2. 不是完全二叉树/满二叉树：需用空位表示树中缺失的结点
5. 二叉树一般采用链式存储

链式存储

1. 二叉树结点数量为n,则指针域数量为2*n，非空指针域数量n-1(根结点不被指针指向)，空指针域数量n+1

typedef struct treeNode{
    int data;
    struct treeNode *lchild,*rchild;
}BNode;

递归

太抽象了此处就放个示例

int f(int n){
    if(n == 1) return 1;
    if(n == 2) return 2;

    return f(n-1) + f(n-2);
}

遍历

     A
    / \
  B     C
 / \   / \
D   E F   G

1. 先序
   顺序：根，左，右

   A B D E C F G

2. 中序
   顺序：左，根，右

   D B E A F C G

3. 后序
   顺序：左，右，根

   D E B F G C A

4. 层次

递归遍历的代码(以中序为例)

void inOrder(BNode *root){
    if(root == NULL) return;

    inOrder(root->lchild);
    cout << root->data << endl;
    inOrder(root->rchild);
}

哈夫曼树

1. 哈夫曼编码条件：
   1. 每单个字符都必须映射到一个唯一的二进制编码
   2. 保证解码器能进行唯一解码(无损压缩)
   3. 保证任何一个编码都不能是其他编码的前缀
2. 无损压缩的选择：
   1. 使用尽量少的bit数进行压缩
   2. 一个字符在原文中出现概率越大，则分配更短的二进制进行表示
   3. 香农熵(自己查罢)

(香农-范诺编码示意图：1/4等概率)
          0            1
      --------A or B--------
      |                    |
  0   |    1           0   |    1 
 ---is A ?---         ---is B ?---
 |          |         |          |
 A          B         C          D
 00         01        10         11     (压缩编码方案)

哈夫曼编码添加了贪心算法

图

1. 图是由一组顶点集合和边集合组成，每条边连接两个顶点
2. 顶点集V={A,B,C,D},边集E={(A,B),(A,C),(A,D),(B,D)},G=(V,E)
3. V不能为空集，E可以为空
4. 无向图：无向边E={(,),(,)}
   1. (a,b) = (b,a)
5. 有向图：有向边E={<,>,<,>}
   1. <a,b> != <b,a>
6. 顶点的度：依附于该顶点边的条数TD
   1. 有向图：入度和出度
      1. 入度：以该顶点为终点的有向边的数量ID
      2. 初度：以该顶点为起点的有向边的数量OD
      3. TD = ID + OD
7. 路径：从一个顶点到另一个顶点的顶点序列
   1. 无向图对路径没有要求
   2. 有向图：路径的方向必须和弧的方向一致
8. 回路(环)：一条路径的出发顶点和结束顶点为同一顶点
9. 连通：
   1. 无向图：一个顶点到另一个顶点之间有路径存在
   2. 有向图：强连通：两个顶点，有一个正向的路径可以到达，同时也有相反方向的路径到达
10. 连通图：
    1. 无向图：图中任意两个顶点都是连通的
    2. 有向图：图中任意两个顶点都是强连通的(强连通图)
    3. 有n个顶点的无向图，至少要n-1条边才是连通图
    4. 有n个顶点的有向图，至少要n条边才是强连通图
11. 极大连通子图：包含尽可能多的顶点和边
12. 连通分量：无向图中的极大连通子图
13. 强连通分量：有向图中的极大强连通子图
14. 带权图：边上含有权值

邻接矩阵

1. 无向图(不带权)：
   $$
   A_{ij} = \begin{cases}
   1, & \text{当 $i$ 和 $j$ 之间存在边} \
   0, & \text{当 $i$ 和 $j$ 之间不存在边}
   \end{cases}
   $$

   A   B   C   D
   -----------------
   A|   |   |   |   |
   -----------------
   B|   |   |   |   |
   -----------------
   C|   |   |   |   |
   -----------------
   D|   |   |   |   |
   -----------------

   1. 上三角和下三角区域相等，即关于主轴对称
   2. 主轴位置为自己到自己的边
2. 有向图(不带权)：
   $$
   A_{ij} = \begin{cases}
   1, & \text{当 $i$ 和 $j$ 之间存在弧} \
   0, & \text{当 $i$ 和 $j$ 之间不存在弧}
   \end{cases}
   $$
3. 带权图：在边或弧对应的位置存储两个顶点之间的权值，若不存在边，可以设为无穷或其他特殊符号，自己指向自己的权值为0
4. 相关代码：

#define MAX_VEX 6
typedef struct{
    char vexs[MAX_VEX]; // 顶点表
    int arc[MAX_VEX][MAX_VEX]; // 邻接矩阵
}MGraph;

void GraphInit(MGraph *G){
    for(int i = 0;i < MAX_VEX;i++){
        for(int j = 0;j < MAX_VEX;j++){
            G->arc[i][j] = 0;
        }
    }
}

// 创建邻接矩阵
G.arc[0][1] = 1; // 以此类推

// 无向图求度
int GraphD(MGraph G, int vexIndex){
    int d = 0;
    for(int i = 0;i < MAX_VEX;i++){
        if(G.arc[vexIndex][i] != 0) d++;
    }
    return d;
}

// 有向图求度
int Graph_D(MGraph G, int vexIndex){
    int id = 0;
    int od = 0;
    for(int i = 0;i < MAX_VEX;i++){
        if(G.arc[i][vexIndex] != 0) id++;
    }
    for(int i = 0;i < MAX_VEX;i++){
        if(G.arc[vexIndex][i] != 0) od++;
    }
    return id + od;
}

邻接链表

// 示例为有向图
A->B，A->C
链表：
A(src==0)
2(C)->1(B)->NULL 其中2 1为dest
以此类推
用一个数组存储链表，A:adjList[0]....以此类推

代码实现：

#define V 5

typedef struct VNode{
    int data;
    VNode *next;
}VNode;

VNode *adjList[V];

void init(){
    for(int i = 0;i < V;i++){
        adjList[i] = NULL;
    }
}

// 有向图
void addEdge(int src, int dest){
    VNode* newNode = (VNode*)malloc(sizeof(VNode));
    newNode->data = dest;

    newNode->next = adjList[src]; // 头插法
    adjList[src] = newNode;
}

// 无向图
void add_edge(int src, int dest){
    VNode* newNode = (VNode*)malloc(sizeof(VNode));
    newNode->data = dest;

    newNode->next = adjList[src];
    adjList[src] = newNode;

    VNode* newNode1 = (VNode*)malloc(sizeof(VNode));
    newNode1->data = src; 
    
    newNode1->next = adjList[dest];
    adjList[dest] = newNode1;
}

// 无向图求度
int GraphD(int src){
    int d = 0;
    VNode *node = adjList[src];
    while(node != NULL){
        d++;
        node = node->next;
    }
    return d;
}

// 有向图求度
int Graph_D(int src){
    int od = 0;
    VNode *node = adjList[src];
    while(node != NULL){
        od++;
        node = node->next;
    }

    int id = 0;
    for(int i = 0;i < V;i++){
        VNode *node1 = adjList[i];
        while(node1 != NULL){
            if(node1->data == src){
                id++;
            }
            node1 = node1->next;
        }
    }
    return id+od;
}

邻接链表和邻接矩阵对比

1. 稠密图：边的数量接近最大边数，或约等于$V^2$，每个顶点都相互连接
2. 稀疏图：边的数量接近最小边数，或等于V
3. 邻接链表存储稀疏图

   使用邻接矩阵会浪费大量内存空间(空间复杂度高)

4. 邻接矩阵存储稠密图

   最大化利用存储空间来存储边集

5. 检查一条边是否存在：
   1. 邻接矩阵：检查对应的元素位置是否为1 O(1)
   2. 邻接链表：遍历链表，找到指定的节点是否存在 O(V)
6. 创建边：
   1. 邻接矩阵：设置arc[i][j] = 1 O(1)
   2. 邻接链表：头插法 O(1)
7. 删除边：
   1. 邻接矩阵：设置arc[i][j] = 0 O(1)
   2. 邻接链表：遍历链表，找到待删除的节点并删除 O(V)
8. 新增顶点：
   1. 邻接矩阵：新建矩阵，复制原矩阵内容 O(V)
   2. 邻接链表：在顶点表中添加一个元素 O(1)

广度优先搜索算法(BFS)

1. 访问目标顶点，再访问其所有距离为1的顶点(邻居顶点)，然后访问距离为2的顶点，以此类推
2. 权值相等时，BFS是解决最短路径问题的首选方法
3. 相同距离的邻接顶点的访问顺序并不重要->BFS序列的顺序不唯一
4. 代码实现：
   1. 从初始节点开始，逐层访问所有相邻顶点(先进先出->队列)
   2. 顶点被访问，其邻居被加入队列的末尾，当前顶点从队列的前端被取出
   3. 搜索相邻顶点：
      1. 邻接矩阵：找对应的出边
      2. 邻接链表：找对应的链表，遍历