首页 > 其他分享 >【数据结构】单链表

【数据结构】单链表

时间：2023-06-11 23:34:14浏览次数：46  
标签：单链 pos pplist plist SListNode 数据结构 节点

前言

  • <font color=blue size=4>在学习数据结构时，单链表可谓是第一个需要跨越的台阶。</font>

  • 从C语言到数据结构，单链表能够真正的反映我们C语言到底学的扎不扎实，那是因为，单链表对于C语言中的指针，结构体，以及函数模块的实现有较高的要求。因此，通过本章的学习，要是能够自我实现单链表，那你的C语言功底会厚实，你的代码能力也会提升。

  • 当然，从C语言到数据结构阶段，单链表只是第一个需要跨越的台阶，后面还有更难的数据结构在等着大家，后面我会相继出文章。

单链表与顺序表的比较

  • 顺序表与单链表同属于线性表, <font color=red size=4>线性表（linear list）</font>是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串......

  • 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

在这里插入图片描述

<font color=red size=4>不同：</font>

  • 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

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

在这里插入图片描述

  • 顺序表扩容一般是二倍扩，这势必会有空间浪费。而单链表非如此，你想增加一个节点，就向内存申请一个节点，想去掉一个节点，就释放返还这个节点给内存。这就体现了，在扩容方面，单链表比顺序表要优。

  • 顺序表在头插头删或者在任意位置插入删除都需要挪动数组的数据，这必然会使效率下降，时间复杂度最多是O(N^2)。而单链表的这些操作，不需要挪动数据，最多也就O(N)。所以，在增删数据方面，单链表优于顺序表。

  • 当然顺序表优于单链表的情况是访问数据操作，顺序表可以直接通过下标访问，为O(1)。而单链表需要从头开始依次寻找，为O(N)。

单链表初始操作

  • 同样的，这里也需要三个文件，一个是SList.h（头文件），SList.c（实现函数接口的文件），test.c（测试文件）。

  • SList.h存放需要使用的库函数的头文件以及单链表节点结构体和接口函数声明。

  • 分析单链表的结构，我们需要一个变量来存放数据，需要一个结构体指针来指向下一个节点进行连接，所以初始操作如下：

#include <stdio.h>
// malloc 所需头文件
#include <stdlib.h>
// assert断言所需头文件
#include <assert.h>

// 每个节点存放的数据的类型
typedef int SLTDataType;  // 这里只需改变int就可以存放不同的数据
// 节点
typedef struct SListNode
{
	SLTDataType data;
	// 存放下一个节点的地址，依此进行链接形成单链表
	struct SListNode* next;
}SListNode;  // typedef 重命名为 SListNode，后面写起来方便

对应的函数接口有：

// 动态申请一个节点
SListNode* BuySListNode(SLTDataType x);
// 单链表打印
void SListPrint(SListNode* plist);

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDataType x);
// 单链表修改节点的data
void SListModify(SListNode* pos, SLTDataType NewData);

// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x);
// 单链表在pos位置之前插入x
void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDataType x);

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 单链表删除pos位置的值
void SListErasePos(SListNode** pplist, SListNode* pos);
// 单链表删除pos位置之前的值
void SListEraseBefore(SListNode** pplist, SListNode* pos);

// 单链表的销毁
void SListDestroy(SListNode** pplist);

我们只需要在SList.c与test.c文件开头包含SList.h,即可链接。

  • 有了上述的初始操作，接下来只需将头文件里的函数接口一一实现即可。

得到一个节点

  • 单链表的每一个元素我们称之为节点，每个节点存放着相应的数据和下一个节点的地址

  • 单链表从得到一个节点开始，由于后面的插入形式有多种，而在每个插入函数中都写得到一个节点的代码，未免有些麻烦，因此，这里将得到一个节点的功能单独拿出来作为一个函数，要插入直接调用这个函数获取节点即可。

  • 每当获取一个节点的时候，节点内的结构体指针都指向NULL。

  • 这里的节点是我们通过malloc在内存中申请的一段空间来存放的，并且每个节点之间的地址不连续（随机申请，可能相邻）。

  • 当我们向内存申请了一个节点时，需要返回指向这个节点的指针，如果不返回的话，函数结束后，指向这个节点的指针会被销毁，此时这个节点就找不到了，也就出现了内存泄漏的问题，所以，一定要返回指向这个节点的指针。

