1. Toy模板网首页
  2. > Toy博客

单链表（数据结构）(C语言)

8月前 作者：outdated_socks 分类：Toy博客 阅读(64) 违法举报

这篇具有很好参考价值的文章主要介绍了单链表（数据结构）(C语言)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

这里特指无哨兵位单向非循环链表

目录

背景

概念

单链表的实现

前景提示

单链表的结构体定义

单链表的打印

关于为什么不断言phead

关于单链表的逻辑结构和物理结构

单链表的尾插

关于为什么要用到二级指针

关于尾插的本质

关于找尾整个过程的解释

关于为什么打印单链表就不需要传二级指针

单链表的动态申请结点

单链表的头插

单链表的尾删

单链表的头删

链表的查找

单链表在pos位置之前插入x(也可以理解为在pos位置插入)

单链表删除pos位置之前的值(也可以理解为删除pos位置的值)

单链表在pos位置之后插入x 

单链表删除pos位置之后的值

关于不传头指针如何在pos前插入/删除（巧思）

单链表的销毁

总代码（想直接看结果的可以看这里）

背景

上一篇文章我们学习了顺序表。

但顺序表要求的是连续的物理空间，这就导致了其有以下几个缺点：

1. 中间/头部的插入删除，时间复杂度为O(N)。
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
为了更好地解决以上问题，我们就引申出了链表。

概念

链表是一种 物理存储结构上非连续、非顺序的存储结构，数据元素的 逻辑顺序是通过链表 中的 指针链接次序实现的 。链表中一个数据存一个内存块。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的 数据域，另一个是存储下一个结点地址的 指针域。
单链表是一种链式存取的数据结构，用一组 地址任意的存储单元（这组存储单元既可以是连续的，也可以是不连续的）存放线性表中的数据元素。链表中的数据是以 结点( 每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。)来表示的，每个结点的构成: 元素+指针，元素就是存储数据的 存储单元，指针就是连接每个结点的 地址数据。
单链表中每个结点的存储地址是存放在其前趋结点 next 域中，而开始结点无前趋，故设头指针head指向开始结点。链表由头指针 唯一确定，单链表可以用头指针的名字来命名，终端结点无后继，故终端结点的指针域为空，即NULL。

单链表的实现

前景提示

SList.h  用于  引用的头文件、单链表的定义、函数的声明。

SList.c  用于  函数的定义。

Test.c    用于  链表功能的测试。

单链表的结构体定义

单链表（数据结构）(C语言)

在SList.h下

#pragma once//使同一个文件不会被包含(include)多次,不必担心宏名冲突

//先将可能使用到的头文件写上
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLTDataType;//假设结点的数据域类型为 int

//单链表的结构体定义
typedef struct SListNode
{
	SLTDataType data;//结点的数据域，用来存储数据元素
	struct SListNode* next;//结点的指针域，用来存储下一个结点地址的指针域
    //next的意思就是下一个结点的指针，上一个结点存的是下一个结点的地址
    //每个结点都是结构体指针类型
	//有些人会把上一行代码写成SListNode* next;这是不对的，因为C语言中 
    //struct SListNode 整体才是一个类型(但C++可以)
	//或者写成SLTNode* next;这也是错的，因为编译器的查找规则是从上忘下找
}SLTNode;

单链表的打印

要理解单链表，首先我们先写一个单链表的打印。

在SList.h下

//链表的打印——助于理解链表
void SLTPrint(SLTNode* phead);
在SList.c下 
#include "SList.h"//别忘了

