当前位置：
  1. 首页
  2. 互联网
  3. 正文
本文介绍: 各位读者老爷好，鼠鼠我又来了哈。鼠鼠我呀现在来基于C语言实现以下单链表，希望对你有所帮助！鼠鼠我上次浅谈了顺序表。但是吧，Any coin has two sides。顺序表有一些缺陷：1.尾部插入效率还不错。头部或者中间插入删除，需要挪动数据，效率低下。2.顺序表满了以后只能扩容。扩容是有一定消耗的，扩容一般是存在一定的空间浪费：一次扩得越多，可能浪费越多；一次扩得少，可能需要频繁扩容。当然，顺序表也有它的优势：得益于它的物理空间连续，顺序表支持随机的下标访问。

各位读者老爷好，鼠鼠我又来了哈。鼠鼠我呀现在来基于C语言实现以下单链表，希望对你有所帮助！

目录

1.链表的概念及结构

2.链表的分类

3.无头单向非循环链表的实现

3.1.单链表打印 

3.2.单链表尾插

3.3.单链表头插

3.4.单链表尾删

3.5.单链表头删

3.6.单链表查找

3.7.单链表在pos位置之和插入值

3.8.单链表删除pos位置之后的值 

3.9.在pos的前面插入值

3.10.删除pos位置的值

3.11.销毁单链表

4.单链表的小应用

4.1.slist.h

4.2.slist.c

4.3.test.c

5.ending 

鼠鼠我上次浅谈了顺序表。但是吧，Any coin has two sides。

顺序表有一些缺陷：

1.尾部插入效率还不错。头部或者中间插入删除，需要挪动数据，效率低下。

2.顺序表满了以后只能扩容。扩容是有一定消耗的，扩容一般是存在一定的空间浪费：一次扩得越多，可能浪费越多；一次扩得少，可能需要频繁扩容。

当然，顺序表也有它的优势：

得益于它的物理空间连续，顺序表支持随机的下标访问。 

So，我们有链表可以避免顺序表的缺陷，那我们先来看看链表哈！

1.链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表
中的指针链接次序实现的 。

不带头非循环单向链表的逻辑结构如下图：

 

链表是由节点（或者结点）构成的。这些个节点一般是动态内存申请得来的，所以每个节点的地址没有关联，是随机的，也就是说链表的物理结构不连续。既然每个节点的地址是随机的，那我们如何管理链表呢？ 

其实也很简单，如上逻辑结构可知，只要节点有俩个数据域即可，一个数据域存放所需存入的值，另一个数据域存放下一个节点的地址（最后一个节点保存空指针）。这样我们就可以通过第一个节点找到第二个节点、第二个节点找到第三个节点……这样就可以管理链表了。

了解了链表的特点，那我们对于数据的增删改等操作，更改节点内存储的地址即可，不必挪动数据。而且节点是一个个动态申请得到的，想要多少就申请多少，自然就避免了扩容有浪费的情况。这样子就很好避免的顺序表的缺陷！

画图方便理解：

2.链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1.单向或者双向

2.带头（哨兵位）或者不带头

3.循环或者非循环

 虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

咱们这篇博客实现的是无头单向非循环链表。 

3.无头单向非循环链表的实现

具体我们实现这些无头单向非循环链表（以下简称单链表）的增删查改等等功能：

typedef int SLTDateType;

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

// 单链表打印
void SListPrint  (SListNode * plist);

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);

// 单链表的尾删
void SListPopBack(SListNode** pplist);

// 单链表头删
void SListPopFront(SListNode** pplist);

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);

// 单链表在pos位置之后插入值
void SListInsertAfter(SListNode* pos, SLTDateType x);

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);

// 在pos的前面插入值
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x);

// 删除pos位置的值
void SLTErase(SListNode** pphead, SListNode* pos);

//销毁单链表
void SLTDestroy(SListNode** pphead);

好了好了，一个个来实现吧！

3.1.单链表打印 

//单链表打印
void SListPrint(SListNode* plist)
{
		SListNode* cur = plist;
		while (cur != NULL)
		{
			printf("%d->", cur->data);
			cur = cur->next;
		}
		printf("NULLn");
}

这个打印的实现还是很简单的，我们只要遍历单链表在将每个节点的数据打印出来即可。

3.2.单链表尾插

//动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
//单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	if (*pplist == NULL)//单链表为空
	{
		*pplist = BuySListNode(x);
	}
	else//单链表不为空
	{
		SListNode* tail = *pplist;
		while (tail->next != NULL)//找尾
		{
			tail = tail->next;
		}
		SListNode* newnode = BuySListNode(x);
		tail->next = newnode;
	}
}

这个尾插的实现来说，正常情况下先找到单链表的最后一个节点（找尾），在让最后一个节点存储新申请节点的地址即可，所以要调用动态申请一个节点的函数（BuySListNode），这个函数已经让新申请的节点存储空指针和需要保存的数据了。 但是要区别单链表是否为空（如果不加以区分单链表是否为空的话就会访问空指针），如果为空的话直接让*pplist保存新申请的节点地址即可。

3.3.单链表头插

//动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
//单链表头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}

对于头插的实现，只要让新申请的节点 存储原来*pplist的地址，让*pplist保存新申请的节点的地址即可。

3.4.单链表尾删

//单链表尾删
void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);
	SListNode* tail = *pplist;
	SListNode* fronttail = *pplist;
	while (tail->next != NULL)//找尾节点和尾节点前一个节点
	{
		fronttail = tail;
		tail = tail->next;
	}
	if (fronttail->next == NULL)//一个节点
	{
		*pplist = NULL;
		free(tail);
		tail = NULL;
		fronttail = NULL;
	}
	else//多个节点
	{
		free(tail);
		tail = NULL;
		fronttail->next = NULL;
	}
}

对于尾删，我们要区分单链表为空、单链表有一个节点和单链表有多个节点的情况。如果单链表为空就不能删除，断言即可。单链表一个节点的话，让*pplist保存空指针，free掉尾节点（也是头节点）。 单链表有多个节点的话，free掉尾节点，让尾节点前一个节点保存空指针即可。（如果不区分一个节点和多个节点的情况，一律按多个节点情况来处理的话，当只有一个节点时，fronttail会成为野指针。）。

3.5.单链表头删

//单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);
	SListNode* next = (*pplist)->next;
	free(*pplist);
	*pplist = next;
}

这个简单，只要free掉头节点（free掉之前需要保存头节点下一个节点地址，不然的话就找不到头节点下一个节点了），*pplist保存头节点下一个节点地址即可。 

3.6.单链表查找

//单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

这个实现的话，只要遍历单链表找到单链表节点中第一个出现的与x相等的val ，再返回该节点的地址即可，找不到就返回空指针。

3.7.单链表在pos位置之和插入值

//动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
// 单链表在pos位置之后插入值
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	SListNode* next = pos->next;
	pos->next = newnode;
	newnode->next = next;
}

实现这个功能的话，我们需要知道pos的值（这个值是某个节点的地址，可以通过单链表查找获得），然后的话让pos指向的节点存储新申请节点的地址，新申请的节点存储pos指向的节点的下一个节点的地址即可（这个地址记得提前用变量存储下来，如果在改变pos指向的节点存储的地址之前没有存储下来的话，就找不到pos指向节点的下一个节点了）。

3.8.单链表删除pos位置之后的值 

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);//防止删pos指向尾节点 
	SListNode* next = pos->next->next;
	free(pos->next);
	pos->next = next;
}

这里需要注意防止单链表为空和防止pos指向尾节点（尾节点后面为空，不可删），断言即可。这个实现大致就是让pos指向的节点存储pos指向节点的后两个节点的地址，free掉pos指向节点后一个节点即可。

3.9.在pos的前面插入值

//动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
// 在pos的前面插入值
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{
	assert(pphead);
	assert((!*pphead && !pos) || (*pphead && pos));
	if (*pphead == pos)
	{
		SListPushBack(pphead, x);
	}
	else
	{
		SListNode* frontpos = *pphead;
		while (frontpos->next != pos)//找pos前一个节点
		{
			frontpos = frontpos->next;
		}
		SListNode* newnode = BuySListNode(x);
		SListNode* next = frontpos->next;
		frontpos->next = newnode;
		newnode->next = next;
	}
}

如果单链表为空，直接调用单链表尾插（单链表头插也行）即可。不为空就找到pos指向节点的前一个节点，让pos指向节点的前一个节点存储新申请节点地址，让新申请节点存储pos指向节点的地址即可。 

3.10.删除pos位置的值

// 删除pos位置的值
void SLTErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);
	assert(*pphead);//没有节点
	assert(pos);
	if ((*pphead)->next == NULL)//一个节点
	{
		SListPopFront(pphead);
	}
	else
	{
		SListNode* frontpos = *pphead;
		while (frontpos->next != pos)//找pos前一个节点
		{
			frontpos = frontpos->next;
		}
		SListNode* next = pos->next;
		free(pos);
		frontpos->next = next;
	}
}

注意断言，防止单链表为空，为空不能删除。如果单链表有一个节点，直接调用单链表头删（单链表尾删也行）即可。如果有单链表有多个节点，大致的话让pos指向的节点前一个节点存储pos指向节点后一个节点地址，free掉pos指向节点即可。

3.11.销毁单链表

//销毁单链表
void SLTDestroy(SListNode** pphead)
{
	assert(pphead);
	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

如果不再使用单链表的话，可以销毁单链表。虽然单链表是动态申请的，不手动销毁的话结束程序也会自动销毁 ，但手动销毁是一个好习惯。这个实现也简单，遍历单链表一一销毁节点即可。

4.单链表的小应用

对于上面的单链表增删查改等等实现来说，鼠鼠我讲解的只是大概思想，我们只要懂得这些思想再注意一些细节就可完成上面代码的实现。单链表的实现不是唯一的，上面代码只是一种参考，最重要要懂得单链表的含义和增删查改等等思想。

鼠鼠我还是一样，写了一个工程来验证单链表增删查改等等功能的实现，有兴趣的读者老爷可以将以下三个文件（上面的实现代码都在slist.c里面了）放到一个工程玩玩！

4.1.slist.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int SLTDateType;


typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;


// 单链表打印
void SListPrint  (SListNode * plist);


// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);


// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);


// 单链表的尾删
void SListPopBack(SListNode** pplist);


// 单链表头删
void SListPopFront(SListNode** pplist);


// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);


// 单链表在pos位置之后插入值
void SListInsertAfter(SListNode* pos, SLTDateType x);


// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);


// 在pos的前面插入值
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x);


// 删除pos位置的值
void SLTErase(SListNode** pphead, SListNode* pos);


//销毁单链表
void SLTDestroy(SListNode** pphead);

4.2.slist.c

#define _CRT_SECURE_NO_WARNINGS
#include"slist.h"


//动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

//单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	if (*pplist == NULL)//单链表为空
	{
		*pplist = BuySListNode(x);
	}
	else//单链表不为空
	{
		SListNode* tail = *pplist;
		while (tail->next != NULL)//找尾
		{
			tail = tail->next;
		}
		SListNode* newnode = BuySListNode(x);
		tail->next = newnode;
	}
}

//单链表打印
void SListPrint(SListNode* plist)
{
		SListNode* cur = plist;
		while (cur != NULL)
		{
			printf("%d->", cur->data);
			cur = cur->next;
		}
		printf("NULLn");
}

//单链表头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}

//单链表尾删
void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);
	SListNode* tail = *pplist;
	SListNode* fronttail = *pplist;
	while (tail->next != NULL)//找尾节点和尾节点前一个节点
	{
		fronttail = tail;
		tail = tail->next;
	}
	if (fronttail->next == NULL)//一个节点
	{
		*pplist = NULL;
		free(tail);
		tail = NULL;
		fronttail = NULL;
	}
	else//多个节点
	{
		free(tail);
		tail = NULL;
		fronttail->next = NULL;
	}
}

//单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);
	SListNode* next = (*pplist)->next;
	free(*pplist);
	*pplist = next;
}

//单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

// 单链表在pos位置之后插入值
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	SListNode* next = pos->next;
	pos->next = newnode;
	newnode->next = next;
}

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);//防止删pos指向尾节点 
	SListNode* next = pos->next->next;
	free(pos->next);
	pos->next = next;
}

// 在pos的前面插入值
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{
	assert(pphead);
	assert((!*pphead &amp;&amp; !pos) || (*pphead &amp;&amp; pos));
	if (*pphead == pos)
	{
		SListPushBack(pphead, x);
	}
	else
	{
		SListNode* frontpos = *pphead;
		while (frontpos->next != pos)//找pos前一个节点
		{
			frontpos = frontpos->next;
		}
		SListNode* newnode = BuySListNode(x);
		SListNode* next = frontpos->next;
		frontpos->next = newnode;
		newnode->next = next;
	}
}

