《數(shù)據(jù)結(jié)構(gòu)》基本概念

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

2、； 線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對(duì)一的線性關(guān)系； 樹結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對(duì)多的層次關(guān)系； 圖結(jié)構(gòu)：數(shù)據(jù)元素之間存在著多對(duì)多的任意關(guān)系。注意：數(shù)據(jù)結(jié)構(gòu)分為兩類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)又稱為物理結(jié)構(gòu),是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示。通常有兩種存儲(chǔ)結(jié)構(gòu)：順序 存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)的基本思想是：用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素,數(shù)據(jù)元素之間的邏輯關(guān)系是由 元素的存儲(chǔ)位置來表示的。鏈接存儲(chǔ)結(jié)構(gòu)的基本思想是：用一組任意的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素,數(shù)據(jù)元素之間的邏輯關(guān)系是用指針 注意：存儲(chǔ)結(jié)構(gòu)除了存儲(chǔ)數(shù)據(jù)元素之外,必須存儲(chǔ)數(shù)據(jù)元素之間的邏輯關(guān)系。 抽象數(shù)據(jù)類型是一

3、個(gè)數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作的總稱。抽象數(shù)據(jù)類型提供了使用和實(shí) 現(xiàn)兩個(gè)不同的視圖,實(shí)現(xiàn)了封裝和信息隱藏。 通俗地講,算法是解決問題的方法,嚴(yán)格地說,算法是對(duì)特定問題求解步驟的一種描述,是指令的有限序 有窮性：一個(gè)算法必須總是對(duì)任何合法的輸入在執(zhí)行有窮步之后結(jié)束,且每一步都在有窮時(shí)間內(nèi)完 確定性：算法中的每一條指令必須有確切的含義,不存在二義性。并且,在任何條件下,對(duì)于相同的輸入只能得到相同的輸出。 可行性：算法描述的操作可以通過已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限次來實(shí)現(xiàn)。 線性表簡(jiǎn)稱表,是零個(gè)或多個(gè)具有相同類型的數(shù)據(jù)元素的有限序列。數(shù)據(jù)元素的個(gè)數(shù)稱為線性表的長度, 長度等于零時(shí)稱為空表。 設(shè)

4、順序表的每個(gè)元素占用c 個(gè)存儲(chǔ)單元,則第i 個(gè)元素的存儲(chǔ)地址為： 順序表利用了數(shù)組元素在物理位置上的鄰接關(guān)系來表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系,這使得順序 無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間； 可以快速地存取表中任一位置的元素即隨機(jī)存取。 插入和刪除操作需移動(dòng)大量元素。在順序表上做插入和刪除操作,等概率情況下,平均要移動(dòng)表中一 表的容量難以確定。由于數(shù)組的長度必須事先確定,因此,當(dāng)線性表的長度變化較大時(shí),難以確定合適 造成存儲(chǔ)空間的碎片。數(shù)組要求占用連續(xù)的存儲(chǔ)空間,即使存儲(chǔ)單元數(shù)超過所需的數(shù)目,如果不連續(xù) 也不能使用,造成存儲(chǔ)空間的碎片現(xiàn)象。 *first; /first

5、為單鏈表的頭指針 *first; 棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表。允許插入和刪除的一端稱為棧頂,另一端稱為棧底,不 含任何數(shù)據(jù)元素的棧稱為空棧。 棧的操作具有后進(jìn)先出的特性。 隊(duì)列是只允許在一端進(jìn)行插入操作,而另一端進(jìn)行刪除操作的線性表。允許插入的一端稱為隊(duì)尾,允許刪 隊(duì)列的操作具有先進(jìn)先出的特性。 循環(huán)隊(duì)列中解決隊(duì)空隊(duì)滿的判斷條件 串是零個(gè)或多個(gè)字符組成的有限序列。 只包含空格的串稱為空格串。串中所包含的字符個(gè)數(shù)稱為串的長度,長度為0 的串稱空串,記作 。 串的比較是通過組成串的字符之間的比較來進(jìn)行的。 當(dāng)下列條件之一成立時(shí),稱XY： 改進(jìn)的模式匹配算法中nextj的求法 0 j

6、=1 在數(shù)組上一般不能做插入、刪除元素的操作。因此,在數(shù)組 讀?。航o定一組下標(biāo),讀取相應(yīng)的數(shù)組元素； 修改：給定一組下標(biāo),存儲(chǔ)或修改相應(yīng)的數(shù)組元素。 特殊矩陣是指矩陣中有很多值相同的元素并且它們的分布有一定的規(guī)律。 壓縮存儲(chǔ)的基本思想是： 為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配存儲(chǔ)空間。 i/2 +j-1 當(dāng)ij 三元組順序表和十字鏈表 ; 廣義表是nn0 個(gè)數(shù)據(jù)元素的有限序列。 稱廣義表LS 中除去表頭后其余元素組成的廣義表為LS 的。 廣義表LS 中括號(hào)的最大嵌套層數(shù)稱為LS 的深度。 樹是nn0 個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n0 時(shí),稱為空樹；任意一棵非空樹滿足以下條件： 有且僅有

7、一個(gè)特定的稱為根的結(jié)點(diǎn)； 合又是一棵樹,并稱為這個(gè)根結(jié)點(diǎn)的子樹。 某結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)稱為該結(jié)點(diǎn)的度；樹中各結(jié)點(diǎn)度的最大值稱為該樹的度。 度為0 的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn),也稱為終端結(jié)點(diǎn)；度不為0 的結(jié)點(diǎn)稱為分支結(jié)點(diǎn),也稱為非終端結(jié)點(diǎn)。 某結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)；反之,該結(jié)點(diǎn)稱為其孩子結(jié)點(diǎn)的雙親 一條由n1 至nk 的路徑；路徑上經(jīng)過的邊的個(gè)數(shù)稱為路徑長度。 如果從結(jié)點(diǎn)x 到結(jié)點(diǎn)y 有一條路徑,那么x 就稱為y 的祖先,而y 稱為x 的子孫。注意：某結(jié)點(diǎn)子樹中的任一結(jié)點(diǎn)都是該結(jié)點(diǎn)的子孫。 規(guī)定根結(jié)點(diǎn)的層數(shù)為1,對(duì)其余任何結(jié)點(diǎn),若某結(jié)點(diǎn)在第k 層,則其孩子結(jié)點(diǎn)在第k+1 層；樹中所

8、有結(jié)點(diǎn)的最 大層數(shù)稱為樹的深度,也稱為樹的高度。 二叉樹是nn0 個(gè)結(jié)點(diǎn)的有限集合,該集合或者為空集稱為空二叉樹,或者由一個(gè)根結(jié)點(diǎn)和兩棵互不 相交的、分別稱為根結(jié)點(diǎn)的左子樹和右子樹的二叉樹組成。 二叉樹的特點(diǎn)是： 每個(gè)結(jié)點(diǎn)最多有兩棵子樹,所以二叉樹中不存在度大于2 的結(jié)點(diǎn)； 子樹的次序 不能任意顛倒,某結(jié)點(diǎn)即使只有一棵子樹也要區(qū)分是左子樹還是右子樹。注意：二叉樹和樹是兩種樹結(jié)構(gòu)。 二叉樹具有五種基本形態(tài)： 空二叉樹； 只有一個(gè)根結(jié)點(diǎn)； 根結(jié)點(diǎn)只有左子樹； 根結(jié)點(diǎn)只 有右子樹； 根結(jié)點(diǎn)既有左子樹又有右子樹。 所有結(jié)點(diǎn)都只有左子樹的二叉樹稱為左斜樹；所有結(jié)點(diǎn)都只有右子樹的二叉樹稱為右斜樹；左斜樹和

9、右 結(jié)點(diǎn)個(gè)數(shù)與其深度相同。 在一棵二叉樹中,如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹,并且所有葉子都在同一層上,這樣的二叉樹 滿二叉樹的特點(diǎn)： 葉子結(jié)點(diǎn)都在最下一層； 只有度為0 和度為2 的結(jié)點(diǎn)。 對(duì)一棵具有n 個(gè)結(jié)點(diǎn)的二叉樹按層序編號(hào),如果編號(hào)為i1in 的結(jié)點(diǎn)與同樣深度的滿二叉樹中編號(hào)為 i 的結(jié)點(diǎn)在二叉樹中的位置完全相同,則這棵二叉樹稱為完全二叉樹。完全二叉樹的特點(diǎn)是： 葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層,且最下層的葉子結(jié)點(diǎn)都集中在左面連續(xù)的位 性質(zhì)3 在一棵二叉樹中,如果葉子結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2 的結(jié)點(diǎn)個(gè)數(shù)為n2,則 性質(zhì)5 對(duì)一棵具有n 個(gè)結(jié)點(diǎn)的完全二叉樹中的結(jié)點(diǎn)從1 開始按層序編號(hào),則對(duì)

10、于任意的編號(hào)為i1i 包括：二叉樹的順序存儲(chǔ)和二叉樹的鏈?zhǔn)酱鎯?chǔ)。二叉鏈表的存儲(chǔ)結(jié)構(gòu)定義如下： BiNode *lchild, *rchild; *root; /root 表示二叉鏈表的頭指針 *root; /三叉鏈表的頭指針 所謂遍歷就是無重復(fù)無遺漏地訪問。二叉樹的遍歷是指從根結(jié)點(diǎn)出發(fā),按照某種次序訪問二叉樹中的所 有結(jié)點(diǎn),使得每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次。 前序遍歷或稱前根遍歷、先序遍歷若二叉樹為空,則空操作返回；否則 前序遍歷根結(jié)點(diǎn)的右子樹。中序遍歷或稱中根遍歷若二叉樹為空,則空操作返回；否則 后序遍歷或稱后根遍歷若二叉樹為空,則空操作返回；否則 層序遍歷二叉樹的層序遍歷是從二叉樹的第

11、一層根結(jié)點(diǎn)開始,從上至下逐層遍歷,在同一層中,則按從左到右的順 序?qū)Y(jié)點(diǎn)逐個(gè)訪問。 在一個(gè)具有n 個(gè)結(jié)點(diǎn)的二叉鏈表中,利用n+1 個(gè)空指針域存放指向該結(jié)點(diǎn)在某種遍歷序列中的前驅(qū)和后 繼結(jié)點(diǎn)的指針,這些指向前驅(qū)和后繼結(jié)點(diǎn)的指針稱為線索,加上線索的二叉樹稱為線索二叉樹,相應(yīng)地,加上線 索的二叉鏈表稱為線索鏈表。 *root; /root 表示線索鏈表的頭指針 包括：雙親表示法、孩子表示法、孩子兄弟表示法。雙親表示法的存儲(chǔ)結(jié)構(gòu)定義如下： ;/樹中最大結(jié)點(diǎn)個(gè)數(shù)/數(shù)組元素的類型/樹中結(jié)點(diǎn)的數(shù)據(jù)信息,/該結(jié)點(diǎn)的雙親在數(shù)組中的下標(biāo) 孩子表示法的存儲(chǔ)結(jié)構(gòu)定義如下： ; ;孩子兄弟表示法又稱為二叉鏈表表示法,存

