编程珠玑读书笔记——串的转置算法

将一个具有n个元素的一维向量向左旋转i个位置.假若n = 8, i = 3, 那么向量abcdefgh 旋转后为defghabc.

1、将待旋转的向量看作是ab两段,假设a比b短,将b分割为b1和b2使b2长度与a相等.

交换a、b2,这样ab1b2变为b2b1a这样a已经在自己最终的位置上了.下面的工作就变成了旋转b2b1.

/**********************************

       Fction:将字符串按条件转置

       char * p:字符串首地址

       int t:所要选择部分的长度

       int n:串的总长度

Return:void

**********************************/

void  Q(char *p,int t,int n){

         char tmp;

         int i;

         int flag = 0;                                   //标记变量

         char *p1 ;                                     //用于指向b2的头地址

         if(n !=1 && n != 0)

         {       

/*********************************************

                   判断t即所要旋转的长度是否大于另一部分,因为我们

                   选择短的那部分,相应的分解长的那部分.所以若t>n-t

                   则把短的那部分赋值给t

*********************************************/

                   if(t>n-t){

                            t = n-t;

                            flag = 1;

                   }

                   //对b2串头地址的初始化

                   p1 = p+n-t;

                   //开始交换变量

                   for(i = 0;i<t;i++){

                            tmp = *(p1+i);

                            *(p1+i) = *(p+i);

                            *(p+i) = tmp;

                   }

/*********************************************

                   根据标志位选择递归

                   若形参t即为分解部分即ab(这里假设a比b短)

                   则a已经在最终位置固串首地址不变,t不变,所选择串总长度-t

                   若是ba,则t为需分解的串的长度.这里为了简化代码

                   我们还把b1b2a看成ab1b2固上文对t赋值n-t

                   但a被换置前端亦为最终位置固.总串首地址后移t

                   而总长度-t,下次所旋转的长度在n-t的基础上再-t

*********************************************/

                   if(flag)

                            Q((p+t),n-2*t,n-t);

                   else

                            Q(p,t,n-t);

         }

额~ 太晚了  今天先睡觉