[es] - Sortiranje jednostruko spregnute liste u C-u?

jumper2high
2High Jumper

Član broj: 39396
Poruke: 27
*.dynamic.sbb.co.yu.

+1 Profil

Sortiranje jednostruko spregnute liste u C-u?

^{12.01.2007. u 10:23 - pre 210 meseci}

Cilj programa mi je da iz tekstualnog fajla procita jedan red, u kome se nalaze ime i prezime, zatim ih strpa u listu, istovremeno sortirajuci istu.

Dakle, da za svaki novi red, prodje kroz listu, nadje od kojeg je elementa liste "veci" po abecednom poretku, pa da se smesti ispred doticnog. Prvi pokusaj ovoga se pokazao kao fatalno neuspesan, pa sam onda pokusao malo glupljom metodom. Da samo naguram sve u listu, a onda prodjem kroz celu listu par stotina puta, poredim "trenutni" sa "prethodnim" i zamenim im pokazivace tako da se ponasaju kao da su zamenili mesta. Iznenadjujuce, ovo nije radilo (cak i posle 2-3 algoritma radi provere). Onda mi je palo na pamet da umesto da cackam pokazivace, samo zamenim sadrzaj podataka unutar memorijskih lokacija, recimo kao sto sam radio sa matricama, naravno ostavljajuci pokazivace iste. Ovo se, kao i sve prethodne metorde, zavrsilo sa Segmentation fault-om.

Ok, dosta price - sada pitanje: da li postoje neka posebna pravila ili ogranicenja sto se tice manipulacije pokazivacima i listama? Za poredjenje dva elementa koristio sam prvo funkciju "strcmp", a onda pribegao primitivnijim metodama if(prethodni->ime[0] < trenutni->ime[0]) medjutim, ne verujem da je u tome problem.

Pozdrav
j2h.

Odgovor na temu

lucky

Član broj: 2032
Poruke: 57
..AT.HighSpeedADSL.beotel.net.

Jabber: lucky@elitesecurity.org

+1 Profil

Re: Sortiranje jednostruko spregnute liste u C-u?

^{12.01.2007. u 16:22 - pre 210 meseci}

Generalno, mozes da ubacujes novi cvor na tacno odredjeno mesto odmah prilikom unosa podataka ili da trpas redom u listu i onda tu listu sortiras. Po tvojoj prici, rekao bih, pokusao si na oba nacina ali nisi uspeo da realizujes. Da bi neko uoste video gde gresis mogao bi da ostavis code, da ne nagadjamo.

Odgovor na temu

jumper2high
2High Jumper

Član broj: 39396
Poruke: 27
*.dynamic.sbb.co.yu.

+1 Profil

Re: Sortiranje jednostruko spregnute liste u C-u?

^{14.01.2007. u 10:41 - pre 210 meseci}

Hvala za quick responce, evo kako moj code izgleda: napravio sam samo osnovni program da ucita tri imena (prezimena) sa STDIN-a, i cilj je da odma u listu stavlja po abecednom poretku. Problem je sto imam odredjena ogranicenja, a to je da koristim samo one osnovne stvari i recimo 2-3 specificne funkcije (naredbe) tipa "strcpy" ili "strcmp". Znaci da ne bude nista fancy :P

Code:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct lista
{
    char string[20];
    struct lista *sled;
};
typedef struct lista Item;

main()
{
    char buffer[20];
    int i=0;
    int k=4;
    int upis=0;
    Item *novi,*glava,*prethodni,*trenutni;
    glava=NULL;

// UNOS PODATAKA

    for(i=0;i<3;i++)
    {
        upis=0;
        printf("Prezime \t=>");
        fgets(buffer,sizeof(buffer),stdin);
        for(k=0;k<20;k++) if(buffer[k]==' '||buffer[k]=='\n'||buffer[k]=='\t') buffer[k]='\0';
// NOVI LIST ITEM
        novi=(Item *)malloc(sizeof(Item));
        strcpy(novi->string,buffer);
        novi->sled=NULL;

        if(glava==NULL)
        {
            printf("Kao prvi\n");
            glava=novi;
        }
        else
        {
            trenutni=glava;
            prethodni=trenutni;
            while(trenutni!=NULL&&buffer[0]<trenutni->string[0]&&upis!=1)
            {
                printf("Nije manji\n");
                prethodni=trenutni;
                trenutni=trenutni->sled;
            }
            if(prethodni==glava)
            {
                printf("Manji je od prvog\n");
                prethodni=novi;
                novi->sled=trenutni;
                upis=1;
            }
            else if(prethodni!=glava)
            {
                printf("U sredini\n");
                prethodni->sled=novi;
                novi->sled=trenutni;
                upis=1;
            }
        }
    }
// KRAJ UNOSA - ISPISIVANJE

    trenutni=glava;
    while(trenutni!=NULL)
    {
        printf("| %s\t|\n",trenutni->string);
        trenutni=trenutni->sled;
    }
}

Pozdrav, i hvala unapred!

Odgovor na temu

lucky

Član broj: 2032
Poruke: 57
..AT.HighSpeedADSL.beotel.net.

Jabber: lucky@elitesecurity.org

+1 Profil

Re: Sortiranje jednostruko spregnute liste u C-u?

^{14.01.2007. u 22:45 - pre 210 meseci}

Evo ovo radi.

Code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct lista
{
    char string[20];
    struct lista *sled;
};
typedef struct lista Item;

main()
{
    char buffer[20];
    int i=0;
    int k=4;
    int upis=0;
    Item *novi,*glava,*prethodni,*trenutni;
    glava=NULL;

// UNOS PODATAKA

    for(i=0;i<4;i++)
    {
        // upis=0;
        printf("Prezime \t=>");
        fgets(buffer,sizeof(buffer),stdin);
        for(k=0;k<20;k++)
        if(buffer[k] == ' ' || buffer[k] == '\n' || buffer[k] == '\t')
            buffer[k] = '\0';
// NOVI LIST ITEM
        novi=(Item *)malloc(sizeof(Item));
        strcpy(novi->string,buffer);
        novi->sled=NULL;

        if(glava==NULL)
        {
            printf("Kao prvi\n");
            glava=novi;
        }
        else
        {
            trenutni=glava;
            prethodni=trenutni;
            while(trenutni != NULL && buffer[0] > trenutni->string[0]) //&& upis != 1) ovo ti ne treba a ako hoces u rastucem poretku onda je znak >
            {
                printf("Nije manji\n");
                prethodni=trenutni;
                trenutni=trenutni->sled;
            }
            if(prethodni==glava && prethodni == trenutni)
            {
                printf("Manji je od prvog\n");
                //prethodni->sled=novi;
                //novi->sled=trenutni->sled;
        novi->sled = glava;
        glava = novi;
                // upis=1;
            }
            else // if(prethodni!=glava)
            {
                printf("U sredini\n");
                prethodni->sled=novi;
                novi->sled=trenutni;
                // upis=1;
            }
        }
    }
// KRAJ UNOSA - ISPISIVANJE

    trenutni=glava;
    while(trenutni!=NULL)
    {
        printf("| %s\t|\n",trenutni->string);
        trenutni=trenutni->sled;
    }
// OSLOBADJANJE MEMORIJE !!!!!!!!!!! Ovo si zaboravio a bitno je!
    while(glava != NULL)
    {
    trenutni=glava;
    glava = glava->sled;
    free(trenutni);
    }
}

Odgovor na temu