Cấu trúc dữ liệu và giải thuật - Chương 3: Danh sách liên kết

CHƯƠNG 3DANH SÁCH LIÊN KẾTNỘI DUNG3.1. Đặt vấn đề 3.2. Khái niệm về biến con trỏ3.3. Danh sách liên kết3.4. Ứng dụng của DSLK3.8. Một số CTDL khác dựa trên danh sách3.9. Giới thiệu Stack, Queue3.1. Đặt vấn đềMảng 1 chiềuKích thước cố định (fixed size)Chèn 1 phần tử vào mảng rất khĩCác phần tử tuần tự theo chỉ số 0  n-1Truy cập ngẫu nhiên (random access)01234n-2n-1chènBiến TĩnhĐược khai báo tường minh, cĩ tên gọiTồn tại trong phạm vi khai báoĐược cấp phát trong stackKích thước khơng đổi => khơng tận dụng hiệu quả bộ nhớVí dụ : int	x,y;	char	c;	float	f[5];Khi biết chắc nhu cầu sử dụng đối tượng trước khi thực sự xử lý : dùng biến khơng độngVí Dụ Hạn Chế Của Biến TinhTổ chức danh sách lớp học Dùng mảng tĩnh :typedef	struct{ char ten[20]; int maso;}Hocvien;Hocvien	danhsach[50];Số lượng học viên lãng phíSố lượng học viện > 50 => thiếu chỗ !Biến Động Khơng được khai báo tường minh, khơng cĩ tên gọiXin khi cần, giải phĩng khi sử dụng xongĐược cấp phát trong heapLinh động về kích thước Vấn đề : biến động khơng cĩ tên gọi tường minh, làm sao thao tác ?3.2. Khái niệm về biến con trỏKiểu con trỏ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.Khai báo trong C :typedef	int	*intpointer;intpointer	p;Bản thân biến con trỏ là khơng độngDùng biến con trỏ để lưu giữ điạ chỉ của biến động => truy xuất biến động thơng qua biến con trỏCác thao tác trên kiểu con trỏ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ớ Hủy một biến động do p chỉ đến :Hàm free(p) huỷ vùng nhớ cấp phát bởi hàm malloc hoặc calloc do p trỏ tớiHàm delete p huỷ vùng nhớ cấp phát bởi hàm new do p trỏ tới0xFFSử dụng biến tinh, con trỏ và biến động5Biến khơng động xint	 x; x = 5 ;Biến con trỏ p int *p; Biến động có địa chỉ 0xFFp = new(int);50xFF*p = 53.3. Danh sách liên kếtKiểu danh sáchDanh 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ướcMỗi phần tử cĩ nhiều nhất 1 phần tử đứng sauLà kiểu dữ liệu quen thuộc trong thực tế :Danh sách học sinhDanh mục sách trong thư việnDanh bạ điện thoạiDanh sách các nhân viên trong cơng tyCác hình thức tổ chức danh sách 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 :Liên kết ngầm : 	MảngLiên kết tường minh : 	Danh sách liên kếtDanh sách liên kết ngầm(mảng)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 dsxi , 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:	address(i) = address(1) + (i-1)*sizeof(T) Ưu điểm : Truy xuất trực tiếp, nhanh chĩngNhược điểm:Sử dụng bộ nhớ kém hiệu quảKích thước cố địnhCác thao tác thêm vào, loại bỏ khơng hiệu quả x0  xixi+1Liên kết tuờng minh(Danh sánh liên kết)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áchx0x1x2x3Mỗi phần tử là một biến độngƯu điểm+ Sử dụng hiệu quả bộ nhớ	 + Linh động về số lượng phần tửCác loại danh sách liên kếtDanh 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áchABCD 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áchABCD 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áchCác loại danh sách liên kết (tt) 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áchDanh sách liên kết đơn vịngABCDABCD Danh sách liên kết đơi vịng 3.4. Ứng dụng của DSLK3.8. Một số CTDL khác dựa trên ds