参考资料：https://www.bilibili.com/video/BV1GW421A7qY/

所有代码均已在Ubuntu 20.04.6 LTS中测试通过

逻辑结构与存储结构

逻辑结构

逻辑结构指的是数据对象中数据元素间的相互关系，分为以下四种：

1. 集合结构
   集合结构中的数据元素除了同属于一个集合外，彼此之间没有其他关系。
2. 线性结构
   线性结构中的数据元素之间是一对一的关系。
3. 树形结构
   树形结构中的数据元素之间存在一对多的层次关系。
4. 图形结构
   图形结构的数据元素存在多对多的关系。

综上，逻辑结构是针对具体问题的，需要选择一个合适的数据结构来标识数据元素之间的逻辑关系。

存储结构

存储结构指的是数据的逻辑结构在计算机中的存储形式，可分为以下四种。

1. 顺序存储
   顺序存储结构就是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。简单理解就是数组形式。
2. 链式存储
   链式存储结构就是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。
   由于该种存储关系不能反映其逻辑关系，因此需要用一个指针存放数据元素的地址，然后通过地址找到相关联数据元素的地址。
3. 索引存储
   索引存储指通过特殊的数据结构将数据组织成树形结构，在这个树形结构中，每个结点都包含了若干个子结点或数据块，并且根据结点上的键值大小进行排序。通过对这些结点的查找，可以快速地定位到存储数据的位置，从而提高查询效率。
4. 散列存储
   散列存储又称哈希存储，是一种基于散列函数将数据元素映射到一个固定位置进行存储的技术，其所采用的底层数据结构通常是数组或哈希表等。

时间复杂度的计算

简单计算：数据结构—计算时间复杂度的常规方法
进阶计算：数据结构—计算时间复杂度“难题”的方法

线性表

线性表定义

线性表是由n个数据元素组成的有限序列，其数据元素间呈现出一对一的顺序关系，可使用顺序存储结构和链式存储结构来实现。

顺序表

顺序表的定义

线性表的顺序存储又称顺序表。
顺序表是指将数据元素按照其逻辑顺序依次存储在一组连续的物理位置上，通过数组来实现。顺序表以连续的存储单元顺序存放线性表的元素，可以根据下标直接访问任意位置的元素，查找和遍历较快，但插入和删除操作需要移动大量元素，效率较低。

注：顺序表下标从1开始，而数组下标从0开始。

顺序表的创建

#define MAX_SIZE 100  // 顺序表可达到的最大长度

typedef struct {
    int len;             // 顺序表实际长度
    int data[MAX_SIZE];  // 顺序表存储空间基地址
} SqList_t;  // 顺序表结构类型为SqList_t

SqList_t* SqList_init()
{
    // 为顺序表动态分配空间
    SqList_t* SqList = (SqList_t*)malloc(sizeof(SqList_t));

    // 初始化顺序表数据长度为0，并赋初值0
    SqList->len = 0;
    memset(SqList->data, 0, sizeof(SqList->data));
    
    return SqList;
}

顺序表元素的插入

在顺序表中插入元素时，需将插入点之后的元素依次后移，然后在插入点插入新元素。
例如，要在顺序表{1, 2, 3, 4, 5}的第三个位置上插入元素6，则实现过程如下：

1. 遍历至顺序表存储第3个数据元素的位置（此时指针指向元素3）；
2. 将元素3以及后续元素4和5整体向后移动一个位置；
3. 将新元素6插入腾出的位置。

int SqList_insert(SqList_t* SqList, int index, int value)
{
    // 索引值合法性判定
    if (index < 1 || index > (SqList->len + 1) || (SqList->len + 1) >= MAX_SIZE)
        return -1;

    // 将index后的所有元素后移一位
    for (int i = SqList->len - 1; i >= index - 1; i--)
        SqList->data[i + 1] = SqList->data[i];
    
    // 将value插入至顺序表index处，更新顺序表长度
    SqList->data[index - 1] = value;
    SqList->len++;

    return 0;
}

顺序表元素的删除

在顺序表中删除元素时，需将删除点之后的元素依次前移，然后删除顺序表最后一个元素。

int SqList_delete(SqList_t* SqList, int index, int* value)
{
    // 索引值合法性判定
    if (index < 1 || index > SqList->len || SqList->len > MAX_SIZE)
        return -1;

    // 提取出被删除元素值
    *value = SqList->data[index - 1];

    // 将index后所有元素前移一位
    for (int i = index; i < SqList->len; i++)
        SqList->data[i - 1] = SqList->data[i];
    
    // 更新顺序表长度
    SqList->len--;

    return 0;
}

顺序表元素的修改

在顺序表中修改元素时，需根据index找到对应的元素，然后用value进行替换即可。

int SqList_modify(SqList_t* SqList, int index, int value)
{
    if (index < 1 || index > SqList->len)
        return -1;
    
    // 直接根据index和value值对顺序表中对应元素进行修改
    SqList->data[index - 1] = value;

    return 0;
}

顺序表元素的查找

在顺序表中查找元素，需根据value值对整个表进行遍历，返回与value值一致的顺序表中数据下标。

int SqList_search(SqList_t* SqList, int value)
{
    // 默认顺序表中没有匹配value的元素
    int index = -1;

    // 遍历顺序表数据，若有多个元素与value相同，仅返回最后一个匹配的元素下标
    for (int i = 0; i < SqList->len; i++)
        if (SqList->data[i] == value)
            index = i;

    return index;
}

顺序表元素的逆序

顺序表的逆序操作可通过交换表头与表尾、表第二个元素和倒数第二个元素、表第三个元素和倒数第三个元素……以此类推来实现，直到两指针相遇。

int SqList_reverse(SqList_t* SqList)
{
    int temp;

    // 交换操作
    for (int i = 0; i <= SqList->len / 2; i++) {
        temp = SqList->data[i];
        SqList->data[i] = SqList->data[SqList->len - 1 - i];
        SqList->data[SqList->len - 1 - i] = temp;
    }

    return 0;
}

顺序表优缺点

优点

1. 支持随机访问， 可通过下标直接访问某个元素，时间复杂度为O(1)；
2. 不需要额外的指针域来存储结点关系，占用空间小；
3. 对于简单的线性表操作，如插入、删除、排序等，实现较为简单。

缺点

1. 插入和删除元素时，需要移动其他元素，时间复杂度为O(n)；
2. 大小固定，无法动态调整，不适用于动态变化的应用；
3. 需要改变存储空间时，须对大量数据进行搬移，效率较低。

单链表

单链表的定义

单链表由多个结点组成，每个结点包含一个值和一个指向下个结点的指针。单链表的头结点是链表的起点，每个结点通过指针连接在一起。
单链表的优点是插入和删除元素的效率很高，因为只需改变指针的指向即可，无需像数组一样移动元素。但访问单链表中的元素效率较低，因为需要遍历整个链表。

注：本小节均认为单链表的头结点不存放数据，“头结点”的概念区别于“链表的第一个结点”的概念。

单链表的创建

typedef struct node
{
    int data;           // 本链表当前结点中存储的数据
    struct node *next;  // 结构体指针，指向本链表中的下一结点
} LinkList_t;

// 本质是创建了一个链表的头结点，该结点不包含数据
LinkList_t* LinkList_init()
{
    // 为单链表动态分配空间
    LinkList_t* linklist = (LinkList_t*)malloc(sizeof(LinkList_t));
    if (linklist == NULL)
        return NULL;

    // 初始化单链表
    linklist->data = 0;
    linklist->next = NULL;

    return linklist;
}

单链表结点的插入

// 头插法：每次在头结点和第一个结点之间插入新结点
int node_insert_head(LinkList_t* LinkList, int value)
{
    // 为插入的结点动态分配内存，并赋值
    LinkList_t* node = (LinkList_t*)malloc(sizeof(LinkList_t));
    if (node == NULL)
        return -1;
    node->data = value;

    // 先使插入结点的*next指向原链表的第二个结点，然后断链，使头结点的*next指向新插入的结点
    node->next = LinkList->next;
    LinkList->next = node;

    return 0;
}

// 尾插法：每次在链表的末尾插入新结点
int node_insert_tail(LinkList_t* LinkList, int value)
{
    // 为插入的结点动态分配内存
    LinkList_t* node = (LinkList_t*)malloc(sizeof(LinkList_t));
    if (node == NULL)
        return -1;

    // 遍历找到当前链表的尾结点
    while (LinkList->next != NULL)
        LinkList = LinkList->next;
    // 退出循环时的LinkList指向链表尾结点
    LinkList->next = node;

    // 为尾结点赋值
    node->data = value;
    node->next = NULL;

    return 0;
}

单链表结点的删除

// 由于单链表的单向性，需先定位到待删除结点的上一个结点
int LinkList_delete(LinkList_t* LinkList, int value)
{
    while (LinkList->next != NULL) {
        if (LinkList->next->data == value) {
            LinkList_t* q = LinkList->next;    // 暂存待删除的结点
            // 使当前链表结点的next指针指向再往后的结点（越过待删除的结点）
            LinkList->next = LinkList->next->next;  
            free(q);  // 释放被删除结点的内存
            return 0;
        }
        else
            LinkList = LinkList->next;
    }

    printf("value %d not found in current linklist.\n", value);

    return -1;
}

单链表结点的修改

// 由于单链表的单向性，需先定位到待修改数据结点的上一个结点
int LinkList_modify(LinkList_t* LinkList, int old_value, int new_value)
{
    while (LinkList->next != NULL) {
        if (LinkList->next->data == old_value) {
            LinkList->next->data = new_value;
            return 0;
        }
        LinkList = LinkList->next;
    }

    printf("value %d not found in current linklist.\n", old_value);

    return -1;
}

单链表结点的查找

// 若在单链表中查找到指定的数据，则返回该数据在链表中的index
int LinkList_search(LinkList_t* LinkList, int value)
{
    int cnt = 0;
    
    while (LinkList->next != NULL) {
        cnt++;
        if (LinkList->next->data == value) {
            return cnt;
        }
        LinkList = LinkList->next;
    }

    return -1;
}

单链表逆序

LinkList_t* LinkList_reverse(LinkList_t* LinkList)
{
    LinkList_t* prev = NULL;  // 保存原链表当前结点的上一结点
    LinkList_t* post = NULL;  // 保存原链表当前结点的下一结点
    LinkList_t* node = LinkList->next;  // node初始指向链表的第一个结点（非头结点）

    while (node != NULL) {
        post = node->next;  // 保存当前结点的下一结点的信息
        node->next = prev;  // 将当前结点的下一结点指定为原链表当前结点的前一结点
        prev = node;        // 将当前结点作为下一次循环的前一结点
        node = post;        // 将当前结点的下一结点作为下一次循环的当前结点
    }
    // 退出循环后，prev指针指向逆序后链表的第一个结点，node指针指向NULL

    // 新申请一个结点作为逆序后链表的头结点
    LinkList_t* first = LinkList_init();
    if (first == NULL)
        return NULL;
    first->data = 0;
    first->next = prev;

    // 返回逆序后链表的头结点
    return first;
}

单链表优缺点

优点

1. 插入和删除结点时，只需改变指针的指向，时间复杂度为O(1)；
2. 可以动态分配内存空间，不受固定大小的限制，能够灵活应用；
3. 能比较容易地实现链表的翻转、查找中间结点等操作。

缺点

1. 不支持随机访问，查找指定结点需要遍历整个链表，时间复杂度为O(n)；
2. 每个结点都需要额外的指针域来存储下一个结点的地址，需要占用额外的存储空间；
3. 在访问某个结点之前，必须先访问它的前一个结点。

单循环链表

单循环链表的定义

单循环链表类似于单向链表，不同之处在于它的最后一个结点连接回第一个结点，形成了一个循环。

注：单循环链表中没有单链表中“头结点”的概念，每个结点均有数据域和指针域

单循环链表的创建

typedef struct node
{
    int data;           // 本链表当前结点中存储的数据
    struct node *next;  // 结构体指针，指向本链表中的下一结点
} LinkList_t;

LinkList_t* CycList_init(int value)
{
    // 为单链表动态分配空间
    LinkList_t* cyclist = (LinkList_t*)malloc(sizeof(LinkList_t));
    if (cyclist == NULL)
        return NULL;

    // 初始化单循环链表，头结点的下一结点指向自身
    cyclist->data = value;
    cyclist->next = cyclist;

    return cyclist;
}

单循环链表结点的插入

// 头插法: 每次在头结点之后插入新结点
int node_insert_head(LinkList_t* CycList, int value)
{
    // 为新插入的结点动态分配内存，赋值并令其下个结点指向原链表的第一个结点
    LinkList_t* node = (LinkList_t*)malloc(sizeof(LinkList_t));
    if (node == NULL)
        return -1;
    node->data = value;
    node->next = CycList->next;
    CycList->next = node;

    return 0;
}

// 尾插法：每次在单循环链表的末尾插入新结点
int node_insert_tail(LinkList_t* CycList, int value)
{  
    LinkList_t* node = (LinkList_t*)malloc(sizeof(LinkList_t));
    if (node == NULL)
        return -1;
    node->data = value;
    node->next = CycList;

    LinkList_t* l = CycList;
    // 遍历找到原链表的最后一个结点
    while (l->next != CycList)
        l = l->next;
    l->next = node;

    return 0;
}

单循环链表结点的删除

// 删除一个单循环链表中的结点，返回值为删除结点后的头结点
LinkList_t* node_delete(LinkList_t* CycList, int value)
{
    LinkList_t* l = CycList;
    
    // 要删除的是头结点
    if (CycList->data == value) {
        while (l->next != CycList)
            l = l->next;
        // 退出循环时，p为原链表的最后一个结点
        l->next = CycList->next;
        free(CycList);
        // 原头结点的下一个结点成为新的头结点
        return l->next;
    }
    // 删除的为非头结点
    else {
        // 遍历整个单循环链表
        while (l->next != CycList) {
            if (l->next->data == value) {
                LinkList_t* q = l->next;
                l->next = l->next->next;
                free(q);
                // 仍返回原链表的头结点
                return CycList;
            }
            l = l->next;
        }
    }

    printf("value %d not found in current linklist.\n", value);

    // 找不到待删除的元素，返回链表头结点
    return CycList;
}

单循环链表结点的修改

int CycList_modify(LinkList_t* CycList, int old_value, int new_value)
{
    if (CycList->data == old_value) {
        CycList->data = new_value;
    }
    else {
        LinkList_t* p = CycList;
        while (p->next != CycList) {
            if (p->next->data == old_value) {
                p->next->data = new_value;
                return 0;
            }
            p = p->next;
        }
    }

    printf("value %d not found in current linklist, modify error.\n", old_value);

    return -1;
}

单循环链表结点的查找

int CycList_search(LinkList_t* CycList, int value)
{
    int cnt = 1;

    if (CycList->data == value) 
        return cnt;
    else {
        LinkList_t* p = CycList;
        while (p->next != CycList) {
            cnt++;
            if (p->next->data == value)
                return cnt;
            p = p->next;
        }
    }

    printf("value %d not found in current linklist, search error.\n", value);

    return -1;    
}

单循环链表逆序

LinkList_t* CycList_reverse(LinkList_t* CycList)
{
    LinkList_t* prev = NULL;
    LinkList_t* curr = CycList;
    LinkList_t* post = CycList->next;

    prev = CycList;
    while (prev->next != CycList)
        prev = prev->next;
    // 将prev定位到单循环链表的最后一个结点
    while (post != CycList) {
        post = curr->next;
        curr->next = prev;
        prev = curr;
        curr = post;
    }  // 退出循环时，curr和post都指向原链表的头结点

    printf("After conversion:\n");

    return prev;
}

单循环链表的应用——Joseph问题

问题描述

设编号为1, 2, 3, ..., n的n个人围坐成一圈，约定序号为k (1 <= k <= n)的人从1开始报数，数到m的人出列，他的下一位又从1开始报数，数到m的人出列，以此类推，直到所有人出列为止。

求解函数

// 用于保存顺次删除结点的序号
int* array;

// n对应入参len，k对应入参start，m对应入参interval
int Joseph(int len, int start, int interval)
{
    printf("Total len = %d, initial point = %d, interval = %d\n\n", len, start, interval);

    // 为array动态分配空间并清零
    array = (int*)malloc(len * sizeof(int));
    if (array == NULL) {
        printf("Allocate memory for array error!\n");
        exit(1);
    }
    memset(array, 0, len * sizeof(int));
    
    int ret, cnt = 0, arr_cnt = 0;
    LinkList_t* node = NULL;
    
    // 初始化单循环链表头结点，并构建整个单循环链表
    LinkList_t* cyclist = CycList_init(1);
    if (cyclist == NULL) {
        printf("Allocate memory for cyclist error!\n");
        return -1;
    }

    for (int i = 2; i <= len; i++) {
        ret = node_insert_tail(cyclist, i);
        if (ret < 0)
            printf("insert node %d error!\n", i);
    }
    printf("Initial cyclist:\n");
    CycList_print(cyclist);

    LinkList_t* l = cyclist;
    // 定位到Joseph问题起点的上一结点
    if (start == 1) {
        while (l->next != cyclist) 
            l = l->next;
    }
    else {
        for (int j = 1; j < start - 1; j++)
            l = l->next;
    }
    printf("initial node: %d\n", l->next->data);
    
    // 注意：以下由于涉及node的内存释放，如果释放了单循环链表的头结点，则调用CycList_print()函数会出现段错误！！！
    // 循环结束条件：当前结点的下一结点指向自己（仅剩唯一结点）
    while (l->next != l) {
        // m = 1时for循环不生效，逢结点删除
        for (int j = 1; j < interval; j++)
            l = l->next;
        node = l->next;
        *(array + arr_cnt++) = node->data;
        l->next = l->next->next;
        free(node);

        printf("Deleted node:\n");
        for (int count = 0; count < arr_cnt; count++)
            printf("%d\t", *(array + count));
        printf("\n\n");
    }
    // 退出循环时，单循环链表仅剩最后一个结点
    *(array + arr_cnt++) = l->data;
    free(l);

    // 此时输出的是整个单循环链表删除结点的顺序
    printf("Deleted node:\n");
    for (int count = 0; count < arr_cnt; count++)
        printf("%d\t", *(array + count));
    printf("\n\n");
    
    return 0;
}

双链表

双链表的定义

双向链表由一系列结点组成，每个结点都包含一个指向前继结点和后继结点的指针，该种链表既可以从前往后遍历，又可以从后往前遍历。
双向链表的优点是可以方便地在链表中任意位置插入或删除结点，并且可以有效地支持双向遍历；缺点是使用了更多的指针空间，需要更大的内存。

双链表的创建

typedef struct node
{
    int data;
    struct node* prev;
    struct node* next;
} BiDirList_t;

BiDirList_t* BiDirList_init(int value)
{
    BiDirList_t* bidirlist = (BiDirList_t*)malloc(sizeof(BiDirList_t));
    if (bidirlist == NULL)
        return NULL;
    
    // 初始化双链表的第一个结点，前继与后继结点均为NULL
    bidirlist->data = value;
    bidirlist->prev = NULL;
    bidirlist->next = NULL;

    return bidirlist;
}

双链表结点的插入

// 每次在链表的头结点之后插入新结点
int node_insert_head(BiDirList_t* bidirlist, int value)
{
    BiDirList_t* node = (BiDirList_t* )malloc(sizeof(BiDirList_t));
    if (node == NULL)
        return -1;
    
    // 当前结点结构体成员赋值
    node->data = value;
    node->prev = bidirlist;
    node->next = bidirlist->next;
    // 更新上一结点的next指针
    bidirlist->next = node;
    // 更新下一结点的prev指针
    if (node->next != NULL)
        node->next->prev = node;
    
    return 0;
}

// 每次在链表的末尾结点之后插入新结点
int node_insert_tail(BiDirList_t* bidirlist, int value)
{
    BiDirList_t* node = (BiDirList_t* )malloc(sizeof(BiDirList_t));
    if (node == NULL)
        return -1;

    BiDirList_t* l = bidirlist;
    while (l->next != NULL)
        l = l->next;

    // 更新上一结点的next指针
    l->next = node;
    // 当前结点结构体成员赋值
    node->data = value;
    node->prev = l;
    node->next = NULL;

    return 0;
}

双链表结点的删除

// 返回值为删除结点后的双链表头结点地址
BiDirList_t* node_delete(BiDirList_t* bidirlist, int value)
{
    BiDirList_t* l = bidirlist;
    BiDirList_t* node;

    while (l->next != NULL) {
        if (l->data == value) {
            if (l->next != NULL) 
                l->next->prev = l->prev;

            if (l->prev != NULL)
                l->prev->next = l->next;
            else { // 删除的是第一个结点
                node = l->next;
                free(l);
                return node;
            }
            free(l);
            return bidirlist;
        }
        l = l->next;
    }
    // 待删除的是否是最后一个结点
    if (l->data == value) {
        l->prev->next = NULL;
        free(l);
    }
    else 
        printf("value %d not found in current BiDirList\n", value);

    return bidirlist;
}

双链表结点的查找

int node_modify(BiDirList_t* bidirlist, int value_old, int value_new)
{
    BiDirList_t* l = bidirlist;

    while (l->next != NULL) {
        if (l->data == value_old) {
            l->data = value_new;
            return 0;
        }
        l = l->next;
    }
    if (l->data == value_old) {
        l->data = value_new;
        return 0;
    }
    else
        printf("value %d not found in current bidirlist\n", value_old);

    return -1;
}

双链表逆序

// 返回值为逆序后双链表的首个结点
BiDirList_t* BiDirList_reverse(BiDirList_t* bidirlist)
{
    BiDirList_t* l = bidirlist;
    BiDirList_t* p;

    // 使用p指针交换一个结点中prev指针和next指针的内容
    while (l->next != NULL) {
        p = l->next;
        l->next = l->prev;
        l->prev = p;
        l = l->prev;
    }
    // 此时l指向双链表的最后一个结点
    l->next = l->prev;
    l->prev = NULL;

    return l;
}

栈与队列

栈

栈的定义

栈只能从最上层取出元素，且新加入的元素只能添加到最上层，具有后进先出的特点。
栈通常使用数组或链表实现。栈顶是最后一个入栈的元素，栈底是第一个进入栈的元素。向栈中添加元素的操作称为“进栈”或“入栈”，从栈中取出元素的操作称为“出栈”或“弹栈”。栈的操作过程中，只能访问栈顶元素，因此也被称为LIFO (Last In, First Out)数据结构。
注：C语言在调用函数时，函数内部创建的局部变量都使用栈保存。

栈的操作

1. 压栈(Push)：将数据元素插入到栈顶位置；
2. 弹栈(Pop)：删除栈顶元素，并返回该元素的值；
3. 取栈顶元素(Top)：返回栈顶元素，但不删除它；
4. 判断栈是否为空(IsEmpty)：栈中没有任何元素则返回真，否则返回假；
5. 判断栈是否已满(IsFull)：仅在使用顺序存储结构时有意义，已满返回真，否则返回假；
6. 清空栈(Clear)：将栈中所有元素清空；
7. 获取栈中元素个数(Size)：返回当前栈中元素个数。

顺序栈

顺序栈的定义

顺序栈是一种基于数组实现的栈，定义如下：

1. 栈元素存储在一个连续的内存区域中，称为数组；
2. 用一个整型变量top记录栈顶元素在数组中的位置，初始值为-1，标识空栈；
3. 一般情况下，栈的大小是固定的，即数组长度事先确定；
4. 操作包括入栈和出栈两种，执行入栈操作时，将元素插入到top + 1的位置，并将top值加一；执行出栈操作时，将top所指向的元素弹出并返回其值，并将top值减一。

顺序栈的数据结构

#define MAX_SIZE 16
typedef struct
{
    int data[MAX_SIZE];
    int top;
} SeqStack_t;

顺序栈的创建

SeqStack_t* SeqStack_init()
{
    SeqStack_t* seqstack = (SeqStack_t*)malloc(sizeof(SeqStack_t));
    if (seqstack == NULL)
        return NULL;
    memset(seqstack->data, 0, sizeof(seqstack->data));

    seqstack->top = -1;

    return seqstack;
}

顺序栈的操作

顺序栈是否为满

int SeqStack_isfull(SeqStack_t* seqstack)
{
    return (seqstack->top == (MAX_SIZE - 1));
}

顺序栈是否为空

int SeqStack_isempty(SeqStack_t* seqstack)
{
    return (seqstack->top == -1);
}

顺序栈的入栈

int SeqStack_push(SeqStack_t* seqstack, int value)
{
    if (SeqStack_isfull(seqstack)) {
        printf("Current SeqStack is full!\n");
        return -1;
    }

    seqstack->data[++seqstack->top] = value;

    return 0;
}

顺序栈的出栈

int SeqStack_pop(SeqStack_t* seqstack, int* pvalue)
{
    if (SeqStack_isempty(seqstack)) {
        printf("Current SeqStack is empty!\n");
        return -1;
    }

    *pvalue = seqstack->data[seqstack->top--];

    return 0;
}

链式栈

链式栈的定义

链式栈是一种基于链表实现的栈数据结构，与顺序栈不同的是，链式栈没有容量限制，可以动态地添加或删除元素，每个元素通过一个指针指向下一元素。
由于链式栈没有容量限制，因此入栈操作不会导致栈溢出；但是由于链式栈使用了动态内存分配，因此在出栈或清空栈时需要释放内存，以防止内存泄漏。

链式栈的数据结构

typedef struct node
{
    int data;
    struct node* next;
} LinkStack_t;

链式栈的创建

LinkStack_t* LinkStack_init(int value)
{
    LinkStack_t* node = (LinkStack_t*)malloc(sizeof(LinkStack_t));
    if (node == NULL) {
        printf("Init LinkStack error!\n");
        return NULL;
    }

    node->data = value;
    node->next = NULL;

    return node;
}

链式栈的操作

链式栈是否为空

int LinkStack_isempty(LinkStack_t* linkstack)
{
    return (linkstack->next == NULL);
}

链式栈的入栈

LinkStack_t* LinkStack_push(LinkStack_t* linkstack, int value)
{
    LinkStack_t* node = (LinkStack_t*)malloc(sizeof(LinkStack_t));
    if (node == NULL) {
        printf("Allocate memory for new node error!\n");
        return NULL;
    }

    node->data = value;
    node->next = linkstack;

    return node;
}

链式栈的出栈

LinkStack_t* LinkStack_pop(LinkStack_t* linkstack, int* value)
{
    if (LinkStack_isempty(linkstack)) {
        printf("Current LinkStack is NULL!\n");
        return NULL;
    }
    
    LinkStack_t* node = linkstack->next;
    *value = linkstack->data;
    free(linkstack);

    return node;
}

顺序栈和链式栈的优缺点

顺序栈

顺序栈的优点

1. 存储结构简单，可以使用数组来实现；
2. 实现简单，不需要考虑指针等复杂的数据结构。

顺序栈的缺点

1. 容量固定，当栈满时需要扩容；
2. 在插入和删除元素时需要移动其他元素，时间复杂度为O(n)。

链式栈

链式栈的优点

1. 长度可变，不存在容量问题；
2. 插入和删除元素只需要修改指针，时间复杂度为O(1);
3. 支持更多操作，如遍历和反转等。

链式栈的缺点

1. 存储结构相对复杂，需要使用指针；
2. 内存占用相对更大，需要额外的空间来存储指针。

队列

队列的定义

队列是一种先进先出(First In First Out, FIFO)的线性表，常用于实现多个进程间的数据共享。
队列通常有两个指针，一个指向队列头部，一个指向队列尾部。元素加入队列尾部，从头部出队。

队列的操作

1. 入队(Enqueue)：将元素添加到队列的末尾；
2. 出队(Dequeue)：从队列头部删除元素并返回该元素；
3. 队列长度(Length)：返回队列中元素的数量；
4. 队首元素(Front)：返回队列头部的元素，但不删除该元素；
5. 队尾元素(Rear)：返回队列尾部的元素，但不删除该元素。

当队列为空时，无法执行出队操作；当队列已满时，无法执行入队操作。为了解决这些问题，还可以引入循环队列等特殊类型的队列。

顺序队列

顺序队列中，根据队尾指针的更新方式，和队头指针的更新方式，可分为普通顺序队列和循环队列两种类型。

普通顺序队列

普通顺序队列是指在入队操作时，每次将队尾指针后移一位，并将元素插入到队尾指针所在位置。这就导致队尾满时，即便队头已经空出位置，也无法再插入新元素。普通顺序队列适用于元素的入队和出队较少的情况。

循环队列

循环队列同样包含两个指针：队头指针front和队尾指针rear。其中front指向队列的第一个元素，rear指向队列最后一个元素的下一个位置。与顺序队列不同的是，当队列满时rear指针不再前进，而是从数组的起始位置开始添加元素，形成一个循环。
队列空时，front == 0, rear == 0；队列满时，(rear + 1) % MAX_SIZE == front。

循环队列的数据结构

#define MAX_SIZE 10

typedef struct 
{
    int data[MAX_SIZE];
    int writeIdx;
    int readIdx;
} CycQueue_t;

循环队列的创建

CycQueue_t* CycQueue_init()
{
    CycQueue_t* q = (CycQueue_t*)malloc(sizeof(CycQueue_t));
    if (q == NULL) {
        printf("Allocate memory for CycQueue error!\n");
        return NULL;
    }
    memset(q, 0, sizeof(CycQueue_t));

    return q;
}

循环队列的操作

循环队列是否为满

int CycQueue_isfull(CycQueue_t* q)
{
    // 规定循环队列为满时，写指针+1后对循环队列最大长度取余的结果等于读指针idx
    // 正因如此，循环队列实际可用的长度比最大长度少1
    return (((q->writeIdx + 1) % MAX_SIZE) == q->readIdx);
}

循环队列是否为空

int CycQueue_isempty(CycQueue_t* q)
{
    // 规定循环队列为空时，写指针和读指针具有相同的idx
    return (q->writeIdx == q->readIdx);
}

循环队列的入队

int CycQueue_enqueue(CycQueue_t* q, int value)
{
    if (CycQueue_isfull(q)) {
        printf("CycQueue has been full!\n");
        return -1;
    }

    q->data[q->writeIdx] = value;
    q->writeIdx = (q->writeIdx + 1) % MAX_SIZE;
    
    return 0;
}

循环队列的出队

int CycQueue_dequeue(CycQueue_t* q, int* value)
{
    if (CycQueue_isempty(q)) {
        printf("CycQueue has been empty!\n");
        return -1;
    }

    *value = q->data[q->readIdx];
    q->readIdx = (q->readIdx + 1) % MAX_SIZE;

    return 0;
}

链式队列

链式队列的定义

链式队列使用头指针和尾指针分别指向队列的头结点和尾结点。
链式队列通过链表的方式将队列中的结点串连起来，相对于顺序队列来说，可以动态地增加和删减队列中的元素，但是由于使用了指针，因此其对内存的要求更高。

链式队列的数据结构

typedef struct node
{
    int data;
    struct node* next;
} LinkList_t;

typedef struct
{
    LinkList_t* front;  // 始终指向链表头结点（该结点不存储数据）
    LinkList_t* rear;   // 始终指向链表尾结点
} LinkQueue_t;

链式队列的创建

LinkQueue_t* LinkQueue_init(int value)
{
    LinkQueue_t* q = (LinkQueue_t*)malloc(sizeof(LinkQueue_t));
    if (q == NULL) {
        printf("Allocate memory for LinkQueue error!\n");
        return NULL;
    }

    q->front = q->rear = (LinkList_t*)malloc(sizeof(LinkList_t));
    if (q->front == NULL) {
        printf("Allocate memory for pWrite and pRead error!\n");
        return NULL;
    }
    q->front->data = q->rear->data = value;
    q->front->next = q->rear->next = NULL;

    return q;
}

链式队列的操作

链式队列是否为空

int LinkQueue_isempty(LinkQueue_t* q)
{
    // 队尾指针为空时，链式队列为空（但此时仍有头结点）
    return (q->rear == NULL);
}

链式队列的入队

// 链表的尾插法，新插入结点的下一结点为NULL
int LinkQueue_enqueue(LinkQueue_t* q, int value)
{
    LinkList_t* node = (LinkList_t*)malloc(sizeof(LinkList_t));
    if (node == NULL) {
        printf("Allocate memory for new node in LinkQueue error!\n");
        return -1;
    }
    node->data = value;
    node->next = NULL;

    // 当前链表尾结点的下一结点为新插入的node
    q->rear->next = node;
    // 更新链表尾结点
    q->rear = node;

    return 0;
}

链式队列的出队

int LinkQueue_dequeue(LinkQueue_t* q, int* value)
{
    if (LinkQueue_isempty(q)) {
        printf("LinkQueue has been empty!\n");
        return -1;
    }

    LinkList_t* l = q->front->next;
    *value = l->data;
    q->front->next = q->front->next->next;

    // 如果链表的第一个结点为空，则尾结点也为空
    if (q->front->next == NULL)
        q->rear = NULL;
    free(l);

    return 0;
}

