7.27(금) C++ - 일반적인 선형검색

from Study/C++ 2007/07/30 14:36 view 16626

#include <iostream>

using namespace std;

 

// 일반적프로그램의개념

// 선형검색: 주어진구간에서주어진조건을만족하는값을찾는다.

 

// 구간의조건: NULL 로끝나는문자열

// 구간의이동: ++

// 실패의경우: 0을리턴

// 단점: 반드시NULL을끝나는문자열이어야한다. - 너무특수한상황이다.

/*

char* xstrchr( char* s, int c )

{

        while( *s != 0 && *s != c )

               ++s;

 

        return *s == c ? s : (char*)0;

}

*/

 

// 보다일반화한버전.

// 주어진구간의조건: [begin , end) - 반개행구간. 한쪽만열려있다는의미>> [ ~ )

// 이때endpast the end 라고한다.

// 구간의이동: ++

// 실패의처리: past the end

// 장점: 부분문자열검색이가능하다-> 보다일반화되었다.

// 단점: 문자열(char)만검색가능하다. -> template으로일반화하자.

/*

char* xstrchr( char* begin, char* end, int c )

{

        while( begin != end && *begin != c )

               ++begin;

 

        return begin;

}

void main()

{

        char s[10] = "ABCDEFG";

        //char* c = xstrchr( s, 'C' );

        char *c = xstrchr( s, s+4, 'C' );

 

        if ( c == s + 4 )

        {

               cout << "실패" << endl;

        }

        else

               cout << *c << endl;

}

*/

 

// 버전3. template의도입

// 모든type의배열로부터선형검색을수행한다.!!

/*

template<typename T1, typename T2> T1 find( T1 first, T1 last, T2 value )

{

        while( first != last && *first != value )

               ++first;

 

        return first;

}

 

void main()

{

        int x[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

 

        int* p = find( x, x+10, 3 );

 

        if( p == x+10 )

        {

               cout << "값을찾을수없습니다." << endl;

        }

        else

               cout << *p << endl;

}

*/

 

// 이제Single Linked List를고려해보자.

template<typename T> class slist

{

        struct Node

        {

               T         data;

               Node* next;

               Node( T d, Node* n ) : data(d), next(n) {}

        };

        Node* head;

public:

        slist() : head(0)      {}

 

        void push_front( T a ) { head = new Node( a, head ); }

 

        // list의각요소를접근하기위해스마트포인터를넣는다.

        // 내포로만들거나외부에(그리고내부에typedef로선언) 만들수있다.

        class iterator

        {

               Node* current;

        public:

               iterator( Node* init = 0 ) : current( init ) {}

 

               iterator& operator++()

               {

                       current = current->next;

                       return *this;

               }

               T& operator* ()

               {

                       return current->data;

               }

               bool operator !=( const iterator& i )

               {

                       return (current != i.current);

               }

        };

        //-------------------------------------------------------

        // 이제slist의처음과past the end iterator를리턴하는함수를제공한다.

        iterator begin() { return iterator(head); }

        iterator end() { return iterator( 0 ); }

};

 

// 모든type의모든자료구조로부터선형검색을수행한다.!!

template<typename T1, typename T2> T1 find( T1 first, T1 last, T2 value )

{

        while( first != last && *first != value )

               ++first;

 

        return first;

}

 

// 모든type의모든자료구조로부터선형검색을수행한다.!!

// 상수가아닌조건을만족하는것을찾는다.주어진조건을찾는다!!!

template<typename T1, typename T2> T1 find_if( T1 first, T1 last, T2 pred )

{

        while( first != last )

        {

               if ( pred(*first) )

                       break;

               ++first;

        }

 

        return first;

}

bool foo( int a )

{

        return a % 3 == 0;

}

 

void main()

{

        int x[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

 

        int* p2 = find_if( x, x+10, foo );

 

        cout << *p2 << endl;

//////////////////////////////////////////////////

        slist<int> s;

 

        s.push_front(10);

        s.push_front(20);

        s.push_front(30);

        s.push_front(40);

 

        slist<int>::iterator p = find( s.begin(), s.end(), 20 );

 

        cout << *p << endl;

        ++p;

        cout << *p << endl;

/////////////////////////////////////////////////

        p = find_if( s.begin(), s.end(), foo );

        cout << *p << endl;

}

 

Tag |

Trackback Address :: 이 글에는 트랙백을 보낼 수 없습니다