C语言14章零基础干货 第十三章

第13章 数据结构基础

13.1 数据结构概述

数据结构是计算机科学中一门研究数据组织、存储和操作的学科。它是程序设计的基础，良好的数据结构选择可以提高程序的效率和可维护性。

13.1.1 数据结构的基本概念

• 数据：能够输入计算机并被计算机处理的各种符号的总称
• 数据元素：数据的基本单位，也称为记录
• 数据项：数据元素的最小单位，也称为字段
• 数据结构：相互之间存在一种或多种特定关系的数据元素的集合

13.1.2 数据结构的分类

根据数据元素之间的关系，数据结构可以分为以下几类：

• 线性结构：数据元素之间存在一对一的线性关系
  • 顺序表
  • 链表
  • 栈
  • 队列
• 非线性结构：数据元素之间存在一对多或多对多的关系
  • 树
  • 图

13.1.3 算法与数据结构的关系

算法是解决问题的步骤和方法，数据结构是数据的组织方式。算法和数据结构是相辅相成的，良好的数据结构设计可以提高算法的效率，而高效的算法需要合适的数据结构支持。

13.1.4 算法复杂度分析

算法复杂度分析是评估算法效率的重要方法，包括时间复杂度和空间复杂度。

13.1.4.1 时间复杂度

时间复杂度是指算法执行所需的时间与问题规模之间的关系，通常使用大O符号（O-notation）表示。时间复杂度表示算法的渐近行为，即当问题规模n趋近于无穷大时，算法执行时间的增长速度。

常见的时间复杂度级别（从低到高）：

13.1.4.2 空间复杂度

空间复杂度是指算法执行所需的内存空间与问题规模之间的关系，同样使用大O符号表示。空间复杂度包括算法本身占用的空间和算法执行过程中临时占用的空间。

常见的空间复杂度级别：

• O(1)：常数空间，算法执行所需的空间与问题规模无关
• O(n)：线性空间，算法执行所需的空间与问题规模线性相关
• O(n²)：平方空间，算法执行所需的空间与问题规模的平方相关

13.1.4.3 如何计算算法复杂度

计算算法复杂度的基本步骤：

示例：计算冒泡排序的时间复杂度

