Трансляция и ее фазы

Трансляция и компоновка

.

---------------------------------------------------------------¬
¦File Edit Search Run Compile Debug Project Options Window Help¦
L-----------------¦---¦-----------------------------------------
----------------+-¬ ¦
¦Run Ctrl+F9 ---- Команда "Make" и выполнение программы
¦... ¦ ¦
L------------------ ¦
--------------+---------¬
--------¦Compile Alt-F9 ¦
¦-------¦Make F9 ¦
¦¦------¦Link ¦
¦¦¦-----¦Build all ¦
¦¦¦¦ +-----------------------+
¦¦¦¦ ¦Rеmove messages --- Очистить окно сообщений
¦¦¦¦ L------------------------ транслятора (message)
¦¦¦L--- Безусловная трансляция и компоновка файла текущего
¦¦¦ окна или проекта
¦¦L---- Компоновка файла текущего окна или проекта
¦L----- Трансляция и компоновка файла текущего окна или
¦ проекта (каждый файл транслируется только при
¦ условии внесения изменений в текст программы,
¦ в том числе в файлы, включенные директивой include)
L------ Трансляция файла текущего окна

.

---------------------------------------------------------------¬
¦File Edit Search Run Compile Debug Project Options Window Help¦
L----------¦----------------------------------------------------
-----------+-----------¬
¦... ¦ -- Переход к строке программы, вызвавшей
¦Previous error Alt+F7 --- предыдущее сообщение (message)
¦Next error Alt+F8 ---- Переход к строке программы, вызвавшей
¦... ¦ следующее сообщение
L-----------------------

Указатель как элемент архитектуры компьютера

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

УКАЗАТЕЛЬ -- переменная, содержимым которой является адрес другой переменной.

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

-указатель, который содержит адрес переменной, ССЫЛАЕТСЯ на эту переменную или НАЗНАЧЕН на нее;

-переменная, адрес которой содержится в указателе, называется УКАЗУЕМОЙ переменной.

В Си имеется специальная операция - "*" , которую называют КОСВЕННЫМ ОБРАЩЕНИЕМ ПО УКАЗАТЕЛЮ и которая является аналогом косвенной адресации. Кроме того, имеется операция "&#38" , которая дает адрес переменной, перед именем которой она поставлена. Все это позволяет повторить изображенный выше пример с косвенной адресацией с использованием средств языка Си:

Если же эту "картинку" перевести на определения и операции языка, то получим следующее:

int a,x; // Обычные целые переменнные

int *p; // Переменная - указатель на другую

// целую переменную

a = 2000;
p = &#38a; // Указатель содержит адрес переменной a

x = x + *p; // При косвенном обращении по указателю p

// берется значение указуемой переменной a

Указатель как средство доступа к данным

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

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

Указатель на функцию как формальный параметр

//------------------------------------------------------bk56-01.cpp

//------Численное интегрирование произвольной функции

double INTEG(double a, double b, int n, double(*pf)(double))
// a,b - границы интегрирования

// n - число точек

// pf - подынтегральная функция

