Bài giảng Cấu trúc dữ liệu 1 - Chương 1: Mở đầu về cấu trúc dữ liệu

ðại Học Sư Phạm Tp. Hồ Chí Minh
Chương 01: Mở ñầu về CTDL
CẤU TRÚC DỮ LIỆU 1 
Thông tin giảng viên
• LƯƠNG TRẦN HY HIẾN
• Bộ Môn Tin Học
• Khoa Toán – Tin học
• Phone: 0989 366 990
• Email: hienlth@hcmup.edu.vn
Chương 1. Giới thiệu về cấu trúc dữ liệu
1.1 Vai trò của cấu trúc dữ liệu
1.2 Một số tiêu chuẩn chọn CTDL
1.3 Kiểu dữ liệu
1.4 ðộ phức tạp giải thuật
1.1 Vai trò của cấu trúc dữ liệu
Bài toán 
thực tế
Thông tin 
nghiệp vụ
thực tế
Thao tác 
nghiệp vụ
Bài toán trên 
máy tính
ðối tượng
dữ liệu
Yêu cầu
xử lý
1.1 Vai trò của cấu trúc dữ liệu
Bài toán trên 
máy tính
ðối tượng
dữ liệu
Yêu cầu
xử lý
Khi giải quyết các bài toán thực tế cần quan tâm:

 Tổ chức biểu diễn các ñối tượng thực tế
Chọn cấu trúc dữ liệu phù hợp

 Xây dựng các thao tác xử lý dữ liệu
Tìm giải thuật giải quyết bài toán.
Cấu trúc dữ liệu + giải thuật = chương trình
1.1 Vai trò của cấu trúc dữ liệu
 Ví dụ 1: Chương trình quản lý ñiểm sinh viên của một 
khóa học. Mỗi sinh viên học 4 môn học và các ñiểm 
tương ứng như sau:
Cấu trúc dữ liệu + giải thuật = chương trình
Môn 1 Môn 2 Môn 3 Môn 4
Sinh viên 1 7 8 5 6
Sinh viên 2 8 6 4 5
Sinh viên 3 3 7 9 5
Sinh viên 4 9 7 6 5
… … … … …
1.1 Vai trò của cấu trúc dữ liệu
 Phân tích ví dụ 1
Môn 1 Môn 2 Môn 3 Môn 4
Sinh viên 1 7 8 5 6
Sinh viên 2 8 6 4 5
Sinh viên 3 3 7 9 5
Sinh viên 4 9 7 6 5
… … … … …
Chương 
trình quản 
lý ñiểm
ðối tượng dữ liệu Yêu cầu xử lý

Nhập ñiểm

Xuất danh sách ñiểm

Tính ñiểm trung bình

Thống kê tỉ lệ ñậu, hỏng

Các thao tác tìm kiếm theo ñiểm
1.1 Vai trò của cấu trúc dữ liệu
 Phương án 1
Dùng mảng một chiều 
lưu trữ ñiểm của tất 
cả các sinh viên
Môn 1 Môn 2 Môn 3 Môn 4
Sinh viên 1 7 8 5 6
Sinh viên 2 8 6 4 5
Sinh viên 3 3 7 9 5
Sinh viên 4 9 7 6 5
… … … … …
ðối tượng dữ liệu
7 8 5 6 8 6 4 5 3 7 9 5 9 7 6 5
Sinh viên 1 Sinh viên 2 Sinh viên 3 Sinh viên 4
R
R[I] = Bảng ñiểm( dòng (I / số môn) , cột (I % số môn) )
1.1 Vai trò của cấu trúc dữ liệu
 Phương án 1
7 8 5 6 8 6 4 5 3 7 9 5 9 7 6 5R
R[I] = Bảng ñiểm(I / số môn , I % số môn)
int R[16] = {7,8,5,6,8,6,4,5,3,7,9,5,9,7,6,5};
int SO_MON = 4;
int SO_SV = 4;
void xuat() {
for( int I =0 ; I < SO_MON*SO_SV ; I++){
int SV = I / SO_MON;
int MON = I % SO_MON;
cout<<“Diem mon “<<MON<<“ cua sv “<<SV<<“ = “<<R[I];
}
}
1.1 Vai trò của cấu trúc dữ liệu
 Phương án 2
Dùng mảng hai chiều 
lưu trữ ñiểm của tất 
cả các sinh viên
Môn 1 Môn 2 Môn 3 Môn 4
Sinh viên 1 7 8 5 6
Sinh viên 2 8 6 4 5
Sinh viên 3 3 7 9 5
Sinh viên 4 9 7 6 5
ðối tượng dữ liệu
Cột 0 Cột 1 Cột 2 Cột 3
Dòng 0 R[0][0]=7 R[0][1]=8 R[0][2]=5 R[0][3]=6
Dòng 1 R[1][1]=8 R[0][1]=6 R[0][1]=4 R[0][3]=5
Dòng 2 R[2][1]=3 R[0][1]=7 R[0][1]=9 R[0][3]=5
Dòng 3 R[3][1]=9 R[0][1]=7 R[0][1]=6 R[0][3]=5
R
R[I][J] = Bảng ñiểm( dòng I , cột J )
1.1 Vai trò của cấu trúc dữ liệu
 Phương án 2
