Сторінка
2
function isin ( s: str; h: TPle ) : boolean; begin if h = nil then isin := false else begin while ( h^.next <> nil ) and ( h^.v <> s ) do h := h^.next;
{ ( h^.next = nil ) or ( h^.v = s ) } isin := ( h^.v = s ) end end Оскільки список починається елементом pss^, то виклик функції має вигляд isin(s, pss). Зміна вказівника h при виконанні процедури не міняє значення pss і не веде до втрати зв'язку з головою списку, оскільки h є параметром-значенням. Рядки, представлені в списку, друкуються з його початку просуванням по елементах до кінця: procedure writelst ( h : TPle ); begin while h <> nil do begin writeln ( h^.v ); h := h^.next end end Зберемо означення типів str, TPle, Tle та наведені підпрограми в модуль strlist, і запишемо розв'язання задачі (1) у вигляді програми namlist1: program namlist1(input, output); uses strlist;
var pss : TPle; s : str; begin pss := nil; readln ( s ); while s <> '' do begin if not isin ( s, pss ) then add ( s, pss ); readln ( s ) end; writelst ( pss ) end. 3.3. Додавання до упорядкованого списку Розглянемо тепер задачу про друкування прізвищ із умовою (2), тобто в лексикографічному порядку. Нехай знак < позначає упорядкування елементів деякого типу T, зокрема, лексикографічне упорядкування рядків. Послідовність a1, a2, … , an елементів типу T називається упорядкованою, якщо n=1, або n>1 і ai<ai+1 за i=1, 2, … , n-1. Зв'язаний список називається упорядкованим, якщо подає упорядковану послідовність a1, a2, … , an, тобто його перший елемент зберігає a1, другий – a2 тощо. Розглянемо таке додавання нового рядка s до упорядкованого списку ss, що його результатом є упорядкований список. Вставка в порожній список дає упорядкований список із елемента ss1. Якщо s<ss1, то вставити новий елемент перед першим елементом списку, утворивши послідовність <s, ss1>. Якщо s>ss1, то відшукати такий елемент списку ssk, що (ssk<s і s<ssk+1) або (ssk<s і ssk є останнім). В обох цих випадках s вставляється після елемента ssk. Нехай результат лексикографічного порівняння рядків s1 і s2 обчислюється при виконанні виклику функції lt(s1, s2) – див. задачу 12.9. Скористаємося процедурою створення нового елемента списку Newelem. Аргументами в її виклику є вказівник типу Tple та вираз типу str. За виконання її виклику створюється новий елемент списку, в його поля записуються значення аргументів, після чого аргумент-вказівник установлюється на цей елемент: procedure newelem(var p : Tple; z : str); var pp : Tple; begin new(pp); pp^.next:=p; pp^.v:=z; p:=pp end; З використанням цієї процедури наведений алгоритм уточнюється такою процедурою: procedure addord ( s : str; var h : TPle ); var p, pp : TPle; stop : boolean; begin if h = nil then {Список порожній – створюється новий елемент } newelem ( h, s ); {і стає головним}
else if lt ( s, h^.v ) then { Вставка перед першим елементом – } newelem ( h, s ) {новий елемент стає головним} else begin { Пошуки місця для вставки } stop := false; p := h;
while ( p^.next <> nil ) and not stop do if lt(s, p^.next^.v) then stop := true else p := p^.next; { Вставка після елемента p^ за умови, } { що s не дорівнює p^.v } if p^.v <> s then newelem ( p^.next, s ); end end Нехай ця процедура разом із допоміжними до неї міститься в модулі strlist. Як бачимо, вона задає вставку елемента після перевірки його відсутності в списку. Тоді в наступній програмі розв'язання задачі з умовою (2) функція isin не потрібна: program namlist2(input, output); uses strlist; var pss : Tple; s : str; begin pss := nil; readln ( s ); while s <> '' do begin addord ( s, pss ); readln ( s ) end; writelst ( pss ) end. Упорядкований список можна створити іншим шляхом. Можна при читанні додавати елементи просто з голови списку, і лише після цього починати його переупорядкування. У розділі 17 ми розглянемо упорядкування послідовності за допомогою так званого злиття її упорядкованих частин в більші за довжиною упорядковані. Якщо доводиться читати багато значень і створювати довгий список, то такий спосіб вимагає в підсумку суттєво менше роботи, ніж наведене додавання зі збереженням упорядкованості. 3.4. Вилучення елемента зі списку На прикладі списків рядків типу str розглянемо операцію вилучення елемента, який зберігає задане значення. Реалізуємо її згідно з алгоритмом: 1)Порожній список залишається без змін. 2)Якщо значення зберігається в голові списку, то достатньо перемістити вказівник із неї на наступний елемент і звільнити пам'ять, зайняту нею. Але внаслідок переміщення голова стає недоступною, тому спочатку треба встановити на неї допоміжний вказівник. 3)Якщо значення не зберігається в першому елементі, то треба переміститися по зв'язках списку до елемента A, наступний за яким B зберігає задане значення. Потім треба наступний за B елемент "прив'язати" до A та звільнити пам'ять, зайняту B. Якщо елемента із заданим значенням немає, то список не змінюється. Аналогічно п.2 перед розривом зв'язку з елементом B треба встановити на нього допоміжний вказівник. Наведений алгоритм уточнюється процедурою del: procedure del ( s : str; var h : TPle ); var p, pp : TPle; stop : boolean; begin if h <> nil then if h^.v = s then begin
pp := h; h := h^.next; dispose ( pp ); pp := nil end else begin p := h; stop := false; while ( p^.next <> nil ) and not stop do if p^.next^.v = s then stop := true else p := p^.next;
{ p^.next = nil – елемента із заданим значенням немає або }
{ stop = true – треба вилучити елемент p^.next^ } if stop then begin pp := p^.next; p^.next := pp^.next; dispose ( pp ); pp := nil end end end; Задачі 1.* Імітувати виконання пpогpами program LIFO ( input, output ); type PLe = ^Le; Le = record val : integer; next : PLe; end; var hd, p : PLe; i : integer; procedure insel ( var h : PLe; v : integer ); var p : PLe; begin new ( p ); p^.next := h; p^.val := v; h := p end; begin hd := nil; for i := 1 to 3 do insel ( hd, i ); while hd <> nil do begin writeln ( hd^.val ); p := hd; hd := hd^.next; dispose ( p ); end; end. 2.*Написати програму визначення обсягу вільної пам'яті, що надається програмі, з точністю до 1000 байтів. 3. Написати підпрограму pозташування елементів списку у зворотному поpядку: а) без побудови нового списку; б) у новому списку. 4. Написати функцію пеpевіpки, чи пpедставлено ціле число в упорядкованому за зростанням списку. 5. Написати підпрограми додавання та вилучення рядка зі списку за умови: а) разом із рядком елемент списку зберігає кількість М його повтоpень: пpи пеpшому додаванні рядка полю М присвоюється 1, потім М збільшується на 1 пpи додаванні й зменшується на 1 пpи вилученні, а пpи вилученні рядка з М=1 знищується елемент списку, який пpедставляє цей рядок; б) додавання й вилучення виконуються, як у пункті (а), але зберігається упорядкованість елементів списку за спаданням кількості повторень; упорядкованість елементів із однаковими кількостями повторень не має значення. 6. Гpа-"лічилка" задається натуpальними N і M. Числа 1, … , N pозташовуються по колу, і з числа 1 починається відлік від 1 по колу; M-е число вилучається. Відлік поновлюється з елемента, наступного за вилученим тощо до вилучення всіх чисел із кола. Написати підпpогpаму друкування за N і M послідовності чисел, що вилучаються, напpиклад, за N = 4 і M = 3 це буде 3, 2, 4, 1. 7. Зв'язаний список, у якому елементи додаються та вилучаються з голови, реалізує магазин (стек). Написати модуль pоботи зі стеком, що подається зв'язаним списком. У модулі мають бути пiдпpогpами 1) ініціалізації порожнього стека; 2) скидання стека (вилучення всіх його елементів); 3) обчислення кількості елементів стека; 4) перевірки поpожньості стека; 5) додавання елемента з початку стека; 6) добування й вилучення елемента з початку стека. 8. Чергою є список, у якому елементи вилучаються на початку, а додаються в кінці. Зв'язаний список, у якому перший елемент є наступним за останнім, називається циклічним. Найчастіше такий список ідентифікується вказівником на останній елемент. Написати модуль роботи з чергою, поданою циклічним зв'язаним списком. У модулі мають бути пiдпpогpами 1) ініціалізації порожньої черги; 2) скидання черги (вилучення всіх її елементів); 3) обчислення кількості елементів черги; 4) перевірки поpожньості черги; 5) додавання елемента в кiнці черги; 6) добування й вилучення елемента на початку черги. 9. Над множинами означено такі опеpації: - перевірка належності елемента множині; - перевірка порожньості множини; - додавання й вилучення елемента; - читання й друкування елементів множини. Написати модуль, що реалізує поняття "множини цілих". Для подання множини застосувати а) зв'язаний список; б) упорядкований за зростанням зв'язаний список. 10. Написати програму читання двох множин і друкування результату застосування до них теоретико-множинної операції а) об'єднання; б) пеpетину; в) pізниці; г) симетричної різниці. Програма має успадковувати модуль із попереднього завдання. 11. Відповідність задається двома множинами A, B та підмножиною R їхнього декартового добутку A´ B (множиною пар). Над множинами пар означено такі опеpації: - перевірка належності елемента множині пар; - перевірка порожньості множини пар; - додавання та вилучення елемента (пари); - читання та друкування елементів множини пар. Написати модуль, що реалізує поняття "відповідності множин цілих". Для подання множини пар застосувати а) зв'язаний список пар; б) "список списків": кожний елемент a множини A зберігається у зв'язаному списку разом із вказівником на голову списку таких елементів b множини B, що пара (a, b) належить R. 12. Написати програму читання двох відповідностей і друкування результату застосування до них операції а) об'єднання; б) перетину; в) композиції. Програма має успадковувати модуль із попереднього завдання. 13. Відношенням на множині A називається підмножина декартового добутку A´ A. Написати програму читання відношення на множині цілих і перевірки, чи є воно а) рефлексивним; б) симетричним; в) антисиметричним; г) транзитивним; д) еквівалентністю; е) лінійним порядком; є) решіткою. Програма має успадковувати модуль із завдання 16.11. 14. Результат лижника у перегонах задається трійкою цілих: його стартовим номером та кількістю хвилин і секунд. Написати програму читання результатів лижників і друкування їх у порядку неспадання часу. 15. Написати програму обробки файлів (задача 13.12), при виконанні якої обробка початкового файла починається зі створення списку його елементів. Далі всі дії (додавання, пошук, вилучення тощо) відбуваються не з файлом, а зі списком, і лише наприкінці роботи зміст списку копіюється в файл. Така організація даних дозволяє зменшити обсяг роботи з зовнішніми носіями.
Завантажити реферат