入门
类型、运算符和表达式
控制流
函数
指针与数组
结构

1. 入门

1.1. 第一个C语言程序

写一个程序，在屏幕上输出hello, world

   1 #include <stdio.h>
   2 
   3 main()
   4 {
   5     printf("hello, world\n");
   6 }

1.2. 摄氏华氏温度对照表

使用公式℃=(5/9)(℉-32) 打印华氏温度与摄氏温度对照表

   1 #include <stdio.h>
   2 
   3 /* print Fahrenheit-Celsius table
   4    for fahr = 0, 20, ..., 300 */
   5 main()
   6 {
   7     int fahr, celsius;
   8     int lower, upper, step;
   9 
  10     lower = 0;      /* lower limit of temperature scale */
  11     upper = 300;    /* upper limit */
  12     step = 20;      /* step size */
  13 
  14     fahr = lower;
  15     while (fahr <= upper) {
  16         celsius = 5 * (fahr-32) / 9;
  17         printf("%d\t%d\n", fahr, celsius);
  18         fahr = fahr + step;
  19     }
  20 }

1.3. 温度对照表第2版

上述的温度转换程序存在两个问题。比较简单的问题是，由于输出的数不是右对齐的，所以输出的结果不是很美观。另一个较为严重的问题是，由于我们使用的是整型算术运算，因此经计算得到的摄氏温度值不太精确，例如，与0℉对应的精确的摄氏温度应该为-17.8℃，而不是-17℃。

   1 #include <stdio.h>
   2 
   3 /* print Fahrenheit-Celsius table
   4    for fahr = 0, 20, ..., 300; floating-point version */
   5 main()
   6 {
   7     float fahr, celsius;
   8     float lower, upper, step;
   9 
  10     lower = 0;      /* lower limit of temperatuire scale */
  11     upper = 300;    /* upper limit */
  12     step = 20;      /* step size */
  13 
  14     fahr = lower;
  15     while (fahr <= upper) {
  16         celsius = (5.0/9.0) * (fahr-32.0);
  17         printf("%3.0f %6.1f\n", fahr, celsius);
  18         fahr = fahr + step;
  19     }
  20 }

1.4. 温度对照表第3版

对于某个特定任务我们可以采用多种方法来编写程序。上面这个程序如果把while循环改成for循环，程序可以更简洁。

   1 #include <stdio.h>
   2 
   3 /* print Fahrenheit-Celsius table */
   4 main()
   5 {
   6     int fahr;
   7 
   8     for (fahr = 0; fahr <= 300; fahr = fahr + 20)
   9         printf("%3d %6.1f\n", fahr, (5.0/9.0)*(fahr-32));
  10 }

1.5. 温度对照表第4版

对于前面程序中出现的上限、下限、步长等值，使用变量是不恰当的，因为它们不会变，直接使用常数也是不恰当的，因为这样不容易理解。正确的方法之一是使用宏定义：

   1 #include <stdio.h>
   2 
   3 #define LOWER  0     /* lower limit of table */
   4 #define UPPER  300   /* upper limit */
   5 #define STEP   20    /* step size */
   6 
   7 /* print Fahrenheit-Celsius table */
   8 main()
   9 {
  10     int fahr;
  11 
  12     for (fahr = LOWER; fahr <= UPPER; fahr = fahr + STEP)
  13         printf("%3d %6.1f\n", fahr, (5.0/9.0)*(fahr-32));
  14 }

1.6. 文件复制

把输入一次一个字符地复制到输出

   1 #include <stdio.h>
   2 
   3 /* copy input to output; 1st version  */
   4 main()
   5 {
   6     int c;
   7 
   8     c = getchar();
   9     while (c != EOF) {
  10         putchar(c);
  11         c = getchar();
  12     }
  13 }

1.7. 文件复制第2版

对于经验比较丰富的C语言程序员，可以把这个字符复制程序编写得更精炼一些。

   1 #include <stdio.h>
   2 
   3 /* copy input to output; 2nd version  */
   4 main()
   5 {
   6     int c;
   7 
   8     while ((c = getchar()) != EOF)
   9         putchar(c);
  10 }

1.8. 字符计数

下列程序用于对字符进行计数，它与上面的复制程序类似。

   1 #include <stdio.h>
   2 
   3 /* count characters in input; 1st version */
   4 main()
   5 {
   6     long nc;
   7 
   8     nc = 0;
   9     while (getchar() != EOF)
  10         ++nc;
  11     printf("%ld\n", nc);
  12 }

1.9. 字符计数第2版

   1 #include <stdio.h>
   2 
   3 /* count characters in input; 2nd version */
   4 main()
   5 {
   6     double nc;
   7 
   8     for (nc = 0; getchar() != EOF; ++nc)
   9         ;
  10     printf("%.0f\n", nc);
  11 }

1.10. 行计数

接下来的这个程序用于统计输入中的行数。

   1 #include <stdio.h>
   2 
   3 /* count lines in input */
   4 main()
   5 {
   6     int c, nl;
   7 
   8     nl = 0;
   9     while ((c = getchar()) != EOF)
  10         if (c == '\n')
  11             ++nl;
  12     printf("%d\n", nl);
  13 }

1.11. 单词计数

写一个程序用于统计行数、单词数与字符数

   1 #include <stdio.h>
   2 
   3 #define IN   1  /* inside a word */
   4 #define OUT  0  /* outside a word */
   5 
   6 /* count lines, words, and characters in input */
   7 main()
   8 {
   9     int c, nl, nw, nc, state;
  10 
  11     state = OUT;
  12     nl = nw = nc = 0;
  13     while ((c = getchar()) != EOF) {
  14         ++nc;
  15         if (c == '\n')
  16             ++nl;
  17         if (c == ' ' || c == '\n' || c = '\t')
  18             state = OUT;
  19         else if (state == OUT) {
  20             state = IN;
  21             ++nw;
  22         }
  23     }
  24     printf("%d %d %d\n", nl, nw, nc);
  25 }

