数据结构入门指南：线性结构与C语言实现

3.2 链表（链式存储线性结构）

3.2.1 核心特性

离散内存存储，通过指针连接节点，插入/删除元素无需移动数据（仅修改指针），效率O(1)，但不支持随机访问（需从头遍历，效率O(n)），适合元素数量动态变化、插入删除频繁的场景（如Linux进程链表）。

3.2.2 C语言实现（单链表）

单链表是最基础的链表类型，每个节点包含数据域和指向下一节点的指针：

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

// 链表节点结构体
typedef struct LinkNode {
    int node_data; // 数据域
    struct LinkNode* next; // 指针域，指向后续节点
} LinkNode;

// 创建新节点
LinkNode* create_link_node(int data_value) {
    LinkNode* new_node = (LinkNode*)malloc(sizeof(LinkNode));
    new_node->node_data = data_value;
    new_node->next = NULL;
    return new_node;
}

// 头部插入节点（效率O(1)）
void insert_node_head(LinkNode** head_node, int data_value) {
    LinkNode* new_node = create_link_node(data_value);
    new_node->next = *head_node;
    *head_node = new_node;
}

// 遍历链表
void traverse_link_list(LinkNode* head_node) {
    LinkNode* current_node = head_node;
    while (current_node != NULL) {
        printf("%d ", current_node->node_data);
        current_node = current_node->next;
    }
    printf("\n");
}

// 释放链表内存
void free_link_list(LinkNode* head_node) {
    LinkNode* temp_node;
    while (head_node != NULL) {
        temp_node = head_node;
        head_node = head_node->next;
        free(temp_node);
    }
}

int main() {
    LinkNode* head_node = NULL; // 链表头节点初始化
    insert_node_head(&head_node, 30);
    insert_node_head(&head_node, 20);
    insert_node_head(&head_node, 10);
    printf("链表遍历结果：");
    traverse_link_list(head_node); // 输出：10 20 30
    free_link_list(head_node);
    return 0;
}

3.3 栈（先进后出LIFO结构）

3.3.1 核心特性

受限线性结构，仅允许在一端（栈顶）插入/删除元素，另一端（栈底）固定，符合'先进后出'规则，常用顺序存储（数组）实现，效率O(1)，应用场景如函数调用栈、括号匹配、表达式求值。

3.3.2 C语言实现（顺序栈）

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100 // 栈最大容量

// 顺序栈结构体
typedef struct {
    int stack_data[MAX_STACK_SIZE]; // 存储栈元素
    int stack_top; // 栈顶指针（-1 表示空栈）
} SequenceStack;

// 初始化栈
void init_sequence_stack(SequenceStack* sequence_stack) {
    sequence_stack->stack_top = -1;
}

// 判断栈空
int is_stack_empty(SequenceStack* sequence_stack) {
    return sequence_stack->stack_top == -1;
}

// 入栈
void push_stack_element(SequenceStack* sequence_stack, int element_value) {
    if (sequence_stack->stack_top == MAX_STACK_SIZE - 1) {
        printf("栈满，无法入栈\n");
        return;
    }
    sequence_stack->stack_data[++sequence_stack->stack_top] = element_value;
}

// 出栈
int pop_stack_element(SequenceStack* sequence_stack) {
    if (is_stack_empty(sequence_stack)) {
        printf("栈空，无法出栈\n");
        exit(1); // 异常退出
    }
    return sequence_stack->stack_data[sequence_stack->stack_top--];
}

int main() {
    SequenceStack sequence_stack;
    init_sequence_stack(&sequence_stack);
    push_stack_element(&sequence_stack, 10);
    push_stack_element(&sequence_stack, 20);
    push_stack_element(&sequence_stack, 30);
    printf("出栈元素：%d\n", pop_stack_element(&sequence_stack)); // 30
    printf("出栈元素：%d\n", pop_stack_element(&sequence_stack)); // 20
    return 0;
}

3.4 队列（先进先出FIFO结构）

3.4.1 核心特性

受限线性结构，允许在一端（队尾）插入元素，另一端（队头）删除元素，符合'先进先出'规则，常用链式存储实现（避免顺序存储的假溢出），应用场景如任务调度、外设数据缓冲、消息队列。

3.4.2 C语言实现（链式队列）

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

// 队列节点结构体
typedef struct QueueNode {
    int node_data;
    struct QueueNode* next;
} QueueNode;

// 队列结构体（记录队头和队尾）
typedef struct {
    QueueNode* queue_front; // 队头
    QueueNode* queue_rear; // 队尾
} LinkQueue;

// 初始化队列
void init_link_queue(LinkQueue* link_queue) {
    link_queue->queue_front = link_queue->queue_rear = (QueueNode*)malloc(sizeof(QueueNode));
    link_queue->queue_front->next = NULL;
}

// 判断队列空
int is_queue_empty(LinkQueue* link_queue) {
    return link_queue->queue_front == link_queue->queue_rear;
}

