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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.77
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
#1

сортировка перестановками - C++

26.03.2012, 19:18. Просмотров 1787. Ответов 17
Метки нет (Все метки)

нужно отсортировать линейный список перестановками
я так понимаю это тоже самое что пузырек?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.03.2012, 19:18     сортировка перестановками
Посмотрите здесь:

Сортировка перестановками - C++
Хотел написать функцию для сортировки. Компилятор ошибок не выдает.На выводе выходит это: 3 2 5 4 1 8 6 9 7 11 13 10 12 14 -858993460 ....

сортировка линейного списка перестановками - C++
я написал алгоритм который будет просто менять поля value а не перенаправлять указатели, но программа не работает правильно не могли бы вы...

Тема с перестановками - C++
Помогите пожалуйста найти где можно взять алгоритмы перестановок в двумерном массиве К примру: поменять верхнюю и нижнюю половинцы...

Перестановками заполнить главную диагональ двумерного массива наибольшими элементами - C++
Дана квадратная матрица. С помощью перестановок добиться того, чтобы её максимальный элемент находился в верхнем левом углу, следующий по...

Построить последовательность n!, для n=1…7 со всеми возможными перестановками из элементов этой последовательности - C++
Помогите с задачкой...:(Построить последовательность n!, для n=1…7. Для всех элементов этой по-следовательности и построить для них все...

Сортировка чисел выбором и простейшими перестановками - Delphi
Ребят, помогите плииз написать проги! 1. Найти элемент массива, имеющий наименьшее значение, переставить его с первым элементом, затем...

Задача с перестановками - Комбинаторика
Скільки існує перестановок з н-елементів в яких два фіксовані елементи не стоять поряд? Повторное нарушение правил, п. 1.4 - о языках...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
bunny
7 / 7 / 0
Регистрация: 18.03.2012
Сообщений: 77
26.03.2012, 19:19     сортировка перестановками #2
да это тоже самое
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
26.03.2012, 19:58  [ТС]     сортировка перестановками #3
Цитата Сообщение от bunny Посмотреть сообщение
да это тоже самое
хорошо
то есть мне нужно реализовать стандартный код как для массивов?
bunny
7 / 7 / 0
Регистрация: 18.03.2012
Сообщений: 77
26.03.2012, 21:52     сортировка перестановками #4
Цитата Сообщение от crewww Посмотреть сообщение
хорошо
то есть мне нужно реализовать стандартный код как для массивов?
Да но смотря что ты хочешь сортировать? если цифры тогда простые знаки <,> если буквы коды из аски
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,922
Записей в блоге: 1
26.03.2012, 22:15     сортировка перестановками #5
Цитата Сообщение от crewww Посмотреть сообщение
хорошо
то есть мне нужно реализовать стандартный код как для массивов?
создай функцию перестановки двух соседних элементов.
Дальше дело техники.
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
26.03.2012, 23:01  [ТС]     сортировка перестановками #6
естественно числа)
попробую написать код
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
08.04.2012, 01:42  [ТС]     сортировка перестановками #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
39
40
41
#include <iostream>
#include <fstream>
using namespace std;
struct tElem
{
    int value;
    tElem *r;
};
void create(tElem* &list,ifstream &f)
{
    tElem *temp;
    list=new tElem;
    temp=list;
    f>>temp->value;
    while (f.peek()!=EOF)
    {
        temp->r=new tElem;
        temp=temp->r;
        temp->r=NULL;
        f>>temp->value;
    }
}
void change(tElem* &a)
{ifstream f;
create(a,f);
    tElem *temp;
    a=new tElem;
        temp=a;
        a=temp->r;
        temp->r=a;
 
}
 
void bubbleSort (tElem *&list, ifstream &f)
{   create(list);
    while (list)
    {
        if (list->r->value > list->r->r-value)
        change(list);
    }
}
написал код, но он совсем нерабочий компилятор ругается практически на все
подскажите в чем я согрешил
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,922
Записей в блоге: 1
08.04.2012, 11:46     сортировка перестановками #8
наверное там, где не добавил функцию main. (или она в другом файле)?

C++
1
2
3
4
5
6
7
8
9
void change(tElem* &a)
{ifstream f;
create(a,f);
    tElem *temp;
    a=new tElem;
        temp=a;
        a=temp->r;
        temp->r=a;
}
ЛОЛ. То есть ты для перестановки двух элементов
-создаёшь заново список, причём
-создаёшь его из какого-то неинициализированного файлопотока,
-берёшь в качестве аргумента нечто tElem* &a, боюсь предположить, что это, указатель на ссылку?
-затем полностью затираешь свою ссылку "а", теряя всё
-затем в а записываешь неинициализированное поле r из только созданного объекта temp
-И затем снова присваиваешь его a , в точно таком виде, в каком ты его прочитал.

Может тебе рановато списки проходить?

Добавлено через 17 минут
и ещё: вот это
C++
1
2
3
4
5
while (list)
    {
        if (list->r->value > list->r->r-value)
        change(list);
    }
-это не сортировка пузырьком, это один проход пузырька, а надо сортировать, пока не отсортируется
Лучше так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
tElem *list_ptr;
bool run;
while (run){
   run=true;
   list_ptr=start;
   while (list_ptr->r)
    {
        if (list_ptr->value > list_ptr->r-value){
                change(list_ptr);
                run=false;
               }
    }
}
Так что перестань пихать везде create(list)!!!!!
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
08.04.2012, 12:36  [ТС]     сортировка перестановками #9
может и рановато
но меня никто не спрашивает рановато ли мне или нет, задают и я разбираюсь
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,922
Записей в блоге: 1
08.04.2012, 12:45     сортировка перестановками #10
Ой только я похоже с run=true напутал
так чуть вернее:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
tElem *list_ptr;
bool run=true;
while (run){
   run=false;
   list_ptr=start;
   while (list_ptr->r)
       {
        if (list_ptr->value > list_ptr->r-value){
                change(list_ptr);
                run=true;
                }
       }
}
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
08.04.2012, 19:00  [ТС]     сортировка перестановками #11
как сделать правильно перестановку 2-x элементов?
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
09.04.2012, 20:40  [ТС]     сортировка перестановками #12
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 tElem *c;
 tElement *t=c;
 
for (int i=0; i<n; i++)
 { c=t;
 
 while (c->r!=NULL)
 { if (c->value>c->r->value)
 { int temp=c->value;
 c->value=c->r->value;
 c->r->value=temp;
 }
 c=c->r;
 }
 }
а что если вот так реализовать сортировку?
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,922
Записей в блоге: 1
09.04.2012, 20:53     сортировка перестановками #13
твоё право, вполне рабочая вещь, - сработает.

Хотя, конечно, будь я преподавателем, я бы потребовал сделать через "перенаправление указателей".
ну то есть через изменение адресов на которые "следующий" и "предыдущий" указывают,
но это сложнее.
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
09.04.2012, 21:19  [ТС]     сортировка перестановками #14
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
твоё право, вполне рабочая вещь, - сработает.

Хотя, конечно, будь я преподавателем, я бы потребовал сделать через "перенаправление указателей".
ну то есть через изменение адресов на которые "следующий" и "предыдущий" указывают,
но это сложнее.
я то вот именно сам и хотел через перенаправление указателей сделать, про способ выше я додумался к своему стыду не сразу а только когда мне подсказали

а как можно сделать перенаправлением указателей? выше вы написали код, но там есть функция change которая у меня бредово описана, вот как ее грамотно описать?
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,922
Записей в блоге: 1
09.04.2012, 21:45     сортировка перестановками #15
Цитата Сообщение от crewww Посмотреть сообщение
я то вот именно сам и хотел через перенаправление указателей сделать, про способ выше я додумался к своему стыду не сразу а только когда мне подсказали

а как можно сделать перенаправлением указателей? выше вы написали код, но там есть функция change которая у меня бредово описана, вот как ее грамотно описать?
Во! Зацени! Хитро а? Запутаться в таком довольно просто.
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
tElem *list_ptr;
tElem *pre_ptr=NULL;
bool run;
while (run){
   run=true;
   list_ptr=start;
   while (list_ptr->r)
    {
        if (list_ptr->value > list_ptr->r-value){
               /* change(list_ptr);*/
                if (list_ptr==start){//случай если меняем первый и второй элемент особый, т.к
                                    //предыдущего элемента нет
                    start=list_ptr->next;
                    list_ptr->next=start->next;
                    start->next=list_ptr;
                }
                else{//все остальные случаи
                 pre_ptr->next=list_ptr->next;
                 list_ptr->next=list_ptr->next->next;
                 pre_ptr->next->next=list_ptr;
                }
                run=false;
               }
        pre_ptr=list_ptr;
        list_ptr=list_ptr->r;
         
    }
}
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
09.04.2012, 23:09  [ТС]     сортировка перестановками #16
круто) спасибо
а не могли бы вы что нибудь посоветовать мне что ли по спискам, а то чувствую я тяжко ой как тяжко мне будет на контрольной
Kuzia domovenok
1889 / 1744 / 117
Регистрация: 25.03.2012
Сообщений: 5,922
Записей в блоге: 1
10.04.2012, 19:24     сортировка перестановками #17
Цитата Сообщение от crewww Посмотреть сообщение
круто) спасибо
а не могли бы вы что нибудь посоветовать мне что ли по спискам, а то чувствую я тяжко ой как тяжко мне будет на контрольной
Я не уверен, что считается хорошей книгой. Я в своё время начинал с "Крупник. Изучаем Си". В инете есть. Маленькая такая книга, я считаю, что мне помогла, списки там разбирались нормально.
Но опять-таки, я не знаю, возможно есть какая-то более "классическая" литература.
(в книге описывается работа со средой borland C++ for DOS) но на консольные приложения в Visual Studio эти примеры полностью подходят.

Добавлено через 20 часов 9 минут
Сильно извиняюсь, похоже я в предыдущем посте запутался с условием выхода из цикла
Думаю так верно:
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
tElem *list_ptr;
tElem *pre_ptr=NULL;
bool run=true;
while (run){
   run=false;
   list_ptr=start;
   while (list_ptr->r)
    {
        if (list_ptr->value > list_ptr->r-value){
               /* change(list_ptr);*/
                if (list_ptr==start){//случай если меняем первый и второй элемент особый, т.к
                                    //предыдущего элемента нет
                    start=list_ptr->next;
                    list_ptr->next=start->next;
                    start->next=list_ptr;
                }
                else{//все остальные случаи
                 pre_ptr->next=list_ptr->next;
                 list_ptr->next=list_ptr->next->next;
                 pre_ptr->next->next=list_ptr;
                }
                run=true;
               }
        pre_ptr=list_ptr;
        list_ptr=list_ptr->r;
         
    }
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.04.2012, 03:05     сортировка перестановками
Еще ссылки по теме:

Операции с перестановками в массивах - VBA
Здравствуйте, помогите, пожалуйста, написать программу: Заданы два двумерных массива А(4,4) и В(3,3). Для каждого из них переставить...

Проблемы с Перестановками (Сочетаниями) - Дискретная математика
Подзабыл какую формулу использовать для условия: даны названия, допустим, 25 профессий (программист, менеджер, уборщик и тд, это не так...

подгруппа порожденная перестановками alpha и beta - Алгебра
Пусть G\subseteq {S}_{7} подгруппа порожденная перестановками \alpha=\left(1234 \right)\left(567 \right)и \beta=\left(1432 \right). Найти...

Данные String. Операции с перестановками подэлементов. - Pascal
Здравствуйте! Нужно задать два массива &quot;имя&quot; и &quot;фамилия&quot;(ввод фамилий и имен вручную) для составления списка из 5 человек. Имена в...


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

Или воспользуйтесь поиском по форуму:
crewww
30 / 1 / 1
Регистрация: 28.10.2010
Сообщений: 102
17.04.2012, 03:05  [ТС]     сортировка перестановками #18
все таки я пока решил попробовать показать вариант без перенаправления указателей, но он наотрез отказывается работать. Можете указать на ошибку?
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <fstream>
using namespace std;
 
 
struct tElem
{
 int value;
 tElem *next;
 
};
 
void create_list(tElem* &h1,ifstream &f)
{
tElem* temp;
 
h1=new tElem;
 
temp=h1;
 
f>>temp->value;
 
while(f.peek()!=EOF)
    {
        temp->next=new tElem;
        
        temp=temp->next;
        
        temp->next=NULL;
        
        f>>temp->value;
    }
 
}
 
int main()
{
 tElem *c;
 
 ifstream file("bubble.txt");
 
 create_list(c,file);
 tElem *t=c;
 
while (file.peek()!=EOF)
{
     c=t;
 
    while (c->next!=NULL)
    {
     if (c->value>c->next->value)
        {
            int temp=c->value;
 
            c->value=c->next->value;
 
            c->next->value=temp;
        }
    c=c->next;
    }
 }
t=c;
while (t)
{
    cout<<t->value<<" ";
    t=t->next;
}
file.close();
 
 return 0;
}
Yandex
Объявления
17.04.2012, 03:05     сортировка перестановками
Ответ Создать тему
Опции темы

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