const_cast

const로 선언된 상수를 일반변수로 변환하는데 사용된다. volatile를 변환시키는데도 쓰인다

 

-static_cast

c캐스팅과 비슷한 기본적인 캐스팅 연산자로 실수형, 정수형, 열거형등 기본적인 형변환을 할때 사용된다

const_cast와 달리 일반변수를 상수로 바꿀수있지만 상수를 일반변수로 바꾸진못한다

c캐스팅과의 차이점은 타입체크를 run-time으로 하지않고 compile-time에 정적으로 수행한다

 

-reinterpret_cast

어떠한 정수와 포인터 타입간에도 변환이 가능한 강력한 형변환이다

하지만 기본적인 캐스팅개념에서 벗어나 강제로 바꿔 매우 불안정하기 때문에 쓰려면 위험을 감수해야한다

 

-dynamic_cast

상속관계에있는 클래스간의 형변환을 할때 사용한다

형변환에 문제가없는지 안전검사도하는데 문제가 있을시에는 NULL값을 리턴하거나 예외를 띄운다

가상함수가 없는 클래스는 사용할 수 없다




Comment

얼마 전 연결리스트를 클래스로 구현하고자 코딩을 해보았다. 작년에 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

탐색방법을 구현하면서 딱히 객체화 시킬 필요성을 느끼지 못했다. 아직 클래스의 장점을 완벽하게 파악하지 못해서 C가 C++보다 편하고, 코딩하기 쉽다. 시간이 지나고 좀더 객체화된 코딩을 많이 해보면 마인드가 바뀔지 몰라도 아직까진 함수화시켜서 코딩하는게 편하다.

 

순차 탐색 : 배열된 데이터 리스트를 첫번째부터 차례대로 비교하며 항목을 찾아내는 방법.

이진 탐색 : 일정한 순서로 배열된 데이터 항목의 리스트(집합)를 2개 부분으로 되풀이하여나누어서, 그 한 부분을 버리고 남은 부분을 탐색함으로써 목적하는 항목을 찾아내는 방법.

솔찍히 내가 봐서 내가 만든 이 코드는 최적화 된 코딩은 아닌것 같다. dictionary 파일을 불러와 vector에 저장한 뒤, 찾을 문자열이 정리된 query 파일을 찾는 방식이다.

화면에는 검색에 실패한 문자열과 총 문자열의 갯수, 수행시간과 한개를 찾는데 걸리는 평균수행시간을 보이도록 하였다.


#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>


#include <windows.h>

using namespace std;
void filein(vector<string>&amp;, vector<string>&amp;);
void sequential_search(const vector<string>&amp; , const vector<string>&amp; );
void BinarySearch(vector<string> dictionary, vector<string> key);
void BinarySearch_Recursive(const vector<string>&amp; dictionary, string&amp; key, const int left, const int right);
void BinarySearch_nonRecursive(const vector<string>&amp; dictionary, const vector<string>&amp; key);
void sequential_search(const vector<string>&amp; dictionary, const vector<string>&amp; key);


int main()
{
    LARGE_INTEGER start, end, liFrequency;
    vector<string> dictionary, key;
    
    filein(dictionary, key);
    
    QueryPerformanceFrequency(&amp;liFrequency);    // 시간 측정 초기화
    QueryPerformanceCounter(&amp;start);            // 시작 시간 측정


    BinarySearch_nonRecursive(dictionary, key);     //   nonrecursive search
//    BinarySearch(dictionary, key);                  //   recursive search
//    sequential_search(dictionary, key);             //   sequential search
  


    QueryPerformanceCounter(&amp;end);              // 종료 시간 측정

        
    cout &lt;&lt; key.size() &lt;&lt; endl;
    cout &lt;&lt;  (double)(end.QuadPart - start.QuadPart) / (double)liFrequency.QuadPart &lt;&lt; endl;
    cout &lt;&lt; (double)(end.QuadPart - start.QuadPart) / (double)liFrequency.QuadPart / key.size() &lt;&lt; endl;

    system("pause");
    return 0;
}


