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.
Nội dung trích xuất từ tài liệu:
CÂU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - CHƯƠNG 3 (tiếp) DANH SÁCH NỐI ĐƠNDANH SÁCH NỐI ĐƠN CHƯƠNG 3 (tiếp)KHÁINIỆMDANHSÁCHNỐIĐƠNNguyêntắctạothànhdanhsách  Danhsáchđượctạothànhtừcácphầntửgọilànút (Node)  Cácnodecóthểnằmbấtkỳđâutrongbộnhớ  Mỗinodelàmộtcấutrúcgồm2thànhphần inforchứathôngtincủa1phầntửcủadanhsáchL nextlàmộtcontrỏ,nótrỏvàonodeđứngsau. infor next A Một node trong danh sáchKHÁINIỆMDANHSÁCHNỐIĐƠNVí dụ next infor Tran Lan Anh 32 1089 7.8 Một node trong danh sách sinh viên 1089 là địa chỉ vùng nhớ của node đứng sau KHÁINIỆMDANHSÁCHNỐIĐƠN L Node đầu tiên A Đểtruynhậpvàocácnodetrongdanh sáchtaphảiđitừnodeđầutiên Cần một con trỏ, trỏ vào node đầu B trongdanhsách Phần tử cuối cùng của danh sách có C next=NULLL trỏ vào node đầu tiên của danh sách khi DđóĐể truy xuất vào thông tin của phần tử taviết E L->infor Giá trịĐể chỉ ra phần tử đứng sau ta viết Danh sách nối đơn NULL L=2038Ví dụ 2038 Vu Lan Anh 1089 32 7.8 1089 Ha Anh Lan 1547 23 8.7 1547 Ta Bach Lan 3452 23 8.7 3452 Vu Hoa Lan 1032 23 8.7 1032 Bui Nhu Lan 23 NULL 8.7ƯUVÀNHƯỢCĐIỂMCỦADSNĐ Ư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 Khai báo kiểu dữ liệu phần tử Khai báo kiểu con trỏ trỏ vàostruct Item { Node Node * TRO; typedef Các thành phần dữliệu; KB con trỏ trỏ vào Node đầu tiên};Khai báo kiểu dữ liệu Node TRO L;struct Node { Item infor; L=NULL -> ds L rỗng Node *next;}; KHAIBÁOCẤUTRÚCDỮLIỆU Khai báo Cấu trúc dữ liệu sinh viên Khai báo kiểu dữ liệu SV Khai báo kiểu dữ liệu Node struct SINHVIEN { struct Node { char hoten[30]; SINHVIEN infor; int tuoi; Node *next; float diemtb; }; };Khai báo kiểu con trỏ của KB con trỏ trỏ vào Node đầu tiên Node Node * TRO; typedef TRO L;CÁCPHÉPTOÁNTRÊNDANHSÁCH  Khởi tạo danh sách rỗng  Kiểm tra danh sách rỗng  Duyệt danh sách  Tìm kiếm một node trên danh sách  Bổ sung node mới vào đầu danh sách  Bổ sung node mới vào sau một node  Xóa node đầu danh sách  Xóa node đứng sau một node trong danh sách  Sắp xếp danh sáchCÁCPHÉPTOÁNTRÊNDANHSÁCHKhởitạodanhsáchrỗng Giá trị NULL void creat(TRO &L) { L L = NULL; } Danh sách nối đơn rỗngKiểmtradanhsáchrỗng int empty(TRO L) { if (L==Null) Return 1; Else return 0; } DUYỆT DANH SÁCH L Q1. Nếu danh sách không A rỗng, cho con trỏ Q trỏ vào node đầu tiên: Q = L; Q B2. Nếu Q != NULL thì (thực hiện yêu cầu) và chuyển Q C Q xuống node ngay sau nó: Q E Q=Q->next;3. Lặp lại bước 2 Q F Q = NULL QDUYỆT DANH SÁCH Hàm duyệt danh sách như sau void travel(TRO L) { TRO Q; if (!empty(L)) { Q = L; while (Q != NULL) { //Statement Q = Q->next; } } }TÌM KIẾM MỘT NODE TRÊN DANH SÁCH L Q AGiả sử cần tìm node cóinfor là C trong danh sách Q B Tìm thấy và Q C con trỏ Q trỏ vào node tìm E được FTÌM KIẾM MỘT NODE TRÊN DANH SÁCH 1. Nếu danh sách không rỗng, cho con trỏ Q t ...