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

﹏ヽ暗。殇╰゛Y 2022-08-27 07:52 127阅读 0赞

在前面的文章中，我们讨论了如何实现通用类型的链表，方法是用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\n");
    		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\n");
    		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\n");
    		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\n");
    		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);
    }

接下来是单元测试。

测试一下头插和尾插吧。

#include "uni_test.h"
    
    #include "dlist.h"
    
    
    #include <stdio.h>
    
    
    
    
    void setup (void)
    {
    	
    // will excute in every case 	
    }
    
    void teardown (void)
    {
      
    }
    
    void print_student(struct node_info *node)
    {
    	struct student *p = (struct student *)(node->data);
    	printf("Name: %15s  Age:%d\n",p->name,p->age);
    	
    }
    
    
    
    int compare_student(void *dest,void *src)
    {
    	struct student *p1 = dest;
    	struct student *p2 = src;
    	if(strcmp(p1->name,p2->name)==0)
    		return 1;
    	else
    		return 0;
    }
    
    START_TEST(my_dlist_1)
    {
    	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_head(&list,students+i,sizeof(students[0]));
    	list.for_each_safe(&list,print_student);
    	printf("===========\n");
    	dlist_destroy(&list);
    
    }
    END_TEST
    
    START_TEST(my_dlist_2)
    {
    	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,print_student);
    	printf("===========\n");
    	dlist_destroy(&list);
    
    	
    }
    END_TEST

运行结果如图

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("===========\n");
    	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("===========\n");
    
    	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

===========

（完）