日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C語言詳解無頭單向非循環鏈表各種操作方法_C 語言

作者：風＆646 ? 更新時間： 2022-06-21 編程語言

鏈表引入

問：上次我們看了順序表，那么順序表有些什么優缺點呢？

優點：

順序表是連續的物理空間，方便下標的隨機訪問。

缺點：

1.增容需要申請新空間，拷貝數據，釋放舊的空間。會有一定消耗。

2.頭部或者中間位置插入或者刪除數據，需要挪動數據，效率較低。

3.可能存在一定空間占用，浪費空間，不能按需申請和釋放空間。

為了解決上訴問題，我們引入了鏈表。首先我們先來看看單鏈表。

鏈表介紹

鏈表是一種物理存儲結構上非連續、非順序的存儲結構、數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個節點包含兩部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。

實際上，鏈表的結構多樣，如下：

1.單向或者雙向

2.帶頭或者不帶頭

3.循環或者非循環

創建鏈表

鏈表是由結點鏈接而成的，所以創建鏈表需要創建一個結點類型。該類型由指針域和數據域組成。

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;//用來存放該結點的數據
	struct SListNode* next;//用來存放下一個結點的地址
}SListNode;

打印鏈表

從頭指針指向的位置開始，依次向后打印，知道cur訪問到NULL就結束循環。

void SListPrint(SListNode* phead);
void SListPrint(SListNode* phead)
{
	SListNode* cur = phead;//我們一般不會改變頭指針，所以我們把頭指針賦值給cur
	while (cur)//鏈表結束條件
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");//表示數據已經打印完畢
}

創建結點

每當我們需要插入一個數據，我們就需要申請一個結點，如果每次都重新申請就會很麻煩，所以我們將創建一個新結點封裝為一個函數。

SListNode* BuySListNode(SLTDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		printf("BuySListNode::%s\n", strerror(errno));//若申請失敗，則打印錯誤信息
		exit(-1);
	}
	else
	{
		newnode->data = x;//將數據賦值到新點的數據域
		newnode->next = NULL;//新結點指針域置為空指針
	}
	return newnode;//返回新結點的地址
}

單鏈表尾插

我們需要將尾插分為兩種情況：

情況一： 鏈表為空，我們直接讓頭指針指向新的結點即可。

情況二： 鏈表已經有多個結點，我們需要找到鏈表的最后一個結點，然后讓最后一個結點指向新的結點。

void SListPushBack(SListNode** pphead, SLTDataType x);
void SListPushBack(SListNode** pphead, SLTDataType x)
{
	assert(pphead);
	SListNode* newnode = BuySListNode(x);
	//鏈表為空
	if (*pphead == NULL)
	{
		*pphead = newnode;//頭指針指向新的結點
	}
	//鏈表不為空
	else
	{
		SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

注意： 鏈表頭插函數的參數我們應該傳頭指針的地址，而不是頭指針本身。如果為傳值調用，那么形參是實參的一份臨時拷貝，對形參的改變不會影響實參。

單鏈表頭插

單鏈表頭插時，我們申請一個新的結點，然后讓新結點的指針域指向之前的第一個結點，然后讓頭指針指向新結點。

注意：這兩步操作的順序不可以顛倒，如果先讓頭指針指向了新結點，那么將不可能找到第一個結點的位置了。也不可能在找到后面的數據了。

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

單鏈表尾刪

演示一種錯誤的寫法：

對于單鏈表的尾刪，我們需要考慮三種情況：

1.鏈表為空時，不做任何處理。

2.鏈表只有一個結點時，釋放該結點，然后將頭指針置為空。

3.鏈表有多個結點時，有兩種處理方法，詳見一下代碼。

代碼一： 找到最后一個結點的前一個結點，釋放最后一個結點。將前一個結點的指針域置為空指針。

void SListPopBack(SListNode** pphead);
void SListPopBack(SListNode** pphead)
{
	assert(pphead);
	if (*pphead == NULL)
		return;
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* prev = NULL;
		SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}

代碼二： 找到最后一個結點的前一個結點，將后一個結點釋放掉，然后在置為空就可以了。

void SListPopBack(SListNode** pphead);
void SListPopBack(SListNode** pphead)
{
	assert(pphead);
	if (*pphead == NULL)
		return;
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

單鏈表頭刪

若鏈表為空，則不處理。若鏈表不為空，讓頭指針指向第二個結點，釋放掉第一個結點。

void SListPopFront(SListNode** pphead);
void SListPopFront(SListNode** pphead)
{
	assert(pphead);
	if (*pphead == NULL)//鏈表為空
		return;
	else
	{
		SListNode* head = *pphead;
		*pphead = head->next;//讓頭指針指針域中的地址指向頭指針
		free(head);//釋放第一個結點
		head = NULL;
	}
}

在pos位置之前插入數據

若pos是第一個結點，我們直接調用之前寫的頭插。若pos不是第一個結點，我們找到pos位置的前一個結點，讓新的結點指向地址為pos的結點，然后讓前一個結點指向新結點。

void SListInsertBefore(SListNode** pphead, SListNode* pos, SLTDataType x);
void SListInsertBefore(SListNode** pphead, SListNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SListPushFront(pphead,x);//頭插函數
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)//找到pos的前一個結點
		{
			prev = prev->next;
		}
		SListNode* newnode = BuySListNode(x);
		newnode->next = prev->next;//讓新結點指向pos結點
		prev->next = newnode;//讓前一個結點指向新結點
	}
}

在pos位置之后插入數據

讓新結點指向該位置的下一個位置，然后讓該位置的結點指向新結點。

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

刪除pos位置結點

void SListErase(SListNode** pphead, SListNode* pos);
void SListErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SListPopFront(pphead);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

刪除pos位置之后的結點

void SListEraseAfter(SListNode* pos);
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	SListNode* next = pos->next;
	if (next)//如果next不為空，則條件為真
	{
		pos->next = next->next;//讓pos指向要刪除位置的后一個結點
		free(next);//釋放pos的下一個結點
		next = NULL;
	}	
}

銷毀鏈表

在銷毀鏈表時。首先我們將頭指針賦值給一個新的指針，用該指針依次遍歷鏈表，先把該結點的下一個結點的地址保存，然后在釋放該結點，最后將頭指針置為空。

注意： 一定要在釋放該指針之前保存該指針的下一個結點的地址，否則就找不到下一個結點了。

void SListDestroy(SListNode** pphead);
void SListDestroy(SListNode** pphead)
{
	assert(pphead);
	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* next = cur->next;//存放下一個結點地址
		free(cur);//釋放當前結點
		cur = NULL;
	}
	*pphead = NULL;//將頭指針置為空
}

鏈表查找

SListNode* SListFind(SListNode* phead, SLTDataType x)；
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
	SListNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

提示：我們在寫鏈表的時候，盡量畫圖分析，幫助我們理清思路。

原文鏈接：https://blog.csdn.net/qq_61939403/article/details/123601114

欄目分類
最近更新