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

<th id="mu7kb"></th>

<code id="mu7kb"><abbr id="mu7kb"></abbr></code>

<acronym id="mu7kb"></acronym>

<del id="mu7kb"></del>

<del id="mu7kb"></del>

<b id="mu7kb"><abbr id="mu7kb"></abbr></b>

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn)

2年前作者：愛寫代碼的粉毛護理分類：Toy博客閱讀(91)違法舉報

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

上篇文章介紹了數(shù)據(jù)結(jié)構(gòu)的一些基本概念，以及順序表的概念和實現(xiàn)，本文來介紹鏈表的概念和單鏈表的實現(xiàn)，在此之前，首先來回顧以下順序表的特點：

1.順序表特點回顧：

1. 順序表是一組地址連續(xù)的存儲單元依次存儲的線性表的數(shù)據(jù)結(jié)構(gòu)，邏輯上：順序表中相鄰的數(shù)據(jù)元素，其物理次序也是相鄰的。

2. 順序表的優(yōu)點：任一元素均可以隨機存取

3.順序表的缺點：進行插入和刪除操作時，需要移動大量的元素，存儲空間不靈活。

2. 鏈表的分類及概念：

2.1 鏈表的分類：

1.單鏈表：結(jié)點只有一個指針域的鏈表，稱之為鏈式線性表或者單鏈表:

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

? ?

2.雙鏈表：結(jié)點由兩個指針域的鏈表：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

3.循環(huán)鏈表：首尾相連的鏈表：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

?本文將著重介紹單鏈表，下面給出單鏈表的概念及相關(guān)特點：

2.2 單鏈表的概念即特點：

單鏈表指的是鏈表的每個結(jié)點中只包含一個指針域，對于鏈表，下面給出定義：

線性表鏈式存儲的結(jié)構(gòu)是：用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素（這組存儲單元可以連續(xù)，也可以不連續(xù)）。為了表示每個數(shù)據(jù)元素與其后記數(shù)據(jù)元素 $一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯$ 之間的邏輯關(guān)系，所以，對于存儲數(shù)據(jù)元素的存儲單元，還需要存儲一個指示后記數(shù)據(jù)元素 $一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯$ 的相關(guān)信息，（即存儲 $一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯$ 所在的地址）。這兩部分信息構(gòu)成了數(shù)據(jù)元素的存儲映像，稱為結(jié)點。

對于結(jié)點，包括了兩個域：存儲數(shù)據(jù)元素信息的域稱之為數(shù)據(jù)域，存儲后記元素存儲位置的域稱之為指針域。指針域中存儲的信息稱作指針或者鏈。個結(jié)點鏈成一個鏈表，即為線性表的鏈式存儲結(jié)構(gòu)

（注：對于鏈表更詳細的定義可以參考人民郵電出版社出版的《數(shù)據(jù)結(jié)構(gòu)》，本文不再過多說明）

3.單鏈表的代碼實現(xiàn)：

3.1 鏈表的存儲結(jié)構(gòu)及結(jié)點的創(chuàng)建：

單鏈表的定義中提到了，鏈表是由個結(jié)點構(gòu)成的，每個結(jié)點中包含了兩個與，一個是用于存儲數(shù)據(jù)元素信息的數(shù)據(jù)域，另一個是用于存儲下一個數(shù)據(jù)元素信息地址的指針域。不同類型的信息的保存，可以由結(jié)構(gòu)體進行實現(xiàn)，所以，下面用圖給出單個結(jié)點的結(jié)構(gòu)：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

其中，表示存儲的數(shù)據(jù)元素信息，表示下一個數(shù)據(jù)元素信息的地址。并且，將每一個這種結(jié)點命名為，對上述結(jié)點用代碼表示：

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;// 對應(yīng)了存儲的元素信息
	struct SListNode* next; // 對應(yīng)了下一個數(shù)據(jù)元素信息的地址
}SLTNode;

對于鏈表，也和順序表一樣，可以實現(xiàn)增刪查改各種功能，而實現(xiàn)這些功能的基礎(chǔ)，就是如何創(chuàng)造新的結(jié)點，為了解決這個問題，可以專門定義一個函數(shù)來實現(xiàn)。前面說到，鏈表各個結(jié)點之間的鏈接是通過某個結(jié)點存儲下一個結(jié)點的地址來實現(xiàn)的。所以，對于函數(shù)的返回類型，應(yīng)該定義為型，即返回結(jié)構(gòu)體的地址。

對于一個結(jié)點的創(chuàng)建，同樣可以采用在順序表中用動態(tài)內(nèi)存函數(shù)動態(tài)開辟內(nèi)存的方式進行實現(xiàn)。具體代碼如下:

SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc");
        exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

?下面給出代碼來測試函數(shù)的功能:

為了測試函數(shù)的功能，首先需要針對鏈表來封裝一個打印函數(shù)，將打印函數(shù)命名為，代碼如下：

void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
}

在鏈表的定義中說過，鏈表取任意元素必須從頭節(jié)點開始向后依次尋找。所以，為了防止頭指針的值被更改，后續(xù)無法找到第一個結(jié)點，所以，在上述代碼中，創(chuàng)建了一個新的變量用來存放頭指針中的地址。

對于這一行代碼，是用于讓保存下一個結(jié)點的地址，例如下圖中的變化所示：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

?下面，封裝一個函數(shù)來測試插入結(jié)點的功能，代碼初步表示如下：

void Testlist()
{
	printf("請輸入想要插入的元素的個數(shù)：");
	int n = 0;
	scanf("%d", &n);
	printf("請輸入插入的元素：");
	for (size_t i = 0; i < n; i++)
	{
		int val = 0;
		scanf("%d", &val);
		SLTNode* newnode = BuySListNode(val);
		
	}
}
int main()
{
	Testlist1();
	return 0;
}

但是對于上面給出的代碼，并不能完成對多個結(jié)點的數(shù)據(jù)元素的打印，因為在創(chuàng)建結(jié)點后，并沒有將前后的結(jié)點進行鏈接。同時，也并沒有出現(xiàn)上面圖中所說的頭指針。

為了建立前后結(jié)點的鏈接。所以，在上面函數(shù)中的代碼的基礎(chǔ)上，人為建立一個頭指針，定義為,賦值為。

（注：下面為了方便進行演示，對于結(jié)點之間建立的過程采用頭插的思想，但是并不等價于后面的頭插）

對于鏈接各個結(jié)點，需要分以下兩種情況：

1.頭指針為，即還未鏈接任何結(jié)點，但是已經(jīng)創(chuàng)建了一個結(jié)點：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

為了達到鏈接的效果，只需要將中存儲的地址改為新結(jié)點的地址即可。?

2.頭指針不為空：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

?此時，中已經(jīng)通過存儲第一結(jié)點的地址達到鏈接第一結(jié)點的目的，為了鏈接第二結(jié)點，需要將中存儲的地址改為第二結(jié)點的地址。

注釋中提到，為了方便演示采用頭插的思想，對于頭插，可以用下圖進行表示：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

例如，將地址為?的結(jié)點進行頭插。為了完成頭插，需要進行兩步操作：

1.將地址為0x0012ffa0的結(jié)點（即新結(jié)點）中存儲的地址改為0x0012ffb0（插入前的第一個結(jié)點）

2.將頭指針中存儲的地址改為0x0012ffa0（即新結(jié)點的地址）

對上述分析進行歸納，代碼如下：

void Testlist()
{
	printf("請輸入想要插入的元素的個數(shù)：");
	int n = 0;
	scanf("%d", &n);
	SLTNode* plist = NULL;
	printf("請輸入插入的元素：");
	for (size_t i = 0; i < n; i++)
	{
		int val = 0;
		scanf("%d", &val);
		SLTNode* newnode = BuySListNode(val);
		if (plist == NULL)
		{
			plist = newnode;
		}
		else
		{
			newnode->next = plist;
			plist = newnode;
		}
		
	}
    SLTPrint(plist);
}

其中，是一個結(jié)構(gòu)體指針，所以需要用到進行解引用。來改變新結(jié)點中存儲的下一個數(shù)據(jù)元素信息的地址。

測試效果如下：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

3.2 鏈表功能實現(xiàn)——尾插：?

定義尾插函數(shù)其內(nèi)部參數(shù)如下面代碼所示：

void SLTPushBack(SLTNode* phead, SLTDataType x);

對于尾插這一功能，首先需要找到鏈表的尾端。前面說到，頭指針對于鏈表的各種功能來說都非常重要，所以，為了保證頭指針不被更改，這里定義一個新的結(jié)構(gòu)體指針來存儲頭指針中存儲的地址。

對于如何找到尾端，下面給出一段示例的代碼：

void SLTPushBack(SLTNode* phead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	SLTNode* tail = phead;
	while (tail != NULL)
	{
		tail = tail->next;
	}
	tail = newnode;
}

上述代碼給出的思路很明確。利用循環(huán)不斷檢查指針是否為,不為空，則存儲下一個結(jié)點的指針。看似沒有錯誤。但是如果將上述過程用圖形表示，則上述代碼會引起內(nèi)存泄漏這一錯誤，具體如下：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