<font color=red size=4>下面是相关接口函数的代码：</font>

// 动态申请一个节点
SListNode* BuySListNode(SLTDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	// 判断一下是否申请失败，malloc申请失败返回空指针
	assert(newnode);
	// 存放相应数据
	newnode->data = x;
	// 初始化NULL
	newnode->next = NULL;

	// 返回指向这个节点的指针
	return newnode;
}

单链表的打印

  • 由于单链表是用指针相连的，因此也需要运用指针来遍历单链表。

  • 我们只有单链表的头指针，运用这个头指针，依次向下找节点并打印相应的数据，直到这个指针为NULL结束。因此，遍历单链表的循环条件是这个指针不为NULL。

  • 如果传递过来的头指针是空，也就说明这个单链表是空链表，此时循环不会进去，也就不会打印。

  • 所以，该函数模块不需要assert来判断单链表是不是空链表。是空他就不打印嘛。

  • 对于如何遍历，如果phead是指向头节点的指针，我们只需要phead = phead->next;即可使phead指向下一个节点。

<font color=red size=4>下面是相关接口函数的代码：</font>

// 单链表打印
void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;
	// 如果cur为NULL停止循环
	while (cur)
	{
		printf("%d ", cur->data);
		// 跳到下一个节点
		cur = cur->next;
	}
	// 最后指向NULL，打印NULL
	printf("NULL\n");
}

单链表的销毁

  • 由于单链表的每一个节点是用 ==malloc== 在堆上申请的空间，因此，在程序运行的最后需要将这些空间返还给操作系统。

  • 返还空间给操作系统使用的对应函数为==free== ，这里，我们不能天真的以为free指向头节点的指针就可以释放掉整个链表，因为每一个节点的空间分配是不连续的，所以这里也是要遍历一遍单链表，并依次释放每一个节点的空间。

  • 由于又要释放节点，又要遍历单链表，因此这里需要两个指针来操控，一个指针用来释放指向对应的空间，一个指针用来存放下一个节点的地址。

  • 我这里的销毁函数是传递一个二级指针的，也就是传递单链表的头指针的地址。当然，就将单链表的头指针传递过来也是可以的，我是为了能够释放完所有空间后将单链表的头指针置为NULL才这样做的（怕有人销毁完单链表后还用之前的单链表的头指针进行操作）。

  • 当然，此函数需要assert断言判断传过来的二级指针是否是NULL指针。如果是空指针就不再进行后续的操作了。但是，单链表可以为空，因为他为空的话，解引用二级指针（单链表的头节点指针）就为空，此时循环就不会进去。

<font color=red size=4>下面是相关接口函数的代码：</font>

// 单链表的销毁
void SListDestroy(SListNode** pplist)
{
	assert(pplist);
	
	SListNode* cur = *pplist;
	// cur为空的话while不执行
	while (cur)
	{
		SListNode* tmp = cur;
		cur = cur->next;
		free(tmp);
	}
	*pplist = NULL;
}

单链表的尾插

  • 既然是插入，就需要获取一个节点，这时候就需要调用==BuySListNode==函数了。

  • 单链表的尾插是比较简单的，通过循环利用指针依次寻找下一节点，直到找到最后一个节点为止，在将最后一个节点的节点指针next指向新的节点即可。

  • 如果此时单链表为空，当然也是可以插入的，只不过这里就需要分两个情况了，就是单链表为空和不为空。

  • 当单链表为空时插入，此时就是插入一个头节点，所以传过来的空指针要指向这个头节点，也就是节点指针需要改变。在调用函数时，一个指针的值需要改变，那就需要传递这个指针的地址，所以该函数需要使用二级指针来接受这个指针的地址。

在这里插入图片描述

  • 由于是二级指针，因此这里需要assert断言一下这个二级指针，怕直接传递一个空指针过来或者传递一个一级指针。

<font color=red size=4>下面是相关接口函数的代码：</font>

