68989

Списки як динамічна структура даних

Лекция

Информатика, кибернетика и программирование

Розглянуті рядки символів, зображені у вигляді ланцюгів, тобто як динамічна структура, є частковим випадком такої структури - лінійного однонапрямленого списку. Різниця полягає в тому, що коли для рядків інформаційними елементами можуть бути тільки значення типу char...

Украинкский

2014-09-28

47.5 KB

1 чел.

Лекція № 18

Тема: Списки як динамічна структура даних

План заняття:

  1.  Динамічна структура даних
  2.  Вставлення елемента в список
  3.  Вилучення елемента зі списку
  4.  Шукання елемента списку

Динамічна структура даних

Розглянуті рядки символів, зображені у вигляді ланцюгів, тобто як динамічна структура, є частковим випадком такої структури - лінійного однонапрямленого списку. Різниця полягає в тому, що коли для рядків інформаційними елементами можуть бути тільки значення типу char, то в загальному випадку списків елементами можуть бути значення довільного типу - як прості, так і складені. Однак з метою уніфікації під час опрацювання списку вважатимемо, що всі елементи є значеннями одного типу.

Схематично однонаправлений список показаний на рис. 1.

 ……

Рис. 1. Однонаправлений список.

За аналогією з динамічними рядками тут визначено вказівник Sp, який вказує на весь список як на єдину структуру, а також нульову ланку, у якій вказівник вказує на перший елемент.

Недоліком однонапрямлених списків є те, що рухатись по такому списку можна тільки в одному напрямі - від початку до кінця. Немає змоги природним способом, без значного ускладнення алгоритму, перебирати елементи у зворотному напрямі.

Тому введемо нову динамічну структуру - двонаправлений список. Для цього в кожній ланці списку додамо ще по одному полю. Значенням цього поля буде вказівник на попередню ланку списку. Оскільки кожна ланка зображена як запис, то в цей запис відповідно додамо ще одне поле. Тоді структуру ланки опишемо таким списком типу:

type

TypeElm=Char;

Link=^Lanka;

Lanka=record

Elem: Char;

Next: Link;

Predd: Link;

end;

Така структура схематично зображена на рис. 2.

Sp

   ……….

Рис. 2.Двонаправлений список.

Як видно з рис. 2, у полі Predd нульової ланки, як і в полі Next останньої ланки, вказівник має значення nil, що відповідає ситуації, коли нульова ланка не має попередньої, а остання - наступної.

Варіантом двонапрямлених є кільцеві списки, їх утворюють на базі двонапрямлених, якщо вказівній змінній у полі Next останньої ланки присвоїти значення вказівника, що вказує на початок, тобто на нульову ланку, а в полі Predd нульової ланки - значення вказівника, що вказує на останню ланку. Тобто одержимо кільцеву структуру (рис. 3).

Над списками визначені ті ж самі операції, що й над динамічними рядками, тобто пошук елемента в списку, Вставка елемента у визначене місце і вилучення зі списку.

Sp

 ……..

Рис. 3. Кільцевий список.

Вставка елемента в список

Вставка елемента в список виконують за алгоритмом, що подібний до вставки символу в рядок. Процедура вставки має два формальні параметри: перший - елемент, який вставляють, і другий - вказівку на ланку, після якої вставляють елемент:

program Form5;

type

TypeElm=Char;

Link=^Lanka;

Lanka=record

Elem: Char;

Next: Link;

Predd: Link;

end;

procedure lnList(Elm: TypeElm; LanLst: Link);

var Rb: Link;

begin

New(Rb);

Rb^.EIem:=Elm;

Rb^.Next:=LanLst^.Next;

Rb^.Predd:=LanLst^.Next^.Predd;

LanLst^.Next:=Rb;

LanLst^.Next^.Predd:= Rb;

end;

begin

end.

Тут Elm- елемент, який вставляють, LanLst- вказівник на ланку, після якої виконують вставку.

Вилучення елемента зі списку

 Для цього треба змінити вказівку в полі Next попередньої ланки і в полі Predd наступної після тої, яку вилучають. Доцільно ланку, елемент якої вилучають, знищити:

program Form6;

type

TypeElm=Char;

Link=^Lanka;

Lanka=record Elem: Char; Next: Link; Predd: Link;

end;

procedure OutList(LanLst:Link);

begin

LanLst^.Next^.Predd:=LanLst^.Predd;

LanLst^.Predd^.Next:=LanLst^.Next;

Dispose(LanLst);

end;

begin

end.

Тут значення LanLst вказує на ланку, яку вилучають.


 

А также другие работы, которые могут Вас заинтересовать

70950. О ПРИЧИНАХ ИЗМЕНЕНИЯ МЕТОДОВ ГОСУДАРСТВЕННОГО УПРАВЛЕНИЯ 115 KB
  Каждое государство как особая форма политического образования характеризуется наличием индивидуального в некотором роде уникального механизма осуществления функций которые присущи ему вследствие наличия особенностей данной политической системы.
70951. ФОРМА БРАЧНОГО ДОГОВОРА И ПОРЯДОК ЕГО ЗАКЛЮЧЕНИЯ 63.5 KB
  Прежде чем касаться непосредственно порядка и формы заключения брачного договора на наш взгляд следует подчеркнуть что заключение брачного договора не является условием необходимым для вступления в брак поскольку перечень этих условий содержится...
70956. ПРАВОВЫЕ ОСНОВЫ ОРГАНИЗАЦИИ И ДЕЯТЕЛЬНОСТИ ЗАКОНОДАТЕЛЬНЫХ (ПРЕДСТАВИТЕЛЬНЫХ) ОРГАНОВ ГОСУДАРСТВЕННОЙ ВЛАСТИ СУБЪЕКТОВ РОССИЙСКОЙ ФЕДЕРАЦИИ 94.5 KB
  Правовые основы формирования компетенции и организации деятельности законодательных органов субъектов РФ являются актуальной но недостаточно исследованной темой. Роль и функции законодательных органов субъектов РФ определены в Конституции...