chapter5.html

Kernighan and Ritchie - The C Programming Language c程序设计语言（第二版）称作是C语言学习的圣经

such cases, breaking them into two or three steps will be more intuitive.
<p>
<strong>Exercise 5-10.</strong> Write the program <tt>expr</tt>, which
evaluates a reverse Polish expression from the command line, where each
operator or operand is a separate argument. For example,
<pre>
   expr 2 3 4 + *
</pre>
evaluates 2 * (3+4).
<p>
<strong>Exercise 5-11.</strong> Modify the program <tt>entab</tt> and
<tt>detab</tt> (written as exercises in <a href="chapter1.html">Chapter 1</a>)
to accept a list of tab stops as arguments. Use the default tab settings if
there are no arguments.
<p>
<strong>Exercise 5-12.</strong> Extend <tt>entab</tt> and <tt>detab</tt> to
accept the shorthand
<pre>
   entab <em>-m +n</em>
</pre>
to mean tab stops every <em>n</em> columns, starting at column <em>m</em>. Choose
convenient (for the user) default behavior.
<p>
<strong>Exercise 5-13.</strong> Write the program <tt>tail</tt>, which prints
the last <em>n</em> lines of its input. By default, <em>n</em> is set to 10,
let us say, but it can be changed by an optional argument so that
<pre>
   tail <em>-n</em>
</pre>
prints the last <em>n</em> lines. The program should behave rationally no matter
how unreasonable the input or the value of <em>n</em>. Write the program so it
makes the best use of available storage; lines should be stored as in the
sorting program of <a href="chapter5.html#s5.6">Section 5.6</a>, not in a
two-dimensional array of fixed size.

<h2><a name="s5.11">5.11 Pointers to Functions</a></h2>
In C, a function itself is not a variable, but it is possible to define
pointers to functions, which can be assigned, placed in arrays, passed to
functions, returned by functions, and so on. We will illustrate this by
modifying the sorting procedure written earlier in this chapter so that if the
optional argument <tt>-n</tt> is given, it will sort the input lines numerically
instead of lexicographically.
<p>
A sort often consists of three parts - a comparison that determines the
ordering of any pair of objects, an exchange that reverses their order, and a
sorting algorithm that makes comparisons and exchanges until the objects are in
order. The sorting algorithm is independent of the comparison and exchange
operations, so by passing different comparison and exchange functions to it, we
can arrange to sort by different criteria. This is the approach taken in our
new sort.
<p>
Lexicographic comparison of two lines is done by <tt>strcmp</tt>, as before; we
will also need a routine <tt>numcmp</tt> that compares two lines on the basis of
numeric value and returns the same kind of condition indication as <tt>strcmp</tt>
does. These functions are declared ahead of <tt>main</tt> and a pointer to the
appropriate one is passed to <tt>qsort</tt>. We have skimped on error processing
for arguments, so as to concentrate on the main issues.
<pre>
   #include &lt;stdio.h&gt;
   #include &lt;string.h&gt;

   #define MAXLINES 5000     /* max #lines to be sorted */
   char *lineptr[MAXLINES];  /* pointers to text lines */

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

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

   /* sort input lines */
   main(int argc, char *argv[])
   {
       int nlines;        /* number of input lines read */
       int numeric = 0;   /* 1 if numeric sort */

       if (argc &gt; 1 && strcmp(argv[1], "-n") == 0)
           numeric = 1;
       if ((nlines = readlines(lineptr, MAXLINES)) &gt;= 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;
       }
   }
</pre>
In the call to <tt>qsort</tt>, <tt>strcmp</tt> and <tt>numcmp</tt> are
addresses of functions. Since they are known to be functions, the
<tt>&amp;</tt> is not necessary, in the same way that it is not needed before
an array name.
<p>
We have written <tt>qsort</tt> so it can process any data type, not just
character strings. As indicated by the function prototype, <tt>qsort</tt>
expects an array of pointers, two integers, and a function with two pointer
arguments. The generic pointer type <tt>void *</tt> is used for the pointer
arguments. Any pointer can be cast to <tt>void *</tt> and back again without
loss of information, so we can call <tt>qsort</tt> by casting arguments to
<tt>void *</tt>. The elaborate cast of the function argument casts the
arguments of the comparison function. These will generally have no effect on
actual representation, but assure the compiler that all is well.
<pre>
   /* qsort:  sort v[left]...v[right] into increasing order */
   void qsort(void *v[], int left, int right,
              int (*comp)(void *, void *))
   {
       int i, last;

       void swap(void *v[], int, int);

       if (left &gt;= right)    /* do  nothing if array contains */
           return;           /* fewer than two elements */
       swap(v, left, (left + right)/2);
       last = left;
       for (i = left+1; i &lt;= right;  i++)
           if ((*comp)(v[i], v[left]) &lt; 0)
               swap(v, ++last, i);
       swap(v, left, last);
       qsort(v, left, last-1, comp);
       qsort(v, last+1, right, comp);
   }
</pre>
The declarations should be studied with some care. The fourth parameter of
<tt>qsort</tt> is
<pre>
   int (*comp)(void *, void *)
</pre>
which says that <tt>comp</tt> is a pointer to a function that has two
<tt>void *</tt> arguments and returns an <tt>int</tt>.
<p>
The use of <tt>comp</tt> in the line
<pre>
   if ((*comp)(v[i], v[left]) &lt; 0)
</pre>
is consistent with the declaration: <tt>comp</tt> is a pointer to a function,
<tt>*comp</tt> is the function, and
<pre>
   (*comp)(v[i], v[left])
</pre>
is the call to it. The parentheses are needed so the components are correctly
associated; without them,
<pre>
   int *comp(void *, void *)    /* WRONG */
</pre>
says that <tt>comp</tt> is a function returning a pointer to an <tt>int</tt>,
which is very different.
<p>
We have already shown <tt>strcmp</tt>, which compares two strings. Here is
<tt>numcmp</tt>, which compares two strings on a leading numeric value,
computed by calling <tt>atof</tt>:
<pre>
   #include &lt;stdlib.h&gt;

   /* numcmp:  compare s1 and s2 numerically */
   int numcmp(char *s1, char *s2)
   {
       double v1, v2;

       v1 = atof(s1);
       v2 = atof(s2);
       if (v1 &lt; v2)
           return -1;
       else if (v1 &gt; v2)
           return 1;
       else
           return 0;
   }
</pre>
The <tt>swap</tt> function, which exchanges two pointers, is identical to what we
presented earlier in the chapter, except that the declarations are changed to
<tt>void *</tt>.
<pre>
   void swap(void *v[],  int i, int j;)
   {
       void *temp;

       temp = v[i];
       v[i] = v[j];
       v[j] = temp;
   }
</pre>
A variety of other options can be added to the sorting program; some make
challenging exercises.
<p>
<strong>Exercise 5-14.</strong> Modify the sort program to handle a <tt>-r</tt>
flag, which indicates sorting in reverse (decreasing) order. Be sure that
<tt>-r</tt> works with <tt>-n</tt>.
<p>
<strong>Exercise 5-15.</strong> Add the option <tt>-f</tt> to fold upper and lower case
together, so that case distinctions are not made during sorting; for example,
<tt>a</tt> and <tt>A</tt> compare equal.
<p>
<strong>Exercise 5-16.</strong> Add the <tt>-d</tt> (``directory order'') option, which makes
comparisons only on letters, numbers and blanks. Make sure it works in
conjunction with  <tt>-f</tt>.
<p>
<strong>Exercise 5-17.</strong> Add a field-searching capability, so sorting may bee done
on fields within lines, each field sorted according to an independent set of
options. (The index for this book was sorted with <tt>-df</tt> for the index
category and <tt>-n</tt> for the page numbers.)

<h2><a name="s5.12">5.12 Complicated Declarations</a></h2>
C is sometimes castigated for the syntax of its declarations, particularly ones
that involve pointers to functions. The syntax is an attempt to make the
declaration and the use agree; it works well for simple cases, but it can be
confusing for the harder ones, because declarations cannot be read left to
right, and because parentheses are over-used. The difference between
<pre>
   int *f();       /* f: function returning pointer to int */
</pre>
and
<pre>
   int (*pf)();    /* pf: pointer to function returning int */ 
