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

Сортировка двусвязного списка пузырьком

06.12.2017, 03:10. Просмотров 944. Ответов 5
Метки нет (Все метки)

Есть структура:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
struct stud{
    char num[20];
    char tel[15];
    char name[20];
    int byear;
    int bday;
    int bmonth;
    int year;
    int yrs;
    int del;
    struct stud *next;
    struct stud *prev;
};
Есть нормально забитый двусвязный список.
Надо отсортировать его по году рождения (byear).
Где я неправ, что получается какой-то бред на выходе?
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for (i = 0; i < amount; i++)
                while (ptr2->next != NULL)
                {
 
                    if (ptr1->byear > ptr2->byear)
                    {
                        ptr2->prev = ptr1->prev;
                        ptr1->prev = ptr2;
                        ptr1->next = ptr2->next;
                        ptr2->next = ptr1;
                        if (ptr1->next != NULL)
                            ptr1->next->prev = ptr1;
                        if (ptr2->prev != NULL)
                            ptr2->prev->next = ptr2;
                    }
                    ptr2 = ptr2->next->next;
                        ptr2 = ptr2->next;
                        ptr1 = ptr1->next;
                    }
amount - переменная, обозначающая количество элементов. ptr1 - элемент 1, 2, 3..., ptr2 - элемент 2, 3, 4... соответственно.
Заранее спасибо за помощь.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.12.2017, 03:10
Ответы с готовыми решениями:

Сортировка двусвязного списка
Доброго дня! Помогите, пожалуйста, разобраться, что я делаю не так. Задание:...

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

Быстрая сортировка двусвязного списка
Уважаемые ! Продолжаются мое обучение, а с ним и появляются новые вопросы....

Сортировка двусвязного списка - исправить ошибку в коде
Попыталась осуществить сортировку списка, подскажите, пожалуйста, где ошибки в...

Сортировка односвязного списка (пузырьком)
нужно отсортировать информацию о поездах по номеру поезда. Сортировку нужно...

5
Michail97
93 / 40 / 23
Регистрация: 18.09.2016
Сообщений: 372
06.12.2017, 10:31 2
sevaserg, создание собственного алгоритма для сортировки двусвязного списка - это мазохизм, не иначе. Есть два хороших метода сортировки: алгоритм пузырька и алгоритм вставки.
В данном случае у вас алгоритм пузырька.
Опишите две функции:
- обмена
- самой функции пузырька.
Если ничего не будет получаться, скину модуль для сортировки пузырьком чуть позже.
0
sevaserg
0 / 0 / 1
Регистрация: 01.03.2017
Сообщений: 22
06.12.2017, 16:55  [ТС] 3
Michail97, Всё-таки я понял, что куда проще сделать программу с циклическим односвязным массивом. Но почему-то он всё равно ведёт себя дико. Выводит конкретный элемент на все, и всё:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for (i = 0; i < amount; i++)
            for (j = 0; j < amount - 1; j++)
            {
                if (ptr1->byear > ptr2->byear)
                {
                    buf = ptr1;
                    ptr1->next = ptr2->next;
                    ptr2->next = ptr1;
                    ptr3->next = ptr2->next;
                    ptr2 = ptr2->next;
                }
                else
                    ptr1 = ptr1->next;
                ptr2 = ptr2->next;
                ptr3 = ptr3->next;
            }
Где ptr2 - элемент после ptr1, а ptr3 - до.
0
Michail97
93 / 40 / 23
Регистрация: 18.09.2016
Сообщений: 372
06.12.2017, 17:39 4
Лучший ответ Сообщение было отмечено sevaserg как решение

Решение

