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

实验三 队列

一、实验目的

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(\"入队元素\");scanf(\"%d\

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;

}

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)

{

p=Q.front->next;

if(Q.front->next!=NULL)

do

{

\");

printf(\"%5d\

p=p->next;

}while(p!=NULL);

}

else

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

printf(\"\\n\");

return 0;

}//遍历链式队列

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(\"插入元素：

\");scanf(\"%d\

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

}

printf(\"选择: \");

scanf(\"%d\

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

}

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

}