《結(jié)構(gòu)與鏈表》課件

結(jié)構(gòu)與鏈表數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)的基礎(chǔ)，它為組織和管理數(shù)據(jù)提供了框架。鏈表是一種重要的線性數(shù)據(jù)結(jié)構(gòu)，由一系列節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的指針。課程目標(biāo)理解結(jié)構(gòu)掌握結(jié)構(gòu)的定義、特點(diǎn)、聲明、訪問、嵌套、數(shù)組、指針等概念。掌握鏈表深入理解單鏈表、循環(huán)鏈表、雙向鏈表的定義、創(chuàng)建、遍歷、插入、刪除等操作。提升編程能力通過實(shí)際案例學(xué)習(xí)如何運(yùn)用結(jié)構(gòu)和鏈表解決實(shí)際問題。結(jié)構(gòu)的定義數(shù)據(jù)組織結(jié)構(gòu)是一種用戶自定義的數(shù)據(jù)類型，用于將不同類型的數(shù)據(jù)組合在一起。邏輯關(guān)系結(jié)構(gòu)的成員可以是不同數(shù)據(jù)類型，例如整數(shù)、浮點(diǎn)數(shù)、字符等，并以特定的邏輯關(guān)系組織在一起。命名集合結(jié)構(gòu)可以被視為一個(gè)命名集合，可以存儲(chǔ)和操作相關(guān)數(shù)據(jù)的組合。內(nèi)存分配結(jié)構(gòu)在內(nèi)存中分配連續(xù)的內(nèi)存空間，每個(gè)成員占用相應(yīng)的內(nèi)存大小。結(jié)構(gòu)的特點(diǎn)11.數(shù)據(jù)組織結(jié)構(gòu)允許將相關(guān)數(shù)據(jù)項(xiàng)組合在一起，形成一個(gè)邏輯單元，方便管理和操作。22.內(nèi)存分配結(jié)構(gòu)變量在內(nèi)存中分配連續(xù)的存儲(chǔ)空間，所有成員緊密相鄰，便于高效訪問。33.自定義數(shù)據(jù)類型通過結(jié)構(gòu)，可以定義新的數(shù)據(jù)類型，以滿足特定應(yīng)用的需求，提高代碼的可讀性和可維護(hù)性。44.結(jié)構(gòu)成員訪問結(jié)構(gòu)成員通過結(jié)構(gòu)變量名和成員名進(jìn)行訪問，使用點(diǎn)運(yùn)算符(.)或箭頭運(yùn)算符(->)來訪問。結(jié)構(gòu)的聲明與定義1關(guān)鍵字struct定義結(jié)構(gòu)類型2結(jié)構(gòu)體名稱自定義結(jié)構(gòu)類型3成員列表數(shù)據(jù)類型和成員名稱結(jié)構(gòu)體聲明告訴編譯器定義新數(shù)據(jù)類型。結(jié)構(gòu)體定義創(chuàng)建結(jié)構(gòu)變量，并分配內(nèi)存。結(jié)構(gòu)成員的訪問使用點(diǎn)運(yùn)算符點(diǎn)運(yùn)算符用于訪問結(jié)構(gòu)變量中的成員，例如：struct_name.member_name。使用箭頭運(yùn)算符箭頭運(yùn)算符用于訪問結(jié)構(gòu)指針中的成員，例如：pointer_to_struct->member_name。示例代碼例如，訪問一個(gè)名為student的結(jié)構(gòu)中的name成員，可以使用：。結(jié)構(gòu)的嵌套1結(jié)構(gòu)體嵌套結(jié)構(gòu)體嵌套是指在結(jié)構(gòu)體定義中使用其他結(jié)構(gòu)體作為成員2嵌套結(jié)構(gòu)嵌套結(jié)構(gòu)指的是包含嵌套結(jié)構(gòu)體成員的結(jié)構(gòu)體3成員訪問可以通過“.”運(yùn)算符訪問嵌套結(jié)構(gòu)體的成員結(jié)構(gòu)的嵌套可以方便地組織和管理數(shù)據(jù)，例如，使用嵌套結(jié)構(gòu)體定義學(xué)生信息，可以將姓名、性別、年齡等信息歸類到一個(gè)結(jié)構(gòu)體中，再將該結(jié)構(gòu)體作為另一個(gè)結(jié)構(gòu)體的成員來表示班級(jí)信息。結(jié)構(gòu)數(shù)組定義結(jié)構(gòu)數(shù)組是指由多個(gè)相同結(jié)構(gòu)類型的元素組成的數(shù)組。每個(gè)元素都是一個(gè)完整的結(jié)構(gòu)體，包含了結(jié)構(gòu)體中定義的所有成員。聲明聲明結(jié)構(gòu)數(shù)組時(shí)，需要先聲明結(jié)構(gòu)體類型，然后使用結(jié)構(gòu)體類型聲明數(shù)組。數(shù)組名后面跟上中括號(hào)，括號(hào)內(nèi)包含數(shù)組元素個(gè)數(shù)。結(jié)構(gòu)與指針結(jié)構(gòu)體指針的定義結(jié)構(gòu)體指針可以指向一個(gè)結(jié)構(gòu)體變量，通過指針訪問結(jié)構(gòu)體成員。指針遍歷結(jié)構(gòu)體使用指針遍歷結(jié)構(gòu)體鏈表，可以通過指針訪問鏈表中的每個(gè)節(jié)點(diǎn)，實(shí)現(xiàn)對(duì)鏈表的操作。結(jié)構(gòu)體指針作為函數(shù)參數(shù)結(jié)構(gòu)體指針作為函數(shù)參數(shù)可以提高函數(shù)效率，避免結(jié)構(gòu)體變量的復(fù)制。聯(lián)合體的定義1內(nèi)存共享聯(lián)合體成員共享同一內(nèi)存空間,不同成員間相互覆蓋.2數(shù)據(jù)類型聯(lián)合體可以包含不同數(shù)據(jù)類型的成員,但同一時(shí)間只存儲(chǔ)一個(gè)成員的值.3大小聯(lián)合體的大小等于其最大成員的大小.聯(lián)合體成員的訪問1成員訪問方式通過聯(lián)合體變量名和成員名訪問成員，類似于結(jié)構(gòu)體成員訪問。2共享內(nèi)存空間聯(lián)合體成員共用同一塊內(nèi)存空間，訪問一個(gè)成員會(huì)覆蓋其他成員。3訪問注意事項(xiàng)只能訪問當(dāng)前使用的成員，其他成員值可能被覆蓋。枚舉類型的定義枚舉類型定義枚舉類型是一種用戶定義的類型，它允許將一組具有特定含義的常量值定義在一起。定義語法使用關(guān)鍵字enum定義枚舉類型，并指定枚舉常量的名稱和值。枚舉類型優(yōu)勢(shì)枚舉類型使代碼更易讀、易維護(hù)，并有助于提高代碼的安全性。枚舉類型的應(yīng)用時(shí)間管理枚舉類型可以表示一周中的七天、一個(gè)月中的日期，方便代碼編寫和閱讀。顏色管理使用枚舉類型可以定義顏色，提高代碼的可讀性和可維護(hù)性。游戲開發(fā)游戲中的狀態(tài)、角色類型等都可以使用枚舉類型表示，方便管理和維護(hù)。鏈表的概念動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，可以根據(jù)需要分配和釋放內(nèi)存，與靜態(tài)數(shù)組相比更靈活。鏈表中的元素存儲(chǔ)在稱為節(jié)點(diǎn)的結(jié)構(gòu)中，每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的指針。內(nèi)存管理鏈表節(jié)點(diǎn)在內(nèi)存中可以不連續(xù)分布，通過指針連接起來，使得在插入和刪除元素時(shí)不需要移動(dòng)其他元素，提高效率。鏈表的大小可以根據(jù)需要?jiǎng)討B(tài)調(diào)整，無需預(yù)先分配固定大小的內(nèi)存空間，避免空間浪費(fèi)。單鏈表的定義節(jié)點(diǎn)結(jié)構(gòu)每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)域和指針域，分別用于存儲(chǔ)數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的地址。頭指針指向鏈表中第一個(gè)節(jié)點(diǎn)的指針，通過它可以訪問整個(gè)鏈表。尾指針指向鏈表中最后一個(gè)節(jié)點(diǎn)的指針，通常用于快速插入或刪除節(jié)點(diǎn)。單鏈表的創(chuàng)建1頭結(jié)點(diǎn)的創(chuàng)建首先，需要?jiǎng)?chuàng)建一個(gè)頭結(jié)點(diǎn)，它用來指向鏈表的第一個(gè)節(jié)點(diǎn)。2第一個(gè)節(jié)點(diǎn)的創(chuàng)建然后，創(chuàng)建一個(gè)新的節(jié)點(diǎn)，并將其數(shù)據(jù)域設(shè)置為要存儲(chǔ)的數(shù)據(jù)。3連接頭結(jié)點(diǎn)與第一個(gè)節(jié)點(diǎn)最后，將頭結(jié)點(diǎn)的指針指向新創(chuàng)建的第一個(gè)節(jié)點(diǎn)，完成鏈表的創(chuàng)建。單鏈表的遍歷遍歷單鏈表是指依次訪問鏈表中的所有節(jié)點(diǎn)，并對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行操作。遍歷過程從鏈表的頭節(jié)點(diǎn)開始，依次訪問每個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，直到遇到空指針。1頭指針2當(dāng)前節(jié)點(diǎn)訪問節(jié)點(diǎn)數(shù)據(jù)3下一個(gè)節(jié)點(diǎn)移動(dòng)指針遍歷算法的關(guān)鍵是使用指針遍歷鏈表，并通過當(dāng)前節(jié)點(diǎn)的指針訪問下一個(gè)節(jié)點(diǎn)。單鏈表的插入1定位插入位置根據(jù)插入節(jié)點(diǎn)值，找到目標(biāo)節(jié)點(diǎn)2創(chuàng)建新節(jié)點(diǎn)分配內(nèi)存空間，存儲(chǔ)新節(jié)點(diǎn)數(shù)據(jù)3調(diào)整指針修改目標(biāo)節(jié)點(diǎn)指針，連接新節(jié)點(diǎn)單鏈表插入操作涉及找到目標(biāo)節(jié)點(diǎn)，創(chuàng)建新節(jié)點(diǎn)，以及修改指針以連接新節(jié)點(diǎn)。單鏈表的刪除1確定要?jiǎng)h除的節(jié)點(diǎn)首先，需要定位到鏈表中要?jiǎng)h除的節(jié)點(diǎn)?？梢酝ㄟ^遍歷鏈表，比較節(jié)點(diǎn)的值與目標(biāo)值來找到該節(jié)點(diǎn)。2修改指針指向找到要?jiǎng)h除的節(jié)點(diǎn)后，需要修改其前一個(gè)節(jié)點(diǎn)的指針，使其指向下一個(gè)節(jié)點(diǎn)，從而將要?jiǎng)h除的節(jié)點(diǎn)從鏈表中移除。3釋放內(nèi)存最后，需要釋放被刪除節(jié)點(diǎn)所占用的內(nèi)存空間，以避免內(nèi)存泄漏。循環(huán)鏈表的特點(diǎn)首尾相連循環(huán)鏈表中最后一個(gè)節(jié)點(diǎn)的指針指向第一個(gè)節(jié)點(diǎn)，形成閉環(huán)結(jié)構(gòu)。循環(huán)遍歷可以通過循環(huán)遍歷鏈表，從任意節(jié)點(diǎn)開始，一直遍歷到起始節(jié)點(diǎn)。無起始節(jié)點(diǎn)循環(huán)鏈表中不存在明確的起始節(jié)點(diǎn)，可以從任意節(jié)點(diǎn)開始遍歷。循環(huán)鏈表的創(chuàng)建1初始化頭結(jié)點(diǎn)創(chuàng)建空鏈表，頭指針指向NULL2創(chuàng)建第一個(gè)節(jié)點(diǎn)創(chuàng)建新節(jié)點(diǎn)，分配內(nèi)存空間3連接第一個(gè)節(jié)點(diǎn)將第一個(gè)節(jié)點(diǎn)的指針指向自身4后續(xù)節(jié)點(diǎn)創(chuàng)建創(chuàng)建新節(jié)點(diǎn)，并將新節(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)循環(huán)鏈表的創(chuàng)建過程與單鏈表類似。首先需要初始化頭結(jié)點(diǎn)，然后創(chuàng)建第一個(gè)節(jié)點(diǎn)，并將其指針指向自身，形成循環(huán)。后續(xù)節(jié)點(diǎn)創(chuàng)建時(shí)，將新節(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，從而完成循環(huán)鏈表的創(chuàng)建。雙向鏈表的定義11.節(jié)點(diǎn)結(jié)構(gòu)每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)域和兩個(gè)指針域，分別指向其前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)。22.方向性每個(gè)節(jié)點(diǎn)可以雙向訪問，可以通過前驅(qū)指針訪問前一個(gè)節(jié)點(diǎn)，通過后繼指針訪問后一個(gè)節(jié)點(diǎn)。33.首尾節(jié)點(diǎn)鏈表的頭結(jié)點(diǎn)指向第一個(gè)節(jié)點(diǎn)，尾結(jié)點(diǎn)指向最后一個(gè)節(jié)點(diǎn)，方便操作和遍歷。雙向鏈表的創(chuàng)建1.初始化節(jié)點(diǎn)為每個(gè)新節(jié)點(diǎn)分配內(nèi)存空間，并設(shè)置節(jié)點(diǎn)的data值，以及指向其前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)的指針。例如，可以通過malloc()或new來分配內(nèi)存。2.設(shè)置頭節(jié)點(diǎn)創(chuàng)建頭節(jié)點(diǎn)并設(shè)置其指針指向第一個(gè)節(jié)點(diǎn)，并將第一個(gè)節(jié)點(diǎn)的前驅(qū)指針指向頭節(jié)點(diǎn)。頭節(jié)點(diǎn)是鏈表的入口，可以方便地訪問第一個(gè)節(jié)點(diǎn)。3.連接節(jié)點(diǎn)將每個(gè)新節(jié)點(diǎn)的前驅(qū)指針指向其上一個(gè)節(jié)點(diǎn)，并將其后繼指針指向其下一個(gè)節(jié)點(diǎn)。這樣就將節(jié)點(diǎn)串聯(lián)起來，形成一個(gè)雙向鏈表。4.設(shè)置尾節(jié)點(diǎn)設(shè)置尾節(jié)點(diǎn)的指針指向NULL，這樣可以方便地判斷鏈表的尾部，避免越界訪問。雙向鏈表的遍歷1初始化指針指向頭節(jié)點(diǎn)2循環(huán)遍歷訪問當(dāng)前節(jié)點(diǎn)3移動(dòng)指針指向下一個(gè)節(jié)點(diǎn)4判斷結(jié)束指針到達(dá)尾節(jié)點(diǎn)雙向鏈表遍歷需要兩個(gè)指針，分別指向當(dāng)前節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)。通過循環(huán)訪問每個(gè)節(jié)點(diǎn)，直到指針到達(dá)尾節(jié)點(diǎn)。雙向鏈表的插入1定位目標(biāo)節(jié)點(diǎn)找到要插入節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)2創(chuàng)建新節(jié)點(diǎn)分配內(nèi)存并初始化新節(jié)點(diǎn)數(shù)據(jù)3連接新節(jié)點(diǎn)將新節(jié)點(diǎn)連接到前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)雙向鏈表的刪除定位節(jié)點(diǎn)首先需要找到要?jiǎng)h除的節(jié)點(diǎn)。通過遍歷鏈表，查找指定值的節(jié)點(diǎn)。修改指針將要?jiǎng)h除節(jié)點(diǎn)的前后節(jié)點(diǎn)的指針指向彼此，從而將該節(jié)點(diǎn)從鏈表中分離。釋放內(nèi)存釋放被刪除節(jié)點(diǎn)所占用的內(nèi)存空間，防止內(nèi)存泄漏。鏈表的應(yīng)用操作系統(tǒng)內(nèi)存管理鏈表是實(shí)現(xiàn)內(nèi)存分配和回收的理想數(shù)據(jù)結(jié)構(gòu)。它允許動(dòng)態(tài)分配和釋放內(nèi)存塊，并通過指針連接起來形成一個(gè)可擴(kuò)展的內(nèi)存池。音樂播放器播放列表鏈表可以用于創(chuàng)建音樂播放器的播放列表，允許用戶添加、刪除、播放和管理歌曲，并通過指針連接歌曲節(jié)點(diǎn)。網(wǎng)頁瀏覽器歷史記錄鏈表可以用來實(shí)現(xiàn)網(wǎng)頁瀏覽器歷史記錄功能。每個(gè)節(jié)點(diǎn)代表一個(gè)訪問過的網(wǎng)頁，通過指針鏈接起來，允許用戶快速訪問之前瀏覽過的網(wǎng)頁。游戲角色背包鏈表可以用于創(chuàng)建游戲角色背包，每個(gè)節(jié)點(diǎn)代表一個(gè)物品，通過指針連接起來，方便角色存儲(chǔ)和管理各種物品。性能分析鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，其效率取決于操作的類型。插入和刪除操作在鏈表中通常比數(shù)組更快，因?yàn)樗恍枰苿?dòng)元素來騰出空間。但是，訪問