Bài giảng Cấu trúc dữ liệu 1: Chương 2 - Huỳnh Cao Thế Cường

Chương 2 trang bị cho người học những kiến thức về giải thuật tìm kiếm và sắp xếp. Nội dung chính trong chương này gồm có: Nhu cầu tìm kiếm và sắp xếp dữ liệu trong hệ thống thông tin, các giải thuật tìm kiếm nội, các giải thuật sắp xếp nội. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu 1: Chương 2 - Huỳnh Cao Thế Cường TRƯỜNGĐẠIHỌCANGIANGKHOAKỸTHUẬTCÔNGNGHỆMÔITRƯỜNG CẤUTRÚCDỮLIỆU1 Giảng viên phụ trách: HUỲNH CAO THẾ CƯỜNG Bộ môn Tin học email: hctcuong@agu.edu.vn 1 1 Chương 2. TÌM KIẾM VÀ SẮP XẾPNhu cầu tìm kiếm và sắp xếp dữ liệu trong HTTTCác giải thuật tìm kiếm nội  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 2 Nhu cầu tìm kiếm và sắp xếp dữ liệu trong HTTTNhu cầu?Các giải thuật tìm kiếm nội (Searching Techniques)  Tìm kiếm tuyến tính (Sequential Search)  Tìm kiếm nhị phân (Linear Search) 3 Mô tả bài toánCho mảng A[1..n] các đối tượng, có các khóa keyChúng ta cần tìm trong mảng có phần tử nào có giá trị bằng x hay không?Lưu ý:  Khi cài đặt bằng ngôn ngữ C, do chỉ số mảng trong C bắt đầu từ 0 lên các giá trị chỉ số có thể chênh lệnh so với thuật tóan  Để đơn giản: Dùng mảng các số nguyên làm cơ sở để cài đặt thuật tóan. 4 Tìm kiếm tuyến tính (Sequential Search)Ý tưởng:  Đây là giải thuật tìm kiếm cổ điển  Thuật tóan tiến hành so sánh x với lần lượt với phần tử thứ nhất, thứ hai,.. của mảng a cho đến khi gặp được phần tủ có khóa cần tìm. 5 Tìm kiếm tuyến tínhGiải thuật  Bước 1: i=1; //Bắt đầu từ phần từ đầu tiên  Bước 2: So sánh a[i].key với x có 2 khả năng • a[i].key = x: Tìm thấy, Dừng; • a[i].key # x: Sang bước 3;  Bước 3: • i=i +1; //Xét tiếp phần tử kế tiếp 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 bước 2 6 Tìm kiếm tuyến tính – ví dụTìmgiátrịx=5,x=46,x=19 0123456789101112131415a 5 7 99 13 19 15 11 19 23 28 8 30 32 3 41 46 7 Tìm kiếm tuyến tính – cài đặt Cách 1void LinearSearch(int a[], int N, int x) { int i, flag = 0; for(i=0;i Tìm kiếm tuyến tính – cài đặtCách 2int LinearSearch (int a[], int N, int x){ int i=0; while ((i Tìm kiếm tuyến tính – cài đặt Cách 3int LinearSearch (int a[], int N, int x){ int i=0; a[N] =x; //Thêm phần tử N+1 while (a[i]!=x) i++ if (i==N) return -1 ; //Không có x, đã tìm hết mảng else return i; //Tìm thấy ở vị trí i} 10 Tìm kiếm tuyến tính – đánh giá Đánh giá giải thuật: Có thể ước lượng độ phức tạp của giải thuật tìm kiếm qua số lượng các phép so sánh được tiến hành để tìm ra x. Trường hợp giải thuật tìm tuyến tính, có: Trường Số lần Giải thích hợp so sánh Tốt nhất 1 Phần tử đầu tiên có giá trị x Xấu nhất n+1 Phần tử cuối cùng có giá trị x Trung bình (n+1)/2 Giả sử xác suất các phần tử trong mảng nhận giá trị x là như nhau. Vậy giải thuật tìm tuyến tính có độ phức tạp tính toán cấp n: T(n) = O(n) 11 Tìm kiếm nhị phânNhận xét  Không phụ thuộc vào thứ tự các phần tử trong mảng  Một thuật tóan có thể được cài đặt theo nhiều cách khác nhau, kỹ thuật cài đặt ảnh hưởng đến tốc độ thực hiện của thuật tóan. 12 Tìm kiếm nhị phân (binary search)Bạn sẽ làm thế nào để tìm một tên chủ thuê bao trong danh bạ điện thoại, hoặc 1 từ (word) trong từ điển?  Tìm nơi nào đó ở giữa (danh bạ, từ điển)  So sánh nơi tên/từ nằm ở vị trí nào?  Quyết định tìm kiếm ở nửa đầu hay nửa sau danh bạ.  Lặp lại bước trên  Đây chính là ý tưởng giải thuật tìm kiếm nhị phân (the binary search algorithm) 13 Tìm kiếm nhị phânGiải thuật  Bước 1: đặt left=1; right=N; //tìm kiếm tất cả các phần tử  Bước 2: mid =(left+right)/2; //mốc so sánh • So sánh a[mid].key = x; • a[mid].key = x: Tìm thấy, Dừng; • a[mid].key >x : right = mid -1; • a[mid].key Tìm kiếm nhị phân Tìmtrongmảnga,giátrị36: 0123456789101112131415a 5 7 10 13 13 15 19 19 23 28 28 32 32 37 41 46 1.(0+15)/2=7;a[7]=19; tìmtrong8..15 2.(8+15)/2=11;a[11]=32; tìmtrong12..15 3.(12+15)/2=13;a[13]=37; tímtrong12..12 4.(12+12)/2=12;a[12]=32; tìmtrong13..12 ...nhưng13>12,=>36khôngthấy 15 Tìm kiếm nhị phân Tìmtrongmảnga,giátrị7: 0123456789101112131415a 5 7 10 13 13 15 19 19 23 28 28 32 32 37 41 46 1.(0+15)/2=7;a[7]=19; tìmtrong0..6 2.(0+6)/2=3;a[3]=13; tìmtrong0..2 3.(0+2)/2=1;a[1]=7; Kếtthúc 16 Tìm kiếm nhị phân – cài đặtvoid BinarySearch(int a[],int N, int x){ int left,right,mid, flag = 0; left = 0; right= n-1; while(left Tìm kiếm nhị phân – cài đặt ...