C_数据结构

C_常用数据结构

最常用的数据结构有：数组，链表，栈，队列，哈希表和二叉搜索树等。网站推荐 数据结构与算法可视化

链表

链表是一种动态数据结构，由一系列节点组成，与数组不同，链表中的元素在内存中不需要是连续的，通过指针将元素串联起来。链表的主要特性是其动态性，即可以方便地进行插入和删除操作，而无需像数组需要移动元素。

链表

链表有多种类型：单链表（Singly Linked List），双向链表（Doubly Linked List），以及循环链表（Circular Linked List）等。

链表分类

循环链表用的一般比较少，但是当处理的数据具有环形结构时，就特别适合用循环链表（约瑟夫环问题）。

单链表

数据结构

每个节点包含数据部分和指向下一个节点的指针。

1
2
3
4
5
6
7
8
// 定义链表节点结构
struct Node {
    int data;           // 数据域
    struct Node* next;  // 指针域，指向下一个节点
};

// 初始化链表头指针为 NULL
struct Node* head = NULL;

基本操作

  1. 节点插入（头插法）：

    1
    2
    3
    4
    5
    6
    7
    void insertAtHead(int data) {
        // 创建新节点
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = data;
        newNode->next = head;
        head = newNode;  // 更新头指针
    }

  2. 节点插入（尾插法）：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void insertAtTail(int data) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = data;
        newNode->next = NULL;
        
        if (head == NULL) {  // 链表为空
            head = newNode;
        } else {
            struct Node* temp = head;
            while (temp->next != NULL) {
                temp = temp->next;
            }
            temp->next = newNode;
        }
    }

  3. 节点删除（按值删除）：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    void deleteNode(int key) {
        struct Node* temp = head;
        struct Node* prev = NULL;

        // 当头节点就是要删除的节点
        if (temp != NULL && temp->data == key) {
            head = temp->next;
            free(temp);
            return;
        }

        // 搜索要删除的节点
        while (temp != NULL && temp->data != key) {
            prev = temp;
            temp = temp->next;
        }

        if (temp == NULL) return;  // 未找到

        prev->next = temp->next;
        free(temp);
    }

  4. 节点查找：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    struct Node* search(int key) {
        struct Node* temp = head;
        while (temp != NULL) {
            if (temp->data == key) {
                return temp;
            }
            temp = temp->next;
        }
        return NULL;  // 未找到
    }

  5. 链表反转：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void reverseList() {
        struct Node* prev = NULL;
        struct Node* current = head;
        struct Node* next = NULL;

        while (current != NULL) {
            next = current->next;
            current->next = prev;
            prev = current;
            current = next;
        }
        head = prev;
    }

  6. 链表遍历：

    1
    2
    3
    4
    5
    6
    7
    8
    void printList() {
        struct Node* temp = head;
        while (temp != NULL) {
            printf("%d -> ", temp->data);
            temp = temp->next;
        }
        printf("NULL\n");
    }

性能分析

时间复杂度：

  • 插入：在链表头插入节点的时间复杂度为 O(1)；在链表尾插入节点的时间复杂度为 O(n)。
  • 删除：删除节点的时间复杂度为 O(n)。
  • 查找：查找节点的时间复杂度为 O(n)。
  • 反转：链表反转的时间复杂度为 O(n)。

空间复杂度：

  • 链表节点的空间复杂度为 O(n)，其中 n 为节点数量。每个节点的额外空间开销是一个指针的大小。

应用场景

链表适用于以下场景：

  • 需要频繁插入、删除操作，尤其是在链表开头或结尾（如队列和栈的实现）。
  • 需要动态分配内存且不需要连续的内存块时。
  • 数据量不大，且对随机访问要求不高的情况下。

链表不适合用于随机访问，访问链表中的任意节点需要遍历整个链表，时间复杂度为 O(n)，不如数组的 O(1) 高效。

双向链表

双向链表是一种链表数据结构，与单链表不同，双向链表允许在两个方向上遍历节点，从而提高了某些操作的效率。双向链表的主要优点是可以更方便地进行前后节点的访问、插入和删除操作。

数据结构

每个节点包含三个部分：存储数据的区域、指向下一个节点的指针和指向前一个节点的指针。

1
2
3
4
5
6
7
8
9
// 定义双向链表节点
struct Node {
    int data;           // 存储数据
    struct Node* next;  // 指向下一个节点的指针
    struct Node* prev;  // 指向前一个节点的指针
};

// 定义链表头节点
struct Node* head = NULL;

基本操作

  1. 初始化链表

    创建一个空的双向链表：

    1
    2
    3
    void initialize() {
        head = NULL;
    }

  2. 节点插入（头插法）：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void insertAtBeginning(int newData) {
        struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
        newNode->data = newData;
        newNode->next = head;
        newNode->prev = NULL;

        if (head != NULL) {
            head->prev = newNode;
        }
        
        head = newNode;
    }

  3. 节点插入（尾插法）：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    void insertAtEnd(int newData) {
        struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
        newNode->data = newData;
        newNode->next = NULL;

        if (head == NULL) {
            newNode->prev = NULL;
            head = newNode;
            return;
        }

        struct Node* temp = head;
        while (temp->next != NULL) {
            temp = temp->next;
        }

        temp->next = newNode;
        newNode->prev = temp;
    }

  4. 节点删除（按值删除）：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    void deleteNode(int key) {
        struct Node* temp = head;

        // 找到要删除的节点
        while (temp != NULL && temp->data != key) {
            temp = temp->next;
        }

        if (temp == NULL) return; // 节点未找到

        if (temp->prev != NULL) {
            temp->prev->next = temp->next;
        } else {
            head = temp->next; // 删除的是头节点
        }

        if (temp->next != NULL) {
            temp->next->prev = temp->prev;
        }

        free(temp);
    }

  5. 节点查找：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    int search(int key) {
        struct Node* temp = head;
        while (temp != NULL) {
            if (temp->data == key)
                return 1;
            temp = temp->next;
        }
        return 0;
    }

  6. 链表遍历：

    1
    2
    3
    4
    5
    6
    7
    8
    void printList() {
        struct Node* temp = head;
        while (temp != NULL) {
            printf("%d -> ", temp->data);
            temp = temp->next;
        }
        printf("NULL\n");
    }

性能分析

时间复杂度：

  • 插入：在链表头插入节点的时间复杂度为 O(1)；在链表尾插入节点的时间复杂度为 O(1)。
  • 删除：删除节点的时间复杂度为 O(n)。
  • 查找：查找节点的时间复杂度为 O(n)。
  • 遍历：正向/反向遍历链表的时间复杂度为 O(n)。

空间复杂度：

  • 双向链表的空间复杂度为O(n)，其中n是节点数量。相较于单链表，双向链表由于每个节点多一个指针（prev），占用的空间略多。

总结：虽然双向链表更占内存空间，但是它某些操作的性能是优于单链表的。这是空间换时间的思想。

应用场景

双向链表适用于以下场景：

  • 当需要在两端频繁插入或删除节点时，双向链表比单链表更高效。
  • 当需要从任意位置（尤其是中间节点）进行删除操作时，双向链表更合适，可以直接访问前一个节点。
  • 适用于需要在两个方向上遍历数据的场景，如实现浏览器的前进/后退功能。

不适合用于需要频繁访问任意元素的场景，链表的随机访问时间复杂度较高（O(n)）。

栈

栈（Stack）是一种后进先出（LIFO, Last In First Out）的数据结构。特点是只能在一端（栈顶）进行数据的插入和删除操作。栈通常用作函数调用的管理、表达式求值、括号匹配等。

栈

数据结构

栈可以使用数组或链表来实现

1
2
3
4
5
6
#define MAX_SIZE 100  // 栈的最大容量

typedef struct Stack {
    int data[MAX_SIZE];  // 栈的存储空间
    int top;             // 栈顶指针
} Stack;

基本操作

  1. 初始化栈：将栈顶指针top初始化为-1，表示栈为空。

    1
    2
    3
    void initStack(Stack *s) {
        s->top = -1;
    }

  2. 压栈：在栈未满的情况下，将元素压入栈顶。

    1
    2
    3
    4
    5
    void push(Stack *s, int value) {
        if (!isFull(s)) {
            s->data[++(s->top)] = value;
        }
    }

  3. 弹栈：在栈不为空的情况下，从栈顶弹出元素。

    1
    2
    3
    4
    5
    6
    int pop(Stack *s) {
        if (!isEmpty(s)) {
            return s->data[(s->top)--];
        }
        return -1; // 栈为空时返回-1
    }

  4. 获取栈顶元素：获取栈顶元素但不弹出。

    1
    2
    3
    4
    5
    6
    int peek(Stack *s) {
        if (!isEmpty(s)) {
            return s->data[s->top];
        }
        return -1; // 栈为空时返回-1
    }

  5. 判断栈是否为空：判断栈顶指针是否为-1。

    1
    2
    3
    int isEmpty(Stack *s) {
        return s->top == -1;
    }

  6. 判断栈是否已满：判断栈顶指针是否等于数组的最大索引。

    1
    2
    3
    int isFull(Stack *s) {
        return s->top == 99; // 数组大小为100
    }

性能分析

时间复杂度：

  • Push：O(1) —— 插入元素只需要更新栈顶指针并赋值。
  • Pop：O(1) —— 弹出元素只需要读取栈顶指针位置的值并更新指针。
  • Top：O(1) —— 获取栈顶元素只需访问数组中栈顶指针位置的值。

空间复杂度：

  • 空间复杂度为 O(n)，其中 n 是栈的容量。栈的空间由数组固定分配。

应用场景

栈在许多算法中有着广泛的应用，主要包括但不限于以下几个方面：

  • 函数调用管理：递归函数调用时，系统使用栈来保存和恢复函数的上下文信息。
  • 表达式求值：在中缀表达式转后缀表达式或计算后缀表达式时广泛使用栈。
  • 括号匹配：检查代码中括号的匹配情况。
  • 深度优先搜索（DFS）：在图的深度优先搜索算法中，栈用于存储路径信息。

队列

队列是一种特殊的线性数据结构，遵循 FIFO（First In First Out） 原则，即最先进入队列的元素最先被移出。队列通常用于需要按顺序处理数据的场景，比如任务调度、广度优先搜索等。

队列

数据结构

队列可以由队列节点结构和队列结构实现：

1
2
3
4
5
6
7
8
9
10
11
// 定义队列节点结构
typedef struct Node {
    int data;              // 数据域
    struct Node* next;     // 指向下一个节点的指针
} Node;

// 定义队列结构
typedef struct Queue {
    Node* front;           // 队列头
    Node* rear;            // 队列尾
} Queue;

基本操作

  1. 初始化队列：

    1
    2
    3
    void initQueue(Queue* q) {
        q->front = q->rear = NULL;
    }

  2. 入队操作（Enqueue）：

    将一个元素添加到队列的末尾。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void enqueue(Queue* q, int value) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = value;
        newNode->next = NULL;

        if (q->rear == NULL) {    // 队列为空时
            q->front = q->rear = newNode;
        } else {
            q->rear->next = newNode;
            q->rear = newNode;
        }
    }

  3. 出队操作（Dequeue）：

    从队列的头部移除并返回一个元素。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    int dequeue(Queue* q) {
        if (q->front == NULL) {   // 队列为空时
            return -1;            // 表示队列为空
        }

        Node* temp = q->front;
        int value = temp->data;
        q->front = q->front->next;

        if (q->front == NULL) {   // 队列为空时
            q->rear = NULL;
        }

        free(temp);
        return value;
    }

  4. 查看队列头部元素（Peek）：

    获取队列头部的元素，但不移除它。

    1
    2
    3
    4
    5
    6
    int peek(Queue* q) {
        if (q->front == NULL) {
            return -1;  // 队列为空
        }
        return q->front->data;
    }

  5. 检查队列是否为空（IsEmpty）：

    判断队列是否为空。

    1
    2
    3
    int isEmpty(Queue* q) {
        return q->front == NULL;
    }

性能分析

时间复杂度

  • 入队（Enqueue）: O(1)，因为每次操作都只涉及队列尾部。
  • 出队（Dequeue）: O(1)，因为每次操作都只涉及队列头部。
  • 查看队列头部（Peek）: O(1)，只需读取头部元素。
  • 检查是否为空（IsEmpty）: O(1)，只需检查指针是否为空。

空间复杂度

  • 空间复杂度为 O(n)，其中 n 是队列中元素的数量。每个节点占用固定大小的内存。

应用场景

  1. 任务调度: 例如操作系统中的进程调度，保证任务按到达顺序依次处理。
  2. 广度优先搜索(BFS): 在图的遍历中使用队列来按层次访问节点。
  3. 缓冲区管理: 处理数据流时，使用队列作为缓冲区，保证数据按顺序被处理。
  4. 消息队列: 在分布式系统中，队列用来缓存和传递消息。

哈希表

哈希表（Hash Table）是一种用于快速查找的常用数据结构。通过哈希函数（Hash Function）将键（Key）映射到存储位置，从而实现对数据的高效查找、插入和删除。哈希表的核心思想是利用数组的快速访问特点，将键值映射为数组的下标，进行查找、插入和删除操作的时间复杂度可以接近O(1)。

哈希表

数据结构

哈希函数

哈希函数是将键转换为数组索引的函数，设计一个好的哈希函数可以减少冲突。常见的哈希函数有取模法、乘法散列法等。

1
2
3
unsigned int hash_function(int key, int table_size) {
    return key % table_size;  // 取模法
}

冲突解决

由于哈希表的有限大小，不同的键值可能映射到相同的数组索引位置，这种现象称为冲突（Collision）。常见的冲突解决方法有开放地址法和链地址法。

  1. 开放地址法（Open Addressing）: 冲突时寻找下一个空闲的数组位置。
  2. 链地址法（Chaining）: 使用链表将所有冲突的键值存储在同一个数组位置。

定义链表节点

1
2
3
4
5
6
7
#define TABLE_SIZE 10
// 定义链表节点
typedef struct Node {
    int key;
    int value;
    struct Node* next;
} Node;

定义哈希表

1
2
3
typedef struct {
    Node* buckets[TABLE_SIZE];
} HashTable;

