datastruct

C语言数据结构实现详解：链表、栈、队列

数据结构是程序设计的基础，掌握基本数据结构的C语言实现对于理解算法和提高编程能力至关重要。本文将详细介绍链表、栈、队列这三种基础数据结构的C语言实现。

1. 链表（Linked List）

1.1 单向链表

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

// 链表结构
typedef struct {
    ListNode *head;
    size_t size;
} LinkedList;

// 创建新节点
ListNode* create_node(int data) {
    ListNode *node = (ListNode*)malloc(sizeof(ListNode));
    if (!node) {
        fprintf(stderr, "内存分配失败\n");
        return NULL;
    }
    node->data = data;
    node->next = NULL;
    return node;
}

// 初始化链表
LinkedList* list_init() {
    LinkedList *list = (LinkedList*)malloc(sizeof(LinkedList));
    if (!list) {
        fprintf(stderr, "内存分配失败\n");
        return NULL;
    }
    list->head = NULL;
    list->size = 0;
    return list;
}

// 在头部插入节点
int list_insert_head(LinkedList *list, int data) {
    if (!list) return -1;
    
    ListNode *new_node = create_node(data);
    if (!new_node) return -1;
    
    new_node->next = list->head;
    list->head = new_node;
    list->size++;
    return 0;
}

// 在尾部插入节点
int list_insert_tail(LinkedList *list, int data) {
    if (!list) return -1;
    
    ListNode *new_node = create_node(data);
    if (!new_node) return -1;
    
    if (!list->head) {
        list->head = new_node;
    } else {
        ListNode *current = list->head;
        while (current->next) {
            current = current->next;
        }
        current->next = new_node;
    }
    list->size++;
    return 0;
}

// 在指定位置插入节点
int list_insert_at(LinkedList *list, int index, int data) {
    if (!list || index < 0 || index > list->size) return -1;
    
    if (index == 0) {
        return list_insert_head(list, data);
    }
    
    ListNode *new_node = create_node(data);
    if (!new_node) return -1;
    
    ListNode *current = list->head;
    for (int i = 0; i < index - 1; i++) {
        current = current->next;
    }
    
    new_node->next = current->next;
    current->next = new_node;
    list->size++;
    return 0;
}

// 删除头节点
int list_delete_head(LinkedList *list) {
    if (!list || !list->head) return -1;
    
    ListNode *temp = list->head;
    list->head = list->head->next;
    free(temp);
    list->size--;
    return 0;
}

// 删除指定值的节点
int list_delete_value(LinkedList *list, int data) {
    if (!list || !list->head) return -1;
    
    // 如果头节点就是要删除的节点
    if (list->head->data == data) {
        return list_delete_head(list);
    }
    
    ListNode *current = list->head;
    while (current->next && current->next->data != data) {
        current = current->next;
    }
    
    if (current->next) {
        ListNode *temp = current->next;
        current->next = temp->next;
        free(temp);
        list->size--;
        return 0;
    }
    
    return -1;  // 未找到
}