{
double s,h,x;
for (s=0., x=a, h = (b-a)/n; x &#60=b; x+=h)
s += (*pf)(x) * h;
return(s);
}
extern double sin(double);
void main() { cout &#60&#60 INTEG(0.,1.,40,sin)); }

Указатель на структуру -формальный параметр

void proc(man *p)
{
p-&#62name[m]... // Для работы с элементами

// структуры через указатель

cout &#60&#60 p-&#62name; // на нее используется

// операция "-&#62"

cout &#60&#60 p-&#62yy &#60&#60 p-&#62mm &#60&#60 p-&#62dd;
} // Фактические параметры -

void main() { // указатели на структурированные

int i; // переменные, полученные

proc(&#38A); // с помощью операции "&#38"

for (i=0; i&#60 10; i++) proc(&#38X[i]);
}

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

void proc(man *p, int n)
{ // Здесь p[i].name эквивалентно

int i; // (*(p+i)).name - элемент name

for (i=0; i&#60n; i++) // в i-й структурированной пере-

{ // меннной от текущего положения

p[i].name[m]... // указателя

cout &#60&#60 p[i].name; //

cout &#60&#60 p[i].yy &#60&#60 p[i].mm &#60&#60 p[i].dd;
} // Фактические параметры -

// указатели на структурированныe

proc(&#38A,1); // переменные (операция "&#38") и

proc(B,10); // массивы (идентификатор массива)

}

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

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

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

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

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

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

man *find(man *p, int n)
{
int i;
for (i=0; i&#60n; i++)
if (p[i].name[0]=='\0')
return(&#38p[i]); // или return(p+i);

return(NULL);
}

Указатель - результат функции

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

int *min(int A[], int n)
{
int *pmin, i; // Рабочий указатель, содержащий результат

for (i=1, pmin=A; i&#60n; i++)
if (A[i] &#60 *pmin) pmin = &#38A[i];
return(pmin); // В операторе return - значение указателя

}
void main() // Записать 0 на место

{ *min(B,10) = 0; } // минимального элемента массива

return &#38A[k];
return pmin+i;
return A+K;

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

Указатель типа void*

extern void *malloc(int);
int *p;
p = ( int*)malloc(sizeof(int)*20);
p[i] = i;

extern int fread(void *, int, int, FILE *);
int A[20];
fread( (void*)A, sizeof(int), 20, fd);

Как видно из примеров, преобразование типа указателя void* к любому другому типу указателя соответствует " смене точки зрения" программы на адресуемую память от " данные вообще" к " конкретные данные" и наоборот.

Указатели и массивы

.
int A[20]; int *p;

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

.
A; или &#38A[0];

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

.

p = A; p = &#38A[0];

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

.
p = &#38A[5];
p = A + 5;

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

.
A[i] *(p + i)
&#38A[i] p + i
A + i &#38p[i]
*(A + i) p[i]

Работа с областью памяти как с обычным массивом, так и через указатель полностью идентична вплоть до синтаксиса: транслятор интерпретирует конструкцию p[i] как *(p+i) для любого указателя и имени массива.

.
p++;
p +=i;
m = *p++;

Указатель может перемещаться по памяти относительно своего текущего положения.

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

Указатели и многомерные массивы

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

char A[20][80];

определяет массив из 20 массивов по 80 символов в каждом и никак иначе. Массив, таким образом, располагается в памяти по строкам;

-по аналогии имя двумерного массива с единственным индексом интерпретируется как начальный адрес соответствующего внутреннего одномерного массива. A[i] понимается как &#38A[i][0], то есть начальный адрес i-го массива символов.

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

extern void gets(char*);
char A[20][80];
int i;
for (i=0; i&#60 20; i++) // А[i] - указатель на i-ю строку

gets(A[i]); // в двумерном массиве символов

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

char *q,A[20][80];
q = A;
*(q + i*80 + j) // или

q[i*80 + j]

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

char (*p)[][80];
char (*q)[5][80];

Заметим, что круглые скобки имеют здесь принципиальное значение. В контексте определения p является переменной, при косвенном обращении к которой получается двумерный массив символов, то есть p является указателем на двумерный массив. При отсутствии скобок имел бы место двумерный массив указателей на строки. Кроме того, если не используются операции вида p++ или p+=n , связанные с размерностью указуемого массива, то наличия первого индекса не требуется.

p = q = A; // назначить p и q на двумерный массив

(*p)[i][j]... // j-ый символ в i-ой строке

// в массиве по указателю p

p+=2; // переместить p на 2 массива

// по 5 строк по 80 символов

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

Указатели как формальные параметры

void inc(int *p)
{ (*pi)++; } // аналог вызова:

// pi = &#38a

void main()
{ int a;
inc(&#38a); } // *(pi)++ эквивалентно a++

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

int sum(int A[],int n) // Исходная программа

{ int s,i;
for (i=s=0; i&#60n; i++) s+= A[i];
return s; }
int sum(int *p, int n) // Эквивалент с указателем

{ int s,i;
for (i=s=0; i&#60n; i++) s+= p[i];
return s; }

int x,B[10]={1,4,3,6,3,7,2,5,23,6};
void main()
{ x = sum(B,10); } // аналог вызова: p = B, n = 10

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

Рассмотрим третий вариант той же функции:

int sum(int *p, int n)
{ int s;
for (s=0; n &#62=0; n--) s += *p++;
return s; }

В нем операции p[i] и i++ над элементами массива заменены эквивалентной операцией *p++. Это значит, что при просмотре массива операция индексирования с линейно изменяющимся индексом может быть замена аналогичным линейным перемещением указателя.

Указатели, массивы, память

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

Указатели на элементы структуры

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

struct dat
{
int day,month,year;
void Getdat();
void Putdat();
void Nextdat();
};
void main() {
int dat::*p; // Указатель на элемент типа int в структуре dat

p = &#38dat::month; // Значение p - смещение (адрес) элемента month

// в структуре типа dat

dat x,*px = &#38x;
x.*p = 5; // Обращение по внутреннему

px-&#62*p = 5; // указателю эквивалентно

// x.month = 5;

} // px-&#62month =5;

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

fun = &#38 dat::Putdat(); // Значение fun - указатель на элемент-функцию

// Putdat в dat

(x.*fun)(); // Вызовы функции-элемента по

(px-&#62*fun)(); // указателю fun эквивалентны

// x.Putdat(); px-&#62Putdat();

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

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

· подготовки, трансляции и отладки программ в среде Borland C;

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

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

· проектирвоания программ обработки символов и строк;

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

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

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

· распознавания типа переменной по ее контексту ;

· разработки функций, имеющих формальные параметры и результат различных типов ;

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

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

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

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

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

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

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

· разработки резидентных программ и программ, работающих по прерыванию.

· разработка отдельных классов для внедрения в Си++ собственных типов данных ;

· разработки программы в виде системы классов и взаимодействующих объектов ;

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

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

Упаковка данных

//------------------------------------------------------bk48-01.cpp

//------Упаковка символов 5-битным кодом

unsigned char PACK[1000]; // Массив упакованных данных

int np; // Текущий байт

int nb; // Текущий бит

// Добавить бит в последовательность в массиве

void PutBit(int byte)
{
if (nb==0) PACK[np]=0; // Запись нового байта

PACK[np] |= (byte &#38 1) &#60&#60 nb;
nb = (nb+1) % 8; // Следующий бит

if (nb==0) np++; // Переход в следующий байт

}

// Добавить 5-битный код, начиная с младшего бита

void PutBit_5(int code)
{
int n;
for (n=0; n&#60 5; n++)
{ PutBit(code); code &#62&#62=1; }
}

&#35define ULAT 26 // Определение кодов групп

&#35define LLAT 27
&#35define DIGIT 28
int group; // Текущая группа символов

void PutChar(char c) // Упаковать и добавить символ

{
int code;
int newgroup; // Группа нового символа

if (c &#62='A' &#38&#38 c&#60='Z')
{ newgroup = ULAT; code = c - 'A'; }
else
if (c &#62='a' &#38&#38 c &#60='z')
{ newgroup = LLAT; code = c - 'a'; }
else
if (c &#62='0' &#38&#38 c &#60='9')
{ newgroup = DIGIT; code = c - '0'; }
else
if (c == ' ')
{ newgroup = DIGIT; code = 10; }
if (c == '\0')
{ newgroup = DIGIT; code = 11; }
if (newgroup != group)
{ group = newgroup; PutBit_5(group); }
PutBit_5(Code);
}

void PutString(char s[])
{ int n;
nb = np = n = 0;
do PutChar(s[n]); while(s[n++] !='\0');
}

Упаковка последовательности нулей

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

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

-нулевое значение целого счетчика обозначает конец последовательности ;

-пример неупакованной и упакованной последовательностей : 2.2, 3.3, 4.4, 5.5, 0.0, 0.0, 0.0, 1.1, 2.2, 0.0, 0.0, 4.4 и 4, 2.2, 3.3, 4.4, 5.5, -3, 2, 1.1, 2.2, -2, 1, 4.4, 0

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

//------------------------------------------------------bk44-01.cpp

void pack(int *p, double v[], int n)
{
int *pcnt=p++; // Указатель на последний счетчик

*pcnt=0;
for (int i=0; i&#60n; i++)
{ // Смена счетчика

if (i!=0 &#38&#38 (v[i]==0 &#38&#38 v[i-1]!=0) ||
v[i]!=0 &#38&#38 v[i-1]==0))
{ pcnt=p++; *pcnt=0; }
if (v[i]==0)
(*pcnt)--; // -1 к счетчику нулевых

else
{
(*pcnt)++ ; // +1 к счетчику ненулевых

*((double*)p)++ = v[i];
}
}
*p++ = 0;
}

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

//------------------------------------------------------bk44-02.cpp

int unpack(int *p, double v[])
{ int i=0,cnt;
while ((cnt = *p++)!=0) // Пока нет нулевого счетчика

{
if (cnt&#60 0) // Последовательность нулей

while(cnt++!=0)
v[i++]=0;
else // Ненулевые элементы

while(cnt--!=0) // извлечь с преобразованием

v[i++]=*((double*)p)++;
} // типа указателя

}

Упорядоченные строки

//------------------------------------------------------bk34-07.cpp

// Функция сравнивает две строки по значениям

// кодов (гарантированный алфавитный порядок для

// латинских букв). Результат сравнения:

// 0 - строки одинаковы,

// -1 - первая строка "меньше" по алфавиту, либо

// строки равны, но первая короче

// 1 - то же самое, но для второй строки

int Compare1(unsigned char s1[],unsigned char s2[])
{
int n;
for (n=0; s1[n]!='\0' &#38&#38 s2[n]!='\0'; n++)
if (s1[n] != s2[n]) break;
if (s1[n] == s2[n]) return 0;
if (s1[n] &#60 s2[n]) return -1 ;
return 1 ;
}

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

//------------------------------------------------------bk34-08.cpp

//---- Сравнение строк с заданными "весами" символов

char ORD[] = "АаБбВвГгДдЕе1234567890";
int Carry(char c)
{
int n;
if (c=='\0') return(0);
for (n=0; ORD[n]!='\0'; n++)
if (ORD[n]==c) break;
return n+1;
}
int Compare2(char s1[],char s2[])
{
int n;
char c1,c2;
for (n=0; (c1=Carry(s1[n]))!='\0' &#38&#38(c2=Carry(s2[n]))!='\0'; n++)
if (c1 != c2) break;
if (c1 == c2) return 0;
if (c1 &#60 c2) return -1;
return 1;
}

УПРАВЛЕНИЕ

В тетрисе задействованы следующие клавиши:

-A - сдвиг влево;

-D - сдвиг вправо;

-W - разворот;

-S - уронить фигуру;

- Esc - Выход из игры;

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

int a;
double b;
c = x + a &#62 b ? a : b;
// Условие ? Выражение для "истина" : Выражение для "ложь"

Условные операторы

.

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

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

Виртуальные функции - как элемент " отложенного" проектирования

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

// Класс двоичных файлов с " отложенной" функцией обработки ошибок

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

class BinFile : public fstream
{
public:
BOOL Open(char *); // Открыть существующий

virtual int OnError(char *s)
{return NULL}; // Обработка ошибок открытия

// по умолчанию - отказ от дальнейших

}; // попыток открыть файл

BOOL BinFile::Open(char * s)
{
char ss[80];
strcpy(ss,s);
while (1)
{
open(ss,ios::in | ios::out | ios::binary);
if (good()) return 1;
if (!OnError(ss)) // Виртуальная функция в производном классе

return 0; // ищет другое подходящее имя файла

}
return 1;
}

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

class MyFile : public BinFile
{
public:
virtual int OnError(char *s)
{
cout &#60&#60 " не могу открыть файл " &#60&#60 s &#60&#60 endl;
cout &#60&#60 " введите еще (CR-отказ):" ;
cin &#62&#62 s;
if (s[0]==0) return 0;
return 1;
}
};

Вложенные прерывания

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

Вопросы без ответов

//------------------------------------------------------bk13-01.cpp

//------------------------------------------------- 1

int i1 = 0xFFFF; i1 ++;
//------------------------------------------------- 2

unsigned u1,u2,u; u1 = 5; u2 = -1; u=0; if (u1 &#62 u2) u++;
//------------------------------------------------- 3

int i1 = 0x01FF; char c; c = i1; i1 = c;
//------------------------------------------------- 4

int i1 = 0x01FF;
unsigned char c; c = i1; i1 = c;
//------------------------------------------------- 5

double d1,d2,d3;
d1 = 2.56; d2 = (int)d1 + 1.5;
d3 = (int)(d1 + 1.5);
//------------------------------------------------- 6

double d1 = 2.56; int i; i = (d1 - (int)d1) * 10;
//------------------------------------------------- 7

int i1=20000,i2=20000,s ; // sizeof(int) равен 2

long s1,s2;
s1 = i1 + i2; s2 = (long)i1 + i2;
if (s1 == s2) s=0; else s=1;
//------------------------------------------------- 8

i=0; if (i++) i++;
//------------------------------------------------- 9

i=0; if (++i) i++;
//------------------------------------------------ 10

m = a &#62 b ? a : b;
//------------------------------------------------ 11

m = (a * b) &#62 0;
//------------------------------------------------ 12

m = a &#62 0 ? a : -a;

Вставляемые (inline) функции

struct dat
{
int day,month,year;
void Setdat(char *p) // Функция inline по умолчанию

{ ... } // Тело функции

};

Введение элементов многозадачности в MS DOS

- определяется размер программы в параграфах как сумма размеров сегментов данных и команд (справедливо для Small-модели памяти программы на Си);

- сохраняет вектора аппаратных и программных прерываний, по которым она будет в дальнейшем активизироваться (клавиатура, таймер, последовательный порт, прерывание 21h DOS и др.);

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

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

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

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

Ввод целого числа

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

Число: '123' '1234'
Значение: 123 1234 = 123 * 10 + 4

n = n * 10 + c[i] - '0';

где s[i]-'0' -двоичное значение цифры, представленной символом c[i].

//------------------------------------------------------bk34-05.cpp

//------Преобразование внешней формы во внутреннюю в 10СС

int StringToInt(char c[])
{
int n,i;
for (i=0; !(c[i]&#62='0' &#38&#38 c[i]&#60='9'); i++)
if (c[i]=='\0') return(0); // Поиск первой цифры

for (n=0; c[i]&#62='0' &#38&#38 c[i]&#60='9'; i++)
// Накопление целого

n = n * 10 + c[i] - '0'; // "цифра за цифрой"

return n;
}

Ввод-вывод целых чисел

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

char c; int n;
n = c - '0';
c = n + '0';

int,long) или вещественной переменной.

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

ВНЕШНЯЯ ФОРМА ПРЕДСТАВЛЕНИ ЧИСЛА -- представление числа в виде строки символов цифр, соответствующих числу в заданной системе счисления.

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

Ввод-вывод данных по прерыванию

&#35define USERVEC 0x60 // Номер вектора

// программного прерывания

&#35define IOVEC ... // Номер вектора прерывания

// устройства

int cnt; // Текущая длина строки

char far *p=NULL; // Указатель на строку

// в основной программе

// NULL - устройство свободно

void interrupt
USERINT(bp,di,si,ds,es,dx,cx,bx,ax,ip,cs,flgs)
// ds:dx - начальный адрес буфера,

// cx - размер буфера в байтах

// Программное прерывание запускает процесс вывода

// строки из буфера посимвольно по прерыванию

{
if (p!=NULL) {ax=0; return; } // Устройство занято

p = MK_FP(ds,dx); // Сформировать длинный

// указатель из регистров ds,dx

cnt=cx;
setvect(INT,IOVEC); // Установить вектор прерывания

// Разрешить прерывание от устройства

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

// по соответствующему IRQ

// и в контроллере устройства ...

ax=1; // Выйти из программного прерывания

} // с _AX=1

void interrupt INT(...) // Прерывание от устройства по

{ char *c; // готовности к выводу символа

if (cnt==0) // Вывод закончен

{ p=NULL;
// Запретить прерывание от устройства в контроллере

// прерываний по соответствующему IRQ

// и в контроллере устройства ...

}
else
{ c=*p++;
cnt--; // Получить очередной байт и вывести

outportb(c,...);
}}

Вычисление степенного полинома

При вычислении значения степенного полинома необходимы целые степени аргумента x:

.

n n-1
y = An * x + An-1 * x + ... + A1 * x + A0

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

.

y =(((...(((An*x + An-1)*x + An-2)*x +...+ A1)*x+A0
шаг 1 шаг 2 шаг 3 ... шаг n

//------------------------------------------------------bk33-03.cpp

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

double poly(double A[], double x, int n)
{
int i; double y;
for (y=A[n], i=n-1; i&#62=0; i--) y = y * x + A[i];
return(y);
}

Вычисление суммы степенного ряда

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

.

Y = S0(x) + S1(x) + S2(x) +...+ Sn-1(x) + Sn(x) + ...
k(x,n) = Sn / Sn-1

Так, например для ряда, вычисляющего sin(x), коэффициент и функция его вычисления имеют вид:

.

3 5 7 n 2n+1
sin(x)=x - x/3! + x/5! - x/7! +...+ (-1) x / (2n+1)!
.
S0 S1 S2 S3 ... Sn
.
2
k(x,n) = Sn / Sn-1 = - x / (2n (2n+1))

//------------------------------------------------------bk33-04.cpp

//--- Вычисление значения функции sin через степенной ряд

&#35include &#60iostream.h&#62
&#35include &#60math.h&#62
double sum(double x,double eps)
{
double s,sn; // Сумма и текущее слагаемое ряда

int n;
for (s=0., sn = x, n=1; fabs(sn) &#62 eps; n++)
{
s += sn;
sn = - sn * x * x / (2. * n * (2. * n + 1));
}
return s;
}
// Вычисление степенного ряда для x в диапазоне от 0.1 до 1 с шагом 0.1

void main()
{
double x;
for (x=0.1; x &#60= 1.; x += 0.1)
cout &#60&#60 "x=" &#60&#60 x &#60&#60 " sum=" &#60&#60 sum(x,0.0001) &#60&#60 " sin=" &#60&#60 sin(x) &#60&#60 endl;
}

Выделение вложенных фрагментов

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

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

//------------------------------------------------------bk34-09.cpp

// функция возвращает индекс скобки " {" для самой внутренней пары {}

int find(char c[])
{
int i; // Индекс в строке

int k; // Счетчик вложенности

int max; // Максимум вложенности

int b; // Индекс максимальной " {"

for (i=0, max=0, b=-1; c[i]!=0; i++)
{
if (c[i]== } ) k--;
if (c[i]== { )
{
k++;
if (k&#62max) { max=k; b=i; }
}
}
if (k!=0) return 0; // Защита " от дурака" , нет парных скобок

return b;
}

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

//------------------------------------------------------bk34-10.cpp

// функция возвращает индекс скобки " {" для первой внутренней пары {}

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

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

Выполнение и отладка

.

---------------------------------------------------------------¬
¦File Edit Search Run Compile Debug Project Options Window Help¦
L------------------¦--------------------------------------------
------------------+-----¬
¦Run Ctrl+F9 -- Команда "Make" и выполнение программы
¦Programm reset Ctrl+F2 -- Сброс и установка начального состояния
¦Goto cursor F4 ----¬ программы при отладке
¦Trace into F7 ---¬L- Выполнять программу до строки,
¦Step over F8 --¬¦ отмеченной курсором
¦Arguments -¬¦L-- Выполнить одну строку программы
L------------------------¦¦ с трассировкой вызываемой функции
¦L--- Выполнить одну строку программы
¦ без трассировки вызываемой функции
L---- Задать аргументы командной строки
программы при отладке
---------------------------------------------------------------¬
¦File Edit Search Run Compile Debug Project Options Window Help¦
L---------------------------------¦-----------------------------
-+-------------------------¬
--------------------------------- Inspect Alt+F4 ¦
¦-------------------------------- Evaluate/modify Ctrl+F4 ¦
¦¦ Последовательность (стек )---- Call stack Ctrl+F3 ¦
¦¦ вызовов функций ¦Watches --¬
¦¦ Установить/отменить точку----- Toggle breakpoint Ctrl+F8 ¦ ¦
¦¦ останова в текущей строке --- Breakpoints ¦ ¦
¦¦ Просмотр/редактирование ---- L--------------------------- ¦
¦¦ списка точек останова ¦
¦¦ Точки просмотра (вычисляемые выражения в окне Watch) ¦
¦¦ ----------------------+-¬
¦¦ Добавить точку просмотра ------------ Add watch Ctrl+F7 ¦
¦¦ Удалить текущую точку просмотра ----- Delete watch ¦
¦¦ Редактировать текущую точку --------- Edit watch ¦
¦¦ Удалить все точки просмотра --------- Remove all watches ¦
¦¦ L------------------------
¦L- Вычисление и модификация значения адресного выражения
¦ в отдельном окне
L-- Просмотр и модификация (инспектирование) значения текущей
переменной под курсором (Аlt+F4) или явно указанной
переменной или адресного выражения (меню). Значение
переменной или выражения отображается в отдельном окне,
окно закрывается по Esc. Alt+M - модификация выбранного
поля. Для указателя отображается и модифицируется указу-
емый тип данных, для массива - элементы массива.

Вывод двоичного числа

//------------------------------------------------------bk34-06.cpp

//------Преобразование внутренней формы во внешнюю в 10СС

void IntToString(char c[], int n)
{ int nn,k;
for (nn=n, k=1; nn!=0; k++, nn/=10); // Подсчет количества

c[k] = '\0'; // цифр числа

for (k--; k &#62=0; k--, n /= 10) // Получение цифр числа

c[k] = n % 10 + '0'; // в обратном порядке

}

Вызов функцииФункции с переменным количеством параметров

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

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

-отдельным параметром -счетчиком;

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

-форматной строкой, в которой перечислены спецификации параметров (например, функция printf).

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

Вызов оболочки

c:\bc\bin\bc - вызов оболочки
c:\bc\bin\bc a.c - вызов оболочки для файла a.c
c:\bc\bin\bc b.prj - вызов оболочки для проекта b.prj

Взаимодействие прерывающего процесса и основной программы

З нания

После изучения дисциплины студент должен знать:

· основные понятия теории информации;

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

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

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

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

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

После изучения дисциплины студент должен знать:

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

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

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

· принципы управления памятью программы, заложенные в Си, способы работы с данными пер е менного формата ;

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

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

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

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

После изучения дисциплины студент должен знать:

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

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

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

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

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

После изучения дисциплины студент должен знать:

· принципиальные отличия Си++ от Си ;

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

· принципы переопределения операций, особенности переопределения отдельных операций ;

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

· принципы организации объектно-ориентированной библиотеки и работы с ней ;

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

Задачи, задачи и еще раз задачи

Написать функцию поиска парных фрагментов

//------------------------------------------------------prg1pr-03.cpp

int find(char c[])
{
for (int i=0; c[i]!=0; i++)
for (int j=i+1; c[j]!=0; j++)
{
for (int k=0; i+k&#60j &#38&#38 c[i+k]==c[j+k]; k++);
if (k&#62=4) return i;
}
return -1;
}

Написать программу поиска самой внутренней вложенной пары скобок

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

//------------------------------------------------------prg1pr-01.cpp

// функция возвращает индекс скобки " { " для самой внутренней пары {}

int find(char c[])
{
int i; // Индекс в строке

int k; // Счетчик вложенности

int max; // Максимум вложенности

int b; // Индекс максимальной " {"

for (i=0, max=0, b=-1; c[i]!=0; i++)
{
if (c[i]== } ) k--;
if (c[i]== { )
{
k++;
if (k&#62max) { max=k; b=i; }
}
}
if (k!=0) return 0; // Защита " от дурака" , нет парных скобок

return b;
}

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

//------------------------------------------------------prg1pr-02.cpp

// функция возвращает индекс скобки " { " для первой внутренней пары {}

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

Написать программу слияния двух упорядоченных массивов в третий

Варианты "убирания" выбранного элемента:

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

- использовать индексы текущего элемента.

Последовательное проектирование программы .

1. Заголовок функции.

void sleave(int in1[], int in2[], int out[], int n)
{
_ 2. слить массивы in1[] и in2[] размерности n
_ в массив out[] размерности 2*n
}

2. Последовательно сливать по одному элементу из массивов в выходной массив - Шаг 3 - выбор цикла for (){}.

3. Переменная цикла-индекс очередного элемента в выходном массиве out .

for (int i=0; i&#60 2*n; i++)
{
_ 4. Выбрать очередной элемент, исключить и "слить" в out[i]
}

4. Используем вариант извлечения элементов "со сдвигом". В этом случае сравниваются элементы in1[0] и in2[0]. Выбирается и исключается элемент в зависимости от сравнения - выбираем условную конструкцию .

if (in1[0] &#60 in2[0])
_Выбрать in1[0], исключить и перенести в out[i]
else
_Выбрать in2[0], исключить и перенести в out[i]

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

int get(int in[], int m)
{
_Извлечь из массива in[] размерности m
_первый элемент (in[0]), сдвинуть содержимое
_влево, записать в конец "очень большое число"
_и возвратить в виде результата извлеченный элемент
}

6. С вызовом еще не написанной функции фрагмент будет иметь вид :

if (in1[0] &#60 in2[0])
out[i]=get(in1,n);
else
out[i]=get(in2,n);

7. Тело функции-простая последовательность действий :

int get(int in[], int m)
{
_1. Запомнить in[0]
_2. Сдвинуть содержимое in[] влево
_3. Записать в конец "очень большое число"
_4. Возвратить в виде результата извлеченный элемент
}

8. Окончательный вид функции:

int get(int in[], int m)
{
int v=in[0];
for (int i=1; i&#60m; i++) in[i-1]=in[i];
in[m-1]=MAXINT;
return v;
}

9. Окончательный вид функции слияния :

void sleave(int in1[], int in2[], int out[], int n)
{
for (int i=0; i&#60 2*n; i++)
if (in1[0] &#60 in2[0])
out[i]=get(in1,n);
else
out[i]=get(in2,n);
}

Задания к лабораторным работам

2. Найти в массиве элемент, наиболее близкий к среднему арифметическому суммы его элементов.

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

4. Сформировать массив простых чисел, не больших заданного.

5. Сформировать массив простых множителей заданного числа.

6. Найти наименьшее общее кратное всех элементов массива (то есть числа, которое делится на все элементы).

7. Найти наибольший общий делитель всех элементов массива (на который они все делятся без остатка).

8. Интервал между минимальным и максимальным значениями элементов массива разбить пополам и относительно этого значения разбить массив на две части (части не сортировать).

9. Задан массив, определить значение k, при котором сумма |A(1)+A(2)+…A(k)-A(k+1)+…+A(N)| минимальна (то есть минимален модуль разности сумм элементов в правой и левой части, на которые массив делится этим k).

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

11. Известно, что 1 января 1999 г. пятница. Для любой заданной даты программа должна выводить день недели.

12. Известно, что 1 января 1999 г. пятница. Программа должна найти все " черные вторники" и " черные пятницы" 1999 года (то есть 13 числа).

13. Найти в массиве наибольшее число подряд идущих одинаковых элементов (например {1,5,3,l 6,6,6,6,6,3,4,4,5,5,5} = 5).

15. Составить алгоритм решения ребуса МУХА+МУХА+МУХА=СЛОН (различные буквы означают различные цифры, старшая - не 0 ).

16. Составить алгоритм решения ребуса ДРУГ-ГУРД=2727 (различные буквы означают различные цифры, старшая - не 0 ).

17. Составить алгоритм решения ребуса КОТ+КОТ=ТОК (различные буквы означают различные цифры, старшая - не 0 ).

Заголовочные файлы

&#35include &#60iostream.h&#62 // Стандартные потоки ввода-вывода:

// ios,istream,ostream,iostream

// ifstream,ofstream,fstream

&#35include &#60iomanip.h&#62 // Манипуляторы

&#35include &#60strstream.h&#62 // Резидентные потоки ввода-вывода:

// istrstream,ostrstream,strstream

Заголовочные файлы и библиотеки

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

&#35include &#60alloc.h&#62 - заголовочный файл из системного каталога
&#35include "myhead.h" - заголовочный файл из текущего(явно указанного) каталога

Процесс подготовки библиотеки включает в себя следующие шаги:

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

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

-включение объектного модуля в библиотеку.

ЗаписьKлючИндекс

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

Житейский смысл алгоритмов и их фрагментов

Возьмем простой пример. Определим, что делает программа со значениями переменных a,b .

a=5; b=6;
c=a;
a=b;
b=c;

-на примере конкретных значений видно, что переменные меняются своими значениями, но практика показывает, что не все это замечают ;

-формально-логическое объяснение : если переменная а переписывается сначала в c , а потом в b , а перед этим b переписывается в a - то они " меняются местами" ;

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

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