復(fù)旦大學(xué)軟件工程考研(mse)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料

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

2、序圖,鏈表、棧和隊(duì)列,大綱描述：單鏈表,雙向鏈表,環(huán)形鏈表,帶哨兵節(jié)點(diǎn)的鏈表?xiàng)５幕靖拍詈托再|(zhì),棧ADT及其順序,鏈接實(shí)現(xiàn);棧的應(yīng)用;棧與遞歸;隊(duì)列的基本概念和性質(zhì),隊(duì)列ADT及其順序,鏈接實(shí)現(xiàn);隊(duì)列的應(yīng)用;向量基本概念和性質(zhì);向量ADT及其數(shù)組、鏈接實(shí)現(xiàn);,線性表基本概念和性質(zhì),線性表是n個(gè)數(shù)據(jù)元素的有限序列常見線性表包括數(shù)組、鏈表、棧、隊(duì)列等線性表的兩種實(shí)現(xiàn)方式順序鏈?zhǔn)綄Ρ龋翰迦耄ㄓ行?、無序）、刪除、查找、讀取

3、,環(huán)形鏈表,環(huán)形鏈表又稱循環(huán)列表，是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它的特點(diǎn)是表中最后一個(gè)元素的指針域指向頭結(jié)點(diǎn),棧的基本概念和性質(zhì),棧：棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表后進(jìn)先出特性（LIFO）棧頂、棧底、出棧、入棧,例題,設(shè)有一個(gè)棧S，元素S1, S2, S3, S4, S5, S6依次進(jìn)棧，如果6個(gè)元素的出棧順序?yàn)镾2, S3, S4, S6, S5, S1，則棧的容量至少應(yīng)為多少？ 答案：3,棧的基本概念和性質(zhì),設(shè)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

25、構(gòu)造具有n棵二叉樹的集合F = {T0, T1, T2, …, Tn-1}，其中每一棵二叉樹Ti只有一個(gè)帶有權(quán)值wi的根結(jié)點(diǎn)，其左、右子樹均為空。(2) 在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的二叉樹, 做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。(3) 在F中刪去這兩棵二叉樹，加入新得的樹。(4) 重復(fù)(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、,編碼：等長編碼/不等長編碼前綴編碼：若要設(shè)計(jì)長短不等的編碼，則必須是任一個(gè)字符的編碼抖不是另一個(gè)字符編碼的前綴，這種編碼叫做前綴編碼Huffman編碼：以n種字符出現(xiàn)的頻率做權(quán)，設(shè)計(jì)一棵赫夫曼樹，由此得到的前綴編碼稱為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,,習(xí)題,某通訊系統(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。構(gòu)造以字符使用頻率為權(quán)值的Huffman樹，并給出相應(yīng)的Huffman編碼。,習(xí)題答案,習(xí)題答案,A：0110B：10C：1110D：1111,E：110F：00G：0111H：010,課程安排,課程介紹棧、隊(duì)列和向量 樹查找排序圖,查找,大綱

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

47、，i為關(guān)鍵字k的第一個(gè)字母在英文字母表中的序號，地址值域?yàn)閇0:6]，采用線性再散列法處理沖突。插入后的哈希表應(yīng)該如_________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ā)生沖突的元素有______________個(gè)答案：2,例題,已知一組關(guān)鍵字為（26，36，41，38，44，15，68，12，06，51，25），用線性探查法解決沖突構(gòu)造這組關(guān)鍵字的散列表，假設(shè)利用除余法構(gòu)造散列

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

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

51、(x)=[i/2],其中i為關(guān)鍵字中第一個(gè)字母在字母表中的序號,練習(xí)答案,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,練習(xí)答案,0->Apr->Aug2->Dec3->

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

