Giáo trình Cấu trúc dữ liệu và giải thuật 1
Một mục tiêu quan trọng của tin học là nhằm giải quyết tự động những bài
toán trong thế giới thực bằng máy tính điện tử. Các thông tin về bài toán cần giải
quyết trên máy tính luôn được mã hoá dưới dạng nhị phân. Các thông tin này gồm
dữ liệu và các thao tác trên các dữ liệu đó.
Việc biểu diễn dữ liệu ở dạng nhị phân rất bất tiện cho con người trong khi
xử lý các bài toán, đặc biệt là các bài toán lớn và phức tạp. Chính vì lý do đó, các
ngôn ngữ lập trình bậc cao đã cung cấp sẵn các cách biểu diễn dữ liệu trừu tượng
đơn giản và có cấu trúc, nhằm giúp người lập trình không phải mất nhiều thời
gian và công sức thực hiện thường xuyên lặp lại các thao tác sơ cấp nặng nề trên
các kiểu dữ liệu nhị phân ở mức thấp. Tính trừu tượng của dữ liệu thể hiện ở chỗ
nó không quá chú trọng đến những đặc điểm và ý nghĩa riêng của từng đối tượng
cụ thể mà chỉ rút ra và phản ánh những tính chất chung nhất mà các đối tượng
thuộc cùng một lớp có được.
Tóm tắt nội dung tài liệu: Giáo trình Cấu trúc dữ liệu và giải thuật 1
![Giáo trình Cấu trúc dữ liệu và giải thuật 1 Giáo trình Cấu trúc dữ liệu và giải thuật 1](https://s1.tailieubachkhoa.net/rl6k7x3q9zfh00j8/thumb/2021/11/25/giao-trinh-cau-truc-du-lieu-va-giai-thuat-1_No6R17hmMf.jpg)
TRÖÔØNG ÑAÏI HOÏC ÑAØ LAÏT KHOA TOAÙN - TIN HOÏC Y Z TRÖÔNG CHÍ TÍN CAÁU TRUÙC DÖÕ LIEÄU VAØ GIAÛI THUAÄT 1 (Giaùo Trình) -- Löu haønh noäi boä -- Y Ñaø Laït 2008 Z LỜI MỞ ĐẦU Giáo trình này nhằm cung cấp cho sinh viên các kiến thức căn bản về các cấu trúc dữ liệu cơ sở có cấu trúc tuyến tính tĩnh, động (danh sách liên kết), cấu trúc cây và các giải thuật cơ bản liên quan đến chúng như sắp xếp, tìm kiếm ở bộ nhớ trong, cũng như so sánh độ phức tạp của các giải thuật này. Để có thể nắm bắt các kiến thức trình bày học phần này, sinh viên cần nắm được các kiến thức về tin học đại cương, nhập môn lập trình. Ngôn ngữ lập trình được chọn để minh họa các kiến thức trên là C++. Các kiến thức này sẽ tạo điều kiện cho học viên tiếp tục dễ dàng nắm bắt các kiến thức các học phần tin học về sau như: cấu trúc dữ liệu và giải thuật nâng cao, phân tích và thiết kế giải thuật, đồ hoạ, hệ điều hành, trí tuệ nhân tạo, ... Nội dung giáo trình gồm 4 chương: - Chương 1: Giới thiệu các khái niệm ban đầu về mối liên hệ mật thiết giữa cấu trúc dữ liệu và giải thuật, kiểu dữ liệu, thiết kế và phân tích giải thuật, độ phức tạp giải thuật, ... - Chương 2: Giới thiệu các phương pháp cơ bản về tìm kiếm và sắp xếp trong trên kiểu dữ liệu tuyến tính mảng. Thông qua đó, trình bày một số ý tưởng và kỹ thuật cơ bản nhằm cải tiến các giải thuật. - Chương 3: Trình bày kiểu dữ liệu con trỏ. Trên cơ sở đó, trình bày các kiểu dữ liệu động tuyến tính và có nhiều ứng dụng trong tin học là các kiểu danh sách liên kết khác nhau, ngăn xếp, hàng đợi, cũng như một số ứng dụng của chúng. - Chương 4: Giới thiệu một loại cấu trúc dữ liệu động khác là cây và các thao tác cơ bản trên cây nhị phân, cây nhị phân tìm kiếm, cây cân bằng AVL. Nhằm mục đích dành thời gian nhiều hơn cho sinh viên để làm các bài tập lớn, nên trong một số phần tác giả đã trình bày khá chi tiết các dạng cài đặt biến thể khác nhau cho các giải thuật. Các phần thứ yếu hoặc khá phức tạp sẽ được in cỡ chữ nhỏ dành cho sinh viên đọc thêm. Chắn chắn rằng trong giáo trình sẽ còn nhiều khiếm khuyết, tác giả mong muốn nhận được và rất biết ơn các ý kiến quí báu đóng góp của đồng nghiệp cũng như bạn đọc để giáo trình này có thể hoàn thiện hơn nữa về mặt nội dung cũng như hình thức trong lần tái bản sau. Đà lạt, 04/2008 Tác giả MỤC LỤC Chương I. GIỚI THIỆU CẤU TRÚC DỮ LIỆU, PHÂN TÍCH GIẢI THUẬT Trang I.1. Quan hệ giữa cấu trúc dữ liệu và giải thuật, kiểu dữ liệu I.1 I.1.1. Biểu diễn dữ liệu I.1 I.1.2. Quan hệ giữa cấu trúc dữ liệu và giải thuật, kiểu dữ liệu I.1 I.1.3. Các bước chính để giải một bài toán trên máy tính I.2 I.2. Thiết kế và phân tích giải thuật I.4 I.2.1. Thiết kế giải thuật theo phương pháp Top-Down I.4 I.2.2. Các chiến lược khác để thiết kế giải thuật I.5 I.2.3. Phân tích giải thuật và độ phức tạp của giải thuật I.5 I.2.4. Qui ước về ngôn ngữ mã giả I.9 Chương II. TÌM KIẾM VÀ SẮP XẾP TRONG II.1. Giới thiệu về sắp xếp và tìm kiếm II.1 II.1.1. Sắp xếp II.1 a. Định nghĩa sắp xếp II.1 b. Phân loại phương pháp sắp xếp II.1 c. Vài qui uớc về kiểu dữ liệu khi xét các giải thuật sắp xếp II.1 II.1.2. Tìm kiếm II.3 a. Định nghĩa phép tìm kiếm II.3 b. Phân loại các phương pháp tìm kiếm II.3 II.2. Phương pháp tìm kiếm trong II.3 II.2.1. Phương pháp tìm kiếm tuyến tính II.3 a. Dãy chưa được sắp II.3 b. Dãy đã được sắp II.5 II.2.2. Phương pháp tìm kiếm nhị phân II.6 II.3. Phương pháp sắp xếp trong II.7 II.3.1. Phương pháp sắp xếp chọn đơn giản II.8 II.3.2. Phương pháp sắp xếp chèn đơn giản II.9 II.3.3. Phương pháp sắp xếp đổi chỗ đơn giản II.10 II.3.4. Phương pháp sắp xếp đổi chỗ cải tiến (Shake Sort) II.12 II.3.5. Phương pháp sắp xếp chèn cải tiến (Shell Sort) II.14 II.3.6. Phương pháp sắp xếp phân hoạch (Quick Sort) II.16 II.3.7. Phương pháp sắp xếp trên cây có thứ tự (HeapSort) II.19 II.3.8. Phương pháp sắp xếp trộn (Merge Sort) II.25 II.3.9. Phương pháp sắp xếp dựa trên cơ số (Radix Sort) II.28 II.3.10. So sánh các phương pháp sắp xếp trong II.31 Trang Chương III. CẤU TRÚC DANH SÁCH LIÊN KẾT III.1. Giới thiệu đối tượng dữ liệu con trỏ III.1 III.1.1. So sánh cấu trúc dữ liệu tĩnh và cấu trúc dữ liệu động III.1 III.1.2. Kiểu dữ liệu con trỏ III.1 a. Định nghĩa III.1 b. Khai báo III.2 c. Các thao tác trên kiểu dữ liệu con trỏ III.3 III.1.3. Biến động III.4 a. Đặc trưng của biến động III.4 b. Truy xuất biến động III.4 c. Hai thao tác cơ bản trên biến động III.5 III.2. Danh sách liên kết (DSLK) III.7 III.2.1. Định nghĩa danh sách III.7 III.2.2. Các cách tổ chức danh sách III.7 III.3. DSLK đơn III.8 III.3.1. Tổ chức DSLK đơn, các thao tác cơ bản, tìm kiếm và sắp xếp trên kiểu DSLK đơn III.8 a. Tổ chức DSLK đơn (không có nút câm) III.8 b. Các thao tác cơ bản trên kiểu DSLK đơn III.9 c. Sắp xếp trên kiểu DSLK đơn: sắp xếp chèn, QuickSort, MergeSort, RadixSort III.17 III.3.2. Vài ứng dụng của DSLK đơn III.24 III.3.2.1. Ngăn xếp: định nghĩa, cài đặt, các phép toán cơ bản và ứng dụng của ngăn xếp III.24 III.3.2.2. Hàng đợi: định nghĩa, cài đặt, các phép toán cơ bản và ứng dụng của hàng đợi III.31 III.4. Một số kiểu DSLK khác III.34 III.4.1. DSLK đơn có nút câm III.34 III.4.2. DSLK vòng III.37 III.4.3. DSLK đối xứng III.38 a. Cấu trúc dữ liệu biểu diễn DSLK đối xứng III.39 b. Các thao tác cơ bản trên kiểu DSLK đối xứng III.39 c. Ứng dụng của DSLK đối xứng: hàng đợi hai đầu III.47 III.4.4. DS đa liên kết III.48 III.4.5. Một số ứng dụng khác của DSLK III.51 a. DS có thứ tự và DS tổ chức lại III.51 b. Biểu diễn tập hợp bằng DSLK III.53 c. Biểu diễn đa thức rời rạc bằng DSLK III.54 d. Biểu diễn ma trận thưa nhờ DSLK III.56 e. Sắp xếp tôpô III.57 Trang Chương IV. CẤU TRÚC CÂY IV.1. Định nghĩa và các khái niệm cơ bản IV.1 IV.1.1. Định nghĩa cây IV.1 IV.1.2. Các khái niệm khác IV.1 IV.2. Cây nhị phân IV.3 IV.2.1. Định nghĩa IV.3 IV.2.2. Vài tính chất của cây nhị phân IV.3 IV.2.3. Biểu diễn cây nhị phân IV.3 IV.2.4. Duyệt cây nhị phân IV.4 IV.2.5. Một cách biểu diễn khác của cây nhị phân IV.7 IV.2.6. Biểu diễn cây n - phân bằng cây nhị phân IV.8 IV.2.7. Xây dựng cây nhị phân cân bằng hoàn toàn IV.8 IV.3. Cây nhị phân tìm kiếm IV.9 IV.3.1. Định nghĩa cây nhị phân tìm kiếm IV.9 IV.3.2. Tìm kiếm một phần tử trên cây BST IV.10 IV.3.3. Chèn một phần tử vào cây BST, xây dựng cây BST IV.11 IV.3.4. Phương pháp sắp xếp bằng cây BST IV.13 IV.3.5. Xóa một phần tử khỏi cây BST, hủy cây nhị phân IV.13 IV.4. Cây nhị phân tìm kiếm cân bằng IV.16 IV.4.1. Định nghĩa IV.17 IV.4.2. Chiều cao của cây cân bằng IV.17 IV.4.3. Chỉ số cân bằng và việc cân bằng lại cây AVL IV.18 IV.4.4. Chèn một phần tử vào cây AVL IV.24 IV.4.5. Xóa một phần tử khỏi cây AVL IV.25 Bài tập. BT.1 Bài tập chương I BT.1 Bài tập chương II BT.4 Bài tập chương III BT.6 Bài tập chương IV BT.11 Tài liệu tham khảo Chương I GIỚI THIỆU CẤU TRÚC DỮ LIỆU VÀ PHÂN TÍCH GIẢI THUẬT I.1. Quan hệ giữa cấu trúc dữ liệu và giải thuật, kiểu dữ liệu I.1.1. Biểu diễn dữ liệu Một mục tiêu quan trọng của tin học là nhằm giải quyết tự động những bài toán trong thế giới thực bằng máy tính điện tử. Các thông tin về bài toán cần giải quyết trên máy tính luôn được mã hoá dưới dạng nhị phân. Các thông tin này gồm dữ liệu và các thao tác trên các dữ liệu đó. Việc biểu diễn dữ liệu ở dạng nhị phân rất bất tiện cho con người trong khi xử lý các bài toán, đặc biệt là các bài toán lớn và phức tạp. Chính vì lý do đó, các ngôn ngữ lập trình bậc cao đã cung cấp sẵn các cách biểu diễn dữ liệu trừu tượng đơn giản và có cấu trúc, nhằm giúp người lập trình không phải mất nhiều thời gian và công sức thực hiện thường xuyên lặp lại các thao tác sơ cấp nặng nề trên các kiểu dữ liệu nhị phân ở mức thấp. Tính trừu tượng của dữ liệu thể hiện ở chỗ nó không quá chú trọng đến những đặc điểm và ý nghĩa riêng của từng đối tượng cụ thể mà chỉ rút ra và phản ánh những tính chất chung nhất mà các đối tượng thuộc cùng một lớp có được. I.1.2. Quan hệ giữa cấu trúc dữ liệu và giải thuật, kiểu dữ liệu Dựa vào bản chất chung của từng nhóm dữ liệu, các đối tượng dữ liệu được phân thành các lớp. Mỗi lớp dữ liệu được thể hiện qua một kiểu dữ liệu. Một kiểu dữ liệu T là một tập hợp nào đó, mỗi phần tử của tập được gọi là một thể hiện của kiểu. Ta đã biết giải thuật (hay giải thuật) là một dãy câu lệnh rõ ràng, xác định một trình tự các thao tác trên một số đối tượng nào đó (input) sao cho sau một số hữu hạn bước thực hiện (chú ý đến tính khả thi về thời gian), ta đạt được kết quả (output) mong muốn. Giải thuật phản ánh các phép xử lý, còn đối tượng để xử lý bởi giải thuật chính là dữ liệu: dữ liệu (input) đưa vào, dữ liệu trung gian và kết qủa (output) cuối cùng. Đối với bất kỳ một lớp dữ liệu nào, nếu để ý kỹ, ta thấy trên đó luôn tồn tại những thao tác cơ bản mật thiết gắn liền với các đối tượng dữ liệu cùng kiểu đó. Khi cách biểu diễn dữ liệu thay đổi thì các thao tác gắn liền với chúng cũng thay đổi theo. Vì nếu không thì trong nhiều trường hợp việc xử lý sẽ gượng ép, thiếu tự Giôùi thieäu caáu truùc döõ lieäu vaø phaân tích giaûi thuaät I.2 nhiên, khó hiểu, phức tạp không cần thiết và chương trình kém hiệu quả, lãng phí tài nguyên trên máy tính (CPU và bộ nhớ). Chẳng hạn, đối với một chuỗi ký tự, ta có ít nhất hai cách biểu diễn chúng như được thể hiện trong ngôn ngữ lập trình Pascal và C. Với mỗi cách biểu diễn, ta sẽ có những cách xây dựng các thao tác tương ứng trên chúng khác nhau. Một ví dụ khác, sẽ thấy rõ hơn trong các chương tiếp theo, đối với một dãy các phần tử dữ liệu cùng loại, ta có thể lưu trữ chúng ít nhất bằng hai cách: lưu bằng mảng (tĩnh, động) hay lưu trữ bằng danh sách liên kết động. Khi đó, các thao tác cơ bản trên chúng như chèn, xóa, sắp xếp sẽ thực hiện theo những cách thức khác nhau và do đó có hiệu quả khác nhau. Do đó, khi nói đến một kiểu dữ liệu T, ta thường chú ý đến hai đặc trưng quan trọng và liên hệ mật thiết với nhau: - tập V các giá trị thuộc kiểu, đó là tập các giá trị hợp lệ mà đối tượng kiểu T có thể nhận và lưu trữ; - tập O các phép toán (hay thao tác xử lý) xác định có thể thực hiện trên các đối tượng dữ liệu kiểu đó. Người ta thường viết: T = . Trong một ngôn ngữ lập trình cấp cao cụ thể, người ta thường xây dựng sẵn một số kiểu dữ liệu đơn giản hay sơ cấp xác định, chẳng hạn với C++, ta có các kiểu dữ liệu: số (nguyên, thực), ký tự, lôgic. Với kiểu số nguyên, các phép toán thường gặp là: các phép toán số học +, -, *, / (chia nguyên), % (mod, lấy phần dư) và các phép toán so sánh như: ==, !=, ≥, ≤, >, <. Với kiểu số thực, các phép toán thường gặp là: các phép toán số học +, -, *, /, và các phép toán so sánh như: ==, !=, ≥, ≤, >, <. Với kiểu lôgic, các phép toán thường gặp là: ! (not), && (and), || (or). Với kiểu ký tự, các phép toán thường gặp là: phép toán ép kiểu và các phép toán so sánh như: ==, !=, ≥, ≤, >, <, Dựa trên các kiểu đơn giản đã có và các phương pháp xác định của ngôn ngữ lập trình qui định, ta có thể xây dựng nên các cấu trúc dữ liệu hay kiểu dữ liệu có cấu trúc phức tạp hơn nhằm phản ánh tốt hơn các loại dữ liệu phong phú và đa dạng trong thế giới thực. Chẳng hạn như: kiểu mảng, kiểu cấu trúc, kiểu hợp, kiểu file, Một trong những phép toán cơ bản trên các kiểu dữ liệu đó là: truy cập đến từng phần tử hay từng thành phần của đối tượng dữ liệu. I.1.3. Các bước chính để giải một bài toán trên máy tính Để giải một bài toán trên máy tính, ta thường trải qua các giai đoạn chính sau đây: Giôùi thieäu caáu truùc döõ lieäu vaø phaân tích giaûi thuaät I.3 - Đặt bài toán, phân tích, đặc tả và mô hình hoá bài toán - Chọn cấu trúc dữ liệu để biểu diễn bài toán và phát triển giải thuật (chọn kiểu dữ liệu) - Mã hóa chương trình - Thử nghiệm chương trình - Bảo trì chương trình. Hai giai đoạn đầu rất quan trọng, nó góp phần quyết định tính đúng đắn và hiệu quả của chương trình nhằm giải bài toán. Vai trò của kiểu dữ liệu trong việc giải một bài toán trên máy tính Khi đề cập đến một thao tác, cần phải xác định nó tác động lên loại đối tượng hay trên cấu trúc dữ liệu hoặc trong kiểu dữ liệu nào? Với mỗi mô hình dữ liệu, có thể có nhiều cách cài đặt bởi các cấu trúc dữ liệu khác nhau. Trong mỗi cách cài đặt, có thể có một số phép toán được thực hiện thuận lợi, nhưng một số phép toán khác lại không thuận tiện. Khi đề cập đến một thao tác, cần phải xác định rõ nó tác động trên loại đối tượng hoặc kiểu dữ liệu nào? Khi cấu trúc dữ liệu thay đổi thì các giải thuật cơ bản tương ứng với nó cũng thay đổi theo. Vì vậy việc chọn cấu trúc dữ liệu nào để biểu diễn mô hình sẽ phụ thuộc vào từng ứng dụng cụ thể. Để việc chọn cấu trúc dữ liệu biểu diễn bài toán một cách phù hợp, cần chú ý đến những quan hệ giữa các đối tượng và thành phần dữ liệu với nhau; ngoài ra, ta còn cần phải lưu ý đến những phép toán cơ bản nào sẽ được thực hiện thường xuyên trên các đối tượng dữ liệu đó. Chẳng hạn, đối với một dãy các đối tượng dữ liệu cùng loại, nếu số lượng các đối tượng này không quá lớn (để có thể lưu ở bộ nhớ trong), biến động nhiều, hơn nữa các phép toán thêm và hủy các đối tượng xảy ra rất thường xuyên thì ta nên chọn kiểu dữ liệu là danh sách liên kết động hơn là kiểu mảng tĩnh để lưu trữ dãy đối tượng này. Khi xây dựng các giải thuật nhằm giải quyết một bài toán, ta phải dựa trên các yêu cầu cần xử lý để xem xét kỹ lưỡng, cũng như nên dựa trên các đặc trưng của bài toán và tài nguyên (tốc độ xử lý và khả năng lưu trữ của hệ thống máy tính) thực tế hiện có. Tóm lại, khi xây dựng các kiểu dữ liệu nhằm giải quyết một bài toán cụ thể, ta nên để ý các tiêu chuẩn sau: - Phản ánh đúng thực tế: có dự trù đến khả năng biến đổi của dữ liệu trong chu trình sống của nó. Đây là tiêu chuẩn rất quan trọng nhằm quyết định tính đúng đắn của toàn bộ bài toán. - Cấu trúc dữ liệu được xây dựng cần phù hợp với các thao tác trên đó (đặc biệt là các thao tác được sử dụng nhiều nhất). Khi đó, việc phát triển các giải thuật sẽ đơn giản, tự nhiên hơn và đạt hiệu quả cao về mặt tốc độ và bộ nhớ. Giôùi thieäu caáu truùc döõ lieäu vaø phaân tích giaûi thuaät I.4 - Tiết kiệm tài nguyên (tốc độ xử lý và dung lượng bộ nhớ): Đối với các giải thuật không quá tầm thường, hai yêu cầu này thường mâu thuẫn nhau và khó đạt được tối ưu đồng thời. Tùy theo yêu cầu của bài toán và tài nguyên thực tế, ta nên chọn giải thuật cho phù hợp. I.2. Thiết kế và phân tích giải thuật I.2.1. Thiết kế giải thuật theo phương pháp Top-Down Các bài toán giải được trên máy tính ngày càng đa dạng và phức tạp. Việc xây dựng mô hình cùng với các giải thuật và cách cài đặt các chương trình giải chúng ngày càng có quy mô lớn và phức tạp, thường đòi hỏi công sức đồng thời của cả một tập thể các nhóm phân tích - thiết kế viên cũng như các thảo chương viên. Mặt khác, việc thử nghiệm, sửa chữa, bổ sung, mở rộng, bảo trì các hệ chương trình lớn chiếm tỷ lệ thời gian đáng kể so với tổng thời gian xây dựng hệ chương trình. Để chương trì ... ++; while (x[ j] > y) j--; HoánVị(x[i], x[ j]); } while (i <= j); Có bộ dữ liệu x[0], x[1], , x[n-1] nào làm đoạn chương trình trên sai hay không ? Cho ví dụ minh họa. 8) Viết hàm đếm số đường chạy (tự nhiên) của một dãy gồm n phần tử cho trước. 9) Hãy cài đặt thêm thuật toán xuất bảng lương nhân viên (trong bài tập 1 - chương 1) theo thứ tự tiền lương tăng dần. 10) (*) Hãy viết lại giải thuật QuickSort dưới dạng lặp. 11) (*) Cải tiến hai thuật toán QuickSort viết dưới dạng đệ qui và lặp [gợi ý: ta nên thực hiện sắp xếp trước dãy con nào ngắn hơn]. 12) (*) Xây dựng ví dụ để trường hợp xấu nhất của thuật toán QuickSort xảy ra. Baøi taäp Caáu truùc döõ lieäu vaø Thuaät toùan 1 BT.6 Bài tập chương III (Cấu trúc danh sách liên kết) 1) Xét đoạn chương trình tạo một DSLK đơn có 4 nút (không quan tâm đến dữ liệu) sau đây: NodePointer p, Dx = NULL; p = Dx; Dx = new NodeType; for (i = 0; i < 4; i++) { p = p->Next; p = new NodeType; } p->Next = NULL; Đoạn chương trình này có thực hiện đúng như mục đích đã đưa ra không ? Tại sao ? Nếu không thì cần sửa lại như thế nào cho đúng ? 2) Hãy thực hiện các yêu cầu sau đối với từng loại danh sách liên kết: i) DSLK không có nút câm ii) DSLK có nút câm iii) DSLK vòng (không có nút câm) iv) DSLK đối xứng v) DSLK vòng đôi a. Tạo bản sao của một DSLK cho trước. b. Nối hai DSLK cho trước. c. Tính số lượng các nút dữ liệu. d. Tìm nút dữ liệu đầu tiên trong DSLK thỏa một tính chất nào đó, chẳng hạn: - nút thứ k, - hoặc có trường dữ liệu trùng với một giá trị cùng kiểu K cho trước. Nếu có thì trả về con trỏ chỉ đến nút đứng trước nút tìm thấy. e. Xóa một (hay mọi) nút dữ liệu trong DSLK thỏa một tính chất nào đó, ví dụ: - nút thứ k, - hoặc có trường dữ liệu trùng với một giá trị cùng kiểu K cho trước. f. Bổ sung một nút L vào sau một (hay mọi) nút dữ liệu trong DSLK thỏa một tính chất nào đó, chẳng hạn: - nút thứ k, - hoặc có trường dữ liệu trùng với một giá trị cùng kiểu K cho trước. g. Đảo ngược DSLK nói trên theo hai cách : tạo DSLK mới hay sửa lại chiều con trỏ trong DSLK ban đầu. h. Gọi M là con trỏ chỉ tới một nút đã có trong DSLK trên và P là con trỏ chỉ tới một DSLK khác cùng loại. Hãy chèn DSLK P này vào sau nút trỏ bởi M. i. Tách thành 2 DSLK mà DS sau được trỏ bởi M (giả thiết như câu h). j. So sánh 2 DSLK (có trường dữ liệu của các nút liên tiếp tương ứng bằng nhau hay không ?) Baøi taäp Caáu truùc döõ lieäu vaø Thuaät toùan 1 BT.7 3) Hãy viết chương trình nhằm thực hiện các yêu cầu của bài tập 1 – chương 1 (biết rằng số lượng nhân viên biến động nhiều, không dự đoán được giới hạn của nó) bằng cách dùng DSLK để cài đặt. 4) Hãy viết thuật toán và chương trình để trộn hai DSLK tăng A, B cho trước thành một DSLK C cũng tăng theo hai cách: a. C là DSLK mới (cấp phát bộ nhớ mới cho mọi nút của C) và bảo toàn hai DSLK cũ A, B; b. C là DSLK mới do A, B hợp thành (do đổi chỗ vị trí các con trỏ sẵn có trên A, B). Khi đó cấu trúc hai DSLK A, B có thể bị thay đổi. 5) Một số giới hạn vé (MAX_VE) cho buổi hòa nhạc sẽ được bán vào ngày mai. Người nào đăng ký trước sẽ được mua trước. Hãy viết một chương trình: a. Đọc các tên, tuổi của những người đăng ký cùng với số vé họ mua và lưu vào một DSLK (chú ý kiểm tra không có người nào được đăng ký nhiều lần). b. Hiện ra màn hình DSLK trên. 6) (Bài toán Josephus) Một nhóm binh sĩ bị kẻ thù bao vây và một binh sĩ được chọn để đi cầu cứu. Việc chọn được thực hiện theo cách sau đây. Một số nguyên n và một binh sĩ được chọn ngẫu nhiên. Các binh sĩ được sắp theo vòng tròn và họ đếm từ binh sĩ được chọn ngẫu nhiên. Khi đạt đến n, binh sĩ tương ứng được lấy ra khỏi vòng và việc đếm lại được bắt đầu từ binh sĩ tiếp theo. Quá trình này tiếp tục cho đến khi chỉ còn lại một binh sĩ là người gặp may (hoặc không may) được chọn để đi cầu cứu. Hãy viết một thuật toán cài đặt cách chọn này, dùng danh sách liên kết vòng để lưu trữ các tên của binh sĩ. (Ngăn xếp và hàng đợi) 7) Cho X là ngăn xếp chứa các ký tự. Giả sử có hàm sau trong C++: void Out(StackType &S, ElementType &Item) { Pop(S,Item); cout << Item<< endl; } Ta cần sử dụng luân phiên các phép toán Push(S, Item) và Out(S,Item) như thế nào (nếu có thể) từ bộ các ký tự : ‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’ để thu được các anagram (hoán vị) sau đây của nó: a) BDCFEA b) BDACEF c) ABCDEF d) EBFCDA e) FEDCBA 8) Xét một cơ cấu đường tàu và kho sửa chữa như hình sau: Giả sử ở đường vào có 4 đường tàu được đánh số 1, 2, 3, 4. Gọi V là phép đưa một đầu tàu vào kho sửa chữa, R là phép đưa một đầu tàu ra khỏi kho. a. Nếu thực hiện dãy VVRVVRRR thì thứ tự các đầu tàu lúc ra là gì ? (Có thể xem đây là một cách hoán vị các số được không ?) Baøi taäp Caáu truùc döõ lieäu vaø Thuaät toùan 1 BT.8 b. Xét trường hợp có 6 đầu tàu:1, 2, 3, 4, 5, 6 có thể thực hiện một dãy các phép V và R thế nào để đổi thứ tự đầu tàu ở đường ra là: 3, 2, 5, 6, 4, 1 ? và 1, 5, 4, 6, 2, 3 ? Ra Vào Kho sửa chữa 9) Xét chuỗi: EAS*Y**QUE***ST***I*ON Trong đó, mỗi chữ cái tượng trưng cho thao tác thêm nó vào một DSLK List, dấu * tượng trưng cho thao tác lấy nó ra khỏi List và xuất ra màn hình. Trong từng trường hợp sau, với List là: a. ngăn xếp b. hàng đợi hãy cho biết: - Nội dung của List sau mỗi thao tác cơ bản trên ? - Kết quả cuối cùng xuất ra trên màn hình ? - Hãy kiểm tra lại các kết quả trên bằng một chương trình hoàn chỉnh. 10) Viết các thao tác cơ bản trên ngăn xếp và thêm vào các thao tác sau đây: a. ElementType XemPTửThứ_2CủaNX(StackType S) có tác dụng xem phần tử thứ 2 kể từ đỉnh ngăn xếp S mà không làm S thay đổi. b. ElementType LấyPTửThứ_2CủaNX(StackType &S) có tác dụng trả về phần tử thứ 2 của ngăn xếp S và S bị mất đi 2 phần tử ở đỉnh của nó. c. ElementType LấyĐáyNX(StackType &S) có tác dụng trả về phần tử ở đáy ngăn xếp S và làm S trở thành rỗng. d. ElementType XemĐáyNX(StackType S) có tác dụng trả về phần tử ở đáy ngăn xếp S và S không thay đổi. 11) Để có thể duyệt ngăn xếp hay hàng đợi theo cả hai chiều, ta có thể tổ chức chúng theo kiểu DSLK đối xứng như sau: Top Bottom S A B C D Hãy thực hiện các phép toán sau trên ngăn xếp: a. Thực hiện phép duyệt qua DSLK từ dưới lên. Baøi taäp Caáu truùc döõ lieäu vaø Thuaät toùan 1 BT.9 b. Thực hiện phép duyệt qua DSLK từ trên xuống. c. Thực hiện phép bổ sung một phần tử vào (đầu và đuôi) DSLK. d. Thực hiện phép loại bỏ một phần tử (ở đầu và đuôi) khỏi DSLK. 12) a. Cho Q là hàng đợi rỗng. Cho biết kết quả của Q sau một dãy các phép toán thêm vào và lấy ra các ký tự sau đây: EnQueue(Q, ’A’), EnQueue(Q, ’B’), EnQueue(Q, ’C’), DeQueue(Q, Item), EnQueue(Q, ’D’), EnQueue(Q, ’E’), DeQueue(Q, Item), DeQueue(Q, Item), EnQueue(Q, ’F’), DeQueue(Q, Item). b. Viết các thao tác cơ bản trên hàng đợi và thêm vào các thao tác sau đây: duyệt hàng đợi từ đầu đến đuôi của nó và ngược lại. 13) Dùng các phép toán cơ bản trên ngăn xếp và hàng đợi để đảo ngược thứ tự các phần tử trên hàng đợi. 14) Phân tích một số thành tích các thừa số nguyên tố theo thứ tự giảm dần. Ví dụ: phân tích: 60 = 5*3*2*2. 15) Dùng ngăn xếp để kiểm tra một chuỗi ký tự S1 có phải là palyndrome của một chuỗi ký tự S2 hay không ? 16) (*) Viết một chương trình đọc một xâu ký tự chứa các dấu ngoặc và xác định xâu đó có chứa các dấu ngoặc tương ứng hợp lệ hay không. Ví dụ: - các xâu sau là hợp lệ: a*(b+c), a(), b[d(e+f-)], d-{[a(b)d]} - các xâu sau là không hợp lệ: (, ], a*(b+c], a[), b[d(e+f-]), d-{[a((b)d]} (Các ứng dụng khác của DSLK) 17) a. Chuyển các biểu thức trung tố sau đây sang dạng hậu tố: a/(b*c), a/b*c, a∧b∧c, (a∧b)∧c, a-b-c, a-(b-c), a5 + 4a3 - 3a2 + 7, (a+b)*(c- d), Sa+b b. Viết biểu thức sau đây dưới dạng hậu tố: (A * B)/(C + D). Minh họa thông qua hình ảnh Stack để tính giá trị biểu thức hậu tố này ứng với: A= 20, B = 4, C = 9, D = 7. c. (**) Cài đặt một chương trình để : i) Chuyển một biểu thức từ dạng trung tố sang dạng hậu tố (có kiểm tra cú pháp của biểu thức). ii) Tính giá trị của một biểu thức cho trước ở dạng hậu tố. iii) Vẽ đồ thị của một hàm giải tích cho trước được đưa vào dưới dạng biểu thức chuỗi. iv) Có thể viết lại chương trình trên khái quát hơn để có thể áp dụng cho các biểu thức lôgic mệnh đề hay không ? 18) (**) Hãy viết một chương trình thực hiện các yêu cầu tương tự của bài tập 4 - chương 2 để cài đặt các thuật toán sắp xếp sau trên DSLK động (DSLK đơn, DSLK kép): a. QuickSort b. MergeSort c. RadixSort d. Các phương pháp sắp xếp trực tiếp: chèn, chọn, đổi chỗ Baøi taäp Caáu truùc döõ lieäu vaø Thuaät toùan 1 BT.10 19) (*) Hãy lập các giải thuật cộng, trừ, nhân hai đa thức và tính đạo hàm, nguyên hàm của một đa thức cho trước trong hai trường hợp: a) Khi các hệ số của đa thức được lưu đầy đủ trong mảng. b) (*) Khi chỉ các hệ số khác không và các số mũ tương ứng được lưu trong một danh sách liên kết. 20) (*) Hãy cài đặt tập hợp bằng DSLK và thực hiện các phép toán trên tập hợp (quan hệ một phần tử có thuộc vào một tập không; quan hệ bao hàm, bằng nhau giữa hai tập; phép toán giao, hiệu, hợp hai tập hợp, ...) 21) (**) Viết các phép toán cơ bản trên ma trận thưa được cài đặt bằng DSLK tổng quát. 22) a. Hãy cài đặt các thao tác cơ bản trên DSLK có thứ tự và tổ chức lại, hàng đợi ưu tiên. So sánh thời gian tìm kiếm của cách tổ chức này với các cách tổ chức bình thường. b. Tìm một ứng dụng thực tế của hàng đợi ưu tiên. 23) (*) Áp dụng thuật toán sắp xếp tôpô vào bài toán sắp lịch giảng dạy (tuyến tính) cho dãy các học phần thỏa điều kiện “học trước” đã biết. Baøi taäp Caáu truùc döõ lieäu vaø Thuaät toùan 1 BT.11 Bài tập chương IV (Cấu trúc cây) 1) Xuất ra theo thứ tự : giữa, đầu, cuối các phần tử trên cây nhị phân sau: A P R Q E T M N D B C 2) a. Tìm cây nhị phân thỏa đồng thời hai điều kiện kết xuất sau: theo thứ tự đầu NLR của nó là dãy ký tự sau: A, B, C, D, E, Z, U, T, Y và theo thứ tự giữa LNR của nó là dãy ký tự sau: D, C, E, B, A, U, Z, T, Y b. (*) Khi cho trước 2 trong 3 kết quả duyệt NLR, LNR, LRN thì có luôn xác định duy nhất cây nhị phân thỏa điều kiện nêu ra không ? Dùng chương trình để kiểm chứng ? 3) a. Biểu diễn mỗi biểu thức số học dưới đây trên cây nhị phân, từ đó rút ra dạng biểu thức hậu tố của chúng: i. a/(b*c) ii. a5 + 4a3 -3a2 + 7 iii. (a+b)*(c-d) iv. Sa+b b. (*) Viết thuật toán và chương trình: - Chuyển một biểu thức số học ký hiệu lên cây nhị phân (có kiểm tra biểu thức đã cho có hợp cú pháp không ?). - Xuất ra biểu thức số học đó dưới dạng: trung tố, hậu tố, tiền tố. - Sau đó nhập trị cho các ký hiệu trong biểu thức, hãy đánh giá biểu thức hậu tố tương ứng. 4) Xây dựng cây tìm kiếm nhị phân BST và cây AVL từ mỗi bộ mục dữ liệu đầu vào như sau: a. 1, 2, 3, 4, 5 b. 5, 4, 3, 2, 1 c. fe, cx, jk, ha, gc, ap, aa, by, my, da d. 8, 9, 11, 15, 19, 20, 21, 7, 3, 2, 1, 5, 6, 4, 13, 10, 12, 17, 16, 18. Sau đó xóa lần lượt các nút sau: 2, 10, 19, 8, 20, 6, 1. 5) Viết một chương trình có các tác dụng sau: a. Nhập từ bàn phím các số nguyên vào một cây nhị phân tìmkiếm (BST) mà nút gốc được trỏ bởi con trỏ Root. Baøi taäp Caáu truùc döõ lieäu vaø Thuaät toùan 1 BT.12 b. Xuất các phần tử trên cây BST trên theo thứ tự : đầu, giữa, cuối theo dòng và vẽ sơ đồ cây (*) (chỉ yêu cầu trường hợp khi số phần tử của cây nhị phân không quá lớn !). c. Tìm và xóa (nếu có thể) phần tử trên cây Root có dữ liệu trùng với một mục dữ liệu Item cho trước được nhập từ bàn phím. d. Sắp xếp n mục dữ liệu (được cài đặt bằng mảng hay DSLK) bằng phương pháp cây nhị phân tìm kiếm BSTSort. Yêu cầu: viết các thao tác trên bằng 2 phương pháp: đệ quy và lặp (*). (**) Riêng với duyệt cây, hãy viết dưới dạng lặp cả 3 phương pháp duyệt trong một hàm duy nhất có tính khái quát. e. Kiểm tra lại kết quả của bài tập 4) bằng chương trình vừa xây dựng. 6) Tương tự bài tập 5, nhưng mỗi nút có thêm trường con trỏ Parent chỉ đến nút cha của nó. 7) (*) Xây dựng các thao tác cơ bản trên cây n-phân được biểu diễn bởi cây nhị phân: chèn một nút, tạo cây n-phân, xóa một nút, hủy cây n-phân. 8) Cho cây nhị phân T. Viết chương trình chứa các hàm có tác dụng xác định: a. Tổng số nút của cây. Số nút tối đa của cây nhị phân có chiều cao h là bao nhiêu? Chứng minh điều khẳng định bằng qui nạp và kiểm nghiệm lại bằng chương trình. b. (*) Số nút của cây ở mức k. Số nút tối đa ở mức k của cây nhị phân là bao nhiêu ? Chứng minh điều khẳng định bằng qui nạp và kiểm nghiệm lại bằng chương trình. c. Số nút lá. d. (*) Chiều cao của cây. e. Tổng giá trị trường dữ liệu (số !) trên các nút của cây. f. Kiểm tra xem nó có phải là một cây nhị phân chặt (là cây nhị phân mà mỗi nút khác nút lá đều có đúng 2 con) hay không ? g. Kiểm tra xem T có phải là cây cân bằng hoàn toàn hay không ? h. Số nút có đúng 2 con khác rỗng i. Số nút có đúng 1 con khác rỗng j. Số nút có khóa nhỏ hơn x trên cây nhị phân hoặc cây BST k. Số nút có khóa lớn hơn x trên cây nhị phân hoặc cây BST l. Số nút có khóa nhỏ hơn x và lớn hơn y (y ≤ x) trên cây nhị phân hoặc cây BST m. Duyệt cây theo chiều rộng n. Duyệt cây theo chiều sâu o. Độ lệch lớn nhất của các nút trên cây (độ lệch của một nút là trị tuyệt đối của hiệu số giữa chiều cao của cây con phải và cây con trái của nó) p. Đảo nhánh trái và phải của mọi nút trên một cây nhị phân Yêu cầu: viết các thao trên bằng 2 phương pháp: đệ quy và lặp (*). 9) Viết chương trình xây dựng cây nhị phân tìm kiếm có chiều cao bé nhất từ một dãy có thứ tự tăng của các phần tử được lưu trữ trên một danh sách liên kết. 10) a. Hãy vẽ cây AVL có chiều cao cực đại có 12 nút Baøi taäp Caáu truùc döõ lieäu vaø Thuaät toùan 1 BT.13 b. Hãy tìm một ví dụ về một cây AVL có chiều cao là 6 và khi hủy một nút lá (chỉ ra cụ thể), việc cân bằng lại cây lan truyền lên tận gốc. c. (*) Viết chương trình thể hiện các thao tác cơ bản trên cây AVL: chèn một nút, xóa một nút, tạo cây AVL, hủy cây AVL. Kiểm tra lại bằng chương trình với dữ liệu của câu a. và b. trên đây. 11) (*) Viết chương trình cho phép tạo, thêm, bớt, tra cứu, sửa chữa từ điển. TÀI LIỆU THAM KHẢO [1] A.V. AHO , J.E. HOPCROFT , J.D. ULMANN: Data structures and algorithms. Addition Wesley - 1983. [2] DONALD KNUTH: The Art of Programming. (vol.1: Fundamental Algorithms, vol. 3: Sorting and Searching). Addition Wesley Puplishing Company - 1973. [3] ĐINH MẠNH TƯỜNG: Cấu trúc dữ liệu và giải thuật. NXB KHKT - 2001. [4] ĐỖ XUÂN LÔI: Cấu trúc dữ liệu và giải thuật. NXB KHKT - 1995. [5] LARRY N. HOFF, SANFORD LEESTMA: Lập trình nâng cao bằng Pascal với các cấu trúc dữ liệu. Bản dịch của Lê Minh Trung. Công ty Scitec - 1991. [6] NGUYỄN TRUNG TRỰC: Cấu trúc dữ liệu. Trung tâm điện toán, trường ĐH Bách khoa TP. HCM – 1992. [7] NIKLAUS WIRTH: Cấu trúc dữ liệu + Giải thuật = Chươngtrình (Nguyễn Quốc Cường dịch). NXB ĐH và THCN – 1991 [8] TRẦN HẠNH NHI & DƯƠNG ANH ĐỨC: Nhập môn cấu trúc dữ liệu và giải thuật. Khoa Công nghệ thông tin, ĐH KHTN TP HCM – 2000.
File đính kèm:
giao_trinh_cau_truc_du_lieu_va_giai_thuat_1.pdf