【数据结构】详解链表（一）——单链表（动图讲解）

作者：一个喜欢猫咪的的程序员

专栏：《数据结构》

喜欢的话：世间因为少年的挺身而出，而更加瑰丽。                                  ——《人民日报》

---

目录

前言：

单链表的结构和形成：

逻辑结构：

 物理结构（从计算机角度）：

BuySLTNode（创建结构体）： 

CreateSList部分（n个结构体形成链表）：

 PrintSList（打印单链表）：

 单链表的功能实现（增删查改）：

SLTPushBack尾插部分:

当plist不为NULL时：

当plist为NULL时：

SLTPopBack（尾删部分）：

SLTPushFront（头插部分）：

 SLTPopFront（头删部分）：

SLTFide（查找部分）：

SLTInsertAfter（在pos位置之后插入）：

 SLTInsertFront（在pos位置之前插入）：

SLTEraseAfter（删除pos之后的位置）： 

 SLTErase（删除pos位置）：

 SLTDestory（释放空间）：

Slist.h头文件引用和结构体定义： 

Slist.c各种功能函数实现：

Test.c测试文件： 

---

前言：

单链表是一种链式存取的 数据结构 ，用一组地址任意的 存储单元 存放线性表中的数据元素。 链表中的数据是以结点来表示的，每个结点的构成：元素 ( 数据元素 的映象) + 指针 (指示后继元素 存储 位置)，元素就是存储数据的存储单元，指针就是连接每个结点的 地址 数据。 链表中的数据是以结点来表示的，每个结点的构成：元素 ( 数据元素 的映象) + 指针 (指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。 以“结点的序列”表示线性表称作 线性链表 （单链表），单链表是链式存取的结构。 链接方式存储的线性表简称为链表（Linked List）。 ② 链表中结点的逻辑次序和物理次序不一定相同。

---

单链表的结构和形成：

将一个结构体包含两个部分，一个是数据，一个是与本身结构体同类型的结构体指针

typedef int SLDataType;
ct SListNode {//单链表
	SLDataType data;//数据
	struct SListNode* next;//指向下一个与本结构体相同的结构体变量的指针
}SLTNode;

这样就可以在结构体指针找到下一个结构体的位置，第一个指针找到了第二个结构体，第二个结构体指针找到第三个结构体，以此类推....这样就形成了一个链表。

逻辑结构：

 但计算机实际上并没有指向的箭头啊，我们可以通过指针指向下一个结构体的地址来实现！

 物理结构（从计算机角度）：

BuySLTNode（创建结构体）： 

我们是动态开辟malloc结构体，malloc函数可能会异地扩、本地扩或者NULL，因此我们需要判断malloc返回值是否为空！以及我们需要把地址传回去，防止异地扩后，地址不同！

对于malloc函数不熟悉的同学可以看看我的另外一篇博客：对动态内存开辟有详细解释http://t.csdn.cn/IkDCFhttp://t.csdn.cn/IkDCF

言归正传。我们来看一下这个函数如何实现：

SLTNode* BuySLTNode(SLDataType x)
{//创建结构体
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

---

CreateSList部分（n个结构体形成链表）：

我们这种情况是通过写4个语句来将这4个结构体穿起来，那如果我们要n个结构体形成链表呢？

我们结合一个图，来想想怎么把图中代码的能力实现，并实现n个呢？

 n个结构体相连，所以肯定是for循环，利用BuyTNode创建动态结构体，我们再将下一个结构体的地址传给结构体的next指针以此类推.....

SLTNode* CreateSList(int n)
{//将n个结构体形成链表
	SLTNode* phead = NULL;
	SLTNode* plist = NULL;
	for (int i = 0; i < n; i++)
	{
		SLTNode* newnode = BuySLTNode(i);
		if (plist == NULL)
		{
			phead = plist = newnode;
		}
		else
		{
			plist->next = newnode;
			plist = newnode;
		}
	}
	return phead;
}
v

因为使用BuySLTNode创建结构体时，next都为NULL。

plist.next=newnode来形成链表，我们这边有一个矛盾，当第一个结构体时，并没有第二个来赋值，我们可以这样：plist=newnode，这样的时候当newnode为第二个结构体的地址的时候就不为NULL，就会将第二个结构体赋值给第一个结构体的next指针将之前的覆盖。

---

 PrintSList（打印单链表）：

我们利用一个while循环遍历一遍打印就好。

void* PrintSList(SLTNode* phead)
{//打印链表
SLTNode* cur = phead;
while (cur!= NULL)
//如果这里是cur->next != NULL的话，会少一个值，因为cur->next==NULL时，cur->data有值的，它的下一个结构体才没有值
{
printf("[%d|%p]->", cur->data,cur->next);
cur = cur->next;//这里如果想要直接cur->next=...的话有点困难
}
printf("NULL");
}

如果这里是cur->next != NULL的话，会少一个值，因为cur->next==NULL时，cur->data有值的，它的下一个结构体才没有值

---

 单链表的功能实现（增删查改）：

SLTPushBack尾插部分:

当plist不为NULL时：

我们尾插要先找尾部，即NULL的地方。然后将newnode插到null后面就好了。

我们来看下面这个尾插是否有错？

 可能很多人觉得这样没有问题，但实际上是错的！！！

• tail为NULL和tail->next为NULL对于循环条件来说是不一样的。
• tail为NULL代表没有这个结构体，就下图4个结构体为例：当tail指向第4个结构体时，循环不会结束，tail下一个会指向NULL。当循环停止的时候，tail已经指向了NULL，而第四个结构体的next还是指向空，即使我们插进去一个结构体，也会在第四个结构体的时候next到NULL，相当于没有插入！

• tail->next为NULL代表没有下一个结构体了，这样tail->next=newnode就会将之前的尾部结构体和新加入的结构体连接起来形成链表！

当循环条件为tail.next！=NULL时：

void SLTPushBack(SLTNode* phead, SLDataType x)
{//尾插
//assert(phead);//这里不需要断言，空链表也可以尾插
SLTNode* newnode = BuySLTNode(x);
SLTNode* tail = phead;
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}

---

当plist为NULL时：

这个是我在plist为NULL时运行结果的截图：

 这里错误是由指针传参导致的！

你一定很疑惑把我明明把指针传过去，传地址不是可以改变原来的值吗?没有错啊.

我们先来复习一下：

• 你的老师一定跟你说函数在传值调用时，形参不可以改变实参！
• 传址调用才可以改变实参！

这是没有错的，但是它是相对而言的。 

• 指针本质是一个地址，我们所说的指针的值是一个地址，而不是这个地址指向的值。
•  NULL为空指针，NULL=0x0000000000（这是一个地址）。

我们要改变NULL这个指针的时候，注意：我们这里说要改变这个指针是指我们要改变这个地址（0x00000000），而不是这个地址的值。

那我们这里的 SLTNode* phead是不是相当于上图int a。

 因此我们要改变NULL这个指针，我们需要传SLTNode**pphead进去，那我们*pphead就可以改变NULL的值了！

 
void SLTPushBack(SLTNode** pphead, SLDataType x)
{//尾插
//assert(phead);//这里不需要断言，空链表也可以尾插
SLTNode* newnode = BuySLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else {
SLTNode* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
}

---

SLTPopBack（尾删部分）：

找到尾部，把最后一个结构体删掉，再把前一个结构体的next置为NULL

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

---

SLTPushFront（头插部分）：

void SLTPushFront(SLTNode** pphead, SLDataType x)
{//头插
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}

---

 SLTPopFront（头删部分）：

void SLTPopFront(SLTNode** pphead)
{//头删
	assert(*pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

---

SLTFide（查找部分）：

SLTNode* SLTFide(SLTNode* phead, SLDataType x)
{//查找
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
 }

---

SLTInsertAfter（在pos位置之后插入）：

假设pos在d3的位置：

void SLTInsertAfter(SLTNode* pos, SLDataType x)
{//在pos位置之后插入
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

为什么同样是插入数据，头插尾插要传二级指针，而这个函数要传一级指针呢？

在pos位置插入的话，首先这个pos得不为NULL。

而NULL空链表时，pos的值就为NULL，因此这里不需要改变指针的值，所以一级指针就够了！ 

---

 SLTInsertFront（在pos位置之前插入）：

分为两种情况：

• pos为链表第一个，那就相当于头插；
• 除去第一个以外的位置：

  

void SLTInsertFront(SLTNode** pphead, SLTNode* pos, SLDataType x)
{//在pos之前插入
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
		if(*pphead == pos)
		{
			SLTPushFront(pphead, x);
		}
		else
		{
			SLTNode* prev = *pphead;
			while (prev->next != pos)
			{
				prev = prev->next;
			}
			prev->next = newnode;
			newnode->next = pos;
		}
}

---

SLTEraseAfter（删除pos之后的位置）： 

找pos位置的下一个位置将它赋给一个指针nextNode，将pos的next连接到nextNode的下一个结构体的位置，这样就跳过这个指针了，还不要忘了释放这个被跳过的空间！！！

void SLTEraseAfter(SLTNode* pos)
{//删除pos之后的位置
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* nextNode = pos->next;
		pos->next = nextNode->next;
		free(nextNode);
	}
}

---

 SLTErase（删除pos位置）：

void SLTErase(SLTNode** pphead,SLTNode* pos)
{//删除pos位置
	assert(pos);
	if (pos = *pphead)
	{
		SLTEraseAfter(pos);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

---

 SLTDestory（释放空间）：

链表并不是连续的，只是一个又一个结构体跳过结构体指针链接起来，一次我们要一个一个释放！

void SLTDestory(SLTNode** pphead)
{
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

---

Slist.h头文件引用和结构体定义： 

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;
//typedef struct SListNode {//单链表
//	SLDataType data;//数据
//	struct SListNode* next;//指向下一个与本结构体相同的结构体变量的指针
//
//	//可以这么写吗？
//	//SLTNode* next;//答案是不可以的，SLTNode要在下一行之后才可以使用
//}SLTNode;
typedef struct SListNode {//单链表
	SLDataType data;//数据
	struct SListNode* next;//指向下一个与本结构体相同的结构体变量的指针
}SLTNode;
 
SLTNode* BuySLTNode(SLDataType x);//创建结构体
SLTNode* CreateSList(int n);//将n个结构体形成链表
void PrintSList(SLTNode* phead);//打印链表
 
void SLTPushBack(SLTNode** pphead, SLDataType x);//尾插
void SLTPopBack(SLTNode** pphead);//尾删
void SLTPushFront(SLTNode** pphead, SLDataType x);//头插
void SLTPopFront(SLTNode** pphead);//头删
SLTNode* SLTFide(SLTNode* phead, SLDataType x);//查找
void SLTInsertAfter(SLTNode* pos, SLDataType x);//在pos位置之后插入
void SLTInsertFront(SLTNode** pphead,SLTNode* pos,SLDataType x);//在pos位置之前插入
void SLTEraseAfter(SLTNode* pos);//在删除pos之后的位置
void SLTErase(SLTNode**pphead,SLTNode* pos);//删除pos位置
void SLTDestory(SLTNode** pphead);

---

Slist.c各种功能函数实现：

#include"Slist.h"
SLTNode* BuySLTNode(SLDataType x)
{//创建结构体
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
SLTNode* CreateSList(int n)
{//将n个结构体形成链表
	SLTNode* phead = NULL;
	SLTNode* plist = NULL;
	for (int i = 0; i < n; i++)
	{
		SLTNode* newnode = BuySLTNode(i);
		if (plist == NULL)
		{
			phead = plist = newnode;
		}
		else
		{
			plist->next = newnode;
			plist = newnode;
		}
	}
	return phead;
}
void PrintSList(SLTNode* phead)
{//打印链表
	SLTNode* cur = phead;
	while (cur!= NULL)
//如果这里是cur->next != NULL的话，会少一个值，因为cur->next==NULL时，cur->data有值的，它的下一个结构体才没有值
	{
		printf("%d->", cur->data);
		/*printf("[%d|%p]->", cur->data, cur->next);*/
		cur = cur->next;//这里如果想要直接cur->next=...的话有点困难
	}
	printf("NULL\n");
}
void SLTPushBack(SLTNode** pphead, SLDataType x)
{//尾插
	//assert(phead);//这里不需要断言，空链表也可以尾插
	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else {
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
void SLTPopBack(SLTNode** pphead)
{//尾删
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}
void SLTPushFront(SLTNode** pphead, SLDataType x)
{//头插
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
void SLTPopFront(SLTNode** pphead)
{//头删
	assert(*pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}
SLTNode* SLTFide(SLTNode* phead, SLDataType x)
{//查找
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
 }
void SLTInsertAfter(SLTNode* pos, SLDataType x)
{//在pos位置之后插入
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
void SLTInsertFront(SLTNode** pphead, SLTNode* pos, SLDataType x)
{//在pos之前插入
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
		if(*pphead == pos)
		{
			SLTPushFront(pphead, x);
		}
		else
		{
			SLTNode* prev = *pphead;
			while (prev->next != pos)
			{
				prev = prev->next;
			}
			prev->next = newnode;
			newnode->next = pos;
		}
}
void SLTEraseAfter(SLTNode* pos)
{//删除pos之后的位置
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* nextNode = pos->next;
		pos->next = nextNode->next;
		free(nextNode);
	}
}
void SLTErase(SLTNode** pphead,SLTNode* pos)
{//删除pos位置
	assert(pos);
	if (pos = *pphead)
	{
		SLTEraseAfter(pos);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}
void SLTDestory(SLTNode** pphead)
{
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

---

Test.c测试文件： 

#include"Slist.h"
//void test1()
//{
//	//第一种写法：
//	SLTNode* n1 = malloc();
//	SLTNode* n2 = malloc();
//	n1->next = n2;
//	//这里的n1是存放在堆区的，出了这个函数不会被销毁！
//	
//	//第二种写法：
//	//SLTNode n2;
//	//SLTNode n3;
//	//n2.next = &n3;
//	//n2这里是存放函数栈帧里面的，出了函数就会被销毁，因此不能这样写！
//}
void test2()
{
	//SLTNode* n1 = BuySLTNode(1);
	//SLTNode* n2 = BuySLTNode(2);
	//SLTNode* n3 = BuySLTNode(3);
	//SLTNode* n4 = BuySLTNode(4);
	//n1->next = n2;
	//n2->next = n3;
	//n3->next = n4;
	//n4->next = NULL;
 
	 SLTNode*plist=CreateSList(10);
	 PrintSList(plist);
	 printf("\n");
	 SLTPushBack(plist, 100);
	 PrintSList(plist);
	 
}
void test3()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 100);
	SLTPushBack(&plist, 200);
	SLTPushBack(&plist,300);
	PrintSList(plist);
 
	SLTPopBack(&plist);
	PrintSList(plist);
	/*SLTPopBack(&plist);
	PrintSList(plist);
	SLTPopBack(&plist);
	PrintSList(plist);*/
	SLTPushFront(&plist, 1);
	PrintSList(plist);
	SLTPopFront(&plist);
	PrintSList(plist);
	SLTPopFront(&plist);
	PrintSList(plist);
	SLTPopFront(&plist);
	PrintSList(plist);
}
void test4()
{
	SLTNode* plist = NULL;
	SLTNode* pos1 = SLTFide(plist, 200);
	if (pos1 == NULL)
	{
		printf("找不到\n");
	}
	else
	{
		printf("找到了\n");
	}
	SLTPushBack(&plist, 100);
	SLTPushBack(&plist, 200);
	SLTPushBack(&plist, 300);
	PrintSList(plist);
	SLTNode*pos=SLTFide(plist, 200);
	//SLTInsertAfter(pos, 10);
	//PrintSList(plist);
	//SLTInsertFront(&plist, pos, 1);
	//PrintSList(plist);
	SLTErase(&plist,pos);
	PrintSList(plist);
	SLTDestory(&plist);
	//if (pos == NULL)
	//{
	//	printf("找不到\n");
	//}
	//else
	//{
	//	printf("找到了\n");
	//}
}
int main()
{
	test4();
	return 0;
 
}