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

TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ THUẬT GIẢI

Chia sẻ: Nguyen Quoc Khanh | Ngày: | Loại File: PPT | Số trang:35

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

Nhị Phân Ý Tưởng : Phạm vi tìm kiếm ban đầu của chúng ta là từ phần tử đầu tiên của dãy (Left = 1) cho đến phần tử cuối cùng của dãy (Right = N). So sánh giá trị X với giá trị phần tử đứng ở giữa của dãy M là M[Mid]. Nếu X = M[Mid]: Tìm thấy Nếu X M[Mid]: Rút ngắn phạm vi tìm kiếm về nửa sau của dãy M (Left = Mid+1) Lặp lại quá trình này cho đến khi tìm thấy phần tử có giá trị X hoặc phạm vi tìm kiếm của chúng ta...

Chủ đề:

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

Lưu

Nội dung Text: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ THUẬT GIẢI

  1. CHƯƠNG I : TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ THUẬT GI ẢI CHƯƠNG II : MỘT SỐ THUẬT TOÁN TÌM KIẾM VÀ SẮP XẾP CHƯƠNG III : DANH SÁCH LIÊN KẾT - NGĂN XẾP VÀ HÀNG ĐỢI CHƯƠNG IV : CÂY
  2. I. KHÁI NIỆM & KHAI BÁO BIẾN 6 n 4 14 22 38 27 15 a 0 1 2 3 4 5 6 7 8 Cú pháp khai báo các phần tử của mảng #define size 200 int n; // số phần tử thực tế [size];
  3. II. MỘT SỐ TÁC VỤ CƠ BẢN #include #define size 200 1. Nhập & Xuất mảng int a[size]; void main() { int n, i; //Nhap so phan tu cin >> n //Nhap day for (i=0;i> a[i]; //Xuat day for (i=0;i
  4. II. MỘT SỐ TÁC VỤ CƠ BẢN 1. Nhập & Xuất mảng void Input (int mang[ ], int n) void Output (int mang[ ], int n) { { int i; int i; for (i = 0 ; i < n ; i++) for (i = 0 ; i < n ; i++) { cout
  5. II. MỘT SỐ TÁC VỤ CƠ BẢN 2. Chèn 1 phần tử x vào mảng tại vị trí thứ k 4 14 19 15 22 38 27 a 0 1 2 3 4 5 6 7 8 k void Insert (int x, int a[ ], int& n, int k) n=6 n=7 { int i; if ( k > n + 1 ) cout
  6. II. MỘT SỐ TÁC VỤ CƠ BẢN 2. Xóa 1 phần tử x trong mảng tại vị trí thứ k 4 22 27 15 38 14 A 0 1 2 3 4 5 6 7 8 k n=5 n=6 void Delete (int a[ ], int& n , int k) { int i; if ( k > n ) cout
  7. II. TÌM KIẾM 1. Tuần tự Ý Tưởng : 1 2 n 3 5 10 13 6 9 a[0] a[n-1] i=0 i=1 i=2 i=3 i=4 i=5 i 3 -1 Tìm thấy tại vị trí 4 13 19 Tìm không thấy
  8. II. TÌM KIẾM 1. Tuần tự Ý Tưởng :  Duyệt từ đầu đến phần tử cần tìm  Nếu tìm thấy thì dừng, ngược lại thì duyệt tới cuối mảng thì cho kết quả tìm không thấy
  9. II. TÌM KIẾM 1. Tuần tự Giải thuật : Bước 1 : Cho i = 0 Bước 2 : Nếu a[i] == x thì dừng chương trình, xuất kết quả tìm th ấy Bước 3 : Ngược lại tăng i lên một đơn vị Bước 4 : Lặp lại bước 2 và 3 đến khi i >= n thì qua bước 5 Bước 5 : Kết luận không tìm thấy
  10. II. TÌM KIẾM 1. Tuần tự Giải thuật : Cài đặt chương trình int Sequence_Search (int a[ ], int n, int x) Input : Hàm Sequence_Search { Cho i = 0 a : mảng int i = 0; do x : giá trị phần tử cần tìm x : giá trị phần tử cần tìm Thực hiện { Nếu a[i] == x thì if (a[i] == x) dừng ct, trả về kết quả tìm thấy return i; Output : else ngược lại tăng i thêm 1 i++; i : vị trí của x trong mảng Lặp lại thực hiện đến khi i >= n } while (i < n); -1 : tìm không thấy return -1; Trả về kết quả tìm không thấy }
  11. II. TÌM KIẾM 2. Nhị phân 3 5 10 13 16 19 23 25 30 33 36 49 Left Right a[m] a[m] a[m] m Tìm thấy tại 36 vị trí 11 m=(Left + Right)/2 m=(Left + Right)/2 + Right)/2 m=(Left = (0+11)/2 = (6+11)/2 = (9+11)/2 =5 =8 = 10
  12. II. TÌM KIẾM 2. Nhị phân 3 5 10 13 16 19 23 25 30 33 36 49 Left Right a[m] a[m] a[m] m Tìm thấy tại 23 vị trí 7 m=(Left + Right)/2 m=(Left + Right)/2 Right)/2 m=(Left + = (0+11)/2 = (6+7)/2= (6+11)/2 =5 =6 =8
  13. II. TÌM KIẾM 2. Nhị phân 3 5 10 13 16 19 23 25 30 33 36 49 Left Right a[m] a[m]a[m] a[m] -1 Tìm ko thấy 24 m=(Left + m=(Left + Right)/2 m=(Left + Right)/2 Right)/2 Right)/2 m=(Left + = (0+11)/2 (7+7)/2 = (6+7)/2= (6+11)/2 = =5 =6=7 =8
  14. II. TÌM KIẾM 2. Nhị Phân Ý Tưởng :  Phạm vi tìm kiếm ban đầu của chúng ta là từ phần tử đầu tiên của dãy ( Left = 1) cho đến phần tử cuối cùng của dãy (Right = N).  So sánh giá trị X với giá trị phần tử đứng ở giữa của dãy M là M[Mid].  Nếu X = M[Mid]: Tìm thấy  Nếu X < M[Mid]: Rút ngắn phạm vi tìm kiếm về nửa đầu của dãy M (Right = Mid– 1)  Nếu X > M[Mid]: Rút ngắn phạm vi tìm kiếm về nửa sau của dãy M (Left = Mid+1)  Lặp lại quá trình này cho đến khi tìm thấy phần tử có giá trị X hoặc phạm vi tìm kiếm của chúng ta không còn nữa (Left > Right).
  15. II. TÌM KIẾM 2. Nhị Phân Giải thuật : Bước 1 : Cho L = 0; R = n-1 Bước 2 : m = (L + R) /2 Bước 3 : Nếu a[m] = x thì dừng ct, báo kết quả Bước 4 : Nếu x > a[m] thì tăng L lên m + 1 Bước 5 : Ngược lại giảm R xuống m - 1 Bước 6 : Lặp lại bước 2,3,4,5, cho đến khi L > R thì qua bước 7 Bước 7 : Kết luận không tìm thấy
  16. II. TÌM KIẾM 2. Nhị Phân Giải thuật: Cài đặt chương trình Hàm Binary_Search int Binary_Search(int x, int a[ ], int n) { Cho Left = 0, Right = n-1 int L = 0, R = n-1; int m; while (L a[m] thì Left = m+1 else R = m -1; ngược lại Right = m-1 } return -1; //Ket luan khong tim thay x Kết thúc tìm kiếm trong mảng tìm không } thấy Trả về kết quả tìm không thấy (-1)
  17. III. SẮP XẾP 1. Selection Sort (Sắp xếp chọn trực tiếp) Ý Tưởng : 3 15 30 23 6 11 53 25 13 8 36 49 3 6 8 11 13 15 23 25 30 36 53 49
  18. III. SẮP XẾP 1. Selection Sort ( Sắp xếp chọn trực tiếp) Ý Tưởng :  Ta chọn phần tử có giá trị nhỏ nhất trong N Là phương pháp sắp xếp bằng cách chọn phần tử bé phần tử chưa có thứ tự này để đưa lên đầu nhóm.t xếp vào vị trí thứ nhất, tương tự với các phần nhấ tử  Sau thứ thứ nhthứ ba,... phần tử nhỏ nhất nhỏ lần hai, ất chọn lựa và đưa lên đầu nhóm chúng ta còn l ại N-1 phần tử đứng ở phía sau dãy M chưa có thứ t ự.  Chúng ta tiếp tục chọn phần tử có giá trị nhỏ nhất trong N-1 phần tử chưa có thứ t ự này để đưa lên đầu nhóm chưa thứ tự này (N-1)  Làm tiếp tục cho đến cuối dãy
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