数据结构教程（1）

数据结构教程（C语言版）

第一部分：数组 (Array)

数组是最基础、最常见的数据结构。它可以看作是一个固定大小的、存储相同类型元素的连续内存集合。

1.1 什么是数组？

想象一排电影院的座位，每个座位都有一个唯一的编号（0, 1, 2, ...），并且所有座位都是连续排列的。数组就像这样，它在内存中开辟一块连续的空间，然后将数据元素一个挨一个地存放进去。

​由于内存地址是连续的，数组最强大的特性就是可以通过索引（下标）直接访问任何一个元素。这个过程非常快，时间复杂度为 O(1)。

​#### 1.2 数组的特性

• ​连续的内存空间: 数组中的元素在内存中是紧挨着存放的。

​ * ​相同的数据类型: 一个数组只能存储同一种数据类型的元素（例如，一个 int 数组只能存放整数）。

​ * ​固定大小: 在C语言中，数组一旦被创建，其大小就是固定的，不能在运行时动态改变。

​ * ​随机访问: 可以通过索引（下标）直接计算出元素的内存地址，从而实现快速访问。第一个元素的索引是 0，最后一个元素的索引是 n-1（其中 n 是数组的大小）。

​

1.3 数组的声明和初始化

在C语言中，声明一个数组需要指定元素的类型、数组的名称和数组的大小。

codeC

// 声明一个能存储 10 个整数的数组
int numbers[10];

// 声明并初始化一个数组
// 编译器会自动根据初始化列表的元素个数来确定数组大小
char vowels[] = {'a', 'e', 'i', 'o', 'u'}; 

// 声明并初始化一个包含 5 个整数的数组
int scores[5] = {98, 77, 89, 100, 65};

// 初始化部分元素，其余元素会被自动初始化为 0
int partial[10] = {1, 2, 3}; // partial[3] 到 partial[9] 的值都是 0

1.4 数组的基本操作

1. 访问元素 (Access)

通过索引直接访问，这是数组最高效的操作。

codeC

#include <stdio.h>

int main() {
    int scores[5] = {98, 77, 89, 100, 65};

    // 访问第三个元素 (索引为 2)
    int third_score = scores[2]; // third_score 的值为 89

    printf("第三个分数是: %d\n", third_score);

    // 修改第五个元素 (索引为 4)
    scores[4] = 70;
    printf("修改后的第五个分数是: %d\n", scores[4]);

    return 0;
}

2. 遍历数组 (Traversal)

通常使用 for 循环来遍历数组中的所有元素。

codeC

#include <stdio.h>

int main() {
    int scores[5] = {98, 77, 89, 100, 65};
    int size = sizeof(scores) / sizeof(scores[0]); // 计算数组元素的个数

    printf("所有分数: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", scores[i]);
    }
    printf("\n");

    return 0;
}

3. 插入元素 (Insertion)

在数组中插入元素是一个相对低效的操作。因为数组的内存是连续的，如果要在一个中间位置（例如索引 k）插入一个新元素，那么从索引 k 开始的所有后续元素都需要向后移动一个位置，以便为新元素腾出空间。

• ​最坏情况: 在数组开头（索引 0）插入，需要移动所有 n 个元素，时间复杂度为 O(n)。

​ * ​最好情况: 在数组末尾插入（如果数组还有空间），不需要移动元素，时间复杂度为 O(1)。

​

codeC

#include <stdio.h>

void print_array(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[10] = {10, 20, 30, 40, 50}; // 数组有10个空间，但只用了5个
    int current_size = 5;
    int value_to_insert = 25;
    int insert_position = 2; // 插入到索引为 2 的位置 (30的前面)

    printf("原始数组: ");
    print_array(arr, current_size);

    // 从后向前，将元素向后移动
    for (int i = current_size - 1; i >= insert_position; i--) {
        arr[i + 1] = arr[i];
    }

    // 插入新元素
    arr[insert_position] = value_to_insert;
    current_size++; // 数组大小加一

    printf("插入后数组: ");
    print_array(arr, current_size);

    return 0;
}

4. 删除元素 (Deletion)

删除元素与插入类似，也可能需要移动大量元素。如果要删除索引 k 处的元素，那么从索引 k+1 开始的所有后续元素都需要向前移动一个位置来填补空缺。

