Kiểu dữ liệu có cấu trúc – Phần 2

Đặc tả thuộc tính

Ðể giải quyết vấn đề lãng phí bộ nhớ, trong một số ngôn ngữ lập trình có một loại CTDL gọi là mẩu tin có cấu trúc thay đổi.

Mỗi một cấu trúc sẽ có một số trường giống nhau cho mọi loại mẩu tin và một số trường khác nhau cho từng loại mẩu tin. Các trường giống nhau gọi là phần chung hay phần tĩnh, các trường khác nhau này gọi là phần động hay phần thay đổi của mẩu tin.

Chẳng hạn đối với bài toán nêu trên thì mỗi công nhân được lưu trong một mẩu tin, có các trường thuộc phần chung đó là Ho_Ten, Ngay_Cong, Tien_Luong. Ngoài ra tùy thuộc vào loại công nhân là biên chế hay hợp đồng mà có các trường riêng. Ðối với công nhân trong biên chế ta cần thêm các trường He_So và Nghi_Bhxh để lưu trữ hệ số lương và số ngày nghỉ bảo hiểm xã hội. Ðối với công nhân hợp đồng ta chỉ cần thêm một trường là Gia_Cong_Nhat để lưu trữ giá công nhật cho mỗi người.

Khai báo trong Pascal như sau:

TYPE

loai_cong_nhan = (bien_che,hop_dong);

VAR

Cong_Nhan : RECORD

ho_ten: String[20];

ngay_cong: Real;

luong: Real;

CASE loai: loai_cong_nhan OF

bien_che:

(he_so: Real;

nghi_bhxh:Real);

hop_dong:

(gia_cong_nhat: Real);

END;

Khai báo trên định nghĩa một mẩu tin có cấu trúc thay đổi. Mẩu tin luôn luôn có các trường Ho_Ten, Ngay_Cong, Luong và Loai. Khi giá trị của Loai = "bien_che" thì mẩu tin còn có các trường He_So và Nghi_Bhxh, trong khi đó nếu giá trị của Loai = "hop_dong" thì nó lại có trường Gia_Cong_Nhat.

Đặc tả phép toán

Phép toán lựa chọn các phần tử của mẩu tin có cấu trúc thay đổi cũng giống như mẩu tin bình thường. Chẳng hạn ta có thể sử dụng Cong_Nhan.Luong, Cong_Nhan.He_So hay Cong_Nhan.Gia_Cong_Nhat. Tuy nhiên các trường thuộc phần động chỉ tồn tại trong một thời điểm nhất định do đó khi chúng ta truy xuất tới một tên trường mà nó không tồn tại thì sẽ bị lỗi. Trường Loai trong ví dụ trên là rất quan trọng vì nó chỉ ra phần động nào của mẩu tin được sử dụng trong quá trình thực hiện chương trình. Người đọc có thể tham khảo ví dụ tương đối hoàn chỉnh viết bằng Pascal.

uses crt;

Const luong_toi_thieu = 290000;

Type

Loai_cong_nhan = (bien_che, hop_dong);

Cong_nhan = Record

ho_ten : String[20];

Ngay_cong : real;

luong : real;

Case loai: Loai_cong_nhan of

bien_che: (He_so, so_ngay_nghi_BHXH : real);

hop_dong: (don_gia: real);

end;

danh_sach_cong_nhan = Array[1..10] of cong_nhan;

Var

n : integer; ho_so : danh_sach_cong_nhan;

{Nhập danh sách công nhân, và các thông tin liên quan đến lao động}

Procedure Nhap (var ho_so: danh_sach_cong_nhan; var n: integer);

Var

i: integer;

loaicn : char;

Begin

write('So cong nhan: '); readln(n);

For i:=1 to n do with ho_so[i] do begin

Writeln('Cong nhan ',i);

Write('Ho va Ten: '); readln(ho_ten);

Write('Loai cong nhan: A la bien che, B la hop dong ');

readln(loaicn);

If Upcase(loaicn) ='A' then loai := bien_che else loai := hop_dong;

write('So ngay cong: '); readln(ngay_cong);

if loai = bien_che then begin

write('He so: '); readln(he_so);

write('So ngay nghi bao hiem: '); readln(so_ngay_nghi_BHXH);

end else begin

write('Don gia hop dong: '); readln(don_gia);

end;

end; { with Ho_so[i] }

end; {nhap}

{Tính lương cho từng công nhân, theo công thức của từng loại công nhân}

Procedure Tinh_luong (var ho_so: danh_sach_cong_nhan; n: integer);

Var

i : integer; luong_binh_quan: real;

begin

for i:=1 to n do with ho_so[i] do begin

if loai = bien_che then begin {tính lương của công nhân biên chế}

luong_binh_quan := he_so * luong_toi_thieu/20;

luong := ngay_cong * luong_binh_quan +

so_ngay_nghi_BHXH * luong_binh_quan*0.80;

end else {tính lương của công nhân hợp đồng}

luong := ngay_cong * don_gia;

end; { with Ho_so[i] }

end; {Tinh_luong }

Procedure In_luong (ho_so: danh_sach_cong_nhan; n: integer);

Var

i : integer;

begin

for i:=1 to n do with ho_so[i] do begin

Write(ho_ten:25);

If loai = bien_che then write('Bien che':10)

else write('Hop dong':10);

write(ngay_cong:5:1);

if loai = bien_che then begin

write(he_so:5:1);

write(so_ngay_nghi_BHXH:5:1);

end else

write(don_gia:10:2);

writeln(luong:10:2);

end; { with Ho_so[i] }

end; { In_luong }

begin {Chuong trinh chinh}

nhap(ho_so,n);

tinh_luong(ho_so,n);

in_luong(ho_so,n);

readln;

end.

Biểu diễn bộ nhớ

Biểu diễn tuần tự sẽ được sử dụng để biểu diễn cho một mẩu tin có cấu trúc thay đổi.

Thông qua việc dịch, tổng bộ nhớ cần để lưu các phần tử của mỗi một phần động được xác định và bộ nhớ được cấp phát đủ để lưu trữ mẩu tin với phần động lớn nhất. Chẳng hạn với mẩu tin cong_nhan ta có mô hình lưu trữ như trong hình vẽ sau:

Vì khối ô nhớ đủ lớn để lưu trữ phần động lớn nhất nên có đủ chỗ cho bất kỳ một phần động nào nhưng đối với những phần động nhỏ hơn sẽ không sử dụng tới một số ô nhớ đã được cấp phát.

Với mẩu tin có cấu trúc thay đổi, rõ ràng ta đã tiết kiệm được một số ô nhớ so với mẩu tin bình thường.

Giải thuật thực hiện phép toán

Lựa chọn một phần tử của phần động cũng giống như lựa chọn một phần tử bình thường, qua việc dịch thì độ dời của phần tử được lựa chọn sẽ được tính toán và qua việc thực hiện thì độ dời được cọng vào địa chỉ cơ sở của khối để xác định vị trí của phần tử.

Đặc tả thuộc tính

Tùy ngôn ngữ, có thể có 3 cách đặc tả đối với kiểu chuỗi ký tự:

a/ Ðộ dài được khai báo cố định: Chuỗi ký tự có thể có độ dài (kích thước) cố định được khai báo trong chương trình. Mọi giá trị được gán cho đối tượng dữ liệu chuỗi đều có cùng độ dài như vậy. Khi một chuỗi thực được gán cho đối tượng dữ liệu mà độ dài của chuỗi thực khác độ dài được khai báo thì sẽ có sự điều chỉnh độ dài của chuỗi thực bằng cách cắt bớt các ký tự dư hoặc thêm vào các ký tự trắng để có được một chuỗi có độ dài đúng như khai báo.

Ðây là kỹ thuật cơ bản được dùng trong COBOL trong đó từ khóa PICTURE được dùng để xác định số lượng ký tự, ví dụ: Last_Name PICTURE X(20) khai báo biến chuỗi ký tự Last_Name chứa một chuỗi 20 ký tự.

Trong Pascal (chuẩn) kiểu dữ liệu chuỗi ký tự không có. Thay vào đó kiểu chuổi ký tự được biểu diễn như là một véctơ của các ký tự Last_Name: PACKED ARRAY [1..20] OF Char.

