Fórum Root.cz

Hlavní témata => Vývoj => Téma založeno: alza 23. 07. 2012, 18:50:32

Název: C++ třídění seznamu
Přispěvatel: alza 23. 07. 2012, 18:50:32
Zdravím, předem bych chtěl poděkovat všem za jakoukoliv snahu. Ve škole jsem dostal za úkol udělat program v C++ na řazení celých kladných čísel metodou Radix sort (http://www.alg.webzdarma.cz/diplomka/kap5/radix.html). V programu se musí využít seznam.

Tímto úkolem se již zabývám druhý den a zdá se mi, že se v tom čím dál víc zamotávám. Ze začátku jsem převzal kód z linuxsoft.cz (http://www.linuxsoft.cz/article.php?id_article=868) a snažil se ho upravit. Našel jsem dokonce knihu na books.google.com (http://books.google.cz/books?id=f_nvYNdA30MC&pg=PA6&lpg=PA6&dq=%22c%2B%2B%22+seznam+t%C5%99%C3%ADdeni&source=bl&ots=t2tKVjGC-M&sig=raFT9H3fUwJmcMPpNatYGbew7QU&hl=cs&sa=X&ei=YPQLUJ6hI4XA0QW9g8DRCg&ved=0CFYQ6AEwAQ#v=onepage&q=%22c%2B%2B%22%20seznam%20t%C5%99%C3%ADdeni&f=false), kde se tato problematika popisuje, ale pořad mi něco uniká a nechce to pracovat, ať to zkouším, jak to chci.

Nejvíce by mi pomohlo, kdyby mi někdo poradil, jak mam vytvořit seřazený seznam. Jinak řečeno, bych potřeboval, aby se mi vygenerovalo číslo, zavolala se funkce přidat, kde by se spustil nějaký cyklus, který by porovnával čísla, až by našel místo kam to číslo patří, seznam by se rozpojil a číslo bylo vnořené.

Přidávám kód, se kterým jsem to zkoušel udělat:

Kód: [Vybrat]
void pridej(SEZNAM **pps, int prvek, SEZNAM *s) {

SEZNAM *s2, *s3;
s2 = s;
 
cout << "gener "  << prvek << endl;
if (s != NULL) cout << "s "  << s->data << endl;

if (s == NULL){
s = (SEZNAM *) malloc(sizeof(SEZNAM));
s->data = prvek;
s->dalsi = *pps;
  *pps = s;
}
else {
while (s != NULL)  {
if (s->data < prvek){ 
cout << s->data << " mensi "  << prvek << endl;

}
else if (s->data >= prvek){ 

cout << s->data << " neni mensi - pridat "  << prvek << endl;
s3 = (SEZNAM *) malloc(sizeof(SEZNAM));

s3->data = prvek;
s3->dalsi = s2;
s2->dalsi = s3;
 
return;
}
s2 = s;
s = s->dalsi;
}

    }   

cout << " "  << endl;
while (s != NULL)  {     
cout << "vypis------ "  << s->data << endl;
s = s->dalsi;       
}
Název: Re:C++ třídění seznamu
Přispěvatel: Sten 23. 07. 2012, 19:04:57
Vyrobíte m prázdných seznamů (prvek* seznamy[m] = {};), do nich roztřídíte čísla (pridej_na_konec_seznamu(seznamy[číslo % m], číslo);), potom ty seznamy vezmete jeden za druhým a spojíte je do jednoho dlouhého seznamu (prvku na konci jednoho seznamu nastavíte jako další prvek první prvek následujícího seznamu), a potom znovu třídíte čísla, tentokrát o řád výš.

Btw. pojmenovat prvek seznamu SEZNAM není nejlepší nápad ;-)
Název: Re:C++ třídění seznamu
Přispěvatel: qwerqwerqwerqwr 23. 07. 2012, 19:09:09
http://stackoverflow.com/questions/9368076/quick-sort-on-a-linked-list-with-a-random-pivot-in-c

Quick Sort na linkovanem seznamu v C
Název: Re:C++ třídění seznamu
Přispěvatel: alza 23. 07. 2012, 19:54:14
Vyrobíte m prázdných seznamů (prvek* seznamy[m] = {};), do nich roztřídíte čísla (pridej_na_konec_seznamu(seznamy[číslo % m], číslo);), potom ty seznamy vezmete jeden za druhým a spojíte je do jednoho dlouhého seznamu (prvku na konci jednoho seznamu nastavíte jako další prvek první prvek následujícího seznamu), a potom znovu třídíte čísla, tentokrát o řád výš.

Btw. pojmenovat prvek seznamu SEZNAM není nejlepší nápad ;-)

Velice Vám děkují, určitě je to mnohem jednodušší, než to co jsem tvořil já. Mohl bych Vás prosím poprosit, jestli byste mi pomohl trochu více za nějakou odměnu. Kdybyste napsal email, velice rád bych Vás kontaktoval.
Název: Re:C++ třídění seznamu
Přispěvatel: Nobody 23. 07. 2012, 21:02:34
Dneska mam dobrou naladu a mel jsem i 10 minut casu, ale:

Ale ciste jenom tak pro inspiraci, jak by to mohlo vypadat :-)

