数据结构课设电子版部分参考模版.docx
- 文档编号:12165387
- 上传时间:2023-06-04
- 格式:DOCX
- 页数:26
- 大小:500.95KB
数据结构课设电子版部分参考模版.docx
《数据结构课设电子版部分参考模版.docx》由会员分享,可在线阅读,更多相关《数据结构课设电子版部分参考模版.docx(26页珍藏版)》请在冰点文库上搜索。
数据结构课设电子版部分参考模版
目录
1需求分析-1-
2系统设计-2-
2.1数据结构设计-2-
2.2函数设计-2-
2.3关键流程-3-
2.3.1系统主流程-3-
2.3.2查找函数流程-4-
2.3.3插入函数流程-4-
3调试分析-8-
4测试及运行结果-9-
参考文献-10-
附录-11-
1需求分析
2-3树不是一种二叉树,但他的形状满足以下性质:
(1)一个节点包含一个或两个键值
(2)每个内部节点有两个子节点(如果它有一个键值)或三个子节点(如果它有两个键值)
(3)所有叶节点都在树结构的同一层,因此树的高度总是平衡的。
对于每个结点,左子树中所有后继结点的值都小于第一个键的值,而其中间子树中所有结点的值都大于或等于第一个键的值。
如果结点有右子树的话(相应地,结点存储两个键值),那么其中间子树中所有后继结点的值都小于第二个键的值,而其右子树中所有后继结点的值都大于或等于第二个键的值。
同时,同一层的键值从左到右增大。
2-3树的查找方法与二分查找树相似,从根节点出发,如果在根节点找到查找值则查找成功返回,否则根据节点键的规则递归地查找下去,直到找到或返回失败。
在2-3树中插入新值时并不为其开辟一个新的叶子节点来存储,也就是说,2-3树不是向下生长的。
插入算法首先找到一个合适的叶子节点来存放该值,使树的性质不被破坏。
如果该叶子节点只包含一个值(每个节点都最多有两个值),则简单将该值放入叶子节点即可。
如果叶子结点本身已经包含两个值了,则需要为前加入的叶子开辟新的空间。
设节点L为插入节点,但是已经满了,也就是,这个节点因为包含了三个值,所以必须进行分裂,设新分裂出来的节点为L’,则L将存储这三个值中最小的那个值,而L’则存储这三个值中最大的那个。
处于中间的值将得到提升,作为插入值晋升到父节点去。
如果父节点只包含一个键值,该值直接放入节点即可,否则,同样的“分裂-晋升”过程将在该父节点进行,一直递归到根节点为止。
2-3的插入实现中利用了一个函数split,它接收被插入节点的指针和插入的数据,并将指向L'指针和被往上传的值通过引用传回来。
当插入结点已满时便启用这个函数。
从2-3树删除一个节点,有三种可能情况需要考虑:
最简单的情况是,如果删除的值存储在有两个键值的节点上,直接删除该值并不影响树的性质与结构。
如果被删除的值所在的节点只有它一个键值,被删除后该节点将为空,因此通过向兄弟节点借一个记录,并修改父节点来解决。
如果兄弟节点不够借,则需要合并相邻节点,并影响双亲,可能导致树的高度下降。
如果被删除的值是树的内部节点,则将被删除记录用右边子树中的最小键值代替,然后再根据第一、二种情况将该值删除。
第一种情况的实现相当简单,只需要考虑如果删除的是左键值,那么要把右键值移过来而已。
被借的情况由六个不同的转动和合并子程序实现。
2系统设计
2.1数据结构设计
typedefstructTree23Node{//定义2-3树的节点类型
intdatal;//有两个数据域,用来存放节点内数据
intdatar;
Tree23lchild,mchild,rchild;//三个指针域,分别指向左中右三个孩子
}Tree23Node;
2.2函数设计
本系统所设计的函数见表2.1。
表2.1函数列表
函数名称
函数原型
功能描述
main
voidmain();
系统主程序
compare
intcompare(intx,Tree23t);
比较输入数和节点中数的大小关系
createNode
Tree23createNode(intkey);
建立一个新节点
newRoot
voidnewRoot(Tree23*root,intkey,Tree23midSub);
新建一棵2-3树
isleaf
boolisleaf(Tree23root);
判断是否为叶子节点
findNode
Tree23findNode(Tree23root,intkey);
寻找节点
put
voidput(Tree23*root,intkey,Tree23q);
向未满的节点插入一个数
split
voidsplit(Tree23p,int*key,Tree23*q);
对节点的插入操作
del
Tree23del()
删除空节点的具体操作
insert23
voidinsert23(Tree23*root,intkey)
建立2-3树的主要过程
visit
voidvisit(Tree23T)
通过使用“()”分隔层与层
inOrder
voidinOrder(Tree23T)
与visit函数共同作用控制格式
search23
Tree23search23(Tree23root,intkey)
查找一个数在2-3树中的位置
min23
Tree23min23(Tree23root)
找当前树中最小值
deletex
voiddeletex(Tree23t,intkey)
删除节点里的一个数据
leftRotate
voidleftRotate(Tree23&p,Tree23&q,Tree23&r)
将一个数据插入树中的六种情况
leftCombine
voidleftCombine(Tree23&p,Tree23&q,Tree23&r)
将一个数据插入树中的六种情况
middleRotate
voidmiddleRotate(Tree23&p,Tree23&q,Tree23&r)
将一个数据插入树中的六种情况
middleCombine
voidmiddleCombine(Tree23&p,Tree23&q,Tree23&r)
将一个数据插入树中的六种情况
rightRotate
voidrightRotate(Tree23&p,Tree23&q,Tree23&r)
将一个数据插入树中的六种情况
rightCombine
voidrightCombine(Tree23&p,Tree23&q,Tree23&r)
将一个数据插入树中的六种情况
delete23
booldelete23(Tree23*root,intkey)
从树中删除一个数据
2.3关键流程
2.3.1系统主流程
主函数主要保证程序能够多次输入正确的数据,起到开始和停止的作用。
流程图如下。
图2.1
2.3.2查找函数流程
因为2-3树的节点元素与子树上元素的大小上有一定关系,因此,通过指针和查找结点程序的递归调用,实现搜素整个树。
流程图如下
图2.2
2.3.3插入函数流程
在2-3树中插入新值时并不为其开辟一个新的叶子节点来存储,也就是说,2-3树不是向下生长的。
插入算法首先找到一个合适的叶子节点来存放该值,使树的性质不被破坏。
如果该叶子节点只包含一个值(每个节点都最多有两个值),则简单将该值放入叶子节点即可。
如果叶子结点本身已经包含两个值了,则需要为前加入的叶子开辟新的空间。
设节点L为插入节点,但是已经满了,也就是,这个节点因为包含了三个值,所以必须进行分裂,设新分裂出来的节点为L’,则L将存储这三个值中最小的那个值,而L’则存储这三个值中最大的那个。
处于中间的值将得到提升,作为插入值晋升到父节点去。
如果父节点只包含一个键值,该值直接放入节点即可,否则,同样的“分裂-晋升”过程将在该父节点进行,一直递归到根节点为止。
往2-3树中插入元素和往二叉查找树中插入元素一样,首先要进行查找,然后将节点挂到未找到的节点上。
2-3树之所以能够保证在最差的情况下的效率的原因在于其插入之后仍然能够保持平衡状态。
如果查找后未找到的节点是一个2-node节点,那么很容易,我们只需要将新的元素放到这个2-node节点里面使其变成一个3-node节点即可。
但是如果查找的节点结束于一个3-node节点,那么可能有点麻烦。
图2.3
往一个3-node节点插入一个新的节点可能会遇到很多种不同的情况,下面首先从一个最简单的只包含一个3-node节点的树开始讨论。
图2.4
如上图,假设2-3树只包含一个3-node节点,这个节点有两个key,没有空间来插入第三个key了,最自然的方式是我们假设这个节点能存放三个元素,暂时使其变成一个4-node节点,同时他包含四个子节点。
然后,我们将这个4-node节点的中间元素提升,左边的节点作为其左节点,右边的元素作为其右节点。
插入完成,变为平衡2-3查找树,树的高度从0变为1。
对于节点是3-node,父节点是2-node,和第一种情况一样,我们也可以将新的元素插入到3-node节点中,使其成为一个临时的4-node节点,然后,将该节点中的中间元素提升到父节点即2-node节点中,使其父节点成为一个3-node节点,然后将左右节点分别挂在这个3-node节点的恰当位置。
操作如下图:
图2.5
对于节点是3-node,父节点也是3-node,当我们插入的节点是3-node的时候,我们将该节点拆分,中间元素提升至父节点,但是此时父节点是一个3-node节点,插入之后,父节点变成了4-node节点,然后继续将中间元素提升至其父节点,直至遇到一个父节点是2-node节点,然后将其变为3-node,不需要继续进行拆分。
图2.6
当根节点到字节点都是3-node节点的时候,这是如果我们要在字节点插入新的元素的时候,会一直查分到跟节点,在最后一步的时候,跟节点变成了一个4-node节点,这个时候,就需要将跟节点查分为两个2-node节点,树的高度加1,这个操作过程如下:
图2.7
3调试分析
主要撰写在调试中遇到的典型问题及解决方法,可以按如下格式写。
(1)键盘缓存区问题
●问题描述:
在读入键盘输入的数字时,多次读入回车符,导致程序无找到应该插入的位置,从而导致程序错误退出。
●问题分析:
输入时没有清除键盘缓存区,在反复读取时容易产生问题。
●解决方法:
每次输入数字之前加入一条清除键盘缓存区的指令。
(2)无法表示节点之间关系问题
●问题描述:
用“,”分隔节点非常混乱,不利于辨别层与层之间的关系
●问题分析:
“,”虽然有分隔的作用,但是没有包络的作用,无法完成层次的区分
●解决方法:
改用“()”和“,”
4测试及运行结果
图4.1
图4.2
参考文献
[1]严蔚敏,吴伟民.数据结构(c语言版).北京:
清华大学出版社,1997
[2]
[3]
[3]
[4]章节2.3.3中流程图来自
附录
源程序文件名清单:
iostream.h//标准输入输出流
stack.h//栈操作的头文件
源.cpp//源代码
源程序清单:
#include
#include
usingnamespacestd;
typedefstructTree23Node*Tree23;
typedefstructTree23Node{
intdatal;
intdatar;
Tree23lchild,mchild,rchild;
}Tree23Node;
#defineINT_MAX0x3f3f3f3f
stack
intcompare(intx,Tree23t)
{
if(x
return1;
elseif(x>t->datar)
return3;
elseif(x
return2;
else
return4;
}
Tree23createNode(intkey)
{
Tree23t=newTree23Node;
t->datal=key;
t->datar=INT_MAX;
t->lchild=t->mchild=t->rchild=NULL;
returnt;
}
voidnewRoot(Tree23*root,intkey,Tree23midSub)
{
Tree23t=createNode(key);
t->lchild=*root;
t->mchild=midSub;
*root=t;
}
boolisleaf(Tree23root)
{
if(root&&root->datal
root->mchild==NULL&&root->rchild==NULL)
returntrue;
returnfalse;
}
Tree23findNode(Tree23root,intkey)
{
Tree23t=NULL;
while(root){
if(!
isleaf(root))
s.push(root);
if(isleaf(root))
t=root;
switch(compare(key,root)){
case1:
root=root->lchild;
break;
case2:
root=root->mchild;
break;
case3:
root=root->rchild;
break;
case4:
returnNULL;
}
}
returnt;
}
voidput(Tree23*root,intkey,Tree23q)
{
if(key<(*root)->datal){
(*root)->datar=(*root)->datal;
(*root)->datal=key;
(*root)->rchild=(*root)->mchild;
(*root)->mchild=q;
}
else{
(*root)->datar=key;
(*root)->rchild=q;
}
}
voidsplit(Tree23p,int*key,Tree23*q)
{
Tree23t=createNode(INT_MAX);
if(*key
t->datal=p->datar;
/*swap*keyandp->datal*/
p->datar=*key;
*key=p->datal;
p->datal=p->datar;
/*setp->datartononsense*/
p->datar=INT_MAX;
}
elseif(*key>p->datar){
t->datal=*key;
*key=p->datar;
p->datar=INT_MAX;
}
else{
t->datal=p->datar;
p->datar=INT_MAX;
}
t->lchild=p->rchild;
p->rchild=NULL;
t->mchild=*q;
*q=t;
}
Tree23del()
{
if(!
s.empty()){
Tree23t=s.top();
s.pop();
returnt;
}
returnNULL;
}
voidinsert23(Tree23*root,intkey)
{
Tree23p,q,temp;
if(*root==NULL){
/*treeisempty*/
newRoot(root,key,NULL);
}
else{
/*insertintoanemptytree*/
p=findNode(*root,key);
if(p==NULL){
cout<<"Thekeyiscurrentlyinthetree."< return; } q=NULL; for(;;){ if(p->datar==INT_MAX){ /*twosubnode*/ put(&p,key,q); break; } else{ /*threesubnode*/ split(p,&key,&q); if(p==*root){ /*splittheroot*/ newRoot(root,key,q); break; } else /*removeanodefromstack*/ p=del(); } } } } voidvisit(Tree23T) { if(T->datar cout<<"("< } elseif(T->datal cout<<"("< } elsecout<<"(,)"; } voidinOrder(Tree23T) { if(T) { visit(T); //cout< if(T->lchild==NULL) return; cout<<"("; inOrder(T->lchild); cout<<","; inOrder(T->mchild); cout<<","; inOrder(T->rchild); cout<<")"; } } Tree23search23(Tree23root,intkey) { while(root){ s.push(root); switch(compare(key,root)){ case1: root=root->lchild; break; case2: root=root->mchild; break; case3: root=root->rchild; break; case4: returnroot; } } returnNULL; } Tree23min23(Tree23root) { while(root->lchild){ s.push(root); root=root->lchild; } s.push(root); returnroot; } voiddeletex(Tree23t,intkey) { /*deletekeyfromnodet*/ if(key==t->datal){ /*deletefirstkey*/ if(t->datar /*threesubnode*/ t->datal=t->datar; t->datar=INT_MAX; } else /*twosubnode*/ t->datal=INT_MAX; } else /*deletesecondkey*/ t->datar=INT_MAX; } voidleftRotate(Tree23&p,Tree23&q,Tree23&r) { p->datal=r->datal; r->datal=q->datal; q->datal=q->datar; q->datar=INT_MAX; p->mchild=q->lchild; q->lchild=q->mchild; q->mchild=q->rchild; q->rchild=NULL; } voidleftCombine(Tree23&p,Tree23&q,Tree23&r) { p->datal=r->datal; p->datar=q->datal; p->mchild=q->lchild; p->rchild=q->mchild; deleteq; if(r->datar==INT_MAX){ /*ristwosubnode*/ r->datal=INT_MAX; r->mchild=NULL; } else{ r->datal=r->datar; r->datar=INT_MAX; r->mchild=r->rchild; r->rchild=NULL; } } voidmiddleRotate(Tree23&p,Tree23&q,Tree23&r) { p->datal=r->datal; r->datal=q->datar; q->datar=INT_MAX; p->mchild=q->rchild; q->rchild=NULL; } voidmiddleCombine(Tree23&p,Tree23&q,Tree23&r) { q->datar=r->datal; q->rchild=p->lchild; deletep; if(r->datar r->datal=r->datar; r->datar=INT_MAX; r->mchild=r->rc
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 电子版 部分 参考 模版