一開始，指針存儲了頭指針中的地址，此時,于是執(zhí)行循環(huán)內(nèi)部的代碼，此時，中存儲的地址為，效果如下圖所示：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

依次循環(huán)上述步驟：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

?再次循環(huán)上述步驟：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

?到最后一步時，指針中存儲的地址為。到這里，循環(huán)終止。已經(jīng)尋找到尾端地址。假設(shè)，在循環(huán)之前新建立的結(jié)點如下圖所示：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

如果按照上面給出的代碼來執(zhí)行，即：，則，執(zhí)行結(jié)束后，最后一個結(jié)點和指針中存儲的地址如下：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

此時，便會出現(xiàn)一個問題，即，指針是只存在與函數(shù)內(nèi)部的一個臨時變量，出函數(shù)便會銷毀。但是，最后一個結(jié)點中存儲的地址仍然為。最后一個結(jié)點和新的結(jié)點并未建立聯(lián)系。造成了內(nèi)存泄露的問題。?

因為，完成尾插的標志，便是最后一個結(jié)點存儲的地址被更改為新結(jié)點的地址。通過上面的錯誤例子?？梢缘贸鲆粋€結(jié)論。如果想要將最后一個結(jié)點存儲的地址改為新結(jié)點的地址，則，不可以讓臨時指針賦值最后一個結(jié)點中存儲的地址。應(yīng)該賦值最后一個結(jié)點的前一個結(jié)點的存儲的地址。

再通過這個結(jié)點存儲的地址，來對最后一個結(jié)點存儲的地址進行修改。所以，代碼可以更改為：
?

void SLTPushBack(SLTNode* phead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	SLTNode* tail = phead;
	while (tail ->next != NULL)
	{
		tail = tail->next;
	}
	tail -> next = newnode;
}

通過下面的測試來測試尾插的功能：

void Testlist1()
{
	printf("請輸入想要插入的元素的個數(shù)：");
	int n = 0;
	scanf("%d", &n);
	SLTNode* plist = NULL;
	printf("\n請輸入插入的元素：");
	for (size_t i = 0; i < n; i++)
	{
		int val = 0;
		scanf("%d", &val);
		SLTNode* newnode = BuySListNode(val);
		if (plist == NULL)
		{
			plist = newnode;
		}
		else
		{
			newnode->next = plist;
			plist = newnode;
		}
	}
	SLTPrint(plist);
	printf("\n");
	SLTPushBack(plist, 10000);
	SLTPrint(plist);
}

結(jié)果如下：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

上面關(guān)于尾插的代碼，只能是在有結(jié)點的情況下運行。對于頭指針為空的情況下并不適用，下面將對上面的尾插代碼進行完善：

給出下列代碼：

void SLTPushBack(SLTNode* phead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	if (phead == NULL)
	{
		phead = newnode;
	}
	SLTNode* tail = phead;
	while (tail ->next != NULL)
	{
		tail = tail->next;
	}
	tail -> next = newnode;
}

這里給出的代碼對比尾插，僅僅是多了一個對于頭指針的情況的判定。中心思想就是在頭指針時，將頭指針保存的地址改為第一個結(jié)點的地址。但是這種做法并不正確。因為這里所說的頭指針只是函數(shù)內(nèi)部的一個形式參數(shù)。真正的頭指針時上面定義的。此時，函數(shù)形式參數(shù)傳遞的時形參中保存的值，在前面關(guān)于C語言函數(shù)的文章中曾提到函數(shù)的兩個傳遞參數(shù)的方式：傳值和傳址。對于傳值調(diào)用，并不能改變外部變量的值。所以，這里雖然對頭指針存儲的地址進行改變。但是卻沒有真正的改變函數(shù)外部實際參數(shù)中保存的地址。

對于上面的錯誤，可以通過傳址調(diào)用來改變頭指針中保存的地址。在前面對于C語言函數(shù)的文章的介紹中曾寫過一個用傳址調(diào)用來實現(xiàn)交換函數(shù)。所以，通過函數(shù)來交換兩個變量中的值，需要用到一級指針。相對于，對于頭指針，想要通過函數(shù)來改變他的值，需采用二級指針。

所以，正確的尾插代碼應(yīng)為：

void SLTPushBack(SLTNode** phead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	if (*phead == NULL)
	{
		*phead = newnode;
	}
    else
    {
	   SLTNode* tail = *phead;
	   while (tail ->next != NULL)
	     {
		   tail = tail->next;
	     }
	   tail -> next = newnode;
    } 
}

運用下面的測試，來測試尾插的功能：

void Testlist2()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	SLTPrint(plist);
}

結(jié)果如下：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

3.3 鏈表功能實現(xiàn)——頭插：

對于頭插功能的實現(xiàn)，上面已經(jīng)給出來了大體思路。但是上面的頭插并不是通過函數(shù)實現(xiàn)的。根據(jù)剛才尾插的實現(xiàn)可以發(fā)現(xiàn)。每進行一次頭插，都需要對頭指針中存儲的地址進行更改。所以。在函數(shù)傳遞參數(shù)時，也需要傳遞二級指針。

代碼如下：

void SLTPushFront(SLTNode** phead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *phead;
	*phead = newnode;
}

用下列代碼對頭插功能進行測試：

void Testlist3()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPushFront(&plist, 6);
	SLTPrint(plist);
}

結(jié)果如下：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

3.4 鏈表功能實現(xiàn)——尾刪：

對于尾刪功能的實現(xiàn)，需要考慮下面的三種情況：

1. 鏈表整體為空：

2.鏈表內(nèi)只有一個結(jié)點

3.鏈表有多個結(jié)點

對第一種情況，只需要在進行尾刪功能前，檢查一下地址是否合法即可。

對于第三種情況，需要兩步。第一步是刪除處于尾部的結(jié)點。第二種情況是將前一個結(jié)點中保存的地址改為即：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

?第二種情況也需要分為兩步，首先刪除尾部結(jié)點。再把頭指針中存儲的地址改為。與第三步不同的時，第三步更改地址的對象是結(jié)構(gòu)體中的一個成員。第二步中更改的對象時頭指針。所以，在進行對于第二種情況的地址改動時，需要傳遞二級指針。

下面先給出針對第一、第二種情況下的代碼：

//尾刪
void SLTPopBack(SLTNode** phead)
{
	assert(*phead);
	if ((*phead)->next == NULL)//只有一個結(jié)點的情況
	{
		free(*phead);
		*phead = NULL;
	}

}

對于第三種情況，假設(shè)此時有三個結(jié)點：

對于尾刪功能，與尾插功能相同，第一步都是需要找到尾結(jié)點：

尋找尾結(jié)點時，采用與尾插尋找尾結(jié)點相同的方式，創(chuàng)建一個函數(shù)內(nèi)部的指針變量來保存頭指針保存的地址。當找到尾結(jié)點時：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

如果此時就刪除尾結(jié)點，還是會造成在講解尾插原理中的錯誤。即，沒能更改尾部結(jié)點前一個結(jié)點中存儲的地址。如下圖所示：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

此時最后一個由函數(shù)開辟的結(jié)點已經(jīng)被?。

為了解決上面的問題，可以在創(chuàng)建一個臨時變量也用于保存中存儲的地址。不過，這個變量的作用是用于更改尾結(jié)點前一個結(jié)點中存儲的地址。這里將這個指針命名為,再有了這個指針后，當找到尾結(jié)點時，這兩個指針的關(guān)系如下圖所示：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

先用代碼表示指針：

SLTNode* tail = *phead;
		SLTNode* tailprev = *phead;
		while (tail->next != NULL)
		{
			tail = tail->next;

		}

?為了達到圖中兩個指針一前一后的關(guān)系，可以讓循環(huán)中在執(zhí)行之前，讓存儲一次中的地址。代碼如下：

//尾刪
void SLTPopBack(SLTNode** phead)
{
	assert(*phead);
	if ((*phead)->next == NULL)//只有一個結(jié)點的情況
	{
		free(*phead);
		*phead = NULL;
	}
	else
	{
		SLTNode* tail = *phead;
		SLTNode* tailprev = NULL;
		while (tail->next != NULL)
		{
			tailprev = tail;
			tail = tail->next;

		}
		free(tail);
		tailprev->next = NULL;
	}
}

測試功能的代碼如下：
?

void Testlist3()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPushFront(&plist, 6);
	SLTPrint(plist);
	printf("\n尾刪");
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	printf("\n");
	SLTPrint(plist);
}

結(jié)果如下：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

3.5 鏈表功能實現(xiàn)——頭刪：

對于頭刪功能，依舊分為以下三種情況：

1. 鏈表整體為空：

2.鏈表內(nèi)只有一個結(jié)點

3.鏈表有多個結(jié)點

對于第一種情況，直接檢查頭指針合法性即可。對于第三種情況，即多個結(jié)點，需要分為兩步來完成頭刪：首先將頭指針存儲的地址改為第二個結(jié)點的地址。再把第一個結(jié)點。對于第二種情況，和第三種情況相同，雖然只有一個結(jié)點。但是可以將看作第二個結(jié)點的地址。代碼如下：

//頭刪
void SLTPopFront(SLTNode** phead)
{
	assert(*phead);
	SLTNode* newhead = (*phead)->next;
	free(*phead);
	*phead = newhead;
}