//链表的打印
void SLTPrint(SLTNode* phead)
{
	//assert(phead);这里并不需要断言phead不为空
	//为什么这里不需要断言phead？
	//空链表可以打印，即phead==NULL可以打印，直接断言就不合适了
	//那空顺序表也可以打印，那它为什么就要断言呢？
	//因为phead是指向第一个存有数据的结点的
	//而顺序表的ps是指向一个结构体
	SLTNode* cur = phead;//将phead赋值给cur，所以cur也指向第一个结点
	while (cur != NULL)//或while(cur)
	{
		printf("%d->", cur->data);//打印的时候加了个箭头更方便理解
		cur = cur->next;//next是下一个结点的地址
		//++cur/cur++;这种是不行的，指针加加，加到的是连续的下一个位置
		//链表的每一个结点都是单独malloc出来的，我们不能保证结点之间的地址是连续的
	}
	printf("NULL\n");
}

关于为什么不断言phead

单链表（数据结构）(C语言)

单链表（数据结构）(C语言)

关于单链表的逻辑结构和物理结构

单链表（数据结构）(C语言)

                     单链表（数据结构）(C语言)

                     单链表（数据结构）(C语言)

                   单链表（数据结构）(C语言)

单链表（数据结构）(C语言)                     

在打印之前，我们得先有数据

单链表的尾插

在SList.h下

// 单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//用二级指针，解释看下文,x为要插入的数据

关于为什么要用到二级指针

单链表（数据结构）(C语言)

单链表（数据结构）(C语言)

在SList.c下

// 单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);//pphead是plist的地址，不能为空
    //注意区分几个断言的判断，plist有可能是空，pphead一定不能为空

	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//先创建个结点
	if (newnode == NULL)//如果malloc失败
	{
		perror("malloc fail");
		return;
	}
	//如果malloc成功
	newnode->data = x;//插入的数据
	newnode->next = NULL;//初始化为空
	//找尾(尾插之前先找到尾)
	if (*pphead == NULL)//若链表为空
	{
		*pphead = newnode;
	}
	else//若链表不为空
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)//对于不为空的链表：尾插的本质
                                  //是原尾结点要存新尾结点的地址
		{
			tail = tail->next;
		}
		tail->next = newnode;
		/*有些同学会写成:
		while (tail != NULL)
		{
			tail = tail->next;
		}
		tail = newnode;*/
	}
}

关于尾插的本质

单链表（数据结构）(C语言)

 单链表（数据结构）(C语言)

 而

单链表（数据结构）(C语言)

关于找尾整个过程的解释

单链表（数据结构）(C语言)

↓

 单链表（数据结构）(C语言)

 ↓

单链表（数据结构）(C语言)

在Test.c下

#include "SList.h"//别忘了

//用于函数功能的测试
void TestSList1()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);

	SLTPrint(plist);
}

int main()
{
	TestSList1();
	return 0;
}

单链表（数据结构）(C语言)

关于为什么打印单链表就不需要传二级指针

因为打印单链表没有改变指针。如果要改变传过去的指针(实参)，那就要传实参的地址，不改变就不传。

单链表的动态申请结点

要写头插时，我们发现不管是尾插和头插都要动态申请一个结点，所以我们可以先写一个函数来复用。

在SList.c下

// 动态申请一个结点
SLTNode* BuySLTNode(SLTDataType x)
{
	//同样不需要断言
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//先创建个结点
	if (newnode == NULL)//如果malloc失败
	{
		perror("malloc fail");
		return NULL;
	}
	//如果malloc成功
	newnode->data = x;//插入的数据
	newnode->next = NULL;//初始化为空

	return newnode;//返回newnode
}

// 单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);//pphead是plist的地址，不能为空

	SLTNode* newnode = BuySLTNode(x);
	//找尾(尾插之前先找到尾)
	if (*pphead == NULL)//若链表为空
	{
		*pphead = newnode;
	}
	else//若链表不为空
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
        //对于不为空的链表：尾插的本质是原尾结点要存新尾结点的地址
		{
			tail = tail->next;
		}
		tail->next = newnode;
		/*有些同学会写成:
		while (tail != NULL)
		{
			tail = tail->next;
		}
		tail = newnode;*/
	}
}

单链表的头插

 在SList.h下

// 单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);

在SList.c下

