数据结构 表结构实现

本文最后更新于 2025年9月11日 晚上

值，指针，引用与数组

我们知道，C语言的代码实现经过了预处理，编译，汇编，链接，加载，执行的过程。在这个过程中，进行了对编码的控制与处理。在完成处理之后，以上的概念被对应到内存中的：

  1. 值： 通过确定的地址与偏移量，使用命令将对应的内存地址段解释为对应的值（整型，浮点型，无符号整型，字符，以及地址值（指针））
  2. 指针：定长的内存段，用于存储一个地址信息，通过声明或者强制转换确定地址段长度
  3. 引用：编译时概念，主要应用于高级语言，在高级语言的加载过程中被替换为直接引用（即实际变量的内存地址）
  4. 数组：C实现的数组内存地址即为数组中第一个元素的地址，编译器对数组类型做了以下限制：
    1. 不允许对数组变量名进行直接赋值（不允许数组变量名在初始化后作为左值）
    2. 通过下标对数组中的元素进行访问
    3. 允许声明一个指针指向数组（数组作为一个地址赋值给指针）

数组增强

C数组实现的缺陷

C通过简单快捷的实现完成了 数组基础的随机访问功能，但是它仍然存在以下不足：

  1. 初始化后的数组是一个定长数组，无法随着元素的增加自动扩容
  2. 数组以”\0“ 为结尾，意味着在数组中无法存储”\0“ 字符，通过需要通过字符判断去判断数组的结尾
  3. 数组只提供了最基础的元素存储功能，结构简陋

数组增强示例：SDS

SDS 是一种优雅的数组增强实现，它的实现思路是定义了一个头结构，其中增加了用于描述数组实际存储长度的len 和 空闲空间的free 。通过初始化过程动态申请内存存储初始化的字符数组，返回的是对应的字符数组段。这样我们既可以通过判断”\0”的方式 使用原有数组，又可以使用头偏移向SDS头查询数组长度。

通过这个扩展，向数组增加了扩容功能。通过判断空余空间的大小，我们可以判断是否申请更多的内存空间进行结构存储。

SDS

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

/* SDS 头部结构 */
typedef struct sdshdr {
    int len;    // 已使用长度
    int free;   // 空闲空间
    char buf[]; // 实际数据
} sdshdr;

/* 定义 sds 为 char* 类型，方便操作 */
typedef char *sds;

/* 创建一个新的 SDS */
sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);     // sds 初始化
    sdshdr *sh = malloc(sizeof(sdshdr) + initlen + 1);      // 从堆中申请内存创建sdshdr实例
    if (!sh) return NULL;

    sh->len = initlen;                                      // 设置数组长
    sh->free = 0;                                           // 设置空闲数组长
    if (initlen && init) {
        memcpy(sh->buf, init, initlen);                     // 将传入的字符数组拷贝到buf中
    }
    sh->buf[initlen] = '\\0';
    return (char*)sh->buf;                                  // 返回的是一个标准的C数组结构
}

/* 获取 SDS 长度 */
size_t sdslen(const sds s) {
    sdshdr *sh = (sdshdr*)(s - sizeof(sdshdr));             // 通过头长度偏移查询头结构 
    return sh->len;                                         // 获取长度信息
}

/* 获取剩余空间 */
size_t sdsavail(const sds s) {                           
    sdshdr *sh = (sdshdr*)(s - sizeof(sdshdr));             // 通过头长度偏移查询头结构 
    return sh->free;                                        // 获取剩余空间信息  
}

/* 扩容函数 */
sds sdsMakeRoomFor(sds s, size_t addlen) {
    sdshdr *sh = (sdshdr*)(s - sizeof(sdshdr));
    size_t free = sh->free;
    if (free >= addlen) return s;                           // 增加的数据小于空余空间时，返回s
    size_t newlen = sh->len + addlen;                       // 扩容策略：小于 1MB 翻倍，大于 1MB 每次加 1MB
    if (newlen < 1024*1024)
        newlen *= 2;
    else
        newlen += 1024*1024;
    sh = realloc(sh, sizeof(sdshdr) + newlen + 1);          // 扩展内存空间
    if (!sh) return NULL;
    sh->free = newlen - sh->len;
    return sh->buf;
}

