讀古今文學網 > C語言解惑 > 25.5 注意函數設計的多樣化和效率 >

25.5 注意函數設計的多樣化和效率

同樣,函數設計的實現方法也是具有多樣化的,實現的方式也不盡相同。有時可以使用普通函數,有時也可以用宏定義。下面就舉一個例子說明這個問題。

【例25.5】編寫一個將整型數轉換為字符串的程序。

設計函數盡量使用void類型,從而簡化程序設計。

為了設計方便,先將整數轉換為逆序的字符串,然後再將其反序,轉換成正確的字符串。程序中完成將整數轉換為逆序的字符串序後,用printf語句將其輸出以供驗證。


#include <stdio.h>
void itoa
(char *buf
, int num
);          //
轉換函數
void reverse
( char buf
, int i
);          //
反序函數
void swap
( char *a
, char *b
);          //
交換函數
int main
()
{
     int num = 0
;                    //
接受鍵盤輸入應初始化為0
     char buf[128]
;               //
緩存
     printf
(\"
輸入數字: \"
);
     scanf
(\"%d\"
,&num
);
     itoa
( buf
, num
);
     printf
(\"
轉換的字符串:%sn\"
, buf 
);
     return 0
;
}
//
數字-
字符轉換函數
void itoa
(char *buf
, int num
)
{
      int i=0
;
      //
數字轉換為倒序的字符串
      do
      {
            buf[i] = num % 10 + \'0\'
;     //
加數字0
的值完成轉換
            i++
;
            num /= 10
;
      }while
(num 
!=0
);
      buf[i]=\'\0\'
;                    //
添加結束符
      printf
(\"
逆序:%sn\"
,buf
);          //
驗證信息
      reverse
(buf
, i
);               //
反序
}
void reverse
( char buf
, int i
)
{
     int j=0
;
     //
字符串反序
     for
(j=0
; j<i/2
; j++
)
           swap
( &buf[j]
, &buf[i-1-j]
);
}
void swap
( char *a
, char *b
)
{
      char temp
;
      temp = *b
;
      *b = *a
;
      *a = temp
;
}
  

運行示範如下:


輸入數字: 
10250986
逆序:68905201
轉換的字符串:10250986
  

swap函數應該使用指針傳遞參數,調用使用地址符&。如果設計為如下形式:


void swap
( char a
, char b
)
{
      char temp
;
     temp = b
;
      b = a
;
      a = temp
;
}
  

則實現不了。可以定義為宏,則不用使用&傳遞參數。為了簡單,直接將宏定義在reverse函數里。下面使用宏定義swap函數,程序中給出兩種方式:位運算和使用臨時變量進行交換。其實,也可以不使用臨時變量,直接對變量進行運算實現交換。在程序中註釋掉一種,使用位運算實現交換。下面是程序實現和運行示範。


