《【2017年整理】字符串冗余编辑距离实验报告》由会员分享，可在线阅读，更多相关《【2017年整理】字符串冗余编辑距离实验报告（10页珍藏版）》请在金锄头文库上搜索。
1、科 技 学 院课程设计(综合实验)报告( 2016 - 2017 年度第 1 学期)题 目：字符串的冗余编辑距离实验 院 系： 班 级： 学 号： 141909030130 学生姓名： 薛鹏 指导教师： 成 绩： 2016 年 11 月一、 设计内容有两个字符串，要用最少的字符操作将一个字符串转换为另一个字符串（字符操作：删除一个字符串；插入一个字符串；将一个字符改为另一个字符），将一个字符串变为另一个字符串所用最少字符操作数成为一个字符串到另一个字符串的编辑距离。字符串由字母，数字，中文组成实现数字 09 与中文零九是相等的，编辑距离为 0；二数据描述 两个字符串: str1,str2;字符
2、串的长度: max1,max2;用于计算与保存编辑距离矩阵的一维数组: ptr ,长度为: (max1+1)*(max2+1)编辑距离: dis = ptr(max1+1)*(max2+1)-1三功能描述以及实现/ 函数说明 / 类型：整型/参数：传值类型的整型参数，代表取最小值的两个操作数/功能： 求两个参数之间的最小值将最小的参数的值返回 int min(int a, int b)return a b ? a : b;/ 函数说明 / 类型：整型/参数：传值类型的字符串参数，代表求字符串长度的操作字符串 /功能： 求字符串的长度然后返回长度的值 int size(string s)int
3、j=0;/计数器，用于记录字符串的长度 for(int i=0;is.length();i+) if(si0)/当 si小于零代表当前指针 i 指向的是中文的第一个字符/计数器累加 /指针 i 加一跳过中文的第二个字符指向下一个中文或者字母 j+;i+;else/si大于零，当前指针指向的是字母或者数字 /计数器累加 j+;return j;/ 函数说明 / 类型：整型/参数：两个传值类型的字符串型参数，分别代表需要比较的两个字符串 /功能：求两个参数之间进行比较，主要是进行数字 09 和汉字零九作比较，相同则返回1，否则返回 0/ 例 ：1 与一返回值为 1，2 与一返回值为 0 int c
4、ompare(string s1,string s2)if(s1.length()=(s2.length() /比较两个字符串的长度是否相等 ，/相等则是西文与西文或者中文与中文之间的比较 if(s1=s2)/两个字符串相等返回 1，否则返回零 return 1;else return 0;else /两个字符串长度不相等 if(s1.length()=2)/第一个字符串长度为二，表示此字符串为中文/进行比较if(s1=一)if(s2=1)return 1;else return 0;else if(s1=二)if(s2=2)return 1;else return 0;else if(s1=
5、三)if(s2=3)return 1;else return 0;else if(s1=四)if(s2=4)return 1;else return 0;else if(s1=五)if(s2=5)return 1;else return 0;else if(s1=六)if(s2=6)return 1;else return 0;else if(s1=七)if(s2=7)return 1;else return 0;else if(s1=八)if(s2=8)return 1;else return 0;else if(s1=九)if(s2=9)return 1;else return 0;els
6、e if(s1=零)if(s2=0)return 1;else return 0;else /第一个字符串在一九范围之外 /进行直接比较 if(s1=s2)return 1;else return 0;else/第二个字符串长度为二，表示此字符串为中文/进行比较if(s2=一)if(s1=1)return 1;else return 0;else if(s2=二)if(s1=2)return 1;else return 0;else if(s2=三)if(s1=3)return 1;else return 0;else if(s2=四)if(s1=4)return 1;else return
7、0;else if(s2=五)if(s1=5)return 1;else return 0;else if(s2=六)if(s1=6)return 1;else return 0;else if(s2=七)if(s1=7)return 1;else return 0;else if(s2=八)if(s1=8)return 1;else return 0;else if(s2=九)if(s1=9)return 1;else return 0;else if(s1=零)if(s2=0)return 1;else return 0;else/第一个字符串在一九范围之外 /进行直接比较 if(s1=s
8、2)return 1;else return 0;/ 函数说明 / 类型：字符串 /参数：传值类型的字符串参数和整数类型参数，代表求字符串第几个字符的字符串和位数 /功能： 求字符串第 x 位的字符（数字，字母，中文） ，返回第 x 位的字符 string getstr(string str,int x)int j=0;/累加器，用于记录第 x 位的字符在字符串里的真实的位置 for(int i=0;ix;i+)if(strj0)/当 strj小于零代表当前指针 i 指向的是中文的第一个字符/计数器累加 /指针 j 加一跳过中文的第二个字符指向下一个中文或者字母 j+;j+;else/sj大于
9、零，当前指针指向的是字母或者数字 /计数器累加 j+;string s;/用于存储第 x 位的字符 if(strj0)/如果找到真实位置 j 为负代表应该提取一个中文 s = str.substr(j,2);/用于提取字符串子串的函数/第一个参数为要提取的子串第一个的位置 /第二个参数为要提取第一个参数的后几位 /返回值为 string 类型 else/否则代表应该提取一个西文 s = str.substr(j,1);return s;/返回提取的字符串 / 函数说明 / 类型：整型/参数：两个传值类型的字符串参数，代表求字符串之间编辑距离的字符串 /功能： 求字符串的之间的编辑距离，返回求得
10、的编辑距离 int edit(string str1, string str2)int max1 = size(str1);/第一个字符串的长度 int max2 = size(str2);/第二个字符串的长度 int i;/用于循环 int *ptr = new int (max1+1)*(max2+1);/用于保存编辑距离矩阵的数组，用一维数组代替二维数组 for(i = 0;imax1+1;i+)/向矩阵第一列赋值 ptr(i*(max2+1)=i;for(i=0;imax2+1;i+)/ 矩阵第一行赋值 ptri = i;for(i = 1 ;i max1 + 1 ;i+)for(in
11、t j = 1 ;j max2 + 1; j+)/矩阵第 i 列，j 行赋值 string s1 = getstr(str1,(i-1);/获得第一个字符串第 i-1 个字符 string s2 = getstr(str2,(j-1);/获取第二个字符串第 j-1 个字符 int d; / 保存两个字符串提取的字符比较之后得到的值 相等为 0；不等为1 int temp = min(ptr(i-1)*(max2+1)+j)+1,ptr(i)*(max2+1)+j-1)+1);/将矩阵当前位置的左边上边的数值进行比较，取较小的值 if(compare(s1,s2)/比较两个字符串提取的字符 d
12、= 0 ;elsed = 1 ;ptr(i*(max2+1)+j) = min(temp, ptr(i-1)*(max2+1)+j-1) + d);/ 矩阵当前位置与其左上角加 d 作比较，取较小的值 cout * endl;for(i = 0 ;i max1 + 1 ;i+)for(int j = 0; j max2 + 1; j+)/输出矩阵 cout ptr(i*(max2+1)+j) ;cout endl;cout * endl;int dis = ptr(max1+1)*(max2+1)-1;/取得编辑距离 delete ptr;/删除数组 return dis;/返回编辑距离 四.运行效果五、课程实验总结或结论本次实验困难在于把实现求取字符串长度的函数与提取字符串某位的字符与使用一维数组代替二维数组六、参考文献1 作者：王晓东 书名：计算机算法设计与分析. 出版单位：电子工业出版社 , 版本：第四版. 出版日期：2014.6
