Bài giảng Cấu trúc dữ liệu và giải thuật - Phan Thị Hà

CẤU TRÚC DỮ LIỆU VÀ GIẢI 
THUẬT 
TS.Phan Thị Hà 
Học Viện CNBCVT 
Phan Thị Hà 
BT kiểm tra kiến thức LT 
 Viết chƣơng trình tính tổng các số nguyên 
tố của 1 ma trận các số nguyên. Biết rằng 
ct gồm có ít nhất các hàm sau: 
 Void Nhập( int **a, int n); nhập ma trận 
 Voi nhap( int a[][10], int n) 
 int ngt( int so): Xác định so có phải ng tố k? 
 Int Tong( int ** a, int n): Tính tổng các số 
nguyên tố theo yêu cầu đầu bài 
 Int Tong( int a[][10], int n) 
 Int Main() 
Phan Thị Hà 
Danh sách nhóm trƣởng 
 Nhóm 4: Bùi Thành Lộc 01663177081 mrkasa1201@gmail.com 
 Phan Văn Quang 0988806405 buinhulac110i@gmail.com 
 Nhóm 5: Trần Quang Hoàn 0919963616 Tranhoanhq@gmail.com 
 Đặng thị Ngọc Trâm0915365653 ngoctramnd2013@gmail.com 
 Nhóm 7: Phan Văn Trung 0943241608 trungphanptit@gmail.com 
 Phạm Quang Sơn 0964535086 quángon137@gmail.com 
 Nhóm 8: Bùi Văn Công 0978776096 conghcl2010@gmail.com 
 Nguyễn Mạnh Toàn 01677535717 
nguyenmanhtoan1501@gmail.com 
 Nhóm 9: Nghuyễn Thanh Tuấn 01685155229 
thanh.tuan.1995.0411@gmail.com.vn 
 Đào Bá Huỳnh 0974021385 boy.sl.pro.1994@gmail.com 
 Nhóm 10: Nguyễn Văn Tiến 0966626212 nvtien94@gmail.com 
 Trần Lƣơng Bằng 0975453108 
Phan Thị Hà 
Nội dung 
 Chƣơng 1: Phân tích – Thiết kế giải thuật 
 Chƣơng 2: Đệ Quy 
 Chƣơng 3: Mảng và Danh sách liên kết 
 Chƣơng 4: Ngăn xếp và Hàng đợi 
 Chƣơng 5: Cấu trúc dữ liệu kiểu cây 
 Chƣơng 6: Đồ thị 
 Chƣơng 7: Sắp xếp và tìm kiếm 
Phan Thị Hà 
CHƢƠNG 1: 
PHÂN TÍCH – THIẾT KẾ GIẢI THUẬT 
Phan Thị Hà 
Giải thuật là gì? 
 Giải thuật – hay thuật toán 
 Thuật toán là một chuỗi hữu hạn các lệnh. Mỗi lệnh có một ngữ 
nghĩa rõ ràng và có thể được thực hiện với một lượng hữu hạn tài 
nguyên trong một khoảng hữu hạn thời gian. 
 Tính chất của thuật toán: 
 Xác định rõ đầu vào, đầu ra 
 Hữu hạn 
 Chính xác 
 Tổng quát 
Phan Thị Hà 
Ngôn ngữ diễn đạt giải thuật 
 Ngôn ngữ tự nhiện 
 Sơ đồ khối 
 Giả mã 
 Vd 
Phan Thị Hà 
Phân tích thuật toán 
 Nhiệm vụ: Phân tích – tính toán thời gian thực 
hiện của chƣơng trình 
Phan Thị Hà 
Phân tích thuật toán 
 Định nghĩa. Cho 2 hàm f và g là các hàm thực không 
âm có miền xác định trong tập số tự nhiên. Ta viết 
f(n)=O(g(n)) (đọc là f(n) là O lớn của g(n)) nếu tồn tại 
hằng số C>0 và số tự nhiên n0 sao cho f(n)<Cg(n), với 
mọi n>n0 . 
 Nếu một thuật toán có thời gian thực hiện T(n)=O(g(n)) ta 
nói rằng thuật toán có thời gian thực hiện cấp cao nhất là 
g(n) 
 Đôi khi ta cũng nói đơn giản là thuật toán có thời gian thực hiện cấp 
g(n) hay độ phức tạp tính toán của thuật toán là g(n). 
 Ngƣời ta cũng thƣờng nói đến độ phức tạp tính toán của thuật toán 
trong trƣờng hợp xấu nhất, trƣờng hợp tốt nhất, độ phức tạp trung bình. 
Phan Thị Hà 
Các quy tắc để đánh giá thời gian thực hiện 
thuật toán 
 Nếu T1(n) = O(f(n)), T2(n) = O(g(n)), khi 
đó 
 Qui tắc tổng: T1(n)+ T2(n) = 
O(max(f(n),g(n))) 
 Quy tắc nhân: T1(n)T2(n) = O(f(n)g(n)) 
Phan Thị Hà 
Một số quy tắc chung: 
 Thời gian thực hiện các lệnh gán, đọc, ghi .v.v, luôn là O(1). 
 Thời gian thực hiện chuỗi tuần tự các lệnh đƣợc xác định theo quy 
tắc cộng cấp độ tăng. 
 Có nghĩa là thời gian thực hiện của cả nhóm lệnh tuần tự được 
tính là thời gian thực hiện của lệnh lớn nhất. 
 Thời gian thực hiện lệnh rẽ nhánh (If) đƣợc tính bằng thời gian 
thực hiện các lệnh khi điều kiện kiểm tra đƣợc thoả mãn và thời 
gian thực hiện việc kiểm tra điều kiện. 
 Trong đó thời gian thực hiện việc kiểm tra điều kiện luôn là 
O(1). 
 Thời gian thực hiện 1 vòng lặp đƣợc tính là tổng thời gian thực 
hiện các lệnh ở thân vòng lặp qua tất cả các bƣớc lặp và thời gian 
để kiểm tra điều kiện dừng. 
 Thời gian thực hiện này thường được tính theo quy tắc nhân 
cấp độ tăng số lần thực hiện bước lặp và thời gian thực hiện 
các lệnh ở thân vòng lặp. 
Phan Thị Hà 
Ví dụ 1 
 Giả sử ta cần đánh giá độ phức tạp tính toán của các câu lệnh sau 
đây: 
 (a) for(i=0;i< n;i++) 
 {x=0; 
 for(j=0;j<n;j++) x++; 
 }; 
 (b) for(i=0;i< n;i++) y++; 
 Câu lệnh x++ đƣợc đánh giá là O(1), do đó câu lệnh (a) có thời gian 
thực hiện là n(n+1) do đó đƣợc đánh giá O(n2+n)) = n2 , câu lệnh (b) 
đƣợc đánh giá là O(n). Do đó thời gian thực hiện cả 2 thuật toán trên 
đƣợc đánh giá là: 
 O(n(n+1)+n) = O(max(n(n+1),n)=O(n(n+1)) = n2 . 
Phan Thị Hà 
 Thuật toán nổi bọt nhƣ sau : 
 void buble (int a[n]){ 
 int i, j, temp; 
 1. for (i = 0; i < n-1; i++) 
 2. for (j = n-1; j>= i+1; j--) 
 3. if (a[j-1] > a[j]{ 
 // Đổi chỗ cho a[j] và a[j-1] 
 4. temp = a[j-1]; 
 5. a[j-1] = a[j]; 
 6. a[j] = temp; 
 } 
 } 
 Kích thƣớc dữ liệu vào chính là số phần tử đƣợc sắp, n. Mỗi lệnh gán sẽ có thời gian thực hiện 
cố định, không phụ thuộc vào n, do vậy, các lệnh 4, 5, 6 sẽ có thời gian thực hiện là O(1), tức 
thời gian thực hiện là hằng số. Theo quy tắc cộng cấp độ tăng thì tổng thời gian thực hiện cả 3 
lệnh là O(max(1, 1, 1)) = O(1). 
 If sẽ có thời gian thực hiện là O(1). 
 Vòng lặp j. mỗi bƣớc lặp có thời gian thực hiện là O(1). Số bƣớc lặp là n-i, do đó theo quy tắc 
nhân cấp độ tăng thì tổng thời gian thực hiện của vòng lặp này là O((n-i)x1) = O(n-i). 
 Vòng lặp i, đƣợc thực hiện (n-1) lần: O(n-1) 
 Do đó, tổng thời gian thực hiện của chƣơng trình là: 
 ∑ (n-i) = n(n-1)/2 = n2/2- n/2 = O(n2) 
Phan Thị Hà 
CHƢƠNG 2: ĐỆ QUY 
Phan Thị Hà 
 Định nghĩa đệ qui 
 Hàm trình đệ qui 
 Các ƣu điểm của hàm đệ qui 
 Một số thuật toán đệ qui 
Phan Thị Hà 
Đệ quy là gì(PPđịnh nghĩa 
bằngĐQ) 
 Khái niệm 
 Một đối tƣợng đƣợc gọi là đệ qui nếu nó hoặc một phần của nó 
đƣợc định nghĩa thông qua khái niệm về chính nó. 
 Ví dụ 
 Định nghĩa số tự nhiên: 
 0 là số tự nhiên. 
 Nếu k là số tự nhiên thì k+1 cũng là số tự nhiên. 
 Định nghĩa hàm giai thừa, n!. 
 Khi n=0, định nghĩa 0!=1 
 Khi n>0, định nghĩa n!=(n-1)! x n 
Như vậy, khi n=1, ta có 1!=0!x1 = 1x1=1. Khi n=2, ta có 
2!=1!x2=1x2=2, v.v. 
Phan Thị Hà 
Giải thuật đệ qui 
 Nếu lời giải của bài toán P đƣợc thực hiện 
bằng lời giải của bài toán P‟ giống nhƣ P 
thì lời giải này đƣợc gọi là lời giải đệ qui. 
Giải thuật tƣơng ứng với lời giải bài toán P 
đƣợc gọi là giải thuật đệ qui. 
Phan Thị Hà 
Hàm đệ qui 
 Hàm này có thể gọi chính nó nhƣng nhỏ hơn 
Khi hàm gọi chính nó, mục đích là để giải quyết 1 vấn đề 
tƣơng tự, nhƣng nhỏ hơn.Vấn đề nhỏ hơn này, cho tới 1 
lúc nào đó, sẽ đơn giản tới mức hàm có thể tự giải quyết 
đƣợc mà không cần gọi tới chính nó nữa. 
Phan Thị Hà 
Quá trình hoạt động của giải thuật 
ĐQ 
 Bƣớc phân tích 
 Bƣớc thay thế ngƣợc lại 
VD:tính f(n)= n! 
+f(n)=n*f(n-1) 
 . 
 f(1)=1*f(0) 
 f(0)=0!=1 
+f(0)=1 
 f(1)=1*f(0) 
. 
 f(n)=n*f(n-1) Phan Thị Hà 
Đặc điểm của hàm đệ qui 
 Chỉ ra trƣờng hợp dừng đệ quy 
 Chỉ ra việc đệ quy 
Phan Thị Hà 
Khi nào sử dụng đệ qui 
 Vấn đề cần xử lý phải đƣợc giải quyết có 
đặc điểm đệ quy 
 Ngôn ngữ dùng để viết chƣơng trình phải 
hỗ trợ đệ qui. Để có thể viết chƣơng trình 
đệ qui chỉ cần sử dụng ngôn ngữ lập trình 
có hỗ trợ hàm hoặc thủ tục, nhờ đó một thủ 
tục hoặc hàm có thể có lời gọi đến chính 
thủ tục hoặc hàm đó 
Phan Thị Hà 
Một số thuật toán đệ qui 
 Thuật toán cột cờ ( sách) 
 Thuật toán quay lui 
Thuật toán sinh xâu ( hoặc sinh hoán vị) 
Mã đi tuần 
 Bài toán 8 quân hậu (sách) 
Phan Thị Hà 
Bài toán cột cờ 
Phan Thị Hà 
Bài toán cột cờ 
Phan Thị Hà 
Phân tích bài toán CC 
 T/C Chia để trị: Chuyển hàm với dl lớn (bài 
toán lớn) thành hàm với dl nhỏ hơn (bài 
toán nhỏ hơn),., cứ tiếp tục nhƣ thế cho 
đến khi gặp ĐK dừng 
 Chỉ ra việc đệ quy: Bài toán chuyển n cọc đã đƣợc 
chuyển về bài toán đơn giản hơn là chuyển n-1 cọc. 
 Điểm dừng của thuật toán đệ qui là khi n=1 và ta 
chuyển thẳng cọc này từ cọc ban đầu sang cọc đích. 
Phan Thị Hà 
Thiết kế một số giải thuật đệ quy 
 Giải thuật đệ quy CHIA ĐỂ TRỊ - Bài toán tháp Hà 
Nội 
void chuyen(int n, char a, char c){ 
printf(„Chuyen dia thu %d tu coc %c sang coc %c \n”,n,a,c); 
 return; 
} 
void thaphanoi(int n, char a, char c, char b){ 
 if (n==1) chuyen(1, a, c); 
 else{ 
 thaphanoi(n-1, a, b, c); 
 chuyen(n, a, c); 
 thaphanoi(n-1, b, c,a); 
 } 
 return; 
} 
Phan Thị Hà 
Phan Thị Hà 
Thuật toán quay lui 
 Xây dựng dần các thành phần của cấu hình bằng 
cách thử tất cả các khả năng. Giả sử cần phải tìm 
một cấu hình của bài toán x = (x1, x2, . ., xn) mà i-
1 thành phần x1, x2, . ., xi-1 đã đƣợc xác định. 
 Bây giờ ta xác định thành phần thứ i của cấu hình 
bằng cách duyệt tất cả các khả năng có thể có và 
đánh số các khả năng từ 1 . .ni. 
 Với mỗi khả năng j, kiểm tra xem j có chấp nhận 
đƣợc hay không. Khi đó có thể xảy ra hai trƣờng 
hợp: 
Phan Thị Hà 
 Nếu chấp nhận j thì xác định xi theo j, nếu 
i=n thì ta đƣợc một cấu hình cần tìm, ngƣợc 
lại xác định tiếp thành phần xi+1. 
 Nếu thử tất cả các khả năng mà không có 
khả năng nào đƣợc chấp nhận thì quay lại 
bƣớc trƣớc đó để xác định lại xi-1. 
Phan Thị Hà 
Phân tích đặc điểm của bài toán 
quay lui 
 Toàn bộ vấn đề đƣợc thực hiện dần từng 
bƣớc.Tại mỗi bƣớc có ghi lại kết quả để 
sau này có thể quay lại và hủy kết quả đó 
nếu phát hiện ra rằng hƣớng giải quyết theo 
bƣớc đó đi vào ngõ cụt và không đem lại 
giải pháp tổng thể cho vấn đề. 
 =>Do đó, thuật toán đƣợc gọi là thuật toán quay lui 
 Đệ quy: Bƣớc thứ sau làm giống hệt bƣớc trƣớc, 
nhƣng dl khác 
 Điều kiện dừng: Sau khi duyệt tất cả các khả nămg có 
thể có của dữ liệu ở mỗi bƣớc 
 Quay lui, nếu hƣớng giải quyết vào ngõ cụt (xóa vết 
hoặc không xóa vết) 
Phan Thị Hà 
Thuật toán 
 void Try( int i ) { 
 int j; 
 for ( j = ; j < ni; j ++) { 
 if ( ) { 
 
 if (i==n) 
 ; 
 else Try(i+1); 
 } 
 } 
Phan Thị Hà 
Thuật toán sinh xâu nhị phân( sử dụng quay 
lui) 
 Void Try ( int i ) { 
 for (int j =0; j<=1; j++){ 
 X[i] = j; 
 if ( i ==n) Result(); 
 else Try (i+1); 
 } 
 } 
Phan Thị Hà 
Hoán vị 
 Void Try ( int i ) { 
 for (int j =1; j<=N; j++){ 
 if (chuaxet[j] ) { 
 X[i] = j;chuaxet[j] = 0; 
 if ( i ==N) Result(); 
 else Try (i+1); 
 Chuaxet[j] = 1; 
 } 
 } 
 } 
Phan Thị Hà 
Mã đi tuần 
 3 2 
4 1 
5 8 
 6 7 
Banco[x][y] = 0: ô (x,y) chưa được quân 
mã đi qua 
Banco[x][y] = i: ô (x,y) đã được quân mã 
đi qua tại nước thứ i. 
Bước đi kế tiếp (u,v) 
 u = x + dx[i] 
 v = y + dy[i] 
(u,v)chấp nhận được nếu: 
+Banco[u][v] = 0 - ĐK 1 để chấp nhận. 
+0 u, v < n – đk 2 để chấp nhận 
ĐK dừng : Kiểm tra xem bàn cờ còn ô 
trống không bằng cách kiểm tra xem i đã 
bằng n2 chưa và đã đi hết các nước đi 
chưa (nhiều nhất là 8) 
Danh sách 8 vị trí bước đi kế tiếp : (x+2, y-1); (x+1, y-2); (x-1, y-2); (x-2, y-1); (x-
2, y+1); (x-1, y+2); (x+1; y+2); (x+2, y+1) 
Phan Thị Hà 
Bài toán Mã đi tuần-Thuật toán quay lui 
 void ThuNuocTiepTheo; 
 { 
 Khởi tạo danh sách các nước đi kế tiếp; 
 do{ 
 Lựa chọn 1 nước đi kế tiếp từ danh sách; 
 if Chấp nhận được 
 { 
 Ghi lại nước đi; 
 if Bàn cờ còn ô trống 
 { 
 ThuNuocTiepTheo; 
 if Nước đi không thành công 
 Hủy bỏ nước đi đã lưu ở bước 
trước 
 } 
 } 
 }while (nước đi không thành công) && (vẫn còn nước đi) 
 } 
Phan Thị Hà 
 void ThuNuocTiepTheo(int i, int x, int y, int *q) 
 { 
 int k, u, v, *q1; 
 k=0; 
 do{ 
 *q1=0; 
 u=x+dx[k]; 
 v=y+dy[k]; 
 if ((0 <= u) && (u<n) && (0 <= v) && (v<n) && 
(Banco[u][v]==0)) 
 { 
 Banco[u][v]=i; 
 if (i<n*n) { 
 ThuNuocTiepTheo(i+1, u, v, q1) 
 if (*q1==0) Banco[u][v]=0; } 
 else *q1=1; 
 } 
 k=k+1; 
 }while ((*q1==0) && (k<8)); 
 *q=*q1; 
 } 
Phan Thị Hà 
int dx[8]={2,1,-1,-2,-2,-1,1,2}; 
int dy[8]={-1,-2,-2,-1,1,2,2,1}; 
int n=8; 
Có 3 chiếc cọc và một bộ n chiếc đĩa. Các 
đĩa này có kích thước khác nhau và mỗi đĩa 
đều có 1 lỗ ở giữa để có thể xuyên chúng 
vào các cọc. Ban đầu, tất cả các đĩa đều 
nằm trên 1 cọc, trong đó, đĩa nhỏ hơn bao 
giờ cùng nằm trên đĩa lớn hơn. 
Phan Thị Hà 
Thiết kế một số giải thuật đệ quy 
Bài toán 8 quân hậu 
void DatHau(int i) 
{ 
 Khởi tạo danh sách các vị trí có thể đặt quân hậu tiếp theo; 
 do{ 
 Lựa chọn vị trí đặt quân hậu tiếp theo; 
 if Vị trí đặt là an toàn 
 { 
 Đặt hậu; 
 if i<8 
 { 
 DatHau(i+1); 
 if Không thành công 
 Bỏ hậu đã đặt ra khỏi vị trí 
 } 
 } 
 }while (Không thành công) && (Vẫn còn lựa chọn) 
} 
Phan Thị Hà 
CHƢƠNG 3: 
 MẢNG VÀ DANH SÁCH LIÊN KẾT 
Phan Thị Hà 
Mảng 
 Một mảng là 1 tập hợp cố định các thành phần có cùng 1 
kiểu dữ liệu, đƣợc lƣu trữ kế tiếp nhau và có thể đƣợc 
truy cập thông qua một chỉ số. 
 Ví dụ, để truy cập tới phần tử thứ i của mảng a, ta viết a[i]. 
Mảng có thể có nhiều hơn 1 
chiều. Khi đó, số các chỉ số của 
mảng sẽ tương ứng với số chiều. 
Chẳng hạn, trong mảng 2 chiều 
a, thành phần thuộc cột i, hàng j 
được viết là a[i][j]. Mảng 2 chiều 
còn được gọi là ma trận (matrix). 
Phan Thị Hà 
Nhƣợc: 
 Kích thƣớc (số phần tử) của mảng là cố 
định 
Phan Thị Hà 
Ôn lại thao tác với mảng 
 Khai báo mảng 
 Mảng tĩnh 
 Mảng động 
 Truy nhập 1 phần tử của mảng 
Phan Thị Hà 
Ôn lại CẤP PHÁT BỘ NHỚ 
ĐỘNG 
 Cấp phát bộ nhớ động 
 = new <kiểu 
con trỏ>; 
 VD: 
 int *pa; 
 pa = new int; 
 Hoặc 
 int *pa; 
 pa = new int(12); 
 Giải phóng bộ nhớ động 
 delete ; 
VD: 
 int *pa = new int(12); 
 delete pa; 
VD: 
 int *pa = new int(12); 
 int *pb = pa; 
 *pb += 5; 
 delete pa; 
Phan Thị Hà 
 Cấp phát bộ nhớ cho mảng động một chiều 
 = new [<Độ dài 
mảng>]; 
 VD: int *A = new int[5]; 
 Giải phóng bộ nhớ của mảng động một chiều 
 delete [] ; 
 VD: 
 int *A = new int[5]; 
 delete [] A; 
Ôn lại CẤP PHÁT BỘ NHỚ ĐỘNG 
Phan Thị Hà 
Danh sách liên kết 
 Khái niệm 
 Danh sách liên kết là 1 cấu trúc dữ liệu bao gồm 1 tập các phần tử , 
trong đó mỗi phần tử là 1 phần của 1 nút có chứa một liên kết tới 
nút kế tiếp. 
 Biểu diễn 
 Đầu Cuối 
 Điểm khác biệt giữa DSLK và Mảng 
 Mảng có thể đƣợc truy cập ngẫu nhiên thông qua chỉ số, còn danh 
sách chỉ có thể truy cập tuần tự. 
 Việc bố trí, sắp đặt lại các phần tử trong 1 danh sách liên kết đơn 
giản hơn nhiều so với mảng. 
 Do bản chất động của danh sách liên kết, kích thƣớc của danh 
sách liên kết có thể linh hoạt hơn nhiều so với mảng. 
Phan Thị Hà 
Khai báo danh sách trong C,C++ 
 Đơn giản 
struct node { 
int item; 
struct node *next; 
}; 
typedef struct node *listnode; 
 Phức tạp 
struct node { 
itemstruct item; 
struct node *next; 
}; 
typedef struct node *listnode; 
Phan Thị Hà 
Các thao tác trên DSLK 
 Tập các thao tác: 
 Tạo, cấp phát, và giải phóng bộ nhớ cho 1 nút 
 Chèn một nút vào đầu danh sách 
 Chèn một nút vào cuối danh sách 
 Chèn một nút vào trước nút r trong danh sách 
 Xóa một nút ở đầu danh sách 
 Xóa một nút ở cuối danh sách 
 Xóa một nút ở trước nút r trong danh sách 
 Duyệt toàn bộ danh sách 
 Cài đặt các thao tác: SGK 
Phan Thị Hà 
Tạo, cấp phát, và giải phóng bộ 
nhớ cho 1 nút 
 listnode p; // Khai báo biến p 
 p = new (node);//cấp  ... thứ tự sau 
Gốc 
n 
T1 T2 Tk 
... 
Quá trình duyệt: 
•Thăm cây con T1 theo 
phương pháp thứ tự sau. 
•Thăm cây con T2 theo 
phương pháp thứ tự sau. 
•... 
•Thăm cây con Tk theo 
phương pháp thứ tự sau. 
•Thăm nút gốc n. 
Gốc 
1 
2 
3 
4 
5 
6 7 
8 9 
4 -> 5 -> 3 -> 2 -> 6 -> 8 
-> 9 -> 7 -> 1 
Phan Thị Hà 
Cây nhị phân 
 Khái niệm 
 Cây nhị phân là một loại cây đặc biệt mà mỗi nút của 
nó chỉ có nhiều nhất là 2 nút con. Khi đó, 2 cây con của 
mỗi nút đƣợc gọi là cây con trái và cây con phải. 
 Ví dụ 
1 
2 3 
4 5 6 
7 
Phan Thị Hà 
Cây nhị phân 
 Một số dạng cây nhị phân 
đặc biệt: 
 Cây nhị phân đầy đủ: 
 Là cây nhị phân mà mỗi nút 
không phải lá đều có đúng 2 nút 
con và các nút lá phải có cùng độ 
sâu. 
 Cây nhị phân tìm kiếm: 
 Là cây nhị phân có tính chất khóa 
của nút con bên trái bao giờ cũng 
nhỏ hơn khóa của nút cha, còn 
khóa của cây con bên phải bao 
giờ cũng lớn hơn hoặc bằng khóa 
của nút 
10 
23 31 
9 15 87 22 
20 
12 30 
8 
15 25 37 
Phan Thị Hà 
Cài đặt cây nhị phân bằng mảng 
 Đối với cây nhị phân không cân bằng, cần sử dụng cấu 
trúc sau: 
typedef struct { 
 int item; 
 int leftchild; 
 int rightchild; 
} node; 
node tree[max]; 
 Phan Thị Hà 
Cài đặt cây nhị phân sử dụng 
DSLK 
 Mỗi nút của cây nhị phân khi cài đặt bằng 
DSLK sẽ có 3 thành phần: 
 Thành phần item chứ thông tin về nút. 
 Con trỏ left trỏ đến nút con bên trái. 
 Con trỏ right trỏ đến nút con bên phải. 
Phan Thị Hà 
Cài đặt cây nhị phân sử dụng 
DSLK 
 Mã nguồn: 
struct node { 
 int item; 
 struct node *left; 
 struct node *right; 
} 
typedef struct node *treenode; 
treenode root; 
Phan Thị Hà 
Cài đặt các phƣơng pháp duyệt 
cây nhị phân 
 Duyệt thứ tự trƣớc 
void PreOrder (treenode root ) { 
if (root !=NULL) { 
 printf(“%d”, root.item); 
 PreOrder(root.left); 
 PreOrder(root.right); 
} } 
 Duyệt thứ tự giữa 
void InOrder (treenode root ) { 
if (root !=NULL) { 
 PreOrder(root.left); 
 printf(“%d”, root.item); 
 PreOrder(root.right); 
} } 
 Duyệt thứ tự sau 
void PostOrder (treenode root ) { 
if (root !=NULL) { 
 PreOrder(root.left); 
 PreOrder(root.right); 
 printf(“%d”, root.item); 
} } 
Phan Thị Hà 
CHƢƠNG 6: ĐỒ THỊ 
Phan Thị Hà 
Các khái niệm cơ bản 
 Đồ thị có hƣớng 
 Đồ thị có hƣớng G = bao gồm: 
 V là một tập hữu hạn các đỉnh. 
 E là một tập hữu hạn, có thứ tự các cặp đỉnh của V, gọi là 
các cạnh. 
 Ví dụ: 
 Đồ thị có hƣớng G1 = , với V1 và E1 đƣợc xác định nhƣ 
sau: 
 V1 = {a, b, c, d} 
 E1 = {(a, b); (a, c}; (b, d); (c, b), (d, d)} 
 Khi đó, biểu diễn hình học của đồ thị này nhƣ sau: 
b a 
d c 
Phan Thị Hà 
Các khái niệm cơ bản (tiếp) 
 Một cạnh (u, v) của đồ thị có hƣớng có thể đƣợc biểu thị 
dạng u v. Đỉnh u khi đó đƣợc gọi là đỉnh kề của v. Cạnh 
(u, v) đƣợc gọi là cạnh xuất phát từ u. Ta ký hiệu A(u) là 
tập các cạnh xuất phát từ u. 
 Bậc ngoài của 1 đỉnh là số các cạnh xuất phát từ đỉnh đó. 
Do đó, bậc ngoài của u = | A(u) |. 
 Bậc trong của 1 đỉnh là số các cạnh đi tới đỉnh đó. Do đó, 
bậc trong của v = | I(v) |. 
 Một đƣờng đi trong đồ thị có hƣớng G(V, E) là một chuỗi 
các đỉnh 
 P = {v1, v2, , vk} 
 Trong đó, vi V (i = 1.. k), và (vi, vi+1) E (i = 1.. k-1). 
 Độ dài của đƣờng đi trong trƣờng hợp này là k - 1. 
 Chu trình là một đƣờng đi mà đỉnh đầu và đỉnh cuối trùng 
nhau. Đồ thị liên thông là một đồ thị mà luôn tồn tại đƣờng 
đi giữa 2 đỉnh bất kì. Phan Thị Hà 
Các khái niệm cơ bản (tiếp) 
 Đồ thị vô hƣớng 
 Đồ thị vô hƣớng là đồ thị có các cạnh không có hƣớng. Hai nút ở 
hai đầu của cạnh có vai trò nhƣ nhau. Định nghĩa về đồ thị vô 
hƣớng nhƣ sau: 
 Đồ thị vô hƣớng G = bao gồm: 
 V là một tập hữu hạn các đỉnh. 
 E là một tập hữu hạn các cặp đỉnh phân biệt của V, gọi là 
các cạnh. 
 Ví dụ, đồ thị có hƣớng G2 = , với V2 và 
E2 đƣợc xác định nhƣ sau: 
 V2 = {a, b, c, d} 
 E2 = {(a, b); (a, c}; (b, d); (c, b) } 
b a 
d c 
Phan Thị Hà 
Các khái niệm cơ bản (tiếp) 
 Đồ thị có trọng số 
Hà Nội 
Bắc Ninh 
Thái Bình 
115km 
40km 
Ninh Bình 96km 
45km 
Phan Thị Hà 
Biểu diễn đồ thị - Ma trận kề 
Đồ thị có hướng Đồ thị vô hướng 
Đồ thị có 
trọng số 
Phan Thị Hà 
Biểu diễn đồ thị - Danh sách kề 
 Đồ thị có hƣớng 
 Đồ thị vô hƣớng 
Phan Thị Hà 
Duyệt đồ thị 
 Duyệt theo chiều sâu: 
void DeepFirstSearch(int v){ 
 Thăm đỉnh v; 
 daxet[v] = 1; 
 for mỗi đỉnh u kề với v { 
 if (daxet[u]=0 ) 
 DeepFirstSearch(v); 
 } 
} 
 Nếu có nhiều thành phần liên thông 
for( i=1; i n; i++) 
 daxet[i] = 0; 
for( i:=1;i n; i++) 
 if (daxet[i]=0) 
 DeepFirstSearch(i); 
Phan Thị Hà 
Duyệt đồ thị 
 Duyệt theo chiều rộng 
void BreadthFirstSearch(int v){ 
 queue = ; 
 Đƣa v vào hàng đợi; 
 daxet[v] = 1; 
 while (queue  ){ 
 Lấy phần tử ra khỏi hàng đợi, đƣa vào biến u; 
 Thăm đỉnh u; 
 for mỗi đỉnh w kề với u { 
 if (daxet[w]=0 ) { 
 Đƣa w vào hàng đợi; 
 daxet[w] = 1; 
 } 
} 
} 
Phan Thị Hà 
Ứng dụng duyệt đồ thị để kiểm tra 
tính liên thông 
 Ví dụ sử dụng duyệt theo chiều rộng: 
int lt=0; 
for( v=1; v n; v++) 
 daxet[v] = 0; 
for(v=1; v n; v++) 
 if (daxet[v]=0){ 
 BreadthFirstSearch(u); 
 lt++; 
 } 
if (lt ==1) printf(“Do thi lien thong!”); 
else printf(“Do thi khong lien thong, so thanh phan lien thong la %d”, 
lt); 
Phan Thị Hà 
CHƢƠNG 7 
SẮP XẾP VÀ TÌM KIẾM 
Phan Thị Hà 
Bài toán sắp xếp 
 Khái niệm 
 Sắp xếp là quá trình bố trí lại các phần tử của 1 tập hợp theo thứ 
tự nào đó. Mục đích chính của sắp xếp là làm cho thao tác tìm 
kiếm phần tử trên tập đó đƣợc dễ dàng hơn. 
 Ví dụ về tập các đối tƣợng đƣợc sắp phổ biến trong thực tế là: 
danh bạ điện thoại đƣợc sắp theo tên, các từ trong từ điển đƣợc 
sắp theo vần, sách trong thƣ viện đƣợc sắp theo mã số, theo 
tên, .v.v. 
 Các giải thuật sắp xếp đƣợc chia làm 2 loại. 
 Loại thứ nhất là các giải thuật đƣợc cài đặt đơn giản, nhƣng 
không hiệu quả (phải sử dụng nhiều thao tác). 
 Loại thứ hai là các giải thuật đƣợc cài đặt phức tạp, nhƣng hiệu 
quả hơn về mặt tốc độ (dùng ít thao tác hơn). 
 Đối với các tập dữ liệu ít phần tử, tốt nhất là nên lựa chọn loại thứ 
nhất. Đối với tập có nhiều phần tử, loại thứ hai sẽ mang lại hiệu 
quả hơn. 
Phan Thị Hà 
Sắp xếp lựa chọn 
Lựa chọn phần tử có giá trị nhỏ nhất, đổi chỗ cho phần tử đầu tiên. Tiếp 
theo, lựa chọn phần tử có giá trị nhỏ thứ nhì, đổi chỗ cho phần tử thứ 2. Quá 
trình tiếp tục cho tới khi toàn bộ dãy được sắp. 
7 bước Phan Thị Hà 
Sắp xếp lựa chọn 
void selection_sort(){ 
 int i, j, k, temp; 
 for (i = 0; i< N; i++){ 
 k = i; 
 for (j = i+1; j < N; j++){ 
 if (a[j] < a[k]) k = j; 
 } 
 temp = a[i]; a[i] =a [k]; a[k] = temp; 
 } 
} 
 Độ phức tạp trung bình của thuật toán là 
 O(N * N/2) = O(N2/2) = O(N2). 
Phan Thị Hà 
Vd: 8,1,2,5,4,3 
 i=0:k=0=>k=1: 1,8,2,5,4,3 
 i=1;k=1=>k=2: 1,2,8,5,4,3 
 i=2;k=2=>k=3: 1,2,5,8,4,3 
 k=4: 1,2,4,8,5,3 
 k=5: 1,2,3,8,5,4 
 i=3; k=3=>k=4: 1,2,3,5,8,4 
 k=5: 1,2,3,4,8,5 
 i=4;k=4=>k=5: 1,2,3,4,5,8 
 i=5;k=5; 
Phan Thị Hà 
Sắp xếp chèn 
 Phần đầu là các phần tử đã đƣợc sắp. Từ 
phần tử tiếp theo, chèn nó vào vị trí thích 
hợp tại nửa đã sắp sao cho nó vẫn đƣợc 
sắp. 
 Để chèn phần tử vào nửa đã sắp, chỉ cần 
dịch chuyển các phần tử lớn hơn nó sang 
phải 1 vị trí và đƣa phần tử này vào vị trí 
trống trong dãy. 
Phan Thị Hà 
.8 bƣớc 
Phan Thị Hà 
Sắp xếp chèn 
void insertion_sort(){ 
 int i, j, k, temp; 
 for (i = 1; i< N; i++){ 
 temp = a[i]; 
 j=i-1; 
 while ((a[j] > temp)&&(j>=0)) { 
 a[j+1]=a[j]; 
 j--; 
 } 
 a[j+1]=temp; 
 } 
} 
 Độ phức tạp trung bình của thuật toán là 
 O(N2/4) = O(N2). 
Phan Thị Hà 
Vd: 8,1,2,3,4,5 
i=1;j=0; 1,8,2,3,4,5 
i=2; temp=2;j=1; 1,2,8,3,4,5 
i=3; temp=3;j=2; 1,2,3,8,4,5 
i=4; temp=4;j=3; 1,2,3,4,8,5 
i=5; temp=5;j=4; 1,2,3,4,5,8 
Phan Thị Hà 
Sắp xếp nổi bọt 
 Duyệt nhiều lần từ cuối lên đầu dãy, tiến 
hành đổi chỗ 2 phần tử liên tiếp nếu chúng 
ngƣợc thứ tự. Đến một bƣớc nào đó, khi 
không có phép đổi chỗ nào xảy ra thì toàn 
bộ dãy đã đƣợc sắp. 
Phan Thị Hà 
 Phan Thị Hà 
 Phan Thị Hà 
Sắp xếp nổi bọt 
 Thủ tục thực hiện sắp xếp nổi bọt trong C nhƣ sau: 
void bubble_sort(){ 
 int i, j, temp, no_exchange; 
 i = 1; 
 do{ 
 no_exchange = 1; 
 for (j=n-1; j >= i; j--){ 
 if (a[j-1] > a[j]){ 
 temp=a[j-1]; 
 a[j-1]=a[j]; 
 a[j]=temp; 
 no_exchange = 0; 
 } 
 } 
 i++; 
 } until (no_exchange || (i == n-1)); 
} 
 Tổng cộng, số phép so sánh cần thực hiện là: (N-1) + (N-2) +  + 2 + 
1 = N(N-1)/2. Nhƣ vậy, độ phức tạp cũng giải thuật sắp xếp nổi bọt 
cũng là O(N2). 
Phan Thị Hà 
QUICK SORT 
 Ý tƣởng dựa trên phƣơng pháp chia để trị . 
 Giải thuật chia dãy cần sắp thành 2 phần, sau đó thực 
hiện việc sắp xếp cho mỗi phần độc lập với nhau. 
 Để thực hiện điều này, đầu tiên chọn ngẫu nhiên 1 phần 
tử nào đó của dãy làm khóa. Trong bƣớc tiếp theo, các 
phần tử nhỏ hơn khoá phải đƣợc xếp vào phía trƣớc khoá 
và các phần tử lớn hơn đƣợc xếp vào phía sau khoá. Để 
có đƣợc sự phân loại này, các phần tử sẽ đƣợc so sánh 
với khoá và hoán đổi vị trí cho nhau hoặc cho khoá nếu nó 
lớn hơn khóa mà lại nằm trƣớc hoặc nhỏ hơn khoá mà lại 
nằm sau. Khi lƣợt hoán đổi đầu tiên thực hiện xong thì dãy 
đƣợc chia thành 2 đoạn: 1 đoạn bao gồm các phần tử nhỏ 
hơn khoá, đoạn còn lại bao gồm các phần tử lớn hơn 
khoá. 
Phan Thị Hà 
 Phan Thị Hà 
 Phan Thị Hà 
QUICK SORT 
 Mã nguồn giải thuật: 
void quick(int left, int right) { 
 int i,j; 
 int x,y; 
 i=left; j=right; 
 x= a[left]; 
 do { 
 while(a[i]<x && i<right) i++; 
 while(a[j]>x && j>left) j--; 
 if(i<=j){ 
 y=a[i];a[i]=a[j];a[j]=y; 
 i++;j--; 
 } 
 }while (i<=j); 
 if (left<j) quick(left,j); 
 if (i<right) quick(i,right); 
} 
 Hàm chính: 
void quick_sort(){ 
 quick(0, n-1); 
} Phan Thị Hà 
QUICK SORT 
 Độ phức tạp tính toán: 
 Thời gian thực hiện thuật toán trong trƣờng hợp xấu 
nhất này là khoảng N2/2, có nghĩa là O(N2). 
 Trong trƣờng hợp tốt nhất, mỗi lần phân chia sẽ đƣợc 2 
nửa dãy bằng nhau, khi đó thời gian thực hiện thuật 
toán T(N) sẽ đƣợc tính là: 
 T(N) = 2T(N/2) + N 
 Khi đó, T(N) ≈ NlogN. 
 Trong trƣờng hợp trung bình, thuật toán cũng có độ 
phức tạp khoảng 2NlogN = O(NlogN). 
Phan Thị Hà 
HEAP SORT 
 Heap sort là một giải thuật đảm bảo kể cả trong trƣờng hợp xấu nhất 
thì thời gian thực hiện thuật toán cũng chỉ là O(NlogN). 
 Ý tƣởng cơ bản của giải thuật này là thực hiện sắp xếp thông qua việc 
tạo các heap, trong đó heap là 1 cây nhị phân hoàn chỉnh có tính chất 
là khóa ở nút cha bao giờ cũng lớn hơn khóa ở các nút con. 
Việc thực hiện giải thuật này đƣợc chia làm 2 giai đoạn. 
 GĐ1: Tạo heap từ dãy ban đầu. Theo định nghĩa của heap thì nút cha 
bao giờ cũng lớn hơn các nút con=> nút gốc của heap bao giờ cũng là 
phần tử lớn nhất. 
 GĐ2 : Sắp dãy dựa trên heap tạo đƣợc. Do nút gốc là nút lớn nhất 
nên nó sẽ đƣợc chuyển về vị trí cuối cùng của dãy và phần tử cuối 
cùng sẽ đƣợc thay vào gốc của heap. Khi đó ta có 1 cây mới, không 
phải heap, với số nút đƣợc bớt đi 1. Lại chuyển cây này về heap và 
lặp lại quá trình cho tới khi heap chỉ còn 1 nút. Đó chính là phần tử bé 
nhất của dãy và đƣợc đặt lên đầu. 
 Phan Thị Hà 
 Với heap ban đầu chỉ có 1 phần tử là phần tử đầu tiên của dãy, ta lần 
lƣợt lấy các phần tử tiếp theo của dãy chèn vào heap sẽ tạo đƣợc 1 
heap gồm toàn bộ n phần tử. 
Phan Thị Hà 
 Phan Thị Hà 
 Phan Thị Hà 
Chèn một phần tử x vào 1 heap đã có k phần tử, ta 
gán phần tử thứ k +1, a[k], bằng x, rồi gọi thủ tục 
upheap(k). 
 void upheap(int m){ 
 int x; 
 x=a[m]; 
 while ((a[(m-1)/2]0)){ 
 a[m]=a[(m-1)/2]; 
 m=(m-1)/2; 
 } 
 a[m]=x; 
 } 
 
 void insert_heap(int x){ 
 a[m]=x; 
 upheap(m); 
 m++; 
 } 
Phan Thị Hà 
 Ta có thủ tục downheap để chỉnh lại heap khi nút 
k không thoả mãn định nghĩa heap : 
 
 void downheap(int k){ 
 int j, x; 
 x=a[k]; 
 while (k<=(m-2)/2){ 
 j=2*k+1; 
 if (j<m-1) if (a[j]<a[j+1]) j++; 
 if (x>=a[j]) break; 
 a[k]=a[j]; k=j; 
 } 
 a[k]=x; 
 } 
Phan Thị Hà 
 Cuối cùng, thủ tục heap sort thực hiện việc sắp xếp trên heap đã tạo 
nhƣ sau: 
 int remove_node(){ 
 int temp; 
 temp=a[0]; 
 a[0]=a[m]; 
 m--; 
 downheap(0); 
 return temp; 
 } 
 void heap_sort(){ 
 int i; 
 m=0; 
 for (i=0; i<=n-1; i++) insert_heap(a[i]); 
 m=n-1; 
 for (i=n-1; i>=0; i--) a[i]=remove_node(); 
 } 
Phan Thị Hà 
MERGE SORT 
 Thủ tục tiến hành trộn 2 dãy đã sắp nhƣ sau: 
void merge(int *a, int al, int am, int ar){ 
 int i=al, j=am+1, k; 
 for (k=al; k<=ar; k++){ 
 if (i>am){ 
 c[k]=a[j++]; 
 continue; 
 } 
 if (j>ar){ 
 c[k]=a[i++]; 
 continue; 
 } 
 if (a[i]<a[j]) c[k]=a[i++]; 
 else c[k]=a[j++]; 
 } 
 for (k=al; k<=ar; k++) a[k]=c[k]; 
} 
Phan Thị Hà 
MERGE SORT 
 Cài đặt cho thuật toán merge_sort bằng đệ 
qui nhƣ sau : 
void merge_sort(int *a, int left, int right){ 
 int middle; 
 if (right<=left) return; 
 middle=(right+left)/2; 
 merge_sort(a, left, middle); 
 merge_sort(a, middle+1, right); 
 merge(a, left, middle ,right); 
} 
Phan Thị Hà 
Bài toán tìm kiếm 
 Khái niệm 
 Tìm kiếm có thể định nghĩa là việc thu thập một số 
thông tin nào đó từ một khối thông tin lớn đã đƣợc lƣu 
trữ trƣớc đó. Thông tin khi lƣu trữ thƣờng đƣợc chia 
thành các bản ghi, mỗi bản ghi có một giá trị khoá để 
phục vụ cho mục đích tìm kiếm. 
 Mục tiêu của việc tìm kiếm là tìm tất cả các bản ghi có 
giá trị khoá trùng với một giá trị cho trƣớc. Khi tìm đƣợc 
bản ghi này, các thông tin đi kèm trong bản ghi sẽ đƣợc 
thu thập và xử lý. 
 Ví dụ: 
 Từ điển máy tính 
Phan Thị Hà 
Tìm kiếm tuần tự 
 Thủ tục tìm kiếm tuần tự trên một mảng các số 
nguyên nhƣ sau: 
int sequential_search(int *a, int x, int n){ 
 int i; 
 for (i=0; i<n ; i ++){ 
 if (a[i] == X) 
 return(i); 
 } 
 return(-1); 
} 
 Thuật toán tìm kiếm tuần tự có thời gian thực hiện 
là O(n). Trong trƣờng hợp xấu nhất, thuật toán 
mất n lần thực hiện so sánh và mất khoảng n/2 
lần so sánh trong trƣờng hợp trung bình. 
Phan Thị Hà 
Tìm kiếm nhị phân 
 Hàm tìm kiếm nhị phân đƣợc cài đặt nhƣ sau (giả 
sử dãy a đã đƣợc sắp): 
int binary_search(int *a, int x){ 
 int k, left =0, right=n-1; 
 do{ 
 k=(left+right)/2; 
 if (x<a[k]) right=k-1; 
 else l=k+1; 
 }while ((x!=a[k]) && (left<=right)) 
 if (x=a[k]) return k; 
 else return -1; 
} 
 Thuật toán tìm kiếm nhị phân có thời gian thực 
hiện là lgN. 
Phan Thị Hà 
Tìm kiếm trên cây nhị phân tìm 
kiếm 
 Mã nguồn: 
struct node { 
 int item; 
 struct node *left; 
 struct node *right; 
} 
typedef struct node *treenode; 
treenode tree_search(int x, treenode root){ 
 int found=0; 
 treenode temp=root; 
 while (temp!=NULL){ 
 if (x < temp.item) temp=temp.left; 
 elseif (x > temp.item)temp=temp.right; 
 else break; 
 } 
 return temp; 
} 
Phan Thị Hà 
 Các nhóm tự tìm hiểu về cây AVL và làm 
báo cáo 
Phan Thị Hà