第二种链表的实现方式利用了 C99 中可伸缩数组成员这个特性,该特性使得我们在进行链表内存管理时,减少内存的申请和释次数。
第一种实现方式,我们在创建结点时如下图所示:
结点内存需要 malloc 一次,数据占用的内存也需要 malloc 一次。那么,当该结点销毁时,就需要 free 两次才能将结点彻底删除。利用 c99 的课伸缩数组成员特性,我们就可以如下图的方式来创建结点:
我们可以将结点内存和数据内存只通过一次 malloc 完成申请,销毁结点时也只需要 free 一次。
下面为头文件代码,注意使用可伸缩数组成员时,该成员一个 struct 中只能有一个,并且只能作为 struct 的最有一个成员,另外,包含可伸缩数组成员的 struct 也只能作为其他 struct 的最后一个成员。
#pragma once
struct link_node
{
// 结点指针
struct link_node* next;
// 数据指针
char data[];
};
struct __linklist
{
struct link_node* rear;
int ele_size;
int length;
struct link_node header;
};
typedef void* linklist;
#ifdef __cpluplus
extern "C" {
#endif
// 初始化链表
linklist init_linklist(int);
// 添加元素
void push_linklist(linklist*, void*);
// 删除元素
void remove_linklist(linklist*, void*, int(*)(void*, void*));
// 遍历元素
void foreach_linklist(linklist*, void(*)(void*));
// 销毁链表
void destroy_linklist(linklist*);
// 删除结点
static void free_node(struct link_node* node);
#ifdef __cpluplus
}
#endif
函数实现代码:
#include "link_list2.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
// 初始化链表
linklist init_linklist(int ele_size)
{
struct __linklist* list = (struct __linklist*)malloc(sizeof(struct __linklist));
if (NULL == list)
{
return NULL;
}
memset(list, 0, sizeof(struct __linklist));
list->ele_size = ele_size;
list->rear = &list->header;
return list;
}
// 添加元素
void push_linklist(linklist* list, void* data)
{
if (NULL == list || NULL == data)
{
return;
}
struct __linklist* my_list = (struct __linklist*)list;
// 创建新的元素结点
struct link_node* new_node = (struct link_node*)malloc(sizeof(struct link_node) + my_list->ele_size);
if (NULL == new_node)
{
return;
}
new_node->next = NULL;
memcpy(new_node->data, data, my_list->ele_size);
new_node->next = NULL;
// 新的结点添加到链表中
my_list->rear->next = new_node;
my_list->rear = new_node;
++my_list->length;
}
// 删除元素
void remove_linklist(linklist* list, void* data, int(*compare)(void*, void*))
{
if (NULL == list || NULL == data || NULL == compare)
{
return;
}
struct __linklist* my_list = (struct __linklist*)list;
struct link_node* p_prev = &my_list->header;
struct link_node* p_current = p_prev->next;
struct link_node* p_next = NULL;
// 找到要删除的结点
while (p_current != NULL)
{
if (0 == compare(p_current->data, data))
{
p_next = p_current->next;
break;
}
p_prev = p_current;
p_current = p_current->next;
}
// 删除结点
if (NULL == p_current)
{
return;
}
free_node(p_current);
// 重新建立结点关系
p_prev->next = p_next;
--my_list->length;
}
// 遍历元素
void foreach_linklist(linklist* list, void(*print)(void*))
{
if (NULL == list || NULL == print)
{
return;
}
struct __linklist* my_list = (struct __linklist*)list;
struct link_node* p_current = my_list->header.next;
while (p_current != NULL)
{
print(p_current->data);
p_current = p_current->next;
}
printf("------------------------\n");
}
// 销毁链表
void destroy_linklist(linklist* list)
{
if (NULL == list)
{
return;
}
struct __linklist* my_list = (struct __linklist*)list;
struct link_node* p_current = my_list->header.next;
struct link_node* p_next = NULL;
// 释放结点内存
while (p_current != NULL)
{
// 缓存下一个结点
p_next = p_current->next;
// 删除当前结点
free_node(p_current);
p_current = p_next;
}
free(list);
list = NULL;
}
static void free_node(struct link_node* node)
{
if (NULL == node)
{
return;
}
free(node);
}