tailieunhanh - Algorithms Programming - Thuật Toán Số phần 4

Cấu trúc dữ liệu và Giải thuật Như ở ví dụ trên, ta có thể xây dựng bảng khoá gồm 2 trường, trường khoá chứa điểm và trường liên kết chứa số thứ tự của người có điểm tương ứng trong bảng ban đầu | Cấu trúc dữ liệu và Giải thuật 83 có thể thực hiện được bằng cách dựa vào trường liên kết của bản ghi tương ứng thuộc bảng khoá. Như ở ví dụ trên ta có thể xây dựng bảng khoá gồm 2 trường trường khoá chứa điểm và trường liên kết chứa số thứ tự của người có điểm tương ứng trong bảng ban đầu Điểm thi STT 20 1 25 2 18 3 21 4 Sau khi sắp xếp theo trật tự điểm cao nhất tới điểm thấp nhất bảng khoá sẽ trở thành Điểm thi STT 25 2 21 4 20 1 18 3 Dựa vào bảng khoá ta có thể biết được rằng người có điểm cao nhất là người mang số thứ tự 2 tiếp theo là người mang số thứ tự 4 tiếp nữa là người mang số thứ tự 1 và cuối cùng là người mang số thứ tự 3 còn muốn liệt kê danh sách đầy đủ thì ta chỉ việc đối chiếu với bảng ban đầu và liệt kê theo thứ tự 2 4 1 3. Có thể còn cải tiến tốt hơn dựa vào nhận xét sau Trong bảng khoá nội dung của trường khoá hoàn toàn có thể suy ra được từ trường liên kết bằng cách Dựa vào trường liên kết tìm tới bản ghi tương ứng trong bảng chính rồi truy xuất trường khoá trong bảng chính. Như ví dụ trên thì người mang số thứ tự 1 chắc chắn sẽ phải có điểm thi là 20 còn người mang số thứ tự 3 thì chắc chắn phải có điểm thi là 18. Vậy thì bảng khoá có thể loại bỏ đi trường khoá mà chỉ giữ lại trường liên kết. Trong trường hợp các phần tử trong bảng ban đầu được đánh số từ 1 tới n và trường liên kết chính là số thứ tự của bản ghi trong bảng ban đầu như ở ví dụ trên người ta gọi kỹ thuật này là kỹ thuật sắp xếp bằng chỉ số Bảng ban đầu không hề bị ảnh hưởng gì cả việc sắp xếp chỉ đơn thuần là đánh lại chỉ số cho các bản ghi theo thứ tự sắp xếp. Cụ thể hơn Nếu r 1 r 2 . r n là các bản ghi cần sắp xếp theo một thứ tự nhất định thì việc sắp xếp bằng chỉ số tức là xây dựng một dãy Index 1 Index 2 . Index n mà ở đây Index j Chỉ số của bản ghi sẽ đứng thứ j khi sắp thứ tự Bản ghi r index j sẽ phải đứng sau j - 1 bản ghi khác khi sắp xếp Do khoá có vai trò đặc biệt như vậy nên sau này khi trình bày các giải thuật ta sẽ coi khoá như đại diện cho các bản ghi và để cho .

• Kỹ thuật lập trình
• Tài liệu IT
• Tài liệu lập trình
• Thuật toán
• Toán logic
• Giải thuật
• Hàm số
• thủ thuật lập trình
• tài chính
• ngân hàng
• kế toán
• quản lý tài chính
• tài liệu tài chính
• tài liệu về ngân hàng
• Tài liệu kinh doanh
• hướng dẫn hạch toán
• Hạch toán doanh nghiệp
• Tài sản doanh nghiệp