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 вказує на ланку, яку вилучають.


 

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

16170. Практика назначения наказания. Учебное пособие 500 KB
  С.А. Разумов ПРАКТИКА НАЗНАЧЕНИЯ НАКАЗАНИЯ Учебнопрактическое пособие Москва Институт международного права и экономики имени А.С. Грибоедова 2001 Разумов С.А. Р17 Практика назначения наказания: Учебнопра...
16171. Основы экологического права. Учебное пособие 1.38 MB
  МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ КРАСНОЯРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Т.Г. Пучинина Основы экологического права Учебное пособие Красноярск 1999 Издательский центр Красноярского государственного университета 660041 г. Красноярск пр. Свобод...
16172. Коммерческое право. Учебное пособие 1.36 MB
  Коммерческое право Предисловие Уважаемый читатель Вы открыли одну из замечательных книг изданных в серии Классический университетский учебник посвященной 250летию Московского университета. Серия включает свыше 150 учебников и учебных пособий рекомендов
16173. Коммерческое право России. Учебное пособие 1.12 MB
  Б.И. Пугинский КОММЕРЧЕСКОЕ ПРАВО РОССИИ Москва 2000 УДК 34 ББК 67.404404.2я73 П88 Пугинский Б.И. Коммерческое право России. М.: Юрайт 2000. 314 с. ISBN 5852940925 Книга написанная Б.И. Пугинским видным российским правоведом доктором юридических наук пр...
16174. Коммерческое право России. Учебно-методическое пособие 619 KB
  Система российского права представляет собой целостное образование, включающее в той или иной степени связанные между собой отдельные отрасли права. С признанием в последний период разделения права на публичное и частное отрасли права дифференцируются прежде всего по их принадлежности к первому или второму. Будучи отнесенным к гражданскому праву, коммерческое право одновременно входит в сферу частного права
16175. Правовое регулирование хозяйственных товариществ и обществ. Учебное пособие 1.1 MB
  Согласно ГК РФ полному товариществу был придан статус юридического лица. Хозяйственные товарищества и общества наконец-то получили от участников имущество, передаваемое в уставный (складочный) капитал этих юридических лиц, а участники получили не право долевой собственности
16176. Правовая организация отраслевых хозяйственных систем. Учебное пособие 776.5 KB
  Пронская Г.В. Правовая организация отраслевых хозяйственных систем/ К.: Вища школа 1985 124с. Грациэлла Васильевна Пронская ПРАВОВАЯ ОРГАНИЗАЦИЯ ОТРАСЛЕВЫХ ХОЗЯЙСТВЕННЫХ СИСТЕМ На примере Украинской ССР Редактор О. А. Ульяницкая Художник В. И. Гридко...
16177. Криминальные организации. Учебное пособие 518 KB
  Криминальные организации Преступность вымогательство и политика американского города. От автора Эта книга совместный труд прошедший множество стадий прежде чем принять настоящую форму. Я обязан огромному числу людей за их помощь. Филипп Дженкинс из ...
16178. Муниципальное право России. Учебное пособие 628.5 KB
  СЕРИЯ ПОДГОТОВКА К ЭКЗАМЕНУ И. В. Постовой Муниципальное право России вопросы и ответы МОСКВА Юриспруденция 2000 УДК35 ББК 67.401 П63 П63 Постовой Н.В. Муниципальное право России: Вопросы и ответы. М.: Юриспруденция 2000. 128 с. С