C언어 콘서트 14장 동적 메모리 Programming 문제

안녕하세요. 이번에는 C언어 콘서트의 마지막 장인 14장인 동적 메모리 문제를 풀어보았습니다. 그 전 장들에 대한 문제의 링크는 아래에 있습니다. 

2018/11/21 - [IT 공부 및 일상] - C언어 콘서트 9장 포인터 Programming 문제

2018/11/22 - [IT 공부 및 일상] - C언어 콘서트 10장 문자와 문자열 Programming 문제

2018/11/25 - [IT 공부 및 일상] - C언어 콘서트 11장 구조체 Programming 문제

2018/11/29 - [IT 공부 및 일상] - C언어 콘서트 12장 표준 입출력과 파일 입출력 Programming 문제

2018/12/11 - [IT 공부 및 일상] - C언어 콘서트 13장 전처리 및 기타 기능 Programming 문제

1번 문제

1번 메뉴에 해당하는 입력한 크기의 동적 배열을 생성하는 부분을 제외한 다른 메뉴들은 각각 함수로 정의하여서 구현하였습니다. 

#include<stdio.h>
#include<stdlib.h>
 
typedef struct NODE {
    int rand_num;
    struct NODE *link;
}NODE;
 
// 2번 메뉴에 해당하는 함수
void fill_rndm_dnmc_array(NODE *p, NODE *list) {
    NODE *next;
    p = list;
 
    while (p != NULL) {
        next = p->link;
        p->rand_num = rand();
        p = next;
    }
}
 
// 3번 메뉴에 해당하는 함수
void print_dnmc_array(NODE *p, NODE *list) {
    NODE *next;
    int num = 1;
    p = list;
 
    while (p != NULL) {
        next = p->link;
        printf("%d번째 배열의 원소: %d\n", num, p->rand_num);
        p = next;
        num++;
    }
}
 
// 4번 메뉴에 해당하는 함수
void print_sum_dnmc_array(NODE *p, NODE *list) {
    NODE *next;
    int sum = 0;
    p = list;
 
    while (p != NULL) {
        next = p->link;
        sum += p->rand_num;
        p = next;
    }
 
    printf("배열의 각 원소들의 합: %d\n", sum);
}
 
// 5번 메뉴에 해당하는 함수
void return_memory_dnmc_array(NODE *p, NODE *list) {
    NODE *next;
    p = list;
 
    while (p != NULL) {
        next = p->link;
        free(p);
        p = next;
    }
}
 
void iterated_printline(void) {
    printf("==============================\n");
    printf("1. 크기가 n인 동적 배열을 생성\n");
    printf("2. 배열을 난수로 채운다.\n");
    printf("3. 배열의 각 원소를 출력한다.\n");
    printf("4. 배열의 각 원소들의 합을 출력한다.\n");
    printf("5. 동적 할당 공간을 반납한다.\n");
    printf("==============================\n");
}
 
int main(void) {
    NODE *list = NULL;
    NODE *p = NULL, *prev = NULL;
    int choice, size;
 
    while (1) {
        iterated_printline();
        printf("메뉴를 선택하시오(-1: 종료): ");
        scanf("%d", &choice);
 
        if (choice == -1) break;
 
        switch (choice) {
            case 1:
                printf("크기 n을 입력하시오: ");
                scanf("%d", &size);
 
                while (size--) {
                    p = (NODE *)malloc(sizeof(NODE));
                    p->rand_num = 0;
 
                    if (list == NULL)
                        list = p;
                    else
                        prev->link = p;
 
                    p->link = NULL;
                    prev = p;
                }
                break;
            case 2:
                fill_rndm_dnmc_array(p, list);
                break;
            case 3:
                print_dnmc_array(p, list);
                break;
            case 4:
                print_sum_dnmc_array(p, list);
                break;
            case 5:
                return_memory_dnmc_array(p, list);
                break;
            default:
                printf("올바른 값을 입력하시오!\n");
                break;
        }
    }
    return 0;
}

2번 문제

정수에 해당하는 숫자를 입력할 때 마다 전에 만들어 놓았던 노드의 링크에 이번에 메모리를 할당받은 노드의 주소를 추가하고 종료를 나타내는 -1을 입력하였을 때 반복문을 빠져나와 리스트를 출력합니다.

#include<stdio.h>
#include<stdlib.h>
 
typedef struct NODE {
    int num;
    struct NODE* link;
}NODE;
 
int main(void) {
    NODE *p, *next;
    NODE *list = NULL, *prev = NULL;
    int input_num;
 
    while (1) {
        printf("양의 정수를 입력하시오(종료: -1): ");
        scanf("%d", &input_num);
 
        if (input_num == -1) break;
 
        p = (NODE *)malloc(sizeof(NODE));
        p->num = input_num;
 
        if (list == NULL)
            list = p;
        else
            prev->link = p;
 
        p->link = NULL;
        prev = p;
    }
 
    p = list;
    while (p != NULL) {
        next = p->link;
        printf("%d->", p->num);
        p = next;
    }
 
    printf("NULL");
 
    p = list;
    while (p != NULL) {
        next = p->link;
        free(p);
        p = next;
    }
 
    return 0;
}

3번 문제

메모리를 할당받아 숫자를 입력한 노드를 그 전까지 입력받았던 노드들의 리스트와 비교를 해야하는데 만약 리스트에 두 개의 노드가 있다고 하고 경우의 수를 살펴보면 크게 3가지로 나뉘어집니다. 값이 리스트의 첫 번째 노드보다 작아서 첫 번째 노드가 되는 경우와 리스트의 첫 번째와 두 번째 노드 사이에 위치하는 경우, 리스트의 두 번째 노드 보다 커서 마지막 노드가 되는 경우로 말입니다.

그래서 조건을 크게 현재 입력받은 노드의 필드인 숫자가 리스트의 노드들의 숫자들 보다 클 경우와 작은 경우로 나누고 만약 클 경우에는 현재의 노드가 비교한 리스트의 노드 보다 뒤에 위치하니 비교하는 노드의 주소를 기억해야합니다. 

작을 경우에는 내림차순 정렬 방식이니 이제 더 이상 리스트의 노드들과 비교를 하지 않아도 됩니다. 그래서 현재의 노드의 필드 링크에 비교한 노드의 주소를 대입하고 반복을 끝내면 됩니다. 이때 비교한 노드가 리스트의 첫 번째인 경우에는 현재의 노드를 헤더포인터에 대입시킵니다.

#include<stdio.h>
#include<stdlib.h>
 
typedef struct __node {
    int num;
    struct __node *link;
}NODE;
 
int main(void) {
    NODE *p, *next, *crnt, *prev_pstn = NULL;
    NODE *prev = NULL, *list = NULL;
    int input, first, end, nend;
 
    while (1) {
        end = 0, nend = 0;
        printf("NULL\n");
 
        printf("정수를 입력하시오(종료: -1): ");
        scanf("%d", &input);
 
        p = (NODE *)malloc(sizeof(NODE));
        p->num = input;
 
        //초기상태에 값 하나 추가
        if (list == NULL) {
            list = p;
            p->link = NULL;
        }
 
        //값이 두개부터 시작됨
        else {
            first = list->num;
            crnt = list;
 
            while (crnt != NULL) {
                next = crnt->link;
 
                // 연결리스트의 값보다 클 때
                if (p->num > crnt->num) {
                    prev_pstn = crnt;
                }
 
                // 연결리스트의 값보다 작을 때
                else if (p->num < crnt->num) {
                    p->link = crnt;                
 
                    // 연결리스트의 처음 값보다 작을 때
                    if (crnt->num == first) {
                        list = p;
                        break;
                    }
 
                    nend = 1;
                    break;
                }
 
                crnt = next;
 
                if (crnt == NULL)
                    end = 1;
            }
 
            if (end) {
                p->link = NULL;
                prev_pstn->link = p;
            }
 
            if (nend)
                prev_pstn->link = p;
        }
 
        p = list;
        // 할당한 메모리 해제
        if (input == -1) {
 
            while (p != NULL) {
                next = p->link;
                free(p);
                p = next;
            }
 
            break;
        }
 
        // 연결리스트 값 출력
        while (p != NULL) {
            next = p->link;
            printf("%d -> ", p->num);
            p = next;
        }
    }
 
    return 0;
}

4번 문제

3번 문제의 연장선에 있는 문제로 비교하는 값이 숫자가 아니라 알파벳 문자라는 점입니다. 알파벳 문자를 비교하기 위해서 저는 알파벳의 대문자와 소문자들을 "AaBbCcDd~" 순으로 나열한 배열을 이용하였는데 이를 통해서 문자를 숫자로 변환시켰습니다. 만약 문자가 a와 A이면 0으로 b와 B이면 1로 말입니다.

