Learn You a Haskell for Great Good!——(3)类型与类型类

重温K&R(1)

daybreakcx posted @ 2010年2月02日 01:42 in 学习笔记 , 5369 阅读

以前没有认真看过C的语言书籍，大概翻了翻老谭的看了看语法套着Pascal的模式就上了，不断练习后略有小成，俗话说：“练武不练功，到老一场空”，考虑到还有一些知识点不是非常熟悉，长久不用就容易忘记，遂加强对于C的练习，重温《The C Programming Language》，同时再巩固一下AT&T汇编，参考书籍是为数不多的Linux下经典汇编书籍《Professional Assembly Language》，在blog上做做学习笔记，加深印象，基本关于K&R的学习一方面走一两遍书本内容，而在blog中列出各个习题的个人解答。

Exercise 1-1. Run the ``hello, world'' program on your system. Experiment with leaving out parts of the program, to see what error messages you get.
解：这个，就略吧，唉第一题就这样pass真是失利，但是说实话，试了不少了。

Exercise 1-2. Experiment to find out what happens when prints's argument string contains \c, where c is some character not listed above.
解：还是试验性的题目，就是尝试转义字符，这个也pass吧，情何以堪啊~。

Exercise 1-3. Modify the temperature conversion program to print a heading above the table.

解：这个题目要求我们打一个表头出来，为了显示美观，我改了改原来的距离。

#include <stdio.h>
int lower, upper, step;
float fahr, celsius;
int main()
{
	lower = 0;
	upper = 300;
	step = 20;
	fahr = lower;
	printf("FAHRENHEIT\tCELCIUS\n");
	while (fahr <= upper) {
		celsius = (5.0/9.0) * (fahr-32.0);
		printf("%10.0f\t %6.1f\n", fahr, celsius);
		fahr = fahr + step;
	}
	return 0;
}

说实话，以前写代码非常不喜欢加空格，而且用的花括号的格式也是左排对齐的，我想还是慢慢贴近K&R的C代码风格吧，加点空格自己看着也爽，阅读起来更方便。

Exercise 1-4. Write a program to print the corresponding Celsius to Fahrenheit table.

解：这个题目是要求我们写一个从摄氏温度转到华氏温度的程序，根据公式 $^\circ{\mathrm C} = \frac{5}{9} (^\circ{\mathrm F} - 32)$ 我们得到逆公式 $^\circ{\mathrm F} = \frac{9}{5} ^\circ{\mathrm C} + 32$ ，然后就有如下程序

#include <stdio.h>
int lower, upper, step;
float fahr, celsius;
int main()
{
	lower = 0;
	upper = 300;
	step = 20;
	celsius = lower;
	printf("FAHRENHEIT\tCELCIUS\n");
	while (celsius <= upper) {
		fahr = (9.0/5.0) * celsius + 32.0;
		printf("%10.0f\t %6.1f\n", fahr, celsius);
		celsius = celsius + step;
	}
	return 0;
}

Exercise 1-5. Modify the temperature conversion program to print the table in reverse order, that is, from 300 degrees to 0.
解：这个题目需要我们从300到0倒序打印温度表，由于这里是接在for循环的介绍之后的，所以用for循环写如下程序，代码很短

#include <stdio.h>
int fahr;
int main()
{
	for (fahr = 300; fahr >= 0; fahr = fahr - 20)
		printf("%3d %6.1f\n", fahr, (5.0/9.0) * (fahr-32));
	return 0;
}

Exercsise 1-6. Verify that the expression getchar() != EOF is 0 or 1.

解：这个可以用一个文件来实现，因为EOF平常输入不好模拟，所以我们建立一个文件，比如我在里头输入少量的字符，注意，默认情况下貌似系统会在每次写文件时候如果最后加一个ASCII为十进制10的字符，如果你想看到预期结果建议用程序生成字符，不要用手动输入，否则将会有所偏差。然后看我的结果就可以了，结果是0和1。

#include <stdio.h>
int i;
int main()
{
	freopen("try.in", "r", stdin);
	for (i = 0; i < 5; i++)
		printf("%d\n", getchar() != EOF);
	return 0;
}

