1、i 課程總結(jié)（提要） -、數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型 ADT 定義：一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。 構(gòu)成一個(gè)抽象數(shù)據(jù)類型的三個(gè)要素是： 數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系、基本操作 v - v- 數(shù)據(jù)結(jié)構(gòu)（非數(shù)值計(jì)算程序設(shè)計(jì)問(wèn)題中的數(shù)學(xué)模型 ） 廠邏輯結(jié)構(gòu) （描述數(shù)據(jù)元素之間的關(guān)系） 線性結(jié)構(gòu)一一線性表、棧、隊(duì)列、串、數(shù)組、廣義表 非線性結(jié)構(gòu)樹和森林、二叉樹、圖 集合結(jié)構(gòu) 查找表、文件 存儲(chǔ)結(jié)構(gòu) （邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象） 按“關(guān)系”的表示方法不同而分： 順序結(jié)構(gòu)一以數(shù)據(jù)元素在存儲(chǔ)器中的一個(gè) 固定的相對(duì)位置來(lái)表示“關(guān)系” 鏈?zhǔn)浇Y(jié)構(gòu)一以指針表示數(shù)據(jù)元素的“后繼”或“前驅(qū)” -基本操作（三類） 結(jié)構(gòu)的建

2、立和銷毀 查找 一一引用型操作（不改變?cè)亻g的關(guān)系） r 按“關(guān)系”進(jìn)行檢索 y 按給定值進(jìn)行檢索 遍歷訪問(wèn)結(jié)構(gòu)中的每一個(gè)數(shù)據(jù)元素，且對(duì)每個(gè)元素只訪問(wèn)一次 修改 一一加工型操作（改變?cè)亻g的關(guān)系） 插入 刪除 更新（刪除+插入）二、線性結(jié)構(gòu) 2 線性表和有序表 不同存儲(chǔ)結(jié)構(gòu)的比較 順序表：可以實(shí)現(xiàn)隨機(jī)存取； (1) 插入和刪除時(shí)需要移動(dòng)元素；匚 (n) 需要預(yù)分配存儲(chǔ)空間； 適用于“不常進(jìn)行修改操作、表中元素相對(duì)穩(wěn)定”的場(chǎng)合。 鏈表：只能進(jìn)行順序存取； 0 (n) 插入和刪除時(shí)只需修改指針；o (1) 不需要預(yù)分配存儲(chǔ)空間； 適用于“修改操作頻繁、事先無(wú)法估計(jì)最大表長(zhǎng)”的場(chǎng)合。 應(yīng)用問(wèn)題的算法

3、時(shí)間復(fù)雜度的比較 例如，以線性表表示集合進(jìn)行運(yùn)算的時(shí)間復(fù)雜度為 -(n2), 而以有序表表示集合進(jìn)行運(yùn)算的時(shí)間復(fù)雜度為 o (n) 棧和隊(duì)列一一數(shù)據(jù)類型的特點(diǎn)及其應(yīng)用范疇 串一一和線性表的差異： 數(shù)據(jù)對(duì)象不同(數(shù)據(jù)元素限定為單個(gè)字符) 、基本操作集不同(串整體作 為操作對(duì)象)、存儲(chǔ)結(jié)構(gòu)不同 串的模式匹配算法 數(shù)組 一一只有引用型的操作，只需要順序存儲(chǔ)結(jié)構(gòu) 多維到一維的不同映象方法 ： 以行序?yàn)橹餍?低下標(biāo)優(yōu)先) 以列序?yàn)橹餍?高下標(biāo)優(yōu)先) 廣義表多層次的線性結(jié)構(gòu) 特性：次序性、長(zhǎng)度、層次性、深度、遞歸等 獨(dú)有的特性：共享 存儲(chǔ)結(jié)構(gòu)的特點(diǎn) 三、非線性結(jié)構(gòu) 3 - 樹和森林、二叉樹、圖 *數(shù)據(jù)類型

