nguyenngoc_k1_khmt
New Member
Download miễn phí Bài giảng Kiểu dữ liệu danh sách
Danh sách
Tóm tắt về trừu tượng hóa cấu trúc danh sách
• Mô tả dữ liệu
• A = (a0, a1, , an)
• Mô tả các phép toán trên cấu trúc danh sách
• empty (A): Kiểm tra danh sách có rỗng hay không
• length (A): Cho biết số phần tử của danh sách
• element (A, i) : Trả phần tử ở vị trí thứ i của A.
• insert (A, i, x): Thêm phần tử x vào danh sách A tại vị trí i.
• append (A, x): Thêm x vào ñuôi danh sách A
• delete (A, i): Loại phần tử ở vị trí thứ i trong danh sách A
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
Kiểu dữ liệu danh sáchLê Sỹ Vinh
Bộ môn Khoa Học Máy Tính – Khoa CNTT
ðại Học Công Nghệ - ðHQGHN
Email: [email protected]
Danh sách
Danh sách là gì?
Danh sách là cấu trúc dữ liệu tuyến tính, trong ñó các phần tử dữ liệu ñược
sắp xếp theo một thứ tự xác ñịnh
Ví dụ:
– Danh sách sinh viên
– Danh sách ñiện thoại
– Danh sách môn học
– Danh sách bài hát
– Danh sách công việc
Danh sách
Trừu tượng hóa cấu trúc danh sách
1. Mô tả dữ liệu
A = (a0, a1, …, an)
trong ñó ai là phần tử thứ i của danh sách A
Ví dụ:
A = (1, 2, 3, 3, 4, 5)
A = (‘Vinh’, ‘Tuấn’,. ‘Ánh’)
2. Mô tả các phép toán trên cấu trúc danh sách
• empty (A): Kiểm tra danh sách có rỗng hay không
• length (A): Cho biết số phần tử của danh sách
• element (A, i) : Trả phần tử ở vị trí thứ i của A.
Ví dụ: A =(1,3,5)
Element (A, 0) → 1
Element (A, 2) → 5
Danh sách
• insert (A, i, x): Thêm phần tử x vào danh sách A tại vị trí i.
A = (a0, a1,…, an) → A = (a0,a1,…,ai-1, x, ai,…an)
Ví dụ: A = (1,3,5)
insert (A, 1, 4) → A = (1, 4, 3, 5)
• append (A, x): Thêm x vào ñuôi danh sách A
A = (a , a ,…, a ) → A = (a ,a ,…,a , x)0 1 n 0 1 n
Ví dụ: A = (1,3,5)
append (A, 8) → A = (1, 3, 5, 8)
• delete (A, i): Loại phần tử ở vị trí thứ i trong danh sách A
A = (a0, a1,…ai-1, ai, ai+1, an) → A = (a0,a1,…,ai-1, ai+1,…an)
Ví dụ: A = (1,3,5)
delete (A, 1) → A = (1, 5)
Cài ñặt danh sách bằng mảng
Mảng (array)
• Tập hợp các phần tử (các biến) có cùng một kiểu
• Một phần tử cụ thể trong mảng sẽ ñược xác ñịnh và truy cập bởi một chỉ số
• Trong C/C++, các phần tử của mạng ñược ñặt cạnh nhau tạo thành một
khối liên tục. ðịa chỉ thấp nhất tương ứng với phần tử ñầu tiên, ñịa chỉ cao
nhất tương ứng với phần tử cuối cùng
• Mảng thì có thể là một chiều hay nhiều chiều
Cài ñặt danh sách bằng mảng
↑ ↑ ↑ ↑
0 1 . . . N Max- 1
Mảng một chiều:
a0 a1
. . . a
n
dataType arrayName [Max];
Ví dụ:
int scoreArr[100];
student studentArr[100];
Danh sách
Tóm tắt về trừu tượng hóa cấu trúc danh sách
• Mô tả dữ liệu
• A = (a0, a1, …, an)
• Mô tả các phép toán trên cấu trúc danh sách
• empty (A): Kiểm tra danh sách có rỗng hay không
• length (A): Cho biết số phần tử của danh sách
• element (A, i) : Trả phần tử ở vị trí thứ i của A.
• insert (A, i, x): Thêm phần tử x vào danh sách A tại vị trí i.
• append (A, x): Thêm x vào ñuôi danh sách A
• delete (A, i): Loại phần tử ở vị trí thứ i trong danh sách A
Các phép toán trên cấu trúc danh sách không phụ thuộc vào kiểu dữ liệu của các
phần tử trong danh sách!!!
Cài ñặt danh sách trong C++
Template
1. Generic function
2. Generic class
ListArr project
List.h
List.cpp
Các phép toán khác trên danh sách
• Tìm phần tử lớn nhất
• ðổi chỗ hai phần tử
• Sắp xếp tăng dần
Con trỏ (pointer)
• Là ñiểm mạnh nhất, nhưng cũng nguy hiểm nhất của C/ C++
• Chứa ñịa chỉ của một tế bào nhớ trong máy tính
Giá trị trong ô nhớ 1 2 3 3 1 4 6 5
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
ðịa chỉ ô nhớ 10 11 12 13 14 15 16 17
Con trỏ (pointer)
Khai báo con trỏ
type * pointerVariable
ví dụ:
int *p
Cấp phát bộ nhớ (allocate memory)
pointerVariable = new type (initializer)
Ví dụ:
p = new int (-1)
Giải phóng bộ nhớ
delete pointerVariable;
ví dụ:
delete p
(xem ví dụ chương trình)
Con trỏ (pointer)
Cấp phát bộ nhớ cho một ñối tượng dữ liệu
pointerVariable = new objectDataType
(xem ví dụ chương trình)
Con trỏ (pointer)
Cấp phát mảng ñộng
pointerVariable = new arrayType[size]
ví dụ:
int* p;
p = new int[10]
Giải phóng mảng ñộng
delete [] pointerVariable
ví dụ:
delete [] p;
(xem ví dụ chương trình)
Danh sách liên kết
-1 1 3 2
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
11 12 13 14 15 16 17 18 19 20 21 22
Mảng
int listArr[4] = {-1, 1, 3, 2}
-1 1 3 2
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
11 12 13 14 15 16 17 18 19 20 21 22
Danh sách
liên kết
(-1, 15) → (1, 16) → (3, 21) → (2, NULL)
head tail
↑ ↑
Cài ñặt danh sách liên kết
Xem chương trình
Các phép toán khác trên danh sách liên kết
• Tìm phần tử lớn nhất
• ðổi chỗ hai phần tử
• Sắp xếp tăng dần
Mảng và danh sách liên kết
• Truy cập phần tử
• Thêm phần tử
• Xóa phần tử
...