C语言数据结构与算法入门：链表、栈与队列的实现

第8篇 《C语言数据结构与算法入门：链表、栈与队列的实现》

一、前言：为什么数据结构与算法是C语言的核心技能？

学习目标

• 理解数据结构的本质：组织和存储数据的方式
• 理解算法的本质：解决问题的步骤和方法
• 明确数据结构与算法的重要性：提高程序的效率和灵活性
• 掌握本章学习重点：线性数据结构的基础概念、链表的定义与实现、栈的定义与实现、队列的定义与实现、常见排序算法的实现、数据结构与算法的避坑指南、实战案例分析
• 学会使用数据结构与算法编写简单的程序

重点提示

💡 数据结构与算法是C语言的核心技能！通过数据结构，你可以组织和存储数据，提高程序的效率；通过算法，你可以解决问题，提高程序的灵活性。

二、模块1：线性数据结构的基础概念——链表、栈与队列的前导知识

2.1 学习目标

• 理解线性数据结构的特点：数据元素之间存在一对一的线性关系
• 掌握链表的基本概念：由节点组成的链式结构
• 掌握栈的基本概念：后进先出的线性结构
• 掌握队列的基本概念：先进先出的线性结构
• 避开线性数据结构使用的3大常见坑

2.2 线性数据结构的特点

• 线性表：数据元素之间存在一对一的线性关系
• 数组：连续的内存空间，支持随机访问
• 链表：由节点组成的链式结构，支持动态大小
• 栈：后进先出的线性结构
• 队列：先进先出的线性结构

代码示例1：线性数据结构的示例

#include <stdio.h>

// 定义一个数组
int arr[] = {10, 20, 30, 40, 50};

int main() {
// 数组的随机访问
for (int i = 0; i < 5; i++) {
printf("arr[%d]的值：%d\\n", i, arr[i]);
}

return 0;
}

三、模块2：链表的定义与实现——动态大小的链式结构

3.1 学习目标

• 理解链表的本质：由节点组成的链式结构
• 掌握链表的定义方法：使用struct关键字声明节点
• 掌握链表的实现方法：创建链表、插入节点、删除节点、遍历链表
• 避开链表使用的3大常见坑

3.2 链表的定义方法

语法：

struct 节点名 {
数据类型 数据;
struct 节点名 *next;
};

代码示例2：链表的实现

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

// 定义一个链表节点
struct ListNode {
int val;
struct ListNode *next;
};

// 创建链表
struct ListNode *create_list() {
return NULL;
}

// 插入节点
struct ListNode *insert_node(struct ListNode *head, int val) {
struct ListNode *new_node = (struct ListNode *)malloc(sizeof(struct ListNode));
new_node->val = val;
new_node->next = head;

return new_node;
}

// 删除节点
struct ListNode *delete_node(struct ListNode *head, int val) {
struct ListNode *current = head;
struct ListNode *prev = NULL;

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

if (current == NULL) {
return head;
}

if (prev == NULL) {
head = current->next;
} else {
prev->next = current->next;
}

free(current);

return head;
}

// 遍历链表
void print_list(struct ListNode *head) {
struct ListNode *current = head;

while (current != NULL) {
printf("%d ", current->val);
current = current->next;
}
printf("\\n");
}

int main() {
struct ListNode *head = create_list();

// 插入节点
head = insert_node(head, 10);
head = insert_node(head, 20);
head = insert_node(head, 30);
head = insert_node(head, 40);
head = insert_node(head, 50);

// 打印链表
printf("插入节点后的链表：");
print_list(head);

// 删除节点
head = delete_node(head, 30);

// 打印链表
printf("删除节点后的链表：");
print_list(head);

return 0;
}

四、模块3：栈的定义与实现——后进先出的线性结构

4.1 学习目标

• 理解栈的本质：后进先出的线性结构
• 掌握栈的定义方法：使用数组或链表实现
• 掌握栈的实现方法：入栈、出栈、获取栈顶元素、判断栈是否为空
• 避开栈使用的3大常见坑

4.2 栈的实现方法

代码示例3：使用数组实现栈

#include <stdio.h>
#define MAX_SIZE 100

// 定义一个栈
struct Stack {
int data[MAX_SIZE];
int top;
};

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

// 判断栈是否为空
int is_empty(struct Stack *stack) {
return stack->top == –1;
}

// 判断栈是否已满
int is_full(struct Stack *stack) {
return stack->top == MAX_SIZE – 1;
}

// 入栈
void push(struct Stack *stack, int val) {
if (is_full(stack)) {
printf("栈已满，无法入栈！\\n");
return;
}

stack->top++;
stack->data[stack->top] = val;
}

// 出栈
int pop(struct Stack *stack) {
if (is_empty(stack)) {
printf("栈为空，无法出栈！\\n");
return –1;
}

int val = stack->data[stack->top];
stack->top—;

return val;
}

// 获取栈顶元素
int get_top(struct Stack *stack) {
if (is_empty(stack)) {
printf("栈为空，无法获取栈顶元素！\\n");
return –1;
}

return stack->data[stack->top];
}

// 打印栈
void print_stack(struct Stack *stack) {
if (is_empty(stack)) {
printf("栈为空！\\n");
return;
}

printf("栈的元素：");
for (int i = 0; i <= stack->top; i++) {
printf("%d ", stack->data[i]);
}
printf("\\n");
}

int main() {
struct Stack stack;

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

// 入栈
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
push(&stack, 40);
push(&stack, 50);

// 打印栈
print_stack(&stack);

// 出栈
int val = pop(&stack);
printf("出栈的元素：%d\\n", val);

// 打印栈
print_stack(&stack);

// 获取栈顶元素
val = get_top(&stack);
printf("栈顶元素：%d\\n", val);

return 0;
}

五、模块4：队列的定义与实现——先进先出的线性结构

5.1 学习目标

• 理解队列的本质：先进先出的线性结构
• 掌握队列的定义方法：使用数组或链表实现
• 掌握队列的实现方法：入队、出队、获取队头元素、判断队列是否为空
• 避开队列使用的3大常见坑

5.2 队列的实现方法

代码示例4：使用数组实现队列

#include <stdio.h>
#define MAX_SIZE 100

// 定义一个队列
struct Queue {
int data[MAX_SIZE];
int front;
int rear;
};

// 初始化队列
void init_queue(struct Queue *queue) {
queue->front = 0;
queue->rear = –1;
}

// 判断队列是否为空
int is_empty(struct Queue *queue) {
return queue->front > queue->rear;
}

// 判断队列是否已满
int is_full(struct Queue *queue) {
return queue->rear == MAX_SIZE – 1;
}

// 入队
void enqueue(struct Queue *queue, int val) {
if (is_full(queue)) {
printf("队列已满，无法入队！\\n");
return;
}

queue->rear++;
queue->data[queue->rear] = val;
}

// 出队
int dequeue(struct Queue *queue) {
if (is_empty(queue)) {
printf("队列为空，无法出队！\\n");
return –1;
}

int val = queue->data[queue->front];
queue->front++;

return val;
}

// 获取队头元素
int get_front(struct Queue *queue) {
if (is_empty(queue)) {
printf("队列为空，无法获取队头元素！\\n");
return –1;
}

return queue->data[queue->front];
}

// 打印队列
void print_queue(struct Queue *queue) {
if (is_empty(queue)) {
printf("队列为空！\\n");
return;
}

printf("队列的元素：");
for (int i = queue->front; i <= queue->rear; i++) {
printf("%d ", queue->data[i]);
}
printf("\\n");
}

int main() {
struct Queue queue;

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

// 入队
enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
enqueue(&queue, 40);
enqueue(&queue, 50);

// 打印队列
print_queue(&queue);

// 出队
int val = dequeue(&queue);
printf("出队的元素：%d\\n", val);

// 打印队列
print_queue(&queue);

// 获取队头元素
val = get_front(&queue);
printf("队头元素：%d\\n", val);

return 0;
}

六、模块5：常见排序算法的实现——冒泡排序、插入排序、选择排序

6.1 学习目标

• 理解排序算法的本质：将一组数据按照特定顺序排列
• 掌握冒泡排序的实现方法：通过交换相邻元素排序
• 掌握插入排序的实现方法：通过插入元素排序
• 掌握选择排序的实现方法：通过选择最小元素排序
• 避开排序算法使用的3大常见坑

6.2 冒泡排序的实现方法

代码示例5：冒泡排序

#include <stdio.h>