单链表（数据结构）(C语言)

// 单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	//发现plist不管是否为空,头插的方法都一样
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

在Test.c下

void TestSList1()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);

	SLTPrint(plist);
}

void TestSList2()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);

	SLTPrint(plist);
}


int main()
{
	TestSList1();
	TestSList2();
	return 0;
}

单链表（数据结构）(C语言)

单链表的尾删

尾删是否需要二级指针？要！

在SList.h下

// 单链表的尾删
void SLTPopBack(SLTNode** pphead);

在Test.c下

void TestSList2()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);
}


int main()
{
	TestSList2();
	return 0;
}

在SList.c下

有些人一开始会这样写：

// 单链表的尾删
void SLTPopBack(SLTNode** pphead)
{
    assert(pphead);//pphead是plist的地址，不能为空

	SLTNode* tail = *pphead;
	while (tail->next != NULL)
	{
		tail = tail->next;
	}
	
	free(tail);
	tail = NULL;
}

结果是：

单链表（数据结构）(C语言)

出现随机值——>很有可能是因为野指针。

 单链表（数据结构）(C语言)→单链表（数据结构）(C语言)

 为什么呢？

单链表（数据结构）(C语言)

这里给更改后的SList.c的两种方法

法一：

单链表（数据结构）(C语言)

// 单链表的尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);//pphead是plist的地址，不能为空

    //法一：
	SLTNode* prev=NULL;
	SLTNode* tail = *pphead;
	while (tail->next != NULL)
	{ 
		prev = tail;
		tail = tail->next;
	}
	
	free(tail);
	tail = NULL;
	
	prev->next = NULL;
}

法二：

单链表（数据结构）(C语言)

// 单链表的尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);//pphead是plist的地址，不能为空

	//法二：
	SLTNode* tail = *pphead;
	while (tail->next->next != NULL)
	{
		tail = tail->next;
	}

	free(tail->next);
	tail->next = NULL;
}

单链表（数据结构）(C语言)

 但是我们再多测试几组

在Test.c下

void TestSList2()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);

    //尾删四个数据
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
}


int main()
{
	TestSList2();
	return 0;
}

结果：

单链表（数据结构）(C语言)两方法最后都还剩一个！

原因是未考虑到只有一个结点或没有结点的情况。

单链表（数据结构）(C语言)

这里是再次更改后的SList.c

// 单链表的尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);//pphead是plist的地址，不能为空

	//检查有无结点
	assert(*pphead != NULL);
	//1.只有一个结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//2.有多个结点
		/*//法一：
		SLTNode* prev=NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}

		free(tail);
		tail = NULL;

		prev->next = NULL;*/
		//法二：
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;
	}
}

只有一个结点单链表（数据结构）(C语言)

没有结点单链表（数据结构）(C语言) 

单链表的头删

在SList.h下

// 单链表头删
void SLTPopFront(SLTNode** pphead);

在SList.c下

单链表（数据结构）(C语言)

// 单链表头删
void SLTPopFront(SLTNode** pphead)
{
	//检查有无结点
	assert(*pphead != NULL);

	SLTNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}

在Test.c下

TestSList3()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
}

int main()
{
	TestSList3();
	return 0;
}

单链表（数据结构）(C语言)

链表的查找

在SList.h下

// 单链表查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

在SList.c下

// 单链表查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;//用cur去遍历,不用phead
	while (cur)//找x
	{
		if (cur->data == x)//如果找到了
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;//如果找不到
}

在Test.c下

void TestSList4()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	//将寻找和修改结合
	//eg:值为2的结点*2
	SLTNode* ret = SLTFind(plist, 2);
	ret->data *= 2;
	SLTPrint(plist);
}


int main()
{
	TestSList4();
	return 0;
}

单链表（数据结构）(C语言)

单链表在pos位置之前插入x(也可以理解为在pos位置插入)

在SList.h下

