gxqcn 发表于 2009-5-2 09:08:16

更优化的版本

/* 对应帖号：http://bbs.emath.ac.cn/viewthread.php?tid=1437&page=2&fromuid=8#pid18832 */
/* 算法功能：矩阵原地逆时针旋转90度（矩阵原地转置、顺时针旋转90度等均可参考） */
/* 算法优化：郭先强 */
/* 修订日期：2009-05-02 */

#include <stdio.h>
#include <stdlib.h>

void output( int *a, int w, int h )
{
    int i, j;
    for ( i=0; i<h; ++i )
    {
      for( j=0; j<w; ++j )
      {
            printf( "%d ", a );
      }
      printf( "\n" );
    }
    printf( "\n" );
}

void transf( int *a, int w, int h )
{
    int k, pos, t, c=w*h;
    div_t xy;

#define TRANSF(pos,w,h)   xy = div( pos, w ); pos = (w-1-xy.rem)*h + xy.quot;

    for( k=0; ; ++k )
    {
      pos = k;
      do
      {
            TRANSF( pos, w, h );
      } while( pos > k );

      if( pos == k )
      {
            t = a;
            do
            {
                TRANSF( pos, w, h );

                a ^= t ^= a ^= t;
                --c;
            } while( pos != k );

            if ( c <= 1 )
                break;
      }
    }

#undef TRANSF
}

int main()
{
    int w=12, h=16, i, j;
    int *a = malloc( w*h*sizeof(int) );

    for( i=0; i<h; ++i )
    {
      for( j=0; j<w; ++j )
      {
            a=i*w+j+1;
      }
    }

    output( a, w, h );
    transf( a, w, h );//旋转
    output( a, h, w );

    free( a );

    return 0;
}此算法相对于 6#，最大的改进是可以提前结束循环。

如果用一个数组标记矩阵各元素是否被置换，则可以更快地判断某些位置上的元素是否已置换，但需多耗元素总数1/8字节的空间；
当然，如果空间充裕，可以另开一个等大的空间，则不存在读写有overlap的问题，算法设计更容易，效率也更高。

无心人 发表于 2009-5-4 08:44:59

一圈圈转吧

gxqcn 发表于 2009-5-5 07:48:35

不是简单意义上的转圈圈，

它要考虑二维变换的几何意义，
又要考虑数据存储的一维特征，
一般人很容易绕晕的。

无心人 发表于 2009-5-5 17:59:10

设计好了就行
页: 1 [2]
查看完整版本: 图像原地旋转 -90°算法