资源描述
XX工业学院计算机工程系数据结构实验报告实验名称实验三、循环队列的应用与串的匹配操作实验时间学生姓名班级学号指导教师批阅教师成绩实验目的：1掌握循环队列和串的基本原理 2掌握循环队列和串的存储结构 3掌握循环队列的入队、出队、判断队空的实现方法和串的匹配方法 4掌握循环队列和串的基本应用和实现方法实验设备与要求：PC机一台.安装有Windows操作系统以及VC6.0及以上版本1熟悉C+语言编程 2熟练使用C+语言实现循环队列的入队、出队、判断栈空等操作.串的匹配操作 3熟练使用循环队列的入队、出队算法.串的BF算法。实验内容：1、舞伴配对问题：假设在周末舞会上.男士们和女士们进入舞厅时.各自排成一队。跳舞开始时.依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同.则较长的那一队中未配对者.等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。 2、用BF算法实现串S=abbacdbaafcefg,T=cdbaaf的匹配操作。实验步骤及实验结果记录：算法分析： 1、舞伴配对问题：假设在周末舞会上.男士们和女士们进入舞厅时.各自排成一队。跳舞开始时.依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同.则较长的那一队中未配对者.等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。 2、用BF算法实现串S=abbacdbaafcefg,T=cdbaaf的匹配操作。问题分析：1、 先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性.可用队列作为算法的数据结构。在算法中.假设男士和女士的记录存放在一个数组中作为输入.然后依次扫描该数组的各元素.并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后.依次将两队当前的队头元素出队来配成舞伴.直至某队列变空为止。此时.若某队仍有等待配对者.算法输出此队列中等待者的人数及排在队头的等待者的名字.他或她将是下一轮舞曲开始时第一个可获得舞伴的人。伪代码：1、 输入两个队列2、 两个队列进行入队操作3、 判断队列长度4、 两个队列进行匹配出队操作5、 短队列出对完成.长队列等待下一队列的到来设Man对为ABCDEFGH.设Woman队为IJKLMN。当Man队列和Woman队列都入队完成之后.开始配对：A- IB- JC- KD- LE- MF- NG-H-此时Man队列就还有两个人没有舞伴.等待下一轮Woman的队列2、 参照教材所列BF算法实现.串S和T的匹配操作。1、在串S和串T中设比较的起始下标i和j；2、循环直到S中所剩字符个数小于T的长度或T的所有字符均比较完 2.1 如果Si=Tj.继续比较S和T的下一个字符；否则2.2 将i和j回溯.准备下一趟比较；3、如果T中所有字符均比较完.则匹配成功.返回匹配的起始比较下标； 否则.匹配失败.返回0； 4、S=abbacdbaafcefg,T=cdbaaf程序代码1、舞伴配对问题：头文件：LinkQueue.h#pragmaoncetemplate structNodeDataType data;Node * next;templateclassLinkQueuepublic:LinkQueue;LinkQueue;void EnQueue;DataType DeQueue;DataType GetQueue;int getArrayLen;int Empty;private:Node * front, *rear;源文件：LinkQueue.cpp#includeLinkQueue.htemplateLinkQueue:LinkQueueNode *s = NULL;s = newNode;s-next = NULL;front = rear = s;templateLinkQueue:LinkQueueNode *p = NULL;while p = front-next;delete front;front = p;templatevoidLinkQueue:EnQueueNode*s = NULL;s = newNode;s-data = x;s-next = NULL;rear-next = s;rear = s;templateDataTypeLinkQueue:DeQueueNode *p = NULL;int x;if throw下溢;p = front-next;x = p-data;front-next = p-next;if next = NULLrear = front;delete p;return x;templateDataTypeLinkQueue:GetQueueif return front-next-data;elsereturnfalse;templateintLinkQueue:Emptyif return 1;elsereturn 0;template /获取数组长度intLinkQueue:getArrayLenreturn sizeof / sizeof-1;源文件：LinkQueue_main.cpp#include#includeLinkQueue.cppusingnamespace std;/334a6c1d5e27c49d 543b75adbb34afc0int main LinkQueue Q1;LinkQueue Q2;char Man100;char Woman100;int length1, length2;cout Man;cout Woman;cout endl;length1 = strlen; /获取Man数组的长度length2 = strlen; /获取Woman数组的长度cout 男士人数: length1 女士人数:length2 endl;cout endl;for int i = 0; i /对Man数组进行入队操作Q1.EnQueue;for int i = 0; i /对Woman进行入队操作Q2.EnQueue;if length1 /当男士人数小于女士人数时.先开始男士的配对.剩余女士进行下一组配对cout 配对开始！男士在前 endl;cout 女士 男士 endl;for int i = 0; i cout Q1.GetQueue - Q2.GetQueue endl;Q1.DeQueue;Q2.DeQueue;if cout 还有以下几位女士等待下一组： endl;for int i = length1; i cout Q2.GetQueue ;Q2.DeQueue;cout endl;elseif length2 /当女士人数小于男士人数时.先开始女士的配对.剩余男士进行下一组配对cout 配对开始！女士在前 endl;cout 女士 男士 endl;for int i = 0; i cout Q2.GetQueue - Q1.GetQueue endl;Q1.DeQueue;Q2.DeQueue;if cout 还有以下几位男士等待下一组： endl;for int i = length2; i cout Q1.GetQueue ;Q1.DeQueue;cout endl;return 0;程序代码2、BF算法：#includeusingnamespace std;int mainchar S = abbacdbaafcefg;char T = cdbaaf;cout 串S: Sendl;cout 串T: Tendl;cout 开始匹配！ endl;int i = 0, j = 0;while & if i+;j+;elsei = i - j + 1;j = 0;if cout 匹配成功! endl;cout T开始匹配S位置： i - j + 1 endl;elsecout 匹配失败！ endl;return 0;运行结果实验一、舞伴配对实验二、BF算法实验总结：本次实验初步了解了队列的创建、入队、出队、取队头等基本操作。能够简单完成队列的基本操作。同时也对算法有了进一步的认识.队列的使用与生活中的现象息息相关.这次实验.也是将生活搬入程序的一次实践。让我明白.生活中很多问题都可以通过程序来实现。同时.这次实验也对BF算法有了一定的理解.这对自己以后写算法有很大的帮助！8 / 8
展开阅读全文