數(shù)據(jù)結(jié)構(gòu)知識點(diǎn)整理

1、學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考數(shù)據(jù) 是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識別和處理的符號（數(shù) 值、字符等）的集合。 數(shù)據(jù)元素（數(shù)據(jù)成員） 是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點(diǎn)、 頂點(diǎn)、記錄等數(shù)據(jù)對象 具有相同性質(zhì)的數(shù)據(jù)元素（數(shù)據(jù)成員）的集合數(shù)據(jù)結(jié)構(gòu) 由某一數(shù)據(jù)對象及該對象中所有數(shù)據(jù)成員之間的關(guān)系組成。記為Data_Structure = D, R 其中， D 是某一數(shù)據(jù)對象， R 是該對象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。數(shù)據(jù)類型 是指一種類型，以及定義在這個(gè)值集合上的一組操作的總稱。 判斷一個(gè)算法的優(yōu)劣主要標(biāo)準(zhǔn) ：正確性、可使

2、用性、可讀性、效率、健壯性、簡單性。算法效率的衡量方法 ：后期測試，事前估計(jì)算法分析 是算法的漸進(jìn)分析簡稱數(shù)據(jù)結(jié)構(gòu) 包括“邏輯結(jié)構(gòu) ”和“物理結(jié)構(gòu) ”兩個(gè)方面 （層次 ）: 邏輯結(jié)構(gòu)是對數(shù)據(jù)成員之間的邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)成員的集合和定義在此集合上的若干關(guān)系來表示物 理結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示和實(shí)現(xiàn)，故又稱 “存儲(chǔ)結(jié)構(gòu) ”線性表的定義：n （0）個(gè)表項(xiàng)的有限序列 L = （a1, a2,an） ai是表項(xiàng)，n是表長度。第一個(gè)表項(xiàng)是表頭，最后一個(gè)是表尾。線性表的特點(diǎn) ：表中元素的數(shù)據(jù)類型相同；線性表中，結(jié)點(diǎn)和結(jié)點(diǎn)間的關(guān)系是一對一的，有序表和無序表線性表的存 儲(chǔ)方式。一，順序存儲(chǔ)方

3、式，二，鏈表存儲(chǔ)方式。順序表的存儲(chǔ)表示有 2種方式 ：靜態(tài)方式和動(dòng)態(tài)方式。順序表的定義是 ：把線性表中的所有表項(xiàng)按照其邏輯順序依次存儲(chǔ)到從計(jì)算機(jī)存儲(chǔ)中指定存儲(chǔ)位置開始的一塊連續(xù)的 存儲(chǔ)空間中。順序表的特點(diǎn) ：用地址連續(xù)的一塊存儲(chǔ)空間順序存放各表項(xiàng)，各表項(xiàng)的邏輯順序與物理順序一致，對各個(gè)表項(xiàng)可以順 序訪問，也可以隨機(jī)訪問 。單鏈表 是一種最簡單的鏈表表示，也叫 線性鏈表 ，用她來表示線性表時(shí)，用指針表示結(jié)點(diǎn)間的邏輯關(guān)系。特點(diǎn)：是長 度可以很方便地進(jìn)行擴(kuò)充。連續(xù)存儲(chǔ)方式（順序表）特點(diǎn) ：存儲(chǔ)利用率高，存取速度快缺點(diǎn)：插入、刪除等操作時(shí)需要移動(dòng)大量數(shù)據(jù)： 鏈?zhǔn)酱鎯?chǔ)方式（鏈表） 特點(diǎn) ：適應(yīng)表的動(dòng)態(tài)增

