Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Добавление элемента в отсортированный массив

Страницы: < 1 2 3
AlexXn © (2004-07-29 12:13:00)
Как быстро добавить элемент в отсортированный массив(список)

Anatoly Podgoretsky (2004-07-29 13:28:00) [41]
Sandman25 © (29.07.04 12:41) [12]
Так это и есть вероятность, а вот в свящаный список сама вставка очень быстро, а если список двунапраленый или есть линейный список индексов, то и поиск можно органиховать очень быстро, методом деления по полам. Вставка в связаный список хоть в начало, хоть в середину, хоть в конец занимает одинаковое время.

TUser (2004-07-29 12:57:00) [42]
Anatoly Podgoretsky © (29.07.04 12:38) [11]
Я имел в виду связные списки.

Sandman25 (2004-07-29 12:41:00) [43]
[11] Anatoly Podgoretsky © (29.07.04 12:38)

>В массив быстро не получится, а вот в список есть вероятность.

А если у нас случайно так получилось, что вставляемый элемент должен быть самым последним? Неужели быстро все равно не получится? :)

Anatoly Podgoretsky (2004-07-29 12:38:00) [44]
Sandman25 © (29.07.04 12:29) [8]
С массивом нет никакой вероятности, все одназначно.

TUser © (29.07.04 12:33) [9]
Это тоже не одназначно, линейный список является массивом. Смотри выше про массивы. Пока не будет уточнения какой список, будет только вероятность.

Гаврила (2004-07-29 12:37:00) [45]

> про двоичный поиск - это я в курсе. Но это найти существующий
> элемент. А нужно найти место для несуществующего

Тот алгоритм, который приведен для TStringList, сделает все как надо. Смотри метод Add - он как раз вставляет элемент в нужное место в случае сортированного списка

TUser (2004-07-29 12:33:00) [46]
В список можно добавить быстро, но нельзя быстро найти место, куда вставлять. Ооочень не уверен, но м.б. в случае массива поможет Move. Правильтнее использовать представление этих данных в виде того или иного дерева, например бинарного.
См. Ахо и др., Структуры данных и алгоритмы.

Sandman25 (2004-07-29 12:29:00) [47]
[7] Anatoly Podgoretsky © (29.07.04 12:26)

С массивом тоже есть вероятность :)

Anatoly Podgoretsky (2004-07-29 12:26:00) [48]
В массив быстро не получится, а вот в список есть вероятность.

Poirot (2004-07-29 12:25:00) [49]
хы))
а если ты добавишь эл-т используя бинарное дерево, то потом при прямом или обратном обходе ты соответственно буишь получать отсортированный массивЖ)
Ну вообщем предлагаю использовать дерево в качестве массива:)))

Sandman25 (2004-07-29 12:25:00) [50]
>А нужно найти место для несуществующего

А это как раз там, где был бы найден элемент, если бы он существовал.
То есть слева элементы меньше него, справа - больше.

AlexXn (2004-07-29 12:19:00) [51]
>Sandman25
мне нужно найти именно место куда вставить. Так вот как это сделать быстро
>Гаврила
про двоичный поиск - это я в курсе. Но это найти существующий элемент. А нужно найти место для несуществующего

Sandman25 (2004-07-29 12:16:00) [52]
Кстати, быстро добавить в отсортированный список не получится.

Гаврила (2004-07-29 12:14:00) [53]
пример двоичного поиска - в TStringList, смотри исходник Classes.pas

Sandman25 (2004-07-29 12:13:00) [54]
Двоичным поиском

Страницы: < 1 2 3

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »