Как найти начало кругового списка? - PullRequest
Новая
       23

Как найти начало кругового списка?

0 голосов
/ 29 мая 2020

Я пытаюсь реализовать список и итератор списка, например C ++ STL.

Узел в списке определяется следующим образом: 

struct Node{
  Node *prev,*next;
  value_type data;
};

И я хочу перегрузить оператор> и <: </p> 

bool list_iterator::operator>(const iterator_impl_base &rhs) const
bool list_iterator::operator<(const iterator_impl_base &rhs) const

, что означает, что если мне нужно позвонить next, чтобы достичь rhs.node, он вернет 0 в> и вернет 1 в <. </p>

, если мне нужно вызвать prev чтобы достичь rhs.node, он возвращает 1 в> и возвращает 0 в <. </p>

И я реализую список, используя круговой список. Ниже приведена одна часть класса списка: 

class List : public ordered_container {
 protected:
  Node* begin_;
  Node* end_;
  size_type size_;
 public:
    List::List() : end_(new Node){
        begin_ = end_->prev = end_->next = end_;
        size_=0;
    }
}

Итак, я не знаю, как отличить guish, передаю ли я просто begin_ of list. Может ли кто-нибудь помочь мне в этом? Спасибо.

Ответы [ 2 ]

2 голосов
/ 29 мая 2020

Во-первых, использование operator< для обозначения «предшествует» - это странно . Я знаю, что это упражнение, я просто не хочу, чтобы вы думали, что это нормально.

Теперь ваш круговой список хранит начало и конец в объекте контейнера верхнего уровня, поэтому нет возможности для самого узла чтобы сказать, голова это или след, или разворот. Это может сказать только контейнер.

Обычное решение для кольцевых списков - установить контрольный узел между головой и хвостом. Тогда sentinel.next - это голова, sentinel.prev - это хвост, и вам нужен какой-то способ пометить самого часового (либо значение magi c, равное data, либо дополнительный флаг). Затем этот контрольный узел может заменить два указателя в вашем объекте-контейнере (так что вы не тратите впустую место).

У часового есть дополнительное преимущество, заключающееся в том, что вам никогда не придется беспокоиться о nullptr в пустом списке.

Между прочим, мне очень странно, что инструкторы оставляют использование двусвязных списков и не показывает расположение дозорных. Он описан на нескольких страницах в копии книги Элсона о структурах данных, которую я унаследовал и которая была опубликована в 1975 году. Какой смысл намеренно обучать плохому двусвязному списку?

Если они хотят, чтобы вы выяснили это сами, им следовало бы попросить вас проработать основные операции со списком, а не эти нечетные операторы «предшествует / завершается», поскольку базовые c операции могут действительно работать без дозорного, но заметно улучшены с его дополнением.

0 голосов
/ 29 мая 2020

Элемент a меньше другого элемента b, если вы можете достичь b перед end, следуя за next.

Элемент a больше другого элемента b iff b меньше a.

...