指针与动态空间分配http://jpkc.nwu.edu.cn/jsjjc/ebooks/p14.htm

http://jpkc.nwu.edu.cn/jsjjc/ebooks/p14.htm
章  指针与动态空间分配
指针极大地丰富了C语言的功能。学习指针是学习C语言最重要的一环，正确地理解指针与多维数组的关系、指针数组的概念、函数指针以及多级指针的概念，将有助于编写高效的程序。另一方面，通过指针可以构建链表，链表的引入解决了通过数组获取连续空间的某些限制。通过链表可以解决一些比较复杂的问题。
指针与多维数组
前面介绍的数组只有一个下标，称为一维数组，其数组元素也称为单下标变量。在实际问题中，有很多量是二维的或多维的，因此C语言允许构造多维数组。多维数组元素通过多个下标来标识它在数组中的位置，所以也称为多下标变量。
本节只介绍二维数组，多维数组可由二维数组类推而得到。
指针与二维数组
1．二维数组的线性存储
通过指针引用二维数组元素要比引用一维数组元素复杂一些，为了便于大家理解，首先介绍二维数组在线性空间的存储。设有
int a[3][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12}};
定义了一个二维数组a，共有12个元素。从逻辑上可以把该二维数组a看成一张由3行4列元素组成的二维表格。
尽管一个二维数组像一个表格，但在C语言中，计算机以行为主序（即一行接一行）把数组存放在一维线性内存空间中，如图14.1所示。从图中可以看出，它同一维数组的存放形式一样，但二者引用数组元素地址的计算方法有所区别。
图14.1  数组与存储空间
2．理解二维数组
（1）C语言将二维数组理解为其构成元素是一维数组的一维数组。C语言将二维数组定义时的行、列下标分别用两个[]括号分开。例如，数组a[3][4]，把数组的每一行看做一个整体时，二维数组a中有3个元素：a[0]、a[1]、a[2]。而每个元素a[i]（行数组）又由4个数据元素a[i][0]、a[i][1]、a[i][2]、a[i][3] 组成。如图14.1所示。
（2）表达式a+i（行指针）。对于二维数组，数组名a是一个“指向行的指针”，它指向数组第0行。而且它仍然是数组的首地址，即第0个元素的地址。由于a是指向行的指针，表达式a+i中的偏移量i是以“行”为单位的，所以a+i就是第i行的地址。
因此，有如下等价关系：
l a等价于&a[0]
l a+i等价于&a[i]
也就是说，a+i表示指向二维数组a中第i行的地址（指针）。
如下等价关系也成立。
*(a+i)等价于a[i]等价于&a[i][0]
特别注意：“*(a+i)”中的“*”已不再是取(a+i)地址中的内容，而是表示数组a中的第i行的首地址。即也可以把a+i看做行指针，而把*(a+i)看做列指针。
（3）二维数组元素的地址。因为表达式a[i]和*(a+i)表示第i行的首地址，因而表达式*(a+i)+j就是第i行第j个元素的地址，即数组a中a[i][j]元素的地址。所以有如下等价关系。
*(a+i)+j等价于a[i]+j等价于&a[i][j]
它们都表示数组a中元素a[i][j]的地址。
如果在上述表达式前面再用一个“*”，即*(*(a+i)+j)、*(a[i]+j)、*&a[i][j]，则它们都表示数组a的元素a[i][j]。
实际上，当用户程序中用a[i][j]格式来引用该元素时，C语言对a[i][j]的地址&a[i][j]计算过程是：先将其转换为*(a[i]+j)，再将其中的a[i]转换为*(a+i)，最后得到*(*(a+i)+j)。系统最终是通过转换后的式子*(*(a+i)+j)来计算地址并引用数组元素的。
注意：在一维数组和二维数组中，a+i和*(a+i)的含义不同。在一维数组中，a+i表示数组a的第i个元素地址，而*(a+i)为数组a中第i个元素的值；在二维数组中，a+i和*(a+i)都表示地址，其中a+i表示数组a的第i行首地址，而*(a+i)表示a数组中第i行第0列元素的地址。
（4）二维数组中元素偏移量计算。C语言对二维数组元素地址的处理方法是，先计算行地址，再计算列地址。对于二维数组a[n][m]中的任意一个元素a[i][j]，相对于a[0][0]的偏移量计算公式为：i*m+j。其中m为该二维数组的列数。从此公式可以看出，二维数组中第1个下标i（行下标）加1表示指针跳过一行（即跳过m个元素），第2个下标j（列下标）加1表示指针向后移动一个元素。
【例14.1】  用数组元素的偏移量访问数组。
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");
}
}
运行结果为：
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]的地址）。
通过指针访问二维数组
由于二维数组在计算机中的存放形式是顺序存放的，所以只要定义一个与数组元素类型相一致的指针变量，再将数组中某个元素的地址赋给这个指针变量，通过对该指针的移动和引用，就可以访问到数组中的每一个元素。
【例14.2】  用指针变量输出二维数组的元素。
[方法一]：
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数组的元素示意图
程序中，利用数组元素在内存中存放的连续性，将二维数组看做是一个以a[0]为数组名的由6个元素组成的一维数组。该方法通过改变指针变量p的值（即p++），实现按顺序对数组元素进行访问（如图14.2所示）。
但应注意此时的指针变量p。如果还要用该指针变量p访问a数组中的元素，则应先重新给指针变量p赋数组a地址值，然后才能通过p引用数组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));
}
}
在程序中，通过计算元素地址的偏移量实现对数组元素进行访问，输出了二维数组中的每一个元素的值。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));
}
}
在程序中，还是通过计算元素地址的偏移量实现对数组元素的访问，输出了二维数组中每一个元素的值。
三个程序的运行结果相同，都为
1   2   3
4   5   6
可以发现，虽然方法二和方法三都是通过计算元素地址的偏移量实现对数组元素的访问，可是两者的使用方法却不同：一个是*(p+i*3+j)，另一个是*(*(a+i)+j。无法实现指针使用格式的统一，原因主要在于指针p所指向的对象是一个整型元素，而指针a所指向的对象却是一个一维数组。
为了实现指针使用格式的统一，需要定义一种指向对象是一维数组的指针变量。
指向一维数组的指针变量
这是一种指向对象是一维数组的指针变量，可以用它指向一个二维数组的某一行，然后进一步通过它再访问数组中的元素。
指针定义形式如下：
      
例如：
int (*p)[4]；   /*表示变量p是指向有4个元素的一维整型数组的指针变量*/
char (*q)[20]； /*表示变量q是指向有20个元素的一维字符数组的指针变量*/
【例14.3】  输出二维数组任一元素的值。
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是指向二维数组a第0行的指针变量，p+i是指向第i行的指针。即p的变化是以“行”为单位的。这与前面介绍二维数组的行指针a+i一样。但它与二维数组名的区别是：p是指针变量，而数组名是指针常量。
该程序也可写为
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]));
}
上述程序实现了指针变量p和二维数组a使用格式的统一。也就是说，如果p是指向二维数组a中第i行的指针变量，则*p与a[i]等价。
特别注意：由于p是指向由m个整数组成的一维数组的指针变量，因而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);
}
运行结果为：
p=-54，*p=-54，**p=1
从运行结果可以看出，p和*p都是指针， p指向第0行，而*p指向数组b的第0行第0列元素，即b[0][0]，二者的起始地址相同，所以其值都等于b[0][0]的地址，而**p代表b数组b[0][0]元素。
如果有如下定义：
int (*p)[4],  a[3][4];
p=a;
则有如表14.1所示的表达式的等价关系成立。
表14.1
等 价 关 系
含     义
p+i      等价 a+i   等价 &a[i]
数组a中第i行的地址
*p      等价 a[0]  等价 &a[0][0]
数组a中第0行的首地址
*(p+i)   等价 a[i]   等价 &a[i][0]
数组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;
注意区分下列表达式的含义。
① 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)。
说明：在二维数组中，由数组名、指向元素的指针变量和指向行的指针变量所组成的表达式只有三种含义。
l 指向行的指针，如上例中的a、a+2、pa、pa++、pa+2。
l 指向元素的指针，即元素的地址，如上例中的*a、a[2]、*a+2、p、p+1*4+2等。
l 数组的元素，如上例中的**a、*(p+2)、*(p+2*4)、*(*pa+2)、*(*(pa+1)+2)。
通过指针变量存取数组元素速度快且程序简明。用指针变量作形参，可以允许数组的行数不同。因此数组与指针联系紧密。
指针数组与指针的指针
指针数组
可以将多个指向同一数据类型的指针存储在一个数组中，用来存储指针型数据的数组就称为指针数组。指针数组中每个元素都是指向同一数据类型的指针。
指针数组的定义形式如下：
类型标识符 *数组名[整型常量表达式]；
例如：
char *strings[10];
int  *a[20];
其中，“char *strings[10];”语句定义了一个有10个元素的一维数组strings，它的每一个元素为指向char型的指针变量，即可以给每一个元素赋一个字符型数据对象的地址。而语句“int*a[20];”定义了一个有20个元素的数组a，它的每一个元素为指向int型的指针变量。
在使用指针数组时，要注意数组元素的值和数组元素所指向的值。例如：
int *p[4], *pa, a=12, b=20;
pa=&a;
p[0]=pa;
p[1]=&b;
数组p的元素p[0]的值为整型变量a的地址，元素p[1]的值为变量b的地址（如图14.3所示）。
【例14.5】  用指针数组输出n个字符串。
#include "stdio.h"
main()
{ char *ps[4]={"Unix","Linux","Windows","Dos"};
int i;
for(i=0;i<4;i++) puts(ps[i]);
}
运行结果为
Unix
Linux
Windows
Dos
程序中，指针数组ps的元素分别指向4个字符串的首地址，如图14.4所示。
指针数组非常有用，因为这种数组中每一个元素实际上都是指向另一个数据的指针。因此，可以通过将不同长度的字符串首地址分别放入指针数组的每一个元素中，从而实现对这些字符串的处理。

图14.3  数组元素的值和数组元素所指向的值                          图14.4  ps的指向示意图
例如，对于图书名的管理就可以使用此方法。把书名作为一个字符串，然后将其首地址放入指针数组的某元素中。这样，通过指针数组就可以对图书进行管理（如图14.5所示）。

图14.5
它的优点在于可以根据书名的实际大小分配存储空间，从而避免采用字符数组浪费空间的问题。假设定义字符数组char c[5][128]存放书名，则该字符数组可以放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])；
}
运行结果为：
Internet
C language
Windows
Linux
Unix
指向指针的指针
指针数组的数组名是一个指针常量，它所指向的目标是指针型数据。也就是说，其目标又是指向其他基本类型数据的指针，所以指针数组名是指向指针类型数据的指针，故称它为指针的指针。
图14.6  变量p与
pp示例图
指针数组名是指针常量，它是在定义指针数组时产生的。那么如何定义指向指针类型的指针变量呢？和一般的变量一样，对于一个指针变量，系统也为其在内存中分配相应的内存空间。因此，可以用一个特殊类型的指针指向一个指针变量（或指针数组中的元素）。这个特殊类型的指针就是指向指针类型的指针变量。
定义形式如下：
类型符 **变量名；
例如：
float **pp;
表示定义指向指针类型的指针变量pp，它所指向的对象是“float  *”类型（即指向实型数的指针变量）。
例如，有如下程序段：
float a=3.14;
float *p;
float **pp;  /* pp是指向float *类型数据的指针 */
p=&a;
pp=&p;    /* 将p的地址赋给pp */
其变量在内存中的分配情况如图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，它可以变为*(*p)形式，而*p就是pp，故**p即为*pp。所以，可以直接用**p的形式引用变量a。而不能使用*p形式。
在下面程序中，首先定义指针数组ps并为其初始化赋值。接着又定义了一个指向指针的指针变量pps。在5次循环中， 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)；
}
}
运行结果为
Internet
C language
Windows
Linux
Unix
注意：该程序是用指向指针的指针变量来访问字符串，所以在“printf("%s\n",*p)；”语句中使用了*p形式。请注意其与**p的区别。**p表示一个具体的字符对象， p存放的是name数组元素的地址，而*p是目标对象的地址。如图14.8所示。

图14.8  p、*p和**p的区别
当需要通过函数参数返回指针型的数据时，需要传入该指针型数据的地址，实际上就是指针的指针，而在函数中要将返回的结果存入该指针所指向的目标，这是对指针的指针类型数据的一个典型应用。
另外，指针的指针类型数据也常用于处理字符串集合，处理时需要将每一个字符串的首地址存储在指针数组中的每个元素中，然后通过这个指针数组就可以访问到所有的字符串。下面通过一个例子来说明这一方面的应用。
【例14.9】  输入5个国名，并按字母顺序排列后输出。
分析  在以前的例子中采用了普通的排序方法，逐个比较之后交换字符串的位置。而交换字符串的物理位置是通过字符串复制函数完成的，反复的交换将使程序执行的速度很慢，同时由于各字符串（国名）的长度不同，又增加了存储管理的负担。
用指针数组能很好地解决这些问题。把所有的字符串存放在一个数组中，把这些字符数组的首地址存放在一个指针数组中，当需要交换两个字符串时，只需交换指针数组相应两元素的内容（地址）即可，而不必交换字符串本身。
#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{
k=i;
for(j=i+1;jif(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}
程序中定义了两个函数，一个名为sort()完成排序，其形参为指针数组name，即为待排序的各字符串数组的指针。形参n为字符串的个数。在sort()函数中，对两个字符串比较，采用了strcmp()函数，strcmp()函数允许参与比较的字符串以指针方式出现。name[k]和name[j]均为指针，因此是合法的。另一个函数为print()，用于排序后字符串的输出，其形参与sort()的形参相同。
主函数main()中，定义了指针数组name并为其做了初始化赋值。然后分别调用sort()函数、print()函数完成排序和输出。
字符串比较后需要交换时，只交换指针数组元素的值，而不交换具体的字符串，这样将大大减少时间的开销，提高了运行效率。
函数指针
函数指针变量定义
在C语言中，一个函数总是占用一段连续的内存空间，而函数名就是该函数所占内存区的首地址。可以把函数的这个首地址（或称入口地址）赋予一个指针变量，使该指针变量指向该函数。然后通过指针变量就可以找到并调用这个函数。这种指向函数的指针变量被称为“函数指针变量”。
函数的类型由其返值类型决定，所以指向函数的指针也有类型之分，它实际上表示所指函数的返回值类型。另外，同指向数据的指针一样，指向函数的指针也有常量与变量之分，常量就是在程序中已定义的函数名，而变量则需要通过定义语句定义之后才能使用。
函数指针变量定义的格式如下：
类型标识符(*标识符)(参数类型表);
类型标识符说明函数指针变量所指函数的返回值类型，标识符则为变量名。注意，()不能少，否则该语句就成为对函数的说明语句了。
例如：
int  (*fun)();
int max(), min();
…
fun=max;
…
fun=min;
该例中定义了一个函数指针变量fun，而max、min则为两个函数，第一条语句是对函数指针变量fun的定义，而第二条语句只是对max和min两个函数的说明，两者是有严格区分的。fun是函数指针变量，可以为它赋值。例如，在程序中将max和min分别赋给fun；而max、min是两个函数指针常量，只能引用不能赋值（这里的引用即为函数调用）。
注意：定义函数指针变量时不能写做“int *fun();”，因为这是一种函数说明的形式，表示fun是返回值为指针类型的函数。
函数指针变量的使用
通过函数指针变量调用函数的语法格式为：
(*函数指针变量名)(参数列表)；
例如，上例中对fun变量所指函数的调用格式为：
(*fun)( a, b )；
这里，假定max、min函数有两个形式参数，在实际应用中通过函数指针变量调用函数时，所传入的参数个数及类型要完全符合它所指向的函数。
另外一点需要说明的是，当要将程序中已定义过的函数名作为常量传给某一函数指针变量时（如本例中的赋值操作，以及将函数名作为参数传给另一个函数的情况），除非该函数在本文件中的这个赋值操作之前已经被定义过，否则就必须经过说明后方能执行这种操作。
在编程过程中经常会遇到这样一种情况，即要传给函数指针变量的函数名是在其他程序文件中定义的，或者是在本文件中这一传值操作之后定义的，那么就必须先说明后使用。
【例14.10】  输入一个两个数的四则运算式，通过函数指针求该运算式的值。
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）有关指针的说明很多是由指针、数组、函数说明组合而成的。但它们并不是可以任意组合的，如数组就不能由函数组成，即数组元素不能是一个函数；函数也不能返回一个数组或返回另一个函数。例如，“int a[5]();”就是错误的。
（2）与指针有关的常见说明和意义，如表14.2所示。
表14.2  与指针有关的常见说明和意义表
指    针
意    义
int *p;
p为指向整型量的指针变量
int *p[n];
p为指针数组，由n个指向整型量的指针元素组成
int (*p)[n];
p为指向整型一维数组的指针变量，一维数组的大小为n
int *p();
p为返回指针值的函数，该指针指向整型量
int (*p)();
p为指向函数的指针，该函数返回整型量
int **p;
p为一个指向另一指针的指针变量，该指针指向一个整型量
（3）关于括号的说明。在解释组合说明符时，标识符右边的方括号和圆括号优先于标识符左边的“*”号，而方括号和圆括号以相同的优先级从左到右结合。但可以用圆括号改变约定的结合顺序。
（4）阅读组合说明符的规则是“从里向外”。从标识符开始，先看它右边有无方括号[]或圆括号()，如有则先做出解释，再看左边有无“*”号。如果在任何时候遇到了闭括号，则在继续之前必须用相同的规则处理括号内的内容。
例如：

上面给出了由内向外的阅读顺序，下面来解释它。
标识符a被说明为：
① 一个指针变量，它指向。
② 一个函数，它返回。
③ 一个指针，该指针指向。
④ 一个有10个元素的数组，其类型为。
⑤ 指针型，它指向。
⑥ int型数据。
因此a是一个函数指针变量，该函数返回的一个指针又指向一个指针数组，该指针数组的元素指向整型量。
指针与链表
指针作为函数的返回值
指针类型的数据除了可以作为函数的形参外，还可以作为函数的返回值类型。返回指针类型数据的函数定义形式为
类型标识符  *函数名(形式参数表)
{
函数体
}
其中，函数名前的“*”号表示函数返回指针类型的数据，类型标识符则表示函数返回的指针所指向目标的类型。
例如：
int * func(int a[], int n)
{
函数体
}
表示定义函数func()，该函数返回一个指向整型数据的指针。
在函数体中要用语句“return指针表达式;”返回指针表达式计算的指针数据，指针表达式所指向目标的类型要同函数头中的类型标识符相一致。
【例14.11】  编写函数，求一个一维数组中的最大元素，返回该元素的地址。
int *max(int a[],int n)
{ int *pa,*pmax;
pmax = a;
for(pa=a+1;paif(*pmax<*pa) pmax=pa;
return  pmax;
}
main()
{
int a[10],*p;
for(p=a;pscanf("%d", p);
p=max(a,10);
printf("max=%d",*p);
}
链表的引入
获取连续存储空间的基本方法是定义数组。通过定义数组，系统可以为用户分配所需的连续空间。但是，通过这种方法获取连续空间存在以下问题。
① 所要分配的空间一旦分配，大小不能改变。
② 空间利用率差，且不能进行空间扩充。
③ 申请连续空间时，要受到内存空间使用情况的限制。
④ 在连续空间上进行数据的插入、删除效率低下。
因此，必须有一种新的方法，使得用户能够根据自己的实际需求动态地申请空间，并且能够通过一定的方法将自己申请的多个空间联系起来。
对于此问题，在C语言中有很好的解决方法，这就是链表。链表的结构如图14.9所示。
图14.9  链表的基本结构
图14.10  单链表的节点结构
链表的基本构成单位是节点（Node），如图14.10所示。
节点包括两个域：数据域和指针域数据。
数据域（data）用于存储节点的值；指针域（next）用于存储数据元素的直接后继的地址（或位置）。链表正是通过每个节点的指针域将n个节点链接在一起。由于链表的每个节点只有一个指针域，故将这种链表又称为单链表。
单链表中每个节点的存储地址存放在其前趋节点的指针域中，而第一个节点无前趋，所以应设一个头指针L指向第一个节点。同时，由于表中最后一个节点没有直接后继，则让表中最后一个节点的指针域为“空”（NULL）。这样对于整个链表的存取必须从头指针开始。
有时为了操作的方便，还可以在单链表的第一个节点之前附设一个头节点，头节点的数据域可以存储一些关于表的附加信息（如长度等），也可以什么都不存。而头节点的指针域存储指向第一个节点的指针（即第一个节点的存储位置），如图14.11所示。
图14.11  带头节点的单链表
此时带头节点单链表的头指针就不再指向表中第一个节点而是指向头节点。如果表为空表，则头节点的指针域为“空”。
设L是单链表的头指针，它指向表中第一个节点（对于带头节点的单链表，则指向单链表的头节点），若L==NULL（对于带头节点的单链表为L->next==NULL），则表示单链表为一个空表，其长度为0。若不是空表，则可以通过头指针访问表中节点，找到要访问的所有节点的数据信息。对于带头节点的单链表L，若p=L->next，则p指向表中的第一个节点，即p->data是数据1，而p->next->data是数据2，依次类推，如图14.12所示。

图14.12  单链表
空间的分配与回收
在C语言中，关于空间使用的基本规则是：谁申请，谁释放。数组所占空间是系统分配的，所以使用完成后，系统会自动释放该空间。若是用户自己调用相关的函数进行了空间的分配，则最后用户必须调用相关的函数释放空间。
1．空间的申请
在C语言的函数库中，有一个非常有用的函数——malloc()函数，该函数用于申请指定字节数的内存空间，该函数是一个返回指针类型数据的函数，其格式如下：
void  *malloc(unsigned size)；
调用malloc()函数时，通过参数size指定所需申请空间字节数，通过函数的返回值得到所申请空间的首地址。如果系统所剩余的连续内存不满足要求，函数返回NULL指针，表示申请失败。
malloc()函数所返回的值是指向目标的地址，在实际编程过程中可以通过强制类型转换将该值转换成我们所要求的指针类型，然后将它赋予同样类型的指针变量，以后就可以通过该指针变量按照我们所定义的类型实现对其所指向的目标元素的访问。
例如：
double  *p;
…
p=(double *)malloc(10*sizeof(double))；
其中，sizeof运算符计算出每一个double型数据所占据的内存单元数，如果p得到的返回值为非NULL的指针，就得到能连续存放10个double型数据的内存空间，就可以通过指针表达式p、p+1、…、p+9按照double型数据对所申请到的空间中的每个数据元素进行访问。
2．空间的释放
与malloc()函数配对使用的另一个函数是free()函数，其格式如下：
void  free(char *p )；
该函数用于释放由malloc()函数申请的内存空间，被释放的空间可以被malloc()函数在下一次申请时继续使用。
例如，“free(p);”语句就可以释放用户自己申请的空间，其中参数p指向将要被释放的空间。
使用malloc()函数和free()函数时，必须包含头文件“stdlib.h”。
链表的基本操作
1．链表的创建与遍历
动态建立单链表有如下两种常用方法。
（1）头插法建表。从一个空表开始，重复读入数据，生成新节点，将读入的数据存放到新节点的数据域中，然后将新节点插入到当前链表的表头节点之后，直至读入结束标志为止。头插法得到的单链表的逻辑顺序与输入的顺序相反，所以也将头插法建表称为逆序建表法。
采用头插法建立链表的程序代码如下：
typedef struct Node                   / * 节点类型定义 * /
{ char data；
struct Node  * next；
}Node, *LinkList；                  /* LinkList为结构指针类型*/
Linklist CreateFromHead()
{
LinkList   L;
Node   *s;
char     c;
int flag=1;                                    /* 设置标志，初值为1，当输入“$”时，flag为0，建表                                                                                                 结束*/
L=(Linklist)malloc(sizeof(Node));   /*为头节点分配存储空间*/
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）尾插法建表。头插法建立链表虽然算法简单，但生成的链表中节点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新节点插到当前链表的表尾上。为此需增加一个尾指针r，使之始终指向当前链表的表尾。
typedef struct Node                   / * 节点类型定义 * /
{ char data；
struct Node  * next；
}Node, *LinkList；                  /* LinkList为结构指针类型*/
Linklist CreateFromTail()             /*将新增的字符追加到链表的末尾*/
{LinkList L;
Node *r, *s;
int flag =1;                                              /*设置一个标志，初值为1，当输入“$”时，flag为0，建                                                                                      表结束*/
L=(Node * )malloc(sizeof(Node));     /*为头节点分配存储空间*/
L->next=NULL;
r=L;                             /*r指针始终动态指向链表的当前表尾，以便于做尾插入*/
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;          /*将最后一个节点的next域置空，表示链表的结束*/
}
}
return L;
}
【例14.12】  采用尾插法建立包含10个节点的单链表。
#include "stdlib.h"
#include "stdio.h"
struct list                                  /*定义节点*/
{ 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);                       /*输入数据*/
ptr->data=num;                          /*填写节点数据域*/
ptr->next=(link)malloc(sizeof(node));        /*插入新节点*/
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．元素的插入与删除
要在带头节点的单链表L中第i个数据元素之前插入一个数据元素e，需要首先在单链表中找到第i-1个节点并由指针pre指示，如图14.13所示。
图14.13  寻找第i-1个节点
然后申请一个新的节点并由指针s指示，其数据域的值为e，修改s节点的指针使其指向第i个节点。接着修改第i-1个节点的指针使其指向s，如图14.14所示。

图14.14  插入新节点
例如，在带头节点的单链表L中第i个位置插入值为e的新节点。程序代码如下：
typedef struct Node                  / * 节点类型定义 * /
{ char data；
struct Node  * next；
}Node, *LinkList；                  /* LinkList为结构指针类型*/
int InsList(LinkList L,int i,char e)
{
Node *pre,*s;
int k;
pre=L;  k=0;
/*在第i个元素之前插入，需先找到第i-1个数据元素的存储位置,使指针Pre指向它*/
while(pre!=NULL&&k{
pre=pre->next;
k=k+1;
}
if(k!=i-1)                 /*即while循环是因为pre=NULL或i<1而跳出的，插入位置不合理*/
{ printf("插入位置不合理！")；
return 0;
}
s=(Node*)malloc(sizeof(Node));    /*为e申请一个新的节点并由S指向它*/
s->data=e;                      /*将待插入节点的值e赋给s的数据域*/
s->next=pre->next;               /*完成插入操作*/
pre->next=s;
return 1;
}
欲在带头节点的单链表L中删除第i个节点，则首先要通过计数方式找到第i-1个节点并使pre指向第i-1个节点，而后通过修改pre的next域，删除第i个节点并释放节点空间。如图14.15所示。

图14.15  删除节点
例如，在带头节点的单链表L中删除第i个元素，并将删除的元素保存到变量e中。程序代码如下：
typedef struct Node                  / * 节点类型定义 * /
{ char data；
struct Node  * next；
}Node, *LinkList；                  /* LinkList为结构指针类型*/
int DelList(LinkList L,int i,char *e)
{
Node *p,*r;
int k;
p=L;k=0;
while(p->next!=NULL&&k{ p=p->next;
k=k+1;
}
if(k!=i-1)                        /* 即while循环是因为p->next=NULL或i<1而跳出的*/
{
printf("删除节点的位置i不合理！");
return 0;
}
r=p->next;
*e=r->data;
p->next=r->next;                 /*删除节点r*/
free(r);                         /*释放被删除的节点所占的内存空间*/
return 1;
}
应用举例
【例14.13】  编写一个函数，输入n为偶数时，调用函数求1/2+1/4+…+1/n；当输入n为奇数时，调用函数求1/1+1/3+…+1/n。要求利用函数指针。
#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);
}
在程序中，函数指针作为dcall的参数。
【例14.14】  输入5个数字，采用链表存放，反向输出内容。
分析  如果采用头插法建立链表，则链表中元素的存放顺序正好与元素的输入顺序相反。所以只需要以头插法建立链表，然后从头到尾遍历链表，便可得到所要求的顺序。
#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】  创建两个链表，并完成两个链表的链接。
#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{ 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．有以下结构体说明和变量定义，如图14.16所示，指针p、q、r分别指向一个链表中的3个连续节点。
struct node
{
int data;
struct node *next;
} *p, *q, *r;
现要将q和r所指节点的前后位置交换，同时要保持链表的连续，以下错误的程序段是    。
图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;
则能够正确表示数组元素x[1][2]的表达式是       。
A．*((*p+1)[2])                                B．(*p+1)+2
C．*(*(p+5))                               D．*(*(p+1)+2)
4．语句“int (*ptr)();”的含义是        。
A．ptr是指向一维数组的指针变量
B．ptr是指向int型数据的指针变量
C．ptr是指向函数的指针，该函数返回一个int型数据
D．ptr是一个函数名，该函数的返回值是指向int型数据的指针
5．若有函数max(a,b)，并且已使函数指针变量p指向函数max，当调用该函数时，正确的调用方法是        。
A．(*p)max(a,b);              B．*pmax(a,b);
C．(*p)(a,b);                         D．*p(a,b);
6．下面程序的运行结果是        。
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．若定义了以下函数：
void f(…)
{…
*p=(double *)malloc( 10*sizeof( double));
…
}
p是该函数的形参，要求通过p把动态分配存储单元的地址传回主调函数，则形参p的正确定义应当是       。
A．double *p       B．float **p       C．double **p       D．float *p
8．假定建立了以下链表结构，指针p、q分别指向如图14.17所示的节点，则以下可以将q所指节点从链表中删除并释放该节点的语句组是        。
图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．以下程序的输出结果是        。
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];
}
则以下选项中能正确表示数组t元素地址的表达式是        。
A．&t[3][2]       B．*pt[0]          C．*(pt+1)          D．&pt[2]
11．设有如下定义：
int (*ptr)*();
则以下叙述中正确的是       。
A．ptr是指向一维组数的指针变量
B．ptr是指向int型数据的指针变量
C．ptr是指向函数的指针，该函数返回一个int型数据
D．ptr是一个函数名，该函数的返回值是指向int型数据的指针
二、填空题
1．以下程序段用于构成一个简单的单向链表，请填空。
struct STRU
{ int x, y ;
float rate;
p;
} a, b;
a.x=0; a.y=0; a.rate=0; a.p=&b;
b.x=0; b.y=0; b.rate=0; b.p=NULL;
2．若要使指针p指向一个double类型的动态存储单元，请填空。
p=          malloc(sizeof(double));
3．以下函数creatlist用于建立一个带头节点的单链表，新的节点总是插在链表的末尾。链表的头指针作为函数值返回，链表最后一个节点的next域放入NULL，作为链表结束标志。data为字符型数据域，next为指针域。读入“#”表示输入结束（“#”不存入链表）。请填空。
struct node
{ char data；
struct node * next；
}；
creatlist()
{ struct node * h，* s，* r； char ch；
h=(struct node *)malloc(sizeof(struct node))；
r=h；
ch=getchar()；
；
{ s=(struct node *)malloc(sizeof(struct node))；
s->data=             ；
r->next=s； r=s；
ch=getchar()； }
r->next=            ；
return h；
}
4．下列函数create用于创建n个student类型节点的链表。
student *create(________)
{
int i;student *h,*p1,*p2;
p1=h=new student;  /*或p1=h=(student*) malloc(sizeof(student));*/
scanf("%s%d",h->name,&h->cj);
for(i=2;i<=n;i++)
{
p2=new student;
________;
p1->next=p2;_______;
}
p2->next=NULL;
________;
}
三、程序设计题
1．用指向指针的指针的方法对5个字符串排序并输出。
2．在主函数中输入10个字符串，用另一函数对它们排序，然后在主函数中输出这10 个已排好序的字符串。
3．通过指针数组p和一维数组a构成一个3×2的二维数组，并为a数组赋初值2、4、6、8、…。要求先按行的顺序输出此二维数组，然后再按列的顺序输出它。
4．使用函数指针编写程序，该程序能对任意输入的两个数a、b求出a+b、a-b、a*b、a/b。
5．请编一函数“void fun(int tt[][],int pp[])”，tt指向一个M行N列的二维数组，求出二维数组中每列的最小元素，并依次放入pp所指的一维数组中，二维数组的元素值已在主函数中赋予。
6．输入若干人的姓名，以“#”作为结束标志，将所输入的姓名存入链表。
7．在上题所创建的链表中再输入一个姓名，在链表中查找该姓名是否存在。若存在，则在链表中删除该姓名数据。