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

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

2022. 8. 9. 18:42ㆍCS/자료구조

728x90

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

구조체에 대한 포인터, 동적 메모리 할당

구조체의 배열 → 구조체 포인터의 배열

1. C언어에서의 매개 변수 전달 방식

typedef struct person{
    char * name, number, email, group;
} Person;

//Person 타입의 디렉토리 배열 선언
Person directory[CAPACITY];

C언어에서 구조체의 배열은 일반적인 방법이 아니다.

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

void print_person(Person p){
    printf("%s:\\n", p.name);
    printf("  Phone: %s\\n", p.number);
    printf("  Email: %s\\n", p.email);
    printf("  Group: %s\\n", p.group);
}

directory[i]와 Person p는 별개
- status() 함수에서 print_person(directory[i]) 함수를 호출할 때 directory[i]는
  - actual parameter: 실 매개 변수
- void print_person(Person p) 함수에서 Person p는
  - 호출되는 함수의 formal parameter: 형식 매개 변수
call-by-value(pass-by-assignment): 값에 의한 매개 변수 전달 방식
호출 시에 모든 멤버들이 복사된다.
- 단일한 값이 아니라 여러 개의 값을 가지고 있는 구조체 변수
- 복사될 때 각각의 값이 따로 복사 = 복사되는 데이터가 많다.
```
p = directory\[i\]
```
구조체 변수의 return문에서도 동일
- 즉시 return 하는 것 X
- directory → 이름 없는 임시 객체로 복사 → 임시 객체가 리턴되면서 사라지고 → 치환문에 의해 복사됨
- 결국 구조체의 크기가 커지면 프로그램의 성능에 영향을 끼칠 수 있다.
```
void function(){
	Person thePerson = get_person("jungwoo");
}

Person get_person(char *name){
	return directory[i];
}
```

version 4의 add()와 remove()에서도

알파벳 순 정렬을 해야 하기 때문에 모든 구조체들이 다음칸으로 복사되어야 한다.

복사되어야 하는 데이터의 양이 많으면 프로그램의 성능에 영향을 끼칠 수 있다.

void add(char * name, char * number, char * email, char * group){
    //이름 순 정렬
    int i = n-1;
    while (i>=0 && strcmp(directory[i].name, name)>0){
        //구조체 이기 때문에 name, number 배열을 따로 이동할 필요 없이 한 번에 이동
        directory[i+1] = directory[i];
        i--;
    }
}

⇒ 구조체의 배열로 표현하게 되면 구조체의 복사를 피할 수 없다.

2. 구조체의 배열 대신 구조체 포인터의 배열

//Person directory[CAPACITY];
Person * directory[CAPACITY];

배열 directory의 각 칸이 person 타입이 아니라
- struct person 타입 객체의 주소를 저장하는 구조체 포인터 타입의 배열
C언어에서 포인터 변수를 매개변수로 사용해도 call-by-value로 값을 전달하는 것은 동일하다.
- 하지만 함수 호출 과정에서 복사되는 매개변수의 값은 이름, 전화번호 … 이 아니라
  - 주소 값만 복사되기 때문에
    - 복사되는 값이 주소 1개로 매우 적어진다.
    - 구조체의 덩치가 크다고 해서 주소 값의 크기가 커지는 것은 아니다.

//구조체의 배열 때 사용한 print_person 함수
void print_person(Person p){
    printf("%s:\\n", p.name);
    printf("  Phone: %s\\n", p.number);
    printf("  Email: %s\\n", p.email);
    printf("  Group: %s\\n", p.group);
}

//구조체 포인터의 배열을 사용하는 print_person 함수
void print_person(Person *p){
    printf("%s:\\n", (*p).name);
    printf("  Phone: %s\\n", (*p).number);
    printf("  Email: %s\\n", (*p).email);
    printf("  Group: %s\\n", (*p).group);
}

Person p는 하나의 포인터
- 구조체 변수의 주소를 가지고 있는 포인터 p
  - 가 가리키는 값을 출력하기 위해서는 * 사용
    - 즉, p는 포인터, (*p)는 구조체
    - (*p) 괄호를 사용하는 이유: (.) 연산자의 우선순위 > (*) 연산자의 우선순위

⇒ 결론: 구조체의 배열을 구조체의 포인터 배열로 변경하면, 매개변수 전달 과정에서 실제로 전달되는 값이 구조체가 통째로 전달되는 것이 아니라 구조체의 주소 값만 전달된다. 따라서 복사되는 데이터의 양이 줄어든다.

2-1. 새로운 연산자 ->

(*p).name 
p->name

(*p).name과 p->name은 동일한 표현이다.
p가 구조체를 가리키는 포인터 일 때
- p가 가리키고 있는 구조체 안에 있는 어떤 한 필드를 접근할 때
  - (*p).name → p->name 으로 간결하게 표현할 수 있다.
```
void print_person(Person *p){
    printf("%s:\\n", p->name);
    printf("  Phone: %s\\n", p->number);
    printf("  Email: %s\\n", p->email);
    printf("  Group: %s\\n", p->group);
}
```

3. 전화번호부

3-1. 자료구조

#define INIT_CAPACITY 100

typedef struct person{
    char * name;
    char * number;
    char * email;
    char * group;
} Person;

Person **directory;
int capacity;
int n;

3-2. init()

//프로그램이 호출되면 맨 앞에서 init함수 호출, 초기화 작업

void init(){
    directory = (Person **)malloc(INIT_CAPACITY * sizeof(Person*));
    capacity = INIT_CAPACITY;
    n = 0;
}

3-3. load()

//데이터 파일로부터 전화번호부 데이터를 읽어 프로그램 내부로 읽어옴

이름을 제외한 값들이 존재하지 않을 때
- ver 4.0) handle_add() 함수에서 존재하지 않는 값을 “ “, 공백 문자 하나로 구성된 문자열로 대체
- ver 5.0) 존재하지 않는다면 공백 문자 대신 NULL을 대입

void load(char *fileName){
    char buffer[BUFFER_LENGTH];
    char *name, *number, *email, *group;
    char *token;

    FILE *fp = fopen(fileName, "r");
    if (fp == NULL){
        printf("Open failed.\\n");
        return;
    }

    while(1){
        if (read_line(fp, buffer, BUFFER_LENGTH)<=0)
            break;
        name = strtok(buffer, "#");
        token = strtok(NULL, "#");
        //공백문자라면 존재하지 않는 것이므로, number 변수에 Null 대입
        if(strcmp(token, " ") == 0)
            number = NULL;
        else
            number = strdup(token);

        token = strtok(NULL, "#");
        if(strcmp(token, " ") == 0)
            email = NULL;
        else
            email = strdup(token);

        token = strtok(NULL, "#");
        if(strcmp(token, " ") == 0)
            group = NULL;
        else
            group = strdup(token);

        add(strdup(name), number, email, group);
    }
    fclose(fp);
}

3-4. add()

//알파벳 순으로 이름을 추가, 정렬

void add(char *name, char *number, char *email, char *group){
    //새로운 사람을 추가할 공간이 없으면
    //배열 재할당을 해라
    if (n>=capacity)
        reallocate();

    //알파벳순 정렬
    int i = n-1;
    //현재 디렉토리에 저장되어 있는 사람의 이름과 새로 추가하려는 이름과 비교해서
    while(i>=0 && strcmp(directory[i] -> name, name) >  0){
        directory[i+1] = directory[i];
        i--;
    }

    //새로운 사람 저장할 하나의 구조체 객체를 할당받아야함 -> Person
    directory[i+1] = (Person *)malloc(sizeof(Person));

    directory[i+1] -> name = name;
    directory[i+1] -> number = number;
    directory[i+1] -> email = email;
    directory[i+1] -> group = group;

    n++;
}

directory[i+1] = (Person *)malloc(sizeof(Person));
- verson 4.0) directory[i]가 각각의 구조체 변수 ~ 구조체간 복사
- verson 5.0) directory[i]는 포인터 ~ 주소 하나가 복사
  - 포인터 변수의 배열이기 때문에 동적 메모리 할당(malloc)으로 새로운 사람을 저장할 구조체 객체(Person)를 하나(= sizeof(Person)) 할당받아야 함
