C++/디딤돌 자료구조와 알고리즘 with C++

도서 관리 프로그림, 이진 탐색 트리 [C++ 소스]

언제나휴일 2016. 6. 11. 18:14
반응형

도서 관리 프로그림, 이진 탐색 트리 [C++ 소스]


이진탐색트리.zip


"본문 내용"은 언제나 휴일 본 사이트에 있습니다.


//ehglobal.h

#pragma once

#pragma warning(disable:4996)

#include <string>

using std::string;

#include <iostream>

using std::cout;

using std::cin;

using std::ostream;

using std::endl;

#include <conio.h>

#include <windows.h>

enum keydata

{

    NO_DEFINED,F1,F2,F3,F4,F5,F6,F7,F8,F9,F10,ESC

};

 

//공통적으로 사용할 정적 메서드를 캡슐화한 클래스

class ehglobal

{

public:

    static void clrscr();//화면을 지우는 메서드

    static void timeflow(int millisecond); //원하는 시간동안 지연시키는 메서드

    static int getnum();//정수를 입력받는 메서드

    static string getstr();//문자열을 입력받는 메서드

    static int getkey();//기능 키를 입력받는 메서드

private:

    ehglobal(void){ }//개체를 생성하지 못하게 하기 위해 private으로 접근 지정

    ~ehglobal(void){}

};


//ehglobal.cpp

#include "ehglobal.h"

 

void ehglobal::clrscr()//화면을 지우는 메서드

{

    system("cls");

}

 

void ehglobal::timeflow(int millisecond) //원하는 시간동안 지연시키는 메서드

{

    Sleep(millisecond);

}

 

int ehglobal::getnum()//정수를 입력받는 메서드

{

    int num;

    char buf[255+1];

    cin.getline(buf,255);

    cin.clear();

    sscanf(buf,"%d",&num);

    return num;

}

 

 

string ehglobal::getstr()//문자열을 입력받는 메서드

{

    char buf[255+1];

    cin.getline(buf,255);

    cin.clear();

    return buf;

}

 

int ehglobal::getkey()//기능 키를 입력받는 메서드

{

    int key = getch();

 

    if(key == 27) //ESC를 누를 때의 key 값이 27

    {

        return ESC;

    }

    if(key == 0) //기능 키를 눌렀을 때는 getch의 반환값이 0

    {

        //어떤 기능 키를 눌렀는지 확인하려면 getch를 다시 호출해야 함

        //사용자에게 다시 키를 입력받는 것은 아님

        key = getch();

        switch(key) //입력한 키에 따라 약속된 값 반환

        {

        case 59: return F1;    case 60: return F2;

        case 61: return F3;    case 62: return F4;

        case 63: return F5;    case 64: return F6;

        case 65: return F7;    case 66: return F8;

        case 67: return F9;    case 68: return F10;

        }

    }

    return NO_DEFINED; //열거되지 않은 키를 눌렀을 때

}


//Book.h

#pragma once

#include "ehglobal.h"

class Book

{   

    const int bnum;

    string title;

public:

    Book(int bnum,string title);   

    int GetBNum()const;

    string GetTitle()const;

    void View()const;

};

 


//Book.cpp

#include "Book.h"

 

Book::Book(int bnum,string title):bnum(bnum)

{

    this->title = title;

}

int Book::GetBNum()const

{

    return bnum;

}

string Book::GetTitle()const

{

    return title;

}

void Book::View()const

{

    cout<<bnum<<", "<<title<<endl;

}

 


//BinSearchTree.h

#pragma once

#include "Book.h"

struct Node

{

    Book *book;

    Node *left;

    Node *right;

    Node *parent;

    Node(Book *book)

    {

        this->book = book;

        left = right = parent = 0;

    }   

};   

 

class BinSearchTree

{   

    Node *root;

public:

    BinSearchTree(void);

    ~BinSearchTree(void);

    bool AddBook(int bnum,string title);

    bool FindBook(int bnum)const;

    bool RemoveBook(int bnum);

    void ListAll()const;   

private:

    Node *Find(Node *sr, int bnum)const;

    void HangNode(Node *parent, Node *now);

    void DeHang(Node *now);

    void PreOrder(Node *sr)const;   

    void InOrder(Node *sr)const;   

    void PostOrder(Node *sr)const;

    void Clear(Node *sr);

};

 


//BinSearchTree.cpp

#include "BinSearchTree.h"

 

 

BinSearchTree::BinSearchTree(void)

{

    root = 0;

}

 

bool BinSearchTree::AddBook(int bnum,string title)

{

    Node *parent = Find(root,bnum);

    if(parent)

    {

        Book *sbook = parent->book;

        if(sbook->GetBNum() == bnum)

        {

            return false;

        }

    }

    Book *book = new Book(bnum,title);

    HangNode(parent,new Node(book));

    return true;

}

Node *BinSearchTree::Find(Node *sr, int bnum)const

{

    if(sr==0)

    {

        return sr;

    }

    int gap = bnum - sr->book->GetBNum();

    if(gap==0)

    {

        return sr;

    }

    if(gap>0)

    {

        if(sr->right)

        {

            return Find(sr->right,bnum);

        }

        return sr;

    }

    if(sr->left)

    {

        return Find(sr->left,bnum);

    }

    return sr;

}

