顺序表

1. 线性表

1.1 基本概念

定义：一种逻辑结构，表示 N 个相同类型元素的有限序列。
常见的线性表：顺序表、栈和队列、链表、字符串等。
线性表的数据集合可以写作 ${a_{1}, a_{2}, a_{3}, . . ., a_{n}}$ ，其中 $n$ 为线性表的长度 (length)， $1, 2, 3, . . ., n$ 称为线性表中各个元素的逻辑下标。
在线性表中，除最后一个元素（这个元素称为终端节点）之外，每一个元素 $a_{i}$ 都有一个元素作为它的后继，记作 $next (a_{i})$ 。
在线性表中，除第一个元素（这个元素称为开始节点）之外，每一个元素 $a_{i}$ 都有一个元素作为它的前驱，记作 $prev (a_{i})$ 。

1.2 基本操作

置空 (clear())
判空 (isEmpty())
长度 (length())
取元素 (get(i))
插入 (insert(i,x))
删除 (remove(i))
查找 (indexOf(x))

2. 顺序表 (SeqList)

2.1 基本概念

元素存储在一段逻辑地址连续的存储单元上，连续保证了可以用指针偏移的方式访问；
通常使用数组实现；
因为数组下标从 0 开始，所以逻辑下标为 1 的元素存储在数组下标为 0 的位置上，这个下标称为此元素的物理下标；
在顺序表中，通常情况下，物理下标 = 逻辑下标 - 1。此二级标题包裹的内容中，下标默认指物理下标；
顺序表可以用一个定长数组实现，但容易造成“不够用”和“过剩”，所以一般动态开辟和扩容数组。

2.2 实现

构建结构体

typedef int ElementType;
typedef struct {
    ElementType* arr;
    size_t size;     // length of the sequence list
    size_t capacity; // size of the array
} SeqList;

初始化
(1) 初始化空顺序表

void initSeqList(SeqList* l) {
    l->arr = (ElementType*)malloc(sizeof(ElementType) * g_initCap);
    if (!(l->arr)) {
        printf("Initialization failed!\n");
        exit(-1);
    }
    l->size = 0;
    l->capacity = g_initCap;
}

(2) 以数组初始化顺序表

void initSeqListFromArray(SeqList* l, const ElementType* a, size_t length) {
    l->arr = (ElementType*)malloc(sizeof(ElementType) * length);
    if (!(l->arr)) {
        printf("Initialization failed!\n");
        exit(-1);
    }
    for (size_t n = 0; n < length; ++n)
        l->arr[n] = a[n];
    l->size = length;
    l->capacity = length;
}

清空

void clearSeqList(SeqList* l) {
    free(l->arr);
    initSeqList(l);
}

判空

bool isSeqListEmpty(const SeqList* l) { return l->size == 0; }

长度

size_t lengthOfSeqList(const SeqList* l) { return l->size; }

取元素

ElementType getFromSeqList(const SeqList* l, size_t i) {
    if (i >= l->size) {
        printf("Index out of bound!\n");
        return 0;
    }
    return l->arr[i];
}

插入
除上文所说在指定位置插入外，还可以实现表尾插入。当当前线性表大小与容量相等时，需要扩容。

(1) 扩容

void expandSeqList(SeqList* l) {
    printf("Expansion\n");
    ElementType* newArr =
        (ElementType*)realloc(l->arr, sizeof(ElementType) * 2 * l->capacity);
    if (!(newArr)) {
        printf("Expansion failed!\n");
        exit(-1);
    }
    l->capacity *= 2;
    l->arr = newArr;
}

(2) 在末尾插入

void insertBack2SeqList(SeqList* l, ElementType x) {
    if (l->size == l->capacity) {
        expandSeqList(l);
    }
    l->arr[l->size++] = x;
}

(3) 指定位置插入

void insert2SeqList(SeqList* l, size_t i, ElementType x) {
    if (l->size == l->capacity) {
        expandSeqList(l);
    }
    for (size_t n = l->size; n > i; --n) {
        l->arr[n] = l->arr[n - 1];
    }
    l->arr[i] = x;
    ++l->size;
}

删除元素

void removeFromSeqList(SeqList* l, size_t i) {
    if (i >= l->size)
        printf("Index out of bound!\n");
    for (size_t n = i; n < l->size - 1; ++n) {
        l->arr[n] = l->arr[n + 1];
    }
    --l->size;
}

查找元素

int indexOfSeqList(const SeqList* l, ElementType x) {
    for (size_t n = 0; n < l->size; ++n)
        if (l->arr[n] == x)
            return (int)n;
    return -1;
}

打印顺序表

void printSeqList(const SeqList* l) {
    printf("cap: %zu  size: %zu ==>", l->capacity, l->size);
    for (size_t i = 0; i < l->size; ++i)
        printf(" [%zu]=%d", i, l->arr[i]);
    printf("\n");
}

额外功能：“反”扩容
当 size < capacity / 4 的时候，可以缩小数组，减小对内存的占用。

void curtailSeqList(SeqList* l) {
    printf("Curtailment\n");
    ElementType* newArr =
        (ElementType*)realloc(l->arr, sizeof(ElementType) * l->capacity / 2);
    if (!(newArr)) {
        printf("Curtailment failed!\n");
        exit(-1);
    }
    l->capacity /= 2;
    l->arr = newArr;
}

在 removeFromSeqList 中添加如下代码：

if ((l->size + 1) * 4 < l->capacity)
    curtailSeqList(l);

2.3 完整示例代码

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

typedef int ElementType;

typedef struct {
    ElementType *arr;
    size_t size;
    size_t capacity;
} SeqList;

static const size_t g_initCap = 8;

void initSeqList(SeqList *l);
void initSeqListFromArray(SeqList *l, const ElementType *a, size_t length);
void clearSeqList(SeqList *l);
void destroySeqList(SeqList *l);
bool isSeqListEmpty(const SeqList *l);
size_t lengthOfSeqList(const SeqList *l);
ElementType getFromSeqList(const SeqList *l, size_t i);
void insertBack2SeqList(SeqList *l, ElementType x);
void insert2SeqList(SeqList *l, size_t i, ElementType x);
void removeFromSeqList(SeqList *l, size_t i);
int indexOfSeqList(const SeqList *l, ElementType x);
void printSeqList(const SeqList *l);

static void expandSeqList(SeqList *l);
static void curtailSeqList(SeqList *l);

void initSeqList(SeqList *l) {
    l->arr = (ElementType *)malloc(sizeof(ElementType) * g_initCap);
    if (!l->arr) {
        perror("Initialization failed");
        exit(EXIT_FAILURE);
    }
    l->size = 0;
    l->capacity = g_initCap;
}

void initSeqListFromArray(SeqList *l, const ElementType *a, size_t length) {
    size_t cap = length > 0 ? length : g_initCap;
    l->arr = (ElementType *)malloc(sizeof(ElementType) * cap);
    if (!l->arr) {
        perror("Initialization from array failed");
        exit(EXIT_FAILURE);
    }
    for (size_t n = 0; n < length; ++n)
        l->arr[n] = a[n];
    l->size = length;
    l->capacity = cap;
}

void clearSeqList(SeqList *l) {
    free(l->arr);
    initSeqList(l);
}

void destroySeqList(SeqList *l) {
    free(l->arr);
    l->arr = NULL;
    l->size = 0;
    l->capacity = 0;
}

bool isSeqListEmpty(const SeqList *l) {
    return l->size == 0;
}

size_t lengthOfSeqList(const SeqList *l) {
    return l->size;
}

