《《大數(shù)據(jù)結(jié)構(gòu)》基本概念》由會員分享，可在線閱讀，更多相關(guān)《《大數(shù)據(jù)結(jié)構(gòu)》基本概念（30頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、基本概念? 數(shù)據(jù)數(shù)據(jù)是信息的載體，在計算機科學(xué)中是指所有能輸入到計算機中并能被計算機程序識別和處理的符號集合。?數(shù)據(jù)元素數(shù)據(jù)元素也稱為結(jié)點，是表示數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。? 數(shù)據(jù)項數(shù)據(jù)項是構(gòu)成數(shù)據(jù)元素的不可分割的最小單位。?數(shù)據(jù)對象數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。注意：在不產(chǎn)生混淆的情況下，將數(shù)據(jù)對象簡稱為數(shù)據(jù)。?數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合，即數(shù)據(jù)結(jié)構(gòu)是一個二元組DataStructure =(D, R)，其中D是數(shù)據(jù)元素的集合，R是D上關(guān)系的集合。按照視點的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存 儲結(jié)構(gòu)。?數(shù)據(jù)

2、的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間邏輯關(guān)系的整體。根據(jù)數(shù)據(jù)元素之間邏輯關(guān)系的不同，數(shù)據(jù)結(jié)構(gòu)分為四類： 集合：數(shù)據(jù)元素之間就是“屬于同一個集合”，除此之外，沒有任何關(guān)系； 線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對一的線性關(guān)系； 樹結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對多的層次關(guān)系； 圖結(jié)構(gòu)：數(shù)據(jù)元素之間存在著多對多的任意關(guān)系。注意：數(shù)據(jù)結(jié)構(gòu)分為兩類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。? 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)又稱為物理結(jié)構(gòu)，是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機中的表示。通常有兩種存儲結(jié)構(gòu)：順 序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)的基本思想是：用一組連續(xù)的存儲單元 依次存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系是由元素的存儲位置

3、來表示的。鏈接存儲結(jié)構(gòu)的基本思想是：用一組任意的存儲單元存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系是用指針來表示的。注意：存儲結(jié)構(gòu)除了存儲數(shù)據(jù)元素之外，必須存儲數(shù)據(jù)元素之間的邏輯關(guān)系。? 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型是一個數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作的總稱。抽象數(shù)據(jù)類型提供了使用和實現(xiàn)兩個不同的視圖，實現(xiàn)了封裝和信息隱藏。? 算法的定義通俗地講，算法是解決問題的方法，嚴格地說，算法是對特定問題求解步驟的一種描述，是指令的有限序列。? 算法的特性 輸入：一個算法有零個或多個輸入（即算法可以沒有輸入），這些輸入通常取自于某個特定的對象 集合。輸出：一個算法有一個或多個輸出（即算法必須要有輸出），通常

4、輸出與輸入之間有著某種特定的 關(guān)系。有窮性：一個算法必須總是（對任何合法的輸入）在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間 內(nèi)完成。 確定性：算法中的每一條指令必須有確切的含義，不存在二義性。并且，在任何條件下，對于相同 的輸入只能得到相同的輸出。 可行性：算法描述的操作可以通過已經(jīng)實現(xiàn)的基本操作執(zhí)行有限次來實現(xiàn)。?線性表的定義線性表簡稱表，是零個或多個具有相同類型的數(shù)據(jù)元素的有限序列。數(shù)據(jù)元素的個數(shù)稱為線性表的長度，長度等于零時稱為空表。?線性表的邏輯關(guān)系在一個非空表L= (ai, a2, , an)中，任意一對相鄰的數(shù)據(jù)元素 a-i和ai之間(1 i n)存在序偶 關(guān)系(ai-i,ai),

5、且ai-i稱為ai的前驅(qū)，ai稱為ai-i的后繼。在這個序列中，ai無前驅(qū)，an無后繼，其它每個元素有且僅有一個前驅(qū)和一個后繼。?順序表的存儲結(jié)構(gòu)定義用MaxSize表示數(shù)組的長度，順序表的存儲結(jié)構(gòu)定義如下：#defi ne MaxSize i00typedef structElemType dataMaxSize; / ElemType表示不確定的數(shù)據(jù)類型int len gth;len gth 表示線性表的長度 SeqList;?順序表是隨機存取結(jié)構(gòu)設(shè)順序表的每個元素占用c個存儲單元，則第i個元素的存儲地址為：LOC(ai)= LOC(ai) + (i 1) xc?順序表的優(yōu)缺點順序表利用了

6、數(shù)組元素在物理位置上的鄰接關(guān)系來表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系，這使得順 序表具有下列優(yōu)點：無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間； 可以快速地存取表中任一位置的元素（即隨機存?。?。同時，順序表也具有下列缺點： 插入和刪除操作需移動大量元素。在順序表上做插入和刪除操作，等概率情況下，平均要移動表中 一半的元素。 表的容量難以確定。由于數(shù)組的長度必須事先確定，因此，當(dāng)線性表的長度變化較大時，難以確定 合適的存儲規(guī)模。 造成存儲空間的“碎片”。數(shù)組要求占用連續(xù)的存儲空間，即使存儲單元數(shù)超過所需的數(shù)目，如果 不連續(xù)也不能使用，造成存儲空間的“碎片”現(xiàn)象。?單鏈表的存儲結(jié)構(gòu)定義單鏈表

