C语言数据结构基础-单链表

1.链表概念

在前面的学习中，我们知道了线性表，其中逻辑结构与物理结构都连续的叫顺序表，那么：

链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表

中的指针链接次序实现的。

2.链表组成

单链表元素（节点）由保存的数据和下个单元的地址组成

//结点结构体的定义
struct SListNode{
  int data;
  struct SListNode* next;
};

（node就是结点的意思）

国际惯例，我们进行typdef

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

那么此时我们可不可以在其中定义next的时候也用SLTNode呢？

SLTNode* next;

当然是不可以的，此时使用的SLTNode还未被定义，编译器还未能识别，使用了就会报错

为什么要用malloc开辟空间？

为了之后删除（使用free函数释放指针指向的空间）的时候方便，进行初始化时用malloc给每一个节点开辟空间

3.单链表各功能的实现

为了便于链表结点的创建和初始化，我们将其初始功能进行封装

SLTNode* SLTBuyNode(SLTDataType x) {
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL) {
		perror("malloc fail!");
		exit(1);
	}
	newnode->next = NULL;
	newnode->data = x;
	return newnode;
}

1.尾差

基于顺序表的经验，大概分为两种情况，一种是链表为空，另一种是链表不为空

我们首先传入该链表的头节点，通过直接链接或者先遍历再链接。

传一个指针进函数，对指针进行操作（每一个结点都有元素与其指针等级），那么以上函数就算传值调用，并不能让phead真正等于newnode

此处的传指针就是传值调用，指针作为变量来修改，就应该传指针的地址，才能达到传址调用的目的。

传递一个指针，可以在函数内部直接修改该指针指向空间的内容，但是想修改、操作传递来的指针，就必须传该指针的指针，才能通过该指针的指针来修改指针的内容。

先让创建的新结构体的next找到现在的phead(也就是*pphead,因为函数中不再存在phead这个变量)

再把现在处于第一个的结构体（我们刚刚自己创建的newnode）的地址给到phead

形参是实参的拷贝。

void SLTPushBack(SLTNode** pphead, SLTDataType x) {
	assert(pphead);

	SLTNode* newnode = SLTBuyNode(x);

	//链表为空，新节点作为phead
	if (*pphead == NULL) {
		*pphead = newnode;
		return;
	}
	//链表不为空，找尾节点
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	//ptail就是尾节点
	ptail->next = newnode;
}

为了便于主函数的调用和检验，我们写出能打印其数据的函数

void SLTPrint(SLTNode* phead) {
	assert(phead);
	SLTNode* pos = phead;
	while (pos) {
		printf("%d->",pos->data);
		pos = pos->next;
	}
	printf("NULL");
}

这样就能检验我们的尾插功能了。

2.头插

此处同理，我们任然需要传一个二级指针，通过二级指针对链表进行修改。

依然是分两种情况，实现如下：

void SLTPushFront(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
    //若为空
	if (*pphead == NULL) {
		*pphead = newnode;
		return;
	}
	//链接newnode 和 *pphead
	newnode->next = *pphead;
	*pphead = newnode;
}

能否调换以下两句的顺序？

当然不行，否则新节点将自己的地址赋给了自己的next。

由此可见，链表的实现，重在理清个节点之间的链接顺序。

3.尾删

释放空间，让原本倒数第二个结点的next指向NULL（先free，再置NULL）

多个节点时，我们需要先遍历链表找到最后一个节点的前驱节点ptail（原来的倒数第二个节点），删除最后一个节点的同时改变前驱节点的next的值

但如果只有一个节点呢？

if ((*pphead)->next == NULL) {
	free(*pphead);
	*pphead = NULL;
	return;
}

所以直接先free再置NULL即可 ,但请注意->和*的优先级不同，箭头是最高优先级，所以需要使用括号

void SLTPopBack(SLTNode** pphead) {
	assert(pphead);
	//没有节点时
	assert(*pphead);
	//只有一个节点时
	if ((*pphead)->next) {
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//多个节点时
	SLTNode* ptail = *pphead;
	while (ptail->next->next) {//很明显，只有一个节点的时候过不了，那么我们就需要在多个节点之前写出只有一个节点的情况
		ptail = ptail->next;
	}
	free(ptail->next);
	ptail->next = NULL;
}

尽管看上去是先写的一个节点，再写的多个节点，但正常逻辑应该是先写多个（通常情况）再考虑一个（特殊情况）

tips：

遍历链表与找链表尾结点是不一样的

（补充一下遍历链表的方法）

SLTNode* ptail = *pphead;
SLTNode* prev = NULL;
while (ptail->next)
{
	prev = ptail;
	ptail = ptail->next;
}

4.头删

如果链表已经为空的话应该直接退出，所以依然分三种情况考虑

void SLTPopFront(SLTNode** pphead) {
	assert(pphead);
	//没有节点 一个节点 多个节点
	assert(*pphead);

	SLTNode* tmp = *pphead;
	*pphead = (*pphead)->next;
	free(tmp);
	tmp = NULL;
	//发现此时一个节点和多个节点都能通过这段代码
}

依然是处理pphead和pphead->next的关系，此处又有一个小技巧，如过发现不能很好的直接通过等式调整各个指针所指向的位置，可以通过建立新的变量拷贝需要处理的数据。

5.指定位置前后的插入

为了能找到指定的位置，我们先写出一个查找函数

SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
	assert(phead);
	while (phead->next) {
		if (phead->data == x) {
			return phead;
		}
		phead = phead->next;
	}
	//没有找到
	return NULL;
}

为什么要断言链表不为空？因为如果链表为空，传进来的pos也必须为空，矛盾。

pos应当是已知链表（首节点地址为*pphead的）一个具体特定结点，而非NULL

当然，此处也可以不传二级指针只传一级指针，因为我们也可以不需要对传入的指针进行操作，但是为了接口的一致性，也可以都使用二级指针接口

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

void SLTInsertBefore(SLTNode* phead, SLTNode* pos, SLTDataType x) {
	assert(pos);
	assert(phead);
	
	if (pos == phead) {
		SLTPushFront(&phead, x);
		return;
	}

	SLTNode* newnode = SLTBuyNode(x);
	SLTNode* prev = phead;
	while (prev->next != pos) {
		prev = prev->next;
	}
	newnode->next = pos;
	prev->next = newnode;
	
}

为什么在指定位置前插入数据需要头结点的位置，而指定位置后的不需要呢（指定位置之前插入需要三个参数，指定位置之后插入需要两个参数）？

因为根据单链表的特性，除了最后一个节点，所有节点都能通过自己找到下一个节点，但是找不到上一个节点，所以当我们需要再指定位置之前插入数据时，就需要遍历链表来找到指定位置。

6.删除指定位置之后的节点

此处的条件为pos->next不为空，具体操作就是链接pos,pos->next,pos->next->next之间的关系

void SLTEraseAfter(SLTNode* pos) {
	assert(pos);
	if (pos->next == NULL) {
		return;
	}
	//pos pos->next pos->next->next
	SLTNode* tmp = pos->next;
	pos->next = pos->next->next;
	free(pos->next);
	pos->next == NULL;
}

7.删除指定位置的节点

同理

void SLTErase(SLTNode* phead, SLTNode* pos) {
	assert(phead);
	assert(pos);
	//刚好是头则执行头删
	if (phead == pos) {
		SLTPopFront(&phead);
		return;
	}
	while (phead->next != pos) {
		phead = phead->next;
	}
	phead->next = pos->next;
	free(pos);
	pos = NULL;
}

6,7检测如下