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; } }
}
}
Ограничители (sentinel) в связных списках. Смысл?
Согласно литературе, использование этих ограничителей (которые представляют собой ничто иное как условно нулевой элемент списка) позволяет упростить обход списков, удаление элементов, вставку и тд
В упор не могу понять - каким образом оно упрощает код. Сейчас, в циклах, я просто проверяю является-ли listNode равным 0.
Может кто-нибудь прояснить для меня - каким конкретно образом эти так называемые ограничители упрощают работу со списками?
ха! прочитал в википедии что это такое и понял что сам этим пользовался не раз )
Ну так может поделишься опытом? )) Какой смысл этих нулевых элементов, если указатель на следующий (предыдущий, голову или хвост) элемент можно просто прировнять к нулю.
node.left.right := node;
node.right.left := node;
но node.left и/или node.right могуть быть 0, приходится делать проверку, код становится некрасивым и теряет эффективность. если же вставить парочку фиктивных элементов в начале и в конце списка, то эти ссылки никогда не станут 0
Правда при этом возникает небольшая трудность с тем чтобы фиктивные элементы не включились в обработку наравне с остальными элементами)
Если говорить про личный опыт, то мне это помогло однажды избежать трудностей с пустотой списка: чтобы не писать специфичный кусок кода для случая когда ссылка на 1-й node списка обнулилась я завёл фиктивный элемент и теперь списиок никогда не становился по настоящему пустым, код упростился
Null Object.
Его применение позволяет избежать NRE (Null Reference Exception) в сложных алгоритмах. Использование этого подхода позволяет обходиться без проверки на null указателей, что упрощает код и способствует его стабильности.
Это частный случай паттерна
Его применение позволяет избежать NRE (Null Reference Exception) в сложных алгоритмах. Использование этого подхода позволяет обходиться без проверки на null указателей, что упрощает код и способствует его стабильности.
Ну хорошо, допустим не делается проверка на то является-ли элемент нулём. Просто присваивается в этот элемент что-то и всё. А что если этот элемент у нас как раз тот самый фиктивный? Получается, что нам нужно-таки делать проверку, и в случае если элемент фиктивно-нулевой - то нам нужно создать новый фиктивный элемент. Как-то громоздно получается.
Можете показать пример кода?
hardcase: Это-то я понял. Я вот только не могу понять другого - ведь всё равно нужно будет делать проверку на то является-ли элемент фиктивно-нулевым (см выше).
Код:
Это классическая реализация односвязного списка.
Код:
// элементы добавляются в обратном порядке
// как в стеке:
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;
// как в стеке:
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;
Цитата: patison
В упор не могу понять - каким образом оно упрощает код. Сейчас, в циклах, я просто проверяю является-ли listNode равным 0.
Может кто-нибудь прояснить для меня - каким конкретно образом эти так называемые ограничители упрощают работу со списками?
Они упрощают не столько написание кода, сколько отладку - с "нулевыми" объектами проще детектировать логические ошибки в программе - они сами рассказывают о некорректном поведении. Например, в моем примере некорректным поведением является получение элемента у пустого списка. EmptyNode.Item в этом случае сгенерирует исключение.
И как-то по логике мне кажется не совсем правильным наследовать ListNode от List .
Но в общих чертах понятно...
Цитата: patison
Да, пример действительно немного громоздким получился :)
И как-то по логике мне кажется не совсем правильным наследовать ListNode от List .
Но в общих чертах понятно...
И как-то по логике мне кажется не совсем правильным наследовать ListNode от List .
Но в общих чертах понятно...
Это список из функциональных языков. В Nemerle например декларация значительно компактнее (в Scala тоже что-то подобное):
Код:
variant list[T] {
| Cons { item : T; tail : list[T]; }
| Nil
}
| Cons { item : T; tail : list[T]; }
| Nil
}
На выходе получается иерархия эквивалентная примеру.
По поводу вопроса о проверках могу добавить: от проверок фиктивности элемента, которые вас так беспокоят, можно избавиться двумя способами: заменой ветвления на полиморфизм как в примере от hardcase, либо просто специальной организацией кода: напр. для прохода по списку берём фиктивный начальный элемент и от него переходим к последующим пока не дойдем до последнего -- тут никакой проверки не нужно независимо от того пустой список или нет.
Цитата:
напр. для прохода по списку берём фиктивный начальный элемент и от него переходим к последующим пока не дойдем до последнего -- тут никакой проверки не нужно независимо от того пустой список или нет.
Вот тут по-подробнее, пжлст.
Обычно, я прохожусь по списку (нецикличному) примерно след образом:
Код:
node* tmp = head;
while( tmp!=0 ){
cout << tmp->data << endl;
tmp = tmp->next;
}
while( tmp!=0 ){
cout << tmp->data << endl;
tmp = tmp->next;
}
Каким образом можно обойти список, не делая проверку while(tmp!=0) ?
я не это имел в виду, а то что без фиктивного элемента head м.б.=0 или надо специальные усилия прикладывать чтобы этого не допустить
Я просто пока что себе до конца не могу представить как должен быть организован обход, используя замыкающие dummy nodes в списке, без использования временных указателей...
/me ушёл дальше ворошить литературу.
- список пустой => 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 элементов
Спасибо.