数据结构笔记【2】

链式存储#

线性表之单链表#

将线性表的个元素分布在存储器的不同存储块，称为结点，通过地址或指针建立元素之间的联系。

结点分为data域和next域，next域是一个指针，指向 $a_i$ 的直接后继 $a_{i+1}$ 的所在结点。next为NULL时表明该元素为链表最后一个元素。

头结点：data不重要，专门用来标记第一个元素的结点地址

结点类型描述:

1
typedef struct node
2
{
3
    data_t data;    //数据域
4
    struct node *next;  //结点的后继指针域
5
}listnode, *linklist;   //linklist 是一个指向链表的指针类型，用于操作链表的头指针

所以有

1
listnode A; // 定义一个结点
2
linklist p = &A;  // 定义一个链表头指针，并指向 A 结点

获取 $a_i$ : p->data;
获取 $a_{i+1}$ : p->next->data;

若指针p的值为NULL，则其不指向任何结点，此时取p->data或p->next是错误的

单链表的遍历#

线性存储中，遍历基于表尾标识符last完成，索引 $i$ 从0循环到last视为遍历一次。

链式存储中，节点之间由next进行后继连接，所以遍历应当从头节点开始，由head = head->next方式进行索引（指针）更新

示例：

1
/*
2
    * @brief: 遍历链表并打印其中的元素
3
    * @param: H: 指向链表的指针
4
    * @return: 遍历成功返回0，失败返回-1
5
*/
6
int list_show(linklist H)
7
{
8
    linklist p;
9

10
    if (H == NULL) // 如果链表为空，直接返回 NULL
11
    {
12
        printf("H is NULL\n");
13
        return -1;
14
    }
15

16
    p = H->next; //p 指向头结点的下一个节点 注意：这里不是线性存储，节点之间通过指针连接，不能写成p=H+1
17
    while (p != NULL)
18
    {
19
        printf("%d ",p->data);
20
        p = p->next;  //p指向下一个节点
21
    }
22

23
    return 0;
24
}

单链表获取指定位置的节点地址#

头节点只有Next域，没有data域；尾节点只有data域，Next域为NULL。

list_get()函数遍历到指定链表的pos位置，遍历到之后返回最后一个节点的指针。注意遍历可以有两种方式：

从头节点开始，初始化p = head,i = -1，遍历到i < pos时结束，此时的pos是包含头节点在内的位置，比如链表{1,2,6,3}，元素2的位置是2，不是1；
从头节点之后的第一个结点开始，初始化p = head->next; i = 0，遍历到i < pos时结束，此时的pos是不包含头节点在内的位置，比如链表{1,2,6,3}，元素2的位置是1；

1
/*
2
    * @brief: 获取链表中指定位置的节点地址
3
    * @param: H: 指向链表的指针
4
    * @param: pos: 指定的位置
5
    * @return: 插入成功返回找到的结点，失败返回NULL
6
*/
7
linklist list_get(linklist H, int pos)
8
{
9
    linklist p; // 声明一个指向链表节点的指针，用于遍历链表
10
    int i = -1; // 用于记录遍历位置，初始化为-1以考虑头结点
11

12
    if (H == NULL) // 如果链表为空，直接返回 NULL
13
    {
14
        printf("H is NULL\n");
15
        return NULL;
16
    }
17

18
    if (pos == -1) // 如果 pos == -1，返回头结点
19
    {
20
        return H;
21
    }
22

23
    p = H; // 从头结点的下一个节点开始遍历
24
    while (i < pos) // 当 i 小于 pos 时继续循环
25
    {
26
        p = p->next; // 移动到下一个节点
27
        if (p == NULL)  // 如果链表到达了末尾，且还没找到 pos，返回 NULL
28
        {
29
            printf("pos is invalid\n");
30
            return NULL;
31
        }
32
        i++; // 记录当前遍历到的节点编号
33
    }
34

35
    return p; // 返回找到的节点
36
}

单链表的其他操作#

1
#include <stdio.h>
2
#include <stdlib.h>
3
#include "linklist.h"
4

5
/*
6
    * @brief: 创建一个空的链式线性表
7
    * @param: 无
8
    * @return: 返回链表的头指针
9
*/
10
linklist list_create()
11
{
12
    linklist head = (linklist)malloc(sizeof(listnode));
13

14
    if (head == NULL)
15
    {
16
        printf("memory allocation failed\n");
17
        return NULL;
18
    }
19
    head->next = NULL;  // 初始化头结点的指针域为空，表示链表为空
20
    return head;
21
}
22

23
/*
24
    * @brief: 插入元素到链表中
25
    * @param: head: 指向链表头结点的指针
26
    * @param: value: 要插入的值
27
    * @param: pos：插入位置，新的节点会放置在该位置之后
28
    * @return: 插入成功返回0，失败返回-1
29
*/
30
int list_insert(linklist head, data_t value, int pos)
31
{
32
    if (head == NULL) return -1;  // 检查链表是否存在
33

34
    // 如果要在第 0 位插入节点（头结点之后）
35
    if (pos == 0)
36
    {
37
        linklist new_node = (linklist)malloc(sizeof(listnode));   //为新节点申请内存
38
        if (new_node == NULL)
39
        {
40
            printf("memory allocation failed\n");
41
            return -1;
42
        }
43

44
        new_node->data = value;   // 新节点的数据域赋值
45
        new_node->next = head->next;  // 新节点指向头结点后的第一个节点
46
        head->next = new_node;  // 头结点的next指向新插入的节点
47
        return 0;
48
    }
49

50
    // 否则查找 pos-1 位置的前驱节点
51
    linklist prev_node = list_get(head, pos-1);
52
    if (prev_node == NULL)
53
    {
54
        printf("Invalid position\n");
55
        return -1;
56
    }
57

58
    // 为新节点申请内存
59
    linklist new_node = (linklist)malloc(sizeof(listnode));
60
    if (new_node == NULL)
61
    {
62
        printf("memory allocation failed\n");
63
        return -1;
64
    }
65

66
    new_node->data = value;  // 设置新节点的数据
67
    new_node->next = prev_node->next;  // 新节点指向原链表在插入位置后的节点
68
    prev_node->next = new_node;  // 前驱节点替换为新插入的节点
69

70
    return 0;
71
}
72

73
/*
74
    * @brief: 获取链表中指定位置的节点地址
75
    * @param: H: 指向链表的指针
76
    * @param: pos: 指定的位置
77
    * @return: 插入成功返回找到的结点，失败返回NULL
78
*/
79
linklist list_get(linklist H, int pos)
80
{
81
    linklist p; // 声明一个指向链表节点的指针，用于遍历链表
82
    int i = -1; // 用于记录遍历位置，初始化为-1以考虑头结点
83

84
    if (H == NULL) // 如果链表为空，直接返回 NULL
85
    {
86
        printf("H is NULL\n");
87
        return NULL;
88
    }
89

90
    if (pos == -1) // 如果 pos == -1，返回头结点
91
    {
92
        return H;
93
    }
94

95
    p = H; // 从头结点开始遍历
96
    while (i < pos) // 当 i 小于 pos 时继续循环
97
    {
98
        p = p->next; // 移动到下一个节点
99
        if (p == NULL)  // 如果链表到达了末尾，且还没找到 pos，返回 NULL
100
        {
101
            printf("pos is invalid\n");
102
            return NULL;
103
        }
104
        i++; // 记录当前遍历到的节点编号
105
    }
106

107
    return p; // 返回找到的节点
108
}
109

110
/*
111
    * @brief: 遍历链表并打印其中的元素
112
    * @param: H: 指向链表的指针
113
    * @return: 遍历成功返回0，失败返回-1
114
*/
115
int list_show(linklist H)
116
{
117
    linklist p;
118

119
    if (H == NULL) // 如果链表为空，直接返回 NULL
120
    {
121
        printf("H is NULL\n");
122
        return -1;
123
    }
124

125
    p = H->next; //p 指向头结点的下一个节点 注意：这里不是线性存储，节点之间通过指针连接，不能写成p=H+1
126
    while (p != NULL)
127
    {
128
        printf("%d ",p->data);
129
        p = p->next;  //p指向下一个节点
130
    }
131

132
    return 0;
133
}
134

135
/*
136
    * @brief: 遍历链表并查找指定的值
137
    * @param: H: 指向链表的指针
138
    * @return: 查找成功返回0，失败返回-1
139
*/
140
int list_search(linklist H, data_t value)
141
{
142
    if (H == NULL) // 如果链表为空，直接返回 NULL
143
    {
144
        printf("H is NULL\n");
145
        return -1;
146
    }
147

148
    linklist p = H->next;
149
    int i = 0; //初始化节点索引为-1
150

151
    while (p != NULL)
152
    {
153
        if (p->data == value)
154
        {
155
            printf("search ok, pos is %d\n",i);
156
        }
157
        i++;
158
        p = p->next;   //更新指针，指向下一个节点
159
    }
160

161
    return 0;
162
}
163

