单链表

木杉乀

发布于 2021-04-02 02:23:52

5820

发布于 2021-04-02 02:23:52

文章被收录于专栏：木杉の小屋木杉の小屋

单链表

一.什么是单链表

单链表, 双链表, 静态链表, 循环链表…

链表: 链式存储结构, 用于存储逻辑关系为 “一对一” 的数据

与顺序表不同在于: 链表的物理地址是不一定连续的

链表的节点

节点分为: 头结点,尾结点,普通节点,首元节点(详细见图1)

一般由结构体组成一个节点(成员: 数据 , 结构体指针)

节点类型一般都是自定义的

头节点: 第一个节点

尾结点: 最后一个节点

首元节点: 第一个真正存储数据的节点(有时第一个节点并不存储数据,仅仅作为头来使用)

头指针,尾指针

头指针指向头节点,尾指针指向尾节点_头指针是找到链表的关键(详细见图1)

图1:

二单链表的基本操作(C语言代码实现)

一. 创建一个单链表

以图1中的情况2为例编写代码

思路:

首先, 定义一个结构体用来存储节点的相关信息(数据域,指针域)

然后,在创建一个头节点(不存任何数据_哑节点),之后在头节点后面不断添加节点

开始代码实现:

// 方便灵活改变数据类型
typedef int DateType;
// 自定义一个节点类型
struct node
{
	DateType num;           // 数据域
    struct node* pnext;     // 指针域
};
// 给结构体类型取别名
typedef struct node Node;

// **创建一个链表并且给初始值
// 参数: 长度
// 返回值: 头指针
Node* CreateList(int length)
{
	// 判断长度
	if (length <= 0)
	{
		printf("Length Error!\n");
		return NULL;
	}

	// 1 创建头尾两个指针
	Node* phead, * prear;
	phead = prear = NULL; // 初始化防止野指针

	// 2 申请内存, 头节点(哑节点)
	phead = (Node*)malloc(sizeof(Node));

	// 3 处理异常情况
	if (phead == NULL) {
		perror("malloc failed!\n");
		exit(EXIT_FAILURE);
	}
	/*  perror函数和EXIT_FAILURE解释(内容来自C库函数,stdlib.h)
	* 
	*   void perror(const char* _ErrMsg): 用于弹出异常(输出错误描述)
	*   exit(0);   正常执行   结束程序
	*   exit(1);   非正常执行 结束程序
	*   #define EXIT_SUCCESS 0;
	*   #define EXIT_FAILURE 1;
	* 
	*/

	// 4 初始化头节点
	phead->pnext = NULL;   // 没有其他节点暂时指向NULL
	phead->num = 0;        // 按图1情况二所示,头节点不存放数据,随便给个初值

	// 5 初始化尾节点
	prear = phead;         // 初始只有一个节点,头节点也是尾节点

	// 6 通过循环,添加节点
	Node* pNewNode = NULL;
	for (size_t i = 0; i < length; i++)
	{
		// 6.1 申请一个节点,检测是否申请成功,给值
		pNewNode = (Node*)malloc(sizeof(Node));  // malloc如果申请内存失败返回NULL
		if (NULL == pNewNode) {
			perror("malloc failed!\n");
			exit(EXIT_FAILURE);
		}
		int n = 0;
		printf("输入节点数据: ");
		scanf("%d", &n);
		pNewNode->num = n;
		pNewNode->pnext = NULL;

		// 6.2 将节点添加到链表(尾插法)
		prear->pnext = pNewNode; //尾指针指向新节点
		prear = pNewNode;        //更新尾节点
	}
	return phead;
}

二.遍历一个单链表

// **遍历一个单链表
// 参数: 链表头指针
// 返回值: 无
void TraverseList(Node* const pList) {  // 遍历链表不希望被改值加上一个const
    // pList->pnext : 避开哑节点
	Node* ptemp = pList->pnext;
	if (NULL == ptemp) {
		printf("链表为空!\n");
	}
	while (ptemp) {
		printf("%d ", ptemp->num);     //输出
		ptemp = ptemp->pnext;          //移位
	}
    printf("\n");
}

测试:

Node* p = CreateList(5);
TraverseList(p);

三.插入一个元素

思路:先插后拆(如果先拆会找不到节点位置)

// **插入一个节点
// 参数:头指针,位置,值
// 返回值:头指针
Node* InsertElement(Node* pList, Node* Position, int val) {
    //创建
	Node* ptemp = (Node*)malloc(sizeof(Node));    //申请内存
    //判断异常
	if (NULL == ptemp) {
		perror("malloc failed!\n");
		exit(EXIT_FAILURE);
	}
    //初始化并插入
	ptemp->num = val;
	ptemp->pnext = Position->pnext;
	Position->pnext = ptemp;
	return pList;
}

测试:(插入并输出)

Node* p = CreateList(5);                        //创建链表
TraverseList(p);                                //遍历输出
TraverseList(InsertElement(p, p->pnext, 666));  //插入节点+遍历输出  (首元节点后插入:666)
// InsertElement函数返回头指针,所以可以采用链式操作.

四.清空链表

// **清空链表
// 参数:头指针
// 返回值:头指针
Node* DeleteList(Node* pList)
{
    // 保存头节点(由于头节点不保存数据,从首元节点依次释放)
	Node* ptemp = NULL, * pos = NULL;
	pos = pList->pnext;
	pList->pnext = NULL; // 清空pList(只剩头节点(哑节点))
    // 逐一释放内存
	while (pos) {           // 原理与上面保存头节点相同
		ptemp = pos->pnext; // ptemp保存了pos(当前要释放节点)后面的全部节点
		free(pos);          // 释放pos
		pos = ptemp;        // 把ptemp保存的节点还给pos,并继续回到while循环判断直到pos==NULL结束
	}
	return pList;           // 返回指针
}

测试:

Node* p = CreateList(5);      //创建链表
TraverseList(p);              //遍历输出
TraverseList(DeleteList(p));  //清空链表+遍历输出

五.删除节点

按值删除单个节点

一.查找

1.找到删除节点的上一个节点_否则不方便解链（所以遍历搜索时通过->next找到删除元素）

已找到!! TempList指向上一节点

二.连接

三.删除释放

// **按值删除单个节点
// 参数:头指针,值
// 返回值:头指针
Node* DeleteElement(Node* pList, int val) {
	Node* TempList = pList;
	Node* TempNode = NULL;
    //遍历查找
	while (TempList->pnext && TempList->pnext->num != val) {
		TempList = TempList->pnext;
	}
    //判断是否找到
	if (!TempList->pnext) {
		printf("未找到删除元素,%d不存在!!\n", val);
	}
	else {
		TempNode = TempList->pnext;          //对照图示学习
		TempList->pnext = TempNode->pnext;
		free(TempNode);
		// TempList->pnext = TempNode->pnext->pnext; 这样的操作是不行的,堆区没有释放内存;
	}
	return pList;
}

测试:

Node* p = CreateList(5);            //创建链表
TraverseList(p);                    //遍历输出
DeleteElement(p, 9);                //删除节点        (删除第一个元素为9的节点,找不到)
TraverseList(DeleteElement(p, 2));  //删除节点+遍历数组 (删除第一个元素为2的节点)

六.查找节点

// **查找一个节点(按数值)
// 参数:头指针,数值
// 返回值: 目标节点指针
Node* FindElement(Node* pList, int val) {
	Node* ptr = pList->pnext;   //指向首元节点用于遍历

	// 1 判断
	if (NULL == ptr) {
		printf("链表为空!\n");
		return NULL;
	}

	// 2 查找
	while (ptr != NULL && ptr->num != val) {
		ptr = ptr->pnext;  //移位
	}

	// 3 反馈
	if (ptr != NULL) {
		printf("找到 %d 了!\n", ptr->num);
	}
	else {
		printf("未找到 %d !\n",val);
	}
	return ptr;
}

测试:

