白乐天

道阻且长，行则将至。

数据结构

发表于 更新于 分类于
本文字数： 22k 阅读时长 ≈ 20 分钟

线性表

线性表（Linear List）是由一组数据元素按一定的顺序排列组成的集合。
线性表的基本操作

  • 初始化：初始化线性表为空。
  • 插入：在指定位置插入元素。
  • 删除：删除指定位置的元素。
  • 查找：查找某个元素的位置。
  • 访问：通过索引访问指定位置的元素。
  • 遍历：从头到尾依次访问线性表中的每个元素。
  • 长度：获取线性表中的元素个数。

顺序表

顺序表是一种线性表的实现方式，其核心思想是将线性表中的元素存储在一块连续的内存空间中。
顺序表通常是使用数组来实现的，元素可以通过索引直接访问。

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
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100  // 假设顺序表最大容量为100

// 定义顺序表结构体
typedef struct {
    int data[MAX_SIZE];  // 存储数据的数组
    int length;          // 顺序表当前长度
} SeqList;

// 初始化顺序表
void initSeqList(SeqList* list) {
    list->length = 0;  // 初始化为空表
}

// 判断顺序表是否为空
int isEmpty(SeqList* list) {
    return list->length == 0;
}

// 判断顺序表是否已满
int isFull(SeqList* list) {
    return list->length == MAX_SIZE;
}

// 插入元素到顺序表
int insert(SeqList* list, int index, int value) {
    if (index < 0 || index > list->length || isFull(list)) {
        return -1;  // 插入位置不合法或顺序表已满
    }

    // 将index及其后面的元素右移一位
    for (int i = list->length; i > index; --i) {
        list->data[i] = list->data[i - 1];
    }

    list->data[index] = value;
    list->length++;
    return 0;
}

// 删除顺序表中指定位置的元素
int delete(SeqList* list, int index) {
    if (index < 0 || index >= list->length) {
        return -1;  // 删除位置不合法
    }

    // 将index后面的元素左移一位
    for (int i = index; i < list->length - 1; ++i) {
        list->data[i] = list->data[i + 1];
    }

    list->length--;
    return 0;
}

// 查找元素在顺序表中的位置
int find(SeqList* list, int value) {
    for (int i = 0; i < list->length; ++i) {
        if (list->data[i] == value) {
            return i;  // 找到元素，返回其位置
        }
    }
    return -1;  // 未找到元素
}

// 访问顺序表中的指定元素
int get(SeqList* list, int index) {
    if (index < 0 || index >= list->length) {
        return -1;  // 索引越界
    }
    return list->data[index];
}

// 打印顺序表中的所有元素
void printSeqList(SeqList* list) {
    for (int i = 0; i < list->length; ++i) {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}

// 获取顺序表的长度
int getLength(SeqList* list) {
    return list->length;
}

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

    // 插入元素
    insert(&list, 0, 10);  // 插入10到位置0
    insert(&list, 1, 20);  // 插入20到位置1
    insert(&list, 2, 30);  // 插入30到位置2
    insert(&list, 1, 15);  // 插入15到位置1
    printSeqList(&list);    // 输出：10 15 20 30

    // 查找元素
    int index = find(&list, 20);
    if (index != -1) {
        printf("元素20在顺序表中的位置：%d\n", index);
    } else {
        printf("未找到元素20\n");
    }

    // 访问元素
    int value = get(&list, 2);
    if (value != -1) {
        printf("顺序表中索引2的元素是：%d\n", value);
    }

    // 删除元素
    delete(&list, 1);      // 删除位置1的元素
    printSeqList(&list);    // 输出：10 20 30

    return 0;
}

链表

单链表

每个节点包含两个部分：

  • 数据域 (Data)：存储节点的数据。
  • 指针域 (Next)：指向下一个节点的地址。

最后一个节点的 Next 指针通常为 NULL，表示链表的终点。

