queue5.c

自己做的常用库和实现的数据结构。public domain.

/* Demo of loop queue, using dynamic array.
 *
 * Written by Cyril Hu ([e-mail]), public domain.
 */
#include "my.h"
#define QUEUE_INIT_SIZE 10
#define QUEUE_INCREMENT 20
#define MAX 40
typedef int ElemType;
typedef size_t OrderTag;
typedef struct {
	ElemType e;
	OrderTag tag;
} QNode, *QNodePtr;
typedef struct {
	QNodePtr head;
	size_t queuesize;
} Queue, *QueuePtr;
void InitQueue(QueuePtr p)
{ 
	QNodePtr q, t;
	p->head = (QNodePtr)mem('m', (p->queuesize = QUEUE_INIT_SIZE) * sizeof(QNode));
	printf("%p\n", p->head);
	q = p->head, t = p->head + p->queuesize - 1;
	for(; q <= t; q->tag = 0, q++);
}
void EnQueue(QueuePtr p, ElemType data)
{
	static size_t cnt = 0;
	QNodePtr q = p->head, t = p->head + p->queuesize - 1;
	for(; q <= t; q++)
		if(q->tag == 0) {
			q->e = data;
			q->tag = ++cnt;
			return;
		}
	p->head = (QNodePtr)mem('r', p->head, (p->queuesize + QUEUE_INCREMENT) * sizeof(QNode));
	printf("%p\n", p->head);
	q = p->head + p->queuesize;
	p->queuesize += QUEUE_INCREMENT;
	t = p->head + p->queuesize - 1;
	q->e = data;
	q->tag = ++cnt;
	for(q++; q <= t; q->tag = 0, q++);
}
void DeQueue(QueuePtr p, ElemType *data)
{
	QNodePtr q = p->head, t = p->head + p->queuesize - 1, r = q;
	static bool queueemptyflag = false;
	if(queueemptyflag)
		return;
	for(queueemptyflag = true; q < t; q++)
		if(q->tag != 0 && r->tag > (q+1)->tag) {
			r = q+1;
			queueemptyflag = false;
		}
	if(queueemptyflag && q->tag == 0)
		queueemptyflag = true;
	if(! queueemptyflag) {
		*data = r->e;
		r->tag = 0;
	}
}
void DestroyQueue(QueuePtr p)
{
	free(p->head);
}
int main(void)
{
	Queue b, *p = &b;
	int i,a[MAX];
	InitQueue(p);
	for(i=0; i<MAX; i++)
		EnQueue(p, i);
	for(i=0; i<MAX*2; i++)
		DeQueue(p, &a[i]);
	for(i=0; i<MAX; i++)
		printf("%d ", a[i]);
	DestroyQueue(p);
	return 0;
}