二叉堆-順序存盤-有解無憂

陣列實作二叉堆

創建3個檔案：heapArray.h、heapArray.c、heapArrayTest.c

heapArray.h

#ifndef HEAP_ARRAY_H_
#define HEAP_ARRAY_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 HeapArray

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

// 功能: 創建一個新的堆.
// 引數: capacity(堆的最大容量), cmp(資料比較函式的指標).
// 回傳: 一個新的堆.
// 注意: 當 capacity 小于0時,默認為512; 當記憶體分配失敗時,將錯誤退出程式.
extern ADT *newHeapArray( int32_t capacity, CompareFunc *cmp );

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

// 功能: 將用戶資料加入到堆頂.
// 引數: heap(堆物件的指標), data(用戶資料).
// 回傳: 被加入到堆頂的用戶資料.
// 注意: 當 heap 為NULL 或 滿堆狀態 時, 將錯誤退出程式.
// 被棄用的函式.
extern DEPRECATED void *addHeadHeapArray( ADT *heap, void *data );

// 功能: 移除堆頂用戶資料.
// 引數: heap(堆物件的指標).
// 回傳: 被移除的堆頂的用戶資料.
// 注意: 當 heap 為NULL 或 空堆狀態 時, 將錯誤退出程式.
extern void *pollHeapArray( ADT *heap );

// 功能: 移除堆呼叫戶資料.
// 引數: heap(堆物件的指標).
// 回傳: 被移除的堆底的用戶資料.
// 注意: 當 heap 為NULL 或 空堆狀態 時, 將錯誤退出程式.
extern void *pollTailHeapArray( ADT *heap );

// 功能: 偷看堆頂的用戶資料.
// 引數: heap(堆物件的指標).
// 回傳: 堆頂的用戶資料.
// 注意: 當 heap 為NULL 或 空堆狀態 時, 將錯誤退出程式.
extern void *peekHeapArray( ADT *heap );

// 功能: 偷看堆底的用戶資料.
// 引數: heap(堆物件的指標).
// 回傳: 堆底的用戶資料.
// 注意: 當 heap 為NULL 或 空堆狀態 時, 將錯誤退出程式.
extern void *peekTailHeapArray( ADT *heap );


// 功能: 堆中所有用戶資料中是否包含了data.
// 引數: heap(堆物件的指標), data(需查找的用戶資料).
// 回傳: 包含了data回傳1, 否則回傳0.
// 注意: 當 heap 為NULL 時, 將錯誤退出程式.
extern int existHeapArray( ADT *heap, void *data );

// 功能: 從堆頂至堆底方向查找data.
// 引數: heap(堆物件的指標), data(需查找的用戶資料).
// 回傳: 堆中包含了data, 回傳data所在位置, 否則回傳-1.
// 注意: 當 heap 為NULL 時, 將錯誤退出程式.
extern int32_t findHeapArray( ADT *heap, void *data );

// 功能: 從堆底至堆頂方向查找data.
// 引數: heap(堆物件的指標), data(需查找的用戶資料).
// 回傳: 堆中包含了data, 回傳data所在位置, 否則回傳-1.
// 注意: 當 heap 為NULL 時, 將錯誤退出程式.
extern int32_t findTailHeapArray( ADT *heap, void *data );

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

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

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

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

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

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

#undef ADT

#endif

heapArray.c

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

// 功能: 陣列的兩個元素進行互換.
// 引數: a(陣列首地址), i(陣列下標), j(陣列下標).
// 回傳: 無.
// 注意: 沒有副作用的宏, C99標準: #define f ({...}).
#define SWAP( a, i, j ) ({            \
	int32_t i1i1i = (i), j1j1j = (j); \
	void *t1t1t = *((a) + i1i1i);     \
	*((a) + i1i1i) = *((a) + j1j1j);  \
	*((a) + j1j1j) = t1t1t;           \
})

#define ADT HeapArray


struct HeapArray {
	int32_t capacity;
	int32_t size;
	CompareFunc *cmp;
	void *array[0];
};


ADT *newHeapArray( int32_t capacity, CompareFunc *cmp ) {
	ADT *heap = NULL;

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

	return heap;
}

void *addHeapArray( HeapArray *heap, void *data ) {
	int32_t i = 0;

	ERROR_EXIT( !heap || heap->size >= heap->capacity, NULL );
	i = heap->size++;
	heap->array[i] = data;

	for( int32_t p = (i - 1) / 2; heap->cmp( heap->array[i], heap->array[p] ) < 0; p = (i - 1) / 2 ) {
		// i: index, p: parent.
		SWAP( heap->array, p, i );
		i = p;
	}

	return data;
}

void *addHeadHeapArray( HeapArray *heap, void *data ) {
	return NULL;
}

void *pollHeapArray( HeapArray *heap ) {
	int32_t i = 0;

	ERROR_EXIT( !heap || heap->size < 1, NULL );
	SWAP( heap->array, 0, heap->size - 1 ); // 堆頂與堆底進行對換.
	--heap->size;
	for( int32_t l = i * 2 + 1; l < heap->size; l = i * 2 + 1 ) { // 從堆頂至堆底方向進行調整.
		// l: left child, r: right child, m: maximum or minimum.
		int32_t r = l + 1, m = l;
		if( r < heap->size && heap->cmp( heap->array[r], heap->array[l] ) < 0 ) {
			m = r;
		}
		if( heap->cmp( heap->array[i], heap->array[m] ) <= 0 ) {
			break;
		}
		SWAP( heap->array, m, i );
		i = m;
	}

	return heap->array[heap->size];
}

void *pollTailHeapArray( HeapArray *heap ) {
	ERROR_EXIT( !heap || heap->size < 1, NULL );

	return heap->array[--heap->size];
}

void *peekHeapArray( HeapArray *heap ) {
	ERROR_EXIT( !heap || heap->size < 1, NULL );

	return heap->array[0];
}

void *peekTailHeapArray( HeapArray *heap ) {
	ERROR_EXIT( !heap || heap->size < 1, NULL );

	return heap->array[heap->size - 1];
}

int existHeapArray( HeapArray *heap, void *data ) {
	ERROR_EXIT( !heap, NULL );

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

	return 0;
}

int32_t findHeapArray( HeapArray *heap, void *data ) {
	ERROR_EXIT( !heap, NULL );
	for( int32_t i = 0; i < heap->size; ++i ) {
		if( !heap->cmp( heap->array[i], data ) ) {
			return i;
		}
	}

	return -1;
}

int32_t findTailHeapArray( HeapArray *heap, void *data ) {
	ERROR_EXIT( !heap, NULL );
	for( int32_t i = heap->size - 1; i >= 0; --i ) {
		if( !heap->cmp( heap->array[i], data ) ) {
			return i;
		}
	}

	return -1;
}

int32_t sizeHeapArray( HeapArray *heap ) {
	ERROR_EXIT( !heap, NULL );

	return heap->size;
}

int emptyHeapArray( HeapArray *heap ) {
	ERROR_EXIT( !heap, NULL );

	return heap->size < 1;
}

int fullHeapArray( HeapArray *heap ) {
	ERROR_EXIT( !heap, NULL );

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

int32_t capacityHeapArray( HeapArray *heap ) {
	ERROR_EXIT( !heap, NULL );

	return heap->capacity;
}

void clearHeapArray( HeapArray *heap ) {
	ERROR_EXIT( !heap, NULL );

	heap->size = 0;
}

void delHeapArray( HeapArray **heap ) {
	ERROR_EXIT( !heap, NULL );
	free( *heap );
	*heap = NULL;
}

heapArrayTest.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
#include "heapArray.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;
	HeapArray *h = 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;
	}
	a[0] = 52; a[1] = 134; a[2] = 93; a[3] = 4; a[4] = 195;

	printf( "&h = %p, h = %p\n", &h, h );
	h = newHeapArray( n, cmp );
	printf( "new: &h = %p, h = %p\n", &h, h );

	printf( "peek       = %d\n", emptyHeapArray( h ) ? INT32_MIN : *(int32_t *) peekHeapArray( h ) );
	printf( "peekTail = %d\n", emptyHeapArray( h ) ? INT32_MIN : *(int32_t *) peekTailHeapArray( h ) );
	printf( "size     = %d\n", sizeHeapArray( h ) );
	printf( "empty = %s\n", tf[emptyHeapArray( h )]);
	printf( "full  = %s\n", tf[fullHeapArray( h )] );
	printf( "capacity = %d\n", capacityHeapArray( h ) );
	printf( "\n" );

	for( i = 0; i < n; ++i ) {
		printf( "add: %d\n", *(int32_t *) addHeapArray( h, &a[i] ) );
	}
	printf( "\n" );

	printf( "peek       = %d\n", emptyHeapArray( h ) ? INT32_MIN : *(int32_t *) peekHeapArray( h ) );
	printf( "peekTail = %d\n", emptyHeapArray( h ) ? INT32_MIN : *(int32_t *) peekTailHeapArray( h ) );
	printf( "size     = %d\n", sizeHeapArray( h ) );
	printf( "empty = %s\n", tf[emptyHeapArray( h )] );
	printf( "full  = %s\n", tf[fullHeapArray( h )] );
	printf( "capacity = %d\n", capacityHeapArray( h ) );
	printf( "\n" );

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

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

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

	for( i = 0; !emptyHeapArray( h ); ++i ) {
		if( i & 1 ) {
			printf( "poll: %d\n", *(int32_t *) pollHeapArray( h ) );
		} else {
			printf( "pollTail %d\n", *(int32_t *) pollTailHeapArray( h ) );
		}
		//printf( "peek       = %d\n", emptyHeapArray( h ) ? INT32_MIN : *(int32_t *) peekHeapArray( h ) );
		//printf( "peekTail = %d\n", emptyHeapArray( h ) ? INT32_MIN : *(int32_t *) peekTailHeapArray( h ) );
		//printf( "size     = %d\n", sizeHeapArray( h ) );
		//printf( "empty = %s\n", tf[emptyHeapArray( h )] );
		//printf( "full  = %s\n", tf[fullHeapArray( h )] );
		//printf( "capacity = %d\n", capacityHeapArray( h ) );
		//printf( "\n" );
	}
	printf( "\n" );

	printf( "peek       = %d\n", emptyHeapArray( h ) ? INT32_MIN : *(int32_t *) peekHeapArray( h ) );
	printf( "peekTail = %d\n", emptyHeapArray( h ) ? INT32_MIN : *(int32_t *) peekTailHeapArray( h ) );
	printf( "size     = %d\n", sizeHeapArray( h ) );
	printf( "empty = %s\n", tf[emptyHeapArray( h )] );
	printf( "full  = %s\n", tf[fullHeapArray( h )] );
	printf( "capacity = %d\n", capacityHeapArray( h ) );
	printf( "\n" );

	delHeapArray( &h );
	printf( "del: &h = %p, h = %p\n", &h, h );

	return EXIT_SUCCESS;
}

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

標籤：C

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

下一篇：復試臨時練習