4、長和刪除。缺點(diǎn)：需要額外的指針存儲(chǔ)空間單鏈表的類定義：多個(gè)類表達(dá)一個(gè)概念（單鏈表）。分為：鏈表結(jié)點(diǎn)（ListNode）類，鏈表（List）類。 循環(huán)鏈表的概念 ：是另一種形式的表示線性表的鏈表，它的結(jié)點(diǎn)結(jié)構(gòu)與單鏈表相同，與單鏈表不同的是鏈表中表尾結(jié) 點(diǎn)的 LINK 域中不是 NULL ，而是存放了一個(gè)指向鏈表開始結(jié)點(diǎn)的指針，這樣，只要知道表中任何一個(gè)結(jié)點(diǎn)的地址， 就能遍歷表中其他任何一結(jié)點(diǎn)。雙向鏈表的概念 ：在雙向鏈表的沒餓結(jié)點(diǎn)中應(yīng)有兩個(gè)鏈接指針作為它的數(shù)據(jù)成員：1LINK 指示它的前驅(qū)結(jié)點(diǎn)， RLINK指示它的后繼結(jié)點(diǎn)， 因此，雙向鏈表的每個(gè)結(jié)點(diǎn)至少有 3個(gè)域：1LINK（前驅(qū)指針）DADA

5、 （數(shù)據(jù)）RLINK （后繼指針）。 棧：定義為只允許在表的末端進(jìn)行插入和刪除的線性表。特點(diǎn)是：后進(jìn)先出。遞歸的定義 ：若一個(gè)對象部分地包含它自己， 或用它自己給自己定義 , 則稱這個(gè)對象是遞歸的； 若一個(gè)過程直接地或 間接地調(diào)用自己 , 則稱這個(gè)過程是遞歸的過程。 以下三種情況常常用到遞歸方法一。 定義是遞歸的二。 數(shù)據(jù)結(jié)構(gòu)是遞 歸的三問題的解法是遞歸的。隊(duì)列 ：隊(duì)列是只允許在一端刪除，在另一端插入的順序表允許刪除的一端叫做隊(duì)頭，允許插入的一端叫做隊(duì)尾。特性： 先進(jìn)先出。優(yōu)先級隊(duì)列 ：是不同于先進(jìn)先出隊(duì)列的另一種隊(duì)列。每次從隊(duì)列中取出的是具有最高優(yōu)先權(quán)的元素。多維數(shù)組是一維 數(shù)組的推廣。多維

6、數(shù)組 是一維數(shù)組的推廣。多維數(shù)組的特點(diǎn)是每一個(gè)數(shù)據(jù)元素可以有多個(gè)直接前驅(qū)和多個(gè)直接后繼。數(shù)組元素的下 標(biāo)一般具有固定的下界和上界，因此它比其他復(fù)雜的非線性結(jié)構(gòu)簡單。字符串是n （ 0 ）個(gè)字符的有限序列，記作S : “c1c2c3c其中，S是串名字c1c2c3cn是串值ci是串中字符n是串的長度， n = 0 稱為空串。廣義表是n （ 0 ）個(gè)表元素組成的有限序列，記作 LS （a1, a2, a3,an）, LS是表名，ai是表元素，可以是表（稱為 子表），可以是數(shù)據(jù)元素（稱為原子） 。 n 為表的長度。 n = 0 的廣義表為空表。 n 0 時(shí)，表的第一個(gè)表元素稱為廣義表 的表頭（head

7、）,除此之外，其它表元素組成的表稱為廣義表的表尾（ tail學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考有根樹：一棵有根樹 T,簡稱為樹，它是 n （n0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng) n = 0時(shí)，T稱為空樹；否則，T是非空樹， 記作 T= 空集 n=0r,T1,T2 .Tn,n0r是一個(gè)特定的稱為根（root）的結(jié)點(diǎn)，它只有直接后繼，但沒有直接前驅(qū)；根以外的其他結(jié)點(diǎn)劃分為m （m 0）個(gè)互不相交的有限集合T1, T2,Tm，每個(gè)集合又是一棵樹，并且稱之為根的子樹。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前 驅(qū)，但可以有 0個(gè)或多個(gè)直接后繼二叉樹的定義 :一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加

