[자료구조] 문자열(Strings)

 

문자열이란 한정된 순서를 가진 크기가 0이상인 문자들의 집합을 말합니다.

 

C에서는 배열을 통해서 문자열을 나타낼 수 있습니다.

#define MAX_SIZE 100
char s[MAX_SIZE] = "dog";
char t[MAX_SIZE] = "house";

 

또한 선언할 때에는 다음과 같이 선언할 수도 있습니다.

char s[] = "dog";
char t[] = "house";

이때에는 문자의 개수+1개 만큼 크기가 자동으로 할당 됩니다.

 

하지만 다음과 같이 선언할 수 없습니다.

char u[]; //compile error

 

배열을 초기화하지도 않고, 크기도 정해주지 않는다면 컴파일 에러가 발생합니다.

---

이번에는 strcat 함수를 이용하여 문자열에 대해 더 알아보겠습니다.

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

void main() {
  char s[] = "dog";
  char t[] = "house";
  char u[] = "rainbow";
  printf("%p: %s\n", s, s);
  printf("%p: %s\n", t, t);
  printf("%p: %s\n", u, u);
  printf("\n");
  strcat(s, u);
  printf("%s\n", s);
  printf("%s\n", t); 
}

 

strcat함수는 다음과 같이 정의됩니다.

char *strcat(char *destination, const char *source)

 

source string을 destination string뒤에 이어 붙이는 함수입니다.

 

현재 배열의 크기를 정해주지 않고 값을 초기화하는 방법을 통해 배열의 크기가 정해졌습니다.

따라서 문자열은 다음과 같이 저장되어있을 겁니다.

이에 따라 문자열들의 각 시작 주소는 다음과 같이 출력됩니다.

 

문자열 s의 크기는 3이며 그 뒤에는 널 문자가 있습니다.

또한 뒤에는 바로 문자열 t가 나옵니다.

여기서 strcat을 사용하여 문자열 s뒤에 문자열 u를 연결한다면 어떻게 될까요?

공간이 충분하지 않은데 이어 붙이는 상황입니다.

 

이럴때는 house의 문자열이 손상됩니다. 

따라서 다음과 같이 출력됩니다.

문자열 s는 이제 dograinbow가 되었으며, 바로 뒤에 있던 문자열 t는 house라는 값을 가지고 있었지만 rainbow가 연결되면서 값이 사라지게 되었습니다. 또한 출력을 해보니 시작주소부터 널문자가 있는 곳까지 출력을 하는데, ainbow라고 출력이 된것을 알 수 있습니다.

---

이번에는 문자열의 삽입에 대해서 살펴보겠습니다.

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

#define MAX_SIZE 100

void strnins(char*, char*, int);

void main() {

  char s[MAX_SIZE] = "amobile";
  char t[MAX_SIZE] = "uto";
  strnins(s, t, 1);
  printf("%s\n", s);
}

void strnins(char *s, char *t, int i) {
  char string[MAX_SIZE] = {0}, *temp = string;

  if(i<0 && i> strlen(s)){
    fprintf(stderr,"position is out of bounds\n");
    exit(1);
  } 

  if(!strlen(s)) strcpy(s,t);

  else if(strlen(t)) {
    strncpy(temp,s,i);
    strcat(temp, t);
    strcat(temp, (s+i));
    strcpy(s, temp);
  }
}

 

amobile이라는 문자열에 uto이라는 문자열을 a 다음에 삽입하여 automobile을 만드는 코드입니다.

strncpy는 strcpy와 비슷한데, 앞에서부터 n개의 문자열만 복사한다는 점이 다릅니다.

 

strnins함수를 살펴보겠습니다.

먼저 string 문자열을 만들어주고 초기화를 해주었습니다. 그 다음에 문자형 포인터 temp로 string의 시작 주소를 가리키도록 하였습니다.

 

이후에는 else if문을 만날 것입니다.

strncpy를 만나 temp가 가리키는 곳부터 문자열의 s를 i개 만큼 입력합니다.

현재 i는 1이므로 a가 temp에 들어갑니다.

다음으로는 temp에 t를 연결합니다.

t는 uto였기 때문에 temp는 결과적으로 auto가 됩니다.

또한 여기에 s의 시작주소로부터 i 만큼 다음부터 입력을 해주어야하기 때문에 (s+i)를 넣어주는 것을 알 수 있습니다.

즉, s의 인덱스가 1인 곳부터 다시 문자열을 연결해주는 것입니다.

따라서 temp에는 결과적으로 automobile이 들어가게 됩니다.

마지막으로 문자열 s에 우리가 완성한 temp의 값을 복사하면 s는 automobile을 가지게 됩니다.

---

이번에는 Patterm Matching을 알아보겠습니다.

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

int nfind(char*, char*);

void main() {

  char pat[] = "wor";
  char str[] = "hello world I am a student.";
  int rv;

  rv = nfind(str, pat);
  if(rv == -1) {
    printf("The pattern %s was not found in the string.\n", pat);
  } else {
    printf("The pattern %s was found at position %d in the string.\n", pat, rv);
  }
}

int nfind(char *string, char *pat) {
  int i, j;
  int start = 0;
  int lasts = strlen(string) - 1;
  int lastp = strlen(pat) -  1;
  int endmatch = lastp;

  for(i = 0; endmatch <=lasts ; endmatch++, start++)
  {
    if(string[endmatch] == pat[lastp])
    {
      for(j = 0, i = start; j < lastp && string[i] == pat[j]; i++, j++);
    }
    if(j == lastp) return start;
  }

  return -1;
}

여기서 주목할 점은 nfind함수입니다. 

외부 for문을 먼저 살펴보겠습니다.

i는 string의 index에 방문할 때 사용할 변수입니다.

start와 endmatch는 패턴의 시작과 패턴의 끝을 나타내며, string에서 비교할때 사용할 변수입니다.

주황색이 패턴이며, 연두색이 string입니다.

if(string[endmatch] == pat[lastp])
    {
      for(j = 0, i = start; j < lastp && string[i] == pat[j]; i++, j++);
    }

이 부분은 패턴의 끝 문자와 스트링에서 endmatch에 있는 문자가 서로 같으면 나머지 문자들도 같은지 탐색하기 위해 내부 반복문을 실행하는 곳입니다. 

j는 패턴의 처음 시작부터 보기위해 0부터 시작하며, i는 탐색을 하며 증가된 start인데, 패턴과 비교할 문제의 시작점을 나타냅니다.

아래와 같은 상황을 생각하시면 이해가 쉽습니다.

i와 j를 증가시켜가며 스트링의 시작문자부터 패턴과 일치하는지 비교합니다.

만약 중간에 패턴과 스트링의 문자가 달라 비교가 멈추면 j는 반드시 lastp보다 못한 값을 가지게 될것입니다.

반대로 스트링과 패턴이 모두 일치하였다면 j는 lastp의 값을 가지고 있을 것입니다. 

그리고 두 상황 모두 내부 반복문을 빠져나오게 되겠습니다.

 

if(j == lastp) return start;

내부 반복문을 빠져나오면 만나게 되는 조건문입니다.

만약 j가 lastp와 같다면 스트링에서의 패턴이 있던 곳의 시작문자를 반환하게 되며, 이로써 스트링 내부에서의 패턴을 찾게 되는 것입니다.

만약 j가 lastp에 못 미치게된 상태로 외부 반복문까지 마친 상태라면 패턴을 찾지 못한 상태이므로 -1을 반환합니다.