//单链表在pos位置之前插入x(效率较低)(得传头指针)(也可以理解为在pos位置插入)
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x);

在SList.c下

单链表（数据结构）(C语言)

//单链表在pos位置之前插入x(也可以理解为在pos位置插入)
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);//pphead是plist的地址，不能为空

	assert(pos);//默认pos一定会找到
	if (pos == *pphead)//如果pos在第一个位置——那就是头插
	{
		SLTPushFront(pphead, x);
	}
	else//如果pos不是第一个位置
	{
		//找到pos的前一个位置
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

在Test.c下

TestSList5()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	//寻找值为2的结点
	SLTNode* ret = SLTFind(plist, 2);
	SLTInsertBefore(&plist, ret, 20);//在该结点前插入值为20的结点
	SLTPrint(plist);

}

int main()
{
	TestSList5();
	return 0;
}

单链表（数据结构）(C语言)

单链表删除pos位置之前的值(也可以理解为删除pos位置的值)

在SList.h下

// 单链表删除pos位置之前的值(效率较低)(得传头指针)(也可以理解为删除pos位置的值)
void SLTEraseBefore(SLTNode** pphead, SLTNode* pos);

在SList.c下

// 单链表删除pos位置之前的值(也可以理解为删除pos位置的值)
void SLTEraseBefore(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)//如果pos在第一个位置
	{
		SLTPopFront(pphead);//头删
	}
	else//如果不在第一个位置
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		//pos = NULL;形参的改变不影响实参,加不加这句话都可以
	}
}

在Test.c下

TestSList6()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	//寻找值为2的结点
	SLTNode* ret = SLTFind(plist, 2);
	SLTEraseBefore(&plist, ret);
	ret = NULL;//一般在这里置空
	SLTPrint(plist);
}

int main()
{
	TestSList6();
	return 0;
}

单链表（数据结构）(C语言)

单链表在pos位置之后插入x 

在SList.h下

// 单链表在pos位置之后插入x,单链表比较适合这种
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

在SList.c下

有些人会这样写：

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

后果：

单链表（数据结构）(C语言)

 所以橙色和紫色的两步应该互换位置

更改后的SList.c

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

在Test.c下

TestSList7()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTNode* ret = SLTFind(plist, 2);
	SLTInsertAfter(ret, 20);
	SLTPrint(plist);
}

int main()
{
	TestSList7();
	return 0;
}

单链表（数据结构）(C语言)

单链表删除pos位置之后的值

在SList.h下

// 单链表删除pos位置之后的值,单链表比较适合这种
void SLTEraseAfter(SLTNode* pos);

在SList.c下

单链表（数据结构）(C语言)

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

	SLTNode* del = pos->next;//保存要删除的结点
	pos->next = pos->next->next;//或者写成pos->next=del->next;
	free(del);
	del = NULL;
}

在Test.c下

TestSList8()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTNode* ret = SLTFind(plist, 2);
	SLTEraseAfter(ret);
	SLTPrint(plist);
}

int main()
{
	TestSList8();
	return 0;
}

关于不传头指针如何在pos前插入/删除（巧思）

插入：先利用单链表在pos位置之后插入x的函数,再交换pos和pos->next的值。

单链表（数据结构）(C语言)

在SList.h下

// 不传头指针,在pos前插入x(也可以理解为在pos位置插入)
void SLTInsertBefore1(SLTNode* pos, SLTDataType x);

在SList.c下

// 不传头指针,在pos前插入x(也可以理解为在pos位置插入)
void SLTInsertBefore1(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	//调用单链表在pos位置之后插入x的函数
	SLTInsertAfter(pos, x);
	
	//交换pos和pos->next的值
	SLTDataType temp;
	temp = pos->data;
	pos->data = pos->next->data;
	pos->next->data = temp;
}

在Test.c下

TestSList9()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTNode* ret = SLTFind(plist, 2);
	SLTInsertBefore1(ret,20);
	SLTPrint(plist);
}

int main()
{
	TestSList9();
	return 0;
}

删除：先将pos->next的值赋给pos,再利用单链表删除pos位置之后的值的函数。(但此方法不能尾删)

单链表（数据结构）(C语言)在SList.h下

// 不传头指针,删除pos位置之前的值(也可以理解为删除pos位置的值)
void SLTEraseBefore1(SLTNode* pos);

在SList.c下

// 不传头指针,删除pos位置之前的值(也可以理解为删除pos位置的值)
void SLTEraseBefore1(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);//不能尾删
	
	SLTNode* del = pos->next;
	pos->data = pos->next->data;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}

在Test.c下

TestSList10()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTNode* ret = SLTFind(plist, 2);
	SLTEraseBefore1(ret);
	SLTPrint(plist);
}

int main()
{
	TestSList10();
	return 0;
}

单链表（数据结构）(C语言)

单链表的销毁

方法一(不传二级指针):

在SList.h下

// 单链表的销毁,不传二级
void SLTDestroy(SLTNode* phead);

在SList.c下

// 单链表的销毁
void SLTDestroy(SLTNode* phead)
{
	SLTNode* cur = phead;
	/*//有些人一开始会这样写
	while (cur)
	{
		//free不是销毁这个指针指向的内存,而是将指针指向的内存还给操作系统
		free(cur);//cur依旧指向free之前的地址
		cur = cur->next;
	}*/

	while (cur)
	{
		SLTNode* tmp = cur->next;
		free(cur);
		cur = tmp;
	}
}

在Test.c下

TestSList11()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTDestroy(plist);
	plist = NULL;
}


int main()
{
	TestSList11();
	return 0;
}

方法二(传二级指针):

在SList.h下

// 单链表的销毁,传二级
void SLTDestroy1(SLTNode** pphead);

在SList.c下

// 单链表的销毁,传二级
void SLTDestroy1(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	*pphead = NULL;
}

在Test.c下

TestSList12()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTDestroy1(&plist);
	SLTPrint(plist);
}

int main()
{
	TestSList12();
	return 0;
}

总代码（想直接看结果的可以看这里）

在SList.h下

#pragma once//使同一个文件不会被包含(include)多次,不必担心宏名冲突

//先将可能使用到的头文件写上
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLTDataType;//假设结点的数据域类型为 int

// 单链表的结构体定义
//		↓结点  单链表 Singly Linked List
typedef struct SListNode
{
	SLTDataType data;//结点的数据域,用来存储数据元素
	struct SListNode* next;//结点的指针域，用来存储下一个结点地址的指针域
	//next的意思就是下一个结点的指针，上一个结点存的是下一个结点的地址
	//每个结点都是结构体指针类型
	//有些人会把上一行代码写成SListNode* next;
    //这是不对的，因为C语言中 struct SListNode 整体才是一个类型(但C++可以)
	//或者写成SLTNode* next;这也是不对的,因为编译器的查找规则是从上忘下找
}SLTNode;


// 链表的打印——助于理解链表
void SLTPrint(SLTNode* phead);

// 单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);//用二级指针,x为要插入的数据

// 单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);

// 单链表的尾删
void SLTPopBack(SLTNode** pphead);

// 单链表头删
void SLTPopFront(SLTNode** pphead);

// 单链表查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

// 单链表在pos位置之前插入x(效率较低)(得传头指针)(也可以理解为在pos位置插入)
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x);

// 单链表删除pos位置之前的值(效率较低)(得传头指针)(也可以理解为删除pos位置的值)
void SLTEraseBefore(SLTNode** pphead, SLTNode* pos);

// 单链表在pos位置之后插入x,单链表比较适合这种
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

// 单链表删除pos位置之后的值,单链表比较适合这种
void SLTEraseAfter(SLTNode* pos);

// 不传头指针,在pos前插入x(也可以理解为在pos位置插入)
void SLTInsertBefore1(SLTNode* pos, SLTDataType x);