Kód: [Vybrat]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>


#define MAXDIGITS 2
#define ELEMENTS 50

struct _t_Element_;
typedef struct _t_Element_ tElement;

struct _t_Element_{
int Value;
tElement *Next;
};

typedef struct{
tElement *Head;
}tList;

typedef struct{
tList Lists[10];
}tBucket;

static
void PrintList(const tList *List){
const tElement *Element;

Element=List->Head;
while (Element!=NULL){
printf(" %d",Element->Value);
Element=Element->Next;
}
printf("\n");
}

static
void CreateList(tList *List){
time_t Time;
int Size,i;

time(&Time);
srand(Time);

List->Head=NULL;

Size=1;
for (i=0;i<MAXDIGITS;i++){
Size*=10;
}

for (i=0;i<ELEMENTS;i++){
tElement *Element;

Element=malloc(sizeof(tElement));
Element->Value=rand()*Size/RAND_MAX;
Element->Next=List->Head;
List->Head=Element;
}
}

static
void DestroyList(tList *List){
while (List->Head!=NULL){
tElement *Element;

Element=List->Head;
List->Head=Element->Next;
free(Element);
}
}

static
void ListAdd(tList *List,tElement *Element){
if (List->Head==NULL){
List->Head=Element;
}
else{
tElement *Next;

Next=List->Head;
while (Next->Next!=NULL){
Next=Next->Next;
}
Next->Next=Element;
}
}

static
void SortList(tList *List){
int Size,i;

Size=1;
for (i=0;i<MAXDIGITS;i++){
tBucket Bucket;
int j;

for (j=0;j<10;j++){
Bucket.Lists[j].Head=NULL;
}

while (List->Head!=NULL){
tElement *Element;
int Index;

Element=List->Head;
List->Head=Element->Next;
Element->Next=NULL;

Index=(Element->Value/Size)%10;
ListAdd(Bucket.Lists+Index,Element);
}

printf("Bucket at %d:\n",i);

for (j=0;j<10;j++){
printf("\t%d:",j);
PrintList(Bucket.Lists+j);
}

List->Head=0;
for (j=0;j<10;j++){
if (Bucket.Lists[j].Head!=NULL){
ListAdd(List,Bucket.Lists[j].Head);
}
}

printf("List at %d:\n",i);
PrintList(List);

Size*=10;
}
}

int main(int argc,char *argv[]){
tList List;

CreateList(&List);
printf("Initial:");
PrintList(&List);

SortList(&List);

printf("FinalList:");
PrintList(&List);

DestroyList(&List);

return 0;
}
Název: Re:C++ třídění seznamu
Přispěvatel: klw 23. 07. 2012, 21:46:29
Pozor na záměnu pojmů 'řazení' × 'třídění'. Řazení je změna pořadí (sorting), třídění je rozdělování do tříd (classification).

PS: Neber to jako rýpání. Tyto pojmy bohužel zaměňují i některé autority s poměrně zvučnými jmény.
Název: Re:C++ třídění seznamu
Přispěvatel: Sten 23. 07. 2012, 22:19:04
Pozor na záměnu pojmů 'řazení' × 'třídění'. Řazení je změna pořadí (sorting), třídění je rozdělování do tříd (classification).

PS: Neber to jako rýpání. Tyto pojmy bohužel zaměňují i některé autority s poměrně zvučnými jmény.

V angličtině se pro oboje používá sorting, proto se to často i v českých překladech učebnic informatiky míchá. Pokud je potřeba to v angličtině rozlišit, řazení je ordering a třídění categorizing nebo classification (tahle dvě slova se nedají moc zaměňovat, ale je dost složité vysvětlit, kdy se používá jedno a kdy druhé, pokud vás to zajímá, Google is your friend; tady by to nicméně bylo categorizing).
Název: Re:C++ třídění seznamu
Přispěvatel: Logik 23. 07. 2012, 23:10:55
Hele, nepleťte mu hlavu blbinama. Radixsort byl je a myslím ještě dlouho bude algoritmus na třídění. Jen to vžité názvosloví, i když ne úplně logicky správné (stejně jako je fakticky nepsrávné mluvit např. o elektronových orbitalech a také se to běžně používá atd...).

