データ構造学習ノート---キュー(キュー)

3304 ワード

データ構造 struct null

1.引用
本文は主にチェーンの行列について説明します.スタックと同様に、キューも動作制限の線形表であり、列の最後に要素を挿入し、対頭に要素を削除することだけが許される.キュー構造に対して、
を選択します
要素を挿入しやすいようにして、列の最後の指針を設けました.このように要素を挿入する操作はキューの長さに無関係です.
2.チェーン列

#include "ds.h"

typedef 	int 	QElemType;

typedef struct QNode{
	QElemType 		data;
	struct QNode 	*next;
}*QueuePtr;

struct LinkQueue{
	QueuePtr 	front, rear;
};

void InitQueue(LinkQueue &Q);
void DestroyQueue(LinkQueue &Q);
void ClearQueue(LinkQueue &Q);
Status QueueEmpty(LinkQueue Q);
int QueueLength(LinkQueue Q);
Status GetHead(LinkQueue Q, QElemType &e);
void EnQueue(LinkQueue &Q, QElemType e);
Status DeQueue(LinkQueue &Q, QElemType &e);
void QueueTraverse(LinkQueue Q, void(*vi)(QElemType));

//          
void InitQueue(LinkQueue &Q)
{
	Q.front = (QueuePtr)malloc(sizeof(QNode));
	if (!Q.front) exit(OVERFLOW);
	
	Q.front->next = NULL;
	Q.rear = Q.front;
		
}
void DestroyQueue(LinkQueue &Q)
{
	QueuePtr q, p = Q.front;
	
	while (p)
	{
		q = p->next;
		free(p);
		p = q;
	}
	
	Q.front = Q.rear = NULL;
}
void ClearQueue(LinkQueue &Q)
{
	QueuePtr q, p = Q.front->next;
	
	while (p)
	{
		q = p->next;
		free(p);
		p = q;
	}
	Q.front->next = NULL;
	Q.rear = Q.front;
}
Status QueueEmpty(LinkQueue Q)
{
	if (Q.front == Q.rear)
		return TRUE;
	else
		return FALSE;
}
int QueueLength(LinkQueue Q)
{
	int i = 0;
	QueuePtr p = Q.front->next;
	
	while (p)
	{
		i++;
		p = p->next;
	}
	
	return i;
}
Status GetHead(LinkQueue Q, QElemType &e)
{
	if (Q.front->next)
	{
		memcpy(&e, &(Q.front->next->data), sizeof(QElemType));
		return OK;
	}
	else
	{
		return FALSE;
	}
}
void EnQueue(LinkQueue &Q, QElemType e)
{
	QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
	if (!p) exit(OVERFLOW);
	
	p->next = NULL;
	memcpy(&(p->data), &e, sizeof(QElemType));
	Q.rear->next = p;
	Q.rear = p;
}
Status DeQueue(LinkQueue &Q, QElemType &e)
{
	QueuePtr p = Q.front, q;
	if (Q.front == Q.rear)
		return FALSE;
	
	q = p->next;
	memcpy(&e, &(q->data), sizeof(QElemType));
	p->next = q->next;
	if (Q.rear == q)
		Q.rear = Q.front;
	free(q);
	
	return OK;
}
void QueueTraverse(LinkQueue Q, void(*vi)(QElemType))
{
	QueuePtr p = Q.front->next;
	
	while (p)
	{
		vi(p->data);
		p = p->next;
	}
	printf("
");
}

void print(QElemType e)
{
	printf("%d ", e);
}


int main()
 {
   int i;
   QElemType d;
   LinkQueue q;
   InitQueue(q);
   printf("           !
");
   printf("     ？%d(1:  0: )  ",QueueEmpty(q));
   printf("      %d
",QueueLength(q));
   EnQueue(q,-5);
   EnQueue(q,5);
   EnQueue(q,10);
   printf("  3   (-5,5,10) ,      %d
",QueueLength(q));
   printf("     ？%d(1:  0: )  ",QueueEmpty(q));
   printf("        ：");
   QueueTraverse(q,print);
   i=GetHead(q,d);
   if(i==OK)
     printf("     ：%d
",d);
   DeQueue(q,d);
   printf("       %d
",d);
   i=GetHead(q,d);
   if(i==OK)
     printf("       ：%d
",d);
   ClearQueue(q);
   printf("     ,q.front=%u q.rear=%u q.front->next=%u
",q.front,q.rear,q.front->next);
   DestroyQueue(q);
   printf("     ,q.front=%u q.rear=%u
",q.front, q.rear);
 }

可変長構造体