5.6指针数组以及指向指针的指针
由于指针本身也是变量,所以它们也可以像其他变量一样存储在数组中。下面编写UNIX程序sort的一个简化版本说明这一点。该程序按照字母顺序对由文本行组成的集合进行排序。我们在第3章中曾描述过一个用于整型数组中的元素进行排序的Shell排序函数,并在第4章中使用快速排序的方式对它进行了改进。这些排序在此仍然是有效的,但是,现在处理的长度不一的文本行,并且,与整数不同的是,它们不能在单个运算中完成比较或者移动操作。我们需要一个能高效、方便地处理可变长度文本行的数据表示方法。 我们引入指针数组处理这种问题。如果待排序的文本行首尾相连地存储在一个长字符数组中,那么每个文本可通过指向它第一个字符的指针来访问。这些指针本身可以存储在一个数组中。这样,将指向两个文本行的指针传递给函数strcmp就可以实现对两个文本行的比较。当交换次序颠倒的两个文本行时,实际上交换的是指针数组中与这两个文本行相对应的指针,而不是两个文本行本身。 这种实现方法消除了因移动文本行本身所带来的复杂的存储管理和巨大的开销这两个孪生问题。 排序过程包含下面的三个步骤: 读取所有的输入行 对文本行进行排序 按次序打印文本行 通常情况下,最好将程序化分若干个与问题的自然划分一致的函数,并通过主函数控制其他函数的执行。关于文本的排序这一步,我们稍后再做说明,现在主要考虑数据结构以及输入和输出函数。 输入函数必须收集和保存每个文本行中的字符,并建立一个指向这些文本行的指针数组。它同时还必须统计输入的行数,因为在排序和打印时要用到这些信息。由于输入函数只能处理有限行数的输入行,所以在输入行数过多而超过限定的最大行数时,该函数返回某个用于表示法行数的数值,例如-1。 输出函数只需要按照指针数组中的次序依次打印这些文本即可。

#include <stdio.h>
#include <string.h>

#define MAXLINES 5000                          //进行排序的最大文本行数

char *lineptr[MAXLINES];                         //指向文本行的指针数组

int readlines(char *lineptr[],int nlines);
void writelines(char *lineptr[],int nlines);

void qsort(char *lineptr[],int left,int right);

//对输入文本进行排序
main()
{
int nlines;                                          //读取输入行的数目
if((nlines=readlines(lineptr,MAXLINES))>=0)
{
qsort(lineptr,0,nlines-1);
writelines(lineptr,nlines);
return 0;
}else
{
printf("error:input too big to sort\n");
return 1;
}
}

#define MAXLEN 1000                             //每个输入文本行的最大长度
int getline(char *,int);
char *alloc(int);

/*读取输入行*/
int readlines(char *lineptr[],int maxlines)
{
int len,nlines;
char *p,line[MAXLEN];
nlines=0;
while((len=getline(line,MAXLEN))>0)
{
if(nlines>=maxlines||(p=alloc(len))==NULL)
return -1;
else
{
line[len-1]='\0';                        //删除换行符
strcpy(p,line);
lineptr[nlines++]=p;
}
}
return nlines;
}

