chapter4.html

c语言编程-c语言作者的书。英文原版。非常好。

without supplying all the preceding values as well.
<p>
Character arrays are a special case of initialization; a string may be used
instead of the braces and commas notation:
<pre>
   char pattern = "ould";
</pre>
is a shorthand for the longer but equivalent
<pre>
   char pattern[] = { 'o', 'u', 'l', 'd', '\0' };
</pre>
In this case, the array size is five (four characters plus the terminating
<tt>'\0'</tt>).

<h2><a name="s4.10">4.10 Recursion</a></h2>
C functions may be used recursively; that is, a function may call itself
either directly or indirectly. Consider printing a number as a character
string. As we mentioned before, the digits are generated in the wrong order:
low-order digits are available before high-order digits, but they have to be
printed the other way around.
<p>
There are two solutions to this problem. On is to store the digits in an
array as they are generated, then print them in the reverse order, as we did
with <tt>itoa</tt> in <a href="chapter3.html#s3.6">section 3.6</a>. The
alternative is a recursive solution, in which <tt>printd</tt> first calls
itself to cope with any leading digits, then prints the trailing digit.
Again, this version can fail on the largest negative number.
<pre>
   #include &lt;stdio.h&gt;

   /* printd:  print n in decimal */
   void printd(int n)
   {
       if (n &lt; 0) {
           putchar('-');
           n = -n;
       }
       if (n / 10)
           printd(n / 10);
       putchar(n % 10 + '0');
   }
</pre>
When a function calls itself recursively, each invocation gets a fresh set of
all the automatic variables, independent of the previous set. This in <tt>
printd(123)</tt> the first <tt>printd</tt> receives the argument <tt>n = 123</tt>.
It passes <tt>12</tt> to a second <tt>printd</tt>, which in turn passes
<tt>1</tt> to a third. The third-level <tt>printd</tt> prints <tt>1</tt>, then
returns to the second level. That <tt>printd</tt> prints <tt>2</tt>, then
returns to the first level. That one prints <tt>3</tt> and terminates.
<p>
Another good example of recursion is quicksort, a sorting algorithm developed
by C.A.R. Hoare in 1962. Given an array, one element is chosen and the others
partitioned in two subsets - those less than the partition element and those
greater than or equal to it. The same process is then applied recursively to
the two subsets. When a subset has fewer than two elements, it doesn't need
any sorting; this stops the recursion.
<p>
Our version of quicksort is not the fastest possible, but it's one of the
simplest. We use the middle element of each subarray for partitioning.
<pre>
   /* qsort:  sort v[left]...v[right] into increasing order */
   void qsort(int v[], int left, int right)
   {
       int i, last;
       void swap(int v[], int i, int j);

       if (left &gt;= right) /* do nothing if array contains */
           return;        /* fewer than two elements */
       swap(v, left, (left + right)/2); /* move partition elem */
       last = left;                     /* to v[0] */
       for (i = left + 1; i &lt;= right; i++)  /* partition */
           if (v[i] &lt; v[left])
               swap(v, ++last, i);
       swap(v, left, last);            /* restore partition  elem */
       qsort(v, left, last-1);
       qsort(v, last+1, right);
   }
</pre>
We moved the swapping operation into a separate function <tt>swap</tt> because it
occurs three times in <tt>qsort</tt>.
<pre>
   /* swap:  interchange v[i] and v[j] */
   void swap(int v[], int i, int j)
   {
       int temp;

       temp = v[i];
       v[i] = v[j];
       v[j] = temp;
   }
</pre>
The standard library includes a version of <tt>qsort</tt> that can sort objects of
any type.
<p>
Recursion may provide no saving in storage, since somewhere a stack of the
values being processed must be maintained. Nor will it be faster. But
recursive code is more compact, and often much easier to write and understand
than the non-recursive equivalent. Recursion is especially convenient for
recursively defined data structures like trees, we will see a nice example
in <a href="chapter6.html#s6.6">Section 6.6</a>.
<p>
<strong>Exercise 4-12.</strong> Adapt the ideas of <tt>printd</tt> to write a recursive
version of <tt>itoa</tt>; that is, convert an integer into a string by calling
a recursive routine.
<p>
<strong>Exercise 4-13.</strong> Write a recursive version of the function <tt>reverse(s)</tt>,
which reverses the string <tt>s</tt> in place.

<h2><a name="s4.11">4.11 The C Preprocessor</a></h2>
C provides certain language facilities by means of a preprocessor, which is
conceptionally a separate first step in compilation. The two most frequently
used features are <tt>#include</tt>, to include the contents of a file during
compilation, and <tt>#define</tt>, to replace a token by an arbitrary sequence of
characters. Other features described in this section include conditional
compilation and macros with arguments.

<h3><a name="s4.11.1">4.11.1 File Inclusion</a></h3>
File inclusion makes it easy to handle collections of <tt>#define</tt>s and
declarations (among other things). Any source line of the form
<pre>
   #include "<em>filename</em>"
</pre>
or
<pre>
   #include &lt;<em>filename</em>&gt;
</pre>
is replaced by the contents of the file <em>filename</em>. If the <em>filename</em>
is quoted, searching for the file typically begins where the source program
was found; if it is not found there, or if the name is enclosed in &lt; and
&gt;, searching follows an implementation-defined rule to find the file. An
included file may itself contain <tt>#include</tt> lines.
<p>
There are often several <tt>#include</tt> lines at the beginning of a source
file, to include common <tt>#define</tt> statements and <tt>extern</tt> declarations,
or to access the function prototype declarations for library functions from
headers like <tt>&lt;stdio.h&gt;</tt>. (Strictly speaking, these need not be files;
the details of how headers are accessed are implementation-dependent.)
<p>
<tt>#include</tt> is the preferred way to tie the declarations together for a
large program. It guarantees that all the source files will be supplied with
the same definitions and variable declarations, and thus eliminates a
particularly nasty kind of bug. Naturally, when an included file is changed,
all files that depend on it must be recompiled.

<h3><a name="s4.11.2">4.11.2 Macro Substitution</a></h3>
A definition has the form
<pre>
   #define <em>name replacement text</em>
</pre>
It calls for a macro substitution of the simplest kind - subsequent
occurrences of the token <tt>name</tt> will be replaced by the
<em>replacement text</em>. The name in a <tt>#define</tt> has the same form
as a variable name; the replacement text is arbitrary. Normally the
replacement text is the rest of the line, but a long definition may be
continued onto several lines by placing a <tt>\</tt> at the end of each line
to be continued. The scope of a name defined with <tt>#define</tt> is from
its point of definition to the end of the source file being compiled. A
definition may use previous definitions. Substitutions are made only for
tokens, and do not take place within quoted strings. For example, if
<tt>YES</tt> is a defined name, there would be no substitution in
<tt>printf("YES")</tt> or in <tt>YESMAN</tt>.
<p>
Any name may be defined with any replacement text. For example
<pre>
   #define  forever  for (;;)    /* infinite loop */
</pre>
defines a new word, <tt>forever</tt>, for an infinite loop.
<p>
It is also possible to define macros with arguments, so the replacement text
can be different for different calls of the macro. As an example, define a
macro called <tt>max</tt>:
<pre>
   #define  max(A, B)  ((A) &gt; (B) ? (A) : (B))
</pre>
Although it looks like a function call, a use of <tt>max</tt> expands into
in-line code. Each occurrence of a formal parameter (here <tt>A</tt> or <tt>B</tt>)
will be replaced by the corresponding actual argument. Thus the line
<pre>
   x = max(p+q, r+s);
</pre>
will be replaced by the line
<pre>
   x = ((p+q) > (r+s) ? (p+q) : (r+s));
</pre>
So long as the arguments are treated consistently, this macro will serve for
any data type; there is no need for different kinds of <tt>max</tt> for different
data types, as there would be with functions.
<p>
If you examine the expansion of <tt>max</tt>, you will notice some pitfalls. The
expressions are evaluated twice; this is bad if they involve side effects like
increment operators or input and output. For instance
<pre>
   max(i++, j++)  /* WRONG */
</pre>
will increment the larger twice. Some care also has to be taken with
parentheses to make sure the order of evaluation is preserved; consider what
happens when the macro
<pre>
   #define square(x)  x * x  /* WRONG */
</pre>
is invoked as <tt>square(z+1)</tt>.
<p>
Nonetheless, macros are valuable. One practical example comes from
<tt>&lt;stdio.h&gt</tt>, in which <tt>getchar</tt> and <tt>putchar</tt> are
often defined as macros to avoid the run-time overhead of a function call per
character processed. The functions in <tt>&lt;ctype.h&gt;</tt> are also usually
implemented as macros.
<p>
Names may be undefined with <tt>#undef</tt>, usually to ensure that a routine is
really a function, not a macro:
<pre>
   #undef getchar

   int getchar(void) { ... }
