《認(rèn)識(shí)結(jié)構(gòu)》課件

認(rèn)識(shí)結(jié)構(gòu)結(jié)構(gòu)是事物內(nèi)部各部分之間的聯(lián)系和排列方式。結(jié)構(gòu)是事物存在的本質(zhì)特征。課程介紹課程目標(biāo)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的基本概念和理論掌握常用數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)方法培養(yǎng)學(xué)生分析問題和解決問題的能力課程內(nèi)容線性結(jié)構(gòu)：數(shù)組、鏈表、棧、隊(duì)列樹形結(jié)構(gòu)：二叉樹、樹、圖結(jié)構(gòu)的性質(zhì)、表示、遍歷什么是結(jié)構(gòu)結(jié)構(gòu)是數(shù)據(jù)組織、存儲(chǔ)和訪問的方式。數(shù)據(jù)結(jié)構(gòu)是一種數(shù)據(jù)元素之間的相互關(guān)系，它描述了數(shù)據(jù)的邏輯結(jié)構(gòu)。例如，一本書的章節(jié)結(jié)構(gòu)是線性的，而網(wǎng)頁的結(jié)構(gòu)是樹形的。結(jié)構(gòu)的分類11.線性結(jié)構(gòu)數(shù)據(jù)元素之間存在一對(duì)一關(guān)系，可以按照順序訪問。22.非線性結(jié)構(gòu)數(shù)據(jù)元素之間存在一對(duì)多或多對(duì)多關(guān)系，例如樹形結(jié)構(gòu)和圖結(jié)構(gòu)。33.混合結(jié)構(gòu)結(jié)合了線性結(jié)構(gòu)和非線性結(jié)構(gòu)的特性，例如樹形結(jié)構(gòu)可以看作是線性結(jié)構(gòu)和非線性結(jié)構(gòu)的結(jié)合。線性結(jié)構(gòu)線性結(jié)構(gòu)是最簡單、最基本的數(shù)據(jù)結(jié)構(gòu)之一。線性結(jié)構(gòu)中的元素按照一定的順序排列，每個(gè)元素都有一個(gè)唯一的前驅(qū)和后繼（除了第一個(gè)和最后一個(gè)元素）。線性結(jié)構(gòu)可以用數(shù)組或鏈表來實(shí)現(xiàn)，不同的實(shí)現(xiàn)方式會(huì)影響其性能和空間占用。樹形結(jié)構(gòu)層級(jí)關(guān)系樹形結(jié)構(gòu)表示數(shù)據(jù)之間分層和從屬關(guān)系。非線性結(jié)構(gòu)樹形結(jié)構(gòu)是一種非線性結(jié)構(gòu)，節(jié)點(diǎn)之間沒有前后順序。廣泛應(yīng)用樹形結(jié)構(gòu)廣泛用于文件系統(tǒng)、目錄結(jié)構(gòu)、數(shù)據(jù)庫等領(lǐng)域。圖形結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)節(jié)點(diǎn)和邊表示現(xiàn)實(shí)世界中的各種關(guān)系例如社交網(wǎng)絡(luò)、交通網(wǎng)絡(luò)地圖結(jié)構(gòu)節(jié)點(diǎn)和邊表示地理位置例如城市、道路、距離家族關(guān)系結(jié)構(gòu)節(jié)點(diǎn)和邊表示家庭成員關(guān)系例如父母、子女、兄弟姐妹結(jié)構(gòu)的性質(zhì)邏輯性結(jié)構(gòu)定義了元素之間的邏輯關(guān)系，例如包含、順序、層次等，使數(shù)據(jù)組織清晰且可理解。抽象性結(jié)構(gòu)是一種抽象的模型，不依賴于具體的實(shí)現(xiàn)細(xì)節(jié)，可以用不同的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)同一邏輯結(jié)構(gòu)。動(dòng)態(tài)性結(jié)構(gòu)允許動(dòng)態(tài)地添加、刪除、修改元素，以適應(yīng)不斷變化的數(shù)據(jù)需求。共享性結(jié)構(gòu)可以被多個(gè)模塊共享，提高程序代碼的可復(fù)用性。結(jié)構(gòu)的表示1圖形表示圖形表示法使用圖形來直觀地展示結(jié)構(gòu)關(guān)系。例如，樹狀結(jié)構(gòu)可以用樹形圖表示，線性結(jié)構(gòu)可以用線段表示。2文字表示文字表示法使用文本描述結(jié)構(gòu)關(guān)系。例如，可以采用樹形結(jié)構(gòu)的括號(hào)表示法，或使用線性結(jié)構(gòu)的列表表示法。3數(shù)學(xué)表示數(shù)學(xué)表示法使用數(shù)學(xué)符號(hào)和公式來表達(dá)結(jié)構(gòu)關(guān)系。例如，可以用集合論的符號(hào)來描述結(jié)構(gòu)元素之間的關(guān)系。結(jié)構(gòu)的遍歷結(jié)構(gòu)的遍歷是指按照某種順序訪問數(shù)據(jù)結(jié)構(gòu)中的所有節(jié)點(diǎn)的過程。遍歷是數(shù)據(jù)結(jié)構(gòu)中最基礎(chǔ)的操作之一，它是很多其他操作的基礎(chǔ)。1深度優(yōu)先遍歷先訪問根節(jié)點(diǎn)，再依次訪問其子節(jié)點(diǎn)2廣度優(yōu)先遍歷先訪問同一層級(jí)節(jié)點(diǎn)，再依次訪問下一層級(jí)節(jié)點(diǎn)3前序遍歷先訪問根節(jié)點(diǎn)，再遞歸訪問左子樹，最后遞歸訪問右子樹4中序遍歷先遞歸訪問左子樹，再訪問根節(jié)點(diǎn)，最后遞歸訪問右子樹5后序遍歷先遞歸訪問左子樹，再遞歸訪問右子樹，最后訪問根節(jié)點(diǎn)線性表的定義有序的元素序列線性表是一個(gè)由零個(gè)或多個(gè)數(shù)據(jù)元素組成的有限序列，元素之間有順序關(guān)系。邏輯地址每個(gè)數(shù)據(jù)元素都擁有一個(gè)唯一的邏輯地址，用于區(qū)分不同的元素。相同類型線性表中的所有數(shù)據(jù)元素都具有相同的類型，比如整型、浮點(diǎn)型或字符型。線性表的特點(diǎn)有序性線性表中的元素按其邏輯順序排列。每個(gè)元素都有一個(gè)唯一的前驅(qū)和后繼（除了第一個(gè)和最后一個(gè)元素）。有限性線性表中的元素個(gè)數(shù)是有限的?？梢允强毡恚礇]有任何元素。線性表的基本操作1插入將一個(gè)新元素插入到線性表中指定位置。2刪除從線性表中刪除指定位置的元素。3查找在線性表中查找指定元素。4修改修改線性表中指定位置的元素。線性表的基本操作包括插入、刪除、查找和修改，這些操作是線性表數(shù)據(jù)結(jié)構(gòu)的常用功能。這些操作的設(shè)計(jì)和實(shí)現(xiàn)必須滿足數(shù)據(jù)結(jié)構(gòu)的定義和要求。線性表的實(shí)現(xiàn)順序存儲(chǔ)順序存儲(chǔ)結(jié)構(gòu)是指用一組連續(xù)的內(nèi)存單元存放線性表中的數(shù)據(jù)元素。每個(gè)數(shù)據(jù)元素占用一個(gè)內(nèi)存單元，數(shù)據(jù)元素在內(nèi)存中按邏輯順序存放。鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指用一組任意的內(nèi)存單元存放線性表中的數(shù)據(jù)元素。每個(gè)數(shù)據(jù)元素占用一個(gè)內(nèi)存單元，數(shù)據(jù)元素在內(nèi)存中不一定要按邏輯順序存放，而是通過指針來鏈接。選擇合適的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)適合存儲(chǔ)數(shù)據(jù)元素?cái)?shù)量固定且不需要頻繁插入或刪除元素的線性表；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)適合存儲(chǔ)數(shù)據(jù)元素?cái)?shù)量不固定且需要頻繁插入或刪除元素的線性表。順序存儲(chǔ)結(jié)構(gòu)連續(xù)存儲(chǔ)將線性表中的所有元素存儲(chǔ)在一段連續(xù)的內(nèi)存空間中。地址映射每個(gè)元素的地址可以由起始地址和元素在表中的位置計(jì)算得出。隨機(jī)訪問可以通過索引直接訪問任意元素，支持隨機(jī)訪問。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)節(jié)點(diǎn)結(jié)構(gòu)每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)域和指針域。動(dòng)態(tài)分配節(jié)點(diǎn)在需要時(shí)動(dòng)態(tài)分配內(nèi)存，無需預(yù)先確定大小。指針連接節(jié)點(diǎn)通過指針域相互連接，形成鏈表。靈活高效鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)靈活，可方便地插入或刪除節(jié)點(diǎn)。棧的定義11.后進(jìn)先出棧是一種線性數(shù)據(jù)結(jié)構(gòu)，遵循后進(jìn)先出的原則。22.數(shù)據(jù)訪問只能在棧頂進(jìn)行數(shù)據(jù)的插入和刪除操作。33.數(shù)據(jù)存儲(chǔ)棧中的數(shù)據(jù)元素按照線性順序存儲(chǔ)。44.應(yīng)用廣泛棧在函數(shù)調(diào)用、表達(dá)式求值、瀏覽器歷史記錄等方面有著廣泛應(yīng)用。棧的基本操作1入棧將元素壓入棧頂2出棧彈出棧頂元素3獲取棧頂元素查看棧頂元素，不改變棧結(jié)構(gòu)4判斷棧是否為空檢查棧中是否包含元素棧的基本操作可以看作是數(shù)據(jù)的進(jìn)出管理，入棧相當(dāng)于添加元素，出棧相當(dāng)于移除元素，獲取棧頂元素方便查看最新添加的元素，判斷棧是否為空可以避免程序出現(xiàn)異常。棧的應(yīng)用1表達(dá)式求值?？梢杂糜趯⒅芯Y表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，然后進(jìn)行求值，這在編譯器和解釋器中非常有用。2函數(shù)調(diào)用棧用于存儲(chǔ)函數(shù)調(diào)用時(shí)的參數(shù)、局部變量和返回地址，以確保函數(shù)調(diào)用和返回的正確執(zhí)行。3撤銷操作在文本編輯器或圖形軟件中，?？梢杂脕泶鎯?chǔ)用戶的操作歷史記錄，以便用戶可以撤銷之前的操作。4瀏覽器歷史記錄瀏覽器使用棧來存儲(chǔ)用戶訪問過的網(wǎng)頁，以便用戶可以輕松地返回到之前訪問過的頁面。隊(duì)列的定義先進(jìn)先出隊(duì)列是一種線性數(shù)據(jù)結(jié)構(gòu)，遵循“先進(jìn)先出(FIFO)”原則。等待隊(duì)列它就像一個(gè)排隊(duì)等候的隊(duì)伍，先加入隊(duì)列的元素將先被處理?；静僮麝?duì)列的基本操作包括入隊(duì)(enqueue)和出隊(duì)(dequeue)。隊(duì)列的基本操作入隊(duì)將新元素添加到隊(duì)列的尾部。新元素成為隊(duì)尾。出隊(duì)從隊(duì)列的頭部刪除元素。隊(duì)頭元素被移除。獲取隊(duì)頭元素返回隊(duì)列的隊(duì)頭元素，但不刪除該元素。判斷隊(duì)列是否為空檢查隊(duì)列是否為空。返回真值或假值。隊(duì)列的應(yīng)用超市收銀顧客排隊(duì)結(jié)賬，先到先服務(wù)，符合FIFO原則。打印機(jī)任務(wù)打印機(jī)按順序執(zhí)行打印任務(wù)，確保先提交的任務(wù)先完成。網(wǎng)頁請求處理服務(wù)器接收并處理網(wǎng)頁請求，按順序執(zhí)行，提高效率。樹的定義非線性結(jié)構(gòu)樹是一種非線性數(shù)據(jù)結(jié)構(gòu)，它由節(jié)點(diǎn)和邊組成，節(jié)點(diǎn)之間通過邊連接。層次結(jié)構(gòu)樹具有層次結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)最多有一個(gè)父節(jié)點(diǎn)，可能有多個(gè)子節(jié)點(diǎn)，形成一個(gè)樹形結(jié)構(gòu)。根節(jié)點(diǎn)樹結(jié)構(gòu)中只有一個(gè)根節(jié)點(diǎn)，沒有父節(jié)點(diǎn)，其他節(jié)點(diǎn)都從根節(jié)點(diǎn)開始往下延伸。葉節(jié)點(diǎn)沒有子節(jié)點(diǎn)的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)，是樹結(jié)構(gòu)中最底層的節(jié)點(diǎn)。樹的基本術(shù)語根節(jié)點(diǎn)樹的頂端節(jié)點(diǎn)，沒有父節(jié)點(diǎn)，是樹的起點(diǎn)。它代表著樹的起始位置，其他節(jié)點(diǎn)都可從根節(jié)點(diǎn)開始訪問。子節(jié)點(diǎn)樹中除根節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)都只有一個(gè)父節(jié)點(diǎn)，可以擁有多個(gè)子節(jié)點(diǎn)。子節(jié)點(diǎn)是從父節(jié)點(diǎn)衍生出來的，代表著數(shù)據(jù)結(jié)構(gòu)的分支關(guān)系。父節(jié)點(diǎn)樹中具有子節(jié)點(diǎn)的節(jié)點(diǎn)，它位于子節(jié)點(diǎn)之上。父節(jié)點(diǎn)與子節(jié)點(diǎn)之間的關(guān)系反映了數(shù)據(jù)結(jié)構(gòu)的層次關(guān)系。葉子節(jié)點(diǎn)沒有子節(jié)點(diǎn)的節(jié)點(diǎn)，是樹的末端節(jié)點(diǎn)，代表著數(shù)據(jù)結(jié)構(gòu)的最終元素。它們通常是樹的最底層，表示著數(shù)據(jù)結(jié)構(gòu)的最小單位。樹的遍歷1先序遍歷根節(jié)點(diǎn)->左子樹->右子樹2中序遍歷左子樹->根節(jié)點(diǎn)->右子樹3后序遍歷左子樹->右子樹->根節(jié)點(diǎn)樹的遍歷指的是按照某種順序訪問樹中的所有節(jié)點(diǎn)，并對(duì)每個(gè)節(jié)點(diǎn)執(zhí)行某種操作。常見的樹的遍歷方法包括先序遍歷、中序遍歷和后序遍歷，它們的區(qū)別在于訪問根節(jié)點(diǎn)的時(shí)機(jī)。二叉樹的定義樹狀結(jié)構(gòu)二叉樹是一種特殊的樹結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)最多有2個(gè)子節(jié)點(diǎn)，分別稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。節(jié)點(diǎn)關(guān)系二叉樹節(jié)點(diǎn)之間的關(guān)系用父子關(guān)系來描述，根節(jié)點(diǎn)沒有父節(jié)點(diǎn)，其他節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)。二叉樹的特點(diǎn)層次結(jié)構(gòu)根節(jié)點(diǎn)位于頂層，子節(jié)點(diǎn)位于下一層，形成清晰的層次結(jié)構(gòu)。遞歸定義二叉樹由一個(gè)根節(jié)點(diǎn)和至多兩個(gè)子樹組成，子樹也都是二叉樹。節(jié)點(diǎn)關(guān)系每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，分別稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。路徑唯一從根節(jié)點(diǎn)到任意節(jié)點(diǎn)的路徑是唯一的，不存在重復(fù)的路徑。二叉樹的應(yīng)用11.表達(dá)式計(jì)算二叉樹可以有效地表示算術(shù)表達(dá)式，方便計(jì)算機(jī)進(jìn)行解析和計(jì)算。22.數(shù)據(jù)庫索引二叉搜索樹可以快速查找數(shù)據(jù)，提