7查找4-資料下載頁(yè)
2024-09-30 09:33本頁(yè)面
【導(dǎo)讀】的查找算法及其性能分析方法；查找長(zhǎng)度的計(jì)算。2）影響哈希查找ASL的因素有哪些？3）哈希表處理沖突的方法主要有哪幾種？紅黑樹(shù)的統(tǒng)計(jì)性能要好于一般的平衡二。叉樹(shù)，所以被STL選擇作為了關(guān)聯(lián)容器的內(nèi)部結(jié)構(gòu)。set的特性是集合的基本特性：元素唯一性等。合的包含判斷、交、并、差等操作。下面是部分參考用法：。map是一類(lèi)關(guān)聯(lián)式容器。它的特點(diǎn)是增加和刪除節(jié)點(diǎn)對(duì)迭代。對(duì)于迭代器來(lái)說(shuō)，可以修改Value值，而不能修改。自動(dòng)建立Key－value的對(duì)應(yīng)。key和value可以是任意你需要的類(lèi)型。根據(jù)key值快速查找記錄，查找的復(fù)雜度基本是Log，如果有1000個(gè)。記錄，最多查找10次，1,000,000個(gè)記錄，最多查找20次。根據(jù)Key修改value記錄。一個(gè)實(shí)例，值為初始化值。cout<<iter->first<<""<<iter->second<<endl;//讀取元素的辦法
【正文】 線性探測(cè)法和鏈地址法的平均查找長(zhǎng)度（含查找失?。? 熟練 掌握 哈希表的查找算法和插入算法 (開(kāi)放定址 ) 基本掌握 本章要求（二） 數(shù)據(jù)結(jié)構(gòu) 查找 課后建議： ? HLoj 8871~8877 ? HDoj 1563, 2095 , 1029（ Hash） ? HDoj 1880（ Hash，但內(nèi)存限制，需要考慮變通） ? Poj 2418（ BST或 Hash） ? Zoj 1899（ Hash） ? Zoj 1109（ BST或 Hash） ? 注意收集各類(lèi)高效 hash函數(shù) ? 熟悉并嘗試使用 STL中的查找算法 如： binary_search(A, A + N, value) 最新的 STL已經(jīng)支持 Hash結(jié)構(gòu)，但 不支持 數(shù)據(jù)結(jié)構(gòu) 查找 推薦 2個(gè)經(jīng)典字符串 hash函數(shù) unsigned int Hash1(string s) { // zoj 1899 約 4000ms AC unsigned int h = 0。 for(int i=0。 i()。 i++) { h = 31 * h + s[i]。 } return h % MaxN。 // MaxN就是除留余數(shù)法中的 p } unsigned int Hash2(string s) { // 大量采用位運(yùn)算以提高效率 unsigned int h = 0。 for(int i=0。 i()。 i++){ h = (h 4) + s[i]。 unsigned int g = h amp。 0Xf0000000L。 if ( g ) h ^= g 24。 h amp。= ~g。 } return h % MaxN。 }
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1