使用反向冒泡排序按字母顺序排列数据结构数组

Question

我正在尝试按字母顺序对 2 元素数据结构的数组进行排序。整个程序将数据文件读入数组，然后按字母顺序排列数组并通过查询对其进行搜索。

我的问题是，排序后数据库的第一个条目被清除。这可以在本文末尾的输出中看到。

代码如下

#include <iostream>                 //Required if your program does any I/O
#include <fstream>                  //Required for file I/O
#include <string>                   //Required if your program uses C++ strings

using namespace std;                //Required for ANSI C++ 1998 standard.

struct Book     // Data structure of database entry
{
       string title;
       string author;
};

const int ARRAY_SIZE = 1000;      //Maximum database size
Book books [ARRAY_SIZE];          //Library database

void loadData ( int& librarySize ); //Function prototype to load data file into database
void showAll ( int librarySize );  //Function prototype to display entire database contents
void menu ( int librarySize ); //Function prototype to process menu of database functions
void searchByAuthor ( int librarySize );  //Function prototype to search database by author
void searchByTitle ( int librarySize );   //Function prototype to search database by title
void sortByAuthor ( int librarySize );    //Function prototype to alphabetically sort database by author
void sortByTitle ( int librarySize );     //Function prototype to alphabetically sort database by title

int main ()
{ 
    int librarySize = 0;           //Declaring and initializing databse size variable

    cout << "Welcome to Greathouse's Library Database" << endl;

    loadData ( librarySize );        //Prompt for and loading of data file into database.

    menu ( librarySize );  //Processing of database functions menu

    system("pause");
    exit(0);
}

void loadData ( int& librarySize )
{
    ifstream inputFile;         //File I/O variable
    string inputFileName;       //Data file path

    //Prompt for data file path
    cout << "Please enter the name of the backup file: ";
    getline(cin, inputFileName);

    // Open the data file.
    inputFile.open(inputFileName.c_str());      // Need .c_str() to convert a C++ string to a C-style string

    // Check the file opened successfully.
    if ( ! inputFile.is_open())
    {
        cout << "Unable to open input file." << endl;
        system("pause");
        exit(-1);
    }

    //Read data file into database
    for ( librarySize = 0; inputFile.peek() != EOF && librarySize < ARRAY_SIZE ; librarySize++ )
    {
        getline( inputFile, books[librarySize].title );
        getline( inputFile, books[librarySize].author );
    }

    //Confirm number of records loaded with user
    cout << librarySize << " records loaded successfully." << endl;

    // Clear EOF flag on file stream
    inputFile.clear();

    // Return to the beginning of the file stream
    inputFile.seekg(0);
}

void menu ( int librarySize )
{
     char command = ' ';

     //Display and processing of menu and commands until escape character 'q' is entered
     while ( command != 'Q' && command != 'q' )
     {
           cout << "Would you like to (Q)uit, (S)howall, Search by (A)uthor, or Search by (T)itle? : ";
           cin >> command;

           switch ( command )
           {
                  case 'S':
                  case 's':

                      showAll ( librarySize );           //Call to function to show database contents in response to user input
                      break;

                 case 'A':
                 case 'a':

                      searchByAuthor ( librarySize );    //Call to function to search database by author and display results alphabetically in response to user input

                      break;

                 case 'T':
                 case 't':

                      searchByTitle ( librarySize );     //Call to function to search database by title and display results alphabetically in response to user input

                      break;

                 case 'Q':
                 case 'q':

                      break;        //Case option to prevent extraneous output when quitting program

                 default:

                         cout << "That is not a valid command." << endl;
                         break;
          }
    }
}

void searchByAuthor ( int librarySize )   //Function to search database by author
{
     string authorSearch = " ";       //User query
     int authorResults = 0;  //Number of query results found
     int iteration = 0;  //Loop counting variable

     //Prompt for and reading of user query
     cout << "Author: : ";
     cin >> authorSearch;

     sortByAuthor ( librarySize ); //Call to sort database alphabetically by author so output will be alphabetical

     //Iterative search of database for all instances of query
     for ( iteration = 0; iteration <= librarySize; iteration++ )
     {
         if ( books[iteration].author.find ( authorSearch ) != string::npos )
         {
            cout << books[iteration].title << " (" << books[iteration].author << ")" << endl;
            authorResults++;
         }
     }

     cout << authorResults << " records found." << endl;                      //Output of number of results
}

void searchByTitle ( int librarySize )
{
     string titleSearch = " ";       //User query
     int titleResults = 0;  //Number of query results found
     int iteration = 0; //Loop counting variable

     //Prompt for and reading of user query
     cout << "Title: ";
     cin >> titleSearch;

     sortByTitle ( librarySize );     //Call to sort database alphabetically by title so output will be alphabetical

     //Iterative search of database for all instances of query
     for ( iteration = 0; iteration <= librarySize; iteration++ )
     {
         if ( books[iteration].title.find ( titleSearch ) != string::npos )
         {
            cout << books[iteration].title << " (" << books[iteration].author << ")" << endl;
            titleResults++;
         }                         
     }

     cout << titleResults << " records found." << endl;                       //Output of number of results
}

void showAll ( int librarySize )       //Function to show database contents
{
     //Iterative walk through database to display contents
     for ( int iteration = 0; iteration < librarySize; iteration++ )
     {
         cout << books[iteration].title << " (" << books[iteration].author << ")" << endl;
     }
}

