數據結構課件圖片2024/3/261數據結構概述線性表棧和隊列樹和二叉樹圖論基礎查找與排序算法文件組織與索引技術動態規劃思想在數據結構中的應用contents目錄2024/3/26201數據結構概述2024/3/263數據結構是計算機中存儲、組織數據的方式，它定義了數據元素之間的邏輯關系以及如何在計算機中表示這些關系。數據結構的定義根據數據元素之間關系的不同，數據結構可分為線性結構、樹形結構、圖形結構等。數據結構的分類數據結構定義與分類2024/3/264數據結構是計算機科學的基礎，它直接影響程序的效率、可維護性和可擴展性。掌握數據結構對于編寫高質量代碼和解決實際問題具有重要意義。數據結構廣泛應用于各種計算機程序和應用中，如操作系統、編譯器、數據庫系統、人工智能、機器學習等。數據結構重要性及應用領域數據結構的應用領域數據結構的重要性2024/3/265算法與數據結構的聯系算法是解決特定問題的步驟和方法，而數據結構是算法的基礎。算法的設計和實現依賴于數據結構的選擇和使用。算法與數據結構的區別算法關注問題的解決方案和步驟，而數據結構關注數據的組織和存儲方式。算法可以獨立于數據結構存在，但數據結構的選擇會直接影響算法的效率。算法與數據結構關系2024/3/26602線性表2024/3/26703線性表的抽象數據類型描述定義線性表的抽象數據類型，包括數據對象集、數據關系和基本操作集。01線性表的定義線性表是具有n個元素的有限序列。02線性表的基本操作包括創建、插入、刪除、查找、遍歷等。線性表定義及基本操作2024/3/268順序存儲結構01用一段地址連續的存儲單元依次存儲線性表的數據元素。鏈式存儲結構02用一組任意的存儲單元存儲線性表的數據元素，這組存儲單元可以是連續的，也可以是不連續的。比較03順序存儲結構可以隨機存取，而鏈式存儲結構只能順序存取；順序存儲結構需要預分配存儲空間，而鏈式存儲結構不需要預分配存儲空間，可以動態申請和釋放。順序存儲結構與鏈式存儲結構比較2024/3/269使用線性表表示多項式，每個元素表示多項式的一個項，包括系數和指數。多項式的相加可以通過合并兩個線性表實現。多項式的表示與相加使用線性表管理圖書借閱信息，每個元素表示一本書的借閱記錄，包括書名、借閱人、借閱時間等。可以實現借閱、歸還、查詢等操作。圖書借閱管理使用線性表管理學生成績信息，每個元素表示一個學生的成績記錄，包括學號、姓名、各科成績等。可以實現成績的錄入、修改、查詢、排序等操作。學生成績管理線性表應用舉例2024/3/261003棧和隊列2024/3/26110102棧的定義棧（Stack）是一種特殊的線性數據結構，其操作只能在一端進行，遵循后進先出（LIFO,LastInFirstOut）的原則。入棧（Push）在棧頂插入一個元素。出棧（Pop）刪除棧頂元素并返回其值。查看棧頂（Peek/T…返回棧頂元素的值，但不刪除該元素。判斷棧是否為空（IsE…檢查棧中是否還有元素。030405棧定義及基本操作2024/3/2612隊列的定義查看隊頭（Front）查看隊尾（Rear）判斷隊列是否為空（IsEmpty）出隊（Dequeue）入隊（Enqueue）隊列（Queue）也是一種特殊的線性數據結構，其操作在兩端進行，遵循先進先出（FIFO,FirstInFirstOut）的原則。在隊列的末尾插入一個元素。刪除隊列頭部的元素并返回其值。返回隊列頭部的元素值，但不刪除該元素。返回隊列尾部的元素值，但不刪除該元素。檢查隊列中是否還有元素。隊列定義及基本操作2024/3/2613利用棧可以方便地處理算術表達式中的括號和運算符優先級問題。表達式求值在程序執行過程中，函數調用會形成一個調用棧，用于保存函數調用的上下文信息。函數調用棧和隊列應用舉例2024/3/2614瀏覽器的前進后退功能：通過維護兩個棧，分別記錄用戶瀏覽過的頁面，實現瀏覽器的前進和后退功能。棧和隊列應用舉例2024/3/2615