void bubble_sort(int arr[], int n) {
for (int i = 0; i < n – 1; i++) { // 执行n-1次
for (int j = 0; j < n – i – 1; j++) { // 执行(n-1)+(n-2)+…+1 = n(n-1)/2次
if (arr[j] > arr[j + 1]) { // 基本操作，执行n(n-1)/2次
// 交换元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

冒泡排序的基本操作是比较和交换元素，执行次数为n(n-1)/2，忽略低阶项和常数系数后，时间复杂度为O(n²)。

章节趣事：数据结构的起源

数据结构的概念最早可以追溯到20世纪60年代，当时计算机科学家们开始意识到，高效的算法设计必须建立在合理的数据组织之上。1968年，Donald Knuth出版了《计算机程序设计艺术》第一卷，系统地阐述了数据结构和算法的关系，这本书被誉为计算机科学领域的圣经。有趣的是，Knuth在撰写这本书时，使用的是自己设计的排版系统TeX，而TeX本身也成为了计算机科学史上的经典之作。

13.2 线性表

线性表是最简单、最常用的数据结构之一，它是由n个具有相同特性的数据元素组成的有限序列。

13.2.1 顺序表

顺序表是用一组地址连续的存储单元依次存储线性表的数据元素，通常使用数组实现。

顺序表的特点：

• 元素在内存中连续存储
• 可以通过索引直接访问任意元素
• 插入和删除元素需要移动大量元素
• 存储密度高

顺序表的基本操作：

• 初始化
• 插入元素
• 删除元素
• 查找元素
• 遍历元素

示例：顺序表的实现

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

#define MAX_SIZE 100

// 顺序表结构体
typedef struct {
int data[MAX_SIZE];
int length;
} SeqList;

// 初始化顺序表
void init_list(SeqList *L) {
L->length = 0;
}

// 插入元素到指定位置
int insert_list(SeqList *L, int pos, int elem) {
if (L->length >= MAX_SIZE) {
printf("顺序表已满，无法插入\\n");
return 0;
}
if (pos < 1 || pos > L->length + 1) {
printf("插入位置无效\\n");
return 0;
}

// 移动元素
for (int i = L->length; i >= pos; i–) {
L->data[i] = L->data[i – 1];
}

L->data[pos – 1] = elem;
L->length++;
return 1;
}

// 删除指定位置的元素
int delete_list(SeqList *L, int pos, int *elem) {
if (L->length == 0) {
printf("顺序表为空，无法删除\\n");
return 0;
}
if (pos < 1 || pos > L->length) {
printf("删除位置无效\\n");
return 0;
}

*elem = L->data[pos – 1];

// 移动元素
for (int i = pos; i < L->length; i++) {
L->data[i – 1] = L->data[i];
}

L->length–;
return 1;
}

// 查找元素
int search_list(SeqList *L, int elem) {
for (int i = 0; i < L->length; i++) {
if (L->data[i] == elem) {
return i + 1; // 返回位置
}
}
return 0; // 未找到
}

// 遍历顺序表
void traverse_list(SeqList *L) {
if (L->length == 0) {
printf("顺序表为空\\n");
return;
}

printf("顺序表元素：");
for (int i = 0; i < L->length; i++) {
printf("%d ", L->data[i]);
}
printf("\\n");
}

int main() {
SeqList L;
int elem;

// 初始化顺序表
init_list(&L);

// 插入元素
insert_list(&L, 1, 10);
insert_list(&L, 2, 20);
insert_list(&L, 3, 30);
insert_list(&L, 2, 15);

// 遍历顺序表
traverse_list(&L); // 输出：10 15 20 30

// 查找元素
int pos = search_list(&L, 20);
printf("元素20的位置：%d\\n", pos); // 输出：3

// 删除元素
if (delete_list(&L, 2, &elem)) {
printf("删除的元素：%d\\n", elem); // 输出：15
}

// 遍历顺序表
traverse_list(&L); // 输出：10 20 30

return 0;
}

13.2.2 链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表的特点：

• 元素在内存中不连续存储
• 通过指针访问元素，不能直接索引
• 插入和删除元素只需要修改指针，不需要移动大量元素
• 存储密度低，每个元素需要额外的指针空间

13.2.2.1 单链表

单链表是链表中最简单的一种，每个节点只包含一个数据域和一个指针域。

示例：单链表的实现

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

// 单链表节点结构体
typedef struct Node {
int data;
struct Node *next;
} Node;

// 初始化单链表
void init_list(Node **head) {
*head = NULL;
}

// 创建节点
Node *create_node(int data) {
Node *new_node = (Node *)malloc(sizeof(Node));
if (new_node == NULL) {
printf("内存分配失败\\n");
return NULL;
}
new_node->data = data;
new_node->next = NULL;
return new_node;
}

// 插入节点到链表头部
void insert_head(Node **head, int data) {
Node *new_node = create_node(data);
if (new_node == NULL) {
return;
}
new_node->next = *head;
*head = new_node;
}

// 插入节点到链表尾部
void insert_tail(Node **head, int data) {
Node *new_node = create_node(data);
if (new_node == NULL) {
return;
}

if (*head == NULL) {
*head = new_node;
return;
}

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

// 删除指定值的节点
void delete_node(Node **head, int data) {
if (*head == NULL) {
return;
}

Node *temp = *head;
Node *prev = NULL;

// 如果头节点就是要删除的节点
if (temp->data == data) {
*head = temp->next;
free(temp);
return;
}

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

// 未找到要删除的节点
if (temp == NULL) {
return;
}

// 删除节点
prev->next = temp->next;
free(temp);
}

// 遍历链表
void traverse_list(Node *head) {
if (head == NULL) {
printf("链表为空\\n");
return;
}

Node *temp = head;
printf("链表元素：");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\\n");
}

// 销毁链表
void destroy_list(Node **head) {
Node *temp;
while (*head != NULL) {
temp = *head;
*head = (*head)->next;
free(temp);
}
}

int main() {
Node *head;

// 初始化链表
init_list(&head);

// 插入节点到尾部
insert_tail(&head, 10);
insert_tail(&head, 20);
insert_tail(&head, 30);

// 遍历链表
traverse_list(head); // 输出：10 20 30

// 插入节点到头部
insert_head(&head, 5);
traverse_list(head); // 输出：5 10 20 30

// 删除节点
delete_node(&head, 10);
traverse_list(head); // 输出：5 20 30

// 销毁链表
destroy_list(&head);
traverse_list(head); // 输出：链表为空

return 0;
}

13.2.2.2 双链表

双链表是在单链表的基础上，每个节点增加了一个指向前驱节点的指针，使得可以双向遍历链表。双链表的优点是可以从任意节点开始向前或向后遍历，但缺点是每个节点需要额外的指针空间。

双链表节点结构体：

typedef struct DNode {
int data; // 数据域
struct DNode *prev; // 指向前驱节点的指针
struct DNode *next; // 指向后继节点的指针
} DNode;

示例：双链表的实现

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

// 双链表节点结构体
typedef struct DNode {
int data;
struct DNode *prev;
struct DNode *next;
} DNode;

// 初始化双链表
void init_list(DNode **head) {
*head = NULL;
}

// 创建双链表节点
DNode *create_node(int data) {
DNode *new_node = (DNode *)malloc(sizeof(DNode));
if (new_node == NULL) {
printf("内存分配失败\\n");
return NULL;
}
new_node->data = data;
new_node->prev = NULL;
new_node->next = NULL;
return new_node;
}

// 插入节点到链表头部
void insert_head(DNode **head, int data) {
DNode *new_node = create_node(data);
if (new_node == NULL) {
return;
}

if (*head == NULL) {
*head = new_node;
return;
}

new_node->next = *head;
(*head)->prev = new_node;
*head = new_node;
}

// 插入节点到链表尾部
void insert_tail(DNode **head, int data) {
DNode *new_node = create_node(data);
if (new_node == NULL) {
return;
}

if (*head == NULL) {
*head = new_node;
return;
}

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

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

// 插入节点到指定位置之后
void insert_after(DNode *node, int data) {
if (node == NULL) {
return;
}

DNode *new_node = create_node(data);
if (new_node == NULL) {
return;
}

new_node->next = node->next;
new_node->prev = node;

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

node->next = new_node;
}

// 删除指定节点
void delete_node(DNode **head, DNode *node) {
if (*head == NULL || node == NULL) {
return;
}

// 如果是头节点
if (*head == node) {
*head = node->next;
if (*head != NULL) {
(*head)->prev = NULL;
}
free(node);
return;
}

// 如果是中间节点或尾节点
if (node->prev != NULL) {
node->prev->next = node->next;
}

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

free(node);
}

// 删除指定值的节点
void delete_by_value(DNode **head, int data) {
if (*head == NULL) {
return;
}

DNode *temp = *head;

// 查找要删除的节点
while (temp != NULL) {
if (temp->data == data) {
DNode *next_node = temp->next;
delete_node(head, temp);
temp = next_node;
} else {
temp = temp->next;
}
}
}

// 遍历双链表（正向）
void traverse_forward(DNode *head) {
if (head == NULL) {
printf("链表为空\\n");
return;
}

DNode *temp = head;
printf("正向遍历：");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\\n");
}

// 遍历双链表（反向）
void traverse_backward(DNode *head) {
if (head == NULL) {
printf("链表为空\\n");
return;
}

// 先找到尾节点
DNode *temp = head;
while (temp->next != NULL) {
temp = temp->next;
}

printf("反向遍历：");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->prev;
}
printf("\\n");
}

// 查找节点
DNode *search_node(DNode *head, int data) {
DNode *temp = head;
while (temp != NULL) {
if (temp->data == data) {
return temp;
}
temp = temp->next;
}
return NULL;
}

// 销毁双链表
void destroy_list(DNode **head) {
DNode *temp;
while (*head != NULL) {
temp = *head;
*head = (*head)->next;
free(temp);
}
}

int main() {
DNode *head;

// 初始化双链表
init_list(&head);

// 插入节点
insert_tail(&head, 10);
insert_tail(&head, 20);
insert_tail(&head, 30);
insert_head(&head, 5);

// 正向遍历
traverse_forward(head); // 输出：5 10 20 30

// 反向遍历
traverse_backward(head); // 输出：30 20 10 5

// 查找节点
DNode *node = search_node(head, 20);
if (node != NULL) {
printf("找到节点：%d\\n", node->data);
// 在找到的节点后插入新节点
insert_after(node, 25);
traverse_forward(head); // 输出：5 10 20 25 30
}

// 删除节点
delete_by_value(&head, 10);
traverse_forward(head); // 输出：5 20 25 30

// 销毁双链表
destroy_list(&head);
traverse_forward(head); // 输出：链表为空

return 0;
}

13.2.2.3 循环链表

循环链表是将链表的最后一个节点的指针指向链表的头节点，形成一个环形结构。循环链表可以分为单向循环链表和双向循环链表。

单向循环链表的特点：

• 最后一个节点的next指针指向头节点
• 可以从任意节点开始遍历整个链表
• 适合需要反复遍历的数据结构，如约瑟夫环问题

示例：单向循环链表的实现

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

// 单向循环链表节点结构体
typedef struct CNode {
int data;
struct CNode *next;
} CNode;

// 初始化循环链表
void init_list(CNode **head) {
*head = NULL;
}

// 创建节点
CNode *create_node(int data) {
CNode *new_node = (CNode *)malloc(sizeof(CNode));
if (new_node == NULL) {
printf("内存分配失败\\n");
return NULL;
}
new_node->data = data;
new_node->next = NULL;
return new_node;
}

// 插入节点到链表头部
void insert_head(CNode **head, int data) {
CNode *new_node = create_node(data);
if (new_node == NULL) {
return;
}

if (*head == NULL) {
*head = new_node;
new_node->next = *head;
return;
}

// 找到尾节点
CNode *tail = *head;
while (tail->next != *head) {
tail = tail->next;
}

new_node->next = *head;
tail->next = new_node;
*head = new_node;
}

// 插入节点到链表尾部
void insert_tail(CNode **head, int data) {
CNode *new_node = create_node(data);
if (new_node == NULL) {
return;
}

if (*head == NULL) {
*head = new_node;
new_node->next = *head;
return;
}

// 找到尾节点
CNode *tail = *head;
while (tail->next != *head) {
tail = tail->next;
}

tail->next = new_node;
new_node->next = *head;
}

// 删除头节点
void delete_head(CNode **head) {
if (*head == NULL) {
return;
}

if ((*head)->next == *head) {
// 只有一个节点
free(*head);
*head = NULL;
return;
}

// 找到尾节点
CNode *tail = *head;
while (tail->next != *head) {
tail = tail->next;
}

CNode *temp = *head;
*head = (*head)->next;
tail->next = *head;
free(temp);
}

// 遍历循环链表
void traverse_list(CNode *head) {
if (head == NULL) {
printf("链表为空\\n");
return;
}

CNode *temp = head;
printf("循环链表元素：");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\\n");
}

// 销毁循环链表
void destroy_list(CNode **head) {
if (*head == NULL) {
return;
}

CNode *temp = (*head)->next;
CNode *next_node;

while (temp != *head) {
next_node = temp->next;
free(temp);
temp = next_node;
}

free(*head);
*head = NULL;
}

int main() {
CNode *head;

// 初始化循环链表
init_list(&head);

// 插入节点
insert_tail(&head, 10);
insert_tail(&head, 20);
insert_tail(&head, 30);
insert_head(&head, 5);

// 遍历循环链表
traverse_list(head); // 输出：5 10 20 30

// 删除头节点
delete_head(&head);
traverse_list(head); // 输出：10 20 30

// 销毁循环链表
destroy_list(&head);
traverse_list(head); // 输出：链表为空

return 0;
}

疑难解析：链表操作常见问题

易错部分：链表操作中的常见错误

13.3 栈和队列

13.3.1 栈

栈是一种特殊的线性表，它的插入和删除操作只允许在表的一端进行，这一端称为栈顶。栈的操作遵循后进先出（LIFO）的原则。

栈的基本操作：

• 压栈（Push）：将元素插入到栈顶
• 弹栈（Pop）：从栈顶删除元素
• 获取栈顶元素（Top）：查看栈顶元素，但不删除
• 判空（Empty）：检查栈是否为空
• 获取栈的大小（Size）：返回栈中元素的个数

示例：栈的实现（使用数组）

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

#define MAX_SIZE 100

// 栈结构体
typedef struct {
int data[MAX_SIZE];
int top;
} Stack;

// 初始化栈
void init_stack(Stack *s) {
s->top = -1;
}

// 判空
int is_empty(Stack *s) {
return s->top == -1;
}

// 判满
int is_full(Stack *s) {
return s->top == MAX_SIZE – 1;
}

// 压栈
int push(Stack *s, int data) {
if (is_full(s)) {
printf("栈已满，无法压栈\\n");
return 0;
}
s->data[++s->top] = data;
return 1;
}

// 弹栈
int pop(Stack *s, int *data) {
if (is_empty(s)) {
printf("栈为空，无法弹栈\\n");
return 0;
}
*data = s->data[s->top–];
return 1;
}

// 获取栈顶元素
int get_top(Stack *s, int *data) {
if (is_empty(s)) {
printf("栈为空\\n");
return 0;
}
*data = s->data[s->top];
return 1;
}

// 获取栈的大小
int get_size(Stack *s) {
return s->top + 1;
}

// 遍历栈
void traverse_stack(Stack *s) {
if (is_empty(s)) {
printf("栈为空\\n");
return;
}

printf("栈元素（从栈顶到栈底）：");
for (int i = s->top; i >= 0; i–) {
printf("%d ", s->data[i]);
}
printf("\\n");
}

int main() {
Stack s;
int data;

// 初始化栈
init_stack(&s);

// 压栈
push(&s, 10);
push(&s, 20);
push(&s, 30);

// 遍历栈
traverse_stack(&s); // 输出：30 20 10

// 获取栈顶元素
if (get_top(&s, &data)) {
printf("栈顶元素：%d\\n", data); // 输出：30
}

// 弹栈
if (pop(&s, &data)) {
printf("弹出的元素：%d\\n", data); // 输出：30
}

// 遍历栈
traverse_stack(&s); // 输出：20 10

// 获取栈的大小
printf("栈的大小：%d\\n", get_size(&s)); // 输出：2

return 0;
}

13.3.2 队列

队列是一种特殊的线性表，它的插入操作在表的一端进行，称为队尾；删除操作在表的另一端进行，称为队头。队列的操作遵循先进先出（FIFO）的原则。

队列的基本操作：

• 入队（Enqueue）：将元素插入到队尾
• 出队（Dequeue）：从队头删除元素
• 获取队头元素（Front）：查看队头元素，但不删除
• 获取队尾元素（Rear）：查看队尾元素，但不删除
• 判空（Empty）：检查队列是否为空
• 获取队列的大小（Size）：返回队列中元素的个数

示例：队列的实现（使用数组，循环队列）

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

#define MAX_SIZE 100

// 队列结构体
typedef struct {
int data[MAX_SIZE];
int front;
int rear;
int size;
} Queue;

// 初始化队列
void init_queue(Queue *q) {
q->front = 0;
q->rear = 0;
q->size = 0;
}

// 判空
int is_empty(Queue *q) {
return q->size == 0;
}

// 判满
int is_full(Queue *q) {
return q->size == MAX_SIZE;
}

// 入队
int enqueue(Queue *q, int data) {
if (is_full(q)) {
printf("队列已满，无法入队\\n");
return 0;
}
q->data[q->rear] = data;
q->rear = (q->rear + 1) % MAX_SIZE;
q->size++;
return 1;
}

// 出队
int dequeue(Queue *q, int *data) {
if (is_empty(q)) {
printf("队列为空，无法出队\\n");
return 0;
}
*data = q->data[q->front];
q->front = (q->front + 1) % MAX_SIZE;
q->size–;
return 1;
}

// 获取队头元素
int get_front(Queue *q, int *data) {
if (is_empty(q)) {
printf("队列为空\\n");
return 0;
}
*data = q->data[q->front];
return 1;
}

// 获取队尾元素
int get_rear(Queue *q, int *data) {
if (is_empty(q)) {
printf("队列为空\\n");
return 0;
}
int rear_index = (q->rear – 1 + MAX_SIZE) % MAX_SIZE;
*data = q->data[rear_index];
return 1;
}

// 获取队列的大小
int get_size(Queue *q) {
return q->size;
}

// 遍历队列
void traverse_queue(Queue *q) {
if (is_empty(q)) {
printf("队列为空\\n");
return;
}

printf("队列元素：");
for (int i = 0; i < q->size; i++) {
int index = (q->front + i) % MAX_SIZE;
printf("%d ", q->data[index]);
}
printf("\\n");
}

int main() {
Queue q;
int data;

// 初始化队列
init_queue(&q);

// 入队
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);

// 遍历队列
traverse_queue(&q); // 输出：10 20 30

// 获取队头元素
if (get_front(&q, &data)) {
printf("队头元素：%d\\n", data); // 输出：10
}

// 获取队尾元素
if (get_rear(&q, &data)) {
printf("队尾元素：%d\\n", data); // 输出：30
}

// 出队
if (dequeue(&q, &data)) {
printf("出队的元素：%d\\n", data); // 输出：10
}

// 遍历队列
traverse_queue(&q); // 输出：20 30

// 获取队列的大小
printf("队列的大小：%d\\n", get_size(&q)); // 输出：2

return 0;
}

13.4 树和二叉树

树是一种非线性数据结构，它是由n个有限节点组成的一个具有层次关系的集合。

13.4.1 树的基本概念

• 根节点：树的顶端节点，没有父节点
• 父节点：一个节点的直接上级节点
• 子节点：一个节点的直接下级节点
• 叶子节点：没有子节点的节点
• 节点的度：一个节点的子节点个数
• 树的度：树中节点的最大度
• 节点的层次：根节点的层次为1，其子节点的层次为2，依此类推
• 树的高度：树中节点的最大层次

13.4.2 二叉树

二叉树是一种特殊的树，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树的性质：

• 第i层最多有2^(i-1)个节点
• 深度为k的二叉树最多有2^k – 1个节点
• 对于任意一棵二叉树，叶子节点数等于度为2的节点数加1

13.4.2.1 二叉树的遍历

二叉树的遍历是指按照一定的顺序访问二叉树中的所有节点，常用的遍历方法有：

• 前序遍历：根节点 → 左子树 → 右子树
• 中序遍历：左子树 → 根节点 → 右子树
• 后序遍历：左子树 → 右子树 → 根节点
• 层序遍历：按照节点的层次从上到下，每层从左到右访问

示例：二叉树的实现和遍历

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

// 二叉树节点结构体
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;

// 创建二叉树节点
TreeNode *create_node(int data) {
TreeNode *new_node = (TreeNode *)malloc(sizeof(TreeNode));
if (new_node == NULL) {
printf("内存分配失败\\n");
return NULL;
}
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}

// 前序遍历
void preorder_traversal(TreeNode *root) {
if (root == NULL) {
return;
}
printf("%d ", root->data);
preorder_traversal(root->left);
preorder_traversal(root->right);
}

// 中序遍历
void inorder_traversal(TreeNode *root) {
if (root == NULL) {
return;
}
inorder_traversal(root->left);
printf("%d ", root->data);
inorder_traversal(root->right);
}

// 后序遍历
void postorder_traversal(TreeNode *root) {
if (root == NULL) {
return;
}
postorder_traversal(root->left);
postorder_traversal(root->right);
printf("%d ", root->data);
}

// 层序遍历
void level_order_traversal(TreeNode *root) {
if (root == NULL) {
return;
}

// 使用队列实现层序遍历
TreeNode *queue[100];
int front = 0, rear = 0;

queue[rear++] = root;

while (front < rear) {
TreeNode *node = queue[front++];
printf("%d ", node->data);

if (node->left != NULL) {
queue[rear++] = node->left;
}
if (node->right != NULL) {
queue[rear++] = node->right;
}
}
}

// 销毁二叉树
void destroy_tree(TreeNode *root) {
if (root == NULL) {
return;
}
destroy_tree(root->left);
destroy_tree(root->right);
free(root);
}

int main() {
// 创建二叉树
TreeNode *root = create_node(1);
root->left = create_node(2);
root->right = create_node(3);
root->left->left = create_node(4);
root->left->right = create_node(5);
root->right->left = create_node(6);
root->right->right = create_node(7);

// 前序遍历
printf("前序遍历：");
preorder_traversal(root); // 输出：1 2 4 5 3 6 7
printf("\\n");

// 中序遍历
printf("中序遍历：");
inorder_traversal(root); // 输出：4 2 5 1 6 3 7
printf("\\n");

// 后序遍历
printf("后序遍历：");
postorder_traversal(root); // 输出：4 5 2 6 7 3 1
printf("\\n");

// 层序遍历
printf("层序遍历：");
level_order_traversal(root); // 输出：1 2 3 4 5 6 7
printf("\\n");

// 销毁二叉树
destroy_tree(root);

return 0;
}

13.5 图的基本概念

图是一种复杂的非线性数据结构，它由顶点和边组成，顶点表示数据元素，边表示数据元素之间的关系。

13.5.1 图的基本术语

• 顶点：图中的数据元素
• 边：连接两个顶点的线，表示两个顶点之间的关系
• 有向图：边有方向的图
• 无向图：边没有方向的图
• 顶点的度：无向图中，顶点的边数
• 顶点的入度：有向图中，指向该顶点的边数
• 顶点的出度：有向图中，从该顶点出发的边数
• 路径：从一个顶点到另一个顶点的顶点序列
• 路径长度：路径中边的数量
• 环：起点和终点相同的路径

13.5.2 图的存储方式

• 邻接矩阵：使用二维数组表示图，数组的行和列分别表示顶点，数组元素表示边的存在与否
• 邻接表：使用链表表示图，每个顶点对应一个链表，链表中存储与该顶点相邻的顶点

13.6 查找算法

查找算法是在数据结构中查找特定元素的算法，常用的查找算法有线性查找、二分查找等。

13.6.1 线性查找

线性查找是最简单的查找算法，它从数据结构的一端开始，依次检查每个元素，直到找到目标元素或遍历完整个数据结构。

示例：线性查找

#include <stdio.h>

// 线性查找
int linear_search(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // 返回目标元素的索引
}
}
return -1; // 未找到，返回-1
}

int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 30;

int index = linear_search(arr, n, target);
if (index != -1) {
printf("元素%d的索引：%d\\n", target, index); // 输出：元素30的索引：2
} else {
printf("未找到元素%d\\n", target);
}

return 0;
}

13.6.2 二分查找

二分查找是一种高效的查找算法，它要求数据结构是有序的。它通过不断将查找区间减半，直到找到目标元素或查找区间为空。

示例：二分查找

#include <stdio.h>

// 二分查找
int binary_search(int arr[], int n, int target) {
int left = 0;
int right = n – 1;

while (left <= right) {
int mid = left + (right – left) / 2;

if (arr[mid] == target) {
return mid; // 找到目标元素，返回索引
} else if (arr[mid] < target) {
left = mid + 1; // 目标元素在右半部分
} else {
right = mid – 1; // 目标元素在左半部分
}
}

return -1; // 未找到，返回-1
}

int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 30;

int index = binary_search(arr, n, target);
if (index != -1) {
printf("元素%d的索引：%d\\n", target, index); // 输出：元素30的索引：2
} else {
printf("未找到元素%d\\n", target);
}

return 0;
}

