dlist.c

此代码是C编的EWZ的测试程序,大家可以尝试对这个包里lena.pgm进行图像压缩处理.

/*--------------------------------------------------------------------------------------------*/
#include <stdlib.h>
#include <string.h>
#include "dlist.h"


/*--------------------------------------------------------------------------------------------*/
void DListInit(DList *dlist, void (*destroy)(void *data),
					int  (*match)(const void *key1, const void *key2),
					void (*print)(int i, const void *data))
{
	dlist->size = 0;
	dlist->destroy = destroy;
	dlist->match = match;
	dlist->print = print;
	dlist->head = NULL;
	dlist->tail = NULL;
	return;
}

/*--------------------------------------------------------------------------------------------*/
void DListDestroy(DList *dlist)
{
	void *data;

	/* Remove each element */
	while (DListSize(dlist) > 0){
		if (DListRemove(dlist, DListTail(dlist), (void **)&data) == 0 
			&& dlist->destroy != NULL){
			/* Call a user-defined function to free dynamically allocated data */
			dlist->destroy(data);
		}
	}
	memset(dlist, 0, sizeof(DList));
	return;
}

/*--------------------------------------------------------------------------------------------*/
int  DListAppend(DList *dlist, const void *data)
{
	return DListInsertNext(dlist, DListTail(dlist), data);
}

/*--------------------------------------------------------------------------------------------*/
int  DListInsertAsHead(DList *dlist, const void *data)
{
	return DListInsertPrev(dlist, DListHead(dlist), data);
}

/*--------------------------------------------------------------------------------------------*/
int  DListInsertNext(DList *dlist, DListElement *element, const void *data)
{
	DListElement *NewElement;

	if ((NewElement = (DListElement *)malloc(sizeof(DListElement))) == NULL){
		return -1;
	}

	NewElement->data = (void *)data;

	if (DListSize(dlist) == 0){
		/* Handle insertion when the list is empty */
		dlist->head = NewElement;
		dlist->head->prev = NULL;
		dlist->head->next = NULL;
		dlist->tail = NewElement;
	}
	else{
		/* handle insertion when list is not empty */
		NewElement->next = element->next;
		NewElement->prev = element;
		if(element->next == NULL){
			dlist->tail = NewElement;
		}
		else{
			element->next->prev = NewElement;
		}
		element->next = NewElement;
	}
		
	/* adjust the size of the list to account for the inserted element */	
	dlist->size++;

	return 0;
}

/*--------------------------------------------------------------------------------------------*/
int  DListInsertPrev(DList *dlist, DListElement *element, const void *data)
{
	DListElement *NewElement;

	if ((NewElement = (DListElement *)malloc(sizeof(DListElement))) == NULL){
		return -1;
	}

	NewElement->data = (void *)data;

	if (DListSize(dlist) == 0){
		/* Handle insertion when the list is empty */
		dlist->head = NewElement;
		dlist->head->prev = NULL;
		dlist->head->next = NULL;
		dlist->tail = NewElement;
	}
	else{
		/* handle insertion when list is not empty */
		NewElement->next = element;
		NewElement->prev = element->prev;
		if (element->prev == NULL){
			dlist->head = NewElement;
		}
		else{
			element->prev->next = NewElement;
		}
		element->prev = NewElement;
	}

	/* adjust the size of the list to account for the inserted element */	
	dlist->size++;

	return 0;
}

/*--------------------------------------------------------------------------------------------*/
/* insert a sub list before the element into the main list 
 * 
 * author : mow-song, ng
 * date   : 25 Apr. 2004
 *
 */
int DListInsertListPrev(DList *mainlist, DList *sublist, DListElement *element)
{
   DListElement *prev;

   if (mainlist->match != sublist->match || mainlist->print != sublist->print ||
      mainlist->destroy != sublist->destroy){
      return -1;      
   }

   if (DListSize(sublist)==0){
      /* handle insertion when sublist is empty */
      /* NOP */
   }
   else if ((DListSize(mainlist)==0)){
      /* handle insertion when mainlist is empty */
      mainlist->head = sublist->head;
      mainlist->tail = sublist->tail;
      mainlist->size = sublist->size;
   }
   else{
      /* connect sublist to previous element */
      if (element == DListHead(mainlist)){
         // no previous element
         mainlist->head = sublist->head;
      }
      else{
         prev = element->prev;
         prev->next = sublist->head;
         sublist->head->prev = prev;
         
      }

      /* connect the tail of the sublist to element */
      sublist->tail->next = element;
      element->prev = sublist->tail;         
      mainlist->size += sublist->size;
      
   }

   return 0;
}

/*--------------------------------------------------------------------------------------------*/
/* insert a sub list after the element into the main list 
 * 
 * author : mow-song, ng
 * date   : 25 Apr. 2004
 *
 */
int DListInsertListNext(DList *mainlist, DList *sublist, DListElement *element)
{
   DListElement *next;

   if (mainlist->match != sublist->match || mainlist->print != sublist->print ||
      mainlist->destroy != sublist->destroy){
      return -1;      
   }

   if (DListSize(sublist)==0){
      /* handle insertion when sublist is empty */
      /* NOP */
   }
   else if ((DListSize(mainlist)==0)){
      /* handle insertion when mainlist is empty */
      mainlist->head = sublist->head;
      mainlist->tail = sublist->tail;
      mainlist->size = sublist->size;
   }
   else{
      /* connect tail of sublist to next element */
      if (element == DListTail(mainlist)){
         // no next element
         mainlist->tail = sublist->tail;
      }
      else{
         next = element->next;
         next->prev = sublist->tail;
         sublist->tail->next = next;
      }

      /* connect the head of sublist to the element */
      element->next = sublist->head;
      sublist->head->prev = element;      
      mainlist->size += sublist->size;     
      
   }

   return 0;
}

/*--------------------------------------------------------------------------------------------*/
int  DListRemove(DList *dlist, DListElement *element, void **data)
{
	if (element == NULL || DListSize(dlist) == 0){
		return -1;
	}

	/* return the data pointer */
	*data = element->data;

	/* remove the element from the list */
	if (element == dlist->head){
		dlist->head = element->next;
		if (dlist->head == NULL){
			dlist->tail = NULL;
		}
		else{
			element->next->prev = NULL;
		}
	}
	else{
		element->prev->next = element->next;

		if (element->next == NULL){
			dlist->tail = element->prev;
		}
		else{
			element->next->prev = element->prev;
		}
	}

	/* free the list element */
	free(element);

	/* adjust the list size */
	dlist->size--;
		
	return 0;
}

/*--------------------------------------------------------------------------------------------*/
void DListPrint(const DList *dlist) 
{	
	DListElement *element;
	int *data, i;
	
	fprintf(stdout, "DList size is %d\n", DListSize(dlist));
	
	if (dlist->print==NULL){
		return;
	}

	i = 0;
	element = DListHead(dlist);
	
	while (1) {
		data = DListData(element);
		dlist->print(i, data);
		i++;
		if (DListIsTail(element)){
			break;
		}
		else{
			element = DListNext(element);
		}
	}
	return;
}
/*--------------------------------------------------------------------------------------------*/