復旦大學軟件工程考研(mse)數(shù)據(jù)結構復習資料

1、數(shù)據(jù)結構2016MSE考研沖刺,,課程安排,課程介紹棧、隊列和向量 樹查找排序圖,課程目的,（以最小代價）通過考試！不是成為專家不是初學授課,試題結構,考試滿分60分考試題型：問答、分析、編程,樣題－問答和編程題,插入排序、選擇排序、冒泡排序、快速排序中最快的排序方法是________試論述什么叫Hash沖突及有那些處理方法編程實現(xiàn)對二叉樹所有節(jié)點的統(tǒng)計,課程安排,課程介紹棧、隊列和向量 樹查找排

2、序圖,鏈表、棧和隊列,大綱描述：單鏈表,雙向鏈表,環(huán)形鏈表,帶哨兵節(jié)點的鏈表棧的基本概念和性質,棧ADT及其順序,鏈接實現(xiàn);棧的應用;棧與遞歸;隊列的基本概念和性質,隊列ADT及其順序,鏈接實現(xiàn);隊列的應用;向量基本概念和性質;向量ADT及其數(shù)組、鏈接實現(xiàn);,線性表基本概念和性質,線性表是n個數(shù)據(jù)元素的有限序列常見線性表包括數(shù)組、鏈表、棧、隊列等線性表的兩種實現(xiàn)方式順序鏈式對比：插入（有序、無序）、刪除、查找、讀取

3、,環(huán)形鏈表,環(huán)形鏈表又稱循環(huán)列表，是另一種形式的鏈式存儲結構。它的特點是表中最后一個元素的指針域指向頭結點,棧的基本概念和性質,棧：棧是限定僅在表尾進行插入和刪除操作的線性表后進先出特性（LIFO）棧頂、棧底、出棧、入棧,例題,設有一個棧S，元素S1, S2, S3, S4, S5, S6依次進棧，如果6個元素的出棧順序為S2, S3, S4, S6, S5, S1，則棧的容量至少應為多少？ 答案：3,棧的基本概念和性質,設

4、計遞歸問題的非遞歸算法一般需要用到棧機制三個數(shù)a、b、c進棧，不可能出現(xiàn)c、a、b順序出棧,例題,若某棧的輸入序列為a、b、c，則所有可能的出棧序列有___種，所有不可能的出棧序列有____種。答案：5，1,例題,若棧的輸入序列為1,2,3,4，則——是不可能的棧輸出序列之一。答案：4，3，1，2,習題,若某棧的輸入序列為a、b、c、d，則所有可能的出棧序列有___種，所有不可能的出棧序列有____種。請寫出所有可能的序列

5、和不可能的序列。,棧的應用,數(shù)制轉換十進制數(shù)字與d進制數(shù)字的轉換N = ( N div d) × d + N mod d其中div為整除，mod為求余。算法：將算法3.1中8換成d,例題,十進制數(shù)1167等于八進制數(shù)——？答案： 2217思路：計算方法：除余倒排法驗證方法：指數(shù)相加法,習題,十進制數(shù)1167等于七進制數(shù)——？,棧的應用,表達式求值：中綴表達式轉后綴表達式后綴表達式求值三種表達式：前綴

6、表達式 + a b中綴表達式 a + b后綴表達式 a b +,例題,中綴表達式a + b × c – d轉為后綴表達式是————？答案： a b c×＋d－,例題,中綴表達式（a + b） × c – d轉為后綴表達式是————？答案： a b ＋ c×d－思路：數(shù)字位序不變，運算符位置改變后綴表達式無括號，運算順序同中綴表達式,習題,中綴表達式A-(B+C)*D/

7、E的后綴形式是_________________。,練習,中綴表達式a * ( b + c ) / d轉為后綴表達式是————？,例題,計算后綴表達式1 2 + 4 * 2 /的值為——？答案：6思路：順序計算或 轉換為中綴表達式計算,習題,計算后綴表達式3 2 － 4 * 2 / 3＋的值為——？,遞歸,一個直接調用自己或通過一系列的調用語句間接地調用自己的函數(shù)，稱為遞歸函數(shù)優(yōu)點：結構清晰、程序易讀、正確性容易得到證明缺

8、點：效率相對較低,隊列的基本概念和性質,隊列：隊列是限定僅在表的一頭進行插入、另一頭進行刪除操作的線性表先進先出特性（FIFO）隊尾、隊頭、入隊、出隊,例題,在初始為空的隊列中插入元素a,b,c,d以后，緊接著作了兩次刪除操作，此時的隊頭元素是——，隊尾元素是————。答案：c，d,雙向隊列,雙向隊列：亦稱雙端隊列（Deque）是限定插入和刪除操作在表的兩端進行的線性表可以用于包裝產生棧和隊列,課程安排,課程介紹棧、隊

