用B-树实现虚拟图书管理系统

学校数据结构的课程实验之一。

用到的数据结构：B-树

基本功能：对虚拟书库的图书进行查看、增加、删除、修改。

主函数：

 1 #include <iostream>
 2 #include "Library.h"
 3 using namespace std;
 4 int main()
 5 {
 6     Library myLib=Library("books.txt");
 7     char choice='y';
 8     while(choice=='y')
 9     {
10         cout << "请选择操作"<<endl;
11         cout << "--------------------------------" << endl;
12         cout << "1----新书入库" << endl;
13         cout << "2----查看库存" << endl;
14         cout << "3----借阅" << endl;
15         cout << "4----归还" << endl;
16         cout << "5----删除旧书" << endl;
17         cout << "6----修改图书信息" << endl;
18         cout << "--------------------------------" << endl;
19         int option;
20         cin >> option;
21         switch (option)
22         {
23         case 1: myLib.add(); break;
24         case 2: myLib.display(); break;
25         case 3: myLib.lend(); break;
26         case 4: myLib.back(); break;
27         case 5: myLib.remove(); break;
28         case 6: myLib.change(); break;
29         }
30         cout << "继续吗?[y/n]";
31         cin >> choice;
32     }
33     cout << "是否保存修改？[y/n]";
34     cin >> choice;
35     if (choice == 'y')
36         myLib.save("books.txt");//需要保存时保存文件
37     return 0;
38 }

