chapter5.html

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

   void strcpy(char *s, char *t)
   {
       while ((*s++ = *t++) != '\0')
           ;
   }
</pre>
This moves the increment of <tt>s</tt> and <tt>t</tt> into the test part of the
loop. The value of <tt>*t++</tt> is the character that <tt>t</tt> pointed to before
<tt>t</tt> was incremented; the postfix <tt>++</tt> doesn't change <tt>t</tt> until
after this character has been fetched. In the same way, the character is
stored into the old <tt>s</tt> position before <tt>s</tt> is incremented. This
character is also the value that is compared against <tt>'\0'</tt> to control
the loop. The net effect is that characters are copied from <tt>t</tt> to
<tt> s</tt>, up and including the terminating <tt>'\0'</tt>.
<p>
As the final abbreviation, observe that a comparison against <tt>'\0'</tt> is
redundant, since the question is merely whether the expression is zero. So
the function would likely be written as
<pre>
   /* strcpy:  copy t to s; pointer version 3 */
   void strcpy(char *s, char *t)
   {
       while (*s++ = *t++)
           ;
   }
</pre>
Although this may seem cryptic at first sight, the notational convenience is
considerable, and the idiom should be mastered, because you will see it
frequently in C programs.
<p>
The <tt>strcpy</tt> in the standard library (<tt>&lt;string.h&gt;</tt>) returns
the target string as its function value.
<p>
The second routine that we will examine is <tt>strcmp(s,t)</tt>,  which compares
the character strings <tt>s</tt> and <tt>t</tt>, and returns negative, zero or
positive if <tt>s</tt> is lexicographically less than, equal to, or greater than
<tt>t</tt>. The value is obtained by subtracting the characters at the first
position where <tt>s</tt> and <tt>t</tt> disagree.
<pre>
   /* strcmp:  return &lt;0 if s&lt;t, 0 if s==t, &gt;0 if s&gt;t */
   int strcmp(char *s, char *t)
   {
       int i;

       for (i = 0; s[i] == t[i]; i++)
           if (s[i] == '\0')
               return 0;
       return s[i] - t[i];
   }
</pre>
The pointer version of <tt>strcmp</tt>:
<pre>
   /* strcmp:  return &lt;0 if s&lt;t, 0 if s==t, &gt;0 if s&gt;t */
   int strcmp(char *s, char *t)
   {
       for ( ; *s == *t; s++, t++)
           if (*s == '\0')
               return 0;
       return *s - *t;
   }
</pre>
Since <tt>++</tt> and <tt>--</tt> are either prefix or postfix operators, other
combinations of <tt>*</tt> and <tt>++</tt> and <tt>--</tt> occur, although less
frequently. For example,
<pre>
   *--p
</pre>
decrements <tt>p</tt> before fetching the character that <tt>p</tt> points to.
In fact, the pair of expressions
<pre>
   *p++ = val;  /* push val onto stack */
   val = *--p;  /* pop top of stack into val */
</pre>
are the standard idiom for pushing and popping a stack; see
<a href="chapter4.html#s4.3">Section 4.3</a>.
<p>
The header <tt>&lt;string.h&gt;</tt> contains declarations for the functions
mentioned in this section, plus a variety of other string-handling functions
from the standard library.
<p>
<strong>Exercise 5-3.</strong> Write a pointer version of the function
<tt>strcat</tt> that we showed in <a href="chapter2.html">Chapter 2</a>:
<tt>strcat(s,t)</tt> copies the string <tt>t</tt> to the end of <tt>s</tt>.
<p>
<strong>Exercise 5-4.</strong> Write the function <tt>strend(s,t)</tt>, which
returns 1 if the string <tt>t</tt> occurs at the end of the string <tt>s</tt>,
and zero otherwise.
<p>
<strong>Exercise 5-5.</strong> Write versions of the library functions
<tt>strncpy</tt>, <tt>strncat</tt>, and <tt>strncmp</tt>, which operate on at
most the first <tt>n</tt> characters of their argument strings. For example,
<tt>strncpy(s,t,n)</tt> copies at most <tt>n</tt> characters of <tt>t</tt> to
<tt>s</tt>. Full descriptions are in <a href="appb.html">Appendix B</a>.
<p>
<strong>Exercise 5-6.</strong> Rewrite appropriate programs from earlier
chapters and exercises with pointers instead of array indexing. Good
possibilities include <tt>getline</tt> (<a href="chapter1.html">Chapters
1</a> and <a href="chapter4.html">4</a>), <tt>atoi</tt>, <tt>itoa</tt>, and
their variants (<a href="chapter2.html">Chapters 2</a>, <a
href="chapter3.html">3</a>, and <a href="chapter4.html">4</a>),
<tt>reverse</tt> (<a href="chapter3.html">Chapter 3</a>), and
<tt>strindex</tt> and <tt>getop</tt> (<a href="chapter4.html">Chapter 4</a>).

<h2><a name="s5.6">5.6 Pointer Arrays; Pointers to Pointers</a></h2>
Since pointers are variables themselves, they can be stored in arrays just as
other variables can. Let us illustrate by writing a program that will sort a
set of text lines into alphabetic order, a stripped-down version of the UNIX
program <tt>sort</tt>.
<p>
In <a href="chapter3.html">Chapter 3</a>, we presented a Shell sort function
that would sort an array of integers, and in <a href="chapter4.html">Chapter
4</a> we improved on it with a quicksort. The same algorithms will work,
except that now we have to deal with lines of text, which are of different
lengths, and which, unlike integers, can't be compared or moved in a single
operation. We need a data representation that will cope efficiently and
conveniently with variable-length text lines.
<p>
This is where the array of pointers enters. If the lines to be sorted are
stored end-to-end in one long character array, then each line can be accessed
by a pointer to its first character. The pointers themselves can bee stored
in an array. Two lines can be compared by passing their pointers to
<tt>strcmp</tt>. When two out-of-order lines have to be exchanged, the
pointers in the pointer array are exchanged, not the text lines themselves.
<p align="center">
<img src="pic58.gif">
<p>
This eliminates the twin problems of complicated storage management and high
overhead that would go with moving the lines themselves.
<p>
The sorting process has three steps:
<p>
<em>
&nbsp;&nbsp;read all the lines of input<br>
&nbsp;&nbsp;sort them<br>
&nbsp;&nbsp;print them in order
</em>
<p>
As usual, it's best to divide the program into functions that match this
natural division, with the main routine controlling the other functions. Let
us defer the sorting step for a moment, and concentrate on the data structure
and the input and output.
<p>
The input routine has to collect and save the characters of each line, and
build an array of pointers to the lines. It will also have to count the
number of input lines, since that information is needed for sorting and
printing. Since the input function can only cope with a finite number of
input lines, it can return some illegal count like <tt>-1</tt> if too much
input is presented.
<p>
The output routine only has to print the lines in the order in which they
appear in the array of pointers.
<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(char *lineptr[], int left, int right);

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

       if ((nlines = readlines(lineptr, MAXLINES)) &gt;= 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  /* max length of any input line */
   int getline(char *, int);
   char *alloc(int);

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

       nlines = 0;
       while ((len = getline(line, MAXLEN)) &gt; 0)
           if (nlines &gt;= maxlines || p = alloc(len) == NULL)
               return -1;
           else {
               line[len-1] = '\0';  /* delete newline */
               strcpy(p, line);
               lineptr[nlines++] = p;
           }
       return nlines;
   }

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

       for (i = 0; i &lt; nlines; i++)
           printf("%s\n", lineptr[i]);
   }
</pre>
The function <tt>getline</tt> is from
<a href="chapter1.html#s1.9">Section 1.9</a>.
<p>
The main new thing is the declaration for <tt>lineptr</tt>:
<pre>
   char *lineptr[MAXLINES]
</pre>
says that <tt>lineptr</tt> is an array of <tt>MAXLINES</tt> elements, each
element of which is a pointer to a <tt>char</tt>. That is,
<tt>lineptr[i]</tt> is a character pointer, and <tt>*lineptr[i]</tt> is the
character it points to, the first character of the <tt>i</tt>-th saved text
line.
<p>
Since <tt>lineptr</tt> is itself the name of an array, it can be treated as a
pointer in the same manner as in our earlier examples, and <tt>writelines</tt>
can be written instead as
<pre>
   /* writelines:  write output lines */
   void writelines(char *lineptr[], int nlines)
   {
       while (nlines-- &gt; 0)
           printf("%s\n", *lineptr++);
   }
</pre>
Initially, <tt>*lineptr</tt> points to the first line; each element advances
it to the next line pointer while <tt>nlines</tt> is counted down.
<p>
With input and output under control, we can proceed to sorting. The quicksort
from <a href="chapter4.html">Chapter 4</a> needs minor changes: the
declarations have to be modified, and the comparison operation must be done
by calling <tt>strcmp</tt>. The algorithm remains the same, which gives us
some confidence that it will still work.
<pre>
   /* qsort:  sort v[left]...v[right] into increasing order */
   void qsort(char *v[], int left, int right)
   {
       int i, last;
       void swap(char *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);
       last = left;
       for (i = left+1; i &lt;= right; i++)
           if (strcmp(v[i], v[left]) &lt; 0)
               swap(v, ++last, i);
       swap(v, left, last);
       qsort(v, left, last-1);
       qsort(v, last+1, right);
   }
</pre>
Similarly, the swap routine needs only trivial changes:
<pre>
   /* 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;
   }
</pre>
Since any individual element of <tt>v</tt> (alias <tt>lineptr</tt>) is a
character pointer, <tt>temp</tt> must be also, so one can be copied to the
other.
<p>
<strong>Exercise 5-7.</strong> Rewrite <tt>readlines</tt> to store lines in
an array supplied by <tt>main</tt>, rather than calling <tt>alloc</tt> to
maintain storage. How much faster is the program?

<h2><a name="s5.7">5.7 Multi-dimensional Arrays</a></h2>
C provides rectangular multi-dimensional arrays, although in practice they
are much less used than arrays of pointers. In this section, we will show
some of their properties.
<p>
Consider the problem of date conversion, from day of the month to day of the
year and vice versa. For example, March 1 is the 60th day of a non-leap year,
and the 61st day of a leap year. Let us define two functions to do the
conversions: <tt>day_of_year</tt> converts the month and day into the day of the
year, and <tt>month_day</tt> converts the day of the year into the month and
day. Since this latter function computes two values, the month and day
arguments will be pointers:
<pre>
   month_day(1988, 60, &m, &d)
</pre>
sets <tt>m</tt> to 2 and <tt>d</tt> to 29 (February 29th).
<p>
These functions both need the same information, a table of the number of days
in each month (``thirty days hath September ...''). Since the number of days
per month differs for leap years and non-leap years, it's easier to separate
them into two rows of a two-dimensional array than to keep track of what
happens to February during computation. The array and the functions for
performing the transformations are as follows:
<pre>
   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:  set day of year from month & day */
   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 &lt; month; i++)
           day += daytab[leap][i];
       return day;
   }

   /* month_day:  set month, day from day of year */
   void month_day(int year, int yearday, int *pmonth, int *pday)
   {
       int i, leap;

       leap = year%4 == 0 && year%100 != 0 || year%400 == 0;
       for (i = 1; yearday &gt; daytab[leap][i]; i++)
           yearday -= daytab[leap][i];
       *pmonth = i;