// 不传头指针,删除pos位置之前的值(也可以理解为删除pos位置的值)
void SLTEraseBefore1(SLTNode* pos);

// 单链表的销毁,不传二级
void SLTDestroy(SLTNode* phead);

// 单链表的销毁,传二级
void SLTDestroy1(SLTNode** pphead);

在SList.c下

#include"SList.h"//别忘了

//链表的打印
void SLTPrint(SLTNode* phead)
{
	//assert(phead);这里并不需要断言phead不为空
	//为什么这里不需要断言？
	//空链表可以打印，即phead==NULL可以打印，直接断言就不合适了
	//那空顺序表也可以打印，那它为什么就要断言呢？
	//因为phead是指向第一个存有数据的结点的
	//而顺序表的ps是指向一个结构体
	SLTNode* cur = phead;//将phead赋值给cur，所以cur也指向第一个结点
	while (cur != NULL)//或while(cur)
	{
		printf("%d->", cur->data);//打印的时候加了个箭头更方便理解
		cur = cur->next;//next是下一个结点的地址
		//++cur/cur++;这种是不行的，指针加加，加到的是连续的下一个位置
		//链表的每一个结点都是单独malloc出来的，我们不能保证结点之间的地址是连续的
	}
	printf("NULL\n");
}

// 动态申请一个结点
SLTNode* BuySLTNode(SLTDataType x)
{
	//同样不需要断言
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//先创建个结点
	if (newnode == NULL)//如果malloc失败
	{
		perror("malloc fail");
		return NULL;
	}
	//如果malloc成功
	newnode->data = x;//插入的数据
	newnode->next = NULL;//初始化为空

	return newnode;//返回newnode
}

// 单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);//pphead是plist的地址，不能为空
	//注意区分几个断言的判断，plist有可能是空，pphead一定不能为空

	SLTNode* newnode = BuySLTNode(x);
	//找尾(尾插之前先找到尾)
	if (*pphead == NULL)//若链表为空
	{
		*pphead = newnode;
	}
	else//若链表不为空
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
        //对于不为空的链表：尾插的本质是原尾结点要存新尾结点的地址
		{
			tail = tail->next;
		}
		tail->next = newnode;
		/*有些同学会写成:
		while (tail != NULL)
		{
			tail = tail->next;
		}
		tail = newnode;*/
	}
}


// 单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);//pphead是plist的地址，不能为空

	//发现plist不管是否为空,头插的方法都一样
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

// 单链表的尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);//pphead是plist的地址，不能为空

	//检查有无结点
	assert(*pphead != NULL);//或者写成assert(*pphead);
	//1.只有一个结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//2.有多个结点
		/*//法一：
		SLTNode* prev=NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}

		free(tail);
		tail = NULL;

		prev->next = NULL;*/
		//法二：
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;
	}
}

// 单链表头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);//pphead是plist的地址，不能为空

	//检查有无结点
	assert(*pphead != NULL);

	SLTNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}

// 单链表查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;//用cur去遍历,不用phead
	while (cur)//找x
	{
		if (cur->data == x)//如果找到了
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;//如果找不到
}

//单链表在pos位置之前插入x(也可以理解为在pos位置插入)
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);//默认pos一定会找到
	assert(pphead);//pphead是plist的地址，不能为空
	if (pos == *pphead)//如果pos在第一个位置——那就是头插
	{
		SLTPushFront(pphead, x);
	}
	else//如果pos不是第一个位置
	{
		//找到pos的前一个位置
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

// 单链表删除pos位置之前的值(也可以理解为删除pos位置的值)
void SLTEraseBefore(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)//如果pos在第一个位置
	{
		SLTPopFront(pphead);//头删
	}
	else//如果不在第一个位置
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		//pos = NULL;形参的改变不影响实参,加不加这句话都可以
	}
}

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

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

	SLTNode* del = pos->next;//保存要删除的结点
	pos->next = pos->next->next;//或者写成pos->next=del->next;
	free(del);
	del = NULL;
}

