intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Cxzvscv Cxzvscv | Ngày: | Loại File: PDF | Số trang:36

Thêm vào BST
Báo xấu
91
lượt xem 6
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

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

Lưu

Nội dung Text: 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

  1. 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
  2. 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
  3. 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ử 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í 5 3
  4. I. 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 9 4 Bổ sung thêm
  5. 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
  6. 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 ? 15 10 9 5 7 3 2 1 1 2 3 4 5 6 7 8 6
  7. 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 ? 15 10 9 5 7 3 2 1 1 2 3 4 5 6 7 8 7
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. II. Con Trỏ  Xét ví dụ sau : int foo; int *x; foo = 123; x = &foo; 14
  15. 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
  16. 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
  17. II. Con Trỏ  Toán tử ‘&’ : dùng để lấy địa chỉ của một biến. 17
  18. 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
  19. 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
  20. II.1 Con Trỏ Với Dữ Liệu Cấu Trúc 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2