数据结构=brainfucking.作业.

设计一个算法,用尽可能少的辅助空间将顺序表前 m 个元素和后 n 个元素进行互换. {a1,a2,a3..am,b1,b2,b3..bn} => {b1,b2,b3..bn,a1,a2,a3..am} 让我想起某单词. brainfucking. now let's fucking. 问题简化到 int 数组吧. 差不多. 函数原型:

void swapSeq(int *lst, int m, int n);

惯例, lst 索引为 1..(m n) "用尽可能少的辅助空间"..... 果然 brainfucking. 函数里定义某数组, 把 b1~bn, a1~am 按顺序复制再拿出来, OK. 不好玩. 直觉告诉我们, 既然是 brainfucking..... Show 实现.

void swapSeq(int *lst, int m, int n)
{
   int i,tmp;
   if(m n<= 1)
         return ;
   for(i=1; i<= m && i<= n; i )
     {
         tmp = lst[i];
         lst[i] = lst[m i];
         lst[m i] = tmp;
     }
   if(m> n)
       return swapSeq(lst n, m-n, n);
   if(n> m)
       return swapSeq(lst m, m, n-m);
}

---

发现可爱的尾递归. OK, 立即抛弃, 上 while~!

void swapSeq(int *lst, int m, int n)
{
   int i,tmp;
   while(m n> 1)
   {
       for(i=1; i<= m && i<= n; i )
         {
             tmp = lst[i];
             lst[i] = lst[m i];
             lst[m i] = tmp;
         }
       if(m> n)
       {
           lst = n;
           m = m-n;
       }
       else if(n> m)
       {
           lst = m;
           n = n-m;
       }
       else
           return ;
   }
}

---

抛弃题目本质. BT 下. BT 无罪.

void swapSeq(int *lst, int m, int n)
{
   int i;
   if(m n<= 1)
         return ;
   for(i=1; i<= m && i<= n; i )
     {
         lst[i]^= lst[m i];
         lst[m i]^= lst[i];
         lst[i]^= lst[m i];
     }
   if(m> n)
       return swapSeq(lst n, m-n, n);
   if(n> m)
       return swapSeq(lst m, m, n-m);
}

---

其实递归未优化的消耗还是很大的, 开优化另说.

void swapSeq(int *lst, int m, int n)
{
   int i;
   while(m n> 1)
   {
       for(i=1; i<= m && i<= n; i )
         {
             lst[i]^= lst[m i];
             lst[m i]^= lst[i];
             lst[i]^= lst[m i];
         }
       if(m> n)
       {
           lst = n;
           m = m-n;
       }
       else if(n> m)
       {
           lst = m;
           n = n-m;
       }
       else
           return ;
   }
}