Bài giảng Cấu trúc dữ liệu và thuật toán trên C

MỤC LỤC
CHƯƠNG 1: GIỚI THIỆU CHUNG
1.1. Thuật toán và cấu trúc dữ liệu:
	Theo Niklaus Wirth: Thuật toán + Cấu trúc dữ liệu = Chương trình.
	Ví dụ: Cho 1 dãy các phần tử, có thể biểu diễn dưới dạng mảng hoặc danh sách.
	Cấu trúc dữ liệu và thuật toán có mối quan hệ mật thiết với nhau. do đó việc nghiên cứu các cấu trúc dữ liệu sau này đi đôi với việc xác lập các thuật toán xử lý trên các cấu trúc ấy.
1.2. Một số vấn đề liên quan:
	Lựa chọn một cấu trúc dữ liệu thích hợp để tổ chức dữ liệu vào ra và trên cơ sở đó xây dựng được thuật toán xử lý hữu hiệu nhằm đưa tới kết quả mong muốn cho bài toán là một khâu rất quan trọng.
	Ta cần phân biệt 2 loại quy cách dữ liệu: 
Quy cách biểu diễn hình thức: Còn được gọi là cấu trúc logic của dữ liệu. Đối với mỗi ngôn ngữ lập trình xác định sẽ có một bộ cấu trúc logic của dữ liệu. Dữ liệu thuộc loại cấu trúc nào thì cần phải có mô tả kiểu dữ liệu tương ứng với cấu trúc dữ liệu đó. Ví dụ: Trong C có các kiểu dữ liệu: Struct, Union, File,..
Quy cách lưu trữ: là cách biểu diễn một cấu trúc dữ liệu trong bộ nhớ. Ví dụ: Cấu trúc dữ liệu mảng được lưu trữ trong bộ nhớ theo quy tắc lưu trữ kế tiếp. Có 2 quy cách lưu trữ:
 Lưu trữ trong: ví dụ RAM.
 Lưu trữ ngoài: ví dụ đĩa (disk).
1.3. Ngôn ngữ diễn đạt thuật toán:
	Ngôn ngữ diễn đạt thuật toán được quy ước sử dụng trong giáo trình này là ngôn ngữ tựa C++.
	Đặc điểm: Gần giống với Turbo C++, do đó dễ dàng trong việc chuyển một chương trình viết bằng ngôn ngữ tựa C++ sang ngôn ngữ C++.
1.3.1. Cấu trúc của một chương trình chính:
void main()
{
	S1;
Các lệnh của chương trình dùng để diễn tả thuật toán
	S2;
	...
	Sn;
}
Lưu ý:
Để đơn giản, chương trình có thể không cần viết khai báo. Tuy nhiên có thể mô tả trước chương trình bằng ngôn ngữ tự nhiên.
Phần thuyết minh được đặt giữa 2 dấu /* , */ hoặc // để ghi chú trên 1 dòng.
Ví dụ:	
void main() /* Chuong trinh chuyen so he 10 thanh he 2*/
{
cout << "n = ";
cin >> n; /* Nhap n la so he cs 10*/
T=0;
while (n!=0)
	{
	r = n % 2;
	Push(T, r);
	n = n / 2;
	}
cout << "Ket qua chuyen doi sang he co so 2 la: ";
while (T!=0)
	{
	Pop(T, r);
	cout << r;
	}
}
1.3.2. Các ký tự:
 Các ký tự sử dụng trong chương trình là tương tự như trong C++.
Lưu ý: Trong C++ là có sự phân biệt giữa chữ hoa và chữ thường.
1.3.3. Các câu lệnh:
-	Lệnh gán: V = E;
	Trong đó: V là biến (variable), và E là biểu thức (expression).
	Lưu ý: Có thể dùng phép gán chung. Ví dụ: a=b=1; 
-	Lệnh ghép: {S1; S2; ...; Sn;} coi như là một câu lệnh (trong đó Si là các câu lệnh).
-	Lệnh if: Tương tự như lệnh if của ngôn ngữ C.
 if () ;
hoặc: if () ;
 else ;	
-	Lệnh switch: Theo cấu trúc sau:
	switch () 
	{
	case gt1: S1;
	case gt2: S2; 
	...
	case gtn: Sn; 
	[default : Sn+1;]
	}
-	Lệnh lặp: for, while, do ... while: Tương tự như các lệnh lặp của C.
-	Lệnh nhảy: goto n (n: số hiệu/nhãn của chương trình).
- 	Lệnh vào ra: cin và cout giống như C++.
1.3.4. Chương trình con: 
	 ()
 {
	S1;
	S2;
	...
	S3;
 [return (giá trị trả về) ]	 Báo kết thúc chương trình con
 }
Lưu ý: Nếu hàm có kiểu trả về khác kiểu void thì khi kết thúc hàm phải có câu lệnh return để gán kết quả cho hàm.
Sau đây là ví dụ về hàm có trả về giá trị.
Ví dụ: Viết chương trình con dạng hàm NamNhuan(x). Cho kết quả nếu số x là năm nhuận có giá trị là True(1), ngược lại có giá trị là False(0); chẳng hạn: NamNhuan(1996) cho giá trị 1, NamNhuan(1997) cho giá trị 0. Biết rằng x được gọi là năm nhuận nếu x chia hết cho 4 và x không chia hết cho 100 hoặc x chia hết cho 400.
	Cách 1: int namnhuan(x)
	{	if ((x % 4 == 0 && x % 100 != 0)||(x % 400 == 0))
	return 1;
	else
	 return 0;
	}
	Cách 2: int namnhuan(x)
	 { return(((x % 4 == 0) && (x % 100 != 0)) ||
	 (x % 400 = 0));
	}
