坚持fgets
.
正如其他人指出的那样,使用char input1[100]
代替char *input1 = malloc(...)
但是,即使有了这样的变化,这使得sizeof
里面的fgets
正确,使用sizeof
设置时len1
and len2
是错的。您将处理一个entire100 个缓冲区,即使其中只有 10 个有效字符(即其余字符未定义/随机)。
你[可能]想要的是strlen
[和换行符] 以获得实际有用的长度。
这是修改后的代码[请原谅无偿的风格清理]:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
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;
}
UPDATE:
好吧,亲爱的,我明白你的意思了!我尝试使用 malloc 的原因是为了避免制作必须打印 100x100 空格大小的矩阵。
与固定尺寸input1
or the malloc
ed one, fgets
只会将其填充到输入的输入大小[如有必要,剪裁到第二个参数]。但是,它确实not填充/填充缓冲区的剩余部分anything(例如右侧的空格)。什么does要做的就是在从输入读取的最后一个字符[通常是换行符]之后添加一个 EOS [字符串结束]字符[这是一个二进制 0x00]。
因此,如果输入字符串是:abcdef\n
,长度[可从strlen
] 为 7,输入[7] 将为 0x00,并且input1[8]
通过input1[99]
将具有未定义/随机/不可预测的值并且not spaces.
由于换行符不是很有用,因此通常在进一步处理之前将其删除。例如,在计算小短语的编辑距离时,它并不是非常相关。
使用 strlen() 是否只计算数组内的字符数,还是也包括所有空格?
正如我上面提到的,fgets
does not将字符串填充在end,所以,不用担心。它会做你想要/期望的事情。
strlen
只计算 [但是not包括 EOS 终止符(即零)]。如果其中一些字符恰好是空格,那么它们will被计算为strlen
——这就是我们想要的。
考虑计算以下任意两个之间的编辑距离phrases:
quick brown fox jumped over the lazy dogs
the quick brown fox jumped over lazy dogs
quick brown fox jumps over the lazy dog
在每种情况下,我们want strlen
在长度计算中包括[内部/嵌入]空格。那是因为它is计算短语的编辑距离完全有效。
有一个有效的用法malloc
:当数据量太大而无法放入堆栈时。大多数系统都有默认限制(例如在 Linux 下,为 8 MB)。
假设我们正在计算两本书章节的编辑距离[从文件中读取],我们会有(例如):
char input1[50000];
char input2[50000];
上面的内容是合适的,但是c
矩阵会导致堆栈溢出:
int c[50000][50000];
因为这个的大小是50000 * 50000 * 4
大约为 9.3 GB。
因此,为了容纳所有这些数据,我们需要将其分配在堆上。虽然可以做malloc
for c
and维护 2D 矩阵访问,我们必须创建一个函数并将指针传递给c
to it.
因此,这是一个修改版本,它接受任意大尺寸的输入:
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>
#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;
}