欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言中單鏈表的基本操作(創(chuàng)建、銷毀、增刪查改等)

 更新時(shí)間：2023年02月05日 10:20:16   作者：安河橋畔  
這篇文章主要介紹了C語言中單鏈表的基本操作(創(chuàng)建、銷毀、增刪查改等)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教

鏈表分類

鏈表主要有下面三種分類方法：

  • 單向或者雙向
  • 帶頭或者不帶頭
  • 循環(huán)或者非循環(huán)綜合來看鏈表有八種類型，本文主要針對(duì)的是不帶頭節(jié)點(diǎn)的非循環(huán)單鏈表。

單鏈表的介紹

typedef struct SListNode
{
	DataType data;//數(shù)據(jù)域
	struct SListNode *next;//結(jié)構(gòu)體指針，指向下一個(gè)節(jié)點(diǎn)
}SListNode;//類型別名

如圖

鏈表的每一個(gè)節(jié)點(diǎn)由數(shù)據(jù)域和指針域構(gòu)成，數(shù)據(jù)域存放數(shù)據(jù)，指針域中的指針指向下一個(gè)節(jié)點(diǎn)。

plist表示鏈表的指針，指向鏈表的第一個(gè)節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)的指針為空。

單鏈表的基本操作

創(chuàng)建

創(chuàng)建單鏈表有幾點(diǎn)需注意：

  • 鏈表與順序表的區(qū)別是，順序表是物理空間上連續(xù)的，而鏈表只在邏輯上連續(xù)，所以鏈表申請(qǐng)空間時(shí)是使用一個(gè)申請(qǐng)一個(gè)，順序表則是一次申請(qǐng)一段空間，空間不足時(shí)進(jìn)行擴(kuò)容。
  • 如果在棧上申請(qǐng)空間，在函數(shù)調(diào)用結(jié)束后會(huì)釋放，所以需要在堆區(qū)申請(qǐng)空間。
  • 每次申請(qǐng)一個(gè)節(jié)點(diǎn)都要存入數(shù)據(jù)，所以鏈表總是滿的，而順序表則可能有一段空間沒有利用。
  • 函數(shù)的返回值是指向節(jié)點(diǎn)的結(jié)構(gòu)體類型的指針
SListNode* BuySListNode(DataType x)
{
	SListNode* plist = (SListNode*)malloc(sizeof(SListNode));
	if (plist == NULL)
	{
		return NULL;//判斷是否申請(qǐng)成功
	}
	plist->data = x;
	plist->next = NULL;
	return plist;
}

打印

遍歷鏈表，進(jìn)行打印

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

尾插

尾插的操作步驟：

  • 若鏈表為空，*pplist指向新插入的節(jié)點(diǎn)
  • 鏈表不為空則遍歷鏈表，找到最后一個(gè)節(jié)點(diǎn)
  • 令最后一個(gè)節(jié)點(diǎn)的next指向新插入的節(jié)點(diǎn)
  • 新插入的節(jié)點(diǎn)next指向NULL

注意事項(xiàng)：

  • 因?yàn)椴迦朐匾淖冊(cè)湵碇兄羔樀闹赶?，故傳參時(shí)要傳入二級(jí)指針。
  • assert(pplist)是判斷鏈表是否存在，因?yàn)閜plist是指向鏈表的指針的地址，若pplist為空，說明鏈表的地址不存在，即鏈表不存在；而如果(*pplist)為空，表示的是該鏈表是空鏈表。
void SListPushBack(SListNode** pplist, DataType x)
{
	//改變指針指向，參數(shù)傳二級(jí)指針
	assert(pplist);//判斷鏈表是否存在,與鏈表是否為空不同
	//1.若鏈表為空，*pplist指向插入的節(jié)點(diǎn)
	if (*pplist == NULL)
	{
		*pplist = BuySListNode(x);
	}
	else {
		//2.鏈表不為空，指針移動(dòng)到鏈表最后一個(gè)節(jié)點(diǎn)，其next指向插入的節(jié)點(diǎn)
		SListNode* cur = *pplist;
		while (cur->next)
		{
			cur = cur->next;//cur的next為空時(shí)，cur指向最后一個(gè)節(jié)點(diǎn)
		}
		cur->next = BuySListNode(x);
	}
}

