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

數(shù)據(jù)結(jié)構(gòu)課件圖片2024/3/261數(shù)據(jù)結(jié)構(gòu)概述線(xiàn)性表?xiàng)：完?duì)列樹(shù)和二叉樹(shù)圖論基礎(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)可分為線(xiàn)性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖形結(jié)構(gòu)等。數(shù)據(jù)結(jié)構(gòu)的分類(lèi)數(shù)據(jù)結(jié)構(gòu)定義與分類(lèi)2024/3/264數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)的基礎(chǔ)，它直接影響程序的效率、可維護(hù)性和可擴(kuò)展性。掌握數(shù)據(jù)結(jié)構(gòu)對(duì)于編寫(xiě)高質(zhì)量代碼和解決實(shí)際問(wèn)題具有重要意義。數(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)系算法是解決特定問(wèn)題的步驟和方法，而數(shù)據(jù)結(jié)構(gòu)是算法的基礎(chǔ)。算法的設(shè)計(jì)和實(shí)現(xiàn)依賴(lài)于數(shù)據(jù)結(jié)構(gòu)的選擇和使用。算法與數(shù)據(jù)結(jié)構(gòu)的區(qū)別算法關(guān)注問(wè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線(xiàn)性表2024/3/26703線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型描述定義線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型，包括數(shù)據(jù)對(duì)象集、數(shù)據(jù)關(guān)系和基本操作集。01線(xiàn)性表的定義線(xiàn)性表是具有n個(gè)元素的有限序列。02線(xiàn)性表的基本操作包括創(chuàng)建、插入、刪除、查找、遍歷等。線(xiàn)性表定義及基本操作2024/3/268順序存儲(chǔ)結(jié)構(gòu)01用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線(xiàn)性表的數(shù)據(jù)元素。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)02用一組任意的存儲(chǔ)單元存儲(chǔ)線(xiàn)性表的數(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àn)性表表示多項(xiàng)式，每個(gè)元素表示多項(xiàng)式的一個(gè)項(xiàng)，包括系數(shù)和指數(shù)。多項(xiàng)式的相加可以通過(guò)合并兩個(gè)線(xiàn)性表實(shí)現(xiàn)。多項(xiàng)式的表示與相加使用線(xiàn)性表管理圖書(shū)借閱信息，每個(gè)元素表示一本書(shū)的借閱記錄，包括書(shū)名、借閱人、借閱時(shí)間等?？梢詫?shí)現(xiàn)借閱、歸還、查詢(xún)等操作。圖書(shū)借閱管理使用線(xiàn)性表管理學(xué)生成績(jī)信息，每個(gè)元素表示一個(gè)學(xué)生的成績(jī)記錄，包括學(xué)號(hào)、姓名、各科成績(jī)等?？梢詫?shí)現(xiàn)成績(jī)的錄入、修改、查詢(xún)、排序等操作。學(xué)生成績(jī)管理線(xiàn)性表應(yīng)用舉例2024/3/261003棧和隊(duì)列2024/3/26110102棧的定義棧（Stack）是一種特殊的線(xiàn)性數(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）也是一種特殊的線(xiàn)性數(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í)問(wèn)題。表達(dá)式求值在程序執(zhí)行過(guò)程中，函數(shù)調(diào)用會(huì)形成一個(gè)調(diào)用棧，用于保存函數(shù)調(diào)用的上下文信息。函數(shù)調(diào)用棧和隊(duì)列應(yīng)用舉例2024/3/2614瀏覽器的前進(jìn)后退功能：通過(guò)維護(hù)兩個(gè)棧，分別記錄用戶(hù)瀏覽過(guò)的頁(yè)面，實(shí)現(xiàn)瀏覽器的前進(jìn)和后退功能。棧和隊(duì)列應(yīng)用舉例2024/3/2615

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