VPF::Сортировка динамической структуры, рекурсия

Master_

Дата 16.3.2009, 20:45 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

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

Репутация: нет
Всего: нет

Код


struct student {
    char fam[20];
    int  year;
    char group[6];
    int  time;
    student *next;
};
typedef student* ptr;
ptr headptr;

int sort(ptr headptr)
{
    ptr p,p_pred,g;
    //string c_min[20];
    int c_min = 0;
    if ( !headptr ) return 1;//если нет

    if ( !headptr->next ) return 1;//один элемент
    g = NULL;
    p_pred = headptr;
    p = headptr->next;
    while ( p != NULL )
    {
        if ( p->year > c_min )
        {
            g = p_pred;
            c_min = p->year;
        }
        p_pred = p;
        p = p->next;
    }
    if (g)
    {
        p = g->next;
        g->next = p->next;
        p->next = headptr;
        headptr = p;
    }
    sort(headptr->next);
}

Может кто подскажет почему выводится только первый элемент? Сортировка по полю year.

mes

Дата 16.3.2009, 21:12 (ссылка)

(нет голосов)

Загрузка ...

любитель

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

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

Цитата(Master_ @ 16.3.2009, 19:45

)

Может кто подскажет почему выводится только первый элемент? Сортировка по полю year.

А чего то я не вижу чтоб в коде был вывод. Или Вы телепатические способности форумчан проверяете ? smile

Цитата(Master_ @ 16.3.2009, 19:45

)

Сортировка по полю year.

ну так бы и указали в названии сортировки, чем лишний комментарий писать smile

из того что бросилось в глаза :

Цитата(Master_ @ 16.3.2009, 19:45

)

}
sort(headptr->next);

а где return ?

Цитата(Master_ @ 16.3.2009, 19:45

)

int c_min = 0;
if ( p->year > c_min )

year у Вас объявлен как int, а значит отрицательные значения не отсортируются.

ну и напоследок :
сделайте элементарные функции необходимые для работы сортировки,
например swap для обмена местами двух элементов списка и тогда не придется разбираться в куче сваленного вместе кода. smile

конечно также было бы хорошо отсоединить список от описания структуры.
т.е так :

Код


struct Student {...};

struct StudentNode
{
  StudentNode * next;
};
struct StudentList
{
     StudentNode * head;
};

это также уменьшит головомойку при написании кода.

Это сообщение отредактировал(а) mes - 16.3.2009, 21:18

--------------------

http://opendots.net

Master_

Дата 16.3.2009, 21:17 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

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

Репутация: нет
Всего: нет

Года - все положительные.
Печать вызываю с главной функции

Код


void print(student *stud)
{
    cout << setw(20) << left << stud->fam << " " << stud->year << " " << stud->group << " " << stud->time << endl;
}

void print_list()
{
    ptr p;
    p = headptr;
    while (p!=NULL)
    {
        print(p);
        p = p->next;
    }
}
int main()
{
    setlocale( LC_ALL, "Russian" );

    read_file();
    cout << "Список: " << endl;
    print_list();

    cout << endl << "Сортировка: " << endl;
    sort(headptr);
    print_list();
    return 0;
}

mes

Дата 16.3.2009, 21:19 (ссылка)

(нет голосов)

Загрузка ...

любитель

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

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

Цитата(Master_ @ 16.3.2009, 20:17

)

Печать вызываю с главной функции

а почему грeшите на сортировку ? до сортировки у Вас список нормально выводится ?

Это сообщение отредактировал(а) mes - 16.3.2009, 21:19

--------------------

http://opendots.net

Master_

Дата 16.3.2009, 21:20 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

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

Репутация: нет
Всего: нет

До сортировки все нормально выводится.

Добавлено через 2 минуты и 48 секунд
Сделал печать перед каждым новым вызовом рекурсии (return sort)

ВОт что выводит после каждого прохождения, в консоли:

Код


Список:
Кузьмин              2000 2 13
Кузьмин              1997 2 13
Прохоров             1995 4 24
Щенок)               1994 6 13
Жадаев               1990 1 46
Алексеев             1989 8 51
Гавриков             1991 6 12
Лисков               1991 3 29

Сортировка:

Кузьмин              2000 2 13
Прохоров             1995 4 24
Щенок)               1994 6 13
Жадаев               1990 1 46
Алексеев             1989 8 51
Гавриков             1991 6 12
Лисков               1991 3 29

Кузьмин              2000 2 13
Щенок)               1994 6 13
Жадаев               1990 1 46
Алексеев             1989 8 51
Гавриков             1991 6 12
Лисков               1991 3 29

Кузьмин              2000 2 13
Жадаев               1990 1 46
Алексеев             1989 8 51
Гавриков             1991 6 12
Лисков               1991 3 29

Кузьмин              2000 2 13
Жадаев               1990 1 46
Алексеев             1989 8 51
Лисков               1991 3 29

Кузьмин              2000 2 13
Жадаев               1990 1 46
Алексеев             1989 8 51

Кузьмин              2000 2 13
Алексеев             1989 8 51

Кузьмин              2000 2 13
Кузьмин              2000 2 13

zim22

Дата 16.3.2009, 21:46 (ссылка)

(нет голосов)

Загрузка ...

depict1

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

Репутация: 24
Всего: 69

Master_, выложите функцию read_file и сам файл с которого читаешь.
p_pred - я сначала думал, что это предикат. а это предЫдущий? smile

ещё вопрос: функцию сортировки вы с головы придумали или это алгоритм какой-то?

Это сообщение отредактировал(а) zim22 - 16.3.2009, 21:51

--------------------

C++ FAQ Lite

Master_

Дата 16.3.2009, 22:00 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

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

Репутация: нет
Всего: нет

Код

Код


#include <iostream>
#include <iomanip>
#include <fstream>
//#include <conio.h>
using namespace std;
struct student {
    char fam[20];
    int  year;
    char group[6];
    int  time;
    student *next;
};
typedef student* ptr;
ptr headptr;

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

void read(student &stud)
{
    cout << "Фамилия: ";
    cin >> stud.fam;
    cout << "Год: "; 
    cin >> stud.year;
    cout << "Группа: "; 
    cin >> stud.group;
    cout << "Время: "; 
    cin >> stud.time;
}

void print(student *stud)
{
    cout << setw(20) << left << stud->fam << " " << stud->year << " " << stud->group << " " << stud->time << endl;
}

void print_list()
{
    ptr p;
    p = headptr;
    while (p!=NULL)
    {
        print(p);
        p = p->next;
    }
}
int sort(ptr headptr)
{//cout << endl;print_list();cout << endl;
    ptr p,p_pred,g;
    //string c_min[20];
    int c_min = 0;
    if ( !headptr || !headptr->next ) return 1;//если нет

    g = NULL;
    p_pred = headptr;
    p = headptr->next;
    while ( p != NULL )
    {
        if ( p->year > c_min )
        {
            g = p_pred;
            c_min = p->year;
        }
        p_pred = p;
        p = p->next;
    }
    if (g)
    {
        p = g->next;
        g->next = p->next;
        p->next = headptr;
        headptr = p;
    }
    cout << endl;print_list();
    return sort(headptr->next);
    
}

int main()
{
    setlocale( LC_ALL, "Russian" );

    read_file();
    cout << "Список: " << endl;
    print_list();

    cout << endl << "Сортировка: " << endl;
    sort(headptr);
    print_list();
    return 0;
}

Файл прикрепляю
Содержимое файла:

Код


Кузьмин             2000 2 13
Кузьмин             1997 2 13
Прохоров            1995 4 24
Щенок)              1994 6 13
Жадаев              1990 1 46
Алексеев            1989 8 51
Гавриков            1991 6 12
Лисков              1991 3 29

Это сообщение отредактировал(а) Master_ - 16.3.2009, 22:00

Присоединённый файл ( Кол-во скачиваний: 5 )

list.txt 0,24 Kb

mes

Дата 16.3.2009, 22:09 (ссылка)

(нет голосов)

Загрузка ...