串

串

串的定义

串(String)是由零个或多个字符组成的有限序列，又称为字符串。每个字符在串中都有一个位置，其位置从左到右逐一编号，最左边字符的位置为1，最右边字符的位置为n，n为串的长度。
串常用于文本编辑、字符串匹配、密码学和计算机语言等领域。在实际应用中，串也可用于表示各种类型的数据，如音乐、图像、视频等。

串的操作

1. 求长度：获取串的长度；
2. 求子串：截取某个位置的字符序列；
3. 比较：比较两个串是否相等或大小关系；
4. 插入：在一个串中插入另一个串；
5. 删除：删除指定位置上的某个子串；
6. 查找：在一个串中查找是否包含某个子串，返回其出现的位置；
7. 替换：用指定的串替换原串中的某个子串。

串的分类

串的存储分类通常有两种：

1. 顺序存储
   使用一段连续的内存空间存储，每个字符占用一个存储单元，串的长度为数组的长度。优点是随机访问速度快，缺点是插入和删除操作效率低。
2. 链式存储
   通过指针连接串中每个字符，并用一个头结点保存串的长度信息。优点是插入和删除操作效率高，缺点是随机访问速度慢。

顺序串

顺序串的定义

顺序串是指由一系列相邻字符组成的串，这些字符按照一定的顺序排列。
在内存中，顺序串通常被表示为一个字符数组，数组中的每个元素都代表串中的一个字符。由于数组在内存中是连续存储的，因此顺序串在内存中的存储也是连续的，可使用数组下标来访问和修改串中的各个字符。串的长度就是字符数组的长度。

顺序串的数据结构

#define MAX_SIZE 100

typedef struct 
{
    char ch[MAX_SIZE];
    int length;
} SeqString_t;

顺序串的创建

SeqString_t* SeqString_init()
{
    SeqString_t* s = (SeqString_t*)malloc(sizeof(SeqString_t));
    if (s == NULL) {
        printf("Allocate memory for SeqString error!\n");
        return NULL;
    }
    memset(s, 0, sizeof(SeqString_t));

    return s;
}

顺序串的操作

顺序串的长度

int SeqString_length(SeqString_t* s)
{
    return s->length;
}

顺序串是否为空

int SeqString_isempty(SeqString_t* s)
{
    return (s->length == 0);
}

顺序串是否为满

int SeqString_isfull(SeqString_t* s)
{
    return (s->length == MAX_SIZE);
}

两个顺序串是否相等

int SeqString_isequal(SeqString_t* s1, SeqString_t* s2)
{
    return (strcmp(s1->ch, s2->ch) == 0);
}

顺序串的插入

// 将substr插入到s字符串第pos个字符之后
int SeqString_insert(SeqString_t* s, int pos, char* substr)
{
    if (strlen(substr) <= 0) {
        printf("Length of string to insert (%ld) error!", strlen(substr));
        return -1;
    }
    if (pos > s->length || pos < 0) {
        printf("The position to insert exceeds the length of string\n");
        return -1;
    }
    if (s->length + strlen(substr) > MAX_SIZE) {
        printf("Sum of length of two strings exceeds MAX_SIZE.\n");
        return -1;
    }
    
    // 先根据待插入字符串的长度，将原字符串位于第pos个字符后的内容向后搬移
    memcpy(s->ch + pos + strlen(substr), s->ch + pos, s->length - pos + 1);
    // 将待插入的字符串拷贝至原字符串中腾出的空间
    memcpy(s->ch + pos, substr, strlen(substr));
    // 更新插入子串后，顺序串的长度
    s->length += strlen(substr);

    return 0;
}

顺序串删除指定长度字符

int SeqString_delete(SeqString_t* s, int pos, int len)
{
    if (pos >= s->length) {
        printf("No content after %dth characters in given string!\n", pos);
        return -1;
    }
    if (pos + len > s->length) {
        printf("Character to delete beyonds the string limit!\n");
        return -1;
    }
    memcpy(s->ch + pos, s->ch + pos + len, s->length - len + 1);
    memset(s->ch + s->length - len, 0, len);
    s->length -= len;

    return 0;
}

顺序串内查找子串

int SeqString_find(SeqString_t* s, char* str)
{
    return (strstr(s->ch, str) ? 1 : 0);
}

顺序串内替换子串

int SeqString_sub(SeqString_t* s, char* str, char* sub)
{
    char* p = strstr(s->ch, str);
    if (p == NULL) {
        printf("%s not found in string\n", str);
        return -1;
    }
    if (s->length + strlen(sub) > MAX_SIZE) {
        printf("Length of string exceeds MAX_SIZE after substitution\n");
        return -1;
    }
    
    // 指针相减除以数据类型的size得到偏移量
    int pos = (p - s->ch) / sizeof(char), ret;
    ret = SeqString_delete(s, pos, strlen(str));
    if (ret < 0) {
        printf("Delete %s in string error!\n", str);
        return -1;
    }
    ret = SeqString_insert(s, pos, sub);
    if (ret < 0) {
        printf("Insert %s in string error!\n", sub);
        return -1;
    }

    return 0;
}

顺序串内截取子串

int SeqString_extract(SeqString_t* s, char* str, int pos, int len)
{
    if (pos > s->length) {
        printf("pos %d exceeds string length\n", pos);
        return -1;
    }
    if (pos + len > s->length) {
        printf("Extracted string length is less than expected\n");
        return -1;
    }
    strncpy(str, &(s->ch[pos]), len);
    // 在提取出字符串的末尾加上'\0'字符
    str[len] = '\0';
    
    return 0;
}

顺序串的拼接

int SeqString_cat(SeqString_t* s1, SeqString_t* s2)
{
    if (s1->length + s2->length > MAX_SIZE) {
        printf("Connected string exceeds MAX_SIZE!\n");
        return -1;
    }
    strcat(s1->ch, s2->ch);
    s1->length += s2->length;

    return 0;
}

链式串

链式串的定义

链式串使用链表来存储字符串中的每个字符。
链式串的每个结点包含一个字符和一个指向下一结点的指针。由于链式串使用动态分配内存，因此其长度可以根据需要动态地增加或减少。

链式串的数据结构

typedef struct node
{
    char ch;
    struct node* next;
} LinkString_t;

链式串的创建

LinkString_t* LinkString_init()
{
    LinkString_t* s = (LinkString_t*)malloc(sizeof(LinkString_t));
    if (s == NULL) {
        printf("Allocate memory for LinkString error!\n");
        return NULL;
    }
    s->ch = 0;
    s->next = NULL;

    return s;
}

链式串的操作

链式串尾部插入字符

int LinkString_append_ch(LinkString_t* s, char ch)
{
    LinkString_t* node = (LinkString_t*)malloc(sizeof(LinkString_t));
    if (node == NULL) {
        printf("Allocate memory for new node error!\n");
        return -1;
    }
    node->ch = ch;
    node->next = NULL;

    LinkString_t* q = s;
    while (q->next != NULL)
        q = q->next;
    q->next = node;

    return 0;
}

将字符串插入链式串

int LinkString_append_str(LinkString_t* s, char* str)
{
    int len = strlen(str), ret;
    for (int i = 0; i < len; i++) {
        ret = LinkString_append_ch(s, *(str + i));
        if (ret < 0)
            printf("Append char %c in LinkString error!\n", *(str + i));
    }

    return 0;
}

链式串中字符替换

int LinkString_subs(LinkString_t* s, char old, char new)
{
    int flag = 0;
    LinkString_t* p = s;
    while (p->next != NULL) {
        if (p->next->ch == old) {
            p->next->ch = new;
            flag = 1;
        }
        p = p->next;
    }

    return flag;
}

链式串中字符删除

int LinkString_delete(LinkString_t* s, char ch)
{
    int flag = -1;
    LinkString_t* p = s;
    while (p->next != NULL) {
        if (p->next->ch == ch) {
            flag = 1;
            LinkString_t* l = p->next;
            p->next = p->next->next;
            free(l);
        }
        // 如果当前字符的下一字符仍是待删除的字符，则不移动指针
        if ((p->next->ch != ch))
            p = p->next;
    }

    return flag;
}

串的匹配

串的匹配算法

串的匹配是指在一个串（主串）中查找另一个串（成为模式串）出现的位置或判断它是否存在的问题。
数据结构中，串的匹配主要包括朴素匹配算法、KMP算法、BM算法、Sunday算法等。

1. 朴素匹配算法：对于主串中的每个字符，逐一与模式串中的字符进行比较。时间复杂度为O(m*n)，其中m为主串的长度，n为模式串的长度。
2. KMP算法：该算法利用前缀和后缀的概念，通过预处理模式串，来确定在主串中匹配失败时，模式串应跳过的字符数。时间复杂度为O(m+n)。
3. BM算法：该算法是一种启发式算法，利用模式串本身的信息快速跳过不匹配的子串，时间复杂度最优情况下为O(n/m)，其中n为主串长度，m为模式串长度。
4. Sunday算法：该算法同样是一种启发式算法，通过预处理模式串中最后一个字符出现的位置，快速跳过不匹配的子串，时间复杂度最坏情况下为O(m*n)，但实际运行效率较高。

朴素匹配算法

朴素匹配算法对主串的每个字符作为子串开头，与要进行匹配的字符串进行匹配。需要对主串做大循环，每个字符开头做长度为待匹配串长度的小循环，直到匹配成功或结束遍历。

int naive_str_match(char* str, char* pattern)
{
    int cnt = 0;  // 匹配成功的次数
    int m = strlen(str), n = strlen(pattern);
    int i, j;

    if (m < n) {
        printf("Length of pattern string is longer, match error!\n");
        return 0;
    }

    for (i = 0; i <= m - n; i++) {
        for (j = 0; j < n; j++) {
            if (*(str + i + j) != *(pattern + j))
                break;
        }
        if (j == n) {
            printf("Found %s at index %d\n", pattern, i);
            cnt++;
        }
    }

    return cnt;
}

KMP匹配算法

每次模式串匹配失败后，计算模式串向后移动的距离是KMP算法的核心部分。匹配失败后模式串移动的距离和主串没有关系，仅与模式串自身相关。
模式串中任何一个字符都可能导致匹配失败，因此模式串中的每个字符都应对应一个数字，来指示匹配失败后模式串移动的距离。因此可以给每个模式串配备一个数组next[]用于存储模式串中每个字符对应指针j重定向的位置，例如j = 2时，若该字符匹配失败，指针j应指向模式串下标为2的字符。

前缀字符串

指包含该串首个字符且不包含该串末尾字符的所有顺序子串。例如对于字符串“ABCD”，子串“A”“AB”“ABC”都是其前缀字符串。

后缀字符串

指包含该串末尾字符且不包含该串首个字符的所有顺序子串。例如对于字符串“ABCD”，子串“D”“CD”“BCD”都是其后缀字符串。

next[]数组的生成方式

