AOAPC 读书笔记 Ⅰ

Posted on

程序设计入门

算术表达式

整数 / 整数 = 整数，浮点数 / 浮点数 = 浮点数。

变量及其输入

scanf 中占位符和变量的数据类型一一对应，每个变量前需要加“&”符号；
输入输出过程是自动的，没有人工干预。输入前不要打印提示信息，输出完毕后应立即终止程序；
尽量用 const 关键字声明常数。

顺序结构程序设计

交换变量：

  • 三变量法（适用范围广，推荐使用）

    1
    2
    3
    t = a;
    a = b;
    b = t;

  • 加减法

    1
    2
    3
    4
    a = a + b;
    b = a - b;
    a = a - b;
    // 可用异或运算`^`代替加法和减法

  • KISS 法

    1
    2
    3
    // 比谁能更好地解决问题
    scanf("%d%d", &a, &b);
    printf("%d %d\n", b, a);

分支结构程序设计

单个整数值可以表示真假，其中 0 为假，其他值为真；
C 语言中的逻辑运算符都是短路（short-circuit）运算符；
有多个并列、情况不交叉的条件需要一一处理，用 else if 语句。

小结

gets 在 C11 中被移除了，ANSI C 即 C89；
需要把 C 语言程序当作 C++ 程序提交，学习的是 C++ 语言中与 C 兼容的部分；
\n：n 是英文单词 newline 的首字母；
编译器会把双斜线“\\”理解成单个字符“\”。
两条建议：

  • 重视实验
  • 学会模仿

循环结构程序设计

for 循环

要特别留意“当前行”的跳转和变量的改变；
有经验的程序员总是尽量缩小变量定义的范围；
使用伪代码来思考和描述算法是一种值得推荐的做法；
进行浮点数比较时，应考虑浮点误差。四舍五入，即 floor(x+0.5)；
continue 可以帮助我们偷懒，不必求出循环的起始点；有了 break，连循环终点也不必指定；
for(;;) 是一个死循环，三部分都是可以省略的。

while 循环和 do-while 循环

对于 n 不是“递增式”的循环，很适合用 while 循环来实现；
当需要统计某种事物的个数时，可以用一个变量来充当计数器；
int 都是 32 位整数，范围是 -2147483648～2147483637；
long long 在 Linux 下的输入输出格式符为 %lld，Windows 下有时为 %I64d。

循环的代价

可以使用 time.h 和 clock() 函数获得程序运行时间，返回值应除以 CLOCKS_PER_SEC；
Windows 命令行下执行“echo 20 | 程序名”，操作系统会自动把 20 输入。
两个实用工具：

  • 输出中间结果
  • 计时函数

输入输出框架

对于 scanf，空格、TAB、回车都是无关紧要的；
变量在未赋值之前的值是不确定的，不一定等于 0。
一个技巧：
先读取第一个整数 x，然后令 max = min = x；
有经验的程序员往往会使用条件编译编译指令并且将重要的测试语句注释掉而非删除。
重定向和 fopen 两种方法各有优劣：

  • 重定向的方法写起来简单、自然，但不能同时读写文件；
  • fopen 的写法稍嫌繁琐，但灵活性比较大。

程序的鲁棒性在工程中也非常重要；
多数据的题目中，一个常见的错误：计算完一组数据后某些变量没有重置，影响到下组数据的求解；
嵌套中有同名变量时，内层变量会屏蔽外层变量。

用编译选项 -Wall 编译程序时，会给出很多警告信息。

数组和字符串

数组

在空间够用的前提下，数组会声明得稍大一些；
“++”运算符是 C 语言的特色之一；
比较大的数组应尽量声明在 main 函数外。
数组 a 复制 k 个元素到数组 b：

1
memcpy(b, a, sizeof(int) * k);

数组 a 全部复制到数组 b 中：

1
memcpy(b, a, sizeof(a));

把数组 a 清零：

1
memset(a, 0, sizeof(a));

为了避免输出多余空格，可以设置一个标志变量 first：

1
2
3
4
5
6
7
8
9
10
11
// 第一个变量前没有空格，其他变量都有
int first = 1;
if(first == 1)
{
    first = 0;
}
else
{
    printf(" ");
}
printf("%d", i);

用一条语句完成许多事情的前提是：保持代码的可读性。

最好是在做一件事情之前检查是不是可以做，而不要做完再后悔。

字符数组

字符串其实就是字符数组；
以反斜线开头的字符称为转义序列（Escape Sequence）；
字符常量可以用’a’表示，语法上可以把字符当作 int 型使用；
字符串数组 char s[a][b]，可以用 scanf(“%s”, s[i]) 读取第 i 个字符串；
scanf(“%s”, s) 遇到空白字符会停下来；
strchr 的作用是在一个字符串中查找单个字符首次出现的位置；
strlen(s) 返回字符串 s 中结束标记“\0”之前的字符个数；
“++”、“+=”等，每条语句最多只用一次这种运算符。

题目选讲

读取一个字符可以用 getchar，它等价于 fgetc(stdin)；
在使用 fgetc 和 getchar 时，应避免写出和操作系统相关的程序。

1
2
3
4
5
int c;
while((c = getchar()) != EOF)
{
    ... ...
}

fgets(buf, maxn, fin)，读取完整的一行存放在字符数组 buf 中；
善用常量数组往往能简化代码，定义时无须指明大小；
头文件 ctype.h 中定义的 isalpha、isdigit、isprint 等工具可以用来判断字符的属性；
字符串数组，就是二维字符数组。

小结

作为数组下标，i 经常代表“当前考虑的位置”；
八进制应写成“\o”，十六进制应写成“\x”；
“<<”运算符的优先级没有减法高；
多数计算机内部，整数采用的是补码表示法；
一个好玩的 bug，两种不同的 0：

  • 00000000（正零）
  • 10000000（负零）

数组的大小可以用 sizeof 在编译时获得（它不是一个函数）；
按照自己的方式处理字符串，千万要保证它以“\0”结尾；
如果 char 值为正，则是西文字符；如果为负，则是汉字的前一半（需再读一个 char）。