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

@crewww · Регистрация: 28.10.2010

Студворк — интернет-сервис помощи студентам

нужно отсортировать линейный список перестановками
я так понимаю это тоже самое что пузырек?

@bunny · 26.03.2012, 19:19

да это тоже самое

@crewww · 26.03.2012, 19:58 **[ТС]**

Сообщение от bunny

да это тоже самое

хорошо
то есть мне нужно реализовать стандартный код как для массивов?

@bunny · 26.03.2012, 21:52

Сообщение от crewww

хорошо
то есть мне нужно реализовать стандартный код как для массивов?

Да но смотря что ты хочешь сортировать? если цифры тогда простые знаки <,> если буквы коды из аски

@Kuzia domovenok · 26.03.2012, 22:15

Сообщение от crewww

хорошо
то есть мне нужно реализовать стандартный код как для массивов?

создай функцию перестановки двух соседних элементов.
Дальше дело техники.

@crewww · 26.03.2012, 23:01 **[ТС]**

естественно числа)
попробую написать код

@crewww · 08.04.2012, 01:42 **[ТС]**

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 · 08.04.2012, 11:46

наверное там, где не добавил функцию 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 · 08.04.2012, 12:36 **[ТС]**

может и рановато
но меня никто не спрашивает рановато ли мне или нет, задают и я разбираюсь

@Kuzia domovenok · 08.04.2012, 12:45

Ой только я похоже с 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 · 08.04.2012, 19:00 **[ТС]**

как сделать правильно перестановку 2-x элементов?

@crewww · 09.04.2012, 20:40 **[ТС]**

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 · 09.04.2012, 20:53

твоё право, вполне рабочая вещь, - сработает.

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

@crewww · 09.04.2012, 21:19 **[ТС]**

Сообщение от Kuzia domovenok

твоё право, вполне рабочая вещь, - сработает.

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

я то вот именно сам и хотел через перенаправление указателей сделать, про способ выше я додумался к своему стыду не сразу а только когда мне подсказали

а как можно сделать перенаправлением указателей? выше вы написали код, но там есть функция change которая у меня бредово описана, вот как ее грамотно описать?

@Kuzia domovenok · 09.04.2012, 21:45

Сообщение от 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 · 09.04.2012, 23:09 **[ТС]**

круто) спасибо
а не могли бы вы что нибудь посоветовать мне что ли по спискам, а то чувствую я тяжко ой как тяжко мне будет на контрольной

@Kuzia domovenok · 10.04.2012, 19:24

Сообщение от 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;
         
    }
}

@crewww · 17.04.2012, 03:05 **[ТС]**

все таки я пока решил попробовать показать вариант без перенаправления указателей, но он наотрез отказывается работать. Можете указать на ошибку?

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;
}

Новые блоги и статьи Все статьи Все блоги /
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .

@crewww 30 / 1 / 1 Регистрация: 28.10.2010 Сообщений: 102

	сортировка перестановками 26.03.2012, 19:18. Показов 10808. Ответов 17 Метки нет (Все метки) нужно отсортировать линейный список перестановками я так понимаю это тоже самое что пузырек? 0

@bunny 8 / 8 / 2 Регистрация: 18.03.2012 Сообщений: 77
	26.03.2012, 19:19
	да это тоже самое 1

@crewww 30 / 1 / 1 Регистрация: 28.10.2010 Сообщений: 102
	26.03.2012, 23:01 [ТС]
	естественно числа) попробую написать код 0

@crewww 30 / 1 / 1 Регистрация: 28.10.2010 Сообщений: 102
	08.04.2012, 12:36 [ТС]
	может и рановато но меня никто не спрашивает рановато ли мне или нет, задают и я разбираюсь 0

@crewww 30 / 1 / 1 Регистрация: 28.10.2010 Сообщений: 102
	08.04.2012, 19:00 [ТС]
	как сделать правильно перестановку 2-x элементов? 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,536 Записей в блоге: 1
	09.04.2012, 20:53
	твоё право, вполне рабочая вещь, - сработает. Хотя, конечно, будь я преподавателем, я бы потребовал сделать через "перенаправление указателей". ну то есть через изменение адресов на которые "следующий" и "предыдущий" указывают, но это сложнее. 0

@crewww 30 / 1 / 1 Регистрация: 28.10.2010 Сообщений: 102
	09.04.2012, 23:09 [ТС]
	круто) спасибо а не могли бы вы что нибудь посоветовать мне что ли по спискам, а то чувствую я тяжко ой как тяжко мне будет на контрольной 0