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

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

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

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

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

Добавлено через 2 часа 16 минут
ап перед сном
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.11.2014, 10:15
Ответы с готовыми решениями:

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

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

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

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

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

4
Kuzia domovenok
2320 / 2069 / 480
Регистрация: 25.03.2012
Сообщений: 7,372
Записей в блоге: 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
banfollowesme
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
igorrr37
1867 / 1483 / 751
Регистрация: 21.12.2010
Сообщений: 2,473
Записей в блоге: 11
02.11.2014, 23:15 4
Сортировка односвязного списка
1
banfollowesme
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
03.11.2014, 05:04
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.11.2014, 05:04

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

Спроектировать шаблон класса spisok для реализации односвязного линейного списка. Не работает сортировка
Здравствуйте! Очень нужна помощь в реализации программы. Задание:...

Удаление элементов из односвязного списка списка
Привет всем знатокам, суровым программистам и профессионалам своего дела. Засел...


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

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

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