C Primer Plus 第6版中文版 8~10章

第8章 字符输入/输出和输入验证

单字符I/O:getchar()和 putchar()

getchar() 和 putchar() 每次只处理一个字符,与我们的阅读方式相差甚远。 但是, 这种方法很适合计算机。 而且, 这是绝大多数文本( 即, 普通文字) 处理程序所用的核心方法。

#include <stdio.h>

int main(void) {
    // 该程序获取从键盘输入的字符, 并把这些字符发送到屏幕上。 程序使用 while 循环, 当读到# 字符时停止。
    char ch;
    int maxLen = 50;
    int i = 0;

    printf("请输入字符串,以#结束:\n");
    while (((ch = getchar()) != '#') && i < 50) {
        putchar(ch); // 在标准输出上打印字符 ch
        i += 1;
    }

    printf("\n");
    return 0;
}
/*
输入50个字符的例子, 每输入10个字符按 ENTER (回车键也算一个字符的)

- 按回车键才会执行 While 循环回显
- 每行不算回车键输入10个字符,第四次按回车键已经输入 40 +4 =44 个字符
- 所以最后一行即使输入超过了10个字符, 也只回显了6个字符,因为已经超过50个字符跳出 while循环了


请输入字符串,以#结束:
0123456789
0123456789
abcdefghij
abcdefghij
klmnopqrst
klmnopqrst
0123456789
0123456789
abcdefghijkl
abcdef

输入#结束的例子:

请输入字符串,以#结束:
adcdefg   hello#kitty
adcdefg   hello
*/

缓冲区

如果在老式系统运行程序清单, 可能会立刻回显用户的输入, 比如输入 Hello, 屏幕显示 HHeelllloo, 像这样回显用户输入的字符后立即重复打印该字符是属于无缓冲 (或直接 )输入, 即正在等待的程序可立即使用输入的字符。

大部分系统在用户按下 Enter 键之前不会重复打印刚输入的字符, 这种输入形式属于缓冲输入。 用户输入的字符被收集并存储在一个被称为缓冲区 (buffer )的临时存储区, 按下 Enter 键后, 程序才可使用用户输入的字符。

缓冲输入和无缓冲输入示例:

为什么要有缓冲区?

  • 首先, 把若干字符作为一个块进行传输比逐个发送这些字符节约时间。
  • 其次, 如果用户打错字符, 可以直接通过键盘修正错误。 当最后按下 Enter 键时, 传输的是正确的输入。

虽然缓冲输入好处很多, 但是某些交互式程序也需要无缓冲输入。 例如, 在游戏中, 你希望按下一个键就执行相应的指令。 因此, 缓冲输入和无缓冲输入都有用武之地。

缓冲分为两类: 完全缓冲 I/ O 和行缓冲 I/ O。

  • 完全缓冲输入指的是当缓冲区被填满时才刷新缓冲区( 内容被发送至目的地), 通常出现在文件输入中。 缓冲区的大小取决于系统, 常见的大小是 512 字节和 4096 字节。
  • 行缓冲 I/ O 指的是在出现换行符时刷新缓冲区。 键盘输入通常是行缓冲输入, 所以在按下 Enter 键后才刷新缓冲区。

ANSI C 和后续的 C 标准都规定输入是缓冲的, ANSI 没有提供调用无缓冲输入的标准方式, 这意味着是否能进行无缓冲输入取决于计算机系统。 本书假设所有的输入都是缓冲输入。

文件、 流和键盘输入

文件 (file )是存储器中存储信息的区域。 通常, 文件都保存在某种永久存储器中( 例如, 硬盘、 U 盘或 DVD 等)。

从概念上看, C 程序处理的是流而不是直接处理文件。 流 (stream )是一个实际输入或输出映射的理想化数据流。 这意味着不同属性和不同种类的输入, 由属性更统一的流来表示。 于是, 打开文件的过程就是把流与文件相关联, 而且读写都通过流来完成。

本章着重理解 C 把输入和输出设备视为存储设备上的普通文件, 尤其是把键盘和显示设备视为每个 C 程序自动打开的文件。 stdin 流表示键盘输入, stdout 流表示屏幕输出。 getchar() 、putchar() 、printf() 和 scanf()函数都是标准 I/ O 包的成员, 处理这两个流。

  • 输入输出文件: 键盘,屏幕
  • 输入输入文件对应的流: stdin,stdout
  • 处理这两个流的函数: getchar(),scanf(); putchar() 、printf()

以上讨论的内容说明, 可以用处理文件的方式来处理键盘输入。 例如, 程序读文件时要能检测文件的末尾才知道应在何处停止。 因此, C 的输入函数内置了文件结尾检测器。 既然可以把键盘输入视为文件, 那么也应该能使用文件结尾检测器结束键盘输入。

文件结尾

计算机操作系统要以某种方式判断文件的开始和结束。 检测文件结尾的一种方法是, 在文件末尾放一个特殊的字符标记文件结尾。 CP/ M、 IBM-DOS 和 MS-DOS 的文本文件曾经用过这种方法。 如今, 这些操作系统可以使用内嵌的 Ctrl + Z 字符来标记文件结尾。 这曾经是操作系统使用的唯一标记, 不过现在有一些其他的选择, 例如记录文件的大小。 所以现代的文本文件不一定有嵌入的 Ctrl + Z (^Z), 但是如果有, 该操作系统会将其视为一个文件结尾标记。

操作系统使用的另一种方法是存储文件大小的信息。 如果文件有 3000 字节, 程序在读到 3000 字节时便达到文件的末尾。 MS-DOS 及其相关系统使用这种方法处理二进制文件, 因为用这种方法可以在文件中存储所有的字符, 包括 Ctrl + Z。 新版的 DOS 也使用这种方法处理文本文件。 UNIX 使用这种方法处理所有的文件。

