Stack overflow error cause of malloc in linked list

Question

0.00/5 (No votes)

See more:

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;
}

Posted 8-Jul-18 12:14pm

Member 13606974

Updated 9-Jul-18 2:51am

v2

Add a Solution

Comments

Patrice T 8-Jul-18 18:46pm

are you sure it is a linked list ?
what is the size of the file with all the words?

Member 13606974 8-Jul-18 19:40pm

I'm not familiar with link list too much but it seems so.
the file size is 24.8 mb

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Mohibur Rashid · Accepted Answer · 2018-07-08T12:55:00

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

C++

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:

C++

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;
}

----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[^]