Алан Перлис «Лучше иметь сто функций, работающих с одной структурой данных...»

Да не, анон все правильно сказал, а вот у вас какая-то каша в голове. То, что вы можете выдумать любой АТД и любую структуру данных ничего не меняет.

[qoute]я не программист[/qoute] Дальше не читал.

вообщет аноним путает(в отличии от r) - внешние черты(достоверно известные пользователю) - от черт реализации(о которых пользователь может предполагать если только реализатор не (тем или иным способом) гарантирует нечто)

для списка вообще необязательно иметь ссылки на соседний/соседнии элементы - это всё реализация.

для списка (пользователю) важны стоимости его операций.

для списка вообще необязательно иметь ссылки на соседний/соседнии элементы - это всё реализация.

Для списка(АТД) - необязательно. Для односвязного списка(структура данных) - обязательно(по определению).

Не знаю, что там путает анон, но у Ахо, например, тоже самое написано. Там даже по разделам видно. Есть АТД список и есть реализации - структуры данных.

++

потому-что в 10 структурах ты запутаешься быстрее, чем в одной.

Да иной раз и в трех структурах путаешься. А уж если у них есть одноименные поля…

И шо?

Я тоже не программист, однако былокожу помаленьку. И на сосфорж выкладываю.

тут полисемия «список»

односвязный_список вообще обычно стек, и если двойной хэндл(на xor или разностях , или вообще произвольной функции удовлетворяющей свойству:по двум значениям из тройки востанавливать третье ) то даже и очередь - односвязный_список это реализация

Смотри. Список - это АТД. Допустим, мы его определим как «упорядоченный набор неуникальных значений» и опишем так(псевдоязык):

atd list {
    type value_type
    type iterator_type

    fn make() -> this.type
    fn is_empty(this.type) -> bool
    fn insert(this.type, iterator_type) -> this.type
    fn head(this.type) -> value_type
    fn tail(this.type) -> this.type
}

На практике это может быть абстрактный класс в любом ОО-языке, концепт С++, trait Scala, тайпкласс haskell, структурка с указателями на функции в С и пр. и пр.

После этого мы делаем ряд реализаций - односвязный список, двусвязный список, динимический массив, да хоть на деревьях делай(если сложность операций не оговорена или соответствует).

adt там в псевдокоде.

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

После этого мы делаем ряд реализаций - односвязный список, двусвязный список, динимический массив, да хоть на деревьях делай

Почему ты считаешь что односвязный список не может быть ADT? Ты сам сказал что можно сделать иерархию ADT списков.

потому что во втором случае придется навелосипедить еще 90*10=900 функций

можно переформулировать: «лучше использовать одно надежное и проработанное решение, чем десяток кривых костылей».

поправочка- из двух соседних востанавливать соседа с любой стороны.

А для меня этот тезис самоочевиден, хоть я и не программист.

Просто по определению. Можно, конечно, придумать свои определения, но это неудобно.

Назовите свой АТД forward list, например.

Просто по определению. Можно, конечно, придумать свои определения, но это неудобно.

В каком смысле «свои»?

обычный связный список можно описать как:

adt linked_list extends list {
fn value(node) -> any
fn next(node) -> node
fn push(head) -> linked_list complexity O(1)
...
}

Если ты посмотришь - то связных списков - вагон. Linked List, Double Linked List, XOR Linked List, Unrolled Linked List, Skip List...

К стати интересная штука Unrolled Linked List - это связный список, но в то же время он не соответствует твоему определению про указатели в каждой ноде на следующий.

Бинарное дерево согласно этим же букварям - структура согласно твоему определению структура. И согласно ему же можно сказать что узел дерева содержит значение и указатели на левый правый элемент. Видел когда нибудь реализацию бинарного дерева на массивах? Тоже интересный момент неправдали? Потому что если задать дерево как data tree 'a = node a (tree a) (tree a) | leaf a - то оно совсем не то же что в реализации на массивах (это возвращаясь к твоему аргументу по поводу представления связных списков в скале, эрланге и сях).

Это в жабьих интерфейсах кажется что оно там внутри имплементации а в снаруже лист. А вот скальная либа избавляет от подообных розовых очков представляя в снуружу конкретные ADT типа Traversable, TraversableOnce и т.д. где каждая из них обладает конкретными свойствами. А HKT позволяют даже от «абстрагирования интерфейсами» абстрагироваться имея в каждом конкретном месте весьма конкретный тип.

связных списков - вагон.

Именно.

он не соответствует твоему определению про указатели в каждой ноде на следующий.

В моем определение в скобочках было сказано, какой вид имеется в виду.

Видел когда нибудь реализацию бинарного дерева на массивах? Тоже интересный момент неправдали?

Я не понимаю тебя. Бинарное дерево(как и любое другое дерево) - это абстрактный тип данных. Просто часто под этим же термином подразумевают конкретную структуру данных. Ничего тут странного нет.

Бинарное дерево(как и любое другое дерево) - это абстрактный тип данных.

Да правда? А что насчет этого говорят буквари?

Так и говорят. Но, как я и говорил, иногда так же называется конкретные структуры данных.