数据结构 队列实验报告_数据结构报告实验报告

数据结构 队列实验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构报告实验报告”。

队列实验报告

小组成员：xxxxxxxx日期：xxxxxxxx

一、需求分析（xxx）

1.链队列

1）在本演示程序中，首先要链队列添加一个头结点，并判断队列是否为空，它只允许在表的一端进行插入，而在另一端删除元素，允许插入的一段叫队尾，允许删除的一端则为对头，接着访问队列中所有元素，并输出，输出是每个元素之间用空格来完成。最后销毁队列，释放空间。2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“欢迎来到链队列”“元素入队”“元素出队”“销毁队列”“清空队列”之后。由用户在键盘上输入演示程序中规定的运算命令，相应的运算数据和显示结果显示在其后。3）程序执行的命令包括： 欢迎来到链队列 1输出队列长度 2元素入队 3元素出队 4销毁队列 5清空队列 6对头元素 7退出链队列 4）测试数据 入队 1 2 3 4 5 分别执行“元素入队”“元素出队”“销毁队列”“清空队列”等操作。2.顺序队列

1）在本演示程序中，首先要顺序队列添加一个头结点，并判断队列是否为空，它只允许在表的一端进行插入，而在另一端删除元素，允许插入的一段叫队尾，允许删除的一端则为对头，接着访问队列中所有元素，并输出，输出是每个元素之间用空格来完成。2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“欢迎来到链队列”“元素入队”“元素出队”“取得头结点”“输出显示”之后。由用户在键盘上输入演示程序中规定的运算命令，相应的运算数据和显示结果显示在其后。3）程序执行的命令包括： 欢迎来到顺序队列 1入队 2出队

3判断是否为空 4取得头结点 5输出显示 6退出顺序队列 4）测试数据 入队 1 2 3 4 5 分别执行“元素入队”“元素出队”等操作。3循环队列

1）在本演示程序中，首先要顺序队列添加一个头结点，并判断队列是否为空，初始化建空队列时，令front=rear=0,每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。接着访问队列中所有元素，并输出，输出是每个元素之间用空格来完成。2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“欢迎来到链队列”“元素入队”“元素出队”“取得头结点”“输出显示”之后。由用户在键盘上输入演示程序中规定的运算命令，相应的运算数据和显示结果显示在其后。3）程序执行的命令包括： 欢迎来到循环队列 1入队 2出队

3判断是否为空 4取得头结点 5输出显示 6退出顺序队列 4）测试数据 入队 1 2 3 4 5 分别执行“元素入队”“元素出队”等操作。

二．概要设计(xxxx)

⒈ 为实现上述算法，需要顺序表的抽象数据类型，抽象数据类型定义如下：

ADT Queue { 数据对象：D={ ai|ai∈ElemSet, i=1,2,3...,n, n>=0 } 数据关系: R={ |ai-1,ai∈D,i=2,...,n } 基本操作： InitQueue(&Q)操作结果：构造一个空队列。DestroyQueue(&Q)初始条件：队列Q已存在。

操作结果：队列Q已被销毁。ClearQueue(&Q)初始条件：队列Q已存在。

操作结果：将Q清为空队列。QueueEmpty(Q)初始条件：队列Q已存在。

操作结果：若Q为空队列，则返回TRUE,否则FALSE。QueueLength(Q)初始条件：队列Q已存在。

操作结果：返回Q元素的个数，即队列的长度。GetHead(Q,&e)初始条件:Q为非空队列。

操作结果：用e返回Q的队头元素。EnQueue(&Q,e)初始条件：队列Q已存在。

操作结果：插入e返回Q的新的队尾元素。DeQueue(&Q，&e)初始条件：Q为非空队列。

操作结果：删除Q的队头元素，并用e返回其值。}ADT Queue

2.单链队列

typedefstructQNode { QElemType;structQNode *next;//指针域 }QNode,*QueuePtr;Typedefstruct{ QueuePtr front;QueuePtr rear;}LinkQueue;Status InitQueue(LinkQueue&Q)//构造一个空队列。

Status DestroyQueue(LinkQueue&Q)//销毁队列Q，Q不存在。

Status ClearQueue(LinkQueue&Q)//将Q清为空队列。

Status QueueEmpty(LinkQueueQ)//若Q为空队列，则返回TRUE,否则FALSE。intQueueLength(LinkQueueQ)//返回Q元素的个数，即队列的长度。

Status GetHead(LinkQueueQ,QElemType&e)//若队列不为空，则用e返回Q的队头元素，并返回OK;否则返回ERROR。

Status EnQueue(LinkQueue&Q,QElemType e)//插入e返回Q的新的队尾元素。

Status DeQueue(LinkQueue&Q,QElemType&e)//若队列不空，则删除Q的队头元素，并用e返回其值，并返回OK;否则返回ERROR。

三．详细设计（xxx）

1.顺序队列的实现和运算

1）元素的类型 typedefstruct { Datatypedata[MAXSIZE];intfront,rear;}Squeue;2）空的队列的构造

void InitSqueue(Squeue *p)/*初始化队列*/ { p->front=0;p->rear=0;} 3）元素的入队

int Ensqueue1(Squeue1 *q, Datatype e)/*入队*/ { if((q->rear+1)% MAXSIZE == q->front){ printf(“n队列已满n”);return 0;} 4）元素的出队

int DeSqueue1(Squeue1 *q,Datatype *e)/*出队*/ { if(q->front==q->rear){ printf(“队列已空,无法出队!”);return 0;} *e=q->data[q->front];q->front=(q->front+1)%MAXSIZE;return 1;} 5）判断队列是否为空

int QueueEmpty1(Squeue1 q)// 判断是否为空 { if(q.front==q.rear)return 1;else return 0;} 6）队头元素的取值的算法

int Gethead1(Squeue1 *q,Datatype *e)// 取对头元素 { if(q->front==q->rear){ printf(“队列已空，无法出队!”);return 0;} else *e=q->data[q->front];return 1;} 7）遍历顺序队列的算法

void display1(Squeue1 q)//遍历顺序对列 { printf(“此队列数据为:n”);if(q.front==q.rear)printf(“此队列为空!”);else { while(q.front

void InitQueue2(LinkQueue *q){ // 构造一个空队列Q q->front=q->rear=malloc(sizeof(QNode));if(!q->front)exit(1);q->front->next=NULL;} 2）元素的入队算法

void EnQueue2(LinkQueue *q, QElemType e)//将元素e进队 { QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));//创建新节点

if(!p)//如果内存分配成功

exit(1);

p->data=e;//初始化新节点数据为e p->next=NULL;

q->rear->next=p;

q->rear=p;} 3）元素的出队的算法

int DeQueue2(LinkQueue *q,QElemType e)//队头结点出队,将出队的元素存入e { QueuePtr p;if(q->front==q->rear)//队列为空

return 0;p=q->front->next;//初始化temp为要出队的结点指针

if(q->front->next==q->rear)//要出队的结点为最后一个结点

q->rear=q->front;e=p->data;//要出队的数据元素为e q->front->next=p->next;//使下一个结点变为对头

free(p);//删除要出队的结点

return e;} 4）队列的长度算法

void QueueLength2(LinkQueue *q)//返回队列长度 { QueuePtr p;int i=0;p=q->front->next;while(p){

++i;

p=p->next;} printf(“链队列长度为:%dn”,i);} 5）队列的销毁

void DestroyQueue2(LinkQueue *q){ while(q->front){

q->rear=q->front->next;

free(q->front);

q->front=q->rear;

if(!q->rear)

free(q->rear);} free(q->front);} 6）队列的输出算法

void output2(LinkQueue *q)//输出队列 { QueuePtr p;p=q->front->next;printf(“链队列元素依次为:”);while(p){

printf(“%d->”,p->data);

p=p->next;} printf(“n”);} 7）队列的清空的算法 void Clear2(LinkQueue *q)//清空队列 { QueuePtr temp=q->front->next;while(temp){

QueuePtrtp=temp;

temp=temp->next;

free(tp);} temp=q->front;

q->front=q->rear=NULL;free(temp);} 8）返回对头元素的算法

int GetHead2(LinkQueue *q, int *e)//返回对头结点元素，存入e { if(q->front==q->rear)

return 0;*e=q->front->next->data;return 1;} 3.循环队列的实现和运算 1）队列的初始化算法

void InitSqueue3(Squeue3 *p)/*初始化队列*/ { p->base=(Datatype *)malloc(sizeof(Datatype)* MAXSIZE);p->front=0;p->rear=0;} 2）入队的算法