// 单链表尾插
// 二级指针接收一级指针的地址
void SListPushBack(SListNode** pplist, SLTDataType x)
{
	// 断言二级指针，截断二级指针为NULL的情况
	assert(pplist);
	
	// 获取一个结点
	SListNode* newnode = BuySListNode(x);
	// 如果单链表为空，更新头节点即可
	if (*pplist == NULL) *pplist = newnode;
	else
	{
		SListNode* cur = *pplist;
		// 遍历找尾节点，如果该节点的next为NULL，说明此节点就是尾节点，停止循环
		while (cur->next) cur = cur->next;
		// 连接新的尾
		cur->next = newnode;
	}
}

单链表的头插

  • 既然是插入，就需要获取一个节点，这时候就需要调用==BuySListNode==函数了。

  • 单链表的头插不需要遍历单链表，只要将新节点的next指向此时单链表的头节点即可。当然单链表指向头节点的指针需要改变指向新的头节点。既然需要改变头指针，那么此时就需要用到二级指针来操作了。

  • 如果此时单链表为空，也是一样，直接插入，更改头指针（二级指针操作）指向这个结点即可。

<font color=red size=4>下面是相关接口函数的代码：</font>

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x)
{
	assert(pplist);

	SListNode* newnode = BuySListNode(x);
	// 如果单链表为空，更新头节点即可
	if (*pplist == NULL) *pplist = newnode;
	else  // 不为空则将newnode的next指向当前的头节点即可
	{
		newnode->next = *pplist;
		// 更新头节点
		*pplist = newnode;
	}
}

单链表的尾删

  • 尾删，既然是尾，那么就需要遍历单链表找尾，但要注意的是，我们还需要找到尾的前一个节点，因为删完尾后，新的尾的next需要置为NULL。

  • 既然需要找到尾的前一个节点，那么循环内就需要两个指针来进行操作，如果说此时单链表只有一个节点，那么尾节点的前一个节点就不存在，因此此时对指向尾的前一个结点的指针进行操作就会出现问题，所以当单链表只有一个节点的时候，需要单独操作。

  • 当只有一个节点的时候，我们直接free头节点即可。这里需要将指向头节点的指针置为NULL（避免后面对该指针进行不当的操作），因此，这里也是需要使用二级指针的。

  • 当单链表为空的时候，是不可以删的，因此这里需要assert断言判断单链表是否为空，如果为空，直接暴力结束程序不给他删。

<font color=red size=4>下面是相关接口函数的代码：</font>

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	// 断言判断pplist是否为NULL，判断链表是否为空（为空就不能删）
	assert(pplist && *pplist);
	
	// 如果此时单链表只有一个节点，直接free头节点，将指向头节点的指针置为空，此时需要二级指针来操作
	if (!(*pplist)->next) free(*pplist), * pplist = NULL;
	else
	{
		// 找尾，和找尾的前一个节点，需要两个指针来操作
		SListNode* cur = *pplist, * tmp = NULL;
		while (cur->next)  // 判断条件找到尾就停止
		{
			tmp = cur;  // 最终tmp会指向尾节点的前一个节点
			cur = cur->next;
		}
		// 释放尾节点
		free(cur);
		// 将尾节点的前一个节点置为NULL
		tmp->next = NULL;
	}
}

单链表的头删

  • 头删不需要遍历单链表，只需释放头节点即可。

  • 当然，删除前需要找到头节点的下一个节点，这是因为头节点删除后，单链表的头需要更新，而新的头也就是删除的那个头节点的下一个节点。

  • 要更新新的头也就是需要改变头指针，因此这里也是需要用到二级指针的。

  • 既然是删除，当然也要判断单链表是否为空。

<font color=red size=4>下面是相关接口函数的代码：</font>

// 单链表头删
void SListPopFront(SListNode** pplist)
{
	// 判断pplist是否为空指针，判断单链表是否为空
	assert(pplist && *pplist);
	
	// 先存放下一个节点
	SListNode* cur = (*pplist)->next;
	// 释放头节点
	free(*pplist);
	// 更新头节点
	*pplist = cur;
}

