文档介绍：数据结构
课程设计报告
班级:
学号:
姓名:
指导老师: 郭艳
日期: 2016年7月
题目:10图书管理系统
需求分析
图书管理基本业务活动包括:对一本书的采编入库、清除库存、借阅和归还等等。试设
计一个图书管理系统,将上述业务活动借助于计算机系统完成。
【要求】
(1)每种书的登记内容至少包括书号、书名、著者、现存量和总库存量等五项。
(2)作为演示系统,不必使用文件,全部数据可以都在内存存放。要用B-树(4 阶树)
对书号建立索引,以获得高效率。
(3)系统应有以下功能:
采编入库、清除库存、借阅、归还、显示(以凹入表的形式显示)等。
设计
(1)数据与操作的特性:定义一个图书book类,能够实现对象的查找插入删除等功能,由于书籍数据量较大,所以函数功能需要尽可能的缩小时间复杂度。
(2)数据结构设计:使用B-树来进行存储,其逻辑结构为树形结构,B-树有利于关键字的查找,是一种平衡多叉排序树。
(3)算法设计:将比关键字小的元素插到该关键字的左孩子结点中,比关键字大的的元素插到该关键字的右孩子结点中,当一个结点中关键字的个数超过规定的个数时,该节点要进行分裂,并且保证所有的叶子结点都在同一层。 包括如下几个模块:图书采编入库、清除库存、图书借阅、图书归还、显示所有图书、查阅库存。
(1)函数调用关系图
(2)函数接口规格说明
void insert(book &key) //在B树中插入关键字key
void remove(const book &key) //将key移除
void clear() //删除树
void recursive_clear(Node *pNode) //删除节点pNode
void splitChild(Node *pParent, int nChildIndex, Node *pChild)
//分裂子节点
void insertNonFull(Node *pNode, const book &key)//在非满结点插入关键字
void mergeChild(Node *pParent, int index) //合并两个结点
void displayInConcavo(Node *pNode, int count) //打印
book getPredecessor(Node *pNode) //找前驱结点
book essor(Node *pNode) //找后驱结点
首先定义了book类,用来表示书本的标记信息。
struct book{
int booknum;
char name[30];
char type[30];
char author[30];
char publish[40];
int sign; //现存量,也是书本借还的标记
int allstore;
}
根据题目要求分析,建立B-树
class BTree{
private:
static const int KEY_MAX = 3; //节点包含关键字的最大个数
static const int KEY_MIN =1; //非根节点包含关键字的最小个数
static const int CHILD_MAX = 4; //孩子节点的最大个数
static const int CHILD_MIN =2; //孩子节点的最小个数
struct Node{
bool isLeaf; //是否是叶子节点
int keyNum; //节点包含的关键字数量
book keyValue[KEY_MAX]; //关键字的值数组
Node *pChild[CHILD_MAX]; //子树指针数组
Node(bool b = true, int n = 0) :isLeaf(b), keyNum(n){}
};
Node * m_pRoot; //B树的根节点
B树的查找功能,是进行其它任务的前提。根据给定值查找结点和在结点的关键字中进行查找交叉进行。首先从根结点开始重复如下过程: 若比结点的第一个关键字小,则查找在该结点第一个指针指向的结点进行;若等于结点中某个关键字,则查找成功;若在两个关键字之间,则查找在它们之间的指针指向的结点进行;若比该结点所有关键字大,则查找在该
结点最后一个指针指向的结点进行;若查找已经到达某个叶结点,则说明给定值对应的数据记录不存在,查找失败。代码实现如下:
bool search(Node *pNode, const int &key