頭插

頭插操作順序：

  • 申請(qǐng)一個(gè)新節(jié)點(diǎn)
  • 新節(jié)點(diǎn)的next指向原來的第一個(gè)節(jié)點(diǎn)，即*pplist
  • 改變*pplist指向，使其指向新增的節(jié)點(diǎn)

進(jìn)行頭插時(shí)，要注意各個(gè)步驟的順序，如果直接令*pplist指向了新增的的節(jié)點(diǎn)，會(huì)導(dǎo)致原有的第一個(gè)節(jié)點(diǎn)無法找；另外，鏈表為空時(shí)的操作方法與鏈表非空時(shí)代碼可以合并，不用再分開寫各種情況。

void SListPushFront(SListNode** pplist, DataType x)
{
	assert(pplist);
	//if (NULL == *pplist)
	//{
	//	//鏈表為空
	//	*pplist = BuySListNode(x);
	//}
	//else
	//{
	//	SListNode* temp = *pplist;//temp指向鏈表原來的第一個(gè)節(jié)點(diǎn)
	//	*pplist = BuySListNode(x);//plist指向新增的節(jié)點(diǎn)
	//	(*pplist)->next = temp;//新增的節(jié)點(diǎn)指向原來的第一個(gè)節(jié)點(diǎn)
	//}
	//上面兩種情況代碼可以合并
	SListNode* node = BuySListNode(x);//申請(qǐng)一個(gè)新節(jié)點(diǎn)
	node->next = *pplist;//新增的節(jié)點(diǎn)的next指向原來的第一個(gè)節(jié)點(diǎn)
	*pplist = node;//*pplist指向新增的節(jié)點(diǎn)
}

尾刪

尾刪步驟：

  • 判斷鏈表是否為空或只有一個(gè)結(jié)點(diǎn)
  • 遍歷找到最后一個(gè)節(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)prev
  • 令prev的next指向NULL
  • 釋放原來最后一個(gè)節(jié)點(diǎn)申請(qǐng)的空間

注意事項(xiàng)：

  • 區(qū)分鏈表為空、單個(gè)結(jié)點(diǎn)、多個(gè)結(jié)點(diǎn)各種情況
  • 不能找到最后一個(gè)節(jié)點(diǎn)并將其置空，而是要找到其前驅(qū)節(jié)點(diǎn)，斷開與最后一個(gè)節(jié)點(diǎn)的連接
  • 刪除節(jié)點(diǎn)后要釋放空間，避免內(nèi)存泄漏
void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	//1.鏈表為空
	if (NULL== *pplist)
	{
		return;
	}
	//2.鏈表只有一個(gè)元素
	else if (NULL == (*pplist)->next)
	{
		free(*pplist);
		*pplist = NULL;
	}
	//3.鏈表有多個(gè)元素
	else
	{
		SListNode* prev = NULL; 
		SListNode* cur = *pplist;
		while (cur->next)
		{
			prev = cur;
			cur = cur->next;//循環(huán)結(jié)束時(shí)cur指向最后一個(gè)節(jié)點(diǎn)
		}
		//cur= NULL;//這里不能寫cur=NULL,需要找到cur的前一個(gè)節(jié)點(diǎn)，將其next置空\
		否則前一個(gè)結(jié)點(diǎn)的next依然指向原來的最后一個(gè)節(jié)點(diǎn)
		prev->next = NULL;//prev成為最后一個(gè)節(jié)點(diǎn)
		free(cur);//釋放原來最后一個(gè)節(jié)點(diǎn)的空間
	}

頭刪