13.7 排序算法

排序算法是将数据结构中的元素按照一定的顺序排列的算法，常用的排序算法有冒泡排序、选择排序、插入排序、快速排序等。

13.7.1 冒泡排序

冒泡排序是一种简单的排序算法，它通过重复遍历要排序的数组，比较相邻的两个元素，如果它们的顺序错误就交换它们，直到整个数组排序完成。

示例：冒泡排序

#include <stdio.h>

// 冒泡排序
void bubble_sort(int arr[], int n) {
for (int i = 0; i < n – 1; i++) {
for (int j = 0; j < n – i – 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

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

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

printf("排序前：");
print_array(arr, n); // 输出：64 34 25 12 22 11 90

bubble_sort(arr, n);

printf("排序后：");
print_array(arr, n); // 输出：11 12 22 25 34 64 90

return 0;
}

13.7.2 选择排序

选择排序是一种简单的排序算法，它每次从待排序数组中选择最小（或最大）的元素，放到数组的起始位置，然后从剩余未排序元素中继续寻找最小（或最大）元素，放到已排序数组的末尾，直到所有元素排序完成。

示例：选择排序

#include <stdio.h>

// 选择排序
void selection_sort(int arr[], int n) {
for (int i = 0; i < n – 1; i++) {
int min_index = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
// 交换元素
int temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
}
}

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

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

printf("排序前：");
print_array(arr, n); // 输出：64 34 25 12 22 11 90

selection_sort(arr, n);

printf("排序后：");
print_array(arr, n); // 输出：11 12 22 25 34 64 90

return 0;
}

13.7.3 插入排序

插入排序是一种简单的排序算法，它将数组分为已排序部分和未排序部分，每次从未排序部分中取出一个元素，插入到已排序部分的适当位置，直到所有元素排序完成。

示例：插入排序

#include <stdio.h>

// 插入排序
void insertion_sort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i – 1;

// 将大于key的元素向右移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j–;
}
arr[j + 1] = key;
}
}

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

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);

