CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT DỮ LIỆU

Chia sẻ: Trần Thế Anh | Ngày: | Loại File: PPT | Số trang:29

Thêm vào BST

Báo xấu

135
lượt xem 50
download

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

Tài liệu tham khảo và giới thiệu cấu trúc dữ liệu và giải thuật

Chủ đề:

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

Lưu

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

GiỚI THIỆU CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan 1
Nội dung Giới thiệu chung Mã giả Phương pháp phân tích thiết kế hướng đối tượng Trò chơi Life ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan 2
Giới thiệu chung 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ì ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan 3
Giới thiệu chung (tt) Chương trình: Program = Data structures + Algorithms (Niklaus Wirth) Giải thuật: Các bước (logical steps) giải quyết một bài toán ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan 4
Giới thiệu chung (tt) Vấn đề ngôn ngữ lập trình Dùng C++ 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++ ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan 5
Nội dung Giới thiệu chung Mã giả Phương pháp phân tích thiết kế hướng đối tượng Trò chơi Life ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan 6
Mã giả (Pseudocode) Algorithm Header Algorithm Body ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan 7
Mã giả (Pseudocode) Algorithm Header: Tên Các tham số và kiểu dữ liệu của từng tham số Mục đích Điều kiện ban đầu (Precondition) Kết quả (Postcondition, Return condition) ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan 8
Mã giả (Pseudocode) Algorithm Body: Các phát biểu Thứ tự các phát biểu Các biến Chú thích ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan 9
Ví dụ Algorithm average Pre nothing Post numbers read and their average printed 1 i=0 2 loop (all data not read) 1 i=i+1 2 read number 3 sum = sum + number 3 average = sum / i 4 print average 5 return End average ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan 10
Nội dung Giới thiệu chung Mã giả Phương pháp phân tích thiết kế hướng đối tượng Trò chơi Life ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan 11
Phương pháp lập trình Lập trình thủ tục chương trình chia nhỏ thành các chương trình con riêng rẽ Trình tự nghĩa là các câu lệnh được thực hiện theo trình tự nhất định: trên xuống. Lập trình hướng đối tượng Lấy đối tượng làm nền tảng để xây dựng thuật giải, xây dựng chương trình. ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan 12
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 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan 13
Kiểu dữ liệu Định nghĩa: Một kiểu dữ liệu là một tập hợp, các phần tử của tập hợp này được gọi là trị của các kiểu dữ liệu Kiểu dữ liệu nguyên tố Kiểu có cấu trúc Kiểu dữ liệu trừu tượng Một kiểu dữ liệu trừu tượng là một mô hình toán học đi cùng với những tác vụ được định nghĩa trên mô hình này. ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan 14
Kiểu trừu tượng Kiểu dữ liệu Một kiểu dữ liệu là một tập hợp, các phần tử của tập hợp này được gọi là trị của các kiểu dữ liệu Kiểu dữ liệu nguyên tố Kiểu dữ liệu cấu trúc Kiểu dữ liệ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 ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan 15
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(); ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan 16
Đặ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. ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan 17
Cấu trúc của đối tượng Internal data Internal function method Internal function method method ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan 18
Khai báo một class trên C++ class Student { khai báo một lớp mới private: khai báo dữ liệu bên trong int StudentID; string StudentName; constructor public: copy constructor Student(); Student(const Student &) destructor ~Student() overload assignment operator void operator=(const Student &) void print(); phương thức (hành vi) }; void main() { Student aStudent; khai báo một đối tượng sStudent.print(); gọi phương thức } ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan 19
Nội dung Giới thiệu chung Mã giả Phương pháp phân tích thiết kế hướng đối tượng Trò chơi Life ĐH Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Chương 1: Tổng quan 20