《數(shù)據(jù)結(jié)構(gòu)(C語言版)》復(fù)習(xí)重點(diǎn)

./《數(shù)據(jù)結(jié)構(gòu)<C語言版>》復(fù)習(xí)重點(diǎn)重點(diǎn)在二、三、六、七、九、十章,考試容兩大類：概念,算法第1章、緒論1.數(shù)據(jù)：是對(duì)客觀事物的符號(hào)表示,在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。2.數(shù)據(jù)元素：是數(shù)據(jù)的基本單位,在計(jì)算機(jī)程序常作為一個(gè)整體進(jìn)行考慮和處理。3.數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。其4類基本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)4.邏輯結(jié)構(gòu)：是數(shù)據(jù)元素之間的邏輯關(guān)系的描述。5.物理結(jié)構(gòu)〔存儲(chǔ)結(jié)構(gòu)：是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示〔又稱映像。其4種存儲(chǔ)結(jié)構(gòu)：順序存數(shù)結(jié)構(gòu)、鏈?zhǔn)酱鏀?shù)結(jié)構(gòu)、索引存數(shù)結(jié)構(gòu)、散列存數(shù)結(jié)構(gòu)6.算法：是對(duì)特定問題求解步驟的一種描述,它是指令的有限序列,其中每一條指令表示一個(gè)或多個(gè)操作。其5個(gè)重要特性：有窮性、確定性、可行性、輸入、輸出7.時(shí)間復(fù)雜度：算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f<n>,算法的時(shí)間度量記作,T<n>=O<f<n>>；他表示隨問題規(guī)模n的增大,算法執(zhí)行時(shí)間的增長率和f<n>的增長率相同,稱做算法的漸進(jìn)時(shí)間復(fù)雜度,簡(jiǎn)稱時(shí)間復(fù)雜度。例如：<a>{++x;s=0;}<b>for<i=1;i<=n;++i>{++x;s+=x;}<c>for<j=1;j<=n;++j> for<k=1;k<=n;++k>{++x;s+=x;}含基本操作"x增1"的語句的頻度分別為1、n和n2,則這3個(gè)程序段的時(shí)間復(fù)雜度分別為O<1>、O<n>和O<n2>,分別稱為常量階、線性階和平方階。還可呈現(xiàn)對(duì)數(shù)階O<logn>、指數(shù)階O<2的n次方>等。8.空間復(fù)雜度：算法所需存儲(chǔ)空間的度量記作,S<n>=O<f<n>>。第2章、線性表1.線性表：是最常用最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu),一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列。2.線性表的順序存儲(chǔ)結(jié)構(gòu)：是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。其特點(diǎn)為邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上也相鄰,可以隨機(jī)存取表中任一元素。存儲(chǔ)位置計(jì)算：假設(shè)線性表的每個(gè)元素需占用L個(gè)存儲(chǔ)單元,并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置,線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為LOC<ai>=LOC<a1>+<i-1>*L式中LOC<a1>是線性表第一個(gè)元素a1的存儲(chǔ)位置,通常稱做線性表的起始位置或基地址。3.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素<這組存儲(chǔ)單元可以是連續(xù)的,也可以是不連續(xù)的>。數(shù)據(jù)元素ai的存儲(chǔ)映像稱為結(jié)點(diǎn),包括2個(gè)域：存數(shù)據(jù)的數(shù)據(jù)域、存后繼存儲(chǔ)位置的指針域。1>線性鏈表<單鏈表>特點(diǎn)：每個(gè)結(jié)點(diǎn)只包含1個(gè)指針域。在單鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn),稱之為頭結(jié)點(diǎn)。假設(shè)L是LinkList型變量,則L為單鏈表的頭指針,它指向表中第一個(gè)結(jié)點(diǎn)；L->next為第一個(gè)結(jié)點(diǎn)地址,L->next=NULL為空表。生成結(jié)點(diǎn)：p=<LinkList>malloc<sizeof<LNode>>回收結(jié)點(diǎn)：free<q>2>循環(huán)鏈表特點(diǎn)：表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn),整個(gè)鏈表形成一個(gè)環(huán)。循環(huán)鏈表的操作與線性鏈表基本一致,差別僅在于算法中的循環(huán)條件不是P或P->next是否為空,而是它們是否等于頭指針。3>雙向鏈表特點(diǎn)：有2個(gè)指針域,其一指向直接后繼,另一指向直接前趨。第3章、棧和隊(duì)列1.棧：是限定僅在表尾進(jìn)行插入或刪除操作的線性表。表尾端稱為棧頂,表頭端稱為棧底,不含有元素的空表稱為空棧；棧又稱為后進(jìn)先出的線性表。2.隊(duì)列：是一種先進(jìn)先出的線性表,它只允許在表的一端進(jìn)行插入,而另一端刪除元素。允許插入的一端叫做隊(duì)尾,允許刪除的一端則稱為隊(duì)頭。1>鏈隊(duì)列：用鏈表示的隊(duì)列。一個(gè)隊(duì)列需要兩個(gè)分別指示隊(duì)頭和隊(duì)尾的指針〔分別成為頭指針和尾指針才能確定唯一。和單鏈表一樣,也給鏈隊(duì)列添加一個(gè)頭結(jié)點(diǎn),并令頭指針指向頭結(jié)點(diǎn)。2>循環(huán)隊(duì)列：與順序棧類似,除了用一組地址連續(xù)的存儲(chǔ)單元依次存放從隊(duì)列頭到隊(duì)列尾的元素之外,尚需附設(shè)兩個(gè)指針front和rear分別指示隊(duì)列頭元素及隊(duì)列尾元素的位置。初始化建空隊(duì)列時(shí),令front=rear=0,每當(dāng)插入新的隊(duì)列尾元素時(shí),"尾指針增1"；每當(dāng)刪除隊(duì)列頭元素時(shí),"頭指針增1"。第4章、串1.串：是由零個(gè)或多個(gè)字符組成的有限序列。第5章、數(shù)組和廣義表1.數(shù)組特點(diǎn)：與線性表一樣,所有數(shù)據(jù)元素都必須屬于同一數(shù)據(jù)類型。2.數(shù)組的順序存儲(chǔ)結(jié)構(gòu)：由于數(shù)組一般不作插入或刪除操作,一旦建立了數(shù)組,則結(jié)構(gòu)中的數(shù)據(jù)元素個(gè)數(shù)和元素之間的關(guān)系就不會(huì)發(fā)生變動(dòng),因此采用順序存儲(chǔ)結(jié)構(gòu)表示數(shù)組。存儲(chǔ)位置計(jì)算：假設(shè)每個(gè)數(shù)據(jù)元素需占用L個(gè)存儲(chǔ)單元,則二維數(shù)組A中任一元素aij的存儲(chǔ)位置可由下式確定以行序?yàn)橹餍虻拇鎯?chǔ)結(jié)構(gòu)：LOC<i,j>=LOC<0,0>+<b2*i+j>*L以列序?yàn)橹餍虻拇鎯?chǔ)結(jié)構(gòu)：LOC<i,j>=LOC<0,0>+<b2*j+i>*L式中LOC<i,j>是aij的存儲(chǔ)位置；LOC<0,0>是a00的存儲(chǔ)位置,即二維數(shù)組A的起始存儲(chǔ)位置,也稱基地址或基址；b2在以行序?yàn)橹餍虻拇鎯?chǔ)結(jié)構(gòu)時(shí)為每行存儲(chǔ)元素的個(gè)數(shù)<列數(shù)>,在以列序?yàn)橹餍虻拇鎯?chǔ)結(jié)構(gòu)時(shí)為每列存儲(chǔ)元素的個(gè)數(shù)<行數(shù)>。3.廣義表：是線性表的推廣,也有人稱其為列表〔lists,用復(fù)數(shù)形式以示與統(tǒng)稱的表list的區(qū)別。記作LS=<a1,a2,…an>,其中LS是廣義表<a1,a2,…an>的名稱,n是它的長度。在線性表的定義中,ai<1≤i≤n>只限于是單個(gè)元素。而在廣義表的定義中,ai可以是單個(gè)元素,也可以是廣義表,分別稱為廣義表LS的原子和子表。例如：第6章、樹和二叉樹1.二叉樹：是一種樹型的結(jié)構(gòu),它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有兩棵子樹〔即二叉樹中不存在度大于2的結(jié)點(diǎn),并且,二叉樹的子樹有左右之分,其次序不能任意顛倒。2.二叉樹的性質(zhì)：1>性質(zhì)1：在二叉樹的第i層上至多有2的i減1次方個(gè)結(jié)點(diǎn)<i≥1>。2>性質(zhì)2：深度為k的二叉樹至多有2的k次方減1個(gè)結(jié)點(diǎn)<k≥1>。深度為k的二叉樹至少有k個(gè)結(jié)點(diǎn)<k≥1>。深度為k的完全二叉樹至少有2的k次方減2的k減1次方個(gè)結(jié)點(diǎn)<k≥1>。3>性質(zhì)3：對(duì)任何一棵二叉樹T,如果其終端結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則n0=n2+1。4>性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1。5>性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹〔其深度為[log2n]+1的結(jié)點(diǎn)按層序編號(hào)〔從第1層到第[log2n]+1層,每層從左到右,則對(duì)任一結(jié)點(diǎn)i〔1≤i≤n有：a>如果i=1,則結(jié)點(diǎn)i是二叉樹的根,無雙親；如果i>1,則其雙親PARENT<i>是結(jié)點(diǎn)[i/2]。b>如果2i>n,則結(jié)點(diǎn)i無左孩子〔結(jié)點(diǎn)i為葉子結(jié)點(diǎn)；否則其左孩子LCHILD<i>是結(jié)點(diǎn)2i。c>如果2i+1>n,則結(jié)點(diǎn)i無右孩子；否則其右孩子RCHILD<i>是結(jié)點(diǎn)2i+1。3.滿二叉樹：一顆深度為k且有2的k次方減1個(gè)結(jié)點(diǎn)的二叉樹。4.完全二叉樹：深度為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)。5.遍歷二叉樹：1>根據(jù)二叉樹寫遍歷結(jié)果：a>先序遍歷〔先根遍歷：DLR-+a*b-cd/efb>中序遍歷〔中根遍歷：LDRa+b*c-d-e/fc>后序遍歷〔后根遍歷：LRDabcd-*+ef/-2>根據(jù)遍歷結(jié)果畫二叉樹：一棵二叉樹的先序、中序和后序序列分別如下,其中有部分未給出,試求出空格處的結(jié)點(diǎn)字符,并畫出該二叉樹。先序：__B__EHI__FG__K中序：D__HEIA__CJG__后序：__H__EBF__KG__A解題思路：a>由先序或后序確定根結(jié)點(diǎn)；如本題后序最后一個(gè)為A,根結(jié)點(diǎn)為A,所以先序第一個(gè)空就為A。b>在中序找出根結(jié)點(diǎn),根結(jié)點(diǎn)左側(cè)為左子樹,右側(cè)為右子樹；如本題D__HEI為左子樹,__CJG__為右子樹。c>由先序確定緊跟在根結(jié)點(diǎn)后的左子樹根；如本題緊跟在A后的是B,B為左子樹根,中序根結(jié)點(diǎn)的左子樹只有一個(gè)空,所以為B。d>繼續(xù)由中序確定左子樹根的左右子樹,左側(cè)為左子樹,右側(cè)為右子樹；如本題B的左子樹為D,右子樹為HEI,所以先序第二個(gè)空為D。e>重復(fù)c>、d>步驟確定整棵左子樹；如本題先序中緊跟在D后的是E,E為B的右子樹,由中序中看出E左子樹為H,右子樹為I,補(bǔ)充后序填空,前兩空分別為D和I。f>由后序確定右子樹根的左子樹,再由中序確定右子樹根；如本題緊跟在B后的是F,F為右子樹根的左子樹,已知中序__CJG__為右子樹,F只可能第一個(gè)空,那第二個(gè)空為K,補(bǔ)全先序、中序、后序填空并可畫出二叉樹。6.森林與二叉樹的轉(zhuǎn)換：1>樹轉(zhuǎn)換成二叉樹：連兄弟,留長子,刪孩子。a>連線,連接所有兄弟結(jié)點(diǎn)。b>刪線,僅保留雙親與長子結(jié)點(diǎn)的連線,刪除與其他孩子結(jié)點(diǎn)之間的連線。c>整理,原有的長子結(jié)點(diǎn)為左子樹,從兄弟轉(zhuǎn)換為孩子的結(jié)點(diǎn)為右子樹。d>注意,由于樹根沒有兄弟結(jié)點(diǎn),固樹轉(zhuǎn)換為二叉樹后,二叉樹根結(jié)點(diǎn)的右子樹必為空。2>森林轉(zhuǎn)換成二叉樹：連樹根及兄弟,留長子,刪孩子。a>連線,連接每棵樹的根結(jié)點(diǎn)及所有兄弟結(jié)點(diǎn)。b>刪線,僅保留雙親與長子結(jié)點(diǎn)的連線,刪除與其他孩子結(jié)點(diǎn)之間的連線。c>整理,第一棵樹根結(jié)點(diǎn)為二叉樹根結(jié)點(diǎn),原有的長子結(jié)點(diǎn)為左子樹,從兄弟轉(zhuǎn)換為孩子的結(jié)點(diǎn)為右子樹。3>二叉樹轉(zhuǎn)換成樹：連左孩子的右孩子及其右孩子…,刪原樹右孩子。a>連線,若某結(jié)點(diǎn)X存在左孩子XL,則將這個(gè)左孩子的右孩子結(jié)點(diǎn)XLR、左孩子的右孩子的右孩子結(jié)點(diǎn)XLRR、左孩子的右孩子的右孩子的右孩子結(jié)點(diǎn)XLRRR…都與X結(jié)點(diǎn)連線。b>刪線,刪除原二叉樹的所有雙親與右孩子結(jié)點(diǎn)的連線。c>整理,原二叉樹根結(jié)點(diǎn)為樹根結(jié)點(diǎn)。4>二叉樹轉(zhuǎn)換成森林：連左孩子的右孩子及其右孩子…,刪原樹右孩子。a>連線,若某結(jié)點(diǎn)X存在左孩子XL,則將這個(gè)左孩子的右孩子結(jié)點(diǎn)XLR、左孩子的右孩子的右孩子結(jié)點(diǎn)XLRR、左孩子的右孩子的右孩子的右孩子結(jié)點(diǎn)XLRRR…都與X結(jié)點(diǎn)連線。b>刪線,刪除原二叉樹的所有雙親與右孩子結(jié)點(diǎn)的連線。c>整理,調(diào)整為多棵樹的森林。7.赫夫曼樹：又稱最優(yōu)樹,是一類帶權(quán)路徑長度最短的樹。a>兩個(gè)最小數(shù)值組成一對(duì),小的在前,大的在后；如上圖中2與4最小,2在前,4在后。b>將兩個(gè)最小數(shù)值的和算作一個(gè)數(shù),再與其他數(shù)重復(fù)a>步驟；如上圖中2與4的和為6,5與6最小,5在前,6在后。c>最后計(jì)算WPL,它等于每個(gè)數(shù)值乘以從根結(jié)點(diǎn)到這個(gè)數(shù)值的連線個(gè)數(shù)的積之和；如上圖中WPL=2*3+4*3+5*2+7*1=35。8.赫夫曼編碼：a>在赫夫曼樹上,左分支代表0,右分支代表1。b>由根結(jié)點(diǎn)到指定結(jié)點(diǎn)的路徑<從上到下把0、1連起來>,就是該結(jié)點(diǎn)的赫夫曼編碼；如上圖<d>中a為0,b為10,c為110,d為111。第7章、圖1.圖：多個(gè)結(jié)點(diǎn),結(jié)點(diǎn)之間的關(guān)系可以是任意的,圖中任意兩個(gè)數(shù)據(jù)元素之間都有可能相關(guān)。2.無向完全圖：有n<n-1>/2條邊的無向圖。3.有向完全圖：有n<n-1>條邊的有向圖。4.入度：以頂點(diǎn)V為頭的弧的數(shù)目稱為V的入度。5.出度：以V為尾的弧的數(shù)目稱為V的出度。6.連通圖：在無向圖中,任意兩個(gè)頂點(diǎn)之間都有路徑。7.連通分量：在無向圖中的極通子圖。8.鄰接矩陣：無向圖的鄰接矩陣關(guān)于主對(duì)角線對(duì)稱,在整個(gè)矩陣中非零元素的個(gè)數(shù)等于邊個(gè)數(shù)的2倍,第i行和第i列中非零元素的個(gè)數(shù)等于該結(jié)點(diǎn)的度。9.鄰接表：無向圖的鄰接矩陣關(guān)于主對(duì)角線對(duì)稱,在整個(gè)矩陣中非零元素的個(gè)數(shù)等于邊個(gè)數(shù)的2倍,第i行和第i列中非零元素的個(gè)數(shù)等于該結(jié)點(diǎn)的度。10.深度優(yōu)先遍歷：從圖中某個(gè)頂點(diǎn)出發(fā),搜索與之相關(guān)聯(lián)的頂點(diǎn),選擇一個(gè)訪問〔從左到右,從上到下；再從該頂點(diǎn)出發(fā),搜索與之相關(guān)聯(lián)且未訪問過的頂點(diǎn),選擇一個(gè)訪問；重復(fù)上步驟,直到?jīng)]有相關(guān)聯(lián)且未訪問過的頂點(diǎn)；后退一個(gè)頂點(diǎn)繼續(xù)搜索訪問,直到所有頂點(diǎn)都被訪問過。a>從V0出發(fā),先找到V0的關(guān)聯(lián)頂點(diǎn)V3。b>由V3出發(fā),找到V1；由V1出發(fā),沒有關(guān)聯(lián)的頂點(diǎn)。c>回到V3,從V3出發(fā),找到V2；由V2出發(fā),沒有關(guān)聯(lián)的頂點(diǎn)。d>回到V3,再回到V0,由V0出發(fā),找到V4。e>從V4出發(fā),找到V1,因?yàn)閂1已經(jīng)被訪問過了,所以不訪問。所以最后順序是V0,V3,V1,V2,V4。11.廣度優(yōu)先遍歷：從圖中某個(gè)頂點(diǎn)出發(fā),搜索與之相關(guān)聯(lián)的頂點(diǎn),逐個(gè)訪問〔從左到右,從上到下；再從這些頂點(diǎn)出發(fā),搜索與之相關(guān)聯(lián)且未訪問過的頂點(diǎn),逐個(gè)訪問；重復(fù)上步驟,直到所有頂點(diǎn)都被訪問過。a>從V0出發(fā),先找到V0的關(guān)聯(lián)頂點(diǎn)V3、V4。b>由V3出發(fā),找到V1、V2；由V4出發(fā),找到V1,因?yàn)閂1已經(jīng)被訪問過了,所以不訪問。c>由V1出發(fā),沒有關(guān)聯(lián)的頂點(diǎn)；由V2出發(fā),沒有關(guān)聯(lián)的頂點(diǎn)。所以最后順序是V0,V3,V4,V1,V2。12.最小生成樹：1>普里姆算法：連相鄰權(quán)值最小的。2>克魯斯卡爾算法：先連權(quán)值最小的,再依次連。13.拓?fù)渑判颍河赡硞€(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序的操作。14.關(guān)鍵路徑：路徑長度最長的路徑。1>如圖,先求各事件的最早發(fā)生時(shí)間〔順序?yàn)閂1~V9V1的最早發(fā)生時(shí)間為0,V2的最早發(fā)生時(shí)間為6,V3的最早發(fā)生時(shí)間為4,V4的最早發(fā)生時(shí)間為5。對(duì)于V5,需要V2,V3均發(fā)生,V2發(fā)生且完成的時(shí)間為6+1=7；V3發(fā)生且完成的時(shí)間為4+1=5,因而V5的最早發(fā)生時(shí)間為7。同理可求出各頂點(diǎn)的最早發(fā)生時(shí)間：V1V2V3V4V5V6V7V8V9e<i>0645771614182>求各事件的最晚發(fā)生時(shí)間〔順序?yàn)閂9~V1V9的最晚時(shí)間為18,V8的最晚時(shí)間為18-a11=14,V7的最晚時(shí)間為18-a10=16,V6的最晚時(shí)間為14-a9=10,V5的最晚時(shí)間為V7的最晚時(shí)間減去a7和V8的最晚時(shí)間減去a8兩者較小的,則V5的最晚時(shí)間為7,同理可得其他頂點(diǎn)的最晚發(fā)生時(shí)間：V1V2V3V4V5V6V7V8V9l<i> 0 668710161418則l[i]與e[i]相等的事件即為關(guān)鍵事件即：V1,V2,V5,V7,V8,V9可得關(guān)鍵路徑：V1,V2,V5,V7,V9或V1,V2,V5,V8,V93>求各活動(dòng)的最早發(fā)生時(shí)間a1a2a3a4a5a6a7a8a9a10a11e<i>00064577716144>求各活動(dòng)的最晚發(fā)生時(shí)間a1a2a3a4a5a6a7a8a9a10a11l<i>6-6=06-4=28-5=37-1=67-1=610-2=816-9=714-7=714-4=1018-2=1618-4=14則l[i]與e[i]相等的活動(dòng)即為關(guān)鍵活動(dòng)即：a1,a4,a7,a8,a10,a11可得關(guān)鍵路徑：V1,V2,V5,V7,V9或V1,V2,V5,V8,V915.最短路徑：從某頂點(diǎn)出發(fā),沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中,各邊上權(quán)值之和最小的一條路徑。1>迪杰斯特拉算法：2>弗洛伊德算法：方法：兩條線,從左上角開始計(jì)算一直到右下角如下所示：給出矩陣,其中矩陣A是鄰接矩陣,而矩陣Path記錄u,v兩點(diǎn)之間最短路徑所必須經(jīng)過的點(diǎn)。最后A3即為所求結(jié)果。第9章、查找1.查找表：是由同一類型的數(shù)據(jù)元素〔或記錄構(gòu)成的集合。2.關(guān)鍵字：是數(shù)據(jù)元素〔或記錄中某個(gè)數(shù)據(jù)項(xiàng)的值,用它可以標(biāo)識(shí)〔識(shí)別一個(gè)數(shù)據(jù)元素〔或記錄。3.靜態(tài)查找表：查詢某個(gè)特定的數(shù)據(jù)元素是否在查找表中,檢索某個(gè)特定的數(shù)據(jù)元素的各種屬性。1>順序查找法：從表中最后一個(gè)記錄開始,逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值比較,若某個(gè)記錄的關(guān)鍵字和給定值比較相等,則查找成功,找到所查記錄；反之若直至第一個(gè)記錄,其關(guān)鍵字和給定值比較都不相等,則表明表中沒有所查記錄,查找不成功。其存儲(chǔ)結(jié)構(gòu)要求：以順序表或線性鏈表表示的靜態(tài)查找表。其平均查找長度：假設(shè)每個(gè)記錄的查找概率相等,即Pi=1/n,則在等概率情況下順序查找的平均查找長度為,ASL=<n+1>/2。2>折半查找法〔二分查找法：先確定待查記錄所在的圍〔區(qū)間,然后逐步縮小圍直到找到或找不到該記錄為止。其存儲(chǔ)結(jié)構(gòu)要求：以有序表表示的靜態(tài)查找表。其平均查找長度：假設(shè)表中每個(gè)記錄的查找概率相等〔Pi=1/n,則查找成功時(shí)折半查找的平均查找長度為,ASL=<n+1>/n*log2<n+1>-1。3>索引順序表查找法〔分塊查找法：先確定待查記錄所在的塊〔子表,然后在塊中順序查找。其存儲(chǔ)結(jié)構(gòu)要求：以索引順序表表示的靜態(tài)查找表。其平均查找長度：將長度為n的表均勻地分成b塊,每塊含有s個(gè)記錄,即b=[n/s]；又假設(shè)表中每個(gè)記錄的查找概率相等,則每塊查找概率為1/b,塊中每個(gè)記錄的查找概率為1/s,若用順序查找確定所在塊,則分塊查找的平均查找長度為,ASL=<n/s+s>/2+1；若用折半查找確定所在塊,則分塊查找的平均查找長度為,ASL≈log2<n/s+1>+s/2。4.動(dòng)態(tài)查找表：在查找過程中同時(shí)插入查找表中不存在的數(shù)據(jù)元素,或者從查找表中刪除已存在的某個(gè)數(shù)據(jù)元素。1>二叉排序樹：或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：1、若它的左子樹不空,則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；2、若它的右子樹不空,則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；3、它的左、右子樹也分別為二叉排序樹。2>平衡二叉樹〔AVL樹：它或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹,且左子樹和右子樹的深度之差的絕對(duì)值不超過1。若將二叉樹上結(jié)點(diǎn)的平衡因子BF定義為該結(jié)點(diǎn)的左子樹的深度減去它的右子樹的深度,則平衡二叉樹上所有結(jié)點(diǎn)的平衡因子只可能是-1、0和1。只要二叉樹上有一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1,則該二叉樹就是不平衡的。下面即四種情況分別為：左左、右右、左右、右左,每種情況又有兩個(gè)圖①、②,①是該情況的最簡(jiǎn)單的圖形,②是該情況的一般的圖形。設(shè)x為最小不平衡子樹的根結(jié)點(diǎn),y為剛插入的點(diǎn)左左：即在x的左孩子a的左孩子c上插入一個(gè)結(jié)點(diǎn)y〔該結(jié)點(diǎn)也可以是c,如圖①,即y可以是c,也可以是c的左孩子〔如圖②,也可以是c的右孩子〔不在畫出。圖①就不用說了,結(jié)點(diǎn)x和結(jié)點(diǎn)a變換,則樹平衡了；那么圖②就是樹中的一般情況了a結(jié)點(diǎn)有右孩子d,那要進(jìn)行x和a變換,那么a的右孩子放哪??？很簡(jiǎn)單,如圖放在x的左孩子上；分析：x>d,d>a,所以d可作為x的左孩子,且可作為a的右孩子中的孩子。下邊這樣的類似情況不再一一分析,自己分析分析~實(shí)現(xiàn)：找到根結(jié)點(diǎn)x,與它的左孩子a進(jìn)行交換即可使二叉樹樹再次平衡；右右：即在x的右孩子a的右孩子c上插入一個(gè)結(jié)點(diǎn)y〔該結(jié)點(diǎn)也可以是c,如圖①,即y可以是c,也可以是c的右孩子〔如圖②,也可以是c的左孩子〔不在畫出。實(shí)現(xiàn)：找到根結(jié)點(diǎn)x,與它的右孩子a進(jìn)行交換即可使二叉樹樹再次平衡；左右：即在x的左孩子a的右孩子c上插入一個(gè)結(jié)點(diǎn)y〔該結(jié)點(diǎn)也可以是c,如圖①,即y可以是c,也可以是c的右孩子〔如圖②,也可以是c的左孩子〔不在畫出。這個(gè)左右和下邊的右左,稍微復(fù)雜了點(diǎn),需要進(jìn)行兩次交換,才能達(dá)到平衡,注意這時(shí)y是c的右孩子,最終y作為x的左孩子；若y是c的左孩子,最終y作為a的右孩子,畫圖分析一下~~下邊類似,不再敖述。實(shí)現(xiàn)：找到根結(jié)點(diǎn)x,讓x的左孩子a與x的左孩子a的右孩子c進(jìn)行交換,然后再讓x與x此時(shí)的左孩子c進(jìn)行交換,最終達(dá)到平衡；右左：即在x的右孩子a的左孩子c上插入一個(gè)結(jié)點(diǎn)y〔該結(jié)點(diǎn)也可以是c,如圖①,即y可以是c,也可以是c的右孩子〔如圖②,也可以是c的左孩子〔不在畫出。實(shí)現(xiàn)：找到根結(jié)點(diǎn)x,讓x的右孩子a與x的右孩子a的左孩子c進(jìn)行交換,然后再讓x與x此時(shí)的右孩子c進(jìn)行交換,最終達(dá)到平衡；上邊的四種情況包含了所有插入時(shí)導(dǎo)致不平衡的情況,上面給出的僅僅是一棵大樹中的最小不平衡子樹,一定要想清楚,別迷了！另外一定要注意這個(gè)交換操作,比如a與b交換〔a在上,b在下,b一定要占據(jù)a的位置！什么意思？就是b要放在〔覆蓋儲(chǔ)存a的那塊存上,再通俗點(diǎn)說,若a是x的左孩子,則交換后b要做x的左孩子；這就是所謂的b占據(jù)a的位置！5.哈希表：1>構(gòu)造方法：a>直接定址法：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址。即H<key>=key或H<key>=a·key+b,其中a和b為常數(shù)〔這種散列函數(shù)叫做自身函數(shù)。若其中H<key中已經(jīng)有值了,就往下一個(gè)找,直到H<key中沒有值了,就放進(jìn)去。b>數(shù)字分析法：分析一組數(shù)據(jù),比如一組員工的出生年月日,這時(shí)我們發(fā)現(xiàn)出生年月日的前幾位數(shù)字大體相同,這樣的話,出現(xiàn)沖突的幾率就會(huì)很大,但是我們發(fā)現(xiàn)年月日的后幾位表示月份和具體日期的數(shù)字差別很大,如果用后面的數(shù)字來構(gòu)成散列地址,則沖突的幾率會(huì)明顯降低。因此數(shù)字分析法就是找出數(shù)字的規(guī)律,盡可能利用這些數(shù)據(jù)來構(gòu)造沖突幾率較低的散列地址。c>平方取中法：當(dāng)無法確定關(guān)鍵字中哪幾位分布較均勻時(shí),可以先求出關(guān)鍵字的平方值,然后按需要取平方值的中間幾位作為哈希地址。這是因?yàn)椋浩椒胶笾虚g幾位和關(guān)鍵字中每一位都相關(guān),故不同關(guān)鍵字會(huì)以較高的概率產(chǎn)生不同的哈希地址。d>折疊法：將關(guān)鍵字分割成位數(shù)相同的幾部分,最后一部分位數(shù)可以不同,然后取這幾部分的疊加和〔去除進(jìn)位作為散列地址。數(shù)位疊加可以有移位疊加和間界疊加兩種方法。移位疊加是將分割后的每一部分的最低位對(duì)齊,然后相加；間界疊加是從一端向另一端沿分割界來回折疊,然后對(duì)齊相加。e>除留余數(shù)法：取關(guān)鍵字被某個(gè)不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址。即H<key>=keyMODp,p<=m。不僅可以對(duì)關(guān)鍵字直接取模,也可在折疊、平方取中等運(yùn)算之后取模。對(duì)p的選擇很重要,一般取素?cái)?shù)或m,若p選的不好,容易產(chǎn)生同義詞。2>處理沖突方法：a>開放定址法：Hi=<H<key>+di>MODm,i=1,2,…,k<k<=m-1,其中H<key