[关闭]
@ChristopherWu 2018-01-29T18:43:33.000000Z 字数 25119 阅读 22106

Linux C一站式编程答案ii

Study

const常量, 字符串字面值都是位于.rodata段, 在链接时.rodata段与.text段合并到Text Segment中, 在加载运行时操作系统把Text Segment的页面只读保护起来, 防止意外改写.

编译器会给函数中的static变量的符号名加一个后缀, 比如a会变成a.1706(某种程度上, 跟C++的重载函数的处理差不多)

.bss段与.data段的不同之处在于, .bss断在文件中不占存储空间, 加载到内存时这个段用0填充.
C语言规定全局变量和static变量(不管是函数里还是函数外)如果不初始化初值都为0, 未初始化的和明确初始化为0的全局变量,static变量都会分配在bss段.

[bss是历史遗留下来的名词, 全称是"Block Started by Symbol", 最初是IBM 704汇编器的一条伪指令名字, 沿用至今. 不过你也可以记成"Better Save Space", 因为.bss段在文件中不占存储空间]

虽然栈是从高地址向低地址增长的,但是数组跟结构体都是从低地址向高地址排列.

应用程序二进制接口规范(ABI, Application Binary Interface)

  1. 数据类型的长度(例如ILP32 LP64)
  2. Calling Convention
  3. 访问内存地址的对齐要求
  4. 结构体和Bit-field的填充方式
  5. 字节序(大端,小端)
  6. 用什么指令做系统调用, 各种系统调用的参数
  7. 可执行文件和库文件格式(例如ELF格式)
    如果两个平台具有相同的体系结构 并且遵循系统的API, 就可以保证一个平台上的二进制程序直接拷贝到另一个平台上就能运行, 不用重新编译.

进程之间传递信息的各种途径(包括各种IPC机制)总结如下:

上篇 C语言入门

程序的基本概念

1、解释执行的语言相比编译执行的语言有什么优缺点？

由于少了编译过程，解释型语言开发调试的周期更短；由于不需要生成机器指令，解释型语言平台无关性更好；解释型语言的执行效率不如编译型语言，因为在运行时还要解释源代码或中间代码，而编译型语言的程序在运行时没有这个负担。

1、总结前面介绍的转义序列的规律，想想在printf的格式化字符串中怎么表示一个%字符？写个小程序试验一下。

printf("%%")
根据转义序列的\规则类比可知printf("%%");

假设变量x和n是两个正整数,我们知道 x/n 这个表达式的结果是取Floor,例
如x是17,n是4,则结果是4。如果希望结果取Ceiling应该怎么写表达式呢?例
如x是17,n是4,则结果是5,而x是16,n是4,则结果是4。

答案是(x+n-1)/n。
这题很重要，多给点时间让学生想。一个班差不多有一两个人能想出来。有些人自以为学得不错，不好好听课，就可以拿这题打击打击。有些人用if/else或三目运算符做出来，应该discourage他们。这种写法以后很常见，绝非奇技淫巧，比如以后讲到对齐会见到这样的情况，分配的内存必须是4字节的整数倍。
给学生解释可以这么说：先拆成x/n+(n-1)/n来看，如果x/n还能余出一点儿来，合写成(x+n-1)/n就可以把余出来的那一点儿给(n-1)，从而使(n-1)/n等于1。

简单函数

如果在一个程序中调用了printf函数却不包含头文件，例如int main(void) { printf("\n"); }，编译时会报警告：warning: incompatible implicit declaration of built-in function ‘printf’。请分析错误原因。

(答案)没有包含头文件就没有printf函数的声明，编译器要做隐式声明，返回值int，参数一个，而真正的printf原型返回值是int，参数是可变个数的，所以incompatible。

定义变量时可以把同样类型的变量列在一起,而定义参数却不可以。其实这里的这个规定也不算十分的例外,并不是C语言的设计者故意找茬,而是不得不这么规定,读者想想为什么
呢?

假如使用该规则, 当有多个类型的变量即int add(int a, b, double c, d);
难以检查语法正确性.

分支语句

1、以下程序段编译能通过，执行也不出错，但是执行结果不正确（根据第 3 节 “程序的调试”的定义，这是一个语义错误），请分析一下哪里错了。还有，既然错了为什么编译能通过呢？
int x = -1;
if (x > 0);
printf("x is positive.\n");

if判断后有个分号;(空语句), 因为这不是语法错误，所以能够编译通过。

1、写两个表达式，分别取整型变量x的个位和十位。

1)、 x%10
2)、 x%100/10

2、写一个函数，参数是整型变量x，功能是打印x的个位和十位。

void print_x(int x) {
    printf("个位： %d 十位: %d \n", x%10, x%100/10);
}

1、把代码段
if (x > 0 && x < 10);
else
printf("x is out of range.\n");
改写成下面这种形式：
if (__ || __)
printf("x is out of range.\n");
____应该怎么填？ 

x<=0      x>=10
德摩根律

2、把代码段：
if (x > 0)
printf("Test OK!\n");
else if (x <= 0 && y > 0)
printf("Test OK!\n");
else
printf("Test failed!\n");
改写成下面这种形式：
if (__ && __)
printf("Test failed!\n");
else
printf("Test OK!\n");
____应该怎么填？

(不确定是否最优) y<=0 x<=0
x+¬x*y=x+y，德摩根律

3、有这样一段代码：
if (x > 1 && y != 1) {
...
} else if (x < 1 && y != 1) {
...
} else {
...
}
要进入最后一个else，x和y需要满足条件__ || __。这里应该怎么填？

x==1 y==1
x*(y+z)=x*y+x*z，德摩根律

4、以下哪一个if判断条件是多余的可以去掉？这里所谓的“多余”是指，某种情况下如果本来应该打印Test OK!，去掉这个多余条件后仍然打印Test OK!，如果本来应该打印Test failed!，去掉这个多余条件后仍然打印Test failed!。
if (x<3 && y>3)
printf("Test OK!\n");
else if (x>=3 && y>=3)
printf("Test OK!\n");
else if (z>3 && x>=3)
printf("Test OK!\n");
else if (z<=3 && y>=3)
printf("Test OK!\n");
else
printf("Test failed!\n");

第四个条件else if (z<=3 && y>=3) 可以去掉。
因为在第二个判断假如不符合条件,可以确定y一定小于3。那么而第三个条件不符合，可以得到z>3,换言之，第四个条件一定为假，没有必要。
x*y+¬x*z+y*z=x*y+¬x*z

深入理解函数

1、编写一个布尔函数int is_leap_year(int year)，判断参数year是不是闰年。如果某年份能被4整除，但不能被100整除，那么这一年就是闰年，此外，能被400整除的年份也是闰年。

code

2、编写一个函数double myround(double x)，输入一个小数，将它四舍五入。例如myround(-3.51)的值是-4.0，myround(4.49)的值是4.0。可以调用math.h中的库函数ceil和floor实现这个函数。

