AllinToyou

这个屌丝很懒，什么也没留下！

热门标签

数据结构-链表_链表数据结构

作者：AllinToyou | 2024-04-22 21:12:05

踩

链表数据结构

1、链表的概念及结构

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

注意：

链表在逻辑上是连续的，但是在物理上不一定连续。
现实中的节点一般都是从堆上申请出来的
从堆上申请的空间，是按照一定的策略分配的，两次申请的空间可能连续，也可能不连续

2、链表的分类

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

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

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

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。

3、单链表的实现

3.1定义单向链表的结构体

这里用typedef重新定义了int类型的名称，方便以后更换类型。


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

3.2 创建一个新节点

用malloc在堆上申请一个 SListNode 结构体大小的空间，这里在vs2019上面要对malloc开的空间进行判断，为空就报错误码，退出。不为空就继续，把x的值赋给data，让新节点的next指向空，这样一个新节点就创建好了，返回结构体指针。


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

3.3 单链表打印

这里的打印需不需要判空呢？答案是不需要，因为链表如果为空，那么plist肯定会指向空，所以在这里判断了也没用，单链表为空不打印是很正常的。

用一个指针cur指向头节点plist，遍历链表，如果cur不为空就继续，输出链表节点的值，这里的cur = cur->next;类似于++，表示指向下一个节点。


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

3.4 单链表尾插

这里的参数如果用一级指针，那么对函数内部的链表插入，并不会修改外部的链表。因为这里用一级指针相当于传值传参，因为刚开始链表为空，要想给链表插入第一个节点需要传二级指针。相当于是给一个函数传值，修改函数内部的变量，不会对外部的变量做修改，要想修改必须要传指针。

这里尾插稍微复杂一点，有两种情况，一链表里没有节点，那么创建一个新节点，让头指针指向新节点即可；二链表里有节点，定义一个cur指针，先让它指向头结点，遍历链表，直到cur指向最后一个节点，把新节点连在尾结点上即可，尾插完成。这里不用考虑新节点的next，因为创建的时候就已经让它指向空了。


// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
 
	SListNode* newnode = BuySListNode(x);
 
	//1.没有节点
	//2.多个节点
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		SListNode* cur = *pplist;
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}

3.5 单链表头插

这里二级指针就不过多解释了。二级指针相当于是一级指针的地址，地址不能为空，所以要判断一下，以防对空指针解引用。

头插比较简单，创建一个新节点，把新节点的next指向头结点，把原本指向头结点的指针指向新节点，头插就完成了。


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

3.6 单链表尾删

同样尾删也稍微复杂一些，有三种情况，一链表为空链表，判断链表里是否为空，为空就返回；二链表只有一个节点，直接释放掉指针指向的空间就可以了，把头指针置空，表示为空链表；三链表里有多个节点，创建一个指针del指向头节点，遍历链表让del指针指向倒数第二个节点，释放掉del的下一个节点，这里为什么这样做？是因为如果直接指向最后的节点，释放空间后，那么尾结点的前一个节点还是会指向释放掉的空间，会出现野指针问题，所以要注意！


// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	if (*pplist == NULL)
	{
		return;
	}
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* del = *pplist;
		while (del->next->next != NULL)
		{
			del = del->next;
		}
		free(del->next);
		del->next = NULL;
	}
}

3.7 单链表头删

头删比较简单，首先判断链表里是否为空，为空就返回，因为没有链表可以删了。链表里有节点，就先创建一个指针del指向头节点，让头指针指向头结点的下一个节点（因为不指向下一个节点，释放空间后就找不到下一个节点了），释放del指针指向的空间，养成好习惯给del指针置空，头删结束。


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

3.8 单链表查找

这里不需要对链表进行修改，所以传一级指针也没有问题。定义一个指针cur，指向头结点，遍历链表，如果cur里data的值等于x，那么就返回当前的节点，如果找不到返回空。


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

3.9 单链表在pos位置之后插入x

首先判断pos是不是空指针，然后创建一个新节点，让新节点的next指向pos节点的下一个节点，而后再让pos的next指针指向新节点，插入完成。


// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？  
//因为单链表找pos前面的位置比较麻烦，而且如果pos是第一个节点，那么还需要修改plist，
//所以不建议在pos之前插入，如果非得前插，那么定义两个指针即可。
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

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

