http://jpkc.nwu.edu.cn/jsjjc/ebooks/p14.htm章 指針與動態(tài)空間分配
指針極大地豐富了C語言的功能。學習指針是學習C語言最重要的一環(huán)，正確地理解指針與多維數(shù)組的關系、指針數(shù)組的概念、函數(shù)指針以及多級指針的概念，將有助于編寫高效的程序。另一方面，通過指針可以構(gòu)建鏈表，鏈表的引入解決了通過數(shù)組獲取連續(xù)空間的某些限制。通過鏈表可以解決一些比較復雜的問題。
指針與多維數(shù)組
前面介紹的數(shù)組只有一個下標，稱為一維數(shù)組，其數(shù)組元素也稱為單下標變量。在實際問題中，有很多量是二維的或多維的，因此C語言允許構(gòu)造多維數(shù)組。多維數(shù)組元素通過多個下標來標識它在數(shù)組中的位置，所以也稱為多下標變量。
本節(jié)只介紹二維數(shù)組，多維數(shù)組可由二維數(shù)組類推而得到。
指針與二維數(shù)組
1．二維數(shù)組的線性存儲
通過指針引用二維數(shù)組元素要比引用一維數(shù)組元素復雜一些，為了便于大家理解，首先介紹二維數(shù)組在線性空間的存儲。設有
int a[3][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12}};
定義了一個二維數(shù)組a，共有12個元素。從邏輯上可以把該二維數(shù)組a看成一張由3行4列元素組成的二維表格。
盡管一個二維數(shù)組像一個表格，但在C語言中，計算機以行為主序（即一行接一行）把數(shù)組存放在一維線性內(nèi)存空間中，如圖14.1所示。從圖中可以看出，它同一維數(shù)組的存放形式一樣，但二者引用數(shù)組元素地址的計算方法有所區(qū)別。
圖14.1 數(shù)組與存儲空間
2．理解二維數(shù)組
（1）C語言將二維數(shù)組理解為其構(gòu)成元素是一維數(shù)組的一維數(shù)組。C語言將二維數(shù)組定義時的行、列下標分別用兩個[]括號分開。例如，數(shù)組a[3][4]，把數(shù)組的每一行看做一個整體時，二維數(shù)組a中有3個元素：a[0]、a[1]、a[2]。而每個元素a[i]（行數(shù)組）又由4個數(shù)據(jù)元素a[i][0]、a[i][1]、a[i][2]、a[i][3] 組成。如圖14.1所示。
（2）表達式a+i（行指針）。對于二維數(shù)組，數(shù)組名a是一個“指向行的指針”，它指向數(shù)組第0行。而且它仍然是數(shù)組的首地址，即第0個元素的地址。由于a是指向行的指針，表達式a+i中的偏移量i是以“行”為單位的，所以a+i就是第i行的地址。
因此，有如下等價關系：
l a等價于&a[0]
l a+i等價于&a[i]
也就是說，a+i表示指向二維數(shù)組a中第i行的地址（指針）。
如下等價關系也成立。
*(a+i)等價于a[i]等價于&a[i][0]
特別注意：“*(a+i)”中的“*”已不再是取(a+i)地址中的內(nèi)容，而是表示數(shù)組a中的第i行的首地址。即也可以把a+i看做行指針，而把*(a+i)看做列指針。
（3）二維數(shù)組元素的地址。因為表達式a[i]和*(a+i)表示第i行的首地址，因而表達式*(a+i)+j就是第i行第j個元素的地址，即數(shù)組a中a[i][j]元素的地址。所以有如下等價關系。
*(a+i)+j等價于a[i]+j等價于&a[i][j]
它們都表示數(shù)組a中元素a[i][j]的地址。
如果在上述表達式前面再用一個“*”，即*(*(a+i)+j)、*(a[i]+j)、*&a[i][j]，則它們都表示數(shù)組a的元素a[i][j]。
實際上，當用戶程序中用a[i][j]格式來引用該元素時，C語言對a[i][j]的地址&a[i][j]計算過程是：先將其轉(zhuǎn)換為*(a[i]+j)，再將其中的a[i]轉(zhuǎn)換為*(a+i)，最后得到*(*(a+i)+j)。系統(tǒng)最終是通過轉(zhuǎn)換后的式子*(*(a+i)+j)來計算地址并引用數(shù)組元素的。
注意：在一維數(shù)組和二維數(shù)組中，a+i和*(a+i)的含義不同。在一維數(shù)組中，a+i表示數(shù)組a的第i個元素地址，而*(a+i)為數(shù)組a中第i個元素的值；在二維數(shù)組中，a+i和*(a+i)都表示地址，其中a+i表示數(shù)組a的第i行首地址，而*(a+i)表示a數(shù)組中第i行第0列元素的地址。
（4）二維數(shù)組中元素偏移量計算。C語言對二維數(shù)組元素地址的處理方法是，先計算行地址，再計算列地址。對于二維數(shù)組a[n][m]中的任意一個元素a[i][j]，相對于a[0][0]的偏移量計算公式為：i*m+j。其中m為該二維數(shù)組的列數(shù)。從此公式可以看出，二維數(shù)組中第1個下標i（行下標）加1表示指針跳過一行（即跳過m個元素），第2個下標j（列下標）加1表示指針向后移動一個元素。
【例14.1】 用數(shù)組元素的偏移量訪問數(shù)組。
main()
{
int a[3][4]={{1,2,3,4},{2,3,4,5},{3,4,5,6}};
int i,j;
for(i=0; i<3; i++)
{ for(j=0; j<4; j++)
printf("a[%d][%d]=%-5d",i,j,*(a[0]+i*4+j) );
printf("\n");
}
}
運行結(jié)果為：
a[0][0]=1 a[0][1]=2 a[0][2]=3 a[0][3]=4
a[1][0]=2 a[1][1]=3 a[1][2]=4 a[1][3]=5
a[2][0]=3 a[2][1]=4 a[2][2]=5 a[2][3]=6
在該程序中，表達式a[0]+i*4+j表示第i行第j列元素的地址，因此 *(a[0]+i*4+j)就是元素a[i][j]。
注意：不能寫成*(a+i*4+j)。因為a所指對象是行，a+i*4+j表示從a開始跳過i*4+j行所得到的地址。而a[0]（即*(a+0)）所指的對象為元素，所以a[0]+i*4+j表示從a[0]開始跳過i*4+j個元素所得到的地址（即a[i][j]的地址）。
通過指針訪問二維數(shù)組
由于二維數(shù)組在計算機中的存放形式是順序存放的，所以只要定義一個與數(shù)組元素類型相一致的指針變量，再將數(shù)組中某個元素的地址賦給這個指針變量，通過對該指針的移動和引用，就可以訪問到數(shù)組中的每一個元素。
【例14.2】 用指針變量輸出二維數(shù)組的元素。
[方法一]：
main()
{
int i,a[2][3]={1,2,3,4,5,6};
int *p;
for(p=&a[0][0],i=0;i<6; i++)
{
if(i%3==0)
printf("\n");
printf("%3d", *p++);
}
}
圖14.2 指針變量p訪問a數(shù)組的元素示意圖
程序中，利用數(shù)組元素在內(nèi)存中存放的連續(xù)性，將二維數(shù)組看做是一個以a[0]為數(shù)組名的由6個元素組成的一維數(shù)組。該方法通過改變指針變量p的值（即p++），實現(xiàn)按順序?qū)?shù)組元素進行訪問（如圖14.2所示）。
但應注意此時的指針變量p。如果還要用該指針變量p訪問a數(shù)組中的元素，則應先重新給指針變量p賦數(shù)組a地址值，然后才能通過p引用數(shù)組a中的元素。
[方法二]：
main()
{
int a[2][3]={1,2,3,4,5,6};
int *p,i,j;
for(p=&a[0][0],i=0;i<2;i++)
{
printf("\n");
for(j=0;j<3;j++)
printf("%3d", *(p+i*3+j));
}
}
在程序中，通過計算元素地址的偏移量實現(xiàn)對數(shù)組元素進行訪問，輸出了二維數(shù)組中的每一個元素的值。p所指的對象為元素，所以p+i*3+j為a[i][j]的地址。
[方法三]：
main()
{
int a[2][3]={1,2,3,4,5,6};
int i,j;
for(i=0;i<2;i++)
{
printf("\n");
for(j=0;j<3;j++)
printf("%3d", *(*(a+i)+j));
}
}
在程序中，還是通過計算元素地址的偏移量實現(xiàn)對數(shù)組元素的訪問，輸出了二維數(shù)組中每一個元素的值。
三個程序的運行結(jié)果相同，都為
1 2 3
4 5 6
可以發(fā)現(xiàn)，雖然方法二和方法三都是通過計算元素地址的偏移量實現(xiàn)對數(shù)組元素的訪問，可是兩者的使用方法卻不同：一個是*(p+i*3+j)，另一個是*(*(a+i)+j。無法實現(xiàn)指針使用格式的統(tǒng)一，原因主要在于指針p所指向的對象是一個整型元素，而指針a所指向的對象卻是一個一維數(shù)組。
為了實現(xiàn)指針使用格式的統(tǒng)一，需要定義一種指向?qū)ο笫且痪S數(shù)組的指針變量。
指向一維數(shù)組的指針變量
這是一種指向?qū)ο笫且痪S數(shù)組的指針變量，可以用它指向一個二維數(shù)組的某一行，然后進一步通過它再訪問數(shù)組中的元素。
指針定義形式如下：
例如：
int (*p)[4]； /*表示變量p是指向有4個元素的一維整型數(shù)組的指針變量*/
char (*q)[20]； /*表示變量q是指向有20個元素的一維字符數(shù)組的指針變量*/
【例14.3】 輸出二維數(shù)組任一元素的值。
main()
{
int a[2][6]={0,1,2,3,4,5,6,7,8,9,10,11};
int (*p)[6],i,j;
p=a;
scanf("%d,%d",&i,&j);
printf("\na[%d][%d]=%d\n",i,j,*(*(p+i)+j));
}
若輸入：1,2
則輸出為：a[1][2]=8
在該程序中，p是指向二維數(shù)組a第0行的指針變量，p+i是指向第i行的指針。即p的變化是以“行”為單位的。這與前面介紹二維數(shù)組的行指針a+i一樣。但它與二維數(shù)組名的區(qū)別是：p是指針變量，而數(shù)組名是指針常量。
該程序也可寫為
main()
{
int a[2][6]={0,1,2,3,4,5,6,7,8,9,10,11};
int (*p)[6],i,j;
p=a;
scanf("%d,%d",&i,&j);
printf("\na[%d][%d]=%d\n",i,j,p[i][j]));
}
上述程序?qū)崿F(xiàn)了指針變量p和二維數(shù)組a使用格式的統(tǒng)一。也就是說，如果p是指向二維數(shù)組a中第i行的指針變量，則*p與a[i]等價。
特別注意：由于p是指向由m個整數(shù)組成的一維數(shù)組的指針變量，因而p和*p的值相同（因為第i行的地址和元素a[i][0]的地址相等），但含義卻不同，即p指向行的方向，而*p指向列的方向。
【例14.4】 分析下面的程序。
main()
{
int b[2][3]={{1,2,3},{4,5,6}};
int (*p)[3];
p=b;
printf("p=%d, ",p);
printf("*p=%d, ",*p);
printf("**p=%d",**p);
}
運行結(jié)果為：
p=-54，*p=-54，**p=1
從運行結(jié)果可以看出，p和*p都是指針， p指向第0行，而*p指向數(shù)組b的第0行第0列元素，即b[0][0]，二者的起始地址相同，所以其值都等于b[0][0]的地址，而**p代表b數(shù)組b[0][0]元素。
如果有如下定義：
int (*p)[4], a[3][4];
p=a;
則有如表14.1所示的表達式的等價關系成立。
表14.1
等 價 關 系
含 義
p+i 等價 a+i 等價 &a[i]
數(shù)組a中第i行的地址
*p 等價 a[0] 等價 &a[0][0]
數(shù)組a中第0行的首地址
*(p+i) 等價 a[i] 等價 &a[i][0]
數(shù)組a中第i行的首地址
*(p+i)+j 等價 &a[i][j]
第i行第j列元素的地址
*p+i 等價 &a[0][i]
第0行第i列元素的地址
假設有如下定義：
int a[3][4] ,*p, (*pa)[4];
p = a[0]; pa = a;
注意區(qū)分下列表達式的含義。
① a、*a、**a、a[2]、a+2、*a+2；
② p、p++、p+2、*(p+2)、*p+2、p+1*4+2、*(p+2*4)；
③ pa、pa++、pa+2、*pa、*pa+2、*(pa+2)、*(*pa+2)、*(*(pa+1)+2)。
說明：在二維數(shù)組中，由數(shù)組名、指向元素的指針變量和指向行的指針變量所組成的表達式只有三種含義。
l 指向行的指針，如上例中的a、a+2、pa、pa++、pa+2。
l 指向元素的指針，即元素的地址，如上例中的*a、a[2]、*a+2、p、p+1*4+2等。
l 數(shù)組的元素，如上例中的**a、*(p+2)、*(p+2*4)、*(*pa+2)、*(*(pa+1)+2)。
通過指針變量存取數(shù)組元素速度快且程序簡明。用指針變量作形參，可以允許數(shù)組的行數(shù)不同。因此數(shù)組與指針聯(lián)系緊密。
指針數(shù)組與指針的指針
指針數(shù)組
可以將多個指向同一數(shù)據(jù)類型的指針存儲在一個數(shù)組中，用來存儲指針型數(shù)據(jù)的數(shù)組就稱為指針數(shù)組。指針數(shù)組中每個元素都是指向同一數(shù)據(jù)類型的指針。
指針數(shù)組的定義形式如下：
類型標識符 *數(shù)組名[整型常量表達式]；
例如：
char *strings[10];
int *a[20];
其中，“char *strings[10];”語句定義了一個有10個元素的一維數(shù)組strings，它的每一個元素為指向char型的指針變量，即可以給每一個元素賦一個字符型數(shù)據(jù)對象的地址。而語句“int*a[20];”定義了一個有20個元素的數(shù)組a，它的每一個元素為指向int型的指針變量。
在使用指針數(shù)組時，要注意數(shù)組元素的值和數(shù)組元素所指向的值。例如：
int *p[4], *pa, a=12, b=20;
pa=&a;
p[0]=pa;
p[1]=&b;
數(shù)組p的元素p[0]的值為整型變量a的地址，元素p[1]的值為變量b的地址（如圖14.3所示）。
【例14.5】 用指針數(shù)組輸出n個字符串。
#include "stdio.h"
main()
{ char *ps[4]={"Unix","Linux","Windows","Dos"};
int i;
for(i=0;i<4;i++) puts(ps[i]);
}
運行結(jié)果為
Unix
Linux
Windows
Dos
程序中，指針數(shù)組ps的元素分別指向4個字符串的首地址，如圖14.4所示。
指針數(shù)組非常有用，因為這種數(shù)組中每一個元素實際上都是指向另一個數(shù)據(jù)的指針。因此，可以通過將不同長度的字符串首地址分別放入指針數(shù)組的每一個元素中，從而實現(xiàn)對這些字符串的處理。
圖14.3 數(shù)組元素的值和數(shù)組元素所指向的值 圖14.4 ps的指向示意圖
例如，對于圖書名的管理就可以使用此方法。把書名作為一個字符串，然后將其首地址放入指針數(shù)組的某元素中。這樣，通過指針數(shù)組就可以對圖書進行管理（如圖14.5所示）。
圖14.5
它的優(yōu)點在于可以根據(jù)書名的實際大小分配存儲空間，從而避免采用字符數(shù)組浪費空間的問題。假設定義字符數(shù)組char c[5][128]存放書名，則該字符數(shù)組可以放5本書，每本書名最長可為127個字符，當書名的長度小于127個字符時，就會浪費大量空間。
【例14.6】 將一批順序給定的字符串按反序輸出。
main()
{
int i;
char *name[ ]={"Unix","Linux","Windows","C language","Internet"}；
for(i=4；i>=0；i--)
printf("%s\n",name[i])；
}
運行結(jié)果為：
Internet
C language
Windows
Linux
Unix
指向指針的指針
指針數(shù)組的數(shù)組名是一個指針常量，它所指向的目標是指針型數(shù)據(jù)。也就是說，其目標又是指向其他基本類型數(shù)據(jù)的指針，所以指針數(shù)組名是指向指針類型數(shù)據(jù)的指針，故稱它為指針的指針。
圖14.6 變量p與
pp示例圖
指針數(shù)組名是指針常量，它是在定義指針數(shù)組時產(chǎn)生的。那么如何定義指向指針類型的指針變量呢？和一般的變量一樣，對于一個指針變量，系統(tǒng)也為其在內(nèi)存中分配相應的內(nèi)存空間。因此，可以用一個特殊類型的指針指向一個指針變量（或指針數(shù)組中的元素）。這個特殊類型的指針就是指向指針類型的指針變量。
定義形式如下：
類型符 **變量名；
例如：
float **pp;
表示定義指向指針類型的指針變量pp，它所指向的對象是“float *”類型（即指向?qū)嵭蛿?shù)的指針變量）。
例如，有如下程序段：
float a=3.14;
float *p;
float **pp; /* pp是指向float *類型數(shù)據(jù)的指針 */
p=&a;
pp=&p; /* 將p的地址賦給pp */
其變量在內(nèi)存中的分配情況如圖14.6所示。
【例14.7】 用指向指針類型的指針變量輸出一個變量。
main()
{
int a=15,**p;
int *pp=&a;
p=&pp;
printf("%d\n",**p);
}
該程序定義了一個指向指針類型的指針變量p，它所指向的對象是“int *”型（即指向int型的指針變量）。同時還定義了一個int型的指針變量pp，并將變量a的地址賦給它，然后再將指針變量pp的地址賦值給p變量。變量關系如圖14.7所示。
圖14.7
因此，指針p的目標變量是*p（即pp）；而pp的目標變量是*pp（即a）。對于表達式**p，它可以變?yōu)?(*p)形式，而*p就是pp，故**p即為*pp。所以，可以直接用**p的形式引用變量a。而不能使用*p形式。
在下面程序中，首先定義指針數(shù)組ps并為其初始化賦值。接著又定義了一個指向指針的指針變量pps。在5次循環(huán)中， pps 分別取得了ps[0]、ps[1]、ps[2]、ps[3]、ps[4]的地址值。通過這些地址即可找到對應的字符串。
main()
{
char *ps[]={ "BASIC","DBASE","C","FORTRAN","PASCAL"};
char **pps;
int i;
for(i=0;i<5;i++)
{
pps=ps+i;
printf("%s\n",*pps);
}
}
【例14.8】 用指向指針的指針變量將一批順序給定的字符串按反序輸出。
main()
{
int i;
char *name[ ]={"Unix","Linux","Windows","C language","Internet"}；
char **p； /*定義指針變量p，用來指向“char *”類型的指針*/
for(i=4；i>=0；i--)
{ p=name+i； /*由于name+i等價&name[i]，所以p指向name[i] */
printf("%s\n",*p)；
}
}
運行結(jié)果為
Internet
C language
Windows
Linux
Unix
注意：該程序是用指向指針的指針變量來訪問字符串，所以在“printf("%s\n",*p)；”語句中使用了*p形式。請注意其與**p的區(qū)別。**p表示一個具體的字符對象， p存放的是name數(shù)組元素的地址，而*p是目標對象的地址。如圖14.8所示。
圖14.8 p、*p和**p的區(qū)別
當需要通過函數(shù)參數(shù)返回指針型的數(shù)據(jù)時，需要傳入該指針型數(shù)據(jù)的地址，實際上就是指針的指針，而在函數(shù)中要將返回的結(jié)果存入該指針所指向的目標，這是對指針的指針類型數(shù)據(jù)的一個典型應用。
另外，指針的指針類型數(shù)據(jù)也常用于處理字符串集合，處理時需要將每一個字符串的首地址存儲在指針數(shù)組中的每個元素中，然后通過這個指針數(shù)組就可以訪問到所有的字符串。下面通過一個例子來說明這一方面的應用。
【例14.9】 輸入5個國名，并按字母順序排列后輸出。
分析 在以前的例子中采用了普通的排序方法，逐個比較之后交換字符串的位置。而交換字符串的物理位置是通過字符串復制函數(shù)完成的，反復的交換將使程序執(zhí)行的速度很慢，同時由于各字符串（國名）的長度不同，又增加了存儲管理的負擔。
用指針數(shù)組能很好地解決這些問題。把所有的字符串存放在一個數(shù)組中，把這些字符數(shù)組的首地址存放在一個指針數(shù)組中，當需要交換兩個字符串時，只需交換指針數(shù)組相應兩元素的內(nèi)容（地址）即可，而不必交換字符串本身。
#include "string.h"
main()
{
void sort(char *name[],int n);
void print(char *name[],int n);
char *name[]={ "CHINA","AMERICA","AUSTRALIA","FRANCE","GERMAN"};
int n=5;
sort(name,n);
print(name,n);
}
void sort(char *name[],int n)
{
char *pt;
int i,j,k;
for(i=0;i<n-1;i++)
{
k=i;
for(j=i+1;j<n;j++)
if(strcmp(name[k],name[j])>0) k=j;
if(k!=i)
{
pt=name[i];name[i]=name[k];name[k]=pt;
}
}
}
void print(char *name[],int n)
{
int i;
for (i=0;i<n;i++) printf("%s\n",name[i]);
}
程序中定義了兩個函數(shù)，一個名為sort()完成排序，其形參為指針數(shù)組name，即為待排序的各字符串數(shù)組的指針。形參n為字符串的個數(shù)。在sort()函數(shù)中，對兩個字符串比較，采用了strcmp()函數(shù)，strcmp()函數(shù)允許參與比較的字符串以指針方式出現(xiàn)。name[k]和name[j]均為指針，因此是合法的。另一個函數(shù)為print()，用于排序后字符串的輸出，其形參與sort()的形參相同。
主函數(shù)main()中，定義了指針數(shù)組name并為其做了初始化賦值。然后分別調(diào)用sort()函數(shù)、print()函數(shù)完成排序和輸出。
字符串比較后需要交換時，只交換指針數(shù)組元素的值，而不交換具體的字符串，這樣將大大減少時間的開銷，提高了運行效率。
函數(shù)指針
函數(shù)指針變量定義
在C語言中，一個函數(shù)總是占用一段連續(xù)的內(nèi)存空間，而函數(shù)名就是該函數(shù)所占內(nèi)存區(qū)的首地址。可以把函數(shù)的這個首地址（或稱入口地址）賦予一個指針變量，使該指針變量指向該函數(shù)。然后通過指針變量就可以找到并調(diào)用這個函數(shù)。這種指向函數(shù)的指針變量被稱為“函數(shù)指針變量”。
函數(shù)的類型由其返值類型決定，所以指向函數(shù)的指針也有類型之分，它實際上表示所指函數(shù)的返回值類型。另外，同指向數(shù)據(jù)的指針一樣，指向函數(shù)的指針也有常量與變量之分，常量就是在程序中已定義的函數(shù)名，而變量則需要通過定義語句定義之后才能使用。
函數(shù)指針變量定義的格式如下：
類型標識符(*標識符)(參數(shù)類型表);
類型標識符說明函數(shù)指針變量所指函數(shù)的返回值類型，標識符則為變量名。注意，()不能少，否則該語句就成為對函數(shù)的說明語句了。
例如：
int (*fun)();
int max(), min();
…
fun=max;
…
fun=min;
該例中定義了一個函數(shù)指針變量fun，而max、min則為兩個函數(shù)，第一條語句是對函數(shù)指針變量fun的定義，而第二條語句只是對max和min兩個函數(shù)的說明，兩者是有嚴格區(qū)分的。fun是函數(shù)指針變量，可以為它賦值。例如，在程序中將max和min分別賦給fun；而max、min是兩個函數(shù)指針常量，只能引用不能賦值（這里的引用即為函數(shù)調(diào)用）。
注意：定義函數(shù)指針變量時不能寫做“int *fun();”，因為這是一種函數(shù)說明的形式，表示fun是返回值為指針類型的函數(shù)。
函數(shù)指針變量的使用
通過函數(shù)指針變量調(diào)用函數(shù)的語法格式為：
(*函數(shù)指針變量名)(參數(shù)列表)；
例如，上例中對fun變量所指函數(shù)的調(diào)用格式為：
(*fun)( a, b )；
這里，假定max、min函數(shù)有兩個形式參數(shù)，在實際應用中通過函數(shù)指針變量調(diào)用函數(shù)時，所傳入的參數(shù)個數(shù)及類型要完全符合它所指向的函數(shù)。
另外一點需要說明的是，當要將程序中已定義過的函數(shù)名作為常量傳給某一函數(shù)指針變量時（如本例中的賦值操作，以及將函數(shù)名作為參數(shù)傳給另一個函數(shù)的情況），除非該函數(shù)在本文件中的這個賦值操作之前已經(jīng)被定義過，否則就必須經(jīng)過說明后方能執(zhí)行這種操作。
在編程過程中經(jīng)常會遇到這樣一種情況，即要傳給函數(shù)指針變量的函數(shù)名是在其他程序文件中定義的，或者是在本文件中這一傳值操作之后定義的，那么就必須先說明后使用。
【例14.10】 輸入一個兩個數(shù)的四則運算式，通過函數(shù)指針求該運算式的值。
float add(float a,float b)
{return a+b;}
float minus(float a,float b)
{return a-b;}
float mult(float a,float b)
{return a*b;}
float div(float a,float b)
{return a/b;}
main()
{
float m, n, r;
char op;
float (*p)(float,float);
scanf("%f%c%f", &m, &op, &n);
switch(op)
{case '+':p=add; break;
case '-':p=minus;break;
case '*':p=mult; break;
case '/':p=div; break;
default:printf("Error Operation!");
return;
}
r=(*p)(m,n);
printf("%f", r);
}
對指針的幾點說明
（1）有關指針的說明很多是由指針、數(shù)組、函數(shù)說明組合而成的。但它們并不是可以任意組合的，如數(shù)組就不能由函數(shù)組成，即數(shù)組元素不能是一個函數(shù)；函數(shù)也不能返回一個數(shù)組或返回另一個函數(shù)。例如，“int a[5]();”就是錯誤的。
（2）與指針有關的常見說明和意義，如表14.2所示。
表14.2 與指針有關的常見說明和意義表
指 針
意 義
int *p;
p為指向整型量的指針變量
int *p[n];
p為指針數(shù)組，由n個指向整型量的指針元素組成
int (*p)[n];
p為指向整型一維數(shù)組的指針變量，一維數(shù)組的大小為n
int *p();
p為返回指針值的函數(shù)，該指針指向整型量
int (*p)();
p為指向函數(shù)的指針，該函數(shù)返回整型量
int **p;
p為一個指向另一指針的指針變量，該指針指向一個整型量
（3）關于括號的說明。在解釋組合說明符時，標識符右邊的方括號和圓括號優(yōu)先于標識符左邊的“*”號，而方括號和圓括號以相同的優(yōu)先級從左到右結(jié)合。但可以用圓括號改變約定的結(jié)合順序。
（4）閱讀組合說明符的規(guī)則是“從里向外”。從標識符開始，先看它右邊有無方括號[]或圓括號()，如有則先做出解釋，再看左邊有無“*”號。如果在任何時候遇到了閉括號，則在繼續(xù)之前必須用相同的規(guī)則處理括號內(nèi)的內(nèi)容。
例如：
上面給出了由內(nèi)向外的閱讀順序，下面來解釋它。
標識符a被說明為：
① 一個指針變量，它指向。
② 一個函數(shù)，它返回。
③ 一個指針，該指針指向。
④ 一個有10個元素的數(shù)組，其類型為。
⑤ 指針型，它指向。
⑥ int型數(shù)據(jù)。
因此a是一個函數(shù)指針變量，該函數(shù)返回的一個指針又指向一個指針數(shù)組，該指針數(shù)組的元素指向整型量。
指針與鏈表
指針作為函數(shù)的返回值
指針類型的數(shù)據(jù)除了可以作為函數(shù)的形參外，還可以作為函數(shù)的返回值類型。返回指針類型數(shù)據(jù)的函數(shù)定義形式為
類型標識符 *函數(shù)名(形式參數(shù)表)
{
函數(shù)體
}
其中，函數(shù)名前的“*”號表示函數(shù)返回指針類型的數(shù)據(jù)，類型標識符則表示函數(shù)返回的指針所指向目標的類型。
例如：
int * func(int a[], int n)
{
函數(shù)體
}
表示定義函數(shù)func()，該函數(shù)返回一個指向整型數(shù)據(jù)的指針。
在函數(shù)體中要用語句“return指針表達式;”返回指針表達式計算的指針數(shù)據(jù)，指針表達式所指向目標的類型要同函數(shù)頭中的類型標識符相一致。
【例14.11】 編寫函數(shù)，求一個一維數(shù)組中的最大元素，返回該元素的地址。
int *max(int a[],int n)
{ int *pa,*pmax;
pmax = a;
for(pa=a+1;pa<a+n;pa++)
if(*pmax<*pa) pmax=pa;
return pmax;
}
main()
{
int a[10],*p;
for(p=a;p<a+10;p++)
scanf("%d", p);
p=max(a,10);
printf("max=%d",*p);
}
鏈表的引入
獲取連續(xù)存儲空間的基本方法是定義數(shù)組。通過定義數(shù)組，系統(tǒng)可以為用戶分配所需的連續(xù)空間。但是，通過這種方法獲取連續(xù)空間存在以下問題。
① 所要分配的空間一旦分配，大小不能改變。
② 空間利用率差，且不能進行空間擴充。
③ 申請連續(xù)空間時，要受到內(nèi)存空間使用情況的限制。
④ 在連續(xù)空間上進行數(shù)據(jù)的插入、刪除效率低下。
因此，必須有一種新的方法，使得用戶能夠根據(jù)自己的實際需求動態(tài)地申請空間，并且能夠通過一定的方法將自己申請的多個空間聯(lián)系起來。
對于此問題，在C語言中有很好的解決方法，這就是鏈表。鏈表的結(jié)構(gòu)如圖14.9所示。
圖14.9 鏈表的基本結(jié)構(gòu)
圖14.10 單鏈表的節(jié)點結(jié)構(gòu)
鏈表的基本構(gòu)成單位是節(jié)點（Node），如圖14.10所示。
節(jié)點包括兩個域：數(shù)據(jù)域和指針域數(shù)據(jù)。
數(shù)據(jù)域（data）用于存儲節(jié)點的值；指針域（next）用于存儲數(shù)據(jù)元素的直接后繼的地址（或位置）。鏈表正是通過每個節(jié)點的指針域?qū)個節(jié)點鏈接在一起。由于鏈表的每個節(jié)點只有一個指針域，故將這種鏈表又稱為單鏈表。
單鏈表中每個節(jié)點的存儲地址存放在其前趨節(jié)點的指針域中，而第一個節(jié)點無前趨，所以應設一個頭指針L指向第一個節(jié)點。同時，由于表中最后一個節(jié)點沒有直接后繼，則讓表中最后一個節(jié)點的指針域為“空”（NULL）。這樣對于整個鏈表的存取必須從頭指針開始。
有時為了操作的方便，還可以在單鏈表的第一個節(jié)點之前附設一個頭節(jié)點，頭節(jié)點的數(shù)據(jù)域可以存儲一些關于表的附加信息（如長度等），也可以什么都不存。而頭節(jié)點的指針域存儲指向第一個節(jié)點的指針（即第一個節(jié)點的存儲位置），如圖14.11所示。
圖14.11 帶頭節(jié)點的單鏈表
此時帶頭節(jié)點單鏈表的頭指針就不再指向表中第一個節(jié)點而是指向頭節(jié)點。如果表為空表，則頭節(jié)點的指針域為“空”。
設L是單鏈表的頭指針，它指向表中第一個節(jié)點（對于帶頭節(jié)點的單鏈表，則指向單鏈表的頭節(jié)點），若L==NULL（對于帶頭節(jié)點的單鏈表為L->next==NULL），則表示單鏈表為一個空表，其長度為0。若不是空表，則可以通過頭指針訪問表中節(jié)點，找到要訪問的所有節(jié)點的數(shù)據(jù)信息。對于帶頭節(jié)點的單鏈表L，若p=L->next，則p指向表中的第一個節(jié)點，即p->data是數(shù)據(jù)1，而p->next->data是數(shù)據(jù)2，依次類推，如圖14.12所示。
圖14.12 單鏈表
空間的分配與回收
在C語言中，關于空間使用的基本規(guī)則是：誰申請，誰釋放。數(shù)組所占空間是系統(tǒng)分配的，所以使用完成后，系統(tǒng)會自動釋放該空間。若是用戶自己調(diào)用相關的函數(shù)進行了空間的分配，則最后用戶必須調(diào)用相關的函數(shù)釋放空間。
1．空間的申請
在C語言的函數(shù)庫中，有一個非常有用的函數(shù)——malloc()函數(shù)，該函數(shù)用于申請指定字節(jié)數(shù)的內(nèi)存空間，該函數(shù)是一個返回指針類型數(shù)據(jù)的函數(shù)，其格式如下：
void *malloc(unsigned size)；
調(diào)用malloc()函數(shù)時，通過參數(shù)size指定所需申請空間字節(jié)數(shù)，通過函數(shù)的返回值得到所申請空間的首地址。如果系統(tǒng)所剩余的連續(xù)內(nèi)存不滿足要求，函數(shù)返回NULL指針，表示申請失敗。
malloc()函數(shù)所返回的值是指向目標的地址，在實際編程過程中可以通過強制類型轉(zhuǎn)換將該值轉(zhuǎn)換成我們所要求的指針類型，然后將它賦予同樣類型的指針變量，以后就可以通過該指針變量按照我們所定義的類型實現(xiàn)對其所指向的目標元素的訪問。
例如：
double *p;
…
p=(double *)malloc(10*sizeof(double))；
其中，sizeof運算符計算出每一個double型數(shù)據(jù)所占據(jù)的內(nèi)存單元數(shù)，如果p得到的返回值為非NULL的指針，就得到能連續(xù)存放10個double型數(shù)據(jù)的內(nèi)存空間，就可以通過指針表達式p、p+1、…、p+9按照double型數(shù)據(jù)對所申請到的空間中的每個數(shù)據(jù)元素進行訪問。
2．空間的釋放
與malloc()函數(shù)配對使用的另一個函數(shù)是free()函數(shù)，其格式如下：
void free(char *p )；
該函數(shù)用于釋放由malloc()函數(shù)申請的內(nèi)存空間，被釋放的空間可以被malloc()函數(shù)在下一次申請時繼續(xù)使用。
例如，“free(p);”語句就可以釋放用戶自己申請的空間，其中參數(shù)p指向?qū)⒁会尫诺目臻g。
使用malloc()函數(shù)和free()函數(shù)時，必須包含頭文件“stdlib.h”。
鏈表的基本操作
1．鏈表的創(chuàng)建與遍歷
動態(tài)建立單鏈表有如下兩種常用方法。
（1）頭插法建表。從一個空表開始，重復讀入數(shù)據(jù)，生成新節(jié)點，將讀入的數(shù)據(jù)存放到新節(jié)點的數(shù)據(jù)域中，然后將新節(jié)點插入到當前鏈表的表頭節(jié)點之后，直至讀入結(jié)束標志為止。頭插法得到的單鏈表的邏輯順序與輸入的順序相反，所以也將頭插法建表稱為逆序建表法。
采用頭插法建立鏈表的程序代碼如下：
typedef struct Node / * 節(jié)點類型定義 * /
{ char data；
struct Node * next；
}Node, *LinkList； /* LinkList為結(jié)構(gòu)指針類型*/
Linklist CreateFromHead()
{
LinkList L;
Node *s;
char c;
int flag=1; /* 設置標志，初值為1，當輸入“$”時，flag為0，建表 結(jié)束*/
L=(Linklist)malloc(sizeof(Node)); /*為頭節(jié)點分配存儲空間*/
L->next=NULL;
While(flag)
{
c=getchar();
if(c!='$')
{
s=(Node*)malloc(sizeof(Node)); /*為讀入的字符分配存儲空間*/
s->data=c;
s->next=L->next;
L->next=s;
}
else
flag=0;
}
return L
}
（2）尾插法建表。頭插法建立鏈表雖然算法簡單，但生成的鏈表中節(jié)點的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新節(jié)點插到當前鏈表的表尾上。為此需增加一個尾指針r，使之始終指向當前鏈表的表尾。
typedef struct Node / * 節(jié)點類型定義 * /
{ char data；
struct Node * next；
}Node, *LinkList； /* LinkList為結(jié)構(gòu)指針類型*/
Linklist CreateFromTail() /*將新增的字符追加到鏈表的末尾*/
{LinkList L;
Node *r, *s;
int flag =1; /*設置一個標志，初值為1，當輸入“$”時，flag為0，建 表結(jié)束*/
L=(Node * )malloc(sizeof(Node)); /*為頭節(jié)點分配存儲空間*/
L->next=NULL;
r=L; /*r指針始終動態(tài)指向鏈表的當前表尾，以便于做尾插入*/
while(flag)
{
c=getchar();
if(c!='$')
{
s=(Node*)malloc(sizeof(Node));
s->data=c;
r->next=s;
r=s
}
else
{
flag=0;
r->next=NULL; /*將最后一個節(jié)點的next域置空，表示鏈表的結(jié)束*/
}
}
return L;
}
【例14.12】 采用尾插法建立包含10個節(jié)點的單鏈表。
#include "stdlib.h"
#include "stdio.h"
struct list /*定義節(jié)點*/
{ int data;
struct list *next;
};
typedef struct list node;
typedef node *link;
main()
{link ptr,head;
int num,i;
head=(link)malloc(sizeof(node));
ptr=head;
printf("please input 10 numbers==>\n");
for(i=0;i<10;i++)
{
scanf("%d",&num); /*輸入數(shù)據(jù)*/
ptr->data=num; /*填寫節(jié)點數(shù)據(jù)域*/
ptr->next=(link)malloc(sizeof(node)); /*插入新節(jié)點*/
if(i==9)
ptr->next=NULL;
else
ptr=ptr->next;
}
ptr=head;
while(ptr!=NULL) /*遍歷鏈表*/
{
printf("The value is ==>%d\n",ptr->data);
ptr=ptr->next; /*指針后移*/
}
}
2．元素的插入與刪除
要在帶頭節(jié)點的單鏈表L中第i個數(shù)據(jù)元素之前插入一個數(shù)據(jù)元素e，需要首先在單鏈表中找到第i-1個節(jié)點并由指針pre指示，如圖14.13所示。
圖14.13 尋找第i-1個節(jié)點
然后申請一個新的節(jié)點并由指針s指示，其數(shù)據(jù)域的值為e，修改s節(jié)點的指針使其指向第i個節(jié)點。接著修改第i-1個節(jié)點的指針使其指向s，如圖14.14所示。
圖14.14 插入新節(jié)點
例如，在帶頭節(jié)點的單鏈表L中第i個位置插入值為e的新節(jié)點。程序代碼如下：
typedef struct Node / * 節(jié)點類型定義 * /
{ char data；
struct Node * next；
}Node, *LinkList； /* LinkList為結(jié)構(gòu)指針類型*/
int InsList(LinkList L,int i,char e)
{
Node *pre,*s;
int k;
pre=L; k=0;
/*在第i個元素之前插入，需先找到第i-1個數(shù)據(jù)元素的存儲位置,使指針Pre指向它*/
while(pre!=NULL&&k<i-1)
{
pre=pre->next;
k=k+1;
}
if(k!=i-1) /*即while循環(huán)是因為pre=NULL或i<1而跳出的，插入位置不合理*/
{ printf("插入位置不合理！")；
return 0;
}
s=(Node*)malloc(sizeof(Node)); /*為e申請一個新的節(jié)點并由S指向它*/
s->data=e; /*將待插入節(jié)點的值e賦給s的數(shù)據(jù)域*/
s->next=pre->next; /*完成插入操作*/
pre->next=s;
return 1;
}
欲在帶頭節(jié)點的單鏈表L中刪除第i個節(jié)點，則首先要通過計數(shù)方式找到第i-1個節(jié)點并使pre指向第i-1個節(jié)點，而后通過修改pre的next域，刪除第i個節(jié)點并釋放節(jié)點空間。如圖14.15所示。
圖14.15 刪除節(jié)點
例如，在帶頭節(jié)點的單鏈表L中刪除第i個元素，并將刪除的元素保存到變量e中。程序代碼如下：
typedef struct Node / * 節(jié)點類型定義 * /
{ char data；
struct Node * next；
}Node, *LinkList； /* LinkList為結(jié)構(gòu)指針類型*/
int DelList(LinkList L,int i,char *e)
{
Node *p,*r;
int k;
p=L;k=0;
while(p->next!=NULL&&k<i-1) /*尋找被刪除節(jié)點i的前驅(qū)節(jié)點i-1使p指向它*/
{ p=p->next;
k=k+1;
}
if(k!=i-1) /* 即while循環(huán)是因為p->next=NULL或i<1而跳出的*/
{
printf("刪除節(jié)點的位置i不合理！");
return 0;
}
r=p->next;
*e=r->data;
p->next=r->next; /*刪除節(jié)點r*/
free(r); /*釋放被刪除的節(jié)點所占的內(nèi)存空間*/
return 1;
}
應用舉例
【例14.13】 編寫一個函數(shù)，輸入n為偶數(shù)時，調(diào)用函數(shù)求1/2+1/4+…+1/n；當輸入n為奇數(shù)時，調(diào)用函數(shù)求1/1+1/3+…+1/n。要求利用函數(shù)指針。
#include "stdio.h"
main()
{
float peven(),podd(),dcall();
float sum;
int n;
while (1)
{
scanf("%d",&n);
if(n>1)
break;
}
if(n%2==0)
{
printf("Even=");
sum=dcall(peven,n);
}
else
{
printf("Odd=");
sum=dcall(podd,n);
}
printf("%f",sum);
}
float peven(int n)
{
float s;
int i;
s=1;
for(i=2;i<=n;i+=2)
s+=1/(float)i;
return(s);
}
float podd(int n)
{
float s;
int i;
s=0;
for(i=1;i<=n;i+=2)
s+=1/(float)i;
return(s);
}
float dcall(float (*fp)(),int n)
{
float s;
s=(*fp)(n);
return(s);
}
在程序中，函數(shù)指針作為dcall的參數(shù)。
【例14.14】 輸入5個數(shù)字，采用鏈表存放，反向輸出內(nèi)容。
分析 如果采用頭插法建立鏈表，則鏈表中元素的存放順序正好與元素的輸入順序相反。所以只需要以頭插法建立鏈表，然后從頭到尾遍歷鏈表，便可得到所要求的順序。
#include "stdlib.h"
#include "stdio.h"
struct list
{ int data;
struct list *next;
};
typedef struct list node;
typedef node *link;
main()
{
link ptr,head,tail;
int num,i;
tail=(link)malloc(sizeof(node));
tail->next=NULL;
ptr=tail;
printf("\nplease input 5 data==>\n");
for(i=0;i<=4;i++)
{
scanf("%d",&num);
ptr->data=num;
head=(link)malloc(sizeof(node));
head->next=ptr;
ptr=head;
}
ptr=ptr->next;
while(ptr!=NULL)
{ printf("The value is ==>%d\n",ptr->data);
ptr=ptr->next;
}
}
【例14.15】 創(chuàng)建兩個鏈表，并完成兩個鏈表的鏈接。
#include "stdlib.h"
#include "stdio.h"
struct list
{ int data;
struct list *next;
};
typedef struct list node;
typedef node *link;
link create_list(int array[],int num)
{ link tmp1,tmp2,pointer;
int i;
pointer=(link)malloc(sizeof(node));
pointer->data=array[0];
tmp1=pointer;
for(i=1;i<num;i++)
{ tmp2=(link)malloc(sizeof(node));
tmp2->next=NULL;
tmp2->data=array[i];
tmp1->next=tmp2;
tmp1=tmp1->next;
}
return pointer;
}
link concatenate(link pointer1,link pointer2)
{ link tmp;
tmp=pointer1;
while(tmp->next)
tmp=tmp->next;
tmp->next=pointer2;
return pointer1;
}
void disp_list(link pointer)
{
link tmp;
printf("\n");
tmp=pointer;
while(tmp)
{
printf("%6d",tmp->data);
tmp=tmp->next;
}
}
main()
{
int arr1[]={3,12,8,9,11};
int arr2[]={12,34,56,78,75,67,52};
link ptr1,ptr2;
ptr1=create_list(arr1,5);
ptr2=create_list(arr2,7);
concatenate(ptr1,ptr2);
disp_list(ptr1);
}
一、選擇題
1．有以下結(jié)構(gòu)體說明和變量定義，如圖14.16所示，指針p、q、r分別指向一個鏈表中的3個連續(xù)節(jié)點。
struct node
{
int data;
struct node *next;
} *p, *q, *r;
現(xiàn)要將q和r所指節(jié)點的前后位置交換，同時要保持鏈表的連續(xù)，以下錯誤的程序段是 。
圖14.16
A．r->next=q; q->next=r->next; p->next=r;
B．q->next=r->next; p->next=r; r->next=q;
C．p->next=r; q->next=r->next; r->next=q;
D．q->next=r->next; r->next=q; p->next=r;
2．以下與“int *q[5];”等價的定義語句是 。
A．int q[5]; B．int *q C．int * (q[5]); D．int (*q)[5];
3．若有以下定義：
int x[4][3]={1,2,3,4,5,6,7,8,9,10,11,12};
int (*p)[3]=x;
則能夠正確表示數(shù)組元素x[1][2]的表達式是 。
A．*((*p+1)[2]) B．(*p+1)+2
C．*(*(p+5)) D．*(*(p+1)+2)
4．語句“int (*ptr)();”的含義是 。
A．ptr是指向一維數(shù)組的指針變量
B．ptr是指向int型數(shù)據(jù)的指針變量
C．ptr是指向函數(shù)的指針，該函數(shù)返回一個int型數(shù)據(jù)
D．ptr是一個函數(shù)名，該函數(shù)的返回值是指向int型數(shù)據(jù)的指針
5．若有函數(shù)max(a,b)，并且已使函數(shù)指針變量p指向函數(shù)max，當調(diào)用該函數(shù)時，正確的調(diào)用方法是 。
A．(*p)max(a,b); B．*pmax(a,b);
C．(*p)(a,b); D．*p(a,b);
6．下面程序的運行結(jié)果是 。
main()
{ int x[5]={2,4,6,8,10},*p,**pp;
p=x;
pp=&p;
printf("%d",* (p++));
printf("%3d\n",* *pp);
}
A．4 4 B．2 4 C．2 2 D．4 6
7．若定義了以下函數(shù)：
void f(…)
{…
*p=(double *)malloc( 10*sizeof( double));
…
}
p是該函數(shù)的形參，要求通過p把動態(tài)分配存儲單元的地址傳回主調(diào)函數(shù)，則形參p的正確定義應當是 。
A．double *p B．float **p C．double **p D．float *p
8．假定建立了以下鏈表結(jié)構(gòu)，指針p、q分別指向如圖14.17所示的節(jié)點，則以下可以將q所指節(jié)點從鏈表中刪除并釋放該節(jié)點的語句組是 。
圖14.17
A．free(q); p->next=q->next;
B．(*p).next=(*q).next; free(q);
C．q=(*q).next; (*p).next=q; free(q);
D．q=q->next; p->next=q; p=p->next; free(p);
9．以下程序的輸出結(jié)果是 。
fut (int**s,int p[2][3])
{ **s=p[1][1]; }
main( )
{
int a[2][3]={1,3,5,7,9,11},*p;
p=(int*)malloc(sizeof(int));
fut(&p,a);
primtf("%d\n",*p);
}
A．1 B．7 C．9 D．11
10．若有以下的說明和語句：
main()
{int t[3][2], *pt[3],k;
fpr(k=0; k<3;k++)pt[k]=t[k];
}
則以下選項中能正確表示數(shù)組t元素地址的表達式是 。
A．&t[3][2] B．*pt[0] C．*(pt+1) D．&pt[2]
11．設有如下定義：
int (*ptr)*();
則以下敘述中正確的是 。
A．ptr是指向一維組數(shù)的指針變量
B．ptr是指向int型數(shù)據(jù)的指針變量
C．ptr是指向函數(shù)的指針，該函數(shù)返回一個int型數(shù)據(jù)
D．ptr是一個函數(shù)名，該函數(shù)的返回值是指向int型數(shù)據(jù)的指針
二、填空題
1．以下程序段用于構(gòu)成一個簡單的單向鏈表，請?zhí)羁铡?div style="height:15px;">