图书馆类：

  1 #include <fstream>
  2 #include <string>
  3 #include "B_tree.h"
  4 using namespace std;
  5 
  6 struct Book
  7 {
  8     int number;
  9     string name;
 10     string introduction;
 11     unsigned left;
 12     Book(){}
 13     Book(int num) :number(num), name(""), introduction(""), left(0){}//只有编号的初始化
 14     Book(int num, string nam,string intro, unsigned lef)//完整初始化
 15         :number(num),name(nam),introduction(intro),left(lef){}
 16     void print()//显示信息
 17     {
 18         cout << "-------------------------------" << endl;
 19         cout << "这本书的信息如下：" << endl;
 20         cout << "编号: " << number << endl;
 21         cout << "书名: " << name << endl;
 22         cout << "简介: " << introduction << endl;
 23         cout << "剩余数量: " << left << endl;
 24         cout << "-------------------------------" << endl;
 25     }
 26     bool operator==(const Book &b) const//重载关系运算符
 27     {
 28         if(this->number == b.number) return true;//编号等即命中
 29         else return false;
 30     }
 31     bool operator<(const Book &b) const
 32     {
 33         if (this->number < b.number) return true;
 34         else return false;
 35     }
 36     bool operator>(const Book &b) const
 37     {
 38         if (this->number > b.number) return true;
 39         else return false;
 40     }
 41 };
 42 ofstream outFile;//输出流
 43 
 44 class Library
 45 {
 46 private:
 47     B_tree<Book,3> books;
 48     unsigned total;
 49     static void readBook(Book &aBook)//写一本书的内容（一定要是静态的） 
 50     {
 51         outFile<<aBook.number<<endl;
 52         outFile<<aBook.name<<endl;
 53         outFile<<aBook.introduction<<endl;
 54         outFile << aBook.left << endl;
 55     }
 56     void readFile(const char filename[20])//读文件
 57     {
 58         total = 0;
 59         ifstream inFile;
 60         inFile.open(filename);
 61         char trying;
 62         while(inFile.is_open() && !inFile.eof())
 63         {
 64             //先试探是否为结束符
 65             inFile >> trying;
 66             if (trying == '#') break;
 67             else
 68             {
 69                 inFile.putback(trying);
 70                 int number;
 71                 inFile>>number;
 72                 string name;
 73                 inFile>>name;
 74                 string introduction;
 75                 inFile>>introduction;
 76                 unsigned left;
 77                 inFile>>left;
 78                 Book aBook=Book(number,name,introduction,left);
 79                 aBook.print();//显示这本书的信息
 80                 books.insert(aBook);
 81                 total+=left;
 82             }            
 83         }
 84         cout << "库存共有图书" << total << "本"<<endl;
 85         inFile.close();
 86     }
 87     void writeFile(const char filename[20])//写文件
 88     {
 89         outFile.open(filename);
 90         books.traverse(readBook);
 91         outFile << '#';//此处必须有一个结束标识符
 92         outFile.close();
 93     }
 94     Book search(int num)//以编号为依据进行查找
 95     {
 96         Book se_book(num);
 97         books.search_tree(se_book);
 98         return se_book;
 99     }
100     static void print(Book &aBook)//显示信息（必须是静态的）
101     {
102         cout << "-------------------------------" << endl;
103         cout << "这本书的信息如下：" << endl;
104         cout << "编号: " << aBook.number << endl;
105         cout << "书名: " << aBook.name << endl;
106         cout << "简介: " << aBook.introduction << endl;
107         cout << "剩余数量: " << aBook.left << endl;
108         cout << "-------------------------------" << endl;
109     }
110 public:
111     Library(const char filename[20])
112     {
113         cout << "这是现在的库存信息：" << endl;
114         readFile(filename);
115     }
116     void add()//增加图书
117     {
118         cout << "请输入图书信息(编号 书名 简介 数量)" << endl;
119         int num;
120         string name;
121         string introduction;
122         unsigned left;
123         cin >> num >> name >> introduction >> left;
124         Book new_book = Book(num, name, introduction, left);
125         books.insert(new_book);
126         cout << "这本书已入库，信息如下：" << endl;
127         new_book.print();
128         total += left;
129     }
130     void display()//查看库存
131     {
132         cout << "这是现在的库存信息：" << endl;
133         books.traverse(print);
134         cout << "库存共有图书" << total << "本" << endl;
135     }
136     void remove()//删除
137     {
138         cout << "请输入要删除的图书编号：";
139         int num;
140         cin >> num;
141         Book &old_book =search(num);//通过编号找到这本书的记录
142         cout << "您即将删除这本书的所有信息：" << endl;
143         old_book.print();
144         cout << "确定要删除吗？[y/n]";
145         char choice;
146         cin >> choice;
147         if (choice == 'y')
148         {
149             books.remove(old_book);//删除这本书的记录
150             cout << "编号为" << num << "的书已成功从库中删除" << endl;
151             total--;
152         }        
153     }
154     void lend()//借出
155     {
156         cout << "请输入要借出的图书编号：";
157         int num;
158         cin >> num;
159         Book &old_book = search(num);//通过编号找到这本书的记录
160         old_book.left--;
161         cout << "编号为" << num << "的图书已借出1本，下面是这本书的现存信息：" << endl;
162         old_book.print();
163         total--;
164     }
165     void change()//修改（先删除再添加）
166     {
167         cout << "请输入要修改的图书编号：";
168         int num;
169         cin >> num;
170         Book &old_book = search(num);
171         cout << "这是这本书的当前信息：" << endl;
172         old_book.print();//显示这本书之前的信息
173         books.remove(old_book);
174         cout << "请输入修改后的图书信息（编号 书名 简介 数量）" << endl;
175         string name;
176         string introduction;
177         unsigned left;
178         cin >> num >> name >> introduction >> left;
179         Book new_book = Book(num, name, introduction, left);
180         books.insert(new_book);
181         cout << "这本书的信息已修改为：" << endl;
182         new_book.print();
183     }
184     void back()//归还
185     {
186         cout << "请输入要归还的图书编号：";
187         int num;
188         cin >> num;
189         Book &old_book = search(num);//通过编号找到这本书的记录
190         old_book.left++;
191         cout << "编号为" << num << "的图书已归还，下面是这本书的现存信息：" << endl;
192         old_book.print();
193         total++;
194     }
195     void save(const char filename[20])
196     {
197         writeFile(filename);
198     }
199 };

Library.h

B-树的实现参考了经典教材"Data Structures and Program Design in C++" Robert L. Kruse, Alexander J. Ryba 高等教育出版社-影印版，代码如下：

  1 #include <iostream>
  2 using namespace std;
  3 enum Error_code
  4 {
  5     success, not_present, overflow, duplicate_error
  6 };
  7 
  8 template <class Record, int order>//阶数（分支数）
  9 struct B_node
 10 {
 11     int count;//成员数
 12     Record data[order-1];
 13     B_node<Record,order> *branch[order];
 14     B_node(){count=0;}
 15 };
 16 
 17 template <class Record, int order>
 18 class B_tree
 19 {
 20 public:
 21     B_tree(){root=NULL;}
 22     Error_code search_tree(Record &target)
 23     {
 24         return recursive_search_tree(root,target);
 25     }
 26     Error_code insert(const Record &new_entry)
 27     {
 28         Record median;
 29         B_node<Record,order> *right_branch, *new_root;
 30         Error_code result=push_down(root,new_entry,median,right_branch);
 31         if(result==overflow)
 32         {
 33             new_root=new B_node<Record,order>;
 34             new_root->count=1;
 35             new_root->data[0]=median;
 36             new_root->branch[0]=root;
 37             new_root->branch[1]=right_branch;
 38             root=new_root;
 39             result=success;
 40         }
 41         return result;
 42     }
 43     Error_code remove(const Record &target)
 44     {
 45         Error_code result;
 46         result=recursive_remove(root, target);
 47         if(root != NULL && root->count==0)
 48         {
 49             B_node<Record,order> *old_root=root;
 50             root=root->branch[0];
 51             delete old_root;
 52         }
 53         return result;
 54     }
 55     void traverse(void (*visit)(Record &))
 56     {
 57         recursie_traverse(root,visit);
 58     }
 59 private:
 60     B_node<Record, order> *root;
 61     void recursie_traverse(B_node<Record,order> *current, void (*visit)(Record &))
 62     {
 63         if(current!=NULL)
 64         {
 65             for(int i=0; i<current->count; i++)
 66                 (*visit)(current->data[i]);
 67             for(int i=0; i<current->count+1; i++)
 68                 recursie_traverse(current->branch[i], visit);
 69         }
 70     }
 71     Error_code search_node(B_node<Record,order> *current, const Record &target, int &position) const
 72     {
 73         position=0;
 74         while(position < current->count && (target > current->data[position]))
 75             position++;
 76         if(position < current->count && target == current->data[position])
 77             return success;
 78         else return not_present;
 79     }
 80     Error_code recursive_search_tree(B_node<Record,order> *current, Record &target)
 81     {
 82         Error_code result=not_present;
 83         int position;
 84         if(current != NULL)
 85         {
 86             result=search_node(current,target,position);
 87             if(result==not_present)
 88                 result=recursive_search_tree(current->branch[position],target);
 89             else
 90                 target=current->data[position];
 91         }
 92         return result;
 93     }
 94     void split_node(B_node<Record,order> *current, const Record &extra_entry,
 95         B_node<Record,order> *extra_branch, int position, 
 96         B_node<Record,order>*&right_half, Record &median)
 97     {
 98         right_half=new B_node<Record,order>;
 99         int mid=order/2;
100         if(position <= mid)
101         {
102             for(int i=mid; i<order-1; i++)
103             {
104                 right_half->data[i-mid]=current->data[i];
105                 right_half->branch[i+1-mid]=current->branch[i+1];
106             }
107             current->count=mid;
108             right_half->count=order-1-mid;
109             push_in(current,extra_entry,extra_branch,position);
110         }
111         else
112         {
113             mid++;
114             for(int i=mid; i<order-1; i++)
115             {
116                 right_half->data[i-mid]=current->data[i];
117                 right_half->branch[i+1-mid]=current->branch[i+1];
118             }
119             current->count=mid;
120             right_half->count=order-1-mid;
121             push_in(right_half,extra_entry,extra_branch,position-mid);
122         }
123         median=current->data[current->count-1];
124         right_half->branch[0]=current->branch[current->count];
125         current->count--;
126     }
127     void push_in(B_node<Record,order> *current, const Record &entry,
128         B_node<Record,order> *right_branch, int position)
129     {
130         for(int i=current->count; i>position; i--)
131         {
132             current->data[i]=current->data[i-1];
133             current->branch[i+1]=current->branch[i];
134         }
135         current->data[position]=entry;
136         current->branch[position+1]=right_branch;
137         current->count++;
138     }
139     Error_code push_down(B_node<Record,order> *current, const Record &new_entry,
140         Record &median, B_node<Record,order>*&right_branch)
141     {
142         Error_code result;
143         int position;
144         if(current==NULL)
145         {
146             median=new_entry;
147             right_branch=NULL;
148             result=overflow;
149         }
150         else
151         {
152             if(search_node(current,new_entry,position)==success)
153                 result=duplicate_error;
154             else
155             {
156                 Record extra_entry;
157                 B_node<Record,order> *extra_branch;
158                 result=push_down(current->branch[position],new_entry,
159                     extra_entry,extra_branch);
160                 if(result==overflow)
161                 {
162                     if(current->count < order-1)
163                     {
164                         result=success;
165                         push_in(current,extra_entry,extra_branch,position);
166                     }
167                     else
168                         split_node(current,extra_entry,extra_branch,position,
169                             right_branch,median);
170                 }
171             }
172         }
173         return result;
174     }
175     void restore(B_node<Record,order> *current, int position)
176     {
177         if(position==current->count)
178             if(current->branch[position-1]->count > (order-1)/2)
179                 move_right(current,position-1);
180             else
181                 combine(current,position);
182         else if(position==0)
183             if(current->branch[1]->count > (order-1)/2)
184                 move_left(current,1);
185             else
186                 combine(current,1);
187         else
188             if(current->branch[position-1]->count > (order-1)/2)
189                 move_right(current,position-1);
190             else if(current->branch[position+1]->count > (order-1)/2)
191                 move_left(current,position+1);
192             else combine(current,position);
193     }
194     void move_left(B_node<Record,order> *current, int position)
195     {
196         B_node<Record,order> *left_branch=current->branch[position-1],
197         *right_branch=current->branch[position];
198         left_branch->data[left_branch->count]=current->data[position-1];
199         left_branch->branch[++left_branch->count]=right_branch->branch[0];
200         current->data[position-1]=right_branch->data[0];
201         right_branch->count--;
202         for(int i=0; i<right_branch->count; i++)
203         {
204             right_branch->data[i]=right_branch->data[i+1];
205             right_branch->branch[i]=right_branch->branch[i+1];
206         }
207         right_branch->branch[right_branch->count]=
208             right_branch->branch[right_branch->count+1];
209     }
210     void move_right(B_node<Record,order> *current, int position)
211     {
212         B_node<Record,order> *right_branch=current->branch[position+1],
213         *left_branch=current->branch[position];
214         right_branch->branch[right_branch->count+1]=
215             right_branch->branch[right_branch->count];
216         for(int i=right_branch->count; i>0; i--)
217         {
218             right_branch->data[i]=right_branch->data[i-1];
219             right_branch->branch[i]=right_branch->branch[i-1];
220         }
221         right_branch->count++;
222         right_branch->data[0]=current->data[position];
223         right_branch->branch[0]=left_branch->branch[left_branch->count--];
224         current->data[position]=left_branch->data[left_branch->count];
225     }
226     void combine(B_node<Record,order> *current, int position)
227     {
228         int i;
229         B_node<Record,order> *left_branch=current->branch[position-1],
230             *right_branch=current->branch[position];
231         left_branch->data[left_branch->count]=current->data[position-1];
232         left_branch->branch[++left_branch->count]=right_branch->branch[0];
233         for(i=0; i<right_branch->count; i++)
234         {
235             left_branch->data[left_branch->count]=right_branch->data[i];
236             left_branch->branch[++left_branch->count]=right_branch->branch[i+1];
237         }
238         current->count--;
239         for(i=position-1; i<current->count; i++)
240         {
241             current->data[i]=current->data[i+1];
242             current->branch[i+1]=current->branch[i+2];
243         }
244         delete right_branch;
245     }
246     void copy_in_predecessor(B_node<Record,order> *current, int position)
247     {
248         B_node<Record,order> *leaf=current->branch[position];
249         while(leaf->branch[leaf->count] != NULL)
250             leaf=leaf->branch[leaf->count];
251         current->data[position]=leaf->data[leaf->count-1];
252     }
253     void remove_data(B_node<Record,order> *current, int position)
254     {
255         for(int i=position; i<current->count-1; i++)
256             current->data[i]=current->data[i+1];
257         current->count--;
258     }
259     Error_code recursive_remove(B_node<Record,order> *current, const Record &target)
260     {
261         Error_code result;
262         int position;
263         if(current==NULL) result=not_present;
264         else
265         {
266             if(search_node(current,target,position)==success)
267             {
268                 result=success;
269                 if(current->branch[position]!=NULL)
270                 {
271                     copy_in_predecessor(current,position);
272                     recursive_remove(current->branch[position],current->data[position]);
273                 }
274                 else
275                     remove_data(current,position);
276             }
277             else result=recursive_remove(current->branch[position],target);
278             if(current->branch[position]!=NULL)
279                 if(current->branch[position]->count < (order-1)/2)
280                     restore(current,position);
281         }
282         return result;
283     }
284 };

B_tree.h