Ничто не встроено в сам язык или стандартную библиотеку, но, в зависимости от ваших требований, есть несколько способов сделать это.
Если набор данных останется относительно небольшим, самый простойрешение состоит в том, чтобы просто иметь массив структур вдоль строк:
typedef struct {
char *key;
int val;
} tElement;
, а затем использовать последовательный поиск для их поиска.Имейте функции, которые вставляют ключи, удаляют ключи и ищут ключи так, чтобы, если вам нужно изменить это в будущем, сам API не изменился.Псевдокод:
def init:
create g.key[100] as string
create g.val[100] as integer
set g.size to 0
def add (key,val):
if lookup(key) != not_found:
return already_exists
if g.size == 100:
return no_space
g.key[g.size] = key
g.val[g.size] = val
g.size = g.size + 1
return okay
def del (key):
pos = lookup (key)
if pos == not_found:
return no_such_key
if pos < g.size - 1:
g.key[pos] = g.key[g.size-1]
g.val[pos] = g.val[g.size-1]
g.size = g.size - 1
def find (key):
for pos goes from 0 to g.size-1:
if g.key[pos] == key:
return pos
return not_found
Вставка означает, что она не существует, а затем просто прикрепляет элемент до конца (вы будете поддерживать отдельную переменную размера для структуры).Удаление означает поиск элемента, затем просто перезаписать его последним использованным элементом и уменьшить переменную размера.
Теперь это не самый эффективный метод в мире, но вы должны помнить, что он обычно только делаетразница, так как ваш набор данных становится намного больше.Разница между двоичным деревом или хешем и последовательным поиском не имеет значения, скажем, для 20 записей.Я даже использовал пузырьковую сортировку для небольших наборов данных, где более эффективный не был доступен.Это связано с тем, что кодирование выполняется очень быстро, а производительность не имеет значения.
Поднявшись дальше, вы можете удалить фиксированный верхний размер, используя связанный список.Поиск все еще относительно неэффективен, поскольку вы делаете это последовательно, но применяются те же предостережения, что и для решения с массивами, описанного выше.Стоимость удаления верхней границы - это небольшое наказание за вставку и удаление.
Если вы хотите немного большей производительности и нефиксированного верхнего предела, вы можете использовать двоичное дерево для хранения элементов,Это избавляет от последовательного поиска при поиске ключей и подходит для несколько больших наборов данных.
Если вы не знаете , насколько большим будет ваш набор данных, я бы подумалэто абсолютный минимум.
Хеш, вероятно, следующий шаг оттуда.Это выполняет функцию над строкой для получения номера сегмента (обычно рассматривается как некоторый индекс массива).Это поиск O (1), но цель состоит в том, чтобы иметь хеш-функцию, которая выделяет только один элемент на группу, так что для получения значения не требуется никакой дополнительной обработки.
Вырожденный регистр "всех элементов водин и тот же сегмент "ничем не отличается от массива или связанного списка.
Для максимальной производительности и при условии, что ключи фиксированы и известны заранее, вы можете фактически создать свою собственную функцию хеширования на основе ключейсами по себе.
Зная ключи заранее, у вас есть дополнительная информация, которая позволяет вам полностью оптимизировать функцию хеширования для генерации фактического значения, чтобы вы даже не задействовали сегменты - значение, генерируемое функцией хеширования, может бытьнужное значение, а не контейнер для получения значения.
Мне пришлось недавно собрать одно из них вместе для преобразования текстовых месяцев («январь» и т. д.) в числа месяцев.Вы можете увидеть процесс здесь .
Я упоминаю эту возможность из-за вашего комментария "предопределенная строка".Если ваши ключи ограничены "X" и "Y" (как в вашем примере), и вы используете набор символов с непрерывными {W,X,Y} символами (который даже охватывает EBCDIC и ASCII, хотя не обязательно каждый разрешенный набор эзотерических символовпо ISO) простейшая функция хеширования будет выглядеть так:
char *s = "X";
int val = *s - 'W';
Обратите внимание, что это плохо работает, если вы предоставляете неверные данные.Они идеально подходят для случаев, когда известно, что данные ограничены определенными значениями.Стоимость проверки данных часто может свести на нет экономию, обеспечиваемую предварительно оптимизированной хэш-функцией, подобной этой.