数据结构实验报告：循环队列的应用与串的匹配操作.doc

《数据结构实验报告：循环队列的应用与串的匹配操作.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.工业学院计算机工程系《数据结构》·实验报告实验名称实验三、循环队列的应用与串的匹配操作实验时间学生班级学号指导教师批阅教师成绩实验目的：1）掌握循环队列和串的基本原理2）掌握循环队列和串的存储结构3）掌握循环队列的入队、出队、判断队空的实现方法和串的匹配方法4）掌握循环队列和串的基本应用和实现方法实验设备与要求：PC机一台，安装有Windows操作系统以及VC6.0及以上版本1）熟悉C++语言编程2）熟练使用C++语言实现循环队列的入队、出队、判断栈空等操作，串的匹配操作3）熟练使用循环队列的入队、

2、出队算法，串的BF算法。实验容：1、舞伴配对问题：假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者，等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。2、用BF算法实现串S=”abbacdbaafcefg”,T=”cdbaaf”的匹配操作。实验步骤及实验结果记录：算法分析：1、舞伴配对问题：假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人

3、配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者，等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。2、用BF算法实现串S=”abbacdbaafcefg”,T=”cdbaaf”的匹配操作。问题分析：1、..先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性，可用队列作为算法的数据结构。在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直

4、至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。伪代码：1、输入两个队列2、两个队列进行入队操作3、判断队列长度4、两个队列进行匹配出队操作5、短队列出对完成，长队列等待下一队列的到来设Man对为ABCDEFGH，设Woman队为IJKLMN。当Man队列和Woman队列都入队完成之后，开始配对：A-IB-JC-KD-LE-MF-NG-H-此时Man队列就还有两个人没有舞伴，等待下一轮Woman的队

5、列1、参照教材所列BF算法实现，串S和T的匹配操作。（1）、在串S和串T中设比较的起始下标i和j；（2）、循环直到S中所剩字符个数小于T的长度或T的所有字符均比较完2.1如果S[i]=T[j]，继续比较S和T的下一个字符；否则2.2将i和j回溯，准备下一趟比较；（3）、如果T中所有字符均比较完，则匹配成功，返回匹配的起始比较下标；否则，匹配失败，返回0；（4）、S=”abbacdbaafcefg”,T=”cdbaaf”程序代码1、舞伴配对问题：头文件：LinkQueue.h#pragmaoncetem

6、platestructNode{DataTypedata;Node*next;};..templateclassLinkQueue{public:LinkQueue();~LinkQueue();voidEnQueue(DataTypex);DataTypeDeQueue();DataTypeGetQueue();intgetArrayLen(DataTypeArray[]);intEmpty();private:Node

7、*front,*rear;};源文件：LinkQueue.cpp#include"LinkQueue.h"templateLinkQueue::LinkQueue(){Node*s=NULL;s=newNode;s->next=NULL;front=rear=s;}templateLinkQueue::~LinkQueue(){Node

8、aType>*p=NULL;while(front!=NULL){p=front->next;deletefront;front=p;}}templatevoidLinkQueue::EnQueue(DataTypex){Node*s=NULL;s=newNode;s->data=x;s->next=NULL;rear->next=s;rear=s;}templat