測試函數(shù)如下：

void Testlist4()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPushFront(&plist, 6);
	printf("\n");
	printf("頭刪");
	printf("\n");
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPopFront(&plist);
	SLTPopFront(&plist);
	printf("\n");
	SLTPrint(plist);

}

?結(jié)果如下：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

?4. 單鏈表的代碼實現(xiàn)——針對某一元素對應(yīng)的位置進行操作：

4.1 通過某一具體元素來找到特定位置：

例如給出下面所示的一個單鏈表：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

如果需要找到元素所對應(yīng)的位置，只需要將整體單鏈表進行一次遍歷，若某個結(jié)點中的元素= 想要尋找的元素。則返回這個元素對應(yīng)的結(jié)點的坐標，具體代碼如下：

//尋找某個元素所對應(yīng)的節(jié)點的地址：
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* tail = phead;
	while (phead != NULL)
	{
		if (tail->data == x)
		{
			return tail;
		}
		else
		{
			tail = tail->next;
		}
	}
	return NULL;
}

4.2 在某一特定數(shù)據(jù)對應(yīng)的結(jié)點前插入新結(jié)點：

前面知道了如何找到一個特定數(shù)據(jù)對應(yīng)的結(jié)點的位置后，如果需要在這個結(jié)點之前插入一個新的結(jié)點。

對于這種形式的插入，需要分為兩種情況：

1. 頭指針為空，此時無法插入，檢查指針合法性即可

2. 鏈表中只有一個結(jié)點，此時的插入就等于頭插

3. 鏈表中有多個結(jié)點

對于前兩種情況，具體的代碼如下：

void SLTInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)
{
	assert(*phead);
	if (*phead == NULL)
	{
		SLTPushFront(phead, x);
	}
}

對于第三種情況，需要考慮到，上面給出的查找函數(shù)返回的地址并不是插入新結(jié)點的地址，而是在這個地址對應(yīng)的結(jié)點的前面進行插入。所以，此時的插入可以分為兩步：

1.將新結(jié)點存儲查找函數(shù)找到的結(jié)點的地址，這里將用查找函數(shù)找到的地址用指針存儲。即：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

2. 將原來對應(yīng)的結(jié)點的前一個結(jié)點中存儲的地址，改為存儲新結(jié)點的地址，即：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

?用代碼表示上述過程，即：

void SLTInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)
{
	assert(*phead);
	if (*phead == NULL)
	{
		SLTPushFront(phead, x);
	}
	else
	{
		SLTNode* prev = *phead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;

	}
}

用下面的函數(shù)測試前插的功能：

void Testlist5()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPrint(plist);
	printf("\n");
	int x = 0;
	printf("請輸入想要查找的值");
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	printf("插入后：");
	SLTInsert(&plist, pos, x*10);
	SLTPrint(plist);
}

結(jié)果如下：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

4.3 在某一特定數(shù)據(jù)對應(yīng)的結(jié)點后插入新結(jié)點：

原理與前插相似，這里不再敘述，只給出圖形表示：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

對應(yīng)代碼如下：

void SLTInsertafter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

測試函數(shù)如下：

void Testlist5()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPrint(plist);
	printf("\n");
	int x = 0;
	int y = 0;
	printf("請輸入想要查找的值");
	scanf("%d %d", &x,&y);
	SLTNode* pos = SLTFind(plist, x);
	printf("插入后：");
	SLTInsert(&plist, pos, x*10);
	SLTPrint(plist);
	printf("\n");
	printf("前插\n");
	SLTInsertafter(pos, y * 10);
	SLTPrint(plist);
}

結(jié)果如下：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

4.4 刪除某一特定元素對應(yīng)位置的結(jié)點：

對于刪除結(jié)點，也要分三種情況：

1. 鏈表整體為空，檢查指針合法性即可

2.鏈表內(nèi)只有一個結(jié)點，相當于頭刪?

3.鏈表有多個結(jié)點。

對于第三種情況。與前插相同，也需要創(chuàng)建一個指針來改變前面的結(jié)點中存儲的地址，具體對應(yīng)的代碼如下：

