數(shù)據(jù)結(jié)構(gòu)(c描述)電子教案第5章

數(shù)據(jù)結(jié)構(gòu)(c描述)電子教案第5章目錄緒論線性表棧與隊列串與數(shù)組樹與二叉樹圖論基礎(chǔ)查找技術(shù)排序技術(shù)01緒論數(shù)據(jù)元素數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進(jìn)行考慮和處理。數(shù)據(jù)對客觀事物的符號表示，在計算機科學(xué)中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。數(shù)據(jù)項數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)對象性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu)基本概念數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組操作的總稱。抽象數(shù)據(jù)類型（ADT）是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計算機內(nèi)部如何表示和實現(xiàn)無關(guān)。抽象數(shù)據(jù)類型表示算法算法的特性算法設(shè)計的要求算法分析算法和算法分析是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。正確性、可讀性、健壯性、效率與低存儲量需求。有窮性、確定性、可行性、輸入、輸出。時間復(fù)雜度、空間復(fù)雜度。02線性表線性表是由n（n>=0）個具有相同類型的數(shù)據(jù)元素（結(jié)點）a1，a2，...，an組成的有序序列，其中n為表長，當(dāng)n=0時該線性表是一個空表。線性表的基本操作包括創(chuàng)建、插入、刪除、查找、遍歷等。這些操作都可以通過相應(yīng)的算法來實現(xiàn)。線性表定義及基本操作基本操作線性表定義順序存儲結(jié)構(gòu)是用一段連續(xù)的存儲空間來存放線性表中的數(shù)據(jù)元素，邏輯上相鄰的元素在物理位置上也相鄰。存儲方式順序存儲結(jié)構(gòu)的優(yōu)點是存儲密度大、可以隨機存取；缺點是插入和刪除操作需要移動大量元素。優(yōu)缺點順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲空間來存放線性表中的數(shù)據(jù)元素，這組存儲空間可以是連續(xù)的，也可以是不連續(xù)的。數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。存儲方式鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)點是插入和刪除操作不需要移動元素，只需要修改指針；缺點是存儲密度小、不可以隨機存取。優(yōu)缺點鏈?zhǔn)酱鎯Y(jié)構(gòu)03棧與隊列棧的定義：棧（Stack）是一種特殊的線性數(shù)據(jù)結(jié)構(gòu)，其操作只能在一端進(jìn)行，遵循后進(jìn)先出（LIFO,LastInFirstOut）的原則。入棧（Push）：在棧頂插入一個元素。出棧（Pop）：刪除棧頂元素并返回其值。查看棧頂（Top）：返回棧頂元素的值，但不刪除。判斷棧空（Empty）：檢查棧是否為空。棧定義及基本操作隊列的定義：隊列（Queue）也是一種特殊的線性數(shù)據(jù)結(jié)構(gòu)，其操作在兩端進(jìn)行，遵循先進(jìn)先出（FIFO,FirstInFirstOut）的原則。入隊（Enqueue）：在隊尾插入一個元素。出隊（Dequeue）：刪除隊頭元素并返回其值。查看隊頭（Front）：返回隊頭元素的值，但不刪除。判斷隊空（Empty）：檢查隊列是否為空。0102030405隊列定義及基本操作表達(dá)式求值利用棧的后進(jìn)先出特性，可以方便地處理算術(shù)表達(dá)式中的括號和運算符。函數(shù)調(diào)用在程序執(zhí)行過程中，函數(shù)調(diào)用會形成一個調(diào)用棧，用于保存函數(shù)調(diào)用的上下文信息。棧與隊列應(yīng)用舉例瀏覽器前進(jìn)后退：瀏覽器歷史記錄可以用兩個棧來實現(xiàn)前進(jìn)和后退功能。棧與隊列應(yīng)用舉例打印機中的打印任務(wù)可以看作是一個隊列，按照先進(jìn)先出的原則進(jìn)行打印。打印任務(wù)管理CPU任務(wù)調(diào)度網(wǎng)絡(luò)數(shù)據(jù)傳輸操作系統(tǒng)中的CPU任務(wù)調(diào)度可以采用隊列結(jié)構(gòu)，按照任務(wù)的優(yōu)先級和時間順序進(jìn)行調(diào)度。在網(wǎng)絡(luò)通信中，數(shù)據(jù)的傳輸可以采用隊列結(jié)構(gòu)，確保數(shù)據(jù)按照發(fā)送順序進(jìn)行接收和處理。030201棧與隊列應(yīng)用舉例04串與數(shù)組串的定義01串（string）是由零個或多個字符組成的有限序列，又名叫字符串。串的基本操作02串的基本操作包括串的賦值、串的比較、串的連接、串的求長度、串的復(fù)制、串的清空等。串的存儲結(jié)構(gòu)03串的存儲結(jié)構(gòu)包括順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。其中，順序存儲結(jié)構(gòu)是用一組地址連續(xù)的存儲單元來存儲串中的字符序列；鏈?zhǔn)酱鎯Y(jié)構(gòu)則是用鏈表來存儲串中的字符序列。串定義及基本操作數(shù)組的定義數(shù)組（Array）是有序的元素序列。若將有限個類型相同的變量的集合命名，那么這個名稱為數(shù)組名。組成數(shù)組的各個變量稱為數(shù)組的分量，也稱為數(shù)組的元素，有時也稱為下標(biāo)變量。數(shù)組的基本操作數(shù)組的基本操作包括數(shù)組的創(chuàng)建、數(shù)組的初始化、數(shù)組的訪問、數(shù)組的遍歷、數(shù)組的排序等。數(shù)組的存儲結(jié)構(gòu)數(shù)組的存儲結(jié)構(gòu)通常采用順序存儲結(jié)構(gòu)，即使用一塊連續(xù)的存儲空間來存放數(shù)組的所有元素。數(shù)組定義及基本操作特殊矩陣是指具有特殊形狀或特殊性質(zhì)的矩陣，如對稱矩陣、三角矩陣、稀疏矩陣等。特殊矩陣的定義對于特殊矩陣，可以采用壓縮存儲方法來節(jié)省存儲空間。常見的壓縮存儲方法包括對稱矩陣的壓縮存儲、三角矩陣的壓縮存儲和稀疏矩陣的壓縮存儲等。其中，稀疏矩陣的壓縮存儲通常采用三元組表示法或十字鏈表表示法。特殊矩陣的壓縮存儲方法特殊矩陣壓縮存儲方法05樹與二叉樹樹是一種非線性數(shù)據(jù)結(jié)構(gòu)，由節(jié)點和邊組成，具有層次結(jié)構(gòu)。樹定義根節(jié)點、子節(jié)點、父節(jié)點、葉子節(jié)點、節(jié)點的度、樹的度、深度、高度等。樹的基本術(shù)語樹中任意兩個節(jié)點之間有且僅有一條路徑；樹中無環(huán)；除根節(jié)點外，每個節(jié)點有且僅有一個父節(jié)點。樹的性質(zhì)樹基本概念和性質(zhì)二叉樹定義和性質(zhì)二叉樹定義二叉樹是一種特殊的樹，每個節(jié)點最多有兩個子節(jié)點，分別稱為左子節(jié)點和右子節(jié)點。二叉樹的性質(zhì)二叉樹中每個節(jié)點的度最大為2；二叉樹是有序的，即左子樹和右子樹是有區(qū)別的；滿二叉樹和完全二叉樹是二叉樹的兩種特殊形態(tài)。二叉樹遍歷算法設(shè)計先訪問根節(jié)點，然后遍歷左子樹，最后遍歷右子樹。先遍歷左子樹，然后訪問根節(jié)點，最后遍歷右子樹。先遍歷左子樹，然后遍歷右子樹，最后訪問根節(jié)點。按照樹的層次自上而下、自左至右遍歷每個節(jié)點。先序遍歷中序遍歷后序遍歷層次遍歷06圖論基礎(chǔ)圖是由頂點集和邊集構(gòu)成的數(shù)據(jù)結(jié)構(gòu)，表示對象及其之間的關(guān)系。圖的基本概念連通性、有向性、無向性、稀疏性、稠密性等。圖的性質(zhì)鄰接矩陣、鄰接表、邊集數(shù)組等。圖的表示方法圖論基本概念和性質(zhì)

