數(shù)據(jù)結(jié)構(gòu)名詞解釋(個(gè)人備考時(shí)結(jié)合群里那個(gè)文檔和王道書自己摘錄的-僅供參考)

1、數(shù)據(jù)結(jié)構(gòu)：一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和 操作等的學(xué)科。數(shù)據(jù)：數(shù)據(jù)是信息的載體，是描述客觀事物屬性的數(shù)、 字符以及所有能輸入到計(jì)算機(jī)中并被 計(jì)算機(jī)程序處理的符號(hào)的集合。數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)類型：是一個(gè)值的集合和定義在此集合上一組操作的總稱。包括原子類型：其值不可在分的數(shù)據(jù)類型結(jié)構(gòu)類型：其值可以在分解為若干成分的數(shù)據(jù)類型抽象數(shù)據(jù)類型：ADT,指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。通常用數(shù)據(jù)對(duì)象、 數(shù)據(jù)關(guān)系、基本操作集這樣的三元組來表示。有數(shù)據(jù)抽象和數(shù)據(jù)封裝兩個(gè)重要特性。數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一

2、種或多種特定關(guān)系的數(shù)據(jù)元素的集合。包括（邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算）。數(shù)據(jù)的邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的邏輯關(guān)系。包括集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu) 或網(wǎng)狀結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，也成物理結(jié)構(gòu)。主要有順序存儲(chǔ)、連接存儲(chǔ)、索引存儲(chǔ)、散列存儲(chǔ)。數(shù)據(jù)的運(yùn)算：施加在數(shù)據(jù)上的運(yùn)算包括運(yùn)算的定義和實(shí)現(xiàn)。定義是針對(duì)邏輯結(jié)構(gòu)， 指出運(yùn)算的功能。實(shí)現(xiàn)是針對(duì)存儲(chǔ)結(jié)構(gòu)的，指出運(yùn)算的具體操作步驟。算法：對(duì)特定問題求解步驟的一種描述，是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。有5個(gè)重要特性（有窮性、確定性、可行性、輸入、輸出） 算法設(shè)計(jì)的要求：正確性、可讀性、健壯性、效率與低存

3、儲(chǔ)量需求。時(shí)間復(fù)雜度：一般情況下，算法中基本操作的重復(fù)次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f（n），算法的時(shí)間度量記作 T （n） =O（f（n）,表示隨著問題規(guī)模 n的增大，算法執(zhí)行時(shí)間增長(zhǎng)率 和f （n）的增長(zhǎng)率相同，稱為時(shí)間復(fù)雜度?？臻g復(fù)雜度：S（n）定義為該算法所耗費(fèi)的村粗空間，是問題規(guī)模n的函數(shù)。第二章：線性表線性表：具有相同數(shù)據(jù)類型的 n （n=0）個(gè)數(shù)據(jù)元素的有限序列。線性表的順序存儲(chǔ)又稱 順序表；鏈?zhǔn)酱鎯?chǔ)又稱 單鏈表。靜態(tài)鏈表：借助數(shù)組來描述線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，結(jié)點(diǎn)也有數(shù)據(jù)域和指針域。但指針是結(jié)點(diǎn)的相對(duì)地址（數(shù)組下標(biāo)）。需要預(yù)先分配連續(xù)的內(nèi)存空間。棧：限定在表尾進(jìn)行插入或刪除操作的線性

4、表。操作端稱為棧頂，后進(jìn)先出隊(duì)列：一種先進(jìn)先出的線性表， 只允許在表的一段插入元素，另一端刪除元素，在隊(duì)列中允許插入的一端為隊(duì)尾，允許刪除的一端為隊(duì)頭。串：由零個(gè)或者多個(gè)字符組成的有限序列。串中任意個(gè)連續(xù)的字符組成的子序列稱為該串的子串。字符在序列中的序號(hào)為該字符的位置。樹的結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)元素以及若干指向其子樹的分支。結(jié)點(diǎn)擁有的子樹稱為結(jié)點(diǎn)的 度。度為0的結(jié)點(diǎn)稱為葉子或終端結(jié)點(diǎn)。樹的度是樹內(nèi)個(gè)結(jié)點(diǎn)的度的最大值。 結(jié)點(diǎn)的子樹的根稱為 該結(jié)點(diǎn)的孩子，相應(yīng)的該節(jié)點(diǎn)為孩子的 雙親。同一個(gè)雙親的孩子之間互稱 兄弟。結(jié)點(diǎn)的祖先 是從根到該結(jié)點(diǎn)的所經(jīng)分支上的所有結(jié)點(diǎn)。反之，以某結(jié)點(diǎn)為根的子樹中任一結(jié)點(diǎn)都稱

