DataLife Engine > Версия для печати > Динамічні структури даних. Рішення задач. Стек. Чергу. Грудень

Курсова робота

"Динамічні структури даних. Рішення задач. Стек. Чергу. Дек "

Введення

Для вирішення багатьох практичних завдань використовуються структури даних - масив, запис, безліч і так далі. Мета опису типів даних і подальшого опису змінних, як відносяться до цього типом, полягає в тому, щоб зафіксувати на час виконання програми розмір значень, що присвоюються цим змінним і, відповідно, фіксувати розмір виділюваної області пам'яті для них. Такі змінні називаються статичними.

Внаслідок фіксування розміру виділеної пам'яті виникають певні труднощі: неефективне використання оперативної пам'яті. Нам, у багатьох випадках, заздалегідь не відомі значення тієї чи іншої змінної, і навіть факт існування цього значення. Для вирішення завдань ми можемо використовувати тільки статичні змінні, але ми не знаємо значення результату і його розміри, тому нам би довелося виділяти місце в пам'яті для максимально можливого підсумкового значення, що призводить до нераціонального використання пам'яті машини.

Створені і не описані заздалегідь, змінні розміщуються на вільні ділянки в динамічної області оперативної пам'яті. Такий спосіб розподілу пам'яті називається динамічним. Існують безліч типів динамічних структур даних, серед них, такі як стек, чергу, лінійні списки, деки, дерева і інші.

В деяких випадках рішення задачі ефективніше при використанні стеків, в інших дерев, по-третє, - наступних. У цій роботі неповний огляд стеків, черг і деков.

1. Стек

Типова ситуація, коли одна проблема вимагає вирішення іншої, яка нерозв'язна без рішення третьої і так далі. У цьому ряду проблема, не викликала нових проблем, вирішується нами першою, хоча оформилася останньої, а вихідна проблема вирішується в останню чергу. Така дисципліна обслуговування позначається LIFO і часто використовується в програмах. Їй відповідає абстрактна лінійна структура, звана стек.

Визначення для стека на мові лінійного списку:

стек - окремий випадок лінійного односвязного списку, для якого дозволено додавати або видаляти елементи тільки з одного кінця списку, який називається вершиною стека.

Приміщення нового елемента в стек, читання для обробки і його видалення відбувається в одному його кінці - верхівці. Інший кінець стека неактивний. Якщо ми видалимо елемент, в верхівці виявляється наступний, можна порівняти з дією магазину в стрілецьку зброю. Включення нового елемента як би проштовхує наявні елементи в сторону дна. Порядок їх проходження при зберіганні не порушується, як і в чергах, масивах та інших структурах. Оскільки в кожний момент потрібен доступ до одного, верхньому, елементу стека, індекси елементів не потрібні.

Нехай Т - деякий тип. Розглянемо тип В«стек елементів типу ТВ». Його значеннями є послідовності значень типу Т. Основні операції, які використовуються при застосуванні стека

В· Зробити порожнім;

В· Додати елемент; В· Взяти елемент; В· Стек порожній; В· Вершина стека: Т;

Процедура В«Зробити порожнімВ» робить стек порожнім, тобто В«на дні стека нічого немаєВ», малюнок № 2. Процедура В«додати елементВ» додає елемент Х, типу Т, в кінець послідовності.

Процедура В«Взяти елементВ» застосовна, якщо послідовність S непорожній, вона забирає з неї останній елемент, який стає значенням змінної т.). Вираз В«стек порожнійВ» істинно, якщо послідовність S порожня. Вираз В«вершина стека В»визначено, якщо послідовність s непорожній, і одно останньому елементу послідовності s (.

Реалізація стека на основі масиву

Будемо вважати, що вершина нашого стека - це перший елемент масиву, тоді вершина буде знаходитись завжди у першій клітинці масиву, а дно буде просуватися по масиву. Для зручності домовимося порожнім членам масиву - вільному стеку привласнювати - 1000.

Помітно, що стек обмежений по розмірах: у нього можна записати обмежена кількість елементів

Розділ оголошення змінних і констант на мові програмування Паскаль виглядає наступним чином:

Const n = 10;

турі typeelem = Integer; { оголошення типу змінного }

Stack = Array Of typeelem;

Var s: stack;

Х: typeelem ;

I : Integer ;

Стек можна моделювати за допомогою двох змінних:

1. S - Стек.

2. Х - змінна для вмісту вершини.

Для того щоб не було непорозумінь і помилок потрібно роздруковувати вміст стека. Ця процедура виводить на екран вміст стека у вигляді стовпчика, на верху якої буде виводитися вершина. У самому нижньому положенні буде знаходитися перший занесений елемент.

Procedure list ; { процедура роздруківки змісту стека }

Var i: Integer;

Begin

Writeln;

I : = 1; { покажчик вершини ставиться на вершину стека }

While And Do Begin

Writeln;

Inc

End ;

End; {list}

Для додавання елемента в стек треба, щоб цей елемент був типу елемента стека. Процедуру додавання можна описати таким чином:

Procedure push ;

Var i : Integer ; {процедура вставки}

Begin

For i: = n Downto 2 Do s: = s;

S : = x

End ; { push }

Процедура додавання: спочатку ми повинні звільнити місце під новий елемент, для цього зрушуємо всі елементи стека по масиву вправо і тільки після додаємо новий в вільну комірку.

Функція В«взяти елемент В»в змінну криється у тому, щоб вважати елемент в змінну і видалити його з стека. Функції ми присвоюємо значення вершини стека, після чого зрушуємо весь стек на одну комірку вліво. У циклі присвоюємо I - тому I +1 значення. Останньому члену масиву - В«дноВ» стека присвоюємо -1000.

Function pop : typeelem ; { зчитування з видаленням}

Var i: Integer;

Begin

Pop: = S;

For i: = 1 To n-1 Do s: = s;

S : = -1000

End ; { pop }

Функція вершина стека: значенню функції присвоюємо значення вершини стека.

Function stacktop : typeelem ; { зчитування без видалення }

Begin

Stacktop: = S

End; {stacktop}

Функція стек порожній: якщо значення вершини стека не дорівнює -1000, то функції присвоюємо значення логічної змінної FALSE .

Function empty: Boolean; { перевірка на порожнечу }

Begin

If s <> -1000 empty: = false;

End; {empty}

В основній програмі використовуються вище зазначені процедури, наприклад:

init; { процедура ініціалізації }

list; { роздруківка вмісту стека }

For i: = 1 To 3 Do

push; { вставка в стек }

Writeln;

list; { роздруківка вмісту стека }

Writeln);

х: = stacktop; { зчитування без видалення }

Writeln;

List;

For i: = 1 To 2 Do Begin

х: = pop; { зчитування з видаленням }

Writeln

End;

Writeln;

List;

х : = pop;

Writeln;

list;

Writeln);

Недолік реалізації стека на основі масиву - це його обмеженість в довжині, для подолання цього недоліку використовують стек на основі лінійного списку.

2. Черга

Черга - окремий випадок лінійного односвязного списку, для якого дозволені тільки дві дії: додавання елемента в кінець черги і видалення елемента з початку черзі. Для створення і роботи з нею необхідно мати як мінімум два покажчика:

В· На початок черги.

В· На кінець черги.

Черга можна представити у вигляді ланок, кожна з яких складається з двох полів: перше - поле елемента, друге - поле посилання на наступний елемент черги.

Для черг застосовні наступні операції:

В· Зробити порожній.

В· Додати в чергу.

В· Взяти з черги.

В· Черга порожня.

В· Черговий елемент.

Реалізація черзі на основі лінійного списку

Опис типу змінних для реалізації черги: користуємося рекурсивним описом полів: Type typeelem = Integer; тип елемента черзі connect = ^ data; рекурсивне визначення покажчика data = Record elem: typeelem; тип інформаційної осередку next: connect тип покажчика End;

В цьому випадку кожна ланка міститься в покажчику попереднього ланки.

Процедура ініціалізації черзі включає в себе виділення пам'яті для створення нової осередки, покажчики присвоюються рівними нової осередку, покажчик на наступне ланка одно nil:

Процедура друкування вмісту черзі: незалежної змінної присвоюємо значення покажчика початку, задаємо цикл, до того моменту як покажчик не буде дорівнює nil; виписуємо вміст ланки і вказівником задаємо значення наступної ланки:

S: = Sn;

While s <> nil do begin

Write;

S: = S ^. Next; end;

Функція перевірки на порожнечу черзі виглядає наступним чином:

Empty : = Sn = SK ;

Функція може приймати два значення. Якщо початок і кінець співпадають, то функція дорівнює правді, і навпаки: не збігаються - брехні.

Процедура вставки:

new;

P ^. Next : = nil ;

P ^. Elem: = x;

Sk ^. Next: = p;

sk : = p ;