• ​最坏情况: 删除数组开头的元素，需要移动 n-1 个元素，时间复杂度为 O(n)。

​ * ​最好情况: 删除数组末尾的元素，不需要移动元素，时间复杂度为 O(1)。

​

codeC

#include <stdio.h>

void print_array(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[10] = {10, 20, 25, 30, 40, 50};
    int current_size = 6;
    int delete_position = 3; // 删除索引为 3 的元素 (30)

    printf("原始数组: ");
    print_array(arr, current_size);

    // 从删除位置开始，将后续元素向前移动
    for (int i = delete_position; i < current_size - 1; i++) {
        arr[i] = arr[i + 1];
    }

    current_size--; // 数组大小减一

    printf("删除后数组: ");
    print_array(arr, current_size);

    return 0;
}

1.5 数组的优缺点

优点:

• ​访问速度快: 由于其随机访问的特性，通过索引访问元素非常高效（O(1)）。

​ * ​实现简单: 数组是许多编程语言内置的基本结构，易于理解和使用。

​ * ​内存连续性: 元素在内存中连续存储，这可以利用CPU缓存来提高遍历效率。

​

缺点:

• ​大小固定: 一旦创建，大小无法改变。如果需要存储更多元素，可能需要创建一个全新的、更大的数组，并将旧数组的元素复制过去，成本很高。

​ * ​插入和删除效率低: 在数组中间进行插入和删除操作需要移动大量元素，时间复杂度为 O(n)。

​ * ​空间浪费: 如果声明了一个很大的数组但只使用了其中的一小部分，会造成内存空间的浪费。

​

1.6 总结

数组是学习所有其他数据结构的基础。当你需要一个能够快速访问、大小固定且元素类型相同的集合时，数组是最佳选择。然而，在需要频繁进行插入和删除操作，或者无法预估元素数量的场景下，其他数据结构（如下一部分将要介绍的链表）可能会是更好的选择。

---

第二部分：链表 (Linked List)

​​链表是另一种非常重要的线性数据结构。与在内存中连续存储元素的数组不同，链表的元素（称为节点）在内存中是非连续存储的。每个节点除了包含数据本身，还包含一个指向下一个节点的指针。

​​#### 2.1 什么是链表？

想象一个寻宝游戏。你手里的第一张纸条告诉你宝藏的一部分信息，并指引你去下一个地点找第二张纸条。第二张纸条同样包含一部分信息，并指引你到第三个地点... 直到最后一张纸条告诉你游戏结束。

在这个比喻中：

• ​每一张纸条就是一个节点 (Node)。

​ * ​纸条上的宝藏信息就是节点存储的数据 (Data)。

​ * ​纸条上指向下一个地点的指引就是指针 (Pointer)。

​ * ​你开始寻找的第一张纸条就是链表的头节点 (Head)。

​ * ​最后一张纸条没有新的指引，这就相当于链表末尾的NULL指针。

​

通过这种方式，即使纸条（节点）散落在各个地方（内存中的不同位置），我们也能通过指针将它们有序地串联起来。

2.2 链表的节点结构

在C语言中，我们通常使用结构体（struct）来定义链表的节点。一个最简单的单向链表节点包含两部分：

• ​数据域 (Data): 用于存储该节点的数据。

​ * ​指针域 (Pointer): 用于存储下一个节点的内存地址。

​

codeC

// 定义一个链表节点
struct Node {
    int data;             // 数据域，这里以整数为例
    struct Node *next;    // 指针域，指向下一个 Node 类型的节点
};

2.3 链表的特性

• ​动态大小: 链表的大小可以在程序运行时动态地增加或减少，不需要预先分配固定大小的空间。

​ * ​非连续内存: 节点可以分散在内存的任何地方，通过指针连接。

​ * ​高效的插入和删除: 在链表的开头或中间插入/删除节点非常高效（通常是 O(1) 或 O(n) 的查找时间 + O(1) 的操作时间），因为只需要修改相邻节点的指针，而不需要像数组那样移动大量元素。

​ * ​顺序访问: 链表不支持随机访问。要访问第 i 个元素，必须从头节点开始，沿着指针逐个遍历，直到找到该元素。访问操作的时间复杂度为 O(n)。

​

2.4 链表的基本操作

