Bài giảng môn Kỹ thuật lập trình - Nguyễn Duy Phương

 A[f]=ivalue; 
 } 
} 
void In(int *A, int n){ 
 register int i; 
 for(i=0;i<n;i++) 
 printf("%5d",A[i]); 
 delay(1000); 
} 
void main(void){ 
 int *A,n;clrscr(); 
 printf("\n Nhap n="); scanf("%d",&n); 
 A=(int *) malloc(n*sizeof(int)); 
 Init(A,n);Heap(A,n);printf("\n"); 
 In(A,n);getch(); 
 free(A); 
} 
6.8. GIẢI THUẬT MERGE SORT 
Sắp xếp theo Merge Sort là phương pháp sắp xếp bằng cách trộn hai danh sách đã 
được sắp xếp thành một danh sách đã được sắp xếp. Phương pháp Merge Sort được tiến 
hành thông qua các bước như sau: 
ƒ Bước 1: Coi danh sách là n danh sách con mỗi danh sách con gồm một phần tử, như 
vậy các danh sách con đã được sắp xếp. Trộn từng cặp hai danh sách con kế cận 
thành một danh sách có hai phần tử đã được sắp xếp, chúng ta nhận được n/2 danh 
sách con đã được sắp xếp. 
ƒ Bước 2: Xem danh sách cần sắp xếp như n/2 danh sách con đã được sắp xếp. Trộn 
cặp hai danh sách kế cận thành từng danh sách có 4 phần tử đã được sắp xếp, chúng 
ta nhận được n/4 danh sách con. 
Chương 6: Sắp xếp và tìm kiếm (sorting and searching) 
 144
ƒ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
ƒ Bước thứ i: Làm tương tự như bước i- 1. Quá trình được tiếp tục khi chúng ta nhận 
được danh sách có n phần tử đã được sắp xếp. Ví dụ với dãy: 
42 23 74 11 68 58 94 36 
lần 1: [23 42] [11 74] [58 68] [94 36] 
lần 2: [11 23 42 74] [36 58 68 94] 
lần 3: [11 23 42 36 58 68 74 94] 
 Chương trình cài đặt giải thuật Merge Sort được thực hiện như sau: 
#include 
#include 
#include 
#include 
#include 
#define MAX 10 
void Merge(int *, int ); 
void Init(int *, int); 
void In(int *, int); 
void Init(int *A, int n){ 
 int i; 
 printf("\n Tao lap day so:"); 
 for (i=0; i<n;i++){ 
 A[i]=random(1000); 
 printf("%5d",A[i]); 
 } 
 delay(1000); 
} 
void Merge(int *A, int n) { 
 int i,j,k,low1,up1,low2,up2,size; 
 int *dstam;size=1;dstam=(int *) malloc(n*sizeof(int)); 
 while(size<n){ 
 low1=0;k=0; 
 while(low1 +size <n){ 
 low2=low1+size; up1=low2-1; 
 if (low2+size-1< n) 
 up2=low2+size-1; 
 else 
 up2=n-1; 
 for(i=low1, j=low2; i<=up1 && j<=up2; k++){ 
 if(A[i]<=A[j]) 
Chương 6: Sắp xếp và tìm kiếm (sorting and searching) 
 145
 dstam[k]=A[i++]; 
 else 
 dstam[k] =A[j++]; 
 } 
 for(;i<=up1;k++) 
 dstam[k]=A[i++]; 
 for(;j<=up2;k++) 
 dstam[k]=A[j++]; 
 low1=up2+1; 
 } 
 for (i=low1; k<n;i++) 
 dstam[k++]=A[i]; 
 for(i=0;i<n;i++) 
 A[i]=dstam[i]; 
 size*=2; 
 } 
 printf("\n Ket qua:"); 
 In(A,n);free(dstam); 
} 
void In(int *A, int n){ 
 register int i; 
 for(i=0;i<n;i++) 
 printf("%5d",A[i]); 
 delay(1000); 
} 
void main(void){ 
 int *A,n;clrscr(); 
 printf("\n Nhap n="); scanf("%d",&n); 
 A=(int *) malloc(n*sizeof(int)); 
 Init(A,n);Merge(A,n);printf("\n"); 
 free(A); 
} 
6.9. TÌM KIẾM (SEARCHING) 
Tìm kiếm là công việc quan trọng đối với các hệ thống tin học và có liên quan mật 
thiết với quá trình sắp xếp dữ liệu. Bài toán tìm kiếm tổng quát có thể được phát biểu như 
sau: 
“Cho một bảng gồm n bản ghi R1, R2, . ., Rn. Với mỗi bản ghi Ri được tương ứng với 
một khoá ki (trường thứ i trong record). Hãy tìm bản ghi có giá trị của khoá bằng X cho 
trước”. 
Chương 6: Sắp xếp và tìm kiếm (sorting and searching) 
 146
