/*
JSL - Jednostruko spregnute liste - DOKTORAT
Sa menijem.
Sa globalnim promenljivama.
*/
#include <stdio.h>
#include <stdlib.h> // zbog malloc(), calloc(), realloc(), free()
// #include <malloc.h> // ne treba
typedef struct cvor{
int broj;
struct cvor *sledeci;
} Cvor;
Cvor *glava, *novi, *tek; // deklarisemo tri cvora:
// glava - pocetni cvor, pocetak liste
// novi - pomocni cvor, za stvaranje novih cvorova
// tek - tekuci cvor, za obilazak tj. kretenje kroz listu
/*
struct cvor {
int broj;
struct cvor* sledeci; // sada je tip podatka struct cvor
};
typedef struct cvor CVOR; // sada tip podatka umesto struct cvor postaje samo CVOR
typedef CVOR* PCVOR;
*/
// Vraca 1 ako je lista prazna, inace vraca 0.
int ListaJePrazna(void)
{
if( glava == NULL ){ // ako nema clanova u listi tj. ako je lista prazna
printf(" Lista je prazna.\n\n");
return 1;
}
else return 0;
} // ListaJePrazna()
/*
Prolazak kroz listu:
U radu sa listama cesto je potrebno kretati se kroz listu, od elementa do elementa.
Najcesce je u pitanju obrada podataka u listi, pretraga liste kako bi se nasao
odgovarajuci element ili trazenje kraja liste.
U svim ovim slucajevima algoritam je slican.
Uvodi se pomocni pokazivac koji je inicijalno jednak glavi liste,
tj. pokazuje na prvi element liste ako ona nije prazna.
Nakon provere da li pokazivac pokazuje na neki element (ima vrednost razlicitu od NULL),
vrsi obrada podatka u tom elementu (stampa, uporedjivanje, racun...).
Po zavrsetku obrade podatka, pomocni pokazivac dobija vrednost pokazivaca na sledeci element,
a citav postupak se ponavlja sve dok pomocni pokazivac ima nenultu vrednost,
tj. dok pokazuje na neki element.
Kada pomocni pokazivac dobije vrednost NULL, to znaci da smo dosli do kraja liste.
*/
// Prolazi kroz celu listu i broji elemente liste.
int PrebrojElementeListe()
{
int BrojElemenataListe=0;
tek = glava; // tekuci clan se postavlja na glavu
while( tek ){ // za sve clanove liste ( dok tek ne bude NULL tj. poslednji )
BrojElemenataListe++; // uvecavamo broj clanova liste
tek = tek->sledeci; // prelazimo na sledeci clan liste
}
return BrojElemenataListe;
} // PrebrojElementeListe()
// Stvaranje novog cvora, unos se vrsi u cvor novi
void novicvor(){
novi = (Cvor*)malloc( sizeof(Cvor) ); // rezervisanje memorije za cvor novi
printf("\n\n Unesi novi->broj : "); // unos novi->broj tj. sadrzaja novog cvora
scanf("%d", &novi->broj); // ovde treba ubaciti proveru da li je unet integer !!!
novi->sledeci = NULL; // novi je novi cvor i za sada pokazuje na NULL
} // novicvor()
// Dodavanje novog cvora novi na pocetak liste
void NoviNaPocetak(){
novicvor(); // unos novog cvora u novi
if( glava == NULL ){ // ako nema clanova u listi tj. ako je lista prazna
glava=novi; // onda je glava novi clan (vec pokazuje na NULL)
}
else{ // ako ima clanova u listi tj. ako lista nije prazna
novi->sledeci=glava; // novi clan pokazuje na dosadasnju glavu
glava=novi; // glava postaje novi clan
}
} // NoviNaPocetak()
// Prikazuje celu listu, svaki clan liste u novom redu i ujedno broji clanove liste.
// Za svaki cvor prikazuje sadrzaj i pointer na sledeceg. Vraca broj clanova liste.
int prikaz_liste_sa_pointerima(){
int br_clanova_liste=0; // sluzi za prebrojavanje clanova liste
printf("\n\n"); // novi red
if( glava == NULL ) // ako nema clanova u listi tj. ako je lista prazna
printf(" Lista je prazna.\n\n");
else{ // ako ima clanova u listi tj. ako lista nije prazna
tek = glava; // tekuci clan se postavlja na glavu
printf("\t\t | tek->broj - tek->sledeci | \n\n"); // prikaz zaglavlja liste
while( tek ){ // za sve clanove liste ( dok tek ne bude NULL tj. poslednji )
br_clanova_liste++; // uvecavamo broj clanova liste
printf("\n \t %2d. \t | %5d - %p | \n",
br_clanova_liste, tek->broj, tek->sledeci ); // prikazujemo clana liste
tek = tek->sledeci; // prelazimo na sledeci clan liste
} // while( tek )
} // else // ako ima clanova u listi tj. ako lista nije prazna
// printf("\n\n Lista ima %d elemenata. \n\n", br_clanova_liste );
return( br_clanova_liste );
} // prikaz_liste_sa_pointerima()
// Prikazuje samo sadrzaje cvorova u jednom redu i ujedno broji clanove liste.
// Vraca broj clanova liste.
int prikaz_liste(void){
int br_clanova_liste=0; // sluzi za prebrojavanje clanova liste
printf("\n\n"); // novi red
if( glava == NULL ) // ako nema clanova u listi tj. ako je lista prazna
printf(" Lista je prazna.\n\n");
else{ // ako ima clanova u listi tj. ako lista nije prazna
tek = glava; // tekuci clan se postavlja na glavu
while( tek ){ // za sve clanove liste ( dok tek ne bude NULL tj. poslednji )
br_clanova_liste++; // uvecavamo broj clanova liste
printf("%4d", tek->broj ); // prikazujemo sadrzaj tekuceg cvora
tek = tek->sledeci; // prelazimo na sledeci clan liste
}
}
// printf("\n\n\n Lista ima %d elemenata. \n\n", br_clanova_liste );
printf("\n\n"); // novi red
return( br_clanova_liste );
} // prikaz_liste()
// Umetanje novog cvora posle cvora ciji je sadrzaj x
int UmetniPosleX(){
int x;
printf("\n\n"); // novi red
printf("\n\n Novi cvor unesi posle cvora koji ima vrednost, x = ");
scanf("%d", &x);
novicvor(); // unos novog cvora u novi
if( glava == NULL ){ // ako nema clanova u listi
printf("\n\n Lista je prazna!!! \n\n");
system("PAUSE");
return(0);
}
else{ // ako ima clanova u listi
tek = glava; // postavimo se na prvi clan liste
while( tek->broj != x && tek->sledeci != NULL ){ // do kraja liste ili do clana ciji je sadrzaj x
tek = tek->sledeci; // prelazimo na sledeci cvor
}
// sada smo na cvoru ciji je sadrzaj x
// on je pokazivao na svog sledeceg clana
// a sada treba da pokazuje na novi
// a novi treba da pokazuje na clana na kojeg je dosad pokazivao cvor x
// ili, jednostavnije:
// x je pokazivao na c
// sada x treba da pokazuje na novi
// a novi treba da pokazuje na c
novi->sledeci = tek->sledeci;
tek->sledeci = novi;
}
} // UmetniPosleX()
// Dodavanje novog cvora novi na kraj liste
void NoviNaKraj(){
novicvor(); // unos novog cvora u novi
if( glava == NULL ){ // ako nema clanova u listi tj. ako je lista prazna
glava=novi; // onda taj novouneti clan novi postaje pocetak liste (glava)
} // ( a ujedno je i kraj liste jer je jedini )
else{ // ako ima clanova u listi tj. ako lista nije prazna
tek = glava; // postavimo se na prvi clan liste
while( tek->sledeci != NULL ){ // dok se ne dodje do poslednjeg clana liste
tek = tek->sledeci; // prelazimo na sledeci clan liste
}
// sada je tekuci clan (tek) poslednji clan liste,
tek->sledeci = novi; // i on treba da pokazuje na novouneti clan novi
}
} // NoviNaKraj()
// Brisanje pocetnog (prvog) cvora u listi, brisanje glave
void BrisiPrvi(){
if( glava == NULL ){ // ako nema clanova u listi tj. ako je lista prazna
printf("\n\n Lista je prazna! Nemoguce brisanje !!! \n\n");
system("PAUSE");
}
else{ // ako ima clanova u listi tj. ako lista nije prazna
novi = glava; // pocetni clan glava pamtimo u pomocni clan novi zbog oslobadjanja memorije
glava = glava->sledeci; // drugi clan postaje prvi, tj. novi pocetni clan glava postaje njegov (bivsi) sledeci clan
free(novi); // oslobadjamo memoriju koja je bila rezervisana za pomocni clan novi
} // (tu smo zapamtili bivsi pocetni clan glava)
} // BrisiPrvi()
// Brisanje poslednjeg cvora u listi
void BrisiPoslednji(){
if( glava == NULL ) { // ako nema clanova u listi tj. ako je lista prazna
printf("\n\n Lista je prazna! Nemoguce brisanje!!! \n\n");
system("PAUSE");
}
else{ // ako ima clanova u listi tj. ako lista nije prazna
tek=glava; // postavimo se na prvi clan liste
if(tek->sledeci != NULL){ // ako postoji sledeci clan
while(tek->sledeci->sledeci != NULL){ // do pretposlednjeg clana
tek=tek->sledeci; // predji na sledeci clan
}
// sada je tekuci clan (tek) pretposlednji clan liste
novi = tek->sledeci; // u novi pamtimo adresu poslednjeg clana liste
// zbog oslobadjanja memorije (njega brisemo)
tek->sledeci = NULL; // pretposlednji clan tek nema sledeceg i zato pokazuje na NULL
free(novi); // oslobadjamo memoriju koju je zauzimao bivsi poslednji clan liste
} // jer smo ga obrisali i on nam vise ne treba
else{ // ako ne postoji sledeci clan, tj. tek je jedini clan u listi, i prvi i poslednji
BrisiPrvi(); // onda brisemo taj jedini clan liste
}
}
} // BrisiPoslednji()
// Brise sve cvorove liste i oslobadja memoriju koju su cvorovi zauzimali
void BrisiSveCvorove()
{
while( ( tek = glava ) != NULL ){ // dok glava postoji, brisemo glavu
novi = glava; // pocetni clan glava pamtimo u pomocni clan novi zbog oslobadjanja memorije
glava = glava->sledeci; // drugi clan postaje prvi, tj. novi pocetni clan glava postaje njegov (bivsi) sledeci clan
free(novi); // oslobadjamo memoriju koja je bila rezervisana za pomocni clan novi
}
} // BrisiSveCvorove()
/*
Brisanje elementa iz liste:
Da bi smo obrisali odredjeni element x iz liste, potrebno je da znamo njegovu poziciju u listi.
Krecemo se kroz listu dok tekuci element ne bude onaj koji brisemo ( tek->broj = x ).
Potrebno je da znamo i pokazivac na prethodni element u listi, kako bi smo njegovom linku
dodelili pokazivac na element koji sledi elementu koji brisemo.
Nakon toga mozemo da obrisemo trazeni element, odnosno da oslobodimo memoriju koju on zauzima.
*/
// Brise prvi cvor koji ima sadrzaj x i oslobadja memoriju koju je taj cvor zauzimao.
// Vraca BrojObrisanih cvorova.
int BrisiPrviSaVrednoscuX( int x )
{
int BrojObrisanih=0;
if( glava == NULL ) { // ako nema clanova u listi tj. ako je lista prazna
printf("\n\n Lista je prazna! Nemoguce brisanje!!! \n\n");
system("PAUSE");
}
else { // ako ima clanova u listi tj. ako lista nije prazna
tek = glava; // postavimo se na prvi clan liste
if( tek->broj == x ) { // ako je sadrzaj glave x
BrisiPrvi();
}
else { // ako sadrzaj glave nije x
// do kraja liste ili do clana ciji je sadrzaj x
while( tek->broj != x && tek->sledeci != NULL ){
printf("\n\n while tek->broj = %2d \n\n", tek->broj );
novi = tek; // u novi pamtimo prethodni od tek
tek = tek->sledeci; // prelazimo na sledeci cvor
}
// sada je tek cvor cija je vrednost x, novi je prethodni od tek
if( tek->broj == x ){ // ako postoji cvor ciji je sadrzaj x
novi->sledeci = tek->sledeci;// prethodni od tek pokazuje na sledeci od tek (jer tek brisemo)
novi = tek; // u novi pamtimo tek zbog brisanja i zbog oslobadjanja memorije (njega brisemo)
free(novi); // oslobadjamo memoriju koju je zauzimao bivsi poslednji clan liste
BrojObrisanih++;
}
else {
printf("\n\n U listi ne postoji cvor ciji je sadrzaj %2d ! \n\n", x );
system("PAUSE");
}
} // ako je sadrzaj glave nije x
} // ako ima clanova u listi tj. ako lista nije prazna
return BrojObrisanih;
} // BrisiPrviSaVrednoscuX()
// Brise zadati element iz liste.
int BrisiPrviSaVrednoscuX_1( int x )
{
int BrojObrisanih=0;
if( glava == NULL ) { // ako nema clanova u listi tj. ako je lista prazna
printf("\n\n Lista je prazna! Nemoguce brisanje!!! \n\n");
system("PAUSE");
}
else { // ako ima clanova u listi tj. ako lista nije prazna
tek = glava; // postavimo se na prvi clan liste
if( tek->broj == x ) { // ako je sadrzaj glave x
BrisiPrvi();
}
else { // ako sadrzaj glave nije x
// do kraja liste ili do clana ciji je sadrzaj x
while( tek->broj != x && tek->sledeci != NULL ){
printf("\n\n while tek->broj = %2d \n\n", tek->broj );
novi = tek; // u novi pamtimo prethodni od tek
tek = tek->sledeci; // prelazimo na sledeci cvor
}
// sada je tek cvor cija je vrednost x, novi je prethodni od tek
if( tek->broj == x ){ // ako postoji cvor ciji je sadrzaj x
novi->sledeci = tek->sledeci;// prethodni od tek pokazuje na sledeci od tek (jer tek brisemo)
novi = tek; // u novi pamtimo tek zbog brisanja i zbog oslobadjanja memorije (njega brisemo)
free(novi); // oslobadjamo memoriju koju je zauzimao bivsi poslednji clan liste
BrojObrisanih++;
}
else {
printf("\n\n U listi ne postoji cvor ciji je sadrzaj %2d ! \n\n", x );
system("PAUSE");
}
} // ako je sadrzaj glave nije x
} // ako ima clanova u listi tj. ako lista nije prazna
return BrojObrisanih;
} // BrisiPrviSaVrednoscuX_1()
// Brise sve cvorove koji imaju sadrzaj x i oslobadja memoriju koju su ti cvorovi zauzimali.
// Vraca BrojObrisanih cvorova.
int BrisiSveSaVrednoscuX( int x ) {
Cvor *prethodni, *trenutni;
int BrojObrisanih=0;
if( glava == NULL ) { // ako nema clanova u listi tj. ako je lista prazna
printf("\n\n Lista je prazna! Nemoguce brisanje!!! \n\n");
system("PAUSE");
}
else { // ako ima clanova u listi tj. ako lista nije prazna
trenutni = glava; // postavimo se na prvi clan liste
prethodni = NULL;
while( trenutni != NULL ){ // za sve clanove liste ( dok tek ne bude NULL tj. poslednji )
prethodni = trenutni;
// novi = trenutni;
trenutni = trenutni->sledeci;
// printf("\n\n while prethodni->broj = %d trenutni->broj = %2d \n\n", prethodni->broj, trenutni->broj );
if ( trenutni->broj == x ){
// printf("\n\n if: prethodni->broj = %d trenutni->broj = %2d \n\n", prethodni->broj, trenutni->broj );
// novi = trenutni;
trenutni = trenutni->sledeci;
prethodni->sledeci = trenutni;
// printf("\n\n if: prethodni->broj = %d trenutni->broj = %2d novi->broj %d\n\n", prethodni->broj, trenutni->broj , novi->broj );
//free(novi); // oslobadjamo memoriju koju je zauzimao bivsi poslednji clan liste
BrojObrisanih++;
}
// system("PAUSE");
}
} // ako ima clanova u listi tj. ako lista nije prazna
if( BrojObrisanih == 0 ){
printf("\n\n U listi ne postoji cvor ciji je sadrzaj %2d ! \n\n", x );
system("PAUSE");
}
return BrojObrisanih;
} // BrisiSveSaVrednoscuX()
// Brisanje elementa po rednom broju u listi
Cvor *ObrisiCvorCijiJeRedniBrojK( Cvor *p, int redni_broj )
{
Cvor *prethodni, *trenutni;
int i;
if (p == NULL ){ // ako je lista prazna
printf("Lista je prazna. \n");
system("PAUSE");
}
else // ako lista nije prazna
{
if ( redni_broj > PrebrojElementeListe(p) ){
printf("\n\n Redni broj %d je veci od broja elemenata liste %d ! \n\n",
redni_broj, PrebrojElementeListe(p));
system("PAUSE");
}
else{
prethodni = NULL;
trenutni = p;
i = 1;
while ( i < redni_broj ){
prethodni = trenutni;
trenutni = trenutni->sledeci;
i = i+1;
}
if ( prethodni == NULL ){
p = trenutni->sledeci;
free( trenutni );
}
else{
prethodni->sledeci = trenutni->sledeci;
free( trenutni );
}
} // else // ( redni_broj <= PrebrojElementeListe(p) )
} // else // ako lista nije prazna
return( p );
} // ObrisiCvorCijiJeRedniBrojK()
/*
Sortiranje liste u rastuci redosled:
Da bismo sortirali listu, prvo prolazimo kroz nju kako bismo pronasli element
sa najmanjom vrednoscu podatka. Nakon toga uklanjamo taj element iz liste i
dodajemo ga na kraj druge liste, koja je inicijalno bila prazna.
Ovaj proces ponavljamo sve dok pocetna lista ne postane prazna.
Na kraju ostaje samo da funkcija vrati pokazivac na listu u koju su prebaceni svi elementi.
*/
// Sortira listu u rastucem redosledu
Cvor *SortirajURastuciRedosled( Cvor *p )
{
Cvor *pom1, *pom2, *min, *prethodni, *q;
q = NULL;
while( p != NULL )
{
prethodni = NULL;
min = pom1 = p; // pretpostavljamo da je najmanji bas prvi element (glava)
pom2 = p->sledeci;
while ( pom2 != NULL )
{
if( pom2->broj < min->broj )
{
min = pom2;
prethodni = pom1;
}
pom1 = pom2;
pom2 = pom2->sledeci;
}
if(prethodni == NULL)
p = min->sledeci;
else
prethodni->sledeci = min->sledeci;
min->sledeci = NULL;
if( q == NULL )
q = min; // premesta element sa najmanjom vrednoscu podatka iz liste p na pocetak liste q
else
{
pom1 = q;
// prolazi kroz listu q da bi pronasao njen poslednji element
while( pom1->sledeci != NULL )
pom1 = pom1->sledeci;
// premesta element sa najmanjom vrednoscu podatka iz liste p na kraj liste q
pom1->sledeci = min;
}
}
return ( q );
} // SortirajURastuciRedosled()
/*
Sortiranje liste u opadajuci redosled:
Da bismo sortirali listu, prvo prolazimo kroz nju kako bismo pronasli element
sa najvecom vrednoscu podatka. Nakon toga uklanjamo taj element iz liste i
dodajemo ga na pocetak druge liste, koja je inicijalno bila prazna.
Ovaj proces ponavljamo sve dok pocetna lista ne postane prazna.
Na kraju ostaje samo da funkcija vrati pokazivac na listu u koju su prebaceni svi elementi.
*/
// Sortira listu u opadajucem redosledu
Cvor *SortirajUOpadajuciRedosled( Cvor *p )
{
Cvor *pom1, *pom2, *max, *prethodni, *q;
q = NULL;
while( p != NULL ) // do kraja liste
{
prethodni = NULL;
max = pom1 = p; // pretpostavljamo da je najveci bas prvi element (glava)
pom2 = p->sledeci;
while ( pom2 != NULL )
{
if( pom2->broj > max->broj )
{
max = pom2;
prethodni = pom1;
}
pom1 = pom2;
pom2 = pom2->sledeci;
}
if( prethodni == NULL )
p = max->sledeci;
else
prethodni->sledeci = max->sledeci;
max->sledeci = NULL;
if( q == NULL )
q = max; // premesta element sa najvecom vrednoscu podatka iz liste p na pocetak liste q
else
{
pom1 = q;
// prolazi kroz listu q da bi pronasao njen poslednji element
while( pom1->sledeci != NULL )
pom1 = pom1->sledeci;
// premesta element sa najvecom vrednoscu podatka iz liste p na kraj liste q
pom1->sledeci = max;
}
}
return ( q );
} // SortirajUOpadajuciRedosled()
// Pravi listu od 10 cvorova, da bi se izbegao pojedinacni unos cvorova (elemenata liste)
void napravi_listu(void)
{
int i;
BrisiSveCvorove(); // Brise sve cvorove liste i oslobadja memoriju koju su cvorovi zauzimali
// sledece if je potrebno samo ako prethodno ne pozovemo BrisiSveCvorove()
if( glava == NULL ){ // ako nema clanova u listi tj. ako je lista prazna
for(i=1;i<=10;i++){
novi=(Cvor*)malloc(sizeof(Cvor)); // rezervisanje memorije za novi cvor
novi->broj = i;
novi->sledeci = NULL; // novi je novi cvor i za sada pokazuje na NULL
// formiran i-ti cvor dodjaemo na kraj liste
if( glava == NULL ){ // ako nema clanova u listi tj. ako je lista prazna
glava=novi; // onda taj novouneti clan novi postaje pocetak liste (glava)
} // ( a ujedno je i kraj liste jer je jedini )
else{ // ako ima clanova u listi tj. ako lista nije prazna
tek=glava; // postavimo se na prvi clan liste
while(tek->sledeci!=NULL){ // dok se ne dodje do poslednjeg clana liste
tek=tek->sledeci; // prelazimo na sledeci clan liste
}
// sada je tekuci clan (tek) poslednji clan liste,
tek->sledeci=novi; // i on treba da pokazuje na novouneti clan novi
} // if( glava == NULL )
} // for(i=1;i<=6;i++)
} // if( glava == NULL )
else {
printf("\n\n Lista nije prazna. Prvo obrisite sve clanove liste ! \n\n");
system("PAUSE");
}
} // napravi_listu()
/*
Krecemo se po listi od glave na desno.
Prvo je trenutni element glava a prethodni element NULL (pocetne vrednosti).
Zatim, do kraja liste ponavljamo:
sledeci = trenutni->sledeci; // sledeci je onaj na koji pokazuje trenutni
trenutni->sledeci = prethodni; // trenutni sada pokazuje na prethodni
prethodni = trenutni; // prethodni postaje trenutni
trenutni = sledeci; // trenutni postaje sledeci (idemo na sledeci element)
Okretanje redosleda u listi:
Da bi smo izvrsili okretanje redosleda u listi, neophodno je da
za svaki element znamo pokazivace na njegovog prethodnika i sledbenika.
Nakon toga trenutni element proglasavamo za prethodnika,
a njegovog sledbenika za trenutni.
*/
// Obrce redosled cvorova liste
Cvor *ObrniRedosled( Cvor *p )
{
Cvor *prethodni, *trenutni, *sledeci;
trenutni = p; // trenutni je glava, prvi element u listi
prethodni = NULL; // pocetna vrednost za prethodni
while( trenutni != NULL ) // od glave do kraja liste
{
sledeci = trenutni->sledeci; // sledeci je onaj na koji pokazuje trenutni
trenutni->sledeci = prethodni; // trenutni sada pokazuje na prethodni
prethodni = trenutni; // prethodni postaje trenutni
trenutni = sledeci; // trenutni postaje sledeci (idemo na sledeci element)
}
return prethodni; // vraca prethodni jer je to sada glava (prvi element) liste
} // ObrniRedosled()
/*
Umetanje novog elementa u rastuce sortiranu listu:
Da bismo umetnuli novi element u listu koja je prethodno sortirana,
uporedjujemo redom podatke u listi sa vrednoscu podatka novog elementa.
Ovaj proces se ponavlja sve dok ne dobijemo pokazivac na element
koji se nalazi ispred elementa ciji je podatak veci od podatka u novom elementu.
*/
// Umece novi element u rastuce sortiranu listu
Cvor *DodajURastuceSortiranuListu( Cvor *p, int x )
{
Cvor *trenutni, *prethodni, *pom;
trenutni = p;
prethodni = NULL;
while( trenutni->broj < x )
{
prethodni = trenutni;
if ( trenutni->sledeci != NULL )
trenutni = trenutni->sledeci;
else
break;
}
pom = (Cvor *) malloc( sizeof(Cvor) );
if( pom == NULL )
{
printf("Greska pri alociranju memorije.\n");
exit(0);
}
if ( prethodni == NULL ) // element ce biti umetnut na pocetak liste
{
pom->broj = x;
pom->sledeci = p;
p = pom;
}
else
{
pom->broj = x;
pom->sledeci = prethodni->sledeci;
prethodni->sledeci = pom;
}
return( p );
} // DodajURastuceSortiranuListu
/*
Umetanje novog elementa u opadajuce sortiranu listu:
Da bismo umetnuli novi element u listu koja je prethodno sortirana,
uporedjujemo redom podatke u listi sa vrednoscu podatka novog elementa.
Ovaj proces se ponavlja sve dok ne dobijemo pokazivac na element
koji se nalazi iza elementa ciji je podatak veci od podatka u novom elementu.
*/
// Umece novi element u opadajuce sortiranu listu
Cvor *DodajUOpadajuceSortiranuListu( Cvor *p, int x )
{
Cvor *trenutni, *prethodni, *pom;
trenutni = p;
prethodni = NULL;
while( trenutni->broj > x )
{
prethodni = trenutni;
if ( trenutni->sledeci != NULL )
trenutni = trenutni->sledeci;
else
break;
}
pom = (Cvor *) malloc( sizeof(Cvor) );
if( pom == NULL )
{
printf("Greska pri alociranju memorije.\n");
exit(0);
}
if ( prethodni == NULL ) // element ce biti umetnut na pocetak liste
{
pom->broj = x;
pom->sledeci = p;
p = pom;
}
else
{
pom->broj = x;
pom->sledeci = prethodni->sledeci;
prethodni->sledeci = pom;
}
return( p );
} // DodajUOpadajuceSortiranuListu()
// Meny za sortiranje cvorova
int SortiranjeCvorova(void)
{
int izbor, x, y;
while(1){
system("CLS");
prikaz_liste();
printf("\n\n +-------------------------------------------------------+ \n");
printf(" | | \n");
printf(" | SORTIRANJE CVOROVA LISTE koja ima %2d elemenata \n", PrebrojElementeListe() );
printf(" | | \n");
printf(" +-------------------------------------------------------+ \n");
printf(" | | \n");
printf(" | 1 - Sortiraj listu u rastucem redosledu | \n");
printf(" | | \n");
printf(" | 2 - Sortiraj listu u opadajucem redosledu | \n");
printf(" | | \n");
printf(" | 3 - Umetanje novog cvora u rastuce sortiranu listu | \n");
printf(" | | \n");
printf(" | 4 - Umetanje novog cvora u opadajuce sortiranu listu | \n");
printf(" | | \n");
printf(" | 5 - | \n");
printf(" | | \n");
printf(" | 6 - | \n");
printf(" | | \n");
printf(" | 7 - | \n");
printf(" | | \n");
printf(" | 8 - | \n");
printf(" | | \n");
printf(" | 9 - | \n");
printf(" | | \n");
printf(" | 10 - | \n");
printf(" | | \n");
printf(" | 11 - | \n");
printf(" | | \n");
printf(" | 12 - | \n");
printf(" | | \n");
printf(" | 0 - Izlaz | \n");
printf(" | | \n");
printf(" +-------------------------------------------------------+ \n");
printf("\n\t Izbor (0-12): ");
scanf("%d", &izbor);
switch(izbor){
case 1: // Sortiraj listu u rastucem redosledu
glava = SortirajURastuciRedosled( glava );
break;
case 2: // Sortiraj listu u opadajucem redosledu
glava = SortirajUOpadajuciRedosled( glava );
break;
case 3: // Umetanje novog cvora u rastuce sortiranu listu
printf("\n\n Unesi vrednost novog elementa: x = ");
scanf("%d",&x);
glava = DodajURastuceSortiranuListu( glava, x );
break;
case 4: // Umetanje novog cvora u opadajuce sortiranu listu
printf("\n\n Unesi vrednost novog elementa: x = ");
scanf("%d",&x);
glava = DodajUOpadajuceSortiranuListu( glava, x );
break;
case 5: //
break;
case 6: //
break;
case 7: //
break;
case 8: //
break;
case 9: //
break;
case 10: //
break;
case 11: //
break;
case 12: //
break;
case 0: // Izlaz
return 0;
break;
default :
printf("\n\n \t Morate izabrati (0-12) ! \n\n");
break;
} // switch(izbor)
} // while(1)
} // SortiranjeCvorova() // Meny za sortiranje cvorova
// Meny za brisanje cvorova
int BrisanjeCvorova(void)
{
int izbor, x, y;
while(1){
system("CLS");
prikaz_liste();
printf("\n\n +-------------------------------------------------------+ \n");
printf(" | | \n");
printf(" | BRISI CVOROVE LISTE koja ima %2d elemenata \n", PrebrojElementeListe() );
printf(" | | \n");
printf(" +-------------------------------------------------------+ \n");
printf(" | | \n");
printf(" | 1 - celu listu (sve cvorove u listi) | \n");
printf(" | | \n");
printf(" | 2 - glavu (prvi u listi) | \n");
printf(" | | \n");
printf(" | 3 - rep (poslednji u listi) | \n");
printf(" | | \n");
printf(" | 4 - prvi sa vrednoscu x | \n");
printf(" | | \n");
printf(" | 5 - prvih k sa vrednoscu x | \n");
printf(" | | \n");
printf(" | 6 - sve sa vrednoscu x | \n");
printf(" | | \n");
printf(" | 7 - sve vece od x | \n");
printf(" | | \n");
printf(" | 8 - sve manje od x | \n");
printf(" | | \n");
printf(" | 9 - sve u intervalu [x,y] | \n");
printf(" | | \n");
printf(" | 10 - element sa rednim brojem k | \n");
printf(" | | \n");
printf(" | 11 - sve parne | \n");
printf(" | | \n");
printf(" | 12 - sve neparne | \n");
printf(" | | \n");
printf(" | 0 - Izlaz | \n");
printf(" | | \n");
printf(" +-------------------------------------------------------+ \n");
printf("\n\t Izbor (0-12): ");
scanf("%d", &izbor);
switch(izbor){
case 1: // celu listu (sve cvorove u listi)
BrisiSveCvorove();
break;
case 2: // glavu (prvi u listi)
BrisiPrvi();
break;
case 3: // rep (poslednji u listi)
BrisiPoslednji();
break;
case 4: // prvi sa vrednoscu x
printf("\n\n Unesite vrednost cvora ciju prvu pojavu brisete: ");
scanf("%d", &x );
BrisiPrviSaVrednoscuX( x );
break;
case 5: // prvih k sa vrednoscu x
break;
case 6: // sve sa vrednoscu x
printf("\n\n Unesite vrednost cvora cije sve pojave brisete: ");
scanf("%d", &x );
BrisiSveSaVrednoscuX( x );
break;
case 7: // sve vece od x
break;
case 8: // sve manje od x
break;
case 9: // sve u intervalu [x,y]
break;
case 10: // element sa rednim brojem k
printf("\n\n Unesi redni broj elementa koji brises, k = ");
scanf ("%d",&x);
glava = ObrisiCvorCijiJeRedniBrojK( glava , x );
break;
case 11: // sve parne
break;
case 12: // sve neparne
break;
case 0: // Izlaz
return 0;
break;
default :
printf("\n\n \t Morate izabrati (0-12) ! \n\n");
break;
} // switch(izbor)
} // while(1)
} // BrisanjeCvorova() // Meny za brisanje cvorova
// Glavni program ( glavni Meny )
int main(void)
{
int izbor, x;
napravi_listu();
while(1){
system("CLS");
// prikaz_liste_sa_pointerima();
prikaz_liste();
printf("\n\n +-------------------------------------------------------+ \n");
printf(" | | \n");
printf(" | RAD SA LISTOM od %2d elemenata \n", PrebrojElementeListe() );
printf(" | | \n");
printf(" +-------------------------------------------------------+ \n");
printf(" | | \n");
printf(" | 1 - Novi cvor na pocetak liste | \n");
printf(" | | \n");
printf(" | 2 - Novi cvor posle cvora ciji je sadrzaj x | \n");
printf(" | | \n");
printf(" | 3 - Novi cvor na kraj liste | \n");
printf(" | | \n");
printf(" | 4 - Brisanje cvorova ( meny ) | \n");
printf(" | | \n");
printf(" | 5 - Obrtanje redosleda cvorova liste | \n");
printf(" | | \n");
printf(" | 6 - Sortiranje cvorova ( meny ) | \n");
printf(" | | \n");
printf(" | 7 - Napravi novu listu | \n");
printf(" | | \n");
printf(" | 0 - Kraj rada | \n");
printf(" | | \n");
printf(" +-------------------------------------------------------+ \n");
printf("\n\t Izbor: (0-7): ");
scanf("%d", &izbor);
switch(izbor){
case 1: NoviNaPocetak(); // Novi cvor na pocetak liste
break;
case 2: UmetniPosleX(); // Umetanje novog cvora posle cvora ciji je sadrzaj x
break;
case 3: NoviNaKraj(); // Novi cvor na kraj liste
break;
case 4: BrisanjeCvorova(); // Brisanje cvorova (meny)
break;
case 5: glava = ObrniRedosled( glava ); // Obrtanje redosleda cvorova liste
break;
case 6: SortiranjeCvorova(); // Sortiranje cvorova ( meny )
break;
case 7: napravi_listu(); // Napravi novu listu
break;
case 0: // Kraj rada
exit(0);
break;
default :
printf("\n\n \t Morate izabrati (0-7) ! \n\n");
break;
} // switch(izbor)
} // while(1)
printf("\n\n");
system("PAUSE");
system("del *.o");
return 0;
} // Glavni program ( glavni Meny )