基于二叉排序树的图书信息检索.docx
- 文档编号:5072145
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:23
- 大小:207.31KB
基于二叉排序树的图书信息检索.docx
《基于二叉排序树的图书信息检索.docx》由会员分享,可在线阅读,更多相关《基于二叉排序树的图书信息检索.docx(23页珍藏版)》请在冰点文库上搜索。
基于二叉排序树的图书信息检索
课程设计报告
设计题目:
基于二叉排序树的图书信息检索
学院:
电子工程学院
专业:
电子信息工程
班级:
021115学号:
02111410
学生姓名:
李晨
电子邮件:
550724092@
时间:
2014年10月17
成绩:
指导教师:
1前言
1.1课程设计的目的
通过数据结构课程设计能更加熟练的掌握C语言以及数据结构的相关知识,能宏观的把握数据结构的各个相关部分的知识,深入的理解各个分支结构的作用和运用,特别是通过本此课程设计更能熟练的掌握和运用二叉树的相关知识,如通过二叉树能实现查找、删除、排序等从而实现对图书借阅管理。
因而课程设计的主要目的就是使同学们能熟练的运用数据结构的相关知识实现各种功能。
1.2图书借阅管理系统的设计与实现的基本要求
对每种书登记内容包括书号、书名、作者、出版社、出版日期、页码、价格;对所有藏书以书号为关键字建立索引表——排序二杈树,用以方便进行二分查找;
(1)采编入库:
新购一种书,确定书号后,登记到图书帐目表中,如果表中已有,则只将库存量增加;
(2)借阅:
如果一种书的现存量大于0,则借出一本,登记借阅者的书证号和归还期限,改变现存量;
(3)归还:
注销对借阅者的登记,改变该书的现存量。
系统主要功能如下:
输出形式:
能按书号、书名、著作者查找库存的书籍信息;能按学生的借书证号显示学生信息和借阅信息;书籍入库;借书功能实现;还书功能实现。
1.3数据结构相关知识的阐述
本课程设计运用到得数据结构部分主要在于二叉树的运用,采用二叉树的二叉链表存储结构把单本的书关联起来,这样就可对馆藏的所有书进行统一的管理;采用排序二叉树作为索引表的优点是方便按索书号为关键字进行查询;对于一个实用的管理系统来说缺省查找是必不可少的,本系统中采用字符串的模式匹配算法来实现信息的缺省检索。
采用二分查找实现精确查找;运用二叉树的插入、删除、排序来实现对图书的添加、删除、排列。
2功能描述
二叉树的排序主要用于对图书管理系统的图书进行排序,采用二叉树的二叉链表存储结构把单本的书关联起来。
这样就可对馆藏的所有书进行统一的管理了。
二叉树的插入用于实现对图书管理系统的图书进行添加,对二叉树的节点插入新节点,然后从新排列新序列来实现图书的插入。
二叉树的删除主要用来对图书管理系统的图书进行销毁,对二叉树节点的删除,节点表示一本图书,删除节点就表示销毁不需要的图书信息
。
3系统设计
3.1设计思路
由于课程设计的要求是用纯的c语言实现,不能采用数据库等操作数据,故节点的设计采用标准c语言提供的一种叫做结构体的复合数据类型存储书的信息,然后再采用二叉树的二杈链表存储结构把单本的书关联起来。
这样就可对馆藏的所有书进行统一的管理了。
根据我们日程经验,客户到图书馆借书或者到书店买书,客户可以通过多种查询方式获得所需要的书,通过索书号只能进行精确查找,对于一个实用的管理系统来说缺省查找是必不可少的,本系统中采用字符串的模式匹配算法来实现信息的缺省检索。
采用二分查找实现精确查找。
4算法设计
4.1节点数据的设计
4.1.1图书的存储结构模型
(1)typedefstructbook
{
longintstarting;//借书日期
longintending;//应还日期
charbookinform[120];//这里面存储书籍的描述信息
longintcallnum;//索书号
charbookname[30];
charwriter[20];
inttotalstorage,nowstorage;//书本的馆藏量,现有量
}book;
(2)/*本结构体用于创建二叉树*/
typedefstructvolume
{
bookbooks;
structvolume*lchild;
structvolume*rchild;
}volume,*Btvolume;
说明:
采用二叉树而非链表进行图书的管理
4.1.1管理员存储模型
typedefstructadminister
{
charadminID[12];
charpassword[12];
charadminname[20];//管理员名字...
charadminmessage[150];
structadminister*next;
}administer;
说明:
采用二叉树而非链表进行图书的管理
4.2公共参变量说明
4.2.1administer*admins,*current_admin=NULL;
说明:
admins作为链接所有管理员的头指针
current_admin用于管理当前登陆的管理员用户
同一时刻只允许最多一名管理员登录
4.2.2libcard*clients,*current_client=NULL;
说明:
clients作为链接所有客户的头指针
current_client用于管理当前登陆的客户
同一时刻最多只允许一名客户登录
4.3二叉排序树的插入模块的设计——voidinsertBST(Btvolume*bst,book*key)
功能说明:
利用二叉树的结点插入方法对结点进行插入设置,从而来实现对图书信息进行插入。
如下图:
4.4二叉排序树的创建模块的设计——voidcreateBST(Btvolume*bst,intmanner)
功能说明:
在二叉树的根节进行创建,通过文件和键盘的信息输入方法来添加相关结点及相关图书信息。
如下图:
4.5二叉排序树的查找模块设计——BtvolumesearchBST(Btvolumebst,longintkey)
功能说明:
利用二叉树的结点查找方法对结点进行查找设置,从而来实现对图书信息进行查找。
如下图:
4.6二叉排序树的删除模块设计——intdelBST(Btvolumebst,intkey)
功能说明:
利用二叉树的结点删除方法对结点进行删除设置,然后从新排列,从而来实现对图书信息进行删除,如下图:
4.7主函数的设计
功能说明:
主要目的是对图书管理的实现,通过对算法设计和组织,利用图形化界面来实现用户和管理员对图书系统的访问。
如下图:
5详细设计
5.1采用排序二叉树作为存储结构
#include
#include
#include
#include
#include
#defineMAXNUM10
typedefstructbook
{
longintstarting;//借书日期
longintending;//应还日期
charbookinform[120];//这里面存储书籍的描述信息
longintcallnum;//索书号
charbookname[30];
charwriter[20];
inttotalstorage,nowstorage;//书本的馆藏量,现有量
}book;
5.2创建链表的二叉树
功能:
本结构体用于创建链表的二叉树,通过对结点的生成来创建新的二叉树,最终生成图书管理系统。
typedefstructvolume
{
bookbooks;
structvolume*lchild;//左孩子部分
structvolume*rchild;//右孩子部分
}volume,*Btvolume;
typedefstructlibcard
{
charuserID[12];
charpassword[12];//用户的密码
charclientname[20];//用户的名字
charusermessage[150];//用户信息
bookborrow[10];//每本借书证限借书十本
structlibcard*next;
}libcard;
typedefstructadminister
{
charadminID[12];
charpassword[12];
charadminname[20];//管理员的名字...
charadminmessage[150];
structadminister*next;
}administer;
administer*admins,*current_admin=NULL;
libcard*clients,*current_client=NULL;
5.3二叉排序树的插入模块,采用递归算法实现
功能:
本结构体用于二叉排序树的插入模块,采用递归算法实现,通过对结点的插入来创建新的二叉树,最终生成图书管理系统。
voidinsertBST(Btvolume*bst,book*key)
{
Btvolumes;
if(*bst==NULL)//递归结束条件
{
s=(Btvolume)malloc(sizeof(volume));
s->books.callnum=key->callnum;
s->books.nowstorage=key->nowstorage;
s->books.totalstorage=key->totalstorage;
s->books.starting=key->starting;
s->books.ending=key->ending;
strcpy(&(s->books.bookinform),&(key->bookinform));
strcpy(&(s->books.bookname),&(key->bookname));
strcpy(&(s->books.writer),&(key->writer));
s->lchild=NULL;
s->rchild=NULL;
*bst=s;
}//递归结束条件
elseif(key->callnum<(*bst)->books.callnum)
{
insertBST(&((*bst)->lchild),key);
}
elseif(key->callnum>(*bst)->books.callnum)
{
insertBST(&((*bst)->rchild),key);
}
else
{
(*bst)->books.nowstorage+=key->nowstorage;
(*bst)->books.totalstorage+=key->totalstorage;
}
}
5.4本模块实现二叉排序树的建立
功能说明:
1、参数Btvolume*bst为待创建树的根节点
2、只有库存量为空的时候才能调用本模块
3、只有管理员才能调用本模块
4、参数manner用于指定从文件创建还是从键盘创建
manner=1:
键盘、manner=2:
从文件
5、只有在系统初始化是才允许从键盘创建
voidcreateBST(Btvolume*bst,intmanner)
{
book*key;
FILE*f_book_store=NULL;
f_book_store=fopen("book_store.txt","r");
*bst=NULL;
while
(1){
key=(book*)malloc(sizeof(book));//
if(manner==1)
{
/*输入书本信息*/
key->starting=0;
key->ending=0;
printf("输入索书号:
");
scanf("%ld",&(key->callnum));
if(key->callnum==0){
free(key);
break;
}/*输入书本信息*/
printf("输入入库量:
");
scanf("%d",&(key->totalstorage));
key->nowstorage=key->totalstorage;
printf("输入书本名:
");
scanf("%s",&(key->bookname));
printf("输入著作者:
");
scanf("%s",&(key->writer));
printf("输入书描述:
");
scanf("%s",&(key->bookinform));
}
else
{
if(!
feof(f_book_store))//判断文件是否结束
{
key=read_book_file(f_book_store);
if(key->callnum<-1)
{
free(key);
key=NULL;
}
}
else
{
free(key);
break;
}
}
if(key!
=NULL)
insertBST(bst,key);//调用插入操作实现新书入库
}
fclose(f_book_store);
///////////////////////////////////////////////////////////////////////
f_book_store=fopen("book_store.txt","w");
write_book_file(f_book_store,*bst);
fclose(f_book_store);
///////////////////////////////////////////////////////////////////////
}
5.5二叉排序树的查找算法
功能:
按索书号为关键字进行二分查找,采用递归算法实现,通过对结点的查找来创建新的二叉树,最终生成图书管理系统。
BtvolumesearchBST(Btvolumebst,longintkey)
{
if(bst==NULL)
returnNULL;
if(bst->books.callnum==key)
returnbst;
if(bst->books.callnum returnsearchBST(bst->rchild,key); returnsearchBST(bst->lchild,key); } 5.6二叉排序树的删除算法 功能: 实现对馆藏的书籍进行销毁,返回是否成功 intdelBST(Btvolumebst,intkey) { intsuccess=0; Btvolumep,f,s,q; p=bst; f=NULL;//实现对图书管理 while(p) { if(p->books.callnum==key) break; f=p; if(p->books.callnum>key) p=p->lchild; else p=p->rchild; }//选择对左节点还是右结点进行访问 if(p==NULL) { success=1; returnsuccess;//结点为空,对结点访问成功 } if(p->lchild==NULL) { if(f==NULL) bst=p->rchild; elseif(f->lchild==p) f->lchild=p->rchild; else f->rchild=p->rchild; free(p); success=1; }//访问结点的左孩子和右孩子成功 else { q=p; s=p->lchild; while(s->rchild) { q=s; s=s->rchild; } if(q==p) q->lchild=s->lchild; else q->rchild=s->lchild; p->books.callnum=s->books.callnum;//对左右孩子进行设置 free(s); success=1; } returnsuccess; } 5.7显示管理员信息 功能: 本结构体重要用于对管理员信息进行管理,显示管理员的信息。 voiddisplay_admins(administer*head) { inti=0; administer*temp=head; if(head==NULL) { printf("您好,当前无管理员! \n"); return; } while(temp! =NULL) { printf("---------------------------------------------\n"); printf("管理员ID: %s\n",temp->adminID); printf("管理员姓名: %s\n",temp->adminname); printf("管理员信息: %s\n",temp->adminmessage); printf("---------------------------------------------\n"); temp=temp->next; } } voiddisplay(volume*key) { time_tt; if(key==NULL) { printf("对不起,本馆目前无此藏书! \n"); return; } printf("---------------------------------------------\n"); printf("索书号: %d\n",key->books.callnum); printf("书名: %s\n",key->books.bookname); printf("作者: %s\n",key->books.writer); } 6调试 6.1进入系统 您有三种选择,登录,注册和离开如果您已注册可直接登录,若目前还没有注册请先注册。 当您选择注册之后会出现如下界面,当您两次输入的密码不能匹配系统会让你一直输,直到匹配为止。 6.2成进入系统之后你就可以进行相关操作了 6.2.1管理员用户 (1)图书入库功能 (2)图书查询 (3)图书浏览 7总结 通过一周多的学习思考与实践,让我对C语言有了更深层次的了解,一个好的程序需要一个好的数据结构和一个好的算法,通过本次课程设计的过程中,掌握了数据结构的作用,数据结构的重点不在于它的算法的复杂度,数据结构的主要目的是为了让学生们学会如何将算法组合成为一个正确的、可靠的、可维护的系统。 通过熟练的运用数据结构的二叉树的遍历、排序、节点的插入以及删除,从而来实现对图书管理系统的设计和维护。 在这次课程设计的过程中,遇到过很多难题,主要表现在代码的错误上。 而很多错误并不是由于没有掌握好数据结构的知识,而是在一些细节上出错,如代码拼写错误等等。 因此在课程设计的过程中,我们得细心的去写每一个代码。 避免不该出现的错误,耽误了大量的时间。 这次还要多谢同学,耐心给我解答各种疑惑,提供给我多条解决问题的途径,虽然这次我们是各行其是,但我也感觉到了团队合作的魅力,见识到了同学学识的渊博,感觉到了自己和同学的差距,要多向同学学习,学习同学的积极进取及踏实努力。 这次课程设计也加深了我们同学之间的友谊,总之,这次课程设计让我受益匪浅。 8参考文献 [1]《数据结构》(C语言版),严蔚敏,清华大学出版社,2003. [2]《c程序设计》,容政,胡建伟,西安电子科技大学,2006. [3]《计算机软件技术基础教程》,刘彦明,西安电子科技大学2001.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 二叉排序树 图书 信息 检索
![提示](https://static.bingdoc.com/images/bang_tan.gif)