queue.c

关于图的深度搜索的C语言代码实现

#include <stddef.h>
#include "assert.h"
#include "mem.h"
#include "queue.h"


#define T Queue_T 

#define MINSIZE 7

struct T
{
	int cap;
	int size;
	int front;
	int rear;
	void **array;
};





T Queue_new(int hint)
{
	int i;
	T que;
	assert(hint >= 0);
	if(hint < MINSIZE)
		hint = MINSIZE;
	que = ALLOC(sizeof(*que) + hint * sizeof(que->array[0]));
	que->cap = hint;
	que->size = 0;
	que->front = que->rear = 0;
	que->array = (void **)(que + 1);
	for(i = 0; i < que->cap; i++)
		que->array[i] = NULL;
	return que;
}


int Queue_full(T que)
{
	assert(que);
	return que->size == que->cap;
}


int Queue_empty(T que)
{
	assert(que);
	return que->size == 0;
}


void Queue_push(T que, void *x)
{
	assert(que);
	assert(que->size < que->cap);
	que->array[que->rear] = x;
	que->size++;
	if(que->rear == que->cap - 1)
		que->rear = 0;
	else
		que->rear++;
}


void *Queue_pop(T que)
{
	void *x;
	assert(que);
	assert(que->size > 0);
	que->size--;
	x = que->array[que->front];
	if(que->front == que->cap - 1)
		que->front = 0;
	else
		que->front++;
	return x;
}


void Queue_free(T *que)
{
	assert(que && *que);
	FREE(*que);
}




/*
#include <stdio.h>
void Queue_print(T que)
{
	int i;
	if(que == NULL)
		return ;
	printf("que->cap = %d, que->size = %d\n", que->cap, que->size);
	printf("que->front = %d: array[%d] = %s\n", que->front, 
		que->front, que->array[que->front]);
	printf("que->rear = %d: array[%d] = %s\n", que->rear, 
		que->rear, que->array[que->rear]);
	for(i = que->front; i < que->rear; i++)
		printf("que->array[%d] = %s\n", i, que->array[i]);
}

//test the function
#include <stdio.h>
int main(void)
{	
	int i;
	
	i=1;
	printf("======T Queue_new(int hint)======\n");
	printf( "the (%d) th to test: \n", i++ );
	{
		T que;
		int hint;
		hint = 0;
		que = Queue_new(hint);
		Queue_print(que);
	}
	printf("\n");

	printf( "the (%d) th to test: \n", i++ );
	{
		T que;
		int hint;
		hint = 19;
		que = Queue_new(hint);
		Queue_print(que);
	}
	printf("\n");
	printf("\n\n\n\n");




	i=1;
	printf("======void Queue_push(T que, void *x)======\n");
	printf( "the (%d) th to test: \n", i++ );
	{
		T que;
		int hint;
		char *str1 = "wangjing is good man...";
		char *str2 = "wangxiaoqing";
		hint = 0;
		que = Queue_new(hint);
		Queue_push(que, str1);
		Queue_push(que, str2);
		Queue_print(que);
	}
	printf("\n");
	
	printf( "the (%d) th to test: \n", i++ );
	{
		T que;
		int hint;
		hint = 19;
		que = Queue_new(hint);
		Queue_print(que);
	}
	printf("\n");
	printf("\n\n\n\n");




	i=1;
	printf("======void *Queue_pop(T que)======\n");
	printf( "the (%d) th to test: \n", i++ );
	{
		T que;
		int hint;
		char *str1 = "wangjing is good man...";
		char *str2 = "wangxiaoqing";
		char *s;
		hint = 0;
		que = Queue_new(hint);
		Queue_push(que, str1);
		Queue_push(que, str2);
		Queue_print(que);
		s = Queue_pop(que);
		printf("\ns = %s\n\n", s);
		Queue_print(que);
	}
	printf("\n");
	
	printf( "the (%d) th to test: \n", i++ );
	{
		T que;
		int hint;
		char *str1 = "wangjing is good man...";
		char *str2 = "wangxiaoqing";
		char *str3 = "liuzhulin";
		char *s;
		hint = 0;
		que = Queue_new(hint);
		Queue_push(que, str1);
		Queue_push(que, str2);
		Queue_push(que, str3);
		Queue_print(que);
		s = Queue_pop(que);
		printf("\ns = %s\n\n", s);
		Queue_print(que);
		s = Queue_pop(que);
		printf("\ns = %s\n\n", s);
		Queue_print(que);

	}
	printf("\n");
	printf("\n\n\n\n");
	
	


	i=1;
	printf("======int Queue_empty(T que)======\n");
	printf( "the (%d) th to test: \n", i++ );
	{
		T que;
		int hint, cont;
		char *str1 = "wangjing is good man...";
		char *str2 = "wangxiaoqing";
		hint = 0;
		que = Queue_new(hint);
		Queue_push(que, str1);
		Queue_push(que, str2);
		cont = Queue_empty(que);
		printf("cont = %d\n", cont);
		Queue_print(que);
	}
	printf("\n");
	
	printf( "the (%d) th to test: \n", i++ );
	{
		T que;
		int hint, cont;
		char *str1 = "wangjing is good man...";
		char *str2 = "wangxiaoqing";
		char *str3 = "liuzhulin";
		hint = 0;
		que = Queue_new(hint);
		Queue_push(que, str1);
		Queue_push(que, str2);
		Queue_push(que, str3);
		cont = Queue_empty(que);
		printf("cont = %d\n", cont);
		Queue_print(que);
		
	}
	printf("\n");
	printf("\n\n\n\n");
	
	
	
	
	
	
	i=1;
	printf("======int Queue_full(T que)======\n");
	printf( "the (%d) th to test: \n", i++ );
	{
		T que;
		int hint, cont;
		char *str1 = "wangjing is good man...";
		char *str2 = "wangxiaoqing";
		hint = 0;
		que = Queue_new(hint);
		Queue_push(que, str1);
		Queue_push(que, str2);
		cont = Queue_full(que);
		printf("cont = %d\n", cont);
		Queue_print(que);
	}
	printf("\n");
	
	printf( "the (%d) th to test: \n", i++ );
	{
		T que;
		int hint, cont;
		char *str1 = "wangjing is good man...";
		char *str2 = "wangxiaoqing";
		char *str3 = "liuzhulin";
		hint = 0;
		que = Queue_new(hint);
		Queue_push(que, str1);
		Queue_push(que, str2);
		Queue_push(que, str3);
		cont = Queue_full(que);
		printf("cont = %d\n", cont);
		Queue_print(que);
		
	}
	printf("\n");
	printf("\n\n\n\n");




	i=1;
	printf("======void Queue_free(T *que)======\n");
	printf( "the (%d) th to test: \n", i++ );
	{
		T que;
		int hint;
		char *str1 = "wangjing is good man...";
		char *str2 = "wangxiaoqing";
		hint = 0;
		que = Queue_new(hint);
		Queue_push(que, str1);
		Queue_push(que, str2);
		Queue_free(&que);
		Queue_print(que);
	}
	printf("\n");
	
	printf( "the (%d) th to test: \n", i++ );
	{
		T que;
		int hint;
		char *str1 = "wangjing is good man...";
		char *str2 = "wangxiaoqing";
		char *str3 = "liuzhulin";
		hint = 0;
		que = Queue_new(hint);
		Queue_push(que, str1);
		Queue_push(que, str2);
		Queue_push(que, str3);
		Queue_free(&que);
		Queue_print(que);
			
	}
	printf("\n");
	printf("\n\n\n\n");






	
	return 0;
}
*/







/*
#include <stdio.h>
void Queue_print(T que)
{
	int i;
	if(que == NULL)
		return ;
	printf("que->cap = %d, que->size = %d\n", que->cap, que->size);
	printf("que->front = %d: array[%d] = %d\n", que->front, 
		que->front, que->array[que->front]);
	printf("que->rear = %d: array[%d] = %d\n", que->rear, 
		que->rear, que->array[que->rear]);
	for(i = que->front; i < que->rear; i++)
		printf("que->array[%d] = %d\n", i, *((int *)que->array[i]));
}


//test the function
#include <stdio.h>
int main(void)
{	
	int i;
	
	i=1;
	printf("======T Queue_new(int hint)======\n");
	printf( "the (%d) th to test: \n", i++ );
	{
		T que;
		int hint;
		hint = 0;
		que = Queue_new(hint);
		Queue_print(que);
	}
	printf("\n");
	
	printf( "the (%d) th to test: \n", i++ );
	{
		T que;
		int hint;
		hint = 19;
		que = Queue_new(hint);
		Queue_print(que);
	}
	printf("\n");
	printf("\n\n\n\n");
	
	
	
	
	i=1;
	printf("======void Queue_push(T que, void *x)======\n");
	printf( "the (%d) th to test: \n", i++ );
	{
		T que;
		int hint;
		int a = 3;
		int b = 4;
		int c = 5;
		hint = 0;
		que = Queue_new(hint);
		Queue_push(que, &a);
		Queue_push(que, &b);
		Queue_push(que, &c);
		Queue_print(que);
	}
	printf("\n");
	printf("\n\n\n\n");
	

	return 0;
}
*/