IMHO.WS - Структура данных: упорядоченная таблица(+)

IMHO.WS (https://www.imho.ws/index.php)

- Программирование (https://www.imho.ws/forumdisplay.php?f=40)

- - Структура данных: упорядоченная таблица(+) (https://www.imho.ws/showthread.php?t=57803)

Sheryld

04.05.2004 11:22

Структура данных: упорядоченная таблица(+)

Возникли проблемы с сабжем, подскажите что это такое и с чем его едят. Желательно дать ссылку на простенькую реализацию на c++.

Я попробовал реализовать через список:

Код:



struct TableItem

{

        int key;

        int release;

        char *info;



        TableItem *next;

};

сортировка идет по полю key, но оно может быть и одинаковым, тогда сортируется по полю release.

подскажите, это называется упорядоченной таблицей или это что-то совершенно другое?

Sheryld

06.05.2004 15:32

а может кто подскажет, как такую штуку вектором реализовать?

Drakosha

06.05.2004 16:28

Структура данных: упорядоченная таблица - ???

есть СТЛ (http://www.sgi.com/tech/stl/stl_index.html) - стандарт в c++. Там есть и веkтор, и лист, и set и т.д.....

a_ber

06.05.2004 19:36

Ты путаешь интерфейс об'екта и имплементацию... Интерфейс об'екта --- да, конечно, можно и упорядоченной таблицей назвать... а имплементция смотри выше в СТЛ, выбери по дополнотелым требованиям стуктуру и она там есть
Критерий выбора структуры: будут ли добавления/извлечения/изменения после сортировки и какого типа...

crawler

06.05.2004 22:16

мне кааатся так:

Цитата:

struct TableItem
{
int key;
int release;
char *info;
};

TableItem Table[100];

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

Sheryld

07.05.2004 15:07

хех, а мне как раз надобно не пользоваться STL, а реализовать вручную, есть только cout и cin:)

Sheryld

07.05.2004 15:08

2a_ber

интересует логическая структура данных: упорядоченная таблица, физически реализованная:списком и вектором - так правильно?:)

a_ber

20.05.2004 11:51

Извини, что долго не заметил вопроса ;(
Главное отличие списка от вектора (извини, за пересказ учебника за 2й семестр): возможность рандомального (по индексу) доступа за О(1) в векторе против возможности засунуть/убрать на любое указанное место за О(1) с сохранением порядка... Если О(1) << О(н) то это делает выбор, если речь идет о паре-тройке-даже дюжине элементов, то это критерием выбора не является... А то что является, это удовство сочленить элемент интерфейса с внутренним представлением (а тут мне кажется векторы удобнее)

Часовой пояс GMT +4, время: 00:13.