链表的实现（文末附完整代码）

链表的概念及结构

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
我们在上一篇文章所学习的顺序表是连续存储的
例如：
顺序表就好比火车上的一排座位，是连续的
而链表就好比是火车的各节车厢，中间有东西将其互相连接的

链表的基本结构图如下：
有一个指针指向下一个节点

链表的概念及结构

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
链表可以是单向和双向，循环和不循环，带头和不带头，这样一组合，就会出现八种类型的列表
单向的列表如下：

双向列表：
相比较单向，双向的增删查改较为容易，他会自带一个prev的节点，能顾标记当前节点的前一个节点

循环列表：
其实循环列表就是最后一个节点指向了开头节点

带头和不带头：
头节点我们可以称其为哨兵位，它是不会在链表中存储有效的数据的

其实八种链表我们最常用的只有两种：
无头单向非循环链表：

带头双向循环列表：

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是后面的学习中你会发现其实他是比较简单的

链表的实现

首先我们要了解的就是单链表的实现：
头文件如下：

#include<stdio.h>
#include<assert.h>
#include<ctype.h>
#include<string.h>
#include<stdlib.h>
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
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位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestroy(SListNode** plist);

新节点的创建：
我们要创建一个节点，首先就是要为他动态开辟一个空间
然后再将这个新节点newnode的值赋予x，并且将他的next置为空，然后函数返回这个节点

SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

链表的打印：
打印链表是我们可以用一个符号->来代替空格，但是链表实际上是没有这个符号的
我们可以首先定义cur，从链表的第一个节点开始遍历，知道cur为空时，就不会打印了，并且打印一次cur的data，cur要等于cue的next

void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

单链表的尾插：
这里我们要注意的是要记得用二级指针，因为当链表为空时，我们要改变的是节点的地址，而我们要改变地址，就要用地址的地址，也就是二级指针
首先，需要插入一个节点我们要做的就是创建一个新节点，我们之前定义了的一个函数直接使用
然后我们创建一个tail指针，让他从链表的第一个位置开始遍历，一直遍历到最后一个节点，此时令tail的next等于newnode即可

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

单链表的头插：
头插比较简单，我们直接将新节点的next等于链表的第一个节点即可，也就是*pplist，我们传进来的是**pplist，是节点地址的地址，所以我们需要解引用一次才能将地址给newnode的next

void SListPushFront(SListNode** pplist, SLTDateType x)
{
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}

单链表的尾删：
尾删的情况我们要分为两种：
1.只有一个节点时：
只有一个节点时我们直接free掉这个节点，其次为了防止野指针，我们要将其置空
2.当有多个节点时：
我们创建一个tail和prev，然后用循环将tail遍历到最后一个节点，循环的终止条件时tail->next为空，条件满足时就将tail赋予prev，当跳出循环时，prev就是尾节点的前一个节点，我们直接将tail给free掉，将其置空，这样尾节点就被删除了

void SListPopBack(SListNode** pplist)
{
	assert(*pplist);//链表为空时不能再删，暴力检查 
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* prev = NULL;
		SListNode* tail = *pplist;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}

单链表的头删：
头删就很简单了，首先定义一个tail存入第一个节点的位置，然后将第一个节点的位置移动到他的next，注意记得将临时存储第一个节点位置的指针给free掉，避免出现野指针的问题

void SListPopFront(SListNode** pplist)
{
	assert(*pplist);//链表为空时不能再删，暴力检查
	SListNode* tail = *pplist;
	*pplist = (tail)->next;
	free(tail);
}

节点的查找：
节点的查找也比较容易，直接用while循环遍历，如果cur的data和x相等，就返回cur，否则就是没有这个节点，返回null

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	while (cur->next)
	{
		if (cur->data == x)
		{
			return cur;
			//break;
		}
		cur = cur->next;
	}
	return NULL;
}

在一个节点之后插入节点：
需要插入节点首先要做的就是创建一个新节点
然后首先要做的是将newnode的next连接到要插入位置pos的next
再将pos的next置为newnode
这里注意，位置不能颠倒，不然newnode的next就找不到了

void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

删除一个节点之后的节点：
要删除节点之后的一个节点，首先这个节点之后一定要有一个节点，所以要对pos->next进行断言
我们将pos->next存储到next中，然后将pos->next直接指向next->next即可，也就是把pos->next=pos->next->next

void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);
	//pos->next = pos->next->next;
	SListNode* next = pos->next;
	pos->next = next->next;
	free(next);
}

单链表的销毁：
直接将pplist置空即可

void SListDestroy(SListNode** pplist)
{
	SListNode* node = *pplist;
	node = NULL;
	free(node);
}

好了，今天的分享到这里就结束了，感谢大家的支持！
完整代码如下：

SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

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

void SListPushFront(SListNode** pplist, SLTDateType x)
{
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}

void SListPopBack(SListNode** pplist)
{
	assert(*pplist);//链表为空时不能再删，暴力检查 
	//SListNode* tail = pplist;
	//while (tail->next->next)
	//{
	//	tail = tail->next;
	//}
	//free(tail->next);
	//tail->next = NULL;
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* prev = NULL;
		SListNode* tail = *pplist;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}

void SListPopFront(SListNode** pplist)
{
	assert(*pplist);//链表为空时不能再删，暴力检查
	SListNode* tail = *pplist;
	*pplist = (tail)->next;
	free(tail);
}

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	while (cur->next)
	{
		if (cur->data == x)
		{
			return cur;
			//break;
		}
		cur = cur->next;
	}
	return NULL;
}

void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}


void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);
	//pos->next = pos->next->next;
	SListNode* next = pos->next;
	pos->next = next->next;
	free(next);
}

void SListDestroy(SListNode** pplist)
{
	SListNode* node = *pplist;
	node = NULL;
	free(node);

}

文章出处登录后可见！

已经登录？立即刷新

链表的实现（文末附完整代码）

链表的概念及结构

链表的概念及结构

链表的实现

相关推荐