数据结构与算法：企业级链表实现（超详细）

Myth丶恋晨 2022-05-31 10:21 253阅读 0赞

# 企业级链表介绍 #

如果我们使用原始的C语言写链表的话，数据类型是被固定死的，如果业务换了 需要另一种数据类型，我们又得重新在写一个链表，**当然我们可以使用void\* 万能指针，因为void\* 可以接受任意类型的指针，那么我们就可以接受任意类型的数据的地址了，我们只需要维护用户提供的数据地址就可以**。详细介绍请看：[**数据结构与算法：单链表（利用万能指针实现对任意类型数据进行操作）**][Link 1]。今天我们介绍另外一种方法，让我们的写的链表不受业务结构而限制，在我们用的数据类型发生改变时并不需要去改变底层的链表结构。这就今天要和大家分享的**企业级链表，感觉这种思想太赞了**。我们在c语言中一般使用结构体作为复合数据类型，可以定义我们需要的数据集。如果我们将具体的业务数据放到LinkNode 链表结点中去，就会遇到前面分析的问题，业务和底层代码实现 耦合的太紧了。企业级链表就是来解决这个问题。

# 企业级链表分析 #

接前面分析的问题，**那么为何不把业务数据域分离出来呢？链表结点LinkNode中只放next指针域**。

typedef struct LinkNode  
\{  
struct LinkNode\* next;  
\}LinkNode;

**那我们的数据业务数据呢？放哪里呀？下面就是企业级链表的高明处。你定义的业务数据，该怎么定义就怎么定义，只需将LinkNode 作为你定义的业务数据类型的第一个成员 就行了**。比如说，下面定义一个学生数据类型。由于LinkNode 放在我们自定义的数据类型Student类型的第一个成员，**那么&LinkNode和&Student 他们是一样的！他们的起始地址是重合**的。那么我们底层使用LinkNode数据类型，**就不用管用户上层怎么定义了，你只要放置一个LinkNode成员在你定义的数据 类型的第一位，你将Student数据的地址传进来，我们依旧可以取到LinkNode数据，就行使用LinkNode 来维护链表之间的前驱后继关系**！**就如同下图一样**，给你定义的数据类型 安装一个钩子，将你定义的数据像链表一样链接起来了。

typedef struct Student  
\{  
LinkNode node;  
char name\[64\];  
int age;  
\}Student;

![Center][]

# 企业级链表代码实现 #

相关算法还是和正常的单链表差不多，只是用户使用的时候，按照要求使用就ok，LinkNode做为用户定义的业务数据的第一个成员，然后可以使用了。

## CompanyLinkList.h ##

#pragma once
    #ifndef __COMPANY_LINKLIST_H__
    #define __COMPANY_LINKLIST_H__
    
    typedef enum {TRUE,FASLE} BOOLEAN  ;//成功状态 FALSE 不成功 TRUE成功
    typedef enum { ERROR, OK } STATUS;	//状态信息 ERROR 发生错误 OK 一切正常
    
    typedef struct LinkNode
    {
    	struct LinkNode* next;
    }LinkNode;
    
    typedef struct LinkList
    {
    	LinkNode head;
    	int size;
    }LinkList;
    
    //创建链表并初始化
    LinkList* Create_LinkList();
    
    //插入数据 根据位置插入
    int Insert_LinkList(LinkList* list,int pos, LinkNode* data);
    
    //删除数据 根据位置删除
    int Remove_LinkList(LinkList* list, int pos);
    
    //查找数据，根据数据内容
    int Find_LinkList(LinkList* list, LinkNode* data,int (*Compare_Function)(LinkNode*,LinkNode*));
    
    //遍历链表
    int Foreach_LinkList(LinkList* list, void(*Foreach_Function)(LinkNode*));
    
    //清空数据 链表仍然可用
    int Clear_LinkList(LinkList* list);
    
    //销毁链表 链表不可用
    int Destroy_LinkList(LinkList* list);
    
    
    
    #endif // !__COMPANY_LINKLIST_H__

