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

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

Thêm vào BST

Báo xấu

66
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ủ đề:

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

Lưu

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

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
* 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ả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 ………………........ // 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 4
1 7 2 6 3 10 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
Node List 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