Ví dụ viết về chương trình con không có giá trị trả về (hay còn gọi là thủ tục).
Ví dụ: Viết hàm Hoandoi(a, b) để hoán đổi giá trị của 2 biến số a và b cho nhau.
	Cách 1:	void hoandoi(&a, &b) //a và b là các tham biến
	 	{	tam=a;
	a=b;
	b=tam;
	}
	Cách 2:	void hoandoi(&a, &b)
	 	{	a= a+b;
	b= a-b;
	a= a-b;
	}
Lưu ý: Bên trong 1 chương trình con có thể dùng lệnh return; (thoát khỏi chương trình con), exit(1) (thoát khỏi chương trình chính).
CHƯƠNG 2: THIẾT KẾ VÀ PHÂN TÍCH THUẬT TOÁN
2.1. Thiết kế thuật toán:
2.1.1. Module hoá thuật toán:
	Các bài toán ngày càng đa dạng và phức tạp, do đó thuật toán mà ta đề xuất càng có quy mô lớn và việc viết chương trình cần có một lượng lập trình đông đảo. Muốn làm được việc này , người ta phân chia các bài toán lớn thành các bài toán nhỏ (module). Và dĩ nhiên một module có thể chia nhỏ thành các module con khác nữa,... bấy giờ việc tổ chức lời giải sẽ được thể hiện theo một cấu trúc phân cấp.
A
B
C
E
F
G
H
I
D
	Ví dụ:
	Quá trình module hoá bài toán được xem là nguyên lý “chia để trị” (divide & conquer) hay còn gọi là thiết kế từ đỉnh xuống (top-down) hoặc là thiết kế từ khái quát đến chi tiết (specialization).
	Việc module hoá trong lập trình thể hiện ở:
Các chương trình con.
Cụm các chương trình con xung quanh một cấu trúc dữ liệu nào đó. Chẳng hạn, thư viện trong C.
Ví dụ: Chương trình quản lý đầu sách của một thư viện nhằm phục vụ độc giả tra cứu sách. Cụ thể, giả sử ta đã có một file dữ liệu gồm các bảng ghi về các thông tin liên quan đến một đầu sách như: tên sách, mã số, tác giả, nhà xuất bản, năm xuất bản, giá tiền, ...
Yêu cầu:
-	Cập nhật dữ liệu được.
-	Tìm kiếm.
Hệ chương trình quản lý sách
Cập nhật dữ liệu
Tìm kiếm
In ấn
Bổ sung thêm sách
Sửa thông tin file dữ liệu
Xoá dữ liệu
Xem với mọi bản ghi
Tra cứu
Thẻ sách
Thống kê
Theo mã
Theo ngày nhập
-	In ấn.
Nhận xét:
-	Việc module hoá làm cho bài toán được định hướng rõ ràng.
-	Bằng cách này, người ta có thể phân chia công việc cho đội ngũ lập trình.
-	Đây là một công việc mất nhiều thời gian.
2.1.2. Phương pháp tinh chỉnh từng bước:
	Phương pháp tinh chỉnh từng bước là phương pháp thiết kế thuật toán gắn liền với lập trình. Nó phản ánh tinh thần của quá trình module hoá và thiết kế thuật toán theo kiểu top-down.
	Xuất phát từ ngôn ngữ tự nhiên của thuật toán, thuật toán sẽ được chi tiết hoá dần dần và cuối cùng công việc xử lý sẽ được thay thế dần bởi các câu lệnh (của một ngôn ngữ lập trình nào đó). Quá trình này là để trả lời dần dần các câu hỏi: What? (làm gì?), How (làm như thế nào?)
2.2. Phân tích thuật toán: 
Chất lượng của một chương trình hay thuật toán bao gồm:
-	Tính đúng đắn.
-	Tính đơn giản (dễ hiểu, dễ quản lý, dễ lập).
-	Tính tối ưu (hiệu quả) về mặt thời gian cũng như không gian nhớ.
2.2.1. Tính đúng đắn:
	Đây là một yêu cầu phân tích quan trọng nhất cho một thuật toán. Thông thường, người ta thử nghiệm (test) nhờ một số bộ dữ liệu nào đó để cho chạy chương trình rồi so sánh kết quả thử nghiệm với kết quả mà ta đã biết. Tuy nhiên, theo Dijkstra: “Việc thử nghiệm chương trình chỉ chứng minh sự có mặt của lỗi chứ không chứng minh sự vắng mặt của lỗi”.
	Ngày nay, với các công cụ toán học người ta có thể chứng minh tính đúng đắn của một thuật toán.
2.2.2. Mâu thuẫn giữa tính đơn giản và tính hiệu quả:
	Một thuật toán đơn giản (dễ hiểu) chưa hẳn tối ưu về thời gian và bộ nhớ. Đối với những chương trình chỉ dùng một vài lần thì tính đơn giản có thể coi trọng nhưng nếu chương trình được sử dụng nhiều lần (ví dụ, các phần mềm) thì thời gian thực hiện rõ ràng phải được chú ý.
	Yêu cầu về thời gian và không gian ít khi có một giải pháp trọn vẹn.
2.2.3. Phân tích thời gian thực hiện thuật toán:
	Thời gian thực hiện thuật toán phụ thuộc vào nhiều yếu tố:
Kích thước dữ liệu đưa vào (dung lượng). Nếu gọi n là kích thước dữ liệu vào thì thời gian thực hiện một thuật toán, ký hiệu là T(n).
Tốc độ xử lý của máy tính, bộ nhớ (RAM).
Ngôn ngữ để viết chương trình.
	Tuy nhiên, ta có thể so sánh thời gian thực hiện của hai thuật toán khác nhau.
	Ví dụ:	Nếu thời gian thực hiện của thuật toán thứ nhất T1(n) = Cn2 (C: hằng dương) và thời gian thực hiện thuật toán thứ hai T2(n) = Kn (K: hằng) thì khi n khá lớn, thời gian thực hiện thuật toán 2 sẽ tối ưu hơn so với thuật toán 1.
	Cách đánh giá thời gian thực hiện thuật toán theo kiểu trên được gọi là đánh giá thời gian thực hiện thuật toán theo “độ phức tạp tính toán của thuật toán”.
2.2.3.1. Độ phức tạp tính toán của thuật toán:
	Nếu thời gian thực hiện một thuật toán là T(n) = Cn2 (C: hằng), thì ta nói rằng: Độ phức tạp tính toán của thuật toán này có cấp là n2 và ta ký hiệu T(n) = O(n2).
	Tổng quát: T(n) = O(g(n)) thì ta nói độ phức tạp của thuật toán có cấp là g(n).
2.2.3.2. Xác định độ phức tạp của thuật toán:
	Việc xác định độ phức tạp tính toán của một thuật toán nói chung là phức tạp. Tuy nhiên, trong thực tế độ phức tạp của một thuật toán có thể được xác định từ độ phức tạp từng phần của thuật toán. Cụ thể, ta có một số quy tắc sau:
-	Quy tắc tính tổng:
	Nếu chương trình P được phân tích thành 2 phần: P1, P2 và nếu độ phức tạp của P1 là T1(n) = O(g1(n)) và độ phức tạp của P2 là T2(n) = O(g2(n)) thì độ phức tạp của P là: T(n) = O(max(g1(n), g2(n))).
	Ví dụ: g1(n) = n2, g2(n) = n3. Suy ra: T(n) = O(n3).
	Lưu ý: 	g1(n) £ g2(n)	("n ³ n0) Þ O(g1(n) + g2(n)) = O(g2(n))
	Ví dụ:	O(n + log2n) = O(n)
-	Quy tắc nhân:
	Nếu độ phức tạp của P1 là O(g1(n)), độ phức tạp của P2 là O(g2(n)) thì độ phức tạp của P1 lồng P2 (P1 câu lệnh lặp) thì độ phức tạp tính toán là O(g1(n).g2(n)).
Lưu ý:
Câu lệnh gán, cin, cout, if, switch có thời gian thực hiện bằng hằng số C = O(1).
Câu lệnh lặp trong vòng g(n) lần thì sẽ có thời gian thực hiện là O(g(n)).
O(Cg(n)) = O(g(n))	(C: hằng)
	Ví dụ:
	1)	Câu lệnh:	for (i=1;i<=n;i++)	// O(n) 
	 P=P*i;	// O(1) 
	có thời gian thực hiện là: O(n*1) = O(n).
	2)	for (i=1;i<=n;i++)
	for (j=1;j<=n;j++) x=x+1;
	có thời gian thực hiện là: O(n*n*1) = O(n2).
Thông thường, để xác định độ phức tạp tính toán của một thuật toán, người ta đi tìm một lệnh/phép toán có số lần thực hiện là nhiều nhất (lệnh/phép toán tích cực) từ đó tính số lần này Þ độ phức tạp của tính toán.
Có khi thời gian thực hiện một thuật toán còn phụ thuộc vào đặc điểm của dữ liệu. Bấy giờ T(n) trong trường hợp thuận lợi nhất có thể khác T(n) trong trường hợp xấu nhất. Tuy nhiên, thông thường người ta vẫn đánh giá độ phức tạp tính toán của thuật toán thông qua T(n) trong trường hợp xấu nhất.
	Ví dụ: Cho một dãy gồm có n phần tử mảng: V[0], V[1], ..., V[n-1]. X là một giá trị cho trước.
	void timkiem(x)
	{
	found=0;// gán giá trị cho found lúc ban đầu là False
	i=0;
	while ((i< n) && (!found)) 
	if (v[i]==x)
	{
	cout << i; found=1;
	}
	else i=i+1;
	if (found==0) 
	cout << “không có”;
	}
	Þ	T(n) thuận lợi = O(1)	(X = V[0])
	 	T(n) xấu nhất = O(n)	(X ¹ V[i], "i=0..n-1)
T(n) = O(n)
CHƯƠNG 3: ĐỆ QUY (RECURSION)
3.1. Đại cương:
-	Chương trình đệ quy là chương trình gọi đến chính nó.
	Ví dụ: Một hàm đệ quy là một hàm được định nghĩa dựa vào chính nó.
-	Trong lý thuyết tin học, người ta thường dùng thủ thuật đệ quy để định nghĩa các đối tượng.
	Ví dụ: Tên biến được định nghĩa như sau:
	- Mỗi chữ cái là một tên.
	- Nếu t là tên biến thì t , t cũng là tên biến.
-	Một chương trình đệ quy hoặc một định nghĩa đệ quy thì không thể gọi đến chính nó mãi mãi mà phải có một điểm dừng đến một trường hợp đặc biệt nào đó, mà ta gọi là trường hợp suy biến (degenerate case).
	Ví dụ: Cho số tự nhiên n, ta định nghĩa n! như sau:	n! = 
-	Lời giải đệ quy: Nếu lời giải của một bài toán T nào đó được thực hiện bằng một lời giải của bài toán T' có dạng giống như T, nhưng theo một nghĩa nào đó T' là "nhỏ hơn" T và T' có khuynh hướng ngày càng tiếp cận với trường hợp suy biến.
	Ví dụ: Cho dãy các phần tử mảng V[1], V[2], ..., V[n] đã được sắp xếp theo thứ tự tăng dần, gọi X là một giá trị bất kỳ. Viết thuật toán tìm kiếm để in vị trí của phần tử nào đó trong mảng có giá trị bằng X (nếu có). Ngược lại, thông báo không có.
	void timkiem(d, c, x)
	{
	if (d>c) 
 cout << “khong co”;
	else
	{
	g=(d+c)/ 2;
	if (x==V[g]) 
 cout << g;
	else if (x<V[g]) timkiem(d, g-1, x);
	 else timkiem(g+1, c, x);
	}
	}
Nhận xét:
Bài toán tìm kiếm ban đầu được tách thành các bài toán tìm kiếm với phạm vi nhỏ hơn cho đến khi gặp phải các trường hợp suy biến. Chính việc phân tích đó, người ta đã xem thuật toán đệ quy là thuật toán thể hiện phương pháp "chia để trị".
Nếu thủ tục hoặc hàm chứa lời gọi đến chính nó (ví dụ trên) thì được gọi là đệ quy trực tiếp. Ngược lại, có thủ tục chứa lời gọi đến thủ tục khác mà ở thủ tục này chứa lại lời gọi đến nó thì được gọi là đệ quy gián tiếp, hay còn gọi là đệ quy tương hỗ hay còn gọi là Forward.
	Ví dụ:
	void Ba(int n)
	{
	cout << n;
	if (n>0) Ong(n-1);
	}
	void	Ong(int n);
	{
	cout << n;
	if (n>0) Ba(n-1);
	}
 void main()
	{
	Ong(3);
	}
	Kết quả:	3 Ong
	2 Ba
	1 Ong
	0 Ba
3.2. Phương pháp để thiết kế một thuật toán đệ quy:
-	Tham số hoá bài toán.
-	Phân tích trường hợp chung (đưa bài toán dưới dạng bài toán cùng loại nhưng có phạm vi giải quyết nhỏ hơn theo nghiã dần dần sẽ tiến đến trường hợp suy biến).
-	Tìm trường hợp suy biến.
Ví dụ:
Lập hàm GT(n) = n!
long GT(n)
	{	if (n==0) return 1;
	else return n*GT(n-1);
	}
	2)	Dãy số Fibonaci:	F1 = F2 = 1;
	Fn = Fn-1 + F n-2. (n ³ 3)
	long F(n)
	{	if (n£ 2) return 1;
	else return F(n-1)+F(n-2);
	}
