在Free Pascal中的链表建模

Question

我目前正在解决在Free Pascal中使用指针创建单链表的问题。任务:

编写一个程序，从标准输入流中读取整数，直到文件结束;情况发生，然后它按照输入的顺序将所有输入的数字打印两次。数字的数量是事先不知道的，禁止对这个数字进行明确的限制。

在我的程序中，列表的构建顺序是错误的。如何构建正确的序列?

program InputStreamNumbers;
type
itemptr = ^item;
item = record
data: Integer;
next: itemptr;
end;
var
first, tmp: itemptr;
n: Integer;
begin
first := nil;            { make the list properly empty! }
while not SeekEof do            { number reading loop }
begin
read(n);
new(tmp);               { created }
tmp^.data := n;         { fill out}
tmp^.next := first;
first := tmp;           { include in the list}
end;
tmp := first;           { go through the list from beginning to end }
while tmp <> nil do             
begin
writeln(tmp^.data);
tmp := tmp^.next;        { move to the next element}
end;
end.

Answer 1

当您向列表中添加节点时，您将创建一个名为tmp的新节点并分配其数据。这是正确的。但是在如何向列表中添加新项目时出现了错误。错误在

tmp^.next := first; // this creates the backwards linkage 
first := tmp;

如果可以的话(假设它不违背你的任务)，多添加一个变量

last: itemptr;

，顾名思义，指的是列表中的最后一项。

目的是直接访问列表的末尾，以便更容易地添加项。否则，您需要从头遍历列表，直到找到最后一项(谁的item.next是nil)。

列表应该像这样结束:

first                                  last
|                                      |
v                                      v
item.next -> item.next -> item.next -> item.next = nil
.data        .data        .data        .data

我把实现留给你去做。但如果有帮助的话，最初first和last是零。创建一个项目后，first和last都指向该项目。创建第二个项目后，first仍然指向第一个创建的，但最后指向第二个…等等。