C++ třídění seznamu

alza

C++ třídění seznamu
« kdy: 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. 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 a snažil se ho upravit. Našel jsem dokonce knihu na books.google.com, 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;       
}


Sten

Re:C++ třídění seznamu
« Odpověď #1 kdy: 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 ;-)

qwerqwerqwerqwr

Re:C++ třídění seznamu
« Odpověď #2 kdy: 23. 07. 2012, 19:09:09 »

alza

Re:C++ třídění seznamu
« Odpověď #3 kdy: 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.

Nobody

Re:C++ třídění seznamu
« Odpověď #4 kdy: 23. 07. 2012, 21:02:34 »
Dneska mam dobrou naladu a mel jsem i 10 minut casu, ale:
  • je to C a ne C++ (takze minimalne malloc,free versus new,delete)
  • stejne si to neobhajis ze jsi to psal ty

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


klw

Re:C++ třídění seznamu
« Odpověď #5 kdy: 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.

Sten

Re:C++ třídění seznamu
« Odpověď #6 kdy: 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).

Logik

  • *****
  • 1 022
    • Zobrazit profil
    • E-mail
Re:C++ třídění seznamu
« Odpověď #7 kdy: 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.

Sten

Re:C++ třídění seznamu
« Odpověď #8 kdy: 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í.

Vasek

Re:C++ třídění seznamu
« Odpověď #9 kdy: 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 ;-)

alza

Re:C++ třídění seznamu
« Odpověď #10 kdy: 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;
}

iwtu

Re:C++ třídění seznamu
« Odpověď #11 kdy: 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

Nobody

Re:C++ třídění seznamu
« Odpověď #12 kdy: 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:
  • 'roztrhas' ten seznam na jednotlive prvky
  • ty podle daneho kriteria (v tvem pripade x-te posledni cislice) rozdelis do nekolika 'supliku'
  • vsechny 'supliky' zase spojis dohromady

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.


Sten

Re:C++ třídění seznamu
« Odpověď #13 kdy: 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.

Nobody

Re:C++ třídění seznamu
« Odpověď #14 kdy: 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 .......