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

C語言數(shù)據(jù)結(jié)構(gòu)超詳細(xì)講解單向鏈表

 更新時(shí)間：2022年03月25日 11:33:04   作者：天影云光  
鏈表可以說是一種最為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)了，而單向鏈表更是基礎(chǔ)中的基礎(chǔ)。鏈表是由一組元素以特定的順序組合或鏈接在一起的，不同元素之間在邏輯上相鄰，但是在物理上并不一定相鄰。在維護(hù)一組數(shù)據(jù)集合時(shí)，就可以使用鏈表，這一點(diǎn)和數(shù)組很相似

1.鏈表概況

1.1 鏈表的概念及結(jié)構(gòu)

概念：鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的 。

1.2 鏈表的分類

實(shí)際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來就有8種鏈表結(jié)構(gòu)

單向或者雙向

帶頭或者不帶頭

循環(huán)或者非循環(huán)

雖然有這么多的鏈表的結(jié)構(gòu)，但是我們實(shí)際中最常用還是兩種結(jié)構(gòu)

  • 無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會(huì)單獨(dú)用來存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。
  • 帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲(chǔ)數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶來很多優(yōu)勢(shì)，實(shí)現(xiàn)反而簡單了，后面我們代碼實(shí)現(xiàn)了就知道了

2. 單向鏈表的實(shí)現(xiàn)

單向鏈表結(jié)構(gòu)

2.1 SList.h（頭文件的匯總，函數(shù)的聲明）

#pragma once
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;

typedef struct SListNode
{
	int data;//數(shù)據(jù)
	struct SListNode* next;//下一個(gè)節(jié)點(diǎn)的地址
}SListNode;

void SListPrint(SListNode* phead);//打印

SListNode* BuySListNode(SLTDataType x);//搞出一個(gè)新節(jié)點(diǎn)

void SListPushBack(SListNode** pphead, SLTDataType x);//尾插
void SListPushFront(SListNode** pphead, SLTDataType x);//頭插

void SListPopBack(SListNode** pphead);//尾刪
void SListPopFront(SListNode** pphead);//頭刪

SListNode* SListFind(SListNode* phead, SLTDataType x);//查找

void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);//在pos位置之前插入
void SListInsertAfter(SListNode* pos, SLTDataType x);//在pos位置之后插入

void SListErase(SListNode** pphead, SListNode* pos);//刪除pos位置
void SListEraseAfter(SListNode* pos);//刪除pos之后位置

void SListDestroy(SListNode** pphead);//銷毀

2.2 SList.c（函數(shù)的具體實(shí)現(xiàn)邏輯）

2.2.1 打印鏈表

//打印
void SListPrint(SListNode* phead)
{
	//assert(phead);//沒必要斷言，空鏈表也能打印
	SListNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

//test.c
void TestSList1()
{
	SListNode* slist;//結(jié)構(gòu)體指針，用于存節(jié)點(diǎn)的地址
	SListNode* n1 = (SListNode *)malloc(sizeof(SListNode));
	SListNode* n2 = (SListNode*)malloc(sizeof(SListNode));
	SListNode* n3 = (SListNode*)malloc(sizeof(SListNode));
	n1->data = 1;
	n2->data = 2;
	n3->data = 3;
	n1->next = n2;
	n2->next = n3;
	n3->next = NULL;
	slist = n1;

	SListPrint(slist);
}

2.2.2 搞出一個(gè)新節(jié)點(diǎn)（為其他函數(shù)服務(wù)）

//搞出一個(gè)新節(jié)點(diǎn)
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;
}

2.2.3 鏈表尾插

