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

数据结构队列实验报告

第一篇：数据结构队列实验报告队列实验报告小组成员：xxxxxxxx日期：xxxxxxxx一、需求分析（xxx）1.链队列1）在本演示程序中，首先要链队列添加一个头结点，并判断队列是否为空，它只允许在表的一端进行插入，而在另一端删除元素，允许插入的一段叫队尾，允许删除的一端则为对头，接着访问队列中所有元素，并输出，输出是每个元素之间用空格来完成。最后销毁队列，释放空间。2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“欢迎来到链队列”“元素入队”“元素出队”“销毁队列”“清空队列”之后。由用户在键盘上输入演示程序中规定的运算命令，相应的运算数据和显示结果显示在其后。3）程序执行的命令包括：欢迎来到链队列1输出队列长度2元素入队3元素出队4销毁队列5清空队列6对头元素7退出链队列4）测试数据入队12345分别执行“元素入队”“元素出队”“销毁队列”“清空队列”等操作。2.顺序队列1）在本演示程序中，首先要顺序队列添加一个头结点，并判断队列是否为空，它只允许在表的一端进行插入，而在另一端删除元素，允许插入的一段叫队尾，允许删除的一端则为对头，接着访问队列中所有元素，并输出，输出是每个元素之间用空格来完成。2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“欢迎来到链队列”“元素入队”“元素出队”“取得头结点”“输出显示”之后。由用户在键盘上输入演示程序中规定的运算命令，相应的运算数据和显示结果显示在其后。3）程序执行的命令包括：欢迎来到顺序队列1入队2出队3判断是否为空4取得头结点5输出显示6退出顺序队列4）测试数据入队12345分别执行“元素入队”“元素出队”等操作。3循环队列1）在本演示程序中，首先要顺序队列添加一个头结点，并判断队列是否为空，初始化建空队列时，令front=rear=0,每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。接着访问队列中所有元素，并输出，输出是每个元素之间用空格来完成。2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“欢迎来到链队列”“元素入队”“元素出队”“取得头结点”“输出显示”之后。由用户在键盘上输入演示程序中规定的运算命令，相应的运算数据和显示结果显示在其后。3）程序执行的命令包括：欢迎来到循环队列1入队2出队3判断是否为空4取得头结点5输出显示6退出顺序队列4）测试数据入队12345分别执行“元素入队”“元素出队”等操作。二．概要设计(xxxx)⒈为实现上述算法，需要顺序表的抽象数据类型，抽象数据类型定义如下：ADTQueue{数据对象：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返回其值。}ADTQueue2.单链队列typedefstructQNode{QElemType;structQNode*next;//指针域}QNode,*QueuePtr;Typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;StatusInitQueue(LinkQueue&Q)//构造一个空队列。StatusDestroyQueue(LinkQueue&Q)//销毁队列Q，Q不存在。StatusClearQueue(LinkQueue&Q)//将Q清为空队列。StatusQueueEmpty(LinkQueueQ)//若Q为空队列，则返回TRUE,否则FALSE。intQueueLength(LinkQueueQ)//返回Q元素的个数，即队列的长度。StatusGetHead(LinkQueueQ,QElemType&e)//若队列不为空，则用e返回Q的队头元素，并返回OK;否则返回ERROR。StatusEnQueue(LinkQueue&Q,QElemTypee)//插入e返回Q的新的队尾元素。StatusDe