Giáo trình Kỹ thuật lập trình 2

ight. Các bước tiến hành như sau: Bước 1: left =1, right = n // tìm kiếm trên tất cả phần tử. Bước 2: mid = (left + right)/2 // lấy mốc so sánh So sánh a[mid] với x có 3 khả năng: a[mid] = x, tìm thấy Þ dừng a[mid]> x, tìm tiếp trong dãy a[left].. a[mid-1] right = mid -1; a[mid] < x, tìm tiếp trong dãy a[mid+1].. a[right] left = mid +1; Bước 3: Nếu left £ right; còn phần tử Þ tìm tiếp Þ bước 2 Ngược lại: dừng, đã xét hết phần tử Þ không tìm thấy. Ví dụ: cho dãy số gồm 8 phần tử {1, 2, 4, 5, 6, 8, 12, 15} và x = 8 1 Left = 1 X = 8 Right = 8 Mid = 4 Đoạn tìm kiếm 2 4 5 6 8 12 15 1 Left = 5 X = 8 Right = 8 Mid = 6 Đoạn tìm kiếm 2 4 5 6 8 12 15 = Hình 4.2: Tìm kiếm nhị phân. Hàm C minh họa cài đặt thuật toán tìm kiếm nhị phân int BinarySearch(int key) { int left = 0, right = n-1, mid; while (left <= right) { mid = (left + right)/ 2; // lấy điểm giữa if (a[mid] == key) // nếu tìm được return mid; if (a[mid] < x) // tìm đoạn bên phải mid left = mid+1; else right = mid-1; // tìm đoạn bên trái mid } return -1; // không tìm được } Kết luận Giải thuật tìm kiếm tuyến tính không phụ thuộc vào thứ tự của các phần tử trong mảng, do vậy đây là phương pháp tổng quát nhất để tìm kiếm trên một dãy bất kỳ. Thuật giải nhị phân dựa vào quan hệ giá trị của các phần tử trong mảng để định hướng trong quá trình tìm kiếm, do vậy chỉ áp dụng được với dãy đã có thứ tự. Thuật giải nhị phân tìm kiếm nhanh hơn tìm kiếm tuyến tính. Tuy nhiên khi áp dụng thuật giải nhị phân thì cần phải quan tâm đến chi phí cho việc sắp xếp mảng. Vì khi mảng được sắp thứ tự rồi thì mới tìm kiếm nhị phân. Bài toán sắp xếp 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. Ví dụ như: tăng dần, giảm dần với một dãy số, thứ tự từ điển với các từ...Việc sắp xếp là một bài toán thường thấy trong tin học, do các yêu cầu tìm kiếm thuận lợi, sắp xếp kết quả các bảng biểu... Dữ liệu thường được tổ chức thành mảng các mẫu tin dữ liệu, mỗi mẫu tin thường có một số các trường dữ liệu khác nhau. Không phải toàn bộ các trường đều tham gia quá trình sắp xếp mà chỉ có một trường nào đó (hoặc một vài trường) được quan tâm. Người ta gọi trường này là khoá, việc sắp xếp sẽ được tiến hành dựa vào giá trị khoá này. Ví dụ: sắp xếp một mảng các số nguyên tăng dần, sắp xếp một danh sách học sinh với điểm thi giảm dần... Một số phương pháp sắp xếp cơ bản Trong phần này giới thiệu một số phương pháp sắp xếp cơ bản thường được dùng để sắp xếp một danh sách, mảng dữ liệu. Phương pháp chọn Đây là một trong những thuật toán sắp xếp đơn giản nhất. Ý tưởng cơ bản của phương pháp này được thể hiện như sau: Ở lượt thứ nhất, ta chọn trong dãy khoá k[1..n] ra khoá nhỏ nhất và đổi giá trị nó với k[1], khi đó k[1] sẽ trở thành khoá nhỏ nhất. Ở lượt thứ hai, ta chọn trong dãy khoá k[2..n] ra khóa nhỏ nhất và đổi giá trị nó cho k[2]. ... Ở lượt thứ i, ta chọn trong dãy khóa k[i..n] ra khóa nhỏ nhất và đổi giá trị nó cho k[i]. Tới lượt k-1, ta chọn giá trị nhỏ nhất trong k[n-1] và k[n] ra khoá nhỏ nhất và đổi cho giá trị cho k[n-1]. Thuật giải SelectionSort: (mã giả, chỉ số 1 là đầu mảng) begin for i:= 1 to n-1 do begin jmin := i; for j:=i+1 to n do if a[j] < a[jmin] then jmin = j; if ( jmin i) Swap(a[i], a[jmin]) end. end. Phương pháp sắp xếp nổi bọt Trong thuật toán sắp xếp nổi bọt, dãy khóa sẽ được duyệt từ cuối lên đầu dãy, nếu gặp hai khóa kế cận ngược thứ tự thì đổi chỗ cho nhau. Sau lần duyệt như vậy, khóa nhỏ nhất trong dãy khóa sẽ được chuyển về vị trí đầu tiên và vấn đề trở thành sắp xếp dãy khoá từ k[n] đến k[2]. Thuật giải bubblesort: (mả giả, chỉ số 1 là đầu mảng) begin for i:=2 to n do for j:= n downto i do if (a[j] < a[j-1]) Swap(a[j],a[j-1]) end. Phương pháp sắp xếp chèn Xét dãy khóa k[1..n], ta thấy dãy con chỉ gồm mỗi một khoá là k[1] có thể coi là đã sắp xếp rồi. Xét thêm k[2], ta so sánh nó với k[1], nếu thấy k[2] < k[1] thì chèn nó vào trước k[1]. Đối với k[3], ta chỉ xét dãy chỉ gồm hai khoá k[1] và k[2] đã sắp xếp và tìm cách chèn k[3] vào dãy khóa đó để được thứ tự sắp xếp. Một cách tổng quát, ta sẽ sắp xếp dãy k[1..i] trong điều kiện dãy k[1..i-1] đã sắp xếp rồi bằng cách chèn k[i] vào dãy đó tại vị trí đúng khi sắp xếp. Thuật giải InsertionSort: (mả giả, chỉ số 1 là đầu mảng) begin for i:= 2 to n do begin tmp = a[i]; j = i-1; while (j>0) and (tmp < a[j]) begin a[j+1] = a[j]; // đẩy lùi giá trị k[i] về sau -> tạo khoảng trống j := j-1; end k[j+1] = tmp; // chèn vào khoảng trống. end end. Phương pháp đổi chỗ trực tiếp Ý tưởng chính: xuất phát từ đầu dãy, tìm những phần tử còn lại không thoả thứ tự sắp xếp với phần tử đang xét, hoán vị các phần tử tương ứng để thỏa thứ tự. Lặp lại tương tự với các phần tử tiếp theo của dãy. Các bước tiến hành như sau: Bước 1: i = 1; // xuất phát từ đầu dãy Bước 2: j = i+1; // tìm các phần tử phía sau i Bước 3: While j £ n do Nếu a[j]< a[i] Þ Swap(a[i], a[j]); j = j+1; Bước 4: i = i+1; Nếu i < n: Þ Bước 2 Ngược lại Þ Kết thúc Ví dụ: cho dãy số a: 10 3 7 6 2 5 4 16 Hình 4.3: Minh họa đổi chỗ trực tiếp. Phương pháp ShellSort Trong phương pháp sắp xếp kiểu chèn nếu ta luôn phải chèn một khóa vào vị trí đầu dãy thì dẫn đến hạn chế của thuật toán này. Để khắc phục trong trường hợp này thì người ta đưa ra một phương pháp sắp xếp là ShellSort. Ý tưởng chính: xét một dãy a[1]...a[n], cho một số nguyên h (1 £ h £ n), ta có thể chia dãy đó thành h dãy con như sau: Dãy con 1: a[1], a[1+ h], a[1+2h]... Dãy con 2: a[2], a[2+h], a[2+2h]... Dãy con 3: a[3], a[3+h], a[3+2h]... ... Dãy con h: a[h], a[2h], a[3h]... Ví dụ cho dãy: 10 3 7 6 2 5 4 16 n = 8, h = 3. Ta có dãy con sau: Dãy chính 10 3 7 6 2 5 4 16 Dãy con 1 10 6 4 Dãy con 2 3 2 16 Dãy con 3 7 5 Những dãy này được coi là những dãy con xếp theo độ dài bước h. Tư tưởng chính của thuật toán ShellSort là: với mỗi bước h, áp dụng thuật toán sắp xếp kiểu chèn từng dãy con độc lập để làm mịn dần các phần tử trong dãy chính. Tiếp tục làm tương tự đối với bước (h div 2)... cho đến khi h = 1 thì ta được dãy phần tử được sắp. Xét trong ví dụ trên, nếu chúng ta dùng phương pháp chèn thì với phần tử a[5] = 2 là phần tử nhỏ nhất trong dãy, do đó nó phải chèn vào vị trí thứ 1, tức là phải chèn trước 4 phần tử trước nó. Nhưng nếu chúng ta xem 2 là phần tử của dãy 2 thì ta chỉ cần chèn trước một phần tử là 3. Đây chính là nguyên nhân thuật toán ShellSort thực hiện hiệu quả hơn sắp xếp chèn. Khi đó khóa nhỏ nhanh chóng đưa về gần vị trí đúng của nó. Các bước thực hiện chính như sau: Bước 1: chọn k khoảng cách h[1], h[2],.., h[k], và i = 1. Bước 2: Chia dãy ban đầu thành các dãy con có bước nhảy là h[i]. Thực hiện sắp xếp từng dãy con bằng phương pháp chèn trực tiếp. Bước 3: i = i+1 Nếu i > k: Þ Dừng Ngược lại: Þ Bước 2. Ví dụ: cho dãy bên dưới với n = 8, h = {5, 3, 1}. 10 3 7 6 2 5 4 16 Ta có minh họa như sau: Hình 4.4: Minh hoạ ShellSort. Cài đặt ShellSort: sắp xếp dãy a[] tăng, với h[] là mảng chứa các độ dài (bước nhảy) đã chọn sẵn: void ShellSort(int a[], int n, int h[], int k) { int step, i, j; int x, len; for(step = 0; step < k; step++) // duyệt qua từng bước nhảy { len = h[step]; // chiều dài của bước nhảy for(i = len; i < n; i++) // duyệt các dãy con { // lưu phần tử cuối để tìm vị trí thích hợp trong dãy con x = a[i]; // a[j] đứng trước a[i] trong cùng dãy con j = i – len; while ((x = 0)) // sắp xếp dãy con chứa x dùng pp chèn { a[j+len] = a[j]; // dời về sau theo dãy con j = j – len; // qua phần tử trước trong dãy con } a[j+len] = x; // đưa x vào vị trí thích hợp trong dãy con } } } Phương pháp phân đoạn QuickSort Đây là một phương pháp sắp xếp tốt do C.A.R Hoare đề xuất. Thuật toán này có tốc độ trung bình nhanh hơn các thuật toán sắp xếp tổng quát khác. Do đó Hoare dùng chữ “Quick” để đặt tên cho thuật toán này. Ý tưởng chính: Để sắp dãy a[1] ... a[n], ta thực hiện sắp xếp dãy a từ chỉ số 1 đến chỉ số n. QuickSort dựa trên phân hoạch dãy ban đầu thành hai phần dựa vào giá trị x, x là giá trị của một phần tử tùy ý trong dãy ban đầu: Dãy thứ 1: gồm các phần tử a[1]..a[i] có giá trị không lớn hơn x. Dãy thứ 2: gồm các phần tử a[i]..a[n] có giá trị không nhỏ hơn x. Sau khi phân hoạch thì dãy ban đầu được phân thành ba phần: a[k] < x, với k = 1..i a[k] = x, với k = i..j a[k] > x, với k = j..n Ta có nhận xét khi đó dãy con thứ 2 đã có thứ tự, nếu dãy con 1 và dãy con 3 có một phần tử thì chúng cũng đã có thứ tự, khi đó dãy ban đầu đã được sắp. Ngược lại, nếu dãy con 1 và 3 có nhiều hơn một phần tử thì dãy ban đầu có thứ tự khi dãy con 1 và 3 được sắp. Để sắp xếp dãy con 1 và 3, ta lần lượt tiến hành việc phân hoạch từng dãy con theo cùng phương pháp vừa trình bày. Giải thuật phân hoạch dãy a[left], a[left+1],.., a[right] thành hai dãy con: Bước 1: Chọn tùy ý một phần tử a[k] trong dãy là giá trị mốc, left £ k £ right, Cho x = a[k], i = left, j = right. Bước 2: Tìm và hoán vị cặp phần tử a[i] và a[j] không đúng thứ tự đang sắp. Bước 2-1: Trong khi a[i] < x Þ i++; Bước 2-2: Trong khi a[j] > x Þ j--; Bước 2-3: Nếu i < j Þ Swap(a[i], a[j]) // a[i], a[j] sai thứ tự Bước 3: Nếu i < j: Þ Bước 2; // chưa hết mảng dừng Nếu i ³ j: Þ Dừng. Giải thuật để sắp xếp dãy a[left], a[left+1],.., a[right]: được phát biểu theo cách đệ quy như sau: Bước 1: Phân hoạch dãy a[left]...a[right] thành các dãy con: Dãy con 1: a[left]...a[j] < x Dãy con 2: a[j+1]...a[i-1] = x Dãy con 3: a[i]...a[right] > x Bước 2: Nếu (left < j) // dãy con 1 có nhiều hơn 1 phần tử Phân hoạch dãy a[left]...a[j] Nếu (i < right) // dãy con 3 có nhiều hơn 1 phần tử Phân hoạch dãy a[i]...a[right] Ví dụ phân hoạch dãy sau: 10 3 7 6 2 5 4 16 Phân hoạch đoạn left = 1, right = 8, x = a[4] = 6 Phân hoạch đoạn left = 1, right = 4, x = a[2] = 3 Phân hoạch đoạn left = 3, right = 4, x = a[3] = 5 Phân hoạch đoạn left = 6, right = 8, x = a[7] = 10 QuickSort được cài đặt đệ quy như sau: void QuickSort(int a[], int left, int right) { int i, j; int x; x = a[(left+right)/2]; // chọn phần tử giữa làm gốc i = left; j = right; do{ while (a[i] = x while (a[j] > x) j--; // lặp đến khi a[i] <= x if ( i <= j) // nếu có 2 phần tử a[i] và a[j] ko theo thứ tự { Swap(a[i], a[j]); i++; // qua phần tử kế tiếp j--; // qua phần tử đứng trước } } while (i<j); if (left < j) // phân hoạch đoạn bên trái QuickSort(a, left, j); if (right > i) // phân hoạch đoạn bên phải QuickSort(a, i, right); }  Phương pháp cơ số RadixSort Thuật giải sắp xếp theo phương pháp cơ số không quan tâm đến việc so sánh giá trị của các phần tử như các thuật giải trước. RadixSort sử dụng cách thức phân loại các con số trong dãy và thứ tự phân loại con con số này để tạo ra thứ tự cho các phần tử. Đây là cách tiếp cận khác so với các phương pháp sắp xếp trước là so sánh các giá trị của các phần tử. Thuật giải dựa trên ý tưởng chính là sắp xếp từng con số của một dãy các số. Giả sử chúng ta có dãy số như sau: 493 812 715 710 195 437 582 340 385. Đầu tiên sắp xếp các số theo hàng đơn vị: 493 812 715 710 195 437 582 340 385. Ta được bảng kết quả minh họa như sau: Số hàng đơn vị Dãy con 0 710 340 1 - 2 812 582 3 493 4 - 5 715 195 385 6 - 7 437 8 - 9 - Bảng 4.1: Sắp theo hàng đơn vị Lưu ý những phần tử này được đưa vào dãy con theo thứ tự tìm thấy, do đó chúng ta có thể thấy là các dãy con chưa có thứ tự. Lúc này chúng ta thu được một danh sách gồm các dãy con từ 0 ® 9 như sau: 710 340 812 582 493 715 195 385 437 Tiếp tục chúng ta phân loại các phần tử của dãy trên theo con số của hàng chục: 710 340 812 582 493 715 195 385 437 Số hàng chục Dãy con 0 - 1 710 812 715 2 - 3 437 4 340 5 - 6 - 7 - 8 582 385 9 493 195 Bảng 4.2: Sắp theo hàng chục Lúc này chúng ta thu được danh sách như sau: 710 812 715 437 340 582 385 493 195 Thực hiện tiếp với phân loại các con số hàng trăm: 710 812 715 437 340 582 385 493 195 Số hàng trăm Dãy con 0 - 1 195 2 - 3 340 385 4 437 493 5 582 6 - 7 710 715 8 812 9 - Bảng 4.3: Sắp theo hàng trăm Thu được danh sách các phần tử từ dãy con được phân loại theo hàng trăm từ 0 ® 9. 195 340 385 437 493 582 710 715 812 Như chúng ta thấy thì lúc này dãy đã được sắp! Tóm lại để sắp xếp dãy a[1], a[2],..., a[n] giải thuật RadixSort thực hiện như sau: Xem mỗi phần tử a[i] trong dãy a[1]...a[n] là một số nguyên có tối đa m chữ số Lần lượt phân loại các chữ số theo hàng đơn vị, hàng chục, hàng trăm...Tại mỗi bước phân loại ta sẽ nối các dãy con từ danh sách đã phân loại theo thứ tự 0 ® 9. Sau khi phân loại xong ở hàng thứ m cao nhất ta sẽ thu được danh sách các phần tử được sắp. Các bước thực hiện thuật giải: Bước 1: k = 0; // k là chữ số phân loại, k = 0 hàng đơn vị, k = 1 hàng chục... Bước 2: // Tạo các dãy chứa phần tử phân loại B[0]...B[9] Khởi tạo B[0]...B[9] rỗng, chưa chứa phần tử nào, B[i] sẽ chứa các phần tử có chữ số thứ k là i. Bước 3: For i=1 to n do Đặt a[i] vào dãy B[j] với j là chữ số thứ k của a[i]. Nối B[0], B[1],..., B[9] lại theo đúng trình tự thành a. Bước 4: k = k +1 Nếu k < m: Þ Bước 2. // m là số lượng chữ số tối đa của các số trong mảng Ngược lại: Þ Dừng. Giải thuật sắp xếp theo cơ số RadixSort: Mảng a[MAX] chứa các phần tử của mảng cần sắp tăng. Mảng B[10][MAX] chứa các dãy số được phân tạm thời theo các con số. Ví dụ B[0] chứa các phần tử có con số ở hàng đơn vị là 100, 210, 320...Khi đó với mỗi dòng của B thì sẽ phân các phần tử có con số ở hàng thứ i (i từ 0 - 9), các giá trị cột j sẽ lần lượt chứa các phần tử có cùng con số ở hàng thứ i. Mảng Len[10] chứa số lượng các phần tử của các dòng B[i]. Ví dụ B[0] có 3 phần tử thì Len[0] = 3, B[5] có 2 phần tử thì B[5] = 2. Tại mỗi bước trước khi phân các phần tử vào mảng B thì các Len[i] được khởi tạo là 0. Cài đặt RadixSort: void RadixSort(long a[], int n) { int i, j, d; int h = 10; // biến để lấy các con số, bắt đầu từ hàng đơn vị long B[10][MAX]; // mảng hai chiều chứa các phần tử phân lô int Len[10]; // kích thước của từng mảng B[i] // MAXDIGIT là số con số tối đa của các phần tử a[i] for(d = 0; d < MAXDIGIT; d++) { // khởi tạo kích thước các dãy B[i] là 0 for( i = 0; i < 10; i++) Len[i] = 0; // thực hiện phân lô các phần tử theo con số hàng thứ d tính từ cuối for(i = 0; i < n; i++) // duyệt qua tất cả các phần tử của mảng { digit = (a[i] % h) / (h/ 10); // lấy con số theo hàng h // đưa vào dãy (lô) B[digit] ở cột Len[digit] B[digit][Len[digit]++] = a[i]; }// end for i // thực hiện nối lại tuần tự từ B[0] – đến B[9] vào mảng a[] ban đầu num = 0; // chỉ số bắt đầu cho mảng a[] for(i = 0; i < 10; i++) // duyệt qua các dãy từ B[0] – đến B[9] { // lấy từng phần tử của từng dãy B[i] for(j =0; j < Len[i]; j++) a[num++] = B[i][j]; }// end for i h *= 10; // qua hàng kế tiếp. }// end for d }// end RadixSort ›¯š Stack - Queue ›¯š Giới thiệu Stack – ngăn xếp Ngăn xếp là kiểu danh sách với hai thao tác đặc trưng bổ sung một phần tử vào cuối danh sách và loại bỏ một phần tử cũng ở cuối danh sách. Nói một cách khác là thao tác thêm phần tử và loại phần tử chỉ diễn ra ở một đầu của danh sách. Đưa vào (Push) Lấy ra (Pop) Stack Đỉnh stack (top) Hình 5.1: Minh họa Stack. Chúng ta có thể hình dung một cách đơn giản như hình ảnh một chồng đĩa, đĩa nào được đặt vào chồng sau cùng sẽ nằm trên tất cả đĩa khác và sẽ được lấy ra đầu tiên. Vì nguyên tắc vào sau ra trước đó, Stack còn có tên gọi là danh sách kiểu LIFO (Last In First Out). Vị trí cuối cùng được gọi là đỉnh (top) của ngăn xếp. Hai thao tác chính trên Stack là: Thao tác push: đưa một phần tử vào đỉnh của Stack Thao tác pop: xoá đi một phần tử ở đỉnh của Stack. Ví dụ: Cho Stack S và các thao tác như sau: Khởi tạo S là rỗng như hình 5.2.1. Thêm một phần tử vào Stack S: Push(S, A) có kết quả như hình 5.2.2 Thêm một phần tử vào Stack S: Push(S, B) có kết quả như hình 5.2.3. Loại phần tử đầu Stack S: Pop(S) ta được Stack S như hình 5.2.4. Thêm phần tử vào Stack S: Push(S, C) kết quả Stack S như hình 5.2.5. Hình 5.2: Minh họa các thao tác trên Stack. Cài đặt Stack dùng CTDL mảng Trong phần này chúng ta sẽ cài đặt một Stack dùng cấu trúc dữ liệu mảng. Để cho tổng quát ta gọi Data là kiểu dữ liệu được định nghĩa mà Stack lưu trữ, ví dụ Data có thể là số nguyên, thực... hoặc một cấu trúc dữ liệu nào đó: typedef int Data typedef float Data typedef struct { int ID; char Name[50]; float Salary; ... } Data; ... Khai báo cấu trúc dữ liệu Stack trên mảng: #define MAX 100 typedef struct{ int top; Data S[MAX]; } Stack; Hình 5.3: Minh họa Stack dùng mảng một chiều. Trong cấu trúc Stack này các trường có ý nghĩa như sau: top: chỉ đến đỉnh của Stack, top = -1 Þ Stack rỗng, top ³ 0 Þ Stack có phần tử S[MAX]: chứa dữ liệu của Stack lưu trữ, để truy cập đến phần tử đỉnh thì dùng trường top. Các thao tác trên Stack được mô tả như sau: void Push(Stack &st, Data x): Đưa một phần tử x vào đỉnh của Stack. Data Pop(Stack &st): Lấy một phần tử ở đỉnh ra khỏi Stack. void InitStack(Stack &st): Hàm khởi tạo một Stack mới rỗng int IsEmpty(Stack st): Kiểm tra xem Stack có rỗng hay không. int IsFull(Stack st): Kiểm tra xem Stack đầy hay chưa. Data Top(Stack st): Xem một phần tử ở đỉnh (không lấy ra). Cài đặt của các thao tác: #define TRUE 1 #define FALSE 0 void Push(Stack &st, Data x) { if (IsFull(st)) { printf(“\nStack full!”); } else st.S[++st.top] = x; } Data Pop(Stack &st) { if (IsEmpty(st)) printf(“\nStack empty!”); else return (st.S[st.top--]); } void InitStack(Stack &st) { st.top = -1; } int IsEmpty(Stack st) { if (st.top == -1) return TRUE; else return FALSE; } int IsFull(Stack st) { if (st.top >= MAX) return TRUE; else return FALSE; } Data Top(Stack st) { Data d; if (IsEmpty(st)) printf(“\n Stack empty!”); else d = st.S[st.top]; return d; } Các ứng dụng stack Thông thường cấu trúc dữ liệu stack thích hợp cho việc lưu trữ dữ liệu mà trình tự truy xuất ngược với trình tự lưu trữ. Có nghĩa là dữ liệu lưu trữ trước sẽ được lấy ra sau những dữ liệu lưu sau (LIFO). Do đó stack có một số ứng dụng như sau: Trong trình biên dịch, stack dùng để lưu trữ các lời gọi hàm, ví dụ như hàm A gọi hàm B, hàm B lại gọi hàm C, khi hàm C thực hiện xong thì sự điều khiển chương trình sẽ trở về thực hiện chương trình B. Rồi khi hàm B thực hiện xong thì sự điều khiển chương trình sẽ được trả về cho A. Khi đó ta thấy là hàm C được gọi sau cùng và chúng được thực hiện xong trước tiên rồi mới đến B và A. Đây là dạng thực hiện sau và kết thúc trước. Hình 5.4: Minh họa xử lý gọi hàm trong trình biên dịch Lưu trữ dữ liệu để giải các bài toán lý thuyết đồ thị. Ví dụ như tìm chu trình Euler, tìm đường đi... Ngoài ra, stack còn được sử dụng để khử một số bài toán đệ quy. Còn rất nhiều ứng dụng của Stack... Các ví dụ minh họa Chương trình xuất chuỗi ký tự theo thứ tự ngược lại Sử dụng stack chứa dữ liệu là các ký tự, khi đó ta sẽ push lần lượt các ký tự của chuỗi vào stack và sau đó lấy (Pop) lần lượt các ký tự này ra. Kết quả là chuỗi được xuất dưới dạng đảo ngược lại. #include "stdio.h" #include "conio.h" #include "string.h" #define TRUE 1 #define FALSE 0 #define MAX 100 typedef char Data; typedef struct{ int top; Data S[MAX]; } Stack; void Push(Stack & st, Data x); Data Pop(Stack &st); void InitStack(Stack &st); int IsEmpty(Stack st); int IsFull(Stack st); Data Top(Stack st); void Push(Stack & st, Data x) { if (IsFull(st)) printf("\nStack is full!"); else st.S[++st.top] = x; } Data Pop(Stack &st) { if (IsEmpty(st)) printf("\nStack is empty!"); else return (st.S[st.top--]); } void InitStack(Stack &st) { st.top = -1; } int IsEmpty(Stack st) { if (st.top == -1) return TRUE; else return FALSE; } int IsFull(Stack st) { if (st.top >= MAX) return TRUE; else return FALSE; } Data Top(Stack st) { Data d; if (IsEmpty(st)) printf("\n Stack is empty!"); else d = st.S[st.top]; return d; } void main() { char s[MAX]; Stack st; clrscr(); printf("Nhap chuoi: "); gets(s); InitStack(st); for(int i=0; i < strlen(s); i++) Push(st, s[i]); printf("\n Chuoi nguoc lai: "); while (!IsEmpty(st)) printf("%c", Pop(st)); getch(); } Chương trình đổi số sang hệ cơ số bất kỳ. #include "stdio.h" #include "conio.h" #include "string.h" #define MAX 100 #define TRUE 1 #define FALSE 0 typedef unsigned int Data; typedef struct{ int top; Data S[MAX]; } Stack; void Push(Stack & st, Data x); Data Pop(Stack &st); void InitStack(Stack &st); int IsEmpty(Stack st); int IsFull(Stack st); Data Top(Stack st); void Push(Stack & st, Data x) { if (IsFull(st)) printf("\nStack is full!"); else st.S[++st.top] = x; } Data Pop(Stack &st) { if (IsEmpty(st)) printf("\nStack is empty!"); else return (st.S[st.top--]); } void InitStack(Stack &st) { st.top = -1; } int IsEmpty(Stack st) { if (st.top == -1) return TRUE; else return FALSE; } int IsFull(Stack st) { if (st.top >= MAX) return TRUE; else return FALSE; } Data Top(stack st) { Data d; if (IsEmpty(st)) printf("\n Stack is empty!"); else d = st.S[st.top]; return d; } void main() { char s[MAX]; int coso, so, du; stack st; clrscr(); printf("Nhap co so can doi: "); scanf("%d", &coso); printf("Nhap so:"); scanf("%d",&so); InitStack(st); while (so != 0) { du = so % coso; Push(st, du); so = so/coso; } printf("\n Co so : "); while (!IsEmpty(st)) printf("%3X", Pop(st)); getch(); } Bài toán tháp Hanoi Bài toán tháp Hanoi thường được giải bằng phương pháp đệ quy, trong chương trước đã trình bày. Tuy nhiên có thể giải bằng cách dùng stack để khử đệ quy. Để thực hiện việc lưu trữ tạm trong quá trình di chuyển chúng ta dùng một stack. Trong đó mỗi phần tử của stack này chứa các thông tin gồm: số đĩa di chuyển (N), cột nguồn bắt đầu di chuyển (Nguon) và cột đích là nơi cần di chuyển đến (Dich). Ở đây không cần lưu cột trung gian vì có 3 cột đánh số là 1, 2 và 3 thì cột trung gian để di chuyển là: 6 – (Nguon+Dich). Đầu tiên đưa vào stack thông tin di chuyển {n, 1, 2}, tức là di chuyển n đĩa từ cột 1 sang cột thứ 2 qua cột trung gian là 6-(1+2) = 3. Tại mỗi bước khi lấy trong stack ra một phần tử, thực hiện như sau: Nếu N = 1: Þ di chuyển đĩa từ cột Nguon Þ cột Dich Ngược lại (nếu N > 1): Xác định cột trung gian TrungGian = 6 – (Nguon+Dich) Push Þ stack thông tin di chuyển {N-1, TrungGian, Dich} Push Þ stack thông tin di chuyển {1, Nguon, Dich} Push Þ stack thông tin di chuyển {N-1, Nguon, TrungGian} Quá trình còn thực hiện khi stack khác rỗng. Nhận xét: lưu ý thứ tự khi đưa vào thông tin di chuyển vào stack. Trong phần trên thông tin {N-1, Nguon, TrungGian} được đưa vào stack sau cùng nên chúng sẽ được lấy ra trước tiên, kế đến là thông tin di chuyển {1, Nguon, Dich} và cuối cùng là thông tin di chuyển {N-1, TrungGian, Dich}. Chương trình minh họa: #include "stdio.h" #include "conio.h" #define MAX 100 #define TRUE 1 #define FALSE 0 typedef struct { int N; // số đĩa cần di chuyển int Nguon; // cột bắt đầu di chuyển int Dich; // cột đích đến } Data; typedef struct{ int top; Data S[MAX]; } stack; void Push(stack & st, Data x); Data Pop(stack &st); void InitStack(stack &st); int IsEmpty(stack st); int IsFull(stack st); Data Top(stack st); void Push(stack & st, Data x) { if (IsFull(st)) printf("\nStack full!"); else st.S[++st.top] = x; } Data Pop(stack &st) { if (IsEmpty(st)) printf("\nStack empty!"); else return (st.S[st.top--]); } void InitStack(stack &st) { st.top = -1; } int IsEmpty(stack st) { if (st.top == -1) return TRUE; else return FALSE; } int IsFull(stack st) { if (st.top >= MAX) return TRUE; else return FALSE; } Data Top(stack st) { Data d; if (IsEmpty(st)) printf("\n Stack is empty!"); else d = st.S[st.top]; return d; } void Hanoi(int n) { stack st; // stack chứa thông tin di chuyển InitStack(st); // khởi tạo stack Data d,d1,d2,d3; // các biến tạm chứa thông tin di chuyển. int TrungGian; // cột trung gian // đưa thông tin ban đầu vào stack {n, 1, 2} : di chuyển n đĩa từ cột 1 đến 2 d.N = n; d.Nguon = 1; d.Dich = 2; Push(st, d); // đưa vào stack while (!IsEmpty(st)) // lặp khi stack còn phần tử { d = Pop(st); // lấy một phần tử đầu stack ra thực hiện if (d.N == 1) // nếu chỉ có một đĩa thì di chuyển Nguồn ® Đích printf("\nDi chuyen: %d -> %d", d.Nguon, d.Dich); else // nhiều hơn một đĩa { TrungGian = 6 - (d.Nguon+d.Dich); // lấy cột Trung gian /* Đưa vào stack theo thứ tự ngược lại. Tức là đưa vào thông tin: di chuyển N-1 đĩa từ cọc trung gian đến cọc đích, di chuyển 1 đĩa từ nguồn sang đích, và cuối cùng đưa N-1 đĩa từ cọc nguồn sang trung gian. Khi đó lấy từ stack ra chúng ta sẽ có thứ tự ngược lại là: di chuyển N-1 đĩa từ cọc nguồn sang trung gian, di chuyển 1 đĩa từ cọc nguồn sang đích và cuối cùng di chuyển N-1 đĩa từ cọc trung gian sang đích. Đây chính là thứ tự mà chúng ta cần thực hiện chuyển N đĩa từ cọc nguồn sang đích. */ // đưa thông tin di chuyển N-1 đĩa từ Trung gian ® Đích d1.N = d.N-1; d1.Nguon = TrungGian; d1.Dich = d.Dich; Push(st,d1); // đưa thông tin di chuyển 1 đĩa từ Nguồn ® Đích d2.N = 1; d2.Nguon = d.Nguon; d2.Dich = d.Dich; Push(st, d2); // đưa thông tin di chuyển N-1 đĩa từ Nguồn ® Trung gian d3.N = d.N -1; d3.Nguon = d.Nguon; d3.Dich = TrungGian; Push(st,d3); } } // end while stack Æ } // end Hanoi int main() { int n; clrscr(); printf("Nhap vao so cot: "); scanf("%d",&n); Hanoi(n); getch(); return 0; } Thuật toán QuickSort sử dụng stack Như chúng ta đã biết thì thuật toán QuickSort thường được cài đặt bằng giải thuật đệ quy. Tuy nhiên một cách khác là dùng cấu trúc dữ liệu stack để cài đặt cũng tốt. Cách thực hiện là tạo một cấu trúc stack để lưu trữ hai biên trái và phải của một đoạn. Ví dụ như khi phân đoạn left đến right, chúng ta được ba đoạn là [left...i] là các phần tử nhỏ hơn x, đoạn [i+1..j-1] là các phần tử bằng x, và đoạn cuối là [j...right]. Khi đó chúng ta sẽ đưa vào stack đoạn bên phải, nếu đoạn bên trái nhiều hơn một phần tử ta cập nhật lại right = i, khi đó chúng ta sẽ lặp lại với đoạn [left...i] một cách tương tự, khi đoạn bên trái hết thì chúng ta sẽ lấy từ trong stack ra những đoạn được lưu giữ để thực hiện tiếp tục...quá trình thực hiện cho đến khi stack rỗng. #include "stdio.h" #include "conio.h" #include "stdlib.h" #define TRUE 1 #define FALSE 0 #define MAX 100 typedef struct { int left; int right; } Data; typedef struct{ int top; Data S[MAX]; } stack; void Push(stack & st, Data x); Data Pop(stack &st); void InitStack(stack &st); int IsEmpty(stack st); int IsFull(stack st); Data Top(stack st); void Swap(int &a, int &b) { int tmp =a; a = b; b = tmp; } void Push(stack & st, Data x) { if (IsFull(st)) printf("\nStack is full!"); else st.S[++st.top] = x; } Data Pop(stack &st) { if (IsEmpty(st)) printf("\nStack is empty!"); else return (st.S[st.top--]); } void InitStack(stack &st) { st.top = -1; } int IsEmpty(stack st) { if (st.top == -1) return TRUE; else return FALSE; } int IsFull(stack st) { if (st.top >= MAX) return TRUE; else return FALSE; } Data Top(stack st) { Data d; if (IsEmpty(st)) printf("\n Stack is empty!"); else d = st.S[st.top]; return d; } void QuickSort(int a[MAX], int n) { int i, j, l, r; int x; l = 0; r = n-1; stack st; InitStack(st); while (l < r ) { x = a[(l+r)/2]; i = l; j = r; do{ while (a[i] < x) i++; while (a[j] > x) j--; if ( i <= j) { Swap(a[i], a[j]); i++; j--; } } while (i<j); if (r > i) { Data d; d.left = i; d.right = r; Push(st,d); } if (l < j) { r = j; } else if (!IsEmpty(st)) { Data d = Pop(st); l = d.left; r = d.right; } else break; // thoat khoi vong lap -> while (l < r) } } void main() { int a[MAX] ; int n = 30; clrscr(); randomize(); printf("Mang truoc khi sap: \n"); for(int i=0; i < n;i++) { a[i] = random(100); printf("%4d", a[i]); } QuickSort(a,n); printf("\nMang sau khi sap:\n"); for(i=0; i <n; i++) printf("%4d",a[i]); getch(); } Bài toán chuyển biểu thức trung tố sang hậu tố. Như chúng ta đã biết một biểu thức được biểu diễn dưới dạng hậu tố hay còn gọi là ký pháp nghịch đảo Ba Lan RPN (Reverse Polish Notation) giúp ích rất nhiều cho việc tính toán giá trị biểu thức tốt hơn là biểu thức dạng trung tố. Các trình biên dịch máy tính thường chuyển những biểu thức trung tố sang hậu tố để dễ xử lý hơn. Trong phần này chúng ta sẽ tìm hiểu thuật toán để chuyển một biểu thức dạng trung tố đơn giản sang biểu thức hậu tố tương ứng. Ví dụ một biểu thức trung tố như sau: (6 / 2 + 3) * (7 - 4) được chuyển thành biểu thức hậu tố như sau: 6 2 / 3 + 7 4 - *. Chúng ta có thể thấy cách biểu diễn của trung tố cần phải xử lý dấu ngoặc trong khi biểu thức hậu tố thì không cần sử dụng. Đây là ưu điểm của biểu thức hậu tố. Để chuyển đổi chúng ta sử dụng một Stack dùng lưu trữ các toán tử và dấu ngoặc mở. Ngoài ra cũng quy định độ ưu tiên của các toán tử thông qua hàm Priority, trong đó phép toán *, / có độ ưu tiên cao nhất là 2, phép toán +, - có độ ưu tiên ít hơn là 1, và cuối cùng dấu ngoặc mở ‘(’ là 0. Ý tưởng của thuật toán: Duyệt qua từng phần tử trong biểu thức trung tố, gọi C là phần tử đang xét: Nếu C là ‘(’ thì push vào stack Nếu C là ‘)’ thì lấy trong stack ra cho đến khi gặp ‘(‘: xuất ra những phần tử này. Nếu C là toán tử ‘+’,’-‘,’*’,’/’: Lấy trong stack ra tất cả những toán tử có độ ưu tiên cao hơn C, xuất những phần tử này ra ngoài. Sau đó đưa C vào stack. Cuối cùng lấy tất cả những phần tử còn lại trong stack xuất ra ngoài. Thuật toán chuyển đổi từ trung tố sang hậu tố: Stack = {Æ}; // khởi tạo stack rỗng for do { if ( C == ‘(‘ ) Push(Stack, C); // đưa vào stack else if ( C== ‘)’) { do { x = Pop(Stack); // lấy từ stack ra cho đến khi gặp ‘(‘ if (c != ‘(‘) printf(“%c”, x); } while ( x!= ‘(‘) } else if (C == ‘+’ || C ==’-‘ || C == ‘*’ || C==’/’) { while ( !IsEmpty(Stack) && Priority(C) <= Priority(Top(Stack))) printf(“%c”, Pop(Stack)); // nếu độ ưu tiên toán tử trong // stack lớn hơn thì lấy ra. Push(Stack, C); // đưa toán tử mới vào stack } else // toán hạng printf(“%c”,C); } while ( !IsEmpty(Stack)) // lặp để lấy tất cả các phần tử trong stack ra printf(“%c”, Pop(Stack)); Ví dụ khi thực hiện với biểu thức trung tố: (2 * 3 + 7 / 8) * (5 – 1) Đọc Xử lý Stack Output ( Đẩy vào stack ( 2 Xuất ( 2 * Do ‘*’ ưu tiên hơn ‘(‘ ở đỉnh stack nên đưa ‘*’ vào stack ( * 2 3 Xuất ( * 2 3 + Do ‘+’ ưu tiên thấp hơn ‘*’ ở đỉnh stack nên ta lấy ‘*’ ra. Tiếp tục so sánh ‘+’ với ‘(‘ thì ‘+’ ưu tiên cao hơn nên đưa vào stack ( + 2 3 * 7 Xuất ( + 2 3 * 7 / Do ‘/’ có độ ưu tiên cao hơn ‘+’ trên đỉnh stack nên đưa ‘/’ vào stack. ( + / 2 3 * 7 8 Xuất ( + / 2 3 * 7 8 ) Lấy trong stack ra cho đến khi gặp ngoặc (. 2 3 * 7 8 / + * Đưa vào stack * 2 3 * 7 8 / + ( Đưa vào stack * ( 2 3 * 7 8 / + 5 Xuất * ( 2 3 * 7 8 / + 5 - Độ ưu tiên của ‘-‘ cao hơn ‘(‘ trong đỉnh stack nên đưa ‘-‘ vào stack * ( - 2 3 * 7 8 / + 5 1 Xuất * ( - 2 3 * 7 8 / + 5 1 ) Lấy trong stack ra cho đến khi gặp ngoặc đóng * 2 3 * 7 8 / + 5 1 - Lấy những phần tử còn lại trong stack và hiển thị 2 3 * 7 8 / + 5 1 - * Bài toán tính giá trị biểu thức hậu tố. Trong những năm đầu 1950 nhà logic học người Ba Lan Jan Lukasiewicz đã chứng minh rằng: biểu thức hậu tố không cần có dấu ngoặc vẫn có thể tính đúng bằng cách đọc lần lượt biểu thức từ trái qua phải và dùng một stack để lưu trữ kết quả trung gian. Các bước thực hiện như sau: Bước 1: Khởi tạo một stack = {Æ} Bước 2: Đọc lần lượt các phần tử của biểu thức hậu tố từ trái sang phải, với mỗi phần tử đó thực hiện kiểm tra: Nếu phần tử này là toán hạng thì đẩy nó vào stack Nếu phần tử này là toán tử thì ta lấy hai toán hạng trong stack ra và thực hiện phép toán với hai toán hạng đó. Kết quả tính được sẽ được lưu vào trong stack. Bước 3: Sau khi kết thúc bước hai thì toàn bộ biểu thức đã được đọc xong, trong stack chỉ còn duy nhất một phần tử, phần tử đó chính là giá trị của biểu thức. Ví dụ: tính giá trị biểu thức 10 2 / 3 + 7 4 - *, có biểu thức trung tố là: (10/2 + 3)*(7-4), ta có các bước thực hiện như sau: Đọc Xử lý Stack Output 10 Đưa vào stack 10 2 Đưa vào stack 10 2 / Lấy hai phần tử đầu stack là 2, 10 và thực hiện phép toán 10/2 = 5. Sau đó lưu kết quả 5 vào stack 5 3 Đưa 3 vào stack 5 3 + Lấy hai giá trị 3, 5 ra khỏi stack, thực hiện phép cộng của hai số đó, kết quả là 8 được đưa vào lại stack 8 7 Đưa 7 vào stack 8 7 4 Đưa 4 vào stack 8 7 4 - Lấy hai giá trị 4, 7 ra khỏi stack, thực hiện phép tính 7 – 4 = 3, kết quả 3 được đưa vào lại stack 8 3 * Lấy hai giá trị 3, 8 ra khỏi stack, thực hiện phép tính 8 * 3 = 24, lưu kết quả vào stack 24 Lấy kết quả từ stack Þ đây chính là kết quả của biểu thức. 24 Giới thiệu Queue – hàng đợi Hàng đợi Queue là kiểu danh sách với hai phép toán cơ bản là bổ sung một phần tử vào cuối danh sách (Rear) và loại bỏ một phần tử ở đầu danh sách (Front). Nói tóm lại là hai thao tác cơ bản đưa vào một phần tử và lấy ra một phần tử ở hai đầu của danh sách. Thêm vào (Insert) Danh sách hàng đợi làm việc theo cơ chế FIFO (First In First Out), nghĩa là việc thêm một phần tử vào hàng đợi hay lấy một phần tử từ hàng đợi ra ngoài theo thứ tự “Vào trước ra trước”. Lấy ra (Remove) Queue Cuối Queue (Rear) Đầu Queue (Front) Hình 5.5: Minh họa hàng đợi Queue. Hai thao tác chính trên hàng đợi: Thao tác Insert: thêm một phần tử vào cuối danh sách. Thao tác Remove: xoá một phần tử ở đầu danh sách. Ví dụ: Cho hàng đợi Q và các thao tác như sau: Hàng đợi ban đầu có hai phần tử A và B hình 5.6 Thêm một phần tử C vào cuối Queue: Insert(Q, C) hình 5.7 Lấy một phần tử ở đầu Queue: Remove(Q) hình 5.8 Thêm một phần tử D vào cuối Queue: Insert(Q, D) hình 5.9 Lấy một phần tử ở đầu Queue: Remove(Q) hình 5.10 A B Front Rear A B C Rear Front B C Rear Front B C D Rear Front C D Rear Front Hình 5.6: Hàng đợi có hai phần tử A và B. Hình 5.7: Hàng đợi sau khi thêm phần tử C vào cuối. Hình 5.8: Hàng đợi sau khi lấy phần tử ở đầu. Hình 5.9: Hàng đợi sau khi thêm phần tử D vào cuối. Hình 5.10: Hàng đợi sau khi lấy phần tử ở đầu. Cài đặt Queue dùng CTDL mảng Để sử dụng cấu trúc dữ liệu mảng mô tả Queue người ta dùng hai chỉ số là Front và Rear để đánh dấu vị trí đầu và cuối của hàng đợi trong mảng. Nếu mảng tính từ chỉ số 0 thì ban đầu chúng ta khởi tạo Rear = -1 và Front = 0. Để thêm một phần tử vào Queue, ta tăng Rear lên 1 và đưa nó vào phần tử thứ Rear. Để loại một phần tử khỏi Queue, ta lấy giá trị ở vị trí Front và tăng chỉ số này lên 1. Khi Rear tăng lên hết khoảng chỉ số của mảng thì mảng đầy, khi đó ta không thể thêm vào mảng được nữa. Khi Front > Rear Þ Queue = {Æ}. Tương tự như phần Stack ở đây sẽ xây dựng một cấu trúc Queue chứa các phần tử có kiểu dữ liệu là Data, Data là kiểu dữ liệu do người dùng định nghĩa có thể số nguyên, thực, ký tự hoặc một cấu trúc dữ liệu nào đó tùy ý. Khai báo cấu trúc Queue dùng mảng: #define MAX 100 typedef struct { int Front; // chỉ đến vị trí đầu của queue int Rear; // chỉ đến vị trí cuối của queue Data Q[MAX]; // mảng dữ liệu cần lưu trữ } Queue; Trong cấu trúc này trường Front chỉ đến vị trí đầu của Queue còn Rear chỉ đến vị trí cuối của Queue. Ban đầu khi Queue được khởi tạo rỗng thì Rear = -1 và Front = 0. Các thao tác trên cấu trúc Queue: void Insert(Queue &queue, Data x): Đưa phần tử x vào cuối Queue Data Remove(Queue &queue): Lấy một phần tử ở đầu Queue int IsEmpty(Queue queue): Kiểm tra xem Queue có rỗng hay không int IsFull(Queue queue): Kiểm tra xem Queue đầy hay không. void InitQueue(Queue &queue): Khởi tạo Queue. Phần cài đặt các thao tác trên Queue: #define TRUE 1 #define FALSE 0 void Insert(Queue &queue, Data x) { queue.Rear++; // tăng Rear lên 1 if (IsFull(queue)) printf(“Queue full!”); else queue.Q[queue.Rear] = x; } Data Remove(Queue &queue) { Data x; if (IsEmpty(queue)) printf(“Queue empty!”); else x = queue.Q[queue.Front++]; return x; } int IsEmpty(Queue queue) { if (queue.Front > queue.Rear) return TRUE; return FALSE; } int IsFull(Queue queue) { if (queue.Rear == MAX) return TRUE; return FALSE; } void InitQueue(Queue &queue) { queue.Rear = -1; queue.Front = 0; } Các ứng dụng Queue Thông thường các vấn đề liên quan đến cơ chế “vào trước ra trước” đều có thể dùng cấu trúc dữ liệu Queue. Ví dụ như cơ chế sản xuất và tiêu thụ, hàng hóa sản xuất trước được đưa vào kho và sẽ được xuất ra trước. Các ứng dụng đặt vé tàu lửa máy bay, hệ thống rút tiền...Ngoài ra hàng đợi còn được dùng nhiều trong hệ điều hành: bộ đệm ứng dụng, hàng đợi xử lý các sự kiện, hàng đợi xử lý phím nhấn, tiến trình... Bài toán quản lý kho hàng: Đây là dạng bài toán sản xuất & tiêu dùng, mặt hàng được sản xuất ra sẽ được lưu vào kho, hàng hóa từ kho này sẽ được xuất ra ngoài cho nhà phân phối. Khi đó những mặt hàng nào đưa vào kho trước tiên sẽ ra được xuất kho trước. Đây là dạng FIFO nên chúng ta có thể dùng cấu trúc dữ liệu Queue để minh họa cho nó. #include "stdio.h" #include "conio.h" #define MAX 100 #define TRUE 1 #define FALSE 0 typedef struct { char MaSP[10]; // Ma san pham char TenSP[50]; // Ten san pham } Data; typedef struct { int Rear, Front; Data Q[MAX]; }Queue; void Insert(Queue &queue, Data x); Data Remove(Queue &queue); int IsEmpty(Queue queue); int IsFull(Queue queue); void InitQueue(Queue &queue); void Insert(Queue &queue, Data x) { queue.Rear++; // tăng Rear lên 1 if (IsFull(queue)) printf("Queue full!"); else queue.Q[queue.Rear] = x; } Data Remove(Queue &queue) { Data x; if (IsEmpty(queue)) printf("Queue empty!"); else x = queue.Q[queue.Front++]; return x; } int IsEmpty(Queue queue) { if (queue.Front > queue.Rear) return TRUE; return FALSE; } int IsFull(Queue queue) { if (queue.Rear == MAX) return TRUE; return FALSE; } void InitQueue(Queue &queue) { queue.Rear = -1; queue.Front = 0; } Data InputProduct() // đọc một sản phẩm { Data sp; printf("\nMa san pham: "); scanf("%s",sp.MaSP); printf("Ten san pham: "); scanf("%s", sp.TenSP); return sp; } void OutputProduct(Data sp) // xuất một sản phẩm { printf("\nSan pham : MaSP: %s, TenSP: %s", sp.MaSP, sp.TenSP); } void ListProducts(Queue q) // liệt kê những sản phẩm trong kho { if (!IsEmpty(q)) // nếu có sản phẩm trong kho { printf("\n Danh sach san pham trong kho:\n"); for(int i= q.Front; i <= q.Rear; i++) // duyệt qua các phần tử { printf("\nSan pham: MaSP: %s, TenSP: %s",q.Q[i].MaSP, q.Q[i].TenSP); } } } int main() { Queue queue; InitQueue(queue); // khởi tạo hàng đợi clrscr(); int i; do { clrscr(); printf("CHUONG TRINH MINH HOA QUAN LY KHO\n"); printf("-----------------------------------------------\n"); printf("1. Them san pham vao kho.\n"); printf("2. Xuat san pham ra khoi kho.\n"); printf("3. Xem san pham chuan bi xuat kho.\n"); printf("4. Xem tat ca hang hoa trong kho. \n"); printf("5. Thoat.\n"); printf("Chon chuc nang: (1- 5): "); scanf("%d",&i); switch (i) { case 1: Insert(queue, InputProduct()); // thêm sp vào kho break; case 2: OutputProduct(Remove(queue)); // lấy sp khỏi kho break; case 3: if (!IsEmpty(queue)) // xem sp sắp lấy OutputProduct(queue.Q[queue.Front]); break; case 4: // xem tất cả sp ListProducts(queue); break; } getch(); } while (i != 5); return 0; } Duyệt cây theo chiều rộng trong đồ thị: Đây là phương pháp duyệt hay tìm kiếm phổ biến trên đồ thị. Việc duyệt một đỉnh v sẽ cho phép chúng ta đi duyệt tiếp với những đỉnh kề của nó sao cho thỏa thứ tự ưu tiên theo chiều rộng, tức là đỉnh nào gần với v nhất sẽ được duyệt trước. Hình 5.11: Minh họa thứ tự duyệt theo chiều rộng. Khi đó tại mỗi bước xét một đỉnh v ta có một danh sách các đỉnh kề của nó, những đỉnh này chờ được duyệt do đó ta sẽ đưa những đỉnh này vào cuối danh sách chờ được duyệt, khi đó những đỉnh nào vào danh sách chờ trước thì sẽ được duyệt trước. Với cấu trúc dữ liệu này thì thích hợp cho việc sử dụng Queue. Thuật toán: Breadth First Search void BFS(int v) // thủ tục duyệt theo chiều rộng từ một đỉnh v { Queue QList; InitQueue(QList); // khởi tạo hàng đợi Insert(QList, v); // đưa v vào hàng đợi Xet[v] = TRUE; // đánh dấu v đã duyệt while (IsEmpty(QList) == 0) { p = Remove(QList); // lấy đỉnh trong hàng đợi Visit(p); // thăm đỉnh p, có thể xuất đỉnh ra ... for( i=1; i <= n; i++) // duyệt qua các đỉnh if ( A[v][i] == 1 && Xet[i] == FALSE) // nếu i là đỉnh kề v và chưa xét { Insert(QList, i); // đưa vào hàng đợi Xet[i] = TRUE; // đánh dấu i đã xét. } } } Mảng A[][]: chứa ma trận kề của đồ thị (G) Mảng Xet[]: đánh dấu một đỉnh v đã được duyệt hay chưa; 1: đã duyệt, 0: chưa duyệt. Tất cả các phần tử của mảng Xet[] ban đầu được khởi tạo là 0. Chương trình minh họa duyệt theo chiều rộng: #include "stdio.h" #include "conio.h" #define MAX 100 #define TRUE 1 #define FALSE 0 typedef int Data; typedef struct { int Rear, Front; Data Q[MAX]; } Queue; void Insert(Queue &queue, Data x); Data Remove(Queue &queue); int IsEmpty(Queue queue); int IsFull(Queue queue); void InitQueue(Queue &queue); void Insert(Queue &queue, Data x) { queue.Rear++; // tăng Rear lên 1 if (IsFull(queue)) printf("Queue full!"); else queue.Q[queue.Rear] = x; } Data Remove(Queue &queue) { Data x; if (IsEmpty(queue)) printf("Queue empty!"); else x = queue.Q[queue.Front++]; return x; } int IsEmpty(Queue queue) { if (queue.Front > queue.Rear) return TRUE; return FALSE; } int IsFull(Queue queue) { if (queue.Rear == MAX) return TRUE; return FALSE; } void InitQueue(Queue &queue) { queue.Rear = -1; queue.Front = 0; } void BFS(int v, int a[][MAX], int xet[], int n) { int d; Queue queue; InitQueue(queue); Insert(queue, v); xet[v] = TRUE; while (!IsEmpty(queue)) { d = Remove(queue); printf("%d\t", d); for(int i=1; i <= n; i++) if (a[d][i]== 1 && xet[i]== FALSE) { Insert(queue, i); xet[i] = TRUE; } } } int main() { int a[MAX][MAX], xet[MAX], n; clrscr(); char name[50]; printf(“Nhap ten file ma tran ke cua (G): ”); gets(name); FILE * f = fopen(name,"r"); if (f == NULL) { printf("Loi doc file!"); return 1; } fscanf(f,"%d",&n); for(int i=1; i <= n;i++) for(int j=1; j <= n; j++) fscanf(f,"%d",&a[i][j]); // danh dau cac dinh chua xet for(i =1; i <= n; i++) xet[i] = FALSE; // duyet qua cac dinh cua do thi printf("Cac dinh cua do thi duoc duyet theo chieu rong\n"); for(i =1; i <= n; i++) if (xet[i] == FALSE) BFS(i, a, xet, n); getch(); return 0; } Tập tin ma trận kề có dạng sau: N A[1][1]… A[1][N] … A[N][1]… A[N][N] Trong đó A[i][j] = 1 nếu (i, j) có cạnh nối và ngược lại A[i][j] = 0 nếu không có cạnh nối Ví dụ tập tin ma trận kề minh họa đồ thị có 5 đỉnh. 5 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 ›¯š BÀI TẬP Tinh chỉnh lại đoạn chương trình sau: … for (int i=0; i < n; i++) { if ( flag) b[i] = 0; a[i] = a[i] + b[i]; c[i] = a[i] + 2*b[i]; } … Tinh chỉnh lại đoạn chương trình sau: ... while ( sqrt( i*i) < sqrt (a*a) ) { // đoạn chương trình …. i++; } Tinh chỉnh lại đoạn chương trình sau: ... flag = FALSE; k =0; while ( k < n) { if (a[i] == x) flag = TRUE; k++; } if (flag) printf("Tim thay phan tu!"); … Tinh chỉnh lại đoạn chương trình sau: ... while ( i < n) { d = sqrt (a+b)*i; printf("gia tri %.2f", d); i++; } ... Tinh chỉnh lại đoạn chương trình sau: ... for(int i=0; i < strlen(strBuff); i++) { …. } Tinh chỉnh lại đoạn chương trình sau: if (a==0 && b==0 && c==0) Function1(); else if (a==0 && b==0) Function2(); else if (a==0) Function3(); else Function4(); Tối ưu lại đoạn chương trình sau: char S1[MAX], S2[MAX]; …. int i; for (i=0;i<strlen(S1); i++) { if ( i<strlen(S1)/3 && S1[i] < ’M’ ) S2[i]= S1[i]+2; else if ( i < strlen(S1)/2 && S[i] < ‘X’) S2[i] = S1[i] +3; else S2[i]= S1[i]; } Tinh chỉnh đoạn chương trình sau … if (strcmp(s1, s2)==0) printf(“equal”); else if (strcmp(s1, s2) >0) printf(“greater than”); else printf(“less than”); … Tinh chỉnh lại đoạn chương trình sau: … x1 = (-b + sqrt(b*b-4*a*c))/(2*a); x2 = (-b - sqrt(b*b-4*a*c))/(2*a); … Viết chương trình với giao diện đồ hoạ minh họa cho bài toán tháp Hanoi. Chương trình thể hiện từng bước sự chuyển các đĩa. Cho phép nhập vào số n và thời gian di chuyển từng đĩa. Viết hàm đệ quy tìm phần tử lớn nhất và nhỏ nhất trong mảng nguyên. Viết hàm đệ quy tính tổng các phần tử trong mảng các số nguyên. Viết chương trình tìm kiếm giá trị x trên ma trận vuông các số nguyên, dùng đệ quy để tìm kiếm. Viết chương trình chuyển đổi cơ số từ hệ thập phân sang hệ k, yêu cầu dùng hàm đệ quy để giải. Viết chương trình tháp Hanoi không dùng đệ quy. Viết chương trình chuyển đổi số từ cơ số thập phân sang cơ số k bất kỳ, không dùng đệ quy. Viết chương trình liệt kê chuỗi nhị phân n bit. Dùng phương pháp sinh. Cho tập các số tự nhiên {1, 2, .., n}, viết chương trình liệt kê tập con k phần tử. Dùng phương pháp sinh. Viết chương trình liệt kê hoán vị n phần tử. Dùng phương pháp sinh. Nhập vào một chuỗi ký tự S, hãy liệt kê các hoán vị ký tự của chuỗi S. Ví dụ: chuỗi S nhập vào là "abc" thì kết quả là abc, acb, bac, bca, cab, cba. Tương tự như bài 1, liệt kê tổ hợp chập k ký tự của chuỗi S. Một hoán vị hoàn toàn của tập{1, 2, .., n} là dãy hoán vị mà thoả mãn x[i] ¹ i, "i: 1£ i £ n. Viết chương trình nhập vào giá trị n, sau đó xuất ra tất cả hoán vị hoàn toàn của tập {1, 2, .., n}. Viết chương trình nhập vào một số nguyên n, liệt kê tất cả cách chia số tự nhiên n thành tổng các số nhỏ hơn. Ví dụ: n = 4 Kết quả 3 1 2 2 2 1 1 1 1 1 1 Cho một bàn cờ tổng quát có kích thước nxn và quân mã. Viết chương trình cho phép liệt kê ra hành trình của quân mã từ một vị trí (x ,y) đi qua tất cả các ô còn lại của bàn cờ, mỗi ô đi qua một lần. Hình: Các nước đi có thể có của quân mã Cho bàn cờ vua nxn, hãy viết chương trình minh hoạ bàn cờ và cách sắp xếp n quân hậu sao cho các quân hậu không thể ăn lẫn nhau. Hình: Một cách bố trí các quân Hậu. Nhập danh sách tên gồm n người, liệt kê ra tất cả cách chọn k người trong số n người đó. Ví dụ: n =6: {"Nam", "Hung", "Viet", "Hoa", "Lan", "Tien"}, Kết quả: k = 2 {"Nam", "Hung"}, {"Nam", "Viet"}, {"Nam", "Hoa"}…. Nhập danh sách tên gồm n người, xuất ra các cách xếp n người đó vào trong một bàn tròn. Nhập vào danh sách n bạn nam và n bạn nữ, hãy xuất ra danh sách cách xếp 2n bạn đó vào một bàn tròn trong đó có sự xen lẫn giữa nam và nữ. Viết chương trình liệt kê tất cả hoán vị của từ “HUTECH” Viết chương trình liệt kê tất cả hoán vị chữ cái trong từ "MISSISSIPPI" Viết chương trình mô phỏng từng bước thực hiện của các thuật toán sắp xếp sau: Phương pháp chọn Phương pháp nổi bọt Phương pháp chèn Phương pháp đổi chỗ trực tiếp Phương pháp ShellSort Phương pháp phân đoạn Phương pháp cơ số Cho một mảng nguyên n >100 phần tử, các phần tử phát sinh ngẫu nhiên. Viết hàm tìm kiếm một phần tử trong mảng. Tương tự như bài tập bên trên, nhưng hàm tìm kiếm theo dạng nhị phân. Sinh viên có thể dùng một trong các phương pháp sắp xếp để sắp xếp lại mảng trước khi thực hiện tìm kiếm nhị phân. Viết chương trình đo thời gian thực hiện của các thuật toán sắp xếp bên trên. Chương trình phát sinh ngẫu nhiên bộ dữ liệu test (mảng số nguyên, có kích thước n >= 1000) , cho các thuật toán lần lượt chạy và ghi nhận lại thời gian thực hiện. Viết chương trình không đệ quy cho thuật giải Quicksort, (áp dụng stack để khử đệ quy). Nhập vào một biểu thức trung tố, chuyển đổi thành biểu thực hậu tố và tính giá trị của biểu thức. Lưu ý: toán hạng có thể nhiều hơn một con số hay số thực. Sinh viên mở rộng với các toán tử khác... Ví dụ: (20+5)*3+(10/5) => 20 5 + 3 * 10 5 / + Kết quả: 77 Viết chương trình mô phỏng hàng đợi mua vé xem phim. Thông tin của việc đăng ký gồm: họ tên, địa chỉ, tuổi và số ghế... Viết chương trình mô phỏng hàng đợi mua vé xe lửa. Viết chương trình sắp xếp theo cơ số (RadixSort), trong đó sử dụng cấu trúc dữ liệu queue để lưu tạm trong quá trình sắp xếp. Hướng dẫn sử dụng 10 hàng đợi để lưu tạm các con số. Gồm hàng đợi 0 đến 9, khi đó hàng đợi 0 sẽ chỉ lưu những con số có số 0 ở các bước phân hàng đơn vị, hàng chục, hàng trăm tương ứng... ›¯š TÀI LIỆU THAM KHẢO Brian W. Kernighan, Rob Pike, The Practice of Programming, Addison Wesley, 1999. Ellis Horowitz, Sartaj Sahni, Fundamentals of Data Structures, ebook, 1981. R. Neapolitan, K. Naimipour , Foundations of Algorithms Using C++ Pseudocode, Jones and Bartlett Publishers , 2004. Lê Hoài Bắc, Nguyễn Thanh Nghị, Kỹ năng lập trình, NXB KHKT, 2005. Trần Hoàng Thọ, Giáo trình Kỹ thuật Lập trình Nâng cao, ĐH Đà Lạt, 2002. Dương Anh Đức, Trần Hạnh Nhi, Nhập môn Cấu trúc dữ liệu và thuật toán, ĐH KHTN, 2000. 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. Lê Minh Hoàng, Giải thuật và lập trình, NXB ĐH Sư Phạm HN, 1999- 2002 ›¯š