[패스트캠퍼스 수강 후기] 올인원 패키지 : 컴퓨터 공학 전공 필수👉C언어인강 100% 환급 챌린지 40회차 미션

 

 

환급미션 40일째...

 

 

 

소프트웨어 베이직 - 자료구조와 알고리즘 - 03. 양방향 연결 리스트

 

 

 

 

- 양방향 연결 리스트

 

 

머리head와 꼬리tail을 모두 갖는다.

각 노드는 앞 노드와 뒤 노드의 정보를 모두 저장하고 있다.

 

 

 

 

* 데이터를 '오름차순'으로 저장하는 양방향 연결리스트를 구현해볼 것이다.

 

 

기본적으로 위와 같이 코드가 구성되고,

 

 

위와 같이

삽입할 노드가 각각 앞, 뒤 노드와 양방향으로 연결되도록 한다.

 

 

해당 함수의 코드는 위와 같다.

경고메시지는 일단 무시... ^^;

 

 

 

 

위와 같이 연결리스트 삭제하는 함수도 넣어줄 것이다. 

(가장 앞쪽에 있는 노드를 삭제하는 함수를 만들 예정)

 

 

위와 같이 코드를 작성한다.

 

 

 

마지막으로,

node를 모두 출력하는 함수를 작성할 것이다.

 

 

현재 보고있는 원소의 데이터를 출력한 다음,

tail 이전까지 모든 값을 출력할 수 있게 된다.

 

 

삽입, 제거, 출력함수까지 모두 작성했고 

마지막으로 간단하게 테스트해볼 수 있도록 코드를 작성해볼 것이다.

 

 

위처럼 메인함수를 작성한 후에 실행하면 

 

의도했던 것처럼 오름차순으로 정렬되어 출력되는 것을 확인할 수 있다.

 

 

( 오름차순으로 정렬된 다음 removeFront함수에 의해 제일 앞 원소가 삭제되었다. )

 

 

 

실제 양방향 연결 리스트 구현에 있어서

삽입/삭제 기능에서의 예외사항을 처리해야 할 필요가 있고,

더이상 삭제할 원소가 없을 때 삭제하는 경우 등의 오류 또한 확인해야 한다.

 

 

 

 

=> 양방향 연결 리스트에서 각 노드가 앞/뒤 노드의 정보를 모두 저장하고 있으며,

양방향 연결 리스트를 이용해서 리스트의 앞에서 or 뒤에서부터 모두 접근할 수 있게 된다.

 

포인터가 2개 사용되기 때문에 

기존의 다른 리스트에 비해 메모리 공간이 더 많이 사용될 수 있다는 단점이 있긴 하다.

 

 

 

 

 

소프트웨어 베이직 - 자료구조와 알고리즘 - 04. 스택

 

 

 

스택의 정의와 구현에 대해 알아볼 예정...인듯?

&

c언어를 이용, 스택 자료구조를 직접 구현

 

 

 

- 스택 (Stack)

 

한쪽으로 들어가서 한쪽으로 나오는 자료구조

-> 수식 계산 등의 알고리즘에서 다방면으로 활용된다.

 

•PUSH : 스택에 데이터를 넣는다.

•POP : 스택에서 데이터를 빼낸다.

(다른 함수도 존재하긴 한다.)

 

 

위의 예시에서 결과는 다음과 같다.

7 5 4 -> 7 5 -> 7 5 6 -> 7 5

 

 

•배열을 이용한 구현

•연결 리스트를 이용한 구현

 

두 가지의 방법으로 구현할 수 있는데,

가장 기본적인 형태의 자료구조에 속하기 때문에 구현 난이도가 낮은 편이라고 한다.

 

 

 

 

 

- 배열을 이용한 스택 구현

 

 

 

 

위의 코드에서와 같이 

push, pop, show함수를 이용,

배열을 이용해 스택을 구현할 수 있다.

 

 

 

 

 

- 연결 리스트를 이용한 스택의 구현

 

 

 

새로운 노드의 삽입

 

