最小回文问题实验报告

《最小回文问题实验报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、Xx学院计算机科学与技术系课程设计报告2010～2011学年第2学期课程数据结构与算法课程设计题目名称最小回文代价问题学生姓名XXXX学号XXXXXXXX专业班级XXXX班指导教师XXX、XXX2011年6月1、题目最小回文代价问题：回文是指一个对称的字符串，代表这个串从左往右读和从右往左读是一样的。给定一个字符串,往其中插入最少的字符，得到一个回文串，求最小插入字符数。2、问题分析（一）本程序要求实现给定一个字符串,往其中插入最少的字符，得到一个回文串，求最小插入字符数。首先需要明确算法思想，根据提示知道，算法

2、思想是用原字符串的长度减去原字符串和逆序字符串的公共序列长度，所以本程序关键要实现：（1）输入一给定字的符串；（2）求该字符串的逆序；（3）求原字符串和逆序字符串的最大公共序列长度；（4）求原字符串的长度减去最大公共序列长度，即为最少插入字符数（二）数据的输入形式和输入值的范围：首先输入一个字符串，然后输入选择键：1表示继续输入字符串，0表示结束该程序。（1）结果的输出形式：如果该字符串是回文，则输出该字符串是回文，最少需要插入字符0；如果该字符串不是回文，则输出该字符串不是回文并输出最少需要插入的字符数。（2）

3、测试数据：（a）输入的字符串为：abacdbac（b）输入的字符串为：abcddcba（c）输入的字符串为：abcdefghijk3、数据结构的选择和概要设计（1）该程序的数据结构为一个存放原字符串的数组s，一个存放逆序字符串的数组daoxu和一个用于存放公共序列长度的二维数组LCS。（2）为了实现上述程序的功能，需要：A，输入一给定的字符串B，求出该字符串的逆序C，求出原字符串和逆序字符串的最大公共序列长度D，求出原字符串的长度减去最大公共序列长度，即为最少插入字符数daozhi（）（3）本程序包含4个函数：m

4、ain（）a，主函数main（）b，字符串倒置函数：daozhi（）length（）c，计算最大公共序列长度函数：length（）各函数间关系如右图1所示：图14、算法思想该程序的算法思，从整个算法来看，是先求出原字符串和逆序字符串的最大公共序列长度，用原字符串的长度减去原字符串和逆序字符串的最大公共序列长度。而该程序的关键是求出原字符串和逆序字符串的最大公共序列长度。其算法思想是：(1)建立一个二维数组LCS，用于存放记录最长公共序列长度。(2)可以将这个二维数组看做是一个表格，初始化表格的第一行和第一列为0(

5、3)从上向下、从左到右填充表格，每个单元格包含一个数字，代表该行和该列之前的两个字符串的LCS的长度。(4)当比较的两个字符元素相同时，在它们的右下侧的那个单元格的值等于该单元格的值加一;如果不相同，则取该行右侧、该列下侧那个单元格的最大值。因为任何单元格中的数字都是该单元格所在行之上和列之前的字符串的LCS长度。所以，表格右下角的数字就是原字符串和逆序字符串的LCS的长度。5、详细设计和主要编码段1，字符串倒置函数伪代码：voiddaozhi(chara[],charb[],intlen){inti;for(i

6、=0;i

7、][j-1]+1;else{if(LCS[i-1][j]>=LCS[i][j-1])LCS[i][j]=LCS[i-1][j];elseLCS[i][j]=LCS[i][j-1];}}}returnLCS[m][n];}3，整个函数流程图如下图2所示：图24，计算原字符串与逆字符串最大公共序列长度流程图如下图3示：图36、上机调试情况记录1，在while循环语句处，输入选择选项语句“scanf("%d",&ch)”时，把地址符弄丢，虽然系统不提示错误，但在运行过程中不能正常运行，导致出错。2，计算公共序列长度函数

8、函数length在定义时定义错误的定义为void型，而结果却返回的时int型，出现错误提示如下图4所示：图47、测试用例、结果及其算法性能分析1，测试数据：（a）输入的字符串为：abacdbac（b）输入的字符串为：abcddcba（c）输入的字符串为：abcdefghijk2，测试用例如下图5示：图53，算法性能分析字符串倒置函数只有一个for循环语句，所以它的时间复杂