© 2004, HOÀNG MINH SƠN
Chương 1
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
0101010101010101100001
0101010100101010100101
0101010100101010100101

Chương 4: Khái quát về cấutrúcdữ liệu
© 2005 - HMS
 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.1 Giớithiệuchung
4
© 2004, HOÀNG MINH SƠN
Chương 4: Khái quát về cấutrúcdữ liệu
© 2005 - HMS
 Đ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ụ:
— Danh sách sinh viên: Các dữ 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

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ỏ
7
© 2004, HOÀNG MINH SƠN
Chương 4: Khái quát về cấutrúcdữ liệu
© 2005 - HMS
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
© 2005 - HMS
Các cấutrúcdữ liệu thông dụng (tiếp)

© 2004, HOÀNG MINH SƠN
Chương 4: Khái quát về cấutrúcdữ liệu
© 2005 - HMS
Mảng ₫ộng
 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
© 2005 - HMS
Cấpphátvàgiảiphóngbộ 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++:

Chương 4: Khái quát về cấutrúcdữ liệu
© 2005 - HMS
Cấpphátbộ nhớ₫ộng cho biến ₫ơn
 Ý nghĩa: Các ₫ốitượng có thể₫ượctạora₫ộng, trong khi
chương trình chạy(bổ sung sinh viên vào danh sách, vẽ thêm
mộthìnhtrongbảnvẽ, bổ sung mộtkhâutronghệ thống, )
 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
© 2005 - HMS
Ý 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

© 2005 - HMS
Tham số₫ầuralàcon trỏ?
void createDateList(int n, Date* &p) {
p = new Date[n];
}
void main() {
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;
}
17
© 2004, HOÀNG MINH SƠN
Chương 4: Khái quát về cấutrúcdữ liệu
© 2005 - HMS
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;

Chương 4: Khái quát về cấutrúcdữ liệu
© 2005 - HMS
Định nghĩacáchàmcơ bản
 Tên file: vector.cpp
#include <stdlib.h>
#include "vector.h"
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;
}
20
© 2004, HOÀNG MINH SƠN
Chương 4: Khái quát về cấutrúcdữ liệu
© 2005 - HMS
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) {

Chương 4: Khái quát về cấutrúcdữ liệu
© 2005 - HMS
 Vấn ₫ề: Xây dựng mộtcấutrúc₫ể quảnlýmộtcách
hiệuquả và linh hoạtcácdữ liệu ₫ộng, ví dụ:
—Hộpthư₫iệntử
— 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ớ
4.4 Xây dựng cấutrúcList
23
© 2004, HOÀNG MINH SƠN
Chương 4: Khái quát về cấutrúcdữ liệu
© 2005 - HMS
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

Dữ liệuY0x00
Dữ liệuC
pHead
Dữ liệuT
Dữ liệuA
Dữ liệuB
Dữ liệuX
Dữ liệuY0x00
Dữ liệuC
pHead
Dữ liệuT