void SLTErase(SLTNode** phead, SLTNode* pos)
{
	assert(pos);
	if (pos == *phead)
	{
		SLTPopFront(phead);
	}
	else
	{
		SLTNode* prev = *phead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

測試函數(shù)如下：

void Testlist6()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPrint(plist);
	printf("\n");
	printf("請輸入想要查找的值");
	int x = 0;
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	SLTErase(&plist,pos);
	printf("\n");
	SLTPrint(plist);
}

結(jié)果如下：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

?4.5刪除某一特定元素對應(yīng)位置后一個結(jié)點：

隨機給出一個鏈表：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

通過觀察不難發(fā)現(xiàn)：對于刪除某一特定元素對應(yīng)結(jié)點的后一個結(jié)點這個功能，對于兩種情況是沒有意義的：

1. 鏈表中沒有結(jié)點。

2. 對應(yīng)元素的結(jié)點恰好是最后一個結(jié)點。

所以，在進行刪除之前，應(yīng)該針對這兩種情況進行地址的檢查。

而對于刪除，也需要創(chuàng)建一個新的指針，用來保存這個地址。如果不保存，則刪除結(jié)點和鏈接結(jié)點之間會出現(xiàn)矛盾，例如：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯

如果不保存，若選擇直接鏈接數(shù)據(jù)元素為3的結(jié)點，此時沒有指針保存數(shù)據(jù)為2的結(jié)點的地址。如果先刪除，也無法得到數(shù)據(jù)元素為3的結(jié)點的地址。所以應(yīng)該創(chuàng)建一個新的指針，，用指針變量保存這個地址。在進行鏈接數(shù)據(jù)元素為這兩個結(jié)點時，可以來實現(xiàn)。刪除數(shù)據(jù)元素為的結(jié)點時，直接，代碼如下：

//刪除對應(yīng)位置后一個結(jié)點：
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);//檢查是否是最后一個結(jié)點
	SLTNode* posNext = pos->next;
	pos->next = posNext->next;
	free(posNext);
}

測試函數(shù)如下：

void Testlist6()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPrint(plist);
	printf("\n");
	printf("請輸入想要查找的值");
	int x = 0;
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	/*SLTErase(&plist,pos);
	printf("\n");
	SLTPrint(plist);*/
	SLTEraseAfter(pos);
	printf("\n");
	SLTPrint(plist);

}

結(jié)果如下：

一起學數(shù)據(jù)結(jié)構(gòu)（3）——萬字解析：鏈表的概念及單鏈表的實現(xiàn),初階數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表,c++,c語言,leetcode,藍橋杯文章來源地址http://www.zghlxwxcb.cn/news/detail-635173.html

?5.總體代碼：

5.1 頭文件 SList.h:

#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

//創(chuàng)建結(jié)點
SLTNode* BuySListNode(SLTDataType x);

//打印各節(jié)點的信息
void SLTPprint(SLTNode* phead);

//尾插
void SLTPushBack(SLTNode** phead, SLTDataType x);

//頭插
void SLTPushFront(SLTNode** phead, SLTDataType x);

//尾刪
void SLTPopBack(SLTNode** phead);

//頭刪
void SLTPopFront(SLTNode** phead);

//尋找某個元素所對應(yīng)的節(jié)點的地址：
SLTNode* SLTFind(SLTNode* phead,SLTDataType x);

//對應(yīng)位置前插入
void SLTInsert(SLTNode** phead, SLTNode* pos, SLTDataType x);

//對應(yīng)位置后插入：
void SLTInsertafter(SLTNode* pos, SLTDataType x);

//對應(yīng)位置前刪除
void SLTErase(SLTNode** phead, SLTNode* pos);

//刪除對應(yīng)位置后一個結(jié)點：
void SLTEraseAfter(SLTNode* pos);

5.1 函數(shù)功能實現(xiàn)——SLIst.c:

#include"SList.h"

//創(chuàng)建結(jié)點
SLTNode* BuySListNode(SLTDataType  x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

//打印結(jié)點信息
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
}

//尾插
void SLTPushBack(SLTNode** phead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	if (*phead == NULL)
	{
		*phead = newnode;
	}
	else
	{
		SLTNode* tail = *phead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

//頭插：
void SLTPushFront(SLTNode** phead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *phead;
	*phead = newnode;
}

//尾刪
void SLTPopBack(SLTNode** phead)
{
	assert(*phead);
	if ((*phead)->next == NULL)//只有一個結(jié)點的情況
	{
		free(*phead);
		*phead = NULL;
	}
	else
	{
		SLTNode* tail = *phead;
		SLTNode* tailprev = NULL;
		while (tail->next != NULL)
		{
			tailprev = tail;
			tail = tail->next;

		}
		free(tail);
		tailprev->next = NULL;
	}
}


//頭刪
void SLTPopFront(SLTNode** phead)
{
	assert(*phead);
	SLTNode* newhead = (*phead)->next;
	free(*phead);
	*phead = newhead;
}


//尋找某個元素所對應(yīng)的節(jié)點的地址：
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* tail = phead;
	while (phead != NULL)
	{
		if (tail->data == x)
		{
			return tail;
		}
		else
		{
			tail = tail->next;
		}
	}
	return NULL;
}


//特定位置前插入：
void SLTInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)
{
	assert(*phead);
	if (*phead == NULL)
	{
		SLTPushFront(phead, x);
	}
	else
	{
		SLTNode* prev = *phead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;

	}
}

