Viết unit các thuật toán trong sách cấu trúc dữ liệu và giải thuật bằng ngôn ngữ Pascal

Lời nói đầu Với tốc phát triển hiện nay thì môn tin học trở thành một môn học không thể thiếu trong các trường phổ thông và các trường đại học. Cuốn sách Cấu Trúc Dữ Liệu và Giải Thuật của PGS. Đỗ Xuân Lôi đã trở thành tài liệu học tập và tham khảo của sinh viên ngành công nghệ thông tin ở nhiều cơ sở đào tạo Cao Đẳng, Đại Học và sau Đại Học. Để việc học môn này trở nên dễ dàng hơn em đã viết lại một số thuật toán trong sách dưới dạng các Unit. Phần 1:Yêu cầu của đề: Viết unit các thuật toán trong sách cấu trúc dữ liệu và giải thuật bằng ngôn ngữ Pascal Phần 2: Giới thiệu chi tiết đề tài Chương 1: Tổng Quan: Công việc đã làm Tiến trình công việc: Trong thời gian 2 tuần đầu của thực tập em đã nghiên cứu một số vấn đề quan trọng và căn bản có ý nghĩa trong việc thực hiện yêu cầu đã đặt ra của đề tài. Các unit và menu chương trình được viết trong tuần thứ 3 và hoàn thành trong tuần 4. Tuần 5 viết báo cáo và chỉnh sửa giao diện chương trình Công việc cụ thể: Dưới sự hướng dẫn tận tình của thầy Phạm Đức Khánh, sau 5 tuần : từ ngày 12-4-2005 đến ngày 16-5-2005 em đã làm được các công việc như sau: Đệ quy: Viết Unit dequy gồm các thủ tục N! Fibonacci Bài Toán Tháp Hà Nội Bài Toán Xếp 8 Hậu Sắp xếp: Viết Unint sapxep gồm các phương pháp lựa chọn Thêm dần Nổi bọt Sắp xếp nhanh Vun đống Hoà nhập Tìm kiếm Unit timkiem gồm các thủ tục Tìm kiếm tuần tự Tìm kiếm nhị phân Ngăn xếp Unit nganxep có úng dung Đổi cơ số từ một số hệ 10 sang hệ bất kỳ <10 Công việc chưa làm Do thời gian có hạn nên còn nhiều thuật toán hay trong sách em chưa có điều kiên hoàn thành. Menu chương trình chính chưa được đẹp vì chương trình em viết hoàn toàn bằng ngôn ngữ Pascal – một ngôn ngữ có nhiều hạn chế về giao diện. Chương 2 Tóm tắt các menu chính: Chương trình chính có tên menu.pas gồm các modul sau: KeO: kẻ khung chương trình HienThi: hiển thị các lựa chọn của chương trình Call_n: Gọi thủ tục giaithua trong Unit dequy.tpu để tính n! Call_Fibonacci: Gọi thủ tục Fibonacci trong Unit dequy.tpu để tính dãy Fibonacci của một số nhập vào từ bàn phím Call_ThapHN: Gọi thủ tục ThapHaNoi trong Unit dequy.tpu để thực hiện bài toán chuyển n đĩa từ cọc 1 sang cọc 2 Call_XepHau: Gọi thủ tục XepHau trong Unit Dequy.tpu để đưa ra các phương án xếp 8 con hậu không ăn nhau trên bàn cờ vua Call_Select: Gọi thủ tục Select_Sort trong Unit SX_va_TK.tpu để Sắp xếp theo phương pháp lựa chọn Call_Insert: Gọi thủ tục Insert_Sort trong Unit SX_va_TK.tpu để Sắp xếp theo phương pháp thêm dần Call_Bubble: Gọi thủ tục Bubble_Sort trong Unit SX_va_TK.tpu để Sắp xếp theo phương pháp nổi bọt Call_Quick: Gọi thủ tục Quick_Sort trong Unit SX_va_TK.tpu để Sắp xếp theo phương pháp sắp xếp nhanh Call_Heap: Gọi thủ tục Head_Sort trong Unit SX_va_TK.tpu để Sắp xếp theo phương pháp vun đống Call_Mergring: Gọi thủ tục Mergring_Sort trong Unit SX_va_TK.tpu để Sắp xếp theo phương pháp hoà nhập Call_TimTuanTu: Gọi thủ tục Sequen_Search trong Unit SX_va_TK.tpu để tìm vị trí của một số trong dãy đã cho theo phương pháp tìm kiếm tuần tự. Call_TimNhiPhan: Gọi thủ tục Binary_Search trong Unit SX_va_TK.tpu để tìm vị trí của một số trong dãy đã cho theo phương phán tìm vị trí của một số trong dãy đã cho theo phương phán tìm kiếm Nhị Phân Call_DoiCoSo: Gọi thủ tục DoiCoSo trong Unint Stack.tpu để đổi một số từ số hệ 10 sang hệ bất kỳ < 10. Chương 3 Chi tiết các modul : n!:Begin Nhập N K= 1 I = 2 K: = k*i I: =i+1 I > N GiaiThua: = k END True False Fibonacci: ta có : if n< = 2 then F(n) = 1 F(n) = F(n-2) + F(n-1) Begin Fibo = x+y X = Y Y = Fibo END i< = n True False I = i+ 1 Nhập N i = 2 x = 1 y = 1 Fibo = 0 ThapHaNoi Begin Chuyển n -1 đĩa từ a sang b Out a b Chuyển n -1 đĩa từ c sang b END True False N0 N 4. Select_Sort: Begin True False N I = 1 m = i j = i+1 a[j] < a[m] m = j j = j+1 I > N m i True True M i Đổi Chỗ a[j] , a[m] I = i + 1 i > n - 1 False False False END 5. Insert_Sort: Begin False True N a [0] = -32767 i = 2 X = a [i] j = j - 1 x < a[j] a [j+1] = x I = i + 1 False END I < = N True a[j+1] = a[j] j = j - 1 6. Bubble_Sort: Begin False True N i = 1 j = n a[j] < a[j-1] J = J - 1 False END J< I + 1 True Đổi chỗ a[j] , a[j-1] I = i+1 I > n-1 False True 7. Quick_Sort: Begin False True N i = l j = r x= a[(i+j) div 2] a[i] < x i = i + 1 END x< a[j] Đổi chỗ a[j] , a[j] i = i + 1 j = j - 1 True True j = j - 1 False i< = j True i< = j False False L < i True R = j I < R False True R = j False 8. Sequen_Search: Begin END False N0 K I = 1 a[n+1] = k a[i] k I = I+1 Sequen = i True 9. Sequen_Search: Begin END False N0 K I = 1 a[n+1] = k a[i] k I = I+1 Sequen = i True \ 10. Binary_Search: Begin END False N0 K I = 1; a[n+1] = k Binary = 0 L< = r M = (r+l) div 2 True K < a[m] R = m - 1 True K > a[m] L = m + 1 True False False Binary = m 11. DoiCoSo: Begin END False X, Y T = 0 x 0 r = x mod y True push(c,t,r) x = x div y T > 0 pop(c,t,r) R True False Chương 4: Hướng dẫn sử dụng qua giao diện chương trình Chương trình có thể chạy trên môi trường Windows 9x, 2000, xp hoặc Dos. Dung lượng chương trình nhỏ, gọn, không phài cài đặt. Menu chương trình chính: Tính n!: Fibonacci: ThapHaNoi: XepHau: Select_Sort: Insert_Sort: bubble_Sort: Quick_Sort: Heap_Sort: Mergring: Sequen_Search: Binary_Search: DoiCoSo: Tài liệu tham khảo: Giáo trình: Ngôn ngũ lập trình Pascal – Quách Tuấn Ngọc Giáo trình: Bài tập ngôn ngũ lập trình Pascal – Quách Tuấn Ngọc Giáo trình: Ngôn Ngữ lập trình Pascal nâng cao - Quách Tuấn Ngọc Giáo trình: Bài tập ngôn Ngữ lập trình Pascal nâng cao - Quách Tuấn Ngọc Sách :Turbo Pascal, cẩm nang tra cứu - Quách Tuấn Ngọc Giao trình: Cấu trúc dữ liệu và giải thuật – Đỗ Xuân Lôi