（一）C程序設(shè)計(jì)語(yǔ)言與實(shí)現(xiàn)

指針是C語(yǔ)言的精華部分，它極大地豐富了C語(yǔ)言的功能。通過(guò)利用指針，可以描述復(fù)雜的數(shù)據(jù)機(jī)構(gòu)，在編程時(shí)能很好地利用內(nèi)存資源，使其發(fā)揮最大的效率。

1. 指針類型

（1）變量和指針

變量： 是內(nèi)存單元的抽象。變量具有類型、值、地址、作用域和生存期等屬性。

變量的本質(zhì)是程序中用來(lái)存放數(shù)據(jù)的一段存儲(chǔ)空間。一般情況下，變量所對(duì)應(yīng)的存儲(chǔ)空間在內(nèi)存區(qū)域，在C語(yǔ)言中程序員可以通過(guò)關(guān)鍵字register聲明變量的存儲(chǔ)單元是CPU中的寄存器。

變量的數(shù)據(jù)類型不同，它所占的內(nèi)存單元數(shù)也不同。

在訪問(wèn)變量時(shí)，首先應(yīng)找到其在內(nèi)存的地址。如果在程序中將變量的地址保持在另一個(gè)變量中，則形成指針變量，通過(guò)指針對(duì)所指向變量的訪問(wèn)是一種對(duì)變量的“間接訪問(wèn)”。

例如：

定義了兩個(gè)變量：
整形變量 a 和指針變量 ptr ，
在存取變量 a 中的數(shù)據(jù)時(shí)，
可通過(guò)變量 a 或指向變量 a 的指針來(lái)進(jìn)行，
分別稱為直接訪問(wèn)和間接訪問(wèn)。
//a是整形變量，其值為整數(shù)
int a;
/*
ptr是指針變量，
其值為一個(gè)整型變量的地址
*/
int *ptr;

（1）直接訪問(wèn)變量 a 中的數(shù)據(jù)
a = 5;
a + 10;
（2）簡(jiǎn)介訪問(wèn)變量 a 中的數(shù)據(jù)
/*
將變量 a 的地址賦值給指針變量 ptr ，
稱 ptr 指向變量 a
*/
ptr = &a;
/*
指針變量 ptr 指向的對(duì)象用 *ptr 表示
等價(jià)于 a=5; ，
通過(guò)指針變量 ptr 訪問(wèn)變量 a
*/
*ptr = 5;

經(jīng)過(guò)上述定義和處理后，變量a和指針變量ptr之間的關(guān)系如下圖所示：

指針變量ptr與指針變量指向的對(duì)象*ptr(a)

（2）通過(guò)指針訪問(wèn)數(shù)組中的元素

C程序中常利用指針對(duì)數(shù)組和字符串進(jìn)行處理。

一個(gè)數(shù)組由連續(xù)的一塊內(nèi)存單元組成，數(shù)組名就是這塊連續(xù)內(nèi)存單元的首地址（起始地址）。一個(gè)數(shù)組是由各個(gè)數(shù)組元素組成的，每個(gè)數(shù)組元素按其類型不同占有若干個(gè)連續(xù)的內(nèi)存單元。

1）指針變量與一維數(shù)組

指針變量指向一維數(shù)組的方法如下所示：

定義一個(gè)整型數(shù)組 st 
和指向數(shù)組元素的指針 ptr。
//定義包含10個(gè)整型數(shù)據(jù)的數(shù)組
int st[10];
/*
定義 ptr 為指向整型變量 st[0] 的指針，
等價(jià)于 int *ptr = st
*/
int *ptr = &st[0];

若ptr指向數(shù)組的第一個(gè)元素（即下標(biāo)為0的元素），則*(p+i)指向數(shù)組的第i+1個(gè)元素（即下標(biāo)為i的元素）。

2）指針變量與二維數(shù)組

指針變量指向二維數(shù)組的情形比較復(fù)雜，舉例說(shuō)明：
定義int a[3][4]，其元素布局如下圖所示：

二維數(shù)組a[3][4]元素布局

數(shù)組a[3][4]可看作是由3個(gè)一維數(shù)組（a[0]、a[1]、a[2]）構(gòu)成的一維數(shù)組，每個(gè)一維數(shù)組的元素是4個(gè)。a是二維數(shù)組名，它代表整個(gè)二維數(shù)組的首地址。

a[0]是第0個(gè)一維數(shù)組的數(shù)組名和首地址。*(a+0)、*a和a[0]是等效的，它們都表示一維數(shù)組a[0]的0號(hào)元素的首地址。&a[0][0]表示a的第0行和第0列元素的首地址。因此，a、a[0]、*(a+0)、*(a+1)和&a[0][0]所表示的內(nèi)容相同。

對(duì)于二維數(shù)組a[m][n]、a+i、a[i]、*(a+i)和&a[i][0]是相同的。

（3）指針與函數(shù)

C程序中將指針與函數(shù)結(jié)合使用的常見(jiàn)方式有函數(shù)參數(shù)為指針、函數(shù)返回值為指針及通過(guò)函數(shù)指針變量調(diào)用函數(shù)（函數(shù)指針變量）。

1）函數(shù)參數(shù)為指針

參數(shù)使用指針類型的作用是將一個(gè)變量的地址傳送到另一個(gè)函數(shù)中。

C語(yǔ)言中實(shí)參向形參傳值，反之則不行。

例如：

定義函數(shù) swap(a,b)的功能是
交換 a 和 b 的值，代碼如下：
void swap(int a,int b){
  int temp;
  temp = a;
  a = b;
  b = temp;
}

如果發(fā)生函數(shù)調(diào)用swap(x,y)，則系統(tǒng)將x的值傳給a、y的值傳給b，在函數(shù)中實(shí)現(xiàn)了a和b的值的交換，但是x和y的值并沒(méi)有發(fā)生交換。

為實(shí)現(xiàn)將函數(shù)中對(duì)形參的修改結(jié)果返回給調(diào)用函數(shù)，可使用指針參數(shù)。

對(duì)上個(gè)例子進(jìn)行修改，代碼如下：

void swap_1(int *a,int *b){
  int temp;
  temp = *a;
  *a = *b;
  *b = temp;
}

當(dāng)形參為指針類型時(shí)，傳遞給形參的應(yīng)該是地址信息，因此調(diào)用swap_1的形式為swap_1(&x,&y)。這樣通過(guò)“間接訪問(wèn)”，實(shí)現(xiàn)了在被調(diào)用函數(shù)中修改實(shí)參所對(duì)應(yīng)的變量。

2）函數(shù)返回值為指針

函數(shù)類型是指函數(shù)返回值的類型。返回指針的函數(shù)稱為指針型函數(shù)。需要注意的是，不能返回局部數(shù)據(jù)的指針。

例如下面的函數(shù)，函數(shù)get_str雖然返回了局部數(shù)組str的首地址，但調(diào)用get_str的其他函數(shù)并不能通過(guò)此地址訪問(wèn)字符串testing local pointer。

char* get_str(void){
  char str[] = {"testing local pointer"};
  return str;
}

int main(){
  char *p;
  int i;
  p = get_str();
  for(i = 0; *(p+i); i++)
    putchar(*(p+i));
  return 0;
}

將函數(shù)get_str中的char str[] = {"testing local pointer"};改成char *str = {"testing local pointer"};即可。

3）指針變量

程序中的一個(gè)函數(shù)總是占用一段連續(xù)的內(nèi)存區(qū)，而函數(shù)名就是該函數(shù)所占內(nèi)存區(qū)的首地址?？梢园押瘮?shù)的首地址（或稱入口地址）賦給一個(gè)指針變量，使指針變量指向該函數(shù)，然后通過(guò)指針變量就可以找到并調(diào)用這個(gè)函數(shù)。

指針函數(shù)的指針變量稱為“函數(shù)指針變量”。

函數(shù)指針變量定義的一般形式為：

類型說(shuō)明符 (*指針變量名)();

其中，“類型說(shuō)明符”表示被指明函數(shù)的返回值的類型；“(*指針變量名)”表示*后面的變量是指針變量；最后的一對(duì)空括號(hào)表示指針變量所指向的對(duì)象是一個(gè)函數(shù)。

例如，下面定義了一個(gè)函數(shù)指針變量funptr。

int (*funptr)();

2. 指針與數(shù)據(jù)結(jié)構(gòu)

隨著軟件開(kāi)發(fā)環(huán)境的不斷完善和程序語(yǔ)言的抽象程度不斷提高，數(shù)據(jù)結(jié)構(gòu)的內(nèi)部設(shè)計(jì)細(xì)節(jié)被封裝和屏蔽起來(lái)，在很多應(yīng)用軟件的開(kāi)發(fā)中沒(méi)有必要也不再涉及底層細(xì)節(jié)，但是在系統(tǒng)級(jí)程序設(shè)計(jì)或嵌入式應(yīng)用的軟件設(shè)計(jì)中，指針及相關(guān)機(jī)制的應(yīng)用仍然是十分必要的。

（二）算法設(shè)計(jì)與實(shí)現(xiàn)

1. 算法設(shè)計(jì)過(guò)程

1. 理解問(wèn)題
2. 確定相關(guān)因素
   預(yù)測(cè)所有可能的輸入，在精確解和近似解之間做選擇，確定適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，確定算法設(shè)計(jì)技術(shù)。
3. 設(shè)計(jì)算法
4. 證明算法的正確性
5. 分析算法的效率
6. 根據(jù)算法編寫代碼

2. 算法問(wèn)題類型

• 查找問(wèn)題
• 排序問(wèn)題
• 圖問(wèn)題
• 組合問(wèn)題
• 幾何問(wèn)題