Bài giảng Cấu trúc Dữ liệu và giải thuật - Chương 1: Giới thiệu chung - Nguyễn Thị Xuân Hương

Nội dung text: Bài giảng Cấu trúc Dữ liệu và giải thuật - Chương 1: Giới thiệu chung - Nguyễn Thị Xuân Hương

1. TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG KHOA CÔNG NGHỆ THÔNG TIN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Ths. Nguyễn Thị Xuân Hƣơng 1
2. THÔNG TIN MÔN HỌC •Thời lượng: 67.5 tiết –Số tiết lý thuyết: 51 tiết thực dạy + 3 tiết kiểm tra –Số tiết thực hành : 13.5 –Số tiết sinh viên tự học: 112 •Học liệu: •Tài liệu bắt buộc –Cấu trúc dữ liệu & giải thuật – Đỗ Xuân Lôi – NXB Thống kê –Cấu trúc dữ liệu & Thuật toán – Đinh Mạnh Tƣờng – NXB KHKT –Toán rời rạc – Nguyễn Tô Thành, Nguyễn Đức Nghĩa – NXB KHKT •Tài liệu tham khảo: –Toán rời rạc ứng dụng trong tin học – Sách dịch 2 –Tài liệu WEB
3. NỘI DUNG Chƣơng 1: GIỚI THIỆU CHUNG Chƣơng 2: THIẾT KẾ VÀ ĐÁNH GIÁ THUẬT TOÁN Chƣơng 3: CÁC CẤU TRÚC DỮ LIỆU CƠ BẢN Chƣơng 4: DANH SÁCH TUYẾN TÍNH Chƣơng 5: CẤU TRÚC CÂY Chƣơng 6: CẤU TRÚC TẬP HỢP Chƣơng 7: ĐỒ THỊ Chƣơng 8: THUẬT TOÁN SẮP XẾP Chƣơng 9: THUẬT TOÁN TÌM KIẾM Chƣơng 10: CÁC CHIẾN LƢỢC THIẾT KẾ THUẬT TOÁN 3
4. Chương 1: GIỚI THIỆU CHUNG 1.1 Mối quan hệ giữa cấu trúc dữ liệu và giải thuật - Giải thuật (algorithms): là một dãy các chỉ thị (statements) chặt chẽ và rõ ràng xác định một trình tự các thao tác trên một số đối tƣợng nào đó, sao cho sau một số bƣớc hữu hạn nhất định cho kết quả mong muốn. - Dữ liệu (data): là các đối tƣợng để xử lý trên máy tính – biểu diễn các thông tin cần thiết cho bài toán. - Cấu trúc dữ liệu (data structures): là cách kết hợp các dữ liệu theo cấu trúc thích hợp -> các phép xử lý trên đó thuận lợi hơn. 4
5. Chương 1: GIỚI THIỆU CHUNG 1.1 Mối quan hệ giữa cấu trúc dữ liệu và giải thuật Thảo luận: - Những tác động qua lại giữa cấu trúc dữ liệu và giải thuật thể hiện như thế nào? Ví dụ thực tế nào bạn cho thấy điều đó? 5
6. Chương 1: GIỚI THIỆU CHUNG 1.2 Các vấn đề liên quan đến cấu trúc dữ liệu - Tại sao cần có Cấu trúc dữ liệu? - Một Cấu trúc dữ liệu mới bao gồm: định nghĩa (các thành phần biểu diễn của nó), các phép toán cơ bản: Khởi tạo, hủy một cấu trúc, phép bổ sung (insertion), phép loại bỏ (deletion), - Cấu trúc lưu trữ: cách biểu diễn Cấu trúc dữ liệu trên máy tính (NNLT) + Lưu trữ trong + Lưu trữ ngoài? -Cấu trúc dữ liệu tiền định (predifined data structures): VD: mảng, kiểu cấu trúc (struct), 6
7. Chương 1: GIỚI THIỆU CHUNG 1.2 Các vấn đề liên quan đến cấu trúc dữ liệu Thảo luận: -Với các cấu trúc dữ liệu đã được định nghĩa: biểu diễn chúng trên máy tính như thế nào? - Cấu trúc dữ liệu và cấu trúc lưu trữ khác nhau ở điểm nào? - Sử dụng các Cấu trúc dữ liệu tiền định như thế nào?Các cấu trúc dữ liệu tiền định trong một ngôn ngữ có đáp ứng được mọi yêu cầu về tổ chức dữ liệu không? 7
8. Chương 1: GIỚI THIỆU CHUNG 1.3 Ngôn ngữ diễn đạt giải thuật - Ngôn ngữ tự nhiên (liệt kê) - Lƣu đồ khối. - Câu lệnh chƣơng trình: 8
9. Chương 1: GIỚI THIỆU CHUNG 1.3 Ngôn ngữ diễn đạt giải thuật -Lƣu đồ khối. BẮT ĐẦU LỆNH ĐIỀU KẾT THÚC KIỆN NHẬP/ XUẤT 9
10. Chương 1: GIỚI THIỆU CHUNG 1.3 Ngôn ngữ diễn đạt giải thuật Ngôn ngữ lập trình C/C++ Ngôn ngữ lập trình Pascal Lệnh gán: Biến = Biến := lệnh ghép: { } Begin End ; lệnh tuần tự : lệnh1 ; Lệnh 2 ; lệnh1 ; Lệnh 2 ; Lệnh điều kiện: Dạng 1: if ( ) ; Dạng 1: if then ; Dạng 2: Dạng 2: if ( ) ; if then else ; Else ; 10
11. Chương 1: GIỚI THIỆU CHUNG 1.3 Ngôn ngữ diễn đạt giải thuật Ngôn ngữ lập trình C/C++ Ngôn ngữ lập trình Pascal lệnh tuyển switch (bt) case of { hằng 1: ; case : ; hằng 2: ; break; case : ; hằng n: break; else ; default ; end; } 11
12. Chương 1: GIỚI THIỆU CHUNG 1.3 Ngôn ngữ diễn đạt giải thuật Ngôn ngữ lập trình C/C++ Ngôn ngữ lập trình Pascal Lệnh lặp for (bt1; bt2;bt3) for := to do VD: for(i=1;i ; ; VD: for i:=1 to n do ; while (btđk) ; do while (btđk); while (btđk) do ; Lệnh nhảy: repeat ; until (!btđk); goto ; Lệnh nhập/xuất goto ; cout > ; writeln(item1,item2, ); readln(biến); 12
13. Chương 1: GIỚI THIỆU CHUNG 1.3 Ngôn ngữ diễn đạt giải thuật Ngôn ngữ lập trình C/C++ Ngôn ngữ lập trình Pascal Khai báo hàm void Tên_hàm (ds tham số procedure Tên_hàm (ds tham số hình thức) hình thức); type Tên_hàm(ds tham số function Tên_hàm (ds tham số hình hình thức) thức): type; Lời gọi hàm: Tên_hàm(ds tham số thực Tên_hàm(ds tham số thực sự); sự); 13
14. Chương 1: GIỚI THIỆU CHUNG 1.3 Ngôn ngữ diễn đạt giải thuật Thảo luận: Sử dụng các ngôn ngữ diễn đạt trong trường hợp nào? Ưu nhược điểm? 14
15. Chương 1: GIỚI THIỆU CHUNG 1.4 Bài tập về nhà: - Hãy nêu các tính chất của một giải thuật và cho ví dụ minh họa. - Hãy vẽ sơ đồ khối để minh họa giải thuật cho các bài toán sau: 1. Sắp xếp dãy n số nguyên theo thứ tự tăng dần 2. Tìm các số Fibonaci nhỏ hơn số nguyên k cho trƣớc. ( biết rằng các số Fibonaci đƣợc xây dựng nhƣ sau: F1=1, F2=1, . Fn=Fn-2+Fn-1) 1 1 1 3. Tính tổng sau: S 1 2! 3! n! 4. Tính tổng và trung bình cộng của các số nguyên chẵn trong một dãy số nguyên có n phần tử. 15