얼마 전 연결리스트를 클래스로 구현하고자 코딩을 해보았다. 작년에 c언어를 혼자 공부할때 스트럭쳐로 구현을 해보았는데 이번에는 객체화 시켜 클래스로 구현하는 거였다. 예전에 해본거라서 그런지 딱히 어려운점 없이 쉽게 구현할 수 있었다.

 

연결 리스트 : 일정한 순설르 가지는 데이터 항목들을 표현한느 방법중 하나. 배열과 같은 순차적 표현방법과 달리 데이터 항목의 논리적인 순서만 유지되고 기억장소 내에서는 각 항목들의 임의의 위치를 가지도록 하는 자료구조.

해더파일로 #include 를 이용하면 Double Linked List(이중 연결 리스트)를 이용할수 있지만 이번 숙제에선 구지 이중 연결 리스트를 할 필요성을 느끼지 않아 Single Linked List(단일 연결 리스트)를 이용하여 프로그래밍 하였다.

 


 


나중에 이걸 다시 쓸지는 모르겠지만, template 를 이용하여 여러 변수를 받을수 있도록 적용시켰다. 그에 대한 삽입, 검색, 삭제, 전체삭제, 전체출력 총 5가지를 구현하였으며, 삽입에선 오름차순 정렬삽입과 리스트 가장 처음에 삽입하는 Front 삽입 두가지를 구현하였다. 뒤에다 삽입하는 것은 Front 삽입에서 조금만 수정하면 될거같지만 귀찮아서 넘어간다.

 

컴파일은 Bloodshed Dev-C++ 를 이용하였다.

 


#include <iostream>
#include <string>
#include <stdlib.h>

using namespace std;

template <class T>  class BST ;

template <class T>  class Node {
    friend class BST<T>;
    private :
        T data;
        int data_num;
        pair<Node<T>*, Node<T>*> link;
};

template <class T>  class BST {
    public :
        BST() {   root = 0, count = 0;   };
        int BST_Count() {   return count;   };
        void BST_Insert(const T& mesg);
        string BST_Search(const T& mesg);
        void BST_Delete(const T& mesg);
        void BST_AllDelete();
        void BST_AllPrint();

    private :
        int count;
        Node<T> *root;
        void go_print(Node<T>* node);
};


template <class T>  void BST<T>::BST_Insert(const T& mesg){
    Node<T> *newNode = new Node<T>;
    newNode->data = mesg;
    newNode->data_num++;
    if(root)    {       // 이원트리가 존재할때.. 
        Node<T> *newNode1 = root;
        while(true) {
            if(newNode1->data == mesg)    {
                newNode1->data_num++;
                break;
            }else if(newNode1->data > mesg)   {
                if(newNode1->link.first == 0)   {
                    newNode1->link.first = newNode;
                    count++;
                    break;
                }
                else newNode1 = newNode1->link.first;
            }else if(newNode1->data < mesg) {
                if(newNode1->link.second == 0)  {
                    newNode1->link.second = newNode;
                    count++;
                    break;
                }
                else newNode1 = newNode1->link.second;
            }
        }
    }   else    {           // 이원트리가 존재하지 않을때 
        root = newNode;
        count++;
    }
}

template <class T> string BST<T>::BST_Search(const T& mesg) {
    bool search = false;
    Node<T> *newNode1 = root;
    
    while(true) {
        if(count == 0 )  break;
        if(newNode1->link.first == 0 && newNode1->link.second == 0) {
            if(newNode1->data == mesg)  search = true;
            break;
        }
        if(newNode1->data > mesg && newNode1->link.first != 0)  {
            newNode1 = newNode1->link.first;
            continue;
        }
        else if(newNode1->data < mesg && newNode1->link.second != 0)    {
            newNode1 = newNode1->link.second;
            continue;
        }
        else if(newNode1->data == mesg) {
            search = true;  break;
        }
        break;
    }

    if(search) {
        char msg_count[100];
        itoa(newNode1->data_num, msg_count , 10);
        return  mesg + "(*" + msg_count + ")";
    }else    return "no item";
}

