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);
}
投递旷视等公司10个岗位 >
