[C] 문자열 배열 동적 할당 & 버블 정렬 구현

C에서는 일반적으로 문자열을 char * 이나 char []로 구현하며, 문자열 배열은 앞 문자열 구현의 배열형인

char*[] 이나 char[][] 로 구현합니다. 즉 C에서 여러 문자열을 배열 형태로 저장하고 싶으면 (char*)[] 의 포인터 배열 형태나 char[][] 의 2차원 배열로 구현을 해야합니다.

 

char strings[4][20] =
{
    {"Hello"},{"I am"}, {"File"}, {"nice to meet you"}
};

1. 문자열 배열을 2차원 배열로 저장하면 다음과 같이 파란색 공간에 메모리 공간이 낭비되는 문제가 발생합니다.

또한 동적으로 문자열 크기를 할당할 수 없는 문제를 가지고 있습니다.

 

 

 

char * strings[4] = {"Hello", "I am", "File", "nice to meet you"};

2. 문자열 배열을 char 포인터 배열로 저장할 경우 직관적인 표현으로 저장할 수 있고, 메모리 낭비도 없이 저장할 수 있습니다. 그러나 문자열을 대입 연산(=)을 통해 한번 할당한 경우 그 메모리 공간은 Read-Only 공간에 할당되어서 scanf(...), strcpy() 등으로 메모리 공간에 값을 쓸 수 없고, 값 할당이라곤 다시 대입 연산자를 통해 새로운 Read-Only 메모리 공간에 문자열을 할당 하는 방법 밖에 존재하지 않습니다.

 

간단하게 문자열을 저장하는데 사용하기엔 좋지만 문자열 값을 확정 이후 나중에 쓰기를 해야 하는 경우 난감해집니다.

 

또 대입 연산이 아닌 어떤 문자열 공간을 할당하고 포인터로 가리키는 형태로 문자열을 읽어낸다고 해도 역시 "할당" 이 필요합니다.

 

결론 : 2차원 배열을 동적 할당해서 문자열 배열 형태로 저장해보자

오늘의 주제입니다. 2차원 char 배열을 동적 할당해서 문자열 배열을 구현해봅시다. 

* C에는 C++ 처럼 String Class 가 없어서 이런 똥꼬쇼를 해야 합니다 ㅠㅠ

 

코드와 사진은 아래 링크를 참고했습니다.

https://codeng.tistory.com/8

 

char **dynamic_string_array(int row, int col) {
    // 문자열 배열 동적 할당 (heap에 할당하므로 나중에 사용하는쪽에서 free()
    // 필수)
    char **result = (char **)malloc(sizeof(char *) * row);
    for (int i = 0; i < row; i++) {
        result[i] = (char *)malloc(sizeof(char) * col);
    }
    return result;
}

우선 다음 함수를 사용하면 Row(행) x Col(열) 로 char형의 2차원 배열 공간을 동적할당해준 후 그 메모리 주소(이중 포인터) 를 반환해줍니다.

행의 경우 몇 개의 문자열들을 저장할 지 갯수를 정하는 것이고, 열은 각 문자열을 몇 글자만큼 저장할 수 있는지에 대한 공간입니다. 열 크기는 넉넉하게 잡아줍시다.

 

그림으로 나타내면 위와 같은 형태가 된다고 합니다.

물론 효율적으로 할당하기 위해선 각 포인터 요소가 그 문자열에 길이에 맞는 열로 할당되어야 겠지만 우선 편의를 위해 다음과 같이 정했습니다.

 

포인터가 안에서 또 할당한 공간을 가리키게끔 하고 그 포인터의 첫번째를 다시 가리키는 형태라서 이중 포인터로 반환된 듯 합니다. (사실 글 쓰는 지금까지도 정확한 구조를 잘 이해못했습니다 죄송합니다 ㅎㅎ;;)

 

#include <stdio.h>
#include <string.h>

char **dynamic_string_array(int row, int col);

int main()
{
    int count = 3;
    char **result = dynamic_string_array(count, 100); //문자열 3개를 저장 (각 문자열의 길이는 100)

    // result 값 설정
    strcpy(result[0], "xasdqw");
    strcpy(result[1], "doesdfsabd");
    strcpy(result[2], "sdfasdf");

    // result 출력
    for (int i = 0; i < count; i++)
    {
        // 문자열 글자수 출력
        printf("%d ", strlen(result[i]));
    }
}

사용하는 입장에선 dynamic_string_array() 에서 반환된 값(문자열 배열 공간)을 char ** 이중 포인터로 받아주고, result 변수는 일반 문자열 배열 처럼 사용해주시면 끝입니다.

동적 할당된 공간(heap) 이라 strcpy() 로 쓰기는 당연히 잘됩니다.

 

이중 포인터인데도 일반 문자열 배열(char *[], char[][]) 처럼 동일하게 접근할 수 있는 이유는 아마 메모리 구조상 컴퓨터가 이해하기엔 거의 차이가 없어서 그런거 같습니다...? 

// result 메모리 해제
for (int i = 0; i < count; i++)
{
    free(result[i]);
}
free(result);

그리고 사용이 끝났으면 반드시 free()를 이용해 메모리 공간을 해제시켜줍니다.

위에서 malloc() 을 row + 1 번 호출했는데 그렇기에 free() 역시 row + 1 번 호출시켜 줍니다.

 

void sort_string(char **arr, int count)
{
    // 버블 정렬 수행 (O(n^2))
    for (int i = 0; i < count - 1; i++)
        for (int j = 0; j < count - i - 1; j++)
            if (strcmp(arr[j], arr[j + 1]) > 0)
            {
                // 임시 저장소 동적 할당
                char *temp = (char *)malloc(sizeof(char) * (strlen(arr[j]) + 1));
                strcpy(temp, arr[j]);
                strcpy(arr[j], arr[j + 1]);
                strcpy(arr[j + 1], temp);

                //동적할당된 공간 삭제
                free(temp);
            }
}

만약 동적 할당한 문자열 배열을 정렬하고 싶다면 다음 함수를 이용해줍니다.

strcmp() 를 이용해 문자열을 비교하고 버블 정렬을 이용해 정렬합니다.

 

물론 버블 정렬의 시간 복잡도는 $O(n^2)$ 로 좋지 않긴 한데 C언어에서 지원하는 qsort() 로 동적할당된 메모리를 정렬할 때 오류가 나서 일단 쉬운 버블정렬로 구현을 해봤습니다. 뭐 C가 워낙 빨라서 그런가 10만개 정도는 100만번 반복이라 그렇게 느리다는 느낌은 받지 못했습니다. strcmp() 함수도 상당히 빠른듯하구요..?

 

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

char **dynamic_string_array(int row, int col);
void sort_string(char **arr, int count);

int main()
{
    int count = 3;
    char **result = dynamic_string_array(count, 100); //문자열 3개를 저장 (각 문자열의 길이는 100)

    // result 값 설정
    strcpy(result[0], "casdqw");
    strcpy(result[1], "boesdfsabd");
    strcpy(result[2], "adfasdf");

    // result 문자열 배열 정렬
    sort_string(result, count);

    // result 출력
    for (int i = 0; i < count; i++)
    {
        // 문자열 글자수 출력
        printf("%s\n", result[i]);
    }
}

char **dynamic_string_array(int row, int col)
{
    // 문자열 배열 동적 할당 (heap에 할당하므로 나중에 사용하는쪽에서 free()
    // 필수)
    char **result = (char **)malloc(sizeof(char *) * row);
    for (int i = 0; i < row; i++)
    {
        result[i] = (char *)malloc(sizeof(char) * col);
    }
    return result;
}

void sort_string(char **arr, int count)
{
    // 버블 정렬 수행 (O(n^2))
    for (int i = 0; i < count - 1; i++)
        for (int j = 0; j < count - i - 1; j++)
            if (strcmp(arr[j], arr[j + 1]) > 0)
            {
                // 임시 저장소 동적 할당
                char *temp = (char *)malloc(sizeof(char) * (strlen(arr[j]) + 1));
                strcpy(temp, arr[j]);
                strcpy(arr[j], arr[j + 1]);
                strcpy(arr[j + 1], temp);

                //동적할당된 공간 삭제
                free(temp);
            }
}

<Output>
adfasdf
boesdfsabd
casdqw

해당 코드를 실행해보면 문자열 동적할당과 정렬이 모두 정상적으로 이루어지는걸 확인할 수 있었습니다.

문자열 3줄 저장해보자고 코드가 벌써 57줄이 됐네요.. 걍 파이썬 하고 싶다 ㅠ