上海网站公司,手机网站前端开发布局技巧,传媒公司名称,赣州新闻广播目录1. 需求分析2. 项目核心设计2.1 结点插入2.2 结点删除3 测试结果4 总结分析4.1 调试过程中的问题是如何解决的#xff0c;以及对设计与实现的回顾讨论和分析4.2 算法的时间和空间复杂度的分析#xff0c;以及进一步改进的设想4.3 本次实验的经验和体会5 完整代码(C)1. 需…
目录1. 需求分析2. 项目核心设计2.1 结点插入2.2 结点删除3 测试结果4 总结分析4.1 调试过程中的问题是如何解决的以及对设计与实现的回顾讨论和分析4.2 算法的时间和空间复杂度的分析以及进一步改进的设想4.3 本次实验的经验和体会5 完整代码(C)1. 需求分析
设计和实现一个简易的图书管理系统通过AVL树的插入、查找和删除等完成各功能每种书的登记内容至少包括书号、书名、著者、现存量和总库存量等五项书的数据用二叉排序树存储借阅登记信息采用顺序表—链表存储采编入库新购入一种书经分类和确定书号之后登记到图书帐目中去。如果这种书在帐中已有则只将该书的总库存量增加。图书按登记的先后顺序入库利用平衡二叉树实现动态查找表的插入书号为图书的关键字。初始时平衡二叉树为空树借阅如果一种书的现存量大于零则借出一本登记借阅者的图书证号和归还期限。借阅者借阅图书时先检查借阅者有无超期未归还图书如有则不能借阅如无利用平衡二叉树实现动态查找表的查找登记借阅信息。同一种书不能重复借阅归还注销对借阅者的登记改变该书的现存量如果借阅者归还所有的书则注销该借阅者的信息清除库存将该图书从平衡二叉树中删除同时确保二叉树平衡凹入表打印平衡二叉树同时展示结点平衡因子bf确保插入和删除操作的正确性。
2. 项目核心设计
本程序使用C语言编写与AVL树相关的内容故函数形参中未使用引用变量需修改的实参均以指针形式呈现。后因图书管理系统封装函数的需求更改.c文件为.cpp文件从而引入class。
项目核心部分为AVL树的生成和结点删除的同时如何保证树的平衡性下面对其实现原理进行解释。基于此构建图书管理系统系统逻辑和具体功能见MindMap。 2.1 结点插入
对结点插入的解释以向其根结点左侧插入为例右插类似不做赘述。 若插入结点的关键词小于根结点的关键词则插入根结点的左孩子。插入后向根结点回溯时返回一个taller告知根结点因插入新结点而高度是否发生改变。此时分三种情况进行讨论
若根结点原本右高RH则因新结点的插入而使根结点等高EHtallerFALSE告知根结点未因插入新结点而高度发生改变若根结点原本等高EH则因新结点的插入而使根结点左高LHtallerTRUE告知根结点因插入新结点高度增高若根结点原本左高LH向左插入新结点后根结点失衡故因左调平根结点。 else if(LT(elem.number,(*T)-data.number)) {//insert its left child treeif(!InsertAVLTree(((*T)-lchild),taller,elem)) return ERROR;if(!*taller) return OK;switch((*T)-bf) { //update the BF of the nodecase LH://adjust to make it balancedL_Balance(T);*tallerFALSE; break;case EH: (*T)-bfLH; *tallerTRUE; break;case RH: (*T)-bfEH; *tallerFALSE; break;}//switch((*T)-bf)}左调平根结点时根据根结点左孩子的平衡因子判断是LL型还是LR型采用不同的调平方法。无论何种调平方法都应遵循以下两原则
确保二叉树性质不变即中序遍历结果不变使最小失衡子树的高度降低。
若左孩子的平衡因子为左高LH说明为LL型修改根结点和其左孩子的平衡因子EH向左旋转根结点。若左孩子的平衡因子为右高RH说明为LR型此时根据其左孩子的右孩子的平衡因子修改结点平衡因子再分三种情况进行讨论
若其左的右孩子为左高LH则左和左的右孩子BFEH根结点BFRH若其左的右孩子为等高EH则左孩子和根结点BFEH。左的右孩子已为EH若其左的右孩子为右高RH则根结点和左的右孩子BFEH左孩子BFLH。
void LibManage::L_Balance(AVLTree *t){//adjust the root to make left tree balancedTNode *lc(*t)-lchild,*rd;switch(lc-bf){ //check condition: LL or LR, through BF of roots lchildcase EH: //a case when deleting the node(*t)-bfLH; lc-bfRH;R_Rotate(t);break;case LH: //LL(*t)-bflc-bfEH; //modify BFR_Rotate(t); //R rotate root nodebreak;case RH: //LRrdlc-rchild;switch(rd-bf){ //modify BF according to different BF conditionscase LH: lc-bfrd-bfEH; (*t)-bfRH; break;case EH: lc-bf(*t)-bfEH; break;case RH: rd-bf(*t)-bfEH; lc-bfLH; break;}//switch(rd-bf)L_Rotate(((*t)-lchild)); //part Left rotation, firstlyR_Rotate(t); //root Right rotation, thenbreak;}//switch(lc-bf)
}修正平衡因子后对失衡子树进行旋转。先对失衡子树根结点的左孩子进行局部左旋转再对根结点进行整体右旋。至此结点左插调平完成。以下为左调平操作示意图解。 2.2 结点删除
AVL树结点的删除操作同二叉搜索树结点删除相同但删除结点后需要调整使AVL树重新平衡。根据所删结点的双亲和孩子情况分三种情况进行讨论
若所删结点为叶子结点无孩子直接删除之。若其无双亲即为AVL树的根结点置AVL树根root为空NULL若所删结点只有一孩子令其双亲结点连接其孩子至于是双亲的左还是右连接之只需判断双亲和孩子的关键词大小若双亲孩子则双亲左连之反之则双亲右连之。若无双亲可置树根root为所删结点的孩子若所删结点两孩子均存在则可通过寻找其在中序遍历下的前驱或后继来实现删除操作。为同程序一致这里以寻找前驱为例。进入所删结点的左孩子向其右方通过遍历寻至其最右方的结点姑且称作待删结点的相邻点将待删结点的值替换为相邻点的值。再进入待删结点的左子树中递归删除相邻点。
else if(EQ(bknum,(*curT)-data.number)) {//find the node, and delete itif(!((*curT)-lchild)) {//if(the node has no left child or has neither left nor right one)if(!preT) *curT(*curT)-rchild;//if(the node has no parent)else if(LT(bknum,preT-data.number)) preT-lchild(*curT)-rchild;//check the current node is its parents left child or its right oneelse preT-rchild(*curT)-rchild;*shorterTRUE;}//if(!((*curT)-lchild))else if(!((*curT)-rchild)) {//if(the node has no right child but has left one)if(!preT) *curT(*curT)-lchild;//if(the node has no parent)else if(LT(bknum,preT-data.number)) preT-lchild(*curT)-lchild;//check the current node is its parents left child or its right oneelse preT-rchild(*curT)-lchild;*shorterTRUE;}//else if(!((*curT)-rchild))else {//if(the node has both right and left child)TNode *tempT(*curT)-lchild; //enter curTs left childwhile(tempT-rchild) //find curNodes precursor in inorder traversetempTtempT-rchild;BookCpy(((*curT)-data),tempT-data); //assign the precursors data to the node that needs to be deletedDeleteAVLTree(((*curT)-lchild),NULL,shorter, tempT-data.number); //delete the precursor of the deleted elem in curTs left child接下来对删除结点后的调平工作进行解释同样以删除根结点左子树中的结点为例右子树中删除操作类似不做赘述。
若所删结点的关键词根结点的关键词则进入根结点左子树中进行删除操作。删除后向根结点回溯时返回一个shorter告知根结点因删除结点而高度是否发生改变。此时分三种情况进行讨论
根结点原本左高LH删除后根结点等高EHshorterTRUE根结点原本等高EH删除后根结点右高RHshorterFALSE根结点原本右高RH删除后根结点失衡应当对其进行右调平R_Balance()操作。
调平前需根据根结点的右孩子的平衡因子判断调平后失衡子树shorter情况如何此时分三种情况进行讨论
根的右孩子BFLH调平后shorterTRUE根的右孩子BFEH调平后shorterFALSE根的右孩子BFRH调平后shorterTRUE。也可与情况1归并
else if(LT(bknum,(*curT)-data.number)) {//if the keynum is less than the curTs numberif(!DeleteAVLTree(((*curT)-lchild),*curT,shorter,bknum)) return ERROR;if(!*shorter) return OK;switch((*curT)-bf) {case LH: (*curT)-bfEH; *shorterTRUE; break;case EH: (*curT)-bfRH; *shorterFALSE; break;case RH://another 3 conditions need to be considered, according to curTs right child BFswitch((*curT)-rchild-bf) {case LH: *shorterTRUE; break;case EH: *shorterFALSE; break;case RH: *shorterTRUE; break;}//switch((*curT)-rchild-bf)R_Balance(curT);}//switch((*curT)-bf)}//else if(LT(bknum,(*curT)-data.number))判断回溯的shorter的结果后开始右调平。右调平操作与结点插入时的右调平基本无异但需在“通过根结点右孩子BF值判断是RR型还是RL型失衡”时增加一种EH的情况。因为在插入时只考虑了因插入才会产生的LH和RH情况未将删除时所会遇到的EH纳入其中。当BFEH时先更新各结点的平衡因子根结点的BFRH根结点右孩子的BFLH再根结点左旋。同理左平衡操作时也需补充“EH条件”。
void LibManage::R_Balance(AVLTree *t){//adjust the root to make right tree balancedTNode *rc(*t)-rchild,*ld;switch(rc-bf){ //check condition: RL or RR, through BF of roots rchildcase EH: //a case when deleting the node(*t)-bfRH; rc-bfLH;L_Rotate(t);break;//......以下为右调平操作图解。 3 测试结果 //为模拟方便起见添加初始图书、阅读者和阅读者的借阅数据 //book{number,name,author,stock,total} Book book1{“01”,“PromisedLand”,“Obama”,6,8}; Book book2{“02”,“Humans”,“Stanton”,4,5}; Book book3{“03”,“Becoming”,“Michelle”,0,3}; Book book4{“04”,“DeepEnd”,“Kinney”,0,6}; InsertAVLTree(tree,taller,book1); InsertAVLTree(tree,taller,book2); InsertAVLTree(tree,taller,book3); InsertAVLTree(tree,taller,book4); //reader{code,name,telephone,firstarc} Reader reader1{1,“Sylvan”,“95566”,NULL}; Reader reader2{2,“JIXIANG”,“10086”,NULL}; AddReader(reader_list,reader1); AddReader(reader_list,reader2); //reader{booknumber,bookname,return date,*next} ArcBox arcbox1{“01”,“PromisedLand”,20251211,NULL}; ArcBox arcbox2{“02”,“Humans”,20300201,NULL}; AddReaderBook(reader_list.readers[0],arcbox1); AddReaderBook(reader_list.readers[0],arcbox2); AddReaderBook(reader_list.readers[1],arcbox1); (以下内容均来自终端) //启动图书管理系统设置系统时间 Launch Library Management System Successfully! Set current time:20201120 successfully! //菜单界面待用户输入指令
* * * MENU * * *
(1). Add books
(2). Lend books
(3). Return books
(4). Erase books
(5). Print All Books
(6). Print All Readers
(7). *(Testing MODE)
(0). [ E X I T ]
* * * * * * * * *
Menu-Option:
//功能一、采编入库
Menu-Option: 1
- - - - Add Book - - - -
Book Number: ISBN 01
Increment: 2
Find the BOOK...
Would you like to increase it? (y/n)...
y
Original stock: 6
Original total amount: 8
- - - - Book Info - - - -
Name: PromisedLand
Author: Obama
Number: ISBN 01
Total: 10
Stock: 8
- - - - - - - - - - - - -
Increase successfully!
Menu-Option: 1
- - - - Add Book - - - -
Book Number: ISBN 05
Increment: 3
ERROR: Cant find BOOK: ISBN 05 Would you like to create a new item? (y/n)...
y
Number: ISBN 05
Stock/Total: 3
Name: Sherlock
Author: Arthur
- - - - Book Info - - - -
Name: Sherlock
Author: Arthur
Number: ISBN 05
Total: 3
Stock: 3
- - - - - - - - - - - - -
Add new book successfully!
//功能二、借阅
Menu-Option: 2
- - - - Lend Book - - - -
Reader Code: 01
- - - - Reader Info - - - -
Name: Sylvan
Code: 00001
Tele: 95566
Borrowed books:
Humans | ISBN 02 | Deadline:20300201([Normal])
PromisedLand | ISBN 01 | Deadline:20251211([Normal])
- - - - - - - - - - - - -
Book Number to lend: ISBN 02
No borrow permission: The reader has borrowed a same book Humans.
//……相同操作省略
Book Number to lend: ISBN 03
ERROR: Book Stock of Becoming is not enough...
Menu-Option: 2
- - - - Lend Book - - - -
Reader Code: 02
- - - - Reader Info - - - -
Name: JIXIANG
Code: 00002
Tele: 10086
Borrowed books:
PromisedLand | ISBN 01 | Deadline:20251211([Normal])
- - - - - - - - - - - - -
Book Number to lend: ISBN 02
Return Date(e.g.20201230): 20191230
Lend Book Successfully!
Menu-Option: 2
- - - - Lend Book - - - -
Reader Code: 02
- - - - Reader Info - - - -
Name: JIXIANG
Code: 00002
Tele: 10086
Borrowed books:
Humans | ISBN 02 | Deadline:20191230(![Overdue]!)
PromisedLand | ISBN 01 | Deadline:20251211([Normal])
- - - - - - - - - - - - -
No borrow permission: The reader has a book Humans needs to be returned before 20191230
Menu-Option: 2
- - - - Lend Book - - - -
Reader Code: 05
ERROR: Cant find reader 00005...
Would you like to create one? (y/n)...
y
Code: 00005
Name: Benedict
Tele: 197362
- - - - Reader Info - - - -
Name: Benedict
Code: 00005
Tele: 197362
Borrowed books: (Empty)
- - - - - - - - - - - - -
Add reader successfully!
Book Number to lend: ISBN 01
Return Date(e.g.20201230): 20201231
Lend Book Successfully!
//功能三、还书
Menu-Option: 3
- - - - Return Book - - - -
Reader Code: 01
- - - - Reader Info - - - -
Name: Sylvan
Code: 00001
Tele: 95566
Borrowed books:
Humans | ISBN 02 | Deadline:20300201([Normal])
PromisedLand | ISBN 01 | Deadline:20251211([Normal])
- - - - - - - - - - - - -
Book Number to return: ISBN 02
Return Successfully!
Menu-Option: 3
- - - - Return Book - - - -
Reader Code: 01
- - - - Reader Info - - - -
Name: Sylvan
Code: 00001
Tele: 95566
Borrowed books:
PromisedLand | ISBN 01 | Deadline:20251211([Normal])
- - - - - - - - - - - - -
Book Number to return: ISBN 01
Warning: Reader Sylvan has returned all books, now erase his or her info from the memory...
Erased successfully!
Return Successfully!
Menu-Option: 6
- - - - Reader Info - - - -
Name: JIXIANG
Code: 00002
Tele: 10086
Borrowed books:
PromisedLand | ISBN 01 | Deadline:20251211([Normal])
- - - - - - - - - - - - -
//功能四、清除库存
Menu-Option: 4
- - - - Erase Book - - - -
Book Number to erase: ISBN 01
Delete book successfully!
Menu-Option: 5
- - - - Book Info - - - -
Name: Becoming
Author: Michelle
Number: ISBN 03
Total: 3
Stock: 0
- - - - Book Info - - - -
Name: Humans
Author: Stanton
Number: ISBN 02
Total: 5
Stock: 4
- - - - Book Info - - - -
Name: DeepEnd
Author: Kinney
Number: ISBN 04
Total: 6
Stock: 0
- - - - - - - - - - - - -
//功能五、展示所有图书
//功能六、展示所有借阅者
//功能七、测试模式便捷地测试AVL树的插入与删除。4 总结分析
4.1 调试过程中的问题是如何解决的以及对设计与实现的回顾讨论和分析
平衡二叉排序树(Balanced Binary Sort Tree)又称AVL树是一种时间复杂度较低的理想的动态查找表。通过在树结点TNode中增设整型变量bf即平衡因子balance factor来判定结点是否平衡。Bf为该结点左子树高与右子树高的差值当其绝对值超过1以后结点失衡需要对其进行调平操作。
写程序过程中遇到逻辑问题后通过一步步debug发现问题解决问题。
4.2 算法的时间和空间复杂度的分析以及进一步改进的设想
经分析平衡二叉树的查找、插入和删除其时间复杂度均为1 ◯(logn).\bigcirc \left ( \log n\right ). ◯(logn). 是一种理想的动态查找表。
4.3 本次实验的经验和体会
通过使用C语言编写平衡二叉树插入和删除部分大量使用指针变量深入理解了指针的含义和用法。函数中重复使用回溯的方法进行二叉树平衡加强了对算法逻辑对掌握。
使用C编写图书管理部分学习和培养了考虑项目要全面的能力。
语法错误越来越少而真正困难的逻辑部分问题增多。
在编写平衡二叉树插入和删除时调试过程中遇到许多问题如旋转错误、结点平衡因子错误等等。Edsger W. Dijkstra曾说过 “有效的程序员不应该浪费很多时间用于程序调试他们应该一开始就不要把故障引入。” 2 表明在写程序前就应当理清逻辑和考虑所有情况因此后续还需继续培养编程的逻辑性和严谨性。
5 完整代码(C)
#includestdio.h
#includestdlib.h
#includestring.h
#includetime.h/* status macro definition */
#define OK 1
#define ERROR 0
#define OVER_FLOW -2/* memory length macro definition */
#define MAXNAMELEN 15
#define MAXBOOKNUMBERLEN 20
#define MAXREADERNUM 20 //the max amount of all readers
#define MAXREADERCODEDIGIT 5 //max reader code digits
#define INDENTATION 0 //for printing the BiTree/* some macros related to AVLTree */
#define EQ(a,b) (!strcmp((a),(b)))
#define LT(a,b) (strcmp((a),(b))0)
#define LH 1
#define EH 0
#define RH -1typedef int Status;
typedef enum {FALSE,TRUE} boolean;
typedef char *KeyType;
typedef char NameType[MAXNAMELEN];
typedef char *BookNum,BookNumType[MAXBOOKNUMBERLEN];
typedef char TeleType[111]; //telephone: 11digits
typedef unsigned int DateType; //return date
//typedef Book DataType; //data type in TNodetypedef struct{BookNumType number; //no prefix ISBNNameType name;NameType author;int stock; //current amount of the bookint total; //total amount of the book
}Book,DataType;typedef struct TNode{DataType data;int bf; //balance factorstruct TNode *lchild,*rchild;
}TNode,*AVLTree;typedef struct ArcBox{BookNumType bknum;NameType bknam;DateType return_date; //e.g. 20010205struct ArcBox *next;
}ArcBox;typedef struct{int code;NameType name;TeleType tele; //telephoneArcBox *first_arc;
}Reader;typedef struct{Reader *readers;int length,size;
}AdjList;class LibManage{
public:AVLTree tree;AdjList reader_list;DateType current_date;LibManage();~LibManage() {DestoryTree(tree);}void Menu();void AddBook();void LendBook();void ReturnBook();void EraseBook();void OutputBooks();void OutputReaders();void TestMode();
private:void gettime();void PrintBook(Book b);void PrintBiTree_Simple(AVLTree T,int indent);void PrintBiTree_Detail(AVLTree T);void BookCpy(Book *a,Book b);void L_Rotate(AVLTree *t);void R_Rotate(AVLTree *t);void L_Balance(AVLTree *t);void R_Balance(AVLTree *t);TNode* SearchAVLTree(AVLTree T,BookNum bn);Status InsertAVLTree(AVLTree *T,boolean *taller,DataType elem);Status DeleteAVLTree(AVLTree *curT,AVLTree preT,boolean *shorter,KeyType bknum);Status InitAdjList(AdjList list);Status AddReader(AdjList list,const Reader r);Status AddReaderBook(Reader r,const ArcBox ab);Status SearchReader(AdjList list,int code);Status DeleteReader(AdjList list,int code);Status CheckBorrowPermission(Reader r,BookNum bknumNULL);ArcBox* SearchBorrowedBook(Reader r,KeyType bknum,ArcBox* prep);void ReaderCpy(Reader r1,const Reader r2);void PrintReader(const Reader r);void PrintBorrowedBooks(Reader r);void DestoryTree(AVLTree T);
};void LibManage::gettime(){//get system time and convert it to unsigned inttime_t rawtime;struct tm *ptminfo;time(rawtime); //get time raw infoptminfolocaltime(rawtime); //convert raw time info to processed and readable time infocurrent_date((ptminfo-tm_year)1900)*10000(ptminfo-tm_mon)*100(ptminfo-tm_mday);printf(Set current time:%u successfully! \n,current_date);
}LibManage::LibManage() {treeNULL; //initialize treeInitAdjList(reader_list); //initialize AdjListprintf(Launch Library Management System Successfully! \n);gettime();/* Simulate a library, so add some items first *///book{number,name,author,stock,total}boolean tallerFALSE;Book book1{01,PromisedLand,Obama,6,8};Book book2{02,Humans,Stanton,4,5};Book book3{03,Becoming,Michelle,0,3};Book book4{04,DeepEnd,Kinney,0,6};InsertAVLTree(tree,taller,book1);InsertAVLTree(tree,taller,book2);InsertAVLTree(tree,taller,book3);InsertAVLTree(tree,taller,book4);//reader{code,name,telephone,firstarc}Reader reader1{1,Sylvan,95566,NULL};Reader reader2{2,JIXIANG,10086,NULL};AddReader(reader_list,reader1);AddReader(reader_list,reader2);//reader{booknumber,bookname,return date,*next}ArcBox arcbox1{01,PromisedLand,20251211,NULL};ArcBox arcbox2{02,Humans,20300201,NULL};AddReaderBook(reader_list.readers[0],arcbox1);AddReaderBook(reader_list.readers[0],arcbox2);AddReaderBook(reader_list.readers[1],arcbox1);
}void LibManage::DestoryTree(AVLTree T){//free the memory of the tree, using post-order traverse to guarantee that the nodes parent wont get lostif(!T) return;DestoryTree(T-lchild);DestoryTree(T-rchild);free(T); TNULL;
}//the following function is related to AVLTreevoid LibManage::L_Rotate(AVLTree *t){//left rotate root node, and update the rootTNode *rc(*t)-rchild;(*t)-rchildrc-lchild;rc-lchild*t;(*t)rc;
}
void LibManage::R_Rotate(AVLTree *t){//right rotate root node, and update the rootTNode *lc(*t)-lchild;(*t)-lchildlc-rchild;lc-rchild*t;(*t)lc;
}
void LibManage::L_Balance(AVLTree *t){//adjust the root to make left tree balancedTNode *lc(*t)-lchild,*rd;switch(lc-bf){ //check condition: LL or LR, through BF of roots lchildcase EH: //a case when deleting the node(*t)-bfLH; lc-bfRH;R_Rotate(t);break;case LH: //LL(*t)-bflc-bfEH; //modify BFR_Rotate(t); //R rotate root nodebreak;case RH: //LRrdlc-rchild;switch(rd-bf){ //modify BF according to different BF conditionscase LH: lc-bfrd-bfEH; (*t)-bfRH; break;case EH: lc-bf(*t)-bfEH; break;case RH: rd-bf(*t)-bfEH; lc-bfLH; break;}//switch(rd-bf)L_Rotate(((*t)-lchild)); //part Left rotation, firstlyR_Rotate(t); //root Right rotation, thenbreak;}//switch(lc-bf)
}
void LibManage::R_Balance(AVLTree *t){//adjust the root to make right tree balancedTNode *rc(*t)-rchild,*ld;switch(rc-bf){ //check condition: RL or RR, through BF of roots rchildcase EH: //a case when deleting the node(*t)-bfRH; rc-bfLH;L_Rotate(t);break;case RH: //RR(*t)-bfrc-bfEH; //modify BFL_Rotate(t); //L rotate root nodebreak;case LH: //RLldrc-lchild;switch(ld-bf){ //modify BF according to different BF conditionscase LH: (*t)-bfrc-bfEH; ld-bfRH; break;case EH: rc-bf(*t)-bfEH; break;case RH: ld-bfrc-bfEH; (*t)-bfLH; break;}//switch(rd-bf)R_Rotate(((*t)-rchild)); //part Right rotation, firstlyL_Rotate(t); //root Left rotation, thenbreak;}//switch(lc-bf)
}TNode* LibManage::SearchAVLTree(AVLTree T,BookNum bn){/* if the booknum can be found in AVLTree, then return its address, else return NULL */if(!T) return NULL;if(EQ(bn,T-data.number)) return T;if(LT(bn,T-data.number)) return SearchAVLTree(T-lchild,bn);return SearchAVLTree(T-rchild,bn);
}Status LibManage::InsertAVLTree(AVLTree *T,boolean *taller,DataType elem){/* insert an elem to AVLTree, and adjust the tree to keep its balance. If elem has existed, then return ERROR, else return OK *//* parameter taller means that after inserting the elem, the tree is taller or not. */if(!*T) { //create a new node*T(TNode*)malloc(sizeof(TNode));if(!*T) exit(OVER_FLOW);BookCpy(((*T)-data),elem);(*T)-bfEH;(*T)-lchild(*T)-rchildNULL;*tallerTRUE;}else if(EQ(elem.number,(*T)-data.number)) {//if the node has already existedPrintBook((*T)-data);printf(ERROR: book %s has already been in the AVL Tree. \n,elem.name);*tallerFALSE;return ERROR;}else if(LT(elem.number,(*T)-data.number)) {//insert its left child treeif(!InsertAVLTree(((*T)-lchild),taller,elem)) return ERROR;if(!*taller) return OK;switch((*T)-bf) { //update the BF of the nodecase LH://adjust to make it balancedL_Balance(T);*tallerFALSE; break;case EH: (*T)-bfLH; *tallerTRUE; break;case RH: (*T)-bfEH; *tallerFALSE; break;}//switch((*T)-bf)}else {//insert its right child treeif(!InsertAVLTree(((*T)-rchild),taller,elem)) return ERROR;if(!*taller) return OK;switch((*T)-bf) { //update the BF of the nodecase LH: (*T)-bfEH; *tallerFALSE; break;case EH: (*T)-bfRH; *tallerTRUE; break;case RH://adjust to make it balancedR_Balance(T);*tallerFALSE; break;}//switch((*T)-bf)}return OK;
}Status LibManage::DeleteAVLTree(AVLTree *curT,AVLTree preT,boolean *shorter,KeyType bknum){/* delete a node in AVLTree according to its book number, and adjust the tree to keep its balance. If elem has existed, then return OK, else return ERROR *///©SylvanDing/* parameter shorter means that after deleting the node, the tree is shorter or not. */if(!*curT) {//if the node doesnt existprintf(ERROR: Cant find BOOK: ISBN %s \n,bknum);*shorterFALSE;return ERROR;}//if(!*curT)else if(EQ(bknum,(*curT)-data.number)) {//find the node, and delete itif(!((*curT)-lchild)) {//if(the node has no left child or has neither left nor right one)if(!preT) *curT(*curT)-rchild;//if(the node has no parent)else if(LT(bknum,preT-data.number)) preT-lchild(*curT)-rchild;//check the current node is its parents left child or its right oneelse preT-rchild(*curT)-rchild;*shorterTRUE;}//if(!((*curT)-lchild))else if(!((*curT)-rchild)) {//if(the node has no right child but has left one)if(!preT) *curT(*curT)-lchild;//if(the node has no parent)else if(LT(bknum,preT-data.number)) preT-lchild(*curT)-lchild;//check the current node is its parents left child or its right oneelse preT-rchild(*curT)-lchild;*shorterTRUE;}//else if(!((*curT)-rchild))else {//if(the node has both right and left child)TNode *tempT(*curT)-lchild; //enter curTs left childwhile(tempT-rchild) //find curNodes precursor in inorder traversetempTtempT-rchild;BookCpy(((*curT)-data),tempT-data); //assign the precursors data to the node that needs to be deletedDeleteAVLTree(((*curT)-lchild),NULL,shorter, tempT-data.number); //delete the precursor of the deleted elem in curTs left childif(!*shorter) return OK;switch((*curT)-bf) {case LH: (*curT)-bfEH; *shorterTRUE; break;case EH: (*curT)-bfRH; *shorterFALSE; break;case RH://another 3 conditions need to be considered, according to curTs right child BFswitch((*curT)-rchild-bf) {case LH: *shorterTRUE; break;case EH: *shorterFALSE; break;case RH: *shorterTRUE; break;}//switch((*curT)-rchild-bf)R_Balance(curT);}//switch((*curT)-bf)}}//else if(EQ(bknum,(*curT)-data.number))else if(LT(bknum,(*curT)-data.number)) {//if the keynum is less than the curTs numberif(!DeleteAVLTree(((*curT)-lchild),*curT,shorter,bknum)) return ERROR;if(!*shorter) return OK;switch((*curT)-bf) {case LH: (*curT)-bfEH; *shorterTRUE; break;case EH: (*curT)-bfRH; *shorterFALSE; break;case RH://another 3 conditions need to be considered, according to curTs right child BFswitch((*curT)-rchild-bf) {case LH: *shorterTRUE; break;case EH: *shorterFALSE; break;case RH: *shorterTRUE; break;}//switch((*curT)-rchild-bf)R_Balance(curT);}//switch((*curT)-bf)}//else if(LT(bknum,(*curT)-data.number))else {//if the keynum is larger than the curTs number, enter its right childif(!DeleteAVLTree(((*curT)-rchild),*curT,shorter,bknum)) return ERROR;if(!*shorter) return OK;switch((*curT)-bf) {case LH://another 3 conditions need to be considered, according to curTs left child BFswitch((*curT)-lchild-bf) {case LH: *shorterTRUE; break;case EH: *shorterFALSE; break;case RH: *shorterTRUE; break;}//switch((*curT)-rchild-bf)L_Balance(curT);case EH: (*curT)-bfLH; *shorterFALSE; break;case RH: (*curT)-bfEH; *shorterTRUE; break;}//switch((*curT)-bf)}//elsereturn OK;
}void LibManage::TestMode(){//this mode is for testing AVLTrees insertion and deletion quickly and easilyBook bk{,,,0,0};AVLTree testTNULL; boolean flag;printf(- - - Testing Mode - - -\n);printf(//This mode allows you to test AVLTrees insertion and deletion quickly and easily. Whenever you insert or delete an item, it will print the AVLTree: KeyValue(BalanceFactor) \n//Have created a new Empty AVLTree for testing... \n//Input numbers(like 01,21,36...) to insert it, input end to stop inserting. \n);//©SylvanDingdo{flagFALSE;scanf(%s,bk.number);getchar();if(EQ(bk.number,end)) break;InsertAVLTree(testT,flag,bk);printf(* Tree Print * \n);PrintBiTree_Simple(testT,INDENTATION);}while(1);printf(//End inserting, and then you can input the item you wanna delete, input quit to exit testing mode... \n);do{flagFALSE;scanf(%s,bk.number);getchar();if(EQ(bk.number,quit)) break;DeleteAVLTree(testT,NULL,flag,bk.number);printf(* Tree Print * \n);PrintBiTree_Simple(testT,INDENTATION);}while(1);printf(//Exit TESTING MODE... \n);
}//the following function is about Library Managementvoid LibManage::Menu(){printf(* * * MENU * * *\n);printf((1). Add books\n);printf((2). Lend books\n);printf((3). Return books\n);printf((4). Erase books\n);printf((5). Print All Books\n);printf((6). Print All Readers\n);printf((7). *(Testing MODE)\n);printf((0). [ E X I T ]\n);printf(* * * * * * * * *\n);
}void LibManage::BookCpy(Book *a,Book b){//copy bs info and assign it to astrcpy(a-number,b.number);strcpy(a-name,b.name);strcpy(a-author,b.author);a-stockb.stock;a-totalb.total;
}void LibManage::PrintBook(Book b){printf(- - - - Book Info - - - -\n);printf(Name: %s\n,b.name);printf(Author: %s\n,b.author);printf(Number: ISBN %s\n,b.number);printf(Total: %d\n,b.total);printf(Stock: %d\n,b.stock);printf(- - - - - - - - - - - - -\n);
}void LibManage::PrintBiTree_Simple(AVLTree T,int indent){if(!T) return;printf(%*s%s(%d)\n,indent,,T-data.number,T-bf);PrintBiTree_Simple(T-lchild,indent1);PrintBiTree_Simple(T-rchild,indent1);
}void LibManage::PrintBiTree_Detail(AVLTree T){if(!T) return;PrintBook(T-data);PrintBiTree_Detail(T-lchild);PrintBiTree_Detail(T-rchild);
}void LibManage::AddBook(){//to add a new book when bknum-related book doesnt exist in AVLTree, or increase its original amountAVLTree *Ttree;TNode *nodeNULL; char flag;BookNumType bknum; int amount;printf(- - - - Add Book - - - -\n);printf(Book Number: ISBN );scanf(%s,bknum);printf(Increment: );scanf(%d,amount);getchar();if(!(nodeSearchAVLTree(*T,bknum))) {boolean tallerFALSE;Book new_book; NameType bk_name,aut_name;printf(ERROR: Cant find BOOK: ISBN %s \n Would you like to create a new item? (y/n)...\n,bknum);scanf(%c,flag);switch(flag){case n:case N: return; break;case y:case Y:printf(Number: ISBN %s\n,bknum);printf(Stock/Total: %d\n,amount);printf(Name: );scanf(%s,bk_name);printf(Author: );scanf(%s,aut_name);strcpy(new_book.number,bknum);strcpy(new_book.name,bk_name);strcpy(new_book.author,aut_name);new_book.stocknew_book.totalamount;if(!InsertAVLTree(T,taller,new_book)) return;PrintBook(new_book);printf(Add new book successfully! \n);break;default: printf(Error: Wrong command, try again...\n);}//switch(flag)}//if(!(nodeSearchAVLTree(*T,bknum)))else {printf(Find the BOOK...\nWould you like to increase it? (y/n)...\n);scanf(%c,flag);switch(flag){case n:case N: return; break;case y:case Y:printf(Original stock: %d \nOriginal total amount: %d \n,node-data.stock,node-data.total);node-data.stockamount;node-data.totalamount;PrintBook(node-data);printf(Increase successfully! \n);break;default: printf(Error: Wrong command, try again...\n);}//switch(flag)}//else
}void LibManage::
LendBook(){//to lend booksint code,index; char flag;printf(- - - - Lend Book - - - -\n);printf(Reader Code: );scanf(%d,code);getchar();if((indexSearchReader(reader_list,code))0) {indexreader_list.length;Reader newreader; newreader.first_arcNULL;printf(ERROR: Cant find reader %0*d...\nWould you like to create one? (y/n)...\n,MAXREADERCODEDIGIT,code);scanf(%c,flag);switch(flag){case n:case N: return; break;case y:case Y:printf(Code: %0*d \n,MAXREADERCODEDIGIT,code);newreader.codecode;printf(Name: );scanf(%s,newreader.name);printf(Tele: );scanf(%s,newreader.tele);if(!AddReader(reader_list,newreader)) return;PrintReader(reader_list.readers[reader_list.length-1]);printf(Add reader successfully! \n);break;default: printf(Error: Wrong command, try again...\n); return;}//switch(flag)}//if(index0)else {PrintReader(reader_list.readers[index]);if(!CheckBorrowPermission(reader_list.readers[index])) return;}//if(index0)BookNumType bknum; TNode *tptr;printf(Book Number to lend: ISBN );scanf(%s,bknum);if(!CheckBorrowPermission(reader_list.readers[index],bknum)) return;if(!(tptrSearchAVLTree(tree,bknum)))printf(ERROR: Cant find book: %s in Library System... \n,bknum);else if(tptr-data.stock0)printf(ERROR: Book Stock of %s is not enough... \n,tptr-data.name);else {ArcBox *new_arcbox(ArcBox*)malloc(sizeof(ArcBox));if(!new_arcbox) exit(OVER_FLOW);--tptr-data.stock;printf(Return Date(e.g.20201230): );scanf(%u,(new_arcbox-return_date));strcpy(new_arcbox-bknum,bknum);strcpy(new_arcbox-bknam,tptr-data.name);new_arcbox-nextreader_list.readers[index].first_arc;reader_list.readers[index].first_arcnew_arcbox;printf(Lend Book Successfully! \n);}
}void LibManage::ReturnBook(){//to return booksint code,index; TNode *tptr;BookNumType bknum; ArcBox *abptr,*pre_abptr;printf(- - - - Return Book - - - -\n);printf(Reader Code: );scanf(%d,code);getchar();if((indexSearchReader(reader_list,code))0) {printf(ERROR: Cant find reader %0*d...\n,MAXREADERCODEDIGIT,code);return;}PrintReader(reader_list.readers[index]);printf(Book Number to return: ISBN );scanf(%s,bknum);if(!(abptrSearchBorrowedBook(reader_list.readers[index],bknum,pre_abptr))) {printf(ERROR: No lended book: %s...\n,bknum);return;}if(!pre_abptr)reader_list.readers[index].first_arcabptr-next;elsepre_abptr-nextabptr-next;free(abptr);if(!reader_list.readers[index].first_arc) {printf(Warning: Reader %s has returned all books, now erase his or her info from the memory... \n,reader_list.readers[index].name);DeleteReader(reader_list,index);printf(Erased successfully! \n);}if((tptrSearchAVLTree(tree,bknum)))tptr-data.stock;printf(Return Successfully! \n);
}void LibManage::EraseBook(){//to erase bookBookNumType bknum; boolean shorter;printf(- - - - Erase Book - - - -\n);printf(Book Number to erase: ISBN );scanf(%s,bknum);getchar();if(DeleteAVLTree(tree,NULL,shorter,bknum))printf(Delete book successfully! \n);
}void LibManage::OutputBooks(){//in-order traverse the AVLTreeif(!tree){printf(No book... \n);return;}PrintBiTree_Detail(tree);
}void LibManage::OutputReaders(){if(reader_list.length0) {printf(No reader... \n);return;}for(int i0;ireader_list.length;i)PrintReader(reader_list.readers[i]);
}//the following function is about Readers ManagementStatus LibManage::InitAdjList(AdjList list){//initialize reader adjacency listif(!(list.readers(Reader*)malloc(MAXREADERNUM*sizeof(Reader)))) exit(OVER_FLOW);list.length0; list.sizeMAXREADERNUM;return OK;
}Status LibManage::AddReader(AdjList list, const Reader newr){//add a new reader to reader listif(list.lengthlist.size) {printf(ERROR: System unable to hold more readers... \n);return ERROR;}ReaderCpy(list.readers[list.length],newr);return OK;
}Status LibManage::AddReaderBook(Reader r,const ArcBox ab){//for stimulating a whole library management//no real functionArcBox *abptr(ArcBox*)malloc(sizeof(ArcBox));if(!abptr) exit(OVER_FLOW);strcpy(abptr-bknum,ab.bknum);strcpy(abptr-bknam,ab.bknam);abptr-return_dateab.return_date;abptr-nextr.first_arc;r.first_arcabptr;return OK;
}Status LibManage::SearchReader(AdjList list,int code){//if code exists, then return its index, else return -1int index0;while(indexlist.lengthcode!list.readers[index].code) index;if(indexlist.length) return index;else return -1;
}Status LibManage::DeleteReader(AdjList list,int index){while(indexlist.length) {ReaderCpy(list.readers[index],list.readers[index1]);index;}--list.length;return OK;
}Status LibManage::CheckBorrowPermission(Reader r,BookNum bknum){//if the second parameter bknumNULL, only check whether the borrower has overdue unreturned book, if he does, return 0, else return 1//if the bknum!NULL, then check if there has any same book that he has already borrowed. if he does, return 0, else return 1ArcBox *pr.first_arc;if(!bknum) {while(pp-return_datecurrent_date)pp-next;if(p) {printf(No borrow permission: The reader has a book %s needs to be returned before %u \n,p-bknam,p-return_date);return 0;}else return 1;}//if(!bknum)else {while(p!EQ(bknum,p-bknum))pp-next;if(p) {printf(No borrow permission: The reader has borrowed a same book %s. \n,p-bknam);return 0;}else return 1;}//else
}ArcBox* LibManage::SearchBorrowedBook(Reader r,KeyType bknum,ArcBox* prep){//if bknum can be found in readers borrowed list, then return its arcboxs address, else return NULL.//prep return temps precursor, when it has no precursor, return NULLArcBox *tempr.first_arc; prepNULL;while(temp!EQ(bknum,temp-bknum)){preptemp;temptemp-next;}return temp;
}void LibManage::ReaderCpy(Reader r1,const Reader r2){//copy readers info from r2 to r1strcpy(r1.name,r2.name);strcpy(r1.tele,r2.tele);r1.coder2.code;r1.first_arcr2.first_arc;
}void LibManage::PrintReader(const Reader r){printf(- - - - Reader Info - - - -\n);printf(Name: %s\n,r.name);printf(Code: %0*d\n,MAXREADERCODEDIGIT,r.code);printf(Tele: %s\n,r.tele);PrintBorrowedBooks(r);printf(- - - - - - - - - - - - -\n);
}void LibManage::PrintBorrowedBooks(Reader r){printf(Borrowed books: \n);if(!r.first_arc) printf(\t(Empty) \n);while(r.first_arc) {printf(%s | ISBN %s | Deadline:%u(%s)\n,r.first_arc-bknam,r.first_arc-bknum,r.first_arc-return_date,current_dater.first_arc-return_date? ![Overdue]!:[Normal]);r.first_arcr.first_arc-next;}
}int main(int argc, char *argv[]){LibManage LMSystem;int opt;LMSystem.Menu();do{printf(Menu-Option: );scanf(%d,opt);getchar();switch(opt){case 0: break;case 1: LMSystem.AddBook(); break;case 2: LMSystem.LendBook(); break;case 3: LMSystem.ReturnBook(); break;case 4: LMSystem.EraseBook(); break;case 5: LMSystem.OutputBooks(); break;case 6: LMSystem.OutputReaders(); break;case 7: LMSystem.TestMode(); break;default: printf(ERROR: Wrong command, try again... \n); break;}//switch(opt)}while(opt);return 0;
}
头一次写文章难免有些纰漏还望各位指正。 二叉搜索树平衡二叉树红黑树的算法效率 ↩︎ 艾兹格·W·迪科斯彻 (Edsger Wybe Dijkstra1930年5月11日~2002年8月6日) ↩︎