我们将使用一个head指针来始终指向链表的第一个节点。如果head为NULL，则表示链表为空。

1. 遍历链表 (Traversal)

遍历是所有操作的基础。我们从head节点开始，沿着每个节点的next指针前进，直到遇到NULL为止。

codeC

#include <stdio.h>
#include <stdlib.h>

// (在此处放置上面定义的 Node 结构体)
struct Node {
    int data;
    struct Node *next;
};

// 打印链表中的所有元素
void printList(struct Node *head) {
    struct Node *current = head; // 创建一个临时指针，从头节点开始
    while (current != NULL) {
        printf("%d -> ", current->data); // 打印当前节点的数据
        current = current->next;         // 移动到下一个节点
    }
    printf("NULL\n");
}

2. 在链表头部插入节点 (Insertion at the Beginning)

这是链表最高效的插入操作，时间复杂度为 O(1)。

• 创建一个新节点。
• 让新节点的next指针指向当前的head节点。
• 将head指针更新为指向这个新节点。

codeC

// 在链表头部插入新节点
void insertAtBeginning(struct Node **head_ref, int new_data) {
    // 1. 分配新节点的内存
    struct Node *new_node = (struct Node*) malloc(sizeof(struct Node));

    // 2. 为新节点赋值
    new_node->data = new_data;

    // 3. 让新节点的 next 指向当前的 head
    new_node->next = *head_ref;

    // 4. 将 head 指向新节点
    *head_ref = new_node;
}

注意：这里我们使用了指向指针的指针 struct Node **head_ref，因为我们需要在函数内部修改原始的 head 指针。

3. 在链表尾部插入节点 (Insertion at the End)

这个操作需要先遍历到链表的最后一个节点，时间复杂度为 O(n)。

• 创建一个新节点。
• 如果链表为空，则让head指向新节点。
• 否则，遍历到最后一个节点（即next为NULL的节点）。
• 让最后一个节点的next指针指向新节点。

codeC

// 在链表尾部插入新节点
void insertAtEnd(struct Node **head_ref, int new_data) {
    // 1. 分配新节点的内存
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    struct Node *last = *head_ref; // 用于遍历的指针

    // 2. 为新节点赋值
    new_node->data = new_data;
    new_node->next = NULL; // 新节点将是最后一个，所以 next 是 NULL

    // 3. 如果链表为空，新节点就是头节点
    if (*head_ref == NULL) {
       *head_ref = new_node;
       return;
    }

    // 4. 否则，遍历到最后一个节点
    while (last->next != NULL) {
        last = last->next;
    }

    // 5. 让最后一个节点的 next 指向新节点
    last->next = new_node;
}

4. 删除节点 (Deletion by Key)

删除一个具有特定值的节点。

• 找到要删除的节点（current）以及它的前一个节点（previous）。
• 将previous节点的next指针绕过current节点，直接指向current节点的下一个节点。
• 释放current节点的内存。

codeC

// 根据 key 删除节点
void deleteNode(struct Node **head_ref, int key) {
    struct Node *temp = *head_ref, *prev = NULL;

    // Case 1: 如果头节点就是要删除的节点
    if (temp != NULL && temp->data == key) {
        *head_ref = temp->next; // 改变 head
        free(temp);             // 释放旧的 head
        return;
    }

    // Case 2: 查找要删除的节点，并记录其前一个节点
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    // 如果遍历完也没找到 key
    if (temp == NULL) return;

    // 从链中断开要删除的节点
    prev->next = temp->next;

    free(temp); // 释放内存
}

2.5 数组 vs. 链表

特性	数组 (Array)	链表 (Linked List)
大小	固定大小	动态大小
内存分配	连续的内存块	非连续，分散在各处
访问元素	O(1) - 随机访问	O(n) - 顺序访问
插入/删除 (开头)	O(n) - 需要移动元素	O(1) - 只需改变指针
插入/删除 (中间)	O(n) - 需要移动元素	O(n) - O(n)查找 + O(1)操作
内存开销	无额外开销	每个节点都有一个指针的额外开销

2.6 总结

链表是解决数组大小固定和插入/删除效率低下问题的一种优秀方案。当你无法预知需要存储的数据量，或者需要频繁地在列表的开头进行插入和删除操作时，链表是比数组更好的选择。然而，它的代价是失去了快速随机访问元素的能力。