//特定位置后插入新結(jié)點
void SLTInsertafter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}


void SLTErase(SLTNode** phead, SLTNode* pos)
{
	assert(pos);
	if (pos == *phead)
	{
		SLTPopFront(phead);
	}
	else
	{
		SLTNode* prev = *phead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}


//刪除對應(yīng)位置后一個結(jié)點：
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);//檢查是否是最后一個結(jié)點
	SLTNode* posNext = pos->next;
	pos->next = posNext->next;
	free(posNext);
}

5.3 函數(shù)測試文件Test.c:

#include"SList.h"


void Testlist1()
{
	printf("請輸入想要插入的元素的個數(shù)：");
	int n = 0;
	scanf("%d", &n);
	SLTNode* plist = NULL;
	printf("\n請輸入插入的元素：");
	for (size_t i = 0; i < n; i++)
	{
		int val = 0;
		scanf("%d", &val);
		SLTNode* newnode = BuySListNode(val);
		if (plist == NULL)
		{
			plist = newnode;
		}
		else
		{
			newnode->next = plist;
			plist = newnode;
		}
	}
	SLTPrint(plist);
	printf("\n");
	SLTPushBack(&plist, 10000);
	SLTPrint(plist);
	printf("\n");
}

void Testlist2()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	printf("尾插");
	printf("\n");
	SLTPrint(plist);
	printf("\n");
}

void Testlist3()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPushFront(&plist, 6);
	SLTPrint(plist);
	printf("\n尾刪");
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	printf("\n");
	SLTPrint(plist);

}
void Testlist4()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPushFront(&plist, 6);
	printf("\n");
	printf("頭刪");
	printf("\n");
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPopFront(&plist);
	SLTPopFront(&plist);
	printf("\n");
	SLTPrint(plist);

}

void Testlist5()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPrint(plist);
	printf("\n");
	int x = 0;
	int y = 0;
	printf("請輸入想要查找的值");
	scanf("%d %d", &x,&y);
	SLTNode* pos = SLTFind(plist, x);
	printf("插入后：");
	SLTInsert(&plist, pos, x*10);
	SLTPrint(plist);
	printf("\n");
	printf("前插\n");
	SLTInsertafter(pos, y * 10);
	SLTPrint(plist);
	printf("\n");
}

void Testlist6()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPrint(plist);
	printf("\n");
	printf("請輸入想要查找的值");
	int x = 0;
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	/*SLTErase(&plist,pos);
	printf("\n");
	SLTPrint(plist);*/
	SLTEraseAfter(pos);
	printf("\n");
	SLTPrint(plist);

}
int main()
{
	/*Testlist1();*/
	/*Testlist2();*/
	/*Testlist3();
	Testlist4();*/
	/*Testlist5();*/
	Testlist6();
	return 0;
}

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

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

分享到：

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