12、儲(chǔ)結(jié)構(gòu)定義如下： ; 加線樹中所有相鄰兄弟結(jié)點(diǎn)之間加一條連線；去線對(duì)樹中的每個(gè)結(jié)點(diǎn),只保留它與第一個(gè)孩子結(jié)點(diǎn)之間的連線,刪去它與其它孩子結(jié)點(diǎn)之間的 層次調(diào)整以根結(jié)點(diǎn)為軸心,將樹順時(shí)針轉(zhuǎn)動(dòng)一定的角度,使之層次分明。 森林轉(zhuǎn)換為二叉樹的方法如下： 將森林中的每棵樹轉(zhuǎn)換成二叉樹； 從第二棵二叉樹開始,依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子,當(dāng)所有二叉樹連起來后,所得到的二叉樹就是由森林轉(zhuǎn)換的二叉樹。 樹和森林轉(zhuǎn)換為二叉樹的過程是可逆的,將一棵二叉樹還原為樹或森林的方法如下：加線若某結(jié)點(diǎn)x 是其雙親y 的左孩子,則把結(jié)點(diǎn)x 的右孩子、右孩子的右孩子、,都與結(jié)點(diǎn)y去線刪去原二叉樹中所有

13、的雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線；層次調(diào)整整理由、兩步所得到的樹或森林,使之層次分明。樹的遍歷序列與二叉樹的遍歷序列之間的對(duì)應(yīng)關(guān)系根據(jù)樹與二叉樹的轉(zhuǎn)換關(guān)系以及樹和二叉樹遍歷的操作定義可知,樹的遍歷序列與由樹轉(zhuǎn)化成的二叉樹 的遍歷序列之間具有如下對(duì)應(yīng)關(guān)系：樹的前序遍歷序列等于二叉樹的前序遍歷序列,樹的后序遍歷序列等于 二叉樹的中序遍歷序列。 葉子結(jié)點(diǎn)的權(quán)值是指對(duì)葉子結(jié)點(diǎn)賦予的一個(gè)有意義的數(shù)值量。 設(shè)二叉樹具有n 個(gè)帶權(quán)值的葉子結(jié)點(diǎn),從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長度與相應(yīng)葉子結(jié)點(diǎn)權(quán)值的乘積 之和稱做二叉樹的帶權(quán)路徑長度,記為：n n 給定一組具有確定權(quán)值的葉子結(jié)點(diǎn),可以構(gòu)造出不同的二叉樹,將其中帶權(quán)路

14、徑長度最小的二叉樹稱為 哈夫曼樹,也稱為最優(yōu)二叉樹。 初始化：由給定的n 個(gè)權(quán)值w1,w2,wn構(gòu)造n 棵只有一個(gè)根結(jié)點(diǎn)的二叉樹,從而得到一個(gè)二叉樹集 這棵新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和； 刪除與加入：在F 中刪除作為左、右子樹的兩棵二叉樹,并將新建立的二叉樹加入到F 中； 重復(fù)、兩步,當(dāng)集合F 中只剩下一棵二叉樹時(shí),這棵二叉樹便是哈夫曼樹。 圖是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成,通常表示為： 若頂點(diǎn)vi 和vj 之間的邊沒有方向,則稱這條邊為無向邊,用無序偶對(duì)來表示；若從頂點(diǎn)vi 到vj 的邊 有方向,則稱這條邊為有向邊也稱為弧,用有序偶對(duì)來表示,vi 稱為弧

15、尾,vj 稱為弧頭。如果圖的任意兩 個(gè)頂點(diǎn)之間的邊都是無向邊,則稱該圖為無向圖,否則稱該圖為有向圖。 若不存在頂點(diǎn)到其自身的邊,且同一條邊不重復(fù)出現(xiàn),則稱這樣的圖為簡(jiǎn)單圖。 在無向圖中,對(duì)于任意兩個(gè)頂點(diǎn)vi 和vj,若存在邊,則稱頂點(diǎn)vi 和vj 互為鄰接點(diǎn),同時(shí)稱邊依附 在無向圖中,如果任意兩個(gè)頂點(diǎn)之間都存在邊,則稱該圖為無向完全圖。含有n 個(gè)頂點(diǎn)的無向完全圖有n 在有向圖中,如果任意兩頂點(diǎn)之間都存在方向互為相反的兩條弧,則稱該圖為有向完全圖。含有n 個(gè)頂點(diǎn) 稱邊數(shù)很少的圖為稀疏圖,反之,稱為稠密圖。 在有向圖中,頂點(diǎn)v 的入度是指以該頂點(diǎn)為弧頭的弧的個(gè)數(shù),記為ID；頂點(diǎn)v 的出度是指以該頂

