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

         

Модульное проектирование


Принцип модульности на самом деле самый простой для понимания и в то же время самый сложный для соблюдения. МОДУЛЬ - это логически завершенная часть программы (алгоритма). Принцип модульности предполагает, что программа строится из множества ограниченных по размеру, логически завершенных, универсальных частей - модулей. В языках программирования понятию модуля соответствует понятие ПРОЦЕДУРА, конкретно в Си - ФУНКЦИЯ. Перечислим основные свойства модуля :



-функция (модуль) должна реализовывать логически законченный, целостный алгоритм ;



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



-функция (модуль) не должна содержать ввода и вывода результатов во внешние потоки - результаты должны быть размещены в структурах данных ;



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



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

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

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



-выполнить goto к имеющемуся фрагменту (категорически не рекомендуется) ;



-повторить текст фрагмента в новом месте (не эффективно) ;



-оформить повторяющийся фрагмент в виде модуля (лучше всего) .



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

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

Для начала необходимо определить интерфейс взаимодействия функции поиска слова и оставшейся части программы. Функция возвращает индекс первого символа слова максимальной длины из входного массива или -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;
}


Модульное программирование


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



Модульное программирование, компоновка


Полученный в результате трансляции ОБЪЕКТНЫЙ МОДУЛЬ включает в себя готовые к выполнению коды команд, адреса и содержимое памяти данных. Но это касается только собственных внутренних объектов программы (функций и переменных). Обращение к внешним функциям и переменным, отсутствующим в данном фрагменте программы, не может быть полностью переведено во внутреннее представление и остается в объектном модуле в исходном (текстовом) виде. Но если эти функции и переменные отсутствуют, значит они должны быть каким-то образом получены в других объектных модулях. Самый естественный способ -написать их на том же самом Си и оттранслировать. Это и есть принцип МОДУЛЬНОГО ПРОГРАММИРОВАНИЯ -представление текста программы в виде нескольких файлов, каждый из которых транслируется отдельно. С модульным программированием мы сталкиваемся в двух случаях:



-когда сами пишем модульную программу;



-когда используем стандартные библиотечные функции.

БИБЛИОТЕКА ОБЪЕКТНЫХ МОДУЛЕЙ -это файл (библиотечный файл), содержащий набор объектных модулей и собственный внутренний каталог. Объектные модули библиотеки извлекаются из нее целиком при наличии в них требуемых внешних функций и переменных и используются в процессе компоновки программы.

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

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



Модульное программированиеПроект


Файл проекта используется при разработке модульной программы, состоящей из нескольких файлов (модулей) (см.4.6). Проект содержит список файлов исходных текстов (.c и

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

.


---------------------------------------------------------------¬
¦File Edit Search Run Compile Debug Project Options Window Help¦
L-----------------------------------¦---------------------------
-+--------------¬
----------------------------------- Open project ¦
¦---------------------------------- Close project ¦
¦¦ +---------------+
¦¦ Добавить файл в проект --------- Add item ¦
¦¦ Удалить файл из проекта -------- Delete item ¦
¦¦ Установка параметров ----------- Local options ¦
¦¦ трансляции текущего файла -- Include files¦
¦¦ Список включаемых файлов ------ L----------------
¦¦ текущего файла
¦¦
¦L Закрыть файл проекта и перейти в обычный режим работы
¦
L- Открыть файл проекта. В отдельном окне выбирается имя файла
проекта. Тип по умолчанию - PRJ. При вводе имени нового файла -
создается файл проекта с текущими установками параметров транс-
лятора и оболочки. Открывается отдельное омно project - список
файлов проекта. При работе в этом окне можно удалять выбранные
файлы из проекта (Del) и включать файлы в проект (Ins). В по-
следнем случае открывается меню для выбора файла.



Нахождение корня функции методом половинного деления


Если имеется математическая функция, значение которой в Си вычисляется некоторой функций вида


double f(double x);

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

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


//------------------------------------------------------bk33-01.cpp


//-----Корень функции по методу середины интервала


double f(double); // Объявление функции f()


double find(double a, double b)
{
double c; // Середина интервала


if (f(a)*f(b) &#62 0)
return (0.); // Одинаковые знаки


for (; b-a &#62 0.001;)
{
c = (a+b) / 2; // Середина интервала


if (f(c)*f(a) &#62 0)
a = c; // Правая половина интервала


else
b = c; // Левая половина интервала


}
return(a); // Возвратить один из концов


} // интервала

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



Нахождение корня функции методом последовательных приближений


Итерационный характер процесса нахождения корня функции явно присутствует в методе последовательных приближений. Для того, чтобы найти корень функции f(x)=0, решается эквивалентное уравнение x = f(x) + x. Если для него значение x в правой части считать результатом итерационного цикла на предыдущем шаге (x1), а значение x в левой части - результатом текущего шага цикла, то такой цикл можно представить следующей схемой, а реализацию ее -программой:

.


x1 = x
________________
| | |
x = f( x1 ) + x1 ------- x1 = x0

// Программа:


x = x0;
do {
x1 = x;
x = f(x1) + x1;
} while( l(x,x1) );

Окончательный вид программы включает еще и проверку качественного характера (сходимости) процесса. Дело в том, что данный метод успешно работает не для всех видов функций f() и начальных значений x0. В принципе итерационный процесс может приводить, наоборот, к бесконечному удалению от значения корня. Тогда говорят, что процесс расходится. Для проверки сходимости приходится запоминать разность значений x и x1 предыдущего шага:


//------------------------------------------------------bk33-02.cpp


// Корень функции по методу последовательных


// приближений


double f(double); // Объявление функции f()



double process(double x, double eps)
{ // начальное значение и точность


double x1,dd;
dd = 100.;
do {
x1 = x;
x = f(x1) + x1;
if (fabs(x1-x) &#62 dd )
return(0.); // Процесс расходится


dd = fabs(x1-x);
}
while (dd &#62 eps);
return(x); // Выход - значение корня


}



Настройка


.


---------------------------------------------------------------¬
¦File Edit Search Run Compile Debug Project Options Window Help¦
L-------------------------------------------¦-------------------
----+-----------¬
¦Application ¦
¦Compiler -
¦Transfer ¦
¦Make ¦
¦Linker -
¦Libraries ¦
¦Debugger ¦
¦Directories ¦
+---------------+
¦Environment -
+---------------+
¦Save ¦
L----------------



Назад: Информатика и технология программирования Структура курса для дневного отделения


Основной материал изложен в "Содержании курса". Курс разбит на главы, которые приблизительно выравнены по семестрам. В каждой главе к каждому параграфу имеются тестовые вопросы ( “Вопросы без ответов ”) и задания к лабораторным работам.



- Информатика (семестр 1). Главы 1-3. 4 лабораторные работы (3.2-3.5). Расчетно-графическая работа (РГР). a href=" prg1ex.htm" target="new" Экзамен&#60/a&#62 включает в себя также тестирование по " Вопросам без ответов" .



- Информатика (семестр 2). Глава 4, начало главы 5. 7 лабораторных работ (4.1-5.3). Зачет.



- Информатика (семестр 3). Главы 5,6. 7 лабораторных работ (5.4-6.3). a href=" prg3ex.htm" target="new" Экзамен&#60/a&#62 (теоретический вопрос, задача, 3 теста), а также тестирование по " Вопросам без ответов" .



- Технология программирования (семестр 4). Главы 7,8. Лабораторные работы (материал отсутствует). a href=" att98.htm" target="new" Аттестационный экзамен&#60/a&#62 по курсам Информатика и Технология программирования.


Для второго высшего образования по специальности 2204 по учебному плану заочного образования материал разбит следующим образом :



- Информатика (семестр 3). Главы 1-3. 4 лабораторные работы (3.2-3.5). a href=" prg1ex.htm" target="new" Экзамен&#60/a&#62 включает в себя также тестирование по " Вопросам без ответов" .



- Информатика (семестр 4). Глава 4. 5 лабораторных работ (4.1-4.8). Экзамен включает в себя тестирование по " Вопросам без ответов" .



- Информатика (семестр 5), Структуры и алгоритмы обработки данных (семестр 5). Глава 5. 8 лабораторных работ (5.2-5.9). a href=" prg3ex.htm" target="new" Аттестационный экзамен&#60/a&#62 (теоретический вопрос, задача, 3 теста), а также тестирование по " Вопросам без ответов" .



- Объектно-ориентированное программирование (семестр 7). Главы 7,8. a href=" att98.htm" target="new" Государственный экзамен&#60/a&#62.

Все изложенное в формате документов Word-97 уложено в a href= "http://ermak.cs.nstu.ru/book_win.arj" архив - 840Kb&#60/a&#62 .




Здесь размещены методические материалы по дисциплинам "Информатика. Алгоритмические языки и программирование" и "Технология программирования". Дисциплины читаются в 1-4 семестрах студентам дневного отделения направления 552800 "Информатика и вычислительная техника" факультета Автоматики и вычислительной техники (АВТФ) Новосибирского государственного технического университета (НГТУ).

По всем вопросам обращайтесь к автору курса Романову Евгению Леонидовичу a href="mailto:romanow@vt.cs.nstu.ru" romanow@vt.cs.nstu.ru&#60/a&#62 или на сайт кафедры вычислительной техники НГТУ a href="http://ermak.cs.nstu.ru" target="new" http://ermak.cs.nstu.ru&#60/a&#62.


Структура курса для дневного отделения


Структура курса для второго высшего образования



Назад: Си++ = Си + классы + объектно-ориентированное


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

Сохранение с новом классе свойств старого называется НАСЛЕДОВАНИЕМ . Принцип наследования состоит в том, что элементы данных старого класса автоматически становятся элементами данных нового класса, а все функции-элементы старого класса применимы к объекту нового класса, точнее к его старой составляющей.

Старый класс при этом называется БАЗОВЫМ КЛАССОМ (БК), новый - ПРОИЗВОДНЫМ КЛАССОМ (ПК).

Синтаксис определения производного класса имеет вид:


class производный : базовый_1, базовый_2,...базовый_n
{ определение личной и общей частей производного класса
}

Перечислим основные свойства базового и производного классов:



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



-элементы данных базового класса включаются в объект производного класса (как правило, транслятор размещает их в начале объекта производного класса). Однако личная часть базового класса закрыта для прямого использования в производном классе;



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



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

Сказанное проиллюстрируем весьма условным примером определения производного класса:


class a
{
public:
void f() {}
void g() {}
};
// производный класс : базовый класс


class b : a


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



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



-по умолчанию, то есть при использовании заголовка class B : A { } общая часть класса A попадает в личную часть класса B. Это значит, что функции-элементы класса A доступны из функций -элементов класса B, но не могут быть вызваны извне при обращении к объектам класса B. То есть для внешнего пользователя класса B интерфейс класса A закрывается;



-при использовании заголовка class B : public A { } общая часть класса A попадает в общую часть класса B, и внешнему пользователю при работе с объектами класса B доступны интерфейсы обоих классов;



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


class B : A
{
public:
public A::fun;
} ;

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

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




С понятием производных классов тесно связан ПОЛИМОРФИЗМ. Прежде всего, полиморфизм -это свойство функции определенной в множестве производных классов, построенных на основе общего базового. В каждом из классов функция может быть переопределена, а может быть унаследована из базового. Свойство полиморфности заключается в том, что при отсутствии полной информации о том, к какому из классов относится объект, функция в состоянии идентифицировать его класс и корректно выполниться в этом классе. Важнейшее следствие полиморфности -возможность организовать регулярный процесс обработки объектов группы производных классов.

Сформулируем теперь свойство полиморфности уже с использованием терминов Си++. Пусть имеется базовый класс A и производные классы B,C. В классе А определена функция -элемент f(), в классах B,C -унаследована и переопределена. Пусть теперь имеется массив указателей на объекты базового класса -p. Он инициализирован как указателями на объекты класса A, так и на объекты производных классов B,C (точнее, на вложенные в них объекты базового класса A):


class a
{ ... void f(); };
class b : public a
{ ... void f(); };
class c : public a
{ ... void f(); };
a A1;
b B1;
c C1;
a *p[3] = { &#38B1, &#38C1, &#38A1 };

Как будет происходить вызов обычной неполиморфной функции при использовании указателей из этого массива ? Очевидно, что транслятор, располагая исключительно информацией о том, что указуемыми переменными являются объекты базового класса A (что следует из определения массива), вызовет во всех случаях функцию a::f(). То же самое произойдет, если обрабатывать массив указателей в цикле:


p[0]-&#62f(); // Вызов a::f()


p[1]-&#62f(); // во всех трех случаях


p[2]-&#62f(); // по указателю на объект базового класса


for (i=0; i&#60=2; i++)
p[i]-&#62f();

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


Если базовый класс используется только для порождения производных классов, то виртуальные функции в базовом классе могут быть "пустыми", поскольку никогда не будут вызваны для объекта базового класса. Базовый класс в котором есть хотя бы одна такая функция, называется АБСТРАКТНЫМ. Виртуальные функции в определении класса обозначаются следующим образом:


class base
{
public:
virtual print()=0;
virtual get() =0;
};

Определять тела этих функций не требуется.




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


class d : public a,public b, public c { };
d D1;
pd = &#38D1; // &#35define db sizeof(a)


pa = pd; // &#35define dc sizeof(a)+sizeof(b)


pb = pd; // pb = (char*)pd + db


pc = pd; // pc = (char*)pd + dc


pc

Такое действие выполняется компилятором как явно при преобразовании в программе типов указателей, так и неявно, когда в объекте производного класса наследуется функция из второго и последующих базовых классов. Для вышеуказанного примера при определении в классе bb функции f() и ее наследовании в классе "d" вызов D1.f() будет реализован следующим образом:


this = &#38D1; // Указатель на объект производного класса


this = (char*)this + db // Смещение к объекту базового класса


b::f(this); // Вызов функции в базовом классе

Механизм виртуальных функций при множественном наследовании имеет свои особенности. Во-первых, на каждый базовый класс в производном классе создается свой массив виртуальных функций (в нашем случае -для aa в d, для bb в d и для cc в d ). Во-вторых, если функция базового класса переопределена в производном, то при ее вызове требуется преобразовать указатель на объект базового класса в указатель на объект производного. Для этого транслятор включает соответствующий код, корректирующий значение this в виде "заплаты", передающей управление командой перехода к переопределяемой функции, либо создает отдельные таблицы смещений.




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


class base {}
class aa : public base {}
class bb : public base {}
class cc : aa, bb {}

В классе cc присутствуют два объекта класса base. Для исключения такого дублирования объект базового класса должен быть объявлен виртуальным:


class a : virtual public base {}
class b : virtual public base {}
class c : public a, public b {}
a A1;
b B1;
c C1;

Объект обычного базового класса располагается, как правило, в начале объекта производного класса и имеет фиксированное смещение. Если же базовый класс является виртуальным, то требуется его динамическое размещение. Тогда в объекте производного класса на соответствующем месте размещается не сам объект базового класса, а указатель на него, который устанавливается конструктором. Для вышеприведенного примера получим такую картину:




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

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


class ADT
{
public:
virtual int Get(char *)=0; // Загрузка объекта из строки


virtual char *Put()=0; // Выгрузка объекта в строку


virtual long Append(BinFile&#38)=0; // Добавить объект в двоичный файл


virtual int Load(BinFile&#38)=0; //


virtual int Type()=0; // Возвращает
идентификатор


// типа объекта


virtual char *Name()=0; // Возвращает имя типа объекта


virtual int Cmp(ADT *)=0; // Сравнивает значения объектов


virtual ADT *Copy()=0; // Создает динамический объект -


// копию с себя


virtual ~ADT(){}; // Виртуальный деструктор


};

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

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



Неизменяемые переменные (константы)


В Си++ введен дополнительный контроль за изменением значений переменных. Ключевое слово const, используемое при определении и инициализации переменной, запрещает ее изменение, что контролируется транслятором при ее дальнейшем использовании. Такая же возможность существует и для формальных параметров функции, например:


const int n=5;
n++; // Запрещено


int xxx(const int m)
{
m++; // Запрещено


}

Применительно к указателю const может использоваться в двух вариантах, как к значению указателя (адресу), так и к указуемой переменной:



-при использовании cons t применительно к указуемой переменной разрешается модифицировать сам указатель при помощи присваивания и операций адресной арифметики, а операции косвенного обращения по указателю запрещены. Такой указатель называется указателем на постоянный объект:


const char * p;
p = "1234567890"; // Разрешено


p + =3; // Разрешено


*(p+3) = '3'; // Запрещено


(*p)++; // Запрещено



-при использовании const применительно к указателю запрещается менять значение указателя после инициализации, в том числе средствами адресной арифметики. Такой указатель называется постоянным указателем:


char const* p = "1234567890";
char c;
(*p) = '3'; // Разрешено


p++; // Запрещено


c = *(p+3); // Запрещено

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


const char const* p = "1234567890";



Немного арифметики


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



Немного о процессе программирования


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



Нисходящее пошаговое структурное проектирование


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



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



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



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

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



-простая последовательности действий;



-конструкция выбора или оператор if;



-конструкция повторения или оператор цикла.

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

.

Формулировка 1: Сделать "что-то" с переменной i
Формулировка 2: i=0;
Сделать "что-то немного другое"
Если i изменилось, сделать "что-то еще"

.

Формулировка 1: Сделать "что-то" с массивом А размерности n.
Формулировка 2: int i;
for (i=0; i&#60n; i++)
{
Проверить и если нужно, сделать
"что-то" с A[i]
}

.

Формулировка 1: Сделать "что-то" с целой переменной B
Формулировка 2: if (B "такое-то")
{ Сделать "одно" }
else
{ Сделать "другое" }



Примеры нарочно выбраны таким образом, чтобы их конкретное содержание не мешало восприятию самого принципа: конструкции языка программирования замещают словесную формулировку алгоритма "сверху-вниз", действие общего вида превращается в формальную конструкцию, содержащую частные действия, но тоже в неформальной словесной формулировке. В результате проектирования получается программа, в которой принципиально отсутствует оператор перехода goto, поэтому структурное программирование иначе называется как "
ПРОГРАММИРОВАНИЕ БЕЗ GOTO".

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

.

Формулировка 1: Сделать "что-то" с массивом А размерности n.

.

Формулировка 1а: Для каждого элемента массива
выполнить проверку и, если нужно, сделать "что-то" с ним.

.

Формулировка 2: int i;
for (i=0; i&#60n; i++)
{ Проверить и если нужно, сделать "что-то" с A[i] }

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

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


Нумерация вершин в деревьяхСпособы обхода дерева


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


//------------------------------------------------------bk55-08.cpp


// Рекурсивный обход двоичного дерева с нумерацией вершин


// снизу-вверх слева-направо, n - текущий номер вершины


int Scan(btree * p, int n)
{
if (p==NULL) retur n n;
Scan(p-&#62lef t,n);
n++;
cout &#60&#60 n &#60&#60 p-&#62val &#60&#60 endl;
n=Scan(p-&#62righ t,n) ;
return n;
}

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


n++;
cout &#60&#60 n &#60&#60 p-&#62val &#60&#60 endl;
n=Scan(p-&#62left,n);
n=Scan(p-&#62right,n);

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


//------------------------------------------------------bk55-09.cpp


// Рекурсивный обход двоичного дерева с последовательной


// нумерацией вершин в возвратом указателя на вершину


// с заданным номером


// Глобальный счетчик вершин передается через указатель


btree *ScanNum(btree *p, int *n)
{
btree *q;
if (p==NULL) return NULL;
q=Scan Num(p-&#62left,n);
if (q!=NULL) return q;
if ((*n)-- ==0) return p;
return Scan Num(p-&#62right,n);
}
void main()
{
btree *ph; int N=26; // Пример вызова


btree *s = ScanNum(ph,&#38N);
}



Объединения


Объединение представляет собой структурированную переменную с несколько иным способом размещения элементов в памяти. Если в структуре (как и в массиве) элементы расположены последовательно друг за другом, то в объединении "параллельно". То есть для их размещения выделяется одна общая память, в которой они перекрывают друг друга и имеют в ней общий адрес. Размерность ее определяется максимальной размерностью элемента объединения. Синтаксис объединения полностью совпадает с синтаксисом структуры, только ключевое слово struct заменяется на union :


union memo
{
long ll;
int ii[2];
char cc[4];
int xx;
} MEM;

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

.


char z;
// 3 2 1 0


// -¬-¬-¬-¬ Элемент ll размещается в MEM,


MEM.ll = 0x12345678; // начиная с младшего байта


z = MEM.cc[2]; // Второй байт в массиве байтов cc


// в MEM имеет значение 0x34


// Результат: z получает значение


// второго байта длинного целого

Естественно, что при таком манипулировании внутренним представлением данных, необходимо знать их форматы и размерность.



Объект и класс как элементы технологии программирования


Технология ООП прежде всего накладывает ограничения на способы представления данных в программе. Любая программа отражает в них состояние физических предметов либо абстрактных понятий (назовем их объектами программирования), для работы с которыми она предназначена. В традиционной технологии варианты представления данных могут быть разными. В худшем случае программист может "равномерно размазать" данные о некотором объекте программирования по всей программе. В противоположность этому все данные об объекте программирования и его связях с другими объектами можно объединить в одну структурированную переменную. В первом приближении ее можно назвать ОБЪЕКТОМ. Кроме того, с объектом связывается набор действий, иначе называемых МЕТОДАМИ. С точки зрения языка программирования это функции, получающие в качестве обязательного параметра указатель на объект. Технология ООП запрещает работать с объектом иначе, чем через методы, то есть внутренняя структура объекта скрыта от внешнего пользователя. Описание множества однотипных объектов называется КЛАССОМ.

Это определение можно проиллюстрировать средствами классического Си:


struct myclass
{
int data1;
};


void method1(myclass *this,...)
{ ... this-&#62data1 ... }


void method2(myclass *this,...)
{ ... this-&#62data1 ... }


struct myclass obj1, obj2;
method1(&#38obj1,...); ... method2(&#38obj2,...);



Объект и класс в синтаксисе языка программирования


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



-класс определяется как структурированный тип данных (struct );



-объекты определяются как переменные класса;



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


struct matrix
{ // определение структурированного типа matrix и методов,


// реализующих операции matrix * matrix, matrix * double


};
matrix a,b; // Определение переменных -


double dd; // объектов класса matrix


a = a * b; // Использование переопределенных операций


b = b * dd * 5.0;

программистом базовый тип данных. Объект - переменная класса



Объекты и классы


Для начала - краткая пробежка по терминам и определениям. ООП - это прежде всего объекты и классы, а технология ООП - программирование не "от функции к функции", а "от класса к классу".



ОБЪЕКТЫ ИЗУЧЕНИЯ


· " Классический" Си с базовыми типами данных и массивами;

· Базовые фрагменты алгоритмов, алгоритмы обработки строк, приближенных (итерационных) в ы числений, поиска и сортировки;

· Система программирования Borland C под DOS.


Типы данных, производные типы данных, контекстное определение типа данных в Си, указатели, структуры, функции, управление памятью в Си, структуры данных переменного формата,




· язык и среда программирования Си++ ( Borland C ) под DOS;

· классы, объекты и методы, их синтаксис и свойства ;

· технология объектно-ориентированного программирования применительно к типам данных, структурам данных и организации программы.




· рекурсивные алгоритмы и структуры данных - деревья ;

· указатели на функции, динамическое связывание алгоритмов, итераторы ;

· иерархические структуры данных ;

· двоичные файлы произвольного доступа, структуры данных в файлах - массивы, массивы указат е лей, списки, деревья ;

· таблицы и индексные файлы баз данных, их организация ;

· машинно-зависимое программирование на Си, модели памяти, указатели ;

· прерывания и квази-параллельные процессы, резидентные программы.



Обход шахматной доски


В качестве примера рассмотрим проектирование функции для поиска последовательности обхода конем шахматной доски.

Шаг 1. Алгоритм обхода можно разбить на последовательность шагов. Каждый шаг характеризуется начальным состоянием - текущим положением коня. Алгоритм на каждом шаге предполагает проверку возможности сделать ход в каждом из 8 допустимых направлений. Схема алгоритма имеет вид:


void step(int x0, int y0)
{ // формальные параметры -


// текущая позиция коня


// приращения координат для 8 ходов


static int xy[8][2] = {{ 1,-2},{ 1, 2},{-1,-2},{-1, 2},
{ 2,-1},{ 2, 1},{-2, 1},{-2,-1}
};
int i; // локальный параметр - номер хода


if (x &#60 0 || x &#62=7 || y &#60 0 || y &#62=7 )
return; // выход за пределы доски


for (i=0; i&#60 8; i++)
step(x0+xy[i][0], y0+xy[i][1]);
// выполнить следующий ход


}

Шаг 2. Предыдущий шаг дает полный перебор возможных последовательностей ходов коня. Функция имеет результат void, то есть является безусловной. Далее необходимо определить, как производить выбор необходимой последовательности. Очевидно, функция должна давать логический результат - 0, если при выполнении очередного хода в данном направлении задача не решается и 1, если решается успешно. При этом цикл, в котором происходит рекурсивный вызов - просмотр очередных ходов, выполняется до первого успешного вызова:


int step(int x0, int y0)
{
static int xy[8][2] = {{ 1,-2},{ 1, 2},{-1,-2},{-1, 2},
{ 2,-1},{ 2, 1},{-2, 1},{-2,-1}
};
int i; // локальный параметр - номер хода


if (x &#60 0 || x &#62=7 || y &#60 0 || y &#62=7 )
return(0); // выход за пределы доски


for (i=0; i&#60 8; i++)
if (step(x0+xy[i][0], y0+xy[i][1]))
return(1); // поиск успешного хода


return(0); // последовательность не найдена


}

Шаг 3. Далее необходимо определить условия начала и завершения рекурсивного процесса, а также условия взаимодействия шагов между собой. Условием завершения процесса является обход всех 64 полей доски. При этом не должно производиться повторное попадание на то же самое поле.
Тогда необходимо фиксировать количество пройденных полей и отмечать пройденные. Это можно сделать только используя внешние переменные, так как они проверяются на разных шагах рекурсии. Номер шага будем использовать также для отметки поля. По завершению программы массив полей будет содержать номера шагов коня.



//------------------------------------------------------bk54-02.cpp

//------Обход шахматной доски конем

int desk[8][8]; // поля доски

int nstep; // номер шага

int step(int x0, int y0)
{
static int xy[8][2] = {{ 1,-2},{ 1, 2},{-1,-2},{-1, 2},
{ 2,-1},{ 2, 1},{-2, 1},{-2,-1}
};
int i; // локальный параметр - номер хода

if (x0 &#60 0 || x0 &#62=7 || y0 &#60 0 || y0 &#62=7 )
return(0); // выход за пределы доски

if (desk[x0][y0] !=0)
return(0); // поле уже пройдено

desk[x0][y0] = nstep++; // отметить свободное поле

if (nstep == 64)
return(1); // все поля отмечены - успех

for (i=0; i&#60 8; i++)
if (step(x0+xy[i][0], y0+xy[i][1]))
return(1); // поиск успешного хода

nstep--; // вернуться на ход назад

desk[x0][y0] = 0; // стереть отметку поля

return(0); // последовательность не найдена

}
void Path(int x0, int y0)
{
int i,j; // очистка доски

for (i=0; i&#60 8; i++)
for (j=0; j&#60 8; j++) desk[i][j] =0;
nstep = 1; // установить номер шага

step(x0,y0); // вызвать функцию для исходной

} // позиции


Область переполнения


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



- при поиске по индексу производится двоичный поиск в основной области и последовательный в области переполнения;



- при добавлении записи ссылка на нее заносится в область переполнения;



- при удалении записи и удалении ссылки на нее из основной области "уплотнение" этой области не производится, в индексной таблице возникает "пустое место";



- при обновлении записи ссылка на нее может быть исключена из основной области и включена в область переполнения;



- при увеличении области переполнения выше некоторого предела индекс пересобирается заново.



Области действия функций


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



-внешние функции: доступны во всех модулях программы;



-статические функции: доступны только в модуле, в котором они определены.

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

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

.


Файл a.c Файл b.c

.


объявление функции в объявление внешней
собственном модуле функции
char *f(int,int); extern char *f(int,int);

.


область действия область действия
... f(10,n) ... ... f(15,m) ...
определение функции
char *f(int n1, int n2)
{ ... тело функции ... }

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

.


Обычное объявление Объявление по прототипу
int strcmp(); int strcmp(char* ,char*);
char getch(); char getch(void);

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


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

extern int f();



Такое умолчание приводит к нескольким достаточно распространенным ошибкам:




-если программист по ошибке указывает вызов функции с неправильным именем, то при трансляции ошибка, как правило, не возникает, но при этом компоновщик не находит данное имя в собственных библиотеках. Ошибка, таким образом, переносится на этап компоновки. Например,
pintf("%d %d\n",a,b) приводит к успешной трансляции, но к ошибочной компоновке программы в связи с отсутствием функции pintf ;


-если вызов функции в модуле выполняется до ее определения, то по умолчанию она также объявляется в точке ее вызова. Это может привести к конфликту типов результата в месте ее последующего определения. Особенно это касается "любителей" располагать
функцию main в начале модуля:

void main()
{ // по умолчанию объявляются как

f(); // extern int f();

g(); // extern int g();

}
void f() // конфликт типов результата

{ // int и void в объявлении

} // и определении функции




Такую ошибку можно исключить предварительным объявлением функции в любом месте перед ее вызовом:



void f();








-если используется библиотечная функция, которая возвращает не целый результат, то отсутствие ее объявления приводит к тому, что возникает расхождение между ожидаемым транслятором по умолчанию типом int и реально возвращаемым типом (например,
char* или double ). Если эти результаты имеют одну размерность, то, как правило, ошибки не происходит. В противном случае возвращаемое значение "усекается" или "расширяется" до int и становится неопределенным. В приведенном ниже примере результат типа double "усекается" (но не преобразуется) до int , а затем опять переводится в тип double . Ошибка связана с отсутствием объявления функции sin:





// отсутствует объявление extern double sin();

double y; y = sin(1.0);






В следующем примере размерность указателя, возвращаемой функцией malloc в зависимости от текущей модели памяти будет равна размерности int или
long . Это приведет к тому, что при отсутствии объявления функции в одних моделях памяти она будет работать, а в других -нет:



// отсутствует объявление extern void *malloc();

double *p; p = malloc(sizeof(double));



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

&#35include &#60alloc.h&#62
&#35include &#60math.h&#62


Области действия функцийОпределения и объявления


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



-имя функции;



-тип результата;



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

Вся перечисленная информация о функции находится в ее заголовке. Таким образом, достаточно этот заголовок привести отдельно, и проблема корректного вызова решается. Такой заголовок называется объявлением или в рассматриваемом нами варианте синтаксиса ПРОТОТИПОМ ФУНКЦИИ.

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


int B[10];
int sum(int s[],int n); // Объявление функции,


// определенной далее по тексту


extern int printf(char *,...);
// Объявление библиотечной функции


// с переменным числом параметров


extern int other(void); // Объявление функции без


// параметров из другого


void main() // файла программы


{ //


sum(B,10); // Вызовы объявленных функций


cout &#60&#60 B[i]);
other();
}
int sum(int s[], int n)


{...}

Из примера видно, что объявление функции практически дублирует заголовок, отличаясь в некоторых деталях:


-объявление заканчивается символом ";" ;


-если функция находится вне текущего файла, то объявление предваряется служебным словом
extern;


-имена переменных в списке формальных параметров объявления могут отсутствовать;


-если функция не имеет формальных параметров, то в объявлении присутствует формальный параметр типа void.

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

extern double sin(double);
int x;
double y;
y = sin(x);
//------Неявное преобразование (double)x

В заключение отметим существенную разницу между определением и объявлением.

ОПРЕДЕЛЕНИЕ ОБЪЕКТА (переменной, функции) задает объект и приводит к трансляции во внутреннее
представление. ОБЪЯВЛЕНИЕ ОБЪЕКТА -- это информация транслятору о факте наличия объекта в недоступной на данный момент части программы.

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


-определения и объявления функций и переменных;


-исторические варианты синтаксиса определений и объявлений и контроля параметров функций;


-ошибки программирования, связанные с объявлениями.


Обменные сортировки


Обзор алгоритмов сортировки начнем с горячо любимой автором (с методической точки зрения), но с наименее эффективной простой сортировки обменом, или сортировки МЕТОДОМ "ПУЗЫРЬКА". Суть ее заключается в следующем: производится попарное сравнение соседних элементов 0-1,1-2 и т.д. и перестановка, если пара расположена не в порядке возрастания. Просмотр повторяется до тех пор, пока перестановок больше не будет. Метод получил свое название за то, что "более весомые" элементы поднимаются в процессе сортировки к концу массива:


//------------------------------------------------------bk35-03.cpp


//------Сортировка методом "пузырька"


void sort(int A[], int n)
{
int i,found; // Количество сравнений


do { // Повторять просмотр...


found =0;
for (i=0; i&#60n-1; i++)
if (A[i] &#62 A[i+1]) // Сравнить соседей


{ // Переставить соседей


int cc;
cc = A[i]; A[i]=A[i+1]; A[i+1]=cc;
found++;
}
} while(found !=0); //...пока есть перестановки


}

Оценить трудоемкость алгоритма можно через среднее количество сравнений, которое равно ( n*n -n )/2.

ШЕЙКЕР-СОРТИРОВКА учитывает тот факт, что от последней перестановки до конца массива будут находиться уже упорядоченные данные, например:


шаг n 5 7 10 9 8 12 14
5 7 ***** 8 12 14
последняя перестановка 5 7 9 ***** 12 14
5 7 9 8 10 12 14
шаг n+1 ------------
упорядоченная часть

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



Обработка программного прерывания


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


&#35include &#60dos.h&#62
&#35define USERVEC 0x60 // Вектор программного прерывания


void interrupt
USERINT(bp,di,si,ds,es,dx,cx,bx,ax,ip,cs,flgs)
// ds:dx - начальный адрес буфера


// cx - размер буфера в байта


// ax,bx - координаты строки x,y


// Программное прерывание выводит строку из буфера


// непосредственно в видеопамять


{
char far *p; // Указатель на буфер строки


char (far *video)[25][80][2]; // Указатель на на страницу 0


video=0xB8000000; // видеопамяти


p = MK_FP(ds,dx); // Сформировать длинный


// указатель из регистров ds,dx


while(cx-- !=0) // bx,cx не сохраняются


{
(*video)[bx ][ax][0]= *p++;
(*video)[bx++][ax][1]= 0x5E;
}}


char name[80]="a-a-a-a-a-a-a-a";
void main()
{
union REGS R; // Union для установки содержимого


// регистров в программном прерывании


setvect(USERVEC, (void interrupt (far*)(...))USERINT);
// Установка вектора прерывания


R.x.ax=5; // Запись содержимого регистров


R.x.bx=10; // ax,bx - координаты строки


R.x.cx=strlen(name); // cx - длина строки


R.x.dx=name; // dx - начальный адрес строки


int86(USERVEC,&#38R,&#38R); // Выполнение программного


// прерывания по вектору USERVEC


_DX=name; // Альтернативный вариант


_CX=strlen(name); // с непосредственным


_BX=10; // использованием регистров


_AX=5;
geninterrupt(USERVEC);
}



Односвязные списки


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


//------------------------------------------------------bk53-01.cpp


struct list
{ int val; list *next; };
//----- Линейный просмотр списка --------------------------


void scan(list *ph) // Заголовок списка


{ list *p;
for (p = ph; p != NULL; p = p-&#62next) { /* ...*/ }
}
//----- Включение элемента в начало списка


// v - включаемое значение


// ph - Указатель на заголовок списка


list *insertfirst(list *ph, int v)
{ list *p = new list; // создать элемент списка


p-&#62val = v; // и заполнить его


p-&#62next = ph; // следующий за новым - старый первый


ph = p; // новый первый - вновь созданный


return ph ; } // вернуть указатель на первый


//----- Включение элемента в конец списка ----------------


list *insertlast(list *ph, int v)
{ list *q ,*p= new list; // создать элемент списка;


p-&#62val = v; // и заполнить его


p-&#62next = NULL; // новый элемент - последний


if (*ph == NULL) ph = p; // список пуст


else // поиск последнего в


{ // непустом списке


for (q = *ph; q-&#62next !=NULL; q = q-&#62next);
q-&#62next = p; // включить за последним


}
return ph;
}
//----- Удаление элемента из списка по заданному номеру


list *removelist *p h, int n)
{ list *q ,*pr,*p;
// Двигаться по списку, пока он не кончится, либо пока


// не обнулится счетчик, сохраняя указатель на предыдущий



// элемент - pr

for ( p=ph,pr=NULL; n!=0 &#38&#38 p!=NULL; n--, pr=p, p =p-&#62next);
if (p==NULL) return ph;
if (pr==NULL)
{ q=ph; ph=ph-&#62next; } // Исключить первый

else // Исключить из середины

{ q=p; pr-&#62next=p-&#62next; }
delete q; // Уничтожить элемент списка

return ph;
}

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


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


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



//------------------------------------------------------bk53-02.cpp

// Поиск и удаление элемента списка с минимальным значением

// Заголовок списка - " фиктивный" элемент без данных

// Используется указатель на предыдущий элемент от искомого

int remove_min(list *ph)
{ // pmin - предыдущий перед минимальным

list *pmin,*p;
for (pmin=p=ph; p-&#62next!=NULL; p=p-&#62next)
if (pmin-&#62next-&#62val &#60 p-&#62next-&#62val)
pmin=p;
list *q=pmin-&#62next;
pmin-&#62next = q-&#62next;
int vv=q-&#62val;
delete q;
return vv;
}
void main()
{list PH={0,NULL};} // Заголоков пустого списка в программе

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



//------------------------------------------------------bk53-03.cpp

// Включение в конец списка

// Используется ссылка на указатель на переменную-заголовок




void insertlast(list * &#38ph, int v)
{ list *qq; // указатель на текущий

list *p= new list; // создать элемент списка;

p-&#62val = v; // и заполнить его

p-&#62next = NULL; // новый элемент - последний

if (ph==NULL) ph=p; // Список пустой меняем заголовок

else
{ // Поиск последнего

for (qq = ph; qq-&#62next!=NULL; qq = qq-&#62next);
qq -&#62next = p;
}
}
//----- Удаление элемента из списка по заданному номеру

// Используется ссылка на указатель на переменную-заголовок

void removelist * &#38p h, int n)
{ list *q ,*pr,*p;
// Двигаться по списку, пока он не кончится, либо пока

// не обнулится счетчик, сохраняя указатель на предыдущий

// элемент - pr

for ( p=ph,pr=NULL; n!=0 &#38&#38 p!=NULL; n--, pr=p, p =p-&#62next);
if (p==NULL) return ph;
if (pr==NULL)
{ q=ph; ph=ph-&#62next; } // Исключить первый

else // Исключить из середины

{ q=p; pr-&#62next=p-&#62next; }
delete q; // Уничтожить элемент списка

}


Односвязный список в файле


Наиболее показателен примером структуры данных при поэлементной загрузке данных в память является односвязный список. В приведенном ниже примере следует обратить внимание на полную функциональную аналогию алгоритма работы с односвязным списком в памяти и в файле. Особенности работы с файлом заключаются в том, что для каждого активизируемого элемента структуры данных необходим аналогичный элемент в памяти, а для указателя на него - соответствующий файловый указатель. Так, если для включения в односвязный список с сохранением упорядоченности необходимо использовать текущий и предыдущий элементы списка, то необходимы две локальные структурированные переменные - текущий и предыдущий элементы списка cur и prev, а также два файловых указателя, определяющих их расположение в файле - fcur и fprev . В начале файла размещается заголовок списка - файловый указатель на первый элемент.


//------------------------------------------------------bk59-11.cpp


// Список в файле. Поэлементная работа . В начале файла -


// заголовок - указатель на первый элемент.


&#35define FNULL -1L
struct flist // Определение элемента списка


{
int val; // Значение элемента списка


long fnext; // Файловый указатель на следующий элемент


}; // При поэлементной работе flist *next не нужен


void show(FILE *fd) // Просмотр списка


{ flist cur; // Файловый указатель текущего элемента


long fcur; // Текущий элемент


fseek(fd,0L,SEEK_SET);
fread(&#38fcur,sizeof(long),1,fd); // Загрузить указатель на первый


for (; fcur!=FNULL; fcur=cur.fnext)
{ // Загрузка текущего элемента


fseek(fd,fcur,SEEK_SET);
fread(&#38cur,sizeof(flist),1,fd);
printf("%d ",cur.val);
}
puts("");}


void ins_sort(FILE *fd, int vv)
{ // Включение с сохранением упорядоченности


fl ist cur,prev,lnew; // Текущий и предыдущий и новый элементы списка


long fnew,fcur,fprev; // Файловые указателя элементов списка


fseek(fd,0L,SEEK_SET);
fread(&#38fcur,sizeof(long),1,fd);
for (fprev=FNULL; fcur!=FNULL;


fprev=fcur, prev=cur, fcur=cur.fnext)
{ // Переход к следующему с запоминанием

fseek(fd,fcur,SEEK_SET); // предыдущего элемента и его адреса

fread(&#38cur,sizeof(flist),1,fd);
if (cur.val &# 62 vv) break; // Поиск места - текущий &#62 нового

}

lnew.val = vv;
lnew.fnext=fcur;
fseek(fd,0L,SEEK_END); // Заполнение нового элемента списка

fnew=ftell(fd); // Запись в файл и получение адреса

fwrite(&#38lnew,sizeof(flist),1,fd);

if (fprev==FNULL) // Включение первым -

{ // обновить заголовок

fseek(fd,0L,SEEK_SET);
fwrite(&#38fnew,sizeof(long),1,fd);
}
else // Включение после предыдущего -

{
prev.fnext=fnew; // обновить предыдущий

fseek(fd,fprev,SEEK_SET);
fwrite(&#38prev,sizeof(flist),1,fd);
}}


Одновременное проектирование алгоритма и структур данных


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

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



Ограничение доступа к объектам классаДружественность


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

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


class A
{
int x; // Личная часть класса


...
friend class B; // Функции класса B дружественны A


// (имеют доступ к приватной части A)


friend void C::fun(A&#38); // Элемент-функция fun класса C имеет


// доступ к приватной части A


friend void xxx(A&#38,int); // Функция xxx дружественна классу A


friend void C::operator+(А&#38); // Переопределяемая в классе C операция


}; // &#60объект C&#62+&#60объект A&#62 дружественна


// классу A


class B // Необходим доступ к личной части A


{
public: int fun1(A&#38);
void fun2(A&#38);
};
class C
{
public: void fun(A&#38);
void operator+(A&#38);
};

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


void dat::put() const { ... }



Операции над индексными таблицами и файлами


Создание индексной таблицы (файла) заключается в заполнении и последующей сортировке таблицы ссылок.

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

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

- при добавлении записи ссылка на нее должна быть добавлена в индекс с сохранением установленной упорядоченности, что, возможно, требует "раздвигания" индексной таблицы;

- при удалении записи ссылка на нее должна быть удалена из индекса с соответствующим "уплотнением" индексной таблицы;

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



Операции над указателями


В процессе определения указателей мы рассмотрели основные операции над указателями:



-операция присваивания указателей одного типа. Назначение указателю адреса переменной p=&#38a есть одни из вариантов такой операции: выражение &#38a является постоянным (константным) указателем такого же типа, что и p;



-операция косвенного обращения по указателю;



-операция адресной арифметики " указатель+целое" и все производные от нее.

Кроме того, имеется еще ряд операций, понимание которых не выходит за рамки "здравого смысла" понятия указателя .

СРАВНЕНИЕ УКАЗАТЕЛЕЙ НА РАВЕНСТВО: равенство указателей однозначно понимается как совпадение адресов, то есть назначение их на одну и ту же область памяти (переменную);

ПРЕОБРАЗОВАНИЕ " УКАЗАТЕЛЬ -ЦЕЛОЕ" : в конечном счете адрес, который представляет собой значение указателя, является обычным машинным словом определенной размерности, чему в Си соответствует целая переменная. Поэтому в Си преобразования типа " указатель-целое" и " целое-указатель" понимаются как получение адреса памяти в виде целого числа и преобразование целого числа в адрес памяти, то есть как работа с реальными адресами памяти компьютера. Такие операции являются в большинстве своем машинно-зависимыми, поскольку требуют знания некоторых тонкостей работы компьютера, операционной системы и транслятора:



-системы преобразования адресов компьютера, размерностей используемых указателей (int или long);



-особенностей распределения памяти транслятором и операционной системой;



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

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

"ПУСТОЙ" УКАЗАТЕЛЬ: среди множества адресов выделяется такой, который не может быть использован в правильно работающей программе для размещения данных.
Это значение адреса называется NULL-УКАЗАТЕЛЕМ или "пустым" указателем. Считается, что указатель с таким значением не является корректным (указывает "в никуда"). Обычно такое значение определяется в
стандартной библиотеке ввода-вывода в виде &#35define NULL 0.

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



int *p,a;
if () p=NULL; else p=&#38a; ...
if (p !=NULL) *p = 5; ...





СРАВНЕНИЕ УКАЗАТЕЛЕЙ НА БОЛЬШЕ-МЕНЬШЕ: при сравнении указателей производится сравнение соответствующих адресов как беззнаковых переменных. Естественный смысл такого сравнения имеется, если оба указателя ссылаются на элементы одного и того же
массива, тогда соотношение " больше-меньше" следует понимать как " ближе-дальше" к началу массива:

// Перестановка элементов массива симметрично середины

int A[20],i,j,x;
for(i=0,j=19; i&#60j; i++, j--)
{ x = A[i]; A[i] = A[j]; A[j] = x; }
int A[20],*pi,*pj,x;
for (pi=A,pj=A+19; pi &#60 pj; pi++, pj--)
{ x = *pi; *pi = *pj: *pj = x; }

РАЗНОСТЬ ЗНАЧЕНИЙ УКАЗАТЕЛЕЙ: в случае, когда указатели ссылаются на один и тот же массив, их разность понимается как "расстояние между ними",
выраженную в количестве указуемых переменных.

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


Операции присваивания


К операциям присваивания относятся все операции, которые меняют значение одного из операндов. В Си их целых три группы:



-обычное присваивание (=);



-присваивание, соединенное с одной их бинарных операций (+=, -=, *=, /=, %=, &#60=, &#62=, &#38=, |=, ^=);



-операции инкремента и декремента (увеличения и уменьшения на 1).

Операция присваивания "=" сохраняет значение выражения, стоящего в левой части, в переменной, а точнее, в адресном выражении, стоящем а правой части. Термин "АДРЕСНОЕ ВЫРАЖЕНИЕ" (или l-value ) используется для обозначения тех выражений, которым соответствуют объекты (переменные) в памяти программы. На данном уровне знакомства со структурами данных -это простые переменные и элементы массивов.

При выполнении операции присваивания тип выражения в правой части преобразуется к типу адресного выражения в левой. Результатом операции является значение левой части после присваивания, соответственно, тип результата -это тип левой части. Кроме того, присваивание -одна из немногих операций с направлением выполнения "справа налево". Из сказанного следует возможность многократного присваивания "справа налево", в котором результат каждого из них используется как правая часть последующего:


long a; char b; int c;
a = b = c; // эквивалентно b = c; a = b;

В данном случае при первом (правом) присваивании тип int преобразуется к char, а результатом операции является значение переменной b типа char после выполнения этого присваивания.

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


a +=b; // эквивалентно a = a + b;

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


A[i++] +=b; // эквивалентно A[i] = A[i] + b; i++;

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

.


int a; // Эквивалент Интерпретация


a++; // Rez=a; a=a+1; Увеличить на 1 после использования


++a; // a=a+1; Rez=a; Увеличить на 1 до использования


a--; // Rez=a; a=a-1; Уменьшить на 1 после использования


--a; // a=a-1; Rez=a; Уменьшить на 1 до использования



Операции сравнения и логические операции


В Си отсутствует особый базовый тип данных для представления логических значений "ИСТИНА" и "ЛОЖЬ". Для этой цели используются значения целой переменной. Значение 0 всегда является "ложью". Значение 1 - "истиной". Такие значения дают операции сравнения и логические операции. Вообще, в широком смысле любое ненулевое значение является истинным. В такой интерпретации проверяются условия в операторах программы. Поэтому можно записать:


if (1) { A } else { B } // Всегда выполнять B


while (1) { ... } // "Вечный" цикл


if (k) { A } else { B } // Эквивалентно if(k !=0)

Все операции сравнения дают в качестве результата значения 1 или 0. Следовательно, их можно использовать совместно с арифметическими и другими операциями:


a = b &#62 c; // Запомнить результат сравнения


a = (b &#62 c)* 2 // Принимает значения 0 или 2

ЛОГИЧЕСКИЕ ОПЕРАЦИИ И (&#38&#38) , ИЛИ (||) и НЕ (!) едины для всех языков программирования и соответствуют логическим функциям И, ИЛИ и НЕ для логических (булевых) переменных. Операция И имеет результатом значение "истина" тогда и только тогда, когда оба ее операнда истинны, то есть по отношению к операндам -утверждениям звучит как "одновременно оба". Операция ИЛИ имеет результатом значение "истина", когда хотя бы один из операндов истинен, то есть характеризуется фразой "хотя бы один":


if (a &#60 b &#38&#38 b &#60 c) // если ОДНОВРЕМЕННО ОБА a &#60 b и b &#60 c, то...


if (a==0 || b &#62 0) // если ХОТЯ БЫ ОДИН a==0 или b &#62 0, то...

Логические операции И и ИЛИ имеют еще одно свойство. Если в операции И первый операнд имеет значение "ложь", а в операции ИЛИ -"истина", то вычисление выражения прекращается, потому что значение его уже становится известным ("ложь" -для И , "истина" -для ИЛИ ). Поэтому возможны выражения, где в первом операнде операции И проверяется корректность некоторой переменной, а во втором -она же используется с учетом этой корректности:


if (a &#62=0 &#38&#38 sin(sqrt(a)) &#62 0) ...

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

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


while(!k) {...} // эквивалентно while(k==0) {...}



Операции, выражения


Содержание этого и последующих параграфов ясно из их названия.



Операция поразрядной ИНВЕРСИИ


Поразрядная операция инверсии ("~") меняет значение каждого бита машинного слова на противоположное (инвертирует). Операция настолько простая, что не нуждается в комментариях. В качестве примера рассмотрим поразрядную операцию И между переменной и инвертированной константой, которая в таком случае интерпретируется как ОЧИСТКА БИТОВ по маске, заданной константой:


a &#38= ~0x0861; // Очистить биты 0,5,6,11, остальные сохранить


a &#38= ~0x00F0; // Очистить биты с 4 по 7, остальные сохранить


// (биты второй цифры справа)



Операция последовательности действий ("запятая")


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

.


for (i=0; i&#60n; i++) // Обычный цикл


{...A[i]...}
// Выражение Выражение


// __________ ________


for (i=0,j=n-1; i&#60j; i++,j--) //Цикл с двумя индексами


{...A[i]...A[j]...}

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

.

// __________ Выражение


while( a=b, a &#60 0) {....}

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

Некоторые группы операций тесно связаны со специфическими разделами программирования, поэтому рассматривать их отдельно не имеет смысла. К таковым относятся машинно - ориентированные (поразрядные) операции (3.5), операции с указателями и памятью (4.1,4.4), массивами и структурами (4.2,4.3)



Операция СДВИГ ВЛЕВО


Поразрядная операция " сдвиг влево" ("&#60&#60") переносит каждый бит первого операнда на то количество разрядов влево, которое задано вторым операндом, освобождающиеся разряды справа заполняются нулями. Результат операции содержит сдвинутое машинное слово, а первый операнд не изменяется. В общем случае значение результата можно получить путем перевода значения машинного слова в двоичный код и выполнения над ним операции


0x764A &#60&#60 3 ... 0111 0110 0100 1010 &#60&#60 3 ...
1011 0010 0101 0000 ... 0xB250

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


a &#60&#60= 4; // сдвиг влево на одну шестнадцатеричную цифру;


a = 1&#60&#60n; // установить 1 в n-й разряд машинного слова.

У операции сдвига влево есть еще одна интерпретация. Если рассматривать машинное слово как целое без знака, то однократный сдвиг увеличивает его значение в 2 раза, двукратный -в 4 раза, n-кратный -в n-ю степень 2. То есть операция сдвига влево равносильна умножению целого на степень 2. В таком виде, например, умножение числа на 10 можно представить так:


a*10 ... a*(8+2) ... 8*a + 2*a ... (a&#60&#60 3) + (a&#60&#60 1)



Операция СДВИГ ВПРАВО


Поразрядная операция " сдвиг вправо" ("&#62&#62") переносит каждый бит первого операнда на то количество разрядов вправо, которое задано вторым операндом, Результат операции содержит сдвинутое машинное слово, а первый операнд не изменяется. В общем случае значение результата можно получить путем перевода значения машинного слова в двоичный код и выполнения над ним операции:


0x764A &#62&#62 3 ... 0111 0110 0100 1010 &#62&#62 3 ...
0000 1110 1100 1001 ... 0x0EC9

По аналогии со сдвигом влево операция сдвига вправо на n разрядов для положительного числа или беззнакового целого интерпретируется как целочисленное деление на 2 в степени n. Несколько слов следует сказать о заполнении освобождающихся старших разрядов. Оно производится таким образом, чтобы сдвиг соответствовал операции деления с учетом формы представления целого. Для беззнакового целого заполнение должно производиться нулями (ЛОГИЧЕСКИЙ СДВИГ), а для целого со знаком -сопровождаться дублированием значения старшего знакового разряда (АРИФМЕТИЧЕСКИЙ СДВИГ). В последнем случае отрицательное число при сдвиге останется отрицательным:


int n=0xFF00; n&#62&#62=4; // n=0xFFF0;


unsigned u=0xFF00; u&#62&#62=4; // u=0x0FF0;



Операторы цикла


В Си имеется три вида циклических конструкций. Общее у них одно: все условия в них являются УСЛОВИЯМИ ПРОДОЛЖЕНИЯ, то есть циклы продолжаются, пока значение этих условных выражений -" истина" . Операторы цикла состоят из заголовка, в котором определяется характер циклического процесса и тела цикла. Скобки в заголовке цикла являются неотъемлемым элементом синтаксиса языка. Первые два вида циклов отличаются временем проверки условия продолжения - до или после очередного шага цикла:

.


while (выражение) оператор

.


do оператор while(выражение);
___________ __________
тело цикла условие продолжения

Наиболее универсальный цикл for имеет полный эквивалент в цикле while:

.


Заголовок цикла Тело цикла
______________________________________ ________
for (выражение_1; выражение_2; выражение_3) оператор
___________ ____________ ___________
инициализация условие повторяющаяся
продолжения часть
___Эквивалент___________________________________________
выражение1; while (выражение2) { оператор выражение3; }

Первое выражение вычисляется перед началом цикла -инициализирует его или устанавливает начальное состояние. Второе выражение является условием его продолжения. Оно проверяется перед каждым шагом цикла, и при условии его истинности цикл повторяется. И, наконец, в самом шаге цикла выполняется оператор и третье выражение, которое является повторяющейся частью цикла. Как видим, цикл for не накладывает никаких ограничений на вид выражений в его заголовке, поэтому привычный для нас


for (i=0; i&#60n; i++) ...

с последовательно меняющейся переменной цикла является лишь очень частным случаем.

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



Операторы continue, break и return


Наиболее часто встречаются случаи более "мягкого" нарушения структурированной логики выполнения программы, которые нарушают ее "естественный" ход в текущем цикле или функции. Они реализуются операторами continue, break, return, которые рассматриваются как ограниченный вариант goto, а именно:



-continue -переход завершающую часть цикла;



-break -выход из внутреннего цикла;



-return -выход из текущего модуля (функции).

Хотя такие конструкции нарушают "чистоту" подхода, все они имеют достаточно простые структурированные эквиваленты, поэтому их использование все-таки предпочтительнее обычного goto. Рассмотрим пример использования оператора break и его эквивалент:


for (i=0; i&#60n; i++)
{ if (..a[i]...) break; ... }
if (i==n) A else B


int found;
for (found=0, i=0; i&#60n &#38&#38 !found; i++)
{ if (..a[i]..) found++; ... }
if (!found) A else B

При отсутствии в массиве элемента с заданным свойством выполняется A, в противном случае -B. Во втором фрагменте используется специальный признак для имитации оператора break.



Операторы перехода


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

.


оператор
goto mmm:
...
mmm: оператор

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



-оператор continue выполняет переход из тела цикла к его повторяющейся части, то есть досрочно завершает текущий шаг и переходит к следующему;



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



-оператор return производит досрочный выход из текущей функции. Он, кроме всего прочего, возвращает значение результата функции. Это его свойство будет рассмотрено в 2.4.


void F()
{
for (i=0; i&#60n; m1: i++)


{
if (A[i]==0) continue; //goto m1;

if (A[i]==-1) return; //goto m2;

if (A[i] &#60 0) break; //goto m3;

}
m2: ... продолжение тела функции
m3:
}

Операторы continue, break и return должны завершаться ограничителем ";" .

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



switch (выражение)
{
case константа1: последовательность операторов_1
case константа2: последовательность операторов_2
case константа3: последовательность операторов_3
default: последовательность операторов
}













Выполняется он следующим образом. Вычисляется значение выражения, стоящего в скобках. Затем последовательно проверяется его совпадение с каждой из констант, стоящих после ключевого слова
case и ограниченных двоеточием. Если произошло совпадение, то производится переход на идущую за константой простую последовательность операторов. Отсюда следует, что если не предпринять никаких действий, то после перехода к n-й последовательности операторов будет выполнена n+1 -я и все последующие. Чтобы этого не происходило, в конце каждой из них ставится оператор break , который в данном случае производит выход за пределы оператора switch . И последнее. Метка default обозначает последовательность, которая выполняется "по умолчанию", то есть когда не было перехода ни по какой другой ветви. Все эти нюансы отражены в примере, содержащем полный программный эквивалент оператора switch с использованием операторов goto :

.

switch (n) Эквивалент
if (n==1) goto m1;
{ if (n==2) goto m2;
case 1: n=n+2; break; if (n==4) goto m3;
case 2: n=0; break; goto md;
case 4: n++; break; m1: n=n+2; goto mend;
default: m2: n=0; goto mend;
n=-1; m3: n++; goto mend;
} md: n=-1;
mend: ...





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

.

switch (c) Эквивалент
{ if (c==' ') {...}
case ' ': ... break; if (c=='+') {...}
case '+': ... break; if (c=='-') {...}


case '-': ... break;
}







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

for (i=0; i&#60 20; i++) // Достигло ли 20-ти значение i

{ ... if (A[i] &#60 0) break; ... }
if (i==20) {...был естественный выход ...}
else {...был выход по break...}





Если несколько ветвей оператора switch должны содержать идентичные действия (возможно, с различными параметрами), то можно использовать общую последовательность операторов в одной ветви, не отделяя ее оператором break от предыдущих:



sign=0; // Ветвь для значения c, равного '+',

switch (c) // используется и предыдущей ветвью

{ // для значения '-'

case '-': sign=1;
case '+': Sum(a,b,sign); break;
}


Операторы простой последовательности


Прежде всего отметим основной " источник" операторов в программе - выражения. Любое из них, ограниченное символом ";", превращается в оператор. По аналогии символ ";", встречающийся в программе " сам по себе" обозначает ПУСТОЙ ОПЕРАТОР, не производящий никаких действий. Пустой оператор используется там, где по синтаксису требуется наличие оператора, но никаких действий производить не нужно. Например, в цикле, где все необходимое делается в его заголовке


for (i=0; i&#60n; i++) s = s + A[i]; // Обычный цикл


for (i=0; A[i]!=0 &#38&#38 i&#60n; i++); // Цикл с пустым оператором

Любая последовательность операторов, заключенная в фигурные скобки ({}), может выступать в любой синтаксической конструкции как один СОСТАВНОЙ ОПЕРАТОР (БЛОК). В начале его могут быть определены собственные переменные блока, действие которых не распространяется за его пределы, а время существования совпадает с временем его выполнения. Операторы, составляющие блок, выполняются последовательно друг за другом. Естественно, что в языке программирования этому соответствует обычное последовательное расположение операторов в тексте программы.

716edd1253ebe5e81aa7a426fbb2bc72010009000003c304000009001f00000000001400000026060f001e00ffffffff040014000000576f72640e004d6963726f736f667420576f7264050000000b020000ffff050000000c02be00ae011c000000fb021000070000000000bc02000000000000000253797374656d0000080000000c008a0100000a00060000000c008a0100000a00040000002d010000050000000201010000001c000000fb02ecff0000000000009001000000000440001254696d6573204e657720526f6d616e00db7ced77d067ef772a020af700000a00040000002d01010005000000090200000000050000000201010000001000000026060f001600ffffffff00000000000000000000ab010000bc00000007000000fc020000ffffff000000040000002d01020008000000fa0200000100000000000002040000002d010300070000001b042a006e000100000007000000fc020000ffffff000000040000002d01040004000000f001020008000000fa0200000000000000000000040000002d01020004000000f0010300030000001e000700000016042000610008000c00050000000201010000001c000000fb02ecff000000000000bc020000000004400022417269616c0000004d030aabd27ced77db7ced77d067ef774d030aab00000a00040000002d01030005000000140209002500050000002e01010000000e000000320a090025000200040000000000ad01bf00613d0b000c00050000002e01000000000500000014020000000005000000140209003c00050000002e01010000000d000000320a09003c000100040000000000ad01bf00353d0b00050000002e01000000000500000014020000000005000000020101000000040000002701ffff07000000fc020000ffffff000000040000002d01050008000000fa0200000100000000000002040000002d010600070000001b0479006e0050000000040000002d01040004000000f0010500040000002d01020004000000f0010600030000001e000700000016047000610058000c0005000000020101000000040000002d0103000500000009020000000005000000140259001b00050000002e010100000013000000320a59001b000500040000000000ad01bf00623d612a32000c000c000b0008000b00050000002e0100000000050000001402027f34eb05000000020101000000040000002701ffff07000000fc020000ffffff000000040000002d01050008000000fa0200000100000000000002040000002d010600070000001b04be006e0095000000040000002d01040004000000f0010500040000002d01020004000000f0010600030000001e00070000001604b40061009c000c0005000000020101000000040000002d010300050000000902000000000500000014029d001900050000002e01010000000e000000320a9d0019000200040000000000ad01bf00613d0b000c00050000002e0100000000050000001402027f34eb0500000014029d003000050000002e010100000010000000320a9d0030000300040000000000ad01bf00612b312a0b000c000b00050000002e01000000000500000014020000000005000000020101000000040000002701ffff1000000026060f001600ffffffff00003000000027000000420000005200000008000000fa0200000100000000000000040000002d01050007000000fc020100000000000000040000002d0106000800000025030200390028003900450008000000fa0205000100000000000000040000002d01070004000000f001050007000000fc020000000000000000040000002d0105000a00000024030300310043003900500040004300040000002d010200040000002d01040004000000f00105000800000026060f000600ffffffff01001000000026060f001600ffffffff00003000000077000000420000009700000008000000fa0200000100000000000000040000002d010500040000002d01060008000000250302003900780039008a00040000002d01070004000000f001050007000000fc020000000000000000040000002d0105000a00000024030300310088003900950040008800040000002d010200040000002d01040004000000f00105000800000026060f000600ffffffff010007000000fc020000ffffff000000040000002d01050008000000fa0200000100000000000002040000002d010800070000001b048500ad011900be00040000002d01040004000000f0010500040000002d01020004000000f0010800030000001e000700000016047b00a0012000ca0005000000020101000000040000002d010300050000000902000000000500000014022000ca001c000000fb02ecff000000000000bc02000000cc04400022417269616c00000038050a28d27ced77db7ced77d067ef7738050a2800000a00040000002d010500050000002e01010000000e000000320a2000ca000200040000000000ad01bf00d2e50c000b00050000002e0100000000040000002d01030004000000f0010500050000001402027f34eb0500000014022000e1001c000000fb02ecff000000000000bc02000000cc04400022417269616c00000038050a29d27ced77db7ced77d067ef7738050a2900000a00040000002d010500050000002e01010000001f000000320a2000e1000d00040000000000ad01bf00eaf1f220eff0eee3f0e0ececfb000a000b000a0007000b000c000c0009000c000b000e000d001000050000002e0100000000040000002d01030004000000f00105000500000014020000000005000000140220007501050000002e01010000000d000000320a200075010100040000000000ad01bf003a000800050000002e01000000000500000014020000000005000000020101000000050000000201010000000500000014023700ca00050000002e010100000011000000320a3700ca000400040000000000ad01bf00613d353b0b000c000a000800050000002e01000000000500000014020000000005000000020101000000050000000201010000000500000014024e00ca00050000002e010100000014000000320a4e00ca000600040000000000ad01bf00623d612a323b0c000c000b0008000a000800050000002e01000000000500000014020000000005000000020101000000050000000201010000000500000014026500ca00050000002e010100000014000000320a6500ca000600040000000000ad01bf00613d612b313b0b000c000b000c000a000800050000002e010000000005000000140200000000050000000201010000000500000002010100000005000000020101000000040000002701ffff040000002d01000003000000000000


for (i=0; i&#60n-1; i++)
{ // Составной оператор - блок


int c;
c = A[i];
A[i]=A[i+1];
A[i+1]=c;
}

.


выражение ; - оператор
; - пустой оператор
{ оператор ... оператор } - составной оператор (блок)

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



Определение дескриптора открытого файла в stdio.h



.
typedef struct
{
//...
unsigned flags; // Флаги состояния ---------------¬
char fd; // Номер открытого файла (handle) ¦
unsigned char hold; // Возвращенный символ ¦
short bsize; // Размер внутреннего буфера ¦
unsigned char *buffer,*curp; ¦
... // и его указатели ¦
} FILE; ---- Определение типа "Дескриптор файла" ¦
(описатель потока) ¦
---- Флаги состояния - биты, определенные через define ----
¦
_F_RDWR - открыт для чтения и записи
_F_READ - открыт только для чтения
_F_WRIT - открыт только для записи
_F_BUF - имеет динамически выделенный буфер данных
_F_LBUF - построчная буферизация
_F_ERR - обнаружена ошибка при выполнении операции
_F_EOF - обнаружен конец файла при выполнении операции
_F_BIN - двоичный (прозрачный) режим
_F_IN - выполняется операция чтения
_F_OUT - выполняется операция записи
_F_TERM - файл открыт на терминале



Определение функции


Функция состоит из двух частей: ЗАГОЛОВКА ФУНКЦИИ, создающего " интерфейс" функции к внешнему миру, и ТЕЛА ФУНКЦИИ, реализующего заложенный и нее алгоритм с использованием внутренних локальных данных. Вместе заголовок и тело составляют ОПРЕДЕЛЕНИЕ ФУНКЦИИ.


//------------------------------------------------------bk15-01.cpp


// Результат функции


// | Имя функции


// | |


int sum(int A[], int n)
// -------------- Формальные параметры


//---- ------------------ Тело функции (блок)


{
int s,i; // Локальные(автоматические) переменные блока


for (i=s=0; i&#60n; i++) // Последовательность операторов блока


s +=A[i];
return s ; // Значение результата в return


}

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


void main()
{
int ss, x, B[10]={ 1,6,3,4,5,2,56,3,22,3 };
ss = x + sum(B,10) ;
// Вызов функции : ss = x + результат sum(фактические параметры )


}

Интерфейс функции состоит из формальных параметров (вход) и результата (выход).

ФОРМАЛЬНЫЕ ПАРАМЕТРЫ -- это собственные переменные функции, которым при ее вызове присваиваются значения фактических параметров.

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

контексте (окружении) выражения, где был произведен ее вызов

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


int sum(... // Результат - целая переменная


char *FF(... // Результат - указатель на символ

Значение переменной-результатa устанавливается в операторе return , который производит это действие наряду с завершением выполнения функции и выходом из нее.
Между ключевым словом return и ограничивающим символом ";" может стоять любое выражение, значение которого и становится результатом функции. Если вспомнить еще и о преобразованиях типов, то при таком "присваивании" результата таковое должно производиться от типа, соответствующего выражению к типу результата функции:

double FF()
{ int nn; // Эквивалент

return (nn+1) ; // FF = (
double)(nn + 1)

Имеется специальный пустой тип результата -
void , который обозначает, что функция не возвращает никакого результата и, соответственно, не может быть вызвана внутри выражения. Оператор return в такой функции также не содержит никакого выражения:

void Nothing() { return; }

Вызов функции выглядит как имя функции, за которым в скобках следует список фактических параметров.

ФАКТИЧЕСКИЕ ПАРАМЕТРЫ - - переменные, константы или выражения, значения которых при вызове присваиваются соответствующим по списку формальным параметрам.



Тело функции представляет собой уже известную нам синтаксическую конструкцию -блок. Это простая последовательность операторов, заключенная в фигурные скобки. После открывающейся скобки в блоке могут стоять определения переменных. Это ЛОКАЛЬНЫЕ ПЕРЕМЕННЫЕ блока (в данном случае тела функции). Они обладают следующими свойствами:


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


-локальные переменные могут использоваться только в том блоке, в котором они определены. Это значит, что за пределами блока они "не видны";


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



Локальные переменные в теле функции обозначаются в Си термином АВТОМАТИЧЕСКИЕ ПЕРЕМЕННЫЕ.


Определение переменной внутри выражения


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


for (int i=0; i&#60 10; i++) ...

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



Определение типа данных (спецификатор typedef)


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

Спецификатор typedef имеет синтаксис контекстного определения типа данных, в котором вместо имени переменной присутствует имя вводимого типа данных. Рассмотрим пример:


// Синтаксис контекстного определения типа для переменной PSTR


typedef char *PSTR; // PSTR - имя производного типа данных.

Тип данных PSTR определяется в контексте как указатель на символ (строку).


PSTR p,q[20],*pp;



Переменная p типа PSTR, массив из 20 переменных типа PSTR и указатель типа PSTR представляют собой указатель на строку, массив указателей на строку и указатель на указатель на строку.


long l;
*((PSTR)&#38l + 2) = 5;



Указатель на переменную типа long преобразуется к типу указатель на строку.

В принципе, использование оператора typedef характеризует скорее стиль программирования, нежели насущную необходимость. Дело в том, что один и тот же тип данных в Си может использоваться для работы с различными структурами данных (особенно это касается указателей). Например, тип char* может использоваться для обозначения:



-указателя на отдельный символ (адрес символа);



-указателя на массив символов (строку);



-указателя на область байтов (начальный адрес).

С помощью typedef программистами могут устанавливать соглашения по обозначению тех или иных типов и связанных с ними структур данных. Например, тип PSTR используется для обозначения указателя на строку символов, заканчивающуюся символом '\0'. Заметим, что в этом случае никаких дополнительных действий по проверке корректности структур данных транслятором не производится: тип данных PSTR только улучшает читаемость программы.



Основные характеристики двоичных файлов


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

ЗАПИСЬ - - стандартная единица хранения данных в файле .

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

ЗАПИСИ ФИКСИРОВАННОЙ ДЛИНЫ -- все записи файла представляют собой переменные одного типа и имеют фиксированную для данного файла размерность .

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

ПРОИЗВОЛЬНЫЙ ДОСТУП -- если записи файла могут быть прочитаны в любом порядке (вследствие особенностей структуры данных, хранящейся в файле), то такой файл называется файлом произвольного (прямого) доступа .

ПОСЛЕДОВАТЕЛЬНЫЙ ДОСТУП -- если файл по своей физической организации (устройство ввода-вывода) или по характеру структуры данных допускает просмотр записей в последовательном порядке, то такой файл называется файлом последовательного доступа



Особенности языка Си++


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



Особенности программирования рекурсивных функций


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


.void main() void F() void F() void F()
{ { { {
F(); ..if()F(); ...if()F(); ...if()F();
} } } }

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

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



-формальные параметры рекурсивной функции представляют начальное состояние для текущего шага процесса;



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


-автоматические переменные представляют внутренние характеристики процесса на текущем шаге его выполнения;


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

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


- в стеке резервируется место для формальных параметров, в которые записываются значения фактических параметров. Обычно это производится в порядке, обратном их следованию в списке ;


- при вызове функции в стек записывается точка возврата - адрес той части программы, где находится вызов функции ;


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

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



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

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

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


Особое число


Число 1997 имеет особые свойства. Будучи простым, оно при разделении его цифр на две любые части также дает простые числа (199 и 7, 19 и 97, 1 и 997). Найти другие подобные числа в диапазоне от 1000 до 2000.

l Идея : Поскольку проверка на то, является ли число простым, производится в нескольких случаях, то ее необходимо оформить в виде функции. Сущность алгоритма состоит в последовательной проверке всех значений от 1000 до 2000 на предмет соблюдения указанного свойства (полный перебор). Разделить число на две части можно, используя частное и остаток от его деления на степени 10, то есть 10,100,1000.

l Фактыl :

1. Алгоритм проверки - является ли число простым, приведен в тестовых вопросах предыдущего параграфа. Число a простое, если оно не делится ни на одно из чисел в диапазоне от 2 до a-1 . Это свойство всеобщности проверяется циклом с break.


for (i=2; i&#60a; i++) if (a%i==0) break;
if (a==i)... // выход по a==i без break - не было ни одного деления

2. . Этот фрагмент оформляется в виде функции, возвращающей логическое значение 0 /1.


int PR(int a)
{ int i;
for (i=2; i&#60a; i++) if (a%i==0) break;
if (a==i) return 1; else return 0;
}

3. Усовершенствование : завершить функцию с результатом 0 можно сразу же по обнаружении факта деления нацело. Кроме того, функция не проверяет значение 1, которое также является простым числом.


int PR(int a)
{ int i;
if (a==1) return 1;
for (i=2; i&#60a; i++) if (a%i==0) return 0;
return 1;
}

4. Сам процесс поиска состоит в полном переборе значений в заданном диапазоне.


void main()
{
for (int n=1000; n&#60 2000; n++)
{ ... Удовлетворяет ли n - условиям
if (удовлетворяет ) cout &#60&#60 n &#60&#60 endl;
}
}

5. Разделить число n на две части и проверить, являются ли они простыми, можно, используя частное и остаток от его деления на степень 10, например


int v=100;
n / v - число без двух младших цифр
n % v - число из двух младших цифр

6. Получить подряд степени числа 10 можно следующим циклом :



for (int v=10; v&#60n; v*=10) { ...n/v...n%v...}

7. Проверить, являются ли простыми все части, на которые делится число n, можно с помощью цикла проверки свойства ВСЕОБЩНОСТИ

for (int v=10; v&#60=n; v*=10)
{
if (!PR(n/v)) break;
if (!PR(n%v)) break;
}
if (v&#62n) ... // Не было выхода по break (свойство : число простое )







8. Оператор
continue досрочно завершает шаг цикла и переходит к следующему, его можно использовать, если в результате проверки оказывается, что число n не удовлетворяет одному из условий. Тогда последовательность конструкций if ( условие не соблюдается ) continue; позволяет организовать " сито" проверок

{
if (!PR(n)) continue; // пропустить - число не простое

for (int v=10; v&#60=n; v*=10)
{
if (!PR(n/v)) break;
if (!PR(n%v)) break;
}
if (v&#60=n) continue; // пропустить - был выход по break

cout &#60&#60 n &#60&#60 endl; // прошли сквозь сито - найдено число

}

Практически программа уже написана, остается составить ее из частей.




Отложенное прерывание ( Fork-обработка)


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


&#35define N 100
int FIFO[N]; // Циклическая очередь данных в массиве


int fst=0,lst=0; // Указатели начала и конца очереди


void interrupt FORK(...)
{
int data=inportb(...); // Читать данные


outportb(...); // Запустить процесс


// подготовки следующих


int busy=(fst!=lst); // Признак busy - очередь


// была не пуста


FIFO[lst]=data; // Поместить данные


// в циклическую очередь


lst = (lst+1)%N; // Продвинуть указатель


outportb(0x20,0x20); // Разрешить обработку


// прерываний контроллеру


if (busy) return; // Очередь не пуста - выполняется


// " отложенная обработка" данных


// от предыдущих прерываний - выйти


busy++;
while(fst!=lst) // Иначе - войти в режим


{ // " отложенной обработки"


int fdata=FIFO[fst];
fst = (fst+1)%N; // Извлечь данные из начала очереди


enable(); // " Отложенную обработку" производить


fdata ... // при разрешенном прерывании


disable(); // На время изменения и проверки общих


} // переменных прерывание запрещать


busy--;
}

Заметим, что в данном примере, как и во всех случаях синхронизации процессов через общие переменные, проверка и изменение этих переменных должна производиться при запрещенном прерывании. В данном примере это касается переменных fst, lst, характеризующих очередь полученных данных.

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