Ранжирование массива символьных строк по алфавиту

Ранжирование массива символьных строк по алфавиту в принципе реализуется использованием методик сортировки символов в строке.

Математически оптимальный вариант – на первом шаге выполнить сортировку символьных строк по первой их букве. При наличии блоков строк с одинаковыми первыми буквами осуществить сортировку каждого блока по второй букве. При необходимости, полученные новые блоки с двумя одинаковыми начальными буквами ранжируются по третьей букве и т.д.

Оптимальный по количеству шагов выполнения алгоритм достаточно сложно реализуется.

Более простой вариант – последовательное попарное сравнение символов двух соседних строк, от первой буквы и далее.

Каждое сравнение определяет возможность одного из вариантов:

  • буквы одинаковы (коды равны);
  • буква текущей строки ближе к началу алфавита, чем буква последующей строки (код первой меньше кода второй);
  • буква текущей строки дальше от начала алфавита, чем буква последующей строки (код первой больше кода второй).

Первый и второй варианты подтверждают правильное расположение по алфавиту сравниваемых строк. Третий – предписывает поменять строки местами.

Существенное увеличение количества выполняемых операций компенсируется значительным упрощением алгоритма ранжирования строк, то есть простотой его реализации на ЭВМ.

Упорядочение символов в строке по алфавиту рассмотрим на конкретной задаче (9.7) о символьном массиве.

Постановка задачи

Дан не упорядоченный список студенческой группы. Количество студентов не превышает 25, количество символов в каждой строке (фамилия, имя, отчество) не более 30. Требуется отранжировать исходный массив строк по алфавиту.

Формирование математической модели

Исходные данные

СТР(N, М) –массив символьных строк;

N ? 25 – максимальное количество строк массива;

М ? 30 – максимальное количество символов в строке;

n – реальное количество строк массива.

Модель массива СТР(N, М):

с11 с12 с1j с1k – 1-я строка (стр1)
с21 с22 с2j с2l – 2-я строка (стр2)
сi1 сi2 сij сil сim – i-я строка (стрi)
сn1 сn2 сnj сnk – n-я строка (стрn)

i, j – текущие индексы строки массива и символа в строке;

i = i + 1, j = j + 1 – законы изменения индексов;

1 i n, 1 j m – диапазоны изменения индексов элементов.

Характерная особенность массивов символьных строк – длины строк (количество символов каждой) различны, не более максимально возможного значения, заданного в описателе.

Внимание! При составлении расчетных зависимостей под минимальной будем понимать строку с наименьшим кодом.

Расчётные зависимости

стрmin1 = min(стр1, стр2,…, стрi,…, стрn);

стр1 = стрmin1;

стрmin2 = min(стр2,…, стрi,…, стрn);

стр2 = стрmin2;

стрmin i = min(стрi,…, стрn-1, стрn);

стрi = стрmin i;

стрmin n-1 = min(стрn-1,стрn);

стрn-1 = стрmin n-1;

Выбор метода решения

Решение задачи реализуем модифицированным методом «пузырька», описанным ранее:

  • присвоить индексу внешнего цикла его начальное значение (i = 1) – зафиксировать номер i строки стрi, с которой идет сравнение;
  • присвоить индексу внутреннего цикла его начальное значение через внешний (j = i+1);
  • сравнить зафиксированное значение стрi с текущим стрj (стрi > стрj);
  • выполнить переприсваивание стрпр = стрi, стрi = стрj и стрj = стрпр, если условие выполняется;
  • изменить индекс внутреннего цикла по закону j = j + 1;
  • повторять три предыдущих пункта пока j ? n;
  • изменить индекс внешнего цикла по закону i = i + 1;
  • повторять предыдущие пункты, кроме первого, пока i ? n-1;
  • прекратить решение при i > n-1.

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

Рандомно подобранные статьи с сайта:

Самоучитель C++ (25 серия) Visual Studio, Массивы строк char, инициализация массивов строк


Похожие статьи:

admin