Параметризованные файлы записей фиксированной длины

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

//------------------------------------------------------bk59-02.cpp

// Параметризованный файл записей фиксированной длины

&#35include &#60stdio.h&#62
&#35include &#60alloc.h&#62
struct item // Описатель столбца

{
int type; // тип столбца

int size; // размерность столбца

char name[30]; // Имя столбца

};

struct TableDef // Описатель таблицы

{
FILE *fd; // Дескриптор файла

int ns; // Количество столбцов

int nr; // Количество строк

int strlnt; // Размер строки таблицы

int size0; // Смещение строк таблицы в файле

item *ST; // Динамический массив описателей

};
//------ Открыть файл и прочитать описатели столбцов -----

TableDef *OpenTable(char *name)
{ int i; // Ниже для простоты

TableDef *p; // отсутствуют многочисленные

p= new TableDef; // проверки результата функции

if ((p-&#62fd = fopen(name,"rb+wb"))==NULL)
{ delete p; return NULL; } // Открыть файл

fread( (void*) &#38p-&#62ns,sizeof(int),1,p-&#62fd); // Чтение ns

fread( (void)&#38p-&#62nr,sizeof(int),1,p-&#62fd); // Чтение nr

p-&#62ST= new item[p-&#62ns];
fread(p-&#62ST,sizeof(item),p-&#62ns,p-&#62fd); // Чтение массива описателей

// Определение size0

p-&#62size0=sizeof(int)*2 + sizeof(item) * p-&#62ns;
for (i=0,p-&#62strlnt=0; i&#60p-&#62ns; i++) // Определение длины

p-&#62strlnt += p-&#62ST[i].size; // строки таблицы

return(p);
}
//----- Чтение элемента таблицы из столбца j строки i

// функция возвращает элемент в динамической памяти

void *getrec(int i, int j, TableDef *p)
{
void *data;
int lnt; // Суммарная размерность

int k; // столбцов от 0 до j-1

if (p-&#62fd ==NULL) return NULL;
if (p-&#62ns &#60=j || p-&#62nr &#60=i) return NULL;
for (k=0,lnt=0; k&#60j; k++) lnt += p-&#62ST[k].size;
data = malloc(p-&#62ST[j].size);
fseek(p-&#62fd, p-&#62size0 + (long)p-&#62strlnt*i + lnt, 0);
//

// Смещение строк таблицы в файле +

// Размерность i полных строк +

// Сумма длин столбцов от 0 до j-1

//

fread(data,p-&#62ST[j].size,1,p-&#62fd);
return data;
}

Параметры функций по умолчанию

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

struct dat { int day,month,year; };
//----- Функция устанавливает по умолчанию текущее значение

// года, месяца и дня

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

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

year = (y == 0) ? x.da_year : y;
month= (m == 0) ? x.da_month: m;
day = (d == 0) ? x.da_day : d;
}

Перегрузка (переопределение) функций

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

overload SetDat;
void SetDat(int dd,int mm,int yy,dat *p)
{ // Дата вводится в виде трех целых

p-&#62day=dd;
p-&#62month=mm;
p-&#62year=yy;
}
void SetDat(char *s,dat *p)
{ // Дата вводится в виде строки

sscanf(s,"%d%d%d", &#38p-&#62day, &#38p-&#62month, &#38p-&#62year);
}
void main()
{
dat a,b;
SetDat(12, 12, 1990, &#38a); // Вызов первой функции

SetDat("12,12,1990", &#38b); // Вызов второй функции

}

Функции-элементы структуры также могут быть переопределены, при этом явного объявления не требуется:

&#35include &#60stdio.h&#62
struct dat
{
int day,month,year;
void SetDat(int,int,int);
void SetDat(char *);
};
void dat::SetDat(int dd,int mm,int yy)
{
day=dd; month=mm; year=yy;
}
void dat::SetDat(char *s)
{
sscanf(s,"%d%d%d",&#38day,&#38month,&#38year);
}
void main()
{
dat a,b;
a.SetDat(12,12,1990);
b.SetDat("12,12,1990");
}

Переключение процессовСостояние процесса

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

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

Переопределение операции присваивания

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

//------------------------------------------------------bk73-10.cpp

//------Переопределение операции присваивания

class string // При переопределении операции

{ // присваивания для класса строк

char *Str; // необходимо сначала освободить

int size; // динамический массив, содержании

public: // строку в левом операнде

string &#38operator =(string&#38);
};
string &#38string::operator=(string&#38 right)
{
if (Str !=NULL) delete Str; // Освободить динамическую

// память левого операнда

size = Str.right.size; // Резервировать память под

Str = new char[size]; // размер строки правого

strcpy(Str,right-&#62Str); // Копировать строки

}

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

&#35include &#60iostream.h&#62
class myclass
{
int d1,d2;
public:
friend istream&#38 operator&#62&#62(istream&#38, myclass&#38);
friend ostream&#38 operator&#60&#60(ostream&#38, myclass&#38);
};

istream&#38 operator&#62&#62(istream &#38STR, myclass &#38DAT)
{
STR &#62&#62 DAT.d1 &#62&#62 DAT.d2;
return(STR);
}

ostream&#38 operator&#60&#60(ostream &#38STR, myclass &#38DAT)
{
STR &#60&#60 "d1=" &#60&#60 DAT.d1 &#60&#60 " d2=" &#60&#60 DAT.d2 &#60&#60 "\n";
return(STR);
}

Переопределение операций () и []

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

//------------------------------------------------------bk73-09.cpp

//------Переопределение операций [] и ()

&#35include &#60string.h&#62
class string // Строка переменной длины

{
char *Str; // Динамический массив символов

int size; // Длина строки

public:
string operator()(int,int); // Операция выделения подстроки

char operator[](int); // Операция выделения символа

int operator[](char*); // Операция поиска подстроки

};
//------ Операция выделения подстроки -------------------

string string::operator()(int n1, int n2)
{
string tmp = *this;
delete tmp.Str;
tmp.Str = new char[n2-n1+1];
strncpy(tmp.Str, Str+n1, n2-n1);
}

Переопределение операций new и delete

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

void *operator new(size_t size);
void operator delete (void *); где
void * - указатель на область памяти, выделяемую под объект,
size - размер объекта в байтах,
size_t - тип размерности области памяти, int или long.

Переопределение этих операций позволяет написать собственное распределение памяти для объектов класса.

Переопределение операторов

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

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

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

Для переопределения операции используется особая форма функции-элемента с заголовком такого вида:

. operator операция( список_параметров-операндов)

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

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

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

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

В качестве примера рассмотрим переопределение стандартных операций над датами:

//------------------------------------------------------bk73-05.cpp

//------ Операция "дата + целое"

// 1. Функция с неявным первым операндом по указателю this

// 2. Изменяется автоматический объект - копия операнда

// 3. Результат - значение автоматического объекта

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

dat dat::operator+(int n)
{
dat tmp = *this; // Объект - копия операнда

while (n-- !=0) tmp.next(); // Вызов next с объектом tmp

return(tmp); // Возврат значения объекта tmp

}
//------ Операция "дата + целое" -------------------------

// 1. Дружественная функция с полным списком аргументов

// 2. Первый параметр класса dat передается по значению,

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

// выполнении операции

// 3. Результат - значение формального параметра

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

dat operator+(dat p,int n)
{
while (n-- !=0) p.next(); // Вызов next для объекта p, копии операнда

return(p); // Возврат значения - формального параметра

}

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

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

В потоках переопределены операции &#62&#62 (ввод) и &#60&#60 (вывод) для базовых и некоторых других типов данных. Ввод-вывод осуществляется с преобразованием внутренней (двоичной) формы представления во внешнюю (символьную).

ostream &#38operator&#60&#60(char);
ostream &#38operator&#60&#60(int);
ostream &#38operator&#60&#60(long);
ostream &#38operator&#60&#60(char*);
istream &#38operator&#62&#62(char&#38);
istream &#38operator&#62&#62(int&#38);
istream &#38operator&#62&#62(long&#38);

Данное определение позволяет использовать цепочки операций :

int n;
double d;
cout &#60&#60 "n=" &#60&#60 n &#60&#60 " d=" &#60&#60 d &#60&#60 "\n";
cin &#62&#62 n &#62&#62 d;

" Подводные камни" и " маленькие хитрости"

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

if (a=b) // вместо if (a==b)

while (a &#60&#60 3) // вместо while (a &#60 3)

if (a &#38&#38 0x10) // вместо if (a &#38 0x10)

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

char c[80];
&#35define CODE 193
if (c[i] == CODE) // Эквивалентно (int)c[i] == 193

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

&#35define CODE -63 // Непонятно

&#35define CODE (char)193 // Приемлемо

&#35define CODE '\301' //

unsigned char c[80]; // Лучше всего для символов с кодами &#62 128

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

int a,b; long c;
c = a * b; // Неправильно

c = (long)a * b; // Правильно

Операция присваивания, операция "запятая" и условная операция позволяют выполнять многие действия "на лету", не выходя за пределы синтaксиса выражения в условных выражениях оперaторов if, while , например:

while ((c=getchar()) !='*') {...c...}

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

while (x0=x1, x0 &#62 0) {... x1 =f(x0) ...}

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

for (...; d&#62 0 ? a&#62b : b&#62=a; ...) {...}

В зависимости от значения переменной d меняется условие продолжения цикла for .

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

if (a&#60b)
if (a&#60c)
if (b&#60c) {...} // a &#60 b &#38&#38 a &#60 c &#38&#38 b &#60 c

else {...} // a &#60 b &#38&#38 a &#60 c &#38&#38 b &#62=c

else
if (b&#60c) {...} // a &#60 b &#38&#38 a &#62=c &#38&#38 b &#60 c

else {...} // a &#60 b &#38&#38 a &#62=c &#38&#38 b &#62=c

else ...

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

int n; n = (a &#60 b)*4 + (a &#60 c)*2 + (b &#60 c);
switch(n)
{
case 0:... break; // a &#62=b &#38&#38 a &#62=c &#38&#38 b &#62=c

case 7: ... break; // a &#60 b &#38&#38 a &#60 c &#38&#38 b &#60 c

}

Поиск выхода в лабиринте

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

int LB[10][10]={
{1,1,0,1,1,1,1,1,1,1},
{1,1,0,1,1,1,1,1,1,1},
{1,1,0,0,1,0,0,0,1,1},
{1,1,1,0,0,0,1,0,1,1},
{1,0,1,1,1,0,0,0,1,1},
{1,0,0,0,0,0,1,1,1,1},
{1,1,1,1,1,0,1,1,1,1},
{1,1,1,1,1,0,0,0,1,1},
{1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1}};

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

void step(int x,int y)
{
step(x+1,y);...
step(x,y+1);...
step(x-1,y);...
step(x,y-1);...
}

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

int step(int x,int y)
{...
if (step(x+1,y)) return 1;
if (step(x,y+1)) return 1;
if (step(x-1,y)) return 1;
if (step(x,y-1)) return 1;
return 0;
}

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

int step(int x,int y)
{...
if (step(x+1,y)) { LB[x][y]=2; return 1;}
if (step(x,y+1)) { LB[x][y]=2; return 1;}
if (step(x-1,y)) { LB[x][y]=2; return 1;}
if (step(x,y-1)) { LB[x][y]=2; return 1;}
return 0;
}

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

int step(int x,int y)
{
if (LB[x][y]==1) return 0;
if (x==0 || x==9 || y==0 || y==9) return 1; ...

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

//------------------------------------------------------bk54-01.cpp

int step(int x,int y)
{
if (LB[x][y]==1 || LB[x][y]==1) return 0; // стенки и циклы

if (x==0 || x==9 || y==0 || y==9) return 1; // края

LB[x][y]=2; // отметить точку

if (step(x+1,y)) return 1;
if (step(x,y+1)) return 1;
if (step(x-1,y)) return 1;
if (step(x,y-1)) return 1;
LB[x][y]=0; // снять отметку

return 0;
}

Поэлементная загрузка динамических структур данных

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

//------------------------------------------------------bk59-06.cpp

//------Поиск вершины с поэлементной загрузкой

ftree* FindTree(long pos, int vv, FILE *fd)
{
ftree *p, *pnext;
if (pos == FNULL) return NULL;
if ((p = new ftree)==NULL) return NULL;
fseek(fd, pos, SEEK_SET);
fread((void*)p, TSZ, 1, fd);
if (p-&#62val == vv) return p ;
if (p-&#62val &#62 vv)
pnext = FindTree(p-&#62fleft, vv, fd);
else
pnext = FindTree(p-&#62fright, vv, fd);
delete p; // Уничтожить текущую вершину

return pnext; // и вернуть вершину - потомка

}

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

//------------------------------------------------------bk59-07.cpp

//----- Добавление нового элемента в дерево, хранящееся в файле.

long AppendOne(int vv, FILE *fd)
{ // Добавить в файл новую

long pos; // вершину дерева

ftree Elem; // В памяти - автоматическая переменная

Elem.fright = Elem.fleft = FNULL;
Elem.val = vv;
fseek(fd, 0L, SEEK_END);
pos = ftell(fd);
fwrite((void*)&#38Elem, TSZ, 1, fd);
return pos;
}
// Замечание: функция добавления вершины в дерево не работает

// пустым деревом, поэтому этот случай необходимо

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

void AppendTree(long pos, int vv, FILE *fd)
{
ftree Elem; // Автоматическая переменная

fseek(fd, pos, SEEK_SET); // для хранения текущей

fread((void*)&#38Elem, TSZ, 1, fd); // вершины дерева

if (Elem.val==vv) return;
if (Elem.val &#62 vv)
{
if (Elem.fleft !=NULL)
{
AppendTree(Elem.fleft,vv,fd);
return;
}
else
Elem.fleft = AppendOne(vv,fd);
}
else
{
if (Elem.right !=NULL)
{
AppendTree(Elem.fright,vv,fd);
return;
}
else
Elem.fright = AppendOne(vv,fd);
}
fseek(fd, pos, SEEK_SET); // Обновить текущую

fwrite((void*)&#38Elem, TSZ, 1, fd); // вершину дерева

}

Понятие процессаПроцесс и программа

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

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

// Текст:

void proc(int vv)
{... if (...) proc(x); }
// Реализация:

void proc1(int vv1)
{...
if (...) proc2(x1);
}
void proc2(int vv2)
{...
if (...) proc3(x2);
}
void proc3()
{ ... }

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

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

strust message { ... данные ... }; // сообщение

void f1() // программа - процесс

{
while (1) // цикл работы процесса

{ // процесс f1, ожидающий сообщения

message *p = get_message(f1) ;

send_message(p,f3); // передать сообщение процессу f3

}}
void f2() // автономный процесс,

{ while(1) { ... }} // ни с кем не взаимодействующий

void f3() // процесс f3, принимающий сообщение

{
while (1)
{
message *p = get_message(f3);
delete p;
}}
void f4() // процесс f4, создающий и перeдающий

{ // сообщение процессу f1

while (1)
{ ...
message *p = new message;
send_message(p,f1);
}}

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

Поразрядная операция И

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

0 &#38 0 = 0
0 &#38 1 = 0
1 &#38 0 = 0
1 &#38 1 = 1

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

a = a &#38 b; или a &#38= b;

Он интерпретируется таким образом: если бит операнда b равен 0 то бит результата однозначно будет нулевым, если 1 -то результат сохранит значение бита переменной a. Такую операцию можно назвать ВЫДЕЛЕНИЕ БИТОВ по маске, или просто МАСКИРОВАНИЕ БИТОВ первого операнда. Более очевиден смысл такой операции, если b является константой -в операнде a сохраняются значения только тех битов, которые установлены в 1 в константе, остальные очищаются:

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

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

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

Поразрядную операцию " и" можно использовать и без сохранения результата как операцию ПРОВЕРКИ БИТОВ, например:

if ((a &#38 0x0200) !=0) // Проверить, установлен ли в 1

// 9-й бит переменной a

Поразрядная операция ИЛИ

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

0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1

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

0x7506 0111 0101 0000 0110
0xFF28 1111 1111 0010 1000
__________________________________
0xFF2E 1111 1111 0010 1110

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

a = a | b; или a |= b;

Тогда при значении бита операнда b, равном 0, значение соответствующего бита операнда a не меняется, а при значении 1 безусловно устанавливается в 1. Такую операцию можно назвать УСТАНОВКА БИТОВ по маске. Фиксированные биты можно установить, если второй операнд является константой. В шестнадцатеричной константе номера этих битов легко определяются из шестнадцатеричных цифр:

a |= 0x0861; // Установить в 1 биты 0,5,6,11

a |= 0x00F0; // Установить в 1 биты с 4 по 7

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

Поразрядная операция ИСКЛЮЧАЮЩЕЕ ИЛИ

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

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

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

a = a ^ b; или a ^= b;

Он интерпретируется таким образом: если бит операнда b равен 0 то бит результата сохраняет свое значение, если 1 -то меняется на противоположное (инвертируется). Такую операцию можно назвать ИНВЕРСИЯ БИТОВ по маске, установленной во втором операнде. Наиболее естественно это выглядит в том случае, когда второй операнд является константой

a ^= 0x0861; // Инвертировать биты 0,5,6,11

a ^= 0x00F0; // Инвертировать биты с 4 по 7

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

Поразрядная сортировка разделением

Одним из способов сортировки разделением (см.3.7) является поразрядная сортировка разделением. Массив сортируемых значений делится на две части так, что в левой оказываются значения со старшим значащим битом, равным 0, а в правой -со значением 1. Затем обе части массива делятся в свою очередь каждая на 2 части по значению следующего правого бита и так далее. В результате, когда мы доберемся до младшего бита, массив окажется упорядоченным. Покажем это на примере с небольшим количеством разрядов:

13 6 11 15 8 14 Исходный
1101 0110 1011 1111 1000 1110 массив
-- ------------------------ Разделение
6 15 13 11 8 14 по биту 3
-- --------- --------- Разделение
6 11 8 15 13 14 по биту 2
-- -- -- -- --------- Разделение
6 8 11 13 15 14 по биту 1
-- -- -- -- -- -- Разделение
6 8 11 13 14 15 по биту 0

В нашем примере после выполнения разделения по 3-у биту массив делится на две части, границей которых является значение 8. Затем обе части делятся пополам со значениями границ, определяемых 2-м битом, т.е. 4 и 12 и т.д..

void bitsort(int A[],int a,int b, unsigned m)
{
int i;
if (a+1 &#62= b) return; // Интервал сжался в точку

if (m == 0) return; // Проверяемые биты закончились

// Маска после сдвига стала 0

// Разделить массив на две части по значению бита,

// установленного в m, i - граница разделенных частей

bitsort(A,a,i,m &#62&#62 1);
bitsort(A,i+1,b,m &#62&#62 1);
}

Приведенная функция выполняет поразрядную сортировку части массива A, ограниченного индексами a и b. Этот интервал разделяется на две части (интервалы a..i, i+1..b), в которые попадают значения элементов массива соответственно с нулевым и единичным значением проверяемого бита. Сам бит задается маской m -переменной, в котором его значение установлено в 1. Затем функция вызывает самое себя для обработки полученных частей, для которых выполняется разделение по следующему правому биту. Для этого текущая маска m сдвигается на 1 разряд вправо. Вызов функцией самой себя называется рекурсией (см.5.4).

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

void mainsort(int B[], int n)
{
int max,i;
unsigned m;
for(max = 0, i=0; i&#60 n; i++)
if (B[i] &#62 max) max = B[i];
for (m=1; m &#60 max; m &#60&#60= 1);
m &#62&#62=1;
bitsort(B,0,n-1,m);
}

Для разделения интервала массива по заданному биту происходит по принципу "сжигания свечи с двух концов". Два индекса (i и j) движутся от концов интервала к середине, оставляя после себя слева и справа разделенные элементы. На каждом шаге производится сравнение битов по маске m в элементах массива, находящихся по указанным индексам (граница неразделенной части массива). В зависимости от комбинации битов (4 варианта) производится перестановка элементов и перемещение одного или обоих индексов к середине:

СОСТОЯНИЕ ПАРЫ ЭЛЕМЕНТОВ СДВИГ ГРАНИЦ
Оба на месте 0 1 Сдвинуть обе
Размещены наоборот 1 0 Переставить элементы, сдвинуть обе
Левый на месте 0 0 Сдвинуть левую
Правый на месте 1 1 Сдвинуть правую

{
int j,vv; // Цикл разделения массива
for (i=a, j=b; i&#60j; ) // в поразрядной сортировке
if ((A[i] &#38 m) ==0)
{
if ((A[j] &#38 m) !=0) i++,j--; // Вариант 0,1
else i++; // Вариант 0,0
}
else
{
if ((A[j] &#38 m) !=0) j--; // Вариант 1,1
else // Вариант 1,0
{
vv = A[i]; A[i]=A[j]; A[i]=vv;
i++, j--;
}
}
if ((A[i] &#38 m)!=0) i--; // Уточнить границу разделения

Последовательное переписывание вложенных фрагментов

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

Пример : a{b{c}b}a{d{e{g}e}d}a =&#62 {c}{b1b}{g}{e3e}{d4d}a2a5a

//---------------------------------------------------------------------
// Окончательный вариант
//----------------------------------------------------------------------
int find(char c[])
{
int i; // Индекс в строке
int b; // Индекс максимальной " {"
for (i=0, b=-1; c[i]!=0; i++)
{
if (c[i]== } ) return b;
if (c[i]== { ) b=i;
}
return b;
}
void copy(char c1[], char c2[])
{
int i=0; // Индекс в выходной строке
int k; // Индекс найденного фрагмента
int n; // Запоминание начала фрагмента
int m; // Счетчик фрагментов
for (m=1; (k=find(c1))!=-1; m++)
{
for (n=k; c1[k]!= } ; k++, i++) c2[i]=c1[k];
c2[i++] = c1[k++];
if (m/10!=0) c1[n++] = m/10 + 0 ;
c1[n++] = m%10 + 0 ;
for (;c1[k]!=0; k++, n++) c1[n]=c1[k];
c1[n]=0;
}
for (k=0; c1[k]!=0; k++, i++) c2[i]=c1[k];
c2[i]=0;
}

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

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

-строка с последним символом '\0' (байт 0) в памяти;

-строка с последним символом ' \n' при посимвольном вводе и выводе функциями getchar(), putchar().

Клавиатура (ввод) функция getchar()
___________ ___________
a b c d \r a b c d \n
___________ ___________

Память Файл (MS DOS)
____________ _______________
a b c d \0 a b c d \r \n
____________ _______________

Экран (вывод) Файл (VMS)
_______________ _____________
a b c d \r \n L a b c d
_______________ ___---L---___

Стандартная библиотека содержит функции ввода-вывода текста трех видов:

-посимвольный - getchar,putchar,getc,putc;

-построчный - gets,puts,fgets,fputs;

-форматный - scanf,fscanf,sscanf,printf,fprintf, sprintf .

Постановка задачи

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

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

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

-размерность коллекции не ограничена и растет по мере ее заполнения;

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

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

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

Позиционирование в текстовом файле

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

//------------------------------------------------------bk58-01.cpp

&#35include &#60stdio.h&#62
&#35include &#60conio.h&#62
FILE *fd;
char name[30];
int NP; // Количество страниц в файле

int n; // Номер текущей страницы

long POS[100]; // Массив указателей начала

int i; // страниц в файле

char str[80];
void main()
{
printf("Имя файла:"); // Открыть текстовый файл

gets(name);
if ((fd=fopen(name,"r"))==NULL) exit(1);
for (NP=0; NP&#60 100; NP++)
{ // Просмотр страниц файла

POS[NP]=ftell(fd); // Запомнить начало страницы

for (i=0; i&#60 20; i++) // Чтение строк страницы

if (fgets(str,80,fd)==NULL)
break; // Конец файла - выход из цикла

if (i &#60 20) break; // Неполная страница - выход

}
while(1)
{
clrscr();
gotoxy(1,23);
printf("Номер станицы:");
scanf("%d",&#38n);
if ((n &#60 NP) || (n &#60 0)) break;
fseek(fd,POS[n],SEEK_SET); // Указатель на страницу n

for (i=0; i&#60 20; i++) // Повторное чтение страницы

{ // и вывод на экран

if (fgets(str,80,fd)==NULL) break;
gotoxy(1,1+i);
puts(str);
}
}
}

Практические занятия ( часов)

1. . Принципы разработки класса. Классы обычных и разреженных матриц.

2. . Закрепление синтаксиса Си++ при проектировании классов.

3. . Переопределение операций.

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

5. . Классы структур данных : массивы указателей, списки, деревья.

6. . Проектирование шаблонов для классов структур данных.

7. . Взаимодействие классов в программе : класс двоичного файла, типа данных (строка. матрица) и структуры данных (массив указателей).

8. . Технология наследования классов и использования виртуальных функций.

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

1. . Общая структура языка. Данные. Переменные. Алгоритм. Блок-схема. Управляющие конструкции языка программирования. Принцип вложенности. Практика: написать программу сортировки л ю бым способом (2 часа).

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

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

4. . Проектирование программы. Сортировка вставками. Способы: вставка с раздвижкой, вставка п о гружением. Сбор фактов, структурное проектирование (2 часа).

5. . Слияние последовательностей. Модульность. Сортировка однократным слиянием с оформлением алгоритма извлечения в виде модуля (2 часа).

6. . Работа со строками. Программа сортировки слов путем выбора слова максимальной длины. М о дульность: нахождение слова максимальной длины (2 часа).

7. . Работа со строками. Проектирование " сложных" программ. Замена повторяющихся последов а тельностей символов на счетчик + символ. Сбор фактов. Структурное проектирование (2 часа).

8. . Зачетное. Работа с тестами (2 часа).

ПРЕДМЕТЫ ИЗУЧЕНИЯ

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

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

Технология объектно-ориентированного программирования и язык программирования Си++.

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

Предопределенные объекты-потоки

Следующие потоки заранее определены и открыты в программе перед вызовом функции main:

extern istream cin; // Стандартный поток ввода с клавиатуры

extern ostream cout; // Стандартный поток вyвода на экран

extern ostream cerr; // Стандартный поток вывода

// сообщений об ошибках (экран)

extern ostream cerr; // Стандартный буферизованный поток

// вывода сообщений об ошибках (экран)

Представление очереди и стека односвязным списком

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

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

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

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

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

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

//------------------------------------------------------bk53-04.cpp

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

// list *PH[2]; - заголовок очереди

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

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

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

if (ph[0] == NULL) // включение в пустую

ph[0] = ph[1] = p; // очередь

else // включение за последним

{ // элементом

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

ph[1] = p; // новый = последний

}
}
//----- Извлечение из очереди

int fromFIFO(list *ph [])
{ list *q;
if (ph[0] ==NULL) return -1; // очередь пуста

q = ph[0]; // исключение первого

ph[0] = q-&#62next; // элемента

if (ph[0] ==NULL)
ph[1] = NULL; // элемент единственный

int v = q-&#62val;
delete q;
return v;
}

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

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

Пусть имеется 3-разрядное десятичное число со знаком. Представим его в следующем виде:

-добавим слева еще одну цифру -знак числа, принимающую всего два значения: 0 -плюс, 1 -минус;

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

-каждая цифра отрицательного числа заменяется на дополнение ее до n-1, где n -основание системы счисления. Для десятичной системы -это дополнение до 9, то есть цифра, которая в сумме с исходной дает 9;

-к полученному числу добавляется 1.

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

- 3 8 6 - отрицательное число
1 6 1 3 - дополнение каждой цифры до 9
1 6 1 4 - добавление 1
___________________________________________
512 - 386 =
0 5 1 2
+ 1 6 1 4
_______
2 1 2 6 - для знака используется 0 или 1
0 1 2 6 (переполнение)
___________________________________________
119 - 386 =
0 1 1 9
+ 1 6 1 4
_______
1 7 3 3 - результат в дополнительном коде
- 2 6 6 - дополнение каждой цифры до 9
- 2 6 7 - добавление 1

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

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

-взять абсолютное значение числа в двоичной системе;

-инвертировать все разряды, включая знаковый; -добавить 1.

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

.

положительное число
15 - знаковый разряд
14-0 - абсолютное значение числа в двоичной системе
_______________________________________
0 0 0 0 0 1 1 0 1 1 0 1 1 0 0 0
_______________________________________
+ 0 6 D 8

.

отрицательное число в дополнительном коде
_______________________________________
1 1 1 1 1 0 0 1 0 0 1 0 0 1 1 1 инверсия машинного слова
_______________________________________
F 9 2 7
_______________________________________
1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 0 добавление 1
_______________________________________
F 9 2 8

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

.

Целое со знаком Значение в дополнительном коде
0 0
1 1
... ...
+32766 0x7FFE
+32767 0x7FFF
-1 0xFFFF
-2 0xFFFE
-16 0xFFF0
-32767 0x8001
не определено (-0) 0x8000

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

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

.

Дополнение 6 = Дополнение 0110 = 1001 = 9

.

24-66 = 0x18-0x42 = 0x18+(-0x42) = 0x18+0xFFBD+1 =

.

0x18+0xFFBE = 0xFFD6 = -(0x0029 + 1) = -0x2A = - 42

Представление символьных данных

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

Представление текста

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

char A[20][80];
char B[][40] = { "Строка","Еще строка","0000","abcdef"};

Первый индекс двумерного массива соответствует номеру строки, второй -номеру символа в нем:

int i,k;
for (k=0; A[i][k] !='\0'; k++)
{} // Работа c i-й строкой

Представления

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

· архитектуре компьютера с точки зрения реализации понятий алгоритма и программы;

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

· фазах трансляции и видах ошибок (лексические, синтаксические, семантические, связывания).

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

· средствах определения данных (типы данных, переменные) и алгоритмов, принятых в большинс т ве языков программирования ;

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

· процессах распределения памяти в программе, осуществляемых при трансляции и выполнении программы.

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

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

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

· основных компонентах базы данных и их физической организации ;

· особенностях программирования систем управления процессами, основанными на прерываниях .

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

· общих принципах взаимоотношений алгоритма и данных в традиционной и объектно-ориентированной технологиях ;

Преобразование к базовому типу данных

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

//------------------------------------------------------bk73-07.cpp

//------Преобразование к базовым типам данных

&#35include &#60stdio.h&#62
static int days[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
class dat
{
int day,month,year;
public:
operator int(); // Преобразование dat в int

operator long(); // Преобразование dat в long

long operator -(dat &#38p); // Операция dat-dat вычисляет

dat(); // разность дат в днях

dat(char *);
};
//------ Преобразование dat в int -------------------------

dat::operator int()
{
int r; // Текущий результат

int i; // Счетчик месяцев

for (r=0, i=1; i&#60month; i++) // Число дней в прошедших

r += days[month]; // месяцах

if ((month&#62 2) &#38&#38 (year%4==0)) r++; // Високосный год

r += day; // Дней в текущем месяце

return(r);
}
//------ Преобразование dat в long ------------------------

dat::operator long()
{
long r; // Текущий результат

r = 365 * (year-1); // Дней в предыдущих полных годах

r += year / 4; // Високосные года

r += (int)(*this); // Дней в текущем году- предыдущая

return(r); // операция (явное преобразование dat в int)

}
//-------- Операция вычисления разницы двух дат -----------

long dat::operator-(dat&#38 p)
{
return((long)(*this) - (long)p); // Преобразовать оба объекта

} // к типу long и вычислить разность

void main()
{
dat a("12-05-1990"); // Дата, заданная строкой

dat b; // Текущая дата

int c;
long d; // Явное преобразование к long

cout &#60&#60 "С 12-05-1990 прошло" &#60&#60 (long)b-(long)a &#60&#60 "дней\n";
// Явное преобразование к int

cout &#60&#60 "В этом году прошло " &#60&#60 (int)b &#60&#60 " дней\n";
c = b; // Неявное преобразование при присваивании

d = b - a; // Операция dat-dat

printf("С 12-05-1990 прошло %4ld дней\n",d);
printf("В этом году прошло %3d дней\n",c);
}

Преобразование ключей

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

f(key) -&#62 m

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

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

int Place1024(key) // Функция рассеивания для файла из

unsigned key; // 1024 записей и 16 разрядного

{ // ключа

unsigned long n,n1;
int m;
n = (unsigned long)key * key;
for (m=0, n1 = n; n1 !=0; m++, n1 &#62&#62= 1);
// Подсчет количества значащих

if (m &#60 10) return(n); // битов в n

m = (m - 10) / 2; // m - количество битов по краям

return( (n &#62&#62 m) &#38 0x3FF);
}

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

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

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

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

- первая свободная позиция, начиная от текущей;

- проверяются позиции, пропорциональные квадрату шага относительно текущей занятой, то есть m = ( f(key) + i * i ) mod n, где i - номер шага, n - размер таблицы. Такое размещение позволяет лучше "рассеивать" записи при коллизии.

Рассматриваемый метод обозначается терминами расстановка или хеширование (от hash - смешивать, перемалывать).

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

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

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

xxx(yyy &#38);

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

-при использовании операции явного преобразования типов;

-при выполнении операции присваивания, если она не переопределена в виде " xxx=yyy" (транслятором создается временный объект класса " xxx", для которого вызывается указанный конструктор и который затем используется в правой части операции присваивания);

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

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

-при определении объекта класса "xxx" одновременно с его инициализацией объектом класса "yyy" (вместо конструктора копирования)

yyy b;
xxx a = b;

При конструировании объекта класса "xxx" с использованием объекта класса "yyy" естественно должна быть обеспечена доступность необходимых данных последнего (например, через дружественность).

В качестве примера рассмотрим обратное преобразование базового типа long к типу dat -количество дней от начала летоисчисления преобразуется к дате. Здесь же рассмотрим другой класс - man , в котором одним из элементов личной части является дата. Значение этого объекта копируется при преобразовании типа man в тип dat .

//------------------------------------------------------bk73-08.cpp

//------ Преобразование переменной к объекту класса -------

static int days[]={0,31,28,31,30,31,30,31,31,30,31,30,31};

class man;
class dat
{
int day,month,year;
public:
dat(long); // Преобразование long в dat

dat(man&#38); // Преобразование man в dat

dat() {}
};

class man
{
friend class dat;
dat WasBorn; // объект класса dat в объекте класса man

public:
man(dat&#38); // Преобразование dat в man

};

//------ Преобразование man в dat ----------------------

dat::dat(man&#38 p)
{ *this = p.WasBorn; }
//------ Преобразование dat в man ------------------------

man::man(dat&#38 p)
{ WasBorn = p; }
//------ Преобразование long в dat ----------------------

dat::dat(long p)
{
year = p / 365.25; // Число лет с учетом високосных

p-=(year-1)*365L - year/4; // Остаток дней в текущем году

year++; // Начальный год - 0001

for (month=1; p &#62 0; month++)
{ // Вычитание дней по месяцам

p -= days[month];
if (month == 2 &#38&#38 year % 4 == 0) p--;
}
month--; // Восстановление последнего месяца

p += days[month];
if (month == 2 &#38&#38 year % 4 == 0) p++;
day = p + 1;
}
// Преобразование объектов класса имеет место при выполнении

// операций явного приведения типов, присваивания, а также

// при определении объектов с инициализацией их объектами

// приводимого класса

long l=1000;
dat a = l, b; // Вызов конструктора dat(long)

man c = a; // Вызов конструктора man(dat&#38)

man f(man a)
{ return(a); }

void main()
{
a = 2000L; / / Вызов конструктора dat(long)
(dat)3000L; // Вызов конструктора dat(long)

c = b; // Вызов конструктора man(dat&#38)

b = f(b); // Вызов конструктора dat(man&#38) при преобразовании

// типа параметра. Вызов конструктора man(dat&#38)

} // при преобразовании типа результата

Преобразование типов операндов

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

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

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

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

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

int n=0x7654;
char c; c = n; // Потеря значащих цифр (0x54)

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

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

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

Таким образом, при увеличении размерности целого его значение сохраняется:

int n; unsigned u;
char c=0x84; n = c; // Значение n=0xFF84

unsigned char uc=0x84; u = uc; // Значение u=0x0084

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

double d1=855.666, d2=0.5E16;
int n; n = d1; // Отбрасывание дробной части

n = d2; // Потеря значимости

Препроцессор

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

В языке Си директивы препроцессора оформлены отдельными строками программы, которые начинаются с символа "&#35". Здесь мы рассмотрим наиболее простые и "популярные".

&#35define идентификатор строка_текста

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

&#35define SIZE 100
int A[SIZE];
...
for (i=0; i&#60SIZE; i++) {...}

В данном примере вместо имени SIZE в текст программы будет подставлена строка, содержащая константу 100. Теперь, если нас не устраивает размерность массива, нам достаточно увеличить это значение в директиве define и повторно оттранслировать программу.

&#35define идентификатор(параметры) строка_с_параметрами

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

&#35define FOR(i,n) for(i=0; i&#60n; i++)
FOR(k,20) A[k]=0; // for(k=0; k&#60 20; k++) A[k]=0;

FOR(j,m+2) {...} // for(j=0; j&#60m+2; j++) {...}

В таком варианте директива define представляет собой МАКРООПРЕДЕЛЕНИЕ , а замена в тексте программы идентификатора с параметрами на строку - МАКРОПОДСТАНОВКУ .

&#35include &#60имя_файла&#62
&#35include "имя_файла"

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

&#35include &#60stdio.h&#62

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

Аналогичные средства в других языках программирования носят название МАКРОПРОЦЕССОР , МАКРОСРЕДСТВА . Полный перечень директив препроцессора приведен в Приложении 4.

Прерывание

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

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

Прежде всего прерывание является ПРОЦЕДУРОЙ, то есть некоторым алгоритмом, после выполнения которого происходит возврат к той части основной программы (точнее к тому состоянию процесса), в котором она была вызвана.

Понятие АСИНХРОННАЯ процедура означает, что она вызывается не как обычная процедура (функция) в языке программирования, то есть в основной программе (прерываемом процессе) отсутствует вызов этой процедуры в явном виде. Ее вызов осуществляется независимо от хода выполнения основной программы. Условием вызова ее является наступление некоторого внешнего по отношению к процессу события (например, поступление входных данных от внешнего устройства). Прерывающая процедура "вклинивается" между любыми последовательными шагами процесса, поэтому она должна обладать ПРОЗРАЧНОСТЬЮ , то есть ее выполнение не должно влиять на прерываемый процесс.

Можно сформулировать понятие прерывания и в терминологии процессов .

ПРЕРЫВАНИЕ - - приоритетный процесс, выполняемый по внешнему событию.

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

Prgrg-

Назад: Рабочая программа (семестр 2)

ЦЕЛЬ И ЗАДАЧИ ПРЕПОДАВАНИЯ ДИСЦИПЛИНЫ

1. ЦЕЛЬ ПРЕПОДАВАНИЯ ДИСЦИПЛИНЫ
2. ПРЕДМЕТЫ ИЗУЧЕНИЯ

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

4. РЕЗУЛЬТАТЫ ИЗУЧЕНИЯ

Представления

З нания

Умения и навыки

Приложения

9.1. Операции и приоритеты
9. 2. Интерфейс командной строки main

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

9. 4. Директивы препроцессора

9. 5. Анахронизмы языка Си

9. 6. Библиотеки стандартных функций

9.7. Таблицы кодов символов ASCII

Кодовая таблица 866 - MS DOS

Кодовая таблица 1251 - MS Windows

9. 8. Классы потоков ввода-вывода на Си++

9. 9. Работа в оболочке Borland C в DOS

Пример анализа программы : выбор возрастающих последовательностей

for (m=0, k=0, i=1; i&#60 20; i++)
if (A[i-1]&#60A[i]) k++;
else { l il f (k&#62m) m=k; k=0; }

1. Смысл цикла for() - последовательный просмотр элементов массива.

2. Смысл переменной m из выражения if (k&#62m) m=k; - выбор максимального значения из последовательности получаемых значений k.

3. A[i] - текущий элемент массива, A[i-1] - имеет смысл - предыдущий элемент массива, A[i-1] A[i] &#60/b имеет смысл - два соседних элемента массива (предыдущий и текущий) расположены в порядке возрастания.

4. Смысл переменной k из выражения if () k++; - переменная-счетчик.

5. Смысл фрагмента if (A[i-1] A[i]) k++; &#60/b - подсчет количества пар соседних элементов, расположенных в порядке возрастания.

6. После фиксации очередного значения k на предмет определения максимума в m , его значение сбрасывается, то есть процесс подсчета начинается сначала.

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

i= 1 2 3 4 5 6 7 8
A[] 3 4 5 2 1 3 4 6 2
k=0 k++ k++ k=0 k=0 k++ k++ k++ k=0
1 2 0 0 1 2 3 0
m=0 m=k m=k
2 3

Очевидно, что процесс подсчета k связан каким-то образом с процессом возрастания значений A[i]. Если несколько значений расположены подряд в порядке возрастания, то выполняется одна и та же ветка if , а k последовательно увеличивается. При появлении первого убывающего значения в последовательности счетчик сбрасывается, но перед этим его значение фиксируется на предмет максимума. Таким образом, программа определяет МАКСИМАЛЬНУЮ ДЛИНУ ПОСЛЕДОВАТЕЛЬНОСТИ ВОЗРАСТАЮЩИХ ЗНАЧЕНИЙ в массиве.

Пример проектирования : сложение смешанных чисел

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

1. Представление данных.
int a[3]; a[0] - целое, a[1] - числитель, a[2] - знаменатель.
Целое число: b[3] = {3,0,1}; - знаменатель не может быть 0.
2. Модуль
void sum(int c[], int a[], int b[])
{}
3. Шаг1 алгоритма: простая последовательность действий
{
1.1 Сложить целые
1.2 Общий знаменатель
1.3 Сложить числители
1.4 Если числитель &#62 знаменателя - скорректировать
1.5 Сократить числитель и знаменатель
}
4. Шаг 1.1
c[0] = a[0] + b[0];
5. Шаг 1.2
Общий знаменатель - наименьшее общее кратное,
минимальное числа, которое делится на числитель и
знаменатель без остатка.
6. Шаг 1.2 Конкретизируем на словах:
Алгоритм - проверять все числа от 1 до бесконечности, пока
не найдется первое которое делится на a[2] и b [2].
Замечание: можно начинать от любого a[2],b[2].
7. Шаг 1.2. Следующая конструкция:
for (начиная с b[2] до бесконечности проверять число)
{ если делится на оба знаменателя - выйти }
7. Шаг 1.2 Записывает отдельные фразы:
int N; - искомое число.
for (N=b[2]; 1; N++) - проверять от b[1] до бесконечности
N % b[2] - число делится на знаменатель
if (делится) выход из цикла.
8. Шаг 1.2. Запись алгоритма.
int N;
for (N=b[2]; 1; N++)
if (N % b[2]==0 &#38&#38 N % a[2]==0) break;
9. Шаг 1.3. Формулировка:
Сложить числители, домножив каждый на частное от
деления общего знаменателя на знаменатель дроби.
10.Шаг 1.3. Запись алгоритма.
c[1] = b[1] * (N / b[2]) + a[1] * (N / a[2]);
11.Замечание - общий знаменатель нужно сохранить в результате.
c[2] = N;
12.Шаг 1.4. Формулировка:
Если числитель =&#62 знаменателя, к целому добавить 1, а из
числителя вычесть знаменатель.
13.Шаг 1.4. Запись алгоритма.
if (c[1] &#62=c[2]) { c[1]-=c[2]; c[0]++; }
14.Шаг 1.4. Замечания: не больше, а больше или равно.
если числитель стал 0, то знаменатель нужно сделать
равным 1:
if (c[1]==0) c[2]=1;
(это, чтобы не было лишних множителей в знаменателе).
15.Шаг 1.5. Обсуждение:
Надо найти наибольший общий делитель, который делит
числитель и знаменатель без остатка. Для этого можно
проверять все числа, начиная, например, со знаменателя,
с убыванием, пока не найдем делитель, либо пока не
дойдем до 1 (кстати она всегда будет общим делителем).
16.Шаг 1.5. Формулировка:
Проверять все числа от c[2] до 1 с убыванием, пока
одновременно не разделится на c[2] и c[1].
c[1], c[2] разделить на найденное число.
17.Шаг 1.5. Следующая конструкция - простая
последовательность:
1.5.1. Поиск N
1.5.2. Деление c[1],c[2] на N
18.Шаг 1.5.1. Запись алгоритма:
for (N=c[2]; 1; N--)
if (c[2] % N==0 &#38&#38 c[1] % N==0) break;
19.Шаг 1.5.2. Запись алгоритма:
c[2] /=N; c[1]/=N;

Присваивание указателей различного типа

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

char *p, A[20];
int *q;
long *l;
p = A; q = (int*)p; l = (long*)p;

В этом примере p -указатель на область байтов, q -на область целых, l -на область длинных целых. Соответственно операции адресной арифметики *(p+i), *(q+i), *(l+i) или p[i], q[i], l[i] адресуют i-ый байт, i-ое целое и i-ое длинное целое от начала области:

p[2] = 5; // записать 5 во второй байт области A

q[1] = 7; // записать 7 в первое слово области A

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

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

Таким образом, операция присваивания указателя включает в себя:

-явное преобразование типа указателя от правого к левому ;

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

Проблема концов списка и циклические списки

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

-список пустой;

-элемент единственный;

-элемент в начале списка;

-элемент в конце списка;

-элемент в середине списка.

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

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

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

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

//------------------------------------------------------bk53-06.cpp

// Просмотр циклического списка

void scan(list2 *ph)
{
list2 *p;
if (ph ==NULL) return;
p = ph;
do { /* ... */
p = p-&#62next;
}
while (p != ph); // возврат к началу списка

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

list2 *insert(list2 *ph, int v)
{
list2 *p = new list;
p-&#62val = v;
p-&#62next = p-&#62pred = p; // указатели на самого себя

if (ph ==NULL)
return p; // включение в пустой список

list2 *pr; // текущий и предыдущий элементы списка

pr = ph-&#62pred; // в циклическом списке l предыдущий

// l от первого - последний

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

ph-&#62pred = p; // l предыдущий для первого = новый

p-&#62pred = pr; // l предыдущий для нового = последний

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

return ph;
}

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

ph = p;

Программа = алгоритм + данные

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

Программа как система взаимодействующих объектов

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

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

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

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

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

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

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

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

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

Программирование "от класса к классу"

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

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

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

Простые числа

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

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

void calc(int val, int A[], int n) {...}

Шаг 2: Сущность алгоритма состоит в проверке всех чисел от 2 до val и сохранении их в массиве, если они простые.

void calc(int val, int A[], int n)
{
int i; // Номер очередного простого часла

int m; // Очередное проверяемое число

for (i=0, m=2; i &#60 n-1 &#38&#38 m &#60 val; m++)
{
if (m - простое число)
A[i++] = m;
}
A[i] = 0;
}

Шаг 3: Конкретизируем утверждение, что m -простое число. Во-первых, оно не делится ни на одно число в диапазоне от 2 до m/2 включительно. Во-вторых, что то же самое, оно не делится ни на одно простое число от 2 до m-1. Тогда можно воспользоваться накопленными простыми числами в массиве A от A[0] до А[i-1]. Фрагмент программы, где определяется "простота" числа будет иметь вид:

int n;
for (n=0; n &#60 i; n++)
if (m % A[n]==0) break; // Разделилось нацело

if (i==n)
{ ...m - простое число... }

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

//------------------------------------------------------bk32-02.cpp

//-------Простые числа

void calc(int val, int A[], int n)
{
int i,m,k;
for (i=0, m=2; i &#60 n-1 &#38&#38 m &#60 val; m++)
{
for (k=0; k &#60 i; k++)
if (m % A[k]==0) break;
if (i==k)
A[i++] = m;
}
A[i] = 0;
}

Простые множители

Сформировать массив простых множителей заданного числа. Простые множители числа -простые числа, произведение которых дает заданное число, например: 72 = 2*2*2*3*3.

Шаг 1: Исходные данные и результат -формальные параметры функции.

void calc(int val, int A[], int n) { ... }
val -Заданное число
A - Масссив простых множителей
n - Размерность массива

Шаг 2: Форма представления результата. Последовательность простых множителей в массиве А ограничена значением 0. Основной цикл получения множителей состоит в выделении очередного множителя из val и запоминания его.

void calc(int val, int A[], int n)
{
int i; // Количество множителей

int m; // Значение множителя

for (i=0; не кончился массив и есть множители; i++)
{
// Получить значение множителя m

A[i] = m;
}
A[i]=0;
}

Шаг 3. Получение очередного простого множителя. Простой множитель -минимальное простое число, на которое исходное делится без остатка. Если оно найдено, то в следующем шаге нужно использовать частное от деления исходного числа на множитель, чтобы искать следующий, то есть val = val / m; Последний множитель даст переменной val значение 1.

void calc(int val, int A[], int n)
{
int m,i;
for (i=0; i&#60n-1 &#38&#38 val !=1; i++)
{
// Получить минимальное простое число m, нацело делящее val

val /= m; A[i] = m;
}
A[i] = 0;
}

Шаг 4: Для поиска минимального m, нацело делящего val, в цикле подряд проверяются все m, начиная с 2, до тех пор, пока остаток от деления не станет равным 0. Окончательный вариант:

//------------------------------------------------------bk32-01.cpp

//------Простые множители числа

void calc(int val, int A[], int n)
{
int m,i;
for (i=0; i&#60n-1 &#38&#38 val !=1; i++)
{
for (m=2; val % m !=0; m++);
val /= m; A[i] = m;
}
A[i] = 0;
}

РАБОЧАЯ ПРОГРАММА ( семестр

Лекции - 34 часа

Лабораторные занятия - 34 часа

Практические занятия - 17 часов

Самостоятельная работа - 34 часа

Всего - 119 часов

Аттестационный экзамен - 4 семестр

ЦЕЛЬ И ЗАДАЧИ ПРЕПОДАВАНИЯ ДИСЦИПЛИНЫ

СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

ЛИТЕРАТУРА

Работа с битовыми растрами

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

unsigned char BITS[8192];
void PutBit(int x, int y, int bit)
{
unsigned char m,b;
m = 1 &#60&#60 (x % 8); // Маска пиксела в байте

b = (bit &#38 1) &#60&#60 (x % 8); // Бит пиксела в байте

BITS[y*8 + x/8] &#38= ~m; // Очистить пиксел

BITS[y*8 + x/8] |= b; // Записать пиксел

}

При вычислении индекса в массиве BITS учитывается, что одна строка растра занимает в массиве 256/8=8 байтов и что пикселы строки размещаются в байте, начиная с младшего бита.