Bài 5.5. Trộn hai tệp
Cho hai tệp văn bản data1.inp và
data2.inp chứa các số nguyên được sắp tăng. Viết chương trình trộn hai dãy dữ
liệu trong hai tệp này thành một dãy dữ liệu sắp tăng duy nhất và ghi trong tệp
văn bản data.out.
Chú ý:
-
Với dữ liệu đã
cho trong tệp thứ nhất là 5 số, tệp thứ hai là 6 số thì tệp kết quả sẽ chứa 11
số.
-
Số lượng các số
trong mỗi tệp tối đa là 50 nghìn và không biết trước.
-
Các số có giá trị
kiểu nguyên, được tách nhau bởi dấu cách và có thể nằm trên nhiều dòng.
-
Khi trộn hai tệp
nói trên ta phải thực hiện tối thiểu 22 lần đọc-ghi bao gồm 11 lần đọc và 11
lần ghi.
Thí dụ:
data1.inp
2
3
5
5
10
|
data2.inp
3
3
4
7
12
20
|
data.out
2
3
3
3
4
5
5
7
10
12
20
|
Thuật toán
Ta dùng phương pháp cân. Gọi hai tệp chứa dữ liệu cần trộn là f và g,
tệp chứa kết quả trộn là h. Hãy tưởng
tượng, ta dùng tay trái lấy lần lượt, mỗi lần một phần tử của
tệp f (ghi vào biến t) và dùng tay phải lấy lần lượt mỗi lần
một phần tử của tệp g (ghi vào biến p). So sánh vật nặng trên hai tay t và p.
Tay nào cầm phần tử nhẹ hơn thì đặt phần tử đó vào tệp kết quả h và do tay đó rỗi nên lấy tiếp phần tử
từ tệp tương ứng. Quá trình này kết thúc khi nào một trong hai tệp f hoặc g được duyệt xong. Cuối cùng ta
chuyển nốt các phần tử còn lại của tệp chưa duyệt hết (tệp f hoặc g) vào tệp kết quả
h.
Ta cần lưu ý mấy điểm sau đây:
Khi đọc xong phần tử cuối cùng của một tệp thì tệp đó chuyển sang trạng
thái kết thúc (EOF), do đó nếu ta tổ chức vòng lặp WHILE trong thủ tục trộn hai tệp theo điều kiện (NOT EOF(f)) AND (NOT
EOF(g)) thì phần tử cuối của các tệp
đó sẽ chưa kịp được so sánh, trong khi ta muốn tôn trọng nguyên tắc: sau khi so
sánh t và p thì một trong hai biến, t
hoặc p phải được giải phóng. Có thể
thực hiện nguyên tắc này bằng kĩ thuật săn đuổi như sau: dùng biến lôgic ef ghi nhận trạng thái hết tệp f sớm hơn một nhịp. Điều đó có nghĩa khi ef=FALSE biến t vẫn
đang chứa giá trị chưa xử lí (chưa so sánh với p và do đó chưa được ghi vào tệp h). Chú ý rằng dù ef = FALSE nhưng có thể ta vẫn có EOF(f)=TRUE. Một
biến eg tương tự cũng được tạo cho tệp g. Về bản chất có thể hiểu các biến ef và eg khi chúng nhận giá trị TRUE là thực sự đã
đọc được 1 đơn vị dữ liệu từ file.
(* Pascal *)
(*----------------------
Merge Files
----------------------*)
program MergeFiles;
uses crt;
const
BL = #32; MN = 12;
fn = 'data1.inp'; gn = 'data2.inp';
hn = 'data.out';
{---------------------------------
Tron tep fn va gn ghi vao hn
----------------------------------}
procedure
FMerge;
var
f,g,h: text;
ef, eg: Boolean;
t, p: integer;
d: longint; {so phan tu trong tep out}
begin
assign(f,fn);
reset(f);
assign(g,gn);
reset(g);
assign(h,hn);
rewrite(h);
ef := SeekEof(f);
if NOT eof
then read(f,t);
eg := SeekEof(g);
if NOT eg then
read(g,p);
d := 0;
while (NOT ef)
AND (NOT eg) do
if t < p then
begin
inc(d);
write(h,t,BL);
if d mod 10 = 0 then writeln(h);
ef := SeekEof(f);
if NOT ef then read(f,t);
end else
begin
inc(d);
write(h,p,BL);
if d mod 10 = 0 then writeln(h);
eg := SeekEof(g);
if NOT eg then read(g,p);
end;
while (NOT ef) do
begin
inc(d);
write(h,t,BL);
if
d mod 10 = 0 then writeln(h);
ef := SeekEof(f);
if
NOT ef then read(f,t);
end;
while (NOT eg) do
begin
inc(d);
write(h,p,BL);
if d
mod 10 = 0 then writeln(p);
eg := SeekEof(g);
if
NOT eg then read(g,p);
end;
close(f); close(g); close(h);
end;
BEGIN
FMerge;
END.
Chú thích Thực ra có thể đọc dữ liệu từ hai file vào hai mảng
tương ứng rồi trộn hai mảng này. Tuy nhiên chúng ta muốn minh họa lời giải với
hạn chế là mỗi lần chỉ được phép đọc một đơn vị dữ liệu từ mỗi file.
Hàm bool
ReadInt(StreamReader f, ref int i) đọc mỗi lần một số nguyên i từ file text f. Nếu đọc được, hàm cho ra giá trị true và số i, ngược lại, nếu không gặp số nguyên, hàm cho ra giá trị false.
Hàm hoạt động như sau. Trước hết bỏ qua các kí tự trắng. Nếu gặp dấu trừ ‘-‘
hàm ghi nhận dấu đó, sau đó hàm đọc tiếp dãy số và tích lũy dần vào biến nguyên
i.
Không có nhận xét nào:
Đăng nhận xét