Giáo trình CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - Chương 1

Chương 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT1.1. Tầm quan trọng của cấu trúc dữ liệu và giải thuật trong một đề án tin học1.1.1. Xây dựng cấu trúc dữ liệu Có thể nói rằng không có một chương trình máy tính nào mà không có dữ liệu để xử lý. Dữ liệu có thể là dữ liệu đưa vào (input data), dữ liệu trung gian hoặc dữ liệu đưa ra (output data). Do vậy, việc tổ chức để lưu trữ dữ liệu phục vụ cho chương trình có ý nghĩa rất quan trọng trong toàn...
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 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi ThuaätChöông 1: TOÅNG QUAN VEÀ CAÁU TRUÙC DÖÕ LIEÄU VAØ GIAÛI THUAÄT1.1. Taàm quan troïng cuûa caáu truùc döõ lieäu vaø giaûi thuaät trong moät ñeà aùn tin hoïc1.1.1. Xaây döïng caáu truùc döõ lieäuCoù theå noùi raèng khoâng coù moät chöông trình maùy tính naøo maø khoâng coù döõ lieäu ñeå xöû lyù.Döõ lieäu coù theå laø döõ lieäu ñöa vaøo (input data), döõ lieäu trung gian hoaëc döõ lieäu ñöa ra(output data). Do vaäy, vieäc toå chöùc ñeå löu tröõ döõ lieäu phuïc vuï cho chöông trình coù yùnghóa raát quan troïng trong toaøn boä heä thoáng chöông trình. Vieäc xaây döïng caáu truùc döõlieäu quyeát ñònh raát lôùn ñeán chaát löôïng cuõng nhö coâng söùc cuûa ngöôøi laäp trình trong vieäcthieát keá, caøi ñaët chöông trình.1.1.2. Xaây döïng giaûi thuaätKhaùi nieäm giaûi thuaät hay thuaät giaûi maø nhieàu khi coøn ñöôïc goïi laø thuaät toaùn duøng ñeå chæphöông phaùp hay caùch thöùc (method) ñeå giaûi quyeát vaàn ñeà. Giaûi thuaät coù theå ñöôïc minhhoïa baèng ngoân ngöõ töï nhieân (natural language), baèng sô ñoà (flow chart) hoaëc baèng maõgiaû (pseudo code). Trong thöïc teá, giaûi thuaät thöôøng ñöôïc minh hoïa hay theå hieän baèngmaõ giaû töïa treân moät hay moät soá ngoân ngöõ laäp trình naøo ñoù (thöôøng laø ngoân ngöõ maøngöôøi laäp trình choïn ñeå caøi ñaët thuaät toaùn), chaúng haïn nhö C, Pascal, …Khi ñaõ xaùc ñònh ñöôïc caáu truùc döõ lieäu thích hôïp, ngöôøi laäp trình seõ baét ñaàu tieán haønhxaây döïng thuaät giaûi töông öùng theo yeâu caàu cuûa baøi toaùn ñaët ra treân cô sôû cuûa caáu truùcdöõ lieäu ñaõ ñöôïc choïn. Ñeå giaûi quyeát moät vaán ñeà coù theå coù nhieàu phöông phaùp, do vaäysöï löïa choïn phöông phaùp phuø hôïp laø moät vieäc maø ngöôøi laäp trình phaûi caân nhaéc vaø tínhtoaùn. Söï löïa choïn naøy cuõng coù theå goùp phaàn ñaùng keå trong vieäc giaûm bôùt coâng vieäccuûa ngöôøi laäp trình trong phaàn caøi ñaët thuaät toaùn treân moät ngoân ngöõ cuï theå.1.1.3. Moái quan heä giöõa caáu truùc döõ lieäu vaø giaûi thuaätMoái quan heä giöõa caáu truùc döõ lieäu vaø Giaûi thuaät coù theå minh hoïa baèng ñaúng thöùc: Caáu truùc döõ lieäu + Giaûi thuaät = Chöông trìnhNhö vaäy, khi ñaõ coù caáu truùc döõ lieäu toát, naém vöõng giaûi thuaät thöïc hieän thì vieäc theå hieänchöông trình baèng moät ngoân ngöõ cuï theå chæ laø vaán ñeà thôøi gian. Khi coù caáu truùc döõ lieäumaø chöa tìm ra thuaät giaûi thì khoâng theå coù chöông trình vaø ngöôïc laïi khoâng theå coùThuaät giaûi khi chöa coù caáu truùc döõ lieäu. Moät chöông trình maùy tính chæ coù theå ñöôïc hoaønthieän khi coù ñaày ñuû caû Caáu truùc döõ lieäu ñeå löu tröõ döõ lieäu vaø Giaûi thuaät xöû lyù döõ lieäutheo yeâu caàu cuûa baøi toaùn ñaët ra.1.2. Ñaùnh giaù caáu truùc döõ lieäu vaø giaûi thuaät1.2.1. Caùc tieâu chuaån ñaùnh giaù caáu truùc döõ lieäuÑeå ñaùnh giaù moät caáu truùc döõ lieäu chuùng ta thöôøng döïa vaøo moät soá tieâu chí sau: - Caáu truùc döõ lieäu phaûi tieát kieäm taøi nguyeân (boä nhôù trong), Trang: 3 By Hút thuốc lá có hại cho sức khỏe at 9:19 pm, Jun 25, 2007 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät - Caáu truùc döõ lieäu phaûi phaûn aûnh ñuùng thöïc teá cuûa baøi toaùn, - Caáu truùc döõ lieäu phaûi deã daøng trong vieäc thao taùc döõ lieäu.1.2.2. Ñaùnh giaù ñoä phöùc taïp cuûa thuaät toaùnVieäc ñaùnh giaù ñoä phöùc taïp cuûa moät thuaät toaùn quaû khoâng deã daøng chuùt naøo. ÔÛ daây,chuùng ta chæ muoán öôùc löôïng thôøi gian thöïc hieän thuaän toaùn T(n) ñeå coù theå coù söï sosaùnh töông ñoái giöõa caùc thuaät toaùn vôùi nhau. Trong thöïc teá, thôøi gian thöïc hieän moätthuaät toaùn coøn phuï thuoäc raát nhieàu vaøo caùc ñieàu kieän khaùc nhö caáu taïo cuûa maùy tính,döõ lieäu ñöa vaøo, …, ôû ñaây chuùng ta chæ xem xeùt treân möùc ñoä cuûa löôïng döõ lieäu ñöa vaøoban ñaàu cho thuaät toaùn thöïc hieän.Ñeå öôùc löôïng thôøi gian thöïc hieän thuaät toaùn chuùng ta coù theå xem xeùt thôøi gian thöïc hieänthuaät toaùn trong hai tröôøng hôïp: - Trong tröôøng hôïp toát nhaát: Tmin - Trong tröôøng hôïp xaáu nhaát: TmaxTöø ñoù chuùng ta coù theå öôùc löôïng thôøi gian thöïc hieän trung bình cuûa thuaät toaùn: Tavg1.3. Kieåu döõ lieäu1.3.1. Khaùi nieäm veà kieåu döõ lieäuKieåu döõ lieäu T coù theå xem nhö laø söï keát hôïp cuûa 2 thaønh phaàn: - Mieàn giaù trò maø kieåu döõ lieäu T coù theå löu tröõ: V, - Taäp hôïp caùc pheùp toaùn ñeå thao taùc döõ lieäu: O.T = Moãi kieåu döõ lieäu thöôøng ñöôïc ñaïi dieän bôûi moät teân (ñònh danh). Moãi phaàn töû döõ lieäu coùkieåu T seõ coù giaù trò trong mieàn V vaø coù theå ñöôïc thöïc hieän caùc pheùp toaùn thuoäc taäp hôïpcaùc pheùp toaùn trong O.Ñ ...