Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - GV. Nguyễn Minh Thành

Chương 3 Con Trỏ và Cấu Trúc Dữ Liệu Động nằm trong bài giảng Cấu trúc dữ liệu và giải thuật nhằm trình bày về so sánh dữ liệu tĩnh và dữ liệu động, con trỏ, con trỏ với dữ liệu cấu trúc, cấp phát bộ nhớ, tổng quan về danh sách liên kết, các loại DSLK, so sánh mảng và DSLK.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - GV. Nguyễn Minh ThànhChươ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.vnNội DungI. So sánh dữ liệu tĩnh và dữ liệu độngII. 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ếtIV. Các loại DSLKV. So sánh mảng và DSLK2I. 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ử 6 15 10 9 5 7 3 2 1 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í 53I. So Sánh Dữ Liệu Tĩnh và Động Xét kiểu dữ liệu tĩnh 6 ? Giả sử cần thêm tiếp 1 phần tử 15 10 9 5 7 3 2 1 1 2 3 4 5 6 7 8 94 Bổ sung thêmI. 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);5I. 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 ? 15 10 9 5 7 3 2 1 1 2 3 4 5 6 7 86I. 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 ? 15 10 9 5 7 3 2 1 1 2 3 4 5 6 7 87I. 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);8I. 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 động9II. 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 động10II. 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ố định11II. 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 đổi12II. 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óng13II. Con Trỏ Xét ví dụ sau : int foo; int *x; foo = 123; x = &foo;14II. 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;15II. 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ỏ16II. Con Trỏ Toán tử ‘&’ : dùng để lấy địa chỉ của một biến.17II. Con Trỏ Một con ...