數(shù)據(jù)庫(kù)系統(tǒng)工程師考點(diǎn)知識(shí)精講.docx

第二章：數(shù)據(jù)結(jié)構(gòu)與算法1、線性表的定義及特點(diǎn)線性表是若干數(shù)據(jù)元素組成的有限集合。線性表的特點(diǎn)是，有惟一的起始結(jié)點(diǎn)和惟一的終端結(jié)點(diǎn)，其它元素都有惟一的直接前驅(qū)和惟一的直接后繼。線性表的抽像數(shù)據(jù)類型定義包括2方面：數(shù)據(jù)對(duì)象、關(guān)系的定義；線性表有關(guān)操作的定義；線性表的數(shù)據(jù)對(duì)象是具有相同性質(zhì)數(shù)據(jù)元素的集合。線性表的有關(guān)操作有：基本操作：初始化線性表、撤消線性表、判/置空表、取表長(zhǎng)、取前驅(qū)元素、取后繼元素、取第i個(gè)元素、遍歷等。插刪操作：在順序結(jié)構(gòu)下，結(jié)點(diǎn)的插入（n/2）和刪除（n-1）/2主要是進(jìn)行元素的移動(dòng)；在鏈?zhǔn)浇Y(jié)構(gòu)下，結(jié)點(diǎn)的插刪是調(diào)整指針的指向。查找操作：在順序表中可以進(jìn)行折半查找，在鏈表中只能進(jìn)行順序查找。2、線性表的基本存儲(chǔ)結(jié)構(gòu)及特點(diǎn)，線性表有順序和鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)是：用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的數(shù)據(jù)元素。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是：用一組地址任意的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素。（存儲(chǔ)單元節(jié)點(diǎn)可以是連續(xù)的，也可以是不連續(xù)的）。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)包括：?jiǎn)捂湵恚ㄓ址Q線性鏈表），結(jié)點(diǎn)的結(jié)構(gòu)體有兩個(gè)域，分別存儲(chǔ)數(shù)據(jù)元素和當(dāng)前元素有關(guān)系的其它元素所在結(jié)點(diǎn)的指針。雙向鏈表，每個(gè)結(jié)點(diǎn)包含兩個(gè)指針，分別指明直接前驅(qū)和直接后繼元素，可以在兩個(gè)方向上遍歷其后及其前的元素。循環(huán)鏈表，鏈表中最后一個(gè)結(jié)點(diǎn)的指針指向第一個(gè)結(jié)點(diǎn)，開成環(huán)狀結(jié)構(gòu)，可以在任意位置上方向不變地遍歷全表。靜態(tài)鏈表，借助數(shù)組描述線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3、棧的定義：是只能通過訪問它的一端來實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)和檢索的一種線性數(shù)據(jù)結(jié)構(gòu)。棧的特點(diǎn)：是先進(jìn)后出（FILO）。在線結(jié)構(gòu)中，允許進(jìn)行插、刪操作的一端稱為棧頂，相應(yīng)另一端稱為棧底。不含數(shù)據(jù)的棧稱為空棧。棧的基本運(yùn)算有：置空棧、判空棧、元素入棧、出棧和讀取棧頂元素的值。棧的存儲(chǔ)結(jié)構(gòu)：順序棧和鏈棧。順序棧指，用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)自棧頂?shù)綏５椎脑?，同時(shí)設(shè)置指針top指示棧頂元素的位置。順序棧的空間容量是有限的，要預(yù)先定義。順序棧的入棧和出棧操作是通過修改數(shù)組下標(biāo)來完成。假設(shè)棧底對(duì)應(yīng)于數(shù)組下標(biāo)較大的一端，那么在元素入棧時(shí)就是下標(biāo)減1,而元素出棧時(shí)就是下標(biāo)加1。鏈棧，類似于線性鏈表，棧頂指針就是鏈表首結(jié)點(diǎn)的位置，元素的插刪操作限定在首結(jié)點(diǎn)處進(jìn)行。棧的應(yīng)用：表達(dá)式計(jì)算，數(shù)制轉(zhuǎn)換，括號(hào)匹配，迷宮問題，遞歸問題。4、隊(duì)列的定義：是一種先進(jìn)先出（FIFO）的線性表。隊(duì)列的特點(diǎn)：它只允許在表的一端插入元素而在表的另一端刪除元素。在隊(duì)列中允許插的一端叫隊(duì)尾（rear），允許刪的一端叫隊(duì)頭（front）。隊(duì)列的基本運(yùn)算：置隊(duì)空、判隊(duì)空、入隊(duì)、出隊(duì)、讀隊(duì)頭元素等。隊(duì)列的存儲(chǔ)結(jié)構(gòu)：順序隊(duì)列和鏈隊(duì)列。順序隊(duì)列，又被叫作循環(huán)隊(duì)列，設(shè)順序隊(duì)列Q,Q.front表示隊(duì)頭指針，Q.rear表示隊(duì)尾指針，則Q.front和Q.rear相等且為0時(shí)為空隊(duì)列；元素入隊(duì)時(shí)Q.rear加1,元素出隊(duì)時(shí)Q.front加1.因?yàn)轫樞蜿?duì)列的空間容量是提前設(shè)定的，所以當(dāng)Q.rear達(dá)到了上限時(shí)表示隊(duì)列滿。 為區(qū)別隊(duì)列空和隊(duì)列滿兩種情況下可能出現(xiàn)的Q.front = Q.rear,有兩種方法。一個(gè)是設(shè)置一個(gè)標(biāo)識(shí)位，以區(qū)別頭尾指針相同時(shí)隊(duì)列是空還是滿；另一個(gè)方法是犧牲一個(gè)元素空間，約定以Q.rear所指的下一個(gè)位置是Q.front時(shí)表示隊(duì)列滿。鏈隊(duì)列，鏈隊(duì)列為空的判定條件是頭尾指針相同且均指向頭結(jié)點(diǎn)。隊(duì)列的應(yīng)用：常用于需要排隊(duì)的場(chǎng)合，如操作系統(tǒng)中的打印隊(duì)列，離散事件的復(fù)讀機(jī)模擬等。5、串的定義：是僅由字符構(gòu)成的有限序列。是取值范圍受限的線性表。一般記為S = a1a2an。串的幾個(gè)概念：空串、空格串、子串、串相等、串比較。串的幾個(gè)操作：賦值操作StrAssign（s,t）、聯(lián)接操作Concat（s,t）、求串長(zhǎng)StrLength（s）、串比較StrCompare（s,t）、求子串SubString（s,start,len）。串的存儲(chǔ)：靜態(tài)存儲(chǔ)（順序存儲(chǔ)），是定長(zhǎng)的存儲(chǔ)結(jié)構(gòu)。當(dāng)串超長(zhǎng)時(shí)，超過部分將被截?cái)?。堆存?chǔ)，通過程序語(yǔ)言提供的字符數(shù)組定義串的存儲(chǔ)空間，事先不限定串的長(zhǎng)度，在程序執(zhí)行過程中動(dòng)態(tài)地申請(qǐng)地址連續(xù)的串值的空間。塊鏈存儲(chǔ)，使用鏈表存儲(chǔ)串值，每個(gè)結(jié)點(diǎn)可以存儲(chǔ)一個(gè)或多個(gè)字符，同時(shí)每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)指針指向后繼結(jié)點(diǎn)。串的模式匹配：樸素的模式匹配法、KMP算法。6、數(shù)組：是定長(zhǎng)線性表在維數(shù)上的擴(kuò)張，即線性表中的每個(gè)元素又是一個(gè)線性表。N維數(shù)組是一種同構(gòu)的數(shù)據(jù)結(jié)構(gòu)，其每個(gè)數(shù)據(jù)元素類型相同，結(jié)構(gòu)一致。數(shù)組的特點(diǎn)： 數(shù)組元素?cái)?shù)目固定。一旦定義了一個(gè)數(shù)組結(jié)構(gòu)就不再有元素的增減變化；數(shù)據(jù)元素具有相同的類型；數(shù)據(jù)元素的下標(biāo)關(guān)系受上下界的約束且下標(biāo)有序。數(shù)組的基本運(yùn)算：給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素；給定一組下標(biāo)，修改相應(yīng)的數(shù)據(jù)元素中的某個(gè)數(shù)據(jù)項(xiàng)的值。數(shù)組的存儲(chǔ)： 數(shù)組的固定結(jié)構(gòu)適于使用順序存儲(chǔ)。對(duì)于數(shù)組，只要知道它的維數(shù)和長(zhǎng)度，就可以為它分配存儲(chǔ)空間。反之，只要給出一組下標(biāo)就可以求出該數(shù)組元素的存儲(chǔ)位置。就是說，在數(shù)組的順序存儲(chǔ)結(jié)構(gòu)中，數(shù)據(jù)元素的位置是其下標(biāo)的線性函數(shù)。以行為主序； Loc（Aij） = Loc（Aij） + （i-1）*n + （j-1）*L以列為主序； Loc（Aij） = Loc（Aij） + （j-1）*m + （i-1）*L多維數(shù)組的順序存儲(chǔ)計(jì)算：例如3維數(shù)組A110, 58, -36,數(shù)組空間的起始位置是a,每個(gè)元素占4個(gè)存儲(chǔ)單元，試以行為主存儲(chǔ)和以列為主存儲(chǔ)時(shí)給出數(shù)組元素Ai,j,k的存儲(chǔ)地址。解：理解上面給出的以行為主序和以列為主序的兩個(gè)線性函數(shù)公式。把3維數(shù)組拆開計(jì)算，例如以行為主序時(shí)先將3維數(shù)組看成是有一個(gè)行和2個(gè)列的數(shù)組，算出此時(shí)以行為主占用了多少空間。然后再單獨(dú)看兩個(gè)列的組合Bj,k又會(huì)占用多少空間。前后結(jié)果相加就是這個(gè)3維數(shù)組元素在以行為主序存儲(chǔ)時(shí)的地址。如下，以行為主序時(shí)，Ai,j,k前面的元素個(gè)數(shù)是： （i-1）（8-5+1）（6-（-3）+1） + （j-5）（6-（-3）+1） + k-（-3） = 40i-40 + 10j-50 + k+3 = 40i + 10j + k -87因此Ai,j,k的地址為a + （40i+10j+k-87）*4以列為主序時(shí)，Ai,j,k的地址為a + （40k+10j+i+69）*47、特殊矩陣與稀疏矩陣，稀疏矩陣就是非零元素很少的矩陣，而特殊矩陣是非零元素分布有規(guī)律的一類矩陣。為節(jié)省空間，在存儲(chǔ)它們時(shí)都使用壓縮存儲(chǔ)，特殊矩陣有壓縮算法，稀疏矩陣使用三元組順序表或使用十字鏈表存儲(chǔ)矩陣元素。8、廣義表的定義：是由零個(gè)或多個(gè)單元素或子表所組成的有限序列。廣義表的長(zhǎng)度是指廣義表中元素的個(gè)數(shù)，深度是指廣義表展開后所含的括號(hào)的最大層數(shù)。廣義表的基本運(yùn)算：取表頭head（LS），非空廣義表的第一個(gè)元素稱為表頭；取表尾tail（LS），非空廣義表中除第一個(gè)元素之外，由其余元素構(gòu)成的表稱為表尾。表尾必定是一個(gè)表。Head（LS）=a1, Tail（LS）=（a2,a3,，an）9、樹的定義：樹是n（n=0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)稱為空樹。在任一非空樹中，有且僅有一個(gè)稱為根的結(jié)點(diǎn)；其余m個(gè)結(jié)點(diǎn)可分為m（m=0）個(gè)互不相交的有限集，其中每個(gè)子集合又都是一棵樹，稱為根結(jié)點(diǎn)的子樹。樹的定義是遞歸的，樹形結(jié)構(gòu)具有明顯的層次結(jié)構(gòu)。樹的術(shù)語(yǔ)：雙親和孩子，兄弟，結(jié)點(diǎn)的度，葉子結(jié)點(diǎn)，內(nèi)部結(jié)點(diǎn)，結(jié)點(diǎn)的層次，樹的高度，有序樹和無(wú)序樹，森林。樹的基本操作是：先根遍歷和后根遍歷。10、二叉樹的定義：二叉樹是另一種樹形結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多有兩棵子樹并且有左右之分，且左、右子樹的次序不能顛倒。滿二叉樹，若二叉樹上每一層的結(jié)點(diǎn)數(shù)目都達(dá)到最大值，則稱為滿二叉樹；完全二叉樹，若二叉樹的除第H層以外，其余各層的結(jié)點(diǎn)數(shù)目達(dá)到了最大值，而第H層上的結(jié)點(diǎn)集中存放在左側(cè)，則稱為完全二叉樹；非完全二叉樹，就是完全二叉樹的相反情況。二叉樹的性質(zhì)： 1）二叉樹第i層（i=1）上至多有2（i-1）個(gè)結(jié)點(diǎn)。2）深度為K的二叉樹至多有2k -1 個(gè)結(jié)點(diǎn)（k=1）。3）對(duì)任何一棵二叉樹，若其終端結(jié)點(diǎn)個(gè)數(shù)為N0,度為2的結(jié)點(diǎn)個(gè)數(shù)為N2,則N0 = N2 + 1 。4）具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log（2,n）+1。5）對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層次自左至右進(jìn)行編號(hào)，則對(duì)任一結(jié)點(diǎn)i （1=i1則其雙親為i/2。若2in,則結(jié)點(diǎn)i無(wú)左孩子，否則其左孩子為2i。若2i+1n,則結(jié)點(diǎn)i無(wú)右孩子，否則其右孩子為2i+1。例：一棵有124個(gè)葉結(jié)點(diǎn)的完全二叉樹，最多有多少結(jié)點(diǎn)？N0=N2+1N=N0+N1+N2N1=1綜合上面3個(gè)表達(dá)式可以求解。例2:具有N個(gè)結(jié)點(diǎn)的滿二叉樹，其葉子結(jié)點(diǎn)個(gè)數(shù)為多少？設(shè)其深度為h,則： N0=2（h-1）N = 2h - 1所以N0 = （n+1）/2二叉樹的存儲(chǔ)結(jié)構(gòu)：二叉樹的順序存儲(chǔ)結(jié)構(gòu)，若采用二叉樹的性質(zhì)5對(duì)樹中的結(jié)點(diǎn)進(jìn)行編號(hào)，即樹根結(jié)點(diǎn)的編號(hào)為1,若編號(hào)為i的結(jié)點(diǎn)存在左孩子，則其左孩子的編號(hào)為2i;若編號(hào)為i的結(jié)點(diǎn)存在右孩子，則其右孩子的編號(hào)為2i+1,這樣利用數(shù)組元素的下標(biāo)作為結(jié)點(diǎn)的編號(hào)，表示出結(jié)點(diǎn)間的關(guān)系。二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，二叉鏈表（有單向性）和三叉鏈表（有雙向性）。遍歷二叉樹，有4種方式：先序、中序、后序和層序遍歷。先序遍歷二叉樹的操作定義為：訪問根結(jié)點(diǎn)；先序遍歷根的左子樹；先序遍歷根的右子樹。（若二叉樹為空，則進(jìn)行空操作）。中序遍歷二叉樹的操作定義為：中序遍歷根的左子樹；訪問根結(jié)點(diǎn)；中序遍歷根的右子樹。（若二叉樹為空，則進(jìn)行空操作）。后序遍歷二叉樹的操作定義為：后序遍歷根的左子樹；后序遍歷根的右子樹；訪問根結(jié)點(diǎn)。層序遍歷二叉樹的操作定義為：從根結(jié)點(diǎn)開始，從或到右依次訪問每層上的結(jié)點(diǎn)。二叉樹遍歷思想的關(guān)鍵：首先在想象中把二叉樹補(bǔ)齊為滿二叉樹，葉子結(jié)點(diǎn)也要被想象為有2個(gè)子結(jié)點(diǎn)。然后，畫一條路線，從根出發(fā)，逆時(shí)針沿著二叉樹的外緣移動(dòng)，全程對(duì)每個(gè)結(jié)點(diǎn)均途經(jīng)三次。若第一次經(jīng)過時(shí)即訪問，則是先序遍歷；若是第二次經(jīng)過結(jié)點(diǎn)時(shí)訪問結(jié)點(diǎn)，則是中序遍歷；若是第3次經(jīng)過時(shí)訪問則是后序遍歷。這3種方法的路徑相同，但結(jié)果不同。遍歷二叉樹的基本操作就是，訪問結(jié)點(diǎn)。-遍歷二叉樹實(shí)質(zhì)上是按一定規(guī)則，將樹中的結(jié)點(diǎn)排成一個(gè)線性序列。11、線索二叉樹：對(duì)于有N個(gè)結(jié)點(diǎn)的二叉樹的二叉鏈表存儲(chǔ)表示，其中必有N+1個(gè)空指針。遍歷時(shí)使結(jié)點(diǎn)中原本為空的左孩子指針或（和）右孩子指針指向結(jié)點(diǎn)的前驅(qū)或（和）后繼，這樣的處理稱為對(duì)二叉樹的線索化，指向前驅(qū)或后繼的指針稱為線索。加上線索的二叉樹稱為線索二叉樹。為了區(qū)分結(jié)點(diǎn)中的指針是孩子還是線索，在結(jié)點(diǎn)結(jié)構(gòu)中增加標(biāo)志域ltag, rtag。兩個(gè)標(biāo)志取值0,則lchild,rchild域分別指向左孩子和右孩子；兩個(gè)標(biāo)志取值1,則lchild,rchild域分別指向直接前驅(qū)和直接后繼。訪問線索二叉樹時(shí)，如何查找結(jié)點(diǎn)的前驅(qū)和后繼？以中序線索二叉樹為例，令P指向樹中的某個(gè)結(jié)點(diǎn)。當(dāng)p-ltag = 0時(shí)，P的中序直接前驅(qū)一定是其左子樹進(jìn)行中序遍歷得到的最后一個(gè)結(jié)點(diǎn)，也可以沿P的左子樹根結(jié)點(diǎn)出發(fā)沿右孩子指針向下查找，直到找到一個(gè)沒有右孩子的結(jié)點(diǎn)時(shí)為止，該結(jié)點(diǎn)就是P的直接前驅(qū)結(jié)點(diǎn)，也稱為P的左子樹中“最右下”的結(jié)點(diǎn)。當(dāng)P-rtag = 0時(shí)，P的中序直接后繼一定是其右子樹進(jìn)行中序遍歷得到的第一個(gè)結(jié)點(diǎn)， 也可以沿P的右子樹根結(jié)點(diǎn)出發(fā)沿左孩子指針向上查找，直到找到一個(gè)沒有右孩子的結(jié)點(diǎn)時(shí)為止，該結(jié)點(diǎn)就是P的直接后繼結(jié)點(diǎn)，也稱為P的右子樹中“最左下”的結(jié)點(diǎn)。12、二叉樹的應(yīng)用：最優(yōu)二叉樹（又稱霍夫曼樹），是一種帶權(quán)路徑長(zhǎng)度最短的樹。路徑，是從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的通路，路徑上的分支數(shù)目稱為路徑長(zhǎng)度。樹的路徑長(zhǎng)度，是從根到每一個(gè)葉子結(jié)點(diǎn)之間的路徑長(zhǎng)度之和。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度，是從該結(jié)點(diǎn)到樹根之間的路徑長(zhǎng)度與該結(jié)點(diǎn)權(quán)的乘積。樹的帶權(quán)路徑長(zhǎng)度，是樹的所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記為 WPL 。如何構(gòu)造最優(yōu)二叉樹？使用霍夫曼算法如下：1）將給定的N個(gè)結(jié)點(diǎn)的權(quán)值構(gòu)成N棵二叉樹的集合F,其中每棵樹Ti只有一個(gè)權(quán)為Wi的根結(jié)點(diǎn)，其左右子樹為空。2）在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹，并新生成一個(gè)根結(jié)點(diǎn)，根結(jié)點(diǎn)的權(quán)值為左右子樹的權(quán)值和。3）從F中刪除被取出的兩棵樹并將新生成的樹放入F。4）重復(fù)2,3步驟到只剩一棵樹為止，這棵樹就是最優(yōu)二叉樹。最優(yōu)二叉樹的形式不唯一，但其WPL值卻是唯一確定的。霍夫曼編碼：若要設(shè)計(jì)長(zhǎng)度不等的編碼，則任一字符的編碼都不是其他字符編碼的前綴，這種編碼稱為“前綴編碼”。要設(shè)計(jì)總長(zhǎng)最短的二進(jìn)制前綴編碼，應(yīng)以N種字符出現(xiàn)的頻率作為權(quán)來構(gòu)造一棵霍夫曼樹，由此得到的二進(jìn)制前綴編碼稱為霍夫曼編碼。樹的左右分枝分別標(biāo)上0和1（或相反）。從根到葉子路徑上的0,1組成的串就是每個(gè)字符的二進(jìn)制編碼。13、樹的存儲(chǔ)結(jié)構(gòu)1）樹的雙親表示法，用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)樹的結(jié)點(diǎn)，并在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示器，指示其雙親結(jié)點(diǎn)在該存儲(chǔ)結(jié)構(gòu)中的位置；2）樹的孩子表示法，是在存儲(chǔ)結(jié)構(gòu)中用指針指出結(jié)點(diǎn)的每個(gè)孩子。要為樹的每個(gè)結(jié)點(diǎn)的孩子建立一個(gè)鏈表，則N個(gè)結(jié)點(diǎn)的樹具有N個(gè)單鏈表，這N個(gè)單鏈表的頭指針又排成了一個(gè)線性表（頭指針即樹的存儲(chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)的指示器）。將上兩種方法結(jié)合起來可以形成樹的雙親孩子表示法。3）樹的孩子兄弟表示法，是指用二叉鏈表表示樹。在鏈表的結(jié)點(diǎn)中設(shè)置兩個(gè)指針域，分別指向該結(jié)點(diǎn)的第一個(gè)孩子和下一個(gè)兄弟。 |firstchild| data |nextbrother| 若將樹的孩子指針解釋為左孩子、兄弟指針解釋為右孩子，則可以得到這棵樹的二叉樹結(jié)構(gòu)。14、樹的遍歷：先根遍歷；后根遍歷。樹進(jìn)行先根遍歷也就是對(duì)轉(zhuǎn)換得到的二叉樹進(jìn)行先序遍歷；對(duì)樹進(jìn)行后根遍歷也就是對(duì)轉(zhuǎn)換得到的二叉樹進(jìn)行中序遍歷。（先根遍歷的順序是：由根出發(fā)從左至右遍歷每棵子樹。后根遍歷的順序是從左至右從每棵子樹的葉子結(jié)點(diǎn)向根的方向訪問子樹，最后訪問根結(jié)點(diǎn)。）15、森林的遍歷：先序遍歷森林；中序遍歷森林。先序遍歷森林，若森林非空，訪問森林中第一棵樹的根結(jié)點(diǎn)，先序遍歷第一棵子樹根結(jié)點(diǎn)的子樹森林，再先序遍歷除第一棵樹之外的樹所構(gòu)成的森林。中序遍歷森林，若森林非空，中序遍歷森林中第一棵樹的子樹森林，再訪問第一棵樹的根結(jié)點(diǎn)，再中序遍歷除第一棵樹以外的樹所構(gòu)成的森林。16、樹、森林和二叉樹的轉(zhuǎn)換利用樹的孩子兄弟表示法可以由一棵樹轉(zhuǎn)成唯一的一棵二叉樹。森林如何轉(zhuǎn)換成二叉樹呢？因?yàn)闃涓鶝]有兄弟，所以樹轉(zhuǎn)換成二叉樹后一定沒有右子樹，所以森林轉(zhuǎn)換成二叉樹的方法是：1）先將森林中的每棵樹全轉(zhuǎn)成二叉樹；2）用第一棵樹的根做新二叉樹的根，第一棵樹轉(zhuǎn)為二叉樹后得到的左子樹做為新二叉樹的左子樹，第二棵樹作為新二叉樹的右子樹，第三棵樹作為新二叉樹的右子樹的右子樹，依此類推，森林便轉(zhuǎn)為了一棵二叉樹。17、圖的定義：在數(shù)據(jù)結(jié)構(gòu)中，圖是一個(gè)由頂點(diǎn)集合和邊集合構(gòu)成的二元組，其中邊表示頂點(diǎn)之間的關(guān)系。圖的主要術(shù)語(yǔ)：有向圖，圖中每條邊都是有方向的，弧、弧尾、弧頭；無(wú)向圖，圖中的邊是沒有方向的，邊；無(wú)向完全圖，圖中的N個(gè)結(jié)點(diǎn)之間每?jī)蓚€(gè)結(jié)點(diǎn)間都有邊，共有n（n-1）/2條邊；有向完全圖，圖中的N個(gè)結(jié)點(diǎn)之間每?jī)蓚€(gè)結(jié)點(diǎn)間都有方向相反的兩條弧，共有n（n-1）條弧；度、入度、出度，頂點(diǎn)v的度是指關(guān)聯(lián)于該頂點(diǎn)的邊的數(shù)目，記作D（v）。若是有向圖則以該頂點(diǎn)為終點(diǎn)的有向邊數(shù)目稱為入度，從該頂點(diǎn)出發(fā)的有向邊的數(shù)目稱為出度，有向圖的度是入庫(kù)和出度的和。路徑，兩個(gè)頂點(diǎn)之間由邊組成的一條通路。若是有向圖則路徑也有方向。路徑長(zhǎng)度是路徑上邊或弧的數(shù)目。第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路。若首尾頂點(diǎn)以外的頂點(diǎn)均不相同則是簡(jiǎn)單路徑，若只有首尾頂點(diǎn)相同則稱為簡(jiǎn)單回路。子圖，一個(gè)圖的頂點(diǎn)集合與邊集合都從屬于另一個(gè)圖，則稱之為另一個(gè)圖的子圖；連通圖與連通分量，在無(wú)向圖中若兩個(gè)頂點(diǎn)之間有路徑則稱為這兩個(gè)頂點(diǎn)是連通的。若無(wú)向圖中任兩個(gè)頂點(diǎn)間都是連通的則稱其為連通圖。該無(wú)向圖的最大連通子圖稱為它的連通分量。強(qiáng)連通圖與強(qiáng)連通分量，是有向圖的連通概念；網(wǎng)，邊（?。?quán)值的圖稱為網(wǎng)；生成樹，是一個(gè)極小的連通子圖，它包括圖中的全部頂點(diǎn)，但只有構(gòu)成一棵樹的n-1條邊；有向樹和生成森林，一個(gè)有向圖恰有一個(gè)頂點(diǎn)的入度為0其它頂點(diǎn)的入度均為1,則這是一棵有向樹。生成森林是一個(gè)有向圖中的若干棵有向樹組成，特點(diǎn)是含有全部頂點(diǎn)但只有足以構(gòu)成若干棵不相交的有向樹的弧。圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣表示法，用于表示圖有頂點(diǎn)之間的關(guān)系。對(duì)于個(gè)有n個(gè)頂點(diǎn)的圖G=（V,E）來說，其鄰接矩陣就是一個(gè)n階方陣。依靠判斷圖的兩頂點(diǎn)間是否存在邊或弧來決定Aij=1或Aij=0;網(wǎng)的鄰接矩陣，當(dāng)兩頂點(diǎn)間存在邊或弧時(shí)Aij等于權(quán)值否則Aij等于無(wú)窮。鄰接鏈表表示法，為圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表，單鏈表中的結(jié)點(diǎn)表示依附于相應(yīng)頂點(diǎn)的邊或弧，有表頭結(jié)點(diǎn)和表結(jié)點(diǎn)兩種結(jié)構(gòu)類型。圖的遍歷：深度優(yōu)先搜索；廣度優(yōu)先搜索。一個(gè)類似于先根遍歷，一個(gè)類似于層序遍歷。生成樹的概念：生成樹是連通圖的一個(gè)子圖，它由全部頂點(diǎn)和一次遍歷圖所經(jīng)過的邊組成。圖的生成樹不惟一，按深度優(yōu)先搜索得到深度優(yōu)先生成樹，按廣度優(yōu)先搜索得到廣度優(yōu)先生成樹。一個(gè)非連通圖，每個(gè)連通分量中的頂點(diǎn)集和遍歷時(shí)走過的邊集一起構(gòu)成若干棵生成樹，稱為非連通圖的生成樹森林。18、最小生成樹：連通網(wǎng)的邊是帶有權(quán)值的，將生成樹的各邊權(quán)值和稱為生成樹的權(quán)。其中權(quán)值最小的生成樹稱為最小生成樹。構(gòu)造最小生成樹的兩種算法：普里母算法：以一個(gè)頂點(diǎn)集合U作為初態(tài)，不斷尋找與U中頂點(diǎn)相鄰且代價(jià)最小的邊的另一個(gè)頂點(diǎn)，擴(kuò)充U至U=V時(shí)為止。例如初始只給U一個(gè)頂點(diǎn)且邊的集合TE=;這種算法的時(shí)間復(fù)雜度為O（n2），因?yàn)樗身旤c(diǎn)推算出的，所以適合于邊稠密的網(wǎng)的最小生成樹。克魯斯卡爾算法：假設(shè)連通網(wǎng)N=（V,E），令最小生成樹的初始狀態(tài)為只有n個(gè)頂點(diǎn)而無(wú)邊的非連通圖T=（V,），圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。在E中選擇代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價(jià)最小的邊。信此類推，直至T中所有頂點(diǎn)都在一個(gè)連通分量上為止。這種算法與頂點(diǎn)數(shù)無(wú)關(guān)，所以適合計(jì)算頂點(diǎn)多而邊稀疏的網(wǎng)的最小生成樹。19、AOV網(wǎng)（active on vertex）：在有向圖中，以頂點(diǎn)表示活動(dòng)，用有向邊表示活動(dòng)之間的優(yōu)先關(guān)系，這樣的網(wǎng)稱為AOV網(wǎng)。在AOV網(wǎng)中不應(yīng)出現(xiàn)有向環(huán)。拓樸排序：是將AOV網(wǎng)中所有頂點(diǎn)排成一個(gè)線性序列的過程，并且該序列滿足：若在AOV網(wǎng)中從頂點(diǎn)Vi到Vj有一條路徑，則在該線性序列中，頂點(diǎn)Vi必然在Vj之前。拓樸排序的方法：在AOV網(wǎng)中選一個(gè)入度為0的頂點(diǎn)并輸出它；從網(wǎng)中刪除該頂點(diǎn)及與其有關(guān)的邊；重復(fù)前兩步至網(wǎng)中不存在入度為0的頂點(diǎn)為止。這樣操作會(huì)有兩種結(jié)果：一個(gè)是所有頂點(diǎn)已輸出，也就是拓樸排序完成，說明網(wǎng)中不存在回路；另一個(gè)可能結(jié)果是尚有未輸出的結(jié)點(diǎn)，剩余頂點(diǎn)均有前驅(qū)頂點(diǎn)，表明網(wǎng)中存在回路！也可以進(jìn)行逆拓樸排序，即計(jì)算出度為0的頂點(diǎn)。拓樸算法的時(shí)間復(fù)雜度為O（n+e）。AOE網(wǎng)（active on edge）：,在帶權(quán)有向圖中，以事件表示頂點(diǎn)，以邊表示活動(dòng)，以邊上的權(quán)值表示活動(dòng)持續(xù)的時(shí)間，則這種網(wǎng)稱為用邊表示活動(dòng)的網(wǎng)，簡(jiǎn)稱AOE網(wǎng)。AOE網(wǎng)特點(diǎn)：1）頂點(diǎn)所表示的事件是指該頂點(diǎn)的所有進(jìn)入邊所表示的活動(dòng)已完成，所有發(fā)出邊表示的活動(dòng)可以開始的一種狀態(tài)。2）對(duì)一個(gè)工程來說，要有一個(gè)開始狀態(tài)和一個(gè)結(jié)束狀態(tài)，所以在AOE網(wǎng)中有一個(gè)入度為0的開始頂點(diǎn)，稱為源點(diǎn)；有一個(gè)出度為0的結(jié)束頂點(diǎn)，稱為匯點(diǎn)。AOE網(wǎng)中也不允許存在回路。3）完成整個(gè)工程的時(shí)間是從開始頂點(diǎn)到結(jié)束頂點(diǎn)間的最長(zhǎng)路徑的長(zhǎng)度（指該路徑上的權(quán)值和）?；顒?dòng)的松馳時(shí)間：用活動(dòng)的持續(xù)時(shí)間和該活動(dòng)兩側(cè)的兩個(gè)事件的關(guān)鍵路徑時(shí)間，二者取差。關(guān)鍵路徑：從源點(diǎn)到匯點(diǎn)的路徑長(zhǎng)度最長(zhǎng)路徑稱為關(guān)鍵路徑。關(guān)鍵路徑上的所有活動(dòng)均是關(guān)鍵活動(dòng)。最短路徑？20、查找的基本概念1）查找是一種常用的基本運(yùn)算。查找表是由同一類型數(shù)據(jù)元素構(gòu)成的集合；2）靜態(tài)查找表，指在進(jìn)行查找運(yùn)算時(shí)不再修改的已經(jīng)構(gòu)造好的查找表。靜態(tài)查找表只進(jìn)行兩種操作：查詢某個(gè)特定的數(shù)據(jù)元素是否在查找表中；檢索某個(gè)特定的數(shù)據(jù)元素的各種屬性。3）動(dòng)態(tài)查找表，是可以進(jìn)行另兩種操作的查找表，即在查找表中插入一個(gè)數(shù)據(jù)元素；從查找表中刪除一個(gè)數(shù)據(jù)元素。4）關(guān)鍵字，是數(shù)據(jù)元素的某個(gè)數(shù)據(jù)項(xiàng)的值，用它來識(shí)別這個(gè)數(shù)據(jù)元素；5）主關(guān)鍵字，指能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的關(guān)鍵字；6）次關(guān)鍵字，指能標(biāo)識(shí)多個(gè)數(shù)據(jù)元素的關(guān)鍵字；7）查找，根據(jù)給定的某個(gè)值，在查找表中確定是否存在一個(gè)其關(guān)鍵字等于給定值的記錄，并返回結(jié)果。順序查找，從表的一端開始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較，若找到一個(gè)記錄的關(guān)鍵字和給定值相等則查找成功；若整個(gè)表均比較過仍未找到則查找失敗。若要查找的記錄不在表中則需進(jìn)行n+1次查找。平均查找長(zhǎng)度為（n+1）/2。折半查找（二分查找），可以用二叉樹進(jìn)行分析，以中間記錄為根，左子表為左子樹，右子表為右子樹，依此類推。關(guān)鍵字的比較次數(shù)即為被查找結(jié)點(diǎn)在樹中的層數(shù)。查找成功或失敗時(shí)所比較的關(guān)鍵字?jǐn)?shù)不超過樹的層數(shù)。折半查找只適用于有序順序表（以數(shù)組方式存儲(chǔ)的有序表）。 n=2k - 1, k=log（n+1）分塊查找，又稱為索引順序查找，綜合使用上面兩種方法。將長(zhǎng)度為n的表均勻分為b塊，每塊含有s個(gè)記錄，按順序查找確定元素所在的塊，則ASL = Lb + Lw , 即塊內(nèi)查找與索引查找之和。ASL=（b+1）/2 + （s+1）/2 , 當(dāng)s取n的平方根時(shí)，ASL取得最小值“n的平方根加1”。21、二叉排序樹（又稱二叉查找樹）：二叉查找樹或者是一棵空樹，或者具有這樣的特性，1）若二叉查找樹的左子樹非空，則左子樹上的結(jié)點(diǎn)值均小于根結(jié)點(diǎn)的值；2）若它的右子樹非空，則右子樹上的結(jié)點(diǎn)值均大于根結(jié)點(diǎn)的值；3）左、右子樹的子身就是一棵二叉查找樹。二叉查找樹的查找過程從根結(jié)點(diǎn)開始，過程類似于折半查找（二分查找）。二叉查找樹的插入操作按它的特性法則進(jìn)行插入，若是空樹則作根結(jié)點(diǎn)，否則會(huì)成為一個(gè)新的葉子結(jié)點(diǎn)。在二叉查找樹中刪除一個(gè)結(jié)點(diǎn)時(shí)不能把該結(jié)點(diǎn)的子樹也刪掉，只能刪除這個(gè)結(jié)點(diǎn)但仍要保持二叉查找樹的特性，相當(dāng)于是從一個(gè)有序序列中刪除一個(gè)元素，不能破壞其它元素的有序性。一種方法是，如果刪除結(jié)點(diǎn)*P,則可以用*P的直接前驅(qū)或直接后繼代替*P,同時(shí)刪除它的直接前驅(qū)（或直接后繼）。二叉排序樹順序存儲(chǔ)在一地址連續(xù)的空間內(nèi)，則序列按中序遞增存儲(chǔ)。22、平衡二叉樹：它或者是一棵空樹，或者具有這樣的性質(zhì)：它的左右子樹都是平衡二叉樹，且左右子樹的深度之差的絕對(duì)值不超過1。平衡因子： 某結(jié)點(diǎn)的平衡因子定義為該結(jié)點(diǎn)的左子樹深度減去它的右子樹深度。平衡二叉樹上的所有結(jié)點(diǎn)的平衡因子只可能是-1、0和1。為了得到樹形均勻的二叉排序樹，在構(gòu)造二叉排序樹的過程中可以使用幾種辦法讓它保持為一棵平衡二叉樹。每插入一個(gè)新結(jié)點(diǎn)時(shí)，就檢查是否打破了平衡。若是，則找出最小不平衡二叉樹，在保持二叉排序樹特性的情況下，調(diào)整最小不平衡二叉樹中結(jié)點(diǎn)間關(guān)系，達(dá)到新的平衡。最小不平衡二叉樹是指離插入結(jié)點(diǎn)最近且以平衡因子的絕對(duì)值大于1的結(jié)點(diǎn)作為根的子樹。平衡二叉樹上的插入操作引起不平衡的解決方法：1）單向右旋平衡處理 -用于在根的左子樹根結(jié)點(diǎn)的左子樹上插入新結(jié)點(diǎn)情況。2）單向左旋平衡處理 -用于在根的右子樹根結(jié)點(diǎn)的右子樹上插入新結(jié)點(diǎn)情況。3）雙向旋轉(zhuǎn)（先左旋后右旋）操作 -用于在根的左子樹根結(jié)點(diǎn)的右子樹上插入新結(jié)點(diǎn)的情況。4）雙向旋轉(zhuǎn)（先右旋后左旋）操作 -用于在根的右子樹根結(jié)點(diǎn)的左子樹上插入新結(jié)點(diǎn)的情況。B樹，有幾個(gè)比較鮮明的特點(diǎn)。如：一棵m階的B樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹；非終結(jié)點(diǎn)（根除外）至少有m/2棵樹；根至少有兩棵子樹（當(dāng)根不是葉子時(shí)）；所有葉子結(jié)點(diǎn)出現(xiàn)在同一層次上。23、哈希表的定義：根據(jù)設(shè)定的哈希函數(shù)H（key）和處理沖突的方法，將一組關(guān)鍵字映射到一個(gè)有限的連續(xù)地址集上，并以關(guān)健字在地址集中的“像”作為記錄在表中的存儲(chǔ)位置，這種表稱為哈希表。這一映射過程稱為哈希造表或散列，所得的存儲(chǔ)位置稱為哈希地址或散列地址。哈希函數(shù)是從關(guān)鍵字集合到地址集合的映像。對(duì)于哈希表主要考慮兩個(gè)問題：一是如何構(gòu)造哈希函數(shù)；一是如何解決沖突。構(gòu)造哈希函數(shù)要解決好兩個(gè)問題：首先哈希函數(shù)是一個(gè)壓縮映像函數(shù)；其次哈希函數(shù)應(yīng)具有較好的散列性。前者為節(jié)省空間，后者為減少?zèng)_突。常用的哈希函數(shù)構(gòu)造方法有直接定址法、數(shù)字分析法、平方取中法、折疊法、隨機(jī)數(shù)法和除留余數(shù)法。處理沖突的方法：1）開放地址法 Hi = （H（key） + Di）%m i=1,2,，k （k=m-1）H（key）為哈希函數(shù)；m為哈希表的表長(zhǎng)；Di為增量序列。Di=1,2,3,，m-1 稱為線性探測(cè)再散列；Di=12,-12,22,-22，k2 （k=m/2） 稱為二次探測(cè)再散列；Di=偽隨機(jī)序列，稱為隨機(jī)探測(cè)再散列。最簡(jiǎn)單的產(chǎn)生探測(cè)序列的方法是線性探測(cè)，即當(dāng)沖突時(shí)順序?qū)ο乱粏卧M(jìn)行探測(cè)并存儲(chǔ)。在用線性探測(cè)法解決沖突構(gòu)造的哈希表中進(jìn)行查找時(shí)有3種可能結(jié)果：一是在某一位置上找到關(guān)鍵字等于key的記錄，查找成功；一是按探測(cè)序列查找不到而又遇到了空單元，查找失敗，此時(shí)可進(jìn)行插入操作；一是查遍全表，未查到指定關(guān)鍵字且存儲(chǔ)區(qū)已滿，要進(jìn)行溢出處理。線性探測(cè)法的缺點(diǎn)是“溢出處理需別編程序”,“很容易產(chǎn)生聚集現(xiàn)象”。2）鏈地址法 ,它在符號(hào)表的每一個(gè)記錄增加一個(gè)鏈域，鏈域中存放下一個(gè)有相同哈希函數(shù)值的記錄的的存儲(chǔ)地址。3）再哈希法 ,Hi = RHi（key） i= 1,2,k RHi均是不同的哈希函數(shù)，即在同義詞發(fā)生地址沖突時(shí)計(jì)算另一個(gè)哈希函數(shù)地址，直到解決。4）建立一個(gè)公共溢出區(qū)，一溢出全放這里去；哈希表的裝填因子， a = （表中添入的記錄數(shù)/哈希表長(zhǎng)度） -a越小，發(fā)生沖突的可能越小雖然哈希表在關(guān)鍵字與記錄的存儲(chǔ)位置之間建立了直接映像，但由于“沖突”的產(chǎn)生，使得哈希表的查找過程仍是一個(gè)給定值和關(guān)鍵字進(jìn)行比較的過程。仍須以平均查找長(zhǎng)度衡量哈希表的查找效率。在查找過程中須與給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)取決于3個(gè)因素：哈希函數(shù)、處理沖突方法、哈希表的裝填因子。24、排序：穩(wěn)定的排序、不穩(wěn)定的排序。內(nèi)部排序、外部排序。簡(jiǎn)單排序法：包括直接插入排序、冒泡排序和簡(jiǎn)單選擇排序。它們的算法復(fù)雜度為O（n2），在元素已經(jīng)基本有序的情況下，使用直接排序方法可獲得較高的效率O（n）。直接插入排序和冒泡排序是穩(wěn)定的排序方法，簡(jiǎn)單選擇排序是不穩(wěn)定的排序方法。直接插入排序適用于“在文件局部有序或文件長(zhǎng)度較小的情況下的一種最佳內(nèi)部排序方法”.直接插入排序的時(shí)間復(fù)雜度為O（n*n），若記錄序列為正序時(shí)其時(shí)間復(fù)雜度可提高到O（n）。正序？冒泡排序算法： void bubblesort（int data, int n）int i,j,tag,temp;for（i=0,tag=1;tag=1&in-1;i+）tag = 0;for（j=0;jdataj+1）temp=dataj;dataj=dataj+1;dataj+1=temp;tag=1;簡(jiǎn)單選擇排序算法：void selectsort（int data, int n）int i,j,k,temp;for（i=0;in-1;i+）k=i;for（j=i+1;jn;j+）if（datajdatak）k=j;if（k!=j）temp=datai;datai=datak;datak=temp;希爾排序，又稱為縮小增量排序。它是在直接插入排序的基礎(chǔ)上加以改進(jìn)得到的排序方法。基本思想就是：設(shè)定一個(gè)初始間隔d,dn,按間隔d將元素分組，在每一組內(nèi)進(jìn)行直接插入排序，可以使得最小元素跳躍式向前移動(dòng)。然后縮小增量d的值，重復(fù)上述操作到d=1時(shí)為止?？焖倥判颍舅枷胧峭ㄟ^一趟排序?qū)⒋判虻挠涗浄指顬楠?dú)立的兩部分，其中一部分的關(guān)鍵字均比另一部分小，然后再分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序。具體做法：在頭尾設(shè)兩個(gè)指針low,high,分別指向第一個(gè)元素和最后一個(gè)元素。設(shè)樞軸記錄為正向（返向）的第一個(gè)記錄。當(dāng)初始序列有序時(shí)，快速排序蛻變?yōu)槊芭菖判?，此時(shí)算法的時(shí)間復(fù)雜度為n*n。例如，對(duì)50個(gè)整數(shù)進(jìn)行快速排序時(shí)，因?yàn)槌跏夹蛄杏行?，所以排序過程退化為冒泡排序，總過程中的比較次數(shù)為49+48+1 = 49*50/2堆排序，基本思想是對(duì)一組待排序記錄的關(guān)鍵字，首選把它們按堆的定義排成一個(gè)序列，從而輸出堆頂?shù)淖钚￡P(guān)鍵字。然后將剩余關(guān)鍵字再調(diào)整成堆，便得到次小關(guān)鍵字，反復(fù)進(jìn)行，直至全部關(guān)鍵字排成有序序列