实验七：简易图书管理模拟系统

【实验目的】

插入、查找和删除等数据操作在实际应用中非常普遍，通过设计和实现一个简易的图书管理系统，进一步提高学生对插入、查找和删除等操作的理解和应用能力。帮助学生理解和掌握线性表和平衡二叉树等数据结构的基本操作和实现方法，加强学生综合应用数据结构知识解决实际问题的水平和能力。

【实验内容】

1. 问题描述：一个简易图书管理的基本业务活动包括：对新购入一种书的采编入库、图书的借阅和归还等。

2. 基本要求：
   （1）每种书的登记内容至少包括书号、书名、著者、现存量和总库存量等五项。
   （2）作为演示系统，不必使用文件存储书籍数据和借阅登记信息。我们要求各种书的数据用二叉排序树来存储，借阅登记信息采用顺序表—链表来存储。顺序表存储借阅者信息，链表存储借阅者所借的各种书籍信息。借阅登记信息的存储结构如下示意：
   
   需要实现的三种主要功能定义如下：
   ①采编入库：新购入一种书，经分类和确定书号之后登记到图书帐目中去。如果这种书在帐中已有，则只将该书的总库存量增加。
   ②借阅：如果一种书的现存量大于零，则借出一本，登记借阅者的图书证号和归还期限。
   ③归还：注销对借阅者的登记，改变该书的现存量（如果借阅者归还所有的书，则注销该借阅者的信息）。

3. 测试数据：
   入库书号：ISBN 7-302-02368-9，ISBN 978-7-115-16985-3/TP，ISBN 978-7-302-03314-1，ISBN7-115-10563-4/TP·3043，ISBN 978-7-121-07479-0，ISBN 978-7-115-18809-0/TP，ISBN 978-7-04-024246-1，ISBN 7-111-12886-9，ISBN 978-7-115-19601-9/TP，ISBN 7-900183-01-9。
   借书证号为081716的借阅者，先借阅10种图书各一本，后归还图书ISBN 7-302-02368-9和ISBN 978-7-121-07479-0。
   借书证号为081710的借阅者，先借阅图书ISBN 978-7-121-07479-0和ISBN 978-7-302-03314-110各一本，后归还图书ISBN 978-7-121-07479-0。
   其余数据可自行设计。

4. 实现提示：
   （1）各种图书按登记的先后顺序入库（利用平衡二叉树实现动态查找表的插入），书号为图书的关键字。初始时，平衡二叉树为空树。
   （2）借阅者借阅图书时，先检查借阅者有无超期未归还图书，如有，则不能借阅，如无，利用平衡二叉树实现动态查找表的查找，登记借阅信息。注意，按规定，同一种书不能重复借阅。

【实验代码】

#include <bits/stdc++.h>
//#include <string>

using namespace std;

struct BorrowedBook // 书
{
    string bookNumber; // 书号
    string deadLine; // 归还期限
    BorrowedBook *next;
};

struct Student // 学生
{
    string studentNumber; // 借书号
    BorrowedBook *firstBook;
};

struct StudentBorrowedBook // 学生借书
{
    Student *student; // 借阅者数组
    int sum; // 借阅者总数
};

typedef struct Book {
    string name; // 书名
    string bookNumber; // 书号
    string author; // 作者
    int numNow; // 现存量
    int numTotal; //总存量
    int BF; // 平衡因子
    Book *lChild, *rChild; // 左右孩子
} Book, *AVLBook;

int InsertBook(AVLBook &book, string bookNumber, bool &flag); //插入新值,flag用于判定是否需要调整平衡因子

void addStudent(StudentBorrowedBook &stu, string studentNumber);//添加新学生
bool IsExistStu(StudentBorrowedBook stu, string numberStu); // 判断是否存在此学生
bool findStudent(StudentBorrowedBook stu, string numberStu, Student &res); // 寻找学生
int SearchTreeBorrow(AVLBook book, StudentBorrowedBook &stu, Student &student, string bookNumber, string time); // 寻找书并借书
int SearchTreeReturn(AVLBook book, StudentBorrowedBook &stu, Student &student, string bookNumber); // 寻找书并还书

void display(StudentBorrowedBook stu); // 描述借阅登记信息
void InOrderTraverse(AVLBook T); // 中序遍历
void printT(AVLBook T, int n); //凹入表打印树结构

int main() {
    AVLBook book = NULL;
    StudentBorrowedBook stu;
    stu.sum = 0;

    while (true) {
        cout << "请问您要做什么，入库书籍请按P，借书请按B，还书请按R，退出系统请按Q：" << endl;
        char ch;
        cin >> ch;
        if (ch == 'Q') {
            cout << "退出程序成功！" << endl;
            break;
        }
        switch (ch) {
            case 'P': { // 入库
                bool flag;
                int bookSum;
                cout << "请问您要入库几本书：" << endl;
                cin >> bookSum;
                for (int i = 0; i < bookSum; i++) {
                    cout << "请输入第" << i + 1 << "本书的书号：" << endl;
                    string bookNumber;
                    getchar();
                    getline(cin,bookNumber);
                    //cin >> bookNumber;
                    InsertBook(book, bookNumber, flag);
                }
                break;
            }
            case 'B': { // 借书
                cout << "请输入你的借书证号：" << endl;
                string studentNum;
                cin >> studentNum;
                getchar();
                cout << "请输入你要借的书的书号：" << endl;
                string bookNumber;
                getline(cin,bookNumber);
                //cin >> bookNumber;

                if (!IsExistStu(stu, studentNum)) // 不存在此学生
                {
                    addStudent(stu, studentNum); // 新建并添加此学生
                }
                Student nowStu;
                if(findStudent(stu, studentNum,nowStu))
                {
                    SearchTreeBorrow(book, stu, nowStu, bookNumber, "9");
                }

                break;
            }
            case 'R': { // 还书
                cout << "请输入你的借书证号：" << endl;
                string studentNum;
                cin >> studentNum;
                getchar();
                cout << "请输入你要还的书的书号：" << endl;
                string bookNumber;
                getline(cin,bookNumber);
                //cin >> bookNumber;

                Student nowStu;
                if(findStudent(stu, studentNum,nowStu))
                {
                    SearchTreeReturn(book, stu, nowStu, bookNumber);
                } else{
                    cout << "查无此人，无法还书！" << endl;
                }

                break;
            }
            default:
                cout << "输入的功能代码错误，请重新输入！" << endl;
        }
    }
    cout << "\n借阅人的信息有：" << endl;
    display(stu); // 打印借阅人信息
    cout << "中序遍历平衡二叉树：" << endl;
    InOrderTraverse(book);//中序遍历平衡二叉树
    cout << "\n凹入表打印平衡二叉树：" << endl;
    printT(book, 0); //凹入表打印平衡二叉树
    return 0;
}

void R_Rotate(AVLBook &book) // 右旋 顺时针旋转
{
    AVLBook tmp = book->lChild;
    book->lChild = tmp->rChild;
    tmp->rChild = book;
    book = tmp;
}

void L_Rotate(AVLBook &book) //左旋，逆时针旋转
{
    AVLBook tmp = book->rChild;
    book->rChild = tmp->lChild;
    tmp->lChild = book;
    book = tmp;
}

void leftBalance(AVLBook &book) //左边失衡调整
{
    AVLBook lchild = book->lChild;
    AVLBook tmpRightChild = NULL;
    switch (lchild->BF) {
        case 1:                                                                     //LL型失衡
            book->BF = lchild->BF = 0;
            R_Rotate(book);
            break;
        case -1:                                                                    //LR型失衡
            tmpRightChild = lchild->rChild;
            switch (tmpRightChild->BF) {
                case 1:
                    book->BF = -1;
                    lchild->BF = 0;
                    break;
                case 0:
                    book->BF = lchild->BF = 0;
                    break;
                case -1:
                    book->BF = 0;
                    lchild->BF = 1;
                    break;
            }
            tmpRightChild->BF = 0;
            L_Rotate(book->lChild);
            R_Rotate(book);
            break;
    }
}

void rightBalance(AVLBook &book) //右边失衡调整
{
    AVLBook rightchild = book->rChild;
    AVLBook tmpChild = NULL;
    switch (rightchild->BF) {
        case -1:                                                                          //RR型失衡
            book->BF = rightchild->BF = 0;
            L_Rotate(book);
            break;
        case 1:                                                                         //RL型失衡
            tmpChild = rightchild->lChild;
            switch (tmpChild->BF) {
                case 1:
                    book->BF = 0;
                    rightchild->BF = -1;
                    break;
                case 0:
                    book->BF = rightchild->BF = 0;
                    break;
                case -1:
                    book->BF = 0;
                    rightchild->BF = 1;
                    break;
            }
            tmpChild->BF = 0;
            R_Rotate(book->rChild);
            L_Rotate(book);
            break;
    }
}

