0

クラス プロジェクトの一般的な二分探索関数を実装する必要があります。テスト ファイルとヘッダー ファイル (クラス定義) が提供されており、変更することはできません。

テストした 3 つのテスト オブジェクト タイプのうち 2 つを使用して動作させることができました。

これが私のアルゴリズムです：

template <typename T, typename V>
int binarySearch(T* list[], const V& searchValue,
    const int firstIndex, const int lastIndex) { 

        int half = (firstIndex + lastIndex) /2;

        // if not completly split down already
        if(firstIndex != lastIndex && half != 0){ 

            if(searchValue < *list[half]){  
                // lower half of array
                binarySearch(list, searchValue, firstIndex, half); 
            }
            else if(searchValue > *list[half]){     
                // upper half of array
                binarySearch(list, searchValue, ++half, lastIndex); 
            }
        }
        else if(searchValue == *list[half]){
            return half; // found it
        }
        return -1; // didnt find it
}

オブジェクトのテスト ケースの 3 つの配列を次に示します。

// pointers to child class objects
Customer* customer[] = { new Customer(1002, 100000.50, "F4", "L1"),
    new Customer(1004, 45000.90, "F1", "L3"),
    new Customer(1003, 120000, "F3", "L2"),
    new Customer(1001, 340000, "F2", "L4")
};

// pointers to child class objects
Employee* employee[] = { new Employee(102, 65000, "F2", "L1"),
    new Employee(104, 45000, "F4", "L3"),
    new Employee(103, 120000, "F1", "L2"),
    new Employee(101, 35000, "F3", "L4")
};

// pointers to parent class objects
Person* person[] = { customer[0],
    customer[3],
    employee[3],
    employee[0],
    employee[2],
    customer[1],
    employee[1],
    customer[2]
};

次のように、各オブジェクトで関数を呼び出しています。

// Search the customer array. -> WORKS
cout << endl
     << "Searching customer array for customer with cId = 1002: "
     << (binarySearch(customer, 1002, 0, 3) != -1? "found it." : "did not find it.")
     << endl;

// Search the employee array. -> WORKS
cout << "Searching employee array for employee with eId = 105: "
     << (binarySearch(employee, 105, 0, 3) != -1? "found it." : "did not find it.")
     << endl;

// Search the person array. -> OPERATOR ERRORS
cout << "Searching people array for person with name = 'Mickey Mouse': "
     << (binarySearch(person, "Mickey Mouse", 0, 7) != -1? "found it." : "did not find it.")
     << endl;

検索関数は、Employee オブジェクト配列と Customer オブジェクト配列の両方で正常に実行されます。Person 配列で検索を実行しようとすると、次のような比較演算子ごとに 3 つのエラーが発生します。

既に提供されている関数定義から、3 つのオブジェクトすべてに対してまったく同じ方法で演算子のオーバーロードを実装しました。person クラスでは、次のオーバーロードされた演算子を実装しました。

bool operator ==(const Person& lhs, const Person& rhs){
    if(lhs.getKeyValue() == rhs.getKeyValue())
        return true;
    return false;
}
bool operator <(const Person& lhs, const Person& rhs){
    if(lhs.getKeyValue() < rhs.getKeyValue())
        return true;
    return false;
}
bool operator >(const Person& lhs, const Person& rhs){
    if(lhs.getKeyValue() > rhs.getKeyValue())
        return true;
    return false;
}

2 つの人物オブジェクトで簡易テスト比較を行うと、問題なく比較できます。すなわち:

cout << "test person compare: " << ("mickey mouse" < person[1] ? "true" : "false");

ここからどこに持っていけばいいのかわからないので、方向性を教えていただければ幸いです。

編集: 追加 (完全な個人ヘッダー ファイル):

#ifndef PERSON_H
#define PERSON_H

#include <string>
#include <iostream>

using namespace std;

namespace P03 {
    class Person {

    private:
        string firstName;
        string lastName;

    public:
        /* Initializes the object.
         */
        Person(const string& firstName = "na", const string& lastName = "na");

        /* Getter methods retun the field value.
         */
        string getFirstName() const;
        string getLastName() const;

        /* Returns the eid.
         */
        string getKeyValue() const;

        /* Returns the compound value: <lastName><space><firstName>
         */
        string getName() const;

        /* Setter methods, set the object.
         */
        void setFirstName(const string& firstName);
        void setLastName(const string& lastName);


        /* Returns the object formatted as:
        *  Person{ firstName=<firstName>, lastName=<lastName> }
        */
        virtual string toString() const;
    }; // end Person


    /* Displays a Person to the screen.
     * Calls the toString() method.
     */
    ostream& operator <<(ostream& out, const Person& person);

    /* The following relational operators compare two instances of the
     * Person class. The comparison is made on the compound value of:
     * <lastName><space><firstName>
     */
    bool operator ==(const Person& lhs, const Person& rhs);
    bool operator !=(const Person& lhs, const Person& rhs);
    bool operator <(const Person& lhs, const Person& rhs);
    bool operator <=(const Person& lhs, const Person& rhs);
    bool operator >(const Person& lhs, const Person& rhs);
    bool operator >=(const Person& lhs, const Person& rhs);

} // end namespace P03

#endif
4

1 に答える 1

1

文字列を人に変換する方法がないため、次のような行は失敗します。

        if(searchValue < *list[half]){

一時的に次のように変更すると、デバッグが改善されます。

        if (T(searchValue) < *list[half]){

operator<これがこのコードが機能する唯一の方法*list[half]ですconst T &。

于 2013-03-12T01:47:48.177 に答える