对于每个字符串中的字符，取其和位于其之前的顺序字符串，该字符串中前缀字符串和后缀字符串具有相同字符的最大个数即为该字符的next值。
例如，对于字符串“AABAAF”：

1. 由于字符串“A”既是该串的首字符，也是该串的尾字符，所以根据上述规则，next[0]的值为0（事实上任何模式串的next[0]值均为0）；
2. 对于字符串“AA”，前缀字符串和后缀字符串均为“A”，所以next[1] = 1；
3. 对于字符串“AAB”，前缀字符串有“A”和“AA”，后缀字符串有“B”和“AB”，不存在具有相同字符的子串，所以next[2] = 0;
4. 同理可以得到next[3] = 1, next[4] = 2, next[5] = 0。

KMP算法的实现

#define MAX_SIZE 100

// 可以将next[i]理解为记录的是下标0 - i字符组成的字符串和下标0 - j字符组成的字符串的最长相等前后缀长度
void get_next_array(char* pattern, int* next)
{
    int i = 1;  // i初始指向模式串长度为2的子串串尾，也是next[]数组的下标
    int j = 0;  // j初始指向模式串的头部
    next[0] = 0;  // next数组的首个元素必为0

    for (; i < strlen(pattern); i++) {
        // 如果i和j指向的字符不同，且j>0，则对j进行回溯，直到j==0或i和j指向的字符相等
        while ((j > 0) && (pattern[i] != pattern[j]))
            j = next[j - 1];  //  该行代码事实上等价于j -= 1;是否更好理解？
        // 如果i和j指向的字符相同，则对j进行++操作，表示对于长度为i+1的前缀字符串，以j指向字符为尾部的模式串子串存在长度为++后j的数值的最长相等前后缀
        if (pattern[i] == pattern[j]) 
            j++;
        // 填写next[i]的值
        next[i] = j;
    }
}

int kmp_str_match(char* str, char* pattern)
{
    int next[MAX_SIZE];
    get_next_array(pattern, next);
    int i = 0, j = 0, cnt = 0;

    for (; i < strlen(str); i++) {
        while ((j > 0) && (str[i] != pattern[j]))
            j = next[j - 1];
        if (str[i] == pattern[j]) {
            j++;
        }
        if (j == strlen(pattern)) {
            printf("Successfully match at index %ld!\n", i - strlen(pattern) + 1);
            cnt++;
            j = 0;
        }
    }

    return cnt;
}

树

树的概念

树的定义

树是一种非线性的数据结构，它由若干个结点组成，这些结点通过边连接在一起。
树的最顶层结点称为根结点，每个结点可以有零个或多个子结点。除根结点外，每个结点都有且仅有一个父结点。没有子结点的结点称为叶子结点。
树的一些基本概念：

1. 结点：树中的每个元素称为结点，每个结点可以包含一个或多个数据元素，以及指向其子结点的指针；
2. 根结点：树的最顶层结点称为根结点，它没有父结点，是树的开始；
3. 子结点：每个结点下面可以有若干个子结点；
4. 叶子结点：没有子结点的结点；
5. 父结点：若某结点有其子结点，则该结点为其子结点的父结点；
6. 深度：从根结点到某指定结点的最长简单路径边的条数；
7. 高度：从某指定结点到叶子结点的最长简单路径边的条数；
8. 子树：以某结点为根结点，构成的子树包含该结点及其所有的子结点。
   树被广泛应用于搜索、存储、排序等领域。常见的树结构有二叉树、红黑树、B树等，还有一些高级的树结构如字典树、B+树、线段树等。

树的操作

1. 遍历：按某种规则依次访问树中的所有结点。常见的遍历方式有前序遍历、中序遍历和后序遍历。
2. 查找：在树中查找某个或某些结点。常见的查找算法包括深度优先算法和广度优先算法。
3. 插入：在树结构中插入一个新的结点。
4. 删除：从树结构中删除一个结点，并保持树的结构不变。
5. 统计：统计树中所有结点的数量、深度、高度等信息。
6. 排序：利用树结构进行排序。常见的排序算法包括二叉查找树、红黑树、AVL树等。
7. 建立：使用给定的数据构建一棵树，常见的方法有深度优先搜索和广度优先搜索。
8. 更新：修改树结构中某个结点的值或属性。

树的逻辑结构

树中任何结点都可以有零个或多个直接后继结点（子结点），但至多只能有一个直接前驱结点（父结点）。根结点没有前驱结点，叶结点没有后继结点。

树的存储结构

可以使用链式存储结构或顺序存储结构来实现树的存储。

链式存储结构

该存储结构使用链表来存储树。每个结点都包含一个数据元素和两个分别指向子结点和父结点的指针。链式存储结构虽然灵活，但是由于需要额外的空间存放指针，因此空间占用较大，访问效率不及顺序存储结构。

顺序存储结构

该存储结构使用数组来存储树。如果树的深度为k，则可以使用一个长度为2^k-1的数组来存储树。其中，根结点存放在数组的第一个位置，每个结点的左子结点存储在数组的第2i个位置，右子结点存储在数组的第2i+1个位置。若某个结点没有子结点，则可以使用空值来表示。对于不完全树，顺序存储结构浪费了较多空间，但访问效率较高。该存储结构适用于完全二叉树等高度相近的树。

二叉树

二叉树的定义

二叉树是一种树形结构，其中每个子结点最多有两个子结点，分别称为左子结点和右子结点。二叉树中，每个结点最多有一个父结点（根结点除外）。
二叉树是一种递归结构，因此在二叉树的定义中，也包括了递归定义。
二叉树可以是空树，也可以只有一个根结点

特殊的二叉树

斜树

所有结点都只有左子树的二叉树称为左斜树，所有结点都只有右子树的二叉树称为右斜树。左斜树和右斜树统称为斜树。

满二叉树

同时满足以下条件的二叉树被称为满二叉树：

1. 所有的叶子结点都在同一层；
2. 每个非叶子结点都有两个子结点；
3. 所有的结点都具有相同的深度或高度。

满二叉树也可描述为是一棵高度为h，且拥有(2^h-1)个结点的二叉树。
由于满二叉树具有良好的对称性和规律性，因此在某些算法和应用中，满二叉树比普通二叉树更容易处理和操作。

完全二叉树

同时满足以下条件的二叉树被称为完全二叉树：

1. 除最后一层外，所有层的结点都是满的；
2. 如果最后一层存在结点，那么这些结点都是从左到右依次排列的。

完全二叉树在存储和访问时具有一定的优势，因为其结构规则，每个结点的父结点、左右兄弟结点、左右子结点在数组中的位置可以通过简单的计算获得，因此常用数组存储。
除完全二叉树外的其他二叉树，基本使用链表作为树的存储结构。

二叉排序树

又称二叉搜索树（Binary Search Tree, BST），同时满足以下条件：

1. 对于任意一个非空结点，左子树上所有结点的键值小于其根结点的键值，右子树上所有结点的键值大于其根结点的键值。

对二叉排序树使用中序遍历，可以得到一个有序序列。其性质在插入、删除、查找等操作上具有良好的性能，时间复杂度为O(log n)，与树的高度有关。但如果插入的数据序列是有序的，则其时间复杂度会退化为O(n)。

平衡二叉树

平衡二叉树（Balanced Binary Tree, BBT）同时满足以下条件：

1. 左子树和右子树的高度之差不超过1；
2. 左子树和右子树都是平衡二叉树。

常见的平衡二叉树有红黑树、AVL树和B树等，其特点是树的高度越低，查询、插入、删除等操作的效率越高。虽然平衡二叉树的操作比普通二叉树要复杂，但其复杂度依然优于线性结构，因此具有良好的性能表现。

二叉树遍历

二叉树遍历是指按照某种顺序依次访问二叉树中的所有结点，常见的遍历方式有三种：前序遍历、中序遍历和后序遍历。

1. 前序遍历：先访问根结点，然后递归遍历左子树，最后递归遍历右子树。即根→左→右。
2. 中序遍历：先递归遍历左子树，然后访问根结点，最后递归遍历右子树。即左→根→右。
3. 后序遍历：先递归遍历左子树，然后递归遍历右子树，最后访问根结点。即左→右→根。

上述三种遍历方式都是深度优先遍历，此外还有以层序遍历为代表的广度优先遍历。

二叉树创建

递归创建二叉树和非递归创建二叉树各有优缺点。递归创建简单直观，但在数据量较大的情况下可能导致堆栈溢出，；非递归创建可以避免该问题，但需要借助队列等辅助空间。

递归创建

递归创建二叉树是一种简单且直观的方法，其基本思想是：先创建根结点，然后递归创建左右子树。

二叉树的数据结构

typedef struct node
{
    int data;
    struct node* left_ch;
    struct node* right_ch;
} BiTree_t;

二叉树的创建

// 创建一个数据自init_value始，terminal_value止的二叉树
BiTree_t* create_bitree(int init_value, int terminal_value)
{
    BiTree_t* bitree = (BiTree_t*)malloc(sizeof(BiTree_t));
    if (bitree == NULL) {
        printf("Allocate memory for bitree error!\n");
        return NULL;
    }

    bitree->data = init_value;
    printf("Added value: %d\n", bitree->data);
    
    if (2 * init_value <= terminal_value)
        bitree->left_ch = create_bitree(2 * init_value, terminal_value);
    else
        bitree->left_ch = NULL;
    if (2 * init_value + 1 <= terminal_value)
        bitree->right_ch = create_bitree(2 * init_value + 1, terminal_value);
    else
        bitree->right_ch = NULL;

    return bitree;
}

二叉树的遍历

// parent - left - right
void preorder_travelsal(BiTree_t* bitree)
{
    if (bitree == NULL)
        return;
    
    printf("%d\t", bitree->data);
    preorder_travelsal(bitree->left_ch);
    preorder_travelsal(bitree->right_ch);

    return;
}

// left - parent - right
void inorder_traversal(BiTree_t* bitree)
{
    if (bitree == NULL)
        return;

    inorder_traversal(bitree->left_ch);
    printf("%d\t", bitree->data);
    inorder_traversal(bitree->right_ch);

    return;
}

// left - right - parent
void postorder_traversal(BiTree_t* bitree)
{
    if (bitree == NULL)
        return;
    
    postorder_traversal(bitree->left_ch);
    postorder_traversal(bitree->right_ch);
    printf("%d\t", bitree->data);
}

非递归创建

非递归创建二叉树需要借助辅助数据结构——队列。其基本思路是：先创建根结点，然后依次将左右结点插入队列中，再逐个取出队列中的结点，继续插入其左右结点，直至队列为空。

二叉树的应用

二叉排序树

根据二叉排序树的定义，可以得知左子树结点值 < 根结点值 < 右子树结点值，所以对二叉树进行中序遍历，可以得到一个递增的有序序列。

二叉排序树的常用操作：

1. 插入结点：在二叉排序树中插入一个结点，保证二叉排序树的性质不被破坏；
2. 删除结点：从二叉排序树中删除一个结点，保证二叉排序树的性质不被破坏；
3. 查找结点：在二叉排序树中查找一个结点；
4. 遍历操作：即采用前序、中序或后序遍历方式遍历整个二叉树；
5. 调整平衡：在插入或删除结点后，若二叉排序树不平衡，可通过旋转操作进行调整。

