数据结构及算法

韩乔落
  2025-01-03 17:27:33 2025-01-03 17:27:33 Created   2025-04-02 16:41:15 2025-04-02 16:41:15 Updated  

前言

建议有基础的同学直接学习 LibCSTL，本文内容大部分是以前学习时写的，没有考虑实用性，仅供学习参考

大一打为了打C语言基础打过一阵子ACM，不久我就转到了二进制安全，开始深入学习操作系统，内存管理器(ptmalloc2，jemalloc等)相关的知识，ACM算法的一些东西只记得一些原理和概念，代码快忘光了。那时也没有记录博客的习惯。后面就开始做二进制安全一阵子才开始写一些博客，现在想专注到AIoT开发，重新开始总结学习一些数据结构和算法，虽然没什么机会再去打ACM，但是学习算法总还是对提高编程能力有好处的。本文中的数据结构和算法用C实现， 少有借用C++ STL。

参考链接 这个链接文章很丰富，不过大都是C++/Python实现的，有一些只讲了原理和伪代码。我们挑了其中比较常用的数据结构和算法用C来实现。

打算重写其中部分数据结构，原版代码的扩展性并不好，实用性也不强。参考Linux内核的一些数据结构设计了C STL库，里面包含了一些扩展性和移植性较好的数据结构和算法，相较于原版代码，去除了不实用的功能，精简代码，最小程度还原数据结构本质功能。相较于内核，去除了static inline等这种比较消耗内存的设计，增加了更多的错误处理。

项目链接：https://github.com/jelasin/LibCSTL

基础知识

大O表示法

f(x) = O(g(x)) 表示的含义是f(x)以g(x)为上界。

f(x) = O(g(x))正式的数学定义：存在正常数c、n、n0，当 n>n0 的时，任意的 f(n) 符合 0 <= f(n) <= c.g(n)。

2becf2eb18f2916f3eac7d8a1aa553a3

image-20250210140113870

image-20250210140131118

image-20250210140151514

image-20250210140213877

初级数据结构

初级数据结构这里看代码和注释应该就能看懂，都是线性结构，不做过多解释。

顺序表

顺序表(Sequence List)，实现和数组差不多，代码很简单，不再赘述。对于顺序表的排序问题，可以指定排序标准以后，比如按照age排序，然后直接使用qsort进行排序即可，cmp函数为两个结构体中age的查差值。当然也可以自定义排序算法，和普通的排序没有差别。

图示

image-20250210161831058

seqlist.h

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
#ifndef __SEQLIST_H__
#define __SEQLIST_H__

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

#define RED "\033[31m"
#define NONE "\033[0m"

#define MAX 10 

struct student
{
	char name[20];
	int id;
	int age;
};
typedef struct student datatype_t;

typedef struct{
	datatype_t buf[MAX];
	int n;
}seqlist_t;

extern seqlist_t *create_empty_seqlist();
extern bool is_full_seqlist(seqlist_t *l);
extern void insert_data_seqlist(seqlist_t *l, datatype_t data);
extern void printf_data_seqlist(seqlist_t *l);
extern void destroy_seqlist(seqlist_t *l);
extern bool is_empty_seqlist(seqlist_t *l);
extern bool is_equal(datatype_t a, datatype_t b);
extern int delete_data_seqlist(seqlist_t *l, datatype_t data);
extern int find_data_seqlist(seqlist_t *l, datatype_t data);
extern int replace_data_seqlist(seqlist_t *l, datatype_t old, datatype_t new);

#endif

seqlist.c

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

seqlist_t *create_empty_seqlist()
{
    seqlist_t * l = (seqlist_t *)malloc(sizeof(seqlist_t));
    if (NULL == l)
    {
        perror(RED "[-] malloc error when create_empty_seqlist" NONE);
        return NULL;
    }
    memset(l, '\x00', sizeof(seqlist_t));
    l->n = 0;
    return l;
}
bool is_full_seqlist(seqlist_t *l)
{
    return l->n >= MAX ? true : false;
}
void insert_data_seqlist(seqlist_t *l, datatype_t data)
{
    if (is_full_seqlist(l)) 
    {
        printf(RED "[*]The list is full, cannot insert data.\n" NONE);
        return;
    }
    
    l->buf[l->n] = data;
    l->n++;

    return;
}
void printf_data_seqlist(seqlist_t *l)
{
    for (int i = 0; i < l->n; i++)
    {
        printf("Name: %s, ID: %d, Age: %d\n", l->buf[i].name, l->buf[i].id, l->buf[i].age);
    }
    return;
}
void destroy_seqlist(seqlist_t *l)
{
    free(l);
    l = NULL;
    return;
}
bool is_empty_seqlist(seqlist_t *l)
{
    return l->n == 0 ? true : false;
}
bool is_equal(datatype_t a, datatype_t b)
{
    if (a.age == b.age && a.id == b.id && !strcmp(a.name, b.name))
    {
        return true;
    }
    else
    {
        return false;
    }
}
int delete_data_seqlist(seqlist_t *l, datatype_t data)
{
    if (is_empty_seqlist(l)) 
    {
        return -1;
    }

    int i = 0, j = 0;
	
	// i用于遍历整个表，j用于标记被删除或已经移动的data。
    for (i = 0; i < l->n; i++) 
    {
        if (!is_equal(l->buf[i], data)) 
        {
            l->buf[j++] = l->buf[i];
        }
    }
    // 遍历完成，j刚好是应该更新的n。
    l->n = j;
	// 没找到要删除的元素。
    if (i == j)
    {
        return -2;
    }
    
}
int find_data_seqlist(seqlist_t *l, datatype_t data)
{
    for (int i = 0; i < l->n; i++) 
    {
        if (is_equal(l->buf[i], data)) 
        {
            return i;
        }
    }
    return -1;
}
int replace_data_seqlist(seqlist_t *l, datatype_t old, datatype_t new)
{
    while (-1 != find_data_seqlist(l, old))
    {
        l->buf[find_data_seqlist(l, old)] = new;
    }
    return 0;
}

main.c

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

int test()
{
    seqlist_t *list = create_empty_seqlist();
    if (NULL == list)
    {
        perror(RED "[-]Failed to create seqlist" NONE);
        return 0;
    }

    printf("[1] is_empty ==> %s \n", is_empty_seqlist(list) ? "true" : "false");
    

    datatype_t data_1 = { .age = 25, .id = 1, .name = "John Doe" };
    datatype_t data_2 = { .age = 26, .id = 2, .name = "Trump" };

    for (size_t i = 0; i < 5; i++)
    {
        insert_data_seqlist(list, data_1);
        insert_data_seqlist(list, data_2);
    }
    printf("[2] printf_data_seqlist\n");
    printf_data_seqlist(list);

    printf("[3] delete data_2\n");
    if(0 > delete_data_seqlist(list, data_2))
    {
        perror(RED "[-] Failed to delete data from seqlist, seqlist is empty or data is not exist" NONE);
    }

    printf("[4] printf_data_seqlist\n");
    printf_data_seqlist(list);
    
    replace_data_seqlist(list, data_1, (datatype_t){ .age = 30, .id = 3, .name = "Jane Doe" });

    printf("[5] After replacement\n");
    printf_data_seqlist(list);

    printf("[6] destroy_seqlist\n");
    destroy_seqlist(list);

    return 0;
}

int main(int argc, char const *argv[])
{
    return test();
}

单链表

单链表(Singly linked list)。我写的这种是带有头节点的单链表，并且头节点不存储数据，留有uint n用来记录链表长度。但是实现的时候却没怎麼用到uint n，而是按照不知道链表长度的方式来写。

图示

image-20250210162052725

SList.h

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
#ifndef __SLIST_H__
#define __SLIST_H__

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

#define RED "\033[31m"
#define NONE "\033[0m"

typedef int datatype_t;

typedef struct slist_node
{
    datatype_t data;
    struct slist_node * next;
} slist_node;

typedef struct slist_head
{
    uint32_t n;
    slist_node *next;
} slist_head;

extern slist_head* create_empyt_slist();

extern int insert_head_slist(slist_head* head, datatype_t value);

extern void print_slist(const slist_head* head);

extern int insert_tail_slist(slist_head* head, datatype_t value);

extern int insert_order_slist(slist_head* head, datatype_t value);

extern void delete_node_slist(slist_head* head, datatype_t value);

extern void destyroy_slist(slist_head* head);

extern bool is_empty_slist(slist_head* head);

extern uint32_t num_of_node_slist(slist_head* head);

extern slist_node* find_node_slist(const slist_head* head, datatype_t value);

extern void reverse_node_slist(slist_head* head);

#endif

SList.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
#include "SList.h"

