编辑代码

/*===============算法4.17~算法4.22（102~103页）=======
                        链队列
- 算法4.17（102页）建立空链队列
- 算法4.18（102页）链队列置空
- 算法4.19（102页）链队列判空队
- 算法4.20（102页）链队列入队
- 算法4.21（102页）链队列出队
- 算法4.22（103页）取链队列的队头元素
======================================================*/
#include <stdlib.h>
#include <stdio.h>

#define datatype int
#define TRUE 1
#define FALSE 0

/*===============(1)链队列的结点的数据类型描述(101页）=========
======================================================*/
typedef  struct  node {
	datatype  data;
	struct  node  *next;
}   QueueNode;

/*===============（2）链中头尾指针的数据类型描述(101页）=========
======================================================*/
typedef struct {
	QueueNode *front, *rear;
} LinkQueue;

/*===============算法4.17（102页）=======
建立空链队列
======================================================*/
void  InitQueue(LinkQueue *&q) {
	q = (LinkQueue *)malloc(sizeof(LinkQueue)); //产生头、尾指针结构体
	q->front = q->rear = (QueueNode *)malloc(sizeof(QueueNode)); //产生头结点
	q->front->next = NULL; //头结点指针域置空
}

/*===============算法4.18（102页）=======
链队列置空
======================================================*/
void SetNull (LinkQueue *q) { //置队列sq为空队
	q->rear = q->front;
	q->front->next = NULL;
}

/*===============算法4.19（102页）=======
链队列判空队
======================================================*/
int Empty (LinkQueue *q) {
	if (q->front == q->rear)
		return (1);
	else
		return (0);
}


/*===============算法4.20（102页）=======
链队列入队
======================================================*/
void EnQueue (LinkQueue *q, datatype x)

//将新元素x加入链队列*q
{
	q->rear->next = (QueueNode *)malloc(sizeof(QueueNode));
	// 新结点插入队尾
	q->rear = q->rear->next; //尾指针指向新结点
	q->rear->data = x;     //给新结点赋值
	q->rear->next = NULL; //队尾结点的指针域置空
}

/*===============算法4.21（102页）=======
链队列出队
======================================================*/
int DeQueue(LinkQueue *q, datatype &x)

//通过参数x带回该元素值，出队成功返回1，不成功返回0
{
	QueueNode *s;
	if (Empty(q)) {
		printf("队列下溢.\n");
		return (0);
	} else {
		s = q->front->next;     //s指向被删除的队头结点 　　
		if (s->next == NULL) {
			//当前链队列的长度等于1，出队后为空队 　　
			q->front->next = NULL;
			q->rear = q->front ; //置为空队
		} else
			q->front->next = s->next; //队列的长度大于1，修改头结点的指针域　　

		x = s->data;
		free(s); //释放被删除的结点空间
		return (1);
	}
}

/*===============算法4.22（103页）=======
取链队列的队头元素
======================================================*/
int GetFront(LinkQueue *q, datatype &x)

//通过参数x带回队头元素值，取队头元素成功，返回1，不成功，返回0
{
	if (Empty (q)) {
		printf("队列下溢");
		return (0);
	} else {
		x = q->front->next->data;
		return (1);
	}
}

// 销毁链队列  (考虑到程序中间某个时刻后可能永远不再使用该队列)
void Destory(LinkQueue *q) {
	QueueNode  *s;
	datatype x;
	while ( ! Empty(q) ) {
		DeQueue(q, x);
	}
	free(q->front);
	q->front = NULL;
	q->rear = NULL;
}


int main() {
	LinkQueue *lq;
	InitQueue(lq);

	datatype y;

	EnQueue(lq, 1);
	EnQueue(lq, 2);
	EnQueue(lq, 3);
	GetFront(lq, y);
	printf("队列的队头元素值为%d\n", y);

	int flag;
	flag = DeQueue(lq, y);
	printf("出队列: flag=%d，值为%d\n", flag, y);
	flag = DeQueue(lq, y);
	printf("出队列: flag=%d，值为%d\n", flag, y);
	flag = DeQueue(lq, y);
	printf("出队列: flag=%d，值为%d\n", flag, y);
	flag = DeQueue(lq, y);
	printf("出队列: flag=%d，值为%d\n", flag, y);

	Destory(lq);
	return 0;

}