单链表的查找

  • 查找比较简单，就是遍历单链表看看val与那个节点的数据相等，相等则返回该节点的地址，如果遍历完单链表都没有找到，那么返回NULL。

  • 查找函数不需要判断单链表是否为空，因为如果单链表为空的话，循环就不进去，直接返回空，就说明找不到，当然啦，空的单链表当然找不到啦。

<font color=red size=4>下面是相关接口函数的代码：</font>

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDataType x)
{
	SListNode* cur = plist;
	// 当cur为空时结束循环
	while (cur)
	{
		if (cur->data == x) return cur;
		cur = cur->next;
	}
	// 如果没找到就返回NULL
	return NULL;
}

单链表节点数据的修改

  • 该函数是将你想修改的节点的数据改为你想要的值。

  • 一般的，修改函数与查找函数是一起用的，因为有了前面的查找函数，我们可以先查找在修改。因此该函数的第一个参数为指向单链表节点的指针。

  • 当然，这里需要判断一下节点指针是否合法，如果该指针为NULL，说明在查找的时候没有找到对应数据的节点，此时直接暴力结束。

<font color=red size=4>下面是相关接口函数的代码：</font>

// 单链表修改节点的data
void SListModify(SListNode* pos, SLTDataType NewData)
{
	// 一般以find的返回值作为pos参数
	// 如果pos为空，说明没有这个节点，这里断言一下
	assert(pos);
	
	pos->data = NewData;
}

单链表在pos位置之后插入节点

  • 既然是pos位置之后，因此我们需要先利用查找函数来确定你想要的pos，然后再进行插入。

  • 插入需要先获取一个节点，调用==BuySListNode==函数。

  • 插入操作前，我们需要一个节点指针指向pos位置的下一个节点，这样是为了连接，然后插入操作如下图：

在这里插入图片描述

  • 当然，这里也需要判断一下pos的合法性。

<font color=red size=4>下面是相关接口函数的代码：</font>

// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	// 判断pos就间接的判断了单链表是否为空的情况
	assert(pos);

	SListNode* newnode = BuySListNode(x);
	// 存放pos节点的下一个节点
	SListNode* tmp = pos->next;
	pos->next = newnode;
	newnode->next = tmp;
}

单链表在pos位置之前插入节点

  • 既然是在pos位置之前插入，但单链表具有单向性，因此这里需要遍历单链表找到pos位置的前一个节点，然后再进行插入。

  • 可以取巧的是，如果pos刚好指向头节点，此时直接调用头插。

  • 由于这里调用了头插，而头插使用的是二级指针，因此该函数也是需要二级指针来操作的。

在这里插入图片描述

<font color=red size=4>下面是相关接口函数的代码：</font>

// 单链表在pos位置之前插入x
void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDataType x)
{
	// 如果pos不合法，就说明要么再查找时没有该节点，要么单链表为空，因此这里间接判断了单链表是否为空的情况
	assert(pplist && pos);

	// 如果pos为第一个节点，直接调用前面的头插
	if (*pplist == pos) SListPushFront(pplist, x);
	else
	{
		SListNode* newnode = BuySListNode(x);
		SListNode* cur = *pplist;
		// 找pos位置的前面一个节点
		while (cur->next != pos)
			cur = cur->next;
		// 连接
		cur->next = newnode;
		newnode->next = pos;
	}
}

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

  • 由于是直接对pos节点后面的节点进行操作，因此不需要传递头节点。

  • 对于pos，如果pos合法，就说明单链表一定不为空。

  • 因此这里只需要判断pos的合法性，当然，如果pos恰好指向最后一个节点，此时就删不了了，所以这种情况也需要assert断言。

  • 对于删除操作，首先需要找到pos的下一个节点的下一个节点，这是为了连接，然后再对pos的下一个节点进行删除。

在这里插入图片描述

<font color=red size=4>下面是相关接口函数的代码：</font>

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	// 直接判断pos
	assert(pos && pos->next);

	// 存放pos下一个节点的下一个节点
	SListNode* tmp = pos->next->next;
	// 释放pos的下一个节点
	free(pos->next);
	// 连接
	pos->next = tmp;
}

