范文一:构造平衡二叉排序树
构造平衡二叉排序树
程序如下:
#include"stdio.h"
#include"stdlib.h"
typedef int KeyType;
typedef struct node
{KeyType key;
struct node *lchild,*rchild;
}BSTNode;
typedef BSTNode *BSTree;
BSTree CreateBST(void);
void DelBSTNode(BSTree *Tptr,KeyType Key); void InorderBST(BSTree T);
void InsertBST(BSTree *bst,KeyType key); main()
{BSTree T;
char ch1,ch2;
KeyType Key;
printf("建立一棵二叉排序树的二叉链表存储\n"); T=CreateBST();
ch1='y';
while (ch1=='y'||ch1=='Y')
{printf("请选择下列操作:\n");
printf("1------更新二叉树上的存储\n"); printf("2------二叉排序树上的删除\n"); printf("3------二叉排序树中序输出\n"); printf("4------退出\n");
scanf("\n%c",&ch2);
switch(ch2)
{case '1':T=CreateBST();break;
case '2':printf("\n请输入要删除的数据:"); scanf("\n%d",&Key);
DelBSTNode(&T,Key);
printf("删除操作完毕.\n");break;
case '3':InorderBST(T);
printf("\n二叉排序树输出完毕.\n"); break;
case '4':ch1='n';break;
default:ch1='n';
}
}
}
void InsertBST(BSTree *bst,KeyType key) {BSTree s;
if(*bst==NULL) /*递归结束条件*/ {s=(BSTree)malloc(sizeof(BSTNode)); /*申请新的结点*/
s->key=key;
s->lchild=NULL;
s->rchild=NULL;
*bst=s;
}
else
if(key<(*bst)->key)
InsertBST(&((*bst)->lchild),key); /*将S插入左子树*/
else
if(key>(*bst)->key)
InsertBST(&((*bst)->rchild),key); /*将S插入右子树*/
}
BSTree CreateBST(void)
{BSTree T;
KeyType Key;
T=NULL;
printf("请输入一个关键字(输入0时结束输入):\n");
scanf("%d",&Key);
while(Key)
{InsertBST(&T,Key);
printf("请输入下一个关键字(输入0时结束输入):\n");
scanf("\n%d",&Key);
}
return T;
}
void DelBSTNode(BSTree *T,KeyType Key) {BSTNode *parent=NULL,*p,*q,*child;
p=*T;
while(p)
{if(p->key==Key) break;
parent=p;
p=(Key } if(!p) {printf("没有找到要删除的结点\n");return;} q=p; if(q->lchild && q->rchild) for(parent=q,p=q->rchild;p->lchild;parent=q,p=p->lchild); child=(p->lchild)?p->lchild:p->rchild; if(!parent) *T=child; else {if(p==parent->lchild) parent->lchild=child; else parent->rchild=child; if(p!=q) q->key=p->key; } free(p); } void InorderBST(BSTree T) {if(T!=NULL) {InorderBST(T->lchild); printf("%5d",T->key); InorderBST(T->rchild); } } 实验结果: 建立二叉检索树并输入数据: 输出数据:(二叉检索树中序输出) 删除二叉检索树中的一个点: 最后的输出结果:(二叉检索树中序输出) 严格平衡二叉排序树及其构造 严格平衡二叉排序树及其构造 岑岗周炳生 (浙江科技学院,杭州310023) E—mail:gcen@zust.edu,ca 摘要论文对一直沿用至今的平衡二叉树和平衡二叉排序树概念的合理性提出质 疑,给出了二叉树结点的严格平衡 因子和严格平衡二叉树及严格平衡二叉排序树的新概念.论文给出的构造严格平 衡二叉排序树的递归算法及二叉排序 树元素插入和删除的严格平衡化过程比动态构造平衡二叉排序树的传统Adelson —Velskii和Landis算法更加简单而 自然. 关键词严格平衡因子严格平衡二叉树严格平衡二叉排序树平衡因子平衡二叉树 平衡二叉排序树 文章编号1002—8331-(2005)13—0057—04文献标识码A中图分类号TP311 StrictBalancedBinarySortTreeanditsConstruction CenGangZhouBingsheng (Zh~iangUniversityofScienceandTechnology,Hangzhou310023) Abstract:Inthispaperreasonablenessoftheconceptofthebalancedbinarytreeandthebalancedbinarysorttree uptonowingeneralusehasbeencalledinquestion,andnewconceptofstrictbalancefactor,strictbalancedbinary treeandstrictbalancedbinarysorttreehasbeenpresented.Inthispapergivenrecursivealgorithmofconstructingthe strictbalancedbinarysorttreeandprocessofstrictbalancingunderinsertinganddeletingelementinthebinarysort treearemoresimpleandnaturalthantraditionalAdelson-Velskii&Landisalgorithmof dynamicconstructingthe balancedbinarysorttree. Keywords:strictbalancefactor,strictbalancedbinarytree,strictbalancedbinarysorttree,bal ancefactor,balancedbinary tree,balancedbinarysorttree 1问题的提出 至今,人们都认为平衡二叉树是形态最平衡的二叉树,而 平衡二叉排序树作为动态查找表的一种存储结构一直被认为 其查找的时间复杂度是最优的.然而,事实并非如此.下面随便 举的两个例子表明:平衡二叉树并非真正平衡(图1),而平衡 二叉排序树用于查找的时间效率并不能达到静态查找表二分 查找的时问效率(图2).' 图1不平衡的平衡二叉树 图2查找效率并非最优的平衡二叉排序树 动态构造平衡二叉树和平衡二叉排序树的传统算法(称之 谓Adelson—Velskii和Landis算法)过于繁琐而难于接受.那么 是否存在比平衡二叉树和平衡二叉排序树更加平衡的二叉树 和二叉排序树呢?是否存在比构造平衡二叉树和平衡二叉排序 树的传统算法更加简单,更加自然的算法呢?这是作者一直在 思索的问题,而论文的结果正是对上述两个问题的正面回答. 2严格平衡二叉树和严格平衡二叉排序树 有关二叉树结点的平衡因子和平衡二叉树及平衡二叉排 序树的概念在文献中都有定义,这里不再重复.本节给出的是 论文提出的几个新概念的定义及主要结果. 定义1二叉树结点的严格平衡因子sbf(ki)是其左子 树的结点个数lc(ki)与右子树的结点个数rc(后)之差,即: sbf(ki)=()一rc(ki) 定义2若二叉树的所有结点ki(i=l,2,3……,n)的严格 平衡因子的绝对值Isbf(ki)l?1,则称该二叉树是严格平衡二叉 树.空二叉树通常被认为是严格平衡二叉树. 定义3若二叉排序树是严格平衡二叉树,则称该二叉排 序树是严格平衡二叉排序树. 引理深度为d的严格平衡二叉树的前d一1层的结点个数 为'1,即深度为d的严格平衡二叉树的前d一1层结点构成 满二叉树. 证明对严格平衡二叉树的深度用数学归纳法.d=l时,严 作者简介:岑岗(1959一),男,副教授,高级工程师(双职称),长期从事计算机基础教 育工作.周炳生(1939-),男,副教授,主要研究计算机软件技 术,应用软件. 计算机工程与应用2oo5.1357 格平衡二叉树只有一个根结点,其前d一1层的结点个数为O, 而2一一1=21=0,故引理显然成立.假设d=k时引理成立,证 明d--k+1时引理亦成立. 深度为+1的严格平衡二叉树,其根结点r的左子树 和右子树RT中至少有一棵是深度为k的严格平衡二叉树,不 失一般性,不妨设根r的左子树的深度为k.根据归纳假设, LT的前k-1层的结点个数ln=2k-l_1,而LT的结点个数lc>ln, 所以2.现对根r的右子树RT的形态分两种情况讨论: (1)尺的深度吐.设尺的结点个数为I'C,因为尺的深 度吐,所以有: rc<-- 2一1(1) (不等式的右端是深度为k-1的满二叉树的结点个数).因 为的根r的严格平衡因子的绝对值Isbf(r)I?1,即: 一 1/C--re?1(2) 但/c2,rc--<21,所以有: _rc2一(2一1):1(3) 由(2)和(3)得lc-rc=l,所以有: rc:一12?一 1(4) 由(1)和(4)得rc=2一一1.此式表明:根r的右子树尺必 定是深度为k-1的满二叉树,附带也说明左子树的第k层 只有一个结点.这时的前k层结点个数为: ln+rc+1:(2一1)+(2一1)+1:2一1 即引理当d=k+1时亦成立. (2)RT的深度.根据归纳假设,RT的前k-1层的结点个 数rn=2一一1,所以的前k层的结点个数为: ln+rn+1:(2一1)+(2一1)+1:2一1 即引理当d=k+1时亦成立. 综合以上(1)和(2)两种情况,证明了引理的正确性. 定理1结点个数为n的严格平衡二叉树的深度d由下列 公式确定: d=Flog2(n+1)](或d=[1og2(n+1)j) 严格平衡二叉树的深度公式与完全二叉树的深度公式相 同.尽管二者是完全不同的概念,其应用的领域也不相同,但它 们有一个共性,即其前d一1层结点都构成满二叉树,从而导致 其证明方法完全相同,有关证明请参阅文献,这里从略. 定理2严格平衡二叉树一定是平衡二叉树. 证明对严格平衡二叉树的结点个数用数学归纳法.n=l 时,严格平衡二叉树只有一个根结点r,其平衡因子bf(r)=O,所 以是平衡二叉树.n=2时,严格平衡二叉树只有以下两种形态: Q\\() 其根结点的平衡因子分别为1和一1,所以它们都是平衡二 叉树. 假设n?时严格平衡二叉树是平衡二叉树,证明当n=+ 1时严格平衡二叉树是平衡二叉树.根据归纳假设,显然只 需证明的根r的平衡因子的绝对值I(r)I?1即可.按k+l 的奇偶性,分以下两种情况讨论: (1)k+l为奇数,设k+l=2m+l.因为的根r的严格平衡 因子的绝对值Isbf(r)l?1,所以r的左子树LT的结点个数lc和 右子树RT的结点个数I'C必须相等,即lc=rc=m<k.由定理1得: 5820D5.13计算机工程与应用 LT的深度Id=Flog2(m+1)] 尺的深度rd=[1og2(m+1)] 即/d=rd,所以根r的平衡因子~r)--O. (2)k+l为偶数,设k=2m.因为的根r的严格平衡因子 的绝对值Isbf(r)I?1,故其左,右子树和尺的结点个数只 能相差1.不失一般性,不妨设LT的结点个数/c=m-1,RT的结 点个数I'c=m.由定理1得: LT的深度/d=[1og~n3 尺的深度rd=Flog2(m+1)] 则必有rd=Id,否则与引理矛盾.若 若不是满二叉树, 是满二叉树,则必有rd=Id+1.这表明,当k+l为偶数时,严 格平衡二叉树的根r的左,右子树的深度最多相差J,即根r 的平衡因子的绝对值Ibf(r)l?1. 综合以上(1)和(2)两种情况,定理2得证. 平衡因子和严格平衡因子是二叉树的形态特性,而与二叉 树的结点信息无关,所以下述定理3和定理4显然成立. 定理3结点个数为n的严格平衡二叉排序树的深度d由 下列公式确定: d=Flog2(n+1)](或d=Llog2nj+1) 定理4严格平衡二叉排序树一定是平衡二叉排序树. 定理2和定理4表明:严格平衡二叉树和严格平衡二叉排 序树是要求更加严格的平衡二叉树和平衡二叉排序树. 3严格平衡二叉排序树的构造 从二叉排序树构造严格平衡二叉排序树主要是通过称之 谓二叉排序树的转换(函数bst_translation)和严格平衡二叉排 序树的构造(函数sbbst_construction)完成二叉排序树的严格平 衡化. (1)二叉排序树结点类型的定义 typedefstructsomef intdam; structsome*lch,*rch; }bstnode; (2)两个辅助函数(二叉排序树结点的计数和删除二叉排 序树) intbstnode_count(bstnodep)f if(p==O) return0; elseretumbstnode_count(p->lch)+ bstnode_count(p->rch)+1; } voidbst_free(bstnodep)f if(p!--o)f bst_free(p->lch); bst_free(p-->rch); free(p); } } (3)基于中序遍历,把二叉排序树转换成递增有序顺序表 voidbst_translation(bsmodep,inta)f staticinti: if(p!--o)f bst_translation(p->lch,a); (a+i++)=p一>data; bst_mmslation(p-->rch,a); 】 ) (4)基于二分法,按后序方式构造严格平衡二叉排序树 bstnode*sbbst_construction(inta,intl,inth)( bstnodeP; if(1>h) l'etlll~0; else( p=(bstnode)malloc(sizeof(bstnode)); p->data=(a+(I+h)/2); p->lch=sbbst_ construction(a,l,(1+h)/2—1); p->rch=sbbst_ construction(a,(1+h)/2+1,h); returnP; J ) (5)二叉排序树的严格平衡化过程 bstnode*bst_ sbbst(bstnoder)f intn,a: n=bstnode—count(r); a=(int*)mall~(n*sizeof(int)); bst_translation(r,a); bsLfree(r); r=-sbbsLconstruction(a,0,n一1); free(a); retrunr; ) 4严格平衡二叉排序树元素的插入和删除 作者给出的严格平衡二叉排序树元素的插入和删除算法 通过称之谓插入转换(函数insert_translation)和删除转换(函数 delete—translation)直接构造二叉排序树插入和删除元素后的严 格平衡二叉排序树,无须在二叉排序树中先插入和删除元素而 后再构造严格平衡二叉排序树,也无须额外增加二叉排序树结 点的信息域. (1)基于中序遍历,把插入元素的二叉排序树转换成递增 有序顺序表 voidinsert_translation(bstnodep,inta)( staticinti,flag; if(p!--O)( insert_translation(p一>lch,a); if(flag==lll(a+i)<p->data)( fa+.+1)=p->data; i++: if(flag!=1)flag=l; )else( (a+.+1)=(a+1); (a+i++)=p一>dat; ) insert_translation(p一>rch,d); ) ) (2)从插入元素的二叉排序树构造严格平衡二叉排序树 bstnodeinsert_ construction(bstnoder,intx)f intn,a; n=bstnode_count(r); a=(int)malloc((n+1)sizeof(int)); *amx; insert_translation(r,a); bstfree(a); r=-sbbst_construction(a,0,n); free(a); l~tumr; 】 (3)基于中序遍历,把删除元素的二叉排序树转换成递增 有序顺序表 intdelete_translation(bstnodep,inta)( staticinti,flag; if(p=--O) returnO: elsef delete_translation(p一>lch,a); if(flag==1)( fa+i+1)=p-->data; i++: )elseif((a+i)==p->data)( flag=l; im; )else( 木(a+i+1)=(a+i); 木(a+i++)=p一>data; ) delete_translation(p->rch,a); returnflag; J J 函数delete_translation的返回值指示二叉排序树是否存在 删除的元素. (4)从删除元素的二叉排序树构造严格平衡二叉排序树 bstnode*delete_ construction(bstnoder,intx)f intn,幸a,flag; n=bstnode_count(r); a=(int)malloe((n+1)*sizeof(int)); }a=X: flag=delete_translation(r,a); bst_free(r); if(flag==1) r=-sbbsLconstruction(a,0,n一2); else r=-sbbst_construction(a,0,n-1); free(a); returnr; ) 二叉排序树删除元素的平衡化过程尚未见之于文献,而这 里给出的二叉排序树删除元素的严格平衡化过程如同插入元 素的严格平衡化过程一样简单. 以上程序中数据元素的类型指定为int,这只是为了表述 的简单和直观.利用C++语言的类属机制,可以设计适用于任 何数据元素类型的通用的严格平衡二叉树类属类,使之成为包 容数据结构;或者为严格平衡二叉排序树的构造,插入和删除 操作设计独立的类属函数. 5结论 由论文给出的严格平衡二叉树和严格平衡二叉排序树的 定义及有关定理,可以得到以下两个重要结果. 计算机工程与应用2005.1359 性质l有rt个结点的所有二叉树中,严格平衡二叉树的 深度最小,与完全二叉树的深度相等,而平衡二叉树未必能取 该最小值. 性质2有rt个结点的所有二叉排序树中,严格平衡二叉 排序树查找的最坏时间复杂度最小,为:WorstTime(rt)=~-log2 (n+1)]. 而查找成功的等概率平均查找长度为: _1蚀.fR+l11 A观…:二二 …'rt 后者就是静态查找表二分查找的平均查找长度,可以从引 理和定理l推导而得,这里从略. 由此认为:从二叉树的形态来看,严格平衡二叉树才是真 正平衡的二叉树,而平衡二叉树未必真正平衡;从二叉排序树 用于查找的时间复杂度分析,严格平衡二叉排序树作为动态查 找表的存贮结构,其查找的时间复杂度与静态查找表二分查找 的时间复杂度相同,而平衡二叉排序树用于查找的时间效率未 必很理想. 尽管构造严格平衡二叉排序树递归算法的简洁性以增加 辅助存贮空问和元素复制为代价,但由于采用了动态存贮分配 的程序设计方法,从而最大限度地减少了对辅助存贮空间的需 求.考虑到严格平衡二叉树和严格平衡二叉排序树的概念比平 衡二叉树和平衡二叉排序树完美,而其构造算法远比构造 AVL树的传统算法简单而自然.(收稿日期:2004年lO月) 参考文献 1.严蔚敏等.数据结构【M].第二版,,北京:清华大学出版社,1992:237,241 2.唐策善等.数据结构一用C语言描述[MI.北京:高等教育出版社, 1995:201-207 3.CollinsWJ.影印版:数据结构与STL[M].北京:机械工业出版社. 2003:353,380 4.李师贤等.面向对象程序设计基础【M】.北京:高等教育出版社,1998: 274-287 (上接9页) (2)系统性能分析 由于每个中间洋葱路由器在转发洋葱包时,首先用所在组 的组管理实体ME的公钥对洋葱包中的和签名SignMEj ()进行验证,及时发现和丢弃伪造的洋葱包,提高了系统的 性能.将洋葱路由器实行分组管理,可以使洋葱路由器在验证 洋葱包时,不必使用所有的ME的公钥去验证和签名sign. MEi(),直接用所在组的MEj的公钥进行验证即可,减少了系 统附加管理开销. 另外,该模型中路径的选择与洋葱路由原型系统中的路径 选择是一致的,代理洋葱路由器可以在所有的洋葱路由器中随 机进行选择,因此,洋葱路由器的分组并不影响该模型的匿名 性能.当在同一组内选择两个以上的洋葱路由器时,在封装洋 葱包时包人相同的和SignMEj()U为组编号)即可. 4结论 匿名通信系统不仅要考虑保护信息系统的安全,又要防止 匿名的滥用;既要保证匿名的健壮性,又要保证系统应用的可 行性.因此,可控匿名通信技术的研究是非常必要的.论文对此 问题给出了一些探讨,提出了一个基于洋葱路由技术的可撤销 匿名通信模型,在保持与原洋葱路由系统相当的匿名性能的同 时可以及时发现和丢弃伪造的洋葱包,对匿名滥用者的IP进 行追踪. 进一步的工作包括:(1)根据论文提出的方法,研究基于P2P 的匿名原型系统的可控制性;(2)研究匿名系统的信誉度机制, 给出一个匿名系统的匿名性能和效率的折衷模型,供用户选择. (收稿日期:2005年3月) 参考文献 1.赵福祥,王育民等.可靠洋葱路由方案的设计与实现【J】.计算机, 2001;24(5):463—|67 2.王伟平.陈建二,王建新.基于组群的有限路长匿名通信协议【J】.计算 机研究与发展,2003;4o(4):609-614 3.SharadGoel,MarkRobson,MiloPolteeta1.Herbivore:AScalable andEfficientProtocolforAnonymousCormnunication[Mq.TR2003-1890, CoroellUniversity,2003-02 4.BrianNeilLevine,MichaelReiter,ChenxiWangeta1.StoppingTim- 602005.13计算机工程与应用 ingAttacksinI删一LatencyMix—BasedSystems[C].In:PrecFinancial Cryptography,2004-02 5.DavidM"Rai'hi,DavidPointcheva1.DistributedTrusteesandRevoca— bility:AFrameworkforInternetPayment[C】.In:FinancialCryptography, 1998:28--42 6.FZhang.FTZhang.YWang.Fairelectroniccashsystemswithmul— tiplebanks[C].In:SEC:~2000,Kluwer,2000:461,470 7.GDavida,YFrankel,YTsiouniseta1.AnonymitycontrolinE-cash systems[C].In:RdoclHirsehfelded.FinancialCryptography:FirstInter- nationalConference,FC07,volume1318ofLectureNotesinCom- puterScience,Anguilla,BritishWestIndies,Springer-Verlag,1997: 1,16 8.CamenischJ,MaurerU,StadlerM.Distalpaymentsystemswithpas— siveanonymity—revokingtrostee~C].In:BertinoEetaleds.LectureNotesin ComputerScience,1146,Berlin:Springer—Verlag,1996:33-43 9.TSander.ATa-Shma.Flowcontrol:Anewapproachforanonymity controlinelectroniccashsystems[C]Jn:proceedingsofFinancialCryp- tography'99,ForthcomingvolumeinLectureNotesinComputerScience, 1999 10.JorisClaessens,ClaudiaDtaz,CarolineGoelnanseta1.Revocable anonymousaccesstotheInternet[J].JournalofInteroetResearch: ElectronicNetworkingApplicationsandPolicy,2003;13(4):242-258 11.JanCamenisch.EfficientAnonymousFingerprintingwithGroupSig- natures[C].In:AdvancesinCryptology—Asiacrypt2000,volume1976 ofLNCS,SpringerVerlag,2000:415-428 12.FBao,RHDeng.AnewtypeofMagicInksignatures-Towards transcript—irrelevantanonymityrevocation[C].In:PKC'99,LNCS1560, Springer-Verlag,1999:1-11 13.YanWang,ShuwangLu,ZhenhuaLiu.ASimpleAnonymousFinger- printingSchemeBasedonBhndSignature[C].In:InformationandCom- municafionsSecurity(ICICS03),LNCS2836,Springer—Verlag,2003: 260,268 14.吴振强,杨波.追踪洋葱包的高级标记方案与实现叨.通信,2002; 23(5):96-102 15.GoldschlagD,ReedM,SyversonP.Onionroutingforanonymousand privateInteroetconnections[J].CommunicationsoftheACM,1999;42 (2):39-41 16.AShamir.Howtoshareasecret[J].CormnunicationsofACM,1979; 22:612,613 课程设计任务书 学生姓名: 专业班级 班 指导教师: 夏红霞 工作单位: 计算机科学与技术学院 题 目: 二叉排序树的构造与运算 课程设计要求: 1、熟练掌握基本的数据结构; 2、熟练掌握各种算法; 3、运用高级语言编写质量高、风格好的应用程序。 课程设计任务: 1、系统应具备的功能: (1)建立二叉排序树 (2)中序遍历二叉排序树并输出排序结果 2、数据结构设计; 3、主要算法设计; 4、编程及上机实现; 5、撰写课程设计报告,包括: (1)设计题目; (2)摘要和关键字; (3)正文,包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、 不足之处、设计体会等; (4)结束语; (5)参考文献。 时间安排: 2010年7月5日-9日 (第19周) 7月5日 查阅资料 7月6日 系统设计,数据结构设计,算法设计 7月7日 -8日 编程并上机调试 7月9日 撰写报告 7月10日 验收程序,提交设计报告书。 指导教师签名: 2010年7月4日 系主任(或责任教师)签名: 2010年7月4日 二叉排序树的构造与运算 摘要:该程序主要部分有:①数据的输入;②将输入的数据构造成一个二叉排序树;③将构造好的二叉排序树用中序遍历的方法输出;④用中序遍历输出最终结果。 关键字:二叉排序树、中序遍历、数据的输入输出 1. 引言:现今,数据的排序过程在很多方面都有运用,大量数据的排序在很多行业都有很大的作用,二叉排序树能更为直观的表现排序过程,而用中序遍历二叉排序树的结果就是一组由小到大依次排列的数据,此过程能检验构造二叉排序树的过程是否正确。 2. 需求分析:①二叉排序树能直观的反映排序的过程,能更好的解释排 序过程;②大量数据的排序过程在多个行业都有广泛的应用;③用户能通过中序遍历的过程检测排序是否正确。 3. 数据结构设计 typedef struct bnode { int data; s truct bnode *left , *right ; } btree ; //构造一个二叉树 4. 算法设计 4.1输入数据建立一个二叉树 void creatTree(btree **b) { int x ; btree *s ; *b = NULL ; while(x !=0 ) { printf("请输入数据(输入0结束) : "); scanf("%d",&x); if(x!=0) { s = (btree *)malloc(sizeof(btree)) ; s->data = x ; s->left = NULL ; s->right = NULL ; insert( b , s ); } else break; } } 4.2与4.1相结合构造一个二叉排序树 void insert(btree **b , btree *s) { if(*b==NULL) *b = s ; else if((*b)->data == s->data) insert(&(*b)->left , s); else if(s->data > (*b)->data) insert(&(*b)->right , s); else if(s->data < (*b)-="">data) insert(&(*b)->left , s); } 4.3按中序遍历的顺序输出二叉排序树 void Print(btree * p) { if(p!=NULL) { Print(p->left); printf( "%d",p->data); if(p->left!=NULL) printf( "\t %d 的左结点:%d ",p->data,p->left->data); else printf( "\t %d 的左结点=NULL",p->data); if(p->right!=NULL) printf( "\t %d 的右结点:%d ",p->data,p->right->data); else printf( "\t %d 的右结点=NULL",p->data); printf( "\n"); Print(p->right); } } void InOrder(btree *b) { if (b!=NULL) { InOrder(b->left ); printf("%d ",b->data); InOrder(b->right ); } } 5. 程序运行结果 5.1 该程序可输入任意个数的数据,输入一个数据后点击ENTER 输入下一个,直到输入为0为止。 5.2 输入完毕后程序自动运行建立二叉排序树并用中序遍历的方式输出结果。 6. 设计体会 这个实验与其他实验相比相对简单,不需要写出界面实现功能也较少,所以报告不多。但我觉得这个实验是非常贴近数据结构所讲的内容,实验中充分运用了二叉树、二叉排序树、中序遍历等我们在数据结构课上讲到的概念,将他们运用到实际问题中,不仅能让算法过程更加清晰,还能更简单的将问题得到解决。我觉得这个实验是将课堂学习与实践结合在一起的直接例子,让我知道课本上的知识是如何在实际中运用的。 同时,通过这次课程设计,我读了一些书籍,对数据结构有了更多的了解,对C 语言的编程也有了新的体会。我还了解到算法对程序设计的重要性,好的算法能写出更高效的程序,编码过程也更加轻松。 参考文献: [1] 严蔚敏 吴伟民 编著 《数据结构》 清华大学出版社 2001年1月 [2] 高一凡 编著 《数据结构》算法实现及解析 西安电子科技大学出版社 武汉理工大学《数据结构》课程设计说明书 二叉排序树的构造与运算 摘要:该程序主要功能有:可由用户选择自己输入数据或由机器随机生成数据,生成数据后存储于数组中;将数组中的数值作为结点的关键字建立二叉排序树; 中序遍历二叉排序树并输出排序结果;还有退出程序的功能。 关键字:二叉排序树 (Binary Sort Tree) 插入结点 (Inserting Knot) 中序遍历 (Inorder Traversaling) 0 引言 实际生活中,我们会经常遇到需要对大量无序的数据序列进行排序的情况。排序的方法有很多,而利用二叉排序树对无序序列进行排序也是常用的方法。由于二叉排序树其独特的结构特点,中序遍历二叉排序树即可得到一个关键字的有序序列,而构造树的过程即是对无需序列进行排序的过程。 1 需求分析 由机器产生随机数,对机器产生的随机数进行存储,或由用户输入数据,对用户输入的数据进行存储;将所存储的数据作为关键字,用向空树中不段插入结点的方法建立二叉排序树;将所建立的二叉排序树中序遍历输出;退出程序等。 2 数据结构设计 typedef int KeyType;/*二叉排序树中的数据元素的类型,即用户输入的数据类 型为整型*/ static int num[100];/*用于存储用户输入的数据或由机器随机生成的数据*/ typedef struct BinSTreeNode /*定义二叉排序树结点的存储结构*/ { KeyType key; 1 武汉理工大学《数据结构》课程设计说明书 BinSTreeNode *lchild; BinSTreeNode *rchild; }BinSTreeNode; 3 算法设计及实现 3.1 用户输入数据函数 此函数的功能:提示用户输入数据的个数及输入具体的数据值,用全局变量数组存储其数值,以便之后的函数能直接调用已经改变的数组的值;并提示用户输入的数据个数不超过100,以至于不浪费更多的空间来存储全局变量数组。 void BSTreeKey() { //由用户输入数据,用全局变量数组num[]存储用户所输入的n个数据 cout<<"please input="" the="" number="" of="" the="" figures="" you="" want="" to="" set(less="" than="" 100):";=""><"please> cin>>n; cout<<"please input="" the="" figures(the="" whole="" number=""><"please><><> for(int i=0;i { cin>>num[i]; } } 3.2 产生随机数函数 此函数的功能:提示用户输入想进行排序的数据的个数,由随机函数产生相应个数的随机数,并存储于全局变量数组中,其中,随机数的范围是0,2000。 void RandBSTreeKey() {//产生随机数,并将产生的随机数用全局变量数组num[]存储 cout<<"please input="" the="" number="" of="" the="" figures="" you="" want="" to="" set(less="" than="" 100):";=""><"please> cin>>n; int randfig[100]; for(int i=0;i { 2 武汉理工大学《数据结构》课程设计说明书 randfig[i]=(double)rand()*2000/32767; num[i] = (int)randfig[i]; } cout<<"the random="" figures=""><"the> for(int j=0;j { cout<><<" ";=""><"> } cout } 3.3 建立二叉排序树函数 此函数的功能:从空树开始,将以存储的数据按其在数组中的顺序逐个插入到二叉排序树中,其中用到二叉排序树插入结点的具体算法(之后会提到)。 BinSTreeNode *BinSTreeBuild(KeyType *num,int n,BinSTreeNode *root) {//根据用户输入的数据建立二叉排序树 for(int i=0;i { BinSTreeNode *p; p=root; root=BSTreeInsert(num[i],p,root); }//endfor return root; }//endBinSTreeBuild 3.4 二叉排序树插入结点函数 此函数的功能:把作为函数参数传递的数据作为关键字生成左右孩子为空的结点,将其关键字首先由于以生成的二叉排序树的根结点比较;若根结点为空,直接将该结点作为根结点;若其关键字比根结点的关键字小,则用递归算法将其关键字于根结点的左子树的根结点比较;若其关键字比根结点的关键字大,则用递归算法将其关键字于根结点的右子树的根结点比较。 3 武汉理工大学《数据结构》课程设计说明书 BinSTreeNode *BSTreeInsert(KeyType k,BinSTreeNode *p,BinSTreeNode *root) {//将数据作为结点的关键字,并将结点插入已生成的二叉排序树中 BinSTreeNode *r=new BinSTreeNode; r->key=k; r->lchild=NULL; r->rchild=NULL;//建立以数据作为关键字的二叉排序树 if(root==NULL) root=r;//若根结点为空,直接将r值赋给根结点 else { if(k { if(p->lchild) { p=p->lchild; BSTreeInsert(k,p,root); }//endif else p->lchild=r; }//endif else { if(p->rchild) { p=p->rchild; BSTreeInsert(k,p,root); }//endif else p->rchild=r; }//endelse }//endelse return root; 4 武汉理工大学《数据结构》课程设计说明书 }//endBSTreeInsert 3.5 中序遍历输出函数 此函数的功能:中序遍历已经生成的二叉排序树,并将访问到的结点输出,即可得一有序序列。 void InOrderPrint(BinSTreeNode *t) {//中序遍历二叉排序树并输出 if(t!=NULL) { InOrderPrint(t->lchild); cout InOrderPrint(t->rchild); } } 4 程序实现和测试 初始界面:提示用户选择有自己输入数据或由机器随机产生数据; 用户选择自己输入数据后,提示用户输入数据的个数及具体数值,显示排序后的序列 5 武汉理工大学《数据结构》课程设计说明书 用户选择由机器生成随机数后,提示用户输入随机数产生的个数,显示排序后的序列 排序结束后,提示用户是否继续进行排序 若是,回到初始界面的提示 若否,退出程序 6 武汉理工大学《数据结构》课程设计说明书 5 不足之处 本程序主要不足在于没有直观地将建立好的二叉排序树按树形输出,这样能方便用户理解二叉排序树的构造过程。但由于没有了解关于图的输出函数的有关知识,所以无法实现二叉排序树的图形输出。 存储数据时用数组,为了方便用户随机定义数据的个数,因此程序开始时定义了全局变量数组,且限定了数组的个数的最大值为100。实现用户输入数据和机器随机生成数据时,开辟了同样大的空间存储,因而耗费了空间;同时,为了能够正常显示结果,把机器产生的随机数的数据范围改成0,2000之间,无法适应数据量更大的情况,需改进,但是,其体现的功能仍然是正确的。 程序中没有完全考虑用户输入信息出错的情况,如用户输入的数据的实际个数值与之前输入的数据个数值不符,或需要用户输入“Y”或“N”时,用户输入的字符与“Y”、“N”。但在程序中起到补偿作用的是在提示用户输入数据时,也显示之前输入的数据个数,及在提示用户选择时,在提示语句后加上“Y/N”。这些都有较好的提示效果。 6 设计体会 通过实际操作,学会 C语言程序编程的基本步骤、基本方法,开发了自己的逻辑思维能力,培养了分析问题、解决问题的能力。希望以后应多进行这样的课程设计,加长设间,培养学生独立思考问题的能力,提高实际操作水平。 在具体操作中对这学期所学的C++语言的理论知识得到巩固,达到训练的基本目的,也发现自己的不足之出,在以后的上机中应更加注意,同时体会到C++语言具有的语句简洁,使用灵活,执行效率高等特点。发现上机实训的重要作用,特别是对数组和循环有了深刻的理解。而且通过对此课程的设计,我不 7 武汉理工大学《数据结构》课程设计说明书 但知道了以前不知道的理论知识,而且也巩固了以前知道的知识。最重要的是在实践中理解了书本上的知识,明白了学以致用的真谛。不仅使自己的编程能力得到了锻炼和提高,也对于《数据结构》这门课程有了更加深入的了解。对于以后的深入学习奠定了基础。 7 结束语 本文主要是对用户输入的数据和机器生成的随机数进行顺序表存储,根据已记录的数据建立二叉排序树,最后中序遍历二叉排序树输出数据,得到的序列即为有序序列。整个程序用c++语言编写,在visual c++中运行成功。 参考文献 [1] 严蔚敏 ,吴伟名,《数据结构》,清华大学出版社,2006年 [2] 李春葆,苏光奎,《数据结构与算法教程》,清华大学出版社,2005年 [3] 宁正元,易金聪,《数据结构学习辅导》,清华大学出版社,2005年 [4] 秦锋,《数据结构(C++)》,北京大学出版社,2006年 8 #include #include #include #define LENGTH 1000 int longth=1; //用于重分配内存 const int nnumber=0,nrank=1,nscore=2;//按学号 名词 总分 排序 typedef struct Birthday { int year; int month; int day; }Birthday; typedef struct Sstu { char name[20]; char sex[10]; Birthday birthday; char colloge[20]; int grade; char major[20]; int info[10]; }Sstu; typedef struct Student { int stunumber; int scorenumber; char information[10][10]; Sstu *hole; }Student; void Editdeal(Student *S); void Filedeal(Student *S); void Fileread(FILE *fp,Student *S); void Filesave(FILE *fp,Student *S); void Filesaveother(FILE *fp,Student *S); int Find(int id,Student *S,int flag); int Getint(void); void InitS(Student *S); void Read(Student *S); void Searchdeal(Student *S); void Sortdeal(Student *S); void Sort(int m,Student *S,int start,int end); int Partition(int m,Student *S,int start,int end); void Sort2(int m,Student *S,int start,int end); int Partition2(int m,Student *S,int start,int end); void Sort3(int m,Student *S,int start,int end); void dellast(void); void Print(Student *S); void main(void) { Student S; int flag; FILE *fp=0; InitS(&S); if((fp=fopen("配置文件.txt","rb"))!=0) { printf("\n正在读取配置文件,请稍等、、、"); Fileread(fp,&S); fclose(fp); printf("\n读取完毕"); } else { printf("\n首次使用没有生成配置文件,请首先输入学生成绩等信息"); Read(&S); fp=fopen("配置文件.txt","wb"); Filesave(fp,&S); fclose(fp); } printf("\n---------------------------------------------------------"); printf("\n| |"); printf("\n| o(?_?)o... 欢迎使用学生成绩管理系统 |"); printf("\n| |"); do { printf("\n|---------------------------------------------------|"); printf("\n|1,文件||2,编辑||3,查找||4,排序||5,输出||0,退出 |"); printf("\n|---------------------------------------------------|\n选择="); flag=Getint(); switch(flag) { case 1: Filedeal(&S); break; case 2: Editdeal(&S); break; case 3: Searchdeal(&S); break; case 4: Sortdeal(&S); break; case 5: Print(&S); break; case 0: break; default : printf("\n选择无效,请重新选择"); break; } }while(flag); printf("\n你想保存操作吗,\n1,保存||0,不保存\n选择="); flag=Getint(); if(flag) { if((fp=fopen("配置文件.txt","wb"))!=0) { Filesave(fp,&S); fclose(fp); } else printf("\n保存失败"); } printf("\n谢谢使用"); } void Filedeal(Student *S) { int flag; FILE *fp=0; char address[50]; printf("\n1,重新读取||2,重新键盘输入||3,保存||4,另存为||0,退出\n选择="); flag=Getint(); switch(flag) { case 1: if((fp=fopen("配置文件.txt","rb"))!=0) { Fileread(fp,S); fclose(fp); } else printf("\n读取失败"); break; case 2: Read(S); break; case 3: if((fp=fopen("配置文件.txt","wb"))!=0) { Filesave(fp,S); fclose(fp); } else printf("\n保存失败"); break; case 4: if(S->stunumber==0) { printf("没有学生的信息!"); return; } printf("\n请输入地址如:D:\\文件\\成绩.txt,保存到当前文件夹如:成 绩.txt\n文件地址="); gets(address); if((fp=fopen(address,"w"))!=0) { Filesaveother(fp,S); fclose(fp); } else printf("\n保存失败"); break; case 0: break; default : printf("\n选择无效"); } } void Editdeal(Student *S) { int flag,flag2,id,i,j,sum=0; printf("\n1,插入||2,删除||3,编辑某个学生信息||0,退出\n选择="); flag2=Getint(); switch(flag2) { case 1: if(S->stunumber+1>=longth*LENGTH) { longth++; while(!(S->hole=(Sstu *)realloc(S->hole,(longth*LENGTH)*sizeof(Sstu)))) continue; } Sort(nnumber,S,0,S->stunumber-1);//快速排序按学号排序//////////////////////////////////////// printf("\n请输入学号:\n学号="); id=Getint(); flag=1; i=Find(id,S,flag); if(i<0)>0)> { printf("\n学号不能小于0~~"); return; } for(j=S->stunumber;j>i;j--)////////////////// S->hole[j]=S->hole[j-1]; S->hole[i].info[nnumber]=id; printf("\n请输入姓名\n姓名="); gets(S->hole[i].name); printf("\n请输入性别\n性别="); gets(S->hole[i].sex); printf("\n请输入出生日期 如2009,08,15\n出生日期="); scanf("%d,%d,%d",&(*S).hole[i].birthday.year,&(*S).hole[i].birthday.month,&(*S). hole[i].birthday.day); dellast(); printf("\n请输入所在学院\n学院="); gets(S->hole[i].colloge); printf("\n请输入所在专业\n专业="); gets(S->hole[i].major); printf("\n请输入入学时间\n入学时间="); S->hole[i].grade=Getint(); for(j=0;j { printf("\n请输入 %s 的成绩",S->information[j+3]); sum+=S->hole[i].info[j+3]=Getint(); } S->hole[i].info[nscore]=sum; S->stunumber++; Sort3(nscore,S,0,S->stunumber); for(i=0;i S->hole[i].info[nrank]=i+1; break; case 2: if(S->stunumber==0) { printf("没有学生的信息!"); return; } Sort(nnumber,S,0,S->stunumber-1); printf("\n请输入要删除的学号\n学号="); id=Getint(); flag=0; i=Find(id,S,flag);//二分查找返回结构体的位置 if(i<0||i>S->hole[S->stunumber-1].info[nnumber]) { printf("\n没有学号是%d的学生的信息",id); return; } for(j=i;j S->hole[j]=S->hole[j+1]; S->stunumber--; Sort3(nscore,S,0,S->stunumber-1); for(i=0;i S->hole[i].info[nrank]=i+1; break; case 3: if(S->stunumber==0) { printf("没有学生的信息!"); return; } Sort(nnumber,S,0,S->stunumber-1); printf("\n请输入要编辑的学号\n学号="); id=Getint(); flag=0; i=Find(id,S,flag); if(i<0||i>=S->stunumber) { printf("\n没有学号是%d的学生的信息3",id); return; } printf("\n学号是%d的学生信息如下",id); printf("\n-------------------------------------------------------------"); printf("\n学号:%d\t姓名:%s\t",S->hole[i].info[nnumber],S->hole[i].name); printf("\n出生日期:%d年%d月%d日",S->hole[i].birthday.year,S->hole[i].birthday.month,S->hole[i].birthday.day); printf("\n学院:%s\t专业:%s\t年 级:%d",S->hole[i].colloge,S->hole[i].major,S->hole[i].grade); printf("\n排名:%d\t总分:%d",S->hole[i].info[nrank],S->hole[i].info[nscore]); for(j=0;j printf("\t%S:%d",S->information[j+3],S->hole[i].info[j+3]); printf("\n-------------------------------------------------------------"); printf("\n请输入新的学号\n学号="); S->hole[i].info[nnumber]=Getint(); printf("\n请输入姓名\n姓名="); gets(S->hole[i].name); printf("\n请输入性别\n性别="); gets(S->hole[i].sex); printf("\n请输入出生日期 如2009,08,15\n出生日期="); scanf("%d,%d,%d",&(*S).hole[i].birthday.year,&(*S).hole[i].birthday.month,&(*S). hole[i].birthday.day); dellast(); printf("\n请输入所在学院\n学院="); gets(S->hole[i].colloge); printf("\n请输入所在专业\n专业="); gets(S->hole[i].major); printf("\n请输入入学时间\n入学时间="); S->hole[i].grade=Getint(); for(j=0;j { printf("\n请输入 %s 的成绩",S->information[j+3]); sum+=S->hole[i].info[j+3]=Getint(); } S->hole[i].info[nscore]=sum; Sort3(nscore,S,0,S->stunumber-1); for(i=0;i S->hole[i].info[nrank]=i+1; break; case 0: break; default : break; } } void Searchdeal(Student *S) { int id,i,j,flag=0; if(S->stunumber==0) { printf("没有学生的信息!"); return; } Sort(nnumber,S,0,S->stunumber-1); printf("请输入学号\n学号="); id=Getint(); i=Find(id,S,flag); if(i<0)>0)> { printf("\n没有学号是%d的学生的信息",id); return; } printf("\n学号是%d的学生信息如下",id); printf("\n-------------------------------------------------------------"); printf("\n学号:%d\t姓 名:%s\t",S->hole[i].info[nnumber],S->hole[i].name); printf("\n出生日期:%d年%d月%d日 ",S->hole[i].birthday.year,S->hole[i].birthday.month,S->hole[i].birthday.day); printf("\n学院:%s\t专业:%s\t年 级:%d",S->hole[i].colloge,S->hole[i].major,S->hole[i].grade); printf("\n排名:%d\t总 分:%d",S->hole[i].info[nrank],S->hole[i].info[nscore]); for(j=0;j printf("\t%s:%d",S->information[j+3],S->hole[i].info[j+3]); printf("\n-------------------------------------------------------------"); } void Sortdeal(Student *S) { int num,i,j; if(S->stunumber==0) { printf("没有学生的信息!"); return; } printf("\n请输入按什么排序"); printf("\n1,学号||2,排名||3,总成绩"); for(i=0;i printf("||%d,%s",i+4,S->information[i+3]); printf("\n选择="); num=Getint(); num--; if(num==0||num==1) Sort(num,S,0,S->stunumber-1); else Sort3(num,S,0,S->stunumber-1); printf("\n按照 %s 排序的学生成绩信息如下:\n",S->information[num]); for(i=0;i { printf("\n-------------------------------------------------------------"); printf("\n学号:%d\t姓 名:%s\t",S->hole[i].info[nnumber],S->hole[i].name); printf("\n出生日期:%d年%d月%d日 ",S->hole[i].birthday.year,S->hole[i].birthday.month,S->hole[i].birthday.day); printf("\n学院:%s\t专业:%s\t年 级:%d",S->hole[i].colloge,S->hole[i].major,S->hole[i].grade); printf("\n排名:%d\t总 分:%d",S->hole[i].info[nrank],S->hole[i].info[nscore]); for(j=0;j printf("\t%s:%d",S->information[j+3],S->hole[i].info[j+3]); } printf("\n-------------------------------------------------------------"); } void InitS(Student *S) { strcpy(S->information[0],"学号"); strcpy(S->information[1],"排名"); strcpy(S->information[2],"总分"); while(!(S->hole=(Sstu *)malloc((LENGTH)*sizeof(Sstu)))) continue; } void Fileread(FILE *fp,Student *S) { int i; fscanf(fp,"\t%d",&S->stunumber); fscanf(fp,"\t%d",&S->scorenumber); fread(&S->information,sizeof(S->information),1,fp); for(i=0;i { if(S->stunumber+1>=longth*LENGTH) { longth++; while(!(S->hole=(Sstu *)realloc(S->hole,(longth*LENGTH)*sizeof(Sstu)))) continue; } fread(&S->hole[i],sizeof(S->hole[i]),1,fp); } } void Read(Student *S) { int i,j,sum; printf("\n请输入学科的数量\n学科数量="); S->scorenumber=Getint(); for(i=0;i { printf("\n请输入第%d个学科的名称\n名称=",i+1); gets(S->information[i+3]); } printf("\n开始输入学生详细信息,当学号输入为非整数时停止输入"); for(i=0;;i++) { sum=0; if(S->stunumber+1>=longth*LENGTH) { longth++; while(!(S->hole=(Sstu *)realloc(S->hole,(longth*LENGTH)*sizeof(Sstu)))) continue; } printf("\n请输第%d个学生的学号\n学号=",i+1); if(scanf("%d",&S->hole[i].info[nnumber])!=1) break; dellast(); printf("\n请输入姓名\n姓名="); gets(S->hole[i].name); printf("\n请输入性别\n性别="); gets(S->hole[i].sex); printf("\n请输入出生日期 如2009,08,15\n出生日期="); scanf("%d,%d,%d",&(*S).hole[i].birthday.year,&(*S).hole[i].birthday.month,&(*S). hole[i].birthday.day); dellast(); printf("\n请输入所在学院\n学院="); gets(S->hole[i].colloge); printf("\n请输入所在专业\n专业="); gets(S->hole[i].major); printf("\n请输入入学时间\n入学时间="); S->hole[i].grade=Getint(); for(j=0;j { printf("\n请输入 %s 的成绩\n%s成绩=",S->information[j+3],S->information[j+3]); sum+=S->hole[i].info[j+3]=Getint(); } S->hole[i].info[nscore]=sum; } S->stunumber=i; Sort3(nscore,S,0,S->stunumber-1); for(i=0;i S->hole[i].info[nrank]=i+1; } void Filesave(FILE *fp,Student *S) { int i; if(S->stunumber==0) { printf("没有学生的信息!"); return; } fprintf(fp,"\t%d",S->stunumber); fprintf(fp,"\t%d",S->scorenumber); fwrite(S->information,sizeof(S->information),1,fp); for(i=0;i fwrite(&S->hole[i],sizeof(Sstu),1,fp); } void Filesaveother(FILE *fp,Student *S) { int i,j; if(S->stunumber==0) { printf("没有学生的信息!"); return; } fprintf(fp,"学生数量:%d\n",S->stunumber); fprintf(fp,"学科数量:%d\n",S->scorenumber); fprintf(fp,"学科名称:"); for(j=0;j fprintf(fp,"\t%s",S->information[j+3]); for(i=0;i { fprintf(fp,"\n-------------------------------------------------------------"); fprintf(fp,"\n学号:%d\t姓 名:%s\t",S->hole[i].info[nnumber],S->hole[i].name); fprintf(fp,"\n出生日期:%d年%d月%d日 ",S->hole[i].birthday.year,S->hole[i].birthday.month,S->hole[i].birthday.day); fprintf(fp,"\n学院:%s\t专业:%s\t年 级:%d",S->hole[i].colloge,S->hole[i].major,S->hole[i].grade); fprintf(fp,"\n排名:%d\t总 分:%d",S->hole[i].info[nrank],S->hole[i].info[nscore]); for(j=0;j fprintf(fp,"\t%s:%d",S->information[j+3],S->hole[i].info[j+3]); } fprintf(fp,"\n-------------------------------------------------------------"); } int Find(int id,Student *S,int flag) { int i,j=0; if(id<0)>0)> { printf("\n找不到学号为%d的学生信息",id); return -1; } if(flag==0) { if(id==S->hole[0].info[nnumber]) return 0; if(id==S->hole[S->stunumber-1].info[nnumber]) return S->stunumber-1; i=(S->stunumber-1)/2; while(S->hole[i].info[nnumber]!=id&&j<=s->stunumber) { if(S->hole[i].info[nnumber]>id) i=i/2; if(S->hole[i].info[nnumber] i=(i+S->stunumber-1)/2; j++; } if(S->hole[i].info[nnumber]==id) return i; } else if(flag==1) { if(id<=s->hole[0].info[nnumber]) return 0; if(id>=S->hole[S->stunumber-1].info[nnumber]) return S->stunumber; for(i=0;i if(id>S->hole[i].info[nnumber]&&id return i; } return -1; } int Getint(void) { int m; while(scanf("%d",&m)!=1) { while(getchar()!='\n') continue; printf("\n请输入一个整数\n整数="); } while(getchar()!='\n') continue; return m; } void Sort(int m,Student *S,int start,int end) { int pivotloc; if(start { pivotloc=Partition(m,S,start,end); Sort(m,S,start,pivotloc-1); Sort(m,S,pivotloc+1,end); } } int Partition(int m,Student *S,int start,int end) { int pivotkey; Sstu A; A=S->hole[start]; pivotkey=S->hole[start].info[m]; while(start { while(start end--; S->hole[start]=S->hole[end]; while(start start++; S->hole[end]=S->hole[start]; } S->hole[start]=A; return start; } void Sort3(int m,Student *S,int start,int end) /*调用Sort2函数,首先进行从大到小排序,若有若干人成绩相同,则对他们按学号排序*/ { int i=0,j=1; Sort2(m,S,start,end); while(i<><=end)>=end)> { if(S->hole[i].info[m]!=S->hole[j].info[m]&&i<><=end)>=end)> { i++; j++; } if(S->hole[i].info[m]==S->hole[j].info[m]&&i<><=end)>=end)> { while(S->hole[i].info[m]==S->hole[j].info[m]&&i<><=end)>=end)> j++; Sort(nnumber,S,i,j-1); i=j-1; } } } void Sort2(int m,Student *S,int start,int end)///////////////从大到小排序 { int pivotloc; if(start { pivotloc=Partition2(m,S,start,end); Sort2(m,S,start,pivotloc-1); Sort2(m,S,pivotloc+1,end); } } int Partition2(int m,Student *S,int start,int end) { int pivotkey; Sstu A; A=S->hole[start]; pivotkey=S->hole[start].info[m]; while(start { while(start end--; S->hole[start]=S->hole[end]; while(start start++; S->hole[end]=S->hole[start]; } S->hole[start]=A; return start; } void dellast(void) { while(getchar()!='\n') continue; } void Print(Student *S) { int i,j; if(S->stunumber==0) { printf("没有学生的信息!"); return; } for(i=0;i { printf("\n-------------------------------------------------------------"); printf("\n学号:%d\t姓 名:%s\t",S->hole[i].info[nnumber],S->hole[i].name); printf("\n出生日期:%d年%d月%d日 ",S->hole[i].birthday.year,S->hole[i].birthday.month,S->hole[i].birthday.day); printf("\n学院:%s\t专业:%s\t年 级:%d",S->hole[i].colloge,S->hole[i].major,S->hole[i].grade); printf("\n排名:%d\t总 分:%d",S->hole[i].info[nrank],S->hole[i].info[nscore]); for(j=0;j printf("\t%s:%d",S->information[j+3],S->hole[i].info[j+3]); } printf("\n-------------------------------------------------------------"); }范文二:严格平衡二叉排序树及其构造
范文三:二叉排序树的构造与运算
范文四:二叉排序树的构造与运算
范文五:二叉排序树构造课程设计.txt