K&R 第五章 指针与数组
5-1 在上面的例子中,如果符号+或-的后面紧跟的不是数字,getint函数将把符号视为0数字0的有效表达式。修改该函数，将这种形式的+或-符号重新写回到输入流
#include <stdio.h>
#include <ctype.h>
int getch(void);
void ungetch(int);
int getint(int *pn)
{
int c,sign,d;
while(isspace(c=getch())) //跳过空格
;
if(!isdigit(c)&&c!=EOF &&c!='+'&&c!='-')
{
ungetch(c);
return 0;
}
sign=(c=='-')?-1:1;
if(c=='+'||c=='-')
{ d=c;
if(!isdigit(c=getch()))
{
if(c!=EOF)
ungetch(c);
ungetch(d);
return d;
}
}
for(*pn=0;isdigit(c);c=getch())
*pn=10* *pn+(c-'0');
*pn *=sign;
if(c!=EOF)
ungetch(c);
return c;
}
#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;
} 5-2 模仿函数 getint的实现方法，编写一个读取浮点数的函数getfloat。 getfloat函数的返回值应该是什么类型
//返回EOF或者紧跟在浮点数后面的那个字符的ASCII值
int getfloat(float *pn)
{
int c,sign;
float power;
while(isspace(c=getch()))
;
if(!isdigit(c) && c!=EOF&&c!='+'&&c!='-'&&c!='.')
{
ungetch(c);
return 0;
}
sign=(c=='-')?-1:1;
if(c=='+'||c=='-')
c=getch();
for(*pn=0.0;isdigit(c);c=getch())
*pn=10.0* *pn+(c-'0');
if(c=='.')
c=getch();
for(power=1.0;isdigit(c);c=getch())
{
*pn=10.0* *pn+(c-'0');
power *=10.0;
}
*pn *=sign/power;
if(c !=EOF)
ungetch(c);
return c;
} 书中用指针编写的一些案例
#define ALLOCSIZE 10000
static char allocbuf[ALLOCSIZE]; //storage for alloc
static char *allocp=allocbuf; //next free position
char *alloc(int n)
{
if(allocbuf+ALLOCSIZE-allocp >=n)
{
allocp +=n;
return allocp-n;
}
else //not enough room
return 0; //0永远不是有效的数据地址
}
void afree(char *p)
{
if(p>=allocbuf && p<allocbuf+ALLOCSIZE)
allocp=p;
}
//把指针t指向的字符串复制到指针s指向的位置
void strcpy(char *s,char*t)
{
while(*s++=*t++)
;
}
void strcpy_1(char*s,char *t)
{
while(*t!='\0')
*(s++)=*(t++);
*s='\0';
}
void strcpy_2(char *s,char *t)
{
int i;
i=0;
while( (s[i]=t[i]) !='\0')
i++;
}
//比较字符串s和t,并且根据s按照字典顺序小于、等于或大于t分别返回负整数、0或正整数
int strcmp(char *s,char *t)
{
int i;
for(i=0;s[i]==t[i];i++)
if(s[i]=='\0')
return 0;
return s[i]-t[i];
}
int strcmp_1(char*s,char*t)
{
for(;*s==*t;s++,t++)
if(*s=='\0')
return 0;
return *s-*t;
} 5-3 用指针方式实现第2章的strcat。函数strcat(s,t)将t指向的字符串复制到s指向的字符串的尾部
void strcat(char*s,char*t)
{
//while(*s++); //错误
while(*s)
s++;
while(*s++=*t++)
;
} 5-4 编写函数strend(s,t) 如果字符串t出现在字符串s的尾部，该函数返回1，否则返回0
int strend(char*s,char*t)
{
char *bs=s;
char *bt=t;
for(;*s;s++) //end of the string s
;
for(;*t;t++) //end of the string t
;
for(;*s==*t;s--,t--)
if(t==bt||s==bs)
break;
if(*s==*t &&t==bt &&*s!='\0')
return 1;
else
return 0;
} 5-5 实现库函数strncpy、strncat和strncmp,它们最多对参数字符串中的前n个字符进行操作。例如，函数strncpy(s，t，n) 将t中最多前n个字符复制到s中
void strncpy(char*s,char*t,int n)
{
while(*t && n-->0)
*s++=*t++;
while(n-->0)
*s++='\0';
}
#include <string.h>
void strncat(char*s,char*t,int n)
{
strncpy(s+strlen(s),t,n);
}
int strncmp(char*s,char*t,int n)
{
for(;*s==*t;s++,t++)
if(*s=='\0'||--n <=0)
return 0;
return *s-*t;
} 5-6 采用指针而非数组索引方式改写前面章节和练习中的某些程序，例如getline,atoi,itoa,reverse,strindex,getop等
int getline(char*s,int lim)
{
int c;
char *t=s;
while(--lim>0 && (c=getchar())!=EOF &&c!='\n')
*s++ = c;
if(c == '\n')
*s++ =c;
*s = '\0';
return s-t; //返回长度
}
int atoi(char *s)
{
int n,sign;
for(;isspace(*s);s++)
;
sign=(*s=='-')?-1:1;
if(*s=='+'||*s=='-')
s++;
for(n=0;isdigit(*s);s++)
n=10*n+*s-'0';
return sign*n;
}
void reverse(char *s)
{
int c;
char*t;
for(t=s+(strlen(s)-1);s<t;s++,t--)
{
c=*s;
*s=*t;
*t=c;
}
}
void itoa(int n,char *s)
{
int sign;
char *t=s;
if((sign=n)<0)
n=-n;
do{
*s++ = n%10+'0';
}while((n /=10)>0);
if(sign<0)
*s++='-';
*s='\0';
reverse(t);
}
int strindex(char *s,char*t)
{
char *b=s;
char *p,*r;
for(;*s!='\0';s++)
{
for(p=s,r=t;*r!='\0'&&*p==*r;p++,r++)
;
if(r>t&&*r == '\0')
return s-b;
}
return -1;
} 排序：通过指针数组处理长度不一的文本行 排序过程包括下列3个步骤：
- 读取所有输入行
- 对文本行进行排序
- 按次序打印文本行
#include <stdio.h>
#include <string.h>
#define MAXLINES 5000 //最大行数
char *lineptr[MAXLINES]; //pointers to text lines
int readlines(char *lineptr[],int nlines);
void writelines(char*lineptr[],int nlines);
void qsort(char *lineptr[],int left,int right);
void sortFile()
{
int nlines; //读取行数
if((nlines=readlines(lineptr,MAXLINES))>0)
{
qsort(lineptr,0,nlines-1);
writelines(lineptr,nlines);
}
else
{
printf("error:input too big to sort\n");
}
}
#define MAXLEN 1000 //一行最大长度
int getline(char*,int);
char*alloc(int);
int readlines(char *lineptr[],int maxlines)
{
int len,nlines;
char *p,line[MAXLINES];
nlines=0;
while((len=getline(line,MAXLEN))>0)
if(nlines>=maxlines || (p=alloc(len)) ==NULL)
return -1;
else{
line[len-1]='\0'; //delete newline
strcpy(p,line);
lineptr[nlines++] =p;
}
return nlines;
}
void writelines(char *lineptr[],int nlines)
{
while(nlines-- >0)
printf("%s\n",*lineptr++);
}
void swap(char *v[],int i,int j)
{
char *temp;
temp=v[i];
v[i]=v[j];
v[j]=temp;
}
void qsort(char *v[],int left,int right)
{
int i,last;
if(left>=right)
return;
swap(v,left,(left+right)/2);
last=left;
for(i=left+1;i<=right;i++)
if(strcmp(v[i],v[left])<0)
swap(v,++last,i);
swap(v,left,last);
qsort(v,left,last-1);
qsort(v,last+1,right);
} 5-7 重写函数readlines,将输入的文本行存储到由main函数提供的一个数组中，而不是存储到调用alloc分配的存储空间。该函数的运行速度比改写前快多少？
#define MAXLEN 1000
#define MAXSTOP 5000
int readlines_1(char *lineptr[],char*linestor,int maxlines)
{
int len,nlines;
char line[MAXLEN];
char *p=linestor;
char *linestop=linestor+MAXSTOP;
nlines=0;
while((len=getline(line,MAXLEN)) >0)
if(nlines>=maxlines ||p+len>linestop)
return -1;
else
{
line[len-1]='\0';
strcpy(p,line);
lineptr[nlines++]=p;
p +=len;
}
return nlines;
} 5-8 函数day_of_year和month_day中没有进行错误检查，请解决该问题
//日期转换
static char daytab[2][13]={
{0,31,28,31,30,31,30,31,31,30,31,30,31},
{0,31,29,31,30,31,30,31,31,30,31,30,31},
};
//set day of year from month &day
int day_of_year(int year,int month,int day)
{
int i,leap;
leap= year%4 ==0 && year%100!=0 ||year%400==0;
if(month<1 || month>12)
return -1;
if(day<1 || day>daytab[leap][month])
return -1;
for(i=1;i<month;i++)
day +=daytab[leap][i];
return day;
}
//set month,day from day of year
void month_day(int year,int yearday,int *pmonth,int *pday)
{
int i,leap;
if(year<1)
{
*pmonth =-1;
*pday= -1;
return;
}
leap= year%4 ==0 && year%100!=0 ||year%400==0;
for(i=1;yearday>daytab[leap][i];i++)
yearday -=daytab[leap][i];
if(i>12 &&yearday>daytab[leap][12])
{
*pmonth=-1;
*pday=-1;
}
else
{
*pmonth=i;
*pday=yearday;
}
} 5-9 用指针方式代替数组下标方式，改写函数day_of_year和month_day
int day_of_year_1(int year,int month,int day)
{
int leap;
char *p;
if(month<1 || month>12)
return -1;
if(day<1 || day>daytab[leap][month])
return -1;
leap= year%4 ==0 && year%100!=0 ||year%400==0;
p=daytab[leap];
while(--month)
day +=*++p;
return day;
}
void month_day_1(int year,int yearday,int *pmonth,int *pday)
{
int leap;
char *p;
if(year<1)
{
*pmonth =-1;
*pday= -1;
return;
}
leap= year%4 ==0 && year%100!=0 ||year%400==0;
p=daytab[leap];
while(yearday>*++p)
yearday -=*p;
if( p-*(daytab+leap) >12 &&yearday>daytab[leap][12])
{
*pmonth=-1;
*pday=-1;
}
else
{
*pmonth=p-*(daytab+leap);
*pday=yearday;
}
} 5-10 编写程序expr,以计算从命令行输入的逆波兰表达式的值，其中每个运算符或操作数用一个单独的参数表示。例如,命令 expr 2 3 4 + * 计算表达式 2*(3+4)的值
#include <stdio.h>
#include <math.h> //for atof()
#define MAXOP 100 //max size of operand or operator
#define NUMBER '0'
int getop(char []);
void ungets(char []);
void push(double);
double pop(void);
int main11(int argc,char*argv[])
{
char s[MAXOP];
double op2;
while(--argc >0)
{
ungets(" "); //push end of argument
ungets(*++argv);
switch(getop(s))
{
case NUMBER:
push(atof(s));
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:zeor divisor\n");
break;
default:
printf("error:unknown command %s\n",s);
argc=1;
break;
}
}
printf("\t%.8g\n",pop());
return 0;
} 5-11 修改程序entab和detab(第一章练习中编写的函数),使它们接收一组作为参数的制表符停止位.如果启动程序时不带参数,则使用默认的制表符停止位设置
#include <stdio.h>
#define MAXLINE 100
#define TABINC 8
#define YES 1
#define NO 0
int tabpos(int pos,char *tab)
{
if(pos>MAXLEN)
return YES;
else
return tab[pos];
}
void settab(int argc,char*argv[],char*tab)
{
int i,pos;
if(argc <=1)
for(i=1;i<=MAXLEN;i++)
if(i%TABINC ==0)
tab[i]=YES;
else
tab[i]=NO;
else
{
for(i=1;i<=MAXLEN;i++)
tab[i]=NO; //turn off all tab stops
while(--argc>0)
{
pos=atoi(*++argv);
if(pos>0&&pos<=MAXLEN)
tab[pos]=YES;
}
}
}
void entab(char *tab)
{
int c,pos;
int nb=0;
int nt=0;
for(pos=1;(c=getchar())!=EOF;pos++)
if(c==' ')
{
if(tabpos(pos,tab)==NO)
++nb;
else
{
nb=0;
++nt;
}
}
else
{
for(;nt>0;nt--)
putchar('\t');
if(c=='\t')
nb=0;
else
for(;nb>0;nb--)
putchar(' ');
putchar(c);
if(c=='\n')
pos=0;
else if(c=='\t')
while(tabpos(pos,tab)!=YES)
++pos;
}
}
void detab(char *tab)
{
int c,pos=1;
while((c=getchar()) !=EOF)
if(c=='\t')
{
do
putchar(' ');
while(tabpos(pos++,tab) !=YES);
} else if(c=='\n'){
putchar(c);
pos=1;
}else{
putchar(c);
++pos;
}
}
//replace strings of blanks with tabs
int main(int argc,char*argv[])
{
char tab[MAXLEN+1];
settab(argc,argv,tab);
entab(tab);
return 0;
} 5-13 编写程序tail,将其中输入中的最后n行打印出来。默认情况下,n的值为10，但可通过一个可选参数改变n的值，因此，命令 tail -n 将打印其输入的最后n行
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define DEFLINES 10 //default of lines to print
#define LINES 100
#define MAXLEN 100
void error(char *s)
{
printf("%s\n",s);
exit(1);
}
int getline(char*s,int lim)
{
int c;
char *t=s;
while(--lim>0 && (c=getchar())!=EOF &&c!='\n')
*s++ = c;
if(c == '\n')
*s++ =c;
*s = '\0';
return s-t; //返回长度
}
int main(int argc,char *argv[])
{
char *p;
char *buf; //pointer to large buffer
char *bufend; //end of buffer
char line[MAXLEN]; //current input line
char *lineptr[LINES]; //pointers to lines read
int first,i,last,len,n,nlines;
if(argc ==1) //no argument present
n=DEFLINES;
else if(argc ==2 &&(*++argv)[0]== '-')
n=atoi(argv[0]+1);
else
error("usage: tail [-n]");
if(n<1 || n>LINES)
n=LINES;
for(i=0;i<LINES;i++)
lineptr[i]=NULL;
if((p=buf=(char*)malloc(LINES*MAXLEN)) ==NULL)
error("tail:cannot allocate buf");
bufend=buf+LINES*MAXLEN;
last=0;
nlines=0;
while((len=getline(line,MAXLEN)) >0)
{
if(p+len+1>=bufend)
p=buf;
lineptr[last]=p;
strcpy(lineptr[last],line);
if(++last >=LINES)
last=0;
p +=len+1;
nlines++;
}
if(n>nlines)
n=nlines;
first=last-n;
if(first<0)
first +=LINES;
for(i=first;n-->0;i=(i+1)%LINES)
printf("%s",lineptr[i]);
return 0;
} 在给定可选参数-n的情况下,该函数将按数值大小而非字典顺序对输入行进行排序
#include <stdio.h>
#include <string.h>
#define MAXLINES 5000
#define MAXLEN 1000 //一行最大长度
char*lineptr[MAXLINES];
int getline(char*,int);
char*alloc(int);
int readlines(char *lineptr[],int maxlines)
{
int len,nlines;
char *p,line[MAXLINES];
nlines=0;
while((len=getline(line,MAXLEN))>0)
if(nlines>=maxlines || (p=alloc(len)) ==NULL)
return -1;
else{
line[len-1]='\0'; //delete newline
strcpy(p,line);
lineptr[nlines++] =p;
}
return nlines;
}
void writelines(char *lineptr[],int nlines)
{
while(nlines-- >0)
printf("%s\n",*lineptr++);
}
void swap(void *v[],int i,int j)
{
void *temp;
temp=v[i];
v[i]=v[j];
v[j]=temp;
}
int getline(char*s,int lim)
{
int c;
char *t=s;
while(--lim>0 && (c=getchar())!=EOF &&c!='\n')
*s++ = c;
if(c == '\n')
*s++ =c;
*s = '\0';
return s-t; //返回长度
}
#define ALLOCSIZE 10000
static char allocbuf[ALLOCSIZE]; //storage for alloc
static char *allocp=allocbuf; //next free position
char *alloc(int n)
{
if(allocbuf+ALLOCSIZE-allocp >=n)
{
allocp +=n;
return allocp-n;
}
else //not enough room
return 0; //0永远不是有效的数据地址
}
void afree(char *p)
{
if(p>=allocbuf && p<allocbuf+ALLOCSIZE)
allocp=p;
}
void qsort(void*v[],int left,int right,int(*comp)(void*s1,void*s2))
{
int i,last;
if(left >=right)
return;
swap(v,left,(left+right)/2);
last=left;
for(i=left+1;i<=right;i++)
if((*comp)(v[i],v[left])<0)
swap(v,++last,i);
swap(v,left,last);
qsort(v,left,last-1,comp);
qsort(v,last+1,right,comp);
}
#include <stdlib.h>
int numcmp(char *s1,char *s2)
{
double v1,v2;
v1=atof(s1);
v2=atof(s2);
if(v1<v2)
return -1;
else if(v1>v2)
return 1;
else
return 0;
}
typedef int(*cmp)(void*s1,void*s2) ;
int main(int argc,char *argv[])
{
int nlines; //number of inout lines read
int numeric=0; //1 if numeric stort
if(argc>1&& strcmp(argv[1],"-n") ==0)
numeric = 1;
cmp s;
if(numeric)
s= (cmp)(numcmp);
else
s= (cmp)(numcmp);
if((nlines=readlines(lineptr,MAXLINES)) >=0)
{
qsort((void**)lineptr,0,nlines-1, s );
//三元表达式强转报错，拆开写
// qsort((void**)lineptr,0,nlines-1,(int(*)(void*s1,void*s2))(numeric?numcmp:strcmp) );
writelines(lineptr,nlines);
return 0;
}else{
printf("input too big to sort\n");
return 1;
}
}
投递腾讯等公司10个岗位 >
查看4道真题和解析