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

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

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

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

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.

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 1: Chương 2 - Huỳnh Cao Thế Cường

  1. TRƯỜNG ĐẠI HỌC AN GIANG KHOA KỸ THUẬT­ CÔNG NGHỆ ­ MÔI TRƯỜNG CẤU TRÚC DỮ LIỆU 1 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. Tìm kiếm tuyến tính – ví dụ Tìm giá trị x =5, x=46, x=19  0    1     2    3    4    5     6     7   8     9  10   11   12  13  14   15 a 5 7 99 13 19 15 11 19 23 28 8 30 32 3 41 46 7
  8. Tìm kiếm tuyến tính – cài đặt  Cách 1 void LinearSearch(int a[], int N, int x) { int i, flag = 0; for(i=0;i
  9. Tìm kiếm tuyến tính – cài đặt Cách 2 int LinearSearch (int a[], int N, int x) { int i=0; while ((i
  10. Tìm kiếm tuyến tính – cài đặt  Cách 3 int 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. Tìm kiếm nhị phân Tìm trong mảng a, giá trị 36:  0    1     2    3    4    5     6     7   8     9  10   11   12  13  14   15 a 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ìm trong 8..15 2. (8+15)/2=11; a[11]=32; tìm trong 12..15 3. (12+15)/2=13; a[13]=37; tím trong 12..12 4. (12+12)/2=12; a[12]=32; tìm trong 13..12 ...nhưng 13>12, => 36 không thấy  15
  16. Tìm kiếm nhị phân Tìm trong mảng a, giá trị 7:  0    1     2    3    4    5     6     7   8     9  10   11   12  13  14   15 a 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ìm trong 0..6 2. (0+6)/2=3; a[3]=13; tìm trong 0..2 3. (0+2)/2=1; a[1]=7; Kết thúc 16
  17. Tìm kiếm nhị phân – cài đặt void BinarySearch(int a[],int N, int x) { int left,right,mid, flag = 0; left = 0; right= n-1; while(left
  18. Tìm kiếm nhị phân – cài đặt 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; //thấy x tại vị trí mid else if(x
  19. Tìm kiếm nhị phân Nhận xét:  Chỉ áp dụng cho dãy các phần tử đã có thứ tự  Tiết kiệm thời gian hơn so với tìm tiếm tuần tự.  Nếu dãy chưa được sắp xếp thứ tự? • Sắp xếp • Tìm kiếm • Tốn thời gian 19
  20. Các giải thuật sắp xếp nội  Mô tả bài tóan  Các phương pháp sắp xếp thông dụng  Phương pháp chọn trực tiếp – Selection Sort  Phương pháp chèn trực tiếp – Insertion sort  Phương pháp đổi chỗ trực tiếp – Interchange Sort  Phương pháp nổi bọt - Bubble Sort  Sắp xếp cây – Heap Sort  Sắp xếp với độ dài bước giảm dần – Shell Sort  Sắp xếp dựa trên phân hoạch – Quick Sort  Sắp xếp theo phương pháp trôn trực tiếp – Merge Sort  Sắp xếp theo phương pháp cơ số - Radix Sort 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