Стек С Динамической Структурой

ovaaal

New Member
07.11.2011
0
0
#1
В общем начал только-только разбираться со стеками, очередями и т.п.
Смысл, то понятен, но вот реализация (т.к. я только начинаю) хромает, да что уж говорить - ползает на четвереньках :(.
Вот нужно выполнить такую вот довольно-таки легкую (увы пока не для меня) задачу:
"Реализовать операции работы со стеком, построенным на основе динамических структур. Распечатать символы введенной пользовательской строки в обратном порядке."
Начал я пытаться реализовать все это дело (только начало, можно сказать, что практически ничего и не сделал-то я :(), но смысл улавливаю (возможно по-своему), но все же...
Код:
program stack_dm;
uses crt;
type
nodeptr=^nodetype; 
nodetype=record
number:char;
nextnode:nodeptr;
end;
var stack:nodeptr;
invalue,ch:char;
l,l2:string;
i:byte;
k:integer;
procedure push(var st:nodeptr; value:char); 
var
p:nodeptr;



begin
new(p);
p^.number:=value;
p^.nextnode:=st;
st:=p;
end;
procedure write_stack(stack:nodeptr);
var
p:nodeptr;
begin
p:=stack;
while p<>nil do
begin
write(p^.number:3);
p:=p^.nextnode;
end;
end;

begin
clrscr;
stack^.nextnode:=nil;
writeln('vvedite stek');
read(l);
k:=length(l);
for i:=1 to k do

begin
push(stack,l[i]);
read(l2[i]);
end;
write_stack(stack);
readkey;
end.
Как видно из кода - решил я все это делать "поэлементно", т.е. не строку целиком, а символы по отдельности заносить/выносить в стек, как-то так...
Прошу помощи :)
 

Senset

Well-Known Member
11.09.2006
136
0
14
Москва
#2
Стек - динамический список, который имеет один главный указатель (на голову стека)
Очередь - динамический список, который имеет два указателя (на голову и на конец очереди)
Кольцо - динам. список, который если имеет хотя бы 1 элемент то, не может иметь в указателях nil (если дошел до конца списка, указатель nextnode последнего элемента кидаешь на первый)... Хотя наверно зря я это написал

Насчет кода:
1) если правильно понял задание - то вот рабочий вариант. Tested: Borland TP 7.0
2) Главная переменная stack - это указатель на голову твоего стека, потому именно его а не его объект обнуляешь
3) при добавлении/удалении - фигурирует указатель al - адрес левого по порядку элемента стека... добавляется после него (если не nil) или в начало если (al=nil) - тоже самое с удалением
4) Исходя из особенности архитектуры "Стека" - добавляют как правило элементы в nil - это позволяет зеркально отразить данные в нем)
Принцип прост: LIFO - Last In First Out
5) После работы проги - необходимо самому очистить всю динамическую память... Это конечно может сделать и ось (если конечно не заглючит), когда .exe уничтожиться... но это не есть хороший стиль программирования.

Код:
program stack_dm;
uses crt;
type
nodeptr=^nodetype;
nodetype=record
number:char;
nextnode:nodeptr;
end;

var stack:nodeptr;
l:string;
k,i:integer;

procedure push(var st:nodeptr;al:nodeptr;value:char);
var p:nodeptr;
begin
new(p);
p^.number:=value;
if (al=nil)or(st=nil) then
begin
p^.nextnode:=st;
st:=p;
end
else
begin
p:=al^.nextnode;
al:=p;
end;
end;

procedure write_stack(stack:nodeptr);
var p:nodeptr;
begin
p:=stack;
while p<>nil do
begin
write(p^.number:3);
p:=p^.nextnode;
end;
end;

procedure delete_stack_element(var st:nodeptr;al:nodeptr);
var del:nodeptr;
begin
if st<>nil then
begin
if al=nil then
begin
del:=st;
st:=st^.nextnode;
end
else
begin
del:=al^.nextnode;
al^.nextnode:=del^.nextnode;
end;
dispose(del);
end;
end;

procedure CLEAR_STACK(var st:nodeptr);
begin
while st<>nil do delete_stack_element(st,nil);
end;

begin
clrscr;
stack:=nil;
writeln('vvedite stek');
readln(l);
k:=length(l);
for i:=1 to k do push(stack,nil,l[i]);
write_stack(stack);
CLEAR_STACK(stack);
readkey;
end.
 

ovaaal

New Member
07.11.2011
0
0
#3
Стек - динамический список, который имеет один главный указатель (на голову стека)
Очередь - динамический список, который имеет два указателя (на голову и на конец очереди)
Кольцо - динам. список, который если имеет хотя бы 1 элемент то, не может иметь в указателях nil (если дошел до конца списка, указатель nextnode последнего элемента кидаешь на первый)... Хотя наверно зря я это написал

Насчет кода:
1) если правильно понял задание - то вот рабочий вариант. Tested: Borland TP 7.0
2) Главная переменная stack - это указатель на голову твоего стека, потому именно его а не его объект обнуляешь
3) при добавлении/удалении - фигурирует указатель al - адрес левого по порядку элемента стека... добавляется после него (если не nil) или в начало если (al=nil) - тоже самое с удалением
4) Исходя из особенности архитектуры "Стека" - добавляют как правило элементы в nil - это позволяет зеркально отразить данные в нем)
Принцип прост: LIFO - Last In First Out
5) После работы проги - необходимо самому очистить всю динамическую память... Это конечно может сделать и ось (если конечно не заглючит), когда .exe уничтожиться... но это не есть хороший стиль программирования.

Код:
program stack_dm;
uses crt;
type
nodeptr=^nodetype;
nodetype=record
number:char;
nextnode:nodeptr;
end;

var stack:nodeptr;
l:string;
k,i:integer;

procedure push(var st:nodeptr;al:nodeptr;value:char);
var p:nodeptr;
begin
new(p);
p^.number:=value;
if (al=nil)or(st=nil) then
begin
p^.nextnode:=st;
st:=p;
end
else
begin
p:=al^.nextnode;
al:=p;
end;
end;

procedure write_stack(stack:nodeptr);
var p:nodeptr;
begin
p:=stack;
while p<>nil do
begin
write(p^.number:3);
p:=p^.nextnode;
end;
end;

procedure delete_stack_element(var st:nodeptr;al:nodeptr);
var del:nodeptr;
begin
if st<>nil then
begin
if al=nil then
begin
del:=st;
st:=st^.nextnode;
end
else
begin
del:=al^.nextnode;
al^.nextnode:=del^.nextnode;
end;
dispose(del);
end;
end;

procedure CLEAR_STACK(var st:nodeptr);
begin
while st<>nil do delete_stack_element(st,nil);
end;

begin
clrscr;
stack:=nil;
writeln('vvedite stek');
readln(l);
k:=length(l);
for i:=1 to k do push(stack,nil,l[i]);
write_stack(stack);
CLEAR_STACK(stack);
readkey;
end.
В общем-то и моя программа рабочая, немного не оптимальная, куча не нужых действий и переменных, да и помощь уже не требуется, я элементарно недопонял задание, и вот результат...
Ну вам тоже спасибо за помощь и внимание