列表中的双面引用

Question

我刚刚开始学习Perl，我必须做一个包含引用的练习。

我必须创建一个程序，它构造一个带有双面引用的列表，它们作为命令行参数接收。在程序的开头，列表中只有一个元素 - 0.要浏览列表，正在使用引用，引用列表中唯一的元素 - 0。命令行的参数正在被逐一阅读并添加到元素后面，这是被引用的。添加一个参数时，引用会向右滑动一个元素（它引用新添加的元素）。还有两个特殊元素 - +和 - 。 +允许引用将一个元素向右移动， - 向左移动一个元素。此外，重要的是参考不会超出列表限制。

输出是列表正确顺序的所有参数。

附加要求是必须使用散列创建列表，散列包含指向相邻元素的链接。此外，我不能使用数组来存储整个列表。

有一些例子可以让你更容易理解这个概念，这是最有用的一个：

./3.pl A D - B C + E.

0 A B C D E

我现在所拥有的只是程序的开始，它远没有完成，也没有编译，但我无法弄清楚从那里去的地方。我已经尝试寻找有关双面引用的一些信息（我不确定我是否正确翻译它），但我似乎找不到任何东西。任何有关双面参考的信息或任何有关如何正确开始编写此程序的提示都将非常感激。

我的代码：

#!/usr/bin/perl 

use strict;
use warnings;

my $A= {
  value=>'0',
  prev=>'undef',
  next=>'$B'
};

my $B= {
  value=>'0',
  prev=>'$A',
  next=>'$C'
};

my $C= {
  value=>'0',
  prev=>'$B',
  next=>'undef'
};

for my $smbl(0..#$ARGV) {
  $A-> {value} = $ARGV[$smbl];
  $Α-> {next} = $ARGV[$smbl+1];
}

Answer 1

首先，你正在建设的是一个doubly linked list。

让我告诉你使用链表的最大诀窍：创建一个虚拟的“head”节点和一个虚拟的“tail”节点。您不会打印它们的值，但拥有它们将大大减少代码中的特殊情况数量，使其变得更加简单！

在核心，你将有三个“指针”（参考）。

• $head指向列表的第一个节点。
• $tail指向列表的最后一个节点。
• $cursor最初指向$tail的节点。将在此节点之前插入新节点。

处理+时，需要处理两种不同的情况：

• $cursor == $tail：错误！光标移动到列表末尾之外。
• $cursor != $tail：将$cursor指向它引用的节点之后的节点。

处理-时，您需要处理两种不同的情况：

• $cursor->{prev} == $head：错误！光标移动到列表开头之外。
• $cursor->{prev} != $head：将$cursor指向它引用的节点之前的节点。

处理插入节点时，由于虚节点，不需要执行检查！