/*写输出行*/
void writelines(char *lineptr[],int nlines)
{
int i;
for(i = 0;i < nlines;i++)
{
printf("%s\n",lineptr[i]);
}
}
该例子中指针数组lineptr的声明是新出现的重要的概念:
char *linesptr[MAXLINES];
它表示lineptr是一个具有MAXLINES个元素的一维数组,其中数组的而每一个元素是一个指向字符类型对象的指针。也就是说,lineptr[i]是一个字符指针,而*lineptr[i]是该指针指向的第i个文本行的首字符。 由于lineptr是一个数组名,因此,可以按照前面例子中相同的方法将其作为指针使用,这样writelines函数可以写成:
void write(char *lineptr[],int nlines)
{
while(nlines-->0)
{
printf("%s\n",*lineptr++);
}
}
循环开始执行时,lineptr指向第一行,每执行依次自增运算都使得lineptr指向下一行,同时对Lines进行自减运算。 在明确了输入和输出函数实现的方式以后,下面就可以考虑文本的排序问题。在这里需要对第4章的快速排序函数做一些小改动:首先,需要修改该函数的声明部分;其次,需要调用strcmp函数完成文本行的比较运算。但排序算法在这里扔有效,不需要做任何的改动。
void qsort(char *v[],int left,int right)
{
int i,last;
void swap(char *v[],int i,int j);
if(left>=right)                   //如果数组元素小于2则返回
return;
swap(v,left,(left+right)/2);
last=left;
for(i=left+1;i<=right;i++)
{
if(strcmp(v[i],v[left])<0)
swap(v,++last,i);
}
swap(v,left,last);
qsort(v,left,last-1);
qsort(v,last+1,right);
}
同样swap函数也只需要做一些很小的改动。
void swap(char *v[],int i,int j)
{
char *temp;
temp=v[i];
v[i]=v[j];
v[j]=temp;
}
因为v(别名lineptr)的所有元素都是字符指针,并且temp也必须是字符指针,因此,temp与v的任意元素之间可以相互复制。 5.7多维数组 C语言提供了类似于矩阵的多维数组,但实际上它们并不像指针数组使用得那样广泛。本节将对多维数组的特性进行介绍。 我们考虑一个日期转换问题:把某月某日这种日期表示形式转换成某年中第几天的表示形式,反之亦然。例如,3月1日是非闰年的第60天,是闰年的61天。在这里,我们定义下列两个函数以进行日期的转换:函数day_of_year将某月某日的日期形式转换成某一年第几天的表示形式,函数month_day则执行相反的转换。因为后一个函数要返回两个值,所以在函数month_day中月和日这两个参数使用指针形式。例如,下列语句:
month_day(1988,60,&m,&d)
将把m的值设置为2,把d的值设置为29(2月29日) 这些函数都需要用到记录每月天数的表(如“9月有30天”等)。对闰年和非闰年来说,每个月的天数不同,所以,将这些天数分别存放在一个二维数组的两行中比在计算过程中判断2月有多少天更容易。该数组以及执行日期转化的函数如下所示:
static char daytab[2][13]={
{0,31,28,31,30,31,30,31,31,30,31,30,31},
{0,31,29,31,30,31,30,31,31,30,31,30,31}
}
//day_of_year函数:将某月某日的日期表示形式转换为某年中第几天的表示形式
int day_of_year(int year,int month,int day)
{
int i,leap;
leap=year%4==0&&year%100!=0||year%400==0;
for(i=1;i<month;i++)
{
day+=daytab[leap][i];
}
return day;
}
//month_day函数:将某年中的第几天日期表示形式转换为某月某日的表现形式。
void month_day(int year,int yearday,int *pmonth,int *pday)
{
int i,leap;
leap=year%4&&year%100!=0||year%400==0;
for(i=1;yearday>daytable[leap][i];i++)
yearday-=daytable[leap][i];
*pmonth=i;
*pday=yearday;
}
我们在前面的章节曾经讲过,逻辑表达式的算术运算值只可能为0(假)或者1(真),因此在本例中,可以将逻辑表达式leap用作数组daytable的下标。 数组daytable必须在函数day_of_year和month_day的外部进行声明,这样这两个函数都可以使用该数组。这里之所以将daytable的元素声明为char类型,是为了说明在char类型的变量中存放较小的非字符整数也是合法的。 到目前为止,daytab使我们遇到的第一个二维数组。在C语言中,二维数组实际上是一个特殊的一维数组,它的每一个元素也是一个数组。因此数组下标应该写成:
daytable[i][j];   //[行][列]
而不是写成
daytable[i,j];    //错误的形式
除了表示方法的区别外,C语言中二维数组的使用方式和其他语言一样。数组元素按行存储,因此,当按存储顺序访问数组时,最右边的数组下标(即列)变化的最快。 数组可以用花括号括起来的初值表进行初始化,二维数组的每一行由相应的子列表进行初始化。在本例中,我们将数组daytable的第一列元素设置为0,这样月份的值是1-12,而不是0-11.由于这里的存储空间不是主要问题,所以这种处理方式比在程序中调整数组的下标更加直观。 如果将二维数组作为参数传递给函数,那么在函数的声明中必须指明数组的列数。数组的行数没有太大的关系,因为前面已经讲过,函数调用时传递的是一个指针,它指向由行向量构成的一维数组。其中每个行向量是具有13个整型元素构成的一维数组。因此,如果将数组daytab作为参数传递给函数f,那么f声明应该写成下面的形式
f(int daytable[2][13]){...}
也可以写成 f(int daytable[][13]){...} 因为数组的行数无关紧要,所以该声明还可以写成
f(int (*daytable)[13]){...}
这种声明形式表明参数是一个指针,它指向具有13个整型元素的一维数组。因为方括号[]的优先级高于*的优先级,所以上述声明中必须使用圆括号。如果去掉括号,则声明变成 int *daytable[13] 这相当于声明了一个数组,该数组有13个元素,其中每个元素都是一个指向整型对象的指针。一般来说,除数组的第一维(下标)可以不指明大小,其他的各维必须明确指定的大小。
5.8指针数组的初始化
考虑这样一个问题:编写一个函数month_name(n),它返回一个指向第n个月名字的字符串指针。这是内部static类型数组的一种理想的应用。month_name函数中包含一个私有的字符串数组,当它被调用时,返回一个指向正确元素的指针。本节将介绍如何初始化该名字数组。 指针数组的初始化语法和前面所讲的其他类型对象的初始化语法类似:
//month_name函数:函数返回第n个月份的名字
char *month_name(int n)
{
static char *name[]=
{
"Illegal month","January","February","March","April","May","June",
"July","August","September","October","November","December"
};
return (n<1||n>12)?name[0]:name[n];
}
其中,name的声明与排序例子中lineptr的声明相同,是一个一维数组,数组的元素为字符指针。name数组的初始化通过一个字符串列表实现,列表中的每一个字符串赋值给数组相应位置的元素。第i个字符串的所有字符存储在存储器中的某个位置,指向它的指针存储在name[i]中。由于上述声明中没有指明数组name的长度,因此,编译器编译时将对初值的个数进行统计,并将这一准确数字填入数组长度。
5.9指针与多维数组
对C语言的初学者来说,很容易混淆二维数组和指针数组之间的区别,比如上面例子中的name。加入有下面两个定义:
int a[10][20];
int *b[10];
那么,从语法角度上讲,a[3][4]和b[3][4]都是对一个int对象的合法引用。但a是一个真正的二维数组,它分配了200个int类型长度的存储空间,并且通过常规的矩阵下标计算公式20*row+col计算得到元素a[row][col]的位置。但是,对比b来说,该定义仅分配了10个指针,并且没有对它进行初始化,它们的初始化初始化必须以显示的方式来进行,比如静态初始化或者通过代码初始化。假定b的每一个元素都指向一个具有20个元素的数组,那么编译器就会为它分配200个int类型长度的存储空间以及10个指针的存储空间。指针数组的一个重要的优点在于,数组的每一行的长度可以不同,也就是说,b的每一个元素不必指向一个具有20个元素的向量,某一些元素可以指向2个元素的向量,某一些元素可以指向50个元素的向量,而某一些元素可以不指向任何向量。 尽管我们在上面的讨论中都借助了整型进行讨论,但到目前为止,指针数组最频繁的用处是存放具有不同长度的字符串,比如函数month_name中的情况,结合下面的声明和图形化描述,我们可以做一个比较。下面是指针数组的声明和图形化描述 5.10命令行参数
在支持C语言的环境中,可以在程序开始执行时将命令行参数传递给程序。调用主函数main时,它带有两个参数。第一个参数(习惯上称为argc,用于参数计数)的值表示运行程序时命令行中参数的数目;第二个参数(称为argv,用于参数向量)是一个指向字符数组的指针,其中每个字符串对应一个参数。我们通常用多级指针处理这些字符串。
最简单的例子是程序echo,它将命令行参数回显在屏幕中的一行中,其中命令行中各参数之间用空格隔开,也就是说,命令
echo hello, word
将打印下列输出: hello,word 按照C语言约定,argv[0]的值是启动该程序的程序名,因此,argc的值至少为1。如果argc的值为1,则说明程序名后面没有命令行参数。在上面的例子中,argc的值为3,argv[0], argv[1], 和argv[2]的值分别"echo","hello,"以及"word"。第一个可选的参数为argv[1],而最后一个可选参数为argv[argc-1]。另外,ANSI标准要求argv[argc]的值必须为一个空指针。
程序echo的第一个版本将argv看成是一个字符指针数组。
#include <stdio.h>
//回显程序命令行参数,版本1
main(int argc,char *argv[])
{
int i;
for(i=1;i<argc;i++)
{
printf("%s%s",argv[i],(i<argc-1)?" ":"");
}
printf("\n");
return 0;
}
因为argv是一个指向指针数组的指针,所以,可以通过指针而非数组小标方式处理命令行参数。echo程序的第二个版本是在对argv进行自增运算、对argc进行自减运算的基础上实现的,其中argv是一个指向char类型的指针的指针:
#include 
//回显程序命令行参数,版本2
main(int argc,char *argv[])
{
int i;
while(--argc>0)
printf("%s%s",*++argv,(i<argc-1)?" ":"");

printf("\n");
return 0;
}
因为argv是一个指向参数字符串数组起始位置的指针,所以,自增(++argv)将使得它在最开始指向argv[1]而非argv[0]。每执行依次自增运算,就使得argv指向下一个参数,*argv就是指向那个参数的指针。与此同时,argc执行自减运算,当它变成0时,就完成了所有参数的打印。 也可以将printf语句改写成下列形式:
printf((argc>1)?"%s ":"%s",*++argv);
这就说明,printf的格式化参数也可以是表达式。 我们将来看第二个例子。在该例子中,我们将增强4.1节中模式查找程序的功能。在4.1节中,我们将查找模式内置到程序中了,这种解决方法显然不能令人满意。下面我们来效仿UNIX程序grep的实现方法改写模式查找程序,通过命令行的第一个参数指定待匹配的模式。
#include 
#include 
#define MAXLINE 1000

int getline(char *line,int max)
//find函数:打印与第一个参数指定的模式匹配的行
main(int argc, char *argv[])
{
char line[MAXLINE];
int found=0;

if(argc!=2)
printf("Usage: find pattern\n");
else
while(getline(line,MAXLINE)>0)
if(strstr(line,argv[1])!=NULL)
{
printf("%s",line);
found++;
}
return found;
}
标准库函数strstr(s,t)返回一个指针,该指针指向字符串t在字符串s中第一次出现的位置;如果字符串t没有在字符串s中出现,函数返回NULL。该函数声明在头文件<string.h>中。
为了更进一步解释指针结构,我们来改变模式查找程序。假定允许程序带两个可选参数。其中一个参数表示“打印除匹配模式之外所有的行”,另一个参数表示“每个打印的文本前面加上相应的行号”。
UNIX系统中的C语言程序中有一个公共的约定:以负号开头的参数表示一个可选标志或者参数。假定-x(代表,除...之外)表示打印所有与模式不匹配的文本行,用-n(代表行号)表示打印行号,那么下列命令:
find -x -n 模式
将打印所有与模式不匹配的行,并在每一个打印行前面加上行号。 可选参数应该允许任意参数出现,同时,程序的其余部分应该与命令行中参数的数目无关。此外,如果可选参数能够组合使用,将会给使用者带来更大的方便,比如:
find-nx模式
改写后的模式查找程序如下表示:
#include <stdio.h>
#include <string.h>
#define MAXLINE 1000

int getline(char *line,int max);

main(int argc,char *argv[])
{
char line[MAXLINE];
long lineno=0;
int c,except=0,number=0,found=0;

while(--argc>0&&(*++argv)[0]=='-')
{
while(c=*++argv[0])
{
switch(c)
{
case 'x':
except=1;
break;
case 'n'
number=1;
break;
default:
printf("find:illegal option %c\n",c);
argc=0;
found=-1;
break;
}
}
}
if(argc!=1)
printf("Usage:find -x -n Pattern \n");
else
while(getline(line,MAXLINE)>0)
{
lineno++;
if((strstr(line,*argv)!=NULL)!=except)
{
if(number)
printf("%ld:",lineno);
printf("%s",line);
found++;

}
}
return found;
}
在处理每一个可选参数之前,argc执行自减运算,argv执行自加运算。循环语句结束时,如果没有错误,则argc的值表示还没有处理参数的数目,而argv则指向这些未处理参数中的第一个参数。因此,这时argc的值应为1,而argv应该指向模式。注意,++argv是一个指向参数字符串的指针,因此(*++argv)[0]是它的第一个字符(另一种有效形式是**++argv)。因为[]与操作数的优先结合优先级比*和++高,所以在上述表达式中必须使用圆括号,否则编译器将会把该表达式当做*++(argv[0])。实际上,我们在内层循环中就使用了表达式*++argv[0],其目的是遍历特定的参数串。在内层循环中,表达式*++argv[0]对指针argv[0]进行了自增运算。 很少有人使用比这个更复杂的指针表达式。如果遇到这种情况,可以将它们分成两步或者三步来理解,这样会更直观一些。 5.11指向函数的指针
在C语言中,函数本身不是变量,但可以定义指向函数的指针。这种类型的指针可以被赋值,存放在数组中,传递给函数以及作为函数的返回值等等。为了说明指向函数的指针的用法,我们接下来将修改本章前面的排序函数。在给定的可选参数-n的情况下,该函数将按数值大小而非字典顺序对输入进行排序。 排序程序通常包括三个部分:判断任何两个对象之间次序的比较操作,颠倒对象次序交换的操作,一个用于比较和交换对象知道所有对象都按正确次序排列的排列算法。由于排序算法与比较、交换操作无关,因此,通过在排序算法中调用不同的比较和交换函数,便可以实现按照不同的标准培训。这就是我们的新版本排序函数所采用的方法。 我们在前面讲过,函数strcmp按字典顺序比较两个输入行。在这里,我们还需要一个以数值为基础来比较两个输入行,并返回与strcmp同样的比较结果的函数numcmp。这些函数在main之前声明,并且,指向恰当函数的指针将被传递给qsort函数。在这里,参数的出错处理并不是问题的重点,我们将主要考虑指向函数的指针问题。
#include 
#include 
#define MAXLINES 5000
char *linestr[MAXLINES];

int readlines(char *lineptr[],int nlines);
void writelines(char *lineptr[],int nlines);
void qsort(void *lineptr[],int left,int right,int (*cmp)(void *,void *));
int numcmp(char *,char *);

main(int argc,char *argv)
{
int nlines;
int numeric=0;

if(argc>1&&strcmp(argv[1],'-n')==0)
numeric=1;
if((nlines=readlines(lineptr,MAXLINES))>=0)
{
qsort((void**)lineptr,0,nlines-1,(int(*)(void*,void*))(numeric?numcmp:strcmp));
writelines(lineptr,nlines);
return 0;
}
else
{
printf("input too big to sort\n");
return 1;
}

在调用函数qsort的语句中,strcmp和numcmp是函数的地址。因为它们是函数,所以前面不需要加上取地址运算符&,同样的原因,数组名前面也不需要&运算符。 改写后的sort函数能够处理任何数据类型,而不仅仅限于字符串。从函数qsort的原型可以看出,它的原型包含一个指针数组、两个整数和一个有两个指针参数的函数。其中,指针数组参数类型为通用指针类型void。由于任何类型的指针都可以转换成void类型,并且在将它转换成原来类型时不会丢失信息,所以,调用qsort函数时可以将参数强制转换成void*类型。比较函数的参数也要执行这种类型的转换。这种转换通常不会影响到数据的实际表示,但要确保编译器不会报错。
void qsort(void *v[],int left,int right,int (*cmp)(void *,void *))
{
int i,last;
void swap(void *v[],int,int);

if(left>=right)
return;
swap(v,left,(left+right)/2);
last=left;
for(i=left+1;i<=right;i++)
if((*comp)(v[i],v[left])<0)
swap(v,++last,i);
swap(v,left,last);
qsort(v,left,last-1,comp);
qsort(v,last+1,right,comp);
}
我们仔细研究一下其中的声明。qsort函数的第四个参数声明如下: int (comp)(void *,void *) 它表明comp是一个指向函数的指针,该函数具有两个void类型的参数,其返回值类型为int。 在下列语句中:
if((*comp)(v[i],v[left])<0)
comp的使用和声明是一致的,comp是一个指向函数的指针,*comp代表一个函数。下列语句是对函数进行调用:
#include 
//numcmp函数:按照数值顺序比较字符串s1和s2
int numcmp(char *s1,char *s2)
{ 
double v1,v2;
v1=atof(s1);
v2=atof(s2);
if(v1<v2)
return -1;
else if(v1>v2)
return 1;
else return 0;
}
其中圆括号是必须的,这样才能保证其中的各个部分正确结合。如果没有括号,例如写成下面的形式: int *comp(void *,void *)//错误的写法 则表明comp是一个函数,该函数返回一个指向int类型的指针,这同我们的本意显然有很大差别。 我们前面讲过函数strcmp,它用于比较两个字符串。这里介绍函数numcmp也是比较两个字符串,但它通过调用atof计算字符串对应的数值,然后在此基础上进行比较:
(*comp)(v[i],v[left])
交换两个指针的swap函数和本章前面的所述的swap函数相同,但它的参数声明为void*类型
void swap(void *v[],int i, int j)
{
void *temp;
temp=v[i];
v[i]=v[j]
v[j]=temp;
}
还可以将其他一些选项增加到排序过程中,有些可以作为较难的练习。