单链表删除pos位置之前的节点

  • 在之前，同样的，需要遍历单链表，找到pos节点的前一个节点和pos节点的前一个节点的前一个节点。

  • 如果pos刚好指向头节点，这是删不了的，会出问题，因此需要assert断言；如果pos刚好指向头节点的下一个节点，这里直接调用头删完成删除。

在这里插入图片描述

<font color=red size=4>下面是相关接口函数的代码：</font>

// 单链表删除pos位置之前的值
// 使用二级指针是因为调用头删函数需要传递二级指针，当然二级指针便于操作
void SListEraseBefore(SListNode** pplist, SListNode* pos)
{
	// pplist不能为NULL
	// pos要合法，间接体现了单链表是否为空
	// pos不能指向头节点，因为头节点的前面没有节点
	assert(pplist && pos && pos != *pplist);

	// 如果pos指向头节点的下一个节点，直接调用头删函数完成删除
	if ((*pplist)->next == pos) SListPopFront(pplist);
	else  // 正常情况
	{
	    // cur最终要指向pos的前一个结点，tmp最终要指向pos的前一个节点的前一个节点
		SListNode* cur = *pplist, * tmp = NULL;
		// 循环找位
		while (cur->next != pos)
		{
			tmp = cur;
			cur = cur->next;
		}
		// 删除前一个结点
		free(cur);
		// 连接
		tmp->next = pos;
	}
}

单链表删除pos位置的节点

  • 如果pos刚好指向头节点，直接调用头删；如果pos刚好指向尾节点（用pos->next == NULL ? 判断），直接调用尾删。

  • 因为头删尾删都需要传递二级指针，因此该函数也运用二级指针，而且二级指针也便于操作。

  • 一般情况，我们只需要遍历单链表找到pos节点的前一个结点和存放pos的后一个节点，然后将pos节点删除，连接pos的前一个节点和pos的后一个节点即可。

在这里插入图片描述

<font color=red size=4>下面是相关接口函数的代码：</font>

// 单链表删除pos位置的值
void SListErasePos(SListNode** pplist, SListNode* pos)
{
	assert(pplist && pos);

	if (*pplist == pos) SListPopFront(pplist); // 如果pos是指向头节点，直接复用头删
	else if (!pos->next) SListPopBack(pplist); // 如果pos是指向尾节点，直接复用尾删
	else  // 一般情况
	{
		// cur为pos的前一个结点
		SListNode* cur = *pplist;
		while (cur->next != pos) cur = cur->next;
		// tmp为pos的后一个结点
		SListNode* tmp = pos->next;
		// 删除pos结点
		free(pos);
		// 将pos的前一个节点与pos的后一个节点连接
		cur->next = tmp;
	}
}

整体代码

<font color=red size=5>SList.h</font>

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

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

// 动态申请一个节点
SListNode* BuySListNode(SLTDataType x);
// 单链表打印
void SListPrint(SListNode* plist);

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDataType x);
// 单链表修改节点的data
void SListModify(SListNode* pos, SLTDataType NewData);

// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x);
// 单链表在pos位置之前插入x
void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDataType x);

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 单链表删除pos位置的值
void SListErasePos(SListNode** pplist, SListNode* pos);
// 单链表删除pos位置之前的值
void SListEraseBefore(SListNode** pplist, SListNode* pos);

// 单链表的销毁
void SListDestroy(SListNode** pplist);

<font color=red size=5>SList.c</font>

#include "SList.h"

// 动态申请一个节点
SListNode* BuySListNode(SLTDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	assert(newnode);
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}
// 单链表打印
void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

