c++ - BinSearch 在冒泡排序后失败

Question

我的程序似乎突然表现得很奇怪，无论我怎么看都不知道为什么。

让我们从标题开始

    //inventoryData.h
//This is the second edition of inventory data, now featuring an actual description
//This header will load an array, sort it, and then be used in InventorySearch to produce parts and prices.
//by Robert Moore on [DATE]

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

class InventoryData{
    //Variables
    private:
        int partNum[1000];
        double price[1000];
        int invCount;

    public:
        InventoryData();//Build Up
        void loadArrays(); //Feed the data from the database into our arrays
        void arraySort(); //Bubblesort for the array
        int seqSearch(int); //Our one by one search method
        int binSearch(int); //The other search
        int returnpart(int); //Return Part Number
        double returnPrice(int); //Return price

        //Incorportate a search counter to both these searches?
                //IE: bin search found [x] (completed after [y] records)

};

InventoryData::InventoryData()
{
    //Load the array
    invCount = 0;
    for (int count = 0; count < 1000; count++)
    {
        partNum[count] = 0;
        price[count] = 0;
    }
}

void InventoryData::arraySort()
{
    int counter = 0; //Used to keep track of subscripts
    int temp = 0; //Used to sort subscript contents
    double tempPrice = 0;
    int maxSub = invCount; 
    int lastKnown  = 0; //Used to indicate what the last swapped value was
    char swap = 'Y'; //used to indicate if a swap was made or not

    while (swap == 'Y')
    {
        swap = 'N';
        counter = 0;


        while (counter < maxSub){
            if (partNum[counter] < partNum[counter+1])
            {

                //Swap the part number
                temp = partNum[counter];
                partNum[counter] = partNum[counter+1];
                partNum[counter+1] = temp;

                //Swap the price
                tempPrice = price[counter];
                price[counter] = price[counter+1];
                price[counter+1] = tempPrice;

                //Report the swap occured
                swap = 'Y';
                lastKnown = counter;
            }
            counter++;
            }//End of While Loop
            maxSub = lastKnown;
        }//End this While Loop Too
    cout<<"File sort complete."<<endl;
}

void InventoryData::loadArrays()
    {
        ifstream partIn;
        partIn.open("masterInventory.dat");
        cout<<"Loading..."<<endl;
        if (partIn.is_open())
            {
                //Prime Read
                partIn    >>    partNum[invCount]
                          >>    price[invCount];

                //cout<<partNum[invCount]<<" and "<<price[invCount] <<" have been loaded."<<endl;            

            while(!partIn.eof())
                {
                                invCount++;
                    partIn  >>  partNum[invCount]
                            >>  price[invCount];
            //  cout<<partNum[invCount]<<" and "<<price[invCount] <<" have been loaded."<<endl; 

                } //END While

            partIn.close();
            cout<<"All files loaded successfully."<<endl;
            }   //END IF*/

        else
            {
                invCount = -1;
                cout<<"File failed to open."<<endl;
            }
            //arraySort();
    }



int InventoryData::seqSearch(int searchKey)
{
    int index = 0;
    int found = -1;
    int counter = 0;
    while(index < invCount)
    {
        counter++;
        if (searchKey == partNum[index]
)
        {
            found = index;
            index = invCount;
        }
        else
        {
            index++;
        }

    }
    cout<<"(Sequential completed after reading "<< counter<<" files.)"<<endl;
    return found;

}

int InventoryData::binSearch(int searchKey)
{
    int first = 0;
    int last = invCount;
    int found = 0;
    int mid = 0;
    int counter = 0;

    while (first <= last && found == 0)
    {
        counter++;
        mid = (first + last)/2;
        if (searchKey == partNum[mid] ){
            found = 1;

            return mid;
        }
        else
        {
            if (partNum[mid] < searchKey)
            {
                first = mid+1;
            }
            else 
            {
                last = mid - 1;
            }

        }
    }
    if (found == 0)
    {
        mid  = -1;

    }
    cout<<"(Binary completed after reading "<< counter <<" files.)"<<endl;
    return mid;
}