頭刪的操作步驟：

  • 保存第一個(gè)節(jié)點(diǎn)的指針信息
  • 令*pplist指向第二個(gè)節(jié)點(diǎn)
  • 釋放原來的第一個(gè)節(jié)點(diǎn)的空間

同樣的，頭刪也要注意保存原來第一個(gè)節(jié)點(diǎn)的位置，否則*pplist指向改變后，原來的第一個(gè)節(jié)點(diǎn)就找不到了，會(huì)無法釋放空間造成內(nèi)存泄漏。

void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	//1.單鏈表為空
	if (NULL == *pplist)
	{
		return;
	}
	2.單鏈表有一個(gè)節(jié)點(diǎn)
	//else if (NULL == (*pplist)->next)
	//{
	//	*pplist = NULL;//刪除后鏈表為空
	//}
	3.單鏈表有多個(gè)節(jié)點(diǎn)
	//else
	//{
	//*pplist= (*pplist)->next;
	//}
	
	//兩種情況可以合并，只有一個(gè)節(jié)點(diǎn)時(shí)，*pplist的next為空
	else
	{
		SListNode* delNode = *pplist;
		*pplist = delNode->next;
		free(delNode);//釋放刪除節(jié)點(diǎn)的空間
	}
}

查找

用于查找某一元素是否存在于鏈表中，若存在則返回其第一次出現(xiàn)在鏈表中的位置，不存在則返回NULL。

遍歷時(shí)注意循環(huán)條件。

SListNode* SListFind(SListNode* plist, DataType x)
{
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return	NULL;
}

任意位置插入

pos節(jié)點(diǎn)后插入的步驟：

  • 申請(qǐng)一個(gè)新的節(jié)點(diǎn)
  • 新增節(jié)點(diǎn)的next指向原pos的next
  • pos的next指向新增的節(jié)點(diǎn)

注意事項(xiàng)

  • 任意位置的插入操作只能在給定節(jié)點(diǎn)的后面插入，前面的節(jié)點(diǎn)無法同通過給出的節(jié)點(diǎn)找到。
  • 要注意插入的操作順序，否則原來鏈表pos后的節(jié)點(diǎn)可能會(huì)找不到
void SListInsertAfter(SListNode* pos, DataType x)
{
	assert(pos);//指針合法性校驗(yàn)
	SListNode* newNode = BuySListNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}

任意位置刪除

與任意位置的插入相同，只能刪除給定節(jié)點(diǎn)pos后面的節(jié)點(diǎn)

void SListDeleteAfter(SListNode* pos)
{
	assert(pos);
	 //1.鏈表有一個(gè)節(jié)點(diǎn)
	if (NULL == pos->next)
	{
		return;
	}
	//2.鏈表有多個(gè)節(jié)點(diǎn)
	else
	{
		SListNode* temp = pos->next;
		pos->next = temp->next;
		free(temp);
	}
}

銷毀

鏈表的銷毀，遍歷一遍，逐個(gè)釋放空間

void SListDestroy(SListNode** pplist)
{
	assert(pplist);//鏈表是否存在
	//1.鏈表為空
	if (NULL == *pplist)
	{
		return;
	}
	else
	{
		SListNode* cur = NULL;
		while (*pplist)
		{
			cur = *pplist;
			*pplist = (*pplist)->next;
			free(cur);
		}
	}
}

完整代碼

work.h

頭文件包含，函數(shù)聲明，定義結(jié)構(gòu)體

#pragma once
#include<stdio.h>
#include<Windows.h> 
#include<assert.h>
#include<assert.h>

typedef int DataType;
typedef struct SListNode
{
	DataType data;//數(shù)據(jù)域
	struct SListNode *next;//結(jié)構(gòu)體指針，指向下一個(gè)節(jié)點(diǎn)
}SListNode;//類型別名

