1

我被要求使用 shell 排序对文件进行就地排序（也使用快速排序，但我认为如果我找到一种方法，我将能够同时完成这两种方法）。我一直在想什么可能会有所帮助，但我找不到办法。我有一个数组的算法，但我想不出一种让它与文件一起工作的方法。

有什么办法可以做到这一点？

编辑：

在 André Puel 发布的代码的帮助下，我能够编写一些目前有效的代码，如果你想检查一下，这里是：

#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <sstream>
using namespace std;

int toNum(const string &s) {
  stringstream ss(s);
  int n;
  ss >> n;
  return n;
}

string toStr(int n) {
  stringstream ss;
  ss << n;
  string s;
  ss >> s;
  return string(5 - s.size(),' ') + s;
}

int getNum(fstream &f,int pos) {
  f.seekg(pos*5);
  string s;
  for(int i = 0; i < 5; ++i) s += f.get();
  return toNum(s);
}

void putNum(fstream &f, int pos,int n) {
  f.seekp(pos*5);
  f.write(toStr(n).c_str(),5);
}

int main() {
  fstream input("entrada1",fstream::in | fstream::out);
  string aux;
  getline(input,aux);
  int n = aux.size() / 5,temp,j;

  int gaps[] = {701,301,132,57,23,10,4,1};
  int g = sizeof(gaps)/sizeof(gaps[0]);
  for(int k = 0; k < g; ++k) {
    for(int i = k; i < n; ++i) {
      temp = getNum(input,i);
      for(j = i; j >= k and getNum(input,j - k) > temp; j -= k) {
        putNum(input,j,getNum(input,j - k));
      }
      putNum(input,j,temp);
    }
  }
  input.close();
  return 0;
}
4

1 回答 1

3

当你在 C++ 中打开一个文件时，你有两个指针。getter 指针和 putter 指针。它们指示您在文件中写入和读取的位置。

使用seekp，你可以告诉你想写的地方。使用tellp你知道你要在哪里写。每次你写东西时，推杆指针都会自动前进。

getter 指针也是如此，函数是seekg和tellg。

使用这些操作，您可以轻松地模拟一个数组。让我给你看一些代码：

class FileArray {
public:
    FileArray(const char* path) 
    : file(path, std::fstream::app|std::fstream::binary)
    {
        file.seekg(0,std::fstream::end);
        size = file.tellg();
    }

    void write(unsigned pos, char data) {
        assert(pos < size );
        file.tellp(pos);
        file.put(data);
    }

    char read(unsigned pos) {
        assert(pos < size);
        file.seekg(pos);
        return file.get();
    }
private:
    std::fstream file;
    std::size_t size;
}

这是一种处理文件的幼稚方法，因为您假设随机访问。好吧，随机访问是正确的，但它可能会很慢。当您访问彼此靠近的数据（空间位置）时，文件流的工作速度更快。

尽管这是开始处理您的问题的好方法，但您将获得文件 IO 的经验，并且您将最终找出提高特定问题性能的方法。让我们保持婴儿的脚步。

我想让您注意的另一件事是，当您执行写入时，数据将被重定向到将写入文件的 fstream。我知道内核会尝试缓存这些东西，并优化速度，但如果你有某种缓存层来避免直接写入磁盘，那就更好了。

最后，我假设您正在处理字符（因为它会更容易），但是您可以处理其他数据类型，您只需要注意数据类型的索引和大小。例如，long long类型确实有 8 个字节的大小，如果您想访问文件数组中的第一个元素，您将访问位置 8*0，并且您必须读取 8 个字节。如果您想要第 10 个元素，您将访问位置 8*10 并再次读取 8 个字节的数据以构造该long long值。

于 2013-02-06T17:20:02.683 回答