Форум программистов, компьютерный форум CyberForum.ru

Сортировка кастомного списка - C++

Восстановить пароль Регистрация
 
FlashLight13
0 / 0 / 0
Регистрация: 05.11.2013
Сообщений: 7
05.11.2013, 20:14     Сортировка кастомного списка #1
Приветствую. У меня возникла проблема, связанная с сортировкой своего двусвязного списка функцией qsort. Она не работает. Реализован список как класс, содержащий в себе структуру(данные + ссылка), из которых состоит список

Использую ее так:


MyList myList = MyList::MyList();
...
qsort(myList.getFirst(), myList.Count(), sizeof(myList.getFirst()), NameCMP);
, где
getFirst() возвращает указатель на первый элемент списка,
Count() возвращает количество элементов списка,
NameCMP - функция сравнения по одному из полей.

В режиме отладки посмотрел, что передается в функцию. На первой итерации туда попадает передаваемый первый элемент и какой-то мусор. А потом все совсем забивается непонятными значениями. Если что, могу скинуть весь код целиком. Прошу помощи знатоков.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.11.2013, 20:14     Сортировка кастомного списка
Посмотрите здесь:

Сортировка списка C++
C++ Сортировка списка
C++ Сортировка списка
Сортировка списка C++
Сортировка списка C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
castaway
Эксперт С++
4848 / 2987 / 368
Регистрация: 10.11.2010
Сообщений: 11,028
Записей в блоге: 10
Завершенные тесты: 1
05.11.2013, 20:19     Сортировка кастомного списка #2
Элементы твоего списка не располагаются в памяти последовательно, поэтому его нельзя отсортировать через qsort.
FlashLight13
0 / 0 / 0
Регистрация: 05.11.2013
Сообщений: 7
05.11.2013, 20:21  [ТС]     Сортировка кастомного списка #3
у меня та же мысль. Память выделяю через new. Может быть стоит попробовать через malloc?
castaway
Эксперт С++
4848 / 2987 / 368
Регистрация: 10.11.2010
Сообщений: 11,028
Записей в блоге: 10
Завершенные тесты: 1
05.11.2013, 20:23     Сортировка кастомного списка #4
Нет смысла. Покажи на всякий случай весь код. Ну или хотя бы реализацию списка.
FlashLight13
0 / 0 / 0
Регистрация: 05.11.2013
Сообщений: 7
05.11.2013, 20:28  [ТС]     Сортировка кастомного списка #5
Кликните здесь для просмотра всего текста
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
#pragma once
#include "StdAfx.h"
#include "SENSOR.h"
#include <string>
#include <iostream>
 
using namespace std;
 
void SENSOR::PushBack(char* name, int cypher)
{
    NoteObj* boof = head;
    NoteObj* newNote = new NoteObj;
    newNote->next = last;
    newNote->sensor = SENSOR::Sensor(name, cypher);
    while(boof != NULL)
    {
        boof = boof->next;
    };
    head = boof;
    boof = newNote;
}
void SENSOR::PushFoward(char* name, int cypher)
{
    NoteObj *newNote = new NoteObj;
    newNote->next = head;
    newNote->sensor = SENSOR::Sensor(name, cypher);
    if (head)
    {
        head->prev = newNote;
    }
 
    NoteObj* boof = head;
    for (int i = 0; i < SENSOR::Count() - 1; i++)
        boof = boof->next;
    last = boof;
 
    head = newNote;
}
SENSOR::Sensor SENSOR::GetByIndex(int index)
{
int count = 0;
        NoteObj* boof = head;
        while(count < index && boof != last)
        {
            boof = boof->next;
            count += 1;
        };
    return boof->sensor;
}
void SENSOR::DeleteByIndex(int index)
{
    if (index == 0)
    {
        NoteObj* boof = new NoteObj;
        boof->next = head->next;
        boof->sensor = head->sensor;
        delete head;
        head = boof->next;
        delete boof;
    }
    else 
    {
        if (index < SENSOR::Count())
        {
            int count = 0;
            NoteObj* boof1 = head;
            NoteObj* boof = head;
            while(count < index - 1)
            {
                count += 1;
                boof1 = boof1->next;
            };
            count = 0;
            while(count < index)
            {
                count += 1;
                boof = boof->next;
            };
            boof1->next = boof->next;
            delete boof;
        }
    }
}
 
int SENSOR::Count()
{
    int count = 0;
    NoteObj* boof = head;
    while(boof != NULL)
    {
        boof = boof->next;
        count += 1;
    };
    return count;
}
 
SENSOR::NoteObj* SENSOR::getFirst()
{
    return head;
}
SENSOR::NoteObj* SENSOR::getLast()
{
    return last;
}
SENSOR::SENSOR(void)
{
    head = NULL;
    last = NULL;
}
 
SENSOR::~SENSOR(void)
{
}
castaway
Эксперт С++
4848 / 2987 / 368
Регистрация: 10.11.2010
Сообщений: 11,028
Записей в блоге: 10
Завершенные тесты: 1
05.11.2013, 20:30     Сортировка кастомного списка #6
Как вариант можно реализовать итератор произвольного доступа и сортировать через std::sort.
FlashLight13
0 / 0 / 0
Регистрация: 05.11.2013
Сообщений: 7
05.11.2013, 20:32  [ТС]     Сортировка кастомного списка #7
Реализация списка:

Кликните здесь для просмотра всего текста
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
#pragma once
#include "StdAfx.h"
#include "SENSOR.h"
#include <string>
#include <iostream>
 
