用B-樹實作虛拟圖書管理系統

學校資料結構的課程實驗之一。

用到的資料結構：B-樹

基本功能：對虛拟書庫的圖書進行檢視、增加、删除、修改。

主函數：

#include <iostream>
#include "Library.h"
using namespace std;
int main()
{
    Library myLib=Library("books.txt");
    char choice='y';
    while(choice=='y')
    {
        cout << "請選擇操作"<<endl;
        cout << "--------------------------------" << endl;
        cout << "1----新書入庫" << endl;
        cout << "2----檢視庫存" << endl;
        cout << "3----借閱" << endl;
        cout << "4----歸還" << endl;
        cout << "5----删除舊書" << endl;
        cout << "6----修改圖書資訊" << endl;
        cout << "--------------------------------" << endl;
        int option;
        cin >> option;
        switch (option)
        {
        case : myLib.add(); break;
        case : myLib.display(); break;
        case : myLib.lend(); break;
        case : myLib.back(); break;
        case : myLib.remove(); break;
        case : myLib.change(); break;
        }
        cout << "繼續嗎?[y/n]";
        cin >> choice;
    }
    cout << "是否儲存修改？[y/n]";
    cin >> choice;
    if (choice == 'y')
        myLib.save("books.txt");//需要儲存時儲存檔案
    return ;
}

圖書館類：

#include <string>
#include "B_tree.h"
using namespace std;

struct Book
{
    int number;
    string name;
    string introduction;
    unsigned left;
    Book(){}
    Book(int num) :number(num), name(""), introduction(""), left(){}//隻有編号的初始化
    Book(int num, string nam,string intro, unsigned lef)//完整初始化
        :number(num),name(nam),introduction(intro),left(lef){}
    void print()//顯示資訊
    {
        cout << "-------------------------------" << endl;
        cout << "這本書的資訊如下：" << endl;
        cout << "編号: " << number << endl;
        cout << "書名: " << name << endl;
        cout << "簡介: " << introduction << endl;
        cout << "剩餘數量: " << left << endl;
        cout << "-------------------------------" << endl;
    }
    bool operator==(const Book &b) const//重載關系運算符
    {
        if(this->number == b.number) return true;//編号等即命中
        else return false;
    }
    bool operator<(const Book &b) const
    {
        if (this->number < b.number) return true;
        else return false;
    }
    bool operator>(const Book &b) const
    {
        if (this->number > b.number) return true;
        else return false;
    }
};
ofstream outFile;//輸出流

class Library
{
private:
    B_tree<Book,> books;
    unsigned total;
    static void readBook(Book &aBook)//寫一本書的内容（一定要是靜态的） 
    {
        outFile<<aBook.number<<endl;
        outFile<<aBook.name<<endl;
        outFile<<aBook.introduction<<endl;
        outFile << aBook.left << endl;
    }
    void readFile(const char filename[])//讀檔案
    {
        total = ;
        ifstream inFile;
        inFile.open(filename);
        char trying;
        while(inFile.is_open() && !inFile.eof())
        {
            //先試探是否為結束符
            inFile >> trying;
            if (trying == '#') break;
            else
            {
                inFile.putback(trying);
                int number;
                inFile>>number;
                string name;
                inFile>>name;
                string introduction;
                inFile>>introduction;
                unsigned left;
                inFile>>left;
                Book aBook=Book(number,name,introduction,left);
                aBook.print();//顯示這本書的資訊
                books.insert(aBook);
                total+=left;
            }           
        }
        cout << "庫存共有圖書" << total << "本"<<endl;
        inFile.close();
    }
    void writeFile(const char filename[])//寫檔案
    {
        outFile.open(filename);
        books.traverse(readBook);
        outFile << '#';//此處必須有一個結束辨別符
        outFile.close();
    }
    Book search(int num)//以編号為依據進行查找
    {
        Book se_book(num);
        books.search_tree(se_book);
        return se_book;
    }
    static void print(Book &aBook)//顯示資訊（必須是靜态的）
    {
        cout << "-------------------------------" << endl;
        cout << "這本書的資訊如下：" << endl;
        cout << "編号: " << aBook.number << endl;
        cout << "書名: " << aBook.name << endl;
        cout << "簡介: " << aBook.introduction << endl;
        cout << "剩餘數量: " << aBook.left << endl;
        cout << "-------------------------------" << endl;
    }
public:
    Library(const char filename[])
    {
        cout << "這是現在的庫存資訊：" << endl;
        readFile(filename);
    }
    void add()//增加圖書
    {
        cout << "請輸入圖書資訊(編号 書名 簡介 數量)" << endl;
        int num;
        string name;
        string introduction;
        unsigned left;
        cin >> num >> name >> introduction >> left;
        Book new_book = Book(num, name, introduction, left);
        books.insert(new_book);
        cout << "這本書已入庫，資訊如下：" << endl;
        new_book.print();
        total += left;
    }
    void display()//檢視庫存
    {
        cout << "這是現在的庫存資訊：" << endl;
        books.traverse(print);
        cout << "庫存共有圖書" << total << "本" << endl;
    }
    void remove()//删除
    {
        cout << "請輸入要删除的圖書編号：";
        int num;
        cin >> num;
        Book &old_book =search(num);//通過編号找到這本書的記錄
        cout << "您即将删除這本書的所有資訊：" << endl;
        old_book.print();
        cout << "确定要删除嗎？[y/n]";
        char choice;
        cin >> choice;
        if (choice == 'y')
        {
            books.remove(old_book);//删除這本書的記錄
            cout << "編号為" << num << "的書已成功從庫中删除" << endl;
            total--;
        }       
    }
    void lend()//借出
    {
        cout << "請輸入要借出的圖書編号：";
        int num;
        cin >> num;
        Book &old_book = search(num);//通過編号找到這本書的記錄
        old_book.left--;
        cout << "編号為" << num << "的圖書已借出1本，下面是這本書的現存資訊：" << endl;
        old_book.print();
        total--;
    }
    void change()//修改（先删除再添加）
    {
        cout << "請輸入要修改的圖書編号：";
        int num;
        cin >> num;
        Book &old_book = search(num);
        cout << "這是這本書的目前資訊：" << endl;
        old_book.print();//顯示這本書之前的資訊
        books.remove(old_book);
        cout << "請輸入修改後的圖書資訊（編号 書名 簡介 數量）" << endl;
        string name;
        string introduction;
        unsigned left;
        cin >> num >> name >> introduction >> left;
        Book new_book = Book(num, name, introduction, left);
        books.insert(new_book);
        cout << "這本書的資訊已修改為：" << endl;
        new_book.print();
    }
    void back()//歸還
    {
        cout << "請輸入要歸還的圖書編号：";
        int num;
        cin >> num;
        Book &old_book = search(num);//通過編号找到這本書的記錄
        old_book.left++;
        cout << "編号為" << num << "的圖書已歸還，下面是這本書的現存資訊：" << endl;
        old_book.print();
        total++;
    }
    void save(const char filename[])
    {
        writeFile(filename);
    }
};

這裡寫代碼片

B-樹的實作參考了經典教材”Data Structures and Program Design in C++” Robert L. Kruse, Alexander J. Ryba 高等教育出版社-影印版，代碼如下：

#include <iostream>
using namespace std;
enum Error_code
{
    success, not_present, overflow, duplicate_error
};

template <class Record, int order>//階數（分支數）
struct B_node
{
    int count;//成員數
    Record data[order-];
    B_node<Record,order> *branch[order];
    B_node(){count=;}
};

