Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Đỗ Ngọc Như Loan

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 5: Bảng băm (Hashtable)" trình bày các khái niệm về bảng băm, giải quyết đụng độ bằng kết nối, định nghĩa bảng băm, các thao tác, độ phức tạp,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Đỗ Ngọc Như LoanGV:ĐỗNgọcNhưLoanKháiniệm Bảngbămlàmộtcấutrúcdữliệucóthểlưu trữmộttậpcácđốitượngcósốphầntửtùyý Cácthaotáctìmkiếm,chèn,xoátrênbảng bămrấthiệuquả Phầntửcókhoák(nguyên)đượclưutrữ trongsloth(k),trongđóhlàhàmbăm(hash function)từtậpUcáckhóađếntậpcácslot củabảngbămT[0..m1]Kháiniệm Hàmbămcódạngh:U→{0,1,...,m1},mlà kíchthướccủabảngbăm h(k)làgiátrịbăm(hashvalue)củakhoák haycònnóiphầntửcókhoákbămsloth(k) Vớihàmbămchỉcầnxửlýmgiátrịthayvì| U|giátrịBảngbăm Cóthểcósựdụngđộ(collision)lưutrữcác khóa,vídụk2dụngđộk5,nghĩalàh(k2)= h(k5) Cácphươngphápgiảiquyếtđụngđộ§ Thiếtkếhàmbămh(U)phânbốđềutrênT (khôngtriệtđể)§ Giảiquyếtdụngđộbằngdanhsáchliênkết collisionresolutionbychaining)§ Giảiquyếtdụngđộbằngđịachỉmở(open addressing)GiẢIQUYẾTĐỤNGĐỘBẰNGKẾTNỐI Đặttấtcảcácphầntửcócùnggiátrịhàm bămvàomộtdanhsáchliênkết Slotjchứapointerchỉđếnđầucủadanh sáchliênkếtcủatấtcảcácphầntửđượclưu trữcóhàmbămlàj Nếukhôngcókhóakđểh(k)=jthìthìslotjtrỏ đếnNULLĐỊNHNGHĨABẢNGBĂM ĐịnhnghĩabảngbămtrongC++,cáckhóalà sốnguyêntypedefstructCELL*LIST;structCELL{ intkey; LISTnext;};typedefLISTTABLE[MAX];TABLET;CÁCTHAOTÁC HashInitialize(T):Khởitạobảngbăm HashInsert(T,k):Chènmộtphầntửcókhóak vàobảngbămT HashSearch(T,k):Tìmmộtphầntửcókhoák trongT HashDelete(T,k):Xoámộtphầntửcókhóak khỏiT HashInitializevoidHashInitialize(TABLE&T,int&m)//mlàkíchthước{ //bảngbăm for(inti=0;iHashInsertvoidHashInsert(TABLE&T,intm,intk){ ListInsert(T[Hash(k,m)],k);}intHash(intk,intm)//hàmbăm{ returnk%m;}HashSearchLISTHashSearch(TABLET,intk,intm){ returnListSearch(T[Hash(k,m)],k);}HashDeletevoidHashDelete(TABLE&T,intm,intk){ ListDelete(T[Hash(k,m)],k);}ĐỘPHỨCTẠP HashInsert(T,k)cóT(n)=O(1) HashSearch(T,k)vàHashDelete(T,k)cóđộ phứctạptrungbìnhT(n)=O(n/m),trongđóm làkíchthướcbảngbămHÀMBĂM Mộthàmbămlàtốtnếuh(k)cóthểlàbấtkỳ slotnàotrênbảngbăm Trongứngdụngcầntìmcáchàmbămthích hợp Luôngiảsửmỗikhoálàmộtsốtựnhiên Cómộtsốcáchxâydựnghàmbămnhư: phươngphápchia(divisionmethod),phương phápnhân(multiplicationmethod)v.vHÀMBĂM Vớiphươngphápchia,tạohàmbămbằng cáchđặttươngứngmỗikhoákvớisốdư trongphépchiakchosốslotm Vậyh(k)=kmodm Tậpcáckhoáđượcchiathànhmlớp Nênchọnmlàsốnguyêntốkhôngquágần vớilũythừacủa2HÀMBĂM Phươngphápnhân,hàmbămcódạng: §h(k)=,Alàhằngthỏa0Yêucầu:Chodãysốnguyêndươnggồmnsốđôimộtkhácnhauvàsốk.Hãykiểmtraxemcógiátrịktrongdãykhông?Input:DữliệuvàotừfileHASH.INPgồm2dòng:+Dòng1:Gồm2sốnguyênnvàk(n