理解链表对于掌握更复杂的数据结构（如栈、队列、哈希表、树等）至关重要。

第三部分：栈 (Stack) 与 队列 (Queue)

​​栈和队列是两种重要的抽象数据类型 (Abstract Data Type, ADT)。这意味着我们更关心它们的行为和规则（即允许哪些操作），而不是它们的底层实现。它们都可以通过数组或链表来实现。

​​### 3.1 栈 (Stack)

3.1.1 什么是栈？

栈是一种遵循后进先出 (Last-In, First-Out, LIFO) 原则的数据结构。

最经典的现实世界比喻就是一叠盘子。你只能在最顶端放上一个新盘子，也只能从最顶端拿走一个盘子。你最新放上去的那个盘子，必然是第一个被拿走的。

3.1.2 核心操作

• ​Push: 向栈的顶部添加一个元素。

​ * ​Pop: 从栈的顶部移除一个元素，并返回该元素。

​ * ​Peek (或 Top): 查看栈顶部的元素，但不移除它。

​ * ​isEmpty: 检查栈是否为空。

​ * isFull (主要用于数组实现): 检查栈是否已满。

3.1.3 栈的实现

1. 基于数组的实现

这是最简单的实现方式。我们需要一个数组来存储元素，以及一个名为 top 的整型变量来追踪栈顶元素的位置。top 通常初始化为 -1，表示栈是空的。

codeC

#include <stdio.h>
#include <stdlib.h>

#define CAPACITY 100 // 栈的最大容量

// 定义栈结构
struct Stack {
    int top;
    unsigned capacity;
    int* array;
};

// 创建一个栈
struct Stack* createStack() {
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
    stack->capacity = CAPACITY;
    stack->top = -1; // 初始化 top 为 -1
    stack->array = (int*) malloc(stack->capacity * sizeof(int));
    return stack;
}

// 检查栈是否已满
int isFull(struct Stack* stack) {
    return stack->top == stack->capacity - 1;
}

// 检查栈是否为空
int isEmpty(struct Stack* stack) {
    return stack->top == -1;
}

// Push 操作
void push(struct Stack* stack, int item) {
    if (isFull(stack)) {
        printf("栈溢出 (Stack Overflow)\n");
        return;
    }
    stack->array[++stack->top] = item; // top 先加 1，再赋值
    printf("%d 已推入栈中\n", item);
}

// Pop 操作
int pop(struct Stack* stack) {
    if (isEmpty(stack)) {
        printf("栈下溢 (Stack Underflow)\n");
        return -1; // 返回一个错误值
    }
    return stack->array[stack->top--]; // 先返回值，top 再减 1
}

// Peek 操作
int peek(struct Stack* stack) {
    if (isEmpty(stack)) return -1;
    return stack->array[stack->top];
}

​​优点: 实现简单，访问速度快。 缺点: 大小固定，可能造成空间浪费或溢出。

​​2. 基于链表的实现

使用链表实现栈可以解决大小固定的问题。链表的 head 节点就可以作为栈的 top。push 操作相当于在链表头部插入节点，pop 操作相当于删除头部节点。这两个操作的时间复杂度都是 O(1)。

codeC

#include <stdio.h>
#include <stdlib.h>

// 链表节点作为栈的节点
struct StackNode {
    int data;
    struct StackNode* next;
};

// 创建一个新节点
struct StackNode* newNode(int data) {
    struct StackNode* stackNode = (struct StackNode*) malloc(sizeof(struct StackNode));
    stackNode->data = data;
    stackNode->next = NULL;
    return stackNode;
}

int isEmpty(struct StackNode* root) {
    return !root;
}

// Push 操作 (在链表头部插入)
void push(struct StackNode** root, int data) {
    struct StackNode* stackNode = newNode(data);
    stackNode->next = *root;
    *root = stackNode;
    printf("%d 已推入栈中\n", data);
}

// Pop 操作 (删除链表头部)
int pop(struct StackNode** root) {
    if (isEmpty(*root)) {
        printf("栈为空\n");
        return -1;
    }
    struct StackNode* temp = *root;
    *root = (*root)->next;
    int popped = temp->data;
    free(temp);
    return popped;
}

3.1.4 栈的应用场景

