Правила форума
Пожалуйста помогите решить задачку! М е т о д а л ф а в и т н о й и н д е к с а ц и и.
Данный алгоритм применяется для таблиц, содержащих алфавитно-
цифровую информацию, таких, как таблицы символических имен и литералов,
таблицы внешних имен и другие. Идея его заключается в том, что для
сортировки используется первый символ ключа. Строки результирующей
таблицы, начинающиеся с одной и той же буквы, будут объединены в группы.
Кроме результирующей таблицы создается массив входов, количество
элементов которого определяется количеством символов в алфавите. Каждый
элемент массива сопоставляется конкретному символу алфавита, и будет
содержать указатель на номер первой строки группы строк, начинающихся с
данного символа. Если учесть, что символы в алфавите упорядочены, то
преобразование кода символа в номер элемента массива входов выполняется
достаточно просто. Например, если используются только заглавные буквы
латинского алфавита, то количество элементов будет равно 26. Тогда первый
элемент массива будет соответствовать букве A, а последний - букве Z. Для
преобразования можно воспользоваться формулой:
i=ord(CH)-ord('A')+1,
где CH - символ алфавита;
i - номер элемента массива входов;
ord()- функция преобразования символьного формата в числовой.
Сортировка выполняется за один проход исходной таблицы и
складывается из следующих шагов:
- в ключе поиска выделить первый символ и преобразовать его код
в номер элемента массива входов;
- если элемент массива входов пуст(=0), то занести в него
значение указателя на свободную строку в результирующей таблице;
указатель нарастить; а в результирующую строку перенести строку из
исходной таблицы; после чего перейти к следующей строке исходной таблицы;
- если элемент массива входов занят(<>0), то:
1) в результирующей таблице выполнить физическое перемещение
строк на одну позицию, начиная со строки, на которую указывает элемент
массива входов (пусть j), в направлении к концу таблицы;
2) в массиве входов все элементы, значения которых больше j,
нарастить на 1;
3) обрабатываемую строку исходной таблицы перенести в
освободившуюся строку j результирующей таблицы;
4) перейти к следующей строке исходной таблицы.
Алгоритмы поиска наиболее часто используются в системных
программах, и от их эффективности во многом зависит эффективность работы
системной программы. Все алгоритмы поиска можно разделить на 2
класса: алгоритмы, работающие с неупорядоченной и только с упорядоченной
таблицей. К первому классу могут быть отнесены алгоритмы линейного и
случайного поиска. Ко второму - алгоритмы двоичного, вычислением адреса
и с алфавитной индексацией.
Не как не пойму как это выполнить!
Если есть какие то идеи напишите пожалуйста!!
Отсортировать надо массив строк. В строке должно быть по 3-и символа!
Сообщение отредактировано: Sanya01078 -
 Метод алфавитной индексации |