Nếu chúng ta tìm được bản ghi có giá trị khóa là X thì phép tìm kiếm được thoả 
(successful). Nếu không có giá trị khóa nào là X thì quá trình tìm kiếm là không thoả 
(unsuccessful). Sau quá trình tìm kiếm, có thể xuất hiện yêu cầu bổ xung thêm bản ghi mới 
có giá trị khóa là X thì giải thuật được gọi là giải thuật tìm kiếm bổ sung. 
6.9.1. Tìm kiếm tuần tự (Sequential Searching) 
Tìm kiếm tuần tự là kỹ thuật tìm kiếm cổ điển trên một danh sách chưa được sắp xếp. 
Nội dung cơ bản của phương pháp tìm kiếm tuần tự là duyệt từ bản ghi thứ nhất cho tới bản 
ghi cuối cùng, và so sánh lần lượt giá trị của khoá với giá trị X cần tìm. Trong quá trình 
duyệt, nếu có bản ghi trùng với giá trị X thì chúng ta đưa ra vị trí của bản ghi trong dãy, nếu 
duyệt tới cuối dãy mà không có bản ghi nào có giá trị của khoá trùng với X thì quá trình tìm 
kiếm trả lại giá trị -1 (-1 được hiểu là giá trị khoá X không thuộc dãy). Chương trình cài đặt 
phương pháp tìm kiếm tuần tự được thực hiện như sau: 
#include 
#include 
#include 
#include 
#include 
int Sequential(int *, int, int); 
void Init(int *, int); 
void Init(int *A, int n){ 
 int i; 
 printf("\n Tao lap day so:"); 
 for (i=0; i<n;i++){ 
 A[i]=random(1000); 
 printf("%5d",A[i]); 
 } 
 delay(1000); 
} 
int Bubble(int *A, int x, int n){ 
 register i,temp; 
 for (i=0; i<n ; i ++){ 
 if (A[i] == X) 
 return(i); 
 } 
 return(-1); 
} 
void main(void){ 
 int *A,n, x, k;clrscr(); 
 printf("\n Nhap n="); scanf("%d",&n); 
 printf(“\n Số x cần tìm:”); scanf(“%d”, &x); 
Chương 6: Sắp xếp và tìm kiếm (sorting and searching) 
 147
 A=(int *) malloc(n*sizeof(int)); 
 k= Sequential(A,x,n); 
 if ( k>=0) 
 printf(“\n %d ở vị trí %d”, x,k); 
 else 
 printf(“\n %d không thuộc dãy”); 
 free(A); getch(); 
} 
6.9.2. Tìm kiếm nhị phân (Binary Searching) 
Tìm kiếm nhị phân là phương pháp tìm kiếm phổ biến được thực hiện trên một dãy đã 
được sắp thứ tự. Nội dung của giải thuật được thực hiện như sau: lấy khóa cần tìm kiếm X 
so sánh với nội dung của khóa của phần tử ở giữa, vị trí của phần tử ở giữa là mid = (low + 
hight )/ 2, trong đó cận dưới low =0, cận trên hight = n-1. Vì dãy đã được sắp xếp nên nếu 
nội dung của khóa tại vị trí giữa lớn hơn X thì phần tử cần tìm thuộc khoảng [mid+1, hight], 
nếu nội dung của khóa tại vị trí giữa nhỏ hơn X thì phần tử cần tìm thuộc khoảng [low, mid-
1], nếu nội dung của khóa tại vị trí giữa trùng với X thì đó chính là phần tử cần tìm. Ở bước 
tiếp theo, nếu nội dung của khóa tại vị trí giữa lớn hơn X thì ta dịch chuyển cận dưới low 
lên vị trí mid+ 1, nếu nội dung của khóa tại vị trí giữa nhỏ hơn X thì ta dịch chuyển cận 
trên về vị trí mid- 1. Quá trình được lặp lại cho tới khi gặp khóa có nội dung trùng với X 
hoặc cận dưới vượt quá cận trên hay X không thuộc dãy. Thuật toán tìm kiếm nhị phân 
được minh họa như sau: 
int Binary_Search( int *A, int X, int n){ 
 int mid, low=0, hight = n-1; 
 while ( low<=hight ){ // lặp nếu cận dưới vẫn nhỏ hơn cận trên 
 mid = (low + hight) /2; // xác định vị trí phần tử ở giữa 
 if (X > A[mid] ) low = mid +1; // X thuộc [mid+1, hight] 
 else if (X < A[mid] ) hight = mid- 1; // X thuộc [low, mid-1] 
 else return(mid); 
 } 
 return(-1); // X không thuộc dãy 
} 
 Chương trình cụ thể được cài đặt như sau: 