-> 어떤 데이터를 넣고자 할때 항상 top(스택의 최상단 노드)의 위치에 들어가게 된다.

(계속해서 top이 갱신되는 형태)

 

 

노드의 삭제

-> 삭제할 노드의 다음 노드를 top으로 설정 & 삭제할 노드를 할당 해제

 

 

 

 

---------

 

#include <stdio.h>

#include <stdlib.h>

#define INF 99999999;

 

typedef struct Node

{

    int data;

    struct Node *next; //다음 노드를 가리키는 포인터변수

} Node;

 

typedef struct Stack

{

    Node *top; //모든 스택은 top이라는 노드를 하나씩 가지고 있으면 된다.

} Stack;

 

void push(Stack *stack, int data) //삽입하고자 하는 스택을 명시, 데이터 삽입

{

    Node *node = (Node*)malloc(sizeof(Node)); //malloc 을 이용해 새로운 노드가 들어갈 공간 할당

    node->data = data;

    node->next = stack->top;

    stack->top = node; //스택의 top을 현재 노드로 바꿔치기

}

 

int pop(Stack *stack)

{

    if (stack->top == NULL) //현재 스택이 비어있다면, 문제가 발생했음을 알려줌

    {

        printf("스택 언더플로우 발생\n");

        return -INF;

    }

    Node *node = stack->top; //최상단 노드를 현재의 노드에 잠깐 둔다

    int data = node->data; //데이터 추출

    stack->top = node->next; //다음 노드를 최상단 노드로 지정

    free(node); //기존의 노드는 할당 해제

    return data;

}

 

void show(Stack *stack)

{

    Node *cur = stack->top;

    printf("--- 스택의 최상단 ---\n");

    while (cur != NULL)

    {

        printf("%d\n", cur->data);

        cur = cur->next;

    }

    printf("--- 스택의 최하단 ---\n");

}

 

int main(void)

{

    Stack s;

    s.top = NULL; //반드시 처음에 top에는 NULL값을 넣어줘야 한다. 그래야 언더플로우나 출력함수의 loop문을 체크함

    push(&s, 7); //각 스택함수가 스택의 포인터를 받도록 구현했기 때문에 &를 사용

    push(&s, 5);

    push(&s, 4);

    pop(&s);

    push(&s, 6);

    pop(&s);

    

    return 0;

}

 

-----

 

 

우선 강의에서 알려준대로 코드를 따라 작성했는데 실행이 되지않아서

원인을 찾아봐야 할 듯

 

강의에선 pop함수를 void로 선언했는데,

void에서는 return을 사용할 수 없다는 경고 때문에 int형으로 바꾼 상태긴 함

 

 

 

 

 

 

 

 

 

 

두 파트씩 병행해가면서 강의를 들을 계획이었는데,

어쩌다보니 이론에 가까운 부분(?) 위주로만 강의를 듣고 있다.

컴퓨터 구조를 먼저 듣고 운영체제 파트로 넘어오면서 

소프트웨어 베이직 파트와 잘 병행될 수 있어야 할텐데 하는 고민을 했는데

역시나 운영체제 강의에 집중하고 있다..

c언어가 끝나고 자료구조/알고리즘으로 넘어오면서 갑자기 10일동안의 공백이 생겨버렸..

조금 더 신경써서 진행해야 할 듯 하다.

소프트웨어 베이직 파트가 강의 시간이 짧아서 (짧은 것은 4분짜리도 있고 대부분 10분 내외)

만만하게 봤었는데...

사실 코드 해석 다시 해보고 작성 다시 해보고 하다보면 시간이 제일 오래 걸린다.

아무튼... 

 

정작 스택/큐와 같은 자료구조의 개념도 모르면서

그 자료구조가 필요한 운영체제 파트의 강의를 잘 이해하고(?) 있는 게 오히려 신기한 지경...

 

 

 

 

 

 

 

 

 

 

올인원 패키지 : 컴퓨터 공학 전공 필수👉https://bit.ly/3i4sCVE