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

Алгоритм добавления элемента в сортированный список - C++

Восстановить пароль Регистрация
 
Antonioni
0 / 0 / 0
Регистрация: 17.07.2014
Сообщений: 12
02.08.2014, 17:30     Алгоритм добавления элемента в сортированный список #1
Нужно придумать алгоритм для добавления элемента в сортированный список(STL list<char>), то есть этот алгоритм должен сравнивать введенный элемент с уже имеющимися элементами в списке и встать в нужное место. Я думал организовать алгоритм с помощью бинарного поиска, но возникает вопрос, как определить итератор на центр списка.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.08.2014, 17:30     Алгоритм добавления элемента в сортированный список
Посмотрите здесь:

класс список, функция добавления элемента в конец C++
C++ Реализовать приложение, содержащее функции добавления нового элемента в массив и удаления элемента из массива. (Имитируется “резиновый” массив)
Списки: разработать функцию добавления элемента C++
Добавления элемента в бинарное дерево C++
C++ Возможность добавления элемента к базе данных
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
GetHelp
-8 / 60 / 6
Регистрация: 27.02.2013
Сообщений: 1,112
02.08.2014, 17:32     Алгоритм добавления элемента в сортированный список #2
вставляй в конец, а потом заново вызывай сортировку списка
Antonioni
0 / 0 / 0
Регистрация: 17.07.2014
Сообщений: 12
02.08.2014, 17:34  [ТС]     Алгоритм добавления элемента в сортированный список #3
GetHelp Вариант не подходит, потому что элементов должно быть более 500к
_Ivana
2185 / 1390 / 124
Регистрация: 01.03.2013
Сообщений: 4,139
Записей в блоге: 2
02.08.2014, 17:52     Алгоритм добавления элемента в сортированный список #4
Antonioni, если я предложу вам сыграть в игру - я загадываю число от 1 до 1000, вы пытаетесь его угадать, а я отвечаю только "больше", "меньше" или "равно" - какую стратегию минимизации числа ходов для выигрыша вы выберете?

UPD сорри, теперь я отвечаю не читая темы....
GetHelp
-8 / 60 / 6
Регистрация: 27.02.2013
Сообщений: 1,112
02.08.2014, 17:53     Алгоритм добавления элемента в сортированный список #5
Antonioni, ну тебе так или иначе придется перебирать поэлементно, это же список...
Antonioni
0 / 0 / 0
Регистрация: 17.07.2014
Сообщений: 12
02.08.2014, 18:11  [ТС]     Алгоритм добавления элемента в сортированный список #6
_Ivana Стратегию "Разделяй и властвуй" я хотел бы реализовать, но как вы предлагаете итератор на центр определить, ведь операции "+" и "-" для итераторов списка не определены.

Добавлено через 3 минуты
GetHelp Вы хотите сказать, что list.sort() единственный вариант?
GetHelp
-8 / 60 / 6
Регистрация: 27.02.2013
Сообщений: 1,112
02.08.2014, 18:14     Алгоритм добавления элемента в сортированный список #7
Цитата Сообщение от Antonioni Посмотреть сообщение
GetHelp Вы хотите сказать, что list.sort() единственный вариант?
не работал с этим контейнером, но предположительно да вы представляете вообще что такое список? в нем нельзя обратиться по индексу к конкретному элементу, только перебирать их... вот почитайте например про односвязный список http://learnc.info/adt/linked_list.html, двусвязный - тоже самое, только есть указатель на предыдущий элемент
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
02.08.2014, 18:16     Алгоритм добавления элемента в сортированный список #8
Antonioni, поясни-ка особо одаренному! изначально есть пустая строка, дальше 500к раз добавляестя символ. после каждого добавлнеия ты должен поддерживать посорченную сторчку? И это все надо делать обязательно списками(я сам ими не пользовался никогда)?
Antonioni
0 / 0 / 0
Регистрация: 17.07.2014
Сообщений: 12
02.08.2014, 18:29  [ТС]     Алгоритм добавления элемента в сортированный список #9
GetHelpПросто основным достоинством list является, то что добавление элемента в любую часть списка имеет постоянную сложность. Если перебирать все элементы то этот плюс теряется
SlavaSSU
500к не символов добавлять нужно, а строк. Вообще это задание на множества, нужно организовать с помощью списка множества и создать функции, выполняющие операции(объединение, разность, симметрическая разность, произведение, удаление элемента и удаление всего множества)
GetHelp
-8 / 60 / 6
Регистрация: 27.02.2013
Сообщений: 1,112
02.08.2014, 18:33     Алгоритм добавления элемента в сортированный список #10
Цитата Сообщение от Antonioni Посмотреть сообщение
Просто основным достоинством list является, то что добавление элемента в любую часть списка имеет постоянную сложность. Если перебирать все элементы то этот плюс теряется
я не знаю что значит постоянная сложность, но при добавлении он просто будет перебирать все элементы начиная с добавляемого и исправлять в них указатели (предварительно выделив память)
Mr.X
Эксперт С++
 Аватар для Mr.X