slist_head* create_empyt_slist()
{
    slist_head * l = (slist_head*)malloc(sizeof(slist_head));
    if (NULL == l)
    {
        perror("Failed to allocate memory for slist_head");
        return NULL;
    }
    memset(l, 0, sizeof(slist_head));
    l->n = 0;
    l->next = NULL;
    return l;
}
int insert_head_slist(slist_head* head, datatype_t value)
{
    slist_node* new_node = (slist_node*)malloc(sizeof(slist_node));
    if (NULL == new_node)
    {
        perror("Failed to allocate memory for new node");
        return -1;
    }
    new_node->data = value;
    
    new_node->next = head->next;
    head->next = new_node;
    head->n++;

    return 0;
}
int insert_tail_slist(slist_head* head, datatype_t value)
{
    slist_node* new_node = (slist_node*)malloc(sizeof(slist_node));
    if (NULL == new_node)
    {
        perror("Failed to allocate memory for new node");
        return -1;
    }
    new_node->data = value;

    slist_node* temp = head->next;

    if (NULL != temp)
    {
        while(NULL != temp->next)
        {
            temp = temp->next;
        }
    }
    else // 只有首个元素会调用,放在else block
    {
        head->next = new_node;
        new_node->next = NULL;
        head->n++;

        return 0;
    }
    temp->next = new_node;
    new_node->next = NULL;
    head->n++;

    return 0;
}
int insert_order_slist(slist_head* head, datatype_t value)
{
    slist_node* new_node = (slist_node*)malloc(sizeof(slist_node));
    if (NULL == new_node)
    {
        perror("Failed to allocate memory for new node");
        return -1;
    }
    new_node->data = value;

    slist_node* temp = head->next;
    if (NULL != temp)
    {
        while (NULL != temp->next && temp->next->data < value)
        {
            temp = temp->next;
        }
    }
    else  // 只有首个元素会调用,放在else block
    {
        head->next = new_node;
        new_node->next = NULL;
        head->n++;

        return 0;
    }
    
    new_node->next = temp->next;
    temp->next = new_node;
    head->n++;

    return 0;
}
slist_node* find_node_slist(const slist_head* head, const datatype_t value)
{
    slist_node* current = head->next;
    if (NULL != current)
    {    
        while (value != current->data) 
        {
            if (NULL != current->next)
            {
                current = current->next;
            }
            else
            {
                return NULL;
            }
        }
    }

    return current;
}
void delete_node_slist(slist_head* head, datatype_t value)
{
    while (NULL != find_node_slist(head, value))
    {
        slist_node * p = head->next;
        slist_node * q = NULL;
        if (NULL != p)
        {
            while (p->data != value)
            {
                if (NULL != p->next)
                {
                    q = p;
                    p = p->next;
                }
                else
                {
                    return;
                }
            }
            // 边界判断
            if (NULL != q)
            {
                q->next = p->next;
                free(p);
                p = NULL;
                head->n--;
            }
            else
            {
                head->next = p->next;
                free(p);
                p = NULL;
                head->n--;
                if (head->n == 0)
            	{
                	head->next = NULL;
            	}
            }
        }
    }
}
void destyroy_slist(slist_head* head)
{
    slist_node* current = head->next;
    slist_node* p = NULL;

    if (NULL != current)
    {
        while (NULL != current->next) 
        {
            p = current;
            current = current->next;
            printf("%d ", p->data);
            free(p);
            p = NULL;
        }
        // current != NULL && current->next == NULL
        printf("%d \n", current->data);
        free(current);
        current = NULL;
    }

    free(head);
    head = NULL;
}
bool is_empty_slist(slist_head* head)
{
    return head->next == NULL ? true : false;
}
uint32_t num_of_node_slist(slist_head* head)
{
    return head->n;
}
void reverse_node_slist(slist_head* head)
{
    slist_node *prev = NULL;
    slist_node *current = head->next;
    slist_node *next = NULL;
    // 只需要想办法把指针转过来即可,最简单的就是迭代法,记住前后位置,然后改变当前node的指针即可.
    while (current != NULL)
    {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    // 最后head指向原tail.
    head->next = prev;
}
void print_slist(const slist_head* head)
{
    const slist_node* current = head->next;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

main.c

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

int test()
{
    slist_head * l = create_empyt_slist();
    if (NULL == l)
    {
        perror("Failed to create list");
        return -1;
    }
    
    insert_head_slist(l, 1);
    insert_head_slist(l, 5);
    insert_head_slist(l, 3);
    insert_head_slist(l, 7);
    insert_head_slist(l, 9);

    print_slist(l);
    reverse_node_slist(l);
    print_slist(l);

    destyroy_slist(l);
}
int main(int argc, char const *argv[])
{
    return test();
}

双链表

双链表(Doubly Linked List)的实现也很简单，除了删除以外和单链表差不多。这里头节点不存储值，头节点的prev和尾节点的next置空。双链表一般都会以双循环的形式存在。

image-20250210162135009

DList.h

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
#ifndef __DLIST_H__
#define __DLIST_H__
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<stdint.h>

typedef int datatype_t;

typedef struct dlist_node {
    datatype_t data;
    struct dlist_node* prev;
    struct dlist_node* next;
} dlist_node;

typedef dlist_node dlist_head;


extern dlist_head* create_dlist();

extern void debug(dlist_head* l);

extern int insert_head_dlist(dlist_head* l, datatype_t data);

extern int insert_tail_dlist(dlist_head* l, datatype_t data);

extern void print_dlist(const dlist_head* l);

extern dlist_node* find_node_dlist(dlist_head* l, datatype_t data);

extern void delete_dlist_node(dlist_head* l, datatype_t data);

extern void destroy_dlist(dlist_head* l);

#endif

Dlist.c

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

dlist_head* create_dlist()
{
    dlist_head * l = (dlist_head*)malloc(sizeof(dlist_head));
    if (NULL == l)
    {
        perror("Memory allocation failed");
        return NULL;
    }

    memset(l, '\x00', sizeof(dlist_head));
    return l;
}

int insert_head_dlist(dlist_head* l, datatype_t data)
{    
    dlist_node* new_node = (dlist_node*)malloc(sizeof(dlist_node));
    if (NULL == l)
    {
        perror("Memory allocation failed");
        return -1;
    }
    new_node->data = data;
    
    new_node->next = l->next;
    new_node->prev = l;
    l->next = new_node;
    if (NULL != new_node->next)
    {
        new_node->next->prev = new_node;
    }

    return 0;
}

int insert_tail_dlist(dlist_head* l, datatype_t data)
{
    dlist_node* new_node = (dlist_node*)malloc(sizeof(dlist_node));
    if (NULL == l)
    {
        perror("Memory allocation failed");
        return -1;
    }
    new_node->data = data;
    dlist_node* tail = l;
    while (NULL != tail->next)
    {
        tail = tail->next;
    }
    
    new_node->next = NULL;
    tail->next = new_node;
    new_node->prev = tail;
}

void debug(dlist_head* l)
{
    const dlist_node* current = l;
    while (NULL != current->next)
    {
        printf("current ==> %p, next ==> %p, prev ==> %p\n",current, current->next, current->prev);
        current = current->next;
    }
    printf("current ==> %p, next ==> %p, prev ==> %p\n",current, current->next, current->prev);
}

void print_dlist(const dlist_head* l)
{
    const dlist_node* current = l;
    while (NULL != current->next)
    {
        current = current->next;
        printf("%d ==> ",current->data);

    }
    printf("NULL\n");
}

dlist_node* find_node_dlist(dlist_head* l, const datatype_t data)
{
    dlist_node* current = l;
    while (NULL != current->next)
    {
        current = current->next;
        if (data == current->data)
        {
            return current;
        }
    }
    return NULL;
}

void delete_dlist_node(dlist_head* l, datatype_t data)
{
    while (NULL != find_node_dlist(l, data))
    {
        dlist_node* current = l;
        while (NULL != current->next)
        {
            current = current->next;
            if (data == current->data)
            {
                break;
            }
        }

        current->prev->next = current->next;
        if (NULL != current->next)
        {
            current->next->prev = current->prev;
        }
        free(current);
        current = NULL;
    }
}

void destroy_dlist(dlist_head* l)
{
    dlist_node* current = l;
    if (NULL == l->next)
    {
        free(l);
        l = NULL;
        return;
    }
    
    dlist_node* p = NULL;
    while (NULL != current->next)
    {
        p = current;
        current = current->next;
        free(p);
        p = NULL;
    }
    free(current);
    current = NULL;  
    l = NULL;
}

main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include "DList.h"

int main(int argc, char const *argv[])
{
    dlist_head * l = create_dlist();
    insert_head_dlist(l, 1);
    insert_head_dlist(l, 2);
    insert_head_dlist(l, 3);

    insert_tail_dlist(l, 4);
    insert_tail_dlist(l, 5);
    insert_tail_dlist(l, 6);

    debug(l);
    print_dlist(l);

    delete_dlist_node(l, 3);

    debug(l);
    print_dlist(l);
    destroy_dlist(l);
    return 0;
}

单循环链表

单循环链表(Singly Circular Linked List)，看起来简单，写起来要注意的细节很多，主要还是边界检查。前面单链表没怎麼用到uint n参数，这里单循环链表的实现则是用到了头节点的uint n参数。

图示

image-20250210162241027

SCList.h

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
#ifndef __SCLIST_H__
#define __SCLIST_H__

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

#define RED "\033[31m"
#define NONE "\033[0m"

typedef int datatype_t;

typedef struct sclist_node
{
    datatype_t data;
    struct sclist_node * next;
} sclist_node;

typedef struct sclist_head
{
    uint32_t n;
    sclist_node *next;
} sclist_head;

extern sclist_head* create_empyt_sclist();

extern int insert_head_sclist(sclist_head* head, datatype_t value);

extern void print_sclist(const sclist_head* head);

extern void delete_node_sclist(sclist_head* head, datatype_t value);

extern void destyroy_sclist(sclist_head* head);

extern bool is_empty_sclist(sclist_head* head);

extern uint32_t num_of_node_sclist(sclist_head* head);

extern sclist_node* find_node_sclist(const sclist_head* head, datatype_t value);

#endif

SCList.c

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

sclist_head* create_empyt_sclist()
{
    sclist_head * l = (sclist_head*)malloc(sizeof(sclist_head));
    if (NULL == l)
    {
        perror("Failed to allocate memory for sclist_head");
        return NULL;
    }
    memset(l, 0, sizeof(sclist_head));
    l->n = 0;
    l->next = NULL;
    return l;
}
int insert_head_sclist(sclist_head* head, datatype_t value)
{
    sclist_node* new_node = (sclist_node*)malloc(sizeof(sclist_node));
    if (NULL == new_node)
    {
        perror("Failed to allocate memory for new node");
        return -1;
    }
    new_node->data = value;

    if (NULL != head->next)
    {
        sclist_node* p = head->next;
        new_node->next = p->next;
        p->next = new_node;
        head->n++;
    }
    else
    {
        head->next = new_node;
        new_node->next = new_node;
        head->n++;
    }

    return 0;
}
sclist_node* find_node_sclist(const sclist_head* head, const datatype_t value)
{
    sclist_node* current = head->next;
    for (size_t i = 0; i < head->n; i++)
    {
        if (current->data != value)
        {
            current = current->next;
        }
        else
        {
            return current;
        }
    }
    
    return NULL;
}
void delete_node_sclist(sclist_head* head, datatype_t value)
{
    while (NULL != find_node_sclist(head, value))
    {
        sclist_node * p = head->next;
        sclist_node * q = NULL;
        for (size_t i = 0; i < head->n; i++)
        {
            if (p->data != value)
            {
                q = p;
                p = p->next;
            }
        }
        // 边界判断
        if (NULL != q)
        {
            q->next = p->next;
            free(p);
            p = NULL;
            head->n--;
        }
        else
        {
            q = head->next;
            head->next = p->next;
            for (size_t i = 1; i < head->n; i++)
            {
                q = q->next;
            }
            q->next = p->next;
            free(p);
            p = NULL;
            head->n--;
            if (head->n == 0)
            {
                head->next = NULL;
            }
        }
        
    }
}
void destyroy_sclist(sclist_head* head)
{
    if (head->next == NULL)
    {
        free(head);
        head = NULL;
        return;
    }
    sclist_node* p = head->next;
    sclist_node* q = NULL;
    for (size_t i = 1; i < head->n; i++)
    {
        q = p;
        p = p->next;
        free(q);
        q = NULL;
    }
    free(p);
    p = NULL;
    free(head);
    head = NULL;
}
bool is_empty_sclist(sclist_head* head)
{
    return head->next == NULL ? true : false;
}
uint32_t num_of_node_sclist(sclist_head* head)
{
    return head->n;
}
void print_sclist(const sclist_head* head)
{
    const sclist_node* current = head->next;
    
    for (size_t i = 0; i < head->n; i++)
    {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("%d\n", head->next->data);
}

main.c

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

int test()
{
    // 约瑟夫问题的循环链表解决
    sclist_head* l = create_empyt_sclist();
    int n = 8, k = 3, m = 4;
    // scanf("%d %d %d", &n, &k, &m);
    for (size_t i = n; i > 0; i--)
    {
        insert_head_sclist(l, i);
    }

    for (size_t i = 0; i < k; i++)
    {
        l->next = l->next->next;
    }
    printf("num_of_list == > %d\n", num_of_node_sclist(l));
    printf("k == > %d\n", l->next->data);

    while (0 != l->n)
    {
        for (size_t i = 1; i < m; i++)
        {
            l->next = l->next->next;
        }
        printf("m == > %d\n", l->next->data);
        delete_node_sclist(l, l->next->data);
        printf("num_of_list == > %d\n", num_of_node_sclist(l));
    }

    destyroy_sclist(l);    
}
int main(int argc, char const *argv[])
{
    return test();
}

双循环链表

双循环链表(Doubly Circular Linked List)，在双链表的基础上，将头节点的prev指向尾部，将尾部节点的next指向头部。

图示

image-20250210162342515

DList.h

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
#ifndef __DLIST_H__
#define __DLIST_H__
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<stdint.h>

typedef int datatype_t;

typedef struct dlist_node {
    datatype_t data;
    struct dlist_node* prev;
    struct dlist_node* next;
} dlist_node;

typedef dlist_node dlist_head;

extern dlist_head* create_dlist();

extern void debug(dlist_head* l);

extern int insert_head_dlist(dlist_head* l, datatype_t data);

extern void print_dlist(const dlist_head* l);

extern dlist_node* find_node_dlist(dlist_head* l, datatype_t data);

extern void delete_dlist_node(dlist_head* l, datatype_t data);

extern void destroy_dlist(dlist_head* l);

#endif

DList.c

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

dlist_head* create_dlist()
{
    dlist_head * l = (dlist_head*)malloc(sizeof(dlist_head));
    if (NULL == l)
    {
        perror("Memory allocation failed");
        return NULL;
    }

    memset(l, '\x00', sizeof(dlist_head));
    l->next = l;
    l->prev = l;
    return l;
}

int insert_head_dlist(dlist_head* l, datatype_t data)
{    
    dlist_node* new_node = (dlist_node*)malloc(sizeof(dlist_node));
    if (NULL == l)
    {
        perror("Memory allocation failed");
        return -1;
    }
    new_node->data = data;
    
    new_node->next = l->next;
    new_node->prev = l;
    l->next = new_node;
    new_node->next->prev = new_node;

    return 0;
}

void debug(dlist_head* l)
{
    const dlist_node* current = l;
    while (l != current->next)
    {
        printf("current ==> %p, next ==> %p, prev ==> %p\n",current, current->next, current->prev);
        current = current->next;
    }
    printf("current ==> %p, next ==> %p, prev ==> %p\n",current, current->next, current->prev);
}

void print_dlist(const dlist_head* l)
{
    const dlist_node* current = l;
    while (l != current->next)
    {
        current = current->next;
        printf("%d ==> ",current->data);

    }
    printf("NULL\n");
}

dlist_node* find_node_dlist(dlist_head* l, const datatype_t data)
{
    dlist_node* current = l;
    while (l != current->next)
    {
        current = current->next;
        if (data == current->data)
        {
            return current;
        }
    }
    return NULL;
}

void delete_dlist_node(dlist_head* l, datatype_t data)
{
    while (NULL != find_node_dlist(l, data))
    {
        dlist_node* current = l;
        while (l != current->next)
        {
            current = current->next;
            if (data == current->data)
            {
                break;
            }
        }

        current->prev->next = current->next;
        current->next->prev = current->prev;

        free(current);
        current = NULL;
    }
}

void destroy_dlist(dlist_head* l)
{
    dlist_node* current = l;
    if (l == l->next)
    {
        free(l);
        l = NULL;
        return;
    }
    
    dlist_node* p = NULL;
    while (l != current->next)
    {
        p = current;
        current = current->next;
        free(p);
        p = NULL;
    }
    free(current);
    current = NULL;  
    l = NULL;
}

main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include "DList.h"

int main(int argc, char const *argv[])
{
    dlist_head * l = create_dlist();
    insert_head_dlist(l, 1);
    insert_head_dlist(l, 2);
    insert_head_dlist(l, 3);

    debug(l);
    print_dlist(l);

    delete_dlist_node(l, 2);

    debug(l);
    print_dlist(l);
    destroy_dlist(l);
    return 0;
}

十字链表

如果简单实现可以用顺序表来存储头节点，十字链表就是用链表将链表头节点链接起来，实现起来除了嵌套多一下，其他很容易，不再赘述。

图示

image-20250210171219074

顺序栈

图示

08a367b3a2d2a9ee53c8e36e7b46d32d

78ea46434302cd966baa9834f9b5df5e

seqstack.h

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
#ifndef __SEQSTACK_H__
#define __SEQSTACK_H__
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<stdint.h>

typedef int data_t;

#define MAX 20

typedef struct
{
    data_t buf[MAX];
    int top;
} seqstack_t;

extern seqstack_t* create_empty_seqstack();

extern bool is_empty_seqstack(seqstack_t* s);

extern bool is_full_seqstack(seqstack_t* s);

extern void push_seqstack(seqstack_t*s,data_t data);

extern data_t pop_seqstack(seqstack_t* s);

extern data_t get_top_data(seqstack_t *s);


#endif

seqstack.c

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

seqstack_t* create_empty_seqstack()
{
    seqstack_t* stack = (seqstack_t*)malloc(sizeof(seqstack_t));
    if (NULL == stack)
    {
        perror("Memory allocation failed");
        return NULL;
    }
    stack->top = -1;
    return stack;
}

bool is_empty_seqstack(seqstack_t* s)
{
    return s->top == -1;
}

bool is_full_seqstack(seqstack_t* s)
{
    return s->top == MAX - 1;
}

void push_seqstack(seqstack_t*s,data_t data)
{
    if (is_full_seqstack(s))
    {
        perror("Stack overflow");
        return;
    }
    s->buf[++s->top] = data;
}

data_t pop_seqstack(seqstack_t* s)
{
    if (is_empty_seqstack(s))
    {
        perror("Stack underflow");
        return -1;
    }
    return s->buf[s->top--];
}

data_t get_top_data(seqstack_t *s)
{
    if (is_empty_seqstack(s))
    {
        perror("Stack is empty");
        return -1;
    }
    return s->buf[s->top];
}

main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include "seqstack.h"

int main(int argc, char const *argv[])
{
    data_t data[] = {'a','n','i','h','c',' ','e','v','o','l',' ','I'};
    seqstack_t* s = create_empty_seqstack();

    for (size_t i = 0; i < sizeof(data)/sizeof(data_t); i++)
    {
        push_seqstack(s, data[i]);
    }

    while (!is_empty_seqstack(s))
    {
        printf("==> %c\n", (char)pop_seqstack(s));
    }
    

    return 0;
}

链式栈

这里我们实现的时候不使用尾指针。数据结构类似于前面的单循环链表。

图示

入栈：

e703e52f1e01092b83f03a44bf4949b9

出栈：

cdb9b7301ac41187667f272cebc050b5

link_stack.h

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
#ifndef __LINK_STACK_H__
#define __LINK_STACK_H__
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<stdint.h>

typedef char data_t;

typedef struct node
{
    data_t data;
    struct node *next;
} linknode_t;

typedef struct 
{
    linknode_t *top;
    int n;
} linkstack_t;

extern linkstack_t * create_empty_linkstack();

extern int is_empty_linkstack(linkstack_t *s);

extern int push_linkstack(linkstack_t *s, data_t data);

extern data_t pop_linkstack(linkstack_t *s);

extern data_t get_top_data(linkstack_t *s);

#endif

link_stack.c

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

linkstack_t * create_empty_linkstack()
{
    linkstack_t *s = (linkstack_t *)malloc(sizeof(linkstack_t));
    if (NULL == s)
    {
        perror("Failed to allocate memory for link stack");
        return NULL;
    }
    s->top = NULL;
    s->n = 0;
    return s;
}

int is_empty_linkstack(linkstack_t *s)
{
    return s->top == NULL;
}

int push_linkstack(linkstack_t *s, data_t data)
{
    linknode_t *new_node = (linknode_t *)malloc(sizeof(linknode_t));
    if (NULL == new_node)
    {
        perror("Failed to allocate memory for new node");
        return -1;
    }
    new_node->data = data;
    new_node->next = s->top;
    s->top = new_node;
    s->n++;
    return 0;
}

data_t pop_linkstack(linkstack_t *s)
{
    if (is_empty_linkstack(s))
    {
        perror("Stack is empty");
        return -1;
    }
    linknode_t* top_node = s->top;
    s->top = top_node->next;
    data_t data = top_node->data;
    free(top_node);
    top_node = NULL;
    s->n--;
    return data;
}

data_t get_top_data(linkstack_t *s)
{
    if (is_empty_linkstack(s))
    {
        perror("Stack is empty"); 
        return -1;
    }
    return s->top->data;
}

main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include "link_stack.h"

int main()
{
    linkstack_t *s = NULL;
    data_t array[] = {'a','n','i','h','c'};
    int i = 0;

    s = create_empty_linkstack();

    for(i = 0;i < sizeof(array)/sizeof(array[0]);i++)
    {
        push_linkstack(s,array[i]);
    }

    while(!is_empty_linkstack(s))
    {
        printf("==> %c\n", pop_linkstack(s));
    }

    return 0;
}

双端栈

实现起来很简单，不再赘述。

图示

2292084acf85e8e1631fd7baadc02ee9

1c804a05158b63f890f0ebd639fbdc52

循环队列

7d5f1515b4fdaebaaaad07d5bf94e13b

loop_queue.h

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
#ifndef __LOOP_QUEUE_H__
#define __LOOP_QUEUE_H__

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

typedef int data_t;

#define N 5

typedef struct 
{
    data_t buf[N];
    int front;
    int rear;
}loopqueue_t;

extern loopqueue_t *create_empty_loopqueue();

extern bool is_empty_loopqueue(loopqueue_t *q);

extern bool is_full_loopqueue(loopqueue_t *q);

extern void enter_loopqueue(loopqueue_t *q,data_t data);

extern data_t delete_loopqueue(loopqueue_t *q);

#endif

loop_queue.c

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

loopqueue_t *create_empty_loopqueue()
{
    loopqueue_t * q = (loopqueue_t*)malloc(sizeof(loopqueue_t));
    if (NULL == q)
    {
        perror("Failed to allocate memory for loop queue");
        return NULL;
    }
    q->front = q->rear = 0;
    return q;
}

bool is_empty_loopqueue(loopqueue_t *q)
{
    return q->front == q->rear;
}

bool is_full_loopqueue(loopqueue_t *q)
{
    return q->front == (q->rear + 1) % N;
}

void enter_loopqueue(loopqueue_t *q, data_t data)
{
    if (is_full_loopqueue(q))
    {
        perror("Failed to enter data into loop queue: queue is full");
        return;
    }
    
    q->buf[q->rear] = data;
    q->rear = (q->rear + 1) % N;
}

data_t delete_loopqueue(loopqueue_t *q)
{
    if(is_empty_loopqueue(q))
    {
        perror("Failed to delete data from loop queue: queue is empty");
        return;
    }
    data_t data = q->buf[q->front];
    q->front = (q->front + 1) % N;
    return data;
}

main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include "loop_queue.h"

int main(int argc, char const *argv[])
{
    int i = 0;
    loopqueue_t *q = NULL;

    q = create_empty_loopqueue();

    while(!is_full_loopqueue(q))
    {
        enter_loopqueue(q,i++);
    }

    while(!is_empty_loopqueue(q))
    {
        printf("%d ",delete_loopqueue(q));
    }
    printf("\n");


    return 0;
}

链式队列

1a8f5fc2694b540ebfaac38357f618c5

36ecc736f2fb5dea4b7b2c020b0e3bef

link_queue.h

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
#ifndef __LINK_QUEUE_H__
#define __LINK_QUEUE_H__

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

typedef int data_t;

typedef struct node
{
    data_t data;
    struct node *next;
}linknode_t;

typedef struct
{
    linknode_t *front;
    linknode_t *rear;
}linkqueue_t;

extern linkqueue_t *create_empty_linkqueue();

extern bool is_empty_linkqueue(linkqueue_t *queue);

extern bool enqueue_linkqueue(linkqueue_t *queue, data_t value);

extern data_t dequeue_linkqueue(linkqueue_t *queue);

#endif

link_queue.c

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

linkqueue_t *create_empty_linkqueue()
{
    linkqueue_t * q = (linkqueue_t*)malloc(sizeof(linkqueue_t));
    if (NULL == q)
    {
        perror("Failed to allocate memory for link queue");
        return NULL;
    }
    q->front = q->rear = NULL;
    return q;
}

bool is_empty_linkqueue(linkqueue_t *queue)
{
    return queue->front == NULL || queue->rear == NULL;
}

bool enqueue_linkqueue(linkqueue_t *queue, data_t value)
{
    linknode_t* new_node = (linknode_t*)malloc(sizeof(linknode_t));
    if (NULL == new_node)
    {
        perror("Failed to allocate memory for new node in link queue");
        return false;
    }
    new_node->data = value;
    new_node->next = NULL;

    if (is_empty_linkqueue(queue))
    {
        queue->front = queue->rear = new_node;
        return true;
    }
    
    queue->rear->next = new_node;
    queue->rear = new_node;
    return true;
}

data_t dequeue_linkqueue(linkqueue_t *queue)
{
    if (is_empty_linkqueue(queue))
    {
        perror("queue is empty");
        return -1;
    }
    
    linknode_t* temp = queue->front;

    if (NULL != queue->front->next)
    {
        queue->front = queue->front->next;
    }
    else
    {
        queue->front = queue->rear = NULL;
    }

    data_t data = temp->data;
    free(temp);
    temp = NULL;
    
    return data;
}

main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include "link_queue.h"

int main(int argc, char const *argv[])
{
    linkqueue_t* q = create_empty_linkqueue();
    for (size_t i = 0; i < 8; i++)
    {
        enqueue_linkqueue(q, i);
    }
    while (!is_empty_linkqueue(q))
    {
        printf("==> %d\n", dequeue_linkqueue(q));
    }
    
    return 0;
}

双端队列

双端队列又名double ended queue，简称deque，双端队列没有队列和栈这样的限制级，它允许两端进行入队和出队操作，也就是说元素可以从队头出队和入队，也可以从队尾出队和入队。实现很简单，带尾指针的双链表即可实现，不再赘述。

c1c6edff7547aea2990d254e5f774b90

优先队列

二叉堆是优先队列的一种实现方式。二叉堆是一棵完全二叉树，分为大端堆和小端堆，其中每个父节点的值都>=（大端堆）或<=（小端堆）其子节点的值。二叉堆通常用于实现优先队列，支持高效的插入和删除最大元素操作。

下面是大端堆的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 二叉树节点结构体
typedef struct Node {
    int value;
    struct Node* parent;
    struct Node* left;
    struct Node* right;
} Node;

// 二叉堆结构体
typedef struct {
    Node* root;      // 堆的根节点
    Node* last_node; // 最后一个节点
    int size;        // 堆的大小
    Node** queue;    // 用于维护插入位置的队列
    int queue_size;  // 队列当前大小
    int queue_cap;   // 队列容量
} BinaryHeap;

// 创建新节点
Node* create_node(int value) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->value = value;
    node->parent = node->left = node->right = NULL;
    return node;
}

// 初始化二叉堆
void heap_init(BinaryHeap* heap) {
    heap->root = heap->last_node = NULL;
    heap->size = 0;
    heap->queue_cap = 8; // 初始队列容量
    heap->queue = (Node**)malloc(sizeof(Node*) * heap->queue_cap);
    heap->queue_size = 0;
}

// 扩展队列容量
void resize_queue(BinaryHeap* heap) {
    heap->queue_cap *= 2;
    heap->queue = (Node**)realloc(heap->queue, sizeof(Node*) * heap->queue_cap);
}

// 插入节点时的队列操作
void enqueue(BinaryHeap* heap, Node* node) {
    if (heap->queue_size >= heap->queue_cap) resize_queue(heap);
    heap->queue[heap->queue_size++] = node;
}

// 取出队列头部节点
Node* dequeue(BinaryHeap* heap) {
    if (heap->queue_size == 0) return NULL;
    Node* node = heap->queue[0];
    for (int i = 1; i < heap->queue_size; i++) {
        heap->queue[i-1] = heap->queue[i];
    }
    heap->queue_size--;
    return node;
}

// 上滤操作（保持堆性质）
void percolate_up(Node* node) {
    while (node->parent != NULL && node->value > node->parent->value) {
        // 交换父子节点值
        int temp = node->value;
        node->value = node->parent->value;
        node->parent->value = temp;
        node = node->parent;
    }
}

// 插入元素
void heap_insert(BinaryHeap* heap, int value) {
    Node* new_node = create_node(value);
    
    if (heap->size == 0) {
        heap->root = heap->last_node = new_node;
        enqueue(heap, new_node);
        heap->size++;
        return;
    }

    Node* parent = heap->queue[0];
    if (parent->left == NULL) {
        parent->left = new_node;
        new_node->parent = parent;
        // 将父节点重新放回队列前端
        heap->queue[0] = parent;
        enqueue(heap, new_node);
    } else {
        parent->right = new_node;
        new_node->parent = parent;
        dequeue(heap); // 父节点处理完毕
        enqueue(heap, new_node);
    }
    heap->last_node = new_node;
    heap->size++;
    percolate_up(new_node);
}

// 下滤操作（保持堆性质）
void percolate_down(Node* node) {
    while (true) {
        Node* max_child = NULL;
        // 比较左右子节点
        if (node->left && node->right) {
            max_child = (node->left->value > node->right->value) ? node->left : node->right;
        } else if (node->left) {
            max_child = node->left;
        } else {
            break; // 没有子节点
        }

        if (max_child->value > node->value) {
            // 交换节点值
            int temp = node->value;
            node->value = max_child->value;
            max_child->value = temp;
            node = max_child;
        } else {
            break;
        }
    }
}

// 查找最后一个节点（使用二进制路径法）
Node* find_last_node(BinaryHeap* heap) {
    if (heap->size == 0) return NULL;
    
    int mask = 1 << (31 - __builtin_clz(heap->size)); // 找到最高位
    Node* current = heap->root;
    
    while (mask > 1) {
        mask >>= 1;
        current = (heap->size & mask) ? current->right : current->left;
    }
    return current;
}

// 提取最大值
int heap_extract_max(BinaryHeap* heap) {
    if (heap->size == 0) return -1; // 错误码
    
    int max_val = heap->root->value;
    if (heap->size == 1) {
        free(heap->root);
        heap->root = heap->last_node = NULL;
        heap->size = 0;
        return max_val;
    }

    // 将最后一个节点的值移到根节点
    heap->root->value = heap->last_node->value;
    
    // 删除最后一个节点
    Node* parent = heap->last_node->parent;
    if (parent->right == heap->last_node) {
        free(parent->right);
        parent->right = NULL;
    } else {
        free(parent->left);
        parent->left = NULL;
    }
    
    heap->size--;
    heap->last_node = find_last_node(heap);
    percolate_down(heap->root);
    return max_val;
}

// 清理堆内存
void heap_clean(BinaryHeap* heap) {
    // 实现层次遍历清理内存（此处省略具体实现）
    free(heap->queue);
}

/*************** 测试用例 ***************/
int main() {
    BinaryHeap heap;
    heap_init(&heap);

    // 插入测试
    heap_insert(&heap, 5);
    heap_insert(&heap, 8);
    heap_insert(&heap, 3);
    heap_insert(&heap, 11);
    heap_insert(&heap, 10);
    heap_insert(&heap, 18);

    // 提取最大值测试
    printf("Max: %d\n", heap_extract_max(&heap)); // 18
    printf("Max: %d\n", heap_extract_max(&heap)); // 11
    printf("Max: %d\n", heap_extract_max(&heap)); // 10
    printf("Max: %d\n", heap_extract_max(&heap)); // 8
    printf("Max: %d\n", heap_extract_max(&heap)); // 5
    
    heap_clean(&heap);
    return 0;
}

中级数据结构

这部分不难，但是内容比较多。

二叉树

这里我们只谈二叉树的创建(完全二叉树)，遍历以及一些扩展功能，重点在遍历部分。插入，查找和删除我们放在二叉查找树来讲。

BiTree.h

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
#ifndef __BITREE_H__
#define __BITREE_H__

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

typedef char BTDataType;
 
// 定义二叉树节点
typedef struct BinaryTreeNode
{
    int n; // 保存编号
	BTDataType data; // 存放的数据
	struct BinaryTreeNode* left; // 指向左孩子的指针
	struct BinaryTreeNode* right; // 指向右孩子的指针
} BTNode_t;

// 创建新节点
extern BTNode_t* create_binary_tree(int n);
// 递归先序遍历
extern void pre_order_rec(BTNode_t* root);
// 递归中序遍历
extern void in_order_rec(BTNode_t* root);
// 递归后序遍历
extern void post_order_rec(BTNode_t* root);
// 层序遍历
extern void level_order(BTNode_t* root);
// 先序遍历
extern void pre_order(BTNode_t* root);
// 中序遍历
extern void in_order(BTNode_t* root);
// 后序遍历
extern void post_order(BTNode_t* root);

#endif

BiTree.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
#include "BiTree.h"

#include <bits/stdc++.h>

using namespace std;

#define N 6

// 创建新节点
BTNode_t* create_binary_tree(int n)
{
    BTNode_t* root = (BTNode_t*)malloc(sizeof(BTNode_t));
    memset(root, '\x00', sizeof(BTNode_t));

    root->n = n;
    root->left =  NULL;
    root->right = NULL;
    
    printf("input data for node %d : ", n);
    scanf("%c", &(root->data));

    while(getchar() != '\n');

    if (2 * n <= N)
    {
        root->left = create_binary_tree(2 * n);
    }

    if (2 * n + 1 <= N)
    {
        root->right = create_binary_tree(2 * n + 1);
    }

    return root;

}
// 递归先序遍历
void pre_order_rec(BTNode_t* root)
{
    if (NULL == root)
    {
        return;
    }
    printf("%d ==> %c\n", root->n, root->data);
    pre_order_rec(root->left);
    pre_order_rec(root->right);
}
// 递归中序遍历
void in_order_rec(BTNode_t* root)
{
    if (NULL == root)
    {
        return;
    }
    in_order_rec(root->left);
    printf("%d ==> %c\n", root->n, root->data);
    in_order_rec(root->right);
}
// 递归后序遍历
void post_order_rec(BTNode_t* root)
{
    if (NULL == root)
    {
        return;
    }
    post_order_rec(root->left);
    post_order_rec(root->right);
    printf("%d ==> %c\n", root->n, root->data);
}
// 层序遍历
void level_order(BTNode_t* root)
{
    if (NULL == root)
    {
        return;
    }
    BTNode_t* pRoot = root;
    BTNode_t* cur = NULL;

    queue<BTNode_t*> q;
    q.push(pRoot);
    while (!q.empty())
    {
        cur = q.front();
        printf("%d ==> %c\n", cur->n, cur->data);
        if (NULL != cur->left)
        {
            q.push(cur->left);
        }
        if (NULL != cur->right)
        {
            q.push(cur->right);
        }
        q.pop();
    }
}
// 先序遍历 模拟递归即可
void pre_order(BTNode_t* root)
{
    if (NULL == root)
    {
        return;
    }
    BTNode_t* pRoot = root;

    stack<BTNode_t*> s;

    while (pRoot != NULL || !s.empty())
	{
		while (pRoot != NULL)
		{
			s.push(pRoot);
			printf("%d ==> %c\n", pRoot->n, pRoot->data);
			pRoot = pRoot->left;
		}
		if (!s.empty())
		{
			pRoot = s.top();
			s.pop();
			pRoot = pRoot->right;
		}
	}
}
// 中序遍历 模拟递归即可
void in_order(BTNode_t* root)
{
    if (NULL == root)
    {
        return;
    }

    BTNode_t* pRoot = root;
    stack<BTNode_t*> s;

    while (pRoot != NULL || !s.empty())
	{
		while (pRoot != NULL)
		{
			s.push(pRoot);
			pRoot = pRoot->left;
		}
		if (!s.empty())
		{
			pRoot = s.top();
            printf("%d ==> %c\n", pRoot->n, pRoot->data);
			s.pop();
			pRoot = pRoot->right;
		}
	}
}
// 后序遍历
void post_order(BTNode_t* root)
{
	if (NULL == root)
    {
        return;
    }

	stack<BTNode_t*>s;
	BTNode_t* cur = NULL;
    BTNode_t* pre = NULL; // 划分左右结点
    BTNode_t* pRoot = root;

	s.push(pRoot);
	while (!s.empty())
	{
		cur = s.top();
         // pre 不是 cur 左右孩子,则开始遍历当前节点的右子树,中间节点位于右左节点后面,先访问左右,最后访问中间
		if ( (cur->left == NULL && cur->right == NULL) ||  \
			 (pre != NULL && (pre == cur->left || pre == cur->right)) )
		{
			printf("%d ==> %c\n", cur->n, cur->data);
			s.pop();
			pre = cur;
		}
		else
		{
			if (cur->right != NULL)
				s.push(cur->right);
			if (cur->left != NULL)
				s.push(cur->left);
		}
	}
}

main.cpp

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

int main(int argc, char const *argv[])
{
    BTNode_t* root;
    root = create_binary_tree(1);
    /*
    *             [1:a]
    *              /\
    *             /  \
    *            /    \
    *           /      \
    *          /        \
    *       [2:b]       [3:e]
    *        /\          /
    *       /  \        /
    *      /    \      /
    *   [4:c]  [5:d] [6:f]
    **/
    puts("pre_order_rec");
    pre_order_rec(root);
    puts("in_order_rec");
    in_order_rec(root);
    puts("post_order_dec");
    post_order_rec(root);

    puts("pre_order");
    pre_order(root);
    puts("in_order");
    in_order(root);
    puts("post_order");
    post_order(root);
    puts("level_order");
    level_order(root);

    return 0;
}

二叉查找树

二叉查找树的定义（Binary Search Tree）：

  • 该树是一颗二叉树。
  • 如果左子树不为空，则左子树上所有节点的值均小于根节点的值。
  • 如果右子树不为空，则右子树上所有节点的值均大于根节点的值。
  • 左、右子树也都是二叉查找树。

二叉查找树最坏情况就是一个链表。

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

// 定义二叉查找树的节点结构
struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 创建新节点
struct TreeNode* createNode(int value) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 插入节点
struct TreeNode* insert(struct TreeNode* root, int value) {
    // 如果树为空，创建新节点并返回
    if (root == NULL) {
        return createNode(value);
    }

    // 如果值小于当前节点的值，插入到左子树
    if (value < root->data) {
        root->left = insert(root->left, value);
    }
    // 如果值大于当前节点的值，插入到右子树
    else if (value > root->data) {
        root->right = insert(root->right, value);
    }

    // 返回当前节点
    return root;
}

// 查找节点
struct TreeNode* search(struct TreeNode* root, int value) {
    // 如果树为空或找到目标值
    if (root == NULL || root->data == value) {
        return root;
    }

    // 如果值小于当前节点的值，查找左子树
    if (value < root->data) {
        return search(root->left, value);
    }
    // 如果值大于当前节点的值，查找右子树
    else {
        return search(root->right, value);
    }
}

// 中序遍历（用于打印树的内容）
void inorderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

// 测试二叉查找树的创建和查找
int main() {
    struct TreeNode* root = NULL;

    // 插入节点
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    // 中序遍历打印树的内容
    printf("中序遍历结果: \n");
    inorderTraversal(root);
    printf("\n");

    // 查找节点
    int searchValue = 40;
    struct TreeNode* result = search(root, searchValue);
    if (result != NULL) {
        printf("找到节点: %d\n", result->data);
    } else {
        printf("未找到节点: %d\n", searchValue);
    }

    return 0;
}

Splay 树

AVL 树

Huffman 树

哈希表

图的存储结构

邻接矩阵

邻接表

边集数组

链式前向星

位图

位图并没有什么特别值得讲的，属于一种技巧，比如ptmalloc2的堆内存分配，就是用过位图来记录，bins中哪些链表没有被使用，或者已经被使用。64位的位图通过0,1来表示哪些节点已经被使用或为被使用。

高级数据结构

红黑树

Radix 树

跳跃表

这里也包含了确定性跳跃表的实现，之所以把他归纳到这里，是因为他是redis的底层实现，但原理并不算复杂，代码一定程度上比红黑树简单一些。

B 树

B+ 树

MySQL的底层实现。MySQL是持久化数据库，即是存储到磁盘上的，因此查询时要求更少磁盘IO，且mysql是读多写少的场景较多，显然B+树更加适合mysql。

算法

排序算法

冒泡排序

7c9c26a5c5aa806ddff4f502f6f40de6

冒泡基本实现原理：通过相邻元素两两对比将最大或最小的那一个元素往另一边移动，这样下来从左到右每一轮都能得到一个最大或最小元素，再通过一定轮次的比较即实现有序数列。

算法步骤

  1. 比较相邻元素：从列表的第一个元素开始，比较相邻的两个元素。
  2. 交换位置：如果前一个元素比后一个元素大，则交换它们的位置。
  3. 重复遍历：对列表中的每一对相邻元素重复上述步骤，直到列表的末尾。这样，最大的元素会被”冒泡”到列表的最后。
  4. 缩小范围：忽略已经排序好的最后一个元素，重复上述步骤，直到整个列表排序完成。

时间复杂度

  • 最坏情况：O(n²)，当列表是逆序时。
  • 最好情况：O(n)，当列表已经有序时。
  • 平均情况：O(n²)。

空间复杂度

  • O(1)，因为冒泡排序是原地排序算法，不需要额外的存储空间。

经典算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// usage SWAP(&a, &b)
#define SWAP(x, y) ({    \
    typeof(*x) _x = *x;  \
    typeof(*y) _y = *y;  \
    (void) (&_x == &_y); \ // 类型检查
    *x = _y; *y = _x;    \
})