9、列和向量 樹查找排序圖,樹,大綱描述：樹的基本概念和術語；樹的前序、中序、后序、層次序遍歷；二叉樹及其性質；普通樹與二叉樹的轉換；樹的存儲結構,標準形式;完全樹(complete tree)的數(shù)組形式存儲;樹的應用，Huffman樹 。,樹的基本概念和術語,樹：是n（n≥0）個結點的有限集在任意一棵非空樹中：有且僅有一個特定的稱為根的結點當n>1時，其余結點可以分為m（m>0）個互不相交的有限集，其中

10、每個集合本身又是一棵樹，并且稱為根的子樹樹屬于層次結構數(shù)據(jù)結構,樹的基本概念和術語,節(jié)點標簽父節(jié)點、子節(jié)點、兄弟節(jié)點、祖先節(jié)點、子孫節(jié)點路徑、樹枝,根、葉子次數(shù)內部節(jié)點、外部節(jié)點樹的次數(shù)、K次樹節(jié)點層次、樹的高度和深度子樹有序樹、無序樹森林、果園,例題,例題,列出如上圖所示樹的所有葉子結點答案：K,L,F,G,M,I,J列出如上圖所示樹的所有分支結點答案：A,B,C,D,E,H樹A為幾次樹？子樹B呢？答案

11、：3，2前頁圖所示樹的高度為多少？答案：4,樹的基本概念和術語,如果將樹中結點的各子樹看作從左到右有序的,則該樹為有序樹(ordered tree),否則為無序樹。森林(forest)是m棵互不相交的樹的集合。如果把一棵樹的根砍去，剩下的部分就是森林。如果原來的樹是有序的,則砍去根后的森林也是有序的,此時稱該森林為有序森林或果園。,二叉樹及其性質,二叉樹（Binary Tree）另一種樹形結構，特點是每個結點至多只有二棵子樹

12、，且子樹有左右之分，其次序不能任意顛倒二叉樹可能的五種基本形態(tài),二叉樹及其性質,在二叉樹的第i層上至多有2i－1個結點（i≥1）,例題,一棵二叉樹第五層上至多有多少個結點？至少多少？答案：16，1,二叉樹及其性質,深度為k的二叉樹至多有2k－1個結點（k≥1）,例題,深度為n(n>0)的二叉樹最多有_____個結點。答案：2n-1,例題,一棵深度為5的二叉樹至多有多少個結點？至少多少？答案：31，5,例題,高度為h(

13、h>0)的二叉樹最少有________個結點？答案：h,二叉樹及其性質,對于任何二叉樹,如果葉子節(jié)點數(shù)為n0,度為2的節(jié)點數(shù)為n2,則n0=n2+1,例題,在一棵二叉樹中有n0個葉結點，有n2個度為2的結點，則n2=________。答案： n0 －1,例題,若一棵二叉樹有10個葉結點，則該二叉樹中度為2的結的點個數(shù)為______________。答案：9,例題,若一二叉樹有2度結點100個，則其葉結點有多少個？答

14、案：101,例題,若二叉樹中度為2的結點有15個，度為1的結點有10個，共有多少個結點？答案：41,例題,在一棵度為3的樹中，度為3的結點有2個，度為2的結點有1個，度為1的結點有2個，那么，該樹有__________個葉結點。答案：6構造法,二叉樹及其性質,滿二叉樹：一棵深度為k且有2k－1個結點的二叉樹可以對滿二叉樹的結點進行連續(xù)編號，約定編號從根開始，自上而下，自左而右。完全二叉樹：深度為k的，有n個結點的二

15、叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1到n的結點一一對應時，稱為完全二叉樹。,二叉樹及其性質,完全二叉樹特點：葉子結點只可能出現(xiàn)在層次最大的兩層上對任一結點，若其右分支下子孫的最大層次為l，其左下分支的子孫的最大層次必為l或者l＋1。深度為k的完全二叉樹第k層最少1個結點，最多2k-1-1個結點；整棵樹最少2k-1個結點，最多2k-2個結點,例題,若某完全二叉樹的深度為h，則該完全二叉樹中至少有______個

16、結點。答案：2h-1,例題,若深度為6的完全二叉樹的第6層有3個葉結點，則該二叉樹一共有______個結點。答案：25-1+3＝34,例題,一個具有767個結點的完全二叉樹，其葉子結點個數(shù)為____。 答案：384分析：可以根據(jù)公式進行推導，假設n0是度為0的結點總數(shù)（即葉子結點數(shù)），n1是度為1的結點總數(shù)，n2是度為2的結點總數(shù)，由二叉樹的性質可知：n0＝n2＋1，則n= n0＋n1＋n2（其中n為完全二叉樹的結點總數(shù)）

17、，由上述公式把n2消去得：n= 2n0+n1－1，由于完全二叉樹中度為1的結點數(shù)只有兩種可能0或1，由此得到n0＝（n＋1）/2或n0＝n/2，合并成一個公式：n0＝[（n＋1）/2 ]，就可根據(jù)完全二叉樹的結點總數(shù)計算出葉子結點數(shù)。本題計算得：384。,二叉樹及其性質,具有n個結點的完全二叉樹的深度為[log2n]+1,例題,具有2000個結點的二叉樹，其深度至少為_________。答案：11,二叉樹及其性質,如果含有n ?1個

18、節(jié)點的二叉樹的高度為[log2n]＋1,將其所有結點按層次序編號,則對于任一節(jié)點j(1?j ? n),有如果j=1,則節(jié)點j是樹的根,無雙親;如果j>1,則其父節(jié)點parent(j)是節(jié)點[j/2]如果2j>n,則節(jié)點j無左子節(jié)點;否則其左子節(jié)點為2j如果2j+1>n,則節(jié)點j無右子節(jié)點;否則其右子節(jié)點為2j+1證明,完全樹的數(shù)組形式存儲,完全樹的數(shù)組形式存儲算法將其編號為i的結點元素存儲在一維數(shù)組下標為i－

19、1的分量中,例題,已知數(shù)組[20,30,19,87,30,40]表示一棵完全二叉樹，請畫出該樹。,練習答案,樹的遍歷,樹的遍歷 按某種搜索路徑巡訪樹中每個結點，使每個結點均被訪問一次僅且一次二叉樹的遍歷可分為前序、中序、后序、層次序等普通樹的遍歷可以分為先根、后根、層次序等,樹的遍歷,二叉樹的遍歷前序、中序、后序定義層次序：從上而下，從左至右常見問題已知樹寫遍歷結果已知遍歷結果畫樹依據(jù)：二叉樹的前序和中序遍歷可以唯一確

20、定一棵二叉樹思路：前序定根，中序定左右遞歸和非遞歸算法實現(xiàn),例題,寫出左圖所示二叉樹的前序、中序、后序、層次序遍歷結果,例題答案,前序：ABDCEFG中序：DBAECFG后序：DBEGFCA層次序：ABCDEFG,例題,假設一棵二叉樹的前序遍歷為EBADCHGFIKJ，中序遍歷為ABCDEFGHIJK，請畫出該樹。,例題答案,樹的遍歷,普通樹的遍歷前根：先遍歷根結點，再依次前根遍歷各棵子樹后根：先后根遍歷各課子樹，再遍歷根

21、結點已知樹寫遍歷結果已知遍歷結果畫樹思路：先根定根，后根定子樹,例題,寫出如右圖所示樹的先根、后根、層次序遍歷結果,例題答案,前序： ABECFGHD后序：EBFHGCDA層次序：ABCDEFGH,練習,給出如圖所示樹的先根、后根和層次序遍歷結果,練習答案,前根：ABEFHIGCJKLDMNOQP后根：EHIFGBKLJCNQOPMDA層次序：ABCDEFGJMHIKLNOPQ,例題,畫出和下列已知序列對應的樹T：樹的

22、先根次序訪問序列為GFKDAIEBCHJ樹的后根次序訪問序列為DIAEKFCJHBG,例題答案,普通樹與二叉樹的轉換,對于任意k次樹到相應二叉樹的轉換算法對于具有子節(jié)點n1,n2…nk的節(jié)點n,將n1作為其左子節(jié)點,且kj+1作為kj(1 ?j ? k-1)的右子節(jié)點思路：“不同層在左，同層在右”,普通樹與二叉樹的轉換,對于任意森林到相應二叉樹的轉換算法為 設T=(T1,T2…..Tm)為m(m?0)棵樹的序列,而BT (T

23、1,T2…..Tm)為相應的二叉樹,則如果m=0,則BT為空樹如果m>0,則T1的根節(jié)點就是BT的根節(jié)點,而BT的左子樹是T1的子樹T11,T12…T1K轉換成的BTl(T11,T12…T1K),其右子樹為BTr(T2…..Tm),例題,將下頁圖所示森林轉換為等價的二叉樹,例題,例題答案,練習,將如圖所示樹轉換為二叉樹,練習答案,Huffman樹,Huffman樹：又稱最優(yōu)樹，是一類帶權路徑長度最短的樹基本概念：樹的路徑

24、長度：從根到每一結點的路徑長度之和。結點的帶權路徑長度：從該結點到樹根之間的路徑長度與結點上權的乘積。樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度之和，通常記做WPL。,Huffman樹,基本概念：假設有n個權值wi，試構造一棵有n個葉子結點的二叉樹，每個葉子的結點帶權為wi，則其中WPL最小的二叉樹稱為最優(yōu)二叉樹或赫夫曼樹算法見下頁,Huffman算法,(1) 由給定的n個權值{w0, w1, w2, …, wn-1}，

25、構造具有n棵二叉樹的集合F = {T0, T1, T2, …, Tn-1}，其中每一棵二叉樹Ti只有一個帶有權值wi的根結點，其左、右子樹均為空。(2) 在F中選取兩棵根結點的權值最小的二叉樹, 做為左、右子樹構造一棵新的二叉樹。置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和。(3) 在F中刪去這兩棵二叉樹，加入新得的樹。(4) 重復(2) (3)，直到F只含一棵樹為止。這棵樹就是赫夫曼樹,Step 1,2Z,7K

26、,24F,32C,37U,42D,42L,120E,9,,,33,,,,,Round 1,Round 2,例題,2Z,7K,24F,32C,37U,42D,42L,120E,9,,,33,,,65,,,Round 3,2Z,7K,24F,32C,37U,42D,42L,120E,9,,,33,,,65,,,79,,,Round 4,2Z,7K,24F,32C,37U,42D,42

27、L,120E,9,,,33,,,65,,,79,,,107,,,Round 5,2Z,7K,24F,32C,37U,42D,42L,120E,9,,,33,,,65,,,79,,,107,,,186,,,Round 6,2Z,7K,24F,32C,37U,42D,42L,120E,9,,,33,,,65,,,79,,,107,,,186,,,306,,,Round 7 (final),Huffman編碼

28、,編碼：等長編碼/不等長編碼前綴編碼：若要設計長短不等的編碼，則必須是任一個字符的編碼抖不是另一個字符編碼的前綴，這種編碼叫做前綴編碼Huffman編碼：以n種字符出現(xiàn)的頻率做權，設計一棵赫夫曼樹，由此得到的前綴編碼稱為Huffman編碼,例題,2Z,7K,24F,32C,37U,42D,42L,120E,9,,,33,,,65,,,79,,,107,,,186,,,306,,,0,0,0,0,0,1,1,1,1,1

29、,1,0,0,1,,習題,某通訊系統(tǒng)只使用8種字符a、b、c、d、e、f、g、h，其使用頻率是0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11。構造以字符使用頻率為權值的Huffman樹，并給出相應的Huffman編碼。,習題答案,習題答案,A：0110B：10C：1110D：1111,E：110F：00G：0111H：010,課程安排,課程介紹棧、隊列和向量 樹查找排序圖,查找,大綱

30、描述：查找的基本概念；對線性關系結構的查找，順序查找，二分查找；Hash查找法,常見的Hash函數(shù)(直接定址法,隨機數(shù)法),hash沖突的概念, 解決沖突的方法(開散列方法/拉鏈法,閉散列方法/開址定址法),二次聚集現(xiàn)象;BST樹定義,性質,ADT及其實現(xiàn),BST樹查找,插入,刪除算法;平衡樹 (AVL) 的定義,性質,ADT及其實現(xiàn),平衡樹查找,插入算法,平衡因子的概念;優(yōu)先隊列與堆,堆的定義,堆的生成,調整算法;范圍查詢;

31、,查找的基本概念,查找表(search table)：具有同一類型數(shù)據(jù)元素(經(jīng)常稱為記錄)的集合查找表的基本操作有：查找某個“特定”記錄是否在表中查找到后取出某個“特定”記錄的各個數(shù)據(jù)項向表中插入記錄從表中刪除記錄,查找的基本概念,靜態(tài)查找表(static search table)：僅用于查詢的查找表。動態(tài)查找表(dynamic search table):若在查找過程中需同時插入表中不存在的記錄;或者需要刪除記錄,

32、則稱之為動態(tài)查找表。關鍵字/鍵值(key) ：記錄某個數(shù)據(jù)項的值,用其可以標示該記錄當記錄只有一個數(shù)據(jù)項時,其關鍵字即為該記錄的值如果一個key可以唯一標示一個就,則稱之為主關鍵字(primary key),否則稱之為次關鍵字(secondary key),查找的基本概念,查找(search)：在一個查找表中找出具有“特定”鍵值的那些記錄所謂查找成功是指在查找表中找到了滿足條件的記錄,此時一般會返回找到的記錄,或者返回記錄的

