Problemi u C-u

[NEWSWEETTOFFEE]

Ćao!

Dakle, problem je sledeći:

Imam kod za stek definisan preko pokazivača i on štampa članove steka od onog koji je zadnji unešen, a nije uklonjen sa steka. Ovo je taj kod:

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

typedef struct el
{
     int v;
     struct el *sledeci;
}Elem;

Elem *stek;

void Dodaj(int v)
{
     Elem *novi=(Elem*)malloc(sizeof(Elem));
     novi->v=v;
     novi->sledeci=stek;
     stek=novi;
     printf("Dodaje se element %d.\n", v);
}

void Ukloni()
{
     if(stek==NULL)
     {
          printf("Stek je prazan.\n"); 
          return;
     }
     
     int v=stek->v;
     stek=stek->sledeci;
     printf("Uklanja se element %d.\n", v); 
}

void Ukloni()
{
     if(stek==NULL)
     {
          printf("Stek je prazan.\n"); 
          return;
     }
     
     int v=stek->v;
     stek=stek->sledeci;
     printf("Uklanja se element %d.\n", v); 
}

void Stampaj()
{
     Elem *t=stek;
     printf("Stek: ");
     while(t!=NULL)
     {
           printf("%d  ", t->v);
           t=t->sledeci;
      }
      putchar('\n');
}


int main()
{
     Dodaj(5);
     Dodaj(-2);
     Dodaj(0);
     Dodaj(9);
     Dodaj(2);
     Stampaj();
     Ukloni();
     Stampaj();

     return 0;
}

Odlučio sam da izmenim funkciju 'Stampaj', tako da se elementi u steku štampaju od prvog unesenog pa dalje, i ovo je ta nova funkcija 'Stampaj':

void Stampaj()
{
     int n=0, i; 
     Elem *t1=stek, *t2=stek;
     while(t1!=NULL)
     {
          n++;
          t1=t1->sledeci;
     }
 
     int *niz=(int*)malloc(sizeof(int)*n);
     while(t2!=NULL)
     {
          niz[--n]=t2->v;
          t2=t2->sledeci;
     }

     printf("Stek: ");
     for(i=0; i<n; i++)
          printf("%d  ", niz[i]);
     putchar('\n');
     free(niz);
}

Kada pokrenem program sa novom funkcijom 'Stampaj', onda se sve pojavljuje kao i ranije, samo nema članova steka. U prozoru za prikaz rezultata piše: 'Stek: '. Sva ostala obaveštenja o dodavanju i uklanjanju su ista i tačna.

Molim vas, može li mi neko reći zašto ova nova funkcija ne radi ono što želim da radi?

[NIx Car]

Pa naravno da nece da radi kada si ti n povecavao i onda si to n opet smanjivao. I sad ti je n = 0 jer si ga smanjio onoliko puta koliko puta si ga i povecao
Mozda bi bilo dobro da napravis strukturu stek, koja bi od polja imala Element i int velicinu, pa bi uvezivanjem novog elementa u stek, povecavao i taj brojac

[NEWSWEETTOFFEE]

Hvala na brzom odgovoru. Našao sam rešenje. Dodao sam drugi brojač:

void Stampaj()
{
     int m=0, n=0, i;
     Elem *t1=stek, *t2=stek;
     while(t1!=NULL)
     {
           m++;
           n++;
           t1=t1->sledeci;
     }

     int *niz=(int*)malloc(sizeof(int)*m);
     while(t2!=NULL)
     {
          niz[--m]=t2->v;
          t2=t2->sledeci;
     }

     printf("Stek: ");
     for(i=0; i<n; i++)
          printf("%d  ", niz[i]);
     putchar('\n');
     free(niz);
}

[NEWSWEETTOFFEE]

Imam pitanje u vezi sledećeg koda:

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

typedef struct el
{
    int kljuc;
    char vrednost[10];
    struct el *sledeci;
}Elem;

Elem *lista=NULL;

void Dodaj(Elem *e, int k, char *v)
{
    Elem *novi=(Elem*)malloc(sizeof(Elem));
    novi->kljuc=k;
    strcpy(novi->vrednost, v);
    novi->sledeci=lista;
    lista=novi;
}

void Pronadji(Elem *e, int k)
{
    if(e==NULL)
    {
        printf("Ne postoji element sa kljucem %d.\n", k);
        return;
    }
    else if(k==e->kljuc)
    {
        printf("Vrednost sa kljucem %d je: %s\n", k, e->vrednost);
        return;
    }
    else
        Pronadji(e->sledeci, k);
}

