《C Programming Language》書中在遞歸這一節預留了兩個使用遞歸實現的函數,其中itoa函數是用來將一個整數轉換為一個字符串。書中已有使用循環實現的版本,但是直接得到的是反序的結果,需要最後調用reverse函數。而遞歸版本則可以避免這個問題。
首先使用原接口void itoa(int n, char s[])進行實現,發現遞歸調用的時候總是錯誤,輸出的結果只能得到整數n的最高位和最低位的數字。代碼如下:
1 void itoa(int n, char* s) 2 { 3 if (n < 0) 4 { 5 *s = '-'; 6 s++; 7 } 8 if (abs(n) / 10) 9 itoa(abs(n) / 10, s++); 10 *s = abs(n) % 10 + '0'; 11 }
基本思想:使用字符指針s進行移動,遞歸調用的過程中進行指針的自增。但是使用gcc編譯後運行結果並不正確。只能輸出整數n的最高位和最低位的兩個數字。
錯誤原因:經過仔細調試,發現字符指針參數每次遞歸調用時,傳入的s++
這個變量時進行了復制,也就是在後續的遞歸調用中對指針s的自增操作不會反映到第一次調用的指針s上去,因此,第一次調用這個函數並最終調用*s = abs(n) % 10 + '0';
這一語句時,指針s指向的是字符數組的第二個位置。就將整數n的最低位放在第二個位置,而整數n的最高位一直進行遞歸調用並將參數指針變量復制(一直指向第一個位置),也就放在了第一個位置。最後返回的結果就只有兩個數字。
針對上述遇到的問題,在網上搜索了這個問題。使用最多的就是使用局部靜態變量保存字符數組的下標,參考http://blog.csdn.net/long_xing/article/details/2212450。但是,另外一篇博客中的實現存在邏輯錯誤,提前給字符數組賦“\0”,參見http://blog.csdn.net/roma823/article/details/6546719。
經過一段時間的思考,最終想到的辦法就是二級字符指針,因為使用字符指針函數參數時,遞歸調用傳入的字符指針使用了復制,這應該是編譯器對字符指針(相當於字符串),在進行傳遞參數時使用復制指針(也就是復制字符串)這種實現,與普通意義上的指針參數調用時直接操作源指針的思想有所區別。因此在使用一個二級字符指針,每次傳遞的是指向字符串的同一個指針,這樣就不會出現遞歸調用過程中對指針的自增操作對上一級調用函數無效的情況,代碼如下:
1 void itoa(int num, char** s) 2 { 3 if (num < 0) 4 { 5 **s = '-'; 6 (*s)++; 7 } 8 if (abs(num / 10) > 0) 9 { 10 itoa(abs(num / 10), s); 11 (*s)++; 12 } 13 **s = abs(num % 10) + '0'; 14 }
上述版本使用了abs庫函數,可以轉換最大負整數。測試如下:
1 int main() 2 { 3 char s[100], *ps = s; 4 itoa(12345, &ps); //測試正整數 5 *(++ps) = '\0'; 6 printf("%s\n", s); 7 8 ps = s; 9 itoa(-2147483647, &ps); //測試最大的負整數(32 bits) 10 *(++ps) = '\0'; 11 printf("%s\n", s); 12 13 return 0; 14 }