Đồ án Xây dựng chương trình hỗ trợ giảng dạy môn học cấu trúc dữ liệu và giải thuật

(2). Lặp lại các bước dưới cho đến khi dấu kết thúc biểu thức được đọc: (a). Đọc phần tử (token - hằng số, biến số, toán tử số học ) tiếp theo trong biểu thức RPN. (b). Nếu phần tử này là một toán hạng, đẩy nó vào ngăn xếp. Nếu nó là toán tử, thực hiện các bước sau: (i). Lấy ra từ đỉnh ngăn xếp hai giá trị ( nếu ngăn xếp không chứa hai phần tử, xảy ra lỗi biểu thức không đúng dạng RPN, và thuật toán kết thúc) . (ii). Áp dụng toán tử trên vào hai giá trị vừa lấy ra. (iii). Đẩy giá trị kết quả vào ngăn xếp. (3). Khi gặp dấu kết thúc biểu thức, giá trị của nó là giá trị ở đỉnh của ngăn xếp (và nó phải là giá trị duy nhất trong ngăn xếp). Chuyển đổi biểu thức trung tố sang dạng hậu tố. Để minh hoạ cách dùng ngăn xếp chuyển đổi từ dạng trung tố sang dạng hậu tố, ta xét biểu thức trung tố sau : 7 + 2 * 3 Khi đọc biểu thức này từ trái sang phải, giá trị 7 có thể được thực hiện ngay lập tức. Tiếp theo là toán tử +, nhưng nó phải được lưu trữ vì toán hạng bên phải của nó chưa được hiển thị, vì vậy nó được đẩy vào ngăn xếp các toán tử. Tiếp theo là toán hạng 2 được đọc và hiển thị. Lúc này nó phải được xác định là toán hạng bên phải của toán tử + hay là toán hạng bên trái của toán tử tiếp theo. Chúng ta xác định điều này bằng cách so sánh toán tử + ở đỉnh của ngăn xếp với toán tử tiếp theo *. Bởi vì * được ưu tiên hơn +, toán hạng 2 là toán hạng bên trái của toán tử *, vì vậy chúng ta đẩy * vào ngăn xếp và tìm toán hạng bên phải của nó. Toán hạng 3 được đọc và hiển thị, bởi vì lúc này ta đạt đến kết thúc biểu thức, toán hạng bên phải của toán tử * ở đỉnh ngăn xếp được tìm ra, toán tử * có thể lấy ra từ ngăn xếp và hiển thị. Dấu kết thúc biểu thức cũng chỉ ra rằng toán hạng bên phải của toán tử còn lại + trong ngăn xếp được tìm ra, vì vậy có thể lấy nó ra khỏi ngăn xếp và hiển thị, ta được biểu thức hậu tố. 7 2 3 * + Mô tả thuật toán thực hiện chuyển đổi từ dạng trung tố sang hậu tố. (1). Khởi động một ngăn xếp rỗng của các toán tử. (2). While (không xảy ra lỗi và chưa đạt đến kết thúc của biểu thức trung tô) làm các bước sau: (a). Đọc Token( hằng số, biến số, toán tử số học, các dấu ngoặc) tiếp theo trong biểu thức trung tố. (b). Nếu phần tử (Token) là (i). Một dấu ngoặc trái : đẩy nó vào ngăn xếp. (ii). Một dấu ngoặc phải : lấy ra và hiển thị các phần tử của ngăn xếp cho đến khi dấu ngoặc trái được đọc.(nếu ngăn xếp là rỗng thì báo lỗi). (iii). Một toán tử : nếu ngăn xếp là rỗng hay Token được ưu tiên hơn phần tử ở đỉnh ngăn xếp, đẩy Token vào ngăn xếp. Nếu khác lấy ra và hiển thị phần tử đỉnh của ngăn xếp; lặp lại việc so sánh Token với phần tử ở đỉnh ngăn xếp. Chú thích : dấu ngoặc trái được xem là có ưu tiên thấp hơn các toán tử. (iv). Một toán hạng : hiển thị nó. (3). Khi đạt đến kết thúc của biểu thức trung tố, lấy ra và hiển thị các phần tử của ngăn xếp cho đến khi ngăn xếp rỗng. Hàng đợi. Khái niệm về hàng đợi. Hàng đợi như là một cấu trúc dữ liệu là một kiểu danh sách đặc biệt trong đó các phép toán cơ bản chèn và xoá được giới hạn ở các điểm cuối của danh sách. Các phần tử của hàng đợi được lấy ra từ một điểm cuối, gọi là đầu của hàng đợi, và được thêm vào tại đầu kia của hàng đợi, gọi là đuôi. Vậy hàng đợi là một cấu trúc “vào trước - ra trước” = ( FIST IN - FIST OUT =FIFO). Các thao tác với hàng đợi. Các phép toán cơ bản của hàng đợi. CreateQ : Tạo một hàng đợi rỗng. EmptyQ : Xác định hàng đợi có rỗng hay không. AddQ : Thêm phần tử mới vào đuôi hàng đợi. FullQ : Kiểm tra hàng đầy. RemoveQ : Tìm và lấy ra phần tử ở đầu hàng đợi. Các giải thuật đệ quy. Khái niệm về đệ quy. Ta nói một đối tượng là đệ quy nếu nó bao gồm chính nó như một bộ phận hoặc nó được định nghĩa dưới dạng của chính nó. Giải thuật đệ quy và thủ tục đệ quy : Nếu lời giải của một bài toán T được thực hiện bằng lời giải của một bài toán T’, có dạng giống như T, thì đó là một lời giải đệ quy. Giải thuật tương ứng với lời giải như vậy gọi là giải thuật đệ quy. Ở đây điểm mấu chốt là T’ tuy có dạng giống T, nhưng theo một nghĩa nào đó nó phải nhỏ hơn T. Các ví dụ về giải thuật đệ quy. Ví dụ : trong toán học ta gặp các định nghĩa đệ quy như sau : Số tự nhiên : (1) 1 là một số tự nhiên. (2) x là số tự nhiên nếu x -1 là số tự nhiên. Hàm n giai thừa : N! (1) 0!=1 (2) Nếu n > 0 thì n!=n(n-1)!. Bài toán tháp Hà Nội. Có n đĩa, kích thước nhỏ dần, đĩa có lỗ ở giữa, có thể xếp chồng chúng lên nhau xuyên qua một cọc, to dưới nhỏ trên để cuối cùng có một chồng đĩa dạng như hình tháp, như sau : Yêu cầu đặt ra là : Chuyển chồng đĩa từ cọc A sang cọc khác, chẳng hạn sang cọc C, theo những điều kiện sau : (1). Mỗi lần chỉ được chuyển một đĩa. (2). Không khi nào có tình huống đĩa to ở trên đĩa nhỏ (dù là tạm thời). (3). Được phép sử dụng một cọc trung gian, ở đây cọc B để đặt tạm đĩa. Tính đúng đắn của các giải thuật đệ quy. Để chứng minh tính đúng đắn của một thuật toán, chúng ta phải chứng minh rằng thuật toán sẽ kết thúc và cho ra kết quả đúng. Ta dùng quy nạp. Tính đúng đắn của giải thuật FACTORIAL hàm N!. Ta muốn chứng minh rằng thủ tục hàm FACTORIAL(n) sẽ cho giá trị : FACTORIAL(0) = 1 FACTORIAL(n) = n*(n - 1)*. . .*2*1 nếu n>0. Ta thấy trong thủ tục có chỉ thị If n= 0 then FACTORIAL : =1 Chứng tỏ thủ tục đã đúng với n =0 ( cho giá trị bằng 1). Giả sử nó đã đúng với n =k, nghĩa là với FACTORIAL(k) thủ tục cho ra giá trị là : FACTORIAL(k) = k * (k -1)*. . . * 2*1 Bây giờ ta sẽ chứng minh nó đúng với n=k+1 Với n =k +1 >0 chỉ thị đứng sau else FACTORIAL := n *FACTORIAL( n-1) sẽ được thực hiện. Vậy với n=k+1 thì giá trị sẽ là : (k+1)*FACTORIAL(k) = (k+1)*k*(k-1)*. . . *2*1 và việc chứng minh hoàn tất. Các thuật 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ự ấn định. Chẳng hạn thứ tự tăng dần ( hay giảm dần) đối với một dãy số, thứ tự từ điển với các chữ.v.v . . . Như vậy bài toán đặt ra ở đây là sắp xếp đối với một bảng gồm n bản ghi R1, R2, R3, . . .Rn. Sắp xếp chọn (Selection Sort). Ý tưởng cơ bản của cách sắp xếp này là đi qua nhiều lần danh sách hay một phần của nó, và cứ mỗi lần đi qua có một phần tử được sắp xếp theo đúng vị trí. Thuật toán mô tả như sau với danh sách cài đặt bằng mảng. /*Thuật toán sắp xếp n phần tử trong mảng X[1], X[2],...,X[n] theo thứ tự tăng dần */. For i=1 to n-1 làm các bước sau : /* chọn phần tử nhỏ nhất trong danh sách con X[i], . . ., X[n] */ - Gán giá trị i cho SmallPos - Gán giá trị X[SmallPos] cho Smalllest. - For j = i +1 to n làm các bước sau : If X[j] < SmallLest then /* Tìm ra phần tử nhỏ hơn*/ + Gán giá trị j vào SmallPos + Gán giá trị X[SmallPos] cho SmallLest /* Chuyển phần tử nhỏ nhất này vào đầu danh sách con */ - Gán giá trị X[i] vào X[SmallPos] - Gán giá trị SmallLest vào X[i] Sắp xếp chèn (Insertion Sort). Nguyên tắc sắp xếp ở đây dựa theo kinh nghiệm của những người chơi bài. Khi có i-1 lá bài đã được sắp xếp đang ở trên tay, nay rút thêm lá bài thứ i nữa thì sắp xếp lại thế nào ? Có thể so sánh lá bài mới lần lượt với lá bài thứ (i-1), thứ (i-2), . . . để tìm ra ‘chỗ’ thích hợp và ‘chèn’ nó vào chỗ đó. Dựa trên nguyên tắc này có thể triển khai một cách sắp xếp như sau : Thoạt đầu k1 được coi như bảng chỉ gồm có một khoá đã được sắp xếp. Xét thêm k2, so sánh nó với k1 để xác định chỗ chèn nó vào, sau đó ta sẽ có một bảng gồm hai khoá đã được sắp xếp. Đối với k3 lại so sánh với k1, k2 và cứ tương tự như vậy đối với k4, k5, k6, . . .v.v cuối cùng sau khi xét xong kn thì bảng khoá đã được sắp xếp hoàn toàn. Thuật toán được mô tả như sau : /* Thuật toán này sắp xếp một danh sách chứa các phần tử trong mảng A[1], A[2], ..., A[n] theo thứ tự tăng dần bằng cách sắp xếp kiểu chèn; gọi -∞ là một giá trị nào đó nhỏ hơn tất cả những giá trị có trong danh sách*/. . Khởi động X[0] tại giá trị - ∞. . For i=2 to làm các bước sau : /* chèn X[i] vào đúng vị trí của nó trong danh sách con chứa các phần tử X[1], X[2], . . ., X[i-1] */ (a). Đặt NextElement bằng X[i]. (b). Đặt j bằng i-1 (c). While NextElement < X[j] làm các bước sau : /* chuyển một phần tử sang để tạo ô trống */ (i). Đặt X[j+1] bằng X[j]. (ii). Tăng j thêm 1 /* Chuyển NextElement vào ô trống*/ (d). Đặt X[j+1] bằng NextElement. Sắp xếp nổi bọt (Buble Sort). Ý tưởng của sắp xếp nổi bọt như sau : Ta đi từ trái sang phải mảng, khi gặp hai thành phần kề nhau mà không đúng trật tự (khoá của thành phần đi trước lớn hơn khoá của thành phần đi sau), thì ta trao đổi hai thành phần này. Sau quá trình này ta sẽ có A[n] thành phần có khoá lớn nhất trong mảng A[1..n]. Thuật toán sắp xếp kiểu nổi bọt. /*Thuật toán sắp xếp một danh sách các mục X1, X2,...,Xn theo thứ tự tăng dần*/. (1). Khởi động NumPairs tại n-1 và Last tại 1. /*NumPairs là số cặp cần được so sánh trong lần đi qua hiện thời và Last đánh dấu vị trí của phần tử cuối cùng đã cần phải hoán vị */ (2). Lặp lại các bước sau : (a). For i=1 to NumPairs If Xi > Xi +1 then (i). Hoán vị Xi và Xi + 1 (ii). Đặt Last bằng i (b). Đặt NumPairs bằng Last -1 Cho đến khi NumPairs = 0. Trường hợp tồi nhất xảy ra khi các phần tử trong danh sách có thứ tự ngược lại. Sắp xếp nhanh (Quick Sort). Ý tưởng của phương pháp như sau : Chọn một khoá ngẫu nhiên nào đó của dãy làm “chốt”. Mọi phần tử nhỏ hơn “khoá chốt” phải được sắp xếp vào vị trí ở trước chốt, và mọi phần tử lớn hơn khoá chốt được xếp ở vị trí sau chốt. Muốn vậy các phần tử trong dãy phải được so sánh với khoá chốt và sẽ đổi vị trí cho nhau, hoặc cho chốt, nếu nó lớn hơn chốt mà lại nằm trước chốt, hoặc nhỏ hơn chốt mà lại nằm sau chốt. Khi việc đổi chỗ đã thực hiện xong thì dãy khoá lúc đó được phân làm hai đoạn : một đoạn gồm các khoá nhỏ hơn chốt, một đoạn gồm các khoá lớn hơn chốt, còn khoá chốt ở giữa hai đoạn nói trên. Đó cũng chính là vị trí thực của nó trong dãy khi đã được sắp xếp, tới đây coi như kết thúc một lượt sắp xếp. Ở các lượt tiếp theo cũng áp dụng một kỹ thuật tương tự đối với các phân đoạn còn lại, tất nhiên chỉ có một phân đoạn được xử lý ngay sau đó, còn phân đoạn để lúc khác. Quá trình cứ tiếp tục cho đến khi phân đoạn chỉ còn hai phần tử thì việc ghi nhớ không cần thiết nữa. Lúc đó một phân đoạn mới được xác định và lặp lại quá trình như trên. Sắp xếp kết thúc khi phân đoạn cuối cùng đã được xử lý xong. Thuật toán QuickSort. Procedure Split( var List; Low, Hight :integer; var Pos : integer); /* Thủ tục này sắp lại các phần tử X[low], . . ., X[hight] sao cho phần tử đầu tiên X[low] được định vị đúng trong mảng tại vị trí Pos */. Var Left,Right : integer; /* chỉ số dùng để tìm từ bên trái và bên phải */ Item : DataType; /* Mục đang được định vị đúng*/ Begin Item : = X[low]; Left : = low; Right : = Hight; While Left < Right do /* khi hai con trỏ chưa gặp nhau */ Begin /* Tìm từ bên phải các phần tử nhỏ hơn Item */ While X[Right] > Item do Right : =Right - 1; /* Tìm từ bên trái các phần tử > Item*/ While (Left < Right) and (X[left] <=Item) do Left : = Left+1; If (Left < Right) then IterChange(X[Left], X[Right])/*hoán vị*/ End; /* Tìm xong đặt mục Item được chọn vào vị trí đúng */ Pos : = Right; InterChange(X[Low], X[Pos]); End; Procedure QuickSort(var List; Low, Hight : integer); /*Thủ tục này dùng QuickSort để sắp xếp các phần tử X[low], . . . , X[Hight] */ Var Pos : integer; Begin If (Low < Hight) then /* danh sách gồm nhiều hơn một mục */ Begin Split(X, Low, Hight, Pos); /* chia thành hai danh sách con */ QuickSort(X, Low, Pos -1 ); /*Sắp xếp danh sách con bên trái*/ QuickSort(X, Pos +1, Hight);/*Sắp xếp danh sách con bên phải*/ End; /*Nếu khác, danh sách là rỗng hay chỉ có một phần tử và không cần phải sắp xếp*/. End; Bảng băm. Khái niệm bảng băm. Bảng băm, trong đó vị trí của một mục được xác định trực tiếp bằng một hàm của chính nó chứ không phải bằng một dãy các so sánh thử - và - sai. Thời gian cần thiết để định vị một mục trong bảng băm trong trường hợp tốt nhất là O(1), nghĩa là nó là một hằng số và không phụ thuộc vào số các mục được lưu trữ. Để thực hiện phép biến đổi hàm băm, ta có hai bước: Bước 1: Tính toán hàm băm H để biến đổi khoá cần tìm thành địa chỉ trong bảng. Trường hợp lý tưởng là khoá khác nhau thông qua hàm H sẽ cho những địa chỉ khác nhau, nhưng trong thực tế thì hai hoặc nhiều khoá khác nhau thông qua hàm H sẽ cho cùng một địa chỉ trong bảng. Bước 2: Quá trình giải quyết sự đụng độ cho những khoá khác nhau có cùng một địa chỉ trong bảng. Một trong những phương pháp giải quyết sự đụng độ là dùng danh sách liên kết bởi vì ta không thể biết trước số các khoá khác nhau có cùng địa chỉ trong bảng là bao nhiêu. Và phương pháp khác để giải quyết sự đụng độ với thời gian nhanh là dùng danh sách đặc có kích thước cố định. Phương pháp băm mở. Tư tưởng cơ bản của băm mở là phân chia tập hợp đã cho thành một số cố định các lớp. Chẳng hạn, ta muốn phân thành N lớp được đánh số 0, 1, . . ., N-1. Ta sử dụng mảng T với chỉ số chạy từ 0 đến N-1. Mỗi thành phần T[i] của mảng được nói đến như một “rổ” đựng các phần tử của tập hợp thuộc lớp thứ i. Các phần tử của tập hợp thuộc mỗi lớp được tổ chức dưới dạng một danh sách liên kết. Do đó T[i] sẽ chứa con trỏ trỏ đến danh sách của lớp i. Ta gọi mảng T là bảng băm. Việc phân chia các phần tử của tập hợp vào các lớp được thực hiện bởi hàm băm H. nếu x là một giá trị khoá của phần tử nào đó của tập hợp thì H(x) là chỉ số nào đó của mảng T và ta gọi H(x) là giá trị băm của x. Như vậy H là ánh xạ từ tập hợp các khoá K vào tập hợp {0, 1, . . ., N-1}. Một số phương pháp thiết kế hàm băm như sau : + Phương pháp cắt bỏ: Giả sử khoá là số nguyên (nếu khoá không là số nguyên ta xét đến các mã số của chúng ). Ta sẽ bỏ đi một phần nào đó của khoá, và lấy phần còn lại làm giá trị băm của khoá. + Phương pháp gấp: Giả sử khoá là số nguyên. Ta phân chia khoá thành một số phần, sau đó kết hợp các phần lại bằng một cách nào đó (có thể dùng phép cộng hoặc phép nhân) để nhận giá trị băm. + Phương pháp sử dụng phép toán lấy phần dư: Giả sử khoá là số nguyên, và giả sử ta muốn chia tập hợp các khoá thành N lớp. Chia số nguyên cho N rồi lấy phần dư làm giá trị băm. Phương pháp băm đóng. Băm đóng, mỗi phần tử của tập thể được lưu giữ trong chính các thành phần T[i] của mảng. Do đó ta có thể khai báo kiểu dữ liệu từ điển được cài đặt bởi mảng băm đóng như sau: Type Dictionary = array[0 . . N-1] of keytype. Ở đây keytype là kiểu dữ liệu của khoá của các phần tử trong từ điển. Các phương pháp băm lại. (1.) Băm lại tuyến tính. Đây là phương pháp băm lại đơn giản nhất, các hàm Hi(x) được xác định như sau : Hi(x) = (H(x) + i ) mod N Tức là, ta xem mảng là mảng vòng tròn và lần lượt xem xét các vị trí H(x) +1, H(x) +2, . . . (2.) Băm lại bình phương. Phương pháp băm lại tốt hơn, cho phép ta tránh được sự tích tụ trong bảng các giá trị xung quanh các giá trị đưa vào bảng ban đầu, là sử dụng các hàm băm lại được xác định như sau: Hi(x) = ( H(x) + i2 ) mod N Đánh giá các phương pháp băm. Dưới đây ta đánh giá thời gian trung bình cần để thực hiện mỗi phép toán trên từ điển trong các bảng băm. a.) Bảng băm mở. Giả sử có N rổ T[0], T[1], . . ., T[N-1] và có M phần tử được lưu giữ trong bảng. Giả sử rằng, hàm băm phân phối đều các phần tử vào mỗi rổ. Do đó trung bình mỗi rổ chứa M/N phần tử. Vì vậy thời gian trung bình để thực hiện mỗi phép toán từ điển Insert, Delete và Member là 0. Nếu N = M thì thời gian trung bình sẽ là hằng số. b.) Bảng băm đóng.(Ta sử dụng phương pháp xác suất để đánh giá). Giả sử rằng, hàm băm H phân phối đều các phần tử của tập hợp trên các chỉ số của bảng. Giả sử ta cần phải đưa một phần tử vào bảng T có chiều N và bảng đã chứa k phần tử. Khi đó xác suất để trong lần đầu ta tìm ra được một vị trí trống là (N-k)/N ta gọi xác suất này là p1, nó chính là xác suất của sự kiện cần một lần thăm dò để đưa phần tử mới vào bảng. Xác suất p2 của sự kiện cần hai lần thăm dò để đưa phần tử mới vào bảng sẽ bằng xác suất lần thăm dò thứ nhất gặp va chạm nhân với xác suất lần thăm dò thứ hai tìm được vị trí trống, tức là : Một cách tương tự, ta tính được xác suât pi của sự kiện i lần thăm dò để đưa phần tử mới vào bảng. Như vậy ta có. Cần chú ý, để đưa phần tử mới vào bảng đã chứa k phần tử đòi hỏi nhiều nhất k +1 lần thăm dò. Từ công thức tính giá trị trung bình (phương sai) của một đại lượng ngẫu nhiên, ta tính được số trung bình các lần thăm dò để đưa một phần tử mới vào bảng đã chứa k phần tử. Ta có nhận xét, số lần thăm dò cần để tìm kiếm một phần tử trong bảng cũng chính là số lần thăm dò để đưa nó vào bảng. Các cấu trúc cây. Khái niệm cây. Khái niệm. Cây là một tập hữu hạn các nút trong đó có một nút đặc biệt gọi là gốc. Giữa các nút có một mối quan hệ phân cấp gọi là “quan hệ cha con”. Có thể định nghĩa cây một cách đệ quy như sau : (1) Một nút là một cây. Nút đó cũng là gốc của cây đó. (2) Nếu n là một nút và T1, T2, . . ., Tk là các cây với n1, n2, . . ., nk lần lượt là các gốc, thì một cây mới T sẽ được tạo lập bằng cách cho nút n trở thành cha của các nút n1, n2, . . ., nk; nghĩa là trên cây này n là gốc còn T1, T2, . . . , Tk là các cây con của gốc. Lúc đó n1, n2, . . ., nk là con của nút n. Các khái niệm về cây. (1.) Bậc của nút và bậc của cây. (2.) Nút kết thúc và nút trung gian. (3.) Mức của nút và chiều cao của cây. (4.) Nút trước và nút sau. (5.) Nút cha và nút con. (6.) Cây có thứ tự. (7.) Chiều dài đường đi. (8.) Rừng. (9.) Cây gán nhãn. Các thao tác với cây. Các cách biểu diễn cây. (1.) Biểu diễn cây bằng đồ thị. (2.) Biểu diễn cây bằng giản đồ. (3.) Biểu diễn cây bằng các dấu ngoặc lồng nhau. (4.) Biểu diễn cây bằng chỉ số. Các phép toán trên cây. (1.) Tìm cha của mỗi đỉnh. (2.) Tìm con bên trái ngoài cùng của mỗi đỉnh. (3.) Tìm em liền kề của mỗi đỉnh. Các phép duyệt cây. Có nhiều phương pháp duyệt cây, chẳng hạn, duyệt lần lượt từ mức 0, mức 1, cho đến mức thấp nhất. Trong cùng một mức ta sẽ thăm các đỉnh từ trái sang phải, đó là phương pháp duyệt cây theo bề rộng. Tuy nhiên ta sẽ nghiên cứu ba phương pháp cơ bản sau : duyệt cây theo thứ tự Preorder (nút gốc trước tiên), Inorder( nút gốc ở giữa ), Postorder (nút gốc ở cuối cùng). Danh sách các đỉnh của cây theo thứ tự Preorder, Inorder, Posorder được xác định đệ quy như sau : (1.) Nếu T là cây gồm một đỉnh duy nhất thì các danh sách Preorder, Inorder, Posorder chỉ chứa một đỉnh nào đó. (2.) Nếu T là cây có gốc r và các cây con của gốc là T1, T2, . . ., Tk thì. + Danh sách Preorder các đỉnh của cây T bắt đầu là r, theo sau là các đỉnh của cây con T1 theo thứ tự Preorder, rồi đến các đỉnh của cây con T2 theo thứ tự Preorder, . . ., cuối cùng là các đỉnh của cây con Tk theo thứ tự Preorder. + Danh sách Inorder các đỉnh của cây T bắt đầu là các đỉnh của cây con T1 theo thứ tự Inorder, rồi đến gốc r, theo sau là các đỉnh của các cây con T2, . . ., Tk theo thứ tự Inorder. + Danh sách Preorder các đỉnh của cây T lần lượt là các đỉnh của các cây con T1, T2, . . ., Tk theo thứ tự Preorder sau cùng là gốc r. Thủ tục duyệt cây theo chiều rộng, ta sử dụng hàng Q để lưu giữ các đỉnh theo thứ tự đã được thăm, đầu hàng là đỉnh ngoài cùng bên trái mà ta chưa thăm các con của nó, còn cuối hàng là đỉnh ta đang thăm. Khi loại một phần tử ở đầu hàng, chúng ta sẽ lần lượt thăm các con của nó (nếu có) và khi thăm đỉnh nào thì đưa đỉnh đó vào cuối hàng. Khi đó ta có thủ tục như sau: Procedure BreadthTraverse(A : Node); /* Thủ tục đi qua cây gốc A theo bề rộng */ Var B: Node; Q: Queue; Begin Initialize(Q); /* Khởi tạo hàng rỗng */ Visit(A); Add(A,Q); /* Đưa gốc A vào hàng Q */ While not Empty(Q) do Begin Delete(Q,B); /* Loại phần tử đầu hàng và gán cho B */ B:=EldestChild(B); While B $ do Begin Visit(B); Add(B,Q); B:=NextSibling(B); End; End; End; Cây quyết định (Decision Trees). Cây được dùng khá phổ biến để biểu diễn lời giải của những bài toán mà đặc điểm thể hiện ở chỗ xuất hiện nhiều tình huống, nhiều khả năng đòi hỏi phải có một quyết định lựa chọn, được gọi là cây quyết định. Cây nhị phân. Khái niệm cây nhị phân. Cây nhị phân là một tập hợp hữu hạn các đỉnh xác định đệ quy như sau: (1) Một tập trống là cây nhị phân. (2) Giả sử T1 và T2 là hai cây nhị phân không cắt nhau (T1∩T2 =F) và r là một đỉnh mới không thuộc T1, T2. Khi đó ta có thể thành lập một cây nhị phân mới T với gốc r có T1 là cây con bên trái, T2 là cây con bên phải của gốc. Được biểu diễn như sau: Đặc điểm của cấy nhị phân : Mọi nút tối đa trên cây nhị phân có tối đa hai con, đối với cây con một nút người ta cũng phân biệt cây con trái, cây con phải. Cây nhị phân lệch trái là cây chỉ có cây con bên trái. Cây nhị phân lệch phải là cây chỉ có cây con bên phải. Cây zích -zắc là cây chỉ có một cây con bên trái (hoặc phải) và tiếp đến một cây con bên phải (hoặc trái). Cây nhị phân hoàn toàn : các nút ứng với các mức trừ mức cuối cùng đều đạt tối đa. Cây nhị phân đầy đủ : các nút tối đa ở tại mọi mức. Đối với cây nhị phân cần lưu ý tính chất sau: Bổ đề : Số lượng tối đa nút ở mức i trên một cây nhị phân là: 2i-1 (i ≥ 1). Số lượng tối đa các nút trên một cây nhị phân có chiều cao h là : 2h – 1 ( h ≤ 1). Các thao tác với cây nhị phân. (1.) Lưu trữ kế tiếp : Nếu có một cây nhị phân hoàn toàn, hoặc đầy đủ, ta sẽ đánh số các nút trên cây đó theo thứ tự từ mức 1 trở lên, hết mức này đến mức khác và từ trái sang phải đối với các nút ở một mức. như sau : Khi đó ta thấy ngay con của nút i là các nút 2i và 2i +1, cha của nút thứ j là ëj/2û. (2.) Lưu trữ móc nối: Mỗi nút ứng với một phần tử nhớ có quy cách: LPTR INFO RPTR Trường INFO : ứng với thông tin (dữ liệu ) của nút. Trường LPTR : ứng với con trỏ trỏ tới cây con trái của nút đó. Trường RPTR : ứng với con trỏ, trỏ tới cây con phải của nút đó. Để có thể truy nhập vào các nút trên cây cần có một con trỏ T, trỏ tới nút gốc của cây đó. Các phép duyệt cây nhị phân. Các phép đó được định nghĩa một cách đệ quy như sau : Duyệt theo thứ tự trước (Preorder - Tiền tự) Thăm gốc. Duyệt cây con trái theo thứ tự trước. Duyệt cây con phải theo thứ tự trước. Duyệt theo thứ tự giữa (Inoder - Trung tự). Duyệt cây con trái theo thứ tự giữa. Thăm gốc. Duyệt cây con phải theo thứ tự giữa. Duyệt theo thứ tự sau (Posorder - Hậu tự). Duyệt cây con trái theo thứ tự sau. Duyệt cây con phải theo thứ tự sau. Thăm gốc. Chú ý : khi gặp cây rỗng thì “thăm” nghĩa là “không làm gì”. Các thủ tục duyệt cây như sau : Procedure RPreOrder(T); /* Ở đây T là con trỏ, trỏ tới gốc cây đã cho có dạng lưu trữ móc nối. Mỗi nút trên cây T có quy cách. Phép duyệt ở đây được đặc trưng bởi việc in giá trị trường INFO của nút. */ (1.) if T null then Begin Write(INFO(T)); Call RPreOrder(LPTR(T)); Call RPreOrder(RPTR(T)); End; (2.) Return; /*============================*/ Procedure RPosOrder(T); (1.) if T null then Begin Call RPosOrder(LPTR(T)); Call RPosOrder(RPTR(T)); Write(INFO(T)); End; (2.) Return; Các thuật toán tìm kiếm. Phát biểu bài toán : “Cho một bảng gồm n bản ghi R1, R2, . . ., Rn. Mỗi bản ghi Ri (1≤i≤ n) tương ứng với một khoá ki. Hãy tìm bản ghi có giá trị khoá tương ứng bằng X cho trước.” X được gọi là khoá tìm kiếm hay đối trị tìm kiếm, công việc tìm kiếm sẽ hoàn thành khi có một trong hai tình huống sau xảy ra. (1.) Tìm được bản ghi có giá trị khoá tương ứng bằng X. (2.) Tìm không được bản ghi nào có giá trị bằng X cả. Tìm kiếm tuần tự. Ý tưởng : Bắt đầu từ bản ghi thứ nhất, lần lượt so sánh khoá tìm kiếm với khoá tương ứng của các bản ghi trong bảng, cho tới khi tìm được bản ghi mong muốn hoặc đã hết bảng mà chưa tìm thấy. Thủ tục tìm kiếm được mô tả như sau: Procedure SequenSearch( var ListType; n : integer; Item : ElementType; var found : Boolean; var Loc : integer); /*Thuật toán này tìm Item trong danh sách X[1], X[2],..., X[n]. Found là True và Loc có giá trị là vị trí Item nếu tìm ra,ngược lại found = False */. Begin Found :=false; Loc :=1; While not found and (Loc <=n) do If Item =X[Loc] then found:=True; Else Loc=Loc+1; End; Đánh giá thuật toán : Ở đây, để đánh giá hiệu quả của giải thuật ta dựa vào số phép toán so sánh. Ta thấy giải thuật trên thuận lợi thì chỉ cần 1 phép toán so sánh ; Cmin = 1; còn xấu nhất Cmax = n+1. Nếu giả sử hiện tượng khoá tìm kiếm trùng với một khoá nào đó của bảng là đồng khả năng thì Ctb = (n+1)/2. Như vậy thời gian thực hiện giải thuật trên là O(n).. Tìm kiếm nhị phân. Nó tương tự như cách thức ta làm khi tra cứu từ điển. Chỉ khác là trong công việc trên để so sánh với khoá tìm kiếm ta chọn hú hoạ một phần tử, còn với phép tìm kiếm nhị phân ta luôn chọn khoá ở giữa, dãy khoá đang xét để thực hiện so sánh với khóa tìm kiếm. Tìm kiếm sẽ kết thúc nếu X = ki (khoá). Nếu X k[i] tìm kiếm được thực hiện với k[i+1], k[i+2], . . ., k[n]. Với dãy khóa sau một kỹ thuật tương tự được thực hiện lại. Quá trình tìm kiếm được tiếp tục khi tìm thấy khoá mong muốn hoặc dãy khoá xét đó trở thành rỗng. Thuật toán như sau : /* Thuật toán tìm Item trong danh