Cấu trúc dữ liệu và giải thuật - Dương Thành Phết

Trong khoa học máy tính, cấu trúc dữ liệu là một cách lưu dữ liệu trong máy tính sao cho nó có thể được sử dụng một cách hiệu quả.Trong thiết kế nhiều loại chương trình, việc chọn cấu trúc dữ liệu là vấn đề quan trọng. Kinh nghiệm trong việc xây dựng các hệ thóng lớn cho thấy khó khăn của việc triển khai chương trình, chất lượng và hiệu năng của kết quả cuối cùng phụ thuộc rất nhiều....
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật - Dương Thành Phết Trường Đại Học Kinh Tế Kỹ Thuật Bình Dương Khoa Kỹ Thuật - Công Nghệ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Giảng viên: Dương Thành Phết Email: phetcm@gmail.com Website: http://www.thayphet.net Tel: 0918158670 – 08.3.7900261 1 Lời Nói Đầu  Cấu trúc DL & GT là 1 trong những môn học cơ bản, quan trong nhất cho sinh viên ngành CNTT Chương trình = Cấu trúc dữ liệu + Giải thuật  Cấu trúc dữ liệu: Là phương pháp tổ chức lưu trữ và sử dụng dữ liệu trong máy tính một cách hiệu qu ả nhất.  Giải thuật (thuật toán): Cách thức để xử lý và khai thác dữ liệu  Cấu trúc dữ liệu và giải thuật là 2 yếu tố có quan hệ chặt chẽ và không thể tách rời. 2 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net Mục tiêu Sau khi kết thúc học phần, sinh viên có khả năng:  Mô tả được vai trò của cấu trúc dữ liệu và giải thu ật  Đánh giá, so sánh được độ phức tạp của các giải thuật  Trình bày được tư tưởng và minh họa các giải thuật tìm kiếm, sắp xếp trên mảng một chiều  Trình bày được các khái niệm, thao tác trên các cấu trúc dữ liệu như: danh sách liên kết đơn, hàng đợi, ngăn xếp, cây nhị phân tìm kiếm  Kỹ năng thực hành cài đặt được các giải thuật và các thao tác trên các cấu trúc dữ liệu bằng ngôn ngữ C/ C++ 3 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net Điều kiện  Đã học qua môn Tin học đại cương  Đã học qua môn kỹ thuật lập trình C Thời lượng Tổng số: 45 tiết lý thuyết: 45 tiết Tự học: 90 giờ 4 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net Đánh giá kết quả học tập  Tham gia học tập trên lớp (đi học đầy đủ, chuẩn bị bài tốt, tích cực thảo luận và phát biểu, …): 10%  Kiểm tra giữa kỳ: 20% (Tự luận)  Thuyết trình: 20%(Thực hiện theo nhóm)  Kiểm tra cuối kỳ : 50% (Tự luận, thời gian 60’, không sử dụng tài liệu) 5 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net Nhiệm vụ của sinh viên  Xem bài giảng và tài liệu tham khảo trước mỗi buổi lên lớp.  Tích cực tham gia phát biểu, đóng góp ý kiến xây dựng bài.  Chia nhóm để làm bài tập và báo cáo do giảng viên giao.  Tự giác tìm tài liệu, nghiên cứu và thảo luận nhóm khi ở nhà.  Nghiêm túc làm tất cả các bài tập trong giờ thực hành. 6 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net Phần mềm thực hành  Microsoft Visual C++ 6.0 hoặc  Microsoft Visual .Net 2005 Viết ứng dụng dạng Console 7 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net Tài liệu học tập & Tài liệu tham khảo [1] Dương Thành Phết, Bài giảng Cấu Trúc Dữ Liệu & Giải thu ật, Khoa CNTT Trường ĐH KTKT Bình Dương(2010). [2] Dương Thành Phết, Bài tập Cấu Trúc Dữ Liệu & Giải thuật, Khoa CNTT Trường ĐH KTKT Bình Dương(2010 [3]. Trần Hạnh Nhi – Dương Anh Đức, Cấu trúc dữ liệu, Khoa CNTT, Trường ĐHKHTN – ĐHQG TP.HCM ------------------------------------------------------------------------ [4]. Nguyễn Trung Trực, Cấu trúc dữ liệu, Khoa CNTT, trường ĐHBK TP.HCM [5]. Nguyễn Xuân Huy. Thuật toán. Nhà xuất bản Thống kê, 1988 [6]. Algorithms + Data Structure = Programs (Sách dịch) - N.Wirth. NXB Thống kê, 1981. [7]. Programs and Data Structures in C - Leendert Ammeraal. John Willey & Sons Press. 8 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net NỘI DỤNG  Chương 1: Tổng quan về cấu trúc dữ liệu và thu ật toán  Chương 2: Tìm kiếm và sắp xếp  Chương 3: Cấu trúc dữ liệu động  Chương 4: Cấu trúc cây 9 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net Chương 1 TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU & THUẬT TOÁN 1.1. Khái niệm về cấu trúc dữ liệu và giải thuật 1.1.1. Cấu trúc dữ liệu 1.1.2. Giải thuật 1.1.3. Sự liên hệ giữa giải thuật và cấu trúc dữ liệu 1.2. Phân tích giải thuật 1.2.1. Phân tích thời gian thực hiện giải thuật 1.2.2. Độ phức tạp tính toán của giải thuật 1.2.3. Xác định độ phức tạp tính toán 1.3. Bài tập 10 10 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net Chương 2 TÌM KiẾM & SẮP XẾP 2.1. Các giải thuật tìm kiếm 2.1.1. Bài toán tìm kiếm 2.1.2. Giải thuật tìm kiếm tuyến tính 2.1.3. Giải thuật Tìm kiếm nhị phân 2.2. Các giải thuật sắp xếp 2.2.1. Bài toán sắp xếp 2.2.2 Giải thuật đổi chổ trực tiếp –Interchange Sort 2.2.3 Giải thuật chọn trực tiếp-Selection Sort 2.2.4 Giải thuật chèn trực tiếp-Insert Sort 2.2.5 Giải thuật nổi bọt – Bubble Sort 2.2.6 Giải thuật nhanh – Quick Sort 2 ...