10.4.2树形选择排序

============================================================
e1:ceil和floor函数。
函数名: ceil
用 法: double ceil(double x);
功 能: 返回大于或者等于指定表达式的最小整数
头文件:math.h
*******************************
函数名： floor
功 能： 返回小于或者等于指定表达式的最大整数
用 法： double floor(double x);
头文件：math.h
*******************************
// aaa.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "iostream.h"
#include "math.h"
#include "stdio.h"
#include "stdlib.h"
#include "process.h"
#include "stdarg.h"
#include "string.h"
//

int main(int argc, char* argv[])
{
printf("-----beg-----\n");
double number = 123.54;
double down, up;
down = floor(number);
up = ceil(number);
printf("--original number %f--\n", number);
printf("--number rounded down %f--\n", down);
printf("--number rounded up %f--\n", up);
printf("-------------------------------------------\n");
number = 123.12;
down = floor(number);
up = ceil(number);
printf("--original number %f--\n", number);
printf("--number rounded down %f--\n", down);
printf("--number rounded up %f--\n", up);
printf("-----end-----\n");
return 0;
}
//////////////////////////////////////////////////////
-----beg-----
--original number 123.540000--
--number rounded down 123.000000--
--number rounded up 124.000000--
-------------------------------------------
--original number 123.120000--
--number rounded down 123.000000--
--number rounded up 124.000000--
-----end-----
Press any key to continue
//////////////////////////////////////////////////////
============================================================
e2:log函数。
原型：double log (double x);
头文件：math.h
功能：计算以e 为底的对数值
*********************************
// aaa.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "iostream.h"
#include "math.h"
#include "stdio.h"
#include "stdlib.h"
#include "process.h"
#include "stdarg.h"
#include "string.h"
//
int main(int argc, char* argv[])
{
printf("-----beg-----\n");
double result;
double x = 321.456;
result = log(x);
printf("The common log of %lf is %lf\n", x, result);
printf("-----end-----\n");
return 0;
}
////////////////////////////////////////////////
-----beg-----
The common log of 321.456000 is 5.772861
-----end-----
Press any key to continue
////////////////////////////////////////////////
============================================================
e3:pow函数。
原型为double pow( double x, double y );
头文件：math.h/cmath(C++中)
功能：计算x的y次幂。
返回值：x应大于零，返回幂指数的结果。
*******************************************
// aaa.c

pp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "iostream.h"
#include "math.h"
#include "stdio.h"
#include "stdlib.h"
#include "process.h"
#include "stdarg.h"
#include "string.h"
//
int main(int argc, char* argv[])
{
printf("-----beg-----\n");
double x = 2.0, y = 3.0;
printf("%lf raised to %lf is %lf\n", x, y, pow(x, y));
x = 4.0;
y = 5.0;
printf("%lf raised to %lf is %lf\n", x, y, pow(x, y));
printf("-----end-----\n");
return 0;
}
////////////////////////////////////////////////////
-----beg-----
2.000000 raised to 3.000000 is 8.000000
4.000000 raised to 5.000000 is 1024.000000
-----end-----
Press any key to continue
////////////////////////////////////////////////////
============================================================
e4:TreeSort(data[]={0,49,38,65,97,76,13,27,49})。1/2.
// aaa.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "iostream.h"
#include "math.h"
#include "stdio.h"
#include "stdlib.h"
#include "process.h"
#include "stdarg.h"
#include "string.h"
//
typedef int Status;
typedef int KeyType;
typedef int ElemType;
#define FALSE 0
#define TRUE 1
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)>(b))
#define LH +1 //左高。
#define EH 0 //等高。
#define RH -1 //右高。
//
#define INT_MAX 200
#define MAXSIZE 20 //一个用作示例的小顺序表的最大长度。
typedef int KeyType; //定义关键字类型为整数类型。
typedef char InfoType;
typedef struct
{
KeyType key; //关键字项。
InfoType otherinfo; //其它数据项。
}RedType; //记录类型。
typedef struct
{
RedType r[MAXSIZE+1]; //r[0]闲置或用作哨兵单元。
int length; //顺序表长度。
}SqList; //顺序表类型。