code

在上面的例子中,如果循环结束条件就要写成 i 

    n += 1;

2、在上一节中讲过怎样把 for 语句写成等价的 while 语句,但也提到如果循环体中有 continue 语句,这两种形式就不等价了,想一想为什么不等价了?

因为for里有执行语句，当continue后会执行（比如++i),而while里则没有。

1、编写递归函数求两个正整数a和b的最大公约数（GCD，Greatest Common Divisor），使用Euclid算法：
1. 如果a除以b能整除，则最大公约数是b。
2. 否则，最大公约数等于b和a%b的最大公约数。
Euclid算法是很容易证明的，请读者自己证明一下为什么这么算就能算出最大公约数。

  1. int GCD(int a, int b) {
  2. if(a%b == 0)
  3.     return b;
  4. else
  5.     return GCD(b, a%b);
  6. }

2、编写递归函数求Fibonacci数列的第n项，这个数列是这样定义的：
fib(0)=1
fib(1)=1
fib(n)=fib(n-1)+fib(n-2)
这个递归函数做两次递归调用，会形成树状的调用关系，需要画图解释。

  1. int Fibonacci(int n) {
  2. if(n==0 || n==1)
  3.     return 1;
  4. else
  5.     return Fibonacci(n-1) + Fibonacci(n-2);
  6. }

循环语句

1、用循环解决第 3 节 “递归”的所有习题，体会递归和循环这两种不同的思路。

  1. int w_GCD(int a, int b) {
  2.     while(a%b != 0) {
  3.         int temp = a;
  4.         a = b;
  5.         b = temp%b;
  6.     }
  7.     return b;
  8. }
  10. int w_Fibonacci(int n) {
  11.     int i, sum=1, before=1;
  12.     for(i=1; i<n; ++i) {
  13.         sum += before;
  14.         before = sum;
  15.     }
  16.     return sum;
  17. }

2、编写程序数一下1到100的所有整数中出现多少次数字9。在写程序之前先把这些问题考虑清楚：
1. 这个问题中的循环变量是什么？
2. 这个问题中的累加器是什么？用加法还是用乘法累积？
3. 在第 2 节 “if/else语句”的习题1写过取一个整数的个位和十位的表达式，这两个表达式怎样用到程序中？

1.数字 1-100
2.i,加法累加 

  1. int count(void) {
  2.     int i, count=1;
  3.     for(i=10; i<=100; ++i) {
  4.         if(i/9==0 || i%10 == 9) {
  5.             ++count;
  6.         }
  7.     }
  8.     return count;
  9. }

其实没有必要从2一直检查到n-1，只要从2检查到⌊sqrt(n)⌋，如果全都不能整除就足以证明n是素数了，解释一下为什么

对称性.

求素数这个程序只是为了说明break和continue的用法才这么写的,其实完全可以不用break和continue,请读者修改一下循环的结构,去掉break和continue而保持功能不变 

  1. #include <stdio.h>
  2. int is_prime(int n)
  3. {
  4.     int i;
  5.     for (i = 2; i < n; i++)
  6.         if (n % i == 0)
  7.             return 0;
  8.         return 1;
  9. }
  10. int main(void)
  11. {
  12.     int i;
  13.     for (i = 1; i <= 100; i++) {
  14.         if (is_prime(i))
  15.             printf("%d\n", i);
  16. }
  17. return 0;
  18. }

1、上面打印的小九九有一半数据是重复的，因为8*9和9*8的结果一样。请修改程序打印这样的小九九：
1
2 4
3 6 9
4 8 12 16
5 10 15 20 25
6 12 18 24 30 36
7 14 21 28 35 42 49
8 16 24 32 40 48 56 64
9 18 27 36 45 54 63 72 81

  1. void print_numbers(void)
  2. {
  3.     int i, j;
  4.     for(i=1; i<10; ++i) {
  5.         for(j=1; j<=i; ++j) {
  6.             printf("%d\t", i*j);
  7.         }
  8.         printf("\n");
  9.     }
  10. }

2、编写函数diamond打印一个菱形。如果调用diamond(3, '*')则打印：

    *
*   *   *
    *

如果调用diamond(5, '+')则打印：

        +
    +   +   +
+   +   +   +   +
    +   +   +
        +

如果用偶数做参数则打印错误提示。

  1. void diamod(int num, char graph)
  2. {
  3.     if(! num&1) {// %2 == 0
  4.         printf("wrong\n");
  5.         return;
  6.     }
  7.     int i, j, count;
  8.     count = -1;
  9.     for(i=num/2; i>=0; --i) {
  10.         count += 2;
  11.         for(j=i; j>0; --j)
  12.             printf("\t");
  13.         for(j=count; j>0; --j)
  14.             printf("%c\t", graph);
  15.         printf("\n");
  16.     }
  18.     for(i=num/2+1; i<num; ++i) {
  19.         for(j=i-num/2; j>0; --j)
  20.             printf("\t");
  21.         for(j=count-2; j>0; --j)
  22.             printf("%c\t", graph);
  23.         printf("\n");
  24.         count -= 2;
  25.     }
  26. }
  1. /* 宋老师答案 */
  2. void diamond(int n, char c)
  3. {
  4.     int i, j;
  5.     if (n <= 0 || !(n % 2))
  6.         return;
  7.     for (i = 1; i <= n/2+1; i++) {
  8.         for (j = 1; j <= n/2-i+1; j++)
  9.             printf("\t");
  10.         for (j = 1; j <= 2*i-1; j++)
  11.             printf("%c\t", c);
  12.         printf("\n");
  13.     }
  14.     for (i = 1; i <= n/2; i++) {
  15.         for (j = 1; j <= i; j++)
  16.             printf("\t");
  17.         for (j = 1; j <= n-2*i; j++)
  18.             printf("%c\t", c);
  19.         printf("\n");
  20.     }
  21. }

以下代码编译没有问题, 但运行结果却和预期不符合, 不能打印出other number, 请分析原因.

  1. #include <stdio.h>
  2. int main(void){
  3.     int n = 3;
  4.     switch(n) {
  5.         case 1:
  6.             printf("1\n");
  7.             break;
  8.         case 2:
  9.             printf("2\n");
  10.             break;
  11.         default:
  12.             printf("other number\n");
  13.     }
  14.     return 0;
  15. }

好像这道题目出错了? 能够正常运行并且打印的.

结构体

1、在本节的基础上实现一个打印复数的函数，打印的格式是x+yi，如果实部或虚部为0则省略，例如：1.0、-2.0i、-1.0+2.0i、1.0-2.0i。最后编写一个main函数测试本节的所有代码。想一想这个打印函数应该属于上图中的哪一层？

存储表示层

  1.     void print_complex(struct complex_struct z) {
  2.         if(z.real()==0 && z.imag()==0)
  3.             printf("0\n");
  4.         else if(z.real() == 0)
  5.             printf("%fi", z.imag());
  6.         else if(z.imag() == 0)
  7.             printf("%f", z.real());
  8.         else
  9.             printf("%f+%fi", z.real(), z.iamg());
  10.     }

