Chương 3(1) : Con trỏ & cấu trúc dữ liệu động

Giảng viên : Nguyễn Minh Thành Email : thanhnm.itc@itc.edu.vn Chương 3 (1) : Con Trỏ & Cấu Trúc Dữ Liệu Động Nội Dung I. So sánh dữ liệu tĩnh và dữ liệu động II. Con trỏ 1. Con trỏ với dữ liệu cấu trúc 2. Cấp phát bộ nhớ III. Tổng quan về danh sách liên kết IV. Các loại DSLK V. So sánh mảng và DSLK 2 I. So Sánh Dữ Liệu Tĩnh và Động  Xét kiểu dữ liệu tĩnh  Cho một mảng có N=8 phần tử 3 1 2 3 4 5 6 7 8 10 5 7 3 9 2 15 1 *Làm sao để chèn thêm số 6 vào mảng tại vị trí 5 6 I. So Sánh Dữ Liệu Tĩnh và Động  Xét kiểu dữ liệu tĩnh 4 1 2 3 4 5 6 7 8 9 10 5 7 3 9 2 15 1 6 Bổ sung thêm Giả sử cần thêm tiếp 1 phần tử? I. So Sánh Dữ Liệu Tĩnh và Động  Xét kiểu dữ liệu tĩnh  Bài tập : 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); 5 I. So Sánh Dữ Liệu Tĩnh và Động  Xét kiểu dữ liệu tĩnh  Xoá phần tử 9 ra khỏi mảng ? 6 1 2 3 4 5 6 7 8 10 5 7 3 9 2 15 1 I. So Sánh Dữ Liệu Tĩnh và Động  Xét kiểu dữ liệu tĩnh  Xoá phần tử 9 ra khỏi mảng ? 7 1 2 3 4 5 6 7 8 10 5 7 3 9 2 15 1 I. So Sánh Dữ Liệu Tĩnh và Động  Xét kiểu dữ liệu tĩnh  Bài tập : 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); 8 I. So Sánh Dữ Liệu Tĩnh và Động  Xét kiểu dữ liệu tĩnh  Ta thấy, các thao tác chèn và xoá dữ liệu trên mảng 1 chiều đều phải duyệt qua tất cả các phần tử => Độ phức tạp O(n)  Các vấ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? Kiểu dữ liệu động 9 II. Con Trỏ  Bộ nhớ gồm 1 tập hợp các ô nhớ được đánh địa chỉ. Bộ nhớ được chia làm 2 phần : stack và heap  Stack : để cấp phát bộ nhớ cho các biến tĩnh & động  Heap : để cấp phát bộ nhớ cho các động  Con trỏ là một biến dùng để lưu địa chỉ của một vùng nhớ được cập phát trên vùng heap.  Con trỏ có thể được cấp phát vùng nhớ và thu hồi vùng nhớ.  Con trỏ là nền tảng cho cấu trúc dữ liệu động 10 II. Con Trỏ  Khai báo dữ liệu tĩnh  tên biến; Vd: int a; float y;  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 11 II. Con Trỏ  Khai báo dữ liệu động (con trỏ)  *tên_biến_động; 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 12 II. Con Trỏ  Khai báo dữ liệu động (con trỏ)  Cấp phát bộ nhớ: new int [kích thước]  Giải phóng bộ nhớ: delete biến_động  Ví dụ: int *a; a=new int; // Cấp phát 1 phan tử a=new int [10]; // Cấp phát 1 mảng //Các thao tác trên a ………………........ delete a; // Giải phóng 13 II. Con Trỏ  Xét ví dụ sau : int foo; int *x; foo = 123; x = &foo; 14 II. Con Trỏ  Xét câu lệnh sau : int *x;  x là một con trỏ trỏ đến một số nguyên  Ta có thể sử dụng số nguyên của x trỏ đến bằng 1 trong 2 cách sau :  Y = *x + 17;  *x = *x + 1; 15 II. Con Trỏ  Lưu ý :  Toán tử ‘*’ có hai chức năng :  Khai báo con trỏ  Truy xuất dữ liệu tại địa chỉ lưu dữ con trỏ 16 II. Con Trỏ  Toán tử ‘&’ : dùng để lấy địa chỉ của một biến. 17 II. Con Trỏ  Một con trỏ phải có giá trị trước khi tham chiếu ngược để truy xuất dữ liệu 18 II. Con Trỏ  Con trỏ NULL :  Không trỏ đến một vị trí nào  Tham chiếu ngược con trỏ NULL sẽ gây ra lỗi thực thi chương trình (run-time error)  Kiểm tra con trỏ NULL trước khi tham chiếu. 19 II.1 Con Trỏ Với Dữ Liệu Cấu Trúc 20 II.2 Cấp Phát Bộ Nhớ Cho Con Trỏ 21 II.2 Cấp Phát Bộ Nhớ Cho Con Trỏ 22 II.2 Cấp Phát Bộ Nhớ Cho Con Trỏ  Bài tập : trình bày thứ tự cấp phát và cho biết giá trị của các biến int x = 5; int *a, *b =&x, *c; a = new int; *a = 5; *b = *a + 2; x++; c = new int; *c = x+2; 23 III. Tổng Quan về Danh Sách Liên Kết  Danh sách liên kết là tập hợp các phần tử kết dính với nhau bằng một “sợi dây liên kết”  Sự liên tiếp của các phần tử không phải liên tiếp về vị trí vật lý. 24 III. Tổng Quan về Danh Sách Liên Kết  Để đơn giản trong việc biểu diễn, danh sách liên kết được minh hoạ như sau 25 III. Tổng Quan về Danh Sách Liên Kết  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 26 III. Tổng Quan về Danh Sách Liên Kết 27  Hình minh hoạ Node pHead pTail List III.1 Cấu Tạo Danh Sách Liên Kết 28  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 III.1 Cấu Tạo Danh Sách Liên Kết 29  Cấu tạo một Node  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 III.3 Một Số Thao Tác Trên DSLK 30  Thêm một Node  Kết nối lại sợi dây liên kết theo trình tự pHead pTail List III.3 Một Số Thao Tác Trên DSLK 31  Xoá một Node Cần xóa pHead pTail List IV. Các loại DSLK 32  Danh sách liên kết đơn : Các phần tử kết nối với nhau theo một hướng “chiều đi tới” IV. Các loại DSLK 33  Danh sách liên kết đôi : Các phần tử kết nối với nhau theo hai hướng “chiều đi tới và và đi lui” IV. Các loại DSLK 34  Danh sách liên kết vòng : Các phần tử kết nối với nhau theo hướng “chiều đi tới” và phần tử cuối cùng có “đường đi vòng trở lại tới” phần tử đầu danh sách V. So Sánh Mảng và DSLK 35 Mảng Danh sách liên kết Kích thước cố định Số phần tử thay đổi tùy ý Các phần tử lưu trữ tuần tự (địa chỉ tăng dần) trong bộ nhớ Các phần tử liên kết với nhau bằng con trỏ Phải dịch chuyển các phần tử khi Thêm/Xóa Chỉ cần thay đổi con trỏ liên kết khi Thêm/Xóa Truy xuất ngẫu nhiên Truy xuất tuần tự Hỏi Đáp 36