4、的定義（結(jié)構(gòu)特點(diǎn)和基本操作） -存儲(chǔ)結(jié)構(gòu) -二叉樹的特性及其證明方法 *遍歷 何謂“遍歷”？對(duì)結(jié)構(gòu)中的每個(gè)元素 都訪問(wèn)到，且只被訪問(wèn)一次 對(duì)非線性結(jié)構(gòu)的遍歷需要確定一條搜索路徑 兩條搜索路徑：深度優(yōu)先搜索和廣度優(yōu)先搜索 邏輯定義 深度優(yōu)先搜索 一一 以結(jié)構(gòu)中的某個(gè)數(shù)據(jù)元素為起始點(diǎn)，首先訪問(wèn)該數(shù)據(jù)元素， 然后依次以它的各個(gè)“后繼”為起始點(diǎn)進(jìn)行“深度優(yōu)先搜索遍歷” 。 其特點(diǎn)為：在訪問(wèn)了起始數(shù)據(jù)元素之后， 沿著某一條“路徑”（后繼）向前，直至“到 底”，然后退回一步找另一個(gè)后繼，再向前繼續(xù)， ，直至所有通路都走遍。 廣度優(yōu)先搜索 一一以結(jié)構(gòu)中的某個(gè)數(shù)據(jù)元素為起始點(diǎn)，首先訪問(wèn)該數(shù)據(jù)元素，然 后先訪問(wèn)

5、其所有后繼； 之后其它結(jié)點(diǎn)的訪問(wèn)次序由已被訪問(wèn)的結(jié)點(diǎn)的訪問(wèn)次序決 定： 先被訪問(wèn)的結(jié)點(diǎn)的后繼“優(yōu)先于”后被訪問(wèn)的結(jié)點(diǎn)的后繼 。 其特點(diǎn)為：在訪問(wèn)了起始數(shù)據(jù)元素之后，先訪問(wèn)它的所有后繼，然后再依這些后 繼被訪問(wèn)的先后次序訪問(wèn)它們的后繼， . ，直至沒(méi)有后繼未被訪問(wèn)為止。 算法的形式描述 深度優(yōu)先搜索 一一通常采用遞歸的形式 二叉樹（先序、中序、后序）、樹/圖（先根、后根） 一般形式算法的描述: void DFSearch(ADT DS, ElemType v) / 從 v 開始，對(duì) DS 進(jìn)行深度優(yōu)先搜索遍歷 if (DS) visit(v); (visitedv=true;) w=FirstS

6、ucc(v); 4 while (w) if (!visitedv) DFSearch(DS, w); w=NextSucc(DS, v, w); /while /if /DFSearch 不同數(shù)據(jù)結(jié)構(gòu) (邏輯和存儲(chǔ) )有不同寫法。 例如對(duì)森林， 起始點(diǎn)只有一個(gè) (第一棵樹的根 )，只有兩個(gè)后繼， 且各棵樹互不 相交，按搜索路徑上的訪問(wèn)次序有先序遍歷和中序遍歷之分。 void PreOrder_F(CSTree T) / 對(duì)以 T 為根指針的森林進(jìn)行先序遍歷 if (T) visit(T-data); PreOrder_F( T-firstchild ); / 先序遍歷第一棵樹的子樹森林 Pr

7、eOrder_F( T-nextsibling ); / 先序遍歷其余樹構(gòu)成的森林 /if / PreOrder_F 或者從森林是樹的集合角度來(lái)看遍歷 (依次從左至右依次先根遍歷各棵子樹 ) while (樹)do PreOrder_T(樹); void PreOrder_T(CSTree T) 5 / 對(duì)以 T 為根指針的樹進(jìn)行先根遍歷 if （T） visit（T-data）; p=T-firstchild; while（p） PreOrder_T（p）; / 對(duì)以 p 為根指針的子樹進(jìn)行先根遍歷 p=p-next; /while / PreOrder_T 由“訪問(wèn)”操作的不同可以實(shí)現(xiàn)不同

8、的操作 具體問(wèn)題具體分析，按分割求解的思想 : “遞歸基”考慮最簡(jiǎn)單的結(jié)構(gòu)（ “空集” / “只含一個(gè)元素” ） “歸納項(xiàng)”分析原問(wèn)題和子問(wèn)題之間的關(guān)系 不同的問(wèn)題要求不同的搜索路徑 “線索化 ”的過(guò)程即為在遍歷過(guò)程中建立結(jié)點(diǎn)之間的線性關(guān)系 廣度優(yōu)先搜索 不能用遞歸（先進(jìn)先出） 必須利用“隊(duì)列”記下訪問(wèn)次序，以便由此確定以后的元素的訪問(wèn)次序 對(duì)不同的存儲(chǔ)結(jié)構(gòu)，算法的差異 不同的存儲(chǔ)結(jié)構(gòu)表現(xiàn)在表示“后繼”的方法不同 二叉樹 二叉鏈表（靜態(tài)、動(dòng)態(tài)） 、順序表 （只適用于完全二叉樹 ） 樹一一 孩子-兄弟鏈表、孩子鏈表（三三圖的鄰接表）、雙親鏈表 圖 鄰接表、鄰接矩陣 具體算法采用何種存儲(chǔ)結(jié)構(gòu)由算法

9、需要解決的問(wèn)題而定 6 四、查找表 集合結(jié)構(gòu) 根據(jù)查找表所需進(jìn)行的操作種類和期望達(dá)到的 ASL 來(lái)選擇構(gòu)造查找表的方法 7 順序表、有序表(靜態(tài)查找樹)、索引順序表 一一靜態(tài)查找表 二叉排序樹、B-樹和B+樹、鍵樹 查找樹 哈希表一一動(dòng)態(tài)查找表也可用于表示靜態(tài)查找表 各自的特點(diǎn)、操作的實(shí)現(xiàn)方法，注意 它們之間的相同點(diǎn)和不同點(diǎn) 例如：順序表的特點(diǎn)是：結(jié)構(gòu)簡(jiǎn)單，便于插入但不便于刪除；平均查找長(zhǎng)度 較大ASL=O(n)，查找樹？哈希表？靜態(tài)查找樹和折半查找的關(guān)系？和動(dòng)態(tài)查找樹 的區(qū)別？ 平均查找長(zhǎng)度的計(jì)算公式對(duì)任何查找表都適用 關(guān)鍵在于如何計(jì)算Ci 判定樹和ASL的計(jì)算方法 - 判定樹用于描述查找方

10、法，關(guān)鍵字在判定樹上的層次恰為找到它時(shí)和給定 值進(jìn)行比較的次數(shù)。注意判定樹的畫法取決于查找方法的本身而不是具體的算法 判定樹非程序流圖 哈希表的特點(diǎn) 是在關(guān)鍵字和記錄的存儲(chǔ)地址之間建立了一個(gè)映象關(guān)系，以此減少查找的盲 目性，哈希表的最大特點(diǎn)是它的平均查找長(zhǎng)度不是表長(zhǎng)的函數(shù)，因此利用它可以 設(shè)計(jì)出使平均查找長(zhǎng)度控制在期望值范圍內(nèi)的查找表。 如何構(gòu)造哈希表以及如何計(jì)算它的 Ci。 在特殊的情況下，可以做到 ASL=0 - 無(wú)法畫出它的判定樹 掌握各種構(gòu)造哈希表的方法以及處理沖突的方法 五、內(nèi)部排序 進(jìn)行排序的目的： 得到有序表 般情況 ASL pi Ci i =1 i i n 1 、qiC i i

11、 =1 下只考慮查找成功的平均查找長(zhǎng)度，即 x Pi=- 8 排序和查找相互關(guān)聯(lián)，有時(shí)排序的過(guò)程也可以看成是一個(gè)動(dòng)態(tài)造表的過(guò)程， 如：插入排序；二叉查找樹 了解各種排序方法的特點(diǎn)以便靈活應(yīng)用 例如： 直接插入排序適用于“近似有序序列” ； 快排的思想可用以“調(diào)整” ； 選擇排序、起泡排序和堆排序可用以“選出若干滿足條件元素” 各種排序方法的混合使用 排序算法的描述 例如： 一次劃分、建堆 算法和存儲(chǔ)結(jié)構(gòu)的關(guān)系 注意排序時(shí)采用的鏈表為什么不是動(dòng)態(tài)鏈表 排序算法的時(shí)間復(fù)雜度及其簡(jiǎn)單分析方法 各種排序方法的綜合比較 時(shí)間性能平均情況、最壞情況、最好情況 （從關(guān)鍵字的比較和記錄的移動(dòng)兩個(gè)方面進(jìn)行分析 ） 空間性能需要的輔助空間 六、 外部排序 外部排序的基本過(guò)程及其訪問(wèn)外存的次數(shù) 多路歸并 置換 -