int Ensqueue3(Squeue3 *q, Datatype e)/*入队*/ { if((q->rear+1)% MAXSIZE == q->front){ printf(“n队列已满n”);return 0;} else q->base[q->rear]=e;/*将接收到得值付给队尾所指的节点*/ q->rear=(q->rear+1)% MAXSIZE;/*队尾向后移一位完成入队*/ return 1;} 3）出队的算法

int DeSqueue3(Squeue3 *q,Datatype *e)/*出队*/ { if(q->front==q->rear){ printf(“队列已空,无法出队!”);return 0;} *e=q->base[q->front];q->front=(q->front+1)%MAXSIZE;return 1;} 4判断队列是否为空的算法

int QueueEmpty3(Squeue3 q)// 判断是否为空 { if(q.front==q.rear)return 1;else return 0;} 5）对头元素的返还的算法

int Gethead3(Squeue3 *q,Datatype *e)// 取对头元素 { if(q->front==q->rear){ printf(“队列已空，无法出队!”);return 0;} else *e=q->base[q->front];return 1;} 6）遍历循环队列的算法

void display3(Squeue3 *q)//遍历循环对列 { int tail;tail=q->front;printf(“此队列数据为:n”);if(q->front==q->rear)printf(“此队列为空!”);else { while(tail!=q->rear){ printf(“%dt”, q->base[tail]);tail=(tail+1)%MAXSIZE;} printf(“n”);} } 4.主函数的算法 void main(){

int choice;Datatype e1;int i1,a1,x1,s1,j1;//顺序队列定义的量 int e2,i2,n2,s2,a2;//链队列定义的量

int i3,a3,x3,s3,j3;//循环队列定义的量 Datatype e3;

Squeue1 Q1;

//******************************* LinkQueue q;

//******************************** Squeue3 Q;

//**************************** choice=-1;Begin();while(choice!=0){ scanf(“%d”,&choice);switch(choice){ case 1://顺序队列

{

system(“cls”);InitSqueue1(&Q1);printf(“创建队列完成!n”);printf(“请输入数据个数j1=”);scanf(“%d”,&j1);for(i1=1;i1

{ printf(“请输入第%d个数据:”,i1);scanf(“%d”,&a1);Ensqueue1(&Q1,a1);

} printf(“对头为:%dn”,Q1.data[Q1.front]);printf(“队尾为:%dn”,Q1.data[Q1.front+j1-1]);display1(Q1);s1=-1;start1();while(s1!=0)

{

scanf(“%d”,&s1);switch(s1)

{ case 0:

system(“cls”);

choice=-1;

Begin();

break;case 1:

{

system(“cls”);printf(“请输入入队元素:n ”);scanf(“%d”,&x1);Ensqueue1(&Q1,x1);display1(Q1);

s1=-1;

start1();break;

} case 2:

{ system(“cls”);DeSqueue1(&Q1,&e1);display1(Q1);s1=-1;

start1();break;

} case 3:

{

system(“cls”);if(QueueEmpty1(Q1))printf(“此队列为空!n”);else printf(“此队列不为空!n”);

}

s1=-1;

start1();break;case 4:

{ system(“cls”);

Gethead1(&Q1,&e1);printf(“对头元素为:%dn”,e1);

s1=-1;

start1();break;

} case 5:

{ system(“cls”);display1(Q1);s1=-1;

start1();break;

}

}//switch

} //while

}//case1

break;//************************************************* case 2:

{

system(“cls”);

InitQueue2(&q);printf(“创建队列完成!n”);printf(“输入将建立链队列元素的个数:n2=”);scanf(“%d”,&n2);printf(“请输入队列的元素：n”);for(i2=1;i2

{

printf(“请输入第%d个元素:”,i2);

scanf(“%d”,&e2);

EnQueue2(&q,e2);

} a2=-1;start2();while(a2!=0)

{

scanf(“%d”,&a2);

switch(a2)

{

case 1:system(“cls”);

QueueLength2(&q);

a2=-1;start2();

break;

case 2:{

system(“cls”);

printf(“请输入入队元素:”);

scanf(“%d”,&e2);EnQueue2(&q,e2);

output2(&q);a2=-1;start2();

}break;

case 3:

system(“cls”);

e2=DeQueue2(&q,e2);

output2(&q);

printf(“出队元素为:%dn”,e2);a2=-1;start2();

break;

case 4:DestroyQueue2(&q);printf(“队列已销毁!n”);

a2=0;system(“cls”);

choice=-1;

Begin();

break;

case 5:

Clear2(&q);printf(“队列已清空n”);

a2=0;system(“cls”);

choice=-1;

Begin();

break;

case 6:

system(“cls”);GetHead2(&q,&e2);

printf(“队头元素为:%dn”,e2);s2=-1;

start2();

break;

case 0: system(“cls”);

choice=-1;

Begin();

break;

}//switch }//while

}//case2

break;//**************************************************

case 3:

{

system(“cls”);

InitSqueue3(&Q);printf(“创建队列完成!n”);printf(“请输入数据个数j3=”);scanf(“%d”,&j3);for(i3=1;i3

{ printf(“请输入第%d个数据:”,i3);scanf(“%d”,&a3);Ensqueue3(&Q,a3);

} printf(“对头为:%dn”,Q.base[Q.front]);printf(“队尾为:%dn”,Q.base[Q.front+j3-1]);display3(&Q);s3=-1;start3();while(s3!=0)

{

scanf(“%d”,&s3);switch(s3)

{ case 0:

system(“cls”);

choice=-1;

Begin();

break;case 1:

{

system(“cls”);printf(“请输入入队元素:n ”);scanf(“%d”,&x3);Ensqueue3(&Q,x3);display3(&Q);

s3=-1;

start3();break;

} case 2:

{ system(“cls”);DeSqueue3(&Q,&e3);display3(&Q);s3=-1;

start3();break;

} case 3:

{ system(“cls”);if(QueueEmpty3(Q))printf(“此队列为空!n”);else printf(“此队列不为空!n”);

}

s3=-1;

start3();break;case 4:

{ system(“cls”);

Gethead3(&Q,&e3);printf(“对头元素为:%dn”,e3);

s3=-1;

start3();break;

} case 5:

{ system(“cls”);display3(&Q);s3=-1;

start3();break;

}

}//switch

} //while

}//case 3

break;

case 0:

printf(“ 谢谢使用！！n”);

break;

//***************************

}//switch }//while }//main

四．调试分析（xxx）

顺序队列

1.编译并调试，运行程序。

2.设计测试用例，分析测试结果，以验证所完成的系统是否达到预期效果。3.判断队列是否为空。队列是否为空的标志就是队头指针和队尾指针是否同时指向队列中的同一个位置，即队头指针和队尾指针是否相等。

4.队列满时候不能入队列，否则会出现溢出现象。即先要判断队列是否已经已满，因为队尾指针的最大值是MAXQSIZE，所以通过检查队尾指针rear是否等于MAXQSIZE来判断队列是否已满。在删除队首元素时，应首先通过队头指针和队尾指针是否相等判断队列是否已空。

5.在元素出队操作，先通过队头指针和队尾指针是否相等判断队列是否已空，空时不能操作，这是要注意的。

6.程序满足了本次试验的目的和任务要求，可以进行人机交互，在后来的程序中将会做些改进，以增强人机交互性。

7.本程序存在较多不足，如有问题，参考用户手册。

8.在程序语句中，原本使用了大量的生僻的函数名，经过改进，目前使用都是通俗易懂的函数名称，方便用户理解。

链队列

1.编译并调试，运行程序。2.设计测试用例，分析测试结果，以验证所完成的系统是否达到预期效果。

3.要注意设定一个在链队列添加一个头结点并令指针指向头结点。同时，删除不可以在最后面进行删除，但是插入可以最后一个进行插入，这点需要注意 4.需要分别指向队头和队尾的指针。

5.程序满足了本次试验的目的和任务要求，可以进行人机交互，在后来的程序中将会做些改进，以增强人机交互性。

6.本程序存在较多不足，如有问题，参考用户手册。

7.在程序语句中，原本使用了大量的生僻的函数名，经过改进，目前使用都是通俗易懂的函数名称，方便用户理解。

循环队列

1.编译并调试，运行程序。

2.设计测试用例，分析测试结果，以验证所完成的系统是否达到预期效果。

3.为了避免顺序队列造成的“假溢出”现象，我们通常采用顺序循环队列实现队列的顺序存储。4.队头指针和对尾指针与队列元素之间关系和顺序队列一样，不变。5.先判断队列是否为空。就是看队头指针和队尾指针是否同时指向队列中的同一个位置，即队头指针和队尾指针是否相等，空时不能操作，这是要注意的。

6.在将元素插入到队列之前首先要判断队列是否已经已满，根据顺序循环队列队满条件front==(rear+1)%MAXQSIZE来判断队列是否已满。在删除队首元素时，应首先通过队头指针和队尾指针是否相等判断队列是否已空。

6.程序满足了本次试验的目的和任务要求，可以进行人机交互，在后来的程序中将会做些改进，以增强人机交互性。

7.本程序存在较多不足，如有问题，参考用户手册。

8.在程序语句中，原本使用了大量的生僻的函数名，经过改进，目前使用都是通俗易懂的函数名称，方便用户理解。

五、用户手册(xx)1.链队列

(1)本程序的运行环境为DOS操作系统，执行文件名为：j.exe.(2)进入演示程序后即显示文本方式的用户界面，输入元素1,2,3,4,5创建队列。

（3）根据提示，选择操作2执行元素入队操作。回车，输入入队元素0，回车，将0插入到队列中。

（4）选择操作3执行元素出队操作，回车，队首元素1出队。

（5）选择操作1执行输出队列长度操作，回车，输出队列长度为5.（6）选择操作5执行清空队列操作，回车，清空。

（7）选择操作6执行输出队头元素操作，回车，输出元素2。

2.顺序队列

（1）创建队列，输入数据

1,2,3,4,5.（2）选择操作1，执行入队操作.输入入队元素0

（3）选择操作2，执行出队操作。

队首元素1出队.（4）选择操作3，判断对是否为空

（5）选择操作4，输出对头元素2.（6）选择操作5，显示队列元素

3、循环队列

（1）创建队列，输入数据 1,2,3,4,5.（2）选择操作1，执行入队操作.输入入队元素0

（3）选择操作2，执行出队操作。队首元素1出队.（3）选择操作3，判断对是否为空

（5）选择操作4，输出对头元素2.（6）选择操作5，显示队列元素为,2,3,4,5,0

六．测试结果（xxx）1.顺序队列的实现和运算

1）输入1即可进行进入到顺序队列

2）顺序队列的建立，输入元素的个数为5，输入的数据分别为1，2，3，4，5，对头为1，队尾为5，此时队列的数据为1 2 3

3）输入2即可进行入队运算，输入的入队元素为0，此时的队列的数据为1 2 3 4 5 0

4）输入3即可进行判断队列的是否为空，如下图：

5）输入4即可进行去的对头元素的算法，如下图所示：

6）此时的队列的数

据

为

0，如

下

图

：

7）输入0即可退出顺序队列，如下图：

8）输入3即可进行顺序队列的算法，如下图所示：

9）输入1即可进

行

相

应的入

队

运

算，如

下

10）输入2即可进行队列的出队运算，如下图所示：

所

示

图

：11）输入3

即可判断顺序队列是否为空的算法，如下图所示：

12）输入4即可进行去的头结点的运算，如下图所示：

13）输入5即可进行队列的输出显示的运算，如

14）输入0即可进行退出顺序队列的算法，如下图所示：

下图所示：2.链式队列的实现和运算

1）队列的建立以及队列的个数输入为5，输入的数据分别为1，2，3，4，5.如下图：

2）输入2即可进入到元素的入队运算，输入入队的元素的为0，输入3即可进行相应的元素的出队运算，出队元素为1.如下图：

3）则此时的队列的长度为5，输入4即可进行队列的销毁以及输入5即可进行队列的清空运算，如下图：

4）输入6即可进行输出队列的对头元素，输入0即可进行退出链队列的运算

3．循环队列的实现和运算

1）输入3即可进行循环队列的操作，输入5个数据，它们分别为1 2 3 4 5，输入1，即可进行入队操作，输入入队的元素为0，则此时的数据为1 2 3 4 5 0，如下图所示：

2）输入2即可进行出队运算，如下图所示：

3）输入3即可进行判断队列的是否为空，如下图所示：

4）输入4即可进行取得对头元素，如

下

5)输入5即可进行输出所有的数据显示，如下图所示：

所示图：

七．心得体会（xx）

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出” 的线性表。注意的是为了避免顺序队列造成的“假溢出”现象，我们通常采用顺序循环队列实现队列的顺序存储。还有要注意的是在C语言中不能用动态分配的一维数组来实现循环队列，如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；若用户无法估计所用队列的最大长度，则宜采用链式队列。