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


 

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

75532. Відвідування театру. Враження від вистави. План-конспект уроку з англійської мови для учнів 9-х класів 55 KB
  Т: The topic of our lesson is Going to the thetre Describing performnce . By the end of the lesson you should be ble: to review nd ctivize the words nd wordcombintions to the topic Going to th thetre nd Describing performnce ; to predict fcts nd events from the newspper rticle by its hedline; to understnd the gist nd detils of the newspper rticle despite the nturl difficulties; to express your opinions bout performnce. I went to the thetre lst Sundy. Do you often go to the thetre Why Cn you sy wht the thetre is Where re the best sets in...
75533. Великий Кобзар, Тарас Шевченко, відомий у всьому світі 66.5 KB
  Т: Wht is this rticle bout Look t the newspper hedline of ex. Predict wht is this rticle bout 2 WhileReding ctivities. Wht kind of the text is it Wht kind of newspper is it tken from Wht is this rticle bout б Scnning. Where do monuments to gret poets of the world literture Ukrinin Trs Shevchenko Russin lexnder Pushkin Byelorussin Ynk Kupl nd mericn Wlt Whitmn stnd nerby on one lwn In wht town is rrow Prk situted Wht poem by Trs Shevchenko resounded in the prk on tht dy Who lid flowers t the monuments to the luminries of...
75534. Кіно в Україні 58 KB
  Т: The topic of our lesson is Cinem in Ukrine Describing film . By the end of the lesson you should be ble: to review the words nd wordcombintions to the topic Going to the cinem Describing film ; to understnd the gist nd detils of the text for reding; to express your opinion bout film you hve recently seen. Т: Red the quottion bout films find Ukrinin equivlent. Повторення ЛО теми Going to the cinem Describing film .
75535. Відвідування кінотеатру. Враження про переглянутий фільм 43.5 KB
  Мета: Перевірити рівень навчальних досягнень і рівень навченості учнів за вивченою темою Going to the cinem Your fvourite film . Т: Weve got test tody to check your skills in communictive writing bout going to the cinem nd your fvourite film. By the end of the lesson you should be ble: to mtch the English words nd word combintions with their Ukrinin equivlents Level 1; to define different kinds of films by their description Level 2; to nswer the questions to show your bility to prticipte in converstionl exchnge bout going to the...
75536. Вибір професії. Нові ЛО 83.5 KB
  Ввести й активізувати у мові учнів ЛО теми «Вибір професії». Практикувати учнів у читанні тексту з метою отримання загального уявлення (skimming) та з метою максимально повного й точного розуміння всієї інформації, що міститься в текст...
75537. Вибір професії. План-конспект уроку з англійської мови для учнів 9-х класів 53 KB
  Активізувати у мові учнів ЛО теми «Вибір професії». Підготувати до самостійного висловлювання про вибір професії та можливість отримана подальшої освіти після закінчення 9 класу.
75538. Вибір професії. Плани на майбутнє 71 KB
  Join together the two hlves of the fmous proverbs nd syings bout work nd peoples occuptions. Work in pirs. The hrdest work is to do nothing. Т: Wht colloctions of words connected with work cn you nme Lets drw Mind Mp.
75539. Вибір професії. Плани на майбутнє. Узгодження часів в англійській мові 60 KB
  We hve to review the words nd word combintions for this topic nd the grmmr: The Sequence of Tenses. By the end of the lesson you should be ble: to operte the words nd word combintions for the topic: Choosing profession People nd Occuptions ; to review the grmmr: The Sequence of Tenses ; to conduct your own dilogues using the given one s n exmple. If you her one of your profession put your hnd up nd cross the word out. the winner is the first student to cross out ll his her words nd shouts Bingo Profession Bingo Pupil\'s grid Professions:...
75540. Даниель Дефо, автор «Робінзона Крузо». Контроль позакласного читання 91.5 KB
  Обладнання: підручник текст для читання The uthor of Robinson Crusoe HO1 True or Flse H02 Personlity Quiz H03 Finish the Sentences H04. Т: The topic of our lesson is Dniel Defoe the uthor of Robinson Crusoe. Пред\'явлення тексту для читання Dniel Defoe the uthor of Robinson Crusoe . Т: Hve you ever red Robinson Crusoe Wht do you know bout the uthor of this book Is the book Robinson Crusoe still red by children nd grownups 2 WhileReding ctivities.