33、位置信息,或者僅僅返回找到(true)否則稱為查找失敗,此時一般返回空指針,或特殊值,或者僅僅返回沒有找到(false),有時也會就此插入這個元素,BST樹定義，性質， 實現(xiàn),二叉排序樹(Binary Sorted Tree)又稱二叉搜索樹或二叉查找樹或者是一棵空樹；或者是具有下列性質的二叉樹：如果左子樹非空,則左子樹中所有節(jié)點的鍵值均小于它的根結點的值；如果右子樹非空,則右子樹中所有節(jié)點的鍵值均大于它的根結點的值；它的左

34、右子樹也都是二叉排序樹。,BST樹定義，性質， 實現(xiàn),二叉排序樹性質 如果對二叉排序樹進行中序遍歷,則得到一個從小到大排好序的列表,所以可以得到一種簡單的排序方法叫做“樹排序”(treesort)。我們也可以根據(jù)這個性質定義二叉排序樹為:如果一棵樹按中序遍歷為排好序的,則這棵樹是二叉排序樹。,BST樹查找，插入，刪除算法,BST樹查找，插入，刪除算法畫圖算法,例題,已知BST樹如左，請畫出插入16，再刪除36之后的BST樹,例題

35、答案,例題,試求按關鍵字序列（12，1，4，3，7，8，1O，2）插入生成的二叉排序樹,例題答案,練習,假設結點序列F＝（60，30，90，50，120，70，40，80），試用BST的插入算法，用F中的結點依次進行插入，畫出由F中結點所構成的BST樹T1；再用刪除算法，依次刪除40，70，60，畫出刪除后的BST樹T2。,練習答案,平衡樹,平衡因子（balanced factor）二叉樹上任一節(jié)點的左子樹高度減去右子樹高度的差AV

36、L Tree，根據(jù)其三位發(fā)明者(Adelson-Velskii and Landis)的名字命名一棵BST樹中每個節(jié)點平衡因子的絕對值不超過1,平衡樹,基本思想 :在插入或刪除節(jié)點后對新樹進行判斷,如果新樹已經(jīng)變得不平衡,則通過旋轉(rotation)的方法對樹進行重組/改組(re-arrange),使得重組后的樹在保持查找樹特性的同時保持平衡所謂旋轉:通過改變支撐點來維持平衡順時針旋轉為右旋;逆時針旋轉為左旋可以進行連續(xù)的

37、多次旋轉,平衡樹,算法代碼及基本的時間復雜度分析,Hash查找法，常見的Hash函數(shù),哈希（Hash）函數(shù)：在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系f，使每個關鍵字和結構中一個唯一的存儲位置相對應。這個對應關系f為哈希函數(shù)。按這個思想建立的表為哈希表。哈希函數(shù)的設定可以很靈活，只要使得任何關鍵字的哈希函數(shù)值都落在表長允許范圍之內即可。,Hash查找法，常見的Hash函數(shù),練習：已知線性表關鍵字集合為：S = { an

38、d, begin, do, end, for, go, if, repeat, then, until, while}，求哈希函數(shù)。答案：H(key)=key[0] – ‘a’;即為關鍵字key中的第一個字母在字母表{a, b, c, ..., z}中的序號,Hash查找法，常見的Hash函數(shù),直接定址法直接取key或者key的某個線性函數(shù)值 h(key) = a*key +b, a,b為常數(shù)如前面的例子,又如人口普查時使用年齡

39、,出生年份等,Hash查找法，常見的Hash函數(shù),除留余數(shù)法選擇一個適當?shù)恼麛?shù)P，用P去除關鍵字，取所得得余數(shù)作為散列地址，即：H(key) = key%P方法的關鍵是選取適當?shù)腜。選擇P最好不要是偶數(shù)，也不要是基數(shù)的冪。一般地選P為小于或等于散列表長度m的某個最大素數(shù)比較好。缺點:整數(shù)相除速度較慢,Hash查找法，常見的Hash函數(shù),如:m = 8，16，32，64，128，256，512，1024P = 7，13，3

40、1，61，127，251，503，1019,解決沖突的方法,對不同的關鍵字可能得到同一哈希地址，這種現(xiàn)象稱沖突。具有相同函數(shù)值的關鍵字對該哈希函數(shù)來說稱作同義詞。在一般情況下，沖突只能盡可能的少，而不能完全避免。,解決沖突的方法,共同思想: 將具有相同函數(shù)值的記錄存作一個鏈閉散列方法/開址定址法沖突記錄存儲在表內開散列方法/鏈地址法沖突記錄存儲在表外,解決沖突的方法,基本思想當沖突發(fā)生時，使用某種方法在散列表中形成一個探查序

