資源簡介
這是數據結構最后的課程設計，我選擇的是用B樹為存儲結構制作一個圖書管理系統，里面還包括實驗報告和用到的資源文件
代碼片段和文件信息
#include?“Library.h“
/********************************B樹接口實現****************************/
int?Search（BTree?p?int?k）?{
//在B樹p中查找關鍵字k的位置i，使得p->node[i].key<=Knode[i+1].key
int?i;
for?（i?=?0;?i?keynum&&p->key[i?+?1]?<=?k;?i++）;
return?i;
}
result SearchBTree（BTree?T?KeyType?k）
//?在m階B樹上查找關鍵字k，返回結果（pt，i，tag）。若查找成功，則特征值tag=1，指針pt
//?所指結點中第i個關鍵字等于k；否則返回特征值tag=0，等于k的關鍵字應插入在pt所指結點
//?中第i和第i+1個關鍵字之間。
{
int i?=?1;
BTree p?=?T?q?=?NULL; //?初始化，p指向待查結點，q指向p的雙親
int found?=?FALSE;
while?（p?&&?!found）
{
i?=?Search（p?k）; //?查找k的位置使p->key[i]<=kkey[i+1]
if?（i>?0?&&?k?==?p->key[i]） found?=?TRUE;
else?{ //?未找到，則查找下一層
q?=?p;
p?=?p->ptr[i];
}
}
if?（found）?{?result r?=?{?p?i?1?}; return?r;?} //?查找成功
else?{?result r?=?{?q?i?0?}; return?r;?} //?查找不成功，返回k的插入位置信息
}
void?split（BTree?&q?int?s?BTree?&ap）?{
//將q結點分裂成兩個結點，前一半保留，后一半移入新結點ap
int?i?n?=?q->keynum;
ap?=?（BTNode*）malloc（sizeof（BTNode））;//生成新結點ap
ap->ptr[0]?=?q->ptr[s];
for?（i?=?s?+?1;?i?<=?M;?i++）?{//后一半移入ap結點
ap->key[i-s]?=?q->key[i];
ap->ptr[i-s]?=?q->ptr[i];
ap->recptr[i?-?s]?=?q->recptr[i];
}
ap->keynum?=?n?-?s;//計算ap的關鍵字個數
ap->parent?=?q->parent;
for?（i?=?0;?i?<=?M?-?s;?i++）?{
if?（ap->ptr[i]）
ap->ptr[i]->parent?=?ap;//將ap所有孩子結點指向ap
}
q->keynum?=?s?-?1;//q結點的前一半保留，修改keynum
}
void?newroot（BTree?&T?BTree?p?int?k?BTree?apRecord?*recptr）?{//生成新的根結點
T?=?（BTNode*）malloc（sizeof（BTNode））;
T->keynum?=?1;
T->ptr[0]?=?p;
T->ptr[1]?=?ap;
T->key[1]?=?k;
T->recptr[1]?=?recptr;??//T的子樹ap的父親指針
if?（p?!=?NULL）?p->parent?=?T;
if?（ap?!=?NULL）?ap->parent?=?T;
T->parent?=?NULL;//新根的雙親是空指針
}
void?Insert（BTree?&q?int?i?int?k?BTree?apRecord?*recptr）?{//k和ap分別插到q->key[i+1]和q->ptr[i+1]
//并插入關鍵字為k的記錄recprt
int?j?n?=?q->keynum;
for?（j?=?n;?j?>?i;?j--）?{
q->key[j?+?1]?=?q->key[j];//關鍵字指針向后移一位
q->ptr[j?+?1]?=?q->ptr[j];//孩子結點指針向后移一位
q->recptr[j?+?1]?=?q->recptr[j];
}
q->key[i+1]?=?k;//賦值
q->ptr[i+1]?=?ap;
q->recptr[i?+?1]?=?recptr;
if?（ap?!=?NULL）?ap->parent?=?q;
q->keynum++;//關鍵字數+1
}
Status?InsertBTree（BTree?&T?KeyType?k?BTree?q?int?i?Record?*rec）
//??在m階B樹T上結點*q的key[i]與key[i+1]之間插入關鍵字K和記錄rec。
//??若引起結點過大，則沿雙親鏈進行必要的結點分裂調整，使T仍是m階B樹。
{
BTree?ap?=?NULL;
int?finished?=?FALSE;
if?（!q）????newroot（T?NULL?k?NULL?rec）; //?T是空樹，生成僅含關鍵字K的根結點*T
else?{
while?（!finished）
{
Insert（q?i?k?ap?rec）; //?將k和ap分別插入到q->key[i+1]和q->ptr[i+1]
if?（q->keynum? else?{
split（q?（M?+?1）?/?2?ap）; //?分裂結點Q
k?=?q->key[（M?+?1）?/?2];
rec?=?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和*ap
newroot（T?q?k?ap?rec）; //?需生成新根結點*Tq和ap為子樹指針
}
return?OK;
}?//??InsertBTree
?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2016-12-17?12:55??楊宇杰_3115005372_實驗四\
?????目錄???????????0??2016-12-17?12:13??楊宇杰_3115005372_實驗四\BTree_Library\
?????目錄???????????0??2016-12-17?12:13??楊宇杰_3115005372_實驗四\BTree_Library\.vs\
?????目錄???????????0??2016-12-17?12:13??楊宇杰_3115005372_實驗四\BTree_Library\.vs\BTree_Library\
?????目錄???????????0??2016-12-17?12:13??楊宇杰_3115005372_實驗四\BTree_Library\.vs\BTree_Library\v14\
?????文件???????38400??2016-12-17?10:45??楊宇杰_3115005372_實驗四\BTree_Library\.vs\BTree_Library\v14\.suo
?????目錄???????????0??2016-12-17?12:13??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\
?????文件????????6022??2016-12-17?12:09??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\BTree_Library.vcxproj
?????文件????????1502??2016-12-17?12:09??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\BTree_Library.vcxproj.filters
?????文件?????????165??2016-12-17?11:08??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\BTree_Library.vcxproj.user
?????文件???????11425??2016-12-17?11:36??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\BTree_Operation.cpp
?????目錄???????????0??2016-12-17?12:13??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\Debug\
?????文件?????????205??2016-12-17?12:11??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\Debug\BTree_Library.log
?????目錄???????????0??2016-12-17?12:13??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\Debug\BTree_Library.tlog\
?????文件?????????202??2016-12-17?12:11??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\Debug\BTree_Library.tlog\BTree_Library.lastbuildstate
?????文件????????1822??2016-12-17?12:11??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\Debug\BTree_Library.tlog\CL.command.1.tlog
?????文件???????66276??2016-12-17?12:11??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\Debug\BTree_Library.tlog\CL.read.1.tlog
?????文件????????4700??2016-12-17?12:11??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\Debug\BTree_Library.tlog\CL.write.1.tlog
?????文件????????1546??2016-12-17?12:11??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\Debug\BTree_Library.tlog\li
?????文件????????3104??2016-12-17?12:11??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\Debug\BTree_Library.tlog\li
?????文件?????????790??2016-12-17?12:11??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\Debug\BTree_Library.tlog\li
?????文件???????52957??2016-12-17?11:36??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\Debug\BTree_Operation.obj
?????文件???????52278??2016-12-17?12:09??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\Debug\Library.obj
?????文件???????45685??2016-12-17?12:11??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\Debug\main.obj
?????文件??????707584??2016-12-17?12:11??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\Debug\vc140.idb
?????文件??????176128??2016-12-17?12:11??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\Debug\vc140.pdb
?????文件????????7626??2016-12-17?12:09??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\Library.cpp
?????文件????????3713??2016-12-17?11:36??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\Library.h
?????文件?????????714??2016-12-17?10:26??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\bookinfo.dat
?????文件???????32000??2009-06-14?01:55??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\borrower.dat
?????文件????????4291??2016-12-17?12:11??楊宇杰_3115005372_實驗四\BTree_Library\BTree_Library\main.cpp
............此處省略15個文件信息
評論
共有 條評論
川公網安備 51152502000135號