ElementType getFromSeqList(const SeqList *l, size_t i) {
    if (i >= l->size) {
        fprintf(stderr, "Index %zu out of bounds (size = %zu)\n", i, l->size);
        exit(EXIT_FAILURE);
    }
    return l->arr[i];
}

void insertBack2SeqList(SeqList *l, ElementType x) {
    if (l->size == l->capacity)
        expandSeqList(l);
    l->arr[l->size++] = x;
}

void insert2SeqList(SeqList *l, size_t i, ElementType x) {
    if (i > l->size) {
        fprintf(stderr, "Insert position %zu invalid (size = %zu)\n", i, l->size);
        exit(EXIT_FAILURE);
    }
    if (l->size == l->capacity)
        expandSeqList(l);
    for (size_t n = l->size; n > i; --n)
        l->arr[n] = l->arr[n - 1];
    l->arr[i] = x;
    ++l->size;
}

void removeFromSeqList(SeqList *l, size_t i) {
    if (i >= l->size) {
        fprintf(stderr, "Remove position %zu invalid (size = %zu)\n", i, l->size);
        exit(EXIT_FAILURE);
    }
    for (size_t n = i; n + 1 < l->size; ++n)
        l->arr[n] = l->arr[n + 1];
    --l->size;
    if (l->size * 4 <= l->capacity && l->capacity > g_initCap)
        curtailSeqList(l);
}

int indexOfSeqList(const SeqList *l, ElementType x) {
    for (size_t n = 0; n < l->size; ++n)
        if (l->arr[n] == x)
            return (int)n;
    return -1;
}

void printSeqList(const SeqList *l) {
    printf("cap: %zu  size: %zu ==>", l->capacity, l->size);
    for (size_t i = 0; i < l->size; ++i)
        printf(" [%zu]=%d", i, l->arr[i]);
    printf("\n");
}

static void expandSeqList(SeqList *l) {
    size_t newCap = l->capacity ? l->capacity * 2 : g_initCap;
    ElementType *newArr =
        (ElementType *)realloc(l->arr, sizeof(ElementType) * newCap);
    if (!newArr) {
        perror("Expansion failed");
        exit(EXIT_FAILURE);
    }
    l->arr = newArr;
    l->capacity = newCap;
}

static void curtailSeqList(SeqList *l) {
    if (l->capacity <= g_initCap)
        return;
    size_t newCap = l->capacity / 2;
    if (newCap < g_initCap)
        newCap = g_initCap;
    ElementType *newArr =
        (ElementType *)realloc(l->arr, sizeof(ElementType) * newCap);
    if (!newArr) {
        perror("Curtailment failed");
        exit(EXIT_FAILURE);
    }
    l->arr = newArr;
    l->capacity = newCap;
}

int main(void) {
    SeqList list;
    initSeqList(&list);

    insertBack2SeqList(&list, 10);
    insertBack2SeqList(&list, 20);
    insertBack2SeqList(&list, 30);
    insert2SeqList(&list, 1, 15);

    printSeqList(&list);

    removeFromSeqList(&list, 2);
    printSeqList(&list);

    printf("Index of 15: %d\n", indexOfSeqList(&list, 15));
    printf("List length: %zu\n", lengthOfSeqList(&list));

    clearSeqList(&list);
    printf("Is empty: %s\n", isSeqListEmpty(&list) ? "true" : "false");

    destroySeqList(&list);
    return EXIT_SUCCESS;
}

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

3. 链表 (Linked List)

3.1 基本概念

上一节中，我们实现了一个简易的顺序表；但是某些操作很麻烦，比如删除元素和插入元素，需要将后面所有元素左移或右移。链式存储使用指针连接结点，更适合频繁的插入、删除操作。

3.2 实现

3.2.1 单链表

结构体定义

typedef int ElementType;

typedef struct SListNode {
    ElementType value;
    struct SListNode *next;
} SListNode;

typedef struct {
    SListNode *head;
    size_t size;
} SinglyLinkedList;

创建节点工具函数

static SListNode *createNode(ElementType value) {
    SListNode *node = (SListNode *)malloc(sizeof(SListNode));
    if (!node) {
        perror("Create node failed");
        exit(EXIT_FAILURE);
    }
    node->value = value;
    node->next = NULL;
    return node;
}

初始化、判空与长度

void initSList(SinglyLinkedList *list) {
    list->head = NULL;
    list->size = 0;
}

bool isSListEmpty(const SinglyLinkedList *list) {
    return list->size == 0;
}

size_t sizeOfSList(const SinglyLinkedList *list) {
    return list->size;
}

插入操作：头插、尾插、任意结点后插

void pushFrontSList(SinglyLinkedList *list, ElementType value) {
    SListNode *node = createNode(value);
    node->next = list->head;
    list->head = node;
    ++list->size;
}

void pushBackSList(SinglyLinkedList *list, ElementType value) {
    SListNode *node = createNode(value);
    if (!list->head) {
        list->head = node;
    } else {
        SListNode *cur = list->head;
        while (cur->next)
            cur = cur->next;
        cur->next = node;
    }
    ++list->size;
}

void insertAfterSList(SinglyLinkedList *list, SListNode *position, ElementType value) {
    if (!position) {
        pushFrontSList(list, value);
        return;
    }
    SListNode *node = createNode(value);
    node->next = position->next;
    position->next = node;
    ++list->size;
}

删除操作：头删、删除指定结点之后的结点

ElementType popFrontSList(SinglyLinkedList *list) {
    if (isSListEmpty(list)) {
        fprintf(stderr, "Pop from empty list\n");
        exit(EXIT_FAILURE);
    }
    SListNode *node = list->head;
    ElementType value = node->value;
    list->head = node->next;
    free(node);
    --list->size;
    return value;
}

void removeAfterSList(SinglyLinkedList *list, SListNode *position) {
    if (!position || !position->next) {
        fprintf(stderr, "RemoveAfter position invalid\n");
        exit(EXIT_FAILURE);
    }
    SListNode *node = position->next;
    position->next = node->next;
    free(node);
    --list->size;
}

查找、遍历、销毁

SListNode *findSList(const SinglyLinkedList *list, ElementType value) {
    for (SListNode *cur = list->head; cur; cur = cur->next)
        if (cur->value == value)
            return cur;
    return NULL;
}

void printSList(const SinglyLinkedList *list) {
    printf("size: %zu ==> ", list->size);
    for (SListNode *cur = list->head; cur; cur = cur->next)
        printf("%d -> ", cur->value);
    printf("NULL\n");
}

void destroySList(SinglyLinkedList *list) {
    SListNode *cur = list->head;
    while (cur) {
        SListNode *next = cur->next;
        free(cur);
        cur = next;
    }
    list->head = NULL;
    list->size = 0;
}

完整示例代码

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

typedef int ElementType;

typedef struct SListNode {
    ElementType value;
    struct SListNode *next;
} SListNode;

typedef struct {
    SListNode *head;
    size_t size;
} SinglyLinkedList;

static SListNode *createNode(ElementType value);

void initSList(SinglyLinkedList *list);
bool isSListEmpty(const SinglyLinkedList *list);
size_t sizeOfSList(const SinglyLinkedList *list);
void pushFrontSList(SinglyLinkedList *list, ElementType value);
void pushBackSList(SinglyLinkedList *list, ElementType value);
void insertAfterSList(SinglyLinkedList *list, SListNode *position, ElementType value);
ElementType popFrontSList(SinglyLinkedList *list);
void removeAfterSList(SinglyLinkedList *list, SListNode *position);
SListNode *findSList(const SinglyLinkedList *list, ElementType value);
void printSList(const SinglyLinkedList *list);
void destroySList(SinglyLinkedList *list);

