Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan về các giải thuật và cấu trúc dữ liệu

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan về các giải thuật và cấu trúc dữ liệu

1. Cấu trúc dữ liệu và giải thuật (Data structure and Algorithms) 1
2. Nội dung chương trình Chương I TỔNG QUAN VỀ GIẢI THUẬT VÀ CẤU TRÚC DỮ LIỆU I. Khái niệm về cấu trúc dữ liệu và giải thuật II. Một số cú pháp điều khiển III. Đánh giá độ phức tạp của giải thuật 2
3. Nội dung chương trình Chương II. TÌM KIẾM VÀ SẮP XẾP I. Các giải thuật tìm kiếm nội 1. Tìm kiếm tuyến tính 2. Tìm kiếm nhị phân II. Các giải thuật sắp xếp nội 1. Chọn trực tiếp (Selection sort) 2. Chèn trực tiếp (Insertion sort) 3. Đổi chỗ trực tiếp (Interchange Sort) 4. Nổi bọt (Buble sort) 5. Sắp xếp cây (Heap sort) 6. Sắp xếp dựa trên phân hoạch (Quick sort) 7. Sắp xếp trộn trực tiếp (Merge sort ) 3
4. Nội dung chương trình Chương III. CẤU TRÚC DỮ LIỆU ĐỘNG I. Kiểu dữ liệu con trỏ II. Danh sách liên kết-khái niệm III. Danh sách liên kết đơn 1. Tổ chức danh sách đơn 2. Các thao tác cơ bản trên danh sách đơn a. Tạo danh sách b. Duyệt danh sách c. Chèn phần tử vào danh sách d. Xoá phần tử khỏi danh sách 3. Sắp xếp dánh sách (lý thuyết+đọc thêm) 4. Các cấu trúc đặc biệt của danh sách đơn Stack Queue IV. Một số cấu trúc dữ liệu dạng danh sách liên kết khác 1. Danh sách liên kết kép 2. Hàng đợi 2 đầu 3. Danh sách liên kết có thứ tự 4. Danh sách liên kết vòng 5. Danh sách có nhiều mối liên kết 4
5. Nội dung chương trình Chương IV. CẤU TRÚC CÂY I. Khái niệm về cây II. Cây nhị phân 1. Một số tính chất của cây nhị phân 2. Biểu diễn cây nhị phân 3. Duyệt cây nhị phân 4. Biểu diễn cây tổng quát III. Cây nhị phân tìm kiếm 1. Tìm một phần tử 2. Thêm một phần tử 3. Huỷ một phần tử IV. Cây nhị phân cân bằng 1. Cây nhị phân cân bằng hoàn toàn 2. Cây nhị phân cân bằng 5
6. Nội dung chương trình Phần II. Bài tập+Thực hành + Ceminar - Cài đặt các chương thuật toán trong phần lý thuyết đã học 6
7. Tài liệu tham khảo 1. Trần Hạnh Nhi-Dương Anh Đức, Giáo trình cấu trúc dữ liệu và giải thuật ĐH Quốc gia Tp Hồ Chí Minh 2. Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật, NXB Khoa học kỹ thuật, 1996 3. Robert Sedgewick, Cẩm nang thuật toán, tập 1, NXB Khoa học kỹ thuật, 1994, bản dịch của nhóm tác giả ĐH TH Tp. HCM 4. N. Wirth: Algorithms+Data structures=Programs (Prentice Hall, 1976) V v 7
8. Chương I Tổng quan về các giải thuật và cấu trúc dữ liệu I. Khái niệm về cấu trúc dữ liệu và giải thuật II. Một số cú pháp điều khiển III. Đánh giá độ phức tạp của giải thuật 8
9. I. Khái niệm về cấu trúc dữ liệu và giải thuật 9
10. 1. Khái niệm bài toán Trong phạm vi tin học, ta có thể quan niệm bài toán (Problems) là công việc mà ta muốn máy tính thực hiện VD: In dòng chữ ra màn hình, giải phương trình bậc 2, quản lý cán bộ trong một cơ quan * Diễn đạt bài toán thành 2 thành phần Input: Thông tin đầu vào Ví dụ Output: Thông tin đầu ra 10
11. 2. Khái niệm Cấu trúc dữ liệu và giải thuật Cấu trúc dữ liệu: là tập các dữ liệu có quan hệ với nhau, được tổ chức theo những phương thức nhất định Giải thuật (thuật toán-Algorithm): là một dãy hữu hạn các thao tác chặt chẽ và rõ ràng được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác đó, ta nhận được mục tiêu định trước 11
12. 3. Các đặc trưng của giải thuật a. Tính xác định Ở mỗi bước của thuật toán các thao tác phải hết sức rõ ràng: Không thể gây nên sự nhập nhằng, tuỳ tiện. Nói một cách khác là trong cùng một điều kiện, hai bộ xử lý cùng thực hiện một bước của giải thuật thì phải cho cùng một kết quả b. Tính hữu hạn dừng Giải thuật bao giờ cũng phải dừng sau một số hữu hạn bước 12
13. 3. Các đặc trưng của giải thuật c. Tính đúng đắn Sau khi thực hiện tất cả các thao tác của thuật toán ta phải được kết quả mong muốn d. Tính phổ dụng Thuật toán có thể giải bất kỳ bài toán nào trong cùng một lớp các bài toán 13
14. 3. Các đặc trưng của giải thuật (tiếp) e. Tính có đại lượng vào, đại lượng ra - Khi bắt đầu giải thuật bao giờ cũng nhận các đại lượng vào mà ta thường gọi là dữ liệu vào - Sau khi kết thúc, một thuật toán bao giờ cũng cho một số đại lượng ra tuỳ theo các chức năng mà thuật toán đảm nhiệm, chúng thường được gọi là dữ liệu ra. 14
15. 3. Các đặc trưng của giải thuật (tiếp) f. Tính có hiệu quả Tính có hiệu quả của giải thuật được đánh giá dựa trên các tiêu chuẩn sau • Dung lượng bộ nhớ cần có • Số các phép tính cần thực hiện • Thời gian cần thiết để chạy • Có dễ hiểu không • Có dễ cài đặt trên máy không 15
16. 4. Ngôn ngữ diÔn đạt giải thuật a. Liệt kê từng bước (ngôn ngữ tự nhiên) -Liệt kê các bước thực hiện giải thuật theo thứ tự thực hiện Ví dụ b. Sơ đồ khối • Khối bắt đầu hoặc kết thúc • Nhập dữ liệu • Khối thao tác • Khối điều kiện • Chỉ hướng thực hiện của Ví dụ giải thuật 16
17. 4. Ngôn ngữ diÔn đạt giải thuật (tiếp) c. Dùng ngôn ngữ phỏng trình (tựa ngôn ngữ lập trình) -Sử dụng cú pháp của một ngôn ngữ lập trình +Ngôn ngữ tự nhiên để diễn đạt giải thuật Ví dụ d. Dùng ngôn ngữ lập trình -Dùng ngôn ngữ lập trình nào đó để viết giải thuật -Hạn chế: Ví dụ ▪Phụ thuộc vào ngữ nghĩa, cú pháp→nặng nề, gò bó ▪Không được nhiều người dùng ưa thích và sử dụng -Lưu ý: Trong quá trình học môn học này, chủ yếu dùng ngôn ngữ phỏng trình tựa Pascal /C để diễn đạt giải thuật 17
18. 5. Kiểu dữ liệu • Dữ liệu : Số, ký tự, hình ảnh, âm thanh •Thuộc tính của một kiểu dữ liệu bao gồm: - Tên kiểu dữ liệu - Mièn giá trị - Kích thức lưu trữ - Tập các phép toán tác động lên KDL đó 18
19. 5. Kiểu dữ liệu Các kiểu dữ liệu Rời rạc: Số nguyên, ký tự, logic, liệt kê, miền con • KDL cơ bản: Liên tục: Số thực Kiểu chuỗi (String) Kiểu Mảng (Array) • KDL cấu trúc Kiểu bản ghi (Recorrd) Kiểu tập hợp (Union) 19
20. 5. Kiểu dữ liệu Các kiểu dữ liệu Danh sách móc nối (List) • KDL trừu tượng Cây (Tree) Đồ thị (Graph) Tập hợp (union) 20
21. 6. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật • North Wirth say that: Data Structures+Algorithms = Programs - Để xây dựng giải thuật phù hợp → phải xác định nó tác động trên các kiểu dữ liệu nào Ví dụ: Làm nhuyễn các hạt đậu → xay chứ không băm - Khi chọn lựa cấu trúc dữ liệu → cần phải hiểu rõ những thao tác (giải thuật) sẽ tác động lên nó Ví dụ: Biểu diễn điểm của sinh viên → dùng số chứ không dùng chữ - Cấu trúc dữ liệu thay đổi → giải thuật thay đổi theo Ví dụ 21
22. 7. Tiêu chuẩn đánh giá CTDL a. Phản ánh đúng thực tế Quan trọng nhất, quyết định tính đúng đắn của toàn bộ bài toán b. Phù hợp với các thao tác trên đó Giúp tăng tính hiệu quả của bài toán c. Tiết kiệm tài nguyên hệ thống CPU, bộ nhớ VD: Khai báo tháng trong năm: Nên dùng kiểu byte thay vì kiểu int 22
23. Chương I Tổng quan về các giải thuật và cấu trúc dữ liệu I. Khái niệm về cấu trúc dữ liệu và giải thuật II. Một số cú pháp điều khiển III. Đánh giá độ phức tạp của giải thuật 23
24. II. Một số cú pháp điều khiển 24
25. II. Một số cú pháp điều khiển 1. Cú pháp tuần tự • Có dạng : S1; S2; S3; Sn • Với Si là các lệnh trọng chương trình • Để thực hiện câu lệnh tuần tự thì chương trình thực hiện lần lượt từ S1 đến Sn. Đầu ra của S1 là đầu vào của S2, đầu ra của S2 là đầu vào của S3 ➔ Phải tôn trọng thứ tự thực hiện công việc, công việc nào làm trước thì phải viết lệnh trước Sơ đồ hoạt động 25
26. II. Một số cú pháp điều khiển 2. Câu lệnh gán • Có dạng V:=E với V chỉ tên biến, tên hàm; E chỉ biểu thức 3. Câu lệnh ghép • Có dạng: Begin S1; S2; , Sn End; • Nó cho phep ghép nhiều câu lệnh lại để được coi như một câu lệnh 26
27. II. Một số cú pháp điều khiển 4. Câu lệnh điều kiện • Có dạng: If B Then S; • B là một biểu thức logic, S là một câu lệnh khác Hoặc • Có dạng: If B Then S1 Else S2; • B là một biểu thức logic, S1, S2 là một câu lệnh khác Sơ đồ hoạt động 27
28. II. Một số cú pháp điều khiển 5. Câu lệnh lặp xác định • Có dạng: for i:=m to n do S; • Thực hiện câu lệnh S với i lấy giá trị nguyên từ m tới n (n>=m), với bước nhảy tăng bằng 1 Hoặc • Có dạng: for i:=n downto m do S; • Thực hiện tương tự như câu lệnh trên với bước nhảy giảm bằng 1 28
29. II. Một số cú pháp điều khiển 6. Câu lệnh lặp không xác định • Có dạng: while B do S; • Trong đó B là biểu thức logic; S là câu lệnh; • Chừng nào B có giá trị True thì thực hiện S Sơ đồ hoạt động Hoặc • Có dạng: repeat S until B; • Trong đó B là biểu thức logic; S là câu lệnh; • Lặp lại cho tới khi B có giá trị True 29
30. II. Một số cú pháp điều khiển 7. Câu lệnh nhảy • Có dạng: go to n; • n là số hiệu của một bước trong chương trình • Thường hạn chế việc dùng Go to 8. Câu lệnh vào, ra • Có dạng: read( ); write( ); 30
31. II. Một số cú pháp điều khiển 9. Chương trình con • Chương trình con Hàm function (danh sách tham số) Begin S1; S2; S3; ; Sn Return End; 31
32. II. Một số cú pháp điều khiển 9. Chương trình con • Chương trình con Thủ tục procedure (danh sách tham số)> Begin S1; S2; S3; ; Sn End; 32
33. Chương I Tổng quan về các giải thuật và cấu trúc dữ liệu I. Khái niệm về cấu trúc dữ liệu và giải thuật II. Một số cú pháp điều khiển III. Đánh giá độ phức tạp của giải thuật 33
34. III. Đánh giá độ phức tạp của giải thuật 34
35. 1. Các tiêu chuẩn đánh giá độ phức tạp ▪ Thời gian ▪ Bộ nhớ ▪ Thực nghiệm Nhược điểm: - Phải cài đặt bằng ngôn ngữ lập trình cụ thể - Phụ thuộc trình độ người cài đặt - Chọn mẫu thử - Phụ thuộc nhiều vào phần cứng ➔ Đánh giá theo hướng xấp xỉ tiệm cận qua các khái niệm toán học: O(), o(), ➔ Quan tâm đến trường hợp trung bình 35
36. 2. Độ phức tạp về thời gian của giải thuật • Nếu thời gian thực hiện một giải thuật là T(n)=c.n2 (với c là hằng số) thì ta nói: Độ phức tạp về thời gian của giải thuật này có cấp n2 và ký hiệu T(n)=O(n2) (ký hiệu chữ O lớn) • Một cách tổng quát ta có thể định nghĩa: Một hàm f(n) được xác định là O(g(n)) f(n)=O(g(n)) và được gọi là có cấp g(n) nếu tồn tại các hàng số c và n0 sao cho: Ví dụ f(n) c.g(n) khi n n0 36
37. 3. Xác định độ phức tạp về thời gian •Quy tắc tổng: Giả sử T1(n) và T2(n) là thời gian thực hiện của 2 đoạn chương trình P1 và P2 mà T1(n)=O(f(n)) và T2(n)=O(g(n)) thì thời gian thực hiện P1 và P2 kế tiếp nhau sẽ là: T(n)=T1(n)+T2(n)=O(max(f(n), g(n))) Ví dụ •Quy tắc nhân Nếu tương ứng với P1 và P2 là T1(n)=O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện P1, P2 lồng nhau sẽ là: Ví dụ T(n)=T (n).T (n)=O(f(n).g(n)) 1 2 37
38. 4. Độ phức tạp về thời gian của các cú pháp điều khiển • Khái niệm: Phép toán tích cực: Là phép toán mà thời gian thực hiện nó không ít hơn thời gian thực hiện các phép toán khác. Ví dụ: a. Câu lệnh gán, đọc, viết, nhẩy: Có thời gian thực hiện =c (hằng số) ➔ đánh giá là O(1) b. Câu lệnh ghép •Begin S1; S2; , Sn End; •Thời gian thực hiện theo luật cộng 38
39. 4. Độ phức tạp về thời gian của các cú pháp điều khiển c. Câu lệnh điều kiện If B then S1 Else S2; •Thời gian thực hiện là O(Max(f1(n), f2(n))) •Trong đó: Thời gian thực hiện S1 là T1(n)=O(f1(n)); S2 là T2(n)=O(f2(n)) 39
40. 4. Độ phức tạp về thời gian của các cú pháp điều khiển d. Câu lệnh lặp While • While B Do S; • Nếu thời gian thực hiện S là T(n)=O(f(n)) và có g(n) lần thực hiện S trong vòng lặp While (tối đa) thì thời gian thực hiện vòng lặp là O(f(n).g(n)) e. Câu lệnh lặp Repeat • Repeat S1; S2; , Sn Until B; • Nếu thời gian thực hiện S1, S2, , Sn là T(n)=O(f(n)) và số lần lặp tối đa là g(n) thì thời gian thực hiện vòng lặp là O(f(n).g(n)) 40
41. 4. Độ phức tạp về thời gian của các cú pháp điều khiển f. Câu lệnh lặp xác định • for i:=m to n do S; • Nếu thời gian thực hiện S là T(n)=O(f(n)) và có g(n) lần lặp For thì thời gian thực hiện là O(f(n).g(n)) Ví dụ về đánh giá độ phức tạp 41
42. 5. Phân lớp các thuật toán • Phức tạp đa thức: O(1), O(n), O(n.logn), O(n2), O(n3) • Phức tạp hàm mũ: O(2n) • Phức tạp giai thừa: O(n!) Mục tiêu thiết kế giải thuật: Đưa bài toán về độ phức tạp đa thức 42
43. So sánh các độ phức tạp Đồ thị của một số hàm số 43
44. So sánh các độ phức tạp Bảng giá trị của một số hàm số long2n n nlog2n n2 n3 2n 0 1 0 1 1 2 1 2 2 4 8 4 2 4 8 16 64 16 3 8 24 64 512 256 4 16 64 256 4096 6536 5 32 160 1024 32768 2.147.483.648 44
45. The End ! 45
46. Ví dụ: Chương trình quản lý điểm của sinh viên Chương trình quản lý điểm của sinh viên, cần lưu điểm số của 3 sinh viên. Do mỗi sinh viên có 4 điểm số ứng với 4 môn học ➔ dữ liệu có dạng bảng sau: SV Môn 1 Môn 2 Môn 3 Môn 4 SV 1 5 6 7 0 SV 2 6 5 8 8 SV 3 5 5 9 7 46
47. Ví dụ: Chương trình quản lý điểm của sinh viên •Phương án 1: Sử dụng mảng một chiểu 12 phần tử, nhóm 4 phần tử là điểm của 1 SV 5 6 7 0 6 5 8 8 5 5 9 7 SV1 SV2 SV3 Truy xuất điểm j của sinh viên i Bảng (dòng i, cột j)=A[(i-1)*số cột+j] •Phương án 2: Sử dụng mảng hai chiều 3X 4, phần tử A[i,j] là điểm thi môn j của sinh viên i 5 6 7 0 A= 6 5 8 8 5 5 9 7 47
48. Dùng sơ đồ khối Tìm UCLN của 2 số nguyên dương m và n Begin m,n Đúng m=n UCLN = m Sai Sai Đúng m>n n:=n-m m:=m-n End 48
49. Dùng ngôn ngữ phỏng trình Function UCLN (m,n) {Tìm ước số chung lớn nhất của hai số nguyên dương m và n} Begin -Nhập m, n nguyên dương -While m n then m:=m-n else n:=n-m -UCLN:=m End; 49
50. Dùng ngôn ngữ lập trình #include Bài toán: Tìm UCLN của 2 số nguyên dương m và n #include void main() { int m, n; printf("Nhap 2 so nguyen duong m,n\n"); scanf("%d%d",&m,&n); while (m!=n) { if(m>n) m=m-n; else n=n-m; } printf("UCLN=%d",m); getch(); } 50
51. Dùng liệt kê từng bước Bài toán: Tìm UCLN của 2 số nguyên dương m và n •Bước 1: Nhập hai số nguyên dương •Bước 2: Nếu m=n sang bước 4; ngược lại sang bước 3 •Bước 3: Nếu m>n thì đặt m=m-n về bước 2 Nếu m<n thì đặt n=n-m về bước 2 •Bước 4: Trả lời UCLN=m, Kết thúc 51
52. Ví dụ: Diễn đạt bài toán thành 2 thành phần Diễn đạt bài toán giải phương trình bậc 2 •Input : Các hệ số a,b,c •Output: Thông báo nghiệm x1, x2; nghiệm kép x; hoặc vô nghiệm Diễn đạt bài toán Tìm ước số chung lớn nhất •Input : Hai số nguyên dương m, n •Output: ước số chung lớn nhất của m, n 52
53. Sơ đồ hoạt động của lệnh điều kiện True B S False True B S1 False S2 53
54. Sơ đồ hoạt động của lệnh lặp không biết trước True B S False Hoặc S B True False 54
55. f. Câu lệnh lặp xác định For i:=1 to n do x:=x+1 Thời gian thực hiện là O(n.1)=O(n) For i:=1 to n do For j:=1 to n do x:=x+1 Thời gian thực hiện là O(n.n)=O(n2) 55
56. Ví dụ: Xác định độ phức tạp •Tính: ex=1+x/1!+x2/2!+ +xn/n! Program EXP1 ; {Tính từng số hạng rồi cộng lại} • Phép toán tích cực p:=p*x/j; Begin • Nó thực hiện Read(x); s:=1; 1+2+ +n=n(n+1)/2 lần For i:=1 to n do ➔ Độ phức tạp T(n)=O(n2) Begin P:=1; For j:=1 to i do p:=p*x/j; S:=s+p; End; End; 56
57. Ví dụ: Xác định độ phức tạp •Tính: ex=1+x/1!+x2/2!+ +xn/n! (cách 2) Tách x2/2!=x/1!.x/2, , xn/n!=xn-1/(n-1)!.x/2 Progam EXP2; Begin Phép toán tích cực p:=p*x/i; Read(x); s:=1;p:=1; Nó thực hiện n lần For i:=1 to n do ➔ Độ phức tạp T(n)=O(n) Begin p:=p*x/i; S:=s+p; End; 57
58. Ví dụ: Xác định phép toán tích cực •Tính: ex=1+x/1!+x2/2!+ +xn/n! Tách x2/2!=x/1!.x/2, , xn/n!=xn-1/(n-1)!.x/2 Progam EXP2; Begin Phép toán tích cực p:=p*x/i; Read(x); s:=1;p:=1; For i:=1 to n do Begin p:=p*x/i; S:=s+p; End; 58
59. Đánh giá độ phức tạp bằng ký pháp O() a. f(n)=n3+4n+4 3 : ➔g(n)=n vì chọn hằng số c=9 và n0 =1 thì n3+4n+4 =1 ➔ Độ phức tạp f(n)=O(n3) b. f(n)=500n2+4nlogn+4n+3 2 ➔g(n)=n : chọn hằng số c=511 và n0 =1 thì 4nlogn =1 4n =1 3 =1 ➔ 500n2+4nlogn+4n+3<= 500n2+ 4n2 + 4n2 + 3n2 =511n2 ➔Độ phức tạp f(n)=O(n2 ) 59
60. Đánh giá độ phức tạp bằng ký pháp O() c. f(n)=n4+4n3+4n2+10000 4 ➔g(n)=n vì chọn hằng số c=10009 và n0 =1 n4+4n3+4n2+10000 =1 n4+4n3+4n2+10000 =1 ➔ Độ phức tạp f(n)=O(n4) d. f(n)=n!+100n3+n2 ➔g(n)=n! vì chọn hằng số c=102 và n0 =10 ta có n!+100n3 +n2 =10 n!+100n3 +n2 =10 ➔ Độ phức tạp f(n)=O(n!) 60
61. Ví dụ: Quy tắc cộng For i:=1 to n do P1 •Thời gian thực hiện P1 là: T (n)=O(n) c[i,i]:=c[i,i]+100 1 S:=0; For i:=1 to n do P2 •Thời gian thực hiện P2 là: 2 For j:=1 to n do T2(n)=O(n ) If c[i,j]>0 then S:=S+c[i,j] ➔Thời gian thực hiện P1 và P2 kế tiếp nhau sẽ là: 2 2 T(n)=T1(n)+T2(n)=O(max(n, n ))= O(n ) 61
62. Ví dụ: Quy tắc nhân Đoạn chương trình P1. For i:=1 to N.N do •Thời gian thực hiện P1 là: T1(n)=O(n). Vì thực hiện n For j:=1 to N do lần tính tổng S:=S+c[j] Đoạn chương trình P2. •Thời gian thực hiện P2 là: • Thời gian thực hiện P1, P2 lồng nhau T (n)=O(n2). Vì thực hiện n2 sẽ là: 2 lần đoạn chương trình P1 2 3 T(n)=T1(n)T2(n)=O(n. n )=O(n ) 62
63. Cú pháp tuần tự S1 S2 S3 Sn 63