字符串.cpp

数据结构试验

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXLEN 2000
#define MAXINT 1000000
int Compute_Distance(char str1,char str2)
{
	return (int)str1 > (int)str2 ? (str1-str2):(str2-str1);
}
int Compare_str(char *str1,char *str2,int k)
{
	int len1,len2,i,j,temp;
	int **val;
	len1=strlen(str1);
	len2=strlen(str2);
	val=new int * [len1+1];
	for(i=0;i<len1+1;i++)
		val[i]=new int[len2+1];
	val[0][0]=0;
	for(i=0;i<=len1;i++)
		for(j=0;j<=len2;j++)
			if(i+j)
			{
				val[i][j]=MAXINT;
				if((i*j)&&(temp=val[i-1][j-1]+Compute_Distance(str1[i-1],str2[j-1]))<val[i][j])
					val[i][j]=temp;
				if(i&&(temp=val[i-1][j]+k)<val[i][j])
					val[i][j]=temp;
				if(j&&(temp=val[i][j-1]+k)<val[i][j])
					val[i][j]=temp;
			}
	return val[len1][len2];
}
void main()
{
	FILE *fp,*fw;
	char *str1,*str2;
	int k;
    if((fp=fopen("input.txt","r"))==NULL)
	{ 
	printf("Cann't open this file!\n");
	exit(0);
	}
	str1=new char[MAXLEN];
	str2=new char[MAXLEN];
	printf("第一个字符串为：");
    fgets(str1,MAXLEN,fp);
	puts (str1); 
	printf("第二个字符串为：");
	fgets(str2,MAXLEN,fp);
	puts (str2); 
    printf("空格与其它字符的距离为："); 
	fscanf(fp,"%d",&k);
    printf("%d\n",k);
	printf("其扩展距离: ");
	printf("%d",Compare_str(str1,str2,k));
	printf("\n");
	fw=fopen("output.txt","w");
	fprintf(fw,"%d\n",Compare_str(str1,str2,k));
	printf("\n");
	printf("实验结果已写入到文件output.txt中，请查收！");
	printf("\n");
	
}