2802 / 1578 / 247
Регистрация: 03.05.2010
Сообщений: 3,666
02.08.2014, 18:34     Алгоритм добавления элемента в сортированный список #11
Сообщение было отмечено автором темы, экспертом или модератором как ответ
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/////////////////////////////////////////////////////////////////////////////////////////
//Нужно придумать алгоритм для добавления элемента в сортированный список(STL list<char>), 
//то есть этот алгоритм должен сравнивать введенный элемент с уже имеющимися элементами 
//в списке и встать в нужное место.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string         T_str;
typedef std::list<char>     T_char_list;
/////////////////////////////////////////////////////////////////////////////////////////
template< typename  TT_cont >
void    print_cont( TT_cont     const   &   cont )
{
    std::copy
        (
            cont.begin                                  (),
            cont.end                                    (),
            std::ostream_iterator<TT_cont::value_type>  ( std::cout )
        );
 
    std::cout   <<  std::endl;
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    const   T_str   s   =   "abcdefghiklmnop";
    T_char_list     char_list
                        (
                            s.begin     (),
                            s.end       ()
                        );
 
    print_cont( char_list );
 
    char    const   SYMB_FOR_INSERT     =   'j';
 
    auto    it  =   std::lower_bound
                        (
                            char_list.begin     (),
                            char_list.end       (),
                            SYMB_FOR_INSERT
                        );
 
    char_list.insert
        (
            it,
            SYMB_FOR_INSERT
        );
 
    print_cont( char_list );
 
    system("pause");
}
Antonioni
0 / 0 / 0
Регистрация: 17.07.2014
Сообщений: 12
02.08.2014, 18:47  [ТС]     Алгоритм добавления элемента в сортированный список #12
GetHelp Вот в этом и есть плюс, а если бы я пользовался вектором к примеру, то при добавлении элемента в середину, вектору пришлось бы переносить элементы (потому что в векторе все элементы располагаются последовательно).

Добавлено через 7 минут
Mr.X Спасибо! То что нужно!
GetHelp
-8 / 60 / 6
Регистрация: 27.02.2013
Сообщений: 1,112
02.08.2014, 18:55     Алгоритм добавления элемента в сортированный список #13
Цитата Сообщение от Antonioni Посмотреть сообщение
Вот в этом и есть плюс, а если бы я пользовался вектором к примеру, то при добавлении элемента в середину, вектору пришлось бы переносить элементы (потому что в векторе все элементы располагаются последовательно).
то что в списке элементы располагаются не последовательно еще не значит что можно вставлять элементы не переставляя существующии... ты так и не прочитал про организацию списков? каждый элемент списка помимо значения несет в себе указатель на предыдущий и следующий элемент, если ты будешь вставлять в список элемент тебе понадобиться перебирать все элементы и менять указатели
orange_fox
 Аватар для orange_fox
34 / 34 / 6
Регистрация: 06.04.2014
Сообщений: 189
04.08.2014, 21:33     Алгоритм добавления элемента в сортированный список #14
А почему бы вместо list не использовать set или multiset? Он автоматически сортируется...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.08.2014, 21:36     Алгоритм добавления элемента в сортированный список
Еще ссылки по теме:

C++ Процедура добавления элемента в список по номеру
C++ Ошибка добавления в односвязный список
C++ Функция добавления элемента в кольцевой список

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

Или воспользуйтесь поиском по форуму:
Jewbacabra
1791 / 1506 / 540
Регистрация: 24.04.2014
Сообщений: 4,231
04.08.2014, 21:36     Алгоритм добавления элемента в сортированный список #15
Цитата Сообщение от orange_fox Посмотреть сообщение
А почему бы вместо list не использовать set или multiset?
потому что:
Цитата Сообщение от Antonioni Посмотреть сообщение
Вообще это задание на множества, нужно организовать с помощью списка множества и создать функции, выполняющие операции(объединение, разность, симметрическая разность, произведение, удаление элемента и удаление всего множества)
Yandex
Объявления
04.08.2014, 21:36     Алгоритм добавления элемента в сортированный список
Ответ Создать тему
Опции темы

Текущее время: 03:57. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru