Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.62/13: Рейтинг темы: голосов - 13, средняя оценка - 4.62
MaximusL
2 / 2 / 0
Регистрация: 12.05.2015
Сообщений: 145
1

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

03.09.2015, 20:40. Просмотров 2381. Ответов 10
Метки нет (Все метки)

Уважаемые ! Продолжаются мое обучение, а с ним и появляются новые вопросы. Пытаюсь остортировать двусвязный список быстрой сортировка. Делаю по аналогии с пузырком и с быстрой сортировкой массива. Вот код:
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 typedef struct L {
int value;
char name[10];
struct L *next, *prev;
} ListItem;
 
static ListItem base,*current,*pos,*prev2,*next2,*current2,*current3;
static int a,b,c,k,g,num;
 
void print_pos(void);
void creation_zero(void);
void creation(void);
void scan_creation(void);
void swap_sort(void);
void quicksort(ListItem*,ListItem*,ListItem*);
void start_pointer_sort(void);
 
int main(){
creation_zero();
do{
 scan_creation();
if(pos->value==0){
    free(pos);
    break;
}
creation();
}
while(1);
print_pos();
quicksort(current,current->next,current->prev);
printf("\n\n");
print_pos();
return 0;
}
 
void print_pos(){/*Печать всего списка*/
    pos=current->prev;
while(pos!=&base){
    printf("\nname=%s                 \ttall=%d\n",pos->name,pos->value);
    pos=pos->prev;
}}
 
void creation_zero(){/*Создать нулевое звено*/
    current = &base;
    base.next = base.prev = &base;
    num=0;
    }
 
void scan_creation(){/*Выделение памяти и запись значений*/
    pos = (ListItem*)malloc(sizeof(ListItem));
    printf("\nWhat is your name? \t");
    scanf("%s",&pos->name);
    printf("\nHow tall are you? \t");
    scanf("%d",&pos->value);
    }
 
void creation(){/*Создание звена и определение его местоположения*/
    pos->next = current->next;
    pos->prev = current;
    current->next->prev = pos;
    current->next = pos;
    num++;
}
 
void quicksort(ListItem *k,ListItem *first,ListItem *last){//быстрая сортировка(указатель на структуру, на начало списка,на конец списка)
    ListItem *i=first,*j=last;
    ListItem *first1=i->prev,*last1=j->next;
    int x=(first->value+last->value)/2;
 
    do {
        while (i->value < x) i=i->next;
       while (j->value > x) j=j->prev;
 
        if(i!=j) {
                if (i->value > j->value){
            i->next->prev=j;
            i->prev->next=j;
            j->prev->next=i;
            j->next->prev=i;
            j->next=i->next;
            i->next=last1;
            i->prev=j->prev;
            j->prev=first1;
            i=j->next;
            j=i->prev;
            first1=i->prev;
            last1=j->next;
                }
        }
    } while (i!=j);
  if (last!=i)
        quicksort(k,i,last);
   if (first!=j)
       quicksort(k,first,j);
}

Если выключить рекурсию, и все условия, код с перестановкой местами ячеек работает. Подозреваю что что то не так в логических условиях. Помогите , наведите на правильную мысль! Спасибо"
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.09.2015, 20:40
Ответы с готовыми решениями:

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

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

Сортировка двусвязного списка пузырьком
Есть структура: struct stud{ char num; char tel; char name; int byear;...

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

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

10
easybudda
Модератор
Эксперт CЭксперт С++
10209 / 6108 / 1536
Регистрация: 25.07.2009
Сообщений: 11,613
03.09.2015, 23:40 2
MaximusL, есть пример быстрой сорировки односвязного списка. Посмотрите, может пригодится...
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
 
typedef struct LISTNODE {
    int key;
    struct LISTNODE * next;
} listnode_t;
 
listnode_t * listnode_new(const int value) {
    listnode_t * node = malloc(sizeof(listnode_t));
    if ( ! node )
        return NULL;
        
    node->key = value;
    node->next = NULL;
    
    return node;
}
 
void listnode_del(listnode_t * node) {
    free(node);
}
 
void listnode_swap(listnode_t * a, listnode_t * b) {
    int tmp = a->key;
    a->key = b->key;
    b->key = tmp;
}
 
void listnode_qsort(listnode_t * left, listnode_t * right) {
    if ( left == right )
        return;
    else if ( left->next == right ) {
        if ( left->key > right->key )
            listnode_swap(left, right);
    }
    else {
        listnode_t * last = left;
        listnode_t * current = left;
        
        do {
            current = current->next;
            
            if ( current->key < left->key ) {
                last = last->next;
                listnode_swap(last, current);
            }
            
        } while ( current != right );
        
        listnode_swap(left, last);
        
        listnode_qsort(left, last);
        if ( last != right )
            listnode_qsort(last->next, right);
    }
}
 
void listnode_print(listnode_t * node) {
    printf("%d ", node->key);
}
 
typedef struct LIST {
    listnode_t * head; 
    listnode_t * tail;
} list_t;
 
list_t * list_new(void) {
    list_t * list = malloc(sizeof(list_t));
    if ( ! list )
        return NULL;
    
    list->head = NULL;
    list->tail = NULL;
    
    return list;
}
 
void list_del(list_t * list) {
    while ( list->head ) {
        list->tail = list->head->next;
        listnode_del(list->head);
        list->head = list->tail;
    }
    free(list);
}
 
int list_add(list_t * list, const int value) {
    listnode_t * node = listnode_new(value);
    if ( ! node )
        return -1;
    
    if ( ! list->head )
        list->head = node;
    else
        list->tail->next = node;
    list->tail = node;
    
    return 0;
}
 
void list_print(list_t * list) {
    listnode_t * node = list->head;
    
    while ( node ) {
        listnode_print(node);
        node = node->next;
    }
    
    printf("\n");
}
 
void list_qsort(list_t * list) {
    listnode_qsort(list->head, list->tail);
}
 
/****************************************************/
 
#define VALUES_COUNT (20)
 
int main(void) {
    int i, ret;
    list_t * list = list_new();
    assert(list);
    
    srand(time(NULL));
    for ( i = 0; i < VALUES_COUNT; ++i ) {
        ret = list_add(list, rand() % 100);
        assert(ret == 0);
    }
    
    printf("Unsorted:\n");
    list_print(list);
    list_qsort(list);
    printf("Sorted:\n");
    list_print(list);
    
    list_del(list);
    
    return 0;
}
0
MaximusL
2 / 2 / 0
Регистрация: 12.05.2015
Сообщений: 145
04.09.2015, 06:25  [ТС] 3
Да я примеров кучу пересмотрел. В том что вы приводите, там перестановка происходит перезаписью значений ячейки , а мне нужно чтобы менялось расположение ячейки, т.е. переименовывались указатели.
0
easybudda
Модератор
Эксперт CЭксперт С++
10209 / 6108 / 1536
Регистрация: 25.07.2009
Сообщений: 11,613
04.09.2015, 07:29 4
MaximusL, лучше в узлах указатели хранить на данные, тогда и менять только два указателя прийдётся. В любом случае, нужно будет только функцию swap изменить. А так без разницы, односвязный список, или двусвязный. Двусвязные списки удобны, если нужна возможность удалять произвольные элементы и просматривать список в обратном порядке. Для создания, вывода и такой вот сортировки не важно, будут у узлов указатели на левых соседей, или нет.
0
MaximusL
2 / 2 / 0
Регистрация: 12.05.2015
Сообщений: 145
04.09.2015, 07:53  [ТС] 5
Вы имеете ввиду отсортировать , выставив указатели только в одну сторону? Да я думал об этом , что нужно оптимизировать код, но сейчас проблема точно не в сортировке , я отключаю все циклы и условия, часть когда где работает только перестановка , работает правильно. Вот я и бьюсь, ища ошибку)
0
zer0mail
2458 / 2094 / 217
Регистрация: 03.07.2012
Сообщений: 7,588
Записей в блоге: 1
04.09.2015, 08:33 6
Зачем биться? Используй отладочный вывод и отладчик.
0
MaximusL
2 / 2 / 0
Регистрация: 12.05.2015
Сообщений: 145
04.09.2015, 08:44  [ТС] 7
Хотелось бы понять логику , куда и при каких условия узел перекидывается.
0
zer0mail
2458 / 2094 / 217
Регистрация: 03.07.2012
Сообщений: 7,588
Записей в блоге: 1
04.09.2015, 09:07 8
Какие проблемы? Берешь листок бумаги, рисуешь объекты и связи. Добавляшь/удаляешь объект (в середину/начало/конец списка) и снова рисуешь связи. Смотришь, какие связи и как изменились (можно даже цветом выделить).
1
MaximusL
2 / 2 / 0
Регистрация: 12.05.2015
Сообщений: 145
04.09.2015, 09:20  [ТС] 9
Да это я сделал уже , еще раз говорю, часть кода которая меняет местами ячейки работает, не вижу ошибки почему не так.
0
zer0mail
2458 / 2094 / 217
Регистрация: 03.07.2012
Сообщений: 7,588
Записей в блоге: 1
04.09.2015, 10:43 10
Вижу, "некоторые сами не знают, чего хочут" (из фильма).
0
easybudda
Модератор
Эксперт CЭксперт С++
10209 / 6108 / 1536
Регистрация: 25.07.2009
Сообщений: 11,613
05.09.2015, 00:21 11

Не по теме:

"аттракцион неслыханной щедрости" (с)


llist.h
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
/* linked list with qsort function */
#ifndef LLIST_H
#define LLIST_H (1)
 
/* фнукции конструктора копирования, деструктора, 
 * обработки и сравнения для данных */
 
typedef void* (*data_copy_t)(const void*);
typedef void (*data_del_t)(void*);
typedef void (*data_proc_t)(const void*);
typedef int (*data_cmp_t)(const void*, const void*);
 
/* сам себе список */
typedef struct LLIST llist_t;
 
/* конструктор списка принимает указатели на конструктор копирования, 
 * деструктор и сравнение данных */
llist_t * llist_new(data_copy_t, data_del_t, data_cmp_t);
 
/* деструктор */
void llist_del(llist_t*);
 
/* добавление элемента в список 
 * в случае ошибки возвращает -1, при удаче 0 */
int llist_add(llist_t*, const void*);
 
/* поиск в списке данных по переданному шаблону
 * если не найдёт, возвращает 0, найдёт - не 0 */
int llist_contains(llist_t*, const void*);
 
/* удаление данных по шаблону
 * если переданные данные в списке не найдены, возвращает -1
 * иначе 0 */
int llist_remove(llist_t*, const void*);
 
/* заменяет данные, если найдёт, на новые и возвращает 0,
 * если не найдёт, возвращает -1 */
int llist_update(llist_t*, const void*, const void*);
 
/* выполнение переданной функции для каждого элемента списка
 * функция должна возвращать void и не должна изменять элементы */
void llist_foreach(llist_t*, data_proc_t);
 
/* сортировка списка по функции сравнения
 * функция должна работать так же, как передаваемая стандартной qsort() */
void llist_sort(llist_t*, data_cmp_t);
 
/* количество элементов в списке */
int llist_size(llist_t*);
 
#endif /* LLIST_H */

llist.c
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
#include <stdlib.h>
#include "llist.h"
 
typedef struct LNODE {
    void * data;
    struct LNODE * prev;
    struct LNODE * next;
} lnode_t;
 
lnode_t * lnode_new(void * data) {
    lnode_t * node = malloc(sizeof(lnode_t));
    if ( ! node )
        return NULL;
    
    node->data = data;
    node->prev = NULL;
    node->next = NULL;
    
    return node;
}
 
void lnode_del(lnode_t * node) {
    free(node);
}
 
void lnode_swap(lnode_t * a, lnode_t * b) {
    if ( a != b ) {
        void * tmp = a->data;
        a->data = b->data;
        b->data = tmp;
    }
}
 
void lnode_sort(lnode_t * left, lnode_t * right, int (*cmp)(const void*, const void*)) {
    if ( left == right )
        return;
    else if ( left->next == right ) {
        if ( cmp(left->data, right->data) > 0 )
            lnode_swap(left, right);
    }
    else {
        lnode_t * last = left;
        lnode_t * current = left;
        
        do {
            current = current->next;
            
            if ( cmp(current->data, left->data) < 0 ) {
                last = last->next;
                lnode_swap(current, last);
            }
            
        } while ( current != right );
        
        lnode_swap(last, left);
        
        lnode_sort(left, last, cmp);
        if ( last != right )
            lnode_sort(last->next, right, cmp);
    }
}
 
/******************************************************/
 
struct LLIST {
    lnode_t * head;
    lnode_t * tail;
    data_copy_t data_copy;
    data_del_t data_del;
    data_cmp_t data_cmp;
    int nodes;
};
 
llist_t * llist_new(data_copy_t data_copy, data_del_t data_del, data_cmp_t data_cmp) {
    llist_t * list = malloc(sizeof(llist_t));
    if ( ! list )
        return NULL;
        
    list->head = NULL;
    list->tail = NULL;
    list->data_copy = data_copy;
    list->data_del = data_del;
    list->data_cmp = data_cmp;
    list->nodes = 0;
    
    return list;
}
 
void llist_del(llist_t * list) {
    while ( list->head ) {
        list->tail = list->head->next;
        list->data_del(list->head->data);
        lnode_del(list->head);
        list->head = list->tail;
    }
    free(list);
}
 
int llist_add(llist_t * list, const void * data) {
    lnode_t * node = lnode_new(list->data_copy(data));
    if ( ! node )
        return -1;
        
    node->prev = list->tail;
    if ( ! list->head )
        list->head = node;
    else
        list->tail->next = node;
    list->tail = node;
    list->nodes += 1;
    
    return 0;
}
 
lnode_t * llist_find(llist_t * list, const void * data) {
    lnode_t * current = list->head;
    
    while ( current ) {
        if ( list->data_cmp(current->data, data) == 0 )
            break;
        current = current->next;
    }
    
    return current;
}
 
int llist_contains(llist_t * list, const void * data) {
    return ( llist_find(list, data) ) ? 1 : 0;
}
 
int llist_remove(llist_t * list, const void * data) {
    lnode_t * node = llist_find(list, data);
    if ( ! node )
        return -1;
        
    else {
        if ( node == list->head ) {
            list->head = list->head->next;
            if ( list->head )
                list->head->prev = NULL;
            else
                list->tail = NULL;
        }
        else if ( node == list->tail ) {
            list->tail = list->tail->prev;
            list->tail->next = NULL;
        }
        else {
            node->prev->next = node->next;
            node->next->prev = node->prev;
        }
        list->data_del(node->data);
        lnode_del(node);
        list->nodes -= 1;
    }
    
    return 0;
}
 
int llist_update(llist_t * list, const void * oldData, const void * newData) {
    lnode_t * node = llist_find(list, oldData);
    if ( ! node )
        return -1;
    
    list->data_del(node->data);
    node->data = list->data_copy(newData);
    
    return 0;
}
 
void llist_foreach(llist_t * list, data_proc_t data_proc) {
    lnode_t * current = list->head;
    
    while ( current ) {
        data_proc(current->data);
        current = current->next;
    }
}
 
void llist_sort(llist_t * list, data_cmp_t data_cmp) {
    if ( ! data_cmp )
        data_cmp = list->data_cmp;
    
    if ( ! list->nodes )
        return;
    
    lnode_sort(list->head, list->tail, data_cmp);
}
 
int llist_size(llist_t * list) {
    return list->nodes;
}