8、上兩棵分別稱為左子樹和 右子樹的、互不相交的二叉樹組成。完全二叉樹：一若設(shè)二叉樹的深度為 k,則共有k層。除第k層外，其它各層 （1k-1）的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 k 層從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹二叉樹的遍歷 就是按某種次序訪問樹中的結(jié)點(diǎn),要求每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。設(shè)訪問根結(jié)點(diǎn)記作V 遍歷根的左子樹記作 L遍歷根的右子樹記作 R。則可能的遍歷次序有：前序VLR鏡像VRL ;中序LVR鏡像RVL ;后序LRV 鏡像 RLV前序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則訪問根結(jié)點(diǎn)（V）;前序遍歷左子樹 （L）;前序遍歷右子樹（R）。遍歷結(jié)果-+ a * b -

9、c d / e f樹的后根次序遍歷 ：當(dāng)樹非空時(shí)依次后根遍歷根的各棵子樹訪問根結(jié)點(diǎn)：樹后根遍歷EFBCGDA ；對應(yīng)二叉樹中序遍歷EFBCGDA ；樹的后根遍歷結(jié)果與其對應(yīng)二叉樹。表示的中序遍歷結(jié)果相同：樹的后根遍歷可以借助對應(yīng)二叉樹的中序遍歷算法實(shí)現(xiàn)最小堆和最大堆：如果有一個(gè)關(guān)鍵碼集合 K=K0,K1 , K2 , K3 ,.,Kn-1，把它的所有元素按完全二叉樹的順序存儲(chǔ)方式存放在一個(gè)一維數(shù)組中。并滿足Ki K2i+1且Ki K2i+1且KiK2i+2 ）i=0,1,.（n-2） /2，則稱這個(gè)集合為最小堆或最大堆。堆是最高效的一種數(shù)據(jù)結(jié)構(gòu) ，每次出隊(duì)列的是優(yōu)先權(quán)最高的元素。用堆實(shí)現(xiàn)其存儲(chǔ)

10、表示，能夠高效運(yùn)作。堆的建立 ：有 2種方式建立最小的堆，一種方式是通過第一個(gè)構(gòu)造函數(shù)建立一個(gè)空堆，其大小通過動(dòng)態(tài)存儲(chǔ)分配得到， 另一中建立最小堆的方式是通過第二個(gè)構(gòu)造函數(shù)復(fù)制一個(gè)記錄數(shù)組并對其加以調(diào)整形成一個(gè)堆。路徑 ：從樹中一個(gè)結(jié)點(diǎn)到達(dá)另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成該兩結(jié)點(diǎn)之間的路徑。路徑長度： 是指路徑上的分支條數(shù)，樹的路徑長度是從樹的根結(jié)點(diǎn)到每一個(gè)結(jié)點(diǎn)的路徑長度之和。由樹的定義，從根 結(jié)點(diǎn)到達(dá)書中每一結(jié)點(diǎn)有且僅有一條路徑。Huffman 樹：帶權(quán)路徑長度最小的二叉樹應(yīng)是權(quán)值大的外結(jié)點(diǎn)離根結(jié)點(diǎn)最近的擴(kuò)充二叉樹。帶路徑長度最小的擴(kuò)充二叉樹不一定是完全二叉樹。集合 是成員 （元素 ）的一個(gè)群集。集

11、合中的成員可以是原子（單元素 ），也可以是集合。字典是一些元素的集合，每個(gè)元素有一個(gè)稱作關(guān)鍵碼（key）的域，不同元素的關(guān)鍵碼互不相同。散列方法： 理想的搜索方法是可以不經(jīng)過比較，一次直接從字典中得到要搜索的元素。如果在元素存儲(chǔ)位置與其關(guān)鍵碼之間建立一個(gè)確定的對應(yīng)函數(shù)關(guān)系Hash（）, 使得每個(gè)關(guān)鍵碼與結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對應(yīng)：Address =Hash（key）。在插入時(shí)依此函數(shù)計(jì)算存儲(chǔ)位置并按此位置存放。在搜索時(shí)對元素的關(guān)鍵碼進(jìn)行同樣的計(jì)算，把求得的函 數(shù)值當(dāng)做元素存儲(chǔ)位置，在結(jié)構(gòu)中按此位置搜索。這就是 散列方法 。在散列方法中所用轉(zhuǎn)換函數(shù)叫做 散列函數(shù) 。按此 方法構(gòu)造出來的表叫做

12、 散列表 。使用散列方法進(jìn)行搜索不必進(jìn)行多次關(guān)鍵碼的比較 , 搜索速度比較快 , 可以直接到達(dá)或 逼近具有此關(guān)鍵碼的表項(xiàng)的實(shí)際存放地址。散列函數(shù) 是一個(gè)壓縮映象函數(shù)。關(guān)鍵碼集合比散列表地址集合大得多。因此有可能經(jīng)過散列函數(shù)的計(jì)算,把不同的關(guān) 鍵碼映射到同一個(gè)散列地址上,這就產(chǎn)生了沖突搜索 就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)對象。搜索的結(jié)果通常有兩種可能：搜索成功,即找到滿足條件的數(shù) 據(jù)對象。這時(shí),作為結(jié)果,可報(bào)告該對象在結(jié)構(gòu)中的位置 , 還可給出該對象中的具體信息。搜索不成功,或搜索失敗。作為結(jié)果,應(yīng)報(bào)告一些信息 , 如失敗標(biāo)志、位置等搜索結(jié)構(gòu) 通常稱用于搜索的數(shù)據(jù)集合為搜索結(jié)構(gòu), 它是由

13、同一數(shù)據(jù)類型的對象 （或記錄 ）組成。在每個(gè)對象中有若干屬性, 其中有一個(gè)屬性,其值可唯一地標(biāo)識這個(gè)對象。稱為 關(guān)鍵碼 。使用基于關(guān)鍵碼的搜索,搜索結(jié)果應(yīng)是唯一的。但在實(shí) 際應(yīng)用時(shí),搜索條件是多方面的,可以使用基于屬性的搜索方法,但搜索結(jié)果可能不唯一。實(shí)施搜索時(shí)有兩種不同的 環(huán)境。靜態(tài)環(huán)境,搜索結(jié)構(gòu)在插入和刪除等操作的前后不發(fā)生改變。靜態(tài)搜索表 動(dòng)態(tài)環(huán)境,為保持較高的搜索效率, 搜索結(jié)構(gòu)在執(zhí)行插入和刪除等操作的前后將自動(dòng)進(jìn)行調(diào)整,結(jié)構(gòu)可能發(fā)生變化。動(dòng)態(tài)搜索表順序搜索 主要用于在線性表中搜索。 設(shè)若表中有 CurrentSize 個(gè)元素, 則順序搜索從表的先端開始, 順序用各元素的關(guān) 鍵碼與給定

14、值 x 進(jìn)行比較若找到與其值相等的元素,則搜索成功,給出該元素在表中的位置。若整個(gè)表都已檢測完仍學(xué)習(xí)資料收集于網(wǎng)絡(luò)，僅供參考未找到關(guān)鍵碼與 x 相等的元素，則搜索失敗。給出失敗信息二叉搜索樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：1每個(gè)結(jié)點(diǎn)都有一個(gè)作為搜索依據(jù)的關(guān)鍵碼(key)，所有結(jié)點(diǎn)的關(guān)鍵碼互不相同。 2 左子樹(如果非空)上所有結(jié)點(diǎn)的關(guān)鍵碼都小于根結(jié)點(diǎn)的關(guān)鍵碼。 3右子樹(如果非空)上 所有結(jié)點(diǎn)的關(guān)鍵碼都大于根結(jié)點(diǎn)的關(guān)鍵碼。 4 左子樹和右子樹也是二叉搜索樹。二叉搜索樹為二叉排序樹 如果對一棵二叉搜索樹進(jìn)行中序遍歷，可以按從小到大的順序，將各結(jié)點(diǎn)關(guān)鍵碼排列起來， 所以也稱二叉搜索樹為

15、二叉排序樹在二叉搜索樹上進(jìn)行搜索 ，是一個(gè)從根結(jié)點(diǎn)開始，沿某一個(gè)分支逐層向下進(jìn)行比較判等的過程。它可以是一個(gè)遞歸的 過程。假設(shè)想要在二叉搜索樹中搜索關(guān)鍵碼為 x 的元素，搜索過程從根結(jié)點(diǎn)開始。如果根指針為 NULL ，則搜索不成 功；否則用給定值 x 與根結(jié)點(diǎn)的關(guān)鍵碼進(jìn)行比較：若給定值等于根結(jié)點(diǎn)關(guān)鍵碼，則搜索成功，返回搜索成功信息并報(bào) 告搜索到結(jié)點(diǎn)地址。若給定值小于根結(jié)點(diǎn)的關(guān)鍵碼，則繼續(xù)遞歸搜索根結(jié)點(diǎn)的左子樹；否則。遞歸搜索根結(jié)點(diǎn)的右子 二叉搜索樹的插入算法： 為了向二叉搜索樹中插入一個(gè)新元素，必須先檢查這個(gè)元素是否在樹中已經(jīng)存在。在插入之 前，先使用搜索算法在樹中檢查要插入元素有還是沒有。如

16、果搜索成功，說明樹中已經(jīng)有這個(gè)元素，不再插入；如果 搜索不成功，說明樹中原來沒有關(guān)鍵碼等于給定值的結(jié)點(diǎn)，把新元素加到搜索操作停止的地方。圖定義：圖是由頂點(diǎn)集合(vertex)及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：Graph= ( V, E )其中V = x | x 某個(gè)數(shù)據(jù)對象是頂點(diǎn)的有窮非空集合；E = (x, y) | x, y V 或E = | x, y V & Path (x, y)，是頂點(diǎn)之間關(guān)系的有窮集合，也叫做邊(edge)集合。Path (x, y)表示從x到y(tǒng)的一條單向通路,它是有方向的。有向圖與無向圖：在有向圖中，頂點(diǎn)對是有序的。在無向圖中，頂點(diǎn)對(x, y)是無序的。完全

17、圖 ：若有 n 個(gè)頂點(diǎn)的無向圖有 n(n-1)/2 條邊, 則此圖為完全無向圖。有 n 個(gè)頂點(diǎn)的有向圖有 n(n-1) 條邊, 則此 圖為完全有向圖在圖的 鄰接矩陣 表示中，有一個(gè)記錄各個(gè)頂點(diǎn)信息的頂點(diǎn)表，還有一個(gè)表示各個(gè)頂點(diǎn)之間關(guān)系的鄰接矩陣。鄰接表 是鄰接矩陣的改進(jìn)形式。為此需要把鄰接矩陣的各行分別組織為一個(gè)單鏈表。在鄰接表中，同一個(gè)頂點(diǎn)發(fā)出的 邊鏈接在同一個(gè)邊鏈表中，每一個(gè)鏈結(jié)點(diǎn)代表一條邊(邊結(jié)點(diǎn)) ，結(jié)點(diǎn)中有另一頂點(diǎn)的下標(biāo) dest 和指針 link 。對于帶 權(quán)圖，邊結(jié)點(diǎn)中還要保存該邊的權(quán)值cost。頂點(diǎn)表的第i個(gè)頂點(diǎn)中保存該頂點(diǎn)的數(shù)據(jù)，以及它對應(yīng)邊鏈表的頭指針adj最短路徑問題 ：

18、如果從圖中某一頂點(diǎn)(稱為源點(diǎn))另一頂點(diǎn)(稱為終點(diǎn))的路徑可能不止一條，如何找到一條路徑使 得沿此路徑上各邊上的權(quán)值總和達(dá)到最小。排序 ：將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。數(shù)據(jù)表 (datalist): 它是待排序數(shù)據(jù)元素的有限集合。排序碼 (key): 通常數(shù)據(jù)元素有多個(gè)屬性域 , 即多個(gè)數(shù)據(jù)成員組成 , 其中有一個(gè)屬性域可用來區(qū)分元素 , 作為排序依據(jù)。 該域即為排序碼。每個(gè)數(shù)據(jù)表用哪個(gè)屬性域作為排序碼，要視具體的應(yīng)用需要而定。插入排序基本方法是 ：每步將一個(gè)待排序的元素， 按其排序碼大小， 插入到前面已經(jīng)排好序的一組元素的適當(dāng)位置上 , 直 到元素全部插入為止。學(xué)習(xí)資料學(xué)習(xí)資料

