Giáo trình Cấu trúc dữ liệu và Giải thuật - Chương 1: Giới thiệu

Chương 1: Giới thiệu Phần 1 – PHẦN MỞ ĐẦU Chương 1 – GIỚI THIỆU 1.1. Về phương pháp phân tích thiết kế hướng đối tượng Thông thường phần quan trọng nhất của quá trình phân tích thiết kế là chia vấ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ản lý 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ụ...
Nội dung trích xuất từ tài liệu:
Giáo trình Cấu trúc dữ liệu và Giải thuật - Chương 1: Giới thiệu Chöông 1: Giôùi thieäu Phaàn 1 – PHAÀN MÔÛ ÑAÀU Chöông 1 – GIÔÙI THIEÄU 1.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ø chia vaá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ûn lyù 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äm cho 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õng töô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äc chia 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ãi lôù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öõng giaû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ái töôï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 khi caà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øn toaø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än thöï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ây döï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ính söû 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ïa cung 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äc giao 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ép baø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øy thaø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/16 Chöô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ùc nhau 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ùc thao 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. Giaû söû chuùng ta caàn vieát moät chöông trình nhaän vaøo moät daõy caùc con soá, vaø in chuùng ra theo thöù töï ngöôïc vôùi thöù töï nhaäp vaøo ban ñaàu. Ñeå giaûi quyeát baøi toaùn naøy, neáu chuùng ta nghó ñeán vieäc phaûi khai baùo caùc bieán ñeå löu caùc giaù trò nhaäp vaøo nhö theá naøo, vaø sau ñoù laø thöù töï in ra sao ñeå ñaùp öùng yeâu caàu baøi toaùn, thì döôøng nhö laø chuùng ta ñaõ queân aùp duïng nguyeân taéc laäp trình höôùng ñoái töôïng: chuùng ta ñaõ phaûi baän taâm ñeán nhöõng vieäc quaù chi tieát. Ñaây chæ laø moät ví duï voâ cuøng ñôn giaûn, nhöng noù coù theå minh hoïa cho vai troø cuûa CTDL. Neáu chuùng ta nhôù raèng, vieäc toå chöùc vaø löu döõ lieäu nhö theá naøo laø moät vieäc quaù chi tieát vaø tæ mæ khoâng neân thöïc hieän vaøo luùc naøy, thì ñoù chính laø luùc chuùng ta ñaõ böôùc ñaàu hieåu ñöôïc vai troø cuûa caùc lôùp CTDL. Moân CTDL vaø giaûi thuaät seõ giuùp chuùng ta hieåu roõ veà caùc lôùp CTDL coù saün trong caùc p ...