数据结构--队列实验报告.docx

队列实验报告小组成员：xxxxxxxx日期：xxxxxxxx1、 需求分析（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分别执行“元素入队”“元素出队”等操作。2 概要设计(xxxx) 为实现上述算法，需要顺序表的抽象数据类型，抽象数据类型定义如下：ADT Queue 数据对象：D= ai|aiElemSet, i=1,2,3.,n, n=0 数据关系: R= |ai-1,aiD,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 Queue2.单链队列typedef struct QNode QElemType; struct QNode *next;/指针域QNode,*QueuePtr;Typedef structQueuePtr 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。 int QueueLength(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）元素的类型typedef struct Datatype dataMAXSIZE; int front,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-dataq-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-dataq-front; return 1; 7）遍历顺序队列的算法void display1(Squeue1 q) /遍历顺序对列 printf(此队列数据为:n); if (q.front=q.rear) printf(此队列为空!); else while(q.front 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)/队头结点出队,将出队的元素存入eQueuePtr 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;/要出队的数据元素为eq-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)QueuePtr tp=temp;temp=temp-next;free(tp);temp=q-front;q-front=q-rear=NULL;free(temp);8）返回对头元素的算法int GetHead2(LinkQueue *q, int *e)/返回对头结点元素，存入eif(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-baseq-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-baseq-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-baseq-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-basetail); 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=j1;i1+) /输入的数据个数不要超过MAXSIZE,多了的部分没有插入队列 printf(请输入第%d个数据:,i1); scanf(%d,&a1); Ensqueue1(&Q1,a1); printf(对头为:%dn,Q1.dataQ1.front); printf(队尾为:%dn,Q1.dataQ1.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=n2;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=j3;i3+) /输入的数据个数不要超过MAXSIZE,多了的部分没有插入队列 printf(请输入第%d个数据:,i3); scanf(%d,&a3); Ensqueue3(&Q,a3); printf(对头为:%dn,Q.baseQ.front); printf(队尾为:%dn,Q.baseQ.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 /main4 调试分析（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