static SListNode *createNode(ElementType value) {
    SListNode *node = (SListNode *)malloc(sizeof(SListNode));
    if (!node) {
        perror("Create node failed");
        exit(EXIT_FAILURE);
    }
    node->value = value;
    node->next = NULL;
    return node;
}

void initSList(SinglyLinkedList *list) {
    list->head = NULL;
    list->size = 0;
}

bool isSListEmpty(const SinglyLinkedList *list) {
    return list->size == 0;
}

size_t sizeOfSList(const SinglyLinkedList *list) {
    return list->size;
}

void pushFrontSList(SinglyLinkedList *list, ElementType value) {
    SListNode *node = createNode(value);
    node->next = list->head;
    list->head = node;
    ++list->size;
}

void pushBackSList(SinglyLinkedList *list, ElementType value) {
    SListNode *node = createNode(value);
    if (!list->head) {
        list->head = node;
    } else {
        SListNode *cur = list->head;
        while (cur->next)
            cur = cur->next;
        cur->next = node;
    }
    ++list->size;
}

void insertAfterSList(SinglyLinkedList *list, SListNode *position, ElementType value) {
    if (!position) {
        pushFrontSList(list, value);
        return;
    }
    SListNode *node = createNode(value);
    node->next = position->next;
    position->next = node;
    ++list->size;
}

ElementType popFrontSList(SinglyLinkedList *list) {
    if (isSListEmpty(list)) {
        fprintf(stderr, "Pop from empty list\n");
        exit(EXIT_FAILURE);
    }
    SListNode *node = list->head;
    ElementType value = node->value;
    list->head = node->next;
    free(node);
    --list->size;
    return value;
}

void removeAfterSList(SinglyLinkedList *list, SListNode *position) {
    if (!position || !position->next) {
        fprintf(stderr, "RemoveAfter position invalid\n");
        exit(EXIT_FAILURE);
    }
    SListNode *node = position->next;
    position->next = node->next;
    free(node);
    --list->size;
}

SListNode *findSList(const SinglyLinkedList *list, ElementType value) {
    for (SListNode *cur = list->head; cur; cur = cur->next)
        if (cur->value == value)
            return cur;
    return NULL;
}

void printSList(const SinglyLinkedList *list) {
    printf("size: %zu ==> ", list->size);
    for (SListNode *cur = list->head; cur; cur = cur->next)
        printf("%d -> ", cur->value);
    printf("NULL\n");
}

void destroySList(SinglyLinkedList *list) {
    SListNode *cur = list->head;
    while (cur) {
        SListNode *next = cur->next;
        free(cur);
        cur = next;
    }
    list->head = NULL;
    list->size = 0;
}

int main(void) {
    SinglyLinkedList list;
    initSList(&list);

    pushBackSList(&list, 1);
    pushBackSList(&list, 2);
    pushFrontSList(&list, 0);
    printSList(&list);

    SListNode *node = findSList(&list, 1);
    insertAfterSList(&list, node, 5);
    printSList(&list);

    ElementType removed = popFrontSList(&list);
    printf("popFront: %d\n", removed);
    printSList(&list);

    destroySList(&list);
    return EXIT_SUCCESS;
}

3.2.2 双链表

结构体定义

typedef int ElementType;

typedef struct DListNode {
    ElementType value;
    struct DListNode *prev;
    struct DListNode *next;
} DListNode;

typedef struct {
    DListNode *head;
    DListNode *tail;
    size_t size;
} DoublyLinkedList;

创建节点工具函数

static DListNode *createDNode(ElementType value) {
    DListNode *node = (DListNode *)malloc(sizeof(DListNode));
    if (!node) {
        perror("Create node failed");
        exit(EXIT_FAILURE);
    }
    node->value = value;
    node->prev = node->next = NULL;
    return node;
}

初始化、判空与长度

void initDList(DoublyLinkedList *list) {
    list->head = list->tail = NULL;
    list->size = 0;
}

bool isDListEmpty(const DoublyLinkedList *list) {
    return list->size == 0;
}

size_t sizeOfDList(const DoublyLinkedList *list) {
    return list->size;
}

插入操作：头插、尾插、在某结点前/后插入

void pushFrontDList(DoublyLinkedList *list, ElementType value) {
    DListNode *node = createDNode(value);
    node->next = list->head;
    if (list->head)
        list->head->prev = node;
    list->head = node;
    if (!list->tail)
        list->tail = node;
    ++list->size;
}

void pushBackDList(DoublyLinkedList *list, ElementType value) {
    DListNode *node = createDNode(value);
    node->prev = list->tail;
    if (list->tail)
        list->tail->next = node;
    list->tail = node;
    if (!list->head)
        list->head = node;
    ++list->size;
}

void insertAfterDList(DoublyLinkedList *list, DListNode *position, ElementType value) {
    if (!position) {
        pushFrontDList(list, value);
        return;
    }
    DListNode *node = createDNode(value);
    node->prev = position;
    node->next = position->next;
    if (position->next)
        position->next->prev = node;
    position->next = node;
    if (list->tail == position)
        list->tail = node;
    ++list->size;
}

void insertBeforeDList(DoublyLinkedList *list, DListNode *position, ElementType value) {
    if (!position) {
        pushFrontDList(list, value);
        return;
    }
    if (position == list->head) {
        pushFrontDList(list, value);
        return;
    }
    DListNode *node = createDNode(value);
    node->next = position;
    node->prev = position->prev;
    position->prev->next = node;
    position->prev = node;
    ++list->size;
}

删除操作：头删、尾删、删除指定结点

ElementType popFrontDList(DoublyLinkedList *list) {
    if (isDListEmpty(list)) {
        fprintf(stderr, "Pop front on empty list\n");
        exit(EXIT_FAILURE);
    }
    DListNode *node = list->head;
    ElementType value = node->value;
    list->head = node->next;
    if (list->head)
        list->head->prev = NULL;
    else
        list->tail = NULL;
    free(node);
    --list->size;
    return value;
}

ElementType popBackDList(DoublyLinkedList *list) {
    if (isDListEmpty(list)) {
        fprintf(stderr, "Pop back on empty list\n");
        exit(EXIT_FAILURE);
    }
    DListNode *node = list->tail;
    ElementType value = node->value;
    list->tail = node->prev;
    if (list->tail)
        list->tail->next = NULL;
    else
        list->head = NULL;
    free(node);
    --list->size;
    return value;
}

void removeNodeDList(DoublyLinkedList *list, DListNode *node) {
    if (!node) {
        fprintf(stderr, "Remove null node\n");
        exit(EXIT_FAILURE);
    }
    if (node == list->head)
        list->head = node->next;
    else
        node->prev->next = node->next;
    if (node == list->tail)
        list->tail = node->prev;
    else
        node->next->prev = node->prev;
    free(node);
    --list->size;
}

查找、遍历（正向、反向）、销毁

DListNode *findDList(const DoublyLinkedList *list, ElementType value) {
    for (DListNode *cur = list->head; cur; cur = cur->next)
        if (cur->value == value)
            return cur;
    return NULL;
}

void printForwardDList(const DoublyLinkedList *list) {
    printf("Forward(size=%zu): ", list->size);
    for (DListNode *cur = list->head; cur; cur = cur->next)
        printf("%d <-> ", cur->value);
    printf("NULL\n");
}

void printBackwardDList(const DoublyLinkedList *list) {
    printf("Backward(size=%zu): ", list->size);
    for (DListNode *cur = list->tail; cur; cur = cur->prev)
        printf("%d <-> ", cur->value);
    printf("NULL\n");
}

void destroyDList(DoublyLinkedList *list) {
    DListNode *cur = list->head;
    while (cur) {
        DListNode *next = cur->next;
        free(cur);
        cur = next;
    }
    list->head = list->tail = NULL;
    list->size = 0;
}

完整示例代码

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

typedef int ElementType;

typedef struct DListNode {
    ElementType value;
    struct DListNode *prev;
    struct DListNode *next;
} DListNode;

typedef struct {
    DListNode *head;
    DListNode *tail;
    size_t size;
} DoublyLinkedList;

static DListNode *createDNode(ElementType value);

void initDList(DoublyLinkedList *list);
bool isDListEmpty(const DoublyLinkedList *list);
size_t sizeOfDList(const DoublyLinkedList *list);
void pushFrontDList(DoublyLinkedList *list, ElementType value);
void pushBackDList(DoublyLinkedList *list, ElementType value);
void insertAfterDList(DoublyLinkedList *list, DListNode *position, ElementType value);
void insertBeforeDList(DoublyLinkedList *list, DListNode *position, ElementType value);
ElementType popFrontDList(DoublyLinkedList *list);
ElementType popBackDList(DoublyLinkedList *list);
void removeNodeDList(DoublyLinkedList *list, DListNode *node);
DListNode *findDList(const DoublyLinkedList *list, ElementType value);
void printForwardDList(const DoublyLinkedList *list);
void printBackwardDList(const DoublyLinkedList *list);
void destroyDList(DoublyLinkedList *list);

static DListNode *createDNode(ElementType value) {
    DListNode *node = (DListNode *)malloc(sizeof(DListNode));
    if (!node) {
        perror("Create node failed");
        exit(EXIT_FAILURE);
    }
    node->value = value;
    node->prev = node->next = NULL;
    return node;
}

void initDList(DoublyLinkedList *list) {
    list->head = list->tail = NULL;
    list->size = 0;
}

bool isDListEmpty(const DoublyLinkedList *list) {
    return list->size == 0;
}

size_t sizeOfDList(const DoublyLinkedList *list) {
    return list->size;
}

void pushFrontDList(DoublyLinkedList *list, ElementType value) {
    DListNode *node = createDNode(value);
    node->next = list->head;
    if (list->head)
        list->head->prev = node;
    list->head = node;
    if (!list->tail)
        list->tail = node;
    ++list->size;
}

void pushBackDList(DoublyLinkedList *list, ElementType value) {
    DListNode *node = createDNode(value);
    node->prev = list->tail;
    if (list->tail)
        list->tail->next = node;
    list->tail = node;
    if (!list->head)
        list->head = node;
    ++list->size;
}

void insertAfterDList(DoublyLinkedList *list, DListNode *position, ElementType value) {
    if (!position) {
        pushFrontDList(list, value);
        return;
    }
    DListNode *node = createDNode(value);
    node->prev = position;
    node->next = position->next;
    if (position->next)
        position->next->prev = node;
    position->next = node;
    if (list->tail == position)
        list->tail = node;
    ++list->size;
}

void insertBeforeDList(DoublyLinkedList *list, DListNode *position, ElementType value) {
    if (!position || position == list->head) {
        pushFrontDList(list, value);
        return;
    }
    DListNode *node = createDNode(value);
    node->prev = position->prev;
    node->next = position;
    position->prev->next = node;
    position->prev = node;
    ++list->size;
}

ElementType popFrontDList(DoublyLinkedList *list) {
    if (isDListEmpty(list)) {
        fprintf(stderr, "Pop front on empty list\n");
        exit(EXIT_FAILURE);
    }
    DListNode *node = list->head;
    ElementType value = node->value;
    list->head = node->next;
    if (list->head)
        list->head->prev = NULL;
    else
        list->tail = NULL;
    free(node);
    --list->size;
    return value;
}

ElementType popBackDList(DoublyLinkedList *list) {
    if (isDListEmpty(list)) {
        fprintf(stderr, "Pop back on empty list\n");
        exit(EXIT_FAILURE);
    }
    DListNode *node = list->tail;
    ElementType value = node->value;
    list->tail = node->prev;
    if (list->tail)
        list->tail->next = NULL;
    else
        list->head = NULL;
    free(node);
    --list->size;
    return value;
}

void removeNodeDList(DoublyLinkedList *list, DListNode *node) {
    if (!node) {
        fprintf(stderr, "Remove null node\n");
        exit(EXIT_FAILURE);
    }
    if (node == list->head)
        list->head = node->next;
    else
        node->prev->next = node->next;
    if (node == list->tail)
        list->tail = node->prev;
    else
        node->next->prev = node->prev;
    free(node);
    --list->size;
}

DListNode *findDList(const DoublyLinkedList *list, ElementType value) {
    for (DListNode *cur = list->head; cur; cur = cur->next)
        if (cur->value == value)
            return cur;
    return NULL;
}

void printForwardDList(const DoublyLinkedList *list) {
    printf("Forward(size=%zu): ", list->size);
    for (DListNode *cur = list->head; cur; cur = cur->next)
        printf("%d <-> ", cur->value);
    printf("NULL\n");
}

void printBackwardDList(const DoublyLinkedList *list) {
    printf("Backward(size=%zu): ", list->size);
    for (DListNode *cur = list->tail; cur; cur = cur->prev)
        printf("%d <-> ", cur->value);
    printf("NULL\n");
}

void destroyDList(DoublyLinkedList *list) {
    DListNode *cur = list->head;
    while (cur) {
        DListNode *next = cur->next;
        free(cur);
        cur = next;
    }
    list->head = list->tail = NULL;
    list->size = 0;
}

int main(void) {
    DoublyLinkedList list;
    initDList(&list);

    pushBackDList(&list, 1);
    pushBackDList(&list, 2);
    pushFrontDList(&list, 0);
    printForwardDList(&list);
    printBackwardDList(&list);

    DListNode *node = findDList(&list, 1);
    insertAfterDList(&list, node, 5);
    printForwardDList(&list);

    popFrontDList(&list);
    popBackDList(&list);
    printForwardDList(&list);

    destroyDList(&list);
    return EXIT_SUCCESS;
}

3.2.3 循环链表

循环链表的尾结点 next 指针指向头结点，实现首尾相连。

结构体定义（使用尾指针方便操作）

typedef int ElementType;

typedef struct CListNode {
    ElementType value;
    struct CListNode *next;
} CListNode;

typedef struct {
    CListNode *tail; // tail->next 即为头指针
    size_t size;
} CircularLinkedList;

创建节点工具函数

static CListNode *createCNode(ElementType value) {
    CListNode *node = (CListNode *)malloc(sizeof(CListNode));
    if (!node) {
        perror("Create node failed");
        exit(EXIT_FAILURE);
    }
    node->value = value;
    node->next = NULL;
    return node;
}

初始化、判空与长度

void initCList(CircularLinkedList *list) {
    list->tail = NULL;
    list->size = 0;
}

bool isCListEmpty(const CircularLinkedList *list) {
    return list->size == 0;
}

size_t sizeOfCList(const CircularLinkedList *list) {
    return list->size;
}

插入操作：头插、尾插、在某结点后插

void pushFrontCList(CircularLinkedList *list, ElementType value) {
    CListNode *node = createCNode(value);
    if (!list->tail) {
        node->next = node;
        list->tail = node;
    } else {
        node->next = list->tail->next;
        list->tail->next = node;
    }
    ++list->size;
}

void pushBackCList(CircularLinkedList *list, ElementType value) {
    pushFrontCList(list, value);
    list->tail = list->tail->next;
}

