API tools faq
paste
Advertisement
dmilicev

single-linked lists

dmilicev
Sep 19th, 2019
237
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 39.64 KB | None | 0 0
raw download clone embed print report
  1.  
  2. /*
  3.  
  4.     JSL - Jednostruko spregnute liste - DOKTORAT
  5.  
  6. Sa menijem.
  7. Sa globalnim promenljivama.
  8.  
  9. */
  10.  
  11. #include <stdio.h>
  12. #include <stdlib.h>         // zbog malloc(), calloc(), realloc(), free()
  13. // #include <malloc.h>      // ne treba
  14.  
  15.  
  16. typedef struct cvor{
  17.     int broj;
  18.     struct cvor *sledeci;
  19. } Cvor;
  20.  
  21. Cvor *glava, *novi, *tek;      // deklarisemo tri cvora:
  22. // glava - pocetni cvor, pocetak liste
  23. // novi - pomocni cvor, za stvaranje novih cvorova
  24. // tek - tekuci cvor, za obilazak tj. kretenje kroz listu
  25.  
  26.  
  27. /*
  28.  
  29. struct cvor {
  30.     int broj;
  31.     struct cvor* sledeci;   // sada je tip podatka struct cvor
  32. };
  33.  
  34. typedef struct cvor CVOR;   // sada tip podatka umesto struct cvor postaje samo CVOR
  35.  
  36. typedef CVOR* PCVOR;
  37.  
  38. */
  39.  
  40.  
  41. // Vraca 1 ako je lista prazna, inace vraca 0.
  42. int ListaJePrazna(void)
  43. {
  44.     if( glava == NULL ){        // ako nema clanova u listi tj. ako je lista prazna
  45.         printf(" Lista je prazna.\n\n");
  46.         return 1;
  47.     }
  48.     else    return 0;
  49. } // ListaJePrazna()
  50.  
  51.  
  52. /*
  53. Prolazak kroz listu:
  54. U radu sa listama cesto je potrebno kretati se kroz listu, od elementa do elementa.
  55. Najcesce je u pitanju obrada podataka u listi, pretraga liste kako bi se nasao
  56. odgovarajuci element ili trazenje kraja liste.
  57. U svim ovim slucajevima algoritam je slican.
  58. Uvodi se pomocni pokazivac koji je inicijalno jednak glavi liste,
  59. tj. pokazuje na prvi element liste ako ona nije prazna.
  60. Nakon provere da li pokazivac pokazuje na neki element (ima vrednost razlicitu od NULL),
  61. vrsi obrada podatka u tom elementu (stampa, uporedjivanje, racun...).
  62. Po zavrsetku obrade podatka, pomocni pokazivac dobija vrednost pokazivaca na sledeci element,
  63. a citav postupak se ponavlja sve dok pomocni pokazivac ima nenultu vrednost,
  64. tj. dok pokazuje na neki element.
  65. Kada pomocni pokazivac dobije vrednost NULL, to znaci da smo dosli do kraja liste.
  66. */
  67. // Prolazi kroz celu listu i broji elemente liste.
  68. int PrebrojElementeListe()
  69. {
  70.     int BrojElemenataListe=0;
  71.  
  72.     tek = glava;            // tekuci clan se postavlja na glavu
  73.  
  74.     while( tek ){       // za sve clanove liste ( dok tek ne bude NULL tj. poslednji )
  75.  
  76.         BrojElemenataListe++;   // uvecavamo broj clanova liste
  77.  
  78.         tek = tek->sledeci;     // prelazimo na sledeci clan liste
  79.     }
  80.  
  81.     return BrojElemenataListe;
  82. } // PrebrojElementeListe()
  83.  
  84.  
  85. // Stvaranje novog cvora, unos se vrsi u cvor novi
  86. void novicvor(){
  87.  
  88.     novi = (Cvor*)malloc( sizeof(Cvor) );   // rezervisanje memorije za cvor novi
  89.  
  90.     printf("\n\n Unesi novi->broj :  ");    // unos novi->broj tj. sadrzaja novog cvora
  91.     scanf("%d", &novi->broj);               // ovde treba ubaciti proveru da li je unet integer !!!
  92.  
  93.     novi->sledeci = NULL;                   // novi je novi cvor i za sada pokazuje na NULL
  94. } // novicvor()
  95.  
  96.  
  97. // Dodavanje novog cvora novi na pocetak liste
  98. void NoviNaPocetak(){
  99.  
  100.     novicvor();             // unos novog cvora u novi
  101.  
  102.     if( glava == NULL ){        // ako nema clanova u listi tj. ako je lista prazna
  103.         glava=novi;             // onda je glava novi clan (vec pokazuje na NULL)
  104.     }
  105.     else{                   // ako ima clanova u listi tj. ako lista nije prazna
  106.         novi->sledeci=glava;    // novi clan pokazuje na dosadasnju glavu
  107.         glava=novi;             // glava postaje novi clan
  108.     }
  109. } // NoviNaPocetak()
  110.  
  111.  
  112. // Prikazuje celu listu, svaki clan liste u novom redu i ujedno broji clanove liste.
  113. // Za svaki cvor prikazuje sadrzaj i pointer na sledeceg. Vraca broj clanova liste.
  114. int prikaz_liste_sa_pointerima(){
  115.  
  116.     int br_clanova_liste=0;     // sluzi za prebrojavanje clanova liste
  117.  
  118.     printf("\n\n");         // novi red
  119.  
  120.     if( glava == NULL )         // ako nema clanova u listi tj. ako je lista prazna
  121.         printf(" Lista je prazna.\n\n");
  122.     else{                   // ako ima clanova u listi tj. ako lista nije prazna
  123.         tek = glava;            // tekuci clan se postavlja na glavu
  124.         printf("\t\t | tek->broj - tek->sledeci | \n\n");   // prikaz zaglavlja liste
  125.  
  126.         while( tek ){       // za sve clanove liste ( dok tek ne bude NULL tj. poslednji )
  127.  
  128.             br_clanova_liste++;     // uvecavamo broj clanova liste
  129.  
  130.             printf("\n \t %2d. \t | %5d     -  %p  | \n",
  131.                    br_clanova_liste, tek->broj, tek->sledeci );   // prikazujemo clana liste
  132.  
  133.             tek = tek->sledeci;     // prelazimo na sledeci clan liste
  134.  
  135.         } // while( tek )
  136.     } // else               // ako ima clanova u listi tj. ako lista nije prazna
  137.  
  138. //    printf("\n\n Lista ima %d elemenata. \n\n", br_clanova_liste );
  139.  
  140.     return( br_clanova_liste );
  141. } // prikaz_liste_sa_pointerima()
  142.  
  143.  
  144. // Prikazuje samo sadrzaje cvorova u jednom redu i ujedno broji clanove liste.
  145. // Vraca broj clanova liste.
  146. int prikaz_liste(void){
  147.  
  148.     int br_clanova_liste=0;     // sluzi za prebrojavanje clanova liste
  149.  
  150.     printf("\n\n");             // novi red
  151.  
  152.     if( glava == NULL )         // ako nema clanova u listi tj. ako je lista prazna
  153.         printf(" Lista je prazna.\n\n");
  154.     else{                   // ako ima clanova u listi tj. ako lista nije prazna
  155.         tek = glava;            // tekuci clan se postavlja na glavu
  156.  
  157.         while( tek ){       // za sve clanove liste ( dok tek ne bude NULL tj. poslednji )
  158.  
  159.             br_clanova_liste++;     // uvecavamo broj clanova liste
  160.  
  161.             printf("%4d", tek->broj );     // prikazujemo sadrzaj tekuceg cvora
  162.  
  163.             tek = tek->sledeci;     // prelazimo na sledeci clan liste
  164.         }
  165.     }
  166.  
  167. //    printf("\n\n\n   Lista ima %d elemenata. \n\n", br_clanova_liste );
  168.  
  169.     printf("\n\n");             // novi red
  170.  
  171.     return( br_clanova_liste );
  172. } // prikaz_liste()
  173.  
  174.  
  175. // Umetanje novog cvora posle cvora ciji je sadrzaj x
  176. int UmetniPosleX(){
  177.  
  178.     int x;
  179.  
  180.     printf("\n\n");         // novi red
  181.  
  182.     printf("\n\n Novi cvor unesi posle cvora koji ima vrednost, x = ");
  183.     scanf("%d", &x);
  184.  
  185.     novicvor();             // unos novog cvora u novi
  186.  
  187.     if( glava == NULL ){        // ako nema clanova u listi
  188.         printf("\n\n Lista je prazna!!! \n\n");
  189.         system("PAUSE");
  190.         return(0);
  191.     }
  192.     else{                   // ako ima clanova u listi
  193.  
  194.         tek = glava;                // postavimo se na prvi clan liste
  195.  
  196.         while( tek->broj != x && tek->sledeci != NULL ){ // do kraja liste ili do clana ciji je sadrzaj x
  197.             tek = tek->sledeci;     // prelazimo na sledeci cvor
  198.         }
  199.         // sada smo na cvoru ciji je sadrzaj x
  200.         // on je pokazivao na svog sledeceg clana
  201.         // a sada treba da pokazuje na novi
  202.         // a novi treba da pokazuje na clana na kojeg je dosad pokazivao cvor x
  203.         // ili, jednostavnije:
  204.         // x je pokazivao na c
  205.         // sada x treba da pokazuje na novi
  206.         // a novi treba da pokazuje na c
  207.  
  208.         novi->sledeci = tek->sledeci;
  209.         tek->sledeci = novi;
  210.     }
  211. } // UmetniPosleX()
  212.  
  213.  
  214. // Dodavanje novog cvora novi na kraj liste
  215. void NoviNaKraj(){
  216.  
  217.     novicvor();         // unos novog cvora u novi
  218.  
  219.     if( glava == NULL ){  // ako nema clanova u listi tj. ako je lista prazna
  220.         glava=novi;         // onda taj novouneti clan novi postaje pocetak liste (glava)
  221.     }                       // ( a ujedno je i kraj liste jer je jedini )
  222.     else{                 // ako ima clanova u listi tj. ako lista nije prazna
  223.         tek = glava;        // postavimo se na prvi clan liste
  224.  
  225.         while( tek->sledeci != NULL ){  // dok se ne dodje do poslednjeg clana liste
  226.             tek = tek->sledeci;         // prelazimo na sledeci clan liste
  227.         }
  228.                                 // sada je tekuci clan (tek) poslednji clan liste,
  229.         tek->sledeci = novi;    // i on treba da pokazuje na novouneti clan novi
  230.     }
  231. } // NoviNaKraj()
  232.  
  233.  
  234. // Brisanje pocetnog (prvog) cvora u listi, brisanje glave
  235.  
  236. void BrisiPrvi(){
  237.  
  238.     if( glava == NULL ){   // ako nema clanova u listi tj. ako je lista prazna
  239.         printf("\n\n Lista je prazna! Nemoguce brisanje !!! \n\n");
  240.         system("PAUSE");
  241.     }
  242.     else{           // ako ima clanova u listi tj. ako lista nije prazna
  243.         novi = glava;      // pocetni clan glava pamtimo u pomocni clan novi zbog oslobadjanja memorije
  244.         glava = glava->sledeci;   // drugi clan postaje prvi, tj. novi pocetni clan glava postaje njegov (bivsi) sledeci clan
  245.         free(novi);          // oslobadjamo memoriju koja je bila rezervisana za pomocni clan novi
  246.     }                       // (tu smo zapamtili bivsi pocetni clan glava)
  247. } // BrisiPrvi()
  248.  
  249.  
  250. // Brisanje poslednjeg cvora u listi
  251. void BrisiPoslednji(){
  252.  
  253.     if( glava == NULL ) {       // ako nema clanova u listi tj. ako je lista prazna
  254.         printf("\n\n Lista je prazna! Nemoguce brisanje!!! \n\n");
  255.         system("PAUSE");
  256.     }
  257.     else{                   // ako ima clanova u listi tj. ako lista nije prazna
  258.         tek=glava;                // postavimo se na prvi clan liste
  259.  
  260.         if(tek->sledeci != NULL){ // ako postoji sledeci clan
  261.  
  262.             while(tek->sledeci->sledeci != NULL){   // do pretposlednjeg clana
  263.                 tek=tek->sledeci;                 // predji na sledeci clan
  264.             }
  265.                                 // sada je tekuci clan (tek) pretposlednji clan liste
  266.             novi = tek->sledeci;  // u novi pamtimo adresu poslednjeg clana liste
  267.                                 // zbog oslobadjanja memorije (njega brisemo)
  268.  
  269.             tek->sledeci = NULL;  // pretposlednji clan tek nema sledeceg i zato pokazuje na NULL
  270.  
  271.             free(novi);  // oslobadjamo memoriju koju je zauzimao bivsi poslednji clan liste
  272.         }               // jer smo ga obrisali i on nam vise ne treba
  273.         else{ // ako ne postoji sledeci clan, tj. tek je jedini clan u listi, i prvi i poslednji
  274.             BrisiPrvi();    // onda brisemo taj jedini clan liste
  275.         }
  276.     }
  277. } // BrisiPoslednji()
  278.  
  279.  
  280. // Brise sve cvorove liste i oslobadja memoriju koju su cvorovi zauzimali
  281. void BrisiSveCvorove()
  282. {
  283.     while( ( tek = glava ) != NULL ){  // dok glava postoji, brisemo glavu
  284.  
  285.         novi = glava;      // pocetni clan glava pamtimo u pomocni clan novi zbog oslobadjanja memorije
  286.         glava = glava->sledeci;   // drugi clan postaje prvi, tj. novi pocetni clan glava postaje njegov (bivsi) sledeci clan
  287.         free(novi);          // oslobadjamo memoriju koja je bila rezervisana za pomocni clan novi
  288.     }
  289. } // BrisiSveCvorove()
  290.  
  291.  
  292. /*
  293. Brisanje elementa iz liste:
  294. Da bi smo obrisali odredjeni element x iz liste, potrebno je da znamo njegovu poziciju u listi.
  295. Krecemo se kroz listu dok tekuci element ne bude onaj koji brisemo ( tek->broj = x ).
  296. Potrebno je da znamo i pokazivac na prethodni element u listi, kako bi smo njegovom linku
  297. dodelili pokazivac na element koji sledi elementu koji brisemo.
  298. Nakon toga mozemo da obrisemo trazeni element, odnosno da oslobodimo memoriju koju on zauzima.
  299. */
  300. // Brise prvi cvor koji ima sadrzaj x i oslobadja memoriju koju je taj cvor zauzimao.
  301. // Vraca BrojObrisanih cvorova.
  302. int BrisiPrviSaVrednoscuX( int x )
  303. {
  304.     int BrojObrisanih=0;
  305.  
  306.     if( glava == NULL ) {   // ako nema clanova u listi tj. ako je lista prazna
  307.         printf("\n\n Lista je prazna! Nemoguce brisanje!!! \n\n");
  308.         system("PAUSE");
  309.     }
  310.     else {                  // ako ima clanova u listi tj. ako lista nije prazna
  311.  
  312.         tek = glava;                // postavimo se na prvi clan liste
  313.  
  314.         if( tek->broj == x ) {  // ako je sadrzaj glave x
  315.             BrisiPrvi();
  316.         }
  317.         else {                  // ako sadrzaj glave nije x
  318.                                 // do kraja liste ili do clana ciji je sadrzaj x
  319.             while( tek->broj != x && tek->sledeci != NULL ){
  320.                 printf("\n\n while tek->broj = %2d \n\n", tek->broj );
  321.                 novi = tek;             // u novi pamtimo prethodni od tek
  322.                 tek = tek->sledeci;     // prelazimo na sledeci cvor
  323.             }
  324.  
  325.                             // sada je tek cvor cija je vrednost x, novi je prethodni od tek
  326.             if( tek->broj == x ){   // ako postoji cvor ciji je sadrzaj x
  327.  
  328.                 novi->sledeci = tek->sledeci;// prethodni od tek pokazuje na sledeci od tek (jer tek brisemo)
  329.                 novi = tek;    // u novi pamtimo tek zbog brisanja i zbog oslobadjanja memorije (njega brisemo)
  330.                 free(novi);  // oslobadjamo memoriju koju je zauzimao bivsi poslednji clan liste
  331.                 BrojObrisanih++;
  332.             }
  333.             else {
  334.                 printf("\n\n U listi ne postoji cvor ciji je sadrzaj %2d ! \n\n", x );
  335.                 system("PAUSE");
  336.             }
  337.         } // ako je sadrzaj glave nije x
  338.     } // ako ima clanova u listi tj. ako lista nije prazna
  339.  
  340.     return BrojObrisanih;
  341. } // BrisiPrviSaVrednoscuX()
  342.  
  343.  
  344. // Brise zadati element iz liste.
  345. int BrisiPrviSaVrednoscuX_1( int x )
  346. {
  347.     int BrojObrisanih=0;
  348.  
  349.     if( glava == NULL ) {   // ako nema clanova u listi tj. ako je lista prazna
  350.         printf("\n\n Lista je prazna! Nemoguce brisanje!!! \n\n");
  351.         system("PAUSE");
  352.     }
  353.     else {                  // ako ima clanova u listi tj. ako lista nije prazna
  354.  
  355.         tek = glava;                // postavimo se na prvi clan liste
  356.  
  357.         if( tek->broj == x ) {  // ako je sadrzaj glave x
  358.             BrisiPrvi();
  359.         }
  360.         else {                  // ako sadrzaj glave nije x
  361.                                 // do kraja liste ili do clana ciji je sadrzaj x
  362.             while( tek->broj != x && tek->sledeci != NULL ){
  363.                 printf("\n\n while tek->broj = %2d \n\n", tek->broj );
  364.                 novi = tek;             // u novi pamtimo prethodni od tek
  365.                 tek = tek->sledeci;     // prelazimo na sledeci cvor
  366.             }
  367.  
  368.                             // sada je tek cvor cija je vrednost x, novi je prethodni od tek
  369.             if( tek->broj == x ){   // ako postoji cvor ciji je sadrzaj x
  370.  
  371.                 novi->sledeci = tek->sledeci;// prethodni od tek pokazuje na sledeci od tek (jer tek brisemo)
  372.                 novi = tek;    // u novi pamtimo tek zbog brisanja i zbog oslobadjanja memorije (njega brisemo)
  373.                 free(novi);  // oslobadjamo memoriju koju je zauzimao bivsi poslednji clan liste
  374.                 BrojObrisanih++;
  375.             }
  376.             else {
  377.                 printf("\n\n U listi ne postoji cvor ciji je sadrzaj %2d ! \n\n", x );
  378.                 system("PAUSE");
  379.             }
  380.         } // ako je sadrzaj glave nije x
  381.     } // ako ima clanova u listi tj. ako lista nije prazna
  382.  
  383.     return BrojObrisanih;
  384. } // BrisiPrviSaVrednoscuX_1()
  385.  
  386.  
  387. // Brise sve cvorove koji imaju sadrzaj x i oslobadja memoriju koju su ti cvorovi zauzimali.
  388. // Vraca BrojObrisanih cvorova.
  389. int BrisiSveSaVrednoscuX( int x ) {
  390.     Cvor *prethodni, *trenutni;
  391.     int BrojObrisanih=0;
  392.  
  393.     if( glava == NULL ) {   // ako nema clanova u listi tj. ako je lista prazna
  394.         printf("\n\n Lista je prazna! Nemoguce brisanje!!! \n\n");
  395.         system("PAUSE");
  396.     }
  397.     else {                  // ako ima clanova u listi tj. ako lista nije prazna
  398.  
  399.             trenutni = glava;                // postavimo se na prvi clan liste
  400.             prethodni = NULL;
  401.  
  402.             while( trenutni != NULL ){ // za sve clanove liste ( dok tek ne bude NULL tj. poslednji )
  403.  
  404.                 prethodni = trenutni;
  405. //                novi = trenutni;
  406.                 trenutni = trenutni->sledeci;
  407.  
  408. //                printf("\n\n while prethodni->broj = %d    trenutni->broj = %2d \n\n", prethodni->broj, trenutni->broj );
  409.  
  410.                 if ( trenutni->broj == x ){
  411. //                printf("\n\n if:  prethodni->broj = %d    trenutni->broj = %2d \n\n", prethodni->broj, trenutni->broj );
  412.                     // novi = trenutni;
  413.                     trenutni = trenutni->sledeci;
  414.                     prethodni->sledeci = trenutni;
  415. //                    printf("\n\n if:  prethodni->broj = %d    trenutni->broj = %2d novi->broj %d\n\n", prethodni->broj, trenutni->broj , novi->broj );
  416.                     //free(novi);  // oslobadjamo memoriju koju je zauzimao bivsi poslednji clan liste
  417.                     BrojObrisanih++;
  418.                 }
  419.  
  420. //                system("PAUSE");
  421.             }
  422.  
  423.     } // ako ima clanova u listi tj. ako lista nije prazna
  424.  
  425.     if( BrojObrisanih == 0 ){
  426.         printf("\n\n U listi ne postoji cvor ciji je sadrzaj %2d ! \n\n", x );
  427.         system("PAUSE");
  428.     }
  429.  
  430.     return BrojObrisanih;
  431. } // BrisiSveSaVrednoscuX()
  432.  
  433.  
  434. // Brisanje elementa po rednom broju u listi
  435. Cvor *ObrisiCvorCijiJeRedniBrojK( Cvor *p, int redni_broj )
  436. {
  437.     Cvor *prethodni, *trenutni;
  438.     int i;
  439.  
  440.     if (p == NULL ){        // ako je lista prazna
  441.         printf("Lista je prazna. \n");
  442.         system("PAUSE");
  443.     }
  444.     else                    // ako lista nije prazna
  445.     {
  446.         if ( redni_broj > PrebrojElementeListe(p) ){
  447.             printf("\n\n Redni broj %d je veci od broja elemenata liste %d ! \n\n",
  448.                    redni_broj, PrebrojElementeListe(p));
  449.             system("PAUSE");
  450.         }
  451.         else{
  452.             prethodni = NULL;
  453.             trenutni = p;
  454.             i = 1;
  455.  
  456.             while ( i < redni_broj ){
  457.                 prethodni = trenutni;
  458.                 trenutni = trenutni->sledeci;
  459.                 i = i+1;
  460.             }
  461.  
  462.             if ( prethodni == NULL ){
  463.                 p = trenutni->sledeci;
  464.                 free( trenutni );
  465.             }
  466.             else{
  467.                 prethodni->sledeci = trenutni->sledeci;
  468.                 free( trenutni );
  469.             }
  470.         } // else   // ( redni_broj <= PrebrojElementeListe(p) )
  471.     } // else   // ako lista nije prazna
  472.     return( p );
  473. } // ObrisiCvorCijiJeRedniBrojK()
  474.  
  475.  
  476. /*
  477. Sortiranje liste u rastuci redosled:
  478. Da bismo sortirali listu, prvo prolazimo kroz nju kako bismo pronasli element
  479. sa najmanjom vrednoscu podatka. Nakon toga uklanjamo taj element iz liste i
  480. dodajemo ga na kraj druge liste, koja je inicijalno bila prazna.
  481. Ovaj proces ponavljamo sve dok pocetna lista ne postane prazna.
  482. Na kraju ostaje samo da funkcija vrati pokazivac na listu u koju su prebaceni svi elementi.
  483. */
  484. // Sortira listu u rastucem redosledu
  485. Cvor *SortirajURastuciRedosled( Cvor *p )
  486. {
  487.     Cvor *pom1, *pom2, *min, *prethodni, *q;
  488.  
  489.     q = NULL;
  490.  
  491.     while( p != NULL )
  492.     {
  493.         prethodni = NULL;
  494.         min = pom1 = p;     // pretpostavljamo da je najmanji bas prvi element (glava)
  495.         pom2 = p->sledeci;
  496.  
  497.         while ( pom2 != NULL )
  498.         {
  499.             if( pom2->broj < min->broj )
  500.             {
  501.                 min = pom2;
  502.                 prethodni = pom1;
  503.             }
  504.  
  505.             pom1 = pom2;
  506.             pom2 = pom2->sledeci;
  507.         }
  508.         if(prethodni == NULL)
  509.             p = min->sledeci;
  510.         else
  511.             prethodni->sledeci = min->sledeci;
  512.  
  513.         min->sledeci = NULL;
  514.  
  515.         if( q == NULL )
  516.             q = min; // premesta element sa najmanjom vrednoscu podatka iz liste p na pocetak liste q
  517.         else
  518.         {
  519.             pom1 = q;
  520.                     // prolazi kroz listu q da bi pronasao njen poslednji element
  521.             while( pom1->sledeci != NULL )
  522.                 pom1 = pom1->sledeci;
  523.                     // premesta element sa najmanjom vrednoscu podatka iz liste p na kraj liste q
  524.             pom1->sledeci = min;
  525.         }
  526.     }
  527.     return ( q );
  528. } // SortirajURastuciRedosled()
  529.  
  530.  
  531. /*
  532. Sortiranje liste u opadajuci redosled:
  533. Da bismo sortirali listu, prvo prolazimo kroz nju kako bismo pronasli element
  534. sa najvecom vrednoscu podatka. Nakon toga uklanjamo taj element iz liste i
  535. dodajemo ga na pocetak druge liste, koja je inicijalno bila prazna.
  536. Ovaj proces ponavljamo sve dok pocetna lista ne postane prazna.
  537. Na kraju ostaje samo da funkcija vrati pokazivac na listu u koju su prebaceni svi elementi.
  538. */
  539. // Sortira listu u opadajucem redosledu
  540. Cvor *SortirajUOpadajuciRedosled( Cvor *p )
  541. {
  542.     Cvor *pom1, *pom2, *max, *prethodni, *q;
  543.  
  544.     q = NULL;
  545.  
  546.     while( p != NULL )      // do kraja liste
  547.     {
  548.         prethodni = NULL;
  549.         max = pom1 = p;     // pretpostavljamo da je najveci bas prvi element (glava)
  550.         pom2 = p->sledeci;
  551.  
  552.         while ( pom2 != NULL )
  553.         {
  554.             if( pom2->broj > max->broj )
  555.             {
  556.                 max = pom2;
  557.                 prethodni = pom1;
  558.             }
  559.  
  560.             pom1 = pom2;
  561.             pom2 = pom2->sledeci;
  562.         }
  563.         if( prethodni == NULL )
  564.             p = max->sledeci;
  565.         else
  566.             prethodni->sledeci = max->sledeci;
  567.  
  568.         max->sledeci = NULL;
  569.  
  570.         if( q == NULL )
  571.             q = max; // premesta element sa najvecom vrednoscu podatka iz liste p na pocetak liste q
  572.         else
  573.         {
  574.             pom1 = q;
  575.                     // prolazi kroz listu q da bi pronasao njen poslednji element
  576.             while( pom1->sledeci != NULL )
  577.                 pom1 = pom1->sledeci;
  578.                     // premesta element sa najvecom vrednoscu podatka iz liste p na kraj liste q
  579.             pom1->sledeci = max;
  580.         }
  581.     }
  582.     return ( q );
  583. } // SortirajUOpadajuciRedosled()
  584.  
  585.  
  586. // Pravi listu od 10 cvorova, da bi se izbegao pojedinacni unos cvorova (elemenata liste)
  587. void napravi_listu(void)
  588. {
  589.     int i;
  590.  
  591.     BrisiSveCvorove();  // Brise sve cvorove liste i oslobadja memoriju koju su cvorovi zauzimali
  592.             // sledece if je potrebno samo ako prethodno ne pozovemo BrisiSveCvorove()
  593.     if( glava == NULL ){  // ako nema clanova u listi tj. ako je lista prazna
  594.         for(i=1;i<=10;i++){
  595.  
  596.             novi=(Cvor*)malloc(sizeof(Cvor));    // rezervisanje memorije za novi cvor
  597.             novi->broj = i;
  598.             novi->sledeci = NULL;                // novi je novi cvor i za sada pokazuje na NULL
  599.  
  600.                 // formiran i-ti cvor dodjaemo na kraj liste
  601.             if( glava == NULL ){  // ako nema clanova u listi tj. ako je lista prazna
  602.                 glava=novi;        // onda taj novouneti clan novi postaje pocetak liste (glava)
  603.             }                   // ( a ujedno je i kraj liste jer je jedini )
  604.             else{           // ako ima clanova u listi tj. ako lista nije prazna
  605.                 tek=glava;        // postavimo se na prvi clan liste
  606.  
  607.                 while(tek->sledeci!=NULL){    // dok se ne dodje do poslednjeg clana liste
  608.                     tek=tek->sledeci;         // prelazimo na sledeci clan liste
  609.                 }
  610.                                     // sada je tekuci clan (tek) poslednji clan liste,
  611.                 tek->sledeci=novi;     // i on treba da pokazuje na novouneti clan novi
  612.             } // if( glava == NULL )
  613.         } // for(i=1;i<=6;i++)
  614.     } // if( glava == NULL )
  615.     else {
  616.         printf("\n\n Lista nije prazna. Prvo obrisite sve clanove liste ! \n\n");
  617.         system("PAUSE");
  618.     }
  619. } // napravi_listu()
  620.  
  621.  
  622. /*
  623. Krecemo se po listi od glave na desno.
  624. Prvo je trenutni element glava a prethodni element NULL (pocetne vrednosti).
  625. Zatim, do kraja liste ponavljamo:
  626.         sledeci     =   trenutni->sledeci;  // sledeci je onaj na koji pokazuje trenutni
  627. trenutni->sledeci   =   prethodni;          // trenutni sada pokazuje na prethodni
  628.           prethodni = trenutni;             // prethodni postaje trenutni
  629.            trenutni = sledeci;              // trenutni postaje sledeci (idemo na sledeci element)
  630. Okretanje redosleda u listi:
  631. Da bi smo izvrsili okretanje redosleda u listi, neophodno je da
  632. za svaki element znamo pokazivace na njegovog prethodnika i sledbenika.
  633. Nakon toga trenutni element proglasavamo za prethodnika,
  634. a njegovog sledbenika za trenutni.
  635. */
  636. // Obrce redosled cvorova liste
  637. Cvor *ObrniRedosled( Cvor *p )
  638. {
  639.     Cvor *prethodni, *trenutni, *sledeci;
  640.  
  641.     trenutni = p;       // trenutni je glava, prvi element u listi
  642.     prethodni = NULL;   // pocetna vrednost za prethodni
  643.  
  644.     while( trenutni != NULL )       // od glave do kraja liste
  645.     {
  646.         sledeci = trenutni->sledeci;    // sledeci je onaj na koji pokazuje trenutni
  647.         trenutni->sledeci = prethodni;  // trenutni sada pokazuje na prethodni
  648.         prethodni = trenutni;           // prethodni postaje trenutni
  649.         trenutni = sledeci;             // trenutni postaje sledeci (idemo na sledeci element)
  650.     }
  651.  
  652.     return prethodni;   // vraca prethodni jer je to sada glava (prvi element) liste
  653. } // ObrniRedosled()
  654.  
  655.  
  656. /*
  657. Umetanje novog elementa u rastuce sortiranu listu:
  658. Da bismo umetnuli novi element u listu koja je prethodno sortirana,
  659. uporedjujemo redom podatke u listi sa vrednoscu podatka novog elementa.
  660. Ovaj proces se ponavlja sve dok ne dobijemo pokazivac na element
  661. koji se nalazi ispred elementa ciji je podatak veci od podatka u novom elementu.
  662. */
  663. // Umece novi element u rastuce sortiranu listu
  664. Cvor *DodajURastuceSortiranuListu( Cvor *p, int x )
  665. {
  666.     Cvor *trenutni, *prethodni, *pom;
  667.  
  668.     trenutni = p;
  669.     prethodni = NULL;
  670.  
  671.     while( trenutni->broj < x )
  672.     {
  673.         prethodni = trenutni;
  674.  
  675.         if ( trenutni->sledeci != NULL )
  676.                 trenutni = trenutni->sledeci;
  677.         else
  678.             break;
  679.     }
  680.  
  681.     pom = (Cvor *) malloc( sizeof(Cvor) );
  682.  
  683.     if( pom == NULL )
  684.     {
  685.         printf("Greska pri alociranju memorije.\n");
  686.         exit(0);
  687.     }
  688.  
  689.     if ( prethodni == NULL ) // element ce biti umetnut na pocetak liste
  690.     {
  691.         pom->broj = x;
  692.         pom->sledeci = p;
  693.         p = pom;
  694.     }
  695.     else
  696.     {
  697.         pom->broj = x;
  698.         pom->sledeci = prethodni->sledeci;
  699.         prethodni->sledeci = pom;
  700.     }
  701.     return( p );
  702. } // DodajURastuceSortiranuListu
  703.  
  704.  
  705. /*
  706. Umetanje novog elementa u opadajuce sortiranu listu:
  707. Da bismo umetnuli novi element u listu koja je prethodno sortirana,
  708. uporedjujemo redom podatke u listi sa vrednoscu podatka novog elementa.
  709. Ovaj proces se ponavlja sve dok ne dobijemo pokazivac na element
  710. koji se nalazi iza elementa ciji je podatak veci od podatka u novom elementu.
  711. */
  712. // Umece novi element u opadajuce sortiranu listu
  713. Cvor *DodajUOpadajuceSortiranuListu( Cvor *p, int x )
  714. {
  715.     Cvor *trenutni, *prethodni, *pom;
  716.  
  717.     trenutni = p;
  718.     prethodni = NULL;
  719.  
  720.     while( trenutni->broj > x )
  721.     {
  722.         prethodni = trenutni;
  723.  
  724.         if ( trenutni->sledeci != NULL )
  725.                 trenutni = trenutni->sledeci;
  726.         else
  727.             break;
  728.     }
  729.  
  730.     pom = (Cvor *) malloc( sizeof(Cvor) );
  731.  
  732.     if( pom == NULL )
  733.     {
  734.         printf("Greska pri alociranju memorije.\n");
  735.         exit(0);
  736.     }
  737.  
  738.     if ( prethodni == NULL ) // element ce biti umetnut na pocetak liste
  739.     {
  740.         pom->broj = x;
  741.         pom->sledeci = p;
  742.         p = pom;
  743.     }
  744.     else
  745.     {
  746.         pom->broj = x;
  747.         pom->sledeci = prethodni->sledeci;
  748.         prethodni->sledeci = pom;
  749.     }
  750.     return( p );
  751. } // DodajUOpadajuceSortiranuListu()
  752.  
  753.  
  754. // Meny za sortiranje cvorova
  755. int SortiranjeCvorova(void)
  756. {
  757.     int izbor, x, y;
  758.  
  759.     while(1){
  760.         system("CLS");
  761.         prikaz_liste();
  762.  
  763.     printf("\n\n +-------------------------------------------------------+ \n");
  764.         printf(" |                                                       | \n");
  765.         printf(" |    SORTIRANJE CVOROVA LISTE koja ima %2d elemenata      \n", PrebrojElementeListe() );
  766.         printf(" |                                                       | \n");
  767.         printf(" +-------------------------------------------------------+ \n");
  768.         printf(" |                                                       | \n");
  769.         printf(" |  1 - Sortiraj listu u rastucem redosledu              | \n");
  770.         printf(" |                                                       | \n");
  771.         printf(" |  2 - Sortiraj listu u opadajucem redosledu            | \n");
  772.         printf(" |                                                       | \n");
  773.         printf(" |  3 - Umetanje novog cvora u rastuce sortiranu listu   | \n");
  774.         printf(" |                                                       | \n");
  775.         printf(" |  4 - Umetanje novog cvora u opadajuce sortiranu listu | \n");
  776.         printf(" |                                                       | \n");
  777.         printf(" |  5 -                                                  | \n");
  778.         printf(" |                                                       | \n");
  779.         printf(" |  6 -                                                  | \n");
  780.         printf(" |                                                       | \n");
  781.         printf(" |  7 -                                                  | \n");
  782.         printf(" |                                                       | \n");
  783.         printf(" |  8 -                                                  | \n");
  784.         printf(" |                                                       | \n");
  785.         printf(" |  9 -                                                  | \n");
  786.         printf(" |                                                       | \n");
  787.         printf(" | 10 -                                                  | \n");
  788.         printf(" |                                                       | \n");
  789.         printf(" | 11 -                                                  | \n");
  790.         printf(" |                                                       | \n");
  791.         printf(" | 12 -                                                  | \n");
  792.         printf(" |                                                       | \n");
  793.         printf(" |  0 - Izlaz                                            | \n");
  794.         printf(" |                                                       | \n");
  795.         printf(" +-------------------------------------------------------+ \n");
  796.  
  797.         printf("\n\t Izbor (0-12): ");
  798.         scanf("%d", &izbor);
  799.  
  800.         switch(izbor){
  801.             case  1:                    // Sortiraj listu u rastucem redosledu
  802.                      glava = SortirajURastuciRedosled( glava );
  803.                     break;
  804.             case  2:                    // Sortiraj listu u opadajucem redosledu
  805.                      glava = SortirajUOpadajuciRedosled( glava );
  806.                     break;
  807.             case  3:                    // Umetanje novog cvora u rastuce sortiranu listu
  808.                     printf("\n\n Unesi vrednost novog elementa: x = ");
  809.                     scanf("%d",&x);
  810.                     glava = DodajURastuceSortiranuListu( glava, x );
  811.                     break;
  812.             case  4:                    // Umetanje novog cvora u opadajuce sortiranu listu
  813.                     printf("\n\n Unesi vrednost novog elementa: x = ");
  814.                     scanf("%d",&x);
  815.                     glava = DodajUOpadajuceSortiranuListu( glava, x );
  816.                     break;
  817.             case  5:                    //
  818.  
  819.                     break;
  820.             case  6:                    //
  821.                     break;
  822.             case  7:                    //
  823.  
  824.                     break;
  825.             case  8:                    //
  826.  
  827.                     break;
  828.             case  9:                    //
  829.  
  830.                     break;
  831.             case 10:                    //
  832.                     break;
  833.             case 11:                    //
  834.  
  835.                     break;
  836.             case 12:                    //
  837.  
  838.                     break;
  839.             case  0:                    // Izlaz
  840.                     return 0;
  841.                     break;
  842.             default :
  843.                     printf("\n\n \t Morate izabrati (0-12) ! \n\n");
  844.                     break;
  845.         } // switch(izbor)
  846.     } // while(1)
  847. } // SortiranjeCvorova()    // Meny za sortiranje cvorova
  848.  
  849.  
  850. // Meny za brisanje cvorova
  851. int BrisanjeCvorova(void)
  852. {
  853.     int izbor, x, y;
  854.  
  855.     while(1){
  856.         system("CLS");
  857.         prikaz_liste();
  858.  
  859.     printf("\n\n +-------------------------------------------------------+ \n");
  860.         printf(" |                                                       | \n");
  861.         printf(" |      BRISI CVOROVE LISTE koja ima %2d elemenata         \n", PrebrojElementeListe() );
  862.         printf(" |                                                       | \n");
  863.         printf(" +-------------------------------------------------------+ \n");
  864.         printf(" |                                                       | \n");
  865.         printf(" |  1 - celu listu (sve cvorove u listi)                 | \n");
  866.         printf(" |                                                       | \n");
  867.         printf(" |  2 - glavu      (prvi u listi)                        | \n");
  868.         printf(" |                                                       | \n");
  869.         printf(" |  3 - rep        (poslednji u listi)                   | \n");
  870.         printf(" |                                                       | \n");
  871.         printf(" |  4 - prvi sa vrednoscu x                              | \n");
  872.         printf(" |                                                       | \n");
  873.         printf(" |  5 - prvih k sa vrednoscu x                           | \n");
  874.         printf(" |                                                       | \n");
  875.         printf(" |  6 - sve sa vrednoscu x                               | \n");
  876.         printf(" |                                                       | \n");
  877.         printf(" |  7 - sve vece od x                                    | \n");
  878.         printf(" |                                                       | \n");
  879.         printf(" |  8 - sve manje od x                                   | \n");
  880.         printf(" |                                                       | \n");
  881.         printf(" |  9 - sve u intervalu [x,y]                            | \n");
  882.         printf(" |                                                       | \n");
  883.         printf(" | 10 - element sa rednim brojem k                       | \n");
  884.         printf(" |                                                       | \n");
  885.         printf(" | 11 - sve parne                                        | \n");
  886.         printf(" |                                                       | \n");
  887.         printf(" | 12 - sve neparne                                      | \n");
  888.         printf(" |                                                       | \n");
  889.         printf(" |  0 - Izlaz                                            | \n");
  890.         printf(" |                                                       | \n");
  891.         printf(" +-------------------------------------------------------+ \n");
  892.  
  893.         printf("\n\t Izbor (0-12): ");
  894.         scanf("%d", &izbor);
  895.  
  896.         switch(izbor){
  897.             case  1:                    // celu listu (sve cvorove u listi)
  898.                     BrisiSveCvorove();
  899.                     break;
  900.             case  2:                    // glavu      (prvi u listi)
  901.                     BrisiPrvi();
  902.                     break;
  903.             case  3:                    // rep        (poslednji u listi)
  904.                     BrisiPoslednji();
  905.                     break;
  906.             case  4:                    // prvi sa vrednoscu x
  907.                     printf("\n\n Unesite vrednost cvora ciju prvu pojavu brisete: ");
  908.                     scanf("%d", &x );
  909.                     BrisiPrviSaVrednoscuX( x );
  910.                     break;
  911.             case  5:                    // prvih k sa vrednoscu x
  912.  
  913.                     break;
  914.             case  6:                    // sve sa vrednoscu x
  915.                     printf("\n\n Unesite vrednost cvora cije sve pojave brisete: ");
  916.                     scanf("%d", &x );
  917.                     BrisiSveSaVrednoscuX( x );
  918.                     break;
  919.             case  7:                    // sve vece od x
  920.  
  921.                     break;
  922.             case  8:                    // sve manje od x
  923.  
  924.                     break;
  925.             case  9:                    // sve u intervalu [x,y]
  926.  
  927.                     break;
  928.             case 10:                    // element sa rednim brojem k
  929.                     printf("\n\n Unesi redni broj elementa koji brises, k = ");
  930.                     scanf ("%d",&x);
  931.                     glava = ObrisiCvorCijiJeRedniBrojK( glava , x );
  932.                     break;
  933.             case 11:                    // sve parne
  934.  
  935.                     break;
  936.             case 12:                    // sve neparne
  937.  
  938.                     break;
  939.             case  0:                    // Izlaz
  940.                     return 0;
  941.                     break;
  942.             default :
  943.                     printf("\n\n \t Morate izabrati (0-12) ! \n\n");
  944.                     break;
  945.         } // switch(izbor)
  946.     } // while(1)
  947. } // BrisanjeCvorova()  // Meny za brisanje cvorova
  948.  
  949.  
  950.  
  951.  
  952. // Glavni program ( glavni Meny )
  953. int main(void)
  954. {
  955.     int izbor, x;
  956.  
  957.     napravi_listu();
  958.  
  959.     while(1){
  960.         system("CLS");
  961. //        prikaz_liste_sa_pointerima();
  962.         prikaz_liste();
  963.  
  964.     printf("\n\n +-------------------------------------------------------+ \n");
  965.         printf(" |                                                       | \n");
  966.         printf(" |      RAD SA LISTOM od %2d elemenata                     \n", PrebrojElementeListe() );
  967.         printf(" |                                                       | \n");
  968.         printf(" +-------------------------------------------------------+ \n");
  969.         printf(" |                                                       | \n");
  970.         printf(" |  1 - Novi cvor na pocetak liste                       | \n");
  971.         printf(" |                                                       | \n");
  972.         printf(" |  2 - Novi cvor posle cvora ciji je sadrzaj x          | \n");
  973.         printf(" |                                                       | \n");
  974.         printf(" |  3 - Novi cvor na kraj liste                          | \n");
  975.         printf(" |                                                       | \n");
  976.         printf(" |  4 - Brisanje cvorova ( meny )                        | \n");
  977.         printf(" |                                                       | \n");
  978.         printf(" |  5 - Obrtanje redosleda cvorova liste                 | \n");
  979.         printf(" |                                                       | \n");
  980.         printf(" |  6 - Sortiranje cvorova ( meny )                      | \n");
  981.         printf(" |                                                       | \n");
  982.         printf(" |  7 - Napravi novu listu                               | \n");
  983.         printf(" |                                                       | \n");
  984.         printf(" |  0 - Kraj rada                                        | \n");
  985.         printf(" |                                                       | \n");
  986.         printf(" +-------------------------------------------------------+ \n");
  987.  
  988.         printf("\n\t Izbor: (0-7): ");
  989.         scanf("%d", &izbor);
  990.  
  991.         switch(izbor){
  992.             case 1: NoviNaPocetak();    // Novi cvor na pocetak liste
  993.                     break;
  994.             case 2: UmetniPosleX();     // Umetanje novog cvora posle cvora ciji je sadrzaj x
  995.                     break;
  996.             case 3: NoviNaKraj();       // Novi cvor na kraj liste
  997.                     break;
  998.             case 4: BrisanjeCvorova();  // Brisanje cvorova (meny)
  999.                     break;
  1000.             case 5: glava = ObrniRedosled( glava ); // Obrtanje redosleda cvorova liste
  1001.                     break;
  1002.             case 6: SortiranjeCvorova();    // Sortiranje cvorova ( meny )
  1003.                     break;
  1004.             case 7: napravi_listu();    // Napravi novu listu
  1005.                     break;
  1006.             case 0:                     // Kraj rada
  1007.                     exit(0);
  1008.                     break;
  1009.             default :
  1010.                     printf("\n\n \t Morate izabrati (0-7) ! \n\n");
  1011.                     break;
  1012.         } // switch(izbor)
  1013.     } // while(1)
  1014.  
  1015.  
  1016.  
  1017.     printf("\n\n");
  1018.     system("PAUSE");
  1019.     system("del *.o");
  1020.     return 0;
  1021. } // Glavni program ( glavni Meny )
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!