Повернуть список Опции

[neic]

Народ подскажите процедуру поворота списка, а то я скоро уже с ума сойду.

Например вводим с клавиатуры (признаком окончания ввода является цифра 0): 1 2 3 4 5 ... 0

Нужно получить: 0 ... 5 4 3 2 1

Заранее благодарен!

[volvo]

А вот тут, кстати, функция init как раз и создает сразу "перевернутый" список: список

[neic]

Так там меняются местами первый и второй элемент, а мне нужно неограниченное число повернуть... или я что не догнал... просто голова уже не соображает

Список создаётся в момент ввода чисел с клавиатуры, а уже полученный список перевернуть.

Плюс ругается на строчку (в примере который ты дал):
r^.Next:=init;

Ошибка 88 говорит что не хватает какой-то скобки.


Добавлено через 8 мин.
Вот я тут на калякал.
Ссылается на procedure ps и говорит что куча переполнена, что я не так сделал?

uses crt;

type tinf=integer;
	tp=^node;
		node=record
			inf:integer;
			sled:tp;
		end;

var head,pn,pss,p:tp;

procedure init(var head:tp);
begin
		head:=nil
end;

procedure vkln(iel:tinf);
begin
	new(pn);
	pn^.inf:=iel;
	pn^.sled:=head;
	head:=pn;
end;

procedure ps(ifn:tinf);
begin
	new(p);
	p^.inf:=ifn;
	p^.sled:=head;
	head:=pn;
end;

Procedure Print(p: tp);
begin
	while p <> nil do begin
		write(p^.inf,' ','');
		p:=p^.sled;
	end;
	writeln;
end;

var s:integer;
begin
clrscr;
init(head);

writeln('‚ўҐ¤ЁвҐ зЁб«  ®в 1 ¤® 99. Љ®­Ґж®¬ ўў®¤  пў«пҐвбп жЁда  0');
repeat
	read(s);
	vkln(s);
until s=0;

print(pn);

pn^.sled:=head;

while pn <> nil do begin
		pn:=pn^.sled;
		ps(pn^.inf);
end;
writeln;

print(p);

readkey;
end.

Сообщение отредактировано: neic - 30.11.2007 22:04

[volvo]

Список создаётся в момент ввода чисел с клавиатуры

Ну, и КАКОЙ список создается, ты не обратил внимания? Ввожу я "1 2 3 4 0", что мне print() напечатает? Чтоб печаталось ТО ЖЕ САМОЕ, что вводишь, надо по-другому организовывать заполнение списка:

uses crt;

type
  tinf=integer;
  tp=^node;
  node=record
    inf:integer;
    sled:tp;
  end;

var
  head, tail: tp;


procedure vkln(iel:tinf);
var new_p: tp;
begin
  new(new_p);
  with new_p^ do begin
    inf := iel;
    sled := nil;
  end;

  if tail = nil then head := new_p
  else tail^.sled := new_p;

  tail := new_p;
end;

procedure Print(p: tp);
begin
  while p <> nil do begin
    write(p^.inf:4);
    p:=p^.sled;
  end;
  writeln;
end;

procedure reverse(p: tp);
begin
  if p <> nil then reverse(p^.sled)
  else exit;

  vkln(p^.inf);
end;

var
  s:integer;

begin
  clrscr;
  head := nil; tail := nil;

  writeln('0 to finish...');
  repeat

    read(s);
    vkln(s);

  until s=0;
  print(head);

  tail := nil;
  reverse(head);

  print(head);
end.

Теперь ясно?

[neic]

Единственное что я не понял, что такое tail и заче он нужен?

Сообщение отредактировано: neic - 3.12.2007 11:51

[volvo]

что такое tail и заче он нужен?

Tail - это "хвост" списка. А нужен он как раз для того, чтобы новый элемент добавлялся к "хвосту" - следовательно, в конец списка; тогда элементы будут располагаться в списке точно в том же порядку, в котором они вводились пользователем, а не в инверсном.

[neic]

ОК. Понял. Спасибо за помощь. Ставлю +.

[volvo]

Ставлю +

Пока с этим придется подождать... До набора тобой 25 сообщений... Или обратиться к модерам с соответствующей просьбой...

[neic]

Ещё один вопрос. А как работает процедура: reverse?

[volvo]

Рекурсивная процедура - сначала "разбирает" список, последовательно проходя по нему, соответственно в стеке будут храниться указатели на все элементы списка. А потом, когда список закончится, начнется "раскручивание" рекурсивных вызовов, при этом те значения, которые были ближе к концу списка, будут фигурировать как параметр P раньше, чем те, которые были в начале списка. Собираем изо всех значений, на которые указывают параметры P, новый список, и он выходит перевернутым относительно исходного.

Вот тебе простейший пример, чтоб было понятно, как это работает...

Допустим, исходный список = <1, 2>
Вызываем Reverse(<1, 2>), P указывает на (1).
Проверяем условие: параметр - нулевой указатель? Нет, вызываем Reverse(<2>), P указывает на 2...

Опять проверка условия - и опять P - не nil, вызываем Reverse(<>), P - нулевой указатель, потому как 2 - это последний элемент списка.

Вот теперь после проверки условия (оно не выполнено) - выходим из рекурсии по Exit... Но вышли-то мы только из последнего рекурсивного вызова, а в стеке висят еще два предыдущих уровня рекурсии... После выхода из последнего уровня возвращаемся в тот уровень (причем возвращаемся уже в точку ПОСЛЕ проверки условия, именно на строку с Vkln), где P указывал на 2... Кстати, почему указывал? Он же и сейчас все еще указывает, добавляем эту двойку в новый список. Он теперь равен <2>... Выполнили этот уровень - выходим еще на один выше: тот, с которого начали, но ведь там P указывает на единицу... Добавили единицу - <2, 1>... А вот теперь окончательно выходим из рекурсии и возвращаемся в вызывающую программу...

Что получилось в результате? Был список <1, 2> стал - <2, 1>... Перевернули, правда?

Я понимаю, что если ты никогда не имел дела с рекурсией, то выглядит то, что я написал сейчас просто устрашающе... Нужно пройтись по процедуре Reverse в пошаговом режиме, и посмотреть на окна Call Stack и Watches - тогда поймешь, что там творится...

Как пользоваться отладчиком - можешь посмотреть здесь: Отладка программ , я там написал самое основное...