void bubble_sort_0(int arr[], int len)
{
    for (size_t i = 0; i < len-1; i++)
    {
        for (size_t j = 0; j < len-1-i; j++)
        {
            if (arr[j] > arr[j+1])
            {
                swap(arr[j], arr[j+1]); // cpp swap
            }
        }
        
    }
    print_arr(arr, len);
}

**改进算法-提前结束有序 **

由于冒泡排序是相邻两元素依次相比，则若出现一轮未发生元素更换的情况下：即为数组已经有序,则可提前结束。这样的好处是当数组在前几轮对比已经有序之后可以节省不必要的元素对比次数，比如需要排序的数组为[3,1,2,4,5]这样第一大轮比较之后数组已经有序，则会再比一轮发现元素没有发生过交换即退出排序结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void bubble_sort_1(int arr[], int len)
{
    bool flag;
    for (size_t i = 0; i < len-1; i++)
    {
        flag = true;
        for (size_t j = 0; j < len-1-i; j++)
        {
            if (arr[j] > arr[j+1])
            {
                swap(arr[j], arr[j+1]);
                flag = false;
            }
        }
        if(true == flag)
        {
            break;
        }
    }
    print_arr(arr, len);
}

**改进算法-跳过部分有序 **

合优化一中讨论的，我们要使得整轮都有序的情况下才可以提前结束排序操作。但当我们遇到比如 [3,2,1,4,5,6] 这种数组时，后面的4,5,6已经有序的情况下我们在每大轮的比较里可以跳过这部分的小轮两两相比，这样又可以提高一部分的效率。

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
void bubble_sort_2(int arr[], int len)
{
    bool flag;
    // 记录最后一个更换元素时的索引值，下一轮的比较可以自动跳过之后的有序队列
    size_t last_idx = len-1, flag_idx = 0;
    while (true)
    {
        flag = true;
        // 跳过后面有序的部分
        for (size_t i = 0; i < last_idx; i++)
        {
            if (arr[i] > arr[i+1])
            {
                swap(arr[i], arr[i+1]);
                flag = false;
                // 记录最后一个交换时的索引
                flag_idx = i;
            }
        }
        if (true == flag)
        {
            break;
        }
        last_idx = flag_idx;
    }
    
    print_arr(arr, len);
}