19、收集于網(wǎng)絡(luò)，僅供參考鏈表1、 單鏈表中的插入與刪除-:第一種情況：在第一個(gè)結(jié)點(diǎn)前插入種情況：在鏈表中間插/第二種情況：在鏈表末尾插入 newnodink=first;firs=newnode2、鏈表插入算法實(shí)現(xiàn)newn odink=Hi nkpHink=las=newnqdeintListlnse(Consbtx const ir)/在鏈表第個(gè)結(jié)點(diǎn)處插入新元素ListNo*pe= fi;stintk = 0 whiiep !=NUL& & k -1 )p = plink k+ /找第1個(gè)結(jié)點(diǎn) if(p = NU&first=NULLcou 無效的插入位n置return；ListNode Few

20、nodstNodNUDL/創(chuàng)建新結(jié)點(diǎn)數(shù)據(jù)為指針為if (first = NU|L=0 /插在表前newnodink = fi;rst if (first = NUlOst = newnode first = new;nodeelse 插在表中或末尾newnodink =-pink if(pdink = Nl)iast = newnode pink = newjnode return；在帶表頭結(jié)點(diǎn)的單鏈表newnodink =inknewnodink=pink pink=newnodeI 3鏈表結(jié)點(diǎn)刪除算法intListRemoveti X /在鏈表中刪除第吉點(diǎn) Noc*p = first; i

21、ntk= 0while p!=NULL& k-1 ) p =ink k+ /找第1個(gè)結(jié)點(diǎn)if (p = NULi nk = NL)_Lcou tempinti ,j; for(i =lef+1; i v=right+) if (Li=ef&temLj)Lj+件temp學(xué)習(xí)資料#includdataList.htemplate Tass voidBinarylnsertSort Ta&liList const left const right)/利用折半搜在L.Vector到Vector申 /查找L.Vecto應(yīng)插入的位再進(jìn)行插入Elemtempinti Jowhighmiddlk；for(i

22、=left+1 =right+) tem=Li； low=left high=i-1 whilow=high) /折半搜索插入位置 middte(low+high取中點(diǎn) if (tem= low; k-) Lk+1 = Lk;/成塊移動(dòng)，空出插入位置Llow = temp;/ 插入;堆排序的算法直接選擇排序的算法template #include dataList.hvoid HeapSort (dataList & L) template 對表 L.Vector0到 L.Vectorn-1進(jìn)行排序，使得表void SelectSort (dataList& L,中各個(gè)兀素按其排序碼非遞減有序

23、const int left, const int right) int i, n = L.length();for (int i = left; i = 0; i-)將表轉(zhuǎn)換為堆int k = i;/在 Li到Ln-1找最小排序碼兀素siftDown (L , i, n-1);for (int j = i+1 ; j = 0; i-) /對表排序if (Lj Lk) k = j;L.Swap(0 , i); siftDown (L, 0 , i-1); ;if (k != i) Swap (Li , Lk) ; /交換 ;希爾排序的算法起泡排序的算法#include dataList.hte

24、mplate template void BubbleSort (dataList & L, con st int left,void Shellsort (dataList & L,const int right) const int left, const intright) int pass = left+1, excha nge = 1;int i, j, gap = right-left+1 ;/增量的初始值while (pass= right & exchange) Eleme nt temp;exchange - 0;標(biāo)志為0假疋未交換do for (int j - right ; j - pass; j-)gap = gap/3+1;/求下一增量值if (Lj-1 Lj) /逆序for (i = left+gap; i = righ