1：間接尋址的基本概念{

間接尋址就是二級(jí)指針的利用，指向指針的指針，一維數(shù)組，二維數(shù)組。間接尋址在此特指其一維數(shù)組的含義；

間接尋址是一維和二維數(shù)組的組合。既保留了數(shù)組的許多優(yōu)點(diǎn)，也獲得了鏈表的眾多特色。首先，可以根據(jù)索引在O（1）

的時(shí)間內(nèi)詢(xún)問(wèn)每個(gè)元素；其次可以采用二分在對(duì)數(shù)時(shí)間內(nèi)對(duì)一個(gè)有序表進(jìn)行搜索；最后，在諸如插入和刪除的操作期間

不必對(duì)元素進(jìn)行實(shí)際的行動(dòng)}

2：間接尋址使用指針數(shù)組來(lái)跟蹤每一個(gè)元素，對(duì)元素本身如何分配不設(shè)限制（可離散可連續(xù)）。將實(shí)體節(jié)點(diǎn)轉(zhuǎn)化為指針節(jié)點(diǎn)。

3 使用：內(nèi)存池

自構(gòu)建等塊內(nèi)存池，每一個(gè)指針?lè)謩e指向每一塊內(nèi)存的首地址。內(nèi)存池可以避免內(nèi)存碎片和系統(tǒng)調(diào)用。

　　：散列鏈表

如果指針指向的元素包含next指針，則間接尋址就變成了散列鏈表。

4：模擬指針簡(jiǎn)單的描述就是利用數(shù)組的下標(biāo)當(dāng)指針。

實(shí)現(xiàn)1：首先構(gòu)造一個(gè)節(jié)點(diǎn)數(shù)組，節(jié)點(diǎn)包含兩個(gè)域：data和link。link域指向數(shù)組中的其他節(jié)點(diǎn)。和間接尋址有相似處。

實(shí)現(xiàn)2：數(shù)組值包含link域，可以用來(lái)模擬樹(shù)。（用來(lái)解決并查集的問(wèn)題）；

等價(jià)類(lèi)：

定義：假定有一個(gè)具有n個(gè)元素的集合u，另有一個(gè)具有r個(gè)關(guān)系的集合r。如果（a，b）%r，則元素a和b是等價(jià)的。等價(jià)類(lèi)

是指等價(jià)元素的最大集合。一言以避之，將集合u根據(jù)關(guān)系進(jìn)行劃分，類(lèi)內(nèi)的元素等價(jià)，可以看做是一種聚類(lèi)。

。離線(xiàn)等價(jià)類(lèi)

　　一直n和R,確定所有的等價(jià)類(lèi)。

。在線(xiàn)等價(jià)類(lèi)

　　初始時(shí)有n個(gè)元素，每個(gè)元素都屬于一個(gè)獨(dú)立的等價(jià)類(lèi)。然后不停地執(zhí)行Find和Union操作向R中增加新關(guān)系。通常被稱(chēng)為并查集問(wèn)題。

5：并查集的操作：

Find：查詢(xún)?cè)豠和b是否屬于同一類(lèi)；

Union：合并元素a和b所在的lei；

并查集的實(shí)現(xiàn)

　　采用方式二的模擬指針。數(shù)組的下標(biāo)即表示指針，指針的指向使并查集構(gòu)成了一顆虛擬的森林。但是并查集不關(guān)注每棵樹(shù)的形狀以及

相互指向關(guān)系，只關(guān)注最終的根節(jié)點(diǎn)以及該樹(shù)的元素個(gè)數(shù)或者高度。

并查集的優(yōu)化

　　可以根據(jù)重量規(guī)則或者高度規(guī)則對(duì)并查集進(jìn)行優(yōu)化?

6：并查集的應(yīng)用

　　最小生成樹(shù)-Kruskal算法

算法的思想：

　　從n個(gè)點(diǎn)的圖中選擇n-1個(gè)點(diǎn)，每次從剩下的邊中選擇一條不會(huì)產(chǎn)生環(huán)路得具有最小消耗的邊加入已選擇的邊集合中

　　從當(dāng)前選擇的邊將所有的點(diǎn)分成不同的類(lèi)（連通分量），當(dāng)判斷下一條要增加的邊的兩個(gè)點(diǎn)是否在同一個(gè)類(lèi)中：若

在同一類(lèi)中說(shuō)明構(gòu)成環(huán)，否則可以增加到生成樹(shù)中。

轉(zhuǎn)載于:https://www.cnblogs.com/ylllove/p/6044830.html

總結(jié)

以上是生活随笔為你收集整理的《数据结构》之数组结构和链表的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。