二叉排序树常用于实现动态集合（集合元素可以动态增删的集合），其兼具数组和链表的优点：

1. 比数组更灵活，支持动态增删元素；
2. 比链表更高效，支持快速查找、插入和删除操作。

平衡二叉树

平衡二叉树是一种特殊的二叉搜索树，其中任意节点的左右子树的高度差不超过1，因此平衡二叉树的形态更稳定，插入、查找和删除操作的时间复杂度都可以达到O(log n)。

常见的平衡二叉树包括：

1. AVL树：是一种具有平衡性质的二叉搜索树，其任意结点的左右子树高度差不超过1。AVL树的调整比较频繁，但对于查找操作效率很高。
2. 红黑树：是一种自平衡二叉搜索树。红黑树的插入和删除操作一般比AVL树更快，但对于查找操作，AVL树效率更高。
3. 替罪羊树：是一种动态平衡二叉搜索树，能保证树高变化不会超过log n，但对插入和删除操作的时间复杂度略高于AVL树和红黑树。

总之，平衡二叉树通过保持树的平衡性，使得查找、插入和删除等操作都能够在O(log n)的时间复杂度内完成，是一种高效的数据结构。

哈夫曼树

哈夫曼树是一种最优二叉树，也叫最优前缀编码树，其构建过程基于贪心算法，可应用于数据压缩、哈夫曼编码、数据加密、图像压缩等方面。

权的理解

在许多应用中，树中结点常被赋予一个表示某种意义的数值，称为该结点的权(Weight)。从树的根到任意结点的路径长度（经过的边数）与该节点上权值的乘积，称为该结点的带权路径长度。

WPL的理解

结点带权路径长度：是从树根到该结点的路径长度和结点上权的乘积。
树的带权路径长度：是所有叶子结点的带权路径长度之和，记为WPL。

在含有n个带权叶结点的二叉树中，其中WPL最小的二叉树称为哈夫曼树，也称最优二叉树。

哈夫曼树的构造

1. 先把有权值的叶子结点按照大小排成一个有序序列；
2. 取两个权值最小的结点分别作为左右子结点（左结点具有更小的权值），它们父结点的权值为这两个子结点权值之和；
3. 从有序序列中移除步骤2中的左右子结点，并将构造出的父结点插入到有序序列中；
4. 重复步骤2和步骤3，直到出现根结点。

图

图的概念

图与线性表和树的对比

图是一种比线性表和树更为复杂的数据结构。

线性表：元素之间是线性关系，即表中元素最多一个直接前驱和一个直接后驱。
树：元素之间是层次关系。除根外，元素只有唯一直接前驱，但可以有若干个直接后继。
图：任意的两个元素都可以有若干个直接前驱和直接后继，属于网状结构类型。

实际上，树是图的特例——有向无环图。

图的定义

数据结构图是一种用图形方式表示数据结构的方法，它用结点和边来表示数据元素和它们之间的关系，通常用于可视化和理解数据结构的内部结构和算法。

数据结构图包含以下几个部分：

1. 结点：表示数据元素，可以是单个值或复合结构；
2. 边：表示结点间的关系，包括数据元素之间的直接关系和操作序列之间的控制流关系；
3. 方向箭头：表示结点与边之间的方向，如单向链表和有向图；
4. 标记：表示结点和边的额外信息，如权值和结点状态等。

图的操作

1. 添加结点和边：可使用邻接矩阵或邻接表等数据结构来实现；
2. 删除结点和边：应注意在删除结点时需要将与该节点相连的边也都删除掉；
3. 遍历图：通过DFS或BFS遍历图中的结点，以进行图的搜索和路径规划等操作；
4. 求最短路径：使用Dijkstra算法或Floyd算法，求解图中两个结点之间的最短路径；
5. 求最小生成树：使用Prim算法或Kruskal算法求解图的最小生成树；
6. 检测环：对于有向图和无向图都可以使用DFS和BFS等算法判断是否存在环；
7. 拓扑排序：对于有向无环图，可使用拓扑排序确定结点的先后顺序。

图的存储结构

图可以使用邻接矩阵和邻接表两种方式进行存储。

邻接矩阵

邻接矩阵这一存储方式是使用一个二维数组来表示图的每一个结点之间的关系，数组中的元素表示两个结点之间的边的权重。如果两个结点之间没有边相连，则数组中相应位置的元素值应为无穷大或0。

邻接表

邻接表这一存储方式是使用一个数组来存储所有结点，每个数组中的元素为一个链表，链表中存储与该结点相邻的结点及其边的权重。邻接表的存储方式更适合稀疏图（即边比结点少的图），在这种情况下使用邻接表可以节省空间。

图的遍历

图的遍历是树的遍历的推广，是按照某种规则（或次序）访问图中各顶点一次且仅一次的操作。
由于图可能会存在回路，为避免顶点在遍历的过程中未被访问和被多次访问，应在遍历的过程中记下每个访问过的顶点，即每个顶点都应对应一个标志位，初始值为false，一旦该顶点被访问，就将其置为true。
对图的遍历通常有深度优先搜索和广度优先搜索两种方法。

深度优先搜索算法

类似于树的前序遍历。假设初始时图中各顶点均未被访问过，从图中的某顶点（设为V0）出发，访问V0，然后搜索V0的一个邻接点Vi，若其未被访问，则访问之，并接着搜索Vi的邻接点Vj，重复此过程直到某顶点的邻接点被全部访问完毕，然后回溯至其上一顶点，继续按上述过程进行搜索，直到所有能被访问的顶点都被访问过一遍。

广度优先搜索算法

类似树的按层次遍历。假设初始时图中各顶点均未被访问过，从图中的某顶点（设为V0）出发，访问V0，然后依次访问V0的所有邻接点，然后分别从这些被访问过的顶点出发，并仍按此方式搜索这些邻接点各自的所有邻接点，直到能访问的顶点都访问完毕。
为了控制广度优先算法的正确搜索，需要用到队列技术，即访问完一个顶点后，让该顶点的序号进队，然后取出队头，考察访问过的顶点的各邻接点，将未访问过的邻接点访问后再依次进队，重复此过程，直到队空为止。

最短路径

解决带权有向图中两顶点间最短路径问题有两个经典算法，分别是Dijkstra（迪杰斯特拉）算法和Floyd（弗洛伊德）算法。

查找

查找的概念

查找的理解

查找是指在一组数据中查找特定元素的过程。数据结构是一组数据的表示方式，一些数据结构也提供了在其中查找元素的能力。
常见的查找方法包括线性查找、二分查找、哈希查找等。如果数据结构中元素存储的方式使得查找速度更快，可以提高算法的效率。

查找表的理解

数据结构中，查找表(Lookup Table)是一种用于快速查找数据的结构。

查找表是由同一类型的数据元素（或记录）构成的集合，其中每个条目包含一个关键字和一个值，这个关键字可以是任何可用于查找数据的唯一标识符，值则表示与之对应的数据。如果该关键字可以唯一地标识一个记录，则称该关键字为主关键字(Primary Key)，对于可标识多个数据元素的关键字，称其为次关键字(Secondary Key)。

查找就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。

查找表的主要优势在于可以通过关键字来快速查找数据，而不需要遍历整个数据集合。通过查找表，可以大大提高处理的速度和准确性。

查找表的分类

1. 按照实现方式分类
   • 基于比较的查找表，如线性查找、二分查找、插值查找等
   • 基于散列的查找表，如哈希表
2. 按照数据结构分类
   • 线性表，如数组、链表
   • 树形结构，如二叉搜索树、B树、红黑树等
   • 散列表，如链表、开放地址法
3. 按照查找条件分类
   • 静态查找表，即查找表在创建之后不再发生变化
   • 动态查找表，即查找表在创建后仍能动态进行添加、删除、修改元素等操作。

顺序查找

顺序查找是一种简单的查找算法，也称线性查找。
顺序查找的基本思路时从数据集合的第一个元素开始，逐个比较直到找到目标元素。对于数据集合大小为n的情况，最坏情况下需要比较n次，因此时间复杂度为O(n)。顺序查找适用于无序集合和小型数据集，对于大型数据集其效率很低，通常改用二分查找等更高效的算法。

int sequence_search(int* array, int target)
{
    for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++) 
        if (array[i] == target)
            return i;

    return -1;
}

有序查找

二分查找

二分查找（也称折半查找Binary Search）是一种在有序数组中查找目标元素的高效算法。其基本原理是从数组的中间位置开始查找，每次将查找范围缩小一半，直到找到目标元素或者确定目标元素不存在为止。

二分查找的算法流程如下：

1. 用两个变量left和right分别表示待查找区间的左右端点，初始时将left置为0，right置为n - 1，其中n为数组长度；
2. 在待查找区间中，取中间位置mid = (left + right) / 2，将mid对应的元素与目标元素进行比较，如果相等则直接返回mid作为目标元素的下标；
3. 如果mid对应的元素小于目标元素，则目标元素必定在mid之右，此时将待查找区间缩小为[mid + 1, right]，重复步骤2；如果mid对应的元素大于目标元素，则目标元素必定在mid之左，此时将待查找区间缩小为[left, mid - 1]，重复步骤2；
4. 若left > right，说明已遍历完整个区间且未找到目标元素，返回-1。

int binary_search(int* array, int n, int target)
{
    int left = 0, right = n - 1;
    int mid = 0;

    while(left <= right) {
        mid = (left + right) / 2;
        if (array[mid] == target)
            return mid;
        else if (array[mid] < target)
            left = mid + 1;
        else if (array[mid] > target)
            right = mid - 1;
        else
            printf("Undefined behivor!\n");
    }

    return -1;
}

二分查找的时间复杂度为O(log n)，速度非常快，适用于静态查找，即在不需要频繁插入和删除元素的情况下进行查找。但是二分查找依赖于数组有序，如果数组无序，需要先对其进行排序。同时，二分查找也不适合在链表等非随机访问数据结构中进行查找。

插值查找

插值查找(Interpolation Search)是一种在有序数组中查找目标元素的算法，与二分查找类似，但是基本原理是根据目标元素的估计位置进行查找，而非取中间位置。
插值查找的算法流程如下：

1. 用两个变量left和right分别表示待查找区间的左右端点，初始时将left置为0，right置为n - 1，其中n为数组长度；
2. 计算目标元素的估计位置pos，pos = left + (target - array[left]) / (array[right] - array[left]) * (right - left)，其中array[]为有序数组，target为目标元素；
3. 将pos对应的元素与目标元素进行比较，如果相等则直接返回pos作为目标元素的下标；
4. 如果pos对应的元素小于目标元素，则目标元素必定在pos之右，此时将待查找区间缩小为[pos + 1, right]，重复步骤2；如果pos对应的元素大于目标元素，则目标元素必定在pos之左，此时将待查找区间缩小为[left, pos - 1]，重复步骤2；
5. 若left > right，说明已遍历完整个区间且未找到目标元素，返回-1。