无论操作系统实际使用何种方法检测文件结尾, 在 C 语言中, 用 getchar() 读取文件检测到文件结尾时将返回一个特殊的值, 即 EOF (end of file 的缩写)。 scanf() 函数检测到文件结尾时也返回 EOF 。通常, EOF 定义在 stdio.h 文件中:

#define EOF (-1)

EOF 是 getchar() 函数的返回值, 而不是该函数读取到的内容.

为什么是-1 ?因为 getchar() 函数的返回值通常都介于 0 ~ 127 ,这些值对应标准字符集。 但是, 如果系统能识别扩展字符集, 该函数的返回值可能在 0 ~ 255 。无论哪种情况,-1 都不对应任何字符, 所以, 该值可用于标记文件结尾。

某些系统也许把 EOF 定义为-1 以外的值, 但是定义的值一定与输入字符所产生的返回值不同。 如果包含 stdio.h 文件, 并使用 EOF 符号, 就不必担心 EOF 值不同的问题。 这里关键要理解 EOF 是一个值, 标志着检测到文件结尾, 并不是在文件中找得到的符号, 也不一定是 -1。

如何在程序中使用 EOF ?把 getchar() 的返回值和 EOF 作比较。 如果两值不同, 就说明没有到达文件结尾。 也就是说, 可以使用下面这样的表达式:

while (( ch = getchar()) != EOF)

绝大部分系统( 不是全部) 都有办法通过键盘模拟文件结尾条件。使用 程序进行键盘输入, 要设法输入 EOF 字符。 不能只输入字符 EOF(这是三个独立的字符) ,也不能只输入-1 (输入-1 会传送两个字符: 一个连字符和一个数字 1 )。 正确的方法是, 必须找出当前系统的要求。 例如,

  • 在大多数 UNIX 和 Linux 系统中, 在一行开始处按下 Ctrl + D 会传输文件结尾信号。
  • 许多微型计算机系统都把一行开始处的 Ctrl + Z 识别为文件结尾信号, 一些系统把任意位置的 Ctrl + Z 解释成文件结尾信号。

键盘输入时, EOF是一种按键组合, 而不是具体的字符

#include <stdio.h>

int main(void) {
    // 该程序获取从键盘输入的字符, 并把这些字符发送到屏幕上。 程序使用 while 循环, 当读到键盘传入的 EOF 信号时停止。
    char ch;
    int maxLen = 50;
    int i = 0;

    printf("请输入字符串,以CTRL + C 结束:\n");
    while (((ch = getchar()) != EOF) && i < 50) {
        putchar(ch); // 在标准输出上打印字符 ch
        i += 1;
    }

    printf("\n");
    return 0;
}
/*
输入超过50个字符的例子, 只回显一部分

请输入字符串,以CTRL + C 结束:
dfaffdsahfjdhafhdjshfjkhdsjkhfjkadshkfhdakjsfhjkdashfjkhjkdsahfjkadshfa
dfaffdsahfjdhafhdjshfjkhdsjkhfjkadshkfhdakjsfhjkda

传入 EOF信号的例子(windows10下 CTRL +C)

请输入字符串,以CTRL + C 结束:
adb

输入字符EOF 或者-1是不会退出的,只会作为普通字符回显:
请输入字符串,以CTRL + C 结束:
EOF
EOF
-1
-1
*/

重定向和文件

在默认情况下, C 程序使用标准 I/ O 包查找标准输入作为输入源。 这就是前面介绍过的 stdin 流, 它是把数据读入计算机的常用方式。 它可以是一个过时的设备, 如磁带、 穿孔卡或电传打印机, 或者( 假设) 是键盘, 甚至是一些先进技术, 如语音输入。 然而, 现代计算机非常灵活, 可以让它到别处查找输入。 尤其是, 可以让一个程序从文件中查找输入, 而不是从键盘。

程序可以通过两种方式使用文件。

  • 第 1 种方法是, 显式使用特定的函数打开文件、 关闭文件、 读取文件、 写入文件, 诸如此类。 我们在第 13 章中再详细介绍这种方法。
  • 第 2 种方法是, 设计能与键盘和屏幕互动的程序, 通过不同的渠道重定向输入至文件和从文件输出。 换言之, 把 stdin 流重新赋给文件。 继续使用 getchar() 函数从输入流中获取数据, 但它并不关心从流的什么位置获取数据。 虽然这种重定向的方法在某些方面有些限制, 但是用起来比较简单, 而且能让读者熟悉普通的文件处理技术。

假设生成的 exe 文件是 CProject.exe:

CProject > temp.txt
hello world
line2
line3

> 符号是重定向运算符号, 会把程序的输出( 即你输入字符的副本) 重定向至该文件而不是回显到显示器上, 符号的方向是指向文件的, 文件内容:

请输入字符串,以CTRL + C 结束:
hello world
line2

现在运行:

CProject < temp.txt

屏幕显示:

CProject < temp.txt
请输入字符串,以CTRL + C 结束:
请输入字符串,以CTRL + C 结束:
hello world
line2

< 会将 temp.txt 的内容作为替代stdin 的输入传送给程序处理, 并从标准输出(显示器)输出.

重定向是一个命令行概念, 因为我们要在命令行输入特殊的符号发出指令。

创建更友好的用户界面

缓冲输入用起来比较方便, 因为在把输入发送给程序之前, 用户可以编辑输入。 但是, 在使用输入的字符时, 它也会给程序员带来麻烦。 前面示例中看到的问题是, 缓冲输入要求用户按下 Enter 键发送输入。 这一动作也传送了换行符, 程序必须妥善处理这个麻烦的换行符。

假设程序要求用 getchar() 处理字符输入, 用 scanf() 处理数值输入, 这两个函数都能很好地完成任务, 但是不能把它们混用。 因为

  • getchar() 读取每个字符, 包括空格、 制表符和换行符;
  • 而 scanf() 在读取数字时则会跳过空格、 制表符和换行符。

C 程序把输入作为传入的字节流。 getchar() 函数把每个字符解释成一个字符编码。 scanf() 函数以同样的方式看待输入, 但是根据转换说明, 它可以把字符输入转换成数值。

