Bài giảng Cấu trúc dữ liệu - Chương 2: 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 
Bộ môn Khoa học cơ bản 
Trường Cao đẳng Kinh tế Đối ngoại 
• Định nghĩa kiểu dữ liệu 1 
• Các kiểu dữ liệu cơ bản 2 
• Các kiểu dữ liệu có cấu trúc 3 
• Nhu cầu tìm kiếm dữ liệu 4 
• Giải thuật tìm tuyến tính 5 
• Giải thuật tìm nhị phân 6 
Nội dung 
2 GV 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 
8 
Tê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 float double 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 
9 GV 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 
22 GV 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 
23 GV 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 
24 GV 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) 
25 GV 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 
26 GV 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. 
27 GV 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 : 
28 GV Thiều Quang Trung 
Tìm kiếm tuyến tính 
12 2 8 5 1 6 4 15 
X = 8 i =0 : 
12 2 8 5 1 6 4 15 
12 2 8 5 1 6 4 15 
X = 8 i =1 : 
i =2 : 
X = 8 
Tìm thấy tại i = 2. Dừng. 
29 GV 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 
30 GV 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 
31 GV 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ử 
32 GV 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 
33 GV 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. 
34 GV 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. 
35 GV 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 
36 GV 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 
} 
37 GV 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. 
38 GV 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 
39 GV 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 
40 GV Thiều Quang Trung 
GV: Thiều Quang Trung 41