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

《《算法與數(shù)據(jù)結(jié)構(gòu)》PPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》PPT課件.ppt（100頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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