[РЕШЕНО] Динамический список на Делфи/Паскаль. Требуется консультации

[Вадим Мошев]

Здравствуйте.

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

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

Пишу программу на Delphi 7.0, однако решил список отлаживать на Turbo Pascal 7.0.

По идее программы, список должен хранить в качестве информационной части записи, поля которых имеют различные типы, но, опять-таки, для тренировки над списком я решил просто хранить в нём числа типа byte.

Наработки (если их так можно назвать) у меня, конечно, есть, я их опубликую, но прежде - несколько слов ходе реализации этой структуры.

Существует несколько способов реализации списков (например, с использованием средств ООП), однако я решил не заморачиваться и реализовал свой список через простые записи:

type TNode = ^Node;

        Node = Record
                  data: byte;
                  next: ^Tnode;
               end;

Как видно, список будет реализован простой совокупностью его узлов (распространённый метод).
Далее, создаётся сам список, что происходит простым созданием его головы:

Procedure CreateList;
begin
 new(head);
 head:=nil;
end;

Список пустой, поэтому пока голова зануляется (устанавливается в nil). Для дальнейшего тестирования списка создана процедура для добавления элементов (по одному):

 
Procedure Add(x: byte);

begin

 if head = nil then
{Этот условной оператор выполняется единственный раз и только в том случае, если список ещё пуст. В этом случае добавление данных происходит в голову списка, ссылка на следущий элемент зануляется и потом - выход}
                begin
                 head^.data:=x;
                 head^.next:=nil;
                 exit
                end;

 new(curr);

 curr:=head;

 while curr^.next <> nil
               do curr:=(curr^.next)^;

 curr^.data:=x;

end;

Для того чтобы убедиться, что у меня всё правильно, я ввёл в свою программу процедуру для вывода всего списка на экран:

Procedure ShowList;
begin
     curr:=head;
     WriteLn;
     While curr^.next <> nil do
                             begin
                               writeLn('!!!!!!!!!!!'); {Это для отладки}
                               readkey; {И это тоже}
                               writeLn(curr^.data);
                             end;

end;

Ну и, собственно, весь код:

program Project1;

uses
  Crt;

type TNode = ^Node;

        Node = Record
                  data: byte;
                  next: ^Tnode;
               end;

 var curr, head: Tnode;

Procedure CreateList;
begin
 new(head);
 head:=nil;
end;

Procedure Add(x: byte);

begin

 if head = nil then
                begin
                 head^.data:=x;
                 head^.next:=nil;
                 exit
                end;

 new(curr);

 curr:=head;

 while curr^.next <> nil
               do curr:=(curr^.next)^;

 curr^.data:=x;

end;

Procedure ShowList;
begin
     curr:=head;
     WriteLn;
     While curr^.next <> nil do
                             begin
                               writeLn('!!!!!!!!!!!');
                               readkey;
                               writeLn(curr^.data);
                             end;

end;


 var k: byte;

begin
    ClrScr; writeln;


    CreateList;

    Read(k);
    Add(k);

    ShowList;


     ReadKey;


end.

Теперь, что же у меня происходит...
Запускаю программу на исполнение, ввожу число (например, 5). Процедура Add благополучно его принимает, далее вызывается процедура ShowList. Но на экран ничего не выводится.

Методом пошаговой трассировки (F7) мною было установлено, что проблемы возникают из-за двух противоречий в коде программы:
В процедуре добавления элементов:

head^.next:=nil

Здесь у меня написано, что после добавления элемента в голову, её ссылка уславливается в nil.

А в процедуре вывода элементов на экран написано:

     curr:=head;
     WriteLn;

While curr^.next <> nil do

Процедура вывода вызывается сразу же после процедуры ввода элементов в список.

Цикл у нас будет выполняться, пока ссылочная часть очередного элемента не будет пустой, а поскольку в проедуре добавления элементов ссылочная часть головы была занулена, а в процедуре вывода curr стал эквивалентен голове списка, цикл не выполняется ни разу, а сразу идёт переход в конец процедуры.

Но как тогда поступать иначе, ведь ссылочная часть последнего добавленного элемента в спике должна указывать в nil, верно?

Да и строка
curr:=(curr^.next)^; мне не очень симпатична...

Итак, я прошу помощи в реализации списка, не могли бы хорошо так меня проконсультировать, чтобы я более-менее понял и разобрался с этим.

Спасибо большое заранее.

[Son Of Pain]

Итак, по порядку.
1)

 type TNode = ^Node;

Поскольку это указатель (Pointer), принято называть такие типы PNode.

2)

                  next: ^Tnode;

Указатель на указатель? Символ ^ - лишний.

3)

 new(head);
 head:=nil;

Сначала ты выделяешь память для структуры, а потом обнуляешь указатель на нее. Зачем? Выделенный блок памяти становится недоступным для дальнейшего использования (memory leak). Строчка с new - лишняя.

4)

 if head = nil then
                begin
                 head^.data:=x;

Смотрим сюда внимательнее, и видим обращение по нулевому указателю - runtime error.

5)

 new(curr);
 curr:=head;

Ошибка, похожая на описанную в пункте 3. Вообще, в процедуре добавления элементов почти все неправильно. Она, например, может выглядеть так (для добавления вконец списка):

Procedure Add(x: byte);
var n, tmp:PNode;
begin
 new(n);
 n^.data:=x;
 n^.next:=nil;
 if head = nil then
     head:=n
 else begin
     tmp:=head;
     while tmp^.next <> nil do tmp:=tmp^.next;
     tmp^.next:=p;
 end;
end;

6) В процедуре вывода списка сейчас есть бесконечный цикл
После вывода значения на экран нужно написать

curr:=curr^.next;

и условие заменить на

while curr <> nil

[Вадим Мошев]

Большое спасибо тебе. Я ещё не всё проанализировал, но тем не менее, очень благодарен.

Да, действительно были вещи элементарные, которые я не углядел (видать, сильно утомился) но также есть и то, что мне следует подучить/запомнить/выучить