私は現在、ハーバードの cs50 の pset6 に取り組んでいます。問題は、トライ辞書を実装することです。私は最終的に小さな問題でそれを機能させることができました。
- メモリ リークをチェックするために valgrind を実行すると、割り当てたよりも 1 つ多く解放したことがわかりますが、アンロード関数に問題は見られません。
- また、初期化されていない値がいくつかあることも警告しますが、結果には影響しませんが、わかりません。
ここに私のコード全体があります：
/****************************************************************************
* dictionary.c
*
* Computer Science 50
* Problem Set 6
*
* valgrind warn that there are uninitialized values, could be the node struct, but don't
* know how to initialize it, anyway, it works at last!
*
* Implements a dictionary's functionality.
***************************************************************************/
#include <stdbool.h>
#include <ctype.h>
#include "dictionary.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#define HASHTABLE_SIZE 5000
int count = 0; // gloabal counter
typedef struct node { // data structure
bool end_word;
struct node *children[27];
} node;
int
charNumber(char c); // function prototype
void
freeNode(node *currentNode);
node root = {false,{NULL}};
/*
* Returns true if word is in dictionary else false.
*/
bool
check(const char *word)
{
node *ptr = &root;
for (int i=0;i<strlen(word);i++)
{
if (ptr->children[charNumber(word[i])] == NULL)
return false;
ptr = ptr->children[charNumber(word[i])];
}
if (ptr->end_word)
return true;
else
return false;
}
/*
* Loads dictionary into memory. Returns true if successful else false.
*/
bool
load(const char *dictionary)
{
// char word[LENGTH+1]; // must initialize to zero! Or there will be some weird problem.
FILE *fp = fopen(dictionary,"r");
if (fp == NULL)
return false;
while (!feof(fp))
{
char word[LENGTH+1] = {};
fscanf(fp,"%s\n",word); // have to use "%s\n" instead of "%s", or the count will be wrong, don't know why.
count++;
node *ptr = &root;
for (int i=0;i<strlen(word);i++)
{
if (ptr->children[charNumber(word[i])] == NULL)
{
node *new = malloc(sizeof(node));
*new = (node) {false,{NULL}}; // initiallization
ptr->children[charNumber(word[i])] = new;
ptr = new;
}
else
{
ptr = ptr->children[charNumber(word[i])];
}
}
ptr->end_word = true;
}
fclose(fp);
return true;
}
/*
* caculate a number for the character
*/
int
charNumber(char c)
{
int num;
if (c == '\'')
return 26;
else if(c >= 'A' && c <= 'Z')
c += 32;
num = c - 'a';
return num;
}
/*
* Returns number of words in dictionary if loaded else 0 if not yet loaded.
*/
unsigned int
size(void)
{
if (count)
return count;
else
return 0;
}
/*
* Unloads dictionary from memory. Returns true if successful else false.
*/
bool
unload(void)
{
freeNode(&root);
return true; // can't figure out when to return false...
}
void freeNode(node *currentNode)
{
for (int i=0;i<27;i++)
{
if (currentNode->children[i] != NULL)
freeNode(currentNode->children[i]);
}
free(currentNode);
}
valgrind の出力の一部を次に示します。
==22110== Invalid free() / delete / delete[]
==22110== at 0x4024ECD: free (vg_replace_malloc.c:366)
==22110== by 0x8048F90: freeNode (dictionary_tries.c:152)
==22110== by 0x8048F45: unload (dictionary_tries.c:141)
==22110== by 0x8048AB5: main (speller.c:158)
==22110== Address 0x804a5a0 is 0 bytes inside data symbol "root"
==22110==
--22110-- REDIR: 0x40b2930 (strchrnul) redirected to 0x4028570 (strchrnul)
==22110==
==22110== HEAP SUMMARY:
==22110== in use at exit: 0 bytes in 0 blocks
==22110== total heap usage: 367,083 allocs, 367,084 frees, 41,113,776 bytes allocated
==22110==
==22110== All heap blocks were freed -- no leaks are possible
==22110==
==22110== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 14 from 9)
==22110==
==22110== 1 errors in context 1 of 1:
==22110== Invalid free() / delete / delete[]
==22110== at 0x4024ECD: free (vg_replace_malloc.c:366)
==22110== by 0x8048F90: freeNode (dictionary_tries.c:152)
==22110== by 0x8048F45: unload (dictionary_tries.c:141)
==22110== by 0x8048AB5: main (speller.c:158)
==22110== Address 0x804a5a0 is 0 bytes inside data symbol "root"
==22110==
--22110--
--22110-- used_suppression: 14 U1004-ARM-_dl_relocate_object
==22110==
==22110== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 14 from 9)