[8] 結構體

上一節：《循環的模式》

考慮一道題目：計算

使用結構體語法就可以把分子和分母這兩個整數看成一個整體。如下定義：

typedef struct {int numer; int denom;} fraction;

首先用到了typedef語法，把結構體struct {int numer; int denom;}定義成fraction類型。

我們知道 ，下面的程序可以計算 ：

typedef struct {int numer; int denom;} fraction;int putchar(int);void pu(int);void print_fraction(fraction p){ pu(p.numer); putchar(/); pu(p.denom);}fraction add(fraction p, fraction q){ fraction sum; sum.numer = p.numer*q.denom + q.numer*p.denom; sum.denom = p.denom * q.denom; return sum;}int main(){ fraction x = {2, 3}; fraction y = {1, 6}; fraction z = add(x, y); print_fraction(z); return 0;}

運行程序，屏幕上列印出15/18，說明：

• typedef創建的結構體類型fraction可以跟int一樣，當做函數輸入參數的類型和輸出類型
• numer和denom是結構體fraction的成員，結構體成員可以隨意命名 。 可以在fraction類型的變數後面用.符號對成員進行讀寫
• 聲明結構體變數時可以用fraction x = {2, 3}，表示用大括弧裡面的值順次對結構體成員賦值。但如果已經聲明了變數，是不能用這個語法來賦值的。例如fraction x; x = {2, 3};就不符合語法

單詞解釋：

• fraction 分數
• numerator 分子
• denominator 分母
• struct 結構
• type 類型

對於一些完美主義者來說，上面的程序還有一點沒有考慮到，那就是「通分」。15/18的分子分母還可以繼續通分成為5/6，方法是先求出15和18的最大公約數3，然後分子分母同時除以3。所以通分的關鍵是求出兩個整數的最大公約數。一個最樸素的步驟如下：

求a和b的最大公約數： i = a和b的最小數p: if (a % i == 0 並且 b % i == 0) { i就是a和b的最大公約數; 終止; } i = i - 1; goto p;

現在我們基於這個想法來實現求最大公約數的函數gcd：

int gcd(int a, int b) { int i = (a > b ? b : a);p: if (a % i == 0 && b % i == 0) return i; i--; goto p;}

說明：

• x ? y : z被稱為三元運算符，或者if-else運算符，可以認為x ? y : z等價於這樣一個函數int if_else(int x, int y, int z) { if (x) return y else return z; }。當然三元運算符並沒有限定y和z一定是整數。
• &&被稱為邏輯與運算符，A && B的計算方法是：當A為真並且B為真時，計算結果為1（真），否則結果為0（假）。把a % i == 0 && b % i == 0翻譯成人類語言就是「a是i的倍數並且b也是i的倍數」，或者翻譯成「a和b都必須是i的倍數」。
• 同理還有||運算符，也就是邏輯或運算符。A || B的計算方法是：只要A和B有一個為真，計算結果就為1（真），只有A和B都為假時結果才是0（假）。例如a % i == 0 || b % i == 0翻譯成人類語言就是「a是i的倍數或者b是i的倍數」，或者翻譯成「a和b中至少有一個是i的倍數」。
• C語言還支持&和|運算符，我們等會兒在「位運算」小節中，講&&和&的差別，還有||和|的差別。
• i--是i = i - 1和i -= 1的簡寫形式。
• 函數名gcd是greatest common divisor的首字母縮寫。
• 當變數i縮小為1的時候，a % i == 0 && b % i == 0一定為真，因此程序不會陷入死循環。

單詞解釋：

• greatest 最大的
• common 公共的
• divisor 約數

基於函數gcd，我們可以實現支持通分的分數加法了：

typedef struct {int numer; int denom;} fraction;int putchar(int);void print_fraction(fraction);int gcd(int, int);fraction add(fraction p, fraction q){ int numer = p.numer*q.denom + q.numer*p.denom; int denom = p.denom * q.denom; int d = gcd(numer, denom); fraction sum = {numer / d, denom / d}; return sum;}int main(){ fraction x = {2, 3}; fraction y = {1, 6}; fraction z = add(x, y); print_fraction(z); return 0;}

說明：

• 請根據之前「多文件工程」一講的內容，補全函數或者多文件鏈接。

上一個用循環求最大公約數的方法並不是最高效的解法，真正高效的做法叫做輾轉相除法，這個演算法最早在歐幾里得的《幾何原本》中出現，原理如下：

如果a是b的倍數，則b就是a和b的最大公約數否則，如果a÷b=x...y，可以推導出a和b的最大公約數一定是b和y的最大公約數也就是說 gcd(a, b)等於gcd(b, a % b)

利用遞歸可以寫出新的gcd函數：

int gcd(int a, int b){ if (a % b == 0) return b; return gcd(b, a % b);}

如果你還能把這個遞歸函數寫成循環的形式，那麼程序的運行效率會更高一點，方法如下：

int gcd(int a, int b){ int y; while ((y = a % b) != 0) { a = b; b = y; } return b;}

說明：

• 賦值操作也是有返回值的，返回值就是賦的這個值。所以x = ((y = a % b) != 0)相當於y = a % b; x = (y != 0)
• int x = 1; return (x = 3);會返回3，int x = 1; return (x == 3);會返回0，這就是為什麼千萬不要把兩個等號寫成一個等號！

位運算

&是求與位運算，A & B的計算方法是對A和B的每個比特按位求「與」，最簡單的情況是1&1=1, 1&0=0, 0&1=0, 0&0=0。假設char a = 10; char b = 6;，那麼a & b = 2

&運算(按位求與): 00001010 <-- 10的二進位 00000110 <-- 6的二進位--------------------------- 00000010 <-- 2的二進位

|是求或位運算，A | B的計算方法是對A和B的每個比特按位求「或」，最簡單的情況是1|1=1, 1|0=0, 0|1=0, 0|0=0。假設char a = 10; char b = 6;，那麼a | b = 14

|運算(按位求或): 00001010 <-- 10的二進位 00000110 <-- 6的二進位--------------------------- 00001110 <-- 14的二進位

位運算還包括左移運算<<、右移運算>>、按位異或^、按位取反~等，這裡不作介紹了。

定義和聲明結構體的語法

定義結構體的時候可以給結構體指定一個名字，這時結構體的類型名就是「struct+名字」，例如：

struct a {int x; int y;}; // 末尾必須加分號int main() { struct a p = {3, 5}; // p的類型名是「struct a」 return p.x + p.y;}

如果用typedef把「struct+名字」重命名一下，以後就不用加「struct」了。例如：

struct a {int x; int y;};typedef struct a b; // 把類型名「struct a」重命名為「b」int main() { b p = {3, 5}; return p.x + p.y;}

開頭的兩句還可以合併為一句，也就是：

typedef struct a {int x; int y;} b;

這種情況下，結構體的臨時名字「a」也可以被省略，就變成了本講一開始的那種定義結構體類型的方法：

typedef struct {int x; int y;} b;

下一講我們介紹指針和數組。在這之前考慮一下這個問題，結構體tuple有a0, a1, a2, a3這4個成員，怎樣利用循環實現一個max函數，找出a0~a3中的最大值：

typedef struct {int a0; int a1; int a2; int a3;} tuple;int max(tuple); // 怎麼實現這個函數？int main(){ tuple t = {5, 1, 20, 15}; return max(t); // 應該返回20}

下一節：《指針和數組》