接著講遞歸結(jié)構(gòu)
接著講遞歸結(jié)構(gòu)
遞歸(遞歸定義的)數(shù)據(jù)結(jié)構(gòu)是在部分中復(fù)制自身的結(jié)構(gòu)。
我們剛剛見過在上面的公司結(jié)構(gòu)的例子。
A公司部門是:
要么是一群人。
或者一個(gè)帶有部門的對(duì)象。
web開發(fā)人員還有更著名的例子:HTML和XML文檔。
在HTML文檔中，一個(gè)HTML標(biāo)簽可能包含以下列表:
文本塊。
html注釋。
其他html標(biāo)簽(可能包含文本片段/注釋或其他標(biāo)簽等)。
這又是一個(gè)遞歸定義。
為了更好地理解，我們將介紹另一種名為“鏈表”的遞歸結(jié)構(gòu)，在某些情況下，它可能是數(shù)組的更好選擇。
鏈表
想象一下，我們想存儲(chǔ)一個(gè)有序的對(duì)象列表。
自然的選擇是一個(gè)數(shù)組:
let?arr?=?[obj1,?obj2,?obj3];
但是數(shù)組有一個(gè)問題。“刪除元素”和“插入元素”操作代價(jià)很高。例如，arr.unshift(obj)操作必須對(duì)所有元素重新編號(hào)，以便為新的obj騰出空間，如果數(shù)組很大，則需要花費(fèi)時(shí)間。與arr.shift()相同。
只有那些不需要大規(guī)模重編號(hào)的結(jié)構(gòu)修改是在數(shù)組末尾操作的:arr.push/pop。數(shù)組對(duì)于大的隊(duì)列來說很慢，當(dāng)我們需要從一開始就處理時(shí)。
另外，如果我們真的需要快速插入/刪除，我們可以選擇另一種稱為鏈表的數(shù)據(jù)結(jié)構(gòu)。
鏈表元素被遞歸定義為一個(gè)對(duì)象:
值。
引用下一個(gè)鏈表元素的next屬性，如果結(jié)束，則為null。
let?list?=?{
??value:?1,
??next:?{
????value:?2,
????next:?{
??????value:?3,
??????next:?{
????????value:?4,
????????next:?null
??????}
????}
??}
};
列表的圖示:
創(chuàng)建的另一個(gè)代碼:
let?list?=?{?value:?1?};
list.next?=?{?value:?2?};
list.next.next?=?{?value:?3?};
list.next.next.next?=?{?value:?4?};
list.next.next.next.next?=?null;
在這里我們可以更清楚地看到有多個(gè)對(duì)象，每個(gè)對(duì)象都有值，下一個(gè)對(duì)象指向鄰居。list變量是鏈表中的第一個(gè)對(duì)象，因此跟隨它的next指針可以到達(dá)任何元素。
這個(gè)列表可以很容易地被分割成多個(gè)部分，然后再連接回來:
let?secondList?=?list.next.next;
list.next.next?=?null;
加入:
list.next.next?=?secondList;
當(dāng)然，我們可以在任何地方插入或刪除物品。
例如，要添加一個(gè)新值，我們需要更新列表的頭:
let?list?=?{?value:?1?};
list.next?=?{?value:?2?};
list.next.next?=?{?value:?3?};
list.next.next.next?=?{?value:?4?};
//?prepend?the?new?value?to?the?list
list?=?{?value:?"new?item",?next:?list?};
要從中間刪除一個(gè)值，更改前一個(gè)值的下一個(gè):
list.next?=?list.next.next;
我們列了清單。下一個(gè)跳過1到值2。值1現(xiàn)在被排除在鏈之外。如果它沒有存儲(chǔ)在其他地方，它將自動(dòng)從內(nèi)存中刪除。
與數(shù)組不同的是，沒有質(zhì)量重編號(hào)，我們可以很容易地重新排列元素。
當(dāng)然，列表并不總是比數(shù)組好。否則，每個(gè)人都會(huì)只使用列表。
主要的缺點(diǎn)是我們不能簡(jiǎn)單地按編號(hào)訪問元素。在數(shù)組中，arr[n]是一個(gè)直接引用。但是在列表中，我們需要從第一項(xiàng)開始，然后再走N次，才能得到第N個(gè)元素。
但我們并不總是需要這樣的操作。例如，當(dāng)我們需要隊(duì)列甚至deque時(shí)——這種有序結(jié)構(gòu)必須允許非?？斓貜膬啥颂砑?刪除元素，但不需要訪問其中間部分。
列表可以增強(qiáng):
我們可以添加屬性prev來引用之前的元素，方便向后移動(dòng)。
我們還可以添加一個(gè)名為tail的變量來引用列表的最后一個(gè)元素(并在從末尾添加/刪除元素時(shí)更新它)。
數(shù)據(jù)結(jié)構(gòu)可以根據(jù)我們的需要而變化。