Помощь - Поиск - Пользователи - Календарь
Полная версия: Задача на стеки и очереди.
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Анисия
Добрый день. Помогите разобраться с очередями и стеками. Как организовать очередь из n целых чисел. Пока взяла 5 чисел, это получается что надо сформировать массив. Посмотрите пожалуйста правильно сделала?

program Lab_4;
const max=5;
type Evt= integer;
var
elem:array [1..max] of Evt;
spos, rpos:integer;

end.

volvo
Цитата
это получается что надо сформировать массив
Тебе что, стек организовать надо на основе массива? Извращение... Стек - он тем и хорош, что не имеет ограничений, которые имеет массив, а ты опять хочешь его загнать в те же рамки?

В FAQ-е, в теме "Все о динамических структурах данных" есть информация о создании стеков/очередей в нормальном виде...
Анисия
Цитата(volvo @ 4.03.2009 13:33) *

Тебе что, стек организовать надо на основе массива? Извращение... Стек - он тем и хорош, что не имеет ограничений, которые имеет массив, а ты опять хочешь его загнать в те же рамки?

В FAQ-е, в теме "Все о динамических структурах данных" есть информация о создании стеков/очередей в нормальном виде...

Мне надо сформировать очередь из n чисел.
volvo
Очередь можно сформировать на основе статического массива, или на основе динамического выделения памяти. Какое формирование нужно тебе?

Вот тебе пример: сформировала ты очередь из 5-ти чисел, а преподаватель тебе говорит: а добавь-ка шестое число... И что? Выходишь из программы, меняешь цифры, перекомпилируешь, запускаешь заново и вводишь 6 чисел? А ведь этого можно избежать, и вводить столько чисел, на сколько хватит памяти. Ну, в общем решать тебе, конечно... Я просто говорю, как лучше, но как всегда это никого не интересует - все делают по-своему. А потом приходят, и говорят, что не сдали...
Lapp
Мне кажется, что дело даже не в том, что шестой элемент не влезет, а в том, что если взять заведомо большой массив (чтоб все влезло на все случаи жизни), то будет неоправданная трата памяти. Динамическая память хороша именно тем, что выделяется только тогда, когда она нужна.

Но использование памяти - это другая тема. И вполне возможно, что Анисия этого еще просто не знает. Так что ничего не вижу плохого в демонстрации собственно принципа очереди на статическом массиве. Вот, я продолжил (немного изменив некоторые идентификаторы) программу из первого поста:
program Lab_4;
const
max=5;
m=max-1;

type
tElem= integer;

var
Line: array [0..m] of tElem;
a: tElem;
spos,rpos,n: integer;


function Put(e: tElem): boolean;
begin
if n<Max then begin
Rpos:=(Rpos+1) mod max;
Line[Rpos]:=e;
Inc(n);
Put:=true
end
else Put:=false
end;


function Get(var e: tElem): boolean;
begin
if n>0 then begin
e:=Line[Spos];
Spos:=(Spos+1) mod max;
Dec(n);
Get:=true
end
else Get:=false
end;


procedure Init;
begin
Spos:=0;
Rpos:=m;
n:=0
end;

begin
Init;
WriteLn(Put(1));
WriteLn(Put(2));
WriteLn(Put(5));
WriteLn(Put(-1));
WriteLn(Put(10));
WriteLn(Put(4)); {тут очередь переполнится, и пойдет false}
WriteLn(Put(6));

while Get(a) do WriteLn('Got ',a);
ReadLn
end.
Анисия - разберешься?
Анисия
Цитата(Lapp @ 4.03.2009 19:28) *
Анисия - разберешься?
smile.gif Попробую...
Анисия
Подскажите что означает две команды Dec и Inс???
Lapp
Цитата(Анисия @ 5.03.2009 5:07) *

Подскажите что означает две команды Dec и Inс???

Dec(x) эквивалентно x:=x-1
Inc(x) эквивалентно x:=x+1
amega
а можно маденький вопросик? уже которою програму просматриваю. били на форуме я ни как не могу понять, чем отличается
type
tElem= integer;

var
Line: array [0..m] of tElem;
a: tElem;
spos,rpos,n: integer; //почему тогда здесь не писали тип telem?
function Put(e: tElem): boolean;

от того что мы просто зделает так

var
Line: array [0..m] of integer;;
a: integer;
spos,rpos,n: integer;
function Put(e: integer): boolean;
volvo
Цитата
//почему тогда здесь не писали тип telem?
Не путай теплое с мягким... TElem описывает тип данных, а то, что ты показал - это индексы, а они всегда целочисленные... А вот если тебе понадобится очень быстро сменить тип данных, с которыми работает программа, например, на вещественный (без лазания по коду и многократной перекомпиляции, чтоб выяснить "а где еще недопустимое присваивание"), то достаточно будет всего лишь изменить TElem.
amega
Цитата
Не путай теплое с мягким... TElem описывает тип данных, а то, что ты показал - это индексы, а они всегда целочисленные... А вот если тебе понадобится очень быстро сменить тип данных, с которыми работает программа, например, на вещественный (без лазания по коду и многократной перекомпиляции, чтоб выяснить "а где еще недопустимое присваивание"), то достаточно будет всего лишь изменить TElem.

о спасибо! буду знать теперь) good.gif
Анисия
Попробовала сегодня написать, счою программку на очереди. Ну не как не могу понять почему у меня выводится значения:
vvod 69
vvod 0
vvod 0
vvod 0

 
program ocher;
const
m=4;

type
tEl=integer;

var
line: array [1..m] of tEl;
a: tEl;
f,r, n:integer;

function vvod( e:tEl): boolean;
begin
if n<m then begin
f:=f+1;
line[f]:=e;
inc(n);
vvod:=true ; end
else vvod:=false; end;

function vivod( var e:tEl): boolean;
begin
if n>0 then begin
e:=line[r];
r:=r+1;
dec(n);
vivod:=true;
end
else vivod:=false; end;

procedure init;
begin
r:=0; f:=m; n:=0;
end;

begin
init;
writeln(vvod(2));
writeln(vvod(3));
writeln(vvod(4));
writeln(vvod(5));
writeln(vvod(6));

while vivod(a) do
writeln('vvod ', a);
readln;
end.

volvo
Добавь первой строкой {$R+} и запусти свою программу еще раз... Ты узнаешь много интересного smile.gif
Анисия
Выходит за пределы страницы blink.gif f:=f+1; на этой строке
Lapp
Цитата(Анисия @ 27.03.2009 7:16) *
Выходит за пределы страницы blink.gif f:=f+1; на этой строке
И это все, что ты можешь сказать?.. Это определила не ты, а железная машина. А ты должна из этого сделать выводы.

Но сначала поправка: не страницы, а массива. И не на этой строке, а на следующей.
Ты f чем инициалицировала? 4? Так. А потом к нему единицу прибавила? Прибавила. Что вышло? Правильно, 5. А массив у тебя размерности какой? 4. Так чего ты хочешь?.. blink.gif

Тебе надо сделать не просто приращение f, а циклическое приращение по модулю 5. И массив тебе, думаю, надо нумерновать с нуля, а не с единицы. Тогда приращение f сделаешь так:

f:=(f+1) mod 5;

Понятно?
Еще ты с m запуталась. Пусть m будет длина очереди, а нумерация - от 0 до m-1=m1.
Вот, смотри, я тебе все это сделал. И, ПОЖАЛУЙСТА, обрати внимание на формат.. Ну нельзя же программы писать как записки соседу по парте!..
program ocher;
const
m=5;
m1=m-1;

type
tEl=integer;

var
line: array [0..m1] of tEl;
a: tEl;
f,r, n:integer;

function vvod( e:tEl): boolean;
begin
if n<m then begin
f:=(f+1) mod m;
line[f]:=e;
inc(n);
vvod:=true
end
else vvod:=false
end;