164
/*
165
    * @brief: 合并两个链表，然后存储到新链表中
166
    * @param: H1: 指向链表1的指针
167
    * @param: H2: 指向链表2的指针
168
    * @return: 返回表3
169
*/
170
linklist list_merge(linklist H1, linklist H2)
171
{
172
    if (H1 == NULL || H2 == NULL)
173
    {
174
        printf("H1 or H2 is null\n");
175
        return NULL;
176
    }
177

178
    linklist H3 = list_create();    //创建新表
179

180
    //拷贝H1至H3
181
    linklist TempPtr1 = H1->next;   //声明TempPtr指向H1的下一个节点，跳过头节点
182
    int count1 = 0;
183
    while (TempPtr1 != NULL)
184
    {
185
        list_insert(H3, TempPtr1->data, count1);    //向H3插入H1的data
186
        TempPtr1 = TempPtr1->next;  //更新指针
187
        count1++;   //更新计数器
188
    }
189

190
    linklist TempPtr2 = H2->next;
191
    int count2 = 0;
192
    while (TempPtr2 != NULL)
193
    {
194
        list_insert(H3, TempPtr2->data, count1 + count2);
195
        TempPtr2 = TempPtr2->next;
196
        count2++;
197
    }
198

199
    return H3;
200
}
201

202
/*
203
    * @brief: 删除两个链表中的重复部分，将剩余元素存在新表中
204
    * @param: H1: 指向链表1的指针
205
    * @param: H2: 指向链表2的指针
206
    * @return: 返回表3
207
    * @note: 仅适用于小链表，大链表可以用哈希表
208
*/
209
linklist list_purge(linklist H1, linklist H2)
210
{
211
    if (H1 == NULL || H2 == NULL)
212
    {
213
        printf("H1 or H2 is null\n");
214
        return NULL;
215
    }
216

217
    linklist H3 = list_create();
218

219
    int is_common = 0;  //初始化标记，09为不重复，1为重复
220

221
    linklist TempPtr1 = H1->next;   //初始化Ptr1指向H1的第一个有效节点
222
    while (TempPtr1 != NULL)
223
    {
224
        linklist TempPtr2 = H2->next;   // 每次遍历TempPtr1时，重置TempPtr2，否则TempPtr2一旦遍历到NULL后不会返回
225
        while (TempPtr2 != NULL)
226
        {
227
            if (TempPtr1->data == TempPtr2->data)
228
            {
229
                printf("common elements:%d\n",TempPtr2->data);
230

231
                is_common = 1;
232
                list_insert(H3, TempPtr2->data, 0);
233
            }
234
            TempPtr2 = TempPtr2->next;  //更新TempPtr2
235
        }
236

237
        if (is_common == 0)  // 如果不是重复元素，插入到H3中
238
        {
239
            list_insert(H3, TempPtr1->data, 0);
240
        }
241
        TempPtr1 = TempPtr1->next;  //更新TempPtr1
242
    }
243

244
    return H3;
245
}
246

247
/*
248
    * @brief: 删除指定位置的节点
249
    * @param: H: 指向链表的指针
250
    * @param: pos：待删除结点的位置
251
    * @return: 成功返回0，失败返回-1
252
*/
253
int list_delete(linklist H, int pos)
254
{
255
    if (H == NULL)
256
    {
257
        printf("no such linklist\n");
258
        return -1;
259
    }
260

261
    // 如果删除的位置是第一个节点
262
    if (pos == 1)
263
    {
264
        linklist TempPtr = H->next; // 保存下一个节点
265
        free(H); // 释放头节点
266
        H = TempPtr; // 更新头指针
267
        return 0;
268
    }
269

270
    // 获取待删除节点的前一个节点
271
    linklist Prev_Node = list_get(H, pos - 1);
272
    if (Prev_Node == NULL || Prev_Node->next == NULL)
273
    {
274
        printf("invalid position\n");
275
        return -1;
276
    }
277

278
    // 获取待删除的节点
279
    linklist TempPtr = Prev_Node->next;
280
    Prev_Node->next = TempPtr->next; // 连接前后节点
281
    free(TempPtr); // 释放被删除的节点
282

283
    return 0;
284
}
285

