Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/18: Рейтинг темы: голосов - 18, средняя оценка - 5.00
6 / 6 / 1
Регистрация: 14.11.2008
Сообщений: 82
1

Индексированные списки

07.07.2009, 13:43. Просмотров 3647. Ответов 7
Метки нет (Все метки)

Разъясните кто может подробнее или может у кого есть материал по таким спискам. Знаю обычные связанные списки, но что такое индексные ток предполагаю. Написано что они повышают производительность при поиске в нем.
Подскажите как это реализовать.
Заранее СПС.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.07.2009, 13:43
Ответы с готовыми решениями:

Списки, как склеить списки между собой?
Ребят, привет всем, есть код, в классе которого описаны несколько методов: добавление элемента в...

Список женихов и невест. Обьеденить списки в списки пар.
Имеется список женихов и невест. каждая запись списка содержит пол, имя, возраст, рост, вес, а...

Индексированные поля
Здравствуйте! Хотел бы узнать, зачем делать поле ключевым и в то же время отключать его индексацию,...

Индексированные свойства
Есть структура такого вида: struct Person { public uint Id { get;...

7
Почетный модератор
7265 / 2542 / 256
Регистрация: 29.07.2006
Сообщений: 13,468
07.07.2009, 13:50 2
Сомневаюсь, что с помощью индексов ты добьешься прироста скорости поиска. Используй красно-черные или бинарные деревья.
Как реализовать понятия не имею, так как, не в курсе о каких индексах, повышающих производительность идет речь. В STL есть куча контейнеров.
0
6 / 6 / 1
Регистрация: 14.11.2008
Сообщений: 82
07.07.2009, 14:08  [ТС] 3
Тема такая была просто хотелось проработать.


Обычный способ улучшения производительности поиска заключается в создании и поддержке индексных указателей списка. Индексный указатель — это множество указателей на места размещения в списке различных ключей. Например, приложение, которое осуществляет поиск в большом списке имен, может повысить производительность, создав индексный указатель с 26 элементами, по
одному на каждую букву английского алфавита.Тогда, например, поиск последнего имени, начинающегося с 'Y' будет начинаться
с поиска в индексном указателе желательного элемента 'Y', а затем можно проводить поиск в списке, начиная с той позиции, на которую указывает соответствующий индекс.
0
Почетный модератор
7265 / 2542 / 256
Регистрация: 29.07.2006
Сообщений: 13,468
07.07.2009, 14:17 4
Хех. Тогда элементы должны быть отсортированы в списке, чтобы начинать с Y искать.
А вообще, что здесь нужно релизовывать? Берем итератор, делаем к нему advance, становимся на нужную нам позицию.
В крайнем случае, мы можем релизовать это через хэш. Значением которого будет указатель на список. Все уже сделано до нас
0
6 / 6 / 1
Регистрация: 14.11.2008
Сообщений: 82
07.07.2009, 14:21  [ТС] 5
Цитата Сообщение от Vourhey Посмотреть сообщение
А вообще, что здесь нужно релизовывать? Берем итератор, делаем к нему advance, становимся на нужную нам позицию.
Ну тогда получается что мы все равно проходим по всему списку? И список тогда будет ограничен числом указателей
0
Почетный модератор
7265 / 2542 / 256
Регистрация: 29.07.2006
Сообщений: 13,468
07.07.2009, 14:29 6
Это в каком месте мы проходим по всему списку, если мы, по сути, мользуемся только адресной арифметикой чтобы один раз изменить указатель?

Добавлено через 6 минут 12 секунд
А выше я уже написал про решение с мапами. Также оно может быть реализовано с любым контейнером с произвольным доступом. Который будет хранить в себе указатели на списки.
0
6 / 6 / 1
Регистрация: 14.11.2008
Сообщений: 82
07.07.2009, 14:50  [ТС] 7
ну тогда к примеру:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <class Y>
class List
{
    public:
    List();
 int isEmpti(void) const {return Head == NULL;}
 void   add_list(Y &, Y &);
 void del_list();
 void   print_list();
 
    private:
    Date<Y> *Head;
 
};
к этому списку добавить массив указателей Date<Y> *Ptr[100];
и потом в функциях добавления/удаления элемента инкриментировать индекс и сохранять в массиве адрес узла. Или я все же недопонимаю
0
Почетный модератор
7265 / 2542 / 256
Регистрация: 29.07.2006
Сообщений: 13,468
07.07.2009, 15:17 8
Тебе нужен просто хэш. Где индексом будет - ключ, выбранный твоей реализацией. Как ты сказал, для строк по буквам алфавита. Это свойство объекта. Значением ключа будет указатель на список всех объектов, обладающих этим свойством. Если я правильно тебя понял про индексирование. Но тебе нужно подумать, как ты будешь обрабатывать то, что я захочу индексированный список из своих объектов.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.07.2009, 15:17

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Индексированные свойства
Всем привет! Дело обстоит так: два класса имеют поля типа array of TSomething. TFirst = class...

В чем ошибка? (Индексированные свойства)
Выдается ошибка Project Project2 raised exception class EClassNotFound with message 'class TShape...

Задание. Массивы. индексированные переменные
Нужна помощь в написании программы, буду очень благодарен. Задание: Заданные действительные...

Прога на массив, индексированные переменные
Заданные действительные числа x1, x2,. . . , X25. Определить порядковый номер того из них, который...

Индексированные наборы контролов (Готовое решение)
В VB.Net нет возможности автоматически создавать индексированные наборы контролов (метки,...

Рассчитать С1, используя интервальные и индексированные переменные
Помогите , пожалуйста. Задание - рассчитать С1 , используя интервальные и индексированные...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.