Bài giảng Cấu trúc dữ liệu - Chương II: Các kiểu dữ liệu và giải thuật tìm kiếm - Thiều Quang Trung

CHƯƠNG 2
CÁC KIỂU DỮ LIỆU VÀ GIẢI THUẬT TÌM KIẾM
GV Th.S. Thiều Quang Trung
Trường Cao đẳng Kinh tế Đối ngoại
• Định nghĩa kiểu dữ liệu1
• Các kiểu dữ liệu cơ bản2
• Các kiểu dữ liệu có cấu trúc3
• Nhu cầu tìm kiếm dữ liệu4
• Giải thuật tìm tuyến tính5
• Giải thuật tìm nhị phân6
Nội dung
2GV Thiều Quang Trung
3Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu T được xác định bởi một bộ 
 V,O , với :
– V : tập các giá trị hợp lệ mà một đố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 kiểu T.
GV Thiều Quang Trung
4Định nghĩa kiểu dữ liệu
• Ví dụ 1: kiểu dữ liệu mẫu tự = Vc,Oc với
– Vc = a-z, A-Z
– Oc= lấy mã ASCII của ký tự, biến đổi ký tự 
thường thành ký tự hoa 
• Ví dụ 2: kiểu dữ liệu số nguyên = Vi,Oi với
– Vi = -32768 .. 32767
– Oi = +, -, *, /, %
GV Thiều Quang Trung
5Định nghĩa kiểu dữ liệu
• Các thuộc tính của một kiểu dữ liệu bao 
gồm:
– 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ử tác động lên kiểu dữ liệu
• Có hai loại kiểu dữ liệu:
– Kiểu dữ liệu cơ bản
– Kiểu dữ liệu có cấu trúc
GV Thiều Quang Trung
6• Các kiểu dữ liệu cơ bản là các loại dữ liệu đơn 
giản không có cấu trúc 
• Là các giá trị vô hướng như các số nguyên, số 
thực, các ký tự, các giá trị logic  
• Được các ngôn ngữ lập trình cấp cao xây 
dựng sẵn như một thành phần của ngôn ngữ 
để giảm nhẹ công việc cho người lập trình. Vì 
vậy còn gọi là các kiểu dữ liệu định sẵn
Các kiểu dữ liệu cơ bản
GV Thiều Quang Trung
7• Các kiểu dữ liệu cơ bản bao gồm:
– Kiểu có thứ tự rời rạc: số nguyên, ký tự, logic, 
liệt kê, miền con 
– Kiểu không rời rạc: số thực. 
• Tùy ngôn ngữ lập trình các kiểu dữ liệu cơ 
bản có thể khác nhau
• Kiểu dữ liệu cơ bản trong ngôn ngữ C gồm: số 
nguyên, số thực, ký tự, logic
Các kiểu dữ liệu cơ bản
GV Thiều Quang Trung
8Tên kiểu K thước Miền giá trị Ghi chú
char 1 byte -128 đến 127 Có thể dùng như số 
nguyên 1 byte có dấu 
hoặc kiểu ký tự 
unsign char 1 byte 0 đến 255 Số nguyên 1 byte 
không dấu 
int 2 byte -32738 đến 32767 
unsign int 2 byte 0 đến 65335 Có thể gọi tắt là 
unsign
long 4 byte - 2.147.483.648 đến 
2.147.483.647
unsign long 4 byte 0 đến 4.2 tỷ 
float 4 byte 6 số chính xác Sử dụng số double 
chính xác hơn floatdouble 8 byte 10 số chính xác 
long double 10 byte 10 số chính xác 
Các kiểu dữ liệu cơ bản trong C 
GV Thiều Quang Trung
Các kiểu dữ liệu cơ bản trong C 
• Kiểu ký tự “char” có thể dùng theo 2 cách:
– số nguyên 1 byte, hoặc
– ký tự 
• Không định nghĩa kiểu logic (boolean), thay thế 
bằng:
– Giá trị số nguyên bằng 0 là FALSE
– Giá trị số nguyên khác 0 là TRUE
9GV Thiều Quang Trung
10
• Kiểu dữ liệu có cấu trúc là kiểu dữ liệu được xây dựng 
dựa trên các thành phần của kiểu dữ liệu cơ bản
• Một số kiểu có cấu trúc cơ bản như mảng, chuỗi, 
• Ví dụ: Để mô tả một đối tượng sinh viên thì cần định 
nghĩa các thông tin sau :
– Mã sinh viên : chuỗi ký tự
– Tên sinh viên : chuỗi ký tự
– Ngày sinh : kiểu ngày tháng
– Nơi sinh : chuỗi ký tự
– Điểm thi : số nguyên
Các kiểu dữ liệu có cấu trúc
GV Thiều Quang Trung
11
• Để thể hiện thông tin về ngày tháng năm sinh cần 
phải xây dựng một kiểu bản ghi :
typedef struct tagDate 
char ngay ;
char thang ;
char nam ;
 Date ; 
