Ferramentas de Usuário

Ferramentas de Site


dev_geral:c:snippet:list

Implementaçao de Listas em C

Implementação simples de listas duplamente ligadas em C.

Ficheiro: list.h

/*
 *  GPL
 *
 *  Written by Diogo Sousa aka orium
 *  Copyright (C) 2008 Diogo Sousa
 *
 *  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 3 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, see <http://www.gnu.org/licenses/>.
 */
 
#ifndef LIST_H_
#define LIST_H_
 
#include <stddef.h>
 
typedef struct list_node 
{
	void *data;
 
	struct list_node *next;	
	struct list_node *prev;
} list_node;
 
typedef struct list
{
	struct list_node *head;	
	struct list_node *tail;
 
	size_t size;
} list;
 
extern void list_init(list *);
extern size_t list_size(list *);
 
extern list_node *list_head(list *);
extern list_node *list_tail(list *);
 
extern list_node *list_add(list *, void *);
extern list_node *list_add_head(list *, void *);
extern list_node *list_add_tail(list *, void *);
 
extern void *list_del(list *, list_node *);
 
extern void list_free(list *, void (*callback)(void *));
 
#define list_node_data(list_node,type) (*((type *)(list_node)->data))
#define list_node_data_ptr(list_node,type) ((type *)(list_node)->data)
#define list_node_next(list_node) ((list_node)->next)
#define list_node_prev(list_node) ((list_node)->prev)
 
#endif

Ficheiro: list.c

/*
 *  GPL
 *
 *  Written by Diogo Sousa aka orium
 *  Copyright (C) 2008 Diogo Sousa
 *
 *  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 3 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, see <http://www.gnu.org/licenses/>.
 */
 
#include "list.h"
#include "xalloc.h"
 
void
list_init(list *list)
{
	list->head=NULL;
	list->tail=NULL;
	list->size=0;
}
 
size_t
list_size(list *list)
{
	return list->size;
}
 
list_node *
list_head(list *list)
{
	return list->head;
}
 
list_node *
list_tail(list *list)
{
	return list->tail;
}
 
list_node *
list_add(list *list, void *data)
{
	return list_add_tail(list,data);
}
 
list_node *
list_add_head(list *list, void *data)
{
	list_node *list_node;
 
	list_node=xmalloc(sizeof(*list_node));
	list_node->data=data;
	list_node->next=list->head;
	list_node->prev=NULL;
 
	if (list->head == NULL)
		list->head=list_node;
	else
		list->head->prev=list_node;
 
	list->head=list_node;
 
	list->size++;
 
	return list_node;
}
 
list_node *
list_add_tail(list *list, void *data)
{
	list_node *list_node;
 
	list_node=xmalloc(sizeof(*list_node));
	list_node->data=data;
	list_node->next=NULL;
	list_node->prev=list->tail;
 
	if (list->head == NULL)
		list->head=list_node;
	else
		list->tail->next=list_node;
 
	list->tail=list_node;
 
	list->size++;
 
	return list_node;
}
 
void *
list_del(list *list, list_node *node)
{
	void *data;
 
	if (node->next != NULL)
		node->next->prev=node->prev;
 
	if (node->prev != NULL)
		node->prev->next=node->next;
 
	if (list->tail == node)
		list->tail=node->prev;
 
	if (list->head == node)
		list->head=node->next;
 
	list->size--;
 
	data=node->data;
 
	free(node);
 
	return data;
}
 
void 
list_free(list *list, void (*callback)(void *))
{
	struct list_node *i;
	struct list_node *next;
 
	for (i=list_head(list); i != NULL; i=next)
	{
		if (callback != NULL)
			callback(i->data);
 
		next=i->next;
 
		free(i);
	}
}

Exemplo de uso

#include <stdio.h>
#include "list.h"
 
int
main(void)
{
	list list;
	list_node *node;
	struct list_node *i;
	int n[]={5,6,7,8};
 
	// inicialização da lista
	list_init(&list);
 
	// adiciona 5 na cauda da lista
	list_add_tail(&list,&n[0]);
	// adiciona 6 na cauda da lista, e devolve o nodo adicionado
	node=list_add_tail(&list,&n[1]);
	// adiciona 7 na cauda da lista
	list_add_tail(&list,&n[2]);
	// adiciona 8 na cauda da lista
	list_add_tail(&list,&n[3]);
	// adiciona 8 na cabeça da lista
	list_add_head(&list,&n[3]);
 
	// percorre os elementos da lista e imprime-os
	for (i=list_head(&list); i != NULL; i=list_node_next(i))
		printf("%d ",list_node_data(i,int));
 
	// elimina node (6) da lista
	list_del(&list,node);
 
	putchar(' | ');
 
	// percorre os elementos da lista e imprime-os (o elemento 6 foi removido)
	for (i=list_head(&list); i != NULL; i=list_node_next(i))
		printf("%d ",list_node_data(i,int));
 
	// liberta o espaço ocupado pela lista
	list_free(&list,NULL);
 
	return 0;
}
dev_geral/c/snippet/list.txt · Última modificação em: 2018/05/14 21:37 (edição externa)