t***e
发帖数: 446 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: tetee (fatfish), 信区: JobHunting
标 题: 请教一道题
发信站: BBS 未名空间站 (Mon Oct 29 11:50:00 2012, 美东)
如图，每个node都和下面两个临近的node相连，这样的数据结构怎么设计呢？ | a*****i
发帖数: 268 | | d****n
发帖数: 1637 | 3 All data structure can be single array
my code 见笑了
#include
#include
int main( int argc, char *argv[]){
int i;
//当前的array index
int num=atoi(argv[1]);
//穷举出当先index所在level: i
int sum=0;
for(i=0;sum
sum+= i*(i+1)/2 ;
int left,right;
//左面的child index
left=num+i-1;
//右面的 child index
right=num+i;
printf("num %d ; left %d ; right %d\n",num,left, right);
}
//没有parent 计算。
//不用穷举，可以存level的计算于一个临时数组
//另外，这个是杨辉三角吧，所以有O(1)的 deindex | d****n
发帖数: 1637 | 4 又拓展了一下，给出parent link和buffed level computation
#include
#include
int *buff=NULL;
int buff_size=1024;
int buff_used=0;
int level(int query ){
while( buff[buff_used-1]
{
if ( buff_size <=buff_used ){
buff_size<=1;
buff=(int *)realloc( buff,sizeof(int)*buff_size );
}
buff_used++;
buff[buff_used]=(buff_used+1 )*(buff_used+1+1)/2;
}
//binary search
int high,low,mid;
high=buff_used;
low=0;
while( low<=high ){
mid=(low+high)/2;
if(buff[mid]>=query )
high=mid-1;
else
low=mid+1;
}
return low+1;
}
int main( int argc, char *argv[]){
if(buff==NULL) buff=(int *)malloc(sizeof(int)*buff_size);
buff[0]=1;
int i;
int num=atoi(argv[1]);
i=level(num);
int left_child,right_child,left_parent,right_parent;
left_child=num+i-1;
right_child=num+i;
left_parent=num-i;
right_parent=num-i+1;
printf("num %d ; lvl %d\n" ,num, i);
printf("left_child %d ; right_child %d\n", left_child, right_child);
if (level(left_parent)==(i-1))
printf("Exists left Parent %d\n",left_parent);
if (level(right_parent)==(i-1))
printf("Exists right Parent %d\n",right_parent);
free(buff);
}
//output
/*
./a.out 101
num 101 ; lvl 14
left_child 114 ; right_child 115
Exists left Parent 87
Exists right Parent 88
./a.out 7
num 7 ; lvl 4
left_child 10 ; right_child 11
Exists right Parent 4
*/ |
|
