TAILIEUCHUNG - Giáo trình giải thuật của Nguyễn Văn Linh part 15

Tập tin chỉ mục (index file) Một cách khác thường gặp là tập tin được sắp xếp theo khoá, rồi chúng ta tiến hành tìm kiếm như là tìm một từ trong từ điển, tức là tìm kiếm theo từ đầu tiên trên mỗi trang. Ðể thực hiện được điều đó ta sử dụng hai tập tin: Tập tin chính và tập tin chỉ mục thưa (sparse index). Tập tin chính bao gồm các khối lưu các mẩu tin sắp thứ tự theo giá trị khóa. Tập tin chỉ mục thưa bao gồm các khối chứa các cặp (x,p) trong. | Giải thuật CTDL và giải thuật lưu trữ ngoài Tập tin chỉ mục index file Tổ chức Một cách khác thường gặp là tập tin được sắp xếp theo khoá rồi chúng ta tiến hành tìm kiếm như là tìm một từ trong từ điển tức là tìm kiếm theo từ đầu tiên trên mỗi trang. Để thực hiện được điều đó ta sử dụng hai tập tin Tập tin chính và tập tin chỉ mục thưa sparse index . Tập tin chính bao gồm các khối lưu các mẩu tin sắp thứ tự theo giá trị khóa. Tập tin chỉ mục thưa bao gồm các khối chứa các cặp x p trong đó x là khoá của mẩu tin đầu tiên trong một khối của tập tin chính còn p là con trỏ trỏ đến khối đó. Ví dụ 4-6 Ta có tập tin được tổ chức thành tập tin chỉ mục với mỗi khối trong tập tin chính lưu trữ được tối đa 3 mẩu tin mỗi khối trong tập tin chỉ mục lưu trữ được tối đa 4 cặp khoá - con trỏ. Hình sau minh hoạ tập tin chỉ mục này. Nguyễn Văn Linh Trang 96 Sưu tầm bởi Giải thuật CTDL và giải thuật lưu trữ ngoài chính Bi B2 B3 B4 B5 B6 Hình 4-3 Tập tin chỉ mục Tìm kiếm Để tìm mẩu tin r có khoá x ta phải tìm cặp z p với z là giá trị lớn nhất và z x. Mẩu tin r có khoá x nếu tồn tại thì sẽ nằm trong khối được trỏ bởi p. Chẳng hạn để tìm mẩu tin r có khoá 46 trong tập tin của ví dụ 4-6 ta tìm trong tập tin chỉ mục được cặp 42 p trong đó 42 là giá trị khoá lớn nhất trong tập tin chỉ mục mà 42 46 và p là con trỏ trỏ tới khối B5 của tập tin chính. Trong khối B5 ta tìm thấy mẩu tin có khoá 46. Việc tìm một mẩu tin trong một khối của tập tin chính có thể tiến hành bằng tìm kiếm tuần tự hoặc bằng tìm kiếm nhị phân bởi lẽ các mẩu tin trong một khối đã được săp thứ tự. Thêm mẩu tin Giả sử tập tin chính được lưu trong các khối B1 B2 . Bm. Để xen một mẩu tin r với khóa x vào trong tập tin ta phải dùng thủ tục tìm kiếm để xác định một khối Bi nào đó. Nếu tìm thấy thì thông báo mẩu tin đã tồn tại ngược lại Bi là nơi có thể chứa mẩu tin r. Nếu Bị còn chỗ trống thì xen r vào đúng vị trí của nó trong Bị. Ta phải chỉnh lại tập tin chỉ mục nếu mẩu tin mới .

• Kỹ thuật lập trình
• Kỹ thuật lập trình
• giải thuật
• hướng dẫn giải thuật
• cấu trúc dữ liệu
• lập trình
• kỹ thuật máy tính C
• kỹ thuật lập trình C
• giáo trình kỹ thuật lập trình C
• bài tập kỹ thuật lập trình C
• tài liệu kỹ thuật lập trình C
• chuyên ngành kỹ thuật lập trình
• Bài tập kỹ thuật lập trình
• Tài liệu kỹ thuật lập trình
• Bài giảng kỹ thuật lập trình
• Ưng dụng kỹ thuật lập trình
• Ngôn ngữ C
• kỹ thuật máy tính
• môn kỹ thuật lập trình
• ôn tập kỹ thuật lập trình
• cách học kỹ thuật lập trình
• kiến thức kỹ thuật lập trình
• học môn kỹ thuật lập trình
• Đề thi Kỹ thuật lập trình cơ bản
• Câu hỏi Kỹ thuật lập trình cơ bản
• Luyện thi Kỹ thuật lập trình cơ bản
• Ôn thi Kỹ thuật lập trình cơ bản
• Bài thi Kỹ thuật lập trình cơ bản
• Tài liệu Kỹ thuật lập trình cơ bản
• giáo trình kỹ thuật lập trình
• thủ thuật lập trình
• lập trình căn bản
• kỹ thuật phần mềm
• chương trình lập trình
• giáo trình lập trình
• lập trình hướng đối tượng
• tài liệu lập trình
• chuyên ngành lập trình
• tổng quan về lập trình
• Tổng quan về kỹ thuật lập trình
• Lập trình tốt
• Nguyên tắc lập trình
• Ngôn ngữ lập trình
• ngôn ngữ C++
• Kỹ thuật lập trình căn bản
• Kỹ thuật lập trình nâng cao
• Lập trình C căn bản
• Lập trình C nâng cao