Ktl-icon-tai-lieu

Chương 1: Tổng quan cấu trúc dữ liệu

Được đăng lên bởi bai-tap-lon
Số trang: 7 trang   |   Lượt xem: 369 lần   |   Lượt tải: 0 lần
A
C

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

B
F
D
E

Chương 1: Tổng quan

G
K
H

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

2

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

3

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

ĐH Bách Khoa Tp.HCM

Khoa Công nghệ Thông tin

Chương 1: Tổng quan

4

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

5

Trò chơi Life – Mã C++ cập nhật
void Life::update()
/* Pre: grid đang chứa một trạng thái của thực thể sống
Post: grid sẽ chứa trạng thái tiến hóa mới của thực thể sống này */
{
int row, col;
int new_grid[maxrow + 2][maxcol + 2];
//Chứa trạng thái mới vào đây
for (row = 1; row <= maxrow; row++)
for (col = 1; col <= maxcol; col++)
switch (neighbor_count(row, col)) {
case 2:
//Trạng thái của tế bào không đổi
new_grid[row][col] = grid[row][col]; break;
case 3:
//Tế bào sẽ sống
new_grid[row][col] = 1; break;
default:
//Tế bào sẽ chết
new_grid[row][col] = 0;
}
for (row = 1; row <= maxrow; row++)
for (col = 1; col <= maxcol; col++)
grid[row][col] = new_grid[row][col];
//Cập nhật các tế bào cùng lúc
}
ĐH Bách Khoa Tp.HCM

Khoa Công nghệ Thông tin

Chương 1: Tổng quan

19

Kết luận
Sự liên quan giữa CTDL và giải thuật:
Cấu trúc dữ liệu cụ thể: chọn giải thuật
Giải thuật cụ thể: chọn cấu trúc dữ liệu

Cấu trúc dữ liệu trừu tượng:
Dữ liệu cụ thể bên trong
Các phương thức: interface ra bên ngoài
Thích hợp cho phương pháp hướng đối tượng

ĐH Bách Khoa Tp.HCM

Khoa Công nghệ Thông tin

Chương 1: Tổng quan

20

...
A
B
C
D
F
G
E
H
K
C U TRÚC D LI U VÀ
C U TRÚC D LI U VÀ
GI I THU T (501040)
GI I THU T (501040)
Ch ng 1: T ng quanươ
Ch ng 1: T ng quanươ
Chương 1: Tổng quan cấu trúc dữ liệu - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
Chương 1: Tổng quan cấu trúc dữ liệu - Người đăng: bai-tap-lon
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
7 Vietnamese
Chương 1: Tổng quan cấu trúc dữ liệu 9 10 359