【数据结构】单链表

发布于：2024-04-28 ⋅ 阅读:(25) ⋅ 点赞:(0)

单链表和顺序表一样都是属于数据结构中的一部分，下面来总结和实现单链表。在这里插入图片描述

一、链表的概念和结构

概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表
中的指针链接次序实现的 。
在这里插入图片描述
链表的结构跟⽕⻋⻋厢相似，淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只
需要将⽕⻋⾥的某节⻋厢去掉/加上，不会影响其他⻋厢，每节⻋厢都是独⽴存在的。
⻋厢是独⽴存在的，且每节⻋厢都有⻋⻔。想象⼀下这样的场景，假设每节⻋厢的⻋⻔都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带⼀把钥匙的情况下如何从⻋头⾛到⻋尾？
最简单的做法：每节⻋厢⾥都放⼀把下⼀节
⻋厢的钥匙。

在链表中每个“车厢”又是什么样的呢？
在这里插入图片描述
与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为**“结点/节点”**
节点的组成主要有两个部分：当前节点要保存的数据和保存下⼀个节点的地址（指针变量）。
图中指针变量 plist保存的是第⼀个节点的地址，我们称plist此时“指向”第⼀个节点，如果我们希
望plist“指向”第⼆个节点时，只需要修改plist保存的内容为0X0012FFA0。

为什么还需要指针变量来保存下⼀个节点的位置？
链表中每个节点都是独⽴申请的（即需要插⼊数据时才去申请⼀块节点的空间），我们需要通过指针
变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。
结合前⾯学到的结构体知识，我们可以给出每个节点对应的结构体代码：

struct SListNode
{
 int data; //节点数据
 struct SListNode* next; //指针变量⽤保存下⼀个节点的地址
};![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/f0e3ebd13b744d6c9c3bf2ef2cf799bd.png)

当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数
据，也需要保存下⼀个节点的地址（当下⼀个节点为空时保存的地址为空）。
当我们想要从第⼀个节点⾛到最后⼀个节点时，只需要在前⼀个节点拿上下⼀个节点的地址（下⼀个
节点的钥匙）就可以了。
给定的链表结构中，如何实现节点从头到尾的打印？
在这里插入图片描述
注意：
链表是线性表的一种。逻辑结构：一定是线性的。
物理结构：不一定是线性的。

  1. 链表由一个一个的节点组成
  2. 节点由数据+指向下一个节点的指针组成
  3. 节点一般是从堆上申请的

二、 单链表的实现

跟顺序表相同，我们需要设置一个头文件同一个源文件写函数具体的实现和一个测试文件。
在这里插入图片描述

在.h头文件中，创建节点和声明函数。

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

typedef int SLDataTypa;
typedef struct SLisNode
{
	 SLDataTypa data;
	 struct SLisNode* next;	
}SLTNode;
//打印
void SLTPrint(SLTNode* phead);
//尾插
void SLTPushBack(SLTNode** pphead, SLDataTypa x);
//头插
void SLTPushFront(SLTNode** pphead, SLDataTypa x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLDataTypa x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataTypa x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLDataTypa x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);

在这里插入图片描述
我们这里和之前我们写过的顺序表相同，要用到typedef int SLDataTypa方便以后类型的更改。

2.1 创建一个新节点

尾插和头插都需要插入新的节点，所以我们要先创建一个新节点
在这里插入图片描述

//创建新节点
SLTNode* SLTBuyNode(SLDataTypa x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
}

用malloc函数在堆上申请新节点。

2.2 尾插

函数声明

void SLTPushBack(SLTNode** pphead, SLDataTypa x);

函数的实现

void SLTPushBack(SLTNode** pphead, SLDataTypa x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;
	}
}

先用assert断言传进来的地址不能为空。
如果原来的头节点是空指针，直接将我们设置的新节点置为我们的头节点。
另一种情况就需要我们在尾部插入了。通过循环找尾然后插入。

注意：我们这里的形参为二级指针。为什么要传二级指针呢？我们在传参的时候，我们传的需要是头节点指针的地址，这时就需要二级指针来接收这才是传址调用。然而当我们传过来的是头节点的指针，不能影响实参是传值调用。

2.3 头插

函数声明

void SLTPushFront(SLTNode** pphead, SLDataTypa x)

函数的实现

//头插
void SLTPushFront(SLTNode** pphead, SLDataTypa x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;

}

在这里插入图片描述
先断言传过来的不能为空指针。让我们创建的新节点的next指针指向之前的头节点，然后把我们的新节点置为头节点。

2.4 尾删

函数声明

void SLTPopBack(SLTNode** pphead)

函数实现

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);
	if ((*pphead)->next = NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	SLTNode* pcur = *pphead;
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		pcur = ptail;
		ptail = ptail->next;
	}
	free(ptail);
	ptail = NULL;
	pcur->next = NULL;
}