</pre>
illustrates the problem: <tt>*</tt> is a prefix operator and it has lower
precedence than <tt>()</tt>, so parentheses are necessary to force the proper
association.
<p>
Although truly complicated declarations rarely arise in practice, it is
important to know how to understand them, and, if necessary, how to create
them. One good way to synthesize declarations is in small steps with
<tt>typedef</tt>, which is discussed in <a href="chapter6.html#s6.7">Section 6.7</a>.
As an alternative, in this section we will present a pair of programs that
convert from valid C to a word description and back again. The word
description reads left to right.
<p>
The first, <tt>dcl</tt>, is the more complex. It converts a C declaration into a
word description, as in these examples:
<pre>
char **argv
    argv:  pointer to char
int (*daytab)[13]
    daytab:  pointer to array[13] of int
int *daytab[13]
    daytab:  array[13] of pointer to int
void *comp()
    comp: function returning pointer to void
void (*comp)()
    comp: pointer to function returning void
char (*(*x())[])()
    x: function returning pointer to array[] of
    pointer to function returning char
char (*(*x[3])())[5]
    x: array[3] of pointer to function returning
    pointer to array[5] of char
</pre>
<tt>dcl</tt> is based on the grammar that specifies a declarator, which is
spelled out precisely in <a href="appa.html#sa.8.5">Appendix A, Section 8.5</a>;
this is a simplified form:
<pre>
<em>
dcl:       optional *'s direct-dcl
direct-dcl name
                 (dcl)
                 direct-dcl()
                 direct-dcl[optional size]
</em>
</pre>
In words, a <em>dcl</em> is a <em>direct-dcl</em>, perhaps preceded by *'s. A
<em>direct-dcl</em> is a name, or a parenthesized <em>dcl</em>, or a <em>direct-dcl</em>
followed by parentheses, or a <em>direct-dcl</em> followed by brackets with an
optional size.
<p>
This grammar can be used to parse functions. For instance, consider this
declarator:
<pre>
   (*pfa[])()
</pre>
<tt>pfa</tt> will be identified as a <em>name</em> and thus as a <em>direct-dcl</em>.
Then <tt>pfa[]</tt> is also a <em>direct-dcl</em>. Then <tt>*pfa[]</tt> is recognized
as a <em>dcl</em>, so <tt>(*pfa[])</tt> is a <em>direct-dcl</em>. Then <tt>(*pfa[])()</tt>
is a <em>direct-dcl</em> and thus a <em>dcl</em>. We can also illustrate the
parse with a tree like this (where <em>direct-dcl</em> has been abbreviated to
<em>dir-dcl</em>):
<p align="center">
<img src="pic512.gif">
<p>
The heart of the <tt>dcl</tt> program is a pair of functions, <tt>dcl</tt> and
<tt>dirdcl</tt>, that parse a declaration according to this grammar. Because
the grammar is recursively defined, the functions call each other recursively
as they recognize pieces of a declaration; the program is called a
recursive-descent parser.
<pre>
   /* dcl:  parse a declarator */
   void dcl(void)
   {
       int ns;

       for (ns = 0; gettoken() == '*'; ) /* count *'s */
           ns++;
       dirdcl();
       while (ns-- &gt; 0)
           strcat(out, " pointer to");
   }

   /* dirdcl:  parse a direct declarator */
   void dirdcl(void)
   {
       int type;

       if (tokentype == '(') {         /* ( dcl ) */
           dcl();
           if (tokentype != ')')
               printf("error: missing )\n");
       } else if (tokentype == NAME)  /* variable name */
           strcpy(name, token);
       else
           printf("error: expected name or (dcl)\n");
       while ((type=gettoken()) == PARENS || type == BRACKETS)
           if (type == PARENS)
               strcat(out, " function returning");
           else {
               strcat(out, " array");
               strcat(out, token);
               strcat(out, " of");
           }
   }
</pre>
Since the programs are intended to be illustrative, not bullet-proof, there
are significant restrictions on <tt>dcl</tt>. It can only handle a simple data
type line <tt>char</tt> or <tt>int</tt>. It does not handle argument types in
functi