緒論(數(shù)據(jù)結(jié)構(gòu)教程課件)

緒論(數(shù)據(jù)結(jié)構(gòu)教程ppt課件)目錄數(shù)據(jù)結(jié)構(gòu)基本概念線性表?xiàng)：完?duì)列串、數(shù)組和廣義表樹(shù)和二叉樹(shù)圖論基礎(chǔ)與圖數(shù)據(jù)結(jié)構(gòu)01數(shù)據(jù)結(jié)構(gòu)基本概念數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)的定義根據(jù)數(shù)據(jù)元素間關(guān)系的不同，數(shù)據(jù)結(jié)構(gòu)可分為線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖形結(jié)構(gòu)等。數(shù)據(jù)結(jié)構(gòu)的分類數(shù)據(jù)結(jié)構(gòu)定義與分類數(shù)據(jù)類型數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無(wú)關(guān)。數(shù)據(jù)類型與抽象數(shù)據(jù)類型算法的定義算法的特性算法設(shè)計(jì)的要求算法分析算法與算法分析01020304算法是一系列解決問(wèn)題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問(wèn)題的策略機(jī)制。有窮性、確定性、可行性、輸入、輸出。正確性、可讀性、健壯性、效率與低存儲(chǔ)量需求。算法分析是對(duì)一個(gè)算法需要多少計(jì)算時(shí)間和存儲(chǔ)空間作定量的分析。02線性表123線性表是具有n個(gè)數(shù)據(jù)元素的有限序列線性表的定義創(chuàng)建、初始化、銷毀、判空、清空、求長(zhǎng)度、獲取元素、修改元素、插入元素、刪除元素等線性表的基本操作數(shù)據(jù)類型名稱、數(shù)據(jù)對(duì)象集合、操作集合等線性表的抽象數(shù)據(jù)類型描述線性表定義及基本操作順序存儲(chǔ)結(jié)構(gòu)的定義01用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素順序存儲(chǔ)結(jié)構(gòu)的基本操作實(shí)現(xiàn)02創(chuàng)建、初始化、銷毀、判空、清空、求長(zhǎng)度、獲取元素、修改元素等操作的實(shí)現(xiàn)方法順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)03無(wú)需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間；可以快速地存取表中任一位置的元素；插入和刪除操作需要移動(dòng)大量元素線性表順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的定義用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的基本操作實(shí)現(xiàn)創(chuàng)建、初始化、銷毀、判空、清空、求長(zhǎng)度、獲取元素、修改元素等操作的實(shí)現(xiàn)方法鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)比順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度?。绘湵碇械脑卦趦?nèi)存中不是順序存儲(chǔ)的，而是通過(guò)存在元素中的指針鏈接在一起；插入和刪除操作只需修改指針，不需要移動(dòng)大量元素線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)03棧和隊(duì)列棧（Stack）是一種特殊的線性數(shù)據(jù)結(jié)構(gòu)，其操作只能在表的一端進(jìn)行，通常稱為棧頂（top）。另一端稱為棧底（bottom）。棧的基本操作包括入棧（push）：在棧頂插入一個(gè)元素。出棧（pop）：刪除棧頂元素并返回其值。查看棧頂（peek/top）：返回棧頂元素的值，但不刪除它。判斷棧是否為空（isEmpty）：檢查棧中是否還有元素。棧定義及基本操作使用棧來(lái)輔助計(jì)算后綴表達(dá)式或中綴表達(dá)式的值。表達(dá)式求值括號(hào)匹配函數(shù)調(diào)用檢查一個(gè)包含括號(hào)（圓括號(hào)、方括號(hào)、花括號(hào)等）的表達(dá)式中的括號(hào)是否正確匹配。在程序執(zhí)行過(guò)程中，使用棧來(lái)保存函數(shù)調(diào)用的信息，如函數(shù)參數(shù)、局部變量和返回地址等。030201棧應(yīng)用舉例010405060302隊(duì)列（Queue）是一種特殊的線性數(shù)據(jù)結(jié)構(gòu)，其操作在表的兩端進(jìn)行。一端稱為隊(duì)頭（front），另一端稱為隊(duì)尾（rear）。隊(duì)列的基本操作包括入隊(duì)（enqueue）：在隊(duì)尾插入一個(gè)元素。出隊(duì)（dequeue）：刪除隊(duì)頭元素并返回其值。查看隊(duì)頭（peek/front）：返回隊(duì)頭元素的值，但不刪除它。判斷隊(duì)列是否為空（isEmpty）：檢查隊(duì)列中是否還有元素。隊(duì)列定義及基本操作使用隊(duì)列來(lái)管理待打印的文件，按照先進(jìn)先出（FIFO）的原則進(jìn)行打印。打印任務(wù)調(diào)度在操作系統(tǒng)中，使用隊(duì)列來(lái)管理等待CPU處理的進(jìn)程或線程，根據(jù)特定的調(diào)度算法進(jìn)行任務(wù)分配。CPU任務(wù)調(diào)度在網(wǎng)絡(luò)傳輸或文件讀寫(xiě)過(guò)程中，使用隊(duì)列作為緩沖區(qū)，暫時(shí)存儲(chǔ)待處理的數(shù)據(jù)，以提高處理效率。緩沖處理隊(duì)列應(yīng)用舉例04串、數(shù)組和廣義表串的基本操作包括賦值操作、連接操作、求串長(zhǎng)、比較操作、定位操作等。串的存儲(chǔ)結(jié)構(gòu)包括順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。串定義及基本操作串模式匹配算法是指在一個(gè)主串中尋找一個(gè)子串（模式串）的位置。常見(jiàn)的串模式匹配算法有：樸素模式匹配算法（Brute-Force算法）、KMP算法（Knuth-Morris-Pratt算法）、BM算法（Boyer-Moore算法）等。這些算法的時(shí)間復(fù)雜度不同，其中KMP算法和BM算法是較為高效的算法。串模式匹配算法數(shù)組（Array）是一種線性表數(shù)據(jù)結(jié)構(gòu)，它用一組連續(xù)的內(nèi)存空間來(lái)存儲(chǔ)一組具有相同類型的數(shù)據(jù)元素。數(shù)組的基本操作包括：存取元素、插入元素、刪除元素等。數(shù)組的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)，可以通過(guò)下標(biāo)直接訪問(wèn)數(shù)組中的元素。數(shù)組定義及基本操作

