图书信息管理系统

功能架构图

查询书本信息

• 对于每本书的信息，只需要找到给定书在程序内所对应的地址，用给定的检索来找到给定书的地址即可。

  • 定义Book结构体大致内容如下：

    const int slenth = 1e2;
    struct Book{
        int ISBN;
        char name[slenth];
        char author[slenth];
        int price;
    };
    typedef struct Book *BookP;
    

添加书本

• 对于新添加的书，向系统申请一块新的Book结构体空间用于储存信息
  • 特别的，需要先在现有的所有书中判断是否存在与新书一样的ISBN码，若存在，则此次操作无效

删除书本

• 根据检索找到对应的书所在的地址，将其释放，并在所有书的检索中删除这本书的所有信息。

修改书本信息

• 根据检索找到书本结构体所在的地址，修改其内容即可。

排序

• 因为给定前提“频繁地进行操作”同时要用价格进行排序，那么考虑用一棵AVL树以价格为节点大小进行维护整棵树，从而实现O(log n)的复杂度进行每个节点的排序，输出排序后的所有信息考虑O(n)的dfs对AVL树进行先序遍历即可。

  • 对于每种信息的检索，都考虑用一棵AVL树来维护，以ISBN为检索举例，树的结构大致如下：

    typedef struct node{
        ElementType ISBN;
        int height;
        BookP cur;
        struct node* left;
        struct node* right;
    }AVL;
    

• BookP cur为当前节点ISBN码对应的结构体地址，以此实现检索找到对应书本的具体信息。那么用AVL树或STL map维护后以上操作的复杂度如下：

1. 查询书本信息：以二分的形式按照检索在树中进行查找O(log n)
2. 添加书本：在树中找到对应位置进行插入O(log n)
3. 删除书本：先找到再删除O(log n)
4. 修改书本信息：先找到再修改O(log n)
5. 排序：因为添加和删除都是有序的，所以排序不需要另外的时间，输出整个有序序列的复杂度为O(n)，原理为对树进行先序遍历
   

关键代码

一、AVL树的维护：

1. 主要操作：

   AVL* Insert(AVL* root,ElementType ISBN);
   int GetHeight(AVL* root);
   int Max(int a,int b);
   AVL* RRRotation(AVL* root);
   AVL* RLRotation(AVL* root);
   AVL* LLRotation(AVL* root);
   AVL* LRRotation(AVL* root);
   

2. 实现：

   AVL* RRRotation(AVL* root){
       AVL* B = root->right;
       root->right = B->left;
       B->left = root;
       B->height = Max(GetHeight(B->left),GetHeight(B->right))+1;
       root->height = Max(GetHeight(root->left),GetHeight(root->right))+1;
       return B;
   }
   AVL* RLRotation(AVL* root){
       AVL* B = root->right;
       AVL* C = B->left;
       root->right = C->left;
       B->left = C->right;
       C->left = root;
       C->right = B;
       C->height = Max(GetHeight(C->left),GetHeight(C->right))+1;
       B->height = Max(GetHeight(B->left),GetHeight(B->right))+1;
       root->height = Max(GetHeight(root->left),GetHeight(root->right))+1;
       return C;
   }
   AVL* LLRotation(AVL* root){
       AVL* B = root->left;
       root->left = B->right;
       B->right = root;
       B->height = Max(GetHeight(B->left),GetHeight(B->right))+1;
       root->height = Max(GetHeight(root->left),GetHeight(root->right))+1;
       return B;
   }
   AVL* LRRotation(AVL* root){
       AVL* B = root->left;
       AVL* C = B->right;
       B->right = C->left;
       root->left = C->right;
       C->left = B;
       C->right = root;
       C->height = Max(GetHeight(C->left),GetHeight(C->right))+1;
       B->height = Max(GetHeight(B->left),GetHeight(B->right))+1;
       root->height = Max(GetHeight(root->left),GetHeight(root->right))+1;
       return C;
   }
   AVL* Insert(AVL* root,ElementType ISBN){
       if(!root){
           root = (AVL*)malloc(sizeof(AVL));
           root->ISBN = ISBN;
           root->height = 0;
           root->left = root->right = NULL;
       }
       else{
           if(ISBN > root->ISBN){
               root->right = Insert(root->right,ISBN);
               if( GetHeight(root->right)-GetHeight(root->left) == 2){
                   if(ISBN > root->right->ISBN){
                       root = RRRotation(root);
                   }
                   else{
                       root = RLRotation(root);
                   }
               }
           }
           else if(ISBN < root->ISBN){
               root->left = Insert(root->left,ISBN);
               if(GetHeight(root->left)-GetHeight(root->right)==2){
                   if(ISBN<root->left->ISBN){
                       root = LLRotation(root);
                   }
                   else{
                       root = LRRotation(root);
                   }
               }
           }
       }
       root->height = Max(GetHeight(root->left),GetHeight(root->right))+1;
       return root;
   }
   int GetHeight(AVL* root){
       int HL = 0,HR = 0,MaxH = 0;
       if(root){
           HL = GetHeight(root->left);
           HR = GetHeight(root->right);
           MaxH = Max(HL,HR);
           return MaxH+1;
       }
       else{
           return 0;
       }
   }
   int Max(int a,int b){
   return a>b?a:b;
   }
   

二、对于树的查找与删除操作：

1. 主要操作：

   AVL* Delete( AVL* BST, ElementType X );
   AVL* Find( AVL* BST, ElementType X );
   AVL* FindMin( AVL* BST );
   AVL* FindMax( AVL* BST );
   

2. 实现：

   AVL* FindMin( AVL* BST ){
       while(BST&&BST->Left){
           BST = BST->Left;
       }
       return BST;
   }
   AVL* FindMax( AVL* BST ){
       while(BST&&BST->Right){
           BST = BST->Right;
       }
       return BST;
   }
   AVL* Delete( AVL* BST, ElementType X ){
       AVL* Tmp;
       if(!BST){
           printf("Not Found\n");
       }
       else if(X>BST->ISBN){
           BST->Right = Delete(BST->Right,X);
       }
       else if(X<BST->ISBN){
           BST->Left = Delete(BST->Left,X);
       }
       else{
           if(BST->Left&&BST->Right){
               Tmp = FindMin(BST->Right);
               BST->ISBN = Tmp->ISBN;
               BST->Right = Delete(BST->Right,BST->ISBN);
           }
           else{
               Tmp = BST;
               if(!BST->Left){
                   BST = BST->Right;
               }
               else if(!BST->Right){
                   BST = BST->Left;
               }
               free(Tmp);
           }
       }
       return BST;
   }
   AVL* Find( AVL* BST, ElementType X ){
       if(!BST){
           return NULL;
       }
       if(X>BST->ISBN){
           return Find(BST->Right,X);
       }
       else if(X<BST->ISBN){
           return Find(BST->Left,X);
       }
       else return BST;
   }