Trộn hai tệp



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à fg, 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 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 tp thì một trong hai biến, thoặ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 efeg 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