Các kiểu dữ liệu có cấu trúc
GV Thiều Quang Trung
12
• Kiểu dữ liệu thể hiện thông tin một sinh viên được 
xây dựng như sau:
typedef struct tagSinhVien 
char masv[15] ;
char tensv[15] ;
char noisinh[15] ;
Date namsinh;
int Diemthi ;
 SinhVien ; 
Các kiểu dữ liệu có cấu trúc
GV Thiều Quang Trung
13
• Giả sử đã có cấu trúc phù hợp để lưu trữ 
một sinh viên, nhưng thực tế lại cần quản lý 
nhiều sinh viên, lúc đó nảy sinh nhu cầu xây 
dựng kiểu dữ liệu mới
• Mục tiêu của việc nghiên cứu cấu trúc dữ 
liệu chính là tìm những phương cách thích 
hợp để tổ chức, liên kết dữ liệu, hình thành 
các kiểu dữ liệu có cấu trúc từ những kiểu dữ 
liệu đã được định nghĩa.
Các kiểu dữ liệu có cấu trúc
GV Thiều Quang Trung
14
• Chuỗi ký tự là một trong các kiểu dữ liệu có cấu trúc 
đơn giản nhất, được các ngôn ngữ lập trình định nghĩa 
như một kiểu cơ bản
• Được cấu trúc như một chuỗi liên tiếp các ký tự kết 
thúc bằng ký tự có mã ASCII bằng 0 (NULL character)
• Giới hạn chiều dài của một chuỗi ký tự trong C tối đa 
65335 ký tự, ký tự đầu được đánh số là ký tự thứ 0
Kiểu chuỗi ký tự
GV Thiều Quang Trung
15
• Ta có thể khai báo một chuỗi ký tự theo một số cách 
sau đây :
– Khai báo một chuỗi ký tự S có chiều dài tối đa 10 
ký tự
char S10 ; 
– Khai báo một chuỗi ký tự S có chiều dài bằng 
chiều dài của chuỗi “ABC” và giá trị khởi đầu của S 
là “ABC”
char S = “ABC”;
– Cách khai báo khác
char *S = “ABC”; 
Kiểu chuỗi ký tự
GV Thiều Quang Trung
16
• Các thao tác trên chuỗi ký tự rất đa dạng và phong 
phú được cài đặt trong thư viện string.lib của C
• Một số thao tác thông dụng :
– strcmp : So sánh 2 chuỗi 
– strcpy : Sao chép 2 chuỗi 
– strstr : Kiểm tra một chuỗi có nằm trong chuỗi kia 
– strtok : Cắt 1 từ ra khỏi 1 chuỗi 
– itoa : Đổi 1 số ra chuỗi 
– atoi,atof,  : Đổi 1 chuỗi ra số 
– sprintf : Đổi 1 hay 1 số giá trị ra chuỗi
– gets : Nhập 1 chuỗi 
– puts : Xuất 1 chuỗi 
Kiểu chuỗi ký tự
GV Thiều Quang Trung
17
• Mảng là kiểu dữ liệu trong đó mỗi phần tử của nó là 
một tập hợp có thứ tự các giá trị có cùng cấu trúc 
được lưu trữ liên tiếp nhau trong bộ nhớ. 
• Có hai dạng: mảng một chiều và mảng nhiều chiều. 
• Một dãy số chính là hình tượng của mảng một chiều, 
ma trận là hình tượng của mảng 2 chiều.
• Mảng 2 chiều có thể coi là là mảng một chiều trong đó 
mỗi phần tử của nó là 1 mảng một chiều.
• Mảng 1 chiều được khai báo như sau :
 [];
