Циклический односвязный список с зацикливанием через указатель (голову), Задача Опции

[zabludshiy]

Помогите добрые люди разобраться в следующей задаче: заполнить циклический односвязный список с зацикливанием «через голову». Дополнительные операции: a) добавить новый узел в хвост; б) вывести текущий список на экран ... примечание к задаче "Некоторые сложности представляет согласование типов указателей. Например, для инициализации пустого списка не всегда удается просто написать «Head := @Head», это может быть синтаксической ошибкой (в зависимости от настроек компилятора). Более корректно использовать явное преобразование типов: «Head := Link(@Head)». При этом важно, чтобы поле Next было обязательно описано как первое поле записи Node."

Прога получилась следующая:

 
program Lr_1;
{Вариант задания: циклический односвязный список с зацикливанием
"через голову".}
Type
  Link = ^Node;
  Node = record
    Next: Link;
    Data: Integer;
   end;
  List = Link;

Var
  choice: Integer;
  item: Integer;
  list1: List;

procedure menu;
{Приглашение к вводу команды}
begin
  Writeln('*************************************************************');
  Writeln('*                 Действие со списком:                                                         *');
  Writeln('* 2 - Добавить узел в хвост                                                                   *');
  Writeln('* 5 - выдача текущего списка на экран                                                  *');
  Writeln('* 0 - Завершить работу (+освобождение памяти)                                    *');
  Writeln('*************************************************************');
  Write('> ');
end;  {menu}

procedure InitList(var L: List);
{Инициализация списка}
begin
  l:=nil;
end;  {InitList}

procedure FreeList(var L: List);
{Освобождение памяти списка}
var
  p: list;
begin
  while L^.next <> link(@L) do
        begin
             p := L;
             L := L^.Next;
             Dispose(p);
        end;
end;  {FreeList}

procedure ShowList(L: List);
var p:list;
begin
  write('Текущий список ');
  p:=l;
  if p = nil then  {Пустой список}
    Write(' ->')
  else
    repeat
      Write(' -> ', p^.Data);
      p := p^.Next;
    until p = link(@l);
  Writeln;
end;  {ShowList}

procedure InTail(var L: List; item: Integer);
{Вставка узла с данными item в хвост списка L}
var
  p, q: Link;
begin
  p := New(Link);
  p^.Next := nil;
  p^.Data := item;
  if L = nil then
    begin
         L := p;
         p^.next:=link(@l);
    end
  else begin
    q := L;
    while q^.Next <> link(@l) do
      q := q^.Next;
      {Теперь q указывает на последний узел}
    p^.Next := q^.next;
    q^.Next := p;
  end;
end;  {InTail}

begin
  {Основная программа}
  InitList(list1);
  repeat
    menu;
    readln(choice);
    case choice of
      0: begin
           FreeList(list1);
           break;
         end;
      2: begin
           Write('Введите добавляемое значение: ');
           Readln(item);
           InTail(list1, item);
         end;
      5: begin
           showlist(list1);
         end;
    else
    end;
  until choice = 0;
end.

Заполняется без зависаний и выпадающих ошибок, но когда список выводится происходит зацикливание. Не могу понять почему, нигде не могу найти ни ответа ни подобного примера. Помогите кто чем может!!!

[IUnknown]

    repeat
      Write(' -> ', p^.Data);
      p := p^.Next;
    until p = link(@l);

Почему, собственно, P сравнивается не с самим L, содержащим нужное значение, а с его адресом? Интересно получается, в начале процедуры ты инициализируешь P := L, а сравниваешь уже P = @L... Пойми, адрес указателя и сам указатель - это совершенно разные вещи.

until P = link(L);

должно отработать без зацикливания...

Добавлено через 12 мин.
Кстати, при удалении списка у тебя "течет" память. Причина - та же:

procedure FreeList(var L: List);
var
   p : list;
begin
   while L^.next <> link(L) do // Вот так утечка прекращается
   begin
      p := L;
      L := L^.Next;
      Dispose(p);
   end;
end; {FreeList}

Так что перепроверяй все подобные конструкции (где сравнивается указатель и адрес)...

Сообщение отредактировано: IUnknown - 8.11.2011 10:07

[zabludshiy]

