数据结构与算法：单链表（利用万能指针实现对任意类型数据进行操作）

水深无声 2022-05-31 05:49 158阅读 0赞

# 前言 #

**C语言的指针真的很强大，万能指针更强大，可以指向任意类型的数据**。在上篇博客** [数据结构与算法：单链表（超详细实现）][Link 1]**中用C语言实现了单链表的相关算法，**不过却有局限性 只能针对某一种数据类型**还是不够强大。**C语言中没有C++中的模板 那如何来实现 类似模板的效果呢？可以针对任意类型数据的单链表呢？在C语言中就有这么一种类型 可以指向任意数据类型的指针，它就是万能指针 void\* ，就是它 ，可以利用它实现 类似模板的效果！我们在链表中不维护数据，我们只维护数据的地址，那么我们的void\* 就可保存任意类型的地址**！

# 实现算法预览 #

## LinkList.h ##

#pragma once
    #ifndef __LINKLIST_H__
    #define __LINKLIST_H__
    
    typedef struct LinkNode LinkNode;
    struct LinkNode
    {
    	void* data;//维护用户提供的数据
    	LinkNode* next;
    };
    typedef struct LINKLIST
    {
    	LinkNode *pHeader;
    	int m_size;
    }LINKLIST;
    
    typedef void* LinkList;//对外提供void*防止用户看到不该看到的东西，避免用户乱修改
    
    //初始化单链表
    LinkList Init_LinkList();
    
    //根据位置插入元素
    //pos 位置范围为1 ~ list->size 更符合人类的叫法
    int InsertByIndex_LinkList(void* list, int pos, void* data);
    
    //插入元素根据元素值
    int InsertByValue_LinkList(void* list, void* search,void* data,int(*compareFunction)(void* data1, void* data2));
    
    //删除元素根据位置
    int RemoveByIndex_LinkList(void* list, int pos);
    
    //删除元素根据值
    int RemoveByValue_LinkList(void * list, void * data, int(*compareFunction)(void* data1, void* data2));
    
    //清空链表
    int Clear_LinkList(void* list);
    
    //销毁链表
    int Destroy_LinkList(void* list);
    
    //获取链表元素个数
    int Length_LinkList(void* list);
    
    //遍历链表
    int Foreach_LinkList(void* list, void(*foreachFunction)(void* data));
    
    //翻转链表
    int Reverse_LinkList(void* list);
    
    #endif // !__LINKLIST_H__

# 实现代码展示 #

## LinkList.c ##

#define _CRT_SECURE_NO_WARNINGS
    #include <stdlib.h>
    #include "LinkList.h"
    
    LinkList Init_LinkList()
    {
    	LINKLIST* list = (LINKLIST*)malloc(sizeof(LINKLIST));
    	list->pHeader = (LinkNode*)malloc(sizeof(LinkNode));
    	list->pHeader->data = NULL;
    	list->pHeader->next = NULL;
    
    	list->m_size = 0;
    	return list;
    }
    //根据位置插入元素
    //pos 位置范围为1 ~ list->size 
    int InsertByIndex_LinkList(void* list, int pos, void* data)
    {
    	LINKLIST* linkList = (LINKLIST*)list;
    	//非法情况
    	if (NULL == list || NULL == data)
    	{
    		return 0;
    	}
    	//位置非法 进行尾插
    	if (pos<1 || pos>=linkList->m_size + 1)
    	{
    		pos = linkList->m_size + 1;
    	}
    	LinkNode* pre = linkList->pHeader;
    	//找到 第pos位置前面一个元素
    	for (int i = 1; i < pos; i++)
    	{
    		pre = pre->next;
    	}
    	//创建结点
    	LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
    	newNode->data = data;
    	newNode->next = pre->next;
    	pre->next = newNode;
    	linkList->m_size++;
    	return 1;
    }
    int InsertByValue_LinkList(void* list, void* search,void* data, int(*compareFunction)(void* data1, void* data2))
    {
    	if (NULL == list || NULL == search || data == NULL || NULL == compareFunction)
    	{
    		return 0;
    	}
    	LINKLIST* linkList = (LINKLIST*)list;
    	LinkNode* pre = linkList->pHeader;
    	LinkNode* cur = linkList->pHeader->next;
    	LinkNode* insertPre = NULL;
    	for (int i = 0; i < linkList->m_size; i++)
    	{
    		if (compareFunction(cur->data, search))
    		{
    			insertPre = pre;
    			break;
    		}
    		pre = cur;
    		cur = cur->next;
    	}
    	//如果没有找到要插入的位置 将其插在尾结点
    	LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
    	newNode->data = data;
    	newNode->next = cur;
    	pre->next = newNode;
    	linkList->m_size++;
    	return 1;
    }
    int RemoveByIndex_LinkList(void * list, int pos)
    {
    	if (NULL == list)
    	{
    		return 0;
    	}
    	LINKLIST* linkList = (LINKLIST*)list;
    	//位置非法返回
    	if (pos > linkList->m_size || pos < 1)
    	{
    		return 0;
    	}
    	LinkNode* cur = linkList->pHeader;
    	//找到删除元素的前驱结点
    	for (int i = 1; i < pos; i++)
    	{
    		cur = cur->next;
    	}
    	//缓存待删除结点
    	LinkNode* del = cur->next;
    	//前驱结点指向删除结点后继结点
    	cur->next = del->next;
    	//删除结点
    	free(del);
    	linkList->m_size--;
    	return 1;
    }
    int RemoveByValue_LinkList(void * list, void * data,int (*compareFunction)(void* data1,void* data2))
    {
    	if (NULL == list || NULL == data || NULL == compareFunction)
    	{
    		return 0;
    	}
    	LINKLIST* linkList = (LINKLIST*)list;
    	LinkNode* pre = linkList->pHeader;
    	LinkNode* cur = linkList->pHeader->next;
    	LinkNode* delPre = NULL;
    	for (int i = 0; i < linkList->m_size; i++)
    	{
    		if (compareFunction(cur->data,data))
    		{
    			delPre = pre;
    			break;
    		}
    		pre = cur;
    		cur = cur->next;
    	}
    	if (NULL != delPre && NULL != cur)
    	{
    		//删除元素前驱结点指向删除元素的后继结点
    		delPre->next = cur->next;
    		//删除结点
    		free(cur);
    		cur = NULL;
    	}
    	linkList->m_size--;
    	return 1;
    }
    int Clear_LinkList(void * list)
    {
    	if (NULL == list)
    	{
    		return 0;
    	}
    	LINKLIST *linkList = (LINKLIST*)list;
    	LinkNode* cur = linkList->pHeader->next;
    	for (int i = 0; i < linkList->m_size; i++)
    	{
    		LinkNode* next = cur->next;
    		free(cur);
    		cur = next;
    	}
    	linkList->m_size = 0;
    	return 1;
    }
    int Destroy_LinkList(void * list)
    {
    	if (NULL == list)
    	{
    		return 0;
    	}
    	LINKLIST* linkList = (LINKLIST*)list;
    	Clear_LinkList(linkList);
    	free(linkList->pHeader);
    	linkList->pHeader = NULL;
    	return 1;
    }
    int Length_LinkList(void * list)
    {
    	if (NULL == list)
    	{
    		return -1;
    	}
    	LINKLIST* linkList = (LINKLIST*)list;
    	return linkList->m_size;
    }
    int Foreach_LinkList(void* list, void(*foreachFunction)(void* data))
    {
    	if (NULL == list || NULL == foreachFunction)
    	{
    		return 0;
    	}
    	LINKLIST* linkList = (LINKLIST*)list;
    	LinkNode* cur = linkList->pHeader->next;
    	for (int i = 0; i < linkList->m_size; i++)
    	{
    		foreachFunction(cur->data);
    		cur = cur->next;
    	}
    	return 1;
    }
    
    int Reverse_LinkList(void * list)
    {
    	if (NULL == list)
    	{
    		return 0;
    	}
    	LINKLIST* linkList = (LINKLIST*)list;
    	LinkNode* pre = NULL;
    	LinkNode* cur = linkList->pHeader->next;
    	LinkNode* next = NULL;
    	while (cur!=NULL)
    	{
    		//记录下一个结点
    		next = cur->next;
    		//当前结点指向前驱结点
    		cur->next = pre;
    		//cur pre 往后移动
    		pre = cur;
    		cur = next;
    	}
    	//将头结点指向最后一个结点 实现翻转
    	linkList->pHeader->next = pre;
    	return 1;
    }

## Main.c ##

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "LinkList.h"
    
    //使用结构体数据类型 测试万能单链表
    typedef struct Hero
    {
    	char name[64];
    	int age;
    }Hero;
    
    int Compare_Hero(void* hero1, void* hero2)
    {
    	Hero* h1 = (Hero*)hero1;
    	Hero* h2 = (Hero*)hero2;
    	return h1->age == h2->age && strcmp(h1->name, h2->name) == 0;
    }
    void Print_Hero(Hero* hero)
    {
    	if (NULL == hero)
    	{
    		return;
    	}
    	printf("name:%s,age:%d\n", hero->name, hero->age);
    	return;
    }
    int main(int argc, char *argv[])
    {
    	Hero h1 = { "关羽",38 };
    	Hero h2 = { "张飞",39 };
    	Hero h3 = { "赵云",29 };
    	Hero h4 = { "许褚",19 };
    	Hero h5 = { "鲁肃",25 };
    	Hero h6 = { "周瑜",27 };
    	Hero h7 = { "太史慈",40 };
    	LinkList list = Init_LinkList();
    	//根据位置进行插入
    	InsertByIndex_LinkList(list, 1, &h1);
    	InsertByIndex_LinkList(list, 100, &h2);
    	InsertByIndex_LinkList(list, 1, &h3);
    	InsertByIndex_LinkList(list, 2, &h4);
    	InsertByIndex_LinkList(list, 3, &h5);
    	InsertByIndex_LinkList(list, 1, &h6);
    	//根据值进行插入
    	InsertByValue_LinkList(list, &h5, &h7, Compare_Hero);//将太史慈插入到鲁肃之前
    	printf("元素个数:%d\n", Length_LinkList(list));
    	//正确顺序 周瑜 赵云 许褚 太史慈 鲁肃 关羽 张飞 
    	Foreach_LinkList(list, Print_Hero);
    
    	//删除第一个元素 周瑜
    	RemoveByIndex_LinkList(list, 1);
    	//删除位置非法
    	RemoveByIndex_LinkList(list, 100);
    	//根据值进行删除
    	Hero hero = { "许褚",19 };
    	RemoveByValue_LinkList(list, &hero,Compare_Hero);
    	printf("元素个数:%d\n", Length_LinkList(list));
    	//正确顺序 赵云 太史慈 鲁肃 关羽 张飞 
    	Foreach_LinkList(list, Print_Hero);
    
    	printf("翻转后:\n");
    	//翻转
    	Reverse_LinkList(list);
    	Foreach_LinkList(list, Print_Hero);
    
    	//清空链表
    	Clear_LinkList(list);
    	printf("清空链表后，元素个数:%d\n", Length_LinkList(list));
    
    	//销毁链表
    	Destroy_LinkList(list);
    
    
    	return 0;
    }

# 运行结果检测 #

![SouthEast][]

[Link 1]: http://blog.csdn.net/qq_29542611/article/details/79265973
[SouthEast]: /images/20220531/74ef36d24b574f9ab5b7f7261ff100b2.png