数据结构实验——队列(附程序)

实验三 队列

一、实验目的

1.了解队列的特性。

2.掌握队列的顺序表示和实现。 3.掌握队列的链式表示和实现。

二、实验内容

实验3. 3队列的顺序表示和实现

编写一个程序实现顺序队列的各种基本运算（采用循环队列），并在此基础上设计一个主程序，完成如下功能： (1)初始化队列。 (2)建立顺序队列。 (3)入队。 (4)出队。

(5)判断队列是否为空。 (6)取队头元素。 (7)遍历队列。

实验3.4队列的链式表示和实现

编写一个程序实现链队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能： (1)初始化并建立链队列。 (2)入链队列。 (3)出链队列。 (4)遍历链队列。 #include #include #define MAXQSIZE 100 typedef struct {

int *base; int front; int rear;

}SqQueue;

int InitQueue(SqQueue &Q) {

Q.base=(int*)malloc(MAXQSIZE*sizeof(int)); if(!Q.base)exit(0); Q.front=Q.rear=0; return 0;

}//初始化顺序队列

int QueueLength(SqQueue Q) {

int i;

i=(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; printf(\"队列长度%5d\\n\if(i)printf(\" else

队列非空\");

printf(\" 队列为空\");

return 0;

}//判断队列是否为空

int EnQueue(SqQueue &Q,int e) {

if((Q.rear+1)%MAXQSIZE==Q.front)return 0; Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%MAXQSIZE; return 0;

}//将元素e入队

int DeQueue(SqQueue &Q,int e) {

if(Q.front==Q.rear)return 0; e=Q.base[Q.front]; printf(\"%5d\\n\

Q.front=(Q.front+1)%MAXQSIZE; return 0;

}// 删除元素e并返回其值 int GetHead(SqQueue &Q,int e) {

if(!(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE)return 0; e=Q.base[Q.front];

printf(\"返回队头元素%5d\\n\return 0;

}//返回队头元素e

void PrintQueue(SqQueue &Q) {

int k;

printf(\"顺序队列中的元素：\\n\"); for(k=Q.front;k!=Q.rear;k++) printf(\"%5d\printf(\"\\n\");

}//遍历顺序队列 void main() { int e,i,n; SqQueue Q; InitQueue(Q);

printf(\"1—元素入队；2—元素出队；3—返回队头元素；4—队列空否0—结束运行\\n\"); printf(\"\\n\");printf(\"\\n\");printf(\"\\n\"); printf(\"\\n\");printf(\"\\n\"); printf(\"选择: \"); scanf(\"%d\printf(\"\\n\");printf(\"\\n\"); while(n!=0) {

switch(n)

}

{ }

case 1:printf(\"入队元素:

case 2:printf(\"出队元素: \");DeQueue(Q,e);PrintQueue(Q);printf(\"\\n\");printf(\"\\n\");break; case 3:GetHead(Q,e);printf(\"\\n\");printf(\"\\n\");break; case 4:QueueLength(Q);printf(\"\\n\");printf(\"\\n\");break;

\");scanf(\"%d\

printf(\"选择: \"); scanf(\"%d\

printf(\"\\n\");printf(\"\\n\"); printf(\"结束运行。再见！\\n\"); } 链式队列 #include #include typedef struct QNode {

int data;

struct QNode *next;

}QNode,*QueuePtr; typedef struct {

QueuePtr front;//队头指针 QueuePtr rear;//队尾指针

}LinkQueue;

int InitQueue(LinkQueue &Q) {

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)exit(0); Q.front->next=NULL; return 0;

}//初始化链式队列

int EnQueue(LinkQueue &Q,int e) {

QueuePtr p;

p=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(0);

p->data=e;p->next=NULL; Q.rear->next=p; Q.rear=p; return 0;

}//在队尾插入元素e

int DeQueue(LinkQueue &Q,int e) {

QueuePtr p;

if(Q.front==Q.rear)return 0;

p=Q.front->next; e=p->data;

Q.front->next=p->next; if(Q.rear==p)Q.rear=Q.front; free(p); return 0;

}//删除队头元素e

int PrintQueue(LinkQueue &Q) {

QueuePtr p;

printf(\"链式队列中的元素 if(Q.front->next!=NULL) { } else

printf(\"队列为空\\n\"); printf(\"\\n\"); return 0; p=Q.front->next; if(Q.front->next!=NULL)

do {

printf(\"%5d\p=p->next;

\");

}while(p!=NULL);

}//遍历链式队列 void main() {

LinkQueue Q; int e,m;

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

printf(\"1——插入元素；2——删除元素；0——结束运行\\n\"); printf(\"\\n\");printf(\"\\n\");printf(\"\\n\"); InitQueue(Q); printf(\"\\n\");printf(\"\\n\"); printf(\"选择: \"); scanf(\"%d\printf(\"\\n\");printf(\"\\n\"); while(m!=0)

{

switch(m) { }

case 1:printf(\"插入元素：

case 2:DeQueue(Q,e);PrintQueue(Q);printf(\"\\n\");printf(\"\\n\");break;

\");scanf(\"%d\

printf(\"选择: \");

}

}

scanf(\"%d\

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

printf(\"结束运行。再见！\\n\");