Prethodna tema :: Sljedeća tema |
Autor/ica |
Poruka |
minnie m. Forumaš(ica)
Pridružen/a: 06. 10. 2011. (20:34:28) Postovi: (16)16
|
|
[Vrh] |
|
Buki Forumaš(ica)
Pridružen/a: 17. 10. 2010. (20:15:17) Postovi: (56)16
|
|
[Vrh] |
|
Tomislav Forumaš(ica)
Pridružen/a: 04. 10. 2010. (20:18:25) Postovi: (181)16
Spol:
|
|
[Vrh] |
|
Cobs Forumaš(ica)
Pridružen/a: 21. 01. 2008. (13:32:15) Postovi: (206)16
Spol:
Lokacija: Geto
|
Postano: 16:52 sri, 9. 11. 2011 Naslov: |
|
|
[quote="Buki"]pitanje u vezi funkcije DEQUEUE kod implementacije reda pomocu pointera:
[code:1]
void DEQUEUE (QUEUE *Q ptr) {
celltype *temp;
if (EMPTY(*Q ptr)) error("queue is empty");
else {
temp = Q ptr->front;
Q ptr->front = Q ptr->front->next;
free(temp);
}
}
[/code:1]
cemu sluzi ovaj temp? jel ne bi moglo samo biti:
[code:1]
void DEQUEUE (QUEUE *Q ptr) {
celltype *temp;
if (EMPTY(*Q ptr)) error("queue is empty");
else {
Q ptr->front = Q ptr->front->next;
free(Q ptr->front);
}
}
[/code:1][/quote]
nije jer bi u drugom slučaju pobrisao novi prvi element u redu... ajd jedan primjer:
recimo da imaš red od 5 elementa i da su poredani kako ih pišem: 1,2,3,4,5
( znači prvi element koji ide van je 1 )
i neka adrese na kojima su ti elementi su redom: 234, 238, 242, 246, 250
u prvom primjeru ( onom točnom ) stavio bi:
temp = 234;
red->prvi_element = 238;
oslobodi_alociranu_memoriju_na_adresi( temp ); // 234
i sad bi red zgledo: 2,3,4,5 ( sa adresama 238,242,246,250 )
u drugom primjeru bi stavio:
red->prvi_element = 238;
oslobodi_alociranu_memoriju_na_adresi( red->prvi_element ); // 238
znači uništio si si prvi element u redu i više nemreš uopće pristupiti samom redu jer ti sad red->prvi_element pokazuje na NULL pokazivač ( taj dio memorije je oslobođen ). Znači nemreš pristupit redu + kaj si prvi element ( onaj na adresi 234 ) zanemario i ta memorija ostaje alocirana
Buki (napisa): | pitanje u vezi funkcije DEQUEUE kod implementacije reda pomocu pointera:
Kod: |
void DEQUEUE (QUEUE *Q ptr) {
celltype *temp;
if (EMPTY(*Q ptr)) error("queue is empty");
else {
temp = Q ptr->front;
Q ptr->front = Q ptr->front->next;
free(temp);
}
}
|
cemu sluzi ovaj temp? jel ne bi moglo samo biti:
Kod: |
void DEQUEUE (QUEUE *Q ptr) {
celltype *temp;
if (EMPTY(*Q ptr)) error("queue is empty");
else {
Q ptr->front = Q ptr->front->next;
free(Q ptr->front);
}
}
|
|
nije jer bi u drugom slučaju pobrisao novi prvi element u redu... ajd jedan primjer:
recimo da imaš red od 5 elementa i da su poredani kako ih pišem: 1,2,3,4,5
( znači prvi element koji ide van je 1 )
i neka adrese na kojima su ti elementi su redom: 234, 238, 242, 246, 250
u prvom primjeru ( onom točnom ) stavio bi:
temp = 234;
red→prvi_element = 238;
oslobodi_alociranu_memoriju_na_adresi( temp ); // 234
i sad bi red zgledo: 2,3,4,5 ( sa adresama 238,242,246,250 )
u drugom primjeru bi stavio:
red→prvi_element = 238;
oslobodi_alociranu_memoriju_na_adresi( red→prvi_element ); // 238
znači uništio si si prvi element u redu i više nemreš uopće pristupiti samom redu jer ti sad red→prvi_element pokazuje na NULL pokazivač ( taj dio memorije je oslobođen ). Znači nemreš pristupit redu + kaj si prvi element ( onaj na adresi 234 ) zanemario i ta memorija ostaje alocirana
|
|
[Vrh] |
|
mrma Forumaš(ica)
Pridružen/a: 15. 01. 2011. (12:28:40) Postovi: (5)16
|
|
[Vrh] |
|
Fikus Forumaš(ica)
Pridružen/a: 14. 07. 2010. (00:00:23) Postovi: (1C)16
Lokacija: Somewhere around the world
|
Postano: 20:34 sri, 9. 11. 2011 Naslov: |
|
|
Moze pomoc oko liste, ja imam implementaciju iz skripte pa me zanima di je tocno grecka
[code:1]
typedef struct _celija {
elementtype element;
struct _celija *next;
} celija;
position MAKE_NULL_L(LIST *L) {
*L = (celija*) malloc(sizeof(celija));
(*L)->next = NULL;
return *L;
}
[/code:1]
Dakle kod prvog mi ocita gresku kod elementtypea (expected specifier list before elementtype)
i kod make null a i ostalih funkcija mi kaze da u mojoj strukturi nema člana koji se zove next
i jos mi ocitava gresku za malloc, kaze :incompatibile implicit declaration of built-in function malloc
Eto to bi bilo sve sto me zanima, dakle glavno pitanje je kako to sve popravit da bi radilo, hvala :)
Moze pomoc oko liste, ja imam implementaciju iz skripte pa me zanima di je tocno grecka
Kod: |
typedef struct _celija {
elementtype element;
struct _celija *next;
} celija;
position MAKE_NULL_L(LIST *L) {
*L = (celija*) malloc(sizeof(celija));
(*L)->next = NULL;
return *L;
}
|
Dakle kod prvog mi ocita gresku kod elementtypea (expected specifier list before elementtype)
i kod make null a i ostalih funkcija mi kaze da u mojoj strukturi nema člana koji se zove next
i jos mi ocitava gresku za malloc, kaze :incompatibile implicit declaration of built-in function malloc
Eto to bi bilo sve sto me zanima, dakle glavno pitanje je kako to sve popravit da bi radilo, hvala
_________________ Pokušate li, možda nećete uspjeti, ne pokušate li, sigurno nećete.
|
|
[Vrh] |
|
pedro Forumaš(ica)
Pridružen/a: 21. 10. 2010. (14:08:21) Postovi: (19B)16
|
|
[Vrh] |
|
kikyca Forumaš(ica)
Pridružen/a: 13. 10. 2009. (18:45:07) Postovi: (32)16
Spol:
|
Postano: 21:52 sri, 9. 11. 2011 Naslov: |
|
|
Jel moze mala pomoc. U mainu mi nesto cudno dodaje na kraj polja pa zbog toga ne rade pozivi funkcija. Zadatak je:
Dvostrani red DQUEUE je lista kojoj se elementi mogu ubacivati i izbacivati na
bilo kojem kraju (no ne u sredini). Implementirajte dvostrani red pomocu polja.
Definirajte elementtype kao int.
Ulazni podaci: niz naredbi koje opisuju operacije nad poljem
(naredbe su UBACI KRAJ n, UBACI POCETAK n, IZBACI KRAJ, IZBACI POCETAK).
Izlazni podaci: za svaku naredbu ispisati sadrzaj cijelog reda
u tom trenutku (mozete ispisivati odmah nakon sto ucitate pojedinu naredbu, a ne tek nakon sto ucitate sve).
Na primjer, za ulazne podatke:
UBACI POCETAK 3
UBACI KRAJ 7
UBACI POCETAK 17
IZBACI KRAJ
IZBACI POCETAK
treba ispisati:
3
3 7
17 3 7
17 3
a ovo je moj kod
[code:1] #include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
#define MAXL 100
typedef int elementtype;
typedef struct{
elementtype elements[MAXL];
int pocetak, kraj;
} DQUEUE;
int addone(int i){
return((i+1)% MAXL);
}
void MAKE_NULL(DQUEUE *Q){
Q->pocetak=0;
Q->kraj=MAXL-1;
}
int EMPTY(DQUEUE Q){
if (Q.pocetak == addone(Q.kraj))
return 1;
else
return 0;
}
elementtype FRONT(DQUEUE Q){
if (EMPTY(Q))
printf("Red je prazan!");
else
return Q.elements[Q.pocetak];
}
void UBACI_KRAJ(elementtype x, DQUEUE *Q){
if(addone(addone(Q->kraj))==(Q->pocetak))
printf("Red je pun!");
else{
Q->kraj=addone(Q->kraj);
Q->elements[Q->kraj]=x;
}
}
void IZBACI_POCETAK(DQUEUE *Q){
if(EMPTY(*Q))
printf("Red je prazan!");
else
Q->pocetak=addone(Q->pocetak);
}
void IZBACI_KRAJ(DQUEUE *Q){
if(EMPTY(*Q))
printf("Red je prazan!\n");
else if(Q->kraj>0)
--Q->kraj;
else Q->kraj=MAXL-1;
}
void UBACI_POCETAK(elementtype x, DQUEUE *Q) {
if(addone(addone(Q->kraj))==(Q->pocetak))
printf("Red je pun!\n");
else {
Q->kraj=addone(addone(Q->kraj));
int i=Q->kraj;
while(i!=Q->pocetak) {
Q->elements[i]=Q->elements[i-1];
if(i>0) --i;
else i=MAXL-1;
}
Q->elements[Q->pocetak]=x;
}
}
int main() {
DQUEUE Q;
elementtype x;
char funkcija[MAXL], pomocni[MAXL], broj[MAXL];
int i, j, br=0, n;
MAKE_NULL(&Q);
while(1) {
i=0; j=0;
gets(funkcija);
n=strlen(funkcija);
while(i<n) {
if(funkcija[i]==' ') {
if(br==0) pomocni[i]=funkcija[i];
br++;
}
else if(isdigit(funkcija[i])) {
broj[j]=funkcija[i];
j++;
}
else pomocni[i]=funkcija[i];
i++;
}
x=atoi(broj);
if(pomocni=="UBACI POCETAK") UBACI_POCETAK(x, &Q);
else if(pomocni=="IZBACI POCETAK") IZBACI_POCETAK(&Q);
else if(pomocni=="UBACI KRAJ") UBACI_KRAJ(x, &Q);
else if(pomocni=="IZBACI KRAJ") IZBACI_KRAJ(&Q);
else break;
if(!EMPTY(Q)) {
i=Q.pocetak;
while(i!=Q.kraj) {
printf("%d ", Q.elements[i]);
addone(i);
}
printf("\n");
}
}
system("pause");
return 0;
}[/code:1]
Jel moze mala pomoc. U mainu mi nesto cudno dodaje na kraj polja pa zbog toga ne rade pozivi funkcija. Zadatak je:
Dvostrani red DQUEUE je lista kojoj se elementi mogu ubacivati i izbacivati na
bilo kojem kraju (no ne u sredini). Implementirajte dvostrani red pomocu polja.
Definirajte elementtype kao int.
Ulazni podaci: niz naredbi koje opisuju operacije nad poljem
(naredbe su UBACI KRAJ n, UBACI POCETAK n, IZBACI KRAJ, IZBACI POCETAK).
Izlazni podaci: za svaku naredbu ispisati sadrzaj cijelog reda
u tom trenutku (mozete ispisivati odmah nakon sto ucitate pojedinu naredbu, a ne tek nakon sto ucitate sve).
Na primjer, za ulazne podatke:
UBACI POCETAK 3
UBACI KRAJ 7
UBACI POCETAK 17
IZBACI KRAJ
IZBACI POCETAK
treba ispisati:
3
3 7
17 3 7
17 3
a ovo je moj kod
Kod: | #include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
#define MAXL 100
typedef int elementtype;
typedef struct{
elementtype elements[MAXL];
int pocetak, kraj;
} DQUEUE;
int addone(int i){
return((i+1)% MAXL);
}
void MAKE_NULL(DQUEUE *Q){
Q->pocetak=0;
Q->kraj=MAXL-1;
}
int EMPTY(DQUEUE Q){
if (Q.pocetak == addone(Q.kraj))
return 1;
else
return 0;
}
elementtype FRONT(DQUEUE Q){
if (EMPTY(Q))
printf("Red je prazan!");
else
return Q.elements[Q.pocetak];
}
void UBACI_KRAJ(elementtype x, DQUEUE *Q){
if(addone(addone(Q->kraj))==(Q->pocetak))
printf("Red je pun!");
else{
Q->kraj=addone(Q->kraj);
Q->elements[Q->kraj]=x;
}
}
void IZBACI_POCETAK(DQUEUE *Q){
if(EMPTY(*Q))
printf("Red je prazan!");
else
Q->pocetak=addone(Q->pocetak);
}
void IZBACI_KRAJ(DQUEUE *Q){
if(EMPTY(*Q))
printf("Red je prazan!\n");
else if(Q->kraj>0)
--Q->kraj;
else Q->kraj=MAXL-1;
}
void UBACI_POCETAK(elementtype x, DQUEUE *Q) {
if(addone(addone(Q->kraj))==(Q->pocetak))
printf("Red je pun!\n");
else {
Q->kraj=addone(addone(Q->kraj));
int i=Q->kraj;
while(i!=Q->pocetak) {
Q->elements[i]=Q->elements[i-1];
if(i>0) --i;
else i=MAXL-1;
}
Q->elements[Q->pocetak]=x;
}
}
int main() {
DQUEUE Q;
elementtype x;
char funkcija[MAXL], pomocni[MAXL], broj[MAXL];
int i, j, br=0, n;
MAKE_NULL(&Q);
while(1) {
i=0; j=0;
gets(funkcija);
n=strlen(funkcija);
while(i<n) {
if(funkcija[i]==' ') {
if(br==0) pomocni[i]=funkcija[i];
br++;
}
else if(isdigit(funkcija[i])) {
broj[j]=funkcija[i];
j++;
}
else pomocni[i]=funkcija[i];
i++;
}
x=atoi(broj);
if(pomocni=="UBACI POCETAK") UBACI_POCETAK(x, &Q);
else if(pomocni=="IZBACI POCETAK") IZBACI_POCETAK(&Q);
else if(pomocni=="UBACI KRAJ") UBACI_KRAJ(x, &Q);
else if(pomocni=="IZBACI KRAJ") IZBACI_KRAJ(&Q);
else break;
if(!EMPTY(Q)) {
i=Q.pocetak;
while(i!=Q.kraj) {
printf("%d ", Q.elements[i]);
addone(i);
}
printf("\n");
}
}
system("pause");
return 0;
} |
|
|
[Vrh] |
|
Gea_ Forumaš(ica)
Pridružen/a: 04. 12. 2010. (00:31:15) Postovi: (12)16
|
Postano: 22:31 sri, 9. 11. 2011 Naslov: |
|
|
Pejstam dio koda koji mi se skroz cudno ponasa.Svaki put kad mi uđe u petlju preskoči prvi scanf. Dakle 'čeka' tek kada treba upisati desno dijete.
Probala sam svakako, ili totalno zablokira kad prođe petlju jednom, dvaput ili samo 'čeka' na drugom scanf-u u petlji. Svaka pomoć je dobrodošla.
[code:1]
while ( i < MAXLENGHT )
{
if ( (*B).labels[i] != LAMBDA )
{
// ni L ni D dijete ne stanu u polje, pa idem na sljedeci node
if ( 2*i+1 > MAXLENGHT && 2*i+2 > MAXLENGHT )
{
i++;
break;
}
printf("Unesi lijevo dijete cvora %d na mjesto %d:\n", i,2*i+1);
scanf ("%c", &c);
(*B).labels[2*i+1]=c;
if ( (*B).labels[2*i+1] == '#' )
return;
printf("Unesi desno dijete cvora %d na mjesto %d:\n", i,2*i+2);
scanf ("%c ", &c);
(*B).labels[2*i+2]=c;
if ( (*B).labels[2*i+2] == '#' )
return;
}
++i;
}
[/code:1]
Pejstam dio koda koji mi se skroz cudno ponasa.Svaki put kad mi uđe u petlju preskoči prvi scanf. Dakle 'čeka' tek kada treba upisati desno dijete.
Probala sam svakako, ili totalno zablokira kad prođe petlju jednom, dvaput ili samo 'čeka' na drugom scanf-u u petlji. Svaka pomoć je dobrodošla.
Kod: |
while ( i < MAXLENGHT )
{
if ( (*B).labels[i] != LAMBDA )
{
// ni L ni D dijete ne stanu u polje, pa idem na sljedeci node
if ( 2*i+1 > MAXLENGHT && 2*i+2 > MAXLENGHT )
{
i++;
break;
}
printf("Unesi lijevo dijete cvora %d na mjesto %d:\n", i,2*i+1);
scanf ("%c", &c);
(*B).labels[2*i+1]=c;
if ( (*B).labels[2*i+1] == '#' )
return;
printf("Unesi desno dijete cvora %d na mjesto %d:\n", i,2*i+2);
scanf ("%c ", &c);
(*B).labels[2*i+2]=c;
if ( (*B).labels[2*i+2] == '#' )
return;
}
++i;
}
|
|
|
[Vrh] |
|
lucka Forumaš(ica)
Pridružen/a: 09. 11. 2011. (22:34:41) Postovi: (2)16
|
Postano: 22:55 sri, 9. 11. 2011 Naslov: |
|
|
Moze netko pomoci oko ovog zadatka:
Implementirajte a.t.p. LIST pomoću pointera i napišite funkciju
void MERGE_SORT (LIST L1, LIST *L2)
za sortiranje liste. Program treba omogućiti sortiranje silazno i uzlazno.
Ulazni podaci: broj članova liste, članovi liste, način sortiranja
Izlazni podaci: sortirana lista
Na primjer, za ulazne podatke:
5
7 3 8 5 2
silazno
treba ispisati:
8 7 5 3 2
Javlja mi svakojake greske u kodu i ne znam vise sta napravit...
#include <stdio.h>
#include <stdlib.h>
typedef int elementtype;
typedef int element;
typedef struct cell_tag{
elementtype element;
struct cell_tag *next;
}celltype;
typedef celltype *LIST;
typedef celltype *position;
position END (LIST L) {
position q;
q=L;
while (q->next != NULL)
q=q->next;
return q;
}
position MAKE_NULL (LIST *Lptr) {
*Lptr=(celltype*)malloc(sizeof(celltype));
(*Lptr)->next=NULL;
return (*Lptr);
}
void INSERT (elementtype x, position p, LIST *Lptr) {
position temp;
temp=p->next;
p->next=(celltype*)malloc(sizeof(celltype));
p->next->element=x;
p->next->next=temp;
}
void DELETE (position p) {
position temp;
temp=p->next;
p->next=p->next->next;
free (temp);
}
position FIRST (LIST *L) {
return (*L);
}
position NEXT (position p, LIST L) {
position q;
q=p->next;
return q;
}
element RETRIEVE (position p, LIST L) {
element q;
q=p->element;
return q;
}
position PREVIOUS (position p, LIST L) {
position q;
q=L;
while (q->next != p)
q=q->next;
return q;
}
void ISPISI (LIST L) {
position q;
for (q=L; q!=NULL; q=q->next)
printf ("%d ", q->element);
}
void MERGE_SORT(int nacin, LIST L1, LIST *L2) {
position p1, p2;
element najmanji, najveci;
p2=MAKE_NULL(L2);
if (nacin == 1) {
p1=FIRST(L1);
najmanji=RETRIEVE(p1,L1);
for (p1; p1=NEXT(p1, L1); p1 != END(L1)){
if (najmanji < RETRIEVE(p1,L1)) {
INSERT(najmanji,p2, L2);
}
}
p1=NEXT(p1, L1);
}
else if (nacin == -1) {
p1=FIRST(L1);
najveci=RETRIEVE(p1,L1);
for (p1; p1=NEXT(p1, L1); p1!= END(L1)){
if (najveci > RETRIEVE(p1,L1)) {
INSERT(najveci,p2, L2);
}
}
p1=NEXT(p1, L1);
}
}
int main (void) {
int n, i, a, value_uzl;
LIST *L1, *header=NULL, L2;
char nacin_sorta [8];
char s[]="uzlazno";
L2=MAKE_NULL(&L2);
value_uzl=atoi(s);
printf ("Ucitaj broj elemenata liste: ");
scanf ("%d", &n);
for (i=0; i<n; i++) {
L1=(celltype*)malloc(sizeof(celltype));
L1->next=header;
header=L1;
printf ("Ucitaj element liste: ");
scanf ("%d", &(*L1)->element);
}
printf ("Zelite li sortirati listu uzlazno ili silazno?");
scanf ("%s", nacin_sorta);
a=atoi(nacin_sorta);
if (a==value_uzl) {
MERGE_SORT(1, &L1, L2);
ISPISI(&L1);
}
else {
MERGE_SORT(-1, &L1, L2);
ISPISI(&L1);
}
}
[/code]
Moze netko pomoci oko ovog zadatka:
Implementirajte a.t.p. LIST pomoću pointera i napišite funkciju
void MERGE_SORT (LIST L1, LIST *L2)
za sortiranje liste. Program treba omogućiti sortiranje silazno i uzlazno.
Ulazni podaci: broj članova liste, članovi liste, način sortiranja
Izlazni podaci: sortirana lista
Na primjer, za ulazne podatke:
5
7 3 8 5 2
silazno
treba ispisati:
8 7 5 3 2
Javlja mi svakojake greske u kodu i ne znam vise sta napravit...
#include <stdio.h>
#include <stdlib.h>
typedef int elementtype;
typedef int element;
typedef struct cell_tag{
elementtype element;
struct cell_tag *next;
}celltype;
typedef celltype *LIST;
typedef celltype *position;
position END (LIST L) {
position q;
q=L;
while (q→next != NULL)
q=q→next;
return q;
}
position MAKE_NULL (LIST *Lptr) {
*Lptr=(celltype*)malloc(sizeof(celltype));
(*Lptr)→next=NULL;
return (*Lptr);
}
void INSERT (elementtype x, position p, LIST *Lptr) {
position temp;
temp=p→next;
p→next=(celltype*)malloc(sizeof(celltype));
p→next→element=x;
p→next→next=temp;
}
void DELETE (position p) {
position temp;
temp=p→next;
p→next=p→next→next;
free (temp);
}
position FIRST (LIST *L) {
return (*L);
}
position NEXT (position p, LIST L) {
position q;
q=p→next;
return q;
}
element RETRIEVE (position p, LIST L) {
element q;
q=p→element;
return q;
}
position PREVIOUS (position p, LIST L) {
position q;
q=L;
while (q→next != p)
q=q→next;
return q;
}
void ISPISI (LIST L) {
position q;
for (q=L; q!=NULL; q=q→next)
printf ("%d ", q→element);
}
void MERGE_SORT(int nacin, LIST L1, LIST *L2) {
position p1, p2;
element najmanji, najveci;
p2=MAKE_NULL(L2);
if (nacin == 1) {
p1=FIRST(L1);
najmanji=RETRIEVE(p1,L1);
for (p1; p1=NEXT(p1, L1); p1 != END(L1)){
if (najmanji < RETRIEVE(p1,L1)) {
INSERT(najmanji,p2, L2);
}
}
p1=NEXT(p1, L1);
}
else if (nacin == -1) {
p1=FIRST(L1);
najveci=RETRIEVE(p1,L1);
for (p1; p1=NEXT(p1, L1); p1!= END(L1)){
if (najveci > RETRIEVE(p1,L1)) {
INSERT(najveci,p2, L2);
}
}
p1=NEXT(p1, L1);
}
}
int main (void) {
int n, i, a, value_uzl;
LIST *L1, *header=NULL, L2;
char nacin_sorta [8];
char s[]="uzlazno";
L2=MAKE_NULL(&L2);
value_uzl=atoi(s);
printf ("Ucitaj broj elemenata liste: ");
scanf ("%d", &n);
for (i=0; i<n; i++) {
L1=(celltype*)malloc(sizeof(celltype));
L1→next=header;
header=L1;
printf ("Ucitaj element liste: ");
scanf ("%d", &(*L1)→element);
}
printf ("Zelite li sortirati listu uzlazno ili silazno?");
scanf ("%s", nacin_sorta);
a=atoi(nacin_sorta);
if (a==value_uzl) {
MERGE_SORT(1, &L1, L2);
ISPISI(&L1);
}
else {
MERGE_SORT(-1, &L1, L2);
ISPISI(&L1);
}
}
[/code]
|
|
[Vrh] |
|
mini Forumaš(ica)
Pridružen/a: 04. 02. 2009. (14:31:34) Postovi: (69)16
Spol:
|
|
[Vrh] |
|
Gea_ Forumaš(ica)
Pridružen/a: 04. 12. 2010. (00:31:15) Postovi: (12)16
|
|
[Vrh] |
|
Lepi91 Forumaš(ica)
Pridružen/a: 15. 09. 2010. (15:22:23) Postovi: (C8)16
Spol:
|
|
[Vrh] |
|
pbakic Forumaš(ica)
Pridružen/a: 05. 10. 2009. (17:48:30) Postovi: (143)16
Spol:
|
Postano: 0:47 čet, 10. 11. 2011 Naslov: |
|
|
Ako je zadana implementacija stabla pomocu pointera (koja omogucuje lagani CREATE), onda se moze napraviti isto kao i evaluacija prefix izraza pomocu stacka:
1) Napravimo STACK koji ce cuvati stabla
2) krecemo se po zadanom izrazu, zdesna nalijevo
-ako je trenutni znak operand, stavi ga na stack
(pri stavljanju na stack moramo pretvoriti operand u jednocvorno stablo kojemu je u korijenu zapisan taj operand. to mozemo napraviti pomocu 2 makenull-a i jednog create-a)
-ako je trenutni znak operator, "digni" prva dva elementa sa stacka (opcenito, to ce biti neka 2 stabla) i sastavi stablo kojemu je u korijenu operator, lijevo dijete jedan element, a desno drugi od ova dva koja smo digli sa stacka (pritom moramo paziti na poredak lijevo/desno dijete, jer postoje i nekomutativne operacije)
dobiveno stablo stavi na stack (dva iskoristena elementa smo maknuli)
Kad zavrsimo postupak (tj procitamo cijeli izraz), na stacku bi se trebao nalaziti samo jedan element - trazeno stablo.
Nap:
ovdje je stack koristen samo teoretski... u jednom trenutku moramo dici 2 elementa sa stacka pa buduci da nemamo funkciju koja (neovisno o implementaciji) kopira stabla, moramo biti u mogucnosti direktno pozvati CREATE na zadnja 2 elementa stacka u ulozi podstabala. Zato je vjerojatno prakticnije koristiti obican niz umjesto stacka
P.S: vjerojatno si je najbolje nacrtat ovaj algoritam na nekom malom primjeru i "isprobat" ga tako
Ako je zadana implementacija stabla pomocu pointera (koja omogucuje lagani CREATE), onda se moze napraviti isto kao i evaluacija prefix izraza pomocu stacka:
1) Napravimo STACK koji ce cuvati stabla
2) krecemo se po zadanom izrazu, zdesna nalijevo
-ako je trenutni znak operand, stavi ga na stack
(pri stavljanju na stack moramo pretvoriti operand u jednocvorno stablo kojemu je u korijenu zapisan taj operand. to mozemo napraviti pomocu 2 makenull-a i jednog create-a)
-ako je trenutni znak operator, "digni" prva dva elementa sa stacka (opcenito, to ce biti neka 2 stabla) i sastavi stablo kojemu je u korijenu operator, lijevo dijete jedan element, a desno drugi od ova dva koja smo digli sa stacka (pritom moramo paziti na poredak lijevo/desno dijete, jer postoje i nekomutativne operacije)
dobiveno stablo stavi na stack (dva iskoristena elementa smo maknuli)
Kad zavrsimo postupak (tj procitamo cijeli izraz), na stacku bi se trebao nalaziti samo jedan element - trazeno stablo.
Nap:
ovdje je stack koristen samo teoretski... u jednom trenutku moramo dici 2 elementa sa stacka pa buduci da nemamo funkciju koja (neovisno o implementaciji) kopira stabla, moramo biti u mogucnosti direktno pozvati CREATE na zadnja 2 elementa stacka u ulozi podstabala. Zato je vjerojatno prakticnije koristiti obican niz umjesto stacka
P.S: vjerojatno si je najbolje nacrtat ovaj algoritam na nekom malom primjeru i "isprobat" ga tako
|
|
[Vrh] |
|
Lepi91 Forumaš(ica)
Pridružen/a: 15. 09. 2010. (15:22:23) Postovi: (C8)16
Spol:
|
|
[Vrh] |
|
minora665 Forumaš(ica)
Pridružen/a: 10. 02. 2010. (22:52:01) Postovi: (1F)16
|
|
[Vrh] |
|
pbakic Forumaš(ica)
Pridružen/a: 05. 10. 2009. (17:48:30) Postovi: (143)16
Spol:
|
|
[Vrh] |
|
Lepi91 Forumaš(ica)
Pridružen/a: 15. 09. 2010. (15:22:23) Postovi: (C8)16
Spol:
|
Postano: 3:55 čet, 10. 11. 2011 Naslov: |
|
|
Implementirajte a.t.p. BTREE pomoću polja i napišite potprogram koji kreira binarno stablo iz prefix oblika aritmetičkog izraza. Za kontrolu napravite i preorder obilazak dobivenog stabla.
Ulazni podaci: string koji sadrži prefix oblik izraza
Izlazni podaci: binarno stablo koje odgovara unešenom izrazu: ako stablo ima n čvorova onda treba ispisati n redova, svaki red je oblika cvor, lijevo dijete, desno dijete (ako nekog djeteta nema, ispišite NULL). Na kraju još ispišite PREORDER oblilazak dobivenog stabla.
Na primjer, za ulazne podatke:
+A*B-*CED
treba ispisati:
+ A *
A NULL NULL
* B -
B NULL NULL
- * D
* C E
C NULL NULL
E NULL NULL
D NULL NULL
+A*B-*CED
[code:1]
#include<stdio.h>
#define MAXL 100
typedef char labeltype;
typedef int node;
const node LAMBDA=-1;
typedef struct
{
labeltype LABELS[MAXL];
} BTREE;
void MAKE_NULL(BTREE *B)
{
int i;
for(i=0;i<MAXL;i++)
B->LABELS[i]='-';
}
int EMPTY(BTREE B)
{
int i=1,j=0;
while(i && j<MAXL)
{
if (B.LABELS[j]!='-')
i=0;
j++;
}
return i;
}
node CREATE (labeltype l, BTREE TL, BTREE TR, BTREE *B)
{
int i=0,k1=1,m=1,k2=2,j;
B->LABELS[0]=l;
while(k1<MAXL && k2<MAXL)
{
j=m;
while(j>0)
{
B->LABELS[k1]=TL.LABELS[i];
B->LABELS[k2]=TR.LABELS[i];
i++;
k1++;
k2++;
j--;
}
k1=k1+m;
m=m*2;
k2=k2+m;
}
return 0;
}
void LEFT_SUBTREE(BTREE B, BTREE *TL)
{
int i=0,k=1,l=1,j;
while(k<MAXL)
{
j=l;
while(j>0)
{
TL->LABELS[i]=B.LABELS[k];
i++;
k++;
j--;
}
k=k+l;
l=l*2;
}
}
void RIGHT_SUBTREE(BTREE B, BTREE *TR)
{
int i=0,k=2,l=1,j;
while(k<MAXL)
{
j=l;
while(j>0)
{
TR->LABELS[i]=B.LABELS[k];
i++;
k++;
j--;
}
l=l*2;
k=k+l;
}
}
node INSERT_LEFT_CHILD(labeltype l, node n, BTREE *B)
{
B->LABELS[n*2+1]=l;
return n*2+1;
}
node INSERT_RIGHT_CHILD(labeltype l, node n, BTREE *B)
{
B->LABELS[n*2+2]=l;
return n*2+2;
}
void DELETE(node n, BTREE *B)
{
B->LABELS[n]='-';
}
node ROOT(BTREE B)
{
return 0;
}
node LEFT_CHILD(node n, BTREE B)
{
if ((2*n+1)>=MAXL || B.LABELS[2*n+1]=='-')
return LAMBDA;
return 2*n+1;
}
node RIGHT_CHILD(node n, BTREE B)
{
if ((2*n+2)>=MAXL || B.LABELS[2*n+2]=='-')
return LAMBDA;
return 2*n+2;
}
node PARENT(node n, BTREE B)
{
if (n==0)
return LAMBDA;
return (n-1)/2;
}
labeltype LABEL(node n, BTREE B)
{
return B.LABELS[n];
}
void CHANGE_LABEL(labeltype l, node n, BTREE *B)
{
B->LABELS[n]=l;
}
int UNOS(int i, node j, char prefix[MAXL], BTREE *B)
{
node n1,n2;
n1=INSERT_LEFT_CHILD(prefix[i], j, B);
if (prefix[i]=='+' || prefix[i]=='-' || prefix[i]=='*' || prefix[i]=='/')
i=UNOS(i+1,n1, prefix, B);
i++;
n2=INSERT_RIGHT_CHILD(prefix[i], j, B);
if (prefix[i]=='+' || prefix[i]=='-' || prefix[i]=='*' || prefix[i]=='/')
i=UNOS(i+1,n2, prefix, B);
return i;
}
void OBILAZAK(node i,BTREE B)
{
node n1,n2;
printf("%c ", LABEL(i,B));
n1=LEFT_CHILD(i,B);
if (n1==LAMBDA)
printf("NULL ");
else
printf("%c ",LABEL(n1,B));
n2=RIGHT_CHILD(i,B);
if (n2==LAMBDA)
printf("NULL");
else
printf("%c",LABEL(n2,B));
printf("\n");
if (n1!=LAMBDA)
OBILAZAK(n1,B);
if (n2!=LAMBDA)
OBILAZAK(n2,B);
}
void PREORDER(node n,BTREE B)
{
if (n==LAMBDA) return;
printf("%c", LABEL(n,B));
PREORDER(LEFT_CHILD(n,B),B);
PREORDER(RIGHT_CHILD(n,B),B);
}
int main()
{
BTREE P, prazno;
char prefix[MAXL];
scanf("%s", prefix);
MAKE_NULL(&P);
MAKE_NULL(&prazno);
CREATE(prefix[0], prazno, prazno, &P);
UNOS(1,0, prefix, &P);
OBILAZAK(0,P);
PREORDER(0,P);
return 0;
}
[/code:1]
uglavnom neznam sta mi je krivo ali krivo mi ispisuje,pa ako itko ista vidi,zna neka mi molim vas napise sta moram promijenit...prva dva reda dobro ispise vec treci fula...*B NULL a treba *B-...hvala unaprijed
Implementirajte a.t.p. BTREE pomoću polja i napišite potprogram koji kreira binarno stablo iz prefix oblika aritmetičkog izraza. Za kontrolu napravite i preorder obilazak dobivenog stabla.
Ulazni podaci: string koji sadrži prefix oblik izraza
Izlazni podaci: binarno stablo koje odgovara unešenom izrazu: ako stablo ima n čvorova onda treba ispisati n redova, svaki red je oblika cvor, lijevo dijete, desno dijete (ako nekog djeteta nema, ispišite NULL). Na kraju još ispišite PREORDER oblilazak dobivenog stabla.
Na primjer, za ulazne podatke:
+A*B-*CED
treba ispisati:
+ A *
A NULL NULL
* B -
B NULL NULL
- * D
* C E
C NULL NULL
E NULL NULL
D NULL NULL
+A*B-*CED
Kod: |
#include<stdio.h>
#define MAXL 100
typedef char labeltype;
typedef int node;
const node LAMBDA=-1;
typedef struct
{
labeltype LABELS[MAXL];
} BTREE;
void MAKE_NULL(BTREE *B)
{
int i;
for(i=0;i<MAXL;i++)
B->LABELS[i]='-';
}
int EMPTY(BTREE B)
{
int i=1,j=0;
while(i && j<MAXL)
{
if (B.LABELS[j]!='-')
i=0;
j++;
}
return i;
}
node CREATE (labeltype l, BTREE TL, BTREE TR, BTREE *B)
{
int i=0,k1=1,m=1,k2=2,j;
B->LABELS[0]=l;
while(k1<MAXL && k2<MAXL)
{
j=m;
while(j>0)
{
B->LABELS[k1]=TL.LABELS[i];
B->LABELS[k2]=TR.LABELS[i];
i++;
k1++;
k2++;
j--;
}
k1=k1+m;
m=m*2;
k2=k2+m;
}
return 0;
}
void LEFT_SUBTREE(BTREE B, BTREE *TL)
{
int i=0,k=1,l=1,j;
while(k<MAXL)
{
j=l;
while(j>0)
{
TL->LABELS[i]=B.LABELS[k];
i++;
k++;
j--;
}
k=k+l;
l=l*2;
}
}
void RIGHT_SUBTREE(BTREE B, BTREE *TR)
{
int i=0,k=2,l=1,j;
while(k<MAXL)
{
j=l;
while(j>0)
{
TR->LABELS[i]=B.LABELS[k];
i++;
k++;
j--;
}
l=l*2;
k=k+l;
}
}
node INSERT_LEFT_CHILD(labeltype l, node n, BTREE *B)
{
B->LABELS[n*2+1]=l;
return n*2+1;
}
node INSERT_RIGHT_CHILD(labeltype l, node n, BTREE *B)
{
B->LABELS[n*2+2]=l;
return n*2+2;
}
void DELETE(node n, BTREE *B)
{
B->LABELS[n]='-';
}
node ROOT(BTREE B)
{
return 0;
}
node LEFT_CHILD(node n, BTREE B)
{
if ((2*n+1)>=MAXL || B.LABELS[2*n+1]=='-')
return LAMBDA;
return 2*n+1;
}
node RIGHT_CHILD(node n, BTREE B)
{
if ((2*n+2)>=MAXL || B.LABELS[2*n+2]=='-')
return LAMBDA;
return 2*n+2;
}
node PARENT(node n, BTREE B)
{
if (n==0)
return LAMBDA;
return (n-1)/2;
}
labeltype LABEL(node n, BTREE B)
{
return B.LABELS[n];
}
void CHANGE_LABEL(labeltype l, node n, BTREE *B)
{
B->LABELS[n]=l;
}
int UNOS(int i, node j, char prefix[MAXL], BTREE *B)
{
node n1,n2;
n1=INSERT_LEFT_CHILD(prefix[i], j, B);
if (prefix[i]=='+' || prefix[i]=='-' || prefix[i]=='*' || prefix[i]=='/')
i=UNOS(i+1,n1, prefix, B);
i++;
n2=INSERT_RIGHT_CHILD(prefix[i], j, B);
if (prefix[i]=='+' || prefix[i]=='-' || prefix[i]=='*' || prefix[i]=='/')
i=UNOS(i+1,n2, prefix, B);
return i;
}
void OBILAZAK(node i,BTREE B)
{
node n1,n2;
printf("%c ", LABEL(i,B));
n1=LEFT_CHILD(i,B);
if (n1==LAMBDA)
printf("NULL ");
else
printf("%c ",LABEL(n1,B));
n2=RIGHT_CHILD(i,B);
if (n2==LAMBDA)
printf("NULL");
else
printf("%c",LABEL(n2,B));
printf("\n");
if (n1!=LAMBDA)
OBILAZAK(n1,B);
if (n2!=LAMBDA)
OBILAZAK(n2,B);
}
void PREORDER(node n,BTREE B)
{
if (n==LAMBDA) return;
printf("%c", LABEL(n,B));
PREORDER(LEFT_CHILD(n,B),B);
PREORDER(RIGHT_CHILD(n,B),B);
}
int main()
{
BTREE P, prazno;
char prefix[MAXL];
scanf("%s", prefix);
MAKE_NULL(&P);
MAKE_NULL(&prazno);
CREATE(prefix[0], prazno, prazno, &P);
UNOS(1,0, prefix, &P);
OBILAZAK(0,P);
PREORDER(0,P);
return 0;
}
|
uglavnom neznam sta mi je krivo ali krivo mi ispisuje,pa ako itko ista vidi,zna neka mi molim vas napise sta moram promijenit...prva dva reda dobro ispise vec treci fula...*B NULL a treba *B-...hvala unaprijed
_________________ tko rano rani,malo spava
|
|
[Vrh] |
|
sailor m Forumaš(ica)
Pridružen/a: 23. 10. 2010. (10:46:13) Postovi: (4E)16
|
Postano: 11:28 čet, 10. 11. 2011 Naslov: |
|
|
ulazni podaci su inorder i postorder
Izlazni podaci: ako stablo ima n čvorova, onda treba ispisati n redova: u svakom redu je oznaka jednog vrha i oznake njegove lijevog i desnog djeteta (NULL ako ih nema). Te redove možete ispisati u bilo kojem redoslijedu.
Na primjer, za ulazne podatke:
DGBFCEA
GDFECAB
treba ispisati:
B D A
D NULL G
A C NULL
C F E
F NULL NULL
E NULL NULL
[code:1]char REKONSTRUIRAJ( char *IN, char *POST)
{ char *Left_IN, *Right_IN, *Left_POST, *Right_POST, right, left;
int n, i, j, t;
char roditelj;
n=strlen(POST);
roditelj=POST[n-1];
for(i=0;i<n; i++)
{
if(IN[i]==roditelj)
{
Left_IN=(char*)malloc((i)*sizeof(char));
for(j=0; j<i; j++)
{
Left_IN[j]=IN[j];
}
Right_IN=(char*)malloc((n-i-1)*sizeof(char));
for(j=0; j+i+1<n; j++)
{
Right_IN[j]=IN[j+i+1];
}
break;
}
}
Left_POST=(char*)malloc(i*sizeof(char));
for(j=0; j<i; j++)
{
Left_POST[j]=POST[j];
}
Right_POST=(char*)malloc((n-i-1)*sizeof(char));
for(j=0; j+i<n-1; j++)
{
Right_POST[j]=POST[j+i];
}
if (strlen (Left_IN) == 0)
left = '-'; // to je NULL
else
left = REKONSTRUIRAJ (Left_IN, Left_POST);
if (strlen (Right_IN) == 0)
right = '-'; // to je NULL
else
right = REKONSTRUIRAJ (Right_IN, Right_POST);
printf ("Cvor: %c %c %c\n", roditelj, left, right);
free (Left_IN);
free (Left_POST);
free (Right_POST);
return roditelj;
}
int main(void)
{
int n;
char *IN, *POST;
printf("unesi broj cvorova:\n");
scanf("%d", &n);
IN=(char*)malloc((n)*sizeof(char));
POST=(char*)malloc((n)*sizeof(char));
printf("Unesi INORDER:\n");
scanf("%s", IN);
printf("Unesi POSTORDER:\n");
scanf("%s", POST);
REKONSTRUIRAJ (IN, POST);
return 0;
}[/code:1]
kad unesem podatke program mi nista ne vrati...?
može pomoć.
i pitanje:
kada je int i=0, char *IN i IN=(char*)malloc(i*sizeof(char))
koliki će biti strlen(IN)?
ulazni podaci su inorder i postorder
Izlazni podaci: ako stablo ima n čvorova, onda treba ispisati n redova: u svakom redu je oznaka jednog vrha i oznake njegove lijevog i desnog djeteta (NULL ako ih nema). Te redove možete ispisati u bilo kojem redoslijedu.
Na primjer, za ulazne podatke:
DGBFCEA
GDFECAB
treba ispisati:
B D A
D NULL G
A C NULL
C F E
F NULL NULL
E NULL NULL
Kod: | char REKONSTRUIRAJ( char *IN, char *POST)
{ char *Left_IN, *Right_IN, *Left_POST, *Right_POST, right, left;
int n, i, j, t;
char roditelj;
n=strlen(POST);
roditelj=POST[n-1];
for(i=0;i<n; i++)
{
if(IN[i]==roditelj)
{
Left_IN=(char*)malloc((i)*sizeof(char));
for(j=0; j<i; j++)
{
Left_IN[j]=IN[j];
}
Right_IN=(char*)malloc((n-i-1)*sizeof(char));
for(j=0; j+i+1<n; j++)
{
Right_IN[j]=IN[j+i+1];
}
break;
}
}
Left_POST=(char*)malloc(i*sizeof(char));
for(j=0; j<i; j++)
{
Left_POST[j]=POST[j];
}
Right_POST=(char*)malloc((n-i-1)*sizeof(char));
for(j=0; j+i<n-1; j++)
{
Right_POST[j]=POST[j+i];
}
if (strlen (Left_IN) == 0)
left = '-'; // to je NULL
else
left = REKONSTRUIRAJ (Left_IN, Left_POST);
if (strlen (Right_IN) == 0)
right = '-'; // to je NULL
else
right = REKONSTRUIRAJ (Right_IN, Right_POST);
printf ("Cvor: %c %c %c\n", roditelj, left, right);
free (Left_IN);
free (Left_POST);
free (Right_POST);
return roditelj;
}
int main(void)
{
int n;
char *IN, *POST;
printf("unesi broj cvorova:\n");
scanf("%d", &n);
IN=(char*)malloc((n)*sizeof(char));
POST=(char*)malloc((n)*sizeof(char));
printf("Unesi INORDER:\n");
scanf("%s", IN);
printf("Unesi POSTORDER:\n");
scanf("%s", POST);
REKONSTRUIRAJ (IN, POST);
return 0;
} |
kad unesem podatke program mi nista ne vrati...?
može pomoć.
i pitanje:
kada je int i=0, char *IN i IN=(char*)malloc(i*sizeof(char))
koliki će biti strlen(IN)?
|
|
[Vrh] |
|
Cobs Forumaš(ica)
Pridružen/a: 21. 01. 2008. (13:32:15) Postovi: (206)16
Spol:
Lokacija: Geto
|
|
[Vrh] |
|
|