створюється нова ланка, покажчик якого дорівнює nil, інформаційної осередку надається якесь значення, і покажчик кінця пересувається до цієї ланки.

Черговий елемент черги: функції присвоюється значення першого елемента, покажчик початку пересувається на одну ланку.

Remove = Sn ^. Elem;

Sn: = Sn ^. Next ;

Для того щоб не було заповнення пам'яті непотрібною інформацією, використовують процедуру dispose , яка звільняє пам'ять.

P: = Sn;

Remove = Sn ^. Elem;

Sn: = Sn ^. Next;

Dispose;

Тема № 3: деки .

грудня як динамічна структура даних включає в себе характерні особливості черги і стека. Переміщення в черги здійснюється від її лівого кінця до правого, тобто від першого до останньому елементу. У стеці рух також йде в одну сторону, але порядок проходження елементів зворотний - від останнього елемента до першого. Грудень ж є двонаправленим списком, де рух може здійснюватися в обидві боку. Дек, як і чергою, визначається посиланнями на свої два кінця, однак, в відміну від черги, можна обробляти елементи на початку, в кінці і в середині.

грудня можна представити у вигляді ланок, кожен з яких складається з трьох полів: перше поле - поле елемента, друге - поле посилання на наступний елемент, третє - поле посилання на попередній. У схемі є дві посилання nil , кожна з яких обмежує рух по деку на його кінцях. Спосіб опису використовуваних типів даних, порівняємо з чергами, але тут вже є три поля.

Uses CRT ; {опис змінних}

Type typeelem = Integer;

connect = ^ data;

data = Record

elem: typeelem;

Next: connect;

Pred : connect

End ;

Процес вставки ланки в дек істотно відрізняється від раніше розглянутих випадків. У деці, як і в динамічній ланцюжку загального вигляду, новий елемент можна вставляти в будь-якому його місці, а, крім того, враховуючи двосторонній зв'язок ланок в деці, можна поставити питання про вставці до або після зазначеного елемента. Звідси випливає, що для вставки елемента в дек необхідно мати дві процедури: процедуру вставки елемента до заданого ланки і процедуру вставки елемента після заданого ланки. Вставка ланки в дек також супроводжується встановленням чотирьох зв'язків.

Для зменшення процедур можна використовувати допоміжні процедури:

Procedure insert1;

{занесення елемента в дек після заданого ланки}

var s1, s2, p: connect;

Begin

s1: = sn1;

s2: = sn2;

while s1 ^. elem <> y do s1: = s1 ^. next;

while s2 ^. pred ^. elem <> y do s2: = s2 ^. pred;

new;

p ^. elem: = x;

p ^. next: = s2;

p ^. pred: = s1;

s2 ^. pred: = p;

s1 ^. next: = p;

end;

{процедура Insert1 використовується при вставці елементу після заданого ланки за умови що це не початок або не кінець дека.}

Procedure insert3;

{занесення елемента в дек до заданого ланки}

var s1, s2, p: connect;

Begin

s1: = sn1;

s2: = sn2;

while s1 ^. next ^. elem <> y do s1: = s1 ^. next;

while s2 ^. elem <> у do s2: = s2 ^. pred;

new;

p ^. elem: = x;

p ^. next: = s2;

p ^. pred: = s1;

s2 ^. pred: = p;

s1 ^. next: = p;

end;

{процедура Insert3 використовується при вставці елементу до заданого ланки за умови що це не початок або не кінець дека}

Procedure insert2;

{занесення елемента в дек}

var p: connect;

Begin

if k = 'до ' then begin

new;

p ^. next: = nil;

p ^. elem: = x;

p ^. pred: = sn2;

sn...2 ^. next: = p;

sn2: = p;

end;

if k = 'н ' then begin

new;

p ^. pred: = nil;

p ^. elem: = x;

p ^. next: = sn1;

sn1 ^. pred: = p;

sn1: = p;

end;

End; {insert}

{ Insert2 - вставка елемента на початок або в кінець дека}

Використовуємо покажчик кінця дека: покажчику кінця дека присвоюємо значення нової ланки, покажчику останнього елемента присвоюємо значення нової ланки.

Procedure insertnext;

{занесення елемента x в дек після заданого ланки}

var s1, s2, p: connect;

Begin

s1: = sn1; s2: = sn2;

if then insert1

else insert2; end;

На противагу першого випадку, покажчику попереднього елемента присвоюємо значення нової ланки, покажчику кінця так само присвоюємо значення нової ланки.

