2

我需要帮助尝试搜索类对象数组。我有一个名为 users 的类,并且有一个存储 3 个玩家的数组。我希望能够在输入他的两个名字时显示特定玩家的信息,并在输入名字时删除他的记录。

我知道我可以使用矢量列表来简化此操作,但我设置了限制。我也认为可以实现线性搜索,但我不知道这是否足够有效。

#include <iostream>
#include <string>
#include <math.h>

using namespace std;

void storeinfo() ;
void showinfo() ;
void menu() ;


class user 
{
    string firstname, lastname, currentteam, position, status ;
    int age ;
public:
    user() {};
    user(string fname, string lname, string cteam, string pos, string stat, int age) 
    {
        setFirstName(fname);
        setLastName(lname);
        setCurrentTeam(cteam);
        setPosition(pos);
        setStatus(stat);
        setAge(age);
    } ;
    void setFirstName(string fname)
        {firstname = fname;}
    void setLastName(string lname)
        {lastname = lname;}
    void setCurrentTeam(string cteam)
        {currentteam = cteam;}
    void setPosition(string pos)
        {position = pos;}
    void setStatus(string stat)
        {status = stat;}
    void setAge(int _age)
        {age = _age;}

    string getFirstName()
        {return firstname ;}
    string getLastName()
        {return lastname ;}
    string getCurrentTeam()
        {return currentteam ;}
    string getPosition()
        {return position ;}
    string getStatus()
        {return status ;}
    int getAge()
        {return age ;}
};

user player[20] ;

int main()
{
    menu() ;



    cin.get() ;
    return 0 ;

}

void storeinfo()
{
    string firstname ;
    string lastname ;
    string currentteam ;
    string position;
    string status ;
    int age ;

    for (int i=0; i < 3; i++)
    {
        cout << "Enter First Name : " ; 
        cin >> firstname ;
        player[i].setFirstName(firstname) ;
        cout << "Enter Last Name : " ; 
        cin >> lastname ;
        player[i].setLastName(lastname) ;
        cout << "Enter Player's Age : " ; 
        cin >> age;
        player[i].setAge(age) ;
        cout << "Enter Current Team : " ; 
        cin >> currentteam ;
        player[i].setCurrentTeam(currentteam) ;
        cout << "Enter Position : " ; 
        cin >> position ;
        player[i].setPosition(position) ;
        cout << "Enter Status : " ; 
        cin >> status ;
        player[i].setStatus(status) ;

        cout << "\n\n\n" ;
    }

    /*cout << string(50, '\n');*/

    menu() ;

}

void showinfo()
{
    for (int i=0; i < 3; i++)
    {
        cout << "First Name : " << player[i].getFirstName() << "\n" << "Last Name : " << player[i].getLastName() <<
            "\n" << "Age : " << player[i].getAge() << "\n" << "Current Team : " << player[i].getCurrentTeam() << 
            "\n" << "Position : " << player[i].getPosition() << "\n" << "Status :  " << player[i].getStatus()  << "\n\n";
    }

    cin.get() ;

    menu() ;
}

void menu()
{
    cout << "\n MENU" << "\n" ;
    cout << "\n 1. Store Player Information" ;
    cout << "\n 2. Show Player Informaton" ;
    cout << "\n 0. Exit \n \n" ;

    string x =  "";
    cin >> x ;

    if (x=="a")
    { 
        storeinfo() ;
    }
    else if (x=="b")
    {
        showinfo() ;
    }
    else if (x=="c")
    {
        exit(0) ;
    }
    else
    {
        cout << "Invalid Choice" ;
        menu() ;
    }   
}

我已经做了一个线性搜索算法,似乎正在工作,但我得到的输出不正确下面是这两个函数的代码,再次感谢你

int linsearch(string val)
{
    for (int j=0; j < 3; j++)
    {
        if  (player[j].getLastName()==val)
        {
            return j;
        }
        else 
        {
            return 1;
        }
    }




void showinfo()
{
    string search;
    int found ;


    cout << "Please Enter The Player's Last Name : " ;
    cin >> search ;

    found=linsearch(search);

    if (found== 1)
    {
        cout << "\n There is no player called " << search ;
    }
    else
    {
        cout << "\n First Name : " << player[found].getFirstName() << "\n" << "Last Name : " << player[found].getLastName() <<
            "\n" << "Age : " << player[found].getAge() << "\n" << "Current Team : " << player[found].getCurrentTeam() << 
            "\n" << "Position : " << player[found].getPosition() << "\n" << "Status :  " << player[found].getStatus()  << "\n\n";
    }

    cin.get() ;

    menu() ;

}
4

2 回答 2

1

如果您的数据集可以变得很大,那么哈希表是一个可以想到的解决方案。请务必为您的任务选择一个没有太多冲突的散列算法。顺便说一下,有“完美的散列算法”——如果“始终有 0 次冲突”很重要,你应该研究一下——无冲突、快速的散列表将显着加快处理速度

于 2013-01-22T20:04:56.840 回答
0

The standard solution for mapping a key (like the user's name) to a record of some kind is a map.

The stock std::map uses a balanced tree, which gives you O(log N) searching, which is usually good enough (and much better than linear), and also lets you iterate through the names in sorted order. This requires an ordered type, meaning user1 < user2 makes sense.

Alternatively, std::unordered_map uses a hash table, which gives you O(1) searching, but doesn't have any ordering. This requires a hashable type, meaning hash(user1) makes sense. It also requires C++11, or a C++03 implementation that has it as part of tr1, or boost.

Which one is appropriate depends on your needs—but often, they're both just fine, and it's just a matter of whether you have a natural ordering or a natural hash function.

Besides being more efficient for both searching and deleting from the middle than a vector, list, or other collection that requires linear searches, it's also a lot simpler and more natural. For example, compare these two:

user find_by_name(vector<user> users, string name) {
    return find_if(users.begin(), users.end(), [](auto it) { it->name == name; });
}

user find_by_name(map<string, user> users, string name) {
    return map.find(name);
}

(And, if you don't have C++11 lambdas, the find_if is even worse.)

As for whether "a linear search… is efficient enough", that really depends on how large the collection is. If you're doing 1 search every few seconds through 100 users, just about anything is efficient enough. If you're doing thousands of searches through millions of users, it probably isn't. If you don't know enough to estimate, just try it and see. Profiling should almost always be the first step in any optimization question. However, in this case, given that map or unordered_map is simpler, easier to read, and more natural than vector or list in the first place, I don't think you need to bother with that.

于 2013-01-22T20:14:40.507 回答