## CompanyLinkList.c ##

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "CompanyLinkList.h"
    
    //创建链表并初始化
    LinkList* Create_LinkList()
    {
    	LinkList* list = (LinkList*)malloc(sizeof(LinkList));
    	list->size = 0;
    	list->head.next = NULL;
    	return list;
    }
    
    //插入结点数据的地址 根据位置插入，pos从1开始
    int Insert_LinkList(LinkList* list, int pos, LinkNode* data)
    {
    	if (NULL == list || NULL==data)
    	{
    		return ERROR;
    	}
    	//位置太小插入到 第一个位置
    	if (pos < 1)
    	{
    		pos = 1;
    	}
    	//位置太大插入到 尾部
    	if (pos > list->size)
    	{
    		pos = list->size + 1;
    	}
    	//找到插入位置的前驱结点
    	LinkNode* pre = &list->head;
    	for (int i = 1; i < pos; i++)
    	{
    		pre = pre->next;
    	}
    	data->next = pre->next;
    	pre->next = data;
    	list->size++;
    	return OK;
    }
    
    //删除数据 根据位置删除 pos 从1 开始
    int Remove_LinkList(LinkList* list, int pos)
    {
    	//list为NULL 或者位置非法 直接返回
    	if (NULL == list || pos < 1 || pos > list->size)
    	{
    		return ERROR;
    	}
    	LinkNode* pre = &list->head;
    	//同样找到删除结点的前驱
    	for (int i = 1; i < pos; i++)
    	{
    		pre = pre->next;
    	}
    	//将不要的元素略过，因为我们只维护用户提供的数据的地址，释放内存不归我们管
    	pre->next = pre->next->next;
    	list->size--;
    	return OK;
    }
    
    //查找数据，根据数据内容，返回时链表中的第几个元素，从1开始计数 ，没找到返回-1
    //Compare_Function 用户提供 结点元素比较的回调函数
    int Find_LinkList(LinkList* list, LinkNode* data, int(*Compare_Function)(LinkNode*, LinkNode*))
    {
    	if (NULL == list || NULL == data || NULL == Compare_Function)
    	{
    		return ERROR;
    	}
    	LinkNode* node = list->head.next;
    	int flag = 0;// 是否查找到的标志
    	int index = 1;
    	while (node!=NULL)
    	{
    		if (Compare_Function(node, data))
    		{
    			flag = 1;
    			break;
    		}
    		node = node->next;
    		index++;
    	}
    	return flag ? index : -1;
    }
    
    //遍历链表
    //Foreach_Function 用户提供的遍历链表元素的回调函数
    int Foreach_LinkList(LinkList* list, void(*Foreach_Function)(LinkNode*))
    {
    	if (NULL == list || NULL == Foreach_Function)
    	{
    		return ERROR;
    	}
    	LinkNode* node = list->head.next;
    	while (NULL!=node)
    	{
    		Foreach_Function(node);
    		node = node->next;
    	}
    	return OK;
    }
    
    //清空数据 链表仍然可用
    int Clear_LinkList(LinkList* list)
    {
    	if (NULL == list)
    	{
    		return ERROR;
    	}
    	list->size = 0;
    	list->head.next = NULL;
    	return OK;
    }
    
    //销毁链表 链表不可用
    int Destroy_LinkList(LinkList* list)
    {
    	if (NULL == list)
    	{
    		return ERROR;
    	}
    	free(list);
    	list = NULL;
    	return OK;
    }
    
    //用户使用 企业级链表,只需要在自己定义的类型中将LinkNode 作为第一个成员即可使用
    //这样就将 具体的业务和底层链表算法 进行分离了
    typedef struct Student
    {
    	LinkNode node;
    	char name[64];
    	int age;
    }Student;
    //用户定义遍历的回调函数
    void Print_Student(LinkNode* node)
    {
    	Student* stu = (Student*)node;
    	printf("姓名:%s，年龄%d\n",stu->name,stu->age);
    	return;
    }
    //用户定义结点的比较回调函数
    int Compare_Student(LinkNode* node1, LinkNode* node2)
    {
    	Student* stu1 = (Student*)node1;
    	Student* stu2 = (Student*)node2;
    	//年龄和名字相同才相同
    	if (stu1->age == stu2->age && 0 == strcmp(stu1->name, stu2->name))
    	{
    		return 1;
    	}
    	return 0;
    }
    
    int main(int argc, char *argv[])
    {
    	//企业链表使用
    	Student s1, s2, s3, s4, s5;
    	s1.age = 11;
    	s2.age = 12;
    	s3.age = 13;
    	s4.age = 14;
    	s5.age = 15;
    
    	strcpy(s1.name, "aaa");
    	strcpy(s2.name, "bbb");
    	strcpy(s3.name, "ccc");
    	strcpy(s4.name, "ddd");
    	strcpy(s5.name, "eee");
    
    	//创建链表
    	LinkList* list = Create_LinkList();
    
    	//插入
    	Insert_LinkList(list, 1, (LinkNode*)&s1);
    	Insert_LinkList(list, 2, (LinkNode*)&s2);
    	Insert_LinkList(list, 3, (LinkNode*)&s3);
    	Insert_LinkList(list, 4, (LinkNode*)&s4);
    	Insert_LinkList(list, 5, (LinkNode*)&s5);
    
    	printf("插入5条数据后遍历:\n");
    	Foreach_LinkList(list, Print_Student);
    
    	//查找
    	Student s6;
    	s6.age = 15;
    	strcpy(s6.name, "eee");
    	int index = Find_LinkList(list,(LinkNode*)&s6, Compare_Student);
    	printf("查找的元素name=eee,age=15,是链表中第%d个元素\n",index);
    
    	//删除元素
    	Remove_LinkList(list, 1);
    
    	printf("删除第1个结点后遍历:\n");
    	Foreach_LinkList(list, Print_Student);
    
    
    	return 0;
    }

# 企业级链表运行验证 #

![Center 1][]

[Link 1]: http://blog.csdn.net/qq_29542611/article/details/79293422
[Center]: /images/20220531/be7affe8c5164e2d9f382c7558b3fa74.png
[Center 1]: /images/20220531/a6dc7305d2784823a0947908fd48fb81.png