1.12. 数字字符计数

编写一个程序，以统计各个数字、空白符(包括空格符、制表符及换行符)以及所有其他字符出现的次数

   1    #include <stdio.h>
   2 
   3    /* count digits, white space, others */
   4    main()
   5    {
   6        int c, i, nwhite, nother;
   7        int ndigit[10];
   8 
   9        nwhite = nother = 0;
  10        for (i = 0; i < 10; ++i)
  11            ndigit[i] = 0;
  12 
  13        while ((c = getchar()) != EOF)
  14            if (c >= '0' && c <= '9')
  15                ++ndigit[c-'0'];
  16            else if (c == ' ' || c == '\n' || c == '\t')
  17                ++nwhite;
  18            else
  19                ++nother;
  20 
  21        printf("digits =");
  22        for (i = 0; i < 10; ++i)
  23            printf(" %d", ndigit[i]);
  24        printf(", white space = %d, other = %d\n",
  25            nwhite, nother);
  26    }

1.13. 函数

写一个求幂的函数power(m,n)

   1    #include <stdio.h>
   2 
   3    int power(int m, int n);
   4 
   5     /* test power function */
   6     main()
   7     {
   8         int i;
   9 
  10         for (i = 0; i < 10; ++i)
  11             printf("%d %d %d\n", i, power(2,i), power(-3,i));
  12         return 0;
  13     }
  14 
  15     /* power:  raise base to n-th power; n >= 0 */
  16     int power(int base, int n)
  17     {
  18         int i,  p;
  19 
  20         p = 1;
  21         for (i = 1; i <= n; ++i)
  22             p = p * base;
  23         return p;
  24     }

1.14. power函数第2版

   1    /* power:  raise base to n-th power; n >= 0; version 2 */
   2    int power(int base, int n)
   3    {
   4        int p;
   5 
   6        for (p = 1; n > 0; --n)
   7            p = p * base;
   8        return p;
   9    }

1.15. 最长的行

写一个程序读入一组文本行，并把最长的文本行打印出来。

   1    #include <stdio.h>
   2    #define MAXLINE 1000   /* maximum input line length */
   3 
   4    int getline(char line[], int maxline);
   5    void copy(char to[], char from[]);
   6 
   7    /* print the longest input line */
   8    main()
   9    {
  10        int len;            /* current line length */
  11        int max;            /* maximum length seen so far */
  12        char line[MAXLINE];    /* current input line */
  13        char longest[MAXLINE]; /* longest line saved here */
  14 
  15        max = 0;
  16        while ((len = getline(line, MAXLINE)) > 0)
  17            if (len > max) {
  18                max = len;
  19                copy(longest, line);
  20            }
  21        if (max > 0)  /* there was a line */
  22            printf("%s", longest);
  23        return 0;
  24    }
  25 
  26    /* getline:  read a line into s, return length  */
  27    int getline(char s[],int lim)
  28    {
  29        int c, i;
  30 
  31        for (i=0; i < lim-1 && (c=getchar())!=EOF && c!='\n'; ++i)
  32            s[i] = c;
  33        if (c == '\n') {
  34            s[i] = c;
  35            ++i;
  36        }
  37        s[i] = '\0';
  38        return i;
  39    }
  40 
  41    /* copy:  copy 'from' into 'to'; assume to is big enough */
  42    void copy(char to[], char from[])
  43    {
  44        int i;
  45 
  46        i = 0;
  47        while ((to[i] = from[i]) != '\0')
  48            ++i;
  49    }

1.16. 最长的行第2版

使用全局变量来实现

   1    #include <stdio.h>
   2 
   3    #define MAXLINE 1000    /* maximum input line size */
   4 
   5    int max;                /* maximum length seen so far */
   6    char line[MAXLINE];     /* current input line */
   7    char longest[MAXLINE];  /* longest line saved here */
   8 
   9    int getline(void);
  10    void copy(void);
  11 
  12    /* print longest input line; specialized version */
  13    main()
  14    {
  15        int len;
  16        extern int max;
  17        extern char longest[];
  18 
  19        max = 0;
  20        while ((len = getline()) > 0)
  21            if (len > max) {
  22                max = len;
  23                copy();
  24            }
  25        if (max > 0)  /* there was a line */
  26            printf("%s", longest);
  27        return 0;
  28    }
  29 
  30    /* getline:  specialized version */
  31    int getline(void)
  32    {
  33        int c, i;
  34        extern char line[];
  35 
  36        for (i = 0; i < MAXLINE - 1
  37             && (c=getchar)) != EOF && c != '\n'; ++i)
  38                 line[i] = c;
  39        if (c == '\n') {
  40            line[i] = c;
  41            ++i;
  42        }
  43        line[i] = '\0';
  44        return i;
  45    }
  46 
  47    /* copy: specialized version */
  48    void copy(void)
  49    {
  50        int i;
  51        extern char line[], longest[];
  52 
  53        i = 0;
  54        while ((longest[i] = line[i]) != '\0')
  55            ++i;
  56    }

2. 类型、运算符和表达式

2.1. 字符串长度

写一个函数求字符串的长度

   1    /* strlen:  return length of s */
   2    int strlen(char s[])
   3    {
   4        int i;
   5 
   6        while (s[i] != '\0')
   7            ++i;
   8        return i;
   9    }

2.2. 字符串转整数

写一个函数将包含一串数字的字符串转换成整数

   1    /* atoi:  convert s to integer */
   2    int atoi(char s[])
   3    {
   4        int i, n;
   5 
   6        n = 0;
   7        for (i = 0; s[i] >= '0' && s[i] <= '9'; ++i)
   8            n = 10 * n + (s[i] - '0');
   9        return n;
  10    }

2.3. 大写变小写

写一个函数，将大写字母变成小写字母，其他字符不变。

   1    /* lower:  convert c to lower case; ASCII only */
   2    int lower(int c)
   3    {
   4        if (c >= 'A' && c <= 'Z')
   5            return c + 'a' - 'A';
   6        else
   7            return c;
   8    }

2.4. 随机函数

写一个函数，用来产生随机的整数

   1    unsigned long int next = 1;
   2 
   3    /* rand:  return pseudo-random integer on 0..32767 */
   4    int rand(void)
   5    {
   6        next = next * 1103515245 + 12345;
   7        return (unsigned int)(next/65536) % 32768;
   8    }
   9 
  10    /* srand:  set seed for rand() */
  11    void srand(unsigned int seed)
  12    {
  13        next = seed;
  14    }

2.5. 字符串删除

写一个函数squeeze(s, c)，删除字符串s中所有的字符c。

   1    /* squeeze:  delete all c from s */
   2    void squeeze(char s[], int c)
   3    {
   4       int i, j;
   5 
   6       for (i = j = 0; s[i] != '\0'; i++)
   7           if (s[i] != c)
   8               s[j++] = s[i];
   9       s[j] = '\0';
  10    }

2.6. 字符串连接

写一个函数strcat(s,t)，它将字符串t连接到字符串s的尾部

   1    /* strcat:  concatenate t to end of s; s must be big enough */
   2    void strcat(char s[], char t[])
   3    {
   4        int i, j;
   5 
   6        i = j = 0;
   7        while (s[i] != '\0') /* find end of s */
   8            i++;
   9        while ((s[i++] = t[j++]) != '\0') /* copy t */
  10            ;
  11    }

2.7. 位运算

写一个函数getbits(x,p,n)，它返回x中从右边数第p位开始向右数n位的字段

   1    /* getbits:  get n bits from position p */
   2    unsigned getbits(unsigned x, int p, int n)
   3    {
   4        return (x >> (p+1-n)) & ~(~0 << n);
   5    }

2.8. 位计数

函数bitcount统计其整型参数的值为1的二进制位的个数

   1    /* bitcount:  count 1 bits in x */
   2    int bitcount(unsigned x)
   3    {
   4        int b;
   5 
   6        for (b = 0; x != 0; x >>= 1)
   7            if (x & 01)
   8                b++;
   9        return b;
  10    }

3. 控制流

3.1. 折半查找

   1    /* binsearch:  find x in v[0] <= v[1] <= ... <= v[n-1] */
   2    int binsearch(int x, int v[], int n)
   3    {
   4        int low, high, mid;
   5 
   6        low = 0;
   7        high = n - 1;
   8        while (low <= high) {
   9            mid = (low+high)/2;
  10            if (x < v[mid])
  11                high = mid + 1;
  12            else if (x  > v[mid])
  13                low = mid + 1;
  14            else    /* found match */
  15                return mid;
  16        }
  17        return -1;   /* no match */
  18    }

3.2. 数字字符计数第2版

   1    #include <stdio.h>
   2 
   3    main()  /* count digits, white space, others */
   4    {
   5        int c, i, nwhite, nother, ndigit[10];
   6 
   7        nwhite = nother = 0;
   8        for (i = 0; i < 10; i++)
   9            ndigit[i] = 0;
  10        while ((c = getchar()) != EOF) {
  11            switch (c) {
  12            case '0': case '1': case '2': case '3': case '4':
  13            case '5': case '6': case '7': case '8': case '9':
  14                ndigit[c-'0']++;
  15                break;
  16            case ' ':
  17            case '\n':
  18            case '\t':
  19                nwhite++;
  20                break;
  21            default:
  22                nother++;
  23                break;
  24            }
  25        }
  26        printf("digits =");
  27        for (i = 0; i < 10; i++)
  28            printf(" %d", ndigit[i]);
  29        printf(", white space = %d, other = %d\n",
  30            nwhite, nother);
  31        return 0;
  32    }

3.3. 字符串转整数第2版

   1    #include <ctype.h>
   2 
   3    /* atoi:  convert s to integer; version 2 */
   4    int atoi(char s[])
   5    {
   6        int i, n, sign;
   7 
   8        for (i = 0; isspace(s[i]); i++)  /* skip white space */
   9            ;
  10        sign = (s[i] == '-') ? -1 : 1;
  11        if (s[i] == '+' || s[i] == '-')  /* skip sign */
  12            i++;
  13        for (n = 0; isdigit(s[i]); i++)
  14            n = 10 * n + (s[i] - '0');
  15        return sign * n;
  16    }

3.4. 希尔排序

   1    /* shellsort:  sort v[0]...v[n-1] into increasing order */
   2    void shellsort(int v[], int n)
   3    {
   4        int gap, i, j, temp;
   5 
   6        for (gap = n/2; gap > 0; gap /= 2)
   7            for (i = gap; i < n; i++)
   8                for (j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap) {
   9                    temp = v[j];
  10                    v[j] = v[j+gap];
  11                    v[j+gap] = temp;
  12                }
  13    }

3.5. 字符串翻转

   1    #include <string.h>
   2 
   3    /* reverse:  reverse string s in place */
   4    void reverse(char s[])
   5    {
   6        int c, i, j;
   7 
   8        for (i = 0, j = strlen(s)-1; i < j; i++, j--) {
   9            c = s[i];
  10            s[i] = s[j];
  11            s[j] = c;
  12        }
  13    }

3.6. 整数转字符串

   1    /* itoa:  convert n to characters in s */
   2    void itoa(int n, char s[])
   3    {
   4        int i, sign;
   5 
   6        if ((sign = n) < 0)  /* record sign */
   7            n = -n;          /* make n positive */
   8        i = 0;
   9        do {      /* generate digits in reverse order */
  10            s[i++] = n % 10 + '0';  /* get next digit */
  11        } while ((n /= 10) > 0);    /* delete it */
  12        if (sign < 0)
  13            s[i++] = '-';
  14        s[i] = '\0';
  15        reverse(s);
  16    }