Node* p = CreateList(5);                                  //创建链表
TraverseList(p);                                          //遍历输出
TraverseList(InsertElement(p, FindElement(p, 4), 666));   //查找节点+插入节点+遍历输出
// 查找4,并在4后面插入666,遍历输出

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wGnkWRQ9-1614408675456)(C:\Users\admin\AppData\Roaming\Typora\typora-user-images\image-20210227144011066.png)]

完整代码

main.c

#include
#include"myList.h"

int main() {
	
	//创建
	Node* p = CreateList(5);
	//遍历
	TraverseList(p);
	//插入
	InsertElement(p, p->pnext, 666);
	//遍历
	TraverseList(p);
	//删一个
	DeleteElement(p, 666);
	//遍历
	TraverseList(p);
	//查找4并在其后插入666并遍历
	TraverseList(InsertElement(p, FindElement(p, 4), 666));
	//清空
	DeleteList(p);
	//遍历
	TraverseList(p);

}

myList.h

#ifndef _MYLIST_ // 添加判断_宏定义 避免重复定义
#define _MYLIST_

// 方便灵活改变数据类型
typedef int DateType;
// 节点结构体
struct node
{
	DateType num;           // 数据域
    struct node* pnext;     // 指针域
};
// 给结构体类型取别名
typedef struct node Node;

// **创建一个链表并且给初始值
// 参数: 长度
// 返回值: 头指针
Node* CreateList(int length);

// **遍历一个单链表
// 参数: 链表头指针
// 返回值: 无
void TraverseList(Node* const pList);

// **插入一个节点
// 参数:头指针,位置,值
// 返回值:头指针
Node* InsertElement(Node* pList, Node* Position, int val);

// **清空链表
// 参数:头指针
// 返回值:头指针
Node* DeleteList(Node* pList);

// **删除单个元素(按数值)
// 参数:头指针,值
// 返回值:头指针
Node* DeleteElement(Node* pList, int val);

// **查找一个节点(按数值)
// 参数:头指针,数值
// 返回值: 目标节点指针
Node* FindElement(Node* pList, int val);

#endif

myList.c

#define _CRT_SECURE_NO_WARNINGS 1   // 解决VS2019 scanf不安全报错问题
#include "myList.h"
#include
#include


// **创建一个链表并且给初始值
// 参数: 长度
// 返回值: 头指针
Node* CreateList(int length)
{
	// 判断长度
	if (length <= 0)
	{
		printf("Length Error!\n");
		return NULL;
	}

	// 1 创建头尾两个指针
	Node* phead, * prear;
	phead = prear = NULL;

	// 2 申请内存, 头节点(哑节点)
	phead = (Node*)malloc(sizeof(Node));

	// 3 处理异常情况
	if (phead == NULL) {
		perror("malloc failed!\n");
		exit(EXIT_FAILURE);
	}
	/*  perror函数和EXIT_FAILURE解释(内容来自C库函数,stdlib.h)
	* 
	*   void perror(const char* _ErrMsg): 用于弹出异常(输出错误描述)
	*   exit(0);   正常执行   结束程序
	*   exit(1);   非正常执行 结束程序
	*   #define EXIT_SUCCESS 0;
	*   #define EXIT_FAILURE 1;
	* 
	*/

	// 4 初始化头节点
	phead->pnext = NULL;
	phead->num = 0;

	// 5 初始化尾节点
	prear = phead;

	// 6 通过循环,添加节点
	Node* pNewNode = NULL;
	for (size_t i = 0; i < length; i++)
	{
		// 6.1 申请一个节点,检测是否申请成功,给值
		pNewNode = (Node*)malloc(sizeof(Node));
		if (NULL == pNewNode) {
			perror("malloc failed!\n");
			exit(EXIT_FAILURE);
		}
		int n = 0;
		printf("输入节点数据: ");
		scanf("%d", &n);
		pNewNode->num = n;
		pNewNode->pnext = NULL;

		// 6.2 将节点添加到链表
		prear->pnext = pNewNode;
		prear = pNewNode;
	}
	return phead;
}

