国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁
  2. >Toy博客

【（數(shù)據(jù)結(jié)構(gòu)）— 單鏈表的實現(xiàn)】

2年前作者：圥忈ゼ分類：Toy博客閱讀(101)違法舉報

這篇具有很好參考價值的文章主要介紹了【（數(shù)據(jù)結(jié)構(gòu)）— 單鏈表的實現(xiàn)】。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

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

概念： 鏈表是?種 物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的 。
【（數(shù)據(jù)結(jié)構(gòu)）— 單鏈表的實現(xiàn)】,# 數(shù)據(jù)結(jié)構(gòu),C語言,# 鏈表,數(shù)據(jù)結(jié)構(gòu),鏈表,C語言

鏈表的結(jié)構(gòu)跟???廂相似，淡季時?次的?廂會相應(yīng)減少，旺季時?次的?廂會額外增加?節(jié)。只需要將???的某節(jié)?廂去掉/加上，不會影響其他?廂，每節(jié)?廂都是獨?存在的。
?廂是獨?存在的，且每節(jié)?廂都有??。想象?下這樣的場景，假設(shè)每節(jié)?廂的??都是鎖上的狀態(tài)，需要不同的鑰匙才能解鎖，每次只能攜帶?把鑰匙的情況下如何從?頭?到?尾？

最簡單的做法：每節(jié)?廂?都放?把下?節(jié)?廂的鑰匙。

在鏈表?，每節(jié)“?廂”是什么樣的呢？

【（數(shù)據(jù)結(jié)構(gòu)）— 單鏈表的實現(xiàn)】,# 數(shù)據(jù)結(jié)構(gòu),C語言,# 鏈表,數(shù)據(jù)結(jié)構(gòu),鏈表,C語言

與順序表不同的是，鏈表?的每節(jié)"?廂"都是獨?申請下來的空間，我們稱之為“結(jié)點/節(jié)點”
節(jié)點的組成主要有兩個部分：當(dāng)前節(jié)點要保存的數(shù)據(jù)和保存下?個節(jié)點的地址（指針變量）。
圖中指針變量 plist保存的是第?個節(jié)點的地址，我們稱plist此時“指向”第?個節(jié)點，如果我們希望plist“指向”第?個節(jié)點時，只需要修改plist保存的內(nèi)容為0x0012FFA0。
為什么還需要指針變量來保存下?個節(jié)點的位置？
鏈表中每個節(jié)點都是獨?申請的（即需要插?數(shù)據(jù)時才去申請?塊節(jié)點的空間），我們需要通過指針變量來保存下?個節(jié)點位置才能從當(dāng)前節(jié)點找到下?個節(jié)點。
結(jié)合前?學(xué)到的結(jié)構(gòu)體知識，我們可以給出每個節(jié)點對應(yīng)的結(jié)構(gòu)體代碼：
假設(shè)當(dāng)前保存的節(jié)點為整型：

struct SListNode
{
 int data; //節(jié)點數(shù)據(jù)
 struct SListNode* next; //指針變量?保存下?個節(jié)點的地址
};

當(dāng)我們想要保存?個整型數(shù)據(jù)時，實際是向操作系統(tǒng)申請了?塊內(nèi)存，這個內(nèi)存不僅要保存整型數(shù)據(jù)，也需要保存下?個節(jié)點的地址（當(dāng)下?個節(jié)點為空時保存的地址為空）。
當(dāng)我們想要從第?個節(jié)點?到最后?個節(jié)點時，只需要在前?個節(jié)點拿上下?個節(jié)點的地址（下?個節(jié)點的鑰匙）就可以了。

給定的鏈表結(jié)構(gòu)中，如何實現(xiàn)節(jié)點從頭到尾的打?。?/p>

【（數(shù)據(jù)結(jié)構(gòu)）— 單鏈表的實現(xiàn)】,# 數(shù)據(jù)結(jié)構(gòu),C語言,# 鏈表,數(shù)據(jù)結(jié)構(gòu),鏈表,C語言

【（數(shù)據(jù)結(jié)構(gòu)）— 單鏈表的實現(xiàn)】,# 數(shù)據(jù)結(jié)構(gòu),C語言,# 鏈表,數(shù)據(jù)結(jié)構(gòu),鏈表,C語言

