авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 | 2 || 4 | 5 |

«Пышкин Е.В. СТРУКТУРНОЕ ПРОЕКТИРОВАНИЕ: ОСНОВАНИЕ И РАЗВИТИЕ МЕТОДОВ С примерами на языке C++ Учебное пособие ...»

-- [ Страница 3 ] --

2. Некто, преобразующий значение из интервала 0..5 к интервалу 1..6 посредством 5 инструкций if и пяти присваиваний.

3. Некто, не использующий ветви else, потому что «они не всегда работают».

4. Некто, никогда не использующий строки переменной длины в PL/1, потому что «они неэффективны».

5. Некто, кто совсем не использует подпрограммы, потому что «они слишком сложны»

[Weinberg, 1988].

В связи с этим С. МакКоннелл предлагает помнить о том, что в случаях из 100 преобразование текста, содержащего goto к тексту без оного, может быть осуществлено без особых усилий. В 9 случаях из преобразование, возможно, потребует некоторых усилий или консультаций с более квалифицированным программистом, но оно, безусловно, должно быть осуществлено. Оставшийся 1%, вероятно, соответствует случаям, когда использование goto уместно, и в целом не нарушает связность программного текста и ясность его восприятия: «если вы в сапогах, вероятно, не стоит обходить к а ж д у ю лужицу».

В целом, можно руководствоваться следующими основными правилами:

Использование goto можно считать оправданным, если это делается для эмуляции управляющих конструкций структурного программирования, не поддерживаемых языком напрямую.

Не используйте goto, если в языке существует встроенная конструкция, обеспечивающая эквивалентный код.

Никогда не используйте goto, передающего управление «назад» (в точку, предшествующую goto), а только «вперед». Код, содержащий goto на предшествующие блоки, обычно не только труднее для восприятия, но и с большей вероятностью содержит ошибки: в некоторой точке A, в общем случае, неизвестно, достигнута она в первый раз в ходе выполнения программы или повторно (см. рис. 3.19).

Если вы – руководитель проекта (или преподаватель), исходите из того, что баталия из-за единственного goto, возможно, не стоит поражения во всей войне: если программист д е й с т в и т е л ь н о о с в е д о м л е н о возможных вариантах решения проблемы (это преподавателю стоит проверить!) и может аргументировать свою позицию, возможно, перед нами как раз один из 1% случаев.

«Хорошо структурированная программа» не обязательно означает «программа без goto». Методически верная функциональная декомпозиция и правильное использование механизмов структурного программирования обычно «автоматически» ведет к программному коду, не требующему goto в подавляющем большинстве случаев. Стремление сфокусировать внимание исключительно на goto не обязательно ведет к получению качественного кода.

В этой точка в общем случае неизвестно, исполнялись ли итерации цикла «Цикл 1»

?

Цикл Заштрихованные участки, возможно, были выполнены Цикл Рис. 3.19. Неоднозначность при использовании goto В заключение следует заметить, что проблема goto имеет явно выраженный текстовый характер. Запутанность кода возникает большей частью в тексте программы, который неадекватно отображает визуальную модель управления действиями. Визуальное программирование во многих случаях решает проблему некорректных переходов и нарушения правил структурного программирования, поскольку можно считать, что визуальные формализмы вообще не содержат каких-либо «правильных» и «неправильных» текстовых конструкций языка.

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

Например, в языке Pascal мультиветвление (обычно называемое оператором выбора) реализовано так, как показано на рис. 3.20.

В языке C++ продолжение исполнения программы после перехода осуществляется в строгом соответствии с фон Неймановским принципом последовательных вычислений. Для выхода за пределы мультиветвления следует дополнительно использовать специальную инструкцию break (рис. 3.21).

Инструкция case языка Pascal условие конст. выраж. конст. выраж.......

конст. выраж. N default Рис. 3.20. Реализация мультиветвления (Pascal) Инструкция switch языков C/C++ условие конст. выраж. break конст. выраж.......

конст. выраж. N default Рис. 3.21. Реализация мультиветвления (язык C) Два простых примера, представленных ниже, иллюстрирует особенности обработки мультиветвления в языках C/C++.

#include stdio.h void main() { int i = 5;

switch( i ) { case 1 :

case 3 : printf( "case 3\n" );

case 5 : printf( "case 5\n" );

case 7 : printf( "case 7\n" );

default: printf( "default\n" );

} printf( "stop\n" );

} При исполнении данной программы будет напечатан следующий текст:

case case default stop Таким образом, последовательно исполняются все инструкции, начиная с ветви мультиветвления, соответствующей текущему значению переменной i. Для исправления ситуации следует использовать инструкцию break:

#include stdio.h void main() { int i = 5;

switch( i ) { case 1 :

case 3 : printf( "case 3\n" );

break;

case 5 : printf( "case 5\n" );

break;

case 7 : printf( "case 7\n" );

break;

default: printf( "default\n" );

break;

} printf( "stop\n" );

} В этом случае программа порождает следующий вывод:

case stop Отметим, что по правилам языка C++, ветвь default не обязана быть последней (хотя чаще всего код организуют именно так), поэтому использование break оправдано и в этой ветви.

Формальный синтаксис мультиветвления C/C++ представлен на рис. 3.22.

Мультиветвление ::= выражение ) switch ( вариант { } вариант ::= константное инструкция :

case выражение инструкция :

default Рис. 3.22. Инструкция switch В большинстве языков при реализации мультиветвления значение условного выражения и значения констант выбора должны иметь порядковый тип. Однако в некоторых языках допускается использование в мультиветвлении более сложных типов. Например, в языке C# допускается разветвление по значению строки.

Реализация программной модели конечного автомата Мультиветвления позволят достаточно наглядно и просто реализовать программную модель конечного автомата. Для конечного автомата, распознающего идентификаторы (см. разд. 3.1.), построение соответствующей программной модели иллюстрирует листинг 3.11:

Листинг 3.11. Конечный автомат, распознающий идентификаторы #include stdio.h #include stdlib.h #include ctype.h /* * Типы входных сигналов автомата * (синтермы литер сканируемого текста) */ enum InputType { ENDFILE, // Конец файла SPACE, // Символ пробельной группы LETTER, // Латинская буква DIGIT, // Десятичная цифра NOALP // Запрещенный символ };

/* * Состояния автомата * (этапы анализа текста) */ enum StateType { S0, // Ожидание первой буквы (начальное состояние) NXTLIT, // Ожидание очередной литеры идентификатора STOP, // Конец текста (завершающее состояние) ERROR // Ошибка (завершающее состояние) };

/* * Тип: литера сканируемого текста */ struct Litera { char value;

// Значение литеры InputType synterm;

// Значение синтерма };

/* * Тип: лексема сканируемого текста */ struct Lexema { char value[ 32 ];

char ix;

char ixLast;

};

/* * GET LITera from input stream * Функция считывания очередного символа из входного потока */ InputType GetLit( FILE *input, Litera& lit ) { lit.value = fgetc( input );

if( lit.value == EOF ) { return lit.synterm = ENDFILE;

} else if( lit.value == ' ' || lit.value == '\n' || lit.value == '\t' ) { return lit.synterm = SPACE;

} else if( isdigit( lit.value ) ) { return lit.synterm = DIGIT;

} else if( isalpha( lit.value ) ) { return lit.synterm = LETTER;

} return lit.synterm = NOALP;

} /* * LEXema: register FIRST litera * Функция регистрации первой литеры в составе лексемы */ void LexFirst( Lexema& lex, const Litera& lit ) { lex.ix = 0;

lex.ixLast = 30;

lex.value[ 0 ] = lit.value;

} /* * LEXema: register NEXT litera * Функция регистрации очередной литеры в составе лексемы */ void LexNext( Lexema& lex, const Litera& lit ) { if( lex.ix != lex.ixLast ) { lex.value[ ++lex.ix ] = lit.value;

} } /* * LEXema: STOP register literas * Функция завершения регистрации литер в составе лексемы */ void LexStop( Lexema& lex ) { lex.value[ ++lex.ix ] = '\0';

} /* * Finite State Machine definition * Определение конечного автомата,распознающего идентификаторы */ void FiniteStateMachine( FILE *input, // Входной поток FILE *output // Выходной поток ) { Litera lit;

// Литера сканируемого текста Lexema ident;

// Идентификатор в сканируемом тексте StateType state = S0;

// Состояние конечного автомата // Цикл работы конечного автомата while( 1 ) { // Считать очередной символ из входного потока InputType synterm = GetLit( input, lit );

// Состояния и переходы в зависимости от // входного символа switch( state ) { case S0 : switch( synterm ) { case SPACE : state = S0;

break;

case ENDFILE : state = STOP;

break;

case LETTER : LexFirst( ident, lit );

state = NXTLIT;

break;

default : state = ERROR;

break;

} break;

case NXTLIT : switch( synterm ) { case SPACE : LexStop( ident );

fprintf( output, "%s\n", ident.value );

state = S0;

break;

case ENDFILE : LexStop( ident );

fprintf( output, "%s\n", ident.value );

state = STOP;

break;

case LETTER :

case DIGIT : LexNext( ident, lit );

state = NXTLIT;

break;

default : state = ERROR;

break;

} break;

case STOP : fprintf( output, "Stopped successfully\n" );

return;

case ERROR : fprintf( output, "Stopped in error state\n" );

return;

} } } Отметим, что, как показано в [Лекарев, 2000-4], продвижение по входной цепочке не является в общем случае обязательным при каждом переходе конечного автомата. Если конечный автомат не осуществляет автоматического чтения при каждом переходе, то такая модель автомата может распознавать язык, не распознаваемый обычным конечным автоматом. Поэтому программная модель позволит обеспечить бльшую общность решения, если операцию GetLit перенести внутрь обработчиков состояний, подчеркивая тем удобство во многих практических случаях реализации считывания из входного потока явным образом.

