Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.94
Alexen
5 / 5 / 0
Регистрация: 14.11.2008
Сообщений: 77
#1

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

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

Разъясните кто может подробнее или может у кого есть материал по таким спискам. Знаю обычные связанные списки, но что такое индексные ток предполагаю. Написано что они повышают производительность при поиске в нем.
Подскажите как это реализовать.
Заранее СПС.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.07.2009, 13:43
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Индексированные списки (C++):

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

Списки в С++ - C++
#include<iostream.h> #include "time_1.h" #include<time.h> #include<windows.h> char* Rus (const char* text); class List { ...

Списки C++ - C++
Уважаемые! Препод задал написать линейный, линейный дважды связанный и линейный цикличный списки с любым количеством элементов для каждого....

С++ списки - C++
драствуйте помиоогите решить програму :списки Построить список согласно заданной входной последовательности чисел, показывая динамику его...

C++ списки - C++
#include "stdafx.h" #include <iostream> #include <list> using namespace std; int main(void) { list< int > l,...

Списки - C++
Всем привет!) У меня есть вопрос..как создать два списка? Просто мне нужно из списка В переместить содержимое в список А. Как это сделать и...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Vourhey
Почетный модератор
6478 / 2253 / 123
Регистрация: 29.07.2006
Сообщений: 12,635
07.07.2009, 13:50 #2
Сомневаюсь, что с помощью индексов ты добьешься прироста скорости поиска. Используй красно-черные или бинарные деревья.
Как реализовать понятия не имею, так как, не в курсе о каких индексах, повышающих производительность идет речь. В STL есть куча контейнеров.
Alexen
5 / 5 / 0
Регистрация: 14.11.2008
Сообщений: 77
07.07.2009, 14:08  [ТС] #3
Тема такая была просто хотелось проработать.


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

Добавлено через 6 минут 12 секунд
А выше я уже написал про решение с мапами. Также оно может быть реализовано с любым контейнером с произвольным доступом. Который будет хранить в себе указатели на списки.
Alexen
5 / 5 / 0
Регистрация: 14.11.2008
Сообщений: 77
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];
и потом в функциях добавления/удаления элемента инкриментировать индекс и сохранять в массиве адрес узла. Или я все же недопонимаю
Vourhey
Почетный модератор
6478 / 2253 / 123
Регистрация: 29.07.2006
Сообщений: 12,635
07.07.2009, 15:17 #8
Тебе нужен просто хэш. Где индексом будет - ключ, выбранный твоей реализацией. Как ты сказал, для строк по буквам алфавита. Это свойство объекта. Значением ключа будет указатель на список всех объектов, обладающих этим свойством. Если я правильно тебя понял про индексирование. Но тебе нужно подумать, как ты будешь обрабатывать то, что я захочу индексированный список из своих объектов.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.07.2009, 15:17
Привет! Вот еще темы с ответами:

Списки - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; using namespace std; struct list { int data; list *next; }; int...

списки - C++
написать функцию, удаляющую первый отрицательный элемент списка.

Списки - C++
Работа со списками( объединение, удаление, вставка и.т.п). при запуске выдает ошибки. :-| устала уже с ней( С++, Builder 6 ...

списки - C++
Организуйте помещение вводимых чисел в список, так чтобы получился список, упорядоченный по возрастанию помогите,пожалуйста,прошу...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
07.07.2009, 15:17
Ответ Создать тему
Опции темы

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