石家庄经济学院
实 验 报 告
学 院: 数理学院
专 业: 数学与应用数学
班 级: 一班
学 号: XXXXXXXX
姓 名: XXXX
信息工程学院计算机实验中心制
实验题目：链队列存储
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示及基本操作的实现
实验室： 260 设备编号： 402 完成日期： 2011/05/13
一、实验目的
1.掌握队列的思想及其存储实现。
2.掌握队列的常见算法的程序实现。
二、实验内容
1.建立一个链式空队列，并能够完成出队、入队及求队长等基本操作。。
三、实验的内容及完成情况
1. 需求分析
(1)链队列的抽象数据类型ADT的描述及实现。
本实验实现使用Visual c++6.0实现线性表顺序存储结构的表示及操作。具体实现要求：
(2)完成链式队列的表示和实现。
(3)实现链式队列的建立和初始化。
(4)实现链式队列的入队、出队、求队长等操作。
2．概要设计
抽象数据类型队列的定义：
ADT Queue{
数据对象：D={ai |ai∈ ElemSet,i=1,2,……,n,n≥0}
数据关系：R1={
|ai-1,ai∈ D,i=2,……,n}
约定其中a1端为队列头，an端为队列尾。
基本操作：
InitQueue(&Q)
操作结果：构造一个空队列Q。
EnQueue(&Q,e)
初始条件：队列Q已存在。
操作结果：插入元素e为Q的新的队尾元素。
DeQueue(&Q,&e)
初始条件：Q为非空队列。
操作结果：删除Q的队头元素，并用e返回其值。
Queuelength(&Q)
初始条件：队列Q已存在。
操作结果：返回Q的元素个数，即队列长度。
DestroyQueue(LinkQueue &Q)
//销毁队列Q，队列Q不再存在
} ADT Queue;
3．详细设计
（1）抽象数据类型队列的表示和实现
//链式队列结构类型
typedef struct QNode
{
Qelemtype data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
//构造一个空队列
status InitQueue(LinkQueue &Q)
{//构造一个空的队列Q
Q.front=Q.rear=(QueuePtr)malloc(100*sizeof(QNode));
if(!Q.front) exit(OVERFLOW);
Q.rear->next=NULL;
return OK;
}
//插入队尾元素
status EnQueue(LinkQueue &Q,Qelemtype e)
{//插入元素e为Q的新的队尾元素
p=(QueuePtr)malloc(100*sizeof(QNode));
if(!p) exit(OVERFLOW);
p->data=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
//删除队头元素
status DeQueue(LinkQueue &Q,Qelemtype &e)
{//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；
//否则返回ERROR;
if(Q.rear==Q.front) return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;
free(p);
return OK;
}
//求队列长度
void Queuelength(LinkQueue &Q)
{
n=0;
p=Q.front->next;
while(p!=NULL)
{
n++; p=p->next;
}
printf("链队列长度为：%d\n",n);
}
//销毁队列
status DestroyQueue(LinkQueue &Q)
{//销毁队列
while(Q.front)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
printf("队列已销毁！\n");
return OK;
}
（2）主函数的伪码算法
void main()//主函数
{
int a;
printf("》》》》》》》》>>数据结构实验二<<《《《《《《《《\n");
printf("**********链队列存储表示及基本操作的实现*********\n");
do
{
menu();
printf("请按提示输入指令:");
scanf("%d",&a);
switch(a)
{//调用各函数
case 1:{
input();
output(Q);
}break;
case 2:
Queuelength(Q);break;
case 3:{
printf("请输入入队元素：");
scanf("%d",&e);
if(EnQueue(Q,e)==1) output(Q);
}break;
case 4:if(DeQueue(Q,e)==1)
{
output(Q);
printf("出队元素为：%d\n",e);
}
else printf("队列为空~无法执行删除操作~\n"); break;
case 5:
DestroyQueue(Q);break;
case 0: printf("谢谢您的使用,再见 (*^__^*)!\n");
return;
default :
printf("输入有误,请重新输入 (*^__^*)\n");
}
}while(a!=0);
}
4. 调试分析
(1)
调试过程中出现的问题
经过上次试验的练习，这次调试过程没有出现变量定义问题等的小错误；主要是逻辑错误，可以通过组建和编译，但是运行的时候达不到要求。通过简单的修改就可以啦！
(2)
经验和体会
1. 多思考、多尝试才能更好的完成程序的编写。
2. 算法是程序编写的灵魂，透彻的了解算法有助于编写程序。
3. 编写程序时细心才能少出错！
(3)
算法的时空分析和改进
入队操作：T(n)=O(1)；
出队操作：T(n)=O(1)；
求队列长度：T(n)=O(n)；
销毁队列：T(n)=O(n)；
5．用户使用说明
打开可执行程序，即Visual C++6.0环境下，,参照用户选择界面提示即可使用本程序
6．测试结果
演示操作如下：运行程序
输入指令：1 创建队列并初始化
初始化完毕，输入指令：3 入队操作
入队操作完毕，输入指令：4 出队操作
出队操作完毕，输入指令：2 输出队列长
操作完毕，输入指令：5 销毁队列
演示完毕，输入指令：0 退出系统
7．附录
源程序清单：
#include
#include
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Qelemtype;
typedef int
status;
typedef struct QNode
{
Qelemtype data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
int e,i,n;
QueuePtr p;
LinkQueue Q;
status InitQueue(LinkQueue &Q)
{//构造一个空的队列Q
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front) exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
status EnQueue(LinkQueue &Q,Qelemtype e)
{//插入元素e为Q的新的队尾元素
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
p->data=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
status DeQueue(LinkQueue &Q,Qelemtype &e)
{//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；
//否则返回ERROR;
if(Q.rear==Q.front) return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;
free(p);
return OK;
}
status Queuelength(LinkQueue &Q)
{
if(Q.rear==Q.front) return ERROR;
n=0;
p=Q.front->next;
while(p!=NULL)
{
n++;
p=p->next;
}
printf("链队列长度为：%d\n",n);
return OK;
}
status DestroyQueue(LinkQueue &Q)
{//销毁队列
while(Q.front)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
printf("队列已销毁！\n");
return OK;
}
void input()
{
if(InitQueue(Q)!=1) printf("分配空间失败！");
printf("输入将建立链队列元素的个数：n= ");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("链队列第%d个元素的值为：",i);
scanf("%d",&e);
EnQueue(Q,e);
}
}
void output(LinkQueue &Q)
{
p=Q.front->next;
printf("链队列元素依次为：");
while(p!=NULL)
{
printf("%d-->",p->data);
p=p->next;
}
printf("\n");
}
void menu()
{//菜单函数
printf("==================================================\n");
printf(" ★1建立队列并初始化 \n");
printf(" ★2输出队列长度 \n");
printf(" ★3元素入队 \n");
printf(" ★4元素出队 \n");
printf(" ★5销毁队列 \n");
printf(" ★0退出系统 \n");
printf("==================================================\n");
}//menu
void main()//主函数
{
int a;
printf("》》》》》》》》>>数据结构实验二<<《《《《《《《《\n");
printf("**********链队列存储表示及基本操作的实现*********\n");
do
{
menu();
printf("请按提示输入指令:");
scanf("%d",&a);
switch(a)
{//调用各函数
case 1:{
input();
output(Q);
}break;
case 2:
Queuelength(Q);break;
case 3:{
printf("请输入入队元素：");
scanf("%d",&e);
if(EnQueue(Q,e)==1) output(Q);
}break;
case 4:if(DeQueue(Q,e)==1)
{
output(Q);
printf("出队元素为：%d\n",e);
}
else printf("队列为空~无法执行删除操作~\n"); break;
case 5:
DestroyQueue(Q);break;
case 0: printf("谢谢您的使用,再见 (*^__^*)!\n");
return;
default :
printf("输入有误,请重新输入 (*^__^*)\n");
}
}while(a!=0);
}
四、实验总结
1.掌握了队列的思想及其存储实现。
2.掌握了队列的常见算法的程序实现，如建队、入队、出队、求队长、销毁队列等。
3.熟练了C程序的编写和链表指针的使用。
五、成绩
浙公网安备 33021202002483