算法競賽基礎(chǔ)：雙向鏈表

本文將會介紹在算法競賽中雙向鏈表的幾種使用方式，適合有一定基礎(chǔ)的人閱讀。

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

一般來說，普通的鏈表結(jié)構(gòu)是這樣的：

struct node {
	int num;
	node *next; 
}

next指針指向下一個(gè)鏈表，這樣的結(jié)構(gòu)只能夠支持單向查詢。

雙向鏈表，顧名思義，就是可以支持雙向的訪問和查詢。

也就是這樣的：

struct node {
	int num;
	node *l, *r;
}

這種鏈表為訪問前后的元素提供的很大的便利性。

C++的STL模板中也有類似的結(jié)構(gòu)：
List

list<int> lis;

List是連續(xù)的容器，而vector是非連續(xù)的容器，即list將元素存儲在連續(xù)的存儲器中，而vector存儲在不連續(xù)的存儲器中。

向量（vector）中間的插入和刪除是非常昂貴的，因?yàn)樗枰罅康臅r(shí)間來移動所有的元素。鏈表克服了這個(gè)問題，它是使用list容器實(shí)現(xiàn)的。

List支持雙向，并為插入和刪除操作提供了一種有效的方法。

在列表中遍歷速度很慢，因?yàn)榱斜碓厥前错樞蛟L問的，而vector支持隨機(jī)訪問。

列表模板

示例

#include<iostream>
#include<list>
using namespace std;
int main()
{
   list<int> l;
}

它創(chuàng)建一個(gè)空的整數(shù)類型值列表。

列表也可以使用參數(shù)初始化。

示例

#include<iostream>
#include<list>
using namespace std;
int main()
{
   list<int> l{1,2,3,4};
}

列表可以通過兩種方式初始化。

示例

list<int>  new_list{1,2,3,4};
or
list<int> new_list = {1,2,3,4};

list支持的操作有以下這些：

但是這種結(jié)構(gòu)往往在大量數(shù)據(jù)的情況下會超時(shí)。我們需要一種更加有效的方式，通常，我們選擇空間換時(shí)間，因此靜態(tài)鏈表通常是更好的選擇，接下來介紹一種靜態(tài)雙向循環(huán)鏈表在競賽中實(shí)現(xiàn)的方式。

競賽方式實(shí)現(xiàn)

思路是這樣的：

要實(shí)現(xiàn)一個(gè)靜態(tài)雙向循環(huán)鏈表，需要模擬一個(gè)左右指針，在這里，我們選擇花費(fèi)大量空間去用數(shù)組的下標(biāo)代替指針和對應(yīng)的值：

#include <bits/stdc++.h>
using namespace std;

const int MAX_N 1e5 + 10;

struct node {
	int l, r;
	int key;
} arr[MAX_N] = {0};

其中，l和r分別表示上一個(gè)和下一個(gè)元素的數(shù)組下標(biāo)。

插入操作

插入操作的思路很簡單：
先將新元素的l和r指向左右兩個(gè)元素。
再分別讓左右兩個(gè)元素的r和l分別指向新元素本身；

//ll:左元素，rr:右元素, new:新元素
void add(int ll， int rr, int new) {
	arr[new].l = ll;
	arr[new].r == rr;
	arr[ll].r == new;
	arr[rr].l == new;
}

這不是一種唯一的實(shí)現(xiàn)方式，其中的參數(shù)和需求都可以根據(jù)具體情況改變。

刪除操作

刪除操作提供兩種思路：

• 第一種與插入操作類似，實(shí)現(xiàn)元素的刪除
• 第二種更加快速，通過在節(jié)點(diǎn)種的key值，去判斷是否輸出（如果要求輸出鏈表的話）

第一種方式：

void del(int target) {
	int l, r;
	l = arr[target].l;
	r = arr[target].r;

	arr[l].r = r;
	arr[r].l = l;
	

第二種方式：

void del(int target) {
	arr[target].key = 0; //在對鏈表元素進(jìn)行操作時(shí)，檢測其key值的真值，如果為0，直接不對其進(jìn)行操作
}

第二種方式雖然沒有改變l和r的值，但是也能夠?qū)崿F(xiàn)鏈表訪問機(jī)制的修改而且還支持?jǐn)?shù)據(jù)恢復(fù)，相當(dāng)好用。

查找操作

這種方式是基于上面刪除操作時(shí)的第二種方式實(shí)現(xiàn)的：

bool find(int target) {
	return arr[target].key == 1;
}

因?yàn)檫@種特殊的鏈表結(jié)構(gòu)支持隨機(jī)訪問（正常的鏈表結(jié)構(gòu)是不支持的），所以查找操作變成檢測對應(yīng)元素的鍵值是否有效，如果有效，返回一個(gè)真值。

遍歷操作

以輸出全部數(shù)值為例：

這里值得一提的是，如果按照這種上文所述的方式去建立雙向鏈表的話，你會發(fā)現(xiàn)沒有頭結(jié)點(diǎn)。

具體原因是由于開辟第一個(gè)結(jié)點(diǎn)時(shí)，也就是數(shù)組下標(biāo)為1的時(shí)候，結(jié)構(gòu)體中的l和r指向的是1本身，那這個(gè)時(shí)候如果再多插入幾個(gè)結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的r會指向1，1的l會指向最后一個(gè)結(jié)點(diǎn)，這樣一來，當(dāng)你在1之前插入結(jié)點(diǎn)時(shí)，按理來說頭節(jié)點(diǎn)會變成新插入的結(jié)點(diǎn)，但由于缺少一個(gè)指向頭節(jié)點(diǎn)的指針而丟失鏈表的頭，這顯然是我們不想看到的。

解決方法也很簡單，我們在數(shù)組下標(biāo)為0的位置創(chuàng)建一個(gè)結(jié)點(diǎn)作為虛擬頭結(jié)點(diǎn)，當(dāng)在真正的頭結(jié)點(diǎn)之前插入新的結(jié)點(diǎn)時(shí)，這時(shí)候新結(jié)點(diǎn)會在0和頭節(jié)點(diǎn)之間，當(dāng)我們需要訪問頭節(jié)點(diǎn)的時(shí)候，通過0去訪問就可以了。

下面是建立的虛擬頭節(jié)點(diǎn)0之后的遍歷輸出操作：文章來源地址http://www.zghlxwxcb.cn/news/detail-821338.html

void bs() {
	// from left to right
	for (int i = arr[0].r; i; i = arr[i].r) {
		cout << arr[i] << " ";
	}

到了這里，關(guān)于算法競賽基礎(chǔ)：C++雙向鏈表的結(jié)構(gòu)和實(shí)現(xiàn)（普通鏈表、List、靜態(tài)鏈表）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！