Поиск в ширину на бинарном дереве

Я пытаюсь пройти по двоичному дереву, чтобы найти чей-то идентификатор, используя его/ее идентификационный номер. Когда я отлаживаю эту функцию, она работает хорошо, но, с другой стороны, когда я запускаю ее напрямую, она завершается. Может кто-нибудь разобраться, пожалуйста?

struct person{
char ID[15];
char name[30] ;
char surname[30];
person *left;
person *right;
};

struct tree{
person *root;
void bfsSearch();
void BFS(person*,char*);
};

void tree::BFS(person *root,char *search)
//BFS traversal on a binary tree
{
    char *temp;
    std::deque<person *> q;
    q.push_back(root);
temp=strncpy(temp,q.front()->ID,8);
while (q.size() != 0)
{
    person *next = q.front();

    if (strcmp(search,temp)==0)
    {
      cout<<"Result: "<<q.front()->ID<<endl;
      break;
    }
    q.pop_front();

    if (next->left)
        q.push_back(next->sol);
    if (next->right)
        q.push_back(next->sag);
    temp=strncpy(temp,q.front()->ID,8);
    }
}

void tree::bfsSearch()
{
    person *scan;
    char *data,*temp;
    data=new char[15];
    scan=root;
    cout<<"Enter the Person`s ID to search: ";cin>>data;
    BFS(root,data);

}

c++ breadth-first-search binary-tree
person Who Cares    schedule 22.12.2011    source источник

Ответы (1)


arrow_upward
1
arrow_downward 

char *temp;
temp=strncpy(temp,q.front()->ID,8);

Вы копируете данные в неинициализированный указатель, что является неопределенным поведением. Вам нужно объявить temp как массив или выделить его динамически. Поскольку вы копируете только до 8 байтов, использования char temp[9]; должно быть достаточно. Обратите внимание, что strncpy оставит строку незавершенной, если ввод будет слишком длинным, поэтому вам нужно будет добавить temp[8]=0;, чтобы быть в безопасности.

Также нет смысла присваивать результат strncpy обратно temp, так как он просто возвращает свой первый аргумент.

Гораздо лучше делать что-то в стиле C++: использовать std::string и избегать всей этой возни с указателями char и нулевыми терминаторами.

person interjay    schedule 22.12.2011
comment
Я сделал это, все равно. но странно то, что когда я ищу идентификационный номер, который находится справа от корня, он работает отлично. возникает ошибка, когда я пытаюсь найти левую часть корня - person Who Cares; 22.12.2011