Các thuật toán tìm kiếm

Chia sẻ: Nguyen Nam | Ngày: | Loại File: PPT | Số trang:16

Thêm vào BST

Báo xấu

324
lượt xem 36
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Thăm tất cả các fần tử của mảng bắt đầu từ fần tử đầu tiên. So sánh key với mỗi fần tử của list hoặc mảng. Nếu fần tử tìm kiếm được tìm thấy, chỉ số của nó(vị trí trong mảng) được trả về.Nếu tìm kiếm không thành công thì trả về -1. Lưu ý rằng tìm kiếm tuần tự không đòi hỏi các fần tử của list fải được đặt theo 1 thứ tự đặc biệt nào.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Các thuật toán tìm kiếm

Chủ đề của tuần thuật toán tìm kiếm Các Tìm kiếm tuần tự Sử dụng lính gác Tìm kiếm tự sắp xếp
Tìm kiếm tuần tự (linear search) tất cả các fần tử của mảng bắt đầu từ fần  Thăm tử đầu tiên.  So sánh key với mỗi fần tử của list hoặc mảng.  Nếu fần tử tìm kiếm được tìm thấy, chỉ số của nó(vị trí trong mảng) được trả về.Nếu tìm kiếm không thành công thì trả về -1.  Lưu ý rằng tìm kiếm tuần tự không đòi hỏi các fần tử của list fải được đặt theo 1 thứ tự đặc biệt nào.
Sequential Search (tìm kiếm tuần tự) int LinearSearch (T M[], int N, T X){ int k = 0; while (M[k] != X && k < N) k++; if (k < N) return (k); return (-1); }
Ví dụ #include int sequential_search(char* items,int count,char key) { Register int t; for(t=0;t
Lính canh (Sentinel)  Lưu ý rằng mỗi lần lặp đòi hỏi 2 điều kiện được kiểm tra và 1 câu lệnh được thi hành.  Chúng ta có thể tránh kiểm tra cuối mảng trong mỗi bước lặp bằng cách chèn 1 giá trị đích (giá trị mà ta cần tìm) như là 1 fần tử ”lính canh” vào cuối của mảng.  Ta đặt nó tại vị trí n và làm theo thuật toán sau:
Sentinel kiếm tuần tự từ vị trí 0 cho đến khi giá  Tìm trị đích được tìm thấy.(Giá trị này chắc chắn sẽ được tìm thấy)  Nếu giá trị được tìm thấy ở vị trí n thì lính canh đã được tìm thấy, tìm kiếm thất bại.  Nếu không thì tìm kiếm thành công, trả về chỉ số đầu tiên mà ở đó giá trị đích được tìm thấy.
Tìm kiếm lính canh int LinearSentinelSearch (T M[], int N, T X){ int k = 0; M[N]=X; while (M[k] != X) k++; return k-1; }
Exercise 6-1 Giả sử rằng bạn viết 1 quyển danh bạ.  Khai báo 1 cấu trúc “Address” chứa ít nhất các trường  name, telephone number, email address, và viết 1 chương trình có thể thao tác với 100 địa chỉ. Đọc khoảng 10 địa chỉ từ file đầu vào, tìm kiếm 1 name  bằng tìm kiếm tuần tự, và ghi dữ liệu fù hợp đầu tiên ra file đầu ra. (1) Triển khai chương trình này sử dụng mảng cấu trúc. - (2) Triển khai chương trình này sử dụng danh sách liên - kết đơn hoặc đôi. Xác thực tìm kiếm thứ 2 đã được tăng tốc bằng cách chuyển dữ liệu fù hợp lên đầu của list. (Tìm kiếm tự tổ chức).
Exercise 6-2: tìm kiếm mảng bằng tìm kiếm tuần tự  Đọc 11 số nguyên từ 1 đầu vào chuẩn và gán 10 số đầu tiên vào mảng.  Nếu số nguyên thứ 11 có ở trong mảng thì in ra vị trí của nó, nếu không thì in ra 0.
Queue (chuyển lên trước)  Tạo 1 hàng đợi chứa các số nguyên, kích thước queue được ấn định là 10.  Đọc các số nguyên được fân cách bởi dấu khoảng trống từ 1 đầu vào chuẩn, và thêm chúng vào queue.Khi chương trình đọc đến số thứ 11, hàng đợi đã đầy.Chương trình fải loại bỏ số đầu tiên và thêm vào số thứ 11.In ra số bị loại bỏ theo đầu ra chuẩn.  Tiến hành với tất cả các số theo cách này.
Tìm kiếm tự sắp xếp (chuyển lên trước)  Mỗi fần tử được tìm kiếm/yêu cầu được chuyển lên fía trước.  Xem hình trong Slide tiếng anh.
Tìm kiếm tự sắp xếp int search( int key,int r[], int n ) { int i,j; int tempr; for ( i=0; i0 ) { tempr = r[i]; for (j=0, j
Tìm kiếm tự sắp xếp int search( int key,int r[], int n ) { int i; int tempr; for ( i=0; i0 ) { /*** Đổi chỗ với fần tử đi trước ***/ tempr = r[i]; r[i] = r[i-1]; r[--i] = tempr; }; return( i ); } else return( -1 );
Exercise : List tự sắp xếp  Sửa 1 list mà bạn đã tạo ở bài tập trước mà được tự sắp xếp bằng chiến lược “chuyển lên trước”.  Phát triển hàm tìm kiếm 1 fần tử trong list.
Exercise : List tự sắp xếp  Triển khai 1 list tự sắp xếp bằng cách sử dụng chiến lược đổi chỗ (hoán vị).
Exercises Viết 1 chương trình theo đặc tả sau:  [Format] look character_string// đinh dang nhập vào [mô tả] Tất cả các từ bắt đầu với xâu kí tự string đã ghi trong file /user/share/dict/words được đưa ra màn hình. [Ví dụ] % look computer computer computerize computerized computerizes computerizing Computers  Gợi ý: Sử dụng tham số trong hàm main() để thực hiện yêu cầu đề bài.