Соответствующую модификацию кода оставляем для самостоятельного упражнения.

3.3. Функционально-иерархическая декомпозиция Одним из возможных и, вероятно, наиболее естественных решений задачи преобразования кода из предыдущего раздела (см. листинг 3.10), является решение с введением дополнительной функции:

if( StatusOK ) { if( DataIsAvailable ) { ImportantVar = x;

ExtraWork( ImporatantVar );

} } else { ImportantVar = GetValue();

ExtraWork( ImporatantVar );

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

Действительно, иерархическая декомпозиция и иерархическая организация программ является важнейшим универсальным методом разработки ПО (и вообще сложных структур). На уровне кода программы актуальна файловая (модульная) и функциональная (процедурная) декомпозиция. Среди студентов бытует выражение «разбиение программы на функции, блоки, файлы и т.д.», которое, однако, принципиально не верно, так как входит в противоречие с принципами системности и в таком виде не имеет ни малейшего отношения к иерархической функциональной декомпозиции. Получится ли из неважной программы после ее деления на куски хороший проект? Очевидно, нет, ибо целое не сводится к сумме составляющих его частей, а разрозненные части сами по себе не образуют целого. Стоит привести замечательное эссе на эту тему из уникального в своем роде романа-головоломки французского писателя Жоржа Перека [Perec, 1978]:

“l’objet vis – qu’il s’agisse d’un acte perceptif, d’un apprentissage, d’un systme physiologique ou, dans le cas qui nous occupe, d’un puzzle de bois – n’est pas une somme d’lments qu’il faudrait d’abord isoler et analyser, mais un ensemble, c’est--dire une forme, une structure: l’lment ne prexiste pas l’ensemble, il n’est ni plus immdiat, ni plus ancien, ce ne sont pas les lments qui dterminent l’ensemble, mais l’ensemble qui dtermine les lments: la connaissance du tout et de ses lois, de l’ensemble et de sa structure, ne saurait tre dduite de la connaissance spare des parties qui le composent: cela veut dire qu’on peut regarder une pice d’un puzzle pendant trois jours et croire tout savoir de sa configuration et de sa couleur sans avoir le moins du monde avanc:

seule compte la possibilit de relier cette pice d’autres pices, et en ce sens il y a quelque chose de commun entre l’art du puzzle et l’art du go;

seules les pices rassembles prendront un caractre lisible, prendront un sens: considre isolment une pice d’un puzzle ne veut rien dire;

elle est seulement question impossible, dfi opaque;

mais peine a-t-on russi, au terme de plusieurs minutes d’essais et d’erreurs, ou en une demi-seconde prodigieusement inspire, la connecter l’une de ses voisines, que la pice disparat, cesse d’exister en tant que pice...” Georges Perec. “La Vie, mode d’emploi”, prambule Итак, задачи построения иерархии проекта, проблемы определения его файлового и функционального состава образуют неотъемлемые составляющие процесса проектирования. Без грамотно принятых решений "...объект, представленный нашему вниманию, будь то акт восприятия, узнавания, функциональная система [sic! - курсив мой - Е.П.] или в том случае, который нас занимает – картонная мозаика – не образуется суммой элементов, которые требовалось бы сначала изолировать друг от друга, и затем анализировать, но единое целое, то есть некая структура, форма: элемент не предшествует в своем существовании целому, он не опережает целое и не одновременен с ним, не отдельные элементы определяют целое, но целое определяет свой элементный состав: знание о законах целого и о его структуре невозможно было бы вывести из информации о его отдельных частях. Иными словами, можно разглядывать кусочек мозаики в течение трех дней и изучить столь досконально его конфигурацию и его цвета, что добавить что-нибудь к этому знанию будет невозможно до тех пор, пока мы не примем в расчет возможность соединения этого элемента с другими, и в этом смысле есть нечто общее между искусством составления мозаики и искусством го: только вместе собранные части обретут видимый, распознаваемый [досл. lisible – читаемый] смысл, – взятая изолированно частичка не означает ничего, лишь повисший вопрос, смутный намек, но стоит только найти одну из соседних с ней, может быть через долгие минуты проб и ошибок, может быть в долю мгновенья чудесным озарением, как частичка вдруг исчезает, перестает существовать..." – Жорж Перек. Жизнь, способ употребления. Из авторского предисловия (перевод с франц.: Е.П.) уже на стадии формулирования технического задания хороший проект невозможен.

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

Листинг 3.12. Функциональная декомпозиция программной модели конечного автомата #include stdio.h #include stdlib.h #include ctype.h // См. листинг 3. //...

// Прототипы функций обработки состояний конечного автомата StateType Process_S0( const Litera&, Lexema& ident );

StateType Process_NXTLIT( const Litera&, Lexema&, FILE* output );

void Process_STOP( FILE* output );

void Process_ERROR( FILE* output );

/* * Finite State Machine definition * Определение конечного автомата,распознающего идентификаторы */ void FiniteStateMachine( FILE *input, // Входной поток FILE *output // Выходной поток ) { Litera lit;

// Литера сканируемого текста Lexema ident;

// Идентификатор в сканируемом тексте StateType state = S0;

// Состояние коненого автомата // Цикл работы конечного автомата while( 1 ) { // Считать очередной символ из входного потока GetLit( input, lit );

// Состояния и переходы в зависимости от // входного символа switch( state ) { case S0 : state = Process_S0( lit, ident );

break;

case NXTLIT : state = Process_NXTLIT( lit, ident, output );

break;

case STOP : Process_STOP( output );

return;

case ERROR : Process_ERROR( output );

return;

} } } /* * Определения функций обработки состояний конечного автомата */ StateType Process_S0( const Litera& lit, Lexema& ident ) { StateType state;

switch( lit.synterm ) { case SPACE : state = S0;

break;

case ENDFILE : state = STOP;

break;

case LETTER : LexFirst( ident, lit );

state = NXTLIT;

break;

default : state = ERROR;

break;

} return state;

} StateType Process_NXTLIT( const Litera& lit, Lexema& ident, FILE* output ) { StateType state;

switch( lit.synterm ) { case SPACE : LexStop( ident );

fprintf( output, "%s\n", ident.value );

state = S0;

break;

case ENDFILE : LexStop( ident );

fprintf( output, "%s\n", ident.value );

state = STOP;

break;

case LETTER :

case DIGIT : LexNext( ident, lit );

state = NXTLIT;

break;

default : state = ERROR;

break;

} return state;

} void Process_STOP( FILE* output ) { fprintf( output, "Stopped successfully\n" );

} void Process_ERROR( FILE* output ) { fprintf( output, "Stopped in error state\n" );

} В модифицированной структуре функция FiniteStateMachine наглядно определяет логику переходов конечного автомата, а для каждой функции-обработчика состояния через список параметров сформулирована ее зависимость от внешних данных, таким образом, обработчики полностью обособлены.

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

Основные стратегии проектирования: первоначальные сведения С точки зрения направления, в котором ведется разработка проекта, специалисты выделяют несколько основных стратегий проектирования:

«сверху вниз», «снизу вверх», «изнутри к границам», «от границ внутрь».

Вероятно, наиболее распространенной при построении систем является стратегия нисходящей функциональной декомпозиции, при которой первоначально система в о о б р а ж а е т с я в виде объекта, исполняющего все функции, далее происходит выделение подфункций с порождением уровней иерархии [Buhr, 1984] (рис. 3.23).

Рис. 3.23. Нисходящая функциональная декомпозиция Проектирование «сверху вниз» позволяет проектировать высокоуровневые абстракции, основываясь на анализе предметной области, однако повторное использование спроектированных компонентов, как правило, затруднено. Кроме того, в сложном проекте, когда за отдельные части отвечают разные разработчики может возникать дублирование компонентов. При использовании стратегии «снизу вверх» проще создавать базовые обобщенные алгоритмы с их последующим многократным использованием, однако труднее прогнозировать вписываемость этих компонентов в высокоуровневую архитектуру [Coplien, 1999].

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

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

нисходящее проектирование восходящее проектирование Рис. 3.24. Сочетание стратегий проектирования Грамотно построенная структура программных компонентов и данных обеспечивает и дополнительные преимущества, например, уменьшение числа переменных, облегчение их локализации в различных частях программы, упрощение связывания аргументов и параметров функций. «Изучите свойства объектов, с которыми должна работать программа», – указывает Д. Грис, – «чем больше свойств объекта вы знаете, тем у вас больше возможностей создать эффективный алгоритм»

[Gries, 1971].

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

Процедурой называется обособленный именованный блок кода, выполняющий определенные действия, и взаимодействующий с другими функциональными блоками посредством связывания аргументов и параметров.

Функцией называется именованный блок, выполняющий определенные действия, и взаимодействующий с другими функциональными блоками посредством связывания аргументов и параметров, а также формирующий возвращаемое значение (см. пример использования функции sin в разд. 2.1, подраздел «Плавающие типы»).

Большинство языков программирования предоставляют самостоятельные синтаксические средства для определения как процедур, так и функций (Pascal, PL/1, FORTRAN, Ada и др.).

Листинг 3.13 иллюстрирует пример определения процедур и функций на языке Pascal.

Листинг 3.13. Процедуры и функции в языке Pascal { Определение високосности года } { Функция возвращает true, если год високосный, иначе – false } function YearIsLeap( year: integer ) : boolean begin if year mod 4 0 then return false;

if year mod 100 0 then return true;

if year mod 400 0 then return false;

return true end;

{ Процедура проверки корректности календарной даты } procedure CheckDate( day, month, year: integer );

var daysLimit : array[ 1..12 ] of integer = ( 31,29,31,30,31,30, 31,31,30,31,30,31 );

correct : boolean = true;

begin if (month 1) or (month 12) then correct := false else if (day 1) or (day daysLimit[ month ]) then correct := false else if (year1) or (year 5000) then correct := false else if (month=2) and (day=29) and not YearIsLeap( year ) then correct := false;

if correct then writeln( 'Date is correct' ) else writeln( 'Date is incorrect' ) end;

Отметим, что, несмотря на тот факт, что пример с определением того, является ли код високосным, весьма распространен в учебной литературе, довольно часто реализация соответствующей функции оказывается некорректной. Да и вообще – многие люди ошибочно полагают, что високосными являются года, делящиеся нацело на 4, хотя в действительности это не совсем так – см. текст функции YearIsLeap.

В некоторых языках семантика процедур и функций соединена в одной синтаксической конструкции, обычно называемой функцией (C, C++, Java, C#).

Эквивалентные функциональные блоки, написанные на языке C, представлены в листинге 3.14.

Листинг 3.14. Функции C/C++ #include stdio.h /* Определение високосности года */ /* Функция возвращает 1, если год високосный, иначе – 0 */ int YearIsLeap( int year ) { if( year % 4 != 0 ) return 0;

if( year % 100 != 0 ) return 1;

if( year % 400 != 0 ) return 0;

return 1;

} /* Процедура проверки корректности календарной даты */ void CheckDate( int day, int month, int year ) { int daysLimit[ 12 ] = { 31,29,31,30,31,30, 31,31,30,31,30,31 };

int correct = 1;

if( (month 1) || (month 12) ) correct = 0;

else if( (day 1) || (day daysLimit[ month-1 ]) ) correct = 0;

else if( (year1) || (year 5000) ) correct = 0;

else if( (month==2) && (day==29) && (!YearIsLeap( year )) ) correct = 0;

if( correct ) printf( "Date is correct\n" );

else printf( "Date is incorrect\n" );

} Из приведенных примеров видно, что в заголовке функции перечисляются типы аргументов, которые она должна принимать (то же справедливо и для процедур). При вызове функции создается локальная переменная, начальное значение которой определяется значением переданного аргумента. Эта переменная называется параметром функции.

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

Отметим, что иногда параметры процедуры или функции называют формальными параметрами, а аргументы – фактическими параметрами.

Вызов функционального блока и возврат управления Для упрощения изложения будем полагать, что функциональный блок – это именованный блок команд, имеющий в большинстве случаев одну точку входа и одну точку выхода. Заметим, что при этом ряд языков и систем программирования обеспечивает реализацию функциональных модулей, имеющих более одной точки входа (PL/1, L-сеть) и два способа завершения (L-сеть).

Передача управления функции не вызывает никаких проблем. Если ориентироваться на простейшую структуру вычислительного устройства, представленную на рис. 1.21, то достаточно обеспечить занесение в РАСК адреса точки входа в функциональный блок. Сложнее обстоит дело с возвратом управления, то есть с реализацией перехода в точку продолжения основной программы после завершения выполнения функции (рис. 3.25).

Вызывающая функция ?

Вызываемая функция Рис. 3.25. Вызов функции и возврат управления Очевидно, информацию об адресе команды в вызывающей функции, куда требуется вернуть управление, нужно где-то хранить. Использовать для этого какой-либо специальный регистр (по аналогии с РАСК) невозможно, так как функции могут вызывать друг друга (рис. 3.26) и глубина вложенности вызовов может быть достаточно большой. Поэтому необходим иной механизм.

?

?

Рис. 3.26. Вложенные вызовы Упрощенная модель стека Оказывается, наилучшей формой хранения информации о точках возврата управления является стек – специальный раздел оперативной памяти с особой дисциплиной управления. Рассмотрим подробности алгоритма работы стека.

Если представить работу стека с точки зрения внешнего наблюдателя, то стек – это хранилище данных, позволяющее заносить и извлекать данные, причем последнее занесенное значение будет извлечено первым (рис. 3.27).

Говоря формальным языком, стек – это разновидность очереди, работающей в соответствии с протоколом «последним пришел – первым ушел» (Last Input – First Output, LIFO). Наглядной «игрушечной» моделью стека является детская пирамидка.

pu p sh po Рис. 3.27. Работа стека С точки зрения внутренней реализации стек представляет собой совокупность соседних ячеек памяти, причем непосредственный доступ возможен только к одной из них. Про эту ячейку говорят, что она находится на вершине стека (рис. 3.28). Появление термина «вершина стека» (top), вероятнее всего, связано с традицией изображения элементов стека снизу вверх – от элементов, занесенных ранее, к элементам, занесенным позднее.

Top pu sh Top = Top = - Стек содержит Стек содержит Стек пуст 1 элемент (Top-1) элементов Рис. 3.28. Вершина стека Отметим, что в реальных архитектурах стек управляется несколько сложнее, чем описано выше. Некоторые подробности более реалистичной модели управления стеком приложения мы рассмотрим далее в этом разделе.

Если представить стек в форме последовательности элементов, хранящихся в соседних ячейках памяти (то есть в форме массива), то индекс вершины стека Top – это индекс последнего занесенного элемента массива. В начальном состоянии стек пуст, этот факт отражает начальное значение Top = -1 (см. рис. 3.28).

Реалистичная модель работы стека приложения Итак, при вызове функции информация о точке адресе возврата сохраняется в стеке приложения. Но необходимо обеспечить связь функциональных блоков (вызывающего и вызываемого) не только по управлению, но и по данным. Основным элементом механизма, обеспечивающего связывание по данным, являются параметры функции (см. подробности в подразделе «Понятие об аргументах и параметрах», а также разд. 3.5).

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

Вызов функции Кадр стека main f( … );

Локальные данные f Кадр Параметры f для f f Адрес возврата в main Рис. 3.29. Кадр стека Таким образом, в отличие от представленной выше упрощенной модели, участки стека, сопутствующие вызову функционального блока, выделяются так называемыми кадрами стека, содержащими всю необходимую информацию о локальных данных функции и об организации возврата управления. В пределах кадра стека имеется н е п о с р е д с т в е н н ы й доступ к его отдельным элементам. В связи с этим более точно говорить, что вершина стека указывает на кадр стека.

Предположим, что структура кадра стека исчерпывается теми элементами, которые мы описали выше (параметры функции, адрес точки возврата и локальные данные). Кстати, это предположение весьма реалистично – именно такая модель стека поддерживается языком FORTRAN.

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

f вызывает g Кадры стека f Локальные данные g Кадр Параметры g g( … );

для g Адрес возврата в f Локальные данные f g Кадр Параметры f для f Адрес возврата в main g возвращает Кадры стека управление f Локальные данные f g Кадр Параметры f для f Адрес возврата в main Рис. 3.30. Вызовы функций: кадры стека К сожалению, для большинства современных языков такой подход не работает, поскольку в общем случае память, занимаемая параметрами функции, может зависеть от значения передаваемых аргументов. Это означает, что в общем случае не просто понять, где именно в памяти начался кадр стека. Следовательно, эту информацию (фактически, речь идет о предшествующем значении вершины стека) тоже нужно сохранить.

Соответствующий элемент кадра называют динамической связью [Sebesta, 2002]. Исправленная картина вызова функции представлена на рис. 3.31.

Теперь удаление кадра стека по завершении работы функции, не вызывает проблем, поскольку информация о прежнем значении вершины стека хранится в явном виде. Таким образом, обеспечивается не только переход в точку продолжения в пределах вызвавшей функции, но и восстановление среды локальных данных этой функции.

f вызывает g Кадры стека f Локальные данные g Параметры g Кадр g( … );

для g Динамическая связь Адрес возврата в f g Локальные данные f Параметры f Кадр для f Динамическая связь Адрес возврата в main Рис. 3.31. Динамическая связь Справедливости ради следует сказать, что и эта модифицированная модель неполна, поскольку проблема заключается в том, что в пределах функционального модуля могут использоваться не только локальные переменные самог модуля, но и нелокальные объекты. Такими объектами данных могут быть переменные, размещенные во внешних функциональных блоках, если язык поддерживает вложение процедур и функций (например, язык Pascal). Поскольку эти объекты данных совсем не обязательно располагаются в соседнем кадре стека, требуется явно хранить информацию о местоположении кадра стека, хранящего соответствующие переменные. Такой элемент кадра стека обычно называют статической связью (рис. 3.32).

f и g - процедуры, вложенные в proc Локальные данные g Параметры g Кадр для g Статическая связь Динамическая связь Адрес возврата в f Локальные данные f Параметры f Кадр Статическая связь для f Динамическая связь Адрес возврата в proc Кадр для proc Рис. 3.32. Статическая связь Для языков, не поддерживающих вложения функций (например, C и C++), возможны только ссылки на внешние глобальные объекты.

Использование таких переменных может быть реализовано значительно проще за счет помещения их вслед за локальными переменными кадра стека.

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

Подробности применительно к архитектуре Intel см., например, в [Robbins, 2000].

3.4. Области видимости и классы памяти В связи с организацией управления данными в функционально ориентированной программе важнейшее значение имеюn понятия области видимости и класса памяти программных объектов.

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

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

В процедурной программе можно выделить следующие стандартные области видимости (см. рис. 3.33):

Глобальная область видимости – область видимости, в которой определяются программные объекты, доступ к которым возможен из любой точки программы.

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

Область видимости в рамках пространства имен (поддерживается не всеми процедурными языками) - область видимости, в которой определяются программные объекты, доступ к которым возможен в пределах явно объявленного пространства имен (пространство имен может содержать объекты, определенные в разных модулях).

Область видимости функционального блока – область видимости, в которой определяются программные объекты, доступ к которым возможен только в пределах процедуры или функции.

Область видимости блока кода – область видимости, ограниченная участком кода, обозначенным специальными ограничителями (например, парой фигурных скобок в C++, или парой begin..end в Паскале). В некоторых источниках (см., например, [Sebesta, 2002]) такая область видимости называется статической, однако мы не будем использовать этот термин в связи с его многократным использованием применительно к описанию классов памяти и моделей связывания.

Область видимости прототипа функции – область видимости параметра функции, ограниченная прототипом функции (см. разд. 2.1 и 3.3).

Глобальная область Область видимости Пространство имен видимости модуля Область видимости Область видимости функционального блока блока Рис. 3.33. Области видимости Использование различных областей видимости (исключая пространства имен) иллюстрирует листинг 3.15.

Листинг 3.15. Области действия и классы памяти // Модуль main.cpp #include stdlib.h // Для exit() #include stdio.h // Для fopen() int count = 0;

// Переменная count в глобальной области видимости:

// доступна во всех модулях проекта static FILE* fin;

// Переменная fin в области видимости модуля // main.cpp: доступна всем функциям модуля // Протитипы функций int InputValue( int* pValue );

// Область видимости pValue // ограничена прототипом int ProcessValue( int );

int Output( int, int );

void Error( FILE* );

void main() { int a;

// Начало области видимости переменной a while( InputValue( &a ) ) { int b;

// Начало области видимости переменной b;

count++;

b = ProcessValue( a );

int check = Output( a, b );

// Начало области видимости // переменной check if( !check ) { FILE *fError;

// Начало области видимости // переменной fError fError = fopen( "error.log", "at" );

if( fError == NULL ) { printf( "Aborted at iteration %d. " "No log file created\n", count );

exit( 1 );

} Error( fError );

fclose( fError );

} // Конец области видимости переменной fError } // Конец области видимости перемернных b и check printf( "%d iterations are successfully completed\n", count );

} // Конец области видимости переменных a // Функция считывания исходных данных int InputValue( int *pValue ) // Начало области видимости { // переменной pValue int retScan;

// Начало области видимости переменной retScan // В этой функции доступны:

// count – глобальная переменная // fin - глобальная статическая переменная // pValue – локальная переменная // retScan – локальная переменная retScan = fscanf( fin, "%d", pValue );

//...

} // Конец области видимости переменных pValue и retScan // Конец модуля main.cpp: конец области видимости переменной fin // Модуль Error.cpp extern int count;

// Глобальная переменная count доступна в // модуле Error.cpp void Error( FILE *fError ) // Начало области видимости { // переменной fError // В этой функции доступны:

// count – глобальная переменная // fError – локальная переменная fprintf( fError, "Error at iteration %d\n", count );

} // Конец модуля Error.cpp //...

Заметим, что глобальные переменные C++ доступны даже в том случае, когда в некоторой локальной области видимости определяется одноименная переменная. Для обращения к глобальной переменной в этом случае используется операция явного разрешения области видимости:

int count;

// Глобальная переменная: какой-то "всеобщий" счетчик void f() { int count = 0;

// Локальная переменная: доступна только в f // Обращение к локальному счетчику count++;

// Обращение к глобальному счетчику ::count++;

} Основной принцип, который должен быть уяснен студентами, заключается в том, что локальные объекты данных недоступны из внешних по отношению к ним областей видимости:

объект, объявленный в области видимости модуля, недоступен в глобальной области видимости;

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

объект, объявленный в области видимости блока кода, недоступен в во внешних блоках кода.

Наоборот, объект, объявленный в блоке кода, доступен во вложенных в него блоках кода (за исключением случая объявления во вложенном блоке объекта с таким же именем, если оно допускается правилами языка). Если язык допускает объявление во вложенном блоке переменной, имя которой совпадает с переменной в охватывающем блоке, то действует принцип сокрытия имен:

#include stdio.h void f() { int a = 10;

{ int a = 20;

// Эта переменная a не имеет ничего общего // с одноименной переменной из охватывающего // блока: данное определение СКРЫВАЕТ // переменную из вмещающего блока printf( "a=%d\n", a );

// Будет напечатано: a= //...

} // Здесь заканчивается область видимости "второй" a // Здесь продолжается действие a, определенной в начале функции printf( "a=%d\n", a );

// Будет напечатано: a= } Некоторые языки (например, Java) не допускают подобных коллизий (контролируется компилятором).

Принцип локализации обеспечивает независимость функциональных блоков друг от друга. Графически области действия имен могут быть наглядно представлены с использованием диаграмм Нэсси-Шнейдермана (рис. 3.34). С точки зрения области видимости, горизонтальные и вертикальные линии можно считать прозрачными в одном направлении (справа налево и снизу вверх – объекты данных «видны» во вложенных блоках) и непрозрачными – в другом (соответственно, слева направо и сверху вниз – локальные объекты не видны снаружи).

f1(() void f1() Здесь доступно { только a a= int a = 5;

i= Здесь доступны a и i for( int i = 1;

i i 10;

i++ ) { Здесь доступны a, i j = ++a;

int j = ++a;

иj } a = 5;

} i++ Здесь доступны a и i a= Здесь доступны a и i f2() void f2() Здесь доступно { только a a= int a = 5;

i= Здесь доступны a и i for( int i = 1;

i i 10;

i++ ) Здесь доступны a и { «внутренняя» i, i = ++a;

int i = ++a;

i из охватывающего } блока скрыта!

a = 5;

} i++ Здесь доступны a и i a= Здесь доступны a и i Рис. 3.34. Области видимости блоков Диаграмма в нижней части рис. 3.34 иллюстрирует одну из особенностей языков C/C++, зачастую недопонимаемую студентами. Если управляющая переменная цикла определяется в заголовке цикла, это не означает, что она определена в области видимости тела цикла. На самом деле она определена в охватывающем блоке, но, разумеется, как правило, доступна в теле цикла. Исключение составляет случай, когда в теле цикла объявлена одноименная переменная (такого кода следует избегать;

кстати, компилятор Visual C++.NET не поддерживает такое переопределение!).

Спецификаторы static и extern обсуждаются в следующем разделе.

Классы памяти и время жизни программных объектов Понятие области видимости тесно связано с понятием класса памяти, определяющим, как программный объект размещается в памяти и какой протокол управления памятью используется при работе с этим объектом.

Полная форма описания переменной помимо типа и имени переменной может включать также информацию о классе памяти, например:

static FILE* fin;

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

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

Наличие автоматического класса памяти очень удобно, поскольку, с одной стороны, избавляет программиста от специального контроля над такими переменными, с другой стороны, обеспечивает рациональное расходование памяти для локальных объектов: они находятся в памяти только до тех пор, пока доступны в своей области видимости. Таким образом, время жизни (время нахождения в памяти) автоматических переменных однозначно определяется их областью видимости. Автоматические переменные хранятся в стеке приложения. Отметим, что автоматическое управление памятью, занимаемой локальными переменными, позволяет писать рекурсивные функции, то есть функции, вызывающие сами себя (см. разд. 3.6).

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

Поэтому такие объекты хранятся в специальном разделе памяти, выделяемой приложению в самом начале работы. Эта память обычно называется статической. Отсюда – и название класса памяти подобных программных объектов – статический. Доступ к статическим локальным переменным имеется только в том блоке, в котором они определены, однако время жизни таких переменных совпадает со временем выполнения приложения. В языках C и C++ статический класс памяти для локальных переменных определяется спецификатором static. В отличие от автоматических переменных, инициализация статических данных гарантирована: если программист не указал другого значения, статическая переменная инициализируется нулем.

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

Использование локальных статических переменных иллюстрирует листинг 3.16, содержащий вариант реализации функции Error из предыдущего примера, подсчитывающей процент ошибочных итераций.

Листинг 3.16. Локальные статические переменные // Модуль Error.cpp extern int count;

// Глобальная переменная count доступна в // модуле Error.cpp void Error( FILE *fError ) // Начало области видимости { // переменной fError static int failed = 0;

// Начало области видимости // локальной статическая переменной // failed // В этой функции доступны:

// count – глобальная переменная // fError – локальная переменная // failed – локальная статическая переменная failed++;

fprintf( fError, "Error at iteration %d\n", count );

fprintf( fError, "Percentage of failed iterations: %.2f\n", (float) failed /count * 100 );

} // Конец области видимости переменной failed // Конец модуля Error.cpp Следует обратить внимание на то, что запись static int failed = 0;

является определением и инициализацией статической переменной. Инициализация переменной осуществляется в самом начале исполнения программы (еще до начала работы функции main). Таким образом, переменная failed существует в памяти в течение всего времени исполнения программы, однако доступна эта переменная только в пределах функции Error.

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

Для доступа к глобальным программным объектам обычно вводится класс памяти «внешний», наименование которого указывает на возможность обращения к этим объектам из внешних модулей (см. объявление переменной count в предыдущем примере).

Если размещение программных объектов в памяти происходит явным образом посредством использования встроенных операций языка (например, операций new и delete в C++) или специальных функций (например, функций malloc и free библиотеки C), то такие объекты называются явными динамическими объектами [Sebesta, 2002]. Явные динамические объекты представляют собой безымянные ячейки памяти. Обращение к таким объектам происходит посредством указателей (например, в C++) или ссылок (например, в Java).

Динамические программные объекты размещаются в специальном сегменте памяти, называемом динамической памятью, или кучей (heap).

Размер динамической памяти, отводимой приложению, может варьироваться довольно в широких пределах (см., например, информацию в [Давыдов, 2003]).

Конкретные языки программирования могут поддерживать и другие классы памяти, определяемые особенностями архитектуры языка, например, регистровый класс памяти в C/C++, пакетный класс памяти в языке Ada, неявные динамические переменные в APL и ALGOL 68 и т. п.

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

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

// Модуль Max.cpp double max1( double arg1, double arg2 ) { if( arg1 arg2 ) return arg1;

return arg2;

} Листинг 3.17 иллюстрирует использование этой функции для определения максимального из двух значений, задаваемых пользователем программы в виде аргументов командной строки.

Листинг 3.17. Вызов функции: связывание по значению // Модуль Main.cpp #include stdio.h #include stdlib.h double max1( double, double );

void main( int argc, char *argv[] ) { if( argc 3 ) { printf( "Not enough command line parameters\n" );

exit( 1 );

} double a = atof( argv[1] );

double b = atof( argv[2] );

double result;

result = max1( a, b );

printf( "Max( %le, %le ) = %le\n", a, b, result );

exit( 0 );

} При передаче управления функции max1 значение переменной a копируется в память, выделяемую в стеке приложения для локальной переменной arg1, являющейся параметром функции max1 (рис. 3.35).

Аналогично, значение переменной b копируется в память, выделяемую в стеке приложения для локальной переменной-параметра arg2.

main max a arg копирование b arg result double Рис. 3.35. Связывание по значению Такой механизм связывания называется связыванием по значению.

Любые возможные изменения параметров arg1 и arg2 не оказывают влияния на аргументы a и b, поскольку различны их области видимости. Из пределов функции max1 нельзя обратиться к локальным переменным, объявленных в другой функции (в данном случае – в функции main).

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


В этом случае проектируемая функция должна, фактически, сформировать два результата:

ответ на вопрос, есть ли среди двух значений наибольшее;

если есть, то какое оно.

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

main max a arg b arg acr acuracy pRes result int возвращаемое значение (0 или 1) Рис. 3.36. Связывание с косвенной адресацией Наиболее распространенное в практике программирования на языке C решение заключается в том, что функции передается в качестве аргумента адрес той ячейки памяти, в которую следует записать результат вычислений.

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

Листинг 3.18. Определение и вызов функции: связывание с косвенной адресацией // Модуль Max.cpp #include math.h // Функция возвращает 1, если наибольшее значение имеется // 0, если исходные аргументы равны int max2( double arg1, // Исходный параметр # double arg2, // Исходный параметр # double acr, // Точность вычислений double *pRes // Адрес хранения результата вычислений ) { if( fabs( arg1 – arg2 ) fabs( acr ) ) return 0;

if( arg1 arg2 ) *pRes = arg1;

else *pRes = arg2;

return 1;

} // Модуль Main.cpp #include stdio.h #include stdlib.h int max2( double, double, double, double* );

void main( int argc, char *argv[] ) { if( argc 3 ) { printf( "Not enough command line parameters\n" );

exit( 1 );

} double a = atof( argv[1] );

double b = atof( argv[2] );

double accuracy = 1e-9;

double result;

if( max2( a, b, accuracy, &result ) ) { printf( "Max( %le, %le ) = %le\n", a, b, result );

} else { printf( "Values %le and %le are equal with accuracy %le\n", a, b, accuracy );

} exit( 0 );

} Как явствует из листинга 3.18, при вызове функции max2 начальным значением параметра pRes становится адрес переменной result, определенной в функции main (см. рис. 3.36).

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

Если результатом работы функции должно быть адресное значение, то связываемый параметр должен иметь тип «указатель на указатель», например, в случае формирования значения файловой переменной (листинг 3.19):

Листинг 3.19. Использование указателя на указатель #include stdio.h #include stdlib.h #include string.h // Функция открытия файла и обработки ошибки bool OpenFile( FILE **pFile, char *filename, char *mode ) { *pFile = fopen( filename, mode );

if( *pFile == NULL ) { printf( "Can’t open file \"%s\" ", filename );

if ( strchr( mode, 'r' ) ) printf( "for reading\n" );

else if( strchr( mode, 'w' ) ) printf( "for writing\n" );

else if( strchr( mode, 'a' ) ) printf( "for appending\n" );

else printf( "\n" );

return false;

} return true;

} // Пример внешней функции void main() { FILE *fin;

if( !OpenFile( &fin, "input.txt", "rt" ) ) exit( 1 );

//...

} В данном случае, поскольку переменная fin является указателем, то параметр, способный хранить адрес этого указателя, должен иметь тип «указатель на указатель на FILE», то есть тип FILE**.

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

Альтернативой является использование ссылочных параметров (листинг 3.20).

Листинг 3.20. Определение и вызов функции: связывание по ссылке // Модуль Max.cpp #include math.h // Функция возвращает 1, если наибольшее значение имеется // 0, если исходные аргументы равны int max3( double arg1, // Исходный параметр # double arg2, // Исходный параметр # double acr, // Точность вычислений double& refRes // Ссылка на переменную, хранящую // результат вычислений ) { if( fabs( arg1 – arg2 ) fabs( acr ) ) return 0;

if( arg1 arg2 ) refRes = arg1;

else refRes = arg2;

return 1;

} // Модуль Main.cpp #include stdio.h #include stdlib.h int max3( double, double, double, double& );

void main( int argc, char *argv[] ) { if( argc 3 ) { printf( "Not enough command line parameters\n" );

exit( 1 );

} double a = atof( argv[1] );

double b = atof( argv[2] );

double accuracy = 1e-9;

double result;

if( max3( a, b, accuracy, result ) ) { printf( "Max( %le, %le ) = %le\n", a, b, result );

} else { printf( "Values %le and %le are equal with accuracy %le\n", a, b, accuracy );

} exit( 0 );

} Код функции max3, действительно, теперь выглядит проще.

Переменная refRes предоставляет способ обращения к аргументу, непосредственно не доступному из пределов max3 (рис. 3.37).

main max a arg b arg acr acuracy refRes result int возвращаемое значение (0 или 1) Рис. 3.37. Связывание по ссылке Существенным недостатком связывания по ссылке является тот факт, что в точке вызова никак не видно, что переменная result может измениться в результате работы функции max3.

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

Листинг 3.21. Константная ссылка на структурный объект typedef struct { int day;

int month;

int year;

} DateType;

bool DateIsCorrect( const DateType& date ) { int daysLimit[ 12 ] = { 31,29,31,30,31,30, 31,31,30,31,30,31 };

if( (date.month 1) || (date.month 12) ) return false;

if( (date.day 1) || (date.day daysLimit[ date.month-1 ]) ) return false;

if( (date.year1) || (date.year 5000) ) return false;

if( (date.month==2) && (date.day==29) && (!YearIsLeap( date.year )) ) return false;

;

return true;

} Определение функции YearIsLeap см. в разд. 3.3 (листинг 3.14).

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

Листинг 3.22 иллюстрирует основные идеи реализации взаимодействия функций через общий интерфейс (см. также рис. 3.38).

Листинг 3.22. Взаимодействие функций через общие интерфейсы // Файл InterType.h // Определение типов интерфейсов #ifndef _InterType_h_ #define _InterType_h_ enum InputType { ENDFILE, // Конец файла SPACE, // Символ пробельной группы LETTER, // Латинская буква DIGIT, // Десятичная цифра NOALP // Запрещенный символ };

/* * Тип интерфейса данных: литера сканируемого текста */ struct Litera { char value;

// Значение литеры InputType synterm;

// Значение синтерма };

/* * Тип интерфейса: лексема сканируемого текста */ struct Lexema { char value[ 32 ];

char ix;

char ixLast;

};

#endif // Файл Litera.h // Заголовочный файл к модулю считывания литер #ifndef _Litera_h_ #define _Litera_h_ #include stdio.h #include "InterType.h" // Прототип функции считывания литеры InputType GetLit( FILE * );

#endif // Файл Lexema.h // Заголовочный файл к модулю конструирования лексем #ifndef _Lexema_h_ #define _Lexema_h_ #include "InterType.h" // Прототипы функций конструирования лексемы void LexNext();

void LexStop();

void LexFirst();

#endif // Файл InterAll.cpp // Определение интерфейсов данных #include "InterType.h" // Определение интерфейса данных "Литера сканируемого текста" Litera litera;

// Определение интерфейса данных "Лексема сканируемого текста" Lexema lexema;

// Файл Litera.cpp // Модуль считывания литер #include stdio.h #include ctype.h #include "InterType.h" #include "Litera.h" extern Litera litera;

// Использование внешнего интерфейса // "Литера сканируемого текста" /* * GET LITera from input stream * Функция считывания очередного символа из входного потока */ InputType GetLit( FILE *input ) { litera.value = fgetc( input );

if( litera.value == EOF ) { return litera.synterm = ENDFILE;

} else if( litera.value == ' ' || litera.value == '\n' || litera.value == '\t' ) { return litera.synterm = SPACE;

} else if( isdigit( litera.value ) ) { return litera.synterm = DIGIT;

} else if( isalpha( litera.value ) ) { return litera.synterm = LETTER;

} return litera.synterm = NOALP;

} // Файл Lexema.cpp // Модуль конструирования лексем входного текста #include stdio.h #include "InterType.h" #include "Lexema.h" extern Litera litera;

// Использование внешнего интерфейса // "Литера сканируемого текста" extern Lexema lexema;

// Использование внешнего интерфейса // "Лексема сканируемого текста" /* * LEXema: register FIRST litera * Функция регистрации первой литеры в составе лексемы */ void LexFirst() { lexema.ix = 0;

lexema.ixLast = 30;


lexema.value[ 0 ] = litera.value;

} /* * LEXema: register NEXT litera * Функция регистрации очередной литеры в составе лексемы */ void LexNext() { if( lexema.ix != lexema.ixLast ) { lexema.value[ ++lexema.ix ] = litera.value;

} } /* * LEXema: STOP register literas * Функция завершения регистрации литер в составе лексемы */ void LexStop() { lexema.value[ ++lexema.ix ] = '\0';

} // Файл FSM.cpp // Реализация конечного автомата, распознающего идентификаторы #include stdio.h #include "InterType.h" #include "Litera.h" #include "Lexema.h" extern Litera litera;

// Использование внешнего интерфейса // "Литера сканируемого текста" extern Lexema lexema;

// Использование внешнего интерфейса // "Лексема сканируемого текста" enum StateType { S0, NXTLIT, STOP, ERROR };

// Прототипы функций обработки состояний конечного автомата StateType Process_S0();

StateType Process_NXTLIT( FILE * );

void Process_STOP( FILE * );

void Process_ERROR( FILE * );

/* * Finite State Machine definition * Определение конечного автомата,распознающего идентификаторы */ void FiniteStateMachine( FILE *input, // Входной поток FILE *output // Выходной поток ) { StateType state = S0;

// Состояние конечного автомата // Цикл работы конечного автомата while( 1 ) { // Считать очередной символ из входного потока GetLit( input );

// Состояния и переходы в зависимости от // входного символа switch( state ) { case S0 : state = Process_S0();

break;

case NXTLIT : state = Process_NXTLIT( output );

break;

case STOP : Process_STOP( output );

return;

case ERROR : Process_ERROR( output );

return;

} } } /* * Определения функций обработки состояний конечного автомата */ StateType Process_S0() { StateType state;

switch( litera.synterm ) { case SPACE : state = S0;

break;

case ENDFILE : state = STOP;

break;

case LETTER : LexFirst();

state = NXTLIT;

break;

default : state = ERROR;

break;

} return state;

} StateType Process_NXTLIT( FILE * output ) { StateType state;

switch( litera.synterm ) { case SPACE : LexStop();

fprintf( output, "%s\n", lexema.value );

state = S0;

break;

case ENDFILE : LexStop();

fprintf( output, "%s\n", lexema.value );

state = STOP;

break;

case LETTER :

case DIGIT : LexNext();

state = NXTLIT;

break;

default : state = ERROR;

break;

} return state;

} void Process_STOP( FILE * output ) { fprintf( output, "Stopped successfully\n" );

} void Process_ERROR( FILE * output ) { fprintf( output, "Stopped in error state\n" );

} Использование связывания через общий интерфейс позволяет уменьшить длину списков параметров функций, однако предъявляет повышенные требования к проектным решениям на уровне модульной структуры.

InterAll.cpp litera lexema Litera.cpp GetLit Lexema.cpp LexFirst LexNext LexStop FSM.cpp FiniteStateMachine Prcoess_S Process_NXTLIT Рис. 3.38. Связывание через общие интерфейсы Взаимодействие функций, реализованное подобным образом, иногда называют связыванием через статический интерфейс, имея в виду жесткую привязку интерфейса данных к программному модулю. Основным недостатком связывания через статический интерфейс является тот факт, что все функции модуля имеют доступ к данным интерфейса. Если требуется реализовать более строгую модель, можно ввести явные операции подключения к интерфейсу данных (link) и отключения от интерфейса (unlink). В C++ такой механизм может быть реализован посредством использования указателей, привязываемых к структурному объекту присваиванием значением адреса интерфейса данных и «отвязыванием»

путем присваивания нуля. При этом доступ может ограничиваться только операциями чтения (если определен константный указатель):

// Определение операций доступа к интерфейсу #define LINK( access, name ) access = &(name) #define UNLINK( access ) access = NULL extern TLitera litera;

// Внешний интерфейс данных const TLitera *acsLitera;

// Доступ к внешнему интерфейсу void SomeFunction() { //...

LINK( acsLitera, litera );

// Здесь можно использовать интерфейс litera...

//...

UNLINK( acsLitera );

// Теперь доступа к интерфейсу litera нет } Таким образом можно реализовать динамическое подключение к интерфейсу. Наравне со статическими интерфейсами, динамические интерфейсы являются основополагающим механизмом связывания в L-сети (см. гл. 7).

Модель на основе динамических интерфейсов имеет некоторое сходство и с моделью запроса и освобождения интерфейса при взаимодействии компонентов COM (см., например, [Пышкин, 2005]).

3.6. Функции и управление исполнением программы В ряде случаев модели, основывающейся на чисто древовидной иерархии функций, когда функции верхних уровней вызывают функции нижних уровней, оказывается недостаточно для выражения управляющих связей между функциональными блоками. Наиболее сложными «нарушениями» чисто иерархической структуры являются функции обратного вызова и рекурсивные функции, которые в данном разделе мы и рассмотрим несколько подробнее.

Механизм обратного вызова Функция обратного вызова (callback function) – это функция, вызываемая не по имени, а с использованием указателя на функцию, хранящего адрес местоположения функции (рис. 3.39).

ptrFun тип функции должны соответствовать типу указателя на функцию...

Рис. 3.39. Функции обратного вызова Классическим примером алгоритма, использующего функцию обратного вызова, является алгоритм сортировки. В [Пышкин, 2005] приведен пример реализации простейшего алгоритма сортировки простыми обменами таким образом, чтобы посредством использования этой функции можно было сортировать данные произвольных типов (листинг 3.23):

Листинг 3.23. Функции обратного вызова // Определение типа функции, сравнивающей два значения // пользовательского типа typedef int (*CompareFunctionType)( const void* pArg1, const void* pArg2 );

// Функция должна возвращать:

// отрицательное значение, // если значение *pArg1 меньше значения *pArg2;

// положительное значение, // если значение *pArg1 больше значения *pArg2;

// 0, если значения *pArg1 и *pArg2 равны.

// Обобщенная реализация функции сортировки простыми обменами void BubbleSortGeneric( void *begin, // Адрес начала сортируемого массива // (любой указатель может быть присвоен // указателю на void) int n, // Число элементов сортируемого массива int elemSize,// Размер одного элемента в байтах CompareFunctionType compare ) // Указатель на функцию сравнения { // Преобразование указателя на начало массива // к типу char* // NB! Необходимо, так как для указателя на void // не разрешены арифметические операции char *base = static_cast char * ( begin );

for( int i = 1;

i n;

i++ ) { for( int j = n-1;

j=i;

j-- ) { char *basej = base+j*elemSize;

// base[ j ] char *basejmin1 = base+(j-1)*elemSize;

// base[ j-1 ] if( compare( basej, basejmin1 ) 0 ) { // Меняем местами base[ j ] и base[ j-1 ] // (переставляем байты) for( int curByte = 0;

curByte elemSize;

curByte++ ) { char byteCopy = basej[ curByte ];

basej[ curByte ] = basejmin1[ curByte ];

basejmin1[ curByte ] = byteCopy;

} } } } } Как явствует из приведенного текста программы, параметр compare функции BubbleSortGeneric является указателем на функцию, то есть принимает в качестве аргумента адрес функции, определяющей семантику сравнения двух элементов пользовательского типа (рис. 3.40).

main BubbleSort size array size begin n elemSize compare CompareInt CompareFunctionType Рис. 3.40. Использование функции обратного вызова в реализации обобщенного алгоритма сортировки Например, для сортировки целых чисел нужно определить функцию сравнения, список параметров и возвращаемое значение которой в точности соответствует типу CompareFunctionType, например:

int CompareInt( const void* px, const void* py ) { int difference = *((const int*) px) - *((const int*) py);

return difference;

} Тогда вызов функции BubbleSortGeneric для сортировки некоторого массива array, содержащего size элементов целого типа, будет выглядеть следующим образом:

BubbleSortGeneric( array, size, sizeof( int ), CompareInt );

Для сортировки массива, состоящего из элементов другого типа, следует определить соответствующий э т о м у типу вариант функции сравнения. Совместную работу функций BubbleSort и CompareInt иллюстрирует рис. 3.41.

BubbleSort begin n size j-1 j 0 1 size- elemSize compare base basejmin basej CompareInt px py Рис. 3.41. Обобщенная сортировка простыми обменами Отметим, что подобным образом реализована функция сортировки qsort в стандартной библиотеке C/C++.

Функции обратного вызова широко применяются при реализации привязки событий к их обработчикам в приложениях, ориентированных на события. Соответствующий материал, анализ ограничений, присущих функциям обратного вызова, и путей преодоления этих ограничений, читатель найдет в учебном пособии [Пышкин, 2005].

Рекурсия Для небольшого числа задач рекурсия позволяет получить компактное элегантное решений. Для несколько большего числа задач рекурсия позволяет получить компактное и элегантное, но трудное для понимания решение. Для большинства задач использование рекурсии ведет к громоздкому, сложному коду – в этих случаях итеративное решение обычно является более понятным Стив МакКоннелл Многие понятия, используемые в математике, лингвистике, философии являются рекурсивными по своей природе. Это означает, что для определения понятия используется само это понятие. Классическим примером является определение факториала: 0! :: =1;

n! ::= n*(n-1)!

Рекурсивная функция – эта такая функция, которая прямо или опосредованно вызывает сама себя. Пример функции, непосредственно вызывающей саму себя, мы рассмотрим в данном разделе. Пример взаимно рекурсивных функциональных модулей читатель найдет в гл. 8 при рассмотрении задачи синтаксического анализа.

Обход лабиринта: решение и анализ Одним из классических примеров рекурсивного алгоритма является решение задачи обхода лабиринта (листинг 3.24).

Листинг 3.24. Простой алгоритм обхода лабиринта (псевдокод) // Необходимые типы:

// // MAZE_TYPE – тип-лабиринт // MAZE_POINT – тип-координата позиции в лабиринте // MAZE_PATH – путь через лабиринт MAZE_TYPE maze;

// Определение лабиринта MAZE_PATH path;

// Путь через лабиринт // (занесение-извлечение координат по // правилам стека) // Рекурсивный алгоритм поиска пути bool FindMazePath( MAZE_TYPE& maze, MAZE_POINT& position ) { MAZE_POINT attempt;

// Попытки движения в лабиринте // (вправо, влево, вверх, вниз) // Проверяем, не посещали ли раньше if( AlreadyTried( maze, position ) ) return false;

// Проверяем, не выход ли это if( PositionIsExit( maze, position ) ) { PushToPath( path, position );

return true;

} MarkAsTried( maze, position );

// Отметить позицию как // посещенную PushToPath( path, position );

// Втолкнуть в стек // Совершаем попытки движения и рекурсивно // вызываем поиск пути из новой позиции if( MoveLeft( maze, position, attempt ) ) { if( FindMazePath( maze, attempt ) ) return true;

} if( MoveRight ( maze, position, attempt ) ) { if( FindMazePath( maze, attempt ) ) return true;

} if( MoveUp( maze, position, attempt ) ) { if( FindMazePath( maze, attempt ) ) return true;

} if( MoveDown ( maze, position, attempt ) ) { if( FindMazePath( maze, attempt ) ) return true;

} // Здесь: ни одна попытка не увенчалась успехом, // следовательно, из этой позиции пути нет PopFromPath( path );

// Исключить из стека return false;

} В процессе поиска пути функция FindMazePath рекурсивно вызывает сама себя до тех пор, пока не будет выполнено одно из условий – выход из лабиринта обнаружен или рассмотрены все возможные пути.

Наличие рекурсивных вызовов приводит к тому, что одновременно выполняются несколько экземпляров функции FindMazePath, имеющих доступ к различным кадрам стека приложения. Рассмотрим организацию рекурсивных вызовов на примере обхода простого лабиринта, изображенного на рис. 3.42. Пунктирной линией изображены попытки движения по лабиринту, осуществляемые в ходе работы алгоритма.

Сплошная линия соответствует обнаруженному пути, сохраняемому в служебном стеке path.

0 1 2 Выход из лабиринта 0 (2,0) Начальная точка (2,4) Рис. 3.42. Поиск пути в лабиринте На рис. 3.43 графически изображены рекурсивные вызовы функции FindMazePath (жирные точки), процесс исполнения экземпляров функций FindMazePath (вертикальные линии) и вызовы сопутствующих функций (подписаны).

Состояния path Рекурсивные вызовы FindMazePath FindMazePath (2,3) PushToPath (2,3) MoveLeft (2,2) PushToPath (2,3) (2,2) MoveLeft (2,1) PushToPath (2,3) (2,2) (2,1) MoveDown (3,1) (2,2) (2,1) (3,1) PushToPath (2,3) (2,3) (2,2) (2,1) PopFromPath false...

(2,2) PopFromPath false (2,3) (2,2) (3,2) PushToPath (3,2) MoveDown (2,3) (2,2) PopFromPath (2,3) false PopFromPath (2,3) false (1,3) MoveUp PushToPath (2,3) (1,3) (1,2) MoveLeft PushToPath (2,3) (1,3) (1,2) (0,2) MoveUp (1,2) (0,2) PushToPath (2,3) (1,3) MoveLeft (0,1) PushToPath (2,3) (1,3) (1,2) (0,2) (0,1) MoveLeft (0,0) (1,2) (0,2) (0,1) (0,0) PushToPath (2,3) (1,3) (1,2) (0,2) (0,1) PopFromPath (2,3) (1,3) false (1,1) MoveDown PushToPath (2,3) (1,3) (1,2) (0,2) (0,1) (1,1) (1,0) MoveLeft PushToPath (2,3) (1,3) (1,2) (0,2) (0,1) (1,1) (1,0) (2,0) MoveDown PushToPath (2,3) (1,3) (1,2) (0,2) (0,1) (1,1) (1,0) (2,0) true true true true true true true путь true обнаружен (2,3) (1,3) (1,2) (0,2) (0,1) (1,1) (1,0) (2,0) максимальная глубина рекурсии Рис. 3.43. Рекурсивные вызовы FindMazePath Число одновременно исполняемых экземпляров рекурсивной функции определяет так называемую глубину рекурсии.

Рекурсивные вызовы Состояние стека при вызове FindMazePath из точки (2,1) FindMazePath FindMazePath Локальные данные FindMazePath (2,1) Локальные данные... Кадр для FindMazePath (2,1) FindMazePath из Динамическая связь... точки (2,1) Адрес возврата в FindMazePath (2,2) Локальные данные FindMazePath (2,2) Параметры Кадр для FindMazePath (2,2) FindMazePath из Динамическая связь точки (2,2) Адрес возврата в FindMazePath (2,3) Локальные данные FindMazePath (2,3) Параметры Кадр для FindMazePath из FindMazePath (2,3) точки (2,3) Динамическая связь Адрес возврата в main Рис. 3.44. Рекурсивные вызовы и кадры стека Текущая глубина рекурсии определяет число кадров стека приложения, относящихся к рекурсивной функции (рис. 3.44). Таким образом, затраты на организацию рекурсии находятся в прямой зависимости от максимальной достигаемой в ходе работы глубины рекурсии. В нашем случае максимальная глубина рекурсии – 8, что совпадает с количеством пар координат в найденном пути: (2,3);

(1,3);

(1,2);

(0,2);

(0,1);

(1,1);

(1,0);

(2,0).

Рекомендации в связи с рекурсией При написании рекурсивного алгоритма следует учитывать следующее:

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

Оцените максимальную глубину рекурсии и вытекающие из этого требования к системному стеку. Сопоставьте полученные результаты с затратами на возможную реализацию алгоритма в итерационной форме.

Не используйте рекурсию для тривиальных алгоритмов.

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

Преобразование рекурсивных алгоритмов в итерационные (на примере быстрой сортировки Хоара) Исследуем преобразование рекурсивного алгоритма к итерационному на примере функции быстрой сортировки массива, хранящегося в оперативной памяти, или так называемой сортировки Хоара [Dahl, Dijkstra, Hoare, 1972]. Для простоты изложения рассмотрим сортировку массива целых чисел.

Быстрая сортировка является представителем класса обменных сортировок (простейшим примером обменной сортировки является представленный выше алгоритм сортировки простыми обменами). Основная проблема алгоритма сортировки простыми обменами заключается в том, что осуществляются обмены соседних элементов. Поэтому наиболее «неудачные» элементы достигают своего окончательного места очень медленно, что и определяет низкую эффективность сортировки простыми обменами, оцениваемую величиной O ( n 2 ) (по числу сравнений и пересылок). Поэтому возникает идея увеличить расстояния, на которых происходят обмены. Эта идея была реализована Ч. Хоаром в виде следующего алгоритма. В основе алгоритма лежат разделение последовательности элементов на две подпоследовательности относительно значения одного из элементов (который называется разделяющим элементом). Очевидно, что такое разделение может быть достигнуто однократным просмотром последовательности (см. рис. 3.45).

=x x =x ixLeft ixRight Элементы, Элементы, меньшие или большие или равные x равные x Рис. 3.45. Разделение сегмента в ходе сортировки Если обозначить за x значение разделяющего элемента массива a, состоящего из n элементов целого типа, фрагмент программы, осуществляющий соответствующее разделение, выглядит следующим образом:

Листинг 3.25. Разделение сегмента int ixLeft;

// Индекс просмотра элементов массива слева направо int ixRight;

// Индекс просмотра элементов массива справа налево int copy;

// Вспомогательная переменная для перестановки ixLeft = 0;

ixRight = n-1;

while( ixLeft = ixRight ) { while( a[ ixLeft ] x ) ixLeft++;

while( x a[ ixRight ] ) ixRight--;

if( ixLeft = ixRight ) { copy = a[ ixLeft ];

a[ ixLeft ] = a[ ixRight ];

a[ ixRight ] = copy;

ixLeft++;

ixRight--;

} } В результате цикла разделения в левой части массива оказываются все элементы, меньшие или равные x, а в правой части массива – все элементы, большие или равные x. Таким образом, исходная последовательность разделена на 2 подпоследовательности, которые далее можно рассматривать независимо. Иными словами, если каждую из получившихся подпоследовательностей упорядочить, упорядоченной окажется и исходная последовательность. Нетрудно заметить, что, продолжая далее разделение последовательностей, мы и получим требуемое упорядочение элементов.

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

Листинг 3.26. Рекурсивная функция сортировки Хоара // Функция разделения сегмента, ограниченного индексами // left и right void Split( int *a, int n, int left, int right ) { int ixLeft;

// Индекс при просмотре слева направо int ixRight;

// Индекс при просмотре справа налево int copy;

// Вспомогательная переменная для перестановки int x;

// Разделяющий элемент if( right = left ) return;



Pages:     | 1 | 2 || 4 | 5 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.