基本操作

  1. 初始化哈希表：

    1
    2
    3
    4
    5
    void init_hash_table(HashTable* table) {
        for (int i = 0; i < TABLE_SIZE; i++) {
            table->buckets[i] = NULL;
        }
    }

  2. 插入键值对：

    1
    2
    3
    4
    5
    6
    7
    8
    void insert(HashTable* table, int key, int value) {
        unsigned int index = hash_function(key, TABLE_SIZE);
        Node* new_node = (Node*)malloc(sizeof(Node));
        new_node->key = key;
        new_node->value = value;
        new_node->next = table->buckets[index];
        table->buckets[index] = new_node;
    }

  3. 查找键对应的值：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int search(HashTable* table, int key) {
        unsigned int index = hash_function(key, TABLE_SIZE);
        Node* node = table->buckets[index];
        while (node != NULL) {
            if (node->key == key) {
                return node->value;
            }
            node = node->next;
        }
        return -1; // 表示未找到
    }

  4. 删除键值对：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    void delete(HashTable* table, int key) {
        unsigned int index = hash_function(key, TABLE_SIZE);
        Node* node = table->buckets[index];
        Node* prev = NULL;
        while (node != NULL && node->key != key) {
            prev = node;
            node = node->next;
        }
        if (node != NULL) {
            if (prev == NULL) {
                table->buckets[index] = node->next;
            } else {
                prev->next = node->next;
            }
            free(node);
        }
    }

性能分析

时间复杂度：

  • 插入：平均情况下 O(1)，最坏情况下 O(n)（所有元素哈希冲突在同一个桶内）。
  • 查找：平均情况下 O(1)，最坏情况下 O(n)。
  • 删除：平均情况下 O(1)，最坏情况下 O(n)。

空间复杂度：O(n) 用于存储所有元素，外加 O(m) 用于存储桶数组（其中 m 是桶的数量）。

应用场景

哈希表适用于以下场景：

  • 快速查找/插入/删除：需要在常数时间内快速查找数据、频繁插入和删除元素，哈希表提供高效的 O(1) 操作。如字典、缓存。
  • 唯一性检查：用于快速判断一个元素是否存在，如检测重复元素。
  • 计数器：如统计字符频率、单词频率等。
  • 集合操作：哈希表可以用于集合操作，如求交集、并集、差集等。

不适用于：

  • 需要维持数据有序的场合，哈希表无法保持元素的顺序。
  • 空间有限且哈希表装载因子较高时，冲突增多可能导致性能下降。

哈希表在需要高效键值对操作的场景中表现尤为出色，但需要注意选择合适的哈希函数以及处理冲突的方法，以避免性能退化。

二叉树

二叉树是一种树形数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树通常用于组织数据以实现快速的查找、插入和删除操作。

二叉树

  • 满二叉树：每一层的结点数目都达到最大值
  • 完全二叉树：一个二叉树除了最后一层，其他层都是满的，且最后一层的节点连续排列在最左边。

满or完全二叉树

(a)满二叉树；(b)完全二叉树；(c)和(d)非完全二叉树

二叉树具有以下性质：

  • 高度为 h 的二叉树最多有 2^h - 1 个节点。
  • 对于 n 个节点的完全二叉树，其高度 h 为 log2(n+1)。

二叉搜索树

二叉搜索树（二叉排序树）是一种特殊的二叉树，其中每个节点都遵循以下规则：

  • 左子树中所有节点的值都小于根节点的值。
  • 右子树中所有节点的值都大于根节点的值。
  • 每个节点的左右子树也都是二叉搜索树。

二叉搜索树在搜索、插入和删除操作时具有较好的性能。

数据结构

二叉搜索树节点的基本结构：

1
2
3
4
5
6
// 二叉搜索树节点结构
struct TreeNode {
    int val;                // 节点的值
    struct TreeNode* left;  // 指向左子树的指针
    struct TreeNode* right; // 指向右子树的指针
};

基本操作

  1. 创建新的二叉搜索树节点：

    1
    2
    3
    4
    5
    6
    7
    struct TreeNode* createNode(int val) {
        struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        newNode->val = val;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }

  2. 插入节点：

    插入节点时，从根节点开始，根据值的大小递归地找到适当的空位置插入新节点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    struct TreeNode* insertNode(struct TreeNode* root, int val) {
        // 如果树为空，则创建一个新节点
        if (root == NULL) {
            return createNode(val);
        }
        // 递归地插入到左子树或右子树
        if (val < root->val) {
            root->left = insertNode(root->left, val);
        } else if (val > root->val) {
            root->right = insertNode(root->right, val);
        }
        // 返回（未变更的）节点指针
        return root;
    }

  3. 搜索节点：

    搜索时，根据当前节点的值和目标值的比较结果决定向左子树或右子树递归。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    struct TreeNode* searchNode(struct TreeNode* root, int val) {
        // 如果找不到或者找到匹配的节点，则返回
        if (root == NULL || root->val == val) {
            return root;
        }
        // 如果目标值小于当前节点的值，继续在左子树中搜索
        if (val < root->val) {
            return searchNode(root->left, val);
        }
        // 否则继续在右子树中搜索
        return searchNode(root->right, val);
    }

  4. 删除节点：

    删除节点分为三种情况：

    • 要删除的节点是叶子节点（无子树）。
    • 要删除的节点有一个子树。
    • 要删除的节点有两个子树：此时需找到右子树中的最小节点（或左子树中的最大节点）代替被删除的节点。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    struct TreeNode* findMinNode(struct TreeNode* node) {
        struct TreeNode* current = node;
        while (current && current->left != NULL) {
            current = current->left;
        }
        return current;
    }

    struct TreeNode* deleteNode(struct TreeNode* root, int val) {
        // 基本情况
        if (root == NULL) {
            return root;
        }
        // 递归找到要删除的节点
        if (val < root->val) {
            root->left = deleteNode(root->left, val);
        } else if (val > root->val) {
            root->right = deleteNode(root->right, val);
        } else {
            // 找到要删除的节点
            // 情况1：节点没有子节点（叶子节点）
            if (root->left == NULL && root->right == NULL) {
                free(root);
                return NULL;
            }
            // 情况2：节点有一个子节点
            else if (root->left == NULL) {
                struct TreeNode* temp = root->right;
                free(root);
                return temp;
            } else if (root->right == NULL) {
                struct TreeNode* temp = root->left;
                free(root);
                return temp;
            }
            // 情况3：节点有两个子节点
            struct TreeNode* temp = findMinNode(root->right);
            root->val = temp->val;
            root->right = deleteNode(root->right, temp->val);
        }
        return root;
    }

  5. 中序遍历（获取有序元素）：

    二叉搜索树的中序遍历可以获得有序的节点序列。

    1
    2
    3
    4
    5
    6
    7
    void inorderTraversal(struct TreeNode* root) {
        if (root != NULL) {
            inorderTraversal(root->left);
            printf("%d ", root->val);
            inorderTraversal(root->right);
        }
    }

