데이터 구조 - Binary Search 두 가지 방법의 코드 구현

Reference Book: 《Data Structures and Program Design in C++》
---------------------------------------------------------------------------------------------------------------------------------------------------
1. Double_Linked_List 문장 보기 DoubleLinked_List 코드 구현
2. (1) Record.h

#ifndef RECORD_H
#define RECORD_H

#include 

using namespace std;

typedef int Key_type;
typedef Key_type Record_type;
class Key
{
    private:
        Key_type key;

    public:
        static Key_type comparisons;
        Key(int x=0);
        Key_type the_key()const;

};
bool operator == (const Key &x, const Key &y);
bool operator > (const Key &x, const Key &y);
bool operator < (const Key &x, const Key &y);
bool operator >= (const Key &x, const Key &y);
bool operator <= (const Key &x, const Key &y);
bool operator != (const Key &x, const Key &y);
ostream &operator << (ostream &output, Key &x);
/*
class Record
{
    public:
        Record(int x=0, int y=0);
        int the_key()const;

    protected:

    private:
        int key;
        int other;
};
*/
#endif // RECORD_H

2. (2) Record.cpp

#include "Record.h"

int Key::comparisons = 0;
Key::Key(int x)
{
    key = x;
}

Key_type Key::the_key()const
{
    return key;
}

bool operator == (const Key &x, const Key &y)
{
    Key::comparisons++;
    return x.the_key()==y.the_key();
}

bool operator > (const Key &x, const Key &y)
{
    Key::comparisons++;
    return x.the_key()>y.the_key();
}

bool operator < (const Key &x, const Key &y)
{
    Key::comparisons++;
    return x.the_key()= (const Key &x, const Key &y)
{
    Key::comparisons++;
    return x.the_key()>=y.the_key();
}

bool operator <= (const Key &x, const Key &y)
{
    Key::comparisons++;
    return x.the_key()<=y.the_key();
}

bool operator != (const Key &x, const Key &y)
{
    Key::comparisons++;
    return x.the_key()!=y.the_key();
}

ostream &operator << (ostream &output, Key &x)
{
    output << x.the_key();
    output << endl;
    return output;
}
/*
Record::Record(int x, int y)
{
    key = x;
    other = y;
}

int Record::the_key()const
{
    return key;
}
*/

3. 순서 표
Ordered_list.h

#ifndef ORDERED_LIST_H
#define ORDERED_LIST_H
#include "Doubly_Linked_List.h"
#include "Record.h"

using namespace std;

class Ordered_list:public Doubly_Linked_List
{
    public:
        Ordered_list();
        Error_code insert(const Key &data);
        Error_code insert(int position, const Key &data);
        Error_code replace(int position, const Key &data);

    protected:

    private:
};



/*
    C++             ，             
*/
Ordered_list::Ordered_list()
{
    //ctor
}

Error_code Ordered_list::insert(const Key &data)
/*Pre：
  Post:       data           pos,       insert  .
*/
{
    int s = size();
    int position;
    for(position = 0; position < s; position++)
    {
        Key list_data;
        retrieve(position, list_data);
        if(data < list_data)break;
    }
    return Doubly_Linked_List::insert(position, data);
            //          insert   ,              ::  
            //     insert  
}

Error_code Ordered_list::insert(int position, const Key &data)
/*Pre:
  Post:                     ,       fail;
              insert  (   pos      ).
*/
{
    Key list_data;
    if(position>0)
    {
        retrieve(position-1, list_data);
        if(datalist_data)return fail;
    }
    //   pos              insert  
    return Doubly_Linked_List::insert(position, data);
}

Error_code Ordered_list::replace(int position, const Key &data)
/*Pre:
  Post:                     (     if  ),
              fail;       replace  (   pos      ).
*/
{
    Key list_data;
    if(position>0)
    {
        retrieve(position-1, list_data);
        if(datalist_data)return fail;
    }
    return Doubly_Linked_List::replace(position, data);
}

#endif // ORDERED_LIST_H

4. main.cpp

#include 
#include "Ordered_list.h"

using namespace std;

/*********************************************
    The Forgetful Version of Binary Search
*********************************************/
Error_code recursive_binary_1(const Ordered_list &the_list, const Key &target,
                              int bottom, int top, int &position)
/*Pre:     bottom top      Key   .
  Post:        bottom top     1   ,      target     
        success    position;     not_present.
*/
{
    Key data;
    if(bottom