guitar83vn
New Member
Download miễn phí Luận văn Xây dựng chương trình từ điển tiếng Nga
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 chức 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
Để tải tài liệu này, vui lòng Trả lời bài viết, Mods sẽ gửi Link download cho bạn ngay qua hòm tin nhắn.
Ketnooi -
You must be registered for see links
Ai cần tài liệu gì mà không tìm thấy ở Ketnooi, đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
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 hay 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ử (hay 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 thay mặt 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 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 độ...
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 hay 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ử (hay 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 thay mặt 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 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 độ...