一、帶頭結(jié)點(diǎn)單鏈表

Single linked list with leading nodes

關(guān)于不帶頭結(jié)點(diǎn)的單鏈表：不帶頭結(jié)點(diǎn)的單鏈表

二、結(jié)點(diǎn)與接口定義

結(jié)點(diǎn)定義：

typedef int SLLWDataType;
typedef struct SLLWNode
{
	SLLWDataType data;
	struct SLLWNode* next;
}SLLWNode;

接口定義：

void SLLWInit(SLLWNode** phead);

void SLLWPrint(SLLWNode* phead);

void SLLWPushFront(SLLWNode* phead, SLLWDataType x);
void SLLWPushBack(SLLWNode* phead, SLLWDataType x);

void SLLWPopFront(SLLWNode* phead);
void SLLWPopBack(SLLWNode* phead);

SLLWNode* SLLWFind(SLLWNode* phead, SLLWDataType x);

// 在pos之前插入
void SLLWInsert(SLLWNode* phead, SLLWNode* pos, SLLWDataType x);
// 在pos之后插入
void SLLWInsertAfter(SLLWNode* pos, SLLWDataType x);

// 刪除pos位置的值
void SLLWErase(SLLWNode* phead, SLLWNode* pos);
// 刪除pos位置后面的值
void SLLWEraseAfter(SLLWNode* pos);

// 銷(xiāo)毀
void SLLWDestroy(SLLWNode* phead);

三、接口實(shí)現(xiàn)

3.1 Init初始化與申請(qǐng)節(jié)點(diǎn)

初始化需要申請(qǐng)頭結(jié)點(diǎn)，讓頭指針指向空的頭結(jié)點(diǎn)。

void SLLWInit(SLLWNode** phead)
{
	assert(phead);
	*phead = SLLWMalloc((SLLWDataType)230504);
}

將申請(qǐng)結(jié)點(diǎn)的代碼進(jìn)行封裝：

SLLWNode* SLLWMalloc(SLLWDataType x)
{
	SLLWNode* newnode = (SLLWNode*)malloc(sizeof(SLLWNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

3.2 打印

需要越過(guò)頭結(jié)點(diǎn)

void SLLWPrint(SLLWNode* phead)
{
	assert(phead);
	SLLWNode* cur = phead->next;
	while (cur)
	{
		print("[%d]->", cur->data);
		cur = cur->next;
	}
	print("NULL\n");
}

3.3 尾插PushBack

找到尾結(jié)點(diǎn)，然后插入到尾結(jié)點(diǎn)的后面。

void SLLWPushBack(SLLWNode* phead, SLLWDataType x)
{
	assert(phead);

	// Find the tail node 
	SLLWNode* tail = phead;
	while (tail->next)
	{
		tail = tail->next;
	}

	// insert it after the tail node
	SLLWNode* newnode = SLLWMalloc(x);
	tail->next = newnode;
}

對(duì)比不帶頭結(jié)點(diǎn)的單鏈表的尾插：

void SLLPushBack(SLLNode** pphead, SLLDataType x)
{
	assert(pphead); // 鏈表為空，pphead也不為空

	SLLNode* newnode = CreateSLLNode(x);
	
	if (*pphead == NULL)
	{
		// 1、空鏈表
		*pphead = newnode;
	}
	else
	{
		// 2、非空鏈表
		SLLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newnode;
	}
}

我們發(fā)現(xiàn)相比于不帶頭結(jié)點(diǎn)的單鏈表尾插，帶頭結(jié)點(diǎn)的尾插的代碼要更簡(jiǎn)潔，不用判斷是否是空鏈表對(duì)插入第一個(gè)元素的單獨(dú)處理。

此外，在函數(shù)的接口定義時(shí)，不帶頭結(jié)點(diǎn)的單鏈表還要傳入二級(jí)指針，讓函數(shù)外的頭指針指向第一個(gè)節(jié)點(diǎn)，這也同樣是對(duì)插入第一個(gè)元素的單獨(dú)處理，而帶頭結(jié)點(diǎn)的單鏈表不用這樣做，因?yàn)閹ь^結(jié)點(diǎn)的鏈表在初始化時(shí)就有頭結(jié)點(diǎn)，函數(shù)外的頭指針始終指向頭結(jié)點(diǎn)。

3.4 頭插PushFront

void SLLWPushFront(SLLWNode* phead, SLLWDataType x)
{
	assert(phead);
	SLLWNode* newnode = SLLWMalloc(x);
	newnode->next = phead->next;
	phead->next = newnode;
}

3.5 頭刪PopFront

無(wú)論是頭刪還是尾刪，鏈表中至少有一個(gè)數(shù)據(jù)元素才能進(jìn)行刪除：

void SLLWPopFront(SLLWNode* phead)
{
	assert(phead);
	assert(phead->next); // At least one element in the linked list can be deleted
	
	SLLWNode* del = phead->next;
	phead->next = del->next;
	free(del);
}

3.6 尾刪PopBack

同頭刪一樣，鏈表中要求至少有一個(gè)數(shù)據(jù)元素。

找到尾結(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，然后將尾結(jié)點(diǎn)刪除，其前一個(gè)節(jié)點(diǎn)的next域置空。

void SLLWPopBack(SLLWNode* phead)
{
	assert(phead);
	assert(phead->next);

	// Find the node before the tail node
	SLLWNode* pretail = phead;
	while (pretail->next->next)
	{
		pretail = pretail->next;
	}

    // Delete the tail node
	free(pretail->next);
	pretail->next = NULL;
}

對(duì)比不帶頭結(jié)點(diǎn)的單鏈表，還要對(duì)鏈表中只有一個(gè)元素時(shí)的PopBack進(jìn)行單獨(dú)處理，因?yàn)閷?duì)頭的處理。

3.7 查找Find

遍歷鏈表，找到返回該節(jié)點(diǎn)，找不到返回空。

SLLWNode* SLLWFind(SLLWNode* phead, SLLWDataType x)
{
	assert(phead);

	SLLWNode* cur = phead->next;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}

3.8 插入insert-在指定結(jié)點(diǎn)前插入

找到該結(jié)點(diǎn)前一個(gè)結(jié)點(diǎn)，插入到其后面。

如果pos節(jié)點(diǎn)沒(méi)找到，在下面while循環(huán)遍歷過(guò)程中，會(huì)產(chǎn)生空指針異常，直接報(bào)錯(cuò)。

void SLLWInsert(SLLWNode* phead, SLLWNode* pos, SLLWDataType x)
{
	assert(phead);
	assert(pos);

	// Find the node before the pos node
	SLLWNode* prev = phead;
	// The pos node is not found, a null pointer exception is raised
	while (prev->next != pos)
	{
		prev = prev->next;
	}

	// The pos node is found
	SLLWNode* newnode = SLLWMalloc(x);
	prev->next = newnode;
	newnode->next = pos;
}

對(duì)比不帶頭結(jié)點(diǎn)的單鏈表的在pos之前進(jìn)行插入，還要單獨(dú)判斷pos是否是第一個(gè)元素節(jié)點(diǎn)。而帶頭結(jié)點(diǎn)的單鏈表在實(shí)現(xiàn)時(shí)，不需要判斷。

另一種偷梁換柱方法：

void SLLWInsert1(SLLWNode* phead, SLLWNode* pos, SLLWDataType x)
{
	assert(phead);
	assert(pos);

	// The consumer calls find first, then insert, 
	// so pos must be in the linked list

	SLLWNode* newnode = SLLWMalloc(pos->data);
	newnode->next = pos->next;
	pos->data = x;
	pos->next = newnode;
}

這里不需要判斷pos是否在鏈表中，因?yàn)閺氖褂谜叩慕嵌葋?lái)看，一般是先Find找到x所在的pos，然后Insert插入到找到的pos的位置之前。所以pos必在鏈表中。

3.9 指定pos后插

void SLLWInsertAfter(SLLWNode* pos, SLLWDataType x)
{
	assert(pos);

	SLLWNode* newnode = SLLWMalloc(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

3.10 刪除Erase-在指定pos處插入

刪除時(shí)，鏈表中至少有一個(gè)元素結(jié)點(diǎn)。

找到pos的前一個(gè)節(jié)點(diǎn)，然后將pos刪除即可。

void SLLWErase(SLLWNode* phead, SLLWNode* pos)
{
	assert(phead);
	assert(phead->next);
	assert(pos);

	// Find the node before the pos node
	SLLWNode* prev = phead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	// The pos node is not found, a null pointer exception is raised
	
	// The pos node is found, delete it
	prev->next = pos->next;
	free(pos);
}

對(duì)比不帶頭結(jié)點(diǎn)的單鏈表，刪除時(shí)還需要對(duì)只有一個(gè)元素時(shí)的鏈表進(jìn)行單獨(dú)處理。

3.11 指定pos后刪

void SLLWEraseAfter(SLLWNode* pos)
{
	assert(pos);

	SLLWNode* del = pos->next;
	pos->next = del->next;
	free(del);
}

3.12 銷(xiāo)毀Destroy

頭結(jié)點(diǎn)也要進(jìn)行銷(xiāo)毀。

void SLLWDestroy(SLLWNode* phead)
{
	assert(phead);

	SLLWNode* cur = phead;
	while (cur)
	{
		SLLWNode* del = cur;
		cur = cur->next;
		free(del);
	}
}

源碼

gitee-SingleLinkedListWithLeadingNode

總結(jié)

帶頭結(jié)點(diǎn)的單鏈表，只要跳過(guò)頭結(jié)點(diǎn)就變成了不帶頭結(jié)點(diǎn)的單鏈表，鏈表永遠(yuǎn)有一個(gè)頭結(jié)點(diǎn)，所以代碼寫(xiě)起來(lái)更簡(jiǎn)潔，特別是尾插PushBack、尾刪PopBack、插入insert、刪除Erase的代碼。

事實(shí)上也確實(shí)如此，在實(shí)際的鏈表OJ題中，題目的要求是不帶頭結(jié)點(diǎn)的單鏈表，我們?nèi)藶榧由项^結(jié)點(diǎn)，然后將邏輯代碼寫(xiě)完后，再將添加的頭結(jié)點(diǎn)刪除，這樣代碼的邏輯會(huì)變得更簡(jiǎn)單。如 鏈表分割 、合并兩個(gè)有序鏈表文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-433526.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】C語(yǔ)言實(shí)現(xiàn)單鏈表（帶頭結(jié)點(diǎn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！