Синтаксис указателя на функцию

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

int (*pf)(); // без контроля параметров вызова

int (*pf)(int, char*); // с контролем по прототипу

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

В соответствии с принципом контекстного определения типа данных эту конструкцию следует понимать так: pf -переменная, при косвенном обращении к которой получается вызов функции, возвращающей int в качестве результата, то есть pf -адрес функции или указатель на функцию. Следует обратить внимание на то, что в определении указателя присутствует тип результата - указатель ссылается не на произвольную функцию, а только на одну из функций, дающих результат этого типа. Перед началом работы с указателем его необходимо назначить на соответствующий объект, в данном случае - на функцию. В синтаксисе Си выражение вида &#38имя_функции имеет смысл -начальный адрес функции или указатель на функцию. Кроме того, по аналогии с именем массива использование имени функции без скобок интерпретируется как указатель на эту функцию. Указатель может быть инициализирован и при определении. Таким образом, возможны следующие способы назначения указателей:

int INC( int а) { return a+1; }
extern int DEC(int);
int (*pf)(int);
pf = &#38INC;
pf = INC; // присваивание указателя

int (*pp)(int) = &#38DEC; // инициализация указателя

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

n = (*pf)(1) + (*pp)(n); // эквивалентно

n = INC(1) + DEC(n);

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

extern double sin(double);
extern double cos(double);
extern double tan(double);
char *names[] = { "sin","cos","tan",NULL};
double (*pf[])(double) = { sin, cos, tan};

Переменная pf представляет собой массив указателей на функции, инициализированный адресами библиотечных функций sin, cos и tan .

double call(char *pn,int val)
// pn - имя вычисляемой функции

// val - значение аргумента

{
int i;
for (i=0; names[i]!=NULL; i++)
if (strcmp(names[i],pn) == 0)
{ // Имя найдено

return ((*pf[i])(val));
} // вызов функции по i-му

return(0.); // указателю в массиве pf

}

Система меню

Меню верхней части экрана. Вход по F10 или по Alt+"Z", где Z - первая (прописная) буква в соответствующем слове меню (например, Alt+F --&#62 строка меню File) .

---------------------------------------------------------------¬
¦File Edit Search Run Compile Debug Project Options Window Help¦
L---------------------------------------------------------------

Некоторые команды меню выполняются при нажатии функциональных клавиш (F1-F10) в сочетании с Shift, Alt или Ctrl, что указано в соответствующих строках меню.

Система объектов, управляемых сообщениями

Здесь мы рассмотрим очень приближенную модель того, что реально происходит при программировании в объектно-ориентированных библиотеках, основанных на обработке сообщений (или событий) объектами программы. (Например, OWL в Windows или Turbo Vision в DOS) . Система объектов, управляемых сообщениями, должна включать в себя несколько классов, взаимодействие между которыми скрыто от внешнего наблюдателя :

-класс сообщений ;

-базовый класс объектов, управляемых сообщениями ;

-класс прикладной программы, единственный объект которого является аналогом main и реализует в своем методе run диспетчер сообщений и объектов.

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

// Класс сообщений -----------------------------------

&#35define ms_NULL 0 // Пустое сообщение

&#35define ms_KEYB 1 // Символ клавиатуры

&#35define ms_TICK 2 // Тик таймера

&#35define ms_MS_MOVE 3 // Перемещение мыши

&#35define ms_MS_CLICK 4 // Кнопка мыши

&#35define ms_ECHO 5 // Ответ объекта с this

&#35define ms_EXIT 6 // Завершение программы

&#35define ms_KILL 7 // Уничтожение объекта

&#35define ms_BORN 8 // Порождение объекта

class MS
{
public:
char code; // Код сообщения

int x,y; // Параметры сообщения

void *p; // Указатель на данные

MS(char,int,int,void *); // Констуктор - создать сообщение

~MS();
void clear()
{ code=ms_NULL; }; // " Очистить" сообщение

};

MS::MS(char c,int xx,int yy,void *q)
{ code = c; x = xx; y = yy; p = q; }

MS::~MS() {}

Система помощи

---------------------------------------------------------------¬
¦File Edit Search Run Compile Debug Project Options Window Help¦
L----------------------------------------------------------¦----
-------------------+---¬
Тематическое содержание Help ----------- Contents F1 ¦
Перечень ключевых слов (индекс) -------- Index Shift+F1 ¦
Контекстный поиск по текущему слову ---- Topic Search Ctrl+F1 ¦
Возвращение к предыдущей теме ---------- Previous Topic Alt+F1 ¦
Информация о Help ---------------------- Help on help ¦
L-----------------------

Смысл индексных переменных при работе с массивами

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

while() {... c=A[i]; i++; ...} // Извлечь очередной и продвинуть индекс

while() {... c=A[i++]; ...} // " Нежесткая" связь с циклом

for (...;...;i++) { ... c=A[i]; ... } // " Жесткая" связь с циклом

while() {... A[i]=c; i++; ...} // Записать очередной и продвинуть индекс

while() {... A[i++]=c; ...} // " Нежесткая" связь с циклом

for (...;...;i++)
{ ... c=A[i]; ... } // " Жесткая" связь с циклом

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

В качестве примера рассмотрим процесс разделения массива на две части относительно значения некоторого элемента - медианы. Пусть требуется переписать элементы массива A в массив B так, чтобы в выходном массиве слева относительно выбранного A[k] , называемого медианой, находились все элементы, меньшие данного, а справа - большие. Это можно сделать, если заполнять массив B с двух концов, перенося поочередно элементы из исходного массива. Для реализации такой программы потребуется три индекса и один цикл, поскольку имеет место три независимых " движения" по массивам, причем одно из них связано с циклом просмотра :

-" движение" по массиву A слева направо, связанное с циклом просмотра массива ;

-" движение" по массиву B в процессе заполнения его с левого конца ;

-" движение" по массиву B в процессе заполнения его с правого конца.

int A[20],B[20];
int i; // Движение по массиву A

int k1; // Движение по массиву B слева направо

int k2; // Движение по массиву B справа налево

int m; // Индекс элемента - медианы в А

for (i=0,k1=0,k2=19; i&#60 20; i++) // Просмотр A жестко связан с циклом

{
if (i==m) continue; // Медиану - пропустить

if (A[i]&#60A[m])
B[k1++]=A[i]; // Добавить слева

else
B[k2--]=A[i]; // Добавить справа

} // Движение по B не связано жестко с циклом

B[k1]=A[m]; // Перенести медиану в точку " встречи" k1-k2

Смысл операции присваивания

ПРИСВАИВАНИЕ -- это не только запоминание вычисленного значения. Переменная может использоваться также и как элемент логики алгоритма (к которой, как известно, относятся операторы) :

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

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

Непосредственная связь Связь через переменную-результат
Фрагмент 1 Фрагмент 1
if (...) goto mmm; if (...) k=1; else k=0;
... ...
Фрагмент 2 Фрагмент 2
mmm: ... if (k==1) ...

Смысл переменных

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

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

-затем определяется, какие для этого потребуются переменные, и какой " смысл" они будут иметь :

-в конце выбирается стандартный фрагмент алгоритма, который придает переменной этот смысл.

Перечислим наиболее простые варианты смысла переменных в программе:

l ПЕРЕМЕННАЯ - СЧЕТЧИК. Переменная считает количество появлений в программе того или иного события. В следующем примере переменная m подсчитывает количество положительных переменных в массиве. Заметим, что ключевой "фразой", определяющей смысл переменной-счетчика, является следующая :

for (...) { if (...удовлетворяет условию...) m++; }

for (i=0, m=0; i&#60n; i++) if(A[i]&#62 0) m++;

l ПЕРЕМЕННАЯ - ПРИЗНАК. Переменная фиксирует факт наступления какого-либо события в программе. Такая переменная принимает только логические значения 0 или 1 (событие наступило или не наступило). В одной точке программы проверяется это условие и устанавливается признак, в другой - наличие или отсутствие признака оказывает влияние на логику работы программы, в третьей - признак сбрасывается. Простой пример - суммирование элементов массива до первого отрицательного включительно:

for (s=0, k=0, i=0; i&#60n &#38&#38 k==0; i++)
{
s+=A[i];
if (A[i]&#60 0) k=1;
}

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

for (s=0, i=0; i&#60n; i++)
{
s+=A[i];
if (A[i]&#60 0) break;

}

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

for (i=0,s=0,k=0; i&#60 10; i++)
if (A[i]&#60 0) k=1;
else
{ if (k==1) s++; k=0; }

Несложно догадаться, что " смысл" переменной k - текущий элемент массива является отрицательным, а " смысл" s - счетчик. Счетчик увеличивается, если выполняется ветка else - текущий элемент массива положителен, и в то же самое время k==1 - соответствует отрицательному значению элемента массива. Преодолеть это противоречие можно, если учесть, что признак проверяется в этой ветке до его изменения, то есть l проверяется его значение, оставшееся от предыдущего шага. Следовательно. фрагмент подсчитывает количество пар элементов вида " отрицательный - положительный" .

Еще один пример - обнаружение комментариев в строке. Признак com в процессе переписывания строки устанавливается в 1, если программа находится " внутри комментария" .

void copy(char dst[], char src[])
{ int i,com=0,j=0;
for (com=0,i=0; src[i]!=0; i++)
if (com)
{ // внутри комментария

if (src[i]== * &#38&#38 src[i+1]== / )
{ com=0; i++; } // не в комментарии, пропустить символ

}
else
{ // вне комментария

if (src[i]== / &#38&#38 src[i+1]== * )
{ com=1; i++; } // в комментарии, пропустить символ

else
dst[j++] = src[i]; // переписать символ в выходную строку

}
dst[j]=0; }

for (s=0,...;...;...) { получить k; s=s+k; }

Он дает переменной s единственный " смысл" - переменная накапливает сумму значений k , полученных на каждом из шагов выполнения цикла. Для доказательства этого факта можно привлечь метод математической индукции : действительно, если на очередном шаге s содержит сумму, накопленную на предыдущих шагах, то после выполнения s=s+k она будет содержать сумму уже с учетом текущего шага. Типичный пример - сумма элементов массива.

for (s=0,i=0; i&#60 10; i++) s=s+A[i];

То же самое можно сказать и о произведении, которое накапливается следующим фрагментом :

for (s=1,...;...;...;) { Получить k; s=s*k; }

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

for (s=0,i=0; i&#60n; i++) // Сумма элементов массива

s+=A[i];

for (s=0,i=0; i&#60n &#38&#38 A[i]&#62=0; i++) // Сумма элементов массива до первого

s+=A[i]; // отрицательного

for (s=0,i=0; i&#60n; i++) // Сумма положительный элементов

if (A[i]&#62 0) s+=A[i]; // массива

for (s=0,x=0; x&#60=1; x+=0.1) // Сумма значений функции sin

s+=sin(x); // в диапазоне 0..1 с шагом 0.1

for (s=0,...;...;...) { получить k; if (k&#62s) s=k; }

Для доказательства этого факта можно привлечь метод математической индукции : действительно, если на очередном шаге s содержит максимальное значение, полученное на предыдущих шагах, то после выполнения if (k&#62s) s=k; она будет содержать такой же максимум, но уже с учетом текущего шага. Типичный пример - нахождение максимального элемента массива.

for (s=0,i=0; i&#60 10; i++) if (A[i]&#62s) s=A[i];

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

for (i=1,k=0; i&#60 10; i++) if (A[i]&#62A[k]) k=i;

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

for (i=0,k=-1; i&#60 10; i++) // k=-1 - нет элемента, принятого за минимальный

{ if (A[i]&#60 0) continue;
if (k==-1 || A[i]&#60A[k]) k=i;
}

Смысл переменных при завершении циклов

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

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

for (i=0; i&#60n; i++) if (A[i]&#60 0) break;
if (i==n) ...

В данном примере мы имеем два варианта завершения цикла. В первом случае, который зафиксирован в заголовке цикла, цикл завершается по достижении переменной i значения n . Альтернативный выход из цикла по break происходит при обнаружении отрицательного значения элемента массива. Естественно, если он происходит, то это будет раньше, чем естественное завершение. Тогда проверка (i==n) на самом деле имеет следующий "смысл": был или не был обнаружен в массиве отрицательный элемент. Если условие соблюдается, то не был. Если не соблюдается, то значение i содержит индекс первого встреченного отрицательного элемента. Таким образом, фрагмент цикла, содержащий break , проверяет выполнения свойства , обратного указанному в операторе if СВОЙСТВО " ВСЕОБЩНОСТИ" для всех элементов массива. Или, наоборот, проверяет СВОЙСТВО " СУЩЕСТВОВАНИЯ" элемента массива, для которого справедливо данное условие.

Смысл переменных в структурах данных

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

l ПОСЛЕДОВАТЕЛЬНОСТЬЮ называется упорядоченное множество переменных, количество которых может меняться. В идеальном случае последовательность может быть неограниченной, реально же в программе имеются те или иные ограничения на ее длину. Рассмотрим самый простой способ представления последовательности. Если переменные принимают целые положительные значения, то их последовательность может быть размещена в обычном массиве. Для того, чтобы определить текущее количество элементов последовательности можно поступить двумя способами :

-использовать дополнительную переменную - счетчик числа элементов ;

-добавлять каждый раз в качестве обозначения конца последовательности дополнительный элемент с особым значением - признак конца последовательности, например нулевой (ОГРАНИЧИТЕЛЬ ПОСЛЕДОВАТЕЛЬНОСТИ).

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

// создать пустую последовательность

A[0]=0;

// найти конец последовательности

for(n=0; A[n]!=0; n++);

// добавить в конец последовательности

for(n=0; A[n]!=0; n++);
A[n]=c; A[n+1]=0;

// включить в последовательность под заданным номером n

for (i=0; A[i]!=0; i++);
for (; i&#62=n; i--) A[i+1]=A[i];
A[n]=c;

// удалить из последовательности под заданным номером n

Смысл выражений в арифметических задачах

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

n % 10... // младшая цифра числа n

n=n/10; // отбросить младшую цифру n

for (i=0; n!=0; i++, n/=10)
{ ... n%10... } // получить цифры числа в обратном порядке

n%i==0... // n делится нацело на i

s = s*10 + k; // добавить цифру k к значению числа s

Сортировка и поиск

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

Сортировка подсчетом

l Идея алгоритма : если для элемента массива A[i] подсчитано количество элементов, меньших его, например, cnt то это значение будет являться местом размещения в выходном массиве. Действительно, cnt элементов будут лежать слева.

l Фактыl :l

1. Потребуется два массива, входной A[ ] и выходной B[ ] , соответственно - формальные параметры функции, которая выполняет сортировку, а также их размерность - n .

void sort(int A[], int B[], int n)
{...}

2. Действие, связанное с подсчетом и перенесением элемента массива будет производиться для каждого из элементов массива A[ ], можно в любом порядке :

for (int i=0; i&#60n; i++)
{ подсчитать cnt для A[i] и перенести его в B[] }

3. Если для переменной cnt известен смысл - счетчик элементов, меньших текущего, то процесс перенесения значения из A[ ] в B[ ] можно записать, даже не зная способа его получения:

B[cnt]=A[i];

4. Для переменной-счетчика используется известный контекст :

for(cnt=0;...) { if(...) cnt++; }

5. Для подсчета количества значений, меньших A[i] нужно просмотреть в цикле все значения массива. Отдельный цикл требует нового индекса :

for (cnt=0,j=0; j&#60n; j++) if (A[j] &#60 A[i]) cnt++;

6. Уточнение. Если в массиве есть два одинаковых значения, то они попадут в одну и ту же ячейку выходного, поскольку счетчики их будут одинаковы. Следующая же ячейка окажется пуста. Это можно исправить, если, например, подсчитывать также и равные значения, но расположенные справа от текущего. Смысл фразы " справа от i- го" выражается соотношением j&#62i. Тогда фрагмент подсчета примет вид :

for (cnt=0,j=0; j&#60n; j++)
if (A[j] &#60 A[i] || A[j]==A[i] &#38&#38 j&#62i) cnt++;

Собранная из фрагментов программа будет иметь вид (не забывайте определения переменных) .

void sort(int A[], int B[], int n) // 1

{
for (int i=0; i&#60n; i++) // 2

{
for (cnt=0,j=0; j&#60n; j++) // 4,5,6

if (A[j] &#60 A[i] || A[j]==A[i] &#38&#38 j&#62i) cnt++;
B[cnt]=A[i]; // 3

}
}

Путем сравнения всех пар элементов массива для каждого из них подсчитывается количество элементов, меньших его. Это дает новое местоположение этого элемента в выходном массиве. Трудоемкость алгоритма -n*n/2. Текст ищите в " Вопросах без ответов " .

Сортировка слиянием

ОДНОКРАТНОЕ СЛИЯНИЕ. Очевидно, что если из упорядоченных последовательностей брать по одному очередному элементу из каждой, затем выбирать из них минимальный и переносить его, то выходная последовательность будет упорядоченной. Отсюда возможен самый простой способ однократного слияния : массив разбивается на n частей, каждая из них сортируется независимо, а затем отсортированные части объединяются слиянием. Текст ищите в " Вопросах без ответов " .

ЦИКЛИЧЕСКОЕ СЛИЯНИЕ. Первоначально массив разделяется на n последовательностей. Затем в каждой из них выбирается по одному элементу (первому) в таком порядке, чтобы получилась упорядоченная группа из n элементов, которая запоминается в выходной последовательности (слияние). Выходная последовательность будет состоять из групп по n элементов, каждая из которых упорядочена. Далее файл опять распределяется, но уже группами по n элементов по тем же самым n входным последовательностям. В результате слияния образуются упорядоченные группы из n*n элементов. Затем процесс повторяется группами по n*n*n и т.д.. В качестве примера рассмотрим случай с n=2 (двухпутевое слияние). Для простоты будем считать размерность сортируемого массива кратной 2.

void sort(int in[],int n, int v1[], int v2[])

{
int step,m,k0;
for (m=n; m!=1; m/=2) // Проверка на степень 2

if (m%2 !=0) return;
for (step=1 step &#60n; step *=2) // Слияние группами по

{ // step = 1,2,4...n/2

for (k0=0; k0 &#60 n/2; k0 += step)
// Распределить in[], начиная с 2*k0, группy по step

// элементов в v1 и в v2, начиная с k0

for (k0=0; k0 &#60 n; k0 += step*2)
// "Слить" по step элементов из v1 и v2, начиная с k0,

// в in[], начиная с 2*k0

}
}

Часть алгоритма, которая распределяет, начиная с 2*k0 из массива in группу из step элементов в массив v1 и такую же группу в v2, в комментариях не нуждается:

int i;
for (i=0, i&#60step; i++) v1[k0 + i] = in[2*k0 + i];
for (i=0, i&#60step; i++) v2[k0 + i] = in[2*k0 + step + i];

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

int i1,i2;
for (i1=i2=0; i1+i2 &#60 2*step; )
{
if (i1==step)
{ in[2*k0+i1+i2] = v2[k0+i2]; i2++; }
else
if (i2==step)
{ in[2*k0+i1+i2] = v1[k0+i1]; i1++; }
else
if (v1[k0+i1] &#60 v2[k0+i2])
{ in[2*k0+i1+i2] = v1[k0+i1]; i1++; }
else
{ in[2*k0+i1+i2] = v2[k0+i2]; i2++; }
}

Некоторая сложность алгоритма простого слияния состоит в слежении за группами, в результате чего получаются такие " дикие " индексы массивов. ПОРАЗРЯДНАЯ РАСПРЕДЕЛЯЮЩАЯ СОРТИРОВКА работает с двумя последовательностями целиком, не выделяя в нем групп. Слияние осуществляется как обычно, путем выбора минимального из двух текущих элементов последовательностей. Зато распределение происходит на первом шаге по значению старшего значащего бита (0/1), и по значению каждого следующего бита на очередном шаге. Алгоритм при этом упрощается настолько, что приведен в "Вопросах без ответов...".Распределение можно вести одновременно для нескольких соседних битов, при этом количество выходных массивов будет равно соответствующей степени 2.

Сортировка выбором

В массиве выбирается меньший элемент из 0..n и обменивается с нулевым. Затем то же самое повторяется с элементами от 1 до n-1 и т.д.. Трудоемкость алгоритма - n*n/2. Сортировка выбором естественно выглядит при работе со списками. Текст ищите в " Вопросах без ответов " .

Сортировки разделением

Сортировки, основанные на принципе разделения массива разделяют его на две части относительно некоторого значения, называемого МЕДИАНОЙ. Сами части не упорядочены, но обладают таким свойством, что элементы в левой части меньше медианы, а элементы правой - больше. Благодаря такому свойству эти части можно сортировать независимо. Для этого нужно вызвать ту же самую функцию сортировки, но уже не по отношению к массиву, а к его частям. Функции, вызывающие сами себя, называются рекурсивными и рассмотрены в 5.4. Рекурсивный вызов продолжается до тех пор, пока очередная часть массива не станет содержать единственный элемент:

void sort(int in[], int a, int b)
{
int i;
if (a==b) return;
// Разделить массив в интервале a..b

// на две части a..i-1 и i+1..b

// A[i] - медиана интервала

sort(in,a,i-1); sort(in,i+1,b);
}

В так называемой БЫСТРОЙ СОРТИРОВКЕ разделение производится с использованием оригинального алгоритма. Специфика алгоритма " быстрой сортировки" состоит в выполнении разделения на основе обмена. Сравнение элементов производится с концов массива (i=a, j=b) к середине (i++ или j--), причем "укорочение" происходит только с одной из сторон. После каждой перестановки меняется тот конец, с которого выполняется "укорочение". В результате этого массив разделяется на две части относительно значения первого элемента in[a] , который и становится медианой.

//------------------------------------------------------bk35-04.cpp

//-------"Быстрая" сортировка

void sort(int in[], int a, int b)
{
int i,j,mode;
if (a&#62=b) return;
for (i=a, j=b, mode=1; i &#60 j; mode &#62 0 ? j-- : i++)
if (in[i] &#62 in[j])
{
int c;
c = in[i]; in[i] = in[j]; in[j]=c;
mode = -mode;
}
sort(in,a,i-1); sort(in,i+1,b);
}

Очевидно, что медиана делит массив на две неравные части. Вышеуказанный алгоритм разделения можно выполнить итерационно, применяя его к той части массива, которая содержит его середину (по аналогии с двоичным поиском). Тогда в каждом шаге итерации медиана будет сдвигаться к середине массива. Другой пример обменной сортировки на основе разделения -ПОРАЗРЯДНАЯ СОРТИРОВКА - будет рассмотрен в 4.8.

Сортировки вставками

ПРОСТАЯ ВСТАВКА: определяется место в отсортированной части массива, куда должен помещаться элемент. Элементы от данной позиции сдвигаются вверх и на освободившееся место помещается элемент. Трудоемкость алгоритма при линейном поиске -n*n/4. Если используется двоичный поиск для определения места элемента, то трудоемкость алгоритма составляет n*log(n). Однако эта трудоемкость не учитывает затрат на перемещение элементов при сдвиге. Естественным образом простые вставки выполняются в линейных списках. Текст ищите в " Вопросах без ответов " .

ВСТАВКА ПОГРУЖЕНИЕМ: очередной элемент путем ряда обменов " погружается " до требуемой позиции в уже упорядоченную часть массива. Текст ищите в " Вопросах без ответов " .

Существенными в сортировках вставками являются затраты на обмены или сдвиги элементов. Для их уменьшения желательно сначала производить погружение с большим шагом, сразу определяя элемент "по месту". Этим отличается СОРТИРОВКА ШЕЛЛА: исходный массив разбивается на n частей, в каждую из которых попадают элементы с шагом m, начиная от 0,1,...,m-1 соответственно, то есть

.
0 , m , 2m , 3m ,...
1 , m+1, 2m+1, 3m+1,...
2 , m+2, 2m+2, 3m+2,...

Каждая часть сортируется отдельно с использованием алгоритма вставок. Затем выбирается меньший шаг, и алгоритм повторяется. Шаг может быть выбран равным степеням 2, например 64,32,16,8,4,2,1. Последняя сортировка выполняется с шагом 1.

Составные части языка программирования

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

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

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

-непосредственно операции преобразования данных ;

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

-вызов (выполнение) модулей (процедур, функций) ;

-присваивание, то есть запоминание значения переменной ;

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

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

-последовательность действий (блок) ;

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

-повторяющаяся конструкция (цикл) ;

-переход.

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

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

Состояние потока

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

enum ios::io_state
{
goodbit = 0x00, // Ошибок нет

eofbit = 0x01, // Обнаружен признак конца файла

failbit = 0x02, // Ошибка форматирования или

// преобразования данных

badbit = 0x04, // Серьезная ошибка (буферизация,

// чтение после конца файла и т.д.)

hardfail = 0x08 // Аппаратная ошибка

};

Функции управления состоянием в класса ios :

int rdstate(); // Чтение текущего состояния

int eof(); // Проверка флага eof

int fail(); // Проверка badbit | failbit | hardfail

int bad(); // Проверка badbit | hardfail

int good(); // Проверка на отсутствие ошибок

int clear(int=0); // Установка флагов ошибки, по

// умолчанию - очистка всех

operator void*(); // Преобразование к типу void*,

// возвращает NULL, если fail()==1

int operator!(); // Возвращает 1, если fail()==1

Последние переопределения позволяют проверять наличие ошибок в потоках в виде :

if (cout) ... или if (!cout) ...

Состояние процесса

Если считать, что процесс может выполняться с собственной скоростью, независимо (асинхронно) от аналогичных процессов, то в каждый момент его выполнения может потребоваться " приостановить" или вообще " затормозить" его протекание. Для этих целей вводится понятие - СОСТОЯНИЕ ПРОЦЕССА.

Термин " состояние процесса" имеет непосредственное отношение к понятию ПРОЗРАЧНОСТЬ. Так, если некоторые действия включаются в выполнение процесса и не оказывают влияние на результаты его работы, то они называются ПРОЗРАЧНЫМИ. Очевидно, что любое действие может быть прозрачным, если перед его выполнением состояние процесса сохраняется, а после выполнения - восстанавливается.

Создание алфавитного и тематического каталогов

После выполнения 1-го и 2-го проходов форматирования база данных содержит информацию о всех терминах. Отдельная операция ЭКСПОРТ БД создает HTML-страницы алфавитного указателя по одной странице на каждую букву и общий файл алфавитного указателя _termins.htm. Процедуры создания тематического каталога находятся в стадии разработки.

Создание и уничтожение объектовКонструкторы и деструкторы

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

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

Момент вызова конструктора и деструктора определяется временем создания и уничтожения объектов:

-для статических и внешних объектов -конструктор вызывается перед входом в main , деструктор -после выхода из main() . Конструкторы вызываются в порядке определения объектов, деструкторы -в обратном порядке;

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

-для динамических объектов -конструктор вызывается при выполнении оператора new , деструктор -при выполнении оператора delete .

В Си++ возможно определение массива объектов класса. При этом конструктор и деструктор вызываются для каждого элемента массива и не должны иметь параметров. При выполнении оператора delete кроме указателя на массив объектов необходимо также указывать его размерность.

//------------------------------------------------------bk73-01.cpp

&#35include &#60io stream.h&#62
&#35include &#60alloc.h&#62
&#35include &#60string.h&#62

&#35include &#60dos.h&#62
static int days[] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };

class dat
{
int day,month,year;
public:
dat(int=0,int=0,int=0); // Конструктор с параметрами

// (возможно умолчание)

dat(char *); // Конструктор с одним параметром

~dat(); // Деструктор

};
//------- Конструктор с параметром - текстовая строка -----

dat::dat(char *s)
{
int i;
char ss[80];
strcpy(ss,s);
for (i=0; ss[i] !=0; i++)
if (ss[i]=='-') ss[i]=','; // Замена '-' на ','

sscanf(ss,"%d%d%d",&#38day,&#38month,&#38year);
}
//------ Конструктор с тремя параметрами ------------------

// (по умолчанию 0 - текущая дата)

dat::dat(int d=0, int m=0, int y=0)
{
struct date x;
getdate(&#38x); // Стандартная функция получения текущей даты

// Проверка на значение по умолчанию

year = (y == 0) ? x.da_year : y;
month= (m == 0) ? x.da_mon : m;
day = (d == 0) ? x.da_day : d;
}
//------ Деструктор --------------------------------------

dat::~dat()
{
cout &#62&#62 "Дата ==&#62" &#62&#62 day &#62&#62 " -" &#62&#62 month &#62&#62 " -" &#62&#62 year;
}
//----------------------------------------------------------

dat a("12-12-1990"); // Внешний объект - конструктор

// вызывается перед main()

dat b[10]; // Массив объектов - конструктор без

// параметров вызывается перед main()

void xxx(dat &#38p)
{
dat c(12,12); // Вызывается конструктор dat(int,int,int)

// для автоматического объекта

dat d = p; // Конструктор для автоматического объекта не

// вызывается, т.к. объект инициализируется

} // копированием

// При выходе из функции вызываются

void main() // деструкторы для объектов c и d

{ int i,n;
cin &#60&#60 n;
dat *p = new dat[n]; // Создание массива динамических объектов -

// конструктор без параметров явно вызывается

// n раз

delete [n] p; // Уничтожение массива динамических объектов -

// деструктор явно вызывается n раз

} // Деструкторы для a и b[10] вызываются после

// выхода из main()

Списки как динамические структуры данных

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

-односвязные -каждый элемент списка имеет указатель на следующий;

-двусвязные -каждая элемент списка имеет указатель на следующий и на предыдущий элементы;

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

Сразу же необходимо отметить основное свойство списков как структур данных. Последовательность обхода списка, естественно, зависит не от физического размещения элементов списка в памяти, а от последовательности из связывания указателями. Точно так же определяется нумерация элементов списка - ЛОГИЧЕСКИЙ НОМЕР элемента в списке - это номер, получаемывй им в процессе движения по списку.

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

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

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

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

Способ передачи параметров

В Си принят единый способ передачи параметров, который называется ПЕРЕДАЧЕЙ ПО ЗНАЧЕНИЮ. Выглядит он так:

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

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

-при изменении формальных параметров значения соответствующих им фактических параметров не меняются.

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

int f(int n1,int n2) // Эквивалент

int n1,n2 ,rez_f;
void f()
{ {
int i,j; int i,j;
... ...
n1 ++; n1 ++;
n2 = n1; n2 = n1;
return n2; rez_f = n2;
... ...
} }
int m=2; int m=2;
void main() void main()
{ {
int z; int z;
z = f( m,3); n1 = m; n2 = 3; f(); z = rez_f;
} }

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

int sum(int s[], int n) // Сумма элементов массива

int z; // Размерность передается

{ int i; // отдельным параметром

for (i=0,z=0; i&#60n; i++) z += s[i];
return(z); }
int c[10] = {1,6,4,7,3,56,43,7,55,33};
void main()
{ int nn; nn = sum(c,10); }

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

Способы анализа программы

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

переменных.

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

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

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

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

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

Смысл фрагментов алгоритмов может быть разным :

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

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

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

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

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

Способы формирования списков

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

Вариант 1. Элементы -обычные переменные, связи инициализируются транслятором, вся структура данных "зашита" в программный код:

struct list
{
list *next;
int val;
} a={0,NULL}, b={1,&#38a}, c={2,&#38b}, *ph = &#38c;

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

struct list A[100],*ph; // Создать список из

for (i=0; i&#60 99; i++) // элементов, размещенных

{ // в статическом массиве

A[i].next = A+i+1;
A[i].val = i;
}
A[99].next = NULL;
ph = A;

Вариант 3. Элементы списка являются динамическими переменными, связи между ними устанавливаются программно:

list *InsertFirst(list *ph, int n)
// Включить в начало списка

// ph - заголовок списка

// n - Значение элемента списка

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

pnew-&#62val = n; // динамическую переменную,

pnew-&#62next = *ph; // заполнить его и

ph = pnew; // поместить в начало списка

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

}

Средства обработки прерываний в Си

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

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

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

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

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

Для обработки прерываний в Си предусмотрен специальный вид функций с ключевым словом interrupt следующего вида (здесь и далее синтаксис приводится для Си++ - расширений файлов исходного текста вида . cpp ):

void interrupt INTR(bp,di,si,ds,es,dx,cx,bx,ax,ip,cs,flgs) { } // или

void interrupt INTR( ...) { }

Особенности работы компилятора при трансляции такой функции состоят в следующем:

- перед началом программного кода функции генерируются команды сохранения в стеке всех регистров процессора - ax, bx, cx, dx, es, ds, si, di, bp, кроме сохраняемых аппаратно - регистра флагов, cs,ip и регистров указателя стека - ss,sp, которые остаются без изменения (переключения стека не происходит);

- ds устанавливается на сегмент данных Си-программы. Этим обеспечивается возможность работы с внешними переменными;

- в bp копируется текущее значение sp - этим обеспечивается возможность работы с автоматическими переменными;

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

- выход из функции производится командой выхода из прерывания - RETI.

Ссылка (неявный указатель)

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

-синтаксис определения ссылки имеет вид синтаксиса определения указателя, в котором операция "*" заменена на "&#38";

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

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

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

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

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

struct dat { int day,month, year };
//--------------------------------------------------------

// Си++Эквивалент в "классическом" Си

//--------------------------------------------------------

//--------------- Инициализация константой --------------

int &#38a = 5; int aа = 5, *pa = &#38аa;
//--------------- Инициализация переменной --------------

int x; int x,*pa;
int &#38a = x; pa = &#38x;
a = 5; *pa = 5;
//-------------- Ссылка на структуру ---------------------

dat x; dat x;
dat &#38b = x; dat *pb = &#38x;
dat &#38c = {12,12,1990}; dat cc = {12,12,1990};
dat *pc = &#38cc;
b.year = 1990; pb-&#62year= 1990;
c.day=b.day+3; pc-&#62day = pb-&#62day+3;
// копирование структуры

c = b; *pc = *pb;
...sizeof(b)... ...sizeof(x)...
...sizeof(*pb)... // но не sizeof(pb)

//------------------------------------------------------bk72-02.cpp

//------ Включение в список с использованием ссылки на указатель и рекурсии

struct list
{
int val;
list *next;
} *head=NULL;

void InsertList(list *&#38ph, int n)
{
list *pnew;
if (ph==NULL || n &#60 ph-&#62val)
{
pnew = new list;
pnew-&#62val=n;
pnew-&#62next=ph;
ph=pnew;
return;
}
InsertList(ph-&#62next, n);
}
//------ Включение в дерево с использованием ссылки на указатель и рекурсии

struct btree
{
int val;
btree *l,*r;
} *hd=NULL;

void Insert(btree *&#38p, int n)
{
if (p==NULL)
{
btree *pnew=new btree;
pnew-&#62val=n;
pnew-&#62l=pnew-&#62r=NULL;
p=pnew;
return;
}
if (p-&#62val &#60 n) Insert(p-&#62l,n);
else Insert(p-&#62r,n);
}

Стандартная библиотека ввода-вывода

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

&#35 include &#60stdio.h&#62
void my_gets(char s[]) // Собственная функция gets(char s[])

{
int i;
char c;
for (i=0; i &#60 79 &#38&#38 (c=getchar()) !=EOF &#38&#38 c !='\n'; i++)
s[i] = c;
s[i]='\0';
}
&#35include &#60iostream.h&#62
char c,s[80];
void main() // Пример использования объектов потокового ввода

{
cin &#62&#62 c; // Посимвольный ввод

cin &#62&#62 s; // Построчный форматированный ввод

cin.getline(s,80); // Построчный неформатируемый ввод

}

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

В стандартной библиотеке каждый файл представлен структурированной переменной, в которой сосредоточена вся информация об открытом файле: тип файла, идентификатор файла в операционной системе (номер, handle ), буфер на 1 блок (сектор) файла, текущее состояние и способ работы с файлом. Назовем ее описателем или ДЕСКРИПТОРОМ ФАЙЛА. Спецификатор typedef для этой структуры, а также прототипы всех функций ввода-вывода содержатся в заголовочном файле stdio.h, который необходимо включить в текст программы макрокомандой &#35include.

typedef struct {.....} FILE;

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

&#35include &#60stdio.h&#62
FILE *fd; // Переменная fd - указатель на дескриптор файла

fd = fopen("aaa.txt","r");
// режим "чтение текстового файла"

// имя файла - строковая константа

// или указатель на строку

// fopen() возвращает указатель на дескриптор файла

// запомнить результат функции

if (fd == NULL)
printf("Файл не открыт\n");
else
{ // Указатель на дескриптор файла

fscanf(fd,....); // при обращении к файлу

fclose(fd); // Закрыть файл

}

Стандартные потоки (файлы) ввода-вывода

В библиотеке имеются внешние переменные-указатели на дескрипторы файлов - стандартных устройств ввода-вывода.

.
extern FILE *stdin, *stdout, *stderr, *stdaux, *stdprn;
стандартный ввод --- ¦ ¦ ¦ ¦
стандартный вывод ---------- ¦ ¦ ¦
регистрация ошибок ------------------ ¦ ¦
дополнительное устройство -------------------- ¦
устройство печати -------------------------------------

Эти файлы открываются библиотекой автоматически перед выполнением main и по умолчанию назначаются на терминал (stdin - клавиатура, stdout,stderr - экран), последовательный порт (stdaux) и принтер (stdprn). stdin и stdout могут быть переназначены в командой строке запуска программы на любые другие файлы

.
&#62test.exe &#60a.dat &#62c:\xxx\b.dat
¦ L------- файл stdout
L----------------- файл stdin

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

Статические элементы класса

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

. имя_класса::имя_элемента

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

//------------------------------------------------------bk73-02.cpp

// Все объекты класса dat связаны в односвязный список

//----------------------------------------------------

&#35include &#60stdio.h&#62
class dat
{
int day,month,year;
static dat *fst; // Указатель на первый элемент

dat *next; // Указатель на следующий элемент

public:
void show(); // Просмотр всех объектов

dat(); // Конструктор

~dat(); // Деструктор

};
dat *dat::fst=NULL; // Определение статического элемента

//---------------------------------------------------------

void dat::show()
{
dat *p;
for (p=fst; p !=NULL; p=p-&#62next)
{ /* вывод информации об объекте */ }
}
//------ Конструктор - включение в начало списка --------

dat::dat()
{ /* ... */ next = fst; fst = this; }
//------ Деструктор - поиск и исключение из списка -------

dat::~dat()
{
dat *p; // указатели на текущий и предыдущий

dat *pred; // элементы списка

for ( p=fst,pred=NULL; p !=NULL; pred=p,p = p-&#62next)
if (p = this) break; // Найден - выйти

if (p!=NULL) // Найденный исключить из списка

{
if (pred==NULL) fst=fst-&#62next;
else pred-&#62next=p-&#62next;
}
}

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

class list
{ ...
static void show(); // Cтaтическая функция просмотра

} // списка объектов

//--------------------------------------------------------

static void list::show()
{
list *p;
for (p=fst; p !=NULL; p=p-&#62next)
{ ...вывод информации об объекте... }
}
//-------------------------------------------------------

void main()
{ ... list::show(); } // Вызов функции по полному имени

Стеки, очереди

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

Стратегии взаимодействия объектов программе

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

Строки, массивы символов и указатели char*

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

-указатель на отдельный байт;

-указатель на область памяти -массив байтов;

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

-указатель на массив символов.

Какая из них в действительности имеет место -зависит от программы, транслятор здесь не накладывает ограничений. Тем не менее, по сложившейся традиции будем считать, что указатель на char ссылается на массив символов. А поскольку стандартным содержимым массива символов является строка - последовательность символов, ограниченная символом с кодом 0, то такой указатель логично назвать УКАЗАТЕЛЕМ НА СТРОКУ. Использование его в программе при работе со строками предпочтительнее в сравнении с массивом символов уже потому, что размерность массива символов фиксирована, а размерность памяти, адресуемой указателем, ограничивается внешними факторами. Таким образом, он является более естественным средством для представления строки.

int strlen(char *p) // Возвращает длину строки, заданной

{ // указателем на на строку char*

int n;
for (n=0; *p != '\0'; p++);
return n;
}
void strcat(char *dst, char *src)
{ // Объединяет строки,

while (*dst !='\0') dst++; // заданные указателями

for (; *src !='\0'; *dst++ = *src++);
*dst = '\0';
}

Несколько замечаний необходимо сделать о СТРОКОВЫХ КОНСТАНТАХ. Строковая константа представляет собой последовательность символов, заключенных в двойные кавычки (например "abcd"). Для строковой константы транслятор в любом контексте программы выполняет следующие действия:

-создает массив символов с размерностью, достаточной для размещения строки;

-инициализирует (заполняет) массив символами строки, дополняя символом '\0';

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

СТРОКОВАЯ КОНСТАНТА в любом контексте программы это указатель на создаваемый транслятором массив символов, инициализированный этой строкой.

char *q; // ПРОГРАММА

q = "ABCD";
char *q; // ЭКВИВАЛЕНТ

char A[5] = {'A','B','C','D','\0'};
q = A;

С точки зрения такого определения корректны и такие на первый взгляд " дикие" выражения:

char c,*q;
c = "ABCD"[3];
q = "12345" + 2;
for (q = "12345"; *q !='\0'; q++);

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

extern int strcmp(char *, char*);
char *p,A[20];
strcmp(A,"1234");
strcmp(p,A+2);

Строковые потоки

Строковые потоки - потоки, источниками символов которых являются не файлы, а строки в памяти. Они наследуют все функции и операции istream, ostream и iostream. Конструкторы строковых потоков (p - буфер строки, n - длина, mode - режим открытия) .

istrstream(char *p);
ostrstream(char *p, int n, int mode);
// mode = ios::out - запись с начала строки

// mode = ios::ate - добавление к существующей строке

strstream (char *p, int n, int mode);
// ios::in - чтение строки

// ios::out - запись строки

// ios::ate - добавление к существующей строке

// функция seekg - позиционирование в строке

Структура данных - вовсе не массивы

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

Структура как базовый тип данных

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

- операция ПРИСВАИВАНИЯ СТРУКТУРИРОВАННЫХ ПЕРЕМЕННЫХ производит побайтное копирование одной структуры в другую. Присваивание возможно также при косвенном обращении по указателю на структуру;

- ФОРМАЛЬНЫЙ ПАРАМЕТР СТРУКТУРИРОВАННАЯ ПЕРЕМЕННАЯ : имеет место способ передачи параметра по значению: в стеке резервируется место для размещения структуры -формального параметра и производится присваивание ей значения фактического параметра (копирование);

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

-в обозначении типа данных -структуры служебное слово struct можно опускать.

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

struct dat { int day,month,year; };
//-------------------------------------------------------

// Си++ Эквивалент в "классическом" Си

//-------------------------------------------------------

dat COPY(dat x) void COPY(dat *ret, dat x)
{ {
return(x); *ret = x;
}; };
void main() void main()
{ {
dat a1,a2,a3,*p; dat a1,a2,a3,*p;
//----- Прямое присваивание структур -----------------

a1 = a2; a1 = a2;
//----- Присваивание структур косвенно по указателю --

p = &#38a3; p = &#38a3;
*p = a2; *p = a2;
//----- Прямое присваивание результата - структуры ---

a1 = COPY(a2); a2 = x;
ret = &#38a1;
*ret = x;
//----- Неявная структурированная переменная ---------

a1 = COPY(COPY(a2)); dat dummy;
x = a2;
ret = &#38dummy;
*ret = x;
x = dummy;
ret = &#38a1;
*ret = x;
} }

Структурное программирование

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

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

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

Структуры данных с элементами произвольных типов

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

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

-в первом -"системная" и "прикладная" части структуры данных разделяются на отдельные переменные и связываются через указатель. Поскольку при работе с "системной" частью "прикладная" является неопределенной (произвольной), то такой указатель будет иметь тип void*. Но тогда при работе с "прикладной" частью потребуется преобразовать указатель void* к конкретному типу указателя на "прикладную" часть, и обратно. В "классическом" Си это может производиться по умолчанию, сопровождаясь предупреждением транслятора, в Си++ это должно быть сделано явно;

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

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

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

//------------------------------------------------------bk57-02.cpp

struct list
{
struct list *next; // системная часть элемента

void *pdata; // указатель на прикладную часть

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

list *insert (list *p h, void *pd)
{
list *p =new list)); // создать "системную" часть

p-&#62next = NULL; // нового элемента списка

p-&#62pdata = pd; // привязать "прикладную"

if (ph == NULL) // часть к "системной"

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

void *exclude( list **ph)
{
list *p = *ph;
if (p==NULL) return NULL;
*ph = p-&#62next;
void *pd = p-&#62pdata;
delete p; // уничтожить системную часть

return pd;
}
//----- Работа с конкретным списком

void main()
{ int *pval, A[ 10] ={3,4,8,32,67,5,7,4,78,45};
list *PH=NULL; // пустой список

for (i=0; i&#60 10; i++)
{
pval=new int; *pval=A[i]; // создать переменную

PH=insert(PH, (void*) pval); // включение в список

} // с преобразованием типа

for (i=0; i&#60 10; i++)
{
pval = (int*)exclude( &#38PH); // исключение элемента

delete pval; // уничтожение элемента

}
}

Во втором случае используется подмена : функция, работающая с элементами списка типа list получает элементы типа list1 с совпадающей " системной" частью :

//------------------------------------------------------bk57-03.cpp

struct list
{
struct list *next; // системная часть элемента

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

list *insert(list *ph, list *p)
{
if (ph == NULL) return p;
for (list *q=ph; q-&#62next!=NULL; q=q-&#62next);
q-&#62next=p;
return ph;
}
//----- Исключение первого элемента ----------------------

list *exclude(list * *ph)
{
list *p;
if ( *ph == NULL) return NULL;
p = *ph; *ph=p-&#62next;
return p;
}
//----- Работа с конкретным списком -----------------------

struct list1
{
struct list *next; // системная часть элемента

int value; // прикладная часть

} // элемента

*PH = NULL; // пустой список

void main()
{ list1 *pp;
for ( int i=0; i&#60 10; i++)
{
pp = new list1; // создание элемента

pp-&#62value = i; // заполнение

PH=(list1*)insert((list*)PH,(list*)pp);
// включение в список -

// преобразование типа list1* - list*

}
for (i=0; i&#60 10; i++) // исключение элемента -

{ // преобразование типа list* - list1*

pp = (list1*)exclude((list**)PH);
delete pp;
}
}

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

Структуры данных с произвольными связямиГрафы

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

//------------------------------------------------------bk55-10.cpp

//------Рекурсивный обход графа

struct graph
{
int cnt; // Счетчик обходов вершин

graph **pl; // Динамический массив

}; // указателей

void ScanGraph(graph *p)
{ int i;
p-&#62cnt++; // Увеличить счетчик

for (i=0; p-&#62pl[i] !=NULL; i++)
{
if (p-&#62pl[i]-&#62cnt !=p-&#62cnt) // Вершина не просмотрена

ScanGraph(p-&#62pl[i]); // Рекурсивный обход

}
}

Структуры данных " в узком смысле"

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

Структуры данных этого типа строятся на основе трех основных базовых структур данных :

- массивов (массивы указателей) (см.5.2.) ;

- списков (см.5.3.) ;

- деревьев (см.5.5.).

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

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

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

Для работы со структурой данных имеет место набор стандартных операций :

- выбор (поиск) по логическому номеру ;

- добавление последним ;

- включение по логическому номеру ;

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

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

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

- сортировка неупорядоченной структуры данных .

И, наконец , последняя характеристика HYPERLINK "bk51.htm" \l "def1" 08d0c9ea79f9bace118c8200aa004ba90b02000000090000000303000000000000c000000000000046000009000000626b35312e68746d00ffffadde00000000000000000000000000000000000000001600000010000000030062006b00350031002e00680074006d000500000064006500660031000000 структуры данных. В зависимости от способа хранения элементов различают:

- структуры данных, хранящие сами элементы данных;

- структуры данных, хранящие указатели на элементы данных. В этом случае сами элементы данных полностью независимы от структуры. Такой способ организации данных часто называют КОЛЛЕКЦИЕЙ. В этом случае допускается, что структура данных может хранить как указатели на элементы данных одного типа, так и на элементы данных различных (произвольных) типов (указатели типа void* ).

Структуры данных: все, кроме массивов

5.1. Структура данных - переменные, связанные алгоритмом
5.2. Массивы указателей

5.3. Линейные списки

5.4. Рекурсия

5.5. Рекурсивные структуры данных. Деревья

5.6. Указатели на функции

5.7. В стремлении к совершенству

5.8. Последовательные текстовые файлы

5.9. Двоичные файлы произвольного доступа

5.10. Организация файлов баз данных

Структуры и объединения

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

Структуры переменной размерности

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

struct man
{
char name[30]; // Фиксированная часть

int dd,mm,yy;
char address[]; // Переменная часть

};
man *create()
{
man *p;
char xxx[200];
gets(xxx); // Ввод значения элемента address

p = malloc(sizeof(man) + strlen(xxx) + 1);
strcpy(p-&#62address, xxx);
// Ввод фиксированной части

return p;
}

Связанные записи в файлеФайловый указатель

При размещении в файле динамических структур данных возникает вопрос, каким образом в файле будут представлены указатели, которые используются в переменных динамических структур данных. Само собой разумеется, что значение указателя, представляющего собой адрес указуемой переменной в памяти программы, никакого смысла при размещении той же переменной в файле не имеет. Но тогда обычному указателю, связывающему две переменные в памяти, нужно сопоставить аналогичный указатель в файле -назовем его ФАЙЛОВЫМ УКАЗАТЕЛЕМ. Его значением является позиция (адрес) переменной при ее размещении в файле. Как известно, позиция в файле определяется значением типа long, поэтому файловый указатель не является типизированным: тип его одинаков для любой переменной. Теперь рассмотрим подробнее задачу размещения связанных переменных (или записей). Если структурированная переменная а1 имеет указатель ptr на переменную a2 , то при размещении в файле переменная a1 должна получить еще один дополнительный параметр -файловый указатель fptr на место размещения в файле переменной a2. Сформировать значение файлового указателя можно следующим образом:

-если указуемая переменная (a2) еще не размещена в файле, позиционироваться на конец файла, получить текущую позицию как значение ее адреса в файле и записать переменную в файл. Если указуемая переменная уже размещена в файле, то просто использовать адрес ее размещения;

-полученный адрес указуемой переменной (a2) в файле сохранить как значение файлового указателя (fptr) в переменной, содержащей обычный указатель (ptr в a1);

-сохранить переменную (a2) в файле.

&#35define FNULL -1L
struct x
{
int val;
x *ptr;
long fptr;
} a2 = {0,NULL,FNULL}, a1 = {1, &#38a2, FNULL};

fseek(fd, 0L, SEEK_END);
a1.fptr = ftell(fd);
fwrite((void*)a1-&#62ptr, sizeof(x), 1, fd);

fseek(fd, 0L, SEEK_END);
fwrite((void*)&#38a1, sizeof(x), 1, fd);

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

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

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

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

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

//------------------------------------------------------bk59-03.cpp

&#35include &#60stdio.h&#62
&#35include &#60alloc.h&#62
struct ftree
{
int val;
struct ftree *left,*right; // Указатели в памяти

long fleft,fright; // Указатели в файле

};

&#35define FNULL -1L
&#35define TSZ sizeof(ftree)

//------ Функция записи возвращает адрес вершины в файле

//

long PutTree(ftree *p, FILE *fd)
{
long pos;
if (p == NULL) return(FNULL);
p -&#62fleft = PutTree(p-&#62left,fd);
p -&#62fright = PutTree(p-&#62right,fd);
pos = ftell(fd);
fwrite( (void*)p, TSZ, 1, fd);
return(pos);
}
//------ Функция формирует файл записей фиксированной длины

// В начало файла записывается указатель на головную

// вершину дерева

void SaveTree(ftree *p, char *name)
{
long pos0; // Указатель на головную запись

FILE *fd;
if ((fd=fopen(name,"wb")) ==NULL) return;
// Резервировать место под указатель

fwrite(&#38pos0, sizeof(long), 1, fd);
pos0 = PutTree(p,fd);
fseek(fd, 0L, SEEK_SET); // Обновить указатель

fwrite( (void*)&#38pos0, sizeof(long), 1, fd);
return;
}

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

Затем рекурсивно вызывает самое себя для размещения правого и левого поддерева. Полученные после размещения файловые указатели запоминает в текущей вершине, после чего "обновляет" ее в файле:

//------------------------------------------------------bk59-04.cpp

//------Вариант функции записи вершины дерева в файл

long PutTree_(ftree *p, FILE *fd)
{
long cpos; // Адрес в файле текущей

if (p==NULL) return(FNULL); // вершины дерева

fseek(fd, 0L, SEEK_END);
cpos = ftell(fd);
fwrite((void*)p, TSZ, 1, fd); // Записать в файл текущую вершину

p-&#62fright = PutTree(p-&#62right,fd);
p-&#62fleft = PutTree(p-&#62left,fd);
fseek(fd, cpos, SEEK_SET); // Обновить текущую вершину

fwrite((void*)p, TSZ, 1, fd);
return cpos;
}

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

//------------------------------------------------------bk59-05.cpp

//----- Функция возвращает указатель на динамическую

// переменную - вершину дерева, считывая ее и связанное

// с ней поддерево из файла

ftree *GetTree(long pos, FILE *fd)
{
struct ftree *p;
if (pos == FNULL) return NULL;
if ((p = new ftreeTSZ) ==NULL) return NULL;
fseek(fd,pos,SEEK_SET);
fread((void *)p, TSZ, 1, fd);
p -&#62left = GetTree(p -&#62fleft,fd);
p -&#62right = GetTree(p-&#62fright,fd);
return p;
}
//----- Функция открывает файл и читает файловый указатель

// на головную вершину дерева, по которой загружает дерево

// в память

ftree *LoadTree(char *name)
{
FILE *fd;
long phead;
if ((fd = fopen(name,"rb")) ==NULL) return(NULL);
fread((void*)&#38phead, sizeof(long), 1, fd);
return GetTree(phead, fd);
}

СвязываниеВнешние ссылки и точки входа

ВНЕШНЯЯ ССЫЛКА -- обращение к переменной или вызов функции во внутреннем представлении модуля, которые определены в другом модуле и отсутствуют в текущем ТОЧКА ВХОДА -- адрес переменной или функции во внутреннем представлении модуля, к которым возможно обращение из других модулей

ОБЪЕКТНЫЙ МОДУЛЬ -- файл данных, содержащий оттранслированные во внутреннее представление собственные функции и переменные, а также информацию о внешних ссылках и точках входа модуля в символьном виде

КОМПОНОВЩИК, линкер (LINK) -- программа, составляющая из объектных модулей и библиотек загрузочный модуль программы и выполняющая взаимное увязывание (разрешение) внешних ссылок и точек входа модулей

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

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

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

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

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

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

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

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

-связывание внешних ссылок и соответствующих точек входа (редактирование связей);

-подключение необходимых объектных модулей из библиотек с выполнением над ними вышеуказанных действий.

Рассмотрим подробнее алгоритм работы компоновщика:

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

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

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

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

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

.

Исходные модули Объектные модули
a.c pp a.obj
extern double f(); 0000
double g() {} 1000 код функции g()
... внешняя ссылка
f(); 2000 CALL (0000) "f"
g(); 300 0 CALL 1000
4000
b.c pp b.obj
double f() { 1200 точка входа f=1200
код функции f()
... внешняя ссылка
printf("%d",n); 1400 CALL (0000) "printf"
} код функции f()
1600

.

Загрузочный модуль a.exe

.

0000 a.obj
1000 код функции g()
внешняя ссылка
2000 CALL (5200) - адрес точки входа f
3000 CALL 1000
4000 b.obj
5200 Точка входа f= 4000 + 1200 = 5200
код функции f()
внешняя ссылка
5400 CALL (6600) - адрес точки входа printf
код функции f()
5600 библиотечный модуль
Точка входа printf = 1000 + 5600 = 6600
6600 Код функции printf

Технология объектно-ориентированного программирования на Си++ (часов)

1. . Тотальное ООП как программирование " от класса к классу" (1 час).

2. . Пример разработки программы на основе системы классов - база данных. Абстрактный класс хр а нимого объекта данных, классы типов данных, класс строки, класс таблицы, классы файлов (3 часа)

3. . Модульное ООП. Заголовочные файлы, библиотеки модулей и проекты. О ОП с использованием стандартных библиотек классов. Работа c OWL - Object Windows Library (2 часа).

4. . Стратегии взаимодействия объектов в сложной программе. Принцип разработки программ под Windows - объекты, управляемые сообщениями ( bk66.doc ) (2 часа).

Технология программирования - это

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

и алгоритм, выполняемый над ней

Структура формальных параметров для функции

Типы данных и переменные

Особенности иерархического проектирования типов данных в Си состоят в том, что принцип контекстного определения типа данных (в контексте операций, выполняемых над переменной, которые присутствуют в ее определении), толком не объясняется в литературе (по крайней мере автор не видел ни одного издания, где это обсуждалось в целом, а не на отдельных примерах типа "вот так это выглядит"). С этой целью пришлось выделить отдельную группу операций (по их назначению) - операции выделения составляющего типа данных ( [],'.',(),* ) для всех производных типов данных - указателей, массивов, структур и функций. Кроме объяснения самого способа контекстного определения типов данных рассматривается ряд примеров формальной расшифровки контекста даже для тех типов данных, с которыми читатель столкнется позднее. Это позволяет глубже понять сам принцип. Естественно, что в "Вопросах без ответов..." на эту тему подобраны тесты.

Типы данных: не только массивы

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

4.1. Указатели, массивы, память
4.2 Структуры и объединения

4.3. Типы данных и переменные

4.4. Указатели и управление памятью в Си

4.5. Функция как тип данных и модуль

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

4.7. Динамические переменные и массивы

4.8. Биты, байты, слова