Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
1 / 1 / 0
Регистрация: 25.09.2014
Сообщений: 26
1

Гайд по сортировке односвязного линейного списка

02.11.2014, 10:15. Просмотров 886. Ответов 4
Метки нет (Все метки)

Посоветуйте пожалуйста толковый гайд по сортировке. Уже столько всего перерыл, прочитал, но понять алгоритм не получается

Добавлено через 2 часа 23 минуты
Плиииииз!

Добавлено через 2 часа 16 минут
ап перед сном
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.11.2014, 10:15
Ответы с готовыми решениями:

Ошибка при сортировке односвязного списка методом пузырька
Здравствуйте, возникла проблема. Нужно отсортировать элементы структуры односвязного списка. ...

Проход по элементам односвязного линейного списка
Допустим у меня существует класс линейного односвязного списка. Надо пройти по его элементам и...

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

Сортировка односвязного линейного списка по алфавиту
Всем здравствуйте! Имеется линейный список. Помогите, пожалуйста, написать сортировку студентов...

4
3298 / 2679 / 724
Регистрация: 25.03.2012
Сообщений: 9,677
Записей в блоге: 1
02.11.2014, 10:49 2
так же как и массива, только все операции производятся на списке.
Например, цикл по всем элементам:
C++
1
for(node* i=begin; i!=NULL; i=i->next)
или, например, операция обмена двух соседних элементов.
C++
1
2
3
prev->next=second;
first->next=second->next;
second->next=first;
Добавлено через 43 секунды

Не по теме:

Цитата Сообщение от banfollowesme Посмотреть сообщение
Сегодня, 10:15
ап перед сном
с добрым утром!

1
1 / 1 / 0
Регистрация: 25.09.2014
Сообщений: 26
02.11.2014, 21:07  [ТС] 3
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
так же как и массива, только все операции производятся на списке.
Например, цикл по всем элементам:
Код C++
1
for(node* i=begin; i!=NULL; i=i->next)
или, например, операция обмена двух соседних элементов.
Код C++
1
2
3
prev->next=second;
first->next=second->next;
second->next=first;
Спасибо за ответ. Я не понимаю как регулировать поведение цикла после смены указателей на элементы. Например, есть прога( полный код ниже), которая содержит массив структур из 2х элементов структуры. Надо отсортировать их по возрастанию pnum:
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
72
73
74
#include <iostream>
using namespace std;
struct ppl{
int pnum;
char* lastname;
char* name;
int age;
char* country;
char* profession;
char* hobby;
char* tnum;
 
}base[2]={2 ,"Pelevin","Roman",23 ,"Russia","IT","Lazy","111-11-11 ",
          1,"Rozov","Viktor",23 ,"Russia","IT","Geo","111-11-12 "};
          template <class X>
struct spisok{
X a;
spisok *next;
};
void show(spisok<ppl> *start){
    spisok<ppl> *t;
    t=start;
    while(t)
    {
        cout<<t->a.pnum<<" "<<t->a.lastname<<t->a.name<<"\n"//<<t->a.age<<" "<<t->a.country<<t->a.profession<<t->a.hobby<<t->a.tnum<<'\n';
        ;t=t->next;
    }
}
void Sort(spisok<ppl> **start) {
 
    spisok<ppl> *f,*pre,*tt;
    f=*start;
    tt=f->next;
     // связанный список
cout<< "F is"<< f <<"f->next is "<< f->next;
   while (f)
    {   if(f->next!=NULL){
        if (f->a.pnum > f->next->a.pnum)
        {
            spisok<ppl> *temp=f->next;
            spisok<ppl> *temp2=f->next->next;
            f->next=f;
            f=temp;
           f->next->next=temp2;
        }
        else{
            f=f->next;
        }
    }
  f=f->next;
 }
}
}
int main(){
    spisok<struct ppl> *start,*b=NULL;
start=new spisok<ppl>;
b=start;
for (int i=0;i<2;i++){
if(i!=0){start->next=new spisok<ppl>;start=start->next;}
start->a.pnum=base[i].pnum;
start->a.lastname=base[i].lastname;
start->a.name=base[i].name;
start->a.age=base[i].age;
start->a.country=base[i].country;
start->a.profession=base[i].profession;
start->a.hobby=base[i].hobby;
start->a.tnum=base[i].tnum;
start->next=NULL;
};
show (b);
Sort(&b);
show(b);
return 0;
}
Собственно, здесь как я понимаю сортировка делает следующее :
1) пока p не возвращает false (нулл) идет проверка условия если f->next!=NULL
2)если условие выполнено, то дальше идет проверка на условие (f->a.pnum > f->next->a.pnum)
3) Если условие выполнено, указатели меняются местами. Помимо стандартной перестановки так же указатель
p->next->next,который соответствует переходу оригинального p->next к элементу next и имеет значение null теперь имеет смысл p->next для указателя с меньшей a.pnum.
Прога вылетает. Хелп плиз
0
2208 / 1717 / 859
Регистрация: 21.12.2010
Сообщений: 3,055
Записей в блоге: 11
02.11.2014, 23:15 4
Сортировка односвязного списка
1
1 / 1 / 0
Регистрация: 25.09.2014
Сообщений: 26
03.11.2014, 05:04  [ТС] 5
Спс за ответ. Не могу понять, что такое _pst. Указатель на структуру? У меня доступ к структуре осуществляется через точку, т.к. объект не указатель). Попробовал подогнать код из примера под мой, но итератор ругается на :
C++
1
 iter_swap(p1->a, p1->next->a);
