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


 

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

22466. Структура и система классификации и кодирования товаров в ТН ВЭД ТС 17.69 KB
  Основным классификационным признаком, на основе которого товары распределялись в Брюссельской товарной номенклатуре, был вид материала, из которого они изготовлены.
22467. Важнейшие классификаторы России 17.68 KB
  Объектом классификации и кодирования в этой системе является информация в областях статистики, финансовой и правоохранительной деятельности, банковского дела, бухгалтерского учета, стандартизации, сертификации, таможенного дела, торговли, внешнеэкономической деятельности.
22468. Разновидности методов кодирования. Штриховое кодирование товаров. Правила и примеры штрихового кодирования 37.69 KB
  Целью кодирования является систематизация объектов путем их идентификации максимально коротким способом, то есть с помощью минимального числа знаков.
22469. Сущность, цели и функции стандартизации. Значение стандартизации в международной торговле. Национальный орган по стандартизации в РФ 20.65 KB
  Стандартизация — деятельность по установлению правил и характеристик в целях их добровольного многократного использования, направленная на достижение упорядоченности в сферах производства и обращения продукции и повышение конкурентоспособности продукции, работ и услуг.
22470. Категории стандартов. Общая характеристика стандартов разных категорий. Их объекты, разработка, обозначение и утверждение. Изменения в ГСС в свете закона «О техническом регулировании 19.24 KB
  Система стандартизации Российской Федерации — это совокупность организационно-технических, правовых и экономических мер, осуществляемых под управлением федерального органа исполнительной власти по стандартизации и направленных на разработку и применение нормативных документов в области стандартизации с целью защиты потребителей и государства
22471. Глобальная экология 327.41 KB
  Беспрецедентный рост возможностей человека вооруженного достижениями НТР подняло на качественно новую ступень возможности его по преобразованию окружающей природной среды и расширило сферы его воздействия на нее, выходящие за рамки БИОСФЕРЫ.
22473. ИНТЕРФЕЙСЫ, ТЕРМИНАЛЬНОЕ ОБОРУДОВАНИЕ, СТРУКТУРА TDMA КАДРОВ И ФОРМИРОВАНИЕ СИГНАЛОВ В СТАНДАРТЕ GSM 381.44 KB
  Цель работы Изучить интерфейсы структуру служб терминальное оборудование структуру TDMA кадров и формирование сигналов в стандарте GSM. Ознакомиться с внутренними интерфейсами используемыми для соединения между различным оборудованием сетей GSM. Ознакомиться со структурой служб и передачей данных в стандарте GSM.
22474. ОБОРУДОВАНИЕ ПОДВИЖНЫХ И БАЗОВЫХ СТАНЦИЙ, ЦЕНТРА КОММУТАЦИИ 124.5 KB
  Цель работы Изучить блоксхемы подвижной станции абонентского радиотелефонного аппарата базовой станции и центра коммутации. Задание Изучить блоксхему подвижной станции ПС. Изучить блоксхему базовой станции БС. Краткая теория вопроса Рассмотрение элементов системы сотовой связи начнем с подвижной станции наиболее простого по функциональному назначению устройства и к тому же единственного элемента системы который не только реально доступен пользователю но и находится у него в руках в буквальном смысле этого слово.