空白实验报告

数 据 结 构 实 验 报 告

实验项目 链循环队列的基本运算

专 业 信息管理与信息系统 班 级 2009212104 学 号 09212264 姓 名 郭洋

2010年 12 月 30 日

1. 问题描述

通过对链循环队列进行一些基本操作，加深对队列只能从队头取从队尾入和先进先出这些特性的理解。

对链循环队列进行初始化、入队列、出队列、判断队列空和获取队头元素五种基本操作。

要求用户选择需要对循环队列进行的操作， 0:退出 1：入队列 2：出队列 3:判断队列是否为空 4:取队列头元素。

2. 算法描述

（1）队列初始化：Init_Queue(q) 初始条件：队q不存在。

操作结果：构造了一个空队。 （2）入队操作：In_Queue(q,x) 初始条件：队q存在。

操作结果：对已存在的队列q，在队尾插入一个元素x，队发生变化。

（3）出队操作：Out_Queue(q,x) 初始条件：队q存在且非空。

操作结果：删除队头元素，并返回其值，队发生变化。 （4）读队首元素：Read_Queue(q,x) 初始条件：队q存在且非空。

操作结果：读队首元素，并返回其值，队不变。 （5）判队空操作：Empty_Queue(q) 初始条件：队q存在。

操作结果：若q为空队则返回为1，否则返回为0。

3. 代码

typedef struct queuenode {

DataType data;

struct queuenode * next; }QueueNode;

typedef struct {

QueueNode * front; QueueNode * rear; }LinkQueue;

int InitQueue(LinkQueue *Q) {

QueueNode *w;

w=(QueueNode*)malloc(sizeof(QueueNode)); w->data=NULL;

Q->front=Q->rear=w; return 1; }

int QueueEmpty(LinkQueue * Q) {

if(Q->front->data==NULL&&Q->rear->data==NULL) return 1; else return 0; }

void EnQueue(LinkQueue *Q,DataType x) {

QueueNode *w;

w=(QueueNode*)malloc(sizeof(QueueNode)); w->data=x;

if(QueueEmpty(Q)) {

Q->front=w;

Q->rear=w; w->next=w; }

else {

w->next=Q->rear->next; Q->rear->next=w; Q->rear=w; } }

void DeQueue(LinkQueue *Q) {

QueueNode *w;

w=(QueueNode*)malloc(sizeof(QueueNode)); if(QueueEmpty(Q))

cout<<\队列为空\;

else {

w=Q->front;

w->next=Q->front->next; cout<data<front=w->next; free(w); } }

void QueueFront(LinkQueue *Q) {

if(QueueEmpty(Q))

cout<<\队列为空\;

else cout<front->data<

int main() {

LinkQueue *Q; QueueNode *w; char x;