对磁盘文件记录进行排序（外排序）-C++语言描述

昨天用c++排了一天，也没排成功，今天终于排好了，呵呵，好开心啊，贴出来给大家看看，希望多提意见！有一个问题是，我用c++排好之后，又马上用c语言把算法描述了一遍，刚开始编译成功了，但是排来排去，把数据都排没了，后来不知道怎么改了一下，出现了错误，怎么也发现不了。

 

源文件如下(c++描述):

 

#include
#include
#include
#include

 

//记录结构
struct stu
{
    long ID;
    int g;
};

 

//b是每条记录所占的字节数

#define b sizeof(struct stu)

typedef stu DataType;

 

//对文件a的第s~m和m+1~t的两个有序记录进行两路归并的函数

void FTwomerge(fstream &A, fstream &R, int s, int m, int t)
{
    int i, j, k;
    DataType a1, b1;
 for (i = m+1, k = s; s <= m && i <= t; ++k)
 {
        A.seekg(s*b);             /* b是每个记录的大小 */
        A.read((char *)&a1, b);   /* 读一个记录到a1中 */
        A.seekg(i*b);
        A.read((char *)&b1, b);   /* 读另一条记录到b1中 */
        if (a1.g <= b1.g)
        {
     R.seekg(k*b);
              R.write((char *)&a1, b);
              s++;
        }
        else
        {
     R.seekg(k*b);
              R.write((char *)&b1, b);
              i++;
        }
    }

    //对前一个归并段中存在的未归并元素进行处理
 for (j = s; j <= m; ++j, ++k)
 {
  A.seekg(j*b);
  R.seekg(k*b);
  A.read((char *)&a1, b);
  R.write((char *)&a1, b);
 }

    //对后一个归并段中存在的未归并元素进行处理
 for (j = i; j <= t; ++j, ++k)
 {
  A.seekg(j*b);
  R.seekg(k*b);
  A.read((char *)&a1, b);
  R.write((char *)&a1, b);
 }
}

 

 

/* 对文件A进行一趟二路归并的算法 */

void FMergePass(fstream &A, fstream &R, int n, int len)
{
    //把文件A中每个长度为len的有序表两两归并到文件R
    DataType x;
    int start_p, end_p;
 start_p = 0;
 while (start_p + len < n)
 {
  end_p = start_p + 2*len - 1;
  if (end_p >= n)
   end_p = n-1;
        FTwomerge(A, R, start_p, start_p + len - 1, end_p);
        start_p = end_p+1;
    }
 if (start_p < n)
  for (; start_p < n; start_p++)
  {
   A.seekg(start_p*b);
   R.seekg(start_p*b);
   A.read((char *)&x, b);
   R.write((char *)&x, b);
  }
}

 

//将文件A进行归并排序
void FMergeSort(fstream &A, int BlockSize)
{
    //采用归并排序的方法对文件A中的，每个有序子表长度为BlockSize的记录进行排序
    fstream R("temp.rec", ios::in | ios::out | ios::binary);
    //定义一个能够按块随机存取的辅助文件R
    if (!R)
    {
        cerr << "temp.dat" << ' ' << "Not Open!" << endl;
        abort();
    }
 DataType x;
    int k = 0;
    int len = BlockSize;   //有序表长度
    A.seekg(0, ios::end);   //将文件A的指针移到文件的末尾
    int n = A.tellg() / b; //n =文件的记录条数

    while (len < n)
    {
  if (k == 0)
        FMergePass(A, R, n, len);  //从A归并到R中，得到每个有序表的长度为2*len
  else
        FMergePass(R, A, n, len);  //从R归并到A中，得到每个有序表的长度为2*len
        len = len*2;
  k = 1-k;
    }
 if (k == 1)
 {
  for (k = 0; k < n; ++k)
  {
   A.seekg(k*b);
   R.seekg(k*b);
   R.read((char *)&x, b);
   A.write((char *)&x, b);
  }
 }
    R.close();
    remove("temp.rec");   //删除磁盘上的临时文件
}

int main(int argc, char* argv[])
{
    char num[20], ch = 'y';
    struct stu s;
    fstream outfile, infile, sortfile;
    outfile.open("st.rec", ios::out | ios::binary | ios::app);
    if (!outfile)
    {
        cout << "st.rec can't open" << endl;
        abort();
    }
    while (ch == 'y')
    {
        cout << "ID    :";
        cin >> num;
        s.ID = atol(num);
        cout << "Grade :";
        cin >> num;
        s.g = atoi(num);
  outfile.seekg(sizeof(s));
        outfile.write((char *)&s, sizeof(s));
        cout << "another(y/n)?";
        cin >> ch;
    }
    outfile.close();

 

//打开文件，对文件进行排序

 sortfile.open("st.rec", ios::in | ios::binary | ios::out);
 if (!sortfile)
 {
  cout << "st.rec can't open" << endl;
  abort();
 }
 FMergeSort(sortfile, 1);          
 sortfile.close();

 

//输出刚排好序的文件

 infile.open("st.rec", ios::in | ios::binary);
    if (!infile)
    {
        cout << "st.rec can't open" << endl;
        abort();
    }
 while (infile.read((char *)&s, sizeof(s)))
 {
  cout << s.ID << ":" << s.g << endl;
 }
    infile.close();

 return 0;
}