隊列-鏈式存儲_ZenDei技術網路在線

鏈表實現隊列創建3個文件：queueLinked.h、queueLinked.c、queueLinkedTest.c queueLinked.h c include include include include "queueLinked.h" // 功能: 列印錯誤信息後就錯誤退出程式. // ...

鏈表實現隊列

創建3個文件：queueLinked.h、queueLinked.c、queueLinkedTest.c

queueLinked.h

#ifndef QUEUE_LINKED_H_
#define QUEUE_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 QueueLinked

// 功能: 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 NodeQueueLinked QueueLinked;

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

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

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

// 功能: 移除隊頭用戶數據.
// 參數: queue(隊列對象的指針).
// 返回: 被移除的隊頭的用戶數據.
// 註意: 當 queue 為NULL 或 空隊列狀態 時, 將錯誤退出程式.
extern void *pollQueueLinked( ADT *queue );

// 功能: 移除隊尾用戶數據.
// 參數: queue(隊列對象的指針).
// 返回: 被移除的隊尾的用戶數據.
// 註意: 當 queue 為NULL 或 空隊列狀態 時, 將錯誤退出程式.
extern void *pollTailQueueLinked( ADT *queue );

// 功能: 偷看隊頭的用戶數據.
// 參數: queue(隊列對象的指針).
// 返回: 隊頭的用戶數據.
// 註意: 當 queue 為NULL 或 空隊列狀態 時, 將錯誤退出程式.
extern void *peekQueueLinked( ADT *queue );

// 功能: 偷看隊尾的用戶數據.
// 參數: queue(隊列對象的指針).
// 返回: 隊尾的用戶數據.
// 註意: 當 queue 為NULL 或 空隊列狀態 時, 將錯誤退出程式.
extern void *peekTailQueueLinked( ADT *queue );

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

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

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

// 功能: 隊列實際已使用大小.
// 參數: queue(隊列對象的指針).
// 返回: 隊列實際已使用大小.
// 註意: 當 queue 為NULL 時, 將錯誤退出程式.
extern int32_t sizeQueueLinked( ADT *queue );

// 功能: 空隊列狀態.
// 參數: queue(隊列對象的指針).
// 返回: 是空隊列返回1, 否則返回0.
// 註意: 當 queue 為NULL 時, 將錯誤退出程式.
extern int emptyQueueLinked( ADT *stsack );

// 功能: 反轉隊列.
// 參數: queue(隊列對象的指針).
// 返回: 無.
// 註意: 當 queue 為NULL 時, 將錯誤退出程式.
extern void reversalQueueLinked( ADT *queue );

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

// 功能: 隊列最大容量.
// 參數: queue(隊列對象的指針).
// 返回: 隊列最大容量.
// 註意: 當 queue 為NULL 時, 將錯誤退出程式.
// 被棄用的函數.
extern DEPRECATED int32_t capacityQueueLinked( ADT *queue );

// 功能: 清空隊列.
// 參數: queue(隊列對象的指針).
// 返回: 無.
// 註意: 當 queue 為NULL 時, 將錯誤退出程式.
extern void clearQueueLinked( ADT *queue );

// 功能: 銷毀隊列.
// 參數: queue(存放隊列對象的指針的指針).
// 返回: 無.
// 註意: 當 queue 為NULL 時, 將錯誤退出程式.
extern void delQueueLinked( ADT **queue );

#undef ADT

#endif

queueLinked.c

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

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

#define MAX( a, b ) ((a) > (b) ? (a) : (b))

#define ADT QueueLinked

typedef struct NodeQueueLinked {
	void *data;
	struct NodeQueueLinked *prev; // 隊列頭結點的prev指向隊頭.
	struct NodeQueueLinked *next; // 隊列頭結點的next指向隊尾.
} Node;

ADT *newQueueLinked( void ) {
	ADT *queue = NULL;

	queue = calloc( sizeof(*queue), 1 );
	ERROR_EXIT( !queue, NULL );

	return queue;
}

void *addQueueLinked( ADT *queue, void *data ) {
	Node *n = NULL;

	ERROR_EXIT( !queue, NULL );
	n = malloc( sizeof(*n) );
	ERROR_EXIT( !n, NULL );
	n->data = data;
	n->prev = NULL;
	n->next = queue->next;
	if( queue->next != NULL ) {
		queue->next->prev = n;
	}
	queue->prev = !queue->prev ? n : queue->prev;
	queue->next = n;
	queue->data = ITOP( PTOI( queue->data ) + 1 );

	return data;
}

void *addHeadQueueLinked( ADT *queue, void *data ) {
	Node *n = NULL;

	ERROR_EXIT( !queue, NULL );
	n = malloc( sizeof(*n) );
	ERROR_EXIT( !n, NULL );
	n->data = data;
	n->prev = queue->prev;
	n->next = NULL;
	if( queue->prev != NULL ) {
		queue->prev->next = n;
	}
	queue->prev = n;
	queue->next = !queue->next ? n : queue->next;
	queue->data = ITOP( PTOI( queue->data ) + 1 );

	return data;
}

void *pollQueueLinked( ADT *queue ) {
	void *data = NULL;
	Node *n = NULL;

	ERROR_EXIT( !queue || PTOI( queue->data ) < 1, NULL );
	n = queue->prev;
	if( n->prev != NULL ) {
		n->prev->next = NULL;
	}
	queue->prev = n->prev;
	queue->next = n != queue->next ? queue->next : NULL;
	queue->data = ITOP( PTOI( queue->data ) - 1 );
	data = n->data;
	free( n );

	return data;
}

void *pollTailQueueLinked( ADT *queue ) {
	void *data = NULL;
	Node *n = NULL;

	ERROR_EXIT( !queue || PTOI( queue->data ) < 1, NULL );
	n = queue->next;
	if( n->next != NULL ) {
		n->next->prev = NULL;
	}
	queue->prev = n != queue->prev ? queue->prev : NULL;
	queue->next = n->next;
	queue->data = ITOP( PTOI( queue->data ) - 1 );
	data = n->data;
	free( n );

	return data;
}

void *peekQueueLinked( ADT *queue ) {
	ERROR_EXIT( !queue || PTOI( queue->data ) < 1, NULL );

	return queue->prev->data;
}

void *peekTailQueueLinked( ADT *queue ) {
	ERROR_EXIT( !queue || PTOI( queue->data ) < 1, NULL );

	return queue->next->data;
}

int existQueueLinked( ADT *queue, void *data, CompareFunc *cmp ) {
	Node *n = NULL;

	ERROR_EXIT( !queue || !cmp, NULL );
	for( n = queue->prev; n != NULL; n = n->prev ) {
		if( !cmp( n->data, data ) ) {
			return 1;
		}
	}

	return 0;
}

int32_t findQueueLinked( ADT *queue, void *data, CompareFunc *cmp ) {
	Node *n = NULL;
	int32_t i = 0;

	ERROR_EXIT( !queue || !cmp, NULL );
	for( n = queue->prev; n != NULL; n = n->prev ) {
		if( !cmp( n->data, data ) ) {
			return PTOI( queue->data ) - 1 - i;
		}
		++i;
	}

	return -1;
}

int32_t findTailQueueLinked( ADT *queue, void *data, CompareFunc *cmp ) {
	Node *n = NULL;
	int32_t i = 0;

	ERROR_EXIT( !queue || !cmp, NULL );
	for( n = queue->next; n != NULL; n = n->next ) {
		if( !cmp( n->data, data ) ) {
			return i;
		}
		++i;
	}

	return -1;
}

int32_t sizeQueueLinked( ADT *queue ) {
	ERROR_EXIT( !queue, NULL );

	return PTOI( queue->data );
}

int emptyQueueLinked( ADT *queue ) {
	ERROR_EXIT( !queue, NULL );

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

void reversalQueueLinked( ADT *queue ) {
	Node *p1 = NULL, *p2 = NULL, *p3 = NULL;

	ERROR_EXIT( !queue, NULL );
	queue->prev = queue->next;
	for( p1 = NULL, p2 = queue->next; p2 != NULL; p2 = p3 ) { // 三指針法反轉鏈表.
		p3 = p2->next;
		p2->prev = p3;
		p2->next = p1;
		p1 = p2;
	}
	queue->next = p1;
}

int fullQueueLinked( ADT *queue ) {
	ERROR_EXIT( !queue, NULL );

	return 0;
}

int32_t capacityQueueLinked( ADT *queue ) {
	ERROR_EXIT( !queue, NULL );

	return INT32_MAX;
}

void clearQueueLinked( ADT *queue ) {
	Node *current = NULL, *prev = NULL;

	ERROR_EXIT( !queue, NULL );
	for( current = queue->prev; current != NULL; current = prev ) {
		prev = current->prev;
		free( current );
	}
	queue->data = ITOP( 0 );
}

void delQueueLinked( ADT **queue ) {
	Node *current = NULL, *prev = NULL;

	ERROR_EXIT( !queue, NULL );
	if( !queue ) {
		return;
	}
	for( current = queue[0]->prev; current != NULL; current = prev ) {
		prev = current->prev;
		free( current );
	}
	free( *queue );
	*queue = NULL;
}

queueLinkedTest.c

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

// a>b返回正數, a<b返回負數, 否則返回0.
static int cmp( const void *a, const void *b ) {
	return *(int32_t *) a - *(int32_t *) b;
}

int main( int argc, char *argv[] ) {
	char *tf[] = {"false", "true"};
	int32_t *a = NULL, n = 0;
	int32_t i = 0, k = 0;
	QueueLinked *q = NULL;

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

	a = malloc( sizeof(*a) * n );
	for( i = 0; i < n; ++i ) {
		a[i] = rand() % 322;
		//a[i] = 1;
	}

	printf( "&q = %p, q = %p\n", &q, q );
	q = newQueueLinked();
	printf( "new: &q = %p, q = %p\n", &q, q );

	printf( "peek       = %d\n", emptyQueueLinked( q ) ? INT32_MIN : *(int32_t *) peekQueueLinked( q ) );
	printf( "peekTail = %d\n", emptyQueueLinked( q ) ? INT32_MIN : *(int32_t *) peekTailQueueLinked( q ) );
	printf( "size     = %d\n", sizeQueueLinked( q ) );
	printf( "empty = %s\n", tf[emptyQueueLinked( q )]);
	printf( "\n" );

	for( i = 0; i < n; ++i ) {
		#if 1
		printf( "add: %4d\n", *(int32_t *) addQueueLinked( q, &a[i] ) );
		#else
		printf( "addHead: %4d\n", *(int32_t *) addHeadQueueLinked( q, &a[i] ) );
		#endif
	}
	printf( "\n" );

	printf( "peek       = %d\n", emptyQueueLinked( q ) ? INT32_MIN : *(int32_t *) peekQueueLinked( q ) );
	printf( "peekTail = %d\n", emptyQueueLinked( q ) ? INT32_MIN : *(int32_t *) peekTailQueueLinked( q ) );
	printf( "size     = %d\n", sizeQueueLinked( q ) );
	printf( "empty = %s\n", tf[emptyQueueLinked( q )] );
	printf( "\n" );

	k = a[0];
	//k = rand();
	//printf( "exist &k(%d) = %s\n", k, tf[existQueueLinked( q, &k, cmp )] );
	printf( "\n" );

	k = a[0];
	printf( "add: %d\n", *(int32_t *) addQueueLinked( q, &k ) );
	//k = rand();
	printf( "find &k(%d) = %d\n", k, findQueueLinked( q, &k, cmp ) );
	printf( "\n" );

	k = a[0];
	//k = rand();
	printf( "add: %d\n", *(int32_t *) addQueueLinked( q, &k ) );
	printf( "findTile &k(%d) = %d\n", k, findTailQueueLinked( q, &k, cmp ) );
	printf( "\n" );

	//reversalQueueLinked( q ); // 反轉隊列.

	while( !emptyQueueLinked( q ) ) {
		#if 1
		printf( "poll: %4d\n", *(int32_t *) pollQueueLinked( q ) );
		#else
		printf( "pollTail: %4d\n", *(int32_t *) pollTailQueueLinked( q ) );
		#endif
		printf( "peek       = %d\n", emptyQueueLinked( q ) ? INT32_MIN : *(int32_t *) peekQueueLinked( q ) );
		printf( "peekTail = %d\n", emptyQueueLinked( q ) ? INT32_MIN : *(int32_t *) peekTailQueueLinked( q ) );
		printf( "size     = %d\n", sizeQueueLinked( q ) );
		printf( "\n" );
	}
	printf( "\n" );

	printf( "peek       = %d\n", emptyQueueLinked( q ) ? INT32_MIN : *(int32_t *) peekQueueLinked( q ) );
	printf( "peekTail = %d\n", emptyQueueLinked( q ) ? INT32_MIN : *(int32_t *) peekTailQueueLinked( q ) );
	printf( "size     = %d\n", sizeQueueLinked( q ) );
	printf( "empty = %s\n", tf[emptyQueueLinked( q )] );
	printf( "\n" );

	delQueueLinked( &q );
	printf( "del: &q = %p, q = %p\n", &q, q );

	return EXIT_SUCCESS;
}