20210730 자료구조 erase ~ 정렬, Array class

안녕하세요 틴구입니다

오늘은 자료구조 링크드 리스트에 이어서 erase, 정렬에 대해서 알아보도록 할게요.

어제와 똑같은 파일에서 추가하는 형식으로 해보도록 하겠습니다.

어제와 오늘의 코드 굵기와 구분선을 넣도록 하겠습니다.(맨 아래쪽에 있음)

어제 / 오늘

erase / 정렬

List.h

#pragma once

#include <assert.h>

// friend : 아래처럼 Listnode에 List를 friend로 지정하면 List에서는 ListNode의
// private에 접근할 수 있다.

template <typename T>
class CListNode
{
    template <typename T>
    friend class CList;

    template <typename T>
    friend class CListIterator;

private:
    CListNode() :
        m_Next(nullptr),
        m_Prev(nullptr)
    {
    }

    ~CListNode()
    {
    }

private:
    T m_Data;
    CListNode<T>* m_Next;
    CListNode<T>* m_Prev;
};

/*
iterator : 노드를 순차적으로 방문하기 위해서  iterator를 만들어서 제공한다.
iterator를 이용해서 앞에서 부터 혹은 뒤에서부터 노드를 순차적으로 접근할 수 있게 해준다.
*/
template <typename T>
class CListIterator
{
    template <typename T>
    friend class CList;

public:
    CListIterator() :
        m_Node(nullptr)
    {
    }

    ~CListIterator()
    {
    }

private:
    CListNode<T>* m_Node;

public:
    // iterator끼리 서로 가지고 있는 노드가 같을 경우 같다고 판단한다.
    bool operator == (const CListIterator<T>& iter) const
    {
        return m_Node == iter.m_Node;
    }

    bool operator != (const CListIterator<T>& iter) const
    {
        return m_Node != iter.m_Node;
    }

    bool operator == (const CListNode<T>* Node) const
    {
        return m_Node == Node;
    }

    bool operator != (const CListNode<T>* Node) const
    {
        return m_Node != Node;
    }

    void operator ++ ()
    {
        m_Node = m_Node->m_Next;
    }

    void operator ++ (int)
    {
        m_Node = m_Node->m_Next;
    }

    void operator -- ()
    {
        m_Node = m_Node->m_Prev;
    }

    void operator -- (int)
    {
        m_Node = m_Node->m_Prev;
    }

    T& operator * () const
    {
        return m_Node->m_Data;
    }
};

// 숙제 : reverseiterator 클래스를 만들어오기.
// reverseiterator 는 역방향으로 진행하는 iterator이다.


template <typename T>
class CList
{
public:
    CList()
    {
        m_Size = 0;

        // Begin과 End노드를 생성하고 두 노드를 서로 연결한다.
        m_Begin = new NODE;
        m_End = new NODE;

        m_Begin->m_Next = m_End;
        m_End->m_Prev = m_Begin;
    }

    ~CList()
    {
        // Begin노드는 이전노드가 nullptr이다.
        // End노드는 다음노드가 nullptr이다.
        PNODE DeleteNode = m_Begin;

        while (DeleteNode)
        {
            PNODE Next = DeleteNode->m_Next;

            delete DeleteNode;

            DeleteNode = Next;
        }
    }

private:

    // typedef : 타입을 다른 이름으로 재정의 해주는 기능을 제공한다.
    typedef CListNode<T> NODE;
    typedef CListNode<T>* PNODE;

public:
    typedef CListIterator<T> iterator;

private:
    // Begin과 End는 데이터를 저장하기 위한 노드는 아니다.
    // 명시적으로 시작과 끝을 의미하는 노드로 사용하기 위해 할당해두고 사용한다.
    // 실제 데이터를 저장하는 노드는 Begin과 End노드 사이에 위치하게 될것이다.
    PNODE m_Begin;
    PNODE m_End;
    int m_Size;

public:
    void push_back(const T& data)
    {
        // 데이터를 저장해둘 노드를 생성한다.
        PNODE Node = new NODE;

        Node->m_Data = data;

        // End노드와 End노드의 이전노드 사이에 새로 생성된 노드를 추가해주도록 한다.
        PNODE Prev = m_End->m_Prev;

        // End노드의 이전노드의 다음노드를  End에서 새로 생성된 노드로 교체한다.
        Prev->m_Next = Node;

        // 새로 생성된 노드의 이전노드를 End의 이전노드로 지정한다.
        Node->m_Prev = Prev;

        // 새로 생성된 노드의 다음 노드를 End노드르 지정한다.
        Node->m_Next = m_End;

        // End노드의 이전노드를 새로 생성한 노드로 지정한다.
        m_End->m_Prev = Node;

        ++m_Size;
    }

    void push_front(const T& data)
    {
        PNODE Node = new NODE;

        Node->m_Data = data;

        // Begin노드와 Begin노드의 다음노드 사이에 새로 생성된 노드를 추가한다.
        PNODE Next = m_Begin->m_Next;

        // 새로 생성된 노드의 다음노드로 Begin노드의 다음노드를 지정한다.
        Node->m_Next = Next;

        // Begin노드의 다음노드의 이전노드를 새로 생성된 노드로 지정한다.
        Next->m_Prev = Node;

        // Begin노드의 다음노드로 새로 생성된 노드를 지정한다.
        m_Begin->m_Next = Node;

        // 새로 생성된 노드의 이전노드로 Begin노드를 지정한다.
        Node->m_Prev = m_Begin;

        ++m_Size;
    }

    // 마지막 노드를 제거한다.
    void pop_back()
    {
        if (empty())
        {
            assert(false);
        }

        // End노드의 이전 노드를 지워준다. 그러므로 End의 이전노드를 얻어오고
        // End의 이전 노드의 이전노드를 얻어와서 End와 연결해준다.
        PNODE DeleteNode = m_End->m_Prev;

        PNODE Prev = DeleteNode->m_Prev;

        // 지울노드의 이전노드의 다음노드를 End노드로 지정한다.
        Prev->m_Next = m_End;

        // End노드의 이전노드로 지울노드의 이전노드를 지정한다.
        m_End->m_Prev = Prev;

        // 노드를 제거한다.
        delete DeleteNode;

        --m_Size;
    }

    void pop_front()
    {
        if (empty())
        {
            assert(false);
        }

        // Begin노드의 다음 노드를 지워준다.
        PNODE DeleteNode = m_Begin->m_Next;

        // 지울 노드의 다음 노드를 얻어온다.
        PNODE Next = DeleteNode->m_Next;

        // Begin노드의 다음노드로 지울 노드의 다음노드를 지정한다.
        m_Begin->m_Next = Next;

        // 지울노드의 다음노드의 이전노드로 Begin노드를 지정한다.
        Next->m_Prev = m_Begin;

        // 노드를 제거한다.
        delete DeleteNode;

        --m_Size;
    }

    const T& front() const
    {
        if (empty())
            assert(false);

        return m_Begin->m_Next->m_Data;
    }

    const T& back() const
    {
        if (empty())
            assert(false);

        return m_End->m_Prev->m_Data;
    }


    // 클래스의 멤버함수는 함수의 뒤에 const를 붙일 수 있다.
    // 멤버함수의 뒤에 const가 붙으면 이 함수에서는 멤버변수의 값을 변경할 수 없게 된다.
    // const 객체가 만들어진 경우라면 뒤에 const가 붙은 멤버함수만 호출이 가능하다.
    int size() const
    {
        return m_Size;
    }

    bool empty() const
    {
        return m_Size == 0;
    }

    // 추가된 모든 노드를 제거한다.
    void clear()
    {
        if (empty())
            return;

        PNODE DeleteNode = m_Begin->m_Next;

        // End노드가 아니라면 while을 돌면서 제거해주도록 한다.
        while (DeleteNode != m_End)
        {
            // 지울 노드의 다음노드를 미리 받아둬야 한다.
            // 왜냐하면 노드를 먼저 지워버린다면 다음노드를 얻어올 수 없기 때문이다.
            PNODE Next = DeleteNode->m_Next;

            // 노드를 제거한다.
            delete DeleteNode;

            // 지울 노드를 다음 노드로 갱신한다.
            DeleteNode = Next;
        }

        // Begin노드와 End노드를 서로 연결해준다.
        m_Begin->m_Next = m_End;
        m_End->m_Prev = m_Begin;

        // 노드의 개수를 0으로 초기화해준다.
        m_Size = 0;
    }

    iterator begin() const
    {
        iterator iter;
        iter.m_Node = m_Begin->m_Next;
        return iter;
    }

    iterator end() const
    {
        iterator iter;
        iter.m_Node = m_End;
        return iter;
    }
       void operator = (const CList<T>& list)
    {
        // 기존 정보를 제거한다.
        clear();

        m_Size = list.m_Size;

        PNODE Node = list.m_Begin->m_Next;

        while (Node != list.m_End)
        {
            push_back(Node->m_Data);
            Node = Node->m_Next;
        }
    }

    // 삭제한 노드의 다음 노드를 가지고 있는 iterator를 반환해준다.
    iterator erase(const T& data)
    {
        iterator iter = Find(data);

        if (iter == end())
            return iter;

        return erase(iter);
    }

    iterator erase(const iterator& iter)
    {
        if (iter == end() || iter == m_Begin)
            return end();

        // 지울 노드의 이전노드와 다음노드를 얻어온다.
        // 지울 노드의 이전노드와 다음노드를 서로 연결시켜준다.
        PNODE Prev = iter.m_Node->m_Prev;
        PNODE Next = iter.m_Node->m_Next;

        Prev->m_Next = Next;
        Next->m_Prev = Prev;

        delete iter.m_Node;

        --m_Size;

        iterator result;
        result.m_Node = Next;

        return result;
    }

    iterator Find(const T& data)
    {
        iterator iter = begin();
        iterator iterEnd = end();

        for (; iter != iterEnd; ++iter)
        {
            if (*iter == data)
                return iter;
        }

        // 못찾을 경우 end를 리턴한다.
        return iterEnd;
    }

    // 정렬
    void sort(bool (*pFunc)(const T&, const T&))
    {

        // 두번째 부터 마지막까지 반복하기위해서 --iter1End;를 한다
        iterator iter1 = begin();
        iterator iter1End = end();
        --iter1End;

        iterator iter2;
        iterator iter2End = end();

        // 예를 들어 10개라면 0 ~ 8 까지만 반복한다.
        // 마지막 9번은 반복을 안한다.

        // 첫번째 꺼를 그 다음꺼랑 비교하기 때문에 ++iter2;를 한것이다.

        // 그리고 함수를 변수로 초기화시키고 사용을 하게 되면 더 빠르게 동작 시킬 수 있다.
        for (; iter1 != iter1End; ++iter1)
        {
            iter2 = iter1;
            ++iter2;
            for (; iter2 != iter2End; ++iter2)
            {
                if (pFunc(*iter1, *iter2))
                {
                    T data = *iter1;
                    *iter1 = *iter2;
                    *iter2 = data;
                }
            }
        }
    }
};

 

---

메인함수에서 이런식으로 코드를 짜볼게요

#include <iostream>
#include "List.h"
#include <time.h>

/*
자료구조 : 데이터를 관리하는 방법.
*/bool SortInt(const int& Left, const int& Right)
{
    return Left < Right;
}


// F5 로 실행을 하면 Debuging 모드로 실행이 된다.
int main()
{
    srand((unsigned int)time(0));
    rand();

    CList<int> listInt;

    for (int i = 0; i < 100; ++i)
    {
        listInt.push_back(i);
    }

    std::cout << listInt.back() << std::endl;
    std::cout << listInt.front() << std::endl;

    CList<int>::iterator iter;
    

    // 위에서 for문의 push_back(i)에 의해서 0 ~ 99 숫자가 생성이 되는데 erase(80)을 하게되면 중간에 들어가는

    // 80이 사라지게 되고 0 ~ 79  81 ~ 99가 출력이 되게 된다
    iter = listInt.erase(80);
    
    std::cout << "Delete Next Node Data : " << *iter << std::endl;

    listInt.clear();



    // 0이상1000미만의 랜덤한 수를 100번 출력
    for (int i = 0; i < 100; ++i)
    {
        listInt.push_back(rand() % 1000);
    }

    
    std::cout << "======= Before =======" << std::endl;
    for (iter = listInt.begin(); iter != listInt.end(); ++iter)
    {
        std::cout << *iter << std::endl;
    }

    listInt.sort(SortInt);

    std::cout << "======= After =======" << std::endl;
    for (iter = listInt.begin(); iter != listInt.end(); ++iter)
    {
        std::cout << *iter << std::endl;
    }
    return 0;
}

이렇게 짜면 befor에서는 1000미만 100개의 랜덤한 수가 뒤죽박죽으로 생성되는데

after에서는 1000미만 100개의 랜덤한 수가 작은숫자부터 큰 숫자로의 정렬이 이루어지게 됩니다.

 

Array class

Array class 같은 경우는 배열을 사용하기 편하게 만들기 위한 목적으로 사용하는 class입니다.

만약에 선언되어 있는 배열이 꽉찼다면 그 배열을 늘려주는 방법을 배웠습니다

그렇게 하기위해서는 일반적인 배열로는 사용이 불가능하고 반드시 동적 배열로 처리를 해야합니다.

Array.h

 

#pragma once

#include <assert.h>
#include <string.h>

template <typename T>
class CArray
{
public:
    CArray()
    {
        m_Size = 0;
        m_Capacity = 4;

        m_Array = new T[m_Capacity];
    }
    // 복사 생성자
    CArray(const CArray<T>& Array)
    {
        m_Size = Array.m_Size;
        m_Capacity = Array.m_Capacity;

        m_Array = new T[m_Capacity];

        memcpy(m_Array, Array.m_Array, sizeof(T) * m_Size);
    }

    ~CArray()
    {
        delete[] m_Array;
    }

private:
    T* m_Array;
    int m_Capacity; // 실제 배열이 생성된 전체 개수
    int m_Size; // 생성된 배열중 채워진 개수

public:

    // Array 클래스 같은경우는 push_front를 하면 안 된다.
    void push_back(const T& data)
    {
        // 이미 모든 데이터가 다 채워져 있다면 공간을 늘려준다.
        if (m_Size == m_Capacity)
        {

            // 공간을 2배만큼 늘려준다
            m_Capacity *= 2;

            T* Array = new T[m_Capacity];

            // memcpy : 메모리 복사 기능이다.
            // 2번인자에 들어간 메모리 주소로부터 복사를 시작한다.
            // 3번인자의 크기만큼을 1번인자의 메모리주소에서 그 크기만큼 채워준다.

            // sizeof(T) * m_Size가 의미하는 것은 복사할 메모리 크기를 말하는 것이다. 하나의 크기 * 전체 개수이다.
            memcpy(Array, m_Array, sizeof(T) * m_Size);

            // 기존 공간을 제거한다.
            delete[] m_Array;
            // 제거한 공간에 복사한 주소를 불러온다.
            m_Array = Array;
        }

        m_Array[m_Size] = data;
        ++m_Size;
    }

    // push_back()에서 정한 마지막 인덱스 m_Size를 제거하게 되는 것이다.
    void pop_back()
    {
        if (empty())
            assert(false);

        --m_Size;
    }

    T& front() const
    {
        if (empty())
            assert(false);

        return m_Array[0];
    }

