數(shù)據(jù)結(jié)構(gòu)1ppt課件

1、數(shù)據(jù)構(gòu)造數(shù)據(jù)構(gòu)造第一章第一章 緒論緒論第二章第二章 線性表線性表第三章第三章 稀疏矩陣和廣義表稀疏矩陣和廣義表第四章第四章 棧和隊列棧和隊列第五章第五章 樹和二叉樹樹和二叉樹第六章第六章 二叉樹的運用二叉樹的運用第七章第七章 圖圖第八章第八章 查找查找第九章第九章 排序排序1010niiniiisuccpcpASL) 1 ( .)(110ipASLniisucc.)()(102121111nisuccnnnninASL順序查找算法Struc elemtypeeneytype data; keytype key;Int seqserch(elemtype a, int n, keytype k)

2、an.key=k; for(int i=0;i+) if(ai.key=k) break;If(in) return IElse return -1;2.二分查找條件：表已排序思想：第一步把表一分為二；斷定查找的元素落在哪部分；根據(jù)上述步驟反復直到最后找到或?qū)Π虢K了查找不成功算法下一頁Int binserch(elemtype a, int low, int hiht ,keytype k) if(low=high) int mid =(low+high)/2; if(k=amid.key) return mid; else if(kamid.key) return binserch(a,lo

3、w,mid-1,k); else return binserch(a,mid,high-1,k) return -1;下一頁圖示搜索勝利的例子搜索勝利的例子 搜索失敗的例子搜索失敗的例子下一頁斷定樹搜索勝利的情形搜索勝利的情形 搜索不勝利的情形搜索不勝利的情形一、索引順序查找的數(shù)據(jù)構(gòu)造：一、索引順序查找的數(shù)據(jù)構(gòu)造：Struct indexitemindexkeytype index;int start ;int length;職工號職工號 姓名姓名JS001JS002JS003JS004DZ001DZ002DZ003JJ001JJ002HG001HG002HG003主表主表Js04Dz43Jj

4、72hg930123Index start lengh索引表索引表二、分塊查找：在索引表為稀疏索引二、分塊查找：在索引表為稀疏索引15261834367240574386939834 72 9805104530 1 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14IndexStartlengh索引表索引表主表主表注：同一塊中的數(shù)據(jù)沒有排序注：同一塊中的數(shù)據(jù)沒有排序動態(tài)查找表動態(tài)查找表一、散列的概念一、散列的概念散列：經(jīng)過對表中的每個元素關(guān)健字散列：經(jīng)過對表中的每個元素關(guān)健字K為自變量的為自變量的H()計算出一值作為一延續(xù)存儲空間的位置計算出一值作為一延續(xù)存儲空間的位置,并

5、將并將該元素存儲到這個單元中該元素存儲到這個單元中.此函數(shù)稱散列函數(shù)或此函數(shù)稱散列函數(shù)或哈希函數(shù)哈希函數(shù).()稱散列地址或哈希地址稱散列地址或哈希地址,上述的存儲上述的存儲空間稱散列表或哈希表空間稱散列表或哈希表.例例:A=(18,75,60,43,54,90,46) h(k)=k%m :m為散列表的長度為散列表的長度=1343 1860750 1 2 3 4 5 6 7 8 9 10 11 12549046同義詞沖突同義詞沖突:70下一頁沖突引起沖突的三個緣由引起沖突的三個緣由:一、裝填因子一、裝填因子:=n/m 二、與散函數(shù)有關(guān)二、與散函數(shù)有關(guān)三、與處理的方法有關(guān)三、與處理的方法有關(guān)181 2 3 4 5 6 7 82627非同義詞沖突非同義詞沖突線性探查法線性探查法 0 1 2 3 4 5 6 7 8 9 10 11 12B(18,75,60,43,54,90,46,31,58,73,15,34)H(k)=k%13155443315846347518