进阶链表（C实现）

2023-08-24 / 2023-08-24 / C语言

进阶链表（C实现）

大家好，又见面了，今天又要跟大家来个链表，链表实现的方式有很多，本文将使用线性表的方式实现链表

链表是什么

关于链表的定义，本文不再详细赘述，详情可查看两年前的文章-->https://mp.weixin.qq.com/s/yj3RBr2nSAyQwFV8JHoOKA

线性链表定义

首先定义链表

 #define _COMMON_VARIABLES  \
     void *free_pointer;   \
     u16_t data_numbers;   \
     u16_t data_free_numbers; \
     u32_t data_size
 
 typedef struct {
     _COMMON_VARIABLES;
     char datas[0];
 }commonn_list_t;
 
 #define DEFINE_LIST_TYPE(list_type_name, data_numbers, data_size)  \
     typedef struct {                                               \
         _COMMON_VARIABLES;                                         \
         char datas[data_numbers * data_size];                      \
     }list_type_name

为什么要使用固定大小的链表，对于底层来说，空间性能等方面都是需要考虑的问题，在设计结构的同时必须考虑这些问题，对于不连续的内存来说，影响性能。

初始化

 void list_init(void* list, u16_t data_numbers ,u32_t data_size){
     commonn_list_t *comm_list = (commonn_list_t*)list;
     u64_t* p;
     u32_t i;
     //printf("list_init size %d\n", sizeof(p)); //because PC pointer size is 8 bytes, which is different from the arm platform
     comm_list->data_numbers = data_numbers;
     comm_list->data_size = data_size;
     p = (u64_t*)&comm_list->datas[0];
     comm_list->free_pointer = &comm_list->datas[0];
 
     for( i = 1; i < data_numbers; ++i){
         *p = (u64_t)&comm_list->datas[i * data_size];
         p = (u64_t*)&comm_list->datas[i * data_size];
     }
     comm_list->data_free_numbers = data_numbers;
     *p = 0;
 }

获取链表中的空间

 void* list_get(void* list){
     commonn_list_t* comm_list = (commonn_list_t*)list;
     void* p = comm_list->free_pointer;
     if(p){
         comm_list->free_pointer = (void*)*((u64_t*)p);
         --comm_list->data_free_numbers;
     }
     return p;
 }

归还链表中的空间

 void list_put(void* list, void* data){
     commonn_list_t* comm_list = (commonn_list_t*)list;
     *((u64_t*)data) = (u64_t)comm_list->free_pointer;
     comm_list->free_pointer = data;
     ++comm_list->data_free_numbers;
 }
 void list_put_use_index(void* list, u32_t index){
     list_put(list, list_from_index_get_data(list, index));
 }

结

累了，想划划水，写完代码之后就索然无味，本文链表的实现的本质是，当前链表保存下一个链表的地址，同时有一个头指针一直指向最开始的指针，仔细阅读init函数就可以明白本文链表的本质。

代码经过简单的测试，有问题请指正。

附全部代码

Makefile

 CC = gcc
 CFLAGS = -I.
 DEPS = list.h
 OBJ = main.o list.o 
 
 %.o: %.c $(DEPS)
 $(CC) -c -o $@ $< $(CFLAGS)
 
 list: $(OBJ)
 $(CC) -o $@ $^ $(CFLAGS)
 
 .PHONY: clean
 
 clean:
 rm -f list *.o

list.h

 /****************************************************************
   *@file       : list.h
   *@description: 
   *@time       : 2023/08/24 18:49:04
   *@author     : Nick Xia
   *@blog       : https://aeneag.xyz
 *****************************************************************/
 #ifndef _LIST_H
 #define _LIST_H
 
 typedef unsigned char u8_t;
 typedef unsigned short u16_t;
 typedef unsigned int u32_t;
 typedef unsigned long long u64_t;
 
 #define _COMMON_VARIABLES  \
     void *free_pointer;   \
     u16_t data_numbers;   \
     u16_t data_free_numbers; \
     u32_t data_size
 
 typedef struct {
     _COMMON_VARIABLES;
     char datas[0];
 }commonn_list_t;
 
 #define DEFINE_LIST_TYPE(list_type_name, data_numbers, data_size)  \
     typedef struct {                                               \
         _COMMON_VARIABLES;                                         \
         char datas[data_numbers * data_size];                      \
     }list_type_name
 
 void list_init(void* list, u16_t data_numbers ,u32_t data_size);
 u16_t list_get_data_index(void* list, void* data);
 void* list_from_index_get_data(void* list, u32_t index);
 void* list_get(void* list);
 void list_put(void* list, void* data);
 void list_put_use_index(void* list, u32_t index);
 u32_t list_free_numbers(void* list);
 u32_t list_data_numbers(void* list);
 u32_t list_used_numbers(void* list);
 
 #endif // I_LIST_H

list.c

 /****************************************************************
   *@file       : list.c
   *@description: 
   *@time       : 2023/08/24 18:49:12
   *@author     : Nick Xia
   *@blog       : https://aeneag.xyz
 *****************************************************************/
 #include "list.h"
 // #include <stdio.h>
 void list_init(void* list, u16_t data_numbers ,u32_t data_size){
     commonn_list_t *comm_list = (commonn_list_t*)list;
     u64_t* p;
     u32_t i;
     //printf("list_init size %d\n", sizeof(p)); //because PC pointer size is 8 bytes, which is different from the arm platform
     comm_list->data_numbers = data_numbers;
     comm_list->data_size = data_size;
     p = (u64_t*)&comm_list->datas[0];
     comm_list->free_pointer = &comm_list->datas[0];
 
     for( i = 1; i < data_numbers; ++i){
         *p = (u64_t)&comm_list->datas[i * data_size];
         p = (u64_t*)&comm_list->datas[i * data_size];
     }
     comm_list->data_free_numbers = data_numbers;
     *p = 0;
 }
 u16_t list_get_data_index(void* list, void* data){
     commonn_list_t* comm_list = (commonn_list_t*)list;
     return (u16_t)((char*)data - (char*)comm_list->datas) / comm_list->data_size;
 }
 void* list_from_index_get_data(void* list, u32_t index){
     commonn_list_t* comm_list = (commonn_list_t*)list;
     return comm_list->datas + index * comm_list->data_size;
 }
 void* list_get(void* list){
     commonn_list_t* comm_list = (commonn_list_t*)list;
     void* p = comm_list->free_pointer;
     if(p){
         comm_list->free_pointer = (void*)*((u64_t*)p);
         --comm_list->data_free_numbers;
     }
     return p;
 }
 void list_put(void* list, void* data){
     commonn_list_t* comm_list = (commonn_list_t*)list;
     *((u64_t*)data) = (u64_t)comm_list->free_pointer;
     comm_list->free_pointer = data;
     ++comm_list->data_free_numbers;
 }
 void list_put_use_index(void* list, u32_t index){
     list_put(list, list_from_index_get_data(list, index));
 }
 u32_t list_free_numbers(void* list){
     commonn_list_t* comm_list = (commonn_list_t*)list;
     return (u32_t)comm_list->data_free_numbers;
 }
 u32_t list_data_numbers(void* list){
     commonn_list_t* comm_list = (commonn_list_t*)list;
     return (u32_t)comm_list->data_numbers;
 }
 u32_t list_used_numbers(void* list){
     commonn_list_t* comm_list = (commonn_list_t*)list;
     return (u32_t)(comm_list->data_numbers - comm_list->data_free_numbers);
 }

main.c

 /****************************************************************
   *@file       : main.c
   *@description: 
   *@time       : 2023/08/24 19:05:56
   *@author     : Nick Xia
   *@blog       : https://aeneag.xyz
 *****************************************************************/
 #include "list.h"
 #include <stdio.h>
 
 typedef struct l_data{
     /* data */
     u8_t data1;
     u8_t data2;
     u16_t data3;
     u32_t data4;
     u64_t data5;
 }__attribute__((packed)) l_data_t;
 
 #define MY_DATA_NUM 256
 DEFINE_LIST_TYPE(my_list_t, MY_DATA_NUM, sizeof(l_data_t));
 my_list_t my_list;
 
 int main(int argc, char **argv){
     list_init(&my_list, MY_DATA_NUM, sizeof(l_data_t));
     printf("free_numbers: %d\n", list_free_numbers(&my_list));
     printf("used_numbers: %d\n", list_used_numbers(&my_list));
     l_data_t* my_= list_get(&my_list);
 
     printf("\n");
     printf("free_numbers: %d\n", list_free_numbers(&my_list));
     printf("used numbers: %d\n", list_used_numbers(&my_list));
     my_->data1 = 1;
 
     l_data_t* my_1;
     list_get(&my_list);
 
     printf("\n");
     printf("free numbers: %d\n", list_free_numbers(&my_list));
     printf("used_numbers: %d\n", list_used_numbers(&my_list));
     my_1->data2 = 2;
     list_put_use_index(&my_list,list_get_data_index(&my_list, my_1));
 
     printf("\n");
     printf("free_numbers: %d\n", list_free_numbers(&my_list));
     printf("used_numbers: %d\n", list_used_numbers(&my_list));
     list_put(&my_list, my_);
     printf("\n");
     printf("free_numbers: %d\n", list_free_numbers(&my_list));
     printf("used_numbers: %d\n", list_used_numbers(&my_list));
 }

原文链接

公众号'艾恩凝'

个人微信

吾心信其可行，
则移山填海之难，
终有成功之日！
——孙文

链表是什么
线性链表定义
初始化
获取链表中的空间
归还链表中的空间
结
附全部代码
Makefile
list.h
list.c
main.c
原文链接

0 评论