数据结构初阶——单链表_phead

上一篇为各位介绍了顺序表， 那么这一篇就来介绍另一种数据结构：单链表。

单链表只是链表的一种形式，后面还会介绍其它的形式。

---

目录

1. 单链表的基本结构

2. 增加数据

        2.1 尾插

        2.2 头插

3. 删除数据

        3.1 尾删

        3.2 头删

4. 查找

5. 修改

6. 随机插入

7. 随机删除

8. 其它随机插入删除

        8.1 在随机位置后插入

        8.2 在随机位置后删除

结尾总结

---

1. 单链表的基本结构

首先我们先思考一下：

（1 ）中间/头部的插入删除，时间复杂度为O(N)。

（1）增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

（2）增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

为了解决这些问题，就有了链表结构。

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

和顺序表一样，我们都会用到结构体，data为要存放的数据，next则存放下一个内存块的地址。

先申请四块空间为大家解释一下链表的结构，给每个结构体变量的data赋值，再依次把下一个结构体变量地址存放的每个next变量中，最后一个内存块的next指向一个空指针。

每个变量都是指针也是地址，所以逻辑上是可以连续的，由上一个就可以访问到这一个，这一个就可以访问到下一个，直到访问的下一个为空指针就停止。

写到这里就可以测试一下，顺便写一个打印函数，之后也是会用到的。

 此时phead指向这里，也是cur。

       phead不是NULL，就打印phead->data再把phead->next赋给phead，也就移动到了下一个位置，以此类推，直到访问到NULL就停止，这里打印一个箭头的样子也是为了形象，最后再打印一个NULL。 

---

2. 增加数据

        2.1 尾插

增加数据的时候就要考虑一下如何去传参

像把" 5 "插入到链表的尾部 ，这样传参会不会成功呢，一旦我这样说，那这里肯定是有问题的。

       这个函数返回值是void类型，不需要返回，传入plist和5，plist就是就是n1的地址，使用一级指针接收，当我们要操作的时候，phead形参只是plist实参的临时拷贝，而且函数返回类型还是void类型，调用完函数没有值被改变，这样就达不到插入数据的效果，所以就要思考一下，既然我们想要改变这个链表，也就是想要改变传入的plist，这样我们就得到了一个思路，想要改变一级指针就要传入二级指针。

传入一级指针的地址，使用二级指针来接收。

       改变值的问题解决了，接下来就是插入，插入的是一个新的内存块，就需要malloc申请一块新的内存，我们定义为newnode，这样我们就直接封装成一个新的函数，因为后面也会用到。

虽然说是一块空间，但在链表中有一个名字为节点，这里最后需要找到尾节点。

最后再想一个问题，如果一开始就是一个空链表呢？

所以这里一开始就不用assert来判断了，毕竟空链表也不是一个错误。那么空链表只有一个NULL那就比较方便了，直接把newnode赋给*pphead就可以了。

 来几个数测试一下。

 看到没有什么问题，那尾插就写完了。

        2.2 头插

开始时，还是先申请一块空间

如果开始是空链表，也是没有问题的，直接把newnode变成新的头节点。

再来几个数测试一下。

---

3. 删除数据

        3.1 尾删

 那我们再尾删3次

 就剩下一个节点了，那再删一次就变成空链表了。

看到最后的返回值，代码挂掉了。

当链表中只有一个值的时候，tail->next直接为NULL，就不会进入循环，free(tail)，那最后tailPrev->next就是对空指针访问，那自然会报错。

所以要判断链表中是有一个节点还是多个节点。

所以打印函数也不要去assert判断，空链表也打印出来看看，当然有需要也可以加，决定权在自己手里。

        3.2 头删

 回到刚才插入的地方，这回再头删测试一下，看看能不能回到最初的链表。

也是没有问题的，再换一个思路

 

同样的效果 。

还要注意的是(*pphead)->next ，这个小括号一定不能省略，如果不注意会出现操作符优先级引发的错误。

---

4. 查找

---

5. 修改

修改也是建立在查找的基础上的，只有找到了才能修改

pos就是找到的ret

---

6. 随机插入

上一个函数把最后的节点修改了，在这个节点之前插入。 

那再来想一想，如果pos指向的是头节点呢，想找到prev->next为pos，那根本就找不到，所以头插的情况要单独写。

把头节点改了，再头插。

---

7. 随机删除

---

8. 其它随机插入删除

        8.1 在随机位置后插入

        8.2 在随机位置后删除

---

结尾总结

关于链表的内容就介绍到这里，链表也是一种存放数据的形式，当然后面也会对单链表进行优化，想要变得好看一点可以写一个菜单，下面就是所有的代码。

SList.h文件

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
 
typedef int SLDataType;
 
typedef struct SListNode
{
	SLDataType data;
	struct SListNode* next;
}SLTNode;
 
//打印
void SListPrint(SLTNode* phead);
 
//申请新的内存
SLTNode* BuySListNode(SLDataType x);
 
//尾插/头插/尾删/头删
void SListPushBack(SLTNode** pphead, SLDataType x);
void SListPushFront(SLTNode** pphead, SLDataType x);
void SListPopBack(SLTNode** pphead);
void SListPopFront(SLTNode** pphead);
 
//查找
SLTNode* SListFind(SLTNode* phead, SLDataType x);
//修改
void SListModify(SLTNode** pphead, SLTNode* pos, SLDataType x);
//随机插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLDataType x);
//随机删除
void SListErase(SLTNode** pphead, SLTNode* pos);
 
//在pos位置后插入
void SListInsertAfter(SLTNode* pos, SLDataType x);
//在pos位置后插入
void SListEraseAfter(SLTNode* pos);

SList.c文件

#define _CRT_SECURE_NO_WARNINGS 1
 
#include "SList.h"
 
void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
 
SLTNode* BuySListNode(SLDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;
 
	return newnode;
}
 
void SListPushBack(SLTNode** pphead, SLDataType x)
{
	SLTNode* newnode = BuySListNode(x);
 
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
 
}
 
void SListPushFront(SLTNode** pphead, SLDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
 
void SListPopBack(SLTNode** pphead)
{
	assert(*pphead);//判断一下，如果是空链表就不能删了
 
	if ((*pphead)->next == NULL)
	{
		(*pphead) = NULL;
	}
	else
	{
		//SLTNode* tail, * tailPrev;
		//tail = *pphead;
		//tailPrev = NULL;
		//while (tail->next != NULL)
		//{
		//	tailPrev = tail;
		//	tail = tail->next;
		//}
		//free(tail);
		//tailPrev->next = NULL;
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}
 
void SListPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
 
	//SLTNode* next = *pphead;
	//*pphead = (*pphead)->next;
	//free(next);
	//next = NULL;
 
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}
 
SLTNode* SListFind(SLTNode* phead, SLDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
 
void SListModify(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
	assert(pos);
	SLTNode* cur = *pphead;
	while (cur != pos)
	{
		cur = cur->next;
	}
	cur->data = x;
 
}
 
void SListInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
	assert(pphead);
	assert(pos);
 
	if (*pphead == pos)
	{
		SListPushFront(pphead, x);	
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}
 
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
 
	if (*pphead == pos)
	{
		SListPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
 
}
 
void SListInsertAfter(SLTNode* pos, SLDataType x)
{
	assert(pos);
 
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
 
}
 
void SListEraseAfter(SLTNode* pos)
{
	assert(pos);
 
	if (pos->next == NULL)
	{
		return;
	}
	SLTNode* del = pos->next;
	pos->next = NULL;
	free(del);
	del = NULL;
}