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


 

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

17933. Управління прибутком на підприємстві 226 KB
  5. Управління прибутком на підприємстві 5.1. Зміст та завдання управління прибутком підприємства 5.2. Формування прибутку від операційної діяльності 5.3. Управління операційними витратами 5.4. Управління операційним прибутком підприємства 5.5. Роль операційного аналіз
17934. Математичні основи фінансового менеджменту. Прості та складні відсотки 55 KB
  6. Математичні основи фінансового менеджменту. Прості та складні відсотки 6.1. Об'єктивна необхідність визначення вартості грошей у часі 6.2. Нарахування простих відсотків 6.3. Розрахунок майбутньої вартості грошового потоку методом компаундування Література 6. Матем...
17935. Ануїтети. Визначення вартості грошей у часі та її використання у фінансових розрахунках 60 KB
  7. Ануїтети. Визначення вартості грошей у часі та її використання у фінансових розрахунках 7.1. Розрахунок теперішньої вартості ануїтетів 7.2. Розрахунок теперішньої вартості грошового потоку методом дисконтування Література 7. Ануїтети. Визначення вартості грошей у
17936. Термінологія та базові показники фінансового менеджменту. Ефект фінансового важелю 90.5 KB
  8. Термінологія та базові показники фінансового менеджменту. Ефект фінансового важелю 8.1. Базові показникі фінансового менеджменту 8.2. Ефект фінансового важелю 8.3. Розгляд другої концепції ефекту фінансового важеля 8.4.. Взаємодія фінансового і операційного важелю
17937. Тактика фінансового менеджменту. Управління активами 162.5 KB
  10. Тактика фінансового менеджменту. Управління активами 10.1. Завдання управління необоротними активами підприємства 10.2. Особливості управління необоротними активами 10.3. Завдання управління оборотними активами підприємства 10.4. Визначення поточних фінансових потр
17938. СУЧАСНА УКРАЇНСЬКА ЛІТЕРАТУРНА МОВА. СТИЛІ МОВИ 728.5 KB
  1. СУЧАСНА УКРАЇНСЬКА ЛІТЕРАТУРНА МОВА. СТИЛІ МОВИ 1.1. Виникнення української мови 1.2. Сучасна ділова українська мова 1.3. Зміни в українському правописі 1.4. Стилі сучасної української мови 1.5. Загальні і граматичні особливості офіційноділового стилю мови 1.6. Запит
17939. ЛЕКСИЧНІ ЗАСОБИ ДІЛОВОГО МОВЛЕННЯ 119 KB
  2. ЛЕКСИЧНІ ЗАСОБИ ДІЛОВОГО МОВЛЕННЯ 2.1. Лексичне значення слова 2.2. Однозначні і багатозначні слова 2.3. Пряме і переносне значення слова 2.4. Омонімія синонімія антонімія паронімія 2.5. Стилістична диференціація слова 2.6. Фразео
17940. СЛОВОТВОРЧІ ЗАСОБИ ДІЛОВОГО МОВЛЕННЯ 54 KB
  3. СЛОВОТВОРЧІ ЗАСОБИ ДІЛОВОГО МОВЛЕННЯ 3.1. Морфемна структура слова 3.2. Способи словотвору 3.3. Запитання і завдання для самоперевірки 3.1. Морфемна структура слова Кожна одиниця мови має свою структуру. Структура слова є системою взаємопов'язаних і співвідносн
17941. МОРФОЛОГІЧНІ ЗАСОБИ ДІЛОВОГО МОВЛЕННЯ 440 KB
  4. МОРФОЛОГІЧНІ ЗАСОБИ ДІЛОВОГО МОВЛЕННЯ 4.1. Частини мови принципи їх виділення 4.2. Іменник 4.3. Прикметник 4.4. Числівник 4.5. Займенник 4.6. Дієслово 4.7. Прислівник 4.8. Службові частини мови 4.9. Вигук 4.10. Запитання і завдання для самоперевірки 4.1. Частини мови прин...