Giáo trình môn Cấu trúc dữ liệu và giải thuật

TRƯỜNG CAO ĐẲNG NGHỀ ĐẮK LẮK 
KHOA ĐIỆN TỬ - TIN HỌC 
GIÁO TRÌNH 
CẤU TRÚC DỮ LIỆU VÀ 
GIẢI THUẬT 
NGHỀ: CÔNG NGHỆ THÔNG TIN 
TRÌNH ĐỘ: CAO ĐẲNG NGHỀ - TRUNG CẤP NGHỀ 
Người biên soạn: Nguyễn Thị Thu Hà 
Lưu hành nội bộ - 2014 
1 
Lời nói đầu 
Hiện nay, tại Trường chưa có giáo trình Cấu trúc dữ liệu & giải thuật. Đặc 
biệt trên thị trường không có tài liệu học tập, tham khảo phù hợp với chương 
trình khung Cao đẳng nghề, trung cấp nghề thuộc nghề Công nghệ thông tin 
(CNTT) trong quá trình đào tạo nghề hiện nay. 
Nhóm tác giả biên soạn giáo trình lập trình cơ bản nhằm mục đích giúp học 
sinh, sinh viên (HSSV) sử dụng giáo trình làm tài liệu nghiên cứu và học 
tập một cách thuận tiện. Chương trình môn học được sử dụng để giảng dạy 
cho sinh viên cao đẳng nghề Công nghệ thông tin (ứng dụng phần mềm) và 
làm tài liệu tham khảo cho các nghề thuộc các ngành nghề kỹ thuật. 
Vậy, rất mong được sự góp ý của bạn đọc để tài liệu này ngày càng được 
hoàn thiện hơn, chúng tôi xin chân thành cảm ơn. 
 Đắk Lắk, ngày 02 tháng 09 năm 2014 
Tham gia biên soạn 
Chủ biên: Nguyễn Thị Thu Hà 
ThS. Lê Văn Tùng 
2 
CHƯƠNG TRÌNH MÔN HỌC CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 
Mã số của môn học: MH 12; 
Thời gian của môn học: 75 giờ; (Lý thuyết: 24 giờ; Thực hành: 51 giờ) 
I. VỊ TRÍ, TÍNH CHẤT CỦA MÔN HỌC: 
 Cấu trúc dữ liệu và giải thuật là môn cơ sở nghề bắt buộc, được học sau các môn học 
Tin học, Lập trình căn bản. 
II. MỤC TIÊU CỦA MÔN HỌC: 
- Hiểu được mối quan hệ giữa cấu trúc dữ liệu và giải thuật trong việc xây dựng 
chương trình; 
- Hiểu được ý nghĩa, cấu trúc, cách khai báo, các thao tác của các loại cấu trúc dữ liệu: 
mảng, danh sách liên kết, cây và các giải thuật cơ bản xử lý các cấu trúc dữ liệu đó; 
- Xây dựng được cấu trúc dữ liệu và mô tả tường minh các giải thuật cho một số bài 
toán ứng dụng cụ thể; 
- Cài đặt được một số giải thuật trên ngôn ngữ lập trình C; 
 Coi việc học môn này là một nền tảng cho các môn học chuyên môn tiếp theo, 
nghiêm túc và tích cực trong việc học lý thuyết và làm bài tập, chủ động tìm kiếm các 
nguồn tài liệu liên quan đến môn học. 
III. NỘI DUNG MÔN HỌC: 
1. Nội dung tổng quát và phân bổ thời gian: 
Số 
TT 
Tên chương, mục 
Thời gian 
Tổng 
số 
Lý 
thuyết 
Thực 
hành, 
Bài tập 
Kiểm tra* 
(LT hoặc 
TH) 
I Thiết kế và phân tích giải thuật 15 4 11 0 
II Các kiểu dữ liệu cơ sở 8 2 6 0 
III 
Mảng, danh sách và các kiểu dữ liệu 
trừu tượng 
20 5 13 2 
IV Cây 7 3 4 0 
V Sắp xếp 15 5 10 0 
VI Tìm kiếm 10 3 5 2 
 Tổng cộng 75 22 49 4 
