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

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

 

1. 자료구조

• 프로그램에서 사용되는 data들을 어디에 어떤 구조로 저장할 것인지
• 어떤 자료구조가 필요한지?
  • 어떤 data를 다루는지에 따라
  • 복습) 배열을 사용하는데 필요한 3가지 요소
    • 배열의 이름
    • 배열의 크기
    • 배열의 타입: 각 칸에 저장되는 데이터의 타입
      • 전화번호부의 이름: names의 문자열의 각 칸은 John과 같은 이름의 주소를 가리키고 있다.
        • char * names[100];
      • 전화번호부의 번호: numbers의 문자열의 각 칸은 01012345678과 같은 문자열의 주소를 가리키고 있다.
        • char * numbers[100];

 

2. 전화번호부 v1.0

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

#define CAPACITY 100
#define BUFFER_SIZE 20

char * names[CAPACITY];
char * numbers[CAPACITY];
int n = 0;

//뒤에 작성할 함수들의 프로토타입을 main함수 앞에 나열
void add();       //전화번호부에 사람 추가
void find();      //전화번호부에 있는 사람을 검색
void status();    //전화번호부의 상태 조회
void delete();    //전화번호부에 사람 삭제

int main(){
    char command[BUFFER_SIZE];
    while(1){
        printf("$ ");
        scanf("%s", command);
        
        if (strcmp(command, "add") == 0)
            add();
        else if (strcmp(command, "find") == 0)
            find();
        else if (strcmp(command, "status") == 0)
            status();
        else if (strcmp(command, "delete") == 0)
            delete();
        else if (strcmp(command, "exit") == 0)
            break;;
    }
    return 0;
}

2-1. add()

void add(){
    char buf1[BUFFER_SIZE], buf2[BUFFER_SIZE];    //지역변수 buf1, buf2
    scanf("%s", buf1);
    scanf("%s", buf2);
    
    names[n] = strdup(buf1);                      //strdup와 strcpy
    numbers[n] = strdup(buf2);
    n++;
    printf("%s was added successfully.\\n", buf1);
}

• add() 함수에서 buf1, buf2는 지역변수이다.
  • 속해 있는 함수가 호출되는 순간 만들어지고 함수가 return 되어 끝나면 지역변수는 사라진다. → strdup를 사용
• strcpy대신 strdup를 사용하는 이유

//strdup는 string.h 라이브러리가 제공하는 함수이기 때문에 직접구현할 필요는 없다. - 참조만
char * strdup(char *s){
	char *p;
	//새로운 배열을 동적 메모리 할당으로 할당 받음
	p = (char *)malloc(strlen(s)+1);    //null을 포함하기 때문에 strlen + 1
	if (p != NULL)
	//원래 배열의 값 s(null 포함)를 새로운 배열 p로 복사
    	strcpy(p,s);                      
	return p;    //새로운 배열의 시작 주소를 리턴
}

• • buf1과 buf2는 스택에 할당된 메모리이므로(= 지역변수) add함수가 return 되고 나면 소멸된다. 따라서 프로그램 중에 계속 유지되는 문자열인 names에 배열의 주소를 저장하기 위해서는 지역변수인 buf1과 buf2의 주소가 아닌 
    → add함수가 종료된 후에도 소멸하지 않는 strdup함수 내에서 malloc으로 (heap에) 할당받아서 값을 복사한 새로운 문자열의 주소를 저장해야 한다.

 

2-1-1. C언어에서 메모리 관리

C 프로그램이 data를 저장하기 위해 사용하는 메모리는 크게 3가지의 형태를 가진다.

• 전역변수(global variable)
  • 함수의 외부에 선언된 변수들(= 어떤 함수에도 속해있지 않음)
  • 프로그램이 시작될 때 메모리가 할당되며, 종료될 때까지 유지
  • Data section이라고 부르는 메모리 영역에 위치
• 지역변수(local variable)
  • 함수의 내부에 선언된 변수들
  • 자신이 속한 함수가 호출될 때 메모리가 할당되며 함수가 return 될 때 소멸
  • 스택(stack)이라고 부르는 영역에 위치
• 동적 메모리 할당(dynamic memory allocation)
  • 아무 때나 malloc 등의 함수를 호출하여 필요한 크기의 메모리를 할당할 수 있다
    • 동적 메모리 할당이라고 함
  • 힙(heap)이라고 부르는 영역에 위치
  • 동적으로 할당된 메모리는 명시적으로 free() 함수를 호출하여 반환하지 않는 한 계속 유지된다.
    • 내부에서 할당받았다 한들 내부에 국한되지 않음
    • 내부 함수가 return, 종료되더라도 그 메모리는 계속해서 사용할 수 있다.
• C언어에서 메모리 레이아웃(=메모리가 어떤 구조를 가지고 있는지)
  • 프로그램이 실행되면 일정한 크기의 메모리가 할당됨

2-2. find()

void find(){
    char buf[BUFFER_SIZE];
    scanf("%s", buf);
    
    int i;
    for (i=0; i<n; i++){
        if (strcmp(buf, names[i])==0){
            printf("%s\\n", numbers[i]);
            return;
        }
    }
    printf("No person named '%s' exists.\\n", buf);
}

2-3. 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);
}

2-4. delete()

void delete(){
    char buf[BUFFER_SIZE];
    scanf("%s", buf);
    
    int i;
    for (i=0; i<n; i++){
        if(strcmp(buf, names[i])==0){  //삭제할 사람을 찾았다
            names[i] = names[n-1];
            numbers[i] = numbers[n-1];
            n--;
            printf("'%s' was deleted successfully. \\n", buf);
            return;
        }
    }
    printf("No person named '%s' exists.\\n", buf);
}

• 일치하는 부분을 찾아 삭제하고 그냥 빈칸으로 남겨두면 다른 함수들에 문제가 생길 수 있다.(n명에 빈칸이 없다고 가정한 상태이므로)
  • (n-1) 번째를 i번째로 옮겨라!
    • names[i] = names[n-1];
    • numbers[i] = numbers[n-1];
    • n—;

3. 출력

$ add Jungwoo 01022223333
Jungwoo was added successfully.
$ add Jay 01044445555
Jay was added successfully.
$ add FullSun 4839103394
FullSun was added successfully.
$ find Mark
No person named 'Mark' exists.
$ find FullSun
4839103394
$ status
Jungwoo 01022223333
Jay 01044445555
FullSun 4839103394
Total 3 persons
$ delete Jay
'Jay' was deleted successfully. 
$ delete jw
No person named 'jw' exists.
$ delete FullSun
'FullSun' was deleted successfully. 
$ status
Jungwoo 01022223333
Total 1 persons
$ exit
Program ended with exit code: 0

 

 

 

 

---

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

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

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