编辑距离矩阵
我正在尝试构建一个程序，它需要两个字符串并填充它们的编辑距离矩阵。 绊倒我的是，对于第二个字符串输入，它正在跳过第二个输入。 我尝试用getch（）清除缓冲区，但它没有用。 我也尝试过切换到scanf（），但这也导致了一些崩溃。 请帮忙！
码：
#include #include int min(int a, int b, int c){ if(a > b && a > c) return a; else if(b > a && b > c) return b; else return c; } int main(){ // allocate size for strings int i, j; char *input1 = (char*)malloc(sizeof(char)*100); char *input2 = (char*)malloc(sizeof(char)*100); // ask for input printf("Enter the first string: "); fgets(input1, sizeof(input1), stdin); printf("\nEnter the second string: "); fgets(input2, sizeof(input2), stdin); // make matrix int len1 = sizeof(input1), len2 = sizeof(input2); int c[len1 + 1][len2 + 1]; // set up input 2 length for(i = 0; i < len2 + 1; i++){ c[0][i] = i; } // set up input 1 length for(i = 0; i < len1 + 1; i++){ c[i][0] = i; } // fill in the rest of the matrix for(i = 1; i < len1; i++){ for(j = 1; j < len2; j++){ if(input1[i] == input2[j]) // if the first letters are equal make the diagonal equal to the last c[i][j] = c[i - 1][j - 1]; else c[i][j] = 1 + min(c[i - 1][j - 1], c[i - 1][j], c[i][j - 1]); } } // print the matrix printf("\n"); for(j = 0; j < len2; j++){ for(i = 0; i < len1; i++){ printf("| %d", c[i][j]); } printf("\n"); } return 1; } 坚持fgets 。
正如其他人所指出的，使用char input1[100]而不是char *input1 = malloc(...)
但是，即使有这种改变，这使得fgets内部的sizeof正确，在设置len1和len2时使用sizeof是错误的。 您将处理100的整个缓冲区，即使它们只有10个有效字符（即其余的未定义/随机）。
您[可能]想要的是strlen [和换行条]以获得实际有用的长度。
这是修改后的代码[请原谅无偿风格的清理]：
#include #include #include int min(int a, int b, int c) { if (a > b && a > c) return a; if (b > a && b > c) return b; return c; } int main(void) { // allocate size for strings int i; int j; char input1[100]; char input2[100]; // ask for input printf("Enter the first string: "); fgets(input1, sizeof(input1), stdin); int len1 = strlen(input1); if (input1[len1 - 1] == '\n') { input1[len1 - 1] = 0; --len1; } printf("\nEnter the second string: "); fgets(input2, sizeof(input2), stdin); int len2 = strlen(input2); if (input2[len2 - 1] == '\n') { input2[len2 - 1] = 0; --len2; } // make matrix int c[len1 + 1][len2 + 1]; // set up input 2 length for (i = 0; i < len2 + 1; i++) { c[0][i] = i; } // set up input 1 length for (i = 0; i < len1 + 1; i++) { c[i][0] = i; } // fill in the rest of the matrix for (i = 1; i < len1; i++) { for (j = 1; j < len2; j++) { // if the 1st letters are equal make the diagonal equal to the last if (input1[i] == input2[j]) c[i][j] = c[i - 1][j - 1]; else c[i][j] = 1 + min(c[i - 1][j - 1], c[i - 1][j], c[i][j - 1]); } } // print the matrix printf("\n"); for (j = 0; j < len2; j++) { for (i = 0; i < len1; i++) { printf("| %d", c[i][j]); } printf("\n"); } return 1; }
更新：
好的，我明白你的意思！ 我试图使用malloc的原因是为了避免制作我必须打印100x100空格大小的矩阵。
对于固定大小的input1或malloc ed， fgets只会将其填充到输入的输入大小[必要时剪裁到第二个参数]。 但是，它不会用任何东西填充/填充缓冲区的其余部分（例如右边的空格）。 它做的是在从输入读取的最后一个char [通常是换行符]之后添加一个EOS [字符串结束]字符[这是一个二进制0x00]。
因此，如果输入字符串是： abcdef\n ，则[可从strlen获得]的长度为7，输入[7]将为0x00，而input1[8]到input1[99]将具有未定义/随机/不可预测的值，而不是空间。
由于换行符char不是非常有用，因此在进一步处理之前通常会将其删除。 例如，在计算小短语的编辑距离时，它并不十分相关。
使用strlen（）只计算数组中的字符数，还是包含所有空格？
正如我上面提到的， fgets不会在最后填充字符串，所以，不用担心。 它会做你想要/期望的事情。
strlen只计算字符数[但不包括EOS终止符字符（即）为零]。 如果其中一些字符碰巧是空格，那么它们将被strlen计算 - 这就是我们想要的。
考虑计算以下任意两个短语之间的编辑距离：
quick brown fox jumped over the lazy dogs the quick brown fox jumped over lazy dogs quick brown fox jumps over the lazy dog
在每种情况下，我们希望 strlen在长度计算中包含[internal / embedded]空格。 那是因为计算短语的编辑距离是完全有效的。
malloc有一个有效的用法：当数据量太大而无法放入堆栈时。 大多数系统都有默认限制（例如在linux下，它是8 MB）。
假设我们计算了两本书章节的编辑距离[从文件中读取]，我们有（例如）：
char input1[50000]; char input2[50000];
以上适合，但c矩阵会导致堆栈溢出：
int c[50000][50000];
因为它的大小是50000 * 50000 * 4 ，大约是9.3 GB。
因此，为了适应所有这些数据，我们需要在堆上分配它。 虽然可以为c执行malloc 并维护2D矩阵访问，但我们必须创建一个函数并将指向c的指针传递给它。
所以，这是一个修改版本，可以输入任意大的尺寸：
#include #include #include #include #define sysfault(_fmt...) \ do { \ fprintf(stderr,_fmt); \ exit(1); \ } while (0) #define C(y,x) c[((y) * (len2 + 1)) + (x)] long min(long a, long b, long c) { if (a > b && a > c) return a; if (b > a && b > c) return b; return c; } char * input(const char *prompt,long *lenp,const char *file) { FILE *fp; char *lhs; int chr; long siz; long len; if (file != NULL) fp = fopen(file,"r"); else { fp = stdin; printf("Enter %s string: ",prompt); fflush(stdout); } lhs = NULL; siz = 0; len = 0; while (1) { chr = fgetc(fp); if (chr == EOF) break; if ((chr == '\n') && (file == NULL)) break; // grow the character array if ((len + 1) >= siz) { siz += 100; lhs = realloc(lhs,siz); if (lhs == NULL) sysfault("input: realloc failure -- %s\n",strerror(errno)); } lhs[len] = chr; len += 1; } if (file != NULL) fclose(fp); if (lhs == NULL) sysfault("input: premature EOF\n"); // add the EOS lhs[len] = 0; // return the length to the caller *lenp = len; return lhs; } int main(int argc,char **argv) { long i; long j; char *input1; long len1; char *input2; long len2; long *c; --argc; ++argv; switch (argc) { case 2: input1 = input("first",&len1,argv[0]); input2 = input("second",&len2,argv[1]); break; default: input1 = input("first",&len1,NULL); input2 = input("second",&len2,NULL); break; } // make matrix c = malloc(sizeof(*c) * (len1 + 1) * (len2 + 1)); if (c == NULL) sysfault("main: malloc failure -- %s\n",strerror(errno)); // set up input 2 length for (i = 0; i < len2 + 1; i++) { C(0,i) = i; } // set up input 1 length for (i = 0; i < len1 + 1; i++) { C(i,0) = i; } // fill in the rest of the matrix for (i = 1; i < len1; i++) { for (j = 1; j < len2; j++) { // if the 1st letters are equal make the diagonal equal to the last if (input1[i] == input2[j]) C(i,j) = C(i - 1,j - 1); else C(i,j) = 1 + min(C(i - 1,j - 1), C(i - 1,j), C(i,j - 1)); } } // print the matrix printf("\n"); for (j = 0; j < len2; j++) { for (i = 0; i < len1; i++) { printf("| %ld", C(i,j)); } printf("\n"); } return 1; }