Главная

Процедуры, обслуживающие стек

Пнд, 02/14/2011 - 11:51 — tech
Темы учебника
Операции над указателями
Ссылочные и динамические переменные
Стек ("магазин")
Указатели, или ссылки (Pointer)
Задача: 

Создать процедуры для добавления элемента в стек (add), удаления элемента из стека (del), вывода содержимого стека на экран (wstack).

Описание переменных: 

top – указатель на конец стека;
p – указатель на обслуживаемую в текущий момент область памяти.

Алгоритм решения задачи: 

В теле основной ветки программы переменной top присваивается значение nil, т.е. стек еще не заполнен.

Добавление элемента в стек

Процедура add принимает в качестве фактического параметра число x, которое будет записано в содержательную часть элемента стека.

Выделяется память под указатель p, в содержательную часть которого записывается x, а в указатель – адрес, хранимый в top. Переменная top, в свою очередь, начинает ссылаться на выделенную под p область памяти.

Удаление элемента из стека

В процедуре del в переменную p записывается адрес предпоследнего элемента стека. Последний элемент, ссылка на который хранится в top, удаляется. Далее top присваивается адрес элемента, на участок памяти, который указан p. К этому времени он стал уже не предпоследним, а последним элементом.

Удаление не происходит, если стек пустой (top указывает на nil).

Вывод стека на экран

Сначала p указывает на последний элемент. Выражения цикла while будут выполняться до тех пор, пока в p не запишется nil; это будет означать то, что перед этим был обработан первый элемент стека (который обрабатывается последним). В цикле сначала на экран выводится содержательная часть динамической переменной, на которую указывает p. Затем значение p меняется: переменная начинает указывать на следующий элемент.

Программа на языке Паскаль:  

type
    pitem = ^item;
    item = record
        data: integer;
        prev: pitem
    end;
 
var
    top, p: pitem;
    n, k: integer;
 
procedure add(x:integer);
begin
    new(p);
    p^.data := x;
    p^.prev := top;
    top := p
end;
procedure del;
begin
    if topnil then begin
        p := top^.prev;
        dispose(top);
        top := p
    end;
end;
procedure wstack;
begin
    writeln('Содержимое стека: ');
    p := top;
    while p  nil do begin
        write(p^.data, ' ');
        p := p^.prev;
    end;
    writeln;
end;
 
begin
    top := nil;
    for k := 1 to 10 do
        add(k);
    wstack;
    writeln('Введите добавляемое в стек значение: ');
    readln(n);
    add(n);
    wstack;
    writeln('Количество элементов стека для удаления? ');
    readln(n);
    for k:=1 to n do
        del;
    wstack;
readln
end.

Примечания: 

Основная ветка программы может быть любой. В приведенной выше программе сначала стек заполняется числами от 1 до 10 (процедура add вызывается 10 раз), затем они выводятся на экран. Пользователь вводит число, оно добавляется в стек. В конце программы указывается количество удаляемых элементов, после чего в цикле удаляется именно это количество элементов стека.

  • Добавить комментарий