|
|||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Линейные списки. Наиболее простой способ связать некоторое множество элементов - это организовать линейный списокНаиболее простой способ связать некоторое множество элементов - это организовать линейный список. При такой организации элементы некоторого типа образуют цепочку. Для связывания элементов в списке используют систему указателей. В рассматриваемом случае любой элемент линейного списка имеет один указатель, который указывает на следующий элемент в списке или является пустым указателем, что означает конец списка. Рис. 1.1. Линейный список (связанный список) В языке Turbo Pascal предусмотрены два типа указателей – типизированные и не типизированные указатели. В случае линейного списка описание данных может выглядеть следующим образом. type element = record data: string; next: pointer; end; var head: pointer; current, last: ^element; В данном примере элемент списка описан как запись, содержащая два поля. Поле data строкового типа служит для размещения данных в элементе списка. Другое поле next представляет собой не типизированный указатель, который служит для организации списковой структуры. В описании переменных описаны три указателя head, last и current. Head является не типизированным указателем. Указатель current является типизированным указателем, что позволяет через него организовать доступ к полям внутри элемента, имеющего тип element. Для объявления типизированного указателя обычно используется символ ^ (карат), размещаемый непосредственно перед соответствующим типом данных. Однако описание типизированного указателя еще не означает создание элемента списка. Рассмотрим, как можно осуществить создание элементов и их объединение в список. В системе программирования Turbo Pascal для размещения динамических переменных используется специальная область памяти (heap-область). Heap-область размещается в памяти компьютера следом за областью памяти, которую занимает программа и статические данные, и может рассматриваться как сплошной массив, состоящий из байтов. Попробуем создать первый элемент списка. Это можно осуществить при помощи процедуры New New(Current); После выполнения данной процедуры в динамической области памяти создается динамическая переменная, тип которой определяется типом указателя. Сам указатель можно рассматривать как адрес переменной в динамической памяти. Доступ к переменной может быть осуществлен через указатель. Заполним поля элемента списка. Current^.data:= 'данные в первом элементе списка '; Сurrent^.next:=nil; Значение указателя nil означает пустой указатель. Обратим внимание на разницу между присвоением значения указателю и данным, на которые он указывает. Для указателей допустимы только операции присваивания и сравнения. Указателю можно присваивать значение указателя того же типа или константу nil. Данным можно присвоить значения, соответствующие декларируемым типам данных. Для того чтобы присвоить значение данным, после указателя используется символ ^(карат). Поле Сurrent^.next само является указателем, доступ к его содержимому осуществляется через указатель Current. В результате выполнения описанных действий мы получили список из одного элемента. Создадим еще один элемент и свяжем его с первым элементом. Head:=Current; New(last); Last^.data:= 'данные во втором элементе списка '; Last^.next:=nil; Сurrent^.next:=nil; Непосредственно перед созданием первого элемента мы присвоили указателю Head значение указателя Current. Это связано с тем, что линейный список должен иметь заголовок. Другими словами, первый элемент списка должен быть отмечен указателем. В противном случае, если значение указателя Current в дальнейшем будет переопределено, то мы навсегда потеряем возможность доступа к данным, хранящимся в первом элементе списка. Динамическая структура данных предусматривает не только добавление элементов в список, но и их удаление по мере надобности. Самым простым способом удаления элемента из списка является переопределение указателей, связанных с данным элементом (указывающих на него). Однако сам элемент данных при этом продолжает занимать память, хотя доступ к нему будет навсегда утерян. Для корректной работы с динамическими структурами следует освобождать память при удалении элемента структуры. В языке TurboPascal для этого можно использовать функцию Dispose. Покажем, как следует корректно удалить первый элемент нашего списка. Head:=last; Dispose(current); Рассмотрим пример более сложной организации списка. Линейный список неудобен тем, что при попытке вставить некоторый элемент перед текущим элементом требуется обойти почти весь список, начиная с заголовка, чтобы изменить значение указателя в предыдущем элементе списка. Чтобы устранить данный недостаток введем второй указатель в каждом элементе списка. Первый указатель связывает данный элемент со следующим, а второй – с предыдущим. Такая организация динамической структуры данных получила название линейного двунаправленного списка (двусвязного списка).
Рис.1.2. Двунаправленный список Интересным свойством такого списка является то, что для доступа к его элементам вовсе не обязательно хранить указатель на первый элемент. Достаточно иметь указатель на любой элемент списка. Первый элемент всегда можно найти по цепочке указателей на предыдущие элементы, а последний - по цепочке указателей на следующие. Но наличие указателя на заголовок списка в ряде случаев ускоряет работу со списком. Приведем пример программы, которая выполняет следующие операции с двунаправленным линейным списком: · добавление (справа и слева от текущего); · удаление (справа и слева от текущего); · поиск; · вывод списка. program; type element = record data:string; last, next: pointer; end; var i,n: integer; head: pointer; current, pnt, pnt2: ^element; s:string; begin new(current); head:=current; current^.data:=head; current^.next:=nil; current^.last:=nil; repeat writeln('1 – сделать текущим'); writeln('2 – список элементов'); writeln('3 – добавить справа'); writeln('4 – добавить слева'); writeln('5 – удалить текущий'); writeln('6 – удалить справа от текущего'); writeln('7 – удалить слева от текущего'); writeln('0 – выход'); writeln('текущий элемент: ', current^.data); readln(n); if n=1 then {Выбор нового текущего элемента} begin writeln(''); readln(s); pnt:=head; repeat if pnt^.data=s then current:=pnt; pnt:=pnt^.next; until pnt=nil; end; if n=2 then {Вывод всех элементов} begin pnt:=head; i:=1 repeat writeln(i, ▒ √ ▒, pnt^.data); pnt:=pnt^.next; i:=i+1; until pnt=nil; end; if n=3 then {Добавление нового элемента справа от текущего} begin writeln(▒элемент▓); readln(s); new(pnt); pnt^.data:=s; pnt^.last:=current; pnt^.next:=current^.next; pnt2:=current^.next; if not(pnt2=nil) then pnt2^.last:=pnt; end; if n=4 then {Добавление нового элемента слева от текущего} begin writeln(▒элемент▓); readln(s); new(pnt); pnt^.data:=s; pnt^.last:=current^.last; pnt^.next:=current; pnt2:=current^.last; if not(pnt2=nil) then pnt2^.next:=pnt; end; if n=5 and not(current=head) then {Удаление текущего элемента} begin pnt:=current^.last; pnt^.next:=current^next; pnt2:=current^.next; if not(pnt2=nil) then pnt2^.last:=current^.last; dispose(current); end; if n=6 and not(current^.next=nil) then {Удаление элемента справа от текущего} begin pnt:=current^.next; current^.next:=pnt^next; pnt2:=pnt^.next; if not(pnt2=nil) then pnt2^.last:=current; dispose(pnt); end; if n=7 and not(current^.last=head) and not(current^.last=nil) then {Удаление элемента слева от текущего} begin pnt:=current^.last; current^.last:=pnt^.last; pnt2:=pnt^.last; if not(pnt2=nil) then pnt2^.next:=current; dispose(pnt); end; until n=0; end. В данной программе реализован алгоритм поиска элемента в списке (сделать текущим). В процессе поиска происходит обход с начала списка. Наличие указателя на заголовок списка ускоряет процесс поиска, так как не требуется сначала найти первый элемент, а затем - сделать обход списка. Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.01 сек.) |