АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Линейные списки. Наиболее простой способ связать некоторое множество элементов - это организовать линейный список

Читайте также:
  1. A) линейные
  2. V2: ДЕ 11 - Векторные пространства. Линейные операции над векторами
  3. V2: ДЕ 4 – Линейные отображения. Линейные операции над матрицами
  4. V2: ДЕ 5 - Линейные отображения. Умножение матриц
  5. V2: ДЕ 6 - Линейные отображения. Определители второго порядка
  6. Абстрактные линейные системы
  7. Б) линейные.
  8. Б2 3.Билинейные и квадратичные формы. Приведение их к каноническому виду. акон инерции.
  9. Билет 13. Линейные операторы. Матрица линейного оператора.
  10. Билет18 Векторы линейные операции над ними, симметрические матрицы и их характеристические числа и собственные векторы.
  11. Билинейные и квадратичные формы.
  12. Виды связей в организации: вертикальные и горизонтальные, линейные и функциональные, прямые и косвенные, формальные и неформальные.

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

Рис. 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);

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

nil
nil
next
data
last
head
сurrent – текущий элемент списка

Рис.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.

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


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.01 сек.)