C 实现链表的方式有多种,这篇文章我们将实现一种简单的单向链表。C 语言中由于没有模板技术,实现能够存储不同类型的数据就需要根据实际需求来设计链表。
一种方法是链表可以只存储用户数据的指针,另外一种则将用户数据拷贝到链表中。
如果链表只存储数据的指针,则用户数据的内存由用户自行管理。这是因为用户的数据可能分配在堆上,也可能在栈上。如果用户数据分配在堆上,则需要注意的是,如果用户不小心 delete 了数据,则链表内部存储的数据指针将会变成野指针(悬挂指针),这是一个非常危险的东东。如果用户数据分配到栈上,则要避免链表内部释放用户数据的行为。
当然,我们也可以存储数据本身,这一点实现也非常简单,只要在初始化链表时,告知链表数据类型大小,链表内部根据数据类型大小动态开辟空间,并将用户数据拷贝一份到链表节点中即可。这样,数据空间和链表空间就全部由链表内部管理,即使用户不小心删除原数据也不会影响链表。在这种情况下,对内存的申请和释放操作要额外注意,因为每个节点的创建将会包含 2 次的 malloc 操作,在销毁节点时,也要进行 2 次的 free 操作。
接下来,我们将实现第二种存储方式的链表,即:数据插入时,将用户数据拷贝一份到链表中。
- 链表头文件 {#title-0} ===================
在头文件中,我们链表本身需要的数据。主要包含结点的定义 struct link_node 和链表定义 struct __linklist. 以及链表的操作函数,主要包括:初始化函数、元素添加函数、元素删除函数、链表遍历函数、链表销毁函数,以及一个结点删除函数,该函数为静态函数,用于链表内部,不允许外部访问。
#pragma once
struct link_node
{
// 数据指针
void* data;
// 结点指针
struct link_node *next;
};
struct __linklist
{
// 头结点
struct link_node header;
// 尾指针
struct link_node *rear;
// 元素大小
int ele_size;
// 结点数量
int length;
};
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
- 链表实现文件 {#title-1} ====================
#include "link_list.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));
if (NULL == new_node)
{
return;
}
new_node->next = NULL;
new_node->data = malloc(my_list->ele_size);
if (NULL == new_node->data)
{
return;
}
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;
}
if (node->data != NULL)
{
free(node->data);
node->data = NULL;
}
free(node);
}
- 链表测试代码 {#title-2} ====================
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "link_list.h"
struct Person
{
char name[32];
int age;
};
void print_person(void *data)
{
struct Person* person = (struct Person *)data;
printf("Name: %s Age: %d\n", person->name, person->age);
}
int compare(void *data1, void *data2)
{
struct Person* person1 = (struct Person*)data1;
struct Person* person2 = (struct Person*)data2;
if (0 == strcmp(person1->name, person2->name) && person1->age == person2->age)
{
return 0;
}
return 1;
}
void test()
{
// 初始化链表
linklist *list = init_linklist(sizeof(struct Person));
// 初始化数据
struct Person p1 = { "张三", 18 };
struct Person p2 = { "李四", 20 };
struct Person p3 = { "王五", 19 };
// 数据入链表
push_linklist(list, &p1);
push_linklist(list, &p2);
push_linklist(list, &p3);
foreach_linklist(list, print_person);
// 删除元素
remove_linklist(list, &p3, compare);
foreach_linklist(list, print_person);
// 销毁链表
destroy_linklist(list);
}
int main()
{
test();
return 0;
}
程序执行结果: