2
© 2004, HOÀNG MINH SƠN
Chương 4: Khái quát về cấutrúcdữ liệu
Nộidung chương 4
4.1 Cấutrúcdữ liệulàgì?
4.2 Mảng và quảnlýbộ nhớ₫ộng
4.2 Xây dựng cấu trúc Vector
4.3 Xây dựng cấutrúcList
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g
e

V
i
e
w
e
r
w
w
w
.

w
e
r
w
w
w
.
d
o
c
u
-
t
r
a
c
k
.
c
o
m
Simpo PDF Merge and Split Unregistered Version -

TÌM HIỂU CÁC DỮ LIỆU PHỨC HỘP TRONG LẬP TRÌNH
NỘI DUNG BÀI HỌC:
3
© 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

r
w
w
w
.
d
o
c
u
-
t
r
a
c
k
.
c
o
m
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g

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
— Đốitượng ₫ồ họ
a: Mộtcửasổ bao gồm nhiều ₫ốitượng ₫ồ
họa, mộtbảnvẽ cũng bao gồm nhiều ₫ốitượng ₫ồ họa
 Thông thường, các dữ liệutrongmộttậphợpcócùng
kiểu, hoặcítralàtương thích kiểuvớinhau
 Kiểumảng không phải bao giờ cũng phù hợp!
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g
e


C
h
a
n
g
e

V
i
e
w
e
r
w
w
w
.
d
o
c
u
-
t
r
a
c
k
.
c
o

V
i
e
w
e
r
w
w
w
.
d
o
c
u
-
t
r
a
c
k
.
c
o
m
Click to buy NOW!
P
D
F
-
X

m
Simpo PDF Merge and Split Unregistered Version -
6
© 2004, HOÀNG MINH SƠN
Chương 4: Khái quát về cấutrúcdữ liệu
QuảnlýDL thế nàolàhiệuquả?
 Tiếtkiệmbộ nhớ: Phần "overhead" không ₫áng kể so
vớiphầndữ liệuthực
 Truy nhập nhanh, thuậntiện: Thờigiancầnchobổ
sung, tìm kiếm và xóa bỏ các mụcdữ liệuphảingắn
 Linh hoạt: Số lượng các mụcdữ liệu không (hoặcít)
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ỏ
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g
e


C
h
a
n
g
e

V
i
e
w
e
r
w
w
w
.
d
o
c
u
-
t
r
a
c
k
.
c
o


V
i
e
w
e
r
w
w
w
.
d
o
c
u
-
t
r
a
c
k
.
c
o
m
Click to buy NOW!
P
D
F
-

o
m
Simpo PDF Merge and Split Unregistered Version -
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
 Bảng hash (hash table): Tậphợpcácdữ liệu ₫ượcsắp
xếpdựatheomộtmãsố nguyên tạoratừ mộthàm
₫ặ
cbiệt
 Bộ nhớ vòng (ring buffer): Tương tự như hàng ₫ợi,
nhưng dung lượng có hạn, nếuhếtchỗ sẽ₫ượcghi
quay vòng
 Trong toán họcvàtrong₫iềukhiển: vector, ma trận,
₫athức, phân thức, hàm truyền,
Click to buy NOW!
P
D
F
-
X
C
h
a
n

F
-
X
C
h
a
n
g
e

V
i
e
w
e
r
w
w
w
.
d
o
c
u
-
t
r
a
c
k

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++
Simpo PDF Merge and Split Unregistered Version -
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à
giải phóng bộ nhớ cho mộtbiến ₫ơn, một ₫ốitượng chứ
không nhấtthiế

 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ử!
Simpo PDF Merge and Split Unregistered Version -
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ớ.

int n;
cout << "Enter the number of your national holidays:";
cin >> n;
Date* date_list;
createDateList(n, date_list);
for (int i=0; i < n; ++i) {

}
for ( ) { cout << }
delete [] date_list;
}
Simpo PDF Merge and Split Unregistered Version -
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!

Vector createVector(int n, double init) {
Vector v;
v.nelem = n;
v.data = (double*) malloc(n*sizeof(double));
while (n ) v.data[n] = init;
return v;
}
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;
}
Simpo PDF Merge and Split Unregistered Version -
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;
}

— Danh sách những việccầnlàm
—Các₫ốitượng ₫ồ họatrênhìnhvẽ
— Các khâu ₫ộng họctrongsơ₫ồmô phỏng hệ thống (tương tự
trong SIMULINK)
 Các yêu cầu ₫ặc thù:
—Số lượng mụcdữ liệutrongdanhsáchcóthể thay ₫ổithường
xuyên
— Các thao tác bổ sung hoặcxóadữ liệucần ₫ượcthựchiện
nhanh, ₫ơngiản
—Sử dụng tiếtkiệmbộ nhớ
Simpo PDF Merge and Split Unregistered Version -
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
Simpo PDF Merge and Split Unregistered Version -
24

Dữ liệuY0x00
Dữ liệuC
pHead
Dữ liệuT
Bổ sung vào giữa danh sách
Bổ sung vào ₫ầudanhsách
Simpo PDF Merge and Split Unregistered Version -
26
© 2004, HOÀNG MINH SƠN
Chương 4: Khái quát về cấutrúcdữ liệu
Xóa bớtdữ liệu
Dữ liệuA
Dữ liệuB
Dữ liệuX
Dữ liệuY0x00
Dữ liệuC
pHead
Dữ liệuA
Dữ liệuB
Xóa dữ liệu ₫ầudanhsách
Dữ liệuC
Dữ liệuX
Dữ liệuY0x00
pHead
Xóa dữ liệugiữadanhsách
Simpo PDF Merge and Split Unregistered Version -