**改进算法-两极有序缩略 **

以上的优化总的来说都是分大小两轮，每一大轮排出一个最值到边界。而接下来我们有一个想法，就是一大轮我们同时在左右两边各排出一个最大值与最小值，这样我们的排序效率又会更进一步了。

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
void bubble_sort_3(int arr[], int len)
{
    size_t start = 0, start_pos = start;
    size_t end = len-1, end_pos = end;
    
    while (start < end) 
    {
        for (size_t i = start; i < end; i++) 
        {
            if (arr[i] > arr[i + 1]) 
            {
                swap(arr[i], arr[i+1]);
                end_pos = i;
            }
        }
        // 利用endPos与end位置关系来替代flag变量
        if (end_pos == end) 
        {
            break;
        }
        end = end_pos;
        for (size_t i = end; i > start; i--) 
        {
            if (arr[i] < arr[i - 1]) 
            {
                swap(arr[i], arr[i-1]);
                start_pos = i;
            }
        }
        if (start_pos == start)
        {
            break;
        }
        start = start_pos;
    }

    print_arr(arr, len);
}

选择排序

selectionSort

选择排序（ Selection sort）是一种简单直观的排序算法。它的工作原理是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

算法步骤

  1. 初始化：将列表分为已排序部分和未排序部分。初始时，已排序部分为空，未排序部分为整个列表。
  2. 查找最小值：在未排序部分中查找最小的元素。
  3. 交换位置：将找到的最小元素与未排序部分的第一个元素交换位置。
  4. 更新范围：将未排序部分的起始位置向后移动一位，扩大已排序部分的范围。
  5. 重复步骤：重复上述步骤，直到未排序部分为空，列表完全有序。

时间复杂度

  • 最坏情况：O(n²)，无论输入数据是否有序，都需要进行 n(n-1)/2 次比较。
  • 最好情况：O(n²)，即使列表已经有序，仍需进行相同数量的比较。
  • 平均情况：O(n²)。

空间复杂度

  • O(1)，选择排序是原地排序算法，不需要额外的存储空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void select_sort(int arr[], int len)
{
    int min = 0;
    for (size_t i = 0; i < len - 1; ++i) 
    {
        min = i;
        for (size_t j = i + 1; j < len; ++j)
        {
            if (arr[j] < arr[min])
            {
                min = j;
            }
        }
        swap(arr[i], arr[min]);
    }
    print_arr(arr, len);
}

插入排序

insertionSort

插入排序（Insertion Sort）是一种简单直观的排序算法，它的工作原理类似于整理扑克牌。插入排序通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序和冒泡排序一样，也有优化算法，叫做拆半插入。

算法步骤

  1. 初始化：将列表分为已排序部分和未排序部分。初始时，已排序部分只包含第一个元素，未排序部分包含剩余元素。
  2. 选择元素：从未排序部分中取出第一个元素。
  3. 插入到已排序部分：将该元素与已排序部分的元素从后向前依次比较，找到合适的位置插入。
  4. 重复步骤：重复上述步骤，直到未排序部分为空，列表完全有序。

时间复杂度

  • 最坏情况：O(n²)，当列表是逆序时，每次插入都需要移动所有已排序元素。
  • 最好情况：O(n)，当列表已经有序时，只需遍历一次列表。
  • 平均情况：O(n²)。

空间复杂度

  • O(1)，插入排序是原地排序算法，不需要额外的存储空间。

经典算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void insert_sort_0(int arr[], int len)
{
    for (int i = 1; i < len; ++i) 
    {
        int key = arr[i];
        int j = i-1;
        while ((j >= 0) && (arr[j] > key))
        {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }

    print_arr(arr, len);
}

折半插入

折半插入排序是对直接插入排序)的一种改良方式，时间复杂度为O（n^2），空间复杂度为O（1），是一种稳定的插入排序，在直接插入排序中，每次向已排序序列中插入元素时，都要去寻找插入元素的合适位置，但是这个过程是从已排序序列的最后开始逐一去比较大小的，这其实很是浪费，因为每比较一次紧接着就是元素的移动。折半排序就是通过折半的方式去找到合适的位置，然后一次性进行移动，为插入的元素腾出位置。什么是折半的方式去找合适的位置呢，那就是折半查找了，因为再已排序的序列中，序列元素都是按照顺序排列的，既然这样，完全不需要逐一去比较大小，而是去比较已排序序列的中位数，这个中间的位置将一排序列分为左右两部分，通过一次比较后，就缩小了比较的范围，重复这样的操作，需要插入的元素就找到了合适的位置了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void insert_sort_1(int arr[], int len)
{
    for (int i = 1; i < len; ++i) 
    {
        int key = arr[i]; // 无序首元素

        int low = 0;
        int hight = i-1; // 有序末尾元素

        while (hight >= low) // 二分查找
        {
            int mid = (hight+low)/2;
            if (arr[mid] > key)
            {
                hight = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
            
        }
        // arr[hight] <= key
        for (int j = i-1; j > hight; j--) 
        {
            arr[j+1] = arr[j];
        }
        arr[hight+1] = key;
    }
    print_arr(arr, len);
}

希尔排序

Sorting_shellsort_anim

希尔排序（Shell Sort）是插入排序的一种改进版本，也称为缩小增量排序。它通过将待排序的列表分成若干子列表，对每个子列表进行插入排序，逐步缩小子列表的间隔，最终完成整个列表排序。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。

算法步骤

  1. 选择增量序列：选择一个增量序列（gap sequence），用于将列表分成若干子列表。常见的增量序列有希尔增量（n/2, n/4, ..., 1）等。
  2. 分组插入排序：按照增量序列将列表分成若干子列表，对每个子列表进行插入排序。
  3. 缩小增量：逐步缩小增量，重复上述分组和排序过程，直到增量为 1。
  4. 最终排序：当增量为 1 时，对整个列表进行一次插入排序，完成排序。

示例

  1. 初始状态：
    • 列表：[8, 3, 1, 2, 7, 5, 6, 4]。
    • 初始增量：4（列表长度 8 的一半）。
  2. 第一轮（增量为 4）：
    • 将列表分成 4 个子列表：
      • 子列表 1：[8, 7]。
      • 子列表 2：[3, 5]。
      • 子列表 3：[1, 6]。
      • 子列表 4：[2, 4]。
    • 对每个子列表进行插入排序：
      • 子列表 1：[7, 8]。
      • 子列表 2：[3, 5]。
      • 子列表 3：[1, 6]。
      • 子列表 4：[2, 4]。
    • 排序后的列表：[7, 3, 1, 2, 8, 5, 6, 4]。
  3. 第二轮（增量为 2）：
    • 将列表分成 2 个子列表：
      • 子列表 1：[7, 1, 8, 6]。
      • 子列表 2：[3, 2, 5, 4]。
    • 对每个子列表进行插入排序：
      • 子列表 1：[1, 6, 7, 8]。
      • 子列表 2：[2, 3, 4, 5]。
    • 排序后的列表：[1, 2, 6, 3, 7, 4, 8, 5]。
  4. 第三轮（增量为 1）：
    • 将整个列表视为一个子列表，进行插入排序。
    • 排序后的列表：[1, 2, 3, 4, 5, 6, 7, 8]。

时间复杂度

希尔排序的时间复杂度取决于增量序列的选择：

  • 最坏情况：O(n²)，当增量序列选择不当时。
  • 最好情况：O(n log n)，当增量序列选择合适时。
  • 平均情况：O(n log n) 到 O(n²) 之间。

常见的增量序列：

  • 希尔增量：n/2, n/4, ..., 1，时间复杂度为 O(n²)。
  • Hibbard 增量：1, 3, 7, 15, ..., 2^k - 1，时间复杂度为 O(n^(3/2))。
  • Sedgewick 增量：1, 5, 19, 41, 109, ...，时间复杂度为 O(n^(4/3))。

空间复杂度

  • O(1)，希尔排序是原地排序算法，不需要额外的存储空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void shell_sort(int arr[], int len)
{
    for (int gap = len/2; gap > 0; gap /= 2) 
    {
        for (int i = gap; i < len; i++) 
        {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j-gap] > temp; j -= gap)
            {
                arr[j] = arr[j-gap];
            }
            arr[j] = temp;
        }
    }
    print_arr(arr, len);
}

快速排序

快速排序（Quick Sort）是一种高效的排序算法，基于分治法（Divide and Conquer）的思想。它的核心是通过选择一个基准元素（pivot），将列表分为两部分：一部分小于基准元素，另一部分大于基准元素，然后递归地对这两部分进行排序。快速排序的平均时间复杂度为 O(n log n)，在实际应用中性能优异。

quickSort

算法步骤

  1. 选择基准元素：从列表中选择一个元素作为基准（pivot）。选择方式可以是第一个元素、最后一个元素、中间元素或随机元素。
  2. 分区：将列表重新排列，使得所有小于基准元素的元素都在基准的左侧，所有大于基准元素的元素都在基准的右侧。基准元素的位置在分区完成后确定。
  3. 递归排序：对基准元素左侧和右侧的子列表分别递归地进行快速排序。
  4. 合并：由于分区操作是原地进行的，递归结束后整个列表已经有序。

时间复杂度

  • 分解：每次将列表分成两半，需要 O(log n) 层递归。
  • 合并：每层递归需要 O(n) 的时间来合并子列表。
  • 总时间复杂度：O(n log n)。

空间复杂度

  • O(n)，归并排序需要额外的空间来存储临时列表。
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
void quick_sort_real(int array[], int low, int high) 
{
    int i = low; 
    int j = high;
    if(i >= j) 
    {
        return;
    }
 
    int temp = array[low];
    while(i != j) 
    {
        while(array[j] >= temp && i < j) 
        {
            j--;
        }
	    while(array[i] <= temp && i < j) 
        {
            i++;
        }
	    if(i < j) 
        {
            swap(array[i], array[j]);
        }
    }
 
    //将基准temp放于自己的位置，（第i个位置）
    swap(array[low], array[i]);
    quick_sort_real(array, low, i - 1);
    quick_sort_real(array, i + 1, high);
}
void quick_sort(int arr[], int len)
{
    quick_sort_real(arr, 0, len-1);
    print_arr(arr, len);
}

堆排序

Sorting_heapsort_anim

算法步骤

  1. 首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端

  2. 将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1

  3. 将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组

注意:升序用大根堆，降序就用小根堆(默认为升序)

时间复杂度

  • 构建最大堆：O(n)。
  • 每次调整堆：O(log n)，总共需要调整 n-1 次。
  • 总时间复杂度：O(n log n)。

空间复杂度

  • O(1)，堆排序是原地排序算法，不需要额外的存储空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void max_heapify(int arr[], int start, int end) 
{
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) 
    {
        if (son + 1 <= end && arr[son] < arr[son + 1])
        {
            son++;
        }
        if (arr[dad] > arr[son])
        {
            return;
        }
        else 
        {
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}
void heap_sort(int arr[], int len)
{
    int i;

    for (i = len / 2 - 1; i >= 0; i--)
    {
        max_heapify(arr, i, len - 1);
    }

    for (i = len - 1; i > 0; i--) 
    {
        swap(arr[0], arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}

归并排序

参考链接

算法步骤

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
  4. 重复步骤 3 直到某一指针达到序列尾；
  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

假设有一个待排序的列表 [38, 27, 43, 3, 9, 82, 10]，归并排序的过程如下：

  1. 分解：
    • 将列表分成两半：[38, 27, 43, 3] 和 [9, 82, 10]。
    • 继续分解：
      • [38, 27, 43, 3] 分成 [38, 27] 和 [43, 3]。
      • [9, 82, 10] 分成 [9] 和 [82, 10]。
    • 继续分解：
      • [38, 27] 分成 [38] 和 [27]。
      • [43, 3] 分成 [43] 和 [3]。
      • [82, 10] 分成 [82] 和 [10]。
    • 最终分解为单个元素的子列表。
  2. 合并：
    • 合并 [38] 和 [27] 得到 [27, 38]。
    • 合并 [43] 和 [3] 得到 [3, 43]。
    • 合并 [27, 38] 和 [3, 43] 得到 [3, 27, 38, 43]。
    • 合并 [9] 和 [10, 82] 得到 [9, 10, 82]。
    • 合并 [3, 27, 38, 43] 和 [9, 10, 82] 得到最终有序列表 [3, 9, 10, 27, 38, 43, 82]。

时间复杂度

  • 分解：每次将列表分成两半，需要 O(log n) 层递归。
  • 合并：每层递归需要 O(n) 的时间来合并子列表。
  • 总时间复杂度：O(n log n)。

空间复杂度

  • O(n)，归并排序需要额外的空间来存储临时列表。
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
int min(int x, int y) 
{
    return x < y ? x : y;
}
void merge_sort(int arr[], int len) 
{
    int *a = arr;
    int *b = (int *) malloc(len * sizeof(int));
    int seg, start;
    for (seg = 1; seg < len; seg += seg) 
    {
        for (start = 0; start < len; start += seg * 2) 
        {
            int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) 
    {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}

查找算法

这里记录经典的查找算法，例如顺序查找，二分查找，插入查找，斐波那契查找，树相关的查找，哈希查找在数据结构部分实现。

图算法

DFS深度优先搜索算法

BFS广度优先搜索算法

启发式搜索

最短路径

DP 算法

NP 算法

网络流

外部算法

哈希算法

机器学习算法

移步《机器学习》

安全算法(密码学)

安全算法的加解密还是归纳到了这里，具体请看博客另一篇文章《密码学笔记》

算法题解

钟球问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
//link_queue.h
#ifndef __LINK_QUEUE_H__
#define __LINK_QUEUE_H__

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

typedef int data_t;

typedef struct qnode
{
    data_t data;
    struct qnode *next;
} qlinknode_t;

typedef struct
{
    qlinknode_t *front;
    qlinknode_t *rear;
    int n;
}linkqueue_t;

extern linkqueue_t *create_empty_linkqueue();

extern bool is_empty_linkqueue(linkqueue_t *queue);

extern bool enqueue_linkqueue(linkqueue_t *queue, data_t value);

extern data_t dequeue_linkqueue(linkqueue_t *queue);

extern int get_num_of_linkqueue(linkqueue_t *queue);

#endif
//link_queue.c
#include "link_queue.h"

linkqueue_t *create_empty_linkqueue()
{
    linkqueue_t * q = (linkqueue_t*)malloc(sizeof(linkqueue_t));
    if (NULL == q)
    {
        perror("Failed to allocate memory for link queue");
        return NULL;
    }
    q->front = q->rear = NULL;
    q->n = 0;
    return q;
}

bool is_empty_linkqueue(linkqueue_t *queue)
{
    return queue->front == NULL || queue->rear == NULL;
}

bool enqueue_linkqueue(linkqueue_t *queue, data_t value)
{
    qlinknode_t* new_node = (qlinknode_t*)malloc(sizeof(qlinknode_t));
    if (NULL == new_node)
    {
        perror("Failed to allocate memory for new node in link queue");
        return false;
    }
    new_node->data = value;
    new_node->next = NULL;
    queue->n++;

    if (is_empty_linkqueue(queue))
    {
        queue->front = queue->rear = new_node;
        return true;
    }

    queue->rear->next = new_node;
    queue->rear = new_node;
    return true;
}

data_t dequeue_linkqueue(linkqueue_t *queue)
{
    if (is_empty_linkqueue(queue))
    {
        perror("queue is empty");
        return -1;
    }
    
    qlinknode_t* temp = queue->front;

    if (NULL != queue->front->next)
    {
        queue->front = queue->front->next;
    }
    else
    {
        queue->front = queue->rear = NULL;
    }

    data_t data = temp->data;
    free(temp);
    temp = NULL;
    queue->n--;
    return data;
}
int get_num_of_linkqueue(linkqueue_t *queue)
{
    return queue->n;
}
//link_stack.h
#ifndef __LINK_STACK_H__
#define __LINK_STACK_H__

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

typedef int data_t;

typedef struct snode
{
    data_t data;
    struct snode *next;
} slinknode_t;

typedef struct 
{
    slinknode_t *top;
    int n;
} linkstack_t;

extern linkstack_t * create_empty_linkstack();

extern int is_empty_linkstack(linkstack_t *s);

extern int push_linkstack(linkstack_t *s, data_t data);

extern data_t pop_linkstack(linkstack_t *s);

extern data_t get_top_data(linkstack_t *s);

extern int get_num_of_linkstack(linkstack_t *s);

#endif
//link_stack.c
#include "link_stack.h"

linkstack_t * create_empty_linkstack()
{
    linkstack_t *s = (linkstack_t *)malloc(sizeof(linkstack_t));
    if (NULL == s)
    {
        perror("Failed to allocate memory for link stack");
        return NULL;
    }
    s->top = NULL;
    s->n = 0;
    return s;
}

int is_empty_linkstack(linkstack_t *s)
{
    return s->top == NULL;
}

int push_linkstack(linkstack_t *s, data_t data)
{
    slinknode_t *new_node = (slinknode_t *)malloc(sizeof(slinknode_t));
    if (NULL == new_node)
    {
        perror("Failed to allocate memory for new node");
        return -1;
    }
    new_node->data = data;
    new_node->next = s->top;
    s->top = new_node;
    s->n++;
    return 0;
}

data_t pop_linkstack(linkstack_t *s)
{
    if (is_empty_linkstack(s))
    {
        perror("Stack is empty");
        return -1;
    }
    slinknode_t* top_node = s->top;
    s->top = top_node->next;
    data_t data = top_node->data;
    free(top_node);
    top_node = NULL;
    s->n--;
    return data;
}

data_t get_top_data(linkstack_t *s)
{
    if (is_empty_linkstack(s))
    {
        perror("Stack is empty"); 
        return -1;
    }
    return s->top->data;
}

int get_num_of_linkstack(linkstack_t *s)
{
    return s->n;
}
//main.c
#include "link_queue.h"
#include "link_stack.h"

#define N 27

bool is_orginal_queue(linkqueue_t * lq) 
{
	qlinknode_t* p;

	if (NULL == lq) {
		printf("lq is NULL\n");
		return -1;
	}

	p = lq->front;

	while (p && p->next)
    {
		if (p->data < p->next->data) 
        {
			p = p->next;
		}
        else 
        {
			return false;
		}
	}
	return true;
}

int main(int argc, char const *argv[])
{
    linkqueue_t* ball_queue = create_empty_linkqueue();
    linkstack_t* min_stack = create_empty_linkstack();
    linkstack_t* min5_stack = create_empty_linkstack();
    linkstack_t* hour_stack = create_empty_linkstack();

    int min = 0;
    int ball = 0;
    int half_day = 0;

    for (size_t i = 0; i < N; i++)
    {
        enqueue_linkqueue(ball_queue, i);
    }

    while (true)
    {
        ball = dequeue_linkqueue(ball_queue);
        min++;
        if(get_num_of_linkstack(min_stack) < 4)
        {
            push_linkstack(min_stack, ball);
            continue;
        }

        while(!is_empty_linkstack(min_stack))
        {
            enqueue_linkqueue(ball_queue,pop_linkstack(min_stack));
        }

        if(get_num_of_linkstack(min5_stack) < 11)
        {
            push_linkstack(min5_stack, ball);
            continue;
        }

        while(!is_empty_linkstack(min5_stack))
        {
            enqueue_linkqueue(ball_queue,pop_linkstack(min5_stack));
        }

        if(get_num_of_linkstack(hour_stack) < 11)
        {
            push_linkstack(hour_stack, ball);
            continue;
        }

        while(!is_empty_linkstack(hour_stack))
        {
            enqueue_linkqueue(ball_queue,pop_linkstack(hour_stack));
        }
        // 满时间最后一球入队
        enqueue_linkqueue(ball_queue, ball);

        half_day++;

        if(is_orginal_queue(ball_queue))
        {
            break;
        }  
    }
    // 23 33120
    printf("days ==> %d\nmin ==>%d\n", half_day / 2, min);
    
    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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>

using namespace std;

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

int calculate(int a, int b, char op) 
{
    switch (op) 
    {
        case '+': 
            return a + b;
            break;
        case '-': 
            return a - b;
            break;
        case '*': 
            return a * b;
            break;
        case '/': 
            return a / b;
            break;
        default: 
            return 0;
    }
}

// 处理栈中的操作符并计算
void process_stack(stack<int>& operand_stack, stack<char>& operator_stack) 
{
    int b = operand_stack.top(); operand_stack.pop();
    int a = operand_stack.top(); operand_stack.pop();

    char op = operator_stack.top(); operator_stack.pop();

    operand_stack.push(calculate(a, b, op));
}

// 计算表达式的值
int evaluate_expression(const string& expr) 
{
    stack<int> operand_stack;
    stack<char> operator_stack;

    for (size_t i = 0; i < expr.length(); ++i) 
    {
        char ch = expr[i];

        if (ch == ' ') 
        {
            continue;
        }

        if (isdigit(ch)) 
        {
            int num = 0;
            while (i < expr.length() && isdigit(expr[i])) 
            {
                num = num * 10 + (expr[i] - '0');
                i++;
            }
            i--; // 回退多读取的字符
            operand_stack.push(num);
        }
        else if (ch == '(') 
        {
            operator_stack.push(ch);
        }
        else if (ch == ')') 
        {
            while (!operator_stack.empty() && operator_stack.top() != '(') 
            {
                process_stack(operand_stack, operator_stack);
            }
            if (!operator_stack.empty() && operator_stack.top() == '(') 
            {
                operator_stack.pop(); // 弹出左括号
            }
        }
        else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') 
        {
            while (!operator_stack.empty() &&
                   precedence(operator_stack.top()) >= precedence(ch) &&
                   operator_stack.top() != '(') 
            {
                process_stack(operand_stack, operator_stack);
            }
            operator_stack.push(ch);
        }
        else
        {
            puts("Invalid character in expression");
            exit(1);
        }
    }

    // 最后处理剩余的运算符
    while (!operator_stack.empty()) 
    {
        process_stack(operand_stack, operator_stack);
    }

    return operand_stack.top();  // 返回最终计算结果
}

int main() 
{
    string expr;
    puts("Enter an expression:");
    getline(cin, expr);

    int result = evaluate_expression(expr);
    printf("Result: %d\n", result);

    return 0;
}

主要参考文献

《数据结构与算法 C 语言描述》

《算法导论 第三版》

《算法 C 语言实现 全集》

《算法图解》

  • Title: 数据结构及算法
  • Author: 韩乔落
  • Created at : 2025-01-03 17:27:33
  • Updated at : 2025-04-02 16:41:15
  • Link: https://jelasin.github.io/2025/01/03/数据结构及算法/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
数据结构及算法
  1. 前言
  2. 基础知识
    1. 大O表示法
  3. 初级数据结构
    1. 顺序表
    2. 单链表
    3. 双链表
    4. 单循环链表
    5. 双循环链表
    6. 十字链表
    7. 顺序栈
    8. 链式栈
    9. 双端栈
    10. 循环队列
    11. 链式队列
    12. 双端队列
    13. 优先队列
  4. 中级数据结构
    1. 二叉树
    2. 二叉查找树
    3. Splay 树
    4. AVL 树
    5. Huffman 树
    6. 哈希表
    7. 图的存储结构
      1. 邻接矩阵
      2. 邻接表
      3. 边集数组
      4. 链式前向星
    8. 位图
  5. 高级数据结构
    1. 红黑树
    2. Radix 树
    3. 跳跃表
    4. B 树
    5. B+ 树
  6. 算法
    1. 排序算法
      1. 冒泡排序
      2. 选择排序
      3. 插入排序
      4. 希尔排序
      5. 快速排序
      6. 堆排序
      7. 归并排序
    2. 查找算法
    3. 图算法
      1. DFS深度优先搜索算法
      2. BFS广度优先搜索算法
      3. 启发式搜索
      4. 最短路径
    4. DP 算法
    5. NP 算法
    6. 网络流
    7. 外部算法
    8. 哈希算法
    9. 机器学习算法
    10. 安全算法(密码学)
  7. 算法题解
    1. 钟球问题
    2. 表达式求值
  8. 主要参考文献