list.c

1.linux平台上单链表接口 2.代码的封装性和层次性好 3.接口功能全

/*
 *	Copyright (c) 2007, beijing
 *	All right reserved.
 *	list.c
 *	author:	chengliang
 *	date:	May, 26, 07
 */

#include "list.h"

/*internal API*/

/*create a new node*/
static node *list_new_node(void);
/*insert a node*/
static int list_insert_node(const linklist , int , items * );
/*remove a node*/
static int list_remove_node(const linklist , int );
/*swap the two nodes*/
static int list_swap_node(const linklist , int , int );
/*get the node content*/
static items *list_get_node(const linklist , int );
/*get the node address*/
static node *list_get_node_addr(const linklist , int );

/*basic API*/

/*init the list*/
void list_init(linklist *pllist)
{
	node *phead;

	phead = list_new_node();
	*pllist = phead;
}

/*destroy a list*/
void list_destroy(linklist *pllist)
{
	/*remove all the node*/
	list_remove_all(*pllist);
	/*remove the list head*/
	free(*pllist);
	*pllist = NULL;
}

/*count the list length, including the head of the list*/
int list_count(const linklist llist)
{
	if (llist->next == NULL)
	{
		return 0;
	}

	return 1 + list_count(llist->next);
}

/*judge the list is empty or not*/
int list_is_empty(const linklist llist)
{
	return (llist->next == NULL);
}

/*insert a new node at postion 'pos'*/
int list_insert_at(const linklist llist, int pos, items * pitem)
{
	return  (pos >= 0 ? list_insert_node(llist, pos, pitem) : FALSE);
}

/*remove the list node at position 'pos'*/
int list_remove_at(const linklist llist, int pos)
{
	return (pos >= 0 ? list_remove_node(llist, pos) : FALSE);
}

/*get the position 'pos' and then return the data it refers to*/
items *list_get_at(const linklist llist, int pos)
{
	return (pos >= 0 ? list_get_node(llist, pos) : NULL);
}

/*set the list node at position 'pos' with the given data*/
int list_set_at(const linklist llist, int pos, items *pitem)
{
	items *pdata;
	
	assert(pitem);

	if ((pdata = list_get_at(llist, pos)) == NULL)
	{
		return FALSE;
	}
	else
	{
		node_data_copy(pdata, pitem);
	}
	return TRUE;	
}

/*extension API*/

/*insert a list node at the begin of the list*/
int list_add_head(const linklist llist, items *pitem)
{
	return list_insert_node(llist, 0, pitem);
}

/*insert a list node at the end of the list*/
int list_add_tail(const linklist llist, items *pitem)
{
	return list_insert_node(llist, -2, pitem);
}

/*remove the first node of the list*/
int list_remove_head(const linklist llist)
{
	return list_remove_node(llist, 0);
}

/*remove the last node of the list*/
int list_remove_tail(const linklist llist)
{
	return list_remove_node(llist, -2);
}

/*remove all the node in the list except the head*/
void list_remove_all(const linklist llist)
{
	while (list_remove_node(llist, 0));
}

/*get the first node of the list*/
items *list_get_head(const linklist llist)
{
	return list_get_node(llist, 0);
}

/*get the last node of the list*/
items *list_get_tail(const linklist llist)
{
	return list_get_node(llist, -2);
}

/*append a list source at the tail of another list destination*/
int list_append(const linklist llist_dst, linklist llist_src)
{
	int src_len;
	int num;
	
	if ((src_len = list_count(llist_src)) == 0)
	{
		return FALSE;
	}
	for (num = 0; num < src_len; num++)
	{
		list_add_tail(llist_dst, list_get_at(llist_src, num));
	}

	return TRUE;
}

/*search for whether the list have the node that has the same items*/
int list_search(const linklist llist, items *pitem)
{
	int num;
	int len;

	assert(llist && pitem);

	len = list_count(llist);
	for (num = 0; num < len; num++)
	{
		if (node_data_comp(list_get_at(llist, num), pitem) == 0)
		{
			return num;
		}
	}

	return -1;
}

/*sort the list and arrange it whether by '<' or by '>', decided by the mode*/
int list_sort(const linklist llist, char mode)
{
	int len;
	int i;
	int j;
	items *pprev;
	items *pcurrent;

	assert(llist);
	
	if (mode != '>' && mode != '<')
	{
		return FALSE;
	}
	if ((len = list_count(llist)) == 1)
	{
		return FALSE;
	}
	for (i = 0; i < len; i++)
	{
		for (j = 1; j < len - i; j++)
		{
			pcurrent = list_get_at(llist, j);
			pprev = list_get_at(llist, j - 1);

			/*swap by point*/
			if (mode == '>')
			{
				if (node_data_comp(pprev, pcurrent) < 0)
				{
					list_swap_node(llist, j, j - 1);
				}
			}
			else
			{
				if (node_data_comp(pprev, pcurrent) > 0)
				{
					list_swap_node(llist, j, j - 1);
				}
			}
		}		
	}
	
	return TRUE;	
}

/*reverse the list with the opposite sequence*/
void list_reverse(const linklist llist)
{
	int count;
	int len;
	
	len = list_count(llist);
	for (count = 0; count < len / 2; count++)
	{
		list_swap_node(llist, count, len - 1 - count);
	}
}

/*free the same list node and keep the list different at last*/
void list_diff(const linklist llist)
{
	node *p, *q, *r;

	for (p = llist->next; p != NULL; p = p->next)
	{
		for (r = p, q = p->next; q != NULL; q = q->next)
		{
			if (!node_data_comp(&(p->item), &(q->item)))
			{
				r->next = q->next;
				free(q);
				q = r;
			}
			else
			{
				r = r->next;
			}
		}	
	}
}


/*internal API*/

/*create a new node, then initialize it*/
static node *list_new_node(void)
{
	node *pnode;
	
	pnode = (node *)malloc(sizeof(node));
	if (pnode == NULL)
	{
		printf("insert: out of memory!\n");
		return NULL;
	}
	
	pnode->next = NULL;
	pnode->info = 0;
	
	/* initialize node */
	node_data_init(&(pnode->item));
	
	return pnode;
}

/*insert a new node at postion 'pos'*/
static int list_insert_node(const linklist llist, int pos, items *pitem)
{
	int num;
	node *scan;
	node *new_node;
	
	assert(llist && pitem);
	
	new_node = list_new_node();
	node_data_copy(&(new_node->item), pitem);
	
	/*test the list is empty or not; if empty, insert it after the list head directly*/
	if (list_is_empty(llist))
	{
		llist->next = new_node;
		return TRUE;
	}
	
	scan = llist;
	/* pos equals minus means add to the tail*/
	if (pos < 0)
	{
		while (scan->next != NULL) 
		{
			scan = scan->next;
		}
		scan->next = new_node;	
	}
	else
	{
		for (num = 0; (num < pos) && (scan->next != NULL); num++)
		{
			scan = scan->next;
		}
		/*if the insert position beyonds the count of the whole list, it fails*/
		if ((scan->next == NULL) && (num < pos))
		{
			return FALSE;
		}
		new_node->next = scan->next;
		scan->next = new_node;		
	}
	
	return TRUE;
}

/*remove the list node at position 'pos'*/
static int list_remove_node(const linklist llist, int pos)
{
	node *scan;
	node *pdelete;
	int num;
	
	assert(llist);
	
	if (list_is_empty(llist))
	{
		return FALSE;
	}
	
	scan = llist;
	if (pos < 0)
	{
		pdelete = scan->next;
		while (pdelete->next != NULL)
		{
			scan = pdelete;
			pdelete = pdelete->next;
		}
		node_data_free(&(pdelete->item));
		free(pdelete);
		pdelete = NULL;
		scan->next = NULL;
		return TRUE;
	}	
	
	for (num = 0; (num < pos) && (scan->next != NULL); num++)
	{
		scan = scan->next;
	}
	
	if (scan->next == NULL)
	{
		return FALSE;
	}
	else
	{
		pdelete = scan->next;
		scan->next = pdelete->next;
		node_data_free(&(pdelete->item));
		free(pdelete);
		pdelete = NULL;
	}
	return TRUE;	
}

/*get the position 'pos' and then return the data it refers to*/
static items *list_get_node(const linklist llist, int pos)
{
	node *scan;

	scan = list_get_node_addr(llist, pos);

	return (scan ? &(scan->item) : NULL);
}

/*swap the two nodes*/
static int list_swap_node(const linklist llist, int p1, int p2)
{	
	node *prev_1, *cur_1, *next_1;
	node *prev_2, *cur_2, *next_2;
	int len, tmp;
	
	len = list_count(llist);
	/*ask p1 and p2 should be above zero and below the length*/
	if (!(p1 < len && p2 < len && p1 >= 0 && p2 >= 0))
	{
		return FALSE;
	}
	/*when p1 equals p2, returns*/
	if (p1 == p2)
	{
		return TRUE;
	}

	/*if p1 > p2, swap p1 and p2*/
	if (p1 > p2)
	{
		tmp = p1;
		p1 = p2;
		p2 = tmp;
	}
	
	/*get address*/
	prev_1 = list_get_node_addr(llist, p1 - 1);
	cur_1 = list_get_node_addr(llist, p1);
	next_1 = list_get_node_addr(llist, p1 + 1);
	prev_2 = list_get_node_addr(llist, p2 - 1);
	cur_2 = list_get_node_addr(llist, p2);
	next_2 = list_get_node_addr(llist, p2 + 1);
	/* p1 and p2 are not neighbours */
	if ( p1+1 != p2 )
	{
		prev_1->next = cur_2;
		cur_2->next = next_1;
		prev_2->next = cur_1;
		cur_1->next = next_2;
	}
	/* p1 and p2 are heighbours, so next_1 is point to p2 */
	else
	{
		prev_1->next = cur_2;
		cur_2->next = cur_1;		
		cur_1->next = next_2;
	}

	return TRUE;
}

/*get the node address*/
static node *list_get_node_addr(const linklist llist, int pos)
{
	node *scan;
	int num;
	
	assert(llist);
	
	if (list_is_empty(llist))
	{
		return NULL;
	}
	
	scan = llist->next;
	if (pos == -2)
	{
		while (scan->next != NULL)
		{
			scan = scan->next;
		}		
		return scan;
	}
	else if ( pos == -1)
	{
		return llist;
	}
	
	for (num = 0; (num < pos) && (scan != NULL); num++)
	{
		scan = scan->next;
	}
	if ((scan == NULL) && (num < pos))
	{
		return NULL;
	}	
	return scan;
}

/*debug API*/
/*show the list*/
void list_onshow(const linklist llist)
{
	node *scan;
	int num = 0;

	assert(llist);

	scan = llist->next;
	while (scan != NULL)
	{
		printf("node :[ %d ]: ", num++);
		node_data_display(&(scan->item));
		scan = scan->next;
	}
}