南大軟院ds期末試卷d.s期終復(fù)習(xí)1

1、 D.S.復(fù)習(xí)提綱 第第1章：章： 數(shù)據(jù)，數(shù)據(jù)結(jié)構(gòu)，基本類型，抽象數(shù)據(jù)類型，數(shù)據(jù)，數(shù)據(jù)結(jié)構(gòu)，基本類型，抽象數(shù)據(jù)類型，Java語言的面向?qū)ο笳Z言的面向?qū)ο缶幊?、遞歸的概念與實(shí)現(xiàn)編程、遞歸的概念與實(shí)現(xiàn) 。 主要能用遞歸思想寫出算法主要能用遞歸思想寫出算法 例子：例子： ppt-遞歸例遞歸例1 求求n! 遞歸例遞歸例2 求求a0+a1+a2+an-1 作業(yè)作業(yè)- 例例3 求數(shù)組中的最大值求數(shù)組中的最大值 例例4 求數(shù)組元素的平均值求數(shù)組元素的平均值 例例3,例例4如果用鏈表來實(shí)現(xiàn)呢？如果用鏈表來實(shí)現(xiàn)呢？ 復(fù)習(xí)例題復(fù)習(xí)例題-例例5 統(tǒng)計(jì)二叉樹中的葉結(jié)點(diǎn)個(gè)數(shù)統(tǒng)計(jì)二叉樹中的葉結(jié)點(diǎn)個(gè)數(shù) 例例6 交換每個(gè)結(jié)點(diǎn)

2、的左子女和右子女交換每個(gè)結(jié)點(diǎn)的左子女和右子女 例例1. 1. 求求n!n!factorial function f(n)=n! 1 n1 (recursive component) /遞歸部分遞歸部分 f(n)f(5)=5*f(4)=5*4f( 3)=5*4*3f(2)=5*4*3*2f(1)=120 static long factorial (int n) if ( n 0) return Rsum(a,n-1)+an-1; return 0; 例例3. 3. 求數(shù)組中的最大值求數(shù)組中的最大值public static int findMax(int a, int n)/n表示表示n個(gè)元素

3、，它們在數(shù)組個(gè)元素，它們在數(shù)組a中中 if(n= =1) return a 0; else int temp=findMax(a,n-1); return tempa n-1?temp:a n-1; int max(int a,int n) if(n = = 1) return a0;int m = max(a,n-1);if( m an-1 )return m;else return an-1;例3. 求數(shù)組中的最大值如果用鏈表來實(shí)現(xiàn)表：如果用鏈表來實(shí)現(xiàn)表： 求鏈表中的最大值求鏈表中的最大值 int GetMaxInt( ListNode f ) if( f.link = = NULL )

4、return f .data ; else int i = GetMaxInt( f.link ); if ( i f .data ) return i ; else return f .data ; 或或 else return ( f . data) ( GetMaxInt( f . link ) ) ? f . data : GetMaxInt( f . link );例例4 . 4 . 求數(shù)組元素的平均值求數(shù)組元素的平均值float average( int a,int n) if(n = = 1) return a0;else return (average(a,n-1)*(n-1)

5、+an-1)/n; 如果用鏈表：如果用鏈表： float Average( ListNode f, int n ) if( f.link = = NULL ) return f.data; else return ( Average ( f.link, n-1 ) * ( n-1 ) + f.data ) / n;例5. 統(tǒng)計(jì)葉子結(jié)點(diǎn)個(gè)數(shù)int leafNum ( BinTreeNode * root ) if ( root = = NULL ) return 0 ; if ( root-leafchild = = NULL & root-rightchild = = NULL ) retur

6、n 1; else return leafNum( root- leftchild ) + leafNum ( root- rightchild ) ; 例6. 交換左右子數(shù)void Swapchild ( BinTreeNode * p ) if ( p = = NULL ) return ; BinTreeNode * temp = p - left ; p -left = p - right ; p - right = temp; Swapchild ( p -left ); Swapchild (p -right );第第2 2章章 算法分析算法分析 復(fù)雜性上界和平均復(fù)雜度的漸近分析;

7、 最佳、最差和平均情況下的復(fù)雜度差異; 大O、和 符號 1）分析某個(gè)語句的執(zhí)行次數(shù)（頻度）2）分析某個(gè)程序段執(zhí)行的時(shí)間復(fù)雜度（用大O表示，要求寫出推導(dǎo)過程） ppt:-對排序算法與查找算法的分析 例1-for (int i = 1; i = n; i+) for (int j = 1; j=n; j+) cij = 0.0; for ( int k = 1; k = n; k+) cij = cij+aik*bkj; 次數(shù)為: n*n*n第第2 2章章 算法分析算法分析例例2. x = 0; y = 0; for (int i = 1; i = n; i+) for (int j = 1; j

8、 = i; j+) for (int k = 1; k 0) if(x100) x -= 10; y-; else x+; 1100次次 第3章 表、棧和隊(duì)列 表、棧和隊(duì)列的（基本概念，順序存儲(chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，應(yīng)用），表、棧和隊(duì)列的（基本概念，順序存儲(chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，應(yīng)用）， 特殊矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ) 表：表： 邏輯邏輯-（e1, e2, .en) e1, e2, .en) 物理物理-數(shù)組實(shí)現(xiàn)數(shù)組實(shí)現(xiàn) 鏈表實(shí)現(xiàn)鏈表實(shí)現(xiàn)-單鏈表單鏈表 循環(huán)鏈表循環(huán)鏈表 雙向鏈表雙向鏈表 cursor cursor 表頭結(jié)點(diǎn)表頭結(jié)點(diǎn)用鏈表實(shí)現(xiàn)用鏈表實(shí)現(xiàn) 操作操作-查找、插入、刪除等查找、插入、

9、刪除等 ppt-多項(xiàng)式相加多項(xiàng)式相加 約瑟夫問題約瑟夫問題 雙鏈表的插入、刪除雙鏈表的插入、刪除 例題例題-逆轉(zhuǎn)鏈表等題逆轉(zhuǎn)鏈表等題第3章 表 例例1. 逆轉(zhuǎn)鏈表（假設(shè)不帶表頭結(jié)點(diǎn)）逆轉(zhuǎn)鏈表（假設(shè)不帶表頭結(jié)點(diǎn)） public void inverse( ListNode f ) if ( f = = NULL ) return; ListNode p = f . link ; pr = NULL; while ( p ! = NULL ) f . link = pr ; pr = f ; f = p ; p = p . link ; f . link = pr ; 第第3 3章章例例2. 設(shè)有

10、如下結(jié)構(gòu)的循環(huán)鏈表和可利用空間表設(shè)有如下結(jié)構(gòu)的循環(huán)鏈表和可利用空間表 data link L a0 a1 . an-1 Avail 請?jiān)诔?shù)時(shí)間內(nèi)實(shí)現(xiàn)將請?jiān)诔?shù)時(shí)間內(nèi)實(shí)現(xiàn)將L鏈表中的所有結(jié)點(diǎn)歸還到可利用空間表鏈表中的所有結(jié)點(diǎn)歸還到可利用空間表 ListNode p = L.link; L.link = Avail; Avail = p; 棧、隊(duì)列 定義定義-棧的定義，棧的定義， 隊(duì)列的定義隊(duì)列的定義 機(jī)內(nèi)實(shí)現(xiàn)機(jī)內(nèi)實(shí)現(xiàn)-數(shù)組數(shù)組 （循環(huán)隊(duì)列）（循環(huán)隊(duì)列） 單鏈表單鏈表 應(yīng)用應(yīng)用 棧棧-對表達(dá)式求值。中綴對表達(dá)式求值。中綴-后綴后綴-對后綴表達(dá)式求值對后綴表達(dá)式求值 遞歸函數(shù)的實(shí)現(xiàn)。遞歸函數(shù)的實(shí)現(xiàn)

11、。 PPT：第：第4章中用非遞歸實(shí)現(xiàn)中序章中用非遞歸實(shí)現(xiàn)中序,后序遍歷后序遍歷(在第在第4章中講章中講) 隊(duì)列隊(duì)列-循環(huán)隊(duì)列的補(bǔ)充題：已知隊(duì)尾元素的位置與元素的個(gè)數(shù)，循環(huán)隊(duì)列的補(bǔ)充題：已知隊(duì)尾元素的位置與元素的個(gè)數(shù)， 求隊(duì)頭元素的位置。求隊(duì)頭元素的位置。 中綴到后綴：中綴到后綴： (a+b)*(c-d)/2*e)- ab+cd-2/e* 用了什么棧？用了什么棧？ 對后綴表達(dá)式求值： 用了什么棧 例2. 隊(duì)列-循環(huán)隊(duì)列的補(bǔ)充題 已知隊(duì)尾元素的位置與元素的個(gè)數(shù)， 求隊(duì)頭元素的位置。 先用實(shí)例來分析，然后歸結(jié)到一般情況。 .frontrear情況一情況一: front=rear-length+1.r

12、earfront情況二情況二: front=rear-length+1+m合并合并: front=(rear-length+1+m)%mfront特殊矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ) Arrays and Matrix1D-Array1D-Array1. One-dimensional array 1D-array is a limited sequence composed of n (n0) elements which are of the same data type. For example: Location of the element Loc(ai)=Loc(a0)+i 35