int R[4][4] = {{7,8,5,6},
{8,6,4,5},
{3,7,9,5},
{9,7,6,5}};
int SO_MON = 4;
int SO_SV = 4;
void xuat() {
for( int I=0 ; I < SO_SV ; ++I)
for( int J=0 ; J < SO_MON ; ++J)
cout<<“Diem mon“<<J<<“ cua sv “<<I<<“ = ”<<R[I][J];
}
R[I][J] = Bảng ñiểm( dòng I , cột J )
1.1 Vai trò của cấu trúc dữ liệu
 Phương án 3
Dùng mảng một chiều, 
các phần tử có kiểu 
cấu trúc nhằm lưu 
trữ ñiểm của tất cả
các sinh viên
Môn 1 Môn 2 Môn 3 Môn 4
Sinh viên 1 7 8 5 6
Sinh viên 2 8 6 4 5
Sinh viên 3 3 7 9 5
Sinh viên 4 9 7 6 5
ðối tượng dữ liệu
R[0].Mon1=7 R[1].Mon1=8 R[2].Mon1=3 R[3].Mon1=9
R[0].Mon2=8 R[1].Mon2=6 R[2].Mon2=7 R[3].Mon2=7
R[0].Mon3=5 R[1].Mon3=4 R[2].Mon3=9 R[3].Mon3=6
R[0].Mon4=3 R[1].Mon4=5 R[2].Mon4=5 R[3].Mon4=5
R[ I ] lưu trữ tất cả các ñiểm của sinh viên thứ I
R
1.1 Vai trò của cấu trúc dữ liệu
 Phương án 3
struct DiemSV {
int Mon1,Mon2,Mon3,Mon4;
};
DiemSV R[4];
int SO_SV = 4;
void xuat() {
for( int I=0 ; I < SO_SV ; ++I) {
cout<<“Diem mon 1 cua sv “<<I<<“ = ”<<R[I].Mon1;
cout<<“Diem mon 2 cua sv “<<I<<“ = ”<<R[I].Mon2;
cout<<“Diem mon 3 cua sv “<<I<<“ = ”<<R[I].Mon3;
cout<<“Diem mon 4 cua sv “<<I<<“ = ”<<R[I].Mon4;
}
}
R[I][J] = Bảng ñiểm( dòng I , cột J )
1.2 Một số tiêu chí chọn cấu trúc dữ liệu
a. CTDL phải phản ánh ñúng thực tế.
ðây là yếu tố quyết ñịnh tính ñúng ñắn của bài toán. Cần 
xem xét trạng thái biến ñổi của dữ liệu nhằm chọn CTDL 
phù hợp.
b. CTDL phải phù hợp với thao tác trên ñó.
Tiêu chuẩn này giúp tăng tính hiệu quả của bài toán.Mỗi 
CTDL có các thao tác ñi tương ứng. Nên chọn CTLD sao 
cho các thao tác ñược xử lý ñược ñơn giản và tự nhiên.
c. CTDL phải tiết kiệm tài nguyên hệ thống.
CTDL nên sử dụng tài nguyên vừa ñủ ñể ñảm nhiệm chức 
năng của nó.
1.3 Kiểu dữ liệu
1.3.1 ðịnh nghĩa kiểu dữ liệu
Kiểu dữ liệu T ñược xác ñịnh bởi bộ với:
V : tập các giá trị hợp lệ mà ñối tượng kiểu T có thể lưu trữ
O : tập các thao tác xử lý có thể thi hành trên ñối tượng ñó
ví dụ 1: Giả sử có kiểu dữ liệu Alphabet = 
V = {a – z, A – Z}
O = {lấy mã ASCII của ký tự, ñổi ký tự sang dạng chữ hoa, chữ 
thường}
Giả sử có kiểu dữ liệu Number = 
V = {0..255}
O = { + , - , * , / , %}
1.3 Kiểu dữ liệu
1.3.1 ðịnh nghĩa kiểu dữ liệu
ví dụ 2: Giả sử có kiểu dữ liệu Contact = 
V = {Họ và tên, ñịa chỉ, số ñiên thoại}
O = {Gán giá trị, so sánh}
Giả sử có kiểu dữ liệu ContactList = 
V = {danh sách các ñối tượng có kiểu Contact}
O = { Thêm, xóa, sửa, so sánh, tìm kiếm, sắp xếp}
1.3 Kiểu dữ liệu
1.3.1 ðịnh nghĩa kiểu dữ liệu
Các thuộc tính cần quan tâm về kiểu dữ liệu:

 Tên kiểu dữ liệu

 Miền giá trị

 Kích thước lưu trữ

 Tập các toán tử, thao tác xử lý tác ñộng lên 
ñối tượng có kiểu dữ liệu
1.3 Kiểu dữ liệu
1.3.2 Các kiểu dữ liệu cơ bản

 Kiểu dữ liệu có thứ tự rời rạc: Số nguyên, ký tự, logic, 
liệt kê, miền con

 Kiểu dữ liệu không rời rạc: số thực
Một số kiểu dữ liệu cơ bản trong ngôn ngữ C
Tên kiểu dữ liệu Kích thước Miền giá trị
char 01 Byte -128 ñến 127
unsign char 01 Byte 0 ñến 255
int 02 byte 0 ñến 65535
long 04 byte -231 ñến 231 -1
unsign long 04 byte 0 ñến 232 - 1
float 04 Byte 3.4E-38 ñến 3.4E38
double 08 byte 1.7E-308 ñến 1.7E308
long double 10 byte 3.4E-4932 ñến 1.1E4932
1.3 Kiểu dữ liệu
1.3.2 Các kiểu dữ liệu có cấu trúc
Ví dụ: ðể mô tả thông tin sinh viên cần quan tâm ñến thông tin sau:
Mã số sinh viên : 12 ký tự
Tên sinh viên : 30 ký tự
Ngày sinh : kiểu ngày
Nơi sinh : 255 ký tự
ðiểm trung bình : Số thực
a. Kiểu chuỗi ký tự
Chuỗi ký tự trong là một dãy các ký tự liên tiếp kết thúc bằng ký 
tự có mã ASCII bằng 0. Chuỗi ký tự có tối ña 65535 ký tự
Ví dụ: char S[10]; 
char S[] = “ABC”;
char *S = “ABC”;
1.3 Kiểu dữ liệu
1.3.2 Các kiểu dữ liệu có cấu trúc
Các thao tác trên chuỗi
Tên hàm Công dụng
strcmp(s1,s2) So sánh 2 chuỗi s1 và s2
strcpy(dest,src) Sao chép src vào dest
strstr(s1,s2) Kiểm tra s2 có nằm trong 
chuỗi s1 khong?
itoa(n,s,c) ðổi số nguyên n thành 
chuỗi ở dạng cơ số c
atoi(sn) ,atof(sf), atol(sl) ðổi 1 chuỗi thành số
gets(st) Nhập một chuỗi
puts(st) Xuất một chuỗi
1.3 Kiểu dữ liệu
b. Kiểu mảng
Mảng là kiểu dữ liệu lưu trữ các phần tử cùng kiểu. Mỗi phần tử 
ñược xác ñịnh bởi một vị trí trí của nó trong mảng.
Khai báo mảng 1 chiều
 [];
int a[100];
int a[5]={4, 3, 6, 7, 2};
int a[ ] = {1, 4 , -3, 5, 6};
Khai báo mảng 2 chiều
 [][];
int a[10][10];
int a[3][2]={{4, 3},{ 6, 7},{2,3}};
1.3 Kiểu dữ liệu
c. Kiểu mẩu tin(cấu trúc)
Kiểu mẫu tin là kiểu dữ liệu mà mỗi phần tử của nó là tập hợp 
các giá trị có thể khác cấu trúc. Kiểu mẫu tin cho phép mô tả các 
ñối tượng có cấu trúc phức tạp.
Khai báo
struct {
 ;
 ;
….
};
1.3 Kiểu dữ liệu
d. Kiểu Union
Kiểu Union giống như Struct, nhưng các trường dùng chung 
vùng nhớ.
Khai báo
union {
 ;
 ;
….
};
1.4 ðánh giá ñộ phức tạp của thuật toán
Phương pháp thực nghiệm:
 Cài ñặt thuật toán, chọn các bộ dữ liệu thử, thống kê các 
thông số nhận ñược.
Một số nhược ñiểm:
 Phụ thuộc vào ngôn ngữ lập trình dùng ñể cài ñặt
 Phụ thuộc vào trình ñộ của người cài ñặt
 Việc chọn ra bộ dữ liệu thử ñặc trưng cho tất cả các 
trường hợp rất khó khăn.
 Phụ thuộc vào phần cứng khi thực thi thuật toán
Phương pháp hình thức:
 ðây là phương pháp ñánh giá ít phụ thuộc vào môi 
trường cũng như phần cứng.ðánh giá theo hướng xấp 
xỉ tiệm cận thông qua khái niệm toán học O-lớn O().
 Thời gian tính toán sẽ phụ thuộc vào kích thước 
của dữ liệu ñầu vào(thường gọi là N) và ñánh giá theo 
3 trường hợp:
 Trường hợp tốt nhất
 Trường hợp xất nhất
 Trường hợp trung bình
1.4 ðánh giá ñộ phức tạp của thuật toán
Sự phân lớp các ñộ phức tạp của thuật toán

ðộ phức tạp là hằng số O(1)

ðộ phức tạp là logN O(logN)

ðộ phức tạp là N O(N)

ðộ phức tạp là NlogN O(NlogN)

ðộ phức tạp là N2 O(N2)

ðộ phức tạp là N3 O(N3)

ðộ phức tạp là 2N O(2N)

ðộ phức tạp là N! O(N!)
1.4 ðánh giá ñộ phức tạp của thuật toán
27
Câu hỏi và thảo luận