글 읽기 - C언어 합병 정렬시 런타임 에러 발생 관련

gspear 3년 전 0

합병 정렬(merge sort)를 이용해서 정렬을 하는 과정에서

함수 merge 내부에 구조체 포인터 temp에 적당한 크기로 메모리를 할당한 뒤에 free를 시행하는 과정에서 에러가 발생합니다. (코드 14번 줄, 29번줄)

그래서 temp를 전역 변수로 한 뒤 구조체 배열로 선언하니 문제없이 작동하더라구요. 혹시 malloc 과 free 함수를 많이 사용하면 문제가 발생하나요 ?

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

typedef struct _User
{
    int age;
    char name[101];

} User;

void merge(User *arr,int first,int mid,int end)
{
    int i=first, j=mid+1, k=first;
    User *temp=(User*)malloc(sizeof(User)*end+1);
    while(i<=mid && j<=end)
    {
        if(arr[i].age<=arr[j].age)
            temp[k++]=arr[i++];
        else
            temp[k++]=arr[j++];
    }
    while(i<=mid)
        temp[k++]=arr[i++];
    while(j<=end)
        temp[k++]=arr[j++];
    for(i=first; i<=end; i++)
        arr[i]=temp[i];

    free(temp);

}

void mergesort(User *arr,int first,int end)
{
    int mid;
    if(first<end)
    {
        mid=(first+end)/2;
        mergesort(arr,first,mid);
        mergesort(arr,mid+1,end);
        merge(arr,first,mid,end);

    }
}

int main()
{
    int num,i;
    scanf("%d",&num);

    User *arr=(User *)malloc(sizeof(User)*num);

    for(i=0; i<num; i++)
        scanf("%d %s", &arr[i].age,arr[i].name);

    mergesort(arr,0,num-1);

    for(i=0; i<num; i++)
        printf("%d %s\n",arr[i].age,arr[i].name);

    free(arr);
}

djm03178 3년 전 1

merge 함수는 temp[end]를 접근해야 하기 때문에 sizeof(User)가 end+1개만큼 필요합니다. 즉, sizeof(User) * (end + 1)만큼의 메모리가 할당되어야 하는데, 14번째 줄에서는 sizeof(User) * end에 1바이트만을 추가로 할당하고 있어서 부족합니다.

gspear 3년 전 0

괄호를 안쓴게 원인이었군요. 감사합니다.

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

문제

문제

출처

ICPC

C언어 합병 정렬시 런타임 에러 발생 관련

gspear 3년 전 0

djm03178 3년 전 1

gspear 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말