13、27 49 18 60 54 77 83 41 02a 0 1 2 3 4 5 6 7 8 9Size-1i2D-Array2D-Array Two-dimensional arrays are composed of n rows and m columns.a00 a01 a02a0 m-1 a10 a11 a12a1 m-1a20 a21 a22a2 m-1.an-10 an-11an-12.an-1 m-1 Anm=2D-Array2D-ArrayThere are three ways to implement a 2D array 1) mapping the 2D-array t

14、o a 1D-arraya00 a01a0 m-1a10a11 .an-1 m-1a00 a01 a02a0 m-1 a10 a11 a12a1 m-1a20 a21 a22a2 m-1.an-10 an-11an-12.an-1 m-1 Row major order2D-Array2D-Array Location mapping: a) row-major order Loc(aij)=Loc(a00)+i*m+j*l b) column-major order Loc(aij)=Loc(a00)+j*n+i*l2D-Array2D-Array An 3D-Array: int am1m

15、2m3 Location mapping Loc(aijk)=Loc(a000)+i*m2*m3+j*m3+kMatrix Matrix 1.definition: a m*n Matrix is a table with m rows and n columns. m and n are the dimensions of the matrix. For example: a 5*4 matrix7 2 0 90 1 0 56 4 2 08 2 7 31 4 9 612345 1 2 3 4MatrixMatrix 2.Matrix can be implemented with a two

16、 dimensional array : int xmn or Array2Dxmn use x(i,j) to index the matrix element, 1=i=m , 1=j1;Lower triangular. M(i,j)=0 for ij;Symmetric.M(i,j)=M(j,i);Special MatrixSpecial MatrixFor example: 2 0 0 0 2 1 0 0 2 0 0 0 0 1 0 0 3 1 3 0 5 1 0 0 0 0 4 0 0 5 2 7 0 3 1 0 0 0 0 6 0 0 9 0 4 2 7 0(a)Diagona

