Chapter 3: Cấu trúc dữ liệu động

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ềuCài đặt được các giải thuật bằng ngôn ngữ C/C++
Nội dung trích xuất từ tài liệu:
Chapter 3: Cấu trúc dữ liệu độngChươ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* Làm sao để chèn thêm số 6 vào mảng tại vị trí 5 ? Giả sử cần thêm tiếp 1 phần tử 1 2 3 4 5 6 7 8 9 Bổ sung thêm*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ảngsố 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, theomẫ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óaphầ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ácphần tử trong mảng không trùng nhau), theomẫ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 ………………........ // Giải phóng delete a;*Giới thiệu cấu trúc “Danh sách liênầkết” ết Các ph n tử k 1 dính với nhau bằng “sợi dây liên 7 kết” 2 6 3 10 8 5 9 41726 310 8 Để đơn giản 5 hơn trong việc 9 minh họa 4*Một dãy tuần tự các nút (Node)*Giữa hai nút có con trỏ liên kết*Các nút không cần phải lưu trữ liên tiếp nhau trong bộ nhớ*Có thể mở rộng tuỳ ý (chỉ giới hạn bởi dung lượng bộ nhớ)*Thao tác Chèn/Xóa không cần phải dịch chuyển phần tử mà chỉ cần thay đổi mối liên kết*Quản lý phần tử đầu tiên bằng con trỏ pHead*Có thể truy xuất đến các phần tử khác thông qua con trỏ liên kết NodeList pHead pTail*Quản lý toàn bộ danh sách liên kết thông qua con trỏ đầu pHead*pHead không phải là 1 nút, nó chỉ là “con trỏ chỉ đến nút” mà thôi*Ta cũng có thể quản lý danh sách bằng cách sử dụng thêm con trỏ cuối (pTail)*pTail không phải là 1 nút, nó chỉ là “con trỏ chỉ đến nút” mà thôi*Tạo lập bằng cách cấp phát bộ nhớ động*Mỗi nút có 2 thông tin: *Dữ liệu (data) *Con trỏ liên kết đến phần tử kế tiếp trong danh sách (Next pointer link)*Nếu không trỏ đến phần tử nào thì con trỏ Next = NULL*“Kết nối” lại sợi dây liên kết theo trình tựList pHead pTail