[자료구조 - C언어] 자료구조 제8강: 전화번호부 v3.0

 

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

배열 재할당, 라인 단위 입력과 문자열 tokeninzing

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

#define INIT_CAPACITY 3
#define BUFFER_SIZE 50

void init_directory();
void process_command();
int read_line(char str[], int limit);

char ** names;
char ** numbers;

int capacity = INIT_CAPACITY;
int n = 0;

char delim[] = " ";

int main(){
    init_directory();    //배열 names, numbers를 동적 메모리 할당으로 생성
    process_command();   //사용자의 명령을 받아 처리하는 함수
    
    return 0;
}

• char ** names
  • version 2.0) char * names[100]
    • 캐릭터 포인터 타입의 배열의 이름이 names
      • 배열의 이름은 배열의 시작 주소를 가리키는 포인터 변수 ⇒ 이중 포인터 타입 변수
  • version 3.0) char ** names
    • names라는 변수의 타입은 char **: 캐릭터 포인터 포인터 ⇒ 이중 포인터 타입 변수

 

1. init_directory()

//배열 names와 numbers를 동적 메모리 할당으로 생성
void init_directory(){
    names = (char **)malloc(INIT_CAPACITY * sizeof(char *));
    numbers = (char **)malloc(INIT_CAPACITY * sizeof(char *));
}

• 배열 names와 numbers를 동적 메모리 할당으로 생성
• malloc(필요한 메모리의 byte 수)
  • 할당할 메모리의 byte 수를 직접 숫자로 지정하는 것보다 sizeof 연산자를 사용하는 것이 호환성 문제를 대비할 수 있다.

 

2. read_line()

//표준 입력으로부터 사용자가 enter를 칠 때 까지 한 줄을 입력 받아 첫 번째 매개변수인 str에 저장
int read_line(char str[], int limit){
    int ch, i = 0;
    //줄 바꿈 문자가 나올 때 까지 읽고, 배열의 용량을 초과하지 않을 떄만 저장
    while ((ch = getchar()) != "\n")
        if (i < limit - 1)
            str[i++] = ch;
    //마지막에 null character 추가
    str[i] = '\0';
    
    //실제로 읽은 문자수 반환
    return i;       
}

• 표준 입력으로부터 사용자가 enter를 칠 때까지 한 줄을 입력받아 첫 번째 매개변수인 str에 저장
• line 단위 입력은 gets, fgets, getline 등의 함수들을 이용하여 할 수도 있지만 직접 사용자 정의 함수를 만들어 사용할 수도 있다.
• getchar()는 한 문자씩 입력받는 함수
  • getchar()가 리턴하는 값을 정수형 변수 ch에 저장한다.
    • ch가 저장하는 값이 줄 바꿈 문자가 아닐 때까지
• i < limit - 1은 모든 문자열은 맨 끝에 null character로 끝나야 하기 때문에 -1을 제한한다.
  • 맨 마지막에 null character 추가

2-1. 참고 - 차이점

//1번
while ((ch = getchar()) != "\n")
        if (i < limit - 1)
            str[i++] = ch;

//2번
while (i < limit - 1 && (ch = getchar()) != "\n")
		str[i++] = ch;

• 1번은 어떤 경우에서든 “\n”이 나올 때 까지 읽음
  • 즉, 실행하면 한 라인을 반드시 읽음
    • 이 경우, 다음 라인을 읽지만
• 2번은 i가 limit에 도달하면 while을 빠져나와 return
  • 중간쯤 읽다가 return 할 수도 있음
    • 이 경우에는, 중간에 잘린 부분 이후로 남아있는 부분을 읽게 된다.

 

3. tokenizing

save as directory.txt

• version 2.0)
  • 한 단어씩 순차적으로 입력을 받음
• version 3.0)
  • 한 라인을 순차적으로 입력 받음
    • 해석하려면 공백 문자를 기준으로 쪼개야 한다.
      • 이때 공백 문자는 구분자 역할을 하며, delimiter라고 한다.
• 문자열 tokenizing: 구분 문자(delimiter)를 이용하여 하나의 긴 문자열을 작은 문자열들로 자르는 일
  • 잘라진 작은 문자열들: token
  • c언어에서 주로 strtok 함수 이용

3-1. strtok을 이용한 문자열 자르기

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

int main(void){
    char str[] = "now # is the time # to start preparing ### for the exam#";
    char delim[] = "#";
    char *token;
    
    //첫 번째 호출
    token = strtok(str, delim);
    while(token != NULL){    //문자열이 끝나서 더 이상 토큰이 존재하지 않으면 null 리턴
        printf("next token is: %s:%d\\n", token, strlen(token));
        //이어진 호출들
        token = strtok(NULL, delim);
    }
    return 0;
}

• token = strtok(str, delim);
  • 첫 번째 매개변수: 문자열의 주소(문자열을 포함하고 있는 배열의 이름)
  • 두 번째 매개변수: delimiter로 사용할 문자 배열
    • char delim[] = “#”
      • 하나의 문자 배열 안에 구분자를 넣음 = delimiter도 하나의 string으로 주어짐
  • 리턴 값은 문자열을 구분자를 기준으로 tokenizing 했을 때 첫 번째 token의 시작 주소를 리턴
    • 첫 번째 호출의 리턴 값은 ‘now ‘의 n의 주소
  • token = strtok(NULL, delim)
    • 첫 번째 호출에서는 tokenizing 하고자 하는 문자열의 주소를 주어야 하지만 그다음부터는 NULL입력 주의

printf("next token is: %s:%d\\n", token, strlen(token));
//공백주의

• ###: 구분자가 연속해서 나올 경우에는 통째로 하나의 구분자로 인식
  • 구분자-구분자 사이의 토큰의 길이가 0
  • 구분자-구분자 사이에 토큰 없음
    • 으로 처리할 수 있지만 strtok는 통째로 하나의 구분자로 인식한다

3-2. strtok의 작동 원리

char str[] = " time  to  start"
char delim[] = " "

• printf()는 null character까지 출력한다.
  • 첫 번째 strtok를 하면 첫 공백은 무시한 채로 ‘t’의 주소를 리턴하는 것에 그치면 →“time to start”를 출력해야 한다.
    • 그렇지 않은 이유는
      • strtok가 첫 번째 시작 주소를 찾아 리턴해주는 것에 그치지 않고 첫 번째 토큰이 끝나는 위치에 null character를 삽입하기 때문이다.
        • ⇒ “time” 출력

• strtok은 원본 문자열을 변화시킨다(= ‘\0’을 삽입한다.)

• • str = “now \0 is the time \0 to start preparing \0 for the exam\0”
    • printf로 출력할 때는 ‘\0’까지만 출력
  • str 중간중간에 null character을 삽입할 수 있다 = str이 string literal이 아니다.
    • char * str = “ “
      • string literal: 겹 따옴표로 정의된 문자열로 변경할 수 없는 상수
    • char str[] = “”
      • char array: 수정할 수 있다. strtok 사용할 수 있다.

 

4. process_command()

//사용자의 명령을 받아 처리하는 함수
void process_command(){
    char command_line[BUFFER_SIZE];
    char *command, *argument1, *argument2;
    
    while(1){
        printf("$");
        
        if(read_line(command_line, BUFFER_SIZE) <= 0)
            continue;
        command = strtok(command_line, delim);
        if(command == NULL) continue;
        
        if(strcmp(command, "read") == 0){
            //입력받은 하나의 commandline을 연속해서 strtok하기 때문에
            //이후의 strtok에서 첫 번째 매개변수는 null
            argument1 = strtok(NULL, delim);
            if(argument1 == NULL){
                printf("File name required.\\n");
                continue;
            }
            load(argument1);
        }
        
        else if (strcmp(command, "add") == 0){
            argument1 = strtok(NULL, delim);
            argument2 = strtok(NULL, delim);
            
            if (argument1 == NULL || argument2 == NULL){
                printf("Invalid arguments.\\n");
                continue;
            }
            add(argument1, argument2);
            printf("%s was added successfully.\\n", argument1);
        }
        
        else if (strcmp(command, "find") == 0){
            argument1 = strtok(NULL, delim);
            
            if (argument1 == NULL){
                printf("Invalid arguments.\\n");
                continue;
            }
            find(argument1);
        }
        
        else if (strcmp(command, "status") == 0)
            status();
        
        else if (strcmp(command, "delete") == 0){
            argument1 = strtok(NULL, delim);
            if (argument1 == NULL){
                printf("Invalid arguments.\\n");
                continue;
            }
            delete(argument1);
        }
        
        else if (strcmp(command, "save") == 0){
            argument1 = strtok(NULL, delim);
            argument2 = strtok(NULL, delim);
            
            if (argument1 == NULL || strcmp("as", argument1) != 0 || argument2 == NULL){
                printf("Invalid command format.\\n");
                continue;
            }
            save(argument2);
        }
            
        else if (strcmp(command, "exit") == 0)
            break;;
        
    }
}

• 입력받은 하나의 commandline을 연속해서 strtok 하기 때문에 이후의 strtok에서 첫 번째 매개변수는 null 사용

4-1. load(char *fileName)

void load(char *fileName){
    char buf1[BUFFER_SIZE];    //이름 - 지역변수
    char buf2[BUFFER_SIZE];    //전화번호 - 지역변수
    
    FILE *fp = fopen(fileName, "r");
    if (fp==NULL){
        printf("Open failed.\\n");
        return;
    }
    
    while((fscanf(fp, "%s", buf1) != EOF)){
        fscanf(fp, "%s", buf2);
        add(buf1, buf2);
    }
    fclose(fp);
}

4-2. add(char * name, char * number)

void add(char * name, char * number){
    //현재 저장된 사람의 수 > 배열의 크기: 배열이 꽉찬 경우 재할당
	  //reallocate를 해서 배열의 크기를 키워준다
    if (n>= capacity)    
        reallocate();

    //추가하려는 사람보다 이름이 큰 사람은 한 칸씩 이동시키고
    //그 사이에 새로운 사람을 삽입
    int i = n-1;
    while(i >= 0 && strcmp(names[i], name) >0){
        names[i+1] = names[i];
        numbers[i+1] = numbers[i];
        i--;
    }
    names[i+1] = strdup(name);
    numbers[i+1] = strdup(number);
    
    n++;
}

• 매개변수 name과 numbers는 load() 함수의 지역변수이기 때문에 load 함수가 끝나고 return 되면 사라짐
  • names와 numbers에 저장해두는 데이터들은 프로그램이 실행되는 중에 계속해서 전역적으로 유지되어야 하는 데이터이기 때문에 strdup로 copy 해서 저장
  4-2-1. reallocate()
  • 배열의 크기가 꽉 찬 경우 배열의 크기를 키울 수 있는 방법은 없다.
    • → 배열은 메모리의 연속된 부분을 차지해야 하고, 뒷부분은 다른 변수들이, 다른 용도로 사용되고 있을 것이기 때문에 기존의 크기를 키울 수 있는 방법은 일반적으로 없다.
      • ⇒ 더 큰 배열을 할당받아 원래 있던 배열은 버리고 더 큰 배열을 사용하는 방법

  void reallocate(){
      int i;
      
      //먼저 크기가 2배인 배열들을 할당
      capacity *= 2;
      char **tmp1 = (char **)malloc(capacity*sizeof(char *));
      char **tmp2 = (char **)malloc(capacity*sizeof(char *));
      
      //원본 배열 names와 numbers의 값을 새로운 배열에 복사
      for (i=0; i<n; i++){
          tmp1[i] = names[i];
          tmp2[i] = numbers[i];
      }
      
      //반환
      free(names);
      free(numbers);
      
      //names와 numbers가 새로운 배열을 가리키도록 한다.
      names = tmp1;
      numbers = tmp2;
  }

  • free()
    • 더 이상 사용하지 않지만 없어지지 않고 계속 존재해서 메모리를 차지하는 garbage 메모리를 반환하는 방법
    • names와 numbers가 새로운 배열을 가리키면 더 이상 이전의 names와 numbers를 호출할 방법이 없기 때문에 사용할 수 없이 메모리 공간만 차지하게 됨
    • malloc의 반대, 현재 가리키고 있는 메모리 공간을 반환
  • names와 numbers가 새로운 배열을 가리키면
    • 결과적으로 새로 할당받은 배열을 가리키게 되어 마치 크기가 2배로 늘어난 듯한 효과
      • ⇒ 이것이 가능한 이유는 배열의 이름은 포인터 변수이기 때문
        • 문자열 생성의 차이(https://ksk9820.tistory.com/135?category=916713 참고)
          • str[]: 배열 안의 값은 바꿀 수 있지만(str[1] = “k”;) str이 전혀다른 배열을 가리키도록 할 수 없다.
          • str: 배열안의 값은 바꿀 수 없지만 str이 전혀 다른 새로운 문자열(str = tmp)을 가리키도록 할 수 있다.

4-3. find(char *name)

void find(char *name){
    int index = search(name);
    if (index == -1)
        printf("No person named '%s' exists.\\n", name);
    else
        printf("%s\\n", numbers[index]);
}

4-4. status()

void status(){
    int i;
    for (i=0; i<n; i++)
        printf("%s %s\\n", names[i], numbers[i]);
    printf("Total %d persons\\n", n);
}

4-5. delete(char *name)

void delete(char *name){
    int index = search(name);
    if (index == -1){
        printf("No person named '%s' exists.\\n", name);
        return;
    }
    int j = index;
    for (;j<n-1;j++){
        names[j] = names[j+1];
        numbers[j] = numbers[j+1];
    }
    n--;
    printf("'%s' was deleted successfully. \\n", name);
}

4-6. save(char *fileName)

void save(char *fileName){
    int i;
    FILE *fp = fopen(fileName, "w");
    if (fp==NULL){
        printf("Open failed.\\n");
        return;
    }
    for(i=0; i<n; i++){
        fprintf(fp, "%s %s\\n", names[i], numbers[i]);
    }
    fclose(fp);
}

 

5. 전체 코드

//  version3.c

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

#define INIT_CAPACITY 3
#define BUFFER_SIZE 50


void init_directory();
void process_command();
int read_line(char str[], int limit);
void add(char * name, char * number);
void find();
void status();
void delete();
void load();
void save();
int search();
void reallocate();

char ** names;
char ** numbers;

int capacity = INIT_CAPACITY;
int n = 0;

char delim[] = " ";

int main(){
    init_directory();
    process_command();
    
    return 0;
}

void init_directory(){
    names = (char **)malloc(INIT_CAPACITY * sizeof(char *));
    numbers = (char **)malloc(INIT_CAPACITY * sizeof(char *));
}

//사용자의 명령을 받아 처리하는 함수
void process_command(){
    char command_line[BUFFER_SIZE];
    char *command, *argument1, *argument2;
    
    while(1){
        printf("$");
        
        if(read_line(command_line, BUFFER_SIZE) <= 0)
            continue;
        command = strtok(command_line, delim);
        if(command == NULL) continue;
        
        if(strcmp(command, "read") == 0){
            //입력받은 하나의 commandline을 연속해서 strtok하기 때문에
            //이후의 strtok에서 첫 번째 매개변수는 null
            argument1 = strtok(NULL, delim);
            if(argument1 == NULL){
                printf("File name required.\n");
                continue;
            }
            load(argument1);
        }
        
        else if (strcmp(command, "add") == 0){
            argument1 = strtok(NULL, delim);
            argument2 = strtok(NULL, delim);
            
            if (argument1 == NULL || argument2 == NULL){
                printf("Invalid arguments.\n");
                continue;
            }
            add(argument1, argument2);
            printf("%s was added successfully.\n", argument1);
        }
        
        else if (strcmp(command, "find") == 0){
            argument1 = strtok(NULL, delim);
            
            if (argument1 == NULL){
                printf("Invalid arguments.\n");
                continue;
            }
            find(argument1);
        }
        
        else if (strcmp(command, "status") == 0)
            status();
        
        else if (strcmp(command, "delete") == 0){
            argument1 = strtok(NULL, delim);
            if (argument1 == NULL){
                printf("Invalid arguments.\n");
                continue;
            }
            delete(argument1);
        }
        
        else if (strcmp(command, "save") == 0){
            argument1 = strtok(NULL, delim);
            argument2 = strtok(NULL, delim);
            
            if (argument1 == NULL || strcmp("as", argument1) != 0 || argument2 == NULL){
                printf("Invalid command format.\n");
                continue;
            }
            save(argument2);
        }
            
        else if (strcmp(command, "exit") == 0)
            break;;
    }
}

int read_line(char str[], int limit){
    int ch, i = 0;
    while ((ch = getchar()) != "\n")
        if (i < limit - 1)
            str[i++] = ch;
    str[i] = '\0';
    
    return i;      
}


void load(char *fileName){
    char buf1[BUFFER_SIZE];
    char buf2[BUFFER_SIZE];
    
    FILE *fp = fopen(fileName, "r");
    if (fp==NULL){
        printf("Open failed.\n");
        return;
    }
    
    while((fscanf(fp, "%s", buf1) != EOF)){
        fscanf(fp, "%s", buf2);
        add(buf1, buf2);
    }
    fclose(fp);
}


void add(char * name, char * number){
    if (n>= capacity)
        reallocate();

    //추가하려는 사람보다 이름이 큰 사람은 한 칸씩 이동시키고
    //그 사이에 새로운 사람을 삽입
    int i = n-1;
    while(i >= 0 && strcmp(names[i], name) >0){
        names[i+1] = names[i];
        numbers[i+1] = numbers[i];
        i--;
    }
    names[i+1] = strdup(name);
    numbers[i+1] = strdup(number);
    
    n++;
    //printf("%s was added successfully.\n", buf1);
    
}

void save(char *fileName){
    int i;
    FILE *fp = fopen(fileName, "w");
    if (fp==NULL){
        printf("Open failed.\n");
        return;
    }
    for(i=0; i<n; i++){
        fprintf(fp, "%s %s\n", names[i], numbers[i]);
    }
    fclose(fp);
}

void find(char *name){
    int index = search(name);
    if (index == -1)
        printf("No person named '%s' exists.\n", name);
    else
        printf("%s\n", numbers[index]);
}

void status(){
    int i;
    for (i=0; i<n; i++)
        printf("%s %s\n", names[i], numbers[i]);
    printf("Total %d persons\n", n);
}

void delete(char *name){
    int index = search(name);
    if (index == -1){
        printf("No person named '%s' exists.\n", name);
        return;
    }
    int j = index;
    for (;j<n-1;j++){
        names[j] = names[j+1];
        numbers[j] = numbers[j+1];
    }
    n--;
    printf("'%s' was deleted successfully. \n", name);
}

int search(char *name){
    int i;
    for (i=0;i<n;i++){
        if(strcmp(name, names[i]) == 0){
            return i;
        }
    }
    return -1;
}

void reallocate(){
    int i;
    
    capacity *= 2;
    char **tmp1 = (char **)malloc(capacity*sizeof(char *));
    char **tmp2 = (char **)malloc(capacity*sizeof(char *));
    
    for (i=0; i<n; i++){
        tmp1[i] = names[i];
        tmp2[i] = numbers[i];
    }
    
    free(names);
    free(numbers);
    
    names = tmp1;
    numbers = tmp2;
}

 

 

 

 

 

---

부경대학교 권오흠 교수님의 [c로 배우는 자료구조 및 여러 가지 예제 실습] 강의 정리입니다. 감사합니다.

https://www.youtube.com/watch?v=Dy_QIKLGQE0&feature=emb_imp_woyt 

https://www.youtube.com/watch?v=Mkfb95X2J-0&feature=emb_imp_woyt 

https://www.youtube.com/watch?v=CdHRiFqmPmM