- malloc이 리턴해주는 것은 새로 생성된 객체의 주소

3-4-1. reallocate()

현재 저장되어 있는 사람의 수 > 현재 디렉토리의 크기
- 새로운 사람을 추가할 공간이 없을 때 재할당

void reallocate(){
    capacity *= 2;
    Person **tmp = (Person **)malloc(capacity*sizeof(Person *));
    for (int i = 0; i<n; i++){
        tmp[i] = directory[i];
    }

    //directory라는 포인터 변수가 현재 가지고 있는
    //메모리 블럭을 다시 시스템에게 돌려준다.
    free(directory);

    //directory 객체 자체가 복사되는 것이 아니라 객체의 주소가 복사되는 것
    directory = tmp;
}

구조체의 배열 대신 구조체 포인터의 배열(= 주소를 저장)을 사용했기 때문에 reallocate 할 때에도 복사되는 데이터(= 주소 값들이 새로운 배열로 복사) 양이 훨씬 적어진다.
- directory = tmp;
  - 객체 자체가 복사되는 것이 아니라 directory 객체가 가지고 있던 주소 값이 복사되는 것이기 때문에 구조체 자체를 복사할 때 보다 복사하는 양이 적다.
  - directory = tmp; 는 디렉토리가 새로운 배열(tmp)을 가리키도록 하는 것
    - 새로운 배열을 가리킨 후에 directory는 어떻게 되는가?([주소값을 모르는 데이터 garbage(참고)])
      - directory라는 포인터 변수가 현재 가리키고 있는 메모리 블락을 다시 시스템에게 돌려준다
        
        malloc으로 동적 메모리 할당을 받은 값은 heap에 저장 ~ heap에 garbage가 쌓이면 heap 용량이 부족해져 프로그램이 정상적으로 실행되지 않을 수 있다 ⇒ free(garbage 주소)
        
        malloc으로 할당받은 메모리는 그 메모리가 필요 없어지면 반드시 free 시켜줘야 한다.
        
        주의할 점) free(directory); 후에 directory = tmp;를 해야 한다. 반대로 할 경우 복사한 주소 값을 free 시킨다.

3-5. delete()

void delete(char *name){
    int i = search(name);
    if(i == -1){
        printf("No person named '%s' exists.\\n", name);
        return;
    }

    Person *p = directory[i];
    for(int j=i ;j<n-1;j++){
        //복사 되는 값 = 배열 directory안에 저장되어 있는 포인터 값
        directory[j] = directory[j+1];
    }
    n--;

    //삭제된 사람의 정보를 저장하고 있는 Person 객체를 free 시켜줘야 함
    //Person 객체: malloc으로 할당 받은 메모리
    release_person(p);
    printf("'%s was deleted successfully. \\n", name);
}

free(p) 대신 release_person(p)를 사용하는 이유
- 구조체 Person내의 name, number, email, group 문자열도 동적 메모리 할당으로 할당된 메모리이기 때문에 free 할 때 구조체 안에 매달린 문자열 모두를 free 해줘야 함

3-5-1. release_person()

void relese_person(Person *p){
    free(p ->name);
    //NULL인 경우에는 free 시킬 필요 없기 때문
    if (p -> number != NULL) free(p -> number);
    if (p -> email != NULL) free(p -> email);
    if (p -> group != NULL) free(p -> group);
    free(p);
}

strdup을 호출해 만든 string들(load 함수 참고)도 free해줘야 함
- strdup는 malloc으로 메모리를 할당하기 때문에

4. main 등

main함수는 처음에 init()을 호출해주는 것을 제외하면 v4와 동일
read_line, compose_name은 v4와 동일
save, search, print_person, status, find, handle_add는 변경된 자료구조와 add 함수에 맞게 프로그램의 나머지 부분을 수정
- v4와 다르게 존재하지 않는 항목들은 null로 저장
임의로 수정한 전체 코드입니다. 참고만 바랍니다.

//  version5.c
//  자료구조

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INIT_CAPACITY 100
#define BUFFER_LENGTH 100



typedef struct person{
    char * name;
    char * number;
    char * email;
    char * group;
} Person;



void load(char *fileName);
int read_line(FILE *fp, char str[], int n);
void add(char * name, char * number, char * email, char * group);
void reallocate();
void delete(char * name);
int search(char *name);
void release_person(Person *p);
int read_line(FILE *fp, char str[], int n);
int compose_name(char str[], int limit);
void save(char *fileName);
int search(char *name);
void print_person(Person *p);
void handle_add(char * name);
void status();
void find(char *name);
void init();



Person **directory;
int capacity;
int n;



int main(){
    init();

    char command_line[BUFFER_LENGTH];
    char *command, *argument;
    char name_str[BUFFER_LENGTH];

    while (1){

        printf("$ ");
        //read_line은 자신이 읽은 문자수를 리턴
        //0보다 작으면 사용자가 아무것도 입력하지 않고 enter key를 누른 것
        //키보드 입력은 stdin
        if (read_line(stdin, command_line, BUFFER_LENGTH)<=0)
            continue;


        command = strtok(command_line, " ");

        if (strcmp(command, "read") == 0){
            argument = strtok(NULL, " ");
            if(argument == NULL){
                printf("Invalid arguments.\n");
                continue;
            }
            load(argument);
        }
        else if (strcmp(command, "add") == 0){
            if(compose_name(name_str, BUFFER_LENGTH) <= 0){
                printf("Name required.\n");
                continue;
            }
            handle_add(name_str);
        }
        else if (strcmp(command, "find") == 0){
            if(compose_name(name_str, BUFFER_LENGTH) <= 0){
                printf("Name required.\n");
                continue;
            }
            find(name_str);
        }
        else if (strcmp(command, "status") == 0){
            status();
        }
        else if (strcmp(command, "delete") == 0){
            if(compose_name(name_str, BUFFER_LENGTH) <= 0){
                printf("Invalid arguments.\n");
                continue;
            }
            delete(name_str);
        }
        else if (strcmp(command, "save") == 0){
            argument = strtok(NULL, " ");
            if (strcmp(argument, "as") != 0){
                printf("Invalid argments.\n");
                continue;
            }
            argument = strtok(NULL, " ");
            if(argument == NULL){
                printf("Invalid arguments.\n");
                continue;
            }
            save(argument);
        }
        else if (strcmp(command, "exit") == 0)
            break;
    }
    return 0;
}



//프로그램이 호출되면 맨 앞에서 init함수 호출, 초기화 작업
void init(){
    directory = (Person **)malloc(INIT_CAPACITY * sizeof(Person*));
    capacity = INIT_CAPACITY;
    n = 0;
}



void load(char *fileName){
    char buffer[BUFFER_LENGTH];
    char *name, *number, *email, *group;
    char *token;

    FILE *fp = fopen(fileName, "r");
    if (fp == NULL){
        printf("Open failed.\n");
        return;
    }

    while(1){
        if (read_line(fp, buffer, BUFFER_LENGTH)<=0)
            break;
        name = strtok(buffer, "#");
        token = strtok(NULL, "#");
        //공백문자라면 존재하지 않는 것이므로, number 변수에 Null 대입
        if(strcmp(token, " ") == 0)
            number = NULL;
        else
            number = strdup(token);

        token = strtok(NULL, "#");
        //공백문자라면 존재하지 않는 것이므로, number 변수에 Null 대입
        if(strcmp(token, " ") == 0)
            email = NULL;
        else
            email = strdup(token);

        token = strtok(NULL, "#");
        //공백문자라면 존재하지 않는 것이므로, number 변수에 Null 대입
        if(strcmp(token, " ") == 0)
            group = NULL;
        else
            group = strdup(token);

        add(strdup(name), number, email, group);
    }
    fclose(fp);
}



int read_line(FILE *fp, char str[], int n){
    int ch, i = 0;
    while((ch = fgetc(fp)) != '\n' && ch != EOF){
        if (i<n)
            str[i++] = ch;
    }
    str[i] = '\0';
    return i;
}


int compose_name(char str[], int limit){
    char * ptr;
    int length = 0;

    ptr = strtok(NULL, " ");
    if(ptr == NULL)
        return 0;
    strcpy(str, ptr);
    length += strlen(ptr);

    while((ptr = strtok(NULL, " ")) != NULL){
        if(length + strlen(ptr) + 1 < limit){
            str[length++] = ' ';
            str[length] = NULL;
            strcat(str, ptr);
            length += strlen(ptr);
        }
    }
    return length;
}