3.7. 字符串裁剪

   1    /* trim:  remove trailing blanks, tabs, newlines */
   2    int trim(char s[])
   3    {
   4        int n;
   5 
   6        for (n = strlen(s)-1; n >= 0; n--)
   7            if (s[n] != ' ' && s[n] != '\t' && s[n] != '\n')
   8                break;
   9        s[n+1] = '\0';
  10        return n;
  11    }

4. 函数

4.1. 模式查找

设计并编写一个程序，它将输入中包含特定“模式”或字符串的各行打印出来(这是UNIX程序grep的特例)

   1    #include <stdio.h>
   2    #define MAXLINE 1000 /* maximum input line length */
   3 
   4    int getline(char line[], int max)
   5    int strindex(char source[], char searchfor[]);
   6 
   7    char pattern[] = "ould";   /* pattern to search for */
   8 
   9    /* find all lines matching pattern */
  10    main()
  11    {
  12        char line[MAXLINE];
  13        int found = 0;
  14 
  15        while (getline(line, MAXLINE) > 0)
  16            if (strindex(line, pattern) >= 0) {
  17                printf("%s", line);
  18                found++;
  19            }
  20        return found;
  21    }
  22 
  23    /* getline:  get line into s, return length */
  24    int getline(char s[], int lim)
  25    {
  26        int c, i;
  27 
  28        i = 0;
  29        while (--lim > 0 && (c=getchar()) != EOF && c != '\n')
  30            s[i++] = c;
  31        if (c == '\n')
  32            s[i++] = c;
  33        s[i] = '\0';
  34        return i;
  35    }
  36 
  37    /* strindex:  return index of t in s, -1 if none */
  38    int strindex(char s[], char t[])
  39    {
  40        int i, j, k;
  41 
  42        for (i = 0; s[i] != '\0'; i++) {
  43            for (j=i, k=0; t[k]!='\0' && s[j]==t[k]; j++, k++)
  44                ;
  45            if (k > 0 && t[k] == '\0')
  46                return i;
  47        }
  48        return -1;
  49    }

4.2. 字符串转浮点数

函数atof把字符串s转换为相应的双精度浮点数，是atoi函数的扩展

   1    #include <ctype.h>
   2 
   3    /* atof:  convert string s to double */
   4    double atof(char s[])
   5    {
   6        double val, power;
   7        int i, sign;
   8 
   9        for (i = 0; isspace(s[i]); i++)  /* skip white space */
  10            ;
  11        sign = (s[i] == '-') ? -1 : 1;
  12        if (s[i] == '+' || s[i] == '-')
  13            i++;
  14        for (val = 0.0; isdigit(s[i]); i++)
  15            val = 10.0 * val + (s[i] - '0');
  16        if (s[i] == '.')
  17            i++;
  18        for (power = 1.0; isdigit(s[i]); i++) {
  19            val = 10.0 * val + (s[i] - '0');
  20            power *= 10;
  21        }
  22        return sign * val / power;
  23    }

4.3. 调用atof

   1    #include <stdio.h>
   2 
   3    #define MAXLINE 100
   4 
   5    /* rudimentary calculator */
   6    main()
   7    {
   8        double sum, atof(char []);
   9        char line[MAXLINE];
  10        int getline(char line[], int max);
  11 
  12        sum = 0;
  13        while (getline(line, MAXLINE) > 0)
  14            printf("\t%g\n", sum += atof(line));
  15        return 0;
  16    }

4.4. 字符串转整数第3版

在函数atof的基础上，我们可以利用它编写出函数atoi(将字符串转换为int类型)

   1    /* atoi:  convert string s to integer using atof */
   2    int atoi(char s[])
   3    {
   4        double atof(char s[]);
   5 
   6        return (int) atof(s);
   7    }

4.5. 计算器

编写一个具有加(+)、减(-)、乘(*)、除(/)四则运算功能的计算器程序。为了更容易实现，我们在计算器中使用逆波兰表示法代替普通的中缀表示法，比如： (1 - 2) * (4 + 5) 采用逆波兰表示法表示为： 1 2 - 4 5 + *

   1    #include <stdio.h>
   2    #include <stdlib.h>  /* for  atof() */
   3 
   4    #define MAXOP   100  /* max size of operand or operator */
   5    #define NUMBER  '0'  /* signal that a number was found */
   6 
   7    int getop(char []);
   8    void push(double);
   9    double pop(void);
  10 
  11    /* reverse Polish calculator */
  12    main()
  13    {
  14        int type;
  15        double op2;
  16        char s[MAXOP];
  17 
  18        while ((type = getop(s)) != EOF) {
  19            switch (type) {
  20            case NUMBER:
  21                push(atof(s));
  22                break;
  23            case '+':
  24                push(pop() + pop());
  25                break;
  26            case '*':
  27                push(pop() * pop());
  28                break;
  29            case '-':
  30                op2 = pop();
  31                push(pop() - op2);
  32                break;
  33            case '/':
  34                op2 = pop();
  35                if (op2 != 0.0)
  36                    push(pop() / op2);
  37                else
  38                    printf("error: zero divisor\n");
  39                break;
  40            case '\n':
  41                printf("\t%.8g\n", pop());
  42                break;
  43            default:
  44                printf("error: unknown command %s\n", s);
  45                break;
  46            }
  47        }
  48        return 0;
  49    }

   1    #include <ctype.h>
   2 
   3    int getch(void);
   4    void ungetch(int);
   5 
   6    /* getop:  get next character or numeric operand */
   7    int getop(char s[])
   8    {
   9        int i, c;
  10 
  11        while ((s[0] = c = getch()) == ' ' || c == '\t')
  12            ;
  13        s[1] = '\0';
  14        if (!isdigit(c) && c != '.')
  15            return c;      /* not a number */
  16        i = 0;
  17        if (isdigit(c))    /* collect integer part */
  18            while (isdigit(s[++i] = c = getch()))
  19               ;
  20        if (c == '.')      /* collect fraction part */
  21            while (isdigit(s[++i] = c = getch()))
  22               ;
  23        s[i] = '\0';
  24        if (c != EOF)
  25            ungetch(c);
  26        return NUMBER;
  27    }

   1    #define BUFSIZE 100
   2 
   3    char buf[BUFSIZE];    /* buffer for ungetch */
   4    int bufp = 0;         /* next free position in buf */
   5 
   6    int getch(void)  /* get a (possibly pushed-back) character */
   7    {
   8        return (bufp > 0) ? buf[--bufp] : getchar();
   9    }
  10 
  11    void ungetch(int c)   /* push character back on input */
  12    {
  13        if (bufp >= BUFSIZE)
  14            printf("ungetch: too many characters\n");
  15        else
  16            buf[bufp++] = c;
  17    }

4.6. 打印整数

   1    #include <stdio.h>
   2 
   3    /* printd:  print n in decimal */
   4    void printd(int n)
   5    {
   6        if (n < 0) {
   7            putchar('-');
   8            n = -n;
   9        }
  10        if (n / 10)
  11            printd(n / 10);
  12        putchar(n % 10 + '0');
  13    }

4.7. 快速排序

   1    /* qsort:  sort v[left]...v[right] into increasing order */
   2    void qsort(int v[], int left, int right)
   3    {
   4        int i, last;
   5        void swap(int v[], int i, int j);
   6 
   7        if (left >= right) /* do nothing if array contains */
   8            return;        /* fewer than two elements */
   9        swap(v, left, (left + right)/2); /* move partition elem */
  10        last = left;                     /* to v[0] */
  11        for (i = left + 1; i <= right; i++)  /* partition */
  12            if (v[i] < v[left])
  13                swap(v, ++last, i);
  14        swap(v, left, last);            /* restore partition  elem */
  15        qsort(v, left, last-1);
  16        qsort(v, last+1, right);
  17    }

   1    /* swap:  interchange v[i] and v[j] */
   2    void swap(int v[], int i, int j)
   3    {
   4        int temp;
   5 
   6        temp = v[i];
   7        v[i] = v[j];
   8        v[j] = temp;
   9    }

5. 指针与数组

5.1. 交换两个变量的值

   1    void swap(int *px, int *py)  /* interchange *px and *py */
   2    {
   3        int temp;
   4 
   5        temp = *px;
   6        *px = *py;
   7        *py = temp;
   8    }

5.2. 读取整数

   1    #include <ctype.h>
   2 
   3    int getch(void);
   4    void ungetch(int);
   5 
   6    /* getint:  get next integer from input into *pn */
   7    int getint(int *pn)
   8    {
   9        int c, sign;
  10 
  11        while (isspace(c = getch()))   /* skip white space */
  12            ;
  13        if (!isdigit(c) && c != EOF && c != '+' && c != '-') {
  14            ungetch(c);  /* it is not a number */
  15            return 0;
  16        }
  17        sign = (c == '-') ? -1 : 1;
  18        if (c == '+' || c == '-')
  19            c = getch();
  20        for (*pn = 0; isdigit(c), c = getch())
  21            *pn = 10 * *pn + (c - '0');
  22        *pn *= sign;
  23        if (c != EOF)
  24            ungetch(c);
  25        return c;
  26    }

5.3. 求字符串长度

   1    /* strlen:  return length of string s */
   2    int strlen(char *s)
   3    {
   4        int n;
   5 
   6        for (n = 0; *s != '\0', s++)
   7            n++;
   8        return n;
   9    }

5.4. 内存分配程序

   1    #define ALLOCSIZE 10000 /* size of available space */
   2 
   3    static char allocbuf[ALLOCSIZE]; /* storage for alloc */
   4    static char *allocp = allocbuf;  /* next free position */
   5 
   6    char *alloc(int n)    /* return pointer to n characters */
   7    {
   8        if (allocbuf + ALLOCSIZE - allocp >= n) {  /* it fits */
   9            allocp += n;
  10            return allocp - n; /* old p */
  11        } else      /* not enough room */
  12            return 0;
  13    }
  14 
  15    void afree(char *p)  /* free storage pointed to by p */
  16    {
  17        if (p >= allocbuf && p < allocbuf + ALLOCSIZE)
  18            allocp = p;
  19    }

5.5. 字符串拷贝

   1    /* strcpy:  copy t to s; array subscript version */
   2    void strcpy(char *s, char *t)
   3    {
   4        int i;
   5 
   6        i = 0;
   7        while ((s[i] = t[i]) != '\0')
   8            i++;
   9    }

5.6. 字符串拷贝第2版

   1    /* strcpy:  copy t to s; pointer version */
   2    void strcpy(char *s, char *t)
   3    {
   4        int i;
   5 
   6        i = 0;
   7        while ((*s = *t) != '\0') {
   8            s++;
   9            t++;
  10        }
  11    }

5.7. 字符串拷贝第3版

   1    /* strcpy:  copy t to s; pointer version 2 */
   2    void strcpy(char *s, char *t)
   3    {
   4        while ((*s++ = *t++) != '\0')
   5            ;
   6    }

5.8. 字符串拷贝第4版

   1    /* strcpy:  copy t to s; pointer version 3 */
   2    void strcpy(char *s, char *t)
   3    {
   4        while (*s++ = *t++)
   5            ;
   6    }

5.9. 字符串比较

   1    /* strcmp:  return <0 if s<t, 0 if s==t, >0 if s>t */
   2    int strcmp(char *s, char *t)
   3    {
   4        int i;
   5 
   6        for (i = 0; s[i] == t[i]; i++)
   7            if (s[i] == '\0')
   8                return 0;
   9        return s[i] - t[i];
  10    }

5.10. 字符串比较第2版

   1    /* strcmp:  return <0 if s<t, 0 if s==t, >0 if s>t */
   2    int strcmp(char *s, char *t)
   3    {
   4        for ( ; *s == *t; s++, t++)
   5            if (*s == '\0')
   6                return 0;
   7        return *s - *t;
   8    }

5.11. 文本行排序

该程序按字母顺序对由文本行组成的集合进行排序。

   1    #include <stdio.h>
   2    #include <string.h>
   3 
   4    #define MAXLINES 5000     /* max #lines to be sorted */
   5 
   6    char *lineptr[MAXLINES];  /* pointers to text lines */
   7 
   8    int readlines(char *lineptr[], int nlines);
   9    void writelines(char *lineptr[], int nlines);
  10 
  11    void qsort(char *lineptr[], int left, int right);
  12 
  13    /* sort input lines */
  14    main()
  15    {
  16        int nlines;     /* number of input lines read */
  17 
  18        if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
  19            qsort(lineptr, 0, nlines-1);
  20            writelines(lineptr, nlines);
  21            return 0;
  22        } else {
  23            printf("error: input too big to sort\n");
  24            return 1;
  25        }
  26    }
  27 
  28    #define MAXLEN 1000  /* max length of any input line */
  29    int getline(char *, int);
  30    char *alloc(int);
  31 
  32    /* readlines:  read input lines */
  33    int readlines(char *lineptr[], int maxlines)
  34    {
  35        int len, nlines;
  36        char *p, line[MAXLEN];
  37 
  38        nlines = 0;
  39        while ((len = getline(line, MAXLEN)) > 0)
  40            if (nlines >= maxlines || p = alloc(len) == NULL)
  41                return -1;
  42            else {
  43                line[len-1] = '\0';  /* delete newline */
  44                strcpy(p, line);
  45                lineptr[nlines++] = p;
  46            }
  47        return nlines;
  48    }
  49 
  50    /* writelines:  write output lines */
  51    void writelines(char *lineptr[], int nlines)
  52    {
  53        int i;
  54 
  55        for (i = 0; i < nlines; i++)
  56            printf("%s\n", lineptr[i]);
  57    }

5.12. 输出所有行函数第2版

   1    /* writelines:  write output lines */
   2    void writelines(char *lineptr[], int nlines)
   3    {
   4        while (nlines-- > 0)
   5            printf("%s\n", *lineptr++);
   6    }

5.13. 文本行排序函数

   1    /* qsort:  sort v[left]...v[right] into increasing order */
   2    void qsort(char *v[], int left, int right)
   3    {
   4        int i, last;
   5        void swap(char *v[], int i, int j);
   6 
   7        if (left >= right)  /* do nothing if array contains */
   8            return;         /* fewer than two elements */
   9        swap(v, left, (left + right)/2);
  10        last = left;
  11        for (i = left+1; i <= right; i++)
  12            if (strcmp(v[i], v[left]) < 0)
  13                swap(v, ++last, i);
  14        swap(v, left, last);
  15        qsort(v, left, last-1);
  16        qsort(v, last+1, right);
  17    }

   1    /* swap:  interchange v[i] and v[j] */
   2    void swap(char *v[], int i, int j)
   3    {
   4        char *temp;
   5 
   6        temp = v[i];
   7        v[i] = v[j];
   8        v[j] = temp;
   9    }

5.14. 日期转换

我们考虑一个日期转换的问题：把某月某日这种日期表示形式转换为某年中第几天的表示形式，反之亦然。

   1    static char daytab[2][13] = {
   2        {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
   3        {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
   4    };
   5 
   6    /* day_of_year:  set day of year from month & day */
   7    int day_of_year(int year, int month, int day)
   8    {
   9        int i, leap;
  10        leap = year%4 == 0 && year%100 != 0 || year%400 == 0;
  11        for (i = 1; i < month; i++)
  12            day += daytab[leap][i];
  13        return day;
  14    }
  15 
  16    /* month_day:  set month, day from day of year */
  17    void month_day(int year, int yearday, int *pmonth, int *pday)
  18    {
  19        int i, leap;
  20 
  21        leap = year%4 == 0 && year%100 != 0 || year%400 == 0;
  22        for (i = 1; yearday > daytab[leap][i]; i++)
  23            yearday -= daytab[leap][i];
  24        *pmonth = i;
  25        *pday = yearday;
  26    }

5.15. 月份名称

考虑这样一个问题：编写一个函数month_name(n)，它返回一个指向第n个月名字的字符串的指针。

   1    /* month_name:  return name of n-th month */
   2    char *month_name(int n)
   3    {
   4        static char *name[] = {
   5            "Illegal month",
   6            "January", "February", "March",
   7            "April", "May", "June",
   8            "July", "August", "September",
   9            "October", "November", "December"
  10        };
  11 
  12        return (n < 1 || n > 12) ? name[0] : name[n];
  13    }

5.16. 参数回显

写一个程序echo，它将命令行参数回显在屏幕上的一行中，其中命令行中各参数之间用空格隔开。

   1    #include <stdio.h>
   2 
   3    /* echo command-line arguments; 1st version */
   4    main(int argc, char *argv[])
   5    {
   6        int i;
   7 
   8        for (i = 1; i < argc; i++)
   9            printf("%s%s", argv[i], (i < argc-1) ? " " : "");
  10        printf("\n");
  11        return 0;
  12    }

5.17. 参数回显第2版

   1    #include <stdio.h>
   2 
   3    /* echo command-line arguments; 2nd version */
   4    main(int argc, char *argv[])
   5    {
   6        while (--argc > 0)
   7            printf("%s%s", *++argv, (argc > 1) ? " " : "");
   8        printf("\n");
   9        return 0;
  10    }

5.18. 模式查找第2版

通过命令行的第一个参数指定待匹配的模式

   1    #include <stdio.h>
   2    #include <string.h>
   3    #define MAXLINE 1000
   4 
   5    int getline(char *line, int max);
   6 
   7    /* find:  print lines that match pattern from 1st arg */
   8    main(int argc, char *argv[])
   9    {
  10        char line[MAXLINE];
  11        int found = 0;
  12 
  13        if (argc != 2)
  14            printf("Usage: find pattern\n");
  15        else
  16            while (getline(line, MAXLINE) > 0)
  17                if (strstr(line, argv[1]) != NULL) {
  18                    printf("%s", line);
  19                    found++;
  20                }
  21        return found;
  22    }

5.19. 模式查找第3版

用-x(代表except)表示打印所有与模式不匹配的文本行，用-n(代表number)表示打印行号

   1    #include <stdio.h>
   2    #include <string.h>
   3    #define MAXLINE 1000
   4 
   5    int getline(char *line, int max);
   6 
   7    /* find: print lines that match pattern from 1st arg */
   8    main(int argc, char *argv[])
   9    {
  10        char line[MAXLINE];
  11        long lineno = 0;
  12        int c, except = 0, number = 0, found = 0;
  13 
  14        while (--argc > 0 && (*++argv)[0] == '-')
  15            while (c = *++argv[0])
  16                switch (c) {
  17                case 'x':
  18                    except = 1;
  19                    break;
  20                case 'n':
  21                    number = 1;
  22                    break;
  23                default:
  24                    printf("find: illegal option %c\n", c);
  25                    argc = 0;
  26                    found = -1;
  27                    break;
  28                }
  29        if (argc != 1)
  30            printf("Usage: find -x -n pattern\n");
  31        else
  32            while (getline(line, MAXLINE) > 0) {
  33                lineno++;
  34                if ((strstr(line, *argv) != NULL) != except) {
  35                    if (number)
  36                        printf("%ld:", lineno);
  37                    printf("%s", line);
  38                    found++;
  39                }
  40            }
  41        return found;
  42    }

5.20. 行排序程序

在给定可选参数-n的情况下，该函数将按数值大小而非字典顺序对输入行进行排序。

   1    #include <stdio.h>
   2    #include <string.h>
   3 
   4    #define MAXLINES 5000     /* max #lines to be sorted */
   5    char *lineptr[MAXLINES];  /* pointers to text lines */
   6 
   7    int readlines(char *lineptr[], int nlines);
   8    void writelines(char *lineptr[], int nlines);
   9 
  10    void qsort(void *lineptr[], int left, int right,
  11               int (*comp)(void *, void *));
  12    int numcmp(char *, char *);
  13 
  14    /* sort input lines */
  15    main(int argc, char *argv[])
  16    {
  17        int nlines;        /* number of input lines read */
  18        int numeric = 0;   /* 1 if numeric sort */
  19 
  20        if (argc > 1 && strcmp(argv[1], "-n") == 0)
  21            numeric = 1;
  22        if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
  23            qsort((void**) lineptr, 0, nlines-1,
  24              (int (*)(void*,void*))(numeric ? numcmp : strcmp));
  25            writelines(lineptr, nlines);
  26            return 0;
  27        } else {
  28            printf("input too big to sort\n");
  29            return 1;
  30        }
  31    }

   1    /* qsort:  sort v[left]...v[right] into increasing order */
   2    void qsort(void *v[], int left, int right,
   3               int (*comp)(void *, void *))
   4    {
   5        int i, last;
   6 
   7        void swap(void *v[], int, int);
   8 
   9        if (left >= right)    /* do  nothing if array contains */
  10            return;           /* fewer than two elements */
  11        swap(v, left, (left + right)/2);
  12        last = left;
  13        for (i = left+1; i <= right;  i++)
  14            if ((*comp)(v[i], v[left]) < 0)
  15                swap(v, ++last, i);
  16        swap(v, left, last);
  17        qsort(v, left, last-1, comp);
  18        qsort(v, last+1, right, comp);
  19    }

   1    #include <stdlib.h>
   2 
   3    /* numcmp:  compare s1 and s2 numerically */
   4    int numcmp(char *s1, char *s2)
   5    {
   6        double v1, v2;
   7 
   8        v1 = atof(s1);
   9        v2 = atof(s2);
  10        if (v1 < v2)
  11            return -1;
  12        else if (v1 > v2)
  13            return 1;
  14        else
  15            return 0;
  16    }

   1    void swap(void *v[],  int i, int j;)
   2    {
   3        void *temp;
   4 
   5        temp = v[i];
   6        v[i] = v[j];
   7        v[j] = temp;
   8    }

5.21. 复杂声明

   1    /* dcl:  parse a declarator */
   2    void dcl(void)
   3    {
   4        int ns;
   5 
   6        for (ns = 0; gettoken() == '*'; ) /* count *'s */
   7            ns++;
   8        dirdcl();
   9        while (ns-- > 0)
  10            strcat(out, " pointer to");
  11    }
  12 
  13    /* dirdcl:  parse a direct declarator */
  14    void dirdcl(void)
  15    {
  16        int type;
  17 
  18        if (tokentype == '(') {         /* ( dcl ) */
  19            dcl();
  20            if (tokentype != ')')
  21                printf("error: missing )\n");
  22        } else if (tokentype == NAME)  /* variable name */
  23            strcpy(name, token);
  24        else
  25            printf("error: expected name or (dcl)\n");
  26        while ((type=gettoken()) == PARENS || type == BRACKETS)
  27            if (type == PARENS)
  28                strcat(out, " function returning");
  29            else {
  30                strcat(out, " array");
  31                strcat(out, token);
  32                strcat(out, " of");
  33            }
  34    }

   1    #include <stdio.h>
   2    #include <string.h>
   3    #include <ctype.h>
   4 
   5    #define MAXTOKEN  100
   6 
   7    enum { NAME, PARENS, BRACKETS };
   8 
   9    void dcl(void);
  10    void dirdcl(void);
  11 
  12    int gettoken(void);
  13    int tokentype;           /* type of last token */
  14    char token[MAXTOKEN];    /* last token string */
  15    char name[MAXTOKEN];     /* identifier name */
  16    char datatype[MAXTOKEN]; /* data type = char, int, etc. */
  17    char out[1000];
  18 
  19    main()  /* convert declaration to words */
  20    {
  21        while (gettoken() != EOF) {   /* 1st token on line */
  22            strcpy(datatype, token);  /* is the datatype */
  23            out[0] = '\0';
  24            dcl();       /* parse rest of line */
  25            if (tokentype != '\n')
  26                printf("syntax error\n");
  27            printf("%s: %s %s\n", name, out, datatype);
  28        }
  29        return 0;
  30    }

   1    int gettoken(void)  /* return next token */
   2    {
   3        int c, getch(void);
   4        void ungetch(int);
   5        char *p = token;
   6 
   7        while ((c = getch()) == ' ' || c == '\t')
   8            ;
   9        if (c == '(') {
  10            if ((c = getch()) == ')') {
  11                strcpy(token, "()");
  12                return tokentype = PARENS;
  13            } else {
  14                ungetch(c);
  15                return tokentype = '(';
  16            }
  17        } else if (c == '[') {
  18            for (*p++ = c; (*p++ = getch()) != ']'; )
  19                ;
  20            *p = '\0';
  21            return tokentype = BRACKETS;
  22        } else if (isalpha(c)) {
  23            for (*p++ = c; isalnum(c = getch()); )
  24                *p++ = c;
  25            *p = '\0';
  26            ungetch(c);
  27            return tokentype = NAME;
  28        } else
  29            return tokentype = c;
  30 
  31    }

6. 结构

6.1. 坐标点和矩形结构

   1 struct point {
   2     int x;
   3     int y;
   4 };
   5 struct rect {
   6     struct point pt1;
   7     struct point pt2;
   8 };

6.2. 创建坐标结构

   1 /* makepoint:  make a point from x and y components */
   2 struct point makepoint(int x, int y)
   3 {
   4     struct point temp;
   5 
   6     temp.x = x;
   7     temp.y = y;
   8     return temp;
   9 }

6.3. 坐标相加

   1    /* addpoints:  add two points */
   2    struct addpoint(struct point p1, struct point p2)
   3    {
   4        p1.x += p2.x;
   5        p1.y += p2.y;
   6        return p1;
   7    }

6.4. 判断点是否在矩形中

   1    /* ptinrect:  return 1 if p in r, 0 if not */
   2    int ptinrect(struct point p, struct rect r)
   3    {
   4        return p.x >= r.pt1.x && p.x < r.pt2.x
   5            && p.y >= r.pt1.y && p.y < r.pt2.y;
   6    }

6.5. 矩形规范化

   1    #define min(a, b) ((a) < (b) ? (a) : (b))
   2    #define max(a, b) ((a) > (b) ? (a) : (b))
   3 
   4    /* canonrect: canonicalize coordinates of rectangle */
   5    struct rect canonrect(struct rect r)
   6    {
   7        struct rect temp;
   8 
   9        temp.pt1.x = min(r.pt1.x, r.pt2.x);
  10        temp.pt1.y = min(r.pt1.y, r.pt2.y);
  11        temp.pt2.x = max(r.pt1.x, r.pt2.x);
  12        temp.pt2.y = max(r.pt1.y, r.pt2.y);
  13        return temp;
  14    }

6.6. 关键字统计

编写这样一个程序，它用来统计输入中各个C语言关键字出现的次数。

   1    struct key {
   2        char *word;
   3        int count;
   4    } keytab[] = {
   5        "auto", 0,
   6        "break", 0,
   7        "case", 0,
   8        "char", 0,
   9        "const", 0,
  10        "continue", 0,
  11        "default", 0,
  12        /* ... */
  13        "unsigned", 0,
  14        "void", 0,
  15        "volatile", 0,
  16        "while", 0
  17    };

   1    #include <stdio.h>
   2    #include <ctype.h>
   3    #include <string.h>
   4 
   5    #define MAXWORD 100
   6 
   7    int getword(char *, int);
   8    int binsearch(char *, struct key *, int);
   9 
  10    /* count C keywords */
  11    main()
  12    {
  13        int n;
  14        char word[MAXWORD];
  15 
  16        while (getword(word, MAXWORD) != EOF)
  17            if (isalpha(word[0]))
  18                if ((n = binsearch(word, keytab, NKEYS)) >= 0)
  19                    keytab[n].count++;
  20        for (n = 0; n < NKEYS; n++)
  21            if (keytab[n].count > 0)
  22                printf("%4d %s\n",
  23                    keytab[n].count, keytab[n].word);
  24        return 0;
  25    }
  26 
  27    /* binsearch:  find word in tab[0]...tab[n-1] */
  28    int binsearch(char *word, struct key tab[], int n)
  29    {
  30        int cond;
  31        int low, high, mid;
  32 
  33        low = 0;
  34        high = n - 1;
  35        while (low <= high) {
  36            mid = (low+high) / 2;
  37            if ((cond = strcmp(word, tab[mid].word)) < 0)
  38                high = mid - 1;
  39            else if (cond > 0)
  40                low = mid + 1;
  41            else
  42                return mid;
  43        }
  44        return -1;
  45    }

   1    /* getword:  get next word or character from input */
   2    int getword(char *word, int lim)
   3    {
   4        int c, getch(void);
   5        void ungetch(int);
   6        char *w = word;
   7 
   8        while (isspace(c = getch()))
   9            ;
  10        if (c != EOF)
  11            *w++ = c;
  12        if (!isalpha(c)) {
  13            *w = '\0';
  14            return c;
  15        }
  16        for ( ; --lim > 0; w++)
  17            if (!isalnum(*w = getch())) {
  18                ungetch(*w);
  19                break;
  20            }
  21        *w = '\0';
  22        return word[0];
  23    }