无链表头

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
#include <stdio.h>
#include "stdlib.h"

typedef int E;

// 定义节点结构体
typedef struct Node{
    E element;          // 数据域
    struct Node *next;  // 指针域，指向下一个节点
}Node;

// 创建一个新节点
Node* createNode(E element){
    Node *newNode = (Node*)malloc(sizeof(Node));
    if(!newNode){
        printf("内存分配失败！\n");
        exit(EXIT_FAILURE);
    }
    newNode->element = element;
    newNode->next = NULL;
    return newNode;
}

// 在链表头部插入节点
Node* insertAtHead(Node *head,E element){
    Node *newNode = createNode(element);
    if(head==NULL){
        head = newNode;
        return head;
    }
    newNode->next = head;
    return newNode;
}

// 在链表尾部插入节点
Node* appendAtHead(Node *head,E element){
    Node *newNode = createNode(element);
    // 如果链表为空
    if(head==NULL){
        head = newNode;
        return head;
    }
    Node *temp = head;
    while (temp->next!=NULL){
        temp=temp->next;
    }
    temp->next = newNode;
    return head;
}

// 删除链表中值为 element 的节点
Node* deleteNode(Node *head,E element){
    Node *temp = head;
    Node *prev = NULL;
    if(temp!=NULL && temp->element==element){
        head = head->next;
        free(temp);
        return head;
    }
    while (temp!=NULL && temp->element!=element){
        prev = temp;
        temp=temp->next;
    }
    if(temp==NULL){
        printf("未找到值为 %d 的节点。\n", element);
        return head;
    }
    prev->next=temp->next;
    free(temp);
    return head;
}

// 查询链表中是否包含某个值
int queryNode(Node *head,E element){
    Node *temp = head;
    int count = 0;
    while (temp->next!=NULL){
        if(temp->element==element){
            return count;
        }
        temp = temp->next;
        count++;
    }
    return -1; //未找到，返回 -1
}

// 遍历并打印链表中的所有节点
void printList(Node *head){
    Node *temp = head;
    while (temp!=NULL){
        printf("%d->",temp->element);
        temp = temp->next;
    }
    printf("NULL\n");
}

// 释放链表占用的内存
void freeList(Node *head){
    Node *temp = head;
    Node *next = NULL;
    while (temp!=NULL){
        next = temp->next;
        free(temp);
        temp = next;
    }
    head = NULL;
    printf("free List");
}

int main() {
    Node *head = NULL;
    head = insertAtHead(head,7);
    printf("%d\n",head->element);	// 7
    head = appendAtHead(head,8);
    printf("%d\n",head->next->element);	// 8
    head = deleteNode(head,7);
    printf("%d\n",head->element);	// 8
    head = insertAtHead(head,7);
    printf("%d\n",head->element);	// 7
    head = deleteNode(head,8);		
    printf("%d\n",head->element);	// 7
    int q = queryNode(head,9);
    printf("%d\n",q);		// -1
    printList(head);		// 7->NULL
    freeList(head);			// free List
    return 0;
}

有链表头

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
#include <stdio.h>
#include "stdlib.h"

typedef int E;

// 定义节点结构体
typedef struct Node{
    E element;          // 数据域
    struct Node *next;  // 指针域，指向下一个节点
}Node;

// 创建一个新节点
Node* createNode(E element){
    Node *newNode = (Node*)malloc(sizeof(Node));
    if(!newNode){
        printf("内存分配失败！\n");
        exit(EXIT_FAILURE);
    }
    newNode->element = element;
    newNode->next = NULL;
    return newNode;
}

// 在链表头部插入节点
void insertAtHead(Node *head,E element){
    Node *newNode = createNode(element);
    if(head->next==NULL){
        head->next=newNode;
        return;
    }
    Node *temp = head->next;
    head->next = newNode;
    newNode->next = temp;
}

