Bài giảng Kỹ thuật lập trình - Bài 4: Cấu trúc dữ liệu - Trịnh Thành Trung
Các bài toán thực
tế thường rất
phức tạp
Phải xác định được
o Các dữ liệu liên quan
đến bài toán
o Các thao tác cần thiết
để giải quyết bài toán
Mô tả
Cấu trúc
dữ liệu
. Các dữ liệu cấu thành
. Mối liên kết về mặt cấu
trúc giữa các dữ liệu
đó
Cung cấp các thao tác
trên dữ liệu đó
là cách tổ chức và thao tác
có hệ thống trên dữ liệu
Đặc trưng cho 1 kiểu dữ
liệu
Dữ liệu, kiểu dữ liệu &
cấu trúc dữ liệu
Machine Level Data Storage
0100110001101001010001
3.1415
'A'
28
Primitive Data Types
Basic Data Structures
array
stack
queue
list
High-Level Data Structures
hash table
tree
Các
kiểu dữ liệu
Kiểu dữ liệu cơ bản
(primitive data type)
▪Đại diện cho các dữ liệu
giống nhau, không thể
phân chia nhỏ hơn được
nữa
▪Thường được các ngôn
ngữ lập trình định nghĩa
sẵn
Kiểu dữ liệu có cấu trúc
(structured data type)
▪Được xây dựng từ các
kiểu dữ liệu (cơ bản, có
cấu trúc) khác
▪Có thể được các ngôn
ngữ lập trình định nghĩa
sẵn hoặc do lập trình viên
tự định nghĩa
▪Ví dụ
▫C/C++: int, long, char, bool...
▫Thao tác trên các số nguyên:
+ - * / ...
Nội dung
1. Mảng
2. Danh sách
3. Ngăn xếp
4. Hàng đợi
5. Cây
1.
Mảng
Array
Mảng
Array
▪ Dãy hữu hạn các phần tử liên tiếp có cùng kiểu và tên
▪ Một hay nhiều chiều
▫ C không giới hạn số chiều của mảng
Cú pháp
DataType ArrayName[size];
mảng nhiều chiều
DataType ArrayName[size 1][size 2]...[size n];
Khởi tạo giá trị
mảng
▪ C1. Khi khai báo
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
}, { 3, 1 }, { 3, 2 } };
char s1[6] = { 'H', 'a', 'n', 'o', 'i', '\0' }; //hoặc
char s1[6] = "Hanoi";
char s1[] = "Dai hoc Bach Khoa Hanoi"; //L = 24
int m[][] = { { 1, 2, 3 }, { 4, 5, 6 } };
▪ 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;
2.
Danh sách
List
Danh sách
List
▪ Danh sách
▫ Tập hợp các phần tử cùng kiểu
▫ Số lượng các phần tử của danh sách không cố định
▪ Phân loại
▫ Danh sách tuyến tính:
▸ 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ụ
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
tự này
▫ Danh sách phi tuyến tính: các phần tử trong danh sách không
được sắp thứ tự
Danh sách
List
▪ Lưu trữ
▫ Sử dụng vùng các ô nhớ liên tiếp trong bộ nhớ danh sách kế
tiếp
▫ Sử dụng vùng các ô nhớ không liên tiếp trong bộ nhớ danh
sách móc nối
▸ Danh sách nối đơn
▸ Danh sách nối kép
Thao tác trên
danh sách
. Khởi tạo danh sách (create)
. Kiểm tra danh sách rỗng (isEmpty)
. Kiểm tra danh sách đầy (isFull)
. Tính kích thước (sizeOf)
. Xóa rỗng danh sách (clear)
. Thêm một phần tử vào danh sách tại một ví trí cụ thể (insert)
. Loại bỏ một phần tử tại một vị trí cụ thể khỏi danh sách
(remove)
. Lấy một phần tử tại một vị trí cụ thể (retrieve)
. Thay thế giá trị của một phần tử tại một vị trí cụ thể (replace)
. 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)
Danh sách
kế tiếp
▪ Sử dụng một vector lưu trữ gồm một số các ô nhớ liên tiếp
▫ Các phần tử liền kề nhau được lưu trữ trong những ô nhớ liền
kề nhau
▫ Mỗi phần tử của danh sách cũng được gán một chỉ số chỉ thứ tự
được lưu trữ trong vector
▫ Tham chiếu đến các phần tử sử dụng địa chỉ được tính giống
như lưu trữ mảng.
0
1
2
i
last
n-1
Danh sách
kế tiếp
▪ Ưu điểm
▫ Tốc độ truy cập vào các phần tử của danh sách nhanh
▪ Nhược điểm
▫ Cần phải biết trước kích thước tối đa của danh sách
?
▫ 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
phần tử cũ khá tốn kém
?
Thêm vào
danh sách kế tiếp
▪ Điều kiện tiên quyết:
▫ Danh sách phải được khởi tạo rồi
▫ Danh sách chưa đầy
▫ Phần tử thêm vào chưa có trong danh sách
▪ Điều kiện hậu nghiệm:
▫ Phần tử cần thêm vào có trong danh sách
insert(3, ‘z’)
0 1 2 3 4 5 6 7 8 9
a b c d e f g h
z
count=98
Thêm vào
danh sách kế tiếp
Algorithm Insert
Input: index là vị trí cần thêm vào, element là giá trị cần thêm vào
Output: tình trạng danh sách
if list đầy
return overflow
if index nằm ngoài khoảng [0..count]
return range_error
//Dời tất cả các phần tử từ index về sau 1 vị trí
for i = count-1 down to index
entry[i+1] = entry[i]
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
Xóa khỏi
danh sách kế tiếp
remove(3, ‘d’)
0 1 2 3 4 5 6 7 8 9
a b c d e f g
h
count=7
Xóa khỏi
danh sách kế tiếp
Algorithm Remove
Input: index là vị trí cần xóa bỏ, element là giá trị lấy ra được
Output: danh sách đã xóa bỏ phần tử tại index
if list rỗng
return underflow
if index nằm ngoài khoảng [0..count-1]
return range_error
element = entry[index] //Lấy element tại vị trí index ra
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í
for i = index to count-1
entry[i] = entry[i+1]
return success;
End Remove
Duyệt
danh sách kế tiếp
Algorithm Traverse
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
//Quét qua tất cả các phần tử trong list
for index = 0 to count-1
Thi hành hàm visit để duyệt phần tử entry[index]
End Traverse
Tải về để xem bản đầy đủ
121 trang
197380
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Kỹ thuật lập trình - Bài 4: Cấu trúc dữ liệu - Trịnh Thành Trung", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_ky_thuat_lap_trinh_bai_4_cau_truc_du_lieu_trinh_th.pdf
