使用 BinarySearch 算法的 C++ 函数(.bin 文件)

Question

我必须创建一个函数来检查特定单词是否存在于 .bin 文件中。我想使用二进制搜索算法。问题是，我必须从 .bin 文件中读取，所以我感到困惑(因为没有行，对吧？)。功能对我不起作用。它说“特定词”(由用户输入)不存在，即使它确实存在。 任何帮助都会很好。

#include <iostream>
#include <string>
#include <fstream>
#include <cstring>
#include <algorithm>

using namespace std;
const int buffer_size = 30;

void Create_Bin_File ()
{
ifstream fin ("example.txt");  
ofstream fout ("Binary.bin", ios::binary); 
const unsigned int RECORD_SIZE = 30; // was BUFFER_SIZE
char buffer[RECORD_SIZE] = {0}; // zero init buffer

while (fin.getline (buffer, RECORD_SIZE))
{
fout.write (buffer, RECORD_SIZE);
// refill buffer with zeroes for next time round
fill_n (buffer, RECORD_SIZE, 0);
}
fin.close ();
fout.close ();
}

void Binary_Search (const string& filename, string SearchVal)
{
ifstream file (filename.c_str(), ios::binary);
if (file.is_open())
{
    cout << "The file is opened"<< endl;
    cout << "\n";
}
else
{
    cout << "Error opening file"<< endl;
    cout << "\n";
    return; // no point continuing Binary_Search() if file failed to open!
}
const unsigned int RECORD_SIZE = 30; // was BUFFER_SIZE
char buffer[RECORD_SIZE] = {0}; // zero init buffer
int recordCount  =  0;
int recordWanted = -1;
while (file.read(buffer, RECORD_SIZE))
{
    if(SearchVal == buffer)
    {

        recordWanted = recordCount;
        // if this was just a naive search loop could bail out now...
    }
    cout << recordCount << " : " << buffer << "\n";

    // refill buffer with zeroes for next time round
    fill_n (buffer, RECORD_SIZE, 0);
    ++recordCount;
}

cout << "\n";
cout << "file contains " << recordCount << " records\n";
cout << "\n";
if (recordWanted == -1)

    cout << "record wanted could not be found\n";
else

    cout << "record wanted is at index " << recordWanted << " records\n";
cout << "\n";
} 




int main()
{

Create_Bin_File();  
string word;
cout << "Enter word, that you want to find in a file: " << endl;
cin >> word;

Binary_Search("Binary.bin", word);


return 0;
}

任务: 》用C++写一个程序，如果程序是用文件工作的，就不要把文件的全部内容复制到操作内存中。文件部分是指固定长度的记录。 H7。编写一个程序，将所有标准 C++ 保留字放入有序表中(据我所知，有序表意味着这些词按字母顺序排列)。编写一个函数，该函数使用二进制搜索检查输入字符串(长度 30)是否为 C++ 保留字。表应作为直接访问文件。 C++ 保留程序应从文本文件中读取。”

---

关于 BinarySearch 函数的 grek40 解决方案:

所以我做了记录功能:

std::string GetRecord(std::ifstream& inFile, int pos)
{
char buffer[RECORD_SIZE];
// clear possible flags like EOF, before moving the read position
inFile.clear();
// set the file read position to the requested record position
inFile.seekg(pos * RECORD_SIZE, std::ios::beg);
inFile.read(buffer, RECORD_SIZE);
// note: automatic conversion from char[] to std::string
return buffer;
}

和二进制搜索功能:(已解决 - 工作!)

void Binary_Search (const string& filename, string SearchVal)
{
ifstream file (filename.c_str(), ios::binary);
if (file.is_open())
{
cout << "The file is opened"<< endl;
cout << "\n";
}
else
{
cout << "Error opening file"<< endl;
cout << "\n";
return; // no point continuing Binary_Search() if file failed to open!
}
int pos = 0;
int lowerLimit = 0;
int recordCount = 73; // Calculated before[I'll change this part, when I get      this function working]
                  // At this point, there's exactly 73 records in .bin file
 char buffer[RECORD_SIZE] = {0}; // zero init buffer (while loop will overwrite with record values)
 int upperLimit = recordCount;
 while ( (lowerLimit < upperLimit) ) // Searching as long as it doesn't find it
 {
    pos = (lowerLimit + upperLimit) / 2;
    std::string buffer = GetRecord(file, pos);

    if (buffer == SearchVal)
    {
        cout << "Found!";
        lowerLimit = 1; // For stopping (If found!)
        upperLimit = 0; // For stopping
    }
    else if (SearchVal > buffer)
    {
        lowerLimit = pos + 1;
    }
    else if (SearchVal < buffer)
    {
     upperLimit = pos;
    }

}
}

Answer 1

据我所知，您有一个解决方案，您可以将所有给定的单词从文本文件移动到二进制文件，并且您可以在二进制文件中找到单词(如果它们存在)。

我假设您创建了二进制文件，其中包含等长 (30) 的已排序记录，其中每条记录的文本部分以零结尾。

现在，让我们创建一个函数，它接受一个打开的二进制文件流和一个记录位置，并返回该记录位置的字符串:

std::string GetRecord(std::ifstream& inFile, int pos)
{
    char buffer[RECORD_SIZE];
    // clear possible flags like EOF, before moving the read position
    inFile.clear();
    // set the file read position to the requested record position
    inFile.seekg(pos * RECORD_SIZE, std::ios::beg);
    inFile.read(buffer, RECORD_SIZE);
    // note: automatic conversion from char[] to std::string
    return buffer;
}

对于二分搜索，你应该为你的搜索位置定义一个上限和下限。注意上限是lastItemPosition + 1 , 所以你实际上永远不会访问基于零的索引中的这个位置。

int lowerLimit = 0;
int upperLimit = recordCount; // count when reading the lines in .txt

您需要搜索一个结果，只要您没有找到它并且 lowerLimit < upperLimit .

您的下一个搜索词是 position = (lowerLimit + upperLimit) / 2; .

将单词与您的搜索文本进行比较。关于平等，你完成了。

如果单词小于搜索文本，您的结果位置可能会比您刚刚查看的索引更高。所以你需要调整lowerLimit = position + 1

如果单词大于搜索文本，您的结果位置可能会比您刚刚查看的索引更低。 upperLimit = position

您按照说明使用调整后的上限和下限重复搜索。