第9章 函数

如何组织程序? C 的设计思想是, 把函数用作构件块。

复杂要从简单开始, OOP要从函数开始. OOP只是对一种编程思想的命名.

函数 (function )是完成特定任务的独立程序代码单元。 语法规则定义了函数的结构和使用方式。

  • 一些函数执行某些动作, 如 printf() 把数据打印到屏幕上;
  • 一些函数找出一个值供程序使用, 如 strlen() 把指定字符串的长度返回给程序。

一般而言, 函数可以同时具备以上两种功能。

许多程序员喜欢把函数看作是根据传入信息( 输入) 及其生成的值或响应的动作( 输出) 来定义的“ 黑盒”。 如果不是自己编写函数, 根本不用关心黑盒的内部行为。 例如, 使用 printf() 时, 只需知道给该函数传入格式字符串或一些参数以及 printf() 生成的输出, 无需了解 printf() 的内部代码。 以这种方式看待函数有助于把注意力集中在程序的整体设计, 而不是函数的实现细节上。 因此, 在动手编写代码之前, 仔细考虑一下函数应该完成什么任务, 以及函数和程序整体的关系。

创建一个在一行打印 40 个星号的函数, 并在一个打印表头的程序中使用该函数。

#include <stdio.h>
#define NAME "GIGATHINK, INC."
#define ADDRESS "101 Megabuck Plaza"
#define PLACE "Megapolis, CA 94904"
#define WIDTH 40

void starbar(void);  /* prototype the function */

int main(void)
{
    starbar();
    printf("%s\n", NAME);
    printf("%s\n", ADDRESS);
    printf("%s\n", PLACE);
    starbar();       /* use the function       */

    return 0;
}

void starbar(void)   /* define the function    */
{
    int count;

    for (count = 1; count <= WIDTH; count++)
        putchar('*');
    putchar('\n');
}
/*
****************************************
GIGATHINK, INC.
101 Megabuck Plaza
Megapolis, CA 94904
****************************************
*/

该程序要注意以下几点。

  • 程序在 3 处使用了 starbar 标识符:
  • 函数原型 (function prototype )告诉编译器函数 starbar() 的类型;
  • 函数调用 (function call )表明在此处执行函数;
  • 函数定义 (function definition )明确地指定了函数要做什么。
  • 函数和变量一样, 有多种类型。 任何程序在使用函数之前都要声明该函数的类型。
  • void starbar( void);
  • 圆括号表明 starbar 是一个函数名。
  • 第 1 个 void 是函数类型, void 类型表明函数没有返回值。 第 2 个 void (在圆括号中) 表明该函数不带参数。
  • 分号表明这是在声明函数, 不是定义函数。
  • 也就是说, 这行声明了程序将使用一个名为 starbar() 、没有返回值、 没有参数的函数, 并告诉编译器在别处查找该函数的定义。
  • 一般而言, 函数原型指明了函数的返回值类型和函数接受的参数类型。 这些信息称为该函数的签名 (signature )。 对于 starbar() 函数而言, 其签名是该函数没有返回值, 没有参数。
  • 程序把 starbar() 原型置于 main() 的前面。 当然, 也可以放在 main() 里面的声明变量处。 放在哪个位置都可以。
  • starbar() 不需要与主调函数通信。

定义带形式参数的函数

void show_n_char( char ch, int num);
show_n_char( SPACE, 12);

void dibs( int x, y, z); /* 无效的函数头 */ 
void dubs( int x, int y, int z); /* 有效的函数头 */
  • 该行告知编译器 show_n_char() 使用两个参数 ch 和 num ,ch 是 char 类型, num 是 int 类型。 这两个变量被称为形式参数 (formal argument ,但是最近的标准推荐使用 formal parameter ), 简称形参。
  • 和定义在函数中变量一样, 形式参数也是局部变量, 属该函数私有。 这意味着在其他函数中使用同名变量不会引起名称冲突。
  • 在声明函数变量列表时,ANSI C 要求在每个变量前都声明其类型。 也就是说, 不能像普通变量声明那样使用同一类型的变量列表

调用带实际参数的函数

  • 在函数调用中, 实际参数 (actual argument ,简称实参) 提供了 ch 和 num 的值。
  • 实际参数是空格字符和 12 。这两个值被赋给 show_n_char() 中相应的形式参数: 变量 ch 和 num 。
  • 简而言之, 形式参数是被调函数 (called function )中的变量, 实际参数是主调函数 (calling function )赋给被调函数的具体值。
  • 如上例所示, 实际参数可以是常量、 变量, 或甚至是更复杂的表达式。 无论实际参数是何种形式都要被求值, 然后该值被拷贝给被调函数相应的形式参数。
  • 被调函数不知道也不关心传入的数值是来自常量、 变量还是一般表达式。 再次强调, 实际参数是具体的值, 该值要被赋给作为形式参数的变量
  • 因为被调函数使用的值是从主调函数中拷贝而来, 所以无论被调函数对拷贝数据进行什么操作, 都不会影响主调函数中的原始数据。

实际参数是出现在函数调用圆括号中的表达式。 形式参数是函数定义的函数头中声明的变量。 调用函数时, 创建了声明为形式参数的变量并初始化为实际参数的求值结果。

函数定义中是形式参数, 函数调用中是实际参数.

return;

如何返回 void类型的值. 这条语句会导致终止函数, 并把控制返回给主调函数。 因为 return 后面没有任何表达式, 所以没有返回值, 只有在 void 函数中才会用到这种形式。

声明函数时必须声明函数的类型。类型声明是函数定义的一部分。 要记住, 函数类型指的是返回值的类型, 不是函数参数的类型。

要正确地使用函数, 程序在第 1 次使用函数之前必须知道函数的类型。

  • 方法之一是, 把完整的函数定义放在第 1 次调用函数的前面。 然而, 这种方法增加了程序的阅读难度。 而且, 要使用的函数可能在 C 库或其他文件中。
  • 因此, 通常的做法是提前声明函数, 把函数的信息告知编译器。

我们把函数的前置声明放在主调函数外面。 当然, 也可以放在主调函数里面。注意在这两种情况中, 函数原型都声明在使用函数之前。

ANSI C 标准库中, 函数被分成多个系列, 每一系列都有各自的头文件。 这些头文件中除了其他内容, 还包含了本系列所有函数的声明。 例如, stdio.h 头文件包含了标准 I/ O 库函数( 如, printf() 和 scanf() )的声明。 math.h 头文件包含了各种数学函数的声明。

函数声明告知编译器函数的类型, 而函数定义则提供实际的代码。 在程序中包含 math.h 头文件告知编译器: sqrt() 返回 double 类型, 但是 sqrt() 函数的代码在另一个库函数的文件中。

函数原型是 C 语言的一个强有力的工具, 它让编译器捕获在使用函数时可能出现的许多错误或疏漏。 如果编译器没有发现这些问题, 就很难觉察出来。

有一种方法可以省略函数原型却保留函数原型的优点。 首先要明白, 之所以使用函数原型, 是为了让编译器在第 1 次执行到该函数之前就知道如何使用它。 因此, 把整个函数定义放在第 1 次调用该函数之前, 也有相同的效果。 此时, 函数定义也相当于函数原型。 对于较小的函数, 这种用法很普遍:

#include <stdio.h>

// 下面这行代码既是函数定义, 也是函数原型 
int imax( int a, int b) { return a > b ? a : b; }


int main(void)
{
    int x=5,y=6;


    printf("max of  %d and %d is %d \n", x,y,imax(x,y));  // max of  5 and 6 is 6

    return 0;
}

递归

C 允许函数调用它自己, 这种调用过程称为递归 (recursion )。 递归有时难以捉摸, 有时却很方便实用。

结束递归是使用递归的难点, 因为如果递归代码中没有终止递归的条件测试部分, 一个调用自己的函数会无限递归。

可以使用循环的地方通常都可以使用递归。 有时用循环解决问题比较好, 但有时用递归更好。

递归方案更简洁, 但效率却没有循环高。

/* recur.c -- recursion illustration */
#include <stdio.h>
void up_and_down(int);

int main(void)
{
    up_and_down(1);
    return 0;
}

void up_and_down(int n)
{
    printf("Level %d: n location %p\n", n, &n); // 1
    if (n < 4)
        up_and_down(n + 1);
    printf("LEVEL %d: n location %p\n", n, &n); // 2

}
/*
Level 1: n location 0117FB10
Level 2: n location 0117FA38
Level 3: n location 0117F960
Level 4: n location 0117F888
LEVEL 4: n location 0117F888
LEVEL 3: n location 0117F960
LEVEL 2: n location 0117FA38
LEVEL 1: n location 0117FB10
*/

尾递归

最简单的递归形式是把递归调用置于函数的末尾, 即正好在 return 语句之前。 这种形式的递归被称为尾递归 (tail recursion ), 因为递归调用在函数的末尾。

尾递归是最简单的递归形式, 因为它相当于循环。

下面要介绍的程序示例中, 分别用循环和尾递归计算阶乘。 一个正整数的阶乘 (factorial )是从 1 到该整数的所有整数的乘积。

// factor.c -- uses loops and recursion to calculate factorials
#include <stdio.h>
long long fact(int n);
long long rfact(int n);

int main(void)
{
    int num;

    printf("This program calculates factorials.\n");
    printf("Enter a value in the range 0-12 (q to quit):\n");
    while (scanf("%d", &num) == 1)
    {
        if (num < 0)
            printf("No negative numbers, please.\n");
        //else if (num > 12)
        //    printf("Keep input under 13.\n");
        else
        {
            printf("loop: %lld factorial = %ld\n",
                num, fact(num));
            printf("recursion: %lld factorial = %ld\n",
                num, rfact(num));
        }
        printf("Enter a value in the range 0-12 (q to quit):\n");
    }
    printf("Bye.\n");

    return 0;
}

long long fact(int n)     // loop-based function
{
    long long ans;

    for (ans = 1; n > 1; n--)
        ans *= n;

    return ans;
}

long long rfact(int n)    // recursive version
{
    long long ans;

    if (n > 0)
        ans = n * rfact(n - 1);
    else
        ans = 1;

    return ans;
}

/*
This program calculates factorials.
Enter a value in the range 0-12 (q to quit):
12
loop: 2057296206731673612 factorial = 0
recursion: 2057296206731673612 factorial = 0
Enter a value in the range 0-12 (q to quit):
13
loop: 8298106613802205197 factorial = 1
recursion: 8298106613802205197 factorial = 1
Enter a value in the range 0-12 (q to quit):
16
loop: 8607927000276926480 factorial = 4871
recursion: 8607927000276926480 factorial = 4871
Enter a value in the range 0-12 (q to quit):
17
loop: -1239193584968663023 factorial = 82814
recursion: -1239193584968663023 factorial = 82814
Enter a value in the range 0-12 (q to quit):
q
Bye.
*/

既然用递归和循环来计算都没问题, 那么到底应该使用哪一个?

  • 一般而言, 选择循环比较好。
  • 首先, 每次递归都会创建一组变量, 所以递归使用的内存更多, 而且每次递归调用都会把创建的一组新变量放在栈中。 递归调用的数量受限于内存空间。
  • 其次, 由于每次函数调用要花费一定的时间, 所以递归的执行速度较慢。

那么, 演示这个程序示例的目的是什么? 因为尾递归是递归中最简单的形式, 比较容易理解。 在某些情况下, 不能用简单的循环代替递归, 因此读者还是要好好理解递归。

递归和倒序计算