// 单链表的销毁
void SListDestroy(SListNode** pplist)
{
	assert(pplist);
	
	SListNode* cur = *pplist;
	while (cur)
	{
		SListNode* tmp = cur;
		cur = cur->next;
		free(tmp);
	}
	*pplist = NULL;
}

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x)
{
	assert(pplist);

	SListNode* newnode = BuySListNode(x);
	if (*pplist == NULL) *pplist = newnode;
	else
	{
		SListNode* cur = *pplist;
		while (cur->next) cur = cur->next;
		cur->next = newnode;
	}
}
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x)
{
	assert(pplist);

	SListNode* newnode = BuySListNode(x);
	if (*pplist == NULL) *pplist = newnode;
	else
	{
		newnode->next = *pplist;
		*pplist = newnode;
	}
}
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(pplist && *pplist);

	if (!(*pplist)->next) free(*pplist), * pplist = NULL;
	else
	{
		SListNode* cur = *pplist, * tmp = NULL;
		while (cur->next)
		{
			tmp = cur;
			cur = cur->next;
		}
		free(cur);
		tmp->next = NULL;
	}
}
// 单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(pplist && *pplist);

	SListNode* cur = (*pplist)->next;
	free(*pplist);
	*pplist = cur;
}

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDataType x)
{
	// 这里可以不断言，但建议断言，因为使用find返回NULL可能是单链表本身就是空的，
	// 但一般是找不到才返回NULL
	assert(plist);

	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x) return cur;
		cur = cur->next;
	}
	return NULL;
}
// 单链表修改节点的data
void SListModify(SListNode* pos, SLTDataType NewData)
{
	// 一般以find的返回值作为pos参数
	// 如果pos为空，说明没有这个节点，这里断言一下
	assert(pos);

	pos->data = NewData;
}

// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);

	SListNode* newnode = BuySListNode(x);
	SListNode* tmp = pos->next;
	pos->next = newnode;
	newnode->next = tmp;
}
// 单链表在pos位置之前插入x
void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDataType x)
{
	assert(pplist && pos);

	if (*pplist == pos) SListPushFront(pplist, x);
	else
	{
		SListNode* newnode = BuySListNode(x);
		SListNode* cur = *pplist;
		while (cur->next != pos)
			cur = cur->next;
		cur->next = newnode;
		newnode->next = pos;
	}
}

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	assert(pos && pos->next);

	SListNode* tmp = pos->next->next;
	free(pos->next);
	pos->next = tmp;
}
// 单链表删除pos位置的值
void SListErasePos(SListNode** pplist, SListNode* pos)
{
	assert(pplist && pos);

	if (*pplist == pos) SListPopFront(pplist); // 如果pos是指向头节点，直接复用头删
	else if (!pos->next) SListPopBack(pplist); // 如果pos是指向尾节点，直接复用尾删
	else
	{
		SListNode* cur = *pplist;
		while (cur->next != pos) cur = cur->next;
		SListNode* tmp = pos->next;
		free(pos);
		cur->next = tmp;
	}
}
// 单链表删除pos位置之前的值
void SListEraseBefore(SListNode** pplist, SListNode* pos)
{
	assert(pplist && pos && pos != *pplist);

	if ((*pplist)->next == pos) SListPopFront(pplist);
	else
	{
		SListNode* cur = *pplist, * tmp = NULL;
		while (cur->next != pos)
		{
			tmp = cur;
			cur = cur->next;
		}
		free(cur);
		tmp->next = pos;
	}
}

<font color=red size=5>test.c</font>

这里有多个测试用例，可以自己捣鼓。

#include "SList.h"

void TestList1()
{
	SListNode* plist = NULL;

	SListPrint(plist);
	SListPushBack(&plist, 1);
	SListPrint(plist);
	SListPushBack(&plist, 2);
	SListPrint(plist);
	SListPushBack(&plist, 3);
	SListPrint(plist);
	SListPushBack(&plist, 4);
	SListPrint(plist);
	SListPushBack(&plist, 5);
	SListPrint(plist);
	SListPushBack(&plist, 6);
	SListPrint(plist);

	SListPopBack(&plist);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);

	SListDestroy(&plist);
}

void TestList2()
{
	SListNode* plist = NULL;
	SListPrint(plist);

	SListPushFront(&plist, 1);
	SListPrint(plist);
	SListPushFront(&plist, 2);
	SListPrint(plist);
	SListPushFront(&plist, 3);
	SListPrint(plist);
	SListPushFront(&plist, 4);
	SListPrint(plist);
	SListPushFront(&plist, 5);
	SListPrint(plist);
	SListPushFront(&plist, 6);
	SListPrint(plist);

	SListPopFront(&plist);
	SListPrint(plist);
	SListPopFront(&plist);
	SListPrint(plist);
	SListPopFront(&plist);
	SListPrint(plist);
	SListPopFront(&plist);
	SListPrint(plist);
	SListPopFront(&plist);
	SListPrint(plist);
	SListPopFront(&plist);
	SListPrint(plist);

	SListDestroy(&plist);
}