7、的存儲結(jié)構(gòu)定義如下：Struct Node ElemType data; / ElemType表示不確定的數(shù)據(jù)類型struct Node *n ext; *first;/first 為單鏈表的頭指針?雙鏈表的存儲結(jié)構(gòu)定義雙鏈表存儲結(jié)構(gòu)定義如下：struct DulNodeElemType data; / ElemType表示不確定的數(shù)據(jù)類型struct DulNode *prior, * next;/ prior 為前驅(qū)指針域，next 為后繼指針域 *first;/first表示雙鏈表的頭指針? 棧的定義棧是限定僅在表尾進行插入和刪除操作的線性表。允許插入和刪除的一端稱為棧頂，另一端稱為棧底

8、， 不含任何數(shù)據(jù)元素的棧稱為空棧。?棧的操作特性棧的操作具有后進先出的特性。? 隊列的定義隊列是只允許在一端進行插入操作，而另一端進行刪除操作的線性表。允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。?隊列的操作特性隊列的操作具有 先進先出的特性。?循環(huán)隊列中解決隊空隊滿的判斷條件方法一：附設(shè)一個存儲隊列中元素個數(shù)的變量num，當(dāng)num=0時隊空，當(dāng)num=QueueSize 時為隊滿；方法二：修改隊滿條件，浪費一個元素空間，隊滿時數(shù)組中只有一個空閑單元；即隊空的條件是front =rear，隊滿的條件 是(rear+1) % QueueSize=front ，隊列長度為 (rear-fron

9、t+QueueSize) % QueueSize。方法三：設(shè)置標志 flag，當(dāng)front=rear 且flag=0 時為隊空，當(dāng)front=rear 且flag=1 時為隊滿。? 串的定義串是零個或多個字符組成的有限序列。?空格串和空串的定義只包含空格的串稱為 空格串。串中所包含的字符個數(shù)稱為串的長度，長度為 0的串稱空串，記作” ”。 ? 串的比較串的比較是通過組成串的字符之間的比較來進行的。給定兩個串：X= X1X2XnY= y1y2ym則當(dāng) n=m 且 X1 = y1，Xn=ym時，稱 X=Y；當(dāng)下列條件之一成立時，稱Xv Y： n v m，且 Xi=yi (i=1 , 2，n)； 存

10、在某個 kmin( m , n),使得 Xi=yi (i=i , 2，k-1 ), xkvyk。改進的模式匹配算法中n extj的求法用nextj表示tj對應(yīng)的k值(1 wj j)在一個數(shù)組 SA中的下標為：k = ix(i-1)/2 + j-1。上三角中的元素aij (ivj),則訪問和它對應(yīng)的下三角中的元素aji即可，即：k = jx(j-1)/2 +i-1。精彩文檔三角矩陣的壓縮存儲中：下三角矩陣中任一兀素 aij在一個數(shù)組SA中的下標k與i、j的對應(yīng)關(guān)系為:r i x (i-1)/2 + j-1當(dāng) i jnx (n + 1)/2當(dāng) i 1時，除根結(jié)點之外的其余結(jié)點被分成m (m0 )個

11、互不相交的有限集合Ti, T2,，Tm,其中每個集合又是一棵樹，并稱為這個根結(jié)點的子樹。? 結(jié)點的度、樹的度某結(jié)點所擁有的子樹的個數(shù)稱為該結(jié)點的度；樹中各結(jié)點度的最大值稱為該樹的度。? 葉子結(jié)點、分支結(jié)點度為0的結(jié)點稱為葉子結(jié)點，也稱為終端結(jié)點；度不為0的結(jié)點稱為分支結(jié)點，也稱為非終端結(jié)點。? 孩子結(jié)點、雙親結(jié)點、兄弟結(jié)點某結(jié)點的子樹的根結(jié)點稱為該結(jié)點的孩子結(jié)點；反之，該結(jié)點稱為其孩子結(jié)點的雙親? 路徑、路徑長度如果樹的結(jié)點序列 ni, n2,nk滿足如下關(guān)系：結(jié)點m是結(jié)點m+i的雙親(1 wiv k)，則把ni, n2, nk稱為一條由ni至nk的路徑；路徑上經(jīng)過的邊的個數(shù)稱為路徑長度。?

12、祖先、子孫如果從結(jié)點x到結(jié)點y有一條路徑，那么 x就稱為y的祖先，而y稱為x的子孫。注意：某結(jié)點子樹中的任一結(jié)點都是該結(jié)點的子孫。? 結(jié)點的層數(shù)、樹的深度(高度)規(guī)定根結(jié)點的層數(shù)為i，對其余任何結(jié)點，若某結(jié)點在第k層，則其孩子結(jié)點在第 k+i層；樹中所有結(jié)點的最大層數(shù)稱為樹的深度，也稱為樹的高度。? 二叉樹的定義二叉樹是n (n 0)個結(jié)點的有限集合，該集合或者為空集(稱為空二叉樹)，或者由一個根結(jié)點和兩棵互不相交的、分別稱為根結(jié)點的左子樹和右子樹的二叉樹組成。2的結(jié)點；(2)子樹的次? 二叉樹的特點二叉樹的特點是： 每個結(jié)點最多有兩棵子樹，所以二叉樹中不存在度大于序不能任意顛倒，某結(jié)點即使只

