(2024年)數(shù)據(jù)結(jié)構(gòu)課件圖片

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

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