Bài giảng Cấu trúc dữ liệu: Chương 2 - Các giải thuật tìm kiếm và sắp thứ tự

Bài giảng Cấu trúc dữ liệu: Chương 2 - Các giải thuật tìm kiếm và sắp thứ tự được biên soạn nhằm trang bị cho các bạn những kiến thức về giải thuật tìm kiếm (tìm kiếm tuyến tính, tìm kiếm nhị phân); các giải thuật sắp xếp nội. Mời các bạn tham khảo bài giảng để bổ sung thêm kiến thức về lĩnh vực này.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu: Chương 2 - Các giải thuật tìm kiếm và sắp thứ tựChương 2Các giải thuật tìm kiếm và sắp thứ tự2.1. Giới thiệu chung • Trong hầu hết các hệ lưu trữ, quản lý dữ liệu, thao tác tìm kiếm thường được thực hiện nhất để khai thác thông tin. • Do các hệ thống thông tin thường phải lưu trữ một khối lượngg dữ liệu đángg kể, nên việc xâyy dựngg các giải thuật cho phép tìm kiếm nhanh sẽ có ý nghĩa rất lớn. • Nếu dữ liệu trong hệ thống đã được tổ chức theo một trật tự nào đó, thì việc tìm kiếm sẽ tiến hành nhanh chóng và hiệu quả hơn.09/11/2008 Cấu trúc dữ liệu 1 22.1. Giới thiệu chung • Có nhiều giải thuật tìm kiếm và sắp xếp • Mức độ hiệu quả của từng giải thuật phụ thuộc vào tính chất của cấu trúc dữ liệu cụ thể mà nó tác động đến. • Dữ liệu được lưu trữ chủ yếu trong bộ nhớ chính và trên bộ nhớ phụ, do đặc điểm khác nhau của thiết bị lưu trữ, các thuật toán tìm kiếm và sắp xếp được xây dựng cho các cấu trúc lưu trữ trên bộ nhớ chính hoặc phụ cũng có những đặc thù khác nhau.09/11/2008 Cấu trúc dữ liệu 1 32.2. Các giải thuật tìm kiếm Bài toán: Tìm vị trí xuất hiện của phần tử có giá trị x trên danh sách đặc a. Input: - Một dãy số nguyên a0, a1, ... ,an-1 i t a[n-1]; int [ 1] - Khoá cần tìm là x int x; Output: - Kết ết luận uậ có pphần ầ tử nào ào có khóa óa làà x hay ay không ô g - Vị trí của phần tử có khóa x (nếu có)09/11/2008 Cấu trúc dữ liệu 1 42.2. Các giải thuật tìm kiếm 2 2 1 Tìm kiếm tuyến tính 2.2.1. Ý tưởng: Lần lượt so sánh x với các phần tử của mảng, mảng bắt đầu từ a[0]… a[n-1]. Nếu “gặp” thì kết thúc, nếu không thì kiểm tra cho đến khi hết mảng.09/11/2008 Cấu trúc dữ liệu 1 52.2. Các giải thuật tìm kiếm 2 2 1 Tìm kiếm tuyến tính 2.2.1. Thuật toán: Bước 1: Cho biến i giá trị khởi đầu là 0 Bước 2: So sánh x với a[i], a[i] nếu x = a[i] thì sang bước 3, 3 nếu không sang bước 4. B ớ 3: Bước 3 Kết luận l ậ “Tìm “Tì thấy”. thấ ” Kết thúc. thú Bước 4: Tăng giá trị i thêm một đơn vị Bước 5: Kiểm tra i, nếu i ≥ n thì sang bước 6, không thì quay lại bước 2 Bước 6: Kết luận “Không tìm thấy”. Kết thúc.09/11/2008 Cấu trúc dữ liệu 1 62.2. Các giải thuật tìm kiếm 2 2 1 Tìm kiếm tuyến tính 2.2.1. Ví dụ: Cho dãy số a 12 2 8 5 1 6 4 15 Giá trị cần tìm: 8 i=009/11/2008 Cấu trúc dữ liệu 1 72.2. Các giải thuật tìm kiếm 2 2 1 Tìm kiếm tuyến tính 2.2.1. • i=1 • i=209/11/2008 Cấu trúc dữ liệu 1 82.2. Các giải thuật tìm kiếm 2 2 1 Tìm kiếm tuyến tính 2.2.1. Cài đặt: int LinearSearch(int a[],int n,int x) { int i=0; while(i2.2. Các giải thuật tìm kiếm 2 2 1 Tìm kiếm tuyến tính 2.2.1. Nhận xét: Thuật toán trên có 1 điểm hạn chế: phải kiểm tra 2 lần trong mỗi vòng lặp. lặp ⇒ Khắc phục: Sử dụng kỹ thuật phầnầ tử “lính canh”, nghĩa là ta cho thêm 1 phần tử a[n]=x, như vậy, bảo đảm luôn tìm thấy ấ x trong mảng.09/11/2008 Cấu trúc dữ liệu 1 102.2. Các giải thuật tìm kiếm 2 2 1 Tìm kiếm tuyến tính 2.2.1. Cài đặt: int LinearSearch(int a[],int n,int x) { int i=0; a[n]=x; while(x!=a[i]) i++; if (i==n) return etu -1;; // tìm hết mảng nhưng không có x else return i; // tìm thấy x tại vị trí i }09/11/2008 Cấu trúc dữ liệu 1 112.2. Các giải thuật tìm kiếm 2 2 1 Tìm kiếm tuyến tính 2.2.1. Đánh giá: Vậy giải thuật tìm kiếm tuyến tính có độ phức tạp tính toán cấp n: T(n) = O(n)09/11/2008 Cấu trúc dữ liệu 1 122.2. Các giải thuật tìm kiếm 2 2 1 Tìm kiếm tuyến tính 2.2.1. Nhận xét: • Giải thuật tìm tuyến tính không phụ thuộc vào thứ tự của ủ cácá p ...