void insertAfterCList(CircularLinkedList *list, CListNode *position, ElementType value) {
    if (!position) {
        pushFrontCList(list, value);
        return;
    }
    CListNode *node = createCNode(value);
    node->next = position->next;
    position->next = node;
    if (position == list->tail)
        list->tail = node;
    ++list->size;
}

删除操作：头删、删指定结点后继、查找前驱辅助函数

ElementType popFrontCList(CircularLinkedList *list) {
    if (isCListEmpty(list)) {
        fprintf(stderr, "Pop front on empty circular list\n");
        exit(EXIT_FAILURE);
    }
    CListNode *head = list->tail->next;
    ElementType value = head->value;
    if (head == list->tail) {
        list->tail = NULL;
    } else {
        list->tail->next = head->next;
    }
    free(head);
    --list->size;
    return value;
}

CListNode *findCList(const CircularLinkedList *list, ElementType value) {
    if (!list->tail)
        return NULL;
    CListNode *cur = list->tail->next;
    do {
        if (cur->value == value)
            return cur;
        cur = cur->next;
    } while (cur != list->tail->next);
    return NULL;
}

void removeAfterCList(CircularLinkedList *list, CListNode *position) {
    if (!position || isCListEmpty(list)) {
        fprintf(stderr, "RemoveAfter invalid\n");
        exit(EXIT_FAILURE);
    }
    CListNode *target = position->next;
    if (target == position) { // 仅一个结点
        list->tail = NULL;
    } else {
        position->next = target->next;
        if (target == list->tail)
            list->tail = position;
    }
    free(target);
    --list->size;
}

遍历、销毁

void printCList(const CircularLinkedList *list) {
    if (isCListEmpty(list)) {
        printf("CircularList(size=0): NULL\n");
        return;
    }
    printf("CircularList(size=%zu): ", list->size);
    CListNode *cur = list->tail->next;
    do {
        printf("%d -> ", cur->value);
        cur = cur->next;
    } while (cur != list->tail->next);
    printf("(back to head)\n");
}

void destroyCList(CircularLinkedList *list) {
    if (!list->tail)
        return;
    CListNode *cur = list->tail->next;
    while (cur != list->tail) {
        CListNode *next = cur->next;
        free(cur);
        cur = next;
    }
    free(list->tail);
    list->tail = NULL;
    list->size = 0;
}

完整示例代码

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

typedef int ElementType;

typedef struct CListNode {
    ElementType value;
    struct CListNode *next;
} CListNode;

typedef struct {
    CListNode *tail;
    size_t size;
} CircularLinkedList;

static CListNode *createCNode(ElementType value);

void initCList(CircularLinkedList *list);
bool isCListEmpty(const CircularLinkedList *list);
size_t sizeOfCList(const CircularLinkedList *list);
void pushFrontCList(CircularLinkedList *list, ElementType value);
void pushBackCList(CircularLinkedList *list, ElementType value);
void insertAfterCList(CircularLinkedList *list, CListNode *position, ElementType value);
ElementType popFrontCList(CircularLinkedList *list);
CListNode *findCList(const CircularLinkedList *list, ElementType value);
void removeAfterCList(CircularLinkedList *list, CListNode *position);
void printCList(const CircularLinkedList *list);
void destroyCList(CircularLinkedList *list);

static CListNode *createCNode(ElementType value) {
    CListNode *node = (CListNode *)malloc(sizeof(CListNode));
    if (!node) {
        perror("Create node failed");
        exit(EXIT_FAILURE);
    }
    node->value = value;
    node->next = NULL;
    return node;
}

void initCList(CircularLinkedList *list) {
    list->tail = NULL;
    list->size = 0;
}

bool isCListEmpty(const CircularLinkedList *list) {
    return list->size == 0;
}

size_t sizeOfCList(const CircularLinkedList *list) {
    return list->size;
}

void pushFrontCList(CircularLinkedList *list, ElementType value) {
    CListNode *node = createCNode(value);
    if (!list->tail) {
        node->next = node;
        list->tail = node;
    } else {
        node->next = list->tail->next;
        list->tail->next = node;
    }
    ++list->size;
}

void pushBackCList(CircularLinkedList *list, ElementType value) {
    pushFrontCList(list, value);
    list->tail = list->tail->next;
}

void insertAfterCList(CircularLinkedList *list, CListNode *position, ElementType value) {
    if (!position) {
        pushFrontCList(list, value);
        return;
    }
    CListNode *node = createCNode(value);
    node->next = position->next;
    position->next = node;
    if (position == list->tail)
        list->tail = node;
    ++list->size;
}

ElementType popFrontCList(CircularLinkedList *list) {
    if (isCListEmpty(list)) {
        fprintf(stderr, "Pop front on empty circular list\n");
        exit(EXIT_FAILURE);
    }
    CListNode *head = list->tail->next;
    ElementType value = head->value;
    if (head == list->tail) {
        list->tail = NULL;
    } else {
        list->tail->next = head->next;
    }
    free(head);
    --list->size;
    return value;
}

CListNode *findCList(const CircularLinkedList *list, ElementType value) {
    if (!list->tail)
        return NULL;
    CListNode *cur = list->tail->next;
    do {
        if (cur->value == value)
            return cur;
        cur = cur->next;
    } while (cur != list->tail->next);
    return NULL;
}

void removeAfterCList(CircularLinkedList *list, CListNode *position) {
    if (!position || isCListEmpty(list)) {
        fprintf(stderr, "RemoveAfter invalid\n");
        exit(EXIT_FAILURE);
    }
    CListNode *target = position->next;
    if (target == position) {
        list->tail = NULL;
    } else {
        position->next = target->next;
        if (target == list->tail)
            list->tail = position;
    }
    free(target);
    --list->size;
}

void printCList(const CircularLinkedList *list) {
    if (isCListEmpty(list)) {
        printf("CircularList(size=0): NULL\n");
        return;
    }
    printf("CircularList(size=%zu): ", list->size);
    CListNode *cur = list->tail->next;
    do {
        printf("%d -> ", cur->value);
        cur = cur->next;
    } while (cur != list->tail->next);
    printf("(back to head)\n");
}

void destroyCList(CircularLinkedList *list) {
    if (!list->tail)
        return;
    CListNode *cur = list->tail->next;
    while (cur != list->tail) {
        CListNode *next = cur->next;
        free(cur);
        cur = next;
    }
    free(list->tail);
    list->tail = NULL;
    list->size = 0;
}

int main(void) {
    CircularLinkedList list;
    initCList(&list);

    pushBackCList(&list, 10);
    pushBackCList(&list, 20);
    pushBackCList(&list, 30);
    printCList(&list);

    CListNode *node = findCList(&list, 20);
    insertAfterCList(&list, node, 25);
    printCList(&list);

    popFrontCList(&list);
    printCList(&list);

    destroyCList(&list);
    return EXIT_SUCCESS;
}

3.3 顺序表和链表的对比

占用空间：顺序表需要连续内存，扩容/缩容需要重新分配；链表动态分配，额外指针开销。
随机访问：顺序表支持 O(1) 随机访问；链表为 O(n)。
插入/删除：顺序表插入删除需要大量移动元素；链表在已定位时可 O(1) 完成。

4. 栈 (Stack)

4.1 基本概念

栈是一种只允许在表尾进行插入和删除操作的线性表。
上一条的“表尾”一般称作栈顶；另一端称作栈底。
在栈顶位置插入元素的操作叫做压栈（入栈，进栈）。
删除栈顶元素的操作叫做出栈（弹栈，退栈）。
可以用数组和链表实现栈。

4.2 实现

4.2.1 用数组实现

