雙鏈表_ZenDei技術網路在線

雙向鏈表的實現創建3個文件：doubleLinked.h、doubleLinked.c、doubleLinkedTest.c doubleLinked.h #ifndef DOUBLE_LINKED_H_ #define DOUBLE_LINKED_H_ #ifdef lxx_gnuc #defi ...

雙向鏈表的實現

創建3個文件：doubleLinked.h、doubleLinked.c、doubleLinkedTest.c

doubleLinked.h

#ifndef DOUBLE_LINKED_H_
#define DOUBLE_LINKED_H_

#ifdef __GNUC__
	#define DEPRECATED __attribute__( (deprecated) )
#elif defined(_MSC_VER)
	#define DEPRECATED __declspec( deprecated )
#else
	#define DEPRECATED
#endif

#ifndef PTOI
	#define PTOI( p ) ((int32_t)(int64_t)(p))
#endif
#ifndef ITOP
	#define ITOP( i ) ((void *)(int64_t)(i))
#endif

#define ADT DoubleLinked

#define addFirstDoubleLinked    addHeadDoubleLinked
#define addLastDoubleLinked     addTailDoubleLinked
#define setFirstDoubleLinked    setHeadDoubleLinked
#define setLastDoubleLinked     setTailDoubleLinked
#define removeFirstDoubleLinked removeHeadDoubleLinked
#define removeLastDoubleLinked  removeTailDoubleLinked
#define getFirstDoubleLinked    getHeadDoubleLinked
#define getLastDoubleLinked     getTailDoubleLinked


// 功能: a與b的比較過程.
// 參數: a, b.
// 返回: a>b返回正數, a<b返回負數, 否則返回0.
// 註意: a!=NULL且b=NULL時返回正數, a=NULL且b!=NULL時返回負數, a=b=NULL時返回0.
typedef int ( CompareFunc )( const void *a, const void *b );

typedef struct NodeDoubleLinked DoubleLinked;


// 功能: 創建新的鏈表.
// 參數: 無.
// 返回: 新的鏈表.
// 註意: 當 記憶體分配失敗 時將錯誤退出程式.
extern ADT *newDoubleLinked( void );

// 功能: 將用戶數據加入到鏈表的指定索引位置.
// 參數: list(鏈表對象的指針), index(索引位置), data(用戶數據).
// 返回: 被加入到鏈表的用戶數據.
// 註意: 索引位置從0開始計算.
//       當 list=NULL 或 index<0 或 index>=表尾索引 時將錯誤退出程式.
extern void *addDoubleLinked( ADT *list, int32_t index, void *data );

// 功能: 將用戶數據加入到鏈表的表頭.
// 參數: list(鏈表對象的指針), data(用戶數據).
// 返回: 被加入到鏈表表頭的用戶數據.
// 註意: 當 list=NULL 時將錯誤退出程式.
extern void *addHeadDoubleLinked( ADT *list, void *data );

// 功能: 將用戶數據加入到鏈表的表尾.
// 參數: list(鏈表對象的指針), data(用戶數據).
// 返回: 被加入到鏈表表尾的用戶數據.
// 註意: 當 list=NULL 時將錯誤退出程式.
extern void *addTailDoubleLinked( ADT *list, void *data );

// 功能: 設置鏈表的指定索引位置的用戶數據.
// 參數: list(鏈表對象的指針), index(索引位置), data(新用戶數據).
// 返回: 被加入到鏈表的用戶數據.
// 註意: 索引位置從0開始計算.
//       當 list=NULL 時將錯誤退出程式.
//       當 index<0 或 index>表尾索引 時分別新建鏈表表頭或表尾用來放置 data.
extern void *setDoubleLinked( ADT *list, int32_t index, void *data );

// 功能: 設置鏈表表頭的用戶數據.
// 參數: list(鏈表對象的指針), data(新用戶數據).
// 返回: 被加入到鏈表表頭的用戶數據.
// 註意: 當 list=NULL 時將錯誤退出程式.
//       是 空鏈表狀態 時新建鏈表表頭用來放置 data.
extern void *setHeadDoubleLinked( ADT *list, void *data );

// 功能: 設置鏈表表尾的用戶數據.
// 參數: list(鏈表對象的指針), data(新用戶數據).
// 返回: 被加入到鏈表表尾的用戶數據.
// 註意: 當 list=NULL 時將錯誤退出程式.
//       是 空鏈表狀態 時新建鏈表表尾用來放置 data.
extern void *setTailDoubleLinked( ADT *list, void *data );