sevaserg, лучше нарисуй список и представляй как ты будешь менять связи. Обработай вставку в середину, голову и конец. Лучше вначале на тетрадке.
0
sevaserg
0 / 0 / 1
Регистрация: 01.03.2017
Сообщений: 22
06.12.2017, 21:04  [ТС] 5
Michail97, Понял, как делать, и нашёл ошибку. Птр3 указывал на птр, плюс птр бы смещался вместе с элементом. Спасибо огромное)
Оставлю тут, мало ли кому пригодится:
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
        for (i = 0; i < amount; i++)
        {
            ptr1 = ptr2 = ptr3 = ptr;//все элементы в позиции ptr, который первый элемент.
            for (k = 0; k < amount - 1; k++)//Делаем ptr3 предпоследним.
                ptr3 = ptr3->next;
            ptr2 = ptr2->next;//ptr2 - вторым.
            for (j = 0; j < amount - 1; j++)
            {
                if (ptr1->byear > ptr2->byear)
                {
                    if (ptr == ptr1)//чтобы при свапе 1 и 2 элемента ptr указывал на новый первый
                        ptr = ptr2;
                    ptr1->next = ptr2->next;
                    ptr2->next = ptr1;
                    ptr3->next = ptr2;
                    ptr2 = ptr1->next;//перемещаем элемент, скажем, 1, на позицию 3. Птр1 менять не надо, он теперь в позиции 2.
                }
                else
                {
                    ptr1 = ptr1->next;
                    ptr2 = ptr2->next;
                }
                ptr3 = ptr3->next;//его мы двигаем в любом случае.
            }
0
Michail97
93 / 40 / 23
Регистрация: 18.09.2016
Сообщений: 372
07.12.2017, 00:36 6
sevaserg,
Если интересно, можешь этот глянуть.
Если что непонятно, пиши.
C
1
2
3
4
5
6
7
8
9
10
typedef struct ELEM_
{
    struct ELEM_ *next, *prev;
    size_t size_; 
    void *value;
}ELEM;
typedef struct
{
    ELEM *cur, *head;
}LIST;
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
static void Exchange( LIST *list )
{
    ELEM *temp = list->cur->next;
    list->cur->next = temp->next;
    temp->prev = list->cur->prev;
    if( list->cur->next )
            list->cur->next->prev = list->cur;
    if( temp->prev )
            temp->prev->next = temp;
    temp->next = list->cur;
    list->cur->prev = temp;
    if( list->cur == list->head )
            list->head = temp;
}
 
void sortBubbleList( LIST *list,  int dir, int field,  Pfun fun )
{
    if( !list->head ) return;
    int flag = 1;
    while( flag )
    {
 
        flag = 0;
        list->cur = list->head;
        while( list->cur->next)
        {
            if( fun( list->cur->value, list->cur->next->value, dir, field ) > 0)
            {
                Exchange( list );
                flag = 1;
 
            }
             else
                 list->cur = list->cur->next;
        }
    }
    list->cur = list->head;
}
Добавлено через 1 час 51 минуту
sevaserg, аа, если вам нужен односвязный, то вот
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <stdio.h>
#include <stdlib.h>
 
typedef struct ELEM_
{
    struct ELEM_ *next;
    int value;
}ELEM;
 
typedef struct
{
    ELEM *cur, *head;
}LIST;
 
typedef int (*Pfun)( const void *, const void *);
 
int cmp( const void *a, const void *b )
{
    
    return *( (int * )a ) - *( ( int * )b );
}
 
 void Exchange( LIST *list )
 {
    ELEM *prev = list->head, *temp;
 
    if( list->cur != list->head )
 
         while( prev->next != list->cur )
                        prev = prev->next;
 
 
    temp = list->cur->next;
    list->cur->next = temp->next;
 
        temp->next = list->cur;
    if( list->cur == list->head )
        list->head = temp;
    else
        prev->next = temp;
 
 
 }
void BubbleSortList( LIST *list, Pfun fun )
{
    int flag = 1;
    if( !list->head )
            return;
    while ( flag )
        {
           flag = 0;
           list->cur = list->head;
           while( list->cur->next )
               if( fun( &list->cur->value, &list->cur->next->value) > 0)
                {
 
 
                    Exchange( list );
                    flag = 1;
 
                }
                else
                    list->cur = list->cur->next;
 
           }
 
 
list->cur = list->head;
}
int Push( LIST *list, int value )
    {
        ELEM *temp = (ELEM*)malloc( sizeof(ELEM) );
        if( !temp ) return 1;
        temp->value = value;
        if( !list->head )
 
            list->head = temp;
 
        else
        {
            list->cur = list->head;
            while( list->cur->next )
                    list->cur = list->cur->next;
 
            list->cur->next = temp;
        }
 
        temp->next = NULL;
        return 0;
    }
int Pop( LIST *list )
{
    list->cur = list->head;
    list->head = list->cur->next;
    int value = list->cur->value;
    free( list->cur );
    return value;
}
int main()
{
 
    LIST head;
    head.cur = head.head = NULL;
 
    int mass[] = { 5, -1, 4, 7, 2 , 2,-12,423,12,43, 0,3,1,45,-12,-123
    };
    for( int i = 0; i < sizeof(mass)/sizeof(mass[0] ); i++ )
        Push( &head, mass[i] );
    BubbleSortList( &head, cmp );
    for( int i = 0; i < sizeof(mass)/sizeof(mass[0] ); i++ )
            printf( "%d ", Pop( &head) );
    return 0;
}
0
07.12.2017, 00:36
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.12.2017, 00:36

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

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

Сделать ввод и вывод двусвязного списка
Мне нужно сделать воод и вывод двусвязного списка. Вот что я сделал, но у меня...


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

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

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