Код:
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
#include <iostream>
using namespace std;
struct ppl{
int pnum;
char* lastname;
char* name;
int age;
char* country;
char* profession;
char* hobby;
char* tnum;
 
}base[2]={2 ,"Pelevin","Roman",23 ,"Russia","IT","Lazy","111-11-11 ",
          1,"Rozov","Viktor",23 ,"Russia","IT","Geo","111-11-12 "};
          template <class X>
struct spisok{
X a;
spisok *next;
};
void show(spisok<ppl> *start){
    spisok<ppl> *t;
    t=start;
    while(t)
    {
        cout<<t->a.pnum<<" "<<t->a.lastname<<t->a.name<<"\n"//<<t->a.age<<" "<<t->a.country<<t->a.profession<<t->a.hobby<<t->a.tnum<<'\n';
        ;t=t->next;
    }
}
void Sort(spisok<ppl> **p) {
 
    spisok<ppl> *p1,*p2;
    p1=*p;p2=0;
     for(p2 = *p; p2; p2 = p2->next)
    {
        for(p1 = *p; p1->next; p1 = p1->next)
        {
            if(p1->a.pnum > p1->next->a.pnum)
            {
              iter_swap(p1->a, p1->next->a);
            }
        }
    }
 
 
 
}
int main(){
    spisok<struct ppl> *start,*b=NULL;
start=new spisok<ppl>;
b=start;
for (int i=0;i<2;i++){
if(i!=0){start->next=new spisok<ppl>;start=start->next;}
start->a.pnum=base[i].pnum;
start->a.lastname=base[i].lastname;
start->a.name=base[i].name;
start->a.age=base[i].age;
start->a.country=base[i].country;
start->a.profession=base[i].profession;
start->a.hobby=base[i].hobby;
start->a.tnum=base[i].tnum;
start->next=NULL;
};
show (b);
Sort(&b);
show(b);
return 0;
}
Добавлено через 2 часа 46 минут
Замутил сортировку для 1 параметра(пока что) при помощи перестановки значений. Думаю, для всех остальных она тоже будет работать, но код получится громоздким.

Добавлено через 5 минут
Вроде замутил для всех значений, (код ниже. Он оказался еще меньше, чем для 1 значения). Если кто-нибудь объяснит на примере моей работы как это сделать с указателями, буду очень благодарен.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Sort(spisok<ppl> **p) {
 spisok<ppl> *f=*p;
  spisok<ppl> *z=*p;
 while (f)
    {   if(f->next!=NULL){
        if (f->a.pnum > f->next->a.pnum)
        {
             int  temp=f->next->a.pnum;
            f->next->a.pnum=f->a.pnum;
            f->a.pnum=temp;
           f=z;
        }
        else{
            f=f->next;
        }
    }else
  f=f->next;
 }
}
Добавлено через 6 минут
Админ, отредактируй плиз последний код в последнем сообщении на этот :
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Sort(spisok<ppl> **p) {
 spisok<ppl> *f=*p;
  spisok<ppl> *z=*p;
 while (f)
    {   if(f->next!=NULL){
        if (f->a.pnum > f->next->a.pnum)
        {
           ppl  temp=f->next->a;
            f->next->a=f->a;
            f->a=temp;
           f=z;
        }
        else{
            f=f->next;
        }
    }else
  f=f->next;
 }
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.11.2014, 05:04

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Найти наименьший элемент односвязного линейного списка
Найти наименьший элемент односвязного линейного списка. Сценарий: обходя список найти минимальное...

Удалить из односвязного линейного списка определенный узел
Построить односвязный список из входной последовательности целых чисел. Написать программу, которая...

Задать двумерный массив с помощью линейного односвязного списка
Помогите решить задачу: &quot;Задать двумерный массив с помощью линейного односвязного списка&quot;. Может...

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


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

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