20210527(수)

1. 학습 날짜 : 20210527(수)

2. 학습 시간 : 14:00 ~ 18:00

3. 학습 주제 : push_swap 초기 단계 프로그래밍 + 알고리즘 설계

4. 동료 학습 방법 : 4인 ( slack 에서 복사 )

5. 학습 목표 :

push_swap 초기 단계 프로그래밍

큰 그림 + 함수 모듈화
circular doubly linked list 설계
- Push, Pop
- 구조체 설계
명령어 8개 설계

MakeFile 과 libft 라이브러리 연결

push_swap 알고리즘 설계

6. 학습 내용 :

📦push_swap
 ┣ 📂.git
 ┣ 📂includes
 ┃ ┣ 📜linked_list.h
 ┃ ┗ 📜push_swap.h
 ┣ 📂libft
 ┃ ┣ 📜Makefile
 ┃ ┣ 📜ft_atol.c
 ┃ ┣ 📜ft_print_error.c
 ┃ ┗ 📜libft.h
 ┣ 📂srcs
 ┃ ┣ 📜arg_input.c
 ┃ ┣ 📜inst.c
 ┃ ┣ 📜linked_list.c
 ┃ ┗ 📜rough.c
 ┣ 📜.gitignore
 ┣ 📜Makefile
 ┗ 📜README.md

지금까지의 대략적인 file tree는 위와 같으며,

libft 라이브러리에 malloc 실패시 errror 를 띄우는 ft_print_error.c ,
long형 number 를 representate 하는 argv를 인자로 받아 char *형을 long으로 바꿀 수 있도록, 기존에는 존재하지 않았던 ft_atol함수를 따로 만들어줬다.

linked_list.h에는 node구조체와 linked_list 구조체가 존재하며,

Linked_list를 초기화하고, 사용될 가장 기본적인 연산인 push, pop, delete를 구현했다.

Push, pop, delete 는 아직 검증이 필요한 단계이며, 오늘중으로 검증할 예정이다.

int        main(int argc, char **argv)
{
    t_ll    **ab_array;

    if (init_linked_list(&ab_array) == -1)
        return (-1);
    printf("initialized\n");
    if (input_args(ab_array, argc - 1, argv) == -1)
        return (-1);    //검사, 에러, 스택 A에 넣어줘야됨.
    return(0);
}

ab_array는, linked_list 구조체 2개를 배열로 묶기 위해 필요한 변수이며,

추후 instruction들을 사용해 linked_list의 함수를 사용해 연결리스트의 연산을 할 떄

비슷한 연산을 두개의 함수로 만들지 않도록 해줬다.

ex ) ra, rb, rr , sa, sb, ss

init_linked_list() : 연결리스트 자료구조를 초기화하여, 초기 동적할당을 한다.

input_args() : 인자들을 받아서 해당 인자들이

숫자인지
int 범위를 넘는지
중복되는 숫자가 들어왔는지

를 검사하며, 만약, 위와 같은 상황이 발생하였을때는, (-1)을 반환하고, 함수 밖에서는 (-1)을 받으면 동적할당해준 모든 자료구조를 free한다.

free_ab_array() : input_args() 에서 (-1)을 반환했을 떄, 동적할당해준 모든 메모리를 할당 해제 시켜준다.

int        main(int argc, char **argv)
{
    t_ll    **ab_array;

    if (argc == 1)
        return (0);
    if (init_linked_list(&ab_array) == -1)
        return (-1);
    printf("initialized\n");
    if (input_args(ab_array, argc, argv) == -1)
    {
        free_ab_array(ab_array);
        printf("free\n");
        return (-1);    //검사, 에러, 스택 A에 넣어줘야됨.
    }
    traverse_list(ab_array);
    return(0);
}

//결과 : 
./push_swap 0 1 2 3 4 5 6 7
initialized
7    6    5    4    3    2    1    0

인자 중복 검사

 ./push_swap 0 1 2 3 4 4
initialized
is_overlap
free

인자 숫자 아닌 것 검사

./push_swap 0 1 2 3 4 5 a b
initialized
is_digit
free

./push_swap 0 12abds 3212a
initialized
is_digit
free

인자 int범위 넘는검사

./push_swap 1231232131231
initialized
is_int_range
free

연결리스트 push, pop 기능 검사

Pop 기능이 제대로 작동하지 않는다.

./push_swap 0 1 2 3 4 5 6 7
initialized
7    6    5    4    3    2    1    0
7    6    5    4    3    2    1    0    -1
popped data : �
7    6    5    4    3    2    1    0    -1

  traverse_list(ab_array);
    linked_list_push(ab_array, STACK_A, -1);
    traverse_list(ab_array);
    linked_list_pop(ab_array, STACK_A, &data);
    printf("popped data : %c\n", data);
    traverse_list(ab_array);

popped data : � : 기능은 제대로 작동했지만, 검수 시에 int 형 data -1 을 char 형으로 뽑아주었기 때문에 에러가 발생했다.

막상 제대로 짜보니까, 연결리스트부에서 pop을 할 떄, 데이터가 제대로 popped 되지 않고, 연결리스트 내에 남아있었다.

./push_swap 0 1 2 3 4 5 6 7 8 9 10 11
initialized
11    10    9    8    7    6    5    4    3    2    1    0
11    10    9    8    7    6    5    4    3    2    1    0    200
popped
popped data : 200
11    10    9    8    7    6    5    4    3    2    1    0    200 // << 200이 빠져야되는데 빠지지 않는 문제 발생.

        l_list->tail->prev = NULL;
        l_list->tail->next = NULL;

        //    과 같은 코드를 넣었을 떄 , segfault가 발생하는 것으로 보아, pop과정에서 문제가 있어보인다.

      *data = l_list->tail->data;
        aux_node = l_list->tail;
        l_list->tail->prev->next = l_list->head;
        l_list->head->prev = l_list->tail->prev;
        l_list->tail->prev = NULL;
        l_list->tail->next = NULL;
        l_list->tail = l_list->tail->prev;
        free(aux_node);

학습에 도움된 사이트 :

오늘 발견한 문제와 해결방안:

data pop이 연결리스트에서 작동하지 않는 문제.

7. 학습 총평 :

* 연결리스트의 pop 설계가 잘못되었던가..?

8. 다음 학습 계획 :

관련 알고리즘을 훑는다.
pop 수정
8개 명령어 코딩.

2021 05 27 (수)