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

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

Войти
Регистрация
Восстановить пароль
 
WilFred
31 / 26 / 3
Регистрация: 11.03.2012
Сообщений: 71
#1

Сортировка односвязного циклического списка (Прямым включением) - C++

24.01.2014, 11:46. Просмотров 1008. Ответов 6
Метки нет (Все метки)

Привет всем
Мне требуется отсортировать односвязный циклический список, методом: прямое включение.
Суть сортировки я понимаю, массив отсортирую, но вот с односвязным списком не выходит...
Может кто знает как решить данную задачу?)
Заранее спасибо)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ilot
Модератор
Эксперт С++
1807 / 1164 / 226
Регистрация: 16.05.2013
Сообщений: 3,060
Записей в блоге: 5
Завершенные тесты: 1
24.01.2014, 12:08     Сортировка односвязного циклического списка (Прямым включением) #2
Если цикличность списка не принципиальна, что вполне допустимо:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <algorithm>
#include <iostream>
#include <functional>
#include <list>
#include <iterator>
typedef std::list<int>::iterator lst_iterator;
int main()
{
    const int N = 10;
    int array[N] = {15, 17, 9, 6, 10, 2, 5, 11, 35, 21};
    std::list<int> lst(&array[0], &array[N]);
    std::copy(lst.begin(), lst.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
    lst_iterator iter = lst.begin();
    while(++iter != lst.end()) {
        lst_iterator iter_temp = std::find_if(lst.begin(), iter, std::bind2nd(std::greater<int>(), *iter));
        if (iter_temp != iter)
            lst.splice(iter_temp, lst, iter);
    }
    std::copy(lst.begin(), lst.end(), std::ostream_iterator<int>(std::cout, " "));
    return 0;
}
WilFred
31 / 26 / 3
Регистрация: 11.03.2012
Сообщений: 71
24.01.2014, 12:13  [ТС]     Сортировка односвязного циклического списка (Прямым включением) #3
Цикличность принципиальна, в этом то вся проблема
Ilot
Модератор
Эксперт С++
1807 / 1164 / 226
Регистрация: 16.05.2013
Сообщений: 3,060
Записей в блоге: 5
Завершенные тесты: 1
24.01.2014, 12:18     Сортировка односвязного циклического списка (Прямым включением) #4
Цитата Сообщение от WilFred Посмотреть сообщение
Цикличность принципиальна, в этом то вся проблема
Да нет никакой проблемы. Граничные элементы простого списка указывают в NULL. У циклического друг на друга. Алгоритм от этого не измениться. Всего лишь нужно использовать адаптер для списка и перегрузить некоторые методы связанные с вставкой и удалением элементов, а лучше написать свой вариант цикличекского списка. Он у вас есть?
WilFred
31 / 26 / 3
Регистрация: 11.03.2012
Сообщений: 71
24.01.2014, 12:30  [ТС]     Сортировка односвязного циклического списка (Прямым включением) #5
Да, список я писал сам...
Ilot
Модератор
Эксперт С++
1807 / 1164 / 226
Регистрация: 16.05.2013
Сообщений: 3,060
Записей в блоге: 5
Завершенные тесты: 1
24.01.2014, 12:46     Сортировка односвязного циклического списка (Прямым включением) #6
Ну так в чем проблема? Либо адаптируйте алгоритм сами, либо выкладывайте свои наработки. Впрочем с этого и стоило начать...

Добавлено через 12 минут
Изучаю заголовочники. Наткнулся на вот этот код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
      /**
       *  Returns a read/write iterator that points to the first element in the
       *  %list.  Iteration is done in ordinary element order.
       */
     iterator
      begin()
      { return this->_M_impl._M_node._M_next; }
 
 
      /**
       *  Returns a read/write iterator that points one past the last
       *  element in the %list.  Iteration is done in ordinary element
       *  order.
       */
      iterator
      end() { return &this->_M_impl._M_node; }
Другими словами контейнер list циклический. Действительно если инкрементировать указтель на end то придем к первому элементу списка:
C++
1
2
3
4
5
     iter = lst.end();
    ++iter;
    std::cout << std::endl;
    std::cout << *lst.begin() << std::endl;
    std::cout << *iter << std::endl;
Результат для массива выше:
2
2

Не по теме:

Что день грядущий нам готовит узнать поможет гороскоп.

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.01.2014, 13:51     Сортировка односвязного циклического списка (Прямым включением)
Еще ссылки по теме:
Сортировка односвязного списка (2 метода) C++
Сортировка односвязного списка пузырьком C++
Не работает сортировка для односвязного списка C++
C++ Сортировка односвязного списка (нужно редактирование)
Спроектировать шаблон класса spisok для реализации односвязного линейного списка. Не работает сортировка C++

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

Или воспользуйтесь поиском по форуму:
WilFred
31 / 26 / 3
Регистрация: 11.03.2012
Сообщений: 71
24.01.2014, 13:51  [ТС]     Сортировка односвязного циклического списка (Прямым включением) #7
Список должен быть реализован свой.
Вот класс
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
class CXD
{
public:
    String numb;     // номер
    String datzak;   // дата заключения
    String datzav;   // дата завершения
    String temadog;  // тема
    String namorg;   // наименование организации
    String priznak;  // признак
    String stoimost; // стоимость в тыс руб.
    CXD* next;      // следующий элемент списка
 
    // Конструктор
    CXD(String n, String dzk, String dzv, String td,
        String no, String pr, String st, CXD* t)
    {
        numb = n;
        datzak = dzk;
        datzav = dzv;
        temadog = td;
        namorg = no;
        priznak = pr;
        stoimost = st;
        next = t;
    }
    // Конструктор
    CXD()
    {
        numb = 0;
        datzak = 0;
        datzav = 0;
        temadog = 0;
        namorg = 0;
        priznak = 0;
        stoimost = 0;
        next = NULL;
    }
};
Сортирую так(через чур мудрёно, пытаюсь как-то проще сделать):
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
XD b = x;
    for(int i=0; i<n; i++)
    {
        if(StrToInt(b->numb) >= StrToInt(b->next->numb))
        {
            int j=0;
            XD a = b->next;
            b->next = b->next->next;
            b=x;
            for(; StrToInt(a->numb) >= StrToInt(b->numb) && StrToInt(a->numb) >= StrToInt(b->next->numb); j++)
                b=b->next;
            if(j==0)
            {   for(int q=0; q<n-j-1; q++)
                    b=b->next;
                a->next = b->next;
                b->next = a;
                for(int q=0; q<=i; q++)
                    b=b->next;
                for(int q=0; q<n; q++)
                    x=x->next;
            }
            else
            {
                a->next = b->next;
                b->next = a;
                for(int q=0; q < j-2; q++)
                    b=b->next;
            }
        }
        b = b->next;
    }
n - кол-во элементов в списке, x - сам список, объявлен глобально...
P.S. не всегда сортирует правильно...
Yandex
Объявления
24.01.2014, 13:51     Сортировка односвязного циклического списка (Прямым включением)
Ответ Создать тему
Опции темы

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