53、并排序，基數(shù)排序等排序算法基本思想；算法代碼及基本的時(shí)間復(fù)雜度分析；堆的定義，堆的生成。,排序基本概念,排序(Sorting) ：重排一個(gè)記錄序列,使之成為按關(guān)鍵字有序常見排序可分為以下五類：插入排序（簡單插入排序、希爾排序）交換排序（冒泡排序、快速排序）選擇排序（簡單選擇排序、堆排序）歸并排序計(jì)數(shù)排序（多關(guān)鍵字排序）,插入排序,[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），也是一種屬于插入排序類的算法，但時(shí)間效率較其他排序方法有較大改進(jìn)基本思想是：先將整個(gè)待排記錄序列分割為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列的記錄“基本有序”時(shí)，再對全體記錄進(jìn)行一次直接插

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

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

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,,,例題,寫出對于結(jié)點(diǎn)序列

59、（46，26，22，68，48，42，36，84，66）進(jìn)行第一次分割后序列的情況，注意列出步驟的每一步。,例題答案,【】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,練習(xí),已知序列（2, 8, 7, 1, 3, 5, 6, 4），如果選用4作為樞軸，那么進(jìn)行一次分割后序列表現(xiàn)是怎樣的？答案：2，3，1，4，7，5，6，8,練習(xí),對序列(49,38,65,97,76,27,13,50)采用快速排序法進(jìn)行排序，以序列的第一個(gè)元素為基準(zhǔn)元素得到的劃分結(jié)果是__________________。答案：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)進(jìn)行排序，前三趟排序結(jié)束時(shí)的結(jié)果依次為：第一趟：13，72，68，49，50，97，27；第二趟：13，27，68，49，38，50，97，72；第三趟：13，27，38，49，68，50，97，72；該排序采用的方法是————答案：簡單選擇排序,練習(xí),若對序列(49，38，65，97，76，13，27，50)采用選擇排序法排序，則第三趟結(jié)束后序列的狀態(tài)是___________________。,

63、練習(xí)答案,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)提出堆排序?qū)儆跇湫瓦x擇排序，僅需要一個(gè)記錄大小的輔助空間，每個(gè)待排序記錄僅占有一個(gè)存儲(chǔ)空間。,堆的定義，堆的生成,定義：n個(gè)元素的序列{k1,k2,…,kn}當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)，稱之為堆：ki≤k2i且ki≤k2

64、i+1或ki≥k2i且ki≥k2i+1等價(jià)的樹的定義：如果一棵完全二叉樹,其中每個(gè)節(jié)點(diǎn)的鍵值不小于(或者不大于)其子樹的所有節(jié)點(diǎn)的鍵值,則稱這棵二叉樹為(最大值/最小值)堆(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個(gè)元素的序列重又建成一個(gè)堆，則得到n個(gè)元素中的次小值，如此反腐執(zhí)行，便能得到一個(gè)有序序列，這個(gè)過程稱為堆排序。,堆的定義，堆的生成,堆排序基本思想:將記錄集調(diào)整為堆輸出堆頂?shù)淖钪涤涗泴⑹Ｏ掠涗浿匦抡{(diào)整為一個(gè)堆重復(fù)2,3直至所有記錄被輸出堆排序關(guān)鍵問題:如何將一個(gè)記錄集調(diào)整為堆?,堆的定義，堆的生成,堆生成/調(diào)整算法:從樹的最后一個(gè)非葉子節(jié)點(diǎn)開始,也就是從

66、數(shù)組的第length/2-1個(gè)元素開始調(diào)整每次比較當(dāng)前節(jié)點(diǎn)和及其左右子節(jié)點(diǎn),取三者中最大者作為根按逆層次序考察,直至根節(jié)點(diǎn),也就是數(shù)組的第一個(gè)元素,堆的定義，堆的生成,堆排序算法：先將初始堆調(diào)整成一個(gè)最大值堆；然后將最值與最后一個(gè)元素對調(diào)，將去除最后一個(gè)元素后剩余的堆重新調(diào)整為一個(gè)最大值堆；繼續(xù)以上過程直至最后一個(gè)元素。,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],