void sortByAuthor ( int librarySize ) //Function to sort database alphabetically by author
{
     //Bubble sort of databse alphabetically by author
     for ( int pass = 0; pass < librarySize ; pass++ )
     {
         for ( int iteration = 0; iteration < librarySize - pass; iteration++ )
         {             
             if ( books[iteration].author > books[iteration+1].author )
             {
                  swap ( books[iteration] , books[iteration+1] );
             }
         }
     }
}

void sortByTitle ( int librarySize )      //Function to sort database alphabetically by title
{
     //Bubble sort of databse alphabetically by title
     for ( int pass = 0; pass < librarySize ; pass++ )
     {
         for ( int iteration = 0; iteration < librarySize - pass; iteration++ )
         {             
             if ( books[iteration].title > books[iteration+1].title )
             {
                  swap ( books[iteration] , books[iteration+1] );
             }
         }
     }
}

测试数据是

Objects First with Java  
Barnes and Kolling  
Game Development Essentials  
Novak  
The Game Maker's Apprentice  
Overmars  
C++ Programming: From Problem Analysis...  
Malik  
C++ Programming Lab Manual  
Scholl  
Beginning LINUX Programming  
Stones and Matthew  
C++ Programming: Program Design Including...  
D. S. Malik  
C++ How to Program  
Deitel and Deitel  
Programming and Problem Solving with C++  
Dale, Weems, Headington  
Game Character Development with Maya  
Ward  
Developing Games in Java  
Brackeen  
C# Programming  
Harvey, Robinson, Templeman, Watson  
Java Programming  
Farrell  
Audio for Games  
Brandon  

错误输出是

Welcome to Greathouse's Library Database
Please enter the name of the backup file: library.txt
14 records loaded successfully.
Would you like to (Q)uit, (S)howall, Search by (A)uthor, or Search by (T)itle? :
 s
Objects First with Java (Barnes and Kolling)
Game Development Essentials (Novak)
The Game Maker's Apprentice (Overmars)
C++ Programming: From Problem Analysis... (Malik)
C++ Programming Lab Manual (Scholl)
Beginning LINUX Programming (Stones and Matthew)
C++ Programming: Program Design Including... (D. S. Malik)
C++ How to Program (Deitel and Deitel)
Programming and Problem Solving with C++ (Dale, Weems, Headington)
Game Character Development with Maya (Ward)
Developing Games in Java (Brackeen)
C# Programming (Harvey, Robinson, Templeman, Watson)
Java Programming (Farrell)
Audio for Games (Brandon)
Would you like to (Q)uit, (S)howall, Search by (A)uthor, or Search by (T)itle? :
 t
Title: Game
Audio for Games (Brandon)
Developing Games in Java (Brackeen)
Game Character Development with Maya (Ward)
Game Development Essentials (Novak)
The Game Maker's Apprentice (Overmars)
5 records found.
Would you like to (Q)uit, (S)howall, Search by (A)uthor, or Search by (T)itle? :
 s
 ()
Audio for Games (Brandon)
Beginning LINUX Programming (Stones and Matthew)
C# Programming (Harvey, Robinson, Templeman, Watson)
C++ How to Program (Deitel and Deitel)
C++ Programming Lab Manual (Scholl)
C++ Programming: From Problem Analysis... (Malik)
C++ Programming: Program Design Including... (D. S. Malik)
Developing Games in Java (Brackeen)
Game Character Development with Maya (Ward)
Game Development Essentials (Novak)
Java Programming (Farrell)
Objects First with Java (Barnes and Kolling)
Programming and Problem Solving with C++ (Dale, Weems, Headington)
Would you like to (Q)uit, (S)howall, Search by (A)uthor, or Search by (T)itle? :

Answer 1

在大多数循环中，您使用以下条件：

iteration <= librarySize

数组索引范围从 0 到 librarySize - 1 （因为这些是由 loadData 填充的索引>)，因此数组中的最后一个有效条目是 books[librarySize - 1]。尝试将循环条件更改为：

iteration < librarySize

编辑：排序函数中还存在另一个问题：您正在尝试访问books[iteration+1]，它将再次出现第一次通过时的边界。您的内部循环应该只达到 librarySize - pass - 1：

iteration < librarySize - pass - 1

Answer 2

问题在于你的“泡沫”发生在哪里。在两个循环中，您都从数组 pos 0 开始，您需要向上移动，因为每个第一个元素都位于正确的位置。结局永远不会得到解决。

这是一些我没有测试过的代码，所以它可能会减少 1 等。但是你明白了

 for ( int pass = 0; pass <= librarySize ; pass++ )
 {
     for ( int iteration = 0; iteration <= librarySize - pass; iteration++ )
     {             
         if ( books[iteration+pass].title > books[iteration+pass+1].title )
         {
              swap ( books[iteration+pass] , books[iteration+pass+1] );
         }
     }
 }

或者你可以这样做

 for ( int pass = 0; pass <= librarySize ; pass++ )
 {
     for ( int iteration = pass; iteration <= librarySize ; iteration++ )
     {             
         if ( books[iteration].title > books[iteration+1].title )
         {
              swap ( books[iteration] , books[iteration+1] );
         }
     }
 }