// 查找节点
ListNode* list_find(LinkedList *list, int data) {
    if (!list) return NULL;
    
    ListNode *current = list->head;
    while (current) {
        if (current->data == data) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

// 反转链表
void list_reverse(LinkedList *list) {
    if (!list || !list->head) return;
    
    ListNode *prev = NULL;
    ListNode *current = list->head;
    ListNode *next = NULL;
    
    while (current) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    
    list->head = prev;
}

// 打印链表
void list_print(LinkedList *list) {
    if (!list) return;
    
    printf("链表内容: ");
    ListNode *current = list->head;
    while (current) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("(大小: %zu)\n", list->size);
}

// 销毁链表
void list_destroy(LinkedList *list) {
    if (!list) return;
    
    ListNode *current = list->head;
    while (current) {
        ListNode *temp = current;
        current = current->next;
        free(temp);
    }
    free(list);
}

1.2 双向链表

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// 双向链表节点结构
typedef struct DoublyListNode {
    int data;
    struct DoublyListNode *prev;
    struct DoublyListNode *next;
} DoublyListNode;

// 双向链表结构
typedef struct {
    DoublyListNode *head;
    DoublyListNode *tail;
    size_t size;
} DoublyLinkedList;

// 创建双向链表节点
DoublyListNode* create_doubly_node(int data) {
    DoublyListNode *node = (DoublyListNode*)malloc(sizeof(DoublyListNode));
    if (!node) return NULL;
    
    node->data = data;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

// 初始化双向链表
DoublyLinkedList* doubly_list_init() {
    DoublyLinkedList *list = (DoublyLinkedList*)malloc(sizeof(DoublyLinkedList));
    if (!list) return NULL;
    
    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
    return list;
}

// 在头部插入
int doubly_list_insert_head(DoublyLinkedList *list, int data) {
    if (!list) return -1;
    
    DoublyListNode *new_node = create_doubly_node(data);
    if (!new_node) return -1;
    
    if (!list->head) {
        list->head = list->tail = new_node;
    } else {
        new_node->next = list->head;
        list->head->prev = new_node;
        list->head = new_node;
    }
    
    list->size++;
    return 0;
}

// 在尾部插入
int doubly_list_insert_tail(DoublyLinkedList *list, int data) {
    if (!list) return -1;
    
    DoublyListNode *new_node = create_doubly_node(data);
    if (!new_node) return -1;
    
    if (!list->tail) {
        list->head = list->tail = new_node;
    } else {
        new_node->prev = list->tail;
        list->tail->next = new_node;
        list->tail = new_node;
    }
    
    list->size++;
    return 0;
}

// 删除节点
int doubly_list_delete_node(DoublyLinkedList *list, DoublyListNode *node) {
    if (!list || !node) return -1;
    
    if (node->prev) {
        node->prev->next = node->next;
    } else {
        list->head = node->next;
    }
    
    if (node->next) {
        node->next->prev = node->prev;
    } else {
        list->tail = node->prev;
    }
    
    free(node);
    list->size--;
    return 0;
}

2. 栈（Stack）

2.1 基于数组的栈实现

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define STACK_INITIAL_CAPACITY 16

// 栈结构
typedef struct {
    int *data;
    size_t capacity;
    size_t top;
} Stack;

// 初始化栈
Stack* stack_init() {
    Stack *stack = (Stack*)malloc(sizeof(Stack));
    if (!stack) return NULL;
    
    stack->data = (int*)malloc(STACK_INITIAL_CAPACITY * sizeof(int));
    if (!stack->data) {
        free(stack);
        return NULL;
    }
    
    stack->capacity = STACK_INITIAL_CAPACITY;
    stack->top = 0;
    return stack;
}

// 检查栈是否为空
bool stack_is_empty(Stack *stack) {
    return stack && stack->top == 0;
}

// 检查栈是否已满
bool stack_is_full(Stack *stack) {
    return stack && stack->top == stack->capacity;
}

// 扩容栈
int stack_resize(Stack *stack) {
    if (!stack) return -1;
    
    size_t new_capacity = stack->capacity * 2;
    int *new_data = (int*)realloc(stack->data, new_capacity * sizeof(int));
    if (!new_data) return -1;
    
    stack->data = new_data;
    stack->capacity = new_capacity;
    return 0;
}

// 入栈
int stack_push(Stack *stack, int data) {
    if (!stack) return -1;
    
    if (stack_is_full(stack)) {
        if (stack_resize(stack) != 0) {
            return -1;
        }
    }
    
    stack->data[stack->top++] = data;
    return 0;
}

// 出栈
int stack_pop(Stack *stack, int *data) {
    if (!stack || stack_is_empty(stack)) return -1;
    
    if (data) {
        *data = stack->data[--stack->top];
    } else {
        stack->top--;
    }
    return 0;
}

// 查看栈顶元素
int stack_peek(Stack *stack, int *data) {
    if (!stack || stack_is_empty(stack) || !data) return -1;
    
    *data = stack->data[stack->top - 1];
    return 0;
}

// 获取栈大小
size_t stack_size(Stack *stack) {
    return stack ? stack->top : 0;
}

// 打印栈内容
void stack_print(Stack *stack) {
    if (!stack) return;
    
    printf("栈内容 (栈顶到栈底): ");
    for (int i = stack->top - 1; i >= 0; i--) {
        printf("%d ", stack->data[i]);
    }
    printf("(大小: %zu)\n", stack->top);
}

// 销毁栈
void stack_destroy(Stack *stack) {
    if (stack) {
        free(stack->data);
        free(stack);
    }
}

2.2 基于链表的栈实现

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
60
61
62
// 基于链表的栈节点
typedef struct StackNode {
    int data;
    struct StackNode *next;
} StackNode;

// 链表栈结构
typedef struct {
    StackNode *top;
    size_t size;
} LinkedStack;

// 初始化链表栈
LinkedStack* linked_stack_init() {
    LinkedStack *stack = (LinkedStack*)malloc(sizeof(LinkedStack));
    if (!stack) return NULL;
    
    stack->top = NULL;
    stack->size = 0;
    return stack;
}

// 入栈
int linked_stack_push(LinkedStack *stack, int data) {
    if (!stack) return -1;
    
    StackNode *new_node = (StackNode*)malloc(sizeof(StackNode));
    if (!new_node) return -1;
    
    new_node->data = data;
    new_node->next = stack->top;
    stack->top = new_node;
    stack->size++;
    return 0;
}

// 出栈
int linked_stack_pop(LinkedStack *stack, int *data) {
    if (!stack || !stack->top) return -1;
    
    StackNode *temp = stack->top;
    if (data) {
        *data = temp->data;
    }
    
    stack->top = temp->next;
    free(temp);
    stack->size--;
    return 0;
}

// 销毁链表栈
void linked_stack_destroy(LinkedStack *stack) {
    if (!stack) return;
    
    while (stack->top) {
        StackNode *temp = stack->top;
        stack->top = temp->next;
        free(temp);
    }
    free(stack);
}

2.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
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// 括号匹配检查
bool check_parentheses(const char *expr) {
    Stack *stack = stack_init();
    if (!stack) return false;
    
    for (int i = 0; expr[i]; i++) {
        char ch = expr[i];
        
        if (ch == '(' || ch == '[' || ch == '{') {
            stack_push(stack, ch);
        } else if (ch == ')' || ch == ']' || ch == '}') {
            if (stack_is_empty(stack)) {
                stack_destroy(stack);
                return false;
            }
            
            int top;
            stack_pop(stack, &top);
            
            if ((ch == ')' && top != '(') ||
                (ch == ']' && top != '[') ||
                (ch == '}' && top != '{')) {
                stack_destroy(stack);
                return false;
            }
        }
    }
    
    bool result = stack_is_empty(stack);
    stack_destroy(stack);
    return result;
}

// 中缀表达式转后缀表达式
void infix_to_postfix(const char *infix, char *postfix) {
    Stack *stack = stack_init();
    int j = 0;
    
    for (int i = 0; infix[i]; i++) {
        char ch = infix[i];
        
        if (isalnum(ch)) {
            postfix[j++] = ch;
        } else if (ch == '(') {
            stack_push(stack, ch);
        } else if (ch == ')') {
            int top;
            while (!stack_is_empty(stack) && 
                   stack_peek(stack, &top) == 0 && top != '(') {
                stack_pop(stack, &top);
                postfix[j++] = top;
            }
            stack_pop(stack, NULL);  // 弹出 '('
        } else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
            int top;
            while (!stack_is_empty(stack) && 
                   stack_peek(stack, &top) == 0 && 
                   precedence(top) >= precedence(ch)) {
                stack_pop(stack, &top);
                postfix[j++] = top;
            }
            stack_push(stack, ch);
        }
    }
    
    int top;
    while (!stack_is_empty(stack)) {
        stack_pop(stack, &top);
        postfix[j++] = top;
    }
    
    postfix[j] = '\0';
    stack_destroy(stack);
}

// 运算符优先级
int precedence(char op) {
    switch (op) {
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        default: return 0;
    }
}

3. 队列（Queue）

3.1 基于数组的循环队列

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define QUEUE_INITIAL_CAPACITY 16

// 循环队列结构
typedef struct {
    int *data;
    size_t capacity;
    size_t front;
    size_t rear;
    size_t size;
} CircularQueue;

// 初始化队列
CircularQueue* queue_init() {
    CircularQueue *queue = (CircularQueue*)malloc(sizeof(CircularQueue));
    if (!queue) return NULL;
    
    queue->data = (int*)malloc(QUEUE_INITIAL_CAPACITY * sizeof(int));
    if (!queue->data) {
        free(queue);
        return NULL;
    }
    
    queue->capacity = QUEUE_INITIAL_CAPACITY;
    queue->front = 0;
    queue->rear = 0;
    queue->size = 0;
    return queue;
}

// 检查队列是否为空
bool queue_is_empty(CircularQueue *queue) {
    return queue && queue->size == 0;
}

// 检查队列是否已满
bool queue_is_full(CircularQueue *queue) {
    return queue && queue->size == queue->capacity;
}

// 扩容队列
int queue_resize(CircularQueue *queue) {
    if (!queue) return -1;
    
    size_t new_capacity = queue->capacity * 2;
    int *new_data = (int*)malloc(new_capacity * sizeof(int));
    if (!new_data) return -1;
    
    // 重新排列数据
    for (size_t i = 0; i < queue->size; i++) {
        new_data[i] = queue->data[(queue->front + i) % queue->capacity];
    }
    
    free(queue->data);
    queue->data = new_data;
    queue->capacity = new_capacity;
    queue->front = 0;
    queue->rear = queue->size;
    
    return 0;
}

// 入队
int queue_enqueue(CircularQueue *queue, int data) {
    if (!queue) return -1;
    
    if (queue_is_full(queue)) {
        if (queue_resize(queue) != 0) {
            return -1;
        }
    }
    
    queue->data[queue->rear] = data;
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->size++;
    return 0;
}

// 出队
int queue_dequeue(CircularQueue *queue, int *data) {
    if (!queue || queue_is_empty(queue)) return -1;
    
    if (data) {
        *data = queue->data[queue->front];
    }
    
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size--;
    return 0;
}

// 查看队首元素
int queue_front(CircularQueue *queue, int *data) {
    if (!queue || queue_is_empty(queue) || !data) return -1;
    
    *data = queue->data[queue->front];
    return 0;
}

// 获取队列大小
size_t queue_size(CircularQueue *queue) {
    return queue ? queue->size : 0;
}

// 打印队列内容
void queue_print(CircularQueue *queue) {
    if (!queue) return;
    
    printf("队列内容 (队首到队尾): ");
    for (size_t i = 0; i < queue->size; i++) {
        printf("%d ", queue->data[(queue->front + i) % queue->capacity]);
    }
    printf("(大小: %zu)\n", queue->size);
}

// 销毁队列
void queue_destroy(CircularQueue *queue) {
    if (queue) {
        free(queue->data);
        free(queue);
    }
}

3.2 基于链表的队列

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// 队列节点
typedef struct QueueNode {
    int data;
    struct QueueNode *next;
} QueueNode;

// 链表队列结构
typedef struct {
    QueueNode *front;
    QueueNode *rear;
    size_t size;
} LinkedQueue;

// 初始化链表队列
LinkedQueue* linked_queue_init() {
    LinkedQueue *queue = (LinkedQueue*)malloc(sizeof(LinkedQueue));
    if (!queue) return NULL;
    
    queue->front = NULL;
    queue->rear = NULL;
    queue->size = 0;
    return queue;
}

// 入队
int linked_queue_enqueue(LinkedQueue *queue, int data) {
    if (!queue) return -1;
    
    QueueNode *new_node = (QueueNode*)malloc(sizeof(QueueNode));
    if (!new_node) return -1;
    
    new_node->data = data;
    new_node->next = NULL;
    
    if (!queue->rear) {
        queue->front = queue->rear = new_node;
    } else {
        queue->rear->next = new_node;
        queue->rear = new_node;
    }
    
    queue->size++;
    return 0;
}

// 出队
int linked_queue_dequeue(LinkedQueue *queue, int *data) {
    if (!queue || !queue->front) return -1;
    
    QueueNode *temp = queue->front;
    if (data) {
        *data = temp->data;
    }
    
    queue->front = temp->next;
    if (!queue->front) {
        queue->rear = NULL;
    }
    
    free(temp);
    queue->size--;
    return 0;
}

// 销毁链表队列
void linked_queue_destroy(LinkedQueue *queue) {
    if (!queue) return;
    
    while (queue->front) {
        QueueNode *temp = queue->front;
        queue->front = temp->next;
        free(temp);
    }
    free(queue);
}

3.3 双端队列（Deque）

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
// 双端队列节点
typedef struct DequeNode {
    int data;
    struct DequeNode *prev;
    struct DequeNode *next;
} DequeNode;

// 双端队列结构
typedef struct {
    DequeNode *front;
    DequeNode *rear;
    size_t size;
} Deque;

// 初始化双端队列
Deque* deque_init() {
    Deque *deque = (Deque*)malloc(sizeof(Deque));
    if (!deque) return NULL;
    
    deque->front = NULL;
    deque->rear = NULL;
    deque->size = 0;
    return deque;
}

// 从前端插入
int deque_push_front(Deque *deque, int data) {
    if (!deque) return -1;
    
    DequeNode *new_node = (DequeNode*)malloc(sizeof(DequeNode));
    if (!new_node) return -1;
    
    new_node->data = data;
    new_node->prev = NULL;
    new_node->next = deque->front;
    
    if (deque->front) {
        deque->front->prev = new_node;
    } else {
        deque->rear = new_node;
    }
    
    deque->front = new_node;
    deque->size++;
    return 0;
}

// 从后端插入
int deque_push_rear(Deque *deque, int data) {
    if (!deque) return -1;
    
    DequeNode *new_node = (DequeNode*)malloc(sizeof(DequeNode));
    if (!new_node) return -1;
    
    new_node->data = data;
    new_node->prev = deque->rear;
    new_node->next = NULL;
    
    if (deque->rear) {
        deque->rear->next = new_node;
    } else {
        deque->front = new_node;
    }
    
    deque->rear = new_node;
    deque->size++;
    return 0;
}

// 从前端删除
int deque_pop_front(Deque *deque, int *data) {
    if (!deque || !deque->front) return -1;
    
    DequeNode *temp = deque->front;
    if (data) {
        *data = temp->data;
    }
    
    deque->front = temp->next;
    if (deque->front) {
        deque->front->prev = NULL;
    } else {
        deque->rear = NULL;
    }
    
    free(temp);
    deque->size--;
    return 0;
}

// 从后端删除
int deque_pop_rear(Deque *deque, int *data) {
    if (!deque || !deque->rear) return -1;
    
    DequeNode *temp = deque->rear;
    if (data) {
        *data = temp->data;
    }
    
    deque->rear = temp->prev;
    if (deque->rear) {
        deque->rear->next = NULL;
    } else {
        deque->front = NULL;
    }
    
    free(temp);
    deque->size--;
    return 0;
}

4. 应用示例和性能分析

4.1 综合应用示例

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
// 使用栈实现函数调用跟踪
typedef struct {
    char function_name[64];
    int line_number;
} CallFrame;

typedef struct {
    CallFrame *frames;
    size_t capacity;
    size_t top;
} CallStack;

// 使用队列实现任务调度
typedef struct {
    int task_id;
    int priority;
    char description[128];
} Task;

typedef struct {
    Task *tasks;
    size_t capacity;
    size_t front;
    size_t rear;
    size_t size;
} TaskQueue;

// 使用链表实现LRU缓存
typedef struct CacheNode {
    int key;
    int value;
    struct CacheNode *prev;
    struct CacheNode *next;
} CacheNode;

typedef struct {
    CacheNode *head;
    CacheNode *tail;
    CacheNode **hash_table;
    int capacity;
    int size;
} LRUCache;

4.2 性能比较

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
60
61
62
63
64
65
66
67
68
69
#include <time.h>

// 性能测试函数
void performance_test() {
    const int operations = 100000;
    clock_t start, end;
    
    // 测试数组栈 vs 链表栈
    printf("=== 栈性能测试 ===\n");
    
    // 数组栈测试
    Stack *array_stack = stack_init();
    start = clock();
    for (int i = 0; i < operations; i++) {
        stack_push(array_stack, i);
    }
    for (int i = 0; i < operations; i++) {
        int data;
        stack_pop(array_stack, &data);
    }
    end = clock();
    printf("数组栈: %f 秒\n", ((double)(end - start)) / CLOCKS_PER_SEC);
    stack_destroy(array_stack);
    
    // 链表栈测试
    LinkedStack *linked_stack = linked_stack_init();
    start = clock();
    for (int i = 0; i < operations; i++) {
        linked_stack_push(linked_stack, i);
    }
    for (int i = 0; i < operations; i++) {
        int data;
        linked_stack_pop(linked_stack, &data);
    }
    end = clock();
    printf("链表栈: %f 秒\n", ((double)(end - start)) / CLOCKS_PER_SEC);
    linked_stack_destroy(linked_stack);
    
    // 测试数组队列 vs 链表队列
    printf("\n=== 队列性能测试 ===\n");
    
    // 数组队列测试
    CircularQueue *array_queue = queue_init();
    start = clock();
    for (int i = 0; i < operations; i++) {
        queue_enqueue(array_queue, i);
    }
    for (int i = 0; i < operations; i++) {
        int data;
        queue_dequeue(array_queue, &data);
    }
    end = clock();
    printf("数组队列: %f 秒\n", ((double)(end - start)) / CLOCKS_PER_SEC);
    queue_destroy(array_queue);
    
    // 链表队列测试
    LinkedQueue *linked_queue = linked_queue_init();
    start = clock();
    for (int i = 0; i < operations; i++) {
        linked_queue_enqueue(linked_queue, i);
    }
    for (int i = 0; i < operations; i++) {
        int data;
        linked_queue_dequeue(linked_queue, &data);
    }
    end = clock();
    printf("链表队列: %f 秒\n", ((double)(end - start)) / CLOCKS_PER_SEC);
    linked_queue_destroy(linked_queue);
}

5. 最佳实践和注意事项

5.1 内存管理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 安全的内存分配宏
#define SAFE_MALLOC(ptr, type, size) do { \
    (ptr) = (type*)malloc((size) * sizeof(type)); \
    if (!(ptr)) { \
        fprintf(stderr, "内存分配失败: %s:%d\n", __FILE__, __LINE__); \
        exit(EXIT_FAILURE); \
    } \
} while(0)

// 安全的内存释放宏
#define SAFE_FREE(ptr) do { \
    if (ptr) { \
        free(ptr); \
        (ptr) = NULL; \
    } \
} while(0)