любитель

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

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

Цитата(Master_ @ 16.3.2009, 20:20

)

ВОт что выводит после каждого прохождения, в консоли:

Цитата(Master_ @ 16.3.2009, 19:45

)

sort(headptr->next);

в новой ветви рекурсии при обмене с новонайденным не учитывается оставшийся в предыдущей ветви элемент.
решается путем отделения списка от самого значения (как написано во 2м посту) и обменом самих значений, а не элементов списка.

--------------------

http://opendots.net

Master_

Дата 16.3.2009, 22:40 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

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

Репутация: нет
Всего: нет

Может можно как-то сделать с существующим списком? Просто переделывать остальное не хочется..

mes

Дата 16.3.2009, 22:59 (ссылка)

(нет голосов)

Загрузка ...

любитель

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

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

Цитата(Master_ @ 16.3.2009, 21:40

)

Может можно как-то сделать с существующим списком? Просто переделывать остальное не хочется..

Переделовать делов на 5-20 минут, а чтоб добиться правильной работы придется мучаться не один час, находя все новые и новые баги smile

Так что если своего времени не жалко, не переделывайте - лично я в таком случае пас. smile

Это сообщение отредактировал(а) mes - 16.3.2009, 23:00

--------------------

http://opendots.net

Master_

Дата 16.3.2009, 23:08 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

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

Репутация: нет
Всего: нет

Можно тогда приимерчик с использованием StructNode? smile

mes

Дата 17.3.2009, 00:33 (ссылка)

(нет голосов)

Загрузка ...

любитель

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

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

Цитата(Master_ @ 16.3.2009, 22:08

)

Можно тогда приимерчик с использованием StructNode?

примерно так :

Код


struct Student {... unsigned year; ...};

struct StudentNode
{
  Student     * value;
  StudentNode * next;
};
struct StudentList
{
     StudentNode * head;
};

void sort_by_year (StudentNode * node)
{
   if (!node) return;

   StudentNode * min_node = node;
   unsigned min_year = node->value->year;
 
   for ( StudentNode *p =node->next; p; p=p->next )
     if (p->value->year<min_year) 
     {
          min_node = p;
          min_year = p->value->year; 
     }

   if (node!=min_node) std::swap (node->value, min_node->value);

   sort_by_year(node->next);
}

т.е как можно видеть по коду, список не меняет очередности элементов, а лишь происходит обмен значений (в нашем случае указателей на структуру Student)

P.S. компилить и тестировать не пробовал..но предполагаю что код рабочий.

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

--------------------

http://opendots.net

Anikmar

Дата 17.3.2009, 00:38 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

Репутация: 9
Всего: 59

Цитата(mes @ 17.3.2009, 00:33

)

if (node!=min_node) std::swap (node->value, min_node->value);

Все внутри меня протестует. А если полей там до чертиков? Надо делать двусвязный список и менять нормально элементы, целиком.

mes

Дата 17.3.2009, 00:44 (ссылка)

(нет голосов)

Загрузка ...

любитель

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

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

Цитата(Anikmar @ 16.3.2009, 23:38

)

Нельзя ли поподробней ? Kак будет влиять кол-во полей структуры Student на обмен значений двух указателей ?! smile

Насчет двусвязанногo списка : выгода при применение будет от алгоритма обхода списка , a не от возможности менять элементы smile

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

--------------------

http://opendots.net

Anikmar

Дата 17.3.2009, 00:48 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

Репутация: 9
Всего: 59

Цитата(mes @ 17.3.2009, 00:44

)

Нельзя ли поподробней ? Kак будет влиять кол-во полей структуры Student ?!

Может я недопонял алогритм - мне показалось надо поменять местами структуры: т.е. нашли искомую с наименьшим (наибольшим) годом и поставили ее на текущее место, а текущую на место той, которую нашли - затем следующая итерация.
В виду того, что мы не знаем предка текущей - мы вместо этого меняем год, оставляя остальные поля без изменений. Получится, что года отсортировали, а фамилии оставили...

Либо я просто неврубился - тогда извините.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »