Se qualcuno fosse interessato allego questo src x la gestione delle liste in C
list.h
/*
* Copyright (C) 2010, Max Cavallo <ixamit@gmail.com>
*
* 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
*/
#ifndef _LIST_H
#define _LIST_H
#define EOL NULL
#define LIST_FIRST 0
#define LIST_LAST -1
#define LIST_CURRENT -2
#define LIST_BY_NUM 1
#define LIST_BY_ITEM 2
#define LIST_FORWARD 1
#define LIST_BACKWARD -1
typedef struct itemlist
{
void *data;
//unsigned int data_size;
struct itemlist * next;
struct itemlist * prev;
}ITEMLIST;
typedef struct list
{
unsigned int num_elem;
struct itemlist * first_item;
struct itemlist * current_item;
struct itemlist * last_item;
struct list * next;
struct list * prev;
}LIST;
/*
struct list *list_create ();
define a new list
*/
LIST *list_create ();
/*
list_destroy (LIST *list);
destroy list
*/
void list_destroy (LIST *list);
/*
struct itemlist *list_add (LIST *list, int pos, void *data);
add a new item to list
pos must be a valid position number from 0 to n-1 || LIST_FIRST || LIST_LAST || LIST_CURRENT
it define the #entry
data -> your data
*/
ITEMLIST *list_add (LIST *list, int pos, void *data);
/*
void list_del (LIST *list);
delete the current item list
*/
void list_del (LIST *list);
/*
ITEMLIST *list_findnext (struct list *list);
search next
return ITEMLIST || EOL
*/
ITEMLIST *list_seeknext (LIST *list);
/*
ITEMLIST *list_findprev (struct list *list);
search prev
return ITEMLIST || EOL
*/
ITEMLIST *list_seekprev (LIST *list);
/*
ITEMLIST *list_seek (LIST *list, int START, int skip, int LIST_BY,...)
perform sequential search by LIST_BY_NUM || LIST_BY_ITEM.
START initial position record; can be LIST_FIRST || LIST_LAST || LIST_CURRENT || valid record number from 0 to n-1
skip rekord to skip; negative value skip back
LIST_BY seek mode, must be LIST_BY_NUM || LIST_BY_ITEM
LIST_BY_ITEM needs extra parameter; comparator function and match as below
list_seek (struct list *list, DIRECTION, START, LIST_BY_ITEM, (*comparator) ( const void *, const void *), void *match);
return ITEMLIST || EOL
Some examples:
list_seek (list, LIST_FIRST, 0, LIST_BY_NUM); // rek 1
list_seek (list, LIST_FIRST, 4, LIST_BY_NUM); // rek 5
list_seek (list, LIST_LAST , 0, LIST_BY_NUM); // rek last
list_seek (list, LIST_LAST ,-1, LIST_BY_NUM); // rek last-1
list_seek (list, LIST_CURRENT ,-2, LIST_BY_NUM); // rek current-2
list_seek (list, LIST_LAST, -1, LIST_BY_ITEM,my_compare_function,&"fooname"); // starting from last
// seek backward the 2^ fooname
*/
ITEMLIST *list_seek (LIST *list, int START, int skip, int LIST_BY,...);
/*
ITEMLIST *list_first (LIST *list);
ITEMLIST *list_last (LIST *list);
return ITEMLIST || EOL
*/
ITEMLIST *list_first (LIST *list);
ITEMLIST *list_last (LIST *list);
/*
ITEMLIST *list_EOL (struct list *list);
return true || false
*/
int list_EOL (LIST *list);
/*
ITEMLIST *list_current (struct list *list);
return ITEMLIST || EOL
*/
ITEMLIST *list_current (LIST *list);
/*
void *list_data (struct list *list);
return (void *) || NULL
*/
void *list_data (LIST *list);
/*
unsigned int list_datasize (struct list *list);
return (unsigned int) || 0
unsigned int list_datasize (LIST *list);
*/
/*
unsigned int list_num_elem (struct list *list);
return (unsigned int) || 0
*/
unsigned int list_num_elem (LIST *list);
/*
void list_swap (LIST *listA, ITEMLIST *A, LIST *listB, ITEMLIST *B);
swap two ITEMLIST from same or different list
*/
void list_swap (LIST *listA, ITEMLIST *A, LIST *listB, ITEMLIST *B);
/*
void list_bsort (LIST *list, int (* comparator) ( const void *, const void *));
bubble sort
*/
void list_bsort (LIST *list, int (* comparator) ( const void *, const void *));
#endif // _LIST_H
list.c
/*
* Copyright (C) 2010, Max Cavallo <ixamit@gmail.com>
*
* 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include "list.h"
LIST *First=NULL;
LIST *Last =NULL;
LIST *list_create ()
{
LIST *new;
if((new=malloc (sizeof(struct list)))==NULL)
return NULL;
new->num_elem=0;
new->first_item=NULL;
new->current_item=NULL;
new->last_item=NULL;
new->prev=Last;
new->next=NULL;
if (!First) First=new;
if (Last) Last->next=new;
Last=new;
return (new);
}
void list_destroy (LIST *list)
{
ITEMLIST *next;
list->current_item=list->first_item;
while (list->current_item)
{
next=list->current_item->next;
free (list->current_item);
list->current_item=next;
}
if (list == Last ) Last =list->prev;
if (list == First) First=list->next;
if (list->prev) (list->prev)->next=list->next;
if (list->next) (list->next)->prev=list->prev;
free (list);
}
ITEMLIST *list_add (LIST *list, int START, void *data)//, unsigned int data_size)
{
ITEMLIST *new,*prev,*next;
int pos=START;
if (pos == LIST_FIRST)
{
prev=NULL;
next=list->first_item;
}
else if (pos == LIST_LAST)
{
prev=list->last_item;
next=NULL;
}
else if (pos == LIST_CURRENT)
{
if (list->current_item)
{
prev=list->current_item;
next=list->current_item->next;
}
else
{
pos = LIST_LAST;
prev=list->last_item;
next=NULL;
}
}
else if (pos > 0)
{
next=list->first_item;
while (next && pos--) next=next->next;
if (next)
prev=next->prev;
else
{
prev=list->last_item;
pos = LIST_LAST;
}
}
else
{
fprintf (stderr, "list_add: Warning parameter START=%d\n",pos);
return NULL;
}
if((new=malloc (sizeof(struct itemlist)))==NULL)
return NULL;
new->data=data;
//new->data_size=data_size;
new->prev=prev;
new->next=next;
if (prev) prev->next=new;
if (next) next->prev=new;
if (!list->first_item || pos == LIST_FIRST)
list->first_item=new;
if (!list->last_item || pos == LIST_LAST)
list->last_item=new;
list->current_item=new;
list->num_elem++;
return new;
}
void list_del (LIST *list)
{
ITEMLIST *current_item;
if (list==NULL || list->current_item==NULL)
return;
current_item=list->current_item;
if (current_item == list->last_item ) list->last_item =current_item->prev;
if (current_item == list->first_item) list->first_item=current_item->next;
if (current_item->prev) (current_item->prev)->next=current_item->next;
if (current_item->next) (current_item->next)->prev=current_item->prev;
list->num_elem--;
list->current_item=current_item->next;
free (current_item);
}
ITEMLIST *list_seek (LIST *list, int START, int skip, int LIST_BY,...)
{
ITEMLIST *l;
va_list va;
int FORWARD;
int SKIP=skip;
int (*comparator)();
char *match;
// TODO Error Manager
if (START!=LIST_FIRST && START!=LIST_CURRENT && START!=LIST_LAST)
return NULL;
if (LIST_BY!=LIST_BY_NUM && LIST_BY!=LIST_BY_ITEM)
return NULL;
if (START==LIST_FIRST)
l=list->first_item;
else if (START==LIST_CURRENT)
l=list->current_item;
else if (START==LIST_LAST)
l=list->last_item;
if (skip<0) { SKIP=skip*(-1); FORWARD=0; }
else { SKIP=skip; FORWARD=1; }
if (LIST_BY==LIST_BY_NUM)
{
for (;SKIP;SKIP--)
{
l=(FORWARD) ? l->next : l->prev;
}
}
if (LIST_BY==LIST_BY_ITEM)
{
va_start(va, LIST_BY);
comparator=va_arg(va,void *);
match=va_arg(va,void *);
while (l)
{
if ((* comparator ) (l->data,match)==0)
{
if (SKIP--==0)
break;
}
//else
//{
l=(FORWARD) ? l->next : l->prev;
//}
}
}
list->current_item=l;
return (l);
}
ITEMLIST *list_seeknext (LIST *list)
{
list->current_item=list->current_item->next;
return (list->current_item);
}
ITEMLIST *list_seekprev (LIST *list)
{
list->current_item=list->current_item->prev;
return (list->current_item);
}
ITEMLIST *list_first (LIST *list)
{
return (list_seek (list, LIST_FIRST, 0, LIST_BY_NUM));
}
ITEMLIST *list_last (LIST *list)
{
return (list_seek (list, LIST_LAST, 0, LIST_BY_NUM));
}
int list_EOL (LIST *list)
{
return (list->current_item ? 0 : 1);
}
ITEMLIST *list_current (LIST *list)
{
return (list->current_item);
}
void *list_data (LIST *list)
{
return (list->current_item) ? list->current_item->data : NULL;
}
/*
unsigned int list_datasize (LIST *list)
{
return (list->current_item) ? list->current_item->data_size : 0;
}
*/
unsigned int list_num_elem (LIST *list)
{
return (list->num_elem);
}
void list_swap (LIST *listA, ITEMLIST *A, LIST *listB, ITEMLIST *B)
{
/*
Swap a & b. Examples poiters scheme
+--+ +--+ +--+ +--+ +--+ +--+ +--+
|p0| | | |p1| | | |p2| | | |p3|
| | |A | | | | | | | |B | | |
| | | | | | | | | | | | | |
+--+ +--+ +--+ +--+ +--+ +--+ +--+
+--+ +--+ +--+ +--+ +--+ +--+ +--+
|p2| | | |p3| | | |p0| | | |p1|
| | |B | | | | | | | |A | | |
| | | | | | | | | | | | | |
+--+ +--+ +--+ +--+ +--+ +--+ +--+
+--+ +--+ +--+ +--+ +--+ +--+ +--+
|p0| | | |p1| | | |p3| | | | |
| | |A | |p2| |B | | | | | | |
| | | | | | | | | | | | | |
+--+ +--+ +--+ +--+ +--+ +--+ +--+
+--+ +--+ +--+ +--+ +--+ +--+ +--+
|p2| | | |p0| | | |p1| | | | |
| | |B | |p3| |A | | | | | | |
| | | | | | | | | | | | | |
+--+ +--+ +--+ +--+ +--+ +--+ +--+
+--+ +--+ +--+ +--+ +--+ +--+ +--+
|p0| |p2| |p1| |p3| | | | | | |
| | |A | |B | | | | | | | | |
| | | | | | | | | | | | | |
+--+ +--+ +--+ +--+ +--+ +--+ +--+
+--+ +--+ +--+ +--+ +--+ +--+ +--+
|p2| |p0| |p3| |p1| | | | | | |
| | |B | |A | | | | | | | | |
| | | | | | | | | | | | | |
+--+ +--+ +--+ +--+ +--+ +--+ +--+
*/
ITEMLIST *p[4];
int is_adjacent=0;
if (A==B || A==NULL || B==NULL) return;
if (A->next==B) is_adjacent=1; else if (A->prev==B) is_adjacent=2;
p[0]=A->prev;
p[1]=A->next;
p[2]=B->prev;
p[3]=B->next;
if (p[0]) p[0]->next=B;
if (p[1]) p[1]->prev=B;
if (p[2]) p[2]->next=A;
if (p[3]) p[3]->prev=A;
if (p[1] && p[1]==p[2])
{
p[1]->next=A;
p[2]->prev=B;
}
if (p[0] && p[0]==p[3])
{
p[0]->prev=A;
p[3]->next=B;
}
if (is_adjacent==1)
{
A->prev=B;
A->next=p[3];
B->prev=p[0];
B->next=A;
}
else if (is_adjacent==2)
{
A->prev=p[2];
A->next=B;
B->prev=A;
B->next=p[1];
}
else
{
A->prev=p[2];
A->next=p[3];
B->prev=p[0];
B->next=p[1];
}
if (A==listA->first_item)
listA->first_item=B;
else if (B==listB->first_item)
listB->first_item=A;
if (B==listB->last_item)
listB->last_item =A;
else if (A==listA->last_item)
listA->last_item =B;
}
void list_bsort (struct list *list, int (* comparator) ( const void *, const void *))
{
ITEMLIST *p1,*p2;
int i,n;
n=list_num_elem (list);
while (n > 1)
{
p1=list->first_item;
p2=(p1) ? p1->next : NULL;
for (i=0;i<n-1;i++)
{
if ((* comparator ) (p1->data,p2->data) > 0)
{
list_swap (list, p1, list, p2);
p2=(p1) ? p1->next : NULL;
}
else
{
p1=p2;
p2=(p1) ? p1->next : NULL;
}
}
n--;
}
}
example.c
/*
* Copyright (C) 2010, Max Cavallo <ixamit@gmail.com>
*
* 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//#include "timing.h"
#include "list.h"
/*
------------------------------
------------------------------
*/
#define MAXNAME 32
struct s1
{
char *name;
int ID;
}s1;
int sort_cmp_by_name(const void *a, const void *b)
{
struct s1 *ia = (struct s1 *)a;
struct s1 *ib = (struct s1 *)b;
return (int)(strcmp (ia->name,ib->name));
}
int sort_cmp_by_ID(const void *a, const void *b)
{
struct s1 *ia = (struct s1 *)a;
struct s1 *ib = (struct s1 *)b;
return (int)(ia->ID - ib->ID);
}
int seek_cmp_by_name(const void *a, const void *b)
{
struct s1 *ia = (struct s1 *)a;
char *ib = (char *) b;
return (int)(strcmp (ia->name,ib));
}
int seek_cmp_by_ID(const void *a, const void *b)
{
struct s1 *ia = (struct s1 *)a;
int *ib = (int *) b;
return (ia->ID-(*ib));
}
void show_item (LIST *list)
{
struct s1 *ps1;
ps1=list_data(list);
//
// showing the struct
//
printf ("(%p)%-15s ID=%6d | \t",list->current_item,ps1->name,ps1->ID);
}
void example_insert (LIST *list)
{
struct s1 *ps1;
int i;
if ((ps1=malloc (sizeof(struct s1)))==NULL)
return;
if ((ps1->name=malloc (MAXNAME))==NULL)
{
free (ps1);
return;
}
printf ("Insert name:");
scanf ("%s",ps1->name);
printf (" ID:");
scanf ("%d",&ps1->ID);
printf ("Where should I put it into the list (0=First, 1=second, 2=Third ... -1=Append)");
scanf ("%d",&i);
if (!list_add (list, i , ps1))//, sizeof(struct s1)))
{
free (ps1->name);
free (ps1);
}
}
void example_load_file (LIST *list)
{
struct s1 *ps1;
int i,l;
FILE *fp;
if ((fp=fopen ("./lista.txt","r"))==NULL)
{
printf ("File not Found!\n");
return;
}
while (1)
{
if ((ps1=malloc (sizeof(struct s1)))==NULL)
return;
if ((ps1->name=malloc (MAXNAME))==NULL)
{
free (ps1->name);
free (ps1);
break;
}
if ((l=fscanf (fp,"%s%d",ps1->name,&i))==-1)
{
free (ps1->name);
free (ps1);
break;
}
ps1->ID=i;
if (!list_add (list, LIST_LAST , ps1))//, sizeof(struct s1)))
{
free (ps1->name);
free (ps1);
break;
}
}
fclose (fp);
}
void example_insert_many (LIST *list)
{
struct s1 *ps1;
int i,j;
for (i=0;i<500;i++)
{
if ((ps1=malloc (sizeof(struct s1)))==NULL)
return;
if ((ps1->name=malloc (MAXNAME))==NULL)
{
free (ps1);
return;
}
for (j=0;j<5;j++)
ps1->name[j]=65+rand()%25;
ps1->ID=rand()%9999;
if (!list_add (list, LIST_LAST , ps1))//, sizeof(struct s1)))
{
free (ps1->name);
free (ps1);
}
}
printf ("Done %d random items\n",i);
}
void example_delete (LIST *list)
{
struct s1 *ps1;
int i;
if (list_num_elem(list)==0)
{
printf ("empty list\n");
printf ("\n");
return;
}
do
{
printf ("Witch one of %d items do u want to delete?",list_num_elem(list));
scanf ("%d",&i);
}while (i<0 || i>list_num_elem(list)-1);
list_seek (list,LIST_FIRST, i, LIST_BY_NUM);
ps1=list_data(list);
free (ps1->name);
free (ps1);
list_del (list);
}
void example_sort (LIST *list)
{
int i;
do
{
printf ("Sorting by 0=Name or 1=ID ?");
scanf ("%d",&i);
}while (i < 0 || i >2);
printf ("Sorting...\n");
//timer ();
if (i==0)
list_bsort (list,sort_cmp_by_name);
else
list_bsort (list,sort_cmp_by_ID);
//timer ();
}
void example_show_list (LIST *list)
{
int i,j,START;
do
{
printf ("Show 0=Forward or 1=Reverse ?");
scanf ("%d",&i);
}while (i<0 && i>1);
START=i ? LIST_LAST : LIST_FIRST;
list_seek (list,START, 0, LIST_BY_NUM);
printf ("Showing List:\n");
j=0;
while (!list_EOL(list))
{
show_item (list);
if (++j%3==0)
printf ("\n");
if (i==0)
list_seeknext (list);
else
list_seekprev (list);
}
printf ("\n");
}
void example_swap (LIST *list)
{
struct itemlist *a,*b;
int i,j;
do
{
printf ("Witch elementes ?");
scanf ("%d %d",&i,&j);
}while (i<0 && j<0);
a=list_seek (list,LIST_FIRST, i, LIST_BY_NUM);
b=list_seek (list,LIST_FIRST, j, LIST_BY_NUM);
list_swap (list,a,list,b);
}
void example_free_list (LIST *list)
{
struct s1 *ps1;
list_seek (list,LIST_FIRST, 0, LIST_BY_NUM);
while (!list_EOL(list))
{
ps1=list_data(list);
// Freeing my malloc name
free (ps1->name);
// Freeing my struct
free (ps1);
// Freeing the the current item list
list_del (list);
}
}
void example_search (LIST *list)
{
char buff[MAXNAME];
int ID,i,j;
do
{
printf ("Search by 0=Name or 1=ID ?");
scanf ("%d",&i);
}while (i<0 || i>1);
j=0;
if (i==0)
{
printf ("Name: ");
scanf ("%s",buff);
//timer ();
list_seek (list,LIST_FIRST, 0, LIST_BY_ITEM,seek_cmp_by_name,buff);
while (!list_EOL(list))
{
show_item (list);
if (++j%3==0)
printf ("\n");
list_seek (list,LIST_CURRENT, 1, LIST_BY_ITEM,seek_cmp_by_name,buff);
}
}
else
{
printf ("ID: ");
scanf ("%d",&ID);
//timer ();
list_seek (list,LIST_FIRST, 0, LIST_BY_ITEM,seek_cmp_by_ID,&ID);
while (!list_EOL(list))
{
show_item (list);
if (++j%3==0)
printf ("\n");
list_seek (list,LIST_CURRENT, 1, LIST_BY_ITEM,seek_cmp_by_ID,&ID);
}
}
printf ("\n%d Item(s) Found\n",j);
//timer ();
}
void example ()
{
LIST *list;
int i;
list=list_create ();
do
{
printf ("\nThere are %d item(s) in list\n",list_num_elem(list));
printf ("(1) Insert\t\t");
printf ("(2) Load File\t\t");
printf ("(3) Insert 500 random item\n");
printf ("(4) Show List\t\t");
printf ("(5) Delete\t\t");
printf ("(6) Sort\n");
printf ("(7) Swap\t\t");
printf ("(8) Free List\t\t");
printf ("(9) Search\n");
printf ("(0) Exit\n");
scanf ("%d",&i);
switch (i)
{
case 1:
example_insert (list);
break;
case 2:
example_load_file (list);
break;
case 3:
example_insert_many (list);
break;
case 4:
example_show_list (list);
break;
case 5:
example_delete (list);
break;
case 6:
example_sort (list);
break;
case 7:
example_swap (list);
break;
case 8:
example_free_list (list);
break;
case 9:
example_search (list);
break;
}
}while (i);
//
example_free_list (list);
list_destroy (list);
//
}
int main ()
{
printf ("\nThis example builds list with this struct:\n");
printf ("struct s1\n{\n char *name;\n int ID;\n}s1;\n\n\n");
example ();
return 0;
}
Makefile:
CC = gcc
CFLAGS = -g -Wall
LFLAGS =
SRCPATH = ./src/
SOURCES = $(SRCPATH)list.c $(SRCPATH)example.c
OBJECTS =$(SOURCES:.c=.o)
EXECUTABLE=lista
all: $(EXECUTABLE)
$(EXECUTABLE): $(OBJECTS)
$(CC) $(LFLAGS) $(OBJECTS) -o $@
.c.o:
$(CC) $(CFLAGS) -c $< -o $@
clean:
rm -f $(OBJECTS) $(SRCPATH)*~
tar:
tar czvf list.tgz Makefile $(SRCPATH)*.h $(SOURCES)