重温K&R(4)
这一章是关于函数和程序结构的，虽然看起来像是基本语法的描述，但是中间穿插了很多东西值得我们进一步思考，闲话少说，开始做题。
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后的语句块不管多少句都加上花括号，这样就没有这种问题了。
评论 (0)
