Member 13606974 Ответов: 1

Ошибка переполнения стека причина malloc в связанном списке


Я пишу код для сортировки слов с помощью алгоритма двоичного дерева (который обсуждается в языке программирования C K&R) в любом случае я использовал этот код для теста, и в каком-то тестовом случае было 300000 слов для сортировки.
алгоритм использует связанный список, поэтому для каждого нового узла мне нужно выделение, и в этом специальном тестовом случае(который в лучшем случае требует выделения 300000) он дает мне ошибку переполнения стека.
Есть ли какие-нибудь предложения, как я могу решить эту проблему?
Я добавил код, и если вы увидите этот специальный тестовый случай, сообщите мне, чтобы добавить его, пожалуйста.

Редактирование (1):
Я думаю, что это даже не справедливый вопрос, потому что один из входных данных имеет длину около 1200000, но максимальная длина, которую я могу написать в CMD, составляет 4093 :(
вот ссылка на ограничение CMD:
https://support.microsoft.com/en-us/help/830473/command-prompt-cmd-exe-command-line-string-limitation

Редактирование(2):
Я пробовал читать из файла, но MAXWORDLEN(в коде) не может превышать 1000000.

Что я уже пробовал:

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

Patrice T

вы уверены, что это связанный список ?
каков размер файла со всеми словами?

Member 13606974

Я не слишком хорошо знаком со списком ссылок, но мне так кажется.
размер файла составляет 24,8 Мб

1 Ответов

Рейтинг:
12

Mohibur Rashid

У вашей функции addNode есть некоторые проблемы.
Я укажу на неправильную область

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


Предлагаемый код будет выглядеть следующим образом:
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 раз. Это может быть причиной. Взгляните на этот ответ рекурсия - максимальное количество вызовов рекурсивных функций в C/C++ до того, как стек будет заполнен и даст ошибку сегментации? - переполнение стека[^]. Это еще одно хорошо написанное объяснение стека над потоком: память - как происходит "переполнение стека" и как его предотвратить? - переполнение стека[^]


Member 13606974

Мне жаль, что вы правы, что это было бы word->num++, но все равно это не решит ошибку переполнения стека

Mohibur Rashid

Пожалуйста, взгляните на обновленный ответ

Member 13606974

большое вам спасибо, это было причиной рекурсии, как вы сказали, и определение cmp глобально решило мою проблему. :)

Mohibur Rashid

это могло бы решить вашу проблему, но это не идеальное решение. Это вызовет у вас еще больше проблем. Вместо того чтобы вызывать рекурсию, как насчет циклического перебора? Я не буду создавать никаких проблем с переполнением памяти, и вы можете избежать любых возможных проблем с плохим изменением данных.

Member 13606974

почему ты думаешь, что это может доставить мне еще больше проблем? в соответствии с темами, которые вы предложили, определение переменных глобально может помочь.
пожалуйста, также проверьте правки в вопросе, потому что я получаю неправильный вывод, я сравнил выходы с помощью notepad++, и кажется, что проблема заключается в длине слов, потому что с маленькими словами нет никаких проблем даже для большого количества слов.
или может быть как вы сказали У меня возникнет еще одна проблема причина рекурсии

Mohibur Rashid

Ваш МАКСВОРДЛЕН-200. Посмотрите на пример:

char *x = "test";

в памяти x удерживает 5 байт символа. Включая 0; если у вас есть какая-либо строка, содержащая ровно 200 символов, это вызовет у вас проблемы.

А что касается глобальной переменной, то в данном случае никаких проблем нет. Но попробуйте выработать привычку не использовать глобальную переменную. Или, если вы хотите сохранить глобальную переменную, объявите ее статической.

Member 13606974

это верно, но также нет места, как 1200000 в C. Я связываюсь с владельцем и надеюсь, что он ответит мне в ближайшее время. спасибо за вашу помощь :)