VPF::Сортировка списка - Форум программистов

tmpvar

Дата 2.4.2011, 15:20 (ссылка)

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

Загрузка ...

Новичок

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

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

Всем привет! Помогите пожалуйста отсортировать список, сам список уже сделал, но вот теперь неполучается его отсортировать.

Код


template <class T>
class LIST_UK
    {
public:    
    T info;
  
    LIST_UK <T>  *next;
     LIST_UK <T> *list;    // Указатель на корень
    LIST_UK() { next=NULL; list = NULL; }
    };

template <class T>
class TSIKL:public LIST_UK <T>
    {
    public:
        void insert(T x)
            {
            list = ::insert(list, x);
            }

        void remove()
            {
            list=::remove(list);
            }
        void del_num(int n)
            {
            list=::del_num(list,n);
            }
         
        
          int find(T x)
            {
            if (::find(list, x)) return 1;
            else return 0;
            }

        void show()
            {
            
            ::show(list);
            }
        void sort()
        {
            ::sort(list);
  
        }
        
    };

template <class T>
LIST_UK <T> *find(LIST_UK <T> *t, T x)
    {
    int k=0;
    if(t)
        {
        LIST_UK <T> *cur=t->next;
        do
        { if(x == cur->info)k++;
        cur=cur->next;}
        while(cur!=t->next);
    
        if(k==0)return 0;
        else return t;
}
    else return 0;
    }

template <class T>
LIST_UK <T> *insert(LIST_UK <T> *list, T x)
    {
    LIST_UK <T> *p;
    p=(LIST_UK <T> *)malloc(sizeof(LIST_UK <T>));
    p->info=x;
    if(list){p->next=list->next;
    list->next=p;
    list=p;
    }
    else{list=p; list->next=p;}
    return list;

    }

template <class T>
LIST_UK <T> *remove(LIST_UK <T> *list)
    {
    LIST_UK <T>* p;
    if(list!=0)
    {
        p=list->next;
        if(p==list){list=0;}
        else 
        {
            list->next=p->next;
        delete p;
        }
        }    
        return list;

}

template <class T>
void show( LIST_UK <T> *p )
    {
    
    if (p!=0)
        {
        LIST_UK <T> *cur=p->next;
        do
        { 
            cout<<cur->info;
        cur=cur->next;}
        while(cur!=p->next);
}
    else{return;}
    }

template <class T>
LIST_UK <T> *del_num(LIST_UK <T> *list, int n)
{
  LIST_UK <T> *p=list->next, *q;
  if (n==0) return list=remove(list);
  for(int i=0; i<n; i++)
  {q=p;    p = p->next;}
  if(p==list){list=q;}
  if (p!=0)
  {q->next=p->next;
   delete p;}
  return list;
}

Сюда надо добавить функцию сортировки, но сама сортировка не получается, если важно то это циклический односвязный список.

afiskon

Дата 2.4.2011, 18:57 (ссылка)

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

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 294
Регистрация: 31.3.2011
Где: Россия, Москва

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

а) Используйте sort из STL
б) Либо почитайте про быструю сортировку в Вики

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

Записки программиста

tmpvar

Дата 3.4.2011, 10:53 (ссылка)

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

Загрузка ...

Новичок

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

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

А можно поподробнее, а то я уже замучался как это прикрутить к данному коду, везде просто реализовано всё через массив, а тут через указатели, неполучается никак smile

volatile

Дата 3.4.2011, 19:35 (ссылка)

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

Загрузка ...

Эксперт

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

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

tmpvar, я думал у вас учебный проект, поэтому вы не хотите использовать СТЛ.
Зачем вы изобретаете велосипед? почему не использовать std::list или deque ?

По поводу сортировки. Для большинства видов сортировок нужен произвольный доступ.
У вас его, похоже нет? Это значительно осложняет дело...

Это сообщение отредактировал(а) volatile - 3.4.2011, 19:40

tmpvar

Дата 4.4.2011, 03:53 (ссылка)

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

Загрузка ...

Новичок

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

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

Да, правильно понял, учебный проект, поэтому STL не хочу использовать... Насколько понял везде хранение данных массивом организовано, тогда проблем бы не возникло, но пишу девушке, а там преподаватель малость неадекватный, вот и хочет чтобы было реализовано через указатели, с радостью бы STL заюзал, но увы =((

volatile

Дата 4.4.2011, 23:14 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(tmpvar @ 4.4.2011, 03:53

)

Да, правильно понял, учебный проект

Ну тогда организуйте пузырьковую сортировку. smile

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

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