void TestList3()
{
	SListNode* plist = NULL;
	SListPrint(plist);

	SListPushFront(&plist, 1);
	SListPrint(plist);
	SListPushFront(&plist, 2);
	SListPrint(plist);
	SListPushFront(&plist, 3);
	SListPrint(plist);
	SListPushFront(&plist, 4);
	SListPrint(plist);
	SListPushFront(&plist, 5);
	SListPrint(plist);
	SListPushFront(&plist, 6);
	SListPrint(plist);

	SListModify(SListFind(plist, 1), 99999);
	SListPrint(plist);
	SListModify(SListFind(plist, 2), 99999);
	SListPrint(plist);
	SListModify(SListFind(plist, 3), 99999);
	SListPrint(plist);
	SListModify(SListFind(plist, 4), 99999);
	SListPrint(plist);
	SListModify(SListFind(plist, 5), 99999);
	SListPrint(plist);
	SListModify(SListFind(plist, 6), 99999);
	SListPrint(plist);

	SListDestroy(&plist);
}

void TestList4()
{
	SListNode* plist = NULL;

	/////////////////////////    SListInsertAfter
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPushFront(&plist, 5);
	SListPushFront(&plist, 6);
	SListPrint(plist);
	SListInsertAfter(SListFind(plist, 1), 999999);
	SListPrint(plist);
	SListInsertAfter(SListFind(plist, 6), 999999);
	SListPrint(plist);

	////////////////////////      SListInsertBefore
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushBack(&plist, 5);
	SListPushBack(&plist, 6);
	SListPrint(plist);

	SListInsertBefore(&plist, SListFind(plist, 6), 999999);
	SListPrint(plist);
	SListInsertBefore(&plist, SListFind(plist, 1), 999999);
	SListPrint(plist);

	/////////////////////////       SListEraseAfter
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushBack(&plist, 5);
	SListPushBack(&plist, 6);
	SListPrint(plist);

	SListEraseAfter(SListFind(plist, 1));
	SListPrint(plist);
	SListEraseAfter(SListFind(plist, 3));
	SListPrint(plist);
	SListEraseAfter(SListFind(plist, 5));
	SListPrint(plist);
	// 传递最后一个节点位置会出问题
	//SListEraseAfter(SListFind(plist, 5));
	//SListPrint(plist);

	/////////////////////////        SListErasePos
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushBack(&plist, 5);
	SListPushBack(&plist, 6);
	SListPrint(plist);

	SListErasePos(&plist, SListFind(plist, 1));
	SListPrint(plist);
	SListErasePos(&plist, SListFind(plist, 6));
	SListPrint(plist);
	SListErasePos(&plist, SListFind(plist, 2));
	SListPrint(plist);
	SListErasePos(&plist, SListFind(plist, 3));
	SListPrint(plist);
	SListErasePos(&plist, SListFind(plist, 4));
	SListPrint(plist);
	SListErasePos(&plist, SListFind(plist, 5));
	SListPrint(plist);

	/////////////////////////       SListEraseBefore
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushBack(&plist, 5);
	SListPushBack(&plist, 6);
	SListPrint(plist);

	SListEraseBefore(&plist, SListFind(plist, 6));
	SListPrint(plist);
	SListEraseBefore(&plist, SListFind(plist, 6));
	SListPrint(plist);
	SListEraseBefore(&plist, SListFind(plist, 6));
	SListPrint(plist);
	SListEraseBefore(&plist, SListFind(plist, 6));
	SListPrint(plist);
	//// 不能传第一个节点的位置
	//SListEraseBefore(&plist, SListFind(plist, 1));
	//SListPrint(plist);
	SListEraseBefore(&plist, SListFind(plist, 6));
	SListPrint(plist);

	SListDestroy(&plist);
}

int main()
{
	//TestList1();
	//TestList2();
	//TestList3();
	TestList4();

	return 0;
}

