Những nội dung chính được trình bày trong chương 7 gồm có: Bài toán tìm kiếm, tìm kiếm tuần tự (Sequential searching), tìm kiếm nhị phân (Binary searching), cây nhị phân tìm kiếm. Mời các bạn cùng tham khảo. | 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 12. Tìm kiếm tuần tự Sequential searching . Phương pháp Đây là giải thuật đơn giản cổ điển. Cách thức làm như sau Bắt đầu từ bản ghi thứ nhất lần lượt so sánh khoá tìm kiếm với tương ứng của các bản ghi trong bảng cho đến khi tìm thấy bản ghi mong muốn hoặc đã hết danh sách mà chưa thấy. Giải thuật Cho dãy khoá K có n phần tử. Tìm xem có khoá nào bằng x nếu có đưa ra thứ tự của khoá đó nếu không có thì đưa ra giá trị 0. Trong giải thuật sử dụng khoá phụ kn 1 x. Function SequenceSearch k n x 1. Khởi đầu i 1 k n 1 x 2. Tìm kiếm trong dãy While k i x Do i i 1 3. Không tìm thấy If i n 1 then Return 0 Esle Return i Return 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à km với m L R div 2 Tìm kiếm sẽ kết thúc nếu x km Nếu xkm tìm kiếm sẽ được thực hiện tiếp với km 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 . 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 BinarySearch K n x 1. Khởi tạo L 1 R n 2. Tìm kiếm While L 4. So sánh If xk m then L m 1 Else Return m End End of While 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 BinarySearch L R x If L gt R then Loc 0 Else begin m L R div 2 If xk m then Loc BinarySearch m 1 R x Else Loc m end