5.2 错误处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 统一的错误码定义
typedef enum {
    DS_SUCCESS = 0,
    DS_ERROR_NULL_POINTER = -1,
    DS_ERROR_OUT_OF_MEMORY = -2,
    DS_ERROR_INDEX_OUT_OF_BOUNDS = -3,
    DS_ERROR_EMPTY_CONTAINER = -4,
    DS_ERROR_FULL_CONTAINER = -5
} DataStructureError;

// 错误信息获取函数
const char* ds_error_string(DataStructureError error) {
    switch (error) {
        case DS_SUCCESS: return "成功";
        case DS_ERROR_NULL_POINTER: return "空指针错误";
        case DS_ERROR_OUT_OF_MEMORY: return "内存不足";
        case DS_ERROR_INDEX_OUT_OF_BOUNDS: return "索引越界";
        case DS_ERROR_EMPTY_CONTAINER: return "容器为空";
        case DS_ERROR_FULL_CONTAINER: return "容器已满";
        default: return "未知错误";
    }
}

总结

本文详细介绍了三种基础数据结构的C语言实现：

  1. 链表 - 动态数据结构，适合频繁插入删除操作
  2. 栈 - LIFO结构，适合递归、表达式求值等场景
  3. 队列 - FIFO结构，适合任务调度、缓冲等场景

选择合适的数据结构实现方式需要考虑：

  • 时间复杂度 - 不同操作的效率要求
  • 空间复杂度 - 内存使用效率
  • 使用场景 - 具体的应用需求
  • 维护成本 - 代码的可读性和可维护性

掌握这些基础数据结构的实现原理，是深入学习更复杂算法和数据结构的重要基础。

版权所有，如有侵权请联系我