Giáo trình về môn cấu trúc dữ liệu

Về phương pháp phân tích thiết kế hướng đối tượngThông thường phần quan trọng nhất của quá trình phân tích thiết kế là chiavấn đề thành nhiều vấn đề nhỏ dễ hiểu và chi tiết hơn. Nếu chúng vẫn còn khóhiểu, chúng lại được chia nhỏ hơn nữa. Trong bất kỳ một tổ chức nào, người quảnlý cao nhất cũng không thể quan tâm đến mọi chi tiết cũng như mọi hoạt động.Họ cần tập trung vào mục tiêu và các nhiệm vụ chính, họ chia bớt trách nhiệmcho những người cộng sự dưới quyền của họ. Việc lập trình...
Nội dung trích xuất từ tài liệu:
Giáo trình về môn cấu trúc dữ liệuChöông 1: Giôùi thieäu Phaàn 1 – PHAÀN MÔÛ ÑAÀUChöông 1 – GIÔÙI THIEÄU1.1. Veà phöông phaùp phaân tích thieát keá höôùng ñoái töôïng Thoâng thöôøng phaàn quan troïng nhaát cuûa quaù trình phaân tích thieát keá laø chiavaán ñeà thaønh nhieàu vaán ñeà nhoû deã hieåu vaø chi tieát hôn. Neáu chuùng vaãn coøn khoùhieåu, chuùng laïi ñöôïc chia nhoû hôn nöõa. Trong baát kyø moät toå chöùc naøo, ngöôøi quaûnlyù cao nhaát cuõng khoâng theå quan taâm ñeán moïi chi tieát cuõng nhö moïi hoaït ñoäng.Hoï caàn taäp trung vaøo muïc tieâu vaø caùc nhieäm vuï chính, hoï chia bôùt traùch nhieämcho nhöõng ngöôøi coäng söï döôùi quyeàn cuûa hoï. Vieäc laäp trình trong maùy tính cuõngtöông töï. Ngay caû khi döï aùn ñuû nhoû cho moät ngöôøi thöïc hieän töø ñaàu tôùi cuoái, vieäcchia nhoû coâng vieäc cuõng raát quan troïng. Phöông phaùp phaân tích thieát keá höôùngñoái töôïng döïa treân quan ñieåm naøy. Caùi khoù nhaát laø ñònh ra caùc lôùp sao cho moãilôùp sau naøy seõ cung caáp caùc ñoái töôïng coù caùc haønh vi ñuùng nhö chuùng ta mong ñôïi.Vieäc laäp trình giaûi quyeát baøi toaùn lôùn cuûa chuùng ta seõ ñöôïc taäp trung vaøo nhöõnggiaûi thuaät lôùn. Chöông trình khi ñoù ñöôïc xem nhö moät kòch baûn, trong ñoù caùc ñoáitöôïng seõ ñöôïc goïi ñeå thöïc hieän caùc haønh vi cuûa mình vaøo nhöõng luùc caàn thieát.Chuùng ta khoâng coøn phaûi lo bò maát phöông höôùng vì nhöõng chi tieát vuïn vaët khicaàn phaûi phaùc thaûo moät kòch baûn ñuùng ñaén, moät khi chuùng ta ñaõ tin töôûng hoaøntoaøn vaøo khaû naêng hoaøn thaønh nhieäm vuï cuûa caùc lôùp maø chuùng ta ñaõ giao phoù. Caùc lôùp do ngöôøi laäp trình ñònh nghóa ñoùng vai troø trung taâm trong vieäc hieänthöïc giaûi thuaät.1.2. Giôùi thieäu moân hoïc Caáu truùc döõ lieäu (CTDL) vaø giaûi thuaät Theo quan ñieåm cuûa phaân tích thieát keá höôùng ñoái töôïng, moãi lôùp seõ ñöôïc xaâydöïng vôùi moät soá chöùc naêng naøo ñoù vaø caùc ñoái töôïng cuûa noù seõ tham gia vaøo hoaïtñoäng cuûa chöông trình. Ñieåm maïnh cuûa höôùng ñoái töôïng laø tính ñoùng kín vaø tínhsöû duïng laïi cuûa caùc lôùp. Moãi phaàn meàm bieân dòch cho moät ngoân ngöõ laäp trình naøoñoù ñeàu chöùa raát nhieàu thö vieän caùc lôùp nhö vaäy. Chuùng ta thöû ñieåm qua moät soálôùp maø ngöôøi laäp trình thöôøng hay söû duïng: caùc lôùp coù nhieäm vuï ñoïc/ ghi ñeå traoñoåi döõ lieäu vôùi caùc thieát bò ngoaïi vi nhö ñóa, maùy in, baøn phím,…; caùc lôùp ñoà hoïacung caáp caùc chöùc naêng veõ, toâ maøu cô baûn; caùc lôùp ñieàu khieån cho pheùp xöû lyù vieäcgiao tieáp vôùi ngöôøi söû duïng thoâng qua baøn phím, chuoät, maøn hình; caùc lôùp phuïc vuïcaùc giao dòch truyeàn nhaän thoâng tin qua maïng;…Caùc lôùp CTDL maø chuùng ta saépbaøn ñeán cuõng khoâng laø moät tröôøng hôïp ngoaïi leä. Coù theå chia taát caû caùc lôùp naøythaønh hai nhoùm chính: • Caùc lôùp dòch vuï. • Caùc lôùp coù khaû naêng löu tröõ vaø xöû lyù löôïng döõ lieäu lôùn.Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 1/16Chöông 1: Giôùi thieäu Nhoùm thöù hai muoán noùi ñeán caùc lôùp CTDL (CTDL). Vaäy coù gì gioáng vaø khaùcnhau giöõa caùc lôùp CTDL vaø caùc lôùp khaùc? • Ñieåm gioáng nhau giöõa caùc lôùp CTDL vaø caùc lôùp khaùc: moãi lôùp ñeàu phaûi thöïc hieän moät soá chöùc naêng thoâng qua caùc haønh vi cuûa caùc ñoái töôïng cuûa noù. Moät khi chuùng ta ñaõ xaây döïng xong moät lôùp CTDL naøo ñoù, chuùng ta hoaøn toaøn tin töôûng raèng noù seõ hoaøn thaønh xuaát saéc nhöõng nhieäm vuï maø chuùng ta ñaõ thieát keá vaø ñaõ giao phoù cho noù. Ñieàu naøy raát khaùc bieät so vôùi nhöõng taøi lieäu vieát veà CTDL theo quan ñieåm höôùng thuû tuïc tröôùc ñaây: vieäc xöû lyù döõ lieäu khoâng heà coù tính ñoùng kín vaø tính söû duïng laïi. Tuy veà maët thöïc thi thì caùc chöông trình nhö theá coù khaû naêng chaïy nhanh hôn, nhöng chuùng boäc loä raát nhieàu nhöôïc ñieåm: thôøi gian phaùt trieån giaûi thuaät chính raát chaäm gaây khoù khaên nhieàu cho ngöôøi laäp trình, chöông trình thieáu tính trong saùng, raát khoù söûa loãi vaø phaùt trieån. • Ñaëc tröng rieâng cuûa caùc lôùp CTDL: Nhieäm vuï chính cuûa caùc lôùp CTDL laø naém giöõ döõ lieäu sao cho coù theå ñaùp öùng moãi khi ñöôïc chöông trình yeâu caàu traû veà moät döõ lieäu cuï theå naøo ñoù maø chöông trình caàn ñeán. Nhöõng thao taùc cô baûn ñoái vôùi moät CTDL thöôøng laø: theâm döõ lieäu môùi, xoùa boû döõ lieäu ñaõ coù, tìm kieám, truy xuaát. Ngoaøi caùc thao taùc döõ lieäu cô baûn, caùc CTDL khaùc nhau seõ khaùc nhau veà caùcthao taùc boå sung khaùc. Chính vì ñieàu naøy maø khi thieát keá nhöõng giaûi thuaät ñeågiaûi quyeát caùc baøi toaùn lôùn, ngöôøi ta seõ löïa choïn CTDL naøo laø thích hôïp nhaát. Chuùng ta thöû xem xeùt moät ví duï thaät ñôn giaûn sau ñaây. ...