Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Pomoc oko stabla iz C-u

[es] :: C/C++ programiranje :: C/C++ za početnike :: Pomoc oko stabla iz C-u

[ Pregleda: 2570 | Odgovora: 10 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Savilence85
Sava Savanovic

Član broj: 72692
Poruke: 20
*.dynamic.isp.telekom.rs.



Profil

icon Pomoc oko stabla iz C-u17.09.2011. u 02:59 - pre 152 meseci
Pozdrav,

Vezbam zadatke sa stablima u programskom jeziku C,medjutim dva problema mi zadaju muku,pa sam resio da pitam ako ovde mozda neko zna.

Prvi problem je ,na primer u stablo ucitamo neke cvorove,koji imaju dva polja char ime[100]; char prezime[100];

Ako ubacimo par novih covora u stablo sa sledecim podacima :

Petar Petrovic
Marko Petrovic
Mika Mikic
Zika Mikic
Ana Zivic


kako napisati funkciju koja prolazi kroz stablo i stampa samo prezimena,i to samo JEDNOM.
znaci na izlaz da izadje :

Petrovic
Mikic
Zivic


A drugi problem je,kako da pored tih imena napise pored njih koliko su se puta pojavljivala :

Petrovic 2
Mikic 2
Zivic 1

Unapred hvala na pomoci :)
 
Odgovor na temu

Sonec

Član broj: 284879
Poruke: 892



+332 Profil

icon Re: Pomoc oko stabla iz C-u17.09.2011. u 09:04 - pre 152 meseci
Evo resenja za 2 zadatak, pa ces lako naci resenje sad za prvi :)

Samo, s obzirom da je ovo stablo, ono mora da se sortira po nekom redosledu, tako da je ovo stablo sortirano po prezimenu, a valjda ako hoces kako unosis tako i da ispisuje, onda se koriste liste, a mozda i ne, davno sam ovo radio (ima 3 meseca od ispita :))

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

#define MAX 40

typedef struct cvor {
  char ime[MAX];
  char prezime[MAX];
  int pojavljivanja;
  struct cvor *l, *d;
} CVOR;

/* Funkcija kreira novi cvor koji sadrzi datu rec. */
CVOR* napravi_cvor(char a[],char b[]){
  CVOR *novi = (CVOR*)malloc(sizeof(CVOR));
  if (novi == NULL){
    fprintf(stderr,"Neuspela alokacija.\n");
    exit(1);
  }
  strcpy(novi->ime, a);
  strcpy(novi->prezime,b);
  novi->pojavljivanja = 1;
  novi->l = NULL;
  novi->d = NULL;

  return novi;
}

/* Funkcija ubacuje rec u drvo po prezimenu. */
CVOR* ubaci_u_drvo(CVOR *drvo, char a[],char b[]){
  if (drvo == NULL)
    return napravi_cvor(a,b);

  if (strcmp(b, drvo->prezime) < 0)
    drvo->l = ubaci_u_drvo(drvo->l,a,b);
  else if (strcmp(b, drvo->prezime) > 0)
    drvo->d = ubaci_u_drvo(drvo->d,a,b);
  // Prezime se vec nalazi u drvetu pa se povecava broj pojavljivanja
  else
    drvo->pojavljivanja++;

  return drvo;
}

/* Funkcija ispisuje drvo na ekran. */
void ispisi_drvo(CVOR *drvo){
  if (drvo != NULL){
    ispisi_drvo(drvo->l);
    printf("%s : %d \n",drvo->prezime, drvo->pojavljivanja);
    ispisi_drvo(drvo->d);
  }
}

/* Funkcija dealocira dinamicki alocirano drvo. */
void obrisi_drvo(CVOR *drvo){
  if (drvo != NULL){
    obrisi_drvo(drvo->l);
    obrisi_drvo(drvo->d);
    free(drvo);
  }
}

int main(int argc, char **argv){
  CVOR *drvo = NULL;
  char a[MAX];
  char b[MAX];

  while (scanf("%s%s",a,b) == 2){
    drvo = ubaci_u_drvo(drvo,a,b);
  }

  ispisi_drvo(drvo);
  putchar('\n');

  obrisi_drvo(drvo);

  return 0;
}


EDIT: sad primetih da su charovi ograniceni na 100, samo izmeni to u kodu...
Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.
 
Odgovor na temu

Savilence85
Sava Savanovic

Član broj: 72692
Poruke: 20
*.dynamic.isp.telekom.rs.



Profil

icon Re: Pomoc oko stabla iz C-u17.09.2011. u 09:31 - pre 152 meseci
Hvala za pomoc,mislim da mi je sada sinulo kako treba da resim :)


EDIT : Ustvari ipak ne znam kako bih resio to da stampa samo prezimena samo jednom :((,ako neko zna,bio bih zahvalan da pomogne.

[Ovu poruku je menjao Savilence85 dana 17.09.2011. u 10:46 GMT+1]
 
Odgovor na temu

Sonec

Član broj: 284879
Poruke: 892



+332 Profil

icon Re: Pomoc oko stabla iz C-u17.09.2011. u 10:17 - pre 152 meseci
E bre, kako ne znas :)

Pa samo umesto
Code:
 printf("%s : %d \n",drvo->prezime, drvo->pojavljivanja);

stavi
Code:
 printf("%s\n",drvo->prezime);

i resena stvar
Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.
 
Odgovor na temu

Savilence85
Sava Savanovic

Član broj: 72692
Poruke: 20
*.dynamic.isp.telekom.rs.



Profil

icon Re: Pomoc oko stabla iz C-u17.09.2011. u 12:03 - pre 152 meseci
Ma naravno da to znam,nego ne znam kako da napisem funkciju koja ce da ispisuje samo prezimena samo JEDNOM ?

Fora je sto ova tvoja funkcija za ubacivanje imena i prezimena u stablo,ne ubacuje sva prezimena koja se vise puta pojave,vec samo ubaci jednom.
Tako da ako ja unesem Petar Petrovic
Milos Petrovic u drvetu ce mi samo biti Petar,a meni treba da se ubace oba.

Meni treba da normalno ubacim sve podatke u drvo,pa tek onda sa nekom funcijom da ispisem ono sto mi treba iz njega,a to je da ispise svako prezime pojednom.

[Ovu poruku je menjao Savilence85 dana 17.09.2011. u 13:17 GMT+1]
 
Odgovor na temu

Sonec

Član broj: 284879
Poruke: 892



+332 Profil

icon Re: Pomoc oko stabla iz C-u17.09.2011. u 12:12 - pre 152 meseci
Pa i ispisace ti samo jednom....
Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.
 
Odgovor na temu

Savilence85
Sava Savanovic

Član broj: 72692
Poruke: 20
*.dynamic.isp.telekom.rs.



Profil

icon Re: Pomoc oko stabla iz C-u17.09.2011. u 12:19 - pre 152 meseci
Fora je sto ova tvoja funkcija za ubacivanje imena i prezimena u stablo,ne ubacuje sva prezimena koja se vise puta pojave,vec samo ubaci jednom.

Tako da ako ja unesem

Petar Petrovic
Milos Petrovic

u drvetu ce mi samo biti Petar,a meni treba da se ubace oba.

Pa tek onda sa nekom funcijom da ispisem ono sto mi treba iz njega,a to je da ispise u ovom slucaju samo jednom PEtrovic,ali u drvetu i dalje da budu obe "osobe".
 
Odgovor na temu

Sonec

Član broj: 284879
Poruke: 892



+332 Profil

icon Re: Pomoc oko stabla iz C-u17.09.2011. u 12:54 - pre 152 meseci
Evo, izmenjen je malo kod, al zadatak jos nije resen
Code:
/* Funkcija ubacuje rec u drvo po prezimenu. */
CVOR* ubaci_u_drvo(CVOR *drvo, char a[],char b[]){
  if (drvo == NULL)
    return napravi_cvor(a,b);

  if (strcmp(b, drvo->prezime) < 0)
    drvo->l = ubaci_u_drvo(drvo->l,a,b);
  else if (strcmp(b, drvo->prezime) > 0)
    drvo->d = ubaci_u_drvo(drvo->d,a,b); //ako je prezime isto, uporedjujemo ime !!!
  else if(strcmp(a,drvo->ime) < 0)
     drvo->l = ubaci_u_drvo(drvo->l,a,b);
  else if(strcmp(a,drvo->ime) > 0)
     drvo->d = ubaci_u_drvo(drvo->d,a,b);
  else
     drvo->pojavljivanja++;
  return drvo;
}

/* Funkcija ispisuje drvo na ekran. */
void ispisi_drvo(CVOR *drvo){
  if (drvo != NULL){
    ispisi_drvo(drvo->l);
    printf("%s %s : %d \n",drvo->ime, drvo->prezime, drvo->pojavljivanja);
    ispisi_drvo(drvo->d);
  }
}


Sad ti se ne gube imena, i ostaje nam jos da prebrojimo ista prezimena, moram malo da promislim, pa cu ti javiti vec...
Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.
 
Odgovor na temu

Savilence85
Sava Savanovic

Član broj: 72692
Poruke: 20
*.dynamic.isp.telekom.rs.



Profil

icon Re: Pomoc oko stabla iz C-u17.09.2011. u 13:40 - pre 152 meseci
Hvala ,i ja pokusavam da resim,medjutim nikako da nadjem resenje za ovo...
 
Odgovor na temu

Picsel
Beograd

Član broj: 39817
Poruke: 440
*.dynamic.isp.telekom.rs.



+7 Profil

icon Re: Pomoc oko stabla iz C-u17.09.2011. u 19:49 - pre 152 meseci
Evo ideja. Na trenutnom cvoru ispisi prezime deteta ako se njegovo prezime razlikuje od trenutnog cvora. Koren stabla je specijalan slucaj posto nema roditelja, tako da njega ispisi svakako (pre ili posle obilaska stabla).
Ovo ce da radi korektno jer na nivoima izmedju dva cvora u stablu koja imaju isto prezime ne moze da bude neki cvor koji ima drugacije prezime, tako da ces ispisati prezime samo onog cvora koji je najblizi korenu.

Uz malu modifikaciju mozes lako i da prebrojis koliko ima cvorova sa istim prezimenom. Mozes da prilikom ubacivanja za svaki cvor povecas broj ponavljanja prezimena ako su prezimena ista, pa kasnije samo ispisujes to (uz algoritam iz pasusa iznad).
Postoji i druga opcija, gde broj ponavljanja racunas direktno u obilasku. Prvo obilazis oba deteta, pa tek onda eventualno ispisujes prezimena dece uz broj ponavljanja. Funkcija obilaska bi trebala da ima povratnu vrednost koja predstavlja broj cvorova u podstablu sa istim prezimenom kao i taj cvor. Ako su prezimena trenutnog cvora i deteta identicna, na vrednost koju vracas dodajes 1 + vrednost koju si dobio nakon obilaska tog deteta. Ako su prezimena razlicita, onda jednostavno ispisujes prezime deteta i njegovu povratnu vrednost + 1.
 
Odgovor na temu

Savilence85
Sava Savanovic

Član broj: 72692
Poruke: 20
*.dynamic.isp.telekom.rs.



Profil

icon Re: Pomoc oko stabla iz C-u18.09.2011. u 00:04 - pre 152 meseci
Resio sam problem da mi se prezimena pojave samo jednom.

U strukturu sam doda polje int obidjeno;

I jednostavno kada if (strcmp(b, drvo->prezime) == 0) sto znaci da to prezime vec postoji,ja mu kazem obidjeno =1;
Posle sam samo isprintovao ona polja koja imaju obidjeno =0;

Sada mi je jedino problem,da to moje uskladim sa tim da pored prezimena pise i broj pojavljianja..... tu nastaju neke komplikacije....
 
Odgovor na temu

[es] :: C/C++ programiranje :: C/C++ za početnike :: Pomoc oko stabla iz C-u

[ Pregleda: 2570 | Odgovora: 10 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.