Obojsmerný lineárny zoznam

Riešenie

Úloha 15

Uvedieme len funkcie, ktorými sa realizujú niektoré operácie so zoznamom, ako aj príklady volania týchto funkcií. Všimnite si dobre najmä zvýraznené časti kódu!

#include <stdlib.h>
#include <stdio.h>

/* definícia typu */
typedef struct uzol {
   int hodnota;
   struct uzol *nasled;
   struct uzol *predch;
} TUzol;
-------------------------------------------------------------------------------------
void pridaj_na_koniec(TUzol **z, TUzol **k)
{
   TUzol *novy;

   if (*z == NULL) {
    *z = (TUzol*)malloc(sizeof(TUzol));
    scanf("%d", &((*z)->hodnota));
    (*z)->nasled = NULL;
    (*z)->predch = NULL;
    *k = *z;
   }
   else {
     novy = (TUzol*)malloc(sizeof(TUzol));
     scanf("%d", &(novy->hodnota));
     novy->nasled = NULL;
     (*k)->nasled = novy;
     novy->predch = *k;
     *k = novy;
   }
}
-------------------------------------------------------------------------------------
void pridaj_na_zaciatok(TUzol **z, TUzol **k)
{
  TUzol *novy;

  if (*z == NULL) {
    *z = (TUzol*)malloc(sizeof(TUzol));
    scanf("%d", &((*z)->hodnota));
    (*z)->nasled = NULL;
    (*z)->predch = NULL;
     *k = *z;
   }
   else {
     novy = (TUzol*)malloc(sizeof(TUzol));
     scanf("%d", &(novy->hodnota));
     novy->nasled = *z;
     novy->predch = NULL;
     *z = novy;
   }
}
-------------------------------------------------------------------------------------
void vloz_za(TUzol **z, TUzol **k, TUzol *za)
{
   TUzol *novy;

   /* pointer za ukazuje na prvok ZA ktorý vložíme nový */
   
   if  (za == *k) pridaj_na_koniec(z, k);
   else {
       novy = (TUzol*)malloc(sizeof(TUzol));
       scanf("%d", &(novy->hodnota));

       novy->nasled = za->nasled;
       novy->nasled->predch = novy;
       za->nasled = novy;
       novy->predch = za;
   }
}
-------------------------------------------------------------------------------------
void odstran(TUzol **z, TUzol **k, TUzol *ten)
{
     if (ten == NULL) {
       printf("Error!");
       exit(1);
     }

    if (ten == *z) {
       *z = (*z)->nasled;    /* nový začiatok */
       (*z)->predch = NULL;
    }
    else
      if (ten == *k) {
        *k = (*k)->predch;   /* nový koniec */
        (*k)->nasled = NULL;
      }
      else {
        ten->predch->nasled = ten->nasled;
        ten->nasled->predch = ten->predch;
      }
   free((void*)ten);
}
-------------------------------------------------------------------------------------
void vypis_od_zac(TUzol *z) 
{
   while (z != NULL) {
     printf("%d  ", z->hodnota);
     z = z->nasled;
   }
}
-------------------------------------------------------------------------------------
void vypis_od_kon(TUzol *k) 
{
   while (k != NULL) {
     printf("%d  ", k->hodnota);
     k = k->predch;
   }
}
-------------------------------------------------------------------------------------
void main(void)
{
   TUzol *zac, *kon;

   zac = kon = NULL;    /* vytvorenie prázdneho zoznamu */  

   /* vytvorenie 10 - prvkového zoznamu*/
   int i;
   for(i = 1; i<=10; i++) pridaj_na_koniec(&zac, &kon);
   
   /* výpis prvkov */
   printf("Od zaciatku: ");
   vypis_od_zac(zac);
   printf("\nOd konca: ");
   vypis_od_kon(kon);

   /* odstránenie tretieho prvku zo zoznamu */
   odstran(&zac, &kon, zac->nasled->nasled);
   
   /* za predposledný prvok vložíme nový */
   vloz_za(&zac, &kon, kon->predch);
   ...
}

Pri tvorbe programu zo zadania úlohy nezabudnite na funkciu, ktorá bude v zozname vyhľadáva prvok, ktorý spĺňa nejakú podmienku - jej návratovou hodnotou bude pointer na nájdený prvok. Ten môžeme potom využi ako parameter vo funkciách odstran, vloz_za.