Giáo trình Cấu trúc dữ liệu và giải thuật - Nguyễn Trung Hòa

h sách 9-Sep-10 3.3. Các thao tác cơ bản trên danh sách liên kết đơn 126 4.3.1. Giới thiệu chung „ Giới thiệu các thao tác ‰ Khởi tạo và lập danh sách ‰ Duyệt danh sách ‰ Sắp xếp danh sách ‰ Tìm kiếm trong danh sách ‰ Bổ sung vào danh sách ‰ Loại bỏ khỏi danh sách ‰ Sao chép và kết nối „ Các thao tác này thường được lặp đi lặp lại nhiều lần trong một chương trình có cài đặt danh sách liên kết đơn, do đó chúng thường được viết dưới dạng chương trình con để sử dụng nhiều lần. 64 9-Sep-10 3.3. Các thao tác cơ bản trên danh sách liên kết đơn 127 4.3.1. Giới thiệu chung „ Một số quy ước quan trọng ‰ Con trỏ danh sách: TroDS, TroDS1, (thường là con trỏ tổng quát –không kiểu) ‰ Trỏ đến một node (trỏ có kiểu): Tam, Tam1, ‰ Dữ liệu của node được trỏ bởi Tam: DL(Tam) ‰ Con trỏ liên kết của node được trỏ bởi Tam: Ke(Tam); ‰ Cấp một node và lưu địa chỉ vào Tam: Tam<=Avail ‰ Trả ô nhớ đang được trỏ bởi Tam: Tam=>Avail ‰ 9-Sep-10 3.3. Các thao tác cơ bản trên danh sách liên kết đơn 128 4.3.2. Khởi tạo và lập danh sách (Giải thuật kiểu LIFO để tạo danh sách) TroDS=NULL Tam<=Avail Nhập dữ liệu vào DL(Tam) Ke(Tam)=TroDS TroDS=Tam Kiểm tra đkiện dừng Bắt đầu Kết thúc + _ a b c d NULL DL DL DL DL Trỏ tạm TroDS 65 9-Sep-10 3.3. Các thao tác cơ bản trên danh sách liên kết đơn 129 Ke(Tam)=NULL 4.3.2. Khởi tạo và lập danh sách (Giải thuật kiểu FIFO để tạo danh sách) TroDS=NULL Tam<=Avail Nhập dữ liệu vào DL(Tam) Kiểm tra điều kiện dừng Bắt đầu Kết thúc + _ a b c d NULL DL DL DL DL Tạm TroDS TroDS==NULL TroDS=Tam Ke(Trỏ cuối)=Tam Trỏ cuối=Tam Trỏ cuối _ + 9-Sep-10 3.3. Các thao tác cơ bản trên danh sách liên kết đơn 130 4.3.3. Duyệt danh sách (xem danh sách) a b c d Bắt đầu Trỏ duyệt=TroDS Trỏ duyệt !=NULL viết ra DL(trỏ duyệt) Trỏ duyệt=Ke(trỏ duyệt) Kết thúc + _ Trỏ duyệt TroDS DL a DL a DL d DL d DL c DL c DL b DL b 66 9-Sep-10 3.3. Các thao tác cơ bản trên danh sách liên kết đơn 131 4.3.4. Sắp xếp danh sách „ Nhắc lại thuật toán nổi bọt sắp xếp dãy (mảng): Với i=1 đến n-1 (từ đầu đến áp chót) Với j:=i+1 to n (từ ngay sau i đến hết) Nếu a[i]>a[j] (không thỏa điều kiện sắp xếp) thì Tráo a[i] và a[j] ‰ Ta sẽ bắt chước thuật toán trên, áp dụng vào danh sách liên kết ‰ Các biến chạy i, j ở thuật toán trên đóng vai trò cung cấp các địa chỉ của các phần tử của dãy. 9-Sep-10 3.3. Các thao tác cơ bản trên danh sách liên kết đơn 132 4.3.4. Sắp xếp danh sách „ Với thuật toán sắp xếp danh sách liên kết, biến chạy ở thuật toán ta sẽ xây dựng là các biến con trỏ ‰ Tạm1, Tạm2 „ Quá trình chạy ‰ Tạm1: Từ đầu (trỏ danh sách) đến áp chót (tam1^.ke=NULL) ‰ Tạm2: từ ngay sau tạm1 đến hết (NULL) „ Từ đó ta có giải thuật sau: 67 9-Sep-10 3.3. Các thao tác cơ bản trên danh sách liên kết đơn 133 4.3.4. Sắp xếp danh sách „ Giải thuật sắp xếp Tạm1:=TroDS; Khi tạm1^.kềnil thực hiện Tạm2:=tạm1^.kề; Khi tạm2nil thực hiện Nếu tạm1^.nd>tạm2^.nd thì tráo tạm1^.nd và tạm2^.nd Tạm2:=tạm2^.kề; Tạm1:=tạm1^.kề; „ Lưu ý khi viết chương trình con thì tham số duy nhất của chương trình con là con trỏ danh sách, nó là tham trị. Bắt đầu Tam1=TroDS Ke(Tam1)!=NULL Tam2=Ke(Tam1) Tráo DL(Tam1) và DL(tam2) Kết thúc + Tam2!=NULL DL(Tam1)>DL(Tam2) Tam2=Ke(Tam2) Tam1=Ke(Tam1) + + _ _ _ 9-Sep-10 3.3. Các thao tác cơ bản trên danh sách liên kết đơn 134 „ Tìm kiếm thực chất là duyệt và so sánh khóa tìm kiếm (với thông tin của dữ liệu thuộc trường tương ứng). ‰ Có thể duyệt hết hoặc không hết tùy theo yêu cầu tìm kiếm ‰ Lưu ý khi chọn kiểu vòng lặp và điều kiện dừng „ Chọn while hay repeat? „ Tùy thuộc vào trạng thái ban đầu và yêu cầu tìm kiếm! ‰ Điều kiện dừng thường là biểu thức cộng logic or ‰ Dạng thủ tục: đầu ra là thông báo trực tiếp hoặc là tham biến để truyền giá trị tìm được ra ngoài. ‰ Dạng hàm boolean: thường sử dụng để trả lời câu hỏi có/không? 4.3.5. Tìm kiếm trong danh sách 68 9-Sep-10 3.3. Các thao tác cơ bản trên danh sách liên kết đơn 135 4.3.5. Tìm kiếm trong danh sách „ Thuật toán chung Tạm:= trỏ danh sách; Khi (tạm nil) hoặc (chưa thỏa yêu cầu) thực hiện tạm:=tạm^.kề; Nếu thỏa yêu cầu thì gán trị cho biến ra hoặc/và thông báo có nếu không thỏa thì thông báo không ‰ Ví dụ? Bắt đầu Tạm=TroDS (Tạm !=NULL) V(chưa thỏa yêu cầu) Gán trị tìm được cho biến ra Tạm=Ke(Tạm) Kết thúc + _ thỏa yêu cầu Không tìm được _ + 9-Sep-10 3.3. Các thao tác cơ bản trên danh sách liên kết đơn 136 4.3.6. Bổ sung một phần tử vào danh sách „ Đặt bài toán: ‰Bổ sung gì ? „ (một phần tử vào danh sách) ‰Bổ sung vào đâu? „ (vào danh sách đang được trỏ (quản lý) bởi trods) ‰Vị trí nào? „ (cần một con trỏ Q nữa?) „ Bên trái hay bên phải Q^? „ Trước hay sau Q^? ‰Vậy ta có các bài toán sau: 69 9-Sep-10 3.3. Các thao tác cơ bản trên danh sách liên kết đơn 137 4.3.6. Bổ sung một phần tử vào danh sách „ Bài toán 1: ‰ Xây dựng giải thuật và viết chương trình con để bổ sung phần tử dữ liệu pt vào danh sách liên kết đơn đang được trỏ bởi trods, tại vị trí đang được trỏ bởi con trỏ Q, sao cho sau khi bổ sung con trỏ kề của phần tử mới có giá trị bằng Q. ‰ Tạm đặt tên là Bosungtruoc(...) c a b d e Q Q^ Trods 9-Sep-10 3.3. Các thao tác cơ bản trên danh sách liên kết đơn 138 4.3.6. Bổ sung một phần tử vào danh sách c a b d e TrodsBắt đầu Tam<=Avail Ke(Tam)=Q Nhập dữ liệu vào DL(Tam) Q!=TroDS tam1=trods Ke(Tam1)!=Q tam1=Ke(Tam1) Ke(Tam1)=Tam trods:=tam Kết thúc Tam Q _+ _ + Tam1 DL 70 9-Sep-10 3.3. Các thao tác cơ bản trên danh sách liên kết đơn 139 4.3.6. Bổ sung một phần tử vào danh sách „ Bài toán 2: ‰ Viết chương trình con để bổ sung phần tử dữ liệu pt vào danh sách liên kết đơn đang được trỏ bởi trods, tại vị trí đang được trỏ bởi con trỏ Q, sao cho sau khi bổ sung con trỏ kề của phần tử được trỏ bởi Q trỏ vào phần tử vừa được bổ sung. ‰ Tạm đạt tên là Bosungsau(...) a b c e Q Q^ Trods d 9-Sep-10 3.3. Các thao tác cơ bản trên danh sách liên kết đơn 140 4.3.6. Bổ sung một phần tử vào danh sách Bắt đầu Tam<=Avail Ke(Tam)=Ke(Q) Nhập dữ liệu vào DL(Tam) Ke(Q)=Tam Kết thúc a b c e Q Q^ Trods Tam DL 71 9-Sep-10 3.3. Các thao tác cơ bản trên danh sách liên kết đơn 141 4.3.7. Loại bỏ khỏi danh sách liên kết một phần tử „ Loại bỏ trong danh sách nào? „ Loại bỏ phần tử nào? (vị trí nào) „ Bài toán: Loại bỏ một phần tử ra khỏi danh sách đang được trỏ bởi Trods tại vị trí được trỏ bởi Q „ Chương trình con cần có hai tham số: tham số TroDS và tham số con trỏ Q, trong đó TroDS cần thiết là tham biến 9-Sep-10 3.3. Các thao tác cơ bản trên danh sách liên kết đơn 142 4.3.7. Loại bỏ khỏi danh sách liên kết một phần tử a b c d Bắt đầu Tam=Ke(Tam) Ke(Tam)=Ke(Q) Q=>Avail Kết thúc Q==TroDS Ke(Tam)!=Q TroDS=Ke(Q) _ _ + + Tam=TroDS TroDS Q Tam 72 4.4. Các dạng khác của danh sách liên kết tuyến tính 4.4.1. Danh sách nối vòng 4.4.2. Danh sách liên kết đôi 4.4.1. Danh sách nối vòng „ Là danh sách liên kết đơn „ Nút cuối cùng chứa địa chỉ của nút đầu tiên (Con trỏ của nút cuối không trỏ vào NULL mà trỏ đến nút đầu tiên của danh sách). „ Là danh sách liên kết đơn, sao cho việc kết nối giữa các phần tử tạo thành một chu trình. a b c d 73 4.4.1. Danh sách nối vòng ‰ Nhận xét: trong danh sách nối vòng mọi phần tử đều có vai trò như nhau trong việc kết nối và con trỏ dùng để quản lý danh sách có thể trỏ đến một phần tử bất kỳ trong danh sách ‰ Một ưu điểm của danh sách nối vòng là trỏ danh sách có thể di chuyển được. „ Khi nào thì kết thúc duyệt? (kiểm tra Ke(tam) == TroDS?) „ Bài tập: Viết giải thuật tạo danh sách nối vòng, duyệt và xem danh sách, sắp xếp danh sách. 4.4.2. Danh sách liên kết đôi „ Kh¸i niÖm: ‰ Danh sách liên kết đôi là danh sách tuyến tính, trong đó mỗi nút có chứa hai con trỏ làm nhiệm vụ trỏ đến nút trước và nút sau nó trong danh sách „ S¬ ®å cÊu t¹o: ‰ Mỗi nút ‰ Danh sách a b c d TroDS Ketruoc Kesau DL 74 4.4.2. Danh sách liên kết đôi „ Mỗi nút không chỉ nối đến nút tiếp theo mà còn nối đến nút trước nó „ Có 2 con trỏ trỏ tới NULL: tại nút đầu và nút cuối của danh sách „ Ưu điểm: ‰ tại một nút có thể thăm nút trước nó một cách dễ dàng. ‰ Cho phép duyệt danh sách theo chiều ngược lại ‰ Con trỏ danh sách không cần thiết phải chốt tại một điểm duy nhất 4.4.2. Danh sách liên kết đôi „ Khai báo kiểu để cài đặt danh sách liên kết đôi typedef struct Node{ DL; struct Node* Kesau; struct Node* Ketruoc; } kieupt; Ketruoc Kesau DL 75 4.4.2. Danh sách liên kết đôi „ Thêm nút nằm ngay trước phần tử được trỏ bởi Q (trường hợp tổng quát): ‰ Xin cấp vùng nhớ mới ‰ Nhập dữ liệu mới ‰ Nếu TroDS==NULL „ Tạo 2 kết nối từ phần tử mới tới NULL „ TroDS=Tam ‰ Nếu không, Nếu Q==TroDS „ Tạo một kết nối (sau) đến phần tử đầu đang trỏ bởi Q „ Tạo kết nối (trước) tới NULL „ Thay kết nối trước của Q „ Thay địa chỉ của TroDS ‰ Nếu không, „ Tạo 2 kết nối từ phần tử mới tới danh sách „ Thay 2 kết nối từ danh sách để nối tới phần tử mới Bắt đầu Tam<=Avail Nhập dữ liệu vào DL(Tam) Ketruoc(Tam)=Ketruoc(Q) Kết thúc Ketruoc(Q)=Tam Kesau(Ketruoc(Q)=Tam TroDS==NULL_ Q==TroDS_ Ketruoc(Tam)=Kesau(Tam)=NULL TroDS=Tam + + TroDS=Tam Kesau(Tam)=Q 76 4.4.2. Danh sách liên kết đôi „ Loại bỏ nút được trỏ bởi Q ‰ Nếu Q==Trods „ Nếu (Kesau(Q)!=NULL) Ketruoc(Kesau(Q))=NULL „ TroDS=Kesau(Q) ‰ Nếu không, „ Nếu (Kesau(Q)=NULL) Kesau(Ketruoc(Q))=NULL „ Nếu không ‰ Ketruoc(Kesau(Q))=Ketruoc(Q) ‰ Kesau(Ketruoc(Q))=Kesau(Q) ‰ Q=>Avail Bắt đầu TroDS a b c d Q Q==TroDS _+ Ketruoc(Kesau(Q))=NULL TroDS=(Kesau(Q)) Kesau(Q)==NULL_ Kesau(Ketruoc(Q))=NULL Ketruoc(Kesau(Q))=Ketruoc(Q) Kesau(Ketruoc(Q))=Kesau(Q) Q=>Avail Kết thúc +Kesau(Q)==NULL _+ 77 4.5. Ví dụ sử dụng danh sách liên kết – Cài đặt đa thức Tự đọc và tự cài đặt 4.6. Ngăn xếp và Hàng đợi 4.6.1. Ngăn xếp và các thao tác cơ bản trên các ngăn xếp 4.6.2. Mô hình thiết kế ngăn xếp 4.6.3. Ứng dụng của ngăn xếp 4.6.4. Hàng đợi và các thao tác cơ bản trên các hàng đợi 4.6.5. Cài đặt hàng đợi 78 4.6.1. Ngăn xếp và các thao tác cơ bản trên các ngăn xếp „ Định nghĩa: ‰ Một ngăn xếp (stack) là một mô hình (cơ cấu) mà các tác động vào nó chỉ được thực hiện tại một phía của nó. Phía này được gọi là đỉnh của ngăn xếp. ‰ Trong tin học, một ngăn xếp là là một danh sách tuyến tính mà các tác động vào nó chỉ được thực hiện tại một phía của nó. Phía này được gọi là đỉnh của ngăn xếp. „ Ví dụ: ‰ Ta hình dung ngăn xếp như một ngăn kéo đựng tài liệu (của một bàn làm việc) mà ta chỉ có thể thêm vào hoặc bớt đi các phần tử (tài liệu) trong đó từ mặt trên (đỉnh) của ngăn kéo. ‰ Đoạn đảo chiều toa xe lửa. ‰ Hộp băng đạn của súng AK. ‰ Một chồng các đồ vật cùng kiểu (sách, bát, áo, đồng xu, hộp đạn súng máy AK47) „ Vì vậy mà có tên gọi Stack (danh sách kiểu xếp chồng) 79 4.6.1. Ngăn xếp và các thao tác cơ bản trên các ngăn xếp „ Với kiểu ngăn xếp, ta chỉ có thể thực hiện các thao tác sau: ‰ Khởi tạo một ngăn xếp. ‰ Đẩy (push) một phần tử mới vào ngăn xếp nếu ngăn xếp chưa đầy. Phần tử dữ liệu mới luôn được thêm tại đỉnh. ‰ Lấy (pop) một phần tử ra khỏi ngăn xếp nếu ngăn xếp khác rỗng. Phần tử bị loại là phần tử đang nằm tại đỉnh. ‰ Kiểm tra xem ngăn xếp có hay không có phần tử (rỗng hay không). ‰ Kiểm tra xem ngăn xếp đã đầy hay chưa ‰ Mọi tác động khác vào ngăn xếp đều phải thông qua các thao tác này. „ Như vậy: ‰ Các phần tử của ngăn xếp có cùng một kiểu nào đó ‰ Ngăn xếp là một trường hợp riêng của danh sách, được sử dụng trong các ứng dụng có liên quan đến sự đảo ngược. Trong CTDL ngăn xếp, việc thêm hay lấy dữ liệu chỉ được thực hiện tại một đầu. Dữ liệu thêm vào sau sẽ lấy ra trước, tính chất này còn được gọi là vào sau ra trước (Last In First Out - LIFO). ‰ Vì vậy, từ nay về sau khi nói đến ngăn xếp ta hiểu đó là danh sách kiểu LIFO 4.6.1. Ngăn xếp và các thao tác cơ bản trên các ngăn xếp Push Q vào stack Push A vào stack Pop một phần tử (A) khỏi stack Stack rỗng Push R vào stack Push D vào stack Push M vào stack Push Q vào stack Push G vào stack Pop một phần tử (M) khỏi stack Q QA QA QPop một phần tử (Q) khỏi stack RD RD M RD M RD Q RD QG Stack rỗngR QARD MQG Stack „Ta sẽ thấy trong ví dụ sau, các thao tác push và pop là các thao tác quan trọng, được sử dụng thường xuyên khi làm việc với ngăn xếp. 80 4.6.1. Ngăn xếp và các thao tác cơ bản trên các ngăn xếp „ Ví dụ: IT-IS-A-STACK Push I vào stack I TI S Push T vào stack Pop một phần tử (T) khỏi stack Push I vào stack Push S vào stack Pop một phần tử (S) khỏi stack A Push A vào stack Pop một phần tử (A) khỏi stack Push S vào stack T Push T vào stack Push A vào stack A C Push C vào stack K Push K vào stack 4.6.1. Ngăn xếp và các thao tác cơ bản trên các ngăn xếp „ Ví dụ để đổi một số nguyên dương, chẳng hạn 23, sang cơ số 2, ta thực hiện như sau: „ Như vậy ta phải nhiểu lần thực hiện thao tác push(s, sodu) trong quá trình thực hiện chia liên tiếp cho 2 và sau khi đã thực hiện xong dãy các phép chia lại phải liên tiếp viết ra pop(s) cho đến khi ngăn xếp s rỗng 23 2 111 2 51 2 21 2 10 2 01 1 1 1 0 1 Đặt số dư vào Ngăn xếp Viết ra kết quảQuá trình chia liên tiếp 81 4.6.1. Ngăn xếp và các thao tác cơ bản trên các ngăn xếp Begin repeat write('Cho so tu nhien n: '); readln(n); ktaonx(tronx); while n>0 do begin r:=n mod 2; push(r,tronx); n:=n div 2; end; while not la_rong(tronx) do write(pop(tronx)); writeln; write('Co doi nua khong? (C/K)'); readln(ch); until upcase(ch)='K'; End. 4.6.2. Mô hình thiết kế ngăn xếp „ Thực hiện mô hình hóa ngăn xếp ‰ Ta cần tạo một cấu trúc danh sách tuyến tính và chuẩn bị các thao tác để có thể làm việc với danh sách này với tư cách là một ngăn xếp „ Cần định nghĩa một kiểu danh sách để coi nó như ngăn xếp, bao gồm cấu trúc dữ liệu được sử dụng và đối tượng làm đỉnh của ngăn xếp. Do đó có thể chọn danh sách liên kết đơn với một con trỏ đến đầu (đỉnh) danh sách hoặc mảng một chiều với một tham số nguyên chỉ vị trí đỉnh của ngăn xếp „ Cần tạo các thủ tục/hàm để thao tác trên danh sách này với tư cách là thao tác ngăn xếp bao gồm 5 thao tác đã nói ở trên. 82 4.6.2. Mô hình thiết kế ngăn xếp (Mô hình danh sách liên kết của ngăn xếp) „ Mô hình danh sách liên kết của ngăn xếp ‰ Cấu trúc dữ liệu của mỗi phần tử thuộc ngăn xếp sẽ chính là một bản ghi gồm các trường nội dung và một trường kiểu con trỏ làm nhiệm vụ liên kết. ‰ Ngăn xếp S là một danh sách được quản lý bởi con trỏ danh sách S và các thao tác khởi tạo, push, pop, kiểm tra rỗng, kiểm tra đầy sẽ được tham số hóa bởi các hàm/thủ tục: khoitao(s), push(s,pt), pop(s), la_rong(s), la_day(s) ‰ Việc lưu trữ dữ liệu vào ngăn xếp s thực chất là việc thực hiện một hay nhiều lần thao tác push(s,pt) với s là con trỏ dùng để quản lý ngăn xếp (trỏ đến đỉnh của nó) và pt là một phần tử dữ liệu cần lưu trữ. ‰ Việc lấy dữ liệu ra khỏi ngăn xếp được làm tuần tự bằng các thao tác pop(s) 4.6.2. Mô hình thiết kế ngăn xếp (Mô hình danh sách liên kết của ngăn xếp) „ Khai báo và thủ tục trong Pascal Type kieudl=; tropt=^kieupt; kieupt=record nd:kieudl; ke:tropt; end; Var r:kieudl; tronx:pointer; n:longint; 83 4.6.2. Mô hình thiết kế ngăn xếp (Mô hình danh sách liên kết của ngăn xếp) Procedure ktaonx(var tronx:pointer); Begin tronx:=nil; End; Procedure push(pt:kieudl; var tronx: pointer); Var them:tropt; Begin new(them); them^.nd:=pt; them^.ke:=tronx; tronx:=them; End; 4.6.2. Mô hình thiết kế ngăn xếp (Mô hình danh sách liên kết của ngăn xếp) Function pop(var tronx:pointer):kieudl; var tam:tropt; Begin tam:=tronx; pop:=tam^.nd; tronx:=tam^.ke; dispose(tam); end; Function la_rong(tronx:pointer):boolean; begin la_rong:=(tronx=nil); end; „ Nói chung khi cài đặt bởi danh sách liên kết ta ít phải quan tâm nhiều đến việc ngăn xếp là đầy hay chưa. 84 4.6.2. Mô hình thiết kế ngăn xếp (Mô hình mảng của ngăn xếp) „ Mô hình mảng của ngăn xếp ‰ Cấu trúc dữ liệu của mỗi phần tử thuộc ngăn xếp sẽ chính là cấu trúc dữ liệu của phần tử của mảng. ‰ Ngăn xếp s là một cấu trúc/bản ghi gồm mảng các phần tử dữ liệu được quản lý kèm theo một biến đỉnh (số nguyên) để xác định vị trí của đỉnh ngăn xếp và các thao tác khởi tạo, push, pop, kiểm tra rỗng, kiểm tra đầy sẽ được tham số hóa bởi các hàm/thủ tục: khoitao(s), push(s,pt), pop(s), la_rong(s), la_day(s). ‰ Vì mảng có kích thước cố định nên hàm kiểm tra đầy (la_day(s)) là cần thiết 4.6.2. Mô hình thiết kế ngăn xếp (Mô hình mảng trong C của ngăn xếp) „ Cấu trúc ngăn xếp typedef struct intstack{ int *stackAry; /*mảng lưu trữ các phần tử.*/ int count; /*số phần tử hiện có của stack */ int stackMax; /*giới hạn tối đa các phần tử được lưu trữ*/ int top; /*chỉ số của phần tử đỉnh*/ } IntStack; int PushStack(IntStack *stack, int dataIn) { if(stack->count == stack->stackMax) return 0; /*kiểm tra tràn*/ else{ /* Thêm phần tử vào stack */ (stack->count)++; (stack->top)++; /* Tăng đỉnh */ stack->stackAry[stack->top] =dataIn; return 1;} } /* PushStack*/ 85 4.6.2. Mô hình thiết kế ngăn xếp (Mô hình mảng trong C của ngăn xếp) int PopStack(Int Stack *stack,int *dataOut){ if(stack->count == 0)return 0; /* Kiểm tra stack rỗng */ *dataOut=stack->stackAry[stack->top]; /* lấy giá trị phần tử bị loại*/ (stack->count)--; (stack->top)--; /* giảm đỉnh */ return 1; }/* PopStack*/ /* Xem phần tử ở đỉnh của stack, trả lại 1 nếu thành công và trả lại 0 nếu stack rỗng, dataOut chứa kết quả */ int TopStack(IntStack *stack, int* dataOut){ if(stack->count ==0) return 0; /* Stack rỗng */ *dataOut = stack->stackAry[stack->top]; return 1; }/* Topstack*/ 4.6.2. Mô hình thiết kế ngăn xếp (Mô hình mảng trong C của ngăn xếp) /* Kiểm tra stack rỗng, trả lại 1 nếu là rỗng, Trả lại 0 nếu không rỗng */ int IsEmptyStack(IntStack *stack){ return(stack->count == 0); }/* IsEmptyStack*/ /* Kiểm tra stack đầy. Trả lại 1 nếu là đầy, trả lại 0 nếu không đầy*/ int IsFullStack(IntStack *stack){ return(stack->count==stack->stackMax); }/* IsfullStack*/ 86 4.6.2. Mô hình thiết kế ngăn xếp (Mô hình mảng trong C của ngăn xếp) Int Stack *CreateStack(int max){ IntStack *stack; stack=(IntStack*)malloc(sizeof(IntStack)); if(stack == NULL) return NULL; /*Khởi tạo stack rỗng*/ stack->top = -1; stack->count = 0; stack->stackMax= max; stack->stackAry=malloc(max*sizeof(int)); return stack ; }/* createStack*/ 4.6.2. Mô hình thiết kế ngăn xếp (Mô hình mảng trong Pascal của ngăn xếp) „ Cấu trúc ngăn xếp ‰ Type „ Nmax=100; „ Kieudl=; „ Kieumang=array[1..100] of kieudl; „ Kieunx=record „ dl:kieumang; „ dinh:integer; „ end; ‰ Var „ S: kieunx; 87 4.6.2. Mô hình thiết kế ngăn xếp (Mô hình mảng trong Pascal của ngăn xếp) Thủ tục/hàm: khoitao(s), s.dinh:=0; Thủ tục/hàm: push(s,pt): s.dinh:=s.dinh+1; s.dl[dinh]:=pt; Hàm: pop(s), return(s.dl[dinh]); s.dinh:=s.dinh-1; Hàm la_rong(s) if s.dinh=0 return true Ham la_day(s) if s.dinh=nmax return true 4.6.3. Ứng dụng của ngăn xếp (xử lý biểu thức) „ Đổi cơ số „ Định giá biểu thức hậu tố ‰ Ký pháp trung tố và ký pháp hậu tố của biểu thức „ Ký pháp trung tố (cách viết biểu thức thông thường) ‰ Với phép toán 2 ngôi: Mỗi toán tử được đặt giữa hai toán hạng a+b*c được hiểu là a+(b*c) ‰ Với phép toán một ngôi: Toán tử được đặt trước toán hạng ‰ Tuy nhiên theo cách viết này ta cần phải quy ước: trong dãy các phép tính thì nhân (chia) thực hiện trước, còn cộng (trừ) thực hiện sau (kể từ trái qua phải), nếu muốn thay đổi (quy định thứ tự khác đi) thì phải sử dụng đến các dấu ngoặc theo nghĩa trong ngoặc sẽ được thực hiện trước. (a+b)*c ‰ Sắp xếp giảm dần của thứ tự ưu tiên của toán tử: ( ) > ^ > * = % = / > + = – „ Việc định giá (tính giá trị) biểu thức trung tố khá phức tạp 88 4.6.3. Ứng dụng của ngăn xếp (xử lý biểu thức) „ Để minh hoạ ta xét biểu thức trung tố: 5×(((9+8) × (4+6))+7) 5×((17×10)+7) 5×(170+7) 5× 177 885 „ Ký pháp hậu tố (PRN) ‰ Là ký pháp để trình bày một biểu thức, theo đó toán hạng đặt trước toán tử. ‰ Do nhà toán học BaLan, Jan Lukasiewicz đề xuất vào đầu những năm 50 của thể kỷ trước nên có tên gọi là ký pháp nghịch đảo BaLan (Polish Reverse Notation – PRN). ‰ Biểu thức (a+b)*c trong ký pháp trung tố được viết lại là a b+ c * „ Biểu thức ở hình bên có thể viết lại là: 5 9 8 + 4 6 + × 7+ × 5 17 10 × 7 + × 5 170 7 + × 5 177 × 885 „ Rõ ràng cách viết này có ưu điểm là không cần đễn các dấu ngoặc, đồng thời quá trình tính giá trị của biểu thức này được minh họa bởi hình vẽ sau 4.6.3. Ứng dụng của ngăn xếp (xử lý biểu thức) „ Ta sẽ lưu trữ các toán hạng cho đến khi một toán tử (phép toán) xuất hiện. Với phép toán này hai toán hạng cuối cùng (trong danh sách các toán hạng đã được lưu trữ) sẽ được lấy ra và sau khi thực hiện phép toán, kết quả lại được đưa vào để lưu trữ. Do đó việc sử dụng một ngăn xếp là hợp lý. 5 9 8 + 4 6 + × 7+ × 5 17 10 × 7 + × 5 170 7 + × 5 177 × 885 5 9 8 17 4 6 10 170 7 7 885 89 4.6.3. Ứng dụng của ngăn xếp (xử lý biểu thức) „ Thuật toán để tính giá trị một biểu thức dạng RPN Khởi tạo một ngăn xếp rỗng Lặp Đọc thành phần (tiếp theo) trong biểu thức Nếu là một toán hạng thì đặt nó vào ngăn xếp nếu không (tức là toán tử-phép toán) thì lặp nếu ngăn xếp rỗng thì biểu thức có lỗi thoát ra khỏi thuật toán nếu không thì lấy ra khỏi ngăn xếp một phần tử cho đến khi lấy đủ hai phần tử Thực hiện phép toán vừa đọc với hai phần tử vừa được lấy ra Đặt kết quả vào ngăn xếp cho đến khi có dấu hiệu kết thúc biểu thức Bắt đầu Khởi tạo(s) Đọc thành phần (tiếp theo) của biểu thức Báo lỗi b thức (Return 0) Kết thúc Là toán hạng_ La_Rong(s) _ Push(s,toán hạng) Push(s, op(Tam[1],tam[2])) + + i=i++; tam[i]=pop(s); i<2+ i=0 Hết biểu thức Return pop(s) _ +_ Hết biểu thức + _ 90 4.6.3. Ứng dụng của ngăn xếp (xử lý biểu thức) „ Thuật toán đổi một biểu thức dạng trung tố thành một biểu thức dạng RPN. ‰ Để chuyển một biểu thức dạng trung tố sang dạng RPN (hậu tố) ta cần phải thực hiện các thao tác nào? Để xây dựng thuật toán chuyển đổi này ta hãy xem xét một ví dụ: 5 ×((9+8) × (4+6)+7)=5 ((9 8 +) (4 6 +) × )7+ × 5 9 8 + 4 6 + × 7+ × ‰ và một ví dụ khác: (7+5)/2-3 × 2=((7+5)/2)-(3 × 2)=7 5 + 2 / 3 2 × - ‰ Nó sẽ được thực hiện bằng cách lần lượt đọc từ trái qua phải các thành phần của biểu thức trung tố. Các ký hiệu phép toán (toán tử) và các dấu mở ngoặc sẽ được đặt vào một ngăn xếp tạm thời trước khi được viết nghép với các toán hạng, các toán hạng sẽ được viết ra ngay trong biểu thức RPN khi đọc thấy chúng trong biểu thức trung tố. Cụ thể là: 4.6.3. Ứng dụng của ngăn xếp (xử lý biểu thức) Khởi tạo một ngăn xếp rỗng Lặp Đọc thành phần (tiếp theo) trong biểu thức Nếu thành phần là toán hạng thì viết ra nếu không thì (nó là dấu ngoặc để quy định mức độ ưu tiên hoặc là một toán tử) Nếu là dấu '(' (dấu ngoặc trái) thì đặt nó vào ngăn xếp Nếu là dấu ')' (dấu ngoặc phải) thì Lặp Lấy ra phần tử thuộc ngăn xếp Nếu phần tử này không phải là dấu '(' thì viết ra cho đến khi phần tử được lấy ra là dấu '(‘ Nếu là dấu toán tử thì (chắc chắn phải được đặt vào ngăn xếp) Nếu ngăn xếp khác rỗng thì 91 4.6.3. Ứng dụng của ngăn xếp (xử lý biểu thức) Lặp Lấy ra phần tử ở đỉnh của ngăn xếp Nếu phần tử vừa lấy ra này được ưu tiên hơn toán tử đang xét thì viết phần tử vừa lấy ra cho đến khi toán tử đang xét được ưu tiên hơn phần tử vừa lấy ra hoặc ngăn xếp rỗng Nếu toán tử đang xét được ưu tiên hơn phần tử vừa lấy ra thì đặt trả lại ngăn xếp phần tử vừa lấy ra Đặt toán tử đang xét vào ngăn xếp nếu không thì đặt toán tử đang xét vào ngăn xếp cho đến khi gặp dấu kết thúc biểu thức Khi ngăn xếp đang còn thì lấy ra và viết các phần tử của ngăn xếp. Bắt đầu Khởi tạo(s) Đọc thành phần-tp (tiếp theo) của b thức ttố Là toán hạng(tp)_ + Viết tiếp(bt,tp)La((tp) La)(tp) Latt(tp) Push(s,tp) Pt=pop(s) La((pt) Viết tiếp(bt,pt) La_Rong(s)_ + Push(s,tp) Pt=pop(s) Pt >=tp Viết tiếp(bt,Pt) + _ Push(s,pt) Hết biểu thức+ _La_Rong(s) Kết thúc Viết tiếp(bt,pop(s) _ + + _ 92 4.6.4. Hàng đợi và các thao tác cơ bản trên các hàng đợi „ Định nghĩa: ‰ Một hàng đợi (queue) là một mô hình (cơ cấu) mà tác động bổ sung vào nó được thực hiện ở một phía của nó và tác động loại bỏ một phần tử được thực hiện ở phía còn lại. ‰ Trong tin học, một hàng đợi là một danh sách tuyến tính mà thao tác bổ sung chỉ được thực hiện ở một đầu và thao tác bớt đi được thực hiện ở phía còn lại của nó. „ Ví dụ: ‰ Ta hình dung hàng đợi như một dãy người xếp hàng tại một quầy hàng để mua một mặt hàng nào đó mà chỉ có thể thêm vào hàng đợi từ cuối và bớt đi phần tử ở đầu của hàng đợi. ‰ Một vài ví dụ khác: „ Một dãy các công việc trong một hệ thống máy tính đang chờ một thiết bị nào đó (chẳng hạn như máy in). „ Một dãy máy bay đang trong đường dẫn ra đường băng để chuẩn bị cất cánh 4.6.4. Hàng đợi và các thao tác cơ bản trên các hàng đợi „ Hàng đợi là một cấu trúc dữ liệu trừu tượng, là một danh sách tuyến tính. Tuy nhiên điểm khác căn bản, có thể xem như đối lập với ngăn xếp là trong khi ngăn xếp hoạt động theo nguyên lý vào sau - ra trước (LiFo Last in - First out) thì hàng đợi hoạt động theo nguyên lý vào trước - ra trước (FiFo First in - First out). Kiểm tra an ninh tại ga hàng không (security check) 93 4.6.4. Hàng đợi và các thao tác cơ bản trên các hàng đợi „ Với kiểu hàng đợi, ta quy ước chỉ có thể thực hiện các thao tác sau: ‰ Khởi tạo một hàng đợi. ‰ Đặt (put) một phần tử mới vào hàng đợi nếu hàng đợi chưa đầy. Phần tử dữ liệu mới luôn được thêm tại đuôi. ‰ Nhận lại (get) một phần tử từ hàng đợi nếu hàng đợi khác rỗng. Phần tử bị loại là phần tử đang nằm tại đầu. ‰ Kiểm tra xem hàng đợi có hay không có phần tử (rỗng hay không). ‰ Kiểm tra xem hàng đợi đã đầy hay chưa ‰ Mọi tác động khác vào hàng đợi đều phải thông qua các thao tác này. „ Như vậy: ‰ Các phần tử của hàng đợi có cùng một kiểu nào đó ‰ Hàng đợi là một trường hợp riêng của danh sách, được sử dụng trong các ứng dụng có liên quan đến sự bâor tồn thứ tự. Trong CTDL hàng đợi, dữ liệu thêm vào trước sẽ lấy ra trước, tính chất này còn được gọi là vào trước ra trước (First In First Out -FIFO). ‰ Vì vậy, từ nay về sau khi nói đến hàng đợi ta hiểu đó là danh sách kiểu FIFO 4.6.5. Mô hình thiết kế hàng đợi „ Thực hiện mô hình hóa hàng đợi ‰ Ta cần tạo một cấu trúc danh sách tuyến tính và chuẩn bị các thao tác để có thể làm việc với danh sách này với tư cách là một hàng đợi „ Cần định nghĩa một kiểu danh sách để coi nó như hàng đợi, bao gồm cấu trúc dữ liệu được sử dụng và các đối tượng làm đầu và đuôi của hàng đợi. Do đó có thể chọn danh sách liên kết đơn với một con trỏ đến đầu danh sách và một con trỏ trỏ đến cuối (đuôi) hoặc mảng một chiều với hai tham số nguyên chỉ vị trí đầu và đuôi của hàng đợi. „ Đôi khi cần gắn thêm một biến nguyên để lưu trữ thông tin về kích thước thực tế của hàng đợi. „ Cần tạo các thủ tục/hàm để thao tác trên danh sách này với tư cách là thao tác hàng đợi bao gồm 5 thao tác đã nói ở trên. 94 4.6.5. Mô hình thiết kế hàng đợi (Mô hình danh sách liên kết của hàng đợi) „ Mô hình danh sách liên kết của hàng đợi ‰ Cấu trúc dữ liệu của mỗi phần tử thuộc hàng đợi sẽ chính là một bản ghi gồm các trường nội dung và một trường kiểu con trỏ làm nhiệm vụ liên kết. ‰ hàng đợi Q là một danh sách được quản lý bởi con trỏ danh sách H trỏ tới đầu và một con trỏ phụ T trỏ đến đuôi cùng các thao tác khởi tạo, put, get, kiểm tra rỗng, kiểm tra đầy sẽ được tham số hóa bởi các hàm/thủ tục: khoitao(H,T), put(H,T,pt), get(H,T), la_rong(H,T), la_day(H,T) ‰ Việc lưu trữ dữ liệu vào hàng đợi Q thực chất là việc thực hiện một hay nhiều lần thao tác put(H,T,pt) với H là con trỏ dùng để quản lý hàng đợi (trỏ đến đỉnh của nó), T là con trỏ để tiện bổ sung phần tử và pt là một phần tử dữ liệu cần lưu trữ. ‰ Việc lấy dữ liệu ra khỏi hàng đợi được làm tuần tự bằng các thao tác get(H,T). 4.6.5. Mô hình thiết kế hàng đợi (Mô hình danh sách liên kết của hàng đợi) „ Khai báo và thủ tục/hàm trong Pascal „ Khai báo và hàm trong C 95 4.6.5. Mô hình thiết kế hàng đợi (Mô hình mảng của hàng đợi) „ Mô hình mảng của hàng đợi ‰ Cấu trúc dữ liệu của mỗi phần tử thuộc hàng đợi sẽ chính là cấu trúc dữ liệu của phần tử của mảng. ‰ Hàng đợi q là một cấu trúc/bản ghi gồm một mảng các phần tử dữ liệu được quản lý kèm theo hai biến đầu, đuôi (số nguyên) để xác định vị trí của đầu và đuôi của hàng đợi, một biến nguyên chỉ kích thước hiện thời của nó và các thao tác khởi tạo, put, get, kiểm tra rỗng, kiểm tra đầy sẽ được tham số hóa bởi các hàm/thủ tục: khoitao(q), put(q,pt), get(q), la_rong(q), la_day(q) ‰ Vì mảng có kích thước cố định nên hàm kiểm tra đầy (la_day(q)) là cần thiết. ‰ Một điểm cần lưu ý khi cài đặt hàng đợi bởi mảng „ Trong quá trình xử lý dữ liệu, nếu không khéo thì gây lãng phí ô nhớ trong khi vẫn bị báo tràn (đầu và đuôi tăng liên tục). „ Do đó cần “Xử lý quay vòng”. 4.6.5. Mô hình thiết kế hàng đợi (Mô hình mảng của hàng đợi) 96 4.6.5. Mô hình thiết kế hàng đợi (Mô hình mảng của hàng đợi) 1 2 Đầu Đuôi 1 2 Đầu 1 2 Đầu 3 3 4 2 ĐầuĐuôi 4 Đầu Đuôi 5 Đầu Đuôi 3 3 4 3 4 Đuôi Đuôi 1 2 4.6.5. Mô hình thiết kế hàng đợi (Mô hình mảng của hàng đợi) „ Các giải thuật ‰ Khai báo cấu trúc và biến hàng đợi (q) gồm „ Mảng (động) lưu trữ các phần tử dữ liệu (qarr) với kích thước tối đa là maxsize „ Các biến nguyên (dau, duoi) để trỏ tường minh đến đầu và đuôi của hàng đợi „ Biến nguyên (kth) để xác định kích thước hiện thời của hàng đợi ‰ Khoitao(q) /*tạo hàng đợi q rỗng*/ Cấp mảng lưu dữ liệu với kích thước maxsize; Dau=duoi=-1; Kth=0; 97 4.6.5. Mô hình thiết kế hàng đợi (Mô hình mảng của hàng đợi) „ La_day(q) /* hàng đợi đầy */ return( q->kth == q->maxsize); „ Put(q,pt) /*đặt vào đuôi hàng đợi q phần tử dữ liệu pt*/ (q->duoi)++; If (q->duoi == q->maxsize) /* Queue wraps to element 0 */ q->duoi = 0; q->qarr[q->duoi] = pt; (q->kth)++; if(q->kth == 1) /* Inserting into null queue */ q->dau = 0; return; 4.6.5. Mô hình thiết kế hàng đợi (Mô hình mảng của hàng đợi) „ La_rong(q) /* hàng đợi rỗng*/ return(q->kth == 0); „ Get (q) /*lấy ra từ đầu hàng đợi q phần tử dữ liệu */ Pt=q->qarr[q->dau]; /* gán giá trị cho biến ra pt*/ (Q->dau)++ if(q->dau == q->maxsize) q->dau = 0; /* queue front has wrapped to element 0 */ if(q->kth == 1) /* Deleted only item in queue */ q->duoi = q->dau = -1; (q->kth)--; Return pt; 98 4.6.5. Mô hình thiết kế hàng đợi (Mô hình mảng của hàng đợi) „ Khai báo và hàm trong C typedef struct chqueue{ ch *qarr; int maxsize; int kth; int dau; int duoi; }IntQueue; duoidaukth max size qarr 48710 9876543210 !eueuqsiti dauduoi Chương 5. Cây 5.1. Cây và các khái niệm về cây 5.2. Các phép toán trên cây 5.3. Cài đặt cây 5.4. Cây nhị-phân 99 5.1. Cây và các khái niệm về cây 5.1.1. Định nghĩa cây 5.1.2. Các khái niệm liên quan 5.1.3. Cây được sắp 5.1.4. Ví dụ 5.1.1. Định nghĩa cây „ Sự cần thiết phải sử dụng cấu trúc cây ‰ Danh sách tuyến tính chỉ thể hiện được các mối quan hệ tuyến tính. ‰ Thông tin còn có thể có quan hệ dạng phi tuyến, „ Định nghĩa cây (có gốc) ‰ Là một danh sách T khác rỗng trong đó „ Hoặc T chỉ bao gồm một phần tử r. „ Hoặc nếu nhiều hơn một phần tử r thì r gọi là gốc và có một quan hệ F trên nó để phần còn lại (trừ gốc r) được chia thành m (m>0) cây với các gốc r1, r2,,rm sao cho với mọi i (1 ≤ i ≤ m) đều có r F ri.. Quan hệ F được gọi là quan hệ cha- con. ‰ Nếu x F y thì ta gọi x là cha của y hoặc y là con của x. ‰ Các cây với các gốc r1, r2,,rm được gọi là các cây con của cây r 100 5.1.1. Định nghĩa cây ‰ Biểu diễn cây bởi đồ thị ‰ Mỗi phần tử thuộc T từ nay được gọi là một đỉnh của cây A IE JD G C F B H L K 5.1.2. Các khái niệm liên quan „ Số các con của một đỉnh gọi là bậc (cấp) của đỉnh đó. „ Các đỉnh có bậc 0 được gọi là lá của cây. „ Các đỉnh có ít nhất một con được gọi là đỉnh trong. „ Các con có cùng một cha được gọi là anh em. „ Một dãy các đỉnh a1, a2, ... an (n ≥ 1), sao cho ai (i = 1, 2, ... , n-1) là cha của ai+1 được gọi là đường đi trong quan hệ cha-con từ a1 đến an. Độ dài của đường đi này là n-1. „ Nếu có một đường đi từ đỉnh a đến đỉnh b có độ dài k ≥ 1, thì ta nói a là tiền thân của b và b là hậu thế của a. „ Độ dài của đường đi dài nhất từ đỉnh a đến một lá được gọi là độ cao của đỉnh a. „ Độ cao của gốc được gọi là độ cao của cây. „ Độ dài của đường đi từ gốc đến a được gọi là mức (độ sâu) của đỉnh a. 101 5.1.2. Các khái niệm liên quan ‰ Như vậy, từ các định nghĩa trên ta suy ra rằng: „ Mỗi đỉnh của cây là gốc của các con của nó. „ Lá là đỉnh không có con. „ Các đỉnh của cây hoặc là lá hoặc là đỉnh trong. „ Luôn luôn tồn tại một đường đi duy nhất trong quan hệ cha-con F từ gốc tới một đỉnh bất kỳ trong cây. „ Với mọi x,y (x ≠ r ≠ y) thuộc T đều tồn tại một phần tử z thuộc T để có một đường đi trong quan hệ F từ z đến x và một đường đi trong quan hệ F từ z đến y. „ Gốc của cây có mức 0. 5.1.2. Các khái niệm liên quan ‰ Ví dụ. Trong cây ở bên: „ Đỉnh C là cha của các đỉnh D,E. „ Các đỉnh D,E,I,J,K, F, L là lá, các đỉnh còn lại là đỉnh trong. „ A,B,C,E là đường đi có độ dài 3 từ A đến E. „ Đỉnh B là tiền thân của các đỉnh C,F,D,E. „ Đỉnh B có độ cao là 2, cây có độ cao là 3. Các đỉnh B,G có mức 1 ; các đỉnh C,F,H,L có mức 2, còn mức của các đỉnh D,E,I,J,K là 3. A IE JD G C F B H L K 102 5.1.3. Cây được sắp „ Trong một cây, nếu các cây con của mỗi đỉnh được sắp theo một thứ tự nhất định, thì cây được gọi là cây được sắp (từ trái qua phải). „ Sau này chúng ta chỉ quan tâm đến các cây được sắp. Do đó khi nói đến cây thì cần được hiểu là cây được sắp. „ Giả sử trong một cây được sắp T, đỉnh a có các con được sắp theo thứ tự : b1, b2, ..., bk (k ≥ 1). Khi đó ta nói b1 là con trưởng của a, và bi là anh liền kề của bi+1 (bi+1 là em liền kề của bi), i = 1,2, ..., k-1. Ta còn nói, với i < j thì bi ở bên trái bj (bj ở bên phải bi). „ Quan hệ này được mở rộng như sau: Nếu a ở bên trái b thì mọi hậu thế của a ở bên trái mọi hậu thế của b. „ Ví dụ. ‰ Trong cây đã cho I là con trưởng của H, và là anh liền kề của đỉnh J. Đỉnh K là con út của H (ở tận cùng bên bên phải trong số các con của H. 5.1.4. Ví dụ „ Cây biểu diễn các tổ chức „ Cây thư mục Chính phủ Bộ BBộ A Bộ Z Ban sBan r Sở X Cục Y Vụ T 103 5.2. Các phép toán trên cây 5.2.1. Các phép toán cơ bản trên cây 5.2.2. Đi qua cây (duyệt cây) 5.2.1. Các phép toán cơ bản trên cây „ Tìm cha của mỗi đỉnh ‰ Để tìm cha của mỗi đỉnh x, cần thiết phải xây dựng hàm Parent(x) trả về địa chỉ là địa chỉ của đỉnh cha của x. Trường hợp x là gốc hàm có thể trả về NULL. „ Tìm con bên trái ngoài cùng (con truởng) của mỗi đỉnh. ‰ Hàm EldestChild (x) cho ta con trưởng của đỉnh x. Trong trường hợp x là lá (x không có con) thì EldestChild (x) = NULL. „ Tìm em liền kề của mỗi đỉnh. ‰ Hàm NextSibling (x) xác định em liền kề của đỉnh x. Trong trường hợp x không có em liền kề (tức x là con ngoài cùng bên phải của một đỉnh nào đó) thì NextSibling(x) = NULL. 104 5.2.1. Các phép toán cơ bản trên cây „ Ví dụ. Giả sử T là cây đã cho trong hình bên. Khi đó ‰ Parent(E) = C, Parent(A) = NULL, ‰ EldestChild(C) = D, EldestChild(H) = I, EldestChild(K) = NULL, ‰ NextSibling(g) = NULL, NextSibling(H) = L. A IE JD G C F B H L K 5.2.2. Đi qua cây (duyệt cây) „ Do định nghĩa cây mang tính đệ quy nên các thuật toán trên cây cũng thường được sử dụng bởi đệ quy. „ Duyệt tiền thứ tự ‰ Nếu T là cây gồm một đỉnh duy nhất thì đỉnh (Thăm gốc) ‰ Nếu là cây có gốc (thì „ Thăm gốc „ Duyệt cây con thứ nhất theo tiền thứ tự. „ Duyệt các cây con còn lại theo tiền thứ tự. ‰ Trong cây bên, thứ tự các đỉnh được duyệt theo tiền thứ tự là A B C D E F G H I J K L A IE JD G C F B H L K 105 5.2.2. Đi qua cây (duyệt cây) „ Duyệt trung thứ tự ‰ Nếu T là cây gồm một đỉnh duy nhất thì thăm đỉnh (Thăm gốc). ‰ Nếu là cây có gốc thì „ Duyệt cây con thứ nhất theo trung thứ tự. „ Thăm gốc „ Duyệt các cây con còn lại theo trung thứ tự. ‰ Trong cây bên, thứ tự các đỉnh được duyệt theo trung thứ tự là D, C, E, B, F, A, I, H, J, K, G, L. A IE JD G C F B H L K 5.2.2. Đi qua cây (duyệt cây) „ Duyệt hậu thứ tự ‰ Nếu T là cây gồm một đỉnh duy nhất thì thăm đỉnh (Thăm gốc). ‰ Nếu là cây có gốc thì „ Duyệt cây con thứ nhất theo hậu thứ tự. „ Duyệt các cây con còn lại theo hậu thứ tự. „ Thăm gốc ‰ Trong cây bên, thứ tự các đỉnh được duyệt theo hậu thứ tự là D, E, C, F, B, I, J, K, H, L, G, A. A IE JD G C F B H L K 106 5.3. Cài đặt cây 5.3.1. Biểu diễn cây bằng danh sách các con của mỗi đỉnh 5.3.2. Biểu diễn cây bằng con trưởng và em liền kề của mỗi đỉnh 5.3.3. Biểu diễn cây bởi cha của mỗi đỉnh 5.3.1. Biểu diễn cây bằng danh sách các con của mỗi đỉnh „ Để cài đặt cây, về nguyên tắc là phải lưu trữ được cây (tập hợp) và thông tin vế quan hệ cha-con giữa các đỉnh. „ Phương pháp thông dụng để biểu diễn cây là, với mỗi đỉnh của cây ta thành lập một danh sách các đỉnh con của nó theo thứ tự từ trái sang phải. „ Cài đặt bởi mảng: ‰ sử dụng một mảng để lưu giữ các đỉnh của cây. Mỗi thành phần của mảng là một tế bào chứa thông tin gắn với mỗi đỉnh và danh sách các đỉnh con của nó. A IE JD G C F B H L K 107 5.3.1. Biểu diễn cây bằng danh sách các con của mỗi đỉnh 1 2 3 4 5 6 7 8 9 10 11 12 A B G C F H L D E I J K A IE JD G C F B H L K 2 3 4 5 1 3 10 11 6 12 5 2 74 8 9 6 7 8 9 10 11 12 Các đỉnh của cây được đánh số từ 1 đến N 5.3.1. Biểu diễn cây bằng danh sách các con của mỗi đỉnh „ Vì số con của mỗi đỉnh có thể khác nhau nhiều, cho nên ta sẽ sử dụng danh sách liên kết. Như vậy mỗi phần tử mảng dùng để mô tả đỉnh của cây là một bản ghi gồm hai trường : trường DL chứa thông tin gắn với đỉnh, trường trocon là con trỏ, trỏ tới danh sách các con của đỉnh đó. const N = ... ; { N là số lớn nhất các đỉnh mà cây có thể có } type tropt = ^kcon : kcon = record id : 1..N ; kesau: tropt end ; kptu = record DL : kieudl ; trocon : tropt end ; kcay = array [1 ... N] of kptu ; 108 5.3.1. Biểu diễn cây bằng danh sách các con của mỗi đỉnh „ trong cách cài đặt này, với mỗi đỉnh k ta xác định ngay vị trí của con trưởng của nó trong mảng T có kiểu kcay bởi hàm sau. „ function EldestChild ( k : 1..N ; T : kCay): 0..N ; „ var P : tropt ; „ begin „ if T[k].trocon nil then „ begin „ P : = T[k]. trocon ; „ EldestChild : = P^. id ; „ end „ else EldestChild: = 0 „ end ; 5.3.1. Biểu diễn cây bằng danh sách các con của mỗi đỉnh „ Tuy nhiên trong cách cài đặt này, việc tìm cha và em liền kề của mỗi đỉnh lại không đơn giản. Chẳng hạn, để tìm cha của đỉnh k, ta phải duyệt các danh sách các con của mỗi đỉnh. Nếu phát hiện ra trong danh sách các con của đỉnh m có chứa k thì Parent (k) = m. Hàm Parent (k) được xác định như sau : Function Parent (k : 1..N ; T : kCay) : 0..N ; var P : tropt ; i : 1 ... N ; found : boolean ; begin i : = 1 ; found : = false ; 109 5.3.1. Biểu diễn cây bằng danh sách các con của mỗi đỉnh while ( i < = N) and (not found) do begin P : = T[i].trocon ; while (P nil) and (not found) do if P^.id = k then begin Parent : = i : found : = true ; end else P : = P^.kesau ; i: = i + 1 end ; if not found then Parent : = 0 ; end ; 5.3.1. Biểu diễn cây bằng danh sách các con của mỗi đỉnh „ Bằng cách tương tự (duyệt các danh sách các con), ta cũng có thể tìm được em liền kề của mỗi đỉnh. „ Mô tả chi tiết hàm NextSibling được để lại xem như bài tập. 110 5.3.1. Biểu diễn cây bằng danh sách các con của mỗi đỉnh „ Cài đặt bởi con trỏ ‰ Có thể sử dụng các con trỏ trỏ tới các đỉnh của cây. Tại mỗi đỉnh, ta sẽ sử dụng một danh sách các con trỏ trỏ tới các con của nó, danh sách này được cài đặt bởi mảng các con trỏ. Một con trỏ Root được sử dụng để trỏ tới gốc của cây. Ta có thể khai báo cấu trúc dữ liệu biểu diễn cây trong cách cài đặt này như sau. ‰ const K = ..... ; {K là số tối đa các con của mỗi đỉnh} ‰ type tropt = ^Node ; ‰ Node = record ‰ infor : item ; ‰ child : array [1...K] of tropt ‰ end ; ‰ var Root : tropt ; 5.3.1. Biểu diễn cây bằng danh sách các con của mỗi đỉnh Trường dữ liệu Mảng các con trỏ A B G LFC D E K H JI 111 5.3.1. Biểu diễn cây bằng danh sách các con của mỗi đỉnh „ Giả sử P là một con trỏ trỏ tới một đỉnh nào đó trong cây, ta sẽ gọi đỉnh này là đỉnh P. Sau đây ta sẽ xét xem phép toán tìm cha của nó Parent (P) được thực hiện như thế nào. „ Tư tưởng của thuật toán tìm cha của đỉnh P cũng không có gì khác trước, khi cây cài đặt bởi mảng, tức là ta cũng phải duyệt các đỉnh con của mỗi đỉnh. ‰ Khi các đỉnh của cây được lưu trong mảng, việc đi lần lượt qua các đỉnh của cây để xét các con của nó được thực hiện rất dễ dàng. ‰ Ta sẽ sử dụng một hàng đợi H để lưu các đỉnh đã được xét. „ Đầu tiên hàng đợi chứa gốc Root của cây. „ Tại mỗi thời điểm ta sẽ loại đỉnh Q ở đầu hàng ra khỏi hàng và xét các con của nó. „ Nếu một trong các đỉnh con của Q là P thì Parent (P) = Q, „ Ngược lại ta sẽ đưa các đỉnh con của Q vào cuối hàng. 5.3.1. Biểu diễn cây bằng danh sách các con của mỗi đỉnh ‰ Hàm Parent được xác định như sau. function Parent (P : tropt ; Root : tropt) : tropt ; var Q, R : tropt ; H : Queue ; found : boolean ; begin Initialize (H) ; {khởi tạo hàng rỗng H} Addqueue (Root, H) ; {Đưa Root vào hàng} found : = false ; while (not Emty (H) and (not found) do begin DeleteQueue (H, Q) ; {Loại Q khỏi đầu hàng} i: = 0 ; 112 5.3.1. Biểu diễn cây bằng danh sách các con của mỗi đỉnh repeat i : = i + 1 ; R : = Q^. child [i] ; if R nil then if R = P then begin Parent : = Q found : = true end else AddQueue (R, H) until found or (R = nil) or (i = N) end ; if not found then Parent : = nil end ; „ Một cách hoàn toàn tương tự, ta có thể viết được hàm tìm em liền kề NextSibling. 5.3.2. Biểu diễn cây bằng con trưởng và em liền kề của mỗi đỉnh „ Cài đặt bởi mảng. ‰ Giả sử các đỉnh của cây được đánh số từ 1 đến N. Dùng mảng để lưu giữ các đỉnh của cây, mỗi đỉnh được biểu diễn bởi bản ghi gồm ba trường, ngoài trường infor, các trường EldestChild và Nexsibling sẽ lưu con trưởng và em liền kề của mỗi đỉnh. Ta có thể khai báo như sau : type kieupt = record DL : kieudl ; EldestChild : 0...N ; NextSibling : 0...N end ; Tree = array[1...N] of kieupt ; 113 5.3.2. Biểu diễn cây bằng con trưởng và em liền kề của mỗi đỉnh 00K12 120J11 110I10 00E9 90D8 00L7 00F6 710H5 58C4 06G3 34B2 02A1 Em kềCon trưởng Dữ liệu A IE JD G C F B H L K 1 3 10 11 6 12 5 2 74 8 9 5.3.2. Biểu diễn cây bằng con trưởng và em liền kề của mỗi đỉnh „ Để tìm cha của một đỉnh k nào đó, ta sẽ lần lượt đi qua các đỉnh của cây, với mỗi đỉnh ta tìm đến các con của nó, cho tới khi tìm thấy đỉnh k: Function Parent(k:1..N;T:Tree):0.. N; „ var i, j : 0 ... N ; found: boolean ; „ begin „ i : = 1 ; „ found : = false ; „ while (i <=N) and (not found) do „ begin „ j : = T[i]. EldestChild ; „ if j = k then „ begin „ Parent : = i ; found : = true „ end „ else „ begin „ j : = T[j]. NextSibling ; „ while (j 0) and (not found) do if j = k then „ begin „ Parent : = i ;found : = true „ end „ else j : = T[j].NextSibling ; „ end ; „ i : = i+1 „ end ; „ if not found then Parent : = 0 „ end ; 114 5.3.2. Biểu diễn cây bằng con trưởng và em liền kề của mỗi đỉnh „ Cài đặt bởi con trỏ. ‰ Thay cho dùng mảng, ta có thể sử dụng các con trỏ để cài đặt. Khi đó trong bản ghi Node, các trường EldestChild và NextSibling sẽ là các con trỏ. Cây sẽ được biểu diễn bởi cấu trúc sau. ‰ type tropt=^Node ; ‰ Node = record ‰ DL : kieudl; ‰ EldestChild : tropt ; ‰ NextSibling : tropt ; ‰ end ; ‰ var Root : tropt ; 5.3.2. Biểu diễn cây bằng con trưởng và em liền kề của mỗi đỉnh Trường dữ liệu A B G C F H L D E J KI Trỏ conTrỏ em 115 5.3.3. Biểu diễn cây bởi cha của mỗi đỉnh „ Trong một số áp dụng, người ta còn có thể sử dụng cách biểu diễn cây đơn giản sau đây. Giả sử các đỉnh của cây được đánh số từ 1 đến N. Dựa vào tính chất, mỗi đỉnh của cây (trừ gốc) đều có một cha, ta sẽ dùng một mảng A[1...N] để biểu diễn cây, trong đó A[k] = m nếu đỉnh m là cha của đỉnh k. Trong trường hợp cần quan tâm đến các thông tin gắn với mỗi đỉnh, ta cần phải đưa vào mỗi thành phần của mảng trường DL mô tả thông tin ở mỗi đỉnh. Cây được biểu diễn bởi cấu trúc sau. „ const N = ... ; „ type Node = record „ DL: Kieudl; „ parent : 0 ...N ; „ end ; „ Tree = array [1...N] of Node ; „ var T : Tree ; 5.3.3. Biểu diễn cây bởi cha của mỗi đỉnh 6K12 6J11 6I10 4E9 4D8 3L7 3H6 2F5 2C4 1G3 1B2 0A1 ChaDữ liệu A IE JD G C F B H L K 1 3 10 11 6 12 5 2 74 8 9 116 5.4. Cây nhị phân 5.4.1. Định nghĩa và tính chất 5.4.2. Cài đặt cây nhị phân 5.4.3. Duyệt cây nhị phân 5.4.4. Cây tìm kiếm nhị phân 5.4.1. Định nghĩa và tính chất „ Một tập các đỉnh T được gọi là cây nhị phân nếu ‰ Nó là cây rỗng, hoặc ‰ Gồm 3 tập con không trùng nhau: 1. Một đỉnh gốc 2. Cây nhị phân con trái 3. Cây nhị phân con phải „ Mỗi đỉnh có nhiều nhất 2 đỉnh con: ‰ Con trái và Con phải R B A E C F D 117 5.4.1. Định nghĩa và tính chất „ Cây nhị phân đầy đủ là cây nhị phân trong đó các đỉnh hoặc là lá hoặc có cấp bằng 2 „ Cây nhị phân hoàn chỉnh là cây trong đó tất cả lá đều có cùng mức và tất cả đỉnh trong có cấp bằng 2. A K JI FE GD HC B GFDC EB A 5.4.1. Định nghĩa và tính chất „ Một số tính chất ‰ Số tối đa các đỉnh có mức i là 2i ‰ Với cây nhị phân „ có độ cao H, số tối đa các đỉnh là 2H+1 - 1 „ có N đỉnh, ‰ độ cao H tối đa là N -1 ‰ độ cao H tối thiểu là [log2(N+1)] -1 118 5.4.2. Cài đặt cây nhị phân „ Lưu trữ kế tiếp (Dùng mảng) ‰ Sắp thứ tự các đỉnh từ mức 0 trở đi và trong mỗi mức được đánh số từ trái sang phải. ‰ Đối với các cây nhị phân hoàn chỉnh „ Dễ xác định địa chỉ của các đỉnh ‰ Con của đỉnh i là các đỉnh 2i và 2i+1 ‰ Cha của đỉnh i là [i/2]. „ Do đó mỗi thành phần của mảng chỉ cần trường lưu trữ dữ liệu mà không cần các trường thông tin về quan hệ. ‰ Đối với các cây nhị phân khác, mỗi thành phần của mảng nên có thêm 2 trường: địa chỉ (chỉ số) của cây con trái và của cây con phải. 5.4.2. Cài đặt cây nhị phân „ Lưu trữ móc nối (dùng DS liên kết). A G B C FD H L K I J Trường dữ liệu Trỏ trái Trỏ phải 119 5.4.2. Cài đặt cây nhị phân „ Typedef struct kpt { kieudl DL; struct kpt *trai; Struc kpt *phai; }KieuPT; 5.4.2. Cài đặt cây nhị phân Trường dữ liệu A B G C F H L D E J KI Trỏ conTrỏ em 120 5.4.3. Duyệt cây nhị phân. „ Cũng như đối với cây, trong nhiều áp dụng ta cần phải duyệt cây nhị phân, thăm tất cả các đỉnh của cây một cách hệ thống „ Giả sử với mỗi đỉnh của cây ta cần thực hiện một nhóm hành động nào đó được mô tả trong thủ tục Visit. „ Chúng ta thường duyệt cây nhị phân theo một trong ba thứ tự Preorder, Inorder và Portorder. „ Sau đây là thủ tục đệ quy duyệt cây theo thứ tự Preorder. „ procedure Preorder (Root : tropt) ; „ begin „ if Root nil then „ begin „ Visit (Root) ; „ Preorder (Root^. left) ; „ Preorder (Root^.right) ; „ end „ end ; 5.4.3. Duyệt cây nhị phân „ Một cách tương tự, ta có thể viết được các thủ tục đệ quy đi qua cây theo thứ tự Inordor và Postorder. „ Một ví dụ cây nhị phân: cây biểu thức. ‰ Cây biểu thức là cây nhị phân gắn nhãn, biểu diễn cấu trúc của một biểu thức (số học hoặc logic). ‰ Mỗi phép toán hai ngôi (chẳng hạn, +, -, *, /) được biểu diễn bởi cây nhị phân, gốc của nó chứa ký hiệu phép toán, cây con trái biểu diễn toán hạng bên trái, còn cây con phải biểu diễn toán hạng bên phải. ‰ Với các phép toán một ngôi như 'phủ định' hoặc 'lấy giá trị đối', hoặc các hàm chuẩn như exp ( ) hoặc cos( ) thì cây con bên trái rỗng. ‰ Còn với các phép toán một toán hạng như phép lấy đạo hàm ( )' hoặc hàm giai thừa ( )! thì cây con bên phải rỗng. 121 5.4.3. Duyệt cây nhị phân „ Ta có nhận xét: ‰ nếu đi qua cây biểu thức theo thứ tự Preorder ta sẽ được biểu thức Balan dạng PFN (ký hiệu phép toán đứng trước các toán hạng). ‰ Nếu đi qua cây biểu thức theo thứ tự Postorder, ta có biểu thức Balan dạng PRN (ký hiệu phép toán đứng sau các toán hạng); ‰ còn theo thứ tự Inorder ta nhận được cách viết thông thường của biểu thức (ký hiệu phép toán đứng giữa hai toán hạng). 5.4.4. Cây tìm kiếm nhị phân „ Khoá của một đối tượng là một nhóm các thuộc tính của đối tượng sao cho trong một tập các đối tượng cùng kiểu thì hai đối tượng khác nhau cần phải có các giá trị khác nhau trên (khóa) nhóm các thuộc tính đó. „ Ta giả thiết ‰ kiểu của khoá (keytype) là một kiểu có thứ tự ‰ thông tin gắn với mỗi đỉnh của cây nhị phân là khoá của đối tượng nào đó. Do đó mỗi đỉnh của cây nhị phân được biểu diễn bởi bản ghi kiểu kieupt có cấu trúc như sau. ‰ type tropt = ^kieupt; ‰ kieupt = record ‰ key : keytype ; {DL: kieudl} ‰ left : tropt ; ‰ right : tropt ; ‰ end ; 122 5.4.4. Cây tìm kiếm nhị phân „ Cây tìm kiếm nhị phân là cây nhị phân hoặc trống, hoặc thoả mãn các điều kiện sau. ‰ Khoá của các đỉnh thuộc cây con trái nhỏ hơn khoá của gốc ‰ Khoá của gốc nhỏ hơn khoá của các đỉnh thuộc cây con phải của gốc. ‰ Cây con trái và cây con phải của gốc cũng là cây tìm kiếm nhị phân. J K IG CA EB HD F J KI G CA EB HD F