Cấu trúc dữ liệu và giải thuật - Chương 3: Cấu trúc dữ liệu động

Nội dung text: Cấu trúc dữ liệu và giải thuật - Chương 3: Cấu trúc dữ liệu động

1. CẤCấuU TRÚ trúCc DỮ dữ L IỆUliệu V À1 GIẢI THUẬT 1 Click Click To Master Edit Title Style CẤU TRÚC DỮ LIỆU ĐỘNG LIỆU DỮ TRÚC CẤU NỘI DUNG NỘI 1
2. BiếnClick Tĩnh To Edit Master Title Style  Được khai báo tường minh, cĩ tên gọi  Tồn tại trong phạm vi khai báo  Được cấp phát trong stack  Kích thước khơng đổi => khơng tận dụng hiệu quả bộ nhớ 1 THUẬT  Ví dụ : int x,y; À GIẢI À GIẢI 1 char c; IỆU V float f[5]; c dữ liệu C DỮ L  Khi biết chắc nhu cầu sử dụng đối tượng trước khi trú U TRÚ thực sự xử lý : dùng biến khơng động Cấu CẤ 2
3. Ví DụClick Hạn ChếTo CủaEdit Biến Master Tinh Title Style  Tổ chức danh sách lớp học  Dùng mảng tĩnh : typedef struct { char ten[20]; 1 int maso; }Hocvien; THUẬT Hocvien danhsach[50]; À GIẢI À GIẢI 1 IỆU V  Số lượng học viên lãng phí c dữ liệu C DỮ L  Số lượng học viện > 50 => thiếu chỗ ! trú U TRÚ Cấu CẤ 3
4. BiếnClick Động To Edit Master Title Style  Khơng được khai báo tường minh, khơng cĩ tên gọi  Xin khi cần, giải phĩng khi sử dụng xong 1  Được cấp phát trong heap THUẬT  Linh động về kích thước À GIẢI À GIẢI 1  Vấn đề : biến động khơng cĩ tên gọi tường minh, IỆU V làm sao thao tác ? c dữ liệu C DỮ L trú U TRÚ Cấu CẤ 4
5. KiểuClick con trỏ To Edit Master Title Style  Kiểu con trỏ dùng lưu địa chỉ của một đối tượng dữ liệu khác.  Biến thuộc kiểu con trỏ Tp là biến mà giá trị của nĩ là địa chỉ cuả một vùng nhớ ứng với một biến kiểu T, hoặc là giá trị NULL. 1  Khai báo trong C : typedef int *intpointer; THUẬT intpointer p; À GIẢI À GIẢI 1 IỆU V  Bản thân biến con trỏ là khơng động c dữ liệu C DỮ L  Dùng biến con trỏ để lưu giữ điạ chỉ của biến động => trú truy xuất biến động thơng qua biến con trỏ U TRÚ Cấu CẤ 5
6. Các Clickthao tác To trên Edit kiểu Mastercon trỏ Title Style  Tạo ra một biến động và cho con trỏ ‘p’ chỉ đến nĩ: . void* malloc(size); . void* calloc(n,size); . new // hàm cấp phát bộ nhớ trong C++ 1  Hủy một biến động do p chỉ đến : THUẬT . Hàm free(p) huỷ vùng nhớ cấp phát bởi hàm malloc À GIẢI À GIẢI 1 hoặc calloc do p trỏ tới IỆU V . Hàm delete p huỷ vùng nhớ cấp phát bởi hàm new c dữ liệu C DỮ L do p trỏ tới trú U TRÚ Cấu CẤ 6
7. Sử dụngClick biến To tinh, Edit con Master trỏ và biến Title động Style int x; Biến khơng động x x = 5 ; 5 int *p; Biến con trỏ p 1 p = new(int); 0xFF THUẬT *p = 5 À GIẢI À GIẢI 0xFF 1 IỆU V 5 Biến động có địa chỉ 0xFF c dữ liệu C DỮ L trú U TRÚ Cấu CẤ 7
8. KiểuClick danh sách To Edit Master Title Style  Danh sách = { các phần tử cĩ cùng kiểu}  Danh sách là một kiểu dữ liệu tuyến tính : . Mỗi phần tử cĩ nhiều nhất 1 phần tử đứng trước . Mỗi phần tử cĩ nhiều nhất 1 phần tử đứng sau  Là kiểu dữ liệu quen thuộc trong thực tế : 1 . Danh sách học sinh THUẬT . À GIẢI À GIẢI Danh mục sách trong thư viện 1 IỆU V . Danh bạ điện thoại c dữ liệu C DỮ L . Danh sách các nhân viên trong cơng ty trú U TRÚ . Cấu CẤ 8
9. Các Clickhình thức To tổ Edit chức Master danh sách Title Style  CTDL cho mỗi phần tử ?  Thể hiện liên kết của các phần tử ?  Hai hình thức cơ bản : 1 . Liên kết ngầm : Mảng THUẬT . Liên kết tường minh : Danh sách liên kết À GIẢI À GIẢI 1 IỆU V c dữ liệu C DỮ L trú U TRÚ Cấu CẤ 9
10. DanhClick sách liênTo kếtEdit ngầm(mảng) Master Title Style  Mối liên hệ giữa các phần tử được thể hiện ngầm: . xi : phần tử thứ i trong danh sách . xi , xi+1 là kế cận trong danh sách  Phải lưu trữ liên tiếp các phần tử trong bộ nhớ . cơng thức xác định địa chỉ phần tử thứ i: 1 address(i) = address(1) + (i-1)*sizeof(T) THUẬT  Ưu điểm : Truy xuất trực tiếp, nhanh chĩng À GIẢI À GIẢI 1  Nhược điểm: x0 xi xi+1 IỆU V . Sử dụng bộ nhớ kém hiệu quả c dữ liệu C DỮ L . Kích thước cố định trú U TRÚ Cấu . Các thao tác thêm vào , loại bỏ khơng hiệu quả CẤ 10
11. LiênClick kết tuờng To minh(Danh Edit Master sánh liênTitle kết) Style  CTDL cho một phần tử . Thơng tin bản thân . Địa chỉ của phần tử kế trong danh sách x2 x0 1 x1 x3 THUẬT  Mỗi phần tử là một biến động À GIẢI À GIẢI 1 IỆU V  Ưu điểm c dữ liệu + Sử dụng hiệu quả bộ nhớ C DỮ L trú + Linh động về số lượng phần tử U TRÚ Cấu CẤ 11
12. Các Clickloại danh To sách Edit liên Master kết Title Style  Danh sách liên kết đơn: Mỗi phần tử liên kết với phần tử đứng sau nĩ trong danh sách A B C D 1  Danh sách liên kết kép: Mỗi phần tử liên kết với phần tử đứng trước và sau nĩ trong danh sách THUẬT A B C D À GIẢI À GIẢI 1 IỆU V  Danh sách liên Vịng: Phần tử cuối danh sách c dữ liệu C DỮ L liên với phần tử đầu danh sách trú U TRÚ Cấu CẤ 12
13. Các Clickloại danh To sách Edit liên Master kết (tt) Title Style  Danh sách liên Vịng: Phần tử cuối danh sách liên với phần tử đầu danh sách . Danh sách liên kết đơn vịng A B C D 1 . Danh sách liên kết đơi vịng THUẬT À GIẢI À GIẢI 1 A B C D IỆU V c dữ liệu C DỮ L trú U TRÚ Cấu CẤ 13