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

Chia sẻ: Lê Ngọc Hoàng | Ngày: | Loại File: PPT | Số trang:34

Thêm vào BST

Báo xấu

78
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

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. infor next A Một node trong danh sách
KHÁI NIỆM DANH SÁCH NỐ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ÁI NIỆM DANH SÁCH NỐI ĐƠN L Node đầu tiên A  Để 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 B trong danh sách  Phần tử cuối cùng của danh sách có C next=NULL L 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ử ta viết E L->infor Giá trị Để chỉ ra phần tử đứng sau ta viết Danh sách nối đơn NULL
L=2038 Ví 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
Ư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  Khai báo kiểu dữ liệu phần tử Khai báo kiểu con trỏ trỏ vào struct 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; };
KHAI BÁO CẤU TRÚC DỮ 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ÁC PHÉP TOÁN TRÊN DANH SÁ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ách
CÁC PHÉP TOÁN TRÊN DANH SÁCH  Khởi tạo danh sách rỗng Giá trị NULL void creat(TRO &L) { L L = NULL; } Danh sách nối đơn rỗng  Kiểm tra danh sách rỗng int empty(TRO L) { if (L==Null) Return 1; Else return 0; }
DUYỆT DANH SÁCH L Q 1. Nếu danh sách không A rỗng, cho con trỏ Q trỏ vào node đầu tiên: Q = L; Q B 2. 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 Q
DUYỆ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 A Giả 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 F
TÌ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 trỏ vào node đầu tiên: Q = L; 2. Nếu (Q != NULL) và (chưa trỏ vào node cần tìm) thì (có thể thực hiện yêu cầu) và chuyển Q xuống node ngay sau nó: Q=Q->next; 3. Lặp lại bước 2 4. Trả về con trỏ Q: return Q;
TÌM KIẾM MỘT NODE TRÊN DANH SÁCH L 3. Giả sử cần tìm node có Q A infor là K trong danh sách TRO Search(TRO L) { Q B Q = L; while (Q != NULL && (ĐKTK chưa thỏa)) Q C Q = Q->next; return Q; Q E } Hàm Search trả về NULL nếu Q F không tìm thấy, ngược lại trả về con trỏ trỏ vào node tìm Q được Không tìm thấy
BỔ SUNG VÀO ĐẦU DANH SÁCH P L Danh sách có phần tử đầu tiên được trỏ bởi con trỏ L A Giả sử dữ liệu của phần tử lưu L trong biến X A X B Khai báo con trỏ P: TRO P; Cấp phát bộ nhớ cho con trỏ C P: P = new Node; Đưa dữ liệu vào node mới: D P ->infor = X; next của node mới trỏ vào phần tử E đầu của danh sách: P->next = L; L trỏ vào node mới: L = P;
BỔ SUNG VÀO ĐẦU DANH SÁCH  Hàm thực hiện việc bổ sung void First_Add(TRO &L, Item X) { TRO P; P = new Node; P->infor = X; P->next = L; L = P; }
BỔ SUNG VÀO SAU MỘT NODE Danh sách có phần tử đầu tiên L được trỏ bởi con trỏ L A Q trỏ vào node mà node mới được bổ sung vào sau nó Dữ liệu lưu trong biến X B Q P Khai báo con trỏ P: TRO P; Cấp phát bộ nhớ cho con trỏ C P: P = new Node; E Đưa dữ liệu vào node mới: F P ->infor = X; next của node mới trỏ vào node đứng sau node trỏ bởi Q: P->next = Q- H >next; next của node trỏ bởi Q trỏ vào E X node mới: Q->next = P;
BỔ SUNG VÀO SAU MỘT NODE  Hàm thực hiện việc bổ sung void Insert(TRO &L, TRO Q, Item X) { TRO P; P = new Node; P->infor = X; P->next = Q->Next; Q->next = P; } Hàm Insert cũng thỏa mãn nếu bổ sung phần tử vào cuối danh sách, khi đó Q trỏ vào node cuối danh sách
XÓA NODE ĐẦU DANH SÁCH L Q 1. Khai báo con trỏ Q: TRO Q; A L 2. Cho Q trỏ vào node đầu B tiên: Q = L; 3. Chuyển L xuống node thứ C 2: L = L->next; 4. Xóa node trỏ bởi con trỏ Q: E delete Q; F