数据结构与算法速通

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. 最好：首位，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. 最好：末位，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. 最好：末位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)

栈

先进后出
插入和删除只能在栈顶操作
入栈和出栈：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;
}

队列

先进先出
时间复杂度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++;
    }
}

树

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

二叉树

每个结点最多有两个子结点：左子结点、右子结点
形态：
1. 单结点树：只包含一个结点(只有一个根结点)
2. 空二叉树：没有任何结点(根结点为空)
3. 左斜树：只有左子结点，没有右子结点
4. 右斜树：只有右子结点，没有左子结点
5. 满二叉树：叶子节点无左右子结点，其余节点均有左右子结点
6. 完全二叉树：除最后一层叶子结点可以为空，其余结点必须填满，叶子结点尽可能靠左排列(叶子结点允许缺失)
存入数组之后的下标：
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

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

链式存储

二叉树结点数量为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

先序
顺序：根，左，右

A B D E C F G
中序
顺序：左，根，右

D B E A F C G
后序
顺序：左，右，根

D E B F G C A
层次

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

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

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

哈夫曼树

哈夫曼编码条件：
1. 每单个字符都必须映射到一个唯一的二进制编码
2. 保证解码器能进行唯一解码(无损压缩)
3. 保证任何一个编码都不能是其他编码的前缀
无损压缩的选择：
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     (压缩编码方案)

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