41、列(也稱之為"鏈")，按此序列逐個單元的查找，直到找到一個指定的關鍵字或碰到一個開放的地址（單元為空）為止。Hj = ( H(key) + dj ) MOD m 1 ?j ?m-1;m為hash表長度dj為增量數(shù)列,各種方法的不同就區(qū)別在取不同的增量數(shù)列上,解決沖突的方法,常用的增量數(shù)列:線性探測法二次探測法偽隨機法再哈希法/二次哈希法桶式散列法,解決沖突的方法,線性探測法取dj = 1,2

42、,…m-1將散列表看成是一個環(huán)形表。若地址為d（即H(key)=d）的單元發(fā)生沖突，則依次探查下述地址單元：d+1，d+2，......，m-1，0，1，......，d-1,直到找到一個空單元或查找到關鍵字為key的結點為止。若沿著該探查序列查找一遍之后，又回到了地址d，則無論是做插入操作還是做查找操作，都意味著失敗。,解決沖突的方法,線性探測法缺點:特別容易產生聚集鏈非常長,解決沖突的方法,拉鏈法若選定的散列函數(shù)的值域為0

43、到m-1，則可將散列表定義為一個由m個單鏈表的鏈表頭指針組成的指針數(shù)組HTP(m)，凡是散列地址為i的結點，均插入到以HTP(i)為頭指針的單鏈表中。,,,,,,,,,,,,,,,,,,,,,,,,,0123456789101112,若一組關鍵字為（26，36，41，38，44，15，68，12，06，51，25），散列函數(shù)定義為：H(key) = key%13。用拉練法建立的散列表為：,解決沖突的方法,拉鏈法

44、優(yōu)點:不會堆積,所以平均查找時間較短動態(tài)申請空間,適用于造表前無法確定表長的情況刪除處理簡單快速鏈長易控制,一般較短,解決沖突的方法,負載系數(shù)的定義和作用設key的數(shù)量為N,散列表的大小為M,則N/M稱負載系數(shù)或裝填因子(loadfactor),它表現(xiàn)了平均情況下每個鏈的長度我們一般預先規(guī)定好這個值,然后當不夠的時候再增加hash表的長度(re-hash),這樣可以保證鏈的平均長度不超過負載系數(shù),解決沖突的方法,增加時一般作

45、兩倍的增加，而且增加后需要將所有的表元素全部重新求值放置(因為m變了)一般取值為0.75,解決沖突的方法,聚集(clustering)現(xiàn)象又稱"二次聚集",指處理沖突中發(fā)生的兩個第一個hash地址不同的記錄爭奪同一個后繼hash地址的情況,常發(fā)生在有大量key對應于同一Hash函數(shù)值的情況下聚集現(xiàn)象僅出現(xiàn)于使用"閉散列方法"時當使用"線性探測法"時特別容易發(fā)生聚集現(xiàn)象,很

46、容易使散列查詢退化為對于鏈表或者數(shù)組的順序查詢,解決沖突的方法,假設Hash函數(shù)為H(key)=key MOD 11,表中已經(jīng)有key 17,60,29,此時分別占據(jù)6,7,5;然后再插入38此時可以發(fā)現(xiàn),當表中5,6,7都被占據(jù)后,凡是函數(shù)值為5,6,7,8的key都將爭奪8這個位置!!,例題,在初始為空的哈希表中依次插入關鍵字序列(MON，TUE，WED，THU，F(xiàn)RI，SAT，SUN), 哈希函數(shù)為H(k)=i MOD 7，其中

47、，i為關鍵字k的第一個字母在英文字母表中的序號，地址值域為[0:6]，采用線性再散列法處理沖突。插入后的哈希表應該如_________B_______所示。( )A. 0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MON B. 0 1 2 3 4 5 6 TUE THU WED FRI SUN SAT MON C. 0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MON

48、D. 0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON,例題,若待散列的序列為(18,25,63,50,42,32,9)，哈希函數(shù)為H(key)=key MOD 9，哈希表長度為9，與18發(fā)生沖突的元素有______________個答案：2,例題,已知一組關鍵字為（26，36，41，38，44，15，68，12，06，51，25），用線性探查法解決沖突構造這組關鍵字的散列表，假設利用除余法構造散列

49、函數(shù)。,例題答案,為了減少沖突，通常令裝填因子α<1，在此我們取α=0.75。因為n=11，所以散列表長度m=high(n/α) = 15；對于除余法，選P=13（小于15的最大素數(shù)），即散列函數(shù)為：H(key) = key%13。按順序插入各個結點：26: H(26) = 26/13 = 0 36: ...=10，41: ...=2，38: ...=12，44: ... =5插入15時，其散列地址為2，由于2已

