Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Ограничители (sentinel) в связных списках. Смысл?

444
11 августа 2010 года
patison
323 / / 15.03.2007
Недавно прочёл о так называемых ограничителях в связных списках.
Согласно литературе, использование этих ограничителей (которые представляют собой ничто иное как условно нулевой элемент списка) позволяет упростить обход списков, удаление элементов, вставку и тд

В упор не могу понять - каким образом оно упрощает код. Сейчас, в циклах, я просто проверяю является-ли listNode равным 0.
Может кто-нибудь прояснить для меня - каким конкретно образом эти так называемые ограничители упрощают работу со списками?
1.8K
11 августа 2010 года
LM(AL/M)
332 / / 20.12.2005
ха! прочитал в википедии что это такое и понял что сам этим пользовался не раз )
444
11 августа 2010 года
patison
323 / / 15.03.2007
Ну так может поделишься опытом? )) Какой смысл этих нулевых элементов, если указатель на следующий (предыдущий, голову или хвост) элемент можно просто прировнять к нулю.
1.8K
11 августа 2010 года
LM(AL/M)
332 / / 20.12.2005
при программировании вставки/удаления элементов в/из списка типичны такие конструкции:

node.left.right := node;
node.right.left := node;

но node.left и/или node.right могуть быть 0, приходится делать проверку, код становится некрасивым и теряет эффективность. если же вставить парочку фиктивных элементов в начале и в конце списка, то эти ссылки никогда не станут 0
Правда при этом возникает небольшая трудность с тем чтобы фиктивные элементы не включились в обработку наравне с остальными элементами)

Если говорить про личный опыт, то мне это помогло однажды избежать трудностей с пустотой списка: чтобы не писать специфичный кусок кода для случая когда ссылка на 1-й node списка обнулилась я завёл фиктивный элемент и теперь списиок никогда не становился по настоящему пустым, код упростился
5
11 августа 2010 года
hardcase
4.5K / / 09.08.2005
Это частный случай паттерна Null Object.
Его применение позволяет избежать NRE (Null Reference Exception) в сложных алгоритмах. Использование этого подхода позволяет обходиться без проверки на null указателей, что упрощает код и способствует его стабильности.
444
11 августа 2010 года
patison
323 / / 15.03.2007
LM(AL/M):
Ну хорошо, допустим не делается проверка на то является-ли элемент нулём. Просто присваивается в этот элемент что-то и всё. А что если этот элемент у нас как раз тот самый фиктивный? Получается, что нам нужно-таки делать проверку, и в случае если элемент фиктивно-нулевой - то нам нужно создать новый фиктивный элемент. Как-то громоздно получается.

Можете показать пример кода?

hardcase: Это-то я понял. Я вот только не могу понять другого - ведь всё равно нужно будет делать проверку на то является-ли элемент фиктивно-нулевым (см выше).
5
11 августа 2010 года
hardcase
4.5K / / 09.08.2005
Немного громоздкий пример с рекурсивным вычислением длины связного списка:
Код:
public abstract class List<T> {

    public abstract T Item { get; }

    public abstract List<T> Tail { get; }
   
    public abstract bool IsEmpty { get; }

    public abstract int Length { get; }

    public List<T> Push(T item) {
        return Cons(item, this);
    }
   
    public static List<T> Cons(T item, List<T> tail) {
        return new ListNode<T>(item, tail);
    }
   
    public static readonly List<T> Nil = new EmptyNode<T>();
   
    private sealed class ListNode<T> : List<T> {

        public ListNode(T item, List<T> tail) {
            this.item = item;
            this.tail = tail;
        }

        private readonly T item;
        public override T Item { get { return item; }  }

        private readonly List<T> tail;
        public override List<T> Tail { get { return tail; } }
       
        public override IsEmpty { get { return false; } }
       
        public override int Length { get { return 1 + Tail.Length; } }
    }

    private sealed class EmptyNode<T> : List<T> {

        public override T Item { get { throw new InvalidOperationException("List is empty!"); } }

        public override List<T> Tail { get { return this; } }
       
        public override bool IsEmpty { get { return true; } }

        public override int Length { get { return 0; } }
    }
}


Это классическая реализация односвязного списка.

 
Код:
// элементы добавляются в обратном порядке
// как в стеке:
var lst = List<int>.Nil.Push(4).Push(3).Push(2).Push(1);

