Cơ sở dữ liệu - Chương 3: Danh sách nối đơn

Nội dung text: Cơ sở dữ liệu - Chương 3: Danh sách nối đơn

1. DANH SÁCH NỐI ĐƠN CHƯƠNG 3 (tiếp)
2. 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
3. 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
4. KHÁI NIỆM DANH SÁCH NỐI ĐƠN Node đầu tiên L ⚫ Để truy nhập vào các node trong A 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ó next=NULL C 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 D L->infor Để chỉ ra phần tử đứng sau ta viết E L->next Giá trị NULL Danh sách nối đơn
5. Ví dụ L=2038 2038 Vu Lan Anh 32 1089 7.8 1089 Ha Anh Lan 23 1547 8.7 1547 Ta Bach Lan 23 3452 8.7 3452 Vu Hoa Lan 23 1032 8.7 1032 Bui Nhu Lan 23 NULL 8.7
6. Ư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
7. 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 Node struct Item { typedef Node * TRO; 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; };
8. 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 Node KB con trỏ trỏ vào Node đầu tiên typedef Node * TRO; TRO L;
9. 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
10. 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 = NULL; L } 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; }
11. DUYỆT DANH SÁCH L 1. Nếu danh sách không Q 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 xuống node ngay sau nó: Q C Q=Q->next; Q E 3. Lặp lại bước 2 Q F Q = NULL Q
12. 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; } } }
13. TÌM KIẾM MỘT NODE TRÊN DANH SÁCH L Giả sử cần tìm node có Q A infor là C trong danh sách Q B Tìm thấy và con Q C trỏ Q trỏ vào node tìm được E F
14. 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;
15. TÌM KIẾM MỘT NODE TRÊN DANH SÁCH 3. Giả sử cần tìm node có L infor là K trong danh sách Q A TRO Search(TRO L) { Q = L; Q B while (Q != NULL && (ĐKTK chưa thỏa)) Q = Q->next; Q C 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 được Q Không tìm thấy
16. BỔ SUNG VÀO ĐẦU DANH SÁCH Danh sách có phần tử đầu tiên P L được trỏ bởi con trỏ L Giả sử dữ liệu của phần tử lưu A trong biến X L X A B Khai báo con trỏ P: TRO P; Cấp phát bộ nhớ cho con trỏ P: C 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ử đầu của danh sách: P->next = L; E L trỏ vào node mới: L = P;
17. 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; }
18. BỔ SUNG VÀO SAU MỘT NODE Danh sách có phần tử đầu tiên được trỏ bởi con trỏ L L Q trỏ vào node mà node mới A được bổ sung vào sau nó Dữ liệu lưu trong biến X B Khai báo con trỏ P: TRO P; Q P Cấp phát bộ nhớ cho con trỏ P: C P = new Node; Đưa dữ liệu vào node mới: E P ->infor = X; F next của node mới trỏ vào node đứng sau node trỏ bởi Q: P->next = Q->next; H next của node trỏ bởi Q trỏ vào X E node mới: Q->next = P;
19. 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
20. XÓA NODE ĐẦU DANH SÁCH Q L 1. Khai báo con trỏ Q: TRO Q; A L 2. Cho Q trỏ vào node đầu tiên: Q = L; B 3. Chuyển L xuống node thứ 2: L = L->next; C 4. Xóa node trỏ bởi con trỏ Q: E delete Q; F
21. XÓA NODE ĐẦU DANH SÁCH ⚫ Hàm xóa node đầu danh sách void First_Delete(TRO &L) { TRO Q; Q = L; L = L->next; delete Q; }
22. XÓA NODE SAU NODE TRỎ BỞI M L 1. Khai báo con trỏ Q: TRO Q; A 2. Cho Q trỏ vào node ở sau node trỏ bởi M: Q = M->next; B M 3. next của M trỏ vào node sau node trỏ bởi Q: C M->next = Q->next; Q E 4. Xóa node trỏ bởi con trỏ Q: delete Q; F
23. XÓA NODE SAU NODE TRỎ BỞI M ⚫ Hàm xóa node sau con trỏ M void M_Delete(TRO &L, TRO M) { TRO Q; Q = M->next; M->next = Q->next; delete Q; }
24. TẠO MỘT DANH SÁCH MỚI Xuất phát từ một danh sách rỗng: creat(L); 1. Khai báo 2 con trỏ P, Q và biến X: TRO P, Q; Item X; P L 2. Nhập dữ liệu cho biến X; X 3. Cấp phát bộ nhớ cho con trỏ P A A và đưa dữ liệu vào chỗ nhớ đó, BC Q đồng thời P->next=NULL; 4. Nếu L=NULL thì L trỏ vào P B Ngược lại next của node trỏ P bởi Q trỏ vào node mới C 5. Cho Q trỏ vào node mới 6. Nếu thỏa mãn điều kiện nhập tiếp thì lặp lại bước 2, ngược lại kết thúc
25. TẠO MỘT DANH SÁCH MỚI ⚫ Hàm tạo mới danh sách void input_List(TRO &L) { TRO P, Q; Item X; char tieptuc; //Bước 1 L = NULL; do{ nhap(X); //Bước 2 P = new Node; P->infor = X; P->next = NULL; //Bước 3 if (L==NULL) L = P; //Bước 4 else Q->next = P; Q = P; //Bước 5 cout >tieptuc; }while (toupper(tieptuc) == ‘C’); //Bước 6 }
26. Bài tập ⚫ Chương trình quản lý sinh viên (mã SV, họ tên, năm sinh, điểm tổng kết) bằng danh sách nối đơn với các chức năng Tạo mới danh sách Xác định chiều dài danh sách Hiển thị danh sách Tìm kiếm sinh viên theo mã và hiển thị thông tin của sinh viên nếu tìm thấy Xóa sinh viên khi biết mã Thêm một sinh viên mới vào danh sách theo vị trí Sắp xếp danh sách theo chiều tăng dần
27. DANH SÁCH NỐI VÒNG L Là một danh sách nối đơn Có next của node cuối cùng trỏ A vào node đầu tiên DS nối vòng có ưu điểm là xuất B phát từ một vị trí bất kỳ có thể duyệt hết danh sách C Về cấu trúc dữ liệu và các phép toán tương tự như DS nối đơn D Sinh viên tự nghiên cứu trong tài liệu E
28. DANH SÁCH MÓC NỐI HAI CHIỀU Là một danh sách móc nối mà mỗi node có ba thành phần prev infor B next Thành phần infor chứa dữ liệu Con trỏ next trỏ vào node đứng sau Con trỏ prev trỏ vào node đứng trước
29. DANH SÁCH MÓC NỐI HAI CHIỀU L1 Hình ảnh danh sách móc nối hai chiều A Để quản lý danh sách trong bộ nhớ người ta dùng hai con trỏ B Con trỏ L1 trỏ vào node đầu của danh sách C Con trỏ L2 trỏ vào node cuối của danh D sách L2
30. 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 Node struct Item { typedef Node * TRO; 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 TROvà node L1, L2cuối; struct Node { Item infor; L1/L2=NULL -> ds L rỗng Node *next; Node *prev; };
31. 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 trước/sau một node ⚫ Xóa node đầu danh sách ⚫ Xóa node đứng trước/sau một node trong danh sách ⚫ Sắp xếp danh sách
32. Bổ sung node mới vào đầu danh sách Trường hợp danh sách rỗng P L1 A L2 X A
33. Bổ sung node mới vào đầu danh sách P L1 A X L1 A B C D E L2
34. Bổ sung node mới vào đầu danh sách ⚫ Hàm bổ sung node mới vào đầu danh sách void first_Add(TRO &L1, TRO &L1, Item X) { TRO P; //Khai báo con trỏ P P = new Node; P->infor = X; P->prev = NULL; P->next = L1; if (L2==NULL) //Trường hợp danh sách rỗng L2 = P; else L1->prev = P; L1 = P; }