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

Chương 2: Các ADTs 1

Chương 2

Các kiểu dữ liệu trừu tượng cơ bản

(Basic Abstract Data Types)

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)

Chương 2: Các ADTs 3

• 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)

Danh sách (List)

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)

Chương 2: Các ADTs 5

Các phép toán trên DS (1)

Previous(p, L) Trả về vị trí trước phần tử p trong L

Full_List(L) Kiểm tra xem L có đầy hay không

Next(p, L) Trả về vị trí sau phần tử p trong L

End_List(L) Trả về vị trí sau phần tử cuối trong L

First_List(L) Trả về vị trí phần tử đầu tiên trong L

Empty_List(L) Kiểm tra xem L có rỗng hay không

MakeNull_List(L) Khởi tạo danh sách L rỗng

Phép toán Chức năng

Chương 2: Các ADTs 6

Các phép toán trên DS (2)

Read_List(L) Nhập giá trị các phần tử trong L

Truy xuất giá trị phần tử thứ p trong danh

sách L

Retrieve(p, L)

Trả về vị trí của phần tử có nội dung x trong

L, nếu không tìm thấy trả về End_List(L)

Locate(x, L)

Delete_List(p, L) Xóa phần tử tại vị trí p trong L

Hiển thị các phần tử trong L theo thứ tự

xuất hiện

Print_List(L)

Insert_List(x, p, L) Chèn phần tử có nội dung x vào L tại vị trí p

Phép toán Chức năng

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)

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);

}

}

Chương 2: Các ADTs 9

CĐ DS bằng mảng (1)

• 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”

Vị trí

1

2

3

…

Last

MaxLength

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)

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;

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;

}

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);

}

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);

}

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;

}