数据结构与算法课程笔记（五） |
您所在的位置：网站首页 › 写出在顺序队列中将将元素e入队的算法 › 数据结构与算法课程笔记（五） |
数据结构与算法课程笔记（五）
|
实验五 队列的实现
一、实验目的二、实验环境三、实验内容和步骤四、编程题：（根据附件中的项目，上机验证下面各题目）
一、实验目的
（1） 链式存储结构的队列的特点与实现； （2） 循环顺序存储结构的队列的特点与实现； （3） 栈和队列的简单应用； 二、实验环境Windows 7以上版本的操作系统， VS2010以上编程环境。 三、实验内容和步骤本实验项目包含如下文件： LinkQueue.h和LinkQueue.cpp分别是实现队列链式存储结构的头文件和源代码； SqQueue.h和SqQueue.cpp分别是实现队列顺序存储结构的头文件和源代码； LinkStack.h和LinkStack.cpp分别是实现栈链式存储结构的头文件和源代码； SqStack.h和SqStack.cpp分别是实现栈顺序存储结构的头文件和源代码。 链式队列示意图：（下图包含头结点。课本P104页图3.20没有头结点，程序较复杂。本程序使用头结点的好处是可以在入队和出队时简化程序逻辑。） 2)取消其它断点，在语句 DeQueue(Q1, temp); 处按“F9”设置断点②，按“F5”调试程序至断点处暂停（暂停序号0），然后按“F10”调试程序3次，每次程序暂停时记录数据。 暂停序号队头元素队尾元素队列中全部元素0‘a’‘c’’a’, ‘b’, ‘c’1‘b’‘c’’b’, ‘c’2’c’‘c’’c’3无无无2． 队列的 顺序存储 结构的实现（少用一个存储单元实现循环队列）。 1)取消其它断点，在语句**EnQueue(Q2,‘a’);**处按“F9”设置断点③，按“F5”调试程序至断点处暂停（暂停序号0），然后按“F10”调试程序5次，每次程序暂停时记录数据。观察第5次调试时队列中数据，分析入队EnQueue(Q2,‘e’);是否成功，并说明为什么？ 循环队列队头元素位置：Q2.front 循环队列队尾元素位置： (Q2.rear - 1 + MaxSize) % MaxSize 循环队列容量： MaxSize - 1 暂停序号frontrear队列中全部元素000无101’a’202‘a’, 'b’303‘a’, ‘b’, 'c’404‘a’, ‘b’, ‘c’, 'd’504‘a’, ‘b’, ‘c’, ‘d’答：入队EnQueue(Q2,‘e’);失败，因为队列容量MaxSize-1为4，第4次调试时队列已满。 2)取消其它断点，在语句 DeQueue(Q2, temp); 处按“F9”设置断点④，按“F5”调试程序至断点处暂停（暂停序号0），然后按“F10”调试程序4次，每次程序暂停时记录数据。 注意：出队时，并不会在内存中清除掉实际的元素，这是顺序存储（数组）的特点。队列由 front 和 rear 指示即可。 循环队列队空的标志： Q2.front == Q2.rear 暂停序号frontrear队列中全部元素004’a’, ‘b’, ‘c’, ‘d’114’b’, ‘c’, ‘d’224’c’, ‘d’334’d’444无3)取消其它断点，在语句 EnQueue(Q2,‘j’); 处按“F9”设置断点⑤，按“F5”调试程序至断点处暂停，然后按“F10”调试程序1次，程序暂停时记录数据。观察队列中数据，分析入队 EnQueue(Q2,‘j’); 是否成功，并说明为什么？ 循环队列队满的标志：(Q2.rear + 1) % MaxSize == Q2.front 暂停序号frontrear队列中全部元素043‘f’, ‘g’, ‘h’. ‘i’143‘f’, ‘g’, ‘h’. ‘i’答：入队EnQueue(Q2,‘j’);失败，因为循环队列堆满的标志成立，无法再入队。 通过上述验证过程，总结链式结构和顺序结构在入队、出队操作时的异同？ 答： 相同点： 入队操作：在队尾位置进行，需要更新队尾rear； 出队操作：在对头位置进行，需要更新对头front； 不同点： 链式结构最后一个元素出队时，在更新对头指针的同时也需更新队尾指针。 顺序结构入队操作只需要更新队尾rear；出队操作只需更新对头front。 四、编程题：（根据附件中的项目，上机验证下面各题目）阅读Content.cpp文件中的void Reverse(LinkQueue Q)函数，回答下列问题： 1． 该函数的功能是什么？利用下面的主函数替代原来文件的主函数，观察运行结果验证你的结论。//利用栈结构逆置队列 int main() { LinkQueue Q; InitQueue(Q); for(int i=0; i |
验证题：（根据附件中的项目，上机验证下面各题） 根据课件目录提供的 .cpp 和 .h 文件建立项目。 1． 队列的 链式存储 结构实现。 1)在语句 EnQueue(Q1,‘a’); 处按“F9”设置断点①，按“F5”调试程序至断点处暂停（暂停序号0），然后按“F10”调试程序3次，每次程序暂停时记录数据。调试结束时按“Shift+F5”结束调试过程。 链队列队头元素位置： Q1.front->next 链队列队尾元素位置：Q1.rear 链队列队空的标志： Q1.front == Q1.rear 或 Q1.front->next == NULL【本文地址】
今日新闻 |
推荐新闻 |