tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 7 - Ngô Công Thắng

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 7: Giải thuật tìm kiếm" cung cấp cho người học các kiến thức: bài toán tìm kiếm, tìm kiếm tuần tự, tìm kiếm nhị phân, cây nhị phân tìm kiếm. nội dung chi tiết. | Chương 7: Giải thuật tìm kiếm 1. Bài toán tìm kiếm * Bài toán tìm kiếm được phát biểu như sau: Cho một bảng gồm n bản ghi r1, r2 , . . . , rn; ri ( 1 x Do i:=i+1; 3. { Không tìm thấy } If i=n+1 then Return(0) Esle Return(i); Return + Tìm kiếm sẽ kết thúc nếu: x=ki + Nếu xki tìm kiếm sẽ được thực hiện tiếp với ki+1, . . . , kr với cách tương tự. Qúa trình tìm kiếm kết thúc khi tìm thấy một khoá mong muốn hoặc dãy khoá rỗng ( không tìm thấy ). 3. Tìm kiếm nhị phân (Binary searching ) Phương pháp * Phương pháp tìm kiếm thực hiện trên dãy khóa đã sắp xếp, có nội dung như sau: - Tương tự như tra tìm từ trong từ điển hoặc danh bạ điện thoại. Chỉ khác là trong tra cứu ta chọn từ ngẫu nhiên, còn trong tìm kiếm nhị phân luôn chọn khoá “ở giữa” dẫy khoá. - Giả sử có dãy khoá kL, . . ., kR thì khoá ở giữa là ki với i=(L+R) div 2 * Giải thuật: Cho dãy K gồm n khoá, sắp xếp theo thứ tự tăng dần. Tìm khoá đó có giá trị =x. Dùng biến L, R, m: chỉ số đầu, chỉ số cuối, chỉ số giữa của khoá k. Nếu tìm thấy cho ra chỉ số của khoá đó, nếu không tìm thấy cho ra 0. Function Binary_search(K,n,x) 1. { Khởi tạo } L:=1; R:=n; 2. { Tìm kiếm } While Lk[m] then L:=m+1 Else Return (m); End; 5. { Không tìm thấy } Return (0) * Giải thuật viết dạng đệ quy như sau: L, r là chỉ số đầu, chỉ số cuối của dãy K, biến nguyên Loc để đưa ra chỉ số ứng với khoá cần tìm, nếu không tìm thấy thì Loc =0. Function Binary_search(L,R,x) 1. If L>R then Loc:=0 Else begin m:=(L+R) div 2; If xk[m] then Loc:=Binary_search(m+1,R,x) Else Loc:=m; end; 2. Return(Loc) . Đánh giá Phép tính tích cực là phép so sánh L25 nên lại tìm trong cây con phải. So sánh ta có x=cây con phải cũng là 28 nên phép tìm kiếm được thoả mãn. . Giải thuật tìm kiếm * Đối với một cây nhị phân để tìm kiếm xem một khoá x nào đó có trên cây đó không? Ta có thể thực hiện như sau: So sánh x với khoá ở gốc và một trong 4 tình huống sau đây sẽ xuất hiện: 1- Không có gốc cây ( cây rỗng): X không có trên cây, phép tìm kiếm không thoả .