/* 拼接字符串 */
sds sdscat(sds s, const char *t) {
    size_t tlen = strlen(t);
    s = sdsMakeRoomFor(s, tlen);
    sdshdr *sh = (sdshdr*)(s - sizeof(sdshdr));
    memcpy(s + sh->len, t, tlen);
    sh->len += tlen;
    sh->free -= tlen;
    s[sh->len] = '\\0';
    return s;
}

/* 释放 SDS */
void sdsfree(sds s) {
    if (s == NULL) return;
    free(s - sizeof(sdshdr));
}

数组增强示例：StringBuilder / StringBuffer

StringBuilder

Java中的StringBuilder 也是一种字符数组的增强实现。它也提供了扩容机制。当向StringBuilder中增加字符串数据时，判断 最小所需容量与当前容量的较大值，创建新的对象，复制原StringBuilder对象中的值和新值插入到新的StringBuidler中去。

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
public class MyStringBuilder {
    private char[] value;   // 存储字符数组
    private int count;      // 已经使用的字符个数

    // 默认初始容量
    private static final int DEFAULT_CAPACITY = 16;

    // 构造方法
    public MyStringBuilder() {
        value = new char[DEFAULT_CAPACITY];
        count = 0;
    }

    public MyStringBuilder(String str) {
        int capacity = str.length() + DEFAULT_CAPACITY;
        value = new char[capacity];
        append(str);
    }

    // 追加字符串
    public MyStringBuilder append(String str) {
        if (str == null) str = "null";
        int len = str.length();
        ensureCapacity(count + len);
        str.getChars(0, len, value, count); // 把 str 拷贝进内部数组
        count += len;
        return this;
    }

    // 追加单个字符
    public MyStringBuilder append(char c) {
        ensureCapacity(count + 1);
        value[count++] = c;
        return this;
    }

    // 确保容量足够，不够就扩容
    private void ensureCapacity(int minimumCapacity) {
        if (minimumCapacity > value.length) {
            int newCapacity = Math.max(value.length * 2, minimumCapacity);
            char[] newValue = new char[newCapacity];
            System.arraycopy(value, 0, newValue, 0, count);
            value = newValue;
        }
    }

    // 转换成 String
    @Override
    public String toString() {
        return new String(value, 0, count);
    }

    // 获取当前长度
    public int length() {
        return count;
    }
}

链表增强

单链表的局限性

通过实现单链表，我们完成了链表数据间的松散关联，但是在实际应用用，单链表往往会因为其结构导致查询性能降低到O（n）。我们可以通过增加每个节点中的信息，提高链表整体的查询效率。

双向链表

双向链表

双向链表通过向node结构中增加prev指针，将node与先后节点都进行关联，同时在链表结构中保留指向head和tail的指针，这样允许用户可以从头部和尾部分别进行添加/删除提高了原来的对尾部节点的查询效率。

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 <stdlib.h>

/* 节点结构 */
typedef struct DListElmt_ {
    void *data;                 // 节点存储的数据
    struct DListElmt_ *prev;    // 前驱
    struct DListElmt_ *next;    // 后继
} DListElmt;

/* 链表结构 */
typedef struct DList_ {
    int size;                           // 链表当前大小
    int (*match)(const void *key1, const void *key2); // 匹配函数，可选
    void (*destroy)(void *data);        // 数据销毁回调
    DListElmt *head;                    // 链表头
    DListElmt *tail;                    // 链表尾
} DList;

/* 初始化链表 */
void dlist_init(DList *list, void (*destroy)(void *data));

/* 销毁链表 */
void dlist_destroy(DList *list);

/* 在指定节点之后插入 */
int dlist_ins_next(DList *list, DListElmt *element, const void *data);

/* 在指定节点之前插入 */
int dlist_ins_prev(DList *list, DListElmt *element, const void *data);

/* 移除指定节点 */
int dlist_remove(DList *list, DListElmt *element, void **data);

/* 获取链表大小 */
#define dlist_size(list) ((list)->size)

/* 获取链表头尾 */
#define dlist_head(list) ((list)->head)
#define dlist_tail(list) ((list)->tail)

/* 判断节点 */
#define dlist_is_head(element) ((element)->prev == NULL ? 1 : 0)
#define dlist_is_tail(element) ((element)->next == NULL ? 1 : 0)

