TRƯỜNG ĐH CÔNG NGHIỆP TP. HCM
TT CNTT
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Giáo viên: Trần Thị Kim Chi
DATA STRUCTURES & ALGORITHMS

Giới thiệu

Mục tiêu

Nắm vững khái niệm kiểu dữ liệu, kiểu dữ liệu trừu tượng.

Nắm vững và cài đặt được các kiểu dữ liệu trừu tượng cơ
bản như danh sách, ngăn xếp, hàng đợi, cây, tập hợp, bảng
băm, đồ thị bằng một ngôn ngữ lập trình căn bản.

Vận dụng được các kiểu dữ liệu trừu tượng để giải quyết bài
toán đơn giản trong thực tế.

Ngôn ngữ lập trình minh hoạ

Mã giả (pseudocode)

C++

Nội dung chương trình
TT Nội dung
Số
tiết
Phân bổ thời gian

Các bảng và phục hồi thông tin 10 6
4 10
9
Cây nhị phân 14 9
5 10
10
Cây nhiều nhánh 5 3
2 10
TỔNG 75
45 30 105

Kiến thức tiên quyết

Đã học môn phương pháp lập trình.

Kiến thức về kỹ thuật lập trình.

Sử dụng thành thạo ngôn ngữ C++

Tài liệu

Tài liệu học tập:
[1] C & Data Structures, P. S. Deshpande, O. G. Kakde -
CHARLES RIVER MEDIA, INC. Hingham, Massachusetts.
[2] Robert L.Kruse, Alexander J.Ryba, Data Structures And
Program Design In C++, Prentice-Hall International Inc., 1999.
[3] Bài giảng & Bài thực hành CTDL - Trường ĐHCN.

Tài liệu tham khảo:
[1] Giáo trình Cấu trúc dữ liệu 1, Trần Hạnh Nhi – Dương Anh

1.3. Ôn lại ngôn ngữ C++
1.4. Các kiểu dữ liệu
1.5. Kiểu dữ liệu trừu tượng
1.6. Hàm
1.7. Tổng kết
1.8. Câu hỏi và bài tập
Chương 1


Dữ liệu có thể là dữ liệu đưa vào (input data), dữ liệu trung
gian hoặc dữ liệu đưa ra (output data). Mỗi dữ liệu có một kiểu
dữ liệu riêng. Kiểu dữ liệu có thể là kiểu cơ bản hay kiểu trừu
tượng

Cấu trúc dữ liệu là sự sắp xếp có logic của thành phần dữ liệu
được kết hợp với nhau và là tập hợp các thao tác chúng ta cần
để truy xuất các thành phần dữ liệu.

Ví dụ: thư viện

Bao gồm các sách

Truy cập/tìm kiếm một cuốn sách nào đó đòi hỏi phải biết cách sắp xếp của các sách

Người dùng truy cập sách chỉ thông qua người quản lý thư viện.
Cấu trúc dữ liệu

Một cấu trúc dữ liệu tốt phải thỏa mãn:

Phản ánh đúng thực tế: Cần xem xét kỹ lưỡng cũng như dự

để đạt được kết quả mong muốn.

Giải thuật được xây dựng trên cơ sở của cấu trúc dữ liệu đã
được chọn.

Giải thuật có thể được minh họa bằng ngôn ngữ tự nhiên
(natural language), bằng sơ đồ (flow chart) hoặc bằng mã giả
(pseudo code).

Ví dụ: Sắp xếp các phần tử
1 2 3 4 5 6 7
1
2
3
4
5
6
7


Ví dụ: Tính tổng các số nguyên lẻ từ
1

n

B1: S=0

B2: i=1

B3: Nếu i>n thì sang B7, ngược lại sang B4

trình

Đánh giá CTDL và GT
1. Các tiêu chuẩn đánh giá cấu trúc dữ liệu

Để đánh giá một cấu trúc dữ liệu chúng ta
thường dựa vào một số tiêu chí sau:

Cấu trúc dữ liệu phải tiết kiệm tài nguyên (bộ nhớ trong),

Cấu trúc dữ liệu phải phản ảnh đúng thực tế của bài toán,

Cấu trúc dữ liệu phải dễ dàng trong việc thao tác dữ liệu.

Đánh giá CTDL và GT
Thời gian thực hiện chương trình.

Thời gian thực hiện một chương trình là một hàm của kích thước
dữ liệu vào, ký hiệu T(n) trong đó n là kích thước (độ lớn) của
dữ liệu vào.

Ví dụ: Chương trình tính tổng của n số có thời gian thực hiện là
T(n) = cn trong đó c là một hằng số.

Thời gian thực hiện chương trình là một hàm không âm, tức là
T(n)
≥
0
∀
n

2
≤ 4n
2
với mọi n ≥ 1, tức là tỷ suất tăng của
T(n) là n
2
.

Ví dụ 1-4: Tỷ suất tăng của hàm T(n) = 3n
3
+ 2n
2

là n
3
. Thực vậy, cho n
0
= 0 và c = 5 ta dễ dàng
chứng minh rằng với mọi n ≥ 0 thì 3n
3
+ 2n
2
≤ 5n
3

Đánh giá CTDL và GT
Khái niệm độ phức tạp của giải thuật

Độ phức tạp tính toán của giải thuật là một hàm
chặn trên của hàm thời gian. Vì hằng nhân tử c

Phép gán

Thông thường số các phép tính được thực hiện
phụ thuộc vào cỡ của bài toán, tức là độ lớn của
đầu vào

Vì thế độ phức tạp thuật toán là một hàm phụ
thuộc đầu vào

Tuy nhiên, không cần biết chính xác hàm này mà
chỉ cần biết một ước lượng đủ tốt của chúng

Để ước lượng độ phức tạp của một thuật toán ta
thường dùng khái niệm Big-O
20

Ví dụ

Bước 1. Gán
T
ổng = 0. Gán i = 0.

Bước 2.
– Tăng i thêm 1 đơn vị.
– Gán Tổng = Tổng + i

Bước 3. So sánh i với
n
– Nếu i <
n

thức
có
bậc
từ
2 trở lên

Độ phức tạp hàm mũ: O(2
n
)
22

Bảng so sánh các độ phức tạp của
thuật toán

Một số lớp thuật toán
23

Thứ tự độ phức tạp của thuật toán
24

Đánh giá CTDL và GT

Cách tính độ phức tạp
Qui tắc cộng:

Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn
chương trình P1 và P2; và T1(n)=O(f(n)), T2(n)=O(g(n)
thì thời gian thực hiện của đoạn hai chương trình đó
nối tiếp nhau là T(n)=O(max(f(n),g(n)))
