數(shù)據(jù)基礎(chǔ)及結(jié)構(gòu) 8

第1章緒論1本章目錄01問(wèn)題導(dǎo)入：數(shù)據(jù)結(jié)構(gòu)無(wú)處不在02基本概念：數(shù)據(jù)結(jié)構(gòu)的三大要素03算法分析：時(shí)間與空間復(fù)雜度04應(yīng)用案例：AI大模型背后的數(shù)據(jù)結(jié)構(gòu)05本章小結(jié)問(wèn)題導(dǎo)入：數(shù)據(jù)結(jié)構(gòu)無(wú)處不在短視頻回退刷抖音時(shí)，順滑的回退體驗(yàn)背后，是數(shù)據(jù)結(jié)構(gòu)對(duì)歷史記錄的高效管理。海量搜索搜索引擎在毫秒級(jí)內(nèi)從海量網(wǎng)頁(yè)中找到結(jié)果，依賴于高效的索引結(jié)構(gòu)。社交推薦分析好友關(guān)系鏈并推薦新朋友，圖結(jié)構(gòu)在這里發(fā)揮了核心作用。精準(zhǔn)推薦電商網(wǎng)站總能猜中你的喜好，背后是復(fù)雜的排序與關(guān)聯(lián)數(shù)據(jù)結(jié)構(gòu)。路徑規(guī)劃無(wú)人駕駛汽車規(guī)劃最佳路徑，需要高效的圖搜索算法支持。核心答案這些看似復(fù)雜的問(wèn)題背后，都隱藏著數(shù)據(jù)結(jié)構(gòu)的智慧。數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的核心課程，是程序設(shè)計(jì)與系統(tǒng)開(kāi)發(fā)的基石，主要研究數(shù)據(jù)的組織、存儲(chǔ)與操作。邏輯結(jié)構(gòu)研究數(shù)據(jù)元素之間的抽象關(guān)系（如集合、線性、樹(shù)形、圖形結(jié)構(gòu)），決定了數(shù)據(jù)的組織方式。存儲(chǔ)結(jié)構(gòu)研究數(shù)據(jù)在計(jì)算機(jī)內(nèi)存中的物理實(shí)現(xiàn)方式（如順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)），是邏輯結(jié)構(gòu)的具體映射。數(shù)據(jù)運(yùn)算定義在數(shù)據(jù)上的操作（如增刪改查、排序、檢索），其效率直接依賴于邏輯與存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì)。數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容邏輯結(jié)構(gòu)集合線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖形結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)索引存儲(chǔ)散列存儲(chǔ)運(yùn)算：插入、刪除、查找、排序、遍歷等數(shù)據(jù)結(jié)構(gòu)基本概念和術(shù)語(yǔ)數(shù)據(jù)(Data)計(jì)算機(jī)處理的符號(hào)總稱，是程序加工的“原料”。例如：數(shù)字、文字、圖像、聲音等。數(shù)據(jù)元素(DataElement)數(shù)據(jù)的基本單位，處理和操作的最小單元。例如：一條學(xué)生記錄、一個(gè)圖的頂點(diǎn)。數(shù)據(jù)項(xiàng)(DataItem)數(shù)據(jù)元素的最小標(biāo)識(shí)單位，不可分割。例如：學(xué)生記錄中的“姓名”、“學(xué)號(hào)”字段。數(shù)據(jù)結(jié)構(gòu)(DataStructure)是指組成數(shù)據(jù)的元素之間的結(jié)構(gòu)關(guān)系，即數(shù)據(jù)的組織形式。它一般包括以下三個(gè)方面的內(nèi)容：（1）數(shù)據(jù)元素之間的邏輯關(guān)系，也稱為數(shù)據(jù)的邏輯結(jié)構(gòu)；（2）數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)內(nèi)的表示，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；（3）數(shù)據(jù)的運(yùn)算，即對(duì)數(shù)據(jù)施加的操作。數(shù)據(jù)的邏輯結(jié)構(gòu)集合結(jié)構(gòu)(SetStructure)元素間除了同屬一個(gè)集合外，無(wú)任何其他關(guān)系，如同一個(gè)袋子里的球。線性結(jié)構(gòu)(LinearStructure)元素間存在一對(duì)一的線性關(guān)系，形成一個(gè)有序序列，如鏈表或數(shù)組。樹(shù)形結(jié)構(gòu)(TreeStructure)元素間存在一對(duì)多的層次關(guān)系，結(jié)構(gòu)像一棵倒置的樹(shù)，如家族族譜。圖形結(jié)構(gòu)(GraphStructure)元素間存在多對(duì)多的任意關(guān)系，是最復(fù)雜的結(jié)構(gòu)，如社交網(wǎng)絡(luò)關(guān)系。邏輯結(jié)構(gòu)示例：集合與線性集合結(jié)構(gòu)示例圖書館里所有的書籍構(gòu)成一個(gè)集合待排序的所有學(xué)生成績(jī)構(gòu)成一個(gè)集合

