资源描述：
《数据结构C语言版5-路归并的败者树的实现.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、数据结构C语言版5-路归并的败者树的实现.txt51自信是永不枯竭的源泉，自信是奔腾不息的波涛，自信是急流奋进的渠道，自信是真正的成功之母。/*数据结构C语言版5-路归并的败者树的实现P298.编译环境：Dev-C++4.9.9.2日期：2011年2月9日*/#include#include#include#include#include#include#include//对两个数值型关键字的比较约定为如下的宏定义#defineLT(a,b
2、)((a)<(b))#defineMINKEYINT_MIN#defineMAXKEYINT_MAX//k路归并#definek5//设每小个文件有N个数据(可将整个文件一次读入内存的称为小文件)#defineN3#defineMk//设输出M个数据换行typedefintInfoType;//定义其它数据项的类型typedefintKeyType;//定义关键字类型为整型#defineMAXSIZE20//一个用作示例的小顺序表的最大长度//待排记录的数据类型,记录类型typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;
3、//其它数据项，具体类型自定义}RedType;//顺序表类型typedefstruct{RedTyper[MAXSIZE+1];//r[0]闲置或用作哨兵单元intlength;//顺序表长度}SqList;//定义k+1个文件指针，其中fp[k]为大文件的指针，其他的//都是小文件的指针。FILE*fp[k+1];//因为败者树是完全二叉树且不含叶子，所以可采用顺序存储结构typedefintLoserTree[k];//外节点，用来存放待归并记录的关键字typedefRedTypeExNode,External[k+1];Externalb;//算法10.1，对
4、顺序表L作直接插入排序。voidInsertSort(SqList*L){inti,j;for(i=2;i<=(*L).length;++i)//"<",需将L.r[i]插入有序子表ifLT((*L).r[i].key,(*L).r[i-1].key){//复制为哨兵(*L).r[0]=(*L).r[i];for(j=i-1;LT((*L).r[0].key,(*L).r[j].key);--j)(*L).r[j+1]=(*L).r[j];//记录后移(*L).r[j+1]=(*L).r[0];//插入到正确位置}}//从第i个文件(第i个归并段)读入该段当前第1个记
5、录//的关键字到外结点voidinput(inti,KeyType*a){fread(a,sizeof(KeyType),1,fp[i]);}//将第i个文件(第i个归并段)中当前的记录写至输出归并段voidoutput(inti){ExNodea;//当前记录的关键字已读到b[i].key中a.key=b[i].key;fread(&a.otherinfo,sizeof(InfoType),1,fp[i]);//将结果写入大文件fp[k]中fwrite(&a,sizeof(ExNode),1,fp[k]);}//算法11.2P299//沿从叶子结点b[s]到根结点l
6、s[0]的路径调整败者树。找到最小//关键字赋给ls[0]voidAdjust(LoserTreels,ints){inti,t;t=(s+k)/2;//ls[t]是b[s]的双亲结点while(t>0){//key值的大的为败者，成为节点，ls[t]的值变为sif(b[s].key>b[ls[t]].key){i=s;s=ls[t];//s指示新的胜者,关键字小的为胜者ls[t]=i;}//胜者继续向上比较t/=2;}//ls[0]指向最后的胜者也就是最小关键字b[s].key的sls[0]=s;}/*算法11.3P299已知b[0]到b[k-1]为完全二叉树ls的
7、叶子结点，存有k个关键字，沿从叶子到根的k条路径将ls调整成为败者树。*/voidCreateLoserTree(LoserTreels){inti;b[k].key=MINKEY;//设置ls中“败者”的初值for(i=0;i=0;--i)Adjust(ls,i);}/*算法11.1利用败者树ls将编号从0到k-1的k个输入归并段中的记录归并到输出归并段。b[0]至b[k-1]为败者树上的k个叶子结点，分别存放k个输入归并段中当前记录