// 入队
void enqueue_element(LinkQueue* link_queue, int element_value) {
    QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
    new_node->node_data = element_value;
    new_node->next = NULL;
    link_queue->queue_rear->next = new_node;
    link_queue->queue_rear = new_node;
}

// 出队
int dequeue_element(LinkQueue* link_queue) {
    if (is_queue_empty(link_queue)) {
        printf("队列空，无法出队\n");
        exit(1);
    }
    QueueNode* temp_node = link_queue->queue_front->next;
    int element_value = temp_node->node_data;
    link_queue->queue_front->next = temp_node->next;
    // 队尾与队头重合时，更新队尾
    if (link_queue->queue_rear == temp_node) {
        link_queue->queue_rear = link_queue->queue_front;
    }
    free(temp_node);
    return element_value;
}

int main() {
    LinkQueue link_queue;
    init_link_queue(&link_queue);
    enqueue_element(&link_queue, 10);
    enqueue_element(&link_queue, 20);
    enqueue_element(&link_queue, 30);
    printf("出队元素：%d\n", dequeue_element(&link_queue)); // 10
    printf("出队元素：%d\n", dequeue_element(&link_queue)); // 20
    return 0;
}

四、经典实战案例：括号匹配（栈的应用）

以面试高频题'括号匹配'为例，演示栈的实际应用，判断输入字符串中的括号（()、[]、{}）是否成对闭合：

#include <stdio.h>
#include <string.h>
#define MAX_STACK_SIZE 100

typedef struct {
    char stack_data[MAX_STACK_SIZE];
    int stack_top;
} BracketStack;

void init_bracket_stack(BracketStack* bracket_stack) {
    bracket_stack->stack_top = -1;
}

void push_bracket(BracketStack* bracket_stack, char bracket_char) {
    bracket_stack->stack_data[++bracket_stack->stack_top] = bracket_char;
}

char pop_bracket(BracketStack* bracket_stack) {
    return bracket_stack->stack_data[bracket_stack->stack_top--];
}

// 判断括号匹配
int is_bracket_matched(char* input_string) {
    BracketStack bracket_stack;
    init_bracket_stack(&bracket_stack);
    int string_length = strlen(input_string);
    for (int i = 0; i < string_length; i++) {
        char current_char = input_string[i];
        // 左括号入栈
        if (current_char == '(' || current_char == '[' || current_char == '{') {
            push_bracket(&bracket_stack, current_char);
        } else {
            // 右括号无对应左括号，匹配失败
            if (bracket_stack.stack_top == -1) return 0;
            char top_bracket = pop_bracket(&bracket_stack);
            // 检查括号是否成对
            if ((current_char == ')' && top_bracket != '(') ||
                (current_char == ']' && top_bracket != '[') ||
                (current_char == '}' && top_bracket != '{')) {
                return 0;
            }
        }
    }
    // 栈空说明所有括号都匹配
    return bracket_stack.stack_top == -1;
}

int main() {
    char input_string[100];
    printf("请输入包含括号的字符串：");
    scanf("%s", input_string);
    if (is_bracket_matched(input_string)) {
        printf("括号匹配成功\n");
    } else {
        printf("括号匹配失败\n");
    }
    return 0;
}

五、入门常见问题与避坑指南

• 链表空指针问题：遍历或操作链表时，需先判断节点指针是否为NULL，避免野指针访问（如链表尾节点next必须置空）。
• 栈/队列边界判断：入栈前检查栈满，出栈前检查栈空；队列同理，避免越界访问或空操作。
• 内存泄漏：链式结构（链表、链式队列）的节点需手动free，避免长期运行导致内存耗尽，建议封装专门的释放函数。
• 顺序存储假溢出：顺序队列若仅移动指针，会出现'队尾满但队头有空余'的假溢出，可通过循环队列优化。

六、进阶学习路线（贴合底层开发）

掌握线性结构后，可按以下路线深化，适配Linux系统编程与嵌入式开发需求：

1. 复杂线性结构：双向链表、循环链表（Linux内核常用）、循环队列、优先级队列（堆实现）。
2. 非线性结构：树（二叉树、红黑树）、图，重点掌握二叉树的遍历（前中后序）与红黑树在Linux内核中的应用。
3. 算法结合：学习基于数据结构的排序（链表排序、堆排序）、搜索（二叉树查找）算法，优化时间复杂度。
4. 实战落地：在嵌入式开发中用队列缓冲串口数据，用链表管理传感器节点，复刻Linux内核简单链表逻辑。

总结

数据结构入门的关键是'理解特性 + 多实战'，线性结构虽简单，但需明确不同结构的适用场景——数组适合查询，链表适合增删，栈/队列适合特定顺序需求。本文实现的代码均为核心逻辑，可直接用于课程作业或小型项目，建议手动敲写并调试，理解指针操作与内存管理的细节。

后续学习中，需结合Linux内核源码、嵌入式项目案例，体会数据结构在底层开发中的优化作用，逐步建立'数据结构决定程序性能'的思维，为复杂项目开发筑牢基础。