// 删除pos位置的值
void SLTErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);
	assert(*pphead);//没有节点
	assert(pos);
	if ((*pphead)->next == NULL)//一个节点
	{
		SListPopFront(pphead);
	}
	else
	{
		SListNode* frontpos = *pphead;
		while (frontpos->next != pos)//找pos前一个节点
		{
			frontpos = frontpos->next;
		}
		SListNode* next = pos->next;
		free(pos);
		frontpos->next = next;
	}
}

//销毁单链表
void SLTDestroy(SListNode** pphead)
{
	assert(pphead);
	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

4.3.test.c

#define _CRT_SECURE_NO_WARNINGS
#include"slist.h"
void menu()
{
	printf("**********************n");
	printf("********0.退出********n");
	printf("****1.头插  2.头删****n");
	printf("****3.尾插  4.尾删****n");
	printf("****5.查找  6.打印****n");
	printf("*7.在pos位置之后插入值n");
	printf("*8.删除pos位置之后的值n");
	printf("*9.在pos的前面插入值**n");
	printf("*10.删除pos位置的值***n");
	printf("**********************n");
}
int main()
{
	SListNode* pplist = NULL;
	int input;
	do
	{
		menu();
		printf("请输入你想操作的数字：->");
		scanf("%d", &amp;input);
		if (input == 0)
		{
			SLTDestroy(&amp;pplist);
			printf("n");
			break;
		}
		else if (input == 1)
		{
			int number = 0;
			printf("请输入你要头插数据的个数：->");
			scanf("%d", &amp;number);
			printf("请输入你要头插的数据：->");
			while (number--)
			{
				SLTDateType x = 0;
				scanf("%d", &amp;x);
				SListPushFront(&amp;pplist, x);
			}
			printf("n");
		}
		else if (input == 2)
		{
			SListPopFront(&amp;pplist);
			printf("n");
		}
		else if (input == 3)
		{
			int  number = 0;
			printf("请输入你要尾插数据的个数：->");
			scanf("%d", &amp;number);
			printf("请输入你要尾插的数据：->");
			int i = 0;
			for (i = 0; i < number; i++)
			{
				SLTDateType x = 0;
				scanf("%d", &x);
				SListPushBack(&pplist, x);
			}
			printf("n");
		}
		else if (input == 4)
		{
			SListPopBack(&pplist);
			printf("n");
		}
		else if (input == 5)
		{
			SLTDateType x = 0;
			printf("请输入你要查找的值：->");
			scanf("%d", &x);
			SListNode* p = SListFind(pplist, x);
			if (p != NULL)
			{
				printf("你要查找的值地址是%pn", p);
			}
			else
			{
				printf("找不到！n");
			}
			printf("n");
		}
		else if (input == 6)
		{
			SListPrint(pplist);
			printf("n");
		}
		else if (input == 7)
		{
			SLTDateType x = 0,pos = 0;
			printf("请分别输入你要插入的值及pos指向的值：->");
			scanf("%d %d", &x, &pos);
			SListInsertAfter( SListFind(pplist,pos), x);
			printf("n");
		}
		else if (input == 8)
		{
			SLTDateType pos = 0;
			printf("请输入pos指向的值：->");
			scanf("%d", &pos);
			SListEraseAfter(SListFind(pplist, pos));
			printf("n");
		}
		else if (input == 9)
		{
			SLTDateType x = 0, pos = 0;
			printf("请分别输入你要插入的值及pos指向的值：->");
			scanf("%d %d", &x, &pos);
			SLTInsert(&pplist, SListFind(pplist, pos), x);
			printf("n");
		}
		else if (input == 10)
		{
			SLTDateType pos = 0;
			printf("请输入pos指向的值：->");
			scanf("%d", &pos);
			SLTErase(&pplist, SListFind(pplist, pos));
			printf("n");
		}
		else
		{
			printf("输入错误，请重新输入：->");
		}
	} while (input);
	return 0;
}

5.ending 

鼠鼠我呀不怎么会写博客，读者老爷看到这里如果觉得不好就多多包涵，看看图一乐也不是不行。当然如有不足，恳请斧正哈！

原文地址:https://blog.csdn.net/X__cheng/article/details/134655851

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。

如若转载，请注明出处：http://www.7code.cn/show_19297.html

如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！

上一篇 Hadoop运行模式及目录结构
下一篇 数据结构—堆

相关文章

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

插入图片
浏览器会保存昵称、邮箱和网站cookies信息，下次评论时使用。