【數(shù)據(jù)結(jié)構(gòu)】鏈表的回文結(jié)構(gòu)
單鏈表的操作算法是筆試面試中較為常見的題目。本文將著重介紹平時面試中常見的關(guān)于鏈表的應(yīng)用題目，馬上要進行秋招了。希望對你們有幫助 _ ?? 對于一個鏈表，請設(shè)計一個時間復雜度為O(n),額外空間復雜度為O(1)的算法，判斷其是否為回文結(jié)構(gòu)。給定一個鏈表的頭指針
2024年02月12日
瀏覽(27)
【數(shù)據(jù)結(jié)構(gòu)】鏈表的分類和雙向鏈表
本篇是基于上篇單鏈表所作，推薦與上篇配合閱讀，效果更加 http://t.csdnimg.cn/UhXEj 鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來就有8種（2 x 2 x 2）鏈表結(jié)構(gòu)：我們一般叫這個頭為哨兵位我們上回講的單鏈表就是不帶頭單項不循環(huán)鏈表。今天我們要講帶頭雙向循環(huán)的鏈表。不過
2024年01月25日
瀏覽(26)
數(shù)據(jù)結(jié)構(gòu)-二叉鏈表的結(jié)構(gòu)與實現(xiàn)
目錄一、引言二、什么是二叉鏈表三、二叉鏈表的結(jié)構(gòu) 四、二叉鏈表的實現(xiàn) 1. 創(chuàng)建二叉鏈表 2. 遍歷二叉鏈表 3. 插入節(jié)點 4. 刪除節(jié)點五、應(yīng)用場景六、總結(jié) 七、代碼示例數(shù)據(jù)結(jié)構(gòu)是計算機科學中的重要概念，它是計算機程序設(shè)計的基礎(chǔ)。二叉鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu)
2024年02月08日
瀏覽(23)
數(shù)據(jù)結(jié)構(gòu)：線性表之-循環(huán)雙向鏈表(萬字詳解)
目錄基本概念 1，什么是雙向鏈表 2，與單向鏈表的區(qū)別雙向鏈表詳解功能展示： 1. 定義鏈表 2，創(chuàng)建雙向鏈表 3，初始化鏈表 4,尾插 5，頭插 6，尾刪判斷鏈表是否被刪空尾刪代碼 7，頭刪 8,pos位置之前插入優(yōu)化后的頭插優(yōu)化后的尾插 9,刪除pos位置的節(jié)點優(yōu)化后的尾刪優(yōu)
2024年02月09日
瀏覽(23)
【數(shù)據(jù)結(jié)構(gòu)篇】線性表1 --- 順序表、鏈表（萬字詳解?。。?/a>
目錄 ?順序表（ArrayList）什么是順序表？? 代碼實現(xiàn)?（MyArrayList） --- 打印順序表? --- 新增元素? 1.新增元素，默認在數(shù)組最后新增 2.在指定位置新增元素? --- 判斷是否包含某個元素 --- 查找某個元素具體位置（下標） --- 獲取 pos 位置的元素 --- 給pos位置的值設(shè)為 value? -
2024年02月10日
瀏覽(45)
數(shù)據(jù)結(jié)構(gòu)----鏈表介紹、模擬實現(xiàn)鏈表、鏈表的使用
ArrayList底層使用連續(xù)的空間，任意位置插入或刪除元素時，需要將該位置后序元素整體往前或者往后搬移，故時間復雜度為O(N) 增容需要申請新空間，拷貝數(shù)據(jù)，釋放舊空間。會有不小的消耗。增容一般是呈2倍的增長，勢必會有一定的空間浪費。例如當前容量為100，滿了以后
2024年02月21日
瀏覽(18)
【數(shù)據(jù)結(jié)構(gòu)】——線性表（順序表加鏈表），萬字解讀（加鏈表oj詳解)
前言由于之前存在過對兩者的區(qū)別考慮，所以把他們放在一起來說，更加容易區(qū)別和理解對于有關(guān)線性表的概念這里就不展示了，這里主要是介紹線性表里面的這兩個結(jié)構(gòu)的知識點一.順序表 1.順序表介紹順序表的存儲結(jié)構(gòu)和邏輯結(jié)構(gòu)都是相鄰的，?這里如果我們把a1的地址
2024年03月22日
瀏覽(38)
【（數(shù)據(jù)結(jié)構(gòu)）— 雙向鏈表的實現(xiàn)】
注意：這里的 “帶頭” 跟前面我們說的 “頭節(jié)點” 是兩個概念，實際前面的在單鏈表階段稱呼不嚴謹，但是為了同學們更好的理解就直接稱為單鏈表的頭節(jié)點。帶頭鏈表里的頭節(jié)點，實際為 “哨兵位” ，哨兵位節(jié)點不存儲任何有效元素，只是站在這里“放哨的” “哨
2024年02月06日
瀏覽(27)
【數(shù)據(jù)結(jié)構(gòu)】十字鏈表的畫法
有向邊又稱為弧假設(shè)頂點 v 指向 w，那么 w 稱為弧頭，v 稱為弧尾頂點節(jié)點采用順序存儲頂點節(jié)點 data：存放頂點的信息 firstin：指向以該節(jié)點為終點（弧頭）的弧節(jié)點 firstout：指向以該節(jié)點為起點（弧尾）的弧節(jié)點弧節(jié)點 tailvex：起點（弧尾）在數(shù)組中的索引 headvex：終點（
2024年02月11日
瀏覽(22)
【數(shù)據(jù)結(jié)構(gòu)】雙向鏈表的實現(xiàn)
我要扼住命運的咽喉，他卻不能使我完全屈服。? ? ? ? ? ? ? ? ? ? ? --貝多芬目錄一.帶頭循環(huán)的雙向鏈表的特點二.不帶頭不循環(huán)單向鏈表和帶頭循環(huán)的雙向鏈表的對比三.初始化鏈表，創(chuàng)建哨兵結(jié)點四.雙向鏈表的各種功能的實現(xiàn) 1.雙向鏈表的尾插 2.雙向鏈表的打印?
2023年04月10日
瀏覽(17)

<th id="r2gvv"></th>

<dd id="r2gvv"><dl id="r2gvv"></dl></dd>