void Odstampaj(Elem *e)
{
    if(e==NULL)
    {
        printf("---Kraj liste---\n");
        return;
    }
    printf("%d  %s\n", e->kljuc, e->vrednost);
    Odstampaj(e->sledeci);
}

void OslobodiMemoriju(Elem *e)
{
    if(e==NULL)
        return;
    Elem *n=e->sledeci;
    free(e);
    OslobodiMemoriju(n);
}


int main()
{
    Dodaj(lista, 3, "tri");
    Dodaj(lista, 2, "dva");
    Dodaj(lista, 6, "sest");
    Dodaj(lista, 4, "cetiri");
    Odstampaj(lista);

    Pronadji(lista, 6);
    Pronadji(lista, 12);

    OslobodiMemoriju(lista);

    return 0;
}

Pošto se prvi argument funkcije 'Dodaj' ne koristi, da li ta funkcija može bez tog argumenta, tj. da ima samo druga dva argumenta? Ispitao sam i to, i program daje isti rezultat (sa već adtim podacima u 'main' funkciji), pa mislim da je odgovor potvrdan. Da li sam nešto prevideo?

[NIx Car]

Rezultat ti je isti zato sto ti svakako u globalnu promenljivu te rezultate upisujes, nigde u toj funkciji ne koristis promenljivu e koju prosledjues kao parametar pa to sve gubi smisao. Generalna praksa je da se globalne promenljive (sem konstanti) izbegavaju.

[NEWSWEETTOFFEE]

Da, svestan sam uloge globalne promenljive u ovoj funkciji, ali sam mislio da je prva promenljiva 'e' dodata zbog još nečeg što ne vidim, ali je možda samo onaj ko je napisao program malo zaboravio na globalnu promenljivu.

[NEWSWEETTOFFEE]

Dakle, imam problem sa sledećim kodom:

int brojBita(int x)
{
    int broj=0;
    while(x!=0)
    {
        if((x&0x1)==1)
            broj++;
        x=x>>1;
    }

    return broj;
}


int main()
{
    int n;
    scanf("%d", &n);
    printf("Cifra 1 se u binarnom zapisu pojavljuje %d puta.\n", brojBita(n));

    return 0;
}

Koliko shvatam negativni celi brojevi se u memoriji zapisuju na sledeći način:
1) Odredi se binarni zapis apsolutne vrednosti datog negativnog broja.
2) U tom zapisu se jedinice zamene sa nulama i obrnuto.
3) Taj novi broj se sabere sa jedinicom i taj zbir je binarni zapis datog negativnog celog broja.

Program radi za nenegativne celobrojne vrednosti, ali mi nije jasno zašto ne radi za negativne cele brojeve. Unesem negativan broj, pritisnem 'Enter', i ništa se ne dešava. Funkcija 'brojBita' dobija celi broj, ali radi samo sa njegovim binarnim zapisom, tako da vas molim da mi kažete šta je ovde pogrešno shvatam.

[voodoo_]

Shvatio si lepo kako radi, problem je u implementaciji. Standard za jezik C ne definiše šta mora da se desi kad se negativni broj right-shiftuje, tako da to zavisi od konkretnog kompajlera. Ako kompajler prosto pomeri sve kečeve udesno, a s leve strane dopuni nulama (što radi kad su u pitanju pozitivni i unsigned brojevi), onda bi negativni broj izgubio krajnjeg levog keca, izgubio "status" negativnog broja i dobio neku nelogičnu vrednost. Zbog toga većina kompajlera radi takozvani aritmetički šifting, odnosno udesno "povlači" sve komplementarne jedinice i čuva krajnju levu jedinicu za znak:

n = -16 ( 1111 0000 )
n >> 1 = -8 ( 1111 1000)
n >> 1 = -4 ( 1111 1100)
itd.

Što se poklapa sa logikom desnog šiftovanja pozitivnih brojeva, gde je desno šiftovanje isto što i deljenje sa dva.

Ovo predstavlja problem u tvojoj implementaciji brojenja jer će zbog čuvanja komplementarnih kečeva broj uvek biti različit od nule i nikad neće izaći iz petlje, što možeš lako da debaguješ ubacivanjem printa stanja broja u memoriji:

int brojBita(int x)
{
    int broj=0;
    while(x!=0)
    {
        if((x&0x1)==1)
            broj++;
        x=x>>1;
        printf("Trenutno stanje x: %08X\n", x);
    }

    return broj;
}

Problem možeš da rešiš tako što ćeš da "zezneš" kompajler i broj prethodno kastuješ u unsigned (odnosno kažeš mu da memorijsku lokaciju X tretira kao unsigned int):

int brojBita(int x)
{
    unsigned int ux = (unsigned int) x;
    int broj = 0;
    while (ux) {
        if (ux & 0x1) {
            broj++;
        }
        ux >>= 1;
    }

    return broj;
}

[NEWSWEETTOFFEE]

voodoo_ kaže:

Problem možeš da rešiš tako što ćeš da "zezneš" kompajler i broj prethodno kastuješ u unsigned (odnosno kažeš mu da memorijsku lokaciju X tretira kao unsigned int):

int brojBita(int x)
{
    unsigned int ux = (unsigned int) x;
    int broj = 0;
    while (ux) {
        if (ux & 0x1) {
            broj++;
        }
        ux >>= 1;
    }

    return broj;
}

Ovo sam probao i daje tačan rezultat, ali mi nije jasno kako. Zar se, jednostavno, promenljivoj ux ne doda nenegativna vrednost i onda je njen binarni zapis, zapis za pozitivne brojeve i nulu (mada koliko znam i nula se može zapisati u komplementu dvojke)?

Što se tiče prvog saveta, kada sam dodao printf, ako bih funkciji dao negativan broj, samo sam dobijao ispis sa osam f-ova, i to unedogled. Da li je to trebalo da bude tako?

[voodoo_]

1) Ne dodaje se ništa.

unsigned int ux = (unsigned int) x;

znači "iskopiraj sadržaj x u ux, ali ga iskopiraj doslovno bez razmatranja da li je pozitivan ili negativan (jer nema negativnih kod unsigned int-a)". Što će reći, ako je x bilo npr. -4, (ne zaboravi da je int implicitno isto što i signed int), to se u memorijskoj lokaciji skladišti kao

1111 1111 1111 1111 1111 1111 1111 1100

I onda kad ga kastuješ u unsigned int, tu nema negativnih brojeva nego se tretira kao pozitivni broj 0xFFFFFFFC, i tako se obrađuje za prebrojavanje jedinica (odnosno primenjuje se right-shift logika kao za pozitivne brojeve).

2) Trebalo je, pogledaj prethodno objašnjenje šta se dešava kad se right-shift operator primeni na signed int koji je negativan.

[NEWSWEETTOFFEE]

voodoo_ kaže:

2) Trebalo je, pogledaj prethodno objašnjenje šta se dešava kad se right-shift operator primeni na signed int koji je negativan.

Sad sam shvatio šta se dešava za negativne 'signed' intidžere. Posle nekog vremena se njihov zapis u mom prvom kodu pretvori u same jedinice pa se beskonačno vrti. U ispisu mi se ne vidi to popunjavanje zapisa jedinicama (previše brzo prođe da bih video), pa sam zato bio zbunjen, jer nisam zadavao broj sa heksadecimalnim zapisom 'FFFFFFFF'.

[NEWSWEETTOFFEE]

Sledeći kod mi zadaje muke, iako radi ono što treba da radi:

typedef struct el
{
    int kljuc;
    char string[10];
    struct el *sledeci;
}Elem;

Elem *lista=NULL;

void Dodaj(Elem *e, int k, char *s)
{
    if(/*lista*/e==NULL) // Zasto ne moze da se stavi 'e' umesto 'lista' u ova cetiri navrata?
    {
        Elem *novi=(Elem*)malloc(sizeof(Elem));
        novi->kljuc=k;
        strcpy(novi->string, s);
        novi->sledeci=NULL;
        /*lista*/e=novi;
        return;
    }
    else if(k</*lista*/e->kljuc)
    {
        Elem *novi=(Elem*)malloc(sizeof(Elem));
        novi->kljuc=k;
        strcpy(novi->string, s);
        novi->sledeci=e;
        /*lista*/e=novi;
        return;
    }
    else if(e->sledeci==NULL)
    {
        Elem *novi=(Elem*)malloc(sizeof(Elem));
        novi->kljuc=k;
        strcpy(novi->string, s);
        novi->sledeci=NULL;
        e->sledeci=novi;
        return;
    }
    else if(k<e->sledeci->kljuc)
    {
        Elem *novi=(Elem*)malloc(sizeof(Elem));
        novi->kljuc=k;
        strcpy(novi->string, s);
        novi->sledeci=e->sledeci;
        e->sledeci=novi;
        return;
    }
    else
        Dodaj(e->sledeci, k, s);
}

Dakle, ako se menjanjem argumenta 'e' menja i globalna promenljiva 'lista' (Kada se doda element u 'e', dodaje se u stvari u 'lista'.) šta sprečava da se u prva dva dela if petlje koristi 'e' umesto 'lista'?

Razumem da se u drugom i trećem 'else if'-u koristi 'e' jer možda mora da se ide u "dubinu" liste, dok pri svakom pozivu funkcije 'Dodaj' 'lista' se uvek koristi od prvog člana.

[voodoo_]

Problem je u liniji "e=novi;"

Pretpostavljam da vas u školi uče da se u C-u argumenti funkcije prenose po vrednosti, osim pokazivača koji se prenose "po referenci", što u suštini nije tačno jer se i pokazivači prenose kao kopija vrednosti (odnosno kopija adrese, u slučaju pokazivača). Istina je da možeš da menjaš ono na šta "e" pokazuje i to će biti zapamćeno nakon izlaska iz funkcije, ali izmenjenu vrednost (adresu) pokazivača "e" program neće zapamtiti na izlasku iz funkcije, tako da će nakon inicijalnog Dodaj(lista, 0, "Tekst") vrednost "lista" i dalje ostati NULL.

Rešenje je ili da direktno menjaš globalnu promenljivu, ili da koristiš pokazivač na pokazivač, u tom slučaju i dalje ne možeš da menjaš argument, ali možeš ono na šta on pokazuje

void Dodaj(Elem **e, int k, char *s)
{
    if (*e == NULL)
    {
        Elem *novi=(Elem*)malloc(sizeof(Elem));
        novi->kljuc=k;
        strcpy(novi->string, s);
        novi->sledeci=NULL;
        *e = novi;
        return;
    }
    ...
}

int main()
{
    Dodaj(&lista, 0, "Tekst");

    printf("%s\n", lista->string);

    return 0;
}

To jest prvi argument je pokazivač na pokazivač na element; prvi pokazivač ne možeš da menjaš, ali drugi možeš, a možeš da menjaš i element na koji taj drugi pokazuje.

[NEWSWEETTOFFEE]

voodoo_ kaže:

Kod mene radi i sa "if (e == NULL)", kompajler je GCC 4.8.5.
Koji koristiš i da li bilduješ projekat kao C ili C++?

Projekat je C. Molim te, možeš li proveriti da li radi kada je u sva četiri slučaja koja sam naveo, 'e' umesto 'lista'? Ovaj program radim u Code::Blocks 13.12, a kompajler je GNU GCC (kada pravim projekat onda taj bude ponuđen).

[voodoo_]

Proverio sam detaljnije, editovao sam poruku, imaš gore objašnjenje.

[NEWSWEETTOFFEE]

Ćao!

Imam problem sa sledećim kodom:

void Ukloni(ss *e)
{
    if(e==NULL)
    {
        printf("Lista je prazna.\n");
        return;
    }
    if(e->sledeci==NULL)
    {
        printf("Uklanja se element %d.\n", e->el);
        // Kako napraviti da na 'listi' nema ovog elementa?
        return;
    }
    if(e->sledeci->sledeci==NULL)
    {
        printf("Uklanja se element %d.\n", e->sledeci->el);
        e->sledeci=NULL;
        return;
    }
    Ukloni(e->sledeci);
}

Dakle, nikako ne mogu da napravim da, ako 'e' ima samo jedan element, da ga funkcija izbriše i da 'e' nema nijedan element. Probao sam sa

e->el=NULL; e=NULL; lista=NULL; /* Sortiranu 'listu' zadajem funkciji da je skrati za zadnji element. */

, ali i dalje 'lista->el' ostaje isti element. Molim da mi neko kaže u čemu grešim?

[NIx Car]

Ni slucajno ne smes da radis = NULL jer time samo kazes pokazivacu da ne pokazuje ni na jedan element, dok element na koji je taj pokazivac pokazivao, idalje ostaje u memoriji i dolazi do curenja memorije.
koristi free(e); funkciju koja ce uraditi to sto trazis

[NEWSWEETTOFFEE]

NIx Car kaže:

Ni slucajno ne smes da radis = NULL jer time samo kazes pokazivacu da ne pokazuje ni na jedan element, dok element na koji je taj pokazivac pokazivao, idalje ostaje u memoriji i dolazi do curenja memorije.
koristi free(e); funkciju koja ce uraditi to sto trazis

Izvinjavam se, nisam postavio da sam probao i tu opciju, ali mi samo ispisuje neku adresu.

Kada sam koristio 'e->el=NULL' i pokušao da odštampam listu, onda mi je prvi element postajao nula. Evo celog koda, za svaki slučaj:

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

typedef struct s
{
    int el;
    struct s *sledeci;
}ss;

ss *lista=NULL;

void Dodaj(ss *e, int v)
{
    if(lista==NULL)
    {
        ss *novi=(ss*)malloc(sizeof(ss));
        novi->el=v;
        novi->sledeci=NULL;
        lista=novi;
        return;
    }
   else if(v<lista->el)
    {
        ss *novi=(ss*)malloc(sizeof(ss));
        novi->el=v;
        novi->sledeci=e;
        lista=novi;
        return;
    }
    else if(e->sledeci==NULL)
    {
        ss *novi=(ss*)malloc(sizeof(ss));
        novi->el=v;
        novi->sledeci=NULL;
        e->sledeci=novi;
        return;
    }
    else if(v<e->sledeci->el)
    {
        ss *novi=(ss*)malloc(sizeof(ss));
        novi->el=v;
        novi->sledeci=e->sledeci;
        e->sledeci=novi;
        return;
    }
    else
        Dodaj(e->sledeci, v);
}

void Ukloni(ss *e)
{
    if(e==NULL)
    {
        printf("Lista je prazna.\n");
        return;
    }
    if(e->sledeci==NULL)
    {
        printf("Uklanja se element %d.\n", e->el); // Kako napraviti da na 'listi' nema ovog elementa? */
        ???
        return;
    }
    if(e->sledeci->sledeci==NULL)
    {
        printf("Uklanja se element %d.\n", e->sledeci->el);
        free(e->sledeci->sledeci);
        e->sledeci=NULL;
        return;
    }
    Ukloni(e->sledeci);
}

void Odstampaj(ss *e)
{
    if(e->sledeci==NULL)
    {
        printf("%d -Kraj liste-\n", e->el);
        return;
    }
    printf("%d ", e->el);
    Odstampaj(e->sledeci);
}

void OslobodiMemoriju(ss *e)
{
    if(e==NULL)
        return;
    ss *n=e->sledeci;
    free(e);
    OslobodiMemoriju(n);
}


int main()
{
    Dodaj(lista, 5);
    Dodaj(lista, 2);
    Dodaj(lista, -1);
    Dodaj(lista, 9);
    Dodaj(lista, 6);
    Odstampaj(lista);
    Ukloni(lista);
    Odstampaj(lista);
    Dodaj(lista, 3);
    Dodaj(lista, 2);
    Odstampaj(lista);

    OslobodiMemoriju(lista);

    return 0;
}

Dakle, kada na listi imam samo jedan element i pokušam da ga uklonim, pa da kada odštampam listu mi piše da je prazna, to ne uspevam. Sve ostalo je u redu.

[voodoo_]

Isti problem kao što si imao u prethodnom slučaju.

    if(e->sledeci==NULL)
    {
        free(e);
        e = NULL;   // Ovo neće proći
        return;
    }

Free će osloboditi taj prvi element ali će pointer nastaviti da pokazuje na taj blok memorije, tako da moraš ručno da ga setuješ na NULL. Međutim, setuješ ga preko lokalne kopije "e", a kao što znamo, izmene nad lokalnim kopijama se ne vide van funkcije tako da će argument iskopiran kao "e" i dalje sadržati neku memorijsku lokaciju, pa će nastati problemi.


Isto tako, u funkciji "Odstampaj" lista je prazna kada je e == NULL, a ne kada je e->sledeci == NULL.

[NEWSWEETTOFFEE]

voodoo_ kaže:

Isto tako, u funkciji "Odstampaj" lista je prazna kada je e == NULL, a ne kada je e->sledeci == NULL.

To sam uradio namerno, da kada dođe do zadnjeg ispiše i '-Kraj liste-'. Mislim da bih inače stavio još jednu petlju. Što se tiče, problema, znači treba da bude:

if(e->sledeci==NULL)
{
    free(e);
    lista=NULL;
    return;
}

Sad sam proverio i ovo radi. Kombinaciju:

free(e);
e=NULL;

nisam ispitivao. Dakle, 'free(e)' oslobađa alociranu memoriju, a 'lista=NULL', naređuje da je 'lista' prazna. Da, promenio sam i funkciju 'Odstampaj' odmah posle postovanja cele funkcije. Nova funkcija je dobra, ali nisam ispitivao "dobitnu" naredbu zajedno sa njom. Greške na sve strane!