© 2004, HOÀNG MINH SƠN
Chươn
g
1
Kỹ thuật lập trình
0101010101010101100001
0101010101010101100001
0101010101010101100001
0101010100101010100101
0101010100101010100101
0101010100101010100101
1010011000110010010010
1010011000110010010010
1010011000110010010010
1100101100100010000010
1100101100100010000010
1100101100100010000010
0101010101010101100001
0101010101010101100001
0101010101010101100001
0101010100101010100101
0101010100101010100101
0101010100101010100101
1010011000110010010010
1010011000110010010010
1010011000110010010010
1100101100100010000010
1100101100100010000010
1100101100100010000010
0101010101010101100001
0101010101010101100001

© 2004, HOÀNG MINH SƠN
Chương 4: Khái quát về cấutrúcdữ liệu
4.1 Giớithiệuchung
 Phầnlớn các bài toán trong thựctế liên quan tớicác
dữ liệuphứchợp, những kiểudữ liệucơ bảntrong
ngôn ngữ lập trình không ₫ủ biểudiễn
 Ví dụ:
—Dữ liệu sinh viên: Họ tên, ngày sinh, quê quán, mã số SV,
—Môhìnhhàmtruyền: Đathứctử số, ₫athứcmẫusố
—Môhìnhtrạng thái: Các ma trận A, B, C, D
—Dữ liệuquátrình: Tên₫ạilượng, dải ₫o, giá trị, ₫ơnvị, thời
gian, cấpsaisố, ngưỡng giá trị,
— Đốitượng ₫ồ họa: Kích thước, màu sắc, ₫ường nét, phông
chữ,
 Phương pháp biểudiễndữ liệu: ₫ịnh nghĩakiểudữ
liệumớisử dụng cấu trúc (struct, class, union, )
4
© 2004, HOÀNG MINH SƠN
Chương 4: Khái quát về cấutrúcdữ liệu
Vấn ₫ề: Biểudiễntậphợpdữ liệu
 Đasố những dữ liệuthuộcmột ứng dụng có liên quan
với nhau => cầnbiểudiễntrongmộttậphợpcócấu
trúc, ví dụ:
— Danhsáchsinhviên: Cácdữ liệu sinh viên ₫ượcsắpxếptheo
thứ tự Alphabet
—Mộ hình tổng thể cho hệ thống ₫iều khiển: Bao gồm nhiều
thành phầntương tác
—Dữ liệuquátrình: Mộttậpdữ liệucóthể mang giá trị của
một ₫ạilượng vào các thời ₫iểmgián₫oạn, các dữ liệu ₫ầu
vào liên quan tớidữ liệu ₫ầura

bị hạnchế cố₫ịnh, không cầnbiếttrướckhitạocấu
trúc, phù hợpvớicả bài toán nhỏ và lớn
 Hiệuquả quảnlýdữ liệuphụ thuộcvào
—Cấutrúcdữ liệu ₫ượcsử dụng
—Giảithuật ₫ượcápdụng cho bổ sung, tìm kiếm, sắpxếp, xóa
bỏ
7
© 2004, HOÀNG MINH SƠN
Chương 4: Khái quát về cấutrúcdữ liệu
Các cấutrúcdữ liệu thông dụng
 Mảng (nghĩarộng): Tậphợpcácdữ liệucóthể truy
nhậptùyý theochỉ số
 Danh sách (list): Tậphợpcácdữ liệu ₫ược móc nối ₫ôi
mộtvớinhauvàcóthể truy nhậptuầntự
 Cây (tree): Tậphợpcácdữ liệu ₫ược móc nốivới nhau
theo cấutrúccây, cóthể truy nhậptuầntự từ gốc
—Nếumỗi nút có tối ₫a hai nhánh: cây nhị phân (binary tree)
 Bìa, bảng (map): Tậphợpcácdữ liệucósắpxếp, có
thể truy nhậprất nhanh theo mã khóa (key)
 Hàng ₫ợi (queue): Tậphợpcácdữ liệucósắpxếp
tuầntự, chỉ bổ sung vào từ một ₫ầuvàlấyratừ₫ầu
còn lại
8
© 2004, HOÀNG MINH SƠN
Chương 4: Khái quát về cấutrúcdữ liệu
Các cấutrúcdữ liệu thông dụng (tiếp)
 Tậphợp(set): Tậphợpcácdữ liệu ₫ượcsắpxếptùyý
nhưng có thể truy nhậpmộtcáchhiệuquả
 Ngănxếp (stack): Tậphợpcácdữ liệu ₫ượcsắpxếp
tuầntự, chỉ truy nhập ₫ượctừ một ₫ầu

 Mảng ₫ộng là mộtmảng ₫ượccấpphátbộ nhớ theo
yêu cầu, trong khi chương trình chạy
#include <stdlib.h> /* C */
int n = 50;

float* p1= (float*) malloc(n*sizeof(float)); /* C */
double* p2= new double[n]; // C++
 Sử dụng con trỏ₫ểquảnlýmảng ₫ộng: Cách sử dụng
không khác so vớimảng tĩnh
p1[0] = 1.0f;
p2[0] = 2.0;
 Sau khi sử dụng xong => giải phóng bộ nhớ:
free(p1); /* C */
delete [] p2; // C++
11
© 2004, HOÀNG MINH SƠN
Chương 4: Khái quát về cấutrúcdữ liệu
Cấpphátvàgiải phóng bộ nhớ₫ộng
 C:
—Hàmmalloc() yêu cầuthamsố là số byte, trả về con trỏ
không kiểu(void*) mang ₫ịachỉ vùng nhớ mới ₫ượccấp
phát (nằm trong heap), trả về 0 nếu không thành công.
—Hàmfree() yêu cầuthamsố là con trỏ không kiểu(void*),
giải phóng vùng nhớ có ₫ịachỉ₫ưavào
 C++:
—Toántử new chấpnhậnkiểudữ liệuphầntử kèm theo số
lượng phầntử củamảng cầncấpphátbộ nhớ (trong vùng
heap), trả về con trỏ có kiểu, trả về 0 nếu không thành công.
—Toántử delete[] yêu cầuthamsố là con trỏ có kiểu.
—Toántử new và delete còn có thể áp dụng cho cấpphátvà

 Cú pháp
int* p = new int;
*p = 1;
p[0]= 2; // the same as above
p[1]= 1; // access violation!
int* p2 = new int(1); // with initialization
delete p;
delete p2;
Student* ps = new Student;
ps->code = 1000;

delete ps;
 Mộtbiến ₫ơn khác vớimảng mộtphầntử!
14
© 2004, HOÀNG MINH SƠN
Chương 4: Khái quát về cấutrúcdữ liệu
Ý nghĩacủasử dụng bộ nhớ₫ộng
 Hiệusuất:
—Bộ nhớ₫ượccấpphát₫ủ dung lượng theo yêu cầuvàkhi
₫ượcyêucầutrongkhichương trình ₫ãchạy
—Bộ nhớ₫ượccấpphátnằm trong vùng nhớ tự do còn lạicủa
máy tính (heap), chỉ phụ thuộc vào dung lượng bộ nhớ của
máy tính
—Bộ nhớ có thể₫ượcgiải phóng khi không sử dụng tiếp.
 Linh hoạt:
—Thờigian"sống" củabộ nhớ₫ượccấpphát₫ộng có thể kéo
dài hơnthời gian "sống" củathựcthể cấpphátnó.
—Cóthể mộthàmgọilệnh cấpphátbộ nhớ, nhưng mộthàm
khác giải phóng bộ nhớ.
—Sự linh hoạtcũng dễ dẫn ₫ếnnhững lỗi"ròrỉ bộ nhớ".

Date* date_list;
createDateList(n, date_list);
for (int i=0; i < n; ++i) {

}
for ( ) { cout << }
delete [] date_list;
}
17
© 2004, HOÀNG MINH SƠN
Chương 4: Khái quát về cấutrúcdữ liệu
4.3 Xây dựng cấutrúcVector
 Vấn ₫ề: Biểudiễnmột vector toán họctrongC/C++?
 Giải pháp chân phương: mảng ₫ộng thông thường, nhưng
—Sử dụng không thuậntiện: Ngườisử dụng tự gọicáclệnh cấpphát
và giải phóng bộ nhớ, trong các hàm luôn phải ₫ưathamsố là số
chiều.
—Sử dụng không an toàn: Nhầmlẫnnhỏ dẫn ₫ếnhậuquả nghiêm
trọng
int n = 10;
double *v1,*v2, d;
v1 = (double*) malloc(n*sizeof(double));
v2 = (double*) malloc(n*sizeof(double));
d = scalarProd(v1,v2,n); // scalar_prod đãcó
d = v1 * v2; // OOPS!
v1.data[10] = 0; // OOPS!
free(v1);
free(v2);
18
© 2004, HOÀNG MINH SƠN

}
void destroyVector(Vector v) {
free(v.data);
}
double getElem(Vector v, int i) {
if (i < v.nelem && i >= 0) return v.data[i];
return 0;
}
20
© 2004, HOÀNG MINH SƠN
Chương 4: Khái quát về cấutrúcdữ liệu
void putElem(Vector v, int i, double d) {
if (i >=0 && i < v.nelem) v.data[i] = d;
}
Vector addVector(Vector a, Vector b) {
Vector c = {0,0};
if (a.nelem == b.nelem) {
c = createVector(a.nelem,0.0);
for (int i=0; i < a.nelem; ++i)
c.data[i] = a.data[i] + b.data[i];
}
return c;
}
Vector subVector(Vector a, Vector b) {
Vector c = {0,0};

return c;
}
21
© 2004, HOÀNG MINH SƠN

—Sử dụng tiếtkiệmbộ nhớ
23
© 2004, HOÀNG MINH SƠN
Chương 4: Khái quát về cấutrúcdữ liệu
Sử dụng kiểumảng?
 Số phầntử trong mộtmảng thựcchất không bao giờ
thay ₫ổi ₫ược. Dung lượng bộ nhớ vào thời ₫iểmcấp
phát phảibiếttrước, không thựcsự co giãn ₫ược.
 Nếu không thựcsự sử dụng hết dung lượng ₫ãcấp
phát => lãng phí bộ nhớ
 Nếu ₫ãsử dụng hếtdung lượng và muốnbổ sung
phầntử thì phảicấpphátlạ
i và sao chép toàn bộ dữ
liệusang mảng mới=> cần nhiềuthờigiannếusố
phầntử lớn
 Nếumuốnchènmộtphầntử/xóa mộtphầntửở₫ầu
hoặcgiữamảng thì phải sao chép và dịch toàn bộ
phầndữ liệucònlại => rấtmấtthờigian
24
© 2004, HOÀNG MINH SƠN
Chương 4: Khái quát về cấutrúcdữ liệu
Danh sách móc nối (linked list)
Dữ liệuA
Dữ liệuB
Dữ liệuX
Dữ liệuY0x00
Dữ liệuC
pHead
Item A
Item B