template <class T>  void BST<T>::BST_Delete(const T& mesg) {
    Node<T> *newNode1 = root, *newNode2 = root;
    
    if(BST_Search(mesg) == "no item")       return ;                            // 하나도 선택되지 않았을때 
    if(newNode1->data == mesg)    {                                             // 루트가 잡혔을때... 
        if(newNode1->data_num != 1) {   newNode1->data_num--;   return; }   // 갯수가 남아있을때 갯수 줄이기 
        if(newNode1->link.first == 0 && newNode1->link.second == 0) {        // 서브 트리가 둘다 비었을때.. 
            root = 0;
            count = 0;
            return;
        }else if(newNode1->link.first != 0 && newNode1->link.second == 0)   {   // 서브 트리가 왼쪽만 있을때..
            root = newNode1->link.first;
            count--;
            return;
        }else if(newNode1->link.first == 0 && newNode1->link.second != 0)         {   // 서브 트리가 오른쪽만 있을때..
            root = newNode1->link.second;
            count--;
            return;
        }else    {                                                                   //양쪽다 서브트리가 존재할때.. 
            newNode2 = newNode1->link.first;
            while(newNode2->link.second != 0)   newNode2 = newNode2->link.second;
            newNode2->link.second = newNode1->link.second;
            root = newNode1->link.first;
            count--;
            return;            
        }      
    }

    while(true) {
        if(newNode1->data > mesg)   {
            newNode2 = newNode1;
            newNode1 = newNode1->link.first;
        }
        else if(newNode1->data < mesg)  {
            newNode2 = newNode1;
            newNode1 = newNode1->link.second;
        }
        else if(newNode1->data == mesg) {
            if(newNode1->data_num != 1) {   newNode1->data_num--;   return; }   // 갯수가 남아있을때 갯수 줄이기 
            break;
        }
    }
    
    if(newNode1->link.first == 0 && newNode1->link.second == 0)              {   // 서브 트리가 둘다 비었을때..         00
        if(newNode2->data > newNode1->data)         newNode2->link.first = 0;
        else if(newNode2->data < newNode1->data)    newNode2->link.second = 0;
    }                                                                   
    else if(newNode1->link.first != 0 && newNode1->link.second == 0)         {   // 서브 트리가 왼쪽만 있을때..         00
        if(newNode2->data > newNode1->data)         newNode2->link.first = newNode1->link.first;       
        else if(newNode2->data < newNode1->data)    newNode2->link.second = newNode1->link.first;   
    }
    else if(newNode1->link.first == 0 && newNode1->link.second != 0)         {   // 서브 트리가 오른쪽만 있을때..       00
        if(newNode2->data > newNode1->data)         newNode2->link.first = newNode1->link.second;  
        else if(newNode2->data < newNode1->data)    newNode2->link.second = newNode1->link.second;      
    }
    else    {                                                                   //양쪽다 서브트리가 존재할때.. 
        Node<T> *newNode3 = newNode1->link.first, *newNode4 = newNode1->link.second;
        while(newNode3->link.second != 0)       newNode3 = newNode3->link.second;
        newNode3->link.second = newNode4;
        if(newNode2->data > newNode1->data)         newNode2->link.first = newNode1->link.first;
        else if(newNode2->data < newNode1->data)    newNode2->link.second = newNode1->link.first;
    }
    count--;
}

template <class T>  void BST<T>::BST_AllDelete() {
    root = NULL;
    count = 0;
    // garbage collect function
}

template <class T>  void BST<T>::BST_AllPrint() {
    Node<T> *newNode = root;    
    cout << "PRINT-ALL: " << count;
    if(count <= 1 ) cout << " item" << endl;
    else            cout << " items" << endl;
    go_print(newNode);
    cout << endl;
}

template <class T>  void BST<T>::go_print(Node<T>* node)    {           //리커시브ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ!!!
    if(!node)   return;

    if(node->link.first != 0 )  go_print(node->link.first);             // 앞트리 부터
    cout << node->data << "(*" << node->data_num << "). ";              // 엄마 출격
    if(node->link.second != 0 ) go_print(node->link.second);            // 뒷트리 고고
}