17、l (b) Tridiagonal Lower Triangular 2 1 3 0 2 4 6 0 0 1 3 8 4 1 9 5 0 0 1 6 6 9 4 7 0 0 0 0 0 5 7 0(d)Upper Triangular (e)SymmetricSpecial MatrixSpecial Matrix1)Lower Triangular a11a21 a22a31 a32 a33an1 an2 annLocation mapping in row-major order: Loc(a(i,j)=Loc(a(1,1)+(1+2+3+i-1)+(j-1)*l =Loc(a(1,1)+

18、(i*(i-1)/2+j-1)*lSpecial MatrixSpecial Matrix2)Upper Triangular a11 a12 a1n a22a2n . annK=1i-1Location mapping in row-major order: Loc(a(i,j)=Loc(a(1,1)+(n-k+1)+j-i*lSpecial MatrixSpecial Matrix3) Tridiagonal a11 a12 a21 a22 a23 a32 a33 a34 an,n-1 an,nLocation mapping in row-major order: Loc(a(i,j)=

19、Loc(a(1,1)+(i-1)*3-1+(j-i+1)*lSparse MatricesSparse Matrices1.Definition: An m*n matrix is said to be sparse if “many” of its elements are zero. number of zero elementsnumber of non-zero elementsSparse MatricesSparse Matrices An example of sparse matrix:0 0 0 2 0 0 0 6 0 0 7 00 0 0 9 0 0 0 4 5 0 0 0

20、Sparse MatricesSparse Matrices 2.Array representation The nonzero entries of an sparse matrix may be mapped into a 1D array in row major order. The structure of each element is: row col value Sparse MatricesSparse Matrices For example : 1 4 2 2 2 6 2 5 7 3 4 9 4 2 4 4 3 5row col valuea:MaxTerms-1012

21、0 0 0 2 0 0 0 6 0 0 7 00 0 0 9 0 0 0 4 5 0 0 0 Sparse Matrices3. Linked Representation 例子：例子： 四行四行 0 0 11 0 0 12 0 0 0 0 0 -4 0 0 0 0 0 0 0 0 五五 列列F 4 5 3TTTTTheadnodeH0 H1 H2 H3 H4 TTTTH0H1H2H3F 0 211F 1 012F 2 1-4習(xí)題：習(xí)題： 設(shè)有一個(gè)設(shè)有一個(gè)n*n的對稱矩陣的對稱矩陣A，如下圖，如下圖(a)所示。為了節(jié)約存儲(chǔ)，可以只所示。為了節(jié)約存儲(chǔ)，可以只存對角線及對角線以上的元素，或者只存對

22、角線或?qū)蔷€以下的元存對角線及對角線以上的元素，或者只存對角線或?qū)蔷€以下的元素。前者稱為上三角矩陣，后者稱為下三角矩陣。我們把它們按行素。前者稱為上三角矩陣，后者稱為下三角矩陣。我們把它們按行存放于一個(gè)一維數(shù)組存放于一個(gè)一維數(shù)組B中，如圖中，如圖(b)和圖和圖(c)所示。并稱之為對稱矩陣所示。并稱之為對稱矩陣A的壓縮存儲(chǔ)方式。試問：的壓縮存儲(chǔ)方式。試問： 1）存放對稱矩陣）存放對稱矩陣A上三角部分或下三角部分的一維數(shù)組上三角部分或下三角部分的一維數(shù)組B有多少元有多少元素？素？ 2）若在一維數(shù)組）若在一維數(shù)組B中從中從0號位置開始存放，則如圖號位置開始存放，則如圖(a)所示的對稱矩所示的對稱矩

23、陣中的任一元素陣中的任一元素aij在只存上三角部分的情形下在只存上三角部分的情形下(圖圖(b)應(yīng)存于一維數(shù)應(yīng)存于一維數(shù)組的什么下標(biāo)位置？給出計(jì)算公式。組的什么下標(biāo)位置？給出計(jì)算公式。 3）若在一維數(shù)組）若在一維數(shù)組B中從中從0號位置開始存放，則如圖號位置開始存放，則如圖(a)所示的對稱矩所示的對稱矩陣中的任一元素陣中的任一元素aij在只存下三角部分的情況下在只存下三角部分的情況下*(圖圖(c)應(yīng)存于一維應(yīng)存于一維數(shù)組的什么下標(biāo)位置？給出計(jì)算公式。數(shù)組的什么下標(biāo)位置？給出計(jì)算公式。 a11 a12 a1n a11 a12 a1n a11 a21 a22 a2n a22 a2n a21 a22 .

24、 . an1 an1 ann ann an1 an2 ann (a) (b) (c)答案：答案： 1) 1+2+3+n = *(1+n)*n 2) loc(Ai,j ) = loc(B0) + ( n+n-1+.+n-i+2 + j-i ) t = *(2*n-i+2)*(i-1) + j-i ij 3) loc(Ai,j = loc(B0) + (1+2+3+.+i-1+j-1) t = *i*(i-1) + j-1 i=j t = *j*(j-1) + i-1 ij 第4章 樹 1.二叉樹的定義、性質(zhì)二叉樹的定義、性質(zhì) 2.滿二叉樹與完全二叉樹的概念滿二叉樹與完全二叉樹的概念 3.二叉樹的

25、機(jī)內(nèi)存儲(chǔ)：二叉樹的機(jī)內(nèi)存儲(chǔ)： 數(shù)組表示（完全二叉樹）、左數(shù)組表示（完全二叉樹）、左-右拉鏈表示、右拉鏈表示、cursor 遞歸遞歸 4.先序、中序、后序遍歷先序、中序、后序遍歷 非遞歸非遞歸 層次遍歷層次遍歷-用到隊(duì)列用到隊(duì)列例例1. 第第4章中用非遞歸實(shí)現(xiàn)中序章中用非遞歸實(shí)現(xiàn)中序,后序遍歷后序遍歷Inorder, Postorder non-recursive algorithm Inorder non-recursive algorithm ABCDEFIHGroottemplate void InOrder(BinaryNode* t) if(t) InOrder(tLeft); vis

26、it(t); InOrder(tRight); Inorder non-recursive algorithmInorder non-recursive algorithm void Inorder(BinaryNode * t) StackBinaryNode* s(10); BinaryNode * p = t; for ( ; ; ) 1) while(p!=NULL) s.push(p); p = p-Left; 2) if (!s.IsEmpty( ) p = s.pop( ); cout element; p = p-Right; else return; 5. 利用先序、中序可唯

27、一構(gòu)造一棵樹利用先序、中序可唯一構(gòu)造一棵樹 先序：先序：ABDCEGFHI 中序：中序：DBAEGCHFI 利用中序、后序可唯一構(gòu)造一棵樹利用中序、后序可唯一構(gòu)造一棵樹 手工畫出一棵樹手工畫出一棵樹 利用算法生成一棵樹利用算法生成一棵樹Create BinaryTree recursive algorithm preorder:ABDCEGFHI inorder: DBAEGCHFI ABCDEFIHGCreate BinaryTree recursive algorithm 1void CreateBT(String pres, ins ; BinaryNode * & t) int inp

28、os; String prestemp, instemp ; if (pres.length( )= =0) t=NULL; else t=new BinaryNode; t-element=pres.ch0; inpos=0; while (ins.chinpos!=t-element) inpos+; prestemp=pres(1,inpos); instemp=ins(0,inpos-1); CreateBT(prestemp, instemp, t-left); prestemp=pres(inpos+1, pres.length( )-1); instemp=ins(inpos+1

29、, pres.length( )-1); CreateBT(prestemp, instemp, t-right); Create BinaryTree recursive algorithm 1Create BinaryTree recursive algorithm 1 public: BinaryTree( string pre, string In ) createBT( pre, In, root ) ; main( ) BinaryTree t1( “ABHFDECKG”, “ HBDFAEKCG” ) ; . *6. 利用廣義表表示來構(gòu)造一棵樹利用廣義表表示來構(gòu)造一棵樹 7. 應(yīng)

30、用應(yīng)用 樹的機(jī)內(nèi)表示：樹的機(jī)內(nèi)表示： 廣義表表示、雙親表示、左子女廣義表表示、雙親表示、左子女-右兄弟表示右兄弟表示 1) Take a tree as a binary treeabcdefghijfirstchild data nextsiblingabcdefghij樹的存儲(chǔ)方式：三種樹的存儲(chǔ)方式：三種廣義表表示：廣義表表示：a(b(f,g),c,d(h,i,j),e)雙親表示法雙親表示法左子女左子女右兄弟表示法右兄弟表示法 class TreeNode: T data; TreeNode *firstchild, *nextsibling; class Tree: TreeNode *

31、 root, *current; 樹樹-二叉樹的轉(zhuǎn)換二叉樹的轉(zhuǎn)換 Forest Binary tree Forest Binary tree A F H B C D G I J E K 每棵樹轉(zhuǎn)為二叉樹 A F H B G I C K J D E 把每棵二叉樹根用右鏈相連 A B F C G H D I E R J Binary tree Forest Binary tree Forest A B F C G H D I E R J樹與森林的遍歷樹與森林的遍歷 樹的遍歷：深度優(yōu)先遍歷，廣度優(yōu)先遍歷樹的遍歷：深度優(yōu)先遍歷，廣度優(yōu)先遍歷深度優(yōu)先遍歷深度優(yōu)先遍歷 先序次序遍歷（先序）先序次序遍歷（先

32、序） 訪問樹的根訪問樹的根 按先序遍歷根的第一棵子樹，第二棵子樹，按先序遍歷根的第一棵子樹，第二棵子樹， 等。等。 后序次序遍歷（后序）后序次序遍歷（后序） 按后序遍歷根的第一棵子樹，第二棵子樹，按后序遍歷根的第一棵子樹，第二棵子樹，等等 訪問樹的根。訪問樹的根。 A 先根：先根：ABEFCGKLDHIJM與與 B C D 對應(yīng)的二叉樹的先序一致對應(yīng)的二叉樹的先序一致 E F G H I J 后根：后根：EFBKLGCHIMJDA與與 對應(yīng)的二叉樹的中序一致對應(yīng)的二叉樹的中序一致 K L M 廣度優(yōu)先遍歷廣度優(yōu)先遍歷 A B C D E F G H I J K L M 分層訪問：分層訪問：AB

33、CDEFGHIJKLM 森林的遍歷 深度優(yōu)先遍歷 * 先根次序遍歷 訪問F的第一棵樹的根 按先根遍歷第一棵樹的子樹森林 按先根遍歷其它樹組成的森林 * 中根次序遍歷中根次序遍歷 按中根遍歷第一棵樹的子樹森林按中根遍歷第一棵樹的子樹森林 訪問訪問F的第一棵樹的根的第一棵樹的根 按中根遍歷其它樹組成的森林按中根遍歷其它樹組成的森林 * 后根次序遍歷 按后根遍歷第一棵樹的子樹森林 按后根遍歷其它樹組成的森林 訪問F的第一棵樹的根二叉樹的先序二叉樹的先序 二叉樹的中序二叉樹的后序二叉樹的后序 A K B C D I H E F G J 先根：ABEFCGDKIHJ 中根：EFBGCDAIJHK 后根：

34、FEGDCBJHIKA A B K E C I F G D H J 廣度優(yōu)先遍歷（層次遍歷）補(bǔ)充：補(bǔ)充： 線索樹線索樹 Thread Tree Thread Tree1.Purpose:2. Thread Tree Representation left Thread Tree and right Thread Tree3.Thread Tree class 1.Purpose: Example： A B C D E F G H J Thread Tree A B C D E F G H J Inorder: DBAEGCHFJThread Treeroot2. 機(jī)內(nèi)如何存儲(chǔ)機(jī)內(nèi)如何存儲(chǔ) 一個(gè)

35、結(jié)點(diǎn)增加兩個(gè)標(biāo)記域：一個(gè)結(jié)點(diǎn)增加兩個(gè)標(biāo)記域： leftchild leftthread data rightthread rightchild 0 leftchild 指向左子女指向左子女 leftThread = = 1 leftchild 指向前驅(qū)（某線性序列）指向前驅(qū)（某線性序列） 0 rightchild 指向右子女指向右子女 rightThread = = 1 rightchild 指向后繼指向后繼 Thread TreeThread Tree left threadTree right threadTree 8. 哈夫曼樹 哈夫曼樹的構(gòu)造 哈夫曼編碼 擴(kuò)充的二叉、三叉、.、t叉樹

36、15, 3, 14, 2, 6, 9, 16, 17 構(gòu)造擴(kuò)充的三叉樹。9. 等價(jià)類問題 PPT第8章第第4.14.1章：二叉搜索樹章：二叉搜索樹 1.二叉搜索樹的概念二叉搜索樹的概念 2.帶索引的二叉搜索樹的概念帶索引的二叉搜索樹的概念 3. AVL樹樹-平衡的二叉搜索樹平衡的二叉搜索樹 4. B-樹樹 1.二叉搜索樹的概念二叉搜索樹的概念 二叉搜索樹二叉搜索樹 Example:45125390781006124373 left element right二叉搜索樹二叉搜索樹主要操作：主要操作： 查找、插入、刪除查找、插入、刪除15122410811181617202923213230353

37、3 2. 2.帶索引的二叉搜索樹的概念帶索引的二叉搜索樹的概念A(yù)n indexed binary search tree is derived from an ordinary binary search tree by adding the field leftSize to each tree node.Value in Leftsize field=number of the elements in the nodes left subtree +1leftSize left element right Example: 4 20 2 15 1 25 1 18 1 12 1 30 例子：

38、例子： 寫一遞歸函數(shù)實(shí)現(xiàn)在帶索引的二叉搜索樹（寫一遞歸函數(shù)實(shí)現(xiàn)在帶索引的二叉搜索樹（IndexBST)中查找第中查找第k個(gè)小個(gè)小的元素。的元素。public Comparable findK( BinaryNode root, int k)if( root=null) return null;/空空 if( kroot. leftSize) /在右子樹在右子樹findK( root. right, k-root. leftSize);/注意減去注意減去 else return root.element;3.AVL樹樹-平衡的二叉搜索樹平衡的二叉搜索樹 Definition of an AVL

