文档介绍：队列实验报告
小组成员:********日期:********
需求分析〔**x〕
链队列
在本演示程序中,首先要链队列添加一个头结点,并判断队列是否为空,它只允许在表的一端进展插入,而在另一端删除元素,允许插入的一段叫队尾,允许删除的一端那么为对头,接着访问队列中所有元素,并输出,输出是每个元素之间用空格来完成。最后销毁队列,释放空间。
演示程序以用户和计算机的对话方式执行,即在计算机终端上显示"欢送来到链队列〞"元素入队〞"元素出队〞"销毁队列〞"清空队列〞之后。由用户在键盘上输入演示程序中规定的运算命令,相应的运算数据和显示结果显示在其后。
程序执行的命令包括:
欢送来到链队列
1输出队列长度
2元素入队
3元素出队
4销毁队列
5清空队列
6对头元素
7退出链队列
测试数据
入队 1
2
3
4
5
分别执行"元素入队〞"元素出队〞"销毁队列〞"清空队列〞等操作。
顺序队列
在本演示程序中,首先要顺序队列添加一个头结点,并判断队列是否为空,它只允许在表的一端进展插入,而在另一端删除元素,允许插入的一段叫队尾,允许删除的一端那么为对头,接着访问队列中所有元素,并输出,输出是每个元素之间用空格来完成。
演示程序以用户和计算机的对话方式执行,即在计算机终端上显示"欢送来到链队列〞"元素入队〞"元素出队〞"取得头结点〞"输出显示〞之后。由用户在键盘上输入演示程序中规定的运算命令,相应的运算数据和显示结果显示在其后。
3〕程序执行的命令包括:
欢送来到顺序队列
1入队
2出队
3判断是否为空
4取得头结点
5输出显示
6退出顺序队列
4〕测试数据
入队 1
2
3
4
5
分别执行"元素入队〞"元素出队〞等操作。
3循环队列
1〕在本演示程序中,首先要顺序队列添加一个头结点,并判断队列是否为空,初始化建空队列时,令front=rear=0,每当插入新的队列尾元素时,"尾指针增1〞;每当删除队列头元素时,"头指针增1〞。
接着访问队列中所有元素,并输出,输出是每个元素之间用空格来完成。
演示程序以用户和计算机的对话方式执行,即在计算机终端上显示"欢送来到链队列〞"元素入队〞"元素出队〞"取得头结点〞"输出显示〞之后。由用户在键盘上输入演示程序中规定的运算命令,相应的运算数据和显示结果显示在其后。
3〕程序执行的命令包括:
欢送来到循环队列
1入队
2出队
3判断是否为空
4取得头结点
5输出显示
6退出顺序队列
4〕测试数据
入队 1
2
3
4
5
分别执行"元素入队〞"元素出队〞等操作。
概要设计(****)
⒈为实现上述算法,需要顺序表的抽象数据类型,抽象数据类型定义如下:
ADT Queue {
数据对象:D={ ai|ai∈ElemSet, i=1,2,3...,n, n>=0 }
数据关系: R={ <ai-1,ai>|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
typedef struct QNode
{
QElemType;
struct QNode *next;//指针域
}QNode,*QueuePtr;
Typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
Status InitQueue (LinkQueue&Q)
//构造一个空队列。
Status DestroyQueue (LinkQueue&Q)
//销毁队列Q,Q不存在。
Status ClearQueue(LinkQueue&Q)
//将Q清为空队列。