글 읽기 - C 원형연결리스트 런타임오류

rooni97 3년 전 0

입출력 다 제대로 나오는데 런타임 에러가 납니다.

일단 typedef struct Node
{
int data;
Node* next;
}Node;에서

C에서는 Node* next도 오류가 뜨는데 왜 그런지 모르겠습니다. 도와주시면 감사하겠습니다

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
	int data;
	Node* next;
}Node;

Node* addFirst(Node *head, int i)
{
	Node *temp = (Node*)malloc(sizeof(Node));
	temp->data = i;
	if (head == NULL)
	{
		head = temp;
		temp->next = head;
	}
	else
	{
		temp->next = head->next;
		head->next = temp;
	}
	return head;
}

int removeat(Node *pre)
{
	Node *removed = pre->next;
	pre->next = removed->next;
	int output = removed->data;
	free(removed);
	return output;
}

int main()
{
	Node *head = NULL;
	int n, k;
	scanf("%d %d", &n, &k);
	for (int i = n; i >= 1; i--)
	{
		head = addFirst(head, i);
	}

	int s = 0;
	while (head != NULL)
	{
		for (int i = 0; i < k-1; i++)
		{
			head = head->next;
		}
		int result = removeat(head);
		if (s == 0)
		{
			printf("<");
		}
		printf("%d", result);
		if (s == n-1)
		{
			printf(">\n");
		}
		else
		{
			printf(", ");
		}
		s += 1;
	}

	return 0;
}

ckdgus2482 3년 전 1

댕글링 포인터 버그입니다

52번 라인에서 head->next에서 발생할 수 있는데

54라인에서 removeat(head)를 하면 head가 가리키는 노드의 다음 노드가 아니라 head가 가리키는 노드가 free되는 경우가 있습니다.

n번 노드의 경우인데 n번 노드는 최초에 add된 노드이고 18번 라인에 의해 next가 자기 자신을 가리키고 있습니다.

그래서 removeat 호출을 하면 자기 자신을 free 시키고 파라미터로 전달한 n번 노드를 가리키는 포인터는 댕글링 포인터로 남게 됩니다.

다음 반복에서 head->next 접근할때 런타임 에러가 발생하던지 미정의 행동이 발생할 것입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C 원형연결리스트 런타임오류

rooni97 3년 전 0

ckdgus2482 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말