重温K&R(4) - Daybreakcx's Blog - Keep Programming! With Algorithm! With Fun!
重温K&R(3)
小区别,大容量

重温K&R(4)

daybreakcx posted @ 2010年2月11日 19:18 in 学习笔记 , 3383 阅读

这一章是关于函数和程序结构的,虽然看起来像是基本语法的描述,但是中间穿插了很多东西值得我们进一步思考,闲话少说,开始做题。

 

Exercise 4-1. Write the function strindex(s,t) which returns the position of the rightmost occurrence of t in s, or -1 if there is none.

        解:第一个题目是要求我们进行串匹配,同时要求我们返回的是最后一个匹配串的位置,没有就返回-1。有了原文中程序作为样例,这个程序很容易就能出来了,还是老话,改改就能用。

int strindex(char s[], char t[])
{
	int l = strlen(t), i, j, k;
	for (i = strlen(s) - 1; i >= 0 && i >= l - 1; i--) {
		for (j = i, k = l - 1; k >= 0 && s[j] == t[k]; j--, k--)
			;
		if (k == -1)
			return j + 1;
	}
	return -1;
}

 

Exercise 4-2. Extend atof to handle scientific notation of the form 123.45e-6 where a floating-point number may be followed by e or E and an optionally signed exponent.
        解:会处理普通实数字符串同样也要会处理科学记数法的,这里就是让我们干这个,很简单其实,前面用atof后面如果有e或者E用atoi,最后一组合就是答案:

double atof(char s[])
{
	double val, power;
	int i, sign, ex;
	for (i = 0; isspace(s[i]); i++)
		;
	sign = (s[i] == '-') ? -1 : 1;
	if (s[i] == '+' || s[i] == '-')
		i++;
	for (val = 0.0; isdigit(s[i]); i++)
		val = 10.0 * val + (s[i] - '0');
	if (s[i] == '.')
		i++;
	for (power = 1.0; isdigit(s[i]); i++) {
		val = 10.0 * val + (s[i] - '0');
		power *= 10;
	}
	if (!s[i])
		return sign * val / power;
	val = sign * val / power;
	ex = atoi(s + i + 1);
	sign = (ex < 0) ? -1 : 1;
	for (power = 1.0, i = 0; i != ex; i += sign)
		power *= 10.0;
	return (ex < 0) ? val / power : val * power;
}

 

Exercise 4-3. Given the basic framework, it's straightforward to extend the calculator. Add the modulus (%) operator and provisions for negative numbers.
        解:这里需要能够多处理一取模运算,然后还要处理负数,取模运算其实就是在原先的出发的基础上改改,只不过貌似原先的模都是整数操作,所以强制取整一下,然后还有负数的处理,其实就是判断负号后头是否为紧跟数字,如果是的话就当做负数处理,实际上不难的,这里将原先的代码也贴出来,完整的代码挺长的,实际上改动的部分并不多。

