탐색방법을 구현하면서 딱히 객체화 시킬 필요성을 느끼지 못했다. 아직 클래스의 장점을 완벽하게 파악하지 못해서 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



티스토리 툴바