Procedure insertpred;

{занесення елемента в дек до заданого ланки}

var s1, s2, p: connect;

Begin

s1: = sn1;

s2: = sn2;

if then insert3

else insert2

end;

Розглянуті процедури застосовні тільки для деков, що мають не менше однієї ланки, тому в якості самостійного завдання можна дати модифікацію даних процедур з урахуванням ставки ланки порожній і одноелементні деки.

Видалення ланки з дека полягає в його ізоляції від сусідніх ланок. Це означає, що посилання next попередньої ланки повинна бути переадресована на ланку, наступне за видаляється ланкою, а посилання pred - на ланку перед видаляється ланкою.

Function remove: typeelem;

{ видалення елемента з < i> дека }

var p: connect;

Begin

if andthen begin

remove: = s ^. elem;

s ^. next ^. pred: = s1 ^. pred ^. pred;

s ^. pred ^. next: = s ^. next ^. next;

end

Else begin

if s = sn1 then begin

p: = s;

remove: = s ^. elem;

s ^. next ^. pred: = nil;

sn1: = s ^. next;

dispose;

end;

if s = sn2 then begin

p: = s;

remove: = s ^. elem;

s ^. pred ^. next: = nil;

sn2: = s ^. pred;

dispose;

end;

End;

End; {remove}

Якщо ланка перше, то значенням функції присвоюємо значення першого елемента; якщо - друге, то - останнього елемента.

Висновок:

Використання динамічних структур даних ефективно застосовувати при вирішенні завдань, оскільки кожному значенню змінної виділяється якась область пам'яті, в ході чого відбувається облік ресурсів комп'ютера. При необхідності цю клітинку можна ліквідувати, якщо інформація знаходиться в цій комірці нам більше не знадобиться.

Звичайно, при вирішенні завдань за допомогою статистичних змінних обробка та доступ до інформації полегшується. При використанні статистичних структур даних відбувається нераціональне використання оперативної пам'яті, тому що для статистичних змінних виділяється фіксований розмір пам'яті.

стекового структур даних, черг і деков в середовищі В«ТУРБО ПАСКАЛЬ В»як тип змінних не існує, тому, для наочності, використовують масиви та лінійні списки.

Стек як структура даних використовується при вирішенні рекурсивних завдань, коли необхідно спочатку вирішити останню проблему, а вже за ним попередні проблеми. Рекурсивні процедури звертаються самі до себе, при цьому змінюються значення змінних, що передують значення яких складаються в стек. При виконанні початкової заданої умов, знаходиться рішення для найпростішої функції, потім більш складною.

Додаток

Стек:

1. Дан стек заповнений випадковим чином, з цілих чисел. Видалити з нього всі негативні елементи, використовуючи другий стек і одну змінну.

randomize;

init;

for i: = 1 to n do

begin

y: = random-random;

push;

end;

list; Writeln;

for i: = 1 to n do

begin

push);

pop;

end;

for i: = 1 to n do

begin

if stacktop> = 0 then

push);

pop;

end;

writeln;

list;

2. Дан стек заповнений цілими числами випадковим чином. Видалити з стека всі числа не кратні заданому з клавіатури.

randomize;

init;

for i: = 1 to n do

begin

y: = random-random;

push;

end;

list; Writeln;

for i: = 1 to n do

begin

push);

pop;

end;

writeln;

readln;

for i: = 1 to n do

begin

if) mod f = 0 then

push);

pop;

end;

writeln;

list;

3. Дан стек, що містить цілі числа. Використовуючи другий стек, записати в дно стека номер один суму всіх елементів.

randomize;

init;

for i: = 1 to n-1 do

begin

y: = random-random;

push;

end;

list; Writeln;

f: = 0;

for i: = 1 to n-1 do

begin

f: = f + stacktop;

push);

pop;

end;

push;

for i: = 1 to n-1 do

begin

push);

pop;

end;

list;

writeln;

4. Видалити з стека, який складено з цілих чисел заданих випадковим чином, кожен другий елемент. На дні перебуває перший елемент.

randomize;

init;

for i: = 1 to n do begin

y: = random;

push; end;

list; writeln;

while not emptydo begin

pop;

push);

end;

while not emptydo begin

push); end;

list; writeln;

5. Дан стек з цілих чисел, заповнений випадковим чином. З допомогою другого стека видалити останній негативний елемент.

randomize;

init;

for i: = 1 to n do begin

y: = random-random;

push; end;

list;

y: = 0;

while not empty do begin

if <0) and then begin pop; y: = 1; end;

push);

end;

list;

while not e...mpty do

push);

list;

6. Дан стек заповнений елементами типу typeelem. Видалити з стека передостанній елемент.

randomize;

init;

for i: = 1 to n do

begin

y: = random-random;

push;

end;

list; Writeln;

y: = pop;

pop;

push;

list; Writeln;

7. Дан стек заповнений елементами типу typeelem. Видалити з стека перший елемент і помістити його в вершину стека номер один.

randomize;

init;

for i: = 1 to n do

begin

y: = random-random;

push;

end;

list; Writeln;

repeat

y: = pop;

push;

until empty;

f: = pop;

repeat

y: = pop;

push;

until empty;

push;

list; Writeln;

8. Дан стек з цілих чисел, заповнений випадковим чином. Помістити вершину стека в дно, використовуючи допоміжний стек.

randomize;

init;

for i: = 1 to n do

begin

y: = random-random;

push;

end;

list; Writeln;

f: = pop;

repeat

y: = pop;

push;

until

repeat

until
9. Дан
for
begin

end;

repeat

until
repeat

until
10. Дан
for end;

while
else
end;

else writeln;

while end;

11. Дан
for
begin

end;

for
begin

end;

for
begin

end;

writeln;

12. Дан
for
begin

end;

for
begin

end;

for
begin

end;

writeln;

13. Дан
begin

end;

readln;

begin

end;

begin

end;

14. Дан
15. В
begin

end;

begin

end;

begin

end;

begin

end;

16. В
for
while
end;

while
end;

17. Стек
for
while
end;

while
while
18. Стек стека.

init;

for i: = 1 to n do

begin

y: = random;

push;

end;

list; Writeln;

while not emptydo

if stacktop mod 2 = 0 then push)

else push);

while not emptydo

push);

while not emptydo

push);

list;

19. Дан стек з цілих чисел, заповнений випадковим чином. Використовуючи тільки стеки, відсортувати елементи стека за зростанням. На дні стека мінімальний елемент, в вершині - максимальний. Використовуйте потрібну кількість стеків.

randomize;

init;

init;

init;

init;

for i: = 1 to n do

begin

y: = random;

push;

end;

list; Writeln;

while not emptydo begin

push);

while not emptydo begin

if stacktop> = stacktop then

begin push); push); end

else push); end;

push);

while not emptydo

push);

end;

while not emptydo

push);

list; Writeln;

20. Відсортувати стек, заповнений цілими числами, за спаданням. На дні стека повинен бути максимальний елемент, в вершині - мінімальний. Використовувати тільки потрібне кількість стеків.

21. Дан стек, заповнений випадковими цілими числами. Видалити з стека повторювані елементи, залишивши по одному.

randomize;

init;

init;

init;

init;

for i: = 1 to n do

begin

y: = random;

push;

end;

list; Writeln;

while not emptydo begin

push);

while not emptydo

if stacktop = stacktop then pop

else push);

while not emptydo

push);

end;

while not emptydo

push);

list ; Writeln ;

22. Видалити з стека, який складається з цілих чисел, всі числа, які не повторюються.

23. Стек заповнений однозначними і двозначними числами. Помістити однозначні числа в один стек, двозначні - в інший.

randomize;

init;

init;

init;

for i: = 1 to n do

begin

y: = random;

push;

end;

list; Writeln;

while not emptydo

if stacktopdiv 10 = 0 then push)

else push);

list; Writeln;

list; Writeln;

24. Дан стек, заповнений випадковим чином цілими числами. Помістити парні елементи в один стек, непарні - в другій.

25. Створити стек з цілих чисел, в якому кожен елемент дорівнює сумі попередніх елементів. Перший елемент дорівнює одному.

randomize;

init;

push;

y: = 0;

for i: = 2 to n do begin

y: = y + stacktop;

push; end;

list;

26. Дан стек з цілих чисел. Знайти мінімальний елемент стека і записати його в дно стека.

randomize;

init;

init;

init;

for i: = 1 to n-1 do

begin

y: = random-random;

push;

end;

list; Writeln;

push);

while not emptydo

if stacktop <= stacktop then begin push); push) end

else push);

push);

while not emptydo

push);

writeln;

list;

27. Знайти в стеці, складеному з цілих чисел, максимальний елемент і помістити його в дно стека.

28. В стеці, складеному з цілих чисел, знайти мінімальний елемент і помістити його в вершину стека.

