Giáo trình Cấu trúc dữ liệu và giải thuật - Trần Tiến Thành

Nội dung text: Giáo trình Cấu trúc dữ liệu và giải thuật - Trần Tiến Thành

1. TRƯỜNG ĐẠI HỌC SƯ PHẠM QUY NHƠN KHOA TIN HỌC TRẦN THIÊN THÀNH Giáo trình CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Quy nhơn, 10/2002
2. LỜI NÓI ĐẦU Cấu trúc dữ liệu và giải thuật là một môn học bắt buộc trong chương trình đào tạo cử nhân Tin học và Công nghệ thông tin. Giáo trình này được hình thành dựa trên nội dung giảng dạy nhiều năm tại khoa Tin học trường Đại học sư phạm Quy nhơn của tác giả. Nội dung giáo trình gồm 6 chương: Chương 1 trình bày một số kiến thức cơ bản về cấu trúc dữ liệu và giải thuật. Chương 2 trình bày về mô hình dữ liệu danh sách. Trong chương cũng giới thiệu hai kiểu dữ liệu trừu tượng là Stack và Queue cùng với một số ứng dụng tiêu biểu. Chương 3 trình bày về mô hình cây, chủ yếu tập trung vào cây tìm kiếm nhị phân, cây cân bằng và một số ứng dụng. Chương 4 trình bày về mô hình đồ thị và một số thuật toán thường dùng trên đồ thị. Chương 5 trình bày về cách tổ chức dữ liệu cho bộ nhớ ngoài. Chương 6 trình bày các thuật toán sắp xếp trong và sắp xếp ngoài. Giáo trình được soạn trên cơ sở chương trình đào tạo của Khoa. Một số kiến thức về thuật toán và kỹ thuật lập trình sinh viên đã được học trong các môn học trước đó nên không được đề cập trong giáo trình này. Giáo trình dùng làm tài liệu học tập cho sinh viên năm thứ ba hoặc học kỳ 2 của năm thứ hai ngành Tin học và Công nghệ thông tin với thời lượng 75 tiết. Ngoài ra, giáo trình có thể dùng cho sinh viên thuộc các ngành Toán học, Kỹ thuật và những người muốn có kiến thức sâu hơn về các cấu trúc dữ liệu thường dùng trong lập trình. Trong mỗi chương của giáo trình, các kiến thức lý thuyết được trình bày cơ bản, rõ ràng, được minh hoạ chi tiết cùng với những ứng dụng cụ thể giúp cho người học dễ đọc, dễ hình dung những ứng dụng của các cấu trúc dữ liệu trong một số ứng dụng điển hình. Do đó giáo trình có thể dùng làm tài liệu tự học cho những người đã có những kiến thức cơ bản về thuật toán và lập trình trên một ngôn ngữ lập trình bậc cao. Nội dung trong giáo trình bám sát những nội dung cơ bản về các cấu trúc dữ liệu mà các chương trình đào tạo cử nhân Tin học và Công nghệ thông tin yêu cầu. Cuối mỗi chương đều cung cấp một hệ thống các bài tập từ cơ bản đến nâng cao nhằm giúp cho sinh viên rèn luyện tư duy, kỹ thuật lập trình và hiểu rõ hơn những nội dung lý thuyết. Trong giáo trình sử dụng ngôn ngữ lập trình Pascal để minh hoạ các cấu trúc dữ liệu và thuật toán để giúp sinh viên dễ hình dung hơn trong cài đặt thành chương trình. Các cấu trúc dữ liệu được tổ chức dưới hình thức bao gói thông tin, mỗi cấu trúc dữ liệu được xem như một kiểu dữ liệu độc lập. Các thuật toán trình bày dưới dạng ngôn ngữ tự nhiên và được hoàn chỉnh bằng những thủ tục viết 2
3. bằng Pascal nên rất thuận tiện cho sinh viên trong thực hành bằng Pascal hay bất kỳ một ngôn ngữ lập trình bậc cao nào mà mình ưa thích. Để hoàn thành giáo trình này tác giả đã nhận được nhiều ý kiến đóng góp và động viên của các đồng nghiệp, đặc biệt là ThS Hồ Anh Minh đã đọc bản thảo và đóng góp nhiều ý kiến quý báu. Do thời gian và khả năng còn hạn chế nên giáo trình không thể tránh khỏi những khiếm khuyết nhất định. Chúng tôi chân thành và mong đón nhận những ý kiến đóng góp của độc giả. Tác giả 3
4. MỤC LỤC Lời nói đầu 2 Mục lục 4 Chương 1 Tổng quan về Cấu trúc dữ liệu và giải thuật 8 1. Tổng quan về thuật toán 8 1.1. Khái niệm thuật toán 8 1.2. Các đặc trưng của thuật toán 8 1.3. Tiêu chuẩn đánh giá thuật toán 9 1.4. Độ phức tạp của thuật toán 9 1.5. Ký hiệu O-lớn 11 2. Kiểu dữ liệu và cấu trúc dữ liệu 11 2.1. Kiểu dữ liệu 11 2.2. Cấu trúc dữ liệu 12 2.3. Mô hình dữ liệu 12 2.4. Các tiêu chuẩn của cấu trúc dữ liệu 12 3. Mối liên hệ giữa cấu trúc dữ liệu và giải thuật 13 3.1. Mối liên hệ 13 3.2. Một số ví dụ minh họa 13 4. Bài tập 15 Chương 2 Danh sách 17 1. Khái niệm và các thao tác 17 1.1. Định nghĩa danh sách 17 1.2. Các thao tác trên danh sách 17 2. Biểu diễn danh sách bằng mảng 18 2.1. Tổ chức dữ liệu 18 2.2. Các thao tác trên danh sách 19 3. Danh sách liên kết đơn 24 3.1. Cấp phát động, biến con trỏ và các thao tác 24 3.2. Khái niệm danh sách liên kết 25 3.3. Tổ chức danh sách liên kết 25 3.4. Các phép toán trên danh sách liên kết 26 4
5. 3.5. So sánh cấu trúc dữ liệu danh sách liên kết đơn và mảng 29 3.6. Một số dạng danh sách liên kết khác 29 4. Ngăn xếp (Stack) 34 4.1. Khái niệm 35 4.2. Tổ chức ngăn xếp bằng mảng 36 4.3. Tổ chức ngăn xếp bằng danh sách liên kết 38 4.4. Ứng dụng của ngăn xếp 40 5. Hàng đợi (Queue) 44 5.1. Khái niệm 44 5.2. Tổ chức hàng đợi bằng mảng 45 5.3. Tổ chức hàng đợi bằng danh sách liên kết 49 6. Bài tập 51 Chương 3 Cây 57 1. Các khái niệm về cây 57 1.1. Khái niệm cây 57 1.2. Một số khái niệm khác 58 2. Cây nhị phân 59 2.1. Khái niệm 59 2.2. Biểu diễn cây nhị phân 60 2.3. Duyệt cây nhị phân 63 2.4. Cây tìm kiếm nhị phân 67 2.5. Các thao tác trên cây tìm kiếm nhị phân 68 3. Cây cân bằng 74 3.1. Khái niệm 75 3.2. Thêm vào cây cân bằng 76 3.3. Loại bỏ khỏi cây cân bằng 82 4. Các ứng dụng của cây nhị phân 88 4.1. Mã Huffman 88 4.2. Cấu trúc dữ liệu Heap 91 5. Cây tổng quát 97 5.1. Tổ chức dữ liệu 97 5.2. Các thao tác trên cây tổng quát 100 5
6. 5.3. Cây tìm kiếm tổng quát 103 6. Bài tập 105 Chương 4 Đồ thị 108 1. Các khái niệm 108 1.1. Khái niệm đồ thị (Graph) 108 2. Tổ chức dữ liệu biểu diễn đồ thị 109 2.1. Biểu diễn đồ thị bằng ma trận kề (adjacency matrice) 109 2.2. Biểu diễn đồ thị bằng danh sách kề (adjacency list) 110 2.3. Biểu diễn đồ thị bằng danh sách cạnh (cung) 111 3. Duyệt đồ thị 112 3.1. Duyệt theo chiều sâu 112 3.2. Duyệt đồ thị theo chiều rộng 114 3.3. Tìm đuờng đi trên đồ thị 115 4. Tìm đường đi ngắn nhất 117 4.1. Đường đi ngắn nhất trên đồ thị không có trọng số 117 4.2. Đường đi ngắn nhất trên đồ thị có trọng số 118 5. Cây khung của đồ thị 126 5.1. Khái niệm cây khung (Spanning tree) 126 5.2. Thuật toán tìm cây khung của đồ thị 126 5.3. Cây khung ngắn nhất 127 5.4. Thuật toán tìm cây khung ngắn nhất của đồ thị 127 6. Bài tập 132 Chương 5 Các cấu trúc dữ liệu ở bộ nhớ ngoài 134 1. Mô hình tổ chức dữ liệu ở bộ nhớ ngoài 134 2. File băm 135 2.1. Cấu trúc Bảng băm (Hash Table) 135 2.2. File Băm 142 3. File chỉ số (Indexed File) 143 3.1. Tổ chức File chỉ số 144 3.2. Các thao tác trên file chỉ số 144 4. B-Cây 145 4.1. Khái niệm B-Cây 146 6
7. 4.2. Các thao tác trên B-Cây 147 5. Bài tập 149 Chương 6 Sắp xếp 151 1. Các thuật toán sắp xếp trong 151 1.1. Sắp xếp bằng cách chọn trực tiếp 151 1.2. Sắp xếp bằng cách đổi chỗ trực tiếp 152 1.3. Sắp xếp bằng cách chèn trực tiếp 153 1.4. Sắp xếp với độ dài bước giảm dần 155 1.5. Sắp xếp trộn 156 1.6. Sắp xếp kiểu vun đống 156 1.7. Sắp xếp bằng phân hoạch 159 2. Sắp xếp ngoài 160 2.1. Trộn hai tệp được sắp 160 2.2. Thuật toán sắp xếp trộn tự nhiên 161 3. Bài tập 164 Tài liệu tham khảo 165 7
8. Chương 1 TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1. TỔNG QUAN VỀ THUẬT TOÁN 1.1. Khái niệm thuật toán Khái niệm thuật toán (Algorithm) xuất phát từ tên một nhà toán học Arập Abu Ja'far Mohamed ibn Musa al’Khwarizmi, thường gọi là al’Khwarizmi. Ông là tác giả một cuốn sách về số học, trong đó ông đã dùng phương pháp mô tả rất rõ ràng, mạch lạc cách giải những bài toán. Sau này, phương pháp mô tả cách giải của ông đã được xem là một chuẩn mực và được nhiều nhà toán học khác tuân theo. Thuật ngữ algorithm ra đời từ đó dựa theo cách phiên âm tên của ông. Cùng với thời gian khái niệm thuật toán được hoàn chỉnh dần và khái niệm hình thức chính xác của thuật toán được định nghĩa thông qua mô hình máy Turing. Giáo trình này không đi sâu vào những khía cạnh lý thuyết của thuật toán nên chỉ trình bày khái niệm không hình thức của thuật toán: Thuật toán là một hệ thống chặt chẽ và rõ ràng các quy tắc nhằm xác định một dãy các thao tác trên những đối tượng sao cho sau một số hữu hạn bước thực hiện các thao tác thì đạt được mục tiêu định trước. 1.2. Các đặc trưng của thuật toán Một thuật toán thông thường có 6 đặc trưng cơ bản sau: 1.2.1. Tính kết thúc (tính dừng) Thuật toán bao giờ cũng phải dừng sau một số hữu hạn bước thực hiện. 1.2.2. Tính xác định Thuật toán yêu cầu ở mỗi bước các thao tác phải hết sức rõ ràng, không gây nên sự nhập nhằng, lẫn lộn, tùy tiện. Khi thực hiện thuật toán, trong cùng một điều kiện thì cho cùng một kết quả. 1.2.3. Tính phổ dụng Thuật toán phải có thể giải được một lớp các bài toán. Mỗi thuật toán có thể làm việc với những dữ liệu khác nhau trong một miền xác định. 8
9. 1.2.4. Đại lượng vào Mỗi thuật toán thường có những đại lượng vào gọi là dữ liệu vào để cung cấp dữ liệu cho thuật toán. Tuy nhiên, cũng có những thuật toán không có dữ liệu vào. 1.2.5. Đại lượng ra Sau khi kết thúc thuật toán, tùy vào chức năng của thuật toán mà thu được một số đại lượng xác định gọi là đại lượng ra hay dữ liệu ra. 1.2.6. Tính hiệu quả Với dữ liệu vào, sau một số hữu hạn bước thực hiện thuật toán sẽ dừng và cho đúng kết quả mong muốn với thời gian chấp nhận được. 1.3. Tiêu chuẩn đánh giá thuật toán Một bài toán có thể có nhiều thuật toán giải, mỗi thuật toán có những ưu nhược điểm riêng. Để quyết định chọn thuật toán nào thông thường dựa vào 2 tiêu chuẩn cơ bản sau: 1. Thuật toán đơn giản, dễ hiểu, dễ cài đặt. 2. Thuật toán sử dụng tiết kiệm các tài nguyên của hệ thống máy tính như bộ nhớ, thời gian chiếm dụng CPU và đặc biệt là thời gian chạy. Trong trường hợp chương trình ít sử dụng và giá viết chương trình vượt xa giá chạy chương trình thì tiêu chuẩn 1 được ưu tiên. Với những chương trình thường dùng như các thư viện, các chương trình hệ thống thì tiêu chuẩn 2 được ưu tiên chọn trước. Trong tiêu chuẩn 2, tính hiệu quả của thuật toán bao gồm 2 yếu tố: - Dung lượng không gian nhớ cần thiết để lưu các loại dữ liệu và các kết quả trung gian để giải bài toán (tổ chức dữ liệu cho bài toán). - Thời gian cần thiết để thực hiện thuật toán (thời gian chạy). Hai yếu tố trên thường mâu thuẫn nhau và ảnh hưởng qua lại lẫn nhau. Thường khi chọn thuật toán ta quan tâm đến thời gian thực hiện. Mặc dù hiện nay tốc độ máy tính ngày được cải thiện đáng kể, có thể thực hiện hàng trăm triệu phép tính trên giây nhưng vẫn chưa đáp ứng được cho một số thuật toán có thời gian chạy rất lớn. 1.4. Độ phức tạp của thuật toán Việc đánh giá thời gian thực hiện của thuật toán phụ thuộc vào nhiều yếu tố: - Dữ liệu vào. - Tốc độ của máy tính. 9
10. - Chương trình dịch và hệ điều hành dùng cho chương trình. Do đó việc đo, đếm chính xác thời gian thực hiện thuật toán là bao nhiêu đơn vị thời gian gần như không thể thực hiện được. Để có thể so sánh thời gian chạy của các thuật toán, trên phương diện lý thuyết thời gian thực hiện thuật toán được đánh giá là một hàm phụ thuộc vào kích thước của dữ liệu vào gọi là độ phức tạp thuật toán. Để đánh giá độ phức tạp của thuật toán thông thường người ta tính số phép toán cơ bản thuật toán thực hiện. Các phép toán cơ bản thường dùng để đánh giá như các phép toán: +, -, *, /, các phép so sánh, phép gán, thao tác đọc, ghi file, Tùy thuộc vào thuật toán, độ phức tạp là một hàm phụ thuộc vào kích thước của dữ liệu vào, ký hiệu T(n), với n là đại lượng đặc trưng cho kích thước của dữ liệu vào. Trong trường hợp thuật toán thực hiện nhiều phép toán cơ bản ta có thể đánh giá độ phức tạp trên từng loại phép toán hoặc tổng hợp của các phép toán. Chẳng hạn thuật toán sắp xếp thường được đánh giá trên 2 phép toán thường dùng là so sánh và phép gán. Trong nhiều trường hợp, việc tính toán chính xác độ phức tạp thuật toán T(n) là không thể thực hiện được vì còn tùy thuộc vào sự phân bố của dữ liệu vào. Chẳng hạn thuật toán tìm một phần tử trong một danh sách cho trước không chỉ phụ thuộc vào số phần tử của danh sách mà còn phụ thuộc vào vị trí của phần tử cần tìm có trong danh sách hay không, nếu có thì phụ thuộc vào vị trí của phần tử do đó số phép so sánh phụ thuộc vào từng danh sách và phần tử cần tìm. Trong những trường hợp như thế này thông thường độ phức tạp được đánh giá trong trường hợp xấu nhất của dữ liệu vào. Trong một số tình huống cụ thể có thể tính trung bình hoặc tính theo xác suất. Ví dụ 1: Thuật toán tìm một phần tử x trong danh sách L có n phần tử bằng cách tìm tuần tự. TimThay:=False; For i:=1 To n Do If L[i] = x then begin TimThay:=True; Exit; end Độ phức tạp được đánh giá qua số lần thực hiện phép so sánh L[i]=x trong trường hợp xấu nhất là không có phần tử cần tìm. Khi đó T(n) = n. Ví dụ 2: Thuật toán sắp xếp dãy số a[1 n] tăng dần For i:=1 to n-1 Do For j:=i+1 to n Do If a[i]>a[j] then Begin tg:=a[i]; a[i]:=a[j]; 10
11. a[j]:=tg; End; Độ phức tạp của thuật toán được đánh giá trên 2 phép toán cơ bản là phép so sánh trong biểu thức điều kiện của lệnh If và phép gán, ký hiệu tương ứng là C(n) và M(n). Độ phức tạp được đánh giá trong trường hợp "xấu" nhất của dữ liệu vào là dãy số ở tình trạng thứ tự giảm. Khi đó ta tính được: Số phép so sánh C(n) = (n-1)n/2 Số phép gán M(n) = 3(n-1)n/2. 1.5. Ký hiệu O-lớn Việc đánh giá độ phức tạp thuật toán qua hàm T(n) như trên quá chi tiết vào các phép toán thực hiện của thuật toán nên khó khăn trong việc so sánh và phân lớp các thuật toán. Để thể hiện bản chất hơn độ phức tạp của thuật toán phụ thuộc vào kích thước dữ liệu vào ta dùng khái niệm O-lớn (big oh) bằng cách bỏ qua các hằng trong độ phức tạp thuật toán. Cho T(n), f(n) là hai hàm. Ta nói T(n) là O-lớn của f(n), ký hiệu T(n) = O(f(n)), nếu và chỉ nếu tồn tại các hằng số dương c và số n0 sao cho với mọi n n0 ta có T(n) c f(n). Ví dụ: T(n) = 3n2 + 2n - 10 thì T(n) = O(n2). Một số hàm thường dùng trong đánh giá độ phức tạp thuật toán qua ký hiệu O-lớn Ký hiệu O-lớn Tên gọi thường dùng O(1) Hằng O(logn) logarit O(n) tuyến tính O(nlogn) nlogn O(n2) bình phương O(2n) mũ Quy tắc tổng : Nếu T1(n) = O(f1(n)) và T2(n) = O(f2(n)) thì T1(n) + T2(n)= O(max(f1(n),f2(n)). 2. KIỂU DỮ LIỆU VÀ CẤU TRÚC DỮ LIỆU 2.1. Kiểu dữ liệu Mọi dữ liệu lưu trữ trên máy tính đều được biểu diễn dưới dạng các số nhị phân. Việc sử dụng trực tiếp các số nhị phân trên máy tính là một công việc khó 11
12. khăn cho người lập trình. Chính vì lý do này mà các ngôn ngữ lập trình cấp cao đã xây dựng nên các kiểu dữ liệu. Một kiểu dữ liệu là sự trừu tượng hóa các thuộc tính bản chất của các đối tượng trong thực tế và phù hợp với cách tổ chức thông tin trên máy tính, chẳng hạn như các kiểu số nguyên, số thực, logic, Một kiểu dữ liệu T là một bộ T = , trong đó V là tập các giá trị hợp lệ của kiểu T và O là tập các phép toán trên kiểu T. Ví dụ: Kiểu dữ liệu Byte = , với VByte = {0, 1, , 255}, OByte = {+, -, *, div, mod, >, >=, } 2.2. Cấu trúc dữ liệu Các kiểu dữ liệu cơ sở không đủ để mô tả các đối tượng của thế giới thực nên trong các ngôn ngữ lập trình bậc cao cho phép kết hợp các kiểu dữ liệu cơ sở để tạo nên một kiểu dữ liệu mới phức tạp hơn gọi là cấu trúc dữ liệu. Các kiểu dữ liệu cấu trúc thường dùng trên các ngôn ngữ lập trình bậc cao như: Array, String, Record, File, là các cấu trúc dữ liệu thường dùng. 2.3. Mô hình dữ liệu Các bài toán thực tế cần phải giải trên máy tính ngày càng phức tạp và đa dạng, do đó trước khi tổ chức các cấu trúc dữ liệu mô tả bài toán, người lập trình thường phải dùng các mô hình toán học để biểu diễn các đối tượng của bài toán và mối liên hệ giữa các đối tượng. Việc sử dụng các mô hình toán học cho phép người lập trình mô tả chính xác bản chất của các đối tượng trong bài toán và việc sử dụng toán học như một công cụ giúp cho việc giải các bài toán dễ dàng, chính xác hơn trước khi giải bài toán trên máy tính bằng chương trình. Mô hình toán học có thể biểu diễn được trên máy tính gọi là mô hình dữ liệu. Mô hình dữ liệu muốn cài đặt được trên máy tính phải có một cách tổ chức dữ liệu phù hợp. Các mô hình dữ liệu thường được sử dụng trong các bài toán tin học là: danh sách, cây, đồ thị, bảng băm, quan hệ, 2.4. Các tiêu chuẩn của cấu trúc dữ liệu Khi tổ chức dữ liệu cho một bài toán thường dựa vào các tiêu chuẩn sau để lựa chọn cách tổ chức dữ liệu tối ưu. Phản ánh đúng thực tế: đây là tiêu chuẩn quan trọng nhất, quyết định tính đúng đắn của toàn bộ quá trình giải bài toán. Trong khi tổ chức dữ liệu cũng dự tính các trạng thái biến đổi của dữ liệu trong tương lai để đảm bảo cho chương trình hoạt động được lâu dài. Các thao tác phù hợp: mỗi cấu trúc dữ liệu có thể biểu diễn được một tập các đối tượng và có một tập các phép toán phù hợp. Việc chọn cách tổ chức dữ liệu không chỉ biểu diễn được các đối tượng của bài toán mà còn phải phù hợp với các thao tác trên đối tượng đó, có như vậy ta mới xây dựng được thuật toán giải bài toán đơn giản hơn. 12
13. Tiết kiệm tài nguyên hệ thống: khi tổ chức dữ liệu chỉ nên sử dụng tài nguyên hệ thống vừa đủ đáp ứng được yêu cầu công việc, tránh lãng phí. Có hai loại tài nguyên quan trọng của hệ thống là bộ nhớ và thời gian chiếm dụng CPU để thực hiện các thao tác trên dữ liệu. Thông thường hai loại tài nguyên này thường mâu thuẫn nhau trong khi giải các bài toán. Tuy nhiên nếu tổ chức khéo léo chúng ta cũng có thể tiết kiệm được cả hai loại tài nguyên. 3. MỐI LIÊN HỆ GIỮA CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Trong khi giải một bài toán, thông thường ta chỉ chú trọng đến giải thuật (hay cách giải của bài toán) mà ít khi quan tâm đến việc tổ chức dữ liệu. Tuy nhiên giữa việc tổ chức dữ liệu và thuật toán có mối liên hệ chặt chẽ nhau. 3.1. Mối liên hệ Theo cách tiếp cận của lập trình cấu trúc, Niklaus Wirth đưa ra công thức thể hiện được mối liên hệ giữa cấu trúc dữ liệu và giải thuật: CẤU TRÚC DỮ LIỆU + GIẢI THUẬT = CHƯƠNG TRÌNH (Data structures + Algorithms = Programs) Một thuật toán giải bài toán bao giờ cũng được thao tác trên một cấu trúc dữ liệu cụ thể và các thao tác phải được cấu trúc dữ liệu đó hỗ trợ. Khi tổ chức dữ liệu cho bài toán thay đổi thì thuật toán giải cũng phải thay đổi theo cho phù hợp với cách tổ chức dữ liệu mới. Ngược lại, trong quá trình xây dựng, hoàn chỉnh thuật toán cũng gợi mở cho người lập trình cách tổ chức dữ liệu phù hợp với thuật toán và tiết kiệm tài nguyên hệ thống. Chẳng hạn dùng thêm các ô nhớ phụ để lưu các kết quả trung gian để giảm thời gian tính toán. Quá trình giải một bài toán trên máy tính là một quá trình hoàn thiện dần cách tổ chức dữ liệu và thuật toán để tiết kiệm tài nguyên của hệ thống. 3.2. Một số ví dụ minh họa Ví dụ 1. Xét bài toán đổi giá trị hai biến số x,y. Với bài toán này ta có 2 phương án giải như sau: Phương án 1. Dùng ô nhớ trung gian tg := x; x:= y; y := tg; Phương án 2. Không dùng biến trung gian. x := x + y; y := x - y; x := x - y; Qua ví dụ đơn giản trên, ta nhận thấy việc tổ chức dữ liệu khác nhau (dùng hay không dùng biến trung gian) ảnh hưởng rất lớn đến thuật toán và gần như thay 13
14. đổi toàn bộ thuật toán. Hơn nữa nó còn ảnh hưởng đến tính hiệu quả và phạm vi ứng dụng của thuật toán. k Ví dụ 2. Xét bài toán tính số tổ hợp chập k của n phần tử Cn . n! Phương án 1. Dùng định nghĩa C k . Giả sử gt(n) là hàm trả về n k!(n k)! k n!. Ta có hàm tính hệ số Cn như sau: Function HeSo(n,k:word):Longint; Begin HeSo := gt(n) div gt(k) div gt(n-k); End; k Nhận xét: Với thuật toán này các chương trình chỉ tính được Cn với các số n, k nhỏ vì phải lưu các kết quả trung gian rất lớn là n!, k!, n-k!. k k 1 k 0 i Phương án 2. Dùng công thức Cn = Cn 1 + Cn 1 , với Cn =1, Ci =1. Hàm tính hệ số được viết dưới dạng đệ quy như sau. Function HeSo(n, k : word) : Longint; Begin if (k=0) or (k=n) then HeSo:=1 else HeSo := HeSo(n-1,k-1) + HeSo(n-1,k); End; Nhận xét: Với thuật toán này khắc phục việc phải lưu các giá trị giai thừa trung gian nhưng hạn chế của thuật toán là phải tính lại nhiều lần 3 các giá trị đã tính ở bước trước, chẳng hạn để tính C5 chương trình 2 1 phải lặp lại 2 lần tính C3 , 3 lần tính C2 , Phương án 3. Dùng một mảng hai chiều C[0 n,0 k] mỗi phần tử có kiểu k LongInt để lưu các kết quả trung gian trong khi tính Cn , với j k k 1 k C[i,j]=Ci (0 j i,j k,i n). Từ công thức Cn =Cn 1 +Cn 1 , ta có C[i,j]=C[i-1,j-1]+C[i- 3 1,j-1]. Bảng dưới minh hoạ mảng C dùng để tính C5 . 0 1 2 3 0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 5 1 5 10 10 Function HeSo(n, k : word) : Longint; Var i,j : word; Begin 14
15. For i:=1 to n do C[i,0]:=1; For j:=1 to k do Begin C[j,j]:=1; For i:=j+1 to n do C[i,j]:=C[i-1,j-1]+C[i-1,j]; End; HeSo:=C[n,k]; End; Nhận xét: phương án này còn nhiều ô nhớ của mảng không dùng, cụ thể là các ô nằm ở phần trên đường chéo chính. Vì mục đích của bài k toán là tính giá trị Cn mà không cần các giá trị trung gian nên ta có thể tổ chức bộ nhớ tiết kiệm hơn bằng cách dùng một mảng 1 chiều. Phương án 4. Dùng mảng một chiều H[0 k] để lưu các giá trị của từng dòng trong mảng C của phương án trên. Mảng H được tính qua n bước, ở bước thứ j i, H là dòng thứ i của mảng C, cụ thể tại bước thứ i, H[j]= Ci , với j i. Function HeSo(n,k:Word):LongInt; var H:array[0 1000] of LongInt; i,j : Word; Begin for i:=1 to k do H[i]:=0; H[0]:=1; for j:=1 to n do for i:=k downto 1 do H[i]:=H[i]+H[i-1]; Heso:=H[k]; End; Nhận xét: Với phương án này vừa tiết kiệm được bộ nhớ vừa tăng khả năng tính toán với n, k lớn hơn các phương án khác. 4. BÀI TẬP Bài 1. Cho n điểm trong không gian 2 chiều. Cần tìm hình chữ nhật có các cạnh song song với các trục toạ độ chứa n đỉnh trên có diện tích nhỏ nhất. Hãy tổ chức dữ liệu, trình bày thuật toán và lập trình giải bài toán trên. Bài 2. Cho một dãy số a1, a2, ,an. Hãy trình bày 2 thuật toán chuyển k phần tử đầu tiên ra cuối. Nghĩa là sau khi chuyển ta được dãy ak+1, , an, a1, , ak. Yêu cầu về tổ chức dữ liệu không được dùng mảng trung gian mà chỉ dùng một ô nhớ trung gian. Đánh giá độ phức tạp của thuật toán. Có thể cải tiến để có thuật toán tốt hơn về độ phức tạp không?. Bài 3. Một danh sách học sinh gồm họ tên và điểm trung bình. Hãy tổ chức dữ liệu và trình bày thuật toán xếp thứ hạng cho các học sinh. Đánh giá độ phức tạp của thuật toán. Cài đặt bằng chương trình cụ thể. 15
16. Bài 4. Cho một dãy số nguyên, hãy trình bày thuật toán liệt kê các phần tử khác nhau của dãy số trên. Độ phức tạp của thuật toán? Cài đặt bằng chương trình? Có thể cải tiến thuật toán để đơn giản hơn không?. Bài 5. Cần chia hết m phần thưởng cho n học sinh sắp theo thứ tự từ giỏi trở xuống sao cho mỗi học sinh không nhận ít phần thưởng hơn bạn xếp sau mình. Hãy đề xuất các cách tổ chức dữ liệu và trình bày thuật toán tính số cách chia thưởng, với mỗi cách phân tích những ưu, nhược điểm. Viết các thủ tục tương ứng cho từng cách tổ chức dữ liệu. 16
17. Chương 2 DANH SÁCH 1. KHÁI NIỆM VÀ CÁC THAO TÁC 1.1. Định nghĩa danh sách Danh sách là một dãy hữu hạn các phần tử cùng loại được xếp theo một thứ tự tuyến tính. Danh sách L gồm các phần tử a1, a2, , an được ký hiệu: L = (a1, a2, , an). Trong đó n gọi là chiều dài của danh sách, ai gọi là phần tử thứ i của danh sách. a1 gọi là phần tử đầu tiên của danh sách, an gọi là phần tử cuối cùng của danh sách. Nếu n = 0 thì danh sách được gọi là rỗng. Một tính chất quan trọng của danh sách là các phần tử được sắp xếp tuyến tính theo vị trí của chúng trong danh sách. Với n>1, i =1, 2, , n-1, phần tử ai là phần tử ngay trước phần tử ai+1 và ai+1 là phần tử ngay sau phần tử ai. Trong một danh sách các phần tử có thể giống nhau. Danh sách con Cho L = (a1, a2, , an) là một danh sách và i,j là các vị trí trong danh sách (1 i j n). Danh sách L' = (b1, b2, , bj-i+1), trong đó b1 = ai, b2 = ai+1, , bj- i+1=aj được gọi là danh sách con của danh sách L. Dãy con Danh sách L' được tạo thành từ danh sách L bằng cách bỏ đi một số phần tử của danh sách L nhưng vẫn giữ nguyên thứ tự được gọi là dãy con của danh sách L. Ví dụ: L = (1, 5, 2, 5, 7, 2), L1 = (5, 2, 5) là danh sách con của L, L2 = (2, 5, 7,2) là dãy con của danh sách L. Trong thực tế có rất nhiều dữ liệu được tổ chức dưới dạng danh sách như danh sách nhân viên trong một cơ quan, danh sách các môn học, danh bạ điện thoại, 1.2. Các thao tác trên danh sách Tùy thuộc từng loại danh sách sẽ có các thao tác đặc trưng riêng. Trên danh sách thường thực hiện các thao tác cơ bản sau. - Khởi tạo danh sách: tạo một danh sách rỗng. - Thêm một phần tử vào danh sách. 17
18. - Loại bỏ một phần tử khỏi danh sách. - Sắp thứ tự danh sách theo một khóa nào đó. - Tìm kiếm một phần tử trong danh sách. - Ghép nhiều danh sách thành một danh sách. - Tách một danh sách thành nhiều danh sách. - Sao chép một danh sách. - 2. BIỂU DIỄN DANH SÁCH BẰNG MẢNG Mảng là một cấu trúc dữ liệu cơ bản, thường dùng và được các ngôn ngữ lập trình cấp cao hỗ trợ. Mảng là một dãy cố định các ô nhớ chứa các phần tử cùng kiểu. Mỗi ô nhớ của mảng được xác định bởi chỉ số. Mô hình danh sách có những tính chất gần giống với cấu trúc dữ liệu kiểu mảng nên ta có thể dùng mảng để biểu diễn mô hình danh sách, trong đó các phần tử của danh sách được lưu vào các ô nhớ liên tục của mảng. Điểm khác biệt giữa cấu trúc mảng và mô hình danh sách là số phần tử của mảng cố định trong khi số phần tử của danh sách thay đổi theo các thao tác thêm và xóa. 2.1. Tổ chức dữ liệu Giả sử có danh sách L=(a1,a2, ,an) trong đó mỗi phần tử có kiểu ElementType. Khi đó tổ chức dữ liệu kiểu mảng để lưu danh sách L gồm 2 thành phần: + Thành phần element là một mảng lưu các phần tử của danh sách. + Thành phần count là vị trí của ô nhớ lưu phần tử cuối cùng của danh sách và cũng là số phần tử hiện tại của danh sách. Để đơn giản ta qui định các phần tử của mảng có chỉ số từ 1 đến maxlength, các phần tử của danh sách lưu vào mảng từ vị trí đầu tiên đến vị trí count. Khi đó các vị trí của mảng từ vị trí count+1 đến maxlength chưa sử dụng, những phần tử này sẽ được sử dụng khi thực hiện các thao tác thêm vào danh sách. 1 2 count maxlength a1 a2 an Các phần tử của danh sách các ô nhớ trống Hình 2.1 Tổ chức danh sách bằng mảng Khai báo một danh sách trong Pascal có dạng: Const 18
19. MaxLength = ; {Số phần tử tối đa của danh sách} Type ElementType = ;{Định nghĩa kiểu phần tử của danh sách} ListArr = Record element : Array[1 MaxLength] Of ElementType; count : 0 MaxLength; End; Var L : ListArr; Ví dụ: Khai báo danh bạ điện thoại gồm họ tên, địa chỉ, số điện thoại. Const MaxLength = 100 ; Type DIENTHOAI = Record Họ_tên : String[30]; Địa_Chỉ: String[30]; Số_ĐT : String[10]; End; DANHBA = Record element: Array[1 MaxLength] Of DIENTHOAI; Count : 0 MaxLength; End; Var db : DANHBA; 2.2. Các thao tác trên danh sách 2.2.1. Khởi tạo danh sách Số phần tử của danh sách được lưu vào thành phần count nên để khởi tạo danh sách rỗng ta chỉ cần thực hiện phép gán count := 0. Procedure Init(var l : ListArr); Begin l.count := 0; End; 2.2.2. Kiểm tra danh sách rỗng Function Empty(l : ListArr):Boolean; Begin Empty := l.count = 0; End; 19
20. 2.2.3. Kiểm tra danh sách đầy Khi biểu diễn danh sách bằng mảng sẽ phải khống chế số lượng tối đa các phần tử của danh sách. Do đó có thể đến một lúc nào đó không đủ ô nhớ để thêm các phần tử vào danh sách. Trong trường hợp này gọi là danh sách đầy. Như vậy danh sách đầy khi số phần tử của danh sách bằng kích thước của mảng. Function Full(l : ListArr):Boolean; Begin Full := l.count = maxlength; End; 2.2.4. Thêm một phần tử vào danh sách Cho danh sách L, cần thêm vào trước phần tử thứ k trong danh sách một phần tử x. 1 k count maxlength a1 ak an a1 x 1 k k+1 count Hình 2.2 Thêm một phần tử vào danh sách Thuật toán: + Di chuyển các phần tử từ vị trí thứ k đến cuối danh sách ra sau một vị trí. + Đưa phần tử cần thêm x vào vị trí k. + Tăng thành phần count lên 1. Procedure Insert(var L:ListArr; x:ElementType; k:1 maxlength); var i:1 maxlength; Begin If (k 0) and not Full(L) then Begin For i:= L.count DownTo k Do L.element[i+1] := L.element[i]; L.element[k]:=x; L.count := L.count + 1; End; End; 2.2.5. Loại bỏ một phần tử khỏi danh sách Giả sử cần xóa phần tử thứ k trong danh sách L. Thuật toán: 20
21. + Dồn các phần tử từ vị trí k+1 đến cuối danh sách về trước một vị trí. + Giảm số phần tử của danh sách đi 1. 1 k k+1 count maxlength a1 ak ak+1 a1 1 k k+1 count maxlength Hình 2.3 Xoá phần tử thứ k trong danh sách Procedure Delete(var L : ListArr; k : 1 maxlength); var i : 1 maxlength; Begin If (k 0) and not Empty(L) then Begin For i:= k To L.count-1 Do L.element[i] := L.element[i+1]; L.count := L.count - 1; End; End; Với danh sách có n phần tử, dễ thấy độ phức tạp thuật toán thêm một phần tử và thuật toán xóa một phần tử có độ phức tạp là O(n). 2.2.6. Ghép 2 danh sách Cho hai danh sách L1 và L2. Ghép 2 danh sách này thành danh sách L. Procedure Concat(L1, L2 : ListArr; Var L : ListArray); var i : 1 maxlength; Begin For i:=1 To L1.count Do L.element[i] := L1.element[i]; For i:=1 To L2.count Do L.element[i+L1.count] := L2.element[i]; L.count := L1.count + L2.count; End; 2.2.7. Sắp xếp danh sách Cho danh sách L, sắp xếp danh sách theo thứ tự tăng của trường khóa Key (Key là một trường trong kiểu dữ liệu phần tử của danh sách). Có nhiều thuật toán sắp xếp danh sách tổ chức bằng mảng. Trong phần này trình bày thuật toán sắp xếp bằng chọn trực tiếp. 21
22. Thuật toán: Duyệt lần lượt từng phần tử của danh sách, với phần tử thứ i thực hiện: + Tìm phần tử ở vị trí k có khóa nhỏ nhất trong danh sách con L[i count] + Đổi giá trị phần tử thứ k với phần tử thứ i. Procedure Sort(Var L : ListArr); var i, j, k : 1 maxlength; tg : ElementType; Begin For i:=1 To L.count-1 Do Begin k := i; For j := i+1 To L.count Do If L.element[k].Key > L.element[j].Key then k := j; tg := L.element[i]; L.element[i] := L.element[k]; L.element[k] := tg; End; End; 2.2.8. Tìm kiếm trong danh sách Cho danh sách L, tìm trong danh sách phần tử có khóa của trường Key là x. Thuật toán tìm kiếm tuần tự: Duyệt lần lượt từng phần tử của danh sách, với mỗi phần tử thực hiện: Nếu phần tử thứ i có khóa trùng với x thì phần tử thứ i là phần tử cần tìm, dừng thuật toán và kết quả tìm thấy. Nếu đã duyệt hết danh sách thì kết luận không tìm thấy. Thủ tục Locate tìm trong danh sách L một phần tử có khóa là x. Kết quả nếu tìm thấy được trả về qua tham biến found kiểu boolean và vị trí của phần tử tìm được đầu tiên qua tham biến id. Procedure Locate(L : ListArr; x: KeyType; var found : Boolean; var id : 0 maxlenght); Begin id:=1; Found:=False; While (id<=L.count) and not found Do begin If L.element[id].Key = x then Found:=True else Id:=id+1; end; End; 22
23. Độ phức tạp thuật toán tìm kiếm tuần tự là O(n) với n là số phần tử của danh sách. Bài toán tìm kiếm là một bài toán thường dùng trong tin học. Để giảm độ phức tạp thuật toán tìm kiếm ta có thể dùng thuật toán tìm nhị phân. Yêu cầu để thực hiện được thao tác tìm nhị phân là danh sách phải được sắp xếp trên trường khóa cần tìm. Giả sử danh sách L đã sắp xếp theo thứ tự tăng của trường Key. Thuật toán tìm kiếm nhị phân: Lặp lại trong khi danh sách còn ít nhất một phần tử, mỗi lần lặp thực hiện: - So sánh khóa cần tìm với phần tử ở vị trí giữa của danh sách: + Nếu khóa phần tử giữa lớn hơn khóa cần tìm thì tìm trong nửa đầu của danh sách. + Nếu khóa phần tử giữa nhỏ hơn khóa cần tìm thì tìm trong nửa sau của danh sách. + Nếu khóa phần tử giữa bằng khóa cần tìm thì thuật toán kết thúc và kết quả tìm thấy. Nếu danh sách không có phần tử nào thì kết quả không tìm thấy. Procedrue Seek(L:ListArr;x:KeyType;var found:Boolean; var id : Integer); var left, right : 1 maxlength; Begin left:=1; right:=L.count; found:=false; While (left x then right:=id-1; if L.element[id].Key < x then left :=id+1; if L.element[id].Key = x then found:=true; End; End; Vì sau mỗi lần so sánh, số phần tử trong danh sách cần tìm giảm đi một nửa nên độ phức tạp thuật toán tìm nhị phân được đánh giá trong trường hợp xấu nhất là O(log2n). 2.2.9. Nhận xét về cách biểu diễn danh sách bằng mảng Với cách tổ chức dữ liệu cho mô hình danh sách bằng mảng như trên ta có một số nhận xét về ưu, nhược điểm của cách tổ chức dữ liệu này như sau: - Tổ chức danh sách bằng mảng thuận lợi khi truy xuất trực tiếp các phần tử của danh sách theo vị trí. Điều này thuận lợi cho một số thuật toán như tìm nhị phân. - Khi dùng mảng phải cố định kích thước, trong khi đó các thao tác trên danh sách luôn làm cho số phần tử của danh sách thay đổi. Điều này dẫn đến hai xu hướng: nếu khai báo mảng với kích thước lớn thì gây lãng 23
24. phí vì nhiều ô nhớ không sử dụng hoặc khai báo kích thước nhỏ để ít lãng phí thì sẽ mau chóng đầy danh sách khi thêm. - Các thao tác thêm, xóa cài đặt trên danh sách tổ chức bằng mảng có độ phức tạp là O(n) nên không phù hợp với các danh sách thường xuyên sử dụng các thao tác này. 3. DANH SÁCH LIÊN KẾT ĐƠN Một trong những đặc trưng của danh sách là số phần tử không cố định mà thay đổi tùy thuộc vào thao tác trên nó. Điều này buộc cách tổ chức dữ liệu biểu diễn cho mô hình danh sách cũng phải có đặc trưng này, nghĩa là bộ nhớ phải được cấp phát động (dùng mảng không đáp ứng được yêu cầu này). Mặc khác trong danh sách các phần tử được sắp xếp tuyến tính do đó việc tổ chức dữ liệu cấp phát động phải được tổ chức sao cho thể hiện được thứ tự tuyến tính của các phần tử trong danh sách, một trong những cách thường dùng là danh sách liên kết đơn. Trong danh sách liên kết đơn mỗi phần tử phải quản lý địa chỉ ô nhớ lưu phần tử ngay sau nó. Để thuận lợi cho các thao tác với bộ nhớ cấp phát động, trong phần sau nhắc lại một số thao tác với bộ nhớ cấp phát động thông qua biến con trỏ của Pascal. 3.1. Cấp phát động, biến con trỏ và các thao tác Ô nhớ cấp phát động là những ô nhớ được cấp phát và thu hồi bằng lệnh trong chương trình. Để quản lý các ô nhớ cập phát động cần sử dụng biến kiểu con trỏ. Biến con trỏ chứa địa chỉ của ô nhớ động được cấp phát. Mỗi biến con trỏ chỉ có thể quản lý một ô nhớ cấp phát động có kiểu xác định. Khai báo kiểu và biến con trỏ: Type Kiểu_Con_trỏ = ^Kiểu_dữ_liệu; Var Biến_con_trỏ : ^Kiểu_dữ_liệu; Cấp phát ô nhớ cho biến con trỏ: New(biến_con_trỏ); Thủ tục này cấp phát một ô nhớ đủ dùng để chứa dữ liệu của kiểu dữ liệu mà biến con trỏ trỏ đến và biến con trỏ trỏ đến ô nhớ này. Sử dụng ô nhớ do biến con trỏ quản lý: Mặc dù biến con trỏ chỉ quản lý địa chỉ của ô nhớ cấp phát động, tuy nhiên trong trường hợp cần thao tác với nội dung của ô nhớ ta có thể dùng cú pháp: Biến_con_trỏ^ Giả sử có biến con trỏ p trỏ đến một ô nhớ kiểu số nguyên. (Var p:^Integer;) và đã cấp phát ô nhớ cho con trỏ p (New(p)). Muốn thao tác với nội dung của ô nhớ này ta dùng cú pháp p^ và sử dụng như một biến nguyên thuần túy. Chẳng hạn để chứa số 5 vào ô nhớ này ta có thể gán p^:=5; 24
25. Phép gán con trỏ: Ta có thể thực hiện thao tác gán cho biến con trỏ p:=q; (p,q là 2 biến con trỏ cùng kiểu). Khi đó p và q sẽ cùng trỏ vào một ô nhớ do biến con trỏ q đang quản lý. Hằng con trỏ Nil dùng để gán cho con trỏ có kiểu bất kỳ thường dùng khi mà chưa xác định địa chỉ mà biến con trỏ quản lý. Thu hồi ô nhớ của một biến con trỏ: Khi cần thu hồi ô nhớ do biến con trỏ quản lý ta dùng thủ tục Dispose. Dispose(biến_con_trỏ); Khi đó vùng nhớ mà biến con trỏ p quản lý đã được thu hồi và có thể dùng cho việc khác. Sau khi thu hồi ô nhớ của một biến con trỏ thì nên gán cho nó giá trị nil để tránh những sai sót khi thao tác với biến con trỏ này. Ta cũng có thể thu hồi một số ô nhớ cấp phát bằng cách dùng cặp thủ tục Mark(p) và Release(p). Trong đó thủ tục Mark(p) (với p là một biến con trỏ) dùng để đánh dấu vị trí đầu của một vùng nhớ mà khi cần có thể thu hồi lại. Thủ tục Release(p) thu hồi vùng nhớ bắt đầu từ vị trí được đánh dấu bằng lệnh Mark(p). 3.2. Khái niệm danh sách liên kết Danh sách liên kết là một cách tổ chức dữ liệu cho mô hình danh sách trong đó các phần tử được liên hệ với nhau nhờ vào vùng liên kết. Danh sách liên kết sử dụng cơ chế cấp phát động nên thích hợp với các thao tác thêm vào, loại bỏ, ghép nhiều danh sách. 3.3. Tổ chức danh sách liên kết Mỗi phần tử của danh sách liên kết gồm hai thành phần: + Phần Data chứa dữ liệu thực sự của từng phần tử trong danh sách. + Phần Link dùng để liên kết một phần tử với phần tử ngay sau nó. Data Link Từ một phần tử ta chỉ duy trì một liên kết đến phần tử ngay sau nó nên danh sách liên kết được tổ chức như vậy được gọi là danh sách liên kết đơn. Trong phần này ta chỉ xét cấu trúc dữ liệu danh sách liên kết đơn nên không gây nhầm lẫn khi ta gọi là danh sách liên kết. Hình ảnh một danh sách liên kết biểu diễn danh sách L = (a1, a2, , an) như sau. Head a1 a2 an Hình 2.4 Hình ảnh danh sách liên kết đơn 25
26. Để quản lý danh sách biểu diễn bởi danh sách liên kết ta chỉ cần quản lý phần tử đầu tiên của danh sách. Từ phần tử này ta có thể thao tác được với các phần tử của danh sách nhờ liên kết giữa các phần tử. Khai báo danh sách liên kết có dạng: Type ElementType = ;{Định nghĩa kiểu phần tử của danh sách} ListLink = ^Cell; Cell = Record Data : ElementType; Link : ListLink; End; Var Head : ListLink; Ví dụ : Tổ chức danh sách nhân viên kiểu danh sách liên kết như sau: Type DSCB = ^HSCB; HSCB =Record Ho_Ten : String[30]; NamSinh : 1900 3000; Lk : DSCB; End; Var ds1, ds2: DSCB; 3.4. Các phép toán trên danh sách liên kết 3.4.1. Khởi tạo danh sách liên kết Procedure Init(var Head : ListLink); Begin Head:=Nil; End; 3.4.2. Thêm một phần tử vào danh sách Thêm phần tử x vào sau phần tử ở vị trí p trong danh sách có phần tử đầu là Head. p Head x q Hình 2.5. Thêm một phần tử vào danh sách liên kết 26
27. Thủ tục thêm một phần tử vào vị trí sau p. Trong thủ tục ta xét trường hợp khi danh sách rỗng thì phần tử thêm vào chính là phần tử duy nhất của danh sách. Chi tiết thủ tục như sau: Procedure Insert(var Head:ListLink; x:ElementType; p : ListLink); var q : ListLink; Begin New(q); q^.Data := x; if Head = Nil then begin q^.Link:=nil; Head:=q; end else begin q^.Link := p^.Link; p^.Link := q; end; End; 3.4.3. Loại bỏ một phần tử khỏi danh sách Giả sử cần loại bỏ phần tử ngay sau phần tử ở vị trí p trong danh sách có phần tử đầu là Head. p q Head Hình 2.6. Xóa một phần tử trong danh sách liên kết Procedure Delete(var Head : ListLink; p : ListLink); var q : ListLink; Begin q := p^.Link; if q<>nil then begin p^.Link := q^.Link; Dispose(q); end; End; Dễ thấy độ phức tạp của thao tác thêm và xóa trong danh sách liên kết là O(1). 27
28. 3.4.4. Tìm một phần tử trong danh sách liên kết Cho danh sách liên kết có phần tử đầu Head. Cần tìm một phần tử có khóa Key bằng một giá trị x cho trước. Với cách tổ chức dữ liệu của danh sách liên kết, việc truy xuất các phần tử là tuần tự nên thao tác tìm kiếm phải dùng thuật toán tìm tuần tự. Thủ tục tìm khóa x trong danh sách Head, kết quả trả về qua giá trị found và vị trí của phần tử tìm được p. Procedure Search(Head:ListLink; x:KeyType; var found:Boolean; var p:ListLink); Begin p:=Head; found:=false; While (p^.link nil Do p:=p^.Link; p^.Link := Head2; End; End; 28
29. 3.5. So sánh cấu trúc dữ liệu danh sách liên kết đơn và mảng Khi biểu diễn danh sách bằng mảng phải ước lượng số phần tử tối đa của danh sách. Điều này gây ra lãng phí bộ nhớ trong trường hợp danh sách có ít phần tử nhưng sẽ không thêm phần tử vào danh sách được khi số phần tử nhiều. Trong khi đó biểu diễn danh sách bằng danh sách liên kết đơn sử dụng cơ chế cấp phát động nên bộ nhớ dùng cho danh sách được sử dụng đúng với số phần tử của danh sách tại mọi thời điểm do đó ít gây lãng phí ô nhớ và danh sách chỉ đầy khi không còn không gian nhớ để cấp phát. Tuy nhiên danh sách liên kết phải dùng một phần bộ nhớ để liên kết các phần tử trong danh sách. Trong danh sách tổ chức bằng mảng, thao tác truy xuất các phần tử là truy xuất trực tiếp nhưng các thao tác thêm một phần tử, xóa một phần tử có thời gian tỷ lệ với số phần tử của danh sách. Đối với danh sách liên kết đơn các thao tác thêm vào và xóa một phần tử được thực hiện với thời gian hằng trong khi thao tác với một phần tử là tuần tự. Tùy thuộc vào ứng dụng cụ thể của danh sách với các phép toán thường dùng của nó mà lựa chọn cách tổ chức danh sách bằng mảng hay danh sách liên kết. 3.6. Một số dạng danh sách liên kết khác Một trong những hạn chế của danh sách liên kết đơn là phải quản lý được phần tử đầu tiên của danh sách và những thao tác với một phần tử phải biết phần tử ngay trước nó. Những hạn chế này có thể được khắc phục phần nào bởi việc thay đổi kiểu liên kết. Trong phần này giới thiệu 2 loại danh sách liên kết khác là liên kết vòng và liên kết kép. 3.6.1. Danh sách liên kết vòng Danh sách liên kết vòng là danh sách liên kết đơn với một thay đổi là phần tử cuối của danh sách liên kết với phần tử đầu tiên. Hình ảnh của danh sách liên kết vòng như hình sau. l Hình 2.8. Danh sách liên kết vòng Với cách tổ chức như trên, trong trường hợp không quan tâm đến thứ tự trước-sau của các phần tử, để quản lý danh sách ta chỉ cần quản lý phần tử bất kỳ trong danh sách mà không nhất thiết phải quản lý phần tử đầu tiên vì từ vị trí bất kỳ ta đều có thể truy xuất đến những phần tử còn lại của danh sách bằng cách duyệt tuần tự. Về tổ chức dữ liệu, danh sách liên kết vòng có tổ chức hoàn toàn giống danh sách liên kết đơn. Để quản lý danh sách liên kết vòng ta dùng một biến con trỏ quản lý một phần tử bất kỳ, phần tử này gọi là phần tử hiện tại của danh sách. Trên danh sách liên kết vòng thường thực hiện các thao tác sau: 29
30. - Thêm một phần tử vào ngay sau phần tử hiện tại của danh sách. - Thêm một phần tử vào ngay trước phần tử hiện tại của danh sách. - Xóa phần tử ngay sau phần tử hiện tại. - Duyệt danh sách. Cách tổ chức dữ liệu cho danh sách liên kết vòng giống như danh sách liên kết: Type ListLink = ^Cell; Cell = Record Data : ElementType; Link : ListLink; End; var l : ListLink; Các thủ tục trên danh sách liên kết vòng được mô tả như sau: Thêm vào sau a) Thêm và o danh l sách rỗng x b) Thêm và o danh sách khác rỗng l x Hình 2.9 Thêm vào sau phần tử hiện tại trong danh sách liên kết vòng Procedure InsertAfter(var l:ListLink; x:ElementType); var p:ListLink; Begin New(p); p^.Data := x; if l = nil then begin l:=p; l^.link:=l; end else begin p^.link := l^.link; l^.link := p; end; End; Thêm vào trước 30
31. l x Hình 2.10 Thêm vào trước phần tử hiện tại trong danh sách liên kết vòng Thủ tục thêm vào trước được thực hiện bằng cách thêm vào sau và chuyển phần tử hiện tại của danh sách là phần tử vừa thêm vào. Procedure InsertBefore(var l: ListLink; x:ElementType); Begin InsertAfter(l, x); l := l^.link; End; Xóa phần tử sau a) Xóa danh sách có 1 phần tử p l b) Xóa danh sách nhiều hơn 1 phần tử l p Hình 2.11 xóa phần tử sau phần hiện tại trong danh sách liên kết vòng Procedure DeleteAfter(var l : ListLink); var p : ListLink; Begin if l<>nil then begin p:=l^.link; if l^.link = l then l:=nil else l^.link := p^.link; dispose(p); end; End; Duyệt danh sách 31
32. Thao tác duyệt danh sách liên kết vòng được thực hiện tương tự như thao tác duyệt danh sách liên kết đơn với chú ý vị trí của phần tử xuất phát để tránh duyệt lại danh sách. Procedure Traverse(l : ListLink); var p : ListLink; Begin if l<>nil then begin p:=l; repeat write(p^.data:4); p:=p^.link; until p=l; end; End; Trong một số trường hợp ta có thể tổ chức danh sách liên kết vòng tốt hơn bằng cách dùng một phần tử đặc biệt để đánh dấu phần tử đầu tiên. Với cách tổ chức này danh sách liên kết vòng luôn khác rỗng vì luôn có phần tử đặc biệt. 3.6.2. Danh sách liên kết kép Khi làm việc với những danh sách mà việc thao tác trên một phần tử của nó liên quan đến cả phần tử ngay trước và ngay sau nó thì việc tổ chức danh sách bằng liên kết đơn thì không đáp ứng được. Trong các trường hợp như vậy mỗi phần tử của danh sách thường được dùng hai liên kết đến phần tử ngay trước và ngay sau nó, danh sách như vậy gọi là danh sách liên kết kép. left right Hình 2.12 Danh sách liên kết kép Vì danh sách liên kết kép có thể duyệt theo cả hai chiều nên cần quản lý cả hai phần tử đầu và cuối danh sách. Khai báo dữ liệu cho danh sách liên kết kép như sau: Type DLink = ^Cell2L; Cell2L = Record Data : ElementType; LLink, RLink : DLink; End; List2Link = Record Left, Right : DLink; End; Var l : List2Link; 32
33. Các thao tác cơ bản trên danh sách liên kết kép: Khởi tạo Procedure Init(var l : List2Link); Begin l.Left := nil; l.Right:= nil; End; Thêm một phần tử vào trước phần tử ở vị trí p left x right p Hình 2.13 Thêm một phần tử vào vị trí p trong danh sách liên kết kép Procedure InsertBefore(var l:List2Link;p:DLink; x:ElementType); var q,p1 : DLink; Begin New(q); q^.Data:= x; {danh sách rỗng} if (l.Left=nil) and (l.Right=nil) then begin q^.LLink:=nil; q^.RLink:=nil; l.Left:=q; l.Right:=q; end else Begin if l.Left = p then {thêm vào đầu} begin q^.LLink:=nil; q^.RLink:=p; p^.LLink:=q; l.Left:=q; end else begin p1:=p^.LLink; q^.LLink:=p1; p1^.Rlink:=q; q^.RLink:=p; p^.LLink:=q; end; end; 33
34. End; Xóa phần tử tại vị trí p right left p Hình 2.14 Thêm một phần tử tại vị trí p trong danh sách liên kết kép Procedure Delete(var l : List2Link; p : DLink); Begin if l.Left=p then {xóa phần tử đầu} l.Left := p^.RLink else if l.Right=p then {xóa phần tử cuối} l.Right:=p^.LLink else begin p^.LLink^.RLink:=p^.RLink; p^.RLink^.LLink:=p^.LLink; end; dispose(p); End; Duyệt danh sách liên kết kép Có thể duyệt từ trái sang phải hoặc ngược lại. Thủ tục duyệt từ trái sang phải được thực hiện như sau: Procedure Traverse(l : List2Link); var p : DLink; Begin p:=l.Left; while p<>nil do begin Visit(p); p:=p^.RLink; end; End; 4. NGĂN XẾP (STACK) Trong một số trường hợp chúng ta sử dụng một mô hình dữ liệu nhưng chỉ dùng một số trong các thao tác trên mô hình đó. Khi đó mô hình dữ liệu cùng với một số phép toán cụ thể trên mô hình đó gọi là một kiểu dữ liệu trừu tượng (abstract data type). Trong phần sau ta xét hai kiểu dữ liệu trừu tượng có ứng dụng nhiều trong các thuật toán tin học là ngăn xếp và hàng đợi. 34
35. 4.1. Khái niệm Ngăn xếp là một dạng danh sách đặc biệt chỉ được thực hiện hai thao tác: thêm một phần tử vào cuối danh sách (push) và lấy phần tử cuối ra khỏi danh sách (pop). Hình ảnh một ngăn xếp push pop a4 a3 a2 a1 Hình 2.15 Hình ảnh ngăn xếp Như vậy trong một ngăn xếp phần tử đưa vào sau sẽ được lấy ra trước nên còn gọi là danh sách kiểu LIFO (Last in First out). Vị trí của phần tử cuối cùng của ngăn xếp còn gọi là đỉnh (top) của ngăn xếp. Ngăn xếp là một kiểu dữ liệu trừu tượng có nhiều ứng dụng trong tin học. Trong các ngôn ngữ lập trình bậc cao bao giờ cũng dành riêng một vùng nhớ gọi là Stack dùng để lưu lại các giá trị của biến, hằng, mỗi khi có lời gọi thủ tục, các giá trị này được lấy lại mỗi khi có một lời gọi thực hiện xong. Việc lưu các giá trị như trên phải theo nguyên tắc hoạt động của ngăn xếp vì lời gọi thủ tục cuối cùng sẽ kết thúc trước. Do đó ngăn xếp là một cách tổ chức dữ liệu được dùng nhiều trong các chương trình chuyển từ đệ quy sang lặp. Trong các chương trình dịch (compiler) thường phải biến đổi các biểu thức trung tố thành các biểu thức tương đương ở dạng hậu tố. Chẳng hạn biểu thức (3 + 4) * 2 được chuyển thành 3 4 + 2 *. Việc chuyển các biểu thức từ trung tố thành hậu tố và tính giá trị các biểu thức hậu tố phải dùng cấu trúc dữ liệu kiểu ngăn xếp để lưu các kết quả trung gian. Chi tiết các thuật toán này sẽ được trình bày trong phần sau. Như đã đề cập ở khái niệm của ngăn xếp, các thao tác trên ngăn xếp gồm hai thao tác cơ bản là : push(x,S) : đưa phần tử x vào ngăn xếp S. pop(x) : lấy phần tử ở đỉnh ngăn xếp S ra và lưu vào biến x. Ngoài ra còn các thao tác bổ sung: Init(S) : khởi tạo một ngăn xếp S rỗng. Empty(S) : cho biết ngăn xếp S có rỗng không. Full(S) : cho biết ngăn xếp S có đầy không. Clear(S) : làm rỗng ngăn xếp S. 35
36. Tương tự như mô hình danh sách, trên ngăn xếp cũng có thể tổ chức bằng mảng và danh sách liên kết. Trong phần sau trình bày hai cách tổ chức dữ liệu cho ngăn xếp. 4.2. Tổ chức ngăn xếp bằng mảng 4.2.1. Tổ chức dữ liệu Vì thao tác thêm vào và lấy ra chỉ thực hiện ở đỉnh của ngăn xếp nên dùng một biến để quản lý vị trí đỉnh của ngăn xếp. Một ngăn xếp tổ chức bằng mảng bao gồm hai thành phần: + Một mảng để lưu các phần tử của mảng. + Vị trí đỉnh của ngăn xếp. Hình ảnh ngăn xếp S=(a1,a2, ,an) tổ chức bằng mảng như sau: MaxLength Top an 2 a2 1 a1 Hình 2.16 Hình ảnh ngăn xếp tổ chức bằng mảng Khai báo: Const MaxLength = ; {Số phần tử tối đa của ngăn xếp} Type ElementType = ; {Định nghĩa kiểu phần tử cho ngăn xếp} StackArr =Record Element : Array[1 MaxLength] Of ElementType; Top : 0 MaxLength; End; Var S : StackArr; 4.2.2. Các thao tác trên ngăn xếp Khởi tạo: Đặt đỉnh ngăn xếp tại vị trí 0. 36
37. Procedure Init(var S : StackArr); Begin S.Top := 0; End; Hàm Empty: Kiểm tra đỉnh ngăn xếp nếu top=0 thì ngăn xếp rỗng. Function Empty(S : StackArr):Boolean; Begin Empty := S.Top = 0; End; Hàm Full: Kiểm tra đỉnh ngăn xếp nếu top=MaxLength thì ngăn xếp đầy. Function Full(S : StackArr):Boolean; Begin Full := S.Top = MaxLength; End; Thêm vào: thêm phần tử x vào ngăn xếp S. Procedure Push(x : ElementType; var S : StackArr); Begin if not Full(S) then with S do begin Inc(Top); element[top]:=x; end; End; Lấy ra: lấy một phần tử từ ngăn xếp S ra biến x. Procedure Pop(var x : ElementType; var S : StackArr); Begin if not Empty(S) then with S do begin x:=element[top]; Dec(Top); end; End; Độ phức tạp tính toán: Các thao tác thêm vào và lấy ra đều thực hiện tại đỉnh của ngăn xếp nên độ phức tạp các thao tác này là O(1). 37
38. 4.3. Tổ chức ngăn xếp bằng danh sách liên kết 4.3.1. Tổ chức dữ liệu Một ngăn xếp tổ chức bằng danh sách liên kết cũng giống như những danh sách khác, trong đó đỉnh của ngăn xếp chính là con trỏ của danh sách liên kết. Hình ảnh của ngăn xếp S = (a1, a2, , an) tổ chức bằng danh sách liên kết như sau: S an a2 a1 Hình 2.17 Hình ảnh ngăn xếp tổ chức bằng danh sách liên kết 4.3.2. Khai báo Type StackLink = ^Cell; Cell = Record Data : ElementType; Link : StackLink; End; Var S : StackLink; 4.3.3. Các thao tác Khởi tạo:Đỉnh ngăn xếp trỏ đến nil Procedure Init(var S : StackLink); Begin S := Nil; End; Hàm Empty Function Empty(S : StackLink):Boolean; Begin Empty := S = Nil; End; Thêm vào một phần tử: thêm phần tử x vào ngăn xếp S 38
39. p x S an a2 a1 Hình 2.18. Thêm một phần tử vào ngăn xếp tổ chức bằng danh sách liên kết Procedure Push(x : ElementType; var S : StackLink); var p : StackLink; Begin New(p); p^.Data:=x; p^.Link:=S; S:=p; End; Lấy ra một phần tử p S an an-1 a2 a1 Hình 2.19 Lấy một phần tử từ ngăn xếp tổ chức bằng danh sách liên kết Procedure Pop(var x:ElementType; var S:StackLink); var p:StackLink; Begin if not Empty(S) then begin x := S^.Data; p := S; S:=p^.Link; Dispose(p); end; End; 39
40. Làm rỗng ngăn xếp: xóa và thu hồi các ô nhớ. Procedure Clear(var S:StackLink); var p : StackLink; Begin while not Empty(S) do begin p := S; S:=p^.Link; Dispose(p); end; End; 4.4. Ứng dụng của ngăn xếp 4.4.1. Khử đệ qui Giải thuật đệ qui là một trong những giải thuật thường dùng trong lập trình, tuy nhiên các thủ tục đệ qui khi cài đặt trên các ngôn ngữ lập trình phụ thuộc vào kích thước vùng nhớ dành cho Stack mà cho phép các thủ tục đệ qui được gọi bao nhiêu lần. Hơn nữa các thủ tục đệ qui dễ cài đặt nhưng khó hình dung chi tiết các bước thực hiện. Một số dạng thuật toán đệ qui có thể khử đệ qui bằng cách dùng một ngăn xếp để điều khiển quá trình gọi đệ qui. Chẳng hạn xét bài toán tháp Hà nội, ta có hai thuật toán đệ qui và không đệ qui như sau: Thuật toán đệ qui: Gọi số tầng cần phải chuyển là n, vị trí cọc xuất phát là s, vị trí cọc chuyển đến là d, cọc trung gian là t. Ta có thuật toán đệ qui chuyển tháp như sau: Nếu n = 1 thì chuyển một tầng từ s đến d. Ngược lại, nếu n > 1 thì + Chuyển n-1 tầng trên cùng từ s đến t. + Chuyển 1 tầng từ s đến d. + Chuyển n-1 tầng từ t sang d. Thủ tục chuyển đĩa dạng đệ qui được thể hiện như sau: Procedure Chuyen(n, s, d, t : Byte); Begin if n=1 then writeln(s,' >',d); else begin Chuyen(n-1, s, t, d); Chuyen(1, s, d, t) Chuyen(n-1, t, d, s); end; End; 40
41. Thuật toán không đệ qui: Dùng một Stack, mỗi phần tử chứa một bộ dữ liệu gồm (n,s,d,t). Việc gọi đệ qui trong thuật toán trên tương ứng với việc đưa một bộ dữ liệu vào ngăn xếp. Lúc đầu ngăn xếp được khởi tạo với bộ (n, 1, 2, 3). Quá trình lặp lại cho đến khi ngăn xếp rỗng. Thủ tục khử đệ qui như sau: Procedure Chuyen_Lap(n, s, d, t : Byte); var st : Stack; sn, ss, sd, st : Byte; Begin Init(st); Push(n, s, d, t, st); Repeat pop(ns,ss,ds,ts,st); if ns = 1 then writeln(ss,' >',ds) else begin push(ns-1,ts,ds,ss,st); push(1,ss,ds,ts,st); push(ns-1,ss,ts,ds,st); end; Until Empty(st); End; 4.4.2. Tính giá trị của các biểu thức Tính giá trị của biểu thức là công việc thường làm của các ngôn ngữ lập trình. Thông thường các ngôn ngữ lập trình tính giá trị biểu thức bằng cách: + Chuyển biểu thức từ dạng trung tố (infix) sang dạng hậu tố (posfix). + Tính giá trị biểu thức hậu tố. Biểu thức trung tố là cách con người thường sử dụng, trong biểu thức trung tố các phép toán hai ngôi được viết giữa hai toán hạng. Việc tính trực tiếp các biểu thức trung tố gặp khó khăn vì phải dùng các cặp dấu ngoặc đơn để qui định thứ tự thực hiện các biểu thức con. Để tính các biểu thức, người Balan đã đưa ra một ký pháp qui định cách viết các biểu thức (gọi là ký pháp Balan) trong đó các phép toán được đặt sau toán hạng. Việc dùng ký pháp Balan không cần dấu ngoặc nhưng vẫn thể hiện được thứ tự ưu tiên khi tính giá trị biểu thức nên dễ dàng xây dựng thuật toán tính. Ví dụ: Biểu thức dạng trung tố 3+(5-2)*3/7-4 được viết dưới dạng biểu thức hậu tố : 3 5 2 - 3 * 7 / 4 + - Thuật toán chuyển từ biểu thức trung tố sang hậu tố 41
42. Giả sử ta có một biểu thức E dạng trung tố trong đó ta có thể phân tích thành các thành phần của biểu thức là các toán hạng và phép toán. Dùng một ngăn xếp S mỗi phần tử là phép toán hoặc dấu ngoặc mở. Kết quả đưa ra biểu thức hậu tố E1. Thuật toán: 1. Khởi tạo biểu thức E1 rỗng 2. Duyệt lần lượt các thành phần của biểu thức E, với mỗi thành phần x thực hiện 2.1 Nếu x là toán hạng thì nối vào bên phải biểu thức E1 2.2 Nếu x là dấu ngoặc mở thì đưa vào ngăn xếp 2.3 Nếu x là phép toán thì a. Đọc phần tử y ở đầu ngăn xếp b. Nếu độ ưu tiên của y cao hơn x thì Lấy y ra khỏi ngăn xếp Nối y vào bên phải E1 Lặp lại bước a. c. Nếu độ ưu tiên của x cao hơn y thì đưa x vào ngăn xếp 2.4 Nếu x là dấu ngoặc đóng thì a. Đọc phần tử y ở đầu ngăn xếp b. Nếu y là phép toán thì Lấy y ra khỏi ngăn xếp Nối y vào bên phải biểu thức E1 Lặp lại bước a. c. Nếu y là dấu ngoặc mở thì lấy ra khỏi ngăn xếp 3. Lặp lại bước 2 cho đến hết biểu thức E. 4. Lấy lần lượt các phần tử của ngăn xếp và nối vào bên phải biểu thức E1 cho đến khi ngăn xếp rỗng. Ví dụ: Với biểu thức E = (2+7*3-8)*4-(3+2)*3-2, thuật toán chuyển thành biểu thức hậu tố thực hiện qua các bước thể hiện qua các kết quả ở bảng sau: Thành phần của Ngăn xếp Biểu thức E1 biểu thức E ( (  2 ( 2 + (+ 2 7 (+ 2 7 * ( + * 2 7 3 ( + * 2 7 3 - ( - 2 7 3 * + 8 ( - 2 7 3 * + 8 42
43. )  2 7 3 * + 8 - * * 2 7 3 * + 8 - 4 * 2 7 3 * + 8 - 4 - - 2 7 3 * + 8 - 4 * ( - ( 2 7 3 * + 8 - 4 * 3 - ( 2 7 3 * + 8 - 4 * 3 + - ( + 2 7 3 * + 8 - 4 * 3 + 2 - ( + 2 7 3 * + 8 - 4 * 3 2 ) - 2 7 3 * + 8 - 4 * 3 2 + * - * 2 7 3 * + 8 - 4 * 3 2 + 3 - * 2 7 3 * + 8 - 4 * 3 2 + 3 - - 2 7 3 * + 8 - 4 * 3 2 + 3 * - 2 - 2 7 3 * + 8 - 4 * 3 2 + 3 * - 2  2 7 3 * + 8 - 4 * 3 2 + 3 * - 2 - Thuật toán tính giá trị biểu thức hậu tố Cho biểu thức viết dưới dạng hậu tố E1. Để tính giá trị của biểu thức ta dùng một ngăn xếp S lưu các toán hạng và các kết quả tính toán trung gian. Thuật toán: 1. Duyệt lần lượt các phần tử của biểu thức E1, với thành phần x thực hiện: Nếu x là toán hạng thì đưa vào ngăn xếp Nếu x là phép toán thì lấy hai phần tử đầu ngăn xếp thực hiện tính theo phép toán và đưa kết quả vào ngăn xếp 2. Lặp lại bước 1 cho đến khi hết biểu thức. 3. Giá trị duy nhất còn lại của ngăn xếp là kết quả của biểu thức E1. Ví dụ: Kết quả tính biểu thức hậu tố E1=2 7 3*+8-4*3 2+3*-2- qua các bước được biểu diễn bởi bảng sau: Thành phần biểu thức E1 Ngăn xếp 2 2 7 2 7 3 2 7 3 * 2 21 + 23 8 23 8 - 15 4 15 4 * 60 3 60 3 2 60 3 2 + 60 5 3 60 5 3 * 60 15 - 45 43
44. 2 45 2 - 53 5. HÀNG ĐỢI (QUEUE) 5.1. Khái niệm Hàng đợi là một kiểu dữ liệu trừu tượng xây dựng trên mô hình danh sách với hai thao tác cơ bản: + Thêm một phần tử vào cuối hàng đợi. + Lấy phần tử đầu ra khỏi hàng đợi. Hàng đợi được thực hiện theo nguyên tắc: các phần tử đưa vào trước lấy ra trước nên còn gọi là danh sách FIFO (First In First Out). Hàng đợi Q = (a1, a2, , an) được thể hiện bằng hình dưới. a1 a2 an Lấy ra Thêm và o Hình 2.20. Hình ảnh một hàng đợi Trong thực tế ta thường gặp những công việc thực hiện theo nguyên tắc của hàng đợi, chẳng hạn việc đăng ký mua vé tàu, việc chuyển các toa tàu trên một đường sắt, Trong máy tính mô hình hàng đợi được dùng khá phổ biến. Những hàng đợi được tạo ra khi có nhiều hơn một quá trình đòi hỏi được xử lý, chẳng hạn như máy in, ổ đĩa hay bộ xử lý trung tâm. Khi các quá trình đòi hỏi một tài nguyên, chúng được đặt trong một hàng đợi để chờ phục vụ. Ví dụ, nhiều máy tính có thể được phân phối để sử dụng một máy in, và một hàng đợi spool (Simultanous Peripherial Output On Line - đưa ra đồng thời với quá trình tính toán) được dùng để lập kế hoạch cho các yêu cầu đầu ra theo kiểu “đến trước được phục vụ trước”. Nếu có một yêu cầu cho máy in và máy in rỗi, nó sẽ được cấp phát ngay lập tức công việc này. Trong khi in, một số công việc khác có thể cần đến máy in, chúng được đặt trong spool để chờ đến lượt. Khi công việc hiện thời của máy in kết thúc, máy in được giải phóng khỏi công việc ấy và được cấp phát cho công việc đầu tiên trong hàng spool. Một ứng dụng quan trọng khác của hàng đợi trong máy tính là tổ chức vùng đệm cho các đầu vào/ra (input/output buffering). Việc truyền thông tin từ một thiết bị vào hay đến một thiết bị ra là một thao tác tương đối chậm, do đó nếu phải tạm dừng chương trình trong khi truyền dữ liệu thì ảnh hưởng rất lớn đến tốc độ thực hiện chương trình. Một cách giải quyết thường dùng trên máy tính là dùng các phần của bộ nhớ trong, gọi là vùng đệm (buffer) và việc truyền dữ liệu từ một chương trình sẽ được truyền qua vùng đệm mà không thao tác trực tiếp với các thiết bị vào/ra. Chẳng hạn, một chương trình đọc dữ liệu từ một tệp trên đĩa, dữ liệu sẽ được truyền từ đĩa sang vùng đệm đầu vào trong bộ nhớ chính, trong khi bộ 44
45. xử lý trung tâm đang thực hiện một nhiệm vụ khác nào đó. Khi chương trình đòi hỏi dữ liệu, những giá trị tiếp theo trong hàng đợi này được lấy ra. Trong khi dữ liệu này đang xử lý thì các dữ liệu khác có thể được truyền từ tệp sang vùng đệm. Rõ ràng vùng đệm phải được thực hiện theo kiểu vào trước ra trước. 5.2. Tổ chức hàng đợi bằng mảng 5.2.1. Tổ chức Hàng đợi tổ chức bằng mảng cũng giống như mô hình danh sách nhưng cần 2 thành phần để lưu vị trí phần tử sẽ được lấy ra ở đầu hàng đợi (front) và vị trí phần tử thêm vào cuối cùng của hàng đợi (rear). a1 a2 an 1 maxlength front rear Hình 2.21 Hình ảnh một hàng đợi tổ chức bằng mảng 5.2.2. Khai báo Const MaxLength = ; {Số phần tử tối đa của hàng đợi} Type ElementType = ; {Định nghĩa kiểu phần tử cho hàng đơi} QueueArr = Record Element: Array[1 MaxLength] Of ElementType; Front, Rear : 0 MaxLength; End; Var Q : QueueArr; 5.2.3. Cài đặt các thao tác trên hàng đợi Khởi tạo hàng đợi Procedure InitQueue(var Q : QueueArr); Begin Q.front:=1; Q.rear:=0; End; Hàm Empty Function Empty(Q : QueueArr):Boolean; Begin Empty:= Q.rear = 0; End; 45
46. Hàm Full Function Full(Q : QueueArr):Boolean; Begin Full:= Q.rear = MaxLength; End; Thêm vào một phần tử Thêm phần tử x vào hàng đợi Q. Procedure AddQueue(x : ElementType; var Q : QueueArr); Begin If not Full(Q) Then begin Q.rear := Q.rear + 1; Q.element[Q.rear]:=x; end; End; Lấy một phần tử ra khỏi hàng đợi Q. Lấy phần tử đầu ra khỏi hàng đợi Q, kết quả đưa vào biến x. Trong trường hợp phần tử lấy ra là phần tử cuối cùng (front = rear) thì khởi tạo lại các giá trị của front và rear. Trong các trường hợp còn lại tăng vị trí của front. Procedure RemoveQueue(var x:ElementType;var Q: QueueArr); Begin If not Empty(Q) Then begin x:=Q.element[Q.front]; if Q.front = Q.rear then begin Q.front:=1; Q.rear:=0; end else Q.front := Q.front + 1; end; End; Nhận xét: Với cách tổ chức hàng đợi bằng mảng và các thao tác cài đặt như trên sẽ gặp hạn chế khi thao tác lấy ra không làm cho hàng rỗng vì khi đó các thao tác thêm vào và lấy ra sẽ làm cho phần sử dụng của hàng sẽ chuyển về cuối mảng, và đến một lúc nào đó ta không thể thêm vào hàng đợi vì vị trí rear đã đạt giá trị tối đa của kích thước mảng. Khi đó ta nói hàng bị tràn. Trong nhiều trường hợp khi hàng bị tràn thì vẫn chưa đầy vì các phần tử ở đầu mảng vẫn không được sử dụng do các thao tác lấy ra khỏi hàng đợi. Để khắc phục tình trạng hàng bị tràn thường dùng 2 cách khắc phục là di chuyển tịnh tiến và di chuyển vòng. 46
47. 5.2.4. Khắc phục tràn hàng đợi bằng cách di chuyển tịnh tiến Việc di chuyển tịnh tiến hàng được thực hiện khi thêm vào hàng đang ở tình trạng bị tràn, khi đó các phần tử của hàng được di chuyển về phía trước front - 1 vị trí. Sau khi di chuyển thì front=1 (xem hình). front rear 1 maxlength a1 a2 an a1 a2 an front rear Hình 2.22 Di chuyển tịnh tiến trên hàng đợi Trong khi khắc phục hàng tràn bằng di chuyển tịnh tiến ta luôn có front rear và hàng đầy khi rear-front+1=maxlength. Hàm Full Function Full(Q : QueueArr):Boolean; Begin Full:= Q.rear - Q.front + 1 = MaxLength; End; Thêm vào một phần tử Thêm phần tử x vào hàng đợi Q có khắc phục tràn bằng dời tịnh tiến. Procedure AddQueue(x : ElementType; var Q : QueueArr); var i : Integer; Begin If not Full(Q) Then begin If Q.rear = MaxLength then {dời tịnh tiến} begin {dời hàng lên Q.front-1 vị trí} For i:=Q.front To Q.rear Do Q.element[i-Q.front+1]:=Q.element[i]; Q.rear:= MaxLength-Q.front+1; Q.Front:=1; end else Q.rear := Q.rear + 1; Q.element[Q.rear]:=x; end; End; Khắc phục tràn hàng đợi bằng di chuyển tịnh tiến thao tác thêm có độ phức tạp trong trường hợp xấu nhất là O(n), với n là số phần tử của hàng đợi. Để giảm 47
48. độ phức tạp trong các thao tác thêm nhưng vẫn khắc phục được tình trạng tràn hàng có thể tổ chức hàng đợi bởi mảng vòng tròn. 5.2.5. Khắc phục tràn hàng đợi bằng di chuyển vòng rear fro nt 1 maxlengt h Hình 2.23 Khắc phục tràn hàng bằng di chuyển vòng Trong cách tổ chức hàng bằng mảng vòng tròn không bắt buộc các vị trí front và rear phải thỏa front rear mà các vị trí này di chuyển theo kiểu vòng tròn, nghĩa là khi tăng đến maxlength thì các vị trí này chuyển về 1. Do đó có những trường hợp front rear. Với mảng vòng tròn như trên, hàng tràn trong các trường hợp rear- front+1=0 hoặc rear-front+1=maxlength. Hàm Full Function Full(Q : QueueArr):Boolean; Begin Full:= (Q.rear - Q.front + 1 = MaxLength) or (Q.rear - Q.front + 1 = 0); End; Thêm vào một phần tử Thêm phần tử x vào hàng đợi Q có khắc phục tràn bằng di chuyển vòng. Procedure AddQueue(x : ElementType; var Q : QueueArr); var i : Integer; Begin If not Full(Q) Then begin If Q.rear = MaxLength then Q.rear:=1 else Q.rear := Q.rear + 1; Q.element[Q.rear]:=x; 48
49. end; End; Lấy một phần tử ra khỏi hàng đợi Q. Lấy phần tử đầu ra khỏi hàng đợi Q, kết quả đưa vào biến x. Trong trường hợp phần tử lấy ra là phần tử cuối cùng (front=rear) thì khởi tạo lại các giá trị của front và rear. Trường hợp vị trí front là vị trí cuối cùng của mảng thì vị trí tiếp theo là 1. Trong các trường hợp còn lại tăng vị trí của front. Procedure RemoveQueue(var x:ElementType; var Q:QueueArr); Begin If not Empty(Q) Then begin x:=Q.element[Q.front]; if Q.front = Q.rear then begin Q.front:=1; Q.rear:=0; end else if Q.front = maxlength then Q.front:=1 else Q.front := Q.front + 1; end; End; 5.3. Tổ chức hàng đợi bằng danh sách liên kết 5.3.1. Tổ chức Cũng như ngăn xếp, ta có thể dùng danh sách liên kết để biểu diễn hàng đợi. Do thao tác thêm vào và lấy ra trên hàng đợi được lấy ra ở hai vị trí khác nhau nên ta dùng hai con trỏ front và rear để lưu hai vị trí này. front rear Hình 2.24. Biểu diễn hàng đợi bằng danh sách liên kết Khai báo kiểu như sau: Type ListLink = ^Cell; Cell = Record Data : ElementType; Link : ListLink; End; QueueLink = Record front, rear : ListLink; End; 49
50. Var Q : QueueLink; 5.3.2. Cài đặt các thao tác trên hàng đợi Khởi tạo Procedure InitQueue(var Q : QueueLink); Begin Q.front:=Nil; Q.rear:=Nil; End; Thêm vào Queue a) Thêm và o hà ng đợi rỗng front rear p x b) Thêm và o danh sách khác rỗng front rear p x Hình 2.25 Thêm vào hàng đợi biểu diễn bằng danh sách liên kết Procedure AddQueue(x : ElementType; var Q : QueueLink); var p : ListLink; Begin New(p); P^.Data := x; P^.Link := Nil; If Empty(Q) Then begin Q.front:=p; Q.rear:=p; end Else begin Q.rear^.Link:= p; Q.rear:=p; end; End; Lấy một phần tử ra khỏi hàng đợi fro rear pnt Hình 2.26 Lấy một phần tử từ hàng đợi biểu diễn bằng danh sách liên kết Procedure RemoveQueue(var Q:QueueLink;var x:ElementType); var p : ListLink; Begin 50
51. If not Empty(Q) Then begin x:=Q.front^.Data; P:=Q.front; Q.front:=p^.Link; Dispose(p); If Q.front=Nil Then Q.rear:=Nil; end; End; 6. BÀI TẬP Bài 1. Cho một dãy số nguyên a1, a2, , an. Hãy tổ chức dữ liệu kiểu danh sách liên kết đơn để lưu dãy số và cài đặt các thủ tục thực hiện các công việc sau: - Thủ tục thêm một số vào đầu dãy số. - Thủ tục thêm một số vào cuối dãy số. - Thủ tục thêm một số vào sau vị trí p. - Thủ tục sắp xếp một dãy số theo thứ tự tăng. - Thủ tục thêm một số x vào dãy đã sắp tăng sao cho vẫn giữ được thứ tự. - Xóa một phần tử sau vị trí p. - Thủ tục tìm-xoá một số x trong dãy số. Dựa vào các thủ tục trên viết chương trình tổ chức dạng menu cho phép chọn thực hiện các công việc sau: - Nhập một dãy số gồm n số. - Sắp xếp dãy số - Chèn một số - Tìm và xóa một số - Xóa toàn bộ dãy số - In dãy số lên màn hình m Bài 2. Dùng ngăn xếp khử đệ quy của hàm tính Cn được viết như sau: Function combo(n,m : integer):longint; Begin If (n=1) or (m=0) or (m=n) then Combo:=1 Else combo:=combo(n-1,m)+combo(n-1.m-1); End; Bài 3. Cho một xâu S chỉ gồm các dấu ngoặc tròn (, ). Hãy nêu thuật toán và lập chương trình kiểm tra xem các dấu ngoặc trong xâu S có thể là các dấu ngoặc của một biểu thức hợp lệ không. 51
52. Ví dụ: xâu (()()) : hợp lệ; xâu (()))(: không hợp lệ; (()(()())))) : không hợp lệ. Bài 4. Bằng các thao tác cơ bản trên ngăn xếp và hàng đợi hãy trình bày các thuật toán: - Đảo ngược thứ tự một hàng đợi. - Tìm một phần tử có khóa của trường Key là x trong hàng đợi. Cài đặt các thuật toán trên bằng hàng đợi các số nguyên với cách tổ chức hàng đợi bằng danh sách liên kết. Bài 5. Trình bày thuật toán đảo ngược một danh sách liên kết bằng hai cách: - Đổi giá trị của các phần tử. - Đổi liên kết của các phần tử. Cài đặt các thuật toán trên cho danh sách các số nguyên. Nếu dùng thủ tục đệ qui thì hãy thử dùng ngăn xếp để khử đệ qui. Bài 6. (Danh sách liên kết bội) Để quản lý một danh sách các danh sách liên kết người ta tổ chức dữ liệu dạng danh sách bội. Mỗi phần tử trong danh sách bội quản lý một danh sách liên kết gồm các thành phần sau : - Thành phần head trỏ đến một danh sách liên kết đơn - Thành phần link liên kết tới danh sách tiếp theo (nếu có) Hãy tổ chức dữ liệu và trình bày các thuật toán thực hiện: - Tạo một danh sách bội trống : danh sách chưa có danh sách nào. - Thêm một danh sách mới (trống) vào đầu danh sách bội. - Thêm một phần tử x vào đầu danh sách trỏ bởi con trỏ plist trong danh sách bội. - Xóa phần tử sau vị trí p trong danh sách plist trong danh sách liên kết bội. - Xóa danh sách sau danh sách trỏ bởi con trỏ plist trong danh sách bội. - Tìm một khóa x trong danh sách bội. Kết quả trả về con trỏ trỏ đến ô chứa phần tử có khóa x tìm được đầu tiên. - Xóa tất cả các phần tử có khóa x trong danh sách bội. Cài đặt các thao tác trên cho danh sách bội chứa các số nguyên. Bài 7. Trong các danh sách tổ chức bằng liên kết đơn thường dùng thao tác chèn một phần tử vào cuối danh sách, để tiện thao tác thêm ta phải lưu vị trí phần tử cuối cùng. Hãy trình bày cách tổ chức dữ liệu và thuật toán thực hiện hai thao tác: thêm một phần tử vào cuối danh sách và xóa một phần tử sau vị trí p trong danh sách. Cài đặt các thuật toán trên cho danh sách các số nguyên. 52
53. Bài 8. Dùng ngăn xếp các số nguyên với các phép toán push, pop hãy lập chương trình đổi một số thập phân thành số nhị phân. Bài 9. Cài đặt chương trình tính biểu thức số học bằng cách chuyển biểu thức trung tố thành biểu thức hậu tố dùng ký pháp Balan. Giới hạn chỉ xét các biểu thức số học gồm các phép toán hai ngôi : +, -, *, / trên các số có 1 chữ số. Bài 10. Dùng danh sách liên kết đơn biểu diễn đa thức. Nêu thuật toán và cài đặt các thủ tục thực hiện : - Nhập một đa thức - Xuất một đa thức - Tính giá trị của đa thức tại x0 - Cộng hai đa thức - Nhân hai đa thức Bài 11. Cho một ngăn xếp với các thao tác cơ bản : Initialize, Empty, Push, Pop hãy trình bày thuật toán và viết các thủ tục thực hiện : a. Lấy ra phần tử cuối cùng của ngăn xếp. b. Lấy ra phần tử thứ n của ngăn xếp, với n là một số nguyên dương. Cài đặt cụ thể các thuật toán trên bằng ngăn xếp các số nguyên trên một ngôn ngữ lập trình cụ thể với cách tổ chức ngăn xếp bằng mảng. Bài 12. Cho một hàng đợi với các thao tác cơ bản: Initialize, Empty, Push, Pop hãy trình bày thuật toán và viết các thủ tục thực hiện: a. Lấy ra phần tử cuối cùng của hàng đợi. b. Lấy ra phần tử thứ k của hàng đợi, với k là một số nguyên dương. Cài đặt cụ thể các thuật toán trên bằng hàng đợi các số nguyên trên một ngôn ngữ lập trình cụ thể với cách tổ chức hàng đợi bằng danh sách liên kết. Bài 13. Dùng danh sách liên kết đơn trong đó các phần tử là các số nguyên được sắp theo thứ tự để cài đặt cho tập hợp các số nguyên. Hãy tổ chức dữ liệu, cài đặt các thủ tục: - Thêm một phần tử vào tập hợp. - Loại một phần tử khỏi tập hợp. - Kiểm tra một phần tử có trong tập hợp hay không. - Giao hai tập hợp - Hợp hai tập hợp - Hiệu hai tập hợp Từ các thủ tục trên hãy viết chương trình thực hiện các công việc: - Nhập vào hai tập hợp 53
54. - Tìm giao, hợp, hiệu hai tập hợp trên và in kết quả lên màn hình - Tạo tập hợp chứa các số tự nhiên liên tiếp từ 2 đến 1000 - Cài đặt thuật toán sàng Eratosthenes để tìm các số nguyên tố nhỏ hơn 10000. Bài 14. Trong một số ngôn ngữ lập trình bậc cao không có kiểu con trỏ. Hãy đề xuất một cách tổ chức dữ liệu biểu diễn danh sách liên kết cho những ngôn ngữ lập trình này. Cài đặt các thao tác cơ bản trên cách tổ chức dữ liệu trên. So sách với cách tổ chức bằng kiểu con trỏ. Hướng dẫn: dùng mảng để lưu các phần tử, phần liên kết là chỉ số của phần tử tiếp theo. Bài 15. Cho hai danh sách số nguyên tổ chức bằng mảng L1 = (a1, a2, , an) và L2 = (b1, b2, , bm). Hãy viết các hàm: a) LaDSCon(L1, L2) : trả về kết quả True nếu L2 là danh sách con của L1 và false trong trường hợp ngược lại. b) LaDayCon(L1, L2) : trả về kết quả True nếu L2 là dãy con của L1 và false trong trường hợp ngược lại. Hãy cài đặt các hàm trên trong trường hợp danh sách được tổ chức bằng danh sách liên kết. Từ đó so sánh độ phức tạp của hai thao tác trên đối với hai cách biểu diễn danh sách. Tổng quát thành thuật toán cho danh sách tổng quát cho hai thao tác trên. Bài 16. (Hàng đợi hai đầu - double ended queue : deque) Các phép toán thêm và lấy ra trên hàng đợi được hạn chế sao cho lấy ra ở một đầu và thêm vào ở đầu còn lại. Tuy nhiên trong thực tế trong một số trường hợp ta dùng những hàng đợi mà thao tác thêm vào và lấy ra được thực hiện ở cả hai đầu. Những hàng đợi như thế được gọi là hàng đợi hai đầu. Một trong những ứng dụng của hàng đợi hai đầu là hàng đợi cho bộ đệm bàn phím vì khi đó ta có thể dùng phím xóa để xóa một số phần tử cuối của hàng đợi. Hãy tổ chức dữ liệu kiểu danh sách liên kết và cài đặt các thao tác trên hàng đợi hai đầu. Bài 17. (Hàng đợi hai đầu bằng mảng vòng). Tương tự cách cài đặt hàng đợi bằng mảng vòng, hãy xây dựng cách cài đặt deque. Viết các khai báo và các chương trình con thích hợp cho các thao tác cơ bản (tạo một deque rỗng, kiểm tra deque có rỗng hay không, thêm vào đầu, thêm vào cuối, lấy ra phần tử đầu, lấy ra phần tử cuối). Bài 18. (Hai ngăn xếp) Trong trường hợp cần dùng hai ngăn xếp cùng kiểu, thay vì dùng hai mảng ta có thể dùng một mảng duy nhất để lưu các phần tử của hai ngăn xếp. Hãy tổ chức dữ liệu, viết các khai báo thích hợp cho cách cài đặt này và viết các thủ tục, hàm thực hiện các thao tác trên hai ngăn xếp sao cho thuận lợi nhất. 54
55. Hướng dẫn: Tổ chức dữ liệu như hình sau: 1 Top1 Top2 Max Stack1 Stack2 Bài 19. Xét mạng lưới đường sắt dưới đây: 1 2 n Các toa tàu ở đường ray bên phải (được đánnh số 1, 2, , n) cần phải hoán vị và chuyển sang đường ray bên trái. Như sơ đồ đã chỉ ra, một toa có thể chuyển thẳng sang đường ray bên trái, hay nó có thể rẽ qua đường ray bên cạnh để sau này đặt nó ở đường ray bên trái. Đường ray rẽ ngang bên cạnh đóng vai trò như một ngăn xếp, phép toán đẩy (push) chuyển một toa tàu từ đường ray bên phải sang bên cạnh, và phép toán lấy ra (pop) chuyển toa ở "đỉnh" của đường ray bên cạnh sang đường ray bên trái. Với giả thiết đường ray rẽ ngang đủ chỗ để chứa các toa tàu. a) Với n = 3, tìm tất cả những hoán vị có thể có của các toa nhận được (ở đường ray bên trái) bằng một loạt các phép toán nói trên. Những hoán vị nào là không thể được? b) Một cách tổng quát, những hoán vị nào của dãy 1, 2, , n có thể nhận được khi ngăn xếp được dùng theo cách này? Bài 20. Yêu cầu tương tự như bài trên nhưng mạng lưới đường sắt được tổ chức như hình sau. 1 2 n Trong đó đường ray bên cạnh được tổ chức như hàng đợi. Bài 21. (Hàng đợi ưu tiên - priority queue) Hàng đợi ưu tiên là một hàng đợi mà mỗi phần tử được gắn với một độ ưu tiên. Hàng đợi được tổ chức sao cho những phần tử có độ ưu tiên cao nhất trong hàng đợi bao giờ cũng được lấy ra trước. Với những phần tử mà độ ưu tiên bằng nhau thì thực hiện theo nguyên tắc vào trước ra trước. Hãy tổ chức dữ liệu và cài đặt các thao tác cho hàng đợi ưu tiên. 55
56. Bài 22. Nếu độ ưu tiên của các phần tử trong một hàng đợi ưu tiên là những số nguyên trong đoạn 1 p, ta có thể dùng p mảng khác nhau để cài đặt một hàng đợi ưu tiên, mỗi mảng cho một hàng chứa các phần tử cùng độ ưu tiên. Hãy viết các khai báo và các thủ tục thực hiện các phép toán cơ bản với cách xây dựng hàng đợi ưu tiên như trên. Bài 23. Nếu độ ưu tiên của các phần tử trong hàng đợi ưu tiên có phân bố không đều, một cách khác để tổ chức dữ liệu cho hàng đợi ưu tiên là dùng một mảng duy nhất và dùng p+1 con trỏ, một phần tử ở đầu hàng đợi ưu tiên và một cho phần tử cuối mỗi hàng đợi cùng độ ưu tiên. Hãy tổ chức dữ liệu và viết các thủ tục cần thiết cho cách tổ chức này. 56
57. Chương 3 CÂY Cây là một cấu trúc phân cấp trên một tập các đối tượng. Mô hình cây thường được dùng trong thực tế cũng như tin học chẳng hạn như cây gia phả, mục lục của một cuốn sách, cây thư mục, cây phân tích cú pháp, 7. CÁC KHÁI NIỆM VỀ CÂY 7.1. Khái niệm cây Cây là một tập hữu hạn các phần tử gọi là các nút (node) với một thứ tự phân cấp giữa các phần tử, còn gọi là quan hệ cha-con. Trong cây có một nút đặc biệt ở cấp cao nhất gọi là nút gốc (root), các nút còn lại, mỗi nút là con của một nút nào đó của cây. Có nhiều cách định nghĩa cây, trong chương này định nghĩa cây bằng đệ quy như sau: - Tập hợp gồm một phần tử là một cây và phần tử này chính là nút gốc của cây. - Nếu r là một nút và T1, T2, , Tk là các cây với các nút gốc tương ứng là r1, r2, , rk. Khi đó nếu có quan hệ cha-con của nút r đối với các nút r1, r2, , rk thì tập hợp gồm nút r và tất cả các nút của những cây T1, T2, , Tk tạo thành một cây T có nút gốc là r và T1, T2, , Tk là các cây con của cây T, các nút r1, r2, , rk gọi là các nút con của nút r. T r T T Tk 1 r1 2 r2 rk Hình 3.1 Hình ảnh cây T với các cây con T1, T2, , Tk Trường hợp đặc biệt, một cây không có nút nào được gọi là cây rỗng (null tree). Trong thực tế ta thường gặp những đối tượng có cách tổ chức theo mô hình cây như mục lục một cuốn sách, cây gia phả trong một dòng họ, phân cấp tổ chức trong một cơ quan, đoàn thể, Trong tin học, mô hình phân cấp của cây là một trong những mô hình có nhiều ứng dụng. Chẳng hạn cách tổ chức lưu trữ dữ liệu trên đĩa được tổ chức bằng cây thư mục, mô hình cây dùng để biểu diễn không gian lời giải của các bài 57
58. toán như trong các bài toán trò chơi. Cây còn dùng trong các bước phân tích cú pháp của các văn phạm như các biểu thức, các câu lệnh trong một chương trình. Cây có thể dùng để tổ chức dữ liệu ở bộ nhớ trong và bộ nhớ ngoài thuận tiện cho các bài toán tìm kiếm như từ điển, kiểm tra từ trong một văn bản, Để biểu diễn cây trên thực tế có nhiều cách, tuy nhiên cách thường dùng nhất là biểu diễn cây bằng đồ thị. Mỗi phần tử (nút) được biểu diễn bằng một đỉnh, quan hệ "cha-con" giữa hai nút được biểu diễn bằng một cạnh nối giữa chúng. A B C D E F G H I J K Hình 3.2 Hình ảnh một cây biểu diễn bằng đồ thị 7.2. Một số khái niệm khác Bậc của nút: là số nút con của nút đó. Chẳng hạn với cây trên, bậc của nút A là 3, bậc của nút B là 0, bậc của nút C là 2. Bậc của cây: là bậc của nút có bậc lớn nhất trong các nút của cây. Cây có bậc n thì còn gọi là cây n-phân. Trong thực tế ta thường dùng các cấu trúc cây nhị phân (cây bậc 2), cây tam phân. Ví dụ cây ở hình trên có cấp 3. Nút lá (leaf node) : là nút có bậc bằng 0 (không có nút con). Trong cây ở hình trên có các nút lá là B, E, F, I, J, K, H. Nút trung gian (interior node): là nút của cây không phải nút gốc và nút lá. Mức (level) của nút: được định nghĩa đệ quy như sau: + Mức của nút gốc bằng 1. + Mức của nút khác nút gốc bằng mức của nút cha của nó cộng 1. Chiều cao của cây: là mức lớn nhất trong các nút của cây. Chiều dài đường đi (path length): Chiều dài đường đi của một nút là số các nút cần đi qua từ nút gốc đến nút đó. Chiều dài đường đi của một nút là mức của nút đó. Chiều dài đường đi của một cây: là tổng các độ dài đường đi của tất cả các đỉnh của nó. Chiều dài đường đi của cây còn gọi là đường đi trong của cây. Ví dụ độ dài đường đi của cây ở hình trên là 31. 58
59. 1 h Độ dài đường đi trung bình của cây: PI =  ni i , trong đó ni là số các nút n i 1 ở mức thứ i, n là tổng số các nút của cây, h là chiều của cây. Độ dài đường đi ngoài của cây: Giả sử mọi nút của cây đều có cùng bậc và là bậc của cây (nếu không ta mở rộng cây bằng cách thêm những nút đặc biệt vào vị trí của những cây con rỗng trong cây). Độ dài đường đi ngoài của cây là tổng độ dài đường đi của tất cả các nút đặc biệt. Nếu số nút đặc biệt ở mức i là mi thì độ 1 h dài đường đi ngoài trung bình của cây là PE =  mi i . Ví dụ độ dài đường đi m i 1 ngoài của cây ở hình trên là 96. Cây có thứ tự (ordered tree): là cây có xác định vị trí của các nút. Với cây có thứ tự thì hai cây sau là khác nhau: A A B E B E C D D C Hình 3.3 Cây có thứ tự 8. CÂY NHỊ PHÂN 8.1. Khái niệm Cây nhị phân là một cây mà tại mỗi nút của cây có không quá hai cây con. Cây nhị phân là một cấu trúc cây thường dùng trong tin học, chẳng hạn cây biểu diễn biểu thức (a + b/c)*(d-e*f) như sau: * + - a / d * b c e f Hình 3.4 Biểu diễn cây của biểu thức (a + b/c)*(d-e*f) Cây nhị phân đầy đủ là cây nhị phân mà các nút lá trên cây nằm nhiều nhất ở hai mức liên tiếp nhau, và các lá ở mức dưới nằm dồn về phía bên trái. 59
60. a) Cây nhị phân đầy đủ b) Cây nhị phân không đầy đủ Hình 3.5 Cây suy biến là cây nhị phân mà tại các nút của cây, các cây con trái hoặc cây con phải đều rỗng. Cây suy biến còn gọi là cây lệch phải (hoặc lệch trái). a) Cây lệch trái b) Cây lệch phải Hình 3.6. Cây nhị suy biến Cây suy biến không thuận lợi cho các thao tác trên cây vì các thao tác tương tự như trên danh sách tuần tự. 8.2. Biểu diễn cây nhị phân Tương tự như mô hình danh sách, với mô hình cây nhị phân ta thường dùng hai cách biểu diễn thông dụng là mảng và liên kết. 8.2.1. Biểu diễn cây nhị phân bằng mảng Để biểu diễn cây nhị phân bằng mảng, các phần tử của cây (các nút) được lưu vào các ô nhớ của mảng. Tuy nhiên để lưu được cấu trúc phân cấp ta phải có những tổ chức khác. Ta có hai cách dùng mảng cho cây nhị phân đầy đủ và cây nhị phân bất kỳ như sau: Cây nhị phân đầy đủ Với cây nhị phân đầy đủ ta có thể biểu diễn cây bằng cách đánh số các nút theo thứ tự từ trên xuống dưới và từ trái sang phải. Các nút của cây được lưu trong các ô nhớ của mảng tương ứng với chỉ số đã được qui định. 60
61. 1 A 2 3 B E 4 5 6 7 C D F G A B E C D F G Hình 3.7 Biểu diễn cây nhị phân đầy đủ bằng mảng Tổ chức cây nhị phân đầy đủ bằng mảng như trên thuận lợi cho các thao tác tìm các nút con của một nút và nút cha của một nút. Cụ thể, với phần tử thứ i trong mảng thì nút con bên trái của nó ở vị trí 2*i và nút con bên phải ở vị trí 2*i +1, nút cha của nó ở vị trí i div 2 (với i>1). Tuy nhiên cách tổ chức này không tốt trong trường hợp cây không đầy đủ vì khi đó nhiều ô nhớ trong mảng không sử dụng. Cây nhị phân bất kỳ Với cây nhị phân bất kỳ ta có thể lưu trong một mảng các bản ghi, mỗi bản ghi lưu một nút và thông tin về nút con của nó, gồm 3 thành phần: Data lưu dữ liệu của nút, Left, Right lưu vị trí của nút con bên trái, nút con bên phải của nó. Khai báo: const maxlength = ; {kích thước tối đa của mảng} Type Node = Record Data : ElementType; left, right : 0 maxlength; End; BtreeArr = Array[1 maxlength] of Node; Ví dụ: Cho cây như hình vẽ 1 A 2 B 3 C 4 5 6 D E F 7 8 9 G H I Hình 3.8 Biểu diễn cây nhị phân bất kỳ bằng mảng 61
62. Mảng biểu diễn cây trên có dạng Data Left Right 1 A 2 3 2 B 0 4 3 C 5 6 4 D 0 7 5 E 8 9 6 F 0 0 7 G 0 0 8 H 0 0 9 I 0 0 maxlength Với cách tổ chức cây nhị phân như trên đáp ứng được các yêu cầu về biểu diễn dữ liệu và phân cấp của cây nhị phân. Tuy nhiên cách biểu diễn này không thuận lợi cho các thao tác thêm, xóa các phần tử trong cây vì ta phải tìm các ô nhớ của mảng còn trống khi thêm và đánh dấu các ô nhớ trống khi xóa. Trong chương này chúng ta sử dụng cách biểu diễn cây nhị phân bằng liên kết và cấp phát động được trình bày trong phần sau. 8.2.2. Biểu diễn cây nhị phân bằng liên kết Biểu diễn cây nhị phân bằng liên kết được dựa trên cơ chế cấp phát động, trong đó mỗi nút gồm ba thành phần: + Thành phần Data dùng để lưu dữ liệu của phần tử của nút. + Thành phần Left là con trỏ quản lý nút gốc của cây con bên trái. + Thành phần Right là con trỏ quản lý nút gốc của cây con bên phải. Khai báo: Type BtreeLink = ^Node; Node = Record Data:ElementType; Left,Right:BtreeLink; End; Var Root : BtreeLink; 62
63. Root A C B D E F G H I J K Hình 3.9 Biểu diễn cây nhị phân bằng liên kết Để quản lý một cây ta chỉ cần quản lý nút gốc của cây. 8.3. Duyệt cây nhị phân Duyệt cây là thăm qua tất cả các đỉnh của cây, mỗi đỉnh đúng một lần. Thao tác duyệt cây là một trong những thao tác quan trọng của cây nói chung và cây nhị phân nói riêng. Phụ thuộc vào thứ tự duyệt nút gốc của cây, các thuật toán duyệt cây thường dùng gồm: + Duyệt theo thứ tự trước (PreOrder). + Duyệt theo thứ tự giữa (InOrder). + Duyệt theo thứ tự sau (PostOrder). 8.3.1. Duyệt cây nhị phân theo thứ tự trước Thuật toán đệ qui: Nếu cây không rỗng thì thực hiện: + Thăm nút gốc. + Duyệt theo thứ tự trước cây con trái. + Duyệt theo thứ tự trước cây con phải. Ví dụ với cây nhị phân cho trong hình 3.9. khi duyệt theo thứ tự trước sẽ lần lượt thăm qua các đỉnh : ABDHEIJCFGK. Thủ tục đệ quy duyệt cây nhị phân theo thứ tự trước như sau: Procedure TraversePreOrder(root:BtreeLink); 63
64. Begin If root nil)do begin Visit(p); if (p^.right<>nil) then Push(S,p^.right); p:=p^.left; if (p=nil) and not empty(S) then Pop(s,p) end; End; 8.3.2. Duyệt cây nhị phân theo thứ tự giữa Thuật toán (Đệ qui): Nếu cây không rỗng thì thực hiện: + Duyệt theo thứ tự giữa cây con trái. 64
65. + Thăm nút gốc. + Duyệt theo thứ tự giữa cây con phải. Ví dụ với cây nhị phân cho trong hình 3.9 khi duyệt theo thứ tự giữa sẽ lần lượt thăm qua các nút: DHBIEJAFCKG. Thủ tục đệ quy duyệt cây nhị phân theo thứ tự giữa như sau: Procedure TraverseInOrder(root:BtreeLink); Begin If root nil do begin 65
66. Push(S,p); p:=p^.left; end; if not empty(S) then begin Pop(S,p); Visit(p); p:=p^.right; end; Until Empty(S) and (p=nil); End; 8.3.3. Duyệt cây nhị phân theo thứ tự sau Thuật toán đệ qui: Nếu cây không rỗng thì thực hiện: + Duyệt theo thứ tự sau cây con trái. + Duyệt theo thứ tự sau cây con phải. + Thăm nút gốc. Ví dụ với cây nhị phân cho trong hình 3.9 khi duyệt theo thứ tự sau sẽ lần lượt thăm qua các nút: HDIJEBFKGCA. Thủ tục đệ quy duyệt cây nhị phân theo thứ tự sau như sau: Procedure TraversePostOrder(root:BtreeLink); Begin If root<>nil then Begin TraversePosOrder(Root^.left); TraversePosOrder(Root^.right); Visit(root); End; End; Thuật toán không đệ quy: Tương tự như hai thao tác duyệt trên, với thuật toán duyệt cây nhị phân theo thứ tự sau ta cũng có thể khử đệ quy bằng cách dùng một ngăn xếp S. Do cây con phải được duyệt trước nút gốc nên mỗi bước, trước khi duyệt theo nhánh trái ta lưu nút gốc và con phải (nếu có) vào vào ngăn xếp (nút con phải lưu sau để lấy ra trước). Khi lấy từ ngăn xếp ra để duyệt tiếp ta phải phân biệt nút lấy ra là nút gốc hay nút con phải. Nếu là nút gốc thì thăm còn nếu là nút phải thì tiếp tục duyệt theo nhánh trái. Do đó mỗi phần tử của ngăn xếp gồm hai phần: thành phần dùng để chứa nút và một thành phần để phân biệt nút đưa vào là nút gốc hay nút con phải (thành phần này kiểu Boolean). Chi tiết thuật toán như sau: Xuất phát từ nút gốc của cây. Khởi tạo ngăn xếp rỗng. 66
67. isRoot:=false Lặp Lặp khi cây còn khác rỗng và không phải gốc (not isRoot) + Đưa gốc vào ngăn xếp. + Nếu nút con phải khác rỗng thì đưa vào ngăn xếp + Chuyển sang gốc cây con trái. Nếu gốc khác rỗng thì thăm nút gốc. Nếu ngăn xếp không rỗng thì + Lấy cây con và giá trị isRoot từ ngăn xếp. Đến khi ngăn xếp rỗng và cây rỗng thì dừng Thủ tục duyệt cây theo thứ tự trước không đệ quy như sau: Procedure TraversePostOrder(root:BtreeLink); Var S : StackOfNodes; p:BtreeLink; isRoot:Boolean; Begin p:=Root; Init(S); isRoot:=false; Repeat While (p nil then Push(S,p^.right,false); p:=p^.left; end; if p<>nil then Visit(p); if not empty(S) then Pop(s,p,isRoot); Until Empty(S); End; 8.4. Cây tìm kiếm nhị phân Cây tìm kiếm nhị phân là một dạng cây nhị phân được tổ chức theo một trật tự nào đó của các nút để thuận lợi cho việc tìm kiếm. Trong phần này ta giả sử dữ liệu tại một nút của cây có thành phần Key là khóa của các phần tử. Giả sử trên cây các nút không có hai phần tử trùng khóa. Khái niệm cây tìm kiếm nhị phân (Binary Search Tree - BST) được định nghĩa như sau: Cây tìm kiếm nhị phân là một cây nhị phân mà tại mỗi cây con của nó thỏa điều kiện: khoá của nút gốc lớn hơn khoá của tất cả các nút của cây con trái và nhỏ hơn khoá của tất cả các nút của cây con phải. Ví dụ: Cho cây tìm kiếm nhị phân như hình sau 67
68. 15 9 25 7 1 2 3 2 0 0 1 1 2 3 0 4 7 7 Hình 3.10 Cây tìm kiếm nhị phân 8.5. Các thao tác trên cây tìm kiếm nhị phân Ngoài thao tác như trên cây nhị phân, trên cây tìm kiếm nhị phân thường thực hiện các thao tác sau: + Tìm một nút trên cây theo khóa. + Thêm một nút vào cây. + Xóa một nút trên cây. 8.5.1. Tìm một nút trên cây tìm kiếm nhị phân Cho trước một cây tìm kiếm nhị phân có nút gốc là root. Ta cần tìm một nút có khoá là x trong cây. Thuật toán đệ quy: Nếu khóa của nút gốc bằng khóa x thì thuật toán dừng, kết quả là tìm thấy. Nếu khóa của nút gốc lớn hơn khóa x thì tìm khóa x ở cây con trái. Nếu khóa của nút gốc nhỏ hơn khóa x thì tìm khóa x ở cây con phải. Nếu cây rỗng thì thuật toán dừng, kết quả là không tìm thấy. Thủ tục đệ quy tìm khóa x trong cây tìm kiếm nhị phân có nút gốc là root, kết quả tìm được hay không trả về qua tham biến found và p là nút tìm được (nếu tìm thấy). Procedure Search(x:KeyType; root:Btree; var found:boolean;var p:Btree); Begin p:=root; if p x then Search(x,p^.left,found,p) else Search(x,p^.right,found,p) 68
69. else found:=false; End; Thủ tục không đệ quy tìm một khóa trong cây tìm kiếm nhị phân: Procedure Search(x:KeyType; root:Btree; var found:boolean; var p:Btree); Begin p:=root; Found:=false; While (not found) and (p<>nil) do If p^.key=x then found:=true else If p^.key<x then p:=p^.right else P:=p^.left; End; 8.5.2. Thêm một nút vào cây tìm kiếm nhị phân Cho một cây tìm kiếm nhị phân có nút gốc là root, thêm vào cây một nút có dữ liệu là x sao cho sau khi thêm cũng là cây tìm kiếm nhị phân. Thuật toán đệ quy: Nếu cây rỗng thì x là nút gốc của cây, thuật toán dừng. Nếu khóa của nút gốc bằng khóa của x thì thuật toán dừng (nút đã có). Nếu khóa của nút gốc lớn hơn khóa của x thì thêm x vào cây con trái. Nếu khóa của nút gốc nhỏ hơn khóa của x thì thêm x vào cây con phải. Ví dụ: Cây ở hình 3.19 sau khi thêm nút 11 15 9 25 7 1 2 3 2 0 0 1 1 2 3 0 4 7 7 1 1 Hình 3.11 Thêm vào cây tìm kiếm nhị phân Thủ tục đệ quy thêm nút x vào cây tìm kiếm nhị phân: 69
70. Procedure Insert(x:ElementType; var root:BtreeLink); Var p:BTreeLink; Begin if root=nil then begin New(root); root^.Data:=x; root^.left:=nil; root^.right:=nil; end else if root^.Data.Key>x.Key then Insert(x, root^.left) else if root^.Data.Key nil do begin if q^.Data.key > x then if q^.left nil then q:=q^.right else begin q^.right:=p; q:=nil; end 70
71. else begin q:=nil; dispose(p); end; end; End; 8.5.3. Xóa một nút trên cây tìm kiếm nhị phân Cho một cây tìm kiếm nhị phân có nút gốc là root, xóa nút có khóa là x trên cây sao cho sau khi xóa cây vẫn còn thỏa các tính chất của cây tìm kiếm nhị phân. Để xóa, trước tiên ta phải tìm nút có khóa x cần xóa (dùng thuật toán tìm kiếm trên cây) và ta chỉ thực hiện thao tác xóa nếu tìm được. Giả sử p là nút có khóa x cần xóa. Để xóa nút p, ta xét ba trường hợp: + p là nút lá của cây. + p có một cây con trái hoặc phải. + p có cả hai cây con trái và phải. Trường hợp 1. Nếu p là nút lá và giả sử parent là nút cha của p. Trong trường hợp này ta chỉ cần đặt con trỏ trái hoặc phải của parent đến nil tùy thuộc vào p là nút con trái hay phải của parent. Sau đó giải phóng ô nhớ nút p. Nếu nút cần xóa là nút gốc thì đây là nút duy nhất của cây nên sau khi xóa cây sẽ rỗng. Hình sau cho ta thấy hình ảnh cây sau khi xóa nút có khóa là 7. 15 parent 9 25 p 7 nil 12 20 30 17 27 37 16 14 Hình 3.12 Xóa nút lá trong cây Trường hợp 2. Khi p có đúngmột nút con, giả sử parent là nút cha của p và subtree là nút con khác nil của p. Trong trường hợp này ta chỉ cần đặt con trỏ trái hoặc phải của nút parent vào nút con của p là subtree tùy thuộc vào p là nút con trái 15 parent 9 25 p 7 12 20 30 subtree 17 27 37 71 16 14
72. hay con phải của parent. Sau đó giải phóng ô nhớ của nút p. Trong hình sau, để xóa nút 20 ta liên kết bên trái của nút 25 đến nút 17. Hình 3.13 Xóa nút có một nút con Trong trường hợp nút p là gốc của cây, khi đó chỉ cần chuyển gốc của cây về nút con khác nil của nút p sau đó giải phóng p. Ta có thể kết hợp hai truờng hợp 1 và 2 thành một trường hợp trong đó nút p có không quá một cây con khác rỗng bởi đoạn lệnh sau: subtree:=p^.Left; if subtree= nil then subtree:=p^.Right; if parent=nil then {xóa nút gốc} Root:=subtree else if parent^.Left=p then parent^.Left:=subtree else parent^.Right:=subtree; Trường hợp 3. Nếu nút cần xóa p có cả hai cây con trái và phải. Để xóa nút p trong trường hợp này ta đưa về một trong hai dạng trên bằng cách tìm nút có khóa lớn nhất của các nút trong cây con trái của nút p (hoặc nút có khóa nhỏ nhất của các nút trong cây con phải) giả sử nút này là q. Dễ thấy nút q có không quá một cây con vì nó là nút tận cùng bên phải của cây con bên trái p (hoặc là nút tận cùng bên trái của cây con bên phải p). Để xóa nút p ta thay bằng chuyển dữ liệu của nút q lên nút p rồi xóa nút q như trong trường hợp 1 hoặc 2. Hình dưới minh họa thao tác xóa nút có hai cây con. parent P 15 p 9 25 parent 7 1 2 3 q 2 0 0 1 2 3 7 q 7 7 1 subtre 1 6 eq 4 Hình 3.14 Xóa nút có hai cây con Thủ tục dưới đây cài đặt thao tác xóa nút có khóa x trong cây tìm kiếm nhị phân có nút gốc là Root cho tất cả các trường hợp. 72
73. Procedure Delete(var root : BTreeLink; x : KeyType);var p,q,parent,subtree : BT;Begin (* Tim nut can xoa p, parent la nut cha cua p *) p :=r; parent:=nil; while (p x) do begin parent:=p; if p^.Data.Key x then p := p^.left; end; if p=nil then writeln('Khong co phan tu can xoa') else begin (* Truong hop nut can xoa co 2 nut con : - Tim nut q la nut trai nhat cua cay con ben phai. - parent la nut cha cua nut q. *) if (p^.left nil) then begin q:=p^.right; parent:=p; while q^.left p^.Data.Key then parent^.left := subtree else parent^.right := subtree; end; dispose(p); end; End; Có thể dùng thủ tục đệ quy như sau: Procedure Delete(var root : BTreeLink; x : KeyType); Begin if Root<>nil then 73
74. if x Root^.Data.Key then Delete(Root^.right,x) else Del(Root); End; Thủ tục Del xóa nút p trong cây. Procedure Del(var P : BtreeLink); var q, q1 : BtreeLink; Begin if p^.right=nil then begin q:=p; p:=p^.left; end else if p^.left=nil then begin q:=p; p:=p^.right; end else begin q:=p^.left; if q^.right=nil then begin p^.Data:=q^.Data; p^.left:=q^.left; end else begin repeat q1:=q; q:=q^.right; until q^.right=nil; p^.Data:=q^.data; q1^.right:=q^.left; end; end; Dispose(q); End; 9. CÂY CÂN BẰNG Với các thao tác trên cây tìm kiếm nhị phân đã tìm hiểu ở phần trước ta dễ thấy các thao tác thường dùng trên cây là tìm, thêm và xóa phụ thuộc nhiều vào "hình dáng" của cây. Trong trường hợp cây suy biến thì các thao tác có độ phức 74
75. tạp tương đương trên danh sách tuần tự. Trong nhiều trường hợp, các thao tác thêm vào và xóa có thể làm cây "lệch" đi, độ cao của cây tăng lên trong khi số các nút không nhiều. Điều này làm ảnh hưởng rất lớn đến các thao tác trên cây tìm kiếm nhị phân. Một nhu cầu hiển nhiên là các thao tác trên cây tìm kiếm nhị phân phải được cài đặt như thế nào để hạn chế trường hợp cây "lệch" hay phải điều chỉnh để cây "cân bằng". Lớp các cây này được hai nhà toán học người Nga là G.M. Adelsen-Velskii và E.M. Landis đưa ra vào năm 1962. 9.1. Khái niệm Cây cân bằng hoàn toàn: Một cây tìm kiếm nhị phân được gọi là cây cân bằng hoàn toàn nếu và chỉ nếu với mọi nút của cây số nút của cây con bên trái và số nút của cây con bên phải lệch nhau không quá 1. Hình dưới đây minh họa cây cân bằng hoàn toàn và cây không cân bằng hoàn toàn. 15 15 9 25 9 25 7 12 20 30 7 12 20 30 10 27 37 10 Hình 3.15 a) Cây cân bằng hoàn toàn Hình 3.15 b) Cây không cân bằng hoàn toàn Một cây cân bằng hoàn toàn thì các thao tác tìm kiếm, thêm và xóa được thực hiện rất thuận lợi. Tuy nhiên thuật toán để duy trì cây cân bằng hoàn toàn đối với thao tác thêm và xóa là rất phức tạp. Một dạng cây khác được các tác giả trên đưa ra là cây cân bằng được định nghĩa như sau. Một cây tìm kiếm nhị phân được gọi là cây cân bằng nếu và chỉ nếu với mọi nút của cây chiều cao cây con trái và chiều cao cây con phải lệch nhau không quá 1. Nếu tại một nút bất kỳ của cây, ta gọi: hL, hR tương ứng là chiều cao cây con trái và cây con phải thì điều kiện để cây cân bằng là hL=hR-1 hoặc hL=hR hoặc hL=hR+1. Những cây thỏa điều kiện này còn được gọi là cây AVL. Từ điều kiện trên ta thấy nếu cây cân bằng hoàn toàn thì nó là cây cân bằng. Tuy nhiên, điều ngược lại không đúng. Chẳng hạn cây ở hình 3.15 b) là cây cân bằng nhưng không cân bằng hoàn toàn. Cây cân bằng cũng là một cách tổ chức tốt cho cây tìm kiếm nhị phân. Trong đa số các trường hợp tính toán trung bình, các thao tác trên cây cân bằng và cây cân bằng hoàn toàn không chênh lệch nhau nhiều tuy nhiên các thuật toán trên cây cần bằng thì đơn giản hơn nhiều. Do đó được đa số người lập trình sử dụng 75
76. như một cách tổ chức tốt cho cây tìm kiếm nhị phân. Trong phần sau sẽ đề cập đến hai thuật toán thường dùng trên cây cân bằng là thêm một nút và xóa một nút. Để đơn giản trong các thao tác kiểm tra và cân bằng cây, tại mỗi nút của cây ta lưu hệ số cân bằng (bal) là hiệu của chiều cao cây con phải và cây con trái (bal=hR-hL). Vì cây luôn được cân bằng lại sau mỗi thao tác nên hệ số cân bằng của mỗi nút là -1, 0 hoặc 1. Khai báo kiểu dữ liệu cho cây cân bằng tương tự cây tìm kiếm nhị phân. Type BalanceTree = ^Node; Node = Record Data:ElementType; Bal : -1 1; Left,Right:BalenceTree; End; Var Root : BalanceTree; 9.2. Thêm vào cây cân bằng Một trong những khả năng làm cho cây tìm kiếm nhị phân mất tình trạng cân bằng là khi thêm vào một nút. Trong phần này ta sẽ xem xét các khả năng có thể xảy ra khi thêm một nút vào cây cân bằng. Trong một số trường hợp, khi thêm không làm mất tính cân bằng của cây nhưng làm thay đổi hệ số cân bằng của một số nút liên quan. Có những trường hợp khi thêm vào làm cho cây không cân bằng ở một số cây con. Khi đó ta phải cân bằng lại cây theo nguyên tắc từ cây con không cân bằng nhỏ nhất. Mỗi khi cân bằng phải tính toán lại các hệ số cân bằng của các nút liên quan. Sau đây chúng ta xem xét chi tiết các trường hợp. Giả sử nút thêm vào ở cây có nút gốc là p. Có thể xảy ra những trường hợp sau: Trường hợp 1. p=nil (thêm vào cây trống). Khi thêm vào một đỉnh thì cây ở tình trạng cân bằng và hệ số cân bằng tại nút này là 0. Trường hợp 2. p nil và tại p hệ số cân bằng là 0 (p^.bal=0). Trong trường hợp này, khi thêm nút mới vào cây gốc p không làm mất tính cân bằng của cây tại nút p (các cây con có thể không còn cân bằng). Trường hợp 3. p nil và tại p có p^.bal=1 (hoặc p^.bal=-1). Trong trường hợp này, nếu khi thêm nút mới vào cây gốc p không làm tăng độ cao cây con phải (hoặc cây con trái) thì tại nút p tính cân bằng vẫn không ảnh hưởng. Trường hợp 4. p nil và tại p có p^.bal=1 (hoặc p^.bal=-1). Giả sử nút mới thêm vào cây con phải (hoặc trái) của p và làm tăng chiều cao cây con. Trong trường hợp này thì tại nút p tính cân bằng bị phá vỡ. 76