Kiến trúc máy tính - Part 13

Tập S các phần tử được lưu bằng mảng hoặc danh sách liên kết. Thuật toán tìm kiếm: Xuất phát từ phần tử đầu của dãy, thực hiện so sánh khóa của nó với k. Nếu trùng nhau thì dừng lại, nếu không trùng thì lặp lại với phần tử tiếp theo. Quá trình dừng lại khi tìm thấy hoặc không còn phần tử nào nữa. Khi đó thông báo không tìm thấy.
Nội dung trích xuất từ tài liệu:
Kiến trúc máy tính - Part 13 Bài13.TìmkiếmSearchBàitoán Input:ChomộtdãyScácphầntử,mỗiphầntửlàmột bộgồmkhóagiatrị(keyvalue).Mộtkhóakbấtkỳ.Output:TrongScóphầntửcókhóakhaykhông? 1 SearchCácphươngpháptìmkiếm Tìmkiếmtuầntự(sequencesearch) Tìmkiếmnhịphân(Binarysearch) Bảngbăm(hashtable) 2 Search1.Tìmkiếmtuầntự TậpScácphầntửđượclưubằngmảng hoặcdanhsáchliênkết. Thuậttoántìmkiếm:• Xuất phát từ phần tử đầu của dãy, thực hiện so sánhkhóa của nó với k. Nếu trùng nhau thì dừng lại, nếukhôngtrùngthìlặplạivớiphầntửtiếptheo.• Quátrìnhdừnglạikhitìmthấyhoặckhôngcònphầntửnàonữa.Khiđóthôngbáokhôngtìmthấy. 3 SearchVídụ1 ChodãyS: 0 45 3 34 13 7 43 9 11 Tìmxemtrongdãycóphầntửk=33 Quátrìnhtìmkiếm 0 45 3 34 13 7 43 9 11Bước1 Bước2 Bước3 Bước4 Bước5 Bước6 Bước7 Bước8 Bước9 •Khôngtìmthấy 4 SearchVídụ2 ChodãyS: 0 45 3 34 13 7 43 9 11 Tìmxemtrongdãycóphầntửk=13 Quátrìnhtìmkiếm 0 45 3 34 13 7 43 9 11Bước1 Bước2 Bước3 Bước4 Bước5 •Tìmthấy,tạivịtrí5 5 SearchThuậttoánInput:Cho một dãy S các phần tử, mỗi phần tử là một bộ key và value. Một khóa k bất kỳ.Output:Trong S có phần tử có khóa k hay không?found = 0; i =1;while ((chưa duyệt hết S ) && (found= =0) ){ if (S[i].key == k) found =1; i = i+1;}return found; 6 SearchThờigianchạy Trongtrườnghợpxấunhấtthuậttoán phảiduyệtquatấtcảcácphầntửcủaS. VậythờigianchạylàO(n) 7 Search2.Tìmkiếmnhịphân TậpSđượctổchứclưutrữdựatrên mảng TậpSđượctổchứclưutrữdạngcâynhị phân 8 Search2.1Tìmkiếmnhịphântrênmảng CácphầntửcủaSđượclưutrữtrongmảngvàđược sắpxếptheothứtựtăngdần(giảmdần)củagiátrị khóa(key). Thuật toán tìm kiếm nhị phân được thiết kế dựa trênchiếnlượcchiavàtrị Thuậttoán:Sosánhkhóa k vớikhóacủaphầntử ởgiữadãy. •Nếutrùngthìthôngbáotìmthấyvàdừng •Nếuk>thìgọiđệquitìmtrênnửacuốidãy •NếukVídụ1•Chodãydướiđây.Tìmphầntửk=6 0 1 3 4 5 7 8 9 11 14 16 18 19 Bước1:6< 0 1 3 4 5 7 Bước2:6> 4 5 7 Bước3:6> 7 Bước4:6< Rỗng Khôngtìmthấy Bước5:6 10 SearchVídụ2•Chodãydướiđây.Tìmphầntửk=5 0 1 3 4 5 7 8 9 11 14 16 18 19 Bước1:5< 0 1 3 4 5 7 Bước2:5> 4 5 7 Tìmthấy Bước3:5= 11 SearchThuậttoántìmkiếmnhịphântrênmảngAlgorithmBinarySearch(S,k,n); Found=0; i=1; j=n; while(iThờigianchạy Saumỗilầntìmkiếm,thìdãycầntìmlại đượcchiađôivàtachỉphảitìmtrênmộtnửa Trongtrườnghợpxấunhấtlàkhôngtìmthấy phầntửcókhóak.Vànhưvậytaphảithực hiệnchiađôiliêntiếpđếnkhiđượcdãyrỗng. Sốlầnthựchiệnchiađôilà:log2n VậythờigianchạylàO(log2n) 13 Search2.2Tìmkiếmtrêncâytìmkiếmnhịphân Địnhnghĩa:câytìm 6 kiếmnhịphânlàcây < < nhịphânthỏamãn: 2 10 Nútchacókhóalớnhơn  8 ...