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 ); }