C中具有BST递归的棘手分割错误 [英] Tricky Segmentation faults with BST recursion in C
问题描述
我正在尝试使用递归插入方法(BST，IIRC的常用方法)将字符串添加到二叉搜索树中，以便以后也可以使用递归将它们打印出来.
I'm trying to add strings to a Binary Search Tree using a recursive insert method (the usual for BSTs, IIRC) so I can later print them out using recursion as well.
问题是，我遇到了我不太了解的细分错误.相关代码如下(该代码块来自我的主要功能):
Trouble is, I've been getting a segmentation faults I don't really understand. Related code follows (this block of code is from my main function):
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
// Stores the size of the C-strings we will use;
// Standardized to 100 (assignment specifications say
// ALL strings will be no more than 100 characters long)
// Please note that I defined this as a preprocessor
// directive because using the const keyword makes it
// impossible to define the size of the C-String array
// (C doesn't allow for static array struct members whose
// size is given as a variable)
#define STRING_SIZE 100
// The flags for case sensitivity
// and an output file
int cflag = 0, oflag = 0;
// These are intended to represent the boolean
// values true and false (there's no native bool
// data type in C, apparently)
const int TRUE = 1;
const int FALSE = 0;
// Type alias for the bool type
typedef int bool;
// This is the BST struct. A BST is basically just
// a Node with at most two children (left and right)
// and a data element.
typedef struct BST
{
struct BST *left;
struct BST *right;
char *key;
int counter;
} BST;
// ----- FUNCTION PROTOTYPES -----
void insert(BST **root, char *key);
int caseSenStrCmp(char *str1, char *str2);
int caseInsenStrCmp(char *str1, char *str2);
bool existsInTree(BST *root, char *key, int cflag);
void inOrderPrint(BST *root, int oflag, FILE *outFile);
void deallocateTree(BST *root);
int main(int argc, char **argv) {
extern char *optarg;
extern int optind;
int c, err = 0;
// Holds the current line in the file/user-provided string.
char currentLine[STRING_SIZE];
// This will store the input/output file
// directories
char fileDirectory[STRING_SIZE];
static char usage[] = "Usage: %s [-c] [-o output_file_name] [input_file_name]\n";
while ((c = getopt(argc, argv, "co:")) != -1)
switch (c)
{
case 'c':
cflag = 1;
break;
case 'o':
oflag = 1;
// If an output file name
// was entered, copy it
// to fileDirectory
if (argv[optind] != NULL)
{
strcpy(fileDirectory, argv[optind]);
}
break;
case '?':
err = 1;
break;
default:
err = 1;
break;
}
if (err)
{
// Generic error message
printf("ERROR: Invalid input.\n");
fprintf(stderr, usage, argv[0]);
exit(1);
}
// --- BST SORT CODE STARTS HERE ---
printf("This is BEFORE setting root to NULL\n");
// This is the BST. As the assignment instructions
// specify, it is initially set to NULL
BST *root = NULL;
// Pointer to the mode the files
// will be opened in. Starts as
// "w" since we're opening the output file
// first
printf("This is AFTER setting root to NULL\n");
char *mode = (char*)malloc(sizeof(char*));
strcpy(mode, "w");
printf("Wrote w to mode pointer");
// Pointer to the output file
FILE *outFile;
// Attempt to open output file
outFile = fopen(fileDirectory, mode);
printf("Opened outfile \n");
// Now update mode and fileDirectory so
// we can open the INPUT file
strcpy(mode, "r");
printf("Wrote r to mode\n");
// Check if we have an input file name
// If argv[optind] isn't NULL, that means we have
// an input file name, so copy it into fileDirectory
if (argv[optind] != NULL)
{
strcpy(fileDirectory, argv[optind]);
}
printf("Wrote input file name to fileDirectory.\n");
// Pointer to the input file
FILE *inFile;
// Attempt to open the input file
//printf("%d", inFile = fopen(fileDirectory, mode));
printf("Opened input file\n");
// If the input file was opened successfully, process it
if (inFile != NULL)
{
// Process the file while EOF isn't
// returned
while (!feof(inFile))
{
// Get a single line (one string)
//fgets(currentLine, STRING_SIZE, inFile);
printf("Wrote to currentLine; it now contains: %s\n", currentLine);
// Check whether the line is an empty line
if (*currentLine != '\n')
{
// If the string isn't an empty line, call
// the insert function
printf("currentLine wasn't the NULL CHAR");
insert(&root, currentLine);
}
}
// At this point, we're done processing
// the input file, so close it
fclose(inFile);
}
// Otherwise, process user input from standard input
else
{
do
{
printf("Please enter a string (or blank line to exit): ");
// Scanf takes user's input from stdin. Note the use
// of the regex [^\n], allowing the scanf statement
// to read input until the newline character is encountered
// (which happens when the user is done writing their string
// and presses the Enter key)
scanf("%[^\n]s", currentLine);
// Call the insert function on the line
// provided
insert(&root, currentLine);
} while (caseSenStrCmp(currentLine, "") != 0);
}
// At this point, we've read all the input, so
// perform in-order traversal and print all the
// strings as per assignment specification
inOrderPrint(root, oflag, outFile);
// We're done, so reclaim the tree
deallocateTree(root);
}
// ===== AUXILIARY METHODS ======
// Creates a new branch for the BST and returns a
// pointer to it. Will be called by the insert()
// function. Intended to keep the main() function
// as clutter-free as possible.
BST* createBranch(char *keyVal)
{
// Create the new branch to be inserted into
// the tree
BST* newBranch = (BST*)malloc(sizeof(BST));
// Allocate memory for newBranch's C-string
newBranch->key = (char*)malloc(STRING_SIZE * sizeof(char));
// Copy the user-provided string into newBranch's
// key field
strcpy(newBranch->key, keyVal);
// Set newBranch's counter value to 1. This
// will be incremented if/when other instances
// of the key are inserted into the tree
newBranch->counter = 1;
// Set newBranch's child branches to null
newBranch->left = NULL;
newBranch->right = NULL;
// Return the newly created branch
return newBranch;
}
// Adds items to the BST. Includes functionality
// to verify whether an item already exists in the tree
// Note that we pass the tree's root to the insert function
// as a POINTER TO A POINTER so that changes made to it
// affect the actual memory location that was passed in
// rather than just the local pointer
void insert(BST **root, char *key)
{
printf("We made it to the insert function!");
// Check if the current branch is empty
if (*root == NULL)
{
// If it is, create a new
// branch here and insert it
// This will also initialize the
// entire tree when the first element
// is inserted (i.e. when the tree is
// empty)
*root = createBranch(key);
}
// If the tree ISN'T empty, check whether
// the element we're trying to insert
// into the tree is already in it
// If it is, don't insert anything (the
// existsInTree function takes care of
// incrementing the counter associated
// with the provided string)
if (!existsInTree(*root, key, cflag))
{
// If it isn't, check if the case sensitivity
// flag is set; if it is, perform the
// checks using case-sensitive string
// comparison function
if (cflag) {
// Is the string provided (key) is
// greater than the string stored
// at the current branch?
if (caseSenStrCmp((*root)->key, key))
{
// If so, recursively call the
// insert() function on root's
// right child (that is, insert into
// the right side of the tree)
// Note that we pass the ADDRESS
// of root's right branch, since
// the insert function takes a
// pointer to a pointer to a BST
// as an argument
insert(&((*root)->right), key);
}
// If not, the key passed in is either less than
// or equal to the current branch's key,
// so recursively call the insert()
// function on root's LEFT child (that is,
// insert into the left side of the tree)
else
{
insert(&((*root)->left), key);
}
}
// If it isn't, perform the checks using
// the case-INsensitive string comparison
// function
else {
// The logic here is exactly the same
// as the comparisons above, except
// it uses the case-insensitive comparison
// function
if (caseInsenStrCmp((*root)->key, key))
{
insert(&((*root)->right), key);
}
else
{
insert(&((*root)->left), key);
}
}
}
}
// CASE SENSITIVE STRING COMPARISON function. Returns:
// -1 if str1 is lexicographically less than str2
// 0 if str1 is lexicographically equal to str2
// 1 if str2 is lexicographically greater than str1
我正在使用getopt来分析用户输入的选项.我一直在使用printf语句进行一些基本的调试，只是为了了解在崩溃之前进入代码的程度，并且我或多或少地缩小了原因.似乎是这部分:
I'm using getopt to parse options that the user enters. I've been doing a little bit of basic debugging using printf statements just to see how far I get into the code before it crashes, and I've more or less narrowed down the cause. It seems to be this part here:
do
{
printf("Please enter a string (or blank line to exit): ");
// Scanf takes user's input from stdin. Note the use
// of the regex [^\n], allowing the scanf statement
// to read input until the newline character is encountered
// (which happens when the user is done writing their string
// and presses the Enter key)
scanf("%[^\n]s", currentLine);
// Call the insert function on the line
// provided
insert(&root, currentLine);
} while (caseSenStrCmp(currentLine, "\n") != 0);
或者更确切地说，通常是对插入函数的调用，因为我在插入函数开头放置的printf语句(我们使它进入了插入函数！")会一遍又一遍地打印，直到程序最终崩溃分段错误，这可能意味着问题是无限递归?
Or rather, calls to the insert function in general, since the printf statement I put at the beginning of the insert function ("We made it to the insert function!) gets printed over and over again until the program finally crashes with a segmentation fault, which probably means the problem is infinite recursion?
如果是这样，我不明白为什么会这样.我在main的开头将根节点初始化为NULL，因此至少在第一次调用时，它应该直接进入插入函数* root == NULL的情况.
If so, I don't understand why it's happening. I initialized the root node to NULL at the beginning of main, so it should go directly into the insert functions *root == NULL case, at least on its first call.
这可能与我将root作为指针传递给指针的方式有关(BST ** insert函数的参数列表中的root)吗?我是否不正确地重复使用该语句(以及与此类似的其他语句)
Does it maybe have something to do with the way I pass root as a pointer to a pointer (BST **root in parameter list of insert function)? Am I improperly recursing, i.e. is this statement (and others similar to it)
insert(&((*root)->right), key);
以某种方式不正确?这是我的第一个猜测，但是我不知道这将如何导致无限递归-如果有的话，它应该会失败而根本不递归?无论哪种方式，它都无法解释为什么root为NULL时会发生无限递归(即在第一次调用insert时，我将& root-指向根指针的指针-传递给insert函数).
incorrect somehow? This was my first guess, but I don't see how that would cause infinite recursion - if anything, it should fail without recursing at all if that was the case? Either way, it doesn't explain why infinite recursion happens when root is NULL (i.e. on the first call to insert, wherein I pass in &root - a pointer to the root pointer - to the insert function).
我真的被这个迷住了.起初，我认为这可能与我将字符串复制到currentLine的方式有关，因为该行
I'm really stuck on this one. At first I thought it might have something to do with the way I was copying strings to currentLine, since the line
if(*currentLine != '\0')
在while(！feof(inFile))循环中的
也会由于分段错误而使程序崩溃，但是即使我注释掉整个部分只是为了测试其余代码，我最终还是遇到了无限递归问题.
in the while (!feof(inFile)) loop also crashes the program with a segmentation fault, but even when I commented that whole part out just to test the rest of the code I ended up with the infinite recursion problem.
这里非常感谢您提供任何帮助，我已经尝试将其修复5个小时以上，但无济于事.我当然不知道该怎么办.
Any help at all is appreciated here, I've been trying to fix this for over 5 hours to no avail. I legitimately don't know what to do.
**由于很多评论都涉及到有关我声明其他变量的方式等问题，因此在代码的其余部分中，我决定将我的代码的全部内容包括在内，至少直到insert()为止.功能，这可能是问题所在.我只是省略了一些尝试以尽量减少代码的内容-我确定没有人喜欢阅读大量代码.
** Since a lot of the comments involved questions regarding the way I declared other variables and such in the rest of the code, I've decided to include the entirety of my code, at least until the insert() function, which is where the problem (presumably) is. I only omitted things to try and keep the code to a minimum - I'm sure nobody likes to read through large blocks of code.
Barmar:
关于fopen()和fgets():注释掉了这些内容，以便inFile保持为NULL，并且相关的条件检查将失败，因为该部分代码也因分段错误而失败
Regarding fopen() and fgets(): these were commented out so that inFile would remain NULL and the relevant conditional check would fail, since that part of the code also fails with a segmentation fault
createBranch()确实将其创建的节点的左右子节点都初始化为NULL(如上所示)
createBranch() does initialize both the left and right children of the node it creates to NULL (as can be seen above)
currentLine被声明为具有静态大小的数组.
currentLine is declared as an array with a static size.
@coderredoc:
@coderredoc:
我的理解是，它会从标准输入中读取，直到遇到换行符(即用户按下Enter键)为止，该字符不会记录为字符串的一部分
My understanding of it is that it reads from standard input until it encounters the newline character (i.e. user hits the enter button), which isn't recorded as part of the string
我已经知道你要去哪里了！我的循环条件设置为do/while循环，以检查换行符，因此循环永远不会终止.那绝对是我的错；这是我忘记更改该块的先前实现的结果.
I can already see where you were going with this! My loop conditional was set for the do/while loop was set to check for the newline character, so the loop would never have terminated. That's absolutely my fault; it was a carryover from a previous implementation of that block that I forgot to change.
在您指出之后，我确实进行了更改(请参见上面的新代码)，但是不幸的是，它并没有解决问题(我猜这是因为insert()函数内部发生了无限递归-一旦它得到第一次调用，它永远不会返回，只会因段错误而崩溃). **
I did change it after you pointed it out (see new code above), but unfortunately it didn't fix the problem (I'm guessing it's because of the infinite recursion happening inside the insert() function - once it gets called the first time, it never returns and just crashes with a segfault). **
推荐答案
我设法弄清楚了-原来问题出在毕竟是insert()函数.我重写了它(以及相关的其余代码)，以使用常规指针而不是指向指针的指针:
I managed to figure it out - turns out the problem was with the insert() function after all. I rewrote it (and the rest of the code that was relevant) to use a regular pointer rather than a pointer to a pointer:
BST* insert(BST* root, char *key)
{
// If branch is null, call createBranch
// to make one, then return it
if (root == NULL)
{
return createBranch(key);
}
// Otherwise, check whether the key
// already exists in the tree
if (!existsInTree(root, key, cflag))
{
// If it doesn't, check whether
// the case sensitivity flag is set
if (cflag)
{
// If it is, use the case-sensitive
// string comparison function to
// decide where to insert the key
if (caseSenStrCmp(root->key, key))
{
// If the key provided is greater
// than the string stored at the
// current branch, insert into
// right child
root->right = insert(root->right, key);
}
else
{
// Otherwise, insert into left child
root->left = insert(root->left, key);
}
}
// If it isn't, use the case-INsensitive string
// comparison function to decide where to insert
else
{
// Same logic as before. If the key
// provided is greater, insert into
// current branch's right child
if (caseInsenStrCmp(root->key, key))
{
root->right = insert(root->right, key);
}
// Otherwise, insert into the left child
else
{
root->left = insert(root ->left, key);
}
}
}
// Return the root pointer
return root;
}
立即解决了无限递归/段错误问题.它的确揭示了其他一些次要的语义错误(大多数错误可能是由于沮丧而造成的，因为我拼命试图解决此问题而没有重写插入函数)，但是我一直在一点一点地照顾这些错误.
Which immediately solved the infinite recursion/seg fault issue. It did reveal a few other minor semantic errors (most of which were probably made in frustration as I desperately tried to fix this problem without rewriting the insert function), but I've been taking care of those bit by bit.
我现在遇到了一个新问题(尽管可能比这更简单)，我将为其创建单独的线程，因为它与分段错误无关.
I've now got a new problem (albeit probably a simpler one than this) which I'll make a separate thread for, since it's not related to segmentation faults.
这篇关于C中具有BST递归的棘手分割错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