// другой способ сделать тоже самое, LISP-style:
var lst = List<int>.Cons(1, List<int>.Cons(2, List<int>.Cons(3, List<int>.Cons(4, List<int>.Nil))));


var lst_len = lst.Length;
5
11 августа 2010 года
hardcase
4.5K / / 09.08.2005
Цитата: patison

В упор не могу понять - каким образом оно упрощает код. Сейчас, в циклах, я просто проверяю является-ли listNode равным 0.
Может кто-нибудь прояснить для меня - каким конкретно образом эти так называемые ограничители упрощают работу со списками?


Они упрощают не столько написание кода, сколько отладку - с "нулевыми" объектами проще детектировать логические ошибки в программе - они сами рассказывают о некорректном поведении. Например, в моем примере некорректным поведением является получение элемента у пустого списка. EmptyNode.Item в этом случае сгенерирует исключение.

444
11 августа 2010 года
patison
323 / / 15.03.2007
Да, пример действительно немного громоздким получился :)
И как-то по логике мне кажется не совсем правильным наследовать ListNode от List .
Но в общих чертах понятно...
5
11 августа 2010 года
hardcase
4.5K / / 09.08.2005
Цитата: patison
Да, пример действительно немного громоздким получился :)
И как-то по логике мне кажется не совсем правильным наследовать ListNode от List .
Но в общих чертах понятно...


Это список из функциональных языков. В Nemerle например декларация значительно компактнее (в Scala тоже что-то подобное):

 
Код:
variant list[T] {
 | Cons { item : T; tail : list[T]; }
 | Nil
}

На выходе получается иерархия эквивалентная примеру.
1.8K
11 августа 2010 года
LM(AL/M)
332 / / 20.12.2005
По поводу вопроса о проверках могу добавить: от проверок фиктивности элемента, которые вас так беспокоят, можно избавиться двумя способами: заменой ветвления на полиморфизм как в примере от hardcase, либо просто специальной организацией кода: напр. для прохода по списку берём фиктивный начальный элемент и от него переходим к последующим пока не дойдем до последнего -- тут никакой проверки не нужно независимо от того пустой список или нет.
444
11 августа 2010 года
patison
323 / / 15.03.2007
Цитата:

напр. для прохода по списку берём фиктивный начальный элемент и от него переходим к последующим пока не дойдем до последнего -- тут никакой проверки не нужно независимо от того пустой список или нет.


Вот тут по-подробнее, пжлст.
Обычно, я прохожусь по списку (нецикличному) примерно след образом:

 
Код:
node* tmp = head;
while( tmp!=0 ){
     cout << tmp->data << endl;
     tmp = tmp->next;
}

Каким образом можно обойти список, не делая проверку while(tmp!=0) ?
1.8K
11 августа 2010 года
LM(AL/M)
332 / / 20.12.2005
я не это имел в виду, а то что без фиктивного элемента head м.б.=0 или надо специальные усилия прикладывать чтобы этого не допустить
444
11 августа 2010 года
patison
323 / / 15.03.2007
Ну в моём случае, в качестве "усилия" я всегда при обходе списка юзаю временный указатель, который инициализирую головой. Таким образом head у меня остаётся неизменным при проходе через список.
Я просто пока что себе до конца не могу представить как должен быть организован обход, используя замыкающие dummy nodes в списке, без использования временных указателей...

/me ушёл дальше ворошить литературу.
1.8K
11 августа 2010 года
LM(AL/M)
332 / / 20.12.2005
рассмотрим ситуацию: нужен двусвязный список с возможностью доступа в оба конца, для этого мэйнтэйним два указателя -- head & tail, один указывает на начало другой -- на конец. какие могут быть сложности? во первых слишком много вариантов значений этих указателей:
  • список пустой => head = tail = null
  • 1 элемент => head = tail <> null
  • n>1 элементов => head <> tail <> null
И при вставке/удалении в начале и в конце списка всё нужно учесть, представляете сколько и каких проверок будет?

теперь сделаем фиктивные элементы в начале и в конце, получим:
  • пустой список: head <> tail <> null, между head & tail нет элементов
  • 1 эдемент: head <> tail <> null, между head & tail 1 элемент
  • n>1 элементов: head <> tail <> null, между head & tail n элементов
444
13 августа 2010 года
patison
323 / / 15.03.2007
Вот теперь понятно. Буду пробовать реализовать у себя в приложении.
Спасибо.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог