K&R 第四章 函数与程序结构

将输入中包含特定“模式”或字符串的各行打印出来

//返回字符串t在字符串s中出现的起始位置或索引。当s不包含t时，返回-1 
int strindex(char s[],char t[])
{
	int i,j,k;
	for(i=0;s[i]!='\0';i++)
	{
		for(j=i,k=0;t[k]!='\0' &&s[j]==t[k];j++,k++)
				;
		if(k>0 && t[k]=='\0')
			return i;
	}
	return -1;
}



int getline(char s[],int lim)
{
	int c,i;
	i=0;
	while(--lim>0&&(c=getchar()) !=EOF &&c!='\n')
		s[i++] =c;
	if(c=='\n')
		s[i++]=c;
	s[i] = '\0';
	return i;
}

#define MAXLINE 1000
char pattern[]="ould";

int main()
{
	char line[MAXLINE];
	int found=0;
	
	while(getline(line,MAXLINE)>0)
		if(strindex(line,pattern)>=0)
		{
			printf("%s",line);
			found++;
		}
	return found;	
}

4-1 编写函数strindex(s,t),它返回字符串t在s中最右边出现的位置。如果s中不包含t，则返回-1

int strindex_1(char s[],char t[])
{
	int i,j,k,pos;
	pos=-1;
	
	for(i=0;s[i]!='\0';i++)
	{
		for(j=i,k=0;t[k]!='\0' &&s[j]==t[k];j++,k++)
				;
		if(k>0 && t[k]=='\0')//找到t在s中的出现位置 
			pos=i;
	}
	return pos;
}


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

4-2 对atof函数进行扩充,使它可以处理形如 123.45e-6的科学表示法,其中,浮点数后面可能会紧跟一个e或E以及一个指数(可能有正负号)

double atof(char s[])
{
	double val,power;
	int i,sign,exp;
	
	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.0;
	}
	val=sign*val/power;
	
	if(s[i]=='e'||s[i]=='E')
	{
		sign=(s[++i]=='-')?-1:1;
		if(s[i]=='+' || s[i]=='-')
			i++;
		for(exp=0;isdigit(s[i]);i++)
				exp=10*exp+(s[i]-'0');
		if(sign==1)		
			while(exp-- >0)
				val *=10;
		else
			while(exp-->0)
				val /=10; //连续“除以10 ”要比“乘以0.1”更精确 
	}
	
	return val;
}

计算器程序，逆波兰表达式输入

#include <stdio.h>
#include <stdlib.h>  //for atof()
#include <math.h>
#include <string.h>

#define MAXOP	100 //max size of operand or operator
#define NUMBER  '0' //signal that a number was found
#define NAME	'n' //signal that a name was found

int getop(char[]);
void push(double);
double pop(void);
void mathfnc(char []);

void calculator()
{
	int i,type,var=0;
	double op2,v;
	char s[MAXOP];
	double variable[26];//26个英文字母变量 
	
	for(i=0;i<26;i++)
		variable[i]=0.0;
	
	while((type = getop(s)) !=EOF)
	{
		switch (type)
		{
			case NUMBER:
					push(atof(s));
					break;
			case NAME:
					mathfnc(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 '%':
					op2=pop();
					if(op2!=0.0)
						push(fmod(pop(),op2)); //把余数压入栈 
					else
						printf("error:zero divisor\n");	
			case '\n':
					v=pop();
					printf("\t%.8g\n",v);
					break;
			case '=':
					pop();
					if(var >='A'&&var <='Z')
						variable[var-'A']=pop();
					else
						printf("error:no variable name\n");
					break;	
			default:
					if(type>='A'&&type<='Z')
						push(variable[type-'A']);
					else if(type=='v')
							push(v);
					else		
					    printf("error:unknow command %s\n",s);
					break;	
		}
		var=type;
	}
}

void mathfnc(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("error:%s not support\n",s);
}


#define MAXVAL 100  //maximum depth of val stack

int sp=0;			//next free stack position
double val[MAXVAL];	//value stack

void push(double f)
{
	if(sp<MAXVAL)
		val[sp++]=f;
	else
		printf("error:stack full,cant not push %g\n",f);
}

double pop(void)
{
	if(sp>0)
		return val[--sp];
	else
	{
		printf("error:stack empty\n");
		return 0.0;
	}	
}

void clear(void)
{
	sp=0;
}

#include <ctype.h>
int getch(void);
void ungetch(int);

//获取下一个运算符或操作数 
int getop(char s[])
{
	int i,c;
	while((s[0]=c=getch()) == ' '|| c=='\t')//跳过空格或制表符 
			;
	s[1]='\0';
	i=0;
	
	if(islower(c))
	{
		while(islower(s[++i]=c=getch()))
				;
		s[i]='\0';
		if(c!=EOF)
			ungetch(c);
		if(strlen(s)>1)	
			return NAME;
		else
			return c;	
	}
	
	if(!isdigit(c) && c!='.'&&c!='-')
		return c;
	if(c == '-')
		if(isdigit(c =getch()) ||c=='.')
			s[++i] =c;   //负数 
		else
		{
			if(c!=EOF)
				ungetch(c);
			return '-';     //符号 
		}	

	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;	
}

//把字符串s压回到输入中 
#include <string.h>

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

#define BUFSIZE 100
char buf[BUFSIZE];
int bufp=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 printd(int n) 
{
	if(n<0)
	{
		putchar('-');
		n=-n;
	}
	
	if(n/10)
		printd(n/10);
	
	putchar(n%10+'0');
}

//交换
void swap(int v[],int i,int j)
{
	int temp;
	temp=v[i];
	v[i]=v[j];
	v[j]=temp;
}

//快排
void qsort(int v[],int left,int right)
{
	int i,last;
	if(left>=right)
		return;
	swap(v,left,(left+right)/2); //move partition elem
	last=left;
	for(i=left+1;i<=right;i++)
		if(v[i]<v[left])
			swap(v,++last,i);
	swap(v,left,last);
	qsort(v,left,last-1);
	qsort(v,last+1,right);
}

4-12 运用printd函数的设计思想编写一个递归版本的itoa函数，即通过递归调用把整数转换成字符串

void itoa(int n,char s[]) 
{
	static int i;
	if(n/10)
		itoa(n/10,s);
	else
	{
		i=0;
		if(n<0)
			s[i++]='-';
	}
	s[i++]=abs(n)%10+'0';
	s[i]='\0';
}

4-13 编写一个递归版本的reverse(s)函数，以将字符串s倒置

void reverser(char s[],int i,int len)
{
	int c,j;
	j=len-(i+1);
	if(i<j)
	{
		c=s[i];
		s[i]=s[j];
		s[j]=c;
		reverser(s,++i,len);
	}
}
void reverse(char s[])
{
	reverser(s,0,strlen(s));
}

4-14 定义宏swap(t,x,y)以交换t类型的两个参数

#define swap1(t,x,y) { t _z; \
		        _z=y;\
		        y=x; \
			x=_z;}