數(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)課程對(duì)于培養(yǎng)學(xué)生的數(shù)據(jù)抽象思維、問題解決能力以及軟件開發(fā)能力具有重要意義。數(shù)據(jù)結(jié)構(gòu)課程的重要性數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)是信息的符號(hào)表示，是計(jì)算機(jī)處理的對(duì)象。數(shù)據(jù)的基本單位，一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)元素中的一個(gè)具體單位，是數(shù)據(jù)的最小單位。數(shù)據(jù)元素之間的相互關(guān)系，這種關(guān)系反映了客觀事物的內(nèi)在聯(lián)系。數(shù)據(jù)數(shù)據(jù)元素?cái)?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個(gè)元素的有限序列，每個(gè)元素都有一個(gè)唯一的下標(biāo)，下標(biāo)從0開始遞增。線性表的定義插入、刪除、查找、修改等。線性表的基本操作元素之間是一對(duì)一的關(guān)系，即每個(gè)元素只有一個(gè)前驅(qū)和一個(gè)后繼。線性表的特點(diǎn)線性表的定義和基本操作順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)存取速度快，時(shí)間復(fù)雜度為O(1)。順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)需要預(yù)先分配存儲(chǔ)空間，會(huì)造成空間浪費(fèi)；插入和刪除操作需要移動(dòng)大量元素，時(shí)間復(fù)雜度較高。順序存儲(chǔ)結(jié)構(gòu)的定義將線性表中的元素按照邏輯順序依次存儲(chǔ)在一片連續(xù)的存儲(chǔ)單元中。線性表的順序存儲(chǔ)結(jié)構(gòu)

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