#include <stdio.h>
void itoa
(char *buf
, int num
);          //
轉換函數
void reverse
( char buf
, int i
);          //
反轉函數
int main
()
{
     int num = 0
;                    //
接受鍵盤輸入應初始化為0
     char buf[128]
;                     //
緩存
     printf
(\"
輸入數字: \"
);
     scanf
(\"%d\"
,&num
);
     itoa
( buf
, num
);
     printf
(\"
轉換的字符串:%sn\"
, buf 
);
     return 0
;
}
//
數制轉換函數內部使用宏定義swap
void itoa
(char *buf
, int num
)
{
     int i=0
;
     //
數字轉換為倒序的字符串
     do
     {
             buf[i] = num % 10 + \'0\'
;     //
加數字0
的值完成轉換
             i++
;
             num /= 10
;
     }while
(num 
!`=0
);
     buf[i]=\'\0\'
;                    //
添加結束符
     printf
(\"
逆序:%sn\"
,buf
);          //
驗證信息
     reverse
(buf
, i
);                    //
反序
}
//
定義反序函數reverse
void reverse
( char buf
, int i
)
{
    int j=0
;
    #if 0
    //
定義交換宏實現反轉
    #define SWAP
(a
,b
) do{a=
(a
)+
(b
); 
                        b=
(a
)-
(b
); 
                        a=
(a
)-
(b
); 
                        }while
(0
)
    #endif
    //
使用異或定義交換宏,異或運行快(加法要有進位操作)
    #define SWAP
(a
,b
) do{a=
(a
)^
(b
); 
              b=
(a
)^
(b
);           
              a=
(a
)^
(b
);           
                 }while
(0
)
    //
字符串反序
    for
(j=0
; j<i/2
; j++
)
           SWAP
( buf[j]
, buf[i-1-j]
);
}
輸入數字: 
30257890
逆序:09875203
轉換的字符串:30257890
  

函數設計要在能完成功能的前提下,盡量簡單。盡可能設計為void類型,也是出於這個考慮。

另外,要注意傳結構參數時,是要整體複製結構體的數據。如果結構很大,例如結構裡有很大的數組,這種複製是很費時的。同樣,如果返回值是結構,也需要將結構值整體複製到函數外。為了避免這種費時的操作,常傳遞結構的指針(它們的地址值),返回也是一樣。

尤其要注意字符串常量與字符串數組的區別,字符串常量是分配在全局文字常量區,傳遞效率高。

注意使用一些算法技巧來簡化函數設計,如在第17章的例17.10和例17.11中,用構造不同的數進行位運算以解決統計一個數的二進制中包含1的個數問題。其實,還可以構造出一些特殊數字來簡化求解過程並提高求解的速度。另外,還可以使用一些編程技術提高程序性能,如狀態機等技術。

【例25.6】編寫統計一個數的二進制中包含1的個數的程序。

第17章的兩種編程方法都是使用比較的方法,效率較低。現在使用加法運算。編寫時一般先求正確,正確之後再求優化,不要優化過早,以免進入歧路。

現在先以0xff為例,構造一個數0x55,0x55的特點是01相隔。把兩者進行與運算。在結果一行中的註釋符號裡把它們用序號編號並記為第1次&結果。


  1111 1111
& 0101 0101
  0101 0101     // 
(1
) 
第1
次&0x55
的結果
  

「0xff&0x55=0x55」。解釋一下結果的含義:結果裡的1的含義是0xff如果偶數位有1,則這2位裡的數字就是1(01),由此可知結果代表有4個1。

將0xff右移「0xff>>1」,還是0xff,再與0x55進行&運算。


  1111 1111 >>1  //0xff
右移,  0xff>>1
& 0111 1111      //
再&0x55  
第1
次與
  0101 0101      //
(2
) 
第2
次&0x55
的結果
  

這即相當於把奇數位的1保留,也是4個1。

將兩次二進制數相加,即


  0101 0101    //
(1
)
+ 0101 0101    //
(2
)
  1010 1010    //
(3
) 
第1
輪結果
  

二進制兩兩相加時,不要把它看做一個數,而是表示兩位代表1的個數相加。即原來兩位表示1的個數(二進制)相加,現在的2位就是代表具有幾個1(只能是0或1,2)。上面的結果表明每兩位都是2,下面就是要考慮如何將4個2相加,使其結果代表總共具有的1的位數是8位。

現在的運算結果的十六進制是0xaa,下面進行第二輪操作。這次操作使用0x33,用它與(3)進行&操作。


  0011 0011    //
構造一個數0x33
& 1010 1010    //&
(3
)
  0010 0010    // 
(4
) 
第1
次&0x33
的結果
  

與第1輪一樣,要將(3)的結果移位後再&0x33,但這次是移2位。


  0010 1010   //
將(3
)的結果0xaa>>2
& 0011 0011   //0x33
  0010 0010   // 
(5
) 
第2
次&0x33
的結果
  

進行(5)+(6)運算。


  0010 0010   //
(4
)
+ 0010 0010   //
(5
)
  0100 0100   // 
(6
)
  

經過兩輪得到0x44,第3輪要計算4+4=8,再構造0xf(0000 1111)。與前兩輪的方法一樣,繼續做下去。用0x44,選擇0xf進行第3輪如下:


  0000 1111   //
構造一個數0xf
& 0100 0100   // 
(6
)
  0000 0100   //
(7
) 
第1
次&0xf
的結果
  0000 0100    //
將(6
)>>4
& 0000 1111    //0xf
  0000 0100   //
(8
) 
第2
次&0xf
的結果
+ 0000 0100   //
(7
)
  0000 1000   //
( 8
)+
(7
) = 8
  

由此得出8位的編程方法。固定次數8bit用到2的3次方,先定義3個常量。


#define M1 0x55
#define M2 0x33
#define M3 0x0f
  

對給定的num,將上述3個步驟寫出如下的公式。


(num & M1
) + 
((num >> 1 
) & M1
)
(num & M2
) + 
((num >> 2 
) & M2
)
(num & M3
) + 
((num >> 4 
) & M3
)
  

根據如上公式,編寫如下程序。


#include <stdio.h>
#define M1 0x55
#define M2 0x33
#define M3 0x0f
int main
()
{
     int number
, num=0
;
     printf
(\"
輸入數字: \"
);
     scanf
(\"%d\"
,&number
);
     num=number
;
     num = 
(num & M1
) + 
((num >> 1
) & M1
);
    printf
(\"num=%#xn\"
, num
);
    num = 
(num & M2
) + 
((num >> 2
) & M2
);
    printf
(\"num=%#xn\"
, num
);
    num = 
(num & M3
) + 
((num >> 4
) & M3
);
    printf
(\"num=%#xn\"
, num
);
    printf
(\"%d 
含有%d
個1n\"
, number
, num
);
    return 0
;
}
  

使用255驗證上述算法,第1次是0xaa,第2次是0x44,第3次是0x8,即8個1。


輸入數字: 
255
num=0xaa
num=0x44
num=0x8
255 
含有8
個1
  

32位要定義M4和M5,並構造5個常量。


//32
位程序
 #include <stdio.h>
 #define M1 0x55555555
 #define M2 0x33333333
 #define M3 0x0F0F0F0F
 #define M4 0x0FF00FF
 #define M5 0x0000FFFF
 int main
()
 {
      int number
, num=0
;
      printf
(\"
輸入數字: \"
);
      scanf
(\"%d\"
,&number
);
      num=number
;
      num = 
(num & M1
) + 
((num >> 1 
) & M1
);
      num = 
(num & M2
) + 
((num >> 2 
) & M2
);
      num = 
(num & M3
) + 
((num >> 4 
) & M3
);
      num = 
(num & M4
) + 
((num >> 8 
) & M4
);
      num = 
(num & M5
) + 
((num >> 16
) & M5
);
      printf
(\"%d 
含有%d
個1n\"
, number
, num
);
      return 0
;
}
 

運行示範如下:


輸入數字: 
65535
65535 
含有16
個1
輸入數字: 100
100 
含有3
個1
輸入數字: 0
0 
含有0
個1
  

程序中去掉了打印每次結果的信息,這個程序很確定,不足之處是0也要5次,但也是很確定的5次,所以也是可以的。

很多程序還要受到條件的影響,約瑟夫環就是典型的例子。根據要求,可以使用一維數組、二維數組、結構、動態內存、鏈表、循環鏈表等手段編寫求解程序。可以參考拙作《C程序設計課程設計(第2版)》(機械工業出版社)。