國立成功大學
資源系
計算機概論(C 語言講義)
陳 日 昇 編 著
電 子 計 算 機 中 心
中 華 民 國 1 O 9 年 9 月
上課內容
1. 從一個簡單程式談起
2. 基本知識
3. 輸出與輸入
4. 控制敘述
5. 迴圈敘述
*** 交第一個程式 ***
6. 前處理程式
7. 遞迴運算
8. pointer 與 array
9. 字元串
10. 位元運算
*** 交第二個程式 ***
11. unix 環境下軟體方法論
*** 交第三個程式 ***
/* 計算成績平均值
*/
#include <stdio.h>
#define quiz_rate 0.1
#define hw_rate 0.15
#define proj_rate 0.25
#define mid_rate 0.2
#define final_rate 0.3
main()
{
char name[10];
int
quiz_score,hw_score,proj_score,mid_score,final_score;
float average;
printf("Please
enter student name .\n")；
while
(scanf("%s",name)＝＝1){
printf
("Please enter quiz, hw, proj, mid, final.\n");
if (scanf("%d %d
%d %d %d ", &quiz_score, &hw_score,&proj_score,
&mid_score, &final_score)＝＝5){
average＝quiz_score＊quiz_rate＋hw_score＊hw_rate＋proj_score＊
proj_rate＋mid_score＊mid_rate＋final_score＊final_rate；
printf ("%s final score is %3.1f\n",name,average)；
break;
}
}
}
：a.out
Please enter student name
Peter
Please enter quiz, hw, proj, mid, final.
90 87 95 75 80
Peter final score is 84.8
基本常識
1.字元與語言要素
小字字母 a b c
. . . z
大字字母 A B C
. . . Z
數字
0 1 2 3 4 5 6 7 8 9
其他的字元 + - * / =
( ) { } [ ] < > ' " `
# $ % & _ | ^ ~ \ . , ; : ?
空白字元(white space characters)，例如：空格(blank)和定位字元(tab)。
ｃ的語言要素就是由這些字元所組合而成，基本的語言要素有識別字(identifiers)
，關鍵字(keywords)，常數(constants)，運算符號(operators)以及分隔符號(separators)。
以一個簡單的程式為例：
/* Read in two integers
and print their sum. */
main()
{
int a,b,sum;
printf("Input
two integers: ");
scanf("%d
%d",&a,&b);
sum = a + b ;
printf("\nThe
sum of %d and %d is %d.\n\n",a,b,sum);
}
/*
Read in two integers and print their sum. */
在"/*"和"*/"之間的文字是程式的注解，編譯程式將注解視為空白字元來處理。
main()
{
int a,b,sum;
函數名稱 main 是一個識別字，" ( "，" ) "，"
{ "是分隔符號，int是關鍵字。a，
b，及sum都是識別字，而"，"和";"也是分隔符號。
printf("Input
two integers: ");
scanf("%d
%d",&a,&b);
函數名稱printf和scanf也是識別字，其左右括弧用以告知編譯程式，這兩個識別
字是函數，它們都存放在標準程式庫中，我們不需要重新定義它們。
"Input two
integers: "
由雙引號括起來的一連串字元代表字串常數(string
constant )。
&a,&b
"
& " 是一個運算符號.
sum = a + b ;
"
- " 及 " +
"都是運算符號。在字元間的空格可以忽略不計，因此也可以寫成：
sum=a+b;
或
sum =
a + b ;
但是不可以寫成這樣 :
s
u m = a + b ;
2 識別字
識別字是由一串字母，數字和一個特殊字元 "底線" ( _, underline )所組成，而且
第一個字元必須是字母或是底線。至於識別字的選擇方式應該是便於記憶和具
有實質意義的，以增加程式的可讀性和說明性。以下是一些合法的識別字：
n
_id
iamanidentifier
i_am_an_identifier
而非：
not#me
101_south
-plus
3 關鍵字
不同的識別字使不同的事物在程式中具有唯一的名稱。ｃ語言保留了一些
特殊的字彙，稱為關鍵字。
關鍵字是所保留的識別字，而且每一個都有它特殊的意義，不能被重新定
義或是使用在別的環境。
關鍵字
===================================================================
auto
default
extern
int sizeof
union
break do
float
long static
uigned
case
double
for
register
struct void
char else goto return
switch while
continue enum if short
typedef
4 運算符號
許多特殊字元具有特別的意義，下列是幾個算術運算符號：
+ - * / %
它們分別代表加法、減法、乘法、除法以及模數的算術運算。
5 運算符號的優先順序與結合律
運算式的計算要依據運算符號的優先順序(precedure)與結合律(associativity)的
規則，但是在括弧內的運算式則必須先計算。括弧使運算看來更明白，也能改
變運算的先後次序，以下列的運算式為例：
1 + 2 * 3
由於 "*"的優先順序高於 "+"，亦即要先作乘法再作加法，因此計算後所得結
果為 7 。這式子也可寫成這樣：
1 + ( 2 * 3 )
另一方面，由於括弧中的運算式要先計算，因此下列所示
( 1 + 2 ) * 3
的運算結果就不一樣了；其答案為 9 。再看下面這個運算式
1 + 2 - 3 + 4 - 5
因為 "+"和 "-"具有相同的優先順序，根據結合律，這式子要由左而右計算，
這就相當於
( ( ( 1 + 2 ) - 3 ) + 4
) - 5
下面的表格是一些運算符號的優先順序與結合律。
┌────────────┬─────────┐
│ 運 算
符 號
│ 結 合 律
│
├────────────┼─────────┤
│ - (單元) ++ -- │
由 右 至
左 │
├────────────┼─────────┤
│
* / %
│ 由 左
至 右 │
├────────────┼─────────┤
│
+
-
│
由 左 至
右 │
├────────────┼─────────┤
│
= += -= *= /= │ 由 右
至 左 │
└────────────┴─────────┘
6 遞增與遞減運算符號
" ++ "遞增和" --
"遞減都是單元運算符號，其與單元運算的負號有著相同的
優先順序以及 "由右至左" 的結合律，但僅適用於變數而不能用於常數或普通的
運算式。此外，遞增與遞減運算符號可以是前置式 ( prefix )，也可以是後置式
(postfix)，而兩者可能有不同的效果。以下是合法的例子：
++j
j++
--cnt
cnt--
而非：
777++ /* 常數不能被遞增 */
++ (a * b - 1) /* 不能對運算式作遞增 */
++i 和i++ 都具有一個值，而且使得記憶體中 i 的內含值增加 1，只是++i
在計算 i 之前就增加 i 的內含值，i++則是先計算 i 值再增加 i 的內含值。
請看程式的說明：
int a,b,c = 0 ;
a = ++c ;
printf
("%d %d\n",a,c);
/* 印出 1 1 */
b = c++ ;
printf
("%d %d\n",b,c);
/* 印出 1 2 */
--i
及i-- 的運算方式類似二個遞增的式子，不同的是記憶體中 i 的內含值減
少1。不同於其他的運算符號，++和--會改變記憶體中變數的內含值。而如
"+"
這個運算符號則並不會這麼做。例如 a + b 的運算式會產生一個值，但 a 和 b 體
內含值並不會改變。我們可以說++和--是具有副作用 (side effect)的運算符號。
7 設定運算符號
我們可以利用設定敘述來改變一個變數的內含值，例如：
a = b + c；
與其他的語言不同，ｃ視"="為一個運算符號，其優先順序低於所有我們討
論過的運算符號，而且它的結合律是"由右至左"，請看下列的說明：
int x,y,z;
y = 2 ;
z = 3 ;
x = y + z ;
前二個設定敘述分別將 2 和 3 指定給 y 和 z ,然後計算 y + z 的值並且指定給
x。利用設定運算式，上述式子可以濃縮成
int x,y,z;
x = ( y = 2 ) +
( z = 3 );
y =
2 設定 y 值為 2 ，同時運算式本身的值也是 2 ，同樣的，z = 3 設定 z 值
為 3，運算式本身的值也是 3。最後，兩個式子的值相加，其結果指定給 x 。雖
然上述例題是人為的，但還是有許多情形，設定運算式是一個運算式的一部分
。最常見的就是多重設定。(multiple
assignment)如下所示：
x = y = z = 0 ;
因為"=" 的結合律是由右至左，所以上述式子可以寫成
x = ( y = ( z = 0 ) ) ;
首先，z 被設定為 0，因而
z = 0 運算式的值也是 0。接著，
y被設定為 0，
同時 y = ( z = 0
) 的值也是 0。最後，
x被設定為 0 ,x = (y =
(z = 0))的值也是 0 。
除了"="
,"+=" 和"-="也是設定運算符號，如下所示：
k = k + 2 ;
k 的原值加 2，其結果指定給
k，同時整個運算式也具有相同的值。
下列運算式
k += 2 ;
8 注 解
注解(comment)是"/*"和"*/"二個分界符號(delimiter)之間，任意長度的符號字串
。以下是幾個注解的例子：
/* a comment */
/*** another comment
***/
/*****/
9 常 數
我們知道ｃ可以處理不同種類的值，有些是常數，有些是變數。整數的 7
和浮點數的 3.14159都是常數的範例，如
"a","b"則是字元常數。"
i am a string "
則是字串常數。請注意，字元常數'a'的和字串常數的"a"是兩種不同的常數。
新字元，如'\n'，則是一特殊的字元常數。反斜線在此具有特殊的用意，而其雖
含有"\"和"n"二個字元但仍被視為單一的字元常數。
10 字 串
在一對雙引號之間的一序列字元就是字串(string)。請注意，雙引號"是一個
字元而非二個字元。如果要在字串中放入"，則必須要在\之後；如果要放入\，同
樣要跟在反斜線之後。
main()
{
int
i,j,k;
float
r, s, q;
i = 7;
j = 2;
s = i / j;
printf("s = i / j = %f\n",s);
s = (float) i / j;
printf("s = (float) i / j =
%f\n",s);
s = (float) (i / j);
printf("s = (float) (i / j) =
%f\n",s);
s = (float) i / (float) j;
printf("s = (float) i / (float) j
= %f\n",s);
k = (float) i / (float) j;
printf("k = (float) i / (float) j
= %d\n",k);
r = 7.0;
s = 2.0;
k = r / s;
printf("k = r / s = %d\n",
k);
k = (int) r / s;
printf("k = (int) r / s =
%d\n", k);
k = (int) r / (int) s;
printf("k = (int) r / (int) s =
%d\n", k);
}
s
= i / j = 3.000000
s
= (float) i / j = 3.500000
s
= (float) (i / j) = 3.000000
s
= (float) i / (float) j = 3.500000
k
= (float) i / (float) j = 3
k
= r / s = 3
k
= (int) r / s = 3
k
= (int) r / (int) s = 3
輸出／輸入
┌────────────────────────────────────┐
│printf()
│
├────────────────────────────────────┤
│
│
│轉 換
字 元
以何種形式列印對應的引數
│
├────────────────────────────────────┤
│
c
字元
│
│
d
１０進位整數
│
│
o
無正負號８進位整數
│
│
x
無正負號１６進位整數
│
│
f
浮點數，例如
:7.123000
│
│
s
字串
│
└────────────────────────────────────┘
┌─────────────────────────────────┐
│變數宣告及設定初值
│
├─────────────────────────────────┤
│char c =
'w';
│
│int i = 1,
j = 29;
│
│float x = 333.12345678901234567890;
│
│double y =
333.12345678901234567890;
│
│static char s1[] = "she sells sea shells"
│
│static char s2[] = "by the seashore"
│
├─────────────────────────────────┤
│ 格式 運算式 列印在欄位上的結果 注 解
│
├─────────────────────────────────┤
│
%c
c
"w"
預設的欄度長度為１
│
├─────────────────────────────────┤
│
%2c
c
" w"
向右對齊
│
├─────────────────────────────────┤
│ %-3c c "w "
向左對齊
│
├─────────────────────────────────┤
│
%d
-j
"-29"
預設的欄度長度為３
│
├─────────────────────────────────┤
│%010d i "0000000001"
以０填補
│
├─────────────────────────────────┤
│%-12d j "29 " 向左對齊
│
├─────────────────────────────────┤
│ %12o j " 35" ８進位 ,向右對齊 │
├─────────────────────────────────┤
│%-12x j "1d " １６進位 ,向左對齊 │
├─────────────────────────────────┤
│
%f
x
"333.123456" 預設的精確度為６ │
├─────────────────────────────────┤
│ %.1f x "333.1"
精確度為１
│
├─────────────────────────────────┤
│%20.3f x "
333.123" 向右對齊
│
├─────────────────────────────────┤
│ %.9f y "333.123456789" 精確度為９
│
├─────────────────────────────────┤
│
%s
s1
"she sells sea shells"
預設的欄度長度為２０ │
├─────────────────────────────────┤
│ %7s s1 "she sells sea
shells" 需要更多的空間
│
├─────────────────────────────────┤
│%.5s s2 "by th"
精確度為５
│
├─────────────────────────────────┤
│%-15.12s s2 "by the seash " 精確度為１２ ,向左對齊 │
└─────────────────────────────────┘
控制流程
1 關係、相等和邏輯運算符號
┌───────────────────────┐
│關係、相等和邏輯運算符號
│
├───────────────────────┤
│關係運算符號
:
小於 : < │
│
大於 : > │
│
小於或等於 : <= │
│
大於或等於 : >= │
│
│
│相等運算符號
:
等於 : == │
│
不等於 : != │
│
│
│邏輯運算符號
:
(一元)否定 : ! │
│
邏輯的和 : && │
│
邏輯的或 : || │
└───────────────────────┘
除了" ! " 是單元的之外 ,所有的關係、相等和邏輯運算符號都是二元運算符
號。這三類運算符號的優先順序都低於算術運算符號 ,而高於設定運算符號。我
們能夠直覺的判斷a < b 是真是假，ｃ則是以整數值 1代表為真，0代表為假。事
實上，所有非零值都可以代表為真。
2 關係運算符號和運算式
假設e1和e2是任意的算術運算式，下列的真值表以e1-e2 的值來決定關係運
算式的邏輯值：
運算式的值：
e1-e2 e1 < e2 e1 > e2 e1 <= e2 e1 >= e2
──────────────────────────────
正
F T
F T
零
F F
T T
負
T F
T F
3 相等運算符號和運算式
相等運算符號==及!=是運算式的二元運算符號，產生整數值 0 或 1
運算式的值：
exp1 -
exp2
exp1 == exp2 exp1 != exp2
────────────────────────────
零
1
0
非零
0
1
4 邏輯運算符號和運算式
!、&& 和||是三個邏輯運算符號，其中 !是單元運算符號，而&&和||是二元
運算符號，使用此種運算符號的運算式，其值不是 0 就是 1。
邏輯否定(logical negation)能夠在任何算術運算式中使用，若運算式的值為 0
，其否定式則產生整數值 1；相反的，若運算式的值為一非零的數值，其否定式
則產生整數值 0。
下表為運算符號! 的語意：
運算式的值：
exp !exp
────────
零
1
非零 0
下表為邏輯運算符號的語意：
運算式的值：
exp1
exp2 exp1
&& exp2 exp1 || exp2
─────────────────────────────
F
F
F
F
F
T
F
T
T
F
F
T
T
T
T
T
&&的優先順序高於||，但是兩者都低於單元、算術和關係運算符號，其結
合律為"由左至右"。下列表格以優先順序和結合律來計算幾個邏輯運算式的值：
┌─────────────────────────────────┐
│變數宣告及設定初值
│
├─────────────────────────────────┤
│int i = 7,
j = 8, k = 9;
│
│float
x = 0.0;
│
├─────────────────────────────────┤
│ 運算式
相等運算式
結 果│
├─────────────────────────────────┤
│ i
&& j && k
(i && j) && k
1 │
├─────────────────────────────────┤
│ i || j-3
&& 0 i ||
((j-3) && 0)
1 │
├─────────────────────────────────┤
│ i < j && 2
>= k (i < j)
&& (2 >= k)
0 │
├─────────────────────────────────┤
│ i < j || 2 >=
k (i < j)
|| (2 >= k)
1 │
├─────────────────────────────────┤
│i ==2 || j
==4 || k ==6 ((i ==2) || (j
==4)) || (k ==6)
0 │
├─────────────────────────────────┤
│i =2 || j
==4 || k ==6 i =((2 ||
(j ==4)) || (k ==6)) 1 │
├─────────────────────────────────┤
│x <=5.0
&& x !=1.0 ||i>j ((x
<=5.0) && (x !=1.0)) ||(i>j) 1
│
└─────────────────────────────────┘
我們計算 && 和 || 的運算元的運算式值，其程序是由左至右，一旦得知結
果是真或假，此程序就立即停止。假設 exp1 和 exp2 是運算式，且 exp1 的值為
0，則下列邏輯運算式：
exp1 && exp2
不會計算 exp2 的值，因為整個邏輯運算式的結果已經是 0。同樣的，若exp1
為非零值，則
exp1 || exp2
不會計算 exp2 的值，因為整個邏輯運算式的結果已經是 1。請見下列程式的
說明：
int i, j = 2 ;
i = 0
&& (j = 3) ;
printf(
"%d %d\n", i, j) ;
/* 印出 0 2 */
i = 4 || (j =
5) ;
printf(
"%d %d\n", i, j) ;
/* 印出 1 2 */
i = 0 || (j =
6) ;
printf(
"%d %d\n", i, j) ; /*
印出 1 6 */
main()
{
int a,b=14;
if ((a=1) && (b=10))
printf("TRUE a=%d,b=%d\n", a,b);
else
printf("FALSE a=%d,b=%d\n", a,b);
}
TRUE
a=1,b=10
main()
{
int a,b=14;
if ((a=0) && (b=10))
printf("TRUE a=%d,b=%d\n", a,b);
else
printf("FALSE a=%d,b=%d\n", a,b);
}
FALSE
a=0,b=14
main()
{
int a,b=14;
if ((a=1) || (b=10))
printf("TRUE a=%d,b=%d\n", a,b);
else
printf("FALSE a=%d,b=%d\n", a,b);
}
TRUE
a=1,b=14
main()
{
int a,b=14;
if ((a=0) || (b=10))
printf("TRUE a=%d,b=%d\n", a,b);
else
printf("FALSE a=%d,b=%d\n", a,b);
}
TRUE a=0,b=10
5 複合敘述
複合敘述是指'{ '和'} '之間的一連串敘述，其主要用途是將數個敘述集合在
一起，成為單一的可執行敘述。
控制敘述
(Control Statement)
結構化程式設計所使用流程大致不外三種：
1. 順序式結構(sequence
structure)
2. 選擇式結構(selection
structure)
3. 迴圈式結構(loop
structure)
順序式結構
由一連串簡單敘述組合，其執行順序亦按這些敘述的先後次序：
↓
┌───┐
│ 敘述1│
└───┘
↓
┌───┐
│ 敘述2│
└───┘
↓
┌───┐
│ 敘述3│
└───┘
↓
：
：
選擇結構
條件測試
選擇結構用在作決策判斷時，它能決定程式邏輯的走向。∼(NOT)、&&(AND)、
與 || (OR)是 C三個基本的邏輯運算子。
∼
│ T F && │
T F || │
T F
──┼──── ──┼──── ──┼────
結果│ F T T │ T F T │ T T
F │ F F F │
T F
T (TRUE)以 1 表示，F
(FALSE)則為 0。前章也提到，所有非零的值，在測試
時都被認為是 TRUE。
i = j
* k ;
if (i)
printf("TRUE");
IF 敘述
IF 敘述依其構造的複雜性又可分為三種結構:
一、簡單IF敘述
IF (expression)
↓
{
=0
敘 述 一；
敘 述 二；
expression ─┐
:
│
:
│
}
↓≠0
│
┌───┐ │
│敘述一│ │
└───┘ │
↓ │
┌───┐ │
│敘述二│ │
└───┘ │
↓ ←───┘
例:
if (a-2)
printf("a is not equal
to 2\n");
同義於下式
if (a-2 !=0)
printf("a is not equal
to 2 \n");
二、IF....ELSE
這個結構與第一種的差異在於條件不成立時，有另一組必須完成的工作。
IF
(expression) ↓
{
=0 ┌───┐ ┌───┐ ┌───┐
敘述 1； expression →│敘述 1│→│敘述 2│...│敘述 │┐
：
└───┘ └───┘ └───┘│
敘述 m ↓≠0
│
} ┌───┐
│
ELSE │敘述
1│
│
{ └───┘
│
敘述 1； ↓
│
： ┌───┐
│
敘述 n │敘述 2│
│
} └───┘
│
↓
│
： │
┌───┐
│
│敘述 m│
│
└───┘
│
↓ ←────────────────────┘
三、巢狀式 IF ...
ELSE
A
B
IF (expression1)
IF (expression1)
IF (expression2)
敘述 1；
敘述
1；
ELSE IF (expression2)
ELSE
敘述 2；
敘述
2；
ELSE
ELSE
敘述 3；
敘述3；
≠0
↓ =0
┌───┐
┌───┐
expression1 →│敘述 1│─┐
expression1 →│敘述 3│ ┐
└───┘ │
└───┘ │
↓ =0
│
↓≠0
│
┌───┐ │
┌───┐ │ expression2 →│敘述 3│ │
expression2 →│敘述 1│ │
└───┘ │
└───┘ │
↓ ≠0
│
↓
│ ┌───┐
│
┌───┐
│ │敘述 2│
│
│敘述 2│
│ └───┘
│
└───┘
│
↓ ←────────┘
↓ ←────────┘
§例：
if (x > value)
high = mid - 1;
else if (x < value)
low = mid + 1;
else
return (mid);
當 else 的部份的確不須有任何敘述時，
可以用「；」代替。
§例：
if (A == B) {
printf("correct");
if (B == C)
printf("right");
else
;
}
else
printf("wrong");
★☆★ 例 ★☆★
main()
{
float a,b,c; // 三角形三邊長
float s1, s2, temp; //暫時變數
printf("輸入三邊長:\n");
scanf("%f%f%f",&a,&b,&c);
if (b > a){
temp = a;
a = b;
b = temp;
}
if (c > a) {
temp = a;
a = c;
c = temp;
}
s1 = a * a;
s2 = b * b + c * c;
if (a >= b+c)
printf("\n輸入之三邊無法構成三角形");
else if (s1 == s2)
printf("\n輸入之三邊可構成直角三角形");
else
if (s1 > s2)
printf("\n輸入之三邊可構成鈍角三角形");
else
printf("\n輸入之三邊可構成銳角三角形");
}
輸出結果 :
輸入三邊長:3 4 5
輸入之三邊可構成直角三角形輸入三邊長:
輸入三邊長:3 2 1
輸入之三邊可構成鈍角三角形輸入三邊長:
輸入三邊長:7 5 8
輸入之三邊可構成銳角三角形輸入三邊長:
輸入三邊長:10 5 3
輸入之三邊無法構成三角形
§例：
main ()
{
if (10)
printf
(" 10 is true.\n");
if (-10)
printf ("
-10 is true.\n");
if (0)
printf (" 0 is true.\n");
else
printf
(" 0 is
false.\n");
}
輸出結果 :
1
is true.
-10 is true.
0 is false.
條件表示式：條件運算子為？：
標準格式為
expression1？expression2：expression3
這個運算式等於寫成：
if (expression 1)
expression 2;
else
expression 3;
if (a > b)
z = a ; 同義於 z =
( a > b ) ? a : b ;
else
z = b ;
switch 敘述
提供了多重選擇的功能：
語法：
switch (運算式)
{
case (常數運算式 1 )：敘述 1；
敘述 2；
.
.
.
break；
case (常數運算式 2 )：敘述 1；
敘述
2；
.
.
.
break；
.
.
.
default
: 敘述 1；
敘述 2；
.
.
.
}
使用 switch 時有下列幾點應特別注意：
1．case 後面註明為常數運算式，表示必須是一個值或一個常數符號，不可
是變數或其他運算式。
2．case 內的敘述多於一句時，不必以{
} 作區隔。
3．在 case 中找到第一個正確的值時便執行其後面的敘述，break可以省略，
但程式因此無法跳離 switch，會繼續執行下面其他的 case。
4．當所有 case 都不成立時，會執行
default 部份，但若沒有 default 敘
述，則這一部份也可省略。
5．case 內也可以是『空敘述』(Null
Statement)。
§例：
switch ( ch ) {
case 'F' :
/* Null Statement */
case 'f'
: printf(...)
:
}
若遇到空敘述，則執行流程繼續往下一個 case 執行。
6．break 敘述，指示程式流程立即跳出
switch body，由 switch 後的第一
個敘述往下執行。若沒有 break 敘述，則程式會繼續執行下一個
case
敘述直到遇見 break 或 switch 的尾部才停止。
§例：
main()
{
int i;
scanf("%d",&i);
switch (i) {
case 1: printf("i equals to
%d\n",i);
i++;
case 2: printf("i equals to
%d\n",i);
i++;
default:
printf("Now i becomes %d\n",i);
}
}
輸出結果 :
1 <--- 輸入資料 1
i equals to 1
i equals to 2
Now i becomes 3
§例：
main()
{
int i;
scanf(%d",i);
switch(i) {
case 1: printf("i equals to
%d\n",i);
i++;
break;
case 2: printf("i equals to
%d\n",i);
i++;
break;
default:
printf("Now i becomes %d\n",i);
}
}
輸出結果 :
1 <--- 輸入資料 1
i equals to 1
§例： 輸入任意字串，計數數字、空白、新行(new line)、跳格(Tab)的個數：
#include
<stdio.h>
main()
{
int c; // 輸入字元
int nspace = 0; /* number of space */
int ntab = 0; /* number of
tab */
int nnewline = 0; /* number of new line */
int nothers = 0;
int ndigit = 0; /* number of digit */
printf("輸入資料:");
while((c=getchar()) != EOF)
switch(c){
case '0':
case
'1':
case
'2':
case
'3':
case
'4':
case
'5':
case
36':
case
'7':
case
'8':
case
'9': ++ndigit;
break;
case '
': ++nspace;
break;
case '＼n':
++nnewline;
break;
case '＼t':
++ntab;
break;
default: ++nothers;
break;
}
printf("＼n＼n ** output
result **");
printf("＼n數字個數:&d",ndigit);
printf("＼n<new line>個數:%d",nnewline);
printf("＼n空白個數:%d",nspace);
printf("＼n<Tab>的個數:,%d",ntab);
printf("＼n其它字元的個數:&d",others);
}
迴圈式結構
for 敘述
語法:
for(expr1;expr2;expr3)
{
敘述;
:
:
}
expr1: 迴圈記數器的初值。
expr2: 測試迴圈是否停止。
expr3: 迴圈的增值。
expression之間以『;』分割。
若 expression
內有多個運算式則以『,』隔開,逗號的運算次序由左至右依次
運算。
for(oun=1,cost=FIRST; oun
<= 16; oun++,cost+=next)
for 所函括的敘述可以是空敘述
例：for (t=0;
t < some-value; t++)
;
expression 1~3 皆可省略
但 expression 間的『;』不可省略。
例：for (n=3;
ans <= 25;)
for
(;;){
:
:
}
for 沒有限制
initialize counter 一定是一個算式。
例：for
(printf("keep entering numbers!\n"); num==6;){
…
…
}
§例：/* Add 1 + 2 + ..... + 100 */
main()
{
int sum = 0;
int i = 1;
for ( ; i <= 100; )
sum
+= i++;
printf("The sum is =
%d \n",sum);
}
§例：/* Print 9 * 9 table using double for
loop. */
main()
{
int i,j,result;
for (i = 1; i <= 9;
i++){
for
(j = 1; j <= 9; j++){
result = i * j;
printf("%d*%d=%-3d",i,j,result);
}
printf("\n");
}
}
while 敘述
語法:
while(expression) while(expression)
{
敘述;
敘述1;
:
:
}
若 expression
的值不等於零則執行迴圈的敘述。
若迴圈內敘述只有一句時可省略 {}。
§例：/* add 1 + 2 + ..... + 10 */
main()
{
int i,sum;
i = 1;
sum = 0;
while (i <= 10)
sum
+= i++;
printf("The sum is %d
\n",sum);
}
§例：/* find the greatest common
divisor. */
main()
{
int i,j,tmp;
printf("Please input 2
nonnegative numbers \n==> ");
scanf("%d
%d",&i,&j);
while (j != 0) {
tmp
= i % j;
i =
j;
j =
tmp;
}
printf("The gcd is %d
\n",i);
}
do ~ while 敘述
語法: do
do
{
敘述;
敘述;
:
:
while(expression);
:
}while(expression);
expression 的值為
true 時回到迴圈內執行，至少執行迴圈敘述一次。
§例：/* add 1 + 2 + .... + 100 */
main()
{
int i,sum;
i = 1;
sum = 0;
do {
sum +=
i++;
} while ( i <= 100 );
printf("\1: The sum is
%d \n",sum);
}
§例：輸入一行字串計數共有幾個字組(word)。以空白、逗號或句點表一字組
的結束。
main()
char ch;
int punch;
int cnt = 0;
printf("輸入資料:");
do
{
do
ch=getchar();
while(ch!=' '
&& ch!=',' && ch!='.' && ch!='＼n')
;
while(ch == ' ' || ch
== '.' || ch == ',')
ch = getchar();
cnt++;
} while(ch != '\n');
printf("共輸入 %d 個字",cnt);
}
break 與 continue
使跳出迴圈主體而執行下一敘述
break 之實例應用：
§例:
do {
scanf("%d",i);
if (i < 0)
break;
:
} while(i != 0);
printf("End");
§例：/* for
and break application. */
main()
{
int i;
for (i = 1; i <= 100;
i++){
printf("loop index %d \n",i);
if (i >= 5)
break;
}
}
§例：/* for
loop with forever loop */
main()
{
int i;
int count = 1;
for ( ; ; ) {
printf("guess number here: ");
scanf("%d",&i);
if (i == 5)
break;
count++;
}
printf("You take %d
times to get it.\n",count);
}
continue 之實例應用:
§例： 求1到100中5的倍數之和
#include
<stdio.h>
main()
{
float sum = 0.0;
int i;
printf("由 1 至 100,所有 5 的倍數為:\n");
for (i = 1;i <= 100; i++){
if (i % 5 != 0)
continue;
printf("&d",i);
(i % 25
== 0) ? printf("\n") : printf(" ");
sum += i;
}
printf("其和為:&d",sum);
}
§例：/* add 2
+ 4 + .... + 100 */
main()
{
int i,sum;
sum = 0;
for (i = 2; i <= 100;
i++){
if ((i % 2) != 0)
continue;
sum += i;
}
printf("The sum is %d
\n",sum);
}
2-5 無條件跳躍 -- goto
語法格式:
goto
label-name;
....
....
label-name:
statements;
.....
label name 與變數的命名相同，其後需跟冒號，常用在由巢狀迴圈中跳出。
例：
for (...)
for (...){
...
if (...)
goto error;
...;
}
error:
…
…
§例：/* goto
command application */
main()
{
int i,j;
start: printf("Please
input 2 number here \n==> ");
scanf("%d%d",&i,&j);
if (i > j)
goto stop;
goto
start;
stop:
printf("program stop. \n");
}
閏年的判斷：(1)能夠被 4整除而且不為 100所整除
(2)能被 400所整除
當 (1)與 (2)其中有一成立即為閏年
§例
/* This program is to test logical use
*/
main ()
{
int year ;
printf("This program is to test
wether the input is leap year :\n\n");
printf("Which year :");
scanf("%d",&year);
if ((year%4==0 && year%100 !=0) || (year%400==0))
printf ("%4d
is a leap year\n",year);
else
printf
("%4d is not a leap year\n",year);
}
輸出結果
This program
is to test wether the input is leap year :
Which year :
1984
1984 is a
leap year
This program
is to test wether the input is leap year :
Which year :
1911
1911 is not
a leap year
This program
is to test wether the input is leap year :
Which year :
2000
2000 is a
leap year
strlen(s) /* return length of s */
char s[];
{
int i;
i = 0;
while (s[i] != '\0')
i++;
return (i);
}
strcmp(s,
t) /* return < 0 if s<t, 0 if s==t, >0 if s>t */
{
int i;
i = 0;
while (s[i] == t[i])
if (s[i++] == '\0')
return (0);
return (s[i] - t[i]);
}
strcat(s,
t) /*
concatenate t to s */
char s[], t[]; /* s must be big enough */
{
int i, j;
i = j = 0;
while (s[i] != '\0') /* find end of s */
i++;
while ((s[i++] = t[j++]) != '\0') /* copy t */
;
}
reverse(s) /* reverse string s in place */
char s[];
{
int c, i, j;
for (i = 0, j = strlen(s) - 1; i <
j; i++, j--) {
c = s[i];
s[i] = s[j];
s[j] = c;
}
}
main() /* count lines in input */
{
int c, nl;
nl = 0;
while ((c=getchar()) != EOF)
if (c == '\n')
nl++;
printf("%d\n",nl);
}
#define
YES 1
#define
NO 0
main()
/* count lines, words, chars in input */
{
int c, nl, nw, nc, inword;
inword = NO;
nl = nw = nc = 0;
while ((c = getchar()) != EOF) {
nc++;
if (c == '\n')
nl++;
if (c == ' ' || c == '\n' || c == '\t')
inword = NO;
else if (inword == NO) {
inword =
YES;
nw++;
}
}
printf("%d %d %d \n", nl, nw,
nc);
}
index(s,t)
/* return index of t in s, -1 if none */
char
s[], t[];
{
int i, j, k;
for (i=0; s[i]!='\0'; i++) {
for (j=i,k=0;
t[k]!='\0' && s[j]==t[k]; j++,k++)
;
if (t[k] == '\0')
return (i);
}
return (-1);
}
main()
{
int i, num;
printf("Prime Number
...\n\n");
printf("Please enter number ('0'
to Quit)\n");
do
{
printf("number = ");
scanf("%d", &num);
i = 2;
if (num == 1)
i = 1;
else
while ((num % i) != 0)
i++;
if (i == num)
printf("%d Is a Prime Number.\n", num);
else
printf("%d Is Not a Prime Number.\n", num);
} while (num != 0);
}
1. 定義一 int array P, P[i]=0 2<i<n
2. i=2
3. 印出 i 值(其為質數)
4. 對 i*j < n 的
j 值, 將 P[i*j] 設定為 1
5. 找出下一個符合 P[i]=0 者=> 3,找不到=>
結束
#define
N 1000
main()
{
int p[N],i,j,k,prime,n=0;
for (i = 2; i < N; i++)
p[i] = 0;
printf("... find prime
number ....\n");
printf("input your data :
");
scanf("%d",
&prime);
printf("%d\n\n",
prime);
i = 2;
while (i < prime) {
printf("%5d%c", i, (n++%7==6 || i==prime-1) ? '\n' : ' ');
for (j =
1; (i * j) < prime ; j++)
p[i*j] = 1;
for (k =
i + 1; k < prime+1; k++) {
if (p[k] == 0) {
i = k;
break;
}
}
}
printf("\n");
}
...
find prime number ....
input
your data : 200
2 3 5 7 11 13 17
19 23 29 31 37 41 43
47 53 59 61 67 71 73
79 83 89 97
101 103 107
109 113
127 131 137 139
149
151 157
163 167 173 179
181
191 193
197 199
main()
{
char str[20];
int i, len, sum = 0;
printf("This program is to test
your data is divisible by 9\n");
printf("Please input your data (digits) ");
scanf("%s", str);
len = strlen(str);
for (i = 0; i <= len-1; i++)
sum +=
str[i] - '0';
/* sum +=
str[i]- 48; */
if (sum % 9 == 0)
printf("%s
is divisible by 9\n",str);
else
printf("%s
is not divisible by 9\n",str);
}
binary(x,
v, n) /* find x in v[0] ...
v[n-1] */
int x, v[], n;
{
int low, high, mid;
low = 0;
high = n-1;
while (low <= high) {
mid = (low +
high) / 2;
if (x < v[mid])
high = mid - 1;
else if (x > v[mid])
low = mid
+ 1;
else /* found match */
return (mid);
}
return (-1)
}
前端處理程式
(preprocessor)
＃define ＃include
ｃ提供前端處理程式，凡是前端有＃者皆稱之，如利用＃include把資料從某
一檔案中引含進來。前端處理程式也可用來定義常數。如＃define PI
3.1416 表
示 3.1416以 PI 符號代之，以後出現 PI 的地方就是等於 3.1416，注意＃define
後
面不要有分號（；)。有時為了使程式易讀，往往把定義符號 PI 大寫，如此在程
式中碰到大寫的字，便可知道其為常數而不是變數。
例題 １
#define a
10
#define b
20
#define c
30
main()
{
int sum;
float average;
sum = a + b + c;
average = sum / 3;
printf("a=%d, b=%d, c=%d, sum=%d,
average=%f\n",a,b,c,sum,average);
}
輸出結果
a=10，b=20，c=30，sum=60，average=20.000000
在例題１中利用 #define 定義了 a，b，c 分別為 10，20，30 因此程式中凡是出
現 a，b，c 的地方，其值相當於 10，20，30。
假若程式用到很多＃define的符號，則我們可以先把它存在一個檔案裏，要用時
再利用＃include把它引含進來。
例題 ２
#include
"def.h"
main()
{
int sum;
float average;
sum = a + b + c;
average = sum / 3;
printf("a=%d, b=%d, c=%d, sum=%d,
average=%f\n",a,b,c,sum,average);
}
例題
３
#define
square(x) x*x
main()
{
int result;
result = square(3);
printf("The square(3) is
%d.\n",square(3));
result = square(3+4);
printf("The square(3+4)is
%d.\n",square(3+4));
}
輸出結果
The
square(3) is 9.
The
square(3+4) is 19.
例題 ４
#define
square(x) (x)*(x)
main()
{
int i=1,result;
result = square(++i);
printf("The square(++%d) is
%d.\n",i,square(++i));
result = square(i);
printf("The square(%d) is
%d.\n",i,square(i));
}
輸出結果
The
square(++5) is 20.
The
square(5) is 25.
例題４告訴我們不要在兩個變數一樣的情況下使用 ++。
注意不可以把 #define
square(x) (x)*(x) 寫成
#define
square (x) (x)*(x) 或
#define
square(x) (x)*(x);
#define
square(x) (x)*(x)
main()
{
int i = 1, result;
result = square(i++);
printf("The square(++%d) is %d
\n",i, square(i++));
result = square(i);
printf("The square(%d) is %d
\n",i, square(i));
}
輸出結果
The
square(++3) is 9
The
square(5) is 25
例題 ５ 利用 #define 求兩數之最小值
#define
MIN(x,y) ( ( (x) < (y) ) ? (x) : (y) )
main()
{
int x,
y, min;
printf("The program is to find the
minimun of x & y\n");
printf("Please input your data
(x,y)\n");
scanf("%d %d",&x,&y);
printf("The minimun of %d & %d
is %d\n",x,y,MIN(x,y));
}
輸出結果
The
program is to find the minimun of x & y
Please
input your data (x,y)
17
13
The
minimun of 17 & 13 is 13
例題 ６ 利用 #define 求三數之最大值
#define
MAX(x,y) ( ( (x) > (y) ) ? (x) : (y) )
#define
MAX3(x,y,z) ( (MAX(x,y)) > (z) ? (MAX(x,y)) : (z) )
main()
{
int x,
y, z;
printf("The program is to find the
maximun of three number\n");
printf("Please input your data
(x,y,z)\n");
scanf("%d %d
%d",&x,&y,&z);
printf("The maximun of %d & %d
& %d is %d\n",x,y,z,MAX3(x,y,z));
}
輸出結果
The
program is to find the minimun of three number
Please
input your data (x,y,z)
27
39 15
The
maximun of 27 & 39 & 15 is 39
例題 ７
利用 #define 依輸入 data 的 正負號將 data 向左或向右移若干位元。
如 10 向左移二位元， 10 = (1010) =>
(101000) => 40
2
2
#define
SHIFT(a,b) ((b) > 0 ? (a << b) : (a >> -b) )
main()
{
int value,n;
printf("This program is to shift
your data\n");
printf("IF 'n' > 0 shift left
ELSE shift
right\n");
printf("Please input your
data(value n)\n");
scanf("%d %d
",&value,&n);
if (n >= 0)
printf("%d after shift left %d bits ===>
%d\n",value,n,SHIFT(value,n));
else
printf("%d after shift right %d bits ===>
%d\n",value,-n,SHIFT(value,n));
}
輸出結果
This
program is to shift your data
IF
'n' > 0 shift left ELSE shift
right
Please
input your data(value n)
10 2
10
after shift left 2 bits ===> 40
/* call by value */
swap(x,y)
int x, y;
{
int temp;
temp = x;
x = y;
y = temp;
}
main()
{
int a = 1, b = 2;
swap(a,b);
printf("a is now %d, b is now
%d\n",a,b);
}
a
is now 1, b is now 2
/* call by address */
swap(x,y)
int *x, *y;
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
main()
{
int a = 1, b = 2;
swap(&a,&b);
printf("a is now %d, b is now
%d\n",a,b);
}
a
is now 2, b is now 1
/* call by name */
swap(x,y)
int x, y;
{
int a;
a = x;
x = y;
y = a;
}
main()
{
int a = 1, b = 2;
swap(a,b);
printf("a is now %d, b is now
%d\n",a,b);
}
swap(a,b)
int a, b;
{
int a;
a = a;
a = b;
b = a;
}
a
is now 2, b is now 2
遞歸運算
任何函數都能呼叫它本身
sum (n)
int n;
{
if (n <= 1)
return (n);
else
return (n + sum (n-1));
}
Function call Value returned
===============================================================================
sum (1)
1
sum (2)
2 + sum (1) is 2 + 1
sum (3)
3 + sum (2) is 3 + 2 + 1
sum (4)
4 + sum (3) is 4 + 3 + 2 + 1
sum (5)
5 + sum (4) is 5 + 4 + 3 + 2 + 1
sum = 5 + sum (5-1) ;
{first}
│
sum = 4 + sum (4-1) ; {second}
│
sum = 3 + sum (3-1) ; {third}
│
sum = 2 + sum (2-1) ; {fourth}
│
sum = 1 ; {fifth}
sum = 1 ; {fifth}
│
sum = 2 + 1 ; {fourth}
│
sum = 3 + 3 ; {third}
│
sum = 4 + 6 ; {second}
│
sum = 5 + 10 ; {first}
/* Write a line backwards. */
main ()
{
printf (" Input a line
:");
prn_it();
printf ("\n\n");
}
prn_it()
{
char c;
if ((c = getchar()) != '\n')
prn_it();
putchar(c);
}
Input a line :
sing a song of sixpence
ecnepxis fo gnos a
gnis
#define MAXWORD 100
main ()
{
printf (" Input a line
:");
prn_it_by_word();
printf ("\n\n");
}
prn_it_by_word()
{
char w[MAXWORD];
get_word(w);
if (w[0] != '\n')
prn_it_by_word();
printf ("%s",w);
}
get_word(s)
char *s;
{
static char c = '\0';
if (c == '\n')
*s++ = c;
else
while (( c =getchar()) != '' && c != '\t' && c != '\n')
*s++ = c ;
*s = '\0';
}
Input a line : deep
in the heart of texas
texas of heart the
in deep
/* Reverse the
character between s[j] and s[k] recursively. */
reverse (s,j,k)
char *s;
int j,k ;
{
if (j<k) {
swap
(&s[j], &s[k]);
reverse (s
,++j, --k);
}
}
swap (p ,q )
char *p,*q;
{
char temp ;
temp = *p ;
*p = *q ;
*q = temp ;
}
/* The best
possible minmax algorithm - Pohl , 1972 */
minmax
(a,n,min_ptr,max_ptr) /* n is the
size of a[] */
int a[],
n,*min_ptr ,*max_ptr ; /* n must
be a power of 2 */
{
int min1,max1,min2, max2;
if (n ==2)
if (a[0] < a[1]) {
*min_ptr = a[0] ;
*max_ptr = a[1] ;
}
else {
*min_ptr = a[1] ;
*max_ptr = a[0] ;
}
else {
minmax (a,n/2,&min1,&max1);
minmax (a+n/2,n/2,&min2,&max2);
if (min1 < min2)
*min_ptr = min1 ;
else
*min_ptr = min2 ;
if (max1 < max2)
*max_ptr = max2 ;
else
*max_ptr = max1 ;
}
}
常見的程式錯誤
factorial_forever(n)
int n ;
{
return (n * factorial_forever(n-1)) ;
}
factorial_error(n)
int n ;
{
if (n == 1)
return (1) ;
else
return (n *
factorial_positive(n-1)) ;
}
factorial (n)
int n ;
{
if (n <= 1)
return (1) ;
else
return (n * factorial(n-1))
;
}
河內塔問題 (Tower of Hanoi)
所謂河內塔問題，是指有 n 個盤子，已經按照由大至小的順序，大的在
下，小的在上放在一根柱子上，另外有兩根柱子是空的，現在要將所有的盤子
搬到另外一根柱子上，第三根柱子可以做為暫時放置盤子之用，在搬盤子的過
程中必須遵守下列的三項規則：
1. 一次只能搬動一個盤子。
2. 任何一個盤子可以從一根柱子搬到任何一根柱子上。
3. 在任何時間之內 ,絕不能有大盤子在上
,而小盤子在下的情況發生。
(一)當 n = 1 時 :
只有一個盤子時 ,可不藉助於
C ,直接 A 由搬至 B。
(二)當 n = 2 時 :
1. 未搬動前 ,1 及 2放在 A 柱
, B 柱及 C 柱空著。
┌┐
┌┐
┌┐
││
││
││
││
││
││
┌┴┴┐
││
││
│ 1 │
││
││
┌┴──┴┐
││
││
│ 2 │
││
││
┌─┴────┴─┐ ┌───┴┴───┐ ┌───┴┴───┐
│ A │ │ B │ │ C │
└────────┘ └────────┘ └────────┘
2. 將盤 1 由 A 搬至 C。( A
-> C )
┌┐
┌┐
┌┐
││
││
││
││
││
││
││
││
││
││
││
││
┌─┴┴─┐
││
┌┴┴┐
│ 2 │
││
│ 1 │
┌─┴────┴─┐ ┌───┴┴───┐ ┌──┴──┴──┐
│ A │ │ B │ │ C │
└────────┘ └────────┘ └────────┘
3. 將盤 2 由 A 搬至 B。( A
-> B )
┌┐
┌┐
┌┐
││
││
││
││
││
││
││
││
││
││
││
││
││
┌─┴┴─┐
┌┴┴┐
││
│ 2 │
│ 1 │
┌───┴┴───┐ ┌─┴────┴─┐ ┌──┴──┴──┐
│ A │ │ B │ │ C │
└────────┘ └────────┘ └────────┘
4. 將盤 1 由 C 搬至 B。( C
-> B )
┌┐
┌┐
┌┐
││
││
││
││
││
││
││
┌┴┴┐
││
││
│ 1 │
││
││
┌┴──┴┐
││
││
│ 2 │
││
┌───┴┴───┐ ┌─┴────┴─┐ ┌───┴┴───┐
│ A │ │ B │ │ C │
└────────┘ └────────┘ └────────┘
(三)當n = 3 時 :
1. 未搬動前 ,1、2、3 均放在 A 柱
, B 柱及 C 柱空著。
┌┐
┌┐
┌┐
││
││
││
││
││
││
┌┴┴┐
││
││
│ 1 │
││
││
┌┴──┴┐
││
││
│ 2 │
││
││
┌─┴────┴─┐
││
││
│ 3 │
││
││
┌─┴────────┴─┐┌─────┴┴─────┐┌────┴┴────┐
│ A ││ B ││
C │
└────────────┘└────────────┘└──────────┘
2. 將盤 1 由 A 搬至 B。( A
-> B )
┌┐
┌┐
┌┐
││
││
││
││
││ ││
││
││
││
││
││
││
┌─┴┴─┐
││
││
│ 2 │
││
││
┌─┴────┴─┐
┌┴┴┐
││
│ 3 │
│ 1 │
││
┌─┴────────┴─┐┌────┴──┴────┐┌────┴┴────┐
│ A ││ B ││
C
│
└────────────┘└────────────┘└──────────┘
3. 將盤 2 由 A 搬至 C。( A
-> C )
┌┐
┌┐
┌┐
││
││
││
││
││
││
││
││
││
││
││
││
││
││
││
││
││
││
┌───┴┴───┐
┌┴┴┐
┌─┴┴─┐
│ 3 │
│ 1 │
│ 2 │
┌─┴────────┴─┐┌────┴──┴────┐┌──┴────┴──┐
│ A ││ B ││
C │
└────────────┘└────────────┘└──────────┘
4. 將盤 1 由 B 搬至 C。(
B -> C )
┌┐
┌┐
┌┐
││
││
││
││
││
││
││
││
││
││
││
││
││
││
┌┴┴┐
││
││
│ 1 │
┌───┴┴───┐
││
┌┴──┴┐
│ 3 │
││
│ 2 │
┌─┴────────┴─┐┌─────┴┴─────┐┌──┴────┴──┐
│ A ││ B ││
C │
└────────────┘└────────────┘└──────────┘
5. 將盤 3 由 A 搬至 B。( A
-> B )
┌┐
┌┐
┌┐
││
││
││
││
││
││
││
││
││
││
││
││
││
││
┌┴┴┐
││
││
│ 1 │
││
┌───┴┴───┐ ┌┴──┴┐
││
│
3 │ │ 2 │
┌─────┴┴─────┐┌─┴────────┴─┐┌──┴────┴──┐
│ A
││ B ││
C │
└────────────┘└────────────┘└──────────┘
6. 將盤 1 由 C 搬至 A。(
C -> A )
┌┐
┌┐
┌┐
││
││
││
││
││
││
││
││
││
││
││
││
││
││
││
││
││
││
┌┴┴┐
┌───┴┴───┐ ┌─┴┴─┐
│ 1 │
│
3 │ │ 2 │
┌────┴──┴────┐┌─┴────────┴─┐┌──┴────┴──┐
│ A
││ B ││
C │
└────────────┘└────────────┘└──────────┘
7. 將盤 2 由 C 搬至 B。(
C -> B )
┌┐
┌┐
┌┐
││
││
││
││
││
││
││
││
││
││
││
││
││
┌─┴┴─┐
││
││
│ 2 │
││
┌┴┴┐
┌─┴────┴─┐
││
│ 1 │
│
3 │
││
┌────┴──┴────┐┌─┴────────┴─┐┌────┴┴────┐
│ A ││ B ││
C │
└────────────┘└────────────┘└──────────┘
8. 將盤 1 由 A 搬至 B。(
A -> B )
┌┐
┌┐
┌┐
││
││
││
││
││
││
││
┌┴┴┐
││
││
│ 1 │
││
││
┌┴──┴┐
││
││
│ 2 │
││
││
┌─┴────┴─┐
││
││
│
3 │
││
┌─────┴┴─────┐┌─┴────────┴─┐┌────┴┴────┐
│ A ││ B ││
C │
└────────────┘└────────────┘└──────────┘
觀察上面搬盤子的過程中，我們歸納出一個遞迴處理的原則來了，可以觀察
n
= 3 時的步驟 2至 4 和n = 2 時的步驟 2至 4完全相同，只是柱子的名稱不一樣
罷了，同理在步驟 6至 8中也是和步驟 2至 4相同，也維有柱子名稱不一樣而已
，這個遞迴處理的過程可以描述如下：
1. 搬動 n - 1 個盤子, 由 A柱, 藉著 B柱, 搬至 C柱。
2. 搬動第 n 個盤子, 由 A柱到 B柱。
3. 搬動 n - 1 個盤子, 由 C柱, 藉著 A柱, 搬至 B柱。
根據這個遞迴處理過程 ,我們就很容易可以完成解決河內塔問題的程式了。
int n = 0;
main()
{
int height;
printf("How many disks are you
going to start with? \n");
scanf("%d", &height);
move(height, 'A', 'B', 'C');
printf("\n\nTotal have %d
moves\n", n);
}
move(height, from,
to, using)
int height;
char from, to, using;
{
if (height == 1) {
printf("Move a disk from %c to %c\n", from, to);
n++;
}
else {
move(height-1,
from, using, to);
printf("Move a disk from %c to %c\n", from, to);
n++;
move(height-1, using, to, from);
}
}
輸出結果
How many disks are
you going to start with?
Move a disk from A
to B
Move a disk from A
to C
Move a disk from B
to C
Move a disk from A
to B
Move a disk from C
to A
Move a disk from C
to B
Move a disk from A
to B
Total have 7 moves
氣泡排序法
bubble (a,n)
order (p,q)
int a[], n;
int *p,*q;
{ {
int i , j ;
int temp;
for ( i=0 ; i < n
-1 ;++i)
if (*p>*q) {
for ( j=
n-1 ; i<j ;--j)
temp = *p;
order
(&a[j-1],&a[j]);
*p = *q ;
}
*q = temp;
}
}
假設我們宣告
static
int a[] = { 7,3,66,3,-5,22,-77,2};
然後呼叫 bubble ( a,8 ) 。下列 示每次外 曾迴圈執行之後,a[]陣列元素
的排列情形 :
未排列的資料 : 7 3 66 3 -5 22 -77 2
第一次
: -77 7 3 66 3 -5 22
2
第二次
: -77 -5 7
3 66 3 2
22
第三次
: -77 -5 2
7 3 66 3
22
第四次
: -77 -5 2
3 7 3 66 22
第五次
: -77 -5 2
3 3 7 22 66
第六次
: -77 -5 2
3 3 7 22 66
第七次
: -77 -5 2
3 3 7 22 66
快速排序法 ( 遞迴法 )
一、分析 :
所謂快速排序法，是利用區間劃分的觀念來完成。而所謂劃分則是先在
此區間的左右兩端設定兩個註標，並在其中選擇一個鍵值，此鍵值可隨機選
擇，在此我們以中間元素當鍵值，鍵值 x = a [(l+r)/2] ,此 l 和 r 為陣列
的左端及右端。
假設 l = 1,r = 8
, 並以 48 為鍵值，考慮以下例子：
79 -10 3
48 90 7 42
11
i
x
j
然後 i由左向右檢查，而 j由右向左檢查，直到找出比 x大（小）的資料，若
i <= j，則互換 i及 j位置的資料，並 將 i 加 1，j 減 1。
79 -10 3
48 90 7 42
11
i
x
j
11 -10 3
48 90 7 42
79
i
j
11 -10 3
42 90 7 48
79
i
j
11 -10 3
42 48 7 90
79
i j
┌─┐
11 -10 3
42 7 │48│
90 79
i1
j1 │ x│ i2 j2
└─┘
到此可看出，比鍵值 48 小的數都被放到 48 的左邊，而 48 比大的則在其
右邊，此時重新對新的兩個區間（ 11 - 7 以及 90 - 78）做排序，最後整個
列都將排序完成。
快速排序法 (遞迴法)
1
quicksort(left, right, s)
2
int left, right, s[];
3
{
4 int i, j, x, k,temp;
5
6 i = left;
7 j = right;
8 x = s[(left+right)/2];
9 do {
10 while
(s[i] < x)
11 i++;
12 while
(s[j] > x)
13 j--;
14 if (i <= j) {
15
if (s[i] != s[j]) {
16 }
17
temp = s[j];
18
s[j] = s[i];
19
s[i] = temp;
20 }
21 i++;
22 j--;
23 }
24
25 } while (i <= j)
26 ;
27 if (left <= j)
28
quicksort(left, j, s);
29 if (i < right)
30
quicksort(i, right, s);
31 }
輸出結果
There are 8
intergers to sort.
7 3 66 3 -5 22
-77 2
2 3 66 3 -5 22
-77 7
2 -77
66 3 -5 22 3 7
2 -77
-5 3 66 22 3 7
2 -77
-5 3 66 22 3 7
-77 2 -5 3 66 22 3 7
-77 2 -5 3 66 22 3 7
-77 -5 2 3 66 22 3 7
-77 -5 2 3 66 22 3 7
-77 -5 2 3 7 22 3 66
-77 -5 2 3 7 3 22 66
-77 -5 2 3 3 7 22 66
-77 -5 2 3 3 7
22 66
-77 -5 2 3 3 7 22 66
... Quick Sort ...
-77 -5 2 3 3 7 22 66
1
quicksort(left, right, s)
2
int left, right, s[];
3
{
4 int i, j, x, k,temp;
5
6 i = left;
7 j = right;
8 x = s[(left+right)/2];
9 do {
10 while
(s[i] < x)
11 i++;
12 while
(s[j] > x)
13 j--;
14 if (i <= j) {
15
if (s[i] != s[j]) {
16 }
17
temp = s[j];
18
s[j] = s[i];
19
s[i] = temp;
20 for (k
= left; k <= right; k++) {
21
printf("%5d%c", s[k],((k%10 == 9) ? '\n' : ' '));
22 }
23
printf("\n");
24 i++;
25 j--;
26 }
27
28 } while (i <= j)
29 ;
30 if (left <= j)
31
quicksort(left, j, s);
32 if (i < right)
33
quicksort(i, right, s);
34 }
輸出結果
There are 8
intergers to sort.
7 4 66 3 5 22 77 2
2 4 66 3 5 22 77 7
2 3 66 4 5 22 77 7
2 3
5 4 66 22 77 7
4 5
4
7 22 77 66
7 22 77 66
7
66 77
66
... Quick Sort ...
2 3 4 5 7 22 66 77
fputc , fgetc , fprintc , fscanf
這四個函數是針對檔案作操作，故要先宣告
FILE *data, *out ,*append;
│
└───>名稱可自定
且執行
data = fopen ( "filename" , " r ");
│
└───> 只可讀
out = fopen ( "filename" , " w ");
│
└───> 只可寫
append = fopen ( "filename" , " a ");
│
└───> 可寫,可讀
表示 data 是輸入檔之檔案指標， out 是輸出檔之檔案指標（檔名自訂）
。以後就針對這些指標作操作，而在程式結束以前，記得要
fclose ( data );
fclose ( out );
以將檔案關掉，以免資料流失。 格式如下：
fgetc ( data ) :
從 data 檔中讀取一字元傳回。
fputc ( c, out) :
將字元 c 輸出至檔案 out。
fscanf (data, format_string [
,argument......]) :
從 data 檔依格式化輸入 。
fprintf (out , format_string [
,argument......]) :
依格式外輸出至檔案 out中。
指標
(pointer)
指標(pointer)在 C 語言是極具威力的，可以深及記憶體的位址(memory
addres)
，也可以做為動態記憶體管理(dynamic memory
management)有效利器。變數在記憶
體皆有一位址，就像每個家庭有地址一般，如下圖所示。
變數 位址
── ──
┌──────────────┐
count 0 │
│┐
├──────────────┤│
1 │
││
├──────────────┤│
sum 2 │
││
├──────────────┤├ 記憶體細胞
3 │
││ (memory cell)
. └──────────────┘│
.
.
│
.
.
│
┌──────────────┐│
65535 │
│┘
└──────────────┘
count 在第 0 號的位址,
sum 在第 2 號位址............。
一、指標表示法
如何宣告指標呢？一般形式為：
┌────────┐
type ： 資料型態
│ type
*name │
└────────┘
name ： 變數名稱
如 int *ptr 這樣宣告後具有二個意義：
(一)ptr為一指標變數，此變數在記憶體有自己的位址(可用 &ptr 印出)。
(二)ptr變數所存放的數值是某一變數在記憶體的址。
#define print(x)
printf("x = %d, *x = %d, &x = %d\n",x, *x, &x)
main()
{
static int num[] = {1,2,3};
int *ptr1, *ptr2;
ptr1 = num;
ptr2 = &num[2];
print(ptr1);
ptr1++;
print(ptr1);
print(ptr2);
ptr2++;
print(ptr2);
printf("ptr2 - ptr1 =
%d\n", ptr2 - ptr1);
}
輸出結果
ptr1 = 268436528,
*ptr1 = 1, &ptr1 = 2147466868
ptr1 = 268436532,
*ptr1 = 2, &ptr1 = 2147466868
ptr2 = 268436536,
*ptr2 = 3, &ptr2 = 2147466864
ptr2 = 268436540,
*ptr2 = ?, &ptr2 = 2147466864
ptr2 - ptr1 = 2
變數 位 址 內容 變數 位 址 內容
── ─── ── ── ─── ──
┌─────┐
┌─────┐
ptr1 2147466868 │ 268436528│ ptr2 2147466864┌┤268436532 │
└──┬──┘
│└─────┘
│ ptr1=num
│ ptr2=&num[2]
<──┘
┌<─┘
│
│
│
└> 268436528 268436532
268436536 268436540
┌────┬────┬────┬────┐
│ 1 │ 2
│ 3 │ ?
│
└────┴────┴────┴────┘
&num[0]
&num[1]
&num[2]
num
num+1
num+2
本來ptr1變數所存的數值是268436528，此268436528是num陣列第1個元素，在
記憶體的位址，當執行ptr1++後ptr1指向268436532位址。ptr2指向268436536的
位址，若再向後追蹤，則指向268436540的位址而268436540位址所存的值是多
少就不得而知，因為num陣列只有3個元 素。請注意，&ptr1和&ptr2所在記憶體
位置永遠在2147466868和2147466864。
ptr2
- ptr1表示兩者之間距離，可以這樣想，當執行後，ptr2相當於num+3，而
ptr1相當於num+1，所以num+3
- (num+1)=2。
必需知道雖然陣列也具有指標之功能，但不能用前置加，減或後置加，減來運
算如例題若寫num++那是錯誤的寫法而必需寫成num+1，而指標變數可以用前置
或後置之加,減如ptr++，或ptr+1皆可，這是陣列變數與指標變數最大之不同。
二、陣列表示法
(A) 一維陣列(one dimension array)
一維陣列的宣告方法很簡單如 int
number[5]，意思是number為一維陣列，有5個
元素，每一元素是整數，請注意的是陣列的註標(subscript)是從0開始。所以有
number
[0]，number[1]，number[2]， number[3]， number[4]等5個元素。
┌─────┐
number[0]│ 4 │
├─────┤
number[1]│ 7 │
├─────┤
number[2]│ 5 │
├─────┤
number[3]│ 1 │
├─────┤
number[4]│ 3 │
└─────┘
(B) 二維陣列(two dimension array)
0 1 2 3
┌──┬──┬──┬──┐
0 │ │ │ │ │
├──┼──┼──┼──┤
1 │ ││ │ │ │
├──┼┼─┼──┼──┤
2 │ ││ │ ││ │
└──┴┼─┴──┴┼─┘
│ │
matrix[1][1]
matrix[2][3]
二維陣列與一維陣列的宣告相似只是多了一個中括弧。如果陣列有起始值則必
需是static變數才可。第六行是設定初值，亦可以
static
int matrix[3][4]={12,8,5,10,23,7,17,9,45,16,8,2}表示。
假若 static int
matrix[3][4] = {{12,8,5},{23,7,17},{45,16,8,2}}則表示
matrix[0][3] 及 matrix[1][3] 之值為 0 。
#define
constant_value 2
main()
{
int row,column;
static int matrix[3][4] = {
{12, 8, 5, 10},
{23, 7, 17, 9},
{45, 16, 8, 2},
};
printf("The original matrix[3][4]
is:\n");
for (row = 0; row < 3; row++) {
for (column =
0; column < 4; column++)
printf("%4d",matrix[row][column]);
printf("\n");
};
printf("The original matrix[3][4]
* %d is:\n", constant_value);
for (row = 0; row < 3; row++) {
for (column =
0; column < 4; column++)
printf("%4d",matrix[row][column] * constant_value);
printf("\n");
};
}
輸出結果
The original
matrix[3][4] is:
12 8
5 10
23 7 17 9
45 16 8 2
The original
matrix[3][4] * 2 is:
24 16 10 20
46 14 34 18
90 32 16 4
三. 陣列與指標
main()
{
int a, b, *ptr;
a = 100;
ptr = &a;
b = *ptr;
printf("&ptr =
%d\n\n",&ptr);
printf("ptr = %d\n",ptr);
printf("&a = %d a = %d\n",&a, a);
printf("&b = %d b = %d\n",&b, b);
}
輸出結果
&ptr =
2147466860
ptr = 2147466868
&a = 2147466868 a = 100
&b = 2147466864 b = 100
在例題中宣告ptr為一指標變數並且指定a變數所在記憶體地址給ptr，然後把a的
值指定給b。
變數 位 址 內容
變數 位 址 內容
── ───
──
── ─── ──
┌─────┐
┌──┐
ptr 2147466860 │2747466868├─> a 2147466868 │100 │
└─────┘(1)
└┬─┘
│
│(2)
│
┌┴─┐
(1) : ptr =
&a
b 2147466864 │100 │
└──┘
(2) : b = *ptr
從上面例題，可以知道＆是表示一位置(address)，而＊為其變數值(value)。如＆a
，＆b各表示a變數，b變數所在記憶體的位址。ptr=＆a，意思是將a變數的位址
指定給ptr，*ptr就相當於a之值，所以b=*ptr 乃把a之值指定給b。
main()
{
static int a[10] = {0,1,2,3,4,5,6,7,8,9};
int *ptr, i;
ptr = a;
printf("&ptr =
%d\n\n",&ptr);
for (i = 0; i < 10; i++) {
printf("ptr+%d=%d
a+%d=%d &a[%d]=%d
",i,ptr+i,i,a+i,i,&a[i]);
printf("
*(ptr+%d)=%d
a[%d]=%d\n",i,*(ptr+i),i,a[i]);
}
}
輸出結果
&ptr =
2147466868
ptr+0=268436528 a+0=268436528 &a[0]=268436528
*(ptr+0)=0 a[0]=0
ptr+1=268436532 a+1=268436532 &a[1]=268436532
*(ptr+1)=1 a[1]=1
ptr+2=268436536 a+2=268436536 &a[2]=268436536
*(ptr+2)=2 a[2]=2
ptr+3=268436540 a+3=268436540 &a[3]=268436540
*(ptr+3)=3 a[3]=3
ptr+4=268436544 a+4=268436544 &a[4]=268436544
*(ptr+4)=4 a[4]=4
ptr+5=268436548 a+5=268436548 &a[5]=268436548
*(ptr+5)=5 a[5]=5
ptr+6=268436552 a+6=268436552 &a[6]=268436552
*(ptr+6)=6 a[6]=6
ptr+7=268436556 a+7=268436556 &a[7]=268436556
*(ptr+7)=7 a[7]=7
ptr+8=268436560 a+8=268436560 &a[8]=268436560
*(ptr+8)=8 a[8]=8
ptr+9=268436564 a+9=268436564 &a[9]=268436564
*(ptr+9)=9 a[9]=9
設定a之初值並宣告為一維陣列有十個元素，注意陣列名稱a代表第一個元素的位
址和&a[0]意思一樣。例題表示陣列元素與指標之關係，希望務必要了解。輸出
結果以下圖表示之：
變數 位 址 內容
── ─── ──
┌─────┐
ptr 2147466868 │268436528 │
└──┬──┘
│
│
┌<───────────┘
└>268436528
268436540
268436532
....
268436536
268436564
┌┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┐
│││││││││││││││││││││││││││││││││
│││││││││││││││││││││││││││││││││
└┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┘
ptr ptr+1 ptr+2 ptr+3
ptr+4 ... ptr+9
a a+1 a+2 a+3 a+4
...
a+9
&a[0] &a[1] &a[2] &a[3] &a[4] ... &a[9]
*ptr=a[0],
*(ptr+1)=a[1], *(ptr+2)=a[2],... *(ptr+9)=a[9]由於 int佔 4 byte，所以
&a[0]
及 &a[1]相差 4，以此類推。
main()
{
int i,j;
static int a[3][3] = {
{1,2,3},
{4,5,6},
{7,8,9}};
int *ptr;
ptr = &a[0][0];
printf("&ptr =
%d\n\n",&ptr);
for (i = 0; i < 9; i++)
printf("ptr + %d = %d
*(ptr + %d) = %d\n",i,ptr+i,i,*(ptr+i));
printf("\n");
for (i = 0; i < 3; i++)
for (j = 0; j
< 3; j++)
printf("&a[%d][%d] = %d a[%d][%d] =
%d\n",i,j,&a[i][j],i,j,a[i][j]);
printf("\n");
for (i = 0; i < 3; i++)
printf("a[%d] = %d a + %d = %d\n",i,a[i],i,a+i);
}
輸出結果
&ptr =
2147466860
ptr + 0 =
268436528 *(ptr + 0) = 1
ptr + 1 =
268436532 *(ptr + 1) = 2
ptr + 2 =
268436536 *(ptr + 2) = 3
ptr + 3 =
268436540 *(ptr + 3) = 4
ptr + 4 =
268436544 *(ptr + 4) = 5
ptr + 5 =
268436548 *(ptr + 5) = 6
ptr + 6 =
268436552 *(ptr + 6) = 7
ptr + 7 =
268436556 *(ptr + 7) = 8
ptr + 8 =
268436560 *(ptr + 8) = 9
&a[0][0] =
268436528 a[0][0] = 1
&a[0][1] =
268436532 a[0][1] = 2
&a[0][2] =
268436536 a[0][2] = 3
&a[1][0] =
268436540 a[1][0] = 4
&a[1][1] =
268436544 a[1][1] = 5
&a[1][2] =
268436548 a[1][2] = 6
&a[2][0] =
268436552 a[2][0] = 7
&a[2][1] =
268436556 a[2][1] = 8
&a[2][2] =
268436560 a[2][2] = 9
a[0] =
268436528 a + 0 =
268436528
a[1] =
268436540 a + 1 =
268436540
a[2] =
268436552 a + 2 =
268436552
變數 位 址 內容
── ─── ──
┌─────┐
ptr 2147466860 │268436528 │
└──┬──┘
│ ptr=&a[0][0]
┌─────────────┘
│
└>268436528
268436540
268436532
....
268436536
268436560
┌┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┐
│││││││││││││││││││││││││││││││││
│││││││││││││││││││││││││││││││││
└┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┘
ptr ptr+1 ptr+2
ptr+3 ptr+4 ptr+5 prt+6 ...
ptr+8
&a[0][0] &a[0][1]
&a[1][0] &a[1][2] ... &a[2][2]
a[0]
a[1]
a[2]
a
a+1
a+2
例題是二維陣列與指標關係
,&a[0][0]、a 和a[0]都指向相同的位址，同樣&a[1][0]
、a+1 和 a[1]、&a[2][0]、a+2 和a[2]也指向相同的位址。
真正變數值a[0][0]=1，a[0][1]=2，...a[2][2]=9。因為 a 陣列為整數型態故相鄰元
素所在的位址街相差4。
main()
{
int i,j;
static int a[3][3] = {
{1,2,3},
{4,5,6},
{7,8,9}};
for (i = 0; i < 3; i++)
for (j = 0; j
< 3; j++)
printf("&a[%d][%d] = %d \n", i,j,&a[i][j]);
printf("\n");
for (i = 0; i < 3; i++)
printf("a
+ %d = %d\n",i,a+i);
}
輸出結果
&a[0][0] =
268436528
&a[0][1] =
268436532
&a[0][2] =
268436536
&a[1][0] =
268436540
&a[1][1] =
268436544
&a[1][2] =
268436548
&a[2][0] =
268436552
&a[2][1] =
268436556
&a[2][2] =
268436560
a + 0 = 268436528
a + 1 = 268436540
a + 2 = 268436552
main()
{
int i,j,k;
static int a[2][3][4] =
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24 };
for (i = 0; i < 2; i++)
for (j = 0; j
< 3; j++)
for (k
= 0; k < 4; k++)
printf("&a[%d][%d][%d] = %d \n", i,j,k,&a[i][j][k]);
for (i = 0; i < 2; i++)
printf("a
+ %d = %d\n",i,a+i);
for (i = 0; i < 2; i++)
for (j = 0; j
< 3; j++)
printf("a[%d] + %d = %d\n",i,j,a[i]+j);
for (i = 0; i < 2; i++)
for (j = 0; j
< 3; j++)
for (k
= 0; k < 4; k++)
printf("a[%d][%d]+%d = %d\n",i,j,k,a[i][j]+k);
for (i = 0; i < 2; i++)
for (j = 0; j
< 3; j++)
for (k
= 0; k < 4; k++)
printf("a[%d][%d][%d]+%d = %d\n",i,j,k,k,a[i][j][k]+k);
}
輸出結果
&a[0][0][0] =
268436528 a + 0 = 268436528 a[0][0]+0 = 268436528
&a[0][0][1] =
268436532 a + 1 = 268436576 a[0][0]+1 = 268436532
&a[0][0][2] =
268436536 a[0] + 0 = 268436528
a[0][0]+2 = 268436536
&a[0][0][3] =
268436540 a[0] + 1 = 268436544
a[0][0]+3 = 268436540
&a[0][1][0] =
268436544 a[0] + 2 = 268436560
a[0][1]+0 = 268436544
&a[0][1][1] =
268436548 a[1] + 0 = 268436576
a[0][1]+1 = 268436548
&a[0][1][2] =
268436552 a[1] + 1 = 268436592
a[0][1]+2 = 268436552
&a[0][1][3] =
268436556 a[1] + 2 = 268436608
a[0][1]+3 = 268436556
&a[0][2][0] =
268436560
a[0][2]+0 = 268436560
&a[0][2][1] =
268436564
a[0][2]+1
= 268436564
&a[0][2][2] =
268436568
a[0][2]+2 = 268436568
&a[0][2][3] =
268436572
a[0][2]+3 = 268436572
&a[1][0][0] =
268436576
a[1][0]+0 = 268436576
&a[1][0][1] =
268436580
a[1][0]+1 = 268436580
&a[1][0][2] =
268436584
a[1][0]+2 = 268436584
&a[1][0][3] =
268436588
a[1][0]+3 = 268436588
&a[1][1][0] =
268436592
a[1][1]+0 = 268436592
&a[1][1][1] =
268436596
a[1][1]+1 = 268436596
&a[1][1][2] =
268436600
a[1][1]+2 = 268436600
&a[1][1][3] =
268436604
a[1][1]+3 = 268436604
&a[1][2][0] =
268436608
a[1][2]+0 = 268436608
&a[1][2][1] =
268436612
a[1][2]+1 = 268436612
&a[1][2][2] =
268436616
a[1][2]+2 = 268436616
&a[1][2][3] =
268436620
a[1][2]+3 = 268436620
a[0][0][0]+0 = 1
a[0][0][1]+1 = 3
a[0][0][2]+2 = 5
a[0][0][3]+3 = 7
a[0][1][0]+0 = 5
a[0][1][1]+1 = 7
a[0][1][2]+2 = 9
a[0][1][3]+3 = 11
a[0][2][0]+0
= 9
a[0][2][1]+1 = 11
a[0][2][2]+2 = 13
a[0][2][3]+3 = 15
a[1][0][0]+0
= 13
a[1][0][1]+1 = 15
a[1][0][2]+2 = 17
a[1][0][3]+3 = 19
a[1][2][0]+0
= 21 a[1][1][0]+0 = 17
a[1][2][1]+1 = 23
a[1][1][1]+1 = 19
a[1][2][2]+2 = 25
a[1][1][2]+2 = 21
a[1][2][3]+3 = 27
a[1][1][3]+3 = 23
/*
字元處理：改變一列文字，將字串中的e改成E，並將每個空格改成一個新列
字元和定位字元 */
#define MAXLINE 100
#include <stdio.h>
main()
{
char line[MAXLINE], *change();
printf ("\nWhat is your favorite line? ");
read_in(line);
printf ("\n%s\n\n%s\n\n",
"Here it is after being changed :",change(line));
}
read_in(s)
char s[];
{
int c,i=0;
while ((c = getchar()) != EOF && c != '\n')
s[i++] = c ;
s[i] = '\0';
}
char *change(s)
char *s;
{
static char
new_string[MAXLINE];
char *p=new_string;
*p++ = '\t';
for ( ; *s != '\0' ; ++s)
if (*s == 'e')
*p++ = 'E' ;
else if (*s == ' ') {
*p++ = '\n' ;
*p++ = '\t' ;
}
else
*p++ = *s ;
*p = '\0';
return ( new_string );
}
假設輸入 : she sells
sea shells
輸出結果
shE
sElls
sEa
shElls
main()
{
char *p, *q;
p = q = " RICH";
printf("%s%s%s\n", p,p,p);
*++q = 'p';
*++q = 'o';
*++q = 'o';
*++q = 'r';
printf("%s%s%s\n", p,p,p);
}
輸出結果
RICH RICH RICH
poor poor poor
ascii(7)
| 00 nul| 01 soh| 02
stx| 03 etx| 04 eot| 05 enq| 06 ack| 07 bel|
| 08 bs | 09 ht | 0a
nl | 0b vt | 0c np | 0d cr | 0e so | 0f si |
| 10 dle| 11 dc1| 12
dc2| 13 dc3| 14 dc4| 15 nak| 16 syn| 17 etb|
| 18 can| 19 em | 1a
sub| 1b esc| 1c fs | 1d gs | 1e rs | 1f us |
| 20 sp | 21 ! | 22 " | 23 # |
24 $ | 25 % | 26 & | 27 ' |
| 28 ( | 29 ) | 2a * | 2b + | 2c , | 2d - |
2e . | 2f / |
| 30 0 | 31 1 | 32 2 | 33 3 | 34 4 | 35 5 |
36 6 | 37 7 |
| 38 8 | 39 9 | 3a : | 3b ; | 3c < | 3d = |
3e > | 3f ? |
| 40 @ | 41 A | 42 B | 43 C | 44 D | 45 E |
46 F | 47 G |
| 48 H | 49 I | 4a J | 4b K | 4c L | 4d M |
4e N | 4f O |
| 50 P | 51 Q | 52 R | 53 S | 54 T | 55 U |
56 V | 57 W |
| 58 X | 59 Y | 5a Z | 5b [ | 5c \ | 5d ] |
5e ^ | 5f _ |
| 60 ` | 61 a | 62 b | 63 c | 64 d | 65 e |
66 f | 67 g |
| 68 h | 69 i | 6a j |
6b k | 6c l | 6d m | 6e n |
6f o |
| 70 p | 71 q | 72 r | 73 s | 74 t | 75 u |
76 v | 77 w |
| 78 x | 79 y | 7a z | 7b { | 7c | | 7d } |
7e | 7f del|
main()
{
int i;
static char
*p[6]={"abc","def","hi","jklmo","pqrstuvw","xyz"};
printf("p = %d\n", p);
printf("*p = %d\n", *p);
printf("**p = %d\n", **p);
for (i = 0; i < 6; i++)
printf("p[%d] = %d\n", i,p[i]);
for (i = 0; i < 6; i++)
printf("*p[%d] = %d\n", i,*p[i]);
for (i = 0; i < 6; i++)
printf("&(*p[%d]) = %d\n", i,&(*p[i]));
for (i = 0; i < 6; i++)
printf("&(p[%d]) = %d\n", i,&p[i]);
}
輸出結果
p
= 268436528
*p
= 268440000
**p
= 97
p[0]
= 268440000
p[1]
= 268440004
p[2]
= 268440008
p[3]
= 268440012
p[4]
= 268436552
p[5]
= 268440020
*p[0]
= 97
*p[1]
= 100
*p[2]
= 104
*p[3]
= 106
*p[4]
= 112
*p[5]
= 120
&(*p[0])
= 268440000
&(*p[1])
= 268440004
&(*p[2])
= 268440008
&(*p[3])
= 268440012
&(*p[4])
= 268436552
&(*p[5])
= 268440020
&(p[0])
= 268436528
&(p[1])
= 268436532
&(p[2])
= 268436536
&(p[3])
= 268436540
&(p[4])
= 268436544
&(p[5])
= 268436548
main()
{
int i;
static char
*p[6]={"abc","def","hi","jklmo","pqrstuvw","xyz"};
printf("p = %d\n", p);
printf("*p = %d\n", *p);
printf("**p = %d\n", **p);
for (i = 0; i < 6; i++)
printf("p[%d] = %d\n", i,p[i]);
printf("\n");
for (i = 0; i < 3; i++) {
printf("p[0]+%d = %d\n",i, p[0]+i);
printf("*(p[0]+%d) = %d\n", i,*(p[0]+i));
}
printf("\n");
for (i = 0; i < 3; i++) {
printf("p[1]+%d
= %d\n",i, p[1]+i);
printf("*(p[1]+%d) = %d\n", i,*(p[1]+i));
}
printf("\n");
for (i = 0; i < 2; i++) {
printf("p[2]+%d = %d\n",i, p[2]+i);
printf("*(p[2]+%d) = %d\n", i,*(p[2]+i));
}
printf("\n");
for (i = 0; i < 5; i++) {
printf("p[3]+%d = %d\n",i, p[3]+i);
printf("*(p[3]+%d) = %d\n", i,*(p[3]+i));
}
printf("\n");
for (i = 0; i < 8; i++) {
printf("p[4]+%d = %d\n",i, p[4]+i);
printf("*(p[4]+%d) = %d\n", i,*(p[4]+i));
}
printf("\n");
for (i = 0; i < 3; i++) {
printf("p[5]+%d = %d\n",i, p[5]+i);
printf("*(p[5]+%d) = %d\n", i,*(p[5]+i));
}
}
輸出結果
p = 268436528
*p = 268440160
**p = 97
p[0] = 268440160
p[1] = 268440164
p[2] = 268440168
p[3] = 268440172
p[4] = 268436552
p[5] = 268440180
p[0]+0 = 268440160
*(p[0]+0) = 97
p[0]+1 = 268440161
*(p[0]+1) = 98
p[0]+2 = 268440162
*(p[0]+2) = 99
p[1]+0 = 268440164
*(p[1]+0) = 100
p[1]+1 = 268440165
*(p[1]+1) = 101
p[1]+2 = 268440166
*(p[1]+2) = 102
p[2]+0 = 268440168
*(p[2]+0) = 104
p[2]+1 = 268440169
*(p[2]+1) = 105
p[3]+0 = 268440172
*(p[3]+0) = 106
p[3]+1 = 268440173
*(p[3]+1) = 107
p[3]+2 = 268440174
*(p[3]+2) = 108
p[3]+3 = 268440175
*(p[3]+3) = 109
p[3]+4 = 268440176
*(p[3]+4) = 111
p[4]+0 = 268436552
*(p[4]+0) = 112
p[4]+1 = 268436553
*(p[4]+1) = 113
p[4]+2 = 268436554
*(p[4]+2) = 114
p[4]+3 = 268436555
*(p[4]+3) = 115
p[4]+4 = 268436556
*(p[4]+4) = 116
p[4]+5 = 268436557
*(p[4]+5) = 117
p[4]+6 = 268436558
*(p[4]+6) = 118
p[4]+7 = 268436559
*(p[4]+7) = 119
p[5]+0 = 268440180
*(p[5]+0) = 120
p[5]+1 = 268440181
*(p[5]+1) = 121
p[5]+2 = 268440182
*(p[5]+2) = 122
main()
{
int i,j;
static char
*p[2][3]={"abc","def","hi","jklmo","pqrstuvw","xyz"};
printf("p = %d\n", p);
printf("*p = %d\n", *p);
printf("**p = %d\n", **p);
printf("***p = %d\n", ***p);
for (i = 0; i < 2; i++)
for (j = 0; j
< 3; j++)
printf("p[%d][%d] = %d\n", i,j,p[i][j]);
for (i = 0; i < 2; i++)
for (j = 0; j
< 3; j++)
printf("*p[%d][%d] = %d\n", i,j,*p[i][j]);
for (i = 0; i < 2; i++)
for (j = 0; j
< 3; j++)
printf("&(*p[%d][%d]) = %d\n", i,j,&(*p[i][j]));
for (i = 0; i < 2; i++)
for (j = 0; j
< 3; j++)
printf("&(p[%d][%d]) = %d\n", i,j,&p[i][j]);
}
輸出結果
p = 268436528
*p = 268436528
**p = 268440032
***p = 97
p[0][0] =
268440032
p[0][1] =
268440036
p[0][2] =
268440040
p[1][0] =
268440044
p[1][1] =
268436552
p[1][2] =
268440052
*p[0][0] = 97
*p[0][1] = 100
*p[0][2] = 104
*p[1][0] = 106
*p[1][1] = 112
*p[1][2] = 120
&(*p[0][0]) =
268440032
&(*p[0][1]) =
268440036
&(*p[0][2]) =
268440040
&(*p[1][0]) =
268440044
&(*p[1][1]) =
268436552
&(*p[1][2]) =
268440052
&(p[0][0]) =
268436528
&(p[0][1]) =
268436532
&(p[0][2]) =
268436536
&(p[1][0]) =
268436540
&(p[1][1]) =
268436544
&(p[1][2]) =
268436548
┌─────────────────────┬─────────┐
│ Operator
│ Associativity │
├─────────────────────┼─────────┤
│ () [] -> │ left to right │
├─────────────────────┼─────────┤
│ ! ++
-- - (type) *
& sizeof │ right to left
│
├─────────────────────┼─────────┤
│ * / %
│ left to right │
├─────────────────────┼─────────┤
│ + -
│ left to right │
├─────────────────────┼─────────┤
│ << >>
│ left to right │
├─────────────────────┼─────────┤
│ < <= > >=
│ left to right │
├─────────────────────┼─────────┤
│ == !=
│ left to right │
├─────────────────────┼─────────┤
│ &
│ left to right │
├─────────────────────┼─────────┤
│ ^
│ left to right │
├─────────────────────┼─────────┤
│ |
│ left to right
│
├─────────────────────┼─────────┤
│ &&
│ left to right │
├─────────────────────┼─────────┤
│ ||
│ left to right │
├─────────────────────┼─────────┤
│ ？:
│ right to left │
├─────────────────────┼─────────┤
│ = += -= etc.
│ right to left │
├─────────────────────┼─────────┤
│ ,
│ left to right │
└─────────────────────┴─────────┘
位元運算
( bits operation )
Ｃ語言提供六種運算，位元運算子(bit operators)如表
1。說明如下：
表 一：
────────────────────
符 號
意 義
────────────────────
&
且 ( AND )
|
或 (inclusive OR )
^
或 (exclusive OR )
~
1 補數
<<
左移
>>
右移
────────────────────
一、且 (AND)→ & ：只有在兩個位元皆為 1 時才為 1，其餘皆為零。
main ()
{
int num1 = 067, num2 = 025, num3
= 046;
printf (" ..... bitwise AND
(&) operator .....\n\n");
printf ("\t %d & %d = %o
\n\n", num1 ,num1 ,num1 & num1 );
printf ("\t %d & %d = %o
\n\n", num2 ,num1 ,num1 & num2 );
printf ("\t %d & %d = %o
\n\n", num3 ,num1 ,num1 & num3 );
printf ("\t %d & %d = %o
\n\n", num2 ,num3 ,num2 & num3 );
printf ("\t %d & %d
& %d = %o \n\n", num1 ,num2 ,num3 ,num1 & num2 & num3 );
}
..... bitwise AND (&)
operator .....
55 & 55 = 67
21 & 55 = 25
38 & 55 = 46
21 & 38 = 4
55 & 21 & 38 = 4
請注意，宣告 num1，num2，num3是以八進位表示，因為前面是以0為開始。
num1 = (067) =
(55) = (110111)
8 10
2
num2 = (025) =
(21) = (010101)
8 10
2
num3 = (046) =
(38) = (100110)
8 10
2
運算過程及結果如下：
(55) & (55) =
(110111) & (110111) = (110111) = (067)
10
10
2 2
2
8
(55) & (21) =
(110111) & (010101) = (010101) = (25)
10
10
2
2
2
8
(55) & (38) =
(110111) & (100110) = (100110) = (46)
10
10
2
2
2
8
(21) & (38) =
(010101) & (100110) = (000100) = (4)
10
10
2
2
2 8
(55) & (21) &
(38) = (110111) & (000100) = (000100) = (4)
10
10
10
2
2
2
8
二、或 (OR)→ | ：當兩個位元其中有一為 1 時就為 1。
main ()
{
int num1 = 067, num2 = 025, num3
= 046;
printf (" ..... bitwise OR
(|) operator .....\n\n");
printf ("\t %d | %d = %o
\n\n", num1 ,num1 ,num1 | num1 );
printf ("\t %d | %d = %o
\n\n", num2 ,num1 ,num1 | num2 );
printf ("\t %d | %d = %o
\n\n", num3 ,num1 ,num1 | num3 );
printf ("\t %d | %d = %o
\n\n", num2 ,num3 ,num2 | num3 );
printf ("\t %d | %d & %d
= %o \n\n", num1 ,num2 ,num3 ,num1 | num2 | num3 );
}
..... bitwise OR (|)
operator .....
55 | 55 = 67
21 | 55 = 67
38 | 55 = 67
21 | 38 = 67
55 | 21 | 38 = 67
(55) | (55) =
(110111) | (110111) = (110111) = (067)
10 10
2
2
2 8
(55) | (21) =
(110111) | (010101) = (110111) = (067)
10 10
2
2
2 8
(55) | (38) =
(110111) | (100110) = (110111) = (067)
10 10
2
2
2 8
三、 1 補數 (~)，與exclusive OR(^)：1補數是把1變成0，0變成1，而exclusive如
表 2。
表 2 ：
────────────────────
A B
A (exclusive OR ) B
────────────────────
0 0
0
0 1
1
1 0
1
1 1 0
────────────────────
main ()
{
int num1 = 067, num2 = 025, num3
= 046;
printf (" ..... bitwise
exclusive (^) operator .....\n\n");
printf ("\t %d ^ %d = %o
\n\n", num1 ,num1 ,num1 ^ num1 );
printf ("\t %d ^ %d = %o
\n\n", num2 ,num1 ,num1 ^ num2 );
printf ("\t %d ^ %d = %o
\n\n", num3 ,num1 ,num1 ^ num3 );
printf ("\t %d ^ %d = %o
\n\n", num2 ,num3 ,num2 ^ num3 );
printf ("\t %d ^ %d ^ %d =
%o \n\n", num1 ,num2 ,num3 ,num1 ^ num2 ^ num3 );
}
..... bitwise
exclusive (^) operator .....
55 ^ 55 = 0
21 ^ 55 = 42
38 ^ 55 = 21
21 ^ 38 = 63
55 ^ 21 ^ 38 = 4
main()
{
int num1 = 067, num2 = 025, num3 = 046;
printf("..... Before exclusive OR
(^) operation .....\n\n");
printf("\t num1 = %d \t num2 =
%d\n\n",num1, num2);
/* exchange num1, num2 */
num1 ^=
num2;
num2 ^=
num1;
num1 ^=
num2;
printf("..... After exclusive OR (^) operation
.....\n\n");
printf("\t num1 = %d \t num2 =
%d\n\n",num1, num2);
}
..... Before
exclusive OR (^) operation .....
num1 = 55 num2 = 21
..... After exclusive OR (^) operation .....
num1 = 21 num2 = 55
四、位元左移(<<)與位元右移(>>)：>>n和<<n分別表向右移或向左移n個bits。
main()
{
int num1 = 017777, num2 = 0444;
printf("..... bitwise shift
(>>, <<) operator .....\n\n");
printf("\t %o >> 1 = %o
\n\n", num1, num1 >> 1);
printf("\t %o >> 2 = %o
\n\n", num1, num1 >> 2);
printf("\t %o >> 6 = %o
\n\n", num1, num1 >> 6);
printf("\t %o >> 1 = %o
\n\n", num2, num2 >> 1);
printf("\t %o >> 3 = %o
\n\n", num2, num2 >> 3);
printf("\t %o << 5 = %o
\n\n", num1, num1 << 5);
printf("\t %o << 2 = %o
\n\n", num2, num2 << 2);
}
..... bitwise
shift (>>, <<) operator .....
17777 >> 1 = 7777
17777 >> 2 = 3777
17777 >> 6 = 177
444 >> 1 = 222
444 >> 3 = 44
17777 << 5 = 777740
444 << 2 = 2220
int_size()
{
int n, c, j;
n = 0;
n = ~n
c = 1;
for (j=0; n & c; j++, c <<=
1)
;
return (j);
}
結構體
( struct )
┌───────────┐
│ 結構體 ( structure ) │
└───────────┘
┌────────────┐
│可由 User 自定的資料型別│
└────────────┘
日常生活中所遇到的資料種類太多，任何高階語言，設想再周到也無法包括各
式各樣的資料形態。為了解決這個問題，ｃ語言提供了 "可由 User 自建的" 資料
型別。由 User 定義的資料型別，則是由基本資料型別構成的複合式資料型別，
語言把這種複合式資料型別叫做結構體。
假設學校的電算中心要將全校每個學生的基本資料建成檔案時，會有哪些資料
要輸入呢？我們假設以下就是所需的資料和其型別：
資料項目 資料型別
例如
─────── ─────────── ───────────
─────── ─────────── ───────────
姓名 字串
char name[10] 張大功
地址 字串
char addr[60] 台南市大學路 1號
年齡 整數 int
age
27
每個學生就有三項基本資料要輸入，而且資料型別與長度各有不同，我們可以把學生的資料建立成一個結構體型別，以方便處理。我們把這新建的行別叫
person
，此型別是一複合體，共由人名、地址、年齡三部份組成，此三個
部份依次為字串、字串、整數等基本資料型別：
┌─────┬─────┬────┐
person : │ name │
addr │ age │（各資料向長度不同）
└──┬──┴──┬──┴─┬──┘
（複合式型別） │ │ └─── 整數型別
│ │
│ └──────── 字串型別
│
└────────────── 字串型別
┌───────┐
│ 結構體的宣告 │
└───────┘
結構體的宣告與一般變數的宣告有層次上的差異。因為結構體本身是一種型別
而不是變數，所以結構體的宣告是建立一個新的型別，而不是宣告一個新的變
數。必須此結構體型別建好之後，才能用來宣告變數，這是不同的兩個層次。
結構體的宣告方式有兩種：
一、分離式宣告
───────
先在程式最前面宣告結構體的組成內容，然後再把變數宣告成該結構體型別。
上述學生的基本資料就可這樣宣告：
┌────────────
struct 指令
│
│ ┌───────── 結構體型別名
│ │
│ │ ┌─── 結構體內容
│ │ │
struct person
{ │
char name[10] ; /* 姓名
*/ ──┐
│
char addr[60] ; /* 地址
*/ ├─ 設定資料項
│
int age ; /* 年齡 */ ──┘
}; ──────── 此階段建立一個 person 型別
main ()
{
struct person student ; ────── 此階段宣告 student 變數
................
為 person 型別
}
此處 struct 是ｃ的保留字指令，用來宣告結構體型別。在 struct 之後我們可以放
一個型別名 (tag)，此處 person 即為我們所建的型別名。而person 後面{ }內部所
列即為結構體型別的組成部份。此處我們宣告 person這個結構體型別共由 name 元陣列、addr字元陣列、以及 age整數變數三部份組成，這些組成部份我們稱為
資料項 (member) 。宣告了 person 型別，以後只要提到 person ，ｃ編譯器便知道
這是一個由 name 字元陣列、addr字元陣列、以及 age整數變數組成的結構體型
別。
宣告了 person 型別後，接著我們就可以利用 person 來宣告變數：
┌────────────
struct 指令
│
│ ┌───────── 結構體型別名
│ │
struct person
student ─── 變數名
就表示 student這個變數是 person 這種結構體型別。
二、結合型宣告
───────
這種宣告方式不僅宣告了結構體內的資料項，同時也宣告了結構體變數名稱，
也就是把分離型宣告的兩個階段合而為一：
┌────────────
struct 指令
│
│ ┌───────── 結構體型別名
│ │
│ │
struct person {
char name[10] ;
──┐
│
char addr[30] ; ├─ 資料項
│
int age ; ──┘
}; student ; /* 宣告 student 是
person 型別 */
│
└──── 變數名
有時候，如果我們確定接下來不會再宣告該結構體型別的變數，則上列宣告中
的結構體型別名（即 person ）也可以省略，因以後不使用。
/* compute the
size of the fundamental types */
main()
{
printf("The size of the
fundamental types is computed.\n\n");
printf(" char:%3d bytes\n", sizeof(char));
printf(" short:%3d bytes\n", sizeof(short));
printf(" int:%3d bytes\n", sizeof(int));
printf("unsigned:%3d
bytes\n", sizeof(unsigned));
printf(" long:%3d bytes\n", sizeof(long));
printf(" float:%3d bytes\n", sizeof(float));
printf(" double:%3d bytes\n", sizeof(double));
}
輸出結果
The size of the
fundamental types is computed.
char: 1 bytes
short: 2 bytes
int: 4 bytes
unsigned: 4 bytes
long: 4 bytes
float: 4 bytes
double: 8 bytes
struct test {
char a;
int i;
char b;
};
main ()
{
struct test test_size;
printf ("size of struct test = %d
byte \n",
sizeof
(struct test ));
printf ("size of variable test = %d
byte \n",sizeof (test_size));
}
輸出結果
size of struct
test = 12 byte
size of variable
test = 12 byte
struct test {
char a;
char b;
int i;
};
main ()
{
struct test test_size;
printf ("size of struct test = %d
byte \n",
sizeof
(struct test ));
printf ("size of variable test = %d
byte \n",sizeof (test_size));
}
輸出結果
size of struct
test = 8 byte
size of variable
test = 8 byte
我們可以用 sizeof
算符來求出結構體在電腦中實際所佔的空間。
struct person {
char name[30] ;
char addr[20] ;
int age ;
};
main ()
{
struct person student;
printf ("size of struct person =
%d byte \n",sizeof (struct person ));
printf ("size of variable student
= %d byte \n",sizeof (student ));
}
執行結果：
size of struct person = 56 byte
size of variable student = 56 byte
在電腦記憶體中結構體的資料項是連串排列在一起的：
char
char
int
┌────┬─────┬─┬───┐
student │name[20]│ addr[30] │
│ age │
└────┴─────┴┬┴───┘
└─┬─┘└─┬──┘ │└─┬─┘
佔 20
bytes 佔 30 bytes │ 佔 4 bytes
│
佔 2 bytes
┌───────┐
│ 結構體的陣列 │
└───────┘
結構體也可以組成陣列，其宣告方法如下：
strust 結構體名 陣列名 〔
元素個數 〕;
如果學校中一班級有 20 個學生的話，我們可以宣告一個結構體陣列來容納這些
資料。
struct person {
char name[30] ;
char addr[20] ;
int age ;
};
main
()
{
struct person student[20]; ───────── 宣告結構體陣列
printf ("size of student array = %d
byte \n",sizeof (student ));
}
執行結果：
size
of student array = 1120 byte
在記憶體中， student 的結構體陣列也是以連續排列的方法儲存的：
char
char
int
┌────┬─────┬─┬────┐
student [0] │name[20]│ addr[30] │ │
age │
├────┼─────┼─┼────┤
student [1] │name[20]│ addr[30] │ │
age │
├────┼─────┼─┼────┤
student [2] │name[20]│ addr[30] │ │
age │
├────┼─────┼─┼────┤
. │ ... │
... │ │
... │
. ├────┼─────┼─┼────┤
student [18] │name[20]│ addr[30] │ │
age │
├────┼─────┼─┼────┤
student [19] │name[20]│ addr[30] │ │
age │
├────┼─────┼─┼────┤
└────┴─────┴─┴────┘
└─┬─┘ └─┬─┘ └┬┘
佔 20 bytes 佔 30 bytes 佔 4 bytes
┌─────────┐
│ 結構體的初始設定 │
└─────────┘
外在或是靜態的結構體變數可以在宣告的同時做初值設定，其方法如下：
struct person {
char *name ;
char *addr ;
int age ;
}
a = {"liu","london",25} ;
┌───────────┐
│ 存取結構體資料 │
└───────────┘
┌───────────────┐
│ 結構體資料的存取法一：`.`算符│
└───────────────┘
宣告好結構體變數之後，接下來就是要將學生資料輸進到結構體的資料項上，
有兩種方法可以存取到結構體上的資料項：使用算符．或指位器算符號－＞(減
號及大於的符號)。我們先用算符．做示範，其格式為：
結構體變數名．資料項名
例如在 student 後加 .name 時，即可存取到姓名這個資料項，以下這個例子即利用算符'.'，把一個學生的姓名、地址和年齡輸入到結構體中：
struct person {
char name[30] ;
char addr[20] ;
int age ;
};
main ()
{
struct person student;
┌───── 陣列名不必加 &
printf ("name = :"); │
scanf
("%s",student.name); ───
存入 student.name
printf
("addr = :");
scanf
("%s",student.addr);
printf
("age = :");
scanf
("%d",&student.age); ───
一般變數要加 &
/* input 3 data then display */
printf
("%-30s %-20s %3d", student.name ,
student.addr , student.age );
│
│
}
└────── 印 student 的各資料項
執行結果：
name
= : lee
addr
= : taipei_taiwan
age
= : 30
lee
taipei_taiwan
30
┌────────┐
│ 結構體指位器 │
└────────┘
結構體指位器的使用方法和一般指位器是一樣的。由於結構體中含有許多資料
項，因此結構體指位器加 1 時，其值絕對不會是只加 1 而已，而是加整個結構
體所佔的 byte 數。
struct person {
char name[30] ;
char addr[20] ;
int age ;
};
main ()
{
struct person student [20];
struct person *p; /* pointer of
structure */
int i;
p = student; ─── 把 p 指向結構體 student
for ( i = 0 ; i < 5 ; i++ , p++)
printf ("
address of person [%d] = %Nx\n",i,p);
}
執行結果：
address of person [0] = 2147465752 ─┬─ 相差 56 bytes，等於 person
│ 這個結構體的大小。
address of person [1] = 2147465808 ─┘
address of person [2] = 2147465864
address of person [3] = 2147465920
address of person [4] = 2147465976
┌───────────────┐
│ 結構體項目的存取法二：-> 算符│
└───────────────┘
要存取結構體內的資料項，還有另一種方法可以辦的到，那就是採用－＞
符號（減號與大於符號），此算符須配合指位器來使用，其寫法為：
結構體指位器－＞資料項
我們可以用一個指位器來指向一個的結構體，然後利用此指位器來存取結構體
中的個別資料項。例如 p->age 就取到結構體中的年齡這欄資料項，我們稱這種
存取法為間接存取法，而`.` 算符的方法為直接存取法。
利用指位器存取資料項的方法：`->`算符
struct person {
char name[30] ;
char addr[20] ;
int age ;
};
main ()
{
struct person student [20];
struct person *p; /* pointer of
structure */
p =
&student;
printf ("Your name :");
scanf ("%s",p->name);
printf ("Your address :");
scanf ("%s",p->addr);
printf ("Your age :");
scanf ("%s",p->age);
printf ("%-30s%-20s%3d\n",p->name,p->addr,p->age);
}
執行結果：
Your name : Lee
Your address :
Taipei
Your age : 34
Lee
Taipei 34
以一個結構體整個設給另一個結構體的方法
struct data {
char *name;
int n;
} x,y; /* x
and y are structure */
main ()
{
x.name = "Lin
S.M" ; ──┬── 設定 x 各資料項
│
x.n = 124 ; ───────┘
y = x ;
printf ("y.name
= %s, y.n = %d\n",y.name, y.n); <──┐
│
印出結構體 y 的內容 ───┘
執行結果：
y.name = Lin S.M,
y.n = 124
程式中的 y=x式子即等於
y.name=x.name和 y.n=x兩式，有了這種功能後，我
們以後在設定結構體時，就不須逐一列出每一個資料項了。
┌────────┐
│ 結構體的結構體 │
└────────┘
結構體的資料項也可以是一個結構體：
struct person {
char name[30];
int age;
};
struct card {
struct person p;
char addr [30];
} student, *stp;
當我們要設定
student 的名字時，可以寫：
┌── 多重結構體的資料項表示法
│
scanf(" %s ",
student.p.name);
或 scanf(" %s ",
stp->p.name);
┌─────────┐
│ 遞迴的結構體宣告 │
└─────────┘
結構體可以做遞迴式宣告。比如，一個串列結構，其每個節點(node)包含兩部
份：資料及只向下個節點的指位器，我們可以宣告成：
struct node {
char
*info;
struct
node *next;───遞迴的型別宣告（node宣告裡又有node）
node
node
node
┌──┬──┐ ┌──┬──┐
┌──┬──┐
─→│info│next┼─→
│info│next┼─→ .......... │info│next│
└──┴──┘ └──┴──┘
└──┴┼─┘
↓
NULL
每個節點都有一個資料項是一個的指位器(next)只向下一節點，但這樣一直指下
去，最後節點是什麼呢？最後一個next是指向NULL，這樣遞迴式宣告便有結果
了。
┌───────────┐
│ 型別名稱定義 typedef │
└───────────┘
structure
讓 user 組合自己的資料型別，而 typedef 則可以用來創新自己的型別名
稱 (type name)。比如我們可以宣告：
typedef char *STRING;
則我們就可以用 STRING 作為型別名稱來作變數宣告了：
STRING s ,lineptr[MAX];
這樣就把 s 及 lineptr 宣告成字元指位器字元指位器陣列。通常由 typedef定義出
來的新型別名稱都用大寫字母，以便與一般名稱區別。
typedef
的用途與 #define 一樣，可以使程式更清楚更容易維護。
struct list {
int data;
struct list *next;
};
每一個 struct list 型別的變數都含有 data 和 next 兩個成員。next 指標變數稱為連
結項，每個結構型別資料都可藉著 next 成員而連結至一個連續的結構上。
結構串列
┌──┬──┐
│ │ ─┼─→
└──┴──┘
data next
struct list a,b,c;
a.data = 1;
b.data = 2;
c.data = 3;
a.next = b.next =
c.next = NULL;
此程式碼的結果可以利用圖形來描述：
a
b
c
┌──┬──┐ ┌──┬──┐ ┌──┬──┐
│ 1 │NULL│ │
2 │NULL│
│ 3 │NULL│
└──┴──┘ └──┴──┘ └──┴──┘
其次，我們要串連這三個結構：
a.next = &b;
b.next = &c;
這些指標運算使得 a 連結至
b , b 連結至 c：
a
b
c
┌──┬──┐ ┌──┬──┐ ┌──┬──┐
│ 1 │ ─┼─→ │ 2 │ ─┼─→│ 3 │NULL│
└──┴──┘ └──┴──┘ └──┴──┘
線性連結串列
線性連結串列(linear
linked list)就像一條曬衣繩，上面連續的掛著資料結構。其中
的標頭指標(header
pointer)指著串列的第一個元素，然後每個元素都指向下一個元
素，而最後一個元素的連結項值為NULL。
首先我們建立一個標頭檔，此檔可被下列的串列處理函數包容。此標頭檔包括
stdio.h檔，因為它定義了NULL。
stdio.h 檔：
#include <stdio.h>
typedef char
DATA ; /* 例題中將使用 char
*/
struct linked_list {
DATA
d;
struct linked_list *next;
};
typedef struct linked_list ELEMENT;
typedef ELEMENT*
LINK;
動態的儲存體配置
list.h
檔的 struct
linked_list 宣告，不會配置儲存體，而當宣告這類型的變數和陣
列時，它就做為系統往後配置儲存體時所用的樣版，因為我們希望將這個型別
視為串列的一個元素，所以我們利用 typedef 功能將其名稱改為 ELEMENT。因
為ｃ具有用於動態地配置記憶體的公用程式，因而使得ELEMENT這種自我參考
式結構型別變得格外有用。malloc()函數由標準程式庫提供。下列形式的函數呼
叫：
malloc(size)
會傳回一個指標，其指向一段充足的記憶體，以儲存需要 size 個位元組的物體
。 malloc() 函數傳回值是一個指向 char 的指標，指向此函數所配置儲存體的基
底位址。若 head 是 LINK 型別變數，則
head = (LINK)
malloc(sizeof(ELEMENT));
將取得一段足以儲存一個 ELEMENT 的記憶體，並且將它的基底位址指定給
head指標。
假設我們要動態的建立一個線性連結串列以儲存 n、e 和 w三個字元，其
程式碼如下：
head = (LINK)
malloc(sizeof(ELEMENT));
head -> d =
`n`;
head -> next =
NULL ;
這段程式碼建立了一個單一元素的串列。
動態的建立一個串列
┌──┬──┐
head ☉──→ │ n │NULL│
└──┴──┘
下列設定運算將增加第二個元素：
head -> next =
(LINK) malloc(sizeof(ELEMENT));
head -> next
-> d = `e`;
head -> next
-> next = NULL ;
現在已經是具有二個元素的串列：
┌──┬──┐ ┌──┬──┐
head ☉──→ │ n │ ─┼─→│ e │NULL│
└──┴──┘ └──┴──┘
最後要增加第三個元素：
head -> next
-> next= (LINK) malloc(sizeof(ELEMENT));
head -> next
-> next-> d = `w`;
head -> next
-> next-> next = NULL ;
現在我們有了一個三元素的串列，head為標頭指標並以 NULL 標誌做為終止。
┌──┬──┐ ┌──┬──┐ ┌──┬──┐
head ☉──→ │ n │ ─┼─→ │ e │ ─┼─→│ w │NULL│
└──┴──┘ └──┴──┘ └──┴──┘
串列運算
下列是一些線性連結串列的基本運算：
1. 建立串列
2. 計算元素的數目
3. 查詢某一元素
4. 插入某一元素
5. 刪除某一元素
我們要設計的第一個程式會由一個字串而產生一個串列，它的傳回值是一個指
向串列標頭的指標。
/* 利用遞迴運算建立串列 */
# include "list.h"
LINK
string_to_list(s)
char s[];
{
char *malloc() ;
LINK head ;
if (s[0] == '\0') /* base case */
return (NULL);
else{
head = (LINK) malloc(sizeof(ELEMENT));
head -> d = s[0];
head -> next = string_to_list(s+1) ;
return (head);
}
}
計 數
它會沿著串列一直執行，直到發現NULL指標為止，如果是空串列就傳回0。
/* 遞迴地計算串列元素的數目 */
# include "list.h"
count(head)
LINK head ;
{
if (head == NULL)
return (0);
else
return(1 + count(head -> next ));
}
查 詢
函數是在串列中搜尋一個特定的元素，如果找到這個元素則傳回一個指向該元
素的指標，否則傳回NULL指標。
/* 在串列中查詢 c，並由
head 指出其位置 */
# include "list.h"
LINK lookup
(c,head)
DATA c;
LINK head;
{
if (head == NULL)
return(NULL);
else if (c == head ->d)
return(head);
else
return(lookup(c,head -> next));
}
插 入
串列最有用的特性之一是當我們在串列中找到適當的位置時，只需一段固定的
時間即可完成插入的動作。相對地，如果您要在大型陣列中放入一個值並且保
留其他陣列值的順序，則插入的動作所需要的時間將正比於陣列的長度，而在
新加入的值之後的所有陣列元素值都必須向後移一位。
我們以在 串列中的插入動作為例，p1和p2指向兩個相鄰的元素，q指向要插入的
元素。
插入之前：
插 入
┌──┬──┐ ┌──┬──┐
. . . │ A │ ─┼─→ │ C │ ─┼─→ . . .
┌─→└──┴──┘
┌→└──┴──┘
│
│
│
│
p1 ☉
p2 ☉
┌──┬──┐
q☉──→│ B │NULL│
└──┴──┘
插入之後：
┌──┬──┐
┌──┬──┐
. . . │ A │ ││ ┌───→
│ C │ ─┼─→ . . .
┌─→└──┴─┼┘ │ ┌─→└──┴──┘
│
│ │ │
│
│ │ │
p1 ☉
│ p2 ☉ │
│ │
└→ ┌──┬┼─┐
q ☉──→│ B ││ │
└──┴──┘
insert
() 函數將 q所指的元素放在 p1 和 p2 所指的元素之間：
/* 在連結串列中插入一個元素 */
#include "list.h"
insert (p1,p2,q)
LINK p1,p2,q;
{
p1 -> next = q; /* 插 入 */
q -> next = p2;
}
刪 除
在線性連結串列中刪除一個元素非常簡單，只要將被刪除元素之前的元素連結
項成員設定為被刪除元素之後的元素位址即可。我們以圖形來說明刪除的動作：
刪除之前：
刪 除
┌──┬──┐ ┌──┬──┐ ┌──┬──┐
. . . │ A │ ─┼─→ │ B │ ─┼─→│ C │ ─┼─→. . .
┌─→└──┴──┘ └──┴──┘ └──┴──┘
│
│
p
☉
現在執行下列的程式碼：
p -> next = p -> next -> next ;
插入之後：
┌──────────┐
┌──┬┼─┐
┌──┬──┐ └→ ┌──┬──┐
. . . │ A ││ │ │ B │ ─┼─→ │ C │ ─┼─→. . .
┌─→└──┴──┘ └──┴──┘ └──┴──┘
│
│
p
☉
/* 遞迴地刪除一個串列 */
# include "list.h"
delete_list(head)
LINK head;
{
if (head != NULL)
{
delete_list (head -> next);
free
((char * ) head);
}
}
樹狀結構
基本觀念與定義
樹狀結構(Tree
structure)是圖形結構中一種特殊的結構，也是由節點(Node)及邊
(Edge)所構成，但樹狀結構中，有一個特定的節點叫樹根(Root)，而一般的圖形結
構，並沒有特定的根節點，這是數和圖的不同之處。例如圖一所示，就是一個
樹狀結構。
A ☉
／＼
／ ＼
↙ ↘
B ☉ C ☉
／＼ ／
↙ ↘ ↙
D ☉ E ☉ F ☉
圖 一
二元樹（Binary tree）
二元樹是樹狀結構中特殊的一種樹，在電腦科學的應用上非常廣泛，首先我們
看看二元樹名稱得由來，假如在一顆方向樹上，節點的外分支度如果小於或等
於 m 時，則稱此樹為 m 元樹(m-ary tree)，假如在一顆樹的外分支度小於或等於2
時，就叫二元樹。
二元樹資料在電腦內部的表示法
二元樹資料在電腦內部表示時，可用兩種方法。
（一）以含鏈結欄之陣列表示法
由於二元樹的每一個節點最多有兩個子樹，因此我們可以宣稱一個記錄，其中
有兩個指標，分別指向左節點及右節點的位置，以ｃ做宣稱時，可用下列方式：
typedef struct
treenode
{
char info;
int left;
int right;
} NODE;
NODE tree[20];
至於資料如何安排呢？我們可以將二元樹由上至下，由左至右給予編號，所編
的號碼，就是節點儲存在陣列中的位置，如果沒有子樹的節點，則其指標內容
以 0表示，以圖10為例，其資料儲存在陣列中以圖11表示。
A ☉ 1
／＼
／ ＼
↙ ↘
B ☉ 2 C ☉ 3
／＼
＼
↙ ↘
↘
D ☉ 4 E ☉ 5
F ☉ 6
／
↙
G ☉ 7
圖 10
info left right
┌──┬──┬──┐
1│ A │ 2 │ 3 │
├──┼──┼──┤
2│ B │ 4 │ 5 │
├──┼──┼──┤
3│ C │ 0 │ 6 │
├──┼──┼──┤
4│ D │ 0 │ 0 │
root
├──┼──┼──┤
┌──┐
5│ E │ 7 │ 0 │
│ 1 │
├──┼──┼──┤
└──┘
6│ F │ 0 │ 0 │
├──┼──┼──┤
7│ G │ 0 │ 0 │
└──┴──┴──┘
圖 11 陣列表示法
（二）鏈結表示法（Linked
represention）：
鏈結表示法，就是利用動態資料結構，將子樹的指標放到左、右兩邊的指標變
數欄內。我們可以用ｃ宣告每一個節點的結構如下：
typedef struct
treenode
{
struct treenode *left;
char info;
struct treenode *right;
} NODE;
NODE *root;
此處 root 是儲存根節點指標。
以圖10為例，其鏈結表示法如圖12所示，其中NULL表示不在指向其他節點。
┌─── root
left info↓ right
┌──┬──┬──┐
│ │ A │ │
└┼─┴──┴─┼┘
┌─┘ └─┐
↓
↓
┌──┬──┬──┐ ┌──┬──┬──┐
│ │ B │ │ │NULL│
C │ │
└┼─┴──┴─┼┘ └──┴──┴─┼┘
┌─┘ └─┐
└─┐
↓
↓
↓
┌──┬──┬──┐ ┌──┬──┬──┐ ┌──┬──┬──┐
│NULL│ D │NULL│ │ │
E │NULL│ │NULL│ F │NULL│
└──┴──┴──┘ └──┴──┴──┘ └──┴──┴──┘
┌─┘
↓
┌──┬──┬──┐
│NULL│ G │NULL│
└──┴──┴──┘
圖 12 鏈結表示法
二元樹（Binary tree）排序
利用二元樹(Binary tree)排序時，是將輸入的資料插入數中的左支或右支，而第一
個資料被放在根節點(root)，若有一二元樹目前情況如下：
┌───┐
│ 37 │
└─┬─┘
│
┌────┴───┐
│
│
┌─┴─┐ ┌─┴─┐
│ 24 │ │ 99 │
└─┬─┘ └─┬─┘
│
│
┌──┴──┐ ┌──┴──┐
│ │ │ │
≡ ┌─┴─┐≡ ┌─┴─┐
│ 31 │ │ 105 │
└─┬─┘ └─┬─┘
│
│
┌──┴──┐ ┌──┴──┐
≡ ≡ ≡ ≡
而我們要將48插入樹中，則先從Root找起，因48＞37，所以比較37的右節點，其中的資料是99，而48＜99，故找出99的左節點，但99的左節點並無資料，所
以將48建立於此，新的二元樹如下：
┌───┐
│ 37 │
└─┬─┘
│
┌─────┴─────┐
│
│
┌─┴─┐
┌─┴─┐
│ 24 │
│ 99 │
└─┬─┘
└─┬─┘
│
│
┌──┴──┐ ┌──┴──┐
│ │ │ │
≡ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
│ 31 │
│ 48 │
│ 105 │
└─┬─┘ └─┬─┘ └─┬─┘
│ │ │
┌─┴─┐ ┌─┴─┐ ┌─┴─┐
│ │ │ │ │ │
≡ ≡ ≡ ≡ ≡ ≡
/* makefile */
SRC
= print.c tree.c node.c
OBJ
= tree.o print.o node.o
a.out:
${OBJ}
cc ${OBJ}
-o p4
clean:
rm -f
core a.out ${OBJ} p4
tree.o
: tree.c
print.o
: print.c
node.o
: node.c
/* tree.h */
#
include <stdio.h>
typedef
struct node *TREE
struct
node {
int info ;
TREE left , right ;
};
int
t;
FILE *fopen() , *fp ;
TREE root , CreatNode() ;
/* tree.c */
#include "tree.h"
main()
{
int n,i,k ;
fp = fopen
("treesort.data " , "r") ;
fscanf (fp ,
"%d" , &n) ;
printf ("\nThere
are %d integers to sort.\n\n",n);
for (i=1 ; i<=n ; i++) ; {
fscanf (fp ,
"%d" , &k ) ;
root =
CreatNode (root, k) ;
printf
("%5d%c",k,((i%9 == 0) ? '\n' : ' ' )) ;
}
printf ("\n\n...tree sort...\n\n") ;
t = 1 ;
print (root) ;
printf ("\n\n") ;
fclose(fp) ;
}
/*
node.c */
#include
"tree.h"
TREE
CreatNode(ptr, k)
TREE ptr;
int k;
{
TREE p;
p = ptr;
if (ptr == NULL) {
p = (TREE)
malloc(sizeof(struct node));
p->info = k;
p->left =
NULL;
p->right =
NULL;
}
else if (k > ptr->info)
ptr->right = CreatNode(ptr->right, k);
else
ptr->left = CreatNode(ptr->left, k);
return(p);
}
/* print.c */
#include
"tree.h"
print(ptr)
TREE ptr;
{
if (ptr != NULL) {
print(ptr->left);
printf("%5d%c", ptr->info, ((t++%9 == 0) ? '\n' : ' '));
print(ptr->right);
}
}
/* treesort.data */
12
12 -7 11 999 7
3 66 3
-5 22 -77 2
輸出結果
There are 12
integers to sort.
12 -7 11 999 7 3 66 3 -5
22 -77 2
... tree sort ...
-77 -7 -5 2 3 3 7 11 12
22 66 999
鏈結串列
為了彌補以陣列製作串列之不足，遂有鏈結串列(linked list)的產生，其與陣列的主
要不同點在於：「鏈結串列」中相鄰兩項目在主記憶體的位置並不需要相鄰，
其每一資料項都有一鏈結欄，鏈結欄裡存的是下一項目的位置，因此，就可輕
易取得下一個項目的資料；鏈結串列可由圖一表示，在圖一中，變數 list 稱為
info next
┌───┬───┐
1 │ Yang │ 0 │
├───┼───┤
2 │ Mang │ 1 │
├───┼───┤
3 │ Lai │ 11 │
├───┼───┤
4
│ │ │
├───┼───┤
5 │ Huang│ 3 │
├───┼───┤
6 │ Liu │ 9 │
├───┼───┤
7
│ │ │
├───┼───┤
8 │ Cheng│ 5 │
├───┼───┤
9 │ Pon │ 12 │
├───┼───┤
10 │
│ │
├───┼───┤
11 │ Liang│ 6 │
├───┼───┤
12 │ Tasi │ 2 │
└───┴───┘
圖 一
鏈結串列在主記憶體之儲存形態
鏈結串列之指標變數（其值為8），由list指到串列首，也就是串列由位置8開始
，每一個項目包含兩欄，一個資料欄（info），另一個鏈結欄（next），例如位
置8之鏈結欄為5，代表下一個項目為位置5；位置5之鏈結欄為3，因而可鏈結至
位置3；如此繼續下去值到位置1，其鏈結欄為0，代表串列結束。
習慣上，我們都以圖2表示鏈結串列，而以指標變數list當作整個串列的名稱；因
此，圖2所示之串列稱為串列list。
8
5 1
┌───┬─┐ ┌───┬─┐ ┌───┬─┐
list ─→│Cheng │ 5├→ │Huang │ 3├→ .... ─→│Yang │ 0│
└───┴─┘ └───┴─┘ └───┴─┘
圖 2 鏈結串列的圖示法
ｃ語言提供兩種方法製做上述鏈結串列，一為含鏈結欄之陣列表示法，另一為
指標形態變數（Pointer type
variable）表示法。
以含鏈結欄之陣列表示鏈結串列
要建立圖 2 之結構體鏈結串列，必須宣告一陣列變數 a 如下：
#define N 100
typedef struct listnode {
int info;
int next;
} NODE;
NODE a[N] ;
如此一來等於宣告了100個元素的陣列變數a，而a之每一元素包含兩欄：資料欄
info與鏈結欄next。通常我們稱a之每一元素為節點（node）。
兩多項式相加
數學上兩多項式相加的問題，如以電腦程式處理，本來可以用陣列表示，但因
為有時多項式有很多缺項，如用陣列表示因會浪費主記憶體空間；因此，兩多
項式相加的問題，很適宜用鏈結串列表示多項式，首先，宣告三個多項式指標
如下：
typedef struct listnode
*NODE;
struct listnode {
float info ;
NODE next;
}
NODE a,b,c;
則多項式節點可繪示如下：
┌────┬────┬────┐
│a →coef│a →exp │a →next│
└────┴────┴────┘
其中 a → coef
代表係數
a →
exp 代表乘冪，
a →
next 為鏈結欄。
例：
多項式
A(x) = 2.5 x ** 10 + 12 x ** 6 + x ** 3
可繪示如下：
┌──┬─┬┐ ┌──┬─┬┐ ┌──┬─┬┐
a ─→│2.5 │10│┼─→│ 12 │6
│┼─→│ 1 │3 │┼─→ NULL
└──┴─┴┘ └──┴─┴┘ └──┴─┴┘
再如，多項式
B(x) = 8.5 x ** 8 + 10 x ** 6 + 5.5
可繪示如下：
┌──┬─┬┐ ┌──┬─┬┐ ┌──┬─┬┐
b ─→│8.5 │ 8│┼─→│ 10 │6
│┼─→│5.5 │0 │┼─→ NULL
└──┴─┴┘ └──┴─┴┘ └──┴─┴┘
兩多項式A(x)與B(x)相加，和為C(x)之演算法可寫如下：
1.令指標變數p指向串列a之第一個節點，同時令指標變數q指向串列b之第一個節
點。
2.比較乘冪大小，即比較p→exp與q→exp之大小，若
p→exp＞q→exp
則將p節點之內容抄錄至串列c，並將p移至下一節點位置；若
p→exp == q→exp
則將節點p與q係數欄之和，與乘冪欄之值一起抄錄至串列c，然後p與q均移至
下一節點位置；若
p→exp ＜ q→exp
則將節點q之內容抄錄至串列c，然後將q移至下一節點位置。
3.重複步驟2，直到
p＝NULL或q＝NULL
4.若p＝NULL，則將串列b剩餘部份抄錄至串列c。
5.若q＝NULL，則將串列a剩餘部份抄錄至串列c。
下圖列出 A(x) 與 B(x) 相加的前三項過程：
┌ p ─→┌──┬─┬┐ ┌──┬─┬┐ ┌──┬─┬┐
│ │2.5 │10│┼─→│ 12 │6 │┼─→│
1 │3 │┼─→ NULL
│ a ─→└──┴─┴┘ └──┴─┴┘ └──┴─┴┘
│
│
│ q ─→┌──┬─┬┐ ┌──┬─┬┐ ┌──┬─┬┐
⑴┤ │8.5 │ 8│┼─→│ 10 │6 │┼─→│5.5 │0
│┼─→ NULL
│ b ─→└──┴─┴┘ └──┴─┴┘ └──┴─┴┘
│
│
│ ┌──┬─┬┐
└ c ─→│2.5 │10│┼─→ NULL （ p→exp ＞ q→exp ）
└──┴─┴┘
p─┐
┌ ┌──┬─┬┐└→┌──┬─┬┐ ┌──┬─┬┐
│ │2.5 │10│┼─→│ 12 │6 │┼─→│
1 │3 │┼─→ NULL
│ a ─→└──┴─┴┘ └──┴─┴┘ └──┴─┴┘
│
│
│ q ─→┌──┬─┬┐ ┌──┬─┬┐ ┌──┬─┬┐
⑵┤ │8.5 │ 8│┼─→│ 10 │6 │┼─→│5.5 │0
│┼─→ NULL
│ b ─→└──┴─┴┘ └──┴─┴┘ └──┴─┴┘
│
│
│ ┌──┬─┬┐ ┌──┬─┬┐
└ c ─→│2.5 │10│┼─→ │8.5 │ 8│┼─→
NULL
└──┴─┴┘ └──┴─┴┘
（p→exp
＜ q→exp ）
p─┐
┌ ┌──┬─┬┐└→┌──┬─┬┐ ┌──┬─┬┐
│ │2.5 │10│┼─→│ 12 │6 │┼─→│
1 │3 │┼─→ NULL
│ a ─→└──┴─┴┘ └──┴─┴┘ └──┴─┴┘
│
│
q─┐
│ ┌──┬─┬┐└→┌──┬─┬┐ ┌──┬─┬┐
⑶┤ │8.5 │ 8│┼─→│ 10 │6 │┼─→│5.5 │0
│┼─→ NULL
│ b ─→└──┴─┴┘ └──┴─┴┘ └──┴─┴┘
│
│
│ ┌──┬─┬┐ ┌──┬─┬┐ ┌──┬─┬┐
└ c ─→│2.5 │10│┼─→│8.5 │ 8│┼─→│
22 │ 6│┼─→ NULL
└──┴─┴┘ └──┴─┴┘ └──┴─┴┘
（
p→exp == q→exp ）
兩多項是相加之過程中，每當有一新節點產生，都是附加在串列c之後端，因此
如果有一指標變數隨時指到c之最後一個串列節點因將可省事不少；因此不妨一
開始就讓c與tail同時指到一空節點，然後每附加一節點至串列c，就讓tail指到該
節點（即tail永遠指到c之最後節點），最後在將前端之空節點刪掉即可。
typedef struct listnode *NODE;
struct listnode ｛
float info;
NODE next;
｝
NODE polyadd(a, b)
NODE a, b;
｛
NODE p, q, tail, c, ptr;
p = a;
q = b;
tail = c = (NODE)
malloc(sizeof(struct listnode));
while (p != NULL &&
q!=NULL) ｛
ptr
= (NODE)malloc(sizeof(struct listnode));
if (p->exp > q->exp) ｛
ptr->coef = p->coef;
ptr->exp = p->exp;
p =
p->next;
｝
else if (p->exp < q->exp) ｛
ptr->coef = q->coef;
ptr->exp = q->exp;
q = q->next;
｝
else ｛
ptr->coef = p->coef + q->coef;
ptr->exp = p->exp;
p = p->next;
q = q->next;
｝
tail->next = ptr;
tail = ptr;
｝
if (p !=NULL || q!=NULL) ｛
if (p == NULL)
p = q;
while (p
!=NULL) ｛
ptr = (NODE)
malloc(sizeof(struct listnode));
ptr->coef
= p->coef;
ptr->exp = p->exp;
p =
p->next;
tail->next = ptr;
tail = ptr;
｝
｝
tail->next = NULL;
ptr = c;
c = c->next;
free(ptr);
retrun(c);
｝
再談鏈結串列
鏈結串列在實際應用方面，有一些特別的運算，我們一一介紹。
一、清除一個鏈結串列：
例如提及之兩多項式相加，在求出一組答案之後，如接著再處理另一組多項式
相加，最好將已不用之鏈結串列節點歸還給電腦系統，才能利用這些節點空間
；erase()即為清除並歸還串列節點之副程式：
NODE erase(list)
NODE list;
NODE p;
p = (NODE)malloc(sizeof(struct
listnode));
while (list != NULL) ｛
p = list;
list =
list->next;
free(p);
｝
｝
二、將串列反轉：
我們只要利用三個指標變數，就可以輕易的將一鏈結串列反轉，而不須用及任
何其他節點或串列的幫忙，invert() 即為將串列反轉之副程式：
NODE invert(list)
NODE list;
NODE p, q, r;
p = (NODE)malloc(sizeof(struct
listnode));
q = (NODE)malloc(sizeof(struct
listnode));
r = (NODE)malloc(sizeof(struct
listnode));
p = list;
while (p != NULL) ｛
r = q;
q = p;
p = p->next;
q->next = r;
｝
return(q);
｝
三、將兩串列鏈結成一串列：
NODE concatenate(x, y)
NODE x, y;
｛
NODE p, z;
p =
(NODE)malloc(sizeof(struct listnode));
z =
(NODE)malloc(sizeof(struct listnode));
if (x == NULL)
z = y;
else｛
z = x;
if (y != NULL)｛
p = x;
while (p->next != NULL)
p = p->next;
p->next = y;
｝
｝
return(z);
｝
concatenate()
將串列 x 與 y，鏈結成串列 z，其程序為：
1.若 x 為空串列，則串列 y 即成為串列 z。
2.若 x 為非空串列，則 z 指到 x 之第一個節點；然後再測試 y 是否為空串
列，若是，則結束；若不是，則再尋找 x之最後節點，將其鏈結至 y 之第一
個節點。因此，在執行完程式之後，新串列 z 之前半部為 x，後半部為 y。
首節點
鏈結串列在實際應用方面，有時須在串列首附加一額外節點，以協助串列處理
，這種節點並不屬於串列中的項目，稱為首節點 (Head node)或串列首(List head)。例如，在建立一鏈結串列時，開始時就用了一個空白的首節點，等建立好一串
列後，在將首節點刪除。
首節點之其他用途，例如圖 2（a），首節點之斜線部份（資料欄）可用來儲存
與該串列有關之訊息；例如圖 2（b），首節點資料欄儲存串列節點數目（不含
首節點），如此一來，只要在串列刪掉或插入一節點時，隨時更改首節點之數
目，即可知到整個串列之節點數。
┌──┬┐ ┌──┬┐ ┌──┬┐
list ─→│╱╱│┼─→│ 7 │┼─→│ 10 │┼─→ NULL
└──┴┘ └──┴┘ └──┴┘
（a）斜線部份可存有關串列之各種訊息
┌──┬┐ ┌──┬┐ ┌──┬┐ ┌──┬┐
list ─→│ 3 │┼─→│ 55 │┼─→│ 50 │┼─→│ 30 │┼─→ NULL
└──┴┘ └──┴┘ └──┴┘ └──┴┘
（b）3為串列list之節點數
┌──┬┐
list ─→│ │┼─→ NULL
└──┴┘
（c）只有首節點之空串列
┌──┬┐ ┌──┬┐ ┌──┬┐ ┌──┬┐
list ─→│ │┼─→│ 55 │┼─→│ 50 │┼─→│ 30 │┼─→ NULL
└┼─┴┘ └──┴┘ └──┴┘ └──┴┘
│
↑
└────────────────────┘
（d）首節點之兩欄均為指標形態
圖 2 含首節點之串列
圖 2（c）代表一空串列（因為首節點並非串列之項目）；圖 2（d）實為一鏈結
佇列結構，其首節點之兩欄均為指標形態；由此可知，首節點與其後串列節點
，並不須有相同的資料形態；換言之，首節點也可宣告成獨立變數，與串列節
點分開，例如：
typedef struct queue *QUEUE ;
struct queue {
int info ;
QUEUE next ;
}
typedef struct quehead QUEHEAD ;
struct quehead {
QUEUE front, rear ;
}
QUEHEAD head ;
QUEUE p, q ;
上述變數 head, p,與 q 其實均為指標形態變數，因為 head 之兩欄
head.front 與 head.rear
與 p, q之形態同為 QUEUE，他們之關係可用下圖表示：
p
q
┌─┐ ↓ ↓
│ │ ┌─┬┐ ┌─┬┐
head.front │ ┼──→│5 │┼──→ │10│┼──→ NULL
│ │ └─┴┘ └─┴┘
├─┤
↑
│ │
│
head.rear │
┼────────────┘
│ │
└─┘
上圖可以下列程式片段來達成：
p = (QUEUE) malloc
(sizeof (sruct queue)) ;
head = (QUEHEAD)
malloc (sizeof (QUEHEAD)) ;
head.front = p ;
p -> info = 5 ;
q = (QUEUE) malloc
(sizeof (sruct queue)) ;
q -> info = 10;
q -> next =
NULL ;
p -> next = q ;
head.rear = q ;
以首節點之觀念製作串列，有利於刪除串列第一個節點，或在串列前端加入一
新節點，是一種常用的軟體技巧。