您的位置: 首页  >  IT文章  >  C语言实现通用链表初步(四)----双向链表

C语言实现通用链表初步(四)----双向链表

分类: IT文章 • 2023-11-23 17:14:55

在前面的文章中，我们讨论了如何实现通用类型的链表，方法是用void *类型的指针，指向数据。那么还有其他的方法吗（不考虑内核链表）？

答案是肯定的。用零长数组也可以实现。


struct node_info
{
	struct node_info *next;
	struct node_info *prev;
	char data[0];
};

这里的最后一个元素，是元素个数为0的数组。其不占用任何空间，甚至是一个指针的空间都不占！

注意：在标准C和C++中，长度为0的数组是被禁止使用的。不过在GNU C中，存在一个非常奇怪的用法，那就是长度为0的数组。

在一个结构体的最后 ，定义一个长度为0的数组，就可以使得这个结构体是可变长的。对于编译器来说，这个长度为0的数组并不占用空间，因为数组名本身不占空间，它只是一个偏移量， 数组名这个符号本身代 表了一个不可修改的地址常量 

先来看看整个代码的头文件吧

#pragma once
struct node_info
{
	struct node_info *next;
	struct node_info *prev;
	char data[0];
};


struct student
{
	char name[20];
	unsigned char age;

};//for test

//有头双向循环链表
struct dlist_info
{
	struct node_info *head;
	void (*add_head)(struct dlist_info *info,
			const void *data, size_t size);
	void (*add_tail)(struct dlist_info *info,
			const void *data, size_t size);
	void (*del)(struct node_info *node);
	struct node_info* (*find)(struct dlist_info *info,
				int (*compare)(void *dest_data, void *key_data), void *key_data);
	void (*for_each_safe)(struct dlist_info *info,void (*todo)(struct node_info *));
		

};

int dlist_init(struct dlist_info *info);
void dlist_destroy(struct dlist_info *info);

#define node_init(node) 
	do
	{
		(node)->next = (node);
		(node)->prev = (node);
	}while(0)

#define   dlist_is_empty(info)	
		((info)->head->next == (info)->head)
接下来我们实现一些方法

1.头插

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "dlist.h"

/* 有头循环双链表*/

static void dlist_add_head(struct dlist_info *info,
		const void *my_data, size_t size)
{
	assert(info != NULL && my_data != NULL);
	
	if (size == 0) {
		return ;
	}
	
	struct node_info *new_node = (struct node_info *)malloc(sizeof(struct node_info) + size);
	
	if (new_node == NULL) {
		fprintf(stderr, "out of memory
");
		return ;
	} 
	//数据域，内存拷贝
	memmove(new_node->data, my_data, size);
	
	//指针域修改
	new_node->next = info->head->next;
	new_node->prev = info->head;

	info->head->next = new_node;
	new_node->next->prev = new_node;
}
size 表示数据域占用了多少个字节。memmove(new_node->data, my_data, size); 这句话把用户的数据拷贝到了结构体的最后。关于指针域的修改，是不是有点绕呢？没有关系，画图就明白了。


2.尾插

static void dlist_add_tail(struct dlist_info *info,
		const void *my_data, size_t size)
{

	assert(info != NULL && my_data != NULL);
	
	if (size == 0) {
		return ;
	}
	
	struct node_info *new_node = (struct node_info *)malloc(sizeof(struct node_info) + size);
	
	if (new_node == NULL) {
		fprintf(stderr, "out of memory
");
		return ;
	} 
	//数据域，内存拷贝
	memmove(new_node->data, my_data, size);
	
	//指针域修改
	new_node->next = info->head;
	new_node->prev = info->head->prev;

	info->head->prev->next = new_node;
	info->head->prev = new_node;
	
}


3.删除

static void dlist_del(struct node_info *node)
{
	assert(node != NULL);

	node->next->prev = node->prev;
	node->prev->next = node->next;

	node_init(node);	
	free(node);
}
因为申请空间的时候是带着size一起申请的，所以这里的释放就全部释放了，不存在内存泄漏。


4.查找

static struct node_info *dlist_find(struct dlist_info *info,
				int (*key)(void *dest_data, void *key_data), void *key_data)
{
	assert(info != NULL && key != NULL);

	if (dlist_is_empty(info)) {
		fprintf(stderr, "dlist is empty
");
		return NULL;
	}

	struct node_info *cur = NULL;
	
	for (cur = info->head->next; cur != info->head; 
				cur = cur->next) {
		if (key(cur->data, key_data) != 0) {
			return cur;
		}
	}
	return NULL;
}
回调函数需要用户自己实现，不用多说。

5.安全遍历

static void dlist_for_each_safe(struct dlist_info *info,
		void (*todo)(struct node_info *))
{
	assert(info != NULL && todo != NULL);

	struct node_info *cur = NULL;
	struct node_info *Next = NULL;
	for (cur = info->head->next; cur != info->head;
			cur = Next) {
		Next = cur->next;
		todo(cur);
	}
}

6.构造和析构

int dlist_init(struct dlist_info *info)
{
	info->head = (struct node_info *)malloc(sizeof(struct node_info));
	
	if (info->head == NULL) {
		fprintf(stderr, "Error:Out of memory
");
		return -1;
	}
	
	/*头节点空间的初始化*/
	node_init(info->head);

	/*函数指针的挂接*/
	info->add_head = dlist_add_head;
	info->add_tail = dlist_add_tail;
	info->del = dlist_del;
	info->find = dlist_find;
	info->for_each_safe = dlist_for_each_safe;
	return 0;
}

void dlist_destroy(struct dlist_info *info)
{
	// 依次删除，直到为空
	while (!dlist_is_empty(info)) {
		dlist_del(info->head->next);
	}	

	free(info->head);
}

接下来是单元测试。

测试一下头插和尾插吧。



运行结果如图






Running suite(s): two_way_list_with_head



Name:     WangGuozhen  Age:48



Name:        LiuDehua  Age:53



Name:    ZhangGuorong  Age:47



Name:       LiuXuewei  Age:28



Name:          ChenYu  Age:27



Name:       SunYazhou  Age:21



Name:         LiuMing  Age:19



Name:        WangDong  Age:18



===========



Name:        WangDong  Age:18



Name:         LiuMing  Age:19



Name:       SunYazhou  Age:21



Name:          ChenYu  Age:27



Name:       LiuXuewei  Age:28



Name:    ZhangGuorong  Age:47



Name:        LiuDehua  Age:53



Name:     WangGuozhen  Age:48



===========




测试一下遍历，在遍历的过程中，我们把节点给删除了。这可以体现出安全遍历的好处。



START_TEST(my_dlist_3)//遍历删除
{
	struct student students[8] = {{"WangDong",18},{"LiuMing",19},{"SunYazhou",21},{"ChenYu",27},{"LiuXuewei",28},
	{"ZhangGuorong",47},{"LiuDehua",53},{"WangGuozhen",48}};
	struct dlist_info list;
	dlist_init(&list);
	int i = 0;
	for(;i<sizeof(students)/sizeof(students[0]);++i)
		list.add_tail(&list,students+i,sizeof(students[0]));
	list.for_each_safe(&list,list.del);
	
	list.for_each_safe(&list,print_student);
	printf("===========
");
	dlist_destroy(&list);

}
END_TEST



运行结果是：





===========




果然没有节点了。




查找并删除。




START_TEST(my_dlist_4)//查找并删除
{
	struct student students[8] = {{"WangDong",18},{"LiuMing",19},{"SunYazhou",21},{"ChenYu",27},{"LiuXuewei",28},
	{"ZhangGuorong",47},{"LiuDehua",53},{"WangGuozhen",48}};
	struct dlist_info list;
	dlist_init(&list);
	int i = 0;
	for(;i<sizeof(students)/sizeof(students[0]);++i)
		list.add_tail(&list,students+i,sizeof(students[0]));

	list.del(list.find(&list,compare_student,"ChenYu"));
	
	
	list.for_each_safe(&list,print_student);
	printf("===========
");

	dlist_destroy(&list);

}
END_TEST





Name:        WangDong  Age:18



Name:         LiuMing  Age:19



Name:       SunYazhou  Age:21



Name:       LiuXuewei  Age:28



Name:    ZhangGuorong  Age:47



Name:        LiuDehua  Age:53



Name:     WangGuozhen  Age:48



===========




（完）

相关推荐