字符串相似度实验….docx
文本预览下载声明
数据结构实验报告二——字符串相似度
实验题目：求字符串的相似度
实验目标：
实现两字符串比较，输出字符串比较对应的矩阵、两字符串的长度、最大公共子串及其长度，并用“相似度=最大公共子串的长度/两字符串中较短者的长度”这一公式求出两字符串的相似度。
数据结构：
字符串和数组（二维）。字符串采用静态顺序存储（数组空间），二维数组则实现了字符串比较矩阵mat。
需要的操作有：求字符串长度（strlen）（函数库string.h包含），从字符串string2的pos位置开始复制len个字符形成字符串（stringncopy）（函数库string.h不包含）
算法设计：
一、核心思路(getmaxsamestr)
建立矩阵mat[alen][blen]（alen，blen分别为字符串st1，st2的长度），对其中元素mat[i][j]，若st[i]与st[j]相同，则mat[i][j]赋值为1，否则赋值为0。
求出矩阵mat中对角线方向最长连续1的长度maxlen和起点的j坐标jpos（利用diagmax函数）。
根据2的结果，利用stringncopy函数（从字符串string2的pos位置开始复制len个字符形成字符串）得到最大公共子串，计算出相似度。
二、diagmax函数(求出矩阵mat中对角线方向最长连续1的长度maxlen和起点的j坐标jpos)
void diagmax(int mat[MAX][MAX],int m,int n,int *maxlen,int *jpos)
{
/*求矩阵mat中对角线方向上连续1的最长长度maxlen和起点的j坐标jpos*/
int istart=0,i=0,j=0,k=0;
*maxlen=0;
*jpos=-1;/*右上的第一条对角线起始行坐标*/
for(k=-(n-1);k=m-1;k++)/*当前处理特征量k的对角线，k=i-j*/
{
i=istart;
j=i-k;
diagscan(mat,m,n,i,j,maxlen,jpos);/*扫描特征量为k的对角线连续1的最长段*/
istart+=(k=0)?1:0;/*k〉=0时，istart开始增加*/
}
}
三、diagscan函数（扫描一条确定位置的对角线连续1的最长段）
void diagscan(int mat[MAX][MAX],int m,int n,int i,int j,int *maxlen,int *jpos)
{
/*从[i，j]开始沿对角线方向扫描最长的连续1，maxlen和jpos分别返回最长连续1的长度和起点的j坐标*/
int eq=0,len=0,sj=0;
while(imjn)
{
if(mat[i][j]==1)
{
len++;
if(!eq)/*第一个出现的1*/
{
eq=1;
sj=j;/*改变状态，记下当前位置*/
}
}
else if(eq)/*上一个连续1结束*/
{
if(len*maxlen)/*目前???得的连续1最长*/
{
*maxlen=len;
*jpos=sj;
}
eq=0;
len=0;/*重新开始下一个连续1的扫描*/
}
i++;
j++;
}
if(len*maxlen)/*一个长连续1到达边界而没碰到下一个0*/
{
*maxlen=len;
*jpos=sj;
}
}
源程序：
#includestdio.h
#includestdlib.h
#includestring.h
#define MAX 100
void stringncopy(char *string1,char *string2,int pos,int len);
void diagscan(int mat[MAX][MAX],int m,int n,int i,int j,int *maxlen,int *jpos);
void diagmax(int mat[MAX][MAX],int m,int n,int *maxlen,int *jpos);
void getmaxsamestr(char *string1,char *string2,char *sub);
int minlen(int len1,int len2);
main()
{
int alen,blen,minl,maxpub;
char st1[MAX],st2[MAX],maxsub[MAX];
float sim;
printf(input string1.\n);
scanf(%s,st1);
alen=st
显示全部