文件写入与二分查找：书籍记录文件的增删操作及代码实现问询

Alright, let's break this down step by step. You want to combine binary search with file I/O to manage book records (specifically deleting entries by ID), and you already have a start on your writebook function. Here's how to make this work properly, with practical code examples:

Key Precondition: Keep Records Ordered #

Binary search only works on sorted data. So your book file must store records in a fixed, sorted order (we'll use book_id as the sort key here). This is non-negotiable—without sorted records, binary search can't efficiently locate entries.

Define a Fixed-Length Record Format #

Your current writebook function concatenates fields without structure, which makes it impossible to reliably split records later. Instead, use fixed-length fields for each record. This lets you calculate the exact byte offset of any record, which is critical for file-based binary search.

First, define your struct with helper methods to convert between structs and fixed-length strings:

#include <fstream>
#include <string>
#include <sstream>
#include <cstdio>

// Fixed field lengths (adjust based on your needs)
const int BOOK_ID_LEN = 10;
const int AUTHOR_ID_LEN = 10;
const int BOOK_TITLE_LEN = 50;
const int BOOK_PRICE_LEN = 8;
const int RECORD_SIZE = BOOK_ID_LEN + AUTHOR_ID_LEN + BOOK_TITLE_LEN + BOOK_PRICE_LEN;

struct book_attributes {
    std::string book_id;
    std::string author_id;
    std::string book_title;
    double book_price;

    // Convert struct to a fixed-length string for file storage
    std::string toFixedLengthString() const {
        std::string record;
        // Pad/truncate fields to fixed lengths
        record += std::string(book_id.substr(0, BOOK_ID_LEN)) + std::string(BOOK_ID_LEN - book_id.size(), ' ');
        record += std::string(author_id.substr(0, AUTHOR_ID_LEN)) + std::string(AUTHOR_ID_LEN - author_id.size(), ' ');
        record += std::string(book_title.substr(0, BOOK_TITLE_LEN)) + std::string(BOOK_TITLE_LEN - book_title.size(), ' ');
        // Format price to 8 characters (e.g., "  19.99")
        char price_buf[BOOK_PRICE_LEN + 1];
        snprintf(price_buf, sizeof(price_buf), "%7.2f", book_price);
        record += std::string(price_buf);
        return record;
    }

    // Parse fixed-length string back to struct
    static book_attributes fromFixedLengthString(const std::string& record) {
        book_attributes book;
        // Trim trailing spaces from fields
        book.book_id = record.substr(0, BOOK_ID_LEN).substr(0, record.find_last_not_of(' ') + 1);
        book.author_id = record.substr(BOOK_ID_LEN, AUTHOR_ID_LEN).substr(0, record.find_last_not_of(' ') + 1);
        book.book_title = record.substr(BOOK_ID_LEN + AUTHOR_ID_LEN, BOOK_TITLE_LEN).substr(0, record.find_last_not_of(' ') + 1);
        book.book_price = std::stod(record.substr(BOOK_ID_LEN + AUTHOR_ID_LEN + BOOK_TITLE_LEN, BOOK_PRICE_LEN));
        return book;
    }
};

Implement Binary Search for File-Based Records #

This function locates the index of a book by book_id by calculating byte offsets and reading only the necessary records:

// Returns the index of the target book_id (0-based), or -1 if not found
int binarySearchBookID(std::fstream& stream, const std::string& target_id) {
    stream.seekg(0, std::ios::end);
    std::streampos file_size = stream.tellg();
    int total_records = file_size / RECORD_SIZE;
    if (total_records == 0) return -1;

    int left = 0;
    int right = total_records - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        std::streampos record_pos = mid * RECORD_SIZE;
        
        // Jump to the middle record
        stream.seekg(record_pos);
        std::string record(RECORD_SIZE, ' ');
        stream.read(&record[0], RECORD_SIZE);
        if (!stream) return -1; // Handle read errors

        book_attributes book = book_attributes::fromFixedLengthString(record);
        int cmp = book.book_id.compare(target_id);
        if (cmp == 0) {
            return mid; // Found the target
        } else if (cmp < 0) {
            left = mid + 1; // Target is in the right half
        } else {
            right = mid - 1; // Target is in the left half
        }
    }
    return -1; // Target not found
}

Implement the Delete Operation #

Once you've found the target record, you have two options for deletion:

1. Shift records forward (simple for small files)
2. Mark as deleted (more efficient for large files—add an is_active field to the struct)

Here's the shift-forward implementation:

bool deleteBookByID(std::fstream& stream, const std::string& target_id) {
    int target_index = binarySearchBookID(stream, target_id);
    if (target_index == -1) return false;

    stream.seekg(0, std::ios::end);
    std::streampos file_size = stream.tellg();
    int total_records = file_size / RECORD_SIZE;

    // Shift all records after the target forward by one position
    for (int i = target_index; i < total_records - 1; ++i) {
        std::streampos src_pos = (i + 1) * RECORD_SIZE;
        std::streampos dest_pos = i * RECORD_SIZE;

        // Read the next record
        stream.seekg(src_pos);
        std::string record(RECORD_SIZE, ' ');
        stream.read(&record[0], RECORD_SIZE);

        // Write it to the current position
        stream.seekp(dest_pos);
        stream.write(record.c_str(), RECORD_SIZE);
    }

    // Truncate the file to remove the now-duplicate last record
    stream.seekp((total_records - 1) * RECORD_SIZE);
    stream.truncate(stream.tellp());
    return true;
}

Refine Your writebook Function for Ordered Insertion #

To keep records sorted, your writebook function needs to find the correct insertion position (using binary search) before writing:

int writebook(std::fstream& stream, const book_attributes& BOOKS) {
    stream.seekg(0, std::ios::end);
    std::streampos file_size = stream.tellg();
    int total_records = file_size / RECORD_SIZE;

    int insert_pos = total_records; // Default to end if no smaller ID found
    int left = 0;
    int right = total_records - 1;

    // Binary search to find insertion point
    while (left <= right) {
        int mid = left + (right - left) / 2;
        std::streampos pos = mid * RECORD_SIZE;
        stream.seekg(pos);

        std::string record(RECORD_SIZE, ' ');
        stream.read(&record[0], RECORD_SIZE);
        if (!stream) break;

        book_attributes book = book_attributes::fromFixedLengthString(record);
        int cmp = BOOKS.book_id.compare(book.book_id);
        if (cmp == 0) {
            return -1; // Duplicate ID—return error
        } else if (cmp < 0) {
            insert_pos = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    // Shift records back if inserting in the middle
    if (insert_pos < total_records) {
        // Expand file to make space for new record
        stream.seekp(0, std::ios::end);
        stream.write(std::string(RECORD_SIZE, ' ').c_str(), RECORD_SIZE);

        // Shift records from end to insertion point
        for (int i = total_records - 1; i >= insert_pos; --i) {
            std::streampos src_pos = i * RECORD_SIZE;
            std::streampos dest_pos = (i + 1) * RECORD_SIZE;

            stream.seekg(src_pos);
            std::string record(RECORD_SIZE, ' ');
            stream.read(&record[0], RECORD_SIZE);

            stream.seekp(dest_pos);
            stream.write(record.c_str(), RECORD_SIZE);
        }
    }

    // Write the new record
    std::string new_record = BOOKS.toFixedLengthString();
    stream.seekp(insert_pos * RECORD_SIZE);
    stream.write(new_record.c_str(), RECORD_SIZE);
    return 0; // Success
}

Usage Example #

int main() {
    // Open file in binary read/write mode (create if missing)
    std::fstream book_file("books.dat", std::ios::in | std::ios::out | std::ios::binary);
    if (!book_file) {
        book_file.open("books.dat", std::ios::out | std::ios::binary);
        book_file.close();
        book_file.open("books.dat", std::ios::in | std::ios::out | std::ios::binary);
    }

    // Add test books (they'll be inserted in sorted order)
    book_attributes book1{"B001", "A001", "The Great Gatsby", 19.99};
    book_attributes book2{"B003", "A002", "1984", 14.99};
    book_attributes book3{"B002", "A003", "To Kill a Mockingbird", 17.50};

    writebook(book_file, book1);
    writebook(book_file, book2);
    writebook(book_file, book3); // Inserts between B001 and B003

    // Delete book B002
    if (deleteBookByID(book_file, "B002")) {
        printf("Book B002 deleted successfully!\n");
    } else {
        printf("Book B002 not found!\n");
    }

    book_file.close();
    return 0;
}

Notes for Production Use #

• Always use binary file mode (std::ios::binary) to avoid newline conversion issues that break fixed-length records.
• For large files, replace the shift-based deletion with a mark-and-clean approach (add an is_active field to the struct, mark deleted records as inactive, and periodically rebuild the file to remove inactive entries).
• Add error handling for all file operations (e.g., failed reads/writes, corrupted files) to make the code robust.

内容的提问来源于stack exchange，提问作者Mostafa Anwar