39、tree: (1) is a binary search tree (2) Every node satisfies |hL-hR|=1 where hL and hR are the heights of TL(left subtree) and TR(right subtree),respectively. 例子例子1345681011121518202224+10-10-1AVL TreeAVL TreeHeight of an tree: the longest path from the root to each leaf nodeBalance factor bf(x) of a

40、node x : height of right subtree of x height of left subtree of x Left data Right balance(height) Each node: AVL Tree The height of an AVL tree with n elements is O(log2 n), so an n-element AVL search tree can be searched in O(log2 n) time. AVL Tree 插入插入 左外側(cè)，左外側(cè)， 右外側(cè)右外側(cè)-一次旋轉(zhuǎn)一次旋轉(zhuǎn) 左內(nèi)側(cè)，右內(nèi)側(cè)左內(nèi)側(cè)，右內(nèi)側(cè)-二次旋轉(zhuǎn)二

41、次旋轉(zhuǎn) AVL樹的插入樹的插入: 1. 首先要正確地插入首先要正確地插入 2. 找到有可能發(fā)生的最小不平衡子樹找到有可能發(fā)生的最小不平衡子樹 3. 判別插入在不平衡子樹的外側(cè)還是內(nèi)側(cè)判別插入在不平衡子樹的外側(cè)還是內(nèi)側(cè) 4. 根據(jù)根據(jù)3的判別結(jié)果的判別結(jié)果,再進(jìn)行單旋還是雙旋再進(jìn)行單旋還是雙旋 從空的從空的AVL樹建樹的算法。一個(gè)例子樹建樹的算法。一個(gè)例子 ： 7個(gè)關(guān)鍵碼發(fā)生四種轉(zhuǎn)動(dòng)個(gè)關(guān)鍵碼發(fā)生四種轉(zhuǎn)動(dòng) A， Z， C， W， D， X， YAAZAZCW右雙旋轉(zhuǎn)右雙旋轉(zhuǎn)AAZZCC右內(nèi)右內(nèi)ADZCW左外左外右單旋轉(zhuǎn)右單旋轉(zhuǎn)ACDZW左單旋轉(zhuǎn)左單旋轉(zhuǎn)右外AACCDDZZXXWWY左雙旋轉(zhuǎn)左雙旋轉(zhuǎn)

42、左內(nèi)AACYCDDZZXXWW AVL樹的刪除： 方法 ： 與二叉搜索樹的刪除方法一樣。 假設(shè)被刪除結(jié)點(diǎn)為W, 它的中序后繼為X, 則用X代替W,并 刪除X. 所不同的是:刪除X后,以X為根的子樹高度減1,這一高度 變化可能影響到從X到根結(jié)點(diǎn)上每個(gè)結(jié)點(diǎn)的平衡因子,因此要進(jìn) 行一系列調(diào)整。WX AVL樹的算法分析樹的算法分析 具有具有n個(gè)結(jié)點(diǎn)的平衡二叉樹（個(gè)結(jié)點(diǎn)的平衡二叉樹（AVL），進(jìn)行一次插入或刪除），進(jìn)行一次插入或刪除的時(shí)間最壞情況的時(shí)間最壞情況O（log2 n) 證明：實(shí)際上要考慮證明：實(shí)際上要考慮n個(gè)結(jié)點(diǎn)的平衡二叉樹的最大高度個(gè)結(jié)點(diǎn)的平衡二叉樹的最大高度 (3/2) log2 (n +

43、 1 ) 設(shè)設(shè)T h 為一棵高度為為一棵高度為h，且結(jié)點(diǎn)個(gè)數(shù)最少的平衡二叉樹。，且結(jié)點(diǎn)個(gè)數(shù)最少的平衡二叉樹。h-2h-1h假設(shè)右子樹高度為假設(shè)右子樹高度為h-1因結(jié)點(diǎn)個(gè)數(shù)最少因結(jié)點(diǎn)個(gè)數(shù)最少,左子樹高度左子樹高度只能是只能是h-2這兩棵左子樹這兩棵左子樹,右子樹高度分別右子樹高度分別為為h-2, h-1,也一定是結(jié)點(diǎn)數(shù)最少的也一定是結(jié)點(diǎn)數(shù)最少的:n = 7h = 3T 3h = 1T 1n = 2h =2T 2n = 4 h = 4T 4n = 12h = 0T 0n = 1 以上五棵平衡二叉樹，又稱為以上五棵平衡二叉樹，又稱為Fibonacci樹。樹。 也可以這樣說一棵高度為也可以這樣說一棵高