int interpolation_search(int* array, int n, int target)
{
    int left = 0, right = n - 1;
    int pos = 0;

    while(left <= right) {
        pos = left + (target - array[left]) / (array[right] - array[left]) * (right - left);
        if (array[pos] == target)
            return pos;
        else if (array[pos] < target)
            left = pos + 1;
        else if (array[pos] > target)
            right = pos - 1;
        else
            printf("Undefined behivor!\n");
    }

    return -1;
}

插值查找的时间复杂度不固定，取决于目标元素的估计位置，最优情况下的时间复杂度为O(1)，此时目标元素恰好位于数组的中间位置；最坏情况下的时间复杂度为O(n)，此时数组元素分布不均匀，插值查找每次都取到了数组的边界位置。

平均情况下插值查找的时间复杂度为O(log n)，比二分查找略快。但插值查找对于较大规模的输入可能会出现整型溢出的问题，因此在实际应用中需要进行特殊处理。

斐波那契查找

斐波那契查找是一种基于二分查找算法和斐波那契数列特性的查找算法。
与二分查找不同，斐波那契查找不是使用中间索引来划分待查找区间，而是利用斐波那契数列中相邻两项的比值趋近于黄金分割比率的特性来划分待查找区间，该比值约为1.618。

斐波那契查找算法的基本思想是将待查找的数组划分为两部分，其中一个部分的长度为F(k - 1)，另一个部分的长度为F(k - 2)，其中k是满足F(k) - 1 >= n的最小整数，F(k)是斐波那契数列，n为数组长度。然后根据需要查找的元素与待查找区间中元素的大小关系，将查找区间进一步缩小，直到找到需要查找的元素或查找区间为空为止。

斐波那契查找的时间复杂度为O(log n)，比传统的顺序查找和二分查找都要快，但与二叉搜索树和散列表相比，其优势不够明显。

线性索引查找

线性索引查找的理解

线性索引查找是一种基于索引结构的查找算法，通过在数据集合上建立一个索引表，然后在索引表中定位查找元素所在的数据区间，再在数据区间中使用顺序查找等方法查找目标元素。线性索引查找适用于数据集合较大，但查找的元素比较少的情况，可以大大减少查找时间。

线性索引查找的基本思路是：首先将数据集合划分为若干个大小相等的块，然后建立一个索引表，索引表的每一项记录了对应块的起始元素的位置和块的长度。接着，根据需要查找的元素的值与索引表中对应块的最小值和最大值的比较结果，确定需要查找的元素所在的块，然后在该块中使用顺序查找等方法查找目标元素。

线性索引查找的时间复杂度为O(m + n/m)，其中m为块的大小，n为数据集合的大小。当块的大小合理选择时，线性索引查找可以比顺序查找等方法更快地找到需要查找的元素。但是构建索引表需要额外的存储空间，且索引表需要随着数据集合的改变而实时更新，因此在数据集合经常变化的情况下，线性索引查找的效率可能会受到影响。

核心思想：分块。

线性索引查找的种类

1. 稠密索引：指索引表中每个数据块都有一个索引项，适用于数据集合较小的情况下。由于每个数据块都需要一个索引项，因此稠密索引需要占用大量存储空间。
2. 稀疏索引：指索引表中只有一部分数据块有对应的索引项，适用于数据集合较大的情况下。由于只需要对部分数据块建立索引项，因此稀疏索引可以节省存储空间，但查找效率可能会受到影响。
3. 多级索引：指索引表不止一级，每一级索引指向下一级索引的起始位置，最终指向对应的数据块。多级索引可以减小索引表的长度，提高查找效率，但是需要占用更多的存储空间。
4. 倒排索引：是一种特殊的索引结构，其将数据集合中的每个关键词出现的位置都记录下来，并建立一个以关键词为索引的索引表，方便快速查找数据集合中包含特定关键词的数据项。倒排索引适用于海量数据的查找，并且支持高效的文本搜索和信息检索。

二叉排序树查找

二叉排序树的每个结点值都大于或等于其左子树任何结点的值，而小于或等于其右子树任何结点的值，是一种常用的数据结构，可以高效地进行插入、查找和删除操作。

typedef struct node 
{
    int data;
    struct node* left_ch;
    struct node* right_ch;
} Bstnode_t;  // Binary Search Tree

void insert_node(Bstnode_t** bitree, int data)
{
    if (*bitree == NULL) {
        Bstnode_t* root = (Bstnode_t*)malloc(sizeof(Bstnode_t));
        if (root == NULL) {
            printf("Allocate memory for root node in Bsttree error!\n");
            exit(1);
        }
        root->data = data;
        root->left_ch = NULL;
        root->right_ch = NULL;
        *bitree = root;  // Root node assignment
        return;
    }
    else {
        if (data < (*root)->data) 
            insert_node(&((*root)->left_ch), data);
        else if (data > (*root)->data)
            insert_node(&((*root)->right_ch), data);
        else {  // 这里对二叉排序树的定义，实质上要求树中每个元素大小都不相同
            printf("Insert new node error! Value %d has existed.\n", data);
            return;
        }
    }
}

void delete_node(Bstnode_t** bitree, int data)
{
    if (bitree == NULL) {
        printf("Bsttree has been NULL!\n");
        return;
    }
    else {  // Root node of bitree is not NULL
        if (data < (*bitree)->data)
            delete_node(&((*bitree)->left_ch), data);
        else if (data > (*bitree)->data)
            delete_node(&((*bitree)->right_ch), data);
        else {
            // 待删除结点为叶子结点，直接删除即可
            if (((*bitree)->left_ch == NULL) && ((*bitree)->right_ch == NULL)) {
                
                Bstnode_t* temp_node = *bitree;
                *bitree = NULL;
                free(temp_node);
                printf("Delete value %d from bitree success.\n", data);
                return;
            }
            // 待删除结点只有左子树，则让左子树代替该结点
            else if (((*bitree)->left_ch != NULL) && ((*bitree)->right_ch == NULL)) {
                Bstnode_t* temp_node = *bitree;
                *bitree = (*bitree)->left_ch;
                free(temp_node);
                printf("Delete value %d from bitree success.\n", data);
                return;
            }
            // 待删除结点只有右子树，则让右子树代替该结点
            else if (((*bitree)->left_ch == NULL) && ((*bitree)->right_ch) != NULL) {
                Bstnode_t* temp_node = *bitree;
                *bitree = (*bitree)->right_ch;
                free(temp_node);
                printf("Delete value %d from bitree success.\n", data);
                return;
            }
            // 待删除结点有左右子树，则以该结点中序遍历的后继结点代替该结点
            // 该结点中序遍历的后继结点即为其右子树中，值最小的结点
            else if (((*bitree)->left_ch != NULL) && ((*bitree)->right_ch != NULL)) {
                Bstnode_t* temp_node = (*bitree)->right_ch;
                while (temp_node->left_ch != NULL)
                    temp_node = temp_node->left_ch;
                (*bitree)->data = temp_node->data;
                // 在右子树中删除值为data的结点
                delete_node(&((*bitree)->right_ch), temp_node->data);
                printf("Delete value %d from bitree success.\n", data);
                return;
            }
        }
    }
}

平衡二叉树查找

平衡二叉排序树是一种基于二叉树的高效的数据结构，能快速地处理动态数据集合，尤其适用于需要频繁查找、插入和删除操作的情况。

平衡二叉排序树具有以下特点：

1. 每个结点至多只有两个子结点，左子结点小于父结点，右子结点大于父结点；
2. 所有叶子结点到根结点的路径长度相差不超过1，保证整个树的高度平衡；
3. 支持快速的查找、插入和删除操作，时间复杂度为O(log n)。

平衡二叉排序树的实现主要有红黑树、AVL树、B树、B+树等，其中AVL树是最早被发明的一种平衡树结构，其特点是任意结点的左右子树高度相差不超过1，因此查询效率非常高。相较于红黑树，AVL树的旋转操作比较繁琐，插入和删除效率稍低；而B树和B+树则主要用于磁盘存储和数据库索引，可以支持非常大的数据集。

多路查找树（B树）查找

多路查找树是一种基于多叉树的数据结构，与二叉树不同的是，每个结点可以有多个子结点。常见的多路查找树有B树、B+树、B*树等。

• B树：B树是一种平衡的多路查找树，每个结点可以存储多个关键字和指向子结点的指针。为了保持平衡，B树要求每个结点至少填满m/2个关键字，最多填满m个关键字，其中m为B树的阶数。通常情况下，m的值为几百到上千。B树的查找、插入和删除操作的时间复杂度均为O(log n)，是一种非常有效的数据结构。
• B+树：是在B树的基础上进一步优化的数据结构。与B树不同的是，B+树的内部结点不存储数据，仅存储关键字和指向子结点的指针。所有数据都存储在叶子结点中，这样可以减少磁盘I/O操作，提高查询效率。另外，B+树的叶子结点使用链表连接，支持范围查询和顺序访问。B+树的优势在于提供了更快的查询速度和更好的范围查询性能。
• B*树：是在B树的基础上进一步优化的数据结构。与B树不同的是，B*树的结点填满要求比B树更加严格，可以让树长得更高而非更宽，这样可以减少磁盘I/O操作，提高查询效率。B*树与B+树类似，但是在结点分配和合并时会比B+树更灵活，因此可以减少树的高度，提高查询效率。

红黑树查找

红黑树是一种自平衡的二叉查找树，是一种具有很高效率的数据结构，常用于实现映射、集合等数据类型。其原理如下：

1. 红黑树是一种特殊的二叉查找树，每个结点要么是红色的，要么是黑色的；
2. 根结点固定为黑色，所有叶子结点都是黑色的空结点；
3. 如果一个结点是红色的，那么它的子结点必须是黑色的；
4. 从根结点到叶子结点的路径上，不能有两个联系的红色结点；
5. 任何结点到其所有后代叶子结点的简单路径上包含相同数量的黑色结点。

根据上述规则，红黑树能够自平衡，即其高度保持在O(log n)级别。为了实现插入、删除、查找等操作，红黑树还需要维护一些额外信息，如结点的父结点、左子结点、右子结点等。在进行插入、删除等操作时，需要通过旋转结点、重新着色等方式维护红黑树的平衡性和其他性质。

总的来说，红黑树是一种非常优秀的数据结构，具有较快的插入、删除和查找性能，并且能够自平衡，保持高效率。

哈希查找

哈希查找可以实现常数时间复杂度的插入、删除和查找操作。哈希表的原理如下：

1. 哈希函数：它将数据映射到哈希表中的一个位置，是哈希表中最关键的部分。好的哈希函数应该让数据均匀分布在哈希表中，避免出现哈希冲突。
2. 哈希冲突：由于哈希函数不一定能够将每个数据都映射到唯一的位置，因此可能会出现冲突，该冲突称为哈希冲突。为了解决哈希冲突，哈希表通常使用链表等数据结构来存储冲突的数据。
3. 插入：向哈希表中插入数据时，首先使用哈希函数计算出数据应该插入的位置，然后将数据插入到对应位置的链表中。
4. 查找；先使用哈希函数计算出数据的位置，然后在对应位置的链表中查找数据。
5. 删除：先使用哈希函数计算出数据的位置，然后在对应位置的链表中删除数据。

