Редактировать матрицу расстояний
Я пытаюсь построить программу, которая принимает две строки и заполняет матрицу расстояния редактирования для них. Меня сбивает с толку то, что для второго строкового ввода он пропускает второй вход. Я попытался очистить буфер с помощью getch(), но это не сработало. Я также попытался переключиться на scanf(), но это также привело к некоторым сбоям. Помогите, пожалуйста!
Код:
#include <stdio.h>
#include <stdlib.h>
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;
}
1 ответ
Придерживаться fgets,
Как уже отмечали другие, используйте char input1[100] вместо char *input1 = malloc(...)
Но даже с этим изменением, которое делает sizeof внутри fgets правильно, используя sizeof при настройке len1 а также len2 неправильно. Вы будете обрабатывать весь буфер из 100, даже если в нем всего 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;
}
ОБНОВИТЬ:
Хорошо, сладкий, я понимаю, что ты имеешь в виду! Причина, по которой я пытался использовать malloc, заключалась в том, чтобы избежать создания матрицы, в которой мне приходилось печатать пробелы размером 100x100.
Либо с фиксированным размером input1 или malloc ред один, fgets заполнит его только до введенного размера ввода [обрезает до второго аргумента, если необходимо]. Но он не заполняет / не заполняет оставшуюся часть буфера чем-либо (например, пробелами справа). Что он делает, так это добавляет символ EOS [конец строки] [который является двоичным 0x00] после последнего чтения символа из ввода [который обычно является новой строкой].
Таким образом, если входная строка: abcdef\n длина [получается из strlen ] равно 7, вход [7] будет 0x00, и input1[8] через input1[99] будет иметь неопределенные / случайные / непредсказуемые значения, а не пробелы.
Поскольку символ перевода строки не очень полезен, его часто удаляют перед дальнейшей обработкой. Например, это не очень важно при расчете расстояния редактирования для маленькой фразы.
Использует ли 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 включить [внутренние / встроенные] пробелы в расчет длины. Это потому, что совершенно правильно вычислить расстояние редактирования фраз.
Есть допустимое использование для malloc: когда объем данных слишком велик для размещения в стеке. Большинство систем имеют ограничение по умолчанию (например, в Linux это 8 МБ).
Предположим, что мы вычисляли расстояние редактирования для двух глав книги [прочитанных из файлов], у нас было бы (например):
char input1[50000];
char input2[50000];
Вышеупомянутое соответствовало бы, но c матрица вызовет переполнение стека:
int c[50000][50000];
потому что размер этого будет 50000 * 50000 * 4 что составляет около 9,3 ГБ.
Итак, чтобы уместить все эти данные, нам нужно было бы разместить их в куче. Пока можно сделать malloc за c и поддерживать доступ к 2D матрице, мы должны создать функцию и передать указатель на c к этому.
Итак, вот модифицированная версия, которая принимает ввод произвольно больших размеров:
#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;
}