Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

2.Вторую дисциплину принято называть LIFO (Last input — First output, т.е. последний  пришел — первый ушел), при которой на обслуживание первым выбирается тот элемент очереди, который поступил в нее последним. Очередь такого вида в программировании принято называть СТЕКОМ (магазином) — это одна из наиболее употребительных структур данных, которая оказывается весьма удобной при решении различных задач.
В силу указанной дисциплины обслуживания, в стеке доступна единственная его позиция, которая называется ВЕРШИНОЙ стека — эта позиция, в которой находится последний по времени поступления в стек элемент. Когда мы заносим новый элемент в стек, то он помещается поверх вершины и теперь уже сам находится в вершине стека. Выбрать элемент можно только из вершины стека; при этом выбранный элемент исключается из стека, а в его вершине оказывается элемент, который был занесен в стек перед выбранным из него элементом (структура с ограниченным доступом к данным).

Алгоритм

ОПЕРАЦИИ НАД СТЕКАМИ:
— PUSH ( s , i ) — занесение элемента в стек, где s — название стека, i — элемент, который заносится в стек;
— POP ( s ) — выборка элемента из стека. При выборке элемент помещается в рабочую область памяти, где он используется;
— EMPTY ( s ) — проверка стека на пустоту (true — пуст, false — не пуст);
— STACKTOP ( s ) — чтение верхнего элемента без его удаления.

Фрагмент программы создания стека (необходимые процедуры)

Program STACK;
const
max_st=50;
const
max_st=50;
var
st,st2: array[1..max_st] of integer;
n:integer;

function empty:boolean;  {Проверка стека на наличие элементов в нем}
begin
empty:=n=0
end;

procedure push(a:char);  {Поместить элемент в стек}
begin
inc(n);
st[n]:=a;
end;

procedure pop(var a:char);  {Извлечь элемент из стека}
begin
a:=st[n];
dec(n);
end;

function full:boolean;   {Проверка на переполнение}

begin
Full:=n=max_st
end;

procedure stacktop(var a:char);  {Узнать верхний элемент}
begin
a:=st[n];
end;

begin  {Основная программа}
.
.
end.

Задания

Ввести символы, формируя из них стек.
Варианты :
1.Поменять местами первый и последний элементы стека.
2.Развернуть стек, т.е. «дно» стека сделать вершиной, а вершину — «дном».
3.Удалить элемент, который находится в середине стека, если нечетное число элементов, а если четное, то два средних.
4.Удалить каждый второй элемент стека.
5.Вставить символ ‘*’ в середину стека, если четное число элементов, а если нечетное, то после среднего элемента.
6.Найти минимальный элемент и вставить после него 0.
7.Найти максимальный элемент и вставить после него 0.
8.Удалить минимальный элемент.
9.Удалить все элементы, равные первому.
10.Удалить все элементы, равные последнему.
11.Удалить максимальный элемент.
12.Найти минимальный элемент и вставить на его место 0.
Вывести полученный стек на экран.
Распечатать полученный стек.

Лабораторная работа № 2. «СПИСКОВЫЕ СТРУКТУРЫ ДАННЫХ»

Страницы: 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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники