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


 

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

65999. Глобализация финансов 37.71 KB
  Глобализация - это процесс всевозрастающего воздействия различных факторов международного значения (например, тесных экономических и политических связей, культурного и информационного обмена) на социальную действительность в отдельных странах.
66000. Региональные финансы омской области 46.5 KB
  Одной из важнейших составных частей финансовой системы государства являются региональные финансы которые охватывают региональные бюджеты административно-территориальных единиц и финансы субъектов хозяйствования используемые для удовлетворения потребностей регионов.
66001. Казначейство: функции, цели и механизм функционирования 20.59 KB
  В России переход к казначейскому исполнению бюджета начался в 1992 г. исполнение бюджета в нашей стране было банковским. Чем отличаются эти две формы исполнения бюджета При банковском исполнении бюджета средства...
66002. Золотовалютный резерв РФ 2009-2011 146.67 KB
  Золотовалютные резервы Российской Федерации представляют собой высоколиквидные финансовые активы находящиеся в распоряжении Банка России и Минфина России. Управление резервами Банк России осуществляет в соответствии с действующим...
66003. Организация экономического сотрудничества и развития (ОЭСР) 24.2 KB
  ОЭСР была образована в 1961 году по инициативе США на базе Организации европейского экономического сотрудничества которая координировала американскую и канадскую помощь пострадавшим от Второй мировой войны европейским странам в рамках плана Маршалла.
66005. Европейский банк реконструкции и развития, Европейский инвестиционный банк, Европейский центральный банк, Европейская экономическая комиссия Организации Объединенных Наций, Европейская ассоциация свободной торговли, Европейское экономическое пространство 189.5 KB
  О ЕБРР Европейский банк реконструкции и развития является международной финансовой организацией которая финансирует проекты в 29 странах от Центральной Европы до Центральной Азии. для стран Центральной и Юго-Восточной Европы а также Восточной Европы и Кавказа указав что дальнейшее ухудшение...
66006. Понятие, сущность, возможности СЭЗ 30.02 KB
  Такие зоны создаются для решения внешнеторговых общеэкономических социальных и научно-технических проблем. По оценкам западных специалистов к 2010 году через различные свободные экономические зоны будет проходить до 30 мирового товарооборота.
66007. Бюжетная политика 13.79 KB
  От качества федерального бюджета заложенных в него параметров зависят и уровень социальной защиты граждан и инвестиционные возможности государства и степень влияния России на международной арене и даже предпринимательская активность граждан.