數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第6章

數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第6章緒論線性表?xiàng)：完?duì)列樹和圖查找和排序01緒論數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)和信息技術(shù)專業(yè)的重要基礎(chǔ)課程，是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)學(xué)科的核心課程之一。數(shù)據(jù)結(jié)構(gòu)課程主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)以及基本操作，為后續(xù)的算法設(shè)計(jì)與分析、操作系統(tǒng)、編譯原理等課程提供必要的基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)課程對于培養(yǎng)學(xué)生的數(shù)據(jù)抽象思維、問題解決能力以及軟件開發(fā)能力具有重要意義。數(shù)據(jù)結(jié)構(gòu)課程的重要性數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)是信息的符號表示，是計(jì)算機(jī)處理的對象。數(shù)據(jù)的基本單位，一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)元素中的一個具體單位，是數(shù)據(jù)的最小單位。數(shù)據(jù)元素之間的相互關(guān)系，這種關(guān)系反映了客觀事物的內(nèi)在聯(lián)系。數(shù)據(jù)數(shù)據(jù)元素數(shù)據(jù)項(xiàng)數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)是最基本的數(shù)據(jù)結(jié)構(gòu)，包括線性表、棧、隊(duì)列等。線性結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)樹形結(jié)構(gòu)是一種層次化的數(shù)據(jù)結(jié)構(gòu)，包括二叉樹、多叉樹等。圖形結(jié)構(gòu)是一種復(fù)雜的網(wǎng)狀數(shù)據(jù)結(jié)構(gòu)，包括圖、有向圖、無向圖等。030201數(shù)據(jù)結(jié)構(gòu)的分類02線性表123線性表是一種具有n個元素的有限序列，每個元素都有一個唯一的下標(biāo)，下標(biāo)從0開始遞增。線性表的定義插入、刪除、查找、修改等。線性表的基本操作元素之間是一對一的關(guān)系，即每個元素只有一個前驅(qū)和一個后繼。線性表的特點(diǎn)線性表的定義和基本操作順序存儲結(jié)構(gòu)的優(yōu)點(diǎn)存取速度快，時間復(fù)雜度為O(1)。順序存儲結(jié)構(gòu)的缺點(diǎn)需要預(yù)先分配存儲空間，會造成空間浪費(fèi)；插入和刪除操作需要移動大量元素，時間復(fù)雜度較高。順序存儲結(jié)構(gòu)的定義將線性表中的元素按照邏輯順序依次存儲在一片連續(xù)的存儲單元中。線性表的順序存儲結(jié)構(gòu)