void bubble_sort(int arr[], int size) {
for (int i = 0; i < size – 1; i++) {
for (int j = 0; j < size – i – 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

int main() {
int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int size = sizeof(arr) / sizeof(arr[0]);

bubble_sort(arr, size);

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

return 0;
}

七、模块6：数据结构与算法的避坑指南——避免常见问题

7.1 学习目标

• 理解数据结构与算法的常见问题：语法错误、逻辑错误、内存泄漏、栈溢出、队列溢出
• 掌握避免语法错误的方法：使用编译器检查代码
• 掌握避免逻辑错误的方法：使用调试工具定位和修复问题
• 掌握避免内存泄漏的方法：在使用完内存后，使用free()函数释放内存
• 掌握避免栈溢出的方法：确保栈的大小足够
• 掌握避免队列溢出的方法：确保队列的大小足够
• 避开数据结构与算法使用的3大常见坑

7.2 常见问题

7.2.1 内存泄漏

问题：未正确释放内存，导致程序占用过多内存

解决方法：

• 正确使用动态内存分配函数
• 在使用完内存后，使用free()函数释放内存
• 避免重复分配内存

7.2.2 栈溢出

问题：栈的大小不够，导致程序崩溃

解决方法：

• 确保栈的大小足够
• 避免递归调用过深
• 使用动态内存分配代替栈内存

7.2.3 队列溢出

问题：队列的大小不够，导致程序崩溃

解决方法：

• 确保队列的大小足够
• 使用动态内存分配代替队列内存

八、模块7：实战案例分析——使用数据结构与算法解决实际问题

8.1 学习目标

• 掌握使用数据结构与算法实现计算器：使用栈实现后缀表达式的计算
• 掌握使用数据结构与算法实现迷宫求解：使用队列实现广度优先搜索
• 学会使用数据结构与算法解决实际问题
• 避开实战案例使用的3大常见坑

8.2 使用数据结构与算法实现计算器

代码示例6：使用栈实现计算器

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

#define MAX_SIZE 100

struct Stack {
int data[MAX_SIZE];
int top;
};

void init_stack(struct Stack *stack) {
stack->top = –1;
}

int is_empty(struct Stack *stack) {
return stack->top == –1;
}

int is_full(struct Stack *stack) {
return stack->top == MAX_SIZE – 1;
}

void push(struct Stack *stack, int val) {
if (is_full(stack)) {
printf("栈已满，无法入栈！\\n");
return;
}

stack->top++;
stack->data[stack->top] = val;
}

int pop(struct Stack *stack) {
if (is_empty(stack)) {
printf("栈为空，无法出栈！\\n");
return –1;
}

int val = stack->data[stack->top];
stack->top—;

return val;
}

int get_top(struct Stack *stack) {
if (is_empty(stack)) {
printf("栈为空，无法获取栈顶元素！\\n");
return –1;
}

return stack->data[stack->top];
}

int evaluate_postfix(char *postfix) {
struct Stack stack;
init_stack(&stack);

int i = 0;
while (postfix[i] != '\\0') {
if (isdigit(postfix[i])) {
int val = 0;
while (isdigit(postfix[i])) {
val = val * 10 + (postfix[i] – '0');
i++;
}
push(&stack, val);
} else if (postfix[i] == ' ') {
i++;
} else {
int b = pop(&stack);
int a = pop(&stack);
int result;

switch (postfix[i]) {
case '+':
result = a + b;
break;
case '-':
result = a – b;
break;
case '*':
result = a * b;
break;
case '/':
if (b == 0) {
printf("错误：除以零！\\n");
return –1;
}
result = a / b;
break;
default:
printf("错误：未知操作符！\\n");
return –1;
}

push(&stack, result);
i++;
}
}

return pop(&stack);
}

int main() {
char postfix[MAX_SIZE];

printf("请输入后缀表达式：");
scanf("%[^\\n]", postfix);

int result = evaluate_postfix(postfix);
printf("结果：%d\\n", result);

return 0;
}

九、本章总结与课后练习

9.1 总结

✅ 线性数据结构的基础概念：数据元素之间存在一对一的线性关系，包括链表、栈与队列
✅ 链表的定义与实现：由节点组成的链式结构，支持动态大小，实现创建、插入、删除、遍历
✅ 栈的定义与实现：后进先出的线性结构，使用数组或链表实现，实现入栈、出栈、获取栈顶元素
✅ 队列的定义与实现：先进先出的线性结构，使用数组或链表实现，实现入队、出队、获取队头元素
✅ 常见排序算法的实现：冒泡排序、插入排序、选择排序，通过交换、插入、选择元素排序
✅ 数据结构与算法的避坑指南：避免语法错误、逻辑错误、内存泄漏、栈溢出、队列溢出
✅ 实战案例分析：使用数据结构与算法实现计算器、迷宫求解

9.2 课后练习