Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 2: Kiểu dữ liệu danh sách - Lê Sỹ Vinh

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 2: Kiểu dữ liệu danh sách - Lê Sỹ Vinh

1. Kiu d liu danh sỏch Lờ S Vinh B mụn Khoa Hc Mỏy Tớnh – Khoa CNTT ði Hc Cụng Ngh ðHQGHN Email: vinhioi@yahoo.com
2. Danh sỏch Danh sỏch là gỡ? Danh sỏch là cu trỳc d liu tuyn tớnh, trong ủú cỏc phn t d liu ủưc sp xp theo mt th t xỏc ủnh Vớ d: – Danh sỏch sinh viờn – Danh sỏch ủin thoi – Danh sỏch mụn hc – Danh sỏch bài hỏt – Danh sỏch cụng vic
3. Danh sỏch Tru tưng húa cu trỳc danh sỏch 1. Mụ t d liu A = ( a0, a 1, , a n) trong ủú ai là phn t th i ca danh sỏch A Vớ d: A = (1, 2, 3, 3, 4, 5) A = (‘Vinh’, ‘Tun’,. ‘Ánh’) 2. Mụ t cỏc phộp toỏn trờn cu trỳc danh sỏch • empty (A): Kim tra danh sỏch cú rng hay khụng • length (A): Cho bit s phn t ca danh sỏch • element (A, i ) : Tr phn t v trớ th i ca A. Vớ d: A =(1,3,5) Element ( A, 0) → 1 Element (A, 2) → 5
4. Danh sỏch • insert (A, i, x ): Thờm phn t x vào danh sỏch A ti v trớ i. A = (a 0, a 1, , a n) → A = (a 0,a 1, ,a i1, x, a i, a n) Vớ d: A = (1,3,5) insert ( A, 1, 4) → A = (1, 4, 3, 5) • append (A, x ): Thờm x vào ủuụi danh sỏch A A = (a 0, a 1, , a n) → A = (a 0,a 1, ,a n , x) Vớ d: A = (1,3,5) append ( A, 8) → A = (1, 3, 5, 8) • delete (A, i ): Loi phn t v trớ th i trong danh sỏch A A = (a 0, a 1, a i1, a i, a i+1 , a n) → A = (a 0,a 1, ,a i1, a i+1 , a n) Vớ d: A = (1,3,5) delete ( A, 1) → A = (1, 5)
5. Cài ủt danh sỏch bng mng Mng (array) • Tp hp cỏc phn t (cỏc bin) cú cựng mt kiu • Mt phn t c th trong mng s ủưc xỏc ủnh và truy cp bi mt ch s • Trong C/C++, cỏc phn t ca mng ủưc ủt cnh nhau to thành mt khi liờn tc. ða ch thp nht tương ng vi phn t ủu tiờn, ủa ch cao nht tương ng vi phn t cui cựng • Mng thỡ cú th là mt chiu hoc nhiu chiu
6. Cài ủt danh sỏch bng mng a . . . an a0 1 ↑ ↑ ↑ ↑ 0 1 N Max 1 Mng mt chiu: dataType arrayName [Max]; Vớ d: int scoreArr[100]; student studentArr[100];
7. Danh sỏch Túm tt v tru tưng húa cu trỳc danh sỏch • Mụ t d liu • A = ( a0, a 1, , a n) • Mụ t cỏc phộp toỏn trờn cu trỳc danh sỏch • empty (A): Kim tra danh sỏch cú rng hay khụng • length (A): Cho bit s phn t ca danh sỏch • element (A, i ) : Tr phn t v trớ th i ca A. • insert (A, i, x ): Thờm phn t x vào danh sỏch A ti v trớ i. • append (A, x ): Thờm x vào ủuụi danh sỏch A • delete (A, i ): Loi phn t v trớ th i trong danh sỏch A Cỏc phộp toỏn trờn cu trỳc danh sỏch khụng ph thuc vào kiu d liu ca cỏc phn t trong danh sỏch!!!
8. Cài ủt danh sỏch trong C++ Template 1. Generic function 2. Generic class ListArr project List.h List.cpp
9. Cỏc phộp toỏn khỏc trờn danh sỏch • Tỡm phn t ln nht • ði ch hai phn t • Sp xp tăng dn
10. Con tr (pointer) • Là ủim mnh nht, nhưng cũng nguy him nht ca C/ C++ • Cha ủa ch ca mt t bào nh trong mỏy tớnh 1 2 3 1 4 6 5 Giỏ tr trong ụ nh 3 ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ða ch ụ nh 10 11 12 13 14 15 16 17
11. Con tr (pointer) Khai bỏo con tr type * pointerVariable vớ d: int *p Cp phỏt b nh (allocate memory) pointerVariable = new type (initializer) Vớ d: p = new int (1) Gii phúng b nh delete pointerVariable; vớ d: delete p (xem vớ d chương trỡnh)
12. Con tr (pointer) Cp phỏt b nh cho mt ủi tưng d liu pointerVariable = new objectDataType (xem vớ d chương trỡnh)
13. Con tr (pointer) Cp phỏt mng ủng pointerVariable = new arrayType[size] vớ d: int* p; p = new int[10] Gii phúng mng ủng delete [] pointerVariable vớ d: delete [] p; (xem vớ d chương trỡnh)
14. Danh sỏch liờn kt Mng -1 1 3 2 ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 11 12 13 14 15 16 17 18 19 20 21 22 int listArr[4] = {-1, 1, 3, 2} Danh sỏch -1 1 3 2 liờn kt ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 11 12 13 14 15 16 17 18 19 20 21 22 (-1, 15 ) → (1, 16 ) → (3, 21 ) → (2, NULL ) ↑ ↑ head tail
15. Cài ủt danh sỏch liờn kt Xem chương trỡnh
16. Cỏc phộp toỏn khỏc trờn danh sỏch liờn kt • Tỡm phn t ln nht • ði ch hai phn t • Sp xp tăng dn
17. Mng và danh sỏch liờn kt • Truy cp phn t • Thờm phn t • Xúa phn t