【正文】 這樣，圖G就可以由這個(gè)表頭向量來(lái)表示和存取。鄰接表(adjacency list)是對(duì)圖中的每個(gè)頂點(diǎn)建立一個(gè)鄰接關(guān)系的單鏈表，并把它們的表頭指針用向量存儲(chǔ)的一種圖的表示方法。 0, 對(duì)應(yīng)邊不存在于E(G)中v 從鄰接矩陣中可查兩個(gè)結(jié)點(diǎn)的之間是否存在通路，若兩個(gè)結(jié)點(diǎn)的坐標(biāo)的交叉其值不為零并不是一個(gè)很大的值的話，則有通路，否則沒(méi)有通路。若頂點(diǎn)集為空，則邊集必然為空，若頂點(diǎn)集非空，則邊集可空可不空，當(dāng)邊集為空時(shí)，圖G中的頂點(diǎn)均為孤立頂點(diǎn)。 (2) 結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長(zhǎng)度 在許多應(yīng)用中，常常將樹(shù)中的結(jié)點(diǎn)賦予一個(gè)有著某種意義的實(shí)數(shù)，我們稱此實(shí)數(shù)為該結(jié)點(diǎn)的權(quán)。(1) 若樹(shù)根結(jié)點(diǎn)存在左孩子，則樹(shù)根結(jié)點(diǎn)的值小于等于左孩子結(jié)點(diǎn)的值；(2) 若樹(shù)根結(jié)點(diǎn)存在右孩子，則樹(shù)根結(jié)點(diǎn)的值小于等于右孩子結(jié)點(diǎn)的值；(3) 以左、右孩子為根的子樹(shù)又同樣各是一個(gè)堆。 (1) 若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均小于樹(shù)根結(jié)點(diǎn)的關(guān)鍵字； (2) 若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均大于樹(shù)根結(jié)點(diǎn)的關(guān)鍵字； (3) 左、右子樹(shù)本身又各是一棵二叉搜索樹(shù)。完全二叉樹(shù)中深度h和結(jié)點(diǎn)數(shù)n之間的關(guān)系，在理想平衡樹(shù)中同樣成立，了解二叉樹(shù)的鏈接存儲(chǔ)結(jié)構(gòu)根據(jù)二叉樹(shù)的特性，任何一個(gè)結(jié)點(diǎn)最多有左、右兩棵子樹(shù)，所以每個(gè)結(jié)點(diǎn)至少設(shè)有三個(gè)域：數(shù)據(jù)域和左、右指針域。 完全二叉樹(shù)的深度h和結(jié)點(diǎn)數(shù)n的關(guān)系，還可表示為： 2h1≤n2h 取對(duì)數(shù)后得： h1≤log2nh 即： log2nh≤log2n+1 因h只能取整數(shù)，所以： h= 235。性質(zhì)5：具有n個(gè)(n0)結(jié)點(diǎn)的完全二叉樹(shù)的深度為233。x性質(zhì)2： 深度為k的二叉樹(shù)，最多有2k1個(gè)結(jié)點(diǎn) ( k ≥1)。logk( n(k1)+1)249。 v 性質(zhì)3 深度為h的k叉樹(shù)至多有 個(gè)結(jié)點(diǎn)。在有序樹(shù)中，改變了子樹(shù)的相對(duì)次序就變成了另一棵樹(shù)。v 分支結(jié)點(diǎn)：度非零的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)或稱為非終端結(jié)點(diǎn)。能給出在特定要求下的進(jìn)出棧序列以及判斷某些出棧序列出現(xiàn)的可能性了解棧的順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)，棧頂指針的設(shè)置了解棧的鏈接存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)、棧頂指針的更改熟悉棧在順序和鏈接存儲(chǔ)結(jié)構(gòu)下的進(jìn)棧、出棧和讀取棧頂元素的操作程序了解遞歸算法的特點(diǎn)及遞歸算法的中止條件，會(huì)結(jié)合具體程序來(lái)分析遞歸程序的合理性了解隊(duì)列的定義和它的順序存儲(chǔ)結(jié)構(gòu)v 隊(duì)列（queue）簡(jiǎn)稱隊(duì)，它也是一種運(yùn)算受限的線性表，其限制是僅允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除。那么，指向頭結(jié)點(diǎn)的指針就是頭指針。雙向鏈表是指線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針，一個(gè)稱為左指針，用以指向其直接前驅(qū)；另一個(gè)稱為右指針，用以指向其直接后繼。 線性表的順序存儲(chǔ)指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。 如順序表和鏈表具有相同的邏輯結(jié)構(gòu)，但存儲(chǔ)結(jié)構(gòu)分別為順序結(jié)構(gòu)和鏈表結(jié)構(gòu)算法的設(shè)計(jì)要求有那些，會(huì)結(jié)合實(shí)際的語(yǔ)言設(shè)計(jì)來(lái)說(shuō)明這些要求1）正確性：對(duì)于合法的輸入產(chǎn)生符合要求的輸出；2）可讀性：算法應(yīng)該易讀、便于交流， 這也是保證算法正確性的前提；添加注釋也是一種增加可讀性的辦法；3）健壯性：當(dāng)輸入非法時(shí)， 算法還能做出適當(dāng)?shù)姆磻?yīng)而不會(huì)崩潰， 如輸出錯(cuò)誤信息；算法中應(yīng)該考慮適當(dāng)?shù)腻e(cuò)誤處理；4）效率高且內(nèi)存消耗小：效率高指運(yùn)行時(shí)間短。v 集合結(jié)構(gòu)中的元素是各自獨(dú)立的，元素之間沒(méi)有聯(lián)系v 線性結(jié)構(gòu)中的元素是一個(gè)接一個(gè)串聯(lián)起來(lái)的，它有一個(gè)頭元素和一個(gè)尾元素，其余為中間元素；每個(gè)中間元素既有前驅(qū)元素，又有后繼元素v 在樹(shù)結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)只有后繼結(jié)點(diǎn)，而沒(méi)有前驅(qū)結(jié)點(diǎn)；除樹(shù)根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有唯一一個(gè)前驅(qū)結(jié)點(diǎn)，又稱為是父結(jié)點(diǎn)或雙親結(jié)點(diǎn)v 在圖結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)或稱頂點(diǎn)都可以有任意多個(gè)前驅(qū)結(jié)點(diǎn)和任意多個(gè)后繼結(jié)點(diǎn)。（1）順序的方法: 將邏輯上相鄰的元素存儲(chǔ)到物理上相鄰的存儲(chǔ)位置. 常用于線性的數(shù)據(jù)結(jié)構(gòu).（2）鏈?zhǔn)浇Y(jié)構(gòu)：給結(jié)點(diǎn)附加一個(gè)指針字段, 指出其后繼節(jié)點(diǎn)的位置, 即存放結(jié)點(diǎn)的存儲(chǔ)單元分為兩部分:數(shù)據(jù)項(xiàng)指針項(xiàng)（3）散列（hashing) 結(jié)構(gòu)：散列的方法是用結(jié)點(diǎn)的關(guān)鍵字值直接計(jì)算出結(jié)點(diǎn)的存儲(chǔ)地址。第二章 線性表了解并掌握線性表的定義及性質(zhì)線性表是線性結(jié)構(gòu)的一種表現(xiàn)形式，即是具有相同屬性數(shù)據(jù)元素的一個(gè)有限序列，序列中的元素是一個(gè)接一個(gè)在邏輯上是有序的，序列中元素的個(gè)數(shù)就是該線性表的長(zhǎng)度.v 存在唯一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素v 存在唯一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素v 除起點(diǎn)元素之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)v 除終點(diǎn)元素之外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼v 起點(diǎn)元素只有后繼沒(méi)有前驅(qū)，終點(diǎn)元素只有前驅(qū)沒(méi)有后繼 v 對(duì)于線性表中的數(shù)據(jù)元素ai1和ai來(lái)說(shuō)，ai1是ai的直接前驅(qū)，ai是ai1的直接后繼。v 長(zhǎng)度可以任意擴(kuò)充，存儲(chǔ)效率較高；v 物理存儲(chǔ)可以是不連續(xù)的；v 數(shù)據(jù)元素的邏輯次序可以與其存儲(chǔ)的物理次序不一致。若 L 為“空”(L = NULL)，則所表示的線性表為“空”表，其長(zhǎng)度為“零”。動(dòng)態(tài)鏈表是順序存儲(chǔ)結(jié)構(gòu)，表中的任一結(jié)點(diǎn)都需要從頭指針起順鏈掃描才能取得，時(shí)間復(fù)雜度為O(n)(n為表長(zhǎng))。 v 結(jié)點(diǎn)的度：樹(shù)中每個(gè)結(jié)點(diǎn)具有的非空子樹(shù)數(shù)或者說(shuō)后繼結(jié)點(diǎn)數(shù)被定義為該結(jié)點(diǎn)的度（degree）。v 子孫結(jié)點(diǎn)：每個(gè)結(jié)點(diǎn)的所有子樹(shù)中的結(jié)點(diǎn)被稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)v 祖先結(jié)點(diǎn)：從整個(gè)（子）樹(shù)的根結(jié)點(diǎn)到達(dá)該