AVLBook createBook(string bookNumber) //新建一个书节点
{
    AVLBook newBook = new Book;

    cout << "请输入书名：" << endl;
    cin >> newBook->name;
    newBook->bookNumber = bookNumber;
    cout << "请输入作者：" << endl;
    cin >> newBook->author;
    cout << "请输入总存量：" << endl;
    cin >> newBook->numTotal;

    newBook->numNow = newBook->numTotal;
    newBook->BF = 0;
    newBook->lChild = NULL;
    newBook->rChild = NULL;
    return newBook;
}

int InsertBook(AVLBook &book, string bookNumber, bool &flag) //插入新值,flag用于判定是否需要调整平衡因子
{
    if (book == NULL) {                                    //树中不包含此键值，则新建一个节点，
        book = createBook(bookNumber);
        flag = true;
    } else if (book->bookNumber == bookNumber) {                //树中已经包含此键值，则不需要插入
        book->numNow++; // 现存量+1
        book->numTotal++; // 总存量+1
        flag = false;
        return 0;
    } else if (bookNumber < book->bookNumber) {                  //插入到左子树中
        if (!InsertBook(book->lChild, bookNumber, flag))   //如果左子树中存在该节点
            return 0;
        if (flag) {
            switch (book->BF) {
                case 1:
                    leftBalance(book);
                    flag = false;
                    break;
                case -1:
                    book->BF = 0;
                    flag = false;
                    break;
                case 0:
                    book->BF = 1;
                    flag = true;
                    break;
            }
        }
    } else {
        if (!InsertBook(book->rChild, bookNumber, flag))   //如果右子树中存在该节点
            return 0;
        if (flag) {
            switch (book->BF) {
                case 1:
                    book->BF = 0;
                    flag = false;
                    break;
                case -1:
                    rightBalance(book);
                    flag = false;
                    break;
                case 0:
                    book->BF = -1;
                    flag = true;
                    break;
            }
        }
    }
    return 1;
}

void addStudent(StudentBorrowedBook &stu, string studentNumber) //添加新学生
{
    Student *newStu = new Student[stu.sum + 1];
    Student *oldStu = stu.student;

    for (int i = 0; i < stu.sum; i++) {
        newStu[i] = stu.student[i];
    }
    newStu[stu.sum].studentNumber = studentNumber;
    newStu[stu.sum].firstBook = new BorrowedBook;
    newStu[stu.sum].firstBook->next = NULL;

    stu.student = newStu;
    stu.sum++;
    //delete[] oldStu;
}

bool IsExistStu(StudentBorrowedBook stu, string numberStu) // 判断是否存在此学生
{
    for (int i = 0; i < stu.sum; i++) {
        if (stu.student[i].studentNumber == numberStu) {
            return true;
        }
    }
    return false;
}

bool findStudent(StudentBorrowedBook stu, string numberStu, Student &res) // 寻找学生
{
    for (int i = 0; i < stu.sum; i++) {
        if (stu.student[i].studentNumber == numberStu) {
            res = stu.student[i];
            return true;
        }
    }
    return false;
}

bool IsBook(Student stu, string bookNumber) // 判断此学生是否借过此书
{
    BorrowedBook *p = stu.firstBook->next;
    while (p) {
        if (p->bookNumber == bookNumber) {
            cout << "此学生借过此书了！" << endl;
            return true;
        }
        p = p->next;
    }
    return false;
}

bool IsOverTime(BorrowedBook *book, string time) // 判断是否超过借书日期
{
    return time < book->deadLine;
}

bool IsStuBookOverTime(Student stu, string time) // 判断是否超过借书日期
{
    BorrowedBook *p = stu.firstBook->next;
    while (p) {
        if (IsOverTime(p, time)) {
            cout << "有超时未归还的图书，不允许借书！" << endl;
            return true;
        }
        p = p->next;
    }
    return false;
}

void BorrowBook(Student &stu, string bookNumber) // 借阅一本书
{
    cout << "请输入归还日期：" << endl;
    string deadLine;
    cin >> deadLine;

    BorrowedBook *newBook = new BorrowedBook;
    newBook->bookNumber = bookNumber;
    newBook->deadLine = deadLine;

    newBook->next = stu.firstBook->next;
    stu.firstBook->next = newBook;
}

