编写一个字谜解算器并获取分段错误以释放堆内存

Question

我在堆内存方面遇到了一些问题。我正在用 C 编写一些代码来解决单词谜题——（来自英国的一个名为 Countdown 的游戏）。游戏是给你 9 个字母，目标是尽可能拼出最长的单词。

如果我注释掉对 free() 的所有调用，我的代码就可以工作（尽管我还没有完全测试它），但是当我将 free 调用放入时，我会遇到分段错误。我有运行 valgrind 并收到类似 "Address 0x9cbe627 is 7 bytes inside a block of size 9 free'd" 和 "invalid read of size 1." 的错误消息

任何人都可以看看并解释发生了什么事吗？（下面给出代码）我将不胜感激！

/**
 * Program to solve word puzzles from the TV show Countdown. Asks for 9 
 * letters for input and then prints out the
 * maximum score and an example word of that score
 */

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

/*
 uses recursion to iterate over combinations of size "length" from 
 data[] of size "lengthData." Stores combinations generated in
 combination[] and permutations in permutation[]. For each combination  
 calls checkPermutations to iterate over all permutations
 of the combination checking against a dictionary for word matches   
 returning true if a match is found
 */
bool checkForWords(char data[], int lengthData, int length, char  
                   combination[], int lengthCombination, char permutation[]);

/**
  * takes in an array - (in practice combination[] from main()) and  
  * iterates through all the permutations of the array storing
  * generated permutations in permutation[] by using recursion. For   
  * each checks against a dictionary for word match. Returns true
  * when match is found
  */
bool checkPermutations(char data[], int lengthData, char permutation[],  
                       int lengthPermutation);

/**
 * takes an array of some length and an index and then retruns a  
 * pointer to an array on the heap that is the same but with the
 * elements at the index and to the left removed and then remaining 
 * elements "shifted down"
 */
char* removeLeftOfIndex(char data[], int lengthData, int index);

/**
 * takes an array of some length and index position and returns a    
 * pointer to an array on the heap that has the element removed
 * and remaining elements "shifted down"
 */
char* removeElementAtIndex(char data[], int lengthData, int index);

int main(void)
{
char letters[9];

// getting letters
for (int i = 0; i < 9; i++)
{
    printf("Please enter letter %i: ", i + 1);
    letters[i] = GetChar();
}

// formatting
printf("\n");


// iterating over the length of word to look for starting at 9 and  
   decrementing
for (int i = 9; i > 0; i--)
{
    char* data = malloc(9 * sizeof(char));
    char* permutation = malloc(10 * sizeof(char));
    char* combination = malloc(9 * sizeof(char));

    for (int j = 0; j < 9; j++)
        data[j] = letters[j];

    // checks to see if there is a word of length i
    if (checkForWords(data, 9, i, combination, i, permutation) == true)
    {   
        printf("Max score: %i\nExample word: %s\n", i, permutation);
        free(permutation);
        return 0;
    }

    free(permutation);
}

// no words found
printf("Max score: 0\nNo words can be made\n");
return 0;
}

bool checkForWords(char data[], int lengthData, int length, char  
                   combination[], int lengthCombination, char permutation[])
{   
// base recursive case
if (length == 0)
{   
    free(data);

    // checks for permutations for the fixed combination
    return checkPermutations(combination, lengthCombination, permutation, lengthCombination);
}

else
{   
    // generating combination by fixing one element and the recursively generating and checking
    for (int j = 0; j <= lengthData - length; ++j)
    {   
        // fixes one element
        combination[lengthCombination - length] = data[j];

        // recursive part
        if (checkForWords(removeLeftOfIndex(data, lengthData, j), lengthData - j - 1, length - 1, combination, 
           lengthCombination, permutation) == true)
           {
                free(data);
                return true;
           }
    }

    free(data);
    return false;
}
}

bool checkPermutations(char data[], int lengthData, char permutation[],  int lengthPermutation)
{   

// base recursive case
if (lengthData == 0)
{   
    // null character for printing string later
    permutation[lengthPermutation] = '[=10=]';


    // checking against dictionary - make this much faster with binary search!!!!
    FILE* dictionary= fopen("/usr/share/dict/words", "r");
    char word[15];
    while (fgets(word, sizeof(word), dictionary) != NULL)
    {   
        // checks to see if match
        if (strncmp(permutation, word, lengthPermutation) == 0)
        {   
            fclose(dictionary);
            free(data);
            return true;
        }

    }

    // not in dictionary
    fclose(dictionary);


    free(data);
    return false;

}

else
{   
    // generating permutations and checking for words by fixing one element and then using recursion.
    for (int j = 0; j < lengthData; j++)
    {   
        // fixing element
        permutation[lengthPermutation - lengthData] = data[j];

        // recursive part
        if (checkPermutations(removeElementAtIndex(data, lengthData, j), lengthData - 1, permutation, lengthPermutation) == true)
        {
            free(data);
            return true;
        }

    }
    free(data);
    return false;
}
}

char* removeLeftOfIndex(char data[], int lengthData, int index)
{   
// allocating heap memory
char* newData = malloc((lengthData - index - 1) * sizeof(char));

// loop to copy relevant parts
for (int j = 0; j < lengthData - index - 1; j++)
    newData[j] = data[j + index + 1];

return newData;
}

char* removeElementAtIndex(char data[], int lengthData, int index)
{   
// allocating heap memory
char* newData = malloc((lengthData - 1) * sizeof(char));

// loops to copy relevant parts
for (int i = 0; i < index; i++)
    newData[i] = data[i];
for(int i = index; i < lengthData - 1; i++)
    newData[i] = data[i + 1];

return newData;

}

可能还值得一提的是，当我尝试调试时，在代码中最后一个函数的实现中调用 malloc() 时似乎发生了分段错误：

// allocating heap memory
char* newData = malloc((lengthData - 1) * sizeof(char));

Answer 1

您的代码是内存分配和释放的蜘蛛网。我对其进行了重新设计，因此内存分配更有意义（无论如何对我来说。）让其调用者的子例程释放内存是奇怪的 - 相反是好的，让调用者释放 return 结果一个子程序。

尽管基本情况（字典中的单词完全匹配）似乎可行，但我不能说我能够测试其他可能性，因此此代码可能需要更多调试。但它并没有抱怨内存错误：

/**
 * Program to solve word puzzles from the TV show Countdown. 
 * Asks for 9 letters for input and then prints out the
 * maximum score and an example word of that score
 */

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

/**
 uses recursion to iterate over combinations of size "length" from 
 data[] of size "lengthData." Stores combinations generated in
 combination[] and permutations in permutation[]. For each combination
 calls checkPermutations to iterate over all permutations
 of the combination checking against a dictionary for word matches 
 returning true if a match is found
 */
bool checkForWords(char data[], int lengthData, int length, char combination[], int lengthCombination, char permutation[]);

/**
 * takes in an array - (in practice combination[] from main()) and
 * iterates through all the permutations of the array storing
 * generated permutations in permutation[] by using recursion. For 
 * each checks against a dictionary for word match. Returns true
 * when match is found
 */
bool checkPermutations(char data[], int lengthData, char permutation[], int lengthPermutation);

/**
 * takes an array of some length and an index and then returns a
 * pointer to an array on the heap that is the same but with the
 * elements at the index and to the left removed and then remaining 
 * elements "shifted down"
 */
char *removeLeftOfIndex(char data[], int lengthData, int index);

/**
 * takes an array of some length and index position and returns a
 * pointer to an array on the heap that has the element removed
 * and remaining elements "shifted down"
 */
char *removeElementAtIndex(char data[], int lengthData, int index);

#define LETTER_COUNT (9)

int main(void)
{
    char letters[LETTER_COUNT];

    // getting letters
    for (int i = 0; i < LETTER_COUNT; i++)
    {
        printf("Please enter letter %i: ", i + 1);
        letters[i] = GetChar();
    }

    // formatting
    printf("\n");

    bool success = false;

    char *data = malloc(LETTER_COUNT);
    char *permutation = malloc(LETTER_COUNT + 1);
    char *combination = malloc(LETTER_COUNT);

    // iterating over the length of word to look for starting at 9 and decrementing
    for (int i = LETTER_COUNT; i > 0; i--)
    {
        (void) strncpy(data, letters, LETTER_COUNT);

        // checks to see if there is a word of length i
        if (checkForWords(data, LETTER_COUNT, i, combination, i, permutation))
        {
            printf("Max score: %i\nExample word: %s\n", i, permutation);
            success = true;
            break;
        }
    }

    if (!success)
    {
        printf("Max score: 0\nNo words can be made\n");
    }

    free(data);
    free(permutation);
    free(combination);

    return EXIT_SUCCESS;
}

bool checkForWords(char data[], int lengthData, int length, char combination[], int lengthCombination, char permutation[])
{
    // base recursive case
    if (length == 0)
    { 
        // checks for permutations for the fixed combination
        return checkPermutations(combination, lengthCombination, permutation, lengthCombination);
    }

    // generating combination by fixing one element and the recursively generating and checking
    for (int j = 0; j <= lengthData - length; ++j)
    { 
        // fixes one element
        combination[lengthCombination - length] = data[j];

        // recursive part
        char *reduced = removeLeftOfIndex(data, lengthData, j);
        if (checkForWords(reduced, lengthData - j - 1, length - 1, combination, lengthCombination, permutation))
        {
            free(reduced);
            return true;
        }
        free(reduced);
    }

    return false;
}

bool checkPermutations(char data[], int lengthData, char permutation[], int lengthPermutation)
{
    // base recursive case
    if (lengthData == 0)
    { 
        // null character for printing string later
        permutation[lengthPermutation] = '[=10=]';

        // checking against dictionary - make this much faster with binary search!!!!
        FILE* dictionary= fopen("/usr/share/dict/words", "r");
        char word[64];

        while (fgets(word, sizeof(word), dictionary) != NULL)
        { 
            // checks to see if match
            if (strncmp(permutation, word, lengthPermutation) == 0)
            { 
                fclose(dictionary);
                return true;
            }
        }

        // not in dictionary
        fclose(dictionary);
        return false;
    }

    // generating permutations and checking for words by fixing one element and then using recursion.
    for (int j = 0; j < lengthData; j++)
    { 
        // fixing element
        permutation[lengthPermutation - lengthData] = data[j];

        // recursive part
        char *reduced = removeElementAtIndex(data, lengthData, j);
        if (checkPermutations(reduced, lengthData - 1, permutation, lengthPermutation))
        {
            free(reduced);
            return true;
        }
        free(reduced);
    }

    return false;
}

char *removeLeftOfIndex(char data[], int lengthData, int index)
{ 
    // allocating heap memory
    char *newData = malloc(lengthData - index - 1);

    // loop to copy relevant parts
    for (int j = 0; j < lengthData - index - 1; j++)
    {
        newData[j] = data[j + index + 1];
    }

    return newData;
}

char *removeElementAtIndex(char data[], int lengthData, int index)
{ 
    // allocating heap memory
    char *newData = malloc(lengthData - 1);

    // loops to copy relevant parts
    for (int i = 0; i < index; i++)
    {
        newData[i] = data[i];
    }

    for (int i = index; i < lengthData - 1; i++)
    {
        newData[i] = data[i + 1];
    }

    return newData;
}

祝你好运，希望对你有所帮助！

编写一个字谜解算器并获取分段错误以释放堆内存

Writing a word puzzle solver and getting segmentation fault freeing heap memory

c

puzzle

word

segmentation-fault

cs50