// **遍历一个单链表
// 参数: 链表头指针
// 返回值: 无
void TraverseList(Node* const pList) {
	// pList->pnext : 避开哑节点
	Node* ptemp = pList->pnext;
	if (NULL == ptemp) {
		printf("链表为空!\n");
	}
	while (ptemp) {
		printf("%d ", ptemp->num);
		ptemp = ptemp->pnext;
	}
	printf("\n");
}

// **插入一个节点
// 参数:头指针,位置,值
// 返回值:头指针
Node* InsertElement(Node* pList, Node* Position, int val) {
	Node* ptemp = (Node*)malloc(sizeof(Node));
	if (NULL == ptemp) {
		perror("malloc failed!\n");
		exit(EXIT_FAILURE);
	}
	ptemp->num = val;
	ptemp->pnext = Position->pnext;
	Position->pnext = ptemp;
	return pList;
}

// **清空链表
// 参数:头指针
// 返回值:头指针
Node* DeleteList(Node* pList)
{
	Node* ptemp = NULL, * pos = NULL;
	pos = pList->pnext;
	pList->pnext = NULL;
	while (pos) {
		ptemp = pos->pnext;
		free(pos);
		pos = ptemp;
	}
	return pList;
}

// **按值删除单个节点
// 参数:头指针,值
// 返回值:头指针
Node* DeleteElement(Node* pList, int val) {
	Node* TempList = pList;
	Node* TempNode = NULL;
	while (TempList->pnext && TempList->pnext->num != val) {
		TempList = TempList->pnext;
	}
	if (!TempList->pnext) {
		printf("未找到删除元素,%d不存在!!\n", val);
	}
	else {
		TempNode = TempList->pnext;
		TempList->pnext = TempNode->pnext;
		free(TempNode);
		// TempList->pnext = TempNode->pnext->pnext; //错误
	}
	return pList;
}

// **查找一个节点(按数值)
// 参数:头指针,数值
// 返回值: 目标节点指针
Node* FindElement(Node* pList, int val) {
	Node* ptr = pList->pnext;

	// 1 判断
	if (NULL == ptr) {
		printf("链表为空!\n");
		return NULL;
	}

	// 2 查找
	while (ptr != NULL && ptr->num != val) {
		ptr = ptr->pnext;
	}

	// 3 反馈
	if (ptr != NULL) {
		printf("找到 %d 了!\n", ptr->num);
	}
	else {
		printf("未找到 %d !\n",val);
	}
	return ptr;
}
se {
		TempNode = TempList->pnext;
		TempList->pnext = TempNode->pnext;
		free(TempNode);
		// TempList->pnext = TempNode->pnext->pnext; //错误
	}
	return pList;
}

// **查找一个节点(按数值)
// 参数:头指针,数值
// 返回值: 目标节点指针
Node* FindElement(Node* pList, int val) {
	Node* ptr = pList->pnext;

	// 1 判断
	if (NULL == ptr) {
		printf("链表为空!\n");
		return NULL;
	}

	// 2 查找
	while (ptr != NULL && ptr->num != val) {
		ptr = ptr->pnext;
	}

	// 3 反馈
	if (ptr != NULL) {
		printf("找到 %d 了!\n", ptr->num);
	}
	else {
		printf("未找到 %d !\n",val);
	}
	return ptr;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2021-02-27 ，如有侵权请联系 cloudcommunity@tencent.com 删除

腾讯云测试服务

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

腾讯云测试服务

编程算法

登录后参与评论

0 条评论

热度

单链表

单链表

单链表

一.什么是单链表

链表的节点

头指针,尾指针

二单链表的基本操作(C语言代码实现)

一. 创建一个单链表

二.遍历一个单链表

三.插入一个元素

四.清空链表

五.删除节点

六.查找节点

完整代码

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

单链表

单链表

单链表

一.什么是单链表

链表的节点

头指针,尾指针

二 单链表的基本操作(C语言代码实现)

一. 创建一个单链表

二.遍历一个单链表

三.插入一个元素

四.清空链表

五.删除节点

六.查找节点

完整代码

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

二单链表的基本操作(C语言代码实现)