Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 63
//Chép phần run còn lại trong Ft1 về Fd
B17: IF (K1 > L) //Đã chép hết phần run còn lại trong Ft1 về Fd
Lặp lại B6
B18: fwrite(&a1, sizeof(T), 1, Fd)
B19: K1++
B20: IF (feof(Ft1)) //Đã chép hết các phần tử trong Ft1
Thực hiện B23
B21: fread(&a1, sizeof(T), 1, Ft1)
B22: Lặp lại B17
//Chép các phần tử còn lại trong Ft2 về Fd
B23: fwrite(&a2, sizeof(T), 1, Fd)
B24: IF (feof(Ft2))
Thực hiện Bkt
B25: fread(&a2, sizeof(T), 1, Ft2)
B26: Lặp lại B23
//Chép các phần tử còn lại trong Ft1 về Fd
B27: fwrite(&a1, sizeof(T), 1, Fd)
B28: IF (feof(Ft1))
Thực hiện Bkt
B29: fread(&a1, sizeof(T), 1, Ft1)
B30: Lặp lại B27
Bkt: Kết thúc
- Thuật toán sắp xếp trộn thẳng:
B1: L = 1 //Chiều dài ban đầu của các run
B2: IF (L ≥ N) //Tập tin Fd chỉ còn 01 run
Thực hiện Bkt
B3: Phân_Phối(DataFile, DataTemp1, DataTemp2, L)
B4: Trộn(DataTemp1, DataTemp2, DataFile, L)
B5: L = 2*L

e
r
w
w
w
.
d
o
c
u
-
t
r
a
c
k
.
c
o
m
Click to buy NOW!
P
D
F
-
X
C
h
a
n

và DataTemp2. Hàm trả về giá trò 1 nếu việc phân phối hoàn tất, trong trường hợp
ngược lại hàm trả về giá trò –1.
int FileMerge(char * DataTemp1, char * DataTemp2, char * DataFile, int L);
Hàm thực hiện việc trộn từng cặp tương ứng các đường chạy với độ dài L trên hai
tập tin tạm thời có tên DataTemp1, DataTemp2 về tập tin dữ liệu ban đầu có tên
DataFile thành các đường chạy có chiều dài 2*L. Hàm trả về giá trò 1 nếu việc trộn
hoàn tất, trong trường hợp ngược lại hàm trả về giá trò –1.
Cả hai hàm này đều sử dụng các hàm Finished để làm nhiệm vụ “dọn dẹp” (đóng
các tập tin đã mở, hủy vùng nhớ đã cấp phát, …) và trả về một giá trò nguyên để kết
thúc. Các hàm Finished có prototype như sau:
int Finished (FILE * F1, int ReturnValue);
int Finished (FILE * F1, FILE * F2, int ReturnValue);
int Finished (FILE * F1, FILE * F2, FILE * F3, int ReturnValue);
Nội dung của các hàm như sau:
int Finished (FILE * F1, int ReturnValue)
{ fclose (F1);
return (ReturnValue);
}
//========================================================
int Finished (FILE * F1, FILE * F2, int ReturnValue)
{ fclose (F1);
fclose (F2);
return (ReturnValue);
}
//========================================================
int Finished (FILE * F1, FILE * F2, FILE * F3, int ReturnValue);
{ fclose (F1);
fclose (F2);
fclose (F3);
return (ReturnValue);

e
r
w
w
w
.
d
o
c
u
-
t
r
a
c
k
.
c
o
m
Click to buy NOW!
P
D
F
-
X
C
h
a
n

int SOT = sizeof(T);
while (!feof(Fd))
{ for(int K = 0; K<L && !feof(Fd); K++)
{ int t = fread(&a, SOT, 1, Fd);
if (t < 1)
{ if (feof(Fd))
break;
return (Finished(Fd, Ft1, Ft2, -1));
}
t = fwrite(&a, SOT, 1, Ft1);
if (t < 1)
return(Finished(Fd, Ft1, Ft2, -1));
}
for(K = 0; K<L && !feof(Fd); K++)
{ int t = fread(&a, SOT, 1, Fd);
if (t < 1)
{ if (feof(Fd))
break;
return (Finished(Fd, Ft1, Ft2, -1));
}
t = fwrite(&a, SOT, 1, Ft2);
if (t < 1)
return(Finished(Fd, Ft1, Ft2, -1));
}
}
return (Finished(Fd, Ft1, Ft2, 1));
}
//========================================================
int FileMerge(char * DataTemp1, char * DataTemp2, char * DataFile, int L)
{ FILE * Ft1 = fopen(DataTemp1, “rb”);

V
i
e
w
e
r
w
w
w
.
d
o
c
u
-
t
r
a
c
k
.
c
o
m
Click to buy NOW!
P
D
F
-
X

m
.
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 66
{ int t = fwrite(&a1, SOT, 1, Fd);
if (t < 1)
return (Finished(Fd, Ft1, Ft2, -1));
K1++;
t = fread(&a1, SOT, 1, Ft1);
if (t < 1)
{ if (feof(Ft1))
break;
return (Finished (Fd, Ft1, Ft2, -1));
}
if (K1 == L)
{ for (; K2 < L && !feof(Ft2); K2++)
{ t = fwrite(&a2, SOT, 1, Fd);
if (t < 1)
return (Finished(Fd, Ft1, Ft2, -1));
t = fread(&a2, SOT, 1, Ft2);
if (t < 1)
{ if (feof(Ft2))
break;
return (Finished(Fd, Ft1, Ft2, -1));
}
}
if (feof(Ft2))
break;
}
if (K1 == L && K2 == L)

a
n
g
e

V
i
e
w
e
r
w
w
w
.
d
o
c
u
-
t
r
a
c
k
.
c
o
m
Click to buy NOW!

c
k
.
c
o
m
.
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 67
return (Finished(Fd, Ft1, Ft2, -1));
}
}
if (feof(Ft1))
break;
}
if (K1 == L && K2 == L)
K1 = K2 = 0;
}
}
while (!feof(Ft1))
{ int t = fwrite(&a1, SOT, 1, Fd);
if (t < 1)
return (Finished(Fd, Ft1, Ft2, -1));
t = fread(&a1, SOT, 1, Ft1);
if (t < 1)
{ if (feof(Ft1))
break;
return (Finished (Fd, Ft1, Ft2, -1));
}
}

F
-
X
C
h
a
n
g
e

V
i
e
w
e
r
w
w
w
.
d
o
c
u
-
t
r
a
c
k

u
-
t
r
a
c
k
.
c
o
m
.