/* 获取前驱和后继 */
#define dlist_prev(element) ((element)->prev)
#define dlist_next(element) ((element)->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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* 节点结构 */
typedef struct DListElmt_ {
    void *data;
    struct DListElmt_ *prev;
    struct DListElmt_ *next;
} DListElmt;

/* 链表结构 */
typedef struct DList_ {
    int size;
    int (*match)(const void *key1, const void *key2);
    void (*destroy)(void *data);
    DListElmt *head;
    DListElmt *tail;
} DList;

/* 初始化链表 */
void dlist_init(DList *list, void (*destroy)(void *data)) {
    list->size = 0;
    list->destroy = destroy;
    list->match = NULL;
    list->head = NULL;
    list->tail = NULL;
}

/* 销毁链表 */
void dlist_destroy(DList *list) {
    void *data;
    DListElmt *element;

    while (list->size > 0) {
        element = list->head;
        if (dlist_remove(list, element, (void **)&data) == 0 && list->destroy != NULL) {
            list->destroy(data);
        }
    }
    memset(list, 0, sizeof(DList));
}

/* 在指定节点之后插入 */
int dlist_ins_next(DList *list, DListElmt *element, const void *data) {
    DListElmt *new_element;

    if (element == NULL && list->size != 0)
        return -1;

    if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL)
        return -1;

    new_element->data = (void *)data;

    if (list->size == 0) {
        list->head = new_element;
        list->tail = new_element;
        new_element->prev = NULL;
        new_element->next = NULL;
    } else {
        new_element->next = element->next;
        new_element->prev = element;

        if (element->next == NULL)
            list->tail = new_element;
        else
            element->next->prev = new_element;

        element->next = new_element;
    }

    list->size++;
    return 0;
}

/* 在指定节点之前插入 */
int dlist_ins_prev(DList *list, DListElmt *element, const void *data) {
    DListElmt *new_element;

    if (element == NULL && list->size != 0)
        return -1;

    if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL)
        return -1;

    new_element->data = (void *)data;

    if (list->size == 0) {
        list->head = new_element;
        list->tail = new_element;
        new_element->prev = NULL;
        new_element->next = NULL;
    } else {
        new_element->next = element;
        new_element->prev = element->prev;

        if (element->prev == NULL)
            list->head = new_element;
        else
            element->prev->next = new_element;

        element->prev = new_element;
    }

    list->size++;
    return 0;
}

/* 移除指定节点 */
int dlist_remove(DList *list, DListElmt *element, void **data) {
    if (element == NULL || list->size == 0)
        return -1;

    *data = element->data;

    if (element == list->head) {
        list->head = element->next;

        if (list->head == NULL)
            list->tail = NULL;
        else
            element->next->prev = NULL;
    } else {
        element->prev->next = element->next;

        if (element->next == NULL)
            list->tail = element->prev;
        else
            element->next->prev = element->prev;
    }

    free(element);
    list->size--;

    return 0;
}

/* 宏函数接口 */
#define dlist_size(list) ((list)->size)
#define dlist_head(list) ((list)->head)
#define dlist_tail(list) ((list)->tail)
#define dlist_is_head(element) ((element)->prev == NULL ? 1 : 0)
#define dlist_is_tail(element) ((element)->next == NULL ? 1 : 0)
#define dlist_prev(element) ((element)->prev)
#define dlist_next(element) ((element)->next)

指针数组

指针数组

指针数组的思路是构建一个数组结构存储链表中的元素的指针，实现对链表中数据的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
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

// 动态指针数组结构
typedef struct PointerArray {
    void **data;        // 指针数组
    size_t size;        // 当前元素个数
    size_t capacity;    // 当前容量
    void (*free_func)(void *); // 自定义释放函数
} PointerArray;

// 初始容量
#define INITIAL_CAPACITY 8
PointerArray* pointer_array_create(void (*free_func)(void *)) {
    PointerArray *arr = (PointerArray*)malloc(sizeof(PointerArray));
    if (!arr) {
        fprintf(stderr, "Memory allocation failed\\n");
        return NULL;
    }
    arr->data = (void**)malloc(sizeof(void*) * INITIAL_CAPACITY);
    if (!arr->data) {
        free(arr);
        fprintf(stderr, "Memory allocation failed\\n");
        return NULL;
    }
    arr->size = 0;
    arr->capacity = INITIAL_CAPACITY;
    arr->free_func = free_func;
    // 初始化所有指针为NULL
    for (size_t i = 0; i < arr->capacity; i++) {
        arr->data[i] = NULL;
    }
  
    return arr;
}

// 扩容函数
int pointer_array_resize(PointerArray *arr, size_t new_capacity) {
    if (!arr) return 0;
    void **new_data = (void**)realloc(arr->data, sizeof(void*) * new_capacity);
    if (!new_data) {
        fprintf(stderr, "Memory reallocation failed\\n");
        return 0;
    }
    arr->data = new_data;
    // 如果扩容，将新位置初始化为NULL
    if (new_capacity > arr->capacity) {
        for (size_t i = arr->capacity; i < new_capacity; i++) {
            arr->data[i] = NULL;
        }
    }
    arr->capacity = new_capacity;
    return 1;
}

// 添加元素到末尾
int pointer_array_push(PointerArray *arr, void *ptr) {
    if (!arr) return 0;
    // 检查是否需要扩容
    if (arr->size >= arr->capacity) {
        size_t new_capacity = arr->capacity * 2;
        if (!pointer_array_resize(arr, new_capacity)) {
            return 0;
        }
    }
    arr->data[arr->size] = ptr;
    arr->size++;
    return 1;
}

// 在指定位置插入元素
int pointer_array_insert(PointerArray *arr, size_t index, void *ptr) {
    if (!arr || index > arr->size) return 0;
    // 检查是否需要扩容
    if (arr->size >= arr->capacity) {
        size_t new_capacity = arr->capacity * 2;
        if (!pointer_array_resize(arr, new_capacity)) {
            return 0;
        }
    }
    // 向后移动元素
    for (size_t i = arr->size; i > index; i--) {
        arr->data[i] = arr->data[i - 1];
    }
    arr->data[index] = ptr;
    arr->size++;
    return 1;
}

// 获取指定位置的元素
void* pointer_array_get(PointerArray *arr, size_t index) {
    if (!arr || index >= arr->size) {
        return NULL;
    }
    return arr->data[index];
}

// 设置指定位置的元素
int pointer_array_set(PointerArray *arr, size_t index, void *ptr) {
    if (!arr || index >= arr->size) return 0;
    // 如果有自定义释放函数且原位置有数据，先释放
    if (arr->free_func && arr->data[index]) {
        arr->free_func(arr->data[index]);
    }
    arr->data[index] = ptr;
    return 1;
}

// 删除末尾元素
void* pointer_array_pop(PointerArray *arr) {
    if (!arr || arr->size == 0) return NULL;
    arr->size--;
    void *ptr = arr->data[arr->size];
    arr->data[arr->size] = NULL;
    // 如果使用空间过少，可以考虑缩容
    if (arr->size < arr->capacity / 4 && arr->capacity > INITIAL_CAPACITY) {
        size_t new_capacity = arr->capacity / 2;
        pointer_array_resize(arr, new_capacity);
    }
    return ptr;
}

// 删除指定位置的元素
void* pointer_array_remove(PointerArray *arr, size_t index) {
    if (!arr || index >= arr->size) return NULL;  
    void *ptr = arr->data[index];  
    // 向前移动元素
    for (size_t i = index; i < arr->size - 1; i++) {
        arr->data[i] = arr->data[i + 1];
    }  
    arr->size--;
    arr->data[arr->size] = NULL;  
    // 考虑缩容
    if (arr->size < arr->capacity / 4 && arr->capacity > INITIAL_CAPACITY) {
        size_t new_capacity = arr->capacity / 2;
        pointer_array_resize(arr, new_capacity);
    }  
    return ptr;
}

// 查找元素（线性搜索）
int pointer_array_find(PointerArray *arr, void *ptr) {
    if (!arr) return -1;  
    for (size_t i = 0; i < arr->size; i++) {
        if (arr->data[i] == ptr) {
            return (int)i;
        }
    }
    return -1;
}

// 使用自定义比较函数查找元素
int pointer_array_find_by_compare(PointerArray *arr, void *target, 
    int (*compare)(const void *, const void *)) {
    if (!arr || !compare) return -1;  
    for (size_t i = 0; i < arr->size; i++) {
        if (compare(arr->data[i], target) == 0) {
            return (int)i;
        }
    }
    return -1;
}

// 排序（使用快速排序）
void pointer_array_sort(PointerArray *arr, int (*compare)(const void *, const void *)) {
    if (!arr || !compare || arr->size <= 1) return;
    qsort(arr->data, arr->size, sizeof(void*), compare);
}

// 遍历数组并对每个元素执行函数
void pointer_array_foreach(PointerArray *arr, void (*func)(void *, void *), void *user_data) {
    if (!arr || !func) return;  
    for (size_t i = 0; i < arr->size; i++) {
        if (arr->data[i]) {
            func(arr->data[i], user_data);
        }
    }
}

// 清空数组（可选择是否释放元素内存）
void pointer_array_clear(PointerArray *arr, int free_elements) {
    if (!arr) return;  
    if (free_elements && arr->free_func) {
        for (size_t i = 0; i < arr->size; i++) {
            if (arr->data[i]) {
                arr->free_func(arr->data[i]);
                arr->data[i] = NULL;
            }
        }
    } else {
        for (size_t i = 0; i < arr->size; i++) {
            arr->data[i] = NULL;
        }
    }  
    arr->size = 0;
}

// 获取数组大小
size_t pointer_array_size(PointerArray *arr) {
    return arr ? arr->size : 0;
}

// 获取数组容量
size_t pointer_array_capacity(PointerArray *arr) {
    return arr ? arr->capacity : 0;
}

// 检查数组是否为空
int pointer_array_is_empty(PointerArray *arr) {
    return arr ? (arr->size == 0) : 1;
}

// 销毁指针数组
void pointer_array_destroy(PointerArray *arr, int free_elements) {
    if (!arr) return;  
    // 清空所有元素
    pointer_array_clear(arr, free_elements);  
    // 释放数据数组
    free(arr->data);  
    // 释放结构体
    free(arr);
}

// 打印数组信息（调试用）
void pointer_array_print_info(PointerArray *arr) {
    if (!arr) {
        printf("PointerArray: NULL\\n");
        return;
    }  
    printf("PointerArray Info:\\n");
    printf("  Size: %zu\\n", arr->size);
    printf("  Capacity: %zu\\n", arr->capacity);
    printf("  Memory usage: %zu bytes\\n", arr->capacity * sizeof(void*));
    printf("  Load factor: %.2f%%\\n", 
           arr->capacity > 0 ? (double)arr->size / arr->capacity * 100 : 0.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
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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define MAX_LEVEL 16    // 最大层数
#define PROBABILITY 0.5 // 晋升到下一层的概率

// 跳表节点结构
typedef struct SkipListNode {
    int key;
    int value;
    struct SkipListNode **forward; // 指向各层下一个节点的指针数组
} SkipListNode;

// 跳表结构
typedef struct SkipList {
    int level;                    // 当前最大层数
    SkipListNode *header;         // 头节点
} SkipList;

// 创建新节点
SkipListNode* createNode(int key, int value, int level) {
    SkipListNode* node = (SkipListNode*)malloc(sizeof(SkipListNode));
    node->key = key;
    node->value = value;
    node->forward = (SkipListNode**)malloc(sizeof(SkipListNode*) * (level + 1));
  
    // 初始化指针数组
    for (int i = 0; i <= level; i++) {
        node->forward[i] = NULL;
    }
  
    return node;
}

// 创建跳表
SkipList* createSkipList() {
    SkipList* list = (SkipList*)malloc(sizeof(SkipList));
    list->level = 0;
  
    // 创建头节点，头节点的key设为最小值,将头节点的指针数组长度设置为最高层大小。
    list->header = createNode(-1, -1, MAX_LEVEL);
  
    return list;
}

// 生成随机层数，通过随机层数将数据随机分散在不同层中
int randomLevel() {
    int level = 0;
    while (((double)rand() / RAND_MAX) < PROBABILITY && level < MAX_LEVEL) {
        level++;
    }
    return level;
}

// 查找操作
SkipListNode* search(SkipList* list, int key) {
    SkipListNode* current = list->header;
  
    /*
    核心查询算法，比较当前层的下一个节点的key与目标key大小。如果满足要求，继续
    查询下一个节点，直到查询到forward的key大于等于目标key 结束本轮遍历
    下降到下一层，继续查询
    最终获取的是最接近目标key的节点
    即使在高层次查询到目标key，依然需要遍历到最底层
    */
    for (int i = list->level; i >= 0; i--) {
        // 在当前层向前移动，直到找到大于等于目标key的节点
        while (current->forward[i] != NULL && current->forward[i]->key < key) {
            current = current->forward[i];
        }
    }
  
    // 此时到达最底层，获取目标节点
    current = current->forward[0];
  
    // 检查是否找到目标节点
    if (current != NULL && current->key == key) {
        return current;
    }
  
    return NULL; // 未找到
}

// 插入操作
void insert(SkipList* list, int key, int value) {
    SkipListNode* update[MAX_LEVEL + 1]; // 记录每层需要更新的节点
    SkipListNode* current = list->header;
  
    // 查找插入位置，记录每层的前驱节点
    for (int i = list->level; i >= 0; i--) {
        while (current->forward[i] != NULL && current->forward[i]->key < key) {
            current = current->forward[i];
        }
        update[i] = current;
    }
  
    // 检查是否已存在相同key的节点
    current = current->forward[0];
    if (current != NULL && current->key == key) {
        // 更新已存在节点的值
        current->value = value;
        return;
    }
  
    // 生成新节点的层数
    int newLevel = randomLevel();
  
    // 如果新层数大于当前最大层数，需要更新header的指针
    if (newLevel > list->level) {
        for (int i = list->level + 1; i <= newLevel; i++) {
            update[i] = list->header;
        }
        list->level = newLevel;
    }
  
    // 创建新节点
    SkipListNode* newNode = createNode(key, value, newLevel);
  
    // 在各层插入新节点
    for (int i = 0; i <= newLevel; i++) {
        newNode->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = newNode;
    }
}

// 删除操作
int delete(SkipList* list, int key) {
    SkipListNode* update[MAX_LEVEL + 1];
    SkipListNode* current = list->header;
  
    // 查找要删除的节点，记录每层的前驱节点
    for (int i = list->level; i >= 0; i--) {
        while (current->forward[i] != NULL && current->forward[i]->key < key) {
            current = current->forward[i];
        }
        update[i] = current;
    }
  
    current = current->forward[0];
  
    // 检查节点是否存在
    if (current != NULL && current->key == key) {
        // 从各层删除该节点
        for (int i = 0; i <= list->level; i++) {
            if (update[i]->forward[i] != current) {
                break;
            }
            update[i]->forward[i] = current->forward[i];
        }
      
        // 释放节点内存
        free(current->forward);
        free(current);
      
        // 更新跳表的最大层数
        while (list->level > 0 && list->header->forward[list->level] == NULL) {
            list->level--;
        }
      
        return 1; // 删除成功
    }
  
    return 0; // 节点不存在
}

// 打印跳表
void printSkipList(SkipList* list) {
    printf("\\n=== Skip List Structure ===\\n");
  
    for (int i = list->level; i >= 0; i--) {
        printf("Level %d: ", i);
        SkipListNode* current = list->header->forward[i];
      
        while (current != NULL) {
            printf("[%d:%d] -> ", current->key, current->value);
            current = current->forward[i];
        }
        printf("NULL\\n");
    }
    printf("===========================\\n");
}

// 遍历跳表（只遍历最底层）
void traverse(SkipList* list) {
    printf("Traversal: ");
    SkipListNode* current = list->header->forward[0];
  
    while (current != NULL) {
        printf("[%d:%d] ", current->key, current->value);
        current = current->forward[0];
    }
    printf("\\n");
}

// 获取跳表大小
int size(SkipList* list) {
    int count = 0;
    SkipListNode* current = list->header->forward[0];
  
    while (current != NULL) {
        count++;
        current = current->forward[0];
    }
  
    return count;
}

// 释放跳表内存
void freeSkipList(SkipList* list) {
    SkipListNode* current = list->header;
    SkipListNode* next;
  
    while (current != NULL) {
        next = current->forward[0];
        free(current->forward);
        free(current);
        current = next;
    }
  
    free(list);
}

压缩链表

压缩链表的实现原理是通过预申请内存，在每个元素中添加头部信息,描述每个元素与上个元素和下个元素的偏移关系并记录尾部偏移，便于双向快速查找

1
<zlbytes><zltail><zllen><entry1><entry2>...<entryN><zlend>
  • zlbytes : 整个ziplist的字节数
  • zltail : 尾节点的偏移量（支持快速访问尾部）
  • zllen : 节点数量
  • entries : 紧凑存储的节点数据
  • zlend : 结束标记(0xFF)

压缩链表的实现较为复杂，这里只讨论其压缩结构设计。

Hash实现

hash算法被广泛用于对数据/字符的统一性整理，通过hash算法计算得到的数据特征可以将 字符数据变得”有序“。

Java中的HashMap实现

java中实现的hashmap 提供了元素统计，自动扩容，通过链表/红黑树解决hash碰撞等方案。

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
public class HashMap<K,V> extends AbstractMap<K,V> 
        implements Map<K,V>, Cloneable, Serializable {

    // 默认初始容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 链表转红黑树的阈值
    static final int TREEIFY_THRESHOLD = 8;
    // 红黑树退化为链表的阈值
    static final int UNTREEIFY_THRESHOLD = 6;

    // 存放元素的数组，每个桶要么是链表，要么是红黑树
    transient Node<K,V>[] table;

    // 元素个数
    transient int size;

    // 阈值 (capacity * load factor)
    int threshold;

    // 负载因子
    final float loadFactor;
}

其定义的entry中 定义了以下属性

hash ： hash值

key : 存储hash的键

V： 存储的目标值

Node<K,V> ： hashmap存储的下一个Node元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;      // 哈希值
    final K key;
    V value;
    Node<K,V> next;      // 下一个节点（链表）

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

hash计算

1
2
3
4
5
6
// 高位和低位混合，减少碰撞
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

put方法

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
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;

    // 1. 如果 table 为空，初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // 2. 定位桶下标 (n-1 & hash)
    if ((p = tab[i = (n - 1) & hash]) == null) {
        // 桶为空，直接放入
        tab[i] = newNode(hash, key, value, null);
    }
    else {
        Node<K,V> e; K k;

        // 3. 桶里已有节点，判断是否是同一个 key
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 4. 如果是树节点，调用红黑树插入逻辑
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 5. 链表插入：遍历链表
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    // 到达链表尾部，插入新节点
                    p.next = newNode(hash, key, value, null);
                    // 如果链表长度 >= 8，转为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, i);
                    break;
                }
                if (e.hash == hash && 
                   ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }

        // 如果找到已有 key，替换 value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            return oldValue;
        }
    }

    ++size;
    if (size > threshold)
        resize();
    return null;
}