Nhận xét:
-	Thông thuờng thay vì sử dụng lời giải đệ quy cho một bài toán, ta có thể thay thế bằng lời giải không đệ quy (khử đệ quy) bằng phương pháp lặp.
-	Việc sử dụng thuật toán đệ quy có:
Ưu điểm
Khuyết điểm
Thuận lợi cho việc biểu diễn bài toán.
Có khi không được tối ưu về thời gian.
Gọn (đối với chương trình).
Có thể gây tốn bộ nhớ à xảy ra hiện tượng tràn bộ nhớ ngăn xếp (Stack) nếu dữ liệu lớn.
-	Chính vì vậy, trong lập trình người ta cố tránh sử dụng thủ tục đệ quy nếu thấy không cần thiết.
§ Bài tập:
1) Viết hàm luỹ thừa float lt(float x, int n) cho ra giá trị xn.
2)	Viết chương trình nhập vào số nguyên rồi đảo ngược số đó lại (không được dùng phương pháp chuyển số thành xâu).
3)	Viết chương trình cho phép sản sinh và hiển thị tất cả các số dạng nhị phân độ dài n (có gồm n chữ số).
Ví dụ 1: Viết thủ tục in xâu đảo ngược của xâu X.
Trước khi xây dựng hàm InNguoc thì ta xây dựng hàm tách chuỗi con từ chuỗi mẹ trước từ vị trí là batdau và lấy soluong ký tự.
char *copy(char *chuoi,int batdau,int soluong)
 { int i; char *tam;
 tam=(char *)malloc(100);
 for(i=(batdau-1);i<strlen(chuoi)&& i<(batdau-1+soluong);i++)
 	tam[i-(batdau-1)]=chuoi[i];
 tam[i]=NULL;
 return tam;
}
	Cách 1:
	-	Trường hợp chung:	+ In ký tự cuối của xâu X.
	+ Đảo ngược phần còn lại.
	-	Trường hợp suy biến: Nếu xâu rỗng thì không làm gì hết.
	void	InNguoc(X){
	if (X[0] !=’’) 	
	{
	cout << X[strlen(X)-1];
	InNguoc(copy(X,0,strlen(x)-2);
	}
	}
	Cách 2:
	-	Trường hợp chung:	+ Đảo ngược xâu X đã bỏ ký tự đầu tiên.
	+ In ký tự đầu tiên của X.
	-	Trường hợp suy biến: Nếu xâu rỗng thì không làm gì hết.
	void Innguoc(X){
	if (X!=”“) 
	{
	InNguoc(copy(X, 1,strlen(X)-2);
	cout << X[0];
	 }
	}
Ví dụ 2:	Bài toán  ...  1
 3
V[2]
 1
 2
 4
 5
V[3]
 3
 5
V[4]
 3
 4
V[5]
Nhận xét:
-	Mỗi đỉnh của G có một danh sách tương ứng. Các nút ở trong danh sách i (trỏ bởi V[i]) biểu diễn các đỉnh lân cận của nút i. Mỗi nút có dạng:
Đỉnh
Tiếp
-	Mỗi danh sách i có một nút đầu danh sách (V[i]), các nút này thường được tổ chức thành một mảng để có thể truy cập được nhanh.
Lưu ý: Các nút trong từng danh sách thông thường sắp xếp theo thứ tự.
7.3. Phép duyệt một đồ thị:
7.3.1. Tìm kiếm theo chiều sâu:
	Xét đồ thị không định hướng và liên thông, phép tìm kiếm theo chiều sâu được thực hiện như sau:
	Đầu tiên thăm đỉnh V, sau đó thăm đỉnh W (đỉnh này chưa được thăm) là lân cận của V. Bấy giờ từ W, một phép tìm kiếm theo chiều sâu xuất phát từ W lại được thực hiện. Khi một đỉnh U vừa (đã) được thăm mà mọi đỉnh lân cận của nó được thăm rồi thì ta sẽ quay ngược lên đỉnh gần đây vừa được thăm (đây là thuật toán quay lui). Phép tìm kiếm sẽ kết thúc khi không còn một nút nào chưa được thăm mà vẫn có thể tới được một nút đã được thăm.
V1
V2
V3
V5
V6
V4
V7
V8
Ví dụ:
Thứ tự duyệt như sau:
V1, V2, V4, V8, V5, V7, V3, V6
Từ đó ta có thể xây dựng thuật toán của phép duyệt này là như sau:
	void Tim_Kiem_Sau(V)
	1.	Visited[V]=1;
	cout << V;
	2.	For 
	if Visited[W]==0 	
	Tim_Kiem_Sau(W);
	return;
Chương trình chính:
	For (i=1;i<=n;i++) // n là số nút tối đa của mảng 
	Visited[i]=0;
	Tim_Kiem_Sau(1); // Giả sử đồ thị có đỉnh 1 
	=>	Kết quả in ra sẽ là những đỉnh liên thông với đỉnh 1.
Lưu ý:
Trong thủ tục tìm kiếm sâu, ở bước 1 ta có thể bổ sung thêm lệnh chứng tỏ nút V được thăm (ví dụ, lệnh cout << V). Lúc này ở chương trình chính chỉ cần thực hiện các lệnh:
Khởi tạo các phần tử của mảng Visited bằng 0.
Gọi thủ tục Tim_Kiem_Sau(1).
Chương trình này chỉ duyệt qua tất cả các nút liên thông với nút 1 mà thôi.
Phép duyệt cây theo thủ tục tìm kiếm theo chiều sâu tức là duyệt theo thứ tự trước (đối với cây).
§ Bài tập:
	Viết chương trình bằng C++ thể hiện việc tìm kiếm sâu trong một đồ thị bằng 2 cách biểu diễn đồ thị (ma trận kề, danh sách kề).
7.3.2.Tìm kiếm theo chiều rộng:
	Phép tìm kiếm theo chiều rộng cũng xuất phát từ một đỉnh V nào đó nhưng khác với phép tìm kiếm theo chiều sâu ở chỗ: các đỉnh là lân cận của V mà chưa được thăm sẽ được thăm kế tiếp nhau rồi mới đến các đỉnh chưa được thăm là lân cận lần lượt của các đỉnh này...
	Ví dụ:
V1
V2
V3
V5
V6
V4
V7
V8
Thứ tự duyệt như sau:
V1, V2, V3, V4, V5, V6, V7, V8
Thuật toán tìm kiếm theo chiều rộng sẽ dựa vào nguyên tắc hàng đợi (Queue):
	void Tim_Kiem_Rong(V)
	1.	Visited[V]=1; 
	2.	
	Insert_Queue(Q, V); // cout << V; 
	3.	do 
 {
	Delete_Queue(Q, V);
	For 
	if (Visited[W]==0) 
	{
	Insert_Queue(Q, W);
	Visited[W]=1; // cout << W; 
	}
 }
while ;
	return;
Nhận xét:
Tìm kiếm theo chiều rộng sử dụng cấu trúc hàng đợi (Queue). Còn tìm kiếm theo chiều sâu sử dụng Stack (đệ quy).
Cả 2 thuật toán này đều có độ phức tạp tính toán O(n2).
§ Bài tập:
	Viết chương trình bằng C++ thể hiện việc tìm kiếm theo chiều rộng bằng 2 cách biểu diễn đồ thị.
7.4. Cây khung và cây khung với giá cực tiểu:
	Định nghĩa: Khi một đồ thị G(V, E) liên thông thì một phép tìm kiếm theo chiều sâu hay chiều rộng xuất phát từ một đỉnh nào đó sẽ cho phép thăm được mọi đỉnh của đồ thị. Trong trường hợp này, các cung của E sẽ được phân thành 2 tập:
Tập T bao gồm tất cả các cung được dùng tới hoặc được duyệt qua trong phép tìm kiếm.
Tập B bao gồm các cung còn lại.
	Lúc này, tất cả các cung trong tập T cùng với các đỉnh tương ứng tạo thành một cây khung.
Ví dụ: Cây khung T ứng với ví dụ trong tìm kiếm theo chiều rộng như sau:
1
2
3
4
5
6
7
8
	Cây khung T ứng với ví dụ trong tìm kiếm theo chiều sâu như sau:
8
1
2
3
4
5
6
7
Nhận xét:
Một cây khung T cho ta một đồ thị liên thông nhưng không tồn tại chu trình nào bên trong đồ thị này.
Khi ta bổ sung thêm một cung bất kỳ vào một cây khung thì sẽ xuất hiện một chu trình.
Đồ thị có n đỉnh thì cây khung có n-1 cung.
Ứng dụng (Xác định cây khung với giá cực tiểu):
	Xét bài toán sau:
	Giả sử cho 1 đồ thị liên thông có trọng số, vấn đề được đặt ra: Xác định cây khung với giá cực tiểu (cây khung mà tổng các trọng số trên cây khung đó là nhỏ nhất so với các cây khung khác). 
Giải quyết: Ta có thể sử dụng thuật toán của Kruscal.
Ý tưởng:
Các cung được xét để đưa vào T dựa vào thứ tự không giảm của trọng số tương ứng của chúng. Một cung được đưa vào T nếu nó không tạo nên chu trình với các cung đã có ở trong T.
2
5
1
4
3
5
7
4
2
10
2
5
1
4
3
2
5
Ở đây, nếu đồ thị có n đỉnh thì chỉ cần bổ sung n-1 cung.
Thuật toán:
	void	Kruscal(G)
T= Æ; 	//T là tập chứa các cung
while (½T½<n-1) 
	{
	;
	;
	if ( )
	T = T U {(V, W)} //Bổ sung cung (V, W) vào T
 }
	return;
CHƯƠNG 8: SẮP XẾP
8.1. Đặt vấn đề:
	Sắp xếp là quá trình bố trí lại các phần tử của một tập đối tượng nào đó theo một thứ tự nhất định. Yêu cầu về sắp xếp thường xuyên xuất hiện trong tin học nhằm giúp quản lý dữ liệu được dễ dàng.
	Các thuật toán sắp xếp được phân chia thành 2 nhóm chính:
+	Sắp xếp trong: Toàn bộ dữ liệu sắp xếp được đưa vào bộ nhớ trong. do đó dữ liệu không nhiều lắm nhưng ngược lại thời gian sắp xếp nhanh.
+	Sắp xếp ngoài: Một phần dữ liệu cần sắp xếp được đưa vào bộ nhớ trong, phần còn lại được lưu trữ ở bộ nhớ ngoài. do đó có thể sắp xếp dữ liệu với khối lượng lớn nhưng tiến trình sắp xếp sẽ chậm hơn.
	Nói chung, dữ liệu có thể xuất hiện dưới nhiều dạng khác nhau. Ở đây ta quy ước tập đối tượng được sắp xếp là tập các bản ghi. Tuy nhiên, khi sắp xếp, thường người ta chỉ quan tâm đến giá trị của 1 trường nào đó (gọi là trường khoá) và việc sắp xếp được tiến hành dựa vào trường khoá này. Để đơn giản, ở đây ta xem 1 bản ghi chỉ chứa 1 trường dữ liệu có kiểu số và thứ tự sắp xếp theo chiều tăng.
8.2. Một số phương pháp sắp xếp đơn giản:
8.2.1. Sắp xếp kiểu lựa chọn:
Nguyên tắc:
Tại mỗi bước i ta chọn trong dãy ai+1, ..., an các phần tử lớn hơn ai, sau đó thực hiện hoán đổi vị trí của chúng với ai (sao cho ai có giá trị nhỏ nhất (i =1..n).
Thuật toán:
void Selection_Sort(a, n)
	For (i=1; i<=n-1; i++)
	For (j=i+1; j<=n; j++)
	if (a[i]>a[j]) 
	;
	return;
8.2.2. Sắp xếp kiểu chèn:
Nguyên tắc: Tương tự như khi sắp bài tiến lên. Chia làm 2 trường hợp:
Kết hợp việc sắp xếp với việc nhập dữ liệu:
	void SapXep(a, n)
	For (i=1; i<=n; i++)
	{
	cin >> a[i];
	Chen(a[i]);
	}
	return;
	Trong đó, ta có thủ tục Chen(X) như sau:
 void	Chen(X)
	if (i>1) 
	{
	j=1;
	while ((a[j]<=X) && (j<=i-1)) j=j+1;
	if (j<i) 
	{
	For (k=i;k>=j+1;k--)
	a[k]=a[k-1];
	a[j]=X;
	}
	}
	return;
Sắp xếp từ mảng đã có dữ liệu:
	void Insert_Sort(a, n)
	Const VoCuc = 106;
a[0]= -VoCuc;
For (i=1;i<n;i++)	
	{
	X=a[i]; j=i-1;
	while (x<a[j]) 
	{
	a[j+1]=a[j]; j=j-1;
	}
	a[j+1]=X;
	}
	return;
Lưu ý: Ý tưởng của thuật toán này có thể thực hiện dễ dàng hơn nếu sử dụng danh sách móc nối để lưu dãy số này.
8.2.3. Sắp xếp kiểu nổi bọt:
	void Bubble_Sort(a, n)
	For (i=1; i<n; i++)
	For (j=n; j>=i+1; j--)
	if (a[j]<a[j-1]) 
	;
	return;
Nhận xét: Cả 3 thuật toán trên đều có độ phức tạp tính toán là O(n2).
8.3. Sắp xếp kiểu phân đoạn (Sắp xếp nhanh - quick sort):
Nguyên tắc:
	Chọn ngẫu nhiên một phần tử X của dãy (chẳng hạn phần tử đầu tiên) và cố gắng phân chia dãy này thành 3 dãy con liên tiếp nhau:
	+	Dãy 1: Gồm những phần tử nhỏ hơn X.
	+	Dãy 2: Gồm những phần tử bằng X.
	+	Dãy 3: Gồm những phần tử lớn hơn X.
	Sau đó áp dụng lại thuật toán này cho dãy con thứ nhất và dãy con thứ ba (dãy con này có số phần tử lớn hơn 1).
	void Quick_Sort(a, Be, Lon)
	if (Be<Lon) 
	{	i=Be+1; j=Lon; X=a[Be];
do
 {	while ((a[i]<X) && (i<=Lon)) i=i+1;
	if (i>Lon) 
	{	;
	Quick_Sort(a, Be, Lon-1); return;
	}
	while (a[j]>X) j=j-1;
	if (j=Be )	
	{	Quick_Sort(a, Be+1, Lon);
	return;
	}
	if (i<=j)	
	{	;
	i=i+1;
	j=j-1;
	}
	}
	while (i<=j);
	;
if (Be<j-1) Quick_Sort (a, Be, j-1);
	if (Lon>i) Quick_Sort (a, i, Lon);
	}
	return;
Lưu ý: Tại chương trình chính, để sắp xếp mảng a từ phần tử thứ nhất đến phần tử thứ n thì ta gọi thủ tục sắp xếp như sau: Quick_Sort (a, 1, n);
Người ta chứng minh được trong trường hợp xấu nhất, thuật toán này có độ phức tạp là O(nlog2n) (xem sách). Do đó, với n khá lớn thuật toán Quick sort tỏ ra hữu hiệu hơn các thuật toán đơn giản.
8.4. Sắp xếp kiểu vun đống (Heap sort):
Nguyên tắc: Với phương pháp sắp xếp này dãy số được lưu ở trong mảng sẽ được coi như là cấu trúc của cây nhị phân hoàn chỉnh.
Đầu tiên, cây nhị phân biểu diễn sẽ được sắp xếp để tạo thành một đống (heap). Ta gọi đó là giai đoạn tạo đống (đống là cây nhị phân hoàn chỉnh mà mỗi nút được gán một giá trị sao cho nút cha luôn có giá trị lớn hơn hoặc bằng nút con). Bấy giờ giá trị ở gốc sẽ là các khoá lớn nhất (gọi là khóa trội).
Sau đó, các động tác sau đây sẽ được lặp đi lặp lại nhiều lần cho đến khi cây chỉ còn lại một lá: Đưa khóa trội về vị trí thực của nó (bằng cách đổi chỗ cho khóa ở cuối đống đang xét), sau đó vun lại đống đối với cây gồm các khóa còn lại.
Lưu ý:
	Vấn đề được đặt ra là: cần xây dựng một thuật toán để điều chỉnh một cây thành một đống với giả thiết rằng cây con trái và cây con phải của gốc đã là đống.
	Một cách tổng quát, ta có thuật toán để điều chỉnh lại cây con tại i, biết rằng cây con trái (2i) và cây con phải (2i+1) đã là đống (giả sử đống a có n phần tử):
	void DieuChinh(a, i, n)
Key=a[i];
	j=2*i; // j: chỉ số chỉ tới cây con trái của i 
while (j<=n)
	{
	if ((j<n) && (a[j]<a[j+1])) 
	j=j+1;	/*Chọn j ở vị trí con của i nhưng
	 có giá trị lớn nhất */
	if (Key>=a[j]) 	/*Cần thiết cho lần thực
	 hiện sau của vòng lặp*/
	{
	a[j/2]=Key;
	return;
	}
	a[j/2]=a[j];
	j=2*j;
	}
a[j/2]=Key;
	return;
Lúc này thủ tục sắp xếp theo kiểu vun đống như sau:
	void Heap_Sort(a, n);
//Giai đoạn 1
	For (i=n/2;i>=1;i--)
	DieuChinh(a, i, n);	/*1 lá có thể xem như là đống 
	 cho nên thủ tục này thực hiện
	 từ trên lá trở lên*/
//Giai đoạn 2
	For (i=n-1;i>=1;i--)
	{
	;
	Dieuchinh(a, 1, i);
	}
	return;	
Lưu ý: Người ta cũng chứng minh được rằng độ phức tạp của thuật toán này là O(nlog2n).
8.5. Sắp xếp kiểu trộn (Merge sort):
-	Phép hoà nhập 2 đường. Xét bài toán: 
	Giả sử ta có mảng X chia làm 2 phần đã được sắp xếp: (Xb, Xb+1,....,Xm) và (Xm+1, Xm+2,....,Xn). Viết thuật toán tạo ra mảng Z có chỉ số từ b tới n (Zb, Zb+1,....,Zn) được sắp xếp.
	void Tron(X, b, m, n, Z);
i=b; j=m+1; k=b;
while ((i<=m) && (j<=n))
	{
	if (X[i]<=X[j] ) 	
	{
	Z[k]=X[i]; i=i+1;
	}
	else
	{
	Z[k]=X[j]; j=j+1;
	}
	k=k+1;
	}
	3.	if i>m (Z[k], ..., Z[n])=(X[j], ..., X[n]);
	else (Z[k], ..., Z[n])=(X[i], ..., X[m]);
	return;
-	Sắp xếp kiểu hòa nhập 2 đường trực tiếp: Sau đây là thủ tục thực hiện một bước sắp xếp kiểu trộn bằng cách trộn từng cặp kế cận nhau có độ dài là L từ mảng X sang mảng Y, với n là số phần tử ở trong X.
	void Chuyen(X, Y, n, L)
i=1;
while (i<=n-2*L+1)
	{
	Tron(X, i, i+L-1, i+2*L-1, Y); // i+2*L-1 <= n 
	i=i+2*L;
	}
{Trộn phần còn dư với phần trước}
	if (i+L-1>=n) (Y[i], ..., Y[n])=(X[i], ..., X[n])
	else Tron(X, i, i+L-1, n, Y);
	return;	
=> Từ đây ta có thể suy ra thủ tục sắp xếp theo kiểu trộn như sau:
	void Merge_Sort(X, Y, n)
L=1;
while (L<n)
	{
	Chuyen(X, Y, n, L);
	L=L*2;
	X=Y;
	}
	return;
Lưu ý:
Người ta chứng minh được rằng độ phức tạp của thuật toán này là O(nlog2n). Tuy nhiên, do phải tạo ra mảng Y nên phương pháp này tốn bộ nhớ trong hơn so với 2 thuật toán trên.
Thuật toán này thường được áp dụng cho việc sắp xếp ngoài (có kết hợp với file).
CHƯƠNG 9: TÌM KIẾM
9.1. Bài toán tìm kiếm:
	Tìm kiếm là một yêu cầu rất thường xuyên trong đời sống hàng ngày cũng như trong tin học. Để đơn giản ta xét bài toán tìm kiếm như sau:
	Cho một dãy số gồm các phần tử a1, a2, ..., an. Cho biết trong dãy này có phần tử nào có giá trị bằng X (cho trước) hay không?
9.2. Tìm kiếm tuần tự:
	Thuật toán tìm kiếm tuần tự có sử dụng một biến logic, biểu thị một phần tử có tồn tại trong dãy cần tìm hay không. Ở đây ta cũng có thể giải quyết theo cách khác:
	int TimKiemTT(a, n, X)
i=1; a[n+1]=X;
while (a[i]!=X) i=i+1;
	if (i==(n+1)) return 0
	else return i;
=> Hàm này sẽ trả về giá trị là một chỉ số i nào đó trong dãy nếu tìm thấy, ngược lại hàm sẽ trả về giá trị 0.
Lưu ý: Thuật toán này có độ phức tạp là O(n).
9.3. Tìm kiếm nhị phân:
	Với giả thiết ban đầu dãy đã được sắp theo thứ tự tăng dần. Thuật toán tìm kiếm nhị phân bằng đệ quy ta đã biết trong phần đệ quy. Tuy nhiên ta có thể khử đệ quy thuật toán này như sau:
	int TKNP(a, n, X);
Be=1; Lon=n;
while (Be<=Lon) 
	{
	Giua=(Be+Lon)/ 2;
	if (a[Giua]==X) return Giua;
	if (a[Giua]<X) Be=Giua+1;
	else Lon=Giua-1;
	}
return 0;
Lưu ý: Thuật toán này có độ phức tạp là O(log2n).
9.4. Cây nhị phân tìm kiếm:
	Cây nhị phân tìm kiếm là cây được sắp xếp mà ta đã bàn đến.
³N
N
<N
	Bài toán: Giả sử dãy số trên đã được chuyển vào cây nhị phân tìm kiếm mà nút gốc được trỏ bởi T. Vấn đề đặt ra: Viết một hàm CNPTK(T, X) trả về giá trị NULL nếu không có nút nào mà trường Info có giá trị bằng X, ngược lại cho kết quả là con trỏ trỏ vào phần tử đó.
	Nut * CNPTK(T, X)
q=T;
while (q!=NULL)
	{
	if (q->Info == X) break;
	if (q->Info Right;
	else q=q->Left;
	} 
return q;
Lưu ý: Khi đã có sẵn cây nhị phân tìm kiếm, thuật toán bổ sung một nút vào cây này thì ta đã xét. Nếu cần loại bỏ một nút trong cây nhị phân tìm kiếm, ta xét các trường hợp sau:
	 : Chỉ nút cần xoá	 : Cây con
B
A
Trước khi xóa
B
A
Sau khi xóa
i)	Xoá nút lá:
ii)	Xoá nút nửa lá:
B
A
C
B
A
C
B
A
Sau khi xóa
C
hoặc
Trước khi xóa
-	Xoá 1 nút không là lá, không là nửa lá:
A
B
D
C
E
F
Q, P
T
S
Trước khi xóa
A
B
D
C
F
Sau khi xóa
Thuật toán: Giả sử ta đã có hàm bố Bo(p):
	void	XoaNut(Q)
//Xử lý trong trường hợp nút lá và nửa lá
	p=Q;
	if (p->Left=NULL) 
	{
	R=Bo(Q); R->Left=p->Right;
	Free(p); return;
	}
	if (p->Right==NULL) 
	{
	R=Bo(Q); R->Left=p->Left;
	Free(p); return;
	}
	//Trường hợp Q là con phải của bố Q thì xử lý tương tự
T=p->Left;
	if (T->Right==NULL) 
	{
	R=Bo(Q);	 R->Left=T;
	T->Right=p->Right;	
	Free(p); return;
	}
	S=T->Right;
	while (S->Right!=NULL)	
	{
	T=S; S=S->Right;
	}
	S->Right=p->Right; T->Right=S->Left;
	S->Left=p->Left; R=Bo(Q); R->Left=S;
	Free(p);
return;
TÀI LIỆU THAM KHẢO
[1]	Cấu trúc dữ liệu và thuật toán (Đỗ Xuân Lôi)
[2]	Lập trình nâng cao bằng PASCAL với các cấu trúc dữ liệu (Larry Hoff - Lê Minh Trung dịch) - Tập 2
[3]	Cẩm nang thuật toán ( Robert Sedgewick) - 2 tập
[4]	The Art of Computer Programming (donald Knuth)
[5]	Algorithm + Data Structure = Program (Niklaus Wirth)
[6]	Cấu trúc dữ liệu và thuật toán, Đinh Mạnh Tường, Nhà Xuất bản ĐHQG Hà Nội, 2008
[7]	T. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms, Cambridge, MIT Press, 2nd Edition, 2005