从头学C(48)指针数组以及指向指针的指针

0

由于指针本身也是变量,所以它们可以像其他变量一样存储在数组中,同时,指针也可以指向其他指针。

第五章 指针与数组 >> 5.6 指针数组以及指向指针的指针

1. 指针数组

我们在《从头学C(28)while循环与for循环》中学习过一个用于对整型数组中的元素进行排序的 shell 排序算法,并在《从头学C(41)递归》中学习了另一种快速排序算法 qsort,不过这些都是针对整型数组的排序。

由于C语言不能在单个运算中完成字符串的比较或移动操作,因此如果想要对多行文本进行排序(按字母顺序对文本行组成的集合进行排序),我们就需要一个更高效、方便地处理可变长度文本行的数据表示方法。

引入指针数组(数组中每个元素都是一个指针)来处理这类问题:

  1. 考虑到每个文本行都可以通过指向它的第一个字符的指针来访问,我们可以将这些指针本身存储在一个数组中。
  2. 在进行文本行的比较时,只需将指向这两个文本行的指针传递给 strcmp 函数即可。
  3. 当需要调换两个文本行的次序时,实际上交换指针数组中与这两个文本行相对应的指针即可,而不用移动文本行。

C语言_指针数组

显然,只移动指针要比移动文本行更节省存储空间以及系统计算开销,效率更高。

排序过程主要包含 3 个步骤:①读取所有文本行;②对文本行进行排序;③按次序打印文本行。最好的程序结构当然是将以上各步骤以子函数实现,在主函数中进行调用和控制。

对于①读取所有文本行,它必须完成的功能有:读取并保存每个文本行的全部字符,并建立一个指向这些文本行的指针的数组;统计文本行的行数(排序和打印的过程会用到);读取文本行的函数只能处理有限行的文本,如果行数过多而无法处理,需返回某个用于表示非法行数的数值,如 -1。

对于②对文本行进行排序,我们可以借鉴之前的快速排序算法 qsort:在里面通过调用 strcmp 函数完成文本行的比较运算;而递归算法本身依然是有效的,则不用修改。

对于③按次序打印文本行,只需按指针数组的次序依次打印数组的每个元素所指向的字符串。

完整的实现代码如下:

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

#define MAXLINES 1000     /* max lines to be sorted */

char *lineptr[MAXLINES];  /* pointers to next lines */

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

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

/* sort input lines */
int main()
{
        int nlines;     /* number of input lines read */

        if((nlines = readlines(lineptr, MAXLINES)) >= 0 ) {
                printf("**********  before sort ********** \n");
                writelines(lineptr, nlines);
                printf("********************************** \n");

                qsort(lineptr, 0, nlines-1);

                printf("**********  after  sort ********** \n");
                writelines(lineptr, nlines);
                printf("********************************** \n");
                return 0;
        } else {
                printf("ERROR: input too big to sort\n");
                return 1;
        }
}

#define MAXLEN 1000     /* max length of any input line */

/* my_getline: read a line into s, return length */
int my_getline(char s[], int lim)
{
        int c, i = 0;

        while(--lim > 0 && (c=getchar()) != EOF && c != '\n')
                s[i++] = c;
        if(c == '\n')
                s[i++] = c;
        s[i]= '\0';
        return i;
}

#define ALLOCSIZE (MAXLEN * MAXLINES)
static char allocbuf[ALLOCSIZE];  /* storage for alloc */
static char *allocp = allocbuf;   /* next free position */
/* alloc: return pointer to n characters */
char *alloc(int n)      /* return pointer to n characters */
{
        if( allocbuf + ALLOCSIZE - allocp >= n) { /* it fits */
                allocp += n;
                return allocp - n; /* old p */
        } else
                return 0;
}

/* my_strcpy: copy t to s; pointer version 3 */
void my_strcpy(char *s, char *t)
{
        while(*s++ = *t++)
                ;
}

/* readlines: read input lines */
int readlines(char *lineptr[], int maxlines)
{
        int len, nlines;
        char *p, line[MAXLEN];

        nlines = 0;
        while((len = my_getline(line, MAXLEN)) > 0) {
                if(nlines >= maxlines || (p = alloc(len)) == NULL)
                        return -1;
                else {
                        line[len-1] = '\0';     /* delete the '\n' */
                        my_strcpy(p, line);
                        lineptr[nlines++] = p;
                }
        }
        return nlines;
}

/* writelines: write output lines */
void writelines(char *lineptr[], int nlines)
{
        int i;

        for(i = 0; i < nlines; i++)
                printf("%s\n",lineptr[i]);
}

/* swap: interchange v[i]and v[j]*/
void swap(char *v[], int i, int j)
{
        char *temp;

        temp = v[i];
        v[i]= v[j];
        v[j]= temp;
}

/* my_strcmp: retrun <0 if s<t, 0 if s==t, >0 if s>t*/
int my_strcmp(char *s, char *t)
{
        for( ; *s == *t; s++, t++)
                if(*s == '\0')
                        return 0;
        return *s - *t;
}

/* qsort: sort v[left]...v[right]into increasing order */
void qsort(char *v[], int left, int right)
{
        int i, last;

        if(left >= right)  /* do nothing if array contains*/
                return;
        swap(v, left, (left + right)/2);
        last = left;
        for(i = left+1; i <= right; i++)
                if(my_strcmp(v[i], v[left]) < 0)
                        swap(v, ++last, i);
        swap(v, left, last);
        qsort(v, left, last-1);
        qsort(v, last+1, right);
}

第 6 行是指针数组 lineptr 的声明,它表明 lineptr 是一个具有 MAXLINES 个元素的一维数组,而且数组中的每个元素都是一个指向 char 类型对象的指针。即 lineptr[i]是一个字符指针,而 *lineptr[i]是该指针指向的第 i 个文本行的首字符。

第 51 行我们用了一个一维字符数组 char allocbuf[ALLOCSIZE] 来存储所有的文本行,通过 alloc 函数从中分配空间给新输入的字符串,并将这个分配得到的地址赋给指针数组对应的元素。

由于 lineptr 本身是一个数组名,因此也可以和之前的例子一样将其作为指针使用,第 90 行的 writelines 函数可以改写成:

void writelines(char *lineptr[], int nlines)
{
        while(nlines-- > 0)
                printf("%s\n", *lineptr++);
}

此处的参数 lineptr 是可以进行自增运算的。while 循环开始执行时, *lineptr 指向第一行文本,每一次自增运算都将使 *lineptr 指向下一个行文本。

还要注意第 38 行、71 行、90 行、99 行、118 行函数的形式参数中都是形如:

char *v[]

表明传递的参数是一个指针数组。

最后,由于 getline 函数、 strcmp 函数以及 strcpy 函数会和标准库的中库函数冲突,因此这里均加了“my_ ”前缀以示区分。

2. 指向指针的指针

指向指针的指针变量 是一个指针变量指向另一个指针变量。其声明格式是:

类型标识符 **指针变量名

如 int **ppa; char **ppc;

通过一个简单的例子来理解什么是指向指针的指针。

#include <stdio.h>

int main()
{
        int a = 8;
        int *pa = &a; 
        int **ppa = &pa;

        printf("a     = 0x%x\n", a); 
        printf("&a    = 0x%x\n", &a);
        printf("pa    = 0x%x\n", pa);
        printf("*pa   = 0x%x\n", *pa);
        printf("&pa   = 0x%x\n", &pa);
        printf("ppa   = 0x%x\n", ppa);
        printf("&ppa  = 0x%x\n", &ppa);
        printf("*ppa  = 0x%x\n", *ppa);
        printf("**ppa = 0x%x\n", **ppa);

        return 0;
}

在我的电脑上运行结果是:(在其他电脑上运行的结果不可能完全一样,但其中的逻辑是一样的)

a     = 0x8
&a    = 0xdd54e7fc
pa    = 0xdd54e7fc
*pa   = 0x8
&pa   = 0xdd54e7f0
ppa   = 0xdd54e7f0
&ppa  = 0xdd54e7e8
*ppa  = 0xdd54e7fc
**ppa = 0x8

根据结果我们可以画出内存分布及指针的指向关系:

C语言_指向指针的指针

很形象地说明了三者之间的关系。另外,

  1. 直接通过变量名访问变量值,是直接访问,如直接使用 a。
  2. 通过指针访问它所指向的变量的值,是间接访问,也叫单级间址,如 *pa。
  3. 通过指向指针的指针访问变量值,是间接的间接访问,也叫二级间址,如 **ppa。

不过要注意:通过 **ppa 访问 a 是合法的,但 int **ppa = &&a 的定义是非法的,&& 并不能取地址的地址。

Leave A Reply