printf("排序前：");
print_array(arr, n); // 输出：64 34 25 12 22 11 90

insertion_sort(arr, n);

printf("排序后：");
print_array(arr, n); // 输出：11 12 22 25 34 64 90

return 0;
}

13.7.4 快速排序

快速排序是一种高效的排序算法，它采用分治策略，选择一个基准元素，将数组分为两部分，一部分小于基准元素，一部分大于基准元素，然后递归地对这两部分进行排序。快速排序的平均时间复杂度为O(n log n)，最坏情况为O(n²)，但通过合理选择基准元素（如随机选择或三数取中），可以避免最坏情况的发生。

示例：快速排序

#include <stdio.h>

// 交换元素
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

// 三数取中法选择基准元素
int median_of_three(int arr[], int low, int high) {
int mid = low + (high – low) / 2;

// 将三个元素排序
if (arr[low] > arr[mid]) {
swap(&arr[low], &arr[mid]);
}
if (arr[low] > arr[high]) {
swap(&arr[low], &arr[high]);
}
if (arr[mid] > arr[high]) {
swap(&arr[mid], &arr[high]);
}

// 将基准元素放到high-1位置
swap(&arr[mid], &arr[high – 1]);
return arr[high – 1];
}

// 分区函数
int partition(int arr[], int low, int high) {
int pivot = median_of_three(arr, low, high); // 使用三数取中法选择基准
int i = low; // 小于基准的元素的索引
int j = high – 1; // 大于基准的元素的索引

while (1) {
// 从左向右找到第一个大于等于基准的元素
while (arr[++i] < pivot) {
// 为空循环，直到找到目标元素
}

// 从右向左找到第一个小于等于基准的元素
while (arr[–j] > pivot) {
// 为空循环，直到找到目标元素
}

if (i < j) {
swap(&arr[i], &arr[j]);
} else {
break;
}
}

// 将基准元素放回正确位置
swap(&arr[i], &arr[high – 1]);
return i;
}