50、被關鍵字為41的元素占用，故需進行探查。按順序探查法，顯然3為開放地址，故可將其放在3單元。類似的，68和12可分別放在4和13單元中,練習,在地址空間為0-16的散列區(qū)中,對以下關鍵字構造兩個hash表 : (Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec)使用開散列方法(此時請注明裝載因子為多少)使用閉散列方法(此時使用線性探測法)此處設hash函數(shù)為H

51、(x)=[i/2],其中i為關鍵字中第一個字母在字母表中的序號,練習答案,0 A; 1 BC; 2 DE; 3 FG;4 HI;5 JK; 6 LM; 7 NO; 8 PQ; 9 RS; 10 TU; 11 VW; 12 XY; 13 ZJan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec,練習答案,0->Apr->Aug2->Dec3->

52、Feb5->Jan->Jun->Jul6->Mar->May7->Oct->Nov9->Sep,練習答案,范圍查詢,定義:在指定集合中有多少記錄的關鍵字是落在指定范圍中一維的情況:記錄可以看作直線上的點問題可以看作有多少點落入指定線段區(qū)域中,課程安排,課程介紹棧、隊列和向量 樹查找排序圖,排序,大綱描述：排序基本概念；插入排序，希爾排序，選擇排序，快速排序，歸

53、并排序，基數(shù)排序等排序算法基本思想；算法代碼及基本的時間復雜度分析；堆的定義，堆的生成。,排序基本概念,排序(Sorting) ：重排一個記錄序列,使之成為按關鍵字有序常見排序可分為以下五類：插入排序（簡單插入排序、希爾排序）交換排序（冒泡排序、快速排序）選擇排序（簡單選擇排序、堆排序）歸并排序計數(shù)排序（多關鍵字排序）,插入排序,[46] 26 22 68 48 42 36 84 66 22*[26 46] 22 6

54、8 48 42 36 84 66 22*[22 26 46] 68 48 42 36 84 66 22*[22 26 46 68] 48 42 36 84 66 22*[22 26 46 48 68] 42 36 84 66 22*[22 26 42 46 48 68] 36 84 66 22*[22 26 36 42 46 48 68] 84 66 22*[22 26 36 42 46 48 68 84] 66 22*[

55、22 26 36 42 46 48 66 68 84] 22*[22 22* 26 36 42 46 48 66 68 84],希爾排序,定義Shell Sort又稱“縮小增量排序”（Diminishing Increment Sort），也是一種屬于插入排序類的算法，但時間效率較其他排序方法有較大改進基本思想是：先將整個待排記錄序列分割為若干子序列分別進行直接插入排序，待整個序列的記錄“基本有序”時，再對全體記錄進行一次直接插

56、入排序,冒泡排序,交換排序的一種依次比較相鄰的兩個待排序元素，若為逆序（遞增或遞減）則進行交換，將待排序元素從左至右比較一遍稱為一趟“冒泡”每趟冒泡都將待排序列中的最大關鍵字交換到最后（或最前）位置直到全部元素有序為止/直到某次冒泡過程中沒有發(fā)生交換為止,快速排序,就平均時間而言，快速排序是目前被認為最好的一種內部排序方法,由C. A. R. Hoare發(fā)明分治法(divide and conquer)思想的體現(xiàn)Unix系統(tǒng)函

57、數(shù)庫所提供的標準排序方法C標準函數(shù)庫中的排序方法直接就命名為qsort(),快速排序,基本思想:是對冒泡排序的一種改進選取一個軸值,然后根據(jù)此軸值通過一趟排序對記錄集進行一次分割,然后對分割后產生的兩個記錄子集分別進行快速排序,快速排序,基本概念:軸值(pivot):書上稱樞軸用于將記錄集"分割"為兩個部分的那個鍵值分割(partition):將記錄集分為兩個部分,前面部分記錄的鍵值都比軸值小,后面部

58、分的鍵值都比軸值大,快速排序,快速排序,49,38,65,97,76,13,27,49’,,,,38,65,97,76,13,27,49’,,,27,38,65,97,76,13,,49’,,,27,38,,97,76,13,65,49’,,,27,38,13,97,76,,65,49’,,,27,38,13,,76,97,65,49’,,,27,38,13,49,76,97,65,49’,,,49,temp,,,例題,寫出對于結點序列

59、（46，26，22，68，48，42，36，84，66）進行第一次分割后序列的情況，注意列出步驟的每一步。,例題答案,【】26，22，68，48，42，36，84，6636，26，22，68，48，42，【】，84，6636，26，22，【】，48，42，68，84，6636，26，22， 42， 48，【】， 68，84，6636，26，22， 42，【】， 48， 68，84，6636，26，22， 42，46， 48，