2、实现一个用分子分母的格式来表示有理数的结构体rational以及相关的函数，rational结构体之间可以做加减乘除运算，运算的结果仍然是rational
注意要约分为最简分数，例如1/8和-1/8相减的打印结果应该是1/4而不是2/8，可以利用第 3 节 “递归”练习题中的Euclid算法来约分。在动手编程之前先思考一下这个问题实现了什么样的数据抽象，抽象层应该由哪些函数组成。

  1. struct Ragtional make_rational(int numerator, int denominator)
  2. {
  3.     struct Ragtional a;
  4.     a.numerator = numerator;
  5.     a.denominator = denominator;
  6.     return a;
  7. }
  8. struct Ragtional add_rational(struct Ragtional a, struct Ragtional b)//need to fix -
  9. {
  10.     struct Ragtional result;
  11.     int max, gcm;
  12.     max = GCD(a.denominator, b.denominator);
  13.     gcm = (a.denominator*b.denominator) / max;
  14.     printf("gcm is %d\n", gcm);
  15.     result.denominator = gcm;
  16.     result.numerator = (a.numerator*gcm/a.denominator) + (b.numerator*gcm/b.denominator);
  17.     printf("numerator is %d\n", result.numerator);
  18.     return result;
  19. }
  20. struct Ragtional mul_rational(struct Ragtional a, struct Ragtional b)
  21. {
  22.     struct Ragtional result;
  23.     result.numerator = a.numerator * b.numerator;
  24.     result.denominator = a.denominator * b.denominator;
  25.     return result;
  26. }
  27. struct Ragtional div_rational(struct Ragtional a, struct Ragtional b)
  28. {
  29.     struct Ragtional trans;
  30.     trans.numerator =  b.denominator;
  31.     trans.denominator = b.numerator;
  32.     return mul_rational(a, trans);
  33. }
  34. void print_rational(struct Ragtional a)
  35. {
  36.     int max;
  37.     max = GCD(a.numerator, a.denominator);
  38.     if(a.denominator/max == 1)
  39.         printf("%d\n", a.numerator/max);
  40.     else
  41.         printf("%d/%d\n", a.numerator/max, a.denominator/max);
  42. }

1、本节只给出了make_from_real_img和make_from_mag_ang函数的实现，请读者自己实现real_part、img_part、magnitude、angle这些函数。

  1.     double real_part(struct complex_struct z) {
  2.         if(z.t==RECTANGULAR)
  3.             return z.a;
  4.         else
  5.             return z.a*cos(z.b);
  6.     }
  8.     double imag_part(struct complex_struct z) {
  9.         if(z.t==RECTANGULAR)
  10.             return z.b;
  11.         else
  12.             return z.a*sin(z.b);
  13.         }
  15.     double magnitude(struct complex_struct z) {
  16.         if(z.t==RECTANGULAR)
  17.             return sqrt(z.a*z.a + z.b*z.b);
  18.         else
  19.             return z.a;
  20.         }
  22.     double angle(struct complex_struct z) {
  23.         if(z.t==RECTANGULAR) {
  24.             double PI = acos(-1.0);
  25.             if(z.a > 0)
  26.                 return atan(z.b/z.a);
  27.             else
  28.                 return atan(z.b/z.a) + PI;
  29.             } else
  30.                 return z.b;
  31.         }

2、编译运行下面这段程序：

  1. #include <stdio.h>
  2. enum coordinate_type { RECTANGULAR = 1, POLAR };
  3. int main(void)
  4. {
  5.     int RECTANGULAR;
  6.     printf("%d %d\n", RECTANGULAR, POLAR);
  7.     return 0;
  8. }

结果是什么？并解释一下为什么是这样的结果。

结果是 -1217339392 2， 原因是main函数中的未赋值RECTANGULAR变量覆盖了全局的enum变量。

数组

1、编写一个程序，定义两个类型和长度都相同的数组，将其中一个数组的所有元素拷贝给另一个。既然数组不能直接赋值，想想应该怎么实现。

  1.     void copy(char *a, char *b) {
  2.         int i;
  3.         for(i=0; b[i]; ++i)
  4.             a[i] = b[i];
  5.     }

1、用rand函数生成10~20之间的随机整数，表达式应该怎么写？

rand()%11 + 10

1、补完本节直方图程序的main函数，以可视化的形式打印直方图。例如上一节统计20个随机数的结果是：
0 1 2 3 4 5 6 7 8 9
* * * * * * * *
* * * * * * *
* * *
*
*

  1.     int j, sum;
  2.     for(i=0; i<=9; i++)
  3.         printf("%d ", i);
  4.     printf("\n");
  5.     for(i=0; i<=9; i++)
  6.         printf("%d ", histogram[i]);
  7.     printf("\n");
  8.     do {
  9.         sum = 0;
  10.         for(i=0; i<=9; i++)
  11.             sum += histogram[i];
  12.         for(j=0; j<=9; ++j) {
  13.             if(histogram[j]!=0) {
  14.                 printf("* ");
  15.                 --histogram[j];
  16.             }else
  17.                 printf("  ");
  18.         }
  19.         printf("\n");
  20.     } while(sum != 0);
  21.     return 0;

2、定义一个数组，编程打印它的全排列。比如定义：
#define N 3
int a[N] = { 1, 2, 3 };
则运行结果是：
$ ./a.out
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
1 2 3

code

完成了上述要求之后再考虑第二个问题：如果再定义一个常量M表示从N个数中取几个数做排列（N == M时表示全排列），原来的程序应该怎么改？
最后再考虑第三个问题：如果要求从N个数中取M个数做组合而不是做排列，就不能用原来的递归过程了，想想组合的递归过程应该怎么描述，编程实现它。

code

留给读者思考的问题是：(man - computer + 4) % 3 - 1这个神奇的表达式是如何比较出0、1、2这三个数字在“剪刀石头布”意义上的大小的？
胜 负 平 胜 负
man-computer -2 -1 0 1 2
man-computer+4 2 3 4 5 6
(man-computer+4)%3 2 0 1 2 0
(man-computer+4)%3-1 1 -1 0 1 -1

剪刀石头布相生相克，形成一个环，凡是具有环的特性的数学模型都可以考虑用取模运算，首先确定了man-computer和%3，然后再调整其它常数得到normalized的结果。

编码风格

gdb

看下面的程序:

  1. #include <stdio.h>
  2. int main(void)
  3. {
  4.     int i;
  5.     char str[6] = "hello";
  6.     char reverse_str[6] = "";
  7.     printf("%s\n", str);
  8.     for (i = 0; i < 5; i++)
  9.     reverse_str[5-i] = str[i];
  10.     printf("%s\n", reverse_str);
  11.     return 0;
  12. }

首先用字符串"hello"初始化一个字符数组str(算上'\0'共6个字符)。然后用空字符串""初始化一个同样长的字符数组reverse_str,相当于所有元素用'\0'初始化。然后打印str,把str倒序存入reverse_str,再打印reverse_str。然而结果并不正确: $ ./main hello
我们本来希望reverse_str打出来是olleh的,结果什么都没有。重点怀疑对象肯定是循环,那么简单验算一下,i=0时,reverse_str[5] = str[0],也就是'h',i=1时,reverse_str[4] = str[1],也就是'e',依此类推,i=0,1,2,3,4,共5次循环,正好把h,e,l,l,o五个字母给倒过来了,哪里不对了?
请调试修正这个Bug。

程序把'\0'也换到开头来了。应该改成 reverse_str[4-i] = str[i];

排序与查找

实现选择排序算法

code

1、为了便于初学者理解,本节的merge函数写得有些啰嗦,你能想出哪些办法将它化简?

code

2、快速排序是另外一种采用分而治之策略的排序算法，在平均情况下的时间复杂度也是Θ(nlgn)，但比归并排序有更小的时间常数。它的基本思想是这样的：
int partition(int start, int end)
{
从a[start..end]中选取一个pivot元素（比如选a[start]为pivot）;
在一个循环中移动a[start..end]的数据，将a[start..end]分成两半，
使a[start..mid-1]比pivot元素小，a[mid+1..end]比pivot元素大，而a[mid]就是pivot元素;
return mid;
}
void quicksort(int start, int end)
{
int mid;
if (end > start) {
mid = partition(start, end);
quicksort(start, mid-1);
quicksort(mid+1, end);
}
}
请补完partition函数，这个函数有多种写法，请选择时间常数尽可能小的实现方法。想想快速排序在最好和最坏情况下的时间复杂度是多少？快速排序在平均情况下的时间复杂度分析起来比较复杂，有兴趣的读者可以参考[算法导论]。

  1.     int partition(int a[], int start, int end)
  2.     {
  3.         int pivot = a[end];
  4.         while(start < end) {
  5.             while(start<end && a[start]<=pivot)
  6.                 ++start;
  7.             a[end] = a[start];
  8.             while(start<end && a[end]>=pivot)
  9.                 --end;
  10.             a[start] = a[end];
  11.         }
  12.         a[start] = pivot;
  13.         return start;
  14.     }

1、实现一个算法，在一组随机排列的数中找出最小的一个。你能想到的最直观的算法一定是Θ(n)的，想想有没有比Θ(n)更快的算法？

没有更快的算法，理由同上。

2、在一组随机排列的数中找出第二小的，这个问题比上一个稍复杂，你能不能想出Θ(n)的算法？

secondmin.c

3、进一步泛化，在一组随机排列的数中找出第k小的，这个元素称为k-th Order Statistic。能想到的最直观的算法肯定是先把这些数排序然后取第k个，时间复杂度和排序算法相同，可以是Θ(nlgn)。这个问题虽然比前两个问题复杂，但它也有平均情况下时间复杂度是Θ(n)的算法，将上一节习题1的快速排序算法稍加修改就可以解决这个问题：
/* 从start到end之间找出第k小的元素 */
int order_statistic(int start, int end, int k)
{
用partition函数把序列分成两半，中间的pivot元素是序列中的第i个;
if (k == i)
返回找到的元素;
else if (k > i)
从后半部分找出第k-i小的元素并返回;
else
从前半部分找出第k小的元素并返回;
}
请编程实现这个算法。

  1.     int order_statistic(int a[], int start, int end, int k)
  2.     {
  3.         int i;
  4.         if(end >= start) {
  5.             i = order_partition(a, start, end, k);
  6.             if(k == i)
  7.                 return a[i];
  8.             else if(k > i)
  9.                 return order_statistic(a, i+1, end, k);
  10.             else
  11.                 return order_statistic(a, start, i-1, k);
  12.         }
  13.     }

ordstat.c。可以分析一下为什么时间复杂度是Θ(n)，在最好情况下每次丢掉一半的元素，n+n/2+n/4+n/8+...=2n，平均情况下的分析比较复杂，但快速排序类似，时间复杂度和最好情况下一致。

1、本节的折半查找算法有一个特点：如果待查找的元素在数组中有多个则返回其中任意一个，以本节定义的数组int a[8] = { 1, 2, 2, 2, 5, 6, 8, 9 };为例，如果调用binarysearch(2)则返回3，即a[3]，而有些场合下要求这样的查找返回a[1]，也就是说，如果待查找的元素在数组中有多个则返回第一个。
请修改折半查找算法实现这一特性。

  1.     int binary_search(int a[], int low, int high, int element)
  2.     {
  3.         int mid = -2;
  4.         while(low <= high) {
  5.             mid = (low+high)/2;
  6.             if(a[mid] == element) {
  7.                 while(a[mid-1] == element)/* return first element */
  8.                     --mid;
  9.                 break;
  10.             }
  11.             else if(element < a[mid])
  12.                 high = mid-1;
  13.             else
  14.                 low = mid+1;
  15.         }
  16.         if(low > high)
  17.             return -2;
  18.         return mid;
  19.     }

2、编写一个函数double mysqrt(double y);求y的正平方根，参数y是正实数。我们用折半查找来找这个平方根，在从0到y之间必定有一个取值是y的平方根，如果我们查找的数x比y的平方根小，则x2y，我们可以据此缩小查找范围，当我们查找的数足够准确时（比如满足|x2-y|<0.001），就可以认为找到了y的平方根。思考一下这个算法需要迭代多少次？迭代次数的多少由什么因素决定？ 

  1.     double mysqrt(double y)
  2.     {
  3.         double low=0, high=y, mid = -2;
  4.         while(low < high) {
  5.             mid = (low+high)/2;
  6.             if(abs(pow(mid, 2)-y) < 0.00001)
  7.                 break;
  8.             else if(pow(mid, 2) < y)
  9.                 low = mid+0.00001;
  10.             else
  11.                 high = mid-0.00001;
  12.         }
  13.         return mid;
  14.     }

迭代次数取决于精度（可以用对数函数表示）

3、编写一个函数double mypow(double x, int n);求x的n次方，参数n是正整数。最简单的算法是：
double product = 1;
for (i = 0; i < n; i++)
product *= x;
这个算法的时间复杂度是Θ(n)。其实有更好的办法，比如mypow(x, 8)，第一次循环算出x·x=x2，第二次循环算出x2·x2=x4，第三次循环算出4·x4=x8。这样只需要三次循环，时间复杂度是Θ(lgn)。思考一下如果n不是2的整数次幂应该怎么处理。请分别用递归和循环实现这个算法。

从以上几题可以看出，折半查找的思想有非常广泛的应用，不仅限于从一组排好序的元素中找出某个元素的位置，还可以解决很多类似的问题。[编程珠玑]对于折半查找的各种应用和优化技巧有非常详细的介绍。

栈和队列

1、修改本节的程序，要求从起点到终点正向打印路线。你能想到几种办法？

dfs.c

2、本节程序中predecessor这个数据结构占用的存储空间太多了，改变它的存储方式可以节省空间，想想该怎么改。

计算出row*MAX_ROW+col，把结果保存到predecessor数组，可节省一半的存储，需要座标时可以用/MAX_ROW和%MAX_ROW运算把row和col分离出来

3、上一节我们实现了一个基于堆栈的程序，然后改写成递归程序，用函数调用的栈帧替代自己实现的堆栈。本节的DFS算法也是基于堆栈的，请把它改写成递归程序，这样改写可以避免使用predecessor数据结构，想想该怎么做。

new

1、本节的例子直接在队列元素中加一个指针成员表示前趋，想一想为什么上一节的例 12.3 “用深度优先搜索解迷宫问题”不能采用这种方法表示前趋？

因为出栈的元素被新入栈的元素覆盖了

2、在讲解例 12.1 “用堆栈实现倒序打印”时我们说“top总是指向栈顶元素的下一个元素”是堆栈
操作的Class Invariant,那么本节实现的队列操作的Invariant应该怎么描述?

xy

2、本节例子中给队列分配的存储空间是512个元素，其实没必要这么多，那么解决这个问题至少要分配多少个元素的队列空间呢？跟什么因素有关？

每个点最多入队一次，迷宫中有多少个点就最多需要多大的队列空间

1、现在把迷宫问题的要求改一下，只要求程序给出最后结论就可以了，回答“有路能到达终点”或者“没有路能到达终点”，而不需要把路径打印出来。请把例 12.4 “用广度优先搜索解迷宫问题”改用环形队列实现，然后试验一下解决这个问题至少需要分配多少个元素的队列空间。

bfs_circular.c

注意用%运算移动head和tail，具有环的特性的数学模型都可以考虑用取模运算。队列空的判断条件是head == tail;，队列满的判断条件是head == (tail + 1) % QSIZE;，必须保留一个元素未用，否则无法区分队空和队满。

1、将例 12.4 “用广度优先搜索解迷宫问题”改用环形队列实现。然后回答:
运行原来的程序要求queue数组至少有多长?不用跟踪程序的运行过程,你能很快答上来
吗?
改为环形队列之后要求queue数组至少有多长?

code

C语言本质

计算机中数的表示

1、二进制小数可以这样定义：
(0.A1A2A3...)2=A1×2-1+A2×2-2+A3×2-3+...
这个定义同时也是从二进制小数到十进制小数的换算公式。从本节讲的十进制转二进制的推导过程出发类比一下，十进制小数换算成二进制小数应该怎么算？

每次乘2取整。和除2反序取余的证明过程类似

2、再类比一下，八进制（或十六进制）与十进制之间如何相互换算

不过是把基数换成8或16

例如-1表示
成10000001,+1表示成00000001。思考一下,N个bit的Sign and Magnitude表示法能够表示
的最大整数和最小整数分别是多少?请写出算式。

最小整数 -2^(N-1)
最大整数 2^(N-1)-1

数据类型详解

运算符详解

1、下面两行 printf 打印的结果有何不同?请读者比较分析一下。
int i = 0xcffffff3;
printf("%x\n", 0xcffffff3>>2);
printf("%x\n", i>>2);

第一个printf里的是无符号数，而第二个里的i则是有符号数，有符号数字右移时，与无符号数的差异是负数。当是负数时，最高位移入1还是0是不确定的(Implementation-defined)。
因为0xcffffff3最高位是1,所以是负数，区别如上。

1、统计一个无符号整数的二进制表示中1的个数，函数原型是int countbit(unsigned int x);。

  1.     int countbit(unsigned int x)
  2.     {
  3.         int i = 31, count = 0;
  4.         for(; i>-1; --i)
  5.             if((x>>i)&1==1)
  6.                 ++count;
  7.         return count;
  8.     }

2、用位操作实现无符号整数的乘法运算，函数原型是unsigned int multiply(unsigned int x, unsigned int y);。例如：(11011)2×(10010)2=((11011)2<<1)+((11011)2<<4)。

test

3、对一个32位无符号整数做循环右移，函数原型是
unsigned int rotate_right(unsigned int x);。所谓循环右移就是把低位移出的部分补到高位上去，例如rotate_right(0xdeadbeef, 8)的值应该是0xfdeadbee。

test

1、请在网上查找有关RAID（Redundant Array of Independent Disks，独立磁盘冗余阵列）的资料，理解其实现原理，其实就是利用了本节的性质3和4。

这题可以讲一讲。

本节可以让学生根据教材附录做UTF-8和Unicode编码的相互转换

有一段代码:

  1. #include <stdio.h>
  2. int array[] = {123, 43, 21, 171, 42, 99, 216};
  3. #define LEN (sizeof(array) / sizeof(array[0]))
  4. int main(void){
  5.     int i, sum = 0;
  6.     for(i=0; i<LEN; i++)
  7.         sum += array[i];
  8.     printf("%d\n", sum);
  9.     return 0;
  10. }

如果把for循环写成这样: 

  1.     for(i=-1; i<LEN-1; i++)
  2.         sum += array[i+1];

结果和原来是否相同?

不. 结果会变成0. 因为sizeof求出的结果类型为unsigned int, 当int i=-1与unsigned int进行比较时, 会进行隐式类型提升, int 提升到unsigned int, 此时-1的二进制解读为unsigned int, 会变成非常大的大数, 比LEN-1要大.
(参见CSAPP): 尽可能不使用unsigned int, 因为坑非常多.

以下代码得到的sum是0xfff, 对吗?

  1. int i = 0;
  2. unsigned int sum = 0;
  3. for(; i<16; i++)
  4.     sum = sum + 1U<<i;

不对. 因为符号+的优先级高于<<, 所以代码不能正常工作.

以下代码定义了指针变量p并把它放在一个表达式中参与运算:

  1. char *p = "hello";
  2. size_t n = sizeof (int) * p;

虽然还没有学到指针类型, 但现在我们不关心运算结果, 而是关心表达式的语法解析.
sizeof (int) *p这个表达式应该怎么理解呢? 一种理解是sizeof(int)乘以p, 另一种理解是, *号, (int)和sizeof是依次作用于p的前缀运算符. 动手试验一下看看编译器是怎么理解的, 想想为什么编译器会这样理解.

编译器是理解为sizeof(int) 乘以p的.

1、以下代码查找和打印0~1024之间所有256的倍数,对吗?
int i = 0;
for (; i <= 1024; ++i) {
if (i & 0xff == 0) {
printf("%d\n",i);
}
}

不对;优先级错误，if应该改成if( (i&0xff) == 0)
修改后符合if判断的有0x0, 0x100等，因为0x100根据二进制转换可知0x100=2^8=256, 。随后的后八位是0x00的数都是256的2的倍数。如：

