數(shù)據(jù)結(jié)構(gòu)概念總結(jié)(共6頁)

1、數(shù)據(jù)結(jié)構(gòu)(C語言版)第一章：緒論1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等的科學(xué)。2. 數(shù)據(jù)(data)是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有以輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。3. 數(shù)據(jù)元素(data element)是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。4. 數(shù)據(jù)對(duì)象(data object)是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。5. 數(shù)據(jù)結(jié)構(gòu)(data structure)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。6. 根據(jù)數(shù)據(jù)結(jié)構(gòu)之間關(guān)系的不同特性，通常有下列4類基本結(jié)構(gòu):集

2、合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。7. 抽象數(shù)據(jù)類型(ADT)：是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作，有“數(shù)據(jù)抽象”和“數(shù)據(jù)封裝”兩個(gè)重要特性。8. 算法(algorithm)是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作，具有“有窮性”，“確定性”，“可行性”，“輸入”，“輸出”五個(gè)特性。9. 算法設(shè)計(jì)的要求：正確性、可讀性、健壯性、效率與低存儲(chǔ)需求。10. 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n)，算法的時(shí)間量度記作T(n)=O(f(n)，它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率和f(n)的增長率相

3、同，稱做算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。第二章：線性表1. 線性表：是n個(gè)數(shù)據(jù)元素的有限序列，有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種表示形式。2. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，包括兩個(gè)域，其中存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，存儲(chǔ)直接后繼存儲(chǔ)位置的域稱為指針域。3. 循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。4. 雙向鏈表是指有兩個(gè)指針域，其一指向直接后繼，另一指向直接前趨。第三章：棧和隊(duì)列1. 棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表。因此，對(duì)棧來說，表尾端有其特殊含義稱為棧頂，相應(yīng)地，表頭端稱為棧

4、底。棧的修改是按后進(jìn)先出的原則進(jìn)行的，因此又稱后進(jìn)先出表。2. 隊(duì)列是一種先進(jìn)先出的線性表，它只允許在表的一端進(jìn)行插入，而在另一端刪除元素，在隊(duì)列中，允許插入的一端稱做隊(duì)尾，允許刪除的一端稱做隊(duì)頭。第四章：串1. 串(string)是由零個(gè)或多個(gè)字符組成的有限序列。串中任意個(gè)連續(xù)的字符組成的子序列稱該串的子串，通常稱字符在序列中的序號(hào)為該字符在序列中的序號(hào)為該字符的在串中的位置。2. 稱兩個(gè)串是相等的，當(dāng)且僅當(dāng)這兩個(gè)串的值相等。也就是說，只有當(dāng)兩個(gè)串的長度相等，并且各個(gè)對(duì)應(yīng)位置的字符都相等時(shí)才相等。第六章：樹與二叉樹1. 樹(tree)是指n(n>=0)個(gè)結(jié)點(diǎn)的有限集，在任意一棵非空樹中

5、：1）有且僅有一個(gè)特定的稱為根。2）當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集，其中每一個(gè)集合本身又是一棵樹。2. 樹的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支。結(jié)點(diǎn)擁有的子樹稱為結(jié)點(diǎn)的度。度為0的結(jié)點(diǎn)稱為葉子或終端結(jié)點(diǎn)。樹的度是樹內(nèi)各結(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)都稱為該結(jié)點(diǎn)的子孫。3. 結(jié)點(diǎn)的層次從根開始定義起，根為第一層，根的孩子為第二層。若某結(jié)點(diǎn)在第l層，則其子樹在第l+1層。其雙親在同一層的結(jié)點(diǎn)互為

6、堂兄弟。樹中結(jié)點(diǎn)的最大層次稱為樹的深度或高度。4. 如果將樹中結(jié)點(diǎn)的各種子樹看成是從左到右是有次序的，則稱該樹為有序樹，否則稱為無序樹。5. 森林(forest)是m(m>0)棵互不相交的樹的集合。6. 二叉樹（Binary Tree)是另一種樹型結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有兩棵子樹，并且二叉樹的子樹有左右之分，其次序不能任意顛倒。7. 一個(gè)深度為k且有2K-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱之為完全二叉樹。8. 遍歷二叉樹：指按某條搜索路徑巡訪樹上每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一