b/ Ðộ dài thay đổi trong một giới hạn đã được khai báo: Chuỗi ký tự có thể có độ dài cực đại được khai báo trước trong chương trình nhưng giá trị thực của đối tượng dữ liệu được lưu trữ có thể là chuỗi có độ dài ngắn hơn, thậm chí có thể là chuỗi rỗng. Trong quá trình thực hiện độ dài của giá trị chuỗi của đối tượng dữ liệu có thể thay đổi, nó cũng sẽ bị cắt nếu vượt giới hạn đã khai báo.

Ðây là kỹ thuật được dùng trong PL/1 (và cả trong Turbo Pascal).

c/ Ðộ dài không giới hạn: Chuỗi ký tự có thể có độ dài bất kỳ và độ dài có thể thay đổi một cách động thông qua quá trình thực hiện.

Ðây là kỹ thuật được dùng trong SNOBOL4.

Trong ba phương pháp nói trên thì hai phương pháp đầu cho phép cấp phát bộ nhớ cho mỗi một đối tượng dữ liệu chuỗi được xác định tại thời gian dịch. Ðối vơi phương pháp thứ ba thì sử dụng cấp phát bộ nhớ động tại thời gian thực hiện. Các phương pháp khác nhau cũng đòi hỏi các phép toán khác nhau trên chuỗi. Sau đây là một số phép toán chủ yếu.

Đặc tả phép toán

Trên chuỗi ký tự, thường có các phép toán sau:

a/ Phép ghép nối (concatennation)

Ghép là phép toán nhập hai chuỗi ký tự tạo ra một chuỗi mới ví dụ nếu "//" là ký hiệu của phép ghép thì "BLOCK"//"HEAD" cho ra "BLOCKHEAD". Turbo Pascal sử dụng toán tử “+” cho phép toán ghép chuỗi.

b/ Các phép toán quan hệ trên chuỗi

Các phép toán quan hệ thông thường như bằng, nhỏ hơn, lớn hơn... trên kiểu ký tự có thể được mở rộng cho chuỗi ký tự. Tập hợp các ký tự cơ bản luôn luôn có một thứ tự. Mở rộng thứ tự này cho chuỗi ký tự thành thứ tự alphabe trong đó chuỗi A nhỏ hơn chuỗi B nếu ký tự đầu tiên của A nhỏ hơn ký tự đầu tiên của B hoặc hai ký tự đầu tiên tương ứng của chúng bằng nhau và ký tự thư hai của A nhỏ hơn ký tự thứ hai của B... Nếu chuỗi A ngắn hơn chuỗi B thì A được mở rộng bằng cách thêm vào các ký tự trắng cho dài bằng B để so sánh.

c/ Chọn chuỗi con dùng chỉ số chỉ vị trí của ký tự

Nhiều ngôn ngữ cung cấp một phép toán chọn chuỗi con của một chuỗi bằng cách cho vị trí của ký tự đầu tiên và ký tự cuối cùng của nó (hoặc vị trí của ký tự đầu tiên và chiều dài của chuỗi con). Ví dụ trong FORTRAN, lệnh NEXT = STR(6:10) là gán 5 ký tự, bắt đầu từ vị trí thứ 6 đến vị trị thứ 10 của chuỗi STR cho biến chuỗi NEXT.

d/ Ðịnh dạng nhập - xuất

Ðịnh dạng nhập xuất là phép toán dùng để thay đổi dạng nhập vào hoặc xuất ra của các chuỗi ký tự. Nhập xuất có định dạng là nét nổi bật của FORTRAN và PL/1.

e/ Chọn chuỗi con dùng so mẫu

Thông thường người ta không biết vị trí của một chuỗi con cần chọn trong một chuỗi lớn hơn nhưng quan hệ của nó với một chuỗi con khác thì có thể biết. Ví dụ chuỗi các chữ số sau dấu chấm thập phân hay chuỗi đứng sau một khoảng trống. Phép so mẫu có một đối số thứ nhất để xác định dạng của chuỗi con cần chọn (chẳng hạn độ dài của nó). Ðối số thứ hai của phép toán so mẫu là chuỗi ký tự dùng để tìm trong chuỗi (chẳng hạn dấu chấm thập phân). Như vậy kết quả của phép toán so mẫu là chọn được một chuỗi con bắt đầu từ sau dấu chấm thập phân và có độ dài đã cho.

Giải thuật thực hiện các phép toán