• ​函数调用: 程序在调用函数时，会将返回地址、参数、局部变量等压入“调用栈”，函数返回时再从栈中弹出。递归就是函数调用栈的典型应用。

​ * ​表达式求值: 将中缀表达式转换为后缀（或前缀）表达式，然后进行求值。

​ * ​文本编辑器的撤销(Undo)功能: 每执行一个操作，就将其压入栈中；撤销时，就从栈中弹出一个操作。

​ * ​浏览器的前进/后退功能。

​

---

3.2 队列 (Queue)

3.2.1 什么是队列？

队列是一种遵循先进先出 (First-In, First-Out, FIFO) 原则的数据结构。

这和现实生活中的排队完全一样。第一个来排队的人，第一个接受服务。新来的人只能排在队伍的末尾。

队列有两个端点：

• ​Front (队头): 元素从这里离开队列（出队）。

​ * ​Rear (队尾): 新元素从这里进入队列（入队）。

​

3.2.2 核心操作

• ​Enqueue: 在队列的尾部添加一个元素。

​ * ​Dequeue: 从队列的头部移除一个元素，并返回该元素。

​ * ​Front: 查看队头的元素，但不移除。

​ * ​Rear: 查看队尾的元素，但不移除。

​ * ​isEmpty: 检查队列是否为空。

​

3.2.3 队列的实现

1. 基于链表的实现

这是队列最直观和高效的实现方式。我们需要维护两个指针：front 指向队头，rear 指向队尾。

• ​Enqueue: 在 rear 处添加新节点，并更新 rear 指针。时间复杂度 O(1)。

​ * ​Dequeue: 移除 front 指向的节点，并更新 front 指针。时间复杂度 O(1)。

​

codeC

#include <stdio.h>
#include <stdlib.h>

// 队列的节点
struct QNode {
    int key;
    struct QNode* next;
};

// 队列结构，包含 front 和 rear
struct Queue {
    struct QNode *front, *rear;
};

// 创建一个空队列
struct Queue* createQueue() {
    struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
    q->front = q->rear = NULL;
    return q;
}

// Enqueue 操作
void enqueue(struct Queue* q, int k) {
    struct QNode* temp = (struct QNode*)malloc(sizeof(struct QNode));
    temp->key = k;
    temp->next = NULL;

    // 如果队列为空，新节点既是 front 也是 rear
    if (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }

    // 将新节点添加到队尾，并改变 rear
    q->rear->next = temp;
    q->rear = temp;
}

// Dequeue 操作
int dequeue(struct Queue* q) {
    if (q->front == NULL) {
       printf("队列为空\n");
       return -1;
    }

    struct QNode* temp = q->front;
    int item = temp->key;

    q->front = q->front->next;

    // 如果 front 变为 NULL，说明队列已空，也要改变 rear
    if (q->front == NULL) {
        q->rear = NULL;
    }

    free(temp);
    return item;
}

2. 基于数组的实现 (循环队列)

​如果用普通数组实现队列，出队操作会导致数组前端产生大量闲置空间，造成浪费。为了解决这个问题，我们使用循环队列 (Circular Queue)。

​我们可以把数组想象成一个圆环。当指针到达数组末尾时，它会通过取模运算(%)绕回到数组的开头。这样就有效地利用了所有空间。实现循环队列需要仔细处理边界条件，判断队列是“满”还是“空”。

3.2.4 队列的应用场景

• ​任务调度: 操作系统使用队列来管理待处理的进程（进程队列）。

​ * ​打印机任务: 打印请求被放入一个队列中，打印机按照 FIFO 的顺序逐个处理。

​ * ​广度优先搜索 (BFS): 在图和树的遍历中，BFS 算法使用队列来存储待访问的节点。

​ * ​缓冲区: 在数据传输中，队列被用作缓冲区，以协调生产者和消费者之间不等的速度。例如，你在观看在线视频时，播放器会预先加载一部分数据到缓冲区队列中。

​

3.3 总结

• 栈 (Stack) 是 LIFO 结构，操作受限于“顶部”。它常用于需要“回溯”或“撤销”的场景。
• 队列 (Queue) 是 FIFO 结构，操作在“队头”和“队尾”进行。它常用于管理任务、请求或需要按顺序处理的资源。

理解这两种数据结构的行为模式比死记硬背它们的实现代码更重要。