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


 

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

19862. Проведение количественного анализа в Оже-спектроскопии методом внешних эталонов и методом коэффициентов элементной чувствительности 255.5 KB
  Лекция 27 Проведение количественного анализа в Ожеспектроскопии методом внешних эталонов и методом коэффициентов элементной чувствительности. Растровая Ожеэлектронная спектроскопия. Метод ОЭС позволяет проводить как качественный так и количественный элементный
19863. Физические основы метода вторичной ионной масс-спектрометрии (ВИМС). Аппаратура, необходимая для реализации метода ВИМС 115 KB
  Лекция 28 Физические основы метода вторичной ионной массспектрометрии ВИМС. Аппаратура необходимая для реализации метода ВИМС. Возможности метода ВИМС. Массспектрометрический анализ нейтральных распыленных частиц. Метод вторичной ионной массспектрометрии ВИМС ...
19864. Метод резерфордовского обратного рассеяния (РОР). Форма спектра обратнорассеянных ионов. Аппаратура, необходимая для реализации метода РОР 194 KB
  Лекция 29 Метод резерфордовского обратного рассеяния РОР. Форма спектра обратнорассеянных ионов. Аппаратура необходимая для реализации метода РОР. Первая работа посвященная анализу образца с помощью обратнорассеянных ионов появилась в 1968 г. В основе метода лежит м
19865. Определение стехиометрии образца методом РОР. Разрешение метода по глубине. Определение толщины пленки методом РОР 157 KB
  Лекция 30 Определение стехиометрии образца методом РОР. Разрешение метода по глубине. Определение толщины пленки методом РОР. С помощью метода Резерфордовского обратного рассеяния можно определить стехиометрический состав однородного образца не прибегая к использо
19866. Определение элементного состава образца методом PIXE (Proton Induced X-ray Emission) 85.5 KB
  Лекция 31 Определение элементного состава образца методом PIXE Proton Induced Xray Emission. Метод PIXE русский аналог РФА рентгеновский флуоресцентный анализ является малораспространенным как следует из его названия основан на возбуждении ускоренными протонами линий характе...
19867. Предмет біржового права 63.5 KB
  Тема 1. Предмет біржового права. Мета: Освітня: Ознайомити студентів з виникненням і розвитком бірж в Україні і світі. Вивчення правового статусу світових бірж гарантій майнових прав бірж. Виховна: моделювання поведінки студента як майбутнього спеціаліста на основі
19868. Правове положення товарної біржі 64 KB
  Тема 2. Правове положення товарної біржі . Мета: Освітня: Ознайомити студентів з установчими документами для реєстрації біржі. Вивчення правового статусу біржі гарантій майнових прав біржі. Виховна: моделювання поведінки студента як майбутнього спеціаліста на основ
19869. Угоди на товарній біржі 69.5 KB
  Тема 3. Угоди на товарній біржі. Мета: Освітня: Ознайомлення та складання угод. Ознайомлення з правилами біржових торгів порядком реєстрації біржових угод. Виховна: моделювання поведінки студента як майбутнього спеціаліста на основі отриманих знань та навичок. Розв...
19870. Правове положення фондової біржі 64.5 KB
  Тема 4. Правове положення фондової біржі. Мета: Освітня: Ознайомлення з установчими документами фондової біржі та її функціонуванням. Навчитися складати статут фондової біржі та визначити порядок реєстрації фондових бірж. Виховна: моделювання поведінки студента як...