特點(diǎn)：元素之間無(wú)序，沒(méi)有特定關(guān)系線性結(jié)構(gòu)示例抖音的瀏覽歷史，按時(shí)間順序排列回退操作就是從這個(gè)線性表中取出前一個(gè)元素

特點(diǎn)：元素之間有明確的先后順序邏輯結(jié)構(gòu)示例：樹(shù)形與圖形樹(shù)形結(jié)構(gòu)(TreeStructure)搜索引擎索引(Trie樹(shù))用于快速檢索，利用層級(jí)關(guān)系縮小查找范圍。公司組織架構(gòu)體現(xiàn)上下級(jí)的層次關(guān)系，一個(gè)節(jié)點(diǎn)可指向多個(gè)子節(jié)點(diǎn)。核心特點(diǎn)：呈現(xiàn)一對(duì)多的層級(jí)關(guān)系，結(jié)構(gòu)清晰，路徑唯一。圖形結(jié)構(gòu)(GraphStructure)社交網(wǎng)絡(luò)模型用戶作為節(jié)點(diǎn)，關(guān)注/好友關(guān)系作為邊，關(guān)系錯(cuò)綜復(fù)雜。城市交通路網(wǎng)路口是節(jié)點(diǎn)，道路是邊，用于復(fù)雜的路徑規(guī)劃算法。核心特點(diǎn)：多對(duì)多的任意關(guān)系，非常靈活，能很好地模擬現(xiàn)實(shí)世界。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)1.順序存儲(chǔ)邏輯相鄰的元素，物理地址也相鄰（如數(shù)組）。就像排隊(duì)一樣，位置是連續(xù)的。2.鏈?zhǔn)酱鎯?chǔ)邏輯相鄰的元素，物理地址不一定相鄰，通過(guò)指針連接（如鏈表）。3.索引存儲(chǔ)建立索引表，通過(guò)關(guān)鍵字快速查找元素地址。類似于書的目錄。4.散列存儲(chǔ)通過(guò)哈希函數(shù)直接計(jì)算元素的存儲(chǔ)地址（如哈希表），查找速度極快。

由于數(shù)據(jù)的運(yùn)算也是數(shù)據(jù)結(jié)構(gòu)不可分割的一個(gè)方面，在給定了數(shù)據(jù)的邏輯結(jié)構(gòu)之后，按定義的運(yùn)算集合及其運(yùn)算的性質(zhì)不同，也可能導(dǎo)致完全不同的數(shù)據(jù)結(jié)構(gòu)。