function vivod( var e:tEl): boolean;
begin
if n>0 then begin
e:=line[r];
r:=r+1;
dec(n);
vivod:=true;
end
else vivod:=false;
end;

procedure init;
begin
r:=0; f:=m1; n:=0;
end;

begin
init;
writeln(vvod(2));
writeln(vvod(3));
writeln(vvod(4));
writeln(vvod(5));
writeln(vvod(6));

while vivod(a) do
writeln('vvod ', a);
readln;
end.

И последнее: зачем ты стала переделывать мой код? Только сейчас заметил, что он практически идентичен)). Для тренировки? smile.gif Ок, похвально, что не копи-пейст)).
Спрашивай еще, что неясно.
Анисия
Мне дали вот такое задание: организовать очередь из n целых чисел. Изменить ссылки так, чтобы последний элемент очереди стал первым, первый – вторым, вто-рой – третьим и т.д.
Анисия
Как я правидно поняла, надо циклом создавать очередь чисел, и первый эелемнт помещать в конец очереди

program ctack;

type link=^node;
eltype=integer;
node= record
elem:eltype;
next: link;
end;
list=link;
var start, last:link;


procedure zam( var l:list);
begin
if L<>nil then
begin
start:=l;
last:=l^.next;
l^.next:=nil;



А как сдвигать ссылку на следующий элемент7
volvo
Цитата
Изменить ссылки так, чтобы последний элемент очереди стал первым, первый – вторым, вто-рой – третьим и т.д.
Мне всегда нравятся вот такие задания... Просто великолепно. А ничего, что для этого не надо менять никакие ссылки? Это задание вообще не надо делать. Это не очередь уже, вот в чем дело... Ты в очереди когда-нибудь стояла? Знаешь, что это? Это FIFO - "первым пришел, первым вышел". А ты что предлагаешь? Пришел кто-то последним, тут его раз, перекинуть в самое начало, а всех отодвинуть? Какая-то коррумпированная очередь у тебя. Не пойдет... Не предназначена для этого очередь. Чтоб первый стал последним - легко, для этого достаточно изъять элемент из очереди, и добавить его снова, он добавится в конец... С деком твоя операция тоже делается легко, поскольку там очередь - двухсторонняя, там можно брать элемент с любой стороны, и добавлять его тоже в любую сторону, хоть в "голову", хоть в "хвост", он предназначен для таких операций, рассчитан на них. А очередь, увы, нет...

Поймите уже раз и навсегда: нельзя вообще лезть на уровень указателей, когда работаешь с очередью. Равно, как и с любой другой структурой данных. Твое дело при работе с очередями - запрограммировать 2 операции: Get (которая берет элемент из начала очереди), и Put (которая добавляет элемент в ее конец). Всё, ничего больше... Точно так же, как при работе со стеком никому в голову не придет менять указатели, все что надо - это Push/Pop, иначе это уже не стек, а простой список...
Lapp
Цитата(volvo @ 31.03.2009 11:22) *
А ты что предлагаешь? Пришел кто-то последним, тут его раз, перекинуть в самое начало, а всех отодвинуть?
yes2.gif ага, а так всегда и делалось у нас! smile.gif Так просто не отучишь..

Справедливости ради, замечу, что в принципе эту операцию можно осуществить, если в реализации очереди предусмотрена функция Length (Длина). Тогда просто нужно повторить перекладывание из начала в хвост Length-1 раз.

Мне кажется, нет смысла все это вещать пользователю Анисия. Человек, ни разу не сказавший тривиальное "спасибо" ни одному из отвечавших, практически не отвечающий на вопросы собеседников, вряд ли заслуживает каких бы то ни было советов или объяснений..
Анисия
unsure.gif sad.gif Спасибо за то, что указали за мою бестактность.... Больше не буду.

Но я действительно не понимаю.......
Анисия
Спасибо всем огромное!!!! У меня получилось!!! Эта задача была на полустатические структуры. ( я только не давно поняла это......) Вчиталась в учебник, и поменяв две строчки между собой у меня получилось...

line[f]:=e;
f:=(f+1) mod m;


Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.