Правильный алгоритм, но неправильная реализация?

Question

Я новичок в C с некоторым опытом работы с Python и Java. Я хочу решить проблему с C. Проблема выглядит следующим образом:

Возьмите ввод как предложение со словами, разделенными только пробелами (только в нижнем регистре), перепишите предложение со следующими правилами:

1) Если слово встречается в первый раз, оставьте его таким же.

2) Если слово встречается дважды, замените второе вхождение словом, которое копируется дважды (например, два --> twotwo).

3) Если слово встречается три раза или более, удалите все вхождения после второго.

Распечатайте вывод как предложение. Максимальная длина входного предложения и каждого отдельного слова составляет 500 символов и 50 символов.

Примерный ввод: jingle bells jingle bells весь путь jingle

Примерный вывод: jingle bells jinglejingle bells всеway

Подход, который я выбрал:

1) Прочитать ввод, отделить каждое слово и поместить их в массив указателей символов.

2) Использовать вложенный цикл forпройти через массив. Для каждого слова после первого слова:

 A - If there is no word before it that is equal to it, nothing happens.

 B - If there is already one word before it that is equal to it, change the word as its "doubled form".

 C - If there is already a "doubled form" of itself that exists before it, delete the word (set the element to NULL.

3) Вывести измененный массив.

Я довольно уверен в правильности этого подхода. Однако, когда я на самом деле написал код:

'' '

int main()
{

    char input[500];

    char *output[500];


    // Gets the input
    printf("Enter a string: ");
    gets(input);

    // Gets the first token, put it in the array
    char *token = strtok(input, " ");
    output[0] = token;

    // Keeps getting tokens and filling the array, untill no blank space is found
    int i = 1;
    while (token != NULL) {
        token = strtok(NULL, " ");
        output[i] = token;
        i++;
    }


    // Processes the array, starting from the second element
    int j, k;
    char *doubled;
    for (j = 1; j < 500; j++) {
        strcpy(doubled, output[j]);      
        strcat(doubled, doubled);        // Create the "doubled form"
        for (k = 0; k < j; k++) {
            if (strcmp(output[k], output[j]) == 0) {     // Situation B
                output[j] = doubled;
            }
            if (strcmp(output[k], doubled) == 0) {       // Situation C
                output[j] = ' ';
            }
        }
    }


    // Convert the array to a string
    char *result = output[0];          // Initialize a string with the first element in the array     
    int l;
    char *blank_space = " ";           // The blank spaces that need to be addded into the sentence
    for (l = 1; l < 500; l++) {
        if (output[l] != '\0'){        // If there is a word that exists at the given index, add it
            strcat(result, blank_space);
            strcat(result, output[l]);

        }
        else {                         // If reaches the end of the sentence
            break;
        }
    }

    // Prints out the result string
    printf("%s", result);

    return 0;
}

' ''

, я выполнил несколько тестов для каждого отдельного блока. Есть несколько проблем:

1) При обработке массива strcmp, strcat и strcpy в цикле, похоже, выдают сообщения об ошибках сегментации.

2) При печати массива словане показывал порядок, который они должны делать.

Теперь я разочарован, потому что кажется, что все проблемы происходят из-за некоторых внутренних структурных дефектов моего кода, и они очень тесно связаны с механизмом памятиС, с которым я не очень знаком. Как мне это исправить?

Answer 1

Ваш код вызывает неопределенное поведение в нескольких местах путем записи в память, которая еще не принадлежит, и, вероятно, является причиной ошибки сегментации вы видите. Например, в этом сегменте:

