在不使用数组的情况下对二进制文件中的数据进行排序

Question

你好，我有一个作业要生成随机数。然后将它们写入二进制文件。之后我应该读取数据并将其打印到屏幕上。最后，我必须对数据和输出进行排序。我必须在不使用数组的情况下这样做。我能够完成前两部分。但是，我无法正确完成最后一部分，所以我去了 google 和 youtube 寻找有关如何做到这一点的插图，但我运气不好。我真的很想知道我做错了什么，谢谢。

我想我应该使用递归 fseek 和转换来避免使用数组；但是，我不知道如何使用它们。

这是我的代码和输出：

#include <iostream>
#include <fstream>
#include <iomanip>
#include <stdlib.h> 

using namespace std;

//Function prototypes
void Write_File(int num);
void Read_File(int num);
void Compare(int num);

//**********************

int main()
{
    int num = 0;

    cout << "Enter a positive number to generate random numbers ";
    cin >> num;

    Write_File(num);
    Read_File(num);
    Compare(num);


    return 0;
}

//***************

// Functions Definitions
void Write_File(int num)
{
    ofstream fout("sortfile.dat", ios::out | ios::binary | ios::beg);
    int number = 0;

    if (fout.is_open())
    {
        for (int x = 0; x < num; x++)
        {
            number = rand();
            fout << number << endl;
        }

        fout.close();
    }
    else
    {
        cout << "Error, File not opened" << endl;
    }
}

void Read_File(int num)
{
    ifstream fin("sortfile.dat", ios::in | ios::binary | ios::beg);
    int number = 0;

    cout << endl << "randomly generated numbers befor sorting\n";
    if (fin.is_open())//check first if open already
    {
        for (int i = 0; i < num; i++)
        {
            fin >> number;
            cout << number << endl;
        }


            fin.close();
        }
        else
            cout << "File not opened in read phase." << endl;
}


void Compare(int num) 
{
    int number = 0;
    int temp = 0;
    int hold = 0;
    ifstream fin("sortfile.dat", ios::in | ios::binary | ios::beg);

    if (fin.is_open())//check first if open already
    {
        for (int i = 0; i < num; i++)
        {
            fin >> number;
            fin >> temp;
            if (number > temp)
            {


                hold = temp;
                temp = number;
                number = hold;

            }
            else
            {
                ofstream fout("sortfile.dat", ios::out | ios::binary | ios::beg);
                fout << number;
                fout << temp;
            }

            ofstream fout("sortfile.dat", ios::out | ios::binary | ios::beg);
            fout << number;
            fout << temp;
        }
        cout << endl << "Nums after sort\n";
        for (int i = 0; i < num; i++)
        {
            fin >> number;
            cout << number << endl;
        }

        fin.close();
    }
    else
        cout << "File not opened in read phase." << endl;
}

输出：

Enter a positive number to generate random numbers 4

randomly generated numbers befor sorting
41
18467
6334
26500

Nums after sort
6334
6334
6334
6334
Press any key to continue . . .

Answer 1

据我所知，您会不断重新创建输出流，这意味着您会不断写入文件的开头。

在你的比较函数中：

for (int i = 0; i < num; i++)
{
      ...

     // for every iteration you create an output stream at the beginning of the file
      ofstream fout("sortfile.dat", ios::out | ios::binary | ios::beg);
      fout << number;
      fout << temp;
}

Answer 2

好的，这里有几处错误。首先，您将无法通过仅交换相邻元素来进行一次性排序。那将是一个 O(n) 排序，如果你设法实现它，你将立即成为计算机科学界的名人。你的教授说你不能使用数组？如果 "arrays"、he/she 表示任何类型的内存缓冲区，那就太傻了。如果你想要一个不使用数组的排序，从字面意义上讲，只需使用一个std::map。当您从文件中读取数字时，将数字插入地图。然后，使用迭代器按排序顺序检索数字，并打印出来。

其次，您正在对文件 io 做一些可能不是您想要的事情。在您从文件中读取数字对然后可能交换它们的循环中，您的控制流允许将这对数字写入文件两次，前提是它们是按排序顺序排列的。此外，您在每次循环迭代中构建一个或可能两个 ofstream 对象。每个新的输出流都从文件的开头开始，因此您要重复写入文件的开头。在打印出 "sorted" 内容之前，您也不会将输入流搜索到文件的开头。它打印出相同数字 4 次的原因是它已到达文件末尾，并且没有为 "number".

分配任何新值

我的建议是真正避免尝试同时读取和写入文件。读取中的数字（请注意，不是数组；）），对它们进行排序，然后输出它们。（从作业规范来看，您似乎不必再次将它们写入文件，但我不确定）。

Answer 3

嗯，要对一堆元素进行排序，不管你用什么算法，总有一天你至少要将一个元素（或者它的索引）存储在它存储的指定位置=> 普通程序员使用数组（或数组或索引）调用。

您的要求可以从两个方面理解：

您不能使用数组，但可以使用其他 C++ 容器。好吧，拿一个矢量（一旦填充就可以像数组一样使用），或者@c_dubs 建议的地图。也许吧，但如果我要求不使用数组并且不明确允许 C++ 容器，我不会对该解决方案感到满意
你根本不能在内存中使用。您必须直接对磁盘上的文件（或文件副本）进行排序。如果您遵循该路径，只需使用 fseek 在文件上移动指针，您将能够直接在磁盘上定义的位置读取和写入元素。这足以使用任何排序算法。

注意：我的建议是对该分配使用直接磁盘排序，但切勿在现实世界中这样做！无论如何，它在排序 large 元素数量时很有用，将初始数据分成足够小的束以在内存中处理，对它们进行排序并将它们存储回磁盘，然后合并这些排序的文件.这是对无法加载到内存中的数据进行排序的唯一万无一失的方法。

Answer 4

我的猜测是，您可以使用变量来保存文件中的数字，并允许使用多个文件来保存临时数据（或者您可以随机访问的单个文件，就好像它是 4 个文件一样）。您可以使用 4 个文件实现自下而上的 2 路合并排序。它类似于 wiki 文章中关于合并排序的 4 磁带驱动器排序。

http://en.wikipedia.org/wiki/Merge_sort#Use_with_tape_drives

在不使用数组的情况下对二进制文件中的数据进行排序

Sorting data in binary file without using arrays

c++

sorting

binaryfiles