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

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

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

3 Значение «указатель на » Значение переменной типа «указатель» адрес объекта типа Значение переменной типа «указатель» адрес объекта типа 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

4 Линейный список Односвязный список – это список, каждый элементтт которого, кроме своего значения 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;

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

6 Создание списка 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 *

7 Добавление элементтта с список в начало 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; * *

8 Удаление элементтта из списка 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; * *

9 Пример: Создание списка 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;

10 {Добавление элементтта в начало списка без заглавного звена} {Добавление элементтта в начало списка без заглавного звена} 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:

11 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;

12 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.

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

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

15 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;

16 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);

17 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;

18 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.