Двусторонние ссылки в списке - PullRequest
2 голосов
/ 07 марта 2019

Я только начинаю изучать 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];
}

1 Ответ

4 голосов
/ 07 марта 2019

Прежде всего, то, что вы строите, называется двусвязным списком .

Позвольте мне рассказать вам самый большой трюк для работы со связанными списками: создайте фиктивный узел "head" и фиктивный узел "tail". Вы не будете печатать их значения, но их наличие значительно сократит количество особых случаев в вашем коде, делая его намного проще!

В ядре у вас будет три "указателя" (ссылки).

  • $head указывает на первый узел списка.
  • $tail указывает на последний узел списка.
  • $cursor изначально указывает на узел в $tail. Новые узлы будут вставлены перед этим узлом.

При обработке + необходимо учитывать две разные ситуации:

  • $cursor == $tail: Ошибка! Курсор переместился за конец списка.
  • $cursor != $tail: укажите $cursor на узел, следующий за тем, на который он ссылается.

При обработке - вам нужно разобраться в двух разных ситуациях:

  • $cursor->{prev} == $head: Ошибка! Курсор переместился за пределы начала списка.
  • $cursor->{prev} != $head: укажите $cursor на узел, предшествующий тому, на который он ссылается.

При обработке вставки узлов нет необходимости выполнять проверки из-за фиктивных узлов!

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...