在这里插入图片描述
断言pphead传过来的不能为空，*pphead节点也不能为空，空节点没办法删。
当链表就一个节点，直接释放这个节点然后在把这个节点置为空。
当链表有多个节点的时候，我们需要创建两个临时变量通过循环，一个变量先找到尾节点另一个变量找到尾节点的前一个节点。为什么要这样呢？想一想直接释放掉尾节点的话，那么尾节点的前一个节点的next指针就为野指针了。找到尾节点和尾节点前一个节点后，先释放尾节点然后把尾节点置为空，在把尾节点的前一个节点的next指针置为空。

2.5 头删

函数声明

void SLTPopFront(SLTNode** pphead)

函数的实现

void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;

}

在这里插入图片描述

断言和尾删一样，先把创建一个临时变量存头指针的下一个节点，然后释放头节点，然后将临时变量赋值给头节点。

2.6 查找

函数声明

SLTNode* SLTFind(SLTNode* phead, SLDataTypa x)

函数的实现

SLTNode* SLTFind(SLTNode* phead, SLDataTypa x)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
}

遍历在每个节点里找数据，找到了返回这个节点，没找到返回空指针。

2.7 指定位置之前插入数据

函数声明

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataTypa x)

函数的实现

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataTypa x)
{
	assert(pphead && *pphead);
	SLTNode* newnode= SLTBuyNode(x);
	if (pos = *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;

	}

}

在这里插入图片描述
先断言，这里我们pos节点不能为空节点，我们的链表不能为空，传过来的不能为空。如果指定节点是头节点，我们就用头插。如果指定位置在这个链表之间，我们先用循环便利到指定位置之前的节点。让新节点的next指针指向pos，让pos前一个节点的next指针指向新节点。

2.8 在指定位置之后插

函数声明

void SLTInsertAfter(SLTNode* pos, SLDataTypa x)

函数的实现

void SLTInsertAfter(SLTNode* pos, SLDataTypa x)
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

在这里插入图片描述
现让新节点的next指针指向pos的下一个节点，然后让pos的next指针指向新节点。这里其实还要有种代码
在这里插入图片描述
我们写的是第一种代码，大家想一想第二种代码有什么问题。
第二种代码，先让pos的next指针指向新节点，这时之前pos的next指针指向的节点就找不到了。

2.9 删除指定节点

函数声明

void SLTErase(SLTNode** pphead, SLTNode* pos)

函数的实现

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(*pphead && pphead);
	assert(pos);
	if (pos = *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prve = *pphead;
		while (prve->next != pos)
		{
			prve = prve->next;
		}
		prve->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

在这里插入图片描述

如果指定位置是头节点，直接调用头删就可以了。如果删除位置在链表之间，就用循环遍历到pos节点的前一个节点，让后让pos节点前一个节点的next指针指向pos节点的下一个节点。

2.10 删除pos之后的节点

函数的声明

void SLTEraseAfter(SLTNode* pos)

函数的实现

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

在这里插入图片描述

创建临时变量del存储pos的下一个节点，让pos的next指针指向pos的下一个节点。释放pos节点。

2.11销毁顺序表

函数声明

void SListDesTroy(SLTNode** pphead)

函数实现

void SListDesTroy(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

遍历，释放每一个节点。
.h

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

typedef int SLDataTypa;
typedef struct SLisNode
{
	 SLDataTypa data;
	 struct SLisNode* next;	
}SLTNode;

//打印
void SLTPrint(SLTNode* phead);

//尾插
void SLTPushBack(SLTNode** pphead, SLDataTypa x);

//头插
void SLTPushFront(SLTNode** pphead, SLDataTypa x);

//尾删
void SLTPopBack(SLTNode** pphead);

//头删
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* SLTFind(SLTNode* phead, SLDataTypa x);

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataTypa x);

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLDataTypa x);

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);

void SListDesTroy(SLTNode** pphead);

.c

#include"SList.h"

void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
//创建新节点
SLTNode* SLTBuyNode(SLDataTypa x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
}
//尾插
void SLTPushBack(SLTNode** pphead, SLDataTypa x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;
	}
}
//头插
void SLTPushFront(SLTNode** pphead, SLDataTypa x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;

}
//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);
	if ((*pphead)->next = NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	SLTNode* pcur = *pphead;
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		pcur = ptail;
		ptail = ptail->next;
	}
	free(ptail);
	ptail = NULL;
	pcur->next = NULL;
}
//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;

}
//查找
SLTNode* SLTFind(SLTNode* phead, SLDataTypa x)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
}
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataTypa x)
{
	assert(pphead && *pphead);
	SLTNode* newnode= SLTBuyNode(x);
	if (pos = *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;

	}

}
//在指定位置之后插
void SLTInsertAfter(SLTNode* pos, SLDataTypa x)
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(*pphead && pphead);
	assert(pos);
	if (pos = *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prve = *pphead;
		while (prve->next != pos)
		{
			prve = prve->next;
		}
		prve->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
// 删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}
//销
void SListDesTroy(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

test.c

#include"SList.h"
void test()
{
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;
	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;
	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;
	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;

	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;


	SLTNode* plist = node1;
	SLTPushBack(&plist, 1);
	

	SLTPrint(plist);

}
int main()
{
	test();
	return 0;
}

谢谢大家观看

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布