使用Pascal在链表中插入元素

Question

我看到一些算法被设计为在这里的链接列表末尾添加elment，并浏览其他网站，然后我写了一个小程序，我认为它应该在列表末尾添加一个给定的元素，但它似乎不起作用。我的问题是，为什么它不起作用？

我定义指针和节点如下：

 Pointer = ^Node;
Node = record
    about : element;
    next : Pointer;
end;

下面的过程接收一个链表L和一个应该附加到L 末尾的q元素

首先，我定义了将在之后插入的记录

var INS : Poniter;
........
INS.about := q;

程序如下：

{temp := L}  {I'll use this for my attempt below }
if L<>NIL then
begin
  while L^.next<>NIL do
  begin 
  L:= L^.next;
  end;
  L^.next := INS;
  INS^.next := NIL; 
  {L:=temp;} {I'll explain this in my attempt below}
end
else
 begin
  L:= INS;
 end;

我还有一个小程序，可以打印链接列表的所有元素

 procedure displayElements(L : pointer);
 begin
  while L <> nil do
  begin
   writeln(L^.about);
   L := L^.next;
   end
 end;

问题是：在我运行反程序后，它只显示列表的最后两个条目。

关于这个问题的猜测：我相信它只显示最后两个，因为当我运行displayElements过程时，指针L已经是NIL之前的一个元素了-因为我使用了第二个算法-。

尝试一个解决方案：好吧，我想我需要把L放回第一位，这样当我使用displayElements时，它就会得到列表中的所有元素。但我怎么能做到呢？，我试着用上面的评论把L保存在临时中，但没有用。

有什么想法吗？。谢谢

Answer 1

这里有一个非常简单的程序，它可以执行您想要的操作。维护"tail"指针意味着您不必每次添加值时都遍历列表。如果这是您的代码，那么您将丢失插入中的"tail:=tmp"行：如果没有这一行，Display将打印第一个和最后一个条目，但不会打印在中间的条目。

type
 node = ^MyRec;
 MyRec = record
          value: integer;
          next: node
         end;
var
 head, tail: node;
Procedure Insert (v: integer);
var
 tmp: node;
begin
 new (tmp);
 tmp^.value:= v;
 tmp^.next:= nil;
 if head = nil
  then head:= tmp
  else tail^.next:= tmp;
 tail:= tmp;
end;
Procedure Display;
var
 tmp: node;
begin
 tmp:= head;
 while tmp <> nil do
  begin
   writeln (tmp^.value);
   tmp:= tmp^.next
  end;
end;
begin
 head:= nil;
 Insert (5);
 Insert (10);
 Display;
 Insert (15);
 Display;
 readln
end.

[编辑]

从你的评论来看，还需要进一步的解释。[专业模式开启]大约三十年前，当我开始编程时（OMSI Pascal在PDP 11/70上），链表和指针出现在每个自尊的程序中，但自1990年Delphi兴起以来，这种复杂性一直被隐藏着，大多数程序员现在从未见过裸指针。

链表有不同的格式：简单的和复杂的。简单类型在插入和删除点上有所不同：堆栈在同一端插入和删除，队列在一端插入和在另一端删除，列表允许在任何位置插入和删除。更复杂的类型是树和图。您的问题是关于队列的实现——插入总是在后面，删除在前面。

为了正确实现这一点，我们需要两个变量："head"指向队列的头，"tail"指向队伍的尾。这些变量是正常的全局变量；在程序的数据段中为它们分配存储器。指针是一个简单变量，其值是另一个变量的内存地址。最初，"head"不指向任何东西，因此其值为零（将其视为0）。

通常在教科书中，队列的构建伴随着显示内存分配方式的小框，但我不知道如何在这里做到这一点，所以解释会有点冗长。

当第一次插入发生时，运行时系统中的内存管理器从堆中分配12个字节，并将本地变量"tmp"的值设置为这12个字节中第一个字节的地址（这是"new（tmp）"）。在这12个字节中，"value"部分被设置为5，"next"部分被设为nil。然后程序检查"head"的值是什么：如果它为零，则该值（即上面分配的内存块的地址）将从"tmp"复制到"head）。如果"head"已经指向某个东西，那么"tmp"的值将复制到"tail^.next"（以前为零）。然后将"tmp"的值复制到尾部变量中。因此，"head"总是指向队列的开头，并且不会更改，而"tail"指向队列的末尾，并且每次插入新节点时都会更改。

让我们做一些调试：

When the program starts, head = nil, tail is undefined
After 'insert (5)', head = $870874, tail = $870874
After 'insert (10)', head = $870874, tail = $870880 
After 'insert (15)', head = $870874, tail = $87088C

显示时，

tmp:= head ......... tmp = $870874  (ie head)
tmp:= tmp^.next .... tmp = $870880
tmp:= tmp^.next .... tmp = $87088C
tmp:= tmp^.next .... tmp = nil

如果您的程序有多个队列，则每个队列需要两个变量，并且必须更改"Insert"才能接受两个参数（即给定队列的头和尾）。

不需要写入"new（head）"one_answers"new（tail）"-这样做会导致指向队列开始和结束的原始指针丢失。

[教授模式关闭]我希望这个解释能有所帮助。