Kỹ thuật lập trình - Chương 4: Khái quát về cấu trúc dữ liệu

ượng có thể ₫ược tạo ra ₫ộng, trong khi
chương trình chạy (bổ sung sinh viên vào danh sách, vẽ thêm
một hình trong bản vẽ, bổ sung một khâu trong hệ 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ột biến ₫ơn khác với mảng một phần tử!
14
©
2
0
0
4
,
H
O
À
N
G
M
I
N
H
S
Ơ
N
Chương 4: Khái quát về cấu trúc dữ liệu
Ý nghĩa của sử dụng bộ nhớ ₫ộng
ƒ Hiệu suất:
— Bộ nhớ ₫ược cấp phát ₫ủ dung lượng theo yêu cầu và khi
₫ược yêu cầu trong khi chương trình ₫ã chạy
— Bộ nhớ ₫ược cấp phát nằm trong vùng nhớ tự do còn lại củ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ể ₫ược giải phóng khi không sử dụng tiếp.
ƒ Linh hoạt:
— Thời gian "sống" của bộ nhớ ₫ược cấp phát ₫ộng có thể kéo
dài hơn thời gian "sống" của thực thể cấp phát nó.
— Có thể một hàm gọi lệnh cấp phát bộ nhớ, nhưng một hàm
khác giải phóng bộ nhớ.
— Sự linh hoạt cũng dễ dẫn ₫ến những lỗi "rò rỉ bộ nhớ".
15
©
2
0
0
4
,
H
O
À
N
G
M
I
N
H
S
Ơ
N
Chương 4: Khái quát về cấu trúc dữ liệu
Ví dụ sử dụng bộ nhớ ₫ộng trong hàm
Date* createDateList(int n) {
Date* p = new Date[n];
return p;
}
void main() {
int n;
cout << "Enter the number of your national holidays:";
cin >> n;
Date* date_list = createDateList(n);
for (int i=0; i < n; ++i) {
...
}
for (....) { cout << ....}
delete [] date_list;
}
16
©
2
0
0
4
,
H
O
À
N
G
M
I
N
H
S
Ơ
N
Chương 4: Khái quát về cấu trúc dữ liệu
Tham số ₫ầu ra là 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
©
2
0
0
4
,
H
O
À
N
G
M
I
N
H
S
Ơ
N
Chương 4: Khái quát về cấu trúc dữ liệu
4.3 Xây dựng cấu trúc Vector
ƒ Vấn ₫ề: Biểu diễn một vector toán học trong C/C++?
ƒ Giải pháp chân phương: mảng ₫ộng thông thường, nhưng...
— Sử dụng không thuận tiện: Người sử dụng tự gọi các lệnh cấp phát
và giải phóng bộ nhớ, trong các hàm luôn phải ₫ưa tham số là số
chiều.
— Sử dụng không an toàn: Nhầm lẫn nhỏ dẫn ₫ến hậu quả 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
©
2
0
0
4
,
H
O
À
N
G
M
I
N
H
S
Ơ
N
Chương 4: Khái quát về cấu trúc dữ liệu
Định nghĩa cấu trúc Vector
ƒ Tên file: vector.h
ƒ Cấu trúc dữ liệu:
struct Vector {
double *data;
int nelem;
};
ƒ Khai báo các hàm cơ bản:
Vector createVector(int n, double init);
void destroyVector(Vector);
double getElem(Vector, int i);
void putElem(Vector, int i, double d);
Vector addVector(Vector, Vector);
Vector subVector(Vector, Vector);
double scalarProd(Vector, Vector);
...
19
©
2
0
0
4
,
H
O
À
N
G
M
I
N
H
S
Ơ
N
Chương 4: Khái quát về cấu trúc dữ liệu
Định nghĩa các hàm cơ bản
ƒ Tên file: vector.cpp
#include 
#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 = 0) return v.data[i]; 
return 0;
}
20
©
2
0
0
4
,
H
O
À
N
G
M
I
N
H
S
Ơ
N
Chương 4: Khái quát về cấu trúc dữ 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
©
2
0
0
4
,
H
O
À
N
G
M
I
N
H
S
Ơ
N
Chương 4: Khái quát về cấu trúc dữ liệu
Ví dụ sử dụng
#include "vector.h"
void main() {
int n = 10;
Vector a,b,c;
a = createVector(10,1.0);
b = createVector(10,2.0);
c = addVector(a,b);
//...
destroyVector(a);
destroyVector(b);
destroyVector(c);
}
22
©
2
0
0
4
,
H
O
À
N
G
M
I
N
H
S
Ơ
N
Chương 4: Khái quát về cấu trúc dữ liệu
4.4 Xây dựng cấu trúc List
ƒ Vấn ₫ề: Xây dựng một cấu trúc ₫ể quản lý một cách
hiệu quả và linh hoạt các dữ liệu ₫ộng, ví dụ:
— Hộp thư ₫iện tử
— Danh sách những việc cần làm
— Các ₫ối tượng ₫ồ họa trên hình vẽ
— Các khâu ₫ộng học trong sơ ₫ồ mô phỏng hệ thống (tương tự
trong SIMULINK)
ƒ Các yêu cầu ₫ặc thù:
— Số lượng mục dữ liệu trong danh sách có thể thay ₫ổi thường
xuyên
— Các thao tác bổ sung hoặc xóa dữ liệu cần ₫ược thực hiện
nhanh, ₫ơn giản
— Sử dụng tiết kiệm bộ nhớ
23
©
2
0
0
4
,
H
O
À
N
G
M
I
N
H
S
Ơ
N
Chương 4: Khái quát về cấu trúc dữ liệu
Sử dụng kiểu mảng?
ƒ Số phần tử trong một mảng thực chất không bao giờ
thay ₫ổi ₫ược. Dung lượng bộ nhớ vào thời ₫iểm cấp
phát phải biết trước, không thực sự co giãn ₫ược.
ƒ Nếu không thực sự sử dụng hết dung lượng ₫ã cấp
phát => lãng phí bộ nhớ
ƒ Nếu ₫ã sử dụng hết dung lượng và muốn bổ sung 
phần tử thì phải cấp phát lại và sao chép toàn bộ dữ
liệu sang mảng mới => cần nhiều thời gian nếu số
phần tử lớn
ƒ Nếu muốn chèn một phần tử/xóa một phần tử ở ₫ầu
hoặc giữa mảng thì phải sao chép và dịch toàn bộ
phần dữ liệu còn lại => rất mất thời gian
24
©
2
0
0
4
,
H
O
À
N
G
M
I
N
H
S
Ơ
N
Chương 4: Khái quát về cấu trúc dữ liệu
Danh sách móc nối (linked list)
Dữ liệu A
Dữ liệu B
Dữ liệu X
Dữ liệu Y0x00
Dữ liệu C
pHead
Item A
Item B
Item C
Item X
Item Y
25
©
2
0
0
4
,
H
O
À
N
G
M
I
N
H
S
Ơ
N
Chương 4: Khái quát về cấu trúc dữ liệu
Bổ sung dữ liệu
Dữ liệu A
Dữ liệu B
Dữ liệu X
Dữ liệu Y0x00
Dữ liệu C
pHead
Dữ liệu T
pHead
Dữ liệu A
Dữ liệu B
Dữ liệu X
Dữ liệu Y0x00
Dữ liệu C
pHead Dữ liệu T
Bổ sung vào giữa danh sáchBổ sung vào ₫ầu danh sách
26
©
2
0
0
4
,
H
O
À
N
G
M
I
N
H
S
Ơ
N
Chương 4: Khái quát về cấu trúc dữ liệu
Xóa bớt dữ liệu
Dữ liệu A
Dữ liệu B
Dữ liệu X
Dữ liệu Y0x00
Dữ liệu C
pHead
Dữ liệu A
Dữ liệu B
Xóa dữ liệu ₫ầu danh sách
Dữ liệu C
Dữ liệu X
Dữ liệu Y0x00
pHead
Xóa dữ liệu giữa danh sách
27
©
2
0
0
4
,
H
O
À
N
G
M
I
N
H
S
Ơ
N
Chương 4: Khái quát về cấu trúc dữ liệu
Các ₫ặc ₫iểm chính
ƒ Ưu ₫iểm:
— Sử dụng rất linh hoạt, cấp phát bộ nhớ khi cần và xóa khi
không cần
— Bổ sung và xóa bỏ một dữ liệu ₫ược thực hiện thông qua 
chuyển con trỏ, thời gian thực hiện là hằng số, không phụ
thuộc vào chiều dài và vị trí
— Có thể truy nhập và duyệt các phần tử theo kiểu tuần tự
ƒ Nhược ₫iểm:
— Mỗi dữ liệu bổ sung mới ₫ều phải ₫ược cấp phát bộ nhớ ₫ộng
— Mỗi dữ liệu xóa bỏ ₫i ₫ều phải ₫ược giải phóng bộ nhớ tương
ứng
— Nếu kiểu dữ liệu không lớn thì phần overhead chiếm tỉ lệ lớn
— Tìm kiếm dữ liệu theo kiểu tuyến tính, mất thời gian
28
©
2
0
0
4
,
H
O
À
N
G
M
I
N
H
S
Ơ
N
Chương 4: Khái quát về cấu trúc dữ liệu
Ví dụ: Danh sách thông báo (hộp thư)
#include 
using namespace std;
struct MessageItem {
string subject;
string content;
MessageItem* pNext;
};
struct MessageList {
MessageItem* pHead;
};
void initMessageList(MessageList& l);
void addMessage(MessageList&, const string& sj, 
const string& ct);
bool removeMessageBySubject(MessageList& l, 
const string& sj);
void removeAllMessages(MessageList&);
29
©
2
0
0
4
,
H
O
À
N
G
M
I
N
H
S
Ơ
N
Chương 4: Khái quát về cấu trúc dữ liệu
#include "List.h"
void initMessageList(MessageList& l) {
l.pHead = 0;
}
void addMessage(MessageList& l, const string& sj, 
const string& ct) {
MessageItem* pItem = new MessageItem;
pItem->content = ct;
pItem->subject = sj;
pItem->pNext = l.pHead;
l.pHead = pItem;
}
void removeAllMessages(MessageList& l) {
MessageItem *pItem = l.pHead;
while (pItem != 0) {
MessageItem* pItemNext = pItem->pNext;
delete pItem;
pItem = pItemNext;
}
l.pHead = 0;
}
30
©
2
0
0
4
,
H
O
À
N
G
M
I
N
H
S
Ơ
N
Chương 4: Khái quát về cấu trúc dữ liệu
bool removeMessageBySubject(MessageList& l, 
const string& sj) {
MessageItem* pItem = l.pHead;
MessageItem* pItemBefore;
while (pItem != 0 && pItem->subject != sj) {
pItemBefore = pItem;
pItem = pItem->pNext;
}
if (pItem != 0) {
if (pItem == l.pHead)
l.pHead = 0;
else
pItemBefore->pNext = pItem->pNext;
delete pItem;
}
return pItem != 0;
}
31
©
2
0
0
4
,
H
O
À
N
G
M
I
N
H
S
Ơ
N
Chương 4: Khái quát về cấu trúc dữ liệu
Chương trình minh họa
#include 
#include "list.h"
using namespace std;
void main() {
MessageList myMailBox;
initMessageList(myMailBox);
addMessage(myMailBox,"Hi","Welcome, my friend!");
addMessage(myMailBox,"Test","Test my mailbox");
addMessage(myMailBox,"Lecture Notes","Programming Techniques");
removeMessageBySubject(myMailBox,"Test");
MessageItem* pItem = myMailBox.pHead;
while (pItem != 0) {
cout subject content << '\n';
pItem = pItem->pNext;
}
char c;
cin >> c;
removeAllMessages(myMailBox);
}
32
©
2
0
0
4
,
H
O
À
N
G
M
I
N
H
S
Ơ
N
Chương 4: Khái quát về cấu trúc dữ liệu
Bài tập về nhà
ƒ Xây dựng kiểu danh sách móc nối chứa các ngày lễ
trong năm và ý nghĩa của mỗi ngày (string), cho
phép:
— Bổ sung một ngày lễ vào ₫ầu danh sách
— Tìm ý nghĩa của một ngày (₫ưa ngày tháng là tham số)
— Xóa bỏ ₫i một ngày lễ ở ₫ầu danh sách
— Xóa bỏ ₫i một ngày lễ ở giữa danh sách (₫ưa ngày tháng là
tham số)
— Xóa bỏ ₫i toàn bộ danh sách
ƒ Viết chương trình minh họa cách sử dụng