这里如果删除pos位置的节点，前后链接就比较麻烦所以直接删除pos之后的值会简单一些。

如果pos位置后面没有节点，那么就直接返回，如果有节点，先定义一个指针指向pos节点的下一个节点，然后让pos节点的next直接指向下一个节点的下一个节点（跳过pos之后的节点），释放掉del指向的节点就完成了。


// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
//因为删除pos位置后，pos之前的位置找的话比较麻烦
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
 
	if (pos->next == NULL)
	{
		return;
	}
	SListNode* del = pos->next;
	pos->next = del->next;
	free(del);
}

3.11 单链表的销毁

定义一个指针prve指向头结点，，从头节点开始一个节点一个节点的销毁，定义一个cur指向prve的下一个节点，释放掉prve节点的空间，让prve指向cur节点，重复循环，直至节点释放完毕。


// 单链表的销毁
void SListDestroy(SListNode** pplist)
{
	assert(pplist);
	
	SListNode* prve = *pplist;
	while (prve != NULL)
	{
		SListNode* cur = prve->next;
		free(prve);
		prve = cur;
 
	}
	pplist = NULL;
}

操作演示：

4、双向链表的实现

4.1 定义双向链表的结构体

这里用typedef重新定义了int类型的名称，方便以后更换类型。


typedef int LTDateType;
 
typedef struct ListNode
{
	LTDateType Date;
	struct ListNode* prve;
	struct ListNode* next;
}DL;

4.2 创建一个新节点

从之前的图中可以看到，整个链表是需要一个哨兵位的头结点作为第一个，它里面一般不存放值。如果只有哨兵位的节点，那么他的prve和next是指向它自己的。（这里为了整体的参数保持一致，而用了返回头结点，当然你也可以用二级指针）


//创建一个新节点
DL* BuyDListNode(LTDateType x)
{
	DL* newnode = (DL*)malloc(sizeof(DL));
	if (newnode == NULL)
	{
		printf("malloc fail");
		exit(-1);
	}
	newnode->Date = x;
	newnode->next = NULL;
	newnode->prve = NULL;
	return newnode;
}
// 创建返回链表的头结点.
DL* DListCreate()
{
	DL* Guard = BuyDListNode(0);
	
	Guard->prve = Guard;
	Guard->next = Guard;
 
	return Guard;
}

4.3 双向链表打印

头结点创建以后先把打印函数写出来，因为这个链表是循环体，所以不能用判空作为终止条件，定义一个cur让它指向头节点的下一个，遍历一遍，如果cur等于头结点就结束，打印完成。（这里把头结点单独写出来，因为头结点一般不放值，没办法显示，而如果只有一个头节点，那么循环就不会进去）


// 双向链表打印
void DListPrint(DL* pHead)
{
	assert(pHead);
 
	DL* cur = pHead->next;
	printf("phead<==>");
 
	while (cur != pHead)
	{
		printf("%d<==>", cur->Date);
		cur = cur->next;
	}
	printf("\n");
}

4.4 双向链表尾插

有了头结点以后，就可以插入数据啦。首先进行尾插，尾插就是把新节点连接在尾结点的后面，这里找尾就比较好找啦，头结点的prve就是尾结点，把tail指向的节点和新节点链接起来，而后把头结点和新节点再链接起来就好了。


// 双向链表尾插
void DListPushBack(DL* pHead, LTDateType x)
{
	assert(pHead);
 
	DL* tail = pHead->prve;
	DL* NewNode = BuyDListNode(x);
	tail->next = NewNode;
	NewNode->prve = tail;
	NewNode->next = pHead;
	pHead->prve = NewNode;
}

4.5双向链表头插

头插也很方便，定义一个cur指向头结点的下一个节点，而后把pHead，NewNode和cur三个节点链接起来头插就完成了。


// 双向链表头插
void DListPushFront(DL* pHead, LTDateType x)
{
	assert(pHead);
 
	DL* cur = pHead->next;
	DL* NewNode = BuyDListNode(x);
	NewNode->next = cur;
	cur->prve = NewNode;
	pHead->next = NewNode;
	NewNode->prve = pHead;
}

4.6 双向链表尾删

定义两个指针cur和prve，把pHead和prve的节点链接起来，而后把cur位置申请的空间释放掉，再把cur指针指向空，尾删结束。


// 双向链表尾删
void DListPopBack(DL* pHead)
{
	assert(pHead);
 
	DL* cur = pHead->prve;
	DL* prve = cur->prve;
	prve->next = pHead;
	pHead->prve = prve;
	free(cur);
	cur = NULL;
}

4.7 双向链表头删

定义两个指针prve和cur，把pHead和cur的节点链接起来，而后把prve位置申请的空间释放掉，再把prve指针指向空，头删结束。


// 双向链表头删
void DListPopFront(DL* pHead)
{
	assert(pHead);
 
	DL* prve = pHead->next;
	DL* cur = prve->next;
	pHead->next = cur;
	cur->prve = pHead;
	free(prve);
	prve = NULL;
}

4.8 双向链表销毁

这里把链表遍历一遍，除了头结点其他节点的空间都释放掉，因为先释放头结点循环结束的条件就不那么容易写了，所以先释放其他节点的空间，最后在释放头结点的空间。这里的pHead置不置空都不重要，因为里面置空无法改变外部的指针，如果要在里面置空就需要二级指针，比较麻烦也容易出错，所以不建议，让使用的人用完后再把指针置空，让别人养成良好的习惯。（哈哈哈哈，开个玩笑）


// 双向链表销毁
void DListDestory(DL* pHead)
{
	assert(pHead);
	DL* cur = pHead->next;
	
	while (cur != pHead)
	{
		DL* next = cur->next;
		free(cur);
		cur = next;
	}
	free(pHead);
	pHead = NULL;
	printf("销毁完成\n");
}

4.9 双向链表查找

定义一个cur指针，遍历一遍链表，如果x和cur节点里的值相等就返回cur节点，如果找不到就返回NULL。这里的查找可以和后面的插入删除一起使用。


// 双向链表查找
DL* DListFind(DL* pHead, LTDateType x)
{
	assert(pHead);
	DL* cur = pHead->next;
	while (cur != pHead)
	{
		if (x == cur->Date)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

4.10 双向链表在pos位置之前插入

定义一个prve指针，指向pos的前一个节点，再把新节点链接到prve和pos中间就可以了，相当于在pos位置头插。这里就可以用find查找，找到指定位置，而后用Insert插入一个节点，是不是很方便。


// 双向链表在pos的前面进行插入
void DListInsert(DL* pos, LTDateType x)
{
	assert(pos);
	DL* NewNode = BuyDListNode(x);
	DL* prve = pos->prve;
 
	NewNode->next = pos;
	pos->prve = NewNode;
	prve->next = NewNode;
	NewNode->prve = prve;
}

4.11 双向链表删除pos位置节点

定义两个指针，prve指向pos前一个节点，cur指向pos后面的节点，把prve和cur的位置的节点链接起来，再把pos位置的空间释放掉就完成了。这里想，删除哪个节点用find一找，用Erase一删除，简简单单。


// 双向链表删除pos位置的节点
void DListErase(DL* pos)
{
	assert(pos);
	DL* cur = pos->next;
	DL* prve = pos->prve;
 
	prve->next = cur;
	cur->prve = prve;
	free(pos);
	pos = NULL;
}

5、顺序表和链表的区别

单链表的代码：9_5/9_5 · 景吉祥/作业库 - 码云 - 开源中国 (gitee.com)

双向链表的代码：DList/DList · 景吉祥/作业库 - 码云 - 开源中国 (gitee.com)

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】

数据结构-链表_链表数据结构

1、链表的概念及结构

2、 链表的分类

3、单链表的实现

3.1定义单向链表的结构体

3.2 创建一个新节点

3.3 单链表打印

3.4 单链表尾插

3.5 单链表头插

3.6 单链表尾删

3.7 单链表头删

3.8 单链表查找

3.9 单链表在pos位置之后插入x

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

3.11 单链表的销毁

4、双向链表的实现

4.1 定义双向链表的结构体

4.2 创建一个新节点

4.3 双向链表打印

4.4 双向链表尾插

4.5双向链表头插

4.6 双向链表尾删

4.7 双向链表头删

4.8 双向链表销毁

4.9 双向链表查找

4.10 双向链表在pos位置之前插入

4.11 双向链表删除pos位置节点

5、顺序表和链表的区别

2、链表的分类