例如，若對(duì)線性表的插入、刪除運(yùn)算限制在表的一端進(jìn)行，則該線性表稱為棧；若對(duì)插入限制在表的一端進(jìn)行，而刪除限制在表的另一端進(jìn)行，則該線性表稱為隊(duì)列。更進(jìn)一步，若線性表采用順序表或鏈表作為存儲(chǔ)結(jié)構(gòu)，則對(duì)插入和刪除運(yùn)算做了上述限制之后，可分別得到順序?；蜴湕?，順序隊(duì)列或鏈隊(duì)列。數(shù)據(jù)的操作實(shí)現(xiàn)數(shù)據(jù)的操作與抽象數(shù)據(jù)類型(ADT)數(shù)據(jù)運(yùn)算定義在邏輯結(jié)構(gòu)上的一組操作（如插入、刪除、查找），其定義與具體的物理實(shí)現(xiàn)無(wú)關(guān)。抽象數(shù)據(jù)類型(ADT)一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作。強(qiáng)調(diào)“做什么”而非“怎么做”。數(shù)據(jù)對(duì)象(D)+數(shù)據(jù)關(guān)系(S)+基本操作(P)數(shù)據(jù)的操作與抽象數(shù)據(jù)類型(ADT)ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定義〉

數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉

基本操作：〈基本操作的定義〉}ADT

抽象數(shù)據(jù)類型名在本書中抽象數(shù)據(jù)類型的定義格式為：基本操作名（參數(shù)表）

