Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Как сделать сортировку линейного списка (пузырь)?

Автор: diman_bulgar 9.1.2006, 01:01

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

Автор: Guest 9.1.2006, 01:08

на С++

Автор: Fin 9.1.2006, 02:03

Возьми любую серьезную книгу по Алгоритмам. Там даны полные математические выкладки по пузырьку и вставкам. Рекомендую Д.Кнут "Искусство программирования".

Автор: Guest 9.1.2006, 02:17

мне на С++ надо и именно для линейного списка smile

Автор: BreakPointMAN 9.1.2006, 02:25

Как это ни странно, но никто, кажется, не знает, о существовании на этом форуме ветки http://forum.vingrad.ru/index.php?showtopic=37776&view=all, в которой есть и сортировка: http://forum.vingrad.ru/index.php?showtopic=37776&view=findpost&p=285335.

Ну а из книг, конечно, Кнут и Кормэн... smile

Полезная ссылка по теме: http://algolist.manual.ru/sort/index.php
Добавлено @ 02:32

Цитата(Guest @ 9.1.2006, 02:17

)

именно для линейного списка

посмотри по данным ссылкам, может быть найдешь что полезное...

Автор: Guest 9.1.2006, 03:06

Вот код Johna Smithа :

Код


#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 main(void)
{
 list=(item*)malloc(sizeof(item));
 list->element=0;
 list->next=NULL;
 p=list;

 Add(4);
 Add(7);
 Add(2);
 Add(12);
 Add(0);
 Add(8);
 printlist();
 free(list);
}

Теперь хочу отсортировать методом "пузырька" этот список . КАК ??? Кто знает ?

Автор: threef 11.1.2006, 19:58

Код


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;
   }
}

Неча тут знать. Трясти надо. Это к предыдущему коду

Автор: Guest 11.1.2006, 23:42

огромно спасибо smile