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

Nội dung text: Bài giảng Kỹ thuật lập trình - Chương 4: Khái quát về cấu trúc dữ liệu

1. 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. N Ơ —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ếtphảimộtmảng. 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 11 Ch ©
2. Mộtsố₫iềucầnlưuý ƒ Con trỏ có vai trò quảnlýmảng (₫ộng), chứ con trỏ không phải là mảng (₫ộng) ƒ Cấpphátbộ nhớ và giải phóng bộ nhớ chứ không phảicấpphát con trỏ và giải phóng con trỏ ƒ Chỉ giải phóng bộ nhớ mộtlầ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 N Ơ p[0] = 1; // access violation! delete[] p; // very bad! p = new int[50]; // OK, new array 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 12 Ch ©
3. 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; N Student* ps = new Student; Ơ ps->code = 1000; delete ps; ƒ Mộtbiến ₫ơn khác vớimảng mộtphầntử! 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 13 Ch ©
4. Ý 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 N Ơ khác giải phóng bộ nhớ. —Sự linh hoạtcũng dễ dẫn ₫ếnnhững lỗi"ròrỉ bộ nhớ". 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 14 Ch ©
5. 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 > n; Date* date_list = createDateList(n); for (int i=0; i < n; ++i) { N } Ơ for ( ) { cout << } delete [] date_list; } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 15 Ch ©
6. Tham số₫ầuralàcon trỏ? void createDateList(int n, Date* p) { p = new Date[n]; } void main() { int n; cout > n; Date* date_list; createDateList(n, date_list); for (int i=0; i < n; ++i) { N } Ơ for ( ) { cout << } delete [] date_list; } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 16 Ch ©
7. 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)); N Ơ d = scalarProd(v1,v2,n); // scalar_prod đãcó d = v1 * v2; // OOPS! v1.data[10] = 0; // OOPS! free(v1); free(v2); 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 17 Ch ©
8. Định nghĩacấutrúcVector ƒ Tên file: vector.h ƒ Cấutrúcdữ 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); N Vector addVector(Vector, Vector); Ơ Vector subVector(Vector, Vector); double scalarProd(Vector, Vector); 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 18 Ch ©
9. Định nghĩacáchàmcơ 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); }N doubleƠ getElem(Vector v, int i) { if (i = 0) return v.data[i]; return 0; } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 19 Ch ©
10. 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) { N Vector c = {0,0}; Ơ return c; } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 20 Ch ©
11. 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); N Ơ destroyVector(b); destroyVector(c); } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 21 Ch ©
12. 4.4 Xây dựng cấutrúcList ƒ 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 N Ơ 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ớ 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 22 Ch ©
13. 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 Ơ ƒ 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 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 23 Ch ©
14. Danh sách móc nối (linked list) pHead Item A Dữ liệuA Item B Dữ liệuB Item C Dữ liệuC Item X Dữ liệuX N Ơ Item Y 0x00 Dữ liệuY 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 24 Ch ©
15. Bổ sung dữ liệu pHead pHead pHead Dữ liệuT Dữ liệuA Dữ liệuA Dữ liệuB Dữ liệuB Dữ liệuT Dữ liệuC Dữ liệuC N Dữ liệuX Dữ liệuX Ơ 0x00 Dữ liệuY 0x00 Dữ liệuY Bổ sung vào ₫ầudanhsách Bổ sung vào giữa danh sách 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 25 Ch ©
16. Xóa bớtdữ liệu pHead pHead Dữ liệuA Dữ liệuA Dữ liệuB Dữ liệuB Dữ liệuC Dữ liệuC Dữ liệuX Dữ liệuX N Ơ 0x00 Dữ liệuY 0x00 Dữ liệuY Xóa dữ liệu ₫ầudanhsách Xóa dữ liệugiữadanhsách 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 26 Ch ©
17. Các ₫ặc ₫iểm chính ƒ Ưu ₫iểm: —Sử dụng rấtlinhhoạt, cấpphátbộ nhớ khi cần và xóa khi không cần —Bổ sung và xóa bỏ mộtdữ liệu ₫ượcthựchiện thông qua chuyểncon trỏ, thờigianthựchiệnlàhằng số, không phụ thuộcvàochiều dài và vị trí —Cóthể truy nhậpvàduyệtcácphầntử theo kiểutuầntự ƒ Nhược ₫iểm: —Mỗidữ liệubổ sung mới ₫ềuphải ₫ượccấpphátbộ nhớ₫ộng —Mỗidữ liệuxóabỏ₫i ₫ềuphải ₫ượcgiải phóng bộ nhớ tương N Ơ ứng —Nếukiểudữ liệu không lớnthìphần overhead chiếmtỉ lệ lớn —Tìmkiếmdữ liệutheokiểutuyến tính, mấtthờigian 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 27 Ch ©
18. Ví dụ: Danh sách thông báo (hộpthư) #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, N Ơ const string& ct); bool removeMessageBySubject(MessageList& l, const string& sj); void removeAllMessages(MessageList&); 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 28 Ch ©
19. #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; N Ơ delete pItem; pItem = pItemNext; } l.pHead = 0; } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 29 Ch ©
20. 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; } N Ơ return pItem != 0; } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 30 Ch ©
21. 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 pNext; N Ơ } char c; cin >> c; removeAllMessages(myMailBox); } 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 31 Ch ©
22. Bài tậpvề nhà ƒ Xây dựng kiểu danh sách móc nốichứacácngàylễ trong nămvàý nghĩacủamỗi ngày (string), cho phép: —Bổ sung mộtngàylễ vào ₫ầudanhsách —Tìmý nghĩacủamộtngày(₫ưa ngày tháng là tham số) —Xóabỏ₫imộtngàylễở₫ầu danh sách —Xóabỏ₫imộtngàylễởgiữadanhsách(₫ưa ngày tháng là tham số) —Xóabỏ₫itoànbộ danh sách ƒ Viếtchương trình minh họacáchsử dụng N Ơ 2004, HOÀNG MINH S ương 4: Khái quát về cấutrúcdữ liệu 32 Ch ©