初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉其中基本操作定義格式為：抽象數(shù)據(jù)類型舉例：一元多項(xiàng)式的定義ADTComplex{數(shù)據(jù)對(duì)象：

D＝{pi｜pi∈ElemSet，i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系：R1＝{<pi-1,pi>|pi-1,pi∈D,i=2,...,n}基本操作：PolyCreat(p)操作結(jié)果：構(gòu)造一個(gè)多項(xiàng)式p。PolyDestroy(p)操作結(jié)果：多項(xiàng)式p被銷毀。PolyAdd(p1,p2)初始條件：p1,p2已存在。操作結(jié)果：返回p1加p2的結(jié)果。PolyMinus(p1,p2)初始條件：p1,p2已存在。操作結(jié)果：返回p1減p2的結(jié)果。PolyMulti(p1,p2)初始條件：p1,p2已存在。操作結(jié)果：返回p1乘以p2的結(jié)果。}ADTComplex

算法分析：算法的定義與特性什么是算法？算法是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。它代表著用系統(tǒng)的方法描述解決問(wèn)題的策略機(jī)制。有窮性：在有限步驟后必須結(jié)束，不能無(wú)限循環(huán)。確定性：每一步驟的含義明確，無(wú)二義性，相同輸入必有相同輸出。輸入與輸出：有零個(gè)或多個(gè)輸入，至少一個(gè)輸出，且與輸入相關(guān)?？尚行裕好枋龅牟僮骺梢酝ㄟ^(guò)基本運(yùn)算有限次實(shí)現(xiàn)。算法的5個(gè)重要特性：算法分析：算法的定義與特性通常設(shè)計(jì)一個(gè)算法應(yīng)考慮到以下目標(biāo)：（1）正確性：算法應(yīng)當(dāng)能夠正確地求解問(wèn)題。（2）可讀性：算法應(yīng)當(dāng)具有良好的可讀性，便于人們閱讀與理解。（3）健壯性：當(dāng)輸入非法數(shù)據(jù)時(shí)，算法也能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫名其妙的輸出結(jié)果。（4）效率與低存儲(chǔ)量的要求：效率是指算法的運(yùn)行時(shí)間，存儲(chǔ)量要求是指算法運(yùn)行過(guò)程中所需要的最大存儲(chǔ)空間。算法分析：時(shí)間復(fù)雜度算法的執(zhí)行時(shí)間

當(dāng)算法轉(zhuǎn)換為程序之后，每條語(yǔ)句執(zhí)行一次所需的時(shí)間取決于機(jī)器的硬件性能、速度以及編譯所產(chǎn)生的代碼質(zhì)量，這是很難確定的。同時(shí)，給10個(gè)數(shù)據(jù)排序和給10000個(gè)數(shù)據(jù)排序所需要的執(zhí)行時(shí)間肯定是不同的。如何排除這些影響因素呢？

假設(shè)每條語(yǔ)句執(zhí)行一次所需的時(shí)間均是單位時(shí)間。一個(gè)算法的時(shí)間消耗就是該算法中所有語(yǔ)句的頻度之和。于是，我們就可以獨(dú)立于機(jī)器的軟硬件系統(tǒng)來(lái)分析算法的時(shí)間耗費(fèi)。即T（時(shí)間）正比于f（頻度）。

一般地，我們將算法求解問(wèn)題的輸入量稱為問(wèn)題的規(guī)模，并用一個(gè)整數(shù)n表示。算法分析：時(shí)間復(fù)雜度核心定義衡量算法執(zhí)行時(shí)間隨問(wèn)題規(guī)模n增長(zhǎng)的變化趨勢(shì)，關(guān)注的是時(shí)間效率而非具體耗時(shí)。度量與表示統(tǒng)計(jì)基本操作頻度，使用大O表示法T(n)=O(f(n))描述漸近復(fù)雜度。常見(jiàn)階數(shù)O(1)常數(shù)階|O(n)線性階|O(n2)平方階代碼復(fù)雜度示例解析左圖展示了三種典型的代碼結(jié)構(gòu)對(duì)應(yīng)的時(shí)間復(fù)雜度。單層循環(huán)通常對(duì)應(yīng)O(n)，而嵌套循環(huán)往往意味著O(n2)的指數(shù)級(jí)增長(zhǎng)。常見(jiàn)時(shí)間復(fù)雜度對(duì)比復(fù)雜度增長(zhǎng)排序(從快到慢)O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(2?)算法性能評(píng)估高效區(qū)：O(1),O(logn),O(n),O(nlogn)適用于大數(shù)據(jù)量場(chǎng)景。低效區(qū)：O(n2),O(n3)在數(shù)據(jù)量較大時(shí)性能會(huì)顯著下降。避免使用：O(2?)為指數(shù)級(jí)增長(zhǎng)，隨著n增大計(jì)算量將爆炸式上升。復(fù)雜度增長(zhǎng)趨勢(shì)可視化算法分析：空間復(fù)雜度核心定義指算法執(zhí)行過(guò)程中所需存儲(chǔ)空間隨問(wèn)題規(guī)模n增長(zhǎng)的趨勢(shì)，記為S(n)=O(f(n))。分析重點(diǎn)主要關(guān)注算法執(zhí)行時(shí)所需的“輔助存儲(chǔ)空間”，不包含輸入數(shù)據(jù)本身占用的空間。原地工作(In-place)若算法的輔助存儲(chǔ)空間為常數(shù)O(1)，即不隨數(shù)據(jù)規(guī)模增長(zhǎng)，則稱為原地工作。時(shí)空權(quán)衡(Trade-off)在算法設(shè)計(jì)中，我們經(jīng)常需要在時(shí)間效率和空間消耗之間尋找平衡，通?？梢杂每臻g換時(shí)間，或用時(shí)間換空間。應(yīng)用案例：AI大模型背后的數(shù)據(jù)結(jié)構(gòu)核心背景千億參數(shù)模型（如GPT、ViT）的高效運(yùn)行，離不開(kāi)底層數(shù)據(jù)結(jié)構(gòu)的支撐。關(guān)鍵應(yīng)用場(chǎng)景張量：存儲(chǔ)海量權(quán)重參數(shù)，支持并行計(jì)算。哈希表：實(shí)現(xiàn)詞嵌入向量的O(1)快速查找。圖結(jié)構(gòu)：構(gòu)建自注意力矩陣，建模復(fù)雜關(guān)系。樹(shù)結(jié)構(gòu)：管理特征金字塔，加速圖像處理。數(shù)據(jù)結(jié)構(gòu)是連接理論與應(yīng)用的橋梁，是構(gòu)建高性能AI系統(tǒng)的基石。本章小結(jié)數(shù)據(jù)結(jié)構(gòu)三要素邏輯結(jié)構(gòu)：集合、線性