void filein(vector<string>&amp; dictionary, vector<string>&amp; key)
{
    
    string dic_string;
    fstream ComeIn_dic, ComeIn_key;
    
    ComeIn_dic.open("./dictionary/dictionary.txt", ifstream::in);
    ComeIn_key.open("./dictionary/query.txt", ios::in);
       
    while(ComeIn_dic.good()){
        ComeIn_dic &gt;&gt; dic_string;
        dictionary.push_back(dic_string);
    }
    dictionary.erase(dictionary.begin() + dictionary.size());
    while(ComeIn_key.good()){
        ComeIn_key &gt;&gt; dic_string;
        key.push_back(dic_string);
    }
    key.erase(key.begin() + key.size());
    ComeIn_dic.close();    
    ComeIn_key.close();

}


void sequential_search(const vector<string>&amp; dictionary, const vector<string>&amp; key)
{
    int i , j;
    for(i = 0 ; i != key.size(); i++)   {  
        for(j = 0 ; j != dictionary.size(); j++)    
            if(key[i] == dictionary[j])    break;        
        if(j == dictionary.size())     cout &lt;&lt; key[i] &lt;&lt; endl;
    }
}

void BinarySearch(vector<string> dictionary, vector<string> key)
{

    sort(dictionary.begin(), dictionary.end());
    
    for(int i = 0 ; i != key.size(); i++)   {
        BinarySearch_Recursive(dictionary, key[i], 0, dictionary.size() - 1) ;
    }

}

void BinarySearch_Recursive(const vector<string>&amp; dictionary, string&amp; key, const int left, const int right)
{   
    int middle , flag = 0;
    if(left &lt;= right)   {
        middle = (left + right) / 2;
        if(key &lt; dictionary[middle])        return BinarySearch_Recursive(dictionary, key, left, middle - 1);
        else if(key &gt; dictionary[middle])   return BinarySearch_Recursive(dictionary, key, middle + 1, right);
        else flag = 1;
    }
    if (flag == 0)  
        cout &lt;&lt; key &lt;&lt; endl;

}

  
void BinarySearch_nonRecursive(const vector<string>&amp; dictionary, const vector<string>&amp; key)
{
    vector<string> d = dictionary, k = key;
    sort(d.begin(), d.end());
    
    int middle, left = 0 , right = dictionary.size() - 1, flag;
    for(int i =  0 ; i != k.size(); i++)  {
        left = 0 , right = d.size() - 1, flag = 0;  
        while(left &lt;= right)    {
            middle = (left + right) / 2;
            if(k[i] &gt; d[middle])   left = middle + 1;
            else if( k[i] &lt; d[middle] )      right = middle - 1;
            else  {  
                flag = 1;
                break;
            }
        }

        if(flag == 0 &amp;&amp; key[i] != dictionary[middle]) 
            cout &lt;&lt; k[i] &lt;&lt; endl;        
    }
}




[코드 설명 및 실현 모습]

 

실현 모습은 딱히 적지 않겠다. 이 파일을 컴파일해서 성공적인 모습을 보기 위해선 하위 dictionary 폴더안에  dictionary.txt와 query.txt라는 파일이 존재하여야 한다. dictionary.txt 라는 파일 내부에는 사전처럼 문자열이 정렬(이 프로그램에선 만약 정렬되지 않았을것을 가정하여 algorithm 해더파일의 sort라는 함수를 사용하여 정렬을 시켜 vector에 저장하도록 하였음)되어 적혀있어야되며, query.txt파일은 찾을 문자열들을 적으면 된다.

 

 

Line 20 ~ 46 :메인 함수. search 하는데 시간을 측정할수 있도록 구현하였다.

Line 49 ~ 71 :파일 입출력을 통해 vector 라는 곳에 전체문자열과 찾을 문자열을 기록하여 저장하는 함수.

Line 74 ~ 131 :순차탐색, 이원탐색(재귀와 재귀를 쓰지 않는 방법) 함수를 정의하는 부분.

 

 


Comment



티스토리 툴바