61線性查找62折半查找63分快查找64二元查找樹65散列-文庫吧
2025-08-27 09:51 本頁面
【正文】 ∑j2j1 h j=1 =(n+1)/nlog2(n+1)1 平均查找長度 ASLbs=log2(n+1)1 O(log2n) 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國家示范性軟件學(xué)院 2020 秋 Slide. 6 8 int Bsearch( F , i , j , k ) //折半查找的遞歸算法 { int m。 if(ij) return( 1 )。 else { m=( i + j ) / 2。 if( F[m].key = = k ) return m。 if( F[m].key k ) return( Bsearch( F , i , m1 , k) )。 else return( Bsearch( F , m+1 , j , k) )。 } } 調(diào)用： Bsearch(F,1,n,k) 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國家示范性軟件學(xué)院 2020 秋 Slide. 6 9 分塊查找 ( 線性查找 +折半查找 ) 22 44 74 0 1 2 IX 22 12 13 9 8 33 42 44 38 24 48 60 58 74 47 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 F 索引表 Int index_search( k, last, blocks, ix, F,L ) Keytype k 。 int last,blocks 。 index ix LIST F 。int L 。 { int i, j 。 i = 0。 while (( k ix[i])amp。amp。( i blocks)) i++ 。 if( iblocks ) { j = i*L。 while(( k != F[j].key )amp。amp。( j = (i+1)*L1 )amp。amp。( j last )) j = j + 1 。 if ( k == F[ j ].key ) return j 。 } return –1 。 } Typedef keytype index[maxblock] 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國家示范性軟件學(xué)院 2020 秋 Slide. 6 10 二元查找樹 (二元排序樹 ) 10 3 14 1 5 12 16 7 15 18 Struct celltype { records data 。 celltype *lchild,*rchild 。} Typedef celltype * BST 。 BST search( keytype k, BST F )。 { p = F 。 if ( p == NULL ) return Null 。 else if ( k == p ) return p 。 else if ( K p ) return ( search ( k, plchild ) ) 。 else if ( K p ) return ( search ( k, prchild ) ) 。 } 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國家示范性軟件學(xué)院 2020 秋 Slide. 6 11 Void insert ( records R , BST amp。F ) { if ( F ==NULL ) { F = new celltype 。 Fdata = R 。 Flchild = NULL 。 Frchild = NULL 。 } else if ( F ) insert ( R , Flchild ) else if ( F ) insert ( R , Frchild ) } 在二元查找樹中插入新結(jié)點(diǎn) 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國家示范性軟件學(xué)院 2020 秋 Slide. 6 12 在二元查找樹中刪除結(jié)點(diǎn) 10 5 14 3 7 12 18 1 15 16 刪除之前 10 5 14 3 7 12 15 1 16 刪除 18之后 10 5 15 3 7 12 18 1 16 刪除 14之后 數(shù)據(jù)結(jié)構(gòu)與算法 . 第六章 查 找 國家示范性軟件學(xué)院 2020 秋 Slide. 6 13 Void delete ( keytype k , BST amp。F ) { if ( F != NULL ) if ( k F ) delete( k, flchild ) 。 else if ( k F )
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1