数据结构课程设计(基于AVL树的身份证管理系统)

#include<bits/stdc++.h>
 
using namespace std;
 
/*文件的操作*/
ofstream mycout("Information.txt");//c++牛逼
 
//相关信息的结构体数据结构
struct Person{
    
    string idnumber;//身份证号码
    string name;//姓名
    string address;//地址
    string phonenumber;//手机号码
    
}person;
 
//平衡二叉树的二叉链表节点数据结构
typedef struct BiTNode{
 
    //int height;//节点的高度
    Person person;//数据域
    struct BiTNode *lchild,*rchild;//指针域
    
    //结构体的初始化
    BiTNode()
    {
        lchild = rchild = NULL;
    }
 
}BiTNode, *BiTree;
 
BiTree T;//空树
BiTree temp;//保存找到的那个id的指针
 
//获得树当前节点的高度
int Get_Height(BiTree T)
{
    if(T == NULL)
        return 0;//空树
    return max(Get_Height(T->lchild),Get_Height(T->rchild)) + 1;//左右子树中较高的 + 1
}
 
/*
    LL型失衡，调整二叉树需要两步
    第一步：将失衡节点的左子树的右子树 变成 失衡节点的左子树
    第二步：失衡节点 变成 失衡节点未发生操作前左子树的右子树
*/
 
BiTree LL_Rotation(BiTree T)
{
    BiTree temp;
    temp = T->lchild;//临时保存失衡节点的左子树
    T->lchild = temp->rchild;//将失衡节点的左子树的右子树 变成 失衡节点的左子树
    temp->rchild = T;//失衡节点变成temp的右子树
    return temp;
}
 
/*
    RR型失衡
    RR型的操作和基本相同，只是方向相反
*/
 
BiTree RR_Rotation(BiTree T)
{
    BiTree temp;
    temp = T->rchild;//临时保存失衡节点的右子树
    T->rchild = temp->lchild;//将失衡节点的右子树的左子树 变成 失衡节点的右子树
    temp->lchild = T;//失衡节点变成temp的左子树
    return temp;
}
 
/*
    LR型失衡
    LR型失衡的操作相比于LL型失衡操作相对要复杂一点，需要旋转两次才能恢复平衡
    第一步：对失衡节点的左子树进行RR型旋转
    第二步：对失衡节点进行LL型旋转
*/
 
BiTree LR_Rotation(BiTree T)
{
    T->lchild = RR_Rotation(T->lchild);//对失衡节点的左子树进行RR型旋转
    return LL_Rotation(T);//对失衡节点进行LL型旋转
}
 
/*
    RL失衡
    和LR型的旋转基本相同
*/
 
BiTree RL_Rotation(BiTree T)
{
    T->rchild = LL_Rotation(T->rchild);//对失衡节点的右子树进行LL型旋转
    return RR_Rotation(T);//对失衡节点进行RR型旋转
}
 
/*
    创建树,也就是信息的录入
    能够进行身份证号码及相关信息的录入，相关信息包括姓名、地址和手机号
*/
BiTree CreateTree(BiTree T, Person person)
{
    if(T == NULL)//空树
    {
        BiTree temp = new BiTNode;
        temp->lchild = temp->rchild = NULL;
        temp->person = person;
        return temp;
    }
    /*身份证长度肯定一样长，因此也就是比较每一位数字，数字越大越往前靠*/
    /*根据字典序来排idnumber*/
    /*大于*/
    else if(person.idnumber > T->person.idnumber)
    {
        T->rchild = CreateTree(T->rchild,person);
        if(Get_Height(T->rchild) - Get_Height(T->lchild) == 2)//右子树 - 左子树
        {
            if(person.idnumber < T->rchild->person.idnumber)
                T = RL_Rotation(T);
            else
                T = RR_Rotation(T);
        }
    }
    /*小于*/
    else if(person.idnumber < T->person.idnumber)
    {
        T->lchild = CreateTree(T->lchild,person);
        if(Get_Height(T->lchild) - Get_Height(T->rchild) == 2)//左子树 - 右子树
        {
            if(person.idnumber < T->lchild->person.idnumber)
                T = LL_Rotation(T);
            else
                T = LR_Rotation(T);
        }
    }
    else if(person.idnumber == T->person.idnumber)
    {
        cout << "输入有误，身份证号不应该相同" << endl << endl;
        return T;
    }
    return T;
}
 