7、次，而且僅被訪問一次。有先序遍歷、中序遍歷、后序遍歷三種。9. 若結(jié)點(diǎn)有左子樹，則其lchild（rchild）域指向指示其左(右)孩子，否則令lchild（rchild）域指示其前驅(qū)（后繼），這種結(jié)點(diǎn)構(gòu)成的二叉鏈表做為二叉樹的存儲(chǔ)結(jié)構(gòu)稱為線索鏈表。10. 從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑，路徑上的分支數(shù)目稱做路徑長度。樹的路徑長度是從樹根到每一個(gè)結(jié)點(diǎn)的路徑長度之和。樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和。11. 假設(shè)有n個(gè)權(quán)值w1,w2,，wn，試構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子結(jié)點(diǎn)帶樹為wi,則其中帶權(quán)路徑長度WPL最小的二叉樹稱為最優(yōu)二叉

8、樹或赫夫曼樹。第七章：圖1. 在圖中的數(shù)據(jù)元素通常稱做頂點(diǎn)，<v,w>表示從v到w的一條弧，且稱v為弧尾，稱w為弧頭,此時(shí)稱圖為有向圖，若<v,w>表示v和w之間的一條邊，此時(shí)的圖稱為無向圖。2. 有n*(n-1)/2條邊的無向圖稱為完全圖。具有n(n-1)條弧的有向圖稱為有向完全圖，有很少條邊或弧的圖稱為稀疏圖，反之稱為稠密圖。有時(shí)圖的邊或弧具有與它相關(guān)的數(shù)，這種與圖的邊或弧相關(guān)的數(shù)叫做權(quán)，這種帶權(quán)的圖稱為網(wǎng)。3. 頂點(diǎn)v的度是和v相關(guān)聯(lián)的邊的數(shù)目，記為TD(V)。4. 無向圖G=(V,E)中從點(diǎn)v到頂點(diǎn)v的路徑是一個(gè)頂點(diǎn)序列，路徑的長度是路徑上邊或弧的數(shù)目。第一個(gè)頂

9、點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路或環(huán)。序列中不重復(fù)出現(xiàn)的路徑稱為簡(jiǎn)單路徑。除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)之外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路，稱為簡(jiǎn)單回路或簡(jiǎn)單環(huán)。5. 在無向圖G中，如果從頂點(diǎn)v到頂點(diǎn)v有路徑，則稱v和v是連通的。如果對(duì)于圖中任意兩個(gè)頂點(diǎn)vi、vjV,vi和vj都是連通的，則稱G是連通圖。所謂連通分量指的是無向圖中的極大連通子圖。6. 在有向圖G中，如果對(duì)于每一對(duì)vi、vjV, vivj,從vi到vj和從vj到vi都存在路徑，則稱G是強(qiáng)連通圖。有向圖中的極大強(qiáng)連通子圖稱做有向圖的強(qiáng)連通分量。7. 一個(gè)連通圖的生成樹是一個(gè)極小連通子圖，它含有圖中全部頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1

10、條邊。如果在一棵生成樹上添加一條邊，必定構(gòu)成一個(gè)環(huán)。一棵有n個(gè)頂點(diǎn)的生成樹有且僅有n-1條邊。如果一個(gè)圖有n個(gè)頂點(diǎn)和小于n-1條邊，則是非連通圖，如果它多于n-1條邊，則一定有環(huán)。但是，有n-1條邊的圖不一定是生成樹。8. 如果一個(gè)有向圖恰有一個(gè)頂點(diǎn)的入度為0，其余頂點(diǎn)的入度均為1，則是一棵有向樹。一個(gè)有向圖的生成森林由若干棵有向樹組成，含有圖中全部頂點(diǎn)，但只有足以構(gòu)成若干棵不相交的有向樹的弧。9. 圖的存儲(chǔ)結(jié)構(gòu)有鄰接矩陣、鄰接表、逆鄰接表以及十字鏈表等。10. 圖的遍歷：指從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)，且使每一個(gè)頂點(diǎn)僅被訪問一次。11. 通常有兩條遍歷圖的路徑：1） 深度優(yōu)先搜索：類似

11、于樹的先序遍歷，假設(shè)從圖中某頂點(diǎn)v出發(fā)，在訪問了v之后依次從v的未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直到圖中所有和v有路徑相通的頂點(diǎn)都被訪問到。若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)做為起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。2） 廣度優(yōu)先搜索：類似于村的層序遍歷，假設(shè)從圖中某頂點(diǎn)v出發(fā)，在訪問了v之后依次訪問它們的鄰接點(diǎn)，并使先被訪問的頂點(diǎn)的鄰接點(diǎn)先于后訪問的頂點(diǎn)的鄰接點(diǎn)，直到圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述過程，直到圖中所有頂點(diǎn)都被訪問到為止。12. 假若在刪去頂點(diǎn)v以

12、及和v相關(guān)聯(lián)的各邊之后，將圖的一個(gè)連通分量分割成兩個(gè)或兩個(gè)以上的邊通分量，則稱頂點(diǎn)v為該圖的一個(gè)關(guān)節(jié)點(diǎn)。一個(gè)沒有關(guān)節(jié)點(diǎn)的圖稱為重連通圖。若在連通圖上至少刪去k個(gè)頂點(diǎn)才能破壞圖的連通性，則稱此圖的連通度為k。13. 對(duì)于無向圖來說，若深度優(yōu)先搜索過程中遇到回邊，則必定存在環(huán)，而對(duì)于有向圖來說，這條回邊有可能是指向深度優(yōu)先生成森林中另一棵生成樹上頂點(diǎn)的弧。14. 拓?fù)渑判?Topological Sort)：指由某個(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序。15. AOV-網(wǎng)：指用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間的優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)。16. AOE-網(wǎng)：指用邊表示活動(dòng)的網(wǎng)，是一個(gè)帶權(quán)的

13、有向無環(huán)圖，其中，頂點(diǎn)表示事件弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)的時(shí)間，通常一個(gè)AOE-網(wǎng)可用來估算工程的完成時(shí)間。17. 在正常的情況（無環(huán)）下，網(wǎng)中只有一個(gè)入度為零的點(diǎn)，稱做源點(diǎn)和一個(gè)出度為零的點(diǎn)，稱為匯點(diǎn)。18. 在AOE-網(wǎng)點(diǎn)，路徑長度最長的路徑叫做關(guān)鍵路徑，關(guān)鍵路徑上的所有活動(dòng)都是關(guān)鍵活動(dòng)。第九章：查找1. 查找表（Search Table）：是由同一類型的數(shù)據(jù)元素構(gòu)成的集合。若對(duì)查找表只作查找操作，則稱此類查找表為靜態(tài)查找表(Static Search Table)，若在查找過程中同時(shí)插入查找表中不存在的數(shù)據(jù)元素，則稱此類表為動(dòng)態(tài)查找表(Dynamic Search Table)。2. 關(guān)

14、鍵字（Key）：是數(shù)據(jù)元素或記錄中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可能標(biāo)識(shí)一個(gè)數(shù)據(jù)元素，若此關(guān)鍵字可以惟一地標(biāo)識(shí)一個(gè)記錄，則稱此關(guān)鍵字為主關(guān)鍵字(Primary Key)，反之，稱用以識(shí)別若干記錄的關(guān)鍵為次關(guān)鍵字(Secondary Key)。3. 查找：根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等給定值的記錄或數(shù)據(jù)元素，若表中存在這樣一個(gè)記錄，則稱查找是成功的，此時(shí)查找的結(jié)果為給出整個(gè)記錄的信息，或指示該記錄在查找表中的位置，若表中不存在關(guān)鍵字等于給定值的記錄，則稱查找不成功，此時(shí)查找的結(jié)果可給出一個(gè)“空”記錄或“空”指針。4. 順序查找(Sequential Search)的查找過程為：從表中最后一

15、個(gè)記錄開始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較，若某個(gè)記錄的關(guān)鍵字和給定值比較相等，則查找成功。反之，若直至第一個(gè)記錄，其關(guān)鍵字和給定值比較都不相等，則表明表中沒有所查記錄，查找不成功。5. 平均查找長度(Average Search Length)：為確定記錄在查找表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)的期望值稱為查找算法在查找成功時(shí)的平均查找長度。6. 折半查找(Binary Search)的查找過程：先確定待查記錄在有序表中所在范圍，然后逐步縮小范圍直到找到或找不到該記錄為止。7. 判定樹：樹中每個(gè)結(jié)點(diǎn)表示表中一個(gè)記錄，結(jié)點(diǎn)中的值為該記錄在表中的位置，通常稱這個(gè)查找過程的二叉樹稱為

16、判定樹。折半查找法在成功時(shí)進(jìn)行比較的關(guān)鍵字個(gè)數(shù)最多不超過樹的深度。8. 次優(yōu)查找樹(Nearly Optimal Search Tree)：構(gòu)造一棵二叉樹，使這棵二叉樹的帶權(quán)內(nèi)路徑長度PH值在所有具有同樣權(quán)值的二叉樹中近似為最小。9. 二叉排序樹(Binary Sort Tree)：或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹:a) 若它的左子樹不空，則左子村上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值。b) 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值。c) 它的左、右子樹也分別為二叉排序樹。10. 平衡二叉樹(Balanced Binary Tree)：又稱AVL樹，它或者是一棵空樹，

17、或者是具有下列性質(zhì)的二叉樹，它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對(duì)值不超過1。11. 平衡因子BF(Balance Factor)：為該結(jié)點(diǎn)的左子樹深度減去它的右子樹的深度，則平衡二叉樹上所有結(jié)點(diǎn)的平衡因子只能是-1，0，1，只要二叉樹上一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則該二叉樹是不平衡的。12. 哈希表(Hash Table)：根據(jù)設(shè)定的哈希函數(shù)和處理沖突的方法將一組關(guān)鍵字映射到一個(gè)有限的連續(xù)的地址集上，并以關(guān)鍵字在越來越集中的像作為記錄在表中的存儲(chǔ)位置，這種表便稱為哈希表，這一映射過程稱為哈希造表或散列，所得的存儲(chǔ)位置稱哈希地址或散列地址。13. 沖突(Col

18、lision)：對(duì)不同的關(guān)鍵字可能得到同一哈希地址，這種現(xiàn)象稱為沖突，具有相同函數(shù)值的關(guān)鍵字對(duì)該哈希函數(shù)來說稱做同義詞。14. 常用的構(gòu)造哈希函數(shù)的方法有：a) 直接定址法：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為哈希地址。b) 數(shù)字分析法：假設(shè)關(guān)鍵字是以r為基的數(shù)，并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可取關(guān)鍵字的若干位組成哈希地址。c) 平方取中法：取關(guān)鍵字平方的后的中間幾位做為哈希地址。d) 折疊法：將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和為哈希地址。e) 除留余數(shù)法：取關(guān)鍵字被某個(gè)不大于哈希表表長m的數(shù)p除后的余數(shù)為哈希地址。f) 隨機(jī)數(shù)法：選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的

19、隨機(jī)函數(shù)值為它的哈希地址。15. 常用的處理沖突的方法：a) 開放定址法：其中增量序列有線性探測(cè)再散列，二次探測(cè)再散列，隨機(jī)探測(cè)再散列。b) 再哈希法：即在同義詞產(chǎn)生地址沖突時(shí)計(jì)算另一個(gè)哈希函數(shù)地址，直到?jīng)_突不再發(fā)生。c) 鏈地址法：將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一線性鏈表中。d) 建立一個(gè)公共溢出區(qū)。16. 二次聚集：指在處理沖突過程中發(fā)生的兩個(gè)第一個(gè)哈希地址不同的記錄爭(zhēng)奪同一個(gè)后繼哈希地址的現(xiàn)象。17. 裝填因子：是表中填入的記錄數(shù)與哈希表的長度之商，哈希表的平均查找長度是裝填因子的函數(shù)，不是規(guī)模n的函數(shù)。第十章：內(nèi)部排序1. 排序(Sorting)：指將一個(gè)數(shù)據(jù)元素的任意序列重新排列成一個(gè)按關(guān)鍵字有序的序列。2. 假設(shè)Ri=Rj,且在排序前的序列中Ri領(lǐng)先于Rj，若在排序后的序列中Ri仍領(lǐng)先于Rj，則稱所用的排序方法是穩(wěn)定的，反之稱所用的排序方法是不穩(wěn)定的。3. 由于待排序的記錄的數(shù)量不同，使得排序過程中涉及的存儲(chǔ)器不同，可將排序方法分為兩大類：a) 內(nèi)部排序：指的是待排序記錄放在計(jì)算機(jī)隨機(jī)存儲(chǔ)器中進(jìn)行的排序過程b) 外部排序：指的是待排序記錄的數(shù)量很大，以致內(nèi)