Đề tài Xây dựng chương trỡnh từ điển tiếng Nga

phân cách, ta có thể co giãn kích thước hai biên của đối tượng canh lề. TSpliter nằm trên bảng công cụ Additional. 1.2.8. Thư viện liên kết động (dll) 1.2.8.1. Thư viện DLL Thư viện liên kết động là các đơn thể chương trình chứa mã lệnh, dữ liệu hoặc tài nguyên được dùng để chia sẻ giữa các ứng dụng Windows với nhau. DLL cho phép ứng dụng nạp và điều khiển mã lệnh vào lúc chương trình thực thi thay vì phải liên kết mã lệnh vào lúc biên dịch chương trình. DLL chia sẻ mã lệnh, tài nguyên và dữ liệu giữa nhiều tiến trình. Do vậy, các chương trình ứng dụng khác nhau có thể đồng thời gọi đến hàm hay truy xuất tài nguyên do một DLL cung cấp. 1.2.8.2. So sánh giữa liên kết tĩnh và liên kết động Liên kết động Liên kết tĩnh - Mã lệnh thực thi của hàm (thủ tục) nằm trong tập tin .dll. - Có thể được gọi từ bên ngoài và các ứng dụng khác. - Chiếm ít bộ nhớ. - Mỗi khi cập nhật hoặc nâng cấp ứng dụng thì chỉ cần thay thế bằng DLL mới mà không cần phải biên dịch lại toàn bộ chương trình .EXE. - Mã lệnh thực thi của hàm (thủ tục) nằm trong tập tin .exe. - Không gọi được từ bên ngoài và từ các ứng dụng khác. - Chiếm nhiều bộ nhớ. - Mỗi khi cập nhật hoặc nâng cấp ứng dụng thì phải biên dịch lại toàn bộ chương trình .EXE. 1.2.8.3. Sử dụng thư viện DLL Thư viện DLL được sử dụng để: * Nạp và xử lý các hàm (thủ tục) chứa trong DLL. Thư viện DLL không thể gọi thực thi trực tiếp từ dòng lệnh như các tập tin .exe mà phải được gọi gián tiếp từ các chương trình hay DLL khác. Sau khi khai báo chính xác đường dẫn thì các hàm và thủ tục chứa trong DLL được gọi và sử dụng bình thường như các hàm và thủ tục trong Unit của Delphi. * Hiển thị Form chứa trong DLL. Nếu chương trình ứng dụng cần nhiều cửa sổ Form để xây dựng giao diện phức tạp, thì việc đặt tất cả Form trong chương trình chính sẽ làm cho tập tin .exe phình to về kích thước. Vì vậy, có thể đặt Form vào bên trong DLL và gọi hiển thị Form từ chương trình chính. Có hai cách để hiển thị Form chứa trong DLL: + Hiển thị Form ở dạng modeless: khi Form phụ ở dạng modeless, người sử dụng có thể quay lại tương tác với Form chính trong khi Form phụ đang hiển thị. + Hiển thị Form ở dạng dạng model: người sử dụng không thể quay về tương tác với cửa sổ Form chính nếu cửa sổ Form phụ chưa được đóng lại. 1.2.9. Giới thiệu về WIN32 API và hệ thống thông điệp * API (Application Programming Interface), còn gọi là Giao tiếp lập trình ứng dụng, là tập hợp các lời gọi hàm cấp cao do hệ điều hành Windows cung cấp. Sử dụng Win32 API trong Delphi cần khai báo hai Unit Windows và Messages trong mệnh đề USES ở đầu chương tình như sau: Uses Windows, Messages; Trong đó thư viện Windows chứa các khai báo hàm Windows API, thư viện Messages chứa các khai báo hằng và kiểu dữ liệu. * Thông điệp Thông điệp là một mẫu tin báo hiệu do Windows phát sinh và gửi đến cửa sổ ứng dụng và hàm WndProc chính là nơi tiếp nhận và xử lý các thông điệp đó. Mỗi thông điệp chuẩn của Windows là một hằng số bắt đầu bằng tiếp đầu ngữ WM_. Mỗi thông điệp đều có ý nghĩa và cách thức xử lý khác nhau. Ví dụ: WM_KEYDOWN: Nút bàn phím bị nhấn xuống. WM_KEYUP: Nút bàn phím được nhả ra. CHƯƠNG II: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 2.1. GIỚI THIỆU 2.1.1. Giải thuật và cấu trúc dữ liệu Giải thuật là một dãy các câu lệnh chặt chẽ và 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 đó sao cho sau một số hữu hạn bước thực hiện ta đạt được kết quả mong muốn. Việc giải thuật đó được tác động lên dữ liệu nào và dữ liệu ấy cần được tác động giải thuật gì để đưa tới kết quả tốt. Như vậy giữa cấu trúc dữ liệu và giải thuật có mối quan hệ mật thiết. Chính điều đó đã dẫn tới việc cần nghiên cứu các cấu trúc dữ liệu đi đôi với việc xác lập các giải thuật xử lý trên các cấu trúc ấy. 2.1.2. Cấu trúc dữ liệu và các vấn đề liên quan Trong một bài toán, dữ liệu bao gồm một tập các phần tử cơ sở gọi là dữ liệu nguyên tử. Lựa chọn một cấu trúc dữ liệu thích hợp để tổ chức dữ liệu vào và trên cơ sở đó xây dựng được giải thuật xử lý hữu hiệu đưa tới kết quả mong muốn cho bài toán, đó là khâu rất quan trọng. Cách biểu diễn một cấu trúc dữ liệu trong bộ nhớ được gọi là cấu trúc lưu trữ. Đó chính là cách cài đặt cấu trúc ấy trên máy tính và trên cơ sở các cấu trúc lưu trữ này mà thực hiện các phép xử lý. 2.1.3. Các tiêu chuẩn đánh giá cấu trúc dữ liệu Một cấu trúc dữ liệu tốt phải thỏa mãn các tiêu chuẩn sau: - Phản ánh đúng thực tế: Đây là tiêu chuẩn quan trọng nhất, quyết định tính đúng đắn của toàn bộ bài toán. - Phù hợp với các thao tác trên đó: tiêu chuẩn này giúp tăng tính hiệu quả của đề án: việc phát triển các thuật toán đơn giản, tự nhiên hơn; chương trình đạt hiệu quả cao hơn về tốc độ xử lý. - Tiết kiệm tài nguyên hệ thống: thông thường có 2 loại tài nguyên cần lưu tâm nhất: CPU và bộ nhớ. 2.1..4. Đánh giá độ phức tạp giải thuật Cần tìm những phương pháp đánh giá thuật toán ít phụ thuộc môi trường cũng như phần cứng hơn. Một phương pháp như vậy là phương pháp đánh giá thuật toán theo hướng xấp xỉ tiệm cận qua các khái niệm toán học O(), o(),... Hầu hết các thuật toán đều có một tham số chính là N, thông thường đó là số lượng các phần tử dữ liệu được xử lý mà ảnh hưởng rất nhiều tới thời gian chạy. Hầu hết tất cả các thuật toán trong giáo trình này có thời gian chạy tiệm cận tới một trong các hàm sau: hằng số, logN, N, NlogN, N2, N3, 2N 2.2. SẮP XẾP VÀ TÌM KIẾM Trong hầu hết các hệ lưu trữ, quản lý dữ liệu, thao tác tìm kiếm thường được thực hiện nhiều nhất để khai thác thông tin. Ví dụ: tra cứu từ điển, tìm sách trong thư viện... Do các hệ thống thông tin thường phải lưu trữ một khối lượng dữ liệu đáng kể, nên việc xây dựng các giải thuật cho phép tìm kiếm nhanh sẽ có ý nghĩa rất lớn. Nếu dữ liệu trong hệ thống đã được tổ chức theo một trật tự nào đó, thì việc tìm kiếm sẽ tiến hành nhanh chóng và hiệu quả hơn. Ví dụ: các từ trong từ điển được sắp xếp theo từng vần, trong mỗi vần lại được sắp xếp theo thứ tự bảng chữ cái; sách trong thư viện được xếp theo chủ đề, tên tác giả.... Hiện nay đã có nhiều giải thuật tìm kiếm và sắp xếp được xây dựng, mức độ hiệu quả của từng giải thuật còn phụ thuộc vào tính chất của cấu trúc dữ liệu cụ thể mà nó tác động đến. Dữ liệu được lưu trữ chủ yếu trong bộ nhớ chính và trên bộ nhớ phụ do đặc điểm khác nhau của thiết bị lưu trữ, các thuật toán sắp xếp và tìm kiếm được xây dựng cho các cấu trúc lưu trữ trên bộ nhớ chính hoặc phụ cũng có những đặc thù khác nhau. Các thuật toán sắp xếp được phân thành hai nhóm chính là: - Sắp thứ tự nội: toàn bộ dữ liệu cần sắp thứ tự phải được đưa vào trong bộ nhớ chính, nên thời gian để sắp thứ tự tương đối nhanh. - Sắp thứ tự ngoại: một phần các dữ liệu cần sắp thứ tự được đưa vào trong bộ nhớ chính, phần dữ liệu còn lại được lưu trữ ở trên bộ nhớ ngoài. Thời gian để sắp thứ tự tương đối chậm. 2.2.1.Một số giải thuật sắp xếp. Sắp xếp là quá trình xử lý một danh sách các phần tử (hoặc các mẫu tin) để đặt chúng theo một thứ tự thỏa mãn một tiêu chuẩn nào đó dựa trên nội dung thông tin lưu giữ tại mỗi phần tử. Một số phương pháp sắp xếp thông dụng như: + Sắp xếp kiểu lựa chọn (Selection Sort) + Sắp xếp kiểu thêm dần (Insertion Sort) + Sắp xếp kiểu đổi chỗ (Exchange Sort) + Sắp xếp kiểu nổi bọt (Bubble Sort) + Sắp xếp kiểu phân đoạn (Quick Sort) + Sắp xếp kiểu vun đống (Heap Sort) + Sắp xếp kiển hòa nhập (Merge Sort) + Sắp xếp với độ dài bước giảm dần (Shell Sort) + Sắp xếp theo phương pháp cơ số (Radix Sort) Nhận xét và đánh giá các thuật toán sắp xếp: Phần lớn các thuật toán sắp xếp cơ bản dựa trên sự so sánh giá trị giữa các phần tử. Đó là các thuật toán chọn lựa, thêm dần, nổi bọt, đổi chỗ. Các thuật toán này đều có một điểm chung là chi phí thực hiện chung là tỉ lệ với n2. Các thuật toán shell-sort (cải tiến của phương pháp thêm dần), heap-sort (cải tiến của phương pháp chọn lựa) lại có độ phức tạp nhỏ hơn hẳn các thuật toán gốc. Thuật toán shell-sort có độ phức tạp O(nx) với 1 < x < 2 và thuật toán heap-sort có độ phức tạp O(nlog2n). Các thuật toán merge-sort và quick-sort là những thuật toán thực hiện theo chiến lược chia để trị. Cài đặt chúng tuy phức tạp hơn các thuật toán khác nhưng chi phí thực hiện lại thấp, cả hai thuật toán đều có độ phức tạp O(nlog2n). Merge-sort có nhược điểm là cần dùng thêm bộ nhớ đệm. Thuật toán này sẽ phát huy tốt ưu điểm khi cài đặt trên các cấu trúc dữ liệu khác phù hợp hơn như danh sách liên kết hay phi. Thuật toán quick-sort được đánh giá là thuật toán sắp xếp nhanh nhất trong số các thuật toán sắp xếp dựa trên nền tảng so sánh giá trị của các phần tử. Tuy có chi phí trong trường hợp xấu nhất là O(n) nhưng trong kiểm nghiệm thực tế, thuật toán quick-sort chạy nhanh hơn hai thuật toán cùng nhóm O(nlog2n) là merge-sort và heap-sort. Thuật toán Radix-sort là một thuật toán được phát triển theo hướng khác với các thuật toán trên. Nó được phát triển dựa trên mô phỏng qui trình phân phối thư của người đưa thư. Thuật toán này đại diện cho nhóm các thuật toán sắp xếp có độ phức tạp tuyến tính. Tuy nhiên, thường thì các thuật toán này không thích hợp cho việc cài đặt trên cấu trúc dữ liệu mảng một chiều. 2.2.2. Các giải thuật tìm kiếm nội Thông thường các dữ liệu được phân chia thành các bản ghi, mỗi bản ghi có một khoá được sử dụng trong việc tìm kiếm. Vấn đề của việc tìm kiếm là tìm tất cả các mẩu tin có cùng khoá k cho biết trước để truy xuất nội dung của bản ghi. Công việc tìm kiếm sẽ hoàn thành khi có một trong hai tình huống sau xảy ra: - Tìm được bản ghi có giá trị khóa tương ứng, lúc đó ta nói: phép tìm kiếm được thỏa. - Không tìm được bản ghi nào có giá trị khóa tương ứng: phép tìm kiếm không thỏa. Sau khi phép tìm kiếm không thỏa có khi xuất hiện yêu cầu bổ sung thêm bản ghi mới có khóa không tìm thấy vào bảng. Giải thuật thể hiện cả yêu cầu này được gọi là giải thuật “Tìm kiếm có bổ sung”. Ta có một số thuật toán tìm kiếm như: + Tìm kiếm tuần tự + Tìm kiếm nhị phân + Tìm kiếm dựa vào giá trị khóa Nhận xét và đánh giá các thuật toán tìm kiếm: Giải thuật tìm nhị phân dựa vào quan hệ giá trị của các phần tử mảng để định hướng trong quá trình tìm kiếm, do vậy chỉ áp dụng được cho những dãy đã có thứ tự. Giải thuật tìm nhị phân tiết kiệm thời gian hơn rất nhiều so với giải thuật tìm kiếm tuần tự do Tnhị phân(n) = O(log2n) < Ttuần tự(n) = O(n). Tuy nhiên khi muốn áp dụng giải thuật tìm nhị phân cần phải xét đến thời gian sắp xếp dãy số để thỏa điều kiện dãy số có thứ tự. Với phương pháp tìm kiếm dựa vào giá trị khóa, các khóa có giá trị khác nhau cũng có thể cùng ứng với một địa chỉ và hiện tượng này được gọi là hiện tượng đụng độ. Vì vậy khi xét phương pháp này, không những cần chú ý đến cách xây dựng hàm địa chỉ mà còn phải xét cả tới phương pháp khắc phục đụng độ. 2.3. CẤU TRÚC CÂY 2.3.1. Định nghĩa và khái niệm * Định nghĩa cây Cây là một tập hợp T rỗng hoặc gồm nhiều phần tử được gọi là nút, trong đó: - Một nút được gọi là nút gốc (root). - Các nút còn lại được phân chia thành m nhóm (m>=0), mỗi nhóm là một cây và được gọi là cây con. Trong đó nút có thể được xem như là một phần tử của một danh sách và có thể có kiểu bất kỳ. Các nút được biểu diễn bởi một ký tự chữ, một chuỗi, một số ghi trong một vòng tròn. Giữa các nút có một quan hệ phân cấp gọi là “quan hệ cha con”, các nút ngay bên trên trực tiếp là nút cha, các nút ngay bên dưới trực tiếp là các con của nút đó. Một cây không có một nút nào cả gọi là cây rỗng. * Một số khái niệm cơ bản - Bậc của một nút: là số cây con của nút đó - Bậc của một cây: là bậc lớn nhất của các nút trong cây (số cây con tối đa của một nút thuộc cây). Cây có bậc n thì gọi là cây n-phân. - Nút gốc: là nút không có nút cha. - Nút lá: là nút có bậc bằng 0. - Nút nhánh: là nút có bậc khác 0 và không phải là gốc - Rừng cây: là tập hợp nhiều cây trong đó thứ tự các cây là quan trọng. 2.3.2. Các cách biểu diễn cây Để biểu diễn một cây, ta có nhiều cách: a) Biểu diễn cây bằng đồ thị b) Biểu diễn cây bằng giản đồ c) Biểu diễn cây bằng các dấu ngoặc lồng nhau d) Biểu diễn cây bằng phương pháp Indentation e) Biểu diễn cây bằng chỉ số 2.3.3. Cây nhị phân * Khái niệm: Cây nhị phân là một dạng quan trọng của cấu trúc cây. Nó có đặc điểm là: mọi nút trên cây chỉ có tối đa là hai cây con (cây con trái và cây con phải). Cây nhị phân là cây có thứ tự. 2.3.3.1. Biểu diễn cây nhị phân - Lưu trữ kế tiếp: cây được lưu trữ bằng một vectơ V với nút thứ i của cây được lưu trữ ở V[i]. Với cách lưu trữ này nếu biết được địa chỉ nút cha sẽ tính được địa chỉ nút con và ngược lại. Tuy nhiên nếu cây nhị phân không đầy đủ thì cách lưu trữ này không thích hợp vì sẽ gây ra lãng phí do có nhiều phần tử nhớ bỏ trống (ứng với cây con rỗng). A B C F D E G Ví dụ: Với cây nhị phân Hình số 1 Biểu diễn phương pháp lưu trữ kế tiếp của cây nhị phân trên như sau: A B C D E E G V[1] V[2] V[3] V[4] V[5] V[6] V[7] Hình số 2 - Lưu trữ móc nối: mỗi nút của cây ứng với một phần tử nhớ gồm ba trường là: trường INFO ứng với thông tin dữ liệu của nút; trường LPTR ứng với con trỏ trỏ tới cây con trái của nút đó; trường RPTR ứng với con trỏ trỏ tới cây con phải của nút đó. Với cách biểu diễn này thì nút cha có thể truy nhập vào nút con dễ dàng, nhưng ngược lại thì không làm được Ví dụ: Với cây nhị phân trên ta có phương pháp lưu trữ móc nối như sau A B C D G E F Hình số 3 2.3.3.2. Duyệt cây nhị phân Có ba phép duyệt khác nhau đối với cây nhị phân. - Duyệt theo thứ tự trước: Kiểu duyệt này trước tiên thăm gốc sau đó thăm các nút của cây con trái rồi đến cây con phải. - Duyệt theo thứ tự giữa: Kiểu duyệt này trước tiên thăm các nút của cây con trái sau đó thăm nút gốc rồi đến cây con phải. - Duyệt theo thứ tự sau: Kiểu duyệt này trước tiên thăm các nút của cây con trái sau đó thăm đến cây con phải rồi cuối cùng mới thăm nút gốc. 2.3.4. Biểu diễn cây tổng quát bằng cây nhị phân - Cây tổng quát: có đặc điểm là mọi nút trên cây có thể có nhiều hơn hai cây con. - Nhược điểm của các cấu trúc cây tổng quát là bậc của các nút trên cây có thể dao động trong một biên độ lớn, nên việc biểu diễn gặp nhiều khó khăn và lãng phí. Hơn nữa, việc xây dựng các thao tác trên cây tổng quát phức tạp hơn trên cây nhị phân nhiều. Vì vậy, thường nếu không quá cần thiết phải sử dụng cây tổng quát, người ta chuyển cây tổng quát thành cây nhị phân. Ta có thể biến đổi một cây bất kỳ thành một cây nhị phân theo qui tắc sau: + Giữ lại nút con trái nhất làm nút con trái. + Các nút con còn lại chuyển thành nút con phải. + Như vậy, trong cây nhị phân mới, con trái thể hiện quan hệ cha con và con phải thể hiện quan hệ anh em trong cây tổng quát ban đầu. Khi đó cây tổng quát biểu diễn theo qui tắc trên được gọi là cây nhị phân tương đương. B A C E F G D H I J A B E C D G H I J F Ví dụ: Cây tổng quát chuyển sang cây nhị phân Hình số 4 2.3.5. Cây nhị phân tìm kiếm * Định nghĩa: Cây nhị phân tìm kiếm (CNPTK) là cây nhị phân trong đó tại mỗi nút, khóa của nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn khóa của tất cả các nút thuộc cây con phải. Nhờ ràng buộc về khóa trên CNPTK, việc tìm kiếm trở nên có định hướng. Hơn nữa, do cấu trúc cây việc tìm kiếm trở nên nhanh đáng kể. Nếu số nút trên cây là N thì chi phí tìm kiếm trung bình chỉ khoảng log2N. * Các thao tác trên cây nhị phân tìm kiếm: a) Duyệt cây: Thao tác duyệt cây trên cây nhị phân tìm kiếm hoàn toàn giống như trên cây nhị phân. Chỉ có một lưu ý nhỏ là khi duyệt theo thứ tự giữa, trình tự các nút duyệt qua sẽ cho ta một dãy các nút theo thứ tự tăng dần của khóa. b) Thêm một phần tử x vào cây: Việc thêm vào phải bảo đảm điều kiện ràng buộc của CNPTK. Ta có thể thêm vòa nhiều chỗ khác nhau trên cây, nhưng nếu thêm vào một nút lá sẽ là tiện lợi nhất do ta có thể thực hiện quá trình tương tự thao tác tìm kiếm. Khi chấm dứt quá trình tìm kiếm cũng chính là lúc tìm được chỗ cần thêm. c) Hủy một phần tử có khóa x: Việc hủy một phần tử x ra khỏi cây phải bảo đảm điều kiện ràng buộc của CNPTK. Có 3 trường hợp khi hủy nút x có thể xảy ra: + x là nút lá: chỉ đơn giản hủy x vì nó không móc nối đến phần tử nào khác. + x chỉ có 1 con (trái hoặc phải): trước khi hủy x ta móc nối cha của x với con duy nhất của nó. + x có đủ cả 2 con: ta không thể hủy trực tiếp do x có đủ 2 con. Vì vậy ta sẽ hủy gián tiếp. Thay vì hủy x, ta sẽ tìm một phần tử thế mạng y. Phần tử này có tối đa một con. Thông tin lưu tại y sẽ được chuyển lên lưu tại x. Sau đó, nút bị hủy thật sự sẽ là y giống như 2 trường hợp đầu. Vấn đề là phải chọn y sao cho khi lưu y vào vị trí của x, cây vẫn là CNPTK. Có 2 phần tử thỏa mãn yêu cầu: Phần tử nhỏ nhất (trái nhất) trên cây con phải và phần tử lớn nhất (phải nhất) trên cây con trái. d) Tạo một cây CNPTK: Ta có thể tạo một cây nhị phân tìm kiếm bằng cách lặp lại quá trình thêm 1 phần tử vào một cây rỗng. e) Hủy toàn bộ CNPTK: Việc toàn bộ cây có thể được thực hiện thông qua thao tác duyệt cây theo thứ tự sau. Nghĩa là ta sẽ hủy cây con trái, cây con phải rồi mới hủy nút gốc. 2.3.6. Cây nhị phân cân đối * Cây nhị phân cân đối hoàn toàn: là cây nhị phân tìm kiếm mà tại mỗi nút của nó, số nút của cây con trái chênh lệch không quá một so với số nút của cây con phải. Nhận xét: Một cây khó đạt được trạng thái cân bằng hoàn toàn. Tuy nhiên nếu cây cân đối thì việc tìm kiếm sẽ nhanh, trong trường hợp xấu nhất ta chỉ phải tìm qua log2n phần tử (với n là số nút trên cây). Do cây cân đối hoàn toàn là một cấu trúc kém ổn định nên trong thực tế không thể sử dụng. * Cây nhị phân cân đối: là cây mà tại mỗi nút của nó độ cao của cây con trái và của cây con phải chênh lệch không quá một. Nhận xét: Cây cân đối hoàn toàn là cây cân bằng. Điều ngược lại không đúng. Tuy nhiên cây cân đối là cấu trúc dữ liệu ổn định hơn hẳn cây cân đối hoàn toàn. Từ cây cân đối người ta đã phát triển thêm nhiều lại cấu trúc dữ liệu hữu dụng khác như cây đỏ-đen, B-cây,... 2.3.7. Cây nhị phân tìm kiếm tối ưu Xây dựng cây nhị phân tìm kiếm tương ứng với các từ khóa. Đối với các từ khóa có xác suất xuất hiện lớn thì cần phải được tìm thấy nhanh hơn, nghĩa là tương ứng với đường đi ngắn hơn. Muốn thế gắn với mỗi khóa (nút) một trọng số, đó chính là xác suất xuất hiện của khóa này trong tìm kiếm. Và mục đích là xác định được cây nhị phân tìm kiếm sao cho tổng độ dài đường đi có trọng số tương ứng với mọi nút trên cây (hay còn gọi là độ dài đường đi có trọng số của cây) có giá trị nhỏ nhất. Tuy nhiên việc chọn một cây có trọng số nhỏ nhất là một công vệc khó thực hiện khi n khá lớn. Vậy để giải quyết vấn đề này ta thực hiện theo nguyên tắc sau: “Đối với một cây nhị phân tìm kiếm tối ưu thì bất kỳ một cây con nào của nó cũng phải là cây nhị phân tìm kiếm tối ưu ”. Từ đó dẫn tới một giải thuật cho phép dựng được cây nhị phân tìm kiếm tối ưu lớn dần lên bắt đầu từ một nút lá mà ta gọi là kỹ thuật dựng cây nhị phân tìm kiếm tối ưu theo kiểu “từ đáy lên” (bottom up). CHƯƠNG III: TỔ CHỨC LƯU TRỮ CÂY TỪ ĐIỂN Một cấu trúc dữ liệu khá điển hình và hợp lý với bài toán từ điển là: cấu trúc cây từ điển. Quản lý từ điển có dạng cây là kỹ thuật thường được sử dụng để xử lý những từ điển lớn nhằm thu nhỏ dung lượng. Cây từ điển là tập hợp các bản ghi liên kết với nhau (còn gọi là phương pháp lưu trữ móc nối). Mỗi bản ghi gọi là một nút trong cây. Để quản lý cây từ điển ta luôn luôn phải giữ địa chỉ của cây, tức là nút gốc (nút đầu tiên của cây). Mỗi nút cây từ điển gồm có 3 trường: + Trường Info: chứa một kí tự kiểu CHAR. + Trường Left: chỉ đến nút Anh Em của nó. + Trường Right: chỉ đến nút con của nó. Một nút B gọi là con của nút A nếu B = A.left Tương tự nút B gọi là nút Anh Em của nút A nếu: B = A.right (hoặc A = B.right). Từ đây mở rộng ra: nếu B là Con của A và C là Anh Em của B thì cả B và C đều là Con của A. Nếu A là Anh Em của B và B là Anh Em của C thì A cũng là Anh Em của C. Để tạo thành cây từ điển trong quá trình chạy chương trình, ta phải làm thao tác nạp các từ tiếng Nga vào cây. Về trường nghĩa của từ, vì nó rất lớn nên không thể nạp vào bộ nhớ chương trình được. Vì vậy ta phải để nghĩa của từ ở trong File. Điều này bắt buộc ta phải xen kèm vào trong cây từ điển (tương ứng sau mỗi từ tiếng Nga) chỉ số vị trí của từ tiếng Nga đó trong File. Và tất nhiên chỉ số này phải được đổi thành chuỗi kí tự thập phân trước khi thực hiện xen từ. Khi đọc thì sẽ chuyển ngược chuỗi chỉ số này sang số thập phân. Ví dụ: Với các từ tiếng Nga: а/абажур/абзац/база/базар/бак/бакалея/ баклажан Khi lưu trữ trên cây, các từ tiếng Nga này sẽ là các chuỗi có cấu trúc như sau: а*1 абажур*2 абзац*3 база*4 базар*5 бак*6 бакалея*7 баклажан*8 ta có cấu trúc cây từ điển như sau : * а * 1 б Б а ж у р 2 з а ц * * 3 а з а * 4 р * 5 * к 6 а л е * я 7 а ж а н * 8 Root Nút đánh dấu kết thúc của mỗi từ Nút đánh dấu số thứ tự bản ghi của mỗi từ, sử dụng cho việc tìm kiếm và tra từ Nút thể hiện từng ký tự của mỗi từ Hình số 5 Nhận xét : Theo cây từ điển được minh họa như hình số 5 , ký tự ‘*’ được sử dụng làm ký tự đánh dấu ở đầu cấu trúc cây và làm ký tự kết thúc của một từ. Như vậy theo cây từ điển thì mỗi từ tiếng Nga ngoài các ký tự hình thành còn có thêm ký tự ‘*’ ở cuối mỗi từ để đánh dấu và các ký tự chữ số để đánh số thứ tự từng bản ghi trong file dữ liệu hỗ trợ cho quá trình tìm kiếm trên cây. Mỗi từ trong từ điển tương ứng với một bản ghi gồm ba trường: wordRec = record wordRus: string[25]; // trường Tiếng Nga wordMea: string[200]; // trường nghĩa Tiếng Việt STT:string[6];// trường số thứ tự cho hình ảnh, âm thanh end; Như vậy để chứa các từ trên cây chỉ mất rất ít số bản ghi so với dữ liệu của nó. Với cấu trúc này ta có thể nạp vào chương trình khi chạy tất cả các từ có trong một bộ từ điển lớn khoảng 100.000 từ mà không sợ bị tràn bộ nhớ. Hơn nữa thuật toán xây dựng các thao tác trên cây từ điển này sẽ hoạt động rất nhanh mà không phụ thuộc vào kích thước dữ liệu đầu vào. Khi chương trình hoạt động, mỗi lần ta đánh vào một kí tự (trong quá trình nhập từ để tra) chương trình sẽ phải duyệt cây từ điển để tìm ra các từ gần giống với chuỗi từ mà ta đang nhập nhất. Danh sách các từ này sẽ hiện ra giao diện chương trình. Quá trình duyệt bắt đầu từ nút gốc (Root) dần dần xuống tới các nút con. Đặc điểm của cây từ điển có rất nhiều nút lá, chiều cao của cây lại rất thấp (do số kí tự tạo ra từ không nhiều). Điều này rất thích hợp cho ta trong việc thường xuyên phải tìm kiếm trên cây. Thuật toán xây dựng trên cấu trúc dữ liệu này sẽ đơn giản và hoạt động rất nhanh. Kết luận: Đối với dạng cây Từ Điển đã nói ở trên ta thấy cây Từ Điển là một cây dạng tổng quát có tiền tố chung. Nhưng để ở dạng cây tổng quát thì việc thực hiện các thao tác và các phép xử lý trên cây khó khăn, cho nên cây được chuyển về dạng cây nhị phân với thuật toán chuyển đã trình bày. Qua dạng cấu trúc của cây nhị phân Từ Điển ta có nhận xét chung: Một từ luôn được kết thúc trên nhánh cây con trái. Các từ có tiền tố chung khi chúng là cây con phải của nút con trái của nút chứa kí tự cuối cùng thuộc chuỗi tiền tố. Từ nhận xét trên chúng ta có thể xây dựng được các giải thuật tìm kiếm, thêm, loại bỏ một cách chính xác. CHƯƠNG IV: THIẾT KẾ CHƯƠNG TRÌNH 4.1. TẠO BỘ GÕ VÀ FONT TIẾNG NGA CÓ DẤU NHẤN TRỌNG ÂM CHO NGƯỜI DÙNG 4.1.1. Khái quát về bộ gõ Khi nhập từ, vấn đề xác định kí tự tiếng Nga trên bàn phím đối với người sử dụng là rất khó khăn. Vì thế, chương trình Từ điển này đã hỗ trợ một bộ gõ tiếng Nga cho người dùng trong quá trình tra từ, khi người dùng không nhớ vị trí của kí tự. Tuy thô sơ nhưng giải pháp này phần nào đã mang lại cho người dùng cảm giác thoải mái khi sử dụng bộ gõ. Với giao diện bàn phím nhìn thấy được trên màn hình, người sử dụng chưa quen với bàn phím tiếng Nga có thể xác định được các phím của kí tự tiếng Anh tương ứng với từng ký tự tiếng Nga, qua đó người sử dụng có thể gõ được các từ tiếng Nga một cách dễ dàng. Cũng với giao diện này ta có thể thiết kế để người sử dụng dùng chuột click vào các phím trên bộ gõ để được từ mong muốn. Hình số 6 4.1.2. Cách thiết kế bộ gõ Tiếng Nga và Tiếng Việt cho riêng chương trình Khi sử dụng chương trình Từ điển, nếu trên máy người dùng không cài đặt các chương trình như VietKey, VietWare.... thì không thể thực hiện được chức năng tra từ tiếng Nga cũng như thêm từ tiếng Việt. Vì vậy, việc tạo một bộ gõ tiếng Nga và tiến Việt riêng cho chương trình là điều cần thiết. Bằng font tiếng Nga tự thiết kế và một số font tiếng Việt có sẵn của VietKey, dựa vào bảng mã ASCII của phông chữ chúng ta có thể biết được các mã tương ứng từng chữ cái tiếng Nga cũng như tiếng Việt. Với ngôn ngữ Delphi có hỗ trợ thủ tục chặn thông điệp các phím bấm từ bàn phím (thủ tục PostMessage). Để tạo ra được các ký tự tiếng Nga, tiếng Việt tương ứng với phím gõ chương trình cần phải chặn được thông điệp đến từ bàn phím, xác định được phím gõ tương ứng với phím nào của bàn phím tiếng Nga cũng như tiếng Việt. Bình thường thì ký tự hiển thị trên màn hình sẽ là ký tự Latinh tương ứng phím gõ, do đó để hiển thị được ký tự tiếng Nga chương trình cần phải xóa ký tự Latinh và thay thế bằng ký tự tiếng Nga. Việc thay thế ký tự tiếng Nga được dựa trên mã ASCII của font chữ tiếng Nga được dùng để hiển thị. Hai thủ tục sau trong chương trình sẽ thực hiện việc xóa ký tự Latinh và thay vào ký tự tiếng Nga: 1 PostMessage (frmNgaVietAnh.cboNhapTu.handle, WM_CHAR, 8, 1); 2 PostMessage (frmNgaVietAnh.cboNhapTu.handle, WM_CHAR, MaFont, 1); 1 Dùng để xóa ký tự Latinh với mã ASCII bằng 8 là mã của phím Del. 2 Dùng để hiển thị ký tự Nga có MaFont tương ứng với mã ASCII trong phông tiếng Nga của phím được gõ. Hàm PostMessage cũng được sử dụng tương tự cho ký tự tiếng Việt. 4.1.3. Phương pháp tạo Font Tiếng Nga mới Phông chữ tiếng Nga hiện nay vẫn đang là một vấn đề quan tâm của người dùng. Trong những font chữ hỗ trợ tiếng Nga hiện nay của các phần mềm như Vietkey 2002, VietKey4.0, Unikey,...thì không một font nào có kí tự dấu trọng âm ( là một âm nhấn trên đầu mỗi từ ) nhằm giúp người dùng biết cách phát âm của từ một cách chính xác . Tạo một bộ font mới tưởng chừng là một vấn đề nan giải, nhưng hiện nay với sự hỗ trợ của nhiều phần mềm chuyên dụng thì việc giải quyết không còn mấy khó khăn. Với phần mềm Photographer 4.1, bạn có thể tạo ra một bộ font tùy ý với kí tự do chính bạn thiết kế. Các bước tạo font trên Photographer được tiến hành như sau: - Chọn một bộ font mới, sau đó ứng với từng kí tự trên bàn phím ta có thể vẽ các kí tự bằng các công cụ thiết kế đồ họa được cung cấp sẵn trong phần mềm này. - Sau đó lưu lại để tạo ra một bộ font mơi, đó chính là font RussTimes SNG được sử dụng trong chương trình này. Kí tự dấu nhấn trọng âm sau khi được thiết kế xong. Bảng công cụ thiết kế kí tự của chương trình. Hình số 7 Vị trí của dấu nhấn trọng âm trong bộ font mới tạo. Hình số 8 Nhờ phần mềm này mà chương trình học tiếng Nga đã có một bộ font mới với đầy đủ các chức năng cần thiết cho việc nhập dữ liệu của chương trình. 4.2. PHƯƠNG PHÁP LƯU ÂM THANH VÀ HÌNH ẢNH CHO CHƯƠNG TRÌNH TỪ ĐIỂN 4.2.1. Lưu âm thanh Sau khi thu âm giọng đọc từ bên ngoài vào máy thông qua chương trình JetAudio, hoặc chương trình Recoder. Phiên âm tiếng Nga được tách và lưu thành các file .mp3. Việc tách thành các file (.MP3) sẽ tiết kiệm bộ nhớ hơn so với các file (.WAV). Ngôn ngữ Delphi cho phép mở tập tin âm thanh (.WAV) với hàm PlaySound(). Tuy nhiên hàm này lại không hỗ trợ việc mở các tập tin âm thanh (.MP3), trong khi đó hầu hết các dạng tập tin multimedia, từ âm thanh cho đến phim ảnh, như (.WAV), (,MP3), (.MINI), (.DAT), (.AVI).... đều có thể mở được thông qua đối tượng TMediaPlayer được cung cấp trong ngôn ngữ lập trình. Vì vậy, chương trình đã sử dụng tập hợp các nút nhấn điều khiển thông dụng như Play, Stop, Pause... của đối tượng TMediaPlayer để thực hiện việc mở các tập tin âm thanh. 4.2.2. Lưu hình ảnh Ảnh được nạp vào chương trình thông qua đối tượng TImage của ngôn ngữ lập trình. Để nạp ảnh từ tập tin vào đối tượng TImage, ta sử dụng thuộc tính TImage.Picture và gọi phương thức LoadFromFile. 4.2.3. Cách thức nối kết các file âm thanh và hình vào chương trình Mỗi từ trong từ điển tương ứng với một bản ghi gồm ba trường như sau: wordRec = record wordRus: string[25]; // trường Tiếng Nga wordMea: string[200]; // trường nghĩa Tiếng Việt STT:string[6];// trường số thứ tự cho hình ảnh, âm thanh end; Tên các file âm thanh và hình ảnh được gắn số thứ tự tương ứng với các trường STT của mỗi từ. Vì thế sau khi hiện nghĩa Tiếng Việt, nếu tìm thấy tên file âm thanh hay hình ảnh tương ứng với số thứ tự của trường STT thì các file này được nạp để gọi trong chương trình. 4.3. MỘT SỐ GIẢI THUẬT TRONG CHƯƠNG TRÌNH Các giải thuật hầu hết được cài đặt qua các hàm, thủ tục DLL. Chúng được gọi từ các chương trình DLL khác. Việc sử dụng các hàm, thủ tục DLL giúp người lập trình tránh được những câu lệnh phức tạp, dài dòng đồng thời chương trình trở nên chặt chẽ, dễ hiểu và dễ sửa chữa khi có sai sót trong quá trình thử nghiệm. Một số giải thuật được sử dụng trong chương trình Từ điển Nga – Việt gồm: 4.3.1. Giải thuật tìm kiếm trên cây từ điển - Duyệt cây từ điển bắt đầu từ nút gốc - So sánh từng kí tự của chuỗi cần tìm kiếm có thêm kí tự ‘*’ ở cuối chuỗi với từng nút trên cây. - Nếu kết thúc quá trình duyệt cây gặp kí tự ‘*’ thì thông báo tìm kiếm thành công. Ngược lại thì thông báo quá trình tìm kiếm không thành công. //** Hàm tìm từ trên cây Từ điển Function _FindWord(var p,q: TNode; st: string): Boolean;export;stdcall; var i: integer; ketQua, Found: Boolean; begin i:= 1; p:= Root; Found:=false; ketQua:= false; st:= st + '*'; While (i <length(st)) and (not ketQua) do begin q:=p; if st[i]= #96 then inc(i); {ki tu trong am} if st[i] < p^.Info then begin ketQua:= true; Found:= False; end else if st[i] > p^.Info then if p^.Right nil then begin p:= p^.Right; ketQua:= false; end else begin ketQua:= true; Found:=false; end else if p^.Left nil then if st[i]='*' then begin ketQua:=true; Found:=true; end else begin p:= p^.Left; inc(i); ketQua:=false; end else begin ketQua:=true; Found:=false; end; end; _FindWord:= Found; end; 4.3.2. Các bước tra từ - Gọi hàm tìm từ. - Nếu tìm không thành công thì thông báo lỗi “Từ không có trong từ điển”. - Ngược lại: + Đọc tiếp các nút chữ số đánh dấu số thứ tự của các bản ghi trong file dữ liệu. + Đổi chuỗi số đọc được thành số. + Mở file dữ liệu, chuyển con trỏ file vị trí bản ghi cần tìm. + Xuất trường nghĩa của bản ghi ra màn hình. //** Thủ tục tra từ trong từ điển procedure_SearchWordNV(var keyWor: integer; st: string; MForm: TfrmNgaVietAnh); export;stdcall; var p,q:TNode; findWor:boolean; f:file of TWordNV; word:TWordNV; Begin st:= st + '*'; findWor:= _FindWord(p,q,st); If not findWor then ShowMessage('Khong tim thay tu trong tu dien') Else begin st:= ''; repeat { Doc thong tin cac nut luu so khoa-so thu tu ban ghi} begin p:= p^.Left; st:= st + p^.Info; end; until p^.Left = nil; keyWor:= StrToInt(st); AssignFile(f,FileName); Reset(f); Seek(f,keyWor); read(f,word); MForm.retTuViet.Lines.CommaText:= word.VieMean; MForm.lblHienChu.Caption:=word.RusWord; CloseFile(f); end; end; 4.3.3. Các bước thêm từ - Gọi thủ tục tìm từ. - Nếu tìm thành công thì thông báo “Từ đã có trong từ điển”. - Ngược lại: + Thêm từ vào cuối danh sách. + Thêm từ vào cuối file dữ liệu. + Thêm từ vào cây. //** Thủ tục thêm từ trong từ điển procedure _AddWord(MForm: TfrmNgaVietAnh; stWor: string; stMea: string); export; stdcall; var p,q: TNode; findWor: Boolean; st: string; f: file of TWordNV; recNum: integer; begin st:= stWor + '*'; findWor:= _FindWord(p,q,st); // Ham tim tu If findWor then ShowMessage('Tu da co trong tu dien')//_ErrorMsg(3) // Thong bao co tu trong Tu Dien Else begin AssignFile(f,FileName); Reset(f); try recNum:= FileSize(f); finally CloseFile(f); end; st:= st + IntToStr(recNum); // Gan so ban ghi vao chuoi tu de de tim MForm.lstDSNV.Items.Add(stWor); _AddToFile(stWor,stMea); _AddToTree(st); // Thu tuc "Them tu vao cay" ShowMessage('T míi ®· ®­ỵc l­u!'); end; end; 4.3.4. Các bước sửa từ - Gọi thủ tục tìm từ. - Nếu tìm không thành công thì thông báo “Không có từ trong từ điển”. - Ngược lại: + Mở file dữ liệu. + Đưa con trỏ file đến vị trí bản ghi tương ứng. + Ghi đè bản ghi mới lên bản ghi cũ. / /** Thủ tục sửa từ trong từ điển procedure _RepairWord(stOld:string; stWor: string; stMea: string);export; stdcall; var f: file of TWordNV; findWor:boolean; key:integer; p,q:TNode; worRec:TWordNV; st: string; begin key:=0; st:= stOld + '*'; findWor:= _FindWord(p,q,st); If not findWor then ShowMessage('Tu khong co trong tu dien') //_ErrorMsg(2) Else begin //Doc khoa Repeat p:= p^.Left; key:= key + StrToInt(p^.Info); until p^.Left= nil; worRec.RusWord:= stWor; worRec.VieMean:= stMea; //Mo file AssignFile(f,FileName); Reset(f); //Ghi de len ban ghi hien hanh Seek(f,key); write(f,worRec); CloseFile(f); ShowMessage('Từ sửa đã được lưu!'); end; 4.3.5. Các bước xóa từ - Gọi thủ tục tìm từ. - Nếu không tìm thấy từ thì thông báo “Từ không có trong từ điển”. - Ngược lại: + Xoá trường tiếng Nga trong danh sách hiển thị từ. + Xoá bản ghi chứa từ trong file. + Xoá kí tự “*” đánh dấu ở cuối từ cần xoá trên cây. //** Thủ tục xóa từ trong từ điển procedure _DelWord(MForm:TfrmNgaVietAnh; st: string);export;stdcall; var findWor:boolean; p, q: TNode; begin st:= st + '*'; findWor:= _FindWord(p,q,st); If not findWor then ShowMessage('Khong tim thay tu trong tu dien')//_ErrorMsg(2) Else begin DelWordInFile(p); DelWordInTree(q,p); DelWordInList(MForm, st); ShowMessage('Từ đã được xóa khỏi Từ Điển!'); end; end; 4.3.6. Giải thuật tìm kiếm nhị phân để chèn từ vào đúng vị trí trong danh sách - Tìm kiếm trong danh sách đã được sắp xếp thứ tự. - Tìm vị trí giữa của danh sách ( i ). - Lần lượt so sánh từng kí tự của từ cần chèn (giả sử là x) với kí tự của từ tại vị trí i của danh sách (giả sử là y) theo qui tắc sau: + Nếu x=y thì từ được tìm thấy. + Nếu x<y thì từ có trong khoảng từ đầu danh sách đến kí tự thứ i-1. + Nếu x>y thì kí tự có phạm vi phía sau y. - Sau khi xác định đúng vị trí thì từ sẽ được chèn vào danh sách. //** Thủ tục tìm kiếm và chèn từ Function FindCharFirst(st:string;len:word):word;export;stdcall; Var Tim:boolean; l,r,m:word; begin Tim:=false; l:= 0; r:= len; While (l<=r) and (Tim = false) do begin m:=(l+r)div 2; If st<frmNgaVietAnh.lstDSNV.Items[m] then r:=m-1 Else If st>frmNgaVietAnh.lstDSNV.Items[m] then l:=m+1 else Tim:= true; end; If l<= r then begin While st= frmNgaVietAnh.lstDSNV.Items[m] do m:=m-1; m:= m+1; end; FindCharFirst:= m; end; {===========} Function FindCharNext(st:string;index:word):word;export;stdcall; var m:word; begin While st< frmNgaVietAnh.lstDSNV.Items[index] do index:=index+1; If st=frmNgaVietAnh.lstDSNV.Items[index] then m:=index; If st> frmNgaVietAnh.lstDSNV.Items[index] then m:=index-1; FindCharNext:=m; end; {===========} Procedure _FindWordInDS(st:string;len:word);export;stdcall; begin If st = '' then index:= 0; If length(st)=1 then index := FindCharFirst(st,len) Else index := FindCharNext(st,index); {Di chuyen den vi tri can tim trong danh sach} SendMessage(frmNgaVietAnh.lstDSNV.Handle, lb_SetTopIndex, frmNgaVietAnh.lstDSNV.ItemIndex-1, 0); end; 4.3.7. Mã lệnh tạo bộ gõ Tiếng Việt //** Thủ tục tạo Bộ gõ Tiếng Việt dùng cho các đối tượng có FONT Việt procedure _VietFont; var prevchar, key:char; begin if msg.message=WM_CHAR then begin key:=chr(msg.wParam); case key of '1':case prevchar of 'a','e','o','u','y','i',chr(246),chr(244):key:=chr(249); 'A','E','O','U','Y','I',chr(214),chr(212):key:=chr(217); chr(234),chr(202),chr(226),chr(194):begin PostMessage(Editor.handle,WM_CHAR,8,1); PostMessage(Editor.handle,WM_CHAR,ord(prevchar)-1,1); handled:=true; end; end; '2':case prevchar of 'a','e','o','u','y','i',chr(246),chr(244):key:=chr(248); 'A','E','O','U','Y','I',chr(214),chr(212):key:=chr(216); chr(234),chr(202),chr(226),chr(194):begin PostMessage(Editor.handle,WM_CHAR,8,1); PostMessage(Editor.handle,WM_CHAR,ord(prevchar)-2,1); handled:=true; end; end; '3':case prevchar of 'a','e','o','u','y','i',chr(246),chr(244):key:=chr(251); 'A','E','O','U','Y','I',chr(214),chr(212):key:=chr(219); chr(234),chr(202):begin PostMessage(Editor.handle,WM_CHAR,8,1); PostMessage(Editor.handle,WM_CHAR,ord(prevchar)+16,1); handled:=true; end; chr(226),chr(194):begin PostMessage(Editor.handle,WM_CHAR,8,1); PostMessage(Editor.handle,WM_CHAR,ord(prevchar)+3,1); handled:=true; end; end; '4':case prevchar of 'a','e','o','u','y','i',chr(246),chr(244):key:=chr(245); 'A','E','O','U','Y','I',chr(214),chr(212):key:=chr(213); chr(234),chr(202):begin PostMessage(Editor.handle,WM_CHAR,8,1); PostMessage(Editor.handle,WM_CHAR,ord(prevchar)+18,1); handled:=true; end; chr(226),chr(194):begin PostMessage(Editor.handle,WM_CHAR,8,1); PostMessage(Editor.handle,WM_CHAR,ord(prevchar)+1,1); handled:=true; end; end; '5':case prevchar of 'a','e','o','u','y','i',chr(246),chr(244):key:=chr(239); 'A','E','O','U','Y','I',chr(214),chr(212):key:=chr(207); chr(234),chr(202):begin PostMessage(Editor.handle,WM_CHAR,8,1); PostMessage(Editor.handle,WM_CHAR,ord(prevchar)+1,1); handled:=true; end; chr(226),chr(194):begin PostMessage(Editor.handle,WM_CHAR,8,1); PostMessage(Editor.handle,WM_CHAR,ord(prevchar)+2,1); handled:=true; end; end; '6':case prevchar of 'a','e','o':key:=chr(226); 'A','E','O':key:=chr(194); end; '7':begin if prevchar in ['U','O','u','o'] then begin postmessage(Editor.handle,WM_CHAR,8,1); handled:=true; end; case prevchar of 'u':postmessage(Editor.handle,WM_CHAR,246,1); 'U':postmessage(Editor.handle,WM_CHAR,214,1); 'o':postmessage(Editor.handle,WM_CHAR,244,1); 'O':postmessage(Editor.handle,WM_CHAR,212,1); end end; '8':case prevchar of 'a':key:=chr(234); 'A':key:=chr(202); end; '9':begin if prevchar in ['D','d'] then begin postmessage(Editor.handle,WM_CHAR,8,1); handled:=true; end; case prevchar of 'd':postmessage(Editor.handle,WM_CHAR,241,1); 'D':postmessage(Editor.handle,WM_CHAR,209,1); end; end; end; prevchar:=key; msg.wparam:=ord(key); end; end; 4.3.8. Mã lệnh tạo bộ gõ Tiếng Nga //**Thủ tục đổi mã font procedure DoiMaFont(formTuDien: TfrmNgaVietAnh; MaFont: byte); begin PostMessage(formTuDien.cboNhapTu.handle,WM_CHAR,8,1); PostMessage(formTuDien.cboNhapTu.handle,WM_CHAR,MaFont,1); end; {==============} //** Thủ tục chọn font cho các đối tượng tiếng Nga procedure _ChoseFont(key:char; chose: byte);export;stdcall; begin case key of 'f':DoiMaFont(chose,224); 'F':DoiMaFont(chose,192); ',':DoiMaFont(chose,225); '<':DoiMaFont(chose,193); 'd':DoiMaFont(chose,226); 'D':DoiMaFont(chose,194); 'u':DoiMaFont(chose,227); 'U':DoiMaFont(chose,195); 'l':DoiMaFont(chose,228); 'L':DoiMaFont(chose,196); 't':DoiMaFont(chose,229); 'T':DoiMaFont(chose,197); '/':DoiMaFont(chose,184); '?':DoiMaFont(chose,168); ';':DoiMaFont(chose,230); ':':DoiMaFont(chose,198); 'p':DoiMaFont(chose,231); 'P':DoiMaFont(chose,199); 'b':DoiMaFont(chose,232); 'B':DoiMaFont(chose,200); 'q':DoiMaFont(chose,233); 'Q':DoiMaFont(chose,201); 'r':DoiMaFont(chose,234); 'R':DoiMaFont(chose,202); 'k':DoiMaFont(chose,235); 'K':DoiMaFont(chose,202); 'v':DoiMaFont(chose,236); 'V':DoiMaFont(chose,204); 'y':DoiMaFont(chose,237); 'Y':DoiMaFont(chose,205); 'j':DoiMaFont(chose,238); 'J':DoiMaFont(chose,206); 'g':DoiMaFont(chose,239); 'G':DoiMaFont(chose,207); 'h':DoiMaFont(chose,240); 'H':DoiMaFont(chose,208); 'c':DoiMaFont(chose,241); 'C':DoiMaFont(chose,209); 'n':DoiMaFont(chose,242); 'N':DoiMaFont(chose,210); 'e':DoiMaFont(chose,243); 'E':DoiMaFont(chose,211); 'a':DoiMaFont(chose,244); 'A':DoiMaFont(chose,212); '[':DoiMaFont(chose,245); '{':DoiMaFont(chose,213); 'w':DoiMaFont(chose,246); 'W':DoiMaFont(chose,214); 'x':DoiMaFont(chose,247); 'X':DoiMaFont(chose,215); 'i':DoiMaFont(chose,248); 'I':DoiMaFont(chose,216); 'o':DoiMaFont(chose,249); 'O':DoiMaFont(chose,217); ']':DoiMaFont(chose,250); '}{':DoiMaFont(chose,218); 's':DoiMaFont(chose,251); 'S':DoiMaFont(chose,219); 'm':DoiMaFont(chose,252); 'M':DoiMaFont(chose,220); chr(39):DoiMaFont(chose,253); '"':DoiMaFont(chose,221); '.':DoiMaFont(chose,254); '>':DoiMaFont(chose,222); 'z':DoiMaFont(chose,255); 'Z':DoiMaFont(chose,223); end; end; 4.4. GIAO DIỆN CỦA CHƯƠNG TRÌNH VÀ CÁCH THỨC HOẠT ĐỘNG 4.4.1. Giao diện chính của chương trình với các menu thành phần Tất cả các chức năng đều được thể hiện rõ trên giao diện chính của chương trình. Từ Form chính, người sử dụng có thể kích chuột để chọn một trong các menu có sẳn. Ứng với từng menu được chọn, Form chính sẽ nối kết đến từng Form DLL tương ứng được tạo sẳn. Hình số 9 Menu Thực hành: dùng nối kết tới Form luyện nghe hoặc Form làm bài tập trắc nghiệm. Menu Trợ giúp: nối kết tới trang giới thiệu đề tài hoặc trang hướng dẫn sử dụng chương trình. Menu Từ điển: nối kết tới Form Từ điển Nga – Việt hoặc Từ điển Nga – Anh. Menu Ngữ pháp: nối kết tới Form ngữ pháp tiếng Nga. Hình số 10 4.4.2. Giao diện Từ điển Từ điển gồm các phím chức năng cơ bản như : tra từ, trở về từ trước đó, phần tiện ích với các chức năng: thêm từ, sửa từ, xóa từ. Nhấn nút tra từ sau khi chọn một từ bất kỳ trong danh sách, sẽ xuất hiện nghĩa của từ và hình ảnh (nếu có). Khi gõ từng kí tự vào ô nhập từ, danh sách các từ có kí tự tương ứng được nhảy đến tự động nhằm giúp người sử dụng trong quá trình tra từ. Trở về từ trước: đó giúp người dùng tiết kiệm thời gian trong việc tìm lại nghĩa những từ mình đã tra. Ngoài ra Từ điển còn cung cấp thêm hai nút chức năng: hiển thị bàn phím và thay đổi kích cỡ chữ (có 3 cấp độ: chữ lớn, chữ trung bình và chữ nhỏ). Hình số 11 4.4.3 Giao diện thực hành Trên giao diện này người dùng có thể chọn những bài tập có săn, bài tập dưới dạng trắc nghiệm, sau khi chọn được câu trả lời thì ấn nút Tiếp theo để sang cau khác , chọn mục sửa lỗi đẻ kiểm tra câu trả lời có đúng hay không Ngườ dùng có thể thoát khỏi chương trình thực hành bằng cách ấn nút thoát Hình số 12 Kết Luận 1. Kết quả chương trình đã đạt được : Chương trình đã hoàn thiện công cụ tra từ , và đang hoàn thiện phần thực hành 2. Những hạn chế Khi bắt đầu thực hiện, chương trình gặp phải một số khó khăn sau: - Vì chương trình học Tiếng Nga là một ứng dụng mới nên việc tham khảo về nội dung và kiểu dáng gặp không ít khó khăn. - Một số font tiếng Nga có sẳn không hỗ trợ dấu nhấn trọng âm của từ, do đó trong quá trình sử dụng, người dùng bắt buộc phải chèn thêm dấu này ở font khác. Điều này gây mất thời gian và khó khăn cho người dùng. - Mã kí tự tiếng Nga không theo thứ tự nhất định gây khó khăn cho việc sắp xếp từ trong từ điển. - Việc nhập dữ liệu cho chương trình gặp trở ngại trong việc chuyển đổi bộ gõ giữa tiếng Nga và tiếng Việt. - Cấu trúc con trỏ là kiểu cấu trúc tương đối khó thực hiện khi mới bắt đầu làm quen. 3. Hướng khắc phục và phát triển chương trình Để khắc phục những thiếu sót còn lại, cần có một thời gian dài tìm hiểu và thử nghiệm thực tế. Ngoài ra chương trình có thể phát triển thêm: + Các tài liệu ngữ pháp nâng cao kèm theo bài tập ứng dụng. + Các bài nghe với đủ các cấp độ và cho phép người sử dụng đánh giá được trình độ nghe của mình. ......... TÀI LIỆU THAM KHẢO 1. Đỗ Xuân Lôi – “Cấu trúc dữ liệu và giải thuật” –Nhà xuất bản khoa học và kỹ thuật. 2. J.Courtin I.Kowarski – “Nhập môn thuật toán và cấu trúc dữ liệu” –do nhóm tác giả: Đào Nam Anh, Trần Đình Quế, Phạm Ngọc Khôi dịch và hiệu đính. 3. N.Wirth – “Lập trình nâng cao với các kiểu dữ liệu cấu trúc của PASCAL” (2 tập) –do Lê Minh Trung dịch. 4. Nguyễn Trung Trực – “Cấu trúc dữ liệu” –Trường Đại Học Bách Khoa TP.HCM. 5. Robert Sedgewick – “Cẩm nang thuật toán” – Tập 1: “Các thuật toán thông dụng” –Nhà xuất bản khoa học và kỹ thuật. 6. Tập san “Tin học và nhà trường” – Số 1-2 (40 - 41). 7. Lê Phương Lan & Hoàng Đức Hải – “Giáo trình lý thuyết và bài tập Borland DelPhi” –Nhà xuất bản giáo dục. 8. Lê Hữu Đạt (Chủ biên)– “Các kỹ xảo lập trình với Microsoft Visual Basic và Borland Delphi” –Nhà xuất bản giáo dục. 9. Trần Hạnh Nhi, Dương Anh Đức, Hoàng Kiếm – “Nhập môn cấu trúc dữ liệu và giải thuật” –Đại học Khoa Học Tự Nhiên MỤC LỤC LỜI NÓI ĐẦU............................................................................................................................ 2 CHƯƠNG I. GIỚI THIỆU ĐỀ TÀI VÀ CÔNG CỤ LẬP TRÌNH................. 3 1.1. Giới thiệu đề tài.......... 3 1.1.1. Mục tiêu đề tài................................................................................................................... 3 1.1.2. Yêu cầu đề tài.................................................................................................................... 3 1.2.Công cụ lậ trình....................... 4 1.2.1.Các tính năng của môi trường phát triển ứng dụng Delphi ............................................ . 4 1.2.2.Cấu trúc chương trình Delphi và Unit................................................................................ 5 1.2.3.Lệnh điều khiển trong object pascal................................................................................... 7 1.2.4.Các kiểu dữ liệu trong ngôn ngữ Object Pascal................................................................. .7 1.2.5.Hàm và thủ tục................................................................................................................... .9 1.2.6.Form và các thành phần điều khiển.................................................................................. 11 1.2.7.Lập trình đò họa , in ấn , multimedia , và các đối tượng có liên quan.............................. 12 1.2.8.Thư viện liên kết động ..................................................................................................... 13 1.2.9.Giới thiệu về Win32 API và hệ thống thông điệp............................................................ 14 CHƯƠNG II : TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT......................................................................................... 15 2.1. Giới thiệu......................................................................................................... 15 2.1.1.Giải thuật và cấu trúc dữ liệu .......................................................................................... 15 2.1.2.Cấu trúc dữ liệu và các vấn đề liên quan......................................................................... 15 2.1.3.Các tiêu chuẩn đánh giá cấu trúc dữ liệu......................................................................... 15 2.1.4.Đánh giá độ phức tạp giải thuật....................................................................................... 15 2.2. Sắp xếp và tìm kiếm......................................................................................... 16 2.2.1.Một số giải thuật sắp xếp.................................................................................................. 16 2.2.2.Các giải thuật tìm kiếm nội................................................................................................17 2.3.Cấu trúc cây.......................................................................................................18 2.3.1.Định nghĩa và khái niệm....................................................................................................18 2.3.2.Các cách biểu diễn cây..................................................................................................... 19 2.3.3.Cây nhị phân..................................................................................................................... 19 2.3.4.Biểu diễn cây tổng quát bằng cây nhị phân...................................................................... 20 2.3.5.Cây nhị phân tìm kiếm...................................................................................................... 21 2.3.6.Cây nhị phân cân đối........................................................................................................ 22 2.3.7.Cây nhị phân tìm kiếm tối ưu........................................................................................... 22 CHƯƠNG III : TỔ CHỨC LƯU TRỮ CÂY TỪ ĐIỂN........................ 23 CHƯƠNG IV : THIẾT KẾT CHƯƠNG TRÌNH.................................. 26 4.1.Tạo bộ gõ và font nhần tiếng Nga có dấu nhấn trọng âm cho người dùng...... 26 4.1.1.Khái quát về bộ gõ........................................................................................................... 26 4.1.2.Cách thiết kế bộ gõ tiếng Nga và tiếng Việt cho chương trình........................................ 26 4.1.3.Phương pháp tạo font tiếng Nga mới................................................................................ 27 4.2.Phương pháp lưu âm thanh và hình ảnh cho chương trình từ điển....................29 4.3.Một số giải thuật trong chương trình.................................................................30 4.4.Giao diện của chương trình và cách thức hoạt động......................................... 42 KẾT LUẬN............................................................................................. 46 TÀI LIỆU THAM KHẢO...................................................................... 47 MỤC LỤC 48