60、68，84，66,練習,已知序列（2, 8, 7, 1, 3, 5, 6, 4），如果選用4作為樞軸，那么進行一次分割后序列表現(xiàn)是怎樣的？答案：2，3，1，4，7，5，6，8,練習,對序列(49,38,65,97,76,27,13,50)采用快速排序法進行排序，以序列的第一個元素為基準元素得到的劃分結果是__________________。答案：13，38，27，49，76，97，65，50,簡單選擇排序示例,49,3

61、8,65,97,76,13,27,49’,,13,38,65,97,76,49,27,49’,,13,27,65,97,76,49,38,49’,,13,27,38,97,76,49,65,49’,,13,27,38,49,76,97,65,49’,,13,27,38,49,49’,97,65,76,,13,27,38,49,49’,65,97,76,,13,27,38,49,49’,65,76,97,例題,對數(shù)據(jù)元素序列(49，72，

62、68，13，38，50，97，27)進行排序，前三趟排序結束時的結果依次為：第一趟：13，72，68，49，50，97，27；第二趟：13，27，68，49，38，50，97，72；第三趟：13，27，38，49，68，50，97，72；該排序采用的方法是————答案：簡單選擇排序,練習,若對序列(49，38，65，97，76，13，27，50)采用選擇排序法排序，則第三趟結束后序列的狀態(tài)是___________________。,

63、練習答案,13，38，65，97，76，49，27，5013，27，65，97，76，49，38，5013，27，38，97，76，49，65，50,堆的定義，堆的生成,1964年威洛姆斯(J. willioms)提出堆排序屬于樹型選擇排序，僅需要一個記錄大小的輔助空間，每個待排序記錄僅占有一個存儲空間。,堆的定義，堆的生成,定義：n個元素的序列{k1,k2,…,kn}當且僅當滿足下列關系時，稱之為堆：ki≤k2i且ki≤k2

64、i+1或ki≥k2i且ki≥k2i+1等價的樹的定義：如果一棵完全二叉樹,其中每個節(jié)點的鍵值不小于(或者不大于)其子樹的所有節(jié)點的鍵值,則稱這棵二叉樹為(最大值/最小值)堆(max/min heap),堆的定義，堆的生成,10,15,56,25,30,70,,,,,,10,15,56,25,30,70,小根堆示例,堆的定義，堆的生成,70,56,30,25,15,10,,,,,,70,56,30,25,15,10,大根堆示例

65、,堆的定義，堆的生成,堆排序：若在輸出堆頂?shù)淖钪抵?，使得剩余n－1個元素的序列重又建成一個堆，則得到n個元素中的次小值，如此反腐執(zhí)行，便能得到一個有序序列，這個過程稱為堆排序。,堆的定義，堆的生成,堆排序基本思想:將記錄集調整為堆輸出堆頂?shù)淖钪涤涗泴⑹Ｏ掠涗浿匦抡{整為一個堆重復2,3直至所有記錄被輸出堆排序關鍵問題:如何將一個記錄集調整為堆?,堆的定義，堆的生成,堆生成/調整算法:從樹的最后一個非葉子節(jié)點開始,也就是從

66、數(shù)組的第length/2-1個元素開始調整每次比較當前節(jié)點和及其左右子節(jié)點,取三者中最大者作為根按逆層次序考察,直至根節(jié)點,也就是數(shù)組的第一個元素,堆的定義，堆的生成,堆排序算法：先將初始堆調整成一個最大值堆；然后將最值與最后一個元素對調，將去除最后一個元素后剩余的堆重新調整為一個最大值堆；繼續(xù)以上過程直至最后一個元素。,91,88,42,23,24,16,05,13,,,,,,,,91,88,42,23,24,16,05,1

67、3,（a）初始堆R[1]到R[8],,堆的定義，堆的生成,13,88,42,23,24,16,05,91,,,,,,,,13,88,42,23,24,16,05,91,（b）第一趟排序之后,堆的定義，堆的生成,（c）重建的堆R[1]到R[7],88,24,42,23,13,16,05,91,,,,,,,,88,24,42,23,13,16,05,91,,堆的定義，堆的生成,05,24,42,23,13,16,88,91,,,,,,,,0

68、5,24,42,23,13,16,88,91,（d）第二趟排序之后,堆的定義，堆的生成,（e）重建的堆R[1]到R[6],42,24,16,23,13,05,88,91,,,,,,,,42,24,16,23,13,05,88,91,,堆的定義，堆的生成,（f）第三趟排序之后,05,24,16,23,13,42,88,91,,,,,,,,05,24,16,23,13,42,88,91,堆的定義，堆的生成,（g）重建的堆R[1]到R[5],