Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 1: Giới thiệu về cấu trúc dữ liệu và giải thuật - Lê Sỹ Vinh

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 1: Giới thiệu về cấu trúc dữ liệu và giải thuật - Lê Sỹ Vinh

1. Bà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 Nghe - ĐHQGHN Email: vinhioi@yahoo.com
2. Cu trúc d liu (data structure) Cu trúc d liu là gì? Cu trúc d liu là cách t chc lưu gi d liu trong sao cho hiu qu nht Th nào là hiu qu? 1. “Chính xác” 2. Dùng ít b nh 3. Kh năng tìm kim/truy xut 4. Kh năng cp nht, thêm bt (modification, insertion / deletion) 5. ðơn gin, d hiu Các kiu cu trúc d liu cơ bn • Bn ghi (struct) • Danh sách (array) • Danh sách liên kt (list) • Cây (tree) • Bng băm (hash table)
3. Thut tốn (algorithm) • Thut tốn là gì? Thut tốn là mt phương pháp bao gm mt dãy các bưc tính tốn đ gii quyt mt bài tốn. Thut tốn cĩ th đưc din t dưi dng ngơn ng t nhiên (ting Vit, ting Anh ) hay ngơn ng lp trình (C++, Java ) • Th nào là mt thut tốn tt? 1. “ðúng đn” 2. Nhanh 3. Ít b nh 4. ðơn gin, d hiu
4. Ví d 1: Sp xp danh sách tuyn sinh Năm 2008, ði hc Cơng Ngh cĩ N thí sinh tham gia tuyn sinh, hãy vit chương trình sp xp các thí sinh theo th t gim dn ca tng đim thi ba mơn Ví d: Stt H tên Tốn Lý Hĩa Tng 1 Trn Anh Tun 7 8 7 22 2 Bùi Ngc Thăng 10 10 9 29 3 Lê S Vinh 10 8 8 26 4 Nguyn Th Ánh 8 10 9 27
5. Sp xp ni bt (bubble sort) Ý tưng: Ln lưt duyt qua danh sách thí sinh, nu hai thí sinh khơng đúng th t, đi ch hai thí sinh. Lp li quá trình trên cho đn khi danh sách đưc sp xp Step 0 Step 1 Step 3 1. (Tun, 22) 1. (Thăng, 29) 1. (Thăng, 29) 2. (Thăng , 29) 2. (Tun, 22) 2. (Vinh, 26) 3. (Vinh, 26) 3. (Vinh, 26) 3. (Tun, 22) 4. (Ánh , 27) 4. (Ánh, 27) 4. (Ánh, 27) Step 4 Step 5 1. (Thăng, 29) 1. (Thăng, 29) 2. (Vinh, 26) 2. (Ánh, 27) 3. (Ánh, 27) 3. (Vinh, 26) 4. (Tun, 22) 4. (Tun, 22)
6. Sp xp ni bt (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) }
7. Ví d 1’: Sp xp danh sách website (google search) Google cĩ danh sách N website. Website x cĩ mt đ ưu tiên là f(x). Hãy sp xp các website trên theo đ ưu tiên gim dn Câu hi: Cĩ th dùng bubble sort khơng? Tr li: ðưc, nhưng khơng hiu qu
8. Ví d 2: Danh b đin thoi Vit mt chương trình qun lý danh b đin thoi ca tồn b thành ph Hà Ni, sao cho các thao tác sau đưc hiu qu nht: 1. Kim tra mt s đin thoi 2. Thêm mt s đin thoi 3. Xĩa mt s đin thoi
9. Ví d 3: Tìm đưng đi tt nht • Xây dng h thng phn mm ch đưng đi tt nht cho ngưi dùng 1. ðưng đi ngn nht 2. ðưng đi qua ít đèn xanh – đèn đ nht 3. ðưng đi ít tc nht
10. Ví d 3: Tìm đưng đi tt nht (google map)
11. Ví d 3: Tìm đưng đi tt nht (google map)
12. Ví d 4: Xây dng h thng t đin Vit chương trình t đin Anh – Vit, cho phép thc hin các thao tác sau: 1. Tìm mt t 2. Thêm mt t 3. Xĩa mt t 4. Sa mt t 5. Tìm t đng nghĩa
13. Ví d 5: Ngưi bán hàng traveling salesman problem (TSP) Mt ngưi bán hàng cn đn thăm N khách hàng N đa đim khác nhau. Tìm mt hành trình cho ngưi bán hàng trên sao cho: 1. Mi đa đim thăm đúng 1 ln, sau đĩ quay v đim xut phát 2. Tng chi phí đi li là ít nht
14. Ngưi bán hàng Thut tốn: Thăm đa đim gn nht (nearest neighbor tour) T đim xut phát, ln lưt đi thăm các đim theo quy tc: “ðn thăm đim chưa đưc thăm gn vi đim hin ti nht”
15. Ngưi bán hàng Nearest neighbor tour: 1 → 2 → 3 → X → 7 → 8 → 6 → 5 → 4 → 9 → 1 ðương đi ti ưu: 1 → 2 → 3 → 4 → 5 → 6 → 8 → 7 → X → 9 → 1
16. Các ví d khác (10’)
17. Th nào là mt chương trình tt? 1. ðúng đn 2. Hiu qu 3. D hiu 4. D tìm li 5. D thay đi và nâng cp “Thut tốn + Cu trúc d liu = Chương trình” N. Wirth
18. D liu • D liu là nhng thơng tin mà máy tính cĩ th x lý: s nguyên, s thc, xâu kí t, và các d liu phc tp đưc to t nhiu thành phn • Trong b nh máy tính, d liu đưc biu din dưi dng nh phân (dãy các kí t 0, 1) • Trong các ngơn ng lp trình bc cao (C++, Java ), d liu đưc biu din dưi dng tru tưng, xut phát t biu din tốn hc và d hiu cho con ngưi: – int age – double weight
19. Kiu d liu cơ bn Kiu d liu đưc xác đnh bi: 1. Phm vi giá tr 2. Các phép tốn Ví d trong C++ kiu phm vi phép tốn thưng dùng
    bool true / false and, or, not
    char 127 > 127 ‘ ’, ‘=’
    int 32,767 > 32,767 ‘ ’, ‘=’, ‘+’, ‘’, ‘*’, ‘/’
    float ~1E37 > ~1E+37 ‘ ’, ‘=’, ‘+’, ‘’, ‘*’, ‘/’
    double ~1.7E308 > ~1.7E+308 ‘ ’, ‘=’, ‘+’, ‘’, ‘*’, ‘/’
20. Kiu d liu cĩ cu trúc Câu hi: Làm sao đ biu din d liu v 1 đim trên mt phng? ðáp án: Ngơn ng lâp trình cung cp cho ta nhng lut đ xây dng kiu d liu mi T t nhng kiu d liu đã bit t1, t 2, ,t n. Ví d trong C++: struct T { t1 x1 t2 x2 tn xn }
21. Kiu d liu cĩ cu trúc • Xây dng cu trúc d liu đ biu din d liu ca 1 đim trên mt phng struct pointType { double x; double y; } • Xây dng cu trúc d liu đ biu din d liu ca 1 đon thng trên mt phng struct lineType { point Type start; pointType end; }
22. Kiu d liu cĩ cu trúc • Xây dng cu trúc d liu đ biu din 1 sinh viên (5’) struct studentType { char name[100]; int age; bool sex; } • Xây dng cu trúc d liu đ biu din danh sách 1 lp hc struct studentClassType{ char className[100]; int numberStudent; studentType studentArr[100]; }
23. Phm vi và các phép tốn trên kiu d liu cĩ cu trúc Xét kiu d liu mi T đưc to t nhưng kiu d liu đã bit t1, t 2, ,t n, Ví d: struct complexType { double real; double image; } Phm vi: Xác đnh bi phm vi ca các kiu d liu thành phn – real: là s thc nm trong phm vi kiu ‘double’ – image: là s thc nm trong phm vi kiu ‘double’
24. Phm vi và các phép tốn trên kiu d liu cĩ cu trúc Phép tốn: Do ngưi dùng đnh nghĩa Ví d: struct complexType { double real; double image; } complexType createComplex (double real, double image) { complexType c; c.real = real; c.image = image; return c; }
25. Phm vi và các phép tốn trên kiu d liu cĩ cu trúc complexType add (complexType c1, complextType c2) { complexType c12; c12.real = c1.real + c2.real; c12.image = c1.image + c2.image; return c12; } complexType multiply (complexType c1, complextType c2) { complexType c12; c12.real = (c1.real * c2.real) – (c1.image * c2.image); c12.image = (c1.real * c2.image) + (c1.image * c2.real); return c12; }
26. Phm vi và các phép tốn trên kiu d liu cĩ cu trúc complexType getReal (complexType c) { c.real } complexType getImage (complexType c) { c.image } void printComplex (complexType c) { cout << c.real << “ +i ” << c.image << “ \ n” ; }
27. Tru tưng hĩa d liu (abstraction data type) 1. ðc t đi tưng d liu (các thành phn d liu ca đi tưng) Ví d: đi tưng s phc (complex) – real – image 2. ðc t các phép tốn trên đi tưng d liu (operations) Ví d: ði tưng s phc (complex): – createComplex (real, image) – getReal (complexNumber) – getImage (complexNumber) – add (complexNumber1, complexNumber2) – multiply (complexNumber2, complexNumber2) – print (complexNumber)
28. Tru tưng hĩa d liu Tru tưng hĩa đi tưng sinh viên (student ) (5’) 1. ðc t đi tưng d liu name, age, sex, address 2. ðc t các phép tốn trên đi tưng d liu createStudent (name, age, sex, address) compare (student1, student2) getName (student) getAge (student) getSex (student) getAdd (student)
29. Tru tưng hĩa d liu • studentClass 1. ðc t đi tưng d liu className, numberStudent, studentArr, Address 2. ðc t các phép tốn trên đi tưng d liu addStudent (studentClass, student) findStudent (studentClass, student) deleteStudent (studentClass, student) getClassName (studentClass) getNumberStudent (studentClass) getStudentArr (studentClass) getStudentAddress (studentClass)
30. Lp trình hưng đi tưng Object oriented programming (OOP) • Lâp trình hưng đi tưng giúp chúng ta cài đt các mơ t tru tưng (đi tưng d liu và các phép tốn) thành các đon mã chương trình • Chương trình đưc thit k thành tng đon nh, mi đon mơ t v mt đi tưng (thuc tính d liu, các phép tốn trên d liu) • Hai thuc tính quan trng: đĩng gĩi (encapsulation) và tha k (inheritance)
31. OOP: Tính đĩng gĩi (encapsulation) • Class : Cài đt mt lp đi tưng d liu tru tưng. Vic cài đt bao gm cài đt các thành phn d liu và các phép tốn trên d liu Ví d: class complex { • Liên kt cht ch gia d liu và private: double real; phép tốn double image; public: • Che du d liu void create (double newReal, double newImage) { real = newReal; image = newImage; • D dàng tìm li } double getReal () { return real; • Các đi tưng liên kt vi nhau } thơng qua các phép tốn void print { cout << real << “ +i ” << image << “ \ n” ; } };
32. OOP: Tính đĩng gĩi (encapsulation) Object: Biu din cho mt đi tưng c th ca mt lp complex c1; complex c2;
33. Thit k chương trình • ðc t vn đ • Thit k cu trúc d liu và gii thut • Cài đt (C++, Java ) • Th nghim và sa li
34. Thit k chương trình: ðc t vn đ Chính xác hĩa vn đ cn gii quyt: Chúng ta đưc cho nhng gì? Chúng ta cn tìm ra cái gì? Mi quan h gia chúng là gì? ðc t vn đ trong khoa hc máy tính: Input: D liu vào, các rng buc, đnh dng Ouput: D liu ra, các rng buc, đnh dng
35. ðc t vn đ Ví d: Cho mt dãy s phc, hãy 1. Tính tng ca dãy s phc 2. Tính tích ca dãy s phc 3. Tìm s phc cĩ phn thc (real) ln nht 4. Tìm s phc cĩ phn o (image) ln nht ðc t vn đ: • Input: Mt dãy s phc, mi s phc đưc biu din bi 2 s thc mơ t phn thc (real) và phn o (image) • Output: – c1 (s phc biu din tng ca dãy s phc) – c2 (s phc biu din tích ca dãy s phc) – c3 (s phc cĩ phn thc ln nht) – c4 (s phc cĩ phn o ln nht)
36. Bài tp ðc t vn đ cho các bài tốn dưi đây 1. Sp xp danh sách website 2. H thng t đin 3. Tìm đưng đi tt nht 4. Ngưi bán hàng