Xem mẫu
- Trịnh Thành Trung (ThS)
trungtt@soict.hust.edu.vn
om
.c
ng
Bài 4
co
an
CẤU TRÚC DỮ LIỆU th
ng
o
du
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Các bài toán thực
tế thường rất
om
phức tạp
.c
ng
co
Phải xác định được
an
o Các dữ liệu liên quan
th
đến bài toán
ng
o Các thao tác cần thiết
o
để giải quyết bài toán
du
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Mô tả
Cấu trúc Các dữ liệu cấu thành
dữ liệu Mối liên kết về mặt cấu
om
trúc giữa các dữ liệu
.c
đó
ng
co
là cách tổ chức và thao tác Cung cấp các thao tác
an
có hệ thống trên dữ liệu trên dữ liệu đó
th
ng
Đặc trưng cho 1 kiểu dữ
o
liệu
du
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Dữ liệu, kiểu dữ liệu &
cấu trúc dữ liệu
om
.c
Machine Level Data Storage 0100110001101001010001
ng
co
an
Primitive Data Types 28 3.1415 'A'
th
o ng
array
Basic Data Structures
du
u
cu
High-Level Data Structures stack queue list
hash table tree
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Các
kiểu dữ liệu
om
.c
Kiểu dữ liệu cơ bản Kiểu dữ liệu có cấu trúc
ng
(primitive data type) (structured data type)
co
▪Đại diện cho các dữ liệu ▪Được xây dựng từ các
an
giống nhau, không thể kiểu dữ liệu (cơ bản, có
th
phân chia nhỏ hơn được ng cấu trúc) khác
nữa ▪Có thể được các ngôn
▪Thường được các ngôn ngữ lập trình định nghĩa
o
du
ngữ lập trình định nghĩa sẵn hoặc do lập trình viên
u
sẵn tự định nghĩa
cu
▪Ví dụ
▫C/C++: int, long, char, bool...
▫Thao tác trên các số nguyên:
+ - * / ...
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- om
Nội dung
.c
ng
co
an
1. Mảng th
ng
2. Danh sách
o
du
3. Ngăn xếp
u
cu
4. Hàng đợi
5. Cây
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- om
.c
1.
ng
co
Mảng
an
Array
th
o ng
du
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Mảng
Array
om
.c
▪ Dãy hữu hạn các phần tử liên tiếp có cùng kiểu và tên
ng
▪ Một hay nhiều chiều
co
▫ C không giới hạn số chiều của mảng
an
th
ng
Cú pháp
o
DataType ArrayName[size];
du
mảng nhiều chiều
u
cu
DataType ArrayName[size 1][size 2]...[size n];
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Khởi tạo giá trị
mảng
om
.c
▪ C1. Khi khai báo
ng
co
float y[5] = { 3.2, 1.2, 4.5, 6.0, 3.6 }
int m[6][2] = { { 1, 1 }, { 1, 2 }, { 2, 1 }, { 2, 2
an
}, { 3, 1 }, { 3, 2 } };
th
char s1[6] = { 'H', 'a', 'n', 'o', 'i', '\0' }; //hoặc
ng
char s1[6] = "Hanoi";
o
char s1[] = "Dai hoc Bach Khoa Hanoi"; //L = 24
du
int m[][] = { { 1, 2, 3 }, { 4, 5, 6 } };
u
cu
▪ C2. Khai báo rồi gán giá trị cho từng phần tử của mảng.
int m[4];
m[0] = 1; m[1] = 2; m[2] = 3; m[3] = 4;
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- om
.c
2.
ng
co
Danh sách
an
List
th
o ng
du
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Danh sách
List
om
.c
▪ Danh sách
ng
▫ Tập hợp các phần tử cùng kiểu
co
▫ Số lượng các phần tử của danh sách không cố định
an
▪ Phân loại
th
▫ Danh sách tuyến tính: ng
▸ Có phần tử đầu tiên, phần tử cuối cùng
▸ Thứ tự trước / sau của các phần tử được xác định rõ ràng, ví dụ
o
du
sắp theo thứ tự tăng dần, giảm dần hay thứ tự trong bảng chữ cái
▸ Các thao tác trên danh sách phải không làm ảnh hưởng đến trật
u
tự này
cu
▫ Danh sách phi tuyến tính: các phần tử trong danh sách không
được sắp thứ tự
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Danh sách
List
om
.c
▪ Lưu trữ
ng
▫ Sử dụng vùng các ô nhớ liên tiếp trong bộ nhớ danh sách kế
co
tiếp
an
▫ Sử dụng vùng các ô nhớ không liên tiếp trong bộ nhớ danh
th
sách móc nối
ng
▸ Danh sách nối đơn
o
▸ Danh sách nối kép
du
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Thao tác trên
danh sách
om
.c
Khởi tạo danh sách (create)
ng
Kiểm tra danh sách rỗng (isEmpty)
co
Kiểm tra danh sách đầy (isFull)
Tính kích thước (sizeOf)
an
Xóa rỗng danh sách (clear)
th
Thêm một phần tử vào danh sách tại một ví trí cụ thể (insert)
ng
Loại bỏ một phần tử tại một vị trí cụ thể khỏi danh sách
o
(remove)
du
Lấy một phần tử tại một vị trí cụ thể (retrieve)
u
Thay thế giá trị của một phần tử tại một vị trí cụ thể (replace)
cu
Duyệt danh sách và thực hiện một thao tác tại các vị trí trong
danh sách (traverse)
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Danh sách
kế tiếp
om
.c
▪ Sử dụng một vector lưu trữ gồm một số các ô nhớ liên tiếp
ng
▫ Các phần tử liền kề nhau được lưu trữ trong những ô nhớ liền
co
kề nhau
an
▫ Mỗi phần tử của danh sách cũng được gán một chỉ số chỉ thứ tự
th
được lưu trữ trong vector
ng
▫ Tham chiếu đến các phần tử sử dụng địa chỉ được tính giống
o
như lưu trữ mảng.
du
u
cu
0 1 2 i last n-1
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Danh sách
kế tiếp
om
.c
▪ Ưu điểm
ng
▫ Tốc độ truy cập vào các phần tử của danh sách nhanh
co
▪ Nhược điểm
an
▫ Cần phải biết trước kích thước tối đa của danh sách
th ?
o ng
▫ Thực hiện các phép toán bổ sung các phần tử mới và loại bỏ các
du
phần tử cũ khá tốn kém
u
?
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Thêm vào
danh sách kế tiếp
om
.c
▪ Điều kiện tiên quyết:
ng
▫ Danh sách phải được khởi tạo rồi
co
▫ Danh sách chưa đầy
an
▫ Phần tử thêm vào chưa có trong danh sách
▪ Điều kiện hậu nghiệm:
th
ng
▫ Phần tử cần thêm vào có trong danh sách
o
du
insert(3, ‘z’)
u
cu
0 1 2 3 4 5 6 7 8 9
z
a b c d e f g h
count=9
count=8
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Thêm vào
danh sách kế tiếp
om
.c
Algorithm Insert
ng
Input: index là vị trí cần thêm vào, element là giá trị cần thêm vào
co
Output: tình trạng danh sách
an
if list đầy
th
return overflow ng
if index nằm ngoài khoảng [0..count]
return range_error
o
du
//Dời tất cả các phần tử từ index về sau 1 vị trí
for i = count-1 down to index
u
entry[i+1] = entry[i]
cu
entry[index] = element // Gán element vào vị trí index
count++ // Tăng số phần tử lên 1
return success;
End Insert
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Xóa khỏi
danh sách kế tiếp
om
.c
ng
co
remove(3, ‘d’)
an
0 1 2 3 th
4 5 6 7 8 9
o ng
a b c d e f g h
du
u
cu
count=7
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Xóa khỏi
danh sách kế tiếp
om
.c
Algorithm Remove
Input: index là vị trí cần xóa bỏ, element là giá trị lấy ra được
ng
Output: danh sách đã xóa bỏ phần tử tại index
co
if list rỗng
an
return underflow
th
if index nằm ngoài khoảng [0..count-1]
ng
return range_error
o
element = entry[index] //Lấy element tại vị trí index ra
du
count-- //Giảm số phần tử đi 1
//Dời tất cả các phần tử từ index về trước 1 vị trí
u
cu
for i = index to count-1
entry[i] = entry[i+1]
return success;
End Remove
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Duyệt
danh sách kế tiếp
om
.c
Algorithm Traverse
ng
Input: hàm visit dùng để tác động vào từng phần tử
Output: danh sách được cập nhật bằng hàm visit
co
an
//Quét qua tất cả các phần tử trong list
for index = 0 to count-1
th
Thi hành hàm visit để duyệt phần tử entry[index]
o ng
End Traverse
du
u
cu
CuuDuongThanCong.com https://fb.com/tailieudientucntt
nguon tai.lieu . vn