template <class Record, int order>
class B_tree
{
public:
    B_tree(){root=NULL;}
    Error_code search_tree(Record &target)
    {
        return recursive_search_tree(root,target);
    }
    Error_code insert(const Record &new_entry)
    {
        Record median;
        B_node<Record,order> *right_branch, *new_root;
        Error_code result=push_down(root,new_entry,median,right_branch);
        if(result==overflow)
        {
            new_root=new B_node<Record,order>;
            new_root->count=;
            new_root->data[]=median;
            new_root->branch[]=root;
            new_root->branch[]=right_branch;
            root=new_root;
            result=success;
        }
        return result;
    }
    Error_code remove(const Record &target)
    {
        Error_code result;
        result=recursive_remove(root, target);
        if(root != NULL && root->count==)
        {
            B_node<Record,order> *old_root=root;
            root=root->branch[];
            delete old_root;
        }
        return result;
    }
    void traverse(void (*visit)(Record &))
    {
        recursie_traverse(root,visit);
    }
private:
    B_node<Record, order> *root;
    void recursie_traverse(B_node<Record,order> *current, void (*visit)(Record &))
    {
        if(current!=NULL)
        {
            for(int i=; i<current->count; i++)
                (*visit)(current->data[i]);
            for(int i=; i<current->count+; i++)
                recursie_traverse(current->branch[i], visit);
        }
    }
    Error_code search_node(B_node<Record,order> *current, const Record &target, int &position) const
    {
        position=;
        while(position < current->count && (target > current->data[position]))
            position++;
        if(position < current->count && target == current->data[position])
            return success;
        else return not_present;
    }
    Error_code recursive_search_tree(B_node<Record,order> *current, Record &target)
    {
        Error_code result=not_present;
        int position;
        if(current != NULL)
        {
            result=search_node(current,target,position);
            if(result==not_present)
                result=recursive_search_tree(current->branch[position],target);
            else
                target=current->data[position];
        }
        return result;
    }
    void split_node(B_node<Record,order> *current, const Record &extra_entry,
        B_node<Record,order> *extra_branch, int position, 
        B_node<Record,order>*&right_half, Record &median)
    {
        right_half=new B_node<Record,order>;
        int mid=order/;
        if(position <= mid)
        {
            for(int i=mid; i<order-; i++)
            {
                right_half->data[i-mid]=current->data[i];
                right_half->branch[i+-mid]=current->branch[i+];
            }
            current->count=mid;
            right_half->count=order--mid;
            push_in(current,extra_entry,extra_branch,position);
        }
        else
        {
            mid++;
            for(int i=mid; i<order-; i++)
            {
                right_half->data[i-mid]=current->data[i];
                right_half->branch[i+-mid]=current->branch[i+];
            }
            current->count=mid;
            right_half->count=order--mid;
            push_in(right_half,extra_entry,extra_branch,position-mid);
        }
        median=current->data[current->count-];
        right_half->branch[]=current->branch[current->count];
        current->count--;
    }
    void push_in(B_node<Record,order> *current, const Record &entry,
        B_node<Record,order> *right_branch, int position)
    {
        for(int i=current->count; i>position; i--)
        {
            current->data[i]=current->data[i-];
            current->branch[i+]=current->branch[i];
        }
        current->data[position]=entry;
        current->branch[position+]=right_branch;
        current->count++;
    }
    Error_code push_down(B_node<Record,order> *current, const Record &new_entry,
        Record &median, B_node<Record,order>*&right_branch)
    {
        Error_code result;
        int position;
        if(current==NULL)
        {
            median=new_entry;
            right_branch=NULL;
            result=overflow;
        }
        else
        {
            if(search_node(current,new_entry,position)==success)
                result=duplicate_error;
            else
            {
                Record extra_entry;
                B_node<Record,order> *extra_branch;
                result=push_down(current->branch[position],new_entry,
                    extra_entry,extra_branch);
                if(result==overflow)
                {
                    if(current->count < order-)
                    {
                        result=success;
                        push_in(current,extra_entry,extra_branch,position);
                    }
                    else
                        split_node(current,extra_entry,extra_branch,position,
                            right_branch,median);
                }
            }
        }
        return result;
    }
    void restore(B_node<Record,order> *current, int position)
    {
        if(position==current->count)
            if(current->branch[position-]->count > (order-)/)
                move_right(current,position-);
            else
                combine(current,position);
        else if(position==)
            if(current->branch[]->count > (order-)/)
                move_left(current,);
            else
                combine(current,);
        else
            if(current->branch[position-]->count > (order-)/)
                move_right(current,position-);
            else if(current->branch[position+]->count > (order-)/)
                move_left(current,position+);
            else combine(current,position);
    }
    void move_left(B_node<Record,order> *current, int position)
    {
        B_node<Record,order> *left_branch=current->branch[position-],
        *right_branch=current->branch[position];
        left_branch->data[left_branch->count]=current->data[position-];
        left_branch->branch[++left_branch->count]=right_branch->branch[];
        current->data[position-]=right_branch->data[];
        right_branch->count--;
        for(int i=; i<right_branch->count; i++)
        {
            right_branch->data[i]=right_branch->data[i+];
            right_branch->branch[i]=right_branch->branch[i+];
        }
        right_branch->branch[right_branch->count]=
            right_branch->branch[right_branch->count+];
    }
    void move_right(B_node<Record,order> *current, int position)
    {
        B_node<Record,order> *right_branch=current->branch[position+],
        *left_branch=current->branch[position];
        right_branch->branch[right_branch->count+]=
            right_branch->branch[right_branch->count];
        for(int i=right_branch->count; i>; i--)
        {
            right_branch->data[i]=right_branch->data[i-];
            right_branch->branch[i]=right_branch->branch[i-];
        }
        right_branch->count++;
        right_branch->data[]=current->data[position];
        right_branch->branch[]=left_branch->branch[left_branch->count--];
        current->data[position]=left_branch->data[left_branch->count];
    }
    void combine(B_node<Record,order> *current, int position)
    {
        int i;
        B_node<Record,order> *left_branch=current->branch[position-],
            *right_branch=current->branch[position];
        left_branch->data[left_branch->count]=current->data[position-];
        left_branch->branch[++left_branch->count]=right_branch->branch[];
        for(i=; i<right_branch->count; i++)
        {
            left_branch->data[left_branch->count]=right_branch->data[i];
            left_branch->branch[++left_branch->count]=right_branch->branch[i+];
        }
        current->count--;
        for(i=position-; i<current->count; i++)
        {
            current->data[i]=current->data[i+];
            current->branch[i+]=current->branch[i+];
        }
        delete right_branch;
    }
    void copy_in_predecessor(B_node<Record,order> *current, int position)
    {
        B_node<Record,order> *leaf=current->branch[position];
        while(leaf->branch[leaf->count] != NULL)
            leaf=leaf->branch[leaf->count];
        current->data[position]=leaf->data[leaf->count-];
    }
    void remove_data(B_node<Record,order> *current, int position)
    {
        for(int i=position; i<current->count-; i++)
            current->data[i]=current->data[i+];
        current->count--;
    }
    Error_code recursive_remove(B_node<Record,order> *current, const Record &target)
    {
        Error_code result;
        int position;
        if(current==NULL) result=not_present;
        else
        {
            if(search_node(current,target,position)==success)
            {
                result=success;
                if(current->branch[position]!=NULL)
                {
                    copy_in_predecessor(current,position);
                    recursive_remove(current->branch[position],current->data[position]);
                }
                else
                    remove_data(current,position);
            }
            else result=recursive_remove(current->branch[position],target);
            if(current->branch[position]!=NULL)
                if(current->branch[position]->count < (order-)/)
                    restore(current,position);
        }
        return result;
    }
};

用B-樹實作虛拟圖書管理系統

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器