char *result = output[0];          // Initialize a string with the first element in the array     
    int l;
    char *blank_space = " ";           // The blank spaces that need to be addded into the sentence
    for (l = 1; l < 500; l++) {
        if (output[l] != '\0'){        // If there is a word that exists at the given index, add it
            strcat(result, blank_space);
            strcat(result, output[l]);

Сам по себе ...

char *result = output[0]; //creates a pointer, but provides no memory.

... недостаточно для получения контента, такого как

strcat(result, blank_space);
 strcat(result, output[l]);  

Нужна память:

char *result = malloc(501);//or more space if needed.
if(result)
{
    //now use strcat or strcpy to add content

Answer 2

strspn и strcspn могут использоваться для перебора входной строки.
strstr может использоваться для поиска подстроки.

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

#define SIZE 500

int main ( void) {
    char input[SIZE] = "";
    char substring[SIZE] = "";
    char subspace[SIZE] = "";
    char output[SIZE * 2] = "";//twice as big as
    char *match = NULL;
    size_t offset = 0;
    size_t span = 0;
    size_t space = 0;

    printf("Enter a string: ");
    if ( ! fgets ( input, sizeof input, stdin)) {
        fprintf ( stderr, "fgets problem\n");
        return 0;
    }

    offset += strspn ( input + offset, " \n\t\r");//skip leading whitespace

    while ( input[offset]) {//not terminating zero
        span = strcspn ( input + offset, " \n\t\r");//include non-whitespace
        space = strspn ( input + offset + span, " \n\t\r");//include trailing whitespace
        strncpy ( substring, input + offset, span);
        substring[span] = 0;
        strncpy ( subspace, input + offset + span, space);
        subspace[space] = 0;
        if ( NULL == ( match = strstr ( output, substring))) {//did not find substring
            strcat ( output, substring);
            strcat ( output, subspace);
        }
        else {
            if ( NULL == ( match = strstr ( match + span, substring))) {//did not find substring the second time
                strcat ( output, substring);
                strcat ( output, substring);
                strcat ( output, subspace);
            }
        }
        offset += span + space;
    }

    printf ( "%s\n", output);


    return 0;
}

Answer 3

Один вопрос выскакивает у меня. Этот код неверен:

char *doubled;
for (j = 1; j < 500; j++) {
    strcpy(doubled, output[j]);      
    strcat(doubled, doubled);        // Create the "doubled form"

doubled не указывает на фактическую память. Поэтому попытка скопировать данные туда, куда они указывают, является неопределенным поведением и почти наверняка вызовет SIGSEGV - и это повредит память, если не вызовет SIGSEGV.

, которую необходимо исправить -Вы не можете скопировать строку с strcpy() или strcat() в указатель, который не указывает на фактическую память.

Это было бы лучше, но все же не идеально, так как не выполняется проверка, чтобы убедиться, что естьнет переполнения буфера:

char doubled[ 2000 ];
for (j = 1; j < 500; j++) {
    strcpy(doubled, output[j]);      
    strcat(doubled, doubled);        // Create the "doubled form"

Это также проблема с doubled, определенным так:

        if (strcmp(output[k], output[j]) == 0) {     // Situation B
            output[j] = doubled;
        }

Это просто указывает output[j] на doubled. Следующая итерация цикла перезапишет doubled, и данные, на которые output[j] все еще указывает, будут изменены.

Это решит эту проблему:

        if (strcmp(output[k], output[j]) == 0) {     // Situation B
            output[j] = strdup( doubled );
        }

strdup() isфункция POSIX, которая, что неудивительно, дублирует строку. Эта строка должна быть free() позже, хотя strdup() совпадает с:

char *strdup( const char *input )
{
    char *duplicate = malloc( 1 + strlen( input ) );
    strcpy( duplicate, input );
    return( duplicate );
}

Как указывалось, strcat(doubled, doubled); также является проблемой. Одно из возможных решений:

    memmove(doubled + strlen( doubled ), doubled, 1 + strlen( doubled ) );       

Копирует содержимое строки doubled в память, начиная с исходного терминатора '\0'. Обратите внимание, что, поскольку исходный терминатор '\0' является частью строки, вы не можете использовать strcpy( doubled + strlen( doubled ), doubled );. Вы также не можете использовать memcpy() по той же причине.