Jednostruko povezane liste

Jedan oblik organizacije dinamičkog čuvanja podataka je jednostruko povezana lista. Lista prestavlja skup čvorova, elemenata, povezani pokazivačima u jednom smeru. Svaki čvor je strukturna promenljiva koja ima najmanje dva polja: jedno za čuvanje podataka, ili informacija o čuvanju podataka,  drugo za čuvanje pokazivača na sledećeg čvora liste.

Deklaracija jednostruko povezanih lista

struct cvor
{
char inf;
struct cvor *sledeci;
};
struct cvor *pocetak_liste;

lista1

Na početak liste pokazuje pokazivačka promenljiva početak_liste. Krajnji čvor liste u elementu za vezu (sledeći) sadrži vrednost NULL. Ako je lista prazna početak_liste takođe, ima vrednost NULL.

Formiranje jednostruke liste

Da bi formirali listu, prvo inicijaliziramo praznu listu dodelom

pocetak_liste=NULL;      

pocetakliste

Kako bi se kreirao prvi dinamički objekat (čvor liste), neophodno je da se dodeli memorijski prostor,
novi=new cvor;, gde je novi pokazivač na strukturu cvor  lista2

Dinamičkom objektu novi, mogu se dodeliti vrednosti
novi→inf= „A“;
novi→ sledeci=pocetak_liste; lista3.PNG

Da bi promenljiva pocetak_liste pokazivala na početak, treba joj dodeliti vrednost promenljivve novi, pocetak_liste=novi; 

lista5.PNG

Prostor za novi cvor liste se odvaja operatorom novi=new cvor;

lista4

Nakon novi→inf=“B“;
            novi→sledeci=pocetak_liste; Informacioni deo čvora dobija vrednost, uključuje se u  listu i to na njen početak lista 6

Da bi promenljiva pocetak_liste pokazivala na početak, ponavlja se dodela pocetak_liste=novi;

 lista7

Pr.1 
Formirati i ispisati jednostruko spregnutu listu?

Rešenje:

#include <cstdlib>
#include <iostream>

using namespace std;
/* Definicija cvora liste*/
struct cvor
{
char pod;
cvor* sledeci;
};
/*Funkcija za ispis liste*/
void ispis(cvor *tekuci)
{
while(tekuci!=NULL)
{
cout<<tekuci->pod<<;
tekuci=tekuci->sledeci;
}
return;
}

int main(int argc, char *argv[])
{
char ceo;
cvor *pocetni, *novi;
pocetni=NULL;
cout<<„Unesi sadrzaj liste“<<endl;
cout<<endl;
while ((ceo=getchar())!=’ ‘)
{
novi= new cvor;
novi->pod=ceo;
novi->sledeci=pocetni;
pocetni=novi;

}
ispis(pocetni);

system(„PAUSE“);
return EXIT_SUCCESS;
}

Pr. 2
Kreiraj i ispisi jednostruko spregnutu listu ciji elementi su celi brojevi?

Rešenje:

#include <cstdlib>
#include <iostream>

using namespace std;
/* Definicija cvora liste*/
struct cvor
{
int pod;
cvor* sledeci;
};
/*Funkcija za ispis liste*/
void ispis(cvor *tekuci)
{
while(tekuci!=NULL)
{
cout<<tekuci->pod<<endl;
tekuci=tekuci->sledeci;
}
return;
}

int main(int argc, char *argv[])
{
int ceo;
cvor *pocetni, *novi;
pocetni=NULL;
cout<<„Unesi sadrzaj liste“<<endl;
cout<<endl;
while (ceo!=9999)
{
cout<<„Unesi ceo broj kao element liste“<<endl;
cout<<„Za kraj unesi 9999″<<endl;
cin>>ceo;
if (ceo!=9999)
{
novi= new cvor;
novi->pod=ceo;
novi->sledeci=pocetni;
pocetni=novi;
cout<<endl;
}
}
ispis(pocetni);
system(„PAUSE“);
return EXIT_SUCCESS;
}

 

Pr.
Kreiraj jednostruko spregnutu listu pri čemu novi čvor se ubacuje na kraj liste?

Rešenje:

#include <cstdlib>
#include <iostream>