</pre>
Formal parameters are not replaced within quoted strings. If, however, a
parameter name is preceded by a <tt>#</tt> in the replacement text, the
combination will be expanded into a quoted string with the parameter
replaced by the actual argument. This can be combined with string concatenation
to make, for example, a debugging print macro:
<pre>
   #define  dprint(expr)   printf(#expr " = %g\n", expr)
</pre>
When this is invoked, as in
<pre>
   dprint(x/y)
</pre>
the macro is expanded into
<pre>
   printf("x/y" " = &g\n", x/y);
</pre>
and the strings are concatenated, so the effect is
<pre>
   printf("x/y = &g\n", x/y);
</pre>
Within the actual argument, each <tt>"</tt> is replaced by <tt>\"</tt> and each
<tt>\</tt> by <tt>\\</tt>, so the result is a legal string constant.
<p>
The preprocessor operator <tt>##</tt> provides a way to concatenate actual
arguments during macro expansion. If a parameter in the replacement text is
adjacent to a <tt>##</tt>, the parameter is replaced by the actual argument, the
<tt>##</tt> and surrounding white space are removed, and the result is
re-scanned. For example, the macro <tt>paste</tt> concatenates its two arguments:
<pre>
   #define  paste(front, back)  front ## back
</pre>
so <tt>paste(name, 1)</tt> creates the token <tt>name1</tt>.
<p>
The rules for nested uses of <tt>##</tt> are arcane; further details may be
found in <a href="appa.html">Appendix A</a>.
<p>
<strong>Exercise 4-14.</strong> Define a macro <tt>swap(t,x,y)</tt> that
interchanges two arguments of type <tt>t</tt>. (Block structure will help.)

<h3><a name="s4.11.3">4.11.3 Conditional Inclusion</a></h3>
It is possible to control preprocessing itself with  conditional statements
that are evaluated during preprocessing. This provides a way to include code
selectively, depending on the value of conditions evaluated during compilation.
<p>
The <tt>#if</tt> line evaluates a constant integer expression (which may not
include <tt>sizeof</tt>, casts, or <tt>enum</tt> constants). If the expression is
non-zero, subsequent lines until an <tt>#endif</tt> or <tt>#elif</tt> or
<tt>#else</tt> are included. (The preprocessor statement <tt>#elif</tt> is like
<tt>else-if</tt>.) The expression <tt>defined</tt>(<em>name</em>) in a
<tt>#if</tt> is 1 if the <em>name</em> has been defined, and 0 otherwise.
<p>
For example, to make sure that the contents of a file <tt>hdr.h</tt> are included
only once, the contents of the file are surrounded with a conditional like
this:
<pre>
   #if !defined(HDR)
   #define HDR

   /* contents of hdr.h go here */

   #endif
</pre>
The first inclusion of <tt>hdr.h</tt> defines the name <tt>HDR</tt>; subsequent
inclusions will find the name defined and skip down to the <tt>#endif</tt>. A
similar style can be used to avoid including files multiple times. If this
style is used consistently, then each header can itself include any other
headers on which it depends, without the user of the header having to deal with
the interdependence.
<p>
This sequence tests the name <tt>SYSTEM</tt> to decide which version of a header
to include:
<pre>
   #if SYSTEM == SYSV
       #define HDR "sysv.h"
   #elif SYSTEM == BSD
       #define HDR "bsd.h"
   #elif SYSTEM == MSDOS
       #define HDR "msdos.h"
   #else
       #define HDR "default.h"
   #endif
   #include HDR
</pre>
The <tt>#ifdef</tt> and <tt>#ifndef</tt> lines are specialized forms that test
whether a name is defined. The first example of <tt>#if</tt> above could have
been written
<pre>
   #ifndef HDR
   #define HDR

   /* contents of hdr.h go here */

   #endif
</pre>
<p>
<hr>
<p align="center">
<a href="chapter3.html">Back to Chapter 3</a>&nbsp;--&nbsp;
<a href="kandr.html">Index</a>&nbsp;--&nbsp;
<a href="chapter5.html">Chapter 5</a>
<p>
<hr>

</body>
</html>