// 快速排序
void quick_sort(int arr[], int low, int high) {
if (low + 10 <= high) { // 当数组长度较小时，使用插入排序更高效
int pi = partition(arr, low, high);
quick_sort(arr, low, pi – 1);
quick_sort(arr, pi + 1, high);
} else {
// 插入排序（用于小规模数组）
for (int i = low + 1; i <= high; i++) {
int key = arr[i];
int j = i – 1;
while (j >= low && arr[j] > key) {
arr[j + 1] = arr[j];
j–;
}
arr[j + 1] = key;
}
}
}

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

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90, 5, 18, 75, 33, 55, 89, 21, 44};
int n = sizeof(arr) / sizeof(arr[0]);

printf("排序前：");
print_array(arr, n);

quick_sort(arr, 0, n – 1);

printf("排序后：");
print_array(arr, n);

return 0;
}

13.7.5 归并排序

归并排序是一种稳定的排序算法，它采用分治策略，将数组分成两个子数组，递归地对这两个子数组进行排序，然后将排序好的子数组合并成一个有序数组。归并排序的时间复杂度为O(n log n)，空间复杂度为O(n)。

示例：归并排序

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

// 合并两个有序数组
void merge(int arr[], int left, int mid, int right, int temp[]) {
int i = left; // 左子数组的起始索引
int j = mid + 1; // 右子数组的起始索引
int k = 0; // 临时数组的起始索引

// 合并两个子数组到临时数组
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}

