最优二叉查找树算法c++实现

# include
# include
# include

using namespace std;

const double PI = 3.1415926535897932;

class complex
{
double rpart;
double ipart;
public:
complex()
{
rpart=ipart=0.0;
}

complex(double rp,double ip)
{
rpart = rp;
ipart = ip;
}
const complex operator+(const complex & com)
{
complex temp;
temp.rpart = com.rpart+rpart;
temp.ipart = com.ipart+ipart;
return temp;
}
const complex operator*(const complex &com)
{
complex temp;
temp.rpart=rpart*com.rpart-ipart*com.ipart;
temp.ipart=com.ipart*rpart+com.rpart*ipart;
return temp;
}
const complex operator-(const complex & com)
{
complex temp;
temp.rpart = rpart-com.rpart;
temp.ipart = ipart-com.ipart;
return temp;
}
void print() const
{
if(ipart != 0)
{
if(ipart > 0)
cout<else
cout<}
else
cout<}
};

//生成输入
void generate(complex* input,int n)
{
srand(time(0));
for(int i = 0;i < n;i++)
{
input[i] = complex(rand(),0);
}
}

void fft(complex* input,complex* output,int length,int n)
{
int l = length / 2;
complex* odd_input = new complex[l];
complex* oven_input = new complex[l];
complex* odd_output = new complex[l];
complex* oven_output = new complex[l];
for(int i = 0;i < l;i++)
{
odd_input[i] = input[2 * i + 1];//奇数项
oven_input[i] = input[2 * i];//偶数项
}
fft(oven_input,oven_output,l,n);
fft(odd_input,odd_output,l,n);
for(int k = 0;k < l;k++)
{
double z = (2 * k * PI) / length;
complex w = complex((double)cos(z),(double)sin(z));
output[k] = oven_output[k] + w * odd_output[k];
output[k + l] = oven_output[k] - w * odd_output[k];
}

delete[] odd_input,oven_input,oven_output,odd_output;
}

void main()
{
clock_t start,end;
double total = 0;
int k=4;

complex* input = new complex[k];
complex* output = new complex[k];
generate(input,k);

cout<<"a[]:"<for(int j = 0;j < k;j++)
input[j].print();
cout<
start = clock();
fft(input,output,k,k);
end = clock();
total = total + end - start;

cout<<"y[]:"<for(int j = 0;j < k;j++)
output[j].print();
cout<delete[] input,output;

cout<
}