zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ 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ự

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PDF | Số trang:186

Báo xấu

185
lượt xem 22
download

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

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.

Chủ đề:

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

Lưu

Nội dung Text: 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 2 Cá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 2
2.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 3
2.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 4
2.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 5
2.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 6
2.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=0 09/11/2008 Cấu trúc dữ liệu 1 7
2.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=2 09/11/2008 Cấu trúc dữ liệu 1 8
2.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(i
2.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 10
2.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 11
2.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 12
2.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á phần hầ tử trong t d h sách, danh á h do d vậy ậ đây đâ là phương pháp tổng quát nhất để tìm kiếm trên một danh sách bất kỳ. kỳ • Đối với mảng có thứ tự thuật toán này sẽ không tối ưu vì không tận dụng được tính chất có thứ tự của các phần tử trong mảng. 09/11/2008 Cấu trúc dữ liệu 1 13
2.2. Các giải thuật tìm kiếm 2 2 2 Tìm kiếm nhị phân 2.2.2. Đối với những dãy đã có thứ tự (giả sử thứ tự tăng), ) các phần hầ tử trong dãy d có quan hệ h ai -1 ≤ ai ≤ ai+1 Nếu x > ai thì x chỉ có thể xuất hiện trong đoạn [[ai+1 ,ann-11] của dãy. y Nếu x < ai thì x chỉ có thể xuất hiện trong đoạn [a0 ,aai-1 i 1] của dãy. dãy 09/11/2008 Cấu trúc dữ liệu 1 14
2.2. Các giải thuật tìm kiếm 2 2 2 Tìm kiếm nhị phân 2.2.2. Ý tưởng: So sánh x với phần tử giữa mảng, “bằng” thì kết thúc nếu không thì tùy giá trị của x mà ta sẽ thu hẹp thúc, không gian tìm kiếm và lặp lại bước trên cho đến khi tìm thấy, hoặc không gian tìm rỗng. 09/11/2008 Cấu trúc dữ liệu 1 15
2.2. Các giải thuật tìm kiếm 2 2 2 Tìm kiếm nhị phân 2.2.2. Thuật toán: Bước 1: Khởi tạo left = 0, right = n - 1 Bước 2: Xác định phần tử ở giữa: mid = (left + right)/2 Bước 3: So sánh x với a[mid]. Nếu x = a[mid] thì sang bước 4, nếu không sang bước 5. Bước 4: Kết ế luận l “Tìm thấy”. hấ Kếtế thúc. h Bước 5: Nếu x < a[mid] thì sang bước 6, nếu không sang bước 7. 09/11/2008 Cấu trúc dữ liệu 1 16
2.2. Các giải thuật tìm kiếm 2 2 2 Tìm kiếm nhị phân 2.2.2. Thuật toán: Bước 6: Giới hạn không gian tìm kiếm: right = mid -1, sang bước 8. Bước 7: Giới hạn không gian tìm kiếm: left = mid + 1, sang bước 8 Bước 8: Nếu ế left l f > right i h sang bước b 9, không kh thì h quay lại l i bước 2. Bước 9: 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 17
2.2. Các giải thuật tìm kiếm 2 2 2 Tìm kiếm nhị phân 2.2.2. Ví dụ: Cho dãy số a gồm 8 phần tử: 1 2 4 5 6 8 12 15 Giá trị cần ầ tìm là 8 09/11/2008 Cấu trúc dữ liệu 1 18
2.2. Các giải thuật tìm kiếm 2 2 2 Tìm kiếm nhị phân 2.2.2. left = 0, right = 7, mid = 3 09/11/2008 Cấu trúc dữ liệu 1 19
2.2. Các giải thuật tìm kiếm 2 2 2 Tìm kiếm nhị phân 2.2.2. left = 4, right = 7, mid = 5 09/11/2008 Cấu trúc dữ liệu 1 20

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.