高校數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)資料數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)相關(guān)專業(yè)的核心基礎(chǔ)課程，其重要性不言而喻。它不僅是后續(xù)專業(yè)課程的基石，更是培養(yǎng)邏輯思維與問(wèn)題解決能力的關(guān)鍵。期末考試臨近，這份復(fù)習(xí)資料旨在幫助同學(xué)們梳理核心知識(shí)點(diǎn)，鞏固重點(diǎn)內(nèi)容，提升應(yīng)試能力。請(qǐng)務(wù)必結(jié)合教材、課堂筆記及個(gè)人實(shí)踐進(jìn)行系統(tǒng)復(fù)習(xí)。一、緒論1.1數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。*數(shù)據(jù)(Data):對(duì)客觀事物的符號(hào)表示，能被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。*數(shù)據(jù)元素(DataElement):數(shù)據(jù)的基本單位，通常作為一個(gè)整體進(jìn)行考慮和處理。*數(shù)據(jù)項(xiàng)(DataItem):構(gòu)成數(shù)據(jù)元素的不可分割的最小單位，是數(shù)據(jù)元素的屬性。*數(shù)據(jù)對(duì)象(DataObject):性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。*數(shù)據(jù)結(jié)構(gòu)(DataStructure):相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。它包括數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）。1.2邏輯結(jié)構(gòu)與物理結(jié)構(gòu)*邏輯結(jié)構(gòu):指數(shù)據(jù)元素之間的邏輯關(guān)系，是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型。主要分為：*集合結(jié)構(gòu):數(shù)據(jù)元素間除“同屬一個(gè)集合”外，無(wú)其他關(guān)系。*線性結(jié)構(gòu):數(shù)據(jù)元素間存在一對(duì)一的線性關(guān)系。（如：線性表、棧、隊(duì)列）*樹形結(jié)構(gòu):數(shù)據(jù)元素間存在一對(duì)多的層次關(guān)系。（如：樹）*圖狀結(jié)構(gòu)/網(wǎng)狀結(jié)構(gòu):數(shù)據(jù)元素間存在多對(duì)多的任意關(guān)系。（如圖）*物理結(jié)構(gòu)(存儲(chǔ)結(jié)構(gòu)):指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)表示。主要分為：*順序存儲(chǔ)結(jié)構(gòu):借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素間的邏輯關(guān)系。（如：數(shù)組）*鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):借助指示元素存儲(chǔ)地址的指針來(lái)表示數(shù)據(jù)元素間的邏輯關(guān)系。（如：鏈表）*此外還有索引存儲(chǔ)、散列存儲(chǔ)等。1.3數(shù)據(jù)的運(yùn)算施加于數(shù)據(jù)上的操作，包括插入、刪除、修改、查找、排序等。運(yùn)算的實(shí)現(xiàn)依賴于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。1.4算法與算法分析*算法(Algorithm):對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。*算法的特性:有窮性、確定性、可行性、輸入、輸出。*算法設(shè)計(jì)的要求:正確性、可讀性、健壯性、高效率與低存儲(chǔ)量需求。*算法效率的度量:二、線性表2.1線性表的定義與基本操作線性表是具有相同特性的數(shù)據(jù)元素的一個(gè)有限序列，數(shù)據(jù)元素間存在一對(duì)一的線性關(guān)系?；静僮靼ǎ撼跏蓟?、銷毀、插入、刪除、查找、遍歷、判空等。2.2線性表的順序存儲(chǔ)結(jié)構(gòu)(順序表)*定義:用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。邏輯順序與物理順序一致。*特點(diǎn):隨機(jī)訪問(wèn)（可直接通過(guò)下標(biāo)訪問(wèn)），存儲(chǔ)密度高；但插入和刪除操作需要移動(dòng)大量元素，效率較低。*實(shí)現(xiàn):通常用數(shù)組實(shí)現(xiàn)，需記錄數(shù)組基地址、當(dāng)前長(zhǎng)度和最大容量。*重點(diǎn)操作:*插入:若在第i個(gè)位置插入，需將第i個(gè)及之后的元素后移。平均移動(dòng)次數(shù)為n/2。*刪除:若刪除第i個(gè)位置元素，需將第i+1個(gè)及之后的元素前移。平均移動(dòng)次數(shù)為(n-1)/2。2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(鏈表)*定義:用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，通過(guò)指針（或引用）表示元素間的邏輯關(guān)系。*特點(diǎn):無(wú)需預(yù)先分配固定大小空間，插入刪除只需修改指針，不必移動(dòng)元素；但不能隨機(jī)訪問(wèn)，存儲(chǔ)密度較低（需額外存儲(chǔ)指針）。*常見類型:*單鏈表:每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)域和一個(gè)指向下一節(jié)點(diǎn)的指針域。*雙鏈表:每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)域、一個(gè)指向下一節(jié)點(diǎn)的指針域和一個(gè)指向前一節(jié)點(diǎn)的指針域，可雙向遍歷。*循環(huán)鏈表:表中最后一個(gè)節(jié)點(diǎn)的指針指向頭節(jié)點(diǎn)，形成一個(gè)環(huán)，可從任一節(jié)點(diǎn)出發(fā)遍歷整個(gè)鏈表。*重點(diǎn)操作:*單鏈表的創(chuàng)建:頭插法（逆序）、尾插法（順序）。*單鏈表的插入與刪除:關(guān)鍵在于找到待操作位置的前驅(qū)節(jié)點(diǎn)，并正確修改指針指向。*單鏈表的遍歷與查找。*鏈表的合并等應(yīng)用。2.4順序表與鏈表的比較與選擇根據(jù)實(shí)際應(yīng)用中對(duì)操作效率（查找、插入、刪除）、存儲(chǔ)空間、數(shù)據(jù)規(guī)模可預(yù)測(cè)性等方面的需求進(jìn)行選擇。三、棧與隊(duì)列3.1棧(Stack)*定義:限定僅在表尾進(jìn)行插入和刪除操作的線性表。表尾稱為棧頂(Top)，表頭稱為棧底(Bottom)。*特性:后進(jìn)先出(LIFO-LastInFirstOut)。*基本操作:初始化、判空、入棧(Push)、出棧(Pop)、取棧頂元素(GetTop)。*存儲(chǔ)結(jié)構(gòu):*順序棧:用數(shù)組實(shí)現(xiàn)，需設(shè)置棧頂指針。注意棧滿和?？盏呐袛?。*鏈棧:用單鏈表實(shí)現(xiàn)，通常以頭節(jié)點(diǎn)作為棧頂，操作方便。*應(yīng)用:表達(dá)式求值（中綴轉(zhuǎn)后綴、后綴表達(dá)式求值）、函數(shù)調(diào)用與遞歸實(shí)現(xiàn)、括號(hào)匹配、迷宮求解等。3.2隊(duì)列(Queue)*定義:限定僅在表尾進(jìn)行插入，在表頭進(jìn)行刪除操作的線性表。表尾稱為隊(duì)尾(Rear)，表頭稱為隊(duì)頭(Front)。*特性:先進(jìn)先出(FIFO-FirstInFirstOut)。*基本操作:初始化、判空、入隊(duì)(Enqueue)、出隊(duì)(Dequeue)、取隊(duì)頭元素(GetHead)。*存儲(chǔ)結(jié)構(gòu):*順序隊(duì)列:用數(shù)組實(shí)現(xiàn)。為解決“假溢出”問(wèn)題，通常采用循環(huán)隊(duì)列。需注意隊(duì)空和隊(duì)滿的判斷條件（常用少用一個(gè)元素空間或增設(shè)計(jì)數(shù)變量/標(biāo)志位的方法）。*鏈隊(duì)列:用單鏈表實(shí)現(xiàn)，設(shè)置隊(duì)頭指針和隊(duì)尾指針。*應(yīng)用:緩沖處理、層次遍歷（樹、圖）、調(diào)度算法等。*特殊隊(duì)列:雙端隊(duì)列(Deque)、優(yōu)先級(jí)隊(duì)列。四、串4.1串的定義與基本操作串(String)是由零個(gè)或多個(gè)字符組成的有限序列，又名字符串。基本操作包括：賦值、比較、連接、求子串、查找子串位置（模式匹配）、替換等。4.2串的存儲(chǔ)結(jié)構(gòu)定長(zhǎng)順序存儲(chǔ)、堆分配存儲(chǔ)、塊鏈存儲(chǔ)。4.3串的模式匹配算法*簡(jiǎn)單模式匹配算法(BF算法):從主串的每一個(gè)字符開始，依次與模式串的字符比較。最壞時(shí)間復(fù)雜度較高。*KMP算法:核心思想是利用已經(jīng)匹配的部分結(jié)果，避免主串指針的回溯，從而提高效率。關(guān)鍵在于計(jì)算模式串的部分匹配值(PM值)或失效函數(shù)(next數(shù)組)。理解next數(shù)組的含義及計(jì)算方法是掌握KMP算法的關(guān)鍵。五、樹與二叉樹5.1樹的基本概念*樹(Tree):n(n≥0)個(gè)節(jié)點(diǎn)的有限集。n=0時(shí)為空樹；n>0時(shí)，有且僅有一個(gè)特定的稱為根(Root)的節(jié)點(diǎn)，其余節(jié)點(diǎn)可分為m(m≥0)個(gè)互不相交的有限集，每個(gè)集合又是一棵樹，稱為根的子樹(Subtree)。*基本術(shù)語(yǔ):節(jié)點(diǎn)的度、樹的度、葉子節(jié)點(diǎn)、分支節(jié)點(diǎn)、孩子、雙親、兄弟、祖先、子孫、層次、深度（高度）、森林等。5.2二叉樹(BinaryTree)*定義:每個(gè)節(jié)點(diǎn)至多有兩棵子樹，且左右子樹有次序之分（左子樹、右子樹）。*特殊二叉樹:滿二叉樹、完全二叉樹、線索二叉樹。*二叉樹的性質(zhì):*性質(zhì)1:在第i層上至多有2^(i-1)個(gè)節(jié)點(diǎn)。*性質(zhì)2:深度為k的二叉樹至多有2^k-1個(gè)節(jié)點(diǎn)。*性質(zhì)3:對(duì)任何一棵二叉樹，若葉子節(jié)點(diǎn)數(shù)為n0，度為2的節(jié)點(diǎn)數(shù)為n2，則n0=n2+1。*完全二叉樹的性質(zhì)：具有n個(gè)節(jié)點(diǎn)的完全二叉樹的深度為floor(log2n)+1。節(jié)點(diǎn)編號(hào)的父子關(guān)系。*二叉樹的存儲(chǔ)結(jié)構(gòu):*順序存儲(chǔ)結(jié)構(gòu):適用于完全二叉樹。*鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(二叉鏈表):每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)域、左孩子指針域、右孩子指針域。5.3二叉樹的遍歷按一定規(guī)律訪問(wèn)樹中的每個(gè)節(jié)點(diǎn)，且每個(gè)節(jié)點(diǎn)僅被訪問(wèn)一次。這是樹結(jié)構(gòu)中最基本、最重要的操作。*深度優(yōu)先遍歷:*先序遍歷(DLR):根節(jié)點(diǎn)->左子樹->右子樹*中序遍歷(LDR):左子樹->根節(jié)點(diǎn)->右子樹*后序遍歷(LRD):左子樹->右子樹->根節(jié)點(diǎn)*廣度優(yōu)先遍歷(層次遍歷):從根節(jié)點(diǎn)開始，按層次依次訪問(wèn)各層節(jié)點(diǎn)。通常借助隊(duì)列實(shí)現(xiàn)。*遍歷序列的還原:已知中序遍歷序列和先序/后序遍歷序列，可以唯一確定一棵二叉樹。5.4線索二叉樹為充分利用二叉鏈表中閑置的空指針域（n個(gè)節(jié)點(diǎn)的二叉鏈表有n+1個(gè)空指針），將空的左指針指向其前驅(qū)，空的右指針指向其后繼，這種加上線索的二叉樹稱為線索二叉樹。目的是加快遍歷速度和方便查找前驅(qū)后繼。5.5樹、森林與二叉樹的轉(zhuǎn)換樹和森林都可以轉(zhuǎn)換為唯一對(duì)應(yīng)的二叉樹，轉(zhuǎn)換后便于利用二叉樹的算法進(jìn)行處理。*森林轉(zhuǎn)二叉樹:各棵樹分別轉(zhuǎn)二叉樹，然后依次將后一棵二叉樹作為前一棵二叉樹的右子樹。*二叉樹轉(zhuǎn)樹/森林:根據(jù)左孩子右兄弟的原則進(jìn)行還原。5.6哈夫曼樹(最優(yōu)二叉樹)與哈夫曼編碼*哈夫曼樹:給定n個(gè)權(quán)值作為n個(gè)葉子節(jié)點(diǎn)，構(gòu)造一棵二叉樹，使得帶權(quán)路徑長(zhǎng)度(WPL)最小。*哈夫曼算法:核心是每次選擇權(quán)值最小的兩棵樹合并。*哈夫曼編碼:利用哈夫曼樹構(gòu)造的不等長(zhǎng)編碼，可實(shí)現(xiàn)數(shù)據(jù)的無(wú)損壓縮，且保證無(wú)歧義（前綴編碼特性）。六、圖6.1圖的基本概念*圖(Graph):由頂點(diǎn)集V和邊集E組成。*基本術(shù)語(yǔ):頂點(diǎn)、邊、有向圖、無(wú)向圖、?。ㄓ邢蜻叄?、頂點(diǎn)的度（入度、出度）、完全圖、稠密圖、稀疏圖、子圖、路徑、路徑長(zhǎng)度、回路（環(huán)）、簡(jiǎn)單路徑、簡(jiǎn)單回路、連通圖（強(qiáng)連通圖）、連通分量（強(qiáng)連通分量）、生成樹、權(quán)、網(wǎng)等。6.2圖的存儲(chǔ)結(jié)構(gòu)*鄰接矩陣(AdjacencyMatrix):用一個(gè)二維數(shù)組表示頂點(diǎn)間的相鄰關(guān)系。易于實(shí)現(xiàn)，但空間復(fù)雜度較高，適用于稠密圖。*鄰接表(AdjacencyList):對(duì)每個(gè)頂點(diǎn)建立一個(gè)單鏈表，存儲(chǔ)其所有鄰接頂點(diǎn)?？臻g效率高，適用于稀疏圖。*此外還有：十字鏈表（有向圖）、鄰接多重表（無(wú)向圖）。6.3圖的遍歷從圖中某一頂點(diǎn)出發(fā)，按某種方式訪問(wèn)圖中所有頂點(diǎn)，且每個(gè)頂點(diǎn)僅被訪問(wèn)一次。*深度優(yōu)先搜索(DFS):類似樹的先序遍歷，盡可能深地搜索。通常用遞歸或棧實(shí)現(xiàn)。*廣度優(yōu)先搜索(BFS):類似樹的層次遍歷，按層次訪問(wèn)。通常用隊(duì)列實(shí)現(xiàn)。*遍歷過(guò)程中可得到生成樹（或生成森林）。6.4最小生成樹(MinimumSpanningTree-MST)*定義:在連通網(wǎng)中，所有生成樹中權(quán)值之和最小的生成樹。*構(gòu)造算法:*Prim算法:從一個(gè)頂點(diǎn)開始，逐步添加邊，每次選擇權(quán)值最小的且能連接新頂點(diǎn)的邊。適用于稠密圖。*Kruskal算法:按邊的權(quán)值從小到大排序，依次選擇不構(gòu)成回路的邊加入。適用于稀疏圖，通常需借助并查集(Union-Find)數(shù)據(jù)結(jié)構(gòu)判斷是否構(gòu)成回路。6.5最短路徑*從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑:*Dijkstra算法:按路徑長(zhǎng)度遞增的次序產(chǎn)生最短路徑。要求邊的權(quán)值非負(fù)。*每對(duì)頂點(diǎn)之間的最短路徑:*Floyd算法:基于動(dòng)態(tài)規(guī)劃思想，通過(guò)中間頂點(diǎn)逐步更新距離矩陣?？梢蕴幚韼ж?fù)權(quán)邊的圖，但不能有負(fù)權(quán)回路。6.6拓?fù)渑判蜥槍?duì)有向無(wú)環(huán)圖(DAG)，將所有頂點(diǎn)排成一個(gè)線性序列，使得對(duì)圖中任意一條有向邊(u,v)，在序列中u都出現(xiàn)在v之前。常用于判斷圖中是否存在環(huán)，以及任務(wù)調(diào)度等場(chǎng)景。通常借助入度表和隊(duì)列（或棧）實(shí)現(xiàn)。七、查找7.1查找的基本概念查找表、關(guān)鍵字、平均查找長(zhǎng)度(ASL)。7.2靜態(tài)查找表*順序查找(線性查找):從表的一端開始，依次比較。對(duì)表無(wú)要求，ASL較高。*折半查找(二分查找):要求表中元素按關(guān)鍵字有序，且為順序存儲(chǔ)。每次將待查區(qū)間縮小一半。ASL較低，時(shí)間復(fù)雜度為O(logn)。*分塊查找(索引順序查找):將表分成若干塊，塊內(nèi)無(wú)序，塊間有序。先索引查找確定塊，再塊內(nèi)順序查找。7.3動(dòng)態(tài)查找表*二叉排序樹(BST):左子樹所有節(jié)點(diǎn)關(guān)鍵字<根節(jié)點(diǎn)關(guān)鍵字<右子樹所有節(jié)點(diǎn)關(guān)鍵字。其查找、插入、刪除操作都與樹的形態(tài)有關(guān)。*平衡二叉樹(AVL樹):左右子樹的深度之差（平衡因子）的絕對(duì)值不超過(guò)1。目的是保持樹的平衡，從而保證較高的查找效率。掌握平衡旋轉(zhuǎn)（LL,RR,LR,RL）的方法。*B-樹與B+樹:多路平衡查找樹，常用于文件系統(tǒng)和數(shù)據(jù)庫(kù)索引。7.4哈希表(散列表)*哈希表的概念:根據(jù)關(guān)鍵字直接計(jì)算出該關(guān)鍵字對(duì)應(yīng)的存儲(chǔ)地址，從而實(shí)現(xiàn)快速查找。*哈希函數(shù)(散列函數(shù)):構(gòu)造