手把手教你实现一个C++单链表

时间:2022-11-30 小林同志_____ 人气:0

一. 节点声明

链表是一种数据结构，用于数据的存储。

如图，每一个链表节点所在的内存空间是不延续的，因为不是连续存储，所以需要存入下一个节点的地址，这样方便找到下一个数值，而最后一个链表指向的空间为NULL，因此我们可以声明一个结构体，代表一个节点。

typedef int ListDataType;

typedef struct SListNode
{
	ListDataType  data;
	struct SListNode* Next;

}SLNode;

SListNode 是我们的节点结构体，ListDataType是存储数据的类型。

二. 尾插

链表的节点建立好后，接下来我们来进行尾部插入数据。

那么我们只需要找到尾部节点，把尾部节点指向的NULL值置为新节点。新节点指向NULL

因此我们要新建一个节点，然后找到最后一个节点。

void SListPushBack(SLNode** phead, ListDataType x)
{
	//新开辟一个节点
	SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
	if (newNode == NULL)
	{
		//空间开辟失败
		printf("SListPushBack::newNode");
		exit(-1);
	}

	//找到最后一个节点
	SLNode* cru = *phead;
	//如果cru指向NULL，说明cru是最后一个节点
	while (cru->Next != NULL)
	{
		cru = cru->Next;
	}
	//cru 指向新节点
	cru->Next = newNode; 
	//新节点指向NULL，存储数据x
	newNode->data = x;
	newNode->Next = NULL;

}

但是这种方法，我们需要注意一种情况，那就是如果链表中本身没有节点，那么cru初始就是一个空指针，而循环条件我们对空指针进行了解引用，所以我们需要判断一下。

//尾部数据插入
void SListPushBack(SLNode** phead, ListDataType x)
{
	//新开辟一个节点
	SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
	if (newNode == NULL)
	{
		//空间开辟失败
		printf("SListPushBack::newNode");
		exit(-1);
	}

	//新节点指向NULL，存储数据x
	newNode->data = x;
	newNode->Next = NULL;


	if (*phead == NULL)
	{
		//当前链表为空，那么我直接让新节点替代phead
		*phead = newNode;
		return;
	}

	//找到最后一个节点
	SLNode* cru = *phead;

	//如果cru指向NULL，说明cru是最后一个节点
	while (cru->Next != NULL)
	{
		cru = cru->Next;
	}
	//cru 指向新节点
	cru->Next = newNode; 
	

}

然后我们测试一下，发现链表已经链接起来了

三. 链表打印

为了方便后面测试，我们决定先实现打印链表的函数。我们只需要依次查找节点指向的元素，直到最后一个指向NULL时，我们停下来。

//链表打印
void SListPrint(SLNode* head)
{
	SLNode* cru = head;
	while (cru)
	{
		printf("%d->",cru->data);
		cru = cru->Next;
	}
	printf("NULL\n");
}

四. 头插

头部插入和尾部插入差不多，我们只需要把新节点指向链表中的第一个节点，然后把头节点换成新节点。

因为我们尾插的时候创建了节点，头插又创建节点，太麻烦了，所以我们把创建节点封装成一个函数。

//创建节点
SLNode* SListCreateNode(ListDataType x)
{
	//新开辟一个节点
	SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
	if (newNode == NULL)
	{
		//空间开辟失败
		printf("SListPushBack::newNode");
		exit(-1);
	}

	//新节点指向NULL，存储数据x
	newNode->data = x;
	newNode->Next = NULL; 
	return newNode;
}

尾插函数调整

//尾部数据插入
void SListPushBack(SLNode** phead, ListDataType x)
{
	
	SLNode* newNode = SListCreateNode(x);

	if (*phead == NULL)
	{
		//当前链表为空，那么我直接让新节点替代phead
		*phead = newNode;
		return;
	}

	//找到最后一个节点
	SLNode* cru = *phead;

	//如果cru指向NULL，说明cru是最后一个节点
	while (cru->Next != NULL)
	{
		cru = cru->Next;
	}
	//cru 指向新节点
	cru->Next = newNode; 
}

头插函数

//头部数据插入
void SListPushFront(SLNode** phead, ListDataType x)
{
	//新建节点
	SLNode* newNode = SListCreateNode(x);

	//让节点指向头
	newNode->Next = *phead;
	//头节点更替为新节点
	*phead = newNode;
	
}

头插测试

五. 尾删

尾删也就是删除链表中的最后一个节点。那么我们需要找到最后一个节点，把它释放，并且要把它的前一个节点置为空指针，否则它会变成一个野指针。

//尾部数据删除
void SListPopBack(SLNode** phead)
{
	SLNode* cru = *phead; //最后一个节点
	SLNode* prve = NULL; //前一个节点

	//最后一个节点指向空
	while (cru->Next)
	{
		prve = cru;
		cru = cru->Next;
	}
	//cru 为最后一个节点。释放掉
	free(cru);
	//前一个节点指向空
	prve->Next = NULL;

}

但是这个尾删是建立在有数据的情况下的，如果没有数据我们进行此操作，那会造成空指针prve访问，所以我们在前面要断言一下

void SListPopBack(SLNode** phead)
{
	//链表为空无法删除
	assert(*phead);

	SLNode* cru = *phead; //最后一个节点
	SLNode* prve = NULL; //前一个节点

	//最后一个节点指向空
	while (cru->Next)
	{
		prve = cru;
		cru = cru->Next;
	}
	//cru 为最后一个节点。释放掉
	free(cru);
	//前一个节点指向空
	prve->Next = NULL;

}