特殊矩陣壓縮存儲(chǔ)方法特殊矩陣是指具有特殊性質(zhì)或特殊形狀的矩陣，如對(duì)稱矩陣、三角矩陣、稀疏矩陣等。對(duì)于這些特殊矩陣，可以采用壓縮存儲(chǔ)方法來(lái)節(jié)省存儲(chǔ)空間和提高運(yùn)算效率。常見(jiàn)的特殊矩陣壓縮存儲(chǔ)方法有：對(duì)稱矩陣的壓縮存儲(chǔ)、三角矩陣的壓縮存儲(chǔ)、稀疏矩陣的壓縮存儲(chǔ)等。廣義表（GeneralizedList）是線性表的擴(kuò)展，它允許列表中的元素不僅可以是原子類型，還可以是另一個(gè)廣義表。廣義表的基本操作包括：創(chuàng)建廣義表、訪問(wèn)廣義表元素、修改廣義表元素、插入元素、刪除元素等。廣義表的存儲(chǔ)結(jié)構(gòu)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，每個(gè)元素可以用一個(gè)結(jié)點(diǎn)來(lái)表示，結(jié)點(diǎn)中包含元素值和指向下一個(gè)結(jié)點(diǎn)的指針。廣義表定義及基本操作05樹(shù)和二叉樹(shù)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m（m>0）個(gè)互不相交的有限集T1、T2、…、Tm，其中每一個(gè)集合本身又是一棵樹(shù)，并且稱為根的子樹(shù)（SubTree）。樹(shù)（Tree）是n（n≥0）個(gè)結(jié)點(diǎn)的有限集。n=0時(shí)稱為空樹(shù)。在任意一棵非空樹(shù)中有且僅有一個(gè)特定的稱為根（Root）的結(jié)點(diǎn)。樹(shù)定義及基本術(shù)語(yǔ)表示樹(shù)中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹(shù)的分支。結(jié)點(diǎn)（Node）結(jié)點(diǎn)擁有的子樹(shù)數(shù)。結(jié)點(diǎn)的度（Degree）樹(shù)定義及基本術(shù)語(yǔ)03樹(shù)的度樹(shù)內(nèi)各結(jié)點(diǎn)的度的最大值。01葉子（Leaf）或終端結(jié)點(diǎn)度為0的結(jié)點(diǎn)。02非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)度不為0的結(jié)點(diǎn)。樹(shù)定義及基本術(shù)語(yǔ)從根開(kāi)始定義起，根為第1層，根的子結(jié)點(diǎn)為第2層，以此類推。結(jié)點(diǎn)的層次（Level）樹(shù)中結(jié)點(diǎn)的最大層次。樹(shù)的深度或高度雙親在同一層的結(jié)點(diǎn)。堂兄弟結(jié)點(diǎn)如果將樹(shù)中結(jié)點(diǎn)的各子樹(shù)看成從左至右是有次序的，不能互換的，則稱該樹(shù)為有序樹(shù)，否則稱為無(wú)序樹(shù)。有序樹(shù)和無(wú)序樹(shù)樹(shù)定義及基本術(shù)語(yǔ)二叉樹(shù)（BinaryTree）是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集（稱為空二叉樹(shù)），或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。二叉樹(shù)的五種基本形態(tài)：空二叉樹(shù)、只有一個(gè)根結(jié)點(diǎn)、根結(jié)點(diǎn)只有左子樹(shù)、根結(jié)點(diǎn)只有右子樹(shù)、根結(jié)點(diǎn)既有左子樹(shù)又有右子樹(shù)。二叉樹(shù)定義及性質(zhì)二叉樹(shù)的性質(zhì)在二叉樹(shù)的第i層上至多有2^(i-1)個(gè)結(jié)點(diǎn)（i≥1）。深度為k的二叉樹(shù)至多有2^k-1個(gè)結(jié)點(diǎn)（k≥1）。對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。01020304二叉樹(shù)定義及性質(zhì)先序遍歷（Pre-orderTraversal）：若二叉樹(shù)為空，則空操作返回；否則先訪問(wèn)根結(jié)點(diǎn)，然后先序遍歷左子樹(shù)，最后先序遍歷右子樹(shù)。中序遍歷（In-orderTraversal）：若二叉樹(shù)為空，則空操作返回；否則從根結(jié)點(diǎn)開(kāi)始（注意并不是先訪問(wèn)根結(jié)點(diǎn)），中序遍歷根結(jié)點(diǎn)的左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后中序遍歷右子樹(shù)。后序遍歷（Post-orderTraversal）：若二叉樹(shù)為空，則空操作返回；否則從左到右先葉子后結(jié)點(diǎn)的方式遍歷訪問(wèn)左右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。層序遍歷（Level-orderTraversal）：若二叉樹(shù)為空，則空操作返回；否則從樹(shù)的第一層，也就是根結(jié)點(diǎn)開(kāi)始訪問(wèn)，從上而下逐層遍歷，在同一層中，按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問(wèn)。二叉樹(shù)遍歷方法線索二叉樹(shù)是對(duì)二叉樹(shù)的每個(gè)結(jié)點(diǎn)增設(shè)兩個(gè)標(biāo)志位以及一條線索而得到的。根據(jù)線索性質(zhì)的不同，線索二叉樹(shù)可分為前序線索二叉樹(shù)、中序線索二叉樹(shù)和后序線索二叉樹(shù)三種。這里以中序線索二叉樹(shù)為例來(lái)說(shuō)明線索二叉樹(shù)的構(gòu)造方法。中序線索二叉樹(shù)的構(gòu)造規(guī)則是：若將二叉樹(shù)的中序遍歷序列中的每個(gè)結(jié)點(diǎn)都看作是相應(yīng)指針域?yàn)榭盏闹羔?，則稱這些指針為線索，而指向其前驅(qū)或后繼的指針?lè)Q為線索指針。加上線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹(shù)稱為線索二叉樹(shù)(ThreadedBinaryTree)。根據(jù)線索性質(zhì)的不同，線索二叉樹(shù)可分為前序線索二叉樹(shù)、中序線索二叉樹(shù)和后序線索二叉樹(shù)三種。線索二叉樹(shù)樹(shù)轉(zhuǎn)換為二叉樹(shù)的規(guī)則是：每個(gè)結(jié)點(diǎn)的左指針指向它的第一個(gè)孩子結(jié)點(diǎn)；右指針指向它在樹(shù)上的下一個(gè)兄弟結(jié)點(diǎn)；對(duì)于樹(shù)的根結(jié)點(diǎn)來(lái)說(shuō)，由于沒(méi)有前一個(gè)兄弟結(jié)點(diǎn)，所以它的右指針指向由它的所有孩子結(jié)點(diǎn)構(gòu)成的鏈表的第一個(gè)孩子結(jié)點(diǎn)；對(duì)于其他任何結(jié)點(diǎn)來(lái)說(shuō)，由于它的右指針指向它在樹(shù)上的下一個(gè)兄弟結(jié)點(diǎn)，所以它的所有孩子結(jié)點(diǎn)的左指針均指向它本身。這樣轉(zhuǎn)換后的二叉樹(shù)的左子樹(shù)上樹(shù)和森林轉(zhuǎn)換為二叉樹(shù)方法06圖論基礎(chǔ)與圖數(shù)據(jù)結(jié)構(gòu)圖(Graph)由頂點(diǎn)(Vertex)和邊(Edge)組成的數(shù)據(jù)結(jié)構(gòu)，表示對(duì)象及其之間的關(guān)系。無(wú)向圖(UndirectedGraph)邊沒(méi)有方向的圖。有向圖(DirectedGraph)邊有方向的圖，也稱為有向網(wǎng)絡(luò)。圖論基本概念與術(shù)語(yǔ)圖論基本概念與術(shù)語(yǔ)任意兩個(gè)頂點(diǎn)之間都存在路徑的圖。連通圖(ConnectedGraph)與頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)量。對(duì)于有向圖，分為入度(In-degree)和出度(Out-degree)。頂點(diǎn)的度(Degree)從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)過(guò)的邊的序列。路徑(Path)連通分量(ConnectedComponent)無(wú)向圖中的極大連通子圖。要點(diǎn)一要點(diǎn)二強(qiáng)連通圖(StronglyConnectedGra…有向圖中任意兩個(gè)頂點(diǎn)都存在雙向路徑的圖。圖論基本概念與術(shù)語(yǔ)圖數(shù)據(jù)結(jié)構(gòu)表示方法鄰接矩陣(AdjacencyMatri…用一個(gè)二維數(shù)組表示圖中頂點(diǎn)之間的連接關(guān)系，適用于稠密圖。鄰接表(AdjacencyList)用鏈表或數(shù)組表示每個(gè)頂點(diǎn)的鄰居頂點(diǎn)，適用于稀疏圖。鄰接多重表(AdjacencyMult…改進(jìn)鄰接表，減少存儲(chǔ)空間，方便邊的刪除操作。十字鏈表(CrossList)用于有向圖的存儲(chǔ)結(jié)構(gòu)，可以方便地找到任一頂點(diǎn)的入邊和出邊。圖遍歷算法通過(guò)棧或隊(duì)列輔助實(shí)現(xiàn)深度優(yōu)先遍歷或廣度優(yōu)先遍歷。非遞歸實(shí)現(xiàn)沿著樹(shù)的深度遍歷圖的節(jié)點(diǎn)，盡可能深地搜索圖的分支。深度優(yōu)先遍歷(Depth-FirstSearch,…按層次遍歷圖的節(jié)點(diǎn)，先訪問(wèn)離根節(jié)點(diǎn)近的節(jié)點(diǎn)。廣度優(yōu)先遍歷(Breadth-FirstSearc…普里姆算法(Prim'sAlgorithm)從某一頂點(diǎn)開(kāi)始構(gòu)建生成樹(shù)，每次選擇代價(jià)最小的邊加入生成樹(shù)中，直到所有頂點(diǎn)都加入生成樹(shù)為止。要點(diǎn)一要點(diǎn)