这个拼写检查程序出现了seg错误。我尝试了gnu和valgrind,但我不知道发生了什么。(节点在.h文件中定义)该程序是cs50x的拼写检查它最初在较小的字典上工作,但现在它在运行时也会出现错误。
这里是节点:
typedef struct node
{
bool is_word;
struct node* letters[27];
}
node;
这是课程的拼写。c -由课程人员编写:
#include <ctype.h>
#include <stdio.h>
#include <sys/resource.h>
#include <sys/time.h>
#include "dictionary.h"
#undef calculate
#undef getrusage
// default dictionary
#define DICTIONARY "dictionaries/large"
// prototype
double calculate(const struct rusage* b, const struct rusage* a);
int main(int argc, char* argv[])
{
// check for correct number of args
if (argc != 2 && argc != 3)
{
printf("Usage: speller [dictionary] textn");
return 1;
}
// structs for timing data
struct rusage before, after;
// benchmarks
double time_load = 0.0, time_check = 0.0, time_size = 0.0, time_unload = 0.0;
// determine dictionary to use
char* dictionary = (argc == 3) ? argv[1] : DICTIONARY;
// load dictionary
getrusage(RUSAGE_SELF, &before);
bool loaded = load(dictionary);
getrusage(RUSAGE_SELF, &after);
// abort if dictionary not loaded
if (!loaded)
{
printf("Could not load %s.n", dictionary);
return 1;
}
// calculate time to load dictionary
time_load = calculate(&before, &after);
// try to open text
char* text = (argc == 3) ? argv[2] : argv[1];
FILE* fp = fopen(text, "r");
if (fp == NULL)
{
printf("Could not open %s.n", text);
unload();
return 1;
}
// prepare to report misspellings
printf("nMISSPELLED WORDSnn");
// prepare to spell-check
int index = 0, misspellings = 0, words = 0;
char word[LENGTH+1];
// spell-check each word in text
for (int c = fgetc(fp); c != EOF; c = fgetc(fp))
{
// allow only alphabetical characters and apostrophes
if (isalpha(c) || (c == ''' && index > 0))
{
// append character to word
word[index] = c;
index++;
// ignore alphabetical strings too long to be words
if (index > LENGTH)
{
// consume remainder of alphabetical string
while ((c = fgetc(fp)) != EOF && isalpha(c));
// prepare for new word
index = 0;
}
}
// ignore words with numbers (like MS Word can)
else if (isdigit(c))
{
// consume remainder of alphanumeric string
while ((c = fgetc(fp)) != EOF && isalnum(c));
// prepare for new word
index = 0;
}
// we must have found a whole word
else if (index > 0)
{
// terminate current word
word[index] = ' ';
// update counter
words++;
// check word's spelling
getrusage(RUSAGE_SELF, &before);
bool misspelled = !check(word);
getrusage(RUSAGE_SELF, &after);
// update benchmark
time_check += calculate(&before, &after);
// print word if misspelled
if (misspelled)
{
printf("%sn", word);
misspellings++;
}
// prepare for next word
index = 0;
}
}
// check whether there was an error
if (ferror(fp))
{
fclose(fp);
printf("Error reading %s.n", text);
unload();
return 1;
}
// close text
fclose(fp);
// determine dictionary's size
getrusage(RUSAGE_SELF, &before);
unsigned int n = size();
getrusage(RUSAGE_SELF, &after);
// calculate time to determine dictionary's size
time_size = calculate(&before, &after);
// unload dictionary
getrusage(RUSAGE_SELF, &before);
bool unloaded = unload();
getrusage(RUSAGE_SELF, &after);
// abort if dictionary not unloaded
if (!unloaded)
{
printf("Could not unload %s.n", dictionary);
return 1;
}
// calculate time to unload dictionary
time_unload = calculate(&before, &after);
// report benchmarks
printf("nWORDS MISSPELLED: %dn", misspellings);
printf("WORDS IN DICTIONARY: %dn", n);
printf("WORDS IN TEXT: %dn", words);
printf("TIME IN load: %.2fn", time_load);
printf("TIME IN check: %.2fn", time_check);
printf("TIME IN size: %.2fn", time_size);
printf("TIME IN unload: %.2fn", time_unload);
printf("TIME IN TOTAL: %.2fnn",
time_load + time_check + time_size + time_unload);
// that's all folks
return 0;
}
/**
* Returns number of seconds between b and a.
*/
double calculate(const struct rusage* b, const struct rusage* a)
{
if (b == NULL || a == NULL)
{
return 0.0;
}
else
{
return ((((a->ru_utime.tv_sec * 1000000 + a->ru_utime.tv_usec) -
(b->ru_utime.tv_sec * 1000000 + b->ru_utime.tv_usec)) +
((a->ru_stime.tv_sec * 1000000 + a->ru_stime.tv_usec) -
(b->ru_stime.tv_sec * 1000000 + b->ru_stime.tv_usec)))
/ 1000000.0);
}
}
// prototype of build trie function and unload
int build_trie(int letter, node* root, FILE* dict);
bool unloader(node* head);
// declare global variables
node* root;
int total_words = 0;
/**
* Returns true if word is in dictionary else false.
*/
bool check(const char* word)
{
// iniitialize pointer trav to point to same as root
node* trav = root;
// iterate over the word to see if letters are "open" paths in trie
int i = 0;
while (word[i] != ' ')
{
// check if letter
if (isalpha(word[i]))
{
if (trav->letters[tolower(word[i]) -97] == NULL)
{
return false;
}
else
{
trav = trav->letters[tolower(word[i]) -97];
i++;
}
}
else if (word[i] == ''')
{
if (trav->letters[26] == NULL)
{
return false;
}
else
{
trav = trav->letters[26];
i++;
}
}
else
{
return false;
}
}
// at the end check if word
if (word[i] == ' ')
return (trav->is_word);
else
return false;
}
/**
* Loads dictionary into memory. Returns true if successful else false.
*/
bool load(const char* dictionary)
{
// open a file to read the dictionary
FILE* dict = fopen(dictionary, "r");
if (dict == NULL)
{
printf("Could not open %s.n", dictionary);
return 1;
}
// create root
root = (node*)malloc(sizeof(node));
// initialize all pointers in root to NULL
for (int i = 0; i < 27; i++)
{
root->letters[i] = NULL;
}
// initialize trav
node* trav = root;
// initialize temp variable to store new word
int letter;
// while loop to read through the dictionary
while ((letter = fgetc(dict)) != EOF)
{
build_trie(letter, trav, dict);
}
if (letter == EOF)
return true;
else
return false;
}
// build a trie function
// to be used within load function recursively
int build_trie(int letter, node* trav, FILE* dict)
{
// set up place as value of letter - letters array place to "open"
int place = letter;
// set base case for recursive function -> end of string "n"
if (letter == 'n')
{
trav->is_word = true;
total_words++;
for (int i = 0; i < 27; i++)
{
trav->letters[i] = NULL;
}
return 0;
}
// recursive part
else
{
// determine where in letters arrays to go
if (isalpha(letter))
{
place = letter - 97;
}
else if (letter == 44)
{
place = 26;
}
// check to see if new node exists
// if not - create new node and recurse with new letter and pointer
if (trav->letters[place] == NULL)
{
trav->letters[place] = (node*)malloc(sizeof(node));
// initialize new nodes pointers to NULL
for (int i = 0; i < 27; i++)
{
trav->letters[place]->letters[i] = NULL;
}
letter = fgetc(dict);
return(build_trie(letter, trav->letters[place], dict));
}
// if it does exist - get new letter - and recurse with pointer to that node
else
{
letter = fgetc(dict);
return build_trie(letter, trav->letters[place], dict);
}
}
return 1;
}
/**
* Returns number of words in dictionary if loaded else 0 if not yet loaded.
*/
unsigned int size(void)
{
return total_words;
}
/**
* Unloads dictionary from memory. Returns true if successful else false.
*/
bool unload(void)
{
node* head = root;
return unloader(head);
}
/**
* recursive function to free the trie takes in the "head" of the trie
*/
// use recursion to free all nodes
bool unloader(node* head)
{
// check base case - all null pointers -> free
int total = 0;
for (int i = 0; i < 27; i++)
{
if (head->letters[i] == NULL)
{
total++;
}
}
// base case all 27 pointers == NULL
if (total == 27)
{
free(head);
head = NULL;
return true;
}
else
{
for (int i = 0; i < 27; i++)
{
if (head->letters[i] != NULL)
{
unloader(head->letters[i]);
}
}
}
return false;
}
查看您的代码时,在字典加载期间的build_trie()
和在字典中搜索已读单词的check()
函数之间存在不一致性。
在build_trie()
函数中,letters[26]
表示ASCII码44(魔术数?):
if (isalpha(letter))
{
place = letter - 97;
}
else if (letter == 44) // magic number = ','
{
place = 26;
}
在check()
函数中,letters[26]
用于'
(撇号)。
else if (word[i] == ''') // apostrophe character = ASCII 39
{
if (trav->letters[26] == NULL)
{
return false;
}
else
{
trav = trav->letters[26];
i++;
}
}
在build_trie()
函数中,计算place
索引时,出现以下意外行为:
if (isalpha(letter)) // both uppercase/lowercase are available
{
place = letter - 97; // magic number 97 = ASCII 'a'
}
else if (letter == 44) //''')
{
place = 26;
}
if (trav->letters[place] == NULL)
使用神奇数字97代替'a',可能会出现负数如果
letter
是大写字母,则为place
索引。在进入之前letters[place]
,索引未检查如果
letter
不是isalpha(),也不是44,也不是n
,则place
index已分配给letter
值,可以是任何8位价值。
在使用潜在的负place
索引之前,您可以添加该退出代码。
if ((place < 0) || (place > 26)) {
// exit when unexpected letter is loaded
printf("Unexepected "%c"(%d) in dictionary.n",(char)letter,letter);
return (-1);
}
if (trav->letters[place] == NULL)
在unloader()
函数中,返回条件不依赖于递归返回条件,对于左节点(带is_word = true
),返回条件仅为true
。另一个函数可以是:
bool unloader(node* head)
{
// only return false when node hasn't allocated
if (head == NULL) return (false);
bool bRes = true; // default answer is true
for(int i=0;i<27;i++)
{
// only call the recursive unloader() when allocated
if (head->letters[i]!=NULL) {
// check if all allocated node are freed
bRes = (bRes && unloader(head->letters[i]));
}
}
// free the leave-node
free(head);
head = NULL;
return (bRes);
}