2.domaća zadaća
Select messages from
 # through # FAQ
[/[Print]\]
Idite na Prethodno  1, 2, 3, 4, 5, 6, 7, 8  Sljedeće  :| |:
Forum@DeGiorgi -> Strukture podataka i algoritmi
#61:  Autor/ica: yellow submarine,  PostPostano: 23:36 pet, 13. 1. 2012
    —
@ jabuka

Pogledaj slajdove iz "Vježbe - Poglavlje 4: Skupovi (samo prioritetni red - zadnji zadatak)" na stranicama kolegija, tamo imaš prilično dobar hint. Very Happy
#62:  Autor/ica: Buki,  PostPostano: 20:48 ned, 15. 1. 2012
    —
imam u zadatku implementaciju rjecnika preko otvorene hash tablice i sad kad sam to napisala, build log mi ne javlja nikakve greske niti upozorenja, ali program prestane raditi cim ga pokrenem, prije ikakvog unosa pa molim ako netko vidi u cemu je problem da se javi Smile

ovo je kod:
Kod:
void MAKE_NULL (DICTIONARY *A){
    int i;
    for (i=0; i<B; i++) (*A)[i] = NULL;
}

int MEMBER(char x[], DICTIONARY A){
    celltype *current;
    current = A[h(x)];                     

while (current != NULL){
    if (strcmp(current->element, x)==0) return 1;
            else current = current->next;
    }
return 0;                                   
}

void INSERT(char x[], DICTIONARY *A){
    celltype *temp;
    temp = (*A)[h(x)];

    (*A)[h(x)] = (celltype*)malloc(sizeof(celltype));
    strcpy((*A)[h(x)]->element, x);
    (*A)[h(x)]->next = temp;

return;
}

void DELETE(char x[], DICTIONARY *A){
    celltype *current, *temp;

if ( (*A)[h(x)] != NULL) {

if (strcmp((*A)[h(x)]->element,x)==0) {
        temp = (*A)[h(x)];
        (*A)[h(x)] = (*A)[h(x)]->next;
        free(temp);
}else{                                     
        current = (*A)[h(x)];
while (current->next != NULL)
    if (strcmp(current->next->element, x)==0) {
            temp = current->next;
            current->next = current->next->next;
            free(temp);
            return;
        }else
            current = current->next;
    }
    }
}
#63:  Autor/ica: kkarlo,  PostPostano: 21:14 ned, 15. 1. 2012
    —
Buki (napisa):
imam u zadatku implementaciju rjecnika preko otvorene hash tablice i sad kad sam to napisala, build log mi ne javlja nikakve greske niti upozorenja, ali program prestane raditi cim ga pokrenem, prije ikakvog unosa pa molim ako netko vidi u cemu je problem da se javi Smile

ovo je kod:
Kod:
void MAKE_NULL (DICTIONARY *A){
    int i;
    for (i=0; i<B; i++) (*A)[i] = NULL;
}

int MEMBER(char x[], DICTIONARY A){
    celltype *current;
    current = A[h(x)];                     

while (current != NULL){
    if (strcmp(current->element, x)==0) return 1;
            else current = current->next;
    }
return 0;                                   
}

void INSERT(char x[], DICTIONARY *A){
    celltype *temp;
    temp = (*A)[h(x)];

    (*A)[h(x)] = (celltype*)malloc(sizeof(celltype));
    strcpy((*A)[h(x)]->element, x);
    (*A)[h(x)]->next = temp;

return;
}

void DELETE(char x[], DICTIONARY *A){
    celltype *current, *temp;

if ( (*A)[h(x)] != NULL) {

if (strcmp((*A)[h(x)]->element,x)==0) {
        temp = (*A)[h(x)];
        (*A)[h(x)] = (*A)[h(x)]->next;
        free(temp);
}else{                                     
        current = (*A)[h(x)];
while (current->next != NULL)
    if (strcmp(current->next->element, x)==0) {
            temp = current->next;
            current->next = current->next->next;
            free(temp);
            return;
        }else
            current = current->next;
    }
    }
}

A gdje ti je main i to ucitavanje koje se ne dogodi?
Wink
Nisam siguran isto da li bi u MAKE_NULL trebala radit i alokaciju, ili ces to u mainu...iako mislim da bi to trebala u MAKE_NULL. Mislim radis ti kasnije alokaciju kad ubacujes element, ali ako sam dobro shvatio to bi trebali bit double pointeri, te kad u MAKE_NULL staviš (*A)[i] = NULL; to nemože radit, jer nisi alocirala tu memoriju...
#64:  Autor/ica: Buki,  PostPostano: 22:18 ned, 15. 1. 2012
    —
aha, kuzim otprilike, sad sam izmjenila make_null da mi izgleda ovako

Kod:
void MAKE_NULL (DICTIONARY *A){
    int i;
    for (i=0; i<B; i++){ (*A)[i] = (celltype*)malloc(sizeof(celltype));
                         (*A)[i] = NULL;
                        }
return;
}


i sad mi se vise ne rusi kad ga pokrenem vec se jednostavno nista ne dogada, a mogu pisat normalno u onom crnom prozoru

ovo mi je prvi dio main-a, dalje je sve vezano za konkretan zadatak:

Kod:
int main (void){
DICTIONARY A;
char naredba[30], rijec[30];

MAKE_NULL(&A);

INSERT("auto", &A);
INSERT("break", &A);
INSERT("case", &A);
INSERT("char", &A);
INSERT("const", &A);


EDIT: puno ti hvala, sad mi radi normalno, ali samo ako mi je B<5, imas ideju kako da to ispravim?
#65:  Autor/ica: kkarlo,  PostPostano: 22:46 ned, 15. 1. 2012
    —
Buki (napisa):
aha, kuzim otprilike, sad sam izmjenila make_null da mi izgleda ovako

Kod:
void MAKE_NULL (DICTIONARY *A){
    int i;
    for (i=0; i<B; i++){ (*A)[i] = (celltype*)malloc(sizeof(celltype));
                         (*A)[i] = NULL;
                        }
return;
}


i sad mi se vise ne rusi kad ga pokrenem vec se jednostavno nista ne dogada, a mogu pisat normalno u onom crnom prozoru

ovo mi je prvi dio main-a, dalje je sve vezano za konkretan zadatak:

Kod:
int main (void){
DICTIONARY A;
char naredba[30], rijec[30];

MAKE_NULL(&A);

INSERT("auto", &A);
INSERT("break", &A);
INSERT("case", &A);
INSERT("char", &A);
INSERT("const", &A);


EDIT: puno ti hvala, sad mi radi normalno, ali samo ako mi je B<5, imas ideju kako da to ispravim?

Mislim da bi ti dobar MAKE_NULL izgledao otprilike ovako:
{
int i;
(*A)=(DICTIONARY*)malloc(B*sizeof(DICTIONARY));
for (i=0; i<B; i++){ (*A)[i] = (celltype*)malloc(sizeof(celltype));
(*A)[i] = NULL;
}
}
To je onak na prvu, ak nije to, budem sutra navecer pogledao malo detaljnije, nemogu sada...
Naravno ako ti netko drugi vec ne pomogne...
Mislim da bi trebala imat polje[B] a svaki član tog polja je pointer. Prema tome prvo moras alocirat polje od B elemenata, a potom za svaki clan dodatno...
Valjda...
#66:  Autor/ica: Buki,  PostPostano: 23:01 ned, 15. 1. 2012
    —
Hvala, hvala, hvala Very Happy sad radi Laughing
#67:  Autor/ica: butterfly,  PostPostano: 17:44 uto, 17. 1. 2012
    —
Da li ima netko ideju kako učitati stablo (npr. sa tipkovnice)?
#68:  Autor/ica: pecina, Lokacija: Happily traveling through space since 1986! PostPostano: 10:35 sri, 18. 1. 2012
    —
Unesi prvo oznaku korijena i koristi MAKE_ROOT.

Zatim učitaj oznaku djeteta.
Zatim učitaj oznaku njegovog djeteta.
Na STOP se vraćaš natrag.

Dakle rekurzivno za svaki čvor unosiš djecu, ali prvo ideš po dubini.

Možeš i ovako:
Unesi korijen
pozovi foo(korijen)
foo(node i)
unesi broj djece od i
for i = 1 to n
unesi i-to dijete
for i = 1 to n
foo(i-to dijete)


Prvi ti je unos DFS, drugi BFS (google it).
#69:  Autor/ica: butterfly,  PostPostano: 11:38 sri, 18. 1. 2012
    —
Hvala Very Happy
#70:  Autor/ica: travana,  PostPostano: 1:17 čet, 19. 1. 2012
    —
imam problema s funkcijom delete_max za hrpu, nikako ne vidim u cemu je greska, pogotovo jer je prakticki prepisana iz skripte, a na njoj mi se program rusi Rolling Eyes
pa ako vidite gresku slobodno ukazite na nju Very Happy


Kod:

typedef struct {
    int last;
    elementtype labels[MAXLENGHT];
} HEAP;


elementtype DELETE_MAX (HEAP *H) {
    int i, j;
    elementtype max;

    if (H->last < 0) {
        error("Hrpa je prazna!");

}
    else {
        max = H->labels[0]; //u korijenu je najveci element
        H->labels[0] = H->labels[H->last];
        (H->last)--;
        i = 0;
        while (i <= (H->last+1)/2-1) {
            if ((2*i + 1 == H->last) || (H->labels[2*i + 1] > H->labels[2*i + 2]))
                j = 2*i + 1;
            else
                j = 2*i + 2;
            if (H->labels[i] < H->labels[j]) {
                swap(H->labels[i], H->labels[j]);
                i = j;
            }
            else
                return max;
        }
        return max;
    }
}
#71:  Autor/ica: mini,  PostPostano: 10:04 čet, 19. 1. 2012
    —
michelangelo (napisa):
može neko pojašnjenje ovako zadane strukture nisam sigurna s čime tu zapravo raspolažem... ovaj labels mi nije jasan, što mi tu zapravo ulazi???

Neka je uredjeno stablo prikazano pomoću slijedeće strukture podataka:

typedef struct {
LIST header[maxnodes] ;
labeltype labels[maxnodes] ;
node root;
} TREE;

Uz ovakvu reprezentaciju implementirajte a.t.p. TREE. Pretpostavljamo da je node tipa int, labeltype je podatak tipa char, dok je a.t.p. LIST implementiran pomoću pointera, a header[i] predstavlja listu djece čvora i.


trebalo bi i meni par odgovora. kako uopće implementirati listu. može li mi netko dati primjer za bar jednu funkciju? malo me to sve skupa zbunilo Ehm?
#72:  Autor/ica: pecina, Lokacija: Happily traveling through space since 1986! PostPostano: 10:13 čet, 19. 1. 2012
    —
mini (napisa):
michelangelo (napisa):
može neko pojašnjenje ovako zadane strukture nisam sigurna s čime tu zapravo raspolažem... ovaj labels mi nije jasan, što mi tu zapravo ulazi???

Neka je uredjeno stablo prikazano pomoću slijedeće strukture podataka:

typedef struct {
LIST header[maxnodes] ;
labeltype labels[maxnodes] ;
node root;
} TREE;

Uz ovakvu reprezentaciju implementirajte a.t.p. TREE. Pretpostavljamo da je node tipa int, labeltype je podatak tipa char, dok je a.t.p. LIST implementiran pomoću pointera, a header predstavlja listu djece čvora i.


trebalo bi i meni par odgovora. kako uopće implementirati listu. može li mi netko dati primjer za bar jednu funkciju? malo me to sve skupa zbunilo Ehm?


Piše ti: LIST implementirajte pomoću pointera.
Kod:
typedef struct tag_celltype
{
    struct tag_celltype *next;
    node childIndex;
} celltype;


Dakle, svi čvorovi stabla su zapisani u linearnom polju. root ti je 0 tj. na 0. mjestu se nalazi oznaka korijena u polju labels

labels[root] - oznaka korijena
header[root] - lista nodeova djece, npr [1, 2, 7]

Sad, ako želiš doći do djece od nekog node-a, samo pogledaš u header polje na njegovom mjestu. Dobit ćeš listu [i]novih indeksa u oba polja labels i header koji ti definiraju tim redom oznaku tog čvora i popis djece.

Jasnije?
#73:  Autor/ica: pajopatak,  PostPostano: 17:45 pet, 20. 1. 2012
    —
može mala pomoć,imam implementaciju SET-a pomoću vezane liste, to sam sve napravila i sad kao zadani elementtype mi je char i to nikako nemogu ukomponirat u f-je,stalno mi grešku javlja,evo samo dio koda, pa ako netko zna u čemu je problem:

Kod:
typedef struct cell_tag {
char element[100];
struct cell_tag *next;
} celltype;

typedef celltype *SET;

void MAKE_NULL(SET *A){
*A = (celltype*) malloc(sizeof(celltype));
(*A)->next = NULL;
}

void INSERT(char x[], SET *A){
celltype *novi, *prethodni, *trenutni;
prethodni = *A;
trenutni = prethodni->next;
while(trenutni != NULL && strcmp(trenutni->element,x)<0){
prethodni = trenutni;
trenutni = prethodni->next;
}
if (trenutni != NULL && strcmp(trenutni->element,x)==0)
return;
else{
novi = (celltype*) malloc(sizeof(celltype));
strcpy(novi->element,x);
novi->next=trenutni;
prethodni->next = novi;
}
}
#74:  Autor/ica: satja,  PostPostano: 19:03 pet, 20. 1. 2012
    —
pajopatak (napisa):
može mala pomoć,imam implementaciju SET-a pomoću vezane liste, to sam sve napravila i sad kao zadani elementtype mi je char i to nikako nemogu ukomponirat u f-je,stalno mi grešku javlja,evo samo dio koda, pa ako netko zna u čemu je problem:

Kod:
typedef struct cell_tag {
char element[100];
struct cell_tag *next;
} celltype;

typedef celltype *SET;

void MAKE_NULL(SET *A){
*A = (celltype*) malloc(sizeof(celltype));
(*A)->next = NULL;
}

void INSERT(char x[], SET *A){
celltype *novi, *prethodni, *trenutni;
prethodni = *A;
trenutni = prethodni->next;
while(trenutni != NULL && strcmp(trenutni->element,x)<0){
prethodni = trenutni;
trenutni = prethodni->next;
}
if (trenutni != NULL && strcmp(trenutni->element,x)==0)
return;
else{
novi = (celltype*) malloc(sizeof(celltype));
strcpy(novi->element,x);
novi->next=trenutni;
prethodni->next = novi;
}
}


Kakvu ti grešku javlja? Meni se tvoj kod, uz
Kod:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
normalno kompajlira.
#75:  Autor/ica: viki,  PostPostano: 19:09 pet, 20. 1. 2012
    —
da li ima netko implementaciju a.t.p. TREE pomoću polja na osnovi veze "čvor → (roditelj, (prvo dijete, idući brat))" ? Smile
#76:  Autor/ica: pupi,  PostPostano: 19:35 pet, 20. 1. 2012
    —
Zadatak glasi ovako :

Sortirajte zadanu listu pomoću binarnog stabla traženja uzlazno i silazno koristeći isto binarno stablo traženja. Pretpostavimo da lista sadrži elemente tipa char. Binarno stablo traženja je prikazano pomoću polja, a implementaciju liste odaberite sami. Ne trebate implementirati sve funkcije iz atp LIST, nego samo one koje su vam potrebne u zadatku. Na binarnom stablu implementirajte sve operacije iz atp DICTIONARY osim DELETE.


Ulazni podaci: niz znakova koji čine elemente liste koje treba sortirati; ubacujte ih u BST točno redom kojim su navedeni.
Izlazni podaci: 3 retka: u prvom su elementi uzlazno sortirane liste, u drugom silazno sortirane, a u trećem je (za kontrolu) PREORDER obilazak konstruiranog stabla.
Na primjer, za ulazne podatke:
MIRKO
treba ispisati:
uzlazno sortirana lista: IKMOR
silazno sortirana lista: ROMKI
preorder: MIKRO


Funkcija insert mi uđe u beskonačnu petlju :


Kod:
void INSERT(char x, BTREE *T)
{
   int i;
   if (T->labels[0] == PRAZNO)
   {
      T->labels[0] = x;
      return;
   }
   else if (x < T->labels[0]) {
      i = 1;
      while(1)
      {
         if (T->labels[i] == PRAZNO) { T->labels[i] = x; break; }
         else if (x < T->labels[i]) i = 2*i+1;
         else if (x > T->labels[i]) i = 2*i+2;
      }
      return;
   }
   else if(x > T->labels[0]) {
      i = 2;
      while(1)
      {
         if (T->labels[i] == PRAZNO)  { T->labels[i] = x; break; }
         else if (x < T->labels[i]) i = 2*i+1;
         else if (x > T->labels[i]) i = 2*i+2;
      }
      return;
   }
}


Jel može pomoć u pronalasku greške? Smile
#77:  Autor/ica: satja,  PostPostano: 19:45 pet, 20. 1. 2012
    —
pupi (napisa):
Zadatak glasi ovako :

Sortirajte zadanu listu pomoću binarnog stabla traženja uzlazno i silazno koristeći isto binarno stablo traženja. Pretpostavimo da lista sadrži elemente tipa char. Binarno stablo traženja je prikazano pomoću polja, a implementaciju liste odaberite sami. Ne trebate implementirati sve funkcije iz atp LIST, nego samo one koje su vam potrebne u zadatku. Na binarnom stablu implementirajte sve operacije iz atp DICTIONARY osim DELETE.


Ulazni podaci: niz znakova koji čine elemente liste koje treba sortirati; ubacujte ih u BST točno redom kojim su navedeni.
Izlazni podaci: 3 retka: u prvom su elementi uzlazno sortirane liste, u drugom silazno sortirane, a u trećem je (za kontrolu) PREORDER obilazak konstruiranog stabla.
Na primjer, za ulazne podatke:
MIRKO
treba ispisati:
uzlazno sortirana lista: IKMOR
silazno sortirana lista: ROMKI
preorder: MIKRO


Funkcija insert mi uđe u beskonačnu petlju :


Kod:
void INSERT(char x, BTREE *T)
{
   int i;
   if (T->labels[0] == PRAZNO)
   {
      T->labels[0] = x;
      return;
   }
   else if (x < T->labels[0]) {
      i = 1;
      while(1)
      {
         if (T->labels[i] == PRAZNO) { T->labels[i] = x; break; }
         else if (x < T->labels[i]) i = 2*i+1;
         else if (x > T->labels[i]) i = 2*i+2;
      }
      return;
   }
   else if(x > T->labels[0]) {
      i = 2;
      while(1)
      {
         if (T->labels[i] == PRAZNO)  { T->labels[i] = x; break; }
         else if (x < T->labels[i]) i = 2*i+1;
         else if (x > T->labels[i]) i = 2*i+2;
      }
      return;
   }
}


Jel može pomoć u pronalasku greške? Smile


Čini mi se da, ako se u nekom trenutku petlje dogodi da je x == T→labels[i], brojač i se neće promijeniti i ostat ćeš u beskonačnoj petlji.
#78:  Autor/ica: pupi,  PostPostano: 19:59 pet, 20. 1. 2012
    —
Hvala, tu je bila greška Smile
#79:  Autor/ica: pajopatak,  PostPostano: 20:11 pet, 20. 1. 2012
    —
Implementirajte a.t.p. SET pomoću sortirane vezane liste (veze u listi su uspostavljene pomoću pointera) i pretpostavku da skupovi sadrže podatke tipa char. Nadopunite skupovne operacije iz implementacije sa simetričnom razlikom, tj. napišite dodatni potprogram koji računa simetričnu razliku skupova.


Ulazni podaci: dva stringa čiji znakovi predstavljaju elemente dvaju skupova A i B.
Izlazni podaci: 5 stringova, svaki u jednom redu – unija, presjek, razlika A∖ B, simetrična razlika; zadnji string je DA ako je A⊆ B, a NE u protivnom.
Na primjer, za ulazne podatke:
MIRKO
SLAVKO
treba ispisati:
unija: AIKLMORSV
presjek: KO
razlika: IMR
sim. razlika: AILMRSV
podskup: NE



Ovo je zadatak,ja sad ne razumijem dali ja trebam napravit impl.pomoću vezane liste za slova ili stringove,i kad npr.imam INSERT dali unosim samo slovo u skup ili string?
#80:  Autor/ica: pupi,  PostPostano: 20:25 pet, 20. 1. 2012
    —
Kako napraviti inorder za BST koje je prikazano preko polja ? :S

I kad napravim uzlazni sort kako koresteći isto BST silazno sortitrati?
Forum@DeGiorgi -> Strukture podataka i algoritmi


output generated using printer-friendly topic mod. Vremenska zona: GMT + 01:00.

Idite na Prethodno  1, 2, 3, 4, 5, 6, 7, 8  Sljedeće  :| |:
Stranica 4 / 8.

Powered by phpBB © 2001,2002 phpBB Group
Theme created by Vjacheslav Trushkin