性能分析

时间复杂度:

  • 查找: 平均情况下为O(log n)，最坏情况下为O(n)（当树退化为链表时）。
  • 插入: 平均情况下为O(log n)，最坏情况下为O(n)。
  • 删除: 平均情况下为O(log n)，最坏情况下为O(n)。
  • 遍历: O(n)，需要访问每个节点一次。

空间复杂度:

  • 对于n个节点的二叉搜索树，空间复杂度为O(n)，需要存储n个节点。

应用场景

二叉搜索树适用于以下场景：

  • 动态数据集合：需要频繁插入、删除和查找操作的应用。
  • 有序数据输出：需要频繁获取有序数据的应用。需要快速查找、中序遍历或范围查询的场景。
  • 字典、集合实现：基于键值对操作的数据结构，比如实现符号表。

二叉搜索树适用于需要动态管理有序数据的场景，但需注意在最坏情况下，树的性能会退化到线性时间复杂度。为了保持平衡，可以考虑使用自平衡二叉搜索树（如红黑树或AVL树）来确保更好的性能。

堆

堆（Heap）是一种特殊的二叉树，它可以分为最大堆和最小堆。

  • 完全二叉树：除了最后一层外，所有层的节点都被填满，最后一层的节点从左到右依次填充。

  • 最大堆：在最大堆中，每个父节点的值都大于或等于其子节点的值。

  • 最小堆：在最小堆中，每个父节点的值都小于或等于其子节点的值。

堆通常用数组来实现，而非实际的二叉树。假设节点的索引为i，则有以下关系：

  • 父节点索引为 (i - 1) / 2
  • 左子节点索引为 2 * i + 1
  • 右子节点索引为 2 * i + 2

数据结构

下面是一个简单的堆实现（以最大堆为例）:

1
2
3
4
5
#define MAX_SIZE 100
typedef struct {
    int data[MAX_SIZE];  // 用数组表示堆
    int size;            // 当前堆的大小
} Heap;

基本操作

  1. 初始化堆：

    1
    2
    3
    void initHeap(Heap *h) {
        h->size = 0;
    }

  2. 插入操作：

    插入新元素到堆中，并维护堆的性质。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void insert(Heap *h, int value) {
        if (h->size >= MAX_SIZE) return;  // 堆满
        int i = h->size++;
        h->data[i] = value;
        
        // 向上调整
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (h->data[i] <= h->data[parent]) break;
            int temp = h->data[i];
            h->data[i] = h->data[parent];
            h->data[parent] = temp;
            i = parent;
        }
    }

  3. 删除操作（删除根节点）：

    删除堆顶元素，并维护堆的性质。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    int deleteMax(Heap *h) {
        if (h->size == 0) return -1;  // 堆为空
        
        int max = h->data[0];
        h->data[0] = h->data[--h->size];
        
        // 向下调整
        int i = 0;
        while (2 * i + 1 < h->size) {
            int leftChild = 2 * i + 1;
            int rightChild = 2 * i + 2;
            int largest = i;
            
            if (leftChild < h->size && h->data[leftChild] > h->data[largest]) {
                largest = leftChild;
            }
            if (rightChild < h->size && h->data[rightChild] > h->data[largest]) {
                largest = rightChild;
            }
            
            if (largest == i) break;
            
            int temp = h->data[i];
            h->data[i] = h->data[largest];
            h->data[largest] = temp;
            i = largest;
        }
        
        return max;
    }

  4. 获取堆顶元素：

    获取堆中最大值（最大堆）或最小值（最小堆），时间复杂度为 O(1)。

    1
    2
    3
    4
    int getMax(Heap *h) {
        if (h->size == 0) return -1;  // 堆为空
        return h->data[0];
    }

  5. 堆化（Heapify）：

    将一个无序数组调整为堆，常用于构建堆排序。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    void heapify(Heap *h, int i) {
        int leftChild = 2 * i + 1;
        int rightChild = 2 * i + 2;
        int largest = i;

        if (leftChild < h->size && h->data[leftChild] > h->data[largest]) {
            largest = leftChild;
        }
        if (rightChild < h->size && h->data[rightChild] > h->data[largest]) {
            largest = rightChild;
        }
        
        if (largest != i) {
            int temp = h->data[i];
            h->data[i] = h->data[largest];
            h->data[largest] = temp;
            heapify(h, largest);
        }
    }

性能分析

  • 插入操作：时间复杂度为 O(log⁡n)，因为插入元素后，最多需要沿着树向上调整 log⁡n 次。

  • 删除操作：时间复杂度为 O(log⁡n)，因为删除根节点后，最多需要沿着树向下调整 log⁡n 次。

  • 获取堆顶元素：时间复杂度为 O(1)，因为只需返回根节点的值。

  • 堆化操作：时间复杂度为 O(n)，通常用于构建堆。

  • 空间复杂度：堆通常使用数组实现，空间复杂度为 O(n)，其中 n 为堆中元素个数。

应用场景

堆适用于以下场景：

  • 优先队列：堆广泛用于实现优先队列，能够以较高效率找到和移除优先级最高的元素。

  • 排序算法：堆排序是经典的O(nlogn)排序算法，适用于大数据量的排序任务。

  • 图算法：堆在Dijkstra算法和Prim算法中用于高效地选择最短路径或最小生成树中的下一条边。

  • 任务调度：处理多个任务时，堆可以用来调度优先级较高的任务。

平衡树

平衡树是一种自动调整的数据结构，保证在进行插入、删除、查找等操作时，树的高度始终保持平衡（或接近平衡）。通常平衡树的定义是为了防止树变成一条长链，会导致操作效率下降到 O(n)（线性时间）。在平衡树中，操作的时间复杂度能够保持在 O(log n)，确保高效的查找、插入和删除操作。

常见的平衡树包括 AVL 树、红黑树等。下面的例子将以 AVL树 为例，该树的特性是：每个节点的左右子树的高度差不超过 1。

数据结构

AVL 树作为一种平衡二叉搜索树，能够有效地保证操作的时间复杂度在 O(log n) 范围内，适用于对查找、插入、删除操作都有较高要求的应用场景。 AVL 树的基本数据结构：

1
2
3
4
5
6
 struct AVLNode {
    int key;  // 节点值
    int height;  // 节点的高度
    struct AVLNode* left;  // 左子树
    struct AVLNode* right;  // 右子树
};

基本操作

  1. 获取节点高度：

    1
    2
    3
    4
    5
    int height(struct AVLNode* node) {
        if (node == NULL)
            return 0;
        return node->height;
    }

  2. 创建新节点：

    1
    2
    3
    4
    5
    6
    7
    struct AVLNode* createNode(int key) {
        struct AVLNode* node = (struct AVLNode*)malloc(sizeof(struct AVLNode));
        node->key = key;
        node->left = node->right = NULL;
        node->height = 1;  // 新节点的高度为1
        return node;
    }

  3. 右旋操作：

    右旋是指将某个节点及其左子树向右旋转，调整树的平衡。该操作用于在插入或删除节点后，树变得左重时恢复平衡。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    struct AVLNode* rightRotate(struct AVLNode* y) {
        struct AVLNode* x = y->left;
        struct AVLNode* T2 = x->right;
        // 进行旋转
        x->right = y;
        y->left = T2;
        // 更新高度
        y->height = max(height(y->left), height(y->right)) + 1;
        x->height = max(height(x->left), height(x->right)) + 1;
        // 返回新的根节点
        return x;
    }

  4. 左旋操作：

    左旋是指将某个节点及其右子树向左旋转，调整树的平衡。该操作用于在插入或删除节点后，树变得右重时恢复平衡。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    struct AVLNode* leftRotate(struct AVLNode* x) {
        struct AVLNode* y = x->right;
        struct AVLNode* T2 = y->left;
        // 进行旋转
        y->left = x;
        x->right = T2;
        // 更新高度
        x->height = max(height(x->left), height(x->right)) + 1;
        y->height = max(height(y->left), height(y->right)) + 1;
        // 返回新的根节点
        return y;
    }

  5. 获取平衡因子：

    AVL 树的核心在于维护每个节点的平衡因子，平衡因子等于左右子树高度差。如果平衡因子的绝对值大于 1，则该节点需要旋转以保持平衡。

    1
    2
    3
    4
    5
    int getBalance(struct AVLNode* node) {
        if (node == NULL)
            return 0;
        return height(node->left) - height(node->right);
    }

  6. 插入节点：

    在 AVL 树中插入节点后，可能会破坏树的平衡，此时需要通过旋转来恢复平衡。插入时，需要判断四种情况：左左、右右、左右、右左，并选择相应的旋转操作。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    struct AVLNode* insert(struct AVLNode* node, int key) {
        // 标准的二叉搜索树插入
        if (node == NULL)
            return createNode(key);
        if (key < node->key)
            node->left = insert(node->left, key);
        else if (key > node->key)
            node->right = insert(node->right, key);
        else
            return node; // 键值已存在，返回不做插入
        // 更新节点高度
        node->height = 1 + max(height(node->left), height(node->right));
        // 获取当前节点的平衡因子
        int balance = getBalance(node);
        // 如果节点不平衡，进行相应旋转
        // 左左情况
        if (balance > 1 && key < node->left->key)
            return rightRotate(node);
        // 右右情况
        if (balance < -1 && key > node->right->key)
            return leftRotate(node);
        // 左右情况
        if (balance > 1 && key > node->left->key) {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }
        // 右左情况
        if (balance < -1 && key < node->right->key) {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }
        return node;
    }

  7. 查找节点：

    查找节点与标准的二叉搜索树相同。

    1
    2
    3
    4
    5
    6
    7
    struct AVLNode* search(struct AVLNode* root, int key) {
        if (root == NULL || root->key == key)
            return root;
        if (key < root->key)
            return search(root->left, key);
        return search(root->right, key);
    }

  8. 删除节点：

    删除节点后也可能破坏树的平衡，因此同样需要进行平衡因子的检查与旋转操作。删除的核心与标准二叉搜索树类似，之后根据不同的情况调整平衡。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    // 找到最小值节点
    struct AVLNode* minValueNode(struct AVLNode* node) {
        struct AVLNode* current = node;
        // 找到最左边的叶子节点
        while (current->left != NULL)
            current = current->left;
        return current;
    }

    // 删除节点并维持平衡
    struct AVLNode* deleteNode(struct AVLNode* root, int key) {
        // 标准二叉搜索树删除
        if (root == NULL)
            return root;
        if (key < root->key)
            root->left = deleteNode(root->left, key);
        else if (key > root->key)
            root->right = deleteNode(root->right, key);
        else {
            // 单子节点或无子节点
            if ((root->left == NULL) || (root->right == NULL)) {
                struct AVLNode* temp = root->left ? root->left : root->right;
                if (temp == NULL) {
                    temp = root;
                    root = NULL;
                } else
                    *root = *temp;
                free(temp);
            } else {
                // 找到右子树的最小节点
                struct AVLNode* temp = minValueNode(root->right);
                root->key = temp->key;
                root->right = deleteNode(root->right, temp->key);
            }
        }
        if (root == NULL)
            return root;
        // 更新节点高度
        root->height = 1 + max(height(root->left), height(root->right));
        // 检查平衡因子
        int balance = getBalance(root);
        // 左左情况
        if (balance > 1 && getBalance(root->left) >= 0)
            return rightRotate(root);
        // 左右情况
        if (balance > 1 && getBalance(root->left) < 0) {
            root->left = leftRotate(root->left);
            return rightRotate(root);
        }
        // 右右情况
        if (balance < -1 && getBalance(root->right) <= 0)
            return leftRotate(root);
        // 右左情况
        if (balance < -1 && getBalance(root->right) > 0) {
            root->right = rightRotate(root->right);
            return leftRotate(root);
        }
        return root;
    }

性能分析

时间复杂度：

  • 插入、删除、查找操作的时间复杂度均为 O(log n)，因为 AVL 树的高度始终保持在 O(log n) 的范围内。

空间复杂度：

  • 在最坏情况下，AVL 树的额外空间复杂度为 O(n)，主要用于存储每个节点的指针以及递归栈的深度。

应用场景

  • AVL 树适用于对查找操作要求较高的场景，它能确保树的高度始终平衡，查找性能良好。

  • 在需要频繁插入和删除数据的场景下，AVL 树也能够通过旋转保持平衡，从而保证操作效率。

图

图（Graph）是一种非常重要的非线性数据结构，由顶点（Vertex）和边（Edge）组成。图用于表示对象（顶点）之间的关系（边），广泛应用于社交网络、网络路由、搜索引擎等领域。图可分为以下几类：

  • 无向图：边没有方向，边(u, v)与(v, u)等价。

  • 有向图：边有方向，边(u, v)与(v, u)不等价。

  • 加权图：边带有权重（Weight），表示两个顶点之间的距离或代价。

  • 无权图：边没有权重。

此外，图还可以表示为稀疏图（Sparse Graph）和稠密图（Dense Graph）：

  • 稀疏图：边的数量远小于顶点数的平方。
  • 稠密图：边的数量接近于顶点数的平方。

数据结构

图的数据结构可以通过邻接矩阵（Adjacency Matrix）或邻接表（Adjacency List）来实现。

  • 邻接矩阵

    邻接矩阵是一种二维数组，用于表示图中节点之间的连接关系。假设图中有 n 个节点，matrix[i][j] 表示节点 i 和节点 j 之间的连接关系。若为无向图，matrix[i][j] = matrix[j][i]。

    1
    2
    3
    4
    5
    #define MAX_VERTICES 100
    typedef struct {
        int matrix[MAX_VERTICES][MAX_VERTICES];  // 用二维数组表示图
        int numVertices;                         // 图的顶点数量
    } Graph;

    初始化图：

    1
    2
    3
    4
    5
    6
    7
    8
    void initGraph(Graph* g, int numVertices) {
        g->numVertices = numVertices;
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                g->matrix[i][j] = 0; // 初始化矩阵为0，表示没有边
            }
        }
    }

    添加边：

    1
    2
    3
    void addEdge(Graph* g, int src, int dest) {
        g->matrix[src][dest] = 1;
    }

    移除边：

    1
    2
    3
    void removeEdge(Graph* g, int src, int dest) {
        g->matrix[src][dest] = 0;
    }

  • 邻接表

    邻接表是一种链表数组，数组中的每个元素都是一个链表，用于存储与某个顶点相连的所有顶点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    #define MAX_VERTICES 100
    typedef struct Node {
        int vertex;
        struct Node* next;
    } Node;
    typedef struct {
        Node* list[MAX_VERTICES];  // 用数组存储每个顶点的邻接链表
        int numVertices;           // 图的顶点数量
    } Graph;

    初始化图：

    1
    2
    3
    4
    5
    6
    void initGraph(Graph* g, int numVertices) {
        g->numVertices = numVertices;
        for (int i = 0; i < numVertices; i++) {
            g->list[i] = NULL;  // 初始化链表为空
        }
    }

    创建节点：

    1
    2
    3
    4
    5
    6
    Node* createNode(int vertex) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->vertex = vertex;
        newNode->next = NULL;
        return newNode;
    }

    添加边：

    1
    2
    3
    4
    5
    void addEdge(Graph* g, int src, int dest) {
        Node* newNode = createNode(dest);
        newNode->next = g->list[src];
        g->list[src] = newNode;
    }

    移除边：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    void removeEdge(Graph* g, int src, int dest) {
        Node* temp = g->list[src];
        Node* prev = NULL;
        while (temp != NULL && temp->vertex != dest) {
            prev = temp;
            temp = temp->next;
        }
        if (temp != NULL) {
            if (prev != NULL) {
                prev->next = temp->next;
            } else {
                g->list[src] = temp->next;
            }
            free(temp);
        }
    }

基本操作

图的遍历常见的有两种方式：深度优先遍历（DFS）和广度优先遍历（BFS）。

  • DFS（深度优先搜索）: 使用递归实现，沿着每一个路径深入到不能再深入为止，然后回溯。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void DFS(Graph* g, int vertex, int visited[]) {
        visited[vertex] = 1; // 标记当前节点为已访问
        printf("%d ", vertex); // 访问节点

        Node* adjList = g->list[vertex];
        Node* temp = adjList;

        while (temp != NULL) {
            int connectedVertex = temp->vertex;
            if (visited[connectedVertex] == 0) {
                DFS(g, connectedVertex, visited);
            }
            temp = temp->next;
        }
    }

  • BFS（广度优先搜索）: 使用队列实现，从一个顶点开始，先访问其所有邻接顶点，然后逐层访问。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    void BFS(Graph* g, int startVertex) {
        int visited[MAX_VERTICES] = {0};
        Queue* queue = createQueue();

        visited[startVertex] = 1;
        enqueue(queue, startVertex);

        while (!isEmpty(queue)) {
            int currentVertex = dequeue(queue);
            printf("%d ", currentVertex);

            Node* temp = g->list[currentVertex];

            while (temp) {
                int adjVertex = temp->vertex;

                if (visited[adjVertex] == 0) {
                    visited[adjVertex] = 1;
                    enqueue(queue, adjVertex);
                }
                temp = temp->next;
            }
        }
    }

性能分析

邻接矩阵：

  • 时间复杂度：添加边、移除边、检查边存在性：O(1)；遍历所有邻接顶点：O(V)
  • 空间复杂度：O(V^2)，其中V是图中顶点的数量。不适合稀疏图，会浪费大量空间。

邻接表：

  • 时间复杂度：添加边：O(1)；移除边、检查边存在性、遍历所有邻接顶点：O(E/V) 平均
  • 空间复杂度：O(V + E)，其中E是图中边的数量。适合稀疏图，因为只存储实际存在的边。

对于稠密图（即边的数量接近于顶点数量的平方），建议使用邻接矩阵。对于稀疏图（即边的数量远小于顶点数量的平方），建议使用邻接表。

应用场景

  • 邻接矩阵：适用于图较小且稠密（边较多）的情况，快速检查两个顶点之间是否有边。如社交网络中的好友关系。

  • 邻接表：适用于图较大且稀疏（边较少）的情况，节省空间，适合存储大量顶点及其关系。如城市间的道路网络。

  • DFS常用于解决迷宫问题、连通性检测、拓扑排序等。

  • BFS常用于最短路径问题（如无权图的最短路径），也用于层次遍历（如树的层次遍历）。