Nắm vững, minh họa và tính toán được các phép gán (hoán vị) các giải thuật sắp xếp cơ bản trên mảng một chiều Cài đặt được các giải thuật bằng ngôn ngữ C/C++ | Chương 3 Cấu trúc dữ liệu động Nắm vững khái niệm về kiễu dữ liệu tĩnh và động Nắm vững cách tổ chức dữ liệu động bằng danh sách liên kết và minh họa được các thao tác xử lý trên danh sách liên kết đơn Cài đặt minh họa được các thao tác của danh sách đơn bằng ngôn ngữ C/ C++ Cho một mảng có N=8 phần tử 1 2 3 4 5 6 7 8 Làm sao để chèn thêm số 6 vào mảng tại vị trí 5 1 2 3 4 5 6 7 8 9 Bổ sung thêm Giả sử cần thêm tiếp 1 phần tử ? Làm sao để chèn thêm số 6 vào mảng tại vị trí 5 Hãy cài đặt hàm (bằng ngôn ngữ C/C++) chèn một phần tử có giá trị x vào một mảng số nguyên a, kích thước n (có thứ tự tăng dần) sao cho mảng a vẫn có thứ tự tăng dần, theo mẫu hàm như sau: void ChenX(int a[], int n, int x, int vt); Làm sao để xóa phần tử 9 ? 1 2 3 4 5 6 7 8 Làm sao để xóa phần tử 9 ? 1 2 3 4 5 6 7 8 Hãy cài đặt hàm (bằng ngôn ngữ C/C++) xóa phần tử có giá trị x (nếu có) trong mảng số nguyên a, kích thước n (giả sử giá trị các phần tử trong mảng không trùng nhau), theo mẫu hàm . | Chương 3 Cấu trúc dữ liệu động Nắm vững khái niệm về kiễu dữ liệu tĩnh và động Nắm vững cách tổ chức dữ liệu động bằng danh sách liên kết và minh họa được các thao tác xử lý trên danh sách liên kết đơn Cài đặt minh họa được các thao tác của danh sách đơn bằng ngôn ngữ C/ C++ Cho một mảng có N=8 phần tử 1 2 3 4 5 6 7 8 Làm sao để chèn thêm số 6 vào mảng tại vị trí 5 1 2 3 4 5 6 7 8 9 Bổ sung thêm Giả sử cần thêm tiếp 1 phần tử ? Làm sao để chèn thêm số 6 vào mảng tại vị trí 5 Hãy cài đặt hàm (bằng ngôn ngữ C/C++) chèn một phần tử có giá trị x vào một mảng số nguyên a, kích thước n (có thứ tự tăng dần) sao cho mảng a vẫn có thứ tự tăng dần, theo mẫu hàm như sau: void ChenX(int a[], int n, int x, int vt); Làm sao để xóa phần tử 9 ? 1 2 3 4 5 6 7 8 Làm sao để xóa phần tử 9 ? 1 2 3 4 5 6 7 8 Hãy cài đặt hàm (bằng ngôn ngữ C/C++) xóa phần tử có giá trị x (nếu có) trong mảng số nguyên a, kích thước n (giả sử giá trị các phần tử trong mảng không trùng nhau), theo mẫu hàm như sau: void XoaX(int a[], int &n, int x); Độ phức tạp của chèn/ xóa trên mảng 1 chiều là O(n) Giải quyết vấn đề phức tạp khi chèn/ xóa? Giải quyết vấn đề giới hạn kích thước vùng nhớ tối đa? Giải quyết vấn đề vùng nhớ không liên tục? Giải quyết vấn đề giải phóng vùng nhớ khi không cần dùng đến? DÙNG CẤU TRÚC DỮ LIỆU ĐỘNG Biến tĩnh tên biến; Vd: int a; float y; char s[20]; Tồn tại trong phạm vi khai báo Được cấp phát vùng nhớ trong vùng dữ liệu Kích thước cố định Biến động *tên biến; Vd: int *a; float *y; Chứa địa chỉ của một đối tượng dữ liệu Được cấp phát hoặc giải phóng bộ nhớ tùy thuộc vào người lập trình Kích thước có thể thay đổi Biến động Cấp phát bộ nhớ: new int [kích thước] Giải phóng bộ nhớ: delete vùng nhớ Ví dụ: int *a; a=new int [10]; // Cấp phát //Các thao tác trên a delete a; // Giải phóng Giới thiệu cấu trúc “Danh sách liên kết” 1 7 2 6 3 10 8 5 9 4 Các phần tử kết dính với nhau bằng “sợi dây liên kết” 1 7 2 6 3 10 8