// 在链表尾部插入节点
void appendAtHead(Node *head,E element){
    Node *newNode = createNode(element);
    Node *temp = head;
    while (temp->next!=NULL){
        temp=temp->next;
    }
    temp->next=newNode;
}

// 删除链表中值为 element 的节点
void deleteNode(Node *head,E element){
    Node *temp = head;
    while (temp->next!=NULL){
        if(temp->next->element==element){
            Node *del = temp->next;
            temp->next = temp->next->next;
            free(del);
            break;
        }
    }
}

// 查询链表中是否包含某个值
int queryNode(Node* head,E element){
    Node *temp = head;
    int count =1;
    while (temp->next!=NULL){
        if(temp->next->element==element){
            return count;
        }
        temp=temp->next;
        count++;
    }
    return -1;
}

// 遍历并打印链表中的所有节点
void printList(Node* head){
    Node *temp = head;
    while (temp->next!=NULL){
        printf("%d->",temp->next->element);
        temp = temp->next;
    }
    printf("NULL\n");
}

// 释放链表占用的内存
void freeList(Node *head){
    Node *temp = head;
    Node *next = NULL;
    while (temp!=NULL){
        next = temp->next;
        free(temp);
        temp = next;
    }
    head = NULL;
    printf("free List");
}

int main(){
    Node *head = (Node*)malloc(sizeof(Node));
    head->element=0;
    head->next=NULL;
    insertAtHead(head,7);
    printf("%d\n",head->next->element);	//7
    appendAtHead(head,8);
    printf("%d\n",head->next->next->element);	// 8
    deleteNode(head,7);
    printf("%d\n",head->next->element);		// 8
    appendAtHead(head,7);
    printf("%d\n", queryNode(head,7));		// 2
    printList(head);	// 8->7->NULL
    freeList(head);		// free List
    return 0;
}

双向链表

双向链表的每个节点包含两个指针：

  • 一个指向前驱节点（prev）。
  • 一个指向后继节点（next）。
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
#include <stdio.h>
#include "stdlib.h"

typedef int E;

// 定义节点结构体
typedef struct Node{
    E element;          // 数据域
    struct Node *next;  // 指针域，指向下一个节点
    struct Node *prev;  // 指针域，指向上一个节点
}Node;

// 初始化链表
void initList(Node* head){
    head->element=0;
    head->next=NULL;
    head->prev=NULL;
}

