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

目录

• 一. 节点声明
• 二. 尾插
• 三. 链表打印
• 四. 头插
• 五. 尾删
• 六. 头删
• 七. 查找值
• 八.指定插入
• 九.指定删除
• 十.销毁链表

一. 节点声明

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

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

typedef int ListDataType;

typedef s编程客栈truct 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指向NULLpython，说明cru是最后一个节点
	while (cru->Next != NULL)
	{
		cru = cru->Next;
	}
	//cru 指向新节点
	cru->Next = newNode; 
}

头插函数

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

	//让节点指向头
	newNode->Next = *phead;
	//头节点更替为新节点
	*phead = nhttp://www.devze.comewNode;
	
}

头插测试

五. 尾删

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

//尾部数据删除
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的值并返回当前节点，最终提示我们找到了。

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

八.指定插入

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

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

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

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

www.devze.com	//找到后，创建一个新节点
	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，点这里获取

到此这篇关于手把手教你实现一个C++单链表的文章就介绍到这了,更多相关C++单链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！