数组栈利用顺序表思想，在固定或可扩展数组上维护“栈顶”位置。典型操作：

initArrayStack：初始化容量、栈顶索引；
isArrayStackEmpty / sizeOfArrayStack：判空与获取当前元素个数；
pushArrayStack：如有必要扩容后入栈；
popArrayStack：弹出栈顶，必要时缩容；
peekArrayStack：读取栈顶但不删除；
destroyArrayStack：释放内存。

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

typedef int ElementType;

typedef struct {
    ElementType *data;
    size_t top;
    size_t capacity;
} ArrayStack;

static const size_t g_stackInitCap = 8;

void initArrayStack(ArrayStack *s);
bool isArrayStackEmpty(const ArrayStack *s);
size_t sizeOfArrayStack(const ArrayStack *s);
void pushArrayStack(ArrayStack *s, ElementType value);
ElementType popArrayStack(ArrayStack *s);
ElementType peekArrayStack(const ArrayStack *s);
void destroyArrayStack(ArrayStack *s);

static void expandArrayStack(ArrayStack *s);
static void shrinkArrayStack(ArrayStack *s);

void initArrayStack(ArrayStack *s) {
    s->data = (ElementType *)malloc(sizeof(ElementType) * g_stackInitCap);
    if (!s->data) {
        perror("ArrayStack init failed");
        exit(EXIT_FAILURE);
    }
    s->top = 0;
    s->capacity = g_stackInitCap;
}

bool isArrayStackEmpty(const ArrayStack *s) {
    return s->top == 0;
}

size_t sizeOfArrayStack(const ArrayStack *s) {
    return s->top;
}

void pushArrayStack(ArrayStack *s, ElementType value) {
    if (s->top == s->capacity)
        expandArrayStack(s);
    s->data[s->top++] = value;
}

ElementType popArrayStack(ArrayStack *s) {
    if (isArrayStackEmpty(s)) {
        fprintf(stderr, "Pop from empty stack\n");
        exit(EXIT_FAILURE);
    }
    ElementType value = s->data[--s->top];
    if (s->top * 4 <= s->capacity && s->capacity > g_stackInitCap)
        shrinkArrayStack(s);
    return value;
}

ElementType peekArrayStack(const ArrayStack *s) {
    if (isArrayStackEmpty(s)) {
        fprintf(stderr, "Peek from empty stack\n");
        exit(EXIT_FAILURE);
    }
    return s->data[s->top - 1];
}

void destroyArrayStack(ArrayStack *s) {
    free(s->data);
    s->data = NULL;
    s->top = 0;
    s->capacity = 0;
}

static void expandArrayStack(ArrayStack *s) {
    size_t newCap = s->capacity ? s->capacity * 2 : g_stackInitCap;
    ElementType *newData =
        (ElementType *)realloc(s->data, sizeof(ElementType) * newCap);
    if (!newData) {
        perror("ArrayStack expansion failed");
        exit(EXIT_FAILURE);
    }
    s->data = newData;
    s->capacity = newCap;
}

static void shrinkArrayStack(ArrayStack *s) {
    size_t newCap = s->capacity / 2;
    if (newCap < g_stackInitCap)
        newCap = g_stackInitCap;
    ElementType *newData =
        (ElementType *)realloc(s->data, sizeof(ElementType) * newCap);
    if (!newData) {
        perror("ArrayStack shrink failed");
        exit(EXIT_FAILURE);
    }
    s->data = newData;
    s->capacity = newCap;
}

int main(void) {
    ArrayStack stack;
    initArrayStack(&stack);

    pushArrayStack(&stack, 10);
    pushArrayStack(&stack, 20);
    pushArrayStack(&stack, 30);

    printf("peek: %d\n", peekArrayStack(&stack));
    printf("pop: %d\n", popArrayStack(&stack));
    printf("size: %zu\n", sizeOfArrayStack(&stack));

    while (!isArrayStackEmpty(&stack))
        printf("pop: %d\n", popArrayStack(&stack));

    destroyArrayStack(&stack);
    return EXIT_SUCCESS;
}

4.2.2 用链表实现

链式栈利用单链表的头插/头删实现压栈与弹栈，优势是无需整段移动，也不必关心扩容。

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

typedef int ElementType;

typedef struct ListStackNode {
    ElementType value;
    struct ListStackNode *next;
} ListStackNode;

typedef struct {
    ListStackNode *head;
    size_t size;
} ListStack;

static ListStackNode *createStackNode(ElementType value);

void initListStack(ListStack *s);
bool isListStackEmpty(const ListStack *s);
size_t sizeOfListStack(const ListStack *s);
void pushListStack(ListStack *s, ElementType value);
ElementType popListStack(ListStack *s);
ElementType peekListStack(const ListStack *s);
void destroyListStack(ListStack *s);

static ListStackNode *createStackNode(ElementType value) {
    ListStackNode *node = (ListStackNode *)malloc(sizeof(ListStackNode));
    if (!node) {
        perror("ListStack node alloc failed");
        exit(EXIT_FAILURE);
    }
    node->value = value;
    node->next = NULL;
    return node;
}

void initListStack(ListStack *s) {
    s->head = NULL;
    s->size = 0;
}

bool isListStackEmpty(const ListStack *s) {
    return s->size == 0;
}

size_t sizeOfListStack(const ListStack *s) {
    return s->size;
}

void pushListStack(ListStack *s, ElementType value) {
    ListStackNode *node = createStackNode(value);
    node->next = s->head;
    s->head = node;
    ++s->size;
}

ElementType popListStack(ListStack *s) {
    if (isListStackEmpty(s)) {
        fprintf(stderr, "Pop from empty list stack\n");
        exit(EXIT_FAILURE);
    }
    ListStackNode *node = s->head;
    ElementType value = node->value;
    s->head = node->next;
    free(node);
    --s->size;
    return value;
}

ElementType peekListStack(const ListStack *s) {
    if (isListStackEmpty(s)) {
        fprintf(stderr, "Peek from empty list stack\n");
        exit(EXIT_FAILURE);
    }
    return s->head->value;
}

void destroyListStack(ListStack *s) {
    ListStackNode *cur = s->head;
    while (cur) {
        ListStackNode *next = cur->next;
        free(cur);
        cur = next;
    }
    s->head = NULL;
    s->size = 0;
}

int main(void) {
    ListStack stack;
    initListStack(&stack);

    pushListStack(&stack, 100);
    pushListStack(&stack, 200);
    pushListStack(&stack, 300);

    printf("peek: %d\n", peekListStack(&stack));
    printf("pop: %d\n", popListStack(&stack));
    printf("size: %zu\n", sizeOfListStack(&stack));

    while (!isListStackEmpty(&stack))
        printf("pop: %d\n", popListStack(&stack));

    destroyListStack(&stack);
    return EXIT_SUCCESS;
}

5. 队列 (Queue)

5.1 基本概念

队列是一种只允许在一端插入、在另一端删除的线性表。
允许插入的一端称为队尾 (rear)，允许删除的一端称为队头 (front)。
插入操作称为入队，删除操作称为出队。
队列强调先进先出 (FIFO) 原则。
可以用数组（顺序存储）或链表（链式存储）实现。
常见扩展：循环队列、双端队列、优先队列等。

5.2 实现

5.2.1 用数组实现（循环队列）

结构体定义

typedef int ElementType;

typedef struct {
    ElementType *data;
    size_t front;
    size_t rear;
    size_t size;
    size_t capacity;
} ArrayQueue;

初始化、判空、判满、长度

static const size_t g_queueInitCap = 8;

