Цикл For создает ошибку при рекурсивли перестановки строк в C - PullRequest
Новая
       7

Цикл For создает ошибку при рекурсивли перестановки строк в C

0 голосов
/ 24 января 2019

Я новичок в C и пытаюсь написать функцию, которая возвращает все перестановки подмножества размера k строки, используя рекурсию.Например, для строки 'abc' и k = 1 я бы получил 'a', 'b' и 'c', для k = 2 я бы получил 'aa', 'ab', 'ac', 'ba',' bb ',' bc ',' ca ',' cb 'и' cc 'и так далее.

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

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

#define CHARS "abc"

char *recur(char* prefix, int k, int n);

int main(void)
{     
    int k = 2; //for example
    int n = strlen(CHARS); //set n as length of CHARS
    //print string generated by recur
    printf("string: %s\n", recur("", k, n));
}

char *recur(char *prefix, int k, int n)
{
    //if base case (have already added all letters), return string
    if (k == 0)
    {
        return prefix;
    }
    //otherwise, add character from CHARS to string
    else
    {
        for (int i = 0; i < n; i++)
        {
            // for each letter in CHARS, make a new prefix and add a letter from chars to it
            int prefLen = strlen(prefix);
            char newPrefix[prefLen + 2];
            strcpy(newPrefix, prefix);
            newPrefix[prefLen] = CHARS[i];
            newPrefix[prefLen + 1] = '\0';
            return recur(newPrefix, k-1, n);
        }
    }
}

Однако я получаю сообщение об ошибке 'recur1.c: 40: 1: ошибка: элемент управления может достигнуть конца недействительной функции [-Werror, -Wreturn-type]'при попытке скомпилировать.

Чтобы изучить это немного подробнее, я удалил цикл for, который приводит к обращенной строке: 

char *recur(char *prefix, int k, int n)
{
    //if base case (have already added all letters), return string
    if (k == 0)
    {
        return prefix;
    }
    //otherwise, add character from CHARS to string
    else
    {
        //make a new array called newPrefix, copy current prefix into it and add new letter from CHARS
        int prefLen = strlen(prefix);
        char newPrefix[prefLen + 2];
        strcpy(newPrefix, prefix);
        newPrefix[prefLen] = CHARS[k-1];
        newPrefix[prefLen + 1] = '\0';
        return recur(newPrefix, k-1, n);
    }
}

После замены этой второй функции код компилируется без каких-либо проблем.Есть идеи, почему версия с циклом for не компилируется?

Ответы [ 2 ]

0 голосов
/ 24 января 2019

Если n <= 0, то цикл for никогда не будет введен, и, таким образом, оператор return в теле цикла никогда не будет достигнут. Поскольку после цикла нет оператора return, компилятор жалуется (правильно).

Тем не менее, вы уверены, что не является ошибкой иметь безусловный оператор return внутри тела цикла? Это делает цикл совершенно бесполезным.

0 голосов
/ 24 января 2019

Если i < n равно 0 при обнаружении for (int i = 0; i < n; i++), управление программой не вводит тело цикла for, а оператор return не достигается. Должен ли оператор return действительно находиться в теле цикла for?

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

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

...