이렇게 알파벳 문자를 변환시킨 숫자로 현재의 노드와 리스트의 노드들의 문자를 비교할 수 있는데 여기서 영문자 이름들을 숫자들로 변환시킨 값으로 생각해보면 James는 90-12-4-18이고 Jane은 90-13-4가 될 것입니다. James와 Jane은 두 번째 숫자까지는 동일하고 세 번째 숫자가 다른데 값이 처음부터 다를 수도 있지만 예시를 든 것처럼 값이 같다가 달라 질 수도 있습니다.  

그러므로 조건을 맨 처음에 같은지를 검사하고 같지 않은 경우를 현재의 노드가 작은 경우와 큰 경우를 검사를 하였습니다. 같은 경우의 상태와 다른 상태들은 int형의 변수들에 1을 주어서 구분하였습니다.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
#define SIZE 20
 
typedef struct _phn_info{
    char _phn_name[SIZE];
    char _phn_num[13];
    struct _phn_info *link;
}PHN_INFO; 
 
// 3번 탐색용 함수
int search_phn_info(PHN_INFO *list) {
    PHN_INFO *p, *next;
    char srch_name[SIZE];
 
    printf("탐색하려는 이름을 입력하세요: ");
    gets(srch_name);
    rewind(stdin);
 
    p = list;
    while (p != NULL) {
        next = p->link;
 
        if (strcmp(srch_name, p->_phn_name) == 0)
            return 1;
 
        p = next;
    }
 
    return 0;
}
 
// 4번 변경용 함수
int change_phn_info(PHN_INFO *list) {
    PHN_INFO *p, *next;
    char chng_name[SIZE];
 
    printf("변경하려는 이름을 입력하세요: ");
    gets(chng_name);
    rewind(stdin);
 
    p = list;
    while (p != NULL) {
        next = p->link;
 
        if (strcmp(chng_name, p->_phn_name) == 0) {
            printf("변경할 이름을 입력하세요: ");
            gets(p->_phn_name);
            rewind(stdin);
            printf("변경할 번호를 입력하세요: ");
            gets(p->_phn_name);
            rewind(stdin);
        }
 
        p = next;
    }
 
    return 0;
}
 
void print_phn_info(PHN_INFO *list) {
    PHN_INFO *p, *next;
    int count = 1;
 
    p = list;
    while (p != NULL) {
        next = p->link;
 
        printf("<%d번째>\n", count);
        printf("이름: %s\n", p->_phn_name);
        printf("번호: %s\n", p->_phn_num);
 
        count++;
        p = next;
    }
}
 
// 알파벳을 숫자 인덱스로 변환
int convert_to_index(char c){
    char alphabet[] = "AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz";
    int i;
    
    for(i = 0; i < 52; i++){
        if(c == alphabet[i])
            return i/2;
    }
    
    return -1;
}
 
int main(void){
    PHN_INFO *p, *next, *crnt, *prev_val = NULL;
    PHN_INFO *list = NULL;
    int num, i, crnt_num, p_num, bad_input, end, nend, fnsh, same;
    char first[SIZE];
    
    while(1){
        bad_input = 0, end = 0, nend = 0, fnsh = 0, same = 0;
        
        printf("연결 리스트를 이용한 전화번호부 메뉴\n");
        printf("------------------------------\n");
        printf("1. 초기화\n");
        printf("2. 전화번호 추가\n");
        printf("3. 전화번호 탐색\n");
        printf("4. 전화번호 변경\n");
        printf("5. 종료\n");
        printf("------------------------------\n");
        
        printf("번호를 입력하세요: ");
        scanf("%d", &num);
        rewind(stdin);
        
        switch(num){
            case 1:
                // 초기화하기:메모리반납 후 헤더포인터 비우기
                if (list != NULL) {
                    p = list;
 
                    while (p != NULL) {
                        next = p->link;
                        free(p);
                        p = next;
                    }
 
                    list = NULL;
                }
 
                p = (PHN_INFO*)malloc(sizeof(PHN_INFO));
                
                printf("이름: ");
                gets(p->_phn_name);
                rewind(stdin);
                printf("번호: ");
                gets(p->_phn_num);
                rewind(stdin);
 
                list = p;
                p->link = NULL;            
                    
                break;
 
            case 2:
                p = (PHN_INFO*)malloc(sizeof(PHN_INFO));
                printf("이름: ");
                gets(p->_phn_name);
                rewind(stdin);
                printf("번호: ");
                gets(p->_phn_num);
                rewind(stdin);
                
                crnt = list;
                strcpy(first, list->_phn_name);
                
                while(crnt != NULL){
                    next = crnt->link;
                    
                    for(i = 0; i<SIZE; i++){
                        p_num = convert_to_index(p->_phn_name[i]);
                        crnt_num = convert_to_index(crnt->_phn_name[i]);
                        
                        if (p->_phn_name[i] == '\0' || crnt->_phn_name[i] == '\0') {
                            same = 1;
                            break;
                        }
 
                        if(p_num == -1 || crnt_num == -1){
                            bad_input = 1;
                            break;
                        }
                        
                        if(p_num > crnt_num){
                            prev_val = crnt;
                            break;    
                        }
                        
                        else if(p_num < crnt_num){
                            p->link = crnt;
                            
                            if(strcmp(first, crnt->_phn_name) == 0){
                                list = p;
                                fnsh = 1;
                                break;
                            }
                            
                            nend = 1;
                            break;
                        }
                    }
                    // 값이 마지막자리를 제외하고 일치할 경우
                    if (same) {
                        if (!(crnt->_phn_name[i] != '\0' && p->_phn_name[i] == '\0'))
                            prev_val = crnt;
 
                        else {
                            p->link = crnt;
 
                            if (strcmp(first, crnt->_phn_name) == 0) {
                                list = p;
                                fnsh = 1;
                                break;
                            }
 
                            nend = 1;
                            break;
                        }
                    }
 
                    if(bad_input)
                        break;
                    
                    if(fnsh)
                        break;
 
                    if (nend)
                        break;
 
                    crnt = next;
                    if(crnt == NULL)
                        end = 1;
                }
                    
                if(bad_input == -1)
                    printf("잘못된 값이 포함되었습니다.\n");
 
                if(end){
                    prev_val->link = p;
                    p->link = NULL;    
                }
 
                if(nend)
                    prev_val->link = p;
                
                break;
 
            case 3:
                if (search_phn_info(list))
                    printf("해당하는 이름이 존재합니다.\n");
                else
                    printf("해당하는 이름이 존재하지 않습니다.\n");
 
                print_phn_info(list);
                break;
 
            case 4:
                if (!change_phn_info)
                    printf("해당하는 이름이 존재하지 않습니다.\n");
                break;
 
            case 5:
                return 1;
 
            default:
                printf("올바른 값을 입력하시오\n");
                break;
        }
    }
    
    return 0;
}
 

5번 문제

책의 제목과 연도 그리고 이어질 노드의 주소를 가리키는 자기참조 포인터를 포함하는 구조체를 만들어서 사용하였습니다.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
typedef struct book_info {
    char title[20];
    char year[5];
    struct book_info *link;
}BOOK_INFO;
 
void insert_book_info(BOOK_INFO *p) {
    printf("책의 제목을 입력하시오: ");
    gets(p->title);
    rewind(stdin);
    printf("책의 출판 연도를 입력하시오: ");
    gets(p->year);
    rewind(stdin);
}
 
void print_book_info(BOOK_INFO* list) {
    BOOK_INFO *p, *next;
    int count = 1;
 
    p = list;
    while (p != NULL) {
        next = p->link;
 
        printf("\n");
        printf("<%d번째>\n", count);
        printf("책의 제목: %s\n", p->title);
        printf("책의 출판 연도: %s\n", p->year);
        printf("\n");
 
        count++;
        p = next;
    }
}
 
void return_memory(BOOK_INFO* list) {
    BOOK_INFO *p, *next;
 
    p = list;
    while (p != NULL) {
        next = p->link;
        free(p);
        p = next;
    }
}
 
int main(void) {
    BOOK_INFO *p;
    BOOK_INFO *list = NULL, *prev = NULL;
    int num;
    
    while (1) {
        printf("------------------------------\n");
        printf("1. 추가\n");
        printf("2. 출력\n");
        printf("3. 종료\n");
        printf("------------------------------\n");
 
        printf("번호를 입력하시오: ");
        scanf("%d", &num);
        rewind(stdin);
 
        switch (num) {
            case 1:
                p = (BOOK_INFO*)malloc(sizeof(BOOK_INFO));
                insert_book_info(p);
 
                if (list == NULL)
                    list = p;
                else
                    prev->link = p;
 
                p->link = NULL;
                prev = p;
                break;
 
            case 2:
                print_book_info(list);
                break;
 
            case 3:
                return_memory(list);
                return 1;
 
            default:
                printf("올바른 값을 입력하세요!\n");
                break;
        }
    }
 
    return 0;
}