// 创建一个新节点
Node* createNode(E element){
    Node *newNode = (Node*)malloc(sizeof(Node));
    if(!newNode){
        printf("内存分配失败！\n");
        exit(EXIT_FAILURE);
    }
    newNode->element = element;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

// 在双向链表头部插入节点
void insertAtHead(Node *head,E element){
    Node *newNode = createNode(element);
    if(head->next==NULL){
        head->next=newNode;
        newNode->prev=head;
        return;
    }
    Node *temp = head->next;
    head->next = newNode;
    newNode->prev = head;
    newNode->next = temp;
    temp->prev = newNode;
}


// 在双向链表尾部插入节点
void appendAtHead(Node *head,E element){
    Node *newNode = createNode(element);
    Node *temp = head;
    while (temp->next!=NULL){
        temp=temp->next;
    }
    temp->next=newNode;
    newNode->prev = temp;
}

// 删除双向链表中值为 element 的节点
void deleteNode(Node *head,E element){
    Node *temp = head;
    while (temp->next!=NULL){
        if(temp->next->element==element){
            Node *del = temp->next;
            temp->next = temp->next->next;
            temp->next->prev = temp;
            free(del);
            return;
        }
        temp = temp->next;
    }
    printf("can't find %d\n", element);
}

// 查询双向链表中是否包含某个值
int queryNode(Node* head,E element){
    Node *temp = head;
    int count =1;
    while (temp->next!=NULL){
        if(temp->next->element==element){
            return count;
        }
        temp=temp->next;
        count++;
    }
    return -1;
}

// 遍历并打印链表中的所有节点
void printList(Node* head){
    Node *temp = head;
    while (temp->next!=NULL){
        printf("%d->",temp->next->element);
        temp = temp->next;
    }
    printf("NULL\n");
}

// 释放链表占用的内存
void freeList(Node *head){
    Node *temp = head;
    Node *next = NULL;
    while (temp!=NULL){
        next = temp->next;
        free(temp);
        temp = next;
    }
    head = NULL;
    printf("free List");
}

int main(){
    Node *head = (Node*)malloc(sizeof(Node));
    initList(head);
    insertAtHead(head,7);
    printf("%d\n",head->next->element);	// 7
    appendAtHead(head,8);
    printf("%d\n",head->next->next->element);	// 8
    deleteNode(head,7);
    printf("%d\n",head->next->element);		// 8
    appendAtHead(head,7);
    printf("%d\n", queryNode(head,7));	// 2
    printList(head);	// 8->7->NULL
    freeList(head);	// free List
}

循环链表

循环链表的最后一个节点指向头节点，从而形成一个环状结构。

在循环链表中，任何一个节点的下一个节点都不会是NULL。

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
#include <stdio.h>
#include "stdlib.h"

typedef int E;

// 定义节点结构体
typedef struct Node{
    E element;          // 数据域
    struct Node *next;  // 指针域，指向下一个节点
}Node;

// 初始化链表
void initList(Node* head){
    head->element=0;
    head->next=head;
}

// 创建一个新节点
Node *createNode(E element){
    Node *newNode = (Node*)malloc(sizeof(Node));
    if(!newNode){
        printf("内存分配失败！\n");
        exit(EXIT_FAILURE);
    }
    newNode->element = element;
    newNode->next=NULL;
    return newNode;
}

// 在循环链表头部插入节点
void insertAtHead(Node *head,E element){
    Node *newNode = createNode(element);
    head->next = newNode;
    newNode->next = head;
}

// 在循环链表尾部插入节点
void appendAtHead(Node *head,E element){
    Node *newNode = createNode(element);
    Node *temp = head;
    while (temp->next!=head){
        temp=temp->next;
    }
    temp->next=newNode;
    newNode->next = head;
}

// 删除循环链表中值为 element 的节点
void deleteNode(Node *head,E element){
    Node *temp = head;
    while (temp->next!=head){
        if(temp->next->element==element){
            Node *del = temp->next;
            temp->next = temp->next->next;
            free(del);
            return;
        }
        temp = temp->next;
    }
    printf("can't find %d\n", element);
}

// 查询循环链表中是否包含某个值
int queryNode(Node* head,E element){
    Node *temp = head;
    int count =1;
    while (temp->next!=head){
        if(temp->next->element==element){
            return count;
        }
        temp=temp->next;
        count++;
    }
    return -1;
}

// 遍历并打印链表中的所有节点
void printList(Node* head){
    Node *temp = head;
    while (temp->next!=head){
        printf("%d->",temp->next->element);
        temp = temp->next;
    }
    printf("NULL\n");
}

// 释放链表占用的内存
void freeList(Node *head){
    Node *temp = head->next;
    Node *next = NULL;
    while (temp!=head){
        next = temp->next;
        free(temp);
        temp = next;
    }
    free(head);
    head = NULL;
    printf("free List");
}

int main(){
    Node *head = (Node*)malloc(sizeof(Node));
    initList(head);
    insertAtHead(head,7);
    printf("%d\n",head->next->element);	// 7
    appendAtHead(head,8);
    printf("%d\n",head->next->next->element);	// 8
    deleteNode(head,7);
    printf("%d\n",head->next->element);	// 8
    appendAtHead(head,7);
    printf("%d\n", queryNode(head,7));	// 2
    printList(head);	// 8->7->NULL
    freeList(head);	// free List
}

栈与队列

栈

栈遵循后进先出的原则

顺序结构

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
#include "stdio.h"
#include "stdlib.h"

#define MAX_SIZE 100  // 定义栈的最大容量

typedef int E;  // 定义元素类型为 int

// 栈的结构体定义
typedef struct Stack {
    int data[MAX_SIZE]; // 存储栈元素的数组
    int top;            // 栈顶指针，指向栈顶元素的索引
} Stack;

// 初始化栈，将栈顶指针初始化为 -1
void initStack(Stack *stack) {
    stack->top = -1; // 栈为空时，栈顶指针为 -1
}

// 判断栈是否为空
int isNull(Stack *stack) {
    if (stack->top == -1) { // 如果栈顶指针为 -1，说明栈为空
        return 1;
    }
    return 0;
}

// 将元素压入栈
void push(Stack *stack, E element) {
    stack->top = stack->top + 1; // 栈顶指针加 1，指向新的栈顶位置
    if (stack->top >= MAX_SIZE) { // 检查是否超过栈的最大容量
        printf("out of MAX_SIZE!\n"); // 栈溢出错误提示
        stack->top--; // 恢复栈顶指针
        return;
    }
    stack->data[stack->top] = element; // 将元素存入栈顶位置
}

// 从栈顶弹出元素，并存储到指针 e 中
int pop(Stack *stack, E *e) {
    if (isNull(stack)) { // 如果栈为空，弹出失败
        printf("stack is NULL!\n"); // 提示栈为空
        return 0;
    }
    *e = stack->data[stack->top]; // 获取栈顶元素
    stack->top = stack->top - 1;  // 栈顶指针减 1
    return 1; // 弹出成功
}

// 查看栈顶元素，但不移除
int peek(Stack *stack, E *e) {
    if (isNull(stack)) { // 如果栈为空，查看失败
        printf("stack is NULL!\n"); // 提示栈为空
        return 0;
    }
    *e = stack->data[stack->top]; // 获取栈顶元素
    return 1; // 查看成功
}

int main() {
    // 动态分配内存创建栈
    Stack *stack = (Stack *) malloc(sizeof(Stack));
    initStack(stack); // 初始化栈

    // 压栈操作
    push(stack, 7);
    printf("%d\n", stack->data[stack->top]); // 输出栈顶元素，结果为 7

    // 动态分配内存创建变量用于存储弹出或查看的元素
    E *e = (E *) malloc(sizeof(E));
    
    // 弹栈操作
    pop(stack, e);
    printf("%d\n", *e); // 输出弹出的元素，结果为 7

    // 再次压栈操作
    push(stack, 8);

    // 查看栈顶元素
    peek(stack, e);
    printf("%d\n", *e); // 输出栈顶元素，结果为 8

    // 释放动态分配的内存
    free(stack);
    free(e);

    return 0;
}

链式结构

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
#include "stdio.h"
#include "stdlib.h"

typedef int E; // 定义栈元素类型为 int

// 链表节点结构体定义，用于实现链式栈
typedef struct Stack {
    E data;             // 栈元素数据
    struct Stack* next; // 指向下一个节点的指针
} Stack;

// 初始化栈头节点
void initStack(Stack *head) {
    head->data = 0;   // 栈头数据初始化为 0
    head->next = NULL; // 栈头的下一节点为空，表示栈为空
}

// 创建一个新栈节点，并赋予数据 element
Stack* createStack(E element) {
    Stack *stack = (Stack*) malloc(sizeof(Stack)); // 动态分配内存
    stack->next = NULL; // 初始化节点的 next 指针为 NULL
    stack->data = element; // 设置节点数据为 element
    return stack; // 返回新创建的节点
}

// 判断栈是否为空
int isNULL(Stack* head) {
    if (head->next == NULL) { // 如果头节点的 next 为空，栈为空
        return 1;
    }
    return 0; // 否则栈不为空
}

// 将元素压入栈
void pushStack(Stack* head, E element) {
    Stack *temp = head->next;         // 暂存当前栈顶节点
    Stack *newNode = createStack(element); // 创建新的栈节点
    head->next = newNode;             // 更新头节点的 next，指向新节点
    newNode->next = temp;             // 新节点的 next 指向原来的栈顶节点
}

// 弹出栈顶元素
E popStack(Stack* head) {
    if (isNULL(head)) { // 如果栈为空，无法弹出
        printf("Stack is NULL\n"); // 提示栈为空
        return 0; // 返回默认值
    }
    Stack *temp = head->next;         // 暂存栈顶节点
    head->next = head->next->next;    // 更新头节点的 next 指向栈顶的下一个节点
    E e = temp->data;                 // 获取栈顶数据
    free(temp);                       // 释放栈顶节点内存
    return e;                         // 返回栈顶数据
}

// 打印栈中所有元素
void printStack(Stack* head) {
    Stack *temp = head->next; // 从头节点的 next 开始遍历栈
    while (temp != NULL) {    // 遍历直到栈底（NULL）
        printf("%d->", temp->data); // 打印当前节点数据
        temp = temp->next;         // 移动到下一个节点
    }
    printf("NULL\n"); // 栈底结束后打印 NULL
}

// 释放整个栈的内存
void freeStack(Stack* head) {
    Stack *temp = head->next; // 从头节点的 next 开始释放内存
    while (temp != NULL) {    // 遍历释放所有节点
        free(head);           // 释放当前节点内存
        temp = temp->next;    // 移动到下一个节点
        head = temp;          // 更新头节点为当前节点
    }
    printf("Stack is NULL\n"); // 提示栈已释放完毕
}

// 主函数
int main() {
    Stack *head = (Stack*) malloc(sizeof(Stack)); // 动态分配栈头节点
    initStack(head); // 初始化栈头节点
    
    // 压栈操作
    pushStack(head, 7);
    printf("%d\n", head->next->data); // 输出栈顶元素，结果为 7
    pushStack(head, 8);
    printf("%d\n", head->next->data); // 输出栈顶元素，结果为 8

    // 弹栈操作
    E e = popStack(head);
    printf("%d\n", e); // 输出弹出的栈顶元素，结果为 8

    // 打印栈中元素
    printStack(head); // 输出栈中的元素，结果为 7->NULL

    // 释放栈内存
    freeStack(head); // 释放所有栈内存，并提示栈为空
    return 0;
}

队列

队列遵循先进先出的原则

顺序结构

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
#include "stdio.h"
#include "stdlib.h"

#define MAX_SIZE 5 // 定义队列的最大容量

typedef int E; // 定义队列元素类型为 int

// 定义队列结构体
typedef struct Queue {
    int data[MAX_SIZE]; // 存储队列元素的数组
    int front;          // 队头指针，指向队头元素
    int rear;           // 队尾指针，指向队尾元素的下一个位置
    int size;           // 队列中的元素个数
} Queue;

// 初始化队列
void initQueue(Queue *queue) {
    queue->front = 0;  // 队头指针初始化为 0
    queue->rear = 0;   // 队尾指针初始化为 0
    queue->size = 0;   // 队列大小初始化为 0
}

// 判断队列是否为空
int isEmpty(Queue *queue) {
    if (queue->size == 0) { // 如果队列大小为 0，则队列为空
        printf("Queue is NULL!\n");
        return 1; // 返回 1 表示队列为空
    }
    return 0; // 返回 0 表示队列不为空
}

// 判断队列是否已满
int isFull(Queue *queue) {
    if (queue->size == MAX_SIZE) { // 如果队列大小等于最大容量，则队列满
        printf("Queue is FULL!\n");
        return 1; // 返回 1 表示队列已满
    }
    return 0; // 返回 0 表示队列未满
}

// 入队操作，将元素添加到队尾
void enQueue(Queue *queue, E element) {
    if (isFull(queue)) { // 如果队列已满，打印提示信息并返回
        printf("Queue is FULL!\n");
        return;
    }
    queue->data[queue->rear] = element;         // 将元素插入队尾
    queue->rear = (queue->rear + 1) % MAX_SIZE; // 更新队尾指针，采用循环队列
    queue->size++;                              // 队列大小加 1
}

// 出队操作，将队头元素移除并返回
E deQueue(Queue *queue) {
    if (isEmpty(queue)) { // 如果队列为空，返回 -1 表示无效
        return -1;
    }
    E e = queue->data[queue->front];          // 获取队头元素
    queue->front = (queue->front + 1) % MAX_SIZE; // 更新队头指针，采用循环队列
    queue->size--;                            // 队列大小减 1
    return e;                                 // 返回被移除的元素
}

// 打印队列中所有元素
void printQueue(Queue *queue) {
    if (isEmpty(queue)) { // 如果队列为空，直接返回
        return;
    }
    printf("Queue elements: ");
    int size = queue->size; // 保存队列中元素的数量
    int temp = queue->front; // 从队头开始遍历
    while (size != 0) { // 遍历所有元素
        printf("%d->", queue->data[temp]); // 打印当前元素
        temp = (temp + 1) % MAX_SIZE;      // 更新索引，循环队列
        size--;                            // 元素数量减 1
    }
    printf("NULL\n"); // 队列结束
}

// 主函数，测试队列功能
int main() {
    Queue *queue = (Queue *)malloc(sizeof(Queue)); // 动态分配队列内存
    initQueue(queue); // 初始化队列

    // 测试入队操作
    enQueue(queue, 1);
    printf("%d\n", queue->data[0]); // 输出：1
    enQueue(queue, 2);
    printf("%d\n", queue->data[1]); // 输出：2
    enQueue(queue, 3);
    enQueue(queue, 4);
    enQueue(queue, 5);
    printf("%d\n", queue->size); // 输出队列大小：5

    // 打印队列
    printQueue(queue); // 输出：Queue elements: 1->2->3->4->5->NULL

    // 测试出队操作
    E e;
    e = deQueue(queue); // 移除队头元素
    printf("%d\n", e);  // 输出：1
    e = deQueue(queue); // 移除队头元素
    printf("%d\n", e);  // 输出：2
    e = deQueue(queue); // 移除队头元素
    printf("%d\n", e);  // 输出：3

    // 释放队列内存
    free(queue);

    return 0;
}

链式结构

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
#include "stdio.h"
#include "stdlib.h"

typedef int E; // 定义队列元素类型为 int

// 定义节点结构体
typedef struct Node {
    E element;        // 节点存储的元素
    struct Node* next; // 指向下一个节点的指针
} Node;

// 定义队列结构体
typedef struct Queue {
    Node *front; // 队头指针
    Node *rear;  // 队尾指针
} Queue;

// 初始化队列
void initQueue(Queue* queue) {
    queue->rear = NULL;  // 队尾指针初始化为 NULL
    queue->front = NULL; // 队头指针初始化为 NULL
}

// 判断队列是否为空
int isEmpty(Queue* queue) {
    return (queue->front == NULL); // 如果队头指针为 NULL，说明队列为空
}

// 创建新节点
Node *createNode(E element) {
    Node *newNode = (Node*) malloc(sizeof(Node)); // 动态分配新节点内存
    newNode->next = NULL;       // 新节点的 next 指针初始化为 NULL
    newNode->element = element; // 将传入的元素赋值给节点
    return newNode;             // 返回新创建的节点
}

// 入队操作
void enQueue(Queue* queue, E element) {
    Node *newNode = createNode(element); // 创建新节点
    if (isEmpty(queue)) {                // 如果队列为空
        queue->front = newNode;          // 队头指针指向新节点
        queue->rear = newNode;           // 队尾指针指向新节点
        return;
    }
    queue->rear->next = newNode; // 队尾指针的 next 指向新节点
    queue->rear = newNode;       // 更新队尾指针为新节点
}

// 出队操作
E deQueue(Queue* queue) {
    if (isEmpty(queue)) { // 如果队列为空
        printf("Queue is NULL\n");
        return -1; // 返回一个错误值
    }
    E e = queue->front->element;  // 获取队头元素
    Node *deNode = queue->front;  // 暂存队头节点
    queue->front = deNode->next;  // 更新队头指针
    free(deNode);                 // 释放队头节点内存
    return e;                      // 返回出队的元素
}

// 释放队列内存
void freeQueue(Queue* queue) {
    Node *temp = queue->front; // 从队头开始
    while (temp != NULL) {      // 遍历所有节点
        queue->front = queue->front->next; // 更新队头指针
        free(temp);             // 释放当前节点的内存
        temp = queue->front;    // 移动到下一个节点
    }
    free(queue); // 释放队列结构体内存
    printf("free Queue!\n"); // 输出释放提示信息
}

int main() {
    Queue *queue = (Queue *)malloc(sizeof(Queue)); // 动态分配队列内存
    initQueue(queue); // 初始化队列

    // 测试入队和出队操作
    enQueue(queue, 7); // 入队 7
    enQueue(queue, 8); // 入队 8

    E e = deQueue(queue); // 出队
    printf("Dequeued: %d\n", e); // 输出：Dequeued: 7

    e = deQueue(queue); // 再次出队
    printf("Dequeued: %d\n", e); // 输出：Dequeued: 8

    e = deQueue(queue); // 出队空队列
    printf("Dequeued: %d\n", e); // 输出：Queue is NULL, Dequeued: -1

    freeQueue(queue); // 释放队列内存，输出：free Queue!
    return 0;
}

树

树的定义

树（Tree）是有n个节点的有限集，它或为空树（n=0），或为非空树（n>0）。

有且只有一个根节点。

除根节点以外的节点可以分为m个互不相交的有限集，其中每一个集合本身又是一棵树，称为根的子树。

树的基本术语

结点

树中的一个独立单元。包含一个数据元素及若干指向其子树的分支。

结点的度

结点拥有的子树数称为结点的度。

树的度

树的度是树内各结点度的最大值。

叶子

度为0的结点称为叶子或终端结点。

非终端结点

度不为0的结点称为非终端结点或分支结点。

双亲和孩子

结点的子树的根称为该结点的孩子,相应地,该结点称为孩子的双亲。

兄弟

同一个双亲的孩子之间互称兄弟。

祖先

从根到该结点所经分支上的所有结点。

子孙

以某结点为根的子树中的任一结点都称为该结点的子孙。

层次

结点的层次从根开始定义起，根为第一层,根的孩子为第二层。

树中任一结点的层次等于其双亲结点的层次加1。

堂兄弟

双亲在同一层的结点互为堂兄弟。

树的深度

树中结点的最大层次称为树的深度或高度。

有序数和无序树

如果将树中结点的各子树看成从左至右是有次序的(即不能互换), 则称该树为有序树,否则称为无序树。

在有序树中最左边的子树的根称为第一个孩子,最右边的称为最后一个孩子。

森林

是m (m≥0) 棵互不相交的树的集合。对树中每个结点而言,其子树的集合即 为森林。

二叉树的定义

二叉树（Binary Tree）是n个结点所构成的集合，它或为空树，或为非空树。

有且仅有一个称之为根的节点。

除根结点以外的其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树,且T1和T2本身又都是二叉树。

二叉树与树的区别：

二叉树每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点);

二叉树的子树有左右之分,其次序不能任意颠倒。

二叉树的递归定义表明二叉树或为空,或是由一个根结点加上两棵分别称为左子树和右子树 的、互不相交的二叉树组成。由于这两棵子树也是二叉树,则由二叉树的定义,它们也可以是空树。

二叉树的性质

遍历二叉树和线索二叉树

先序遍历

中序遍历

后序遍历