Bài giảng chương 3: Danh sách liên kết

Bài giảng Danh sách liên kết trình bày khái niệm về biến con trỏ, danh sách liên kết, ứng dụng của danh sách liên kết, giới thiệu Stack, queue. Bài giảng được trình bày khoa học, súc tích giúp các bạn sinh viên tiếp thu bài học nhanh.
Nội dung trích xuất từ tài liệu:
Bài giảng chương 3: Danh sách liên kết Click To EditƯƠNG 3 CH Master Title Style DANH SÁCH LIÊN KẾT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Cấu trúc dữ liệu 1 1 Click ToNỘI DUNG Title Style Edit Master  3.1. Đặt vấn đề  3.2. Khái niệm về biến con trỏ  3.3. Danh sách liên kết  3.4. Ứng dụng của DSLK  3.8. Một số CTDL khác dựa trên danh sách CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  3.9. Giới thiệu Stack, Queue Cấu trúc dữ liệu 1 2 Click To Edit Master ề 3.1. Đặt vấn đ Title Style  Mảng 1 chiều  Kí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-1  Truy cập ngẫu nhiên (random access) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT chèn Cấu trúc dữ liệu 1 0 1 2 3 4 n-2 n-1 3 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ớ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Ví dụ : int x,y; char c; Cấu trúc dữ liệu 1 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 động 4 Ví DClick Chế EditBiến Tinh ụ Hạn To Của Master Title Style  Tổ chức danh sách lớp học  Dùng mảng tĩnh : typedef struct { char ten[20]; int maso; CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT }Hocvien; Hocvien danhsach[50]; Cấu trúc dữ liệu 1  Số lượng học viên lãng phí  Số lượng học viện > 50 => thiếu chỗ ! 5 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  Được cấp phát trong heap  Linh động về kích thước CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT  Vấn đề : biến động không có tên gọi tường minh, Cấu trúc dữ liệu 1 làm sao thao tác ? 6 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Cấu trúc dữ liệu 1 3.2. Khái niệmMastern conStyle Click To Edit về biế Title trỏ 7 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.  Khai báo trong C : CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT typedef int *intpointer; intpointer p; Cấu trúc dữ liệu 1  Bản thân biến con trỏ là không động  Dù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ỏ 8 Các Click To Edit Master thao tác trên kiểu con 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ớ  Hủy một biến động do p chỉ đến : CẤU TRÚC ...