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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

---------------------------------------------------------------¬
¦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);

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

//------------------------------------------------------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); // Возвратить один из концов

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

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

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

.

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----------------

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

- Информатика (семестр 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 теста), а также тестирование по " Вопросам без ответов" .

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

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

- Объектно-ориентированное программирование (семестр 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 .

По всем вопросам обращайтесь к автору курса Романову Евгению Леонидовичу 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. Это соответствует общему принципу защиты данных класса от вмешательства извне.

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

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

Элемент с меткой 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 char *Name()=0; // Возвращает имя типа объекта

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

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

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

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

};

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

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

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

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

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

}

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

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";

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

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

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

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

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

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

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

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

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

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

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

//------------------------------------------------------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);
}

Объединения

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 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); // последовательность не найдена

}

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

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

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

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

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

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

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

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

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

В самом же модуле, где функция определена, ее область действия распространяется от точки определения до конца файла. Если же требуется вызвать функцию ранее ее определения по тексту, то она также должна быть объявлена, но, возможно, и без слова 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);

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

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

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

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

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

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

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

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

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

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

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

{ //

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

//------------------------------------------------------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;
// Двигаться по списку, пока он не кончится, либо пока

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

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

//------------------------------------------------------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);
}}

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

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

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

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

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);
};

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 до использования

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

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)

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

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)

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

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

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

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

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

.

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

.

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

.

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

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

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

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

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

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

-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 mmm:
...
mmm: оператор

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(... // Результат - указатель на символ

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

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

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

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

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

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

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

PSTR p,q[20],*pp;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Особое число

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

l Фактыl :

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 можно следующим циклом :

Отложенное прерывание ( 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, характеризующих очередь полученных данных.

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