線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)的定義將線性表中的元素按照邏輯順序存儲在一系列離散的存儲單元中，每個元素占用一個存儲單元，并利用指針鏈接相鄰元素。鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)點(diǎn)無需預(yù)先分配存儲空間，可以動態(tài)地擴(kuò)展和收縮；插入和刪除操作只需修改指針，時間復(fù)雜度較低。鏈?zhǔn)酱鎯Y(jié)構(gòu)的缺點(diǎn)存取速度較慢，時間復(fù)雜度為O(n)；需要額外的空間來存儲指針。03棧和隊(duì)列棧是一種特殊的線性表，只允許在表的一端進(jìn)行插入和刪除操作。定義push（入棧）、pop（出棧）、peek（查看棧頂元素）、isEmpty（判斷棧是否為空）等?；静僮鳁５亩x和基本操作使用數(shù)組實(shí)現(xiàn)，通過數(shù)組下標(biāo)來定位元素，時間復(fù)雜度為O(1)。使用鏈表實(shí)現(xiàn)，通過指針來鏈接元素，時間復(fù)雜度為O(1)。棧的存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)順序存儲結(jié)構(gòu)定義隊(duì)列是一種特殊的線性表，只允許在表的一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作?；静僮鱡nqueue（入隊(duì)）、dequeue（出隊(duì)）、isEmpty（判斷隊(duì)列是否為空）等。隊(duì)列的定義和基本操作順序存儲結(jié)構(gòu)使用數(shù)組實(shí)現(xiàn)，通過數(shù)組下標(biāo)來定位元素，時間復(fù)雜度為O(n)。鏈?zhǔn)酱鎯Y(jié)構(gòu)使用鏈表實(shí)現(xiàn)，通過指針來鏈接元素，時間復(fù)雜度為O(1)。隊(duì)列的存儲結(jié)構(gòu)04樹和圖樹的定義樹是由節(jié)點(diǎn)和邊組成的數(shù)據(jù)結(jié)構(gòu)，其中節(jié)點(diǎn)表示對象，邊表示對象之間的關(guān)系。樹是一種層次結(jié)構(gòu)，其中每個節(jié)點(diǎn)可以有多個子節(jié)點(diǎn)，但只能有一個父節(jié)點(diǎn)。根據(jù)節(jié)點(diǎn)的度數(shù)，樹可以分為二叉樹、三叉樹、多叉樹等。根據(jù)節(jié)點(diǎn)是否有分支，樹可以分為有序樹和無序樹。樹的遍歷是指按照某種順序訪問樹中的節(jié)點(diǎn)，可以分為前序遍歷、中序遍歷和后序遍歷。在樹中插入和刪除節(jié)點(diǎn)需要遵循一定的規(guī)則，以保證樹的完整性。樹的分類樹的遍歷樹的插入和刪除樹的定義和基本操作將樹中的節(jié)點(diǎn)按照層次順序存儲在數(shù)組中，每個節(jié)點(diǎn)占用固定數(shù)量的存儲單元。順序存儲結(jié)構(gòu)適用于完全二叉樹。順序存儲結(jié)構(gòu)每個節(jié)點(diǎn)包含指向其子節(jié)點(diǎn)的指針，形成一個鏈表結(jié)構(gòu)。鏈?zhǔn)酱鎯Y(jié)構(gòu)適用于任意結(jié)構(gòu)的樹。鏈?zhǔn)酱鎯Y(jié)構(gòu)將樹中的節(jié)點(diǎn)按照散列函數(shù)映射到哈希表中，以加快查找速度。散列存儲結(jié)構(gòu)適用于需要快速查找的應(yīng)用場景。散列存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)圖是由節(jié)點(diǎn)和邊組成的數(shù)據(jù)結(jié)構(gòu)，其中節(jié)點(diǎn)表示對象，邊表示對象之間的關(guān)系。圖是一種無向、有向或混合型的數(shù)據(jù)結(jié)構(gòu)。圖的定義根據(jù)邊的方向性，圖可以分為有向圖和無向圖。根據(jù)節(jié)點(diǎn)的度數(shù)，圖可以分為稠密圖和稀疏圖。圖的分類圖的遍歷是指按照某種順序訪問圖中的節(jié)點(diǎn)和邊，可以分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷。圖的遍歷圖的連通性是指從一個節(jié)點(diǎn)到另一個節(jié)點(diǎn)是否存在路徑，可以分為強(qiáng)連通圖、單向連通圖和連通圖等。圖的連通性圖的定義和基本操作使用一個矩陣來表示圖中節(jié)點(diǎn)之間的關(guān)系，矩陣中的元素表示兩個節(jié)點(diǎn)之間是否有邊相連。鄰接矩陣適用于稠密圖。鄰接矩陣使用鏈表來表示圖中節(jié)點(diǎn)之間的關(guān)系，每個節(jié)點(diǎn)包含一個鏈表，鏈表中的元素表示與該節(jié)點(diǎn)相連的節(jié)點(diǎn)。鄰接表適用于稀疏圖。鄰接表圖的存儲結(jié)構(gòu)05查找和排序線性查找從數(shù)據(jù)結(jié)構(gòu)的第一個元素開始，逐個比較，直到找到目標(biāo)元素或遍歷完整個數(shù)據(jù)結(jié)構(gòu)。查找的基本概念查找是從數(shù)據(jù)結(jié)構(gòu)中找出滿足特定條件元素的過程。查找操作的效率取決于數(shù)據(jù)結(jié)構(gòu)的選擇和查找算法的優(yōu)劣。二分查找適用于有序數(shù)據(jù)結(jié)構(gòu)，通過將數(shù)據(jù)結(jié)構(gòu)分成兩半，每次比較中間元素與目標(biāo)元素的大小，縮小查找范圍。哈希查找利用哈希函數(shù)將關(guān)鍵字轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)中的位置信息，直接訪問該位置進(jìn)行查找。分塊查找將數(shù)據(jù)結(jié)構(gòu)分成若干塊，每塊內(nèi)部有序，通過塊首元素進(jìn)行索引，再在塊內(nèi)進(jìn)行查找。查找的基本概念和方法排序的基本概念和方法選擇排序每次從未排序部分找到最?。ɑ蜃畲螅┰兀瑢⑵浞诺揭雅判虿糠值哪┪病Ｃ芭菖判蛲ㄟ^相鄰元素比較和交換，使得較大的元素逐漸向數(shù)組尾部移動。排序的基本概念排序是將數(shù)據(jù)結(jié)構(gòu)中的元素按照某種順序重新排列的過程。排序操作的效率取決于排序算法的優(yōu)劣。插入排序?qū)⑽磁判虿糠值谝粋€元素與已排序部分元素逐個比較，找到合適的位置插入?？焖倥判蜻x擇一個基準(zhǔn)元素，將數(shù)組分為兩部分，一部分小于基準(zhǔn)，一部分大于基準(zhǔn)，遞歸地對兩部分進(jìn)行排序。分析查找和排序算法在不同情況下的時間復(fù)