數(shù)據(jù)結(jié)構(gòu)(線性表)總結(jié)課件-2024鮮版

數(shù)據(jù)結(jié)構(gòu)(線性表)總結(jié)課件2024/3/281CATALOGUE目錄線性表基本概念與特點(diǎn)順序存儲(chǔ)結(jié)構(gòu)——數(shù)組鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——鏈表線性表應(yīng)用舉例與問題分析線性表性能評(píng)價(jià)與改進(jìn)策略總結(jié)回顧與拓展延伸2024/3/28201線性表基本概念與特點(diǎn)2024/3/283由n（n>=0）個(gè)具有相同類型的數(shù)據(jù)元素（結(jié)點(diǎn)）a1，a2，...，an組成的有序序列。線性表定義每個(gè)元素都是數(shù)據(jù)元素，類型相同。均勻性元素間存在嚴(yán)格的順序關(guān)系，即存在前驅(qū)和后繼關(guān)系。有序性線性表定義及性質(zhì)2024/3/284線性表基本操作插入操作查找操作在指定位置插入一個(gè)元素。查找指定元素的位置。初始化操作刪除操作遍歷操作建立一個(gè)空的線性表。刪除指定位置的元素。訪問線性表中的每個(gè)元素。2024/3/285線性表存儲(chǔ)結(jié)構(gòu)類型順序存儲(chǔ)結(jié)構(gòu)用一段連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素，邏輯上相鄰的元素在物理位置上也相鄰。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，邏輯上相鄰的元素在物理位置上不一定相鄰，通過指針鏈接表示元素間的邏輯關(guān)系。索引存儲(chǔ)結(jié)構(gòu)除建立存儲(chǔ)數(shù)據(jù)元素的信息外，還建立附加的索引表來(lái)標(biāo)識(shí)元素的地址。散列存儲(chǔ)結(jié)構(gòu)根據(jù)元素的關(guān)鍵字直接計(jì)算出該元素的存儲(chǔ)地址，又稱哈希存儲(chǔ)。2024/3/28602順序存儲(chǔ)結(jié)構(gòu)——數(shù)組2024/3/287數(shù)組是一種線性表數(shù)據(jù)結(jié)構(gòu)，用一組連續(xù)的內(nèi)存空間來(lái)存儲(chǔ)具有相同類型的數(shù)據(jù)元素。數(shù)組中的元素按照下標(biāo)進(jìn)行訪問，下標(biāo)從0開始，最大下標(biāo)為數(shù)組長(zhǎng)度減1。數(shù)組是一種隨機(jī)存取結(jié)構(gòu)，即可以在O(1)時(shí)間復(fù)雜度內(nèi)訪問任意位置的元素。數(shù)組定義及特點(diǎn)2024/3/288數(shù)組基本操作實(shí)現(xiàn)初始化數(shù)組為數(shù)組分配一塊連續(xù)的內(nèi)存空間，并確定數(shù)組的大小和數(shù)據(jù)類型。訪問數(shù)組元素通過下標(biāo)訪問數(shù)組中的元素，時(shí)間復(fù)雜度為O(1)。插入元素在數(shù)組的指定位置插入一個(gè)元素，需要將插入位置及其后面的元素依次后移，時(shí)間復(fù)雜度為O(n)。刪除元素刪除數(shù)組中的指定元素，需要將刪除位置及其后面的元素依次前移，時(shí)間復(fù)雜度為O(n)。2024/3/289可以通過下標(biāo)直接訪問任意位置的元素，時(shí)間復(fù)雜度為O(1)。隨機(jī)存取數(shù)組中的元素緊密排列，沒有額外的空間浪費(fèi)?？臻g利用率高順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)分析2024/3/2810無(wú)需額外操作：相對(duì)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，順序存儲(chǔ)結(jié)構(gòu)不需要額外的指針或引用操作。順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)分析2024/3/281103不利于數(shù)據(jù)的動(dòng)態(tài)變化對(duì)于經(jīng)常進(jìn)行插入和刪除操作的數(shù)據(jù)，使用數(shù)組作為存儲(chǔ)結(jié)構(gòu)可能不是最優(yōu)選擇。01插入和刪除操作效率低需要移動(dòng)大量元素來(lái)保證數(shù)組的連續(xù)性。02空間大小固定數(shù)組的大小在創(chuàng)建時(shí)就已經(jīng)確定，無(wú)法動(dòng)態(tài)擴(kuò)展。順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)分析2024/3/281203鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——鏈表2024/3/2813123鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（每一個(gè)結(jié)點(diǎn)包含數(shù)據(jù)域和指針域）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。鏈表的特點(diǎn)是插入和刪除操作靈活，不需要移動(dòng)大量元素，但查找操作相對(duì)較慢，需要從頭結(jié)點(diǎn)開始遍歷。鏈表定義及特點(diǎn)2024/3/2814每個(gè)結(jié)點(diǎn)只包含一個(gè)指向后繼結(jié)點(diǎn)的指針，從頭結(jié)點(diǎn)開始，順著指針可以遍歷整個(gè)鏈表。單鏈表雙向鏈表循環(huán)鏈表每個(gè)結(jié)點(diǎn)包含兩個(gè)指針，一個(gè)指向前驅(qū)結(jié)點(diǎn)，一個(gè)指向后繼結(jié)點(diǎn)，可以方便地進(jìn)行雙向遍歷。尾結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)或某個(gè)中間結(jié)點(diǎn)，形成一個(gè)環(huán)狀的鏈表結(jié)構(gòu)。030201單鏈表、雙向鏈表和循環(huán)鏈表2024/3/2815鏈表的遍歷從頭結(jié)點(diǎn)開始，順著指針依次訪問每個(gè)結(jié)點(diǎn)，直到尾結(jié)點(diǎn)。鏈表的創(chuàng)建通過動(dòng)態(tài)內(nèi)存分配函數(shù)（如malloc或new）為每個(gè)數(shù)據(jù)元素分配存儲(chǔ)空間，并建立相應(yīng)的指針鏈接關(guān)系。鏈表的插入在指定位置插入一個(gè)新結(jié)點(diǎn)，需要修改相鄰結(jié)點(diǎn)的指針鏈接關(guān)系。鏈表的查找從頭結(jié)點(diǎn)開始遍歷鏈表，比較每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域與查找值，直到找到目標(biāo)結(jié)點(diǎn)或遍歷完整個(gè)鏈表。鏈表的刪除刪除指定位置的結(jié)點(diǎn)，需要修改相鄰結(jié)點(diǎn)的指針鏈接關(guān)系，并釋放被刪除結(jié)點(diǎn)的存儲(chǔ)空間。鏈表基本操作實(shí)現(xiàn)2024/3/281604線性表應(yīng)用舉例與問題分析2024/3/2817使用線性表來(lái)表示多項(xiàng)式，每個(gè)元素代表多項(xiàng)式中的一項(xiàng)，包含系數(shù)和指數(shù)兩個(gè)屬性。多項(xiàng)式表示將兩個(gè)多項(xiàng)式線性表中的元素按照指數(shù)進(jìn)行排序，然后依次相加得到新的線性表，即為相加后的多項(xiàng)式。多項(xiàng)式相加將兩個(gè)多項(xiàng)式線性表中的元素兩兩相乘，得到一系列新的項(xiàng)，然后按照指數(shù)進(jìn)行排序并合并同類項(xiàng)，得到相乘后的多項(xiàng)式。多項(xiàng)式相乘多項(xiàng)式表示與運(yùn)算問題2024/3/2818問題描述給定兩個(gè)一元多項(xiàng)式，求它們的和。解決方案使用線性表來(lái)表示一元多項(xiàng)式，每個(gè)元素代表多項(xiàng)式中的一項(xiàng)，包含系數(shù)和指數(shù)兩個(gè)屬性。將兩個(gè)多項(xiàng)式的線性表進(jìn)行合并，并按照指數(shù)進(jìn)行排序，得到相加后的多項(xiàng)式。注意事項(xiàng)在合并過程中，需要注意處理同類項(xiàng)的合并問題。一元多項(xiàng)式相加問題2024/3/2819稀疏矩陣的壓縮存儲(chǔ)01稀疏矩陣中大量元素為零，可以使用線性表來(lái)存儲(chǔ)非零元素及其位置信息，從而節(jié)省存儲(chǔ)空間并提高計(jì)算效率。圖書信息管理02使用線性表來(lái)存儲(chǔ)圖書信息，每個(gè)元素代表一本圖書，包含書名、作者、出版日期等屬性。可以方便地進(jìn)行圖書信息的增刪改查操作。學(xué)生成績(jī)管理03使用線性表來(lái)存儲(chǔ)學(xué)生成績(jī)信息，每個(gè)元素代表一個(gè)學(xué)生的成績(jī)記錄，包含學(xué)號(hào)、姓名、各科成績(jī)等屬性?？梢苑奖愕剡M(jìn)行學(xué)生成績(jī)的錄入、查詢、排序等操作。其他應(yīng)用案例探討2024/3/282005線性表性能評(píng)價(jià)與改進(jìn)策略2024/3/2821刪除操作刪除指定位置的元素，需要移動(dòng)刪除位置之后的元素，時(shí)間復(fù)雜度為O(n)。查找操作順序查找的時(shí)間復(fù)雜度為O(n)，二分查找的時(shí)間復(fù)雜度為O(logn)（針對(duì)有序線性表）。插入操作在已知位置插入一個(gè)元素，需要移動(dòng)插入位置及之后的元素，時(shí)間復(fù)雜度為O(n)。時(shí)間復(fù)雜度分析2024/3/2822預(yù)分配固定大小的數(shù)組空間，空間復(fù)雜度為O(1)。根據(jù)實(shí)際需求動(dòng)態(tài)分配數(shù)組空間，空間復(fù)雜度與元素個(gè)數(shù)成正比，即O(n)?？臻g復(fù)雜度分析動(dòng)態(tài)分配靜態(tài)分配2024/3/2823針對(duì)具體應(yīng)用場(chǎng)景，選擇最合適的數(shù)據(jù)結(jié)構(gòu)，如數(shù)組、鏈表等。選擇合適的數(shù)據(jù)結(jié)構(gòu)通過改進(jìn)算法，減少不必要的元素移動(dòng)或比較操作，提高效率。減少不必要的操作通過增加輔助空間，減少時(shí)間復(fù)雜度，如使用哈希表進(jìn)行查找。利用空間換時(shí)間針對(duì)大規(guī)模數(shù)據(jù)，可以采用并發(fā)處理的方式，提高處理速度。并發(fā)處理算法優(yōu)化思路及技巧2024/3/282406總結(jié)回顧與拓展延伸2024/3/2825線性表的定義和性質(zhì)線性表是一種具有n個(gè)數(shù)據(jù)元素的有限序列，具有順序性、元素個(gè)數(shù)有限、元素具有相同數(shù)據(jù)類型等性質(zhì)。線性表的存儲(chǔ)結(jié)構(gòu)包括順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種，其中順序存儲(chǔ)結(jié)構(gòu)通過數(shù)組實(shí)現(xiàn)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通過鏈表實(shí)現(xiàn)。線性表的基本操作包括初始化、插入、刪除、查找等基本操作，不同存儲(chǔ)結(jié)構(gòu)下的實(shí)現(xiàn)方式有所不同。關(guān)鍵知識(shí)點(diǎn)總結(jié)回顧2024/3/2826常見誤區(qū)及注意事項(xiàng)提醒誤區(qū)一認(rèn)為線性表只能采用數(shù)組或鏈表實(shí)現(xiàn)。實(shí)際上，線性表的存儲(chǔ)結(jié)構(gòu)有多種，如靜態(tài)數(shù)組、動(dòng)態(tài)數(shù)組、單向鏈表、雙向鏈表、循環(huán)鏈表等。注意事項(xiàng)一在使用鏈表作為線性表存儲(chǔ)結(jié)構(gòu)時(shí)，需要注意內(nèi)存的申請(qǐng)和釋放，避免內(nèi)存泄漏。誤區(qū)二忽視線性表操作的復(fù)雜性。不同存儲(chǔ)結(jié)構(gòu)下的線性表操作復(fù)雜性不同，需要根據(jù)實(shí)際需求選擇合適的存儲(chǔ)結(jié)構(gòu)。注意事項(xiàng)二在進(jìn)行線性表操作時(shí)，需要考慮邊界條件和異常情況的處理，保證程序的健壯性。2024/3/2827樹形結(jié)構(gòu)是一種非線性數(shù)據(jù)結(jié)構(gòu)，由節(jié)點(diǎn)和邊組成，具有層次性和遞歸性。常見的樹形結(jié)構(gòu)包括二叉樹、多叉樹、森林等。樹形結(jié)構(gòu)圖形結(jié)構(gòu)也是一