int InventoryData::returnpart(int value)
    {
        return partNum[value];
    }

double InventoryData::returnPrice(int value)
    {
        setprecision(2);
        return price[value];
    }

有了这个设置，程序从数据库中加载数字(数字和另一组“价格”的任意随机组合)，然后我们调用函数来加载、排序和搜索数组，如 CPP 中所找到的文件

//InventorySearch
/*This file is used to search our databases
and return a value for whatever our search may
be looking for.*/
//by Robert Moore


#include "inventoryData.h"
#include <iomanip>
int main()
{
    //Declare Variable
    int tempSeq = 0;
    int tempBin = 0;
    int search = 0;
    char confirmation = 'Y';
    int searchCounter = 0;
    int partsFound = 0;
    int partsLost = 0;

    //Build Object and Load Array
    InventoryData invent;
    invent.loadArrays();
    invent.arraySort();

    //Introduction
    cout<<"Welcome to Part Search."<<endl;

//Begin Loop Here
    while(confirmation != 'N')
    {

        cout<<"Please enter a part number: ";
        searchCounter++;
        cin>>search;
        cout<<endl;


        tempSeq = invent.seqSearch(search);
        if (tempSeq != -1)
        {
              std::cout << std::fixed;
            cout<<"Sequential found part number "<<invent.returnpart(tempSeq)<< ", and it's price is "<<setprecision(2)<<invent.returnPrice(tempSeq)<<endl;
            partsFound++;
        }
        else
        {
            cout<<"Sequential search failed to find part number "<<search<<endl;
            partsLost++;
        }

        tempBin = invent.binSearch(search);
    if (tempBin != -1)
        {
            std::cout << std::fixed;
            cout<<"Binary found part number "<<invent.returnpart(tempBin)<<", and it's price is "<<setprecision(2)<<invent.returnPrice(tempBin)<<endl;
            partsFound++;
        }

    else
        {
            cout<<"Binary search failed to find part number "<<search<<endl;
            partsLost++;
        }
        cout<<"Would you like to search again? (Plese enter Y/N): ";
        cin>>confirmation;
        confirmation = toupper(confirmation);
        }

    cout<<"Today's Summary: "<<endl;
    cout<<setw(5)<<"Total searches: "<<setw(25)<<searchCounter<<endl;
    cout<<setw(5)<<"Total successful searches:"<<setw(15)<<(partsFound/2)<<endl;
    cout<<setw(5)<<"Total unsuccessful searches:"<<setw(12)<<(partsLost/2)<<endl;

    cout<<"Thank you for using Part Search. Have a nice day."<<endl;
    return 0;
}

但是，输出会遇到以下问题:顺序搜索将搜索整个数据库并找到我们的值，而 binSearch 将最多搜索 8 个值并失败。起初我以为这是由于排序加载的方式，但是一旦我将其编码出来，它仍然失败。更糟糕的是，除了添加排序之外，程序在此之前运行正常。

我已经想不出程序哪里出错了，因为这段代码在添加 arraySort() 之前一直运行良好。

Answer 1

在您的arraySort() 方法中，您应该注意这样一个事实，例如如果maxSub=10，那么对于您编写的部分

 while (counter < maxSub){
        if (partNum[counter] < partNum[counter+1])
        {
         .....
        }
 }

你可能最终会表演

 if(partNum[9]<partNum[10]){
  ....
 }

由于 C++ 不对数组执行绑定(bind)检查，因此您的代码虽然有错误，但最终可能会成功编译，并且可能(或可能不会)产生正确的结果。因此，您需要将循环条件更改为

  while((counter+1)<maxSub){
     .....
  }

此外，您的arraySort() 正在按降序排序，而您的binSearch() 已针对按升序排序的数组实现。您可以根据需要更改其中一种方法。

希望这对您有所帮助。