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

老生常談C語言鏈表小結(jié)

 更新時間：2021年11月09日 09:21:44   作者：會掉發(fā)的程序員  
鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的 ，這篇文章主要介紹了C語言鏈表,需要的朋友可以參考下

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

概念

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

結(jié)構(gòu)

代碼

struct Slist
{
	int* a;
	struct Slist* next;
};

邏輯結(jié)構(gòu):

在這里插入圖片描述

物理結(jié)構(gòu)：

在這里插入圖片描述

注意:

  • 從上圖可以看出，鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上是連續(xù)的，但是在物理上是不一定是連續(xù)的。
  • 這些結(jié)點一般是從堆上申請出來的。
  • 從堆上申請的空間，是按照一定的策劃來分配的，兩次申請的空間可能連續(xù)，大概率是不連續(xù)的。

鏈表的分類

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

1. 單向或者雙向
①單向

在這里插入圖片描述

②雙向

在這里插入圖片描述

2.帶頭或者不帶頭
①帶頭

在這里插入圖片描述

②不帶頭

在這里插入圖片描述

3.循環(huán)或者非循環(huán)
①循環(huán)

在這里插入圖片描述

②非循環(huán)

在這里插入圖片描述

雖然有這么多種結(jié)構(gòu)的鏈表，但是我們實際中最常用的只有兩種結(jié)構(gòu):
1. 無頭單向非循環(huán)鏈表

在這里插入圖片描述

2.帶頭雙向循環(huán)鏈表

在這里插入圖片描述

1. 無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。

2. 帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢，實現(xiàn)反而簡單了，后面我們代碼實現(xiàn)了就知道了。

單鏈表的實現(xiàn)（無頭）

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

typedef int SLTDateType;

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

單鏈表需要的功能

// 動態(tài)申請一個節(jié)點
SListNode* BuySListNode(SLTDateType x);
// 單鏈表打印
void SListPrint(SListNode* plist);
// 單鏈表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 單鏈表的頭插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 單鏈表的尾刪
void SListPopBack(SListNode** pplist);
// 單鏈表頭刪
void SListPopFront(SListNode** pplist);
// 單鏈表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 單鏈表在pos位置之后插入x
// 分析思考為什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 單鏈表刪除pos位置之后的值
// 分析思考為什么不刪除pos位置？
void SListEraseAfter(SListNode* pos);
// 單鏈表的銷毀
void SListDestory(SListNode** pplist);

功能實現(xiàn)

SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		exit(-1);
	}
	newnode->data = x;
	return newnode;
}

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

void SListPushBack(SListNode** pplist, SLTDateType x)
{
	SListNode* tail = *pplist;
	SListNode* newnode = BuySListNode(x);
	newnode->next = NULL;
	if (tail == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

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

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

void SListPopFront(SListNode** pplist)
{
	assert(*pplist);
	SListNode* front = *pplist;
	*pplist = front->next;
	free(front);
	front = NULL;
}

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	assert(plist);
	SListNode* pos = plist;
	while (pos && pos->data != x)
	{
		pos = pos->next;
	}
	return pos;
}

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

void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);
	SListNode* node = pos->next;
	pos->next = node->next;
	free(node);
}

void SListDestory(SListNode** pplist)
{
	SListNode* node = *pplist;
	SListNode* PreNode = NULL;
	while (node)
	{
		PreNode = node->next;
		free(node);
		node = PreNode;
	}
}

雙向鏈表的實現(xiàn)

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

SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		exit(-1);
	}
	newnode->data = x;
	return newnode;
}

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

void SListPushBack(SListNode** pplist, SLTDateType x)
{
	SListNode* tail = *pplist;
	SListNode* newnode = BuySListNode(x);
	newnode->next = NULL;
	if (tail == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

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

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

void SListPopFront(SListNode** pplist)
{
	assert(*pplist);
	SListNode* front = *pplist;
	*pplist = front->next;
	free(front);
	front = NULL;
}

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	assert(plist);
	SListNode* pos = plist;
	while (pos && pos->data != x)
	{
		pos = pos->next;
	}
	return pos;
}

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

void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);
	SListNode* node = pos->next;
	pos->next = node->next;
	free(node);
}

void SListDestory(SListNode** pplist)
{
	SListNode* node = *pplist;
	SListNode* PreNode = NULL;
	while (node)
	{
		PreNode = node->next;
		free(node);
		node = PreNode;
	}
}

雙向鏈表的功能

//創(chuàng)建鏈表返回頭結(jié)點
LTNode* ListInit();
// 雙向鏈表銷毀
void ListDestory(LTNode* phead);
// 雙向鏈表打印
void ListPrint(LTNode* phead);

// 雙向鏈表尾插
void ListPushBack(LTNode* phead, LTDateType x);
// 雙向鏈表尾刪
void ListPopBack(LTNode* phead);
// 雙向鏈表頭插
void ListPushFront(LTNode* phead, LTDateType x);
// 雙向鏈表頭刪
void ListPopFront(LTNode* phead);
// 雙向鏈表查找
LTNode* ListFind(LTNode* phead, LTDateType x);
// 雙向鏈表在pos的前面進(jìn)行插入
void ListInsert(LTNode* pos, LTDateType x);
// 雙向鏈表刪除pos位置的節(jié)點
void ListErase(LTNode* pos);

功能實現(xiàn)

LTNode* ListInit()
{
	//哨兵位頭結(jié)點
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	if (phead == NULL)
	{
		printf("開辟空間失敗!!!\n");
		exit(-1);
	}
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead;
	LTNode* p = NULL;
	LTNode* tail = phead->prev;
	while (cur != tail)
	{
		p = cur;
		cur = cur->next;
		free(p);
	}
	free(tail);
}

