学校数据结构的课程实验之一。
用到的数据结构：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 };
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 };