总的来说，哈希函数将关键字映射到哈希值，并将哈希值作为索引，直接访问哈希表中对应位置的元素。相比于顺序查找和二分查找，散列查找具有更快的查找速度，适用于海量数据的查找场景。

散列查找的优点是速度快，只需要O(1)的时间复杂度即可完成查找操作，但同时也存在一些缺点，例如哈希函数的设计需要考虑到冲突问题，即不同关键字可能具有相同的哈希值，这会影响查找的效率。此外，哈希表需要占用较大的空间，而且在插入或删除元素时需要重新调整哈希表，会导致性能下降。

#define MAX_SIZE 100

typedef struct node
{
    char key[20];
    int value;
    struct node* next;
} HashNode_t;

typedef struct
{
    int size;
    HashNode_t** table;
} HashTable_t;

void HashTable_init(HashTable_t* ht)
{
    ht->size = MAX_SIZE;
    ht->table = (HashTable**)malloc(sizeof(HashNode_t*) * ht->size);
    memset(ht->table, 0, sizeof(HashNode_t*) * ht->size);
}

int Hash_encode(char* key)
{
    int code = 0;
    for (int i = 0; i < strlen(key); i++)
        code = code * 31 + key[i];
    return code % MAX_SIZE;
}

void HashTable_insert(HashTable_t* ht, char* key, int value)
{
    int index = Hash_encode(key);

    HashNode_t* hn = (HashNode_t*)malloc(sizeof(HashNode_t));
    strcpy(hn->key, key);
    hn->value = value;
    hn->next = ht->table[index];  // 头插法

    ht->table[index] = hn;
}

int HashTable_search(HashTable_t* ht, char* key)
{
    int index = Hash_encode(key);
    HashNode_t* node = ht->table[index];

    while (node) {
        if (strcmp(node->key, key) == 0) {
            printf("Find [%s] success, value: %d\n", key, node->value);
            return node->value;
        }
        node = node->next;
    }
    printf("string [%s] not exist!\n", key);
    return -1;
}

void HashTable_delete(HashTable_t* ht, char* key)
{
    int index = Hash_encode(key);
    HashNode_t* node = ht->table[index], pre = NULL;

    while (node) {
        if (strcmp(node->key, key) == 0) {
            if (pre == NULL)
                ht->table[index] = node->next;
            else
                pre->next = node->next;
            free(node);
            printf("Deleted string [%s].\n", key);
            return;
        }
        pre = node;
        node = node->next;
    }
    printf("Delete string [%s] error!\n", key);

    return;
}

排序

排序的概念

排序是指对一组数据按照一定的规则进行排列的过程。

排序是计算机科学中的重要操作，因为它可以提高数据处理的效率。在实际应用中，需要根据具体的需求选择不同的排序算法。不同的排序算法具有不同的时间复杂度、空间复杂度以及稳定性等方面的不同表现。

常见的排序算法包括冒泡排序、选择排序、插入排序、希尔排序、堆排序、归并排序、快速排序等。在排序的过程中，需要注意如何处理相同元素的排序问题，以及如何设计算法来尽可能地提高排序的效率。

冒泡排序

冒泡排序是一种基础的排序算法，它的基本思路是通过比较相邻的元素，如果顺序不对则交换它们，每次循环可以把当前未排序的最大元素移动到末尾。由于该过程类似于水中气泡不断上升，因此被称为冒泡排序。冒泡排序算法的时间复杂度为O(n^2)，由于其时间复杂度高，因此在实际的应用中不太常见，但在数据量较小的情况下仍有一定用处。

冒泡排序的具体操作为：

1. 比较相邻的两个元素，如果顺序不对则交换它们；
2. 对每一对相邻元素重复执行步骤1，直到最后一对，此时未排序的最大元素会被移动到最后的位置；
3. 重复步骤1和步骤2，直到排序全部完成。

void bubble_sort(int* array, int n)
{
    int temp;

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j <n - 1 - i; j++) {
            // 前一元素比后一元素大则交换，从小到大的次序
            if (array[j] > array[j + 1]) {  
                temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
            }
        }
    }
}

选择排序

选择排序也是一种简单的排序算法，其操作步骤为：

1. 遍历待排序的数据，找到其中最小（或最大）的元素，并将其与数据的第一个元素交换位置；
2. 从数据的第二个元素开始，重复上述步骤，直到所有元素都排序完毕。

选择排序的时间复杂度同样为O(n^2)。

void select_sort(int* array, int n)
{
    int temp;

    for (int i = 0; i < n - 1; i++) {
        int index = i;
        for (int j = i + 1; j < n; j++) {
            if (array[j] < array[index])
                index = j;
        }
        if (index != i) {
            temp = array[i];
            array[i] = array[index];
            array[index] = temp;
        }
    }
}

插入排序

插入排序是一种简单的排序算法，它的原理是将一个元素插入到已排序的序列中，保持已排序序列仍然有序。

插入排序的步骤为：

1. 认为第一个元素已排序；
2. 取出下一个元素，在已排序的元素序列中从后向前扫描，若已排序的元素大于取出的元素，将已排序元素依次向后移动一个位置，直到已排序元素小于等于取出的元素，否则保持该元素位置不变；
3. 重复步骤2，直到所有元素都排序完毕。

选择排序的时间复杂度同样为O(n^2)。同时，插入排序是一种原地排序算法，不需要额外的存储空间。

void insert_sort(int* array, int n)
{
    int element;

    for (int i = 0; i < n - 1; i++) {
        element = array[i + 1];  // element to sort
        int j = i;
        while ((j >= 0) && array[j] > element) {
            array[j + 1] = array[j];
            j--;
        }
        // compensate the j-- operation
        array[j + 1] = element;
    }

    return;
}

希尔排序

希尔排序（Shell Sort）是插入排序的一种高效的改进版本，由Donald Shell在1959年提出，是第一个突破O(n^2)复杂度的排序算法。

希尔排序的基本思想是，先将待排序的数组按照一定的间隔分成若干个子序列，对每个子序列分别进行插入排序；然后缩小间隔，再对每个子序列进行插入排序，直到间隔为1时，最后进行一次插入排序即可完成排序。

希尔排序的时间复杂度为O(nlog n)或O(n^(3/2))，取决于间隔序列的选择。一般情况下，希尔排序的性能比插入排序要好，但比快速排序和归并排序差。

void shell_sort(int* array, int n)
{
    int gap, temp;

    for (gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            temp = array[i];
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                array[j + gap] = arr[j];
            arr[j + gap] = temp;
        }
    }

    return;
}

堆排序

堆排序（Heap Sort）是一种树形选择排序，利用了堆的特性进行排序。堆是一种特殊的树形数据结构，其满足以下两个条件：

1. 是一个完全二叉树；
2. 二叉树中的每个结点值都大于等于（小于等于）其子结点的值。

堆排序的基本思想是，先将待排序的数组构建为一个堆，然后将栈顶元素（最大值或最小值）与堆底元素交换，然后对除堆底元素外的部分重新构建为堆，重复上述步骤，直到数组排序完成。

堆排序的时间复杂度为O(nlog n)，不过由于其常数较大，因此实际应用中的性能较低。此外，堆排序还是一种不稳定的排序算法，因为交换堆顶元素和堆底元素的操作可能会改变相同元素的相对顺序。

归并排序

归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成若干个子数组，对每个子数组进行排序，最后将排好的子数组合并起来，得到完整的排序数组。

归并排序的基本思路如下：

1. 将待排序的数组分成若干个子数组，每个子数组的长度为1；
2. 对每个子数组进行排序，如果子数组的长度为1，则子数组已经有序；否则将其分为两个长度相等的子数组，对这两个子数组分别进行排序，直到子数组的长度为1；
3. 将排好序的子数组合并起来，即得到完整的排序数组。

归并排序的时间复杂度为O(nlog n)，其中n为待排序数组的长度。归并排序需要使用额外的空间来存储子数组，因此其空间复杂度为O(n)。

归并排序是一种稳定排序算法，因为在合并子数组的过程中，如果两个元素相等，那么会优先选择左边的元素，这样保证了算法的稳定性。

void merge(int* array, int left, int mid, int right)
{
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int left_array[n1], right_array[n2];

    // 分治思想，将原数组左右各一半的元素置入新定义的数组中
    for (i = 0; i < n1; i++)
        left_array[i] = array[left + i];
    for (j = 0; j < n2; j++)
        right_array[j] = array[mid + 1 + j];
    
    // i, j分别控制left_array[]和right_array[]数组元素的访问
    i = 0; j = 0; 
    // k控制将元素写入array[]的下标
    k = left;

    while ((i < n1) && (j < n2)) {
        if (left_array[i] <= right_array[j])
            array[k++] = left_array[i++];
        else
            array[k++] = right_array[j++];
    }

    while (i < n1)
        array[k++] = left_array[i++];

    while (j < n2)
        array[k++] = right_array[j++];

    return;
}

void merge_sort(int* array, int left, int right)
{
    if (left < right) {
        int mid = (left + right) / 2;
        merge_sort(array, left, mid);
        merge_sort(array, mid + 1, right);
        merge(array, left, mid, right);
    }

    return;
}

快速排序

快速排序（Quick Sort）是一种基于分治思想的高效排序算法，它将待排序的数组分成两部分，其中一部分的元素比另一部分的元素小，然后对这两部分元素分别进行快速排序，直到整个数组有序。

快速排序的基本思想如下：

1. 选择数组中任意一个元素为枢轴（pivot），一般选择第一个或最后一个元素；
2. 将小于枢轴的所有元素移到数组左侧，大于枢轴的所有元素移到数组右侧，该过程也成为partition操作；
3. 对左右两个子数组分别进行快速排序，直到左右两个子数组都有序。

快速排序的核心在于partition操作，其实现思路是通过维护两个指针，一个从数组头部开始遍历，一个从数组尾部开始遍历，交换指针所指向的元素，直到两个指针相遇。在这个过程中，如果发现有元素小于枢轴，就将其交换至数组左侧，反之将其交换至数组右侧。最终将枢轴元素交换到中间位置，完成partition操作。

快速排序的时间复杂度为O(nlog n)，其中n为待排序数组的长度，但最坏情况下的时间复杂度为O(n^2)。快速排序是一种不稳定的排序算法。

void quick_sort(int* array, int left, int right)
{
    // return condition
    if (left >= right)
        return;

    int i = left, j = right;
    // select the first element in array as pivot
    int pivot = array[left], temp;  
    
    while (i < j) {
        // 从数组最右侧开始，找比枢轴小的数，并将其与枢轴交换
        while ((i < j) && (array[j] >= pivot))
            j--;
        temp = array[j];
        array[j] = array[i];
        array[i] = temp;
        // 从数组的最左侧开始，找比枢轴大的数，并将其与枢轴交换
        while ((i < j) && (array[i] <= pivot))
            i++;
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    quick_sort(array, left, i - 1);
    quick_sort(array, i + 1, right);

    return;
}