![9
息2004,HONGMINHSN
Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u
4.2 M畉ng v qu畉n l箪 b畛 nh畛 畛ng
M畉ng cho ph辿p bi畛u di畛n v qu畉n l箪 d畛 li畛u m畛t c叩ch
kh叩 hi畛u qu畉:
畛c v ghi d畛 li畛u r畉t nhanh qua ch畛 s畛 ho畉c qua 畛a ch畛
Ti畉t ki畛m b畛 nh畛
C叩c v畉n 畛 c畛a m畉ng t挑nh:
VD: Student student_list[100];
S畛 ph畉n t畛 ph畉i l h畉ng s畛 (bi畉t tr動畛c khi bi棚n d畛ch, ng動畛i s畛
d畛ng kh担ng th畛 nh畉p s畛 ph畉n t畛, kh担ng th畛 cho s畛 ph畉n t畛
l m畛t bi畉n) => k辿m linh ho畉t
Chi畉m ch畛 c畛ng trong ngn x畉p (畛i v畛i bi畉n c畛c b畛) ho畉c
trong b畛 nh畛 d畛 li畛u ch動董ng tr狸nh (畛i v畛i bi畉n ton c畛c) =>
s畛 d畛ng b畛 nh畛 k辿m hi畛u qu畉, k辿m linh ho畉t](https://image.slidesharecdn.com/c4-datastructures-150428165620-conversion-gate01/85/C4-data-structures-9-320.jpg)
![10
息2004,HONGMINHSN
Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u
M畉ng 畛ng
M畉ng 畛ng l m畛t m畉ng 動畛c c畉p ph叩t b畛 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畉n l箪 m畉ng 畛ng: C叩ch s畛 d畛ng
kh担ng kh叩c so v畛i m畉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++](https://image.slidesharecdn.com/c4-datastructures-150428165620-conversion-gate01/85/C4-data-structures-10-320.jpg)
![11
息2004,HONGMINHSN
Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u
C畉p ph叩t v gi畉i ph坦ng b畛 nh畛 畛ng
C:
Hm malloc() y棚u c畉u tham s畛 l s畛 byte, tr畉 v畛 con tr畛
kh担ng ki畛u (void*) mang 畛a ch畛 v湛ng nh畛 m畛i 動畛c c畉p
ph叩t (n畉m trong heap), tr畉 v畛 0 n畉u kh担ng thnh c担ng.
Hm free() y棚u c畉u tham s畛 l con tr畛 kh担ng ki畛u (void*),
gi畉i ph坦ng v湛ng nh畛 c坦 畛a ch畛 動a vo
C++:
To叩n t畛 new ch畉p nh畉n ki畛u d畛 li畛u ph畉n t畛 k竪m theo s畛
l動畛ng ph畉n t畛 c畛a m畉ng c畉n c畉p ph叩t b畛 nh畛 (trong v湛ng
heap), tr畉 v畛 con tr畛 c坦 ki畛u, tr畉 v畛 0 n畉u kh担ng thnh c担ng.
To叩n t畛 delete[] y棚u c畉u tham s畛 l con tr畛 c坦 ki畛u.
To叩n t畛 new v delete c嘆n c坦 th畛 叩p d畛ng cho c畉p ph叩t v
gi畉i ph坦ng b畛 nh畛 cho m畛t bi畉n 董n, m畛t 畛i t動畛ng ch畛
kh担ng nh畉t thi畉t ph畉i m畛t m畉ng.](https://image.slidesharecdn.com/c4-datastructures-150428165620-conversion-gate01/85/C4-data-structures-11-320.jpg)
![12
息2004,HONGMINHSN
Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u
M畛t s畛 i畛u c畉n l動u 箪
Con tr畛 c坦 vai tr嘆 qu畉n l箪 m畉ng (畛ng), ch畛 con tr畛 kh担ng ph畉i
l m畉ng (畛ng)
C畉p ph叩t b畛 nh畛 v gi畉i ph坦ng b畛 nh畛 ch畛 kh担ng ph畉i c畉p ph叩t
con tr畛 v gi畉i ph坦ng con tr畛
Ch畛 gi畉i ph坦ng b畛 nh畛 m畛t l畉n
int* p;
p[0] = 1; // never do it
new(p); // access violation!
p = new int[100]; // OK
p[0] = 1; // OK
int* p2=p; // OK
delete[] p2; // OK
p[0] = 1; // access violation!
delete[] p; // very bad!
p = new int[50]; // OK, new array
...](https://image.slidesharecdn.com/c4-datastructures-150428165620-conversion-gate01/85/C4-data-structures-12-320.jpg)
![13
息2004,HONGMINHSN
Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u
C畉p ph叩t b畛 nh畛 畛ng cho bi畉n 董n
ngh挑a: C叩c 畛i t動畛ng c坦 th畛 動畛c t畉o ra 畛ng, trong khi
ch動董ng tr狸nh ch畉y (b畛 sung sinh vi棚n vo 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畛!](https://image.slidesharecdn.com/c4-datastructures-150428165620-conversion-gate01/85/C4-data-structures-13-320.jpg)
![15
息2004,HONGMINHSN
Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u
V鱈 d畛 s畛 d畛ng b畛 nh畛 畛ng trong hm
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;
}](https://image.slidesharecdn.com/c4-datastructures-150428165620-conversion-gate01/85/C4-data-structures-15-320.jpg)
![16
息2004,HONGMINHSN
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;
}](https://image.slidesharecdn.com/c4-datastructures-150428165620-conversion-gate01/85/C4-data-structures-16-320.jpg)
![17
息2004,HONGMINHSN
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 hm lu担n ph畉i 動a tham s畛 l s畛
chi畛u.
S畛 d畛ng kh担ng an ton: 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);](https://image.slidesharecdn.com/c4-datastructures-150428165620-conversion-gate01/85/C4-data-structures-17-320.jpg)
![19
息2004,HONGMINHSN
Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u
畛nh ngh挑a c叩c hm c董 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;
}](https://image.slidesharecdn.com/c4-datastructures-150428165620-conversion-gate01/85/C4-data-structures-19-320.jpg)
![20
息2004,HONGMINHSN
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;
}](https://image.slidesharecdn.com/c4-datastructures-150428165620-conversion-gate01/85/C4-data-structures-20-320.jpg)
C4 data structures
- 1. 息2004,HONGMINHSN Ch動董ng1 K畛 thu畉t l畉p tr狸nh 010101010101010110000101010101010101011000010101010101010101100001 010101010010101010010101010101001010101001010101010100101010100101 101001100011001001001010100110001100100100101010011000110010010010 110010110010001000001011001011001000100000101100101100100010000010 010101010101010110000101010101010101011000010101010101010101100001 010101010010101010010101010101001010101001010101010100101010100101 101001100011001001001010100110001100100100101010011000110010010010 110010110010001000001011001011001000100000101100101100100010000010 010101010101010110000101010101010101011000010101010101010101100001 010101010010101010010101010101001010101001010101010100101010100101 101001100011001001001010100110001100100100101010011000110010010010 110010110010001000001011001011001000100000101100101100100010000010 9/8/2006 y = A*x + B*u; x = C*x + d*u; StateController start() stop() LQGController start() stop() Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u
- 2. 2 息2004,HONGMINHSN Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u N畛i dung ch動董ng 4 4.1 C畉u tr炭c d畛 li畛u l g狸? 4.2 M畉ng v qu畉n l箪 b畛 nh畛 畛ng 4.2 X但y d畛ng c畉u tr炭c Vector 4.3 X但y d畛ng c畉u tr炭c List
- 3. 3 息2004,HONGMINHSN Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u 4.1 Gi畛i thi畛u chung Ph畉n l畛n c叩c bi to叩n trong th畛c t畉 li棚n quan t畛i c叩c d畛 li畛u ph畛c h畛p, nh畛ng ki畛u d畛 li畛u c董 b畉n trong ng担n ng畛 l畉p tr狸nh kh担ng 畛 bi畛u di畛n V鱈 d畛: D畛 li畛u sinh vi棚n: H畛 t棚n, ngy sinh, qu棚 qu叩n, m達 s畛 SV,... M担 h狸nh hm truy畛n: a th畛c t畛 s畛, a th畛c m畉u s畛 M担 h狸nh tr畉ng th叩i: C叩c ma tr畉n A, B, C, D D畛 li畛u qu叩 tr狸nh: T棚n 畉i l動畛ng, d畉i o, gi叩 tr畛, 董n v畛, th畛i gian, c畉p sai s畛, ng動畛ng gi叩 tr畛,... 畛i t動畛ng 畛 h畛a: K鱈ch th動畛c, mu s畉c, 動畛ng n辿t, ph担ng ch畛, ... Ph動董ng ph叩p bi畛u di畛n d畛 li畛u: 畛nh ngh挑a ki畛u d畛 li畛u m畛i s畛 d畛ng c畉u tr炭c (struct, class, union, ...)
- 4. 4 息2004,HONGMINHSN Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u V畉n 畛: Bi畛u di畛n t畉p h畛p d畛 li畛u a s畛 nh畛ng d畛 li畛u thu畛c m畛t 畛ng d畛ng c坦 li棚n quan v畛i nhau => c畉n bi畛u di畛n trong m畛t t畉p h畛p c坦 c畉u tr炭c, v鱈 d畛: Danh s叩ch sinh vi棚n: C叩c d畛 li畛u sinh vi棚n 動畛c s畉p x畉p theo th畛 t畛 Alphabet M畛 h狸nh t畛ng th畛 cho h畛 th畛ng i畛u khi畛n: Bao g畛m nhi畛u thnh ph畉n t動董ng t叩c D畛 li畛u qu叩 tr狸nh: M畛t t畉p d畛 li畛u c坦 th畛 mang gi叩 tr畛 c畛a m畛t 畉i l動畛ng vo c叩c th畛i i畛m gi叩n o畉n, c叩c d畛 li畛u 畉u vo li棚n quan t畛i d畛 li畛u 畉u ra 畛i t動畛ng 畛 h畛a: M畛t c畛a s畛 bao g畛m nhi畛u 畛i t動畛ng 畛 h畛a, m畛t b畉n v畉 c滴ng bao g畛m nhi畛u 畛i t動畛ng 畛 h畛a Th担ng th動畛ng, c叩c d畛 li畛u trong m畛t t畉p h畛p c坦 c湛ng ki畛u, ho畉c 鱈t ra l t動董ng th鱈ch ki畛u v畛i nhau Ki畛u m畉ng kh担ng ph畉i bao gi畛 c滴ng ph湛 h畛p!
- 5. 5 息2004,HONGMINHSN Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u V畉n 畛: Qu畉n l箪 (t畉p h畛p) d畛 li畛u S畛 d畛ng k畉t h畛p m畛t c叩ch kh辿o l辿o ki畛u c畉u tr炭c v ki畛u m畉ng 畛 畛 bi畛u di畛n c叩c t畉p h畛p d畛 li畛u b畉t k畛 C叩c gi畉i thu畉t (hm) thao t叩c v畛i d畛 li畛u, nh畉m qu畉n l箪 d畛 li畛u m畛t c叩ch hi畛u qu畉: B畛 sung m畛t m畛c d畛 li畛u m畛i vo m畛t danh s叩ch, m畛t b畉ng, m畛t t畉p h畛p, ... X坦a m畛t m畛c d畛 li畛u trong m畛t danh s叩ch, b畉ng, t畉p h畛p,.. T狸m m畛t m畛c d畛 li畛u trong m畛t danh s叩ch, b畉ng t畉p h畛p,... theo m畛t ti棚u chu畉n c畛 th畛 S畉p x畉p m畛t danh s叩ch theo m畛t ti棚u chu畉n no 坦 ....
- 6. 6 息2004,HONGMINHSN Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u Qu畉n l箪 DL th畉 no l hi畛u qu畉? Ti畉t ki畛m b畛 nh畛: Ph畉n "overhead" kh担ng 叩ng k畛 so v畛i ph畉n d畛 li畛u th畛c Truy nh畉p nhanh, thu畉n ti畛n: Th畛i gian c畉n cho b畛 sung, t狸m ki畉m v x坦a b畛 c叩c m畛c d畛 li畛u ph畉i ng畉n Linh ho畉t: S畛 l動畛ng c叩c m畛c d畛 li畛u kh担ng (ho畉c 鱈t) b畛 h畉n ch畉 c畛 畛nh, kh担ng c畉n bi畉t tr動畛c khi t畉o c畉u tr炭c, ph湛 h畛p v畛i c畉 bi to叩n nh畛 v l畛n Hi畛u qu畉 qu畉n l箪 d畛 li畛u ph畛 thu畛c vo C畉u tr炭c d畛 li畛u 動畛c s畛 d畛ng Gi畉i thu畉t 動畛c 叩p d畛ng cho b畛 sung, t狸m ki畉m, s畉p x畉p, x坦a b畛
- 7. 7 息2004,HONGMINHSN Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u C叩c c畉u tr炭c d畛 li畛u th担ng d畛ng M畉ng (ngh挑a r畛ng): T畉p h畛p c叩c d畛 li畛u c坦 th畛 truy nh畉p t湛y 箪 theo ch畛 s畛 Danh s叩ch (list): T畉p h畛p c叩c d畛 li畛u 動畛c m坦c n畛i 担i m畛t v畛i nhau v c坦 th畛 truy nh畉p tu畉n t畛 C但y (tree): T畉p h畛p c叩c d畛 li畛u 動畛c m坦c n畛i v畛i nhau theo c畉u tr炭c c但y, c坦 th畛 truy nh畉p tu畉n t畛 t畛 g畛c N畉u m畛i n炭t c坦 t畛i a hai nh叩nh: c但y nh畛 ph但n (binary tree) B狸a, b畉ng (map): T畉p h畛p c叩c d畛 li畛u c坦 s畉p x畉p, c坦 th畛 truy nh畉p r畉t nhanh theo m達 kh坦a (key) Hng 畛i (queue): T畉p h畛p c叩c d畛 li畛u c坦 s畉p x畉p tu畉n t畛, ch畛 b畛 sung vo t畛 m畛t 畉u v l畉y ra t畛 畉u c嘆n l畉i
- 8. 8 息2004,HONGMINHSN Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u C叩c c畉u tr炭c d畛 li畛u th担ng d畛ng (ti畉p) T畉p h畛p (set): T畉p h畛p c叩c d畛 li畛u 動畛c s畉p x畉p t湛y 箪 nh動ng c坦 th畛 truy nh畉p m畛t c叩ch hi畛u qu畉 Ngn x畉p (stack): T畉p h畛p c叩c d畛 li畛u 動畛c s畉p x畉p tu畉n t畛, ch畛 truy nh畉p 動畛c t畛 m畛t 畉u B畉ng hash (hash table): T畉p h畛p c叩c d畛 li畛u 動畛c s畉p x畉p d畛a theo m畛t m達 s畛 nguy棚n t畉o ra t畛 m畛t hm 畉c bi畛t B畛 nh畛 v嘆ng (ring buffer): T動董ng t畛 nh動 hng 畛i, nh動ng dung l動畛ng c坦 h畉n, n畉u h畉t ch畛 s畉 動畛c ghi quay v嘆ng Trong to叩n h畛c v trong i畛u khi畛n: vector, ma tr畉n, a th畛c, ph但n th畛c, hm truy畛n, ...
- 9. 9 息2004,HONGMINHSN Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u 4.2 M畉ng v qu畉n l箪 b畛 nh畛 畛ng M畉ng cho ph辿p bi畛u di畛n v qu畉n l箪 d畛 li畛u m畛t c叩ch kh叩 hi畛u qu畉: 畛c v ghi d畛 li畛u r畉t nhanh qua ch畛 s畛 ho畉c qua 畛a ch畛 Ti畉t ki畛m b畛 nh畛 C叩c v畉n 畛 c畛a m畉ng t挑nh: VD: Student student_list[100]; S畛 ph畉n t畛 ph畉i l h畉ng s畛 (bi畉t tr動畛c khi bi棚n d畛ch, ng動畛i s畛 d畛ng kh担ng th畛 nh畉p s畛 ph畉n t畛, kh担ng th畛 cho s畛 ph畉n t畛 l m畛t bi畉n) => k辿m linh ho畉t Chi畉m ch畛 c畛ng trong ngn x畉p (畛i v畛i bi畉n c畛c b畛) ho畉c trong b畛 nh畛 d畛 li畛u ch動董ng tr狸nh (畛i v畛i bi畉n ton c畛c) => s畛 d畛ng b畛 nh畛 k辿m hi畛u qu畉, k辿m linh ho畉t
- 10. 10 息2004,HONGMINHSN Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u M畉ng 畛ng M畉ng 畛ng l m畛t m畉ng 動畛c c畉p ph叩t b畛 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畉n l箪 m畉ng 畛ng: C叩ch s畛 d畛ng kh担ng kh叩c so v畛i m畉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. 11 息2004,HONGMINHSN Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u C畉p ph叩t v gi畉i ph坦ng b畛 nh畛 畛ng C: Hm malloc() y棚u c畉u tham s畛 l s畛 byte, tr畉 v畛 con tr畛 kh担ng ki畛u (void*) mang 畛a ch畛 v湛ng nh畛 m畛i 動畛c c畉p ph叩t (n畉m trong heap), tr畉 v畛 0 n畉u kh担ng thnh c担ng. Hm free() y棚u c畉u tham s畛 l con tr畛 kh担ng ki畛u (void*), gi畉i ph坦ng v湛ng nh畛 c坦 畛a ch畛 動a vo C++: To叩n t畛 new ch畉p nh畉n ki畛u d畛 li畛u ph畉n t畛 k竪m theo s畛 l動畛ng ph畉n t畛 c畛a m畉ng c畉n c畉p ph叩t b畛 nh畛 (trong v湛ng heap), tr畉 v畛 con tr畛 c坦 ki畛u, tr畉 v畛 0 n畉u kh担ng thnh c担ng. To叩n t畛 delete[] y棚u c畉u tham s畛 l con tr畛 c坦 ki畛u. To叩n t畛 new v delete c嘆n c坦 th畛 叩p d畛ng cho c畉p ph叩t v gi畉i ph坦ng b畛 nh畛 cho m畛t bi畉n 董n, m畛t 畛i t動畛ng ch畛 kh担ng nh畉t thi畉t ph畉i m畛t m畉ng.
- 12. 12 息2004,HONGMINHSN Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u M畛t s畛 i畛u c畉n l動u 箪 Con tr畛 c坦 vai tr嘆 qu畉n l箪 m畉ng (畛ng), ch畛 con tr畛 kh担ng ph畉i l m畉ng (畛ng) C畉p ph叩t b畛 nh畛 v gi畉i ph坦ng b畛 nh畛 ch畛 kh担ng ph畉i c畉p ph叩t con tr畛 v gi畉i ph坦ng con tr畛 Ch畛 gi畉i ph坦ng b畛 nh畛 m畛t l畉n int* p; p[0] = 1; // never do it new(p); // access violation! p = new int[100]; // OK p[0] = 1; // OK int* p2=p; // OK delete[] p2; // OK p[0] = 1; // access violation! delete[] p; // very bad! p = new int[50]; // OK, new array ...
- 13. 13 息2004,HONGMINHSN Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u C畉p ph叩t b畛 nh畛 畛ng cho bi畉n 董n ngh挑a: C叩c 畛i t動畛ng c坦 th畛 動畛c t畉o ra 畛ng, trong khi ch動董ng tr狸nh ch畉y (b畛 sung sinh vi棚n vo 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. 14 息2004,HONGMINHSN 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 vo 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 di h董n th畛i gian "s畛ng" c畛a th畛c th畛 c畉p ph叩t n坦. C坦 th畛 m畛t hm g畛i l畛nh c畉p ph叩t b畛 nh畛, nh動ng m畛t hm 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. 15 息2004,HONGMINHSN Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u V鱈 d畛 s畛 d畛ng b畛 nh畛 畛ng trong hm 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. 16 息2004,HONGMINHSN 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. 17 息2004,HONGMINHSN 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 hm lu担n ph畉i 動a tham s畛 l s畛 chi畛u. S畛 d畛ng kh担ng an ton: 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. 18 息2004,HONGMINHSN 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 hm 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. 19 息2004,HONGMINHSN Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u 畛nh ngh挑a c叩c hm c董 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. 20 息2004,HONGMINHSN 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. 21 息2004,HONGMINHSN 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. 22 息2004,HONGMINHSN 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 lm 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. 23 息2004,HONGMINHSN 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畛 vo 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 ton 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 ton b畛 ph畉n d畛 li畛u c嘆n l畉i => r畉t m畉t th畛i gian
- 24. 24 息2004,HONGMINHSN 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. 25 息2004,HONGMINHSN 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 vo gi畛a danh s叩chB畛 sung vo 畉u danh s叩ch
- 26. 26 息2004,HONGMINHSN 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. 27 息2004,HONGMINHSN 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 vo chi畛u di 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. 28 息2004,HONGMINHSN 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 <string> 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. 29 息2004,HONGMINHSN 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. 30 息2004,HONGMINHSN 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. 31 息2004,HONGMINHSN Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u Ch動董ng tr狸nh minh h畛a #include <iostream> #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 << pItem->subject << ":" << pItem->content << 'n'; pItem = pItem->pNext; } char c; cin >> c; removeAllMessages(myMailBox); }
- 32. 32 息2004,HONGMINHSN Ch動董ng 4: Kh叩i qu叩t v畛 c畉u tr炭c d畛 li畛u Bi t畉p v畛 nh X但y d畛ng ki畛u danh s叩ch m坦c n畛i ch畛a c叩c ngy l畛 trong nm v 箪 ngh挑a c畛a m畛i ngy (string), cho ph辿p: B畛 sung m畛t ngy l畛 vo 畉u danh s叩ch T狸m 箪 ngh挑a c畛a m畛t ngy (動a ngy th叩ng l tham s畛) X坦a b畛 i m畛t ngy l畛 畛 畉u danh s叩ch X坦a b畛 i m畛t ngy l畛 畛 gi畛a danh s叩ch (動a ngy th叩ng l tham s畛) X坦a b畛 i ton b畛 danh s叩ch Vi畉t ch動董ng tr狸nh minh h畛a c叩ch s畛 d畛ng