C语言实现通用链表初步(一)

心已赠人 2022-08-27 03:21 212阅读 0赞

## 注意：本文讨论的是无头单向非循环链表。    ##

假设不采用Linux内核链表的思路，怎样用C语言实现通用链表呢？

一种常用的做法是：

typedef int element\_t;

struct node\_info

element\_t data;

struct node\_info \*next;

\};

其实这样的链表算不上通用，因为无法同时使用不同的数据类型。参考网友的思路，以上可以改为下面的定义：

//无头非循环单向链表
    struct node_info {
    	void *data;
    	struct node_info *next;
    };

先看看头文件：

#pragma once
    
    
    //无头非循环单向链表
    struct node_info {
    	void *data;
    	struct node_info *next;
    };
    
    
    
    struct student
    {
    	char name[20];
    	unsigned char age;
    
    };//for test
    
    struct  slist_info {
    	struct node_info *first; //指向第一个节点
    	
    	void (*insert_head)(void *one_data, 
    			struct slist_info *info);//头插
    	
    	int (*del)(struct node_info *node, 
    			struct slist_info *info);//删除节点
    
    	struct node_info* (*find)(struct slist_info *info,
    					int(*compare)(void *dest,void *key),void *key);
    	//这里的compare是回调函数，由用户提供
    
    	void (*for_each)(const struct slist_info *info,
    			void (*todo)(void *one_data));//遍历，todo是回调函数
    
    	void (*for_each_safe)(const struct slist_info *info,
    			void (*todo)(void *one_data));//安全遍历（觉得在这里这个方法意义不大）
    
    	void (*invert)(struct slist_info *info);//反转链表
    
    	int (*is_dead_loop)(struct slist_info *info);//判断是否有死环，是返回1，不是返回0
    };
    
    #define   slist_is_empty(info)  ((info)->first == NULL) //链表是否为空
    
    //构造和析构
    void  slist_init(struct  slist_info *info);
    void  slist_destroy(struct slist_info *info);

与这个链表相关的操作如下。

1.插入元素（头插法）

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <assert.h>
    #include "slist.h"
    
    /*无头非循环单链表*/
    static void slist_insert_head(void *one_data, 
                            struct slist_info *info)
    {//头插法
    	assert(one_data != NULL && info != NULL);
    	
    	
    	struct node_info *node = 
    		(struct node_info *)malloc(sizeof(struct node_info));//分配内存
    	assert(node!=NULL);
    	
    	node->data = one_data;//注意，这里只是简单地把指针指向用户的数据，并没有把用户数据复制过来
    	
    	if (slist_is_empty(info)) {//1.空链表
    		info->first = node;
    		node->next = NULL;
    	}else { //2. 非空
    		node->next = info->first;
    		info->first = node;
    	}
    }

2.遍历

static void slist_for_each(const struct slist_info *info,
           							void (*todo)(void *one_data))
    {
    	assert(info != NULL && todo != NULL);
    	struct node_info *cur = NULL;
    
    	for (cur = info->first; cur != NULL; cur = cur->next) {
    		todo(cur->data);
    	}
    }
    
    static void slist_for_each_safe(const struct slist_info *info,
           							void (*todo)(void *one_data))
    {
    	assert(info != NULL && todo != NULL);
    	struct node_info *cur = NULL;
    	struct node_info *Next = NULL;
    	for (cur = info->first; cur != NULL; cur = Next) {
    		Next = cur->next;//Next保存了下一个节点，如果这个节点被删除了，那么下一个节点还可以找到
    		todo(cur->data);
    	}
    }

3.反转（面试的时候，有可能会问到，直接背过好了！）

static void  slist_invert(struct slist_info *info)
    {
    	assert(info != NULL);
    
    	struct node_info *Cur = NULL;
    	struct node_info *Prev = NULL;
    	struct node_info *Next = NULL;
    	//1.移动Next 2.反向 3.移动Prev 4.移动Cur
    	for (Cur = info->first; Cur  != NULL; Cur = Next) {
    		Next = Cur->next;
    		Cur->next = Prev;
    		Prev = Cur;
    	}
    	//修改头指针，指向首节点
    	info->first = Prev;	
    }

4.查找

struct node_info *slist_find(struct slist_info *info,int(*compare)(void *dest,void *key),void *key)
    {
    	assert(info != NULL && compare != NULL);
    	struct node_info *cur = NULL;
    
    	for (cur = info->first; cur != NULL; cur = cur->next) {
    		if(compare(cur->data,key)==1)//回调函数，把链表中的每一个数据和用户传入的关键字做比较，符合条件返回1
    			return cur;//返回节点的地址给用户
    	}
    	return NULL;//没有找到返回空指针
    }

注意，这里的第三个参数（关键字）也是用户传进来的。

5.构造和析构

void slist_init(struct slist_info *info)
    {
    	//空链表， 第一个节点为NULL
    	info->first = NULL;
    
    	info->insert_head = slist_insert_head;
    	info->del = slist_del;
    	info->find = slist_find;
    	info->invert = slist_invert;
    	info->is_dead_loop = slist_is_dead_loop;
    	info->for_each = slist_for_each;
    	info->for_each_safe = slist_for_each_safe;
    }
    
    void slist_destroy(struct slist_info *info)
    {
    	if(!slist_is_empty(info))
    	{
    		struct node_info *cur = NULL;
    		struct node_info *Next = NULL;
    		for (cur = info->first; cur != NULL; cur = Next) 
    		{
    			Next = cur->next;//Next保存了下一个节点，如果这个节点被删除了，那么下一个节点还可以找到
    			free(cur);//释放每个节点占用的内存
    		}
    	}
    	
    }

细心的读者会发现，好像有的函数没有实现啊。下一篇博文我们再讨论！