//函數(shù)聲明
SListNode* BuySListNode(DataType x);//節(jié)點(diǎn)申請(qǐng)
void SListPrint(SListNode* pst);//單鏈表遍歷打印
void SListPushBack(SListNode** pplist, DataType x);//單鏈表尾插
void SListPushFront(SListNode** pplist, DataType x);//單鏈表頭插
void SListPopBack(SListNode** pplist);//單鏈表尾刪
void SListPopFront(SListNode** pplist);//單鏈表頭刪
SListNode* SListFind(SListNode* plist, DataType x);//單鏈表查找
void SListInsertAfter(SListNode* pos, DataType x);//pos后位置的插入
void SListDeleteAfter(SListNode* pos);//pos后位置的刪除
void SListDestroy(SListNode** pplist);//釋放鏈表空間

work.c

各操作函數(shù)的具體實(shí)現(xiàn)

#include"work.h"

//鏈表與順序表的區(qū)別是，順序表是物理空間上連續(xù)的
//而鏈表只在邏輯上連續(xù)，所以鏈表申請(qǐng)空間時(shí)是使用一個(gè)申請(qǐng)一個(gè)
//順序表則是一次申請(qǐng)一段空間
SListNode* BuySListNode(DataType x)
{
	//若在棧申請(qǐng)內(nèi)存函數(shù)調(diào)用結(jié)束后會(huì)釋放，所以使用動(dòng)態(tài)申請(qǐng)
	SListNode* plist = (SListNode*)malloc(sizeof(SListNode));
	if (plist == NULL)
	{
		return NULL;//判斷是否申請(qǐng)成功
	}
	plist->data = x;
	plist->next = NULL;
	return plist;
}

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

//尾插法
void SListPushBack(SListNode** pplist, DataType x)
{
	//改變指針指向，參數(shù)傳二級(jí)指針
	assert(pplist);//判斷鏈表是否存在,與鏈表是否為空不同

	//1.若鏈表為空，*pplist指向插入的節(jié)點(diǎn)
	if (*pplist == NULL)
	{
		*pplist = BuySListNode(x);
	}
	else {
		//2.鏈表不為空，指針移動(dòng)到鏈表最后一個(gè)節(jié)點(diǎn)，其next指向插入的節(jié)點(diǎn)
		SListNode* cur = *pplist;
		while (cur->next)
		{
			cur = cur->next;//cur的next為空時(shí)，cur指向最后一個(gè)節(jié)點(diǎn)
		}
		cur->next = BuySListNode(x);
	}
}

//頭插法
void SListPushFront(SListNode** pplist, DataType x)
{
	assert(pplist);
	//if (NULL == *pplist)
	//{
	//	//鏈表為空
	//	*pplist = BuySListNode(x);
	//}
	//else
	//{
	//	SListNode* temp = *pplist;//temp指向鏈表原來的第一個(gè)節(jié)點(diǎn)
	//	*pplist = BuySListNode(x);//plist指向新增的節(jié)點(diǎn)
	//	(*pplist)->next = temp;//新增的節(jié)點(diǎn)指向原來的第一個(gè)節(jié)點(diǎn)
	//}

	//鏈表為空的情況可以和不為空合并
	SListNode* node = BuySListNode(x);//申請(qǐng)一個(gè)新節(jié)點(diǎn)
	node->next = *pplist;//新增的節(jié)點(diǎn)的next指向原來的第一個(gè)節(jié)點(diǎn)
	*pplist = node;//*pplist指向新增的節(jié)點(diǎn)

}

//尾刪法？
void SListPopBack(SListNode** pplist)
{
	assert(pplist);

	//1.鏈表為空
	if (NULL== *pplist)
	{
		return;
	}
	//2.鏈表只有一個(gè)元素
	else if (NULL == (*pplist)->next)
	{
		free(*pplist);
		*pplist = NULL;
	}
	//3.鏈表有多個(gè)元素
	else
	{
		SListNode* prev = NULL; 
		SListNode* cur = *pplist;
		while (cur->next)
		{
			prev = cur;
			cur = cur->next;//循環(huán)結(jié)束時(shí)cur指向最后一個(gè)節(jié)點(diǎn)
		}
		//cur= NULL;//這里不能寫cur=NULL,需要找到cur的前一個(gè)節(jié)點(diǎn)，將其next置空\
		否則前一個(gè)結(jié)點(diǎn)的next依然指向原來的最后一個(gè)節(jié)點(diǎn)
		prev->next = NULL;//prev最后一個(gè)節(jié)點(diǎn)
		free(cur);//釋放原來最后一個(gè)節(jié)點(diǎn)的空間
	}
}