// 功能: 移除鏈表指定索引位置的用戶數據.
// 參數: list(鏈表對象的指針), index(索引位置).
// 返回: 被移除的用戶數據.
// 註意: 索引位置從0開始計算.
//       當 list=NULL 或 index<0 或 index>表尾索引 或 是空鏈表狀態 時將錯誤退出程式.
extern void *removeDoubleLinked( ADT *list, int32_t index );

// 功能: 移除鏈表表頭的用戶數據.
// 參數: list(鏈表對象的指針).
// 返回: 被移除的鏈表表頭的用戶數據.
// 註意: 當 list=NULL 或 是空鏈表狀態 時將錯誤退出程式.
extern void *removeHeadDoubleLinked( ADT *list );

// 功能: 移除鏈表表尾的用戶數據.
// 參數: list(鏈表對象的指針).
// 返回: 被移除的鏈表表頭的用戶數據.
// 註意: 當 list=NULL 或 是空鏈表狀態 時將錯誤退出程式.
extern void *removeTailDoubleLinked( ADT *list );

// 功能: 偷看鏈表指定索引位置的用戶數據.
// 參數: list(鏈表對象的指針), index(索引位置).
// 返回: 鏈表指定索引位置的用戶數據.
// 註意: 索引位置從0開始計算.
//       當 list=NULL 或 index<0 或 index>表尾索引 或 是空鏈表狀態 時將錯誤退出程式.
extern void *getDoubleLinked( ADT *list, int32_t index );

// 功能: 偷看鏈表表頭的用戶數據.
// 參數: list(鏈表對象的指針).
// 返回: 鏈表表頭的用戶數據.
// 註意: 當 list=NULL 或 是空鏈表狀態 時將錯誤退出程式.
extern void *getHeadDoubleLinked( ADT *list );

// 功能: 偷看鏈表表尾的用戶數據.
// 參數: list(鏈表對象的指針).
// 返回: 鏈表表尾的用戶數據.
// 註意: 當 list=NULL 或 是空鏈表狀態 時將錯誤退出程式.
extern void *getTailDoubleLinked( ADT *list );

// 功能: 鏈表中所有用戶數據中是否包含了data.
// 參數: list(鏈表對象的指針), data(需查找的用戶數據), cmp(比較函數的指針).
// 返回: 包含data返回1, 否則返回0.
// 註意: 當 list=NULL 或 cmp=NULL 時將錯誤退出程式.
extern int existDoubleLinked( ADT *list, void *data, CompareFunc *cmp );

// 功能: 從鏈表表頭至鏈表表尾方向查找data.
// 參數: list(鏈表對象的指針), data(需查找的用戶數據), cmp(比較函數的指針).
// 返回: 包含data, 返回data所在位置, 否則返回-1.
// 註意: 當 list=NULL 或 cmpNULL 時將錯誤退出程式.
extern int32_t findDoubleLinked( ADT *list, void *data, CompareFunc *cmp );

// 功能: 從鏈表表尾至鏈表表頭方向查找data.
// 參數: list(鏈表對象的指針), data(需查找的用戶數據), cmp(比較函數的指針).
// 返回: 包含data, 返回data所在位置, 否則返回-1.
// 註意: 當 list=NULL 或 cmp=NULL 時將錯誤退出程式.
extern int32_t findTailDoubleLinked( ADT *list, void *data, CompareFunc *cmp );

// 功能: 鏈表實際已使用大小.
// 參數: list(鏈表對象的指針).
// 返回: 鏈表實際已使用大小.
// 註意: 當 list=NULL 時將錯誤退出程式.
extern int32_t sizeDoubleLinked( ADT *list );

// 功能: 空鏈表狀態.
// 參數: list(鏈表對象的指針).
// 返回: 是空鏈表返回1, 否則返回0.
// 註意: 當 list=NULL 時將錯誤退出程式.
extern int emptyDoubleLinked( ADT *list );

// 功能: 反轉鏈表.
// 參數: list(鏈表對象的指針).
// 返回: 無.
// 註意: 當 list=NULL 時將錯誤退出程式.
extern void reversalDoubleLinked( ADT *list );

// 功能: 滿鏈表狀態.
// 參數: list(鏈表對象的指針).
// 返回: 是滿鏈表返回1, 否則返回0.
// 註意: 當 list=NULL 時將錯誤退出程式.
// 被棄用的函數.
extern DEPRECATED int fullDoubleLinked( ADT *list );

// 功能: 鏈表最大容量.
// 參數: list(鏈表對象的指針).
// 返回: 鏈表最大容量.
// 註意: 當 list=NULL 時將錯誤退出程式.
// 被棄用的函數.
extern DEPRECATED int32_t capacityDoubleLinked( ADT *list );

// 功能: 清空鏈表.
// 參數: list(鏈表對象的指針).
// 返回: 無.
// 註意: 當 list=NULL 時將錯誤退出程式.
extern void clearDoubleLinked( ADT *list );

// 功能: 銷毀鏈表.
// 參數: list(存放鏈表對象的指針的指針).
// 返回: 無.
// 註意: 當 list=NULL 時將錯誤退出程式.
extern void delDoubleLinked( ADT **list );

#undef ADT

#endif

doubleLinked.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include "adt.h"


// 功能: 列印錯誤信息後就錯誤退出程式.
// 參數: expression(錯誤判斷表達式), message(需列印的錯誤信息).
// 返回: 無.
// 註意: 當表達式 expression 為真時, 才觸發.
#define ERROR_EXIT( expression, message )                                    \
if( (expression) ) {                                                         \
	fprintf( stderr, "\nerror location: file = %s, func = %s, line = %d.\n", \
	                       __FILE__, __func__, __LINE__ );                   \
	fprintf( stderr, "error  message: %s%s.\n\a",                            \
	                       (message) != NULL ? (message) : __func__,         \
		                   (message) != NULL ? "" : " function error" );     \
	exit( EXIT_FAILURE );                                                    \
}

// 功能: 分配記憶體, 與 malloc 功能一樣.
// 參數: p(傳入傳出參數), size(位元組).
// 返回: 無, 實際通過參數p進行傳出.
// 註意: 當 記憶體分配失敗 時將錯誤退出程式.
#define NEW( p, size ) ({                              \
	ERROR_EXIT( (p) == NULL, "NullPointerException" ); \
	*(p) = malloc( (size) );                           \
	ERROR_EXIT( *(p) == NULL, "OutOfMemoryError" );    \
})

// 功能: 分配記憶體並把每個位元組置0, 與 calloc 功能一樣.
// 參數: p(傳入傳出參數), size(位元組), n(數量).
// 返回: 無, 實際通過參數p進行傳出.
// 註意: 當 記憶體分配失敗 時將錯誤退出程式.
#define NEW0( p, nE, sizeofE ) ({                             \
	ERROR_EXIT( (p) == NULL, "NullPointerException" );        \
	ERROR_EXIT( (nE) < 0, "Parameter 'nE' Error" );           \
	ERROR_EXIT( (sizeofE) < 0, "Parameter 'sizeofE' Error" ); \
	*(p) = calloc( nE, sizeofE );                             \
	ERROR_EXIT( *(p) == NULL, "OutOfMemoryError" );           \
})

#define DEL( p ) ({                     \
	if( (p) != NULL && *(p) != NULL ) { \
		free( *(p) );                   \
		*(p) = NULL;                    \
	}                                   \
})

#define ADT DoubleLinked


typedef struct NodeDoubleLinked {
	void *data;
	struct NodeDoubleLinked *prev;
	struct NodeDoubleLinked *next;
} Node, DoubleLinked;


ADT *newDoubleLinked( void ) {
	ADT *list = NULL;

	NEW0( &list, 1, sizeof(*list) );

	return list;
}

void *addDoubleLinked( ADT *list, int32_t index, void *data ) {
	Node *indexN = NULL, *node = NULL;

	ERROR_EXIT( list == NULL, "NullPointerException" );
	ERROR_EXIT( index < 0 || index > PTOI( list->data ), "IndexOutOfBoundsException" );
	for( indexN = list->next; --index >= 0; indexN = indexN->next ) {}
	NEW( &node, sizeof(*node) );
	node->data = data;
	node->next = indexN;
	if( indexN != NULL ) {
		node->prev = indexN->prev;
		if( indexN->prev != NULL ) {
			indexN->prev->next = node;
		}
		indexN->prev = node;
	} else {
		node->prev = list->prev;
		if( list->prev != NULL ) {
			list->prev->next = node;
		}
		list->prev = node;
	}
	list->next = list->next != indexN ? list->next : node;
	list->next = list->next != NULL ? list->next : node;
	list->data = ITOP( PTOI( list->data ) + 1 );

	return data;
}

void *addHeadDoubleLinked( ADT *list, void *data ) {
	Node *node = NULL;

	ERROR_EXIT( list == NULL, "NullPointerException" );
	NEW( &node, sizeof(*node) );
	node->data = data;
	node->prev = NULL;
	node->next = list->next;
	if( list->next != NULL ) {
		list->next->prev = node;
	}
	list->prev = list->prev != NULL ? list->prev : node;
	list->next = node;
	list->data = ITOP( PTOI( list->data ) + 1 );

	return data;
}