using namespace std;
/* definicija strukturnog podatka cvor*/
struct cvor
{
char inf;
struct cvor *sledeci;
};
void pisi (cvor *tekuci)
{
while (tekuci!=NULL)
{
cout<<tekuci->inf<<endl;
tekuci=tekuci->sledeci;
}
return ;
}
int main(int argc, char *argv[])
{
cvor *novi;
cvor *pocl=NULL;
cvor *krajl=NULL;
char ch;
cout<<„Ünesi sadryaj liste“<<endl;
while ((ch=getchar())!=’ ‘)
{
novi= new cvor;
novi->inf=ch;
if(pocl==NULL)
{
pocl=novi;
}
else
{
krajl->sledeci=NULL;
}
krajl=novi;
krajl->sledeci=NULL;
cout<<„Sadrzaj liste“<<endl;
pisi(pocl);
}

system(„PAUSE“);
return EXIT_SUCCESS;
}

 

 

 

Zadaci- dinamicki nizovi

Pr. 1. 

Napravite program koji sumira elemente celobrojnog niza koristeći dinamičke nizove, alociranu memoriju?

Rešenje:

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
int i,n, s=0;
cout<<„Unesi broj elemenata niza“<<endl;
cin>>n;
int *pniz= new int (n);
for( i=0;i<n;i++)
{
cout<<“ Unesi „<<i+1<<“ element niza „<<endl;
cin>>pniz[i];
s+=pniz[i];
}
cout<<“ Suma elemenata alociranog niza je s=“<<s<<endl;
delete[]pniz;
system(„PAUSE“);
return EXIT_SUCCESS;
}

Isti zadatak, ali uradjen korišćenjem funkcije suma koja unosi elemente alociranog, dinamičkog niza i iste sumira

#include <cstdlib>
#include <iostream>

using namespace std;
int suma(int *pniz, int duzina)
{
int i, s=0;
for( i=0;i<duzina;i++)
{
cout<<“ Unesi „<<i+1<<“ element niza „<<endl;
cin>>pniz[i];
s+=pniz[i];
}
return s;
}
int main(int argc, char *argv[])
{
int i,n, s=0;
cout<<„Unesi broj elemenata niza“<<endl;
cin>>n;
int *pniz= new int [n];
cout<<“ Suma elemenata alociranog niza je s=“<<suma(pniz,n)<<endl;
delete[]pniz;
system(„PAUSE“);
return EXIT_SUCCESS;
}

Pr. 2. Šta ispisuje sledeći program?

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
int a[]={0, 1, 2, 3, 4};
int *p;
int i;
for (p=a, i=0;p<&a[4];p++)
{
cout<<*p<<endl;
}
cout<<“ „<<endl;
for (p=&(a[0]), i=0;p+i<a+4;p++,i++)
{
cout<<*(p+i)<<endl;

}
cout<<“ „<<endl;
for (p=a+4, i=0;i<=4;i++)
{
cout<<p[-i]<<endl;
}

system(„PAUSE“);
return EXIT_SUCCESS;
}

Rešenje:

dinamickiniz2

 

Uređivanje niza

Složeniji proces od  pretraživanja niza je uređivanje. Da bi se niz uredio neophodno je da se svaki element uporedi sa ostalim elementima, po potrbi, izvršiti njihovu međusobnu zamenu. Niz može biti sortiran u rastućem i opadajućem redosledu. Postoje nekoliko algoritama za sortiranje nizova.

Metod izbora (selection sort)

Zasniva se na veoma jednostavnoj ideji, izabrati najmanji element niza i dovesti ga na prvo mesto, zatim drugi najmanji, na drugo mesto, itd. do kraja niza.

Primer koji sortira niz u rastućem redosledu

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
int a[10];
int i, j, n, pom;
/* Unos broja elemenata niza*/
cout<<„Unesi broj elemenata niza“<<endl;
cin>>n;
/*Unos elemenata niza*/
for(i=0;i<n;i++)
{
cout<<„Unesi „<<i+1<<“ element niza „;
cin>>a[i];
cout<<endl;
}
/*sortiranje*/
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
pom=a[i];
a[i]=a[j];
a[j]=pom;
}
}
}
/*Ispis niza*/
cout<<„Niz je uredjen u rastu’em redosledu“<<endl;
for(i=0;i<n;i++)
{
cout<<a[i]<<endl;

}
system(„PAUSE“);
return EXIT_SUCCESS;
}

selekt sort

Pr1.

Napravite program koji niz a čiji elementi su celi brojevi uređuje u rastućem redosledu koristeći funkcije?

Rešenje:

#include
#include
using namespace std;
void ucitajniz(int a[], int n)
{
int i;
for (i=0;i<n;i++)
{
cout<<“ Unesi „<<i+1<<“ element niza“<<endl; cin>>a[i];
}
}
void razmeni(int *a, int *b)
{
int pom=*a;
*a=*b;
*b=pom;
}
void sortiraj(int a[], int n)
{
int i, j;
for (i=0;i<n-1;i++)
{
for (j=i+1;j<n;j++) { if (a[i]>a[j])
razmeni(&a[i], &a[j]);
}
}
}
void ispisiniz(int a[], int n)
{
int i;
for (i=0;i<n;i++)
cout<<“ a[„<<i+1<<„] je „<<a[i]<<endl;

}

int main(int argc, char *argv[])
{
int a[10],n;
cout<<„Unesi broj elemenata niza“<<endl; cin>>n;
ucitajniz(a,n);
sortiraj (a,n);
cout<<“ Sortirani niz:“<<endl;
ispisiniz(a,n);
system(„PAUSE“);
return EXIT_SUCCESS;
}

Metod mehuriće (babl sort)

Algoritam sortiranja bubble sort poredi dva susedna elementa niza i ako su pogrešno rasporežđeni zamenjuje im mesta. Posle porežđnja svih susednih parova najmanji od njih će isplivati na kraj niza. Zbog toga se ovaj metod naziva metod mehurića. Da bi se najmanji broj nesortiranog dela niza doveo na svoje mesto treba ponoviti postupak

Primer sortira niz metodom babl sort u rasući redosled

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{

/* deklaracija niza i promenljive koje se koriste*/
int a[10];
int i, j, n, pom;
/* Unos broja elemenata niza*/
cout<<„Unesi broj elemenata niza“<<endl;
cin>>n;
/*Unos elemenata niza*/
for(i=0;i<n;i++)
{
cout<<„Unesi „<<i+1<<“ element niza „;
cin>>a[i];
cout<<endl;
}
/*sortiranje- babl sort*/
for(i=n-1; i>0; i–)
{
for(j=0; j<i; j++)
{
if(a[j]>a[j+1])
{
pom=a[j];
a[j]=a[j+1];
a[j+1]=pom;
}
}
}
/*Ispis niza*/
cout<<„Niz je uredjen u rastu’em redosledu“<<endl;
for(i=0;i<n;i++)
{
cout<<a[i]<<endl;
}
system(„PAUSE“);
return EXIT_SUCCESS;
}

bublesort.JPG

Metod isort

Insert sort, u svakom trenutku je početak niza sortiran a sortiranje se vrši tako što se jedan po jedan element niza sa kraja ubacuje na odgovarajuće mesto.

Primer prikazuje uređivanje niz u opadajućem redosledu metodom isort

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
int a[10];
int i, j, n, pom;
/* Unos broja elemenata niza*/
cout<<„Unesi broj elemenata niza“<<endl;
cin>>n;
/*Unos elemenata niza*/
for(i=0;i<n;i++)
{
cout<<„Unesi „<<i+1<<“ element niza „;
cin>>a[i];
cout<<endl;
}
/*sortiranje*/

for(i=1; i<n; i++)
{
for(j=i; (j>0) && (a[j]>a[j-1]); j–)
{

pom=a[j];
a[j]=a[j-1];
a[j-1]=pom;
}
}
/* Ispis niz*/

cout<<„Niz je uredjen u rastu’em redosledu“<<endl;
for(i=0;i<n;i++)
{
cout<<a[i]<<endl;

}
system(„PAUSE“);
return EXIT_SUCCESS;
}

isort.JPG

Dropbox

Рачунари и програмирање

Дропбокс – мој фаворит.
Дропбокс је мрежни сервис за синхронизацију датотека (фајлова) између више уређаја (истог корисника!): кућни рачунар, рачунар на послу, таблет, паметни телефон…
То је складиште на мрежи у које се пакују фајлови којима корисник може приступити са било ког места: или преко претраживача (фајерфокс, хром…) или преко инсталираног програма, који сам обавља синхронизацију! Подршка је одлична за све системе: линукс, виндовс, андроид…  Бесплатан је и нуди 2GB простора. Тај простор се може повећати до 5GB, позивањем пријатеља да користе дропбокс. Уз доплату од 9,99$ месечно добија се 1ТB!

View original post 680 more words

Primeri zadataka koji koriste cin i cout

Računari i programiranje

Pr1.

Napravi program koji unosi i izdaje brojeve?

Rešenje:
#include <iostream>
usingnamespacestd;
intmain()
{
inta, b;
cout << "Unesi dva broja: ";
cin >> a;
cin >> b;
cout << "a = "<< a << endl;
cout << "b = "<< b << endl;
intc, d;
cout << "unesi jos dva broja: ";
cin >> c >> d;
cout << "c = "<< c << endl;
cout << "d = "<< d << endl;
doublereal;
cout << "Unesi jedan decimalni broj: ";
cin >> real;
cout << "real = "<< real;
return0;
}
Pr2.
Napravi program koji izračunava srednju vrednost četiri broja i ispiši rezultat u sledećem obliku:
Unesi cetiri realna broja:
Srednja vrijednost brojeva …., …., …. i …. je ……?

 Rešenje:

#include<iostream>

using namespace std;

int main()

{

    float a,b,c,d,srvr;

    cout<<„Unesi…

View original post 84 more words

Učeniški projekti

Projekat 1. SRTONOGA

slika

#include <cstdlib>
#include <iostream>
#include <winbgim.h>
using namespace std;

int main()
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode,““);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
int x,r=30;
// crtam oko
for (x=75;x<80;x=x+1)
{
circle(x,210,10);
}
for (x=60;x<65;x=x+1)
{
circle(x,220,10);
}
line(60,240,80,240);
//crtam glava

circle(75, 220, 40);

// crtam trup
for (x=150;x<600;x=x+2*r)
{
for (r=5;r<40;r=r+5)
{

circle(x, 240,r+5);
}
}
// crtam antene
line (70, 180,40,120);
line (85, 180,120,120);
// crtam nozice
for (x=160; x<600;x=x+2*r)
{
line(x, 280,x+r, 280+5);
line(x, 280, x-r,280+15);
}
getch();
return EXIT_SUCCESS;
}

Projekat 2.  KAMIONČE

Kamionceslika

 

#include <cstdlib>
#include <iostream>
#include <winbgim.h>
using namespace std;
int main()
{
//Pode[avanja grafi;kih parametara
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode,“ „);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
rectangle(50,240,150,300);
rectangle(150,300,380,150);
rectangle(380,240,480,300);
moveto(150,240);
lineto(400,240);
circle(100,330,30);
circle(430,330,30);
moveto(50,240);
lineto(150,150);
line(150,195,100,195);
system(„PAUSE“);
return EXIT_SUCCESS;
}

Animacija

Animacija se može napraviti veoma jednostavno. Dovoljno je objekat koji je postavljen, pre ponovnog pozicioniranja obrisati.

Pr1. Napravite program koji crta pravougaonik od jedne do druge pozicije, pri čemu se y koordinata objekta ne menja?

Rešenje:

#include <cstdlib>
#include <iostream>
#include <winbgim.h>
using namespace std;

int main()
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode,““);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
int x,y;
for (x=50;x<600;x=x+1)
{
cleardevice();
rectangle(x, y,x+60,y+60);
}
getch();
return EXIT_SUCCESS;
}

Pr2. Napravite program koji omogućava kretanje kruga po različitim putanjama?

Rešenje:

a)

#include <cstdlib>
#include <iostream>
#include <winbgim.h>
using namespace std;

int main()
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode,““);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
int x,y;

for (y=10;y<400;y=y+30)
{
for (x=10;x<600;x=x+1)
{
cleardevice();
circle(x, y,20);
}
}
getch();
return EXIT_SUCCESS;
}

slika

Krug se kreće sleva prema desno kroz celog grahičkog ekrana.

b)

#include <cstdlib>
#include <iostream>
#include <winbgim.h>
using namespace std;

int main()
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode,““);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
int x,y;

for (x=10;x<600;x=x+30)
{
for (y=10;y<400;y=y+1)
{
cleardevice();
circle(x, y,x+10);
}
}
getch();
return EXIT_SUCCESS;
}

c)

#include <cstdlib>
#include <iostream>
#include <winbgim.h>
using namespace std;

int main()
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode,““);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
int x,y;

for (x=10;x<600;x=x+30)
cleardevice();
{

for (y=10;y<400;y=y+1)
{

circle(x, y,x);
}
}
getch();
return EXIT_SUCCESS;

d)

#include <cstdlib>
#include <iostream>
#include <winbgim.h>
using namespace std;

int main()
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode,““);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
int x,r;

for (x=30;x<610;x=x+60)
{
for (r=5;r<31;r=r+5)
{

delay(100);
// cleardevice();
circle(x, 24,r);
}

}
getch();
return EXIT_SUCCESS;
}

Krug koji menja poluprečnik,  kreće se sleva prema desno, pri čemu y koordinata je fiksna, menja se samo x; Evo kako izgleda slika kada ne bi brisali objekte

slika

Pr3.

a)  Animacija koja od donje pozicije ekrana kreće krug koji nakon dolaska do određenu poziciju menja poluprečnik?

