Bài giảng Cấu trúc dữ liệu 2

Với kết cấu nội dung gồm 7 bài, bài giảng "Cấu trúc dữ liệu 2" trình bày những nội dung về bảng băm, cấu trúc cây và cây nhị phân, cây nhị phân tìm kiếm, cây nhị phân cân bằng, cây đỏ đen,... Với các bạn đang học chuyên ngành Công nghệ thông tin thì đây là tài liệu tham khảo hữu ích.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu 2BàigiảngCấutrúcdữliệu2 Bài1:Bảngbăm(HashTable) Bài1:Bảngbăm Sốtiết:4Nộidung 1.1)Bảngbăm 1.2)Địnhnghĩahàmbăm 1.3)Mộtsốphươngphápxâydựnghàmbăm 1.4)CácphươngphápgiảiquyếtđụngđộCácthuậttoántìmkiếmđềudựavàoviệcsosánhgiátrịkhoá(Key)củaphầntửcầntìmvớicácgiátrịkhoátrongtậpcácphầntử,thaotácnày Phụthuộckíchthướccủatậpcácphầntử Thờigiantìmkiếmkhôngnhanhdophảithựchiệnnhiềuphépsosánhcóthể khôngcầnthiết(O(n),O(logn),…)=>Cóphươngpháplưutrữnàochophépthựchiệntìmkiếmvớihiệusuấtcaohơnkhông(độphứctạphằngsố)?1.1) Bảngbăm(HashTable)Vídụ:Giảsửtacómộttậpphầntửgồmcácgiátrị khoábấtkỳđượctổ chứclưu trữ dướidạngbảngchỉ mụcmphầntử như saugọilàbảngtruyxuấttrựctiếp (Directaccesstable) Phầntử cógiátrị khoákđược lưutrữtươngứngtạivịtríthứk trongbảngchỉmục Đểtìmkiếmmộtphầntửnàođó tasẽ dựavàokhoácủanóvàtra trongbảngchỉmục,nếutạivịtrí đócóphầntử thìchínhlàphần tử cầntìm,nếukhôngcóphần tử nàocónghĩalàphầntử cần tìmkhôngcótrongbảngchỉmục Thời gian tìm kiếm là hằng số Hình1.1 O(1)Đâylàdạngbảngbămcơbảna.MôtảdữliệuGiảsử K:tậpcáckhoá(setofkeys) HàmbămHF(k) A:tậpcácđịachỉ(setofaddresses).PMT =Trang1= TậpkhóaK Tậpđịachỉ Hình1.2 ABàigiảngCấutrúcdữliệu2 Bài1:Bảngbăm(HashTable) HF(k): hàmbămdùngđể ánhxạmộtkhoáktừ tậpcáckhoáKthànhmộtđịachỉtươngứngtrongtậpA.b.Cácphéptoántrênbảngbăm Khởitạo(Initialize) Kiểmtrarỗng(Empty) Lấykíchthướccủabảngbăm(Size) Tìmkiếm(Search) Thêmmớiphầntử(Insert) Loạibỏ(Remove) Saochép(Copy) Duyệt(Traverse)c.Phânloạibảngbăm Bảngbămđóng:mỗikhóa ứngvớimộtđịachỉ,thờigiantruyxuấtlàhằng số Bảngbămmở:mộtsốkhóacócùngđịachỉ,lúcnàymỗimụcđịachỉ sẽ là mộtdanhsáchliênkếtcácphầntửcócùngđịachỉ,thờigiantruyxuấtcóthể bịsuygiảmđôichút1.2) ĐịnhnghĩahàmbămLàhàmbiếnđổigiátrịkhoá(số,chuỗi…)thànhđịachỉ,chỉmụctrongbảngbăm Giátrịkhoá Hàmbăm Địachỉ,chỉmụcVídụ:hàmbămbiếnđổikhoádạngchuỗigồmnkítựthành1địachỉ(sốnguyên) int hashfunc( char *s, int n ) { int sum = 0; while( n-- ) sum = sum + *s++; return sum % 256; }Tínhđịachỉcủakhoá“AB”:hashfunc(“AB”,2)131Tínhđịachỉcủakhoá“BA”:hashfunc(“BA”,2)131Khihàmbăm2khoávàocùng1địachỉthìgọilàđụngđộ(Collision)Hàmbămtốtthỏamãncácđiềukiệnsau: Tínhtoánnhanh. Cáckhoáđượcphânbốđềutrongbảng. Ítxảyrađụngđộ.1.3) Mộtsốphươngphápxâydựnghàmbăma.Hàmbămdạngbảngtra:PMT =Trang2=BàigiảngCấutrúcdữliệu2 Bài1:Bảngbăm(HashTable) Hàmbămcóthể tổ chức ở dạngbảngtra(còngọilàbảngtruyxuất)hoặc thôngdụngnhấtlàởdạngcôngthức. Vídụsauđâylàbảngtravớikhóalàbộchữcái,bảngbămcó26địachỉtừ0 đến25.Khóaaứngvớiđịachỉ0,khoábứngvớiđịachỉ1,…,zứngvớiđịa chỉ25. Khoá Địachỉ Khóa Địachỉ Khóa Địachỉ Khóa Địachỉ a 0 h 7 o 14 v 21 b 1 I 8 p 15 w 22 c 2 j 9 q 16 x 23 d 3 k 10 r 17 y 24 e 4 l 11 s 18 z 25 f 5 m 12 t 19 / / g 6 n 13 u 20 / / Hình1.3Hàmbămdạngbảngtrađượctổchứcdướidạngdanhsáchkề.b.Hàmbămsửdụngphươngphápchia Dùngsốdư: h(k)=kmodm klàkhoá,mlàkíchthướccủabảng. vấnđềchọngiátrịm Nếuchọnm=2nthôngthườngkhôngtốtvìh(k)=kmod2n sẽ chọncùngn bitsthấpcủaknênchọnmlànguyêntố(tốt)gần ...