Thông thường phần cứng hỗ trợ cho việc biểu diễn chuỗi có độ dài cố định nhưng đối với các biểu diễn khác cho chuỗi thì phải được mô phỏng bởi phần mềm. Các phép toán ghép, chọn chuỗi con và so mẫu phải mô phỏng bởi phần mềm.

Cấp phát tĩnh là sự cấp phát ô nhớ cho ÐTDL được thực hiện trong quá trình dịch.

Trong khi biên dịch, thông qua sự khai báo biến, bộ dịch xác định được kiểu dữ liệu của ÐTDL nên sẽ dành sẵn một khối ô nhớ đủ lớn để lưu trữ ÐTDL của kiểu này.

Người lập trình sử dụng ô nhớ được cấp phát thông qua tên biến.

Khi khối chương trình, nơi khai báo biến kết thúc thì ô nhớ đã được cấp phát sẽ được tự động giải phóng.

Ưu điểm

Ưu điểm của cấp phát tĩnh là người lập trình dễ sử dụng, cụ thể là người lập trình chỉ cần khai báo biến, chương trình dịch sẽ tự động cấp phát và sau đó tự động giải phóng.

Nhược điểm

Nhược điểm của cấp phát tĩnh là việc sử dụng bộ nhớ không tối ưu, cụ thể là có thể cấp phát nhiều ô nhớ nhưng sử dụng không hết hoặc cấp phát thiếu.

Cấp phát động là sự cấp phát trong khi thực hiện chương trình.

Người lập trình phải viết lệnh cấp phát trong chương trình, khi thực hiện lệnh này thì bộ nhớ mới được cấp phát.

Sử dụng cấp phát động, người lập trình có thể ra lệnh giải phóng để thu hồi ô nhớ.

Ðể có thể cấp phát động, ta cần có một biến con trỏ hay còn gọi là biến kiểu tham chiếu. Biến con trỏ là một ÐTDL sơ cấp chứa địa chỉ của khối ô nhớ được cấp phát.

Người lập trình sử dụng ô nhớ được cấp phát thông qua biến con trỏ.

Ưu điểm

Ưu điểm nổi bật của cấp phát động là sử dụng bộ nhớ một cách tối ưu.

Nhược điểm

Nhược điểm của cấp phát động là sự lắm tên, có thể có nhiều tên biến con trỏ cùng tham chiếu đến một ô nhớ và do vậy làm giảm độ tin cậy của chương trình. Ngoài ra cũng gặp khó kăn khi sử dụng cấp phát động.

Đặc tả thuộc tính

Có hai loại con trỏ khác nhau:

Con trỏ chỉ có thể tham chiếu tới các ÐTDL cùng kiểu

Ðây là phương pháp được dùng trong Pascal và Ada.

Ví dụ trong Pascal:

Var p: ^integer chỉ ra rằng p là một biến con trỏ chứa địa chỉ của ô nhớ lưu trữ được một số integer.

Var q: ^VECT chỉ ra rằng q là một biến con trỏ chứa địa chỉ của khối ô nhớ của ÐTDL thuộc kiểu véctơ VECT nào đó.

Con trỏ có thể tham chiếu tới các ÐTDL khác kiểu nhau

Ðây là cách được dùng trong các ngôn ngữ như SNOBOL4, nơi mà đối tượng dữ liệu mang bộ mô tả kiểu trong quá trình thực hiện và phép kiểm tra kiểu động được sử dụng.

Đặc tả phép toán

Các phép toán bao gồm:

Phép toán cấp phát ô nhớ động: Phép toán này dùng để cấp phát ô nhớ cho đối tượng dữ liệu mới và trả địa chỉ của ô nhớ đó về trong biến con trỏ. Ðây là phép toán quan trọng nhất của kiểu con trỏ. Phép toán này có hai điểm khác biệt với việc tạo ra đối tượng dữ liệu tĩnh (bằng cách khai báo) là: Ðối tượng dữ liệu được tạo ra không cần có tên vì nó được truy xuất thông qua con trỏ và đối tượng dữ liệu có thể được tạo ra một cách động trong quá trình thực hiện chương trình. Trong Pascal và Ada thì phép toán này có tên là NEW. Ví dụ NEW(p).