即使这样，以上代码依然有问题，因为当链表只有一个节点时，并不会进入while循环，也就导致 prve对空指针解引用，所以我们还需要判断一下，如果链表只有一个节点，那么就直接释放头节点。

//尾部数据删除
void SListPopBack(SLNode** phead)
{
	//链表为空无法删除
	assert(*phead);

	//只有一个节点时
	if((*phead)->Next == NULL)
	{ 
		//释放头空间
		free(*phead);
		//置为空指针
		*phead = NULL;
		return;
	}

	SLNode* cru = *phead; //最后一个节点
	SLNode* prve = NULL; //前一个节点

	//找到最后一个节点
	while (cru->Next)
	{
		prve = cru;
		cru = cru->Next;
	}
	//cru 为最后一个节点。释放掉
	free(cru);
	//前一个节点指向空
	prve->Next = NULL;
}

代码测试

六. 头删

尾删都会了，头删还远吗？头删我们只需要把头节点指向的空间释放，然后让头节点的指针指向下一个节点。

当然，如果链表为空，我们是无法操作的，我们也要断言或者if判断一下。

//头部数据删除
void SListPopFront(SLNode** phead)
{
	//断言
	assert(*phead);

	//链表不为空，存储下一个位置的地址
	SLNode* NextNode = (*phead)->Next;
	//释放 *phead 
	free(*phead);
	//存储的节点给*phead
	*phead = NextNode;
}

测试一下代码

七. 查找值

在链表里查找值，我们只需要找节点，如果与找的值相等，就返回当前下标或者节点，这里我们用返回节点演示。

SLNode* SListFindNode(SLNode* head, ListDataType x)
{
	SLNode* cru = head;
	//查找值
	while (cru)
	{
		//如果当前节点等于要查找的值
		if (cru->data == x)
		{
			//返回当前节点，也可以返回下标，把函数返回值改成int
			return cru;
		}
		  //下一个节点
		cru = cru->Next;
	}

	//遍历完没有找到， 返回空指针
	return NULL;
}

看看测试结果

链表里我们插入了三个值，1，2，3。然后找1的值并返回当前节点，最终提示我们找到了。

当然，也可以用返回下标的方式，然后利用下标控制查找次数。

八.指定插入

指定插入，我们这里来演示前插，也就是在一个节点的前面进行插入，我们只需要把这个节点前面的节点指向新节点，然后新节点指向这个节点。

所以我们要先创建一个节点，让被插入节点之前的节点指向该节点，让新节点指向被插入的节点。

//指定插入
void SListInsert(SLNode** phead, SLNode* pos, ListDataType x)
{
	//首先插入之前，我们必须保证被插入的pos节点存在，不然无法插入
	assert(pos);
	
	SLNode* cru = *phead; //用来查找被插入的节点

	//查找pos节点
	while (cru->Next != pos)
	{
		cru = cru->Next;
	}

	//找到后，创建一个新节点
	SLNode* newNode = SListCreateNode(x);
	//新节点指向pos
	newNode->Next = pos;
	//pos的前一个节点指向cru
	cru->Next = newNode;
	

}

此时这个代码仍有问题，因为如果 pos是第一个节点时，cru->next无法判断判断第一个节点，所以我们要加个判断，如果是头节点，直接调用头插函数。

//指定插入
void SListInsert(SLNode** phead, SLNode* pos, ListDataType x)
{
	//首先插入之前，我们必须保证被插入的pos节点存在，不然无法插入
	assert(pos);

	//头节点就是pos
	if (*phead == pos)
	{
		//调用头插
		SListPushFront(phead,x);
		return 0;
	}
	
	SLNode* cru = *phead; //用来查找被插入的节点

	//查找pos节点
	while (cru->Next != pos)
	{
		cru = cru->Next;
	}

	//找到后，创建一个新节点
	SLNode* newNode = SListCreateNode(x);
	//新节点指向pos
	newNode->Next = pos;
	//pos的前一个节点指向cru
	cru->Next = newNode;
}

代码测试

九.指定删除

指定删除和指定插入差不多，我们只需要把被删除节点的前一个节点，指向后一个节点，然后删除节点。如果要删除的是头节点，直接调用头删函数，或者也可以再次写一个头删。

//指定节点删除
void SListEase(SLNode** phead, SLNode* pos)
{
	//pos是空指针，干掉程序
	assert(pos);

	//如果头节点与pos相等，直接调用头删
	if (*phead == pos)
	{
		SListPopFront(phead);
		return;
	}

	//创建一个节点
	SLNode* cru = *phead;  //查找被删除节点的前一个节点
	while (cru->Next != pos)
	{
		cru = cru->Next;
	}
	
	//cru指向 pos 后的位置
	cru->Next = pos->Next;

	//释放pos所在空间
	free(pos);
	pos = NULL;

}

代码测试

十.销毁链表

如果这个链表不想用了，我们想要清空链表。那我们只需要把依次释放内存。

//销毁链表
void SListDestroy(SLNode** phead)
{
	SLNode* cru = NULL;

	while (*phead)
	{
		//存储下一个节点的地址
		cru = (*phead)->Next;+
		//当前地址置空
		*phead = NULL;
		//释放当前空间
		free(*phead);
		//换成下一个节点继续
		*phead = cru;
	}

}

然后我们测试一下，发现所有的节点都置空了

以上代码以上传至git，点这里获取

加载全部内容