8/4/2020
1
1
BÀI GIẢNG ĐIỆN TỬ
HP:CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Số TC: 3
Bộ môn: Tin học
Cấu trúc dữ liệu và giải thuật
2
Giới thiệu học phần
Số tín chỉ:3 (36,9)
Mục tiêu: Cung cấp:
▪Một số khái niệm cơ bản về giải thuật và cấu trúc dữ
liệu; vai trò của cấu trúc dữ liệu và giải thuật (CTDL
và GT) trong hệ thống thông tin (HTTT); Một số cấu
trúc dữ liệu cơ bản bao gồm:Mảng (Array), Danh
sách (List), Danh sách liên kết (Linked List), Ngăn
xếp (Stack) và Hàng đợi (Queue), và Cây (Tree)
Cấu trúc dữ liệu và giải thuật
8/4/2020
2
3
Giới thiệu học phần
Nội dung chính:
Chương 1: Các khái niệm cơ bản về CTDL & GT (6t)
Chương 2: Mảng và danh sách (12t)
Chương 3: Cây (12t)
Chương 4: Một số giải thuật sắp xếp và tìm kiếm (15t)
Cấu trúc dữ liệu và giải thuật
4
Tài liệu tham khảo
❖Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật, NXB
ĐHQGHN, 2008
❖Nguyễn ĐÌnh Hóa, Cấu trúc dữ liệu và giải thuật, 2008,
NXB ĐHQGHN
❖Lê Minh Hoàng, Bài giảng chuyên đề
❖https://www.tutorialspoint.com/data_structures_algorit
hms/
❖https://www.e-
reading.club/bookreader.php/138793/Advanced_C.pdf.
Cấu trúc dữ liệu và giải thuật
8/4/2020
3
5
Chương 1. Các khái niệm cơ bản về CTDL & GT
1.1 Cấu trúc dữ liệu
1.2 Giải thuật
Cấu trúc dữ liệu và giải thuật
6
1.1 Cấu trúc dữ liệu (Data Structures)
1.1.1 Khái niệm chung
1.1.2 Các vấn đề liên quan
1.1.3 Một số cấu trúc dữ liệu cơ bản
Cấu trúc dữ liệu và giải thuật
8/4/2020
4
7
1.1.1 Khái niệm chung
❖Mục tiêu của tin học?
❖Dữ liệu là gì? →Kiểu dữ liệu ?(kiểu cơ sở/ kiểu có cấu
trúc phức tạp)
❖Khái niệm chung: CTDL là một cách thể hiện và tổ chức
dữ liệu trong máy tính sao cho nó được sử dụng một cách
có hiệu quả nhất.
❖Khái niệm khác: CTDL là một dữ liệu phức hợp, gồm
nhiều thành phần dữ liệu, mỗi thành phần hoặc là dữ liệu
cơ sở hoặc là một CTDL đã được xây dựng. Các thành
phần dữ liệu tạo nên một CTDL được liên kết với nhau theo
một cách nào đó.
Cấu trúc dữ liệu và giải thuật
8
1.1.2 Các vấn đề liên quan
Tầm quan trọng của việc lựa chọn CTDL
▪Tổ chức dữ liệu : dl vào/ra/trung gian
▪Xây dựng giải thuật
→Các cách cài đặt khác nhau
→Thực hiện thao tác thuận lợi/khôngthuận lợi
→CTDL thay đổi →Thuật toán thay đổi
Cấu trúc dữ liệu và giải thuật
8/4/2020
5
9
1.1.2 Các vấn đề liên quan
Các tiêu chuẩn khi lựa chọn CTDL
▪CTDL phải biểu diễn được đầy đủ các thông tin của
bài toán. (in/out) →phản ánh đúng thực tế
▪Cài đặt được trên máy tính và ngôn ngữ lập trình đang
sử dụng
▪Phù hợp với các thao tác của thuật toán (đặc biệt thao
tác được sử dụng nhiều) →phát triển thuật toán đơn
giản và đạt hiệu quả.
▪Tiết kiệm tài nguyên
Cấu trúc dữ liệu và giải thuật
10
1.1.3 Một số cấu trúc dữ liệu cơ bản
❖Mảng (array)
❖Bản ghi (record)/cấu trúc (struct)
❖Tập hợp (set)
❖Tệp (file)
❖Xâu (string)
❖….(bảng băm, danh sách liên kết)
Cấu trúc dữ liệu và giải thuật