/*
libvezlis - skup funkcija za vezane liste
Copyright (C) 2008 mibo@student.math.hr
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/
/*
Kôd je (pre)komentiran s ciljem da pomognem kolegama V.G. i H.M. ;-)
*/
/*
Verzije:
1. 23.06.08.
2. 24.06.08.
*/
#include <stdio.h>
#include <stdlib.h>
#define TIP int
struct _node{
TIP data;
struct _node *next;
};
typedef struct _node node;
/*
Parametri:
node *a -- node za koji treba ustanoviti je li prazan ili ne
Funkcija vraca:
char -- ako je node *a prazan, vraca 1; inace 0
*/
char node_prazan(node *a){
return (a == NULL ? 1 : 0);
}
/*
Parametri:
node *a -- node koji zelimo dodati na pocetak liste
node *h -- head liste
Funkcija vraca:
node* -- (novi) head liste u koju je dodan node *a
Prepostavke:
1. node *a nije NULL
*/
node* dodaj_na_pocetak_liste(node *a, node *h){
if(node_prazan(h)) /* ako je lista prazna */
return a;
else{
a->next = h;
return a;
}
}
/*
Parametri:
node *h -- head liste
Funkcija vraca:
node* -- zadnji node u listi ili NULL ako je lista prazna
*/
node* zadnji_node(node *h){
if(node_prazan(h)) return NULL; /* lista je prazna */
if(h->next == NULL) return h; /* lista sadrzi jedan element */
for( ; h->next != NULL; h = h->next) ;
/* sada smo na zadnjem node-u liste */
return h;
}
/*
Funkcija vraca:
node* -- alocirani node
Napomene:
1. Ako ne uspije alokacija prekida se izvrsenje programa.
*/
node* alociraj_node(void){
node* t;
if((t = (node *)calloc(sizeof(node), 1)) == NULL)
exit(-1);
return t;
}
/*
Parametri:
node *a -- node koji zelimo dodati na kraj liste
node *h -- head liste
Funkcija vraca:
node* -- (novi) head liste u koju je dodan node *a
Prepostavke:
1. node *a nije NULL
*/
node* dodaj_na_kraj_liste(node *h, node *a){
node* t = h;
h = zadnji_node(h);
if(node_prazan(h)) h = alociraj_node();
h->next = a;
a->next = NULL; /* a je sada kraj liste */
return t;
}
/*
Parametri:
node *a -- node nakon kojeg "ubacujemo" b
node *b -- node koji "ubacujemo" iza a
Pretpostavke:
1. a i b nisu NULL
Napomene:
1. Ako je b head neke liste, ta lista je "izgubljena" !
*/
void ubaci_node_u_listu(node *a, node *b){
if(node_prazan(a->next)){
a->next = b;
b->next = NULL;
}
else{
node *t = a->next;
a->next = b;
b->next = t;
}
}
/*
Parametri:
node *a -- node koji zelimo osloboditi
*/
void oslobodi_node(node* a){
if(a != NULL)
free(a);
}
/*
Parametri:
node *h -- head liste koju zelimo osloboditi
*/
void oslobodi_listu(node *h)
/* Rekurzivna verzija */
{
if(node_prazan(h)) return; /* lista je vec prazna */
if(node_prazan(h->next)){
free(h);
return;
}
else oslobodi_listu(h->next);
}
/*
Parametri:
node *h -- head liste koju zelimo osloboditi
*/
void oslobodi_listu_v2(node *h)
/* Nerekurzivna verzija */
{
node *t;
for(t = h; !node_prazan(t); h = h->next){
oslobodi_node(t);
t = h;
}
}
/*
Parametri:
node *h -- head liste
Funkcija vraca:
node* -- novi head liste
Napomena:
1. Ako je lista imala samo jedan element, tada ce funkcija
vratiti NULL
*/
node *oslobodi_prvi_node_liste(node *h)
/* a.k.a. obezglavi ;-) */
{
if(node_prazan(h)) return NULL;
else{
node *t = h->next;
oslobodi_node(h);
return t;
}
}
/*
Parametri:
node *h -- head liste
Funkcija vraca:
node* -- sredina liste ili NULL ako je lista prazna
*/
node* sredina_liste(node *h){
if(node_prazan(h)) return NULL;
else{
node *s, *b;
for(
s = b = h;
b != NULL && b->next != NULL && b->next->next != NULL;
s = s->next, b = b->next->next
);
return s;
}
}
/*
Parametri:
node *h1 -- head prve liste
node *h2 -- head druge liste
Funkcija vraca:
node* -- head prve liste na ciji je kraj "spojena" druga lista
Prepostavke:
1. prva lista nije prazna
*/
node* konkatenacija(node *h1, node *h2){
node *p = h1, *t = zadnji_node(p);
t->next = h2;
return h1;
}
/*
Parametri:
node *h -- head liste
Funkcija vraca:
size_t -- duzina liste
*/
size_t duzina_liste(node *h){
size_t l;
if(node_prazan(h)) return 0;
for(l = 0; !node_prazan(h); h = h->next, l++);
return l;
}
/*****************************************************************/
/* Pomocne funkcije */
void ucitaj(node **h){
node *p; int n, i;
printf("Broj elemenata: "); scanf("%d", &n);
for (i = 0; i < n; i++){
p = alociraj_node();
p->next = *h; *h = p;
printf("Element: "); scanf("%d", &p->data ); /* TIP = int */
}
}
void ispisi(node *h){
while (!node_prazan(h)){
if(!node_prazan(h->next))
printf("[%d|%p-> ", h->data, (void*)h->next); /* TIP = int */
else
printf("[%d|NULL]\n", h->data); /* TIP = int */
h = h->next;
}
}
/*****************************************************************/
int main(void){
return 0;
}