44、度為h的樹，其右子樹高度為的樹，其右子樹高度為h-1的的Fibonacci樹，左子樹是高度為樹，左子樹是高度為h-2的的Fibonacci樹，即樹，即T h - 2T h - 1假設(shè)假設(shè)N h表示一棵高度為表示一棵高度為h的的Fibonacci樹的結(jié)點(diǎn)個(gè)數(shù)，則樹的結(jié)點(diǎn)個(gè)數(shù)，則 N h =N h - 1 + N h - 2 + 1 N 0 = 1 , N 1 = 2 , N 2 = 4 , N 3 = 7 , N4 = 12 , . . .N 0 + 1 =2 , N 1 + 1 = 3 , N2 + 1 = 5 , N 3 + 1 = 8 , N4 + 1 = 13 , . . . N h +

45、 1滿足費(fèi)波那契數(shù)的定義，并且滿足費(fèi)波那契數(shù)的定義，并且N h+ 1= F h + 3 f 0 f 1 f 2 f 3 f 4 f 5 f 6 . . . 0 1 1 2 3 5 8 . . .費(fèi)波那契數(shù)費(fèi)波那契數(shù)F i 滿足下列公式滿足下列公式 F i = ( ) - ( ) 15 1- 5 2iii | | =2Level 2 =2m/2Level 3 =2m/22Level h = 2m/2h-1B-treesB-trees n+1= 2m/2h-1 , (n+1)/2= m/2h-1 , h-1=log m/2 (n+1)/2, logm(n+1)=h=1+logm/2 (n+1)/2

46、In the case that each node has m children Example: n=2*106, m=199 then h=1+log100(102)3=4 search one from 200 branchesB-treesB-trees2) Inserting into a B-Tree always happen at one level above the external nodesB-treesB-trees Case 1:number of children in the nodem, insert into the node as ordered 10

47、802 4 6 20 30 40 50 60 70 82 84 86 88A B-Tree of order 7Insert 3B-treesB-trees 10 802 3 4 6 20 30 40 50 60 70 82 84 86 88B-treesB-treesCase 2.Insert into a node with m children (also called a full node), like insert 25 into the B-Tree in the last example, the full node is split into two nodes. A new

48、 pointer will be added to the parent of the full node .Because km/2 is inserted into parent node, it may cause new split. If the root is split,the height of the tree will increased by 1. B-treesB-trees Example: Insert 4430 802050 6090102535 40557082 8595A B-Tree of order 3B-treesB-trees 802060901025

