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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
FlashLight13
0 / 0 / 0
Регистрация: 05.11.2013
Сообщений: 7
#1

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

05.11.2013, 20:14. Просмотров 289. Ответов 11
Метки нет (Все метки)

Приветствую. У меня возникла проблема, связанная с сортировкой своего двусвязного списка функцией qsort. Она не работает. Реализован список как класс, содержащий в себе структуру(данные + ссылка), из которых состоит список

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


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

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

"Сортировка двусвязного списка путем исключения элемента с минимальным значением и включения его в начало нового списка - C++
Здравствуйте! Возникла проблема с программой. Тема: "Сортировка двусвязного списка путем исключения элемента с минимальным значением и...

Сортировка списка - C++
Люди помогите плиз я уже не могу!! надо сортировать список!!! Останьные недоработки тоже можете указать. Вот код Жду ответов) ...

Сортировка списка - C++
Дан список сел и расстояния до них от города. Нужно вывести села в порядке удаленности от города. Городов до 10^8. Расстояния - целые...

Сортировка списка - C++
Всем привет) Нужно реализовать сортировку списка, линейного однонаправленного. Написал, но что-то как-то не правильно... void...

Сортировка списка - C++
помогите сделать сортировку по возрасту, а то ничего не выходит #include <iostream> #include <conio.h> using namespace std; struct...

Сортировка списка - C++
Народ нужна помощь :) Элементы списка представлены следующим образом: class Node { public: char *name; Node *next; ...

11
castaway
Эксперт С++
4884 / 3019 / 370
Регистрация: 10.11.2010
Сообщений: 11,078
Записей в блоге: 10
Завершенные тесты: 1
05.11.2013, 20:19 #2
Элементы твоего списка не располагаются в памяти последовательно, поэтому его нельзя отсортировать через qsort.
0
FlashLight13
0 / 0 / 0
Регистрация: 05.11.2013
Сообщений: 7
05.11.2013, 20:21  [ТС] #3
у меня та же мысль. Память выделяю через new. Может быть стоит попробовать через malloc?
0
castaway
Эксперт С++
4884 / 3019 / 370
Регистрация: 10.11.2010
Сообщений: 11,078
Записей в блоге: 10
Завершенные тесты: 1
05.11.2013, 20:23 #4
Нет смысла. Покажи на всякий случай весь код. Ну или хотя бы реализацию списка.
0
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)
{
}
0
castaway
Эксперт С++
4884 / 3019 / 370
Регистрация: 10.11.2010
Сообщений: 11,078
Записей в блоге: 10
Завершенные тесты: 1
05.11.2013, 20:30 #6
Как вариант можно реализовать итератор произвольного доступа и сортировать через std::sort.
0
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.
Я бы с радостью, но преподаватель, к сожалению, настаивает на использовании именно этой функции.
0
castaway
Эксперт С++
4884 / 3019 / 370
Регистрация: 10.11.2010
Сообщений: 11,078
Записей в блоге: 10
Завершенные тесты: 1
05.11.2013, 20:33 #8
Цитата Сообщение от FlashLight13 Посмотреть сообщение
Я бы с радостью, но преподаватель, к сожалению, настаивает на использовании именно этой функции.
Ну тогда твой единственных выход это сделать список на подобие std::vector, где элементы хранятся последовательно.
0
FlashLight13
0 / 0 / 0
Регистрация: 05.11.2013
Сообщений: 7
05.11.2013, 20:37  [ТС] #9
Это я понимаю. Как это можно реализовать? Как выделять последовательно память? Мне на ум только пулы что-то приходят =(
0
castaway
Эксперт С++
4884 / 3019 / 370
Регистрация: 10.11.2010
Сообщений: 11,078
Записей в блоге: 10
Завершенные тесты: 1
05.11.2013, 20:39 #10
Выделяешь кусок N элементов. Если при добавлении очередного элемента вся память уже закончилась, выделаешь новый кусок 2N, копируешь туда старый кусок и освобождаешь память старого.
1
FlashLight13
0 / 0 / 0
Регистрация: 05.11.2013
Сообщений: 7
06.11.2013, 09:35  [ТС] #11
Спасибо. Про самый банальный метод то я и позабыл.

Добавлено через 12 часов 52 минуты
Прошу прощения, но я что-то опять туплю. Как выделить такой отрезок памяти? Я пробовал calloc'ом выделять память, но результата нет. Прошу помощи.
0
castaway
Эксперт С++
4884 / 3019 / 370
Регистрация: 10.11.2010
Сообщений: 11,078
Записей в блоге: 10
Завершенные тесты: 1
06.11.2013, 09:37 #12
C++
1
Sensor *p_sensors = new Sensor [N];
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.11.2013, 09:37
Привет! Вот еще темы с ответами:

Сортировка списка - C++
Здравствуйте!!! Прошу помочь мне написать алгоритм сортировки односвязного списка. Задание такое: необходимо из элементов трёх списков...

Сортировка списка - C++
Получается, что пользователь вносит книги в библиотеку, записывая имя писателя, название, год издания и тд... После чего он может...

Сортировка списка - C++
Всем привет задание такое Разработать программу работы со связным списком сеансов в кинотеатре. Для каждого сеанса должна храниться...

Сортировка списка - C++
Привет, всем.. Ребята помогите у подруги зачет по программированию ей надо решить задачку.. Информационное поле элемента...


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

Или воспользуйтесь поиском по форуму:
12
Yandex
Объявления
06.11.2013, 09:37
Ответ Создать тему
Опции темы

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