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

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Сортировка динамической структуры, рекурсия 
V
    Опции темы
mes
Дата 17.3.2009, 00:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


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

Репутация: 144
Всего: 250
а тут есть пример базовых функций по работе со списком :
http://forum.vingrad.ru/index.php?showtopi...t&p=1812858
см. AdjList...

Добавлено через 1 минуту и 32 секунды
Цитата(Anikmar @  16.3.2009,  23:48 Найти цитируемый пост)

Может я недопонял алогритм -


Цитата(mes @  16.3.2009,  23:33 Найти цитируемый пост)
struct Student {... unsigned year; ...};
struct StudentNode
{
  Student     * value;
  StudentNode * next;
};

меняем значения указателей ..node->value.
 smile

Добавлено через 2 минуты и 54 секунды
Цитата(Anikmar @  16.3.2009,  23:48 Найти цитируемый пост)

В виду того, что мы не знаем предка текущей - мы вместо этого меняем год, оставляя остальные поля без изменений. Получится, что года отсортировали, а фамилии оставили...

Такого решения я бы не посмел предложить  smile 


--------------------
http://opendots.net
PM MAIL WWW   Вверх
Master_
Дата 17.3.2009, 01:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: нет
Всего: нет
Я тоже вначале подумал что меняет одно значение smile

Вроде понятно, но вот с head (первым) как быть, в той же функции read_file не могу додумать как изменить код..

Добавлено через 4 минуты и 37 секунд
Попробовал так, но ругается на fin'ы
Код

void read_file()
{
    //headptr=NULL;
    StudentNode *p;
    ifstream fin("list.txt");
    if (fin.is_open())
        while (!fin.eof())
        {
            if (!p)
            { 
                p = new StudentNode;
                p->next = NULL;
                //p = headptr;
            }
            else
            {
                p->next=new StudentNode;
                p = p->next;
                p->next = NULL;
            }
            fin >> p->fam >> p->year >> p->group >> p->time;
        }
    else cout << "Не удалось открыть файл" << endl;
}


Добавлено через 7 минут и 41 секунду
Вот так скомпилил, но не знаю, правильно ли пойдет:
Код

fin >> p->value->fam >> p->value->year >> p->value->group >> p->value->time;
PM   Вверх
mes
Дата 17.3.2009, 01:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


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

Репутация: 144
Всего: 250
Цитата(Master_ @  17.3.2009,  00:19 Найти цитируемый пост)
Попробовал так, но ругается на fin'ы


опять расчет на телепатов ? может поделитесь тем, что пишет Вам компилятор ?  smile 
думаю или #include забыли или std::

Цитата(Master_ @  17.3.2009,  00:19 Найти цитируемый пост)
               p->next=new StudentNode;
                p = p->next;
                p->next = NULL;

может прежде чем загружать из файла напишите функции для удобной работы со списком ?
хотя бы такие как добавить элемент и удалить его.
и ссылку Вам для примера дал же 

Цитата(mes @  16.3.2009,  23:49 Найти цитируемый пост)
http://forum.vingrad.ru/index.php?showtopi...t&p=1812858

увы :(


--------------------
http://opendots.net
PM MAIL WWW   Вверх
Anikmar
Дата 17.3.2009, 01:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

Репутация: 9
Всего: 59
Цитата(mes @  17.3.2009,  00:49 Найти цитируемый пост)
меняем значения указателей ..node->value.
 

Добавлено через 2 минуты и 54 секунды
Цитата(Anikmar @  16.3.2009,  23:48 )

В виду того, что мы не знаем предка текущей - мы вместо этого меняем год, оставляя остальные поля без изменений. Получится, что года отсортировали, а фамилии оставили...

Такого решения я бы не посмел предложить    


Виноват, не посмотрел.  smile 
PM MAIL ICQ   Вверх
inside_pointer
Дата 17.3.2009, 05:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 5
Всего: 12
Код

    if (g) {
        p = g->next;
        g->next = p->next;
        p->next = headptr;
        headptr = p;
    }


вообще непонятно в чём смысл тут

1 p = g->next; предположим g == headptr, тогда p = headptr->next;
2 g->next = p->next; это то же самое headptr->next = headptr->next->next;
3 p->next = headptr; это уже headptr->next->next = headptr;
4 headptr = p; это headptr = headptr->next;

в строках 2 и 3 наблюдается смешивание
PM MAIL   Вверх
mes
Дата 17.3.2009, 13:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


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

Репутация: 144
Всего: 250
Цитата

void sort_by_year (StudentNode * node)

сейчас обратил что я лишнюю сущность ввел (min_year), вот без нее :

Код

void sort_by_year (StudentNode * node)
{
   if (!node) return;
   StudentNode * min_node = node;
 
   for ( StudentNode *p =node->next; p; p=p->next )
     if (p->value->year < min_node->value->year) 
     {
          min_node = p;
     }
   if (node!=min_node) std::swap (node->value, min_node->value);
   sort_by_year(node->next);
}


Добавлено через 11 минут и 45 секунд
а еще лучше будет выделить функцию сравнения, тогда код будет следующим 
Код


typedef bool (*fnLess) (const Student&, const Student);

void Sort (StudentNode * node, fnLess less)
{
   if (!node) return;
   StudentNode * min_node = node;

   for ( StudentNode *p =node->next; p; p=p->next )
     if (less (*p->value, *min_node->value))
     {
          min_node = p;
     }
   if (node!=min_node) std::swap (node->value, min_node->value);
   Sort(node->next, less);
}

А вот пример использования для сортировки по годам :
Код

bool LessByYear  (const Student& s1, const Student s2)
{
    return s1.year < s2.year;
}

int main ()
{
   StudentList list;
   list.head=NULL;

// заполнение списка

   Sort (list.head, LessByYear);
...




Это сообщение отредактировал(а) mes - 17.3.2009, 13:06


--------------------
http://opendots.net
PM MAIL WWW   Вверх
Vaulter
Дата 17.3.2009, 16:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


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

Репутация: 2
Всего: 22
Цитата(mes @  17.3.2009,  14:05 Найти цитируемый пост)
а еще лучше будет выделить функцию сравнения

лучше для быстродействия или для читаемости? обычно это две взаимоисключающиеся вещи.  smile 


--------------------
PM MAIL WWW ICQ   Вверх
mes
Дата 17.3.2009, 16:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


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

Репутация: 144
Всего: 250
Цитата(Vaulter @  17.3.2009,  15:09 Найти цитируемый пост)
лучше для быстродействия или для читаемости? обычно это две взаимоисключающиеся вещи

удобнее для использования и в общем случае безопаснее. Достаточно одной функции сортировки "на все случаи жизни" и предикат под каждый конткретный случай.

По сравнению с остальными затратами этого алгоритма, лишний вызов функции заметен на скорости не будет smile





--------------------
http://opendots.net
PM MAIL WWW   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
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.2335 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


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

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