C語言如何實現單鏈表操作

本篇內容介紹了“C語言如何實現單鏈表操作”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

1 鏈表的概念及結構

概念：鏈表是一種物理存儲結構上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈 接次序實現的 。

注意：

1. 從上圖可以看出，鏈式結構在邏輯上是連續的，但是在物理上不一定是連續

2. 現實中的節點一般是從堆上申請出來的

3. 從對上申請的空間，是按照一定的策略來分配的，兩次申請的空間可能連續，也可能不連續

2 鏈表的分類

實際中鏈表的結構非常多樣，以下情況組合起來就有8種鏈表結構：

1、單向或者雙向鏈表

2、帶頭或者不帶頭鏈表

3、循環或非循環鏈表

最常用的有兩種：無頭單向非循環鏈表、帶頭雙向循環鏈表

• 無頭單向非循環鏈表：結構簡單，一般不會單獨用來存數據。實際中更多是作為其他數據結構的子結 構，如哈希桶、圖的鄰接表等等。另外這種結構在筆試面試中出現很多。

• 帶頭雙向循環鏈表：結構最復雜，一般用在單獨存儲數據。實際中使用的鏈表數據結構，都是帶頭雙向 循環鏈表。另外這個結構雖然結構復雜，但是使用代碼實現以后會發現結構會帶來很多優勢，實現反而簡單了，后面我們代碼實現了就知道了。

3 鏈表的實現無頭+單向+非循環鏈表增刪查改實現

3.1 鏈表的定義

typedef int SLTDataType;//
typedef struct SListNode
{
	int data;//val，存儲的數據，此處假設存儲的數據為int型
	struct SListNode* next;//存儲下一個節點的位置
}SListNode,SLN;

3.2 鏈表數據的打印

void SListPrint(SListNode* phead)
{
	SListNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

3.3 鏈表的尾插

void SListPushBack(SListNode** pphead, SLTDataType x)
{
	SListNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

在找尾的過程中，務必不能寫成下面的代碼：

while(tail!=NULL)
{
	tail = tail->next;
}
tail->next = newnode;

當然，上面的介紹的是尾刪的情況。

尾插其實也是類似的，尾插的話像上面的代碼中，當tail!=NULL不成立之后，tail等于空，然后執行賦值操作，tail->next = newnode這行代碼相當于下面的代碼：

(*tail).next，此處相當于是對空指針進行解引用，其實就是非法訪問了，并還試圖非法修改未授權內存中的數據，這將必然會引發程序的崩潰。而且也并沒有將新節點的地址存儲到之前為節點的next中。

這個地方需要弄明白鏈表進行遍歷的根本原理：

鏈表是一個相對靜態的存儲在堆區中的數據空間，我們通過改變棧區中的局部變量tail中的數據（即每一個鏈表節點的地址）來進行遍歷，之所以能夠通過tail變量能夠進行訪問并且修改節點數據的原因就是因為tail的數據類型是SListNode*，即指向節點的指針，指針的類型決定了對指針解引用能夠訪問的數據類型，所以*tail能夠訪問堆區中的節點的數據并且能夠進行修改。

3.4 鏈表空間的動態申請

SListNode* BuySListNode(SLTDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}
	return newnode;
}

3.5 鏈表的頭插

void SListPushFront(SListNode** pphead, SLTDataType x)
{
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

3.6 鏈表的尾刪

需要考慮三種情況：

• 空

• 一個節點

• 多個節點

兩種寫法：

第一種：

void SListPopBack(SListNode** pphead)
{
	assert(pphead);
	if (*pphead == NULL)//空鏈表
	{
		return;
	}
	else if ((*pphead)->next == NULL)//一個節點
	{
		free(*pphead);//*pphead就是plist的值
		*pphead = NULL;
	}
	else//多個節點
	{
		SListNode* tail = *pphead;
		SListNode* prev = NULL;//為什么要置為空呢？因為這個地方相當于是指向第一個節點之前的節點，這個節點并不存在，設為空
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}

這種方式在面對只有一個節點時也不會出現問題。

第二種：

void SListPopBack(SListNode** pphead)
{
	assert(pphead);
	if (*pphead == NULL)//空鏈表
	{
		return;
	}
	else if ((*pphead)->next == NULL)//一個節點
	{
		free(*pphead);//*pphead就是plist的值
		*pphead = NULL;
	}
	else//多個節點
	{
		SListNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);//釋放尾節點
		tail->next = NULL;//將新尾節點的next置為NULL
	}
}

3.7 鏈表的頭刪

void SListPopFront(SListNode** pphead)
{
	assert(pphead);
	if (*pphead == NULL)//空鏈表
	{
		return;
	}
	else//非空鏈表
	{
		SListNode* next = (*pphead)->next;//next作為臨時變量存放的是被刪除的節點中next存儲的第二個節點的地址
		free(*pphead);
		*pphead = next;
	}
}

3.8 鏈表任意位置的前插入

void SListInsertBefore(SListNode** pphead, SListNode* pos,SLTDataType x)
{
	assert(pphead);
	if (*pphead == pos)//pos是第一個節點，相當于頭插
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SListNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

3.9 鏈表任意位置的后插入

兩種實現方式：

方式一：

void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	
	newnode->next = pos->next;
	pos->next = newnode;
	//這兩行代碼順序是固定的，只能這個順序，無法進行改變
}

圖示：

方式二：

void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);
	SListNode* next = pos->next;
	SListNode* newnode = BuySListNode(x);

	newnode->next = next;
	pos->next = newnode;
	//這兩行代碼可以任意改變順序，誰先誰后都不影響最后的結果
}

圖示：

3.10 鏈表的任意位置的刪除

void SListErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)//當pos為頭節點的時候
	{
		SListPopFront(pphead);
	}
	else//當pos為非頭節點的時候
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

圖示：

3.11 鏈表的任意位置的前刪除

void SListEraseBefore(SListNode** pphead, SListNode* pos)//pos即為任意位置
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		return;
	}
	else if(pos==(*pphead)->next)
	{
		SListPopFront(pphead);
	}
	else
	{
		SListNode* prev = *pphead;//prev用來存儲pos的前一個位置的前一個位置
		while (prev->next->next != pos)
		{
			prev = prev->next;
		}
		SListNode* next = prev->next;//保存pos前一個節點的地址
		prev->next = prev->next->next;//將prev和pos的兩個節點進行連接
		free(next);//刪除pos的前一個節點
	}
}

3.12 鏈表的任意位置的后刪除

void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	SListNode* next = pos->next;
	if (next == NULL)//當pos是最后一個節點的時候
	{
		return;
	}
	else
	{
		pos->next = next->next;
		free(next);
		next = NULL;
	}
}

圖示：

3.13 鏈表的銷毀

void SListDestory(SListNode** pphead)
{
	assert(pphead);
	SListNode* cur = *pphead;
	SListNode* next = *pphead;//是為了存儲cur下一個節點的地址，因為free(cur)之后，cur指針指向的內存中的數據可能已經稱為亂碼了，即不能再正常的使用
	while (cur)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

“C語言如何實現單鏈表操作”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！