Функции построчного ввода-вывода

.
-------------------------------------- Построчный ввод -¬
¦ char *gets(char *str) - стандартный ввод ¦
¦ char *fgets(char *str, int n, FILE *fd) ¦
¦ L-- str или NULL(ошибка) ¦ - явно указанный файл ¦
¦ максимальная длина строки -- ¦
L--------------------------------------------------------
------------------------------------- Построчный вывод -¬
¦ char *puts(char *str) - стандартный ввод ¦
¦ char *fputs(char *str, FILE *fd) ¦
¦ L-- str или NULL(ошибка) - явно указанный файл ¦
L--------------------------------------------------------

Примечание: при вводе-выводе все строки функции используют в качестве стандартного ограничителя строки в памяти символ '\0'. Символ конца строки '\n' уничтожается при стандартном вводе-выводе (gets - не записывает в строку, а puts автоматически добавляет при выводе) и сохраняется в строке при вводе-выводе из явно указанного файла (fgets - записывает в строку, fputs - выводит имеющийся в строке (сам не добавляет)).

Функции позиционирования и блочного ввода-вывода

.
------------------------------------- Позиционирование ---¬
¦ void rewind(FILE *fd) - установить указатель ¦
¦ в файле на начало ¦
¦ long ftell(FILE *fd) - получить значение ¦
¦ ¦ указателя в файле ¦
¦ L-- номер байта (позиция) или -1L ¦
¦ int fseek(FILE *fd, long pos, int mode) - установить ¦
¦ ¦ ¦ ¦ указатель в файле ¦
¦ ¦ номер байта (позиция)-- ¦ на заданную позицию¦
¦ ¦ способ позиционирования --------- ¦
¦ ¦ SEEK_SET(0) - от начала ¦
¦ ¦ SEEK_CUR(1) - от текущей позиции ¦
¦ ¦ SEEK_END(2) - от конца файла ¦
¦ L---- 0 или EOF (ошибка) ¦
¦ int fgetpos(FILE *fd, long *ppos) - аналоги ftell,fseek ¦
¦ int fsetpos(FILE *fd, long *ppos) с указателем, раз- ¦
¦ мещенным в памяти ¦
L----------------------------------------------------------
------------------------------------ Блочный ввод-вывод --¬
¦ int fread(void *buff, int size, int nrec, FILE *fd) ¦
¦ int fwrite(void *buff, int size, int nrec, FILE *fd) ¦
¦ ¦ ¦ ¦ L-- число записей ¦
¦ ¦ ¦ L----------- размер записи ¦
¦ ¦ L------------------- адрес памяти ¦
¦ L----------- число введенных(выведенных) записей ¦
L----------------------------------------------------------

Функции работы с символами (Заголовочный файл - ctype.h)

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

int isalnum(int c);
// латинская буква или цифры (A-Z,a-z,0-9)

int isalpha(int c);
// латинская буква (A-Z,a-z)

int isascii(int c);
// символ ASCII - код в диапазоне 0..127

// 0x00..0x1F или 0x7F.

int isdigit(int c);
// десятичная цифра (0-9)

int isgraph(int c);
// видимый (отображаемый) символ ASCII (0x21-0x7E)

int ispunct(int c);
// символ - разделитель (iscntrl или isspace)

int isspace(int c);
// символ - эквивалент пробелa: пробел (0x20), горизонталь-

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

// перевод страницы, возврат каретки (0x09-0x0D)

int isupper(int c);
// символ верхнего регистра клавиатуры

int isxdigit(int c);
// символ шестнадцатеричной цифры (0-9, A-F, a-f)

int toascii(int c);
// преобразование целого в символ кода ASCII - очистка

// старших битов, начиная с 7-го

int tolower(int c);
// преобразование символа - латинской буквы верхнего

// регистра к нижнему (большой - в маленькую). Остальные

// символы не меняются

int toupper(int c);
// преобразование латинской буквы нижнего регистра к верхнему

Функция как тип данных

Функция main

void main(void) {...}

Глобальные переменныеИнициализация

int B[10]; // B

int sum() // B

{ ...B[i]... } // B

int n; // B,n

void nf() // B,n

{...B[i]...n...} // B,n

char c[80]; // B,n,c

void main() // B,n,c

{...B[i]...n...c[k]...} // B,n,c

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

int a=5, B[10]= {1,5,4,2}, C[]={ 0,1,2,3,4,5 };

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

Границы памяти, адресуемой указателем

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

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

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

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

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

-список, элемент которого содержит массив указателей

struct elem // Элемент односвязного списка

{
elem *next;
void *pp[20]; // Массив указателей на элементы данных

};

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

int count(elem *p)
{
elem *q; int cnt; // Цикл по списку

for (cnt=0, q=p; q!=NULL; q=q-&#62next)
{
int i; // Цикл по массиву указателей

for (i=0; q-&#62pp[i]!=NULL; i++)
cnt++;
}
return cnt; }

-массив, каждый элемент которого является заголовком списка

Иерархия и конструирование типов данных

.

ПРОИЗВОДНЫЙ ТИП ДАННЫХ ОПЕРАЦИЯ ВЫДЕЛЕНИЯ СОСТАВЛЯЮЩЕГО ТИПА ДАННЫХ
Массив [] - элемент массива
Указатель * - косвенное обращение по указателю
Структура(объединение) . - элемент структуры
Указатель на структуру -&#62 - элемент структуры, адресуемой указателем
Функция () - вызов функции

Теперь рассмотрим известные нам операции с точки зрения взаимоотношения типов данных и переменных.

struct man A;
int n;
n = A.dd;

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

.
БТД --- тип выражения -----op2(op1(X))
| |
определение ПТД выделение составляющего ТД
| |
ПТД1 -- тип выражения --------- op1(X)
| |
определение ПТД выделение составляющего ТД
| |
ПТД2 --------------------------- X
определение переменной

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

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

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

Индексное дерево

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

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

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

Исключение парных фрагментов

//------------------------------------------------------prg1pr-04.cpp

void cut(char c[])
{
for (int i=0; c[i]!=0; i++)
{
if (c[i]==' ') continue;
for (int j=i+1; c[j]==c[i]; j++);
for (; c[j]!=0; j++)
{
for (int k=0; i+k&#60j &#38&#38 c[i+k]==c[j+k]; k++);
if (k&#62=4)
{
int m1,m2;
for (m1=j, m2=j+k; c[m2]!=0; m1++,m2++)
c[m1]=c[m2];
c[m1]=0;
j--; // j=i;

}
}
}
}

&#35include &#60iostream.h&#62
void main()
{
char c1[]="00000abcaa0000aabcabcaaa";
cut(c1);
cout &#60&#60 c1 &#60&#60 endl;
}

Итерационные процессы и циклы

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

Итераторы

//------------------------------------------------------bk56-02.cpp

//----- Элемент списка ------------------------------------

struct list
{
list *next; // Указатель на следующий

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

} *PH; // Пример заголовка списка

//----- Итератор: для каждого элемента списка ------------

void ForEach(list *pv, void (*pf)(void*) )
{
for (; pv !=NULL; pv = pv-&#62next)
(*pf)(pv-&#62pdata);
}
//----- Итератор: поиск первого в списке по условию ------

Итоговый экзамен (семестр)

1. Итоговый экзамен по информатике состоит в разработке программы на Си++.

2. Тематика задач, выносимых на экзамен, соответствует разделам курса Информатика:

- 4.4 - данные произвольного формата;

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

- 5.4 - рекурсия;

- 5.2, 5.3, 5.5, 5.7 - структуры данных;

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

Кроме того, возможны варианты заданий, связанные с представлением разли чных типов данных - обычных и разреженных матриц, степенных полиномов и т.п..

При подготовке к экзамену можно использовать соответствующие варианты лабораторных работ 2,3,4 семестров.

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

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

5. Пример задачи. Класс разреженных матриц. Матрица представлена динамическим массивом ненулевых коэффициентов (строка, столбец - int, значение - double).
Переопределить операцию сложения матриц, результат - объект-значение, операнды не меняются.
Комментарии : объект разреженная матрица представлен динамическим массивом структурированных переменных elem. Elem содержит " координаты" коэффициента и его значение. Кроме того объект содержит текущую размерность массива количество ненулевых коэффициентов. Частная проблема при сложении матриц определение размерности выходного массива коэффициентов. Сложение происходит в два этапа сначала определяется размерность выходных данных, а затем происходит само формирование выходного массива коэффициентов. Алгоритм сложения : создается массив коэффициентов в промежуточном (выходном) объекте. Затем в него переносятся коэффициенты первого объекта. Для каждого из коэффициентов второго объекта проверяется, есть ли соответствующий ему в первом объекте. Если есть, то коэффициент суммируется с коэффициентом первого объекта, иначе добавляется в выходной объект. Поскольку операция возвращает копию (значение) объекта-результата и объект имеет динамические данные, обязателен конструктор копирования. Используется также служебный метод (приватный), производящий поиск заданного коэффициента и возвращающий его индекс в динамическом массиве. Сложение корректно выполняется для всех случаев, в том числе и для полностью нулевых матриц. Отсутствует реакция объектов на отсутствие динамической памяти в операторе new.


struct elem{
int x,y; // координаты коэффициента

double k; // значение коэффициента

};

class matrix{
elem *pd; // Динамический массив коэффициентов

int sz; // Размерность массива

int find(int,int); // Поиск позиции коэффициента

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

matrix(); // Конструктор нулевой матрицы

~matrix();
matrix operator+(matrix&#38); // Переопределенная операция сложения

};

matrix::matrix(){
sz=0; pd=new elem; // Для единообразия объектов выделяем память

}

matrix::~matrix(){ // Деструктор

delete pd;
}

matrix::matrix(matrix &#38two){ // Конструктор копирования



pd = new elem[two.sz];
sz=two.sz;
for (int i=0; i&#60sz; i++) pd[i]=two.pd[i];
}

// Личный метод поиска " места расположения" коэффициента

int matrix::find(int xx, int yy){
for (int i=0; i&#60sz; i++)
if (pd[i].x==xx &#38&#38 pd[i].y==yy) return i;
return 1;
}

matrix matrix::operator+(matrix &#38two){
int newsz=sz; // Размерность выходного массива

for (int i=0; i&#60two.sz; i++) // Если коэффициент из второго отсутствует

if (find(two.pd[i].x, two.pd[i].y)==-1)
newsz++; // в первом - увеличить размерность на 1

matrix out(); // Выходной объект

delete out.pd; // При создании не пустой

out.pd = new elem[newsz];
for (i=0; i&#60sz; i++) // Копировать первый в выходной

out.pd[i]=pd[i];
out.sz=sz;
for (i=0; i&#60two.sz; i++) // Если коэффициент из второго присутствует

{ // в выходном сложить, иначе добавить.

int nn=out.find(two.pd[i].x, two.pd[i].y);
if (nn!=-1)
out.pd[nn]+= two.pd[i];
else
out.pd[out.sz++] = two.pd[i];
}
return out;
}

// Вариант 2. Можно использовать в качестве временного

// объекта второй операнд, если передавать его по значению

matrix matrix::operator+(matrix two){
int newsz=sz; // Размерность выходного массива

for (int i=0; i&#60two.sz; i++) // Если коэффициент из второго отсутствует

if (find(two.pd[i].x, two.pd[i].y)==-1)
newsz++; // в первом - увеличить размерность на 1

// Перераспределить память во втором объекте

two.pd=realloc(two.pd, sizeof(elem)*newsz;
for (i=0; i&#60sz; i++) // Если коэффициент из второго присутствует

{ // в выходном сложить, иначе добавить.

int nn=two.find(pd[i].x, pd[i].y);
if (nn!=-1)
two.pd[nn]+= pd[i];
else
two.pd[two.sz++] = pd[i];
}
return two;
}

Избыточность в двоичных файлах и защита от ошибок

Явное преобразование типа

double x,d; // double x,d; int n;

d = x - (int)x; // n = x; d = x - d;

Явное преобразование типа указателя " на лету"

char *p, A[20];
int *q; p = A;
q = (int*)p; p[2] = 5; // 1

(q = ( int*)p) [2] = 5; // 2

((int *)p )[2] = 5; // 3

// p - тип указателя char* до преобразования

// (int*) - явное преобразование указателя

// на байт в указатель на целое

// (int*)p -тип указателя int* после преобразования

Все они дают одинаковый результат -записывают целое 5 во второе слово области памяти, определенной как массив байтов (символов) с именем A. Однако, если в первом и втором случае используется промежуточный указатель типа int*, то в последнем случае такой указатель создается как рабочая переменная, которая получает тип int* и значение переменной p . Такая операция называется явным преобразованием типа указателя. В скобках указывается абстрактный тип данных - указатель на требуемый тип (например, int* ).

Экзаменационные билеты ( семестр )

по курсу "Информатика: алгоритмические языки и программирование" (семестр 1).

Билет 1.

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

Билет 2.

1. Представление отрицательных чисел. Дополнительный код.

2. Упорядочить массив в порядке возрастания (сортировка выбором). Ищется минимум из 0..n элементов и переставляется на первое место, ищется минимум из 1..n элементов и переставляется на второе и т.д..

Билет 3.

1. Базовые типы данных в Си: char,int,long,float,double. Модификатор типа unsigned. Особенности типа данных char. Связь с формами представления данных в ЭВМ.

2. Заменить в строке маленькие латинские буквы на большие.

Билет 4.

1. Понятие массива. Особенности определения и использования массивов в Си. Понятие индекса.

2. Подсчитать в строке количество фрагментов, симметричных относительно центрального символа (например, "abcba"), и содержащих не менее 5 символов.

Билет 5.

1. Массивы символов, строки. Работа со строками в Си.

2. Упорядочить массив в порядке возрастания методом пузырька. Сравниваются элементы 0-1,1-2,2-3,...,n-2-n-1 и переставляются, если они не в порядке возрастания. Цикл повторяется, пока число перестановок при просмотре не станет равным 0.

Билет 6.

1. Понятие переменной. Глобальные (внешние) и локальные (автоматические) переменные программы. Определение типа переменных. Инициализация простых переменных и массивов.

2. Преобразовать строку символов, содержащую число в десятичной системе в двоичную систему (целое типа int).

Билет 7.

1. Программа на Си как совокупность переменных и функций. Общая схема синтаксиса функции. Заголовок, результат, формальные параметры, тело функции. Фактические параметры.

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

Билет 8.

Кэширование структур данных при работе с файлами

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

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

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

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

Класс: тип данных, определенный программистом

Классификация операций

-арифметические ( +,-,*,/,% );

-логические ( &#38&#38, ||, ! );

-сравнения ( &#60,&#62,&#62=, =,==,!=); &#60/b

-машинно-ориентированные (операции над машинными словами, поразрядные ( &#38,|,^,~,&#60&#60,&#62&#62 );

-присваиваниe (=,++,--,+=,-=,*-,/= и т.д.);

-выделение составляющего типа данных ( (),*,[], . , -&#62 );

-явноe преобразованиe типа ( (тип) );

-условная ( ?: );

КЛАССЫ ДОПОЛНИТЕЛЬНЫХ ТИПОВ ДАННЫХ

Варианты классов:

2. Целые произвольной длины, представленные в виде строки символов (цифр).

3. Строки произвольной длины.

4. Матрицы произвольной размерности, представленные динамическим массивом коэффициентов.

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

6. Степенной многочлен произвольной степени.

Варианты переопределяемых операций:

1. Возврат содержимого объекта в динамическом массиве (байтов, символов, коэффициентов).

2. Ввод из строки символов.

3. Сложение с int.

4. Сложение с объектом того же класса.

5. Выделение компоненты объекта (символа, коэффициента) (операция []).

6. Формирование ссылки на компоненту объекта. (операция ()).

7. Получение размерности объекта (операция int).

8. Конструктор копирования объекта.

9. Конструктор объекта из символьной строки, целого, массива коэффициентов.

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

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

12.Ввод из двоичного файла произвольного доступа.

Варианты сохранения результата операции:

1. Результат возвращается в новом объекте, операнды не меняются.

2. Результат возвращается в виде ссылки на один из измененных операндов.

Классы памяти и области действия переменных

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

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

Областью действия переменной могут быть:

-тело функции или блока, ограниченное скобками;

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

-все модули программы.

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

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

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

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

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

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

Синтаксис определения: любая переменная, определенная в начале тела функции или блока (после "{"), по умолчанию является автоматической.

Классы потокового ввода-вывода

ios - базовый потоковый класс
streambuf - буферизация потоков
istream - потоки ввода
ostream - потоки вывода
iostream - двунаправленные потоки
iostream_withassign - поток с переопределенной операцией присваивания
istrstream - строковые потоки ввода
ostrstream - строковые потоки вывода
strstream - двунаправленнные строковые потоки
ifstream - файловые потоки ввода
ofstream - файловые потоки вывода
fstream - двунаправленные файловые потоки

Стандартные потоки (istream,ostream,iostream) - для работы с терминалом.

Файловые потоки (ifstream, ofstream, fstream) - для работы с файлами.

Классы структур данных

Конструктор копирования объектов

dat date2 = date1;

Однако имеются случаи, в которых создание объекта без вызова конструктора осуществляется неявно:

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

Во всех трех случаях транслятор не вызывает конструктора для вновь создаваемого объекта:

-dat2 в приведенном определении;

-создаваемого в стеке формального параметра;

-временного объекта, сохраняющего значение, возвращаемое функцией.

Вместо этого в них копируется содержимое объекта-источника:

-dat1 в приведенном примере;

-фактического параметра;

-объекта -результата в операторе return.

//------------------------------------------------------bk73-06.cpp

//------Конструктор копирования для класса строк

class string
{
char *Str;
int size;
public:
string(string&#38); // Конструктор копирования

};
string::string(string&#38 right) // Создает копии динамических

{ // переменных и ресурсов

s = new char[right-&#62size];
strcpy(Str,right-&#62Str);
}

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

Контекстная замена

Исходная строка Заменяемая Заменяющая Результат
строка строка
"abc234pe4234e" "234" "_00_" "abc_00_pe4_00_e"

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

Шаг 1: Исходные данные и результат. Строки заданы массивами символов s,s1,s2. Результирующая строка размещается в том же массиве, что и исходная. Контроль размерности не производится:

void Context(char s[], char s1[], char s2[]) {...}

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

void Context(char s[], char s1[], char s2[])
{
int n;
for (n=0; s[n] !='\0'; n++)
{
// Если начиная с n-го символа расположена

// подстрока s1, заменить ее на s2 в строке

}
}

Шаг 3: Проверка утверждения, что начиная с n-го символа в строке s расположена подстрока s2:

int i;
for (i=0; s[n+i] !='\0' &#38&#38 s1[i] !='\0'; i++)
if (s[n+i] != s1[i]) break;
if (s1[n+i]=='\0')
{
// заменить s1 на s2 в строке, начиная с s[n]

}

Шаг 4: Замена подстроки s1 на s2, начиная с n-го символа строки s, заключается перемещении "хвоста" строки s вправо или влево в зависимости от знака разности длин строк и в переписывании строки s2 на место строки s1. Для получения длины строки воспользуемся стандартной функцией strlen:

int l2,dd,k;
l2 = strlen(s2)
dd = l2 - strlen(s1);
if (dd != 0)
{
// сдвинуть "хвост" строки s на dd символов

}
for (k = 0; k &#60 l2; k++)
s[n+k] = s2[k];

Шаг 5: Для сдвига всего "хвоста" (для простоты, начиная с n-го символа) влево (dd &#60 0) необходимо все символы, начиная с n+dd перенести на dd позиций влево. Для перемещения вправо нужно сначала найти конец строки, чтобы от него производить перемещения символов с убывающим индексом

if (dd &#60 0)
{
for (k=n; s[k+dd]!='\0'; k++)
s[k] = s[k+dd];
s[k]='\0';
}
else
{
for (k=n; s[k]!='\0'; k++);
for (; k != n; k--)
s[k+dd] = s[k];
}

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

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

A.name[k]

- [] -элемент массива;

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

-() -вызов функции;

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

Заметим, что операции ("." и -&#62), соответствующие структуре, здесь не упоминаются. Это значит, что структурированный тип данных может быть определен только явно. Это связано с тем, что структура конструируется из разнородных элементов, а остальные типы данных строятся на основе однородных.

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

int *p;

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

char *p[];

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

char (*p)[][80];

Переменная, при косвенном обращении к которой получается двумерный массив, состоящий из массивов по 80 символов - указатель на двумерный массив строк по 80 символов в строке.

Контроль преобразования типов указателей

extern void* malloc(int n);
dat *p;
p = (dat*) malloc (10*sizeof(dat)); // преобразование void* в dat*

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

Лаборато р ные занятия, их содержание, объем в часа х ( часа)

2. . Анализ, ввод и отладка фрагментов программ с использованием переменных - счетчиков, накоп и телей и максимумов (bk23.doc ) (4 часа).

3. . Анализ, ввод и отладка фрагментов программ, работающих с цифрами числа (bk23.doc ) (4 часа).

4. . Анализ, ввод и отладка фрагментов программ с проверкой свойств делимости (bk23.doc ) (4 часа).

5. . Проектирование программ решения арифметических задач (bk31.doc ) (4 часа).

6. . Работа со строками (bk34.doc ) (4 часа).

7. . Итерационные циклы. Программа вычисления суммы ряда (bk33.doc) (4 часа).

8. . Сортировка и поиск. Разработка алгоритма сортировки (bk37.doc ) (4 часа).

Все лабораторные работы - 4-часовые.

1. . Указатели ( bk41.doc ) .

3. . Указатели и данные переменного формата ( bc44.doc ) .

4. . Функции с переменным количеством параметров ( bk45.doc ) .

5. . Машинно-ориентированные операции и работа с битами (bk35.doc).

6. . Массивы указателей ( bk52.doc ) .

7. . Списки ( bk53.doc ) .

8. . Заключительное занятие.

· Целые произвольной длины, представленные строкой цифр.

· Целые произвольной длины во внутреннем двоичном представлении (ди намический массив байтов).

· Матрица переменной размерности.

· Разреженная матрица переменной размерности, ненулевые элементы представлены динамическим массивом с элементами

· Смешанные числа.

· Дата, время.

· Группа строк, последовательно расположенная в памяти и ограниченная двойным 0.

· Разреженная матрица переменной размерности, ненулевые элементы представлены односвязным списком.

2. Переопределение операций (в разработанном классе).

3. Разработка класса структур данных и набора стандартных методов :

· Двоичное дерево, содержащее массив указателей.

· Дерево, содержащее указатель на элемент данных и массив указателей на потомков.

· Двухуровневый массив указателей.

· Массив указателей на односвязные списки.

· Список, каждый элемент которого содержит массив указателей.

· Двоичное дерево, содержащее односвязный список.

· Массив указателей на двоичные деревья.

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

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

6. . Разработка абстрактного базового класса объектов, хранимых в структуре данных.

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

8. . Разработка демонстрационной программы.

Все лабораторные работы - 4-часовые.

2. . Деревья ( bk55.doc ) .

3. . Указатели на функции. Итераторы ( bk56.doc ) .

4. . Иерархические структуры данных ( bk58.doc ) .

5. . Текстовые файлы с элементами прямого доступа (bk57.doc).

6. . Двоичные файлы произвольного доступа ( bk57.doc ) .

7. . Обработка прерываний и резидентные программы ( bk83.doc ) .

8. . Заключительное занятие.

Линейная рекурсия

// Рекурсивный алгоритм

int fact(int n)
{
if (n==1) return 1;
return n * fact(n-1);
}
// Циклический алгоритм

int fact(int n)
{
for (int s=1; n!=0; n--) s *=n;
return s;
}

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

Линейный кроссворд

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

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

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

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

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

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

char *w[]={"РАСИСТ","МАТРАС","МАСТЕР","СИСТЕМА","СТЕРВА",
NULL}; // Множество слов - глобальные данные

int step(char *lw) // параметр - текущее слово цепочки

Макроопределения и функции проверки флагов состояния

.
--------------------------------------------------------¬
¦ &#35define ferror(pf) ((pf)-&#62flags &#38 _F_ERR) ¦
¦ &#35define feof(pf) ((pf)-&#62flags &#38 _F_EOF) ¦
¦ &#35define fileno(pf) ((pf)-&#62fd) ¦
¦ void clearerr(FILE *pf) - сбросить _F_EER и _F_EOF ¦
L--------------------------------------------------------

Манипуляторы

endl // Помещение в выходной поток символа

// конца строки '\n' и вызов функции flush

ends // Помещение в выходной поток символа '\0'

flush // Вызов функции вывода буферизованных данных

// в выходной поток

dec // Установка основания 10 системы счисления

hex // Установка основания 16 системы счисления

oct // Установка основания 8 системы счисления

ws // Установка игнорирования при вводе пробелов

setbase(int) // Установка основания системы счисления

// (0 - 10 - по умолчанию, также 8,10,16)

resetiosflasg(long)
// Сброс флагов форматирования по маске

setiosflags(long)
// Установка флагов форматирования по маске

setfill(int) // Установка заполняющего символа

setprecision(int)
// Установка точности вывода вещественных

// чисел

setw(int) // Установка ширины поля ввода-вывода

Пример вызова манипулятора:

cout &#60&#60 15 &#60&#60 hex &#60&#60 15 &#60&#60 setbase(8) &#60&#60 15;

Машинная арифметика - целые произвольной точности

Операция сложения выполняется побайтно. Возникающий при сложении двух байтов перенос (8-й бит с маской 0x0100) используется в операции сложения следующих двух байтов:

//------------------------------------------------------bk48-02.cpp

//------Сложение целых произвольной разрядности

void add(unsigned char out[], unsigned char in1[],
unsigned char in2[], int n)
{int i;
int carry; // Бит переноса

unsigned w; // Рабочая переменная для сложения двух байтов

for (i=0, carry=0; i&#60n; i++)
{
out [i] = w = in1[i]+in2[i]+carry;
carry = (w &#38 0x0100) &#62&#62 8;
}}

Для моделирования операции умножения необходимо реализовать операцию сдвига на 1 разряд влево и вправо:

//------------------------------------------------------bk48-03.cpp

//------Сдвиг целых произвольной разрядности

void lshift(unsigned char in[], int n)
{ int carry; // Бит переноса

int i,z;
for (carry=0, i=0; i&#60n; i++)
{
z=(in[i] &#38 0x80)&#62&#62 7; // Выделить старший бит (перенос)

in[i] &#60&#60= 1; // Сдвинуть влево и установить

in[i] |=carry; // старый перенос в младший бит

carry = z; // Запомнить новый перенос

}}
void rshift(unsigned char in[], int n)
{
int carry; // Бит переноса

int i,z;
for (carry=0, i=n-1; i&#62=0; i--)
{
z = in[i] &#38 1; // Выделить младший бит (перенос)

Машинная зависимость в языках высокого уровня

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

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

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

Рассмотрим в качестве примера простую строку программы и перечислим причины ее машинной зависимости

char far *p = (char far*)0xB8000000;

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

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

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

Массив как производный тип данных

.

int а[20] = {1,5,4,7}; где
int - тип данных элементов массива
a - имя массива
20 - количество элементов массива
1,5,4,7 - инициализация (начальные значения первых 4 элементов, остальные 0)

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

Массив указателей

class MU
{
int sz; // Текущая размерность МУ

void **p; // Динамический МУ на элементы

// данных произвольного вида

int extend(); // Увеличить размерность МУ

public:
MU(int); // Конструктор - создание МУ

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

int size(); // Количество элементов данных

void *operator[](int); // Извлечение по логическому номеру

int operator()( void*,int);
// Включение по логическому номеру

void *remove(int); // Удалить по логическому номеру

void *min( int(*)(void*.void*));
// Итератор поиска минимального

};

MU::MU(int n=20)
{ sz=n; p=new void*[n]; p[0]=0; }

MU::~MU()
{ delete p; }

int MU::extend()
{
void **q=new void*[sz*2];
if (q==NULL) return 0;
for (int i=0; i&#60sz; i++) q[i]=p[i];
delete p;
sz*=2;
return 1;
}

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

int MU::size()
{ int i; for (i=0; p[i]!=NULL; i++); return i; }

void *MU::operator[](int n=-1)
{ // Извлечение по логическому номеру

int k=size(); // По умолчанию - последний

if (n==-1) n=k-1;
if (n&#60 0 || n&#62=k) return NULL; // Недопустимый номер

return p[n];


}

int MU::operator()(void *q, int n=-1)
{ // Включение по логическому номеру

int k=size();
if (n==-1) n=k; // По умолчанию - последним

if (n&#60 0 || n&#62k) return 0; // Недопустимый номер

if (k==sz-1) extend(); // При переполнении - увеличить размерность

for (int i=k; i&#62=n; i--) p[i+1]=p[i];
p[n]=q;
return 1;
}

void *MU::remove(int n=-1) // Удалить по логическому номеру

{
int k=size();
if (n==-1) n=k-1; // По умолчанию - удалить последний

if (n&#60 0 || n&#62=k) return NULL;
void *q=p[n];
for (;p[n]!=NULL; n++) // "Уплотнить" массив указателей

p[n]=p[n+1];
return q;
}

void *MU::min( int (*cmp)(void*,void*))
{ // Итератор поиска минимального

void *pmin;
int i;
for (i=0, pmin=p[0]; p[i]!=NULL; i++)
if ( (*cmp)(pmin,p[i]) &#62 0) pmin=p[i];
return pmin;
}

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

//------------------------------------------------------bk59-08.cpp

void save(char *p[], char *name)
{
FILE *fd;
int i,n;
long *pp;
if ((fd=fopen(name,"wb"))==NULL) return; // Создать двоичный файл

for (n=0; p[n]!=NULL; n++); // Определить размерность МУ

pp=new long[n]; // Создать динамический массив

fwrite((void*)&#38n,sizeof(int),1,fd); // файловых указателей в памяти

fwrite((void*)pp,sizeof(long),n,fd); // Записать в файл размерность

for (i=0; i&#60n; i++) // массива файловых указателей

{ // и сам массив (занять место)

pp[i]=ftell(fd); // Записать строку в файл в виде

int sz=strlen(p[i])+1; // записи переменной длины и

fwrite((void*)&#38sz,sizeof(int),1,fd); // сохранить адрес в массиве

fwrite((void*)p[i],sz,1,fd); // файловых указателей

}
fseek(fd,sizeof(int),SEEK_SET); // Обновить в файле массив

fwrite((void*)pp,sizeof(long),n,fd); // файловых указателей

fclose(fd);
}

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

Массивы указателей на строки

char *pc[20];

Существуют различные варианты формирования массива указателей на строки.

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

char *pc[] = { "aaa", "bbb", "ccc", NULL};

Вариант 2. Массив указателей создается статически, для размещения строк используется двумерный массив символов (массив строк), указатели назначаются программно:

char *pc[20], cc[19][80];
for (i=0; i&#60 19; i++) pc[i] = cc[i];
pc[i] = NULL;

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

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

char *pc[20], *p, c[80];
for (i=0; i&#60 19; i++)
{
gets(c); // ввод строки

if (strlen(c)==0) break; // пустая строка - конец

p = new char [strlen(c)+1]; // динамический массив

strcpy(p,c); // под строку

pc[i] = p;
}
pc[i] = NULL;

Вариант 4. Массив указателей также создается в динамической памяти:

char **pp, *p, c[80];
pp = new char* [20]; // динамический массив

for (i=0; i&#60 19; i++) // из 20 указателей char*

{
gets(c); // ввод строки

if (strlen(c)==0) break; // пустая строка - конец

p = new char [strlen(c)+1]; // динамический массив

strcpy(p,c); // под строку

pp[i] = p;
}
pp[i] = NULL;

Математические функции (math.h)

int abs(int n); // Абсолютное значение n

double acos(double x); // Функция арккосинуса

double asin(double x); // Функция арксинуса

double atan(double x); // Функция арктагенса

double atan2(double y,double x); // Функция арккосинуса y/x

double cos(double x); // Функция косинуса (x - в радианах)

double cosh(double x); // Функция гиперболического косинуса

double exp(double x); // Экспоненциальная функция

double fabs(double x); // Абсолютное значение x

double floor(double x); // Целая часть x

double fmod(double y,double x); // Остаток от деления y на x

double hypot(double y,double x); // Гипотенуза катетов y,x

long labs(dong n); // Абсолютное значение n

double ldexp(double x, int n); // Значение x * 2 ^ n

double log(double x); // Функция натурального логарифма

double log10(double x); // Функция десятичного логарифма

double poly(double x, int n, double c[]);

// Степенной полином

// y = c[n]*x ^n + c[n-1]*x ^(n-1) + ... + c[1]*x + c[0]

double pow(double y,double x); // Функция y в степени x

double pow10(int n); // Функция 10 в степени n

double sin(double x); // Функция синуса

double sinh(double x); // Функция гиперболического синуса

double sqrt(double x); // Функция квадратного корня

double tan(double x); // Функция тангенса

double tanh(double x); // Функция гиперболического тангенса

Механизм прерываний в архитектуре I

void interrupt (*IVEC[256])();

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

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

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

Процесс вхождения в прерывание по вектору N можно условно проиллюстрировать средствами Си :

Многоуровневые индексы

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

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

Многоуровневые массивы указателей на строки

//------------------------------------------------------bk52-04.cpp

&#35define SIZE0 100
char **loadfile(FILE *fd)
{
char **pp,*q,str[80];
int i;
pp = new char* [SIZE0]; // Создать динамический

if (pp ==NULL) return(NULL); // массив указателей

for (i=0; fgets(str,80,fd) !=NULL; i++)
{ // Читать строку из файла

q = new char [strlen(str)+1];
if (q==NULL) return(NULL); // Создать динамический

strcpy(q,str); // массив символов и

// копировать туда строку.

pp[i] = q; // Сохранить указатель

if ((i+1) % SIZE0 ==0) // Расширить массив указа-

{ // телей при переполнении

pp = realloc(pp,sizeof(char *) *(i+1+SIZE0));
if (pp ==NULL) return(NULL);
}
}
pp[i] = NULL; // Ограничитель массива

return pp; // указателей

}

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

char **pp[20]; char ***ppp;

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

Многоуровневые указатели

double **pp;

-указатель на одиночный указатель на переменную типа double ;

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

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

-указатель на массив, содержащий указатели на массивы переменных типа double .

double **pp, *pd[20];
pp = pd; // или pp = &#38pd[0];

*(pp+i) // или pp[i]

**(pp+i) // или *pp[i]

Здесь повторяется та же самая система эквивалентности обычных массивов и указателей -типов double* и double[], но применительно не к массивам обычных переменных, а к массивам указателей. Короче говоря, типы double** и double *[] различаются так же, как указатель-переменная и указатель-константа.

//------------------------------------------------------bk52-02.cpp

double **create(int sz)
{ double **pp,*q; // создать динамический массив

int i; // указателей размерностью sz+1

pp = new double *[sz+1];
for (i=0; i&#60sz; i++) // создать динамическую переменную

{
q = new double;
*q = i; // указатель занести в динамический

pp[i] = q; // массив

}
pp[sz] = NULL;
return(pp); // возвратить указатель

} // на динамический массив указателей

Модель системы процессов, работающих в разделении времени

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

// Дескриптор процесса -------------------------------------

struct PROCESS
{
unsigned SS,SP; // Указатель стека процесса

char *PS; // Область стека процесса

unsigned STATUS; // Слово состояния процесса

unsigned DELAY; // Тайм - аут

}
TASK[NT], // Массив дескрипторов процессов

*PT; // Указатель на дескриптор текущего процесса

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

-АКТИВЕН - в данный момент выполняется (или прерван),

-ГОТОВ - может быть выполнен ;

-БЛОКИРОВАН - не может быть выполнен по каким-либо внешним причинам.

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

// Биты блокировки процесса ---------------------------

&#35define TWAIT 1 // Тайм - аут процесса

&#35define IO 2 // Ввод - вывод

&#35define MESS 4 // Ожидание сообщения

&#35define OFF 16 // Не активен