46. Динамические переменные.

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

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

Область программного кода

Область статических данных

Область динамических данных (куча)

С       (вершина стека) т е к

Для создания и уничтожения динамических переменных в С++ используются операторы new и delete, соответственно. Значением оператора new является адрес созданной переменной, а в случае неудачи NULL. Созданная переменная не имеет имени и связь с нею можно осуществить только одним способом – присвоив ее адрес указателю соответствующего типа. При уничтожении динамической переменной ее адрес (т.е. значение соответствующего указателя) передается оператору delete.

Область видимости динамической переменной совпадает с областью видимости указателя на нее, а время жизни заключено между действием оператора new и оператора delete.

47.Списковые структуры данных

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

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

Элементы ССД могут быть двух типов: простые, логически неделимые (их называют подсписками) или сложные – совокупность простых и сложных меньшего объема.

В простые ССД (или строки, или цепи) входят только простые элементы. В сложные ССД входят и простые, и сложные элементы.

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

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

В однонаправленных списках реализуется взаимосвязь между элементами типа «следующий». Каждый элемент такого списка содержит указатель с адресом следующего элемента. Последний элемент имеет в указателе вместо адреса связи специальный знак – признак конца списка. Указатель списка содержит адрес его первого элемента.

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

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

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

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

-указатель списка, содержащий адрес первого и последнего элементов;

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

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

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

-указатель строки, который содержит адрес указателя начала кольца;

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

-звенья связи элементов, содержащие адрес последующего элемента и адрес значения элемента; звено связи последнего элемента вместо признака конца списка содержит адрес указателя начала кольца. При каждом просмотре кольца значение N уменьшается на единицу и проверяется условие N=0. Если N≠0, просмотр продолжается; при N=0 просмотр заканчивается.

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