intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Chương 2: Các kiểu dữ liệu trừu tượng cơ bản (Basic Abstract Data Types)

Chia sẻ: Nguyen Ngoc Thich | Ngày: | Loại File: PDF | Số trang:162

Thêm vào BST
Báo xấu
106
lượt xem 12
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Các phần tử trong DS có thứ tự tuyến tính theo vị trí xuất hiện: ai đứng trước ai+1 (i=1..n-1)...

Chủ đề:

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

Lưu

Nội dung Text: Chương 2: Các kiểu dữ liệu trừu tượng cơ bản (Basic Abstract Data Types)

  1. Chương 2 Các kiểu dữ liệu trừu tượng cơ bản (Basic Abstract Data Types) 1 Chương 2: Các ADTs
  2. Nội dung • Danh sách (List) – Cài đặt bằng mảng – Cài đặt bằng con trỏ – Cài đặt bằng con nháy (tham khảo) • Ngăn xếp (Stack) • Hàng đợi (Queue) • Danh sách liên kết kép (Double Linked List) (tham khảo) 2 Chương 2: Các ADTs
  3. Danh sách (List) • Khái niệm • Các phép toán • Cài đặt danh sách (CĐ DS) – bằng mảng danh sách đặc – bằng con trỏ danh sách liên kết (Single Linked List) 3 Chương 2: Các ADTs
  4. Khái niệm DS • Là tập hợp hữu hạn các phần tử có cùng kiểu • Kiểu chung được gọi là kiểu phần tử (Element Type) • Thường biểu diễn dưới dạng: a1, a2, ..., an • Nếu – n=0: danh sách rỗng – n>0: phần tử đầu tiên là a1, phần tử cuối cùng là an • Độ dài của DS: số phần tử của DS • Các phần tử trong DS có thứ tự tuyến tính theo vị trí xuất hiện: ai đứng trước ai+1 (i=1..n-1) 4 Chương 2: Các ADTs
  5. Các phép toán trên DS (1) Phép toán Chức năng MakeNull_List(L) Khởi tạo danh sách L rỗng Kiểm tra xem L có rỗng hay không Empty_List(L) Kiểm tra xem L có đầy hay không Full_List(L) Trả về vị trí phần tử đầu tiên trong L First_List(L) Trả về vị trí sau phần tử cuối trong L End_List(L) Trả về vị trí sau phần tử p trong L Next(p, L) Trả về vị trí trước phần tử p trong L Previous(p, L) 5 Chương 2: Các ADTs
  6. Các phép toán trên DS (2) Phép toán Chức năng Insert_List(x, p, L) Chèn phần tử có nội dung x vào L tại vị trí p Trả về vị trí của phần tử có nội dung x trong Locate(x, L) L, nếu không tìm thấy trả về End_List(L) Truy xuất giá trị phần tử thứ p trong danh Retrieve(p, L) sách L Xóa phần tử tại vị trí p trong L Delete_List(p, L) Nhập giá trị các phần tử trong L Read_List(L) Hiển thị các phần tử trong L theo thứ tự Print_List(L) xuất hiện 6 Chương 2: Các ADTs
  7. Áp dụng • Thêm phần tử x vào đầu/ cuối L? • Xóa phần tử ở đầu/ cuối L? • Truy xuất phần tử ở đầu/ cuối L? Insert_List(x, First_List(L), L) Delete_List(First_List(L), L) Retrieve(First_List(L), L) 7 Chương 2: Các ADTs
  8. Ví dụ Dùng các phép toán trừu tượng trên danh sách, viết hàm sắp xếp danh sách theo thứ tự tăng dần void Sort(List L) { Position p,q; //ki u v trí c a các ph n t p= First_List(L); // v trí ph n t ñ u tiên while (p->Next != End_List(L)) { q = Next(p,L); // v trí ph n t sau ph n t p while (q != End_List(L)) { if (Retrieve(p, L) > Retrieve(q, L)) Swap(p, q); // hoán ñ i n i dung 2 ph n t q = Next(q, L); } p = Next(p, L); } } 8 Chương 2: Các ADTs
  9. CĐ DS bằng mảng (1) 1 2 3 … Last MaxLength Vị trí • Vị trí của phần tử trong danh sách:“chỉ số mảng tại vị trí lưu trữ phần tử + 1” 9 Chương 2: Các ADTs
  10. CĐ DS bằng mảng (2) • Dùng 1 mảng để lưu trữ liên tiếp các phần tử (Elements) • Có kiểu phần tử (ElementType) và kiểu vị trí (Position) xác định • Phải ước lượng số phần tử tối đa của danh sách (MaxLength) • Phải lưu trữ độ dài hiện tại của danh sách (Last) 10 Chương 2: Các ADTs
  11. CĐ DS bằng mảng (3)_Khai báo #define MaxLength ... typedef ... ElementType; typedef int Position; typedef struct { ElementType Elements[MaxLength]; Position Last; } List; Khai báo khi sử dụng List L; 11 Chương 2: Các ADTs
  12. CĐ DS bằng mảng (4)_Khởi tạo L rỗng • Cho độ dài danh sách bằng 0 void MakeNull_List(List *L){ L->Last = 0; } 12 Chương 2: Các ADTs
  13. CĐ DS bằng mảng (5)_Kiểm tra L rỗng? • Đ dài danh sách có b ng 0 hay không? int Empty_List(List L){ return (L.Last == 0); } 13 Chương 2: Các ADTs
  14. CĐ DS bằng mảng (6)_Kiểm tra L đầy? • Đ dài danh sách có b ng MaxLength hay không? int Full_List(List L){ return (L.Last == MaxLength); } 14 Chương 2: Các ADTs
  15. CĐ DS bằng mảng (7)_Vị trí phần tử đầu tiên • V trí 1 Position First_List(List L){ return 1; } 15 Chương 2: Các ADTs
  16. CĐ DS bằng mảng (8)_Vị trí sau phần tử cuối • V trí Last + 1 Position End_List(List L){ return (L.Last + 1); } 16 Chương 2: Các ADTs
  17. CĐ DS bằng mảng (9)_Vị trí phần tử kế tiếp p • V trí p + 1 Position Next(Position p, List L){ return (p + 1); } 17 Chương 2: Các ADTs
  18. CĐ DS bằng mảng (10)_Vị trí phần tử trước p • V trí p - 1 Position Previous(Position p, List L){ return (p - 1); } 18 Chương 2: Các ADTs
  19. CĐ DS bằng mảng (11)_Truy xuất phần tử thứ p • Giá tr t i ch s p - 1 ElementType Retrieve(Position p, List L){ return (L.Elements[p-1]); } 19 Chương 2: Các ADTs
  20. CĐ DS bằng mảng (12)_Chèn x vào vị trí p Nếu mảng đầy in thông báo … Nếu vị trí p không hợp lệ ( p < 1 hoặc p > End_List(L) ) in thông báo … Ngược lại • Dời các phần tử từ vị trí p đến cuối ra sau một vị trí • Đưa phần tử x vào vị trí p • Tăng độ dài lên 1 20 Chương 2: Các ADTs
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2