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


 

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

32968. ИНТЕГРАТИВНЫЙ ХАР-Р СОЦ.-ГУМАНИТАРНОГО ЗНАНИЯ 16.07 KB
  ИНТЕГРАТИВНЫЙ ХАРР СОЦ.ГУМАНИТАРНОГО ЗНАНИЯ В сфере социальногуманитарного знания особое место принадлежит философии. экономисты считают экономическую теорию царицей соц. Философия хозва формирует реальное мысленное пространство которое обеспечивает эффективное научное познание нацеленное на комплексное социоэкономическое объяснение явлений и процессов системный подход учёт конкретной специфики той или иной страны.
32969. ИСТОКИ ПОСТНЕКЛАССИЧЕСКОГО ЭТАПА РАЗВИТИЯ НАУКИ (И.ПРИГОЖИН, И.СТИНГЕРС. ВЫЗОВ НАУКИ) 14.72 KB
  ИСТОКИ ПОСТНЕКЛАССИЧЕСКОГО ЭТАПА РАЗВИТИЯ НАУКИ И. ВЫЗОВ НАУКИ Зап. наука: высшая задача науки – сформулировать общие схемы которые бы совпадали с идеалом рационального. Но это привело не к замедлению прогресса науки а способствовало появлению новых концептуальных структур наука выполняет некую универсальную миссию затрагивающую взаимодействие человека и природы и человека с человеком в наши дни основной акцент научных исследований переместился с субстанции на отношение связь время Больцман: м у вероятностью и необходимостью...
32970. ИСТОРИЯ И ФИЛОСОФИЯ НАУКИ КАК МЕЖДИСЦИПЛИНАРНАЯ ДИСЦИПЛИНА 23.23 KB
  ИСТОРИЯ И ФИЛОСОФИЯ НАУКИ КАК МЕЖДИСЦИПЛИНАРНАЯ ДИСЦИПЛИНА Философия входит в жизнь человека очень рано задолго до того как сложится о ней самое 1st элементарное представление навеянное случайными встречами и знакомствами. Философия науки – раздел философии изучающий понятие границы и методологию науки. Периоды преднауки появление элементов научности: докть обоснование систематизация IVв. Дальше начинается триумфальный процесс развития науки производится большое колво открытий.
32971. МЕТОДОЛОГИЧЕСКОЕ ЗНАНИЕ И ЕГО УРОВНИ 14.53 KB
  Термин методология применяется не только к научнопознавательной деятти но и к любой др. деятти человека. Методология познание способа человеческой деятти научной художественной производственной. сферах деятти и их совершенствование.
32972. МЕТОДЫ НАУЧНОГО ПОЗНАНИЯ. ЭМПИРИЧЕСКИЕ И ТЕОРЕТИЧЕСКИЕ МЕТОДЫ НАУЧНОГО ПОЗНАНИЯ 22.52 KB
  МЕТОДЫ НАУЧНОГО ПОЗНАНИЯ. ЭМПИРИЧЕСКИЕ И ТЕОРЕТИЧЕСКИЕ МЕТОДЫ НАУЧНОГО ПОЗНАНИЯ Метод греч. Методы естественных наук подразделяют на: 1. методы изучения неживой природы и методы изучения живой природы.
32973. НАУКА В АНТИЧНОСТИ И СРЕДНИЕ ВЕКА 19.13 KB
  1st позитивистов не изучался генезис науки отдельно. Спенсер Происхождение науки: наука появилась одновременно с появлением человека. во Франции создается кафедра по изучению генезиса науки. Вопрос о периодизации науки до сих пор дискуссионный.
32974. НАУКА И ФИЛОСОФИЯ: ОБЩЕЕ, ОСОБЕННОЕ И ИДЕЯ ДОПОЛНИТЕЛЬНОСТИ (М. БОРН. ФИЗИКА И МЕТАФИЗИКА) 18.66 KB
  ФИЗИКА И МЕТАФИЗИКА Метафизика исследование общих черт структуры мира и наших методов проникновения в эту структуру. Вильям Джемс: Метафизика – это необычайно упорное стремление мыслить ясным образом. Бертран Рассел: Метафизика – попытка постичь мир как целое с помощью мысли. Метафизика – исследование общих черт структуры мира и наших методов проникновения в эту структуру.
32975. НАУКА КАК ЭПИСТЕМОЛОГИЧЕСКИЙ ФЕНОМЕН И СОЦ. ИНСТИТУТ 21.98 KB
  Всеобщие харристики понятия наука: определение науки как рациональнопредметного вида познания выделение в ней 3 ее основных аспектов: наука как специфический тип знания: исследуют логика и методология науки. эмоциональная нейтральность запрещает людям науки use при решении научных проблем эмоции личные симпатии. Все аспекты связаны м у собой и только в своем единстве позволяют достаточно полно и адекватно описать функционирование реальной науки как целого. Выявление структуры науки ставит проблему классификации наук раскрытие их...
32976. «НАУКИ О КУЛЬТУРЕ», ИХ СПЕЦИФИКА И ОТЛИЧИЕ ОТ «НАУК О ПРИРОДЕ» (Г.РИККЕРТ. НАУКИ О ПРИРОДЕ И НАУКИ О КУЛЬТУРЕ) 16.27 KB
  НАУКИ О КУЛЬТУРЕ ИХ СПЕЦИФИКА И ОТЛИЧИЕ ОТ НАУК О ПРИРОДЕ Г. НАУКИ О ПРИРОДЕ И НАУКИ О КУЛЬТУРЕ Науки о культуре: индивидуализирующий или исторический метод т. Одни из них суть науки о законах а др. науки о событиях и исторические.