《算法與數(shù)據(jù)結(jié)構(gòu)》PPT課件.ppt

第5章算法與數(shù)據(jù)結(jié)構(gòu) 5 1算法與數(shù)據(jù)結(jié)構(gòu)的基本概念 5 1 1算法算法 是一個(gè)有窮的指令集 是解決某一問(wèn)題的運(yùn)算序列 算法一般應(yīng)具有以下幾個(gè)基本特征 1 可行性 2 確定性 3 有窮性 4 有0個(gè)或多個(gè)輸入 5 有一個(gè)或多個(gè)輸出 1 算法的兩個(gè)基本要素 1 對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作1 算術(shù)運(yùn)算 主要有加 減 乘 除等運(yùn)算 2 邏輯運(yùn)算 主要有與 或 非等運(yùn)算 3 關(guān)系運(yùn)算 主要有大于 小于 等于 不等于等運(yùn)算 4 數(shù)據(jù)傳輸 主要包括賦值 輸入 輸出等操作 2 算法的控制結(jié)構(gòu)算法中各操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu) 一個(gè)算法一般都可以用順序 選擇 循環(huán)三種基本控制結(jié)構(gòu)組合而成 2 算法設(shè)計(jì)基本方法 1 列舉法列舉法是針對(duì)待解決的問(wèn)題 列舉所有可能的情況 并用問(wèn)題中給定的條件來(lái)檢驗(yàn)?zāi)男┦潜匦璧?哪些是不需要的 2 歸納法歸納法是從特殊到一般的抽象過(guò)程 通過(guò)分析少量的特殊情況 找出一般的關(guān)系 3 遞歸遞歸分為直接遞歸與間接遞歸兩種 如果一個(gè)算法A顯式地調(diào)用自己則稱為直接遞歸 如果算法A調(diào)用另一個(gè)算法B 而算法B又調(diào)用算法A 則稱為間接遞歸調(diào)用 4 回溯法通過(guò)對(duì)待解決的問(wèn)題進(jìn)行分析 找出一個(gè)解決問(wèn)題的線索 然后根據(jù)這個(gè)線索進(jìn)行探測(cè) 若探測(cè)成功便可得到問(wèn)題的解 若探測(cè)失敗 就要逐步回退 改換別的路經(jīng)進(jìn)一步探測(cè) 直到問(wèn)題得到解答或問(wèn)題最終無(wú)解 5 1 2算法的事前估計(jì) 我們可以在算法運(yùn)行之前對(duì)算法進(jìn)行估計(jì) 它可以分為空間復(fù)雜度和時(shí)間復(fù)雜度 1 算法的空間復(fù)雜度算法的空間復(fù)雜度是對(duì)算法所需存儲(chǔ)空間的度量 2 算法的時(shí)間復(fù)雜度所謂算法的時(shí)間復(fù)雜度 是指執(zhí)行算法所需要的計(jì)算工作量 通常 一個(gè)算法所用的時(shí)間等于編譯時(shí)間加上運(yùn)行時(shí)間 5 1 3數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)處理 是指對(duì)數(shù)據(jù)集合中的各元素以各種方式進(jìn)行操作 包括插入 刪除 查找 更改等 也包括對(duì)數(shù)據(jù)元素進(jìn)行分析 數(shù)據(jù)的組織方式不同 通常對(duì)它進(jìn)行處理時(shí)的效率也不同 如 對(duì)兩個(gè)存放相同元素的表進(jìn)行查找時(shí) 一個(gè)表中的所有數(shù)據(jù)元素是沒(méi)有規(guī)律的 而另外一個(gè)表中的元素是經(jīng)過(guò)排序的 則對(duì)于前者用順序查詢法進(jìn)行查找 后者采用折半查詢法進(jìn)行查詢 可見(jiàn)后者效率較高 數(shù)據(jù)結(jié)構(gòu) 是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合 數(shù)據(jù)元素 在數(shù)據(jù)處理領(lǐng)域中 每一個(gè)需要處理的對(duì)象都可以抽象成數(shù)據(jù)元素 數(shù)據(jù)元素一般簡(jiǎn)稱為元素 作為某種處理 其中的數(shù)據(jù)元素一般具有某種共同特征 例如 描述一年四季的季節(jié)名 春 夏 秋 冬 可以作為季節(jié)的數(shù)據(jù)元素 表示家庭成員的各成員名 父親 兒子 女兒 可以作為家庭成員的數(shù)據(jù)元素 表示數(shù)值的各個(gè)數(shù) 35 21 44 70 66 可以作為數(shù)值的數(shù)據(jù)元素 一般情況下 在具有相同特征的數(shù)據(jù)元素集合中 各個(gè)數(shù)據(jù)元素之間存在著關(guān)系 這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu) 在數(shù)據(jù)處理領(lǐng)域中 通常把數(shù)據(jù)元素之間這種固有的關(guān)系簡(jiǎn)單地用前后件關(guān)系 或直接前驅(qū)與直接后繼關(guān)系 來(lái)描述 例如 一年四個(gè)季節(jié)的順序關(guān)系時(shí) 則 春 是 夏 的前件 即直接前驅(qū) 下同 而 夏 是 春 的后件 即直接后繼 下同 1 數(shù)據(jù)的邏輯結(jié)構(gòu)所謂數(shù)據(jù)的邏輯結(jié)構(gòu) 是指描述數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)由某一數(shù)據(jù)對(duì)象及該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系 前后件關(guān)系 組成 即一個(gè)數(shù)據(jù)結(jié)構(gòu)可以表示成 Data Structure D R 上式中Data Structure表示數(shù)據(jù)結(jié)構(gòu) D是數(shù)據(jù)元素的集合 R是D上的關(guān)系 它反映了D中各數(shù)據(jù)元素之間的前后件關(guān)系 例如 設(shè)a與b是D中的兩個(gè)數(shù)據(jù) 則二元組 a b 表示a是b的前件 b是a的后件 例如 一年四季的數(shù)據(jù)邏輯結(jié)構(gòu)可以表示為 B D R D 春 夏 秋 冬 R 春 夏 夏 秋 秋 冬 2 數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)方式稱為數(shù)據(jù)的物理結(jié)構(gòu) 它包括數(shù)據(jù)元素的存儲(chǔ)方式和關(guān)系的存儲(chǔ)方式 一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲(chǔ)結(jié)構(gòu) 常用的存儲(chǔ)結(jié)構(gòu)有順序 鏈接 索引等存儲(chǔ)結(jié)構(gòu) 采用不同的存儲(chǔ)結(jié)構(gòu) 其數(shù)據(jù)處理的效率是不同的 5 1 4線性結(jié)構(gòu)與非線性結(jié)構(gòu) 空的數(shù)據(jù)結(jié)構(gòu) 如果在一個(gè)數(shù)據(jù)結(jié)構(gòu)中一個(gè)數(shù)據(jù)元素都沒(méi)有 則稱該數(shù)據(jù)結(jié)構(gòu)為空的數(shù)據(jù)結(jié)構(gòu) 在一個(gè)空的數(shù)據(jù)結(jié)構(gòu)中插入一個(gè)新的元素后就變?yōu)榉强盏臄?shù)據(jù)結(jié)構(gòu) 根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性 一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型 線性結(jié)構(gòu)與非線性結(jié)構(gòu) 線性結(jié)構(gòu) 如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件 1 有且只有一個(gè)根結(jié)點(diǎn) 2 每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件 也最多有一個(gè)后件 則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu) 線性結(jié)構(gòu)又稱線性表 如一年四季這個(gè)數(shù)據(jù)結(jié)構(gòu)就屬于線性結(jié)構(gòu) 如圖所示 在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)后還應(yīng)是線性結(jié)構(gòu) 非線性結(jié)構(gòu) 如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu) 則稱之為非線性結(jié)構(gòu) 如家庭成員間輩分關(guān)系的數(shù)據(jù)結(jié)構(gòu)就屬于非線性結(jié)構(gòu) 如圖所示 顯然 在非線性結(jié)構(gòu)中 各數(shù)據(jù)元素之間的前后件關(guān)系要比線性結(jié)構(gòu)復(fù)雜 因此 對(duì)非線性結(jié)構(gòu)的存儲(chǔ)與處理比線性結(jié)構(gòu)要復(fù)雜得多 5 2線性表與線性鏈表 5 2 1線性表1 線性表的基本概念線性表是最簡(jiǎn)單且最常用的一種數(shù)據(jù)結(jié)構(gòu) 一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列 表中的每一個(gè)數(shù)據(jù)元素 除了第一個(gè)外 有且只有一個(gè)前件 除了最后一個(gè)外 有且只有一個(gè)后件 線性表或是一個(gè)空表 或可以表示為 a1 a2 ai an 其中ai i 1 2 n 是屬于數(shù)據(jù)對(duì)象的元素 通常也稱其為線性表中的一個(gè)結(jié)點(diǎn) 如26個(gè)英文字母的字母表 A B C Z 是一個(gè)長(zhǎng)度為26的線性表 其中的數(shù)據(jù)元素是單個(gè)字母字符 在稍微復(fù)雜的線性表中 一個(gè)數(shù)據(jù)元素還可以由若干個(gè)數(shù)據(jù)項(xiàng)組成 例如 某班的學(xué)生情況登記表是一個(gè)復(fù)雜的線性表 表中每一個(gè)學(xué)生的情況就組成了線性表中的每一個(gè)元素 每一個(gè)數(shù)據(jù)元素包括姓名 學(xué)號(hào) 性別 年齡和健康狀況5個(gè)數(shù)據(jù)項(xiàng) 如表所示 2 線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素 線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn) 1 線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的 2 線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的 在線性表的順序存儲(chǔ)結(jié)構(gòu)中 如果線性表中各數(shù)據(jù)元素所占的存儲(chǔ)空間 字節(jié)數(shù) 相等 則要在該線性表中查找某一個(gè)元素是很方便的 假設(shè)線性表中的第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為L(zhǎng)OC b1 每一個(gè)數(shù)據(jù)元素占m個(gè)字節(jié) 則線性表中第i個(gè)元素bi在計(jì)算機(jī)存儲(chǔ)空間中的存儲(chǔ)地址為 LOC bi LOC b1 i 1 m 在計(jì)算機(jī)中的順序存儲(chǔ)結(jié)構(gòu)如圖所示 3 順序表的插入操作在一般情況下 要在第i 1 i n 個(gè)元素之前插入一個(gè)新元素時(shí) 首先要從最后一個(gè) 即第n個(gè) 元素開(kāi)始 直到第i個(gè)元素之間共n i 1元素依次向后移動(dòng)一個(gè)位置 移動(dòng)結(jié)束后 第i個(gè)位置就被空出 然后將新元素插入到第i項(xiàng) 插入結(jié)束后 線性表的長(zhǎng)度就增加了1 圖 a 為長(zhǎng)度6的線性表順序存儲(chǔ)在長(zhǎng)度為7的存儲(chǔ)空間中 現(xiàn)在要求在第5個(gè)元素之前插入一個(gè)新元素25 具體操作步驟為 首先從最后一個(gè)元素開(kāi)始直到第5個(gè)元素 將其中的每一個(gè)元素均依次往后移動(dòng)一個(gè)位置 然后將新元素25插入到第5個(gè)位置 插入一個(gè)新元素后 線性表的長(zhǎng)度變成了7 如圖 b 所示 這時(shí) 為線性表開(kāi)辟的存儲(chǔ)空間已經(jīng)滿了 如果再要插入 則會(huì)造成稱為 上溢 的錯(cuò)誤 4 順序表的刪除操作在一般情況下 要?jiǎng)h除第i 1 i n 個(gè)元素時(shí) 則要從第i 1個(gè)元素開(kāi)始 直到第n個(gè)元素之間共n i個(gè)元素依次向前移動(dòng)一個(gè)位置 刪除結(jié)束后 線性表的長(zhǎng)度就減小了1 圖 a 為一個(gè)長(zhǎng)度為6的線性表順序存儲(chǔ)在長(zhǎng)度為7的存儲(chǔ)空間中 現(xiàn)在要求刪除線性表中的第3個(gè)元素 即刪除元素5 具體操作步驟為 從第4個(gè)元素開(kāi)始直到最后一個(gè)元素 將其中的每一個(gè)元素均依次往前移動(dòng)一個(gè)位置 此時(shí) 線性表的長(zhǎng)度變成了5 如圖 b 所示 5 2 2線性鏈表 線性表的順序存儲(chǔ)結(jié)構(gòu)具有簡(jiǎn)單 操作方便等優(yōu)點(diǎn) 但在做插入或刪除操作時(shí) 需要移動(dòng)大量的元素 因此 對(duì)于大的線性表 特別是元素變動(dòng)頻繁的大線性表不宜采用順序存儲(chǔ)結(jié)構(gòu) 而是通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中 存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù) 各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致 鏈?zhǔn)酱鎯?chǔ)方式既可用于表示線性結(jié)構(gòu) 也可用于表示非線性結(jié)構(gòu) 假設(shè)數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)數(shù)據(jù)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)存儲(chǔ)單元 這種存儲(chǔ)單元稱為存儲(chǔ)結(jié)點(diǎn) 簡(jiǎn)稱結(jié)點(diǎn) 在鏈?zhǔn)酱鎯?chǔ)方式中 要求每個(gè)結(jié)點(diǎn)由兩部分組成 一部分用于存放數(shù)據(jù)元素值 稱為數(shù)據(jù)域 另一部分用于存放指針 稱為指針域 其中指針用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn) 從而可以表示數(shù)據(jù)元素之間的邏輯關(guān)系 我們把線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表 線性鏈表中存儲(chǔ)結(jié)點(diǎn)的結(jié)構(gòu)如圖所示 存儲(chǔ)地址i 在線性鏈表中 用一個(gè)專門的指針H 稱為頭指針 指向線性鏈表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn) 即存放線性表中第一個(gè)數(shù)據(jù)元素的存儲(chǔ)結(jié)點(diǎn)的序號(hào) 從頭指針開(kāi)始 沿著線性鏈表各結(jié)點(diǎn)的指針可以掃描到鏈表中的所有結(jié)點(diǎn) 線性表中最后一個(gè)元素沒(méi)有后件 因此 線性鏈表中最后一個(gè)節(jié)點(diǎn)的指針域?yàn)榭?用 NULL或0表示 表示鏈表終止 當(dāng)頭指針H NULL 或0 時(shí)稱為空表 在某些應(yīng)用中 對(duì)線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針 一個(gè)稱為左指針 用以指向其直接前驅(qū) 另一個(gè)稱為右指針 用以指向其直接后繼 這樣的線性鏈表稱為雙向鏈表 5 2 3對(duì)線性鏈表的基本操作 1 在線性鏈表中查找指定的元素在非空線性鏈表中尋找包含指定元素值x的前一個(gè)結(jié)點(diǎn)n的操作過(guò)程為 從頭指針指向的結(jié)點(diǎn)開(kāi)始向后沿指針進(jìn)行掃描 直到后面已經(jīng)沒(méi)有結(jié)點(diǎn)或下一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閤為止 因此 由這種方法找到的結(jié)點(diǎn)n有兩種可能 當(dāng)線性鏈表中存在包含元素x的結(jié)點(diǎn)時(shí) 則找到的n為首次發(fā)現(xiàn)的包含元素x的前一個(gè)結(jié)點(diǎn)序號(hào) 當(dāng)線性鏈表中不存在包含元素x的結(jié)點(diǎn)時(shí) 則找到的n為線性鏈表中的最后一個(gè)結(jié)點(diǎn)序號(hào) 2 線性鏈表的插入線性鏈表的插入操作是指在線性鏈表中的指定位置上插入一個(gè)新的元素 為了要在線性鏈表中插入一個(gè)新元素 首先要為該元素申請(qǐng)一個(gè)新結(jié)點(diǎn) 以存儲(chǔ)該元素的值 然后將存放新元素值的結(jié)點(diǎn)鏈接到線性鏈表中指定的位置 3 線性鏈表的刪除線性鏈表的刪除是指在線性鏈表中刪除包含指定元素的結(jié)點(diǎn) 為了在線性鏈表中刪除包含指定元素的結(jié)點(diǎn) 首先要在線性鏈表中找到這個(gè)結(jié)點(diǎn) 然后將要?jiǎng)h除結(jié)點(diǎn)釋放 以便于以后再次利用 4 循環(huán)鏈表及其基本操作循環(huán)鏈表的結(jié)構(gòu)與前面所討論的線性鏈表相比 具有以下兩個(gè)特點(diǎn) 1 在循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn) 表頭結(jié)點(diǎn)的數(shù)據(jù)域可以是任意值 也可以根據(jù)需要來(lái)設(shè)置 指針域指向線性表的第一個(gè)元素的結(jié)點(diǎn) 循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn) 2 循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不為空 而是指向表頭結(jié)點(diǎn) 從而在循環(huán)鏈表中 所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán) 5 3棧和隊(duì)列 5 3 1棧1 什么是棧棧實(shí)際上是一種特殊的線性表 在這種特殊的線性表中 插入與刪除操作都只在線性表的一端進(jìn)行 因此 棧是指被限定僅在一端進(jìn)行插入與刪除操作的線性表 在棧中 允許插入與刪除的一端稱為棧頂 而不允許插入和刪除的另一端稱為棧底 棧是按照 后進(jìn)先出 的原則組織數(shù)據(jù)的 因此 棧也被稱為 后進(jìn)先出 的線性表 在程序設(shè)計(jì)語(yǔ)言中 一般用一維數(shù)組作為隊(duì)列的順序存儲(chǔ)空間 通常用指針top來(lái)指示棧頂?shù)奈恢?用指針bottom指向棧底 向棧中插入一個(gè)元素稱為進(jìn)棧操作 從棧中刪除一個(gè)元素稱為出棧操作 棧頂指針top動(dòng)態(tài)反映了棧中元素的變化情況 圖是棧的示意圖 棧頂top 棧底bottom 進(jìn)棧出棧 2 對(duì)棧的操作對(duì)棧的基本操作有兩種 進(jìn)棧和出棧 1 進(jìn)棧操作進(jìn)棧操作是指在棧頂位置插入一個(gè)新元素 其過(guò)程是 先將棧頂指針加一 然后將新元素放到棧頂指針指向的位置 當(dāng)棧頂指針已經(jīng)指向存儲(chǔ)空間的最后一個(gè)位置時(shí) 說(shuō)明?？臻g已滿 不能再進(jìn)棧 這種情況稱為棧 上溢 錯(cuò)誤 2 出棧操作出棧操作是指取出棧頂元素 其過(guò)程是 先將棧頂指針指向的元素賦給一個(gè)指定的變量 然后將棧頂指針減1 當(dāng)棧頂指針為0時(shí) 說(shuō)明?？?不能再出棧 這種情況稱為棧 下溢 錯(cuò)誤 5 3 2隊(duì)列 1 什么是隊(duì)列隊(duì)列是指只允許在一端進(jìn)行插入 而在另一端進(jìn)行刪除的線性表 允許插入的一端稱為隊(duì)尾 通常用一個(gè)稱為尾指針 rear 的指針指向隊(duì)尾元素 允許刪除的一端稱為隊(duì)頭 通常也用一個(gè)隊(duì)頭指針 front 指向隊(duì)頭元素的前一個(gè)位置 隊(duì)列是按照 先進(jìn)先出 的原則組織數(shù)據(jù)的 因此隊(duì)列又稱為 后進(jìn)后出 的線性表 在隊(duì)列中 隊(duì)尾指針rear與隊(duì)頭指針front共同反映了隊(duì)列元素中元素動(dòng)態(tài)變化的情況 下圖是隊(duì)列的示意圖 front rear 向隊(duì)列的隊(duì)尾插入一個(gè)元素稱為進(jìn)隊(duì)操作 從隊(duì)列的隊(duì)頭刪除一個(gè)元素稱為出隊(duì)操作 由上圖可知 在隊(duì)列的末尾插入一個(gè)元素 進(jìn)隊(duì)操作 只涉及隊(duì)尾指針rear的變化 而要?jiǎng)h除隊(duì)列中的隊(duì)頭元素 出隊(duì)操作 只涉及隊(duì)頭指針front的變化 2 循環(huán)隊(duì)列及其操作循環(huán)隊(duì)列是一種將順序隊(duì)列臆造為一個(gè)環(huán)狀的空間的方法 通過(guò)把存儲(chǔ)隊(duì)列元素的表在邏輯上看成一個(gè)環(huán) 將隊(duì)列存儲(chǔ)空間的第一個(gè)位置作為隊(duì)列最后一個(gè)位置的下一個(gè)位置 供隊(duì)列循環(huán)使用 循環(huán)隊(duì)列的初始狀態(tài)為空 即rear front m 如圖所示 A 1 n n21 在循環(huán)隊(duì)列中 用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素 用隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置 因此 從隊(duì)頭指針front指向的后一個(gè)位置直到隊(duì)尾指針rear指向的位置之間所有的元素均為隊(duì)列中的元素 循環(huán)隊(duì)列主要有兩種基本操作 進(jìn)隊(duì)操作與出隊(duì)操作 每進(jìn)行一次進(jìn)隊(duì)操作 隊(duì)尾指針加一 當(dāng)隊(duì)尾指針rear n 1時(shí) 則置rear 1 每進(jìn)行一次出隊(duì)操作 隊(duì)頭指針就加一 當(dāng)隊(duì)頭指針front n 1時(shí) 則置front 1 為了能區(qū)分隊(duì)列滿還是隊(duì)列空 通常還需增加一個(gè)標(biāo)志s s值的定義如下 由此可以得出隊(duì)列空與隊(duì)列滿的條件如下 隊(duì)列空的條件為s 0 隊(duì)列滿的條件為s 1且front rear 5 4樹(shù)與二叉樹(shù) 5 4 1樹(shù)的基本概念樹(shù)是一種重要的非線性結(jié)構(gòu) 在這種數(shù)據(jù)結(jié)構(gòu)中 所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性 并以分支關(guān)系定義了層次結(jié)構(gòu) 下圖是一棵樹(shù)的例子 現(xiàn)實(shí)世界中有很多可以用樹(shù)來(lái)表示的例子 例如圖中的樹(shù)表示了高校中院系之間的關(guān)系 樹(shù)中每一個(gè)結(jié)點(diǎn)只有一個(gè)直接前驅(qū) 稱作父結(jié)點(diǎn) 沒(méi)有直接前驅(qū)的結(jié)點(diǎn)只有一個(gè) 稱作樹(shù)的根結(jié)點(diǎn) 簡(jiǎn)稱為樹(shù)的根 例如 在上圖中 結(jié)點(diǎn)沈陽(yáng)工業(yè)大學(xué)是樹(shù)的根結(jié)點(diǎn) 每一個(gè)結(jié)點(diǎn)可以有多個(gè)直接后繼 它們都稱為該結(jié)點(diǎn)的子女 沒(méi)有直接后繼的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn) 如 圖中的結(jié)點(diǎn)理學(xué)院 數(shù)學(xué)教研室等 除樹(shù)根以外的其它結(jié)點(diǎn)被劃分為多個(gè)互不相交的有限集合 每個(gè)集合又是一棵樹(shù) 被稱為根的子樹(shù) 結(jié)點(diǎn)所擁有的子樹(shù)的棵樹(shù)被稱為該結(jié)點(diǎn)的度 如上圖中沈陽(yáng)工業(yè)大學(xué)根節(jié)點(diǎn)的度是4 理學(xué)院的度是2 樹(shù)中所有結(jié)點(diǎn)的度的最大值稱為樹(shù)的度 例如 圖中所示的樹(shù)的度為4 用樹(shù)來(lái)表示算術(shù)表達(dá)式的原則如下 1 算術(shù)表達(dá)式中的每一個(gè)運(yùn)算符對(duì)應(yīng)于樹(shù)中的一個(gè)結(jié)點(diǎn) 2 運(yùn)算符的任一運(yùn)算對(duì)象皆為該運(yùn)算符結(jié)點(diǎn)的子樹(shù) 3 運(yùn)算對(duì)象中的單個(gè)變量均為葉子結(jié)點(diǎn) 下圖是用樹(shù)結(jié)構(gòu)對(duì)表達(dá)式a b c d x y z e的表示 注意 表示一個(gè)表達(dá)式的表達(dá)式樹(shù)可能并不唯一 5 4 2二叉樹(shù)及其基本性質(zhì) 1 什么是二叉樹(shù)二叉樹(shù)是另一種樹(shù)型結(jié)構(gòu) 當(dāng)然二叉樹(shù)也是一種非線性結(jié)構(gòu) 它的特點(diǎn)是 1 非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn) 2 每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù) 順序不能顛倒 分別稱為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù) 可見(jiàn)在二叉樹(shù)中 不存在度大于2的結(jié)點(diǎn) 從而所有子樹(shù)也均為二叉樹(shù) 另外 在二叉樹(shù)中 一個(gè)結(jié)點(diǎn)可以只有左子樹(shù)而沒(méi)有右子樹(shù) 也可以只有右子樹(shù)而沒(méi)有左子樹(shù) 當(dāng)一個(gè)結(jié)點(diǎn)既沒(méi)有左子樹(shù)也沒(méi)有右子樹(shù)時(shí) 該結(jié)點(diǎn)即是葉子結(jié)點(diǎn) 下圖是一棵深度為3的二叉樹(shù) 2 二叉樹(shù)的基本性質(zhì)性質(zhì)1在二叉樹(shù)的第i層上 最多有 i 1 個(gè)結(jié)點(diǎn) 性質(zhì)2深度為m的二叉樹(shù)最多有 1個(gè)結(jié)點(diǎn) 性質(zhì)3在任意一棵二叉樹(shù)中 度為0的結(jié)點(diǎn) 即葉子結(jié)點(diǎn) 總是比度為2的結(jié)點(diǎn)多一個(gè) 性質(zhì)4具有n個(gè)結(jié)點(diǎn)的二叉樹(shù) 其深度至少為 log2n 1 其中 log2n 表示取log2n的整數(shù)部分 2i 1 2m 3 滿二叉樹(shù)與完全二叉樹(shù)滿二叉樹(shù)與完全二叉樹(shù)是兩種特殊形態(tài)的二叉樹(shù) 1 滿二叉樹(shù)滿二叉樹(shù)是一棵深度為m且有 1個(gè)結(jié)點(diǎn)的二叉樹(shù) 該二叉樹(shù)每一層上的所有結(jié)點(diǎn)數(shù)都達(dá)到最大值 2m 2 完全二叉樹(shù)完全二叉樹(shù)除最后一層外 每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值 在最后一層上只缺少右邊的若干結(jié)點(diǎn) 稱之為完全二叉樹(shù) 由滿二叉樹(shù)與完全二叉樹(shù)的特點(diǎn)可以看出 滿二叉樹(shù)也是完全二叉樹(shù) 而完全二叉樹(shù)一般不是滿二叉樹(shù) 5 4 3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 在計(jì)算機(jī)中 二叉樹(shù)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 用于存儲(chǔ)二叉樹(shù)中各元素的存儲(chǔ)結(jié)點(diǎn)由兩部分組成 數(shù)據(jù)域與指針域 但在二叉樹(shù)中 由于每一個(gè)元素可以有兩個(gè)子結(jié)點(diǎn) 因此 用于存儲(chǔ)二叉樹(shù)的存儲(chǔ)結(jié)點(diǎn)的指針域有兩個(gè) 一個(gè)用于指向該結(jié)點(diǎn)的左子結(jié)點(diǎn) 稱左指針域 另一個(gè)用于指向該結(jié)點(diǎn)的右子結(jié)點(diǎn) 稱為右指針域 由于二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)中每一個(gè)存儲(chǔ)結(jié)點(diǎn)有兩個(gè)指針域 因此 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也稱為二叉樹(shù)鏈表 5 4 4二叉樹(shù)的遍歷 二叉樹(shù)的遍歷 是指不重復(fù)地訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn) 在遍歷二叉樹(shù)的過(guò)程中 一般先遍歷左子樹(shù) 然后再遍歷右子樹(shù) 在先左后右的原則下 根據(jù)訪問(wèn)根結(jié)點(diǎn)的次序 二叉樹(shù)的遍歷可以分為三種 前序遍歷 中序遍歷 后序遍歷 1 前序遍歷所謂前序遍歷是指首先訪問(wèn)根結(jié)點(diǎn) 然后遍歷左子樹(shù) 最后遍歷右子樹(shù) 并且 在遍歷左 右子樹(shù)時(shí) 仍然先訪問(wèn)根結(jié)點(diǎn) 然后遍歷左子樹(shù) 最后遍歷右子樹(shù) 下面是二叉樹(shù)中序遍歷的簡(jiǎn)單描述 若二叉樹(shù)為空 則結(jié)束返回 否則 1 中序遍歷左子樹(shù) 2 訪問(wèn)根結(jié)點(diǎn) 3 中序遍歷右子樹(shù) 2 中序遍歷所謂中序遍歷是指首先遍歷左子樹(shù) 然后訪問(wèn)根結(jié)點(diǎn) 最后遍歷右子樹(shù) 并且 在遍歷左 右子樹(shù)時(shí) 仍然先遍歷左子樹(shù) 然后訪問(wèn)根結(jié)點(diǎn) 最后遍歷右子樹(shù) 下面是二叉樹(shù)中序遍歷的簡(jiǎn)單描述 若二叉樹(shù)為空 則結(jié)束返回 否則 1 中序遍歷左子樹(shù) 2 訪問(wèn)根結(jié)點(diǎn) 3 中序遍歷右子樹(shù) 3 后序遍歷所謂后序遍歷是指首先遍歷左子樹(shù) 然后遍歷右子樹(shù) 最后訪問(wèn)根結(jié)點(diǎn) 并且 在遍歷左 右子樹(shù)時(shí) 仍然先遍歷左子樹(shù) 然后遍歷右子樹(shù) 最后訪問(wèn)根結(jié)點(diǎn) 下面是二叉樹(shù)后序遍歷的簡(jiǎn)單描述 若二叉樹(shù)為空 則結(jié)束返回 否則 1 后序遍歷左子樹(shù) 2 后序遍歷右子樹(shù) 3 訪問(wèn)根結(jié)點(diǎn) 5 5查找和排序技術(shù) 5 5 1查找技術(shù)1 順序查找順序查找的基本方法是 從線性表的第一個(gè)元素開(kāi)始 逐個(gè)將線性表中的元素與被查元素進(jìn)行比較 若相等則表示找到 即查找成功 若線性表中所有的元素都與被查元素進(jìn)行了比較但都不相等 則表示線性表中沒(méi)有要找的元素 即查找失敗 雖然順序查找的效率不高 但在下列兩種情況下只能采用順序查找 1 如果線性表為無(wú)序表 則只能用順序查找 2 采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的有序線性表 只能采用順序查找 2 折半查找折半查找只適用于順序存儲(chǔ)的有序表 也就是說(shuō) 線性表中的元素已經(jīng)按值非遞減排列 假設(shè)有序線性表的長(zhǎng)度為m 被查元素值為x 則折半查找的方法如下 將x與線性表的中間項(xiàng)的元素值進(jìn)行比較 若中間項(xiàng)的值等于x 則查找成功 結(jié)束返回 若x小于中間項(xiàng)的值 則在線性表的前半部分用相同的方法進(jìn)行查找 若x大于中間項(xiàng)的值 則在線性表的后半部分用相同的方法進(jìn)行查找 這個(gè)過(guò)程一直進(jìn)行到查找成功或線性表中沒(méi)有這個(gè)元素為止 5 5 2排序技術(shù) 1 插入排序所謂插入排序 是指將無(wú)序序列中的各元素依次插入到已經(jīng)有序的線性表中 1 簡(jiǎn)單插入排序簡(jiǎn)單插入排序的基本思想是 將一個(gè)新元素插入到已經(jīng)排好序的有序序列中 從而元素的個(gè)數(shù)增一 并成為新的有序序列 在簡(jiǎn)單插入排序過(guò)程中 由于每一次比較后最多去掉一個(gè)逆序 因此 這種排序方法的效率在最壞情況下 需要n n 1 2次比較 2 希爾排序希爾排序的基本思想是 將整個(gè)初始序列分割成若干個(gè)子序列 對(duì)每個(gè)子序列分別進(jìn)行簡(jiǎn)單插入排序 最后再對(duì)全體元素進(jìn)行一次簡(jiǎn)單插入排序 由此可見(jiàn) 希爾排序也是一種插入排序方法 2 交換排序所謂交換排序是指借助數(shù)據(jù)元素之間的互相交換進(jìn)行排序的一種方法 冒泡排序法與快速排序法都屬于交換類的排序方法 1 冒泡排序冒泡排序的過(guò)程簡(jiǎn)單 它的基本思想是通過(guò)對(duì)相鄰元素進(jìn)行比較 并根據(jù)比較的結(jié)果交換位置 從而逐步由任意序列變?yōu)橛行蛐蛄?具體過(guò)程是 首先 將第一個(gè)元素和第二元素進(jìn)行比較 若為逆序 則交換之 接下來(lái)對(duì)第二個(gè)元素和第三個(gè)元素進(jìn)行同樣的操作 并依次類推 直到倒數(shù)第二個(gè)元素和最后一個(gè)元素為止 其結(jié)果是將最大的元素交換到了整個(gè)序列的尾部 這個(gè)過(guò)程叫做第一趟冒泡排序 而第二趟冒泡排序是在除去這個(gè)最大元素的子序列中從第一個(gè)元素起重復(fù)上述過(guò)程 直到整個(gè)序列變?yōu)橛行驗(yàn)橹?排序過(guò)程中 小元素好比水中氣泡逐漸上浮 而大元素好比大石頭逐漸下沉 冒泡排序故此得名 假設(shè)初始序列的長(zhǎng)度為n 冒泡排序需要經(jīng)過(guò)n 1趟排序 需要的比較次數(shù)為n n 1 2 下圖是冒泡排序的示意圖 初始序列第一趟排序后第二趟排序后第三趟排序后第四趟排序后第五趟排序后2618181818918262626915323232915185447915264791532915471554 2 快速排序快速排序法就是一種可以通過(guò)一次交換而消除多個(gè)逆序的排序方法 其基本思想如下 任取待排序序列中的某個(gè)元素對(duì)象作為基準(zhǔn) 按照該元素值的大小 將整個(gè)序列劃分為左右兩個(gè)子序列 這個(gè)過(guò)程稱為分割 左側(cè)子序列中所有元素的值都小于或等于基準(zhǔn)對(duì)象元素的值 右側(cè)子序列中所有元素的值都大于基準(zhǔn)對(duì)象元素的值 基準(zhǔn)對(duì)象元素則排在這兩個(gè)子序列中間 這也是該對(duì)象最終應(yīng)該被安放的位置 接下來(lái)分別對(duì)這兩個(gè)子序列重復(fù)進(jìn)行上述過(guò)程 直到所有的對(duì)象都排在相應(yīng)位置上為止 3 選擇排序選擇排序的基本思想是 每一趟排序過(guò)程都是在當(dāng)前位置后面剩下的待排序?qū)ο笾羞x出元素值最小的對(duì)象 放到當(dāng)前的位置上 1 簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序的基本步驟是 1 在一組對(duì)象S i S n 1 中選擇元素值最小的對(duì)象 2 若它不是這組對(duì)象中的第一個(gè)對(duì)象 則將它與這組對(duì)象中的第一個(gè)對(duì)象對(duì)調(diào) 3 在剩下的對(duì)象中重復(fù)執(zhí)行上述兩步 直到只剩下一個(gè)對(duì)象為止 下圖是這種排序法的示意圖 圖中有方框的元素是剛被選出來(lái)的最小元素 2 堆排序堆排序法屬于選擇類的排序方法 堆的定義如下 具有n個(gè)元素的序列 a1 a2 an 當(dāng)且僅當(dāng)滿足 i 1 2 n 2 時(shí)稱之為堆 根據(jù)堆的定義和堆的調(diào)整過(guò)程 可以得到堆排序的方法如下 1 首先將一個(gè)無(wú)序序列建成堆 2 然后將堆頂元素與堆中最后一個(gè)元素交換 并將除了已經(jīng)換到最后的那個(gè)元素之外的其它元素重新調(diào)整為堆 反復(fù)做第 2 步 直到所有的元素都完成交換為止 從而得到一個(gè)有序序列 堆排序的方法對(duì)于規(guī)模較小的線性表并不合適 但對(duì)于較大規(guī)模的線性表來(lái)說(shuō)是很有效的