void *addTailDoubleLinked( ADT *list, void *data ) {
	Node *node = NULL;

	ERROR_EXIT( list == NULL, "NullPointerException" );
	NEW( &node, sizeof(*node) );
	node->data = data;
	node->prev = list->prev;
	node->next = NULL;
	if( list->prev != NULL ) {
		list->prev->next = node;
	}
	list->next = !list->next ? node : list->next;
	list->prev = node;
	list->data = ITOP( PTOI( list->data ) + 1 );

	return data;
}

void *setDoubleLinked( ADT *list, int32_t index, void *data ) {
	Node *indexN = NULL;
	ERROR_EXIT( list == NULL, "NullPointerException" );
	ERROR_EXIT( index < 0 || index > PTOI( list->data ), "IndexOutOfBoundsException" );
	for( indexN = list->next; --index >= 0; indexN = indexN->next ) {}

	return indexN->data = data;
}

void *setHeadDoubleLinked( ADT *list, void *data ) {
	ERROR_EXIT( list == NULL, "NullPointerException" );
	ERROR_EXIT( PTOI( list->data ) < 1, "EmptyContainerError" );

	return list->next->data = data;
}

void *setTailDoubleLinked( ADT *list, void *data ) {
	ERROR_EXIT( list == NULL, "NullPointerException" );
	ERROR_EXIT( PTOI( list->data ) < 1, "EmptyContainerError" );

	return list->prev->data = data;
}

void *removeDoubleLinked( ADT *list, int32_t index ) {
	void *data = NULL;
	Node *indexN = NULL;

	ERROR_EXIT( list == NULL, "NullPointerException" );
	ERROR_EXIT( index < 0 || index >= PTOI( list->data ), "IndexOutOfBoundsException" );
	for( indexN = list->next; --index >= 0; indexN = indexN->next ) {}
	if( indexN->prev != NULL ) {
		indexN->prev->next = indexN->next;
	}
	if( indexN->next != NULL ) {
		indexN->next->prev = indexN->prev;
	}
	list->next = list->next != indexN ? list->next : indexN->next;
	list->prev = list->prev != indexN ? list->prev : indexN->prev;
	list->data = ITOP( PTOI( list->data ) - 1 );
	data = indexN->data;
	DEL( &indexN );

	return data;
}

void *removeHeadDoubleLinked( ADT *list ) {
	void *data = NULL;
	Node *node = NULL;

	ERROR_EXIT( list == NULL, "NullPointerException" );
	ERROR_EXIT( PTOI( list->data ) < 1, "EmptyContainerError" );
	node = list->next;
	if( node->next != NULL ) {
		node->next->prev = node->prev;
	}
	list->prev = list->prev != node ? list->prev : NULL; // 只有一個節點時.
	list->next = node->next;
	list->data = ITOP( PTOI( list->data ) - 1 );
	data = node->data;
	DEL( &node );

	return data;
}

void *removeTailDoubleLinked( ADT *list ) {
	void *data = NULL;
	Node *node = NULL;

	ERROR_EXIT( list == NULL, "NullPointerException" );
	ERROR_EXIT( PTOI( list->data ) < 1, "EmptyContainerError" );
	node = list->prev;
	if( node->prev != NULL ) {
		node->prev->next = node->next;
	}
	list->prev = node->prev;
	list->next = list->next != node ? list->next : NULL; // 只有一個節點時.
	list->data = ITOP( PTOI( list->data ) - 1 );
	data = node->data;
	DEL( &node );

	return data;
}

void *getDoubleLinked( ADT *list, int32_t index ) {
	Node *indexN = NULL;

	ERROR_EXIT( list == NULL, "NullPointerException" );
	ERROR_EXIT( index < 0 || index >= PTOI( list->data ), "IndexOutOfBoundsException" );
	for( indexN = list->next; --index >= 0; indexN = indexN->next ) {}

	return indexN->data;
}

void *getHeadDoubleLinked( ADT *list ) {
	ERROR_EXIT( list == NULL, "NullPointerException" );
	ERROR_EXIT( PTOI( list->data ) < 1, "EmptyContainerError" );

	return list->next->data;
}

void *getTailDoubleLinked( ADT *list ) {
	ERROR_EXIT( list == NULL, "NullPointerException" );
	ERROR_EXIT( PTOI( list->data ) < 1, "EmptyContainerError" );

	return list->prev->data;
}

int existDoubleLinked( ADT *list, void *data, CompareFunc *cmp ) {
	Node *node = NULL;

	ERROR_EXIT( list == NULL, "NullPointerException" );
	ERROR_EXIT( !cmp, "NullPointerException" );
	for( node = list->next; node; node = node->next ) {
		if( !cmp( node->data, data ) ) {
			return 1;
		}
	}

	return -1;
}

int32_t findDoubleLinked( ADT *list, void *data, CompareFunc *cmp ) {
	int32_t i = 0;
	Node *node = NULL;

	ERROR_EXIT( list == NULL, "NullPointerException" );
	ERROR_EXIT( !cmp, "NullPointerException" );
	for( node = list->next; node != NULL; node = node->next ) {
		if( !cmp( node->data, data ) ) {
			break;
		}
		++i;
	}

	return i >= PTOI( list->data ) ? -1 : i;
}

int32_t findTailDoubleLinked( ADT *list, void *data, CompareFunc *cmp ) {
	int32_t i = 0;
	Node *node = NULL;

	ERROR_EXIT( list == NULL, "NullPointerException" );
	ERROR_EXIT( cmp == NULL, "NullPointerException" );
	for( node = list->prev; node != NULL; node = node->prev ) {
		if( !cmp( node->data, data ) ) {
			break;
		}
		++i;
	}

	return PTOI( list->data ) - 1 - i;
}

int32_t sizeDoubleLinked( ADT *list ) {
	ERROR_EXIT( list == NULL, "NullPointerException" );

	return PTOI( list->data );
}

int emptyDoubleLinked( ADT *list ) {
	ERROR_EXIT( list == NULL, "NullPointerException" );

	return PTOI( list->data ) < 1;
}

static void reverse( Node *node ) {
	Node *t = NULL;

	if( node == NULL ) {
		return;
	}
	reverse( node->next );
	t = node->prev;
	node->prev = node->next;
	node->next = t;
}
void reversalDoubleLinked( ADT *list ) {
	Node *p1 = NULL, *p2 = NULL, *p3 = NULL;

	ERROR_EXIT( list == NULL, "NullPointerException" );
	#if 1
	for( p2 = list; p2 != NULL; p2 = p3 ) { // 調換prev與next指針.
		p3 = p2->next;
		p1 = p2->next;
		p2->next = p2->prev;
		p2->prev = p1;
	}
	#else
	list->prev = list->next;
	for( p2 = list->next; p2 != NULL; p2 = p3 ) { // 三指針反轉鏈表.
		p3 = p2->next;
		p2->next = p1;
		p2->prev = NULL;
		if( p1 != NULL ) {
			p2->prev = p1->prev;
			p1->prev = p2;
		}
		p1 = p2;
	}
	list->next = p1;
	#endif
	if( 0 ) reverse( list );
}

int fullDoubleLinked( ADT *list ) {
	ERROR_EXIT( list == NULL, "NullPointerException" );

	return 0;
}

int32_t capacityDoubleLinked( ADT *list ) {
	ERROR_EXIT( list == NULL, "NullPointerException" );

	return INT32_MAX;
}

void clearDoubleLinked( ADT *list ) {
	Node *c = NULL, *t = NULL;

	ERROR_EXIT( list == NULL, "NullPointerException" );
	for( c = list->next; c != NULL; c = t ) {
		t = c->next;
		DEL( &c );
	}
	list->data = ITOP( 0 );
	list->next = NULL;
	list->prev = NULL;
}

void delDoubleLinked( ADT **list ) {
	Node *c = NULL, *t = NULL;

	ERROR_EXIT( list == NULL, "NullPointerException" );
	for( c = (*list)->next; c != NULL; c = t ) {
		t = c->next;
		DEL( &c );
	}
	DEL( list );
}

void addressDoubleLinked( ADT *list ) {
	Node *node = NULL;

	ERROR_EXIT( list == NULL, "NullPointerException" );
	printf( "next[" );
	for( node = list->next; node != NULL; node = node->next ) {
		printf( "%5d%s", *(int32_t *) node->data, !node->next ? "" : "->" );
	}
	printf( "]\n" );
	printf( "prev[" );
	for( node = list->prev; node != NULL; node = node->prev ) {
		printf( "%5d%s", *(int32_t *) node->data, !node->prev ? "" : "<-" );
	}
	printf( "]\n" );
	printf( "list->next = %d, ", !list->next ? INT_MIN : *(int32_t *) list->next->data );
	printf( "list->prev = %d\n", !list->prev ? INT_MIN : *(int32_t *) list->prev->data );
}

doubleLinkedTest.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
#include "doubleLinked.h"


// 功能: 對數組的某一區間內的元素值進行隨機化.
// 參數: a(數組首地址), left(左閉區間), right(右閉區間), v(最大隨機值).
// 返回: 無.
// 註意: 當v是正數/負數/零時,隨機值的區間分別為[-v, v]/[]/[].
static void randomArray( int32_t a[], int32_t left, int32_t right, int32_t v ) {
	v -= v != INT32_MAX ? 0 : 1;
	while( left <= right ) {
		a[left++] = rand() % (v + 1) - rand() % (v + 1);
	}
}

// 功能: 將數組的某一區間內的元素值送入到文件流中.
// 參數: a(數組首地址), left(左閉區間), right(右閉區間), fp(文件流指針).
// 返回: 無.
// 註意: 無.
static void printArray( const int32_t a[], int32_t left, int32_t right, FILE *fp ) {
	fprintf( fp, "[" );
	while( left <= right ) {
		fprintf( fp, "%5d%s", a[left], left != right ? ", " : "" );
		++left;
	}
	fprintf( fp, "]\n" );
}

int cmp( const void *a, const void *b ) {
	return *(int32_t *) a - *(int32_t *) b;
}

#if 0
int main( int argc, char *argv[] ) {
	int32_t *a = NULL;
	int32_t i = 0, n = 0;
	DoubleLinked *list = NULL;

	printf( "please input array length: n = " );
	scanf( "%d%*c", &n );
	printf( "\n" );

	NEW( &a, sizeof(*a) * n );

	randomArray( a, 0, n - 1, 123 );
	printArray( a, 0, n - 1, stdout );

	list = newDoubleLinked();

	addressDoubleLinked( list );
	printf( "emptyDoubleLinked( list ) = %s\n", emptyDoubleLinked( list ) ? "true" : "false" );
	printf( "sizeDoubleLinked( list )  = %d\n", sizeDoubleLinked( list ) );
	printf( "getFirstDoubleLinked( list ) = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getFirstDoubleLinked( list ) : INT32_MIN );
	printf( "getLastDoubleLinked( list )  = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getLastDoubleLinked( list ) : INT32_MIN );
	printf( "\n" );

	for( i = 0; i < n; ++i ) {
		printf( "addDoubleLinked( list, %d, &a[%d] ) = %d\n", i, i, *(int32_t *) addDoubleLinked( list, i, &a[i] ) );
	}
	addressDoubleLinked( list );
	printf( "emptyDoubleLinked( list ) = %s\n", emptyDoubleLinked( list ) ? "true" : "false" );
	printf( "sizeDoubleLinked( list )  = %d\n", sizeDoubleLinked( list ) );
	printf( "getFirstDoubleLinked( list ) = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getFirstDoubleLinked( list ) : INT32_MIN );
	printf( "getLastDoubleLinked( list )  = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getLastDoubleLinked( list ) : INT32_MIN );
	printf( "\n" );

	for( i = 0; i < n; ++i ) {
		printf( "getDoubleLinked( list, %d ) = %d\n", i, *(int32_t *) getDoubleLinked( list, i ) );
	}
	addressDoubleLinked( list );
	printf( "emptyDoubleLinked( list ) = %s\n", emptyDoubleLinked( list ) ? "true" : "false" );
	printf( "sizeDoubleLinked( list )  = %d\n", sizeDoubleLinked( list ) );
	printf( "getFirstDoubleLinked( list ) = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getFirstDoubleLinked( list ) : INT32_MIN );
	printf( "getLastDoubleLinked( list )  = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getLastDoubleLinked( list ) : INT32_MIN );
	printf( "\n" );

	int32_t k = INT32_MAX;
	#if 1
	switch( 3 ) {
		case 0:
			i = 0; break;
		case 1:
			i = 1; break;
		case 2:
			i = sizeDoubleLinked( list ) - 1; break;
		case 3:
			i = sizeDoubleLinked( list ); break;
	}
	printf( "addDoubleLinked( list, %d, &k ) = %d\n", i, *(int32_t *) addDoubleLinked( list, i, &k ) );
	#else
	printf( "addFirstDoubleLinked( list, &k ) = %d\n", *(int32_t *) addFirstDoubleLinked( list, &k ) );
	printf( "addLastDoubleLinked( list, &k ) = %d\n", *(int32_t *) addLastDoubleLinked( list, &k ) );
	#endif
	addressDoubleLinked( list );
	printf( "emptyDoubleLinked( list ) = %s\n", emptyDoubleLinked( list ) ? "true" : "false" );
	printf( "sizeDoubleLinked( list )  = %d\n", sizeDoubleLinked( list ) );
	printf( "getFirstDoubleLinked( list ) = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getFirstDoubleLinked( list ) : INT32_MIN );
	printf( "getLastDoubleLinked( list )  = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getLastDoubleLinked( list ) : INT32_MIN );
	printf( "\n" );

	#if 0
	switch( 3 ) {
		case 0:
			i = 0; break;
		case 1:
			i = 1; break;
		case 2:
			i = sizeDoubleLinked( list ) - 1; break;
	}
	printf( "removeDoubleLinked( list, %d ) = %d\n", i, *(int32_t *) removeDoubleLinked( list, i ) );
	#else
	printf( "removeFirstDoubleLinked( list ) = %d\n", *(int32_t *) removeFirstDoubleLinked( list ) );
	printf( "removeLastDoubleLinked( list ) = %d\n", *(int32_t *) removeLastDoubleLinked( list ) );
	while( !emptyDoubleLinked( list ) ) {
		printf( "removeFristDoubleLinked( list ) = %d\n", *(int32_t *) removeFirstDoubleLinked( list ) );
	}
	#endif
	addressDoubleLinked( list );
	printf( "emptyDoubleLinked( list ) = %s\n", emptyDoubleLinked( list ) ? "true" : "false" );
	printf( "sizeDoubleLinked( list )  = %d\n", sizeDoubleLinked( list ) );
	printf( "getFirstDoubleLinked( list ) = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getFirstDoubleLinked( list ) : INT32_MIN );
	printf( "getLastDoubleLinked( list )  = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getLastDoubleLinked( list ) : INT32_MIN );
	printf( "\n" );

	#if 0
	printf( "findDoubleLinked( list, &k, cmp ) = %d\n", findDoubleLinked( list, &k, cmp ) );
	#else
	printf( "findTailDoubleLinked( list, &k, cmp ) = %d\n", findTailDoubleLinked( list, &k, cmp ) );
	#endif
	addressDoubleLinked( list );
	printf( "emptyDoubleLinked( list ) = %s\n", emptyDoubleLinked( list ) ? "true" : "false" );
	printf( "sizeDoubleLinked( list )  = %d\n", sizeDoubleLinked( list ) );
	printf( "getFirstDoubleLinked( list ) = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getFirstDoubleLinked( list ) : INT32_MIN );
	printf( "getLastDoubleLinked( list )  = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getLastDoubleLinked( list ) : INT32_MIN );
	printf( "\n" );

	reversalDoubleLinked( list );
	addressDoubleLinked( list );
	printf( "emptyDoubleLinked( list ) = %s\n", emptyDoubleLinked( list ) ? "true" : "false" );
	printf( "sizeDoubleLinked( list )  = %d\n", sizeDoubleLinked( list ) );
	printf( "getFirstDoubleLinked( list ) = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getFirstDoubleLinked( list ) : INT32_MIN );
	printf( "getLastDoubleLinked( list )  = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getLastDoubleLinked( list ) : INT32_MIN );
	printf( "\n" );

	delDoubleLinked( &list );
	DEL( &a );

	return EXIT_SUCCESS;
}
#else
int main( int argc, char *argv[] ) {
	int32_t n = 0, i = 0, *a = NULL;
	DoubleLinked *list = NULL;

	printf( "please input array length: n = " );
	scanf( "%d%*c", &n );
	printf( "\n" );

	NEW( &a, sizeof(*a) * n );
	randomArray( a, 0, n - 1, 321 );
	printArray( a, 0, n - 1, stdout );

	list = newDoubleLinked();

	printf( "emptyDoubleLinked( list ) = %s\n", emptyDoubleLinked( list ) ? "true" : "false" );
	printf( "sizeDoubleLinked( list ) = %d\n", sizeDoubleLinked( list ) );
	printf( "getFirstDoubleLinked( list ) = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getFirstDoubleLinked( list ) : INT32_MIN );
	printf( "getLastDoubleLinked( list ) = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getLastDoubleLinked( list ) : INT32_MIN );
	printf( "\n\n" );

	for( i = 0; i < n; ++i ) {
		printf( "addDoubleLinked( list, %d, &a[%d]=%d ) = %d\n", i, i, a[i], *(int32_t *) addDoubleLinked( list, i, &a[i] ) );
	}
	printf( "emptyDoubleLinked( list ) = %s\n", emptyDoubleLinked( list ) ? "true" : "false" );
	printf( "sizeDoubleLinked( list ) = %d\n", sizeDoubleLinked( list ) );
	printf( "getFirstDoubleLinked( list ) = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getFirstDoubleLinked( list ) : INT32_MIN );
	printf( "getLastDoubleLinked( list ) = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getLastDoubleLinked( list ) : INT32_MIN );
	printf( "\n\n" );

	for( i = 0; i < sizeDoubleLinked( list ); ++i ) {
		printf( "getDoubleLinked( list, %d ) = %d\n", i, *(int32_t *) getDoubleLinked( list, i ) );
	}
	printf( "emptyDoubleLinked( list ) = %s\n", emptyDoubleLinked( list ) ? "true" : "false" );
	printf( "sizeDoubleLinked( list ) = %d\n", sizeDoubleLinked( list ) );
	printf( "getFirstDoubleLinked( list ) = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getFirstDoubleLinked( list ) : INT32_MIN );
	printf( "getLastDoubleLinked( list ) = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getLastDoubleLinked( list ) : INT32_MIN );
	printf( "\n\n" );

	int32_t k = rand();
	#if 1
	switch( 3 ) {
		case 0:
			i = 0; break;
		case 1:
			i = 1; break;
		case 2:
			i = sizeDoubleLinked( list ) - 1; break;
		case 3:
			i = sizeDoubleLinked( list ); break;
		default:
			break;
	}
	printf( "addDoubleLinked( list, %d, &k=%d ) = %d\n", i, k, *(int32_t *) addDoubleLinked( list , i, &k ) );
	#else
	printf( "addFirstDoubleLinked( list, &k=%d ) = %d\n",k, *(int32_t *) addFirstDoubleLinked( list, &k ) );
	//printf( "addLastDoubleLinked( list, &k=%d ) = %d\n", k, *(int32_t *) addLastDoubleLinked( list, &k ) );
	#endif
	printf( "emptyDoubleLinked( list ) = %s\n", emptyDoubleLinked( list ) ? "true" : "false" );
	printf( "sizeDoubleLinked( list ) = %d\n", sizeDoubleLinked( list ) );
	printf( "getFirstDoubleLinked( list ) = %d\n", *(int32_t *) getFirstDoubleLinked( list ) );
	printf( "getLastDoubleLinked( list ) = %d\n", *(int32_t *) getLastDoubleLinked( list ) );
	printf( "\n\n" );

	#if 1
	switch( 2 ) {
		case 0:
			i = 0; break;
		case 1:
			i = 1; break;
		case 2:
			i = sizeDoubleLinked( list ) - 1; break;
	}
	printf( "removeDoubleLinked( list, %d ) = %d\n", i, *(int32_t *) removeDoubleLinked( list , i ) );
	#else
	//printf( "removeFirstDoubleLinked( list ) = %d\n", *(int32_t *) removeFirstDoubleLinked( list ) );
	printf( "removeLastDoubleLinked( list ) = %d\n", *(int32_t *) removeLastDoubleLinked( list ) );
	#endif
	printf( "emptyDoubleLinked( list ) = %s\n", emptyDoubleLinked( list ) ? "true" : "false" );
	printf( "sizeDoubleLinked( list ) = %d\n", sizeDoubleLinked( list ) );
	printf( "getFirstDoubleLinked( list ) = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getFirstDoubleLinked( list ) : INT32_MIN );
	printf( "getLastDoubleLinked( list ) = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getLastDoubleLinked( list ) : INT32_MIN );
	printf( "\n\n" );

	#if 0
	printf( "findDoubleLinked( list, &k ) = %d\n", findDoubleLinked( list, &k, cmp ) );
	#else
	printf( "findTailToFrontDoubleLinked( list &k ) = %d\n", findTailDoubleLinked( list, &k, cmp ) );
	#endif
	printf( "emptyDoubleLinked( list ) = %s\n", emptyDoubleLinked( list ) ? "true" : "false" );
	printf( "sizeDoubleLinked( list ) = %d\n", sizeDoubleLinked( list ) );
	printf( "getFirstDoubleLinked( list ) = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getFirstDoubleLinked( list ) : INT32_MIN );
	printf( "getLastDoubleLinked( list ) = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getLastDoubleLinked( list ) : INT32_MIN );
	printf( "\n\n" );

	addressDoubleLinked( list );
	printf( "reversal: " );
	reversalDoubleLinked( list );
	addressDoubleLinked( list );
	printf( "emptyDoubleLinked( list ) = %s\n", emptyDoubleLinked( list ) ? "true" : "false" );
	printf( "sizeDoubleLinked( list ) = %d\n", sizeDoubleLinked( list ) );
	printf( "getFirstDoubleLinked( list ) = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getFirstDoubleLinked( list ) : INT32_MIN );
	printf( "getLastDoubleLinked( list ) = %d\n", !emptyDoubleLinked( list ) ? *(int32_t *) getLastDoubleLinked( list ) : INT32_MIN );
	printf( "\n\n" );

	delDoubleLinked( &list );
	DEL( &a );

	return EXIT_SUCCESS;
}
#endif