#include 
#include 
#include 
#include 
#include 
int Binary_Search( int *, int, int); 
void Bubble(int *, int); 
void Init(int *, int); 
Chương 6: Sắp xếp và tìm kiếm (sorting and searching) 
 148
int Binary_Search( int *A, int X, int n) { 
 int mid, low = 0, hight = n-1; 
 while (low<=hight){ 
 mid = (low +hight)/2; 
 if (X >A[mid] ) low = mid +1; 
 else if (X<A[mid] ) hight = mid -1; 
 else return (mid); 
 } 
 return(-1); 
} 
void Init(int *A, int n){ 
 int i; 
 printf("\n Tao lap day so:"); 
 for (i=0; i<n;i++){ 
 A[i]=random(1000); 
 printf("%5d",A[i]); 
 } 
 delay(1000); 
} 
void Bubble(int *A, int n){ 
 register i,j,temp; 
 for (i=1; i<n; i++){ 
 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; 
 } 
 } 
 printf("\n Ket qua lan:%d", i); 
 In(A,n); 
 } 
} 
void In(int *A, int n){ 
 register int i; 
 for(i=0;i<n;i++) 
 printf("%5d",A[i]); 
 delay(1000); 
} 
void main(void){ 
 int *A,n, X, k;clrscr(); 
Chương 6: Sắp xếp và tìm kiếm (sorting and searching) 
 149
 printf("\n Nhap n="); scanf("%d",&n); 
 printf(“\n Số cần tìm X=”); scanf(“%d”,&X); 
 A=(int *) malloc(n*sizeof(int)); 
 Init(A,n);Bubble(A,n); k= Binary_Search(A, X, n); 
 if ( k>0) 
 printf (“\n %d ở vị trí số %d”, X, k); 
 else 
 printf(“\n %d không thuộc dãy”); 
 getch(); 
 free(A); 
} 
Chương 6: Sắp xếp và tìm kiếm (sorting and searching) 
 150
NHỮNG NỘI DUNG CẦN GHI NHỚ 
9 Hiểu được ý nghĩa vai trò của bài toán sắp xếp và tìm kiếm trong tin học. 
9 Cài đặt nhuần nhuyễn các giải thuật sắp xếp và tìm kiếm trên các cấu trúc dữ liệu 
khác nhau. 
9 Giải quyết các bài tập thực hành kèm theo làm thăng tiến kỹ năng giải quyết bài 
toán sắp xếp & tìm kiếm. 
Chương 6: Sắp xếp và tìm kiếm (sorting and searching) 
 151
BÀI TẬP CHƯƠNG 6 
Bài 1. Cài đặt chương trình theo thuật toán Quick Sort không dùng phương pháp đệ qui mà 
dùng cấu trúc stack. 
Bài 2. Tìm hiểu về giải thuật Shell-Sort là phương pháp cải tiến của Insertion Sort. 
Bài 3. Cài đặt lại giải thuật Bubble Sort sao cho các node nhỏ được đẩy dần về phía trước. 
Bài 4. Một Ternary Heap là cây tam phân gần đầy được cài đặt bằng mảng một chiều, mỗi 
node có ba node con. Nội dung của node cha bao giờ cũng lớn hơn hoặc bằng nội 
dung của node con, các node được đánh số từ 0 đến n-1, node i có 3 con là 3i+1, 3i+2, 
3i+3. Hãy cài đặt giải thuật Ternary Heap. 
Bài 5. Cài đặt giải thuật Bubble Sort trên file. 
Bài 6. Cài đặt giải thuật Insertion Sort trên file. 
Bài 7. Cài đặt giải thuật Quick Sort trên file. 
Bài 8. Cài đặt các giải thuật sắp xếp theo nhiều khoá khác nhau. 
Bài 9. Nghiên cứu và cài đặt thuật toán tìm kiếm tam phân. 
Bài 10. Nghiên cứu và cài đặt thuật toán sắp xếp kiểu hoà nhập thực hiện trên file. 
Bài 11. Viết chương trình chuyển đổi một file dữ liệu được tổ chức theo khuôn dạng *.DBF 
thành file kiểu text. Ngược lại, chuyển đổi file dữ liệu kiểu text thành một file dữ liệu 
theo khuôn dạng DBF. 
Bài 12. Tìm hiểu cách sắp xếp và tìm kiếm theo kiểu index của các hệ quản trị cơ sở dữ liệu 
như foxprol hoặc access. 
Tài liệu tham khảo 
 152
