【DP】 Shortest Edit Distance in C

很不幸，一个晚上都在调试一个程序，本来是在TC2.0环境下写的，结果算法有逻辑错误，程序运行结果总是出错。为了赶时间还是回到VC下进行调试，才发现二年多没用淡出的C语言，好多函数都用错了。

1：将malloc函数与new函数的用法等价了 malloc函数分配的内存是以字节为单位，而new是以数据类型为单位，例如要分配一个大小为N的整形数组，用malloc函数应该是int* pInt = (int*)malloc(N * sizeof(int));而我居然写成了这样……malloc(N)……,结果每次函数运行完毕释放内存时就出错，但就是找不到原因，我狂汗。。。这个小小的错误却让我debug了大半个小时。

2：min()/max()原来是C语言自定义的宏，之前在VC环境下我写了以个min函数，用以判断三个数种的最小数，跑的很ok的代码，贴到TC2.0以后却频繁报错，总是提示说the number of arguments in min function is error，反复检查了min函数N久也发现为什么参数数目为错，最终被我发现原来min()是C语言的自定义宏，汗-_-||

用C实现的最短编辑距离（TC2.0环境下调试通过）

DP思想见《算法概论》（中文版）P177

附代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int diff(char ch1, int ch2)
{
	return ch1 != ch2;
}

int Min(int a, int b, int c)
{
	if (a <= b)
	{
		return a < c ? a : c;
	}
	else if (a <= c)
	{
		return a < b ? a : b;
	}
	return b < c ? b : c;
}



int SED(char* ch1, char* ch2, int m, int n)
{
	int i, j;
	int a, b, c;
	int shortest_edit_distance = 0;
	int** E = (int**)malloc((m + 1) * sizeof(int*));
	for (i = 0; i<= m; i++)
	{
		E[i] = (int*)malloc((n + 1) * sizeof(int));
	}
	for (i = 0; i <= m; i++)
	{
		E[i][0] = i;
	}
	for (i = 0; i <= n; i++)
	{
		E[0][i] = i;
	}


	for (i = 0; i< m; i++)
	{
		for (j = 0; j < n; j++)
		{
			a = E[i][j] + diff(ch1[i], ch2[j]);
			b = E[i][j + 1] + 1;
			c = E[i + 1][j] + 1;
			E[i + 1][j + 1] = Min(a, b, c);
		}
	}

	shortest_edit_distance =  E[m][n];
	for (i = 0; i <= m; i++)
	{
		free((void*)E[i]);
	}
	free(E);
	return shortest_edit_distance;
}


int main()
{

	/*char* str1 = "EXPONENTIAL";*/
	/*char* str2 = "POLYNOMIAL";*/
	char str1[100], str2[100];
	int m = 0;
	int n = 0;
	int shortest_edit_distance = 0;
	printf("Please input two string specified by enter/nThe first string: ");
	scanf("%s", str1);
	printf("The second string: ");
	scanf("%s", str2);
	m = strlen(str1);
	n = strlen(str2);
	shortest_edit_distance = SED(str1, str2, m, n);
	printf("The shortest edit distance is %d /n", shortest_edit_distance);
	getche();
	return 0;
}