Giáo trình phân tích khả năng ứng dụng kĩ thuật thiết kế giải thuật ứng dụng trong sản xuất p10 pot

Giải thuật CTDL và giải thuật lưu trữ ngoài

Một là xoá mẩu tin cần xoá trong khối lưu trữ nó, nếu sau khi xoá, khối trở nên rỗng

thì xoá khối khỏi danh sách (giải phóng bộ nhớ).

Hai là đánh dấu xoá mẩu tin bằng một cách nào đó. Nghĩa là chỉ xoá mẩu tin một

cách logic, vùng không gian nhớ vẫn còn dành cho mẩu tin. Việc đánh dấu có thể

được thực hiện bằng một trong hai cách:

• Thay thế mẩu tin bằng một giá trị nào đó mà giá trị này không bao giờ là

giá trị thật của bất kỳ một mẩu tin nào.

• Mỗi một mẩu tin có một bít xóa, bình thường bit xóa của mẩu tin có giá

trị 0, muốn xóa mẩu tin ta đặt cho bit xóa giá trị 1. Với phương pháp này

thì một mẩu tin sau khi bị đánh dấu xoá cũng có thể phục hồi được bằng

cách đặt bit xoá của mẩu tin giá trị 0.

4.5.1.6 Ðánh giá

Ðây là một phương pháp tổ chức tập tin đơn giản nhất nhưng kém hiệu quả nhất. Ta

thấy tập tin là một danh sách liên kết của các khối nên các thao tác trên tập tin đều

đòi hỏi phải truy xuất hầu như tất cả các khối, từ khối đầu tiên đến khối cuối cùng.

Giả sử tập tin có n mẩu tin và mỗi khối lưu trữ được k mẩu tin thì toàn bộ tập tin

được lưu trữ trong k

n

khối, do đó mỗi lần tìm (hoặc thêm hoặc sửa hoặc xoá) một

mẩu tin thì phải truy xuất k

n

khối.

4.5.2 Tăng tốc độ cho các thao tác tập tin

Nhược điểm của cách tổ chức tập tin tuần tự ở trên là các thao tác trên tập tin rất

chậm. Ðể cải thiện tốc độ thao tác trên tập tin, chúng ta phải tìm cách giảm số lần

truy xuất khối. Muốn vậy phải tìm các cấu trúc sao cho khi tìm một mẩu tin chỉ cần

phép truy xuất một số nhỏ các khối của tập tin.

Ðể tạo ra các tổ chức tập tin như vậy chúng ta phải giả sử rằng mỗi mẩu tin có một

khoá (key), đó là một tập hợp các trường mà căn cứ vào đó ta có thể phân biệt các

mẩu tin với nhau. Hai mẩu tin khác nhau thì khoá của chúng phải khác nhau.

Chẳng hạn mã sinh viên trong mẩu tin về sinh viên, biển số xe trong quản lí các

phương tiện vận tải đường bộ.

Sau đây ta sẽ xét một số cấu trúc như thế.

4.5.3 Tập tin băm (hash files)

4.5.3.1 Tổ chức

Ta sẽ sử dụng bảng băm mở để lưu trữ tập tin. Bảng băm là một bảng có m phần tử,

mỗi phần tử được đánh số từ 0 đến m-1 (đơn giản nhất là mảng một chiều B gồm m

phần tử B[0], B[1], ..., B[m-1]). Mỗi phần tử là một con trỏ, trỏ tới phần tử đầu tiên

của danh sách liên kết các khối.

Nguyễn Văn Linh Trang 94 Click to buy NOW!

PDF-XChange Viewer

www.docu-track.co m

Click to buy NOW!

PDF-XChange Viewer

www.docu-track.co m