for (j = 0; j < п - 1: j++) { if (a[i][j] a[i][j + 1] ) count++: else { if (count > maxcount) {

maxcount = count: line = i: } count = 0:

if (count > maxcount) { maxcount count: line i; }

return line:

2 3

Алгоритм работы функции прост: в каждой строке выполняется сравнение соседних элементов (оператор 2). Если они равны, мы находимся внутри серии, при этом увеличиваем ее текущую длину. Она накапливается в переменной count, которая обнуляется перед обработкой каждой строки (оператор 1). Если же элементы не равны, это означает либо окончание серии, либо просто одиночный элемент (оператор 3). В этом случае надо посмотреть, не является ли данная серия самой длинной из рассмотренных и, если да, то запомнить ее длину и номер строки, в которой она встретилась (оператор 4). Для подготовки к анализу следующих серий в этой же строке надо обнулить счетчик count. Аналогичная проверка после цикла просмотра строки (оператор 5) выполняется для серии, которая расположена в конце строки, поскольку в этом случае ветвь else выполняться не будет. Если в массиве нет ни одной серии одинаковых элементов, функция вернет значение, равное -1.

Задача 7.5. Передача структур в функцию

Написать программу дополнения бинарного файла, сформированного в задаче 6.3, вв(имыми с клавиатуры сведениями о сотрудниках.

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

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

Ниже приведен текст программы.

finclude <stdio.h> #include <string.h> #include <stdlib.h>

finclude <windows.h> 0

const int 1 name = 30;

struct Man {

char name[l name + 1]: int birth year: float pay:

Man read data():

int append2binfile(const Man &man. const char* filename); int print from bin(const char * filename):

int main(){ bool contin; chary n[2]; char filenameC] = dbase.bin ; do { contin - false;

if (append2binfile(read data(), filename) != 0) { putsC* Ошибка при записи в файл ): return 1: }

putsC Продолжить (y/n)? ): gets(y n):

if ((y n[0] - -y) II (y n[0] == Y ) ) contin = true: } while (contin): pri nt from bi n(fi1ename): return 0:

int append2binfile(const Man &man. const char* filename) { FILE *fout:

if ((fout fopen(filename, ab )) NULL ) return 1: int success = fwrite(&man, sizeof(man). 1, fout); fclose(fout):

if (success = 1) return 0; else return 2;

int print from bin(const char * filename) { int num: Man man: FILE *f;

if ((f = fopen(filename, rb )) -= NULL ) return 1:

fseekCf. 0. SEEKJND):

int n record = ftell(f) / sizeof (man):

while (true) {

puts( Введите номер записи или -1: ): scanf( i . &rum): if Сnum < 0 II num >= n record) break: fseek(f. num * sizeof(man). SEEK SET): fread(&man. sizeof(man). 1. f): CharToOem(man.name. man.name):

printf( *30sX5iX10.2f\n . man.name. man.birth year. man.pay);

iSabaUaus

return 0;

Man read data(){ Man man: char buf[80]: char name[l name + 1]: putsCBeeflHTe фамилию И.О. ): gets(name): if (strlen(name) < l name)

for (int i - strlen(name): i < l name: name[i] - : name[l name] - 0:

OemToChar(name, name): 2

strncpy (man. name. name. l name + 1): do {

putsCBeeflHTe год рождения ): gets(buf): } while ((man.birth year - atoi(buf)) - 0): 3

do {

puts( Введите оклад ): gets(buf): } while (!(man.pay - atof(buf))): 4

return man:

В функции ввода read data предусмотрено заполнение пробелами оставшейся части строковой переменной name, чтобы формат имени был идентичен формату ввода в текстовом файле.

ПРИМЕЧАНИЕ -----

Здесь так же, как и в задаче 6.1, необходимо учесть возможные различия в кодировке символов. Если вы работаете в среде Visual С++, а бинарный файл был создан из текстового файла, подготовленного в текстовом редакторе с кодировкой ANSI, то вам нужно раскомментировать операторы 0,1 и 2.

Обратите внимание на то, как в этой функции выполняется проверка правильности ввода числовой информации. Чтение выполняется в буферную строку, которая затем преобразуется с помощью функций atoi () и atof () в числа. Если функции возвращают О, преобразование выполнить не удалось (например, вместо цифр были введены буквы), и информация запрашивается повторно. Условие повторения циклов 3 и 4 записано в двух разных вариантах, чтобы вы сами могли оценить, какой из них вам более понятен (профессионалы предпочли бы второй, более лаконичный вариант).

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

Задача 7.6. Рекурсивные функции

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

Пришло время выполнить обещание, данное на третьем семинаре, - показать рекурсивную реализацию метода быстрой сортировки. Если вы не знаете, что такое рекурсивные функции, загляните в Учебник на с. 82. Говоря кратко, рекурсивной называется функция, в которой имеется обращение к ней самой. Освежите в памяти алгоритм быстрой сортировки, который мы рассматривали, решая задачу 3.3. Там использовалась процедура разделения , применяемая к фрагменту массива (изначально - ко всему массиву). На каждом шаге образовывались две половинки текущего фрагмента, и к ним снова нужно было применять процедуру разделения. То есть по своей сути алгоритм является рекурсивным, и если не здесь применять рекурсивные функции, то где?..

К счастью, любая функция в программе на С++ может вызываться рекурсивно. При этом в стеке выделяется новый участок памяти для размещения копий параметров, а также автоматических и регистровых переменных, поэтому предыдущее состояние выполняемой функции сохраняется, и к нему впоследствии можно вернуться (так и произойдет, если только ваша программа где-нибудь не зависнет). Одна из возможных версий программы сортировки приведена ниже. #include <iostream.h>

void qsort(float* array, int left, int right):

int main(){ const int n = 10: float arr[n]: int i. 1. r:

cout Введите элементы массива: : for (i = 0: i < n: i++) cin arr[i]:

1 = 0: r = n - 1: qscrt(arr. 1. r);

левая и правая границы начального фрагмента

for (i = 0: i < n: i++) cout arr[i] : return 0:

Cm. пояснения к задаче 6.1.

void qsort(float* array, int left, int right) { int i = left, j = right: float middle = array[(left + right) / 2]: float temp:

while (1 < j) { while (arrayCi] < middle) i++: while (middle < arrayCj]) j--: if (i <= j) {

temp = arrayCi]:

arrayCi] - arrayCj]:

arrayCj] = temp:

i++:

J--:

if (left < j) qsort(array. left, j): if (i < right) qsort(array, i. right):

2 3

Мы не будем подробно анализировать эту программу, поскольку алгоритм вам знаком по задаче 3.3. Отметим только, что процедура разделения реализована здесь в виде рекурсивно вызываемой функции qsort (), в теле которой есть два обращения к самой себе: в операторе 2 - для сортировки левой половинки текущего фрагмента, и в операторе 3 - для сортировки его правой половинки. Надеемся, что сравнение этой программы с предыдущей нерекурсивной версией (задача 3.3) вызовет у вас истинное эстетическое наслаждение*.

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

Многофайловые проекты

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

ПРИМЕЧАНИЕ ---

Описанные в приложениях интегрированные среды Visual С++ 6.0 и Borland С++ 3.1, как и подавляющее большинство других, поддерживают создание, компиляцию и сборку многофайловых проектов. С технологией их создания вы можете ознакомиться по приложениям, а здесь мы рассмотрим вопросы, связанные с распределением функций по модулям, разделением интерфейса и реализации и особенностями использования глобальных переменных. Теоретический материал по директивам препроцессора см. в Учебнике на с. 93-96.

Напомним, что пользуясь технологией нисходящего проектирования программ, мы разбиваем исходную задачу на подзадачи, затем при необходимости каждая из них также разбивается на подзадачи, и так далее, пока решение очередной подзадачи не окажется достаточно простым, то есть реализуемым в виде функции обозримого размера (как уже указывалось, наиболее предпочтительным считается размер не более одного-двух экранов текстового редактора). Исходные тексты совокупности функций для решения какой-либо подзадачи, как правило, размещаются в отдельном модуле (файле). Такой файл называют исход-ным (source file). Обычно он имеет расширение . с или . срр. Прототипы всех функций исходного файла выносят в отдельный так называемый заголовочный файл (headerfile), для него принято использовать расширение .h или .hpp. Таким образом, заголовочный файл ххх. h содержит интерфейспдя некоторого набора функций, а исходный файл ххх.срр содержит реализацию этого набора. Если некоторая функция из указанного набора вызывается из какого-то другого исходного модуля ууу.срр, то вы обязаны включить в этот модуль заголовочный файл XXX. h с помощью директивы #i ncl ude. Негласное правило стиля программирования на С++ требует включения этого же заголовочного файла (с помощью #incl ude) и в исходный файл ххх.срр.

Теперь о глобальных переменных. В многофайловом проекте возможны два вида глобальности . Если некоторая глобальная переменная glvarl объявлена в файле ххх.срр с модификатором static, то она видима от точки определения до конца этого файла, то есть область ее видимости ограничена файлом. Если же другая глобальная переменная gl var2 объявлена в файле ххх. срр без модификатора stati с, то она может быть видимой в пределах всего проекта. Правда, для того, чтобы она оказалась видимой в другом файле, необходимо иметь в этом файле ее объявление с модификатором extern (рекомендуется это объявление поместить в файл XXX. h).

Что и как следует размещать в заголовочном файле

в заголовочном файле принято размещать:

□ определения типов, задаваемых пользователем, констант, шаблонов;

□ объявления (прототипы) функций;

□ объявления внешних глобальных переменных (с модификатором extern);

□ пространства имен

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

Если этого не произошло, вернитесь к третьему семинару и выпшнтте все упражнения, вплоть до настоящего семинара, повторно.

Попробуйте не включить и посмотрите на реакцию ко.мпилятора. Пространства имен рассматриваются в Учебнике на с. 99.