2 Способа создания динамической переменной:

1) <тип>*<идентификатор> ,например int*x

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

<указатель>=new (<тип>) , например x=new(int)

2) Одним оператором можно описать указатель и обращение и обращение к функции new

<тип>*<идентификатор>=new(<тип>) ,например int*x=new(int);

Круглые скобки можно не писать.

Мы говорили что любому указателю можно присвоить NULL

x=NULL - x ни на что не ссылается.

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

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

Динамические переменные созданы для решения конкретной задачи, на какое-то время => надо уметь её удалить с помощью delete<имя указателя>;

Функция delete не возвращает значение. пример

int*x=new int;

*x=15

.....

delete x;

Работая с динамической переменной нужно следить за удалением.

Если вместо delete написать x=NULL, то место в динамической памяти на которое он указывал останется занятым, а доступа к этой области уже не будет.

42. Понятие линейного связного списка, типы списков, представление стека с помощью массива, пример использования стека.

Линейный связный список (ЛССп) – конечное множество компонент, каждая из которых состоит из двух частей: информационной (info) и указующей (link). Информационная часть может содержать произвольное количество любого типа данных. Указующая часть содержит адреса других компонент этого же списка. Наиболее часто используются односвязные и двусвязные списки (однонаправленные и двунаправленные). Если указующая часть содержит один адрес, указывает какая компонента следует за данной – односвязный.

Если указующая часть содержит два адреса – список двунаправленный

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

Наиболее часто используются стеки и очереди, реже деки.

Во многих ЭВМ стек реализуется аппаратно. Стек – это линейный список, имеющий одну точку доступа – вершину стека. Работает по принципу LIFO (Last In – First Out).

Описание стека с помощью массива:

Пусть стек состоит из 100 элементов.

const int stacksize=100;

int stack [stacksize], x, sp;

компонентами стека могут быть величины различного типа, в данном случае int. Что бы обратиться к вершине стека, нужна переменная, которая обращается к индексу этого массива. Чаще всего она указывает на первый свободный элемент стека. sp=0 инициализирует стек. Кроме инициализации есть 2 операции: положить в стек, взять из стека.

1. stack [sp]=x; // положить х на вершину стека

sp=sp+1; //указатель стека переместить на следующую компоненту

2. sp=sp-1;

x=stack [sp]

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

1) if (sp=stacksize) cout << "стек полон");

else {stack[sp]=x;sp=sp+1;}

2) if (sp<1) cout "стек пуст");

else (sp=sp-1;x=stack[sp];);