스택 오버플로우

정렬 알고리즘을 실험해 보는 도중 스택 오버플로우란 오류 메시지를 만났는데, 스택 오버플로우 오류는 처음 만나봐서 아래 코드에서 어떻게 고쳐줘야 해결이 될 수 있을 지 궁금합니다

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

#define MAX_LENGTH 10

typedef struct Test Test;
struct Test {

	int data1;
	int data2;
};

typedef struct Management Management;
struct Management {

	Test** test;
	int capacity;
	int usage;
};

Management* Init_Data(int size) {

	Management* data = (Management*)malloc(sizeof(Management));
	if (data != NULL) {

		data->capacity = size;
		data->usage = -1;

		data->test = (Test**)malloc(sizeof(Test*) * size);

		return data;
	}
	return NULL;
}

Test* Add_Data(int data) {

	int static cir = 1;

	Test* test = (Test*)malloc(sizeof(Test));
	if (test != NULL) {

		test->data1 = data;
		test->data2 = cir++;

		return test;
	}
	return NULL;
}


void Print_Data(Management* management) {

	for (int i = 0; i <= management->usage; i++) {

		printf("%02d'th data : %02d => %02d\n", i + 1, management->test[i]->data1, management->test[i]->data2);
	}
}

void Inisert_Data(Management* management, int data) {

	Test* DATA = Add_Data(data);

	if (management->capacity > management->usage + 1)
	management->test[++(management->usage)] = DATA;
}

void Swap(void* x, void* y);
void Quick_Sort(Management* management, int start, int end) {

	int Target = start;
	int Left = Target + 1;
	int Right = end;

	do {
		while (Left <= end && management->test[Left]->data1 <= management->test[Target]->data1)
			Left++;
		while (Right > start && management->test[Right]->data1 >= management->test[Target]->data1)
			Right--;

		if (Left <= Right)Swap(management->test[Left], management->test[Right]);
		else Swap(management->test[Right], management->test[Target]);
	} while (Left <= Right);

	Quick_Sort(management, start, Right - 1);
	Quick_Sort(management, Right + 1, end);
}

void Swap(void* x, void* y) {

	Management data = *(Management*)x;
	*(Management *)x = *(Management*)y;
	*(Management*)y = data;
}

void Delete_Data(Management* management) {

	for (int i = 0; i <= management->usage; i++) {

		free(management->test[i]);
	}
	free(management->test);
	free(management);
}

int main() {

	Management* management = Init_Data(MAX_LENGTH);
	int copy_array[10] = { 4,8,1,9,5,5,5,5,2,10 };

	for (int i = 0; i < MAX_LENGTH; i++) {

		Inisert_Data(management, copy_array[i]);
	}

	printf("\t<Before>\n"); Print_Data(management);

	Quick_Sort(management, 0, MAX_LENGTH - 1);

	printf("\t<After>\n"); Print_Data(management);

	Delete_Data(management);

	return 0;
}

함수가 호출되면 함수가 호출된 후 돌아갈 위치, 함수 인자, 지역 변수 등 기타 여러가지 정보를 기록하기 위해 스택이라는 영역에 이러한 정보들을 저장합니다. 쉽게 말해 이 스택이라는 공간이 가득 차게되면 스택 오버플로우가 발생합니다.

퀵소트를 재귀적인 방식으로 구현하셨는데, 언제 재귀가 멈출지 빠졌어요.
이러면 Quick_Sort가 계속 호출되지 않을까요? :sob:

그리고 이건 다른 얘기지만

void Swap(void* x, void* y) {

	Management data = *(Management*)x;
	*(Management *)x = *(Management*)y;
	*(Management*)y = data;
}

이 함수는 Test* 타입을 스왑해야 하는게 맞지 않나요?

1 Like

Quick_Sort 내부에서 start, end 를 찍어보시면 이해되실듯.

오타시겠죠?

제가 재귀로 구현을 하고선 탈출 조건을 안적어 줬었네요ㅠ 답변 감사드립니다!

1 Like

예리하시네요…ㅋㅋㅋ

내부에서 찍어보라는 말씀을 디버깅 한다는 것으로 이해했는데 맞나요? 답변 감사드립니다~

애초에 Swap(Test *x,Test *y) 이런식으로 스왑했으면
아래에서 Management *로 캐스팅 안해두 되겠네욥…
조언 감사합니다!

처음 swap함수를 배울떄 배웠던 자료가 좀 오래뒤서 void*를 이용해서 스왑하도록 배웠더니 이게 또 습관이 되버렸네요ㅠ