get 方法

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
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 检查第一个节点
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;

        // 如果是链表/树，继续查找
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                   ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

resize 自动扩容

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
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int newCap = (oldCap == 0) ? DEFAULT_INITIAL_CAPACITY : oldCap << 1;
    threshold = (int)(newCap * loadFactor);

    @SuppressWarnings("unchecked")
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;

    // 重新分配节点
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else {
                    // 链表重新分配
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    do {
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null) loHead = e;
                            else loTail.next = e;
                            loTail = e;
                        } else {
                            if (hiTail == null) hiHead = e;
                            else hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = e.next) != null);
                    if (loTail != null) loTail.next = null;
                    if (hiTail != null) hiTail.next = null;
                    newTab[j] = loHead;
                    newTab[j + oldCap] = hiHead;
                }
            }
        }
    }
    return newTab;
}

受限线性表

栈

通常栈的实现包括以下方法

push : 将一个数据压入栈

pop : 将一个数据弹出栈

peek : 检查栈顶数据（不弹出）

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdlib.h>
#include "list.h"

typedef List Stack;

# define stack_init list_init
# define stack_destroy list_destroy

int stack_push(Stack *stack, const void *data);
int stack_pop(Stack *stack, void **data);
# define stack_peek(stack)((stack)->head == NULL ? NULL : (stack)->head->data)
# define stack_size list_size

队列

队列的实现包括以下方法

queue_enqueue : 进队列，将数据加入到队列中

queue_dequeue : 出队列，将数据从队列中取出

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdlib.h>
#include "list.h"

typedef List Queue;

#define queue_init list_init
#define queue_destroy list_destroy

int queue_enqueue(Queue *queue, const void *data);
int queue_dequeue(Queue *queue, void **data);

#define queue_peek(queue) ((queue)->head == NULL ? NULL : (queue)->head->data)
#define queue_size list_size
数据结构
#数据结构
数据结构 表结构实现
http://gadoid.io/2025/09/11/数据结构-表结构实现/
作者
Codfish
发布于
2025年9月11日
许可协议