›
›

Bài giảng Cấu trúc Dữ liệu và giải thuật - Chương 3: Các cấu trúc dữ liệu cơ bản - Nguyễn Thị Xuân Hương

pdf 84 trang huongle 1601
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc Dữ liệu và giải thuật - Chương 3: Các cấu trúc dữ liệu cơ bản - Nguyễn Thị Xuân Hương", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_3_cac_cau_tr.pdf

Nội dung text: Bài giảng Cấu trúc Dữ liệu và giải thuật - Chương 3: Các cấu trúc dữ liệu cơ bản - Nguyễn Thị Xuân Hương

  1. TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG KHOA CÔNG NGHỆ THÔNG TIN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Ths. Nguyễn Thị Xuân Hương 1
  2. Chƣơng 3: CÁC CẤU TRÚC DỮ LIỆU CƠ BẢN 3.1. Khái niệm về kiểu dữ liệu: 3.2. Kiểu dữ liệu nguyên thủy 3. 3. Kiểu đoạn con 3.4. Dữ liệu kiểu mảng 3.5. Kiểu cấu trúc 3.6. Dữ liệu kiểu tập hợp 3.7. Dữ liệu kiểu tệp Chú ý: Các dữ liệu có cấu trúc là các cấu trúc lƣu trữ (phụ thuộc ngôn ngữ lập trình) 2
  3. Chƣơng 3: CÁC CẤU TRÚC DỮ LIỆU CƠ BẢN •Thảo luận: Khái niệm về các cấu trúc dữ liệu cơ bản trên? Biểu diễn các CTDL đó như thế nào trên máy tính? Các phép toán cơ bản trên CTDL đó thực hiện như thế nào? 3
  4. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.1. Khái niệm 4.1.1. Các định nghĩa. - Định nghĩa: Danh sách (DS) là một tập hữu hạn được sắp thứ tự các phần tử cùng một kiểu dữ liệu. Mỗi phần tử trên danh sách xác định một phần tử đứng liền trước nó và một phần tử đứng liền sau nó. Có hai phần tử đặc biệt: phần tử đầu danh sách: không có phần tử liền trước phần tử cuối danh sách: không có phần tử liền sau 4
  5. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.1. Khái niệm 4.1.1. Các định nghĩa. Ví dụ: DS = ( a1,a2, , an) Thảo luận : - Danh sách trên có bao nhiêu phần tử, các phần tử trong danh sách có đặc điểm gì ? - Danh sách con: gồm các phần tử liên tiếp từ ai đến aj của DS. VD: Danh sách con: (a3,a4, a8) - Dãy con: là một danh sách tạo thành bằng cách loại từ DS một số phần tử. VD: Dãy con: (a1,a4,a7,a8) 5
  6. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.1. Khái niệm 4.1.2. Các phép toán trên danh sách: 1. Phép khởi tạo tạo ra một danh sách rỗng 2. Tạo danh sách 3. Xác định độ dài của danh sách 4. Loại bỏ một phần tử 5. Chèn thêm một phần tử vào danh sách 6. Duyệt danh sách 7. Tìm kiếm một phần tử trong danh sách 8. Kiểm tra tính trạng thái rỗng của danh sách 9. Kiểm tra trạng thái tràn của danh sách 10. Sắp xếp lại các phần tử trong danh sách 11. Đảo ngược danh sách 6
  7. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2. Biểu diễn danh sách: 4.2.1. Biểu diễn bằng mảng (Lưu trữ kế tiếp) typedef Type ElementType; define MLIST 100 typedef truct LIST { int n; // Số phần tử của danh sách ElementType Ele[MLIST]; }; LIST A; Ví dụ: danh sách số nguyên: 0 1 2 3 4 5 6 7 8 1 5 3 6 4 8 9 12 15 7
  8. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2. Biểu diễn danh sách: 4.2.1. Biểu diễn bằng mảng (Lưu trữ kế tiếp) Thảo luận : - Các phép toán trên danh sách biểu diễn bằng mảng được thực hiện như thế nào? - Ưu nhược điểm gì khi biểu diễn danh sách bằng mẳng? 0 1 2 3 4 5 6 7 8 1 5 3 6 4 8 9 12 15 8
  9. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2. Biểu diễn danh sách: 4.2.1. Biểu diễn bằng mảng (Lưu trữ kế tiếp) • Phép khởi tạo: danh sách rỗng: 0 1 2 3 4 5 6 7 8 •Tạo một danh sách: 0 1 2 3 4 5 6 7 8 1 5 3 6 4 8 9 12 15 •Duyệt danh sách: 1 5 3 6 4 8 9 12 15 9
  10. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.1. Biểu diễn bằng mảng (Lưu trữ kế tiếp) • Phép chèn thêm một phần tử 21 tại vị trí k =5: •B1: Nếu A.n B2 else Kết thúc •B2: Nếu K B3 else Kết thúc 0 1 2 3 4 5 6 7 8 1 5 3 6 4 8 9 12 15 •B3: Thêm một ô nhớ mới : A.n ++; 0 1 2 3 4 5 6 7 8 9 1 5 3 6 4 8 9 12 15 B4:Dồn các số từ vị trí k đến hết về sau một chỗ: A.Elej= A.Elej-1 (j=n-1,k+1) B5: chèn phần0 tử1 mới2 vào3 vị trí4 k 5 6 7 8 9 1 5 3 6 4 218 89 129 1215 15 10
  11. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.1. Biểu diễn bằng mảng (Lưu trữ kế tiếp) • Phép xóa đi một phần tử tại vị trí k =4 (mang giá trị 4) •B1: Nếu A.n = 0 (ds rỗng)-> Kêt thúc •B2: Nếu k > A.n -> không tồn tại vị trí xóa -> Kêt thúc 0 1 2 3 4 5 6 7 8 1 5 3 6 4 8 9 12 15 •B3: Xóa: dồn các phần tử ở vị trí k +1 đến hết dãy về trước một chỗ 0 1 2 3 4 5 6 7 8 1 5 3 6 48 89 129 1215 15 •B4: Giảm số phần tử của dãy đi 1 phần tử A.n = A.n-1 0 1 2 3 4 5 6 7 1 5 3 6 8 9 12 15 11
  12. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.1. Biểu diễn bằng mảng (Lưu trữ kế tiếp) •Tìm kiếm trên danh sách: x= 8 •B1: Nếu A.n = 0 (rỗng) -> kết thúc •B2: duyệt từng phần tử của danh sách để so sánh với phần tử cần tìm, nếu thấy -> trả về vị trí tìm được •B3: Nếu duyệt hết ds mà không tìm thấy: trả về -1 0 1 2 3 4 5 6 7 8 1 5 3 66 44 88 9 12 15 12
  13. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.1. Biểu diễn bằng mảng (Lưu trữ kế tiếp) •Đảo ngược danh sách: DS A 0 1 2 3 4 5 6 7 8 1 5 3 6 4 8 9 12 15 •C1: Đảo các cặp phần tử đầu và cuối 0 1 2 3 4 5 6 7 8 151 125 39 86 4 68 93 125 151 C2: Lấy các phần tử từ cuối dãy về đầu và gán váo một DS B Gán ngƣợc trở lại DS A = B: DS B: 0 1 2 3 4 5 6 7 8 15 12 9 88 4 6 3 5 1 13
  14. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.1. Biểu diễn bằng mảng (Lưu trữ kế tiếp) • Thảo luận: –Thực hiện các thao tác tách danh sách làm hai tại vị trí k, ghép hai danh sách, sắp xếp danh sách như thế nào? –Độ phức tạp của các thao tác trên danh sách là bao nhiêu? 14
  15. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) Ví dụ: Danh sách tên sinh viên a) An next Đức next next Việt next NULL First Last b) NULL prev An prev Đức prev prev Việt First Last NULL prev prev prev prev c) An Đức Việt next next next next NULL First Last 15
  16. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) Ví dụ: Danh sách tên sinh viên Thảo luận: - Các danh sách trên có đặc điểm gì? - Hãy biểu diễn danh sách trên 16
  17. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) typedef struct NODE { ElementType data; NODE *link; // trường móc nối (next, hoặc prev) }; NODE *first, *last; 17
  18. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) Biểu diễn danh sách sinh viên gồm có các thông tin: Masv, hoten, tuoi typedef struct NODE { int masv; char hoten[30]; int tuoi; NODE *next; }; NODE *first, *last; // Danh sách FIFO (hình a) 18
  19. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Khởi tạo danh sách: danh sách rỗng first = last = NULL Thủ tục: void Init (NODE *(&first), NODE *(&last)) { first = last = NULL; } 19
  20. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Tạo ds có n phần tử: Thêm lần lượt các phần tử vào ds: Bài toán: Input: số phần tử n, các giá trị của n phần tử Output: Một danh sách liên kết FIFO có n phần tử 20
  21. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Tạo ds có n phần tử: Khởi tạo DS rỗng, và thêm lần lượt các phần tử vào ds: Giải thuật: Thêm một phần tử mới vào ds: - Cấp phát một nút mới p, nhập dữ liệu cho p - Nếu bộ nhớ đã hết ( p == NULL) -> kết thúc Ngược lại: Thêm p vào danh sách: -TH1: Nếu ds rỗng: gán phần tử đầu tiên first = last = p; -TH2: Nếu ds khác rỗng: móc nối phần tử cần thêm vào sau phần tử last ( sau khi móc nối – phần tử cuối cùng của ds là p) last -> next = p; last = p; 21
  22. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Thêm một phần tử mới vào danh sách: Khởi tạo: first = last = NULL B1: p = new NODE B2: Nhập giá trị cho nút p An next NULL B3: Móc nối vào ds: TH1: Nếu first = NULL => first =last = p An next NULL TH2: Nếu first != NULL first An next NULL (1) Last -> next = p (2) Last = p Đức next NULL 22
  23. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Duyệt danh sách: Bắt đầu từ phần tử đầu tiên first, tìm đến lần lượt các phần tử tiếp theo của danh sách đến hết (qua trường liên kết next) Giải thuật: -Nếu ds rỗng -> Kết thúc -Ngược lại: Gán p = first; (duyệt ds qua con trỏ p) Trong khi P còn khác rỗng thì: - Truy nhập đến giá trị của nút p - Cho p trỏ đến địa chỉ của phần tử tiếp theo để tiếp tục (p = p->next). 23
  24. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Duyệt danh sách: An P = An next First Đức P = Đức next Hà P = Hà next Hải P = Hải next Tú P = Tú next Vân P = Vân next NULL Last 24
  25. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Chèn một phần tử mới vào DS sau phần tử có giá trị được nhập từ bàn phím. Input: DS lưu trữ bằng hai con trỏ first, last phần tử mới cần chèn p Vị trí chèn sau phần tử có hten (đã nhập từ bàn phím) Output: DS đã được chèn thêm phần tử (first, last) 25
  26. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Chèn một phần tử mới vào DS sau phần tử có giá trị được nhập từ bàn phím (VD:phần tử có tên là Hà) Giải thuật: Nếu ds rỗng -> Kết thúc Ngược lại (DS không rỗng) -Tìm con trỏ ở vị trí cần chèn k (k->hoten = “Hà”) -Nếu không tìm thấy k: Kết thúc -Nếu tìm thấy k: +Cấp phát một nút mới p, cho nó chứa giá trị cần chèn + Móc nối p sau con trỏ k: ( B1. p->next = k->next; B2: k->next = p;) - Nếu vị trí chèn k là phần tử last -> gán lại phần tử last = p (vì p móc nối sau k) 26
  27. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Phép chèn: An next First Đức next P = new NODE k = Hà next (2) Lan next P (1) Hải next Tú next Vân next NULL Last 27
  28. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Xóa một phần tử trong danh sách có giá trị đƣợc nhập từ bàn phím Input: Danh sách được lưu trữ với hai con trỏ: first, last Phần tử cần xóa có Họ tên (đã nhập từ bàn phím) Output: Danh sách đã được xóa đi một phần tử 28
  29. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) .Xóa một phần tử trong DS có họ tên được nhập từ bàn phím Giải thuật: Nếu ds rỗng -> Kết thúc Ngược lại (DS không rỗng) + Nếu phần tử cần xóa p là phần tử first -> Xóa first first = first-> next; dekete(p); + Ngược lại: Tìm hai con trỏ q và p; q đứng trước phần tử cần xóa p: -Nếu không tìm thấy p: Kết thúc -Ngược lại: +Nếu phần tử cần xóa p là last -> xóa last q -> next = NULL; last = q; delete(p) + ngược lại: (p là phần tử trong DS) -> xóa p q->next = p->next; delete(p) 29
  30. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Phép xóa: Ví dụ: Xóa sinh viên An p = An next First first = p->next Đức next delete(p) Hà next Hải next Tú next Vân next NULL Last 30
  31. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Phép xóa: VD: Xóa sinh viên Vân An next First Đức next Hà next Hải next last = q q = Tú next NULL delete( p) p = last Vân next NULL Last 31
  32. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Phép xóa: VD: Xóa sinh viên Hải An next First Đức next q = Hà next q-> next delete(p) p = Hải next = p ->next p ->next Tú next Vân next NULL Last 32
  33. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Kiểm tra danh sách rỗng: Input: DS : first, last Output: DS rỗng hoặc không 33
  34. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Kiểm tra danh sách rỗng: Giải thuật: -Nếu first = NULL -> DS rỗng -Ngược lại DS khác rỗng > Viết hàm? int EmptyL (NODE *first, NODE *last) { return ( first == NULL); } 34
  35. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Đếm số phần tử trong danh sách Input: DS lưu trữ với hai con trỏ first, last Output: số phần tử trong danh sách Giải thuật: Nếu DS rỗng -> trả về số phần tử = 0 Ngược lại: - sử dụng biến đếm = 0 - cho con trỏ p trỏ tới phần tử đầu tiên trong danh sách -Duyệt lần tượt con trỏ p từ đầu đến hết danh sách - mỗi lần duyệt p tăng biến đếm lên 1(trỏ tới phần tử tiếp theo): - Kết thúc: trả về giá trị biến đếm. => viết hàm và tính độ phức tạp thuật toán 35
  36. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Tìm kiếm một phần tử trên danh sách có họ tên nhập từ bàn phím Input: DS lưu trữ với hai con trỏ first, last, hten cần tìm Output: địa chỉ của con trỏ tìm thấy p (Nếu p != NULL -> tìm thấy, ngược lại: không tìm thấy) 36
  37. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Tìm kiếm một phần tử trên danh sách có họ tên nhập từ bàn phím Giải thuật: Nếu DS rỗng -> kết thúc -Ngược lại (DS khác rỗng) -Cho p trỏ tới phần tử đầu tiên trong DS -Duyệt p lần lượt từ phần tử đầu tiên đến hết danh sách và kiểm tra: Nếu p->hoten = hten ( với hten là giá trị cần tìm) > Kết thúc tìm kiếm và trả về phần tử p vừa tím thấy - Ngược lại: tiếp tục xét phần tử tiếp theo (p= p->p->next -Nếu duyệt hết danh sách mà vẫn không tìm thấy thì trả về giá trị NULL => viết hàm và tính độ phức tạp thuật toán 37
  38. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Tìm kiếm phần tử có hten = Hải: An next First P->hoten (An)!= Hải P = P->hoten (Đức)!= Hải P = Đức next P->hoten (Đức)!= Hải P = Hà next P->hoten (Hải)==Hải P = Hải next Trả về con trỏ p đã tìm thấy Tú next Vân next NULL Last 38
  39. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Sắp xếp danh sách Input: DS lưu trữ với hai con trỏ first, last Output: DS đã được xếp theo giá trị tăng dần hoặc giảm dần của trường khóa sắp xếp (VD xếp theo chiều giảm dần của Họ tên) 39
  40. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Sắp xếp danh sách Giải thuật: Nếu DS rỗng -> kết thúc -Ngược lại (DS khác rỗng) -Cho p trỏ tới phần tử đầu tiên trong DS -Để xếp phần tử đầu tiên: -So sánh p với các phần tử q còn lại trong danh sách: (các phần tử q = p->next đến hết danh sách) Nếu P->hoten đổi giá trị của p cho q -> Phần tử p đã được xếp -Tiếp tục xếp phần tử tiếp theo: p = p->next: thực hiện tương tự -Lặp n-1 lần -> DS được xếp ( n là số phần tử trong DS) -=> viết hàm và tính độ phức tạp thuật toán 40
  41. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Ghép hai danh sách thành 1 danh sách: Input: DS 1: first1, last1, DS2: first1, last2 Output: DS được nối first, last 41
  42. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Ghép hai danh sách thành 1 danh sách: Giải thuật: Nếu 2 DS rỗng -> kết thúc -Ngược lại - Nếu DS1 rỗng DS nối là DS2 - Nếu DS2 rông -> DS nối là DS1 -Ngược lại -Cho phần tử cuối cùng của DS1 trỏ tới phần tử đầu tiên của DS2 -Gán phần tử đầu tiên của DS ghép = phần tử đầu tiên của DS1 -Gán phần tử cuối của DS ghép = phần tử cuối của DS2 -=> viết hàm và tính độ phức tạp thuật toán 42
  43. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Tách DS ban đầu thành hai danh sách tại vị trí k ( có họ tên nhập từ bàn phím) Input: DS dan đầu first, last , hten là vị trí cần tách Output: Hai ds sau khi tách DS 1: first1, last1, DS2: first1, last2 43
  44. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Tách DS ban đầu thành hai danh sách tại vị trí k Giải thuật: Nếu DS rỗng -> kết thúc -Ngược lại : Tìm vị trí k cần tách + Nếu không tìm thấy k -> kết thúc + Ngược lại: Tách DS2: Từ vị trí k đến hết DS1: Từ đầu đến trước k => viết hàm và tính độ phức tạp thuật toán 44
  45. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Đảo ngƣợc danh sách Input: DS dan đầu first, last Output: DS sau khi đảo ngược: first, last 45
  46. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Đảo ngƣợc danh sách Giải thuật: Nếu DS rỗng -> kết thúc -Ngược lại: Đảo mối liên kết từ phần tử đầu tiên đến hết ds *Đảo phần tử đầu tiên: -Cho p trỏ tới phần tử first -q trỏ tới p->next -t trỏ tới q>next ( -Đảo: p -> next = NULL; q->next = p nếu p = first thì gán last1 = p; * Tiếp tục đảo phần tử tiếp theo: p = q; q = t; q->next =p - Lặp n lần đến hết ds first1 = last; -=> viết hàm và tính độ phức tạp thuật toán 46
  47. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) Danh sách liên kết LIFO prev Việt NULL prev An prev Đức prev First Last Biểu diễn danh sách sinh viên gồm có các thông tin: Masv, hoten, tuoi typedef struct NODE { int masv; char hoten[30]; int tuoi; NODE *prev; }; NODE *first, *last; 47
  48. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Khởi tạo danh sách: danh sách rỗng first = last = NULL Thủ tục: void Init (NODE *(&first), NODE *(&last)) { first = last = NULL; } 48
  49. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Tạo ds có n phần tử: Thêm lần lượt các phần tử vào ds: Bài toán: Input: số phần tử n, các giá trị của n phần tử Output: Một danh sách liên kết LIFO có n phần tử 49
  50. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Tạo ds có n phần tử: Thêm lần lượt các phần tử vào danh sách: Khởi tạo: first = last = NULL Thêm một phần tử mới vào ds: B1: p = new NODE Last = An prev NULL B3: Móc nối vào ds: Móc nối sau last p->prev = last first = last = p Nếu First == NULL -> Gán first = p Last = Đức prev NULL Thêm phần tử thứ 2 Móc nối: 50
  51. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Tạo DS có n phần tử: Khởi tạo DS rỗng Thêm lần lượt các phần tử vào ds: Giải thuật: Thêm một phần tử mới vào ds: -Thêm một ô nhớ mới p, cho ô nhớ chứa dữ liệu cần thêm - Nếu bộ nhớ đã hết ( p == NULL) -> kết thúc -Ngược lại: Thêm p vào danh sách: -Móc nối phần tử thêm vào last: p->prev= last -KHi đó phần tử cuối là phần tử vừa thêm: last = p; -Nếu first == NULL -> gán first = p > Viết hàm và tính độ phức tạp thuật toán 51
  52. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Xây dựng các phép toán khác tương tự như ds FIFO 52
  53. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) Danh sách liên kết DOUBLE NULL prev prev prev prev An Đức Việt next next next next NULL First Last Biểu diễn danh sách sinh viên gồm có các thông tin: Masv, hoten, tuoi typedef struct NODE { int masv; char hoten[30]; int tuoi; NODE *prev,*next; }; NODE *first, *last; 53
  54. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Khởi tạo danh sách: danh sách rỗng first = last = NULL Thủ tục: void Init (NODE *(&first), NODE *(&last)) { first = last = NULL; } 54
  55. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Tạo DS có n phần tử: Thêm lần lượt các phần tử vào DS: Bài toán: Input: số phần tử n, các giá trị của n phần tử Output: Một danh sách liên kết DOUBLE có n phần tử 55
  56. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Tạo ds có n phần tử: Thêm lần lượt các phần tử vào danh sách: Khởi tạo: first = last = NULL Thêm một phần tử mới vào ds: B1: p = new NODE B2: Nhập giá trị cho nút NULL prev An next NULL B3: Móc nối vào ds: TH1: Nếu first = NULL -> first =last = p prev prev An next NULL TH2: Nếu first != NULL prev An next firstFirst = last NULL NULL Móc nối vào sau last: NULL prev Đức next last->next = p; Last= NULL p->prev = last; last = p 56
  57. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) . Tạo ds có n phần tử: Khởi tạo DS rỗng Thêm lần lượt các phần tử vào ds: Giải thuật: Để thêm một phần tử vào ds: -Thêm một ô nhớ mới p, - Nếu bộ nhớ đã hết ( p == NULL) -> kết thúc -Ngược lại: cho ô nhớ chứa dữ liệu, Thêm p vào danh sách: TH1: DS rỗng: (first ==NULL) gán first = last = p TH2: DS khác rỗng (first !=NULL) Móc nối vào sau phần tử last: last -> next = p; p->prev = last Phần tử cuối cùng chính là phần tử vừa thêm: last = p 57
  58. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.2.2. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) Danh sách nối vòng a) An next Đức next next Việt next NULL First Last An next Đức next next Việt next First 58
  59. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.3. Ngăn xếp (STACK) 4.3.1. Định nghĩa: Stack là danh sách tuyến tính mà việc bổ sung hay loại bỏ một phần tử chỉ thực hiện tại một đầu (top: gọi là đỉnh của Stack) còn đầu kia coi như bịt kín. Hoạt động: STACK hoạt động theo cơ chế LIFO ( Last In First Out): phần tử nào vào sau lấy ra trước, phần tử nào vào trước được lấy ra sau. top C B A 59
  60. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.3. Ngăn xếp (STACK) 4.3.2. Biểu diễn dữ liệu: Biểu diễn bằng mảng (lƣu trữ kế tiếp) Define MAXS 100 typedef truct STACK { int top; // Đỉnh STACK ElementType Ele[MAXS]; }; STACK S; 60
  61. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.3. Ngăn xếp (STACK) 4.3.2. Biểu diễn dữ liệu: Biểu diễn bằng cấu trúc tự trỏ (lƣu trữ móc nối) typedef struct STACK { ElementType data; STACK *prev; }; STACK *top; // con trỏ trỏ tới đỉnh của STACK 61
  62. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.3. Ngăn xếp (STACK) 4.3.3. Các phép toán trên Stack -Khởi tạo Stack - Đẩy một phần tử vào Stack - Kiểm tra Stack đầy - Lấy một phần tử khỏi Stack - Kiểm tra Stack rỗng. 62
  63. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.3. Ngăn xếp (STACK) 4.3.3. Các phép toán trên Stack Biểu diễn bằng danh sách chứa các số nguyên define MAXS 10 typedef struct STACK { int top; int Ele[MAXS]; }; STACK S; 63
  64. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.3. Ngăn xếp (STACK) 4.3.3. Các phép toán trên Stack 1. KHỞI TẠO : STACK rỗng void InitS( STACK &S) { S.top = -1; } 64
  65. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.3. Ngăn xếp (STACK) 4.3.3. Các phép toán trên Stack 2. Kiểm tra STACK đầy : STACK đầy khi đỉnh top = MAXS-1 int fullS( STACK &S) { return (S.top == MAXS -1); } 65
  66. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.3. Ngăn xếp (STACK) 4.3.3. Các phép toán trên Stack 3. Đẩy một phần tử vào STACK Giải thuật: - Kiểm tra nếu STACK đầy -> Kết thúc - Ngược lại: Đẩy vào: Thêm một chỗ mới (S.top ++) Đưa phần tử cần thêm vào vị trí S.top void pushS( STACK &S, int x) { if (FullS(S)) return; S.top ++; // Dành thêm một chỗ mới để đẩy x vào S.Ele[S.top] =x; } 66
  67. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.3. Ngăn xếp (STACK) 4.3.3. Các phép toán trên Stack 4. Kiểm tra STACK rỗng STACK rỗng khi đỉnh STACK = -1 int emptyS( STACK &S) { return (S.top ==-1); } 67
  68. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.3. Ngăn xếp (STACK) 4.3.3. Các phép toán trên Stack 5. Lấy một phần tử ra khỏi STACK Giải thuật: - Kiểm tra nếu STACK rỗng thì kết thúc Ngƣợc lại: Lấy phần tử ở đỉnh ra khỏi STACK Giảm đỉnh đi một đơn vị int popS( STACK &S ) { int y; if (EmptyS(S)) return -1; y = S.Ele[S.top] ; S.top ; // giam di mot cho return y; } 68
  69. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.3. Ngăn xếp (STACK) 4.3.4. Ứng dụng của Stack - Đổi số thập phân sang số nhị phân, hexa - Khử đệ quy - Tính giá trị của biểu thức theo ký pháp nghịch đảo Balance 69
  70. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.4. Hàng đợi (QUEUE) 4.4.1. Định nghĩa Queue là danh sách tuyến tính mà việc bổ sung một phần tử được thực hiện ở một đầu gọi là lối sau (rear), việc loại bỏ một phần tử được thực hiện ở đầu kia gọi là lối trước (front). •Hoạt động: queue hoạt động theo cơ chế FIFO (First Int First Out): front rear A B C D A B C D 70
  71. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.4. Hàng đợi (QUEUE) 4.4.2. Biểu diễn dữ liệu: Biểu diễn bằng mảng (lưu trữ kế tiếp) Define MAXQ 100 typedef truct QUEUE { int front; // vị trí đầu tiên hàng đợi int rear; // vị trí cuối cùng hàng đợi ElementType Ele[MAXQ]; // mảng Ele Chứa các phần tử }; QUEUE Q; 71
  72. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.4. Hàng đợi (QUEUE) 4.4.2. Biểu diễn dữ liệu: Biểu diễn bằng con trỏ (lưu trữ móc nối) (ds dạng FIFO) typedef KeyType ElementType; typedef struct QUEUE { ElementType data; QUEUE *next; }; QUEUE *front,*rear; 72
  73. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.4. Hàng đợi (QUEUE) 4.4.3. Các phép toán trên Queue - Khởi tạo Queue -Thêm một phần tử vào Queue ( Kiểm tra Queue đầy) - Xóa một phần tử khỏi Queue ( Kiểm tra Queue rỗng 73
  74. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.4. Hàng đợi (QUEUE) 4.4.3. Các phép toán trên Queue Chú ý: Hiện tượng tràn giả QUEUE A B C D A B Khắc phục: Tổ chức QUEUE vòng, hoặc dùng con trỏ để biểu diễn. 74
  75. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.4. Hàng đợi (QUEUE) 4.4.3. Các phép toán trên Queue Chú ý: Hiện tượng tràn giả QUEUE A B C D A B Khắc phục: Tổ chức QUEUE vòng, hoặc dùng con trỏ để biểu diễn. 75
  76. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.4. Hàng đợi (QUEUE) 4.4.3. Các phép toán trên Queue VD: Tổ chứa QUEUE vòng chứa các ký tự Define MAXQ 100 typedef truct QUEUE A { int front; B int rear; int count; // Biến để đếm số phần tử trong QUEUE ElementType Ele[MAXQ]; } Q; 76
  77. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.4. Hàng đợi (QUEUE) 4.4.3. Các phép toán trên Queue 1.Khởi tạo: hàng đợi rỗng void Init (QUEUE &Q) { Q.front = Q. rear = -1; Q.count; }; 77
  78. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.4. Hàng đợi (QUEUE) 4.4.3. Các phép toán trên Queue 2. Kiểm tra hàng đợi đầy: Khi số phần tử trong hàng = MAXQ int fullQ (QUEUE &Q) { return (Q.count == MAXQ) }; 78
  79. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.4. Hàng đợi (QUEUE) 4.4.3. Các phép toán trên Queue 2. Kiểm tra hàng đợi rỗng: Khi số phần tử trong hàng = 0 int emptyQ (QUEUE &Q) { return (Q.count == 0) }; 79
  80. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.4. Hàng đợi (QUEUE) 4.4.3. Các phép toán trên Queue 4. Thêm một phần tử vào hàng đợi: •Nếu QUEUE đầy -> kết thúc •Queue chƣa đầy: tăng rear++ –TH1: Nếu rear = MAXQ-1: chứng tỏ QUEUE đầy giả cho rear = 0 (về đầu) để thêm phần tử mới -TH2: ngược lại: rear++ •Thêm phần tử mới •Tăng biến đếm lên 1 phần tử • Sau khi thêm, Nếu front = -1: -> chỉnh front =0; 80
  81. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.4. Hàng đợi (QUEUE) 4.4.3. Các phép toán trên Queue 2. Thêm một phần tử vào hàng đợi: void insertQ( QUEUE &Q, char ch) { if (FullQ) return; if (Q.rear == MAXQ-1) Q.rear=0 else Q.rear++; Q.Ele[Q.rear] = ch; Q.count ++;//đã thêm một phần tử vào hàng đợi if (Q.front == -1) Q.front = 0; } 81
  82. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.4. Hàng đợi (QUEUE) 4.4.3. Các phép toán trên Queue 5. Lấy phần tử ra khỏi hàng đợi: Giải thuật: - Nếu hàng đợi rỗng (Q.count =0)-> kết thúc Ngược lại: -Lấy phần tử ở vị trí front: y = Q.Ele[Q.front] -Số phần tử giảm đi 1 -Chỉnh lại front: -Nếu Queue chỉ còn 1 phần tử (Q.front = Q.rear) thì chỉnh về rỗng: Q.front= Q.rear = -1; -Ngược lại: Nếu Q.front = MAXQ-1 thì chỉnh front về đầu hàng đợi để láy tiếp: Q.front = 0 -Ngược lại tăng front để lấy tiếp: Q.front ++; 82
  83. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.4. Hàng đợi (QUEUE) 4.4.3. Các phép toán trên Queue 3. lấy ra phần tử ra khỏi hàng đợi: char deleteQ( QUEUE &Q) { char ch; if (EmptyQ) return; ch = Q.Ele[Q.front]; // Lấy ký tự ở đỉnh queue (front) Q.count ; // số phần tử queue giảm đi 1 if (Q.rear = Q.front) { Q.rear = Q.front = -1; } else if (Q.front == MAXQ-1) Q.front = 0; else Q.front ++; return ch; } 83
  84. Chƣơng 4: DANH SÁCH TUYẾN TÍNH 4.5 Bài tập về nhà: 1. Cài đặt các phép toán trên STACK biểu diễn bằng mảng, cấu trúc tự trỏ chứa các số nguyên - Viết ứng dụng đổi số thập phân sang nhị phân (sử dụng Stack) -Viết ứng dụng tính giá trị biểu thức được biểu diễn bằng hậu tố (sử dụng Stack) -Mở rộng cho ứng dụng tính giá trị biểu thức được biểu diễn bằng tiền tố, trung tố. 2. Cài đặt hàng đợi chứa các ký tự biểu diễn bằng mảng, cấu trúc tự trỏ 84