void add(char *name, char *number, char *email, char *group){
    //새로운 사람을 추가할 공간이 없으면
    //배열 재할당을 해라
    if (n>=capacity)
        reallocate();

    //알파벳순 정렬
    int i = n-1;
    while(i>=0 && strcmp(directory[i] -> name, name) >0){
        directory[i+1] = directory[i];
        i--;
    }

    //새로운 사람 저장할 하나의 구조체 객체를 할당받아야함 -> Person
    directory[i+1] = (Person *)malloc(sizeof(Person));

    directory[i+1] -> name = name;
    directory[i+1] -> number = number;
    directory[i+1] -> email = email;
    directory[i+1] -> group = group;

    n++;
}


void handle_add(char * name){
    char number[BUFFER_LENGTH], email[BUFFER_LENGTH], group[BUFFER_LENGTH];
    char empty[] = " ";

    printf("  Phone: ");
    read_line(stdin, number, BUFFER_LENGTH);
    printf("  Email: ");
    read_line(stdin, email, BUFFER_LENGTH);
    printf("  Group: ");
    read_line(stdin, group, BUFFER_LENGTH);

    add(strdup(name), strdup((char *)(strlen(number) > 0 ? number : empty)), strdup((char *)(strlen(email) > 0 ? email : empty)), strdup((char *)(strlen(group) > 0 ? group : empty)));
}

void reallocate(){
    capacity *= 2;
    Person **tmp = (Person **)malloc(capacity*sizeof(Person *));
    for (int i = 0; i<n; i++){
        tmp[i] = directory[i];
    }
    free(directory);
    directory = tmp;
}




void delete(char *name){
    int i = search(name);
    if(i == -1){
        printf("No person named '%s' exists.\n", name);
        return;
    }

    Person *p = directory[i];
    for(int j=i ;j<n-1;j++){
        //복사 되는 값 = 배열 directory안에 저장되어 있는 포인터 값
        directory[j] = directory[j+1];
    }
    n--;

    //삭제된 사람의 정보를 저장하고 있는 Person 객체를 free 시켜줘야 함
    //Person 객체: malloc으로 할당 받은 메모리
    release_person(p);
    printf("'%s was deleted successfully. \n", name);
}

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

void release_person(Person *p){
    free(p ->name);
    //NULL인 경우에는 free 시킬 필요 없기 때문
    if (p -> number != NULL) free(p -> number);
    if (p -> email != NULL) free(p -> email);
    if (p -> group != NULL) free(p -> group);
    free(p);
}


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

void print_person(Person *p){
    printf("%s:\n", p->name);
    printf("  Phone: %s\n", p->number);
    printf("  Email: %s\n", p->email);
    printf("  Group: %s\n", p->group);
}

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



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#", directory[i]->name);
        fprintf(fp, "%s#", directory[i]->number);
        fprintf(fp, "%s#", directory[i]->email);
        fprintf(fp, "%s#\n", directory[i]->group);
    }
    fclose(fp);
}

5. 출력

$ add yj
  Phone: 010
  Email: email1
  Group: txt
$ add jw
  Phone: 01011
  Email: 
  Group: nct
$ status
jw:
  Phone: 01011
  Email:  
  Group: nct
yj:
  Phone: 010
  Email: email1
  Group: txt
Total 2 persons.
$ delete jw
'jw was deleted successfully. 
$ find yj
yj:
  Phone: 010
  Email: email1
  Group: txt
$ add jjj      www
  Phone: 
  Email: 
  Group: 
$ status
jjj www:
  Phone:  
  Email:  
  Group:  
yj:
  Phone: 010
  Email: email1
  Group: txt
Total 2 persons.
$ delete yj
'yj was deleted successfully. 
$ status
jjj www:
  Phone:  
  Email:  
  Group:  
Total 1 persons.
$

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

https://www.youtube.com/watch?v=2UG_ZjGhWOs

https://www.youtube.com/watch?v=1iGhHmaIqGY