Информатика и технология программирования


Модульное проектирование - часть 2




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

Пример: разместить в строке слова в порядке убывания. Стандартные решения - найти в строке слово максимальной длины, переписать его в выходную строку, заменяя во входной строке на пробелы, процесс повторять, пока во входной строке есть слова. Такой алгоритм называется сортировкой выбором.

Для начала необходимо определить интерфейс взаимодействия функции поиска слова и оставшейся части программы. Функция возвращает индекс первого символа слова максимальной длины из входного массива или -1, если слов нет.


int find(char c[]) {...}

После чего программа благополучно разделена на две части и их можно разрабатывать в любом порядке. Начнем с основной функции. Для начала необходимо определить ее заголовок и первоначальную формулировку алгоритма:


void copy(char out[], char in[])
{ Пока есть слово во входной строке - переписывать }

Учитывая, что факт наличия очередного слова опреляется функцией find, можно сразу же формализовать алгоритм в виде цикла l:


void copy(char out[], char in[])
{
Выходная строка пуста
while ((m=find(in)) !=-1)
{ Переписать слово, начиная с in[m] в выходную строку }
Завершить выходную строку
}

Для работы с выходной строкой необходимо ввести переменную - индекс текущего символа, после чего две словесные формулировки можно закодировать :


void copy(char out[], char in[])
{
int m,k=0;
while ((m=find(in)) !=-1)
{
Пока не кончилось слово, начиная с in[m],
переписывать символ в out[k++]
Добавить в конце слова пробел
}
out[k]=0;
}

Две последние формулировки также кодируются без проблем (их необходимо поместить в тело цикла уже написанной программы) :


for (;in[m]!=' ' &#38&#38 in[m]!=0; m++)
{ out[k++]=in[m]; in[m]=' '; }
out[k++]=' ';

Функция поиска слова максимальной длины - вариант стандартного алгоритма поиска максимума :


int find(char c[])
{
int maxi=-1,maxl=0,i=0;
while (c[i]!=0)
{
while(c[i]==' ')i++;
if (c[i]!=0)
{
int k;
for (k=0; c[i]!=' ' &#38&#38 c[i]!=0; i++,k++);
if (k &#62 maxl) { maxl=k; maxi=i-k; }
}
}
return maxi;
}




Начало  Назад  Вперед