软件工程系 实验报告封面
课程名称： 数据结构与算法
课程代码： SS1005
实验指导老师: 钟迅科
实验报告名称： Lab05 队列的实现
学生姓名： 张三 学号： 1140888888 教学班： FJ01 递交日期：2012年10月11日
我申明，本报告内的实验已按要求完成，报告完全是由我个人完成，并没有抄袭行为。我已经保留了这份实验报告的副本。
申明人(签名):
本实验报告包括以下几个内容：
一、实验(实践)目的
二、实验(实践)环境
三、实验(实践)实现过程
四、实验(实践)分析与总结
五、指导教师评语与评分
实验题目Lab05 队列的实现
实验地点B406 实验时间2012年10月11日
一、实验目的和要求
1、目的
1）掌握链式存储结构的队列的特点与实现；
2）掌握循环顺序存储结构的队列的特点与实现；
3）理解栈和队列的简单应用。
2、要求
1）验证链式队列的入队过程；
2）验证链式队列的出队过程；
3）验证顺序队列（循环队列）的入队过程；
4）验证顺序队列（循环队列）的出队过程；
5）利用栈的“后进先出”的特性与队列的“先进先出”的特性，编写程序判断回文。
二、实验环境（本实验的硬件和软件环境）
1）PC机；
2）Windows XP以上版本的操作系统；
3）Visual Studio 2010以上版本的开发工具；
4）项目文件：
LinkQueue.h和LinkQueue.cpp：实现队列链式存储结构的头文件和源代码；
SqQueue.h和SqQueue.cpp：实现队列顺序存储结构的头文件和源代码；
LinkStack.h和LinkStack.cpp：实现栈链式存储结构的头文件和源代码；
SqStack.h和SqStack.cpp：实现栈顺序存储结构的头文件和源代码。
三、实验实现过程
链式队列：
1) 在语句EnQueue(Q1,'a');处按“F9”设置断点①，按“F5”调试程序至断点处暂停（暂停序号0），然后按“F10”调试程序3次，每次程序暂停时记录数据。调试结束时按“Shift+F5”结束调试过程。
2) 取消其它断点，在语句DeQueue(Q1, temp);处按“F9”设置断点②，按“F5”调试程序至断点处暂停（暂停序号0），然后按“F10”调试程序3次，每次程序暂停时记录数据。
循环队列：
1) 取消其它断点，在语句EnQueue(Q2,'a');处按“F9”设置断点③，按“F5”调试程序至断点处暂停（暂停序号0），然后按“F10”调试程序5次，每次程序暂停时记录数据。观察第5次调试时队列中数据，分析入队EnQueue(Q2,'e');是否成功，并说明原因。
2) 取消其它断点，在语句DeQueue(Q2, temp);处按“F9”设置断点④，按“F5”调试程序至断点处暂停（暂停序号0），然后按“F10”调试程序4次，每次程序暂停时记录数据。
3) 取消其它断点，在语句EnQueue(Q2,'j');处按“F9”设置断点⑤，按“F5”调试程序至断点处暂停，然后按“F10”调试程序1次，程序暂停时记录数据。观察队列中数据，分析入队EnQueue(Q2,'j');是否成功，并说明原因。
四、实验结果、分析、总结
1）通过上述验证过程，总结链式结构和顺序结构在入队、出队操作时的异同：
相同点：
插入（入队）操作：在队尾位置进行，需要更新队尾rear指针；
删除（出队）操作：在队头位置进行，需要更新队头front指针。
不同点：
链式结构第一元素入队时，在更新队尾指针的同时也须更新队头指针；最后一个元素出队时，在更新队头指针的同时也须更新队尾指针。
顺序结构入队操作只需要更新队尾rear指针；出队操作只需要更新队头front指针。
2）判断回文的函数实现：
int Palindrome_Test(char str[])
{
SNode *S; LinkQueue Q;
InitStack(S); InitQueue(Q);
DataType ts,tq;
for(int i=0; i{
Push(S,str[i]);EnQueue(Q,str[i]);
}
while(!StackEmpty(S))
{
Pop(S,ts);DeQueue(Q,tq);
if(ts!=tq) return 0;
}
return 1;
}
五、实验教师评语及成绩：
教师签名：批阅时间年月日