#include <stdio.h>
#include <stdlib.h>
#define MAXOP    100
#define MAXVAL   100
#define NUMBER   '0'
#define BUFSIZE  100
int sp = 0, bufp = 0;
double val[MAXVAL];
char buf[BUFSIZE];
int getch(void);
void ungetch(int c);
int getop(char []);
void push(double);
double pop(void);
int main()
{
	int type, op2m;
	double op2;
	char s[MAXOP];
	while ((type = getop(s)) != EOF) {
		switch (type) {
		case NUMBER:
			push(atof(s));
			break;
		case '+':
			push(pop() + pop());
			break;
		case '*':
			push(pop() * pop());
			break;
		case '-':
			op2 = pop();
			push(pop() - op2);
			break;
		case '/':
			op2 = pop();
			if (op2 != 0.0)
				push(pop() / op2);
			else
				printf("error: zero divisor\n");
			break;
		case '%':
			op2m = (int)pop();
			if (op2m)
				push((int)pop() % op2m);
			else
				printf("error: zero divisor\n");
			break;
		case '\n':
			printf("\t%.8g\n", pop());
			break;
		default:
			printf("error: unknown command %s\n", s);
			break;
		}
	}
	return 0;
}
int getch(void)
{
    return (bufp > 0) ? buf[--bufp] : getchar();
}
void ungetch(int c)
{
    if (bufp >= BUFSIZE)
         printf("ungetch: too many characters\n");
    else
         buf[bufp++] = c;
}
void push(double f)
{
	if (sp < MAXVAL)
		val[sp++] = f;
	else
		printf("error: stack full, can't push %g\n", f);
}
double pop(void)
{
	if (sp > 0)
		return val[--sp];
	else {
		printf("error: stack empty\n");
		return 0.0;
	}
}
int getop(char s[])
{
	int i, c, next;
	while ((s[0] = c = getch()) == ' ' || c == '\t')
		;
	s[1] = '\0';
	if (!isdigit(c) && c != '.' && c != '-')
		return c;
	i = 0;
	if (c == '-') {
		if (!isdigit(next = getch()) && next != '.')
			return c;
		s[++i] = c = next;
	}
	if (isdigit(c))
		while (isdigit(s[++i] = c = getch()))
			;
	if (c == '.')
		while (isdigit(s[++i] = c = getch()))
			;
	s[i] = '\0';
	if (c != EOF)
		ungetch(c);
	return NUMBER;
}

 

Exercise 4-4. Add the commands to print the top elements of the stack without popping, to duplicate it, and to swap the top two elements. Add a command to clear the stack.
        解:这里要求我们对栈添加几个操作,包括了查看栈顶元素(不弹出),复制栈顶元素,交换顶部两个元素还有清空栈的操作,实际上都是很容易实现的,操作符定义这里就不说了,关键是实现的函数,罗列一下如下所示。

void printtop(void)
{
	if (sp)
		printf("The top of the stack is: %.8g\n", val[sp - 1]);
	else
		printf("The stack is empty!\n");
}
void duplicate(void)
{
	double temp;
	if (sp) {
		temp = pop();
		push(temp);
		push(temp);
	}
	else
		printf("The stack is empty!\n");
}
void swaptop(void)
{
	double temp1, temp2;
	if (sp >= 2) {
		temp1 = pop();
		temp2 = pop();
		push(temp1);
		push(temp2);
	}
	else
		printf("The elements are not enough!\n");
}
void clearstack(void)
{
	sp = 0;
}

 

Exercise 4-5. Add access to library functions like sin, exp, and pow. See <math.h> in Appendix B, Section 4.

        解:这里加入如sin,exp,pow等操作,其实也是很简单的,该怎么改就怎么改,对于这种类型的操作我们可以独立加入一个宏(如FUN)表示是数学函数操作,然后多一个case就可以了,当然操作符那里也要费点心改改了。

#include <string.h>
#include <math.h>
#define FUN      'a'
void oper(char []);

/*Add to the main switch*/
		case FUN:
			oper(s);
			break;
/*Add to the main switch*/

int getop(char s[])
{
	int i, c, next;
	while ((s[0] = c = getch()) == ' ' || c == '\t')
		;
	s[1] = '\0';
	i = 0;
	if (isalpha(c)) {
		while (isalpha(s[++i] = c = getchar()))
			;
		return FUN;
	}
	if (!isdigit(c) && c != '.' && c != '-')
		return c;
	if (c == '-') {
		if (!isdigit(next = getch()) && next != '.')
			return c;
		s[++i] = c = next;
	}
	if (isdigit(c))
		while (isdigit(s[++i] = c = getch()))
			;
	if (c == '.')
		while (isdigit(s[++i] = c = getch()))
			;
	s[i] = '\0';
	if (c != EOF)
		ungetch(c);
	return NUMBER;
}
void oper(char s[])
{
	double op2;
	if (strcmp(s, "sin") == 0)
		push(sin(pop()));
	else if (strcmp(s, "cos") == 0)
		push(cos(pop()));
	else if (strcmp(s, "exp") == 0)
		push(exp(pop()));
	else if (strcmp(s, "pow") == 0) {
		op2 = pop();
		push(pow(pop(), op2));
	}
	else
		printf("%s is not a supported function.\n", s);
}

 