5、為該結(jié)點(diǎn)的子孫。結(jié)點(diǎn)的層次：從樹根開始定義，根結(jié)點(diǎn)為第1層，它的子結(jié)點(diǎn)為第 2層，以此類推。樹的高度或深度：樹中結(jié)點(diǎn)的最大層數(shù)。有序樹和無序樹：樹中結(jié)點(diǎn)的子樹從左到右是有次序的，不能交換，叫做有序樹。反之為無 序樹。路徑和路徑長(zhǎng)度：樹中兩個(gè)結(jié)點(diǎn)之間的路徑是由這兩個(gè)結(jié)點(diǎn)之間所經(jīng)過的結(jié)點(diǎn)序列構(gòu)成的。 路徑長(zhǎng)度是路徑上經(jīng)過的邊的個(gè)數(shù)。樹的路徑長(zhǎng)度：樹根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和樹的帶權(quán)路徑長(zhǎng)度（WPL）:樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。哈夫曼樹：在含有N個(gè)帶權(quán)葉子結(jié)點(diǎn)的二叉樹中，其中帶權(quán)路徑長(zhǎng)度（WPL）最小的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹。哈夫曼編碼：一種廣泛應(yīng)用而且非常有效的數(shù)據(jù)壓縮編碼。

6、森林:m （ m=0）棵互不相交的樹的集合。二叉樹：是另一種樹形結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)至多有兩棵子樹，并且，二叉樹的子樹有左右之分， 其次序不能任意顛倒。滿二叉樹：一棵高度為h，并且含有2Ah -1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。即每層都有最多 的結(jié)點(diǎn)，葉子集中在二叉樹的最下一層且除葉子之外的每個(gè)結(jié)點(diǎn)度為2.完全二叉樹：設(shè)一個(gè)高度為h，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與高度為h的滿二叉樹中編號(hào)為 1-n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為完全二叉樹。二叉排序樹：一棵二叉樹或是空二叉樹或是具有以下性質(zhì)的二叉樹：左子樹上所有關(guān)鍵字均小于根結(jié)點(diǎn)的關(guān)鍵字， 右子樹所有結(jié)點(diǎn)關(guān)鍵字大于根結(jié)點(diǎn)的關(guān)鍵字。左子樹和右子樹又各是

7、一棵二叉排序樹。平衡二叉樹：樹上任一結(jié)點(diǎn)的左子樹和右子樹的深度之差不超過1.平衡因子：該結(jié)點(diǎn)的左子樹深度減去它的右子樹深度。二叉樹的遍歷：指按某條搜索路徑訪問樹中的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次且僅被訪問一次。線索二叉樹：若結(jié)點(diǎn)有左（右）子樹，則其Ichild （ rchild ）域指向其左（右）孩子，否則令I(lǐng)child（ rchild）域指向其前驅(qū)（后繼），這種結(jié)點(diǎn)構(gòu)成的二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)稱為 二叉鏈表。其中指向結(jié)點(diǎn)前驅(qū)和后繼的指針叫做線索。加上線索的二叉樹稱為 線索二叉樹。對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫做線索化。判定樹：樹中每個(gè)結(jié)點(diǎn)表示表中的一個(gè)記錄，結(jié)點(diǎn)里

8、的值為該記錄在表中的位置，通常稱這個(gè)查找過程的二叉樹為判定樹。樹的先根遍歷：若樹非空，則先訪問根結(jié)點(diǎn)，再按從左到右的順序遍歷根節(jié)點(diǎn)的每一顆子樹。 其訪問順序與這棵樹對(duì)應(yīng)的二叉樹的線序遍歷順序相同。樹的后跟遍歷：若樹非空，則按從左到右的順序遍歷根結(jié)點(diǎn)的每一棵子樹，之后再訪問根結(jié)點(diǎn)。其訪問順序與其對(duì)應(yīng)的二叉樹的中序遍歷相同。先序遍歷森林：若森林非空，則按如下規(guī)則遍歷：訪問森林第一棵樹的根結(jié)點(diǎn)選序遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林線序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林 中序遍歷森林：若森林非空，則按如下規(guī)則進(jìn)行遍歷：中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林訪問第一棵樹的根結(jié)點(diǎn)中序遍歷除去第一棵樹之后

