手把手教你實(shí)現(xiàn)一個(gè)C++單鏈表

更新時(shí)間：2022年11月29日 16:31:05 作者：小林同志_____

鏈表是一種數(shù)據(jù)結(jié)構(gòu)，用于數(shù)據(jù)的存儲(chǔ)。這篇文章主要為大家介紹了如何實(shí)現(xiàn)一個(gè)C++單鏈表，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以嘗試一下

一. 節(jié)點(diǎn)聲明

鏈表是一種數(shù)據(jù)結(jié)構(gòu)，用于數(shù)據(jù)的存儲(chǔ)。

如圖，每一個(gè)鏈表節(jié)點(diǎn)所在的內(nèi)存空間是不延續(xù)的，因?yàn)椴皇沁B續(xù)存儲(chǔ)，所以需要存入下一個(gè)節(jié)點(diǎn)的地址，這樣方便找到下一個(gè)數(shù)值，而最后一個(gè)鏈表指向的空間為NULL，因此我們可以聲明一個(gè)結(jié)構(gòu)體，代表一個(gè)節(jié)點(diǎn)。

typedef int ListDataType;

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

}SLNode;

SListNode 是我們的節(jié)點(diǎn)結(jié)構(gòu)體，ListDataType是存儲(chǔ)數(shù)據(jù)的類型。

二. 尾插

鏈表的節(jié)點(diǎn)建立好后，接下來我們來進(jìn)行尾部插入數(shù)據(jù)。

那么我們只需要找到尾部節(jié)點(diǎn)，把尾部節(jié)點(diǎn)指向的NULL值置為新節(jié)點(diǎn)。新節(jié)點(diǎn)指向NULL

因此我們要新建一個(gè)節(jié)點(diǎn)，然后找到最后一個(gè)節(jié)點(diǎn)。

void SListPushBack(SLNode** phead, ListDataType x)
{
	//新開辟一個(gè)節(jié)點(diǎn)
	SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
	if (newNode == NULL)
	{
		//空間開辟失敗
		printf("SListPushBack::newNode");
		exit(-1);
	}

	//找到最后一個(gè)節(jié)點(diǎn)
	SLNode* cru = *phead;
	//如果cru指向NULL，說明cru是最后一個(gè)節(jié)點(diǎn)
	while (cru->Next != NULL)
	{
		cru = cru->Next;
	}
	//cru 指向新節(jié)點(diǎn)
	cru->Next = newNode; 
	//新節(jié)點(diǎn)指向NULL，存儲(chǔ)數(shù)據(jù)x
	newNode->data = x;
	newNode->Next = NULL;

}

但是這種方法，我們需要注意一種情況，那就是如果鏈表中本身沒有節(jié)點(diǎn)，那么cru初始就是一個(gè)空指針，而循環(huán)條件我們對(duì)空指針進(jìn)行了解引用，所以我們需要判斷一下。

//尾部數(shù)據(jù)插入
void SListPushBack(SLNode** phead, ListDataType x)
{
	//新開辟一個(gè)節(jié)點(diǎn)
	SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
	if (newNode == NULL)
	{
		//空間開辟失敗
		printf("SListPushBack::newNode");
		exit(-1);
	}

	//新節(jié)點(diǎn)指向NULL，存儲(chǔ)數(shù)據(jù)x
	newNode->data = x;
	newNode->Next = NULL;


	if (*phead == NULL)
	{
		//當(dāng)前鏈表為空，那么我直接讓新節(jié)點(diǎn)替代phead
		*phead = newNode;
		return;
	}

	//找到最后一個(gè)節(jié)點(diǎn)
	SLNode* cru = *phead;

	//如果cru指向NULL，說明cru是最后一個(gè)節(jié)點(diǎn)
	while (cru->Next != NULL)
	{
		cru = cru->Next;
	}
	//cru 指向新節(jié)點(diǎn)
	cru->Next = newNode; 
	

}

然后我們測(cè)試一下，發(fā)現(xiàn)鏈表已經(jīng)鏈接起來了

三. 鏈表打印

為了方便后面測(cè)試，我們決定先實(shí)現(xiàn)打印鏈表的函數(shù)。我們只需要依次查找節(jié)點(diǎn)指向的元素，直到最后一個(gè)指向NULL時(shí)，我們停下來。

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

四. 頭插

頭部插入和尾部插入差不多，我們只需要把新節(jié)點(diǎn)指向鏈表中的第一個(gè)節(jié)點(diǎn)，然后把頭節(jié)點(diǎn)換成新節(jié)點(diǎn)。

因?yàn)槲覀兾膊宓臅r(shí)候創(chuàng)建了節(jié)點(diǎn)，頭插又創(chuàng)建節(jié)點(diǎn)，太麻煩了，所以我們把創(chuàng)建節(jié)點(diǎn)封裝成一個(gè)函數(shù)。

//創(chuàng)建節(jié)點(diǎn)
SLNode* SListCreateNode(ListDataType x)
{
	//新開辟一個(gè)節(jié)點(diǎn)
	SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
	if (newNode == NULL)
	{
		//空間開辟失敗
		printf("SListPushBack::newNode");
		exit(-1);
	}

	//新節(jié)點(diǎn)指向NULL，存儲(chǔ)數(shù)據(jù)x
	newNode->data = x;
	newNode->Next = NULL; 
	return newNode;
}

尾插函數(shù)調(diào)整

//尾部數(shù)據(jù)插入
void SListPushBack(SLNode** phead, ListDataType x)
{
	
	SLNode* newNode = SListCreateNode(x);

	if (*phead == NULL)
	{
		//當(dāng)前鏈表為空，那么我直接讓新節(jié)點(diǎn)替代phead
		*phead = newNode;
		return;
	}

	//找到最后一個(gè)節(jié)點(diǎn)
	SLNode* cru = *phead;

	//如果cru指向NULL，說明cru是最后一個(gè)節(jié)點(diǎn)
	while (cru->Next != NULL)
	{
		cru = cru->Next;
	}
	//cru 指向新節(jié)點(diǎn)
	cru->Next = newNode; 
}

頭插函數(shù)

//頭部數(shù)據(jù)插入
void SListPushFront(SLNode** phead, ListDataType x)
{
	//新建節(jié)點(diǎn)
	SLNode* newNode = SListCreateNode(x);

	//讓節(jié)點(diǎn)指向頭
	newNode->Next = *phead;
	//頭節(jié)點(diǎn)更替為新節(jié)點(diǎn)
	*phead = newNode;
	
}

頭插測(cè)試

五. 尾刪

尾刪也就是刪除鏈表中的最后一個(gè)節(jié)點(diǎn)。那么我們需要找到最后一個(gè)節(jié)點(diǎn)，把它釋放，并且要把它的前一個(gè)節(jié)點(diǎn)置為空指針，否則它會(huì)變成一個(gè)野指針。

//尾部數(shù)據(jù)刪除
void SListPopBack(SLNode** phead)
{
	SLNode* cru = *phead; //最后一個(gè)節(jié)點(diǎn)
	SLNode* prve = NULL; //前一個(gè)節(jié)點(diǎn)

	//最后一個(gè)節(jié)點(diǎn)指向空
	while (cru->Next)
	{
		prve = cru;
		cru = cru->Next;
	}
	//cru 為最后一個(gè)節(jié)點(diǎn)。釋放掉
	free(cru);
	//前一個(gè)節(jié)點(diǎn)指向空
	prve->Next = NULL;

}

但是這個(gè)尾刪是建立在有數(shù)據(jù)的情況下的，如果沒有數(shù)據(jù)我們進(jìn)行此操作，那會(huì)造成空指針prve訪問，所以我們?cè)谇懊嬉獢嘌砸幌?/p>

void SListPopBack(SLNode** phead)
{
	//鏈表為空無法刪除
	assert(*phead);

	SLNode* cru = *phead; //最后一個(gè)節(jié)點(diǎn)
	SLNode* prve = NULL; //前一個(gè)節(jié)點(diǎn)

	//最后一個(gè)節(jié)點(diǎn)指向空
	while (cru->Next)
	{
		prve = cru;
		cru = cru->Next;
	}
	//cru 為最后一個(gè)節(jié)點(diǎn)。釋放掉
	free(cru);
	//前一個(gè)節(jié)點(diǎn)指向空
	prve->Next = NULL;

}

即使這樣，以上代碼依然有問題，因?yàn)楫?dāng)鏈表只有一個(gè)節(jié)點(diǎn)時(shí)，并不會(huì)進(jìn)入while循環(huán)，也就導(dǎo)致 prve對(duì)空指針解引用，所以我們還需要判斷一下，如果鏈表只有一個(gè)節(jié)點(diǎn)，那么就直接釋放頭節(jié)點(diǎn)。

//尾部數(shù)據(jù)刪除
void SListPopBack(SLNode** phead)
{
	//鏈表為空無法刪除
	assert(*phead);

	//只有一個(gè)節(jié)點(diǎn)時(shí)
	if((*phead)->Next == NULL)
	{ 
		//釋放頭空間
		free(*phead);
		//置為空指針
		*phead = NULL;
		return;
	}

	SLNode* cru = *phead; //最后一個(gè)節(jié)點(diǎn)
	SLNode* prve = NULL; //前一個(gè)節(jié)點(diǎn)

	//找到最后一個(gè)節(jié)點(diǎn)
	while (cru->Next)
	{
		prve = cru;
		cru = cru->Next;
	}
	//cru 為最后一個(gè)節(jié)點(diǎn)。釋放掉
	free(cru);
	//前一個(gè)節(jié)點(diǎn)指向空
	prve->Next = NULL;
}

代碼測(cè)試

六. 頭刪

尾刪都會(huì)了，頭刪還遠(yuǎn)嗎？頭刪我們只需要把頭節(jié)點(diǎn)指向的空間釋放，然后讓頭節(jié)點(diǎn)的指針指向下一個(gè)節(jié)點(diǎn)。

當(dāng)然，如果鏈表為空，我們是無法操作的，我們也要斷言或者if判斷一下。

//頭部數(shù)據(jù)刪除
void SListPopFront(SLNode** phead)
{
	//斷言
	assert(*phead);

	//鏈表不為空，存儲(chǔ)下一個(gè)位置的地址
	SLNode* NextNode = (*phead)->Next;
	//釋放 *phead 
	free(*phead);
	//存儲(chǔ)的節(jié)點(diǎn)給*phead
	*phead = NextNode;
}

測(cè)試一下代碼

七. 查找值

在鏈表里查找值，我們只需要找節(jié)點(diǎn)，如果與找的值相等，就返回當(dāng)前下標(biāo)或者節(jié)點(diǎn)，這里我們用返回節(jié)點(diǎn)演示。

SLNode* SListFindNode(SLNode* head, ListDataType x)
{
	SLNode* cru = head;
	//查找值
	while (cru)
	{
		//如果當(dāng)前節(jié)點(diǎn)等于要查找的值
		if (cru->data == x)
		{
			//返回當(dāng)前節(jié)點(diǎn)，也可以返回下標(biāo)，把函數(shù)返回值改成int
			return cru;
		}
		  //下一個(gè)節(jié)點(diǎn)
		cru = cru->Next;
	}

	//遍歷完沒有找到， 返回空指針
	return NULL;
}

看看測(cè)試結(jié)果

鏈表里我們插入了三個(gè)值，1，2，3。然后找1的值并返回當(dāng)前節(jié)點(diǎn)，最終提示我們找到了。

當(dāng)然，也可以用返回下標(biāo)的方式，然后利用下標(biāo)控制查找次數(shù)。

八.指定插入

指定插入，我們這里來演示前插，也就是在一個(gè)節(jié)點(diǎn)的前面進(jìn)行插入，我們只需要把這個(gè)節(jié)點(diǎn)前面的節(jié)點(diǎn)指向新節(jié)點(diǎn)，然后新節(jié)點(diǎn)指向這個(gè)節(jié)點(diǎn)。