void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* front = phead->next;
	while (front != phead)
	{
		printf("%d ", front->data);
		front = front->next;
	}
	printf("\n");
}

void ListPushBack(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("開辟空間失敗!!\n");
		exit(-1);
	}
	newnode->data = x;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead != phead->next);
	LTNode* tail = phead->prev;
	LTNode* TailFront = tail->prev;
	TailFront->next = phead;
	phead->prev = TailFront;
	free(tail);
}

void ListPushFront(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* next = phead->next;
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("開辟空間失敗!!\n");
		exit(-1);
	}
	newnode->data = x;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;
}

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead != phead->next);
	LTNode* head = phead->next;//頭結(jié)點
	phead->next = head->next;
	head->next->prev = phead;
	free(head);
}

LTNode* ListFind(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

void ListInsert(LTNode* pos, LTDateType x)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("開辟空間失敗!!\n");
		exit(-1);
	}
	newnode->data = x;
	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}

總結(jié):鏈表和順序表的區(qū)別

不同點 順序表 鏈表存儲空間上物理上一定連續(xù)邏輯上連續(xù)，物理上不一定連續(xù)隨機(jī)訪問支持不支持任意位置上插入或者刪除元素可能需要移動元素，效率低下只需修改指針指向插入動態(tài)順序表，空間不夠時需要擴(kuò)容沒有容量的概念應(yīng)用場景元素高效存儲+頻繁訪問任意位置插入和刪除頻繁

到此這篇關(guān)于C語言鏈表的文章就介紹到這了,更多相關(guān)C語言鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

  • 統(tǒng)計C語言二叉樹中葉子結(jié)點個數(shù)

    統(tǒng)計C語言二叉樹中葉子結(jié)點個數(shù)

    這篇文章主要介紹的是統(tǒng)計C語言二叉樹中葉子結(jié)點個數(shù)，文章以C語言二叉樹中葉子結(jié)點為基礎(chǔ)分享一個簡單小栗子講解，具有一定的知識參考價值，需要的小伙伴可以參考一下
    2022-02-02
  • C++實現(xiàn)地鐵自動售票系統(tǒng)程序設(shè)計

    C++實現(xiàn)地鐵自動售票系統(tǒng)程序設(shè)計

    這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)地鐵自動售票系統(tǒng)程序設(shè)計，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2022-03-03
  • C++類與對象深入之引用與內(nèi)聯(lián)函數(shù)與auto關(guān)鍵字及for循環(huán)詳解

    C++類與對象深入之引用與內(nèi)聯(lián)函數(shù)與auto關(guān)鍵字及for循環(huán)詳解

    朋友們好,這篇播客我們繼續(xù)C++的初階學(xué)習(xí)，現(xiàn)在對一些C++的入門知識做了些總結(jié)，整理出來一篇博客供我們一起復(fù)習(xí)和學(xué)習(xí),如果文章中有理解不當(dāng)?shù)牡胤?還希望朋友們在評論區(qū)指出,我們相互學(xué)習(xí),共同進(jìn)步
    2022-06-06
  • QT實現(xiàn)單詞檢索軟件的示例代碼

    QT實現(xiàn)單詞檢索軟件的示例代碼

    本文主要介紹了QT實現(xiàn)單詞檢索軟件的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2022-01-01
  • C語言光標(biāo)信息CONSOLE_CURSOR_INFO類型詳解

    C語言光標(biāo)信息CONSOLE_CURSOR_INFO類型詳解

    本文詳細(xì)講解了C語言光標(biāo)信息CONSOLE_CURSOR_INFO類型，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2021-12-12
  • 淺談分詞器Tokenizer

    淺談分詞器Tokenizer

    分詞器的工作就是分解文本流成詞(tokens).在這個文本中,每一個token都是這些字符的一個子序列。一個分析器(analyzer)必須知道它所配置的字段,但是tokenizer不需要,分詞器(tokenizer)從一個字符流(reader)讀取數(shù)據(jù),生成一個Token對象(TokenStream)的序列
    2021-06-06
  • C++中訪問權(quán)限的示例詳解

    C++中訪問權(quán)限的示例詳解

    C++通過 public、protected、private 三個關(guān)鍵字來控制成員變量和成員函數(shù)的訪問權(quán)限(也稱為可見性),下面這篇文章主要給大家介紹了關(guān)于C++中訪問權(quán)限的相關(guān)資料,需要的朋友可以參考下
    2021-07-07
  • 最新VScode C/C++ 環(huán)境配置的詳細(xì)教程

    最新VScode C/C++ 環(huán)境配置的詳細(xì)教程

    這篇文章主要介紹了最新VScode C/C++ 環(huán)境配置的詳細(xì)教程,本文通過圖文并茂的形式給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下
    2020-11-11
  • Reactor反應(yīng)器的實現(xiàn)方法詳解

    Reactor反應(yīng)器的實現(xiàn)方法詳解

    本篇文章是對Reactor反應(yīng)器的實現(xiàn)方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
    2013-05-05
  • 詳解C++中十六進(jìn)制字符串轉(zhuǎn)數(shù)字（數(shù)值）

    詳解C++中十六進(jìn)制字符串轉(zhuǎn)數(shù)字（數(shù)值）

    這篇文章主要介紹了詳解C++中十六進(jìn)制字符串轉(zhuǎn)數(shù)字（數(shù)值）的相關(guān)資料,這里提供兩種實現(xiàn)方法，需要的朋友可以參考下
    2017-08-08

最新評論