Спасибо за ответ, зацикливание прекратилось, но вот интересная вещь происходит, когда например задать значение item=1, то выводится 1 ->0, если задать второе значение, то выводится 1->2->0, т.е. ноль всегда выводится в хвосте и откуда берется вообще непонятно. И подскажите, пожалуйста, что значит "течет память", может имеется в виду, что уменьшается размер кучи - свободной динамической памяти? (если вопрос глупый, не обессудьте, программированием недавно занялся)

[IUnknown]

что значит "течет память"

Это значит, что не вся память, выделенная программой в куче, освобождена. Есть утечка: неосвобожденные участки памяти.

В общем, чтоб убрать нули и избавиться от утечек, было проще заново переписать процедуру удаления списка, и переработать процедуру добавления:

procedure FreeList(var L: List);
var
   p, q : list;
begin
   if L <> nil then // Если список пустой - сразу уходим
   begin
      q := L;
      repeat
         p := q^.next;
         dispose(q);
         q := p;
      until q = L;
      L := nil;
   end;
end; {FreeList}

procedure InTail(var L: List; item: Integer);
var
  p, q: Link;
begin
   p := New(Link);
   p^.Next := nil;
   p^.Data := item;

   if L = nil then
   begin
      L := p;
      p^.next := link(L); // Опять же, не надо работать с адресами !!!
   end
   else
   begin
      q := L;
      while q^.Next <> link(L) do q := q^.Next;
      p^.Next := q^.next;
      q^.Next := p;
   end;
end;  {InTail}

Теперь нет лишних нулей, и утечки памяти тоже ликвидированы...

[zabludshiy]

К задаче прилагалась схема, которую сразу не выложил (2 схема - структура списка, которую надо сделать), а приведенный код, как я понимаю, описывает структуру, изображенную на 1 схеме. Получается указатель next, который должен указывать на голову L, должен содержать адрес указателя L, т.е. @L, или "явное преобразование типов Head := Link(@Head)"?
Если я правильно понимаю задачу, надо добиться использования link(@L) вместо link(L), т.к. link(L) будет указывать на первую введенную переменную p:

 if L = nil then
   begin
      L := p;
      p^.next := link(L); // Опять же, не надо работать с адресами !!!
   end

, соответственно второй элемент списка будет указывать на первый элемент, а по условию задачи, он должен указывать на указатель-голову L.
Помогите, пожалуйста, разобраться или подскажите, где я заблуждаюсь?!

Сообщение отредактировано: zabludshiy - 8.11.2011 16:34

[IUnknown]

Если я правильно понимаю задачу, надо добиться использования link(@L) вместо link(L)

Нет. Использовать Link(@L) нельзя. Точка. Забудь об этом. Нельзя заткнуть рот компилятору насильным преобразованием какого-то постороннего значения к нужному тебе типу, и потом надеяться, что программа будет работать корректно.

2 схема - структура списка, которую надо сделать

А какой смысл в этом? Сделать какой-то левый указатель, который бы указывал на весь список, но не имел бы ни поля Data, ни поля Next? Зачем он нужен тогда? Чтоб память позанимать лишнюю? Реализация будет вот такая (решай сам, надо оно тебе или нет) :

program Lr_1;
uses crt;
type
{
   Link будет указателем на элемент списка, имеющий поля
   next и Data. Из подобных элементов и будет строиться "кольцо"

   ListPtr же будет указателем на САМ СПИСОК (у тебя на схеме
   он выглядит именно так: нечто, что указывает на начало кольцевого
   списка)
}
   Link = ^Node;
   Node =
   record
      Next : Link;
      Data : Integer;
   end;
   ListPtr = ^Link;

procedure menu;
begin
  Writeln('*************************************************************');
  Writeln('*                 Действие со списком:                      *');
  Writeln('* 2 - Добавить узел в хвост                                 *');
  Writeln('* 5 - выдача текущего списка на экран                       *');
  Writeln('* 0 - Завершить работу (+освобождение памяти)               *');
  Writeln('*************************************************************');
  Write('> ');
end;  {menu}

{ Инициализация списка: выделим память под этот "аппендикс", но указывать
  он пока ни на что не будет }
procedure InitList(var L: ListPtr);
begin
   new(L);
   L^ := nil;
end;  {InitList}

{ Освобождаем список: Все, как и раньше, но чтобы получить первый полезный
  элемент - обращаемся по адресу, который хранится в "аппендиксе" }
procedure FreeList(var L: ListPtr);
var
   p, q : Link;
