【链表之单链表】

本文主要讲的是链表中的一种重要的形式单链表。
在这里插入图片描述
上图就是链表的逻辑图head 是一个指针存放链表第一个节点的地址所以可以形象地称为头指针。
在真实的物理地址中并不存在所谓的箭头这些箭头是我们想象出来的助于理解的东西。

假设地址都是随机的那么上图才是真实的物理图。
每个节点的指针存储的都是下一个节点的地址这样就像链条一样连接起来。

有了这些我们就可以实现单链表的各种操作了。

1.单链表的结构

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

就像上面单链表的结构所讲每个节点都有一个data 和一个指针用来保存下一个节点的地址。

2.单链表的头文件包含

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

3.单链表节点的创建

SLTNode* BuyListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
	//创建节点
}

断言的目的是防止申请空间失败而出错。

4.单链表的打印


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

5.单链表尾插法

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);//*pphead = plist,pphead = &plist,地址是不可能为空的如果为空就是传过来的参数传错了。

	SLTNode*newnode = BuyListNode(x);//创建节点
	//如果一开始链表为空即没有节点
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找到尾结点
		SLTNode* ptail = *pphead;
		while (ptail->next != NULL)
		{
			ptail = ptail->next;
		}
		//找到尾了插入新节点
		if (newnode != NULL)
		{
			newnode->data = x;
			newnode->next = NULL;
			ptail->next = newnode;
			//就是让尾节点的next存newnode的地址
		}
	}
}

尾插需要分情况来讨论当链表为空时如何插入。

6.单链表头插

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);//*pphead = plist,pphead = &plist,地址是不可能为空的如果为空就是传过来的参数传错了。

	SLTNode* newnode = BuyListNode(x);//创建节点
	//头插法不需要分情况讨论
	newnode->next = *pphead;
	*pphead = newnode;
}

头插不需要分情况讨论不管链表是否为空都可以满足要求。

7.单链表的尾删

void SListPopBack(SLTNode** pphead)
{
	assert(pphead);//*pphead = plist,pphead = &plist,地址是不可能为空的如果为空就是传过来的参数传错了。

	assert(*pphead != NULL);//空链表
	//一个节点的情况
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}

	//法1不需要临时变量
	//assert(*pphead);
	//SLTNode* ptail = *pphead;
	//while (ptail->next->next!=NULL)
	//{
	//	ptail = ptail->next;
	//}
	找到尾结点
	//free(ptail->next);
	//ptail->next =  NULL;

	//法2需要临时变量
	SLTNode* ptail = *pphead;
	SLTNode* prev = ptail;
	while (ptail->next!=NULL)
	{
		prev = ptail;
		ptail = ptail->next;
	}
	free(ptail);
	ptail = NULL;
	prev->next = NULL;

}

在尾删中有两种方法可以使用临时变量也可以不使用临时变量空间复杂度为O(1)。

8.单链表头删

void SListPopFront(SLTNode** pphead) // 头删
{
	assert(pphead);//*pphead = plist,pphead = &plist,地址是不可能为空的如果为空就是传过来的参数传错了。

	assert(*pphead != NULL);//针对链表为空的情况

	//让指向头节点的指针指向下一个节点
	SLTNode* pnext = (*pphead)->next;
	free(*pphead);
	*pphead = pnext;
}

值得注意的是单链表的头插和尾插都可以使用带哨兵位的头节点来进行头插和尾插带哨兵位的头节点式的头插或尾插的好处是当链表为空时不需要分类判断。
但是带哨兵位的头节点的头插或尾插也有劣势就是哨兵位节点需要申请并且需要释放掉。

9.单链表查找

SLTNode* SListFind(SLTNode* phead, SLTDataType x)//查找节点
{

	assert(phead!=NULL);
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	//最后没找到
	return NULL;
}

10.在pos位置之后插入节点

void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	SLTNode* newnode = BuyListNode(x);
	assert(newnode);
	
	//注意二者位置不能更换否则整条链表的数据就丢失了
	newnode->next = pos->next;
	pos->next = newnode;
}

11.在pos位置之前插入节点

//在pos的前面插入节点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);//*pphead = plist,pphead = &plist,地址是不可能为空的如果为空就是传过来的参数传错了。
	assert(pos);//地址不能为空
	//不管三七二十一先创建一个节点
	SLTNode* newnode = BuyListNode(x);
	SLTNode* posPrev = *pphead;
	//判断头插的情况
	if (*pphead == pos)
	{
		newnode->next = pos;
		*pphead = newnode;
	}//或者调用头插接口
	else
	{
		while (posPrev->next != pos)
		{
			posPrev = posPrev->next;
		}
		posPrev->next = newnode;
		newnode->next = pos;
	}

}

可以比较发现在pos位置之前和在pos位置之后插入节点的区别是在pos位置之后插入节点的方法更简单效率更高。

12.单链表删除pos位置之后的节点

void SlistEraseAfter(SLTNode* pos)//删除pos后一个节点
{
	assert(pos);//地址不能为空
	assert(pos->next!=NULL);
	SLTNode* Erasenode = pos->next;
	pos->next = Erasenode->next;
	free(Erasenode);
	Erasenode = NULL;
}

13.单链表删除pos位置的节点

void SlistErase(SLTNode** pphead, SLTNode* pos)//删除pos位置
{
	assert(pphead);//*pphead = plist,pphead = &plist,地址是不可能为空的如果为空就是传过来的参数传错了。

	assert(pos);//地址不能为空
	assert(*pphead != NULL);//空链表无法删除
	//链表只有一个节点的情况
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//删除头节点的情况相当于头删可以调用头删接口
	if (*pphead == pos)
	{
		(*pphead) = pos->next;
		free(pos);
		pos = NULL;
		return;
	}

	if (pos->next == NULL)//尾删的情况
	{
		SLTNode* pnext = *pphead;
		while (pnext->next != pos)
		{
			pnext = pnext->next;
		}
		free(pos);
		//pos = NULL;//这里pos是形参置空无意义
		pnext->next = NULL;
		return;
	}

	SLTNode* posprev = *pphead;
	while (posprev->next != pos)
	{
		posprev = posprev->next;
	}
	posprev->next = pos->next;
	free(pos);
	//pos = NULL;//这里pos是形参置空无意义
	//不过好习惯还是置空
}