最小生成樹算法設(shè)計最小生成樹定義一個連通圖的最小生成樹是包含圖中所有頂點的極小連通子圖，且其所有邊的權(quán)值之和最小。普里姆算法從某一頂點開始，每次選擇一條與已選擇頂點集合相連且權(quán)值最小的邊，直到所有頂點都加入生成樹中?？唆斔箍査惴看芜x擇一條權(quán)值最小的邊，若這條邊不會與已選擇的邊構(gòu)成回路，則將其加入生成樹中，直到生成樹包含所有頂點。迪杰斯特拉算法適用于沒有負(fù)權(quán)邊的有向圖，通過逐步確定起點到各頂點的最短路徑，直到到達(dá)終點。最短路徑問題定義給定一個帶權(quán)有向圖和無向圖，找到從起點到終點的最短路徑。弗洛伊德算法適用于帶負(fù)權(quán)邊的有向圖和無向圖，通過動態(tài)規(guī)劃思想求解任意兩點間的最短路徑。最短路徑算法設(shè)計07查找技術(shù)順序查找法的適用情況適用于線性表等數(shù)據(jù)結(jié)構(gòu)，當(dāng)數(shù)據(jù)量不大時，查找效率較高。順序查找法的實現(xiàn)方法通過循環(huán)遍歷數(shù)據(jù)元素，逐個比較，直到找到目標(biāo)元素或遍歷結(jié)束。順序查找法的基本思想從數(shù)據(jù)結(jié)構(gòu)的一端開始，順序掃描，直到找到所查元素為止。順序查找法折半查找法的基本思想將已排序的數(shù)據(jù)結(jié)構(gòu)分成大致相等的兩部分，取中間元素與目標(biāo)元素比較，若相等則查找成功；若目標(biāo)元素小于中間元素，則在左半部分繼續(xù)折半查找；若目標(biāo)元素大于中間元素，則在右半部分繼續(xù)折半查找。折半查找法的適用情況適用于已排序的線性表等數(shù)據(jù)結(jié)構(gòu)，當(dāng)數(shù)據(jù)量較大時，查找效率較高。折半查找法的實現(xiàn)方法通過遞歸或循環(huán)實現(xiàn)折半查找過程，每次比較中間元素與目標(biāo)元素的大小關(guān)系，縮小查找范圍。折半查找法通過哈希函數(shù)將數(shù)據(jù)元素的關(guān)鍵字映射為哈希表中的地址，然后根據(jù)地址直接訪問哈希表中的元素。哈希表查找法的基本思想適用于關(guān)鍵字集合較大且關(guān)鍵字之間無明顯規(guī)律的數(shù)據(jù)結(jié)構(gòu)，當(dāng)數(shù)據(jù)量較大時，查找效率較高。哈希表查找法的適用情況設(shè)計合適的哈希函數(shù)和處理沖突的方法，將關(guān)鍵字映射到哈希表中，然后通過哈希函數(shù)計算出的地址直接訪問哈希表中的元素。哈希表查找法的實現(xiàn)方法哈希表查找法08排序技術(shù)將待排序的元素插入到已排序的序列中，從而達(dá)到排序的目的。從第一個元素開始，認(rèn)為該元素已經(jīng)被排序；取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描；如果該元素（已排序）大于新元素，將該元素移到下一位置；重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；將新元素插入到該位置后；重復(fù)步驟2~5。最好情況下為O(n)，最壞情況下為O(n^2)，平均情況下為O(n^2)。插入排序法的基本思想插入排序法的具體步驟插入排序法的時間復(fù)雜度插入排序法要點三選擇排序法的基本思想在未排序的序列中找到最小（或最大）的元素，將其放到排序序列的起始位置，然后再從剩余未排序的元素中繼續(xù)尋找最?。ɑ蜃畲螅┑脑兀诺揭雅判蛐蛄械哪┪?，如此反復(fù)，直到所有元素均排序完畢。要點一要點二選擇排序法的具體步驟首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?；再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾；重復(fù)第二步，直到所有元素均排序完畢。選擇排序法的時間復(fù)雜度無論最好、最壞還是平均情況，時間復(fù)雜度均為O(n^2)。要點三選擇排序法交換排序法的基本思想：通過不斷地交換相鄰的兩個元素（如果它們的順序錯誤）來把最小的元素交換到序列的最前端，然后再把次小的元素交換到序列的第二位置，以此類推，直到整個序列都排好序為止。交換排序法的具體步驟：從第一個