Работа с динамической памятью в Си

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

void *malloc(int size);
// выделить область памяти размером

// в size байтов и возвратить адрес

void free(void *p);
// освободить область памяти,

// выделенную по адресу p

void *realloc(void *p, int size);
// расширить выделенную область памяти

// до размера size, при изменении адреса

// переписать старое содержимое блока

Пример создания простой динамической переменной:

&#35include &#60alloc.h&#62
double *pd;
pd = malloc(sizeof(double));
if (pd !=NULL)
{
*pd = 5;
free(pd);
}

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

Для более естественной работы с динамическими переменными в Си++ введены также l операторы управления динамической памятью new и delete . Их отличительные особенности :

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

-если выделяется память под массив динамических переменных, то в операторе new добавляются квадратные скобки (см. ниже " Динамические массивы" ).

double *pd;
pd = new double ; // Обычная динамическая переменная

if (pd !=NULL)
{
*pd = 5;
delete pd;
}
double *pd ; // Массив динамических переменных

pd = new double[20];
if (pd !=NULL)
{
for (i=0; i&#60 20; i++) pd[i]=0;
delete pd;
}

Работа с массивом указателей

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

//------------------------------------------------------bk52-01.cpp

double extract 1(double d[], int n , int sz )
{ double x; int i;
x = d[n];
for (i=n; i&#60sz; i++)
d[i]=d[i+1];
return x;
}
double sort 1(double d[],int sz)
{ int i,k;
do
{
k = 0;
for (i=0; i&#60sz-1; i++)
if (d[i] &#62 d[i+1])
{ double c; c = d[i];
d[i] = d[i+1]; d[i+1] = c; k=1;}
}
while (k); }

double *extract2(double *pd[] , int n)
{ double *x; int i;
x = pd[n];
for (i=n; pd[i]!=NULL; i++)
pd[i]=pd[i+1];
return x;
}
double sort 2(double *pd[])
{ int i,k;
do
{
k = 0;
for (i=0; pd[i+1]!=NULL;i++)
if (*pd[i] &#62 *pd[i+1])
{double *c; c = pd[i];pd[i] = pd[i+1];
pd[i+1] = c; k = 1; }
}
while (k);
}

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

- pd[i] -i-й указатель в массиве;

- *pd[i] -значение указуемой переменной по i-му указателю в массиве.

Работа с окнами и файлами

---------------------------------------------------------------¬
¦File Edit Search Run Compile Debug Project Options Window Help¦
L-¦-------------------------------------------------------------
¦ --- Создать новый файл с временным именем
¦ ¦ NONAMExx.C и открыть окно
--+---------------¬ ¦ - Открыть окно с выбранным файлом
¦ New ----- ¦ (файл выбирается в отдельном окне,
¦ Open F3 ------- при вводе нового имени - создается)
¦ Save F2 ------- Сохранить текущее окно в файле
¦ Save as... ------- Сохранить текущее окно в отдельном
¦ Save all ------¬ файле с явно заданным именем
+-----------------+ L Сохранить все окна в файлах
¦ Change dir... ------- Выбрать текущий каталог файлов
¦ Print ------- Печать текущего окна
¦ DOS Shell ------- Запуск оболочки DOS
+-----------------+ (возврат по команде EXIT)
¦ Quit Alt+X ------- Выход
L------------------

.
Alt+0 - открыть список окон. Список окон представляет собой
отдельное окно, содержащее меню - список окон, по
которому можно перейти в любое выбранное окно или
закрыть его (Del)
Alt+n - непосредственно перейти в окно с номером n=1..9

---------------------------------------------------------------¬
¦File Edit Search Run Compile Debug Project Options Window Help¦
L---------------------------------------------------¦-----------
Изменить положение окна клавишами перемещения ¦
курсора и размеры окна клавишами ------------+-------¬
перемещения курсора с Shift ------------ Size/Move Ctrl+F5 ¦
Развернуть/свернуть на полный экран ---- Zoom F5 ¦
Каскадное расположение окон ------------ Cascade ¦
Расположение окон без перекрытий ------- Tile ¦
Перейти в следующее по номеру окно ----- Next F6 ¦
Закрыть текущее окно ------------------- Close Alt+F3 ¦
Закрыть все окна ----------------------- Close all ¦
Открыть или перейти в окно: ¦ ¦
Окно сообщений транслятора -----------¬ +-------------------+
Окно вывода программы (параллельно с L- Message ¦
User screen) --------------------------- Output ¦
Окно точек просмотра ------------------- Watc ¦
Экран программы (переход/возврат) ------ User screen Alt+F5 ¦
Окно регистров процессора -------------- Register ¦
Окно файла проекта --------------------- Project ¦
Окно собственных замечаний ------------- Project notes ¦
+-------------------+
Открыть список окон -------------------- List all Alt+0 ¦
L--------------------

Работа с памятью " на низком уровне"

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

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

&#35define N 40
double *d;
char A[N];
for (i=0, d=( double*)A; i &#60 N / sizeof(double); i++)
d[i] = (double)i;

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

Работа с последовательностью данных переменного формата

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

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

char *p, A[100], c;
int i;
long r;
p=A;
// взять int по указателю и переместить указатель

// к следующей переменной

i = * (( int*)p )++;
// взять long по указателю и переместить указатель

// к следующей переменной

r = *((long*)p)++;
c = *p++; // взять байт по указателю

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

union ptr
{ char *p;
int *q;
long *l;
} PTR;
i = *(PTR.q)++; r = *(PTR.l)++; c = *(PTR.p)++;

Работа с указателем

В отличие от обычной переменной, работа с указателем включает три этапа:

-определение переменной -указателя;

-назначение указателя на указуемую переменную;

-работа с указуемой переменной с использованием косвенного обращения по указателю.

Поскольку все переменные в Си имеют тип, то указатель может содержать адрес не любой переменной, а только переменной определенного типа. Этот тип называется ТИПОМ УКАЗАТЕЛЯ. В нашем примере определение указателя int*p следует понимать как определение переменной, при косвенном обращении к которой получается значение переменной целого типа, или короче -указатель на целое.

Вторым этапом является операция p = &#38a, которая понимается как присваивание переменной p адреса переменной a , или как назначение указателя p на переменную a . Заметим, что без этой операции использование указателя для косвенного обращения является недопустимым.

И, наконец, косвенное обращение по указателю предполагает, что действие производится над указуемой переменной, адрес которой находится в данный момент в указателе. Тогда последняя операция x=x+*p будет эквивалентна x=x + a.

Замечание: образно говоря, операция " &#38" превращает переменную в указатель на эту переменную, точнее тип данных этой переменной в указатель на этот тип (см.4.3.). Тогда в операции присваивания p = &#38a в правой и левой части находятся указатели одного типа (указатели на целое).

Работа со списками

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

struct list
{
list *next;
int val;
} *ph; // заголовок списка

struct list *p; // указатель на текущий элемент

p = ph; // текущий указатель - на первый

p-&#62next ... // указатель на следующий элемент

p = p-&#62next; // переход к следующему элементу

p !=NULL ... // проверка на конец списка

p-&#62next ==NULL ... // проверка на последний элемент

for (p=ph; p !=NULL; p=p-&#62next)...
// просмотр элементов списка

if (ph !=NULL)
{
for (p=ph; p-&#62next !=NULL; p=p-&#62next);
} // поиск последнего элемента

list *pred; // просмотр с сохранением

// указателя на предыдущий элемент

for (pred=NULL, p=ph; p !=NULL; pred=p, p=p-&#62next) ...
// указатель на второй элемент

// от текущего

ph-&#62next = pnew; // включение в начало непустого

ph = pnew; // списка

pnew-&#62next = NULL; // включение в конец непустого

pred-&#62next = pnew; // списка

pred-&#62next = p-&#62next; // исключение текущего элемента

// списка (если он не первый)

pnew-&#62next = p-&#62next; // включение после текущего

p-&#62next = pnew; // элемента

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

struct list2
{
list2 *next,*pred;
int val;
} *ph, *p, *pnew;

pnew-&#62pred = p; // включение после текущего

pnew-&#62next = p-&#62next; // элемента

p-&#62next-&#62pred = pnew;
p-&#62next = pnew;
p-&#62pred-&#62next = p-&#62next; // исключение текущего элемента

p-&#62next-&#62pred = p-&#62pred; // из середины списка

Работа со строкой

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

//------------------------------------------------------bk34-01.cpp

// Удаление лишних пробелов при посимвольном переписывании

&#35include &#60stdio.h&#62
void nospace(c1[],c2[])
{
int i,j;
for (j=0,i=0;c1[i]!=0;i++) // Посимвольный просмотр строки

{
if (c1[i]!=' ') // Текущий символ не пробел

{
if (i!=0 &#38&#38 c1[i-1]==' ') // Первый в слове -

c2[j++]=' '; // добавить пробел

c2[j++]=c1[i]; // Перенести символ слова

} // в выходную строку

}
c2[j]=0;
}

Заметим, что контекст c1[j++]= имеет вполне определенный смысл : добавить к выходной строке очередной символ и переместиться к следующему.

Рассмотрим еще один пример поиск СЛОВА МАКСИМАЛЬНОЙ ДЛИНЫ. Несмотря на ярко выраженный " словный" характер алгоритма его можно реализовать путем посимвольного просмотра. Для этого можно использовать принцип, уже реализованный ранее при определении максимальной длины последовательности возрастающих значений. Достаточно использовать счетчик, который увеличивает свое значение на каждый символ слова и сбрасывает его при обнаружении пробела. Дополнительно в момент сбрасывания счетчика фиксируется его максимальное значение, а также индекс начала слова.

//------------------------------------------------------bk34-02.cpp

// Поиск слова максимальной длины посимвольная обработка

// Функция возвращает индекс начала слова или 1, если нет слов

int find(char s[])
{
int i,n,lmax,imax;
for (i=0,n=0,lmax=0,imax=-1; s[i]!=0; i++)
{
if (s[i]!=' ') n++; // символ слова увеличить счетчик

else // перед сбросом счетчика

{ // фиксация максимального значения

if (n &#62 lmax) { lmax=n; imax=i-n; }
n=0;
}
} // то же самое для последнего слова

if (n &#62 lmax) { lmax=n; imax=i-n; }
return imax;
}

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

//------------------------------------------------------bk34-03.cpp

// Поиск слова максимальной длины пословная обработка

// Функция возвращает индекс начала слова или 1, если нет слов

int find(char in[])
{
int i=0, k, m, b;
b=-1;
m=0;
while (in[i]!=0) // Цикл пословного просмотра строки

{
while (in[i]==' ') i++; // Пропуск пробелов перед словом

for (k=0;in[i]!=' ' &#38&#38 in[i]!=0; i++,k++); // Подсчет длины слова

if (k&#62m)
{
m=k;
b=i-k;
}
}
return b;
}

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

//------------------------------------------------------bk34-04.cpp

// Сортировка слов в строке в порядке убывания (выбором)

void sort(char in[], char out[])
{
int i,k;
i=0;
while((k=find(in))!=-1) // Получить индекс очередного слова

{
for (; in[k]!=' ' &#38&#38 in[k]!=0; i++,k++)
{ // Переписать с затиранием

out[i]=in[k]; in[k]=' ';
}
out[i++]=' '; // После слова добавить пробел

}
out[i]=0;
}

Расчетно-графическая работа

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

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

Цель работы : Закрепление навыков проектирования модульных программ и работы со структурами данных.

Тематика работ : Разработка базы данных в памяти на основе одной из структур данных.

Цель работы : Закрепление навыков проектирования структур данных в памяти и в файлах.

Тематика работ : Разработка простой базы данных в двоичном файле.

Раздел: Информатика и основы программирования на языке Си ( часа )

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

2. . Понятие алгоритма: алгоритм, предметная область, набор операций, интерпретатор. Формы пре д ставления алгоритма - блок схема. Программа как реализация понятия алгоритма в среде обработки данных. Компоненты языка программирования - типы данных и переменных, операции, логика а л горитма, модульная организация программы. Реализация программы на уровне компьютерной а р хитектуры - процессор, память, команда, данные. Принцип хранимой программы (bk11.doc) (2 ч а са).

3. . История развития языков программирования высокого уровня: Фортран, Бейсик, Паскаль, Си, их особенности. Язык Си как средство программирования архитектуры компьютера. Пример простейшей Си-программы вычисления суммы элементов массива. Особенности синтаксиса. Функции, переменные, операции, операторы (2 час).

4. . . Понятие типа данных и переменной. Определение переменных в Си. Базовые типы данных char,int,long как машинные слова. Особенности типа данных char. Байт, слово, двоиной слово. Системы счисления. Представление целых без знака в различных системах счисления, константы. Использование восьмеричной и шестнадцатиричной систем счисления для представления данных и работы с машинными словами (bk12.doc) (3 часа).

5. . Представление отрицательных чисел. Дополнительный код. Знаковая и беззнаковая формы представления в Си. Представление символов. Представление чисел с плавающей запятой . Массивы: особенности работы, инициализация (bk12.doc) (1 час).

6. . Преобразование базовых типов данных в выражениях: действия, порядок. Явные и неявное преобразования. (bk12.doc) (1 час).

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

8. . Выражения и операторы. Роль ";" как ограничителя. Классификации управляющей логики програ м мы - последовательность, условие, цикл, переход. Основные операторы Си: if, while, do-while, for, switch, break, continue, return, goto: классификация, особенности синтаксиса и выполнения (bk14.doc) (2 часа).

9. . Функции. Формальные и фактические параметры. Способ передачи параметров. Понятие стека. Результат функции. Локальные и глобальные (автоматические и внешние) переменные. Функция как основа модульного программирования (bk15.doc, bk36.doc) (2 часа).

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

11. . Основы традиционной технологии программирования. Модульное рограммирование, нисходящее и пошаговое проектирование. Структурное пр ограммирование. Пример проектирования программ поиска простых чисел (bk31.doc) (2 часа).

12. . Циклические программы. Виды циклов. Итерационный цикл. Программа вычисления корня функции. Программа вычисления суммы ряда. (bk33 .doc) (2 часа).

13. . Работа со строками. Представление строки в Си. Строка и массив символов. Функции ввода-вывода. Программы преобразования целого числа из символьной формы в двоичную и обратно. Проектирование программ сортировки слов, форматирования строки и преобразования кодов (bk34.doc) (4 часа).

14. . Сортировка и поиск.Понятие записи и ключа. Линейный и двоичный поиск. Трудоемкость алг о ритмов сортировки и поиска. Классификация сортировок: выбор, вставка, обмен, подсчет, раздел е ние, слияние. Примеры проектирования программ (bk37.doc) (4 часа).

15. . Организация выполнения программ в компьютере. Трансляция. Компилятор и интерпретатор. Ф а зы трансляции: макропроцессор, лексический, синтаксический и семантический анализ, генерация кода. Модульное программирование, объектный модуль, компоновка, библиотеки (bk16.doc) (1 час).

Раздел : " Эпизодическое" объектно-ориентированное программирование ( часов)

1. . Понятие класса. Сущность личной и общих его частей. Понятие объекта, свойства объектов, время жизни. Инициализация. Понятие конструктора и деструктора. Доступ к личной части класса, дружественные функции и классы. Типы объектов: внешний, автоматический, динамический, временный. Массивы объектов. Свойства конструктора и деструктора ( bk63.doc ) (2 часа).

2. . Примеры разработки классов: простейшие (дата) и со связанными динамическими данными данными ( строки, матрицы) . Свойства класса : закрытость, универсальность ( bk63.doc ) (1 час).

3. . Переопределение операций . Особенности переопределения некоторых операций (преобразования типа, индексации, динамической памяти, присваивания ) ( bk63.doc ) (2 часа).

4. . Понятие действия и результата при выполнении элемента-функции или переопределенной операции. Типы результата: пустой, базовый, указатель и ссылка на тип данных, указатель и ссылка на объект, объект . Конвейерные операции. Использование конвейера значений, указателей и ссылок ( bk63.doc ) (2 часа).

5. . Временные объекты при передаче формальных параметров и результата через объект. Конструктор копирования ( bk63.doc ) (1 час).

6. . Представление структур данных в виде классов. Массивы указателей, списки, деревья ( bk64.doc ) (2 часа).

Раздел : Машинно-ориентированные операции и работа с битами (часа).

1. . Побитовые операции (операции над машинными словами). Логические операции И,ИЛИ,НЕ, и с ключающее ИЛИ, их смысл. Смысл побитовых операций при работе с константами. Маскирование битов и полей. Примеры программ : упаковка данных, машинная арифметика ( bk35.doc ) ( 4 часа ) .

Раздел: Обзор технологий программирования (чаc ов).

1. . Понятие технологии программирования. Подходы: процедурное, логическое, объектно-ориентированное программирование. Нисходящее проектирование программ: структурное программирование. Роль языка Паскаль. Пример проектирования программы методом структурного программирования. Восходящее проектирование. Библиотека стандартных функций. (bk61.doc) (2 часа).

2. . Объект и класс. Содержательное и синтаксическое определение объекта и класса. Класс как еди н ство данных и методов. Объектно-ориентированное программирование (ООП) как программир о вание " от класса к классу" . Взаимосвязь и приоритеты данных и алгоритма в традиционном пр о граммировании и ООП. Использования объектно-ориентированного подхода в " классическом" Си (bk61.doc) (1 час).

3. . Особенности языка Cи++ в сравнении с классическим Си. Неявные и контекстные преобразования. Дополнительные средства C++: присваивание структур, структуры как формальные параметры и результат функции, переопределение функций, элементы-функции, операторы динамической памяти, ссылки . (bk62.doc) (3 часа).

4. . Использование ссылок в качестве формальных параметров и результата функции. Конвейер значений, указателей и ссылок в функциях (bk62.doc) (2 час а).

Раздел : Организация файлов данных ( bk.doc ) ( часов)

1. . Определение файла. Запись как единица хранения данных. Классификация : текстовые и двоичные, последовательные и произвольного доступа. Модель файла как система представлений о файле в среде программирования, ее связь с языком. Модель текстового файла. Представление текста в ра з личных частях операционной системы. Технология работы с файлом в stdio. Дескриптор файла. Функции работы с файлом. (2 часа).

2. . Последовательный текстовый файл. Позиционирование в текстовом файле. Примеры программ п о страничного просмотра файла и анализа вложенных фрагментов (1 час).

3. . Модель двоичного файла. Связь представления двоичного файла с организацией работы с памятью в Си. Распределение памяти в двоичном файле. Чтение, запись и добавление в файл отдельных п е ременных и массивов (1 час).

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

5. . Указатель в файле. Связанные записи в файле. Структуры данных с указателями в файле - массивы указателей, деревья, списки (2 часа).

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

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

8. . Поиск вычисление адреса. Хэширование. Особенности функций вычисления адреса. Проблема столкновений (1 час).

Раздел : Основы системного программирования и организации вычислительных процессов ( часов)

1. . Машинно-зависимое программирование на Си. Указатели и организация памяти. " Длинные" ук а затели и работа с физическими адресами ( bk81.doc) (1 час).

2. . Модели памяти компилятора как средства распределения памяти в оттранслированной программе. Модели TINY,SMALL,LARGE,HUGE, использование и ограничения (bk81.doc) (1 час).

3. . Понятие процесса как выполняемой программы. Состояние процесса. Система независимых кв а зипараллельных процессов. Прерывание. Свойства. Прерывание как процесс. Механизм реализ а ции прерывания в I8086 , управление прерываниями в устройстве, контроллере, процессоре . Пр е рывание на Си. Обеспечение прозрачности, установка и сохранение векторов, программные и а п паратные прерывания ( bk82.doc ) (2 часа).

4. . Прерывание как процесс. Взаимодействие прерывающего процесса и основной программы. Ввод и вывод по прерыванию. Вложенные прерывания. Отложенные прерывания (bk82.doc) (2 час).

5. . Технология обработки прерываний в DOS . Перехват прерываний. Резидентные программы как элемент многозадачности. Примеры. Реентерабельность. Средства синхронизации доступа к фун к циям DOS ( bk83.doc ) ( 2 часа ) .

6. . Модель разделения времени. Связь прерывания с переключением задач. Состояния процесса - в ы полнение, готовность, блокировка. Синхронизация. Семафоры ( bk84.doc ) (2 часа).

7. . Ввод-вывод в системах разделения времени. Очереди. Запросы. Блокировка процессов. Структура драйвера ( 2 часа).

Раздел : Структуры данных ( часов)

1. . Понятие структуры данных. Алгоритмическая компонента структуры данных. Статические и дин а мические структуры данных. Структуры данных " в узком смысле" . Упорядоченность. Понятие л о гического номера элемента, ключевого поля. Операции включения, добавления, удаления, поиска по ключу, извлечения по логическому номеру и сортировки структуры данных. Классификация структур данных : массивы, массивы указателей, списки, деревья. Иерархические структуры данных (bk51.doc) (2 часа).

2. . Массивы указателей. Способы формирования массивов указателей - статические, динамические, смешанные. Работа с массивами указателей. Примеры функций включения, исключения, сортиро в ки и поиска. Массив указателей на строки. (bk52.doc) (3 часа).

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

4. . Двусвязные списки. Включение и исключение элемента. Проблема концов списка, циклические списки (1 час).

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

1. . Деревья как рекурсивные структуры данных. Определение вершины дерева. Рекурсивный характер обхода дерева. Алгоритмы полного обхода дерева, поиска минимального значения, включения на заданную глубину. Нумерация вершин дерева. Способы нумерации. Поиск элемента по логическ о му номеру. Способы организации данных в дереве для сокращения глубины просмотра. ( bk54.doc ) (4 часа).

2. . Двоичное дерево. Включение и поиск в двоичном дереве. Связь двоичного дерева с алгоритмов двоичного поиска. Эффективность поиска в двоичном дереве. Сбалансированность. Извлечение из двоичного дерева по логическому номеру (bk54.doc) (2 часа).

3. . Сравнительная характеристика структур данных. Иерархические структуры данных. Примеры : дву х уровневый массив указателей, список, содержащий массивы указателей, массив заголовков сп и сков. Оптимизация иерархических структур данных ( bk58.doc) (2 часа).

4. . Указатель на функцию. Синтаксис. Смысл указателя на функцию - как средства параметризации части алгоритма обработки данных. Указатель на функцию - формальный параметр. Функция в ы числения определенного интеграла. Итератор. Итераторы foreach, firstthat . Итераторы, основанные на сравнении - сортировка, поиск минимального, двоичный поиск. Примеры (2 часа).

Раздел: Типы данныхОсновы организации программы и данных ( часов).

1. . Указатели. Указатель как элемент аржитектуры компьютера. Синтаксис указателя в Си. Указатель - как " степень свободы " программы. Указатель - формальный параметр и результат функции (bk41.doc) (2 часа).

2. . Адресная арифметика. Указатели и массивы. Способы работы через указатель с массивом - инде к сация и перемещение указателя. Указатели char*, работа со строками через указатели. Примеры (bk41.doc) (2 часа).

3. . Структура. Определение структуры как типа данных. Структура и массив. Массивы структурир о ванных переменных. Указатель на структуру. Указатель на структуру - формальный параметр и р е зультат функции. Инициализация структурированных переменных. Проектирование сложных пр о грамм - иерархия типов данных и функций (bk42.doc) (2 часа).

4. . Понятие типа данных. Тип данных и переменная. Базовые и производные типы данных. Виды производных типов данных. Операции извлечения составляющего типа данных. Иерархия опред е лений типов данных и вложенности компонент переменных. Контекстный способ определения типа данных в Си. Примеры анализа контекстных определений. Абстрактный тип данных. Спец и фикация typedef . Иерархия типов данных и иерархия вызовов функций в модульных программах (bk43.doc) ( 4 часа ) .

5. . Операции над указателями. Преобразование типов указателей. Указателии и управление памятью. Машинно-зависимые операции над указателями . Использование указателей для работы с данными переменного формата ( bk44.doc ) (2 часа).

6. . Функция как тип данных. Спецификация типа результата функции. Определение и объявление функции. Прототип. Функции с переменным количеством параметров. ( bk45.doc ) (2 часа ) .

7. . Динамическая память. Динамические переменные и массивы. Операторы и функции управления динамической памятью. Строки - как динамические массивы. " Виртуальные массивы" - програм м ная реализация ( bk47.doc ) (2 часа ) .

8. . Модульная организация программы. Время жизни и область действия переменных. Классификация. Определение и объявление переменных. Внешние, автоматические и статические переменные. О б ласть действия функций. Внешние и статические функции. Модульное программирование. Библи о теки. Заголовочные файлы, их назначение и содержание. Файл проекта ( bk46.doc ) (2 часа).

Раздел : Тотальное объектно-ориентированное программирование (часов)

1. . Объекты - элементы данных класса. Производные классы. Доступность элементов базового и производного классов. Наследование. Особенности конструирования объектов производных классов (bk65.doc) (2 часа) .

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

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

4. . Множественное наследование. Виртуальные базовые классы. (bk65.doc) (1 час).

5. . Шаблоны. Примеры шаблонов для структур данных с произвольными типами хранимых объектов ( bk65.doc ) (2 часа).

Редактирование

---------------------------------------------------------------¬
¦File Edit Search Run Compile Debug Project Options Window Help¦
L-----¦----¦----------------------------------------------------
¦ ---+-----------------¬
¦ ¦Find --- Искать по образцу
¦ ¦Replace --- Искать по образцу с заменой
¦ ¦Search again Ctrl+L --- Искать следующий за найденным
¦ ¦ ¦ по Find или Replace
¦ ¦Go to line number --- Переход к строке с заданным
¦ ¦... ¦ номером
¦ ¦Locate function --- Поиск заголовка функции
¦ L--------------------- в программе
------+-----------------¬
¦Undo ALT+BkSp ------ Отменить последнюю команду
¦Redo Shift+Alt+BkSp------ Повторить последнюю команду
+-----------------------+ Операции с буфером (Clipboard):
¦Cut Shift+Del --- Удалить блок с записью в буфер
¦Copy Ctrl+Ins --- Копировать блок в буфер
¦Paste Shift+Ins --- Вставить блок из буфера
¦Clear Ctrl+Del --- Удалить блок
¦Copy Example --- Копировать выбранный пример
+-----------------------+ из Help в буфер
¦Show Clipboard --- Просмотр буфера
L------------------------

.
Перемещения курсора:
Символ влево &#60-
Символ вправо -&#62
Слово влево Ctrl &#60-
Слово вправо Ctrl -&#62
Строка вверх "стрелка вверх"
Строка вниз "стрелка вниз"
Прокрутка вверх на одну строку Ctrl-W
Прокрутка вниз на одну строку Ctrl-Z
Страница вверх PgUp
Страница вниз PgDn

.
Перемещения на большие расстояния:
К началу строки Home
К концу строки End
К верхнему краю окна Ctrl Home
К нижнему краю окна Ctrl End
К началу файла Ctrl PgUp
К концу файла Ctrl PgDn
К началу блока Ctrl-Q B
К концу блока Ctrl-K K
К последней позиции курсора Ctrl-Q P

.
Команды вставки и перемещения:
Задание/снятие режима вставки Ins
Удалить символ слева от курсора Backspace
Удалить символ у курсора Del
Удалить слово вправо Ctrl-T
Вставить строку Ctrl-N
Удалить строку Ctrl-Y
Удалить символы до конца строки Ctrl-Q Y

.
Команды обработки блоков:
Пометить блок Shift + &#60стрелки&#62
(перемещение курсора)
Начало блока Ctrl-K B
Конец блока Ctrl-K K
Пометить слово под курсором Ctrl-K T
Пометить текущую строку Ctrl-K L
Удалить блок Ctrl-K Y
Прочитать блок из файла (текст Ctrl-K R
из файла читается и размещается
по текущему положению курсора)
Записать блок в файл Ctrl-K W
Копировать блок Ctrl-K C
Переместить блок Ctrl-K V
Печатать блок Ctrl-K P
Скрыть/отобразить блок Ctrl-K H
Задать структурный отступ блока Ctrl-K I
Отменить структурный отступ блока Ctrl-K U

.
Другие команды:
Восстановить строку Ctrl-Q L
Возвратиться к редактору из меню Esc
Искать Ctrl-Q F
Искать и заменить Ctrl-Q A
Табуляционное перемещение Tab

Реентерабельность и проблемы резидентных программ в DOS

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

void fun() {}
void interrupt intr(...) { ... fun(); ...}
void main() { ... fun(); ...}

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

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

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

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

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

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

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

- перед выполнением функции DOS в программе обработки прерывания необходимо убедиться в том, что DOS не занята обработкой программного прерывания от текущей выполняемой (прерванной) программы. Если это так, то необходимо отложить вызов до появления программного прерывания 28h (DOS свободна) или проверять занятость DOS по таймеру. Аналогичные действия необходимы также для ROM BIOS;

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

- аналогичные действия необходимо выполнять и со стеком.

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

Рекурсия

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

Рекурсия и поисковые задачи

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

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

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

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

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

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

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

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

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

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

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

Резидентная программа - всплывающие часы

Данная программа при нажатии ALT+? выводит часы и при повторном нажатии восстанавливает старое содержимое экрана на месте часов.

//------------------------------------------------------bk63-01.cpp

&#35include &#60dos.h&#62
&#35include &#60stdlib.h&#62
&#35include &#60stdio.h&#62
&#35include &#60string.h&#62
unsigned SHO; // Признак высвечивания часов

unsigned SIZE; // Размер программы в параграфах

unsigned HIGH; // Верхняя граница сегмента данных

// Указатели на функции обработки прерываний -

// "старые" вектора прерываний

void interrupt (*TIMSAV)(...),interrupt (*KBSAV)(...);

char save[30][2]; // Массив для хранения строки экрана

// Указатель на страницу 0 видеопамяти

char (far *q)[25][80][2]=(char (far*)[25][80][2])0xB8000000;

static char sss[100],xx[8]={" "};

// Вывод строки непосредственно в 0-страницу видеопамяти

void putstr(char *s,int x, int y)
{
while(*s !=NULL) // 25 строк по 80 символов по 2

{ // байта на символ

(*q)[y][x ][0] = *s++; // запись символа в видеопамять

(*q)[y][x++][1] = 0xE; // запись атрибута - желтый на черном

}
}

char *to10(char *p,int n)
{
*p++ = n/10+'0';
*p++ = n%10+'0';
return p;
}

void interrupt KEYB(...)
{
&#35define SCAN 53 // Скан-код клавиши "?"

&#35define ALT 8 // Бит нажатия ALT в байте состояния клавиатуры

char kbval; // в байте 0000:0417

kbval=peekb(0,0x417);
if (inportb(0x60)==SCAN)
{ // Нажатие "?" при нажатой ALT

if ((kbval &#38 ALT) !=0)
{ // Сброс контроллера клавиатуры

kbval=inportb(0x61);
outportb(0x61,kbval | 0x80);
outportb(0x61,kbval);
outportb(0x20,0x20);
SHO=!SHO; // Переключение режима высвечивания

// часов и сохранение/восстановление

// строки экрана под часами

for (int x=50; x&#60 70; x++)
if (SHO)
{
save[x-50][0]=(*q)[0][x][0];
save[x-50][1]=(*q)[0][x][1];
}
else
{
(*q)[0][x][0]=save[x-50][0];
(*q)[0][x][1]=save[x-50][1];
}
return; // Выход из прерывания

}
} // Иначе эмуляция прерывания

с которой сталкиваются при работе

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

Результат функции рекурсивного поиска

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

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

xxx step(char *lw)
{ ...
for (...)
{ ...
if (step(pw))
{}
}
return ...}

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

char *s(...)
{ char *p;
p=s(...); // вызов char *s(){...}

if (...) p=s(...); // вызов char *s(){...}

}

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

char *step(char *lw ) // результат - строка с цепочкой слов

{ ... // параметр - слово, с которого

// начинается цепочка

for (n=0; w[n]!=NULL;n++) //просмотр оставшихся слов

{
char *pw,*pp; int l; // слово уже выбрано -

if (*w[n]==0) continue; // пропустить

if ((l=TEST(lw,w[n]))!=-1 )
// можно присоединить к текущему

{
pw=w[n]; //убрать очередное слово из списка

w[n]=""; //рекурсивный вызов для нового

if ((pp=step(pw))!=NULL)
{ // !=NULL - цепочка выcтроена

s=new char[l+strlen(pp)];
strcpy(s,lw); // присоединить текущее слово

strcpy(s+l,pp); // к началу и использовать как

delete pp; // новый результат

}
w[n]=pw;
}
} ...}

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

smin=NULL;
for (n=0; w[n]!=NULL;n++)
{ ...if ((pp=step(pw))!=NULL)
{
s= ... //сформировать очередной результат

delete pp; //запоминание самой короткой строки

if (smin==NULL) smin=s; else
if (strlen(smin)&#62strlen(s))
{ delete smin; smin=s; }
}
}
return smin;

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

//------------------------------------------------------bk54-04.cpp

&#35include &#60iostream.h&#62
&#35include &#60string.h&#62
char *w[]={"bba","abb","ba",NULL};

int TEST(char *s, char *r)
{
int n,k;
k=n=strlen(s);
if (n==0) return 0;
for (;*s!=0 &#38&#38 n&#62 0; s++,n--)
if (strncmp(s,r,n)==0)
return k-n;
return -1;
}

char *step(char *lw)
{ int n; char *s,*smin;
for (n=0; w[n]!=NULL;n++)
if (*w[n]!=0) break;
if (w[n]==NULL)
{
s=new char[strlen(lw)+1];
strcpy(s,lw);
return s;
}
smin=NULL;
for (n=0; w[n]!=NULL;n++)

{
char *pw,*pp; int l;
if (*w[n]==0) continue;
if ((l=TEST(lw,w[n]))!=-1)
{
pw=w[n];
w[n]="";
if ((pp=step(pw))!=NULL)
{
s=new char[l+strlen(pp)];
strcpy(s,lw);
str cat(s +l,pp);
delete pp;
if (smin==NULL) smin=s; else
if (strlen(smin)&#62strlen(s))
{ delete smin; smin=s; }
}
w[n]=pw;
}
}
return smin;
}

void main() { cout &#60&#60 step("");}

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

//------------------------------------------------------bk54-05.cpp

&#35include &#60iostream.h&#62
&#35include &#60string.h&#62
char *w[]={"bba","abb","ba",NULL};

int TEST(char *s, char *r)
{
int n,k;
k=n=strlen(s);
if (n==0) return 0;
for (;*s!=0 &#38&#38 n&#62 0; s++,n--)
if (strncmp(s,r,n)==0) return k-n;
return -1;
}

&#35define SZ 80
struct string
{
int null; // Признак строка пустая

char str[SZ]; // Строка ограниченной длины

};
string step(char *lw) // Функция возвращает структуру как результат

{ int n;
string s,smin; // Локальные переменные - структуры

for (n=0; w[n]!=NULL;n++)
if (*w[n]!=0) break;
if (w[n]==NULL) // Последняя строка

{ s.null=0; strcpy(s .str,lw); return s; }
smin.null =1; // Признак строка еще пока пустая

for (n=0; w[n]!=NULL;n++)
{
char *pw; int l;
string pp; // Результат рекурсивного вызова

if (*w[n]==0) continue;
if ((l=TEST(lw,w[n]))!=-1)
{
pw=w[n];
w[n]="";
pp=step(pw) ; // Рекурсивная функция возвращает

if (!pp.null) // структурированную переменную

{ // За распределением памяти под

s.null=0; // структурированные переменные

strcpy(s .str,lw); // не следим

strcat(s.str,pp .str);
if (smin. null) smin=s; else
if (strlen(smin .str)&#62strlen(s .str))
smin=s; // Прямое присваивание структур

}
w[n]=pw;
}
}
return smin;
}
void main() { cout &#60&#60 step("") .str;}

Результат функции - указатель на строку

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

//------------------------------------------------------bk41-01.cpp

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

char * find(char *p,char *q)
{ char *s1,*s2;
for (; *p!='\0'; p++)
{
for (s1=p, s2=q; *s2!='\0' &#38&#38 *s1==*s2; s1++,s2++);
if (*s2 == '\0') return p;
}
return NULL;}
// Поиск всех вхождений фрагмента в строке

void main()
{ char c[80],*q= SYMBOL 34 \f "Courier New" \s 10 abc SYMBOL 34 \f "Courier New" \s 10 , *s;
cin.getline(c,80);
for (s=find(c,q); s!=NULL; s=find(s+strlen(q),q))
cout &#60&#60 s;
}

Результат операции, действия над операндами

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

a = b;
// Действие над операндом: переменная a получает значение переменной b

// Результат: значение переменной a после присваивания

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

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

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

a++;
// Действие над операндом: переменная a увеличивается нa 1

// Результат: значение переменной до ее увеличения

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

Роль символа ";"

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

a = b + c - 5 // Здесь пропущен символ ";"

if (a &#60 b) // Здесь транслятор обнаружит ошибку

// в выражении, которое с его точки

// зрения еще не закончилось

else // В этой части программы транслятор может

// обнаружить "наведенную "ошибку

// Эту часть программы транслятор пропустит

Конечно, здесь много зависит от особенностей транслятора, но чтобы не проверять его на " сообразительность" , лучше приучить себя вовремя ставить этот ограничитель.

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

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

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

Сбор и форматирование терминов

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

Термины представляют собой первичную справочную информацию. К ним относятся :

Отдельные слова, выделенные вручную в таблице слов ( постоянные слова);

Заголовки глав, разделов и подразделов;

Названия Си-программ (раздел, в котором они встречаются) ;

Названия таблиц (раздел, в котором они встречаются) ;

Последовательности слов, выделенные прописными буквами;

Последовательности слов, выделенные жирным шрифтом;

Последовательности слов, выделенные угловыми скобками;

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

Отдельные слова, выделенные из многословных терминов.

ССЫЛКИ представляют собой вторичную справочную информацию. Ссылками являются все упоминания терминов во всех документах. При обнаружении ссылки форматер помещает HTML-ссылку на первое слово алфавитного указателя.

Счастливые билеты

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

Шаг 1: Исходные данные и результат. Функция возвращает целое -количество " счастливых " билетов. Формальных параметров нет.

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

int calc()
{
int n; // Количество "счастливых" билетов

long v; // Проверяемое шестизначное число

int B[6]; // Массив значений цифр

for (n=0,v=0; v &#60 1000000; v++)
{
// Разложить val в массив значений цифр числа - B

if (B[0]+B[1]+B[2]==B[3]+B[4]+B[5]) n++;
}
return n;
}

Шаг 3: Остаток от деления целого числа на 10 дает значение младшей цифры, например 1996 % 10 = 6. Частное от деления целого числа на 10 дает то же самое число без последней цифры: 1996 / 10 = 199. Тогда остатки от последовательного деления на 10 исходного числа дадут искомые значения цифр (при условии, что частное от деления на следующем шаге становится делимым).

int m; // Номер шага (цифры)

long vv; // Исходное число

for (vv = v, m=0; m&#60 6; m++)
{
B[m] = vv % 10; // Остаток - очередная цифра

vv = vv / 10; // Частное становится делимым

}

Окончательный вариант:

//------------------------------------------------------bk32-03.cpp

//------Счастливые билеты

int calc()
{
int n, B[6];
long v;
for (n=0,v=0; v &#60 1000000; v++)
{
int m;
long vv;
for (vv = v, m=0; m&#60 6; m++, vv /=10)
B[m] = vv % 10;
if (B[0]+B[1]+B[2]==B[3]+B[4]+B[5]) n++;
}
return n;
}

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

Шаблоны

Достаточно часто встречаются классы, объекты которых должны содержать элементы данных произвольного типа (в том смысле, что их тип определяется отдельно для каждого конкретного объекта). В качестве примера можно привести любую структуру данных (массив указателей, массив, список, дерево). Для этого в Си++ предлагаются средства, позволяющие определить некоторое множество идентичных классов с параметризованным типом внутренних элементов. Они представляют собой особого вида заготовку класса (ШАБЛОН), в которой в виде параметра задан тип (класс) входящих в него внутренних элементов данных. При создании конкретного объекта необходимо дополнительно указать и конкретный тип внутренних элементов в качестве фактического параметра. Создание объекта сопровождается созданием соответствующего конкретного класса для типа, заданного в виде параметра. Принятый в Си++ способ определения множества классов с параметризованным внутренним типом данных (иначе, макроопределение) называется шаблоном ( template ).

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

//------------------------------------------------------bk73-11.cpp

// &#60class T&#62 - параметр шаблона - класс "T", внутренний тип данных

// vector - имя группы шаблонных классов

template &#60class T&#62 class vector
{
int tsize; // Общее количество элементов

int csize; // Текущее количество элементов

T **obj; // Массив указателей на параметризованные объекты

public: // типа "T"

T *operator[](int); // оператор [int] возвращает указатель на

// параметризованный объект класса "T"

void insert(T*); // включение указателя на объект типа "T"

int index(T*); //

};

Данный шаблон может использоваться для порождения объектов-векторов, каждый из которых хранит объекты определенного типа. Имя класса при этом составляется из имени шаблона " vector" и имени типа данных (класса), который подставляется вместо параметра "Т":

vector&#60int&#62 a;
vector&#60double&#62 b;
extern class time;
vector&#60time&#62 c;

Заметим, что транслятором при определении каждого вектора с новым типом объектов генерируется описание нового класса по заданному шаблону (естественно, неявно в процессе трансляции). Например, для типа int транслятор получит:

class vector&#60int&#62
{
int tsize;
int csize;
int **obj;
public:
int *operator[](int);
void insert(int*);
int index(int*);
};

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

//------------------------------------------------------bk73-12.cpp

// параметр шаблона - класс "T", внутренний тип данных

// имя функции-элемента или оператора - параметризовано

//

template &#60class T&#62 T* vector&#60T&#62::operator[](int n)
{
if (n &#62=tsize) return(NULL);
return (obj[n]);
}
template &#60class T&#62 int vector&#60T&#62::index(T *pobj)
{
int n;
for (n=0; n&#60tsize; n++)
if (pobj == obj[n]) return(n);
return(-1);
}

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

int* vector&#60int&#62::operator[](int n)
{
if (n &#62=tsize) return(NULL);
return (obj[n]);
}
int vector&#60int&#62::index(int *pobj)
{
int n;
for (n=0; n&#60tsize; n++)
if (pobj == obj[n]) return(n);
return(-1);
}

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

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

//------------------------------------------------------bk73-13.cpp

//-------Шаблон с параметром-константой

template &#60class T,int size&#62 class FIFO
{
int fst,lst; // Индексы начала и конца очереди

T queue[size]; // Массив объектов класса "T" размерности "size"

public:
T from(); // Функции включения-исключения

void into(T); //

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

};

template &#60class T,int size&#62 FIFO&#60T,size&#62::FIFO()
{ fst = lst = 0; }

template &#60class T,int size&#62 T FIFO&#60T,size&#62::from()
{
T work;
if (fst !=lst)
{
work = queue[lst++];
lst = lst % size;
}
return(work);
}

template &#60class T,int size&#62 void FIFO&#60T,size&#62::into(T obj)
{
queue[fst++] = obj;
fst = fst % size;
}

Пример определения объектов шаблонного класса:

struct x {};
FIFO&#60double,100&#62 a;
FIFO&#60int,20&#62 b;
FIFO&#60x,50&#62 c;

ШАБЛОНЫ СТАНДАРТНЫХ СТРУКТУР ДАННЫХ

Вариант структуры данных:

1. Стек, представленный динамическим массивом. Размерность - параметр конструктора.

2. Стек, представленный статическим массивом. Размерность - параметр шаблона.

3. Статический массив. Размерность - параметр шаблона.

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

5. Односвязный список.

6. Двусвязный циклический список.

7. Дерево с ограниченным количеством потомков.

8. Двоичное дерево.

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

1. Хранение указателей на объекты.

2. Хранение самих объектов.

Операция:

1. Включение элемента с сохранением упорядоченности.

2. Поиск и возвращение минимального объекта.

3. Сортировка (любым методом).

4. Двоичный поиск на основе сравнения с внешним объектом-ключом.

Операции 1-4 реализовать с учетом переопределения операций сравнения (&#60,&#62,==) для класса-параметра шаблона.

5. Включение элемента по номеру.

6. Исключение (удаление) элемента по номеру.

7. Поиск и возвращение элемента по номеру.

Что делает программа

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

//------------------------------------------------------bk21-01.cpp

&#35include &#60stdio.h&#62
// В текст программы включается заголовочный файл

// стандартной библиотека ввода-вывода, в котором

// содержится необходимая транслятору информация о

// функциях.

double min(double A[], int nn)
// Заголовок функции min, возвращающей в качестве

// результата вещественное число - значение мини-

// мального элемента массива. Формальные параметры-

// указатель на массив А, и размерность массива - nn.

{
double A_min;
int i;
// Локальные переменные функции, текущее минимальное

// значение элемента A_min и индекс в массиве i.

for (i=1, A_min=A[0]; i&#60nn; i++)
// Цикл выполняется для всех значений переменной i

// от 1 до nn-1 включительно. При этом начальное

// значение А_min устанавливается равным элементу

// массива A с индексом 0.

if (A[i] &#60 A_min) A_min=A[i];
// В каждом шаге цикла производится сравнение теку-

// щего элемента массива A[i] и A_min. Если текущий

// элемент меньше, то его значение становится новым

// минимумом.

return (A_min);
}
// Значение A_min возвращается в качестве результата

// функции и выполнение тела функции завершается.

double B[10]={ 3.,6.,-5.,4.,12.,3.3,0.45,5.,4.,8.};
// Массив из 10 вещественных чисел, инициали-

// зированный списком начальных значений, которые

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

// граммы. Массив является глобальной переменной,

// то есть доступен для любой, следующей за ним

// функции (в данном случае main).

double C[20];
// Глобальный массив из 20 вещественных чисел.

// Начальных значений не имеет.

void main()
{
// Основная функция main, вызывается при запуске

// программы.

int i,n1;
double dd;
// Локальные переменные функции. i - теекущий индекс

// элемента массива. n1 - количество заполненных

// элементов в массиве C[]. dd - сохраняет

// результат, возвращаемый функцией min при вызове.

do
// Оператор цикла с проверкой условия продолжения

// после очередного шага цикла.

{
// Тело цикла - составной оператор,

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

cout &#60&#60 "Элементов массива:";
// Выражение содержит операцию вывода в объект - поток.

// Ограниченное символом ";", превращается в простой

// оператор. Выводит на экран текст подсказки.

cin &#62&#62 n1;
// Вводит с клавиатуры значение целой переменной n1.

} while (n1 &#60 1 || n1 &#62 20);
// Цикл продолжается, пока введенное значение n1 не

// попадет в интервал 1..20. Условие продолжения -

// не попадает в интервал, то есть меньше 1 или

// больше 20.

for (i=0; i&#60n1; i++)
// Цикл повторяется для всех значений i, начиная от 0

// и заканчивая nn-1 включительно

{
// Тело цикла - составной оператор

cout &#60&#60 "C[" &#60&#60 i &#60&#60 "]=";
// Вывод подсказки - строка "C[...]", в угловых

// скобках значение переменной i - индекс текущего

// элемента массива.

cin &#62&#62 C[i];
// Ввод значения i-го элемента массива в формате

// вещественного числа

}
dd = min(C,n1);
// Вызов функции min для массива C[] и количества

// заполненых элементов в нем - n1. Результат

// функции присваивается переменной dd.

cout &#60&#60 "Минимум С[]=" &#60&#60 dd &#60&#60 endl;
// Вывод строки "Минимум C[i]=..." со значением пере-

// менной dd в формате вещественного числа.

// После вывода строки производится перевод курсора

// на экране к началу следующей (символ \n в

// форматной строке).

cout &#60&#60 "Минимум B[]=" &#60&#60 min(B,10)) endl;
// Вывод строки в подобном формате для массива B[].

// Вместо промежуточной переменной непосредственно

// следует вызов функции min для массива B[] раз-

// мерностью 10 элементов (фактические параметры).

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

Что такое произвольный элемент коллекции

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

//------------------------------------------------------bk8-02.cpp

//------Класс абстрактных элементов коллекции

class ostream;
class TElem
{
public:
TElem(); // Конструктор

virtual ~TElem();
//----- Виртуальный деструктор. Если объект производного

// класса уничтожается по указателю на объект базового,

// то деструктор должен быть виртуальной функцией. Это

// случается при уничтожении динамических объектов в

// операции delete.

virtual BOOL FromString(char *)=0;
virtual char *ToString()=0;
//----- Функции загрузки содержимого объекта из строки и

// создания строки, содержащей внешнее представление зна-

// чения объекта.

friend ostream&#38 operator&#60&#60(ostream&#38 s, TElem *pm)
{
char *p;
p = pm-&#62ToString();
s &#60&#60 p;
delete p;
return s;
}
//----- Переопределенный оператор &#60&#60 вывода в поток объекта

// TElem, заданного указателем (вызывается виртуальная

// функция ToString в производном классе)

virtual int Compare(TElem *)=0;
//----- Функция сравнения двух объектов. Является основой

// любой сортировки, упорядочения и поиска объекта. Дает

// результат вида:

// 0 - значения равны,

// -1 - значение текущего объекта меньше значения

// объекта - параметра.

// 1 - значение текущего объекта больше

virtual BOOL IsValid()=0;
//----- Функция проверки корректности значения объекта

virtual TElem *Copy()=0;
//----- Функция создания копии объекта, точнее объекта того

// же производного класса, что и текущий.

virtual int IDENT()=0;
virtual char *Name()=0;

//----- Функции, идентифицирующие производный класс объекта,

// возвращают его идентифицирующий номер и строковую

// константу - имя класса.

//----- Следующие функции связаны с хранением объекта в

// файле. Для работы с двоичным файлом произвольного до-

// ступа объект должен уметь сохранить свое значение по

// произвольному смещению в файле (Save), загрузить зна-

// чение (Load), добавить значение (Append). Для других

// классов, осуществляющих планирование файла, важно также

// знать размерность даннных объекта в файле (FSize).

virtual int FSize()=0;
virtual FPTR Update(BinFile&#38, FPTR=FNULL,int=1)=0;
virtual FPTR Append(BinFile&#38)=0;
virtual BOOL Load(BinFile&#38, FPTR=FNULL)=0;
};

TElem::TElem() {}
TElem::~TElem() {}

Файловая коллекция однотипных элементов

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

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

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

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

//------------------------------------------------------bk8-06.cpp

//------Класс - файловая коллекция

class FCollect : FArray
{
TElem *Prototype;
//----- Объект производного класса, тип которого соответст-

// вует типу объектов, с которыми работает программа и ко-

// торые должны храниться в файле.

BinFile F;
FPTR head;
//----- Указатель в файле на массив файловых указателей

public:
BOOL Create(char *,int);
BOOL Open(char *);
void Close();
BOOL Expand();
TElem *operator[](int);
int Insert(TElem *,int=-1);
BOOL Delete(int);
void Sort();
FCollect(TElem *);
~FCollect() {}
};

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

void FCollect::Close()
{
FArray::Close();
F.close();
}

BOOL FCollect::Expand()
{
FPTR *pnew;
if (size != NElem()+1)
return( FArray::Update(F,head,0) !=FNULL);
if ((pnew = new FPTR[size*2]) ==NULL) return(0);
for (int n=0; n &#60 size; n++) pnew[n] = ptr[n];
delete ptr;
ptr = pnew;
size *= 2;
if ((head = FArray::Update(F,head,1)) ==FNULL)
return(0);
F.seekg(sizeof(int));

if (!F.good()) return(0);
F.write((BUF)&#38head, sizeof(FPTR));
if (!F.good()) return(0);
return(1);
}

FCollect::FCollect(TElem *PROTO)
{
Prototype = PROTO;
}

BOOL FCollect::Create(char *nm, int sz)
{
int id;
Close();
if ((ptr = new FPTR[sz])==NULL) return(0);
size = sz;
ptr[0]=FNULL;
id = Prototype-&#62IDENT();
head = sizeof(int) + sizeof(FPTR);
if (!F.Create(nm)) return(0);
if (!F.Open(nm)) return(0);
F.seekg(0L);
F.write((BUF)&#38id, sizeof(int));
F.write((BUF)&#38head, sizeof(FPTR));
if (!F.good()) { F.close(); return(0); }
if (!FArray::Append( F )) return(0);
return(1);
}

BOOL FCollect::Open(char *nm)
{
int id;
Close();
if (!F.Open(nm)) return(0);
F.seekg(0L);
F.read((BUF)&#38id, sizeof(int));
F.read((BUF)&#38head, sizeof(FPTR));
if (!F.good()) return(0);
if (!FArray::Load( F , head)) return(0);
if (id !=Prototype-&#62IDENT()) return(0);
return(1);
}

TElem *FCollect::operator[](int n)
{
TElem *pobj;
if (n &#62=NElem()) return(NULL);
pobj = Prototype-&#62Copy();
if (!pobj-&#62Load( F, ptr[n] ))
{ delete pobj; return(NULL); }
return(pobj);
}

//----- Крайне неэффективный, с постоянной перезагрузкой

// объектов, но тем не менее работающий алгоритм сортировки

// методом "пузырька"

void FCollect::Sort()
{
int k,m;
TElem *p1,*p2;
if ((m = NElem()) &#60 2) return;
do
{
k = 0; p1 = (*this)[0];
for (int n=1; n &#60 m; n++)
{
p2 = (*this)[n];
if (p1-&#62Compare(p2) ==1)
{
k++;
FPTR tmp;
tmp = ptr[n];
ptr[n] = ptr[n-1];
ptr[n-1] = tmp;
delete p2;
}
else
{
delete p1; p1 = p2;
}
}
}
while (k);
FArray::Update( F,head,0);
}

int FCollect::Insert(TElem *pnew, int indx)
{
FPTR pp;
int n = NElem();
if (ptr ==NULL) return(-1);
if (Prototype-&#62IDENT() != pnew-&#62IDENT()) return(-1);
if (indx ==-1)
{
if ((ptr[n] = pnew-&#62Append(F)) ==FNULL)
return(-1);
ptr[n+1] = FNULL;
indx = n;
}
else
{
if (indx &#62 n) return(-1);
if ((pp = pnew-&#62Append(F)) ==FNULL)
return(-1);
for (int i = n; i &#62= indx; i--) ptr[i+1] = ptr[i];
ptr[indx] = pp;
}
if (!Expand()) return(-1);
return(indx);
}

BOOL FCollect::Delete(int indx)
{
int n = NElem();
if (ptr==NULL) return(0);
if (indx &#62= n) return(0);
for (int i=indx; i&#60n; i++) ptr[i] = ptr[i+1];
return (FArray::Update(F,head,0)!=FNULL);
}

Функции и общая структура программы

double min(double A[], int nn)
{
double А_m in;
int i;
...
return (А_min);
}
double B[10]=...
double C[20];
void main()
{
int i,n1;
double dd
... ,min(B,10)...
}

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

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

3. Имя функции -идентификатор.

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

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

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

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

Вне тела функции можно определить

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

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

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

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

12. Если формальный параметр является массивом, то действует исключение из общего правила. Функция не создает собственный массив (в данном случае А[]), а "отображает" пока неизвестным нам образом свой массив на тот, который является фактическим параметром (в данном случае B[]). То есть вместо массива A[] транслятор создает указатель на произвольный массив, который будет "подсунут" функции при ее вызове. Поскольку массив A[] "ненастоящий", размерность его может быть переменной и ее можно не указывать. На месте фактического параметра -массива в вызове функции указывается только его имя (без скобок).

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

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

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

Массив файловых указателей

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

//------------------------------------------------------bk8-05.cpp

//------Класс - массив файловых указателей

class FArray : TElem
{
protected: int size;
//----- Текущая размерность динамического массива в памяти

// и соответствующей записи в файле

protected: FPTR *ptr;
//----- Массив файловых указателей - является динамическим

// массивом переменных типа FPTR с ограничителем FNULL

public:

//----- Стандартные унаследованные и переопределенные

// функции работы с файлом из класса TElem

BOOL FromString(char *) { return(0);}
char *ToString() { return(NULL);}
int Compare(TElem *) { return(0);}
BOOL IsValid() { return(0);}
TElem *Copy() { return(NULL);}
int IDENT() { return(-1);}
char *Name() { return("");}
int FSize();
FPTR Update(BinFile&#38, FPTR=FNULL,int=1);
FPTR Append(BinFile&#38);
BOOL Load(BinFile&#38, FPTR=FNULL);
void Close();
//----------------------------------------------------------

int NElem();
FArray();
~FArray();
};

//----- Массив указателей в файле представляет собой запись

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

// ствующие функции класса BinFile

int FArray::FSize()
{ return(size * sizeof(FPTR)); }

int FArray::NElem()
{
if (ptr==NULL) return(0);
for (int n=0; ptr[n]!=FNULL; n++);
return(n);
}

FPTR FArray::Update(BinFile&#38 F, FPTR pos, int mode)
{
if (ptr == NULL) return(FNULL);
if (pos !=FNULL)
{ F.seekg(pos); if (!F.good()) return(FNULL); }
return (F.VSZUpdate((void *)ptr,FArray::FSize(),mode));
}

FPTR FArray::Append(BinFile&#38 F)
{
if (ptr==NULL) return(FNULL);
return( F.VSZAppend((void *)ptr, FArray::FSize()));
}

BOOL FArray::Load(BinFile&#38 F, FPTR pos)
{
if (ptr !=NULL) delete ptr;
if (pos != FNULL)
{ F.seekg(pos); if (!F.good()) return(0); }
if ((ptr = (long *)F.VSZLoad(size))==NULL) return(0);
size = size / sizeof(FPTR);
return(1);
}

FArray::FArray() { ptr = NULL; }

void FArray::Close()
{
if (ptr!=NULL) delete ptr;
ptr = NULL;
}

FArray::~FArray() { Close(); }

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

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

double min(...
{
for (i=1, А_min=A[0]; i&#60nn; i++ )
if (A[i] &#60 А_min) А_min=A[i];
}
void main()
{
...);
} while (n1 &#60 1 || n1 &#62 20);
...
dd = sum(C,n1);
}

1. Присваивание -это операция, которое значение выражения, стоящее справа от символа "=" запоминает в переменной или элементе массива, стоящем слева. При присваивании происходит преобразование форм представления (типов), если они не совпадают (например int -double или double -int). Четыре действия арифметики (+,-,*,/) и операция получения остатка от деления (%) образуют группу арифметических операций. Их выполнение не имеет каких-либо особенностей, кроме как преобразование типов переменных при их несовпадении. Если в одном выражении встречаются переменные типов double и int, то целая форма представления числа int преобразуется к вещественной double.

2. Операция i++ увеличивает на 1 значение переменной i после использования ее значения в выражении, то есть понимается как (взять i, i=i+1). Операция i-- аналогичным образом уменьшает значение переменной. Операции носят название инкремент и декремент. Те же самые операции, но поставленные перед переменной, изменяют ее значение до использования.

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

4. Операции сравнения ("==" -равно, "!=" -не равно, а также "&#62"," "," =","&#60=") дают в качестве результата значения "истина" или "ложь". Выражения с такими значениями называются условными, поскольку обозначают выполнение или, наоборот, невыполнение некоторого условия в программе. Они используются в условном операторе (if) и в операторах цикла (do -while, for).

5. Над значениями условных выражений можно выполнить логические операции И ("&#38&#38"), ИЛИ ("||") и НЕ ("!"), которые объединяют по правилам логики несколько условий в одно. В данном случае условие продолжения цикла истинно, когда значение переменной nn меньше 1 ИЛИ больше 20.

6. Вызов функции также представляет собой выражение.

Операторы

double min(...
{
for (i=1, А_min=A[0]; i&#60nn; i++ )
if (A[i] &#60 А_min) А_min=A[i] ;
return (А_min);
}
void main()
{
do
{
printf("Элементов массива:");
scanf("%d", &#38n1);
}
while (n1 &#62 0 &#38&#38 n1 &#60 20);
}

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

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

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

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

Тело функции также представляет собой составной оператор.

4. Оператор return формирует значение переменной-результата как значение выражения, стоящего за ключевым словом и ограниченного символом ";". Кроме того, он досрочно прекращает выполнение тела функции и возвращает программу в ту точку, где произошел вызов функции.

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

if (условное выражение) оператор_1 else оператор_2

if (условное выражение) оператор

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

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

while (условное выражение) оператор
do оператор while (условное выражение);

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

7. Оператор цикла for обеспечивает повторяющееся выполнение следующего за ним оператора (или блока) -тела цикла в соответствии с заданными в круглых скобках выражениями. Выражения отделяются друг от друга символом ";".

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

9. Второе выражение является условным. Оно определяет условие продолжения цикла и проверяется перед каждым выполнением тела цикла (шагом цикла).

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

Пример использования: ввод, сохранение и сортировка строк

//------------------------------------------------------bk8-07.cpp

&#35include &#60iostream.h&#62
&#35include &#60strstream.h&#62
void main()
{ char ss[80];
String s0("111111"),s1,*p;
FCollect C((TElem *)&#38s0);
C.Create("b.dat",10);
for (int i=0; i&#60 20; i++)
{
ostrstream z(ss,80);
z &#60&#60 (i+10)%20 &#60&#60 ends;
s1 = ss;
C.Insert((TElem *)&#38s1);
}
C.Close();
C.Open("b.dat");
for (i=19; i&#62=0; i--)
cout &#60&#60 C[i] &#60&#60 " ";
cout &#60&#60 "\n";
C.Sort();
for (i=0; i&#60 20; i++)
cout &#60&#60 C[i] &#60&#60 " ";
cout &#60&#60 "\n";
C.Close();
}

Промежуточный финишРаботаем с файлом строк

Итак, написаны три класса, около 200 строк текста. Уже можно работать с файлом, содержащим записи с виде объектов класса "строки", работать с ними как последовательно, так и в произвольном порядке. Здесь предлагается простой main(), при помощи которого можно в первом приближении отладить то, что написано.

//------------------------------------------------------bk8-04.cpp

&#35include &#60iostream.h&#62
void main()
{
BinFile F;
String a("1111"),b("2222"),c("3333");
String d1;
char *s;
//----- Работа с файлом в режиме последовательного доступа

F.Create("a.dat");
if (!F.Open("a.dat")) return;
a.Append(F);
b.Append(F);
c.Append(F);
F.Close();
if (!F.Open("a.dat")) return;
for (int i=0; i&#60 3; i++)
{
d1.Load(F);
cout &#60&#60 (s = d1.ToString());
delete s;
}
F.Close();
//----- Работа с файлом в режиме произвольного доступа

FPTR pp[3];
F.Create("a.dat");
if (!F.Open("a.dat")) return;
pp[0] = a.Append(F);
pp[1] = b.Append(F);
pp[2] = c.Append(F);
for (i=2; i&#62=0; i--)
{
if (!d1.Load(F,pp[i])) break;
cout &#60&#60 (s = d1.ToString());
delete s;
}
F.Close();
}

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

double min(...
{
double А_min;
int i;
}
double B[10] = { 3.,6.,5.,4.,12.,3.3,0.45,5.,4.,8.};
double C[20];
void main()
{
int i,n1;
double dd;
...i=0; i&#60n1;...
{
...
cin &#62&#62 C[i];
}

1. В программе в разных частях присутствуют имена простых переменных А_min, i, n1, nn, причем i повторяется внутри двух конструкций -min и main. Имя переменной (идентификатор) состоит из больших и маленьких латинских букв, цифр и знака "_" (подчеркивание) и начинается с буквы. Отмеченные здесь конструкции "вводят" в программу (или ее часть) эти переменные и называются определением переменной.

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

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

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

5. Массив также определяется как упорядоченное множество переменных, относящемуся к одному из типов данных. В нашем примере использованы массивы вещественных чисел. Номер элемента массива называется также индексом.

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

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

8. Судя по фрагменту программы, работа с массивами начинается с нулевого элемента, то есть массив размерности n включает в себя элементы с номерами (индексами) от 0 до n-1.

Стандартные функцииВвод-вывод

&#35include &#60io stream.h &#62
...
void main()
{
...
cout &#60&#60 "Элементов массива:";
cin &#62&#62 n1;
...
for (i=0; i&#60n1; i++)
{
cout &#60&#60 "C[" &#60&#60 i &#60&#60 "]=";
cin &#62&#62 C[i];
}
...
cout &#60&#60 "Минимум С[]=" &#60&#60 dd &#60&#60 endl;
cout &#60&#60 "Минимум B[]=" &#60&#60 min(B,10)) endl;

1. В Си отсутствуют функции, "встроенные" в транслятор. Это значит, что транслятор "не знает" о существовании каких-либо других функций, кроме тех, которые определены в программе. Поэтому транслятору нужно сообщить некоторую информацию о внешних функциях, к которым обращается программа. То же самое нужно сделать, если программа использует внешние объекты и переопределенные для них операции. Эта информация в виде тех же конструкций языка Си содержится в заголовочных файлах. По команде &#35include текст заголовочного файла включается в текст Си-программы. Для стандартной библиотеки ввода-вывода заголовочный файл имеет имя "io stream.h".

2. Объект cout обеспечивает вывод на экран, cin ввод с клавиатуры. Для cout переопределена операция &#60&#60 , которая " направляет" в поток вывода (на экран) значение очередной переменной. Здесь могут быть использованы любые простые переменные (базовые типы данных) и строки (массивы символов и строковые константы). Операция &#60&#60 может выполняться в цепочке, то есть она должна быть применена к каждому элементу из списка выводимых.

3. Перед выполнением ввода в программе обычно присутствует вывод на экран " подсказки" .

4. Для cin переопределена операция &#62&#62 , которая загружает очередную переменную значением из потока ввода (с клавиатуры).

Строки -элементы таблицы

//------------------------------------------------------bk8-03.cpp

&#35include &#60string.h&#62
&#35include &#60conio.h&#62
&#35include &#60stdlib.h&#62

class String : TElem
{
//----- Объект класса содержит единственный элемент данных-

// динамический массив символов. Его текущая размерность

// определяется длиной строки.

char *Str;
public:

//----- Эта часть класса представляет собой переопределение

// виртуальных функций базового класса TElem под конкретные

// свойства класса строк

BOOL FromString(char *);
char *ToString();
int Compare(TElem *);
BOOL IsValid();
TElem *Copy();
int IDENT();
char *Name();
int FSize();
FPTR Update(BinFile&#38, FPTR=FNULL,int=1);
FPTR Append(BinFile&#38);
BOOL Load(BinFile&#38, FPTR=FNULL);

//----- Эта часть класса представляет собой переопределение

// минимально необходимого набора операций со строками.

// Операции имеют "естественный" синтаксис, близкий к син-

// таксису арифметических операций.

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

String(char *); //

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

String(String &#38); // Конструктор копирования

int operator &#60 (String &#38); // Операторы сравнения

int operator &#62 (String &#38); //

int operator &#60=(String &#38); //

int operator &#62=(String &#38); //

int operator ==(String &#38); //

int operator !=(String &#38); //

String operator()(int); // Выделение подстроки

String operator()(int,int); //

String &#38operator=(String &#38); // Присваивание

String &#38operator=(char *);
String operator+(String &#38); // Конкатенация

String operator+(char *); //

operator int(); // Длина строки

int operator[](char *); // Поиск подстроки

int operator[](String &#38); //

};

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

// ледованные от абстрактного класса TElem и переопреде-

// ленные в String.

&#35define STRING_ID 10 // Уникальный идентификатор класса

int String::IDENT() { return(STRING_ID); }

char *String::Name() { return("Строка"); }

TElem *String::Copy()
{
String *p = new String;
return(p);
}

int String::Compare(TElem *p)
{
String *q = (String*)p;
if (Str==NULL || q-&#62Str==NULL) return(-1);
return(strcmp(Str,q-&#62Str));
}

BOOL String::FromString(char *p)
{
if (Str !=NULL) delete Str;
if ((Str = new char[strlen(p)+1])==NULL) return(0);
if (p==NULL) return(0);
strcpy(Str,p);
return(1);
}

char *String::ToString()
{
char *p;
if (Str==NULL) return(NULL);
if ((p = new char[strlen(Str)+1])==NULL) return(NULL);
strcpy(p,Str);
return(p);
}

//----- Динамический массив символов Str объекта класса

// "строка" сохраняется в файле в виде записи переменной

// длины, поэтому для работы с файлом используются

// соответствующие функции. Определенное по умолчанию зна-

// чение FNULL указателя в файле - p предполагает работу

// с файлом без позиционирования, то есть как с последова-

// тельным (или потоком).

int String::FSize()
{
if (Str==NULL) return(0);
return(strlen(Str) + 1 + sizeof(int));
}

FPTR String::Append(BinFile &#38F)
{
if (Str==NULL) return(FNULL);
return (F.VSZAppend((void *)Str, strlen(Str)+1));
}

BOOL String::Load(BinFile &#38F, FPTR p)
{
int sz;
if (Str!=NULL) delete Str;
Str = NULL;
if (p !=FNULL) if (!F.seekg(p)) return(0);
if ((Str=(char *)F.VSZLoad(sz)) ==NULL) return(0);
return(1);
}

FPTR String::Update(BinFile &#38F, FPTR p, int mode)
{
if (Str==NULL) return(FNULL);
if (p !=FNULL) if (!F.seekg(p)) return(FNULL);
return( F.VSZUpdate((void *)Str, strlen(Str)+1, mode));
}

//----- Переопределение операций над строками

String::String()
{ Str = NULL; }

String::String(char *s)
{ Str = new char[strlen(s)+1]; strcpy(Str,s); }

String::~String() { if (Str !=NULL) delete Str; }

BOOL String::IsValid() { return(Str !=NULL); }

String String::operator+(char *p)
{
String ss;
if (Str==NULL || p==NULL) return(ss);
ss.Str = new char[strlen(Str) + strlen(p) + 1];
strcpy(ss.Str,Str);
strcat(ss.Str,p);
return(ss);

}

String String::operator+(String &#38two)
{ return((*this) + two.Str); }

int String::operator[](char *sub)
{
int n,i;
if (Str==NULL) return(-1);
for (n=0; Str[n]!=0; n++)
{
for (i=0; Str[n+i]!=0; i++)
if (Str[n+i] !=sub[i]) break;
if (sub[i]==0) return(n);
}
return(-1);
}

int String::operator[](String &#38two)
{
if (Str==NULL || two.Str==NULL) return(-1);
return((*this)[two.Str]);
}

String String::operator()( int nn)
{
String ss;
if (Str==NULL) return(ss);
if (nn &#62=FSize()) return(ss);
FromString(Str + nn);
return(ss);
}

String String::operator()(int nn,int sz)
{
String ss;
if (Str==NULL) return(ss);
if (nn &#62=FSize()) return(ss);
if (nn + sz &#62=FSize()) return(ss);
ss.Str = new char[sz+1];
if (ss.Str==NULL) return(ss);
strncpy(ss.Str,Str+nn,sz);
return(ss);
}

String &#38String::operator=(String &#38right)
{
if (Str !=NULL) delete(Str);
Str = new char[strlen(right.Str)+1];
if (Str==NULL) return(*this);
strcpy(Str,right.Str);
return(*this);
}

String &#38String::operator=(char *p)
{
if (Str !=NULL) delete(Str);
Str = new char[strlen(p)+1];
if (Str==NULL) return(*this);
strcpy(Str,p);
return(*this);
}

int String::operator int()
{
return(FSize());
}

String::String(String &#38right)
{
if (right.Str==NULL) { Str = NULL; return; }
Str = new char[strlen(right.Str)+1];
if (Str==NULL) return;
strcpy(Str,right.Str);
}

int String::operator &#60 (String &#38two)
{ return (Compare(&#38two) == -1); }

int String::operator &#62 (String &#38two)
{ return (Compare(&#38two) == 1); }

int String::operator &#60=(String &#38two)
{ return (Compare(&#38two) != 1); }

int String::operator &#62=(String &#38two)
{ return (Compare(&#38two) != -1); }

int String::operator ==(String &#38two)
{ return (Compare(&#38two) == 0); }

int String::operator != (String &#38two)
{ return (Compare(&#38two) != 0); }

Ударим классом по двоичному файлу

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

//------------------------------------------------------bk8-01.cpp

&#35include &#60fstream.h&#62
&#35define FNULL -1L
typedef int BOOL;
typedef long FPTR; // Тип - указатель в файле

typedef unsigned char _FAR *BUF; // Тип - указатель буфера

// файла в stdio

class TElem;
class BinFile : public fstream
{
public:
BOOL Create(char *); // Создать пустой файл

BOOL Open(char *); // Открыть существующий

FPTR Size() // Получить длину файла и

{ seekg(0L,ios::end); // позиционироваться на

return(tellg()); } // конец файла

void *VSZLoad(int&#38); // Функции для работы с

FPTR VSZAppend(void*,int); // записями переменной

FPTR VSZUpdate(void*,int,int); // длины

BinFile() { fstream(); } //

~BinFile(){ close();} //

};

BOOL BinFile::Create(char *s)
{
int a=1;
open(s, ios::trunc | ios::out | ios::binary );
if (good()) { close(); return(1); }
return(0);
}

BOOL BinFile::Open(char * s)
{
open(s,ios::in | ios::out | ios::binary);
return(good());
}

// До сих пор функции-элементы класса представляли

// собой практически чистые вызовы библиотечных функций.

// Но поскольку значительное число объектов имеет переменную

// размерность, то класс BinFile полезно дополнить функциями,

// работающими с записями переменной длины. Напомним, что

// запись переменной длины в файле представлена целой пере-

// менной - счетчиком и следующими за ними байтами данных,

// число которых определяется счетчиком. */

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

// под нее выделяется в виде динамического массива

void *BinFile::VSZLoad(int &#38sz)
{
char *pdata;
read((BUF)&#38sz, sizeof(int));
if (!good()) return(NULL);
if ((pdata = new char[sz])==NULL ) return(NULL);
read((unsigned char *)pdata,sz);
if (good()) return((void *)pdata);
delete pdata;
return(NULL);
}

//----- При выводе записи переменной длины на место уже

// существующей проверяется размерность старой записи.

// Если она недостаточна, новая запись добавляется в конец

// файла. Значение параметра mode=1 устанавливает режим

// проверки.

FPTR BinFile::VSZUpdate(void *buf ,int sz, int mode)
{
int oldsz;
FPTR pos;
pos = tellg();
if (mode)
{
read((BUF)&#38oldsz,sizeof(int));
if (!good()) return(FNULL);
if (oldsz &#60 sz) return(VSZAppend(buf,sz));
seekg(pos);
if (!good()) return(FNULL);
}
write((BUF)&#38sz,sizeof(int));
write((BUF)buf,sz);
if (!good()) return(FNULL);
return(pos);
}

FPTR BinFile::VSZAppend(void *buf ,int sz)
{
FPTR pos;
if ((pos = Size()) ==FNULL) return(FNULL);
write((BUF)&#38sz,sizeof(int));
write((BUF)buf,sz);
if (!good()) return(FNULL);
return(pos);
}

Символы строки режима работы с файлом

.
Создание нового при отсутствии файла -----------------¬
Начальное значение указателя в файле ---------¬ ¦
Усечение при закрытии ------------¬ ¦ ¦
Запись ---------------¬ ¦ ¦ ¦
Чтение --------¬ ¦ ¦ ¦ ¦
-----T------------------------------T---T---T---T---T---¬
¦ r ¦ чтениe ¦ + ¦ - ¦ - ¦ 0 ¦ - ¦
¦ w ¦ запись ¦ - ¦ + ¦ + ¦ 0 ¦ + ¦
¦ a ¦ запись (дополнение) ¦ - ¦ + ¦ + ¦EOF¦ + ¦
¦ r+ ¦ чтение и запись (обновление) ¦ + ¦ + ¦ - ¦ 0 ¦ - ¦
¦ w+ ¦ чтение и запись (обновление) ¦ + ¦ + ¦ + ¦ 0 ¦ + ¦
¦ a+ ¦ чтение и запись (обновление) ¦ + ¦ + ¦ - ¦EOF¦ + ¦
+----+-------------------T----------+---+---+---+---+---+
¦ b ¦ двоичные данные ¦ после r,w,a,r+,w+,a+ ¦
¦ t ¦ текст ¦ ..... ¦
L----+-------------------+-------------------------------

Символы, строки, тексты

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

Синхронизация процессов

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

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

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

void P(int *sem)
{while(1)
{ RUN++; // " Критическая секция"

if (*sem!=0) // Уменьшить ненулевой семафор и выйти

{ (*sem)--; RUN--; return; }
else // Повторить (с переключение процессов)

{ RUN--; NOCLOCK++;
geninterrupt(TIMVEC);

}
}}

void V(int *sem) // Увеличить семафор

{ RUN++; (*sem)++; RUN--; // Выйти (с переключением процессов)

NOCLOCK++; geninterrupt(TIMVEC);
}
В заключение приведем пример решения классической задачи " поставщик - потребитель" , взаимодействующих через общий циклический буфер .

&#35define N 5 // Размер буфера

&#35define TW 18*2 // Время " работы" потребителя

int EMPTY=N, // Семафор " БУФЕР ПОЛОН"

FULL=0, // Семафор " БУФЕР ПУСТ"

SEMBUF=1; // Семафор " ОПЕРАЦИЯ С БУФЕРОМ"

int fst=0,lst=0; // Циклическая очередь

char BUFF[N];

void consume() // Процесс - потребитель

{ while(1)
{ WAIT(TW); // Процесс " работает"

P(&#38FULL); // P(Буфер не пуст)

P(&#38SEMBUF); // P(Операция с буфером )

char s=BUFF[fst]; // Получить из буфера

fst=(fst+1)%N; // и вывести

textbackground(BLUE);
putch(s);
V(&#38SEMBUF); // V(Операция с буфером )

V(&#38EMPTY); // V(Буфер не полон )

}}

void produce() // Процесс - производитель

{ while(1)
{
if (kbhit()) { // Если есть ввод

char c=getch();
textbackground(BLACK);
putch(c);
if (c=='\r') STOP++;
P(&#38EMPTY); // P(Буфер не полон )

P(&#38SEMBUF); // P(Операция с буфером )

textbackground(MAGENTA);
putch(c);
BUFF[lst]=c; // Поместить в буфер

lst=(lst+1)%N;
V(&#38SEMBUF); // V(Операция с буфером )

V(&#38FULL); // V(Буфер не пуст )

}}}

Синтаксис класса и объекта в Си++

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

struct dat class dat
//--------------------------------------------------------

// Определение структуры Определение класса

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

{ {
// Личная часть класса

int day,month,year; int day,month,year;
public:
// Общая часть класса

void SetDat(int,int,int); void SetDat(int,int,int);
void SetDat(char *); void SetDat(char *);
} }
void main() void main()
{ {
// Переменные a,b типа dat // Объекты a,b класса dat

dat a,b; dat a,b;
a.day = 5; // Непосредственное обращение

a.month = 12; // к личной части объекта запрещено

b.SetDat("12,12,1990"); b.Setdat("12,12,1990");
} }

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

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

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

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

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

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

-динамические, создаваемые и уничтожаемые в свободной памяти задачи в моменты вызова функций malloc и free или выполнения операторов new и delete .
Соответственно в программе возможно определение статических, автоматических и динамических объектов одного класса:

class dat
{ ....... }
dat a,b; // Статические объекты

dat *p; // Указатель на объект

void main()
{
dat c,d; // Автоматические объекты

p = new dat; // Динамический объект

delete p; // Уничтожение динамического объекта

} // Уничтожение автоматических объектов