3 
Chương 1: Thiết kế và phân tích giải thuật 
1. Mở đầu: 
Có thể nói rằng không có một chương trình máy tính nào mà không có dữ liệu để xử lý. 
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). Do vậy, việc tổ chức để lưu trữ dữ liệu phục vụ cho 
chương trình có ý nghĩa rất quan trọng trong toàn bộ hệ thống chương trình. 
Việc xây dựng cấu trúc dữ liệu quyết định rất lớn đến chất lượng cũng như công sức 
của người lập trình trong việc thiết kế, cài đặt chương trình. 
2. Thiết kế giải thuật: 
Khái niệm giải thuật hay thuật giải mà nhiều khi còn được gọi là thuật toán dùng để chỉ 
phương pháp hay cách thức (method) để giải quyết vầ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). Trong thực tế, giải thuật thường được minh họa hay thể hiện 
bằng mã giả tựa trên một hay một số ngôn ngữ lập trình nào đó (thường là ngôn 
ngữ mà người lập trình chọn để cài đặt thuật toán), chẳng hạn như C, Pascal, ? 
Khi đã xác định được cấu trúc dữ liệu thích hợp, người lập trình sẽ bắt đầu tiến 
hành xây dựng thuật giải tương ứng theo yêu cầu của bài toán đặt ra trên cơ sở của cấu 
trúc dữ liệu đã được chọn. Để giải quyết một vấn đề có thể có nhiều phương pháp, do 
vậy sự lựa chọn phương pháp phù hợp là một việc mà người lập trình phải cân nhắc và 
tính toán. Sự lựa chọn này cũng có thể góp phần đáng kể trong việc giảm bớt 
công việc của người lập trình trong phần cài đặt thuật toán trên một ngôn ngữ cụ thể. 
3. Phân tích giải thuật: 
Mối quan hệ giữa cấu trúc dữ liệu và Giải thuật có thể minh họa bằng đẳng thức: 
Cấu trúc dữ liệu + Giải thuật = Chương trình 
Như vậy, khi đã có cấu trúc dữ liệu tốt, nắm vững giải thuật thực hiện thì việc thể hiện 
chương trình bằng một ngôn ngữ cụ thể chỉ là vấn đề thời gian. Khi có cấu trúc dữ liệu 
mà chưa tìm ra thuật giải thì không thể có chương trình và ngược lại không thể 
có Thuật giải khi chưa có cấu trúc dữ liệu. Một chương trình máy tính chỉ có thể được 
hoàn thiện khi có đầy đủ cả Cấu trúc dữ liệu để lưu trữ dữ liệu và Giải thuật 
xử lý dữ liệu theo yêu cầu của bài toán đặt ra. 
3.1 Đánh giá cấu trúc dữ liệu và giải thuật 
3.1.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. 
3.2. Đánh giá độ phức tạp của thuật toán 
Việc đánh giá độ phức tạp của một thuật toán quả không dễ dàng chút nào. Ở 
dây, chúng ta chỉ muốn ước lượng thời gian thực hiện thuận toán T(n) để có thể 
có sự so sánh tương đối giữa các thuật toán với nhau. Trong thực tế, thời gian 
thực hiện một thuật toán còn phụ thuộc rất nhiều vào các điều kiện khác như cấu 
4 
tạo của máy tính, dữ liệu đưa vào, ở đây chúng ta chỉ xem xét trên mức độ của lượng 
dữ liệu đưa vào ban đầu cho thuật toán thực hiện. 
Để ước lượng thời gian thực hiện thuật toán chúng ta có thể xem xét thời gian thực hiện 
thuật toán trong hai trường hợp: 
- Trong trường hợp tốt nhất: Tmin 
- Trong trường hợp xấu nhất: Tmax 
Từ đó chúng ta có thể ước lượng thời gian thực hiện trung bình của thuật toán: Tavg 
4. Một số giải thuật cơ bản: 
4.1: Thuật toán đơn giản 
Có thể nói rằng không có một chương trình máy tính nào mà không có dữ liệu để xử lý. 
Dữ liệu có thể là dữ liệu đưa vào (input data), dữ liệu trung gian và dữ liệu ra (output 
data). 
Ví dụ: Nhập vào một số 3 chữ số, in ra tổng của 3 chữ số đó. 
#include 
int n, dv, ch, tr, tong; 
void main() 
{ 
 printf(“Nhap vao mot so 3 chu so:”); 
 scanf(“%d”, &n); 
 dv = n mod 10; 
 ch = (n div 10) mod 10; 
 tr = (n div 100) mod 10; 
 tong = dv+ ch+ tr; 
 printf(“Tong 3 so la: %d”, tong); 
 getchar(); 
} 
4.2: Thuật toán phức tạp: 
Ví dụ : Dãy số Fibonacci 
0, 1, 1, 2, 3, 5, 8, 13, 21, 34,  Bắt đầu bằng 0 và 1, các số tiếp theo bằng tổng hai số đi 
trước. 
Dãy Fibonacci được khai báo đệ quy như sau: 
Fibonacci(0) = 0 
Fibonacci(1) = 1 
Fibonacci(n) = Fibonacci(n – 1) + Fibonacci(n – 2) 
4.3: Giải thuật đệ quy: 
Bất cứ một hàm nào đó có thể triệu gọi hàm khác, nhưng ở đây một hàm nào đó có thể tự 
triệu gọi chính mình. Kiểu hàm như thế được gọi là hàm đệ quy. 
5 
Phương pháp đệ quy thường dùng phổ biến trong những ứng dụng mà cách giải quyết có 
thể được thể hiện bằng việc áp dụng liên tiếp cùng giải pháp cho những tập hợp con của 
bài toán. 
Ví dụ 1: tính n! 
n! = 1*2*3**(n-2)*(n-1)*n với n >= 1 và 0! = 1. 
/* Ham tinh giai thua */ 
#include 
#include 
void main(void) 
{ 
int in; 
long giaithua(int); 
printf("Nhap vao so n: "); 
scanf("%d", &in); 
printf("%d! = %ld.\n", in, giaithua(in)); 
getch(); 
} 
long giaithua(int in) 
{ 
int i; 
long ltich = 1; 
if (in == 0) 
return (1L); 
else 
{ 
for (i = 1; i <= in; i++) 
ltich *= i; 
return (ltich); 
} 
} 
� Kết quả in ra màn hình 
Nhap vao so n: 5 
5! = 120. 
_ 
Thử lại chương trình với số liệu khác. 
Với n! = 1*2*3**(n-2)*(n-1)*n, 
ta viết lại như sau: (1*2*3**(n-2)*(n-1))*n = n*(n-1)!  = n*(n-1)*(n-2)! 
� Ta viết lại hàm giaithua bằng đệ quy như sau: 
/* Ham tinh giai thua */ 
long giaithua(int in) 
{ 
int i; 
if (in == 0) 
return (1L); 
else 
6 
return (in * giaithua(in – 1)); 
} 
� Chạy lại chương trình, quan sát, nhận xét và đánh giá kết quả 
� Giải thích hoạt động của hàm đệ quy giaithua 
Ví dụ giá trị truyền vào hàm giaithua qua biến in = 5. 
• Thứ tự gọi thực hiện hàm giaithua 
giaithua(in) return(in * giaithua(in – 1)) 
5 * giaithua(4) = 5 * ? 
4 * giaithua(3) = 4 * ? 
3 * giaithua(2) = 3 * ? 
2 * giaithua(1) = 2 * ? 
1 * giaithua(0) = 1 * ? 
Khi tham số in = 0 thì return về giá trị 1L (giá trị 1 kiểu long). Lúc này các giá trị 
? 
bắt đầu định trị theo thứ tự ngược lại. 
• Định trị theo thứ tự ngược lại 
giaithua(in) return(in * giaithua(in – 1)) 
1 * giaithua(0) = 1 * 1 = 1 
2 * giaithua(1) = 2 * 1 = 2 
3 * giaithua(2) = 3 * 2 = 6 
4 * giaithua(3) = 4 * 6 = 24 
5 * giaithua(4) = 5 * 24 = 120 
Kết quả sau cùng ta có 5! = 120. 
Thứ tự gọi đệ quy Định trị theo thứ tự ngược lạiA 
4.4. Bài tập 
1. Viết hàm đệ quy tính tổng n số nguyên dương đầu tiên: 
 tong (n) = n + tong (n – 1). 