9、剩余的樹構(gòu)成的森林 圖：由頂點(diǎn)集V和邊集E組成，記作G=（V,E） 有向圖：E為有向邊的有限集合時(shí)，圖G為有向圖無向圖：E為無向邊的有限集合時(shí)，圖G為無向圖簡(jiǎn)單圖：不存在重復(fù)邊，不存在定點(diǎn)到自身的邊稱圖G為簡(jiǎn)單圖。與多重圖相對(duì)完全圖：在無向圖中，若任意兩個(gè)頂點(diǎn)之間都存在邊，則稱該圖為無向完全圖。具有n* （n-1） 12條邊。有向圖中，若任意兩個(gè)頂點(diǎn)之間存在方向相反的兩條弧，稱為有向完全圖，含有n （n-1）條有向邊。連通：若從頂點(diǎn)v到頂點(diǎn)w存在路徑，則v和w是聯(lián)通的。若圖 G中任意兩個(gè)頂點(diǎn)都是聯(lián) 通的，則稱圖G為連通圖，否則非連通圖。無向圖中的極大連通子圖稱為連通分量。在有向圖中，若從V到頂

10、點(diǎn) W和從頂點(diǎn) W到頂點(diǎn)V都存在路徑，則稱兩個(gè)頂點(diǎn)是強(qiáng)連通的， 若圖中任一對(duì)頂點(diǎn)都是強(qiáng)連通的，則稱為強(qiáng)連通圖。有向圖中的極大強(qiáng)連通子圖稱為有向圖的強(qiáng)連通分量。生成樹和生成森林：連通圖的生成樹是包含圖中所有頂點(diǎn)的一個(gè)極小連通子圖。若頂點(diǎn)為n則含有n-1條邊。非連通圖中，連通分量的生成樹構(gòu)成生成森林最小生成樹：一個(gè)帶權(quán)連通無向圖的生成樹中邊的權(quán)值之和最小的那個(gè)叫做此圖的最小生成樹。有向樹：如果一個(gè)有向圖恰有一個(gè)頂點(diǎn)的入度為0,其余頂點(diǎn)的入度為1，則是一棵有向樹。路徑、路徑長(zhǎng)度和回路：頂點(diǎn)V到頂點(diǎn)Q之間的一條路徑是指之間的一個(gè)頂點(diǎn)序列。路徑 的長(zhǎng)度是路徑上邊的數(shù)目。第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑

11、稱為回路或環(huán)。最短路徑：帶權(quán)圖中，從一個(gè)頂點(diǎn)V0到另一個(gè)頂點(diǎn) V1的一條路徑上所經(jīng)過邊的權(quán)值之和定義為該路徑的帶權(quán)路徑長(zhǎng)度，其中最短的那條稱作最短路徑。此路徑的長(zhǎng)度稱為從v到u的距離。圖的遍歷：從圖中某一頂點(diǎn)出發(fā)， 按照某種搜索方法沿著圖中的邊對(duì)圖中所有頂點(diǎn)訪問一次且僅訪問一次。深度優(yōu)先搜索：類似于樹的先序遍歷，假設(shè)從圖中某頂點(diǎn) V出發(fā)，在訪問了 V之后一次從V 的未被訪問的鄰接點(diǎn)出發(fā)做深度優(yōu)先遍歷，知道圖中所有和v有路徑相同的頂點(diǎn)都被訪問到。若圖中還有頂點(diǎn)未訪問， 則另選圖中一個(gè)未曾被方位的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問。廣度優(yōu)先搜索：類似于樹的層次遍歷， 從頂點(diǎn)v出

12、發(fā)，訪問了 V之后依次訪問v的各個(gè)未被 訪問過的鄰接頂點(diǎn)。 再依次訪問它們的鄰接點(diǎn)，并使先被訪問的頂點(diǎn)的的鄰接點(diǎn)先于后訪問的頂點(diǎn)的鄰接點(diǎn)。直到圖中所有已被訪問頂點(diǎn)的鄰接點(diǎn)都被訪問到。如果圖中還有頂點(diǎn)未被訪問，則另選一個(gè)未被訪問的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述過程，直到圖中所有頂點(diǎn)都被訪問。AOV網(wǎng)，用有向無環(huán)圖表示一個(gè)工程，頂點(diǎn)表示活動(dòng)，有向邊 表示Vi必須先于 Vj 進(jìn)行的關(guān)系。則稱為 AOV網(wǎng)。AOE網(wǎng)，在帶權(quán)有向圖中，以頂點(diǎn)表示事件，有向邊表示活動(dòng)，邊上的權(quán)值表示完成該活動(dòng)的開銷（如時(shí)間），則稱這個(gè)網(wǎng)絡(luò)為 AOE網(wǎng)。關(guān)鍵路徑：在AOE網(wǎng)中，路徑長(zhǎng)度最長(zhǎng)的路徑叫做關(guān)鍵路徑，關(guān)鍵路徑上的所有活動(dòng)都