Rešenje:

#include <cstdlib>
#include <iostream>
#include <winbgim.h>
using namespace std;

int main()
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode,““);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
int x,r;

for (x=465;x>100;x=x-1)
{
cleardevice();
circle(320, x,10);
}
for (r=10;r<91;r=r+1)
{

delay(100);
cleardevice();
circle(320, x,r);
}

getch();
return EXIT_SUCCESS;
}

Kada ne bi brisali predhodno nacrtani objekat dobili bi sliku slika

Pr4.   Napravite animaciju koja se dešava korišćenjem tastera a-levo, f -desno, c-gore, v-dole

Rešenje:

#include <cstdlib>
#include <iostream>
#include <winbgim.h>
using namespace std;

int main()
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode,““);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
int x=290;
int y=220;
char odgovor=’d’;

while (odgovor!=’k’)
{
rectangle(x,y,x+60,y+5);
odgovor=getch();
if (odgovor==’a’)
{
x=x-5;
}
if (odgovor==’f’)
{
x=x+5;
}

if (odgovor==’v’)
{
y=y-5;
}
if (odgovor==’c’)
{
y=y+5;
}
//cleardevice();
}
closegraph();
return EXIT_SUCCESS;
}

Ukoliko se izbriše komanda za brisanje predhodnog objekta dobija se slika slika

ili ako početni objekat je krug, dobija se slika slika

 Pr5. Napravite program koji pomoću miša pomera objekat na grafičkom ekrenu?

Rešenje:

#include <cstdlib>
#include <iostream>
#include <winbgim.h>
using namespace std;

int main()
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode,““);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
while (!kbhit())
{
rectangle(mousex(), mousey(), mousex()+50, mousey()+50);
}
closegraph();
return EXIT_SUCCESS;
}

slika

Napomena: Naredba kbhit() ispituje dali je neki taster tastature pritisnut. Znaši naredbom while(!kbhit()) objekat se pomera sve dok se ne pritisne bilo koji taster na tastaturi.

Grafika- zadaci

Pr 1.

Napravite program koji crta  slika - Copy?

Rešenje:

#include <iostream>
#include <stdlib.h>
#include <winbgim.h>

using namespace std;

int main(int argc, char *argv[])
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode, “ „);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
int i,r=80;
int x=160, y=140;
for (i=1;i<=5;i++)
{
circle(x,y,r);
x=x+r;
}
getch();
closegraph();
system(„PAUSE“);
return 0;
}

Pr 2.

Napravite program koji crta slika

Rešenje:

#include <iostream>
#include <stdlib.h>
#include <winbgim.h>

using namespace std;

int main(int argc, char *argv[])
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode, “ „);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
int i,r=60;
int x=320, y=60;
for (i=1;i<=5;i++)
{
circle(x,y,r);
y=y+2*r;
}
x=80,y=240, r=60;

for (i=1;i<=5;i++)
{
circle(x,y,r);
x=x+2*r;
}
getch();
closegraph();
system(„PAUSE“);
return 0;
}

Pr 3.

Napravite program koji crta slika - Copy

Rešenje:

#include <iostream>
#include <stdlib.h>
#include <winbgim.h>

using namespace std;

int main(int argc, char *argv[])
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode, “ „);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
int i,r=60;
int x=60, y=60;
for (i=1;i<=5;i++)
{
circle(x,y,r);
y=y+85;
x=x+85;
}
getch();
closegraph();

system(„PAUSE“);
return 0;
}

Pr 4.

Napravi program koji prikazuje slika - Copy

Rešenje:

#include <iostream>
#include <stdlib.h>
#include <winbgim.h>

using namespace std;

int main(int argc, char *argv[])
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode, “ „);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
int x,r=20;
for (x=20;x<475;x=x+15)
{
circle(x,240,r);
r=r+5;

}
getch();
closegraph();

system(„PAUSE“);
return 0;
}

Pr 5.  Napravite program koji izdaje slika

Rešenje:

#include <iostream>
#include <stdlib.h>
#include <winbgim.h>

using namespace std;

int main(int argc, char *argv[])
{
int gdriver=9;
int gmode=2;
initgraph(&gdriver,&gmode, “ „);
setbkcolor(WHITE);
setcolor(BLACK);
cleardevice();
int x,y=40,r=20;
for (x=20;x<275;x=x+15)
{
circle(x,y,r);
r=r+10;
y=y+10;

}
getch();
closegraph();

system(„PAUSE“);
return 0;
}