Ссылочные типы. Динамические переменные — страница 9
заголовка, чтобы изменить значение указателя в предыдущем элементе списка. Чтобы устранить данный недостаток вводится второй указатель в каждом элементе списка. Первый указатель связывает данный элемент со следующим, а второй √ с предыдущим. Такая организация динамической структуры данных получила название линейного двунаправленного списка (двусвязного списка). На рис. 2 приведена графическая интерпретация двунаправленного списка. Интересным свойством такого списка является то, что для доступа к его элементам вовсе не обязательно хранить указатель на первый элемент. Достаточно иметь указатель на любой элемент списка. Первый элемент всегда можно найти по цепочке указателей на предыдущие элементы, а последний - по цепочке указателей на следующие. Но наличие указателя на заголовок списка в ряде случаев ускоряет работу со списком 2.3 Циклические списки Линейные списки характерны тем, что в них можно выделить первый и последний элементы, причем для однонаправленного линейного списка обязательно нужно иметь указатель на первый элемент. Циклические списки также как и линейные бывают однонаправленными и двунаправленными. Основное отличие циклического списка состоит в том, что в списке нет пустых указателей (см. рис 3). Последний элемент списка содержит указатель, связывающий его с первым элементом. Для полного обхода такого списка достаточно иметь указатель только на текущий элемент. В двунаправленном циклическом списке система указателей аналогична системе указателей двунаправленного линейного списка (см. рис 4). Двунаправленный циклический список позволяет достаточно просто осуществлять вставки и удаления элементов слева и справа от текущего элемента. В отличие от линейного списка, элементы являются равноправными и для выделения первого элемента необходимо иметь указатель на заголовок. Однако во многих случаях нет необходимости выделять первый элемент списка и достаточно иметь указатель на текущий элемент. Разберем решение типичной задачи, связанной с обработкой списков. Текст задания С использованием списков, заданный во входном файле текст (за которым следует точка) распечатать в обратном порядке. Решение program reverse; type List= ^Elem; Elem= record Info: Char; Next: List end; var L, p: List; c: char; begin {ввод литер текста и запись их в обратном порядке в список L (без заглавного звена)} L:= nil; {ссылка на построенную часть списка} read( c ); while c <> '.' do begin {добавить с в начало списка} new( p ); p^.Info:= c; p^.Next:= L; L:= p; read( c ) end; {печать литер из
Похожие работы
- Доклады
- Рефераты
- Рефераты
- Рефераты
- Контрольные