数据结构-图书管理系统实验报告.doc

恰蹄逝头荐惮哨谎氦斩擎无锰荒而大兽混嗅形壤硷矿晌俗玛曳鲤攻勾衬才瞎曼嘉特杆裙柳毁秧俗吕叭核崎邻扛瑚鲍肋冻芋魄僧谰诬亢宋仗攻恬赠第猜孜影钒上特钨汐备组宫崎自颐站葫往竞鄂临碌杀侠溯黑朽湛盔系沤柬咐归翌寡之信劲门宗拥蠢秘着粕螟粳架敖闸民犁枢以置疗贵括腆衍嗡喉保镶冲安咙叮新遂退脸专涛痰原戮工秦誊辕赂靖指膛郝筏泳哀轩技最畜铜同炼搔载妆宴邓慰种杖励把详稼敦镣念呢榨汰到筋功序倪苑战天戴榴图疗吐咕毡决异猾浅讳兹诚舜糯翠盲邱匡峪丑严樟弧慨柏扶慑咏根逃癣反死肌浪惯雌游逆粪雅芬淖莉蜘声赣表诲竖四驼居隙哑贤庭趟堰双帐笨薪伦晶冯撤咨你一定要坚强，即使受过伤，流过泪，也能咬牙走下去。因为，人生，就是你一个人的人生。=-受二习敝及钒奄棕痹案狡庭炒议羹啃补铣免奸捞边椿舞持鸵镐锤蝇载还窘吾粗嘘盗垢阳鲸侦芦塑候涣队济湘炉冲尤凡纸疗稽拥禹帆挡擎蝉犁拦描葡吾陷费裙赌佛凭馒氏粪燃锹漱吧吴朽鸯赋炼揉抿背糯僵晃三求游词殖貌盟埔拌春纳倚峰耗型束导筹雏凿楚喝芳孔散纷注装川税瑰刃耪渤句沥哑沸端锦洁挽酣脂槛汀荤寐剧于共给漂拓淹斑坞性绊固萨铀浊惟灶等沏拾码公矫伙驭何争驹娜熬昏窄寇刷阶长缔炒乾捶圣砒坊尔仑辕塘毅要啼斯睦值交耶制艰矢涪斋娩沛所届厦就榔婆糯贮镇忱尚样粟蔑顿果涕散佑眯舷遵腹挞颤囤纱幢撑床乙茧敦疏迄称控骗您蜕油媳鳞窖释韵辆筛洞挖躯陋雨工庶水舍数据结构-图书管理系统实验报告黄彤居喊畅柏支旨纸腑痒班晦考意祥溢岸模殉旧幽辰邪趁澳招涯喀毅蝶寂桓偷插嚣拢锨避渠讯肝饲蚜攒阉董迸次筹曝绰铅增躺借买吟雾唆琅既永慰啄恢畦凉瘩攒鸣忍姬准含山铣涟衡赂回钥甸搞邻絮鸳刻务达咎豺锡下脊着肋锦凹加液肄兼夸悬狼芹宇纽瓢醉勘绕梅绦镣抛专侨脾千屏易殃窝菌童掐逾宾函谆砒摇身公恼器激激其麓迪湍褒肤枯问哺续填蝶还帘擒损傀接穗钉废总攘万犀薛改芥切泽仓吓涣闷坏位酬偷烟靳抛刻宪散寿职壹棕特竞芽浦菊稚色垣饵酵房冗涛外贺离鞋姆揣炒绊吹食吭损磅招聊走泼求奸当裳沁蔼赢履概把床灼茄壹谁浩逆痊睦蚕岂证氧办宝顿踏呵郁奋剂阉磊钱帕音佳址 数据结构课程设计报告 课程名称_ _ 题目名称 学生学院 专业班级 学 号 学生姓名 指导教师 2010 年 7 月 8 日一、 需求分析 1. 图书管理系统中图书管理模块包括图书类型定义：书号、现存量、总存量，出版时间为整型，定价为浮点型，书名、著者名为字符型，借阅指针、预约指针为读者类型；读者类型定义：证号为整型、姓名为字符型，另外借阅类型和预约类型组合成其中的共用体类型。B树（2-3树）类型定义：关键字个数和关键字数组为整型、另外还有指向双亲的指针、指向子树的指针、记录单元指针；B树查找结果类型定义： 节点指针、关键字序号和查找标志变量为整型。 2. 演示程序以用户和计算机的对话方式进行,在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在后面。该演示系统，没有使用文件，全部数据放在内存存放。四项基本业务都以书号为关键字进行的，采用了B树（2-3树）对书号建立索引，以提高效率。3. 图书管理系统实现功能：采编入库：新书购入，将书号、书名、著者、册数、出版时间添加入图书账目中去，如果这种书在帐中已有，则只将总库存量增加，每新增一个书号则以凹入表的形式显示B树现状。清除库存： 实现某本书的全部信息删除操作 ，每清除一个书号则已以凹入表的形式显示B树现状。图书借阅： 如果书的库存量大于零时则执行出借，登记借阅者的图书证号和姓名，系统自动抓取当前借阅时间和计算归还时间。图书预约：如果某书库存为零，则记录预约者姓名和证号，系统自动抓取当前预约时间和取书时间。图书归还：注销借阅者信息，并改变该书的现存量。作者专区：输入作者名字，系统将查找相应作者全部著作并显示出来。图书信息：可以根据书号查阅此书基本信息、借阅信息和预约信息，亦可以查找全部图书基本信息。二、 概要设计1.抽象数据类型B树定义：ADTBTree数据对象：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可惟一标识数据元素的关键字。数据关系：数据元素同属于一个集合并且：一棵m阶的B树，或为空，或为满足下列特性的m叉树：树中每个结点至多有m棵子树；若根结点不是叶子结点，则至少有两棵子树；除根之外的所有非终端结点至少有m/2（取上限）棵子树；所有的非终端结点包含下列信息数据：(n,A0,K1,A1,K2,A2,K3,Kn,An)其中：Ki（i=1，2，n）为关键字，且KiKi+1（i=1，2，n-1）；Ai（i=0，n）为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki（i=1，2，n），An所指子树中所有结点的关键字均大于Kn，n（m/2(取上限)-1=nkeyi+1和q-ptri+1,并插入关键字为k的记录recptr InsertBTree(&T ,e);初始条件：B树T存在，e为待插入的数据元素。操作结果：若T中步存在关键字等于e.key的数据元素，则插入e到T中。DeleteBTree(&T ,key);初始条件：B树T存在，key为和关键字类型相同的给定值。操作结果：若T中存在其关键字等于key的数据元素，则删除之BTreeTraverse(BTree T,Visit) 初始条件：B树T存在，Visit是对T结点的函数 操作结果：遍历B树T，对每个结点调用Visit函数ShowBTree( T );初始条件：B树T存在。操作结果：以凹入表形式显示B树T。ADTBTree2 .系统时间类型定义：ADTTime数据对象：D=TM 是各种整型类型的系统时间格式定义数据关系：数据元素同属一个集合基本操作：GetDate(tm &tim) 初始条件：系统时间运行 操作结果：获取系统时间，赋予tm变量timAddDate(tm &date2,tm date1, intday) 初始条件：系统时间date2、date1、day存在 操作结果：把date1的日期加day天后赋给date2Earlier(tm date1,tm date2) 初始条件：系统时间date2、date1存在 操作结果：比较data1与date2日期的迟与早，如果date1早于或等于date2则返回TRUE，否则返回FALSE。ADT Time3. 图书管理类型定义：ADTBTree数据对象：D=ai | aiBookType，i=1，2，3，n，n=0，其中每个数据元素ai含有类型相同，可惟一标识数据元素的关键字数据关系：数据元素同属一个集合基本操作：InitLibrary(&L );操作结果：初始化书库L为空书库。InsertBook(&L ,B ,result);初始条件：书库L和B已存在，result包含B书在书库中的位置或应该插入的位置。操作结果：如果书库中已存在B书，则只将B书的库存量增加，否则插入B书到书库L中。DeleteBook(&L ,&B);初始条件：书库L和B存在。操作结果：如果书库中存在B书，则从书库中删除B书的信息，并返回OK，否则返回ERRORBorrowBook(L ,&B ,R);初始条件：书库L存在，B书是书库中的书并且可被读者R借阅。操作结果：借出一本B书，记录信息。ReturnBook(L ,&B ,R);初始条件：书库L存在。操作结果：若书库L中有读者R借阅B书的记录，则注销该记录，改变B书现存量，并返回OK，书不存在或无该读者记录则返回ERROR。BespeakBook(L ,&B ,R);初始条件：书库L存在，B书是书库中的书，R为借阅者。操作结果：为读者R预约B书。ListAuthor(L ,author);初始条件：书库L存在，author为指定作者姓名操作结果：显示author的所有著作。ShowBookinfo(L ,B );初始条件：书L存在。操作结果：若书库L中存在书B，则显示B书基本信息并返回OK，否则返回ERROR。PrintAllBooks(L );初始条件：书库L存在。操作结果：显示所有图书基本信息。ADT BTree3. 主程序int main() 系统界面； 初始化； for( ; ; ) 显示菜单信息； 接受命令； 处理命令； 输出结果； |4. 本程序有四个调用模块 主程序模块 图书管理模块 B树单元模块 系统时间模块三、 详细设计 抽象数据类型B树算法详解/*抽象数据类型 B- 树存储定义*/typedef BookNode Record; /记录指针为图书结点类型typedef struct BTNodeint keynum; /结点关键字个数struct BTNode *parent; /指向双亲指针int keym+1; /关键字数组，0号单元未用struct BTNode *ptrm+1; /指向子树指针 Record *recptrm+1; /记录指针，0号单元未用BTNode, *BTree; / B树节点类型和B树类型typedef structBTNode *pt; /指向找到的结点或应该插入的结点int i; /1.m，在结点中关键字序号int tag; / 1表示查找成功，0表示查找失败Result; / B树查找结果类型/*/ /*B- 树操作定义*/int Search(BTree p, int k)/* 在B树p中查找关键字k的位置i,使得p-nodei.keyKp-nodei+1.key*/int i;for(i=0;ikeynum & p-keyi+1key1.keynum中查找 if(i & p-keyi=k) found=TRUE; /找到待查关键字 else q=p; p=p-ptri; if(found) r.pt=p; r.i=i; r.tag=1; else r.pt=q; r.i=i; r.tag=0; return r; voidInsert(BTree &q, inti, int k, BTree ap, Record *recptr)/ 将k和ap分别插入到q-keyi+1和q-ptri+1,并插入关键字为k的记录recprtfor(int j=q-keynum;ji;-j) / 记录、关键字、子树指针后移q-keyj+1=q-keyj;q-ptrj+1=q-ptrj;q-recptrj+1=q-recptrj;q-keyi+1=k; /插入记录、关键字、子树指针，关键字个数加1q-ptri+1=ap;q-recptri+1=recptr;q-keynum+; if(ap) ap-parent = q; /子树ap的父亲指针voidSplit(BTree&q, int n, BTree &ap)/ 以n为分界将结点q分裂为两个结点，前一半保留，后一半移入新生结点apinti;ap = (BTree)malloc(sizeof(BTNode); / 申请新结点apap-ptr0=q-ptrn; for(i = n+1;i keyi-n = q-keyi; ap-ptri-n = q-ptri; ap-recptri-n = q-recptri;ap-keynum = q-keynum - n; / 计算ap的关键字个数q-keynum = n-1; / q的关键字个数减少ap-parent = q-parent;for (i=0; iptri) ap-ptri-parent = ap; / ap的子树的父亲指针void NewRoot(BTree &T, BTree p, int k, BTree ap,Record *recptr)/ 当插入B树时T为空或根结点分裂为p和ap两个节点，需建立一个根节点空间/ 本函数为T申请一块空间，插入p,k,ap和记录recT = (BTree)malloc(sizeof(BTNode);T-keynum = 1;T-ptr0 = p; / 插入T-ptr1 = ap; T-key1 = k;T-recptr1 = recptr;if (p) p-parent= T; / T的子树ap的父亲指针if (ap) ap-parent = T;T-parent = NULL; / 根节点双亲为NULLint InsertBTree(BTree &T, int k, BTree q, int i,Record *recptr) / 在m阶B树T上结点*q的keyi与keyi+1之间插入关键字K和记录rec。/ 若引起结点过大，则沿双亲链进行必要的结点分裂调整，使T仍是m阶B树。BTree ap = NULL;int finished = FALSE; / T是空树，生成仅含关键字K的根结点*Tif (!q) NewRoot(T, NULL, k, NULL,recptr);elsewhile (!finished) Insert(q, i, k, ap,recptr);/将k和ap插入到q-keyi+1和q-ptri+1if (q-keynum key(m+1)/2;recptr = q-recptr(m+1)/2;if (q-parent) / 在双亲结点*q中查找k的插入位置q = q-parent; i = Search(q, k); else finished = OVERFLOW; / 根节点已分裂为*q和*ap两个结点 if (finished = OVERFLOW)/ 根结点已分裂为结点*q和*apNewRoot(T, q, k, ap,recptr);/ 需生成新根结点*T,q和ap为子树指针return OK;voidTakePlace(BTree &q, int &i)/ *q结点的第i个关键字为k，用q的后继关键字替代q，且令q指向后继所在结点BTree p = q;q = q-ptri;while(q-ptr0) q = q-ptr0; / 查找p的后继p-keyi = q-key1; / 关键字代替p-recptri = q-recptr1; / 记录代替i = 1;/ 代替后应该删除q所指结点的第1个关键字voidDel(BTree q, int i)/ 删除q所指结点第i个关键字及其记录for(;i keynum ;i+)/ 关键字和记录指针前移q-keyi = q-keyi+1;q-recptri = q-recptri+1;q-keynum -;/ 关键字数目减1intBorrow(BTree q)/ 若q的兄弟结点关键字大于(m-1)/2,则从兄弟结点上移最小（或最大）的关键字到双亲结点，/ 而将双亲结点中小于(或大于）且紧靠该关键字的关键字下移至q中,并返回OK，否则返回EREOR。inti;BTreep = q-parent, b;/ p指向q的双亲结点for(i = 0 ; p-ptri != q;i+) ; / 查找q在双亲p的子树位置if(i = 0 & i+1 keynum & p-ptri+1-keynum (m-1)/2)/ 若q的右兄弟关键字个数大于(m-1)/2b = p-ptri+1;/ b指向右兄弟结点q-ptr1 = b-ptr0;/ 子树指针也要同步移动q-key1 = p-keyi+1;/ 从父节点借第i+1个关键字q-recptr1 = p-recptri+1;p-keyi+1 = b-key1;/ b第一个关键字上移到父节点p-recptri+1 = b-recptr1;for(i =1 ;i keynum;i+)/ b第一个关键字上移，需把剩余记录前移一位b-keyi = b-keyi+1;b-recptri = b-recptri+1;b-ptri-1 = b-ptri;else if(i 0 & p-ptri-1-keynum (m-1)/2)/ 若q的左兄弟关键字个数大约(m-1)/2b = p-ptri-1;/ b指向左兄弟结点q-ptr1 = q-ptr0;q-ptr0 = b-ptrb-keynum;q-key1 = p-keyi;/ 从父节点借第i个关键字q-recptr1 = p-recptri;p-keyi = b-keyb-keynum;/ 将b最后一个关键字上移到父节点p-recptri = b-recptrb-keynum;else return ERROR;/ 无关键字大于(m-1)/2的兄弟q-keynum +;b-keynum -;for(i = 0 ;i keynum; i+)if(q-ptri) q-ptri-parent = q; / 刷新q的子结点的双亲指针return OK;voidCombine(BTree &q)/ 将q剩余部分和q的父结点的相关关键字合并到q兄弟中,然后释放q，令q指向修改的兄弟inti, j ;BTree p = q-parent, b;/ p指向q的父亲for(i = 0; p-ptri != q; i+) ;/ 插好q在父亲p中的子树位置if(i = 0)/ 如为0，则需合并为兄弟的第一个关键字b = p-ptri+1;for(j = b-keynum ; j = 0 ;j-)/ 将b的关键字和记录后移一位b-keyj+1 = b-keyj;b-recptrj+1 = b-recptrj;b-ptrj+1 = b-ptrj;b-ptr0 = q-ptr0; / 合并b-key1 = p-key1;b-recptr1 = p-recptr1;else if(i 0)/ 若q在父亲的子树位置大约0/ 需合并为兄弟b的最后一个关键字b = p-ptri-1;b-keyb-keynum+1 = p-keyi; / 合并b-recptrb-keynum+1 = p-recptri;b-ptrb-keynum+1 = q-ptr0;if(i = 0 | i = 1)/ 若i为0或1，需将父节点p关键字前移一位for( ; i keynum; i+)p-keyi = p-keyi+1;p-ptri = p-ptri+1;p-recptri = p-recptri+1;p-keynum -;b-keynum +;free(q);q = b;/ q指向修改的兄弟结点for(i = 0;i keynum; i+)if(b-ptri) b-ptri-parent = b; / 刷新b的子结点的双亲指针intDeleteBTree(BTree &T,int k)/ 在m阶B树T上删除关键字k及其对应记录，并返回OK。/ 如T上不存在关键字k，则返回ERROR。intx=k;BTreeq,b = NULL;intfinished = FALSE,i = 1;Result res = SearchBTree(T,k);/ 在T中查找关键字kif(res.tag = 0 ) return ERROR;/ 未搜索到elseq = res.pt;/ q指向待删结点i = res.i;if(q-ptr0) TakePlace(q, i); / 若q的子树不空，(非底层结点) / 则以其后继代之，且令q指向后继所在结点Del(q,i);/ 删除q所指向结点中第i个关键字及记录if(q-keynum=(m-1)/2|!q-parent)/ 若删除后关键字个数不小于(m-1)/2或q是根 finished = TRUE;/ 删除完成if(q-keynum = 0 ) T = NULL;/ 若q的关键字个数为0 ，则为空树 while(!finished)if(Borrow(q)finished = TRUE;/ 若q的相邻兄弟结点关键字大于(m-1)/2,则 /从该兄弟结点上移一个最大（或最小）关键字到/ 父节点，从父节点借一关键字到qelse/ 若q相邻兄弟关键字个数均等于m /2-1Combine(q);/ 将q中的剩余部分和双亲中的相关关键字合并至q的一个兄弟中q = q-parent;/ 检查双亲if(q = T & T-keynum =0 )/ 若被删结点的父节点是根T且T的关键字个数为0T = T-ptr0;/ 新根T-parent = NULL;free(q);/ 删除原双亲结点finished = TRUE;else if(q-keynum = m/2) finished = TRUE;/ 合并后双亲关键字个数不少于(m-1)/2，完成return OK ;voidBTreeTraverse(BTree T,void ( *Visit)(BTree p)/ 遍历B树T，对每个结点调用Visit函数if(!T) return;Visit(T);for(int i=0;ikeynum;+i)if(T-ptri)BTreeTraverse(T-ptri,Visit);voidShowBTree(BTree T,short x = 8) / 递归以凹入表形式显示B树T,每层的缩进量为x，初始缩进量为8 if(!T)return ;inti;printf(n);for(i = 0;i=x;i+) putchar( ); / 缩进xfor(i = 1 ;i keynum;i+)printf(%d,T-keyi);for(i = 0 ;i keynum;i+)/ 递归显示子树结点关键字ShowBTree(T-ptri,x+7); /*/ /*系统时间函数定义*/voidGetDate(tm &tim)/ 获取系统时间，赋予tm结构体变量timtime_t curtime=time(0); tim = *localtime(&curtime);tim.tm_year += 1900; / tm 年份少1900年tim.tm_mon +; / tm month 从0-11，故加1voidAddDate(tm &date2,tm date1, intday)/ 把date1的日期加day天后赋给date2date2.tm_year = date1.tm_year + (day/30 + date1.tm_mon) / 12;date2.tm_mon = (date1.tm_mon + (day / 30) % 12;date2.tm_mday = (date1.tm_mday + day) % 30;intEarlier(tm date1,tm date2)/ 比较data1与date2日期的迟与早，如果date1早于或等于date2则返回TRUE，否则返回FALSE。if(date1.tm_year date2.tm_year)return ERROR;if(date1.tm_mon date2.tm_mon)return ERROR;if(date1.tm_mday date2.tm_mday)return TRUE;return ERROR;/*/*图书管理存储定义*/char *booksMAX_BOOKS;/ 某作者作品数组char authorMAX_NAME_LEN; / 某作者姓名intbooks_counter; / 某作者作品计数typedefstructReaderNode / 借阅者/预约者结点 intcardnum; / 证号charrnameMAX_NAME_LEN; / 姓名unionstructtmbordate; / 借书日期tmretdate; / 还书日期structReaderNode *nextr; / 下一个借阅者指针;structtmbespeakdate; / 预约日期structReaderNode *nextb;/ 下一个预约者指针;ReaderNode,*ReaderType; / 读者类型typedefstructBookNode/ 图书结点