13、有一棵子樹也要區(qū)分是左子樹還是右子樹。注意：二叉樹和樹是兩種樹結(jié)構(gòu)。二叉樹的基本形態(tài)二叉樹具有五種基本形態(tài)：空二叉樹； 只有一個根結(jié)點； 根結(jié)點只有左子樹； 根結(jié)點只有右子樹； 根結(jié)點既有左子樹又有右子樹。斜樹所有結(jié)點都只有左子樹的二叉樹稱為左斜樹；所有結(jié)點都只有右子樹的二叉樹稱為右斜樹；左斜樹和 右斜樹統(tǒng)稱為斜樹。斜樹的特點：每一層只有一個結(jié)點，即只有度為1和度為0的結(jié)點并且只有一個葉子結(jié)點； 斜樹的結(jié)點個數(shù)與其深度相同。滿二叉樹在一棵二叉樹中，如果所有分支結(jié)點都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二 叉樹稱為滿二叉樹。滿二叉樹的特點： 葉子結(jié)點都在最下一層；只有度為0和度為

14、2的結(jié)點。完全二叉樹對一棵具有n個結(jié)點的二叉樹按層序編號，如果編號為i (1 wi 1 ）。性質(zhì)2 在一棵深度為k的二叉樹中，最多有2k-1個結(jié)點，最少有k個結(jié)點。性質(zhì)3 在一棵二叉樹中，如果葉子結(jié)點的個數(shù)為no，度為2的結(jié)點個數(shù)為n2，則no= n2+ 1。性質(zhì)4 具有n個結(jié)點的完全二叉樹的深度為log2 n1。性質(zhì)5 對一棵具有n個結(jié)點的完全二叉樹中的結(jié)點從1開始按層序編號，則對于任意的編號為i （1wiwn）的結(jié)點（簡稱為結(jié)點i）,有：如果i 1，則結(jié)點i的雙親的編號為i/2 ；否則結(jié)點i是根結(jié)點，無雙親； 如果2iwn,則結(jié)點i的左孩子的編號為 2i；否則結(jié)點i無左孩子； 如果2i +

15、 1 wn，則結(jié)點i的右孩子的編號為2i+ 1 ；否則結(jié)點i無右孩子。? 二叉樹的存儲包括：二叉樹的順序存儲和二叉樹的鏈式存儲。二叉鏈表的存儲結(jié)構(gòu)定義如下：struct BiNodeElemType data;BiNode *lchild, *rchild; *root;/root 表示二叉鏈表的頭指針struct TriNodeElemType data;TriNode *lchild, *rchild, *pare nt;/ pare nt指向該結(jié)點的雙親 *root;/三叉鏈表的頭指針遍歷的含義所謂遍歷就是無重復(fù)無遺漏地訪問。二叉樹的遍歷是指從根結(jié)點出發(fā)，按照某種次序訪問二叉樹中的 所有

16、結(jié)點，使得每個結(jié)點被訪問一次且僅被訪問一次。? 二叉樹的遍歷次序定義前序遍歷（或稱前根遍歷、先序遍歷）若二叉樹為空，則空操作返回；否則訪問根結(jié)點； 前序遍歷根結(jié)點的左子樹；前序遍歷根結(jié)點的右子樹。中序遍歷（或稱中根遍歷）若二叉樹為空，則空操作返回；否則中序遍歷根結(jié)點的左子樹；訪問根結(jié)點；中序遍歷根結(jié)點的右子樹。后序遍歷（或稱后根遍歷）若二叉樹為空，則空操作返回；否則 后序遍歷根結(jié)點的左子樹； 后序遍歷根結(jié)點的右子樹；訪問根結(jié)點。層序遍歷二叉樹的層序遍歷是從二叉樹的第一層（根結(jié)點）開始，從上至下逐層遍歷，在同一層中，則按從左 到右的順序?qū)Y(jié)點逐個訪問。線索二叉樹的定義在一個具有n個結(jié)點的二叉鏈表

17、中，利用n+1個空指針域存放指向該結(jié)點在某種遍歷序列中的前驅(qū)和后繼結(jié)點的指針，這些指向前驅(qū)和后繼結(jié)點的指針稱為線索，加上線索的二叉樹稱為 線索二叉樹，相應(yīng)地,加上線索的二叉鏈表稱為線索鏈表。?線索二叉樹的存儲結(jié)構(gòu)定義線索鏈表中的結(jié)點定義如下：enum flag Child, Thread;/ 枚舉類型，枚舉常量 Child=0 ，Thread=1struct ThrNodeElemType data; / ElemType表示不確定的數(shù)據(jù)類型ThrNode *lchild, *rchild;flag ltag, rtag;*root;/root 表示線索鏈表的頭指針?樹的存儲結(jié)構(gòu)包括：雙親表示

