堆栈溢出错误导致链接列表中的malloc [英] Stack overflow error cause of malloc in linked list

问题描述

我编写了一个代码来使用二叉树算法（在K& R的C编程语言中讨论）对单词进行排序，无论如何我使用这个代码进行测试，在某些测试用例中有300000个单词要排序。

算法使用链表，所以对于每个新节点我需要一个分配，在这个特殊的测试用例中（最多需要300000分配）它给我堆栈溢出错误。

有没有任何建议如何解决这个问题？

我添加了代码，如果看到特殊的测试用例，请告诉我添加它。



编辑（1）：

我认为它甚至不是一个公平的问题，因为其中一个输入的长度大约为1200000，但我可以用CMD写的最大长度是4093 :(

这里是CMD限制的链接：

https://support.microsoft.com/en-us/help/830473/command-prompt-cmd-exe-command-line-st戒指限制



编辑（2）：

我试过从文件中读取但是MAXWORDLEN（代码中）不能超过1000000.



我尝试过：

I write a code to sort words using binary tree algorithm (which is discussed in C programming language by K&R) anyway I used this code for a test and in some test case there were 300000 words to sort.
algorithm uses linked list, so for each new node I need an allocation and in this special test case(which at most need 300000 allocation) it gives me stack overflow error.
Is there any suggestion how can I solve this problem?
I added the code and if seeing that special test case would help inform me to add it please.

Edit (1):
I think it isn't even a fair question cause one of the input has length about 1200000 but the max length I can write in CMD is 4093 :(
here is the link to limitation of CMD:
https://support.microsoft.com/en-us/help/830473/command-prompt-cmd-exe-command-line-string-limitation

Edit(2):
I tried reading from file but MAXWORDLEN(in code) can't exceed 1000000.

What I have tried:

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

#define MAXWORDLEN 200

#pragma warning(disable:4996)
using namespace std;

struct tnode {
	char *word;
	struct tnode *left;
	struct tnode *right;
	int num;
};

struct tnode *addNode(struct tnode *root, char *word);
void printTree(struct tnode *root);

int main() {
	int numTest;
	int numInput;
	scanf("%d", &numTest);
	for (int i = 0; i < numTest; i++) {
		struct tnode *root = NULL;
		scanf("%d", &numInput);
		getchar();
		for (int j = 0; j < numInput; j++) {
			char word[MAXWORDLEN];
			gets_s(word);
			root = addNode(root, word);
		}
		printTree(root);
	}
	return 0;
}

struct tnode *addNode(struct tnode *root, char *word) {
	int cmp;
	if (root == NULL) {
		root = (struct tnode*)malloc(sizeof(struct tnode));
		root->word = strdup(word);
		root->num = 1;
		root->left = root->right = NULL;
	}
	else if ((cmp = strcmp(word, root->word)) == 0)
		root->word += 1;
	else if (cmp > 0)
		root->right = addNode(root->right, word);
	else
		root->left = addNode(root->left, word);
	return root;
}

void printTree(struct tnode *root) {
	if (root != NULL) {
		printTree(root->left);
		for (int i = 0; i < root->num; i++) {
			printf("%s\n", root->word);
		}
		printTree(root->right);
	}
	return;
}

推荐答案

你的addNode函数有一些问题。

我会指出错误区域

Your addNode function has some issues.
I will point out the incorrect area

struct tnode *addNode(struct tnode *root, char *word) {
	int cmp;
	if (root == NULL) {
		root = (struct tnode*)malloc(sizeof(struct tnode));
		root->word = strdup(word);
		root->num = 1;
		root->left = root->right = NULL;
	}
	else if ((cmp = strcmp(word, root->word)) == 0)
		root->word += 1; // What do you expect this to do?
                // it will add 1 to the current address;
                // so, if you text is "abc", after adding one, you will get "bc", a will be gone. 
                // I am guessing you wanted to root->num++;?
	else if (cmp > 0) // looks nice, but my suggestion would be do the comparison outside and then use in the if else
		root->right = addNode(root->right, word);
	else
		root->left = addNode(root->left, word);
	return root;
}

建议的代码是：

The suggested code would be:

struct tnode *addNode(struct tnode *root, char *word) {
	int cmp= strcmp(word, root->word;
	if (root == NULL) {
		root = (struct tnode*)malloc(sizeof(struct tnode));
		root->word = strdup(word);
		root->num = 1;
		root->left = root->right = NULL;
	}
	else if (cmp == 0)
		root->num += 1;
	else if (cmp > 0)
		root->right = addNode(root->right, word);
	else
		root->left = addNode(root->left, word);
	return root;
}

----添加----

我的错误我忘了回答那个。

你是递归调用addNode的。如果您有300,000个唯一单词，那么您将递归调用150,000到300,000次。这可能是一个原因。看看这个答案 recursion - 在堆栈已满之前C / C ++中的最大递归函数调用并给出分段错误？ - 堆栈溢出 [ ^ ]。这是堆栈溢出流程的另一个写得很好的解释：内存 - 如何发生堆栈溢出，如何防止它？ - 堆栈溢出 [ ^ ]

----add----
My mistake I forget to answer that one.
You are calling addNode recursively. If you have 300,000 unique words, then you will call recursively 150,000 to 300,000 times. It can be a reason. Take a look at this answer recursion - Maximum recursive function calls in C/C++ before stack is full and gives a segmentation fault? - Stack Overflow[^]. This is an another well written explanation of stack over flow: memory - How does a "stack overflow" occur and how do you prevent it? - Stack Overflow[^]

这篇关于堆栈溢出错误导致链接列表中的malloc的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！