写在最后

<font color=red size=4>对于单链表来说，其难度主要在于对指针的运用，能够自我实现单链表，对我们代码能力的提升有很大的帮助。当然，在后续的一些数据结构的学习当中，单链表的一些思想是能用上的。</font>

<font color=blue size=4>感谢阅读本小白的博客，错误的地方请严厉指出噢！</font>

标签：单链,pos,pplist,plist,SListNode,数据结构,节点
From： https://blog.51cto.com/u_16019252/6459306

相关文章

  • HBase的数据结构原理与使用
    一、HBase简介HBase是一个开源的、分布式的、版本化的NoSQL数据库（即非关系型数据库），依托Hadoop分布式文件系统HDFS提供分布式数据存储，利用MapReduce来处理海量数据，用Zookeeper作为其分布式协同服务，一般用于存储海量数据。HDFS和HBase的区别在于，HDFS是文件系统，而HBase是数据库。HBa......
  • 《数据结构与算法》之树
    导言：我们在前面的学习中认识到了栈还有队列这些线性的数据存储结构，而现在我们要了解的数据结构却不是线性的了，我们试想线性的结构最大的缺点查询不方便，不管你是从前往后开始查找数据，还是从后往前开始查找数据都是一个一个的比对，效率很低，所以不推荐使用，那么我们的树结构来存储的......
  • 【数据结构】查找
    基本概念查找表 由同一类型的数据元素（记录）构成的集合。所谓集合指记录间不存在前驱后继关系，因此查找表是一种应用灵便的结构。静态查找表 只对查找表做查找操作，即只查询某个记录是否在表中，或只检索某个记录的各种属性。或者说：查找表加上不会使该表的内容发生变化的查找操作，称作......
  • Redis学习笔记4-脚本、持久化和集群 Redis学习笔记1-基础命令及数据结构： http://blog.
        Redis学习笔记4-脚本、持久化和集群Redis学习笔记1-基础命令及数据结构：http://blog.guoyb.com/2016/07/21/learn-redis-basic-commands/Redis学习笔记2-事务与过期时间：http://blog.guoyb.com/2016/08/23/learn-redis-adv/Redis学习笔记3-排序与消息通知：http://blog......
  • 【数据结构】顺序表
    前言<fontcolor=bluesize=4>顺序表作为数据结构中的小小弟，还是很好应付的</font><fontsize=4>。说到数据结构，顺序表是我们的向导，它让你明白数据结构到底是干啥的，为啥数据结构这么的重要。</font></font><fontsize=4>实际上，通讯录的底层就是一个顺序表，里面的增添联系人，删......
  • Redis数据结构：高频面试题及解析
    概述Redis是速度非常快的非关系型（NoSQL）内存键值数据库，可以存储键和五种不同类型的值之间的映射。键的类型只能为字符串，值支持五种数据类型：字符串、列表、集合、散列表、有序集合。Redis支持很多特性，例如将内存中的数据持久化到硬盘中，使用复制来扩展读性能，使用分片来扩展写性能......
  • 《数据结构与算法》之队列与链表复习
    导言：我们在上一次学习了堆栈的数据结构以后，可以了解到它是受限制的操作，比如我们操作只能在栈顶，现在我们要学习的东西叫做队列，它也是受限制的一种数据结构，它的特点是队头只出数据，而队尾只入数据，它的结构就和它的名字，像我们平时排队一样先来的人肯定要先服务啊，所以它的英文叫做Fri......
  • Redis数据结构--SDS动态字符串
    Redis中保存的key是字符串，value往往是字符串或者字符串的集合，但是redis并没有直接使用c语言中的字符串原因在于：1.获取字符串长度需要通过运算2.非二进制安全3.不可修改SDSstructsdshdr{//记录buf数组中使用字节的数量//等于SDS所保存字符串的长度......
  • 大二上 | 数据结构小测试卷
    一共有三张图片：......
  • 大二上 | 数据结构期中试卷
    这是2019级的数据结构期中试卷，老师是汪芸老师。当时考了66分，作业也经常得“F”，留下了深刻的印象……一共有两张图片：......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99