2014-02-09
421
Содержание
Ветвлениею
Ветвление на множестве Д такое разбиение множества Д на k ³ 2 подмножеств. Дi (i =1,k) для которых справедливы следующие 2 условия.
1. Пересечение 2 подмножеств Дi1 Ç Дi2 = Æ есть пустое множество, а
2. Обьединение всех подмножеств È Дi = Д
В результате ветвей получим дерево решений.
Вершина от которой нет ответвлений называется висячей вершиной. Если выходит две стрелки, то дерево называется диадическое дерево
Перспективное ветвление.
Пусть на каком то шаге дерево возможных вариантов, каждый из которых имеет нижнюю оценку, на очередном шаге выбирается для ветвления вершина с наименьшей минимальной оценкой. и та вершина становится перспективной.
Признак оптимальности.
F(x)=min оценки Д (последней) Пусть есть матрица Х* принадлеж Дк, такой что f(x*)= сигма (Дк) => Х* оптимальное решение.
1 Структуры и объединения.............................................................. 4
1.1 Структуры............................................................................... 4
1.2 Объединения............................................................................ 7
1.3 Битовые поля структур и объединений............................... 10
2 Функции.................................................................................... 11
2.1 Определение, описание, вызов функции............................. 11
2.2 Передача параметров в функции по значению и по указателю 13
2.3 Функции и массивы............................................................... 15
2.4 Функции с умалчиваемыми значениями параметров.......... 16
2.5 Функции с переменным числом параметров....................... 17
2.6 Передача параметров в функцию main().......................... 19
2.7 Рекурсивные и подставляемые функции.............................. 21
2.8 Функции, возвращающие указатель..................................... 22
2.9 Функции и структуры........................................................... 23
2.10 Перегрузка функций............................................................ 24
2.11 Шаблоны функций.............................................................. 25
2.12 Указатели на функции......................................................... 27
3 Работа с файлами.......................................................................... 30
3.1 Потоковый ввод-вывод......................................................... 30
3.2 Открытие и закрытие потока................................................ 31
3.3 Посимвольный ввод-вывод................................................... 34
3.4 Построчный ввод-вывод....................................................... 35
3.5 Форматированный ввод-вывод............................................. 37
3.6 Форматированные вывод в строку и ввод из строки........... 38
3.7 Блоковый ввод-вывод............................................................ 38
3.8 Произвольный доступ к файлу............................................. 39
3.6 Управление файлами и каталогами...................................... 41
4 Многофайловая компиляция........................................................ 44
5 Объекты и их атрибуты................................................................ 48
6 Ссылки........................................................................................... 51
Литература....................................................................................... 54
1 Структуры и объединения
1.1 Структуры
Структуры ‑ это совокупность поименованных объектов в общем случае разных типов. Каждая структура включает в себя один или несколько объектов (переменных, массивов, указателей, структур), называемых элементами структуры.
Структурный тип (шаблон) определяет, сколько элементов и какого типа входят в структуру. Определение шаблона структуры начинается со служебного слова struct, за которым помещаются описания входящих в структуру элементов, заключенные в фигурные скобки. Под шаблон память не выделяется.
Синтаксис определения шаблона структуры следующий:
struct имя_структурного_типа{type_1 элемент_1;
type_2 элемент_2;
......;
type_n элемент_n;};
После определения структурного типа с его помощью можно определить конкретные структуры следующим образом:
имя_структурного_типа имя_структуры; Например:
struct STR {char c;
float f;
int a[3];};
STR rec1, rec2, rec3[2];
Здесь определен структурный тип STR с элементами char c, float f, int a[3] и определены структуры: rec1 и rec2, а также массив из 2-х структур rec3. Каждая из определенных структур rec1, rec2, rec3 содержит в качестве элементов свои собственные данные, состав которых определяется структурным типом с именем STR.
Для доступа (обращения) к элементам структуры используются уточненные имена. Используется следующая конструкция языка: имя_структуры.имя_элемента_структуры.
Например:
rec1.c='z'; rec1.f=3.2;
rec1.a[0]=1; rec2.ch='w';
rec2.f=4.5; rec2.a[1]=10;
rec3[0].c='d'; rec3[1].a[2]=100;
Допустимо определять структуры вместе с определением структурного типа. Например:
struct ABC{int a1;float a2;long a3;}str1, str2;
Выделение памяти под структурную переменную осуществляется по шаблону. Например, для структур rec1, rec2 распределение памяти следующее:
| 1 байт | 2 байт | 3 байт | 4 байт | 5 байт | 6 байт | 7 байт | 8 байт | 9 байт | 10 байт | 11 байт |
| c | f | a[0] | a[1] | a[2] |
Например, для структур rec3 распределение памяти следующее:
| c | f | a[0] | a[1] | a[2] | c | f | a[0] | a[1] | a[2] |
Размер структуры можно определить с помощью операции sizeof().
int n1=sizeof(rec1); // 11 байт
int n2=sizeof(STR); // 11 байт
int n3=sizeof(rec3); // 22 байта
При определении структуры возможна её инициализация, т.е. присвоение начальных значений элементам структуры. После определения структуры ставится знак = и далее в фигурных скобках через запятую задаются значения элементов структуры согласно структурному типу. Инициализация бывает полная и неполная:
struct STR{ char ch; float f; int a[3];};
STR r1={'a',1.1,1,2,3}; // полная
STR r2={'с',2.1}; // неполная
STR r3[2]={{'w',6.6,10,20,30},{'v',7.7,40,50,60}};
Структурный тип можно ввести с помощью служебного слова typedef:
typedef struct RR{char ch;int b;}my_RR;
При этом RR и my_RR – равноправные первичное и вторичное имена структурного типа. Для определения структур можно использовать любое из имен. Например, определены две одинаковые структуры a1, a2.
RR a1; my_RR a2;
Можно определять указатели на структуру. Если определен указатель структурного типа, то память выделяется только под указатель (4 байта). Поэтому необходимо указатель на структуру проинициализировать адресом (или присвоить адрес) раннее определенной структуры этого же типа.
STR *pst1=&rec2,*pst2; pst2=&rec2;
После такого определения доступ к элементам структуры выполняется через разыменование указателя или с помощью операции ->.
(*pts1).f=8.8; (*pts2).a[0]=100;
pts2->f=9.9; pts1->a[0]=1000;
Можно создавать и уничтожать динамические структуры.
Синтаксис определения динамической структуры с помощью функций malloc() и free() следующий:
struct имя_шаблона{…}; // определение структурного типа
имя_шаблона *имя_структуры; // определение указателя на структуру
// Запрос памяти под структуру
имя_струк1=(имя_шаблона*)malloc(N*sizeof(имя_шаблона));
if(имя_струк1==NULL) // проверка выделения памяти
{puts("Ошибка выделения памяти"); return -1;}
// Программа...
free(имя_струк1); // освобождение памяти
Синтаксис определения массива динамических структур с помощью функций malloc() и free() следующий:
int N; scanf("%d",&N); // ввод количества структур
имя_шаблона *имя_струк2; // определение указателя на структуру
// Запрос памяти под массив структур
имя_струк2=(имя_шаблона*)malloc(N*sizeof(имя_шаблона));
if(имя_струк2==NULL) // проверка выделения памяти
{puts("Ошибка выделения памяти"); return -1;}
// Программа...
free(имя_струк2); // освобождение памяти
При работе с операциями new и delete определение динамических структур аналогично, отличаются запрос и освобождение памяти:
// Запрос памяти для одной структуры
имя_струк1=new имя_шаблона;
...
delete имя_струк1; // освобождение памяти одной структуры
// Запрос памяти для массива структур
имя_струк2=new имя_шаблона[N];
...
delete[]имя_струк2;// освобождение памяти массива структур
Пример. Создать одну динамическую структуру согласно заданного структурного типа и присвоить значения элементам.
#include <stdio.h>
int main()
{struct STD{char name[20]; float rating;};
STD *st; // определение указателя
st=(STD*)malloc(sizeof(STD)); // Запрос памяти
//st=new STD; // Запрос памяти
if(st==NULL) // проверка выделения памяти
{puts("Ошибка выделения памяти");return -1;}
gets(st->name);// ввод имени
st->rating=4.5; // присвоение значения
printf("%s\n%.2f\n",st->name, st->rating);
free(st); // освобождение памяти
// delete st; // освобождение памяти
return 0;}
Пример. Создать массив динамических структур согласно заданному шаблону и ввести с клавиатуры значения элементов.
#include <stdio.h>
struct MYSTR{char name[20]; int age;};
int main()
{MYSTR *b; int N;
puts("Ведите размер массива");
scanf("%d",&N);
b=(MYSTR*)malloc(N*sizeof(MYSTR); // Запрос памяти
//b=new MYSTR[N]; // Запрос памяти
if(b==NULL) // проверка выделения памяти
{puts("Ошибка выделения памяти"); return -1;}
for(int i=0;i<N;i++)
scanf("%s %d",b[i].name, &b[i].age);
for(i=0;i<N;i++)
printf("%s\n%d\n",b[i].name,b[i].age);
free(b); // освобождение памяти
//delete [] b; // освобождение памяти
return 0;}
1.2 Объединения
Объединение – это совокупность объектов различных типов, все члены которой начинаются с одного адреса. Т ип объединения (шаблон) определяет, сколько элементов и какого типа входят в него. Определение типа объединения начинается со слова union, за которым помещаются описания элементов, заключенные в фигурные скобки.
Если в структуре все элементы расположены последовательно, то объединение совмещает элементы несколько различных типов. При этом под объединение выделяется память, равная размеру максимального элемента объединения.
Для определения объединения сначала определяется тип объединения, а затем само объединение:
union имя_типа_объединения {type_1 элемент_1;
type_2 элемент_2;
......;
type_n элемент_n;};
имя_типа_объединения имя_объединения;
Например:
union UN1{int a; char ch; long b; }; // определение типа
union UN2{double d; float f[3]; }; // определение типа
UN1 un1; UN2 un2; // определение объединений
Компилятор выделит под объединение un1 память,равную длине элемента типа long.
| 1 байт | 1 байт | 1 байт | 1 байт |
| ch | |||
| a | |||
| b |
Компилятор выделит под объединение un2 память,равную длине массива f типа float.
| 4 байта | 4 байта | 4 байта |
| f[0] | f[1] | f[2] |
| d |
Для доступа (обращения) к элементам объединения используются уточненные имена. Например:
un1.a=10; un1.ch=’k’; un1.b=1193046L; // 0x123456
un2.f[0]=1.2; un2.f[1]=3.2; un2.f[2]=4.5; un2.d=7.4;
В объединении в памяти храниться только одно значение, поэтому после таких присвоений для объединения un1 в памяти будет находиться только un1.b= 1193046, а переменные изменят свои значения, un1.a=13398(0x3456), un1.ch = V (0x56). Для объединения un2 в памяти будут находиться un2.d=7.4 и un2.f[2]=4.5, а переменные un2.f[0], un2.f[1] свои значения изменят.
Объединения можно определять вместе с определением типа объединения. Например:
union N{char c[2];int a; long b;}un2;
Определять тип объединения можно с помощью typedef:
typedef union defun{double d; inti;}my_un;
defun un4; my_un un5;
В этом случае defun, my_un – имена типов объединения, un4, un5 – объединения, определенные с одинаковыми элементами.
Если имеется указатель на объединение и его значением является адрес объединения, то доступ к элементам этого объединения осуществляется через разыменование указателя или операцию ->.
union NN{int a; char c;};
NN un6, *ptru=&un6;
(*ptru).a=13; ptru->c='Y';
Инициализация объединений. При определении объединений их можно инициализировать, но в отличие от структур инициализируется только первый элемент. Например:
union{int i; char ch;} un7={200};
union UN3{char c[4]; int a[2];long g;};
union UN4{int a[2]; long g; char c[4];};
UN3 un8={'a','b','c','d'}; UN4 un9={8,9};
Элементы объединения занимают один и тот же участок памяти и могут использоваться для различных трактовок одного и того же кода:
union COM{int a; char c[2];};
// инициализация объединения com (24930=0х6162)
COM com={24930};
printf("%#x %#x\n",com.c[0],com.c[1]); // 0x62 0x61
printf("%c %c\n",com.c[0],com.c[1]); // b a
Схема размещения элементов объединения в памяти приведена ниже:
| a | c[0] | Aдрес | 0x62 |
| c[1] | Aдрес+1 | 0x61 |
Элементами объединений могут быть структуры. Например, в заголовочном файле <dos.h> определены структуры и объединение:
struct WORDREGS{unsigned int ax, bx, cx, dx;};
struct BYTEREGS{unsigned char al, ah, bl, bh;
unsigned char сl, сh, dl, dh;};
union REGS{WORDREGS x; BYTEREGS h;};
Объекты типа объединение REGS совмещают в себе объекты типа структур WORDREGS и BYTEREGS. С помощью структуры BYTEREGS обеспечивается доступ к отдельным байтам регистров ax, bx, cx, dx. Например:
union REGS rg; // выделится память в 8 байт
rg.x.ax=0x4300;// запись в регистр ax функции прерывания
int86(0x2F,&rg,&rg);// прерывание 0x2F
printf("\n al=%#x",rg.h.al);
Если на печать выведется al=0х80, то драйвер himem.sys установлен.
Объединения могут быть элементами структур. Например:
union UN {int b;char c[2];}; // выделится память 2 байта
struct STR{char st; int a[4]; UN my_u;}str1;
str1.my_u.b=500; str1.st=’z’;
Для структуры str1 выделится память в 11 байт
1.3 Битовые поля структур и объединений
Внутри структур и объединений могут быть определены битовые поля. Без битовых полей можно получить доступ только к целому числу байтов. Битовые поля представляют собой целые (знаковые или беззнаковые) значения, занимающие в памяти фиксированное число битов (от 1 до 16), предназначенные для доступа к отдельным битам данных, а также для более рационального использования памяти.
Определение структуры с битовыми полями имеет формат:
struct имя_типа_структуры {type_1 элемент_1: ширина_1;
type_2 элемент_2: ширина_2;
.........;};
имя_типа_структуры имя_структуры;
где type ‑ один из базовых типов: int, char, long, s hort, unsigned int, unsigned char, unsigned long, unsigned short;
ширина ‑ число от 1 до 16.
struct SS{int a:10; int b:3;};
SS st_b, *ptr=&st_b;
Доступ к элементам битовых полей, как и к элементам структуры:
st_b.а=12; st_b.b=2; (*ptr).a=10; ptr->b=3;
К битовым полям нельзя применять операцию взятия адреса, так как доступ возможен только к целому числу байт. Поэтому для ввода значений битовых полей с клавиатуры функцией scanf() можно использовать дополнительную переменную. Например:
scanf("%d",&st_b.b); // Ошибка
int flag; scanf(“%d”,&flag); // Правильно
st_b.b=flag;
Пример объединения, содержащего структуру с битовыми полями:
union {char ch;
struct{int a:5; // для а отвели 5 битов
int b:3; // под b отвели 3 бита
}h;
}cod; // выделится 8 бит памяти (1 байт)
cod.h.a=4; cod.h.b=2;
printf("cod.ch=%c - %#x\n",cod.ch,cod.ch);
На печать выведется: cod.ch=D – 0x44
Пример фрагмента программы объединения с битовыми полями:
union {char ch; unsigned a:1; unsigned b:2;}y;
y.ch=43; //0010 1011 в двоичном коде или 2b в 16 СС printf("y.ch=%#x y.a=%#x y.b=%#x\n",y.ch,y.a,y.b);
На экран выведется: y.ch=0x2b y.a=0x1 y.b=0x3
2.1 Определение, описание, вызов функции
Каждая программа представляет собой либо одну главную функцию с именем main(), либо функцию main() и любое количество других дополнительных функций, предназначенных для выполнения определенных действий (вычислений, обмена данными и т.д.).
Функция main() обеспечивает точку входа в откомпилированную программу. Остальные функции, используемые в программе, явно или косвенно вызываются из главной функции. Функции, входящие в программу, могут бытьопределены, как в одном с главной функцией файле, так и в отдельных файлах.
Всем именам функций по умолчанию присваивается класс памяти extern, т.е. функции глобальны, имеют внешний вид компоновки, статическую продолжительность существования (до конца выполнения программы) и доступны при определенных условиях во всех модулях программы.
Любая функция, кроме главной функции main(), должна быть определена или описана до её использования (вызова) в конкретном модуле. Определение функции имеет следующий синтаксис
тип_функции имя_функции(список_формальных_параметров)
{ тело функции }
Первая строка функцииназывается заголовком функции:
тип_функции имя_функции(список_формальных параметров)
Тип_функции – это тип возвращаемого функцией значения, т.е. базовый (например, int, float, т.д.) или производный тип вычисленного в функции значения. Если функция ничего не возвращает, то тип функции обозначается void.
Имя_функции – это любой уникальный допустимый идентификатор, например, myfunc, sum, mult, F1.
Список_формальных_параметров (или сигнатура функции) – это пусто или void, если в функцию не передаются параметры, либо список спецификаций отдельных параметров с указанием типов и имен, записанных черех запятую.
Тело функции – это последовательность определений, описаний переменных и операторов, заключенных в фигурные скобки.
Когда функция вызывается, управление передается в начало тела функции. Возврат в точку вызова функции выполняется оператором return выражение или return. В теле функции может быть несколько операторов return. При этом выход из функции может быть осуществлен в нескольких точках. Если функция не возвращает никакого значения, т.е. имеет тип void, то выражение в операторе return отсутствует и сам оператор return тоже может отсутствовать.
Пример. Функция вычисляет сумму трех переменных типа float. Функция имеет формальные параметры и один оператор return.
