Cấu trúc dữ liệu động máy tính

Chia sẻ: Lan Lan | Ngày: | Loại File: PDF | Số trang:210

Thêm vào BST

Báo xấu

102
lượt xem 27
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong khoa học máy tính, cấu trúc dữ liệu là một cách lưu dữ liệu trong máy tính sao cho nó có thể được sử dụng một cách hiệu quả Trong thiết kế nhiều loại chương trình, việc chọn cấu trúc dữ liệu là vấn đề quan trọng. Kinh nghiệm trong việc xây dựng các hệ thóng lớn cho thấy khó khăn của việc triển khai chương trình, chất lượng và hiệu năng của kết quả cuối cùng phụ thuộc rất nhiều....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Cấu trúc dữ liệu động máy tính

Caáu truùc döõ lieäu ñoäng Ca
Muïc tieâu Giôùi thieäu khaùi nieäm caáu truùc döõ lieäu ñoäng. Giô ng. Giôùi thieäu danh saùch lieân keát: Giô ch t: Caùc kieåu toå chöùc döõ lieäu theo DSLK. Ca Danh saùch lieân keát ñôn: toå chöùc, caùc thuaät toaùn, öùng Danh ch c, öù duïng. du ng. Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 2
Kieåu döõ lieäu tónh Khaùi nieäm: Moät soá ñoái töôïng döõ lieäu khoâng thay thay ñoåi Kha m: ng khoâ ñöôïc kích thöôùc, caáu truùc, … trong suoát qua trình soáng. ñö c, Caùc ñoái töôïng döõ lieäu thuoäc nhöõng kieåu döõ lieäu goïi laø Ca ng kieåu döõ lieäu lieäu tónh. nh. Moät soá kieåu döõ lieäu tónh: caùc caáu truùc döõ lieäu ñöôïc xaây Mo ñö xaâ döïng töø caùc kieåu cô sôû nhö: kieåu thöïc, kieåu nguyeân, kieåu ng c, kyù töï ... hoaëc töø caùc caáu truùc ñôn giaûn nhö maåu tin, taäp ky hôïp, maûng ... hô p, ng Caùc ñoái töôïng döõ lieäu ñöôïc xaùc ñònh thuoäc nhöõng kieåu Ca ng ñö döõ lieäu naøy thöôøng cöùng ngaét, goø boù khoù dieãn taû ñöôïc ng ng t, kho thöïc teá voán sinh ñoäng, phong phuù. th sinh ng, Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 3
Ví duï thöïc teá Moâ taû, quaûn lyù moät ñoái töôïng ‘con ngöôøi’ caàn theå hieän Moâ caùc thoâng tin toái thieåu nhö : ca Hoï teân Ho Soá CMND So Thoâng tin veà cha, meï Thoâ Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 4
Ví duï thöïc teá Vieäc bieãu dieãn moät ñoái töôïng coù nhieàu thaønh phaàn thoâng Vie ng nh thoâ tin nhö treân coù theå söû duïng kieåu baûn ghi. Tuy nhieân, caàn tin ng löu yù cha, meï cuûa moät ngöôøi cuõng laø caùc ñoái töôïng kieåu ng NGUOI, do vaäy veà nguyeân taéc caàn phaûi coù ñònh nghóa NGUOI, nhö sau: nh sau: typedef struct NGUOI{ char Hoten[30]; int So_CMND ; NGUOI Cha,Me; }; Nhöng vôùi khai baùo treân, caùc ngoân ngöõ laäp trình gaëp khoù Nh khaên trong vieäc caøi ñaët khoâng vöôït qua ñöôïc nhö xaùc qua ñö ñònh kích thöôùc cuûa ñoái töôïng kieåu NGUOI ? ng NGUOI Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 5
CTDL tónh – Moät soá haïn cheá nh Moät soá ñoái töôïng döõ lieäu trong chu kyø soáng cuûa noù coù theå Mo ng ng thay ñoåi veà caáu truùc, ñoä lôùn, nhö danh saùch caùc hoïc vieân thay n, ch vieâ trong moät lôùp hoïc coù theå taêng theâm, giaûm ñi ... Neáu duøng trong nhöõng caáu truùc döõ lieäu tónh ñaõ bieát nhö maûng ñeå bieåu nh nh dieãn Nhöõng thao taùc phöùc taïp, keùm töï nhieân Nh p, nhieâ chöông trình khoù ñoïc, khoù baûo trì vaø nhaát laø khoù coù theå ch c, söû duïng boä nhôù moät caùch coù hieäu quaû. ng ch Döõ lieäu tónh seõ chieám vuøng nhôù ñaõ daønh cho chuùng suoát ng nh ng quaù trình hoaït ñoäng cuûa chöông trình söû duïng boä nhôù qua ng nh ng keùm hieäu quaû. Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 6
Höôùng giaûi quyeát ng Caàn xaây döïng caáu truùc döõ lieäu ñaùp öùùng ñöôïc caùc yeâu Ca ng ö ñö yeâ caàu: ca u: Linh ñoäng hôn. Linh ng Coù theå thay ñoåi kích thöôùc, caáu truùc trong suoát thôøi Co c, gian soáng. gian ng. Caáu truùc döõ lieäu ñoäng. Ca ng. Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 7
Kieåu döõ lieäu Kie Con troû Con
Bieán khoâng ñoäng khoâ Bieán khoâng ñoäng (bieán tónh, bieán nöûa tónh) laø nhöõng bieán thoûa: Bie khoâ ng Ñöôïc khai baùo töôøng minh, Ñö ng Toàn taïi khi vaøo phaïm vi khai baùo vaø chæ maát khi ra khoûi To phaïm vi naøy, pha y, Ñöôïc caáp phaùt vuøng nhôù trong vuøng döõ lieäu (Data segment) Ñö ng ng (Data hoaëc laø Stack (ñoái vôùi bieán nöûa tónh - caùc bieán cuïc boä). hoa nh ). Kích thöôùc khoâng thay ñoåi trong suoát quaù trình soáng. khoâ ng. Do ñöôïc khai baùo töôøng minh, caùc bieán khoâng ñoäng coù moät Do ng khoâ ng ñònh danh ñaõ ñöôïc keát noái vôùi ñòa chæ vuøng nhôù löu tröõ bieán ònh aõ ñö ng vaø ñöôïc truy xuaát tröïc tieáp thoâng qua ñònh danh ñoù. va thoâ ònh Ví duï : // a, b laø caùc bieán khoâng ñoäng int a; char b[10]; Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 9
Kieåu döõ lieäu Con troû Cho tröôùc kieåu döõ lieäu T = . Cho
Kieåu döõ lieäu Con troû Kieåu con troû laø kieåu cô sôû duøng löu ñòa chæ cuûa moät ñoái Kie ng töôïng döõ lieäu khaùc. ng c. Bieán thuoäc kieåu con troû Tp laø bieán maø giaù trò cuûa noù laø Bie ñòa chæ cuaû moät vuøng nhôù öùng vôùi moät bieán kieåu T, hoaëc ng ng laø giaù trò NULL. la trò NULL Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 11
Kieåu döõ lieäu Con troû Kích thöôùc cuûa bieán con troû tuøy thuoäc vaøo quy öôùc soá quy byte ñòa chæ trong töøng moâ hình boä nhôù cuûa töøng ngoân byte ng ngöõ laäp trình cuï theå. ng Ví duï: Bieán con troû trong Pascal coù kích thöôùc 4 bytes (2 Bie bytes bytes ñòa chæ segment + 2 byte ñòa chæ offset) segment Bieán con troû trong C coù kích thöôùc 2 hoaëc 4 bytes tuøy Bie vaøo con troû near (chæ löu ñòa chæ offset) hay far (löu caû va segment laãn offset) Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 12
Con troû – Khai baùo Cuù phaùp ñònh nghóa moät kieåu con troû trong ngoân ngöõ C : Cu typedef * < kieåu con troû>; Ví duï : typedef int *intpointer; intpointer p; hoaëc int *p; laø nhöõng khai baùo hôïp leä. Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 13
Con troû – Thao taùc caên baûn Caùc thao taùc cô baûn treân kieåu con troû:(minh hoïa baèng C) Ca :(minh ng Khi 1 bieán con troû p löu ñòa chæ cuûa ñoái töôïng x, ta noùi Khi ng ‘p troû ñeán x’. Gaùn ñòa chæ cuûa moät vuøng nhôù con troû p: Ga ng p = ; p = + ; Truy xuaát noäi dung cuûa ñoái töôïng do p troû ñeán (*p) Truy ng Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 14
Bieán ñoäng Trong nhieàu tröôøng hôïp, taïi thôøi ñieåm bieân dòch khoâng Trong ng p, bieâ theå xaùc ñònh tröôùc kích thöôùc chính xaùc cuûa moät soá ñoái the töôïng döõ lieäu do söï toàn taïi vaø taêng tröôûng cuûa chuùng phuï ng ng ng thuoäc vaøo ngöõ caûnh cuûa vieäc thöïc hieän chöông trình. nh nh. Caùc ñoái töôïng döõ lieäu coù ñaëc ñieåm keå treân neân ñöôïc khai Ca ng treâ ñö khai baùo nhö bieán ñoäng. Bieán ñoäng laø nhöõng bieán thoûa: ba ng. ng a: Bieán khoâng ñöôïc khai baùo töôøng minh. Bie ng Coù theå ñöôïc caáp phaùt hoaëc giaûi phoùng boä nhôù khi Co ng khi ngöôøi söû duïng yeâu caàu. ng ng Caùc bieán naøy khoâng theo qui taéc phaïm vi (tónh). Ca Vuøng nhôù cuûa bieán ñöôïc caáp phaùt trong Heap. Vu ng Kích thöôùc coù theå thay ñoåi trong quaù trình soáng. thay ng. Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 15
Bieán ñoäng ng Do khoâng ñöôïc khai baùo töôøng minh neân caùc bieán ñoäng Do ng ng khoâng coù moät ñònh danh ñöôïc keát buoäc vôùi ñòa chæ vuøng ng nhôù caáp phaùt cho noù, do ñoù gaëp khoù khaên khi truy xuaát do ñeán moät bieán ñoäng. ng Ñeå giaûi quyeát vaán ñeà, bieán con troû (laø bieán khoâng ñoäng) bie con tro ng ñöôïc söû duïng ñeå troû ñeán bieán ñoäng. ñö ng ng Khi taïo ra moät bieán ñoäng, phaûi duøng moät con troû ñeå löu Khi ng pha ng con tro ñòa chæ cuûa bieán naøy vaø sau ñoù, truy xuaát ñeán bieán ñoäng truy ng thoâng qua bieán con troû ñaõ bieát ñònh danh. qua bie con tro Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 16
Bieán ñoäng ng Hai thao taùc cô baûn treân bieán ñoäng laø taïo vaø huûy moät Hai ng bieán ñoäng do bieán con troû ‘p’ troû ñeán: ng do bie con tro Taïo ra moät bieán ñoäng vaø cho con troû ‘p’ chæ ñeán noù Ta ng con tro Huûy moät bieán ñoäng do p chæ ñeán Hu ng do ch Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 17
Bieán ñoäng ng Taïo ra moät bieán ñoäng vaø cho con troû ‘p’ chæ ñeán noù Ta ng con tro void* malloc(size); // traû veà con troû chæ ñeán vuøng nhôù // tra con tro ng // size byte vöøa ñöôïc caáp phaùt. // void* calloc(n,size);// traû veà con troû chæ ñeán vuøng nhôù // tra con tro ng // vöøa ñöôïc caáp phaùt goàm n phaàn töû, // pha // moãi phaàn töû coù kích thöôùc size byte // moã new // toaùn töû caáp phaùt boä nhôù trong C++ toa Haøm free(p) huyû vuøng nhôù caáp phaùt bôûi haøm malloc hoaëc Ha huy ng calloc do p troû tôùi do tro Toaùn töû delete p huyû vuøng nhôù caáp phaùt bôûi toaùn töû new Toa huy ng do p troû tôùi do tro Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 18
Bieán ñoäng – Ví duï ng int *p1, *p2; // caáp phaùt vuøng nhôù cho 1 bieán ñoäng kieåu int p1 = (int*)malloc(sizeof(int)); *p1 = 5; // ñaët giaù trò 5 cho bieán ñoäng ñang ñöôïc p1 quaûn lyù // caáp phaùt bieán ñoäng kieåu maûng goàm 10 phaàn töû kieåu int p2 = (int*)calloc(10, sizeof(int)); *(p2+3) = 0; // ñaët giaù trò 0 cho phaàn töû thöù 4 cuûa maûng p2 free(p1); free(p2); Caáu truùc Döõ lieäu - Caáu truùc döõ lieäu ñoäng 19
Danh saùch lieân keát Danh ch (List) (List)