C數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記一線性表課件總結(jié)12024/1/24CONTENTS線性表基本概念與操作順序存儲(chǔ)結(jié)構(gòu)下線性表實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下線性表實(shí)現(xiàn)線性表應(yīng)用舉例與問題分析線性表性能分析與優(yōu)化策略總結(jié)回顧與拓展延伸22024/1/24線性表基本概念與操作0132024/1/24每個(gè)元素必須是同一類型的數(shù)據(jù)。01020304線性表是由n（n≥0）個(gè)具有相同類型的數(shù)據(jù)元素（結(jié)點(diǎn)）a1，a2，…，an組成的有序序列。元素之間具有一對一的前驅(qū)和后繼關(guān)系，即除首尾元素外，每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。線性表的長度可變，即可以插入或刪除元素。線性表定義有序性同一性可變性線性表定義及特點(diǎn)42024/1/24創(chuàng)建一個(gè)空的線性表。線性表基本操作初始化操作在線性表的指定位置插入一個(gè)元素。插入操作刪除線性表中指定位置的元素。刪除操作在線性表中查找指定元素，并返回其位置。查找操作依次訪問線性表中的每個(gè)元素。遍歷操作釋放線性表所占用的內(nèi)存空間。銷毀操作52024/1/24用一段連續(xù)的存儲(chǔ)空間來存儲(chǔ)線性表中的數(shù)據(jù)元素，邏輯上相鄰的元素在物理位置上也相鄰。順序存儲(chǔ)結(jié)構(gòu)具有隨機(jī)存取的特點(diǎn)，即通過下標(biāo)可以直接訪問任意元素。順序存儲(chǔ)結(jié)構(gòu)用一組任意的存儲(chǔ)空間來存儲(chǔ)線性表中的數(shù)據(jù)元素，這組存儲(chǔ)空間可以是連續(xù)的，也可以是不連續(xù)的。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通過指針來表示元素之間的邏輯關(guān)系，每個(gè)結(jié)點(diǎn)包含數(shù)據(jù)域和指針域兩部分。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)具有插入和刪除操作靈活的特點(diǎn)，但需要額外的空間來存儲(chǔ)指針信息。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表存儲(chǔ)結(jié)構(gòu)62024/1/24順序存儲(chǔ)結(jié)構(gòu)下線性表實(shí)現(xiàn)0272024/1/24用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。定義邏輯上相鄰的元素，物理位置也相鄰；可隨機(jī)存取任一元素。特點(diǎn)順序存儲(chǔ)結(jié)構(gòu)定義與特點(diǎn)82024/1/24遍歷操作依次訪問線性表中的每個(gè)元素。查找操作通過元素值查找其在線性表中的位置。刪除操作刪除指定位置的元素，需移動(dòng)刪除位置后的所有元素。初始化操作分配一段連續(xù)的存儲(chǔ)空間，并設(shè)置線性表的初始狀態(tài)。插入操作在指定位置插入一個(gè)元素，需移動(dòng)插入位置后的所有元素。順序存儲(chǔ)結(jié)構(gòu)下基本操作實(shí)現(xiàn)92024/1/24優(yōu)點(diǎn)存儲(chǔ)密度大，空間利用率高?？梢噪S機(jī)存取，即可以直接訪問任意元素。順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)分析102024/1/24利用數(shù)組實(shí)現(xiàn)，編程相對簡單。順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)分析112024/1/24缺點(diǎn)插入和刪除操作需要移動(dòng)大量元素，時(shí)間復(fù)雜度高。由于要求內(nèi)存空間連續(xù)，容易產(chǎn)生內(nèi)存碎片。預(yù)先分配存儲(chǔ)空間，可能會(huì)造成空間浪費(fèi)。順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)分析122024/1/24鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下線性表實(shí)現(xiàn)03132024/1/24鏈表中的結(jié)點(diǎn)由數(shù)據(jù)域和指針域兩部分組成，數(shù)據(jù)域用于存儲(chǔ)數(shù)據(jù)元素值，指針域用于存放其后繼結(jié)點(diǎn)的地址。鏈表的頭指針指向鏈表的第一個(gè)結(jié)點(diǎn)，終端結(jié)點(diǎn)的指針為空。邏輯上相鄰的元素在物理位置上不一定相鄰，元素間的邏輯關(guān)系是通過指針鏈接表示的。定義：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素（這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的）。特點(diǎn)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義與特點(diǎn)142024/1/24初始化鏈表插入操作刪除操作查找操作單鏈表基本操作實(shí)現(xiàn)創(chuàng)建一個(gè)空鏈表，只含有一個(gè)頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的指針域?yàn)榭?。刪除鏈表中指定位置的結(jié)點(diǎn)，需要修改相鄰結(jié)點(diǎn)的指針。在鏈表的指定位置插入一個(gè)新結(jié)點(diǎn)，需要修改相鄰結(jié)點(diǎn)的指針。從鏈表的頭結(jié)點(diǎn)開始，順著鏈表逐個(gè)比較各結(jié)點(diǎn)中的數(shù)據(jù)，直到找到相應(yīng)的結(jié)點(diǎn)或遍歷完整個(gè)鏈表。152024/1/24循環(huán)鏈表將單鏈表中終端結(jié)點(diǎn)的指針端由空指針改為指向頭結(jié)點(diǎn)，就使整個(gè)單鏈表形成一個(gè)環(huán)，這種頭尾相接的單鏈表稱為單循環(huán)鏈表，簡稱循環(huán)鏈表。雙向鏈表在單鏈表的每個(gè)結(jié)點(diǎn)中，再設(shè)置一個(gè)指向其前驅(qū)結(jié)點(diǎn)的指針域。所以在雙向鏈表中的結(jié)點(diǎn)都有兩個(gè)指針域，一個(gè)指向直接后繼，另一個(gè)指向直接前驅(qū)。循環(huán)鏈表和雙向鏈表簡介162024/1/24線性表應(yīng)用舉例與問題分析04172024/1/24問題描述01一元多項(xiàng)式是數(shù)學(xué)中的基本概念，如何有效地在計(jì)算機(jī)中表示和操作一元多項(xiàng)式是一個(gè)重要問題。解決方案02使用線性表來表示一元多項(xiàng)式，每個(gè)節(jié)點(diǎn)存儲(chǔ)多項(xiàng)式的系數(shù)和指數(shù)。通過線性表的插入、刪除和查找等操作，可以實(shí)現(xiàn)對一元多項(xiàng)式的加減乘除等運(yùn)算。優(yōu)缺點(diǎn)分析03該方案簡單直觀，易于實(shí)現(xiàn)。但對于高次多項(xiàng)式，可能會(huì)占用較多的存儲(chǔ)空間。一元多項(xiàng)式表示問題182024/1/24解決方案使用線性表（循環(huán)鏈表）來模擬約瑟夫環(huán)，每個(gè)節(jié)點(diǎn)代表一個(gè)人。通過遍歷鏈表并按照規(guī)則刪除節(jié)點(diǎn)，直到最后只剩下一個(gè)節(jié)點(diǎn)為止。問題描述約瑟夫環(huán)問題是一個(gè)經(jīng)典的數(shù)學(xué)和計(jì)算機(jī)科學(xué)問題，描述了一個(gè)圍成環(huán)狀的n個(gè)人，按照一定規(guī)則一個(gè)接一個(gè)地淘汰，直到最后剩下一個(gè)人為止。優(yōu)缺點(diǎn)分析該方案可以直觀地模擬約瑟夫環(huán)問題的求解過程。但在處理大規(guī)模數(shù)據(jù)時(shí)，可能會(huì)面臨性能瓶頸。約瑟夫環(huán)問題192024/1/24案例一圖書管理系統(tǒng)中的書目信息存儲(chǔ)與檢索?？梢允褂镁€性表來存儲(chǔ)書目信息，每個(gè)節(jié)點(diǎn)包含一本書的詳細(xì)信息（如書名、作者、出版社等）。通過線性表的查找操作，可以快速檢索到特定書目的信息。案例二學(xué)生信息管理系統(tǒng)中的學(xué)生信息存儲(chǔ)與操作?？梢允褂镁€性表來存儲(chǔ)學(xué)生信息，每個(gè)節(jié)點(diǎn)包含一個(gè)學(xué)生的詳細(xì)信息（如學(xué)號、姓名、成績等）。通過線性表的插入、刪除和查找等操作，可以方便地對學(xué)生信息進(jìn)行管理。案例三物流系統(tǒng)中的貨物配送路徑規(guī)劃?？梢允褂镁€性表來表示貨物的配送路徑，每個(gè)節(jié)點(diǎn)代表一個(gè)配送點(diǎn)。通過線性表的遍歷和修改操作，可以優(yōu)化配送路徑并提高配送效率。其他典型應(yīng)用案例202024/1/24線性表性能分析與優(yōu)化策略05212024/1/24在已知位置插入一個(gè)元素，需要移動(dòng)插入位置及之后的元素，時(shí)間復(fù)雜度為O(n)。刪除指定位置的元素，需要移動(dòng)刪除位置之后的元素，時(shí)間復(fù)雜度為O(n)。順序查找的時(shí)間復(fù)雜度為O(n)，二分查找的時(shí)間復(fù)雜度為O(logn)（需滿足有序表）。插入操作刪除操作查找操作時(shí)間復(fù)雜度分析222024/1/24預(yù)分配固定大小的數(shù)組空間，空間復(fù)雜度為O(1)。根據(jù)實(shí)際需求動(dòng)態(tài)分配空間，空間復(fù)雜度與元素個(gè)數(shù)成正比，為O(n)?？臻g復(fù)雜度分析動(dòng)態(tài)分配靜態(tài)分配232024/1/24如哈希表等，可將查找時(shí)間復(fù)雜度降至O(1)。使用更高效的查找算法采用合適的數(shù)據(jù)結(jié)構(gòu)空間優(yōu)化預(yù)處理如鏈表可高效地進(jìn)行插入和刪除操作，時(shí)間復(fù)雜度為O(1)。對于大量數(shù)據(jù)的處理，可采用壓縮存儲(chǔ)等技術(shù)減少空間占用。通過對數(shù)據(jù)進(jìn)行排序、分組等預(yù)處理操作，可提高后續(xù)操作的效率。優(yōu)化策略探討242024/1/24總結(jié)回顧與拓展延伸06252024/1/24關(guān)鍵知識點(diǎn)總結(jié)包括初始化、插入、刪除、查找等基本操作，不同存儲(chǔ)結(jié)構(gòu)下的實(shí)現(xiàn)方式有所不同。線性表的基本操作線性表是一種具有n個(gè)數(shù)據(jù)元素的有限序列，具有順序性、元素個(gè)數(shù)有限、元素類型相同等性質(zhì)。線性表的定義和性質(zhì)包括順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種，其中順序存儲(chǔ)結(jié)構(gòu)使用一片連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)則是通過指針鏈接各個(gè)數(shù)據(jù)元素。線性表的存儲(chǔ)結(jié)構(gòu)262024/1/24注意事項(xiàng)二在編寫線性表的操作函數(shù)時(shí)，需要注意函數(shù)的參數(shù)設(shè)置和返回值類型，以及函數(shù)內(nèi)部的處理邏輯和邊界條件的處理。誤區(qū)一認(rèn)為線性表只能采用順序存儲(chǔ)結(jié)構(gòu)，實(shí)際上鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也是線性表的一種重要存儲(chǔ)方式。誤區(qū)二在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，容易忽略頭結(jié)點(diǎn)的設(shè)置，導(dǎo)致程序出現(xiàn)錯(cuò)誤。頭結(jié)點(diǎn)的作用是為了方便插入和刪除操作，同時(shí)可以避免一些特殊情況的處理。注意事項(xiàng)一在使用線性表時(shí)，需要根據(jù)實(shí)際需求選擇合適的存儲(chǔ)結(jié)構(gòu)，并考慮空間和時(shí)間復(fù)雜度的問題。常見誤區(qū)及注意事項(xiàng)272024/1/24樹形結(jié)構(gòu)是一種非線性結(jié)構(gòu)，由節(jié)點(diǎn)和邊組成，具有層次關(guān)系和分支結(jié)構(gòu)。常見的樹形結(jié)構(gòu)包括二叉樹、多叉樹、森林等。樹形結(jié)構(gòu)圖形結(jié)構(gòu)是一種比樹形結(jié)構(gòu)