Programiranje u C-u

  

Još jedan primjer vezanih lista

/* primjer vezanih lista */

#include <stdio.h>
#include <alloc.h>
#include <stdlib.h>
#include <conio.h>
#include <ctype.h>
#include <string.h>

/* prototipovi funkcije */

struct node * initnode( char *, int );
void printnode( struct node * );
void printlist( struct node * );
void add( struct node * );
struct node * searchname( struct node *, char * );
void deletenode( struct node * );
void insertnode( struct node * );
void deletelist( struct node * );

/* definiranje čvora koji sadrži informacije o studentu */

struct node {
   char name[20];
   int  id;
   struct node *next;
};

/* 'head' pokazuje na prvi čvor u listi, 'end' pokazuje na zadnji čvor u listi */

/* inicijalizacija oba čvora na NULL, što znači da u listi još nema čvorova */

struct node *head = (struct node *) NULL;
struct node *end = (struct node *) NULL;

/* ovo inicijalizira čvor, alocira memoriju za čvor i vraća    */

/* pokazivač na novi čvor. Mora proslijediti detalje čvora, ime i id */

struct node * initnode( char *name, int id )
{
   struct node *ptr;
   ptr = (struct node *) calloc( 1, sizeof(struct node ) );
   if( ptr == NULL )                       /* greška pri alokaciji čvora?     */
       return (struct node *) NULL;        /* onda vrati NULL, inače je      */
   else {                                  /* čvor uspješno alociran  */
       strcpy( ptr->name, name );          /* popunjava detalje imena        */
       ptr->id = id;                       /* kopira id detalje             */
       return ptr;                         /* vraća pokazivač na novi čvor  */
   }
}

/* ovo ispisuje na ekran detalje čvora, kao što su ime i id                 */

/* mora proslijediti adresu čvora kojeg želimo ispisati na ekran             */

void printnode( struct node *ptr )
{
   printf("Ime ->%s\n", ptr->name );
   printf("ID   ->%d\n", ptr->id );
}

/* ovo ispisuje na ekran sve čvorove sa adrese koja im je trenutno dodijeljena. Ukoliko je     */

/* dodijeljen 'head', tada ispisuje čitavu listu kružeći kroz */


/* svaki čvor i pozivajući 'printnode' za ispis svakog pronađenog čvora             */

void printlist( struct node *ptr )
{
   while( ptr != NULL )           /* nastavlja sve dok ima preostalih čvorova */
   {
      printnode( ptr );           /* ispisuje tekući čvor           */
      ptr = ptr->next;            /* ide na slijedeći čvor  liste      */
   }
}

/* ovo dodaje čvor na kraj liste. Moramo alocirati čvor i  */

/* proslijediti njegovu adresu ovoj funkciji                          */

void add( struct node *new )  /* dodavanje na kraj liste */
{
   if( head == NULL )      /* ukoliko više nema čvorova u listi, onda         */
       head = new;         /* postavlja  'head' na ovaj novi čvor                   */
   end->next = new;        /* povezuje novi čvor na kraj liste */
   new->next = NULL;       /* postavlja slijedeće polje da označava kraj liste   */
   end = new;              /* prilagođava 'end' da pokazuje na poslijednji čvor       */
}

/* pretražuje listu za ime i vraća pokazivač na nađeni čvor     */

/* prihvaća ime za traženje i pokazivač od kojeg počinje.Ako    */

/* koristimo pokazivač 'head', traženje počinje na početku liste */

struct node * searchname( struct node *ptr, char *name )
{
    while( strcmp( name, ptr->name ) != 0 ) {    /* dok ime nije pronađeno */
       ptr = ptr->next;                          /* ide na slijedeći čvor   */
       if( ptr == NULL )                         /* zaustavlja se ukoliko smo izišli   */
          break;                                 /* iz liste           */
    }
    return ptr;                                  /* vraća pokazivač na   */
}                                                /* nađeni čvor ili NULL    */

/* briše čvor na koji pokazuje 'ptr' iz liste           */

void deletenode( struct node *ptr )
{
   struct node *temp, *prev;
   temp = ptr;    /* čvor koji će biti izbrisan */
   prev = head;   /* početak liste, kružit će do čvora prije temp    */

   if( temp == prev ) {                    /* da li brišemo prvi čvor  */
       head = head->next;                  /* premiješta head na slijedeći čvor     */
       if( end == temp )                   /* je li kraj, samo jedan čvor?   */
          end = end->next;                 /* prilagodi i 'end'           */
       free( temp );                       /* oslobodi prostor rezerviran za čvor */
   }
   else {                                  /* ako nije prvi čvor, onda */
       while( prev->next != temp ) {       /* premjesti 'prev' na prethodni čvor*/
           prev = prev->next;              /* koji će biti izbrisan       */
       }
       prev->next = temp->next;            /* poveži prethodni čvor sa slijedećim  */
       if( end == temp )                   /* ukoliko je ovo bio zadnji čvor   */
           end = prev;                     /* ponovno postavi pokazivač 'end'   */
       free( temp );                       /* oslobodi prostor rezerviran za čvor */
   }
}