286
/*
287
    * @brief: 删除整个链表并释放内存
288
    * @param: H: 指向链表的指针
289
    * @return: 成功返回0，失败返回-1
290
*/
291
int list_free(linklist H)
292
{
293
    if (H == NULL)
294
    {
295
        printf("no such linklist\n");
296
        return -1;
297
    }
298

299
    linklist TempPtr = H;
300

301
    while (H != NULL)
302
    {
303
        TempPtr = H;    // 保存当前节点
304
        H = H->next;    // 更新链表头指针为下一个节点
305
        free(TempPtr);  // 释放当前节点
306
    }
307

308
    return 0;
309
}
310

311
/*
312
    * @brief: 倒置链表
313
    * @param: H: 指向链表的指针
314
    * @return: 成功返回0，失败返回-1
315
    * @note: 将节点拿出放到
316
*/
317
int list_reverse(linklist H)
318
{
319
    if (H == NULL)
320
    {
321
        printf("no such linklist\n");
322
        return -1;
323
    }
324

325
    if (H->next == NULL)
326
    {
327
        printf("linklist is empty\n");
328
        return -1;
329
    }
330

331
    //链表一分为二
332
    linklist p = H->next->next;
333
    H->next->next = NULL;
334

335

336
    while (p != NULL)
337
    {
338
        linklist q = p; // 暂存当前节点
339
        p = p->next;    // 移动到下一个节点
340
        q->next = H->next; // 将当前节点插入到链表头部（头插法）
341
        H->next = q; // 更新头节点为新插入的节点
342
    }
343

344
    return 0;
345
}
346

347
/*
348
    * @brief: 求链表相邻两节点data值之和为最大的第一结点的指针
349
    * @param: H: 指向链表的指针
350
    * @return: 成功返回指针，失败返回NULL
351
*/
352
int list_getmax(linklist H)
353
{
354
    if (H == NULL)
355
    {
356
        printf("no such linklist\n");
357
        return -1;
358
    }
359

360
    if (H->next == NULL)
361
    {
362
        printf("linklist is empty\n");
363
        return -1;
364
    }
365

366
    int sum_new, max = 0;
367
    linklist p = H->next;
368
    linklist max_p = H->next;
369
    int sum = p->data + p->next->data;
370

371
    while (p != NULL && p->next != NULL)
372
    {
373
        sum_new = p->data + p->next->data;
374

375
        if (sum_new >= max)
376
        {
377
            max = sum_new;
378
            max_p = p;
379
        }
380

381
        p = p->next;
382
    }
383
    //printf("max sum is %d",max);
384
    return max;
385
}

栈(Stack)#

和微机原理中栈的原理相同

注意：

先进后出
注意栈顶指针的更新

栈主要用于以下场景：

函数调用：使用栈来保存当前函数的局部变量、返回地址等信息。当函数调用另一个函数时，新的函数信息被压入栈中，函数执行完毕后会从栈中弹出，返回上一个函数。
撤销操作
递归
二叉树遍历

1
#include <stdio.h>
2
#include <stdlib.h>
3
#include "linear_stack.h"
4
#include <string.h>
5

6
/*
7
    @brief: 创建新的栈
8
    @param: len: 栈的长度
9
    @return: 指向栈的指针
10
*/
11
sqstack *stack_create(int len)
12
{
13
    if (len < 0)
14
    {
15
        printf("len is illegal\n");
16
        return NULL;
17
    }
18

19
    sqstack *ss;
20

21
    //申请用于放置结构体的内存
22
    ss = (sqstack *)malloc(sizeof(sqstack));
23
    if (ss == NULL) {
24
        printf("Failed to allocate memory for stack.\n");
25
        return NULL;
26
    }
27

28
    //申请用于放置栈内数据的内存
29
    ss->data = (data_t *)malloc(sizeof(data_t) * len);
30
    if (ss->data == NULL) {
31
        printf("Failed to allocate memory for stack data.\n");
32
        free(ss);
33
        return NULL;
34
    }
35

36
    memset(ss->data, 0, len*sizeof(data_t));
37
    ss->top = -1;
38
    ss->maxlen = len;
39

40
    return ss;
41
}
42

43
/*
44
    @brief: 入栈
45
    @param: s：对应栈指针 value：待入栈值
46
    @return: 成功返回0，失败返回-1
47
*/
48
int stack_push(sqstack *s, data_t value)
49
{
50
    if (s == NULL)
51
    {
52
        printf("no such stack\n");
53
        return -1;
54
    }
55
    if (s->top == s->maxlen - 1)
56
    {
57
        printf("stack is full\n");
58
        return -1;
59
    }
60

61
    s->top++;
62
    s->data[s->top] = value;
63

64
    printf("stack push ok\n");
65
    return 0;
66
}
67

68
/*
69
    @brief: 判断栈是否为空
70
    @param: s：对应栈指针
71
    @return: 栈为空返回-1，非空返回0，函数非法返回-2
72
*/
73
int stack_empty(sqstack *s)
74
{
75
    if (s == NULL)
76
    {
77
        printf("no such stack\n");
78
        return -2;
79
    }
80

81
    if (s->top == -1)
82
    {
83
        printf("stack is empty\n");
84
        return -1;
85
    }
86
    else
87
    {
88
        return 0;
89
    }
90
}
91

92
/*
93
    @brief: 判断栈是否为满
94
    @param: s：对应栈指针
95
    @return: 栈为满返回-1，非满返回0，函数非法返回-2
96
*/
97
int stack_full(sqstack *s)
98
{
99
    if (s == NULL)
100
    {
101
        printf("no such stack\n");
102
        return -2;
103
    }
104

105
    if (s->top == s->maxlen - 1)
106
    {
107
        printf("stack is full\n");
108
        return -1;
109
    }
110
    else
111
    {
112
        return 0;
113
    }
114
}
115

116
/*
117
    @brief: 数据出栈
118
    @param: s：对应栈指针
119
    @return: 返回出栈值，如果栈为空或出错则返回-999
120
*/
121
data_t stack_pop(sqstack *s)
122
{
123
    if (s == NULL)
124
    {
125
        printf("Stack not initialized\n");
126
        return -999;
127
    }
128

129
    if (s->top == -1)
130
    {
131
        printf("Stack is empty\n");
132
        return -999;
133
    }
134

135
    data_t temp = s->data[s->top];
136
    s->top--;
137
    return temp;
138
}
139

140
/*
141
    @brief: 清除栈内所有元素
142
    @param: s：对应栈指针
143
    @return: 成功返回0，失败返回-1
144
*/
145
int stack_clear(sqstack *s)
146
{
147
    if (s == NULL)
148
    {
149
        printf("Stack not initialized\n");
150
        return -1;
151
    }
152

153
    if (s->top == -1)
154
    {
155
        return 0;
156
    }
157

158
    //一般的栈清空操作只会重置 top，但不释放内存
159
    s->top = -1;
160
    //free(s->data);
161
    //s->data = NULL;
162

163
    return 0;
164
}
165

166
/*
167
    @brief: 释放整个栈的空间
168
    @param: s：对应栈指针
169
    @return: 成功返回0，失败返回-1
170
*/
171
int stack_free(sqstack *s)
172
{
173
    if (s == NULL)
174
    {
175
        printf("Stack not initialized\n");
176
        return -1;
177
    }
178

179
    free(s->data);
180
    s->data = NULL;
181
    free(s);
182

183
    return 0;
184
}

队列(Queue)#

基于数组的队列#

等同于现实生活中的“排队”，元素从列尾存入，列首取出

双端队列：列首和列尾都可以进行存入和取出；或解释为：同一个队列共享列首和列尾

队列多被用于：

任务调度
消息队列
IO请求管理（确保系统资源的有序访问）

队列结构体一般为

1
typedef int data_t;
2
#define N 64
3
typedef struct
4
{
5
    data_t data[N];
6
    int front, rear;    //rear为队尾后一个元素的下标
7
}sequeue_t;

其中rear一般指示队尾元素的下一个位置，也就是下一个要入队的元素位置。用于处理队列为空或只有一个元素时的情况。头尾位置重合时，队列即为空。初始front, rear = 0;

出队列：x = sq[front++]
入队列：sq[rear++] = x;

当队列中前几个元素出队时，会造成这些位置为空，从而浪费队列中的可存储空间。此时可以使用循环队列。为区别空队和满队，满队元素个数比数组元素个数少一个。

