|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Belyakov 2:5020/400 23 Sep 2002 21:14:24
To : Oleg Shatalov
Subject : Re: [Q] Быстpый поиск в отсоpтиpованном спис ке
--------------------------------------------------------------------------------
Ох, Холм, вы как всегда ничего не знанеете за пределами сыска...
Для списка определен ряд допустимых операций:
- получить первый элемент
- получить следующий элемент
- удалить текущий элемент
- добавить элемент
Для двунаправленого списка дополнительно
- получить последний элемент
- получить предыдущий элемент.
Понятие _индекса_ для списка просто не определено.
Андрей.
> > Создали и добавили 1, 2, 3 Удалили 2. Создали и добавили 4... и т.д.
> > Отсортировали результат - требуется назвать _индекс_ бывшего третьего...
>
> Ватсон, это же элементарно! (с)
>
> 1) Создали список.
> 2) Занесли 1,2,3 на позиции 1,2,3.
> 3) Удалили 2 с позиции 2. Получили список из двух элементов 1,3. При этом
> элемент 3 сдвигается на одну позицию и занимает место элемента 2.
> 4) Добавили 4 на позицию 3. Получили список 1,3,4.
> 5) Добавили 10 на позицию 4. Получили список 1,3,4,10.
> 6) Добавили 2 на позицию 2. При этом элементы 3,4,10 сдвигаются на одно
> позицию и получается список 1,2,3,4,10.
>
> Hичего сортировать не надо, список и так отсортирован.
> Поиск позиции, куда вставить новый элемент, производится все тем же
> двоичным поиском.
>
> При этом памяти нужно в три раза меньше чем для хранения двоичного дерева
> (4 байта на индекс вместо 12 байт (индекс ветви и два указателя на левую и
>
> правую дочерние ветви)).
>
> Единственный минус, как я уже говорил выше, это сдвиг массива при вставке
> внутрь или при удалении элемента внутри массива.
>
> Пока,
> Олег.
--
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Talk.Mail.Ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