TÀI LIỆU THAM KHẢO 
[1] Lê Hữu Lập - Nguyễn Duy Phương. Giáo trình Kỹ thuật lập trình. NXB Bưu 
Điện, 2002. 
[2] Đỗ Xuân Lôi. Cấu trúc dữ liệu và giải thuật. NXB Khoa Học Kỹ Thuật, 2000. 
[3] Đặng Huy Ruận. Lý thuyết đồ thị. NXB Khoa Học Kỹ Thuật, 2003 
[4] William Ford, William Topp. Data Structures with C++. Prentice Hall, 1996. 
[5] Mark Allen Weiss. Data Structures and Algorithm Analysis In C. Prentice Hall, 
1996. 
[6] Phan Đăng Cầu. Cấu trúc dữ liệu và Giải thuật (Tài liệu giảng dạy–Học Viện 
Công nghệ BCVT), 2003. 
Mục lục 
 153
MỤC LỤC 
Chương 1: ĐẠI CƯƠNG VỀ KỸ THUẬT LẬP TRÌNH CẤU TRÚC..................................3 
1.1. Sơ lược về lịch sử lập trình cấu trúc...............................................................3 
1.2. Cấu trúc lệnh, lệnh có cấu trúc, cấu trúc dữ liệu ............................................5 
1.2.1. Cấu trúc lệnh (cấu trúc điều khiển) ........................................................5 
1.2.2. Lệnh có cấu trúc .....................................................................................7 
1.2.3. Cấu trúc dữ liệu......................................................................................7 
1.3. Nguyên lý tối thiểu .........................................................................................8 
1.3.1. Tập các phép toán ..................................................................................8 
1.3.2. Tập các lệnh vào ra cơ bản...................................................................11 
1.3.3. Thao tác trên các kiểu dữ liệu có cấu trúc............................................11 
1.4. Nguyên lý địa phương ..................................................................................13 
1.5. Nguyên lý nhất quán.....................................................................................15 
1.6. Nguyên lý an toàn.........................................................................................16 
1.7. Phương pháp Top-Down ..............................................................................18 
1.8. Phương pháp Bottom - Up............................................................................22 
Chương 2: DUYỆT VÀ ĐỆ QUI ..........................................................................................29 
2.1. Định nghĩa bằng đệ qui ................................................................................29 
2.2. Giải thuật đệ qui ...........................................................................................30 
2.3. Thuật toán sinh kế tiếp .................................................................................31 
2.4. Thuật toán quay lui (Back track) .................................................................34 
2.5. Thuật toán nhánh cận ...................................................................................37 
Chương 3: NGĂN XẾP, HÀNG ĐỢI VÀ DANH SÁCH MÓC NỐI (STACK, QUEUE, 
LINK LIST)...........................................................................................................................51 
3.1. Kiểu dữ liệu ngăn xếp và ứng dụng..............................................................51 
3.1.1. Định nghĩa và khai báo ........................................................................51 
3.1.2. Các thao tác với stack ..........................................................................53 
3.1.3. Ứng dụng của stack..............................................................................53 
Mục lục 
 154
3.2. Hàng đợi (Queue) .........................................................................................55 
3.2.1. Định nghĩa và khai báo ........................................................................55 
3.2.2. Ứng dụng hàng đợi...............................................................................57 
3.3. Danh sách liên kết đơn .................................................................................62 
3.3.1. Giới thiệu và định nghĩa.......................................................................62 
3.3.2. Các thao tác trên danh sách móc nối ....................................................63 
3.4. Danh sách liên kết kép..................................................................................67 
Chương 4: CẤU TRÚC DỮ LIỆU CÂY (TREE).................................................................77 
4.1. Định nghĩa và khái niệm ..............................................................................77 
4.2. Cây nhị phân.................................................................................................78 
4.3. Biểu diễn cây nhị phân .................................................................................81 
4.3.1. Biểu diễn cây nhị phân bằng danh sách tuyến tính ..............................81 
4.3.2. Biểu diễn cây nhị phân bằng danh sách móc nối .................................82 
4.4. Các thao tác trên cây nhị phân......................................................................83 
4.4.1. Định nghĩa cây nhị phân bằng danh sách tuyến tính............................83 
4.4.2. Định nghĩa cây nhị phân theo danh sách liên kết:...............................83 
4.4.3. Các thao tác trên cây nhị phân .............................................................83 
4.5. Các phép duyệt cây nhị phân (Traversing Binary Tree)...............................88 
4.5.1. Duyệt theo thứ tự trước (Preorder Travesal)........................................88 
4.5.2. Duyệt theo thứ tự giữa (Inorder Travesal) ...........................................89 
4.5.3. Duyệt theo thứ tự sau (Postorder Travesal) .........................................89 
4.6. Cài đặt cây nhị phân tìm kiếm......................................................................90 
Chương 5: ĐỒ THỊ (GRAPH) ............................................................................................103 
5.1. Những khái niệm cơ bản của đồ thị............................................................103 
5.1.1. Các loại đồ thị ....................................................................................103 
5.1.2. Một số thuật ngữ cơ bản của đồ thị ....................................................106 
5.1.3. Đường đi, chu trình, đồ thị liên thông................................................107 
5.2. Biểu diễn đồ thị trên máy tính ....................................................................107 
5.2.1. Ma trận kề, ma trận trọng số ..............................................................107 
5.2.2. Danh sách cạnh (cung ) ......................................................................109 
5.2.3. Danh sách kề ......................................................................................110 
Mục lục 
 155
5.3. Các thuật toán tìm kiếm trên đồ thị ............................................................110 
5.3.1. Thuật toán tìm kiếm theo chiều sâu ...................................................110 
5.3.2. Thuật toán tìm kiếm theo chiều rộng (Breadth First Search).............111 
5.3.3. Kiểm tra tính liên thông của đồ thị.....................................................112 
5.3.4. Tìm đường đi giữa hai đỉnh bất kỳ của đồ thị ....................................113 
5.4. Đường đi và chu trình Euler .......................................................................115 
5.5. Đường đi và chu trình Hamilton.................................................................118 
5.6. Cây bao trùm ..............................................................................................119 
5.6.1. Khái niệm và định nghĩa ....................................................................119 
5.6.2. Tìm một cây bao trùm trên đồ thị.......................................................120 
5.6.3. Tìm cây bao trùm ngắn nhất...............................................................121 
5.6.4. Thuật toán Kruskal.............................................................................122 
5.6.5. Thuật toán Prim..................................................................................122 
5.7. Bài toán tìm đường đi ngắn nhất ................................................................123 
5.7.1. Phát biểu bài toán...............................................................................123 
5.7.2. Thuật toán Dijkstra.............................................................................124 
5.7.3. Thuật toán Floy ..................................................................................124 
Chương 6: SẮP XẾP VÀ TÌM KIẾM (SORTING AND SEARCHING)..........................131 
6.1. Đặt bài toán ................................................................................................131 
6.2. Giải thuật Selection Sort.............................................................................132 
6.3. Giải thuật Insertion Sort .............................................................................134 
6.4. Giải thuật Bubble Sort ................................................................................136 
6.5. Giải thuật Shaker Sort ................................................................................137 
6.6. Giải thuật Quick Sort..................................................................................139 
6.7. Giải thuật Heap Sort ...................................................................................141 
6.8. Giải thuật Merge Sort .................................................................................143 
6.9. Tìm kiếm (Searching).................................................................................145 
6.9.1. Tìm kiếm tuần tự (Sequential Searching) ..........................................146 
6.9.2. Tìm kiếm nhị phân (Binary Searching)..............................................147 
TÀI LIỆU THAM KHẢO .........................................................................................152 
MỤC LỤC.................................................................................................................153