49、 44557082 859535403050Algorithm analyses: If the insert operation causes s node to split, the number of disk access is h (to read in the nodes on the search path) +2s (to write out the two split parts of each node that is split) +1 (to write the new node).B-treesB-trees3)deletion from a B-Tree Two c

50、ases: The element to be deleted is in a node whose children are external nodes(i.e.the element is in a leaf) The element is to be deleted from a nonleaf.B-treesB-treesa) the element to be deleted is in a leaf Case1: delete it directly if it is in a node which has more than m/2 children Case2: if it

51、is in a node which has m/2children, after deletion ,the number of children(m/2-1) is not suitable for a B-Tree borrow an element from the its nearest sibling if can, and do some adjusting.B-treesB-trees Example: delete 379 283 353 401307 313 331 347367 379 389283 347 401307 313 331353 367 389A B-TRE

52、E of order 7B-treesB-trees If nearest left or right sibling both only has m/2 children, then merge themAfter deletion ,merge the node and its sibling with the element between them in the parent into a single nodeMaybe cause new merge in parent nodesThe height of the tree will deceased by one if root

53、 is merged.B-treesB-trees Example:a B-Tree of order 7 ,delete 431283 353 401367 379 389419 431 439B-treesB-treesb)delete a key in a node in the above levelDelete itReplace it with the smallest key in the right subtree or the largest key in the left subtreeBecause delete a key in the leaf node , do t

54、he adjust mentioned in a)B-treesB-trees Example:Delete 80, then replace it with 82 or 70, delete 82 or 70 at last30 802050 6085102535 4055708290A B-TREE of order 3B-treeB-tree例子：例子：1. 分別分別 delete 50 ,40 in the following 3階階B-樹樹.503060 802040557095B-treeB-tree2. 分別畫出插入分別畫出插入65, 15, 40, 30后的后的3階階B-樹。樹

55、。 554580 90 25 355060 708595第5章：散列 1.散列函數(shù)的選擇 2.解決沖突的方法 開地址法：線性探查法 平方探查法 二次散列 鏈地址法 Hash Function1。散列函數(shù)的選擇。散列函數(shù)的選擇 2. solve a collision2. solve a collision1. Open Addressing 1) linear Probing If hash(key)=d and the bucket is already occupied then we will examine successive buckets d+1, d+2,m-1, 0, 1,

56、2, d-1, in the arraysolve a collisionsolve a collision example keys : Burke, Ekers, Broad, Blum, Attlee, Alton, Hecht, Ederly hash( key ) = ord( x ) ord(A) x為取為取key第一個(gè)字母在字母表中的位置。例如：第一個(gè)字母在字母表中的位置。例如： hash(Attlee) = 0 H( Burke ) = 1 , H( Ekers ) = 4 , H( Broad ) = 1, H( Blum ) = 1, H( Attlee ) = 0 , H

57、( Hecht ) = 7 , H(Alton ) = 0 , H( Ederly ) = 4, 設(shè)散列表長設(shè)散列表長 m = 26 ( 025 ) 分析比較次數(shù)：分析比較次數(shù)： 搜索成功的平均搜索長度搜索成功的平均搜索長度 1/8( 1 + 1 + 2 + 3 + 1 + 1 + 6 + 3 ) = 18/8 * 搜索不成功的平均搜索長度搜索不成功的平均搜索長度 1/26( 9+8+7+6+5+4+3+2+ 1+1+1+.+1) = (9+8+7+6+5+4+3+2+ 18) = 62/26solve a collisionsolve a collision 2) Quadratic pro

58、bing If hash(k)=d and the bucket is already occupied then we will examine successive buckets d+1, d+22, d+33, in the array example : ( 89,18, 49, 58, 69 ) hash( k ) = k % 10; 0 1 2 3 4 5 6 7 8 9 49 58 69 18 89 2 3 3 1 1 ASVsucc=(1+1+2+3+3)/5solve a collisionsolve a collision 3) Double Hashing If has

59、h1(k)=d and the bucket is already occupied then we will counting hash2(k) =c, examine successive buckets d+c, d+2c, d+3c, in the array example: hash1(k) = k % 10; hash2(k) = R (k % R ); 其中 R 1 & parebleTo( array hole / 2 ) 0; hole /= 2 ) array hole = array hole / 2 ; array hole = x; Heaps public Com

60、parable deleteMin( ) if( isEmpty( ) ) return null; Comparable minItem = findMin( ); array 1 = array currentSize- ; percolateDown( 1 ); return minItem; Heaps private void percolateDown( int hole ) int child; Comparable tmp = array hole ; for( ; hole *2 = currentSize; hole = child ) child = hole * 2;