tailieunhanh - CÂU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - CHƯƠNG 3 (tiếp) DANH SÁCH NỐI ĐƠN

Nguyên tắc tạo thành danh sách Danh sách được tạo thành từ các phần tử gọi là nút (Node) Các node có thể nằm bất kỳ đâu trong bộ nhớ Mỗi node là một cấu trúc gồm 2 thành phần infor chứa thông tin của 1 phần tử của danh sách L next là một con trỏ, nó trỏ vào node đứng sau. | DANH SÁCH NỐI ĐƠN CHƯƠNG 3 (tiếp) KHÁI NIỆM DANH SÁCH NỐI ĐƠN Nguyên tắc tạo thành danh sách Danh sách được tạo thành từ các phần tử gọi là nút (Node) Các node có thể nằm bất kỳ đâu trong bộ nhớ Mỗi node là một cấu trúc gồm 2 thành phần infor chứa thông tin của 1 phần tử của danh sách L next là một con trỏ, nó trỏ vào node đứng sau. A infor next Một node trong danh sách KHÁI NIỆM DANH SÁCH NỐI ĐƠN Ví dụ Tran Lan Anh 32 1089 infor next Một node trong danh sách sinh viên 1089 là địa chỉ vùng nhớ của node đứng sau KHÁI NIỆM DANH SÁCH NỐI ĐƠN Để truy nhập vào các node trong danh sách ta phải đi từ node đầu tiên Cần một con trỏ, trỏ vào node đầu trong danh sách Phần tử cuối cùng của danh sách có next=NULL A B C D E Giá trị NULL Danh sách nối đơn Node đầu tiên L trỏ vào node đầu tiên của danh sách khi đó Để truy xuất vào thông tin của phần tử ta viết L->infor Để chỉ ra phần tử đứng sau ta viết L->next L Vu Lan Anh 32 2038 Ha Anh Lan 23 1089 Ta Bach Lan 23 1547 Vu Hoa Lan 23 3452 L=2038 Bui Nhu Lan 23 NULL 1032 1089 1547 3452 1032 Ví dụ ƯU VÀ NHƯỢC ĐIỂM CỦA DSNĐ Ưu điểm: Tiết kiệm bộ nhớ Các thao tác thêm và xóa thực hiện nhanh vì không phải dịch chuyển các phần tử Nhược điểm: Việc truy xuất vào các phần tử chậm vì luôn phải xuất phát từ phần tử đầu tiên Chỉ duyệt được danh sách theo một chiều nhất định, từ trên xuống. Các thao tác khá phức tạp, khó hiểu với người mới LT KHAI BÁO CẤU TRÚC DỮ LIỆU Khai báo Cấu trúc dữ liệu MẪU L=NULL -> ds L rỗng struct Item { Các thành phần dữ liệu; }; Khai báo kiểu dữ liệu phần tử struct Node { Item infor; Node *next; }; Khai báo kiểu dữ liệu Node KB con trỏ trỏ vào Node đầu tiên TRO L; typedef Node * TRO; Khai báo kiểu con trỏ trỏ vào Node KHAI BÁO CẤU TRÚC DỮ LIỆU Khai báo Cấu trúc dữ liệu sinh viên struct SINHVIEN { char hoten[30]; int tuoi; float diemtb; }; Khai báo kiểu dữ liệu SV struct Node { SINHVIEN infor; Node *next; }; Khai báo kiểu dữ liệu Node KB con trỏ trỏ vào Node đầu tiên TRO L; typedef Node * . | DANH SÁCH NỐI ĐƠN CHƯƠNG 3 (tiếp) KHÁI NIỆM DANH SÁCH NỐI ĐƠN Nguyên tắc tạo thành danh sách Danh sách được tạo thành từ các phần tử gọi là nút (Node) Các node có thể nằm bất kỳ đâu trong bộ nhớ Mỗi node là một cấu trúc gồm 2 thành phần infor chứa thông tin của 1 phần tử của danh sách L next là một con trỏ, nó trỏ vào node đứng sau. A infor next Một node trong danh sách KHÁI NIỆM DANH SÁCH NỐI ĐƠN Ví dụ Tran Lan Anh 32 1089 infor next Một node trong danh sách sinh viên 1089 là địa chỉ vùng nhớ của node đứng sau KHÁI NIỆM DANH SÁCH NỐI ĐƠN Để truy nhập vào các node trong danh sách ta phải đi từ node đầu tiên Cần một con trỏ, trỏ vào node đầu trong danh sách Phần tử cuối cùng của danh sách có next=NULL A B C D E Giá trị NULL Danh sách nối đơn Node đầu tiên L trỏ vào node đầu tiên của danh sách khi đó Để truy xuất vào thông tin của phần tử ta viết L->infor Để chỉ ra phần tử đứng sau ta viết L->next L Vu Lan Anh 32 2038 Ha Anh Lan 23 1089 Ta Bach Lan 23 1547 Vu Hoa Lan 23