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


 

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

50027. Темперамента у подростков 235 KB
  Период отрочества характеризуется динамичными изменениями всех физиологических систем и психических функций. Одновременно с этим, подростку приходится осваивать новые социальные роли и функции, перестраивать отношения с окружающим миром, изменять представления о себе как о личности.
50028. Наближене обчислення визначених інтегралів. Методичні вказівки 192 KB
  Загальна квадратурна формула має вигляд: 1. Формула прямокутників Якщо в формулі НьютонаКортеса взяти n=0 то одержимо квадратну формулу методу прямокутників.Кожна з цих сум є інтегральною сумою для на відрізку і тому наближено виражають визначений інтеграл: 1 2 Ці формули називаються формулами прямокутників.1 видно що якщо додатна і зростаюча функція то формула 1 виражає площу ступінчатої фігури що складена із “ внутрішніх†прямокутників а формула 2...
50029. ЧИСЕЛЬНІ МЕТОДИ В ІНФОРМАТИЦІ. МЕТОДИЧНІ ВКАЗІВКИ 74.5 KB
  Розвязування системи лінійних алгебраїчних рівнянь методом Гауса. Мета роботи: вивчити і засвоїти Методи Гауса і Жордана Гауса розвязування СЛАР. Метод Гауса полягає в зведенні квадратної системи 1 до трикутного вигляду з використанням алгоритму послідовного виключення невідомих. Алгоритм методу Гауса складається з двох етапів: Триангуляція матриці 2 Обчислення розвязку системи рівнянь...
50030. Екологічне право 1.16 MB
  Можливе існування різних видів власності на природні ресурси та користування ними, але безумовно визначення організаційно-правових форм приналежності природних обєктів конкретним соціальним субєктам є своєрідною формою взаємодії суспільства і природи.
50031. Инструментальные возможности программы Corel Draw 167 KB
  Это также наиболее известный из графических программных продуктов корпорации Corel которая наряду с dobe Corportion является ведущим производителем программных продуктов для компьютерной графики. Достоинствам продуктов Corel Corportion является разработка нескольких миллионов готовых изображений причем каждая линия в них поддается редактированию. В Corel Drw существуют не только мощные средства векторного редактирования но и средства верстки многостраничных документов а также подготовки их как в печатном так и в электронном виде.
50032. Измерение параметров индуктивности в цепи переменного тока 255 KB
  Цель работы: Определение импеданса сдвига фаз и измерение индуктивности на разных частотах в резистивно-индуктивной цепи. При работе на переменном токе с реактивными элементами в цепи индуктивность емкость следует обязательно учитывать их реактивный характер проводимости. Кроме того реактивные...
50033. Перевірка правил Кірхгофа 133.5 KB
  Мета роботи: перевірити правила Кірхгофа для кола постійного струму. Теоретичні пояснення правил Кірхгофа а також їх практичне використання для розрахунку розгалужених електричних кіл показані в розділі 3. Застосуємо перше правило Кірхгофа до вузла В...
50034. ИЗМЕРЕНИЕ РАЗРЕШАЮЩЕЙ СПОСОБНОСТИ ОБЪЕКТИВОВ 315 KB
  Как следствие фокусное расстояние объектива зависит от длины световой волны и если для одной длины волны изображение хорошо сфокусировано то для других длин волн хорошей фокусировки не наблюдается. Если как это обычно бывает оправа объектива круглая то изображение светящейся точки имеет вид круглого пятна окруженного концентрическими светлыми и темными кольцами рис. Способность объектива создавать раздельные изображения близко расположенных мелких деталей называется разрешающей способностью объектива. Чем меньше угол  тем ближе...
50035. Юридическая психология. Учебно-методический комплекс 677.5 KB
  Цель дисциплины – психологическая подготовка юриста к профессиональной деятельности, формирование эффективных приемов работы с людьми и овладение методами профессионально значимого самопознания и саморазвития личности.