2. Viết hàm đệ quy tính N! 
3. Viết hàm đệ qui. 
7 
Chương 2: Các kiểu dữ liệu cơ sở 
1. Khái niệm về kiểu dữ liệu 
Kiểu dữ liệu T có thể xem như là sự kết hợp của 2 thành phần: 
- Miền giá trị mà kiểu dữ liệu T có thể lưu trữ: V, 
- Tập hợp các phép toán để thao tác dữ liệu: O. 
T = 
Mỗi kiểu dữ liệu thường được đại diện bởi một tên (định danh). Mỗi phần tử dữ liệu 
có kiểu T sẽ có giá trị trong miền V và có thể được thực hiện các phép toán thuộc tập hợp 
các phép toán trong O. 
Để lưu trữ các phần tử dữ liệu này thường phải tốn một số byte(s) trong bộ 
nhớ, số byte(s) này gọi là kích thước của kiểu dữ liệu. 
2. Các kiểu dữ liệu cơ bản 
Kiểu số nguyên là kiểu dữ liệu dùng để lưu các giá trị nguyên hay còn gọi là 
kiểu đếm được. Kiểu số nguyên trong C được chia thành các kiểu dữ liệu con, mỗi 
kiểu có một miền giá trị khác nhau 
2.1. Kiểu số nguyên 1 byte (8 bits) 
Kiểu số nguyên một byte gồm có 2 kiểu sau: 
1. unsigned char Từ 0 đến 255 (tương đương 256 ký tự trong 
bảng mã ASCII) 
2. char Từ -128 đến 127 
Kiểu unsigned char: lưu các số nguyên dương từ 0 đến 255. 
=> Để khai báo một biến là kiểu ký tự thì ta khai báo biến kiểu unsigned char. 
Mỗi số trong miền giá trị của kiểu unsigned char tương ứng với một ký tự trong bảng mã 
ASCII . 
Kiểu char: lưu các số nguyên từ -128 đến 127. Kiểu char sử dụng bit trái nhất 
để làm bit dấu. 
 => Nếu gán giá trị > 127 cho biến kiểu char thì giá trị của biến này có thể là số 
âm (?). 
2.2. Kiểu số nguyên 2 bytes (16 bits) 
Kiểu số nguyên 2 bytes gồm có 4 kiểu sau: 
1. enum Từ -32,768 đến 32,767 
2. unsigned int Từ 0 đến 65,535 
3. short int Từ -32,768 đến 32,767 
4. int Từ -32,768 đến 32,767 
Kiểu enum, short int, int : Lưu các số nguyên từ -32768 đến 32767. Sử dụng 
8 
bit bên trái nhất để làm bit dấu. 
 => Nếu gán giá trị >32767 cho biến có 1 trong 3 kiểu trên thì giá trị của biến 
này có thể là số âm. 
Kiểu unsigned int: Kiểu unsigned int lưu các số nguyên dương từ 0 đến 65535. 
 2.3. Kiểu số nguyên 4 byte (32 bits) 
Kiểu số nguyên 4 bytes hay còn gọi là số nguyên dài (long) gồm có 2 kiểu sau: 
1. unsigned long Từ 0 đến 4,294,967,295 
2. long Từ -2,147,483,648 đến 2,147,483,647 
Kiểu long : Lưu các số nguyên từ -2147483658 đến 2147483647. Sử dụng bit 
bên trái nhất để làm bit dấu. 
=> Nếu gán giá trị >2147483647 cho biến có kiểu long thì giá trị của biến này 
có thể là số âm. 
Kiểu unsigned long: Kiểu unsigned long lưu các số nguyên dương từ 0 đến 
4294967295 
Kiểu số thực thường được thực hiện với các phép toán: O =?{+, -, *, /, , =, =, 
?}? 
2.4. Kiểu số thực: 
 Kiểu số thực dùng để lưu các số thực hay các số có dấu chấm thập phân gồm có 
3 kiểu sau: 
1. float 4 bytes Từ 3.4 * 10-38 đến 3.4 * 1038 
2. double 8 bytes Từ 1.7 * 10-308 đến 1.7 * 10308 
3. long double 10 bytes Từ 3.4 *10-4932 đến 1.1 *104932 
Mỗi kiểu số thực ở trên đều có miền giá trị và độ chính xác (số số lẻ) khác 
nhau. Tùy vào nhu cầu sử dụng mà ta có thể khai báo biến thuộc 1 trong 3 kiểu trên. 
Ngoài ra ta còn có kiểu dữ liệu void, kiểu này mang ý nghĩa là kiểu rỗng không chứa giá 
trị gì cả. 
Kiểu số nguyên thường được thực hiện với các phép toán: O =?{+, -, *, /, DIV, MOD, 
, =, =, ?}? 
2.5. Kiểu ký tự: Có thể có các kích thước sau: 
+ Kiểu ký tự byte 
+ Kiểu ký tự 2 bytes 
Kiểu ký tự thường được thực hiện với các phép toán: O =??{+, -, , =, 
=, ORD, CHR, ?}? 
- Kiểu chuỗi ký tự: Có kích thước tùy thuộc vào từng ngôn ngữ lập trình 
Kiểu chuỗi ký tự thường được thực hiện với các phép toán: O =??{+,???, 
, =, =, Length, Trunc, ?}? 
- Kiểu luận lý: Thường có kích thước 1 byte 
Kiểu luận lý thường được thực hiện với các phép toán: O =?{NOT, AND, OR, 
XOR, , =, =, ?}? 
9 
3. Các kiểu dữ liệu có cấu trúc 
3.1 Khái niệm: 
 Kiểu cấu trúc (Structure) là kiểu dữ liệu bao gồm nhiều thành phần có kiểu khác 
nhau, mỗi thành phần được gọi là một trường (field) 
 Sự khác biệt giữa kiểu cấu trúc và kiểu mảng là: các phần tử của mảng là cùng 
kiểu còn các phần tử của kiểu cấu trúc có thể có kiểu khác nhau. 
 Hình ảnh của kiểu cấu trúc được minh họa: 
3.2 Định nghĩa kiểu cấu trúc 
 struct 
 { 
 ; 
 ; 
 .. 
 ; 
 }; 
 Trong đó: 
 - : là một tên được đặt theo quy tắc đặt tên của danh biểu; tên 
này mang ý nghĩa sẽ là tên kiểu cấu trúc. 
 - (i=1..n): mỗi trường trong cấu trúc có dữ liệu thuộc kiểu 
gì (tên của trường phải là một tên được đặt theo quy tắc đặt tên của danh biểu). 
Ví dụ 1: Để quản lý ngày, tháng, năm của một ngày trong năm ta có thể khai 
báo kiểu cấu trúc gồm 3 thông tin: ngày, tháng, năm. 
struct NgayThang 
{ 
 unsigned char Ngay; 
 unsigned char Thang; 
 unsigned int Nam; 
}; 
 typedef struct 
 { 
10 
 unsigned char Ngay; 
 unsigned char Thang; 
 unsigned int Nam; 
} NgayThang; 
 Ví dụ 2: Mỗi sinh viên cần được quản lý bởi các thông tin: mã số sinh viên, họ 
tên, ngày tháng năm sinh, giới tính, địa chỉ thường trú. Lúc này ta có thể khai báo 
một struct gồm các thông tin trên. 
 struct SinhVien 
{ 
 char MSSV[10]; 
 char HoTen[40]; 
 struct NgayThang NgaySinh; 
 int Phai; 
 char DiaChi[40]; 
}; 
 typedef struct 
{ 
 char MSSV[10]; 
 char HoTen[40]; 
 NgayThang NgaySinh; 
 int Phai; 
 char DiaChi[40]; 
} SinhVien; 
3.3 Khai báo biến cấu trúc 
 Việc khai báo biến cấu trúc cũng tương tự như khai báo biến thuộc kiểu dữ liệu 
chuẩn. 
 Cú pháp: 
 - Đối với cấu trúc được định nghĩa theo cách 1: 
 struct [, ]; 
 - Đối với các cấu trúc được định nghĩa theo cách 2: 
 [, ]; 
 Ví dụ: Khai báo biến NgaySinh có kiểu cấu trúc NgayThang; biến SV có kiểu 
cấu trúc SinhVien. 
 struct NgayThang NgaySinh; 
struct SinhVien SV; 
NgayThang NgaySinh; 
SinhVien SV; 
4. kiểu tập hợp: 
4.1. khái niệm: 
Đối với các kiểu dữ liệu ta đã biết như kiểu số, kiểu mảng, kiểu cấu trúc thì dữ 
liệu kiểu tập hợp (typedef) là kiểu dữ liệu bao gồm nhiều thành phần có kiểu dữ liệu 
giống hoặ khác nhau, mỗi thành phần được gọi là một trường (field). 
11 
4.2.Khai báo biến tập hợp: 
 Sử dụng từ khóa typedef (Type definitions) để định nghĩa kiểu: 
 Typedef struct 
{ 
 ; 
 ; 
 .. 
 ; 
 } ; 
 Trong đó: 
 - typedef (Type definitions): là kiểu do người dùng định nghĩa. 
 - : là một tên được đặt theo quy tắc đặt tên của danh biểu; tên này 
mang ý nghĩa sẽ là tên kiểu cấu trúc. 
 ... ắp xếp thứ tự nội (sắp xếp thứ tự trên dãy/mảng), 