棧和隊列應用舉例打印任務管理打印機使用隊列來管理多個打印任務，按照先進先出的原則依次處理任務。CPU任務調度操作系統使用隊列來管理待執行的進程或線程，根據一定的調度算法從隊列中選擇任務執行。網絡數據傳輸在網絡通信中，發送方將數據包放入發送隊列，接收方從接收隊列中取出數據包進行處理，保證了數據傳輸的順序性和可靠性。2024/3/261604樹和二叉樹2024/3/2617當n>1時，其余結點可分為m（m>0）個互不相交的有限集T1、T2、…、Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹（SubTree）。樹（Tree）是n（n≥0）個結點的有限集。n=0時稱為空樹。在任意一棵非空樹中有且僅有一個特定的稱為根（Root）的結點。樹定義及基本術語2024/3/2618父結點每一個結點最多有一個前件，稱為該結點的父結點（或雙親）。子結點每一個結點可以有多個后件，稱為該結點的子結點。樹定義及基本術語2024/3/2619具有相同父結點的結點互稱為兄弟結點。兄弟結點沒有子結點的結點稱為葉子結點。葉子結點一個結點擁有的子樹數稱為該結點的度。度樹定義及基本術語2024/3/2620一棵樹中，最大的結點的度稱為樹的度。樹的度從根開始定義起，根為第1層，根的子結點為第2層，以此類推。結點的層次樹中結點的最大層次。樹的高度或深度如果將樹中結點的各子樹看成從左至右是有次序的，不能互換的，則稱該樹為有序樹，否則稱為無序樹。有序樹和無序樹樹定義及基本術語2024/3/2621二叉樹的性質在二叉樹的第i層上至多有2^(i-1)個結點（i≥1）。深度為k的二叉樹至多有2^k-1個結點（k≥1）。二叉樹性質與遍歷方法2024/3/2622對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0=n2+1。二叉樹性質與遍歷方法2024/3/2623前序遍歷若二叉樹為空，則空操作返回，否則先訪問根結點，然后前序遍歷左子樹，再前序遍歷右子樹。中序遍歷若二叉樹為空，則空操作返回，否則從根結點開始（注意并不是先訪問根結點），中序遍歷根結點的左子樹，然后訪問根結點，最后中序遍歷右子樹。后序遍歷若二叉樹為空，則空操作返回，否則從左到右先葉子后結點的方式遍歷訪問左右子樹，最后是訪問根結點。二叉樹性質與遍歷方法2024/3/2624具體辦法是，把每個結點的孩子結點排列起來，以單鏈表作存儲結構，則n個結點有n個孩子鏈表，如果是葉子結點則此單鏈表為空。然后n個頭指針又組成一個線性表，采用順序存儲結構，存放進一個一維數組中。孩子表示法任意一棵樹，它的結點的第一個孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我們設置兩個指針，分別指向該結點的第一個孩子和此結點的右兄弟。孩子兄弟表示法樹的存儲結構及其實現2024/3/262505圖論基礎2024/3/2626圖論基本概念介紹圖（Graph）的定義由頂點（Vertex）和邊（Edge）組成的集合，表示對象及其之間的關系。有向圖和無向圖根據邊是否有方向，圖可分為有向圖和無向圖。頂點的度（Degree）與頂點相關聯的邊的數量，對于有向圖，可分為入度和出度。路徑（Path）和回路（Cycle）路徑是由一系列頂點和邊組成的序列，回路是起點和終點相同的路徑。2024/3/2627圖的存儲結構及其實現適用于有向圖，結合了鄰接矩陣和鄰接表的優點，可以高效地處理各種圖論問題。十字鏈表（CrossList）使用二維數組表示圖，數組元素表示頂點之間的連接關系。適用于稠密圖。鄰接矩陣（AdjacencyMatrix）使用鏈表或數組表示圖，每個頂點對應一個鏈表或數組，存儲與該頂點相鄰的頂點。適用于稀疏圖。鄰接表（AdjacencyList）2024/3/2628最短路徑算法Dijkstra算法：適用于沒有負權邊的有向圖或無向圖，通過貪心策略逐步找到起點到各頂點的最短路徑。Floyd算法：適用于任意有向圖或無向圖，通過動態規劃思想計算任意兩點之間的最短路徑。最小生成樹算法Prim算法：從某一頂點開始，每次選擇一條連接已選頂點和未選頂點中權值最小的邊，直至所有頂點都被選中。Kruskal算法：按照邊的權值從小到大的順序選擇邊，每次選擇一條連接兩個未連通集合的邊，直至所有頂點都在同一個連通集合中。最短路徑算法和最小生成樹算法2024/3/262906查找與排序算法2024/3/2630查找算法概述及分類在數據集合中尋找滿足某種條件的數據元素的過程。從數據集合的一端開始，順序掃描，直到找到所查元素為止。針對有序數據集合，每次與中間元素比較，縮小查找范圍。通過哈希函數將數據元素映射到哈希表中，實現快速查找。查找算法定義線性查找二分查找哈希查找2024/3/2631歸并排序采用分治策略，將待排序序列分成若干子序列，分別進行排序后再合并。交換排序通過比較和交換相鄰元素的位置，使得序列變得有序。選擇排序每次從未排序序列中選出最小（或最大）元素，放到已排序序列的末尾。排序算法定義將數據集合按照某種規則進行排序的過程。插入排序將待排序元素插入到已排序序列中的合適位置，達到排序目的。排序算法概述及分類2024/3/2632時間復雜度比較線性查找的時間復雜度為O(n)；二分查找的時間復雜度為O(logn)；常見查找與排序算法性能比較2024/3/2633哈希查找的時間復雜度接近O(1)；插入排序、選擇排序和冒泡排序的時間復雜度為O(n^2)；快速排序、歸并排序和堆排序的時間復雜度為O(nlogn)。常見查找與排序算法性能比較2024/3/2634空間復雜度比較線性查找、二分查找和哈希查找的空間復雜度通常為O(1)；插入排序、選擇排序和冒泡排序的空間復雜度為O(1)；常見查找與排序算法性能比較2024/3/2635快速排序的空間復雜度為O(logn)；歸并排序的空間復雜度為O(n)；堆排序的空間復雜度為O(1)。常見查找與排序算法性能比較2024/3/2636穩定性比較線性查找、二分查找和哈希查找不涉及穩定性問題；插入排序、冒泡排序和歸并排序是穩定的排序算法；選擇排序、快速排序和堆排序是不穩定的排序算法。01020304常見查找與排序算法性能比較2024/3/263707文件組織與索引技術2024/3/2638按照某種順序（如記錄的邏輯順序或物理順序）進行組織的文件。順序文件組織索引文件組織散列文件組織通過建立索引表來組織文件，索引表中包含指向文件記錄的指針。通過散列函數將記錄的關鍵字映射到散列表中，通過散列表進行文件的組織。030201文件組織方式簡介2024/3/2639將文件記錄按照某種順序排列，然后建立一個索引表，每個索引項指向一個記錄。線性索引采用樹形結構來組織索引，如B樹、B+樹等，可以快速定位到指定記錄。樹形索引當文件很大時，可以采用多級索引，即第一級索引指向第二級索引，第二級索引指向記錄。多級索引索引技術原理及實現方法2024/3/2640數據庫系統數據庫系統中大量采用索引技術來提高數據檢索速度，如關系型數據庫中的B樹索引、哈希索引等。搜索引擎搜索引擎中采用倒排索引技術來快速定位包含指定關鍵詞的文檔。大數據處理大數據處理中需要對海量數據進行高效處理，采用分布式文件系統（如HadoopHDFS）和分布式數據庫（如HBase）等技術，這些技術中大量采用了文件組織和索引技術。文件系統文件系統中采用文件組織方式來管理文件，如Windows系統中的FAT表、NTFS文件系統中的MFT表等。文件組織與索引技術應用場景2024/3/264108動態規劃思想在數據結構中的應用2024/3/2642最優子結構動態規劃要求子問題的解能夠推導出原問題的最優解，即子問題的最優解組合起來能夠得到原問題的最優解。分治策略動態規劃通過將問題分解為若干個子問題，并分別求解，最終合并子問題的解得到原問題的解。邊界與狀態轉移動態規劃需要明確問題的邊界條件和狀態轉移方程，以便通過迭代或遞歸的方式求解。動態規劃思想簡介2024/3/2643提高效率通過避免重復計算子問題的解，動態規劃可以顯著提高算法的效率。空間優化動態規劃通常使用一維或二維數組來存儲子問題的解，相對于暴力搜索等方法，可以顯著減少空間復雜度。適用性廣動態規劃可以應用于各種類型的問題，如背