Модераторы: Daevaorn
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Динамические структуры данных, сортировка 
:(
    Опции темы
Metalex
Дата 9.3.2011, 10:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 635
Регистрация: 22.10.2008
Где: Украина-ZPсity

Репутация: нет
Всего: нет
Гуглил много, толком ничего работающего не нашел. У меня есть односвязный динамический список, реализованный на основе структуры. В структуре есть поле "Ключ", по которому нужно провести сортировку. Пытался сделать сам сортировку, подобную вставкам, но возникают очень существенные проблемы с указателями и т.д.
Подскажите, намекните. Спасибо.


--------------------
Don't let the system get you down.
PM WWW ICQ Skype   Вверх
borisbn
Дата 9.3.2011, 10:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135
Цитата(Metalex @  9.3.2011,  10:20 Найти цитируемый пост)
Пытался сделать сам сортировку, подобную вставкам, но возникают очень существенные проблемы с указателями и т.д.


Metalex, перечитай это, и скажи - самому понятно ? Если да, то, всё-таки, советую переформулировать, а то я раза 3 прочитал, но так и не понял.

P.S. Выложи сюда код, который не работает. Посмотрим, подправим...


--------------------
Женщины отличаются от программистов тем, что у них чары состоят из стрингов
PM MAIL Jabber   Вверх
k0rvin
Дата 9.3.2011, 12:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 442
Регистрация: 24.1.2010

Репутация: 1
Всего: 5
Вы определение списка показали бы. а так, навскидку:
Код

#include <iostream>

struct List {
    int   key;
    List* next;
};

List* makeList (int count) {
    List* list = new List();
    list->key  = 0;
    list->next = NULL;

    for (int i = 1; i < count; i++) {
        List* item = new List();
        item->key  = i;
        item->next = list;
        list = item;
    }

    return list;
}

void print (List* list) {
    while (list != NULL) {
        std::cout << list->key << " ";
        list = list->next;
    }
    std::cout << std::endl;
}

void clear (List* list) {
    List* next;

    while (list != NULL) {
        next = list->next;
        delete list;
        list = next;
    }
}

List* beforeMinItem (List* list) {
    if (list != NULL) {
        int   minKey     = list->key;
        List* minItem    = list;
        List* beforeMin  = NULL;
        List* beforeItem = NULL;

        while (list != NULL) {
            if (list->key < minKey) {
                minKey    = list->key;
                minItem   = list;
                beforeMin = beforeItem;
            }
            beforeItem = list;
            list = list->next;
        }

        return beforeMin;
    } else {
        return NULL;
    }
}

List* sort (List* list) {
    if ((list == NULL) || (list->next == NULL)) {
        return list;
    } else {
        List* beforeMin = beforeMinItem(list);
        List* min;
        List* first;
        List* last;

        if (beforeMin == NULL) {
            first = list;
            list  = list->next;
        } else {
            first = beforeMin->next;
        }
        last = first;

        while (list->next != NULL) {
            if (beforeMin == NULL) {
                last = list;
                list = list->next;
            } else {
                min = beforeMin->next;
                beforeMin->next = min->next;
                min->next  = list;
                last->next = min;
                last       = min;
                beforeMin  = beforeMinItem(list);
            }
        }

        return first;
    }
}

int main () {
    List* list = makeList(10);

    print(list);
    list = sort(list);
    print(list);

    clear(list);

    return 0;
}

правда я плюсы плохо знаю, потому тут наверняка косяки есть, но вроде работает =)

Добавлено через 3 минуты и 54 секунды
Цитата(borisbn @ 9.3.2011,  10:59)
Metalex, перечитай это, и скажи - самому понятно ? Если да, то, всё-таки, советую переформулировать, а то я раза 3 прочитал, но так и не понял.

а что тут непонятного? ТС пытался написать функцию сортировки методом вставки для самодельного односвязного списка, но запутался в указателях =)


--------------------
“Object-oriented design is the roman numerals of computing.” — Rob Pike
All software sucks
PM MAIL   Вверх
Metalex
Дата 9.3.2011, 12:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 635
Регистрация: 22.10.2008
Где: Украина-ZPсity

Репутация: нет
Всего: нет
Цитата(k0rvin @  9.3.2011,  12:37 Найти цитируемый пост)
ТС пытался написать функцию сортировки методом вставки для самодельного односвязного списка, но запутался в указателях =)

абсолютно верно  smile 

k0rvin, буду разбираться, благодарю за участие.

Добавлено через 14 минут и 51 секунду
со всеми функциями понятно, кроме сортировки smile
можно, пожалуйста, парочку комментариев?


--------------------
Don't let the system get you down.
PM WWW ICQ Skype   Вверх
Metalex
Дата 9.3.2011, 13:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 635
Регистрация: 22.10.2008
Где: Украина-ZPсity

Репутация: нет
Всего: нет
И еще одно: что это за сортировка?


--------------------
Don't let the system get you down.
PM WWW ICQ Skype   Вверх
k0rvin
Дата 9.3.2011, 13:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 442
Регистрация: 24.1.2010

Репутация: 1
Всего: 5
Цитата(Metalex @ 9.3.2011,  13:38)
И еще одно: что это за сортировка?

не знаю, писал интуитивно. посмотрел в вике, оказалось это сортировка выбором


--------------------
“Object-oriented design is the roman numerals of computing.” — Rob Pike
All software sucks
PM MAIL   Вверх
Metalex
Дата 9.3.2011, 14:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 635
Регистрация: 22.10.2008
Где: Украина-ZPсity

Репутация: нет
Всего: нет
Вроде понятно, но не до конца. В обычном случае (если минимальный элемент где-то посередине):
Код

else {
                min = beforeMin->next;
                beforeMin->next = min->next;
                min->next  = list;
                last->next = min;
                last       = min;
                beforeMin  = beforeMinItem(list);
            }


1. зачем last?
2. пояните этот участок, очень прошу.


--------------------
Don't let the system get you down.
PM WWW ICQ Skype   Вверх
k0rvin
Дата 9.3.2011, 22:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 442
Регистрация: 24.1.2010

Репутация: 1
Всего: 5
last хранит указатель на последний элемент отсортированной части, для быстрого добавления в конец отсортированной части следующего элемента. вообще это я не правильно сделал, нужно было просто вместо минимального искать максимальный и добавлять с головы, тогда бы доп.указатель не нужен был


--------------------
“Object-oriented design is the roman numerals of computing.” — Rob Pike
All software sucks
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0586 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.