算法---6.堆排序之树形打印

1. 

1.2 代码

#include <stdio.h>
#include <stdlib.h>
#define dbmsg(fmt, args ...) printf("%s:%s[%d]: "fmt"\n", __FILE__,__FUNCTION__, __LINE__,##args)
#define SWAP(x,y) (x=(x)+(y),y=(x)-(y),x=(x)-(y))
#define POW(x) (1<<(x))

#define LEN 33

int is_sum_pow2(int n)
{
    int t = n+1;
    return n&t;
}

int get_level(int num)                 //确定树的深度，这儿用了bsr指令
{
    int ret;
    __asm__ volatile("movl %1,%%ecx\n"
        "xor %%eax, %%eax \n"
        "bsr %%ecx, %%eax \n"
        "movl %%eax, %0 \n":"=r"(ret):"r"(num):);
    return ret;
}

int dump_tree(int* arr, int len)
{
    int i,j;
    int level = get_level(len)+1;               //len=1时，bsr返回0，bsr返回值是从0开始的，所以这儿需要加1
    int first = 1;
    for(i=0; i<len; i++)
    {
        if(first)                               //这儿的if else是为了确定数据在该层的位置
        {
            for(j=0; j<POW(level-1)-1; j++)    //每行打印首字符之前插入POW(level-1)-1个单位
                printf("  ");
            first = 0;
        }else {
            for(j=0; j<POW(level)-1; j++)     //每行打印非首字符插入POW(level)-1个单位
                printf("  ");
        }
        printf("%2d", arr[i]);
        if( is_sum_pow2(i+1) == 0)             //这儿是为了确定数据在第几层
        {
            printf("\n");
            level--;
            first = 1;
        }
    }
    printf("\n");
    return 0;
}

int main ( int argc, char *argv[] )
{
    int i, len;
    int arr[1024];
    len = LEN;
    for(i=0; i<len; i++)
        arr[i] = i;
    dump_tree(arr, len);
    return EXIT_SUCCESS;
}

这儿的单位是按数据长度来算的，
如果数据长度是1 (0-9),则这儿的单位是1，则要打印1个空格
如果数据长度是2 (0-99),则这儿的单位是2，则要打印2个空格
如果数据长度是3 (0-999),则这儿的单位是3，则要打印3个空格

1.3 运行结果

                                                               0
                               1                                                               2
               3                               4                               5                               6
       7               8               9              10              11              12              13              14      
  15      16      17      18      19      20      21      22      23      24      25      26      27      28      29      30  
31  32

1.4 这儿有两个问题要确认
1.4.1 确定数据在第几层

1.4.2 数据在该层的位置
如果要打印的数据长度都是1的话，有如下分析:  

L1: @@@@@@@@@@@@@@@0                    //首字符空15, 如果还有数的话，可以推出其余空15+POW(4)=31
L2: @@@@@@@1@@@@@@@@@@@@@@@2            //首字符空7, 其余空15
L3: @@@3@@@@@@@4@@@@@@@5@@@@@@@6        //首字符空3, 其余空7
L4: @7@@@8@@@9@@@0@@@1@@@2@@@3@@@4      //首字符空1, 其余空3
L5: 5@6@7@8@9@0@1@2@3@4@5@6@7@8@9@0     //首字符空0, 其余空1

a. 因为要打印的数字本身会占用一个位置，所以要 -1
b. 首字符所在的位置是POW(倒数的n - 1),  例:L5的char1的位置POW(1-1)=1, L2的char1的位置POW(4-1)=8，
    为了使这个数据在第1或第8的位置上，前面需要插入的空格数为POW(倒数n-1)-1个.
c.中间的字符需要插入的空格是 POW(倒数的n)-1个,例: L5要插入POW(1)=1,L2要插入空格数POW(4)-1=15

1.5 关于bsr指令
BSF(Bit Scan Forward): 位扫描找1, 低 -> 高
BSR(Bit Scan Reverse): 位扫描找1, 高 -> 低