Phép toán truy xuất ô nhớ được cấp phát động: Ðể truy xuất đến giá trị dữ liệu lưu trong khối ô nhớ cấp phát động ta phải sử dụng địa chỉ của khối ô nhớ thông qua tên con trỏ (vì khối ô nhớ này không có tên). Ví dụ q^[5] là phần tử thứ 5 của véctơ Vect được trỏ bởi q.

Phép toán thu hồi ô nhớ được cấp phát động: Phép toán này cho phép giải phóng ô nhớ đã cấp phát. Trong Pascal, dùng phép toán DISPOSE.

Ví dụ sau trong Pascal minh hoạ tổng hợp các điều nói trên:

Type

Vect = ARRAY[1..10] of Integer;

{Lúc này bộ nhớ cho Vect chưa được cấp phát}

VAR

p: ^Vect;

{Khai báo p là một biến con trỏ chứa địa chỉ của khối ô nhớ lưu trữ ÐTDL thuộc kiểu véctơ Vect. Khi dịch đến đây thì ô nhớ cho p sẽ được cấp phát}

Begin

NEW(p);

{Cấp phát ô nhớ cho véctơ và trả địa chỉ của ô nhớ này cho biến con trỏ p (hay còn nói p trỏ tới khối ô nhớ này)}

p^[5] := 20; {Truy xuất đến phần tử thứ 5 của véctơ}

writeln(p^[5]);

Dispose(p); {Giải phóng ô nhớ đã cấp cho véctơ}

End.

Ðịa chỉ tuyệt đối

Giá trị con trỏ là địa chỉ ô nhớ thực của khối ô nhớ của ÐTDL.

Phương pháp này rất hiệu quả, bởi vì giá trị con trỏ tự nó quy định sự truy xuất trực tiếp tới đối tượng dữ liệu bằng cách dùng phép toán truy xuất bộ nhớ của phần cứng.

Ðịa chỉ tương đối

Ðây là phương pháp cấp phát một vùng nhớ rộng với địa chỉ cơ sở của nó. Giá trị con trỏ là độ dời của ÐTDL. Ðịa chỉ của ÐTDL được tính bằng cách lấy địa chỉ cơ sở + độ dời của ÐTDL (tức là giá trị của con trỏ).

Phương pháp này thuận tiện cho việc quản lý bộ nhớ nhưng truy xuất đến ÐTDL chậm vì phải tính địa chỉ của khối ô nhớ biểu diễn cho ÐTDL.

Đặc tả thuộc tính

Tập hợp là một cấu trúc dữ liệu đồng nhất và có kích thước thay đổi.

Trong một tập hợp người ta không quan tâm đến thứ tự của các phần tử; giá trị các phần tử khác nhau.

Đặc tả phép toán

Các phép toán cơ bản trên tập hợp là:

1/ Kiểm tra sự tồn tại của một phần tử

Phép toán này dùng để xác định xem một giá trị X nào đó có phải là một phần tử của tập hợp S hay không.

2/ Thêm và bớt các phần tử cho tập hợp

Thêm giá trị X vào trong tập S, với điều kiện nó chưa là một phần tử của tập hợp. Xóa một giá trị dữ liệu X của tập S nếu nó là một phần tử của S. Hai phép toán này sẽ làm thay đổ kích thước của tập hợp.

3/ Phép hợp, giao và hiệu của 2 tập hợp

Đây là các phép toán được định nghĩa tương tự như trong toán học.

Véctơ bit

Biểu diễn bộ nhớ: Tập hợp được biểu diễn bởi một chuỗi các bit. Cách tiếp cận này phù hợp cho một không gian nhỏ. Chẳng hạn ta có một không gian gồm n phần tử được đánh số thứ tự e₁, e₂, ... e_n. Một tập hợp các phần tử được chọn từ không gian này được biểu diễn bởi một véctơ có n bit, trong đó nếu bit thứ i có giá trị 1 thì phần tử e_i thuộc vào tập hợp, ngược lại bit thứ i có giá trị 0 thì e_i không thuộc tập hợp.

Giải thuật thực hiện các phép toán: Với cách biểu diễn này, việc thêm một phần tử vào trong tập hợp được thực hiện bằng cách cho bit tương ứng giá trị bằng 1. Việc xóa một phần tử trong tập hợp được thực hiện bằng cách cho bit tương ứng giá trị bằng 0. Phép kiểm tra một phần tử có thuộc tập hợp hay không được thực hiện bằng cách kiểm tra bit tương ứng có giá trị là 1 hay 0. Phép hợp của hai tập hợp tương ứng với phép toán logic OR của hai véctơ bit. Phép giao của hai tập hợp tương ứng với phép toán logic AND của hai véctơ bit. Hiệu của hai tập hợp tương ứng với phép toán logic AND của véctơ bit thứ nhất với phần bù của véctơ bit thứ hai. Các phép toán logic trên các véctơ bit đều được hỗ trợ bởi phần cứng.

Ví dụ Ta có một không gian bao gồm 5 phần tử 1,2,3,4,5. Khi đó

Tập hợp A = {1,2,4,5} được biểu diễn bởi véctơ (1,1,0,1,1)

Tập hợp B = {2,3,4} được biểu diễn bởi véctơ (0,1,1,1,0)

Do đó A size 12{ union } {}B sẽ là tập {1,2,3,4,5} bởi vì (1,1,0,1,1) OR (0,1,1,1,0) = (1,1,1,1,1)

A size 12{ intersection } {}B sẽ là tập hơp {2,4} bởi vì (1,1,0,1,1) AND (0,1,1,1,0) = (0,1,0,1,0)

AB sẽ là tập hơp {1,5} bởi vì phần bù của (0,1,1,1,0) là (1,0,0,0,1) và

(1,1,0,1,1) AND (1,0,0,0,1) = (1,0,0,0,1)

Ưu điểm

Dễ dàng cài đặt các phép toán trên tập hợp với tốc độ thực hiện nhanh nhờ sử dụng các phép toán của phần cứng.

Nhược điểm

Không thể biểu diễn cho tập hợp mà các phần tử của nó có thể lấy từ một không gian lớn, có số lượng các phần tử bất kỳ.

Bảng băm

Biểu diễn bộ nhớ: Phương pháp này thích hợp cho các không gian lớn. Theo đó mỗi tập hợp được biểu diễn bởi một bảng băm (bảng băm mở). Mỗi phần tử của tập hợp được lưu trữ trong các lô (bucket) của bảng băm nhờ vào hàm băm (mỗi lô là một danh sách liên kết, mỗi phần tử của danh sách chứa môt phần tử của tập hợp).

Giải thuật thực hiện các phép toán: Phép toán kiểm tra sự tồn tại của một phần tử trong tập hợp được thực hiện bằng cách sử dụng phép tìm kiếm một phần tử trong bảng băm.

Các phép toán thêm và bớt một phần tử của tập hợp được thực hiện bằng cách sử dụng các phép toán tương ứng là xen và xoá một phần tử của bảng băm.

Các phép toán hợp, giao và hiệu của hai tập hợp đòi hỏi phải có một sự cài đặt công phu hơn.

Ưu điểm

Có thể biểu diễn cho tập hợp bất kỳ, không giới hạn về kích thước.Các phép toán kiểm tra một phần tử thuộc tập hợp, thêm và bớt một phần tử thực hiện dễ dàng và khá hiệu quả.

Nhược điểm

Khó khăn trong việc cài đặt các phép toán hợp, giao và hiệu của hai tập hợp.

Sự đặc tả

Tập tin tuần tự là một CTDL bao gồm một dãy tuyến tính các phần tử có cùng kiểu. Ðộ dài của tập tin là không giới hạn. Kiểu phần tử có thể là kiểu sơ cấp hoặc kiểu cấu trúc có kích thước cố định như mảng hoặc mẩu tin. Kiểu cấu trúc có kích tước thay đổi thông thường không thể là phần tử của tập tin (do đó không có tập tin của tập tin hay tập tin của ngăn xếp).

Một cách phổ biến, tập tin có thể được truy nhập theo một trong hai mode: READ hoặc WRITE. Trong cả hai mode này đều có một con trỏ tập tin (file position pointer) dùng để xác định vị trí của phần tử nào đó hoặc sau phần tử cuối cùng. Trong mode WRITE, con trỏ tập tin luôn luôn chỉ vào sau phần tử cuối cùng và phép toán duy nhất có thể là ghi một phần tử mới vào vị trí đó. Trong mode READ, con trỏ tập tin có thể chỉ vào bất kỳ vị trí nào trong tập tin và phép toán duy nhất là đọc phần tử đó. Trong cả hai mode, phép toán READ hoặc WRITE đều di chuyển con trỏ tập tin đến phần tử kế tiếp. Nếu con trỏ tập tin chỉ tới sau phần tử cuối cùng của tập tin thì tập tin được gọi là được chỉ tới cuối tập tin (end-of-file).