- Các giải thuật sắp xếp thứ tự ngoại (sắp xếp thứ tự trên tập tin/file). 
2. Các giải thuật sắp xếp cơ bản (Sắp xếp trên dãy/mảng) 
Ở đây, toàn bộ dữ liệu cần sắp xếp được đưa vào trong bộ nhớ trong (RAM). 
Do vậy, số 
phần tử dữ liệu không lớn lắm do giới hạn của bộ nhớ trong, tuy nhiên 
tốc độ sắp xếp 
tương đối nhanh. Các giải thuật sắp xếp nội bao gồm các nhóm sau: 
- Sắp xếp bằng phương pháp đếm (counting sort), 
- Sắp xếp bằng phương pháp đổi chỗ (exchange sort), 
- Sắp xếp bằng phương pháp chọn lựa (selection sort), 
- Sắp xếp bằng phương pháp chèn (insertion sort), 
- Sắp xếp bằng phương pháp trộn (merge sort). 
Trong phạm vi của giáo trình này chúng ta chỉ trình bày một số thuật toán 
sắp xếp tiêu biểu trong các thuật toán sắp xếp ở các nhóm trên và giả sử thứ 
tự sắp xếp N phần tử có kiểu dữ liệu T trong mảng M là thứ tự tăng. 
2.1. Sắp xếp bằng phương pháp đổi chỗ (Exchange Sort) 
Các thuật toán trong phần này sẽ tìm cách đổi chỗ các phần tử 
đứng sai vị trí (so với mảng đã sắp xếp) trong mảng M cho nhau để 
cuối cùng tất cả các phần tử trong mảng M đều về đúng vị trí như 
mảng đã sắp xếp. 
49 
Các thuật toán sắp xếp bằng phương pháp đổi chỗ bao gồm: 
- Thuật toán sắp xếp nổi bọt (bubble sort), 
- Thuật toán sắp xếp lắc (shaker sort), 
- Thuật toán sắp xếp giảm độ tăng hay độ dài bước giảm dần (shell 
sort), 
- Thuật toán sắp xếp dựa trên sự phân hoạch (quick sort). 
Ở đây chúng ta trình bày hai thuật toán phổ biến là thuật toán 
sắp xếp nổi bọt và sắp xếp dựa trên sự phân hoạch. 
a. Thuật toán sắp xếp nổi bọt (Bubble Sort): 
- Tư tưởng: 
+ Đi từ cuối mảng về đầu mảng, trong quá trình đi nếu phần 
tử ở dưới (đứng phía sau) nhỏ hơn phần tử đứng ngay trên 
(trước) nó thì theo nguyên tắc của bọt khí phần tử nhẹ sẽ bị 
"trồi" lên phía trên phần tử nặng (hai phần tử này sẽ được đổi 
chỗ cho nhau). Kết quả là phần tử nhỏ nhất (nhẹ nhất) sẽ được đưa 
lên (trồi lên) trên bề mặt (đầu mảng) rất nhanh. 
+ Sau mỗi lần đi chúng ta đưa được một phần tử trồi lên đúng chỗ. Do 
vậy, sau N-1 
lần đi thì tất cả các phần tử trong mảng M sẽ có thứ tự tăng. 
- Thuật toán: 
B1: First = 1 
B2: IF (First = N) 
Thực hiện Bkt 
B3: ELSE 
B3.1: Under = N 
B3.2: If (Under = First) 
Thực hiện B4 
B3.3: Else 
B3.3.1: if (M[Under] < M[Under - 1]) 
Swap(M[Under], M[Under - 1]) 
B3.3.2: Under-- 
B3.3.3: Lặp lại B3.2 
B4: First++ 
B5: Lặp lại B2 
Bkt: Kết thúc 
- Cài đặt thuật toán: 
Hàm BubbleSort có prototype như sau: 
void BubbleSort(T M[], int N); 
50 
//Đổi chỗ 2 phần tử cho nhau 
Hàm thực hiện việc sắp xếp N phần tử có kiểu dữ liệu T trên 
mảng M theo thứ tự tăng dựa trên thuật toán sắp xếp nổi bọt. Nội 
dung của hàm như sau: 
void BubbleSort(T M[], int N) 
{ for (int I = 0; I < N-1; I++) 
for (int J = N-1; J > I; J--) 
if (M[J] < M[J-1]) 
Swap(M[J], M[J-1]); 
return; 
}? 
Hàm Swap có prototype như sau: 
void Swap(T????X, T????Y); 
Hàm thực hiện việc hoán vị giá trị của hai phần tử X và Y 
cho nhau. Nội dung của hàm như sau: 
void Swap(T????X, T????Y) 
{ T Temp = X; 
X = Y; 
Y = Temp; 
return; 
}? 
- Ví dụ minh họa thuật toán: 
Giả sử ta cần sắp xếp mảng M có 10 phần tử sau (N = 10): 
M: 15 10 2 20 10 5 25 35 22 
30 
Ta sẽ thực hiện 9 lần đi (N - 1 = 10 - 1 = 9) để sắp xếp mảng M: 
- Phân tích thuật toán: 
+ Trong mọi trường hợp: 
Số phép gán: G = 0 
Số phép so sánh: S = (N-1) + (N-2) + ? + 1 = ½N(N-1) 
+ Trong trường hợp tốt nhất: khi mảng ban đầu đã có thứ tự tăng 
Số phép hoán vị: Hmin = 0 
+ Trong trường hợp xấu nhất: khi mảng ban đầu đã có thứ tự giảm 
Số phép hoán vị: Hmin = (N-1) + (N-2) + ? + 1 = ½N(N-1) 
+ Số phép hoán vị trung bình: Havg = ¼N(N-1) 
- Nhận xét về thuật toán nổi bọt: 
+ Thuật toán sắp xếp nổi bọt khá đơn giản, dễ hiểu và dễ cài đặt. 
51 
+ Trong thuật toán sắp xếp nổi bọt, mỗi lần đi từ cuối mảng về đầu 
mảng thì phần tử 
nhẹ được trồi lên rất nhanh trong khi đó phần tử nặng lại "chìm" 
xuống khá chậm 
chạp do không tận dụng được chiều đi xuống (chiều từ đầu mảng về 
cuối mảng). 
+ Thuật toán nổi bọt không phát hiện ra được các đoạn phần 
tử nằm hai đầu của mảng đã nằm đúng vị trí để có thể giảm bớt 
quãng đường đi trong mỗi lần 
2.2. sắp_xếp_chọn: 
Vấn đề xếp tiền : Có một xấp tiền gồm nhiều tờ có mệnh giá khác nhau đang để lộn 
xộn, cần 
 xếp lại theo thứ tự tiền nhỏ trước, tiền lớn sau. 
Phương pháp xếp tiền là: lần lượt chọn ra các tờ tiền từ nhỏ đến lớn để xếp cho 
đến khi hết 
 xấp tiền. 
Đối với mảng, các bước thực hiện là: 
• Trong N phần tử của mảng, chọn phần tử bé nhất, chuyển lên đầu mảng 
• Trong N-1 phần tử còn lại, chọn phần tử bé nhất, chuyển vào vị trí thứ 2 
• Tiếp tục cho đến khi sắp xếp hết. 
2.3. sắp xếp chèn: 
Phương pháp: 
• Giống như cách xếp bài khi được chia quân bài. 
• Quân bài mới nhận được chèn vào những quân bài đã có trên tay. 
• Các quân bài trên tay luôn được sắp xếp. 
• Thuật toán: 
void InsertionSort(int a[], int N) 
{ 
 int i, j, temp; 
 for(i = 1; i< N; i++) 
 { 
 temp = a[i]; 
 j = i- 1; 
 while ((j>=0)&&(a[j]>a[j+1])) 
 { 
 a[j+1] = a[j]; 
 j--; 
52 
 } 
 if (j!=i-1) 
 a[j+1] = temp; 
 } 
2.4. Sắp xếp phân đoạn: 
– Phương pháp: 
 Dùng giải pháp đệ quy (chia để trị) 
• Bước 1: Phân hoạch mảng A ban đầu thành 2 mảng con B và C sao cho bi 
 cj  bi B, cj C. 
• Bước 2: Sắp xếp mảng con B bằng đệ quy 
• Bước 3: Sắp xếp mảng con C bằng đệ quy 
• Điều kiện dừng: khi mảng con cần sắp chỉ có 1 phần tử xem như được 
sắp. 
• Vì B, C được sắp và bi cj nên mảng A là được sắp 
2.5. Sắp xếp hòa nhập: 
– Phương pháp: 
 Cũng sử dụng giải pháp chia để trị 
• Bước 1: Chia mảng A ban đầu thành 2 mảng con B và C. 
• Bước 2, 3: Sắp xếp mảng con B và C bằng đệ quy (Điều kiện dừng: khi 
mảng con cần sắp chỉ có 1 phần tử) 
• Bước 4: Trộn (merge) 2 mảng con đã sắp B, C thành mảng A được sắp. 
Thuật toán: 
int Partition(int a[], int p, int r) 
{ 
 int t; 
 // phân hoạch 
 return t; 
} 
void QuickSort(int a[], int p, int r) 
{ 
 int t = Partition(a, p, r); 
 if (p< t-1) QuickSort(a, p, t-1); 
 if (t+1< r) QuickSort(a, t+1, r); 
53 
} 
Chương 6: Tìm Kiếm 
1. Khái quát về tìm kiếm 
Trong thực tế, khi thao tác, khai thác dữ liệu chúng ta hầu như lúc 
nào cũng phải thực hiện thao tác tìm kiếm. Việc tìm kiếm nhanh hay 
54 
chậm tùy thuộc vào trạng thái và trật tự của dữ liệu trên đó. Kết quả 
của việc tìm kiếm có thể là không có (không tìm thấy) hoặc có (tìm 
thấy). Nếu kết quả tìm kiếm là có tìm thấy thì nhiều khi chúng ta còn 
phải xác định xem vị trí của phần tử dữ liệu tìm thấy là ở 
đâu? Trong phạm vi của chương này chúng ta tìm cách giải quyết 
các câu hỏi này. 
Trước khi đi vào nghiên cứu chi tiết, chúng ta giả sử rằng mỗi 
phần tử dữ liệu được xem xét có một thành phần khóa (Key) để 
nhận diện, có kiểu dữ liệu là T nào đó, các thành phần còn lại là 
thông tin (Info) liên quan đến phần tử dữ liệu đó. Như vậy 
mỗi phần tử dữ liệu có cấu trúc dữ liệu như sau: 
typedef 
{ T 
struct DataElement 
Key; 
InfoType 
} DataType; 
Info; 
Trong tài liệu này, khi nói tới giá trị của một phần tử dữ liệu chúng ta 
muốn nói tới giá trị khóa (Key) của phần tử dữ liệu đó. Để đơn 
giản, chúng ta giả sử rằng mỗi phần tử dữ liệu chỉ là thành phần 
khóa nhận diện. 
Việc tìm kiếm một phần tử có thể diễn ra trên một dãy/mảng (tìm 
kiếm nội) hoặc diễn ra trên một tập tin/ file (tìm kiếm ngoại). Phần tử 
cần tìm là phần tử cần thỏa mãn điều kiện tìm kiếm (thường có giá trị 
bằng giá trị tìm kiếm). Tùy thuộc vào từng bài toán cụ thể mà điều 
kiện tìm kiếm có thể khác nhau song chung quy việc tìm kiếm 
dữ liệu thường được vận dụng theo các thuật toán trình bày sau đây. 
2. Tìm tuần tự (Linear Search) 
Thuật toán tìm tuyến tính còn được gọi là Thuật toán tìm kiếm 
tuần tự (Sequential Search). 
a. Tư tưởng: 
Lần lượt so sánh các phần tử của mảng M với giá trị X bắt 
đầu từ phần tử đầu tiên cho đến khi tìm đến được phần tử có giá trị 
X hoặc đã duyệt qua hết tất cả các phần tử của mảng M thì kết thúc. 
b. Thuật toán: 
B1: k = 1 
B2: IF M[k]?? X AND k?? N 
B2.1: k++ 
55 
B2.2: Lặp lại B2 
B3: IF k?? N 
Tìm thấy tại vị trí k 
B4: ELSE 
//Duyệt từ đầu mảng 
//Nếu chưa tìm thấy và cũng chưa duyệt hết mảng 
Không tìm thấy phần tử có giá trị X 
B5: Kết thúc 
c. Cài đặt thuật toán: 
Hàm LinearSearch có prototype: 
int LinearSearch (T M[], int N, T X); 
Hàm thực hiện việc tìm kiếm phần tử có giá trị X trên mảng M có N 
phần tử. Nếu tìm thấy, hàm trả về một số nguyên có giá trị từ 0 đến 
N-1 là vị trí tương ứng của phần tử tìm thấy. Trong trường hợp 
ngược lại, hàm trả về giá trị -1 (không tìm thấy). Nội dung của 
hàm như sau: 
int LinearSearch (T M[], int N, T X) 
{ int k = 0; 
while (M[k] != X??? k < N) 
k++; 
if (k < N) 
return (k); 
return (-1); 
}? 
d. Phân tích thuật toán: 
- Trường hợp tốt nhất khi phần tử đầu tiên của mảng có giá trị bằng X: 
Số phép gán: Gmin = 1 
Số phép so sánh: Smin = 2 + 1 = 3 
- Trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng 
X: 
Số phép gán: Gmax = 1 
Số phép so sánh: Smax = 2N+1 
- Trung bình: 
Số phép gán: Gavg = 1 
Số phép so sánh: Savg = (3 + 2N + 1) : 2 = N + 2 
e. Cải tiến thuật toán: 
Trong thuật toán trên, ở mỗi bước lặp chúng ta cần phải thực hiện 2 
phép so sánh để kiểm tra sự tìm thấy và kiểm soát sự hết mảng trong 
quá trình duyệt mảng. Chúng ta có thể giảm bớt 1 phép so sánh nếu 
chúng ta thêm vào cuối mảng một phần tử cầm canh (sentinel/stand 
56 
by) có giá trị bằng X để nhận diện ra sự hết mảng khi duyệt 
mảng, khi đó thuật toán này được cải tiến lại như sau: 
 B1: k = 1 
B2: M[N+1] = X 
B3: IF M[k]?? X 
B3.1: k++ 
B3.2: Lặp lại B3 
B4: IF k < N 
Tìm thấy tại vị trí k 
B5: ELSE 
//Phần tử cầm canh 
//k = N song đó chỉ là phần tử cầm canh 
Không tìm thấy phần tử có giá trị X 
B6: Kết thúc 
Hàm LinearSearch được viết lại thành hàm LinearSearch1 như sau: 
int LinearSearch1 (T M[], int N, T X) 
{ int k = 0; 
M[N] = X; 
while (M[k] != X) 
k++; 
if (k < N) 
return (k); 
return (-1); 
}? 
f. Phân tích thuật toán cải tiến: 
- Trường hợp tốt nhất khi phần tử đầu tiên của mảng có giá trị bằng X: 
Số phép gán: Gmin = 2 
Số phép so sánh: Smin = 1 + 1 = 2 
- Trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng 
X: 
Số phép gán: Gmax = 2 
Số phép so sánh: Smax = (N+1) + 1 = N + 2 
- Trung bình: 
Số phép gán: Gavg = 2 
Số phép so sánh: Savg = (2 + N + 2) : 2 = N/2 + 2 
- Như vậy, nếu thời gian thực hiện phép gán không đáng kể thì thuật 
toán cải tiến sẽ chạy nhanh hơn thuật toán nguyên thủy. 
57 
3. Tìm nhị phân (Binary Search) 
Thuật toán tìm tuyến tính tỏ ra đơn giản và thuận tiện trong trường 
hợp số phần tử của dãy không lớn lắm. Tuy nhiên, khi số phần tử của 
dãy khá lớn, chẳng hạn chúng ta tìm kiếm tên một khách hàng 
trong một danh bạ điện thoại của một thành phố lớn theo thuật 
toán tìm tuần tự thì quả thực mất rất nhiều thời gian. Trong thực tế, 
thông thường các phần tử của dãy đã có một thứ tự, do vậy 
thuật toán tìm nhị phân sau đây sẽ rút ngắn đáng kể thời gian tìm 
kiếm trên dãy đã có thứ tự. Trong thuật toán này chúng ta giả sử các 
phần tử trong dãy đã có thứ tự tăng (không giảm dần), tức là 
các phần tử đứng trước luôn có giá trị nhỏ hơn hoặc bằng 
(không lớn hơn) phần tử đứng sau nó. 
Khi đó, nếu X nhỏ hơn giá trị phần tử đứng ở giữa dãy 
(M[Mid]) thì X chỉ có thể tìm thấy ở nửa đầu của dãy và ngược 
lại, nếu X lớn hơn phần tử M[Mid] thì X chỉ có thể tìm thấy ở nửa sau 
của dãy. 
a. Tư tưởng: 
Phạm vi tìm kiếm ban đầu của chúng ta là từ phần tử đầu tiên 
của dãy (First = 1) cho đến phần tử cuối cùng của dãy (Last = N). 
So sánh giá trị X với giá trị phần tử đứng ở giữa của dãy M là 
M[Mid]. 
Nếu X = M[Mid]: Tìm thấy 
Nếu X < M[Mid]: Rút ngắn phạm vi tìm kiếm về nửa đầu của dãy M 
(Last = Mid-1) 
Nếu X > M[Mid]: Rút ngắn phạm vi tìm kiếm về nửa sau của dãy M 
(First = Mid+1) 
Lặp lại quá trình này cho đến khi tìm thấy phần tử có giá trị 
X hoặc phạm vi tìm kiếm của chúng ta không còn nữa (First > 
Last). 
b. Thuật toán đệ quy (Recursion Algorithm): 
B1: First = 1 
B2: Last = N 
B3: IF (First > Last) 
B3.1: Không tìm thấy 
B3.2: Thực hiện Bkt 
B4: Mid = (First + Last)/ 2 
B5: IF (X = M[Mid]) 
//Hết phạm vi tìm kiếm 
B5.1: Tìm thấy tại vị trí Mid 
B5.2: Thực hiện Bkt 
58 
B6: IF (X < M[Mid]) 
Tìm đệ quy từ First đến Last = Mid - 1 
B7: IF (X > M[Mid]) 
Tìm đệ quy từ First = Mid + 1 đến Last 
Bkt: Kết thúc 
c. Cài đặt thuật toán đệ quy: 
Hàm BinarySearch có prototype: 
int BinarySearch (T M[], int N, T X); 
Hàm thực hiện việc tìm kiếm phần tử có giá trị X trong mảng M có N 
phần tử đã có thứ tự tăng. Nếu tìm thấy, hàm trả về một số nguyên có 
giá trị từ 0 đến N-1 là vị trí tương ứng của phần tử tìm thấy. 
Trong trường hợp ngược lại, hàm trả về giá trị -1 (không tìm 
thấy). Hàm BinarySearch sử dụng hàm đệ quy RecBinarySearch 
có prototype: 
int RecBinarySearch(T M[], int First, int Last, T X); 
Hàm RecBinarySearch thực hiện việc tìm kiếm phần tử có giá 
trị X trên mảng M trong phạm vi từ phần tử thứ First đến phần 
tử thứ Last. Nếu tìm thấy, hàm trả về một số nguyên có giá trị 
từ First đến Last là vị trí tương ứng của phần tử tìm thấy. 
Trong trường hợp ngược lại, hàm trả về giá trị -1 (không tìm thấy). 
4.Câu hỏi và Bài tập 
1. Trình bày tư tưởng của các thuật toán tìm kiếm: Tuyến tính, Nhị 
phân, Chỉ mục? Các thuật toán này có thể được vận dụng trong các 
trường hợp nào? Cho ví dụ? 
2. Cài đặt lại thuật toán tìm tuyến tính bằng các cách: 
- Sử dụng vòng lặp for, 
- Sử dụng vòng lặp do  while? 
Có nhận xét gì cho mỗi trường hợp? 
Trong trường hợp các phần tử của dãy đã có thứ tự tăng, hãy cải tiến 
lại thuật toán tìm tuyến tính? Cài đặt các thuật toán cải tiến? Đánh giá 
và so sánh giữa thuật toán nguyên thủy với các thuật toán cải tiến. 
4. Trong trường hợp các phần tử của dãy đã có thứ tự giảm, hãy trình 
bày và cài đặt lại thuật toán tìm nhị phân trong hai trường hợp: Đệ 
quy và Không đệ quy? 
5. Vận dụng thuật toán tìm nhị phân, hãy cải tiến và cài đặt lại thuật 
toán tìm kiếm dựa theo tập tin chỉ mục? Đánh giá và so sánh giữa 
thuật toán nguyên thủy với các thuật toán cải tiến? 
59 
6. Sử dụng hàm random trong C để tạo ra một dãy (mảng) M có tối 
thiểu 1.000 số nguyên, sau đó chọn ngẫu nhiên (cũng bằng hàm 
random) một giá trị nguyên K. Vận dụng các thuật toán tìm tuyến 
tính, tìm nhị phân để tìm kiếm phần tử có giá trị K trong mảng M. 
Với cùng một dữ liệu như nhau, cho biết thời gian thực hiện các thuật 
toán. 
7. Trình bày và cài đặt thuật toán tìm tuyến tính đối với các phần tử 
trên mảng hai chiều trong hai trường hợp: 
- Không sử dụng phần tử “Cầm canh”. 
- Có sử dụng phần tử “Cầm canh”. 
Cho biết thời gian thực hiện của hai thuật toán trong hai trường hợp 
trên. 
8. Sử dụng hàm random trong C để tạo ra tối thiểu 1.000 số nguyên và 
lưu trữ vào mot tập tin có tên SONGUYEN.DAT, sau đó chọn ngẫu 
nhiên (cũng bằng hàm random) một giá trị nguyên K. Vận dụng thuật 
toán tìm tuyến tính để tìm kiếm phần tử có giá trị K trong tập tin 
SONGUYEN.DAT.