/*
    信息的查找
    能够快速进行身份证号码的查询，并输出相关信息
*/
bool SearchTree(BiTree T,string id)
{
    if(T == NULL)
    {
        cout << "查找值不存在!" << endl;
        return false;
    }
    else
    {
        if(T->person.idnumber == id)
        {
            temp = T;//记录当前节点指针
            cout << "姓名为:    " << T->person.name << endl;
            cout << "身份证号为:    " << T->person.idnumber << endl;
            cout << "家庭地址为:    " << T->person.address << endl;
            cout << "电话号码为:    " << T->person.phonenumber << endl;
        }
        else if(T->person.idnumber < id)//根据字典序来排大小，如果当前节点的idnumber小于查找的idnumber
        {
            SearchTree(T->rchild,id);
        }
        else if(T->person.idnumber > id)//根据字典序来排大小，如果当前节点的idnumber大于查找的idnumber
        {
            SearchTree(T->lchild,id);
        }
    }
    return true;
}
 
bool modificationTree(BiTree T,string id)
{
    /*存在才要修改*/
    if(SearchTree(T,id))
    {
        cout << "请输入你想要修改的信息类型(姓名,地址,手机号码)" << endl;
        string s;
        cin >> s;
        if(s == "姓名")
        {
            cout << "请输入修改后的值:    ";
            cin >> person.name;
            temp->person.name = person.name;
        }
        else if(s == "地址")
        {
            cout << "请输入修改后的值:    ";
            cin >> person.address;
            temp->person.address = person.address;
        }
        else if(s == "手机号码")
        {
            cout << "请输入修改后的值:    ";
            cin >> person.phonenumber;
            temp->person.phonenumber = person.phonenumber;
        }
    }
    else
    {
        cout << "查无此人，抱歉" << endl;
        return false;
    }
    return true;
}
 
/* 若二叉排序树T中存在关键字等于id的数据元素时，则删除该数据元素结点, */
/* 并返回TRUE；否则返回FALSE。 */
bool removeTree(BiTree *T,string id)
{
    //从二叉排序树中删除关键字为id的节点
    if(!*T)
    {
        cout << "查无此人，无法删除!" << endl;
        return false;
    }
    else
    {
        if(id == (*T)->person.idnumber)
        {
            BiTree q,s;
            if((*T)->rchild == NULL) /* 右子树空则只需重接它的左子树（待删结点是叶子也走此分支) */
            {
                q = *T;
                *T = (*T)->lchild;
                free(q);
            }
            else if((*T)->lchild == NULL) /* 只需重接它的右子树 */
            {
                q = *T;
                *T = (*T)->rchild;
                free(q);
            }
            else /* 左右子树均不空 */
            {
                q = *T;
                s = (*T)->lchild;
                while(s->rchild) /* 转左，然后向右到尽头（找待删结点的前驱） */
                {
                    q = s;
                    s = s->rchild;
                }
                (*T)->person = s->person; /*  s指向被删结点的直接前驱（将被删结点前驱的值取代被删结点的值） */
                if(q != (*T))
                    q->rchild = s->lchild; /*  重接q的右子树 */
                else
                    q->lchild = s->lchild; /*  重接q的左子树 */
                free(s);
            }
        }
        else if(id < (*T)->person.idnumber)
            return removeTree(&(*T)->lchild,id);
        else
            return removeTree(&(*T)->rchild,id);
    }
    return true;
}
 
/*中序遍历AVL树，并打印节点高度*/
void Midorder_Traverse(BiTree T)
{
    if(T != NULL)
    {
        Midorder_Traverse(T->lchild);
        cout << endl;
        cout << "姓名: " << T->person.name << endl;
        cout << "身份证号: " << T->person.idnumber << endl;//<< " " << "高度: " << Get_Height(T) << endl;
        cout << "地址: " <<T->person.address << endl;
        cout << "手机号码: " <<T->person.phonenumber << endl;
        Midorder_Traverse(T->rchild);
    }
    return;
}
 
/*文件操作*/
void Midorder_TraverseToFile(BiTree T)
{
    if(T != NULL)
    {
        Midorder_TraverseToFile(T->lchild);
        //cout << endl;
        mycout << "姓名: " << T->person.name << endl;
        mycout << "身份证号: " << T->person.idnumber << endl;//<< " " << "高度: " << Get_Height(T) << endl;
        mycout << "地址: " <<T->person.address << endl;
        mycout << "手机号码: " <<T->person.phonenumber << endl;
        Midorder_TraverseToFile(T->rchild);
    }
    return;
}
 
/*录入信息的输入*/
void InformationInput()
{
    char ch;
    while(true)
    {
        cout << "输入信息?(Y/N):    ";
        cin >> ch;
        if(ch == 'Y' || ch == 'y')
        {
            cout << "请输入姓名:    ";
            cin >> person.name;
            cout << "请输入身份证号:    ";
            cin >> person.idnumber;
            cout << "请输入家庭地址:    ";
            cin >> person.address;
            cout << "请输入手机号码:    ";
            cin >> person.phonenumber;
            T = CreateTree(T,person);
        }
        else if(ch == 'N' || ch == 'n')
        {
            cout << "录入结束，谢谢合作!" << endl << endl;
            return;
        }
        else
        {
            cout << "关键字输入错误,请重新输入!" << endl;
            continue;
        }
    }
}
 
/*查询信息的输入*/
void SearchInformationInput()
{
    char ch;
    while(true)
    {
        cout << "是否查找?(Y/N):    ";
        cin >> ch;
        if(ch == 'Y' || ch == 'y')
        {
            cout << "请输入你想要查找的身份证号码:    ";
            cin >> person.idnumber;
            SearchTree(T,person.idnumber);
        }
        else if(ch == 'n' || ch == 'N')
        {
            cout << "查找结束，祝您愉快!" << endl << endl;
            return;
        }
        else
        {
            cout << "关键字输入错误,请重新输入!" << endl;
            continue;
        }
    }
}
 
/*修改信息的输入*/
void modificationInformationInput()
{
    char ch;
    while(true)
    {
        cout << "修改信息?(Y/N):    ";
        cin >> ch;
        if(ch == 'Y' || ch == 'y')
        {
            cout << "请输入您修改人信息对应的身份证号:    ";
            cin >> person.idnumber;
            modificationTree(T,person.idnumber);
        }
        else if(ch == 'N' || ch == 'n')
        {
            cout << "修改操作已经结束，您可以继续其他操作!" << endl;
            return;
        }
        else
        {
            cout << "关键字输入错误,请重新输入!" << endl;
            continue;
        }
    }
}
 
//身份证及相关信息的删除
void RemoveIdNumberInformationInput()
{
    char ch;
    while(true)
    {
        cout << "删除信息?(Y/N): ";
        cin >> ch;
        if(ch == 'Y' || ch == 'y')
        {
            cout << "请输入您删除人信息对应的身份证号:    ";
            cin >> person.idnumber;
            if(removeTree(&T,person.idnumber))
                cout << "删除成功!" << endl;
            else
                cout << "删除失败!" << endl;
        }
        else if(ch == 'N' || ch == 'n')
        {
            cout << "修改操作已经结束，您可以继续其他操作!" << endl;
            return;
        }
        else
        {
            cout << "关键字输入错误,请重新输入!" << endl;
            continue;
        }
    }
}
 
int main()
{
    int n = 0;
    cout << "************************************************************"<< endl;
    cout << "*             基于二叉排序树身份证管理系统                 *" << endl;
    cout << "* \t\t1.相关信息的录入\t\t           *" << endl;
    cout << "* \t\t2.相关信息的查找\t\t           *" << endl;
    cout << "* \t\t3.相关信息的修改\t\t           *" << endl;
    cout << "* \t\t4.相关信息的删除\t\t           *" << endl;
    cout << "* \t\t5.将相关信息保存到文件中\t\t   *" << endl;
    cout << "* \t\t6.遍历(将信息输出在控制台) \t           *" << endl;
    cout << "************************************************************" << endl << endl;
    cout << "\t     ***欢迎使用该系统***     \t\t" << endl;
    cout << "\t温馨提示,输入 -1 用来结束输入操作哦!\t" << endl << endl;
    while(n != -1)
    {
        cout << "请输入你想要执行的操作:";
        cin >> n;
        cout << endl;
        switch (n)
        {
            case 1:
                InformationInput();//建立树，也就是信息的建立
                break;
            case 2:
                SearchInformationInput();//相关信息的查找
                break;
            case 3:
                modificationInformationInput();//相关信息的修改
                break;
            case 4:
                RemoveIdNumberInformationInput();//身份证信息的删除
                break;
            case 5:
                Midorder_TraverseToFile(T);//将信息保存在文本文档中
                break;
            case 6:
                cout << "*****该系统中的用户列表如下*****" << endl;
                Midorder_Traverse(T);//前序遍历
                cout << endl;
                cout << "********************************" << endl;
                break;
        }
          if(n != -1)
        {
            cout << endl;
            cout << "*****输入-1用来结束输入操作哦!*****" << endl;
            cout << "1.相关信息的录入" << endl;
            cout << "2.相关信息的查找" << endl;
            cout << "3.相关信息的修改" << endl;
            cout << "4.相关信息的删除" << endl;
            cout << "5.将相关信息保存到文件中" << endl;
            cout << "6.遍历" << endl << endl;
        }
        else
        {
            cout << "***您的操作已经结束，祝您愉快!***" << endl;
          }
    }
    return 0;
}