Các phép toán chủ yếu đối với tập tin tuần tự là:

1/ OPEN

Thông thường một tập tin phải được mở trước khi sử dụng. Phép toán OPEN chỉ ra tên của tập tin và mode truy xuất tập tin (READ hoặc WRITE). Nếu mode là READ thì tập tin phải chắc chắn là đã tồn tại. Hệ diều hành cung cấp đặc tính của tập tin, cấp phát ô nhớ cần thiết cho vùng nhớ đệm và đặt con trỏ tập tin vào phần tử đầu tiên. Nếu mode là WRITE thì hệ điều hành tạo một tập tin rỗng, nếu tập tin đã tồn tại thì xóa tất cả các phần tử của tập tin để nó rỗng, con trỏ tập tin chỉ vào vị trí đầu tập tin rỗng.

Ví dụ trong Pascal thủ tục RESET mở một tập tin để READ và thủ tục REWRITE mở một tập tin để WRITE.

2/ READ

Phép toán READ chuyển nội dung của phần tử hiện hành của tập tin (được chỉ định bởi con trỏ tập tin) vào biến được chỉ định trong chương trình.

3/ WRITE

Phép toán WRITE tạo ra một phần tử mới của tập tin tại vị trí hiện hành và chuyển nội dung của biến chương trình được chỉ định vào phần tử mới.

4/ Kiểm tra cuối tập tin

Là phép toán xác định xem vị trí của con trỏ tập tin có nằm sau phần tử cuối cùng của tập tin hay không.

5/ CLOSE

Khi việc xử lý tập tin đã hoàn tất thì nó phải được đóng lại. Thông thường tập tin được đóng một cách tự động khi chương trình kết thúc. Tuy nhiên nếu muốn thay đổi mode truy nhập tập tin từ WRITE sang READ hoặc ngược lại thì tập tin phải được đóng một cách tường minh bằng phép toán CLOSE và sau đó mở lại cho mode mới.

Phép cài đặt

Trong hầu hết các hệ máy tính, thì hệ điều hành chịu trách nhiệm chủ yếu về việc cài đặt tập tin bởi vì tập tin được tạo ra và sử dụng bởi nhiều ngôn ngữ lập trình khác nhau. Ngôn ngữ lập trình chỉ làm một việc là cung cấp những cấu trúc dữ liệu cần thiết để giao diện với hệ điều hành.

Các phép toán trên tập tin được cài đặt một cách chủ yếu bằng cách gọi các phép toán của hệ điều hành.

Khi chương trình mở một tập tin, thì bộ nhớ lưu trữ một bảng thông tin về tập tin (FIT) (File Information Table) và một bộ nhớ đệm (buffer) được cung cấp. Phép toán OPEN của hệ diều hành sẽ lưu trữ thông tin về vị trí và các đặc tính của tập tin vào trong bảng FIT.

Nếu tập tin được mở để ghi thì khi phép toán WRITE chuyển một phần tử để nối vào cuối tập tin, thì dữ liệu được gửi cho phép toán WRITE của hệ điều hành. Phép toán WRITE của hệ điều hành sẽ lưu dữ liệu vào trong vị trí có thể của bộ nhớ đệm. Khi trong bộ nhớ đệm đã tích lũy được một khối các phần tử thì khối đó sẽ được chuyển sang bộ nhớ ngoài (đĩa hoặc băng từ). Quá trình tiếp tục của phép toán WRITE được thực hiện bằng cách lấp đầy bộ nhớ đệm cho đến khi một khối có thể được chuyển ra bộ nhớ ngoài.

Ðối với READ thì ngược lại, một khối các phần tử của tập tin sẽ được chuyển sang bộ nhớ đệm và mỗi một phép toán READ được thực hiện bởi chương trình lại chuyển một phần tử từ bộ nhớ đệm sang biến chương trình cho đến khi bộ nhớ đệm trở thành rỗng thì một khối lại được chuyển từ bộ nhớ ngoài vào bộ nhớ đệm.