数据结构之链表实现（c语言）_c语言链表实现

在数据结构的线性表中有：顺序表，链表等等。

动态顺序表是利用malloc函数创造出一段连续的空间，通过下标来访问空间中的每一个成员。

而今天介绍的链表与顺序表有很大的不同，链表是每有一个新的变量产生就会去malloc一个存放该变量的空间。并且是通过指针相连接。

链表有很多种：

1，单向链表：顾名思义他是只能朝一个方向走的。

1.1.1 单向带头链表 1.1.2 单向不带头链表。

在这里的头也可以叫做哨兵位，他里面存的数据我们是不关心的。我们只是用他来记住链表的头而已。

我们可以从图中看出单向链表之所以 单向是因为他的尾节点指针为空。

2，双向链表

双向链表，每个元素直接可以互相访问。

3，循环链表

循环链表就是尾节点可以指向头节点的链表。

单向，双向，带头，循环。以上几种特性可以随机结合，生成一种链表。链表种类有很多，这次要着重介绍的就是单向不循环不带头链表。

首先创建一个结构体用来存放数据和指向下一块空间的指针。

typedef int  Datatype;
//创建一个结构体来存放数据以及指向下一个数据的指针
typedef struct singlelinklist
{
	int data;
	struct singlelinklist* next;
}SLList;

 1、创建数据

先将要存入数据传入函数，将next指针置空，返回创建好的空间。

SLList* buydata(Datatype n)
{
	SLList* newnode = (SLList*)malloc(sizeof(SLList));
	if(newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = n;
	newnode->next = NULL;
 
	return newnode;
}

2、连接数据

用第一块的next指向下一块空间即可。因为单向的原因，我们需要再创建两个指针。一个叫head

一个叫tail。我们将head放在链表的第一个节点让他做头节点，tail作尾节点，放在链表的最后一个节点。每创建一个节点就将tail的next节点放在新节点上，再更新tail。最后返回头节点。

SLList* Creatsinglinklist(Datatype n)
{
	SLList* head = NULL, * tail = NULL;
 
	for(int i = 0;i<n;i++)
	{
		SLList* newnode = buydata(i);
		if(head == NULL)
		{
			head = tail = newnode;
		}
		else
		{
			tail->next = newnode;
			tail = newnode;
		}
	}
	return head;
}

3、尾删

链表的尾删就是将链表的最后一个节点删除。在实现这个功能时，我们应该考虑链表中的节点个数，当只有一个节点时。我们直接将该节点free掉，在将他置空。但是如果使用一级指针的话，由于形参的改变无法改变实参，所以在这里我们应该传入的是头节点的地址。在参数设置时也应该特别注意。另外，在释放掉尾节点时，新的尾节点的next应该指向空。

void Tail_deletion(SLList** sl)
{
	if((*sl)->next == NULL)
	{
		free(*sl);
		*sl = NULL;
	}
	else
	{
		SLList* prev = NULL;
		SLList* tail = *sl;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		prev->next = NULL;
		free(tail);
 
	}
}

4、尾插

在尾插元素时，我们也应该考虑到有可能该链表为空的情况，因此在参数设置时依旧使用二级指针传参。在该函数编写时我们先找到尾部，再进行操作。最后将新的尾节点的next置空。

void Tail_plugs(SLList** sl, Datatype n)
{
	SLList* newnode = buydata(n);
	SLList* newtail = *sl;
	if(*sl == NULL)
	{
		*sl = newnode;
	}
	else
	{
		//
		while(newtail->next)
		{
			newtail = newtail->next;
		}
		newtail->next = newnode;
	}
 
}

5、打印

我们先在函数中定义一个尾节点，尾节点开始时指向头节点，利用循环依次打印出数据即可。

void print(SLList* sl)
{
	assert(sl);
	SLList* tail = sl;
	while(tail)
	{
		printf("%d->", tail->data);
		tail = tail->next;
	}
	printf("NULL\n");
 
}

6、头插

头插时依然要想到，如果链表中没有节点的情况并且我们需要更新头节点。然后我们创建一个新的节点指向原先的头部即可。最后返回新的头部。

void Head_plug(SLList** sl, Datatype n)
{
	SLList* newnode = buydata(n);
	
	if(*sl = NULL)
	{
		*sl = newnode;
	}
	else
	{
		newnode->next = *sl;
	}
	*sl = newnode;
}

7、头删

因为我们需要改变头节点的地址，所以还是需要二级指针。当链表为空是直接返回空即可。

SLList* Head_deletion(SLList** sl)
{
	SLList* newhead = *sl;
	SLList* prev = *sl;
	if(*sl == NULL)
	{
		return;
	}
	else
	{
		newhead = (*sl)->next;
		free(*sl);
	}
	return newhead;
}

8、查找元素位置

在这个函数中我们需要返回查找到的元素的地址，并不需要对参数进行操作。在这里我们只需要遍历链表，在遍历的过程中进行比较。如果相等返回地址即可。

SLList* Linked_list_lookup(SLList* pos, Datatype n)
{
	assert(pos);
	SLList* tail = pos;
	while(tail)
	{
 
		if(tail->data == n)
		{
			return tail;
		}
		tail = tail->next;
		
	}
	return NULL;
}

9、在pos位置之后的数据插入

我们直接将pos的next保存下来，在将pos的next指向新元素。将这三个节点连接起来即可。

void Insert_backwards(SLList* pos, Datatype n)
{
	SLList* newnode = buydata(n);
	SLList* tail = pos->next;
 
	pos->next = newnode;
	newnode->next = tail;
 
}

10、删除pos之后的位置

因为我们删除的是pos之后的位置，首先应该判断pos的next是否为空，因为我们的pos很有可能是链表的尾。在判断之后，将pos给pos的next的next即可。在这里我们可以在定义一个指针来存放pos的next的地址。

void Delete_backwards(SLList* pos)
{
	if(pos->next = NULL)
	{
		return;
	}
	else
	{
		SLList* node = pos->next;
		pos->next = node->next;
		free(node);
	}
}

11、在pos位之前的插入

首先判断pos是否是链表的头节点，如果是函数逻辑写为头插，如果不是，我们依然需要定义指针，一个指向pos的next，另一个先指向头节点，通过迭代使指针指向pos的前一个节点。

void Insert_forward(SLList** phead,SLList* pos,Datatype n)
{
	SLList* newnode = buydata(n);
	if(*phead == pos)
	{
		Head_plug(phead, n);
	}
	else
	{
		SLList* prev = *phead;
		while(prev->next != pos )
		{
			prev = prev->next;
		}
		SLList* node = prev;
		node->next = newnode;
		newnode->next = pos;
	}
}

12、删除pos位

当pos位为头节点时，我们会改变头节点的地址，所以我们在这里的phead需要传入地址，并且在最后也应该将phead的新地址返回。但pos不是头节点时，我们创建一个指针先指向phead通过迭代时指针指向pos位的前一个节点。

void deleted_pos(SLList** phead, SLList* pos)
{
	if(*phead == pos)
	{
		Head_deletion(phead);
	}
	else
	{
		SLList* prev = *phead;
		while(prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

13、销毁链表

在这里我们需要将phead的空间free掉，地址置空。但传入一级指针是没有办法将传入phead的地址给置空的。因此依旧传入二级指针。通过迭代依次释放空间，最后置空即可。

void Destroyed(SLList** sl)
{
	SLList* cur = *sl;
	while(cur)
	{
		SLList* node = cur->next;
		free(cur);
		cur = node;
	}
	*sl = NULL;
}

完整版代码：

头文件：

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int  Datatype;
//创建一个结构体来存放数据以及指向下一个数据的指针
typedef struct singlelinklist
{
	int data;
	struct singlelinklist* next;
}SLList;
 
//接口实现：增删查改
//创建一个数据
SLList* buydata(Datatype n);
//将创造的各项数据通过指针连接起来
SLList* Creatsinglinklist(Datatype n);
//打印链表中的数据
void print(SLList* sl);
//尾删
void Tail_deletion(SLList** sl);
//尾插
void Tail_plugs(SLList** sl, Datatype n);
//头插
void Head_plug(SLList** sl, Datatype n);
//头删
SLList* Head_deletion(SLList** sl);
//查找
SLList* Linked_list_lookup(SLList* pos, Datatype n);
//在pos位之后的插入
void Insert_backwards(SLList* pos, Datatype n);
//在pos位之后的删除
void Delete_backwards(SLList* pos);
//在pos位之前的插入
void Insert_forward(SLList** phead, SLList* pos, Datatype n);
//删除pos位
void deleted_pos(SLList** phead, SLList* pos);
//销毁
void Destroyed(SLList** sl);

接口实现：

#include "singlelinklist.h"
 
SLList* buydata(Datatype n)
{
	SLList* newnode = (SLList*)malloc(sizeof(SLList));
	if(newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = n;
	newnode->next = NULL;
 
	return newnode;
}
SLList* Creatsinglinklist(Datatype n)
{
	SLList* head = NULL, * tail = NULL;
 
	for(int i = 0;i<n;i++)
	{
		SLList* newnode = buydata(i);
		if(head == NULL)
		{
			head = tail = newnode;
		}
		else
		{
			tail->next = newnode;
			tail = newnode;
		}
	}
	return head;
}
void print(SLList* sl)
{
	assert(sl);
	SLList* tail = sl;
	while(tail)
	{
		printf("%d->", tail->data);
		tail = tail->next;
	}
	printf("NULL\n");
 
}
void Tail_deletion(SLList** sl)
{
	if((*sl)->next == NULL)
	{
		free(*sl);
		*sl = NULL;
	}
	else
	{
		SLList* prev = NULL;
		SLList* tail = *sl;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		prev->next = NULL;
		free(tail);
 
	}
}
void Tail_plugs(SLList** sl, Datatype n)
{
	SLList* newnode = buydata(n);
	SLList* newtail = *sl;
	if(*sl == NULL)
	{
		*sl = newnode;
	}
	else
	{
		//β
		while(newtail->next)
		{
			newtail = newtail->next;
		}
		newtail->next = newnode;
	}
 
}
void Head_plug(SLList** sl, Datatype n)
{
	SLList* newnode = buydata(n);
	
	if(*sl = NULL)
	{
		*sl = newnode;
	}
	else
	{
		newnode->next = *sl;
	}
	*sl = newnode;
}
 
SLList* Head_deletion(SLList** sl)
{
	SLList* newhead = *sl;
	SLList* prev = *sl;
	if(*sl == NULL)
	{
		return;
	}
	else
	{
		newhead = (*sl)->next;
		free(*sl);
	}
	return newhead;
}
SLList* Linked_list_lookup(SLList* pos, Datatype n)
{
	assert(pos);
	SLList* tail = pos;
	while(tail)
	{
 
		if(tail->data == n)
		{
			return tail;
		}
		tail = tail->next;
		
	}
	return NULL;
}
void Insert_backwards(SLList* pos, Datatype n)
{
	SLList* newnode = buydata(n);
	SLList* tail = pos->next;
 
	pos->next = newnode;
	newnode->next = tail;
 
}
void Delete_backwards(SLList* pos)
{
	if(pos->next = NULL)
	{
		return;
	}
	else
	{
		SLList* node = pos->next;
		pos->next = node->next;
		free(node);
	}
}
void Insert_forward(SLList** phead,SLList* pos,Datatype n)
{
	SLList* newnode = buydata(n);
	if(*phead == pos)
	{
		Head_plug(phead, n);
	}
	else
	{
		SLList* prev = *phead;
		while(prev->next != pos )
		{
			prev = prev->next;
		}
		SLList* node = prev;
		node->next = newnode;
		newnode->next = pos;
	}
}
void deleted_pos(SLList** phead, SLList* pos)
{
	if(*phead == pos)
	{
		Head_deletion(phead);
	}
	else
	{
		SLList* prev = *phead;
		while(prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}
void Destroyed(SLList** sl)
{
	SLList* cur = *sl;
	while(cur)
	{
		SLList* node = cur->next;
		free(cur);
		cur = node;
	}
	*sl = NULL;
}