// 将左子数组剩余元素复制到临时数组
while (i <= mid) {
temp[k++] = arr[i++];
}

// 将右子数组剩余元素复制到临时数组
while (j <= right) {
temp[k++] = arr[j++];
}

// 将临时数组中的元素复制回原数组
k = 0;
for (int m = left; m <= right; m++) {
arr[m] = temp[k++];
}
}

// 归并排序
void merge_sort(int arr[], int left, int right, int temp[]) {
if (left < right) {
int mid = left + (right – left) / 2;

// 递归排序左子数组
merge_sort(arr, left, mid, temp);

// 递归排序右子数组
merge_sort(arr, mid + 1, right, temp);

// 合并两个有序子数组
merge(arr, left, mid, right, temp);
}
}

// 归并排序的包装函数
void merge_sort_wrapper(int arr[], int n) {
// 为临时数组分配内存
int *temp = (int *)malloc(n * sizeof(int));
if (temp == NULL) {
printf("内存分配失败\\n");
return;
}

merge_sort(arr, 0, n – 1, temp);

// 释放临时数组内存
free(temp);
}

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

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90, 5, 18, 75};
int n = sizeof(arr) / sizeof(arr[0]);

printf("排序前：");
print_array(arr, n);

merge_sort_wrapper(arr, n);

printf("排序后：");
print_array(arr, n);

return 0;
}

13.7.6 堆排序

堆排序是一种基于堆数据结构的排序算法，它利用堆的性质来进行排序。堆是一种完全二叉树，分为最大堆和最小堆。最大堆的每个节点的值都大于或等于其子节点的值，最小堆的每个节点的值都小于或等于其子节点的值。堆排序的时间复杂度为O(n log n)，空间复杂度为O(1)。

示例：堆排序

#include <stdio.h>

// 交换元素
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

// 调整堆
void heapify(int arr[], int n, int i) {
int largest = i; // 初始化最大值为根节点
int left = 2 * i + 1; // 左子节点索引
int right = 2 * i + 2; // 右子节点索引

// 如果左子节点大于根节点
if (left < n && arr[left] > arr[largest]) {
largest = left;
}

// 如果右子节点大于当前最大值
if (right < n && arr[right] > arr[largest]) {
largest = right;
}

// 如果最大值不是根节点
if (largest != i) {
swap(&arr[i], &arr[largest]);

// 递归调整受影响的子树
heapify(arr, n, largest);
}
}

// 堆排序
void heap_sort(int arr[], int n) {
// 构建最大堆
for (int i = n / 2 – 1; i >= 0; i–) {
heapify(arr, n, i);
}

// 逐个提取堆顶元素（最大值）
for (int i = n – 1; i > 0; i–) {
// 将当前堆顶（最大值）移到数组末尾
swap(&arr[0], &arr[i]);

// 调整剩余元素为最大堆
heapify(arr, i, 0);
}
}

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

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90, 5, 18, 75};
int n = sizeof(arr) / sizeof(arr[0]);

printf("排序前：");
print_array(arr, n);

heap_sort(arr, n);

printf("排序后：");
print_array(arr, n);

return 0;
}

13.8 哈希表

哈希表是一种根据关键码值直接访问数据的数据结构，它通过哈希函数将关键码值映射到表中的一个位置来访问数据，具有O(1)的平均查找时间复杂度。哈希表的主要组成部分包括哈希函数、哈希表数组和解决冲突的方法。

