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

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ìmkiếm của chúng ta...
Nội dung trích xuất từ tài liệu:
TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ THUẬT GIẢICHƯƠNG I : TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ THUẬT GI ẢICHƯƠNG II : MỘT SỐ THUẬT TOÁN TÌM KIẾM VÀ SẮP XẾPCHƯƠNG III : DANH SÁCH LIÊN KẾT - NGĂN XẾP VÀ HÀNG ĐỢICHƯƠNG IV : CÂYI. 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];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;iII. 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 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 kvoid Insert (int x, int a[ ], int& n, int k) n=6 n=7{ int i; if ( k > n + 1 ) cout 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=6void Delete (int a[ ], int& n , int k){ int i; if ( k > n ) cout II. TÌM KIẾM1. 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ấyII. TÌM KIẾM1. 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ấyII. TÌM KIẾM1. 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ấyII. TÌM KIẾM1. 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ìmThự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ảngLặ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 }II. TÌM KIẾM2. 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ại36 ...