13、是關(guān)鍵活動(dòng)。拓?fù)渑判颍河梢粋€(gè)有向無環(huán)圖的頂點(diǎn)組成的序列， 當(dāng)且僅當(dāng)滿足下列條件， 稱為該圖的一個(gè) 拓?fù)渑判?1,每個(gè)頂點(diǎn)出現(xiàn)且僅出現(xiàn)一次。 2若頂點(diǎn)a在b之前，不存在b到a的路徑。 查找：在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)元素的過程稱為查找。查找表（查找結(jié)構(gòu)）：用于查找的數(shù)據(jù)集合稱為查找表。靜態(tài)查找表：如果一個(gè)查找表的操作僅涉及查詢某個(gè)特定的數(shù)據(jù)元素是否在查找表中和檢索滿足條件的某個(gè)特定的數(shù)據(jù)元素的各種屬性，則稱為靜態(tài)查找表。動(dòng)態(tài)查找表：需要?jiǎng)討B(tài)的插入或刪除的查找表稱為動(dòng)態(tài)查找表。關(guān)鍵字：數(shù)據(jù)元素中唯一標(biāo)識(shí)該元素的某個(gè)數(shù)據(jù)項(xiàng)的值，使用基于關(guān)鍵字的查找， 查找結(jié)果應(yīng)該是唯一的。平均查找長(zhǎng)度（AS

14、L :在查找的過程中，一次查找的長(zhǎng)度指需要比較的關(guān)鍵字次數(shù)，而平均查找長(zhǎng)度則是所有查找過程中進(jìn)行關(guān)鍵字的比較次數(shù)的平均值。折半查找：僅適用于有序的順序表。將給定的值key與表中間位置元素的關(guān)鍵字比較，相等則查找成功返回位置。若不等則縮小查找范圍，重復(fù)查找直到找到或者確定表中沒有需查找 的元素。散列函數(shù)：一個(gè)把查找表中的關(guān)鍵字映射成該關(guān)鍵字對(duì)應(yīng)的地址的函數(shù)，沖突：散列函數(shù)可能會(huì)把兩個(gè)或以上的不同關(guān)鍵字映射到同一地址，這種情況為沖突散列表：是根據(jù)關(guān)鍵字而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。散列表建立了關(guān)鍵字和存儲(chǔ)地址指間的一種直接映射關(guān)系。開放定址法：指的是可存放新表項(xiàng)的空閑地址既向它的同義詞表項(xiàng)開放，又向它

15、的非同義詞表項(xiàng)開放。拉鏈法（鏈地址法）：把所有的同義詞存儲(chǔ)在一個(gè)線性鏈表中，這個(gè)線性鏈表由其散列地址 唯一標(biāo)識(shí)。裝填因子：是哈希表中填入的記錄數(shù)和哈希表的長(zhǎng)度之商，哈希表的平均查找長(zhǎng)度是裝填因子的函數(shù)，不是規(guī)模的函數(shù)。（散列表的查找效率取決于三個(gè)因素：散列函數(shù)/處理沖突的方法和裝填因子）二次聚集：指在處理沖突過程中發(fā)生的兩個(gè)第一個(gè)哈希地址不同的記錄爭(zhēng)奪同一個(gè)后繼哈希 地址的現(xiàn)象。第十章：內(nèi)部排序排序：重新排列表中的元素，使表中的元素滿足按關(guān)鍵字遞增或遞減的過程。算法的穩(wěn)定性：假設(shè)Ri=Rj,且在排序之前 Ri領(lǐng)先于Rj,若在排序后的序列中 Ri仍然領(lǐng)先于 Rj,則稱所用的排序算法是穩(wěn)定的，反之

16、則稱所用的算法是不穩(wěn)定的。內(nèi)部排序：排序期間元素全部存放在內(nèi)存中的排序；外部排序是指在排序期間元素?zé)o法全部同時(shí)存放在內(nèi)存中，必須在排序的過程中根據(jù)要求不斷的在內(nèi)外存指間移動(dòng)的排序。插入排序：每次將一個(gè)待排序的記錄，按關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中，直至全部記錄插入完成。希爾排序：又稱縮小增量排序，先將整個(gè)記錄序列分割成若干子序列分別進(jìn)行直接插入排序， 待整個(gè)序列中記錄基本有序時(shí)，再對(duì)全體進(jìn)行一次直接插入排序。冒泡排序：從前往后（或從后往前）兩兩比較相鄰元素的值，若為逆序則交換，知道序列比 較完，既完成一趟冒泡排序。這一趟確定的最小元素不再參與比較，重復(fù)上述過程直到一趟排序沒有記錄交換。快速排序：通過一趟排序?qū)庞涗浄指畛瑟?dú)立兩部分，其中一部分的關(guān)鍵字均比另一部分小，分別對(duì)兩部分再進(jìn)行快速排序直至整個(gè)序列有序選擇排序：每一趟在未排序的記錄中選擇最小的記錄作為有序序列部分的下一個(gè)記錄。歸并排序：將兩個(gè)或兩