Cơ sở dữ liệu - Chương 4: Danh sách tuyến tính

Nội dung text: Cơ sở dữ liệu - Chương 4: Danh sách tuyến tính

1. CHƯƠNG 4 DANH SÁCH TUYẾN TÍNH
2. MỤC TIÊU ◼ Khái niệm danh sách tuyến tính ◼ Các phép toán với danh sách ◼ Lưu trữ kế tiếp của danh sách tuyến tính ◼ Danh sách móc nối đơn ◼ Danh sách nối đôi ◼ Danh sách móc nối vòng ◼ Ngăn xếp ◼ Hàng đợi
3. KHÁI NIỆM DSTT ◼ Danh sách là một tập các phần tử thuộc cùng một lớp đối tượng nào đó  Dãy số nguyên, danh sách sinh viên, ◼ Giả sử L là một danh sách có n phần tử L = { a1, a2, , an }  n gọi là độ dài của danh sách L  n>0 thì a1 là phần tử đầu tiên, an là phần tử cuối cùng  Với L, ta nói ai đứng trước ai+1 và đứng sau ai-1 (i=1 n).  Danh sách mà các phần tử có thứ tự “trước-sau” gọi là “DSTT”
4. CÁC PHÉP TOÁN TRÊN DSTT ◼ Khởi tạo danh sách rỗng (creat) ◼ Kiểm tra danh sách rỗng (empty) ◼ Kiểm tra danh sách đầy (full) ◼ Bổ sung một phần tử vào danh sách (add) ◼ Loại bỏ một phần tử khỏi danh sách (remove) ◼ Sắp xếp danh sách (sort) ◼ Tìm kiếm trên danh sách (search) ◼
5. LƯU TRỮ KẾ TIẾP CỦA DSTT ◼ DSTT được lưu trữ trong bộ nhớ bởi một mảng một chiều gọi là lưu trữ kế tiếp. ◼ Mỗi phần tử của mảng lưu trữ một phần tử của danh sách ◼ Ưu điểm  Truy cập nhanh và đồng đều đối với mọi phần tử  Các thao tác được thực hiện khá đơn giản ◼ Nhược điểm  Do kích thước mảng cố định khi khai báo nên có thể dẫn đến sự lãng phí hoặc thiếu bộ nhớ.
6. BIỂU DIỄN CẤU TRÚC DỮ LIỆU ◼ Giả sử các phần tử của danh sách có kiểu dữ liệu là “Item” ◼ Độ dài của danh sách là một số nguyên dương N ◼ Danh sách được biểu diễn bởi một cấu trúc gồm hai thành phần  Thành phần thứ nhất: biến “count” lưu chỉ số phần tử mảng, lưu trữ phần tử cuối cùng của danh sách.  Thành phần thứ hai: mảng một chiều “E” lưu các phần tử của danh sách L, E[i-1] lưu ai
7. LƯU TRỮ KẾ TIẾP CỦA DSTT ◼ Biểu diễn danh sách Danh sách cần lưu trữ: L = { a1, a2, , an } 0 1 n-1 Max-1 Mảng E a1 a2 an count = n-1
8. LƯU TRỮ KẾ TIẾP CỦA DSTT ◼ Cấu trúc dữ liệu được khai báo như sau #define Max N L.count = -1 -> ds L rỗng struct Item { L.count = Max-1 -> ds L đầy Các thành phần dữ liệu; }; struct List { int count; Item E[Max]; }; List L; //Khai báo ds L
9. LƯU TRỮ KẾ TIẾP CỦA DSTT ◼ Ví dụ #define Max 7 struct List { struct Sinhvien { int count; char hoten[30]; Sinhvien E[Max]; char gioitinh[4]; }; int tuoi; List L; //Khai báo ds L };
10. LƯU TRỮ KẾ TIẾP CỦA DSTT ◼ Ví dụ 0 1 2 3 4 5 6 L.E E S1 S2 S3 S4 S5 L.count count = 4 Danh sách L chứa 5 sinh viên
11. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP ◼ Khởi tạo danh sách rỗng ◼ Kiểm tra danh sách rỗng ◼ Kiểm tra danh sách đầy ◼ Phép loại bỏ một phần tử khỏi danh sách ◼ Bổ sung một phần tử vào danh sách ◼ Thống kê danh sách ◼ Tính toán trên danh sách ◼ Tìm kiếm trên danh sách ◼ Sắp xếp danh sách
12. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP ◼ Khởi tạo danh sách rỗng void creat(List &L) { L.count = -1; } Max = 7 0 1 2 3 4 5 6 Mảng E count = -1 Danh sách rỗng
13. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP ◼ Kiểm tra danh sách rỗng int empty(List L) { return (L.count == -1); } Hàm empty trả về giá trị 1 nếu danh sách rỗng, ngược lại trả về 0
14. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP ◼ Kiểm tra danh sách đầy int full(List L) { return (L.count == Max-1); } Max = 7 0 1 2 3 4 5 6 Mảng E 14 23 11 25 37 19 29 count = 6 Danh sách đầy
15. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP ◼ Thêm một phần tử vào cuối danh sách  Điều kiện: Danh sách chưa đầy Max = 7 0 1 2 3 4 5 6 Mảng E 14 23 11 25 37 29 count =count 4 = 5 Danh sách chưa đầy X 29
16. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP ◼ Thêm một phần tử vào cuối danh sách int Add(List &L, Item X) { if (full(L)) return 0; else{ L.count++; L.E[L.count] = X; return 1; } }
17. LƯU TRỮ KẾ TIẾP CỦA DSTT CHƯƠNG TRÌNH TẠO VÀ HiỂN THỊ DANH SÁCH SINH VIÊN
18. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP ◼ Phép loại bỏ phần tử thứ k khỏi danh sách L Loại bỏ phần tử tại vị trí thứ k=3 for (i=k;i<=L.count; i++) L.E[i-1] = L.E[i]; Max = 7 0 1 2 3 4 5 6 Mảng E 14 23 4211 1125 25 count = 3 count = 4 L.count = L.count-1;
19. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP ◼ Phép loại bỏ một phần tử khỏi danh sách L int Remove(int k, List &L) { if (k 0) { for (int i = k; i <= L.count; i++) L.E[i-1] = L.E[i] ; L.count = L.count - 1; return 1; } else return 0; }
20. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP ◼ Phép loại bỏ một phần tử khỏi danh sách L  Hàm Remove loại bỏ phần tử thứ k trong danh sách L  Phép loại bỏ thành công khi L không rỗng và k là một vị trí nằm trong ds L  Hàm trả về 1 nếu loại bỏ thành công, ngược lại trả về 0
21. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP ◼ Phép bổ sung một phần tử vào vị trí k trong danh sách L Bổ sung X=24 tại vị trí k=3 for (i=L.count;i>=k-1;i ) L.E[i+1]=L.E[i]; Max = 7 0 1 2 3 4 5 6 Mảng E 14 23 4224 1142 1125 25 count =count 4 = 5 X 24 L.E[k-1]=X; L.count++;
22. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP ◼ Phép bổ sung một phần tử vào vị trí k trong danh sách L int Insert(List &L, int k, Item X) { if (k 0 && !full(L)) { for (int i = L.count; i >=k-1; i ) L.E[i+1] = L.E[i] ; L.E[k-1] = X; L.count ++; return 1; } else return 0; }
23. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP ◼ Phép bổ sung một phần tử vào danh sách L  Hàm Insert bổ sung X vào vị trí k trong ds L  Phép bổ sung thành công khi L không đầy và k là một vị trí nằm trong ds L  Hàm trả về giá trị 1 nếu bổ sung thành công, ngược lại trả về 0.
24. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP ◼ Phép bổ sung một phần tử vào cuối danh sách L Bổ sung X=24 vào cuối danh sách L 1 2 3 4 5 6 Max = 7 Mảng E 14 23 42 11 25 X = 24 count = 5 1 2 3 4 5 6 Max = 7 Mảng E 14 23 42 11 25 count = 6
25. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP ◼ Phép bổ sung một phần tử vào cuối danh sách L Bổ sung X=24 vào cuối danh sách L 1 2 3 4 5 6 Max = 7 Mảng E 14 23 42 11 25 24 count = 6
26. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP ◼ Phép bổ sung một phần tử vào cuối danh sách L Procedure Insert_End (X:Item; Var L:List; Var OK:Boolean); Var i : integer; Begin OK := FALSE; if ( L.count < Max) then begin L.count := L.count + 1; L.E[L.count] := X; OK := TRUE; end; END;
27. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP ◼ Phép bổ sung một phần tử vào cuối danh sách L  Thủ tục Insert_End bổ sung X vào cuối ds L  Phép bổ sung thành công khi L không đầy  Biến OK cho biết phép toán có thành công hay không ◼ OK = True -> Thành công ◼ OK = False -> Không thành công
28. BÀI TẬP ◼ Cho L={A1, A2, A3, A4, A5} ◼ Yêu cầu:  Vẽ hình mô tả trạng thái của danh sách qua các bước trong quá trình tạo mới danh sách từ một danh sách rỗng.  Vẽ hình mô tả trạng thái của danh sách trong thao tác loại bỏ phần tử đầu tiên (A1) và phần tử thứ 3 (A3) trong danh sách (cần chú thích rõ ràng)  Vẽ hình mô tả quá trình bổ sung phần tử A6 vào đầu danh sách, vào sau phần tử thứ 3 (A3) trong danh sách.  Giả sử danh sách lưu trữ thông tin về các sinh viên, mỗi sinh viên gồm: Mã sinh viên, họ và tên, năm sinh, điểm tổng kết. Hãy cài đặt chương trình thực hiện các yêu cầu sau:
29. CÁC PHÉP TOÁN TRÊN DS KẾ TIẾP ◼ Khai báo cấu trúc dữ liệu của danh sách ◼ Nhập mới 5 phần tử cho danh sách ◼ Hiển thị danh sách lên màn hình ◼ Xóa phần tử đầu tiên trong danh sách, hiển thị lại danh sách ◼ Xóa phần tử thứ 4 trong danh sách, hiển thị lại danh sách ◼ Thêm một phần tử vào đầu danh sách, hiển thị lại danh sách ◼ Thêm một phần tử vào sau phần tử thứ 3 trong danh sách, hiển thị danh sách ◼ Tìm sinh viên có tên “Doanh” trong danh sách, hiển thị kết quả tìm kiếm. ◼ Sắp xếp danh sách theo chiều giảm dần của điểm tổng kết, hiển thị lại DS.