/////////////////
void TreeSort(SqList &L)
{
int i,j,j1,k,k1,l,n=L.length;
RedType *t;
l=(int)ceil(log(n)/log(2))+1; //完全二叉树的层数
k=(int)pow(2,l)-1; //l层完全二叉树的结点总数
k1=(int)pow(2,l-1)-1; //l-1层二叉完全二叉树的结点总数
//
printf("--l=%d,k=%d,k1=%d--\n",l,k,k1);
//
t=(RedType*)malloc(k*sizeof(RedType)); //二叉树采用顺序存储
for(i=1;i<=n;i++) //将L.r赋值给叶子结点
t[k1+i-1]=L.r[i];
for(i=k1+n;it[i].key=INT_MAX;
j1=k1;
j=k;
while(j1) //给非叶子结点赋值
{
for(i=j1;it[i].keyj=j1;
j1=(j1-1)/2;
}//while(j1)
for(i=0;i{
//
printf("-i=%d",i);
for(int x=0;xprintf("%4d",t[x].key);
printf("\n");
printf("------------------------------------------------------------\n");
//
L.r[i+1]=t[0]; //键当前最小值赋给L.r[i]
j1=0

;
for(j=1;jt[2*j1+1].key==t[j1].key?(j1=2*j1+1):(j1=2*j1+2);
t[j1].key=INT_MAX;
while(j1)
{
j1=(j1+1)/2-1; //序号为j1的节点的双亲节点序号
t[2*j1+1].key<=t[2*j1+2].key?(t[j1]=t[2*j1+1]):(t[j1]=t[2*j1+2]);
}
}//for(i=0;ifree(t);
}//TreeSort

int main(int argc, char* argv[])
{
printf("-----beg-----\n");
int data[]={0,49,38,65,97,76,13,27,49};
SqList main_l;
printf("--main_l.length=%d--\n",main_l.length);
for(int i=0;i<12;i++)
printf("--i=%2d,key=%d,otherinfo=%d--\n",i,main_l.r[i].key,main_l.r[i].otherinfo);
printf("------------------after_set_[main_l.length]--\n");
main_l.length =8;
printf("--main_l.length=%d--\n",main_l.length);
for(i=0;i<12;i++)
printf("--i=%2d,key=%d,otherinfo=%d--\n",i,main_l.r[i].key,main_l.r[i].otherinfo);
printf("------------------after_set_[main_l.r[i].key]--\n");
for(i=0;i<=8;i++)
main_l.r[i].key=data[i];

printf("--main_l.length=%d--\n",main_l.length);
for(i=0;i<12;i++)
printf("--i=%2d,key=%d,otherinfo=%d--\n",i,main_l.r[i].key,main_l.r[i].otherinfo);
printf("----------------------------------------------before_HeapSort--\n");

for(int x=0;x<=8;x++)
{
printf("%3d",main_l.r[x].key);
}
printf("\n");
::TreeSort(main_l);
//////////
printf("----------------------------------------------after_HeapSort--\n");
for( x=0;x<=8;x++)
{
printf("%3d",main_l.r[x].key);
}
printf("\n");
//////////
printf("-----end-----\n");
return 0;
}
//////////////////////////////////////////////////
-----beg-----
--main_l.length=-858993460--
--i= 0,key=-858993460,otherinfo=-52--
--i= 1,key=-858993460,otherinfo=-52--
--i= 2,key=-858993460,otherinfo=-52--
--i= 3,key=-858993460,otherinfo=-52--
--i= 4,key=-858993460,otherinfo=-52--
--i= 5,key=-858993460,otherinfo=-52--
--i= 6,key=-858993460,otherinfo=-52--
--i= 7,key=-858993460,otherinfo=-52--
--i= 8,key=-858993460,otherinfo=-52--
--i= 9,key=-858993460,otherinfo=-52--
--i=10,key=-858993460,otherinfo=-52--
--i=11,key=-858993460,otherinfo=-52--
------------------after_set_[main_l.length]--
--main_l.length=8--
--i= 0,key=-858993460,otherinfo=-52--
--i= 1,key=-858993460,otherinfo=-52--
--i= 2,key=-858993460,otherinfo=-52--
--i= 3,key=-858993460,otherinfo=-52--
--i= 4,key=-858993460,otherinfo=-52--
--i= 5,key=-858993460,otherinfo=-52--
--i= 6,key=-858993460,otherinfo=-52--
--i= 7,key=-858993460,otherinfo=-52--
--i= 8,key=-858993460,otherinfo=-52--
--i= 9,key=-858993460,otherinfo=-52--
--i=10,key=-858993460,otherinfo=-52--
--i=11,key=-858993460,otherinfo=-52--
------------------after_set_[main_l.r[i].key]--
--main_l.length=8--
--i= 0,key=0,otherinfo=-52--
--i= 1,key=49,otherinfo=-52--
--i= 2,key=38,otherinfo=-52--
--i= 3,key=65,otherinfo=-52--
--i= 4,key=97,otherinfo=-52--
--i= 5,key=76,otherinfo=-52--
--i= 6,key=13,o

therinfo=-52--
--i= 7,key=27,otherinfo=-52--
--i= 8,key=49,otherinfo=-52--
--i= 9,key=-858993460,otherinfo=-52--
--i=10,key=-858993460,otherinfo=-52--
--i=11,key=-858993460,otherinfo=-52--
----------------------------------------------before_HeapSort--
0 49 38 65 97 76 13 27 49
--l=4,k=15,k1=7--
-i=0 13 38 13 38 65 13 27 49 38 65 97 76 13 27 49-33686019 0
------------------------------------------------------------
-i=1 27 38 27 38 65 76 27 49 38 65 97 76 200 27 49-33686019 0
------------------------------------------------------------
-i=2 38 38 49 38 65 76 49 49 38 65 97 76 200 200 49-33686019 0
------------------------------------------------------------
-i=3 49 49 49 49 65 76 49 49 200 65 97 76 200 200 49-33686019 0
------------------------------------------------------------
-i=4 49 65 49 200 65 76 49 200 200 65 97 76 200 200 49-33686019 0
------------------------------------------------------------
-i=5 65 65 76 200 65 76 200 200 200 65 97 76 200 200 200-33686019 0
------------------------------------------------------------
-i=6 76 97 76 200 97 76 200 200 200 200 97 76 200 200 200-33686019 0
------------------------------------------------------------
-i=7 97 97 200 200 97 200 200 200 200 200 97 200 200 200 200-33686019 0
------------------------------------------------------------
----------------------------------------------after_HeapSort--
0 13 27 38 49 49 65 76 97
-----end-----
Press any key to continue
//////////////////////////////////////////////////
============================================================
e5:TreeSort(叶子不满时)，2/2。
/*
(data[]={0,49,38,65,97,76,13})。
*/
......其它代码同上。
int main(int argc, char* argv[])
{
printf("-----beg-----\n");
int data[]={0,49,38,65,97,76,13};
SqList main_l;
printf("--main_l.length=%d--\n",main_l.length);
for(int i=0;i<12;i++)
printf("--i=%2d,key=%d,otherinfo=%d--\n",i,main_l.r[i].key,main_l.r[i].otherinfo);
printf("------------------after_set_[main_l.length]--\n");
main_l.length =6;
printf("--main_l.length=%d--\n",main_l.length);
for(i=0;i<12;i++)
printf("--i=%2d,key=%d,otherinfo=%d--\n",i,main_l.r[i].key,main_l.r[i].otherinfo);
printf("------------------after_set_[main_l.r[i].key]--\n");
for(i=0;i<=8;i++)
main_l.r[i].key=data[i];

printf("--main_l.length=%d--\n",main_l.length);
for(i=0;i<12;i++)
printf("--i=%2d,key=%d,otherinfo=%d--\n",i,main_l.r[i].key,main_l.r[i].otherinfo);
printf("----------------------------------------------before_HeapSort--\n");

for(int x=0;x<=6;x++)
{
printf("%3d",main_l.r[x].key);
}
printf("\n");
::TreeSort(main_l);
//////////
printf("----------------------------------------------after_HeapSort--\n");
for( x=0;x<=6;x++)
{
printf("%3d",main_l.r[x].key);
}
printf("\n");
//

////////
printf("-----end-----\n");
return 0;
}
......
////////////////////////////////////////////////
-----beg-----
--main_l.length=-858993460--
--i= 0,key=-858993460,otherinfo=-52--
--i= 1,key=-858993460,otherinfo=-52--
--i= 2,key=-858993460,otherinfo=-52--
--i= 3,key=-858993460,otherinfo=-52--
--i= 4,key=-858993460,otherinfo=-52--
--i= 5,key=-858993460,otherinfo=-52--
--i= 6,key=-858993460,otherinfo=-52--
--i= 7,key=-858993460,otherinfo=-52--
--i= 8,key=-858993460,otherinfo=-52--
--i= 9,key=-858993460,otherinfo=-52--
--i=10,key=-858993460,otherinfo=-52--
--i=11,key=-858993460,otherinfo=-52--
------------------after_set_[main_l.length]--
--main_l.length=6--
--i= 0,key=-858993460,otherinfo=-52--
--i= 1,key=-858993460,otherinfo=-52--
--i= 2,key=-858993460,otherinfo=-52--
--i= 3,key=-858993460,otherinfo=-52--
--i= 4,key=-858993460,otherinfo=-52--
--i= 5,key=-858993460,otherinfo=-52--
--i= 6,key=-858993460,otherinfo=-52--
--i= 7,key=-858993460,otherinfo=-52--
--i= 8,key=-858993460,otherinfo=-52--
--i= 9,key=-858993460,otherinfo=-52--
--i=10,key=-858993460,otherinfo=-52--
--i=11,key=-858993460,otherinfo=-52--
------------------after_set_[main_l.r[i].key]--
--main_l.length=6--
--i= 0,key=0,otherinfo=-52--
--i= 1,key=49,otherinfo=-52--
--i= 2,key=38,otherinfo=-52--
--i= 3,key=65,otherinfo=-52--
--i= 4,key=97,otherinfo=-52--
--i= 5,key=76,otherinfo=-52--
--i= 6,key=13,otherinfo=-52--
--i= 7,key=1245120,otherinfo=-52--
--i= 8,key=4210169,otherinfo=-52--
--i= 9,key=-858993460,otherinfo=-52--
--i=10,key=-858993460,otherinfo=-52--
--i=11,key=-858993460,otherinfo=-52--
----------------------------------------------before_HeapSort--
0 49 38 65 97 76 13
--l=4,k=15,k1=7--
-i=0 13 38 13 38 65 13 200 49 38 65 97 76 13 200 200-33686019 0
------------------------------------------------------------
-i=1 38 38 76 38 65 76 200 49 38 65 97 76 200 200 200-33686019 0
------------------------------------------------------------
-i=2 49 49 76 49 65 76 200 49 200 65 97 76 200 200 200-33686019 0
------------------------------------------------------------
-i=3 65 65 76 200 65 76 200 200 200 65 97 76 200 200 200-33686019 0
------------------------------------------------------------
-i=4 76 97 76 200 97 76 200 200 200 200 97 76 200 200 200-33686019 0
------------------------------------------------------------
-i=5 97 97 200 200 97 200 200 200 200 200 97 200 200 200 200-33686019 0
------------------------------------------------------------
----------------------------------------------after_HeapSort--
0 13 38 49 65 76 97
-----end-----
Press any key to continue
////////////////////////////////////////////////
============================================================
e6:asdfasdfasdfasdfasd

============================================================
e7:

============================================================

e8:

============================================================