// 不传头指针,在pos前插入x(也可以理解为在pos位置插入)
void SLTInsertBefore1(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	//调用单链表在pos位置之后插入x的函数
	SLTInsertAfter(pos, x);

	//交换pos和pos->next的值
	SLTDataType temp;
	temp = pos->data;
	pos->data = pos->next->data;
	pos->next->data = temp;
}

// 不传头指针,删除pos位置之前的值(也可以理解为删除pos位置的值)
void SLTEraseBefore1(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);//不能尾删

	SLTNode* del = pos->next;
	pos->data = pos->next->data;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}

// 单链表的销毁
void SLTDestroy(SLTNode* phead)
{
	SLTNode* cur = phead;
	/*//有些人一开始会这样写
	while (cur)
	{
		//free不是销毁这个指针指向的内存,而是将指针指向的内存还给操作系统
		free(cur);//cur依旧指向free之前的地址
		cur = cur->next;
	}*/

	while (cur)
	{
		SLTNode* tmp = cur->next;
		free(cur);
		cur = tmp;
	}
}

// 单链表的销毁,传二级
void SLTDestroy1(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	*pphead = NULL;
}

在Test.c下

#include"SList.h"

void TestSList1()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);

	SLTPrint(plist);
}

void TestSList2()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
}

TestSList3()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
}

void TestSList4()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	//将寻找和修改结合
	//eg:值为2的结点*2
	SLTNode* ret = SLTFind(plist, 2);
	ret->data *= 2;
	SLTPrint(plist);
}

TestSList5()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	//寻找值为2的结点
	SLTNode* ret = SLTFind(plist, 2);
	SLTInsertBefore(&plist, ret, 20);//在该结点前插入值为20的结点
	SLTPrint(plist);

}

TestSList6()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	//寻找值为2的结点
	SLTNode* ret = SLTFind(plist, 2);
	SLTEraseBefore(&plist, ret);
	ret = NULL;//一般在这里置空
	SLTPrint(plist);
}

TestSList7()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTNode* ret = SLTFind(plist, 2);
	SLTInsertAfter(ret, 20);
	SLTPrint(plist);
}

TestSList8()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTNode* ret = SLTFind(plist, 2);
	SLTEraseAfter(ret);
	SLTPrint(plist);
}

TestSList9()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTNode* ret = SLTFind(plist, 2);
	SLTInsertBefore1(ret, 20);
	SLTPrint(plist);
}

TestSList10()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTNode* ret = SLTFind(plist, 2);
	SLTEraseBefore1(ret);
	SLTPrint(plist);
}

TestSList11()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTDestroy(plist);
	plist = NULL;
}

TestSList12()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);

	SLTDestroy1(&plist);
	SLTPrint(plist);
}

int main()
{
	//TestSList1();
	//TestSList2();
	//TestSList3();
	//TestSList4();
	//TestSList5();
	//TestSList6();
	//TestSList7();
	//TestSList8();
	//TestSList9();
	//TestSList10();
	//TestSList11();
	TestSList12();
	return 0;
}

欢迎指正❀文章来源地址https://www.toymoban.com/news/detail-421011.html

到了这里，关于单链表（数据结构）(C语言)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 单链表（数据结构）(C语言)

    单链表（数据结构）(C语言)

    这里特指无哨兵位单向非循环链表 目录 背景 概念 单链表的实现 前景提示 单链表的结构体定义 单链表的打印 关于为什么不断言phead 关于单链表的逻辑结构和物理结构 单链表的尾插 关于为什么要用到二级指针 关于尾插的本质 关于找尾整个过程的解释 关于为什么打印单链表

    2023年04月22日
    浏览(64)
  • 单链表—C语言实现数据结构

    单链表—C语言实现数据结构

    本期带大家一起用C语言实现单链表🌈🌈🌈 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的；简单来说，线性表的链式存储结构生成的表，称作“链表”。 每个元素本身由两部分组成： 1、本身的信息，称为

    2024年02月07日
    浏览(64)
  • C语言：数据结构之单链表（三）

    C语言：数据结构之单链表（三）

    上篇谈了谈尾插法和头插法，这篇谈谈中间插入元素和删除。 1、中间插入元素 既然谈到了要从中间插入那就得确定插入的位置是否合法了，我总不能链表总长为5，但是插入的位置是60，这就不对了。所以得先确定这个链表的长度为多少。这个比较简单，就是在寻找尾部的过

    2024年02月13日
    浏览(33)
  • ＜数据结构＞ 链表 - 单链表（c语言实现）

    ＜数据结构＞ 链表 - 单链表（c语言实现）

    哨兵位结点也叫哑节点。哨兵位结点 也是头结点 。该节点 不存储有效数据，只是为了方便操作 （如尾插时用带哨兵位的头结点很爽，不需要判空）。 有哨兵位结点的链表，第一个元素应该是链表第二个节点（head - next，head为哨兵位结点）对应的元素。 有哨兵位结点的链表

    2023年04月11日
    浏览(29)
  • C语言：数据结构之单链表（一）

    C语言：数据结构之单链表（一）

    当初刚开始学单链表学的是一头雾水，简直就是彻头彻尾灾难，一塌糊涂，过段时间后经过自己的重新认真思考再结合小练习明白了它是怎么个回事儿。 1、首先从它的逻辑上入手，对他有大体认知。 简单来说就是一个一个有方向小块儿连在一起，好像疫情期间大家排队做核

    2024年02月12日
    浏览(67)
  • C语言：数据结构之单链表（二）

    C语言：数据结构之单链表（二）

    上一篇随笔谈了谈单链表是什么东西，然后进行了初始化，这篇随笔就开始对其进行操作了，首先是增，删，改，查的增。 增，顾名思义就是要增加新的元素，单链表是链式的，那就要考虑怎么去加新元素，有三种，从头部添加，从尾部添加，从中间添加。先说说从尾部添加

    2024年02月12日
    浏览(29)
  • C语言：数据结构之单链表（四）

    C语言：数据结构之单链表（四）

    本篇谈一谈单链表的 改 ，具体操作就是找到他，然后修改元素即可，上一篇有相关代码，可以参考。 改函数代码如下： main函数如下：（修改第6,8,3位） 结果如下：   至此，单链表的增删改查就谈完了，只需理解它的本质是干什么，代码就很好写了。 总结：①改比较简单，

    2024年02月16日
    浏览(30)
  • 数据结构：单链表的实现(C语言)

    数据结构：单链表的实现(C语言)

    个人主页 ： 水月梦镜花 个人专栏 ： 《C语言》 《数据结构》 本博客将要实现的无头单向不循环链表。 我们将节点定义为如下结构： 其成员变量有data，next。 将int重命名为STLDataType，方便我们以后修改数据域的内容。 动态申明一个空间，来放置数据。如下： 将data的内容置

    2024年02月14日
    浏览(36)

  • 【数据结构】C语言实现单链表（带头结点）

    Single linked list with leading nodes 关于不带头结点的单链表：不带头结点的单链表 结点定义： 接口定义： 初始化需要申请头结点，让头指针指向空的头结点。 将申请结点的代码进行封装： 需要越过头结点 找到尾结点，然后插入到尾结点的后面。 对比不带头结点的单链表的尾插

    2024年02月02日
    浏览(63)
  • 【数据结构】—C语言实现单链表（超详细！）

    【数据结构】—C语言实现单链表（超详细！）

                                         食用指南：本文在有C基础的情况下食用更佳                                     🔥 这就不得不推荐此专栏了：   C语言                                      ♈️ 今日夜电波：  あなたは煙草

    2024年02月14日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包