K&R 第三章 流控制

3-1 在上面有关折半查找的例子中，while循环语句内共执行了两次测试，其实只要一次就足够（代价是将更多的测试在循环外执行）。重写该函数，使得在循环内部只执行一次测试。比较两个版本函数的运行时间。

int binsearch(int x,int v[],int n)
{
	int low,high,mid;
	
	low=0;
	high=n-1;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(x<v[mid])
			high=mid+1;
		else if(x>v[mid])
			low=mid+1;
		else
			return mid;	
	}
	return -1;
}

int binsearch_1(int x,int v[],int n)
{
	int low,high,mid;
	
	low=0;
	high=n-1;
	mid=(low+high)/2;
	while(low<=high && x !=v[mid])
	{
		if(x<v[mid])
			high=mid-1;
		else
			low=mid+1;
		mid=(low+high)/2;
	}
	
	if(x==v[mid])
		return mid;
	else
		return -1;	
	
}

3-2 编写一个函数escape(s, t)，将字符串t复制到字符串s中，并在复制过程中将换行符、制表符等不可见字符分别换成\n、\t等相应的可见的转义字符序列。要求使用switch语句。再编写一个具有相反功能的函数，在复制过程中将转义字符序列转换为实际字符。

void escape(char s[], char t[])
{
    unsigned i, j;

    j   = 0;
    for (i = 0; t[i] != '\0'; ++i) {
        switch (t[i]) {
            case '\n':
                s[j++]  = '\\';
                s[j++]  = 'n';
                break;
            case '\t':
                s[j++]  = '\\';
                s[j++]  = 't';
                break;
            default:
                s[j++]  = t[i];
                break;
        }
    }
    s[j]    = '\0';
}

void unescape(char s[],char t[])
{
	int i,j;
	for(i=j=0;t[i] != '\0';i++)
	{
		if(t[i]!='\\')
			s[j++]=t[i];
		else
			switch(t[++i])
			{
				case 'n':
					s[j++]='\n';
					break;
				case 't':
					s[j++]='\t';
					break;
				default:
					s[j++]='\\';
					s[j++]=t[i];
					break;
			}	
	}
	s[j]='\0';
}

书中一些案例

//将字符串转换为对应数值的atoi
#include <ctype.h>
int atoi(char s[])
{
	int i,n,sign;
	
	for(i=0;isspace(s[i]);i++) //skip white space
			;
	sign=(s[i]== '-')?-1:1;
	if(s[i]=='+' || s[i]=='-')
			i++;
	for(n=0;isdigit(s[i]);i++)
		n=10*n+(s[i]-'0');
	
	return sign * n;	
			
}

//字符串的转置 
void reverse(char s[])
{
	int c,i,j;
	for(i=0,j=strlen(s)-1;i<j;i++,j--)
	{
		c=s[i];
		s[i]=s[j];
		s[j]=c;
	}
}

//将数字转化成字符串 
void itoa(int n,char s[])
{
	int i,sign;
	if((sign=n)<0)
		 n=-n;
	i=0;
	do{
		s[i++]=n%10+'0';
	}while( (n /=10) >0);
	if(sign<0)
		s[i++]='-';
	s[i]='\0';
	reverse(s);
}


//希尔排序
void shellsort(int v[],int n) 
{
	int gap,i,j,temp;
	
	for(gap = n/2;gap>0;gap /=2)
		for(i=gap;i<n;i++)
			for(j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap)
			{
				temp=v[j];
				v[j]=v[j+gap];
				v[j+gap]=temp;
			}
			
}


//删除字符串尾部的空格符、制表符和换行符
int trim(char s[]) 
{
	int n;
	for(n=strlen(s)-1;n>=0;n--)
		if(s[n] !=' '&&s[n] !='\t'&&s[n]!='\n')
			break;
	s[n+1]='\0';
	return n;
}

3-3 编写函数expand(s1, s2)，将字符串s1中类似于a-z一类的速记符号在字符串s2中扩展为等价的完整列表abc…xyz。该函数可以处理大小写字母和数字，并可以处理a-b-c、a-z0-9与-a-z等类似的情况。作为前导和尾随的-字符原样排印。

void expand(char s1[],char s2[])
{
	char c;
	int i,j;
	i=j=0;
	while((c = s1[i++]) !='\0')
		if(s1[i]=='-'&&s1[i+1] >=c)
		{
			i++;
			while(c < s1[i])
				s2[j++]=c++;
		}
		else
			s2[j++]=c;
	s2[j] = '\0';
}

    3-4 在数的对二补码表示中，我们编写的itoa函数不能处理最大的负数，即n等于-(2^字长-1)的情况。请解释原因。修改该函   数，使它在任何机器上运行时都能打印出正确的值。

      -(2^字长-1)无法通过 n=-n转化为正数，对二的补码所能表示的最大正数只能是(2^字长-1)-1

#define abs(x)	 ((x)<0 ? -(x):(x))
void itoa_1(int n,char s[])
{
	int i,j,sign;
	sign=n;
	i=0;
	do{
		s[i++]=abs(n%10)+'0';
	}while( (n/=10)!=0);
	
	if(sign<0)
		s[i++]='-';
	s[i]='\0';
	reverse(s);
}

    3-5 编写函数itob(n, s, b)，将整数n转换为以b为底的数，并将转换结果以字符的形式保存到字符串s中。例如，itob(n, s, 16)
    把整数n格式化成十六进制整数保存在s中。

void itob(int n,char s[],int b)
{
	int i,j,sign;
	sign=n;
	i=0;
	if(b<=0)
		{
			s[i++]='0';
			s[i]='\0';
			return;
		}
	do
	{	
		j=abs(n%b);
		s[i++]=(j<=9)? j+'0':j+'a'-10;
	}while((n/=b)!=0);
	if(sign<0)
		s[i++]='-';
	s[i]='\0';
	reverse(s);
}

    3-6 修改itoa函数，使得该函数可以接收三个参数。其中，第三个参数为最小字段宽度。为了保证转换后所得的结果至少具有第三个参数指定的最小宽度，在必要时应在所得结果的左边填充一定的空格。

void itoa_2(int n, char s[],int w)
{
	int i,j,sign;
	sign=n;
	i=0;
	do{
		s[i++]=abs(n%10)+'0';
	}while( (n/=10)!=0);
	
	if(sign<0)
		s[i++]='-';
	while(i<w)
		s[i++]=' ';
	s[i]='\0';
	reverse(s);
}