数据结构与算法精解：单链表

本文详细介绍了单链表的实现方法，主要包括以下几个部分：1. 实现思想：单链表是一种线性、动态、非连续存储的数据结构，支持插入、删除、遍历等操作；2. 数据结构设计：定义了结点结构体，包含数据域和指针域；3. 接口函数：实现了初始化、检查、插入（前插/后插）、删除、查找、遍历等20余个核心操作函数；4. 具体实现：提供了带头结点和不带头结点两种实现方式，以及头插法和尾插法两种建立链表的方法。通过详细的函数定义和代码实现，完整展示了单链表的操作逻辑和实现原理。

作者
WildPointer
发布
2024.06.05
专栏
数据结构与算法精解
阅读
约 12 分钟 / 927 次原文浏览

实现思想

单链表是一种基本的数据结构，它由一系列节点组成，每个节点包含两部分：数据部分和指向下一个节点的指针。单链表的特点是每个节点只包含一个指向下一个节点的指针，因此只能从表头向表尾遍历。下面是单链表的一些基本特性和操作：

  1. 线性结构：数据元素之间是一对一的关系。
  2. 动态数据结构：在运行时可以增加或删除节点。
  3. 非连续性：数据元素在内存中不是连续存储的，每个节点通过指针指向下一个节点。
  4. 插入和删除节点：在链表的指定位置插入新节点，删除链表中的指定节点。
  5. 遍历链表：从表头开始，通过每个节点的指针访问下一个节点。
  6. 查找节点：查找链表中特定值的节点。
  7. 反转链表：将链表的节点顺序反转

包含头文件

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

结点设计

cpp
#define Initsize 10typedef int Elemtype; typedef struct {	Elemtype data[Initsize];	//定义数组data大小为Initsize，存储的是静态顺序表的数据	Elemtype* next;				//定义next为Elemtype类型的指针，用于动态扩展顺序表的大小	int Maxsize;				//定义变量Maxsize存储顺序表的大小	int lenth;					//定义变量lenth存储顺序表所存储的数据个数}SqlList;/*以上封装等同于以下代码:typedef struct LNode LNode;typeddf struct LNode* LinkList;*/

接口函数定义

cpp
bool InitList(LinkList& A);			 //定义函数InitList用于初始化不带头结点的单链表bool CheckList(LinkList& A);		 //定义函数CheckList用于查看不带头结点的单链表是否为空bool InitNodeList(LinkList& A);		 //定义函数InitNodeList用于初始化带头结点的单链表bool CheckNodeList(LinkList& A);	 //定义函数CheckNodeList用于查看带头结点的单链表是否为空bool CheckOrder(LinkList& A,int len);//定义函数CheckOrder用于遍历链表查找结点并判空bool InsertNextNode(LNode* A, Elemtype X);//定义函数InsertNextNode用于在指定结点进行后插操作bool ListDelete(LinkList& A, int len, Elemtype X);//定义函数ListDelete用于按位序删除数据bool NodeDelete(LNode* A);          //定义函数NodeDelete用于指定结点删除数据LNode* GetElem(LinkList& A,int len);//定义函数GetElem用于获取结点元素LNode* LocateElem(LinkList& A, Elemtype X);//定义函数LocateElem用于按值查找结点int ListLength(LinkList& A);		//定义函数ListLenth用于查看单链表的长度bool LoopCheckList(LinkList& A);	//定义函数LoopCheckList用于循环遍历输出单链表中的元素//定义函数ListNodeInsert用于在带头结点单链表中执行按位序插入bool ListNodeInsert(LinkList& A,int len,Elemtype X);//定义函数ListInsert用于在不带头结点的单链表中执行按位序插入bool ListInsert(LinkList& A, int len, Elemtype X);//定义函数InsertPriorNode用于在指定结点进行前插操作bool InsertPriorNode(LNode* A, Elemtype X);//定义函数NextManyElemList用于使用尾插法建立多个元素的单链表bool NextManyElemList(LinkList& A);//定义函数PrioeManyElemList用于使用头插法建立多个元素的单链表bool PriorManyElemList(LinkList& A);	/*函数中带有&的形参意义解读:属于CPP文件中的引用，指将指针另取其名，使用时可以引用指针(类似typedef函数)如:LinkList& A ——>将传入的LihkList参数另取其名为A(调用A等同于调用该实参)*/

接口函数实现

cpp
bool LoopCheckList(LinkList& A) {//定义函数LoopCheckList用于循环遍历输出单链表中的元素	LNode* Q = A->next;	printf("单链表中所含的数据为:");	while (Q!=NULL) {					//遍历输出单链表		printf("   %d", Q->data);		Q = Q->next;	}	return true;}bool PriorManyElemList(LinkList& A){    //定义函数PrioeManyElemList用于使用头插法建立多个元素的单链表	int len, J = 0;	LNode* Q = A;	Elemtype X;	printf("请输入要输入的数据个数:");	scanf_s("%d", &len);	printf("请输入数据");	while (J < len) {		scanf_s("%d", &X);		InsertPriorNode(Q, X);//调用函数InsertPriorNode用于在指定结点进行前插操作		printf("\n");		J++;	}	printf("使用头插法建立大小为%d的单链表成功", len);	return true;}bool NextManyElemList(LinkList& A) {						    //定义函数NextManyElemList用于使用尾插法建立多个元素的单链表	int len,J=0;	LNode* Q = A;	Elemtype X;	printf("请输入要输入的数据个数:");	scanf_s("%d", &len);	printf("请输入数据");	while (J < len) {		scanf_s("%d", &X);		InsertNextNode(Q, X);//调用函数InsertNextNode用于在指定结点进行后插操作		Q = Q->next;		printf("\n");		J++;	}	printf("使用尾插法建立大小为%d的单链表成功", len);	return false;}int ListLength(LinkList& A) {//定义函数ListLenth用于查看单链表的长度	LNode* Q = A;			 //定义LNode指针指向头指针所含的指针域	int len = 0;			 //定义变量len存储单链表长度	while (Q->next != NULL) {//遍历单链表		Q = Q->next;		len++;	}	return len;}LNode* LocateElem(LinkList& A,Elemtype X) {	//定义函数LocateElem用于按值查找结点	LNode* Q = A->next;						//定义LNode指针指向头指针所含的指针域	while (Q != NULL && Q->data != X) {		//遍历单链表，寻找数据域为X的结点		Q = Q->next;	}	if (Q == NULL) {						//判断单链表中是否存在满足条件的结点		printf("不存在数据域为%d的结点", X);	}	else {		return Q;	}}LNode* GetElem(LinkList& A,int len) {		//定义函数GetElem用于获取结点元素	if (len < 0) {							//判断传入的结点是否有误			printf("输入的结点次序有误");		return A;	}	LNode* Q = A;							//定义LNode指针指向传入的头指针	int J = 0;	while (Q != NULL && J < len) {			//遍历单链表寻找传入次序的结点		Q = Q->next;		J++;	}	return Q;}bool NodeDelete(LNode* A) {					//定义函数NodeDelete用于指定结点删除数据	if (A == NULL) {		printf("传入的结点不存在");		return false;	}	if (A->next == NULL) {		printf("传入的结点为最后一个结点，需要遍历单链表才能删除该结点");		return false;	}	LNode* Q = A->next;	A->data == Q->data;	A->next = Q->next;	free(Q);	printf("传入的结点已删除");	return true;}bool ListDelete(LinkList& A, int len, Elemtype X) {//定义函数ListDelete用于按位序删除数据	LNode* Q = A;							//定义一个LNode指针Q指向传入的单链表A	if (CheckOrder(Q, len)) {				//调用函数CheckOrder寻找传入次序的前驱结点		if (Q->next == NULL) {				//查看其传入的结点的前驱结点里的指针域next是否为空			printf("输入的结点不存在");			return false;		}		LNode* W = Q ->next;				//定义一个LNdoe指针W指向前驱结点的指针域next		X = W->data;						//获取删除的结点的数据域data		Q->next = W->next;					//更新前驱结点的数据域next		printf("指定次序的单链表已删除，其删除的数据域为:%d", X);		free(W);							//使用函数free释放删除的结点空间		return true;	}	else {		return false;	}}bool InsertPriorNode(LNode* A, Elemtype X) {    //定义函数InsertPriorNode用于在指定结点进行前插操作	if (CheckList(A)) {					//判断插入的结点是否为空		printf("传入的结点不存在");		return false;	}	LNode* Q = (LNode*)malloc(sizeof(LNode));		//向计算机申请一个大小为LNode的空间	if (CheckList(Q)) {					//判断使用malloc1函数是否申请到空间		printf("计算机内存不足，无法分配空间创建链表插入");		return false;	}	Q->data = X;					//进行单链表的前插操作，并更新数据	Q->next = A->next;	A->next = Q;	printf("在指定结点前执行前插操作成功，其数据域保存的数据为%d", X);	return true;}bool InsertNextNode(LNode *A, Elemtype X) {//定义函数InsertNextNode用于在指定结点进行后插入	if (CheckList(A)) {					//判断插入的结点是否为空		printf("传入的结点不存在");		return false;	}	LNode* Q = (LNode*)malloc(sizeof(LNode));		//向计算机申请一个大小为LNode的空间	if (CheckList(Q)) {					//判断使用malloc1函数是否申请到空间		printf("计算机内存不足，无法分配空间创建链表插入");		return false;	}	Q->next = A->next;					//进行单链表的后插操作，并更新数据	A->next = Q;	Q->data = X;	printf("在指定结点后执行后插入成功，其数据域保存的数据为%d", X);	return true;}bool ListInsert(LinkList& A, int len, Elemtype X) {    //定义函数ListInsert用于在不带头结点的单链表中执行按位序插入	if (len == 1) {				//传入的次序为1的情况		LNode* W = (LNode*)malloc(sizeof(LNode));		W->next = A;					W->data = X;		A = W;					//更新头指针指向的地址		printf("在次序%d中插入单链表成功，其存储的数据为%d", len, X);		return true;	}	ListNodeInsert(A,len,X);	//调用函数ListNodeInsert执行后插操作}bool ListNodeInsert(LinkList& A, int len, Elemtype X) {				    //定义函数ListNodeInsert用于在单链表中执行按位序插入	LNode* Q = A;					//定义一个LNode指针Q指向传入的单链表A	if (CheckOrder(Q, len)) {		//调用函数CheckOrder寻找传入次序的前驱结点		LNode* W = (LNode*)malloc(sizeof(LNode));	//定义LNode指针W指向新开辟的大小为LNode的空间		W->data = X;				//更新单链表数据		W->next = Q->next;		Q->next = W;		printf("在次序%d中插入单链表成功，其存储的数据为%d", len, X);		return true;	}	else {		return false;	}}bool CheckOrder(LinkList& A, int len) {//定义函数CheckOrder用于遍历链表查找结点并判空	if (len < 1) {				//判断传入的次序是否合法		printf("传入的次序过小");		return false;	}	LNode* W = A;					//定义一个LNode型的指针存储传入的头结点地址	int J = 0;					//定义变量J用于循环便利单链表	while (W != NULL && J < len - 1) {			//遍历单链表，寻找满足该次序的前驱结点		W = W->next;		J++;	}	if (W == NULL) {			//判断传入的次序是否合法		printf("传入的次序过大");		return false;	}	A = W;						//改变传入的单链表A指向的地址}bool CheckNodeList(LinkList& A) {//定义函数CheckNodeList用于查看带头结点的单链表是否为空	return (A->next == NULL);}bool InitNodeList(LinkList& A) {			//定义函数InirNodeList用于初始化带头结点的单链表	A = (LNode*)malloc(sizeof(LNode));		//使用函数malloc向计算机申请一片大小为LNode类型的空间，将其地址强转为LNode型	if (CheckList(A)) {						//判断申请的空间是否成功		printf("计算机内存不足，初始化带头结点的单链表失败");		return false;	}	A->next = NULL;							//将头结点所含的指针域next值指向空(头结点不存储数据域data)	printf("初始化带头结点的单链表成功");	return true;}bool CheckList(LinkList& A) {//定义函数CheckList用于查看链表是否为空	return (A == NULL);	}bool InitList(LinkList& A) {//定义函数InitList用于初始化不带头结点的单链表	A = NULL;				//将传入的单链表A赋值为NULL，意为课表	printf("初始化不带头结点的单链表成功\n");	return true;}
1次原文点赞；这里的喜欢仅保存在本机
WildPointer

专注系统编程、工程实践与底层技术，记录 C++、Qt、OpenCV 与 VTK 的学习和实践。