计算机体系结构基础

x86汇编程序基础

*1、把本节例子中的 int $0x80 指令去掉,汇编、链接也能通过,但是执行的时候出现段错误。
你能解释其原因吗?

如果把int 去掉，在执行完指令4, %ebx之后要取下一条指令上来执行，而程序中没有写下一条指令，就要从程序被加载的内存位置之后取指令上来执行，结果是未知的：也许执行了未知的指令，也许存在那里的数据不是合法的指令格式，也许那个内存地址根本没有映射到物理地址。如果有int $0x80指令，CPU执行到这里就会进内核去执行，并且再也不会回来了，就不会取到后面的未知指令。

汇编与C之间的关系

1、在第 2 节 “自定义函数”讲过，Old Style C风格的函数声明可以不指定参数个数和类型，这样编译器不会对函数调用做检查，那么如果调用时的参数类型不对或者参数个数不对会怎么样呢？比如把本节的例子改成这样：
int foo();
int bar();
int main(void)
{
foo(2, 3, 4);
return 0;
}
int foo(int a, int b)
{
return bar(a);
}
int bar(int c, int d)
{
int e = c + d;
return e;
}
main函数调用foo时多了一个参数，那么参数a和b分别取什么值？多的参数怎么办？foo调用bar时少了一个参数，那么参数d的值从哪里取得？请读者利用反汇编和gdb自己分析一下。

调用foo(2, 3, 4)，a和b的取值是2和3，多的参数未使用，调用时压栈，返回时出栈，并没有什么影响；如果调用bar(a)，则参数d的值是从栈帧上强行取来的，结果是未知的。

1、编写一个程序，测试运行它的平台是大端还是小端字节序。

  1. union {
  2.     int n;
  3.     unsigned char byte[4];
  4. } a;

链接详解

预处理

Makefile基础

指针

1、对照本节的描述，像图 23.1 “指针的基本概念”那样画图理解函数的调用和返回过程。在下一章我们会看到更复杂的参数和返回值形式，在初学阶段对每个程序都要画图理解它的运行过程，只要基本概念清晰，无论多复杂的形式都应该能正确分析。

2、现在回头看第 3 节 “形参和实参”的习题1，那个程序应该怎么改？

int a

1、想想以下定义中的 const 分别起什么作用?编写程序验证你的猜测。
const char **p;
char *const *p;
char **const p;

1.char **p为常量
2.*p为常量，指向char *
3.p

分析以下复杂声明

  1. char (*(*x(void))[3])(void);

函数接口

1、定义以下变量:
char a[4][3][2] = {{{'a', 'b'}, {'c', 'd'}, {'e', 'f'}},
{{'g', 'h'}, {'i', 'j'}, {'k', 'l'}},
{{'m', 'n'}, {'o', 'p'}, {'q', 'r'}},
{{'s', 't'}, {'u', 'v'}, {'w', 'x'}}};
char (*pa)[2] = &a[1][0];
char (*ppa)[3][2] = &a[1];
要想通过 pa 或 ppa 访问数组 a 中的 'r' 元素,分别应该怎么写?

pa[5][1]
ppa[1][2][1]

strcpy中还强调了 src 和 dest 所指向的内存空间不能有重叠。凡是有指针参数的C标准库函
数基本上都有这条要求,每个指针参数所指向的内存空间互不重叠,例如这样调用是不允许
的:
char buf[10] = "hello";
strcpy(buf, buf+1);

可是我的程序却没有错误。

自己实现一个 strcpy 函数,尽可能简洁,你能用三行代码写出函数体吗?

  1.     /* 我的实现 */
  2.     char *my_strcpy(char *dest, const char*src)
  3.     {
  4.         char *temp = dest;
  5.         while(*src)
  6.             *dest++ = *src++;
  7.         return temp;
  8.     }
  10.     /* linux的实现 参照：http://www.chinaunix.net/old_jh/23/25356.html */
  11.     char * strcpy(char * strDest,const char * strSrc)
  12.     {
  13.         if ((strDest==NULL)||(strSrc==NULL)) //[1]
  14.                 throw "Invalid argument(s)"; //[2]
  15.         char * strDestCopy=strDest;  //[3]
  16.         while ((*strDest++=*strSrc++)!='\0'); //[4]
  17.         return strDestCopy;
  18.     }

编一个函数,输入一个字符串,要求做一个新字符串,把其中所有的一个或多个连续的空白字符都压缩为一个空格。这里所说的空白包括空格、'\t'、'\n'、'\r'。例如原来的字符串是:
This Content hoho
ok?
file system
uttered words
ok ok
end.
is ok
?
压缩了空白之后就是:
This Content hoho is ok ok? file system uttered words ok ok ? end.
实现该功能的函数接口要求符合下述规范:
char *shrink_space(char *dest, const char *src, size_t n);
各项参数和返回值的含义和 strncpy 类似。完成之后,为自己实现的函数写一个Man Page。

  1.     char *my_strcpy(char *dest, const char*src)
  2.     {
  3.         char *temp = dest;
  4.         while((*dest++ = *src++) != '\0')
  5.             /* do nothing */;
  6.         return temp;
  7.     }
  8.     bool is_space(char c)
  9.     {
  10.         if(c==' ' || c=='\t' || c=='\n' || c=='\r')
  11.             return true;
  12.         else
  13.             return false;
  14.     }
  15.     char *shrink_space(char *dest, const char *src, size_t n)
  16.     {
  17.         size_t i=0, j=0;
  18.         while(i<n && src[i]) {
  19.             if(is_space(src[i])) {
  20.                 dest[j++] = ' ';
  21.                 while(is_space(src[++i]))
  22.                     ;
  23.             }else
  24.                 dest[j++] = src[i++];
  25.         }
  26.         /* my implementation                  https://github.com/YongHaoWu/algorithm_and_datastruct/blob/master/algorithms/my_strcpy.c
  27.         size_t i, j;
  28.         for(j=0,i=0; i<n && src[i]!='\0'; ++i) {
  29.             if(is_space(src[i]) && is_space(src[i+1])) {
  30.                 continue;
  31.             }else {
  32.                 dest[j] = src[i];
  33.                 ++j;
  34.             }
  35.         }
  36.         */
  37.         for(; i<n; ++i)
  38.             dest[i] = '\0';
  39.         return dest;
  40.     }

1、[K&R]的5.6节有一个qsort函数的实现，可以对一组任意类型的对象做快速排序。请读者仿照那个例子，写一个插入排序的函数和一个折半查找的函数。

generics.c

1、实现一个功能更完整的printf，能够识别%，能够处理%d、%f对应的整数参数。在实现中不许调用printf(3)这个Man Page中描述的任何函数。

我的实现，思路基于wine开源项目，比宋老师的实现要好：https://github.com/YongHaoWu/algorithm_and_datastruct/blob/master/algorithms/myprintf.c
其实要完美实现%f打印，难度是非常高的。我自己比较好的实现是在： https://github.com/YongHaoWu/algorithm_and_datastruct/blob/master/algorithms/my_sprintf.c
但是还是不正确的。
更多资料请查阅Dragon4算法或Grisu算法。

C标准库

在系统头文件中找到各种错误码的宏定义

用fgets/fputs编写一个拷贝文件的程序, 根据本节对fgets函数的分析, 这个程序应该只能拷贝文本文件, 试试用它拷贝二进制文件会出现什么问题.

xx

用scanf读入一个字符串, 然后自己编写代码将它转换成整数, 你能给出什么办法?

xy

本节的函数全都要求学生自己实现一遍
memset
strlen
memcpy和memmove，restrict关键字，strdup
strcat和strncat
memcmp，strcmp和strncmp，strcasecmp和strncasecmp
strchr和strrchr，strstr

example

1、出于练习的目的，strtok和strtok_r函数非常值得自己动手实现一遍，在这个过程中不仅可以更深刻地理解这两个函数的工作原理，也为以后理解“可重入”和“线程安全”这两个重要概念打下基础。

  1.     char *mystrtok(char *str, const char *delim)
  2.     {
  3.         char *head = str;
  4.         static char *saver;
  5.         if(str)
  6.             saver = str;
  7.         else
  8.             head = saver;
  9.         if(! *saver)
  10.             return NULL;
  11.         for(; *saver!=*delim; ++saver) {
  12.             if(! *(saver+1)) {
  13.                 ++saver;
  14.                 break;
  15.             }
  16.         }
  17.         while(*saver == *delim) {
  18.             *saver = '\0';
  19.             ++saver;
  20.         }
  21.         return head;
  22.     }
  24.     char *mystrtok_r(char *str, const char *delim, char **saveptr)
  25.     {
  26.         char * head = str;
  27.         if(! *str)
  28.             return NULL;
  29.         for(; *str!=*delim; ++str) {
  30.             if(! *(str+1)) {
  31.                 ++str;
  32.                 break;
  33.             }
  34.         }
  35.         while(*str == *delim) {
  36.             *str = '\0';
  37.             ++str;
  38.         }
  39.         *saveptr = str;
  40.         return head;
  41.     }

2、解析URL中的路径和查询字符串。动态网页的URL末尾通常带有查询，例如：
http://www.google.cn/search?complete=1&hl=zh-CN&ie=GB2312&q=linux&meta=
http://www.baidu.com/s?wd=linux&cl=3
比如上面第一个例子，http://www.google.cn/search是路径部分，?号后面的complete=1&hl=zh-CN&ie=GB2312&q=linux&meta=是查询字符串，由五个“key=value”形式的键值对（Key-value Pair）组成，以&隔开，有些键对应的值可能是空字符串，比如这个例子中的键meta。
现在要求实现一个函数，传入一个带查询字符串的URL，首先检查输入格式的合法性，然后对URL进行切分，将路径部分和各键值对分别传出，请仔细设计函数接口以便传出这些字符串。如果函数中有动态分配内存的操作，还要另外实现一个释放内存的函数。完成之后，为自己设计的函数写一个Man Page。

  1.     int parse_url(char *url, char **buffer)
  2.     {
  3.         int i = 0;
  4.         char *saveptr = NULL;
  5.         //char *result = mystrtok(url, "?");
  6.         char *result = mystrtok_r(url, "?", &saveptr);
  7.         if(result == NULL)
  8.             printf("NULL\n");
  10.         while(1) {
  11.             buffer[i] = malloc(100);
  12.             memset(buffer[i], 0, 100);
  13.             //result = mystrtok(NULL, "&");
  14.             result = mystrtok_r(saveptr, "&", &saveptr);
  15.             if(result == NULL)
  16.                 break;
  17.             memmove(buffer[i++], result, strlen(result));
  18.         }
  19.         return i;
  20.     }
  22.     void release_url(char **buffer, int num)
  23.     {
  24.         int i;
  25.         for(i=0; i<num; ++i)
  26.             free(buffer[i]);
  27.     }

1、在系统头文件中找到各种错误码的宏定义。

man errno

2、做几个小练习,看看 fopen 出错有哪些常见的原因。
打开一个没有访问权限的文件。
fp = fopen("/etc/shadow", "r");
if (fp == NULL) {
perror("Open /etc/shadow");
exit(1);
}
fopen 也可以打开一个目录,传给 fopen 的第一个参数目录名末尾可以加 / 也可以不加 / ,但只允
许以只读方式打开。试试如果以可写的方式打开一个存在的目录会怎么样呢?
fp = fopen("/home/akaedu/", "r+");
if (fp == NULL) {
perror("Open /home/akaedu");
exit(1);
}
请读者自己设计几个实验,看看你还能测试出哪些错误原因?

  1.     FILE *file1;
  2.     if(!(file1 = fopen("dir1","r+")))
  3.         perror("open dir read\n");
  4.     if(!(file1 = fopen("dir1","w+")))
  5.         perror("open dir write\n");
  6.     if(!(file1 = fopen("dir2/file2","w+")))
  7.         perror("open dir only excute flie\n");
  8.     if(!(file1 = fopen("dir2/fi","r+")))
  9.         perror("open dir not exisits flie\n");
  10.     if(!(file1 = fopen("/etc/shadow","r+")))
  11.         perror("open right\n");

1、编写一个简单的文件复制程序。
$ ./mycp dir1/fileA dir2/fileB
运行这个程序可以把 dir1/fileA 文件拷贝到 dir2/fileB 文件。注意各种出错处理

  1.     #include <stdio.h>
  2.     #include <stdlib.h>
  3.     int main(void)
  4.     {
  5.         FILE *file1, *file2;
  6.         int ch;
  7.         if(!(file1 = fopen("dir1/fileA","r+"))) {
  8.             perror("open file1\n");
  9.             exit(1);
  10.         }
  11.         if(!(file2 = fopen("dir2/fileB","w+"))) {
  12.             perror("open file2\n");
  13.             exit(1);
  14.         }
  15.         while((ch=fgetc(file1)) != EOF)
  16.             fputc(ch, file2);
  17.         fclose(file1);
  18.         fclose(file2);
  19.         return 0;
  20.     }

2、虽然我说 getchar要读到换行符才返回,但上面的程序并没有提供证据支持我的说法,如果看成每敲一个键 getchar 就返回一次,也能解释程序的运行结果。请写一个小程序证明 getchar 确 实是读到换行符才返回的。

  1.     #include <stdio.h>
  2.     int main(void)
  3.     {
  4.         while(1)
  5.             printf("%c\n", getchar());
  6.         return 0;
  7.     }

1、用 fgets / fputs 写一个拷贝文件的程序,根据本节对 fgets 函数的分析,应该只能拷贝文本文
件,试试用它拷贝二进制文件会出什么问题

乱码。

  1.     #include <stdio.h>
  2.     #include <stdlib.h>
  3.     int main(void)
  4.     {
  5.         FILE *file1, *file2;
  6.         if(!(file1 = fopen("a.out","r+"))) {
  7.             perror("open file1\n");
  8.             exit(1);
  9.         }
  10.         if(!(file2 = fopen("dir2/file2","w+"))) {
  11.             perror("open file2\n");
  12.             exit(1);
  13.         }
  15.         char *s = (char*)malloc(100);
  16.         fgets(s, 100, file1);
  17.         fputs(s, stdout);
  19.         fclose(file1);
  20.         fclose(file2);
  21.         return 0;
  22.     }

小练习:编写一个小程序让它耗尽系统内存。观察一下,分配了多少内存后才会出现分配失
败?内存耗尽之后会怎么样?会不会死机?

如果有函数接口 void func(const int p); 这里的 const 有意义吗?

没有

这里的参数指针是 const char ** ,有 const 限定符,却不是传入参数而
是传出参数,为什么?如果是传入参数应该怎么表示?

传入参数：char const **

为什么在 main 函数中不能直接调用 free(p) 释放内存,而要调用 free_unit(p) ?为什
么一层指针的函数接口 void alloc_unit(unit_t *p); 不能分配内存,而一定要用两层指针的函
数接口?

Nope

  1.     #include <stdio.h>
  2.     #include <string.h>
  3.     static const char *msg[] = {"Sunday", "Monday",
  4.         "Tuesday", "Wednesday",
  5.         "Thursday", "Friday",
  6.         "Saturday"};
  7.     char *get_a_day(int idx)
  8.     {
  9.         static char buf[20];
  10.         strcpy(buf, msg[idx]);
  11.         return buf;
  12.     }
  13.     int main(void){
  14.         printf("%s %s\n", get_a_day(0), get_a_day(1));
  15.         return 0;
  16.     }

这个程序的运行结果是 Sunday Monday 吗?请读者自己分析一下
不是，是Sunday Sunday。因为在函数里的buf是static类型，所以它的内存地址固定不变。当使用printf时，因为参数的压栈出栈会从右到左运行函数（即先运行get_a_day(1)) ，再调用的是get_a_day(0),所以buf变成了Sunday，而两个get_a_day函数都是返回buf的地址，所以结果都是Sunday。
**注意: ** : 在mac(clang)上, 压栈出栈是从左到右, 结果是两个Monday.
结果取决于函数默认调用是什么.
linux上(gcc), 默认是用_cdecl约定, 按从右至左的顺序压参数入栈.
苹果上(clang) 不知道是什么约定, 从左到右的, 被它坑了. 我还以为跟linux上一样, 一直在想, 究竟是入栈的时候调用函数还是出栈.

现在确定了是入栈的时候就调用了

[K&R]的5.6节有一个 qsort 函数的实现,可以对一组任意类型的对象做快速排序。请读者仿
照那个例子,写一个插入排序的函数和一个折半查找的函数。

code

1、编程读写一个文件 test.txt ,每隔1秒向文件中写入一行记录,类似于这样:
1,
2,
2007-7-30 15:16:42
2007-7-30 15:16:43
该程序应该无限循环,直到按Ctrl-C终止。下次再启动程序时在 test.txt 文件末尾追加记录,并
且序号能够接续上次的序号,比如:
1,
2,
3,
4,
5,
2007-7-30
2007-7-30
2007-7-30
2007-7-30
2007-7-30
15:16:42
15:16:43
15:19:02
15:19:03
15:19:04
这类似于很多系统服务维护的日志文件,例如在我的机器上系统服务进程 acpid 维护一个日志文
件 /var/log/acpid ,就像这样:
$ cat /var/log/acpid
[Sun Oct 26 08:44:46 2008] logfile reopened
[Sun Oct 26 10:11:53 2008] exiting
[Sun Oct 26 18:54:39 2008] starting up
...
每次系统启动时 acpid 进程就以追加方式打开这个文件,当有事件发生时就追加一条记录,包括事件发生的时刻以及事件描述信息。
获取当前的系统时间需要调用 time(2) 函数,返回的结果是一个 time_t 类型,其实就是一个大整
数,其值表示从UTC(Coordinated Universal Time)时间1970年1月1日00:00:00(称
为UNIX系统的Epoch时间)到当前时刻的秒数。然后调用 localtime(3) 将 time_t 所表示
的UTC时间转换为本地时间(我们是+8区,比UTC多8个小时)并转成 struct tm 类型,该类型
的各数据成员分别表示年月日时分秒,具体用法请查阅Man Page。调用 sleep(3) 函数可以指定
程序睡眠多少秒。

code

2、INI文件是一种很常见的配置文件,很多Windows程序都采用这种格式的配置文件,
在Linux系统中Qt程序通常也采用这种格式的配置文件。比如:
;Configuration of http
[http]
domain=www.mysite.com
port=8080
cgihome=/cgi-bin
;Configuration of db
[database]
server = mysql
user = myname
password = toopendatabase
一个配置文件由若干个Section组成,由[]括号括起来的是Section名。每个Section下面有若干个 key = value 形式的键值对(Key-value Pair),等号两边可以有零个或多个空白字符(空格
或Tab),每个键值对占一行。以;号开头的行是注释。每个Section结束时有一个或多个空行,
空行是仅包含零个或多个空白字符(空格或Tab)的行。INI文件的最后一行后面可能有换行符
也可能没有。
现在XML兴起了,INI文件显得有点土。现在要求编程把INI文件转换成XML文件。上面的例子经
转换后应该变成这样:

  1. <!-- Configuration of http -->
  2. <http>
  3. <domain>www.mysite.com</domain>
  4. <port>8080</port>
  5. <cgihome>/cgi-bin</cgihome>
  6. </http>
  7. <!-- Configuration of db -->
  8. <database>
  9. <server>mysql</server>
  10. <user>myname</user>
  11. <password>toopendatabase</password>
  12. </database>
  13. ````
  14. code 
  16. > 3、实现类似 gcc 的 -M 选项的功能,给定一个 .c 文件,列出它直接和间接包含的所有头文件,例
  17. 如有一个 main.c 文件:
  21. <div class="md-section-divider"></div>
#include <errno.h>
#include "stack.h"
int main()
{
return 0;
}

```
你的程序读取这个文件,打印出其中包含的所有头文件的绝对路径:
$ ./a.out main.c
/usr/include/errno.h
/home/akaedu/stack.h: cannot find
/usr/include/features.h
/usr/include/bits/errno.h
/usr/include/linux/errno.h
......
如果有的头文件找不到,就像上面例子那样打印 /home/akaedu/stack.h: cannot find 。首先复
习一下第 2.2 节 “头文件”讲过的头文件查找顺序,本题目不必考虑 -I 选项指定的目录,只
文件所在的目录以及系统目录 /usr/include 中查找。

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注