Giáo trình Phân tích thiết kế hệ thống (Phần 2) - Nghề: Lập trình máy tính - Trình độ: Lành nghề

Nội dung text: Giáo trình Phân tích thiết kế hệ thống (Phần 2) - Nghề: Lập trình máy tính - Trình độ: Lành nghề

1. BỘ LAO ĐỘNG - THƯƠNG BINH VÀ XÃ HỘI TỔNG CỤC DẠY NGHỀ DỰ ÁN GIÁO DỤC KỸ THUẬT VÀ DẠY NGHỀ (VTEP) GIÁO TRÌNH Môn học : PHÂN TÍCH THIẾT KẾ THUẬT TOÁN Mã số : ITPRG3_12 Nghề : LẬP TRÌNH MÁY TÍNH Trình độ (lành nghề) Đà Lạt - 2007
2. Phân tích thiết kế thuật toán Tuyên bố bản quyền : Tài liệu này thuộc loại sách giáo trình Cho nên các nguồn thông tin có thể được phép dùng nguyên bản hoặc trích dùng cho các mục đích về đào tạo và tham khảo . Mọi mục đích khác có ý đồ lệch lạc hoặc sử dụng với mục đích kinh doanh thiếu lành mạnh sẽ bị nghiêm cấm. Tổng Cục Dạy nghề sẽ làm mọi cách để bảo vệ bản quyền của mình. Tổng Cục Dạy Nghề cám ơn và hoan nghênh các thông tin giúp cho việc tu sửa và hoàn thiện tốt hơn tàI liệu này. Địa chỉ liên hệ: Dự án giáo dục kỹ thuật và nghề nghiệp Tiểu Ban Phát triển Chương trình Học liệu 2
3. Phân tích thiết kế thuật toán LỜI TỰA Đây là tài liệu được xây dựng theo chương trình của dự án giáo dục kỹ thuật và dạy nghề, để có đươc giáo trình này dự án đã tiến hành theo hai giai đoạn. Giai đoạn 1 : Xây dựng chương trình theo phương pháp DACUM, kết quả của gian đoạn này là bộ khung chương trình gồm 230 trang cấp độ 2 và 170 trang cấp độ 3. Giai đoạn 2 : 29 giáo trình và 29 tài liệu hướng dẫn giáo viên cho nghề lập trình máy tính 2 cấp độ. Để có được khung chương trình chúng tôi đã mời các giáo viên, các chuyên gia đang làm việc trong lĩnh vực công nghệ thông tin cùng xây dựng chương trình. Trong giai đoạn viết giáo trình chúng tôi cũng đã có những sự điều chỉnh để giáo trình có tính thiết thực và phù hợp hơn với sự phát triển của lĩnh vực công nghệ thông tin. Trong quá trình biên soạn, mặc dù đã cố gắng tham khảo nhiều tài liệu và giáo trình khác nhưng tác giả không khỏi tránh được những thiếu sót và hạn chế. Tác giả chân thành mong đợi những nhận xét, đánh giá và góp ý để cuốn giáo trình ngày một hoàn thiện hơn. Tài liệu này được thiết kế theo từng mô đun/ môn học thuộc hệ thống mô đun/môn học của một chương trình, để đào tạo hoàn chỉnh nghề Lập trình máy tính ở cấp trình độ lành nghề và được dùng làm Giáo trình cho học viên trong các khoá đào tạo, cũng có thể được sử dụng cho đào tạo ngắn hạn hoặc cho các công nhân kỹ thuật, các nhà quản lý và người sử dụng nhân lực tham khảo. Đây là tài liệu thử nghiệm sẽ được hoàn chỉnh để trở thành giáo trình chính thức trong hệ thống dạy nghề. Đà lạt ,Tháng 10 năm 2007 3
4. Phân tích thiết kế thuật toán MỤC LỤC TÊN BÀI TRANG 1. BàI1 :TỔNG QUAN VỀ PHÂN TÍCH THIẾT KẾ THUẬT TOÁN 5 2. Bài2 :CÁC KIỂU DỮ LIỆU TRỪU TƯỢNG 20 3. Bài3 :CÁC CẤU TRÚC DỮ LIỆU CƠ BẢN 51 4. Bài4 :PHƯƠNG PHÁP CHIA ĐỂ TRỊ 109 5. Bài5 :PHƯƠNG PHÁP THAM LAM 116 6. Bài6 :PHƯƠNG PHÁP QUAY LUI 124 7. Bài7 :QUY HOẠCH ĐỘNG 135 8. Bài7(tiếp theo) :NÉN DỮ LIỆU 145 9. Bài 8 :LỚP BÀI TOÁN NP ĐẦY ĐỦ 159 10.CÁC BÀI THỰC HÀNH 172 11. TÀI LIỆU THAM KHẢO 185 4
5. Phân tích thiết kế thuật toán BÀI 1 : TỔNG QUAN VỀ PHÂN TÍCH THIẾT KẾ THUẬT TOÁN Mã bài : ITPRG3_12.1 Giới thiệu Phân tích thiết kế thuật toán là một khâu quan trọng quyết định sự thành công của một chương trình máy tính. Nó giúp chúng ta lựa chọn, xây dựng và đánh giá các thuật toán trước khi viết mã chương trình. Chúng ta chỉ có thể có được một chương trình máy tính tốt nếu và chỉ nếu có một thuật toán tốt. Phân tích thiết kế thuật toán còn có một ý nghĩa vô cùng quan trọng trong trường hợp làm việc theo nhóm (cho phép chia sẻ công việc và đảm bảo sự thống nhất giữa các lập trình viên) và bảo trì, nâng cấp hệ thống chương trình sau này. Trong phần này chúng ta sẽ làm quen với các khái niệm cơ bản về phân tích thiết kế thuật toán, các phương pháp biểu diễn và đánh giá thời gian thực hiện thuật toán. Mục tiêu thực hiện Học xong bài này học viên sẽ có khả năng: Nắm được các khái niệm cơ bản và tầm quan trọng của việc phân tích và thiết kế thuật toán trong việc xây dựng chương trình máy tính. Sử dụng các phương pháp sử dụng sơ đồ khối và ngôn ngữ giả trong việc đặc tả dữ liệu và thuật toán trong thiết kế chương trình. Đánh giá độ phức tạp của thuật toán, so sánh độ phức tạp của thuật toán ứng với từng lời giải của bài toán. .1. Thuật toán (Algorithm) .1.1 Định nghĩa Thuật toán (hay còn gọi là giải thuật) là khái niệm cơ bản trong máy tính và lập trình máy tính. Có thể hiểu thuật toán là phương pháp giải một bài toán bằng cách chia nhỏ bài toán thành những thao tác đơn giản, dễ thực hiện và có trình tự hợp lý. Người ta đã đưa ra những định nghĩa về thuật toán như sau : 5
6. Phân tích thiết kế thuật toán "Thuật toán là tập hợp đặc trưng các trình tự logic và toán học đơn giản, được xác định rõ ràng để theo đó giải quyết một vấn đề với một số bước nhất định ". (L. Nyhof & S. Leestma) Một định nghĩa khác : "Thuật toán là một hệ thống chặt chẽ và rõ ràng với các qui 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 ta đạt được mục tiêu định trước". (B.W. Kernighan) .1.2 Các đặc trưng cần phải có của thuật toán Khi xây dựng một thuật toán máy tính phải đáp ứng các yêu cầu sau : Thuật toán phải kết thúc sau một số bước hữu hạn - tính kết thúc Mỗi thao tác thực hiện phải rõ ràng, cụ thể và duy nhất - tính xác định. Các thao tác phải khả thi (có thể thực hiện được) - tính hiệu quả. Có thể giải bất kỳ bài toán nào trong một lớp các bài toán - tính phổ dụng. Miền xác định của thuật toán: là tập hợp bộ dữ liệu mà thuật toán có thể sử dụng và cho ra kết quả - Đại lượng vào/ra. Lưu ý rằng việc giải quyết một bài toán có thể tồn tại nhiều thuật toán khác nhau. Mỗi thuật toán có thể có hiệu quả như nhau cho một lớp các bài toán. 6
7. Phân tích thiết kế thuật toán .1.3 Công cụ trình bày thuật toán Quá trình xử lý Chương trình con Bắt đầu / Kết thúc Điều kiện rẽ nhánh Nhập xuất dữ liệu Điều kiện lựa chọn Đĩa từ Các hướng xử lý Có hai công cụ phổ biến để trình bày thuật toán: bằng sơ đồ khối (Flowchart) và ngôn ngữ giả (pseudo language). Sơ đồ khối là sơ đồ biểu diễn các hình ký hiệu đặc trưng cho các thao tác cần thực hiện. Ngôn ngữ giả là ngôn ngữ tự nhiên kết hợp với một ngôn ngữ lập trình được chọn để viết chương trình. Đây là công cụ thường được sử dụng để trình bày thuật toán. Trong sơ đồ thuật toán, các hình được nối, liên kết với nhau bởi các mũi tên chỉ ra trình tự thực hiện các thao tác. Các khối cơ bản Các cấu trúc cơ bản Sơ đồ thuật toán 7 Cấu trúc tuần tự Cấu trúc điều kiện Cấu trúc vòng lặp
8. Phân tích thiết kế thuật toán Sơ đồ thuật toán của bất kỳ bài toán nào cũng có thể được xây dựng trên cơ sở các phần tử và các cấu trúc trên. Về cơ bản, các sơ đồ được tạo lập từ các khối sau: 1. Khối thao tác Là khối hình chữ nhật trong đó ghi các lệnh cần thực hiện a := a + b a:=5 i= i + 1 2. Khối điều kiện Là khối hình thoi hoặc elip bên trong ghi các điều kiện cần kiểm tra .T. .T. a=1 i < n b .F. .F. 3. Khối đầu thuật toán Begin 4. Khối cuối thuật toán End 5. Khối nối tiếp Khối thường có hình tròn ghi một giá trị nguyên bên trong, nhằm làm sơ đồ dễ đọc và sáng sủa. a := b i < n a := b 8 i < n 1 1
9. Phân tích thiết kế thuật toán Ta có thể biểu diễn như sau Ví dụ : Dùng sơ đồ khối để biểu diễn thuật toán giải bài toán tìm nghiệm của phương trình bậc 1 : ax + b = 0. Begin a, b Đ a 0 PT vô nghiệm S Vô số nghiệm End Ưu điểm của cách biểu diễn thuật toán bằng sơ đồ khối là rõ ràng, trực quan giúp người đọc dễ hình dung các bước lưu chuyển trong thuật toán. Tuy nhiên, với những bài toán lớn chứa rất nhều bước và phức tạp thì rất khó biểu diễn bằng phương pháp này. Ví dụ: Cho một ngã 5 như hình vẽ 9
10. Phân tích thiết kế thuật toán Giải: Chúng ta có thể mô hình hóa bài toán nói trên theo mô hình toán học đã biết đó là đồ thị (Graph). Ðồ thị là tập hợp các điểm gọi là các đỉnh của đồ thị và một tập hợp các cạnh nối một số các cặp đỉnh với nhau. Hai đỉnh có ít nhất một cạnh nối được gọi là hai đỉnh kề nhau. Tại ngả 5 này có 13 lối đi (AB, AC, AD, BA, BC, BD, DA, DB, DC, EA, EB, EC, ED). Ta sẽ biểu diễn mỗi lối đi là một đỉnh của đồ thị và hai lối đi không thể cùng đi đồng thời ta nối chúng bằng một cạnh. Tóm lại, ta có: Ðỉnh là các tuyến đường đi cho phép. Cạnh nối 2 đỉnh dùng để chỉ tuyến đường không thể lưu thông đồng thời. Ta có đồ thị hình 2 như sau : 10
11. Phân tích thiết kế thuật toán Bài toán của chúng ta rõ ràng là bài toán tô màu cho đồ thị hình 2. Bài toán tô màu cho đồ thị được phát biểu như sau: "Tô màu cho các đỉnh của đồ thị sao cho số màu được dùng là ít nhất và 2 đỉnh kề nhau (có cung nối) không được tô cùng 1 màu. Tuy nhiên, bài toán tô màu cho đồ thị không có thuật toán tốt. Nói cách khác, thuật toán của bài toán tô màu là : "Thử tất cả các khả năng". Thực tế cách giải này khó có thể áp dụng đưọc vì vậy ta cần suy nghĩ cách khác để giải quyết vấn đề. Nếu bài toán nhỏ ta có thể vét cạn các khả năng để tìm ra lời giải tối ưu. Một cách giải quyết dùng cho bài toán chúng ta là: "Cố gắng tô màu cho đồ thị bằng ít màu nhất" một cách nhanh chóng. Một cách giải quyết như vậy gọi là một Heuricstic. Một Heuricstic hợp lý cho bài toán tô màu đồ thị được gọi là thuật toán Greedy. Chọn 1 đỉnh chưa tô màu và tô màu cho nó. Với các đỉnh còn lại mà không có cạnh chung với đỉnh đang xét thì tô các đỉnh đó cùng 1 màu với đỉnh đang xét. Duyệt danh sách các đỉnh chưa tô màu, lấy 1 đỉnh trong số chúng và tô bằng màu mới rồi quay lại bước 1. Ðây là thuật toán hiển nhiên và luôn đạt kết quả tốt (mặc dù có thể không là lời giải tối ưu). Ví dụ : Xét đồ thị dưới đây và cách tô màu cho nó Hình :Xét đồ thị và cách tô màu Dùng Greedy: Tối ưu: +Xanh : 1, 2 + Xanh: 1, 3, 4 + Ðỏ : 3, 4 + Ðỏ : 2, 5 + Tím : 5 Áp dụng thuật toán Greedy cho bài toán của đồ thị hình 2, ta được kết quả: + Xanh : AB, AC, AD, BA, DC, ED + Ðỏ : BC, BD, EA + Tím : DA, DB 11
12. Phân tích thiết kế thuật toán + Vàng : EB, EC Nhận xét: Một đồ thị có k đỉnh mà mỗi cặp đỉnh bất kỳ đều được nối với nhau thì phải dùng k màu để tô. Một đồ thị trong đó có k đỉnh mà mỗi cặp đỉnh bất kỳ trong k đỉnh này đều được nối với nhau thì không thể dùng ít hơn k màu để tô cho đồ thị. Ðồ thị hình 2 có 4 đỉnh AC, DA, EB, BD mà mỗi cặp đỉnh bất kỳ trong số chúng đều được nối với nhau. Vậy đồ thị hình 2 không thể tô với ít hơn 4 màu. Ðiều này khẳng định lời giải trên là lời giải tối ưu. .2. Ngôn ngữ giả và tinh chế từng bước Một khi ta đã có mô hình thích hợp cho bài toán ta cần hình thức hóa một thuật toán trong thuật ngữ của mô hình đó. Mở đầu ta viết những mệnh đề tổng quát rồi tinh chế dần thành những mệnh đề cụ thể hơn và cứ tiếp tục như thế. Ðến cuối cùng ta được những chỉ thị thích hợp trong một ngôn ngữ lập trình. Ví dụ: Xét thuật toán Greedy áp dụng cho bài toán tô màu Giả sử đồ thị đang xét là G. Thuật toán Greedy xác định một tập hợp NewClr các đỉnh của G được tô cùng một màu. Thuật toán Greedy được lập cho đến khi tất cả các đỉnh của G đều được tô màu. Procedure Greedy (Var G : Graph ; Var NewClr : Set); Begin {1} NewClr : = 0 ; {2} For mỗi đỉnh của V chưa tô màu Do {3} If V không được nối với đỉnh nào trong NewClr Then Begin {4} Ðánh dấu V đã được tô màu ; {5} Thêm V vào tập NewClr ; End ; End ; Chú ý : Trong thuật toán bằng ngôn ngữ giả chúng ta đã dùng một số từ khóa của Pascal. Graph và Set là các kiểu dữ liệu trừu tượng, chúng sẽ được xác định bằng phép định nghĩa kiểu của Pascal. Câu lệnh If {3} có thể được tinh chế một bước nữa như sau: Procedure Greedy (Var G : Graph ; Var NewClr : Set); 12
13. Phân tích thiết kế thuật toán Begin {1} NewClr : = 0 ; {2} For mỗi đỉnh của V chưa tô màu Do Begin {3.1} Found : = False ; {3.2} For mỗi đỉnh của W trong NewClr Do {3.3} If có cạnh nối giữa V với W Then {3.4} Found : = True ; {3.5} If Found = False Then Begin {4} Ðánh dấu V đã được tô màu ; {5} Thêm V vào tập NewClr ; End; End; End ; Ta có thể coi Graph và Set như các tập hợp. Có nhiều cách để biểu diễn 1 tập hợp trong ngôn ngữ lập trình. Ðể đơn giản ta xem tập hợp như một danh sách (List) các số nguyên là chỉ số của các đỉnh và kết thúc bằng 1 giá trị đặc biệt Null. Thuật toán Greedy được tinh chế 1 bước nữa như sau: Procedure Greedy (Var G:Graph ; Var NewClr: Set); Var Found : Boolean ; V, W : Integer ; Begin NewClr : = 0 ; V : = Ðỉnh đầu tiên trong G ; While V Null Do Begin If có cạnh nối giữa V với W Then Found : = True ; W:=Ðỉnh kế tiếp trong NewClr ; End; If Found = False Then Begin Ðánh dấu V đã được tô màu ; Thêm V vào tập NewClr ; End; 13
14. Phân tích thiết kế thuật toán V : = Ðỉnh kế trong G ; End; End ; { Greedy} .3. Tóm tắt ba giai đoạn để giải một bài toán Mô hình toán học XD kiểu dữ liệu trừu Cấu trúc dữ liệu trừu G.thuật không hình thức tượng tượng C.trình bằng ngôn ngữ Chương trình thực thi giả Giai đoạn 1: Xây dựng mô hình toán thích hợp cho bài toán và tìm một thuật toán giải quyết bài toán trên mô hình đó. Giai đoạn 2: Thuật toán được trình bày bằng ngôn ngữ giả dựa trên các kiểu dữ liệu trừu tượng. Giai đoạn 3: Chọn một cách cài đặt một kiểu dữ liệu trừu tượng và thay ngôn ngữ giả bằng các mã lệnh của một ngôn ngữ lập trình. Kết quả là ta được một chương trình hoàn chỉnh có thể giải quyết được vấn đề đặt ra. .4. Các kiểu dữ liệu trừu tượng (Abstract Data Type) .4.1 Ðịnh nghĩa Khi xây dựng thuật toán hoặc lập trình, chúng ta thường phải làm việc trên các dữ liệu và trong mục này chúng ta xét một số khái niệm cơ bản về : các kiểu dữ liệu (Data Type), các cấu trúc dữ liệu (Data Structure) và các kiểu dữ liệu trừu tượng (Abstract Data Type - ATD). Trong một ngôn ngữ lập trình, kiểu dữ liệu của một biến là tập hợp các giá trị mà biến đó có thể nhận được. Mỗi một ngôn ngữ lập trình đều có một số kiểu dữ liệu cơ sở khác nhau. Một kiểu dữ liệu được thành lập bằng sự tập hợp các kiểu dữ liệu khác nhau gọi là kiểu dữ liệu hợp thành hay kiểu dữ liệu có cấu trúc hay cấu trúc dữ liệu. Một kiểu dữ liệu trừu tượng (ADT) là một mô hình toán học cùng với một tập hợp các phép toán tác động trên mô hình đó. Thông thường ta sẽ thiết kế thuật toán theo thuật ngữ của kiểu dữ liệu trừu tượng, nhưng để cài đặt được thuật toán trong một ngôn ngữ lập trình, ta phải tìm cách biểu diễn kiểu dữ liệu trừu tượng qua các kiểu dữ liệu của ngôn ngữ. 14
15. Phân tích thiết kế thuật toán .4.2 Ví dụ Kiểu Set có thể được biểu diễn qua danh sách (List) và được quản lý bằng mảng (Array) hay con trỏ (Pointer). Kiểu Graph là một danh sách các số nguyên và các phép toán tác động trên nó là: MakeNull (G): Tạo đồ thị rỗng. W= First (G): Hàm trả về phần tử đầu danh sách của G (= Null nếu G rỗng). W= Next (G): Hàm trả về phần tử kế tiếp trong G (= Null nếu là phần tử cuối). Insert (V ,G): Xen phần tử V vào đồ thị G. Ví dụ về kiểu mảng và bản ghi : A: Array [1 N] of Record Field1: ; Field2: ; FieldN: ; End; .5. Thời gian chạy của một chương trình Trong khi giải bài toán ta có thể có một vài thuật toán, vấn đề là chọn thuật toán nào, tiêu chuẩn như thế nào, thường có 2 yêu cầu chính: Dễ hiểu, dễ viết chương trình. Thuật toán dùng các tài nguyên hiệu quả như dùng ít bộ nhớ, chạy càng nhanh càng tốt, .5.1 Ðo thời gian chạy của một chương trình Thời gian chạy của một chương trình phụ thuộc vào các yếu tố: Dữ liệu đầu vào. Tốc độ của máy được dùng. Tính chất của trình biên dich được dùng. Ðộ phức tạp tính toán của thuật toán. 15
16. Phân tích thiết kế thuật toán Trong thực tế thời gian chạy của một chương trình có thể xem như là một hàm của dữ liệu vào. Cụ thể, đó là kích thước của dữ liệu vào. Vì vậy, ta gọi T(n) là thời gian chạy chương trình với dữ liệu vào có độ dài là n. Ðối với nhiều chương trình thì thời gian chạy chương trình còn phụ thuộc vào đặc tính của dữ liệu vào. Nghĩa là dữ liệu vào có cùng độ dài nhưng thời gian chạy chương trình là khác nhau. Vì vậy, ta có thể xem T(n) là thời gian chạy chương trình trong trường hợp xấu nhất trên dữ liệu vào có độ dài là n. Hay nói cách khác T(n) là thời gian chạy chương trình với mọi dữ liệu vào có độ dài là n. Ðo thời gian chạy chương trình như thế nào ? Chương trình A có thời gian chạy chương trình là T1(n)=n2. Chương trình A có thời gian chạy chương trình là T2(n)=4*n+1 Đối với n càng lớn thì T1(n) càng lớn hơn T2(n), như vậy ta có thể xét bậc của hàm tính toán thời gian hay còn gọi là độ phức tạp của thuật toán. .5.2 Ðộ phức tạp của thuật toán Cho một hàm f(n), f(n) được gọi là có bậc G(n) nếu tồn tại các hằng số C và N0 sao cho : f(n) C * G(n) với n N0 Ví dụ : tìm bậc của hàm f(n) = (n+1)2 2 Ta có : f(n) có bậc G(n)=n vì : C = 4 và N0 = 1 để cho f(n) C * G(n) (n N0) Giả sử T(n) là thời gian chạy chương trình, nếu T(n) có bậc là g(n) thì ta nói độ phức tạp tính toán của thuật toán là G(n). Ký hiệu O(G(n)) với : O(C*f(n)) = O(f(n)) với C là hằng số. Trường hợp đặc biệt : O(C) = O(1) với C là hằng số. .5.3 Cách tính thời gian chạy chương trình Cách tính thời gian chạy của một chương trình bất kỳ là một vấn đề không đơn giản. Nhưng đối với nhiều chương trình ta có thể tính thời gian chạy của nó theo 2 quy tắc sau: (áp dụng được cho tất cả các chương trình không đệ quy). 16
17. Phân tích thiết kế thuật toán Chú ý : Thời gian chạy của các lệnh gán Read, Write là O(1). Thời gian chạy của một chuỗi tuần tự các lệnh được xác định theo quy tắc cộng. Như vậy thời gian này là thời gian thi hành một lệnh nào đó lâu nhất trong chuỗi lệnh (câu lệnh đó được gọi là Câu lệnh tích cực). Thời gian chạy của cấu trúc If là thời gian lớn nhất để thực hiện các lệnh sau Then hoặc sau Else cộng với thời gian kiểm tra điều kiện. Thường thời gian kiểm tra điều kiện là O(1). Thời gian thực hiện vòng lặp là tổng (trên tất cả các lần lặp) thời gian thực hiện từng vòng lặp. Nói cách khác thời gian này được tính theo quy tắc nhân tức là tích của số lần lặp với thời gian thực hiện của thân vòng lặp. Thời gian gọi thủ tục hay hàm là thời gian thực hiện đoạn chương trình tương ứng với hàm hay thủ tục đó. Ví dụ 1: Câu lệnh for i: = 1 to n do for j: = 1 to n do x:= x + 1; Ví dụ 2: Procedure BubbleSort (Var a: array [ 1 n ] of Integer); Var i, j, Temp : Integer; Begin for i: = 1 to n do for j: = i to n do If a[i] > a[j] then Begin Temp:= a[i]; a[i]: = a[j]; (1) a[j]:= Temp; End; 17
18. Phân tích thiết kế thuật toán End; Trong đó 5 dạng hàm đầu tiên gọi là hàm đa thức, còn 3 dạng hàm cuối gọi là hàm mũ. Một thuật toán mà thời gian thực hiện có dạng là một hàm đa thức thì có thể chấp nhận được. 18
19. Phân tích thiết kế thuật toán BÀI TẬP Bài 1 : Viết các thủ tục thực hiện các phép toán cộng và nhân 2 ma trận, rồi tính thời gian chạy của các thủ tục này. Bài 2 : Hãy viết chương trình tính gần đúng Ġ theo công thức : Sau đó hãy tính thời gian chạy của chương trình. Bài 3 : Viết chương trình nhập vào một ma trận vuông cấp n. Sau đó in ra các phần tử thuộc các đường chéo song song với đường chéo chính. Phác họa thuật toán của chương trình và tính độ phức tạp của thuật toán. Bài 4 : Hãy tìm một thuật toán để tính Ġ sao cho độ phức tạp của thuật toán sẽ là O(n) và viết chương trình thể hiện thuật toán đã đề ra bằng ngôn ngữ Pascal. Bài 5 : Hãy viết chương trình đổi một số nguyên dương ở hệ thập phân (cơ số 10) sang hệ nhị phân (cơ số 2) và đánh giá thời gian thực hiện của thuật toán. 19
20. Phân tích thiết kế thuật toán BÀI 2 : CÁC KIỂU DỮ LIỆU TRỪU TƯỢNG Mã bài : ITPRG3_12.2 Giới thiệu Mỗi một thuật toán là được xây dựng trên những kiểu dữ liệu tương ứng. Những kiểu dữ liệu này cho phép chúng ta dễ dàng cài đặt các thuật toán trong việc sử dụng những hỗ trợ sẵn có của nó. Nhiều bài toán là không thể được giải quyết nếu không có các kiểu dữ liệu tương ứng, ví dụ : danh sách để lưu trữ một tập các phần tử, con trỏ để tạo các danh sách động Trong bài này chúng ta sẽ xem xét những kiểu dữ liệu cơ bản nhất như con trỏ, danh sách, hàng đợi Chúng ta quan tâm ở đây những vấn đề chính như cách sử dụng, phương pháp để khai báo và sử dụng những hàm có sẵn để dùng trên các kiểu dữ liệu này. Mục tiêu thực hiện Học xong bài này học viên sẽ có khả năng: Nắm được các khái niệm cơ bản và hiểu được tầm quan trọng của việc sử dụng các cấu trúc dữ liệu trừu tượng trong việc xây dựng thuật toán. Cách thức khai báo và các hàm có sẵn (ví dụ trong Turbo Pascal) trên các dữ liệu này. Áp dụng các kiểu dữ liệu này trên một số kiểu bài toán thường gặp. 2.1Khái niệm về con trỏ (Pointer) 2.1.1Ðịnh nghĩa Con trỏ là một kiểu dữ liệu (chiếm 4 bytes trong bộ nhớ) mà các giá trị của nó là địa chỉ của các phần tử của kiểu dữ liệu mà nó trỏ đến. Các giá trị của biến thuộc kiểu T được phát sinh bất cứ lúc nào khi biến đó được cấp phát bằng lệnh New. 2.1.2Khai báo Gián tiếp : Type Tên kiểu = ^Kiểu dữ liệu; 20
21. Phân tích thiết kế thuật toán Var Tên biến : Tên kiểu; Khai báo trực tiếp : Var Tên biến : ^Kiểu dữ liệu; Ví dụ 1: Type Ref = ^Nhansu; Nhansu = Record Data : DataType; Next : Ref; End; Var p: ^Nhansu; Ví dụ 2: Var N : ^Integer; {N là con trỏ chỉ đến số nguyên} Ta xét một khai báo có dạng : Type = ^T; P : biến kiểu con trỏ. T : kiểu dữ liệu mà con trỏ trỏ tới. P^ : giá trị kiểu T mà nó đang trỏ tới. @ : địa chỉ của giá trị mà nó đang trỏ tới. Vậy muốn truy xuất nội dung tại vị trí mà p đang trỏ tới ta dùng P^. Ngoài ra, còn có một con trỏ tổng quát, nó không chỉ đến một kiểu dữ liệu xác định nào cả. Var p : Pointer; Kiểu dữ liệu con trỏ chiếm 4 bytes trong bộ nhớ, 4 bytes này sẽ chứa địa chỉ của kiểu dữ liệu mà nó trỏ tới còn bản thân biến mà nó trỏ tới thì chưa có trong bộ nhớ. Ví dụ : Var p : ^ Integer; i : Integer; Begin i : = 5; p : = @ i; {Hàm lấy địa chỉ của i và gán cho p} Writeln ('Nội dung mà p đang trỏ tới :', p^); Writeln ('Giá trị của biến i : ', i); 21
22. Phân tích thiết kế thuật toán End. .5.4 Một số hàm thường sử dụng ở biến con trỏ a. Cấp phát vùng nhớ : New (p) Thủ tục này sẽ cấp phát vùng nhớ động do con trỏ p quản lý và đồng thời gán cho p địa chỉ đầu của vùng nhớ này. b. Thu hồi vùng nhớ đã cấp phát : Dispose (p) Thủ tục này sẽ hủy bỏ (giải phóng) vùng nhớ do p trỏ tới (quản lý). c. Cấp phát / thu hồi hàng loạt vùng nhớ : Mark (HeapTop) Realease (HeapTop) Thủ tục Mark (HeapTop) sẽ gán giá trị của địa chỉ của vùng Heap cho một con trỏ p nào đó. Con trỏ p này được dùng như để đánh dấu vị trí đầu của vùng ô nhớ sẽ được giải phóng sau này. Sau thủ tục Mark ta có thể dùng hàng loạt thủ tục New để tạo các biến động khác nhau và chúng sẽ chiếm ô nhớ bắt đầu từ vị trí đã được đánh dấu. Nếu muốn lấy lại toàn bộ vùng nhớ đã cấp phát ta chỉ cần dùng thủ tục Realease(HeapTop). Tất nhiên là sau lệnh Realease ta không còn có thể sử dụng các biến động được tạo ra bằng thủ tục New nằm trong vùng ô nhớ vừa được giải phóng. d. Thủ tục : GetMem (p, k) Thủ tục này sẽ cấp phát k bytes vùng nhớ do con trỏ p quản lý. e. Thủ tục : FreeMem (p, k) Thủ tục này sẽ thu hồi vùng nhớ đã được cấp phát bởi thủ tục GetMem. f. Các hàm cho biết tình trạng của vùng nhớ : Hàm MaxAvail (kiểu Longint) : Hàm cho biết vùng nhớ lớn nhất còn trống trong Heap. Hàm MemAvail (kiểu Longint) : Hàm cho biết tổng số bytes còn lại trên Heap. Hàm SizeOf (Biến) (kiểu Longint) : Cho biết số bytes được cấp phát / thu hồi bởi biến. Ví dụ : P là con trỏ trỏ đến kiểu RecordType nào đó. If MaxAvail >= SizeOf(RecType) then New(p) Else 22
23. Phân tích thiết kế thuật toán Writeln('Không đủ vùng nhớ cấp phát'); g. Các hàm cho biết địa chỉ của một đối tượng trong bộ nhớ : Hàm Add (x) (kiểu Pointer) : Cho biết địa chỉ tổng quát của biến x. Hàm Seg (x) (kiểu Word) : Cho biết địa chỉ segment của biến x. Hàm Ofs (x) (kiểu Word) : Cho biết địa chỉ Offset của biến x. Hàm Ptr (Seg, Ofs) (kiểu Pointer) : Trỏ tới địa chỉ seg : Ofs. Ví dụ 1 : Var a : Integer; b : String; p : ^ Integer; q : ^ String; r : Pointer; Begin a : = 1234; p : = @a; Writeln (' Nội dung của a là : ', a); Writeln (' Nội dung p đang trỏ tới là : ', p^); r : = @b; q : = r; b : = 'Khoa su pham truong dai hoc can tho'; Writeln (q^); End. Ví dụ 2 : Type Name = String [30]; PtrName = ^ Name; Var p, q : ^ Name; k : Word; Begin Writeln ('Vùng nhớ ban đầu',MemAvail,' Bytes trống'); New (p); p : = 'Khoa Su Pham'; k : = SizeOf (p); Writeln ('Vùng nhớ sau khi khởi động',MemAvail,' Bytes'); GetMem(q, SizeOf(q)); P^ : = q^; Writeln ('p có kích thưóc là : ',SizeOf(p^),'); Writeln ('q có kích thưóc là : ',SizeOf(q^),'); 23
24. Phân tích thiết kế thuật toán Writeln ('Nội dung của q là : ',q^,'); Dispose(p); FreeMem (q,k); Writeln ('Vùng nhớ hiện tại là :',MemAvail,'Bytes'); End. .6. Danh sách (LIST) 2.2.1Khái niệm Mô hình toán học của danh sách là một tập hợp các phần tử có cùng một kiểu mà ta gọi là kiểu phần tử (ElementType). Ta thường biểu diễn danh sách bằng một dãy các phần tử của nó và cách nhau bởi dấu ‘,’ : a 1, a2, , an. Nếu n=0 ta gọi là danh sách rỗng. Nếu n >0, ta gọi a1 là phần tử đầu tiên và an là phần tử cuối cùng của danh sách. Số phần tử của danh sách được gọi là độ dài của danh sách. Một tính chất quan trọng của danh sách là các phần tử của danh sách có thứ tự tuyến tính theo vị trí xuất hiện của chúng (position). Ta nói ai là phần tử đứng trước ai+1 (i=1, 2, , n-1) và là phần tử đứng sau phần tử ai-1. ai là phần tử thứ i trong danh sách. .6.1 Các phép toán trên danh sách Để thuận tiện cho việc định nghĩa các phép toán trên danh sách, ta xem như danh sách có tồn tại một phần tử đứng sau phần tử cuối cùng của danh sách L : a1, a2, , an là EndList(L) (mang giá trị n+1 nếu như danh sách có n phần tử). Một số phép toán trên danh sách : a. Hàm MakeNullList (Var L : List) - Hàm tạo một danh sách L rỗng. b. Hàm EmptyList (L : List) : Boolean - Hàm kiểm tra danh sách rỗng (Hàm cho kết quả là True nếu danh sách rỗng và kết quả là False nếu ngược lại). c. Hàm First (L : List) : Position - Hàm cho kết quả là vị trí của phần tử đứng đầu danh sách L. Nếu danh sách rỗng thì ta có First (L) = EndList (L). d. Hàm Next (p : Position ; L : List) : Position - Hàm cho kết quả là vị trí của phần tử đứng sau phần tử thứ p trong danh sách L. Nếu p là phần tử cuối danh sách thì ta có Next (p, L) = EndList (L). e. Hàm Previous (p : Position ; L : List) : Position - Hàm cho kết quả là vị trí của phần tử đứng trước phần tử thứ p trong danh sách L. Nếu p là phần tử đầu danh sách thì hàm không xác định. f. Hàm Retrieve (p : Position ; L : List) : ElementType - Hàm cho kết quả là nội dung của phần tử thứ p trong danh sách L. Nếu vị trí p không tồn tại thì hàm không xác định. 24
25. Phân tích thiết kế thuật toán g. Thủ tục InsertList (x : ElementType ; p : Position ; Var L : List) - Thủ tục thực hiện việc xen phần tử x vào vị trí p trong danh sách L h. Thủ tục DeleteList (p : Position ; Var L : List) - Thủ tục thực hiện việc xóa phần tử tại vị trí p trong danh sách L i. Hàm Locate (x : ElementType ; L : List) : position - Hàm tìm phần tử x trong danh sách L. Hàm trả về vị trí đầu tiên của phần tử x nếu tìm thấy. Nếu không tìm thấy hàm trả về EndList (L). j. Thủ tục PrintList (L : List) - In danh sách các phần tử trong danh sách L theo thứ tự xuất hiện của các phần tử. Ví dụ 1 : Viết thuật toán sắp xếp một danh sách theo thứ tự tăng dần giả sử thủ tục Swap (p, q) thực hiện việc đổi chỗ 2 phần tử tại vị trí p và vị trí q. Thủ tục : Procedure BubbleSort (Var L : List); Var p, q : position; Begin P : = First(L); While p EndList(L) do Begin If Retrieve(p) > Retrieve(q) then Swap(p, q) Else q : = Next(q, L); End; P : = Next(p, L); End; End; Ví dụ 2 : Lặp danh sách các hồ sơ và loại bỏ các hồ sơ trùng lặp. Procedure LoaiBo (Var L : List); Var p, q : position; Begin P : = First(L); While p EndList(L) do Begin 25
26. Phân tích thiết kế thuật toán If Retrieve(p)=Retrieve(q) then DeleteList(q,L) Else q : = Next(q, L); End; P : = Next(p, L); End; End; .6.2 Cài đặt danh sách a. Cài đặt danh sách bằng mảng (danh sách đặc) : Danh sách đặc là danh sách mà các phần tử của nó được sắp xếp trong các vùng nhớ hay ô nhớ liên tiếp nhau. Cài đặt danh sách bằng mảng nghĩa là ta dùng một mảng (array) để lưu trữ liên tiếp các phần tử của danh sách bắt đầu từ vị trí đầu tiên của mảng. Dĩ nhiên là ta phải ước lượng số phần tử của danh sách để khai báo số phần tử của mảng thích hợp và nói chung là còn thừa chỗ trống trong mảng, vì vậy ta phải lưu giữ độ dài hiện tại của danh sách. Danh sách này cho biết mảng có bao nhiêu phần tử và phần tử nào của mảng còn trống. Khai báo : Const Maxlength = ; {Ðộ dài tối đa của danh sách} Type ElementType = ; {Kiểu phần tử trong danh sách} List = Record Elements : array [1 Maxlength] of ElementType; Last : integer; {Ðộ dài thật sự của danh sách} End; Thủ tục khởi tạo danh sách rỗng : Procedure MakenullList (Var L : List); Begin 26
27. Phân tích thiết kế thuật toán L.Last : = 0; End; Hàm kiểm tra danh sách rỗng : Function EmptyList (L : List) : Boolean; Begin EmptyList : = (L.Last = 0); End; Hàm kiểm tra danh sách đầy : Function FullList (L : List) : Boolean; Begin FullList : = (L.Last > = Maxlenght); End; Thủ tục nhập giá trị cho các phần tử của danh sách : Procedure ReadList (Var L : List); Var i : position; Begin For i := 1 to L. Last do Begin Write (' Nhập phần tử thứ ', i ,' của danh sách : '); Readln (L.Elements [i]); End; End; Thủ tục xen một phần tử vào danh sách : Khi xen một phần tử vào danh sách, ta có thể gặp các trường hợp sau đây : Mảng đầy (độ dài của danh sách = độ dài của mảng) thì thủ tục sẽ bị lỗi. Ngược lại nếu vị trí p không tồn tại (p L . Last + 1) thì thủ tục cũng bị lỗi. Ngược lại nếu vị trí p là hợp lệ thì ta thực hiện các bước sau : Dời các phần tử từ vị trí p đến cuối danh sách xuống 1 đơn vị. Ðộ dài của danh sách tăng lên 1. Xen phần tử mới vào vị trí p của danh sách. Procedure InsertList (x:ElementType; p:position; Var L:List); Var i:position; 27
28. Phân tích thiết kế thuật toán Begin If (L.Last>=Maxlength) then writeln('Mảng đầy') Else Begin for i:=L.Last downto p do L.Elements [i+1]:=L.Elements [i]; L.Last:= L.last + 1; L.Elements[p]:=x; End; End; Thủ tục xóa một phần tử khỏi danh sách : Khi xóa một phần tử khỏi danh sách, ta có thể gặp các trường hợp sau đây : - Danh sách rỗng thì thủ tục sẽ bị lỗi. - Ngược lại nếu vị trí p không tồn tại (p L . Last + 1) thì thủ tục cũng bị lỗi. - Ngược lại nếu vị trí p là hợp lệ thì ta thực hiện các bước sau : - Dời các phần tử từ vị trí p + 1 đến cuối danh sách lên 1 đơn vị. - Ðộ dài của danh sách giảm đi 1 đơn vị. Procedure DeleteList(p : position; Var L : List); Var i: position; Begin If EmptyList(L) then Writeln ('Danh sách rỗng') Else Begin for i : = p to L.Last do L.Elements [i] : = L.Elements [i+1]; L.Last : = L.Last - 1; End; End; Hàm tìm kiếm một phần tử trong danh sách : Hàm Locate(x, L) tìm phần tử x trong danh sách L và cho kết quả là phần tử đầu tiên nếu tìm thấy, còn nếu không tìm gûặp thì hàm cho kết quả là EndList (L) (tức là Last + 1) 28
29. Phân tích thiết kế thuật toán Thuật toán đơn giản như sau : Bắt đầu từ phần tử đầu tiên, rồi lần lượt duyệt qua các phần tử tiếp theo cho đến khi tìm được phần tử cần tìm (đầu tiên). Trả kết quả về cho hàm là vị trí của của phần tử được tìm thấy. Function Locate (x : ElementType; L : List) : position; Var i : position; Begin i : = 1; While (i x) do i:=i+1; Locate : = i; End; Thủ tục hiển thị các phần tử của danh sách : Procedure WriteList (L : List); Var i : position; Begin For i := 1 to L. Last do Writeln (L.Elements [i]); End; Ðặc điểm của danh sách đặc : Ưu điểm : Không lảng phí bộ nhớ. Dễ dàng truy xuất đến các phần tử của danh sách. Nhược điểm : Phép xen, xóa tương đối phức tạp, nó phụ thuộc vào số phần tử của danh sách. Ðòi hỏi phải xác định số phần tử của mảng, nếu không ước lượng được số phần tử thì không thể cài đặt một cách hiệu quả. Do đó danh sách đặc được sử dụng phổ biến đối với các danh sách ít biến động. b. Cài đặt danh sách bằng con trỏ (danh sách liên kết) : Ðịnh nghĩa : Danh sách liên kết là danh sách mà các phần tử của nó được nối kết với nhau nhờ vào vùng liên kết của chúng. Với danh sách này, khi cài đặt ta không cần dùng bộ nhớ liên tục và không cần di chuyển các phần tử khi xen hoặc xóa. Mô tả danh sách liên kết : 29
30. Phân tích thiết kế thuật toán a1 a2 an nil Ðể cài đặt danh sách liên kết, ta dùng con trỏ để liên kết các phần tử của danh sách theo phương thức ai chỉ đến ai+1. Ðể một phần tử có thể chỉ đến một phần tử khác ta xem mỗi ô là một Record gồm có 2 trường : Trường Elements để giữ nội dung của phần tử trong danh sách. Trường Next là một con trỏ giữ địa chỉ của ô kế tiếp. Phần tử cuối cùng của danh sách ta cho trỏ đến một giá trị đặc biệt Nil. Ðể quản lý danh sách ta cần một biến chỉ đến phần tử đấu danh sách. Biến này được gọi là chỉ điểm đầu danh sách Header. Header là một ô có cùng kiểu với kiểu phần tử trong danh sách. Nhưng trường Elements của ô header là rỗng, còn trường Next của ô Header thì giữ địa chỉ của phần tử đầu danh sách. Khai báo : Type ElementType = ; {Kiểu phần tử của danh sách} Position = ^ CellType; CellType = Record Elements: ElementType; Next : Position; End; List = Position; Thủ tục khởi tạo danh sách rỗng : Procedure MakenullList (Var Header : List); Begin New (Header); Header.Next : = Nil; End; Hàm kiểm tra danh sách rỗng : Function EmptyList(Header : List): Boolean; 30
31. Phân tích thiết kế thuật toán Begin EmptyList: = (Header.Next = Nil); End; Thủ tục duyệt các phần tử trong danh sách liên kết : Procedure Order (L : List); Var p : Position; Begin p : = L^.Next; While p <> Nil do Begin Write (p^.Elements); p:= p^.Next; End; End; Thủ tục xen thêm một phần tử vào danh sách liên kết : Muốn xen một phần tử x vào danh sách ta cần biết vị trí p trước chỗ xen, rồi ta xen x vào vị trí sau p. Procedure InsertList (x: ElementType; p : Position); Var Temp : Position; Begin New (Temp); Temp^.Elements:=x; Temp^.Next:= p^.Next; p^.Next:= Temp; End; Thủ tục xóa phần tử khỏi danh sách liên kết : 31
32. Phân tích thiết kế thuật toán Muốn xóa một phần tử trong danh sách ta cũng cần biết vị trí p trước chỗ xóa. Procedure DeleteList (p : Position); Var Temp : Position; Begin Temp:= p^.Next; p^.Next:= Temp^.Next; Dispose(Temp); End; Thủ tục tìm kiếm một phần tử trong danh sách liên kết : Function Locate (x: ElementType; L:List) : Position; Var p: Position; Found: Boolean; Begin p:= L^.Next; found:= False; While (p <> Nil) and (not found) do If p^.Elements = x then Found:= True Else p:= p^.Next; Locate:= p; End; So sánh 02 phương pháp cài đặt : c. Cài đặt danh sách liên kết bằng con nháy (trên cơ sở mảng) : Danh sách không phải là một cấu trúc dữ liệu tiền định trong đa số các ngôn ngữ lập trình. Vì vậy, người lập trình phải cài đặt bằng các cấu trúc tiền định khác có sẳn trong ngôn ngữ lập trình. Ví dụ : một số ngôn ngữ lập trình không có định nghĩa biến kiểu con trỏ. Trong trường hợp này ta sẽ giả con trỏ (dựa trên cơ sở cấu trúc tiền định mảng, được định nghĩa trong hầu hết các ngôn ngữ lập trình) để cài đặt danh sách liên kết. 32
33. Phân tích thiết kế thuật toán Ý tưởng: Là dùng một biến số nguyên (Integer) để lưu giữ chỉ số (vị trí) của các phần tử kế tiếp trong mảng. Như vậy để cài đặt danh sách bằng con nháy ta cần một mảng mà mỗi phần tử là một Record gồm 2 trường: Trường Elements: giữ nội dung của phần tử trong danh sách. Trường Next: là một số nguyên chỉ tới vị trí của phần tử kế tiếp.Ðể quản lý danh sách, ta dùng một con nháy (một biến số nguyên) để chỉ đến phần tử đầu danh sách. Phần tử cuối danh sách ta cho chỉ đến một phần tử đặc biệt Null (Giá trị Null có thể chọn là 0, nếu như mảng không có phần tử có giá trị 0). Khi xen một phần tử vào danh sách, ta lấy một ô trống trong mảng để chứa phần tử mới này và nối kết lại các con nháy. Tương tự, khi xóa một phần tử khỏi danh sách, ta nối kết lại các con nháy để loại bỏ phần tử đó. Ðiều này kéo theo số phần tử trong mảng tăng lên 1. Ðể quản lý các ô trống, ta liên kết tất cả các ô trống vào một danh sách đặc biệt gọi là Available. Khi xen một phần tử vào danh sách ta lấy ô trống đầu Available để chứa phần tử mới này. Khi xóa 1 phần tử, ta cho ô bị xóa nối vào đầu Available. Khai báo : Const Maxlenght = ; { Ðộ dài cực đại của mảng } Type ElementType = ; {Kiểu phần tử của danh sách} CursorType = 0 Maxlenght ; { Kiểu con nháy } NodeType = Record Elements: ElementType; Next : CursorType; End; ArrayOfNodes = Array [1 Maxlenght] of NodeType; Var Node: ArrayOfNode; Available: CursorType; {Chỉ đến nút tự do đầu tiên} List: CursorType; { Chỉ đến nút đầu danh sách } 33
34. Phân tích thiết kế thuật toán Thủ tục khởi tạo vùng lưu trữ các nút tự do : Procedure Initialize; Var i: Integer; Begin for i: = 1 to Maxlenght - 1 do Node[i].Next := i + 1; Node[Maxlenght].Next := 0; Available := 1; End; Thủ tục lấy nút tự do đầu tiên : { Thủ tục này trả con nháy p chỉ đến nút tự do, nếu không còn nút tự do, P trả về giá trị Null (0) } Procedure Getnode (Var P:CursorType); Begin p := Available; If p 0 then Available := Node[p].Next Else Writeln('Vung luu tru rong'); End; Thủ tục khởi tạo danh sách rỗng : Procedure Create (Var List: CursorType); Begin List : = 0; {Null} End; Hàm kiểm tra danh sách rỗng : Function EmptyList(List : cursorType): Boolean; Begin EmptyList: = (List = 0); End; Thủ tục duyệt các phần tử trong danh sách liên kết : Procedure Linker (List: CursorType); Var CrrPtr : CursorType; Begin 34
35. Phân tích thiết kế thuật toán CrrPtr := List; While CrrPtr 0 do Begin Write(Node[CrrPtr].Elements); CrrPtr := Node[CrrPtr].Next; End; End; Hàm chuyển 1 phần tử từ danh sách này sang danh sách khác : Ta thấy thực chất của việc xen hay xóa một phần tử là thực hiện công việc chuyển một ô từ danh sách này sang danh sách khác. Vậy ta cần phải viết một hàm Move thực hiện thao tác này. Hàm cho kết quả kiểu Boolean tùy theo việc chuyển thành công hay thất bại. Ta viết hàm Move thực hiện việc chuyển ô được chỉ bởi con nháy p vào ô trước ô được chỉ bởi con nháy q. Function Move (var p, q: Integer) : Boolean; Var Temp : Integer; Begin If p = 0 then Move := false Else Begin Temp := q; q := p; p := Node[p].Next; Node[p].Next := Temp; Move := True; End; End; Thủ tục xen một phần tử vào danh sách : Muốn xen một phần tử vào danh sách, ta cần biết vị trí trước chỗ xen rồi ta chuyển ô đầu Available vào vị trí cần xen (sau p). Tuy nhiên, nếu ta xen vào đầu danh sách thì không có vị trí 35
36. Phân tích thiết kế thuật toán thực sự trước đó. Ta sẽ cho p một giá trị đặc biệt để thủ tục xử lý trong trường hợp này. Ở đây ta cho p = 0 Procedure InsertList(x:ElementType;p:CursorType;Var L:CursorType); Begin If p = 0 then { Xen vào đầu danh sách } Begin If Move (Available, L) then Node[L].Elements := x; End Else If Move (Available, Node[p].Next) then Node [Node [p].Next].Elements := x; End; Thủ tục xóa một phần tử khỏi danh sách : Muốn xóa một phần tử khỏi danh sách ta cũng cần biết vị trí trước chỗ xóa rồi ta chuyển ô cần xóa này vào đầu Available. Tương tự như phép xen vào, muốn xóa phần tử đầu danh sách ta cho p = 0. Procedure DeleteList (p : CursorType; Var L : CursorType); Begin If p = 0 then { Xóa phần tử đầu danh sách } If Move (L, Available) then Writeln ('Da xoa') Else Writeln ('Loi') Else If Move(Node[p].Next, Available) then Writeln('Da xoa') Else Writeln ('Loi') End; .7. Cấu trúc chồng / ngăn xếp (STACK) 2.3.1Ðịnh nghĩa : Stack là một danh sách đặc biệt mà phép thêm vào hoặc loại bỏ một phần tử chỉ thực hiện tại một đầu gọi là đỉnh (Top) của Stack. Như vậy, Stack là một cấu trúc có tính chất vào trước, ra sau (FILO - First In Last Out). .7.1 Các phép toán trên Stack a. Thủ tục MakeNullStack (Var S : Stack) : Tạo một Stack rỗng. b. Hàm/thủ tục Top (S : Stack) : Trả về kết quả là phần tử tại đỉnh của Stack 36
37. Phân tích thiết kế thuật toán c. Thủ tục Pop (Var S : Stack) : Loại bỏ phần tử tại đỉnh của Stack. d. Thủ tục Push (x : ElementsType; Var S : Stack) : Ðặt phần tử x vào đỉnh của Stack. e. Hàm EmptyS (S : Stack) : Boolean : Kiểm tra xem một stack có rỗng hay không? Hàm trả về giá trị True nếu Stack rỗng và False nếu ngược lại. f. Hàm FullS (S : Stack) : Boolean : Kiểm tra xem một stack có đầy hay không? Hàm trả về giá trị True nếu Stack đầy và False nếu ngược lại. Ví dụ : Viết thủ tục nhập từ bàn phím một dãy ký tự cho đến khi gặp ký tự '@' thì ngưng. In dãy ký tự theo thứ tự ngược lại lúc nhập. Ta sẽ trình bày thuật toán cho thủ tục này theo 2 cách sau: Procedure Edit; Procedure Edit1; Var S : Stack; Var S : Stack; C : Char; C : Char; Begin Begin MakeNullStack (S); MakeNullStack (S); Repeat Repeat Read (c); Read (c); Push (c, S); If c '@' then Until c = '@'; Push (c, S); Repeat Until c = '@'; Write (Top(S)); While not EmptyS (S) do Pop (S); Begin Until EmptyS (S); Write (Top(S)); End; Pop (S); End; End; .7.2 Cài đặt Stack bằng mảng Khai báo : Const Maxlength = ; { Ðộ dài mảng } Type ElementType = ; { Kiểu phần tử } Stack = Record Elements : array[1 Maxlength] of ElementType; Top : integer; 37
38. Phân tích thiết kế thuật toán End; Thủ tục khởi tạo Stack rỗng : Procedure MakeNullStack (Var S : Stack); Begin S.Top :=Maxlenght + 1; End; Hàm kiểm tra Stack rỗng : Function EmptyS (S : Stack) : Boolean; Begin EmptyS := (S.Top = Maxlenght + 1); End; Hàm kiểm tra Stack đầy : Function FullS (S : Stack):Boolean; Begin FullS := (S.Top = 1); End; Hàm cho phần tử ở đầu Stack : Function Top (S : Stack) : ElementType; Begin If not EmptyS (S) then Top:=S.Elements[S.Top] Else Writeln('Stack rong'); End; Nếu Elements không thể là kiểu kết quả của hàm thì ta sẽ chuyển thành thủ tục như sau : Procedure Top (S : Stack; Var x : ElementType); Begin If not EmptyS(S) then x:=S.Elements[S.Top] Else Writeln('Stack rong'); End; Thủ tục xóa một phần tử khỏi Stack : Procedure Pop(Var S: Stack); Begin If not FullS(S) then 38
39. Phân tích thiết kế thuật toán S.Top:=S.Top+1 Else Writeln('Stack rong'); End; Thủ tục thêm một phần tử vào Stack : Procedure Push(x:ElementsType; Var S:Stack); Begin If not FullS(S) then Begin S.Top:=S.Top -1; S.Elements[S.Top]:=x; End Else Writeln('Stack day'); End; .7.3 Cài đặt Stack bằng con trỏ Khai báo : Type ElementType = ; { Kiểu phần tử } PointerType = ^ StackNode; StackNode = Record Elements : ElementType; Next : PointerType; End; StackType = PointerType; Var Stack : StackType; { Chỉ đến phần tử ở đỉnh Stack } Thủ tục khởi tạo Stack rỗng : Procedure MakeNullStack(Var S : StackType); Begin Stack := Nil; { Stack rỗng } End; Hàm kiểm tra Stack rỗng : Function EmptyS(S : StackType) : Boolean; Begin EmptyS := (Stack := Nil); End; Thủ tục xóa một phần tử khỏi Stack : Procedure Pop(Var S: StackType; Var x: ElementType); 39
40. Phân tích thiết kế thuật toán Var TempPtr : PointerType; Begin If EmptyS (S) then Writeln('Stack rong') Else Begin x := Stack^.Elements; TempPtr := Stack; Stack := Stack^.Next; Dispose (TempPtr); End; End; Thủ tục thêm một phần tử vào Stack : Procedure Push(Var Stack : StackType; x:ElementType); Var TempPtr : PointerType; Begin New (TempPtr); TempPtr^.Elements :=x; TempPtr^.Next := Stack; Stack := TempPtr; End; Hàm cho phần tử đầu Stack : Function Top(Stack : StackType) : ElementType; Begin Top := Stack^.Elements; End; Ví dụ: Dùng cấu trúc Stack để viết chương trình đổi một số nguyên ở dạng thập phân thành dạng nhị phân. Program Nhi_phan; Type ElementType = integer; { Kiểu phần tử } PointerType = ^ StackNode; StackNode = Record Elements : ElementType; Next : PointerType; End; StackType = PointerType; Var Stack : StackType; { Chỉ đến phần tử ở đỉnh Stack } 40
41. Phân tích thiết kế thuật toán Number, du : Integer; {Các thủ tục cần thiết cho chương trình } Procedure MakeNullStack (Var S : StackType); Function EmptyS (S : StackType) : Boolean; Procedure Push(Var Stack : StackType; x:ElementType); Procedure Pop(Var S: StackType; Var x: ElementsType); BEGIN { Chương trình chính } Write ('Nhap so can doi : '); Readln (Number); MakeNullStack(Stack); While Number 0 do Begin Du := Number mod 2; Push(Stack, du); Number := Number Div 2; End; While not EmptyS(Stack) do Begin Pop(Stack, du); Write(Du : 1); End; Readln; END. { Chương trình chính } .8. Cấu trúc hàng đợi 2.4.1Ðịnh nghĩa Hàng là một danh sách đặc biệt mà phép thêm vào chỉ thực hiện ở một đầu của danh sách gọi là cuối hàng (Rear). Phép loại bỏ lại được thực hiện ở một đầu kia của danh sách gọi là đầu hàng (Front). Như vậy hàng là một cấu trúc dữ liệu có tính chất "Vào trước - ra trước" - FIFO : First In First Out. .8.1 Các phép toán cơ bản trên hàng a. Thủ tục MakeNullQueue (Var Q : Queue) : Tạo một hàng rỗng. b. Hàm Front (Q : Queue) : ElementType : Trả về kết quả là phần tử đầu hàng. c. Thủ tục EnQueue (x : ElementType; Var Q : Queue) : Ðặt phần tử x vào cuối của hàng. d. Thủ tục DeQueue (Var Q : Queue) : Xóa một phần tử đầu hàng. 41
42. Phân tích thiết kế thuật toán e. Hàm EmptyQ (Q : Queue) : Boolean : Kiểm tra xem một Queue có rỗng hay không? Hàm trả về giá trị True nếu Queue rỗng và False nếu ngược lại. f. Hàm FullQ (Q : Queue) : Boolean : Kiểm tra xem một Queue có đầy hay không? Hàm trả về giá trị True nếu Queue đầy và False nếu ngược lại. .8.2 Cài đặt hàng a. Cài đặt hàng bằng mảng: Ta dùng một mảng để chứa các phần tử của hàng. Phần tử đầu hàng xếp vào vị trí thứ nhất của mảng, phần tử thứ hai xếp vào vị trí thứ 2, Giả sử mảng có n phần tử ta có Front = 1 và Rear = n. Khi xóa một phần tử Front tăng lên 1, khi thêm một phần tử vào hàng Rear tăng lên 1. Như vậy, hàng có khuynh hướng đi xuống và đến một lúc nào đó ta không thể thêm vào hàng được nữa dù rằng mảng còn nhiều chỗ trống. Ta gọi là hàng bị tràn. Trong trường hợp toàn bộ mảng đã chứa các phần tử ta gọi là hàng bị đầy. Cách khắc phục hàng bị tràn: Dời toàn bộ hàng lên Front - 1 vị trí. Cách này gọi là di chuyển tịnh tiến và ta luôn có Front < Rear. Xem mảng như là một vòng tròn nghĩa là khi hàng bị tràn nhưng chưa đầy, ta thêm phần tử mới vào vị trí thứ nhất của mảng, thêm phần tử thứ 2 vào vị trí thứ 2 của mảng, (nếu có thể). Cách này gọi là mảng vòng. * Cài đặt hàng bằng phương pháp di chuyển tịnh tiến: Khai báo : Const Maxlength = ; { Ðộ dài mảng } Type ElementType = ; { Kiểu phần tử } Queue = Record Elements : array[1 Maxlength] of ElementType; Front, Rear : integer; End; Thủ tục khởi tạo Queue rỗng : Procedure MakeNullQueue(Var Q : Queue); Begin Q. Front := 0; Q. Rear := 0; End; Hàm kiểm tra Queue rỗng : Function EmptyQ(Q : Queue) : Boolean; Begin EmptyQ := (Q.Front = 0); 42
43. Phân tích thiết kế thuật toán End; Hàm kiểm tra Queue đầy : Function FullQ(Q : Stack):Boolean; Begin FullQ := ((Q.rear - Q.Front + 1) = Maxlenght); End; Hàm ütruy xuất phần tử đầu hàng : Function Front(Q: Queue) : ElementsType; Begin Front := (Q.Elements [Q.Front]); End; Thủ tục xen một phần tử vào cuối hàng : Procedure EnQueue(x : ElementsType; Var Q: Queue); Var i : integer; Begin If not FullQ (Q) then Begin If EmptyQ (Q) then Q.Front := 1; If Q.Rear = Maxlenght then Begin For i := Q.Front to Q.Rear do Q.Elements [i - Q.Front + 1] := Q.Elements[i]; Q.Rear := Maxlenght - Q.Front + 1; End; Q.Rear := Q.Rear + 1; Q.Elements [Q.Rear] := x; End Else Write ('Hang day'); End; Thủ tục xóa một phần tử đầu hàng : Procedure DeQueue(Var Q: Queue); Begin If not EmptyQ(Q) then Begin Q.Front := Q.Front + 1; If Q.Front > Q.Rear then 43
44. Phân tích thiết kế thuật toán MakeNullQueue (Q); End Else Write ('Queue rong'); End; * Cài đặt hàng bằng mảng vòng: Hàm kiểm tra Queue đầy : Function FullQ (Q : Stack):Boolean; Begin FullQ := ((Q.rear - Q.Front + 1) mod Maxlenght = 0); End; Thủ tục xen một phần tử vào cuối hàng : Procedure EnQueue (x : ElementsType; Var Q: Queue); Begin If not FullQ (Q) then Begin If EmptyQ (Q) then Q.Front := 1; Q.Rear := (Q.rear mod Maxlenght) + 1; Q.Elements [Q.Rear] := x; End Else Write ('Hang day'); End; Thủ tục xóa một phần tử đầu hàng : Procedure DeQueue (Var Q: Queue); Begin If not EmptyQ (Q) then If Q.Front=Q.Rear then MakeNullQueue (Q) Else Q.Front := (Q.Front mod Maxlenght) + 1 Else Write ('Queue rong'); End; 44
45. Phân tích thiết kế thuật toán b. Cài đặt hàng bằng con trỏ: Ta sẽ dùng 2 con trỏ Front và Rear để quản lý hàng (Front chỉ đến phần tử đầu hàng, Rear chỉ đến phần tử cuối hàng). Khai báo : Type ElementType = ; { Kiểu phần tử } CellType = ^ Cell; Cell = Record Elements : ElementType; Next: CellType; End; Queue = Record Front, Rear : CellType; End; Thủ tục khởi tạo Queue rỗng : Hàm kiểm tra Queue rỗng : Function EmptyQ (Q : Queue) : Boolean; Begin EmptyQ := (Q.Front = Q.Rear); End; Thủ tục xen một phần tử vào cuối hàng : 45
46. Phân tích thiết kế thuật toán Procedure EnQueue (x : ElementType; Var Q: Queue); Begin If EmptyQ (Q) then Begin New (Q.front); Q.Front^.Elements := x; Q.Front^.Next := Nil; Q.Rear := Q.Front; End Else Begin New (Q.rear^.Next); Q.rear := Q.rear^.Next; Q.rear^.Elements :=x; Q.rear^.Next := Nil; End; End; Thủ tục xóa một phần tử đầu hàng : Procedure DeQueue (Var Q: Queue); Var Temp : CellType; Begin If not EmptyQ (Q) then Begin Temp := Q.Front; Q.front := Q.Front^.Next; Dispose (Temp); End Else 46
47. Phân tích thiết kế thuật toán Write ('Queue rong'); End; .9. Danh sách liên kết kép (Double Link List) .9.1 Nhận xét Ðối với danh sách liên kết đơn, khi biết được một nút ta chỉ có thể truy xuất đến nút đứng sau nó. Nếu muốn truy xuất đến nút đứng trước thì phải quay về đầu danh sách (Ta cần tạo một danh sách liên kết kép để có thể truy xuất các phần tử một cách dễ dàng hơn. Ta xem mỗi phần tử của danh sách là một ô. Ở mỗi ô ta dùng 2 con trỏ ở 2 đầu : Con trỏ Next chỉ đến nút tiếp theo. Con trỏ Prevous chỉ đến nút liền trước. Ngoài ra còn có một trường dữ liệu dùng để lưu trữ dữ liệu của ô đang xét. .9.2 Khai báo Type ElementType = ; { Kiểu phần tử trong danh sách } DList= ^ CellType; CellType = Record Elements: ElementType; Next,Previous:DList; End; Var List = DList; .9.3 Thủ tục khởi tạo danh sách liên kết kép rỗng .9.4 Hàm kiểm tra danh sách liên kết kép rỗng Function EmptyDList (L : DList):Boolean; Begin EmptyDList := ((L^.Next=Nil) and (L^.Previous=Nil)); End; 47
48. Phân tích thiết kế thuật toán .9.5 Thủ tục xen một phần tử vào danh sách liên kết kép Procedure InsertList(x:ElementsType;p:DList; var List : DList); Var Temp : DList; Begin New (Temp); Temp^.Elements := x; Temp^.Next := p^.Next; If p^.Next Nil then p^.Next^.Previous := Temp; Temp ^.previous := p; p^.Next := Temp; End; .9.6 Thủ tục xóa một phần tử khỏi danh sách liên kết kép Procedure DeleDlist (p : DList; Var List : Dlist); Begin If not EmptyDList (List) then Begin If p^.Next Nil then p^.Next^.Previous := p^.Previous; p^.Previous^.Next := p^.Next; Dispose (p); End Else Writeln ('Danh sach rong'); End; 48
49. Phân tích thiết kế thuật toán BÀI TẬP Bài 1 : Hãy giải thích vì sao thời gian chạy của thủ tục xóa một phần tử trong danh sách (cài đặt bằng mảng) trong trường hợp tốt nhất là O(1) và xấu nhất là O(n). Bài 2 : Viết chương trình nhập vào một danh sách các số nguyên, in danh sách theo yêu cầu: In danh sách ra màn hình theo thứ tự như lúc nhập và thứ tự ngược lúc nhập. Bài 3 : Viết thủ tục sắp xếp một danh sách các số nguyên trong các trường hợp : 1. Danh sách được cài đặt bằng mảng. 2. Danh sách được cài đặt bằng con trỏ. Bài 4 : Viết các thủ tục thực hiện yêu cầu sau : 1. Thêm một phần tử vào một danh sách đã có thứ tự (tăng hoặc giảm) sao cho ta được một danh sách mới vẫn bảo đảm thứ tự. 2. Xóa một phần tử trong danh sách liên kết đã có thứ tự. Bài 5 : Viết thủ tục trộn 2 danh sách đã có thứ tự (tăng hoặc giảm) để được một danh sách mới vẫn bảo đảm thứ tự ban đầu. Bài 6 : Viết thủ tục nhập vào một danh sách các số nguyên, loại bỏ các phần tử trùng nhau. Sau đó sắp xếp danh sách theo thứ tự tăng (hoặc giảm). In danh sách sau khi đã được sắp xếp. Bài 7 : Ða thứcĠ được lưu trữ trong máy tính dưới dạng một danh sách liên kết mà mỗi phần tử của danh sách là một Record gồm có 3 trường : lưu trữ hệ số, số mũ và trường Next là một con trỏ chỉ đến phần tử kế tiếp. Chú ý rằng cách lưu trữ đảm bảo thứ tự số mũ giảm dần của từng hạng tử trong đa thức. Hãy viết chương trình thực hiện các công việc sau : 1. Lưu trữ đa thức. 2. Cộng 2 đa thức. 3. Tính độ phức tạp tính toán của thuật toán của thủ tục cộng 2 đa thức. Bài 8 : Viết chương trình nhập vào một xâu ký tự, xếp chúng vào một danh sách liên kết, dùng phím $ để báo hết xâu. Duyệt qua danh sách và in danh sách theo thứ tự đảo ngược lại lúc nhập. Bài 9 : Viết chương trình nhập vào một chuỗi dấu ngoặc và kiểm tra xem chuỗi dấu ngoặc đó đúng hay sai theo quan điểm toán học. Bài 10 : Một danh sách liên kết các ký tự được tạo ra bằng cách dùng mảng như sau: 49
50. Phân tích thiết kế thuật toán Bài 11 : Hình dưới đây biểu diễn một mảng Space gồm có 10 phần tử , dùng để diễn tả danh sách bằng con nháy vad 2 danh sách L1, L2 đã có trong mảng : Bài 12 : Ðể tiện việc truy nhập vào danh sách, người ta tổ chức một danh sách liên kết có dạng như hình vẽ sau : Gọi là danh sách liên kết vòng. Hãy cài đặt một danh sách nối kết vòng như vậy. 50
51. Phân tích thiết kế thuật toán BÀI 3 : CÁC CẤU TRÚC DỮ LIỆU CƠ BẢN Mã bài : ITPRG3_12.3 Giới thiệu Khi xây dựng các thuật toán ta thường sử dụng một số cấu trúc dữ liệu như cây, tập hợp, đồ thị Tầm quan trọng của các cấu trúc dữ liệu đã được N. Wirth khẳng định bởi một công thức rất nổi tiếng : Data Structures + Algorithms = Programs. Việc nắm vững và vận dụng linh hoạt các cấu trúc dữ liệu sẽ giúp ích cho chúng ta rất nhiều khi xây phân tích, chọn lựa và xây dựng các thuật toán cũng như khi viết mã chương trình. Mục tiêu thực hiện Học xong bài này học viên sẽ có khả năng: Hiểu được cấu trúc dữ liệu chồng, hàng đợi, cây, tập hợp, đồ thị, bảng băm. Sử dụng các cấu trúc dữ liệu trên để giải quyết một số bài toán. Chọn cấu trúc dữ liệu thích hợp để giải quyết bài toán của mình. Nêu ra lợi thế của việc sử dụng các cấu trúc dữ liệu cơ bản khi xây dựng giải thuật để giải quyết các bài toán nào đó. .10. Cấu trúc cây .10.1 Định nghĩa và các khái niệm cơ bản .10.1.a Ðịnh nghĩa Cây (Trees) là một tập hợp hữu hạn các phần tử gọi là nút cây (Node), trong đó có một nút đặc biệt gọi là nút gốc (Root). Trên tập hợp các nút này có một quan hệ phân cấp gọi là quan hệ "cha - con". Một nút có thể có kiểu bất ký, ta thường biểu diễn nút bằng tên nút. Tên nút có thể là một ký tự, một số hay một chuỗi và có thể được ghi trong một vòng tròn. Ta quy ước biểu diễn cây như sau: Ta viết nút cha ở dòng trên, các nút con ở dòng dưới và quan hệ "cha-con" được biểu diễn bằng một đoạn thẳng nối liền 2 nút. Ví dụ : 51
52. Phân tích thiết kế thuật toán Ngoài ra ta có thể định nghĩa cây một cách đệ qui như sau : Một nút (đơn độc) là một cây và nút đó cũng là nút gốc của cây. Nếu ta có n là một nút và T1, T2, , Tk là các cây với n1, n2, , nk lần lượt là các nút gốc của các cây con thì ta có thể xây dựng một cây mới bằng cách cho n trở thành cha của các nút n1, n2, , nk; Nghĩa là trên cây mới này n là nút gốc còn các cây T1, T2, , Tk là các cây con của nút n. Ðể tiện việc quản lý, người ta cho phép tồn tại một cây không có nút nào, mà ta gọi là cây rỗng (Null tree). .10.1.b Các khái niệm cơ bản Một nút đơn độc cũng là một cây. Tập hợp rỗng cũng là một cây mà ta gọi là cây rỗng. Mức của một nút : Nút gốc : Mức 0. Các nút cách nút gốc i cạnh được gọi là nút ở mức i. 52
53. Phân tích thiết kế thuật toán Ví dụ: Cha - con: Nút A là nút cha của nút B khi nút A ở mức i và nút B ở mức i+1. Ðồng thời có một cạnh nối giữa cặp nút A và B (ta còn gọi B là con của A). Cha - ông (con - cháu)/ tiền bối - hậu duệ: Nếu có một đường nối từ nút A đến nút B và mức của nút A < mức của nút B thì ta nói A là cha ông (tiền bối) của B và B gọi là con cháu (hậu duệ) của A. Anh em ruột: Các nút con của cùng một nút cha được gọi là các nút anh em ruột. i Ðường đi: Cho một dãy các nút n1, n2, , nk sao cho n là nút cha của ni+1 thì ta nói n1 n2 nk là một đường đi từ nút n1 nk. Ðộ dài của đường đi bằng số nút trên đường đi trừ 1 hay bằng số cạnh trên đường đi. Nút gốc (Root): Là nút không có nút cha. Nút lá (leaf): Là nút không có nút con. Chiều cao của một nút: Là độ dài đường đi từ nút đó đến nút lá xa nhất. Ðộ sâu của một nút (mức của một nút): Là chiều dài đường đi từ nút gốc đến nút đó. Chiều cao của một cây: Là chiều cao của nút gốc. Bậc của một nút: Là số nút con của nút đó. Bậc của một cây: Là bậc cao nhất của các nút trong cây. Cây có bậc n được gọi là cây n - phân. Rừng là một tập hợp hữu hạn các cây phân biệt. 53
54. Phân tích thiết kế thuật toán Nếu ta phân biệt thứ tự các nút con của một cây thì ta gọi cây đó là cây có thứ tự. Ngược lại là cây không có thứ tự. Thứ tự của các nút trong một cây có thứ tự được quy ước từ trái sang phải và từ trên xuống dưới. Nếu A và B là 2 nút anh em ruột và A ở bên trái của B thì các nút con cháu của A là nút bên trái tất cả các nút con cháu của B. Ðể xác định nút trái (phải) của một nút n, ta vẽ một đường đi từ nút gốc đến nút n. Nút nào nằm bên trái của đường đi thì sẽ là nút trái của nút đó, nút nào nằm bên phải của đường đi thì sẽ là nút phải của nút đó. Ví dụ: Thứ tự duyệt cây: Duyệt cây là một quy tắc xử lý lần lượt tất cả các nút của một cây mà ở đó mỗi nút chỉ được xử lý một lần. Danh sách liệt kê các nút theo thứ tự xử lý được gọi là danh sách duyệt cây. .10.1.c Các phép duyệt cây quan trọng Duyệt tiền tự (PreOrder). Duyệt trung tự (InOrder). Duyệt hậu tự (PostOder). Ðịnh nghĩa các phép duyệt cây: Ta có thể định nghĩa phép duyệt cây tổng quát bằng đệ quy như sau : Cây rỗng : Danh sách duyệt tiền tự, trung tự, hậu tự là danh sách rỗng. 54
55. Phân tích thiết kế thuật toán Cây có một nút : Danh sách duyệt tiền tự, trung tự, hậu tự chính là nút đó. Ví dụ : Cho một cây như hình sau : .10.1.d Cây có nhản và cây biểu thức Ta thường lưu trữ kết hợp một nhản (Label) hoặc một giá trị (value) với một nút của cây. Như vậy, nhản của một nút không phải là tên của nút mà là giá trị được lưu tại nút đó. Nhản của một nút còn được gọi là khóa của nút. Ví dụ : Cây sau đây sẽ biểu diễn cho biểu thức (a + b) * (a - c) 55
56. Phân tích thiết kế thuật toán Trong cây trên thì n1, n2, , n7 là các tên nút còn *, +, -, a, b, c là các nhản của nút. .10.1.e Quy tắc biểu diễn một biểu thức toán học trên cây Mỗi nút lá sẽ biểu diễn cho một toán hạng đơn độc. Mỗi nút trung gian sẽ biểu diễn cho một toán tử. Giả sử nút n biểu diễn cho toán tử 2 ngôi, nút con bên trái biểu diễn cho biểu thức E1, nút con bên phải biểu diễn cho biểu thức E2 thì nút n sẽ biểu diễn cho biểu thức Eı E2 Thông thường khi chúng ta duyệt cây thì danh sách duyệt cây là một danh sách các nhản nút. Trong trường hợp cây biểu diễn cho biểu thức toán học thì biểu thức duyệt tiền tự cho chúng ta biểu thức tiền tố (Prefix), duyệt trung tự cho chúng ta biểu thức trung tố (Infix) và duyệt hậu tự cho chúng ta biểu thức hậu tố (Postfix) của biểu thức toán học ban đầu. Ví dụ: Ðối với cây biểu thức được cho ở ví dụ trên, ta có: Biểu thức tiền tố : * + a b - a c. Biểu thức trung tố : a + b * a - c. Biểu thức hậu tố : a b + a c - *. .10.2 Kiểu dữ liệu trừu tượng cây .10.2.a Các phép toán trên cây Hàm Parent (n : Node; T : Tree) : Cho kết quả nút cha của nút n trên cây T. Nếu n là nút gốc thì hàm cho kết quả là Null. Hàm RightSibling (n : Node; T : Tree) : Cho kết quả là nút anh ruột phải của nút n trên cây T. Nếu n không có anh ruột phải thì hàm cho kết quả là Null. Hàm LeftMostChild (n : Node; T : Tree) : Cho kết quả là nút con trái nhất của nút n trên cây T. Nếu n không có con trái nhất thì hàm cho kết quả là Null. Hàm Root (T : Tree) : Cho kết quả là nút gốc của cây T. Nếu cây rỗng thì hàm cho kết quả là Null. Thủ tục Createi (V, T1, T2, , Ti) : Là thủ tục tạo cây mới có nhản gốc là V và i cây con T1, T2, , Ti. Nếu i = 0 thì cây mới tạo chỉ có một nút đơn độc. Hàm LabelNode(n : Node; T : Tree) : Cho nhản của nút n của cây T. Ví dụ : Dùng các phép toán trên để viết các thủ tục duyệt cây : 56
57. Phân tích thiết kế thuật toán Procedure PreOrder (T : Tree); Var n, c : Node; Begin n := Root (T); Write (LabelNode (n, T); c := LeftMostChild (n, T); While c Null do Begin PreOrder (c, T); c := RightSibling (c, T); End; End; Procedure InOrder (T : Tree); Var n, c : Node; Begin n := Root (T); c := LeftMostChild (n, T); While c Null do Begin PreOrder (c, T); Write (LabelNode (n, T); c := RightSibling (c, T); End; End; Procedure PostOrder (T : Tree); Var n, c : Node; Begin n := Root (T); c := LeftMostChild (n, T); While c Null do Begin PostOrder (c, T); c := RightSibling (c, T); Write (LabelNode (n, T); End; End; .10.2.b Cài đặt cây a. Cài đặt cây bằng mảng 57
58. Phân tích thiết kế thuật toán Cho một cây T có các nút 1, 2, 3, , n. Ta có thể dùng mảng A 1 chiều để lưu trữ cây bằng cách cho A[i] = j. Với j là nút cha của nút i. Nếu i là nút gốc thì ta cho A[i] = Null. (Cụ thể là Null = 0). Ví dụ : Cây : Ðược biểu diễn trong mảng A như sau : Nếu cây T có nhản ta có thể dùng thêm một mảng L chứa các nhản của cây. Bằng cách cho L[i] = x, với x là nhản của nút i, hoặc khai báo mảng A là mảng của các Record gồm có 2 trường : Trường Parent giữ chỉ số của nút cha; trường Labels giữ nhản của nút. Khai báo : Const Maxlenght = ; Type ElementType = {Kiểu nhản} ; Tree = Record Parent: Array [1 Maxlenght] of Integer; Labels: Array [1 Maxlenght] of ElementType; End; Var T:Tree; NumNode: Integer; { Số nút tối đa trên cây } Với cách cài đặt này hàm Parent chỉ tốn một hằng thời gian nhưng các hàm khác thì rất khó cài đặt. Để khắc phục tình trạng này người ta quy ước việc đặt tên nút như sau : Ðánh số theo thứ tự tăng dần bắt đầu từ nút gốc. Tại mỗi nút thì nút cha được đánh số trước rồi lần lượt đến các nút con từ trái sang phải. b. Biểu diễn cây bằng danh sách các con 58
59. Phân tích thiết kế thuật toán Một cách biểu diễn khác cũng thường được dùng là biểu diễn cây dưới dạng mỗi nút có một danh sách các nút con. Danh sách có thể được cài đặt bằng bất kỳ cách nào mà ta đã biết. Tuy nhiên, vì số lượng các nút con của một nút là không biết trước nên cài đặt bằng danh sách liên kết sẽ thích hợp hơn. Ví dụ : Cây ở ví dụ trước có thể được lưu trữ theo dạng : Nhận xét : Các hàm tìm kiếm thông tin về các con rất thuận lợi, nhưng hàm parent lại bất tiện. Ví dụ như cần tìm nút cha của nút 8 thì ta phải duyệt qua tất cả các danh sách mới tìm ra kết quả. c. Biểu diễn cây bằng con trái nhất và anh ruột phải : Các cấu trúc đã dùng để biểu diễn cây có nhược điểm là khó có thể tạo cây mới từ các cây con bởi vì mỗi cây con được chứa trong một mảng riêng. Vì vậy, nếu muốn thiết lập một cấu trúc dữ liệu trợ giúp tốt cho phép tạo cây thì tất cả các nút của các cây phải được chứa trong cùng một mảng. Ta có thể tổ chức mảng có các phần tử là một Record gồm có 3 trường : 59
60. Phân tích thiết kế thuật toán Trường Labels : giữ nhản của nút. Trường LeftMostChild : Giữ chỉ số của nút con trái nhất. Trường RightSibling : giữ chỉ số của nút anh ruột phải. Với cấu trúc này các hàm đều được thực hiện dễ dàng trừ hàm Parent. Nếu muốn cải tiến ta có thể tổ chức thêm một trường thứ tư giữ chỉ số của nút cha. Khai báo : Const MaxNode = ; { Ðộ dài mảng } Type LabelType = ; { Kiểu nhản } Var Cellspace : array [ 1 MaxNode ] of Record Labels : LabelType; LeftMostChild : Integer; RightSibling : Integer; Parent : Integer; End; Availble : Integer; Thủ tục khởi tạo vùng lưu trữ các nút tự do : Procedure Initialize; Var i : Integer; Begin For i :=1 to MaxNode - 1 do Cellspace [i].RightSibling := i + 1; Cellspace [MaxNode].RightSibling := 0; Available : = 1; End; Thủ tục khởi tạo cây rỗng : Procedure MakeNullTree (Var T : Integer); Begin T := Null; {0} End; Hàm tìm nút cha của một nút : Function Parent (n : Integer; T : Integer) : Integer; Begin Parent := Cellspace[n]. Parent; End; 60
61. Phân tích thiết kế thuật toán Hàm tìm nút con trái nhất của một nút : Function LeftMostchild (n : Integer; T : Integer) : Integer; Begin LeftMostChild := Cellspace[n]. LeftMostChild; End; Hàm tìm nút anh ruột phải của một nút : Function RightSibling (n : Integer; T : Integer) : Integer; Begin Rightsibling := Cellspace[n]. rightsibling; End; Thủ tục tạo cây mới từ 2 cây con : Procedure Create2 (V : LabelType; T1, T2 : Integer) : Integer; Var Temp : Integer; Begin Temp := Available; Available := Cellspace[Available].Rightsibling; Cellspace [Temp].LeftMostChild := T1; Cellspace [Temp].Labels := V; Cellspace [Temp].Rightsibling := 0; Cellspace [Temp].Parent := 0; Cellspace [T1]. Rightsibling := T2; Create2 := Temp; { Nút gốc mới } End; .10.3 Cây nhị phân (Binary Tree) .10.3.a Ðịnh nghĩa Cây nhị phân là một cây mà trong đó mỗi nút chỉ có tối đa 2 nút con (2 nhánh) 61
62. Phân tích thiết kế thuật toán Trong một cây nhị phân ta cần phân biệt con trái (leftchild) và con phải (rightchild) của một nút. Ta quy ước vẽ nút con trái ở bên trái nút cha và nút con phải ở bên phải nút cha. Ví dụ: Nếu ta xem (a), (b) là cây và là cây có thứ tự thì 2 cây này chỉ là một. Nếu nói là cây nhị phân thì đây là 2 cây khác nhau. Một số dạng đặc biệt của cây nhị phân : Cây lệch trái : Các nút trên cây chỉ có con trái không có con phải. Cây lệch phải : Các nút trên cây chỉ có con phải không có con trái. Cây zic-zắc: Là cây mà nếu nút ở mức i chỉ có một con (phải hoặc trái) thì nút ở mức i+1 cũng chỉ có 1 con (phải hoặc trái). Cây nhị phân đầy đủ: Là cây nhị phân mà các nút đều có đủ 2 con trái và phải (trừ nút lá). 62
63. Phân tích thiết kế thuật toán .10.3.b Tính chất .10.3.c Cài đặt cây nhị phân 63
64. Phân tích thiết kế thuật toán Cách cài đặt này sẽ rất phí miền nhớ khi cây nhị phân là một cây có dạng đặc biệt cây lệch trái, cây lệch phải, cây zic-zắc, và chỉ thích hợp với cây nhị phân đầy đủ. Khai báo : Const Maxlenght = ; Type LabelType = ; Node = Record LeftChild : Integer; RightChild : Integer; Label : LabelType; End; Tree = array [1 Maxlenght ] of Node ; b. Cài đặt cây nhị phân bằng con trỏ : Trong cách cài đặt này mỗi nút sẽ là một record gồm có 3 trường : Left : con trỏ giữ địa chỉ của nút con trái. Right : con trỏ giữ địa chỉ của nút con phải. Info : Lưu trữ nhản (nội dung) của nút. Left Info Right Khai báo : Type ElementType = ; Tree = ^ Node ; Node = Record Elements : ElementType; Left : Tree ; Right : Tree ; End; Thủ tục khởi tạo cây rỗng : Ðể có thể truy cập đến các nút trên cây, ta cần có một con trỏ T để trỏ đến nút gốc của cây đó. Khi cây rỗng thì con trỏ sẽ trỏ đến một giá trị đặt biệt Nil. Procedure MakeNullTree(VarT : Integer); Begin T := Nil; End; 64
65. Phân tích thiết kế thuật toán Hàm tạo cây : Function MakeTree (x : ElementType ; L, R : Tree) : Tree; Var T : Tree ; Begin New (T) ; T.^Elements := x; T. Left := L; T. Right := R; MakeTree := T; End; Hàm xác định chiều cao của cây Function HighTree (T : Tree) : Integer ; Function Max (a, b : Integer) : Integer; Begin If a < b then Max := b Else Max := a ; End; Begin { High tree } If T = Nil then HighTree := 0 Else If (T^.Left = Nil) and (T^.Right = Nil) then HighTree := 0 Else HighTree:=Max(HighTree(T^.Left),HighTree(T^.Right)+1; End; Hàm xác định chiều cao của cây Function NumNode (T : Tree) : Integer ; Begin If T = Nil then NumNode := 0 65
66. Phân tích thiết kế thuật toán Else NumNode := (NumNode(T^.Left), NumNode (T^.Right) + 1; End; Duyệt cây nhị phân Duyệt tiền tự : (NLR) Procedure PreOrder (T : Tree); Begin If T Nil then Begin Write (T^.Elements); PreOrder (T^.Left); PreOrder (T^.Right); End; End; Duyệt trung tự : (LNR) Procedure InOrder (T : Tree); Begin If T Nil then Begin InOrder (T^.Left); Write (T^.Elements); InOrder (T^.Right); End; End; Duyệt hậu tự : (LNR) Procedure PostOrder (T : Tree); Begin If T Nil then Begin PostOrder (T^.Left); PostOrder (T^.Right); Write (T^.Elements); End; End; Hàm tính trị của một biểu thức Cây biểu thức là cây nhị phân trong đó các nút trung gian sẽ chứa các toán tử, còn các lá sẽ chứa các toán hạng. 66
67. Phân tích thiết kế thuật toán Khi thực hiện tính giá trị của một cây biểu thức, ta sẽ tính theo đúng thứ tự của phép duyệt cây trung tự. Function Value(T : Tree) : Real; Var x : Real; Code : integer; Begin If (T^.Left = Nil) and (T^.Right = Nil) then Begin Val (T^.Elements, x , Code); Value := x; End Else Begin If T^.Elements = '+' then Value:= Value (T^.Left) + Value (T^.Right); If T^.Elements = '-' then Value:= Value (T^.Left) - Value (T^.Right); If T^.Elements = '*' then Value:= Value (T^.Left) *Value (T^.Right); If T^.Elements = '/' then If Value(T^.Right) 0 then Value:=Value(T^.Left) / Value(T^.Right) Else Write('Loi chia cho 0 '); End; End; .10.4 Thuật toán mã hóa Huffman .10.4.a Ðặt vấn đề Giả sử ta có một thông báo là một chuỗi các ký tự, trong đó mỗi ký tự xuất hiện độc lập với cùng một xác suất tại bất kỳ vị trí nào trong thông báo. Yêu cầu đặt ra là mã hóa thông báo này thành một chuỗi các ký tự 0, 1. Ta sẽ mã hóa mỗi ký tự trong chuỗi thông báo đã cho, sao cho: Không có ký tự nào được mã hóa thành chuỗi là tiền tố của chuỗi mã hóa ký tự khác (tính chất này được gọi là tính chất tiền tố). Ðộ dài của bộ mã là ngắn nhất. 67
68. Phân tích thiết kế thuật toán Có cách mã hóa nào cho độ dài mã trung bình < 2.2 được hay không? Một kỹ thuật cho lời giải tối ưu gọi là thuật toán Huffman. .10.4.b Thuật toán mã hóa Huffman Chọn 2 nút a, b có xác suất nhỏ nhất trong tập hợp các nút (giả sử xác suất của a làĠ xác suất của b) rồi thay 2 nút này bằng một nút mới là x, có xác suất bằng tổng xác suất của 2 nút. Rồi sau đó lặp lại một cách đệ quy quá trình trên cho tập hợp nút mới (gồm x và các nút còn lại). Mã của a, b sẽ tìm được bằng cách lấy mã của x nối thêm 0 cho a và 1 cho b. Như vậy, thực chất của quá trình trên là ta xây dựng một cây nhị phân từ tập hợp các ký tự muốn mã hóa, cuối cùng ta được một cây nhị phân có lá là các ký tự đó. Mã của một ký tự là 1 đường đi trên cây từ gốc đến lá chứa các ký tự đó, với 0 đi sang trái và 1 đi sang phải. 68
69. Phân tích thiết kế thuật toán .10.5 Cây tìm kiếm nhị phân .10.5.a Ðịnh nghĩa Cây tìm kiếm nhị phân là cây nhị phân mà nhản tại mỗi nút của cây lớn hơn nhản của tất cả các nút thuộc cây con bên trái và nhỏ hơn nhản của tất cả các nút thuộc cây con bên phải. Ví dụ : 69
70. Phân tích thiết kế thuật toán Như vậy, khi duyệt trung tự (InOrder) cây tìm kiếm nhị phân ta được một dãy có thứ tự tăng. Hơn nữa trên cây tìm kiếm nhị phân không có 2 nút nào có cùng một nhản. Chẳng hạn duyệt trung tự cây của ví dụ trên ta được dãy 5, 7, 10, 12, 14, 15, 18. .10.5.b Cài đặt cây tìm kiếm nhị phân Một cách cài đặt cây tìm kiếm nhị phân thường gặp là cài đặt bằng con trỏ. Mỗi nút của cây là một Record gồm 3 trường: một trường chứa nội dung của nút (chứa nhản), hai trường kia là hai con trỏ đến hai nút con (nếu nút con vắng mặt ta cho nó trỏ đến Nil). Khai báo : Type ElementType = ; Tree = ^ Node ; Node = Record Elements : ElementType; Left : Tree ; Right : Tree ; End; Thủ tục khởi tạo cây rỗng : Procedure MakeNullTree(Var T : Integer); Begin T := Nil; { Nút gốc trỏ đến Nil } End; Thủ tục xen một nút vào cây tìm kiếm nhị phân : Nếu nút đã có trên cây thì không xen. Nếu nút có nhản là x lớn hơn nhản của nút gốc thì ta tìm chỗ xen ở cây con bên phải. Nếu nút có nhản là x nhỏ hơn nhản của nút gốc thì ta tìm chỗ xen ở cây con bên trái. Procedure InsertTree(x: ElementType; Var T : Integer); 70
71. Phân tích thiết kế thuật toán Begin If T = Nil then Begin New (T); T^.Elements:=x; T^.Left:=Nil; T^.Right:=Nil; End Else If x T^.Elements then InsertTree (x, T^.Right) Else Writeln (‘ x co roi ’); End; Thủ tục xóa một nút trên cây tìm kiếm nhị phân : Giả sử ta muốn xóa một nút có nhản là x, ta tiến hành tìm kiếm trên cây bắt đầu từ nút gốc: nếu nhản x lớn hơn nhản của nút gốc thì ta tìm sang cây con bên phải, ngược lại thì ta sẽ tìm sang cây con bên trái. Nếu không tìm thấy thì giả thuật kết thúc. Nếu tìm gặp thì có 3 trường hợp sau : Nếu x là lá thì ta thay x bằng Nil. Nếu x chỉ có một nút con thì ta thay x bằng nút con của nó. Nếu x có 2 con thì ta thay x bằng nút lớn nhất trên cây con bên trái (nút cực phải của cây trái) hoặc nút bé nhất trên cây con bên phải của x (nút cực trái của cây phải). Trong thuật toán ta sẽ thay bằng nút cực trái của cây con bên phải. Function DeleteMin (Var T: Tree) : ElementsType; Var Temp : Tree; Begin If T^.Left = Nil then Begin DeleteMin:= T^.Elements; T:= T^.Right; End Else DeleteMin:= DeleteMin (T^.Left); End; Procedure DeleteTree (x: ElementsType; Var T : Integer); Begin 71
72. Phân tích thiết kế thuật toán If T Nil then If x > T^.Elements then DeleteTree (x, T^.Right) Else If x < T^.Elements then DeleteTree (x, T^.Left) Else { Ðúng nút cần xóa} If (T^.Left = Nil) and (T^.Right = Nil) then T:= Nil Else If T^.Right = Nil then T:= T^.Left Else If T^.Left = Nil then T:= T^.Right Else T^.Elements:= DeleteMin(T^.Right); End; .11. Kiểu dữ liệu tập hợp .11.1 Kiểu dữ liệu trừu tượng tập hợp .11.1.a Khái niệm Tập hợp là một sự hợp thành của các phần tử có cùng kiểu. .11.1.b Các phép toán cơ bản trên tập hợp Thủ tục Union (A, B : SetType; Var C : SetType) : thực hiện phép hợp của 2 tập hợp A, B và được kết quả là tập hợp C. Thủ tục Intersection (A, B : SetType; Var C : SetType) : thực hiện phép giao của 2 tập hợp A, B và được kết quả là tập hợp C. Thủ tục Diffirence (A, B : SetType; Var C : SetType) : thực hiện phép trừ của 2 tập hợp A, B và được kết quả là tập hợp C. Hàm Member (x : ElementType; A : SetType) : Boolean : Hàm kiểm tra thành phần cho kết quả là True nếu xĠ A và ngược lại. Thủ tục MakeNullSet (Var A : SetType) : Khởi tạo một tập hợp A rỗng. Thủ tục InsertSet (x: ElementType; Var A : SetType) : Xen phần tử x vào tập hợp A . Thủ tục DeleteSet (x: ElementType; Var A : SetType) : Xóa phần tử x khỏi tập hợp A . 72
73. Phân tích thiết kế thuật toán Thủ tục Assign (A : SetType; Var B : SetType) : Gán tập hợp A cho tập hợp B. .11.1.c Cài đặt tập hợp a. Cài đặt bằng vectơ bit : Sự cài đặt tập hợp tốt nhất phụ thuộc vào các phép toán và kích thước của tập hợp. Khi toàn thể tập hợp là một tập con của một tập số nguyên nằm trong khoảng từ 1 đến N thì ta có thể dùng một mảng (gọi là vectơ bit) có n phần tử để cài đặt tập hợp bằng cách cho phần tử thứ i của mảng này giá trị True nếu i thuộc vào tập hợp và False nếu ngược lại. Ví dụ : A = { 1, 3, 5, 8 } và điều kiện là tất cả các tập hợp mà ta xét tới đều có các thành viên nằm trong phạm vi từ 1 đến 10. Thì ta có thể biểu diễn tập hợp A trong mảng có 10 phần tử như sau : 1 2 3 4 5 6 7 8 9 10 T F T F T F F T F F Khai báo : Const Max = ; { Số phần tử tối đa của tập hợp } Type SetType = Array [ 1 Max ] of Boolean ; ElementType = Integer; Thủ tục khởi tạo tập hợp rỗng : Procedure MakeSet(Var A : SetType); Var i : Integer; Begin For i := 1 to Max do A[i ]:= False; End; Thủ tục hợp hai tập hợp : Procedure Union (A, B : SetType; Var C : SetType); Var i : Integer; Begin MakeNullSet (C); For i := 1 to Max do C[i ]:= A[i] or B[i]; End; Thủ tục giao hai tập hợp : Procedure Intersection (A, B : SetType; Var C : SetType); Var i : Integer; Begin MakeNullSet (C); For i := 1 to Max do 73
74. Phân tích thiết kế thuật toán C[i]:= A[i] and B[i]; End; Thủ tục hiệu hai tập hợp : Procedure Difference (A, B : SetType; Var C : SetType); Var i : Integer; Begin MakeNullSet (C); For i := 1 to Max do C[i ]:= A[i] and (not B[i]); End; Hàm kiểm tra thành phần : Function Member (x : Elementype; A : SetType) : Boolean; Var i : Integer; Begin For i := 1 to Max do If x = A[i] then Member:= True else Member:= False; End; Phép gán tập hợp A cho tập hợp B. Ta lần lượt gán từng phần tử trong tập hợp A cho tập hợp B. Procedure Assign (A : SetType; Var B : SetType); Var i : Integer; Begin MakeNullSet (B); For i := 1 to Max do B[i ]:= A[i]; End; Phép xen một phần tử vào tập hợp : Procedure InsertSet(x : ElementType; Var A : SetType); Begin If x>Max then Writeln(‘Loi!khong the xen ‘ ,x, ‘ vao tap hop‘) Else Begin If Member (x, A) then Writeln (x,’ da co trong tap hop ‘) Else A[x]:= True; End; End; Phép xóa một phần tử khỏi tập hợp : 74
75. Phân tích thiết kế thuật toán Procedure DeleteSet(x : ElementType; Var A : SetType); Begin If (x > Max) or (Not Member(x,A)) then Writeln (‘ Loi ! ‘ ,x, ‘ khong co trong tap hop ‘) Else A[x]:= False; End; b. Cài đặt bằng danh sách liên kết : Tập hợp cũng có thể được cài đặt bằng danh sách liên kết. Trong đó mỗi phần tử của danh sách là một thành viên của tập hợp. Không như sự biểu diễn bằng vectơ bit, sự biểu diễn này dùng kích thước bộ nhớ tỷ lệ với số phần tử trong tập hợp chứ không phải là kích thước đủ lớn cho toàn thể tập hợp đang xét. Hơn nữa ta có thể biểu diễn cho một tập hợp bất kỳ. Mặt dù thứ tự của các phần tử trong tập hợp là không quan trọng. Nhưng nếu một danh sách liên kết là có thứ tự nó sẽ trợ giúp tốt cho phép duyệt danh sách. Chẳng hạn nếu tập hợp A được biểu diễn bằng một danh sách có thứ tự tăng thì hàm Member (x,A) có thể thực hiện so sánh x tuần tự từ đầu cho đến khi gặp phần tử Źx, chứ không cần so sánh với tất cả các phần tử trong tập hợp. Khai báo : Type ElementType = ; { Kiểu phần tử trong tập hợp } SetType = CellType; CellType = Record Elements : ElementType; Next : CellType; End; Thủ tục khởi tạo tập hợp rỗng : Procedure MakeSet (Var A : SetType); Begin New (A); A^. Next := Nil; End; Hàm kiểm tra thành phần : Function Member (x : Elementype; A : SetType) : Boolean; Var p : SetType; Found : Boolean; Begin 75
76. Phân tích thiết kế thuật toán p := A^.Next; Found := False; While (p Nil) and (Not Found) do If p^.Elements = x then Found := True Else p:= p^.Next; Member := Found; End; Phép giao của 2 tập hợp Procedure InterSettion (A, B : SetType; Var C : SetType); Var i, j, k : SetType; Found : Boolean; Begin MakeNullSet (C); i := A^.Next; While (i Nil) do Begin j:= B^.Next; Found := False; While (j Nil) and (Not Found) do If j^.Elements=i^.Elements then Found := True Else j:= j^.Next; If Found then Begin New (k); k^.Elements := i^.Elements; k^.Next := C^.Next; C^.Next := k; i := i^.Next; End; { While } End; Phép hợp của 2 tập hợp Procedure Union (A, B : SetType; Var C : SetType); Var i, j, k : SetType; Begin MakeNullSet (C); i := A^.Next; While (i Nil) do Begin New (k); k^.Elements := i^. Elements; 76
77. Phân tích thiết kế thuật toán k^.Next := C^.Next; C^.Next := k; i := i^.Next; End; J:= B^.Next; While j Nil do Begin New (k); k^.Elements := j^. Elements; k^.Next := C^.Next; C^.Next := k; j := j^.Next; End; End; .11.2 Tự điển .11.2.a Ðịnh nghĩa Tự điển là một kiểu dữ liệu trừu tượng ADT trên mô hình tập hợp với 3 phép toán Insert, Delete và Member. Ta bổ sung thêm phép toán MakeNullDictionary để khởi tạo tự điển rỗng. .11.2.b Cài đặt tự điển đơn giản Một tự điển có thể được cài đặt bằng một danh sách được sắp thứ tự hoặc chưa sắp thứ tự. Có thể cài đặt tự điển bằng vectơ bit với giả thiết rằng các phần tử của tập hợp bị giới hạn trong một khoảng từ 1 đến n nào đó. Một cách cài đặt khác là dùng mảng (giống như danh sách đặc). Cách cài đặt này chỉ có thể áp dụng nếu chúng ta biết chắc rằng tập hợp không bao giờ có số phần tử vượt quá độ dài của mảng. Khai báo : Const Maxlenght = ; { số phần tử tối đa của tự điển } Type ElementType = ; { Kiểu phần tử trong tự điển } Dictionary = Record Data : Array [1 maxlenght] of ElementType; Last : Integer; End; Thủ tục khởi tạo tự điển rỗng : Procedure MakeNullDictonary (Var D : Dictionary); Begin D.Last := 0; End; Hàm kiểm tra phần tử : 77
78. Phân tích thiết kế thuật toán Function Member (x : ElementType; D : Dictionary) : Boolean; Var i: Integer; Found: Boolean; Begin i: = 1; Found:= False; While (i 1 then Begin i := 1; While (i x) do i := i + 1; If D.Data [i] = x then Begin D.Data [i] := D.Data [D.Last]; D.Last := D.Last -1; End; 78
79. Phân tích thiết kế thuật toán End; End; .11.3 Cấu trúc bảng băm (HASH TABLE) .11.3.a Giới thiệu Cài đặt tự điển bằng mảng tốn O(n) bước để thực hiện các phép toán xen, xóa, hoặc kiểm tra phần tử trên một tự điển có n phần tử. Cài đặt bằng danh sách liên kết cũng có cùng tốc độ này. Cài đặt bằng vectơ bit chỉ tốn một hằng thời gian cho cả ba phép toán, nhưng ta lại bị giới hạn trong một phạm vi nhỏ của tập hợp số nguyên. Có một kỹ thuật khác rất quan trọng và được sử dụng rộng rãi để cài đặt tự điển đó là băm. Băm (Hashing) là một phương pháp tính toán trực tiếp vị trí của mảng lưu trữ phần tử của tập hợp dựa vào giá trị của phần tử này (ta còn gọi là khóa). Giả sử ta có một mảng gồm B phần tử được đánh số từ 0 đến B-1 và một tập hợp A muốn lưu trữ vào trong mảng này. Như vậy với mỗi phần tử ŸA ta sẽ dựa vào giá trị khóa của nó để suy ra một số nguyên trong khoảng từ 0 đến B-1 là vị trí cất giữ khóa này. Hay nói cách khác là ta chọn một hàm : h : A 0 B -1 x Ġ h (x) là vị trí của khóa x trong mảng B. Như vậy khi cần tìm một phần tử x, ta chỉ cần tính h(x); h(x) được gọi là giá trị băm của khóa x và hàm h được gọi là hàm băm. Nói chung là sẽ có nhiều khóa có cùng giá trị băm. Tức là với 2 khóa x, y khác nhau nhưng ta lại có h(x) = h(y). Trường hợp này được gọi là đụng độ. Như vậy để sử dụng phương pháp băm ta cần chọn hàm h sao cho ít xảy ra đuụng độ nhất. Hơn nưa ta phải có cách giải quyết khi đụng độ xảy ra. Mảng được dùng trong phương pháp băm được gọi là bảng băm. Ví dụ : Hàm h dưới đây biến đổi một chỗi ký tự thành số nguyên thuộc 0 B-1 Const B = ; Type Index = 0 B - 1 ; ElementType = String [10] ; {Ví dụ minh họa cho hàm băm trên} Function h (x : ElementType) : Index ; Var i, sum : Integer ; Begin Sum := 0 ; For i:=1 to Length(x) do 79
80. Phân tích thiết kế thuật toán Sum := Sum + Ord[x] ; h := Sum mod B ; End; B = 11 h (‘Windows’) = 10; h (‘QUATTRO’) = 10 ; h (‘EXCEL’) = 6; h (‘VENTURA’) = 10 ; h (‘FOXPRO’) = 5 ; .11.3.b Bảng băm mở (Open Hash Table) Ý tưởng đơn giản để giải quyết đụng độ là tạo một danh sách cho các phần tử có cùng giá trị băm. Nếu bảng băm có B phần tử được đánh số từ 0 đến B-1 và hàm h là hàm băm thì tại phần tử k của mảng là một danh sách các phần tử có cùng giá trị băm là k. Mỗi một danh sách như vậy được gọi là một lớp hay là một Bucket. Danh sách có thể được tổ chức theo bất kỳ cách nào mà chúng ta đã biết. Nhưng số sỗ phần tử trong mỗi lớp là không xác định trước nên cài đặc lớp bằng danh sách liên kết sẽ thích hợp nhất. Nếu hàm băm rải đều các khóa thì trung bình ta có N/B phần tử trong mỗi lớp (với N là số phần tử có trong tự điển và B là số phần tử của bảng băm). Như vậy thời gian để thực hiện các phép toán xen, xóa hoặc kiểm tra thành phần sẽ là O(1+ N/B). Nếu ta chọn N và B thích hợp sao cho N/B là nhỏ thì các phép toán trên bảng băm chỉ mất một hằng thời gian độc lập với N và B. Ta nhận thấy rằng mỗi lớp sẽ có số phần tử không nhiều. Vì vậy, nếu ta dùng B phần tử của bảng băm làm B chỉ điểm đầu của danh sách sẽ gây lãng phí bộ nhớ rất lớn. Vì vậy phần tử đầu của mỗi lớp ta đặt ngay vào trong mảng. Khai báo : 80
81. Phân tích thiết kế thuật toán Const B = ; { số phần tử của bảng băm } Type ElementType = ; { Kiểu phần tử trong tự điển } Index = 0 B-1 ; Elementss = ^ Cell ; Cell = Record Data : ElementType; Next : Elements; End; OHT = array [ 0 B-1] of Elements ; Thủ tục khởi tạo OHT rỗng : Procedure MakeNullOHT (Var D : OHT); Var i : Integer ; Begin For i := 0 to B -1 do D[i] := Nil ; End; Hàm kiểm tra phần tử : Function Member (x : ElementType; D : OHT) : Boolean; Var p: Elements; Found: Boolean; Begin Found:= False; p := D[H(x)] ; { H(x) là hàm băm tự chọn } While (p <> Nil) and (Not Found) do If p^.Data = x then Found:= True Else p := p^.Next ; Member:= Found; End; Thủ tục xen một phần tử vào OHT : Procedure InsertOHT(x:ElementType; Var D:OHT); Var Bucket : Index ; t : Elements ; Begin If Not Member (x, D) then Begin Bucket : = h(x) ; 81
82. Phân tích thiết kế thuật toán New (t) ; t^.Data := x ; t^.Next := D[Bucket] ; D[Bucket] := t ; End Else Writeln (‘ Phan tu da ton tai ‘); End; Thủ tục xóa một phần tử khỏi OHT : Procedure DeleteOHT (x: ElementType; Var D : OHT); Var Bucket : Index ; t, p : Elements ; Found : Boolean ; Begin Bucket : = h(x) ; p := D[Bucket] ; If p x } Begin t := p ; p := p^.Next ; Found := False ; While (p <> Nil) and (Not Found) do If p^.Data = x then Begin Found:= True ; t^.Next := p^.Next ; Dispose (p) ; End ; Else Begin t := p ; p := p^.Next ; End; End ; { Else } End; 82
83. Phân tích thiết kế thuật toán .11.3.c Bảng băm đóng (Close Hash Table) Bảng băm đóng lưu giữ các phần tử ngay trong mảng chứ không dùng mảng làm các chỉ điểm đầu. Ô thứ i của mảng chứa phần tử có giá trị băm là i. Nhưng có thể có nhiều phần tử có cùng giá trị băm nên ta thường gặp trường hợp ta muốn đưa vào ô thứ i một phần tử nhưng ô này đã bị chiếm bởi phần tử y nào đó. Như vậy, khi thiết kế một bảng băm đóng ta phải có cách để giải quyết sự đụng độ này. Cách giải quyết đụng độ được gọi là chiến lược băm lại. Chiến lược băm lại là chọn lần lượt các vị trí h1, h2, , hk cho đến khi gặp một vị trí trống để đặt x vào. Dãy h1, h2, , hk được gọi là dãy các phép thử. Một chiến lược đơn giản là băm lại tuyến tính, trong đó dãy các phần tử có dạng : hi(x) = (h(x) + i) mod B Ví dụ : Giả sử B = 8 và các phần tử của tự điển là : a, b, c, d có các giá trị băm lần lượt là 3, 0, 4, 3. Ta muốn đưa các phần tử này vào bảng băm. ta không xóa bất kỳ phần tử nào trong bảng băm. Nếu ta chấp nhận phép xóa thì ta quy ước rằng phần tử bị xóa được thay bằng một giá trị đặc biệt là Deleted, giá trị này cũng không bằng với bất kỳ phần tử nào trong bảng băm kể cả Empty. Ví dụ : Tìm kiếm phần tử e trong bảng băm. Giả sử h(e) = 4, ta tiến hành tìm kiếm tại các vị trí 4, 5, 6. Vị trí 6 chứa empty vậy ta kết luận rằng không có phần tử e trong bảng băm. Tìm kiếm phần tử d trong bảng băm. Giả sử h(d) = 3, ta tiến hành tìm kiếm từ vị trí này và duyệt qua các ô 4, 5 thì tìm thấy d. Giả sử tự điển là một tập hợp của các chuuõi có độ dài là 10 ký tự. Ta có thể quy ước rằng Empty là một chuỗi 10 dấu + và deleteted là một chuỗi gồm 10 dấu * . Giả sử hàm băm h(x) được lấy là hàm băm cho ở ví dụ trước. Khai báo : 83
84. Phân tích thiết kế thuật toán Const B = ; { số phần tử của bảng băm } Type ElementType = String [10] ; { Kiểu phần tử trong tự điển } Index = 0 B-1 ; Empty = ‘ + + + + + + + + + + ’ ; Deleteted = ‘ * * * * * * * * * * ’ ; Dictionary = array [ 0 B-1] of ElementsType ; Thủ tục khởi tạo tự điển rỗng : Procedure MakeNullDictionary (Var D : Dictionary); Var i : Integer ; Begin For i := 0 to B -1 do D[i] := Empty ; End; Hàm kiểm tra phần tử : Function Member (x : ElementType; D : Dictionary) : Boolean; Var start, i: Integer; Begin Start := h(x) ; i := 0 ; While (i x) and (D[start+i] mod B x) and (D[start+i] mod B Deleted) do i := i + 1 ; If (D[start+i] mod B Deleted) then D[start + i] mod B := x Else Writeln (‘ x da ton tai hoac mang day ‘) ; 84
85. Phân tích thiết kế thuật toán End ; Thủ tục xóa một phần tử khỏi tự điển : Procedure DeleteDictionary (x: ElementType; Var D : Dictionary); Var start, i: Integer; Begin Start := h(x) ; i := 0 ; While (i x) and (D[start + i] mod B <> Empty) do i := i + 1 ; If (D[start + i] mod B = x) then D[start + i] mod B := Deleteted Else Writeln (‘ x khong co trong tu dien ‘); End ; .11.3.d Ước lượng hiệu quả hàm băm Thời gian thực hiện các phép toán trên bảng băm là O(1+N/B), điều này xảy ra khi hàm băm rải đều các khóa, liệu một hàm băm như vậy có tồn tại hay không ? Ta thấy việc thiết kế hàm băm dựa trên các tính toán số học để cho ra kết quả ngẫu nhiên. Một hàm băm càng ngẫu nhiên càng rãi đều các phần tử. Mặt khác, hàm băm phải đơn giản vì nếu hàm băm quá phức tạp thì thời gian để băm một khóa là lớn làm ảnh hưởng chung đến hiệu quả của phương pháp. Các phương pháp thiết kế hàm băm thường gặp là: a. Phương pháp chia : Hàm băm có dạng H(x) = x Mod B Phương pháp này rõ ràng là đơn giản nhưng nó có thể cho kết quả không ngẫu nhiên lắm. Chẳng hạn nếu B = 103 thì H(x) chỉ phụ thuộc vào 3 số cuối cùng của khóa mà không phụ thuộc vào các số đứng trước. Kết quả sẽ ngẫu nhiên hơn nếu ta chọn B là số nguyên tố. b. Phương pháp nhân : Lấy 1 khóa nhân với chính nó rồi lấy một số chữ số giữa làm kết quả cho hàm băm. Ví dụ : 85
86. Phân tích thiết kế thuật toán c. Phương pháp phân đoạn : Ðối với các khóa dài và kích thước thay đổi người ta thường dùng phương pháp phân đoạn. Tức là phân khóa thành các đoạn bằng nhau từ một đầu (trừ đoạn đầu cuối). Nói chung các đoạn có độ dài bằng độ dài kết quả của hàm băm. Phân đoạn có thể là tách hoặc gấp. * Tách : Khóa 17046329 được tách thành 071 | 064 | 329 => 071 + 064 + 329 = 392. Sau đó lấy 392 Mod 1000 = 392 là kết quả của khóa. * Gấp : Tương tự như gấp giấy. Như 17046329 gấp 2 mép vào ta được: 923 + 046 + 710 = 1679 => 1679 Mod 1000 = 679. .11.3.e Phân tích bảng băm đóng a. Hiện tượng gôm tụ : Trong bảng băm đóng thời gian thực hiện các phép toán không chỉ phụ thuộc vào sự phân phối của hàm băm mà còn phụ thuộc vào chiến lược băm lại khi giải quyết đụng độ. Chiến lược băm lại có thể làm nảy sinh hiện tượng gôm tụ. Ví dụ : Xét bảng băm có 10 vị trí (B=10) với chiến lược thử tuyến tính và các khóa có giá trị băm như sau : h(H) = 3 - Vị trí này đã bị chiếm, ta thử sang các vị trí 4, 5, 6, 7, 8 và đưa H vào vị trí 8. h(I) = 6 - Vị trí này đã bị chiếm, ta thử sang các vị trí 7, 8, 9 và đưa I vào vị trí 9. 86
87. Phân tích thiết kế thuật toán Rõ ràng là hàm băm của chúng ta cũng tương đối tốt, các trường hợp đụng độ như C, D được giải quyết nhanh chóng. Nhưng việc băm lại phải mất thời gian khá lâu với các khóa H, I để so sánh chúng với các khóa không có cùng giá trị băm. b. Chiến lược băm lại : Như đã phân tích ở trên, chiến lược giải quyết đụng độ như phép thử tuyến tính sẽ nảy sinh hiện tượng gôm tụ làm ảnh hưởng chung đến hiệu quả của phương pháp. Ta biết rằng dãy các phép thử được chọn trong phép thử tuyến tính là : hi(x) = [h(x) + i] mod B. Tổng quát : hi(x) = [h(x) + G(i)] mod B với G(i) = i. Vì G(i) = i làm cho mỗi lần thử ta chỉ thử sang một ô kế tiếp do đó, các phần tử bị gom tụ lại. Muốn khắc phục tình trạng này ta chọn G(i) sao cho có thể chọn được các vị trí xa hơn. Ví dụ : Nếu ta dùng G (i) = C.i, với C>1. Chẳng hạn B = 8, C = 3, H(x) = 4 thì các phép thử của chúng ta sẽ thực hiện lần lượt tại các vị trí 4, 7, 2, 5, 0, 3, 6 và 1. Nếu B và C có ước số chung lớn hơn 1 thì chiến lược này sẽ không thành công vì ta không thể duyệt qua tất cả các ô để tìm vị trí trống. Chẳng hạn: B = 8, C = 2, H(x) = 4 thì ta chỉ có thể duyệt qua các ô chẳn. Chiến lược chọn G(i) = i2 được gọi là phép thử cầu phương. Hi = (H(x) + i2) Mod B c. Xây dựng lại hàm băm : Nếu ta dùng bảng băm mở thì thời gian trung bình phải mất cho các phép toán là N/B. Tỷ số này sẽ lớn nếu N >> B. Nếu ta dùng bảng băm đóng thì thời gian trung bình cho các phép toán tăng lên khá nhanh khi bảng băm gần đầy (N/B -> 1). Ðể khắc phục nhược điểm đó ta có thể xây dựng bảng băm mới có kích thước lớn hơn kích thước của bảng băm cũ rồi đưa các phần tử của bảng băm cũ vào bảng băm mới. .11.4 Hàng ưu tiên .11.4.a Khái niệm về hàng ưu tiên Ðây là một kiểu dữ liệu trừu tượng dựa trên mô hình nền là tập hợp cùng với các phép toán xen (Isnert) và xóa phần tử bé nhất (DeleteMin). Ta cũng bổ sung thêm phép toán MakeNull để khởi tạo cấu trúc rỗng. Ðể xác định phép toán mới DeleteMin ta giả thiết rằng các phần tử trong tập hợp đang xét tương ứng với các phần tử của một tập hợp có thứ tự tuyến tính. Nói cách khác là có một hàm P cho tương ứng một phần tử a trong tập hợp đang xét với một phần tử P(a) thuộc tập hợp có thứ tự tuyến tính. P(a) được gọi là độ ưu tiên của a. Phép toán DeleteMin sẽ cho ra kết quả là phần tử có độ ưu tiên bé nhất trong tập hợp và xóa nó ra khỏi tập hợp này. 87
88. Phân tích thiết kế thuật toán .11.4.b Cài đặt hàng ưu tiên Ta có thể cài đặt hàng ưu tiên bằng danh sách liên kết, danh sách liên kết có thể có hoặc không có thứ tự. Ta không thể cài đặt hàng ưu tiên bằng bảng băm vì bảng băm không thuận tiện cho việc tìm kiếm phần tử bé nhất. Một cách cài đặt hàng ưu tiên thuận lợi là cài đặt bằng cây có thứ tự từng phần. .11.4.c Cài đặt hàng ưu tiên bằng cây có thứ tự từng phần Ý tưởng cơ bản là tổ chức các phần tử của hàng ưu tiên dưới dạng một cây nhị phân và cố gắng là cây nhị phân cân bằng có thể được. Tại mức thấp nhất của cây có thể có một số lá rỗng, nhưng ta quy ước rằng các lá rỗng phải xuất hiện bên phải các lá thật sự. Ðiều quan trọng nhất là cây phải có thứ tự từng phần theo nghĩa độ ưu tiên của một nút nhỏ hơn hoặc bằng độ ưu tiên của nút con của nó. Ví dụ như cây sau: Thực hiện DeleteMin Ðể thực hiện DeleteMin ta chỉ cần trả ra nút gốc của cây và loại bỏ nút này. Tuy nhiên, nếu loại bỏ nút này ta cần xây dựng lại cây với yêu cầu là cây phải có thứ tự từng phần và cân bằng. Chiến lược xây dựng lại cây như sau : Lấy nút lá thật sự tại mức cao nhất và là nút lá bên phải nhất lên thay thế nút gốc. Như thế có thể cây không bảo đảm thứ tự từng phần. Tiếp đó, ta sẽ đẩy nút này xuống dưới tức là đổi chỗ nút với nút con bé nhất của nó nếu nút con này có độ ưu tiên nhỏ hơn nó. Hơn nữa quá trình này diễn ra không quá log2n + 1 bước. Ví dụ : Xóa nút gốc có khóa 3 trong cây có ví dụ trên 88
89. Phân tích thiết kế thuật toán Thực hiện Insert: Xen nút x = 4 vào thay thế lá rỗng bên trái nhất thì ta được cây như sau : .11.4.d Cài đặt cây có thứ tự toàn phần bằng mảng Trong thực tế, cây có thứ tự từng phần thường được cài đặt bằng mảng (gọi là Heap). Nếu cây có n nút, ta chứa n nút này vào n ô đầu của một mảng A nào đó. A[1] chứa nút gốc của cây. Nút A[i] sẽ có con trái là A[2*i] và con phải là A[2*i +1] 89
90. Phân tích thiết kế thuật toán Ví dụ : Heap có 11 phần tử như cây sau : Nói một cách khác, nút cha của nút A[i] là A[i div 2] với i > 1. Như vậy cây được xây dựng lớn dần lên từ mức này đến mức khác bắt đầu từ đỉnh (gốc) và tại mỗi mức cây phát triển từ trái sang phải. Khai báo : Const Maxlenght = ; { số phần tử của mảng } Type ElementType = ; { Kiểu phần tử } PriorityQueue = Record Elements = array [ 1 Maxlenght] of ElementType ; Last : Integer ; End ; Thủ tục khởi tạo hàng ưu tiên rỗng : Procedure MakeNullPriorityQueue (Var A : PriorityQueue); Begin A.Last := 0; End; Thủ tục xen một phần tử vào cây có thứ tự từng phần : Procedure InsertPriorityQueue(x:ElementType;Var A:PriorityQueue); Var i : Integer ; Temp : ElementType ; Begin If A.Last > Maxlenght then Writeln (‘ Mang day ‘) Else Begin A.Last := A.Last + 1; A.Elements [A.Last] := x; 90
91. Phân tích thiết kế thuật toán i := A. Last ; { Cho phần tử mới nổi dần lên } While (i>1) and (p(A.Elements[i]) p(A.Elements[j ]) then Begin Temp := A.Elements[i] ; A.Elements[i] : = A.Elements[j] ; A.Elements[j] := Temp ; i := j ; 91
92. Phân tích thiết kế thuật toán End { If } Else Done := True ; End ; {While } End ; { Else } DeleteMin := Min ; End ; .12. Đồ thị Trong nhiều bài toán của khoa học máy tính, toán học, kỹ thuật và nhiều ngành khoa học khác, chúng ta đôi khi cần biểu diễn mối quan hệ của các đối tượng. Một mô hình thích hợp cho việc biểu diễn như vậy là đồ thị (Graph).Trong chương này chúng ta sẽ tìm hiểu các thuật toán thường gặp trên đồ thị cũng như các cấu trúc dữ liệu cơ bản thường dùng để biểu diễn đồ thị trên máy tính. .12.1 Các định nghĩa Người ta thường dùng ký hiệu G = (V, E) để ký hiệu cho đồ thị G có tập hợp các đỉnh là V (còn được gọi là các nút - node hay các điểm - point) và một tập hợp các cung nối giữa một số đỉnh gọi là tập cạnh E. Hai đỉnh có cung nối được gọi là 2 đỉnh kề nhau, cạnh nối 2 đỉnh trùng nhau được gọi là khuyên, đỉnh không được nối bởi 1 cạnh nào cả được gọi là đỉnh đơn độc. Một cung nối giữa 2 đỉnh i, j có thể coi là một cặp điểm (i, j). Nếu cặp này có thứ tự thì ta có cung có thứ tự, ngược lại thì cung không có thứ tự. Nếu tập các cung của đồ thị G có thứ tự thì G được gọi là đồ thị có hướng (Directed Graph). Nếu tập các cung của đồ thị G không có thứ tự thì G được gọi là đồ thị vô hướng (Undirected Graph). Trong các phần sau ta sẽ dùng thuật ngữ đồ thị (Graph) để chỉ đồ thị nói chung, khi nào cần phân biệt ta sẽ nói rõ đồ thị có hướng hay vô hướng. Các hình vẽ dưới đây chỉ đồ thị vô hướng (hình a) và đồ thị có hướng (hình b) : trong các đồ thị này các đỉnh được biểu diễn bằng các vòng tròn có ghi tên đỉnh, các cạnh được biểu diễn bằng các đoạn thẳng có hướng (đồ thị có hướng) và không có hướng (đồ thị vô hướng) và có một tên gọi. 92
93. Phân tích thiết kế thuật toán Thông thường trong một đồ thị, các đỉnh sẽ biểu diễn cho các đối tượng còn các cung thì biễu diễn cho các quan hệ giữa các đối tượng đó. Chẳng hạn các đỉnh có thể biễu diễn cho các thành phố còn các cạnh sẽ biễu diễn cho các đường giao thông giữa 2 thành phố. Ðường đi gọi là đơn giản nếu mọi đỉnh trên đường đi đều khác nhau, ngoại trừ đỉnh đầu và đỉnh cuối có thể trùng nhau. Một đường đi có đỉnh đầu và đỉnh cuối trùng nhau được gọi là một chu trình (cycle). Một chu trình đơn là một đường đi đơn có đỉnh đầu trùng với đỉnh cuối và có độ dài ít nhất là 1. Trong nhiều ứng dụng ta thường kết hợp các giá trị (value) hay nhãn (label) với các đỉnh và / hoặc các cạnh của đồ thị, khi ấy ta gọi là đồ thị có nhãn. Nhãn kết hợp với các đỉnh và / hoặc cạnh có thể biễu diễn tên, giá của đường đi, khoảng cách, Nói chung nhãn có thể có kiểu tùy ý. Hình dưới đây cho ví dụ về đồ thị có nhãn là các số nguyên biểu diễn cho cước phí vận chuyển của một đơn vị hàng hóa giữa các thành phố. Trong một đồ thị các đỉnh có thể có tên và có một nhãn. Trong trường hợp không phân biệt rõ thì tên hay nhãn của một đỉnh là không quan trọng, ta có thể nói 1 là tên của đỉnh 1 hay là nhãn của đỉnh này. 93