进阶链表（C实现）
大家好，又见面了，今天又要跟大家来个链表，链表实现的方式有很多，本文将使用线性表的方式实现链表
链表是什么
关于链表的定义，本文不再详细赘述，详情可查看两年前的文章-->https://mp.weixin.qq.com/s/yj3RBr2nSAyQwFV8JHoOKA
线性链表定义
首先定义链表
1 #define _COMMON_VARIABLES \
2 void *free_pointer; \
3 u16_t data_numbers; \
4 u16_t data_free_numbers; \
5 u32_t data_size
6
7 typedef struct {
8 _COMMON_VARIABLES;
9 char datas[0];
10 }commonn_list_t;
11
12 #define DEFINE_LIST_TYPE(list_type_name, data_numbers, data_size) \
13 typedef struct { \
14 _COMMON_VARIABLES; \
15 char datas[data_numbers * data_size]; \
16 }list_type_name
为什么要使用固定大小的链表，对于底层来说，空间性能等方面都是需要考虑的问题，在设计结构的同时必须考虑这些问题，对于不连续的内存来说，影响性能。
初始化
1 void list_init(void* list, u16_t data_numbers ,u32_t data_size){
2 commonn_list_t *comm_list = (commonn_list_t*)list;
3 u64_t* p;
4 u32_t i;
5 //printf("list_init size %d\n", sizeof(p)); //because PC pointer size is 8 bytes, which is different from the arm platform
6 comm_list->data_numbers = data_numbers;
7 comm_list->data_size = data_size;
8 p = (u64_t*)&comm_list->datas[0];
9 comm_list->free_pointer = &comm_list->datas[0];
10
11 for( i = 1; i < data_numbers; ++i){
12 *p = (u64_t)&comm_list->datas[i * data_size];
13 p = (u64_t*)&comm_list->datas[i * data_size];
14 }
15 comm_list->data_free_numbers = data_numbers;
16 *p = 0;
17 }
获取链表中的空间
1 void* list_get(void* list){
2 commonn_list_t* comm_list = (commonn_list_t*)list;
3 void* p = comm_list->free_pointer;
4 if(p){
5 comm_list->free_pointer = (void*)*((u64_t*)p);
6 --comm_list->data_free_numbers;
7 }
8 return p;
9 }
归还链表中的空间
1 void list_put(void* list, void* data){
2 commonn_list_t* comm_list = (commonn_list_t*)list;
3 *((u64_t*)data) = (u64_t)comm_list->free_pointer;
4 comm_list->free_pointer = data;
5 ++comm_list->data_free_numbers;
6 }
7 void list_put_use_index(void* list, u32_t index){
8 list_put(list, list_from_index_get_data(list, index));
9 }
结
累了，想划划水，写完代码之后就索然无味，本文链表的实现的本质是，当前链表保存下一个链表的地址，同时有一个头指针一直指向最开始的指针，仔细阅读init函数就可以明白本文链表的本质。
代码经过简单的测试，有问题请指正。
附全部代码
Makefile
1 CC = gcc
2 CFLAGS = -I.
3 DEPS = list.h
4 OBJ = main.o list.o
5
6 %.o: %.c $(DEPS)
7 $(CC) -c -o $@ $< $(CFLAGS)
8
9 list: $(OBJ)
10 $(CC) -o $@ $^ $(CFLAGS)
11
12 .PHONY: clean
13
14 clean:
15 rm -f list *.o
list.h
1 /****************************************************************
2 *@file : list.h
3 *@description:
4 *@time : 2023/08/24 18:49:04
5 *@author : Nick Xia
6 *@blog : https://aeneag.xyz
7 *****************************************************************/
8 #ifndef _LIST_H
9 #define _LIST_H
10
11 typedef unsigned char u8_t;
12 typedef unsigned short u16_t;
13 typedef unsigned int u32_t;
14 typedef unsigned long long u64_t;
15
16 #define _COMMON_VARIABLES \
17 void *free_pointer; \
18 u16_t data_numbers; \
19 u16_t data_free_numbers; \
20 u32_t data_size
21
22 typedef struct {
23 _COMMON_VARIABLES;
24 char datas[0];
25 }commonn_list_t;
26
27 #define DEFINE_LIST_TYPE(list_type_name, data_numbers, data_size) \
28 typedef struct { \
29 _COMMON_VARIABLES; \
30 char datas[data_numbers * data_size]; \
31 }list_type_name
32
33 void list_init(void* list, u16_t data_numbers ,u32_t data_size);
34 u16_t list_get_data_index(void* list, void* data);
35 void* list_from_index_get_data(void* list, u32_t index);
36 void* list_get(void* list);
37 void list_put(void* list, void* data);
38 void list_put_use_index(void* list, u32_t index);
39 u32_t list_free_numbers(void* list);
40 u32_t list_data_numbers(void* list);
41 u32_t list_used_numbers(void* list);
42
43 #endif // I_LIST_H
44
list.c
1 /****************************************************************
2 *@file : list.c
3 *@description:
4 *@time : 2023/08/24 18:49:12
5 *@author : Nick Xia
6 *@blog : https://aeneag.xyz
7 *****************************************************************/
8 #include "list.h"
9 // #include <stdio.h>
10 void list_init(void* list, u16_t data_numbers ,u32_t data_size){
11 commonn_list_t *comm_list = (commonn_list_t*)list;
12 u64_t* p;
13 u32_t i;
14 //printf("list_init size %d\n", sizeof(p)); //because PC pointer size is 8 bytes, which is different from the arm platform
15 comm_list->data_numbers = data_numbers;
16 comm_list->data_size = data_size;
17 p = (u64_t*)&comm_list->datas[0];
18 comm_list->free_pointer = &comm_list->datas[0];
19
20 for( i = 1; i < data_numbers; ++i){
21 *p = (u64_t)&comm_list->datas[i * data_size];
22 p = (u64_t*)&comm_list->datas[i * data_size];
23 }
24 comm_list->data_free_numbers = data_numbers;
25 *p = 0;
26 }
27 u16_t list_get_data_index(void* list, void* data){
28 commonn_list_t* comm_list = (commonn_list_t*)list;
29 return (u16_t)((char*)data - (char*)comm_list->datas) / comm_list->data_size;
30 }
31 void* list_from_index_get_data(void* list, u32_t index){
32 commonn_list_t* comm_list = (commonn_list_t*)list;
33 return comm_list->datas + index * comm_list->data_size;
34 }
35 void* list_get(void* list){
36 commonn_list_t* comm_list = (commonn_list_t*)list;
37 void* p = comm_list->free_pointer;
38 if(p){
39 comm_list->free_pointer = (void*)*((u64_t*)p);
40 --comm_list->data_free_numbers;
41 }
42 return p;
43 }
44 void list_put(void* list, void* data){
45 commonn_list_t* comm_list = (commonn_list_t*)list;
46 *((u64_t*)data) = (u64_t)comm_list->free_pointer;
47 comm_list->free_pointer = data;
48 ++comm_list->data_free_numbers;
49 }
50 void list_put_use_index(void* list, u32_t index){
51 list_put(list, list_from_index_get_data(list, index));
52 }
53 u32_t list_free_numbers(void* list){
54 commonn_list_t* comm_list = (commonn_list_t*)list;
55 return (u32_t)comm_list->data_free_numbers;
56 }
57 u32_t list_data_numbers(void* list){
58 commonn_list_t* comm_list = (commonn_list_t*)list;
59 return (u32_t)comm_list->data_numbers;
60 }
61 u32_t list_used_numbers(void* list){
62 commonn_list_t* comm_list = (commonn_list_t*)list;
63 return (u32_t)(comm_list->data_numbers - comm_list->data_free_numbers);
64 }
main.c
1 /****************************************************************
2 *@file : main.c
3 *@description:
4 *@time : 2023/08/24 19:05:56
5 *@author : Nick Xia
6 *@blog : https://aeneag.xyz
7 *****************************************************************/
8 #include "list.h"
9 #include <stdio.h>
10
11 typedef struct l_data{
12 /* data */
13 u8_t data1;
14 u8_t data2;
15 u16_t data3;
16 u32_t data4;
17 u64_t data5;
18 }__attribute__((packed)) l_data_t;
19
20 #define MY_DATA_NUM 256
21 DEFINE_LIST_TYPE(my_list_t, MY_DATA_NUM, sizeof(l_data_t));
22 my_list_t my_list;
23
24 int main(int argc, char **argv){
25 list_init(&my_list, MY_DATA_NUM, sizeof(l_data_t));
26 printf("free_numbers: %d\n", list_free_numbers(&my_list));
27 printf("used_numbers: %d\n", list_used_numbers(&my_list));
28 l_data_t* my_= list_get(&my_list);
29
30 printf("\n");
31 printf("free_numbers: %d\n", list_free_numbers(&my_list));
32 printf("used numbers: %d\n", list_used_numbers(&my_list));
33 my_->data1 = 1;
34
35 l_data_t* my_1;
36 list_get(&my_list);
37
38 printf("\n");
39 printf("free numbers: %d\n", list_free_numbers(&my_list));
40 printf("used_numbers: %d\n", list_used_numbers(&my_list));
41 my_1->data2 = 2;
42 list_put_use_index(&my_list,list_get_data_index(&my_list, my_1));
43
44 printf("\n");
45 printf("free_numbers: %d\n", list_free_numbers(&my_list));
46 printf("used_numbers: %d\n", list_used_numbers(&my_list));
47 list_put(&my_list, my_);
48 printf("\n");
49 printf("free_numbers: %d\n", list_free_numbers(&my_list));
50 printf("used_numbers: %d\n", list_used_numbers(&my_list));
51 }
原文链接
吾心信其可行，
则移山填海之难，
终有成功之日！
——孙文
则移山填海之难，
终有成功之日！
——孙文
评论
0 评论
