Линейные динамические структуры.

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

1.Непостоянство и непредсказуемость р-ра (числа элементов) структуры в процессе ее обработки. Число элементов динамической структуры может изменяться от 0 до некоторого значения, определяемого спецификой задачи или доступным размером машинной памяти.

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

Часто динамические структуры физически представляются в форме связных списков.

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

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

Логическая структура может быть изображена так:

Указатель

данные

Æ

данные

Указатель

данные

Æ -пустой указатель, означает конец списка.

Физическая структура списка может быть такой:

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

Логическая структура двусвязного списка:

В первой записи пустым является обратный указатель, а в последней – прямой.

В этом случае доступ к списку возможен как с начала списка, так и с его конца.

Включение списка и исключения элемента из списка осуществляется путем корректировки указателей.

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

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

Исключение из списка может быть так:

В этом случае поле указателя записи, после которого удаляется элемент изменяется на значение адреса, следующего за исключаемым элемента списка (L2®L3). Оконченная логическая структура обновленного списка:

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

К таким структурам приводит экономное представление разреженных матриц.

A1				A2		A3
		A4			A5
	A6		A7

Описание очередной строки матрицы º количество ненулевых элементов.

Указатели списка значений элементов º адрес списка значений элементов.

Получим следующую логическую структуру разреженной матрицы:

Дата добавления: 2015-12-08