回圈雙端佇列-順序存盤-有解無憂

陣列實作回圈雙端佇列

創建3個檔案：doubleEndedQueueArray.h、doubleEndedQueueArray.c、doubleEndedQueueArrayTest.c

doubleEndedQueueArray.h

#ifndef DOUBLE_ENDED_QUEUE_ARRAY_H_
#define DOUBLE_ENDED_QUEUE_ARRAY_H_

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

#define ADT DequeArray

// 功能: 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 DoubleEndedQueueArray DequeArray;

// 功能: 創建一個新的雙端佇列.
// 引數: capacity(雙端佇列的最大容量).
// 回傳: 一個新的雙端佇列.
// 注意: 當 capacity 小于0時,默認為512; 當記憶體分配失敗時,將錯誤退出程式.
extern ADT *newDequeArray( int32_t capacity );

// 功能: 將用戶資料加入到隊尾.
// 引數: queue(雙端佇列物件的指標), data(用戶資料).
// 回傳: 被加入到隊尾的用戶資料.
// 注意: 當 queue 為NULL 或 滿雙端佇列狀態 時, 將錯誤退出程式.
extern void *addDequeArray( ADT *queue, void *data );

// 功能: 將用戶資料加入到隊頭.
// 引數: queue(雙端佇列物件的指標), data(用戶資料).
// 回傳: 被加入到隊頭的用戶資料.
// 注意: 當 queue 為NULL 或 滿雙端佇列狀態 時, 將錯誤退出程式.
extern void *addHeadDequeArray( ADT *queue, void *data );

// 功能: 將隊頭用戶資料移除隊頭.
// 引數: queue(雙端佇列物件的指標).
// 回傳: 被移除的隊頭用戶資料.
// 注意: 當 queue 為NULL 或 空雙端佇列狀態 時, 將錯誤退出程式.
extern void *pollDequeArray( ADT *queue );

// 功能: 將隊尾用戶資料移除隊頭.
// 引數: queue(雙端佇列物件的指標).
// 回傳: 被移除的隊尾用戶資料.
// 注意: 當 queue 為NULL 或 空雙端佇列狀態 時, 將錯誤退出程式.
extern void *pollTailDequeArray( ADT *queue );

// 功能: 偷看隊頭的用戶資料.
// 引數: queue(雙端佇列物件的指標).
// 回傳: 隊頭的用戶資料.
// 注意: 當 queue 為NULL 或 空雙端佇列狀態 時, 將錯誤退出程式.
extern void *peekDequeArray( ADT *queue );

// 功能: 偷看隊尾的用戶資料.
// 引數: queue(雙端佇列物件的指標).
// 回傳: 隊尾的用戶資料.
// 注意: 當 queue 為NULL 或 空雙端佇列狀態 時, 將錯誤退出程式.
extern void *peekTailDequeArray( ADT *queue );


// 功能: 雙端佇列中所有用戶資料中是否包含了data.
// 引數: queue(雙端佇列物件的指標), data(需查找的用戶資料), cmp(用戶自定義比較函式).
// 回傳: 包含了data回傳1, 否則回傳0.
// 注意: 當 queue 為NULL 或 cmp 為NULL 時, 將錯誤退出程式.
extern int existDequeArray( ADT *queue, void *data, CompareFunc *cmp );

// 功能: 從隊頭到隊尾方向查找data.
// 引數: queue(雙端佇列物件的指標), data(需查找的用戶資料), cmp(用戶自定義比較函式).
// 回傳: 雙端佇列中包含了data, 回傳data所在位置, 否則回傳-1.
// 注意: 當 queue 為NULL 或 cmp 為NULL 時, 將錯誤退出程式.
extern int32_t findDequeArray( ADT *queue, void *data, CompareFunc *cmp );

// 功能: 從隊尾到隊頭方向查找data.
// 引數: queue(雙端佇列物件的指標), data(需查找的用戶資料), cmp(用戶自定義比較函式).
// 回傳: 雙端佇列中包含了data, 回傳data所在位置, 否則回傳-1.
// 注意: 當 queue 為NULL 或 cmp 為NULL 時, 將錯誤退出程式.
extern int32_t findTailDequeArray( ADT *queue, void *data, CompareFunc *cmp );

// 功能: 雙端佇列實際已使用大小.
// 引數: queue(雙端佇列物件的指標).
// 回傳: 雙端佇列實際已使用大小.
// 注意: 當 queue 為NULL 時, 將錯誤退出程式.
extern int32_t sizeDequeArray( ADT *queue );

// 功能: 空雙端佇列狀態.
// 引數: queue(雙端佇列物件的指標).
// 回傳: 是空雙端佇列回傳1, 否則回傳0.
// 注意: 當 queue 為NULL 時, 將錯誤退出程式.
extern int emptyDequeArray( ADT *stsack );

// 功能: 滿雙端佇列狀態.
// 引數: queue(雙端佇列物件的指標).
// 回傳: 是滿雙端佇列回傳1, 否則回傳0.
// 注意: 當 queue 為NULL 時, 將錯誤退出程式.
extern int fullDequeArray( ADT *queue );

// 功能: 雙端佇列最大容量.
// 引數: queue(雙端佇列物件的指標).
// 回傳: 雙端佇列最大容量.
// 注意: 當 queue 為NULL 時, 將錯誤退出程式.
extern int32_t capacityDequeArray( ADT *queue );

// 功能: 清空雙端佇列.
// 引數: queue(雙端佇列物件的指標).
// 回傳: 無.
// 注意: 當 queue 為NULL 時, 將錯誤退出程式.
extern void clearDequeArray( ADT *queue );

// 功能: 銷毀雙端佇列.
// 引數: queue(存放雙端佇列物件的指標的指標).
// 回傳: 無.
// 注意: 當 queue 為NULL 時, 將錯誤退出程式.
extern void delDequeArray( ADT **queue );

#undef ADT

#endif

doubleEndedQueueArray.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include "doubleEndedQueueArray.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 );                                                    \
}

#define ADT DequeArray


struct DoubleEndedQueueArray {
	int32_t capacity;
	int32_t size;
	int32_t head;
	void *array[0];
};


ADT *newDequeArray( int32_t capacity ) {
	ADT *queue = NULL;

	capacity = capacity < 0 ? 512 : capacity;
	queue = malloc( sizeof(*queue) + sizeof(queue->array[0]) * capacity );
	ERROR_EXIT( !queue, NULL );
	queue->capacity = capacity;
	queue->size = 0;
	queue->head = 0;

	return queue;
}

void *addDequeArray( DequeArray *queue, void *data ) {
	ERROR_EXIT( !queue || queue->size >= queue->capacity, NULL );
	queue->array[(queue->head + queue->size++) % queue->capacity] = data;

	return data;
}

void *addHeadDequeArray( DequeArray *queue, void *data ) {
	ERROR_EXIT( !queue || queue->size >= queue->capacity, NULL );
	queue->head = (queue->head - 1 + queue->capacity) % queue->capacity;
	queue->array[queue->head] = data;
	++queue->size;

	return data;
}

void *pollDequeArray( DequeArray *queue ) {
	void *data = https://www.cnblogs.com/hujunxiang98/p/NULL;

	ERROR_EXIT( !queue || queue->size < 1, NULL );
	data = queue->array[queue->head];
	queue->head = (queue->head + 1) % queue->capacity;
	--queue->size;

	return data;
}

void *pollTailDequeArray( DequeArray *queue ) {
	void *data = NULL;

	ERROR_EXIT( !queue || queue->size < 1, NULL );
	data = queue->array[(--queue->size + queue->head) % queue->capacity];

	return data;
}

void *peekDequeArray( DequeArray *queue ) {
	ERROR_EXIT( !queue || queue->size < 1, NULL );

	return queue->array[queue->head];
}

void *peekTailDequeArray( DequeArray *queue ) {
	ERROR_EXIT( !queue || queue->size < 1, NULL );

	return queue->array[(queue->head + queue->size - 1) % queue->capacity];
}

int existDequeArray( DequeArray *queue, void *data, CompareFunc *cmp ) {
	ERROR_EXIT( !queue || !cmp, NULL );

	for( int32_t i = 0; i < queue->size; ++i ) {
		if( !cmp( queue->array[(queue->head + i) % queue->capacity], data ) ) {
			return 1;
		}
	}

	return 0;
}

int32_t findDequeArray( DequeArray *queue, void *data, CompareFunc *cmp ) {
	int32_t i = 0, j = 0;

	ERROR_EXIT( !queue || !cmp, NULL );
	for( i = 0; i < queue->size; ++i ) {
		j = (queue->head + i) % queue->capacity;
		if( !cmp( queue->array[j], data ) ) {
			return j;
		}
	}

	return -1;
}

int32_t findTailDequeArray( DequeArray *queue, void *data, CompareFunc *cmp ) {
	int32_t i = 0, j = 0;

	ERROR_EXIT( !queue || !cmp, NULL );
	for( i = queue->size - 1; i >= 0; --i ) {
		j = (queue->head + i) % queue->capacity;
		if( !cmp( queue->array[j], data ) ) {
			return j;
		}
	}

	return -1;
}

int32_t sizeDequeArray( DequeArray *queue ) {
	ERROR_EXIT( !queue, NULL );

	return queue->size;
}

int emptyDequeArray( DequeArray *queue ) {
	ERROR_EXIT( !queue, NULL );

	return queue->size < 1;
}

int fullDequeArray( DequeArray *queue ) {
	ERROR_EXIT( !queue, NULL );

	return queue->size >= queue->capacity;
}

int32_t capacityDequeArray( DequeArray *queue ) {
	ERROR_EXIT( !queue, NULL );

	return queue->capacity;
}

void clearDequeArray( DequeArray *queue ) {
	ERROR_EXIT( !queue, NULL );

	queue->size = 0;
	queue->head = 0;
}

void delDequeArray( DequeArray **queue ) {
	ERROR_EXIT( !queue, NULL );
	free( *queue );
	*queue = NULL;
}

doubleEndedQueueArrayTest.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
#include "doubleEndedQueueArray.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;
	DequeArray *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 = newDequeArray( n );
	printf( "new: &q = %p, q = %p\n", &q, q );

	printf( "peek       = %d\n", emptyDequeArray( q ) ? INT32_MIN : *(int32_t *) peekDequeArray( q ) );
	printf( "peekTail = %d\n", emptyDequeArray( q ) ? INT32_MIN : *(int32_t *) peekTailDequeArray( q ) );
	printf( "size     = %d\n", sizeDequeArray( q ) );
	printf( "empty = %s\n", tf[emptyDequeArray( q )]);
	printf( "full  = %s\n", tf[fullDequeArray( q )] );
	printf( "capacity = %d\n", capacityDequeArray( q ) );
	printf( "\n" );

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

	printf( "peek       = %d\n", emptyDequeArray( q ) ? INT32_MIN : *(int32_t *) peekDequeArray( q ) );
	printf( "peekTail = %d\n", emptyDequeArray( q ) ? INT32_MIN : *(int32_t *) peekTailDequeArray( q ) );
	printf( "size     = %d\n", sizeDequeArray( q ) );
	printf( "empty = %s\n", tf[emptyDequeArray( q )] );
	printf( "full  = %s\n", tf[fullDequeArray( q )] );
	printf( "capacity = %d\n", capacityDequeArray( q ) );
	printf( "\n" );

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

	k = a[0];
	//k = rand();
	printf( "find &k(%d) = %d\n", k, findDequeArray( q, &k, cmp ) );
	printf( "\n" );

	//k = a[0];
	k = rand();
	printf( "findTile &k(%d) = %d\n", k, findTailDequeArray( q, &k, cmp ) );
	printf( "\n" );

	for( i = 0; !emptyDequeArray( q ); ++i ) {
		if( i & 1 ) {
			printf( "poll: %d\n", *(int32_t *) pollDequeArray( q ) );
		} else {
			printf( "pollTail: %d\n", *(int32_t *) pollTailDequeArray( q ) );
		}
		//printf( "peek       = %d\n", emptyDequeArray( q ) ? INT32_MIN : *(int32_t *) peekDequeArray( q ) );
		//printf( "peekTail = %d\n", emptyDequeArray( q ) ? INT32_MIN : *(int32_t *) peekTailDequeArray( q ) );
		//printf( "size     = %d\n", sizeDequeArray( q ) );
		//printf( "empty = %s\n", tf[emptyDequeArray( q )] );
		//printf( "full  = %s\n", tf[fullDequeArray( q )] );
		//printf( "capacity = %d\n", capacityDequeArray( q ) );
		//printf( "\n" );
	}
	printf( "\n" );

	printf( "peek       = %d\n", emptyDequeArray( q ) ? INT32_MIN : *(int32_t *) peekDequeArray( q ) );
	printf( "peekTail = %d\n", emptyDequeArray( q ) ? INT32_MIN : *(int32_t *) peekTailDequeArray( q ) );
	printf( "size     = %d\n", sizeDequeArray( q ) );
	printf( "empty = %s\n", tf[emptyDequeArray( q )] );
	printf( "full  = %s\n", tf[fullDequeArray( q )] );
	printf( "capacity = %d\n", capacityDequeArray( q ) );
	printf( "\n" );

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

	return EXIT_SUCCESS;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/30694.html

標籤：C

上一篇：回圈佇列-順序存盤

下一篇：二叉堆-順序存盤