Giới thiệu về lập trình cấu trúc dữ liệu và giải thuật

Cấu trúc dữ liệu là một cách tổ chức các dữ liệu thành một đơn vị hoàn chỉnh bao gồm các thành phần (phần tử) là các dữ liệu cơ bản, các mối liên kết giữa các phần tử ấy và các thao tác cơ bản trên chúng. Các thao tác này thường được gọi là các phép toán trên cấu trúc dữ liệu xác định. Các phép toán cơ bản thường gặp là tạo lập(create), hủy (dipose), thêm (add) hoặc chèn (insert) một phần tử, xóa (delete) một phần tử, tìm kiếm(search),.....
Nội dung trích xuất từ tài liệu:
Giới thiệu về lập trình cấu trúc dữ liệu và giải thuậtBài 1: Gi i thi u v c u trúc d li u và gi i thu t (Introduction to data structures and algorithms) Lê S Vinh B môn Khoa H c Máy Tính – Khoa CNTT ð i H c Công Ngh - ðHQGHN Email: vinhioi@yahoo.com C u trúc d li u (data structure)- C u trúc d li u là gì? C u trúc d li u là cách t ch c lưu gi d li u trong sao cho hi u qu nh t- Th nào là hi u qu ? 1. “Chính xác” 2. Dùng ít b nh 3. Kh năng tìm ki m/truy xu t 4. 4. Kh năng c p nh t, thêm b t (modification, insertion / deletion) 5. ðơn gi n, d hi u- Các ki u c u trúc d li u cơ b n • B n ghi (struct) • Danh sách (array) • Danh sách liên k t (list) • Cây (tree) • B ng băm (hash table) Thu t toán (algorithm)• Thu t toán là gì? Thu t toán là m t phương pháp bao g m m t dãy các bư c tính toán ñ gi i quy t m t bài toán. Thu t toán có th ñư c di n t dư i d ng ngôn ng t nhiên (ti ng Vi t, ti ng Anh…) hay ngôn ng l p trình (C++, Java…)• Th nào là m t thu t toán t t? 1. “ðúng ñ n” 2. Nhanh 3. Ít b nh 4. ðơn gi n, d hi u Ví d 1: S p x p danh sách tuy n sinhNăm 2008, ð i h c Công Ngh có N thí sinh tham gia tuy n sinh, hãy vi t chương trình s p x p các thí sinh theo th t gi m d n c a t ng ñi m thi ba mônVí d :Stt H tên Toán Lý Hóa T ng1 Tr n Anh Tu n 7 8 7 222 Bùi Ng c Thăng 10 10 9 293 Lê S Vinh 10 8 8 264 Nguy n Th Ánh 8 10 9 27 S p x p n i b t (bubble sort)Ý tư ng: L n lư t duy t qua danh sách thí sinh, n u hai thí sinh không ñúng th t , ñ i ch hai thí sinh. L p l i quá trình trên cho ñ n khi danh sách ñư c s p x p Step 0 Step 1 Step 31. (Tu n, 22) 1. (Thăng, 29) 1. (Thăng, 29)2. (Thăng , 29) 2. (Tu n, 22) 2. (Vinh, 26)3. (Vinh, 26) 3. (Vinh, 26) 3. (Tu n, 22)4. (Ánh , 27) 4. (Ánh, 27) 4. (Ánh, 27) Step 4 Step 51. (Thăng, 29) 1. (Thăng, 29)2. (Vinh, 26) 2. (Ánh, 27)3. (Ánh, 27) 3. (Vinh, 26)4. (Tu n, 22) 4. (Tu n, 22) S p x p n i b t (bubble sort)Function bubbleSort (A : danh sách thí sinh) { swapped := false; do swapped := false; for each i = 1 to N – 1 do if A[i].diem < A[i + 1]. diem then { swap (A[i], A[i+1]); swapped := true; } done; while (swapped = true)} Ví d 1’: S p x p danh sách website (google search)Google có danh sách N website. Website x có m t ñ ưu tiên là f(x). Hãy s p x p các website trên theo ñ ưu tiên gi m d nCâu h i: Có th dùng bubble sort không?Tr l i: ðư c, nhưng không hi u qu Ví d 2: Danh b ñi n tho iVi t m t chương trình qu n lý danh b ñi n tho i c a toàn b thành ph Hà N i, sao cho các thao tác sau ñư c hi u qu nh t:1. Ki m tra m t s ñi n tho i2. Thêm m t s ñi n tho i3. Xóa m t s ñi n tho i Ví d 3: Tìm ñư ng ñi t t nh t• Xây d ng h th ng ph n m m ch ñư ng ñi t t nh t cho ngư i dùng 1. ðư ng ñi ng n nh t 2. ðư ng ñi qua ít ñèn xanh – ñèn ñ nh t 3. ðư ng ñi ít t c nh tVí d 3: Tìm ñư ng ñi t t nh t (google map)Ví d 3: Tìm ñư ng ñi t t nh t (google map) Ví d 4: Xây d ng h th ng t ñi nVi t chương trình t ñi n Anh – Vi t, cho phép th c hi n các thao tác sau: 1. Tìm m t t 2. Thêm m t t 3. Xóa m t t 4. S a m t t 5. Tìm t ñ ng nghĩa Ví d 5: Ngư i bán hàng traveling salesman problem (TSP)M t ngư i bán hàng c n ñ n thăm N khách hàng N ñ a ñi m khác nhau. Tìmm t hành trình cho ngư i bán hàng trên sao cho: 1. M i ñ a ñi m thăm ñúng 1 l n, sau ñó quay v ñi m xu t phát 2. T ng chi phí ñi l i là ít nh t Ngư i bán hàngThu t toán: Thăm ñ a ñi m g n nh t (nearest neighbor tour) T ñi m xu t phát, l n lư t ñi thăm các ñi m theo quy t c: “ð n thăm ñi m chưa ñư c thăm g n v i ñi m hi n t i nh t” Ngư i bán hàngNearest neighbor tour: 1 → 2 → 3 → X → 7 → 8 → 6 → 5 → 4 → 9 → 1ðương ñi t i ưu: 1→2 →3→4 →5 →6 →8→7→X→9→1Các ví d khác (10’) Th nào là m t chương trình t t?1. ðúng ñ n2. Hi u qu3. D hi u4. D tìm l i5. D thay ñ i và nâng c p“Thu t toán + C u trúc d li u = Chương trình” N. Wirth D li u• D li u là nh ng thông tin mà máy tính có th x lý: s nguyên, s th c, xâu kí t , và các d li u ph c t p ñư c t o t nhi u thành ph n• Trong b nh máy tính, d li u ñư c bi u di n dư i d ng nh phân (dãy các kí t 0, 1)• Trong các ngôn ng l p trình b c cao (C++, Java..), d li u ñư c bi u di n dư i d ng tr u tư ng, xu t phát t bi u di n toán h c và d hi u cho con ngư i: – int age – double weight Ki u d li u cơ b nKi u d li u ñư c xác ñ nh b i:1. Ph m vi giá tr2. Các phép toán Ví d trong C++ ki u ph m vi phép toán thư ng dùng bool true / false and, or, not char -127 -> 127 ‘’, ‘=’ int -32,767 -> 32,767 ‘’, ‘=’, ‘+’, ‘-’, ‘*’, ‘/’ float ~1E-37 -> ~1E+37 ‘’, ‘=’, ‘+’, ‘-’, ‘*’, ‘/’ double ~1.7E-308 -> ~1.7E+308 ‘’, ‘=’, ‘+’, ‘-’, ‘*’, ‘/’ ...