递归在处理倒序时非常方便( 在解决这类问题中, 递归比循环简单)。 我们要解决的问题是: 编写一个函数, 打印一个整数的二进制数。 二进制表示法根据 2 的幂来表示数字。 例如, 十进制数 234 实际上是 2 × 10^2 + 3 × 10^1 + 4 × 10^0 ,所以二进制数 101 实际上是 1 × 2^2 + 0 × 2^1 + 1 × 2^0 。二进制数由 0 和 1 表示。

#include <stdio.h>
void to_binary(unsigned long n);

int main(void)
{
    unsigned long number;
    printf("Enter an integer (q to quit):\n");
    while (scanf("%lu", &number) == 1)
    {
        printf("Binary equivalent: ");
        to_binary(number);
        putchar('\n');
        printf("Enter an integer (q to quit):\n");
    }
    printf("Done.\n");

    return 0;
}

void to_binary(unsigned long n)   /* recursive function , 该递归函数只是打印出结果, 并未返回*/
{
    int r;

    r = n % 2;
    if (n >= 2)
        to_binary(n / 2);
    putchar(r == 0 ? '0' : '1');

    return;
}

/*
Enter an integer (q to quit):
10
Binary equivalent: 1010
Enter an integer (q to quit):
2
Binary equivalent: 10
Enter an integer (q to quit):
1000
Binary equivalent: 1111101000
Enter an integer (q to quit):
q
Done.
*/

不用递归, 是否能实现这种用二进制形式表示整数的算法? 当然可以。 但是由于这种算法要首先计算最后一位二进制数, 所以在显示结果之前必须把所有的位数都存储在别处( 例如, 数组), 实际上存储在数组中, 再调用倒序函数就OK了,也每那么复杂.

递归的优缺点

递归既有优点也有缺点。 优点是递归为某些编程问题提供了最简单的解决方案。 缺点是一些递归算法会快速消耗计算机的内存资源。 另外, 递归不方便阅读和维护。

Enter an integer (q to quit):
1
Fibonacci(1):1
 调用Fibonacci()的次数1:
Enter an integer (q to quit):
2
Fibonacci(2):1
 调用Fibonacci()的次数1:
Enter an integer (q to quit):
3
Fibonacci(3):2
 调用Fibonacci()的次数3:
Enter an integer (q to quit):
10
Fibonacci(10):55
 调用Fibonacci()的次数109:
Enter an integer (q to quit):
20
Fibonacci(20):6765
 调用Fibonacci()的次数13529:
Enter an integer (q to quit):
30
Fibonacci(30):832040
 调用Fibonacci()的次数1664079:
Enter an integer (q to quit):
40
Fibonacci(40):102334155
 调用Fibonacci()的次数204668309:
Enter an integer (q to quit):
45
Fibonacci(45):1134903170
 调用Fibonacci()的次数2269806339:
Enter an integer (q to quit):
q
Done.

调用40时,2亿次,调用45时,22亿次

为了说明这个问题, 假设调用 Fibonacci( 40) 。这是第 1 级递归调用, 将创建一个变量 n 。然后在该函数中要调用 Fibonacci() 两次, 在第 2 级递归中要分别创建两个变量 n 。这两次调用中的每次调用又会进行两次调用, 因而在第 3 级递归中要创建 4 个名为 n 的变量。 此时总共创建了 7 个变量。 由于每级递归创建的变量都是上一级递归的两倍, 所以变量的数量呈指数增长! 在第 5 章中介绍过一个计算小麦粒数的例子, 按指数增长很快就会产生非常大的值。 在本例中, 指数增长的变量数量很快就消耗掉计算机的大量内存, 很可能导致程序崩溃。

虽然这是个极端的例子, 但是该例说明: 在程序中使用递归要特别注意, 尤其是效率优先的程序。

使用头文件

如果把 main() 放在第 1 个文件中, 把函数定义放在第 2 个文件中, 那么第 1 个文件仍然要使用函数原型。 把函数原型放在头文件中, 就不用在每次使用函数文件时都写出函数的原型。 C 标准库就是这样做的, 例如, 把 I/ O 函数原型放在 stdio.h 中, 把数学函数原型放在 math.h 中。 你也可以这样用自定义的函数文件。

把函数原型和已定义的字符常量放在头文件中是一个良好的编程习惯。

查找地址:& 运算符

指针 (pointer )是 C 语言最重要的( 有时也是最复杂的) 概念之一, 用于存储变量的地址。 前面使用的 scanf() 函数中就使用地址作为参数。 概括地说, 如果主调函数不使用 return 返回的值, 则必须通过地址才能修改主调函数中的值。

一元& 运算符给出变量的存储地址。 如果 pooh 是变量名, 那么& pooh 是变量的地址。 可以把地址看作是变量在内存中的位置。

#include <stdio.h>

int main(void)
{
    unsigned long number = 10;

    printf("number %ul 的地址是: %p \n", number, &number); // % p 是输出地址的转换说明
    // number 10l 的地址是: 0096FD44 
    return 0;
}

调用带一般参数的函数时, 会为传入的参数新分配地址, 并赋予传入的参数的值, 改变这些新建的变量并不会改变主调函数的变量, 因为被调用的函数中使用的并不是主调函数的变量.

#include <stdio.h>

void interchange(int x, int y) {
    // 并不会真正交换调用该函数的主调函数的值
    int temp = x;

    printf("调用前 interchange() 内部的 x,y: %d,%d\n", x, y);
    printf("调用前 interchange() 内部的 x,y地址: %p,%p\n", &x, &y);
    x = y;
    y = temp;
    printf("调用后 interchange() 内部的 x,y: %d,%d\n", x, y);
    printf("调用后 interchange() 内部的 x,y地址: %p,%p\n", &x, &y);

}


int main(void)
{
    int x = 5, y = 6;

    printf("调用前主调函数内部的 x,y: %d,%d\n", x, y);
    printf("调用前主调函数内部的 x,y地址: %p,%p\n", &x, &y);
    interchange(x, y);
    printf("调用后主调函数内部的 x,y: %d,%d\n", x, y);
    printf("调用后主调函数内部的 x,y地址:% p, % p\n", &x, &y);

    return 0;
}

/*
调用前主调函数内部的 x,y: 5,6
调用前主调函数内部的 x,y地址: 00CFF6E8,00CFF6DC
调用前 interchange() 内部的 x,y: 5,6
调用前 interchange() 内部的 x,y地址: 00CFF604,00CFF608
调用后 interchange() 内部的 x,y: 6,5
调用后 interchange() 内部的 x,y地址: 00CFF604,00CFF608
调用后主调函数内部的 x,y: 5,6
调用后主调函数内部的 x,y地址:00CFF6E8, 00CFF6DC
*/

指针简介

从根本上看, 指针 (pointer )是一个值为内存地址的变量( 或数据对象)。 正如 char 类型变量的值是字符, int 类型变量的值是整数, 指针变量的值是地址。

声明指针变量时必须指定指针所指向变量的类型, 因为不同的变量类型占用不同的存储空间, 一些指针操作要求知道操作对象的大小。

int * pi; // pi 是指向 int 类型变量的指针
  • 类型说明符表明了指针所指向对象的类型,
  • 星号(*) 表明声明的变量是一个指针。
  • int * pi; 声明的意思是 pi 是一个指针
  • *pi 是 int 类型
  • pi是int类型的指针
  • *和指针名之间的空格可有可无。 通常, 程序员在声明时使用空格, 在解引用变量时省略空格。
  • &变量名 是取变量的地址, *变量名 是获取该指针变量对应的值

在大部分系统内部, 指针对应的地址由一个无符号整数表示。 但是, 不要把指针认为是整数类型。 一些处理整数的操作不能用来处理指针, 反之亦然。 例如, 可以把两个整数相乘, 但是不能把两个指针相乘。

所以, 指针实际上是一个新类型, 不是整数类型。 因此, 如前所述, ANSI C 专门为指针提供了% p 格式的转换说明。

#include <stdio.h>

int main(void)
{
    int a = 10;  // a是int类型,数值是10
    int *b;   // b是int类型的指针, 可以保存int类型数值对应的指针

    b = &a;  // b的指针存储的值为 a的地址
    printf("a的值为 %d,地址为 %p, b的值为 %p \n", a, &a, b);  // a的值为 10,地址为 007DFC70, b的值为 007DFC70
    printf("b的地址存储的值为 %d, b中存储的地址为 %p \n", *b, b); // b的地址存储的值为 10, b中存储的地址为 007DFC70

    return 0;
}

使用指针在函数间通信

参数如果是指针, 可以直接操作指针对应的值,达到函数间直接通讯的目的

#include <stdio.h>

void interchange(int *x, int *y) {
    // 传入的是变量的地址, 如果修改地址对应的值,会直接修改这些原始值
    int temp = *x;  // 获得了x对应的值

    printf("调用前 interchange() 内部的 *x,*y: %d,%d\n", *x, *y);
    printf("调用前 interchange() 内部的 x,y地址: %p,%p\n", x, y);
    *x = *y;
    *y = temp;
    printf("调用后 interchange() 内部的 *x,*y: %d,%d\n", *x, *y);
    printf("调用后 interchange() 内部的 x,y地址: %p,%p\n", x, y);

}


int main(void)
{
    int x = 5, y = 6;

    printf("调用前主调函数内部的 x,y: %d,%d\n", x, y);
    printf("调用前主调函数内部的 x,y地址: %p,%p\n", &x, &y);
    interchange(&x, &y);
    printf("调用后主调函数内部的 x,y: %d,%d\n", x, y);
    printf("调用后主调函数内部的 x,y地址:% p, % p\n", &x, &y);

    return 0;
}

/*
调用前主调函数内部的 x,y: 5,6
调用前主调函数内部的 x,y地址: 00CFFD94,00CFFD88
调用前 interchange() 内部的 *x,*y: 5,6
调用前 interchange() 内部的 x,y地址: 00CFFD94,00CFFD88
调用后 interchange() 内部的 *x,*y: 6,5
调用后 interchange() 内部的 x,y地址: 00CFFD94,00CFFD88
调用后主调函数内部的 x,y: 6,5
调用后主调函数内部的 x,y地址:00CFFD94, 00CFFD88
*/

如果函数的参数是地址(指针), 那对这些地址上的值的修改会直接修改掉原始数据, 不会另外新建变量临时存储这些数据.

变量: 名称、 地址和值

  • 编写程序时, 可以认为变量有两个属性: 名称和值
  • 计算机编译和加载程序后, 认为变量也有两个属性: 地址和值。 地址就是变量在计算机内部的名称。
  • 在许多语言中, 地址都归计算机管, 对程序员隐藏。 然而在 C 中, 可以通过& 运算符访问地址, 通过* 运算符获得地址上的值。
  • 普通变量把值作为基本量, 把地址作为通过& 运算符获得的派生量, 而指针变量把地址作为基本量, 把值作为通过* 运算符获得的派生量。

第 10章 数组和指针

数组

只存储单个值的变量有时也称为标量变量 (scalar variable ).

可以用以逗号分隔的值列表( 用花括号括起来) 来初始化数组, 各值之间用逗号分隔。 在逗号和值之间可以使用空格。

有时需要把数组设置为只读。 这样, 程序只能从数组中检索值, 不能把新值写入数组。 要创建只读数组, 应该用 const 声明和初始化数组。

如果不初始化数组, 数组元素和未初始化的普通变量一样, 其中存储的都是垃圾值; 但是, 如果部分初始化数组, 剩余的元素就会被初始化为 0 。

指定初始化器( C99): C99 增加了一个新特性: 指定初始化器 (designated initializer )。 利用该特性可以初始化指定的数组元素。

C 不允许把数组作为一个单元赋给另一个数组, 除初始化以外也不允许使用花括号列表的形式赋值。

数组边界在使用数组时, 要防止数组下标超出边界。 也就是说, 必须确保下标是有效的值。使用越界的数组下标会导致程序改变其他变量的值。

C 语言为何会允许这种麻烦事发生? 这要归功于 C 信任程序员的原则。 不检查边界, C 程序可以运行更快。 编译器没必要捕获所有的下标错误, 因为在程序运行之前, 数组的下标值可能尚未确定。 因此, 为安全起见, 编译器必须在运行时添加额外代码检查数组的每个下标值, 这会降低程序的运行速度。 C 相信程序员能编写正确的代码, 这样的程序运行速度更快。 但并不是所有的程序员都能做到这一点, 所以就出现了下标越界的问题。

#include <stdio.h>

int main(void)
{
    int i_ar[10] = { 0,1,2,3,4,5,6,7 };
    const int i_const[10] = { 0,1,2,3,4,5,6,7,8,9 }; // 声明只读数组
    // 初始化指定的数组元素
    // 对于一般的初始化, 在初始化一个元素后, 未初始化的元素都会被设置为 0
    double d_ar[10] = { [0] = 2,[2] = 4 };
    int i;
    for (i = 0; i < 10; i++) {
        printf("%f \n", d_ar[i]);
    }
    /*
    2.000000
    0.000000
    4.000000
    0.000000
    0.000000
    0.000000
    0.000000
    0.000000
    0.000000
    0.000000
    */

    // 使用数组前必须先初始化它。 与普通变量类似, 在使用数组元素之前, 必须先给它们赋初值。 
    // 编译器使用的值是内存相应位置上的现有值,
    // 如果不初始化数组, 数组元素和未初始化的普通变量一样, 其中存储的都是垃圾值; 
    // 但是, 如果部分初始化数组, 剩余的元素就会被初始化为 0 。
    printf("i_ar[7]= %d \n", i_ar[7]); //i_ar[7] = 7
    printf("i_ar[8]= %d \n", i_ar[8]); //i_ar[8] = 0 ,实际是没有初始化的值
    printf("i_ar[9]= %d \n", i_ar[9]); //i_ar[9] = 0 ,实际是没有初始化的值


    printf("i_ar[10]= %d \n", i_ar[10]); //i_ar[10]= -858993460, 实际已经越过数组


    // 多维数组
    int ma[2][3][4] = {
        {
            {1,2,3,4},{5,6,7,8},{9,10,11,12}
        },
        {{13,14,15,16},{17,18,19,20},{21,22,23,24}}
    };


    printf("ma[1][2][3]=%d \n", ma[1][2][3]); // ma[1][2][3]=24, 最后一个元素

    int j, k;

    for (i = 0; i <= 1; i++) {
        for (j = 0; j <= 2; j++) {
            for (k = 0; k <= 3; k++) {
                ma[i][j][k] = i + j + k;
            }
        }

    }

    for (i = 0; i <= 1; i++) {
        for (j = 0; j <= 2; j++) {
            for (k = 0; k <= 3; k++) {
                printf("% d ", ma[i][j][k]);
            }
            printf("\n");
        }
    }
    /*
    0  1  2  3
     1  2  3  4
     2  3  4  5
     1  2  3  4
     2  3  4  5
     3  4  5  6
     */

    return 0;
}

指针和数组

指针提供一种以符号形式使用地址的方法。 因为计算机的硬件指令非常依赖地址, 指针在某种程度上把程序员想要传达的指令以更接近机器的方式表达。 因此, 使用指针的程序更有效率。 尤其是, 指针能有效地处理数组。 我们很快就会学到, 数组表示法其实是在变相地使用指针。

数组名是该数组首元素的地址.可以把它们赋值给指针变量 ,然后可以修改指针变量的值

在 C 中, 指针加 1 指的是增加一个存储单元 。对数组而言, 这意味着加 1 后的地址是下一个元素的地址, 而不是下一个字节的地址。 这是为什么必须声明指针所指向对象类型的原因之一。 只知道地址不够, 因为计算机要知道存储对象需要多少字节( 即使指针指向的是标量变量, 也要知道变量的类型, 否则 *pt 就无法正确地取回地址上的值)。

  • 指针的值是它所指向对象的地址。
  • 在指针前面使用* 运算符可以得到该指针所指向对象的值。
  • 指针加 1, 指针的值递增它所指向类型的大小( 以字节为单位)。
  • 指针表示法和数组表示法是两种等效的方法。
  • 数组名实际上是指针类型
#include <stdio.h>

int main(void)
{
    int i_ar[10] = { 0,1,2,3,4,5,6,7 };
    int* p;

    // 数组名实际上是指针类型
    p = i_ar;

    printf("%d \n", (p == &i_ar[0]));   // 1

    printf("%p %p %p\n", i_ar, &i_ar[0], p); //004FFB24 004FFB24 004FFB24

    printf("%d %d %d \n", *(p + 1), *(p + 2), *(p + 3)); //1 2 3

    printf("%d %d %d \n", *(i_ar + 1), *(i_ar + 2), *(i_ar + 3)); //1 2 3

    printf("%d %d %d \n", i_ar[1], i_ar[2], i_ar[3]); //1 2 3

    return 0;
}

函数、 数组和指针

假设要编写一个处理数组的函数, 该函数返回数组中所有元素之和, 待处理的是名为 marbles 的 int 类型数组。

那么, 该函数的原型是什么? 记住, 数组名是该数组首元素的地址, 所以实际参数 marbles 是一个存储 int 类型值的地址, 应把它赋给一个指针形式参数, 即该形参是一个指向 int 的指针.

#include <stdio.h>

int sum(int* marbles, int theLen);

int main(void)
{
    int i_ar[10] = { 0,1,2,3,4,5,6,7 };
    int theLen = sizeof(i_ar) / sizeof(i_ar[0]);
    printf("%d", sum(i_ar, theLen)); //28

    return 0;
}

// 第 1 个形参告诉函数该数组的地址和数据类型, 第 2 个形参告诉函数该数组中元素的个数。
int sum(int* marbles, int theLen) {
    int s = 0;
    int i;
    for (i = 0; i < theLen; i++) {
        s += *(marbles + i);
    }
    return s;
}

函数要处理数组必须知道何时开始、 何时结束。 sum() 函数使用一个指针形参标识数组的开始, 用一个整数形参表明待处理数组的元素个数( 指针形参也表明了数组中的数据类型)。 但是这并不是给函数传递必备信息的唯一方法。 还有一种方法是传递两个指针, 第 1 个指针指明数组的开始处( 与前面用法相同), 第 2 个指针指明数组的结束处。

#include <stdio.h>

int sum(int* start, int* end);

int main(void)
{
    int i_ar[10] = { 0,1,2,3,4,5,6,7 };
    int* end = i_ar + sizeof(i_ar) / sizeof(i_ar[0]) -1;

    printf("%d", sum(i_ar, end)); //28

    return 0;
}

int sum(int* start, int* end) {
    int s = 0;
    int* i;

    for (i = start; i <= end;i++) {
        s += *i;
    }
    return s;
}

处理数组的函数实际上用指针作为参数, 但是在编写这样的函数时, 可以选择是使用数组表示法还是指针表示法。 使用数组表示法, 让函数是处理数组的这一意图更加明显。

指针表示法( 尤其与递增运算符一起使用时) 更接近机器语言, 因此一些编译器在编译时能生成效率更高的代码。 然而, 许多程序员认为他们的主要任务是确保代码正确、 逻辑清晰, 而代码优化应该留给编译器去做。

指针操作

C 提供了一些基本的指针操作

如果编译器不支持% p 转换说明, 可以用% u 或% lu 代替% p ;如果编译器不支持用% td 转换说明打印地址的差值, 可以用% d 或% ld 来代替。

  • 赋值: 可以把地址赋给指针。 例如, 用数组名、 带地址运算符(& )的变量名、 另一个指针进行赋值。
  • 解引用: *运算符给出指针指向地址上存储的值。
  • 取址: 和所有变量一样, 指针变量也有自己的地址和值。 对指针而言,& 运算符给出指针本身的地址。
  • 指针与整数相加: 可以使用 + 运算符把指针与整数相加, 或整数与指针相加。 无论哪种情况, 整数都会和指针所指向类型的大小( 以字节为单位) 相乘, 然后把结果与初始地址相加。
  • 递增指针: 递增指向数组元素的指针可以让该指针移动至数组的下一个元素。
  • 递减指针: 当然, 除了递增指针还可以递减指针。
  • 指针减去一个整数: 可以使用- 运算符从一个指针中减去一个整数。 指针必须是第 1 个运算对象, 整数是第 2 个运算对象。 该整数将乘以指针指向类型的大小( 以字节为单位), 然后用初始地址减去乘积。
  • 指针求差: 可以计算两个指针的差值。 通常, 求差的两个指针分别指向同一个数组的不同元素, 通过计算求出两元素之间的距离。 差值的单位与数组类型的单位相同。
  • 比较: 使用关系运算符可以比较两个指针的值, 前提是两个指针都指向相同类型的对象。

在递增或递减指针时还要注意一些问题。 编译器不会检查指针是否仍指向数组元素。 C 只能保证指向数组任意元素的指针和指向数组后面第 1 个位置的指针有效。 但是, 如果递增或递减一个指针后超出了这个范围, 则是未定义的。 另外, 可以解引用指向数组任意元素的指针。 但是, 即使指针指向数组后面一个位置是有效的, 也不能保证可以解引用这样的越界指针。

切记: 创建一个指针时, 系统只分配了存储指针本身的内存, 并未分配存储数据的内存。 因此, 在使用指针之前, 必须先用已分配的地址初始化它。

保护数组中的数据

编写一个处理基本类型( 如, int )的函数时, 要选择是传递 int 类型的值还是传递指向 int 的指针。 通常都是直接传递数值, 只有程序需要在函数中改变该数值时, 才会传递指针。 对于数组别无选择, 必须传递指针, 因为这样做效率高。 如果一个函数按值传递数组, 则必须分配足够的空间来存储原数组的副本, 然后把原数组所有的数据拷贝至新的数组中。 如果把数组的地址传递给函数, 让函数直接处理原数组则效率要高。

传递地址会导致一些问题。 C 通常都按值传递数据, 因为这样做可以保证数据的完整性。 如果函数使用的是原始数据的副本, 就不会意外修改原始数据。 但是, 处理数组的函数通常都需要使用原始数据, 因此这样的函数可以修改原数组。 有时, 这正是我们需要的。

在 K& R C 的年代, 避免类似错误的唯一方法是提高警惕。 ANSI C 提供了一种预防手段。 如果函数的意图不是修改数组中的数据内容, 那么在函数原型和函数定义中声明形式参数时应使用关键字 const

int sum( const int ar[], int n); /* 函数原型 */ 

int sum( const int ar[], int n) /* 函数定义 */

以上代码中的 const 告诉编译器, 该函数不能修改 ar 指向的数组中的内容。 如果在函数中不小心使用类似 ar[ i] + + 的表达式, 编译器会捕获这个错误, 并生成一条错误信息。

这里一定要理解, 这样使用 const 并不是要求原数组是常量, 而是该函数在处理数组时将其视为常量, 不可更改。 这样使用 const 可以保护数组的数据不被修改, 就像按值传递可以保护基本数据类型的原始值不被改变一样。

一般而言, 如果编写的函数需要修改数组, 在声明数组形参时则不使用 const ;如果编写的函数不用修改数组, 那么在声明数组形参时最好使用 const 。

虽然用# define 指令可以创建类似功能的符号常量, 但是 const 的用法更加灵活。 可以创建 const 数组、 const 指针和指向 const 的指针。

© Licensed under CC BY-NC-SA 4.0

要节约用水,尽量和女友一起洗澡——加菲猫

发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!