Exercise 1-7. Write a program to print the value of EOF.

解：这个直接输出就可以了，但是看到的效果不一定很直观，我的机子上的值是-1。

#include <stdio.h>
int main()
{
	printf("%d\n", EOF);
	return 0;
}

Exercise 1-8. Write a program to count blanks, tabs, and newlines.

解：这个也是个简单题，根据前面的内容改改就可以了。

#include <stdio.h>
int bn, tn, ln, c;
int main()
{
	bn = tn = ln = 0;
	while ((c = getchar()) != EOF)
		if (c == ' ')
			bn++;
		else if (c == '\t')
			tn++;
		else if (c == '\n')
			ln++;
	printf("There are %d blanks, %d tabs and %d lines\n", bn, tn, ln);
	return 0;
}

Exercise 1-9. Write a program to copy its input to its output, replacing each string of one or more blanks by a single blank.
解：这个题目要求我们将重复的空格归为一个，其实也很好做，只要记录上次的字符，只要不是上次和本次都是空格就可以输出了。我用了文件操作，这里不进行文件真确性的判定，直接就用了，因为重点在于处理。

#include <stdio.h>
int last, c;
int main()
{
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	last=-1;
	while ((c = getchar()) != EOF) {
		if (last != ' ')
			putchar(c);
		else if (c != ' ')
			putchar(c);
		last = c;
	}
	return 0;
}

Exercise 1-10. Write a program to copy its input to its output, replacing each tab by \t, each backspace by \b, and each backslash by \\. This makes tabs and backspaces visible in an unambiguous way.
解：题目要求将一个输入文件的所有空格，制表符还有反斜杆可视化，这个相对上一题更好做，直接判断即可。

#include <stdio.h>
int c;
int main()
{
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	while ((c = getchar()) != EOF)
		if (c == ' ')
			printf("\\b");
		else if (c == '\t')
			printf("\\t");
		else if (c == '\\')
			printf("\\\\");
		else putchar(c);
	return 0;
}

Exercise 1-11. How would you test the word count program? What kinds of input are most likely to uncover bugs if there are any?
解：这里询问如何测试你的统计程序，对于单词的计数，个人来说会有如下测试数据：文首空格回车制表符，连续空格回车制表符，单字母单词，大小写混用与单词内部符号等。

Exercise 1-12. Write a program that prints its input one word per line.

解：这里题目要求我们每个单词输出一行，我们只需要在文中关于单词统计的部分进行修改就可以了，只要把输出空格或者制表符的部分转化为输出回车即可。

#include <stdio.h>
#define IN	1
#define OUT	0
int c, state;
int main()
{
	state = OUT;
	while ((c = getchar()) != EOF) {
		if (state == IN)
			if (c == ' ' || c == '\n' || c == '\t') {
				state = OUT;
				putchar('\n');
			}
			else
				putchar(c);
		else
			if (c != ' ' && c != '\n' && c != '\t') {
				state = IN;
				putchar(c);
			}
	}
	return 0;
}

Exercise 1-13. Write a program to print a histogram of the lengths of words in its input. It is easy to draw the histogram with the bars horizontal; a vertical orientation is more challenging.
解：这个题目挺好玩，他要我们统计单词长度，然后打出图表，貌似竖着打比横着打更好玩点，于是我就竖着打了。然后找了原文一段话测试了一下，效果还行。

#include <stdio.h>
#define IN	1
#define OUT	0
int c, state, l, i, j, len[30];
int main()
{
	state = OUT;
	for (i = 0; i < 30; i++)
		len[i]=0;
	l = 0;
	len[0] = 1;
	while ((c = getchar()) != EOF)
		if (c != ' ' && c != '\t' && c != '\n') {
			state = IN;
			len[l++]--;
			len[l]++;
		}
		else {
			l = 0;
			if (state == IN)
				len[0] = 1;
			state = OUT;
		}
	for (i = 1, l = 0; i < 30; i++)
		if (len[i] > len[l])
			l = i;
	for (i = len[l]; i >= 1; i--)
	{
		printf("      ");
		for (j = 0; j < 30; j++)
			if (len[j] >= i)
				printf(" XX");
			else printf("   ");
		printf("\n");
	}
	printf("Length");
	for (i = 0; i < 30; i++)
		printf("%3d", i);
	printf("\nNumber");
	for (i = 0; i < 30; i++)
		printf("%3d", len[i]);
	printf("\n");
	return 0;
}

Exercise 1-14. Write a program to print a histogram of the frequencies of different characters in its input.

解：这个就更容易了，只是单独统计字符出现的频率，我们只需要统计后输出结果即可，下面是我的程序，测试数据依然是上一题那段话。

#include <stdio.h>
int c, total, i, cnt[127];
int main()
{
	total = 0;
	for (i = 0; i < 127; i++)
		cnt[i] = 0;
	while ((c = getchar()) != EOF) {
		cnt[c]++;
		total++;
	}
	for (i = 0; i < 127; i++)
		if (cnt[i] > 0) {
			if (i == '\t')
				printf("Tab   : ");
			else if (i == '\n')
				printf("Enter : ");
			else if (i == ' ')
				printf("Space : ");
			else printf("\'%c\'   : ",i);
			printf("%.2f%%\n", 100.0 * cnt[i] / total);
		}
	printf("Total : %d chars!\n", total);
	return 0;
}

Exercise 1.15. Rewrite the temperature conversion program of Section 1.2 to use a function for conversion.

解：这里需要我们利用一个转换函数重写1.2节里头的温度转换程序，目的很明确，程序也很简单。

#include <stdio.h>
double convert(double);
int main()
{
	int fahr;
	for (fahr = 0; fahr <= 300; fahr = fahr + 20)
		printf("%3d %6.1f\n", fahr, convert(fahr));
	return 0;
}
double convert(double fahr)
{
	return (5.0/9.0) * (fahr-32);
}

Exercise 1-16. Revise the main routine of the longest-line program so it will correctly print the length of arbitrary long input lines, and as much as possible of the text.
解：这里需要我们改变原来的程序，使得其计算每行的长度没有限制，并且尽可能多的输出一行，我们可以考虑在每次getline之后判断一下是否读到行尾了，如果不是则要继续读入，但是这一部分不记入原字符串（没地方放了）。同时我在编译的时候貌似getline已经呗占用了，所以用gline来代替，代码如下：

#include <stdio.h>
#define MAXLINE	10
int len, c, max;
char line[MAXLINE], longest[MAXLINE];
int gline(char line[], int maxline);
void copy(char to[], char from[]);
int main()
{
	max = 0;
	while ((len = gline(line, MAXLINE)) > 0) {
		if (line[len - 1] != '\n') {
			while ((c = getchar()) != EOF && c != '\n')
				++len;
			if (c == '\n')
				++len;
		}
		if (len > max) {
			max = len;
			copy(longest, line);
		}
	}
	if (max > 0) {
		printf("The length of the longest line is : %d\n", max);
		printf("%s\n", longest);
	}
	return 0;
}
int gline(char s[], int lim)
{
	int c, i;
	for (i = 0; i < lim - 1 && (c = getchar()) != EOF && c != '\n'; i++)
		s[i] = c;
	if (c == '\n') {
		s[i] = c;
		i++;
	}
	s[i] = '\0';
	return i;
}
void copy(char to[], char from[])
{
	int i;
	i = 0;
	while (to[i] = from[i])
		i++;
}

Exercise 1-17. Write a program to print all input lines that are longer than 80 characters.

解：有了上面那题的经验，做这个就很容易了，首先是将阈值定为81,包括回车在内的字符串长度如果小等于80,那么就不输出，否则就在输出已读入的字符串之后继续按照字符输出。我的程序如下：

#include <stdio.h>
#define THRESHOLD 81
int len, c;
char line[THRESHOLD];
int gline(char line[], int maxline);
int main()
{
	while ((len = gline(line, THRESHOLD)) > 0)
		if (line[len - 1] != '\n') {
			printf("%s", line);
			while ((c = getchar()) != EOF && c != '\n')
				putchar(c);
			if (c == '\n')
				putchar('\n');
		}
	return 0;
}
int gline(char s[], int lim)
{
	int c, i;
	for (i = 0; i < lim - 1 && (c = getchar()) != EOF && c != '\n'; i++)
		s[i] = c;
	if (c == '\n') {
		s[i] = c;
		i++;
	}
	s[i] = '\0';
	return i;
}

Exercise 1-18. Write a program to remove trailing blanks and tabs from each line of input, and to delete entirely blank lines.
解：这个题的解题思路也很明显，首先是读入一行，然后不停删除尾部的空格和制表符，如果删完之后长度为0,那么就不用输出了（一整个空行），否则就把剩下的输出来，如果原先尾部没有回车（如文件尾部），那么就不要输出，否则加进去，我的代码如下：

#include <stdio.h>
#define MAXLENGTH 1000
int len, newline;
char line[MAXLENGTH];
int gline(char line[]);
int main()
{
	while ((len = gline(line)) > 0) {
		if (line[len - 1] == '\n') {
			newline = 1;
			len--;
		}
		else
			newline = 0;
		while (len > 0 && (line[len - 1] == ' ' || line [len - 1] == '\t'))
			len--;
		if (len != 0)
		{
			if (newline == 1) {
				line[len] = '\n';
				len++;
			}
			line[len] = 0;
			printf("%s", line);
		}
	}
	return 0;
}
int gline(char s[])
{
	int c, i;
	for (i = 0; (c = getchar()) != EOF && c != '\n'; i++)
		s[i] = c;
	if (c == '\n') {
		s[i] = c;
		i++;
	}
	s[i] = '\0';
	return i;
}

Exercise 1-19. Write a function reverse(s) that reverses the character string s. Use it to write a program that reverses its input a line at a time.
解：很普式的方式，翻转一个字符串，reverse很容易写，就是一个交换的过程。

#include <stdio.h>
#define MAXLENGTH 1000
int len, newline;
char line[MAXLENGTH];
int gline(char line[]);
void reverse_line(char line[], int len);
int main()
{
	while ((len = gline(line)) > 0) {
		reverse_line(line, len);
		printf("%s", line);
	}
	return 0;
}
int gline(char s[])
{
	int c, i;
	for (i = 0; (c = getchar()) != EOF && c != '\n'; i++)
		s[i] = c;
	if (c == '\n') {
		s[i] = c;
		i++;
	}
	s[i] = '\0';
	return i;
}
void reverse_line(char line[], int len)
{
	int i, j;
	char temp;
	if (line[len - 1] == '\n')
		len--;
	for (i = 0, j = len - 1; i < j; i++, j--)
	{
		temp = line[i];
		line[i] = line[j];
		line[j] = temp;
	}
}

Exercise 1-20. Write a program detab that replaces tabs in the input with the proper number of blanks to space to the next tab stop. Assume a fixed set of tab stops, say every n columns. Should n be a variable or a symbolic parameter?

解：这个题目是要求我们将文章中的tab替换为一定数量的空格，使得下文整好从下一个tab起始列开始，这个就有点像我们在printf中定义宽度所做的工作，然后题目问我们这个空格的数量到底是否应该以变量的形式出现，我的答案是肯定的，因为这样更利于我们进行运行时修改。这里我就不再gline然后原地改了，如果一大行的制表符那将会使得复杂度上升，我就直接一个个字节处理。

#include <stdio.h>
int CalcNumberOfSpace(int len, int tabsize);
int main()
{
	int i, j, c, tabsize = 6, len = 0;
	while ((c = getchar()) != EOF)
		if (c == '\t') {
			j = CalcNumberOfSpace(len, tabsize);
			for (i = 0; i < j; i++)
				putchar(' ');
			len = len + j;
		}
		else if (c == '\n') {
			putchar('\n');
			len = 0;
		}
		else {
			putchar(c);
			len++;
		}
	return 0;
}
int CalcNumberOfSpace(int len, int tabsize)
{
	return tabsize - len % tabsize;
}

Exercise 1-21. Write a program entab that replaces strings of blanks by the minimum number of tabs and blanks to achieve the same spacing. Use the same tab stops as for detab. When either a tab or a single blank would suffice to reach a tab stop, which should be given preference?
解：这里让我们将连续的空格替换为制表符，使得总个数越少越好，当然我们的策略就是尽量替换了。

#include <stdio.h>
#define MAXLINE	1000
#define TABSIZE	4
int gline(char line[]);
int main()
{
	int i, j, len, ns;
	char line[MAXLINE];
	while ((len = gline(line)) > 0) {
		for (i = 0, j = 0, ns = 0; j < len; j++)
			if (line[j] != ' ') {
				while (ns > 0) {
					line[i++] = ' ';
					ns--;
				}
				line[i++] = line[j];
			}
			else {
				ns++;
				if (ns == TABSIZE) {
					line[i++] = '\t';
					ns = 0;
				}
			}
		while (ns > 0) {
			line[i++] = ' ';
			ns--;
		}
		line[i++] = 0;
		printf("%s", line);
	}
	return 0;
}
int gline(char line[])
{
	int c, i;
	for (i = 0; i < MAXLINE - 1 && (c = getchar()) != EOF && c != '\n'; i++)
		line[i] = c;
	if (c == '\n') {
		line[i] = c;
		i++;
	}
	line[i] = '\0';
	return i;
}

Exercise 1-22. Write a program to ``fold'' long input lines into two or more shorter lines after the last non-blank character that occurs before the n-th column of input. Make sure your program does something intelligent with very long lines, and if there are no blanks or tabs before the specified column.

解：这里需要我们写一个将长输入行折叠为短输入行的程序，我做的工作是将原先不超过MAXLEN个字符的都归到一行之中，超过的就将其划分，然后还有一些特别的对于回车的处理，即满了一行后判断后一个字符是否回车，如果是就直接采用，否则就添加，总体显示效果还行，程序如下。

#include <stdio.h>
#define MAXLINE	1000
#define TABSIZE	4
#define FOLDLEN	80
int gline(char line[]);
int main()
{
	int i, j, len, lastspace, cur;
	char line[MAXLINE];
	while ((len = gline(line)) > 0) {
		lastspace = -1;
		for (i = 0, cur = 1; i < len; i++, cur++)
			if (line[i] == '\n') {
				cur = 0;
				lastspace = -1;
			}
			else {
				if (line[i] == ' ')
					lastspace = i;
				if (cur == FOLDLEN) {
					if (line[i+1] == '\n') {
						i++;
						cur = 0;
					}
					else {
						if (lastspace != -1) {
							line[lastspace] = '\n';
							cur = i - lastspace;
						}
						else {
							for (j = len + 1; j > i + 1; j--)
								line[j] = line[j-1];
							line[i+1] = '\n';
							len++;
							i++;
							cur = 0;
						}
					}
					lastspace = -1;
				}
			}
		printf("%s", line);
	}
	return 0;
}
int gline(char line[])
{
	int c, i;
	for (i = 0; i < MAXLINE - 1 && (c = getchar()) != EOF && c != '\n'; i++)
		line[i] = c;
	if (c == '\n') {
		line[i] = c;
		i++;
	}
	line[i] = '\0';
	return i;
}

Exercise 1-23. Write a program to remove all comments from a C program. Don't forget to handle quoted strings and character constants properly. C comments don't nest.
解：这里实现的是编译器的功能，对于注释的处理，这里有几个地方要注意，首先，C的注释是以”/*“和”*/“为界定的，至于两个斜杆那是C++的，这里不予以考虑，实际上方法是一样的；其次，对于在注释之中的字符串是不予以显示的，或者说整个注释都不予以显示；最后，对于字符串中的注释格式字符要当做字符串显示，不可隐掉，注意到这几点程序就很容易得到了。

#include <stdio.h>
#define MAXLINE	1000
int gline(char line[]);
int main()
{
	int quot = 0, comm = 0, i, len;
	char line[MAXLINE];
	while ((len = gline(line)) > 0) {
		for (i = 0; i < len; i++)
			if (comm == 0) {
				if (line[i] == '"')
					quot = 1 - quot;
				if (line[i] == '/' && line[i + 1] == '*' && quot == 0) {
					comm = 1;
					i++;
				}
				else
					putchar(line[i]);
			}
			else if (line[i] == '*' && line[i + 1] == '/') {
				comm = 0;
				i++;
			}
	}
	return 0;
}
int gline(char line[])
{
	int c, i;
	for (i = 0; i < MAXLINE - 1 && (c = getchar()) != EOF && c != '\n'; i++)
		line[i] = c;
	if (c == '\n') {
		line[i] = c;
		i++;
	}
	line[i] = '\0';
	return i;
}

Exercise 1-24. Write a program to check a C program for rudimentary syntax errors like unmatched parentheses, brackets and braces. Don't forget about quotes, both single and double, escape sequences, and comments. (This program is hard if you do it in full generality.)

解：完全写下这个题目是比较有难度的，如果光是匹配括号那倒是容易，直接就用符号栈就可以搞定，关键是还有引号那些的影响，操作就稍微复杂一点，但是认真思考还是可以得到结果的。bug应该是有的，不过程序if-else太多弄得自己太烦了，将就用吧，只返回其中一个错误。

#include <stdio.h>
#define MAXLINE	1000
#define STACKL	500
int gline(char line[]);
int main()
{
	int i, len, dismatch;
	char line[MAXLINE];
	int stack[STACKL];
	stack[0] = 0;
	dismatch = 0;
	while (dismatch == 0 && (len = gline(line)) > 0)
		for (i = 0; i < len; i++)
			if (stack[0] >0 && stack[stack[0]] == '"') {
				if (line[i] == '"')
					stack[0]--;
			}
			else if (stack[0] >0 && stack[stack[0]] == '/') {
				if (line[i] == '*' && line[i+1] == '/') {
					stack[0]--;
					i++;
				}
			}
			else if (line[i] == '(' || line[i] == '[' || line[i] == '{' || line[i] == '"' || (line[i] == '/' && line[i+1] == '*')) {
				stack[++stack[0]] = line[i];
				if (line[i] == '/')
					i++;
			}
			else if (line[i] == ')' || line[i] == ']' || line[i] == '}') {
				if (stack[0] > 0 && ((line[i] == ')' && stack[stack[0]] == '(') || line[i] == stack[stack[0]] + 2))
					stack[0]--;
				else
					dismatch = line[i];
			}
			else if (line[i] == '*' && line[i + 1] == '/')
				dismatch = '*';
			else if (line[i] == '"')
				dismatch = '"';
	if (dismatch == 0)
		if (stack[0] == 0)
			printf("Everything done!\n");
		else if (stack[stack[0]] == '/')
			printf("Symbol /* dismatch!\n");
		else
			printf("Symbol %c dismatch!\n", stack[stack[0]]);
	else
		if (dismatch == '*')
			printf("Missing symbol /*\n");
		else if (dismatch == ')')
			printf("Missing symbol (\n");
		else printf("Missing symbol %c\n", dismatch - 2);
	return 0;
}
int gline(char line[])
{
	int c, i;
	for (i = 0; i < MAXLINE - 1 && (c = getchar()) != EOF && c != '\n'; i++)
		line[i] = c;
	if (c == '\n') {
		line[i] = c;
		i++;
	}
	line[i] = '\0';
	return i;
}

[回复]

henry 说:
2010年9月18日 01:37

问一下：
#include <stdio.h>
#include <stdlib.h>

/* count character in input; 1st version*/
int main(int argc, char *argv[])
{
long nc;

nc = 0;
while( getchar() != EOF)
++nc;
printf("%ld\n",nc);

system("PAUSE");
return 0;
}
我在devC++里运行，首先输入一个字符，可结果是什么都没有。比如，我输入'adsad',结果是跳转到了下一行，没有输出。你能看看问题在哪儿吗？

[回复]

daybreakcx 说:
2011年1月27日 03:27

好久没上来了，是这样的，你的getchar返回了EOF的时候才退出程序，而回车并不代表EOF，一般来说windows下EOF采用的是阻塞式的Ctrl+z，而linux下的用的是非阻塞式的Ctrl+d，那样才表示EOF，你可以试试看