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.