思考：當(dāng)我們想保存的數(shù)據(jù)類型為字符型、浮點型或者其他?定義的類型時，該如何修改？
補充說明：
1、鏈?zhǔn)綑C構(gòu)在邏輯上是連續(xù)的，在物理結(jié)構(gòu)上不?定連續(xù)
2、節(jié)點?般是從堆上申請的
3、從堆上申請來的空間，是按照?定策略分配出來的，每次申請的空間可能連續(xù)，可能不連續(xù)

二.單鏈表的實現(xiàn)

2.1單鏈表頭文件——功能函數(shù)的定義

SList.h

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

//創(chuàng)建鏈表節(jié)點結(jié)構(gòu)
typedef int SLDatatype;
typedef struct SListNode
{
	SLDatatype data;//要保存的數(shù)據(jù)
	struct SListNode* next;
}SLNode;

//創(chuàng)建幾個節(jié)點組成鏈表，并且打印鏈表
//打印
void SLNPrint(SLNode* phead);

//尾插
void SLNPushBack(SLNode** pphead, SLDatatype x);
//頭插
void SLNPushFront(SLNode** pphead, SLDatatype x);
//尾刪
void SLNPopBack(SLNode** pphead); 
//頭刪
void SLNPopFront(SLNode** pphead);
//在指定位置插入刪除
// 
//查找指定的pos
SLNode* SLNFind(SLNode** pphead, SLDatatype x);
//在指定位置之前插入
void SLNInsrt(SLNode** pphead, SLNode* pos, SLDatatype x);
//在指定位置之后插入刪除
void SLNInsrtAfter(SLNode* pos, SLDatatype x);
//刪除指定位置的數(shù)據(jù)
void SLNErase(SLNode** pphead, SLNode* pos);
//刪除指定位置之后的數(shù)據(jù)
void SLNEraseAfter(SLNode* pos);
//銷毀鏈表
void SLNDestroy(SLNode** pphead);

2.2單鏈表源文件——功能函數(shù)的實現(xiàn)

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
//打印
void SLNPrint(SLNode* phead)
{
	//循環(huán)打印
	//可以用phead直接來訪問，但是注意，當(dāng)代碼走到
	//第16行的時候，此時phead已經(jīng)變成NULL了
	//若代碼沒寫完，我還要繼續(xù)使用指向第一個節(jié)點的地址時，這時我就
	//找不到第一個節(jié)點的地址
	//所以為了避免第一個節(jié)點被更改，要定義一個新的來代替
	SLNode* pcur = phead;
	while (pcur)
	{
		printf("%d ->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
//創(chuàng)建新的節(jié)點
SLNode* SLByNode(SLDatatype x)
{
	//開辟新的空間
	SLNode* node = (SLNode*)malloc(sizeof(SLNode));
	node->data = x;
	node->next = NULL;
	return node;
}
//尾插
void SLNPushBack(SLNode** pphead, SLDatatype x)
{
	SLNode* node = SLByNode(x);
	//判斷鏈表是否為空，如果為空，直接插入
	if (*pphead == NULL)
	{
		*pphead = node;
		return;
	}

	//說明鏈表不為空 ,找尾
	SLNode* pcur = *pphead;
	while (pcur->next != NULL)
	{
		pcur = pcur->next;
	}
	pcur->next = node;

}

//頭插
void SLNPushFront(SLNode** pphead, SLDatatype x)
{
	//創(chuàng)建新的節(jié)點
	SLNode* node = SLByNode(x);
	//讓新的節(jié)點跟頭節(jié)點連起來
	node->next = *pphead;
	//再讓新節(jié)點成為頭節(jié)點
	*pphead = node;
	
}

//尾刪
void SLNPopBack(SLNode** pphead)
{
	//先判斷鏈表是否為空，如果為空就無法進行刪除操作
	assert(pphead);
	//還要判斷第一個節(jié)點不能為空
	assert(*pphead);
	//只有一個節(jié)點的情況
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//有多個節(jié)點的情況
	//先找到尾節(jié)點/尾節(jié)點的前一個節(jié)點
	SLNode* ptail = *pphead;
	SLNode* prev = NULL;
	while (ptail->next)
	{
		prev = ptail;
		ptail = prev->next;
	}
	//讓尾節(jié)點的前一個節(jié)點指向不再指向尾節(jié)點，而是指向尾節(jié)點的下一個節(jié)點 
	prev->next = ptail->next;
	//然后在刪除尾節(jié)點
	free(ptail);
	//為什么要將ptaii置為空指針？代碼后面明明沒有再使用ptail,因為打印鏈表的代碼有判斷節(jié)點的地址是否為空
	ptail = NULL;

}

void SLNPopFront(SLNode** pphead)
{
	//判斷鏈表不能為空
	assert(pphead);
	//判斷頭節(jié)點不能為空
	assert(*pphead);
	SLNode* del = *pphead;
	*pphead = (*pphead)->next;
	free(del);
	//出于代碼規(guī)范
	del = NULL;

}


//查找指定的pos
SLNode* SLNFind(SLNode** pphead, SLDatatype x)
{
	assert(pphead);
	SLNode* pcur = *pphead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//出循環(huán)，代表沒找到
	return NULL;
}
//在指定位置之前插入
void SLNInsrt(SLNode** pphead, SLNode* pos, SLDatatype x)
{
	SLNode* node = SLByNode(x);
	assert(pphead);
	assert(*pphead);
	//只有一個節(jié)點的情況 == pos就是頭節(jié)點,直接進行頭插
	if (pos == *pphead)
	{
		node->next = *pphead;
		*pphead = node;
		return;
	}
	//有多個節(jié)點的情況
	//找pos的前一個節(jié)點
	SLNode* prev = *pphead;
	while (prev->next != pos)
	{

		prev = prev->next;
	}
	//這里的插入節(jié)點的處理順序可以調(diào)換
	prev->next = node;
	node->next = pos;

}

//在指定的位置之后插入
void SLNInsrtAfter(SLNode* pos, SLDatatype x)
{
	assert(pos);
	SLNode* node = SLByNode(x);
	// node  pos  node->next
	node->next = pos->next;
	pos->next = node;
}

//刪除指定位置的節(jié)點
void SLNErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	if (pos == *pphead)
	{
		*pphead = (*pphead)->next;
		free(pos);
		return;
	}

	//找pos的前一個節(jié)點
	SLNode* prev = *pphead;

	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = pos->next;
	free(pos);
	pos = NULL;
	
}
//刪除指定位置之后的節(jié)點
void SLNEraseAfter(SLNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

//銷毀鏈表
void SLNDestroy(SLNode** pphead)
{
	assert(*pphead);
	SLNode* pcur = *pphead;
	while (pcur)
	{
		SLNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

2.3 單鏈表源文件——功能的測試

test.c

#include"SList.h"



void sllist()
{
	SLNode* node1 = (SLNode*)malloc(sizeof(SLNode));
	node1->data = 1;
	SLNode* node2 = (SLNode*)malloc(sizeof(SLNode));
	node2->data = 2;
	SLNode* node3 = (SLNode*)malloc(sizeof(SLNode));
	node3->data = 3;
	SLNode* node4 = (SLNode*)malloc(sizeof(SLNode));
	node4->data = 4;


	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;


	SLNode* plist = node1;
	SLNPrint(plist);
	
	

}
void sllist01()
{
	SLNode* plist = NULL;
	//尾插
	SLNPushBack(&plist, 1);
	SLNPushBack(&plist, 2);
	SLNPushBack(&plist, 3);
	SLNPushBack(&plist, 4);
	//頭插 
	/*SLNPushFront(&plist, 1);
	SLNPushFront(&plist, 2);
	SLNPushFront(&plist, 3);
	SLNPushFront(&plist, 4);*/
	//尾刪
	//SLNPopBack(&plist);
	//頭刪
	//SLNPopFront(&plist);

	//在指定位置前插入
	//查找指定的pos
	SLNode* find = SLNFind(&plist, 3);
	//SLNInsrt(&plist, find, 11);
	//在指定位置之后插入
	//SLNInsrtAfter(find, 5);
	//刪除指定位置的節(jié)點
	//SLNErase(&plist, find);
	//刪除指定位置之后的節(jié)點
	//SLNEraseAfter(find);
	//銷毀鏈表
	SLNDestroy(&plist);
	SLNPrint(plist);//打印鏈表
}

2.4單鏈表測試結(jié)果運行展示

1.尾部插入
【（數(shù)據(jù)結(jié)構(gòu)）— 單鏈表的實現(xiàn)】,# 數(shù)據(jù)結(jié)構(gòu),C語言,# 鏈表,數(shù)據(jù)結(jié)構(gòu),鏈表,C語言

2.頭部插入
【（數(shù)據(jù)結(jié)構(gòu)）— 單鏈表的實現(xiàn)】,# 數(shù)據(jù)結(jié)構(gòu),C語言,# 鏈表,數(shù)據(jù)結(jié)構(gòu),鏈表,C語言

3.尾部/頭部刪除
【（數(shù)據(jù)結(jié)構(gòu)）— 單鏈表的實現(xiàn)】,# 數(shù)據(jù)結(jié)構(gòu),C語言,# 鏈表,數(shù)據(jù)結(jié)構(gòu),鏈表,C語言

4.在指定位置前插入
【（數(shù)據(jù)結(jié)構(gòu)）— 單鏈表的實現(xiàn)】,# 數(shù)據(jù)結(jié)構(gòu),C語言,# 鏈表,數(shù)據(jù)結(jié)構(gòu),鏈表,C語言

5.在指定位置后插入
【（數(shù)據(jù)結(jié)構(gòu)）— 單鏈表的實現(xiàn)】,# 數(shù)據(jù)結(jié)構(gòu),C語言,# 鏈表,數(shù)據(jù)結(jié)構(gòu),鏈表,C語言

6.刪除指定位置的節(jié)點
【（數(shù)據(jù)結(jié)構(gòu)）— 單鏈表的實現(xiàn)】,# 數(shù)據(jù)結(jié)構(gòu),C語言,# 鏈表,數(shù)據(jù)結(jié)構(gòu),鏈表,C語言

7.刪除指定位置之后的節(jié)點
【（數(shù)據(jù)結(jié)構(gòu)）— 單鏈表的實現(xiàn)】,# 數(shù)據(jù)結(jié)構(gòu),C語言,# 鏈表,數(shù)據(jù)結(jié)構(gòu),鏈表,C語言

8.銷毀鏈表
【（數(shù)據(jù)結(jié)構(gòu)）— 單鏈表的實現(xiàn)】,# 數(shù)據(jù)結(jié)構(gòu),C語言,# 鏈表,數(shù)據(jù)結(jié)構(gòu),鏈表,C語言

3. 鏈表的分類

鏈表的結(jié)構(gòu)?常多樣，以下情況組合起來就有8種（2 x 2 x 2）鏈表結(jié)構(gòu)：
【（數(shù)據(jù)結(jié)構(gòu)）— 單鏈表的實現(xiàn)】,# 數(shù)據(jù)結(jié)構(gòu),C語言,# 鏈表,數(shù)據(jù)結(jié)構(gòu),鏈表,C語言

鏈表說明：
【（數(shù)據(jù)結(jié)構(gòu)）— 單鏈表的實現(xiàn)】,# 數(shù)據(jù)結(jié)構(gòu),C語言,# 鏈表,數(shù)據(jù)結(jié)構(gòu),鏈表,C語言
【（數(shù)據(jù)結(jié)構(gòu)）— 單鏈表的實現(xiàn)】,# 數(shù)據(jù)結(jié)構(gòu),C語言,# 鏈表,數(shù)據(jù)結(jié)構(gòu),鏈表,C語言

雖然有這么多的鏈表的結(jié)構(gòu)，但是我們實際中最常用還是兩種結(jié)構(gòu)：
單鏈表和雙向帶頭循環(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)了就知道了。
文章來源地址http://www.zghlxwxcb.cn/news/detail-716470.html

到了這里，關(guān)于【（數(shù)據(jù)結(jié)構(gòu)）— 單鏈表的實現(xiàn)】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實不符，請點擊違法舉報進行投訴反饋，一經(jīng)查實，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費用

相關(guān)文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包