begin
   if L^ <> nil then { "аппендикс" на что-то указывает? Тогда удаляем }
   begin
      q := L^; { "Первый" элемент списка }
      repeat
         p := q^.next;
         dispose(q);
         q := p;
      until q = L^; { До тех пор, пока не доберемся до того места, куда указывает L }

      dispose(L); { удаляем сам "аппендикс". Это можно делать и в другом месте }
      L := nil;
   end;
end; {FreeList}

{ Показываем список }
procedure ShowList(L: ListPtr);
var p : Link;
begin
   write('Текущий список ');
   P := L^; { Опять же, начинаем оттуда, куда указывает L }
   if p = nil then Write(' ->')
   else
      repeat
         Write(' -> ', p^.Data);
         p := p^.Next;
      until P = L^;
   Writeln;
end; {ShowList}

{ Добавляем элемент }
procedure InTail(var L: ListPtr; item : Integer);
var
  p, q : Link;
begin
   p := New(Link);  { Память выделяем в любом случае }
   p^.Next := nil;
   p^.Data := item; { Сохраняем данные }

   if L^ = nil then { Список был пуст? }
   begin
      L^ := p; { "Аппендикс" теперь указывает на добавленный элемент }
      p^.next := p; { , а элемент указывает сам на себя }
   end
   else
   begin { Нет, уже что-то добавлялось }
      q := L^;
      { Ищем жлемент, указывающий на "начало" }
      while q^.Next <> L^ do q := q^.Next;
      { И добавляем после него (между ним и "началом") новый элемент }
      p^.Next := q^.next;
      q^.Next := p;
   end;
end; {InTail}

var
   choice: Integer;
   item: Integer;
   list1: ListPtr;

begin
   { Основная программа }
   InitList(list1);
   repeat
      Menu;
      readln(choice);
      case Choice of
         0 : FreeList(list1);
         2 :
         begin
            Write('Введите добавляемое значение: ');
            Readln(item);
            InTail(list1, item);
         end;
         5:
         begin
            showlist(list1);
         end;
      
         else {}
      end { case };
   until choice = 0;
end.

[zabludshiy]

Уважаемый Владимир, задачу я не выбирал, передо мной ее поставили, я ее и решаю, во всяком случае, пытаюсь изо всех сил . Благодаря Вашей помощи, сдвинулся с мертвой точки, ввод типа uk=^link облегчил решение проблемы. Насколько я разобрался, переменные-указатели типа uk содержат адреса переменных-указателей типа link, что и нужно для решения задачи. Одного не понял, в рекомендации к задачи было указано "Head := Link(@Head)" откуда это описание link(@l) так и не нашел ни где...

Переработал свой код в соответствии с Вашим и получил следующую прогу:

 
program Lr_1;
...
uk=^link;

Var
  choice: Integer;
  item: Integer;
  list1: List;
  ukaz:uk;

procedure menu;
...
end;  {menu}

procedure InitList(var L: List);
{Инициализация списка}
begin
  l:=nil;
end;  {InitList}

procedure FreeList(var L: List);
{Освобождение памяти списка}
var
  p,q: list;
begin
  if l<>nil then
     begin
          q:=l;
          repeat
                 p:=q^.next;
                 dispose(q);
                 q:=p;
          until q=ukaz^;
          l:=nil;
     end;
end;  {FreeList}

procedure ShowList(L: List);
var p:list;
begin
  write('Текущий список ');
  p:=l;
  if p = nil then  {Пустой список}
    Write(' ->')
  else
    repeat
      Write(' -> ', p^.Data);
      p := p^.Next;
    until p = link(l);
  Writeln;
end;  {ShowList}

procedure InTail(var L: List; item: Integer);
{Вставка узла с данными item в хвост списка L}
var
  p, q: Link;
begin
  {p := New(Link);}
  new(p);
  p^.Next := nil;
  p^.Data := item;
  if L = nil then
    begin
         L := p;
         p^.next:=ukaz^;
    end
  else begin
    q := L;
    while q^.Next <> ukaz^ do
      q := q^.Next;
      {Теперь q указывает на последний узел}
    p^.Next := q^.next;
    q^.Next := p;
  end;
end;  {InTail}

begin
  {Основная программа}
  InitList(list1);
  ukaz:=@list1;
  repeat
    menu;
    readln(choice);
    case choice of
      ...

В таком виде прога, насколько я понимаю, удовлетворяет условию задачи и схеме, и при этом корректно работает.
Спасибо Вам, Владимир, за помощь!!!

Сообщение отредактировано: zabludshiy - 8.11.2011 22:28