Bài 1:
TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU
VÀ GIẢI THUẬT
Tìm hiểu khái niệm cấu trúc dữ liệu
Dữ liệu, Cấu trúc dữ liệu
Các kiểu cấu trúc dữ liệu
Tìm hiểu khái niệm giải thuật (thuật toán, thuật giải)
Khái niệm về giải thuật
Biểu diễn giải thuật
Độ phức tạp của giải thuật
Mối liên hệ giữa cấu trúc dữ liệu và giải thuật
Mục tiêu bài học hôm nay
2
Slide 1 - Tổng quan về CTDL và GT
Tại sao sử dụng máy tính để xử lý dữ liệu
Nhanh hơn, chính xác hơn
Giải quyết nhiều bài toán đòi hỏi khối lượng tính toán cực lớn,
hoặc những bài toán phức tạp với khối lượng dữ liệu lớn
Phương pháp?
Nhờ vào các thuật toán hiệu quả, thông minh -> chi phí thấp
Nhờ vào sự nâng cấp cấu hình máy -> chi phí cao
Dữ liệu và Giải thuật
3
Slide 1 - Tổng quan về CTDL và GT
Trong tin học: Dữ liệu để biểu diễn các thông tin cần thiết
cho bài toán.
Các dữ liệu máy tính gồm: dữ liệu đầu vào, dữ liệu trung
gian, dữ liệu đầu ra.
Khái niệm Dữ liệu
4
Slide 1 - Tổng quan về CTDL và GT

Slide 1 - Tổng quan về CTDL và GT
Ví dụ: một số kiểu dữ liệu cơ sở được định nghĩa trong
Visual Basic:
Kiểu dữ liệu cơ sở
9
Slide 1 - Tổng quan về CTDL và GT
Tên kiểu Kích thước Miền giá trị
Byte 1 byte 0 -> 255 (không dấu)
Boolean Tùy thuộc vào nền tảng
(thường là 1 byte)
True hoặc False
Integer 4 byte -2,147,483,648 -> 2,147,483,647
(có dấu)
Long 8 byte -9,223,372,036,854,775,808 ->
9,223,372,036,854,775,807
(9.2 E+18 †) (có dấu)
Date 8 byte 0:00:00 ngày 1/1/0001 tới 11:59:59
ngày 31/12/9999
Char 2 byte 0 -> 65535 (không dấu)
Kiểu chuỗi kí tự:
Ví dụ: chuỗi kí tự “BOOKS”
Kiểu dữ liệu có cấu trúc
10
Slide 1 - Tổng quan về CTDL và GT
Kiểu mảng (array):
Ví dụ mảng 1 chiều
Ví dụ mảng 2 chiều
Kiểu dữ liệu có cấu trúc
11
Slide 1 - Tổng quan về CTDL và GT

Trần B | 19 | 2A | 6
Vũ D | 18 | 3A | 8
Slide 1 - Tổng quan về CTDL và GT
Nếu tổ chức dưới dạng đối tượng (object)
sẽ có 3 đối tượng
Ví dụ cấu trúc dữ liệu
Slide 1 - Tổng quan về CTDL và GT
14
Sinh viên
Họ tên: Trần B
Tuổi: 19
SBD: 2A
Toán: 6
(các phương thức)
Sinh viên
Họ tên: Nguyễn An
Tuổi: 18
SBD: 1A
Toán: 10
(các phương thức)
Sinh viên
Họ tên: Vũ D
Tuổi: 18
SBD: 3A
Toán: 8
(các phương thức)
Một CTDL tốt phải thỏa mãn:
Phản ánh đúng thực tế
Phù hợp với các thao tác trên đó
Tiết kiệm tài nguyên hệ thống

Slide 1 - Tổng quan về CTDL và GT
Tính Đơn trị (Uniqueness): Các kết quả trung gian của
từng bước thực hiện giải thuật được xác định một cách
đơn trị và chỉ phụ thuộc đầu vào và các kết quả của các
bước trước.
Tính Tổng quát (Generality): Giải thuật có thể áp dụng
để giải mọi bài toán có dạng đã cho.
Các đặc trưng của giải thuật
Slide 1 - Tổng quan về CTDL và GT
19
Các cách biểu diễn giải thuật:
Ngôn ngữ tự nhiên
Lưu đồ (flow chart)
Mã giả (Pseudo code)
Ngôn ngữ lập trình
Các cách biểu diễn giải thuật
20
Slide 1 - Tổng quan về CTDL và GT
Liệt kê tuần tự các bước bằng ngôn ngữ tự nhiên để
biễu diễn thuật toán.
Ưu điểm:
Đơn giản, không cần kiến thức về cách biểu diễn (mã giả, lưu
đồ, )
Nhược điểm:
Dài dòng, không cấu trúc.
Đôi lúc khó hiểu, không diễn đạt được thuật toán.
Biểu diễn bằng ngôn ngữ tự nhiên
21
Slide 1 - Tổng quan về CTDL và GT
Ngôn ngữ tựa ngôn ngữ lập trình:

24
Bắt đầu Kết thúc
2
Slide 1 - Tổng quan về CTDL và GT
Ví dụ lưu đồ
Slide 1 - Tổng quan về CTDL và GT
25