//頭刪
void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	//1.單鏈表為空
	if (NULL == *pplist)
	{
		return;
	}
	2.單鏈表有一個(gè)節(jié)點(diǎn)
	//else if (NULL == (*pplist)->next)
	//{
	//	*pplist = NULL;//刪除后鏈表為空
	//}
	3.單鏈表有多個(gè)節(jié)點(diǎn)
	//else
	//{
	//*pplist= (*pplist)->next;
	//}
	
	//兩種情況可以合并，只有一個(gè)節(jié)點(diǎn)時(shí)，*pplist的next為空
	else
	{
		SListNode* delNode = *pplist;
		*pplist = delNode->next;
		free(delNode);//釋放刪除節(jié)點(diǎn)的空間
	}
}

//單鏈表查找
SListNode* SListFind(SListNode* plist, DataType x)
{
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return	NULL;
	
}
//任意位置的插入
//只能在pos的后面插入
void SListInsertAfter(SListNode* pos, DataType x)
{
	assert(pos);//指針合法性校驗(yàn)
	SListNode* newNode = BuySListNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}
		

//任意位置的刪除
//只能刪除給定的pos后面的節(jié)點(diǎn)
void SListDeleteAfter(SListNode* pos)
{
	assert(pos);
	 //1.鏈表有一個(gè)節(jié)點(diǎn)
	if (NULL == pos->next)
	{
		return;
	}
	//2.鏈表有多個(gè)節(jié)點(diǎn)
	else
	{
		SListNode* temp = pos->next;
		pos->next = temp->next;
		free(temp);
	}
}

// 鏈表空間釋放
void SListDestroy(SListNode** pplist)
{
	assert(pplist);//鏈表是否存在
	//1.鏈表為空
	if (NULL == *pplist)
	{
		return;
	}
	else
	{
		SListNode* cur = NULL;
		while (*pplist)
		{
			cur = *pplist;
			*pplist = (*pplist)->next;
			free(cur);
		}
	}
}

main.c

程序入口，測(cè)試用例

#include"work.h"
void Test()
{
	SListNode* node = NULL;//定義一個(gè)結(jié)構(gòu)體指針
	//尾插法插入五個(gè)節(jié)點(diǎn)
	SListPushBack(&node, 1);
	SListPushBack(&node, 2);
	SListPushBack(&node, 3);
	SListPushBack(&node, 4);
	SListPushBack(&node, 5);
	SListPrint(node);//遍歷打印
	SListPushFront(&node, 0);//頭插一個(gè)節(jié)點(diǎn)
	SListPrint(node);//遍歷打印
	SListPopBack(&node);//尾刪最后一個(gè)節(jié)點(diǎn)
	SListPrint(node);//遍歷打印
	SListPopFront(&node);//頭刪第一個(gè)節(jié)點(diǎn)
	SListPrint(node);//遍歷打印
	printf("%p\n",  SListFind(node, 4));//查找3在鏈表中的位置
	printf("%p\n",  SListFind(node, 99));//查找99在鏈表中的位置
	SListInsertAfter(SListFind(node, 4), 99);//4后面插入一個(gè)節(jié)點(diǎn)99
	SListPrint(node);//遍歷打印
	SListDeleteAfter(SListFind(node, 4));//刪除4的下一個(gè)節(jié)點(diǎn)
	SListPrint(node);//遍歷打印
}

int main()
{
	Test();
	system("pause");
	return 0;
}

總結(jié)

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

相關(guān)文章

最新評(píng)論