randomize;

init;

init;

init;

for i: = 1 to n-1 do

begin

y: = random-random;

push;

end;

list; Writeln;

push);

while not emptydo

if stacktop <= stacktop then begin push); push) end

else push);

while not emptydo

push);

push );

writeln ;

list;

29. Дан стек з цілих чисел, заповнений випадковим чином. Знайти в стеку максимальний елемент і помістити його в вершину.

30. Дан стек, заповнений випадковим чином цілими числами. Відшукати в даному стеку максимальний і мінімальний елементи. Перемістити максимальний елемент в дно стека, мінімальний - у вершину.

randomize;

init;

init;

init;

for i: = 1 to n-1 do

begin

y: = random-random;

push;

end;

list; Writeln;

push);

while not emptydo

if stacktop <= stacktop then begin push); push) end

else push);

while not emptydo

push);

push);

push);

while not emptydo

if stacktop> = stacktop then begin push); push) end

else push);

push);

while not emptydo

push);

writeln;

list;

Гру:

1. Дан грудня з цілих чисел, заповнений випадковим чином. На початок дека вставити число, що вводиться з клавіатури.

2. Грудень складається з цілих чисел. Вставити в цей грудня нуль після числа вводиться з клавіатури.

3. Заповнити грудня цілими позитивними числами. Вставити в дек сьогоднішнє число до елемента, який дорівнює числу запроваджуваному з клавіатури.

4. Заповнити грудня випадковим чином цілими числами. Знайти максимальний елемент в утворився деці і вставити до і після нього нуль.

5. Дан дек, заповнений випадковим чином. До після мінімального елемента вставити тисячу.

6. У деці, що складається з цілих чисел, вставити перед попереднім елементом, рівним введеному числу з клавіатури, число дорівнює добутку елемента і попереднього елемента.

7. Грудень заповнений випадковими цілими числами. Сортувати даний дек по зростанню.

8. Заповнити грудня випадковими цілими числами і відсортувати його за спаданням.

9. Знайти суму всіх елементів дека, заповненого цілими числами, і помістити цю суму в кінець дека.

10. Знайти суму всіх елементів дека, який складається з цілих чисел, і приписати цю суму в початок дека.

11. Грудень заповнений випадковим чином цілими числами. Знайти в деці максимальний і мінімальний елементи і поміняти їх місцями.

12. Дан дек, заповнений цілими позитивними і негативними числами. Знайти в даному деці негативні елементи і видалити їх.

13. Видалити парні елементи дека, заповненого випадковим чином цілими числами.

14. Видалити непарні елементи в деці, який заповнений цілими числами.

15. Знайти в даному деці, заповненому випадковим чином, негативні елементи, видалити ці елементи та вставити замість них модулі віддалених.

16. Грудень складається з цілих негативних і позитивних чисел, заданих випадковим чином. Знайти і записати замість позитивних елементів, рівні їм по модулю негативні числа.

17. Перед негативними елементами даного дека, який складається з цілих негативних і позитивних чисел, вставити їх модулі.

18. Після кожного елемента дека вставити суму всіх елементів дека. Грудень складається з цілих чисел.

19. Видалити з дека всі двозначні числа. Грудень заповнений випадковим чином цілими числами.

20. Дан грудня з цілих чисел, заданих випадковим чином. Залишити в деці тільки двозначні числа, всі інші видалити.

21. Видалити з дека непарні негативні числа. Грудень заповнений випадковим чином цілими числами.

22. Грудень заповнений цілими позитивними і негативними числами. Видалити з дека всі позитивні парні числа.

23. Грудень складається з цілих чисел, заданих випадковим чином. Переписати грудня в зворотному порядку.

24. У деці знаходяться цілі числа. Додати в дек стільки елементів, щоб він став в два рази довше і симетричним, то є: перший елемент був рівний останньому, другий - передостаннього і так далі.

25. Дан грудня з цілих чисел, заданих випадковим чином. Якщо грудня містить парна кількість елементів, то додати в середину дека максимальний елемент; якщо ж Грудні містить непарну кількість елементів, то видалити з нього середній.

26. Дан грудня з цілих чисел, заданих випадковим чином. Якщо грудня містить парна кількість елементів, то додати в середину дека мінімальний елемент; якщо ж Грудні містить непарну кількість елементів, то видалити з нього середній.

Черга:

1. Дана чергу з цілих чисел. Видалити з неї всі негативні елементи.

2. Порівняти модулі сум позитивних і негативних елементів черги. Чергу заповнена цілими числами.

3. Додати в кінець черги суму модулів всіх елементів. Чергу складається з цілих позитивних і негативних чисел.

4. Чергу заповнена випадковим чином цілими числами. Додати в початок черги твір всіх елементів.

5. Відняти з усіх елементів черги число вводиться з клавіатури.

6. Додати до всіх елементів число вводиться з клавіатури. Чергу заповнена цілими числами.

7. Записати чергу в зворотному порядку. Чергу заповнюється з клавіатури.

8. Дана чергу з цілих чисел. Видалити з неї числа кратні заданому з клавіатури числа.

9. Елемент з початку черги поміняти з останнім елементом.

10. Дана чергу з цілих чисел. Поміняти в черзі перший елемент з другим, третій з четвертим і так далі до кінця черзі.

11. На початок черги помістити елементи з парними номерами, а вкінець - з непарними.

12. Чергу складається з цілих чисел. Помістити в початок черги парні, а вкінець - непарні елементи.

Основні процедури:

Стек:

{Реалізація стека на основі масиву}

Program st;

Uses Crt;

Const n = 10;

Type typeelem = Integer;

stack = Array Of typeelem;

Var s: stack; y: typeelem; i: Integer;

Procedure init; {створення стека }

Var i: Integer;

Begin

For i: = 1 To n Do s: = -1000

End; {init}

Procedure list; {роздруківка вмісту стека }

Var i: Integer;

Begin

Writeln;

i: = 1;

While And Do Begin Writeln; Inc End

End; {list}

Procedure push; {занесення елемента в стек }

Var i: Integer;

Begin

For i: = n Downto 2 Do s: = s;

s: = x

End; {push}

Function pop: typeelem; {видалення елемента з стека }

Var i: Integer;

Begin

pop: = s;

For i: = 1 To n-1 Do s: = s;

s: = -1000

End; {pop}

Function stacktop: typeelem; {зчитування верхнього елемента без видалення }
...
Begin

stacktop: = s

End; {stacktop}

Function empty: Boolean; {перевірка стека на порожнечу}

Begin

empty: = false;

End; {empty}

{-}

Begin {main}

Clrscr;

init;

list; Writeln;

For i: = 1 To 3 Do push;

Writeln; list;

Writeln);

y: = stacktop; Writeln; Writeln;

Writeln; list; Writeln;

For i: = 1 To 2 Do Begin y: = pop; Writeln End;

Writeln; list; Writeln;

y: = pop; Writeln;

Writeln; list;

Writeln);

Readln

End. {Main}

Черга:

{pеализация черзі на основі лін списку}

Program spisok;

Uses Crt;

Type typeelem = Integer;

connect = ^ data;

data = Record

elem: typeelem;

next: connect

End;

Var sn, s, sk: connect; x: typeelem; i: Integer;

Procedure init;

{створення черзі }

var p: connect;

Begin

new;

p ^. next: = nil;

sn: = p; sk: = p;

End; {init}

Procedure list;

{роздруківка вмісту черзі}

var s: connect;

begin

s: = sn ^. next;

while s <> nil do begin

write;

s: = s ^. next; end;

End; {list}

Function empty: Boolean;

{перевірка черзі на порожнечу}

Begin

empty: = sn = sk;

End; {empty}

Procedure insert;

{занесення елемента x в чергу}

var p: connect;

Begin

new;

p ^. next: = nil;

p ^. elem: = x;

sk ^. next: = p;

sk: = p;

End; {insert}

Function remove: typeelem;

{видалення елемента з черги}

Begin

remove: = sn ^. next ^. elem;

sn: = sn ^. next;

End; {remove}

{-}

Begin

ClrScr;

randomize;

init; {ініціалізація черзі }

for i: = 1 to 5 do begin

x: = random-random;

insert; {вставка елемента в чергу}

end;

list; writeln; {роздруківка вмісту черзі}

x: = remove; {видалення елемента з черги}

list; writeln; {роздруківка вмісту черзі}

Readln; End.

Гру:

{pеализация дека на основі лінійного списку}

Program dek;

Uses Crt;

Type typeelem = Integer;

connect = ^ data;

data = Record

elem: typeelem;

next: connect;

pred: connect

End;

Var sn1, sn2, s: connect; x, y: typeelem; i: Integer;

k: string;

Procedure init;

{створення дека }

var p: connect;

Begin

new;

p ^. next: = nil;

p ^. pred: = nil;

p ^. elem: = x;

sn1: = p;

sn2: = p;

End; { init}

Procedure listnext;

{роздруківка вмісту дека в прямому порядку}

var s: connect;

begin

s: = sn1;

while s <> nil do begin

write;

s: = s ^. next; end;

write;

End; { list}

Procedure listpred;

{роздруківка вмісту дека в зворотному порядку}

var s: connect;

begin

s: = sn2;

while s <> nil do begin

write;

s: = s ^. pred; end;

write;

End; {list}

Function empty: Boolean;

{перевірка дека на порожнечу}

Begin

empty: = sn1 = sn2;

End; { empty}

Procedure insert1;

{занесення елемента x в дек після заданого ланки}

var s1, s2, p: connect;

Begin

s1: = sn1;

s2: = sn2;

while s1 ^. elem <> y do s1: = s1 ^. next;

while s2 ^. pred ^. elem <> y do s2: = s2 ^. pred;

new;

p ^. elem: = x;

p ^. next: = s2;

p ^. pred: = s1;

s2 ^. pred: = p;

s1 ^. next: = p;

end;

Procedure insert3;

{занесення елемента x в дек до заданого ланки}

var s1, s2, p: connect;

Begin

s1: = sn1;

s2: = sn2;

while s1 ^. next ^. elem <> y do s1: = s1 ^. next;

while s2 ^. elem <> y do s2: = s2 ^. pred;

new;

p ^. elem: = x;

p ^. next: = s2;

p ^. pred: = s1;

s2 ^. pred: = p;

s1 ^. next: = p;

end;

Procedure insert2;

{занесення елемента x в дек}

var p: connect;

Begin

if k = 'до ' then begin

new;

p ^. next: = nil;

p ^. elem: = x;

p ^. pred: = sn2;

sn2 ^. next: = p;

sn2: = p;

end;

if k = 'н ' then begin

new;

p ^. pred: = nil;

p ^. elem: = x;

p ^. next: = sn1;

sn1 ^. pred: = p;

sn1: = p;

end;

End; {insert}

Procedure insertnext;

{занесення елемента x в дек після заданого ланки}

var s1, s2, p: connect;

Begin

s1: = sn1;

s2: = sn2;

if then insert1

else insert2

end;

Procedure insertpred;

{занесення елемента x в дек до заданого ланки}

var s1, s2, p: connect;

Begin

s1: = sn1;

s2: = sn2;

if then insert3

else insert2

end;

Function remove1: typeelem;

{видалення елемента з початку}

Begin

remove1: = sn1 ^. elem;

sn1 ^. next ^. pred: = nil;

sn1: = sn1 ^. next;

End; {remove}

Function remove2: typeelem;

{видалення елемента з кінця}

Begin

remove2: = sn2 ^. elem;

sn2 ^. pred ^. next: = nil; ...

sn2: = sn2 ^. pred;

End; {remove}

Function remove: typeelem;

{видалення елемента з дека }

var s1, s2, s, p: connect;

Begin

s1: = sn1; s2: = sn2;

if andthen begin

while s1 ^. next ^. elem <> y do s1: = s1 ^. next;

while s2 ^. pred ^. elem <> y do s2: = s2 ^. pred;

remove: = s1 ^. next ^. elem;

s1 ^. next: = s1 ^. next ^. next;

s2 ^. pred: = s2 ^. pred ^. pred;

end

else if then remove: = remove2

else remove: = remove1;

End; {remove}

{-}

Begin

ClrScr;

sn1: = nil;

sn2: = nil;

k: = 'до ';

init;

for i: = 2 to 10 do

insert2;

listnext;

writeln;

listpred;

writeln;

insertnext;

listnext;

writeln;

insertpred;

listnext;

writeln;

remove1;

listnext;

writeln;

listpred;

writeln;

remove2;

listnext;

writeln;

listpred;

remove;

writeln;

listnext;

writeln;

listpred;

Readln

End.

Література

стек грудня чергу змінна

1. Інформатика і освіта, № 5 - 1999.

2. Бабушкіна І.А., Бушмелева Н.А., Окулов С.М., Черних С.Ю. Конспекти з інформатики. - Кіров, 1997.

3. Грехем Р., Кнут Д., Паташнік О. Конкретна інформатика. - М.: Мир, 1988.

4. Вірт Н., Алгоритм + структура даних = програма.

5. Райнтлі, Абстракція і структура даних.

6. Зубов В.С., Довідник програміста. - 1999.

Вернуться назад