90. NCP koji prihvata dva velika pozitivna cela broja a, b sa standardnog ulaza (sa ne vise od 50 cifara) i na standardni izlaz ispisuje a,b (u klasi od po 3 cifre kako smo i navikli da pisemo), a+b, a-b(ako a>b), a*b, a/b, a%b. Ucitavanje para brojeva se prekida unosom karaktera koji nije dekadna cifra.
#include <stdio.h>
#include <ctype.h>
#define DA 1
#define NE 0
#define MAX 50
typedef int LRez; /* Tip za logicke rezultate */
LRez nula (const char a[], int na);
int uporedi (const char a[], int na, const char b[], int nb); //poredi dva velika cela broja
void kopiraj (const char a[], int na, char b[], int *nb); //kreira kopiju velikog celog broja
LRez zbir (const char a[], int na, const char b[], int nb,
char c[], int *nc); //sabira dva velika cela broja
LRez razlika (const char a[], int na, const char b[], int nb,
char c[], int *nc); //oduzima dva velika cela broja
LRez proizvod (const char a[], int na, const char b[], int nb,
char c[], int *nc); //mnozi dva velika cela broja
LRez kolicnik (const char a[], int na, const char b[], int nb,
char c[], int *nc, char d[], int *nd);
LRez citaj (char a[], int *n);
void pisi (const char a[], int n, int sir, LRez grupe);
void main () {
char a[MAX], b[MAX], c[2*MAX], d[MAX]; /* brojevi a,b,c,d zadati nizom svojih cifara*/
int na, nb, nc, nd; /*dimenzije nizova a,b,c,d*/
while (citaj (a, &na) && citaj (b, &nb)) {
printf ("a= "); pisi (a, na, MAX, DA); putchar ('\n');
printf ("b= "); pisi (b, nb, MAX, DA); putchar ('\n');
printf ("a+b= "); zbir (a, na, b, nb, c, &nc);
pisi (c, nc, MAX, DA); putchar ('\n');
printf ("a-b= ");
if (razlika (a, na, b, nb, c, &nc))
{ pisi (c, nc, MAX, DA); putchar ('\n'); }
else printf ("ne moze\n");
printf ("a*b= "); proizvod (a, na, b, nb, c, &nc);
pisi (c, nc, MAX, DA); putchar ('\n');
printf ("a/b= ");
if (kolicnik (a, na, b, nb, c, &nc, d, &nd)) {
pisi (c, nc, MAX, DA); putchar ('\n');
printf ("a%%b= "); pisi (d, nd, MAX, DA); putchar ('\n');
} else printf ("ne moze\n");
putchar ('\n');
}
}
LRez nula (const char a[], int na) { return na==1 && a[0]==0; }
int uporedi (const char a[], int na, const char b[], int nb) {
int i;
if (na != nb) return na - nb;
for (i= na-1;i>0 && a[i]==b[i]; i--);
return a[i] - b[i];
}
void kopiraj (const char a[], int na, char b[], int *nb) {
int i;
for (i=0; i<na; i++) b[i] = a[i];
*nb = na;
}
LRez zbir (const char a[], int na, const char b[], int nb,
char c[], int *nc) {
int i, p;
for (p=i=0; i<na || i<nb; i++) {
int d = p;
if (i < na) d += a[i];
if (i < nb) d += b[i];
if (d >= 10) { p = 1; d -= 10; } else p = 0;
c[i] = d;
}
if (p) c[i++] = p;
* nc = i;
return DA;
}
LRez razlika (const char a[], int na, const char b[], int nb,
char c[], int *nc) {
int i, p;
if (uporedi (a, na, b, nb) < 0) return NE;
for (p=i=0; i<na; i++) {
int d = a[i] + p;
if (i <nb) d -= b[i];
if (d < 0) { p = -1; d += 10; } else p = 0;
c[i] = d;
}
for (i=na-1; i>0 && c[i]==0; i--);
*nc = i + 1;
return DA;
}
LRez proizvod (const char a[], int na, const char b[], int nb,
char c[], int *nc) {
if (!nula(a,na) && !nula(b,nb)) {
int i, j, p;
*nc = na + nb;
for (i=0; i<*nc; c[i++]=0);
for (i=0; i<na; i++)
for (p=j=0; j<nb || p; j++) {
int d = c[i+j] + p;
if (j < nb) d += a[i] * b[j];
c[i+j] = d % 10; p = d / 10;
}
if (c[*nc-1] == 0) (*nc)--;
} else { *nc = 1; c[0] = 0; }
return DA;
}
LRez kolicnik (const char a[], int na, const char b[], int nb,
char c[], int *nc, char d[], int *nd) {
int i, j, nn;
if (nula (b, nb)) return NE; /*bez deljenja nulom*/
kopiraj (a, na, d, nd);
nn = na - nb + 1;
if (nn > 0) {
*nc = nn; *nd = nb;
for (i=*nc-1, j=na-nb; i>=0; i--, j--, (*nd)++) {
c[i] = 0;
while (uporedi (d+j, *nd, b, nb) >= 0) {
razlika (d+j, *nd, b, nb, d+j, nd);
c[i]++;
}
}
if (*nc > 1 && c[*nc-1] == 0) (*nc)--;
while (*nd>1 && d[*nd-1]==0) (*nd)--;
} else {
*nc = 1; c[0] = 0;
}
return DA;
}
LRez citaj (char a[], int *n) {
char broj[MAX+1]; int i, j;
scanf ("%s", broj);
for (i=0; broj[i]; i++)
if (! isdigit (broj[i])) return NE;
*n = i;
for (i=*n-1, j=0; i>=0; a[i--]=broj[j++]-'0');
while (*n>1 && a[*n-1] == 0) (*n)--;
return DA;
}
void pisi (const char a[], int n, int sir, LRez grupe) {
int i;
printf ("%*s", (sir - n - (n-1)/3*grupe), "");
for (i=n-1; i>=0; i--) {
putchar (a[i] + '0');
if (grupe && i % 3 == 0) putchar (' ');
}
}
91. NCP koji ce generisati niz slucajnih brojeva (duzine koja se unosi sa standardnog ulaza)
i sortirati niz ili metodom izbora ili poboljsanom metodom izbora ili metodom umetanja ili poboljsanom metodom umetanja ili metodom zamene suseda ili quick sortom. Izbor metoda vrsi korisnik. Ako niz ima manje od 100 clanova, ispisati sortirani niz na standardni izlaz.
Izvrsiti i merenje vremena trajanja svake od metode sortiranja.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef float Elem; /* Tip elemenata niza. */
#define FMTI "%*.*f" /* Format za ispisivanje. */
#define FMTU "%f" /* Format za citanje. */
typedef Elem Niz[]; /* Tip niza. */
typedef void (*Uredi) (Niz a, int n); /* Tip pokazivaca na funkcije. */
void izbor (Niz a, int n); /* Metoda izbora. */
void izbor2 (Niz a, int n); /* Poboljsana metoda izbora. */
void umet (Niz a, int n); /* Metoda umetanja. */
void umet2 (Niz a, int n); /* Poboljsana metoda umetanja. */
void zamena (Niz a, int n); /* Metoda zamene suseda. */
void podela (Niz a, int n); /* Metoda podele. */
void pisi (const char *nasl, Niz a, int n); /* Ispis niza */
/* Niz pokazivaca na funkcije koje realizujuuju algoritme. */
const Uredi metode[] = {izbor, izbor2, umet, umet2, zamena, podela};
/* Niz naziva metoda sortiranja*/
const char *nazivi[]={ "Metoda izbora","Poboljsana metoda izbora", "Metoda umetanja", "Poboljsana metoda umetanja",
"Metoda zamene suseda","Metoda podele"};
int br_alg=sizeof(nazivi)/sizeof(char *); /* Broj algoritama. */
/* Glavni program. */
/*U programu se koriste bibliotecke funkcije rand(), srand(x) iz zaglavlja <stdlib.h>
Vrednost funkcije rand() je (int) pseudoslucajan broj sa ravnomernom raspodelom u opsegu [0, RAND_MAX].
Simbolicka konstanta RAND_MAX ima vrednost koja zavisi od implementacije (kao i INT_MIN,..)
Funkcija srand(x) vrsi postavku na (unsigned int)x pocetne vrednosti sekvence slucajnih brojeva koju ce dati funkciji rand().
Podrazumevana pocetna vrednost sekvence je 1. Povratni tip funkcije je void.
*/
void main ()
{ int duzina =1000, algoritam = 0;
Elem *niz = malloc ((long)duzina*sizeof(Elem));
int izbor, d, i;
clock_t t1, t2;
while (1) {
/* Ispisivanje menija: */
printf ("\n1. Zadavanje duzine niza\n"
"2. Postavljanje generatora slucajnih brojeva za kreiranje clanova niza slucajnih brojeva\n"
"3. Izbor algoritma\n"
"4. Primena algoritma\n"
"9. Kraj programa\n"
"Vas izbor? ");
scanf ("%d", &izbor);
switch (izbor) {
case 1:
/* Zadavanje duzine niza: */
printf ("Duzina niza? "); scanf ("%d", &d);
if(d > 0){
duzina = d;
free (niz);
niz = malloc ((long)duzina*sizeof(Elem));
} else printf ("*** Nedozvoljena duzina!\n");
break;
case 2: /* Postavljanje generatora slucajnih brojeva: */
printf ("Pocetna vrednost generatora? ");
scanf ("%d", &d);
srand (d);
break;
case 3: /* Izbor algoritma: */
putchar ('\n');
for (i= 0; i<br_alg; i++) printf ("%d. %s\n", i+1, nazivi[i]);
printf ("Vas izbor? ");
scanf ("%d", &izbor);
if(izbor>0 && izbor<=br_alg) algoritam = izbor - 1;
else printf ("*** Nedozvoljeni izbor!\n");
break;
case 4: /* Primena algoritma: */
for (i=0; i<duzina; niz[i++]=rand()/(RAND_MAX+1.)*1000);
if (duzina <= 100) pisi ("Pocetni niz:", niz, duzina);
t1 = clock (); /*start vremena rada*/
(*metode[algoritam]) (niz, duzina);
t2 = clock (); /*kraj vremena rada */
if (duzina <= 100)
pisi ("Uredjeni niz:", niz, duzina);
printf ("%s (%d): %.3f\n", nazivi[algoritam],
duzina, (double)(t2-t1)/CLOCKS_PER_SEC); /*ispis vremena rada, probati za n>=1000 */
break;
case 9: /* Kraj programa: */
free (niz); exit (0);
default: /* Pogresan izbor. */
printf ("*** Nedozvoljeni izbor!\n");
break;
}
}
}
/* Ispis niza */
void pisi (const char *nasl, Niz a, int n) {
int i;
printf ("\n%s\n\n", nasl);
for (i=0; i<n; i++) {
printf (FMTI, 7, 1, a[i]);
if (i%10==9 || i==n-1) putchar ('\n');
}
}
/* Metoda izbora (Selection Sort). */
void izbor (Niz a, int n) {
int i, j; Elem b;
for (i=0; i<n-1; i++)
for (j=i+1; j<n; j++)
if (a[j] < a[i]) { b = a[i]; a[i]= a[j]; a[j]=b; }
}
/*Poboljsana metoda izbora. */
void izbor2 (Niz a, int n)
{ int i, j, m; Elem b;
for (i=0; i<n-1; i++) {
m=i;
for(j=i+1; j<n; j++)
if( a[j] < a[m]) m=j;
if( m != i) {b=a[i];a[i]=a[m];a[m]=b;}
}
}
/* Metoda umetanja (Insertion Sort) */
void umet (Niz a, int n)
{int i,j; Elem b;
for(i=1;i<n; i++)
{ for(j=i-1; j>=0 &&a[j]>a[j+1]; j--)
{ b = a[j]; a[j] = a[j+1]; a[j+1] = b; }
}
}
/* Poboljsana metoda umetanja. */
void umet2 (Niz a, int n) {
int i, j; Elem b;
for (i=1; i<n; i++) {
b = a[i];
for (j=i-1; j>=0 &&a[j]>b; j--) a[j+1] = a[j];
a[j+1] = b;
}
}
/* Metoda zamena suseda (Bubble Sort). */
void zamena (Niz a, int n) {
int i, j, dalje; Elem b;
for (dalje=1, i=0; i<n-1 && dalje; i++)
for (dalje=0, j=n-2; j>=i; j--)
if (a[j] > a[j+1]) {
b = a[j]; a[j] = a[j+1]; a[j+1] = b;
dalje = 1;
}
}
/* Metoda podele (Quick Sort). */
void podela (Niz a, int n) {
int i, j; Elem b;
if (n > 1) {
i = -1; j = n - 1;
while (1) {
do i++; while (a[i] < a[n-1]);
do j--; while (j>=0 && a[j]>a[n-1]);
if (i >= j) break;
b = a[i]; a[i] = a[j]; a[j] = b;
}
b = a[i]; a[i] = a[n-1]; a[n-1] = b;
podela (a, i); podela (a+i+1, n-i-1);
}
}
/* Kako dimenzije matrica nisu unapred poznate, vrsi se obrada dinamickih matrica. */
#include <stdio.h>
#include <stdlib.h>
typedef struct { float **a; int m, n; } Din_mat; /* Struktura matrice. */
Din_mat stvori (int m, int n); /* Dodela memorije. */
void unisti (Din_mat dm); /* Oslobadjanje memorije*/
Din_mat kopiraj (Din_mat dm); /* Kopiranje matrice. */
Din_mat citaj (int m, int n); /* Citanje matrice. */
void pisi (Din_mat dm, const char *frm, int max); /* Ispisivanje matrice. */
Din_mat transpon (Din_mat dm); /* Transponovana matrica*/
Din_mat zbir (Din_mat dm1, Din_mat dm2); /* Zbir matrica. */
Din_mat razlika (Din_mat dm1, Din_mat dm2); /* Razlika matrica. */
Din_mat proizvod (Din_mat dm1, Din_mat dm2); /* Proizvod matrica. */
typedef enum {MEM, DIM} Greska; /* Kodovi poruka o gresakama. */
const char *poruke[] = { "Neuspela dodela memorije", /* Poruke o gresci.*/
"Neusaglasene dimenzije matrica"
};
int main () {
while (1) {
Din_mat dm1, dm2, dm3; int m, n;
printf ("Broj vrsta, broj kolona: "); scanf ("%d%d", &m, &n);
if (m<=0 || n<=0) break;
printf ("Prva matrica: "); dm1 = citaj (m, n);
printf ("Broj vrsta, broj kolona: "); scanf ("%d%d", &m, &n);
if (m<=0 || n<=0) break;
printf ("Druga matrica: "); dm2 = citaj (m, n);
if (dm1.m==dm2.m && dm1.n==dm2.n) {
dm3 = zbir (dm1, dm2);
printf ("ZBIR:\n"); pisi (dm3, "%8.2f", 8);
unisti (dm3);
dm3 = razlika (dm1, dm2);
printf ("RAZLIKA:\n"); pisi (dm3, "%8.2f", 8);
unisti (dm3);
}
if (dm1.n == dm2.m) {
dm3 = proizvod (dm1, dm2);
printf ("PROIZVOD:\n"); pisi (dm3, "%8.2f", 8);
unisti (dm3);
}
putchar ('\n');
unisti (dm1); unisti (dm2);
}
return 0;
}
static void greska (Greska g) { /* Ispisivanje poruke o gresci. */
fprintf (stderr, "\n*** %s! ***\n\a", poruke[g]);
exit (g+1);
}
Din_mat stvori (int m, int n) { /* Dodela memorije. */
int i; Din_mat dm;
dm.m = m; dm.n = n;
if ((dm.a = malloc (m * sizeof(float*))) == NULL) greska (MEM);
for (i=0; i<m; i++)
if ((dm.a[i] = malloc (n * sizeof(float))) == NULL) greska (MEM);
return dm;
}
void unisti (Din_mat dm) { /* Oslobadjanje memorije*/
int i;
for (i=0; i<dm.m; free(dm.a[i++]));
free (dm.a);
}
Din_mat kopiraj (Din_mat dm) { /* Kopiranje matrice. */
int i, j;
Din_mat dm2 = stvori (dm.m, dm.n);
for (i=0; i<dm.m; i++)
for (j=0; j<dm.n; j++)
dm2.a[i][j] = dm.a[i][j];
return dm2;
}
Din_mat citaj (int m, int n) { /* Citanje matrice. */
int i, j;
Din_mat dm = stvori (m, n);
for (i=0; i<m; i++)
for (j=0; j<n; scanf("%f",&dm.a[i][j++]));
return dm;
}
void pisi (Din_mat dm, const char *frm, int max){ /* Ispisivanje matrice. */
int i, j;
for (i=0; i<dm.m; i++) {
for (j=0; j<dm.n; j++) {
printf (frm, dm.a[i][j]);
putchar ((j%max==max-1 || j==dm.n-1) ? '\n' : ' ');
}
if (dm.n > max) putchar ('\n');
}
}
Din_mat transpon (Din_mat dm) { /* Transponovana matrica*/
int i, j;
Din_mat dm2 = stvori (dm.n, dm.m);
for (i=0; i<dm.m; i++)
for (j=0; j<dm.n; j++) dm2.a[j][i] = dm.a[i][j];
return dm2;
}
Din_mat zbir (Din_mat dm1, Din_mat dm2) { /* Zbir matrica. */
int i, j; Din_mat dm3;
if (dm1.m!=dm2.m || dm1.n != dm2.n) greska (DIM);
dm3 = stvori (dm1.m, dm1.n);
for (i=0; i<dm3.m; i++)
for (j=0; j<dm3.n; j++)
dm3.a[i][j] = dm1.a[i][j] + dm2.a[i][j];
return dm3;
}
Din_mat razlika (Din_mat dm1, Din_mat dm2) { /* Razlika matrica. */
int i, j; Din_mat dm3;
if (dm1.m!=dm2.m || dm1.n != dm2.n) greska (DIM);
dm3 = stvori (dm1.m, dm1.n);
for (i=0; i<dm3.m; i++)
for (j=0; j<dm3.n; j++)
dm3.a[i][j] = dm1.a[i][j] - dm2.a[i][j];
return dm3;
}
Din_mat proizvod (Din_mat dm1, Din_mat dm2) { /* Proizvod matrica. */
int i, j, k; Din_mat dm3;
if (dm1.n!=dm2.m) greska (DIM);
dm3 = stvori (dm1.m, dm2.n);
for (i=0; i<dm3.m; i++)
for (k=0; k<dm3.n; k++)
for (dm3.a[i][k]=j=0; j<dm2.n; j++)
dm3.a[i][k] += dm1.a[i][j] * dm2.a[j][k];
return dm3;
}
93.
/* Rad sa povezanom listom - iterativne verzije funkcija za rad sa povezanom listom */
#include <stdio.h>
#include <stdlib.h>
typedef struct elem { int broj; struct elem *sled; } Elem; /*Element liste*/
int duz (Elem *lst); /* Broj elemenata liste. */
void pisi (Elem *lst); /* Ispisivanje liste. */
Elem *na_pocetak (Elem *lst, int b); /* Dodavanje na pocetak. */
Elem *na_kraj (Elem *lst, int b); /* Dodavanje na kraj. */
Elem *citaj1 (int n); /* Citanje liste stavljajuci brojeve na pocetak. */
Elem *citaj2 (int n); /* Citanje liste stavljajuci brojeve na kraj. */
Elem *umetni (Elem *lst, int b); /* Umetanje u uredjenu listu. */
void brisi (Elem *lst); /* Brisanje svih elemenata liste. */
Elem *izostavi (Elem *lst, int b); /* Izostavljanje svakog pojavljivanja. */
void main () {
Elem *lst = NULL; int kraj = 0, izbor, broj, n;
while (!kraj) {
printf ("\n1. Dodavanje broja na pocetak liste\n"
"2. Dodavanje broja na kraj liste\n"
"3. Umetanje broja u uredjenu listu\n"
"4. Izostavljanje broja iz liste\n"
"5. Brisanje svih elemenata liste\n"
"6. Citanje uz obrtanje redosleda brojeva\n"
"7. Citanje uz cuvanje redosleda brojeva\n"
"8. Odredjivanje duzine liste\n"
"9. Ispisivanje liste\n"
"0. Zavrsetak rada\n\n"
"Vas izbor? "
);
scanf ("%d", &izbor);
switch (izbor) {
case 1: case 2: case 3: case 4:
printf ("Broj? "); scanf ("%d", &broj);
switch (izbor) {
case 1: /* Dodavanje broja na pocetak liste: */
lst = na_pocetak (lst, broj); break;
case 2: /* Dodavanje broja na kraj liste: */
lst = na_kraj (lst, broj); break;
case 3: /* Umetanje broja u uredjenu listu: */
lst = umetni (lst, broj); break;
case 4: /* Izostavljanje broja iz liste: */
lst = izostavi (lst, broj); break;
}
break;
case 5: /* Brisanje svih elemenata liste: */
brisi (lst); lst = NULL; break;
case 6: case 7: /* Citanje liste: */
printf ("Duzina? "); scanf ("%d", &n);
printf ("Elementi? "); brisi (lst);
switch (izbor) {
case 6: /* uz obrtanje redosleda brojeva: */
lst = citaj1 (n); break;
case 7: /* uz cuvanje redosleda brojeva: */
lst = citaj2 (n); break;
}
break;
case 8: /* Odredjivanje duzine liste: */
printf ("Duzina= %d\n", duz (lst)); break;
case 9: /* Ispisivanje liste: */
printf ("Lista= "); pisi (lst); putchar ('\n'); break;
case 0: /* Zavrsetak rada: */
kraj = 1; break;
default: /* Pogresan izbor: */
printf ("*** Neozvoljeni izbor! ***\a\n"); break;
}
}
}
/* Definicije funkcija za obradu lista (iterativno). */
int duz (Elem *lst) { /* Broj elemenata liste. */
int n = 0; while (lst) { n++; lst = lst -> sled; } return n;
}
void pisi (Elem *lst) { /* Ispisivanje liste. */
while (lst) { printf ("%d ", lst->broj); lst = lst -> sled; }
}
Elem *na_pocetak (Elem *lst, int b) { /* Dodavanje na pocetak. */
Elem *novi = malloc (sizeof(Elem));
novi->broj = b; novi->sled = lst;
return novi;
}
Elem *na_kraj (Elem *lst, int b) { /* Dodavanje na kraj. */
Elem *novi = malloc (sizeof(Elem));
novi->broj = b; novi->sled = NULL;
if (!lst) return novi;
else {
Elem *tek = lst;
while (tek->sled) tek = tek->sled;
tek->sled = novi;
return lst;
}
}
Elem *citaj1 (int n) { /* Citanje liste stavljajuci brojeve na pocetak. */
Elem *prvi = NULL; int i;
for (i=0; i<n; i++) {
Elem *novi = malloc (sizeof(Elem));
scanf ("%d", &novi->broj); novi->sled = prvi;
prvi = novi;
}
return prvi;
}
Elem *citaj2 (int n) { /* Citanje liste stavljajuci brojeve na kraj. */
Elem *prvi = NULL, *posl = NULL; int i;
for (i=0; i<n; i++) {
Elem *novi = malloc (sizeof(Elem));
scanf ("%d", &novi->broj); novi->sled = NULL;
if (!prvi) prvi = novi; else posl->sled = novi;
posl = novi;
}
return prvi;
}
Elem *umetni (Elem *lst, int b) { /* Umetanje u uredjenu listu. */
Elem *tek = lst, *pret = NULL, *novi;
while (tek && tek->broj < b) { pret = tek; tek = tek->sled; }
novi = malloc (sizeof(Elem));
novi->broj = b; novi->sled = tek;
if (!pret) lst = novi; else pret->sled = novi;
return lst;
}
void brisi (Elem *lst) { /* Brisanje svih elemenata liste. */
while (lst) { Elem *stari = lst; lst = lst->sled; free (stari); }
}
Elem *izostavi (Elem *lst, int b){ /* Izostavljanje svakog pojavljivanja. */
Elem *tek = lst, *pret = NULL;
while (tek)
if (tek->broj != b) { pret = tek; tek = tek->sled; }
else {
Elem *stari = tek;
tek = tek->sled;
if (!pret) lst = tek; else pret->sled = tek;
free (stari);
}
return lst;
}
94.
/* Rad sa povezanom listom - REKURZIVNE verzije funkcija za rad sa povezanom listom;
UPOREDITI SA PRETHODNIM ZADATKOM */
#include <stdio.h>
#include <stdlib.h>
typedef struct elem { int broj; struct elem *sled; } Elem; /*Element liste*/
int duz (Elem *lst); /* Broj elemenata liste. */
void pisi (Elem *lst); /* Ispisivanje liste. */
Elem *na_pocetak (Elem *lst, int b); /* Dodavanje na pocetak. */
Elem *na_kraj (Elem *lst, int b); /* Dodavanje na kraj. */
Elem *citaj1 (int n); /* Citanje liste stavljajuci brojeve na pocetak. */
Elem *citaj2 (int n); /* Citanje liste stavljajuci brojeve na kraj. */
Elem *umetni (Elem *lst, int b); /* Umetanje u uredjenu listu. */
void brisi (Elem *lst); /* Brisanje svih elemenata liste. */
Elem *izostavi (Elem *lst, int b); /* Izostavljanje svakog pojavljivanja. */
void main () {
Elem *lst = NULL; int kraj = 0, izbor, broj, n;
while (!kraj) {
printf ("\n1. Dodavanje broja na pocetak liste\n"
"2. Dodavanje broja na kraj liste\n"
"3. Umetanje broja u uredjenu listu\n"
"4. Izostavljanje broja iz liste\n"
"5. Brisanje svih elemenata liste\n"
"6. Citanje uz obrtanje redosleda brojeva\n"
"7. Citanje uz cuvanje redosleda brojeva\n"
"8. Odredjivanje duzine liste\n"
"9. Ispisivanje liste\n"
"0. Zavrsetak rada\n\n"
"Vas izbor? "
);
scanf ("%d", &izbor);
switch (izbor) {
case 1: case 2: case 3: case 4:
printf ("Broj? "); scanf ("%d", &broj);
switch (izbor) {
case 1: /* Dodavanje broja na pocetak liste: */
lst = na_pocetak (lst, broj); break;
case 2: /* Dodavanje broja na kraj liste: */
lst = na_kraj (lst, broj); break;
case 3: /* Umetanje broja u uredjenu listu: */
lst = umetni (lst, broj); break;
case 4: /* Izostavljanje broja iz liste: */
lst = izostavi (lst, broj); break;
}
break;
case 5: /* Brisanje svih elemenata liste: */
brisi (lst); lst = NULL; break;
case 6: case 7: /* Citanje liste: */
printf ("Duzina? "); scanf ("%d", &n);
printf ("Elementi? "); brisi (lst);
switch (izbor) {
case 6: /* uz obrtanje redosleda brojeva: */
lst = citaj1 (n); break;
case 7: /* uz cuvanje redosleda brojeva: */
lst = citaj2 (n); break;
}
break;
case 8: /* Odredjivanje duzine liste: */
printf ("Duzina= %d\n", duz (lst)); break;
case 9: /* Ispisivanje liste: */
printf ("Lista= "); pisi (lst); putchar ('\n'); break;
case 0: /* Zavrsetak rada: */
kraj = 1; break;
default: /* Pogresan izbor: */
printf ("*** Neozvoljeni izbor! ***\a\n"); break;
}
}
}
/* Definicije funkcija za obradu lista (REKURZIVNO). */
int duz (Elem *lst) { /* Broj elemenata liste. */
return lst ? duz (lst->sled) + 1 : 0;
}
void pisi (Elem *lst) { /* Ispisivanje liste. */
if (lst) { printf ("%d ", lst->broj); pisi (lst->sled); }
}
Elem *na_pocetak (Elem *lst, int b) { /* Dodavanje na pocetak. */
Elem *novi = malloc (sizeof(Elem));
novi->broj = b; novi->sled = lst;
return novi;
}
Elem *na_kraj (Elem *lst, int b) { /* Dodavanje na kraj. */
if (!lst) {
lst = malloc (sizeof(Elem));
lst->broj = b; lst->sled = NULL;
} else
lst->sled = na_kraj (lst->sled, b);
return lst;
}
Elem *citaj1 (int n) { /* Citanje liste uz obrtanje redosleda. */
if (n == 0) return NULL;
else {
Elem *novi = malloc (sizeof(Elem));
novi->sled = citaj1 (n - 1); scanf ("%d", &novi->broj);
return novi;
}
}
Elem *citaj2 (int n) { /* Citanje liste uz cuvanje redosleda. */
if (n == 0) return NULL;
else {
Elem *novi = malloc (sizeof(Elem));
scanf ("%d", &novi->broj); novi->sled = citaj2 (n - 1);
return novi;
}
}
Elem *umetni (Elem *lst, int b) { /* Umetanje u uredjenu listu. */
if (!lst || lst->broj >= b) {
Elem *novi = malloc (sizeof(Elem));
novi->broj = b; novi->sled = lst;
return novi;
} else {
lst->sled = umetni (lst->sled, b);
return lst;
}
}
void brisi (Elem *lst) { /* Brisanje svih elemenata liste. */
if (lst) { brisi (lst->sled); free (lst); }
}
Elem *izostavi (Elem *lst, int b){ /* Izostavljanje svakog pojavljivanja. */
if (lst) {
if (lst->broj != b) {
lst->sled = izostavi (lst->sled, b);
} else {
Elem *stari = lst;
lst = izostavi (lst->sled, b);
free (stari);
}
}
return lst;
}
95.
/* rad sa stekom unapred nepoznatog kapaciteta */
#include <stdio.h>
#include <stdlib.h>
typedef struct elem { int broj; struct elem *sled; } Elem;
typedef Elem *Stek;
Stek stvori (void); /* Stvaranje praznog steka. */
void stavi (Stek *stk, int b); /* Stavljanje broja na stek. */
int uzmi (Stek *stk); /* Uzimanje broja sa steka. */
int prazan (Stek stk); /* Da li je stek prazan? */
void pisi (Stek stk); /* Ispisivanje sadrzaja steka. */
void prazni (Stek *stk); /* Praznjenje steka. */
void unisti (Stek *stk); /* Unistavanje steka. */
int main () {
Stek stk = stvori (); int b, izbor, kraj = 0;
while (! kraj) {
printf ("\n1. Smestaj podataka na stek\n"
"2. Skidanje podatka sa steka\n"
"3. Ispisivanje sadrzaja steka\n"
"4. Praznjenje steka\n"
"0. Zavrsetak rada\n\n"
"Vas izbor? "
);
scanf ("%d", &izbor);
switch (izbor) {
case 1: /* podatak na stek: */
printf ("Broj? "); scanf ("%d", &b); stavi (&stk, b);
break;
case 2: /* podatak sa steka: */
if (! prazan (stk))
printf ("Broj= %d\n", uzmi (&stk));
else printf ("*** Stek je prazan! ***\a\n");
break;
case 3: /* Ispisivanje sadrzaja steka: */
printf ("Stek= "); pisi (stk); putchar ('\n');
break;
case 4: /* Praznjenje steka: */
prazni (&stk); break;
case 0: /* Zavrsetak rada: */
kraj = 1; break;
default: /* Pogresan izbor: */
printf ("*** Neozvoljeni izbor! ***\a\n"); break;
}
}
return 0;
}
Stek stvori () { return NULL; } /* Stvaranje praznog steka. */
void stavi (Stek *stk, int b) { /* Stavljanje broja na stek. */
Elem *novi = malloc (sizeof(Elem));
novi->broj = b; novi->sled = *stk; *stk = novi;
}
int uzmi (Stek *stk) { /* Uzimanje broja sa steka. */
Elem *stari; int b;
if (*stk == NULL) exit (2);
b = (*stk)->broj; stari = *stk; *stk = (*stk)->sled; free (stari);
return b;
}
int prazan (Stek stk) { return stk == NULL; } /* Da li je stek prazan? */
void pisi (Stek stk) { Elem *tek; /* Ispisivanje sadrzaja steka. */
for (tek=stk; tek; tek=tek->sled) printf ("%d ", tek->broj);
}
void prazni (Stek *stk) { /* Praznjenje steka. */
while (*stk) { Elem *stari=*stk; (*stk)=(*stk)->sled; free(stari); }
}
void unisti (Stek *stk) { prazni (stk); } /* Unistavanje steka. */
96.
/* rad sa binarnim stablom - implementacija funkcija koje vrse specificnu obradu nad cvorovima
binarnog stabla */
#include <stdio.h>
#include <stdlib.h>
typedef struct cvor { int broj; struct cvor *levo, *desno; } Cvor;
typedef Cvor *Stablo;
Stablo stvori (void); /* Stavaranje praznog stabla. */
int vel (Stablo koren); /* Broj cvorova u stablu. */
int zbir (Stablo koren); /* Zbir brojeva u stablu. */
void pisi_kld (Stablo koren); /* Prefiksno ispisivanje. */
void pisi_lkd (Stablo koren); /* Infiksno ispisivanje. */
void pisi_ldk (Stablo koren); /* Postfiksno ispisivanje. */
void crtaj (Stablo koren, int nivo); /* Graficki prikaz stabla. */
int pojav (Stablo koren, int b); /* Broj pojavljivanja u stablu. */
int min_u (Stablo koren); /* Najmanji u uredjenom stablu. */
int max_u (Stablo koren); /* Najveci u uredjenom stablu. */
int min_n (Stablo koren); /* Najmanji u neuredjenom stablu. */
int max_n (Stablo koren); /* Najveci u neuredjenom stablu. */
int uredjeno (Stablo koren); /* Da li je stablo uredjeno? */
Cvor *nadji_u (Stablo koren, int b); /* Trazenje u uredjenom stablu. */
Cvor *nadji_n (Stablo koren, int b); /* Trazenje u neuredjenom stablu. */
Stablo dodaj_u (Stablo koren, int b); /* Dodavanje u uredjeno stablo. */
Stablo dodaj_n (Stablo koren, int b); /* Dodavanje u neuredjeno stablo. */
Stablo citaj_u (int n); /* Citanje uredjenog stabla. */
Stablo citaj_n (int n); /* Citanje neuredjenog stabla. */
Stablo brisi (Stablo koren); /* Brisanje celog stabla. */
Stablo izost_u (Stablo koren, int b); /* Izost. iz uredjenog stabla. */
Stablo izost_n (Stablo koren, int b); /* Izost. iz neuredjenog stabla. */
Stablo balans_u (Stablo koren); /* Balansiranje uredjenog stabla. */
Stablo balans_n (Stablo koren); /* Balansiranje neuredjenog satbla.*/
int moze (Stablo koren); /* Da li moze uredjena radnja? */
Stablo radi (Stablo (*f)(Stablo,int), Stablo koren); /* Primena operacije na stablo za svaki procitani broj */
void main () {
Stablo koren = stvori (); //stablo
int kraj = 0, broj, n; //indikator kraja rada, element u cvoru stabla, duzina
char izbor[2]; //izbor korisnika sa menija opcija
//obrada menija opcija koje se prikazuju korisniku
while (!kraj) {
printf ("\nDodavanje brojeva: a) uredjeno b) neuredjeno\n"
"Izostavljanje brojeva: c) uredjeno d) neuredjeno\n"
"Citanje stabla: e) uredjeno f) neuredjeno\n"
"Najmanji element: g) uredjeno h) neuredjeno\n"
"Najveci element: i) uredjeno j) neuredjeno\n"
"Pretrazivanje: k) uredjeno l) neuredjeno\n"
"Balansiranje: m) uredjeno n) neuredjeno\n"
"Pisanje stabla: p) koren-levo-desno\n"
" q) levo-koren-desno (uredjeno)\n"
" r) levo-desno-kren\n"
" s) crtanje\n"
"1. Velicina stabla 2. Zbir elemenata\n"
"3. Broj pojavljivanja 4. Praznjenje stabla\n"
" 0. Zavrsetak rada\n\n"
"Vas izbor? "
);
scanf ("%s", &izbor);
switch (izbor[0]) {
case 'a': case 'A': /* Dodavanje brojeva u uredjeno stablo: */
if (moze (koren)) koren = radi (dodaj_u, koren); break;
case 'b': case 'B': /* Dodavanje brojeva u neuredjeno stablo: */
koren = radi (dodaj_n, koren); break;
case 'c': case 'C': /* Izostavljanje brojeva iz uredjenog stabla: */
if (moze (koren)) koren = radi (izost_u, koren); break;
case 'd': case 'D': /* Izostavljanje brojeva iz neuredjenog stabla: */
koren = radi (izost_n, koren); break;
case 'e': case 'E': /* Citanje uredjenog stabla: */
printf ("Duzina? "); scanf ("%d", &n);
printf ("Brojevi? "); koren = brisi (koren); koren = citaj_u (n);
break;
case 'f': case 'F': /* Citanje neuredjenog stabla: */
printf ("Duzina? "); scanf ("%d", &n);
printf ("Brojevi? "); koren = brisi (koren); koren = citaj_n (n);
break;
case 'g': case 'G': case 'h': case 'H':
case 'i': case 'I': case 'j': case 'J':
if (koren) switch (izbor[0]) {
case 'g': case 'G': /* Najmanji element uredjenog stabla: */
if (moze (koren)) printf ("min= %d\n", min_u (koren)); break;
case 'h': case 'H': /* Najmanji element neuredjenog stabla: */
printf ("min= %d\n", min_n (koren)); break;
case 'i': case 'I': /* Najveci element uredjenog stabla: */
if (moze (koren)) printf ("max= %d\n", max_u (koren)); break;
case 'j': case 'J': /* Najveci element neuredjenog stabla: */
printf ("max= %d\n", max_n (koren)); break;
} else printf ("*** Stablo je parzno! ***\a\n");
break;
case 'k': case 'K': /* Broj pojavljivanja u uredjenom stablu: */
if (moze (koren)) {
printf ("Broj? "); scanf ("%d", &broj);
printf ("Broj se%s nalazi u stablu.\n",
(nadji_u (koren, broj) != NULL ? "" : " NE"));
} break;
case 'l': case 'L': /* Broj pojavljivanja u neuredjenom stablu: */
printf ("Broj? "); scanf ("%d", &broj);
printf ("Broj se%s nalazi u stablu.\n",
(nadji_n (koren, broj) != NULL ? "" : " NE"));
break;
case 'm': case 'M': /* Balansiranje uredjenog stabla: */
if (moze (koren)) koren = balans_u (koren); break;
case 'n': case 'N': /* Balansiranje neuredjenog stabla: */
koren = balans_n (koren); break;
case 'p': case 'P': /* Pisanje stabla koren-levo-desno: */
printf ("Stablo= "); pisi_kld (koren); putchar ('\n'); break;
case 'q': case 'Q': /* Pisanje stabla levo-koren-desno: */
printf ("Stablo= "); pisi_lkd (koren); putchar ('\n'); break;
case 'r': case 'R': /* Pisanje stabla levo-desno-koren: */
printf ("Stablo= "); pisi_ldk (koren); putchar ('\n'); break;
case 's': case 'S': /* Crtanje stabla: */
crtaj (koren, 0); break;
case '1': /* Velicina stabla: */
printf ("Vel= %d\n", vel (koren)); break;
case '2': /* Zbir elemenata stabla: */
printf ("Zbir= %d\n", zbir (koren)); break;
case '3': /* Broj pojavljivanja datog broja: */
printf ("Broj? "); scanf ("%d", &broj);
printf ("Broj se pojavljuje %d puta.\n", pojav (koren, broj));
break;
case '4': /* Praznjenje stabla: */
koren = brisi (koren); break;
case '0': /* Zavrsetak rada: */
kraj = 1; break;
default: /* Pogresan izbor: */
printf ("*** Nedozvoljeni izbor! ***\a\n"); break;
}
}
}
Stablo stvori (void) { return NULL; } /* Stvaranje praznog stabla. */
int vel (Stablo koren) /* Broj cvorova u stablu. */
{ return koren ? 1 + vel (koren->levo) + vel (koren->desno) : 0; }
int zbir (Stablo koren) /* Zbir brojeva u stablu. */
{ return koren ? koren->broj + zbir (koren->levo) + zbir (koren->desno) : 0; }
void pisi_kld (Stablo koren) { /* Prefiksno ispisivanje. */
if (koren) {
printf ("%d ", koren->broj); pisi_kld (koren->levo); pisi_kld (koren->desno);
}
}
void pisi_lkd (Stablo koren) { /* Infiksno ispisivanje. */
if (koren) {
pisi_lkd (koren->levo); printf ("%d ", koren->broj); pisi_lkd (koren->desno);
}
}
void pisi_ldk (Stablo koren) { /* Postfiksno ispisivanje. */
if (koren) {
pisi_ldk (koren->levo); pisi_ldk (koren->desno); printf ("%d ", koren->broj);
}
}
void crtaj (Stablo koren, int nivo) { /* Graficki prikaz stabla. */
if (koren) {
crtaj (koren->desno, nivo+1);
printf ("%*s%d\n", 4*nivo, "", koren->broj);
crtaj (koren->levo, nivo+1);
}
}
int pojav (Stablo koren, int b) /* Broj pojavljivanja broja b u stablu. */
{ return koren ? (koren->broj==b)+pojav(koren->levo,b)+pojav(koren->desno,b) : 0;}
int min_u (Stablo koren) /* Najmanji u uredjenom stablu. */
{ return koren->levo ? min_u (koren->levo ) : koren->broj; }
int max_u (Stablo koren) /* Najveci u uredjenom stablu. */
{ return koren->desno ? max_u (koren->desno) : koren->broj; }
int min_n (Stablo koren) { /* Najmanji u neuredjenom stablu. */
int m = koren->broj, k;
if (koren->levo ) { k = min_n (koren->levo ); if (k < m) m = k; }
if (koren->desno) { k = min_n (koren->desno); if (k < m) m = k; }
return m;
}
int max_n (Stablo koren) { /* Najveci u neuredjenom stablu. */
int m = koren->broj, k;
if (koren->levo ) { k = max_n (koren->levo ); if (k > m) m = k; }
if (koren->desno) { k = max_n (koren->desno); if (k > m) m = k; }
return m;
}
int uredjeno (Stablo koren) { /* Da li je stablo uredjeno? */
if (! koren) return 1;
if (koren->levo && (! uredjeno (koren->levo ) ||
max_u (koren->levo) > koren->broj)) return 0;
if (koren->desno && (! uredjeno (koren->desno) ||
min_u (koren->desno) < koren->broj)) return 0;
return 1;
}
Cvor *nadji_u (Stablo koren, int b) { /* Trazenje u uredjenom stablu. */
if (! koren) return NULL;
if (koren->broj == b) return koren;
if (koren->broj > b) return nadji_u (koren->levo, b);
return nadji_u (koren->desno, b);
}
Cvor *nadji_n (Stablo koren, int b) { /* Trazenje u neuredjenom stablu. */
if (! koren) return NULL;
if (koren->broj == b) return koren;
{ Cvor *cvr = nadji_n (koren->levo, b); if (cvr) return cvr; }
return nadji_n (koren->desno, b);
}
Stablo dodaj_u (Stablo koren, int b) { /* Dodavanje u uredjeno stablo. */
if (! koren) {
koren = malloc (sizeof(Cvor));
koren->broj = b; koren->levo = koren->desno = NULL;
} else if (koren->broj > b)
koren->levo = dodaj_u (koren->levo, b);
else if (koren->broj < b)
koren->desno = dodaj_u (koren->desno, b);
else if (rand() / (RAND_MAX+1.) < 0.5)
koren->levo = dodaj_u (koren->levo, b);
else
koren->desno = dodaj_u (koren->desno, b);
return koren;
}
Stablo dodaj_n (Stablo koren, int b) { /* Dodavanje u neuredjeno stablo. */
if (! koren) {
koren = malloc (sizeof(Cvor));
koren->broj = b; koren->levo = koren->desno = NULL;
} else if (rand() / (RAND_MAX+1.) < 0.5)
koren->levo = dodaj_u (koren->levo, b);
else
koren->desno = dodaj_u (koren->desno, b);
return koren;
}
Stablo citaj_u (int n) { /* Citanje uredjenog stabla. */
Stablo koren = NULL; int i, b;
for (i=0; i<n; i++) { scanf ("%d", &b); koren = dodaj_u (koren, b); }
return koren;
}
Stablo citaj_n (int n) { /* Citanje neuredjenog stabla. */
Stablo koren = NULL; int i, b;
for (i=0; i<n; i++) { scanf ("%d", &b); koren = dodaj_n (koren, b); }
return koren;
}
Stablo brisi (Stablo koren) { /* Brisanje celog stabla. */
if (koren) {
koren->levo = brisi (koren->levo); koren->desno = brisi (koren->desno);
free (koren); koren = NULL;
}
return koren;
}
Stablo izost_u (Stablo koren, int b) { /* Izost. iz uredjenog stabla. */
if (koren) {
if (koren->broj > b) koren->levo = izost_u (koren->levo, b);
else if (koren->broj < b) koren->desno = izost_u (koren->desno, b);
else if (koren->levo) {
int m = max_u (koren->levo);
koren->broj = m; koren->levo = izost_u (koren->levo, m);
} else if (koren->desno) {
int m = min_u (koren->desno);
koren->broj = m; koren->desno = izost_u (koren->desno, m);
} else {
free (koren); koren = NULL;
}
}
return koren;
}
Stablo izost_n (Stablo koren, int b) { /* Izost. iz neuredjenog stabla. */
if (koren) {
if (koren->broj == b) {
if (koren->levo ) {
koren->broj = koren->levo->broj;
koren->levo = izost_n (koren->levo, koren->broj);
} else if (koren->desno) {
koren->broj = koren->desno->broj;
koren->desno = izost_n (koren->desno, koren->broj);
} else { free (koren); koren = NULL; }
} else {
int v = vel (koren->levo); koren->levo = izost_n (koren->levo, b);
if (v == vel (koren->levo)) koren->desno = izost_n (koren->desno, b);
}
}
return koren;
}
Stablo balans_u (Stablo koren) { /* Balansiranje uredjenog stabla. */
if (koren) {
int k = vel (koren->levo) - vel (koren->desno);
for (; k>1; k-=2) {
koren->desno = dodaj_u (koren->desno, koren->broj);
koren->broj = max_u (koren->levo );
koren->levo = izost_u (koren->levo , koren->broj);
}
for (; k<-1; k+=2) {
koren->levo = dodaj_u (koren->levo , koren->broj);
koren->broj = min_u (koren->desno);
koren->desno = izost_u (koren->desno, koren->broj);
}
koren->levo = balans_u (koren->levo );
koren->desno = balans_u (koren->desno);
}
return koren;
}
Stablo balans_n (Stablo koren) { /* Balansiranje neuredjenog satbla.*/
if (koren) {
int k = vel (koren->levo) - vel (koren->desno);
for (; k>1; k-=2) {
koren->desno = dodaj_n (koren->desno, koren->broj);
koren->broj = koren->levo ->broj;
koren->levo = izost_n (koren->levo , koren->broj);
}
for (; k<-1; k+=2) {
koren->levo = dodaj_n (koren->levo , koren->broj);
koren->broj = koren->desno->broj;
koren->desno = izost_n (koren->desno, koren->broj);
}
koren->levo = balans_n (koren->levo );
koren->desno = balans_n (koren->desno);
}
return koren;
}
int moze (Stablo koren) { /* Da li moze uredjena radnja? */
if (! uredjeno (koren)) {
printf ("*** Stablo nije uredjeno! ***\a\n");
return 0;
}
else return 1;
}
/* Primena operacije na stablo za svaki procitani broj: */
Stablo radi (Stablo (*f)(Stablo,int), Stablo koren) {
int b; char zn;
printf ("Brojevi? ");
do { scanf ("%d%c", &b, &zn); koren = (*f) (koren, b); } while (zn != '\n');
return koren; /* do kraja reda */
}
|
Jelena Grmuša | |
Osnovi programiranja |