Pomoc oko stabla iz C-u

Pomoc oko stabla iz C-u 17.09.2011. u 03:59 · pre 184 meseca #1

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 :)

Re: Pomoc oko stabla iz C-u 17.09.2011. u 10:04 · pre 184 meseca #2

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...

Potpis

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.

Re: Pomoc oko stabla iz C-u 17.09.2011. u 10:31 · pre 184 meseca #3

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.

Re: Pomoc oko stabla iz C-u 17.09.2011. u 11:17 · pre 184 meseca #4

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

Potpis

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.

Re: Pomoc oko stabla iz C-u 17.09.2011. u 13:03 · pre 184 meseca #5

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.

Re: Pomoc oko stabla iz C-u 17.09.2011. u 13:12 · pre 184 meseca #6

Pa i ispisace ti samo jednom....

Potpis

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.

Re: Pomoc oko stabla iz C-u 17.09.2011. u 13:19 · pre 184 meseca #7

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".

Re: Pomoc oko stabla iz C-u 17.09.2011. u 13:54 · pre 184 meseca #8

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...

Potpis

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.

Re: Pomoc oko stabla iz C-u 17.09.2011. u 14:40 · pre 184 meseca #9

Hvala ,i ja pokusavam da resim,medjutim nikako da nadjem resenje za ovo...

Re: Pomoc oko stabla iz C-u 17.09.2011. u 20:49 · pre 184 meseca #10

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.

Re: Pomoc oko stabla iz C-u 18.09.2011. u 01:04 · pre 184 meseca #11

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....

Forum kao aplikacija na telefonu

Srodne teme