void BinSearchTree::HangNode(Node *parent, Node *now)

{

    if(parent == 0)

    {

        root = now;

        return;

    }

    now->parent = parent;

    int gap = now->book->GetBNum() - parent->book->GetBNum();

    if(gap>0)

    {

        parent->right = now;

    }

    else

    {

        parent->left = now;

    }

}

bool BinSearchTree::FindBook(int bnum)const

{

    Node *now = Find(root,bnum);

    if(now)

    {

        Book *sbook = now->book;

        if(sbook->GetBNum() == bnum)

        {

            sbook->View();

            return true;

        }

    }   

    return false;

}

bool BinSearchTree::RemoveBook(int bnum)

{

    Node *now = Find(root,bnum);

    if(now)

    {

        Book *sbook = now->book;

        if(sbook->GetBNum() == bnum)

        {           

            DeHang(now);

            return true;

        }

    }   

    return false;

}

void BinSearchTree::DeHang(Node *now)

{

    if(now->left && now->right)

    {

        Node *alter = now->left;

        while(alter->right)

        {

            alter = alter->right;

        }

        Book *tmpbook = now->book;

        now->book = alter->book;

        alter->book = tmpbook;

        now = alter;

    }

 

    Node *pa = now->parent;

    Node *child = 0;

    (child = now->left)||(child = now->right);

    if(pa)

    {

        if(pa->left == now)

        {

            pa->left = child;

        }

        else

        {

            pa->right = child;

        }

    }

    else

    {

        root = child;

    }

    if(child)

    {

        child->parent = pa;

    }

    delete now->book;

    delete now;

}

void BinSearchTree::ListAll()const

{   

    cout<<"=== Pre order ===="<<endl;

    PreOrder(root);   

    cout<<"===  In order ===="<<endl;

    InOrder(root);   

    cout<<"=== Post order ===="<<endl;

    PostOrder(root);

}

void BinSearchTree::PreOrder(Node *sr)const

{

    if(sr)

    {

        sr->book->View();

        PreOrder(sr->left);

        PreOrder(sr->right);

    }

}

void BinSearchTree::InOrder(Node *sr)const

{

    if(sr)

    {       

        InOrder(sr->left);

        sr->book->View();

        InOrder(sr->right);

    }

}

void BinSearchTree::PostOrder(Node *sr)const

{

    if(sr)

    {       

        PostOrder(sr->left);

        PostOrder(sr->right);

        sr->book->View();

    }

}

 

 

BinSearchTree::~BinSearchTree(void)

{

    Clear(root);

}

void BinSearchTree::Clear(Node *sr)

{

    if(sr)

    {       

        Clear(sr->left);

        Clear(sr->right);

        delete sr->book;

        delete sr;

    }

}

 


//App.h

#pragma once

#include "ehglobal.h"

#include "BinSearchTree.h"

class App

{

    BinSearchTree bstree;

public:   

    void Run();

private:

    int SelectMenu();

    void AddBook(); //도서 추가

    void RemoveBook();//도서 삭제

    void FindBook()const; //도서 검색   

    void ListAll()const; //전체 보기

};

 


//App.cpp

#include "App.h"

 

void App::Run()

{

    int key=NO_DEFINED;

    while((key = SelectMenu())!=ESC)

    {

        switch(key)

        {

        case F1: AddBook(); break;

        case F2: RemoveBook(); break;

        case F3: FindBook(); break;

        case F4: ListAll(); break;       

        default: cout<<"잘못 선택하셨습니다."<<endl; break;

        }

        cout<<"아무 키나 누르세요."<<endl;

        ehglobal::getkey();

    }

}

 

int App::SelectMenu()

{

    ehglobal::clrscr();//콘솔 화면을 지우기

    cout<<"도서 관리 프로그램 [ESC]: 종료"<<endl;

    cout<<"F1: 도서 추가 F2: 도서 삭제 F3: 도서 검색 F4: 전체 보기"<<endl;

 

    return ehglobal::getkey();//사용자가 입력한 기능 키 반환

}

void App::AddBook() //도서 추가

{

    cout<<"추가할 도서 번호:";

    int num = ehglobal::getnum();

    if(bstree.FindBook(num))

    {

        cout<<"이미 존재합니다."<<endl;

        return;

    }

    cout<<"도서명:";

    string title = ehglobal::getstr();

    bstree.AddBook(num,title);

}

void App::RemoveBook()//도서 삭제

{

    cout<<"삭제할 도서 번호:";

    int num = ehglobal::getnum();

   

    if(bstree.RemoveBook(num))

    {

        cout<<"삭제하였습니다."<<endl;       

    }

    else

    {

        cout<<"존재하지 않는 도서입니다."<<endl;

    }

 

}

void App::FindBook()const //도서 검색   

{

    cout<<"검색할 도서 번호:";

    int num = ehglobal::getnum();

   

    if(bstree.FindBook(num)==0)   

    {

        cout<<"존재하지 않는 도서입니다."<<endl;

    }

}

void App::ListAll()const //전체 보기

{

    bstree.ListAll();

} 


//Program.cpp

#include "App.h"

int main()

{

    App *app = new App();

    app->Run();

    delete app;

    return 0;

}

 


프로그래밍 언어 및 기술 학습, 무료 동영상 강의 언제나 휴일

반응형