void initArrayQueue(ArrayQueue *q) {
    q->data = (ElementType *)malloc(sizeof(ElementType) * g_queueInitCap);
    if (!q->data) {
        perror("Queue init failed");
        exit(EXIT_FAILURE);
    }
    q->front = q->rear = q->size = 0;
    q->capacity = g_queueInitCap;
}

bool isArrayQueueEmpty(const ArrayQueue *q) {
    return q->size == 0;
}

bool isArrayQueueFull(const ArrayQueue *q) {
    return q->size == q->capacity;
}

size_t sizeOfArrayQueue(const ArrayQueue *q) {
    return q->size;
}

扩容与缩容

static void expandArrayQueue(ArrayQueue *q) {
    size_t newCap = q->capacity * 2;
    ElementType *newData =
        (ElementType *)malloc(sizeof(ElementType) * newCap);
    if (!newData) {
        perror("Queue expansion failed");
        exit(EXIT_FAILURE);
    }
    for (size_t i = 0; i < q->size; ++i)
        newData[i] = q->data[(q->front + i) % q->capacity];
    free(q->data);
    q->data = newData;
    q->capacity = newCap;
    q->front = 0;
    q->rear = q->size;
}

static void shrinkArrayQueue(ArrayQueue *q) {
    if (q->capacity <= g_queueInitCap)
        return;
    size_t newCap = q->capacity / 2;
    if (newCap < g_queueInitCap)
        newCap = g_queueInitCap;
    ElementType *newData =
        (ElementType *)malloc(sizeof(ElementType) * newCap);
    if (!newData) {
        perror("Queue shrink failed");
        exit(EXIT_FAILURE);
    }
    for (size_t i = 0; i < q->size; ++i)
        newData[i] = q->data[(q->front + i) % q->capacity];
    free(q->data);
    q->data = newData;
    q->capacity = newCap;
    q->front = 0;
    q->rear = q->size;
}

入队、出队、取队头

void enqueueArrayQueue(ArrayQueue *q, ElementType value) {
    if (isArrayQueueFull(q))
        expandArrayQueue(q);
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % q->capacity;
    ++q->size;
}

ElementType dequeueArrayQueue(ArrayQueue *q) {
    if (isArrayQueueEmpty(q)) {
        fprintf(stderr, "Dequeue from empty queue\n");
        exit(EXIT_FAILURE);
    }
    ElementType value = q->data[q->front];
    q->front = (q->front + 1) % q->capacity;
    --q->size;
    if (q->size * 4 <= q->capacity && q->capacity > g_queueInitCap)
        shrinkArrayQueue(q);
    return value;
}

ElementType frontArrayQueue(const ArrayQueue *q) {
    if (isArrayQueueEmpty(q)) {
        fprintf(stderr, "Front from empty queue\n");
        exit(EXIT_FAILURE);
    }
    return q->data[q->front];
}

销毁与打印

void destroyArrayQueue(ArrayQueue *q) {
    free(q->data);
    q->data = NULL;
    q->front = q->rear = q->size = q->capacity = 0;
}

void printArrayQueue(const ArrayQueue *q) {
    printf("ArrayQueue(size=%zu, cap=%zu): ", q->size, q->capacity);
    for (size_t i = 0; i < q->size; ++i)
        printf("%d <- ", q->data[(q->front + i) % q->capacity]);
    printf("rear\n");
}

完整示例代码

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

typedef int ElementType;

typedef struct {
    ElementType *data;
    size_t front;
    size_t rear;
    size_t size;
    size_t capacity;
} ArrayQueue;

static const size_t g_queueInitCap = 8;

void initArrayQueue(ArrayQueue *q);
bool isArrayQueueEmpty(const ArrayQueue *q);
bool isArrayQueueFull(const ArrayQueue *q);
size_t sizeOfArrayQueue(const ArrayQueue *q);
void enqueueArrayQueue(ArrayQueue *q, ElementType value);
ElementType dequeueArrayQueue(ArrayQueue *q);
ElementType frontArrayQueue(const ArrayQueue *q);
void destroyArrayQueue(ArrayQueue *q);
void printArrayQueue(const ArrayQueue *q);

static void expandArrayQueue(ArrayQueue *q);
static void shrinkArrayQueue(ArrayQueue *q);

void initArrayQueue(ArrayQueue *q) {
    q->data = (ElementType *)malloc(sizeof(ElementType) * g_queueInitCap);
    if (!q->data) {
        perror("Queue init failed");
        exit(EXIT_FAILURE);
    }
    q->front = q->rear = q->size = 0;
    q->capacity = g_queueInitCap;
}

bool isArrayQueueEmpty(const ArrayQueue *q) {
    return q->size == 0;
}

bool isArrayQueueFull(const ArrayQueue *q) {
    return q->size == q->capacity;
}

size_t sizeOfArrayQueue(const ArrayQueue *q) {
    return q->size;
}

void enqueueArrayQueue(ArrayQueue *q, ElementType value) {
    if (isArrayQueueFull(q))
        expandArrayQueue(q);
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % q->capacity;
    ++q->size;
}

ElementType dequeueArrayQueue(ArrayQueue *q) {
    if (isArrayQueueEmpty(q)) {
        fprintf(stderr, "Dequeue from empty queue\n");
        exit(EXIT_FAILURE);
    }
    ElementType value = q->data[q->front];
    q->front = (q->front + 1) % q->capacity;
    --q->size;
    if (q->size * 4 <= q->capacity && q->capacity > g_queueInitCap)
        shrinkArrayQueue(q);
    return value;
}

ElementType frontArrayQueue(const ArrayQueue *q) {
    if (isArrayQueueEmpty(q)) {
        fprintf(stderr, "Front from empty queue\n");
        exit(EXIT_FAILURE);
    }
    return q->data[q->front];
}

void destroyArrayQueue(ArrayQueue *q) {
    free(q->data);
    q->data = NULL;
    q->front = q->rear = q->size = q->capacity = 0;
}

void printArrayQueue(const ArrayQueue *q) {
    printf("ArrayQueue(size=%zu, cap=%zu): ", q->size, q->capacity);
    for (size_t i = 0; i < q->size; ++i)
        printf("%d <- ", q->data[(q->front + i) % q->capacity]);
    printf("rear\n");
}

static void expandArrayQueue(ArrayQueue *q) {
    size_t newCap = q->capacity * 2;
    ElementType *newData =
        (ElementType *)malloc(sizeof(ElementType) * newCap);
    if (!newData) {
        perror("Queue expansion failed");
        exit(EXIT_FAILURE);
    }
    for (size_t i = 0; i < q->size; ++i)
        newData[i] = q->data[(q->front + i) % q->capacity];
    free(q->data);
    q->data = newData;
    q->capacity = newCap;
    q->front = 0;
    q->rear = q->size;
}

static void shrinkArrayQueue(ArrayQueue *q) {
    if (q->capacity <= g_queueInitCap)
        return;
    size_t newCap = q->capacity / 2;
    if (newCap < g_queueInitCap)
        newCap = g_queueInitCap;
    ElementType *newData =
        (ElementType *)malloc(sizeof(ElementType) * newCap);
    if (!newData) {
        perror("Queue shrink failed");
        exit(EXIT_FAILURE);
    }
    for (size_t i = 0; i < q->size; ++i)
        newData[i] = q->data[(q->front + i) % q->capacity];
    free(q->data);
    q->data = newData;
    q->capacity = newCap;
    q->front = 0;
    q->rear = q->size;
}