13.8.1 哈希函数

哈希函数是将关键码值映射到哈希表索引的函数，一个好的哈希函数应该具有以下特点：

• 计算简单，效率高
• 分布均匀，减少冲突
• 定义域覆盖所有可能的关键码值

13.8.2 解决冲突的方法

哈希冲突是指不同的关键码值通过哈希函数得到相同的哈希表索引，常见的解决冲突的方法包括：

• 开放寻址法：当发生冲突时，按照一定的探测序列寻找下一个空位置
• 链地址法：将哈希值相同的元素存储在同一个链表中
• 再哈希法：当发生冲突时，使用另一个哈希函数计算新的哈希值
• 建立公共溢出区：将冲突的元素存储在一个公共的溢出区中

示例：链地址法实现哈希表

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

#define HASH_SIZE 100

// 哈希表节点结构体
typedef struct HashNode {
char *key; // 键
int value; // 值
struct HashNode *next; // 指向下一个节点的指针
} HashNode;

// 哈希表结构体
typedef struct {
HashNode *table[HASH_SIZE]; // 哈希表数组
} HashTable;

// 初始化哈希表
void init_hash_table(HashTable *ht) {
for (int i = 0; i < HASH_SIZE; i++) {
ht->table[i] = NULL;
}
}

// 哈希函数
int hash_function(char *key) {
int hash = 0;
while (*key) {
hash = (hash * 31 + *key++) % HASH_SIZE;
}
return hash;
}

// 创建哈希表节点
HashNode *create_hash_node(char *key, int value) {
HashNode *new_node = (HashNode *)malloc(sizeof(HashNode));
if (new_node == NULL) {
printf("内存分配失败\\n");
return NULL;
}
new_node->key = strdup(key);
new_node->value = value;
new_node->next = NULL;
return new_node;
}

// 插入元素到哈希表
void insert(HashTable *ht, char *key, int value) {
int hash = hash_function(key);

// 查找是否已存在相同的键
HashNode *curr = ht->table[hash];
while (curr != NULL) {
if (strcmp(curr->key, key) == 0) {
// 更新已有键的值
curr->value = value;
return;
}
curr = curr->next;
}

// 插入新节点到链表头部
HashNode *new_node = create_hash_node(key, value);
if (new_node != NULL) {
new_node->next = ht->table[hash];
ht->table[hash] = new_node;
}
}

// 从哈希表中查找元素
int search(HashTable *ht, char *key, int *value) {
int hash = hash_function(key);

HashNode *curr = ht->table[hash];
while (curr != NULL) {
if (strcmp(curr->key, key) == 0) {
*value = curr->value;
return 1; // 找到元素
}
curr = curr->next;
}

return 0; // 未找到元素
}

// 从哈希表中删除元素
void delete(HashTable *ht, char *key) {
int hash = hash_function(key);

HashNode *curr = ht->table[hash];
HashNode *prev = NULL;

while (curr != NULL) {
if (strcmp(curr->key, key) == 0) {
if (prev == NULL) {
// 删除的是链表头节点
ht->table[hash] = curr->next;
} else {
prev->next = curr->next;
}
free(curr->key);
free(curr);
return;
}
prev = curr;
curr = curr->next;
}
}

// 销毁哈希表
void destroy_hash_table(HashTable *ht) {
for (int i = 0; i < HASH_SIZE; i++) {
HashNode *curr = ht->table[i];
while (curr != NULL) {
HashNode *temp = curr;
curr = curr->next;
free(temp->key);
free(temp);
}
ht->table[i] = NULL;
}
}

// 打印哈希表
void print_hash_table(HashTable *ht) {
for (int i = 0; i < HASH_SIZE; i++) {
HashNode *curr = ht->table[i];
if (curr != NULL) {
printf("索引%d: ", i);
while (curr != NULL) {
printf("(%s, %d) ", curr->key, curr->value);
curr = curr->next;
}
printf("\\n");
}
}
}

int main() {
HashTable ht;
int value;

// 初始化哈希表
init_hash_table(&ht);

// 插入元素
insert(&ht, "apple", 10);
insert(&ht, "banana", 20);
insert(&ht, "orange", 30);
insert(&ht, "grape", 40);
insert(&ht, "watermelon", 50);

// 打印哈希表
printf("哈希表内容：\\n");
print_hash_table(&ht);

// 查找元素
if (search(&ht, "banana", &value)) {
printf("\\n查找banana: %d\\n", value);
} else {
printf("\\n未找到banana\\n");
}

// 删除元素
delete(&ht, "orange");
printf("\\n删除orange后哈希表内容：\\n");
print_hash_table(&ht);

// 更新元素
insert(&ht, "apple", 15);
printf("\\n更新apple后哈希表内容：\\n");
print_hash_table(&ht);

// 销毁哈希表
destroy_hash_table(&ht);

return 0;
}

练习题

学习建议

• 理解数据结构的基本概念和分类。
• 掌握常用数据结构的实现和操作，如线性表、栈、队列、树等。
• 学习并实现常用的查找和排序算法。
• 通过大量的练习，加深对数据结构和算法的理解。
• 在实际编程中，根据问题的特点选择合适的数据结构和算法。