GIỚI THIỆU MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

Chia sẻ: Batman_1 Batman_1 | Ngày: | Loại File: PPT | Số trang:33

Thêm vào BST

Báo xấu

131
lượt xem 13
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Môn học giới thiệu Các cấu trúc dữ liệu cơ bản Các giải thuật điển hình trên các cấu trúc dữ liệu đó Dùng phương pháp hướng đối tượng. Ngôn ngữ lập trình minh hoạ Mã giả (pseudocode) C++

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: GIỚI THIỆU MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Giới thiệu môn học
Giới thiệu Môn học giới thiệu   Các cấu trúc dữ liệu cơ bản  Các giải thuật điển hình trên các cấu trúc d ữ li ệu đó Dùng phương pháp hướng đối tượng.  Ngôn ngữ lập trình minh hoạ   Mã giả (pseudocode)  C++ 2 Chương 1: Tổng quan
Nội dung Chương 1. Tổng quan Chương 2. Stack Chương 3. Queue Chương 4. Stack và Queue liên kết Chương 5. Đệ qui Chương 6. List và String Chương 7. Tìm kiếm Chương 8. Sắp xếp Chương 10. Cây nhị phân Chương 11. Cây nhiều nhánh Chương 9. Bảng và truy xuất thông tin 3 Chương 1: Tổng quan
Tài liệu tham khảo [1] Kruse, R. L., and Ryba, A. J. 1999. Data Structures and  Program Design in C++. Prentice-Hall Inc. [2] Trân, N. N. B. 2001. Giáo trình Cấu trúc Dữ liệu và Giải  thuật. KhoaCNTT, ĐH Bách KhoaTp.HCM [3] Jesse Liberty, 1997. Teach Yourself C++ in 21 days. ISBN:  0-672-31070-8, SAMS [4] Davis Chapman, 1998. Teach Yourself Visual C++ 6 in 21  days. ISBN: 0-672-31240-9, SAMS [5] Trần Hạnh Nhi – Dương Anh Đức, 1996. Giáo trình cấu  trúc dữ liệu – Đại học Khoa học Tự nhiên TP HCM [6] Yediyah Langsam, Moshe J. Augenstein, Aaron M.  Tenenbaum., 2006 Data structures using C and C++. Prentice Hall 4 Chương 1: Tổng quan
Vấn đề ngôn ngữ lập trình Dùng C++ để diễn đạt => Có vấn đề?  Mã giả (pseudo code)   Giả lập, thường là dễ hiểu, không chi tiết đến các k ỹ thu ật lập trình  Ở cấp độ hết sức tổng quát: gần ngôn ngữ tự nhiên  Hoặc rất chi tiết: như dùng ngôn ngữ tựa Pascal, t ựa C++ 5 Chương 1: Tổng quan
Giải thuật bằng mã giả Ví dụ: Mã giả của bubble sort  Giải thuật 1 Giải thuật 2 Algorithm Bubble sort Algorithm Bubble sort Input: The list A of n elements is Input: The list A of n elements is given given Output: The list A is sorted Output: The list A is sorted 1. for outter in 0..(n-2) 1. loop for n time 1.1. for inner in 0..(n-2- outter) 1.1. for each pair in the list 1.1.1. if Ainner+1 < Ainner 1.1.1. if it is not in ordered 1.1.1.1. swap Ainner, Ainner+1 1.1.1.1. exchange them End Bubble sort End Bubble sort 6 Chương 1: Tổng quan
Giải thuật bằng ngôn ngữ lập trình Ví dụ: Lập trình cụ thể Bubble sort  Giải thuật 1: Pascal Giải thuật 2: C++ procedure BubbleSort(var A: list); void BubbleSort(list A) var i,j: int; { begin int i, j; for i := 1 to n-1 do for (i=0; i < n-2; i++) for j := 1 to (n-1-i) do for (j=0; j
So sánh mã giả và NNLT Nhận xét:   Mã giả 1: gần với cách trao đổi của con người nh ất nh ưng khó lập trình nhất  Mã giả 2: dễ lập trình hơn Phương pháp:   Đầu tiên: cách giải quyết vấn đề bằng máy tính s ố (giải thuật bằng mã giả)  Sau đó: ngôn ngữ lập trình cụ th ể Học:   Nhớ giải thuật (mã giả)  Dùng NNLT cụ thể để minh chứng 8 Chương 1: Tổng quan
Cấu trúc môn học Cấu trúc:   Lý thuyết: 45 tiết  Thực hành: 30 tiết  Đồ án môn học: làm theo nhóm Tỉ lệ điểm:   Kiểm tra giữa kỳ : 20%  Thực hành và bài tập lớn: 20%  Thi cuối kỳ: 60% 9 Chương 1: Tổng quan
Bài tập thực hành Đề bài tập:   Bài tập cho hàng tuần (file)  Các bài trong tài liệu tham khảo  Tự sưu tầm Giải bài tập:   Giờ thực hành  Tự giải bài tập 10 Chương 1: Tổng quan
Đồ án môn học Mục đích:   Hiểu bài  Làm bài ở nhà và theo nhóm Chọn đồ án, nộp theo đúng thời hạn quy định  Đánh giá: thang điểm 10/10  Hình thức: Báo cáo và mã lệnh, nộp thông qua lớp tr ưởng ho ặc  địa chỉ mail. 11 Chương 1: Tổng quan
Thực hành Mục đích:   Rèn luyện khả năng làm bài độc lập  Sử dụng nhuần nhuyễn các kiến thức đã h ọc.  Giải bài tập + Trao đổi các thắc mắc Thời lượng:   30 tiết (10 buổi) 12 Chương 1: Tổng quan
Các hình thức kiểm tra Thi giữa kỳ (20%)   Thực hiện giải thuật bằng tay  Thiết kế cấu trúc dữ liệu theo yêu cầu  Đánh giá độ phức tập giải thuật  Viết mã lệnh Đồ án môn học (30%)   Trình bày giải thuật chi tiết bằng mã giả  Hiện thực bằng ngôn ngữ lập trình C++  Báo cáo Thi cuối kỳ (50%)   Chỉ được thi cuối kỳ khi các điểm thi giữa kỳ và đồ án >= 5  SV sẽ bị cấm thi nếu nghỉ quá 20% số tiết 13 Chương 1: Tổng quan
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Chương 1: Tổng quan
Giải bài toán bằng phần mềm 1. Xác định bài toán 2. Thiết kế phần mềm 3. Thiết kế dữ liệu 4. Thiết kế và phân tích giải thuật 5. Lập trình và gỡ rối 6. Kiểm tra phần mềm 7. Bảo trì 15 Chương 1: Tổng quan
Lập trình hướng đối tượng (OOP) Chương trình = tập các đối tượng tương tác nhau.  Đối tượng (object) = thuộc tính + tác vụ  local data of object đối tượng (object) entry local data of operation 16 Chương 1: Tổng quan
Kiểu trừu tượng Kiểu trừu tượng (abstract type): định nghĩa interface (t ập các  entry) Entry   Tên method  Danh sách tham số hình thức  Đặc tả chức năng Chưa có dữ liệu bên trong, chưa dùng được  Chỉ dùng để thiết kế ý niệm  17 Chương 1: Tổng quan
Hiện thực và sử dụng Class: hiện thực của abstract type   Định nghĩa các dữ liệu  Định nghĩa các phương thức + hàm ph ụ tr ợ (n ội b ộ)  Định nghĩa các phương phức ‘constructor’ và ‘destructor’ n ếu c ầ n Đối tượng = một instance của một class  Thông điệp (message):   dùng tương tác lẫn nhau = lời gọi phương th ức c ủa các đ ối tượng Student aStudent; aStudent.print(); 18 Chương 1: Tổng quan
Đặc điểm của OOP Tính bao đóng:   Che dấu cấu trúc dữ liệu bên trong.  Che dấu cách thức hiện thực đối tượng. Kế thừa:   Định nghĩa thêm các dữ liệu và ph ương thức cần thi ết t ừ một class có sẵn.  Cho phép overwrite/overload.  Cho phép dùng thay thế và khả năng dynamic biding. Bao gộp:   Một đối tượng chứa nhiều đối tượng khác. 19 Chương 1: Tổng quan
Cấu trúc của đối tượng Internal data Internal function method Internal function method method 20 Chương 1: Tổng quan