//尾插
void SListPushBack(SListNode** pphead,SLTDataType x)//會(huì)改變實(shí)參slist，要傳二級(jí)指針
{
	assert(pphead);//就算鏈表是空，它的二級(jí)指針也不為空
	SListNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//遍歷找尾
		SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

void TestSList2()
{
	SListNode* slist = NULL;
	for (int i = 0; i < 6; i++)
	{
		SListPushBack(&slist,i);
	}
	SListPrint(slist);
}

2.2.4 鏈表頭插

//頭插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
	assert(pphead);//就算鏈表是空，它的二級(jí)指針也不為空

	SListNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

void TestSList2()
{
	SListNode* slist = NULL;
	for (int i = 0; i < 6; i++)
	{
		SListPushFront(&slist,i);
	}
	SListPrint(slist);
}

2.2.5 鏈表尾刪

方法1（用兩個(gè)指針，分別找最后一個(gè)和倒數(shù)第二個(gè)）：

方法2（直接找倒數(shù)第二個(gè)）：

//尾刪
void SListPopBack(SListNode** pphead)//如果只有一個(gè)節(jié)點(diǎn)但還要尾刪，就會(huì)改變實(shí)參slist，建議傳二級(jí)指針
{
	assert(pphead);//就算鏈表是空，它的二級(jí)指針也不為空
	//三種情況：
	//1.空
	//2.一個(gè)節(jié)點(diǎn)
	//3.多個(gè)節(jié)點(diǎn)
	if (*pphead == NULL)
	{
		return;
	}

	else if ((*pphead)->next == NULL)//優(yōu)先級(jí)，記得加括號(hào)
	{
		free(*pphead);
		*pphead = NULL;
	}

	//第一種寫法（用兩個(gè)指針，分別找最后一個(gè)和倒數(shù)第二個(gè)）
	else
	{
		SListNode* prev = NULL;//找倒數(shù)第二個(gè)元素，用于將它指向NULL
		SListNode* tail = *pphead;//找尾
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;//習(xí)慣性free掉就將其置空

		prev->next = NULL;
	}

	//方法二（直接找倒數(shù)第二個(gè)）
	//else
	//{
		//SListNode* tail = *pphead;//找尾
		//while (tail->next->next != NULL)
		//{
		//	tail = tail->next;
		//}
		//free(tail->next);
		//tail->next = NULL;
	//}
}

2.2.6 鏈表頭刪

//頭刪
void SListPopFront(SListNode** pphead)
{
	assert(pphead);
	//1.空
	//2.非空
	if (*pphead == NULL)
	{
		return;
	}
	else
	{
		SListNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
}

2.2.7 查找節(jié)點(diǎn)

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

2.2.8 在pos位置之前插入

//在pos位置之前插入（一般跟find配合使用）
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);//間接檢測(cè)鏈表是否為空，因?yàn)榭真湵碚也坏絧os
	//1.pos是第一個(gè)節(jié)點(diǎn)（頭插）
	//2.pos不是第一個(gè)節(jié)點(diǎn)
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SListNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

2.2.9 在pos位置之后插入

方法1：兩個(gè)指針，先連接pos和newnode還是先連接newnode和next都行

方法2：只有一個(gè)指針，一定要先通過pos連接newnode和下一個(gè)，再連接pos和newnode，否則會(huì)找不到下一個(gè)的地址。

//在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	SListNode* next = pos->next;
	newnode->next = next;//順序無所謂
	pos->next = newnode;
	//或者不定義next
	//newnode->next = pos->next;
	//pos->next = newnode;//順序要定好，否則會(huì)找不到
}

2.2.10 刪除pos位置

//刪除pos位置
void SListErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);
	assert(pos);

	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;//好習(xí)慣
	}
}

2.2.11 刪除pos之后位置

//刪除pos之后位置
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	SListNode* next = pos->next;
	if (next)//防止pos是最后一個(gè)元素
	{
		pos->next = next->next;
		free(next);
		next = NULL;
	}
}

2.2.12 鏈表銷毀

一個(gè)個(gè)找，一個(gè)個(gè)銷毀，最終將slist置空。

//銷毀
void SListDestroy(SListNode** pphead)
{
	assert(pphead);

	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

總結(jié)：單鏈表結(jié)構(gòu)，適合頭插頭刪。尾部或者中間某個(gè)位置插入刪除不適合。如果要使用鏈表單獨(dú)存儲(chǔ)數(shù)據(jù)，那我們之后會(huì)學(xué)的雙向鏈表更合適。單鏈表學(xué)習(xí)的意義：

  • 單鏈表會(huì)作為我們之后學(xué)習(xí)復(fù)雜數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)（圖的鄰接表、哈希桶）
  • 單鏈表會(huì)出很多經(jīng)典的練習(xí)題。

鏈表系列有很多重點(diǎn)內(nèi)容，我會(huì)花不少時(shí)間來跟大家講解鏈表，相信大家跟著練習(xí)的話編程嚴(yán)謹(jǐn)性會(huì)大大提升，加油哦！

到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)超詳細(xì)講解單向鏈表的文章就介紹到這了,更多相關(guān)C語言 單向鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

  • C語言中操作字符串的函數(shù)詳解

    C語言中操作字符串的函數(shù)詳解

    這篇文章主要為大家詳細(xì)介紹了C語言中操作字符串的函數(shù)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
    2022-03-03
  • C語言清楚了解指針的使用

    C語言清楚了解指針的使用

    C語言這門課程在計(jì)算機(jī)的基礎(chǔ)教學(xué)中一直占有比較重要的地位，然而要想突破C語言的學(xué)習(xí)，對(duì)指針的掌握是非常重要的，本文將具體針對(duì)指針的基礎(chǔ)做詳盡的介紹
    2022-06-06
  • C語言實(shí)現(xiàn)雙人五子棋游戲

    C語言實(shí)現(xiàn)雙人五子棋游戲

    這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)雙人五子棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
    2021-06-06
  • C++與Lua交互原理實(shí)例詳解

    C++與Lua交互原理實(shí)例詳解

    這篇文章主要介紹了C++與Lua交互原理實(shí)例詳解，有感興趣的同學(xué)可以研究下
    2021-02-02
  • C語言簡明講解變量的屬性

    C語言簡明講解變量的屬性

    我們知道以在?C?語言中的變量有自己的屬性，只要在定義變量的時(shí)候加上“屬性”關(guān)鍵字即可。“屬性”關(guān)鍵字指明變量的特有意義，但是?register?關(guān)鍵字只是請(qǐng)求寄存器變量，所以不一定會(huì)成功
    2022-04-04
  • C++圖形界面開發(fā)Qt教程:嵌套圓環(huán)示例

    C++圖形界面開發(fā)Qt教程:嵌套圓環(huán)示例

    這篇文章主要介紹了C++實(shí)現(xiàn)圖形界面開發(fā)Qt教程,涉及坐標(biāo)函數(shù)的應(yīng)用及圖形界面程序設(shè)計(jì),需要的朋友可以參考下,希望能給你帶來幫助
    2021-08-08
  • C/C++中虛函數(shù)詳解及其作用介紹

    C/C++中虛函數(shù)詳解及其作用介紹

    這篇文章主要介紹了C/C++中虛函數(shù)詳解及其作用介紹，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
    2021-09-09
  • c++中的內(nèi)聯(lián)函數(shù)inline用法實(shí)例

    c++中的內(nèi)聯(lián)函數(shù)inline用法實(shí)例

    在本篇文章里小編給大家整理的是關(guān)于c++中的內(nèi)聯(lián)函數(shù)inline用法實(shí)例以及相關(guān)知識(shí)點(diǎn)，有需要的朋友們學(xué)習(xí)下。
    2019-09-09
  • C++實(shí)現(xiàn) 單例模式實(shí)例詳解

    C++實(shí)現(xiàn) 單例模式實(shí)例詳解

    這篇文章主要介紹了C++實(shí)現(xiàn) 單例模式實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下
    2017-05-05
  • C++鏈表實(shí)現(xiàn)通訊錄管理系統(tǒng)

    C++鏈表實(shí)現(xiàn)通訊錄管理系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C++鏈表實(shí)現(xiàn)通訊錄管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
    2019-12-12

最新評(píng)論