Динамические структуры данных Указатели Указатели Линейные списки Линейные списки Стеки Стеки Очереди Очереди Форман Э.В.

Переменная типа «указатель» переменная, способная хранить адреса переменных с типом, указанным при ее объявлении Синтаксис: :^ :^ Пример: pi:^integer;// pi – указатель на int pd:^real ;// pd – указатель на real pc :^char;// pc – указатель на char Указатель на Указатель на

Значение «указатель на » Значение переменной типа «указатель» адрес объекта типа Значение переменной типа «указатель» адрес объекта типа i = 9, j = 5, k = 2; i = 9, j = 5, k = 2; pi^ = i;// pi указывает на i pi^ = i;// pi указывает на i pi = &j;// pi указывает на j & операция взятия адреса & операция взятия адреса Нулевой указатель «никуда» не указывает Нулевой указатель «никуда» не указывает pi^ = nil; i 5 j 100 pi 2 k

Линейный список Односвязный список – это список, каждый элементтт которого, кроме своего значения elem имеет ссылку на следующий элементтт списка sled Односвязный список – это список, каждый элементтт которого, кроме своего значения elem имеет ссылку на следующий элементтт списка sled Elem Sled* Elem Sled* Elem Sled* Elem Sled* Elem nil Описание списка Type Sviaz=^zveno; Zveno=record {элементтт списка} Elem:integer; {информационная часть} Sled:sviaz; {ссылка на следующий элементтт} End; Var t:sviaz;

Работа со списком При работе со списками на практике чаще всего приходится выполнять следующие операции: При работе со списками на практике чаще всего приходится выполнять следующие операции: - описать список - описать список - создать список - создать список - найти элементтт с заданным свойством; - найти элементтт с заданным свойством; - вставить дополнительный элементтт до или после указанного узла; - вставить дополнительный элементтт до или после указанного узла; - удалить определенный элементтт из списка; - удалить определенный элементтт из списка; - упорядочить узлы линейного списка в определенном порядке и т.д. - упорядочить узлы линейного списка в определенном порядке и т.д.

Создание списка procedure List_Sozd(var tek: sviaz); procedure List_Sozd(var tek: sviaz); var var zag:sviaz; zag:sviaz; begin begin new(zag); new(zag); zag^.sled:=nil; zag^.sled:=nil; tek:=zag; tek:=zag; end; end; * Elem Sled *

Добавление элементтта с список в начало Elem Sled* Elem Sled* Elem Sled* Elem Sled* Elem nil Sled * procedure Dob(var tek:sviaz; e:integer); var dob:sviaz; begin new(dob); dob^.elem:=e; dob^.sled:=tek; tek:=dob; end; * *

Удаление элементтта из списка Elem Sled* Elem Sled* Elem Sled* Elem nil procedure DelAll(var tek:sviaz); var del :sviaz; begin while tek<>nil do begin del:=tek; tek:=tek^.sled; dispose(del); end; * *

Пример: Создание списка Program List_Proc; Program List_Proc; Type Type Sviaz=^zveno; Sviaz=^zveno; Zveno=record Zveno=record Elem:integer; Elem:integer; Sled:sviaz; Sled:sviaz; End; End; Var t:sviaz; ch:char; Var t:sviaz; ch:char; I:integer; I:integer; { Создание списка с заглавным звеном } { Создание списка с заглавным звеном } procedure List_Sozd(var tek: sviaz); procedure List_Sozd(var tek: sviaz); var var zag:sviaz; zag:sviaz; begin begin new(zag); new(zag); zag^.sled:=nil; zag^.sled:=nil; tek:=zag; tek:=zag; end; end;

{Добавление элементтта в начало списка без заглавного звена} {Добавление элементтта в начало списка без заглавного звена} procedure DobNach(var tek:sviaz; e:integer); procedure DobNach(var tek:sviaz; e:integer); var dob:sviaz; {Додає звено, що,} var dob:sviaz; {Додає звено, що,} begin begin new(dob); new(dob); dob^.elem:=e; dob^.elem:=e; dob^.sled:=tek; dob^.sled:=tek; tek:=dob; tek:=dob; end; end; {Добавление элементтта в конец списка} {Добавление элементтта в конец списка} procedure DobavKon(tek:sviaz; e:integer); procedure DobavKon(tek:sviaz; e:integer); var dobk:sviaz; var dobk:sviaz; p:sviaz; {Вспомогательный указатель, для поиска последнего элементтта в списке } p:sviaz; {Вспомогательный указатель, для поиска последнего элементтта в списке } begin begin new(dob); new(dob); dob^.elem:=e; dob^.elem:=e; dob^.sled:=nil: dob^.sled:=nil:

if tek=nil if tek=nil then tek:=dob then tek:=dob else else begin begin {поиск последнего в списке} {поиск последнего в списке} p:=tek; p:=tek; while p^.sled<>nil do p:=p^.sled; while p^.sled<>nil do p:=p^.sled; p^.sled:=Dob; {Добавление нового звена} p^.sled:=Dob; {Добавление нового звена} end; end; {Вывод на экран списка} {Вывод на экран списка} procedure Print(tek:sviaz); procedure Print(tek:sviaz); begin begin write('<'); write('<'); while tek<>nil do while tek<>nil do begin begin write(tek^.elem); write(tek^.elem); if tek^.sled<>nil then write (','); if tek^.sled<>nil then write (','); tek:=tek^.sled; tek:=tek^.sled; end; writeln('>'); end; end; writeln('>'); end;

procedure DelAll(var tek:sviaz); {удаление всех элементттов списка} procedure DelAll(var tek:sviaz); {удаление всех элементттов списка} var del :sviaz; {удаляемое звено} var del :sviaz; {удаляемое звено} begin begin while tek<>nil do while tek<>nil do begin begin del:=tek; del:=tek; tek:=tek^.sled; tek:=tek^.sled; dispose(del); dispose(del); end; end; end; end; Begin Begin List_Sozd(t); List_Sozd(t); Writeln ('Список инициализирован'); Writeln ('Список инициализирован'); Writeln(Введите элементт, который добавляется в начало и в конец'); Writeln(Введите элементт, который добавляется в начало и в конец'); Readln(i); Readln(i); DobNach(t,I); DobNach(t,I); Dob(t,I); Dob(t,I); Writeln('Список:'); Writeln('Список:'); Print(t); Print(t); Writeln('Видаляти элементи списку?'); Writeln('Видаляти элементи списку?'); Readln (ch); Readln (ch); If ch='Y' or ch='y' then DelAll(t); If ch='Y' or ch='y' then DelAll(t); Writeln('Робота зі списками завершена '); Writeln('Робота зі списками завершена '); Readln; Readln; End. End.

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

Побудувати двухсвязный список кожный элемент якого має два покажчики з відомостями про 20 спортивні команды: назва, кількість очки, місце, місто розташування команды. Перший покажчик указує на наступну команду в списку, другой на наступну команду на приклад зі Слов'янська. Т.е. список буде складатися із двох подсписков First 1 – звичайний лінійний список First 2 – список вказуючий на команды з міста Словянськ * *

Program Primer; Program Primer; Type Sport=^Kom; Type Sport=^Kom; Kom=record Kom=record Name:string[20]; Name:string[20]; K:integer; K:integer; Pos:integer; Pos:integer; Town:string[20]; Town:string[20]; Link1,link2:sport; Link1,link2:sport; End; End; Var first1,first2,pr,tek: Sport; Var first1,first2,pr,tek: Sport; I,k:integer; I,k:integer;

Begin {Створення першого подсписка} Begin {Створення першого подсписка} For I:=0 to 20 do For I:=0 to 20 do Begin Begin Writeln ('Уведіть назву команды') Writeln ('Уведіть назву команды') Readln(name); Readln(name); Writeln ('Уведіть кількість окулярів'); Writeln ('Уведіть кількість окулярів'); Readln(k); Readln(k); Writeln ('Уведіть займане місце'); Writeln ('Уведіть займане місце'); Readln(pos); Readln(pos); Writeln ('Уведіть із якого міста команда'); Writeln ('Уведіть із якого міста команда'); Readln (town); Readln (town);

If I=0 then If I=0 then Begin Begin New(first1); {Адреса початку першого подсписка зберігається в first1} New(first1); {Адреса початку першого подсписка зберігається в first1} First1^.name:=name; First1^.name:=name; First1^.k:=k; First1^.k:=k; First1^.pos:=pos; First1^.pos:=pos; First1^.town:=town; First1^.town:=town; Tek:=first1; Tek:=first1; End End Else Else Begin Begin new(pr); new(pr); {створення чернового элемента першого списку} {створення чернового элемента першого списку} pr^.name:=name; pr^.name:=name; pr^.k:=k; pr^.k:=k; pr^.pos:=pos; pr^.pos:=pos; pr^.town:=town; pr^.town:=town; tek^.link1:=pr; tek^.link1:=pr; tek^.link2:=nil; {другой подсписок попки порожній} tek^.link2:=nil; {другой подсписок попки порожній} tek:=pr; tek:=pr; end; end;

pr^.link1:=nil; pr^.link1:=nil; pr^.link2:=nil; pr^.link2:=nil; {уведення закінчене, починаємо уведення другого подсписка} {уведення закінчене, починаємо уведення другого подсписка} first2:=first1; first2:=first1; if first1<>nil then tek:=first1^.link1 else tek:=first1; if first1<>nil then tek:=first1^.link1 else tek:=first1; pr:=first2; pr:=first2; while tek<>nil do while tek<>nil do begin begin if tek^.town='Слов'янськ' then if tek^.town='Слов'янськ' then begin begin pr^.link2:=tek; pr^.link2:=tek; pr:=tek; pr:=tek; end; end; tek:=tek^.link1; tek:=tek^.link1; end; end; END. END.