Функция поиска с несколькими типами данных в двоичном дереве поиска C

У меня есть BST с идентификатором в качестве ключа следующим образом:

struct node
{
    int id;
    char name[100];
    struct node *right;
    struct node *left;
};

Вот код для поиска идентификатора:

struct node* search(struct node *root, int x)
{
    if(root==NULL || root->id==x)
        return root;
    else if(x>root->id)
        return search(root->right, x);
    else
        return search(root->left,x);
}

Но что, если я хочу найти имя? Является ли это возможным? Любое предложение? Спасибо

У вас может быть общий интерфейс/функция для поиска, например struct node* bst_search (struct node *root, struct node* snode, int stype), где stype указывает, какое поле использовать, а snode будет заполнять это поле перед вызовом. Вы должны написать индивидуальную функцию поиска на основе stype и вызвать их соответствующим образом внутри bst_search ().

SparKot 10.04.2022 15:09
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
Четыре эффективных способа центрирования блочных элементов в CSS
Четыре эффективных способа центрирования блочных элементов в CSS
У каждого из нас бывали случаи, когда нам нужно отцентрировать блочный элемент, но мы не знаем, как это сделать. Даже если мы реализуем какой-то...
1
1
27
3
Перейти к ответу Данный вопрос помечен как решенный

Ответы 3

Ответ принят как подходящий

Поскольку бинарное дерево упорядочено на основе ключа int id, вам нужно обойти все узлы дерева, чтобы найти узел с указанным именем, используя строковую функцию strcmp.

Например

#include <string.h>

//...

struct node* search(struct node *root, const char *name )
{
    if(root==NULL || strcmp( root->name, name ) == 0 )
    {
        return root;
    }
    else 
    {
        struct node *target = search(root->left, name);
        return target != NULL ? target : search(root->right, name);
    }
}

Конечно, это возможно. Для этого вы можете использовать стркмп или любую другую собственную функцию. Однако BST создается с ключом я бы, поэтому вы не получите выгоды от снижения сложности поиска, которое обеспечивает BST.

На самом деле у меня была эта проблема раньше, в итоге я переписал свою собственную реализацию BS вместе с некоторыми улучшениями. поэтому я генерировал определенное число (токен) для каждого слова (в основном, как хеширование, но с числами), и всякий раз, когда я хочу найти слово, оно преобразуется в числовые токены, а затем обычно использует алгоритм BS.

допустим алгоритм хеширования работает так

  • Каждая буква будет иметь предопределенное значение в соответствии с ее алфавитным порядком A->1B->1...
  • Порядок букв в слове играет роль, например, слово yap не может быть таким же, как pay, поэтому мы можем иметь значение i = 1, поэтому всякий раз, когда мы токенизируем одну букву, мы добавляем этот токен к i, поэтому токен следующей буквы мы будем возведен в степень i или что-то подобное
  • Мы также должны ввести пунктуацию count
#include <math.h>
...
/* 
---------------------- NOTE ----------------------
 YOU PROBABLY WILL NEED TO IMPLEMENT A HASHMAP
 TO STORE THE ALPHABET LETTERS PRE-DEFINED VALUE,
 I'LL ASSUME THAT IT ALREADY EXISTS AND I WILL
 USE THIS METHOD TO GRAB THE VALUE
 get_value(hashmap,value);
 I'LL ALSO ASSUME THAT EVERY VALUE THE METHOD
 ABOVE RETURN EXISTS IN THE HASHMAP
-------------------------------------------------
*/
struct AlphabetOrderHashMap* hashmap = new_alphabet_order_hashmap();
int hash(char* word){
  int token = 0;
  int prev_letter_token = 1; // to address the letter order in the word
  for(int i =0;i < strlen(word);i++){
    prev_letter_token = hashletter(word[i],prev_letter_token);
    token +=  prev_letter_token
  }
  return token;

}
int hashletter(char letter,int i){
  int token = 0;
  token += (int)(pow(get_value(hashmap,letter),i) / (int)letter)
  return token;
}
...

и тогда я верю, что вы можете решить это отсюда. поэтому вместо того, чтобы помещать слово в дерево как char[], лучше использовать токен.

вы также можете заменить идентификатор токеном, поэтому вам нужно будет выполнить поиск только один раз

Другие вопросы по теме