所以我們要先創(chuàng)建一個(gè)節(jié)點(diǎn)，讓被插入節(jié)點(diǎn)之前的節(jié)點(diǎn)指向該節(jié)點(diǎn)，讓新節(jié)點(diǎn)指向被插入的節(jié)點(diǎn)。

//指定插入
void SListInsert(SLNode** phead, SLNode* pos, ListDataType x)
{
	//首先插入之前，我們必須保證被插入的pos節(jié)點(diǎn)存在，不然無法插入
	assert(pos);
	
	SLNode* cru = *phead; //用來查找被插入的節(jié)點(diǎn)

	//查找pos節(jié)點(diǎn)
	while (cru->Next != pos)
	{
		cru = cru->Next;
	}

	//找到后，創(chuàng)建一個(gè)新節(jié)點(diǎn)
	SLNode* newNode = SListCreateNode(x);
	//新節(jié)點(diǎn)指向pos
	newNode->Next = pos;
	//pos的前一個(gè)節(jié)點(diǎn)指向cru
	cru->Next = newNode;
	

}

此時(shí)這個(gè)代碼仍有問題，因?yàn)槿绻?pos是第一個(gè)節(jié)點(diǎn)時(shí)，cru->next無法判斷判斷第一個(gè)節(jié)點(diǎn)，所以我們要加個(gè)判斷，如果是頭節(jié)點(diǎn)，直接調(diào)用頭插函數(shù)。

//指定插入
void SListInsert(SLNode** phead, SLNode* pos, ListDataType x)
{
	//首先插入之前，我們必須保證被插入的pos節(jié)點(diǎn)存在，不然無法插入
	assert(pos);

	//頭節(jié)點(diǎn)就是pos
	if (*phead == pos)
	{
		//調(diào)用頭插
		SListPushFront(phead,x);
		return 0;
	}
	
	SLNode* cru = *phead; //用來查找被插入的節(jié)點(diǎn)

	//查找pos節(jié)點(diǎn)
	while (cru->Next != pos)
	{
		cru = cru->Next;
	}

	//找到后，創(chuàng)建一個(gè)新節(jié)點(diǎn)
	SLNode* newNode = SListCreateNode(x);
	//新節(jié)點(diǎn)指向pos
	newNode->Next = pos;
	//pos的前一個(gè)節(jié)點(diǎn)指向cru
	cru->Next = newNode;
}

代碼測(cè)試

九.指定刪除

指定刪除和指定插入差不多，我們只需要把被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，指向后一個(gè)節(jié)點(diǎn)，然后刪除節(jié)點(diǎn)。如果要?jiǎng)h除的是頭節(jié)點(diǎn)，直接調(diào)用頭刪函數(shù)，或者也可以再次寫一個(gè)頭刪。

//指定節(jié)點(diǎn)刪除
void SListEase(SLNode** phead, SLNode* pos)
{
	//pos是空指針，干掉程序
	assert(pos);

	//如果頭節(jié)點(diǎn)與pos相等，直接調(diào)用頭刪
	if (*phead == pos)
	{
		SListPopFront(phead);
		return;
	}

	//創(chuàng)建一個(gè)節(jié)點(diǎn)
	SLNode* cru = *phead;  //查找被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
	while (cru->Next != pos)
	{
		cru = cru->Next;
	}
	
	//cru指向 pos 后的位置
	cru->Next = pos->Next;

	//釋放pos所在空間
	free(pos);
	pos = NULL;

}

代碼測(cè)試

十.銷毀鏈表

如果這個(gè)鏈表不想用了，我們想要清空鏈表。那我們只需要把依次釋放內(nèi)存。

//銷毀鏈表
void SListDestroy(SLNode** phead)
{
	SLNode* cru = NULL;

	while (*phead)
	{
		//存儲(chǔ)下一個(gè)節(jié)點(diǎn)的地址
		cru = (*phead)->Next;+
		//當(dāng)前地址置空
		*phead = NULL;
		//釋放當(dāng)前空間
		free(*phead);
		//換成下一個(gè)節(jié)點(diǎn)繼續(xù)
		*phead = cru;
	}

}

然后我們測(cè)試一下，發(fā)現(xiàn)所有的節(jié)點(diǎn)都置空了