/* ubacuje novi čvor, koristi polje imena da poreda čvorove po abecadi */

/* prosljeđuje adresu novog čvora koji će biti ubačen, sa svim detaljima   */

void insertnode( struct node *new )
{
   struct node *temp, *prev;                /* sličan kao 'deletenode'      */

   if( head == NULL ) {                     /* ukoliko je lista prazna          */
       head = new;                          /* postavi 'head' na nju           */
       end = new;
       head->next = NULL;                   /* postavi kraj liste na  NULL    */
       return;                              /* i završi s radom                 */
   }

   temp = head;                             /* počinje na početku liste */
                      /* dok je tekuće ime < novog imena koje će biti ubačeno onda */
   while( strcmp( temp->name, new->name) < 0 ) {
          temp = temp->next;                /* ide na slijedeći čvor u listi */
          if( temp == NULL )                /* ne prelazi kraj liste  */
              break;
   }

   /*  trebamo prethodni čvor prije ubacivanja  */

   /* prvo treba provjeriti da li se ubacuje prije prvog čvora!          */

   if( temp == head ) {
      new->next = head;             /* poveži slijedeće polje na originalnu listu   */
      head = new;                   /* prilagođava 'head' na novi čvor         */
   }
   else {     /* dobro, nije prvi čvor, drukčiji pristup   */
      prev = head;   /* početak liste, kružit će do čvora prije 'temp' */
      while( prev->next != temp ) {
          prev = prev->next;
      }
      prev->next = new;             /* ubacuje čvor između 'prev' and 'next'  */
      new->next = temp;
      if( end == prev )             /* ukoliko je novi čvor ubačen na */
         end = new;                 /* kraju liste prilabođava 'end'   */
   }
}

/* ovo briše sve čvorove sa mjesta određenog sa 'ptr'                 */

/* ukoliko koristimo 'head', oslobodit će cijelu listu                     */

void deletelist( struct node *ptr )
{
   struct node *temp;

   if( head == NULL ) return;   /* ne pokušavaj izbrisati praznu listu      */

   if( ptr == head ) {      /* ukoliko brišemo cijelu listu       */
       head = NULL;         /* ponovno postavlja 'head' i 'end' da znači da je lista   */
       end = NULL;          /* prazna                                       */
   }
   else {
       temp = head;          /* ikoliko nije čitava lista, ponovno prilagodi 'end'  */
       while( temp->next != ptr )         /* locira prethodni čvor na 'ptr'  */
           temp = temp->next;
       end = temp;                        /* postavlja 'end' na čvor prije 'ptr'   */
   }

   while( ptr != NULL ) {   /* dok još ima čvorova za brisanje    */
      temp = ptr->next;     /* zapiši adresu slijedećeg čvora               */
      free( ptr );          /* oslobodi ovaj čvor                            */
      ptr = temp;           /* pokazuje na slijedeći čvor koji će biti izbrisan     */
   }
}

/* ovo je glavni rutina                */
main()
{
   char name[20];
   int id, ch = 1;
   struct node *ptr;

   clrscr();
   while( ch != 0 ) {
      printf("1 dodaj ime \n");
      printf("2 izbriši ime \n");
      printf("3 izlistaj sva imena \n");
      printf("4 traži ime \n");
      printf("5 ubaci ime \n");
      printf("0 odustani\n");

      scanf("%d", &ch );
      switch( ch )
      {
          case 1:  /* dodaj ime na kraj liste */
                   printf("Unesi ime -- ");
                   scanf("%s", name );
                   printf("Unesi id -- ");
                   scanf("%d", &id );
                   ptr = initnode( name, id );
                   add( ptr );
                   break;
          case 2:  /* briše ime */
                   printf("Unesi ime -- ");
                   scanf("%s", name );
                   ptr = searchname( head, name );
                   if( ptr ==NULL ) {
                       printf("Ime %s nije pronađeno\n", name );
                   }
                   else
                      deletenode( ptr );
                   break;
          case 3:  /* lista sve čvorove */
                   printlist( head );
                   break;
          case 4:  /* traži i ispisuje ime na ekran */
                   printf("Unesi ime -- ");
                   scanf("%s", name );
                   ptr = searchname( head, name );
                   if( ptr ==NULL ) {
                       printf("Ime %s nije pronađeno\n", name );
                   }
                   else
                      printnode( ptr );
                   break;
          case 5:  /* ubacuje ime u listu */
                   printf("Unesi ime -- ");
                   scanf("%s", name );
                   printf("Unesi id -- ");
                   scanf("%d", &id );
                   ptr = initnode( name, id );
                   insertnode( ptr );
                   break;
      }
   }
   deletelist( head );
}

©Copyright B Brown. 1984-1998. All rights reserved.