WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Адреси та вказівники - Реферат

Адреси та вказівники - Реферат

заданим значенням немає або }
{ 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), при виконанні якої обробка початкового файла починається зі створення списку його елементів. Далі всі дії(додавання, пошук, вилучення тощо) відбуваються не з файлом, а зі списком, і лише наприкінці роботи зміст списку копіюється в файл. Така організація даних дозволяє зменшити обсяг роботи з зовнішніми носіями.
4. Списки як рекурсивні об'єкти
Нехай a позначає довільний елемент множини A. Списки її елементів можна означити рекурсивно, а саме:
порожній список є списком;
якщо позначає список, то < a > також є списком.
За цим означенням список складається з головного елемента й підсписку, який сам є списком. Відтворимо рекурсивну природу списків означенням типу зв'язаних списків елементів типу T :
type Plist = ^List;
List = record
v : T; subl : Plist
end
Список ідентифікується вказівником на його головний елемент. Але й кожний наступний елемент, ідентифікований полем subl попереднього, вважається головним елементом підсписку. Порожній список указується значенням nil. Виразимо рекурсивно обробку списку за допомогою обробки головного елемента й підсписку, вважаючи для визначеності, що T = integer.
Перевірку належності елемента списку задає рекурсивна функція
function isinr ( a : integer; lp : Plist ) : boolean;
begin
if lp = nil then isinr := false else
{ обробка голови }
if a = lp^.v then isinr := true else
{ рекурсивно перевірити належність елемента підсписку }
isinr := isinr ( a, lp^.subl )
end
Далі ми запишемо рекурсивну функцію addordr додавання елемента в упорядкований список зі збереженням його упорядкованості та повернення вказівника на список, у який вставлено елемент. Але спочатку напишемо функцію newelemr, подібну процедурі newelem з підр.16.3. На відміну від тієї процедури, вказівник на новий елемент повертається з неї.
function newelemr(p : Plist; z : integer) : Plist;
var pp : Plist;
begin
new(pp); pp^.subl:=p; pp^.v:=z;
newelemr:=pp
end;
Наведена функція використовується в функції addordr:
function addordr ( a : integer; lp : Plist ) : Plist;
var p : Plist;
begin
if (lp = nil) or (a glob-1-8) then
begin
write(k:8, parl(p[k div num])^[k mod num]:8);
cnt:=cnt+1;
end;
if cnt=4 then begin writeln; cnt:=0 end;
end;
writeln;
writeln('вільна пам''ять : ', memavail,
'; найбільша ділянка : ', maxavail);
readln;
end.
Loading...

 
 

Цікаве