int main(void) {
    ArrayQueue queue;
    initArrayQueue(&queue);

    enqueueArrayQueue(&queue, 1);
    enqueueArrayQueue(&queue, 2);
    enqueueArrayQueue(&queue, 3);
    printArrayQueue(&queue);

    printf("front: %d\n", frontArrayQueue(&queue));
    printf("dequeue: %d\n", dequeueArrayQueue(&queue));
    printArrayQueue(&queue);

    destroyArrayQueue(&queue);
    return EXIT_SUCCESS;
}

5.2.2 用链表实现

结构体定义

typedef int ElementType;

typedef struct QListNode {
    ElementType value;
    struct QListNode *next;
} QListNode;

typedef struct {
    QListNode *front;
    QListNode *rear;
    size_t size;
} ListQueue;

工具函数与初始化

static QListNode *createQNode(ElementType value) {
    QListNode *node = (QListNode *)malloc(sizeof(QListNode));
    if (!node) {
        perror("Create queue node failed");
        exit(EXIT_FAILURE);
    }
    node->value = value;
    node->next = NULL;
    return node;
}

void initListQueue(ListQueue *q) {
    q->front = q->rear = NULL;
    q->size = 0;
}

bool isListQueueEmpty(const ListQueue *q) {
    return q->size == 0;
}

size_t sizeOfListQueue(const ListQueue *q) {
    return q->size;
}

入队、出队、取队头

void enqueueListQueue(ListQueue *q, ElementType value) {
    QListNode *node = createQNode(value);
    if (!q->rear) {
        q->front = q->rear = node;
    } else {
        q->rear->next = node;
        q->rear = node;
    }
    ++q->size;
}

ElementType dequeueListQueue(ListQueue *q) {
    if (isListQueueEmpty(q)) {
        fprintf(stderr, "Dequeue from empty list queue\n");
        exit(EXIT_FAILURE);
    }
    QListNode *node = q->front;
    ElementType value = node->value;
    q->front = node->next;
    if (!q->front)
        q->rear = NULL;
    free(node);
    --q->size;
    return value;
}

ElementType frontListQueue(const ListQueue *q) {
    if (isListQueueEmpty(q)) {
        fprintf(stderr, "Front from empty list queue\n");
        exit(EXIT_FAILURE);
    }
    return q->front->value;
}

遍历与销毁

void printListQueue(const ListQueue *q) {
    printf("ListQueue(size=%zu): ", q->size);
    for (QListNode *cur = q->front; cur; cur = cur->next)
        printf("%d <- ", cur->value);
    printf("rear\n");
}

void destroyListQueue(ListQueue *q) {
    QListNode *cur = q->front;
    while (cur) {
        QListNode *next = cur->next;
        free(cur);
        cur = next;
    }
    q->front = q->rear = NULL;
    q->size = 0;
}

完整示例代码

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

typedef int ElementType;

typedef struct QListNode {
    ElementType value;
    struct QListNode *next;
} QListNode;

typedef struct {
    QListNode *front;
    QListNode *rear;
    size_t size;
} ListQueue;

static QListNode *createQNode(ElementType value);

void initListQueue(ListQueue *q);
bool isListQueueEmpty(const ListQueue *q);
size_t sizeOfListQueue(const ListQueue *q);
void enqueueListQueue(ListQueue *q, ElementType value);
ElementType dequeueListQueue(ListQueue *q);
ElementType frontListQueue(const ListQueue *q);
void printListQueue(const ListQueue *q);
void destroyListQueue(ListQueue *q);

static QListNode *createQNode(ElementType value) {
    QListNode *node = (QListNode *)malloc(sizeof(QListNode));
    if (!node) {
        perror("Create queue node failed");
        exit(EXIT_FAILURE);
    }
    node->value = value;
    node->next = NULL;
    return node;
}

void initListQueue(ListQueue *q) {
    q->front = q->rear = NULL;
    q->size = 0;
}

bool isListQueueEmpty(const ListQueue *q) {
    return q->size == 0;
}

size_t sizeOfListQueue(const ListQueue *q) {
    return q->size;
}

void enqueueListQueue(ListQueue *q, ElementType value) {
    QListNode *node = createQNode(value);
    if (!q->rear) {
        q->front = q->rear = node;
    } else {
        q->rear->next = node;
        q->rear = node;
    }
    ++q->size;
}

ElementType dequeueListQueue(ListQueue *q) {
    if (isListQueueEmpty(q)) {
        fprintf(stderr, "Dequeue from empty list queue\n");
        exit(EXIT_FAILURE);
    }
    QListNode *node = q->front;
    ElementType value = node->value;
    q->front = node->next;
    if (!q->front)
        q->rear = NULL;
    free(node);
    --q->size;
    return value;
}

ElementType frontListQueue(const ListQueue *q) {
    if (isListQueueEmpty(q)) {
        fprintf(stderr, "Front from empty list queue\n");
        exit(EXIT_FAILURE);
    }
    return q->front->value;
}

void printListQueue(const ListQueue *q) {
    printf("ListQueue(size=%zu): ", q->size);
    for (QListNode *cur = q->front; cur; cur = cur->next)
        printf("%d <- ", cur->value);
    printf("rear\n");
}

void destroyListQueue(ListQueue *q) {
    QListNode *cur = q->front;
    while (cur) {
        QListNode *next = cur->next;
        free(cur);
        cur = next;
    }
    q->front = q->rear = NULL;
    q->size = 0;
}

int main(void) {
    ListQueue queue;
    initListQueue(&queue);

    enqueueListQueue(&queue, 5);
    enqueueListQueue(&queue, 6);
    enqueueListQueue(&queue, 7);
    printListQueue(&queue);

    printf("front: %d\n", frontListQueue(&queue));
    printf("dequeue: %d\n", dequeueListQueue(&queue));
    printListQueue(&queue);

    destroyListQueue(&queue);
    return EXIT_SUCCESS;
}

3. 基本概念

3.2 对象

3.6 标识符

4. 表达式

4.1 运算符

4.2 常量和字面量

4.3 求值

5. 语句

5.3 选择语句

5.4 循环语句

5.5 跳转语句

6. 函数

7. 派生类型

9. 对象

9.2 对象表示

9.4 声明

10. 预处理器

12. 标准库中的宏

13. 错误处理

14. 输入输出

16. 字符/字符串库

17. 数学库

21. 程序支持

22. 并发支持

MdrOS

番外

顺序表 ​

1. 线性表 ​

1.1 基本概念 ​

1.2 基本操作 ​

2. 顺序表 (SeqList) ​

2.1 基本概念 ​

2.2 实现 ​

2.3 完整示例代码 ​

3. 链表 (Linked List) ​

3.1 基本概念 ​

3.2 实现 ​

3.2.1 单链表 ​

3.2.2 双链表 ​

3.2.3 循环链表 ​

3.3 顺序表和链表的对比 ​

4. 栈 (Stack) ​

4.1 基本概念 ​

4.2 实现 ​

4.2.1 用数组实现 ​

4.2.2 用链表实现 ​

5. 队列 (Queue) ​

5.1 基本概念 ​

5.2 实现 ​

5.2.1 用数组实现（循环队列） ​

5.2.2 用链表实现 ​

顺序表

1. 线性表

1.1 基本概念

1.2 基本操作

2. 顺序表 (SeqList)

2.1 基本概念

2.2 实现

2.3 完整示例代码

3. 链表 (Linked List)

3.1 基本概念

3.2 实现

3.2.1 单链表

3.2.2 双链表

3.2.3 循环链表

3.3 顺序表和链表的对比

4. 栈 (Stack)

4.1 基本概念

4.2 实现

4.2.1 用数组实现

4.2.2 用链表实现

5. 队列 (Queue)

5.1 基本概念

5.2 实现

5.2.1 用数组实现（循环队列）

5.2.2 用链表实现