int main()
{
    BST<string> bst;
    string order, msg;

    cout << "@ ";
    while(cin >> order)
    {
        if(order == "insert")   {
            cin >> msg;
            bst.BST_Insert(msg);
        }else if(order == "search") {
            cin >> msg;
            cout << "SEARCH: " << bst.BST_Search(msg) << endl;
        }else if(order == "delete") {
            cin >> msg;
            bst.BST_Delete(msg);
        }else if(order == "delete-all") {
            bst.BST_AllDelete();
        }else if(order == "print-all")  {
            bst.BST_AllPrint();
        }

        cout << "[bst: " << bst.BST_Count();
        if (bst.BST_Count() <= 1)   cout << " item]" << endl;
        else                        cout << " items]" << endl;
        cout << "@ ";
    }

    system("pause");
    return 0;
}   


[소스 설명 및 실현 모습]

 

되도록이면 함수명과 변수명을 길게 명시해서 어렵지 않게 코드를 이해 할수 있게 하였다. 기본적으로 실행 예는 다음과 같다

 

@ insert zero

[list: 1 item]

@ insert one

[list: 2 items]

@ insert two

[list: 3 items]

@ insert one

[list: 3 items]

@ print-all

PRINT-ALL: 3 items

one, two, zero

[list: 3 items]

@ search one

SEARCH: one

[list: 3 items]

@ search five

SEARCH: no item

[list: 3 items]

@ delete one

[list: 2 items]

@ delete-all

[list: 0 items]

 

파란색 글씨를 콘솔창에 쳤을때 다음과 같이 나오며, 기타 다른 함수도 사용할수있다. 현재 main 함수에서 사용되는 insert 는 sort를 하여 insert하는 방식으로 내 생각엔 front insert 보다 다소 느릴 것으로 생각한다. 숫자일땐 어쩔수없이 linked-list 구현상 순차로 찾은뒤 insert 를 해야하겠지만, 문자열같은경우 알파벳의 첫글자(A~Z) 까지 첫시작 노드를 가리키는 포인트를 만들어 배열에 저장을 하고있다면 좀더 빠른 insert를 볼수 있을거 같다.

 

* 현재 파일에서 함수들 사용 방법

1. 삽입
    명령: insert [문자열]
    출력: 없음
    설명: [문자열]을 리스트에 삽입. [문자열]이 이미 리스트에 있을 경우 무시.

 

2. 검색
    명령: search [문자열]
    출력: [문자열]이 없을 경우 "SEARCH: no item"
            [문자열]이 있을 경우 "SEARCH: [문자열]"
    설명: [문자열]을 리스트에서 찾아 출력. 단, 리스트에 [문자열]이 없을 경우 no item 출력.

 

3. 삭제
    명령: delete [문자열]
    출력: 없음
    설명: 리스트에서 [문자열]을 찾아 삭제. 리스트에 [문자열]이 없을 경우 무시.

 

4. 전체 삭제
    명령: delete-all
    출력: 없음

 

5. 전체 출력
    명령: print-all
    출력:
    PRINT-ALL: ??? items (???: 리스트에 들어있는 원소의 수 출력)
    item1, item2, item3, ..., itemN   (리스트에 들어있는 원소를 콤마(,)로 구분하여 전부 출력)

 

* 공통된 출력
    - 각 명령 입력 전 "@ " 출력
    - 각 명령 실행 후 다음을 출력
    "[list: ??? item(s)]" (??? :  리스트에 들어있는 원소의 수 출력)

 

 

 

 

 

Line 5 ~ 14 :ChainNode 내부에 Node 를 class로 구현.

Line 16 ~ 30 : 기본적인 Single-linked-list 를 Chain이라 명시하여 class로 구현.

Line 34 ~ 135 : ChainNode인 Chain class 내부 함수를 구현하는 모습. sort-insert, front-insert, all-delete, elemental-delete, all-print, search, length 의 함수를 만들었으며, list의 count를 세는경우 반복문을 이용하여 숫자를 세는것보다 한개의 변수값을 만들어 그곳에 숫자를 수시로 수정하는게 시간상 더 빠르다고 판단하여 이렇게 구현하였다.

Line 138 ~ 175 :메인 함수

 

 

p.s) 십중팔구 후배들이 코드를 보고 숙제를 하겠즤... = ㅁ = ...


Comment



티스토리 툴바