bool ReturnBook(Student &stu, string bookNumber) // 归还一本书
{
    BorrowedBook *delBook, *p = stu.firstBook->next, *q = stu.firstBook;
    while (p) {
        if (p->bookNumber == bookNumber) {
            q->next = p->next;
            return true;
        }
        q = p;
        p = p->next;
    }
    return false;
}

void deleteStudent(StudentBorrowedBook &stu, string studentNum) // 删除一个学生
{
    for (int i = 0; i < stu.sum; i++) {
        bool flag = true;
        if (stu.student[i].studentNumber == studentNum) {
            flag = false;
            for (int j = i + 1; j < stu.sum; j++) {
                stu.student[j - 1] = stu.student[j];
            }
        }
        if (!flag) {
            break;
        }
    }
    stu.sum--;
}

int SearchTreeBorrow(AVLBook book, StudentBorrowedBook &stu, Student &student, string bookNumber, string time) // 寻找书并借书
{
    if (book->bookNumber == bookNumber) {

        if (book->numNow > 0) // 如果此书库存大于0
        {
            if (!IsStuBookOverTime(student, time)) // 如果此借阅者没有超期未归还的书
            {
                if (!IsBook(student, book->bookNumber)) // 如果此学生没有借过此书
                {
                    BorrowBook(student, book->bookNumber);
                    book->numNow--;
                    cout << "学生" << student.studentNumber << "借了一本《" << book->name << "》，作者为" << book->author;
                    cout << "，书号为：" << book->bookNumber << "。库存" << book->numTotal << "本，现存";
                    cout << book->numNow << "本" << endl;
                }
            }
        } else {
            cout << "此书已经被借阅完，无余书！" << endl;
        }
        return 1;
    } else if (bookNumber > book->bookNumber && book->rChild) {
        return SearchTreeBorrow(book->rChild, stu,student, bookNumber, time);
    } else if (bookNumber < book->bookNumber && book->lChild) {
        return SearchTreeBorrow(book->lChild, stu,student, bookNumber, time);
    } else {
        cout << "查无此书！" << endl;
        if (student.firstBook->next == NULL) // 如果此学生的所借书为零，那么删除此学生
        {
            deleteStudent(stu, student.studentNumber);
        }
        return 0;
    }
}

int SearchTreeReturn(AVLBook book, StudentBorrowedBook &stu, Student &student, string bookNumber) // 寻找书并还书
{
    if (book->bookNumber == bookNumber) { // 找到书

        if (ReturnBook(student, book->bookNumber)) // 还书
        {
            book->numNow++; // 图书馆书现储备量增加
            cout << "学生" << student.studentNumber << "还了一本《" << book->name << "》，作者为" << book->author;
            cout << "，书号为：" << book->bookNumber << "。库存" << book->numTotal << "本，现存";
            cout << book->numNow << "本" << endl;

            if (student.firstBook->next == NULL) // 如果此学生的所借书为零，那么删除此学生
            {
                deleteStudent(stu, student.studentNumber);
            }
        } else
        {
            cout << "此学生未借此书，无法归还！" << endl;
        }

        return 1;
    } else if (bookNumber > book->bookNumber && book->rChild) {
        return SearchTreeReturn(book->rChild, stu, student, bookNumber);
    } else if (bookNumber < book->bookNumber && book->lChild) {
        return SearchTreeReturn(book->lChild, stu, student, bookNumber);
    } else {
        cout << "查无此书！" << endl;
        return 0;
    }
}

void display(StudentBorrowedBook stu) // 描述借阅登记信息
{
    for (int i = 0; i < stu.sum; i++) {
        BorrowedBook *p = stu.student[i].firstBook->next;
        cout << "此人借书号为：" << stu.student[i].studentNumber << "   所借书籍的书号有：  ";
        while (p) {
            cout << p->bookNumber << " ";
            p = p->next;
        }
        cout << endl;
    }
}

void InOrderTraverse(AVLBook T) // 中序遍历
{
    if (T == NULL) {
        return;
    }

    InOrderTraverse(T->lChild);
    cout << "书号：" << T->bookNumber << "  现存量：" << T->numNow << "  ";
    InOrderTraverse(T->rChild);
}

void printT(AVLBook T, int n) //凹入表打印树结构
{
    if (T) {
        printT(T->rChild, n + 1);
        for (int i = 0; i < n; i++) {
            cout << "   ";
        }
        if (n >= 0) {
            cout << T->bookNumber << endl;
        }
        printT(T->lChild, n + 1);
    }
}