using namespace std;
 
void SENSOR::PushBack(char* name, int cypher)
{
    NoteObj* boof = head;
    NoteObj* newNote = new NoteObj;
    newNote->next = last;
    newNote->sensor = SENSOR::Sensor(name, cypher);
    while(boof != NULL)
    {
        boof = boof->next;
    };
    head = boof;
    boof = newNote;
}
void SENSOR::PushFoward(char* name, int cypher)
{
    NoteObj *newNote = new NoteObj;
    newNote->next = head;
    newNote->sensor = SENSOR::Sensor(name, cypher);
    if (head)
    {
        head->prev = newNote;
    }
 
    NoteObj* boof = head;
    for (int i = 0; i < SENSOR::Count() - 1; i++)
        boof = boof->next;
    last = boof;
 
    head = newNote;
}
SENSOR::Sensor SENSOR::GetByIndex(int index)
{
        int count = 0;
    NoteObj* boof = head;
    while(count < index && boof != last)
    {
        boof = boof->next;
        count += 1;
    };
    return boof->sensor;
}
/*void SENSOR::DeleteByIndex(int index)
{
    if (index == 0)
    {
        NoteObj* boof = new NoteObj;
        boof->next = head->next;
        boof->sensor = head->sensor;
        delete head;
        head = boof->next;
        delete boof;
    }
    else 
    {
        if (index < SENSOR::Count())
        {
            int count = 0;
            NoteObj* boof1 = head;
            NoteObj* boof = head;
            while(count < index - 1)
            {
                count += 1;
                boof1 = boof1->next;
            };
            count = 0;
            while(count < index)
            {
                count += 1;
                boof = boof->next;
            };
            boof1->next = boof->next;
            delete boof;
        }
    }
}*/
 
int SENSOR::Count()
{
    int count = 0;
    NoteObj* boof = head;
    while(boof != NULL)
    {
        boof = boof->next;
        count += 1;
    };
    return count;
}
 
SENSOR::NoteObj* SENSOR::getFirst()
{
    return head;
}
SENSOR::NoteObj* SENSOR::getLast()
{
    return last;
}
SENSOR::SENSOR(void)
{
    head = NULL;
    last = NULL;
}
 
SENSOR::~SENSOR(void)
{
}


переменные:
Кликните здесь для просмотра всего текста
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
public:
typedef struct Sensor
{
    Sensor(){};
    Sensor(char* InName, int InCypher)
    {
        name = InName;
        cypher = InCypher;
    }
 
    int cypher;
    char* name;
} SensorObj;
    typedef struct Note
{
    Note(){};
 
    Sensor sensor;
    Note *next;
    Note *prev;
} NoteObj;
private:
    NoteObj* head;
    NoteObj* last;


Добавлено через 50 секунд
Цитата Сообщение от castaway Посмотреть сообщение
Как вариант можно реализовать итератор произвольного доступа и сортировать через std::sort.
Я бы с радостью, но преподаватель, к сожалению, настаивает на использовании именно этой функции.
castaway
Эксперт С++
4848 / 2987 / 368
Регистрация: 10.11.2010
Сообщений: 11,028
Записей в блоге: 10
Завершенные тесты: 1
05.11.2013, 20:33     Сортировка кастомного списка #8
Цитата Сообщение от FlashLight13 Посмотреть сообщение
Я бы с радостью, но преподаватель, к сожалению, настаивает на использовании именно этой функции.
Ну тогда твой единственных выход это сделать список на подобие std::vector, где элементы хранятся последовательно.
FlashLight13
0 / 0 / 0
Регистрация: 05.11.2013
Сообщений: 7
05.11.2013, 20:37  [ТС]     Сортировка кастомного списка #9
Это я понимаю. Как это можно реализовать? Как выделять последовательно память? Мне на ум только пулы что-то приходят =(
castaway
Эксперт С++
4848 / 2987 / 368
Регистрация: 10.11.2010
Сообщений: 11,028
Записей в блоге: 10
Завершенные тесты: 1
05.11.2013, 20:39     Сортировка кастомного списка #10
Выделяешь кусок N элементов. Если при добавлении очередного элемента вся память уже закончилась, выделаешь новый кусок 2N, копируешь туда старый кусок и освобождаешь память старого.
FlashLight13
0 / 0 / 0
Регистрация: 05.11.2013
Сообщений: 7
06.11.2013, 09:35  [ТС]     Сортировка кастомного списка #11
Спасибо. Про самый банальный метод то я и позабыл.

Добавлено через 12 часов 52 минуты
Прошу прощения, но я что-то опять туплю. Как выделить такой отрезок памяти? Я пробовал calloc'ом выделять память, но результата нет. Прошу помощи.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.11.2013, 09:37     Сортировка кастомного списка
Еще ссылки по теме:

C++ Сортировка списка
"Сортировка двусвязного списка путем исключения элемента с минимальным значением и включения его в начало нового списка C++
Сортировка списка C++

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

Или воспользуйтесь поиском по форуму:
castaway
Эксперт С++
4848 / 2987 / 368
Регистрация: 10.11.2010
Сообщений: 11,028
Записей в блоге: 10
Завершенные тесты: 1
06.11.2013, 09:37     Сортировка кастомного списка #12
C++
1
Sensor *p_sensors = new Sensor [N];
Yandex
Объявления
06.11.2013, 09:37     Сортировка кастомного списка
Ответ Создать тему
Опции темы

Текущее время: 05:53. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru