Extern. Внутренняя переменная.

Является ссылкой на переменную с тем же самым именем, определенную на внешнем уровне в любом исходном файле программы. Целью внутреннего объявления Extern является доступ к определению переменной внешнего уровня. Внутреннее объявление Extern не влияет область действия глобальных переменных в любой другой части программы.

main()

static int i=0;

{

func();

}

int func

{

i++;

printf (“%d”,i);

}

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

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

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

Пример:

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

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

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

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

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

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

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

Данный способ выделения памяти приводит к проблеме фрагментации памяти. Например, освобождение каждого второго 2-байтовогоэлемента из массива из 100 элементов не приведет к возможности выделения памяти под 100-байтовый элемент, если ранее такой возможности не было.

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

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

Задача.

Написать программу для хранения матрицы целых чисел размером 50х50 элементов. Вводят их значение с клавиатуры и выводит ненулевые по 5 значений в строке с указанием индекса элемента. После чего память освобождается, затем выделяется для хранения вектора из 100 действительных чисел, которые вводятся с клавиатуры, печатается минимальный и максимальный элементы, после чего память освобождается. Функция malloc, возвращаемое значение указатель на выделенную область памяти, NULL если данное количество недоступно. Параметр: количество байт. Free – параметр-указатель, ранее полученный с помощью функции выделения памяти.

#include<malloc.h>

#include<conio.h>

#include<stdio.h>

main()

{

int *A;

int i,j,k,min,max;

A=(int*)malloc (50*sizeof(50 int))

for (i=0;i<50;i++)

{

for (j=0;j<50;j++)

{

A[i*50+j]=(int*)malloc (sizeof(int));

}

}

for (i=0;i<50;i++)

{

for (j=0;j<50;j++)

{

printf (“A[%d][%d]=%d”,i,j);

scanf (“%d”,&A[i][j]);

}

}

for (i=0;i<50;i++)

{

for (j=0;j<50;j++)

{

if (A[i][j]!=0)

for (k=0;k<5;k++)

{

printf (“A[%d][%d]=%d”,A[i][j]);

}

printf (“\n”);

}

}

free A;

A=malloc(200*sizeof(float));

min=A[0], max=A[0]

for (j=0;j<100;j++)

{

printf (“A[%d]=%d”,j);

scanf (“%d”,&A[j]);

if(A[j]<min)min=A[j];

if(A[j]>max)max=A[j];

}

printf (“%f\t%f”,max,min);

free A;

getch();

}

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

Использование указателей.

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

Однонаправленный (односвязный) список.

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

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

head

Создание связного списка.

1. Выделить память для хранения адреса головы;

2. Выделить память для хранения элементов списка;

3. Обнулить поле адреса;

4. Записать в поле данных содержащую информацию;

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

Добавление элемента в конец списка.

1. Присвоить указателю адрес головы списка;

2. Проанализировать значение поля адреса. Пока оно не равно 0, присваивать указателю значен000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ие поля адреса.

3. Создать элемент списка и записать его в поле адрес конца списка.

Просмотр связного списка.

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

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

3. если достигнуто значение адреса 0, выдать сообщение, что элемент не найден.

Добавление элемента в произвольное место списка.

Найти заданный элемент, сохранить значение его поля адреса, создать новый элемент, записать адрес нового элемента в поле адреса заданного (найденного) элемента.

Записать в поле адреса добавляемого элемента сохраненный адрес следующего элемента.

Процедура добавления элемента в произвольное место списка показывает преимущество связного хранения перед последовательным (массивы).

Удаление элемента из конца списка.

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

Удаление произвольного элемента связного списка.

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

Кольцевой односвязный список.

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

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

Двунаправленный список.

Каждый элемент списка содержит адрес не только следующего элемента, но и предыдущего. Голова списка в адресе предыдущего элемента содержит NULL.

Кольцевой двунаправленный список.

Поле предыдущий элемент головы списка содержит адрес конца списка.

Двусвязный список.

Каждый элемент списка содержит 2 ссылки на 2 следующих элемента.

Двунаправленный (двусвязный) список.

Элемент такого списка помимо ссылки на левый и правый следующие элементы содержит ссылку на предыдущий элемент.

Многосвязный список.

Каждый элемент содержит n-ссылок на следующие элементы.

Задание.

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

struct node

struct node_t;

struct node

{

int data; struct node_t*v;

};

struct node_t

{

struct node_l;

struct node_t*n;

};

Head

Преимущество последовательного хранения.

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

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

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

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

Дисциплина обслуживания. Очередь.

Принцип: «first-in, first-out» (FIFO)

Стек:«last-in, first-out» (LIFO)

Дек (двунаправленная очередь).

Функции (f).

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

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

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

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

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

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

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