章4函數和遞歸結構體
P66
學習目标
| ！多參數，單傳回值的數學函數定義和使用方法 ！typedef定義結構體 ！assert宏幫助調試 函數調用時用實參給形參指派過程 定義局部變量/全局變量 ！調用棧和棧幀，用gdb檢視調用棧并選擇棧幀 位址和指針 遞歸定義和遞歸函數 *可執行檔案中正文段/資料段/BSS段 *堆棧段，棧溢出的常見原因 |
數學函數
函數的傳回類型最好是int/double/char（特殊int），若是數組則較為麻煩
hypot（x,y）:計算直角三角形斜邊長（不是ANSI C的函數）
使用結構體函數
| struct Point{ double x,y; }; |
| double dist(struct Point a, struct Point b){ return hypot(a.x-b.x,a.y-b.y); } |
重定義方法定義使用：
| typedef struct{ double x,y; } Point; |
| double dist(Point a, Point b){ return hypot(a.x-b.x,a.y-b.y); } |
定義方法：struct 結構體名{域定義;};
注意花括号後有分号
重定義法定義：typedef struct{域定義;}類型名;
即使最終答案在資料類型的範圍之内，中間的計算結果仍然可能溢出
結構體成員變量的通路
如果通過結構體指針通路結構體，或結構體成員變量本身是指針，可以用->。
否則用.
Error: base operand of '->' has non-pointer type ''
結構體操作函數
Memcpy 頭檔案string.h
strcpy和memcpy主要有以下3方面的差別。
1、複制的内容不同。strcpy隻能複制字元串，而memcpy可以複制任意内容，例如字元數組、整型、結構體、類等。
2、複制的方法不同。strcpy不需要指定長度，它遇到被複制字元的串結束符"\0"才結束，是以容易溢出。memcpy則是根據其第3個參數決定複制的長度。
3、用途不同。通常在複制字元串時用strcpy，而需要複制其他類型資料時則一般用memcpy
例4.1組合數
解決溢出（利用組合數兩端對稱特性
| #include<stdio.h> int factorial(int n,int m){ int i,res=1; for(i=n;i>=m;i--){ res*=i; } // printf("%d\t%d\t%d\n",n,m,res); return res; } int main(){ int m,n,res; scanf("%d%d",&n,&m); if(m>n/2){ res=factorial(n,m)/factorial(n-m,1); }else{ res=factorial(n,n-m)/factorial(m,1); } printf("%d",res); return 0; } |
謂詞、for條件多次計算、assert宏
謂詞：判斷一個事物是否具有某個性質（數字是否是素數）
謂詞函數編寫一般規則：命名“is_xxx”，傳回int，0表示假，非0表示真
盡量保證對任何參數都能得到正确結果，否則表明缺陷，以免誤用
判斷素數技巧：1.x%i==0；2.枚舉因數時不超過sqrt(x),若超過，則乘積大于x；3.發現因數及時退出
特殊數：n=1會被判斷為素數，太大數i*i計算邊界時超過int最大值，溢出變成負數
使用sqrt不易溢出，但要處理精度誤差。m=floor(sqrt(x)+0.5);
使用assert.h中的assert宏限制非法的函數調用,傳入函數不符合條件則程式異常終止，并給出提示資訊（幫助調試檢查參數）：assert(x>=0);不符合x>=0則退出
在實際系統中不能因為一個地方參數錯誤，整個程式異常退出。在編寫和調試時可通過assert幫助提升程式品質
例4.2孿生素數
| #include<stdio.h> #include<math.h> int prime(int m){ int i; for(i=2;i<=sqrt(m);i++){ if(m%i==0)return 0; } return 1; } int main(){ int m; scanf("%d",&m); if(m%2==0)m--; for(;m>2;m-=2){ if(prime(m)&&prime(m-2))break; } printf("%d %d",m-2,m); return 0; } |
| 改進： #include<stdio.h> #include<math.h> #include<assert.h> int is_prime(int x){ int i,m; assert(x>=0); if(x==1)return 0; m=floor(sqrt(x)+0.5); for(i=2;i<=m;i++){ if(x%i==0)return 0; } return 1; } int main(){ int m; scanf("%d",&m); if(m%2==0)m--; assert(m>=0); for(;m>2;m-=2){ if(is_prime(m)&&is_prime(m-2))break; } printf("%d %d",m-2,m); return 0; } |
指針與位址
函數的形參和函數内聲明的變量都是函數的局部變量。無法通路其他函數的局部變量。存儲空間臨時配置設定，函數執行完畢釋放。
函數外聲明的變量是全局變量，可以被任何函數使用
調用棧（call stack）由多個棧幀組成，每個棧幀對應着一個未運作完函數。在gdb中可以用backtrace（簡稱bt）列印所有棧幀資訊，若要用p指令列印一個非目前棧幀的局部變量，可以用frame指令選擇另一個棧幀
gdb是源碼級調試器
編譯程式：
| gcc test.cpp -o test -Wall -g |
運作gdb
| gdb test.exe |
檢視源碼
l
| 顯示： (gdb) l 1 #include<stdio.h> 2 void swap(int a,int b) { 3 int t=a;a=b;b=t; 4 } 5 int main() 6 { 7 int a=3,b=4; 8 swap(a,b); 9 printf("%d %d\n",a,b); 10 return 0; |
（swap函數第4行結束，但還沒有傳回）
加斷點并運作：
| (gdb) b 4 Breakpoint 1 at 0x401550: file test.cpp, line 4. (gdb) r Starting program: C:\Users\laugo\test.exe [New Thread 5004.0xa20] [New Thread 5004.0x21c0] Breakpoint 1, swap (a=4, b=3) at test.cpp:4 4 } |
（碰到斷點在第四行停止，這時）
檢視調用棧
| (gdb) bt #0 swap (a=4, b=3) at test.cpp:4 #1 0x0000000000401580 in main () at test.cpp:8 包含兩個棧幀：#0和#1，1号是0的上一個棧幀，0x0000000000401580是swap函數的傳回位址 |
| (gdb) p a $1 = 4 (gdb) p b $2 = 3 P指令列印變量值 |
| (gdb) up #1 0x0000000000401580 in main () at test.cpp:8 8 swap(3,4); (gdb) p a $3 = 3 (gdb) p b $4 = 4 up選擇上一個棧幀進行檢視 |
退出gdb
| (gdb) q A debugging session is active. Inferior 1 [process 5004] will be killed. Quit anyway? (y or n) y |
用指針實作變量交換，修改代碼
| #include<stdio.h> void swap(int *a,int *b) { int t=*a;*a=*b;*b=t; } int main() { int a=3,b=4; swap(&a,&b); printf("%d %d\n",a,b); return 0; } |
gdb調試
| C:\Users\laugo>gcc test.cpp -o test -Wall -g C:\Users\laugo>gdb test.exe GNU gdb (GDB) 7.8.1 Copyright (C) 2014 Free Software Foundation, Inc. License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html> This is free software: you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law. Type "show copying" and "show warranty" for details. This GDB was configured as "x86_64-w64-mingw32". Type "show configuration" for configuration details. For bug reporting instructions, please see: <http://www.gnu.org/software/gdb/bugs/>. Find the GDB manual and other documentation resources online at: <http://www.gnu.org/software/gdb/documentation/>. For help, type "help". Type "apropos word" to search for commands related to "word"... Reading symbols from test.exe...done. (gdb) l 1 #include<stdio.h> 2 void swap(int *a,int *b) { 3 int t=*a;*a=*b;*b=t; 4 } 5 int main() 6 { 7 int a=3,b=4; 8 swap(&a,&b); 9 printf("%d %d\n",a,b); 10 return 0; (gdb) b 4 Breakpoint 1 at 0x40155e: file test.cpp, line 4. (gdb) r Starting program: C:\Users\laugo\test.exe [New Thread 8928.0x280c] [New Thread 8928.0x14c8] Breakpoint 1, swap (a=0x62fe4c, b=0x62fe48) at test.cpp:4 4 } |
| (gdb) bt #0 swap (a=0x62fe4c, b=0x62fe48) at test.cpp:4 #1 0x000000000040158f in main () at test.cpp:8 |
| (gdb) p a $1 = (int *) 0x62fe4c (gdb) p b $2 = (int *) 0x62fe48 (gdb) p *a $3 = 4 (gdb) p *b $4 = 3 |
| (gdb) up #1 0x000000000040158f in main () at test.cpp:8 8 swap(&a,&b); |
| (gdb) p a $5 = 4 (gdb) p b $6 = 3 (gdb) p &a $7 = (int *) 0x62fe4c (gdb) p &b $8 = (int *) 0x62fe48 |
#0棧的ab，*a*b分别對應#1棧的&a&b，ab
位址0x開頭的整數以16進制表示，
(int *)指針*a代表a指向的變量，而不僅是a指向變量所擁有的值
(*a)++代表a指的值+1，不是*a++（++運算符優先級高）
錯誤2：   |
不要濫用指針
遞歸
遞歸
| #include<stdio.h> int f(int n){ return (n==0)?1:f(n-1)*n; } int main(){ printf("%d",f(3)); return 0; } |
三元運算符?:。a?b:c的含義是：如果a為真，則b，如果a為假，則c
gdb調試
| C:\Users\laugo>gcc test.cpp -o test -Wall -g C:\Users\laugo>gdb test.exe Reading symbols from test.exe...done. (gdb) l 1 #include<stdio.h> 2 int f(int n) { 3 return n==0?1:f(n-1)*n; 4 } 5 int main() 6 { 7 printf("%d\n",f(3)); 8 return 0; 9 } |
| 用b f設定斷點，除了按行号設定，也可以用函數名，斷點将設定在函數開頭 (gdb) b f Breakpoint 1 at 0x40153b: file test.cpp, line 3. (gdb) r Starting program: C:\Users\laugo\test.exe [New Thread 10056.0x21f0] [New Thread 10056.0x1fb0] Breakpoint 1, f (n=3) at test.cpp:3 3 return n==0?1:f(n-1)*n; (gdb) s Breakpoint 1, f (n=2) at test.cpp:3 3 return n==0?1:f(n-1)*n; (gdb) s Breakpoint 1, f (n=1) at test.cpp:3 3 return n==0?1:f(n-1)*n; (gdb) Breakpoint 1, f (n=0) at test.cpp:3 3 return n==0?1:f(n-1)*n; (gdb) 4 } 第一次斷點處傳入參數n=3，接下來調用f(3-1)…直到0 |
| 檢視調用棧 (gdb) bt #0 f (n=0) at test.cpp:4 #1 0x000000000040154e in f (n=1) at test.cpp:3 #2 0x000000000040154e in f (n=2) at test.cpp:3 #3 0x000000000040154e in f (n=3) at test.cpp:3 #4 0x0000000000401576 in main () at test.cpp:7 (gdb) s 4 } (gdb) bt #0 f (n=1) at test.cpp:4 #1 0x000000000040154e in f (n=2) at test.cpp:3 #2 0x000000000040154e in f (n=3) at test.cpp:3 #3 0x0000000000401576 in main () at test.cpp:7 (gdb) s 4 } (gdb) bt #0 f (n=2) at test.cpp:4 #1 0x000000000040154e in f (n=3) at test.cpp:3 #2 0x0000000000401576 in main () at test.cpp:7 (gdb) s 4 } (gdb) bt #0 f (n=3) at test.cpp:4 #1 0x0000000000401576 in main () at test.cpp:7 (gdb) s 6 main () at test.cpp:8 8 return 0; (gdb) bt #0 main () at test.cpp:8 每次s，都會有一層遞歸調用終止， 每次遞歸調用多一個棧幀，調用結束少一個棧幀，直到傳回main。 函數調用都是建立新棧幀，傳遞參數，修改目前代碼行。在函數體執行完後删除棧幀，處理傳回值，修改目前代碼行 |
段錯誤與棧溢出
測試f(100000000),不是整數溢出，而是沒有輸出
-g編譯後gdb載入r執行，報錯
| (gdb) r Starting program: C:\Users\laugo\test.exe [New Thread 5044.0x26e4] [New Thread 5044.0x383c] Program received signal SIGSEGV, Segmentation fault.段錯誤 0x0000000000401549 in f (n=99956661) at test.cpp:3 3 return n==0?1:f(n-1)*n; 可執行檔案：UNIX/Linux用ELF格式，DOS是COFF格式，Windows是PE格式（由COFF擴充）這些格式都有段概念：Segmentation 段是二進制檔案内的區域，所有某種特定類型資訊被儲存在裡面。Size程式可以得到可執行檔案中各個段的大小 |
| C:\Users\laugo>size test.exe text data bss dec hex filename 10404 2344 2656 15404 3c2c test.exe 由正文段（存儲指令）、資料段（存儲已初始化的全局變量）、bbs段組成（存儲未指派的全局變量所需空間），總共15404，十六進制表示為3c2c 不能越界通路，否則段錯誤 每次調用往調用棧加一個棧幀，是以越界了，又稱棧溢出（Stack Overflow） |
| Linux棧空間的大小由系統指令ulimit指定， windows棧大小存儲在可執行檔案（連接配接程式ld），gcc在編譯時可以指定可執行檔案的棧大小： -Wl,--stack=<byte count> -Wl,--stack=16777216 |
把較大的數組放在main外，因為局部變量也放在堆棧段，棧溢出不一定是遞歸太多，也也可能是局部變量開太大