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

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Сортировка лин. списка прямыми вставками??? 
:(
    Опции темы
diman_bulgar
  Дата 12.1.2006, 17:23 (ссылка) | (голосов: 0) Загрузка ... Загрузка ... Быстрая цитата Цитата


Unregistered
Есть список елементов (int) надо их отсортировать методом пузырька и методом прямых вставок . Как заносить в список елементы и как выводить я понял . Как отсортировать методом "пузырька" тоже (спасибо threef -у) . Теперь вопрос как организовать сортировку вставками и сравнить с "пузырьком" . Таймером ?
Вот код методом "пузырька"(все работает):
Код



#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>
struct item
{
 int element;
 item *next;
};

item *list; 
item *p; 

void Add(int element)
{
 p->next=(item*)malloc(sizeof(item));
 p=p->next;
 p->element=element;
 p->next=NULL;
}

item* Search(int element)
{
 item *i,*result=NULL;
 char found=0;

 i=list->next;
 while (i!=NULL && found==0)
 {
   if (i->element==element)
   {
     found=1;
     result=i;
   }
   i=i->next;
 }

 return result;
}

void printlist(void)
{
 item *p;

 p=list->next;
 while (p!=NULL)
 {
   printf("%d ",p->element);
   p=p->next;
 }
}

void swapitem(item*&a,item*&b)
{
    item c;
    c.element=b->element;
    b->element=a->element;
    a->element=c.element;
}
void bublesortlist(void)
{
   item *p,*q,*end=NULL;
   q=list->next;
   while( q->next!=end)
   {
       for(p=q;p->next!=end;p=p->next)
       {
           if(p->element>p->next->element)
           {
               swapitem(p,p->next);
           }
       }
       end=p;
   }
}

void main(void)
{
 list=(item*)malloc(sizeof(item));
 list->element=0;
 list->next=NULL;
 p=list;
 cout <<"Kolichestvo elementov v spiske: ";
  int p; 
  cin >> p;
  for (int i = 1; i <= p; i++)
  {
      cout <<i<<"-i: "; 
      int s;
      cin >> s;
      Add(s);
  }
 cout<<" - ishodnij spisok.";
 printlist();
 cout<<endl<<" - sortirovannij spisok.";
 bublesortlist();
 printlist();
 cout<<endl;
 free(list);
}


Это , я так понял , метод вставок (че то здесь не так smile ):
Код

void insertsortlist(void)                      
{
item *q ;                                  
item *pp, * pr;                    
item *tmp = NULL;                                    
while (p !=NULL)                        
     {                           
     q = p; p = p->next;                                       
     for (pp = tmp, pr=NULL; pp!=NULL && pp->element < q->element; pr=pp, pp=pp->next);
     q->next = pp;
     if (pr==NULL) 
        tmp=q; 
    else
       pr->next=q;
     }
     tmp=p;                                     
}


И как их сравнить ?
  Вверх
_hunter
Дата 12.1.2006, 18:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

Репутация: 16
Всего: 98
в смысле "как сравнить"
пишеш две функции сортировки
береш два одинаковых массива ( а лучше читаеш из файла -- масиивы д.б. большими )
передаеш их в функции, замеряв перед вызовом те же тики ( GetTickCount() ) береш тики после вызова, вычитаеш.
сравниваеш разницу тиков первой функции и второй...
все.


--------------------
Tempora mutantur, et nos mutamur in illis...
PM ICQ   Вверх
diman_bulgar
Дата 12.1.2006, 18:07 (ссылка) | (голосов: 0) Загрузка ... Загрузка ... Быстрая цитата Цитата


Unregistered
Меня интересует правильность функции insertsortlist()???
Код

void insertsortlist(void)                      
{
item *q ;                                  
item *pp, * pr;                    
item *tmp = NULL;                                    
while (p !=NULL)                        
     {                           
     q = p; p = p->next;                                       
     for (pp = tmp, pr=NULL; pp!=NULL && pp->element < q->element; pr=pp, pp=pp->next);
     q->next = pp;
     if (pr==NULL) 
        tmp=q; 
    else
       pr->next=q;
     }
     tmp=p;                                     
}
  Вверх
_hunter
Дата 12.1.2006, 18:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

Репутация: 16
Всего: 98
тогда вам сюда:
http://ishodniki.ru/list/?cat=18&show=alg-sort
Добавлено @ 18:41
или сюда:
http://program.rin.ru/razdel/html/771.html


--------------------
Tempora mutantur, et nos mutamur in illis...
PM ICQ   Вверх
threef
Дата 12.1.2006, 22:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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

Код


void insertsortlist(void)                      
{
item *q ;                                  
item *pp, * pr;                    
item *tmp = NULL;                                    
while (p !=NULL)                        
     {                           
     q = p; p = p->next;                                       
     for (pp = tmp, pr=NULL; pp!=NULL && pp->element < q->element; pr=pp, pp=pp->next);
     q->next = pp;
     if (pr==NULL) 
        tmp=q; 
    else
       pr->next=q;
     }
     tmp=p;   
     


У тебя все улетает в NULL, и pr, и tmp, и pp.

А вообще-то для этого используют сортированный список, чтобы избегать подобных извращений. При изменении порядка сортировки легче(и быстрее) создать новый вариант сортированного списка и переставить туды элементы из предыдущего по одному, не теряя дополнительной памяти.
PM MAIL   Вверх
diman_bulgar
Дата 13.1.2006, 03:53 (ссылка) | (голосов: 0) Загрузка ... Загрузка ... Быстрая цитата Цитата


Unregistered
Цитата

void insertsortlist(void)                     
{
item *q ;                                 
item *pp, * pr;                   
item *tmp = NULL;                                   
while (p !=NULL)                       
    {                         
    q = p; p = p->next;                                     
    for (pp = tmp, pr=NULL; pp!=NULL && pp->element < q->element; pr=pp, pp=pp->next);
    q->next = pp;
    if (pr==NULL)
        tmp=q;
    else
      pr->next=q;
    }
    tmp=p; 



Я знаю что код не работает. Поэтому и спрашиваю как правильно его переписать ? Он или не сортирует вообще или выдает ошибку smile . Если кто знает , напишите сорс (правильный). smile
  Вверх
threef
Дата 13.1.2006, 13:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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

void foofoosortlist(void)                      
{
item *p=list->next->next,*q;
while (p !=NULL)                        
 {                       
     q = list;
     while(q->next->element < p->element&&
               q->next!=p)
    {
            q=q->next;
    }
     if(q->next==p)
    {
       p=p->next; 
       continue;
     }
     item *pnext=p->next;

     p->next=q->next;
     q->next=p;
     q=p->next;
     while(q->next!=p&&q->next)
         q=q->next;
     q->next=pnext;
     printlist();
     p=pnext;// !
}
}



Как твою сортировку исправить - не знаю.
Загони в список 30-50 тыс. даблов, подсчитай время сортировки для пузыря, очисть список, Загони в список 30-50 тыс. даблов, подсчитай время сортировки для вставок, сравни при помощи значка > или <
PM MAIL   Вверх
diman_bulgar
Дата 13.1.2006, 15:12 (ссылка) | (голосов: 0) Загрузка ... Загрузка ... Быстрая цитата Цитата


Unregistered
Все спасибо огромное , разобрался smile smile
  Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

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

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

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

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


 




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


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

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