PS: Pokud nesouhlasíte, tak si o tom běžte pohovořit s profesorama na matfyzu, při vší úctě bych řekl, že co se týče odborné terminologie jsou to lidé povolanější než diskutující z roota.
Název: Re:C++ třídění seznamu
Přispěvatel: Sten 23. 07. 2012, 23:31:20
Radixsort je řadicí algoritmus, který se český jmenuje číslicové třídění, protože na rozdíl od mnoha jiných řadicích algoritmů používá třídění. Nevím, jak tomu říkají profesoři na matfyzu, ale na MUNI byli na tohle hodně hákliví.
Název: Re:C++ třídění seznamu
Přispěvatel: Vasek 24. 07. 2012, 09:17:54
Sten: Na matfyzu to bylo vetsine vyucujicich nejake drobne slovickareni fuk, hlavne, kdyz tomu clovek rozumel a umel dukazy okolo ;-)
Název: Re:C++ třídění seznamu
Přispěvatel: alza 24. 07. 2012, 16:20:54
Už jsem to řazení (třídění) seznamu vyřešil, možna je to trochu prasárna, ale je to asi maximum co jsem vlastnoručně vytvořil.  ;D

Chtěl bych poděkovat všem poděkovat za ochotu.

Teď se pustim do toho Radixsortu, snad to stihnu. Větši obavy jsem měl z toho samotného seznamu  :-[


Kód: [Vybrat]
void pridej(SEZNAM **prvniPrvekSeznamu, int prvek, SEZNAM *s) {

SEZNAM *s2, *s3, *s1;

s1 = s;
s2 = s;

cout << "gener "  << prvek << endl;
if (s1 != NULL) cout << "s "  << s1->data << endl;



if (s1 == NULL){
s1 = (SEZNAM *) malloc(sizeof(SEZNAM));
s1->data = prvek;
s1->dalsi = *prvniPrvekSeznamu;
*prvniPrvekSeznamu = s1;
}
else {
while (s1 != NULL)  {
if (prvek < s1->data){ 

cout << prvek << " mensi "  << s1->data << endl;

cout << " dalsi "  << s1->dalsi << endl;

if (s1->dalsi == NULL){
cout << " pridat pred " << s1->data << endl;
s3 = (SEZNAM *) malloc(sizeof(SEZNAM));

s2 = s1->dalsi;
s3->data= prvek;
s3->dalsi= s2;

s1->dalsi = s3;

if (s1 == s){
cout << " prvni prvek je - "  << s->data << endl;
*prvniPrvekSeznamu = s;
break;
}else{
cout << " prvni prvek je - "  << s->data << endl;
*prvniPrvekSeznamu = s;
break;
}

}


s2 = s1;
s1 = s2->dalsi;
}

if (prvek >= s1->data){ 

if (s1 == s){
cout << " pridat pred " << s->data <<  endl;
s = (SEZNAM *) malloc(sizeof(SEZNAM));


s->data = prvek;
s->dalsi = *prvniPrvekSeznamu;

cout << " prvni prvek je - "  << s->data << endl; 

*prvniPrvekSeznamu = s;
break;
}
else{

cout << s1->data << " neni mensi - pridat "  << prvek << endl;

s3 = (SEZNAM *) malloc(sizeof(SEZNAM));
s3->data = prvek;
s3->dalsi = s1;
s2->dalsi = s3;


*prvniPrvekSeznamu = s;

break;



}


}

}

   
}


 
cout << " "  << endl;
while (s != NULL)  {     
cout << "vypis------ "  << s->data << endl;
s = s->dalsi;   
}

return;
}
Název: Re:C++ třídění seznamu
Přispěvatel: iwtu 24. 07. 2012, 19:49:57
neviem, kolko mas rokov ale par obecnych rad.

ad0) premyslaj
ad1) nepreberaj cudzi kod (este na to nemas a ani zdaleka to nie je nutne).
ad2) tieto veci su vo vseobecnosti strasne zname. Ak mas problem, pozri si nejaku animaciu a video http://www.youtube.com/watch?v=50_TCQGjNJc
ad3) ak nevies anglincinu, zacni sa poriadne ucit
ad4) premyslaj
Název: Re:C++ třídění seznamu
Přispěvatel: Nobody 24. 07. 2012, 20:10:07
Už jsem to řazení (třídění) seznamu vyřešil, možna je to trochu prasárna, ale je to asi maximum co jsem vlastnoručně vytvořil.  ;D

Chtěl bych poděkovat všem poděkovat za ochotu.

Teď se pustim do toho Radixsortu, snad to stihnu. Větši obavy jsem měl z toho samotného seznamu  :-[




No jo, ale tady ta 'ekvilibristika' co jsi predvedl, nema zadnou souvislost s Radix sortem :-(

Radix sort funguje tak, ze v nekolika iteracich:

Takze potrebujes jen a pouze vkladani prvku na konec seznamu a mergeovani seznamu, coz je zase enom pridani prvniho prvku dalsiho seznamu za konec predchoziho !!!!

Pak ovsem stoji se zamyslet nad implementaci:

a) neni lepsi seznam 'obalit' nejakym typem? (vyhnu se tim tvemu **)
b) zamyslet se jak to jeste vylepsit.

Treba nejpomalejsi opera v me predchozi implementaci je najiti posledniho prvku seznamu 'Next=Next->Next' pro zarazeni. Co takhle obetovat jeste jeden pointer na seznam a pamatovat si misto tail i head?

Kód: [Vybrat]
typedef struct{
tElement *Head;
tElement *Tail;
}tList;


potom, pridani dalsiho prvku do seznamu:

Kód: [Vybrat]
void ListAdd(tList *List,tElement *Element){
if (List->Head==NULL){
List->Head=Element;
}
else{
List->Tail->Next=Element;
}

List->Tail=Element;
Element->Next=NULL;
}

i spojeni dvou seznamu:

Kód: [Vybrat]
void ListMerge(tList *Where,tList *What){
if (Where->Head==NULL){
Where->Head=What->Head;
}
else{
Where->Tail->Next=What->Head;
}
Where->Tail=What->Tail
}

jsou vice-mene atomicke operace :-)

Toz tak.

Název: Re:C++ třídění seznamu
Přispěvatel: Sten 24. 07. 2012, 21:46:41
Technická: má to být C nebo C++? V C++ bych to alespoň trochu obalil do objektů, aby to nějak vypadalo:

Kód: [Vybrat]
struct Prvek
{
    Prvek(int hodnota)
        : hodnota(hodnota)
        , dalsi(nullptr)
    {}

    int hodnota;
    Prvek *dalsi;
};

class Seznam
{
public:
    Seznam()
        : prvni(nullptr)
        , posledni(nullptr)
    {}

    Prvek* vystrc() // Vystrci prvek zepredu; pokud je seznam prazdny, vrati nullptr
    {
        if (!this->prvni)
            return nullptr;
        Prvek *p = this->prvni;
        this->prvni = this->prvni->dalsi;
        if (!this->prvni) {
            // Vystrkuji posledni prvek
            this->posledni = nullptr;
        }
        // Prvek je mimo seznam, tak nema nikoho dalsiho
        p->dalsi = nullptr;
        return p;
    }

    Seznam& pridej(Prvek *prvek) // Prida prvek na konec
    {
        if (!this->posledni) {
            // Seznam je zatim prazdny, novy prvek bude jeho jedinny
            this->prvni = this->posledni = prvek;
            return *this;
        }
        this->posledni->dalsi = prvek;
        this->posledni = prvek;
        return *this;
    }

    Seznam& pridej(Seznam &seznam) // Ukradne dodanemu seznamu prvky a da je na konec tohoto seznamu
    {
        if (!this->posledni) {
            this->prvni = seznam.prvni;
        } else {
            this->posledni->dalsi = seznam.prvni;
        }
        this->posledni = seznam.posledni;
        seznam.prvni = seznam.posledni = nullptr;
        return *this;
    }

protected:
    Prvek *prvni;
    Prvek *posledni;
};

Potom už je to jenom přehazování prvků mezi různými seznamy pomocí metod vystrc a pridej.
Název: Re:C++ třídění seznamu
Přispěvatel: Nobody 24. 07. 2012, 22:30:03
Technická: má to být C nebo C++? V C++ bych to alespoň trochu obalil do objektů, aby to nějak vypadalo:

No to sem prave taky nepochopil - puvodni tazatel sice pise C++, ale pouziva malloc a struktury.
A navic ta funkce ma nejaky divny prototyp: bud do list pridavam element nebo hodnotu a element vytvorim, ale proc ma jako vstupni i prvek, i SEZNAM*, to tedy vubec nevim :-(

Ale co, snad se nam to chlapec nauci .......