пользователей: 30398
предметов: 12406
вопросов: 234839
Конспект-online
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

Динамические структуры данных (ДСД). Стек. Задача о правильном расположении скобок в формуле. Решение задачи при помощи массива и списка. Системный стек Windows.

 

Строение ДСД: набор узлов, объединенных с помощью ссылок. Вид узла: Данные+ссылки на другие узлы. Типы структур: Списки, деревья, графы.

 

Стек – это линейная структура данных, в которой добавление и удаление элементов возможно только с одного конца (вершины стека). Stack = кипа, куча, стопка (англ.)

LIFO = Last In – First Out

«Кто последним вошел, тот первым вышел».

Структура

const MAXSIZE = 100;

type Stack = record { стек на 100 символов }

            data: array[1..MAXSIZE] of char;

            size: integer; { число элементов }

            end;

Добавление

procedure Push( var S: Stack; x: char);

begin

 if S.size = MAXSIZE then Exit;

 S.size := S.size + 1;

 S.data[S.size] := x;

end;

Снятие

function Pop ( var S:Stack ): char;

begin

 if S.size = 0 then begin

            Result := char(255);

            Exit;

 end;

 Result := S.data[S.size];

 S.size := S.size - 1;

end;

 

Задача: вводится символьная строка, в которой записано выражение со скобками трех типов: [], {} и (). Определить, верно ли расставлены скобки (не обращая внимания на остальные символы). Примеры:

            [()]{}   ][      [({)]}          

Упрощенная задача: то же самое, но с одним видом скобок.

Решение: счетчик вложенности скобок. Последовательность правильная, если в конце счетчик равен нулю и при проходе не разу не становился отрицательным.
Алгоритм:

1)в начале стек пуст;

2)в цикле просматриваем все символы строки по порядку;

3)если очередной символ – открывающая скобка, заносим ее на вершину стека;

4)если символ – закрывающая скобка, проверяем вершину стека: там должна быть соответствующая открывающая скобка (если это не так, то ошибка);

5)если в конце стек не пуст, выражение неправильное.

 

var br1, br2, expr: string;

            i, k: integer;

            upper: char;    { то, что сняли со стека }

            error: Boolean; {признак ошибки }

            S: Stack;

begin

 br1 := '([{'; br2 := ')]}';

 S.size := 0;

 error := False;

 writeln('Введите выражение со скобками');

 readln(expr);

 {основной цикл обработки }

for i:=1 to length(expr)

do begin

            for k:=1 to 3 do begin

            if expr[i] = br1[k] then begin {откр. скобка }

            Push(S, expr[i]);{втолкнуть в стек}

            break;

            end;

            if expr[i] = br2[k] then begin { закр. скобка }

            upper := Pop(S); {снять символ со стека }

            error := upper <> br1[k];

            break;

            end;

            end;

            if error then break;

 end;

 if not error  and  isEmpty(S) then

            writeln('Выражение правильное.')

 else writeln('Выражение неправильное.')

end.

Системный стек windows

Используется для

1)размещения локальных переменных;

2)хранения адресов возврата (по которым переходит программа после выполнения функции или процедуры);

3)передачи параметров в функции и процедуры;

4)временного хранения данных (в программах на языке Ассмеблер).

Переполнение стека (stack overflow):

1)слишком много локальных переменных

(выход – использовать динамические массивы);

2)очень много рекурсивных вызовов функций и процедур

(выход – переделать алгоритм так, чтобы уменьшить глубину рекурсии или отказаться от нее вообще).

21.           


22.01.2015; 17:47
хиты: 184
рейтинг:0
Точные науки
информатика
Языки программирования
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2024. All Rights Reserved. помощь