1
/*
2
    @brief: 创建空队列
3
    @param: 无
4
    @return: 指向队列的指针
5
*/
6
sequeue queue_create()
7
{
8
    sequeue qq = (struct queue*)malloc(sizeof(struct queue));
9

10
    if (qq == NULL)
11
    {
12
        printf("malloc failed\n");
13
        return NULL;
14
    }
15

16
    qq->front = 0;
17
    qq->rear = 0;
18

19
    memset(qq->data, 0, sizeof(qq->data));
20

21
    return qq;
22
}
23

24
/*
25
    @brief: 遍历并打印队列
26
    @param: q：队列指针
27
    @return: 成功返回0，失败返回-1
28
*/
29
int queue_print(sequeue q)
30
{
31
    if (q == NULL)
32
    {
33
        printf("no such queue\n");
34
        return -1;
35
    }
36

37
    if (q->front == q->rear)
38
    {
39
        printf("queue is empty");
40
        return -1;
41
    }
42

43
    for (int i = q->front; i < q->rear; i++)
44
    {
45
        printf("%d ", q->data[i]);
46
    }
47

48
    return 0;
49
}
50

51
/*
52
    @brief: 元素入队
53
    @param: q：队列指针 data：待入队元素
54
    @return: 成功返回0，失败返回-1
55
*/
56
int enqueue(sequeue q, data_t data)
57
{
58
    if (q == NULL)
59
    {
60
        printf("no such queue\n");
61
        return -1;
62
    }
63

64
    if ((q->rear + 1) % N == q->front)
65
    {
66
        printf("queue is full\n");
67
        return -1;
68
    }
69

70
    q->data[q->rear] = data;
71
    q->rear = (q->rear + 1) % N;    // rear 指针移动到队列边界时，通过取余使其返回到数组开头，实现循环
72

73
    return 0;
74
}
75

76
/*
77
    @brief: 元素出队
78
    @param: q：队列指针
79
    @return: 成功返回出队元素，失败返回-1
80
    @note: 出队元素为队首的第一个元素
81
*/
82
int dequeue(sequeue q)
83
{
84
    if (q == NULL)
85
    {
86
        printf("no such queue\n");
87
        return -1;
88
    }
89

90
    if (q->front == q->rear)
91
    {
92
        printf("queue is empty");
93
        return -1;
94
    }
95

96
    int temp = q->data[q->front];
97
    q->front = (q->front + 1) % N;
98

99
    return temp;
100
}
101

102
/*
103
    @brief: 清空队列内元素，但不释放内存
104
    @param: q：队列指针
105
    @return: 成功返回0，失败返回-1
106
    @note:
107
*/
108
int queue_clear(sequeue q)
109
{
110
    if (q == NULL)
111
    {
112
        printf("no such queue\n");
113
        return -1;
114
    }
115

116
    q->front = 0;
117
    q->rear = 0;
118

119
    return 0;
120
}

基于链式存储的队列#

插入操作在队尾进行，删除操作在队首进行，由队首指针和队尾指针控制队列操作

结构体需要定义两个：节点结构体和队列结构体

1
typedef int data_t;
2

3
typedef struct node
4
{
5
    data_t data;
6
    struct node* next;
7
}*linklist;
8

9
typedef struct queue
10
{
11
    linklist front;
12
    linklist rear;
13
};

初始化：创建空队列，front和rear指针都为空
入队：在队尾新增一个节点，并更新当前队尾节点的next指针
出队：更新front指针到待出队节点的下一个节点，然后删除原有队首节点

与线性表不同的是，链式队列中rear指针一般指向最后队列的一个节点，而非最后一个节点的下一个节点。

判断链式队列是否为空的条件只有一个：front == NULL, rear == NULL，不能使用front==rear判断，因为这里front和rear都是指针，并且rear指向的是最后一个节点，而非线性队列中的指向最后一个位置的下一个位置（待插入位置）。假设队伍中只有一个元素，这时候front和rear二者相同，但队列不为空。

创建新的链式队列#

1
/*
2
    @ brief：创建并初始化新的链式队列
3
    @param：无
4
    @return：成功指向新队列的指针，失败返回NULL
5
*/
6
struct queue* queue_create()
7
{
8
    struct queue* q = (struct queue*)malloc(sizeof(struct queue));
9

10
    if (q == NULL)
11
    {
12
        printf("malloc failed\n");
13
        return NULL;
14
    }
15

16
    q->front = NULL;
17
    q->rear = NULL;
18

19
    return q;
20
}

为队列申请内存，暂时先不申请节点的，因为这是一个空队列，目前还没有元素
因为队列中没有节点，front和rear指针都为NULL

遍历队列#

1
/*
2
    @ brief：遍历链式队列并打印所有元素
3
    @param：q：队列指针
4
    @return：成功返回0，失败返回-1
5
*/
6
int queue_print(struct queue* q)
7
{
8
    if (q == NULL)
9
    {
10
        printf("no such queue\n");
11
        return -1;
12
    }
13

14
    if (q->front == NULL)
15
    {
16
        printf("queue is empty\n");
17
        return -1;
18
    }
19

20
    struct node* temp = q->front;
21

22
    while (temp != NULL)
23
    {
24
        printf("%d", temp->data);
25
        temp = temp->next;
26
    }
27

28
    printf("\n");
29

30
    return 0;
31
}

在遍历时要用临时指针temp来代替front，如果直接用front指针的话，遍历一次之后front就回不去了，整个队列会被破坏
尽量不要在遍历前用temp存储front指针，用front指针遍历完之后再front = temp这种形式返回回去的这种方法，在多线程的时候可能会有问题
遍历结束的条件是当temp指针走到NULL之后，表明从队首节点到队尾节点全都扫描到了，而不是temp(front)=rear或者temp(front)=rear->next，因为链式队列中rear指针指向的是最后一个（队尾）节点

其他#

1
/*
2
    @ brief：创建并初始化新的链式队列
3
    @param：无
4
    @return：成功指向新队列的指针，失败返回NULL
5
*/
6
struct queue* queue_create()
7
{
8
    struct queue* q = (struct queue*)malloc(sizeof(struct queue));
9

10
    if (q == NULL)
11
    {
12
        printf("malloc failed\n");
13
        return NULL;
14
    }
15

16
    q->front = NULL;
17
    q->rear = NULL;
18

19
    return q;
20
}
21

22
/*
23
    @ brief：遍历链式队列并打印所有元素
24
    @param：q：队列指针
25
    @return：成功返回0，失败返回-1
26
*/
27
int queue_print(struct queue* q)
28
{
29
    if (q == NULL)
30
    {
31
        printf("no such queue\n");
32
        return -1;
33
    }
34

35
    if (q->front == NULL)
36
    {
37
        printf("queue is empty\n");
38
        return -1;
39
    }
40

41
    struct node* temp = q->front;
42

43
    while (temp != NULL)
44
    {
45
        printf("%d ", temp->data);
46
        temp = temp->next;
47
    }
48

49
    printf("\n");
50

51
    return 0;
52
}
53

54
/*
55
    @ brief：元素入队
56
    @param：q：队列指针 val：待入队元素值
57
    @return：成功返回0，失败返回-1
58
*/
59
int enqueue(struct queue* q, data_t val)
60
{
61
    if (q == NULL)
62
    {
63
        printf("no such queue\n");
64
        return -1;
65
    }
66
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
67

68
    newnode->data = val;
69
    newnode->next = NULL;
70

71
    //判断原队列是否为空
72
    if (q->rear == NULL)
73
    {
74
        q->front = newnode;
75
        q->rear = newnode;
76
    }
77
    else
78
    {
79
        q->rear->next = newnode;
80
        q->rear = newnode;
81
    }
82

83
    return 0;
84
}
85

86
/*
87
    @ brief：元素出队
88
    @param：q：队列指针
89
    @return：成功返回0，失败返回-1
90
*/
91
int dequeue(struct queue* q)
92
{
93
    if (q == NULL)
94
    {
95
        printf("no such queue\n");
96
        return -1;
97
    }
98

99
    if (q->front == NULL)
100
    {
101
        printf("queue is empty\n");
102
        return -1;
103
    }
104

105
    struct node* temp_node = q->front;
106
    int temp = temp_node->data;
107
    q->front = q->front->next;
108

109
    // 如果队列为空，则需要更新 rear 为 NULL
110
    if (q->front == NULL)
111
    {
112
        q->rear = NULL;
113
    }
114

115
    free(temp_node);
116

117
    return temp;
118
}
119

120
/*
121
    @ brief：清空队列并删除对应节点
122
    @param：q：队列指针
123
    @return：成功返回0，失败返回-1
124
*/
125
int queue_clear(struct queue* q)
126
{
127
    if (q == NULL)
128
    {
129
        printf("no such queue\n");
130
        return -1;
131
    }
132

133
    if (q->front == NULL)
134
    {
135
        return 0;
136
    }
137

138
    //临时节点，用于储存待删除的节点而不影响后续节点的遍历
139
    struct node* temp;
140

141
    while (q->front != NULL)
142
    {
143
        temp = q->front;
144
        q->front = q->front->next;
145
        free(temp);
146
    }
147

148
    q->rear = NULL;
149

150
    return 0;
151
}

球钟问题（队列和栈的应用）#

球钟问题（Ball Clock Problem）是一种经典的算法和数据结构题目，主要用于考察队列和栈的结合运用。问题的基本情景是：假设有一个球钟系统，它通过小球来计时。系统中有 3 个轨道，每个轨道容量不同：

分钟轨道（Min Track）：最多可容纳 4 个小球。
五分钟轨道（Five-Min Track）：最多可容纳 11 个小球。
小时轨道（Hour Track）：最多可容纳 11 个小球。

运作机制：

初始状态下有一组编号为 1 到 n 的小球，n 是球的总数，这些小球依次通过队列进行处理。
每分钟，第一个小球从队列中取出，放到分钟轨道上。
当分钟轨道满（即放入第5个小球时），轨道中的 4 个小球被依次放回队列，保持原来的顺序，而第 5 个小球则进入五分钟轨道。
当五分钟轨道满（即放入第12个小球时），轨道中的 11 个小球被依次放回队列，第 12 个小球进入小时轨道。
当小时轨道满（即放入第12个小球时），轨道中的 11 个小球被依次放回队列，第 12 个小球也回到队列的末尾。

问题的一个常见考点是计算在给定的初始状态下，经过多少分钟后，小球队列的顺序会恢复到最初的状态。

1
#include <stdio.h>
2
#include <stdlib.h>
3
#include "queue.h"
4
#include "linear_stack.h"
5

6
#define N 27
7

8
int main()
9
{
10
    struct queue* main_queue = queue_create();
11
    struct stack* minute = stack_create(4);
12
    struct stack* five_minute = stack_create(11);
13
    struct stack* hour = stack_create(11);
14

15
    int time = 0;
16

17
    //初始化主队列中的27个小球
18
    for (int i = 1; i <= N; i++)
19
    {
20
        enqueue(main_queue, i);
21
    }
22

23
    while (!stack_full(hour))   //如果小时轨道未满，继续
24
    {
25
        while (!stack_full(five_minute))    //如果五分钟轨道未满，继续
26
        {
27
            while (!stack_full(minute))     //如果分钟轨道未满，继续
28
            {
29
                int ball = dequeue(main_queue);     //从主队列中获取小球
30
                stack_push(minute, ball);           // 放入分钟栈中
31
                time++;
32

33
                if (stack_full(minute))             //如果分钟栈满了
34
                {
35
                    int count_min = 0;
36
                    while (count_min < 4)
37
                    {
38
                        int min_top_ball = stack_pop(minute);   //从分钟栈中弹出一个小球
39
                        enqueue(main_queue, min_top_ball);      //该小球送入主队列
40
                        count_min++;
41
                    }
42

43
                    stack_push(five_minute, ball);          //将一个小球推入五分钟栈
44
                }
45
            }
46
            if (stack_full(five_minute))    //如果五分钟栈满了
47
            {
48
                int count_five_min = 0;
49
                while (count_five_min < 11)
50
                {
51
                    int five_min_top_ball = stack_pop(five_minute);     //从五分钟栈中弹出一个小球
52
                    enqueue(main_queue, five_min_top_ball);     //送回主队列
53
                    count_five_min++;
54
                }
55

56
                stack_push(hour, dequeue(main_queue));
57
            }
58
        }
59

60
        if (stack_full(hour))
61
        {
62
            int count_hour = 0;
63
            while (count_hour < 11)
64
            {
65
                int hour_top_ball = stack_pop(hour);
66
                enqueue(main_queue, hour_top_ball);
67
                count_hour++;
68
            }
69
        }
70
    }
71

72
    printf("钟表恢复到初始状态所需时间: %d 分钟\n", time);
73

74
    return 0;
75
}