18、法、孩子表示法、孩子兄弟表示法。雙親表示法的存儲結(jié)構(gòu)定義如下:/樹中最大結(jié)點個數(shù)/數(shù)組元素的類型/樹中結(jié)點的數(shù)據(jù)信息，/該結(jié)點的雙親在數(shù)組中的下標#defi ne MaxSize 100; struct PNodeElemType data; int pare nt;PNode TreeMaxSize;孩子表示法的存儲結(jié)構(gòu)定義如下:struct CTNode/ 孩子結(jié)點int child;CTNode *n ext;struct CBNode/ 表頭結(jié)點ElemType data;CTNode *firstchild; /指向孩子鏈表的頭指針 ;孩子兄弟表示法又稱為二叉鏈表表示法，存儲結(jié)構(gòu)定義

19、如下:struct TNodeElemType data;TNode *firstchild;TNode *rightsib;；/ ElemType 表示不確定的數(shù)據(jù)類型 /firstchild 指向該結(jié)點的第一個孩子 /rightsib 指向該結(jié)點的右兄弟樹轉(zhuǎn)換為二叉樹樹轉(zhuǎn)換為二叉樹的方法是:加線樹中所有相鄰兄弟結(jié)點之間加一條連線； 去線對樹中的每個結(jié)點，只保留它與第一個孩子結(jié)點之間的連線，刪去它與其它孩子結(jié)點之間的連線；層次調(diào)整一一以根結(jié)點為軸心，將樹順時針轉(zhuǎn)動一定的角度，使之層次分明。森林轉(zhuǎn)換為二叉樹森林轉(zhuǎn)換為二叉樹的方法如下： 將森林中的每棵樹轉(zhuǎn)換成二叉樹； 從第二棵二叉樹開始，依次把

20、后一棵二叉樹的根結(jié)點作為前一棵二叉樹根結(jié)點的右孩子，當(dāng)所有二 叉樹連起來后，所得到的二叉樹就是由森林轉(zhuǎn)換的二叉樹。? 二叉樹轉(zhuǎn)換為樹或森林樹和森林轉(zhuǎn)換為二叉樹的過程是可逆的，將一棵二叉樹還原為樹或森林的方法如下：加線一一若某結(jié)點 x是其雙親y的左孩子，則把結(jié)點 x的右孩子、右孩子的右孩子、，都與結(jié) 點y用線連起來；去線一一刪去原二叉樹中所有的雙親結(jié)點與右孩子結(jié)點的連線； 層次調(diào)整一一整理由、兩步所得到的樹或森林，使之層次分明。樹的遍歷序列與二叉樹的遍歷序列之間的對應(yīng)關(guān)系根據(jù)樹與二叉樹的轉(zhuǎn)換關(guān)系以及樹和二叉樹遍歷的操作定義可知，樹的遍歷序列與由樹轉(zhuǎn)化成的二叉 樹的遍歷序列之間具有如下對應(yīng)關(guān)系：樹

21、的前序遍歷序列等于二叉樹的前序遍歷序列，樹的后序遍歷序列等于二叉樹的中序遍歷序列。? 哈夫曼樹中葉子結(jié)點的權(quán)值葉子結(jié)點的權(quán)值是指對葉子結(jié)點賦予的一個有意義的數(shù)值量。? 二叉樹的帶權(quán)路徑長度設(shè)二叉樹具有 n個帶權(quán)值的葉子結(jié)點，從根結(jié)點到各個葉子結(jié)點的路徑長度與相應(yīng)葉子結(jié)點權(quán)值的乘 積之和稱做二叉樹的帶權(quán)路徑長度，記為：nWPL= wGkk 1其中，wk為第k個葉子結(jié)點的權(quán)值；lk為從根結(jié)點到第k個葉子結(jié)點的路徑長度。? 哈夫曼樹定義給定一組具有確定權(quán)值的葉子結(jié)點，可以構(gòu)造出不同的二叉樹，將其中帶權(quán)路徑長度最小的二叉樹稱 為哈夫曼樹，也稱為最優(yōu)二叉樹。? 哈夫曼算法的基本思想哈夫曼算法的基本思想是

22、：初始化：由給定的n個權(quán)值wi, W2,，Wn構(gòu)造n棵只有一個根結(jié)點的二叉樹，從而得到一個二 叉樹集合F= Ti, T2，,Tn; 選取與合并：在F中選取根結(jié)點的權(quán)值最小的兩棵二叉樹分別作為左、右子樹構(gòu)造一棵新的二叉樹,這棵新二叉樹的根結(jié)點的權(quán)值為其左、右子樹根結(jié)點的權(quán)值之和； 刪除與加入：在 F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到F中；重復(fù)、兩步，當(dāng)集合 F中只剩下一棵二叉樹時，這棵二叉樹便是哈夫曼樹。? 圖的定義圖是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G=(V,巳 其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中頂點之間邊的集合。?無向圖與有向

23、圖若頂點Vi和Vj之間的邊沒有方向，則稱這條邊為無向邊，用無序偶對（Vi, Vj）來表示；若從頂點 Vi到Vj的邊有方向，則稱這條邊為有向邊（也稱為?。糜行蚺紝i, Vj來表示，Vi稱為弧尾，Vj稱為弧頭。如果圖的任意兩個頂點之間的邊都是無向邊，則稱該圖為無向圖，否則稱該圖為 有向圖。? 簡單圖若不存在頂點到其自身的邊，且同一條邊不重復(fù)出現(xiàn)，則稱這樣的圖為簡單圖。? 鄰接、依附在無向圖中，對于任意兩個頂點Vi和Vj，若存在邊（Vi，Vj），則稱頂點Vi和Vj互為鄰接點，同時稱邊（Vi，Vj）依附于頂點Vi和Vj。在有向圖中，對于任意兩個頂點Vi和Vj，若存在弧Vi，Vj，則稱頂點Vj是V

24、i的鄰接點，同時稱弧Vi，Vj依附于頂點Vi和Vj。?無向完全圖、有向完全圖在無向圖中，如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖。含有n個頂點的無向完全圖有 n X（n-1）/2 條邊。在有向圖中，如果任意兩頂點之間都存在方向互為相反的兩條弧，則稱該圖為有向完全圖。含有n個頂點的有向完全圖有 n x（n-1）條邊。?稠密圖、稀疏圖稱邊數(shù)很少的圖為稀疏圖，反之，稱為稠密圖。?頂點的度、入度、出度在無向圖中，頂點 V的度是指依附于該頂點的邊的個數(shù)，記為TD（v）。在具有n個頂點e條邊的無向圖中，有下式成立：TD (Vi) 2ei 1在有向圖中，頂點v的入度是指以該頂點為弧頭的弧的個數(shù)，記

25、為ID(v)；頂點v的出度是指以該頂點n為弧尾的弧的個數(shù)，記為 OD(v)。在具有n個頂點e條邊的有向圖中，有下式成立:nnID (vjOD(vJ ei 1i 1? 連通圖、連通分量在無向圖中，若任意頂點Vi和vj(ij)之間有路徑，則稱該圖是連通圖。非連通圖的極大連通子圖稱為連通分量。強連通圖、強連通分量在有向圖中，對任意頂點Vi和Vj(izj)，若從頂點Vi到Vj和從頂點Vj到Vi均有路徑，則稱該有向圖是強連通圖。非強連通圖的極大強連通子圖稱為強連通分量。鄰接矩陣的存儲結(jié)構(gòu)定義假設(shè)圖G = (V, E)有n個頂點，則鄰接矩陣是一個 n xn的方陣，定義為:1 若(Vi, Vj) E 或 E

26、 啊山0否則鄰接矩陣的存儲結(jié)構(gòu)定義如下：#defi ne MaxSize 10typedef structElemType vertexMaxSize; int arcMaxSizeMaxSize; int vertexNum, arcNum; MGraph;鄰接表的存儲結(jié)構(gòu)定義/存放圖中頂點的信息，ElemType表示不確定的數(shù)據(jù)類型/存放圖中邊的信息/圖的頂點數(shù)和邊數(shù)鄰接表是一種順序存儲與鏈接存儲相結(jié)合的存儲方法，具體方法為：將頂點Vi的所有鄰接點鏈成一個單鏈表，稱為頂點 Vi的邊表(對于有向圖則稱為出邊表)，邊表的頭指針和頂點的數(shù)據(jù)信息采用順序存儲（稱為頂點表）。所以，在鄰接表中存在兩種

27、結(jié)點：頂點表結(jié)點和邊表結(jié)點。vertexfirstedge頂點表結(jié)點鄰接表表示的結(jié)點結(jié)構(gòu)adjvexn ext邊表結(jié)點其中，vertex :數(shù)據(jù)域，存放頂點信息;firstedge :指針域，邊表的頭指針;adjvex :鄰接點域，存放邊該頂點的鄰接點在頂點表中的下標;next :指針域，指向邊表中的下一個結(jié)點。鄰接表的存儲結(jié)構(gòu)定義如下:struct ArcNode /定義邊表結(jié)點int adjvex;II鄰接點域ArcNode *n ext;；struct VertexNodeII定義頂點表結(jié)點ElemType vertex;II ElemType表示不確定的數(shù)據(jù)類型ArcNode *fir

28、stedge;；#define MaxSize 10typedef structVertexNode adjlistMaxSize;II 頂點表int vertexNum, arcNum;II圖的頂點數(shù)和邊數(shù) ALGraph;圖的遍歷次序定義深度優(yōu)先遍歷從圖中某頂點v出發(fā)進行深度優(yōu)先遍歷的基本思想是： 訪問頂點V； 從v的未被訪問的鄰接點中選取一個頂點w，從w出發(fā)進行深度優(yōu)先遍歷; 重復(fù)上述兩步，直至圖中所有和v有路徑相通的頂點都被訪問到。廣度優(yōu)先遍歷精彩文檔從圖中某頂點v出發(fā)進行廣度優(yōu)先遍歷的基本思想是： 訪問頂點V ； 依次訪問V的各個未被訪問的鄰接點V1 , V2 , , Vk； 分別從

29、Vi , V2,，Vk出發(fā)依次訪問它們未被訪問的鄰接點，直至圖中所有與頂點V有路徑相通的頂點都被訪問到。? 最小生成樹的定義設(shè)G=(V, E)是一個無向連通網(wǎng)，生成樹上各邊的權(quán)值之和稱為該生成樹的代價，在G的所有生成樹中，代價最小的生成樹稱為最小生成樹。? 普里姆(Prim )算法的基本思想設(shè)G=(V，曰是一個無向連通網(wǎng)，令T=(U,TE)是G的最小生成樹。T的初始狀態(tài)為U=vo(vo V),TE= ，然后重復(fù)執(zhí)行下述操作：在所有 u U , V V-U的邊中找一條代價最小的邊 (u , v)并入邊集TE, 同時v并入頂點集U，直至U= V為止。? 克魯斯卡爾(Kruskal )算法的基本思想

30、設(shè)無向連通網(wǎng)為G = (V,E),令G的最小生成樹為T=(U ,TE)，其初態(tài)為U= V,TE=，然后按照邊的權(quán)值由小到大的順序，依次考察邊集E中的各條邊。若被考察邊的兩個頂點屬于T的兩個不同的連通分量，則將此邊加入到 TE中，同時把兩個連通分量連接為一個連通分量；若被考察邊的兩個頂點屬于同一個 連通分量，則舍去此邊，以免造成回路。如此下去，當(dāng)T中的連通分量個數(shù)為 1時，此連通分量便為 G的一棵最小生成樹。? 迪杰斯特拉(Dijkstra )算法的基本思想設(shè)置集合S存放已經(jīng)找到最短路徑的頂點，S的初始狀態(tài)只包含源點 v ,對Vi V-S,假設(shè)從源點v到Vi的有向邊為最短路徑。以后每求得一條最短

31、路徑V,，Vk，就將Vk加入集合S中，并將路徑V,，Vk , Vi與原來的假設(shè)相比較，取路徑長度較小者為當(dāng)前最短路徑。重復(fù)上述過程，直到集合V中全部頂點加入到 集合S中。? Floyd算法的基本思想假設(shè)從Vi到Vj的弧(若從Vi到Vj的弧不存在，則將其弧的權(quán)值看成8)是最短路徑，然后進行n次試探。若Vi,Vk和Vk,，Vj分別是從Vi到Vk和從Vk到Vj中間頂點的序號不大于 k-1的最短路徑，則將Vi, Vk,，出和已經(jīng)得到的從 Vi到出中間頂點的序號不大于 k-1的最短路徑相比較，取長度較短者為從 Vi到Vj 中間頂點的序號不大于 k的最短路徑。? AOV網(wǎng)的定義在一個表示工程的有向圖中，用

32、頂點表示活動，用弧表示活動之間的優(yōu)先關(guān)系，稱這樣的有向圖為頂 點表示活動的網(wǎng)，簡稱 AOV網(wǎng)。? 拓撲序列的定義設(shè)G=(V, E)是一個具有n個頂點的有向圖， V中的頂點序列vi, V2, -, Vn稱為一個拓撲序列，當(dāng)且僅 當(dāng)滿足下列條件：若從頂點 Vi到Vj有一條路徑，則在頂點序列中頂點Vi必在頂點Vj之前。? 拓撲排序的基本思想對AOV網(wǎng)進行拓撲排序的基本思想是： 從AOV網(wǎng)中選擇一個沒有前驅(qū)的頂點并且輸出它； 從AOV網(wǎng)中刪去該頂點，并且刪去所有以該頂點為尾的??； 重復(fù)上述兩步，直到全部頂點都被輸出，或AOV網(wǎng)中不存在沒有前驅(qū)的頂點。? 查找算法的時間性能查找算法用關(guān)鍵碼的比較次數(shù)來度

33、量查找算法的時間性能。對于查找成功的情況，將關(guān)鍵碼比較次數(shù) 的數(shù)學(xué)期望值定義為平均查找長度，即：nASLpi 5i 1其中，n表示問題規(guī)模，即查找集合中的記錄個數(shù)；pi表示查找第i個記錄的概率；Ci表示查找第i個記錄所需的關(guān)鍵碼的比較次數(shù)。? 順序查找算法的時間復(fù)雜度對于具有n個記錄的順序表，查找第 i個記錄時，需進行 n-i+1次關(guān)鍵碼的比較。設(shè)每個記錄的查找概率相等，查找成功時，順序查找的平均查找長度為：O （n）；查找不成功時，關(guān)鍵碼的比較次數(shù)是 n+1次,則查找失敗的平均查找長度為O（ n）。? 順序查找的適用情況順序查找對表中記錄的存儲沒有任何要求，順序存儲和鏈接存儲均可應(yīng)用；對表中

34、記錄的有序性也沒有要求，無論記錄是否按關(guān)鍵碼有序均可應(yīng)用。? 折半查找的適用情況折半查找（也稱對半查找、對分查找、二分查找）要求線性表中的記錄必須按關(guān)鍵碼有序，并且必須采用順序存儲。? 折半查找的基本思想取有序表的中間記錄作為比較對象，則（1 ）若給定值與中間記錄的關(guān)鍵碼相等，則查找成功；（2 ）若給定值小于中間記錄的關(guān)鍵碼，則在中間記錄的左半?yún)^(qū)繼續(xù)查找；（3 ）若給定值大于中間記錄的關(guān)鍵碼，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過程，直到查找成功，或所查找的區(qū)域無記錄，查找失敗。? 折半查找的時間復(fù)雜度具有n個結(jié)點的折半查找判定樹的深度為log2 n 1。最好情況：比較1次，即查找的關(guān)鍵

35、碼是判定樹的根結(jié)點；最壞情況：比較次數(shù)為 log2 n 1，即查找的關(guān)鍵碼是判定樹的最下一層結(jié)點；平均情況：折半查找的平均時間復(fù)雜度為O（log 2n）。查找不成功的比較次數(shù)最多不超過樹的深度，最多為log2 n 1次。?二叉排序樹的定義二叉排序樹或者是一棵空的二叉樹，或者是具有下列性質(zhì)的二叉樹： 若它的左子樹不空，則左子樹上 所有結(jié)點的值均小于根結(jié)點的值； 若它的右子樹不空，則右子樹上 所有結(jié)點的值均大于根結(jié)點的值； 它的左右子樹也都是二叉排序樹。?二叉排序樹的查找性能如果二叉排序樹是平衡的，則其查找效率為O(log 2n)。如果二叉排序樹為一棵斜樹，則其查找效率為0(n)。因此，二叉排序樹

36、的查找性能在O(log2n)和O(n)之間。?平衡二叉樹的定義平衡二叉樹或者是一棵空的二叉排序樹，或者是具有下列性質(zhì)的二叉排序樹：根結(jié)點的左子樹和右子樹的深度最多相差1。根結(jié)點的左子樹和右子樹也都是平衡二叉樹。?構(gòu)造平衡二叉樹的基本思想在構(gòu)造二叉排序樹的過程中，每當(dāng)插入一個結(jié)點時，首先檢查是否因插入而破壞了樹的平衡性，若是，則找出最小不平衡子樹，在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點之間的鏈接關(guān)系，進行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹。?平衡調(diào)整的四種類型設(shè)結(jié)點A為最小不平衡子樹的根結(jié)點，對該子樹進行平衡化調(diào)整有以下四種情況：LL型：結(jié)點x插在根結(jié)點A的左孩子的左子樹上。RR

37、型：結(jié)點x插在根結(jié)點A的右孩子的右子樹上。LR型：結(jié)點x插在根結(jié)點A的左孩子的右子樹上。RL型：結(jié)點x插在根結(jié)點A的右孩子的左子樹上。? 散列查找的基本思想散列查找也稱為哈希查找、Hash查找，其基本思想是：在記錄的存儲位置和它的關(guān)鍵碼之間建立一個確定的對應(yīng)關(guān)系 H，使得每個關(guān)鍵碼 key和唯一的一個存儲位置 H(key)相對應(yīng)。在查找時，根據(jù)這個確定的對應(yīng)關(guān)系找到給定值 k的映射H(k)，若查找集合中存在這個記錄，則必定在H(k)的位置上。? 散列查找的基本概念采用散列技術(shù)將記錄存儲在一塊連續(xù)的存儲空間中，這塊連續(xù)的存儲空間稱為散列表，將關(guān)鍵碼映射為散列表中適當(dāng)存儲位置的函數(shù)稱為散列函數(shù)，所

38、得的存儲位置址稱為散列地址。對于兩個不同的關(guān)鍵碼 kik2,有H(ki)= H(k2),即兩個不同的記錄需要存放在同一個存儲位置，這種現(xiàn)象稱為 沖突，ki和k2相對于H稱做同義詞。? 散列查找的關(guān)鍵問題采用散列技術(shù)需要考慮的兩個關(guān)鍵問題是：散列函數(shù)的設(shè)計。如何設(shè)計一個簡單、均勻、存儲利用率高的散列函數(shù)。沖突的處理。如何采取合適的處理沖突方法來解決沖突。? 處理沖突的方法開放定址法用開放定址法處理沖突得到的散列表叫做閉散列表。所謂開放定址法，就是由關(guān)鍵碼得到的散列地址一旦產(chǎn)生了沖突，就去尋找下一個空的散列地址，只要散列表足夠大，空的散列地址總能找到，并將記錄存入。 線性探測法當(dāng)發(fā)生沖突時，線性探

39、測法從沖突位置的下一個位置起，依次尋找空的散列地址，即對于鍵值key ,設(shè)H (key )= d，閉散列表的長度為 m，則發(fā)生沖突時，尋找下一個散列地址的公式為：精彩文檔Hi=(H(key) + di) % m (di=1 , 2，m-1 )。線性探測法會出現(xiàn)非同義詞之間對同一個散列地址爭奪的現(xiàn)象，稱為堆積或聚集。 二次探測法當(dāng)發(fā)生沖突時，二次探測法尋找下一個散列地址的公式為：Hi=(H(key) + di)% m (di=1 2, - 1 2, 22, 22，q2, q2 且 q wm/2 ) 隨機探測法當(dāng)發(fā)生沖突時，隨機探測法探測下一個散列地址的位移量是一個隨機數(shù)列，即尋找下一個散列地址的

40、公式為：Hi=( H(key)+ di)% m(di是一個隨機數(shù)列，i=1 , 2, , m-1 )拉鏈法(鏈地址法)用拉鏈法處理沖突構(gòu)造的散列表叫做開散列表。拉鏈法的基本思想是：將所有散列地址相同的記錄，即所有關(guān)鍵碼為同義詞的記錄存儲在一個單鏈表中稱為同義詞子表，在散列表中存儲的是所有同義詞子表的頭指針。? 直接插入排序的基本思想直接插入排序的基本思想是：依次將待排序序列中的每一個記錄插入到一個已排好序的序列中，直到全部記錄都排好序。? 直接插入排序算法的性能時間性能最好情況：待排序序列為正序，時間復(fù)雜度為O( n);最壞情況：待排序序列為逆序，時間復(fù)雜度為0( n2)。平均情況：待排序序列

41、中各種可能排列的概率相同，時間復(fù)雜度為0( n2)。-空間性能直接插入排序只需要一個記錄的輔助空間。穩(wěn)定性直接插入排序是一種穩(wěn)定的排序方法。? 希爾排序的基本思想希爾排序的基本思想是：先將整個待排序記錄序列分割成若干個子序列，在子序列內(nèi)分別進行直接插 入排序，待整個序列基本有序時，再對全體記錄進行一次直接插入排序。? 希爾排序算法的性能時間性能希爾排序算法的時間性能是所取增量的函數(shù)，其時間性能在 O(n2)和O(nlog 2n)之間，當(dāng)n在某個特定范圍時，希爾排序的時間性能約為O(n1.3)?？臻g性能希爾排序只需要一個記錄的輔助空間，用于暫存當(dāng)前待插入的記錄。穩(wěn)定性希爾排序是一種不穩(wěn)定的排序方

42、法。? 起泡排序的基本思想起泡排序的基本思想是：兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序的記錄為止。? 起泡排序算法的性能時間性能最好情況：待排序記錄序列為正序，時間復(fù)雜度為O(n)；最壞情況：待排序記錄序列為反序，時間復(fù)雜度為0( n2);平均情況：時間復(fù)雜度為 0( n2)。-空間性能起泡排序只需要一個記錄的輔助空間，用來作為記錄交換的暫存單元。穩(wěn)定性起泡排序是一種穩(wěn)定的排序方法。? 快速排序的基本思想快速排序又稱為分區(qū)交換排序，其基本思想是：首先選一個軸值(即比較的基準)，將待排序記錄分割成獨立的兩部分，左側(cè)記錄的關(guān)鍵碼均小于或等于軸值，右側(cè)記錄的關(guān)鍵碼均大于或等于軸值，然

43、后分別 對這兩部分重復(fù)上述過程，直到整個序列有序。? 快速排序的性能時間性能最好情況：時間復(fù)雜度為 O( niog2 n)。最壞情況：待排序記錄序列為正序或逆序，時間復(fù)雜度為0( n2)。平均情況：時間復(fù)雜度為 0( nlog2 n)?？臻g性能最好情況下為 O(log 2n)；最壞情況下，棧的深度為 0(n)；平均情況下，棧的深度為O(log 2n)。穩(wěn)定性快速排序是一種不穩(wěn)定的排序方法。? 簡單選擇排序的基本思想簡單選擇排序的基本思想是：第i趟(1 wiwn-1 )排序通過n-i次關(guān)鍵碼的比較，在 n-i+1個記錄中選取關(guān)鍵碼最小的記錄，并和第i個記錄交換作為有序序列的第i個記錄。? 簡單選

44、擇排序算法的性能時間性能簡單選擇排序最好、最壞和平均的時間復(fù)雜度均為O（ n2）?？臻g性能在簡單選擇排序過程中，只需要一個用來作為記錄交換的暫存單元。穩(wěn)定性簡單選擇排序是一種不穩(wěn)定的排序方法。? 堆的定義小根堆）；堆是具有下列性質(zhì)的完全二叉樹：每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值（稱為或者每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值（稱為大根堆）。? 堆排序的基本思想首先將待排序的記錄序列構(gòu)造成一個堆（假設(shè)利用大根堆），此時，選出了堆中所有記錄的最大者即 堆頂記錄，然后將它從堆中移走（通常將堆頂記錄和堆中最后一個記錄交換），并將剩余的記錄再調(diào)整成 堆，這樣又找出了次大的記錄，以此類推，直到堆中只有一個記錄為止。? 堆排序算法的性能時間性能堆排序最好、最壞和平均的時間復(fù)雜度為0（nlog 2n）。空間性能在堆排序算法中，只需要一個用來交換的暫存單元。穩(wěn)定性堆排序是一種不穩(wěn)定的排序方法。? 二路歸并排序的基本思想將若干個有序序列進行兩兩歸并，直至所有待排序記錄都在一個有序序列為止。? 二路歸并排序算法的性能-時間性能歸并排序算法最好、最壞、平均的時間性能的時間代價是O(n| og2 n)。空間性能二路歸并排序在歸并過程中需要與原始記錄序列同樣數(shù)量的存儲空間，以便暫存歸并的中間結(jié)果，因 此其空間復(fù)雜度為 O( n)。穩(wěn)定性二路歸并排序是一種穩(wěn)定的排序方法。