Exercise 4-6. Add commands for handling variables. (It's easy to provide twenty-six variables with single-letter names.) Add a variable for the most recently printed value.
        解:任务来了,这里要我们处理变量,题目中说提供的是26个单字母变量我就假设是小写字母,原来val的结构要发生变化,因为数值栈中可能存入的是数值也可存入变量,我们这么改结构:

struct node {
	double realval;
	char var;
}val[MAXVAL];
double vval[26];
int getval[26];

这里val的结构变成了两个域,一个是用来表示实际数值的,一个是用来判定是哪个变量的,如果是一个变量,那么var就对应其变量名,否则var就设置为0(不是小写字母就可以了)同时realval就是真实的值域,而getval则表示原先是否已经得到过这个变量的值了,如果得到过就为1,否则就为0,vval记录的是在getval为1的情况下全局的变量值。原先的push和pop操作相应地做如下改动:

void push(double f, int isvar, int var)
{
	if (sp == MAXVAL)
		printf("error: stack full, can't push %g\n", f);
	else {
		if (!isvar) {
			val[sp].realval = f;
			val[sp].var = 0;
		}
		else {
			if (getval[var] == 1) {
				val[sp].realval = vval[var];
				val[sp].var = 0;
			}
			else
				val[sp].var = var;
		}
		sp++;
	}
}
double pop(void)
{
	if (sp > 0) {
		if (val[sp - 1].var == 0)
			return val[--sp];
		else
			if (getval[val[sp - 1].var] == 1)
				return vval[val[--sp].var];
			else
				printf("error: undefined variable first used!\n");
	}
	else {
		printf("error: stack empty\n");
		return 0.0;
	}
}

这里遇到一个问题,就是如果是赋值操作,那么需要一下特殊处理了:

int spop(void)
{
	if (sp > 0) {
		if (val[sp - 1].var == 0) {
			printf("error: the = operation must be set to a variable!\n");
			return 0;
		}
		else
			return val[--sp].var;
	}
	else {
		printf("error: stack empty\n");
		return 0;
	}
}

接下来剩下的就只有case语句关于“=“的操作了,这里其实已经很明显了,和普通二元操作一样,只不过是第二个pop用上面的pops代替:

case '=':
	op2 = pop();
	op2m = spop();
	getval[op2m] = 1;
	vval[op2m] = op2;
	push(op2, 1, op2m);

对于数值和变量的push,区别就在于isvar的值为0和1了。

 

Exercise 4-7. Write a routine ungets(s) that will push back an entire string onto the input. Should ungets know about buf and bufp, or should it just use ungetch?

        解:这里需要我们用ungetch构造一个ungets来回退整个字符串,这个问题我们只需要逐个操作就可以了,细节交给ungetch。

void ungets(char s[])
{
	int i;
	for (i = strlen(s); i >= 0; i--)
		ungetch(s[i]);
}

 

Exercise 4-8. Suppose that there will never be more than one character of pushback. Modify getch and ungetch accordingly.

        解:假设回退的字符不会超过一个,相应地修改getch和ungetch。既然这样,等于告诉我们buf的大小为1了,这里假设用-1来表示buf为空,其实就是把数组改成单个元素的操作。

int buf = -1;
int getch(void)
{
	int temp;
	if (buf != -1) {
		temp = buf;
		buf = -1;
	}
	else
		temp = getchar();
  return temp;                          
} 
void ungetch(int c)
{
	if (buf != -1)
		printf("ungetch: too many characters\n");
	else
		buf = c;
}

 

Exercise 4-9. Our getch and ungetch do not handle a pushed-back EOF correctly. Decide what their properties ought to be if an EOF is pushed back, then implement your design.
        解:这里说getch和ungetch对于push-back的处理并不正确,题目让我们给出正确处理EOF的实现。我认为问题出在ungetch上,基本上getch没有改动的必要,只要在判断bufp和BUFSIZE的那段加上一个对于EOF的忽略操作就可以实现对于EOF的处理,这个题目没有完全解决,没完全理解题目意思,先留着以后再说

 

Exercise 4-10. An alternate organization uses getline to read an entire input line; this makes getch and ungetch unnecessary. Revise the calculator to use this approach.

        解:这题基本上内容就多了,要我们将原先的代码用读取一整行的方式来执行而省掉getch和ungetch,其实不难,因为我们的getch和ungetch实际上将文件当做了一个字符流,我们只要每次getch的时候往后移动当前字符指针,每次ungetch的时候往前移动即可,基本上代码没太大变化,这里只贴一下对应getch和ungetch的操作,实际中只要改到原文的调用中就可以了。

int getch(void)
{
	if (buf[bufp] == '\0') {
		getline(buf);
		bufp = 0;
	}
	return buf[bufp++];
}
void ungetch()
{
	if (bufp == 0)
		printf("error: unable to roll back\n");
	else
		bufp--;
}

 

Exercise 4-11. Modify getop so that it doesn't need to use ungetch. Hint: use an internal static variable.

        解:这里要我们修改getop是的不需要使用ungetch,提示是说用一个内部静态变量。说来也奇怪,如果没有保证缓冲区大小为1的话,之用一个变量(如一个整型)这个不好实现,因为那个需要开一整个数组来缓冲字符,但是根据题目的意思以及别人的解答,大多数都是假设其缓冲不超过一个char,而且这个题目是跟随4-8之后的,我们有理由相信这个缓冲区可能就是在4-8的基础上改的,我们暂时就这么假设,如果有问题回来再改。

#include <stdio.h>
#include <ctype.h>
#define NUMBER  '0'
int getop(char s[])
{
	int i, c;
	static int buf = -1;
	if (buf == ' ' || buf == '\t')
		buf = -1;
	if (buf != -1)
		if (!isdigit(buf) && buf != '.') {
			c = buf;
			buf = -1;
			return c;
		}
		else
			s[0] = c = buf;
	else
		while ((s[0] = c = getch()) == ' ' || c == '\t')
			;
	buf = -1;
	s[1] = '\0';
	if (!isdigit(c) && c != '.')
		return c;
	i = 0;
	if (isdigit(c))
		while (isdigit(s[++i] = c = getch()))
			;
	if (c == '.')
		while (isdigit(s[++i] = c = getch()))
			;
	s[i] = '\0';
    buf = c;
    return NUMBER;
}

 

Exercise 4-12. Adapt the ideas of printd to write a recursive version of itoa; that is, convert an integer into a string by calling a recursive routine.

        解:这里讲到递归,需要我们用递归来写一个itoa,有了printd的基础,itoa的递归形式并不难,我的itoa处理的是有符号整数,范围为int,返回为最尾指针方便我进行后续操作,这样不用像网上其他的方法那样反复调用,也省去了reverse。

char* itoa(int n, char s[])
{
	if (n < 0) {
		s[0] = '-';
		return itoa(-n, s+1);
	}
	else if (n < 10) {
		s[0] = n + '0';
		s[1] = '\0';
		return s+1;
	}
	else
		return itoa(n % 10, itoa(n / 10, s));
}

 

Exercise 4-13. Write a recursive version of the function reverse(s), which reverses the string s in place. 

        解:这个题目也很有意思,要我们书写一个递归函数reverse,并且是直接在原来的字符串上操作,现在本人就发现了一种原地操作的,其他的要么调用了strlen之类函数,要么是先获得头尾再操作(本质上一样),反正貌似都于题意不符,当然这种方法的空间复杂度就上去了,是平方级的,没办法,练习递归嘛。

void reverse(char s[])
{
	if (s[1] == '\0')
		return;
	reverse(s + 1);
	for (; s[1]; s++)
		s[0] ^= s[1], s[1] ^= s[0], s[0] ^= s[1];
}

 

Exercise 4-14. Define a macro swap(t,x,y) that interchanges two arguments of type t. (Block structure will help.)

        解:这里让我们定义一个通用的宏,其元素x和y的类型为t,根据原文的内容我们很容易得到如下结果(PS:至于为什么需要那个do-while语句,下面会说),同样留下疑问。

#define swap(t, x, y) do{t z = x; x = y; y = z;} while(0)

 

小结:

1.函数的声明参数部分可以不带参数名,而只有参数类型,记住声明最后的分号

2.变量声明时候的关键字

        register是让CPU尽可能用寄存器存储以提高效率,因此无法取地址

        auto是设置为自动,其实可以忽略不写效果是一样的

        static修饰的变量会放在全局变量的区域中,减少重复申请释放的开销,有全局效果,但是作用域是本文件中,无法被其他文件extern获得,其声明时初始化赋值只进行一次

        extern告知编译器这里引用一个外来的变量,不在本文件中定义,但是一定在工程某个源文件中或者某个DLL的输出中

        const一般用户常量的声明,进行数据写保护

                (1)函数参数:在函数调用的时候如果类型为非内部类型(int,char等为内部类型,结构体等为非内部类型)foo(A a)为值传递,改为foo(const A &a)为const引用传递,可以提高效率,内部类型不需要这么操作

                (2)函数返回:一般只对指针作为返回值的进行const修饰,这样可以保证其只读性质,同时外部接受返回的也许要const修饰,如const char * GetString(void);返回时候要用const char *str = GetString();来进行返回,而对于值传递的返回则不要这么做,因为数值都是放到临时存储单元

                (3)变量声明:在网上找到一个不错的比较表

                        const在前:

                        const int nValue; //nValue是const

                        const char *pContent; //*pContent是const, pContent可变

                        const (char *) pContent;//pContent是const,*pContent可变

                        char* const pContent; //pContent是const,*pContent可变

                        const char* const pContent; //pContent和*pContent都是const

                        const在后:

                        int const nValue; // nValue是const

                        char const * pContent;// *pContent是const, pContent可变

                        (char *) const pContent;//pContent是const,*pContent可变

                        char* const pContent;// pContent是const,*pContent可变

                        char const* const pContent;// pContent和*pContent都是const

        volatile表明变量的值可能在外部被改变,一般用于多线程编程中,每次读入值都要从内存中读而不是寄存器中的备份。const和volatile可以同时使用,后者表明其可能被意想不到的改变,前者表示他不该被改变

3.include语句中<>和""的区别,后者只在当前文件夹找

4.宏换行的时候用符号“\”,在宏函数中,所有的参数使用的地方尽量加上括号保证无岐义

5.宏的特殊参数#,下面两个式子为例,#define dprint(expr) printf(#expr " = %g\n", expr)中调用dprint(x/y)表示printf("x/y" " = &g\n", x/y);字符串合并后即printf("x/y = &g\n", x/y);,另一种形式是#define paste(front, back) front ## back作用如调用paste(name, 1)结果是name1

6.宏中do{}while(0)的使用,是为了避免当宏函数有多个语句的时候,被分割成了不同的部分,比如在if语句后如果调用宏函数,那么就会有两个问题,一是如果后头有else就会让else没有if,二是如果没有else就会让if只对第一个语句有效,当然有的说写宏函数的时候加上外围大括号,但是如果那样的话调用后就会多出一个分号使得else无法接入,所以多语句的时候用do{}while(0)语句(注意,右括号后没有分号),良好的习惯是if-else后的语句块不管多少句都加上花括号,这样就没有这种问题了。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter