✨컴공주✨ [1052682] · MS 2021 (수정됨) · 쪽지

2022-07-04 02:16:56
조회수 142

컴공 일기106

게시글 주소: https://orbi.kr/00057433112

LinkedList 를 이용해서 Stack을 구현한 예제입니다. 이건 논리적인 부분이 굉장히 중요한 것 같습니다.

자칫 잘못하면 Segmentation fault가 뜨기 때문에 주의 또 주의...


#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#include <stdlib.h>

#include <string.h>


typedef struct tagNode

{

    char* Data;

    struct tagNode* NextNode;

}Node;


typedef struct tagLinkedListStack

{

    Node* List;

    Node* Top;

}LinkedListStack;


bool LLS_IsEmpty(LinkedListStack* Stack)

{

    return (Stack->List == NULL);

}

void LLS_CreateStack(LinkedListStack** Stack)

{

    (*Stack) = (LinkedListStack*)malloc(sizeof(LinkedListStack));

    (*Stack)->List = NULL;

    (*Stack)->Top = NULL;

}


Node* LLS_CreatNode(const char* NewData)

{

    Node* NewNode = (Node*)malloc(sizeof(Node));

    NewNode->Data = (char*)malloc(strlen(NewData) + 1);


    strcpy(NewNode->Data, NewData);


    NewNode->NextNode = NULL;

    return NewNode;

}


void LLS_DestroyNode(Node* _Node)

{

    free(_Node->Data);

    free(_Node);

}



void LLS_Push(LinkedListStack* Stack, Node* NewNode)

{

    if (Stack->List == NULL)

    {

        Stack->List = NewNode;

    }


    else

    {

        Node* OldTop = Stack->List;

        while (OldTop->NextNode != NULL)

        {

            OldTop = OldTop->NextNode;

        }


        OldTop->NextNode = NewNode;

       

    }


    Stack->Top = NewNode;

}


Node* LLS_Pop(LinkedListStack* Stack)

{

    Node* TopNode = Stack->Top;


    if (Stack->List == Stack->Top)

    {

        Stack->List = NULL;

        Stack->Top = NULL;

    }


    else

    {

        Node* CurrentTop = Stack->List;

        while (CurrentTop != NULL && CurrentTop->NextNode != Stack->Top)

        {

            CurrentTop = CurrentTop->NextNode;

        }


        Stack->Top = CurrentTop;

        CurrentTop->NextNode = NULL;

    }


    return TopNode;

}


Node* LLS_Top(LinkedListStack* Stack)

{

    return Stack->Top;

}


int LLS_GetSize(LinkedListStack* Stack)

{

    int Count = 0;

    Node* Current = Stack->List;


    while (Current != NULL)

    {

        Current = Current->NextNode;

        Count++;

    }


    return Count;

}


void LLS_DestroyStack(LinkedListStack* Stack)

{

    while (!LLS_IsEmpty(Stack))

    {

        Node* Popped = LLS_Pop(Stack);

        LLS_DestroyNode(Popped);

    }


    free(Stack);

}


int main()

{

    int i = 0;

    int Count = 0;

    Node* Popped;


    LinkedListStack* Stack;


    LLS_CreateStack(&Stack);


    LLS_Push(Stack, LLS_CreatNode("abc"));

    LLS_Push(Stack, LLS_CreatNode("def"));

    LLS_Push(Stack, LLS_CreatNode("efg"));

    LLS_Push(Stack, LLS_CreatNode("hij"));


    Count = LLS_GetSize(Stack);

    printf("Size : %d, Top:%s\n\n", Count, LLS_Top(Stack)->Data);


    for (i = 0; i < Count; i++)

    {

        if (LLS_IsEmpty(Stack))

            break;


        Popped = LLS_Pop(Stack);


        printf("Popped : %s, ", Popped->Data);


        LLS_DestroyNode(Popped);


        if (!LLS_IsEmpty(Stack))

        {

            printf("Current Top : %s\n", LLS_Top(Stack)->Data);

        }

        else

        {

            printf("Stack is empty.");

        }

    }


    LLS_DestroyStack(Stack);

    return 0;

}


[실행결과]


Size : 4, Top:hij


Popped : hij, Current Top : efg

Popped : efg, Current Top : def

Popped : def, Current Top : abc

Popped : abc, Stack is empty.


0 XDK (+0)

  1. 유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.

  • 미도씨 · 1096369 · 07/04 02:33 · MS 2021

    코린이라 정렬알고리즘 어제 처음 배웠는데 진짜 무슨 소린지 모르겠더라구요.하노이 문제도 뭔소리인지 모르겠고 암튼 대단하십니다

  • ✨컴공주✨ · 1052682 · 07/04 02:36 · MS 2021

    하노이의 탑... 원반에 대한 순서를 어떻게 파악하느냐 그 문제가 많이 어렵지요 ㅜㅜ 제 기억 상으로는 C언어를 처음 배울 때 정렬 개념에 대한 예시로 봤었는데... 지금 생각해보면 가볍게 넘겨둘 걸 그랬습니다.

    어차피 하노이의 탑 예제는 자료구조 쪽에서 실컷 다루게 될 테고, 유사한 개념들을 백준이나, 알고리즘 수업에서 계속 학습하게 될 테니까요.

    처음 접하시는 상태라면, 가볍게 넘겨가셔도 될 듯 싶습니다 :)

  • 미도씨 · 1096369 · 07/04 02:38 · MS 2021

    네 생각지도못한 답변해주셔서 감사하네요 좋은 밤 되세요!

  • ✨컴공주✨ · 1052682 · 07/04 02:38 · MS 2021

    좋은 밤 되세요 :-)