intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

KỸ THUẬT TÌM KIẾM (SEARCHING)

Chia sẻ: Batman_1 Batman_1 | Ngày: | Loại File: PPT | Số trang:32

Thêm vào BST
Báo xấu
97
lượt xem 8
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong các hệ lưu trữ và quản lý dữ liệu, thao tác tìm kiếm được thực hiện nhiều nhất để khai thác thông tin một các dễ dàng. Số lượng thông tin trong một hệ thống thông tin là đáng kể nên việc xây dựng các giải thuật tìm kiếm nhanh sẽ có ý nghĩa quan trọng.

Chủ đề:

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

Lưu

Nội dung Text: KỸ THUẬT TÌM KIẾM (SEARCHING)

  1. Môn: CẤU TRÚC DỮ LIỆU Chương 2: KỸ THUẬT TÌM KIẾM (SEARCHING) 4 tiết LT     1
  2. NỘI DUNG CHƯƠNG 2 2.1 Khái quát về tìm kiếm 2.2 Các giải thuật tìm kiếm nội (Tìm kiếm trên mảng)  Tìm tuyến tính (Linear Search)  Tìm nhị phân (Binary Search) 2.3 Các giải thuật tìm kiếm ngoại (Tìm kiếm trên tập tin)  Tìm tuyến tính (F Linear Search)  Tìm nhị phân (Binary Search) BÀI TẬP 2
  3. 2.1 Khái quát về tìm kiếm Trong các hệ lưu trữ và quản lý dữ liệu, thao tác tìm kiếm  được thực hiện nhiều nhất để khai thác thông tin m ột các d ễ dàng. Số lượng thông tin trong một hệ thống thông tin là đáng kể  nên việc xây dựng các giải thuật tìm kiếm nhanh sẽ có ý nghĩa quan trọng. Nếu tìm kiếm trong một hệ thống đã tổ chức thì việc tìm kiếm  dễ dàng hơn. Các giải thuật tìm kiếm được xây dựng nhằm mục tiêu hỗ trợ  ứng dụng có hiệu quả hơn. Các giải thuật phụ thuộc vào vào cấu trúc dữ liệu mà nó tác  động đến. Dữ liệu được lưu trữ trên bộ nhớ chính và bộ nhớ phụ. 3
  4. 2.1 Khái quát về tìm kiếm (tt) Giả sử mỗi phần tử được xem xét có một thành phần khóa  (Key) để nhận diện có kiểu dữ liệu T, các thành phần còn lại là thông tin (Info), như vậy mỗi phần tử có cấu trúc như sau: typedef struct DataElement { T Key; InfoData Info; } DataType; Để đơn giản, quan tâm thành phần dữ liệu chỉ là khóa nh ận  diện 4
  5. 2.2 Các giải thuật tìm kiếm nội Bài toán đặt ra: Giả sử có một mảng A gồm n phần tử. Cần xác định có hay không phần tử có giá trị bằng X trong m ảng M?? Nếu có phần tử X thì phần tử bằng phần tử X là ph ần tử th ứ mấy trong mảng X? Các giải thuật tìm kiếm nội đưa ra 2 cách tìm kiếm  Tìm kiếm tuần tự hay (Sequential Search) còn g ọi tìm ki ếm tuyến tính (Linear Search)  Tìm kiếm nhị phân (Binary Search) 5
  6. Tìm tuyến tính (Linear Seach) Ý tưởng: So sánh lần lượt các phần tử của mảng A với giá trị X cần tìm bắt đầu từ phần tử đầu tiên cho đến khi tìm thấy hoặc tìm hết mảng mà không tìm thấy X. Thuật toán B1: i = 1 ;// bắt đầu từ phần tử đầu tiên B2: so sánh A[i] với X, có 2 khả năng : A[i] =X : Tìm thấy. Dừng  A[i] X : Sang B3  B3: i=i+1 // Xét phần tử tiếp theo trong mảng Nếu i>n : Hết mảng, không tìm thấy.Dừng Ngược lại: lặp lại B2 6
  7. Tìm tuyến tính (Linear Seach) Ví dụ: 12 2 8 5 1 X=8 X=8 i=1 12 2 8 5 1 X=8 i=2 12 2 8 5 1 i=3 X=8 12 2 8 5 1 7 ừng D
  8. Tìm tuyến tính (Linear Seach) Cài đặt thuật toán: int LinearSearch (int A[], int n, int X) { int i = 0; while (A[i] != X && i
  9. Tìm tuyến tính (Linear Seach) Phân tích, đánh giá thuật toán:  Trường hợp tốt nhất (phần tử đầu tiên của mảng có giá trị = X)  Số phép gán G min = 1  Số phép so sánh S min = 2+1=3  Trường hợp xấu nhất (không có phần tử nào của mảng có giá trị = X)  Số phép gán G max = 1  Số phép so sánh S max = 2n + 1  Trung bình  Số phép gán G avg = 1  Số phép so sánh S avg = (3+2n + 1)/2=n+2 9
  10. Tìm tuyến tính (Linear Seach) Cải tiến thuật toán:  Mỗi bước lặp với thuật toán trên c ần th ực hi ện 2 phép so sánh  ý tưởng giảm bớt phép so sánh bằng cách thêm vào m ảng một phần tử cầm canh (sentinel/stand by) có giá tr ị bằng X đ ể nhận diện ra sự hết mảng khi duyệt . B1: i = 1 B2: A[i+1] = X B3: Nếu A[i] ≠ X Thì i++ Ngược lại: Lặp lại B3 B4: Nếu i < N Thì Tìm thấy phần tử có giá trịX ở vị trí i B5: Nguợc lại: Thì không tìm thấy phần tử có giá trị X B6: Kết thúc 10
  11. Tìm tuyến tính (Linear Seach) Cài đặt thuật toán cải tiến: int LinearSearchCaiTien (int A[], int n, int X) { int i = 0; A[N] = X; // phần tử mảng A tính từ 0 while (A[i] != X) i++; if (i < i) return (i); return (-1); } 11
  12. Tìm tuyến tính (Linear Seach) Phân tích, đánh giá thuật toán cải tiến:  Trường hợp tốt nhất (phần tử đầu tiên của mảng có giá trị = X)  Số phép gán G min = 2  Số phép so sánh S min = 2  Trường hợp xấu nhất (không có phần tử nào của mảng có giá trị = X)  Số phép gán G max = 2  Số phép so sánh S max = (N + 1) + 1  Trung bình  Số phép gán G avg = 2  Số phép so sánh S avg = N/2 + 2 12
  13. Tìm tuyến tính (Linear Seach) Ví dụ: Tìm tuyến tính 13
  14. Tìm nhị phân (Binary Seach) Ý tưởng: Phạm vi tìm kiếm là từ phần tử đầu tiên của dãy (Left  = 1) cho đến phần tử cuối cùng (Right = n) So sánh giá trị X với giá trị phần tử ở giữa của dãy A là  A[Mid] Nếu X = A[Mid] Tìm thấy  Nếu X < A[Mid] rút ngắn phạm vi tìm kiếm và Right =  Mid –1 Nếu X > A[Mid] rút ngắn phạm vi tìm kiếm và Left =  Mid +1 Lặp lại quá trình cho đến khi tìm thấy phần tử có giá trị  =X 14
  15. Tìm nhị phân (Binary Seach) Thuật toán: B1: Left = 1; Right = n B2: Mid= (Left+ Right)/2 B3: so sánh A[Mid] với X có 3 khả năng xảy ra:  A[mid]=X; // tìm thấy. Dừng  A[mid]>X; //Tiếp tục tìm trong dãy A[1]… A[mid-1] Right=mid-1 A[mid]
  16. Tìm nhị phân (Binary Seach) Ví dụ: 1 2 4 5 6 8 12 15 X=8 X=8 Left=1, Right=8, Mid=4 1 2 4 5 6 8 12 15 X=8 Left=5, Right=8, Mid=6 1 2 4 5 6 8 12 15 16
  17. Tìm nhị phân (Binary Seach) Cài đặt Thuật toán không đệ quy Int BinarySearch( int A[], int n, int X) { int left, right, mid; left=0; right=n-1; do { mid=(left+right)/2 if(X==A[mid]) return(mid); if(X
  18. Tìm nhị phân (Binary Seach) Cài đặt Thuật toán đệ quy (Recursion Algorithm) int RecursiveBinarySearch (int A[], int Left, int Right, int X) { if (Left > Right) return (-1); int Mid = (Left + Right)/2; if (X == A[Mid]) return Mid; if (X < A[Mid]) return RecursiveBinarySearch (A, Left, Mid -1,X); return RecursiveBinarySearch (A, Mid +1, Right,X); 18
  19. Tìm nhị phân (Binary Seach) Phân tích, đánh giá thuật toán đệ quy:  Trường hợp tốt nhất (phần tử đầu tiên c ủa m ảng có giá tr ị = X)  Số phép gán G min = 1  Số phép so sánh S min = 2  Trường hợp xấu nhất (không có phần t ử nào c ủa m ảng có giá trị = X)  Số phép gán G max = log2N +1  Số phép so sánh S max =3log2N +1  Trung bình  Số phép gán G avg = 1/2log2N +1  Số phép so sánh S avg = ½(3log2N + 3) 19
  20. Tìm nhị phân (Binary Seach) Thuật toán không đệ quy (Non-Recursion Algorithm) B1: First = 1 B2: Last = N B3: Nếu (First > Last) // hết phạm vi tìm kiếm Không tìm thấy Thực hiện B8 B4: Mid = (First + Last )/2 B5: Nếu (X = M[Mid]) Tìm thấy tại vị trí Mid Ngược lại: Thực hiện B6 B6: Nếu (XM[Mid]) First = Mid + 1 và lặp lại B3 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2