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

基本概念數(shù)據(jù)數(shù)據(jù)是信息的載體，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)集合。數(shù)據(jù)元素?cái)?shù)據(jù)元素也稱為結(jié)點(diǎn)，是表示數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)是構(gòu)成數(shù)據(jù)元素的不可分割的最小單位。數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。注意：在不產(chǎn)生混淆的情況下，將數(shù)據(jù)對(duì)象簡稱為數(shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合，即數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組）其中是數(shù)據(jù)元素的集合，是上關(guān)系的集合。按照視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(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)系；⑵線性結(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)數(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ù)類型抽象數(shù)據(jù)類型是一個(gè)數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作的總稱。抽象數(shù)據(jù)類型提供了使用和實(shí)現(xiàn)兩個(gè)不同的視圖，實(shí)現(xiàn)了封裝和信息隱藏。>算法的定義通俗地講，算法是解決問題的方法，嚴(yán)格地說，算法是對(duì)特定問題求解步驟的一種描述，是指令的有限序列。>算法的特性⑴輸入：一個(gè)算法有零個(gè)或多個(gè)輸入（即算法可以沒有輸入），這些輸入通常取自于某個(gè)特定的對(duì)象集合。⑵輸出：一個(gè)算法有一個(gè)或多個(gè)輸出（即算法必須要有輸出），通常輸出與輸入之間有著某種特定的關(guān)系。⑶有窮性：一個(gè)算法必須總是（對(duì)任何合法的輸入）在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。⑷確定性：算法中的每一條指令必須有確切的含義，不存在二義性。并且，在任何條件下，對(duì)于相同的輸入只能得到相同的輸出。⑸可行性：算法描述的操作可以通過已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限次來實(shí)現(xiàn)。線性表的定義線性表簡稱表，是零個(gè)或多個(gè)具有相同類型的數(shù)據(jù)元素的有限序列。數(shù)據(jù)元素的個(gè)數(shù)稱為線性表的長度，長度等于零時(shí)稱為空表。線性表的邏輯關(guān)系在一個(gè)非空表=,,,中，任意一對(duì)相鄰的數(shù)據(jù)元素和之間（vW）存在序偶關(guān)系（，），且稱為的前驅(qū)，稱為的后繼。在這個(gè)序列中，無前驅(qū)，無后繼，其它每個(gè)元素有且僅有一個(gè)前驅(qū)和一個(gè)后繼。順序表的存儲(chǔ)結(jié)構(gòu)定義用 表示數(shù)組的長度，順序表的存儲(chǔ)結(jié)構(gòu)定義如下：表示不確定的數(shù)據(jù)類型表示線性表的長度順序表是隨機(jī)存取結(jié)構(gòu)設(shè)順序表的每個(gè)元素占用個(gè)存儲(chǔ)單元，則第個(gè)元素的存儲(chǔ)地址為：+-）>順序表的優(yōu)缺點(diǎn)順序表利用了數(shù)組元素在物理位置上的鄰接關(guān)系來表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系,這使得順序表具有下列優(yōu)點(diǎn)：⑴無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間；⑵可以快速地存取表中任一位置的元素（即隨機(jī)存?。Ｍ瑫r(shí),順序表也具有下列缺點(diǎn)：⑴插入和刪除操作需移動(dòng)大量元素。在順序表上做插入和刪除操作,等概率情況下,平均要移動(dòng)表中一半的元素。⑵表的容量難以確定。由于數(shù)組的長度必須事先確定,因此,當(dāng)線性表的長度變化較大時(shí),難以確定合適的存儲(chǔ)規(guī)模。⑶造成存儲(chǔ)空間的“碎片”。數(shù)組要求占用連續(xù)的存儲(chǔ)空間,即使存儲(chǔ)單元數(shù)超過所需的數(shù)目,如果不連續(xù)也不能使用,造成存儲(chǔ)空間的“碎片”現(xiàn)象。單鏈表的存儲(chǔ)結(jié)構(gòu)定義單鏈表的存儲(chǔ)結(jié)構(gòu)定義如下：表示不確定的數(shù)據(jù)類型為單鏈表的頭指針雙鏈表的存儲(chǔ)結(jié)構(gòu)定義雙鏈表存儲(chǔ)結(jié)構(gòu)定義如下：表示不確定的數(shù)據(jù)類型為前驅(qū)指針域， 為后繼指針域表示雙鏈表的頭指針棧的定義棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表。允許插入和刪除的一端稱為棧頂，另一端稱為棧底，不含任何數(shù)據(jù)元素的棧稱為空棧。>棧的操作特性棧的操作具有后進(jìn)先出的特性。隊(duì)列的定義隊(duì)列是只允許在一端進(jìn)行插入操作，而另一端進(jìn)行刪除操作的線性表。允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭。隊(duì)列的操作特性隊(duì)列的操作具有先進(jìn)先出的特性。>循環(huán)隊(duì)列中解決隊(duì)空隊(duì)滿的判斷條件方法一：附設(shè)一個(gè)存儲(chǔ)隊(duì)列中元素個(gè)數(shù)的變量，當(dāng) 時(shí)隊(duì)空，當(dāng) 時(shí)為隊(duì)滿；方法二：修改隊(duì)滿條件，浪費(fèi)一個(gè)元素空間，隊(duì)滿時(shí)數(shù)組中只有一個(gè)空閑單元；即隊(duì)空的條件是，隊(duì)滿的條件是 ，隊(duì)列長度為 。方法三：設(shè)置標(biāo)志 ，當(dāng) 且 時(shí)為隊(duì)空，當(dāng) 且 時(shí)為隊(duì)滿。串的定義串是零個(gè)或多個(gè)字符組成的有限序列?？崭翊涂沾亩x只包含空格的串稱為空格串。串中所包含的字符個(gè)數(shù)稱為串的長度，長度為0的串稱空串，記作"串的比較串的比較是通過組成串的字符之間的比較來進(jìn)行的。給定兩個(gè)串：則當(dāng)且，…，時(shí)，稱；當(dāng)下列條件之一成立時(shí)，稱V:⑴V，且（，，…，n；⑵存在某個(gè)W,,使得（，，…， ），V。改進(jìn)的模式匹配算法中 的求法用 表示對(duì)應(yīng)的值（WW），其定義如下：J0 ji 口next[j]=]max{k|lWk<j且”丫2…tk1"="tjk+j+2…\1"}I1 其它情況數(shù)組的基本操作數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)集合，在數(shù)組上一般不能做插入、刪除元素的操作。因此，在數(shù)組中通常只有兩種操作：⑴讀?。航o定一組下標(biāo)，讀取相應(yīng)的數(shù)組元素；⑵修改：給定一組下標(biāo)，存儲(chǔ)或修改相應(yīng)的數(shù)組元素。二維數(shù)組的尋址按行優(yōu)先，設(shè)二維數(shù)組的行下標(biāo)與列下標(biāo)的范圍分別為［,］與】，］,則任一元素的存儲(chǔ)地址可由下式確定：= + —X—+ + — ）特殊矩陣的定義特殊矩陣是指矩陣中有很多值相同的元素并且它們的分布有一定的規(guī)律。矩陣壓縮存儲(chǔ)的基本思想壓縮存儲(chǔ)的基本思想是：⑴為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間；⑵對(duì)零元素不分配存儲(chǔ)空間。TOC\o"1-5"\h\z對(duì)稱矩陣的壓縮存儲(chǔ)中：下三角元素（$j在一個(gè)數(shù)組中的下標(biāo)為： X 。上三角中的元素（V）,則訪問和它對(duì)應(yīng)的下三角中的元素即可，即：X 。三角矩陣的壓縮存儲(chǔ)中：下三角矩陣中任一元素在一個(gè)數(shù)組中的下標(biāo)與、的對(duì)應(yīng)關(guān)系為：k=fzX（1）2+j1 當(dāng)i^j=nXn+1）2 當(dāng)iVj上三角矩陣元素在中的下標(biāo)為： X +>稀疏矩陣的壓縮存儲(chǔ)方式三元組順序表和十字鏈表三元組的定義廣義表的定義廣義表是（$）個(gè)數(shù)據(jù)元素的有限序列。A表頭當(dāng)廣義表非空時(shí)，稱第一個(gè)元素為的表頭；A表尾稱廣義表中除去表頭后其余元素組成的廣義表為的。長度廣義表中的直接元素的個(gè)數(shù)稱為的長度；深度廣義表中括號(hào)的最大嵌套層數(shù)稱為的深度。樹的定義樹是（$）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)=時(shí)，稱為空樹；任意一棵非空樹滿足以下條件：⑴有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；⑵當(dāng)>時(shí)，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成（）個(gè)互不相交的有限集合，，…，,其中每個(gè)集合又是一棵樹，并稱為這個(gè)根結(jié)點(diǎn)的子樹。>結(jié)點(diǎn)的度、樹的度~某結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)稱為該結(jié)點(diǎn)的度；樹中各結(jié)點(diǎn)度的最大值稱為該樹的度。葉子結(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)。A孩子結(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)的雙親路徑、路徑長度如果樹的結(jié)點(diǎn)序列 …滿足如下關(guān)系：結(jié)點(diǎn)是結(jié)點(diǎn)的雙親（WV）,則把 …稱為一條由至的路徑；路徑上經(jīng)過的邊的個(gè)數(shù)稱為路徑長度。祖先、子孫如果從結(jié)點(diǎn)到結(jié)點(diǎn)有一條路徑，那么就稱為的祖先，而稱為的子孫。注意：某結(jié)點(diǎn)子樹中的任一結(jié)點(diǎn)都是該結(jié)點(diǎn)的子孫。結(jié)點(diǎn)的層數(shù)、樹的深度（高度）規(guī)定根結(jié)點(diǎn)的層數(shù)為1，對(duì)其余任何結(jié)點(diǎn)，若某結(jié)點(diǎn)在第）層，則其孩子結(jié)點(diǎn)在第）+1層；樹中所有結(jié)點(diǎn)的最大層數(shù)稱為樹的深度，也稱為樹的高度。二叉樹的定義二叉樹是（$）個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹和右子樹的二叉樹組成。二叉樹的特點(diǎn)二叉樹的特點(diǎn)是：⑴每個(gè)結(jié)點(diǎn)最多有兩棵子樹，所以二叉樹中不存在度大于的結(jié)點(diǎn)；⑵子樹的次序不能任意顛倒，某結(jié)點(diǎn)即使只有一棵子樹也要區(qū)分是左子樹還是右子樹。注意：二叉樹和樹是兩種樹結(jié)構(gòu)。二叉樹的基本形態(tài)二叉樹具有五種基本形態(tài)：⑴空二叉樹；⑵只有一個(gè)根結(jié)點(diǎn)；⑶根結(jié)點(diǎn)只有左子樹；⑷根結(jié)點(diǎn)只有右子樹；⑸根結(jié)點(diǎn)既有左子樹又有右子樹。A斜樹所有結(jié)點(diǎn)都只有左子樹的二叉樹稱為左斜樹；所有結(jié)點(diǎn)都只有右子樹的二叉樹稱為右斜樹；左斜樹和右斜樹統(tǒng)稱為斜樹。斜樹的特點(diǎn)：①每一層只有一個(gè)結(jié)點(diǎn)，即只有度為和度為的結(jié)點(diǎn)并且只有一個(gè)葉子結(jié)點(diǎn)；②斜樹的結(jié)點(diǎn)個(gè)數(shù)與其深度相同。滿二叉樹在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹。滿二叉樹的特點(diǎn)：①葉子結(jié)點(diǎn)都在最下一層；②只有度為0和度為2的結(jié)點(diǎn)。完全二叉樹對(duì)一棵具有個(gè)結(jié)點(diǎn)的二叉樹按層序編號(hào)，如果編號(hào)為（WW）的結(jié)點(diǎn)與同樣深度的滿二叉樹中編號(hào)為的結(jié)點(diǎn)在二叉樹中的位置完全相同，則這棵二叉樹稱為完全二叉樹。完全二叉樹的特點(diǎn)是：①葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層，且最下層的葉子結(jié)點(diǎn)都集中在左面連續(xù)的位置；②如果有度為1的結(jié)點(diǎn)，只可能有一個(gè)，且該結(jié)點(diǎn)只有左孩子。二叉樹的基本性質(zhì)性質(zhì)二叉樹的第層上最多有個(gè)結(jié)點(diǎn)（$）。性質(zhì)2在一棵深度為）的二叉樹中，最多有2）-1個(gè)結(jié)點(diǎn)，最少有）個(gè)結(jié)點(diǎn)。~性質(zhì)~在一棵二叉樹中，如果葉子結(jié)點(diǎn)的個(gè)數(shù)為，度為的結(jié)點(diǎn)個(gè)數(shù)為，貝q=+i性質(zhì)具有個(gè)結(jié)點(diǎn)的完全二叉樹的深度為hog2n」+1。性質(zhì)對(duì)一棵具有個(gè)結(jié)點(diǎn)的完全二叉樹中的結(jié)點(diǎn)從開始按層序編號(hào)，則對(duì)于任意的編號(hào)為（WW）的結(jié)點(diǎn)（簡稱為結(jié)點(diǎn)），有：⑴如果>,則結(jié)點(diǎn)的雙親的編號(hào)為l_i/2」；否則結(jié)點(diǎn)是根結(jié)點(diǎn)，無雙親；⑵如果W,則結(jié)點(diǎn)的左孩子的編號(hào)為；否則結(jié)點(diǎn)無左孩子；⑶如果+W,則結(jié)點(diǎn)的右孩子的編號(hào)為+；否則結(jié)點(diǎn)無右孩子。>二叉樹的存儲(chǔ)包括：二叉樹的順序存儲(chǔ)和二叉樹的鏈?zhǔn)酱鎯?chǔ)。二叉鏈表的存儲(chǔ)結(jié)構(gòu)定義如下：表示二叉鏈表的頭指針指向該結(jié)點(diǎn)的雙親三叉鏈表的頭指針遍歷的含義所謂遍歷就是無重復(fù)無遺漏地訪問。二叉樹的遍歷是指從根結(jié)點(diǎn)出發(fā)，按照某種次序訪問二叉樹中的所有結(jié)點(diǎn)，使得每個(gè)結(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)的右子樹；⑶訪問根結(jié)點(diǎn)。層序遍歷二叉樹的層序遍歷是從二叉樹的第一層（根結(jié)點(diǎn)）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問。線索二叉樹的定義在一個(gè)具有個(gè)結(jié)點(diǎn)的二叉鏈表中，利用個(gè)空指針域存放指向該結(jié)點(diǎn)在某種遍歷序列中的前驅(qū)和后繼結(jié)點(diǎn)的指針，這些指向前驅(qū)和后繼結(jié)點(diǎn)的指針稱為線索，加上線索的二叉樹稱為線索二叉樹，相應(yīng)地，加上線索的二叉鏈表稱為線索鏈表。線索二叉樹的存儲(chǔ)結(jié)構(gòu)定義線索鏈表中的結(jié)點(diǎn)定義如下：枚舉類型，枚舉常量 ，表示不確定的數(shù)據(jù)類型表示線索鏈表的頭指針>樹的存儲(chǔ)結(jié)構(gòu)包括：雙親表示法、孩子表示法、孩子兄弟表示法。雙親表示法的存儲(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)定義如下：孩子結(jié)點(diǎn)表頭結(jié)點(diǎn)指向孩子鏈表的頭指針孩子兄弟表示法又稱為二叉鏈表表示法，存儲(chǔ)結(jié)構(gòu)定義如下表示不確定的數(shù)據(jù)類型指向該結(jié)點(diǎn)的第一個(gè)孩子指向該結(jié)點(diǎn)的右兄弟>樹轉(zhuǎn)換為二叉樹樹轉(zhuǎn)換為二叉樹的方法是：精彩文檔~⑴加線——樹中所有相鄰兄弟結(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)換為二叉樹的方法如下：⑴將森林中的每棵樹轉(zhuǎn)換成二叉樹；⑵從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹連起來后，所得到的二叉樹就是由森林轉(zhuǎn)換的二叉樹。>二叉樹轉(zhuǎn)換為樹或森林樹和森林轉(zhuǎn)換為二叉樹的過程是可逆的，將一棵二叉樹還原為樹或森林的方法如下：⑴加線一一若某結(jié)點(diǎn)是其雙親的左孩子，則把結(jié)點(diǎn)的右孩子、右孩子的右孩子、……，都與結(jié)點(diǎn)用線連起來；⑵去線一一刪去原二叉樹中所有的雙親結(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)值葉子結(jié)點(diǎn)的權(quán)值是指對(duì)葉子結(jié)點(diǎn)賦予的一個(gè)有意義的數(shù)值量。二叉樹的帶權(quán)路徑長度設(shè)二叉樹具有個(gè)帶權(quán)值的葉子結(jié)點(diǎn)，從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長度與相應(yīng)葉子結(jié)點(diǎn)權(quán)值的乘積之和稱做二叉樹的帶權(quán)路徑長度，記為：nWP=L€wklkk二1其中，為第個(gè)葉子結(jié)點(diǎn)的權(quán)值；為從根結(jié)點(diǎn)到第個(gè)葉子結(jié)點(diǎn)的路徑長度。哈夫曼樹定義給定一組具有確定權(quán)值的葉子結(jié)點(diǎn)，可以構(gòu)造出不同的二叉樹，將其中帶權(quán)路徑長度最小的二叉樹稱為哈夫曼樹，也稱為最優(yōu)二叉樹。哈夫曼算法的基本思想哈夫曼算法的基本思想是：⑴初始化：由給定的個(gè)權(quán)值，，…，構(gòu)造棵只有一個(gè)根結(jié)點(diǎn)的二叉樹，從而得到一個(gè)二叉樹集合=,，…， ;⑵選取與合并：在中選取根結(jié)點(diǎn)的權(quán)值最小的兩棵二叉樹分別作為左、右子樹構(gòu)造一棵新的二叉樹,這棵新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和；（3） 刪除與加入：在中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到中；（4） 重復(fù)⑵、⑶兩步，當(dāng)集合中只剩下一棵二叉樹時(shí)，這棵二叉樹便是哈夫曼樹。圖的定義圖是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為：=（，）其中，表示一個(gè)圖，是圖中頂點(diǎn)的集合，是圖中頂點(diǎn)之間邊的集合。

無向圖與有向圖若頂點(diǎn)和之間的邊沒有方向，則稱這條邊為無向邊，用無序偶對(duì)，來表示；若從頂點(diǎn)到的邊有方向，則稱這條邊為有向邊（也稱為?。?，用有序偶對(duì) 來表示，稱為弧尾，稱為弧頭。如果圖的任意兩個(gè)頂點(diǎn)之間的邊都是無向邊，則稱該圖為無向圖，否則稱該圖為有向圖。簡單圖若不存在頂點(diǎn)到其自身的邊，且同一條邊不重復(fù)出現(xiàn)，則稱這樣的圖為簡單圖。>鄰接、依附在無向圖中，對(duì)于任意兩個(gè)頂點(diǎn)和，若存在邊，）則稱頂點(diǎn)和互為鄰接點(diǎn)，同時(shí)稱邊, 依附于頂點(diǎn)和。在有向圖中，對(duì)于任意兩個(gè)頂點(diǎn)和，若存在弧， >則稱頂點(diǎn)是的鄰接點(diǎn)，同時(shí)稱弧，依附于頂點(diǎn)和。A無向完全圖、有向完全圖在無向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在邊，則稱該圖為無向完全圖。含有個(gè)頂點(diǎn)的無向完全圖有X 條邊。在有向圖中，如果任意兩頂點(diǎn)之間都存在方向互為相反的兩條弧，則稱該圖為有向完全圖。含有個(gè)頂點(diǎn)的有向完全圖有X條邊。稠密圖、稀疏圖稱邊數(shù)很少的圖為稀疏圖，反之，稱為稠密圖。頂點(diǎn)的度、入度、出度在無向圖中，頂點(diǎn)的度是指依附于該頂點(diǎn)的邊的個(gè)數(shù)，記為 。在具有個(gè)頂點(diǎn)條邊的無向圖中，有下式成立：nZTD⑴）=2ei€1在有向圖中，頂點(diǎn)的入度是指以該頂點(diǎn)為弧頭的弧的個(gè)數(shù)，記為 ；頂點(diǎn)的出度是指以該頂點(diǎn)為弧尾的弧的個(gè)數(shù)，記為 。在具有個(gè)頂點(diǎn)條邊的有向圖中，有下式成立：nnZID（v.）€EOD（v.）€ei€1 i€1連通圖、連通分量在無向圖中，若任意頂點(diǎn)和壬之間有路徑，則稱該圖是連通圖。非連通圖的極大連通子圖稱為連通分量。強(qiáng)連通圖、強(qiáng)連通分量在有向圖中，對(duì)任意頂點(diǎn)和壬）若從頂點(diǎn)到和從頂點(diǎn)到均有路徑，則稱該有向圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖稱為強(qiáng)連通分量。鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義假設(shè)圖=V有個(gè)頂點(diǎn)，則鄰接矩陣是一個(gè)X的方陣，定義為：T若v.,v.GE或vv.,v>WE昨滬仁否則― ―鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義如下：存放圖中頂點(diǎn)的信息,表示不確定的數(shù)據(jù)類型

存放圖中頂點(diǎn)的信息,表示不確定的數(shù)據(jù)類型存放圖中邊的信息

圖的頂點(diǎn)數(shù)和邊數(shù)>鄰接表的存儲(chǔ)結(jié)構(gòu)定義鄰接表是一種順序存儲(chǔ)與鏈接存儲(chǔ)相結(jié)合的存儲(chǔ)方法，具體方法為：將頂點(diǎn)的所有鄰接點(diǎn)鏈成一個(gè)單鏈表，稱為頂點(diǎn)的邊表（對(duì)于有向圖則稱為出邊表），邊表的頭指針和頂點(diǎn)的數(shù)據(jù)信息采用順序存儲(chǔ)（稱為頂點(diǎn)表）。所以，在鄰接表中存在兩種結(jié)點(diǎn)：頂點(diǎn)表結(jié)點(diǎn)和邊表結(jié)點(diǎn)。vertexfirstedgevertexfirstedgeadjvexnext頂點(diǎn)表結(jié)點(diǎn) 邊表結(jié)點(diǎn)鄰接表表示的結(jié)點(diǎn)結(jié)構(gòu)其中， ：數(shù)據(jù)域，存放頂點(diǎn)信息；:指針域，邊表的頭指針；:鄰接點(diǎn)域，存放邊該頂點(diǎn)的鄰接點(diǎn)在頂點(diǎn)表中的下標(biāo);e指針域，指向邊表中的下一個(gè)結(jié)點(diǎn)。鄰接表的存儲(chǔ)結(jié)構(gòu)定義如下：定義邊表結(jié)點(diǎn)鄰接點(diǎn)域定義頂點(diǎn)表結(jié)點(diǎn)表示不確定的數(shù)據(jù)類型頂點(diǎn)表圖的頂點(diǎn)數(shù)和邊數(shù)圖的遍歷次序定義深度優(yōu)先遍歷從圖中某頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷的基本思想是：訪問頂點(diǎn)；從的未被訪問的鄰接點(diǎn)中選取一個(gè)頂點(diǎn)，從出發(fā)進(jìn)行深度優(yōu)先遍歷；重復(fù)上述兩步，直至圖中所有和有路徑相通的頂點(diǎn)都被訪問到。廣度優(yōu)先遍歷從圖中某頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先遍歷的基本思想是：訪問頂點(diǎn)；依次訪問的各個(gè)未被訪問的鄰接點(diǎn)，，……,；分別從，，…，出發(fā)依次訪問它們未被訪問的鄰接點(diǎn)，直至圖中所有與頂點(diǎn)有路徑相通的頂點(diǎn)都被訪問到。最小生成樹的定義~設(shè) V~是一個(gè)無向連通網(wǎng)，生成樹上各邊的權(quán)值之和稱為該生成樹的代價(jià)，在的所有生成樹中,代價(jià)最小的生成樹稱為最小生成樹。普里姆（ ）算法的基本思想設(shè)V是一個(gè)無向連通網(wǎng)，令 ，是的最小生成樹。的初始狀態(tài)為 （W）,｝然后重復(fù)執(zhí)行下述操作：在所有eU￡的邊中找一條代價(jià)最小的邊，并入邊集，同時(shí)并入頂點(diǎn)集，直至為止?？唆斔箍枺?）算法的基本思想設(shè)無向連通網(wǎng)為=V，令的最小生成樹為，，其初態(tài)為=V ｛然后按照邊的權(quán)值由小到大的順序，依次考察邊集中的各條邊。若被考察邊的兩個(gè)頂點(diǎn)屬于的兩個(gè)不同的連通分量,則將此邊加入到中，同時(shí)把兩個(gè)連通分量連接為一個(gè)連通分量；若被考察邊的兩個(gè)頂點(diǎn)屬于同一個(gè)連通分量，則舍去此邊，以免造成回路。如此下去，當(dāng)中的連通分量個(gè)數(shù)為時(shí)，此連通分量便為的一棵最小生成樹。>迪杰斯特拉（ ）算法的基本思想設(shè)置集合存放已經(jīng)找到最短路徑的頂點(diǎn)，的初始狀態(tài)只包含源點(diǎn)，對(duì)e，假設(shè)從源點(diǎn)到的有向邊為最短路徑。以后每求得一條最短路徑…，就將加入集合中，并將路徑…與原來的假設(shè)相比較，取路徑長度較小者為當(dāng)前最短路徑。重復(fù)上述過程，直到集合中全部頂點(diǎn)加入到集合中。算法的基本思想假設(shè)從到的?。ㄈ魪牡降幕〔淮嬖冢瑒t將其弧的權(quán)值看成8）是最短路徑，然后進(jìn)行次試

探。若 …和… 分別是從到和從到中間頂點(diǎn)的序號(hào)不大于 的最短路徑，則將 和已經(jīng)得到的從到中間頂點(diǎn)的序號(hào)不大于 的最短路徑相比較，取長度較短者為從到中間頂點(diǎn)的序號(hào)不大于的最短路徑。網(wǎng)的定義在一個(gè)表示工程的有向圖中，用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)之間的優(yōu)先關(guān)系，稱這樣的有向圖為頂點(diǎn)表示活動(dòng)的網(wǎng)，簡稱網(wǎng)。>拓?fù)湫蛄械亩x設(shè)V是一個(gè)具有個(gè)頂點(diǎn)的有向圖，中的頂點(diǎn)序列 …稱為一個(gè)拓?fù)湫蛄?，?dāng)且僅當(dāng)滿足下列條件：若從頂點(diǎn)到有一條路徑，則在頂點(diǎn)序列中頂點(diǎn)必在頂點(diǎn)之前。拓?fù)渑判虻幕舅枷雽?duì) 網(wǎng)進(jìn)行拓?fù)渑判虻幕舅枷胧牵孩艔木W(wǎng)中選擇一個(gè)沒有前驅(qū)的頂點(diǎn)并且輸出它；⑵從網(wǎng)中刪去該頂點(diǎn)，并且刪去所有以該頂點(diǎn)為尾的??；⑶重復(fù)上述兩步，直到全部頂點(diǎn)都被輸出，或 網(wǎng)中不存在沒有前驅(qū)的頂點(diǎn)。>查找算法的時(shí)間性能查找算法用關(guān)鍵碼的比較次數(shù)來度量查找算法的時(shí)間性能。對(duì)于查找成功的情況，將關(guān)鍵碼比較次數(shù)的數(shù)學(xué)期望值定義為平均查找長度，即：n=€p.c.iii=1其中，表示問題規(guī)模，即查找集合中的記錄個(gè)數(shù)；表示查找第個(gè)記錄的概率；表示查找第個(gè)記錄所需的關(guān)鍵碼的比較次數(shù)。>順序查找算法的時(shí)間復(fù)雜度對(duì)于具有個(gè)記錄的順序表，查找第個(gè)記錄時(shí)，需進(jìn)行 次關(guān)鍵碼的比較。設(shè)每個(gè)記錄的查找概率相等，查找成功時(shí)，順序查找的平均查找長度為：；查找不成功時(shí)，關(guān)鍵碼的比較次數(shù)是次,精彩文檔則查找失敗的平均查找長度為 ）順序查找的適用情況順序查找對(duì)表中記錄的存儲(chǔ)沒有任何要求，順序存儲(chǔ)和鏈接存儲(chǔ)均可應(yīng)用；對(duì)表中記錄的有序性也沒有要求，無論記錄是否按關(guān)鍵碼有序均可應(yīng)用。>折半查找的適用情況折半查找（也稱對(duì)半查找、對(duì)分查找、二分查找）要求線性表中的記錄必須按關(guān)鍵碼有序，并且必須采用順序存儲(chǔ)。折半查找的基本思想取有序表的中間記錄作為比較對(duì)象，則（1） 若給定值與中間記錄的關(guān)鍵碼相等，則查找成功；（2） 若給定值小于中間記錄的關(guān)鍵碼，則在中間記錄的左半?yún)^(qū)繼續(xù)查找；（3） 若給定值大于中間記錄的關(guān)鍵碼，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過程，直到查找成功，或所查找的區(qū)域無記錄，查找失敗。折半查找的時(shí)間復(fù)雜度具有個(gè)結(jié)點(diǎn)的折半查找判定樹的深度為hog2n」+1。最好情況：比較1次，即查找的關(guān)鍵碼是判定樹的根結(jié)點(diǎn)；最壞情況：比較次數(shù)為€log2n」+1，即查找的關(guān)鍵碼是判定樹的最下一層結(jié)點(diǎn)；平均情況：折半查找的平均時(shí)間復(fù)雜度為 2。|查找不成功的比較次數(shù)最多不超過樹的深度，最多為€log2n」+l次。二叉排序樹的定義二叉排序樹或者是一棵空的二叉樹，或者是具有下列性質(zhì)的二叉樹：⑴若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；⑵若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；⑶它的左右子樹也都是二叉排序樹。二叉排序樹的查找性能如果二叉排序樹是平衡的，則其查找效率為 。如果二叉排序樹為一棵斜樹，則其查找效率為）因此，二叉排序樹的查找性能在 和之間。平衡二叉樹的定義平衡二叉樹或者是一棵空的二叉排序樹，或者是具有下列性質(zhì)的二叉排序樹：⑴根結(jié)點(diǎn)的左子樹和右子樹的深度最多相差1。⑵根結(jié)點(diǎn)的左子樹和右子樹也都是平衡二叉樹。構(gòu)造平衡二叉樹的基本思想在構(gòu)造二叉排序樹的過程中，每當(dāng)插入一個(gè)結(jié)點(diǎn)時(shí)，首先檢查是否因插入而破壞了樹的平衡性，若是則找出最小不平衡子樹，在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點(diǎn)之間的鏈接關(guān)系進(jìn)行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹。平衡調(diào)整的四種類型設(shè)結(jié)點(diǎn)為最小不平衡子樹的根結(jié)點(diǎn)，對(duì)該子樹進(jìn)行平衡化調(diào)整有以下四種情況:⑴型：結(jié)點(diǎn)插在根結(jié)點(diǎn)⑵型：結(jié)點(diǎn)插在根結(jié)點(diǎn)⑶型：結(jié)點(diǎn)插在根結(jié)點(diǎn)⑷型：結(jié)點(diǎn)插在根結(jié)點(diǎn)的左孩子的左子樹上。的右孩子的右子樹上的左孩子的右子樹上的右孩子的左子樹上。散列查找的基本思想散列查找也稱為哈希查找、查找，其基本思想是：在記錄的存儲(chǔ)位置和它的關(guān)鍵碼之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系，使得每個(gè)關(guān)鍵碼和唯一的一個(gè)存儲(chǔ)位置 相對(duì)應(yīng)。在查找時(shí)，根據(jù)這個(gè)確定的對(duì)應(yīng)關(guān)系找到給定值的映射，若查找集合中存在這個(gè)記錄，則必定在的位置上。散列查找的基本概念采用散列技術(shù)將記錄存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間中，這塊連續(xù)的存儲(chǔ)空間稱為散列表，將關(guān)鍵碼映射為散列表中適當(dāng)存儲(chǔ)位置的函數(shù)稱為散列函數(shù)，所得的存儲(chǔ)位置址稱為散列地址。對(duì)于兩個(gè)不同的關(guān)鍵碼壬，有= ）即兩個(gè)不同的記錄需要存放在同一個(gè)存儲(chǔ)位置，這種現(xiàn)象稱為沖突，和相對(duì)于稱做同義詞。>散列查找的關(guān)鍵問題采用散列技術(shù)需要考慮的兩個(gè)關(guān)鍵問題是：⑴散列函數(shù)的設(shè)計(jì)。如何設(shè)計(jì)一個(gè)簡單、均勻、存儲(chǔ)利用率高的散列函數(shù)。⑵沖突的處理。如何采取合適的處理沖突方法來解決沖突。處理沖突的方法開放定址法用開放定址法處理沖突得到的散列表叫做閉散列表。所謂開放定址法，就是由關(guān)鍵碼得到的散列地址一旦產(chǎn)生了沖突，就去尋找下一個(gè)空的散列地址，只要散列表足夠大，空的散列地址總能找到，并將記錄存入。線性探測(cè)法當(dāng)發(fā)生沖突時(shí)，線性探測(cè)法從沖突位置的下一個(gè)位置起，依次尋找空的散列地址，即對(duì)于鍵值，設(shè)，閉散列表的長度為，則發(fā)生沖突時(shí)，尋找下一個(gè)散列地址的公式為：+（,,■■■,）。線性探測(cè)法會(huì)出現(xiàn)非同義詞之間對(duì)同一個(gè)散列地址爭奪的現(xiàn)象，稱為堆積或聚集。二次探測(cè)法當(dāng)發(fā)生沖突時(shí),二次探測(cè)法尋找下一個(gè)散列地址的公式為：+ （ ,…， ，一且W2隨機(jī)探測(cè)法當(dāng)發(fā)生沖突時(shí),隨機(jī)探測(cè)法探測(cè)下一個(gè)散列地址的位移量是一個(gè)隨機(jī)數(shù)列,即尋找下一個(gè)散列地址的公式為：（是一個(gè)隨機(jī)數(shù)列， ，，……, ）拉鏈法（鏈地址法）用拉鏈法處理沖突構(gòu)造的散列表叫做開散列表。拉鏈法的基本思想是：將所有散列地址相同的記錄,即所有關(guān)鍵碼為同義詞的記錄存儲(chǔ)在一個(gè)單鏈表中——稱為同義詞子表,在散列表中存儲(chǔ)的是所有同義詞子表的頭指針。直接插入排序的基本思想直接插入排序的基本思想是：依次將待排序序列中的每一個(gè)記錄插入到一個(gè)已排好序的序列中,直到全部記錄都排好序。>直接插入排序算法的性能?時(shí)間性能最好情況：待排序序列為正序，時(shí)間復(fù)雜度為；最壞情況：待排序序列為逆序，時(shí)間復(fù)雜度為)平均情況：待排序序列中各種可能排列的概率相同，時(shí)間復(fù)雜度為 。■空間性能直接插入排序只需要一個(gè)記錄的輔助空間。?穩(wěn)定性直接插入排序是一種穩(wěn)定的排序方法。希爾排序的基本思想希爾排序的基本思想是：先將整個(gè)待排序記錄序列分割成若干個(gè)子序列，在子序列內(nèi)分別進(jìn)行直接插入排序，待整個(gè)序列基本有序時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。>希爾排序算法的性能?時(shí)間性能希爾排序算法的時(shí)間性能是所取增量的函數(shù)，其時(shí)間性能在 和