16、點(diǎn)為 在無向圖中,若任意頂點(diǎn)vi 和vj之間有路徑,則稱該圖是連通圖。非連通圖的極XX 通子圖稱為連通 在有向圖中,對(duì)任意頂點(diǎn)vi 和vj,若從頂點(diǎn)vi 到vj 和從頂點(diǎn)vj 到vi 均有路徑,則稱該有向圖是強(qiáng)連通 圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖稱為強(qiáng)連通分量。 鄰接表是一種順序存儲(chǔ)與鏈接存儲(chǔ)相結(jié)合的存儲(chǔ)方法,具體方法為：將頂點(diǎn)vi 的所有鄰接點(diǎn)鏈成一個(gè)單 鏈表,稱為頂點(diǎn)vi 的邊表對(duì)于有向圖則稱為出邊表,邊表的頭指針和頂點(diǎn)的數(shù)據(jù)信息采用順序存儲(chǔ)稱為頂 點(diǎn)表。所以,在鄰接表中存在兩種結(jié)點(diǎn)：頂點(diǎn)表結(jié)點(diǎn)和邊表結(jié)點(diǎn)。 鄰接表的存儲(chǔ)結(jié)構(gòu)定義如下： ; ; 深度優(yōu)先遍歷從圖中某頂點(diǎn)v 出發(fā)進(jìn)行深度優(yōu)先遍

17、歷的基本思想是： 從v 的未被訪問的鄰接點(diǎn)中選取一個(gè)頂點(diǎn)w,從w 出發(fā)進(jìn)行深度優(yōu)先遍歷； 重復(fù)上述兩步,直至圖中所有和v 有路徑相通的頂點(diǎn)都被訪問到。廣度優(yōu)先遍歷從圖中某頂點(diǎn)v 出發(fā)進(jìn)行廣度優(yōu)先遍歷的基本思想是： 分別從v1,v2,vk 出發(fā)依次訪問它們未被訪問的鄰接點(diǎn),直至圖中所有與頂點(diǎn)v 有路徑相通的頂點(diǎn)都 設(shè) G=是一個(gè)無向連通網(wǎng),生成樹上各邊的權(quán)值之和稱為該生成樹的代價(jià),在G 的所有生成樹中,代 價(jià)最小的生成樹稱為最小生成樹。 普里姆Prim 算法的基本思想 克魯斯卡爾Kruskal算法的基本思想 加入到 TE 中,同時(shí)把兩個(gè)連通分量連接為一個(gè)連通分量；若被考察邊的兩個(gè)頂點(diǎn)屬于同一個(gè)連

18、通分量,則舍 迪杰斯特拉Dijkstra算法的基本思想 假設(shè)相比較,取路徑長度較小者為當(dāng)前最短路徑。重復(fù)上述過程,直到集合V 中全部頂點(diǎn)加入到集合S 中。 i i i i 在一個(gè)表示工程的有向圖中,用頂點(diǎn)表示活動(dòng),用弧表示活動(dòng)之間的優(yōu)先關(guān)系,稱這樣的有向圖為頂點(diǎn)表 示活動(dòng)的網(wǎng),簡(jiǎn)稱AOV 網(wǎng)。 設(shè)G=是一個(gè)具有n個(gè)頂點(diǎn)的有向圖,V中的頂點(diǎn)序列v1, v2, , vn稱為一個(gè)拓?fù)湫蛄?當(dāng)且僅當(dāng)滿足 下列條件：若從頂點(diǎn)vi 到vj 有一條路徑,則在頂點(diǎn)序列中頂點(diǎn)vi 必在頂點(diǎn)vj 之前。 對(duì)AOV 網(wǎng)進(jìn)行拓?fù)渑判虻幕舅枷胧牵?從AOV 網(wǎng)中選擇一個(gè)沒有前驅(qū)的頂點(diǎn)并且輸出它； 從AOV 網(wǎng)中刪去該

19、頂點(diǎn),并且刪去所有以該頂點(diǎn)為尾的??； 重復(fù)上述兩步,直到全部頂點(diǎn)都被輸出,或AOV 網(wǎng)中不存在沒有前驅(qū)的頂點(diǎn)。 查找算法用關(guān)鍵碼的比較次數(shù)來度量查找算法的時(shí)間性能。對(duì)于查找成功的情況,將關(guān)鍵碼比較次數(shù)的 數(shù)學(xué)期望值定義為平均查找長度,即： i1 對(duì)于具有n 個(gè)記錄的順序表,查找第i 個(gè)記錄時(shí),需進(jìn)行n-i+1 次關(guān)鍵碼的比較。設(shè)每個(gè)記錄的查找概率 敗的平均查找長度為O。 順序查找對(duì)表中記錄的存儲(chǔ)沒有任何要求,順序存儲(chǔ)和鏈接存儲(chǔ)均可應(yīng)用；對(duì)表中記錄的有序性也沒有 要求,無論記錄是否按關(guān)鍵碼有序均可應(yīng)用。 折半查找也稱對(duì)半查找、對(duì)分查找、二分查找要求線性表中的記錄必須按關(guān)鍵碼有序,并且必須采用 取

20、有序表的中間記錄作為比較對(duì)象,則2若給定值小于中間記錄的關(guān)鍵碼,則在中間記錄的左半?yún)^(qū)繼續(xù)查找；3若給定值大于中間記錄的關(guān)鍵碼,則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過程,直到查找成功,或所查找的區(qū)域無記錄,查找失敗。 二叉排序樹或者是一棵空的二叉樹,或者是具有下列性質(zhì)的二叉樹： 若它的左子樹不空,則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值； 若它的右子樹不空,則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值； 它的左右子樹也都是二叉排序樹。 如果二叉排序樹是平衡的,則其查找效率為 O。如果二叉排序樹為一棵斜樹 ,則其查找效率為 平衡二叉樹或者是一棵空的二叉排序樹,或者是具有下列性質(zhì)的二叉排序樹： 根結(jié)點(diǎn)

21、的左子樹和右子樹的深度最多相差1。 根結(jié)點(diǎn)的左子樹和右子樹也都是平衡二叉樹。 在構(gòu)造二叉排序樹的過程中,每當(dāng)插入一個(gè)結(jié)點(diǎn)時(shí),首先檢查是否因插入而破壞了樹的平衡性,若是,則找 出最小不平衡子樹,在保持二叉排序樹特性的前提下,調(diào)整最小不平衡子樹中各結(jié)點(diǎn)之間的鏈接關(guān)系,進(jìn)行相 應(yīng)的旋轉(zhuǎn),使之成為新的平衡子樹。 設(shè)結(jié)點(diǎn)A 為最小不平衡子樹的根結(jié)點(diǎn),對(duì)該子樹進(jìn)行平衡化調(diào)整有以下四種情況： LL 型：結(jié)點(diǎn)x 插在根結(jié)點(diǎn)A 的左孩子的左子樹上。 LR 型：結(jié)點(diǎn)x 插在根結(jié)點(diǎn)A 的左孩子的右子樹上。RL 型：結(jié)點(diǎn)x 插在根結(jié)點(diǎn)A 的右孩子的左子樹上。 關(guān)系找到給定值k 的映射 ,若查找集合中存在這個(gè)記錄,則必

22、定在 的位置上。 采用散列技術(shù)將記錄存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間中 ,這塊連續(xù)的存儲(chǔ)空間稱為散列表,將關(guān)鍵碼映射為 散列表中適當(dāng)存儲(chǔ)位置的函數(shù)稱為散列函數(shù),所得的存儲(chǔ)位置址稱為散列地址。對(duì)于兩個(gè)不同的關(guān)鍵碼 k1k2,有 ,即兩個(gè)不同的記錄需要存放在同一個(gè)存儲(chǔ)位置,這種現(xiàn) 采用散列技術(shù)需要考慮的兩個(gè)關(guān)鍵問題是： 散列函數(shù)的設(shè)計(jì)。如何設(shè)計(jì)一個(gè)簡(jiǎn)單、均勻、存儲(chǔ)利用率高的散列函數(shù)。 沖突的處理。如何采取合適的處理沖突方法來解決沖突。 開放定址法用開放定址法處理沖突得到的散列表叫做閉散列表。所謂開放定址法,就是由關(guān)鍵碼得到的散列地址一旦產(chǎn)生了沖突,就去尋找下一個(gè)空的散列地址,只要散列表 足夠大,空的散列地

23、址總能找到,并將記錄存入。線性探測(cè)法當(dāng)發(fā)生沖突時(shí) ,線性探測(cè)法從沖突位置的下一個(gè)位置起 ,依次尋找空的散列地址 ,即對(duì)于鍵值 key,設(shè) 線性探測(cè)法會(huì)出現(xiàn)非同義詞之間對(duì)同一個(gè)散列地址爭(zhēng)奪的現(xiàn)象,稱為堆積或聚集。 二次探測(cè)法當(dāng)發(fā)生沖突時(shí),二次探測(cè)法尋找下一個(gè)散列地址的公式為： 隨機(jī)探測(cè)法當(dāng)發(fā)生沖突時(shí),隨機(jī)探測(cè)法探測(cè)下一個(gè)散列地址的位移量是一個(gè)隨機(jī)數(shù)列,即尋找下一個(gè)散列地址的公Hi=H+di% m拉鏈法鏈地址法di 是一個(gè)隨機(jī)數(shù)列,i=1,2,m-1用拉鏈法處理沖突構(gòu)造的散列表叫做開散列表。拉鏈法的基本思想是：將所有散列地址相同的記錄,即所有關(guān)鍵碼為同義詞的記錄存儲(chǔ)在一個(gè)單鏈表中 稱為同義詞子表,

24、在散列表中存儲(chǔ)的是所有同義詞子表的頭指針。 直接插入排序的基本思想是：依次將待排序序列中的每一個(gè)記錄插入到一個(gè)已排好序的序列中,直到全 最好情況：待排序序列為正序,時(shí)間復(fù)雜度為O；最壞情況：待排序序列為逆序,時(shí)間復(fù)雜度為O。平均情況：待排序序列中各種可能排列的概率相同,時(shí)間復(fù)雜度為O。直接插入排序只需要一個(gè)記錄的輔助空間。直接插入排序是一種穩(wěn)定的排序方法。 希爾排序的基本思想是：先將整個(gè)待排序記錄序列分割成若干個(gè)子序列,在子序列內(nèi)分別進(jìn)行直接插入 排序,待整個(gè)序列基本有序時(shí),再對(duì)全體記錄進(jìn)行一次直接插入排序。 希爾排序算法的時(shí)間性能是所取增量的函數(shù),其時(shí)間性能在O和O之間,當(dāng)n在某個(gè)特定范圍 希爾排序只需要一個(gè)記錄的輔助空間,用于暫存當(dāng)前待插入的記錄。希爾排序是一種不穩(wěn)定的排序方法。 起泡排序的基本思想是：兩兩比較相鄰記錄的關(guān)鍵碼,如果反序則交換,直到?jīng)]有反序的記錄為