МIНIСТЕРСТВО ОСВIТИ І НАУКИ УКРАЇНИ Національний унiверситет "Львiвська полiтехнiка"
СТВОРЕННЯ I ВЕДЕННЯ ЛIНIЙНИХ СПИСКIВ Ознайомитися iз способом подання даних в оперативнiй пам’ятi ЕОМ у виглядi лiнiйних спискiв. Оволодiти алгоритмами роботи з послiдовними i зв’язаними лiнiйними списками. 2. КОРОТКІ ТЕОРЕТИЧНI ВIДОМОСТI Лiнiйний список - це множина, яка складається з n>=0 вузлiв X[1], X[2],(((, X[n], для якої якщо n>0, то X[1] є першим вузлом; якщо 1<k<n, то k-му вузлу X[k] передує X[k-1] i за ним йде X[k+1]; X[n] є останнiм вузлом. Операцiї, якi можна виконувати з лiнiйним списком: отримати доступ до k-го вузла списку, щоб проаналiзувати i/або змiнити його вмiст; ввести новий вузол безпосередньо перед k-м вузлом; 3) видалити k-вузол; 4) об'єднати кiлька лiнiйних спискiв в один; 5) зробити копiю лiнiйного списку; 6) видалити вузол iз списку; 7) знайти вузол iз заданим значенням у деякому полi. 2.1. Вставляння вузла на початок списку Операцiя вставляння вимагає кiлькох крокiв: Крок 1. Вводяться значення полiв нового вузла. Крок 2. Отримують вузол iз списку вiльного простору. Крок 3. Значення полiв, отриманих на першому кроцi, копiюються у вiдповiднi поля нового вузла. Крок 4. Втановлюється зв’язок нового вузла з його наступником (у даний момент першим вузлом списку) шляхом: а) присвоєнням полю Link нового вузла значення змiнної зв’язку, що вказує на перший вузол (First); б) присвоєнням змiннiй зв’язку, що вказує на перший елемент списку, адреси нового вузла. 2.2. Вставляння вузла у кiнець списку Крок 1. Створити новий вузол i записати у нього iнформацiю. Крок 2. Якщо зв’язаний список є порожнiм, тодi присвоїти адресу першого нового вузла змiннiй зв’язку First. Крок 3. Присвоюючи змiннiй зв’язку пошуку кiнця вмiст поля Link кожного вузла, дiйти до кiнця списку. Крок 4. Замiнити вмiст поля Link останнього вузла на вказiвник на новий вузол. 2.3. Вставляння у впорядкований зв’язаний список Певнi застосування вимагають, щоб лiнiйний список був впорядкований. Важко створити загальну процедуру, яка була б корисною для всiх застосувань. Припустимо, що поле Info вузла має структуру запису з кiлькома полями. Одним iз таких полiв буде поле Key, що визначатиме впорядкування зв’язаного списку. Алгоритм вставляння виглядатиме так: Крок 1. Створити новий вузол i зберегти iнформацiю. Крок 2. Якщо список порожнiй, тодi всановити вказiвник First на новий вузол. Крок 3. Якщо новий вузол передує першому, тодi вставити новий вузол у початок списку. Крок 4. Повторювати крок 5, доки ключ вузла зв’язаного списку буде меншим, нiж ключ поточного вузла. Крок 5. Отримати наступний вузол зв’язаного списку. Крок 6. Вставити новий вузол у список. 2.4. Формування копiї зв’язаного списку Крок 1. Якщо список порожнiй, тодi повернути nil. Крок 2. Видiлити пам’ять для нового вузла i скопiювати у нього вмiст першого вузла. Крок 3. Повторювати до кроку 5, поки не буде досягнуто кiнця старого списку. Крок 4. Отримати наступний вузол i у старому списку встановити значення змiнної зв’язку нового списку в останньому його вузлi. Крок 5. Копiювати вузол i додавати його в кiнець нового списку. Крок 6. Встановити поле змiнної зв’язку останнього вузла у новому списку в nil i повернутися. ІНДИВІДУАЛЬНЕ ЗАВДАННЯ Сформувати список з ланкою заголовком і перевірити чи входить в цей список числа 5 і 7. Якщо входять вивести TRUE якщо ні – FALSE. Текст програми Program Lab9; Type Pointer=^Lanka; Lanka=Record Elem:integer; Next:pointer; end; Var Vslov,Vlan:pointer;sym:integer;F:boolean; Begin New(Vslov); Read(sym); Vslov^.Elem:=sym; Vslov^.Next:=nil; Vlan:=Vslov; Repeat New(Vlan^.next); Read(sym); Vlan:=Vlan^.next; Vlan^.Elem:=sym; Vlan^.next:=nil; until eoln; Vlan:=Vslov; While (Vlan^.next<>nil) do Begin if (Vlan^.elem=5) or (Vlan^.elem=7) then F:=true; Vlan:=Vlan^.next; End; Writeln(F); Readln; End. Висновок Виконав[ім’я автора приховано]ними списками.