llist_test.c
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "llist.h"
 
#define NAME_LENGTH (32)
#define get_name(s) ( scanf("%31s", (s)) == 1 )
 
typedef struct DATA {
    char name[NAME_LENGTH];
    int value;
} data_t;
 
void * copy_data(const void * dataTemplate) {
    void * ptr = malloc(sizeof(data_t));
    assert(ptr);
    return memcpy(ptr, dataTemplate, sizeof(data_t));
}
 
void destroy_data(void * dataPtr) {
    free(dataPtr);
}
 
void print_data(const void * ptr) {
    data_t * pData = (data_t*)ptr;
    printf("%3d\t%s\n", pData->value, pData->name);
}
 
int compare_data(const void * pA, const void * pB) {
    data_t * a = (data_t*)pA;
    data_t * b = (data_t*)pB;
    int ret = a->value - b->value;
    
    return ( ret ) ? ret : strcmp(a->name, b->name);
}
 
void print_help(void) {
    printf("1 - help\n"
            "2 - add value\n"
            "3 - delete value\n"
            "4 - dump list\n"
            "5 - sort list\n"
            "6 - find data\n"
            "7 - change data\n"
            "8 - list size\n"
            "0 - quit\n\n"
        );
}
 
void flush_input(void) {
    char c;
    
    while ( scanf("%c", &c) == 1 && c != '\n' )
        ;
}
 
int fill_data(data_t * pData) {
    memset(pData, 0, sizeof(data_t));
    printf("Name: ");
    if ( ! get_name(pData->name) )
        return -1;
    printf("Value: ");
    if ( scanf("%d", &(pData->value)) != 1 )
        return -1;
    flush_input();
    
    return 0;
}
 
int menu(void) {
    int ret;
    
    printf("[1 - help] > ");
    if ( scanf("%d", &ret) != 1 ) {
        flush_input();
        return -1;
    }
    
    flush_input();
    return ret;
}
 
int main(void) {
    int ret, done = 0;
    llist_t * list = llist_new(copy_data, destroy_data, compare_data);
    assert(list);
    
    while ( ! done ) {
        switch ( menu() ) {
            case 1:
                print_help();
                break;
            case 2: {
                data_t data;
                ret = fill_data(&data);
                assert(ret == 0);
                ret = llist_add(list, &data);
                assert(ret == 0);
                printf("Ok\n");
                
                break;
            }
            case 3: {
                data_t data;
                ret = fill_data(&data);
                assert(ret == 0);
                ret = llist_remove(list, &data);
                if ( ret )
                    printf("Not in list!\n");
                else
                    printf("Ok\n");
                
                break;
            }
            case 4:
                llist_foreach(list, print_data);
                break;
            case 5:
                llist_sort(list, NULL);
                printf("Ok\n");
                break;
            case 6: {
                data_t data;
                ret = fill_data(&data);
                assert(ret == 0);
                printf("%sound.\n", ( llist_contains(list, &data) ) ? "F" : "Not f");
                
                break;
            }
            case 7: {
                data_t oldData, newData;
                printf("Old data\n");
                ret = fill_data(&oldData);
                assert(ret == 0);
                printf("New data\n");
                ret = fill_data(&newData);
                assert(ret == 0);
                ret = llist_update(list, &oldData, &newData);
                printf("%s\n", ( ret ) ? "Error!\n" : "Ok");
                
                break;
            }
            case 8: 
                printf("%d items in list.\n", llist_size(list));
                break;
            case 0:
                done = 1;
                break;
            default:
                printf("Wrong choice!\n");
                break;
        }
    }
    
    llist_del(list);
    
    return 0;
}
0
05.09.2015, 00:21
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.09.2015, 00:21

Быстрая сортировка и Обменная сортировка - реализация API функции
Всех приветствую! Делаю курсовой проект и появилась одна проблем-ка.... У меня...

Сортировка Шелла быстрее чем Быстрая сортировка
В универе задали задание построить графики относительно скорости сортировок и...

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


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

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

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