Ссылочные типы. Динамические переменные — страница 9

  • Просмотров 5667
  • Скачиваний 475
  • Размер файла 119
    Кб

заголовка, чтобы изменить значение указателя в предыдущем элементе списка. Чтобы устранить данный недостаток вводится второй указатель в каждом элементе списка. Первый указатель связывает данный элемент со следующим, а второй √ с предыдущим. Такая организация динамической структуры данных получила название линейного двунаправленного списка (двусвязного списка). На рис. 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;   {печать литер из