Kiểu mảng
GV Thiều Quang Trung
18
• Ví dụ mảng một chiều: 
– Khai báo một mảng số nguyên có tối đa 100 phần 
tử:
int a [100];
– Khai báo và gán giá trị ban đầu cho một mảng gồm 
4 phần tử:
int a [4] = 1,7,-3,819 ;
– Cách khai báo khác:
int a [] = 1,7,-3,819 ;
Kiểu mảng
GV Thiều Quang Trung
19
• Mảng 2 chiều được khai báo như sau :
[][];
• Ví dụ : 
– Khai báo mảng số nguyên có kích thước 3x5 :
int a [3][5];
– Khai báo và gán giá trị ban đầu cho mảng 2 chiều :
int a [][] = 1,7,-3,8,19,
 4,5, 2,8,9,
 21,7,45,-1,4;
Kiểu mảng
GV Thiều Quang Trung
• Mẫu tin là kiểu dữ liệu mà trong đó 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 tổng quát của kiểu struct như sau :
typedef struct 
 ;
 ; 
 [] ;
20
Kiểu mẫu tin/bản ghi
GV Thiều Quang Trung 20
• Ví dụ: khai báo kiểu dữ liệu mô tả các thông tin về 
một con người
typedef struct tagNguoi 
char HoTen [35];
int NamSinh;
char NoiSinh[40];
char GioiTinh; // 0 : Nữ, 1 : Nam
char DiaChi [50];
char Ttgd; // 0 : Ko có gia đình, 1 : Có gia đình
 Nguoi ;
21
Kiểu mẫu tin/bản ghi
GV Thiều Quang Trung
Nhu cầu tìm kiếm dữ liệu
22GV Thiều Quang Trung
Nhu cầu tìm kiếm dữ liệu
• Trong các hệ lưu trữ, quản lý dữ liệu, thao tác 
tìm kiếm thường được thực hiện nhiều nhất
• Ví dụ: tra cứu từ điển, tìm sách trong thư 
viện, 
• Do hệ thống thông tin lưu trữ khối lượng dữ 
liệu lớn => xây dựng phép toán tìm kiếm 
nhanh có ý nghĩa rất quan trọng
23GV Thiều Quang Trung
Nhu cầu tìm kiếm dữ liệu
• Nếu dữ liệu trong hệ thống đã được sắp xếp 
=> việc tìm kiếm sẽ thực hiện nhanh hơn
• Ví dụ: các từ trong từ điển đã được sắp xếp 
theo vần, 
• Xây dựng một hệ quản lý thông tin: cần quan 
tâm giải thuật tìm kiếm và cả giải thuật sắp 
xếp dữ liệu
• Mức độ hiệu quả của từng giải thuật phụ 
thuộc vào tính chất của cấu trúc dữ liệu
24GV Thiều Quang Trung
Nhu cầu tìm kiếm dữ liệu
• Để đánh giá thời gian thực hiện dựa vào 2 đại 
lượng đặc trưng:
– Số lần so sánh
– Số phép gán 
• Hai giải thuật tìm kiếm dữ liệu: 
– Tìm Tuyến tính/Tuần tự (Linear/Sequential 
Search)
– Tìm Nhị phân (Binary Search)
25GV Thiều Quang Trung
▪ Ý tưởng :
Thuật toán tiến hành so sánh khóa cần tìm 
là X với lần lượt các phần tử thứ nhất, thứ 
hai,  của mảng A cho đến khi gặp được 
phần tử chứa khóa, hoặc đã tìm hết mảng 
mà không thấy X.
Tìm kiếm tuyến tính
26GV Thiều Quang Trung
Tìm kiếm tuyến tính
▪ Giải thuật vét cạn (Exhaustive):
Bước 1 : i = 0; //bắt đầu phần tử đầu tiên của dãy
Bước 2 : So sánh a[i] với X, có 2 khả năng :
a[i] = X : Tìm thấy => Dừng
a[i] X : Sang bước 3.
Bước 3 : i = i+1 ; //xét tiếp phần tử kế trong mảng
Nếu i >= N : Hết mảng, không tìm thấy => Dừng
Ngược lại : Lặp lại Bước 2.
27GV Thiều Quang Trung
Tìm kiếm tuyến tính
◼ Ví dụ :
Cho dãy số a :
12 2 8 5 1 6 4 15
Nếu giá trị cần tìm là 8, giải thuật được tiến 
hành như sau :
28GV Thiều Quang Trung
Tìm kiếm tuyến tính
12 2 8 5 1 6 4 15
X = 8i =0 :
12 2 8 5 1 6 4 15
12 2 8 5 1 6 4 15
X = 8i =1 :
i =2 :
X = 8
Tìm thấy tại i = 2. Dừng.
29GV Thiều Quang Trung
Cài đặt giải thuật, cách 1: 
int LinearSearch(int a[], int n, int x)
{
int i=0;
while(i<n && a[i]!=x) i++;
if (i<n)return i; //a[i] là phần tử có khoá x
return -1; //tìm hết mảng nhưng không có x
}
Tìm kiếm tuyến tính
30GV Thiều Quang Trung
Cài đặt giải thuật, cách 2: 
int LinearSearch (int a[], int n, int x)
{
for(int i=0;i<n;i++)
if (a[i]==x) 
return i; //a[i] là phần tử có khóa x
return -1; 
}
Tìm kiếm tuyến tính
31GV Thiều Quang Trung
Tìm kiếm tuyến tính
Nhận xét:
• Trường hợp khóa X nằm ở 2 biên của mảng A
=> rất hiếm khi xuất hiện.
• Số phép so sánh trung bình = 2(1+2+  + n)/n 
= n+1
=> Số phép so sánh tăng/giảm tuyến tính 
theo số phần tử
32GV Thiều Quang Trung
Ý tưởng:
• Đối với những dãy số đã có thứ tự thì các 
phần tử trong dãy có quan hệ: 
ai-1 ai ai+1
– Nếu X > ai thì X chỉ có thể xuất hiện trong đoạn 
[ai+1, aN]
– Ngược lại, X chỉ có thể xuất hiện trong đoạn 
[a1, ai-1] của dãy. 
Tìm kiếm nhị phân
33GV Thiều Quang Trung
Tìm kiếm nhị phân
• Ý tưởng của giải thuật tìm nhị phân là tìm 
các giới hạn phạm vi của dãy sau mỗi lần so 
sánh X với một phần tử trong dãy: 
– Tại mỗi bước tiến hành so sánh X với phần tử 
nằm ở vị trí giữa của dãy;
– Dựa vào kết quả so sánh này để quyết định giới 
hạn dãy tìm kiếm ở bước kế tiếp là nửa trên 
hay nửa dưới của dãy.
34GV Thiều Quang Trung
Thuật toán:
B1: left = 0; right = n-1; 
B2: while (left right)
B2.1: mid = (left+right)/2; 
B2.2: if ( a[mid] = x) → Dừng, vị trí xuất hiện: mid
B2.3: if (a[mid] > x) right = mid - 1;
else left = mid + 1;
B3: Dừng, không tìm thấy.
35GV Thiều Quang Trung
Tìm kiếm nhị phân
Ví dụ: Cho dãy số a gồm 8 phần tử, nếu giá trị cần tìm là 8, giải 
thuật được tiến hành như sau :
Tìm kiếm nhị phân
left = 1, right = 8, mid = 4 :
1 2 4 5 6 8 12 15
left = 5, right = 8, mid = 6 :
1 2 4 5 6 8 12 15
Dừng.
X = 8
X = 8
1 2 4 5 6 8 12 15
36GV Thiều Quang Trung
Tìm kiếm nhị phân
Cài đặt:
int BinarySearch(int a[],int n,int x )
{ 
int left = 0, right = n-1, mid;
while (left <= right)
{
mid = (left + right)/2;
if (x == a[mid]) return mid;
if (x<a[mid]) right = mid -1;
else left = mid +1;
}
return -1; // trong dãy không có x
}
37GV Thiều Quang Trung
Tìm kiếm nhị phân
Nhận xét :
• Mỗi lần lặp thì chiều dài của mảng con giảm 
khoảng ½ so với mảng trước đó.
• n = 2k + m, với 0 <= m < 2
• => 2k < n < 2k+1
• => k <= log2 n < k+1 
• => k = log2n
• Số lần thực hiện vòng while là khoảng k lần, 
mỗi vòng lặp thực hiện 1 phép so sánh.
38GV Thiều Quang Trung
Tìm kiếm nhị phân
Nhận xét:
• Trường hợp tốt nhất:
– k = 1  X là phần tử chính giữa của mảng.
• Trường hợp xấu nhất: 
– k= log2n + 1  X không thuộc mảng hoặc X
là phần tử cuối cùng của mảng
– Số phép so sánh tăng theo hàm logarit
39GV Thiều Quang Trung
Tìm kiếm nhị phân
So sánh trường hợp xấu nhất của 2 thuật toán
40GV Thiều Quang Trung
GV: Thiều Quang Trung 41