Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.93/15: Рейтинг темы: голосов - 15, средняя оценка - 4.93
0 / 0 / 0
Регистрация: 17.07.2014
Сообщений: 12

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

02.08.2014, 17:30. Показов 3204. Ответов 14
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Нужно придумать алгоритм для добавления элемента в сортированный список(STL list<char>), то есть этот алгоритм должен сравнивать введенный элемент с уже имеющимися элементами в списке и встать в нужное место. Я думал организовать алгоритм с помощью бинарного поиска, но возникает вопрос, как определить итератор на центр списка.
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
02.08.2014, 17:30
Ответы с готовыми решениями:

Добавление элемента в сортированный список
Привет Форумчане! уже день вишу над вопросом к проекту и не могу сдвинуться дальше. в общем вот что есть: из терминала заходит набор...

Процедура добавления элемента в список по номеру
беда с указателями задание было написать список, вот код: #include &lt;iostream&gt; #include &lt;string.h&gt; using namespace...

Функция добавления элемента в кольцевой список
Здравствуйте. Возник такой вопрос. Как собственно реализовать добавление лемента в кольцевой список? В теории оно то понятно но на практике...

14
63 / 64 / 11
Регистрация: 27.02.2013
Сообщений: 1,116
02.08.2014, 17:32
вставляй в конец, а потом заново вызывай сортировку списка
0
0 / 0 / 0
Регистрация: 17.07.2014
Сообщений: 12
02.08.2014, 17:34  [ТС]
GetHelp Вариант не подходит, потому что элементов должно быть более 500к
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
02.08.2014, 17:52
Antonioni, если я предложу вам сыграть в игру - я загадываю число от 1 до 1000, вы пытаетесь его угадать, а я отвечаю только "больше", "меньше" или "равно" - какую стратегию минимизации числа ходов для выигрыша вы выберете?

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

Добавлено через 3 минуты
GetHelp Вы хотите сказать, что list.sort() единственный вариант?
0
63 / 64 / 11
Регистрация: 27.02.2013
Сообщений: 1,116
02.08.2014, 18:14
Цитата Сообщение от Antonioni Посмотреть сообщение
GetHelp Вы хотите сказать, что list.sort() единственный вариант?
не работал с этим контейнером, но предположительно да вы представляете вообще что такое список? в нем нельзя обратиться по индексу к конкретному элементу, только перебирать их... вот почитайте например про односвязный список http://learnc.info/adt/linked_list.html, двусвязный - тоже самое, только есть указатель на предыдущий элемент
0
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
02.08.2014, 18:16
Antonioni, поясни-ка особо одаренному! изначально есть пустая строка, дальше 500к раз добавляестя символ. после каждого добавлнеия ты должен поддерживать посорченную сторчку? И это все надо делать обязательно списками(я сам ими не пользовался никогда)?
0
0 / 0 / 0
Регистрация: 17.07.2014
Сообщений: 12
02.08.2014, 18:29  [ТС]
GetHelpПросто основным достоинством list является, то что добавление элемента в любую часть списка имеет постоянную сложность. Если перебирать все элементы то этот плюс теряется
SlavaSSU
500к не символов добавлять нужно, а строк. Вообще это задание на множества, нужно организовать с помощью списка множества и создать функции, выполняющие операции(объединение, разность, симметрическая разность, произведение, удаление элемента и удаление всего множества)
0
63 / 64 / 11
Регистрация: 27.02.2013
Сообщений: 1,116
02.08.2014, 18:33
Цитата Сообщение от Antonioni Посмотреть сообщение
Просто основным достоинством list является, то что добавление элемента в любую часть списка имеет постоянную сложность. Если перебирать все элементы то этот плюс теряется
я не знаю что значит постоянная сложность, но при добавлении он просто будет перебирать все элементы начиная с добавляемого и исправлять в них указатели (предварительно выделив память)
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
02.08.2014, 18:34
Лучший ответ Сообщение было отмечено Antonioni как решение

Решение

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");
}
1
0 / 0 / 0
Регистрация: 17.07.2014
Сообщений: 12
02.08.2014, 18:47  [ТС]
GetHelp Вот в этом и есть плюс, а если бы я пользовался вектором к примеру, то при добавлении элемента в середину, вектору пришлось бы переносить элементы (потому что в векторе все элементы располагаются последовательно).

Добавлено через 7 минут
Mr.X Спасибо! То что нужно!
0
63 / 64 / 11
Регистрация: 27.02.2013
Сообщений: 1,116
02.08.2014, 18:55
Цитата Сообщение от Antonioni Посмотреть сообщение
Вот в этом и есть плюс, а если бы я пользовался вектором к примеру, то при добавлении элемента в середину, вектору пришлось бы переносить элементы (потому что в векторе все элементы располагаются последовательно).
то что в списке элементы располагаются не последовательно еще не значит что можно вставлять элементы не переставляя существующии... ты так и не прочитал про организацию списков? каждый элемент списка помимо значения несет в себе указатель на предыдущий и следующий элемент, если ты будешь вставлять в список элемент тебе понадобиться перебирать все элементы и менять указатели
0
 Аватар для orange_fox
34 / 34 / 8
Регистрация: 06.04.2014
Сообщений: 189
04.08.2014, 21:33
А почему бы вместо list не использовать set или multiset? Он автоматически сортируется...
0
Эксперт PHP
4925 / 3920 / 1620
Регистрация: 24.04.2014
Сообщений: 11,441
04.08.2014, 21:36
Цитата Сообщение от orange_fox Посмотреть сообщение
А почему бы вместо list не использовать set или multiset?
потому что:
Цитата Сообщение от Antonioni Посмотреть сообщение
Вообще это задание на множества, нужно организовать с помощью списка множества и создать функции, выполняющие операции(объединение, разность, симметрическая разность, произведение, удаление элемента и удаление всего множества)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
04.08.2014, 21:36
Помогаю со студенческими работами здесь

Сортированный список
Добрый день. Буду благодарен, если поможете: &quot;Сделайте сортированный список представителем класса Monoid (операция — слияние...

Не рекурсивный метод добавления нового элемента n-ым в список
Ничего не работает. И вообще не уверен в правильности. Не понимаю, как вставлять, вместо чего. using System; namespace Лаба_2 {...

Функция добавления элемента в список внутри класса
Доброго времени суток. Зашел в &quot;творческий&quot; кризис. Задание поставлено следующим образом: Создать интерфейс IPerson и два...

Сортированный список, Срока
Ребята помогите пожалуйста с заданием по программированию.В понедельник сдавать индивидуалку.:cry: :Задание:Информационное поле...

WPF MVVM создать окно добавления элемента в список
Есть общий список элементов (в MainViewModel). На добавить в него элемент, юзая доп. окно для &quot;добавления&quot; элемента. Не могу...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Новые блоги и статьи
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов.
anaschu 08.04.2026
работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20%
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики.
Hrethgir 07.04.2026
Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .
Горе от ума
kumehtar 07.04.2026
Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .
Использование значений реквизитов справочника в документе, с определенными условиями и правами
Maks 07.04.2026
1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .
Доступность команды формы по условию
Maks 07.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .
Уведомление о неверно выбранном значении справочника
Maks 06.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .
Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt
8Observer8 05.04.2026
Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .
AkelPad-скрипты, структуры, и немного лирики..
testuser2 05.04.2026
Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru