【第一部分 第一章】The C Programming Language 程序研究 【持续更新】
前言
C语言之父创作的The C Programming Language一书对于所有学习C语言的人来说都可以算作一部圣经。它不到200页的篇幅却几近完整地阐述了C语言的各个方面,不仅如此,书中的每个例程和练习都展现了作者丰富的C编程经验,对于初学者来说这些例程和练习并不是那么简单,即使是对于有些经验的C语言工作者来说,也有很多值得称道的地方。在此,我特意精选了The C Programming Language (second edition)中几个方面的编程例程和练习作深入的探讨和研究,一方面可以帮助自己巩固已学的知识、提高编程能力,另一方面也可以帮助其他C初学者更好地阅读K&R这部圣经。由于博主自己接触编程不久,因此文章中难免会有错误,还请大家不吝赐教,多多批评指正,谢谢。
声明
1、此博文版权归断絮所有,如需转载请注明出处http://blog.csdn.net/duanxu_yzc/article/details/12029803,谢谢。
2、在未经博主断絮允许的情况下,任何个人和机构都不得以任何理由出版此此文章,否则必将追究法律责任!
第一部分 字符和字符串
K&R这部书中的例程和练习大多都是和字符以及字符串有关的,博主遴选了几类典型的字符(串)处理问题,还对其中的某些进行了修改和扩展。
第一章 字符(串)统计
一、单词计数(p14)
问题描述:统计输入文本中的单词数目。(单词:任何不包含空白字符的连续字符。)
输入:This is a C programme.
输出:5
分析
标准输入情况:(用□代表空格,其它不可见字符使用其转义字符表示)
This□is□a
□This□is□a
第一次出现非空白字符时表示已经进入了第一个新单词,程序开始计数,直到遇到空白字符,此时已经读到一个单词之外了,当再次由单词之外进入新单词——出现非空白字符时,再次计数,如此循环,直至文本结束。最后输出统计得到的单词数目。
编码:
/*
*单词计数
* version1.0
*/
#include <stdio.h>
#include <ctype.h>
#define IN 1 //已经进入一个单词的标志
#define OUT 0 //已经退出一个单词的标志
intmain(void )
{
long int ct; //单词数
int state; //是否进入单词的状态
int ch; //读到的字符
ct = 0L; //初始化单词数为0
state = OUT; //初始状态为不在一个单词中
//读取文本,直到EOF
while ( ( ch=getchar() ) != EOF)
{
if (isspace( ch) ) //切勿使用isblank()函数
state= OUT;
else if ( state== OUT) //在读到一个非空白字符时,如果前一状态为OUT,则表示进入了一个新单词
{
state= IN; //在新单词内部时,要保持状态为IN
ct++;
}
}
printf("%ld\n", ct);
return0;
}
关键:如何识别已经进入了一个新单词?
在读到一个非空字符时将状态设置为外(OUT),在一个单词内部时,保持状态为内(IN)。
意外:在编码时,在判断读取是否为空白字符时,意外地使用了错误的isblank()函数,出现了错误的结果。这个函数在C99中有定义,int isblank ( int c );当参数为空格或者水平制表符时,函数返回1,否则返回0;随即测试此函数如下:
/*
*测试isblank()函数
*/
#include <stdio.h>
#include <ctype.h>
intmain(void )
{
int ch;
int i;
char str[] ="\v\f\r\t\n";
i = 0;
while ( ch= str[i] )
{
if (isblank( ch) )
printf("%d\n", i);
i++;
}
return0;
}
/*
*输出为 0 4
*表明只有空格和水平制表符是isblank
*/
扩展:使用枚举类型代替#define常量
/*
*使用枚举类型替代#include
*/
#include <stdio.h>
#include <ctype.h>
intmain(void )
{
enum state{ out, in};//使用枚举类型
int state; //可以与枚举标签使用同样的名字,这样可以使表达更清楚
int ch;
long int ct;
state = out;
ct = 0L;
while ( ( ch=getchar() ) != EOF)
{
if (isspace( ch) )
state= out;
else if ( state== out)
{
state= in;
ct++;
}
}
printf("%ld\n", ct);
return0;
}
小结:此程序的关键是如何判断程序已经读到了一个新单词,另外不要在程序中使用表意不明的“幻数”,可以使用#define常量或者是枚举来代替。
二、统计单词长度并绘制直方图
问题描述:统计输入文本中单词的长度,并绘制水平和垂直直方图表示长度的分布情况。
输入:This is a C programme
输出:
(水平)
1: **
2: *
4: *
9: *
(垂直)
*
* * * *
1 2 4 9
分析
统计不同长度单词的个数,实际需要统计两类数据——每个单词的字符数和各长度的单词数目,这与前一节中只统计单词数目不同。
我们首先考虑如何获取各单词中字符的数目,单词还是不包含空白字符的连续的字符序列,我们仍旧以空白符为分界点,在出现空白符时就结束字符的计数,重置计数器;在遇到非空白符时增加计数器的数值。
在得到了各个单词的长度之后,如何统计不同长度单词的个数呢?我们不难发现,单词的长度L和这种长度的单词数目C是以数对(L,C)的形式出现的,长度的唯一性确定了这个数对的唯一性,也就是说,每个长度只能有一个数对或者单词数目,但是每个单词数目并不一定只有一种长度。这类似于一维数组,每个下标只能有一个对应元素,而同一个元素值可能对应于不同的下标值。我们利用数组的这个特性来模拟L和C之间的关系:将L作为数组的下标,C作为数组的元素。这样就可以实用一个数组来统计不同长度单词的数目。具体操作如下:首先将所有长度的单词数目(数组的所有元素)置为0,然后在得到了具体长度(下标值)的一个单词之后,使这个长度对应的单词数目(下标对应的元素)增1。
具体程序如下:
/*
*统计文本中单词长度分布
*单纯统计数量信息
*/
#include <stdio.h>
#include <ctype.h>
int len[31]; //外部数组自动初始化为0
intmain(void )
{
int ch;
int length;
int i;
length = 0;
while ( ( ch=getchar() ) != EOF)
{
if (isspace( ch) )
{
len[length] ++; //长度所对应的元素自增1
length=0; //恢复长度为0,以便下一单词的长度计数
}
else
length++; //遇到非空就计数
}
if ( length!=0) //处理非空白后直接跟EOF的情况
len[length] ++;
for ( i=1; i<31; i++ ) //输出
if ( len[i] !=0)
printf("length: %2d count: %3d\n", i, len[i] );
return0;
}
水平直方图
至此我们已经得到了单词长度的统计数据,现在要考虑如何将这个一维数组转换为水平和垂直直方图。首先看看比较简单的水平直方图。
我们可以直接利用得到的数据,按照各长度的数目,打印出相应数目的图案(*)。具体方案如下:
for ( i=1; i<31; i++ ) //输出:将一维数组中元素的大小,转化为相应数目的星号,直接输出
if ( len[i] !=0)
{
printf("length %2d: ", i);
for ( j=0; j<len[i]; j++ )
putchar('*');
putchar('\n');
垂直直方图
水平直方图很容易绘制,原因在于打印是按行进行的,也就是说,每行打印完成之后才能打印下一行,这与水平直方图的信息连续性方向刚好吻合,但是垂直直方图的分布并不是这样的,它的信息连续性是按列分布的,而打印只能按行进行,这就产生了矛盾,因此,我们不能直接使用得到的一维数组的数据进行输出,我们可以先看看最终想得到的输出的形式(*的数量代表单词的个数,□表示空格):
□
□
*
□
□
□
□
□
□
□
*
□
*
□
□
□
□
□
□
□
*
□
*
□
□
□
□
□
□
□
*
□
*
*
□
□
*
□
□
□
*
*
*
*
□
*
*
*
□
□
*
*
*
*
*
*
*
*
□
□
*
*
*
*
*
*
*
*
*
□
*
*
*
*
*
*
*
*
*
*
我们将上面的表格转化一下,用1代表*,用0代表□:
R0
0
0
1
0
0
0
0
0
0
0
R1
1
0
1
0
0
0
0
0
0
0
R2
1
0
1
0
0
0
0
0
0
0
...
1
0
1
1
0
0
1
0
0
0
...
1
1
1
1
0
1
1
1
0
0
...
1
1
1
1
1
1
1
1
0
0
...
1
1
1
1
1
1
1
1
1
0
rmax-1
1
1
1
1
1
1
1
1
1
1
这样我们就得到了一个二维数组,按照这个二维数组就可以输出得到最终的分布图,现在的问题就是如何通过已经得到的一维数组生成这个二维数组。
将一维数组转换为二维数组并不难,只需要将一维数组中每个元素的值转换为对应个数的1即可。观察这个二维数组,发现1的分布都是从最下面一行开始的,在转换的过程中应该从最后一行开始。还有一点需要注意,输出数组的行数由含有1最多的列决定(如图中被框住的列),因此我们需要找到包含有最多单词数的长度。最终思路如下:
初始化二维数组→找出一维数组中的最大元素→将一维数组转化为二维数组→按照二维数组输出结果
完整的代码如下:
/*
*统计文本中单词长度分布
*垂直直方图
*/
#include <stdio.h>
#include <ctype.h>
#define R_MAX 1000
int len[31]; //外部数组自动初始化为0
int len_2d[R_MAX][31]; //不确定最多有多少行,预估为R_MAX行
intmain(void )
{
int ch;
int length;
int i;
int j;
int r_max;
length = 0;
while ( ( ch=getchar() ) != EOF)
{
if (isspace( ch) )
{
len[length] ++; //长度所对应的元素自增1
length=0; //恢复长度为0,以便下一单词的长度计数
}
else
length++; //遇到非空就计数
}
if ( length!=0) //处理非空白后直接跟EOF的情况
len[length] ++;
/*
*获取实际的最大行
*/
for ( r_max=len[1], i=1; i<31; i++ )
if ( len[i] > r_max)
r_max= len[i];
/*
*转化为二维垂直数组
*/
for ( j=1; j<31; j++ )
if ( len[j] !=0)
for ( i=r_max-1; i>=r_max-len[j]; i-- )
len_2d[i][j] =1;
/*
*输出
*/
for ( i=0; i<r_max; i++ )
{
for ( j=1; j<31; j++ )
if ( len_2d[r_max-1][j] !=0) //len_2d[r_max-1][j]不输出空列(即没有单词的长度)
{
if ( len_2d[i][j] !=0)
{
putchar(' '); //空格美化间隔
putchar(' ');
putchar('*');
}
else
{
putchar(' '); //空格美化间隔
putchar(' ');
putchar(' ');
}
}
putchar('\n');
}
for ( j=1; j<31; j++ ) //打印长度数
if ( len_2d[r_max-1][j] !=0)
printf("%3d", j);
return0;
}
小结
1、在遇到问题时要善于分解,然后各个击破。比如这个题目中需要绘制单词长度分布的直方图,可以分解为3个子问题:统计各单词包含字符数、统计各长度包含单词数和绘制图像,当然,这些子问题还可以进一步分解。
2、使用数组下标和元素的关系模拟各种二元数对。
3、逆序分析法:从结果入手一步步往前推理,直到找到可以解决的那一步。比如本节中绘制垂直直方图中,从最终的图形入手分析,一直到已经得到的一维数组,解决问题。
4、一维数组转换为二维数组的方法。
本章中探讨了字符和字符串的统计问题,其中也涉及到了图形绘制以及一维数组和二维数组之间的转换,但没有深入展开讨论,这些内容将在后续的章节里面专门介绍。