    T& back() const
    {
        if (empty())
            assert(false);

        return m_Array[m_Size - 1];
    }

    int size() const
    {
        return m_Size;
    }

    int capacity() const
    {
        return m_Capacity;
    }

    bool empty() const
    {
        return m_Size == 0;
    }
    // 대입연산자
    void operator = (const CArray<T>& Array)
    {

        // 대입연산의 경우 기존것을 먼저 제거해야 한다
        delete[] m_Array;

        m_Size = Array.m_Size;
        m_Capacity = Array.m_Capacity;

        m_Array = new T[m_Capacity];

        memcpy(m_Array, Array.m_Array, sizeof(T) * m_Size);
    }
    

    // 일반 배열처럼 사용하기 위한 operator
    T& operator [](int Index) const
    {
        if (Index < 0 || Index >= m_Size)
            assert(false);

        return m_Array[Index];
    }

    bool erase(const T& data)
    {
        // Index를 -1로 설정한 이유는 for문에서 못찾았을경우 for문 밖 if문으로 들어가

        // false를 리턴시켜주기 위함이다.
        int Index = -1;

        for (int i = 0; i < m_Size; ++i)
        {
            if (m_Array[i] == data)
            {
                Index = i;
                break;
            }
        }

        if (Index == -1)
            return false;

        return eraseIndex(Index);
    }
    // 위에서 data를 찾았으면 그 데이타의 인덱스 값을 eraseIndext로 리턴을해서 아래의 함수로 넘어가 eraseIndex의      // Index가 적용이된다
    bool eraseIndex(int Index)
    {
        if (Index < 0 || Index >= m_Size)
            return false;

        for (int i = Index; i < m_Size - 1; ++i)
        {    

            // 만약에 Index 값이 80이라면 80대신 81번째 인덱스 값을 넣어준다
            m_Array[i] = m_Array[i + 1];
        }
        // 위에서 하나의 인덱스를 지웠기때문에 --m_Size를 해준다.
        --m_Size;

        return true;
    }
    // 정렬
    void sort(bool (*pFunc)(const T&, const T&))
    {
        for (int i = 0; i < m_Size - 1; ++i)
        {
            for (int j = i + 1; j < m_Size; ++j)
            {
                if (pFunc(m_Array[i], m_Array[j]))
                {
                    T Temp = m_Array[i];
                    m_Array[i] = m_Array[j];
                    m_Array[j] = Temp;
                }
            }
        }
    }
};

main.cpp

#include <iostream>
#include "Array.h"
#include <time.h>



// sort함수의 인자에 값을 넣어주기 위한 SortInt()함수
bool SortInt(const int& Left, const int& Right)
{
    return Left > Right;
}

int main()
{
    srand((unsigned int)time(0));
    rand();

    CArray<int> Arr1;

    for (int i = 0; i < 10; ++i)
    {
        Arr1.push_back(rand() % 100);
    }

    // 복사생성자

    // 아래처럼 바로 선언하자마자 대입시키면 복사생성자가 된다.
    CArray<int> Arr2 = Arr1;

    // 대입연산자

    // 아래처럼 선언을 하고 그 아래에서 대입을하면 operator의 대입연산자로 선언이 된다.
    CArray<int> Arr3;


    Arr3 = Arr1;

    // Arr1.의 사이즈를 받는다.
    int Size = Arr1.size();
    for (int i = 0; i < Size; ++i)
    {
        std::cout << Arr1[i] << std::endl;
    }

    std::cout << "Sort" << std::endl;

    // Arr1의 데이터에 정렬함수를 이용해 정렬해준다
    Arr1.sort(SortInt);

    Size = Arr1.size();
    for (int i = 0; i < Size; ++i)
    {
        std::cout << Arr1[i] << std::endl;
    }

    return 0;
}

여기까지 erase, sort, Array class까지 배워보았습니다!!

다음에 또 만나요~~