hello world!
分类： C/C++
2011-07-16 18:21:38
4.1 Basics of Functions:
To begin with, let us design and write a program to print each line of its input that contains a particular ``pattern'' or string of characters. (This is a special case of the UNIX program grep.) For example, searching for the pattern of letters ``ould'' in the set of lines
Ah Love! could you and I with Fate conspire
To grasp this sorry Scheme of Things entire,
Would not we shatter it to bits -- and then
Re-mould it nearer to the Heart's Desire!
will produce the output
Ah Love! could you and I with Fate conspire
Would not we shatter it to bits -- and then
Re-mould it nearer to the Heart's Desire!
The job falls neatly into three pieces:
while (there's another line)
if (the line contains the pattern)
print it
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.
/*
*getline: get a line form input
*/
#define GETLINE_MAXLINE 100 //maximum input a line length
char pattern[] = "ould";
int getline(char s[],int lim) //get a line
{
int c,i;
for(i=0;(i
s[i]=c;
}
if(c=='\n'){
s[i++]=c;
}
s[i]='\0';
//printf("line: %s\n",s);
return i;
}
/**
strrindex(s,t) : return the position in the left of string s ,where the sting t begins
s : the string.
t : the string.
returns : -1 is not found
**/
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++)
NULL;
if(k>0 && t[k]=='\0')
return i;
}
return -1;
}
/**
strrindex(s,t) : return the position in the right of string s ,where the sting t begins
s : the string.
t : the string.
returns : -1 is not found
**/
int strrindex(char s[],char t[])
{
int i,j,k,pos=-1;
for(i=0;s[i]!='\0';i++){
for(j=i,k=0;t[k]!='\0' && s[j]==t[k];j++,k++)
NULL;
if(k>0 && t[k]=='\0')
pos=i;
}
return pos;
}
int strindex_test()
{
char line[GETLINE_MAXLINE];
int found=0,i=0;
printf("***********strindex test**********\n");
while(getline(line,GETLINE_MAXLINE))
if( (i=strindex(line,pattern)) >=0 ){
printf("location :%d. %s",i,line);
found++;
}
printf("match %d lines.\n",found);
return found;
}
4.2 Functions Returning Non-integers:
First, atoi itself must declare the type of value it returns, it is int. The type name precedes the function name:
/**
atoi(s,t) : convert string s to int.
s : the string.
returns : int.
**/
int atoi(char s[])
{
int val,power;
int i,j,sign,temp;
for(i=0;isspace(s[i]);i++) //skip white space
NULL;
sign=s[i]=='-' ? -1:1; //plus or negative
if(s[i]=='+' || s[i]=='-')
i++;
for(val=0;isdigit(s[i]);i++)
val=10*val+(s[i]-'0');
return sign*val;
}
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(s,t) : convert string s to double,can
s : the string.
returns : double.
**/
double atof(char s[])
{
double val,power,temp;
int i,j,n,sign,sign1;
char e_max[4];
for(i=0;isspace(s[i]);i++) //skip white space
NULL;
sign=s[i]=='-' ? -1:1; //plus or negative
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;
}
//printf(" sign: %d val: %g power:%g \n",sign,val,power);
if(s[i]=='e'||s[i]=='E'){
++i;
if(isdigit(s[i+1])){
//printf("-!!%d\n",(s[i+1]-'0'));
e_max[0]=s[i]; //restore the +- sign.
++i;
for(n=1;isdigit(s[i]);i++,n++){
e_max[n]=s[i];
}
e_max[n]='\0';
printf("e_max:%s! e_max:%d\n",e_max,atoi(e_max));
for(temp=1,n=abs(atoi(e_max));n>0;n--)
temp=temp*10;
printf("temp:%g\n",temp);
if(atoi(e_max)>=0)
return (sign*val/power)*(double)temp; //- sign
else if(atoi(e_max)<0)
return (sign*val/power)/(double)temp;
else
printf("the falut input number!\n");
}
}
else
return sign*val/power;
}
4.3 External Variables:
A C program consists of a set of external objects, which are either variables or functions. The adjective ``external'' is used in contrast to ``internal'', which describes the arguments and variables defined inside functions. External variables are defined outside of any function, and are thus potentionally available to many functions.
If a large number of variables must be shared among functions, external variables are more convenient and efficient than long argument lists.
Exercise 4-3. Given the basic framework, it's straightforward to extend the calculator. Add the modulus (%) operator and provisions for negative numbers.
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.
Exercise 4-5. Add access to library functions like sin, exp, and pow. See
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.
/*we integrate all answers in a file of c*/
/**
push(f) : push f onto value stack.
pop() : pop and return top value from stack.
**/
#define PUSH_MAXVAL 100 //the depth of value stack.
int push_sp=0;
double push_val[PUSH_MAXVAL];
void push(double f)
{
if(push_sp
push_val[push_sp++]=f;
else
printf("error:stack full, can't push %g\n",f);
}
double pop(void)
{
if(push_sp>0)
return push_val[--push_sp];
else {
printf("error:stack empty\n");
return 0.0;
}
}
/**
getch() : get a (possibly pushed-back) character.
ungetch() : push character back on input.
**/
#define GETCH_BUFFSIZE 100 // getch()&ungetch() buffer size.
char getch_buf[GETCH_BUFFSIZE]; // getch()&ungetch() buffer.converting "char"
// to "int" can handle "EOF".
int getch_bufp=0; // getch()&ungetch() buffer pointer
int getch(void)
{
return (getch_bufp>0) ? getch_buf[--getch_bufp]: getchar();
}
int ungetch(int c)
{
if(getch_bufp>=GETCH_BUFFSIZE){
printf("ungetch:too many characters!\n");
return -1;
}
else{
getch_buf[getch_bufp++]=c;
return c;
}
}
/**
ungets() : push string back onto the input.
**/
int ungets(char s[])
{
int len=strlen(s);
while(len>0)
ungetch(s[--len]);
}
/**
clear_stack() : clear the stack and the pointer point the first element.
**/
void clear_stack()
{
for(;push_sp>=0;push_sp--)
push_val[push_sp]=0;
push_sp++;
printf("push_sp:%d\n",push_sp);
}
/**
getop() : get a (possibly pushed-back) character amd can handle negative number.
return : if 1 ,then it is a number. -1:then not a number.
**/
#define NAME 'n'
#define NUMBER '0'
int getop(char s[])
{
int i,c;
while( (s[0]=c=getch()) ==' ' || c=='\t')
NULL;
s[1]='\0';
printf("s[0]:%c\n",s[0]);
/*if(!isdigit(c)&&c!='.'&&c!='-'){ //&&'-'
printf("debug:\"--%c--\"not a number.\n",c);
return c;} //not a number
*/
i=0;
if(islower(c)){
while(islower(s[++i]=c=getch())){
printf("lower:%c s[i]:%c char flag:%d!\n",c,s[i],islower('c'));
}
s[i]='\0';
printf("islower:%s\n",s);
if(c!=EOF)
ungetch(c);
if(strlen(s)>1)
return NAME;
else
return s[0];
}
if(!isdigit(c)&&c!='.'&&c!='-'){ //&&'-'
printf("debug:\"--%c--\"not a number.\n",c);
return c;} //not a number
if(c=='-') //can detect negative number
if(isdigit(c=getch())||c=='.'){
printf("-num:%c!\n",c);
s[++i]=c;} //negative number
else{
if(c!=EOF){
printf("unnum:%c!\n",c);
ungetch(c);}
return '-';
}
if(isdigit(c)) //collect integer part
while(isdigit(s[++i]=c=getch()))
NULL;
if(c=='.')
while(isdigit(s[++i]=c=getch()))
NULL;
s[i]='\0';
ungetch(' '); //when detect that a line is input,plus ' '.
//so it can handle "1 2-3 4+*",not as "-3" processing.
//"-1 -3--4 -3+*" also can do it.it will input ' ' after
//each string as "3-","-3-" or "3+".
if(c!=EOF)
ungetch(c);
return NUMBER; //a number
}
void mathfunc(char s[])
{
double op2;
if(strcmp(s,"sin")==0)
push(sin(pop()));
else if(strcmp(s,"cos")==0)
push(sin(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 supperted\n",s);
}
/**
polish_cal() : reverse Polish calculator.
**/
#define MAX_OP 100 //max size of operand or opertor
void polish_cal(void)
{
int i,type,var=0;
double op1,op2,v; //restore the second opertor.
//restore the recent input value.
double variable[26]; //the buffer of 26 characteristic variable.
char s[MAX_OP]; //getop(s[]) can restore MAX_OP chars.
for (i=0;i<26;i++) //initialize the variable.
variable[i]=0.0;
printf("**********polish_cal()**********\n");
while((type=getop(s))!=EOF){
switch (type){
case NUMBER:
printf("type :%d string:%s!\n",type,s);
printf("atof :%g \n",atof(s));
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");
break;
case '%':
printf("type :%c. \n",type);
op2=pop();
if(op2!=0.0)
push(fmod(pop(),op2));
else
printf("error:zero divisor\n");
break;
case 'd': //clear the stack
clear_stack();
printf("\tresult:%.8f\n",pop());
break;
case 'p': //print top element of the stack
op2=pop();
printf("the top number of stack is:%g\n",op2);
push(op2);
break;
case 'c': // copy the top element of the stack
op2=pop();
push(op2);
push(op2);
break;
case 's': // swap the top two elements
op2=pop();
op1=pop();
push(op2);
push(op1);
break;
case NAME:
printf("type :%c string:%s!\n",type,s);
mathfunc(s);
break;
case '=':
pop();
if(var>='A' && var<='Z')
variable[var-'A']=pop();
else
printf("error: no variable name!\n");
break;
case 'v':
push(v);
printf("push v:%g\n",v);
break;
case '\n':
v= pop();
printf("\tresult:%g\n",v);
break;
default:
printf("error:type %c %d. unknown command %s\n",type,type,s);
if(type>='A' && type<='Z')
push(variable[type-'A']);
else if(type=='v'){
push(v);
printf("push v:%g\n",v);}
else
;
break;
}
var=type;
}
}
3.4 Scope Rules:
The scope of a name is the part of the program within which the name can be used. For an automatic variable declared at the beginning of a function, the scope is the function in which the name is declared. Local variables of the same name in different functions are unrelated. The same is true of the parameters of the function, which are in effect local variables.
The scope of an external variable or a function lasts from the point at which it is declared to the end of the file being compiled.
On the other hand, if an external variable is to be referred to before it is defined, or if it is defined in a different source file from the one where it is being used, then an extern declaration is mandatory. For example:
in file1:
extern int sp;
extern double val[];
void push(double f) { ... }
double pop(void) { ... }
in file2:
int sp = 0;
double val[MAXVAL];
4.5 Header Files:
4.6 Static Variables:
Static storage is specified by prefixing the normal declaration with the word static. If the two routines and the two variables are compiled in one file, as in
static char buf[BUFSIZE]; /* buffer for ungetch */
static int bufp = 0; /* next free position in buf */
4.7 Register Variables:
A register declaration advises the compiler that the variable in question will be heavily used The idea is that register variables are to be placed in machine registers, which may result smaller and faster programs. But compilers are free to ignore the advice. The register declaration looks like
register int x;
register char c;
and so on. The register declaration can only be applied to automatic variables and to the formal parameters of a function. In this later case, it looks like
f(register unsigned m, register long n)
{
register int i;
...
}
4.8 Block Structure:
C is not a block-structured language in the sense of Pascal or similar languages, because functions may not be defined within other functions. On the other hand, variables can be defined in a block-structured fashion within a function. Declarations of variables (including initializations) may follow the left brace that introduces any compound statement, not just the one that begins a function. Variables declared in this way hide any identically named variables in outer blocks, and remain in existence until the matching right brace. For example, in
if (n > 0) {
int i; /* declare a new i */
for (i = 0; i < n; i++)
...
}
4.9 Initialization:
In the absence of explicit initialization, external and static variables are guaranteed to be initialized to zero; automatic and register variables have undefined (i.e., garbage) initial values.
For external and static variables, the initializer must be a constant expression; the initialization is done once, conceptionally before the program begins execution. For automatic and register variables, the initializer is not restricted to being a constant: it may be any expression involving previously defined values, even function calls.
4.10 Initialization:
C functions may be used recursively; that is, a function may call itself either directly or indirectly. Consider printing a number as a character string. As we mentioned before, the digits are generated in the wrong order: low-order digits are available before high-order digits, but they have to be printed the other way around.
#include
/* printd: print n in decimal */
void printd(int n)
{
if (n < 0) {
putchar('-');
n = -n;
}
if (n / 10)
printd(n / 10);
putchar(n % 10 + '0');
}
Another good example of recursion is quicksort, a sorting algorithm developed by C.A.R Hoare in 1962. Given an array, one element is chosen and the others partitioned in two subsets - those less than the partition element and those greater than or equal to it. The same process is then applied recursively to the two subsets. When a subset has fewer than two elements, it doesn't need any sorting; this stops the recursion.
Our version of quicksort is not the fastest possible, but it's one of the simplest. We use the middle element of each subarray for partitioning.
/* qsort: sort v[left]...v[right] into increasing order */
void qsort(int v[], int left, int right)
{
int i, last;
void swap(int v[], int i, int j);
if (left >= right) /* do nothing if array contains */
return; /* fewer than two elements */
swap(v, left, (left + right)/2); /* move partition elem */
last = left; /* to v[0] */
for (i = left + 1; i <= right; i++) /* partition */
if (v[i] < v[left])
swap(v, ++last, i);
swap(v, left, last); /* restore partition elem
qsort(v, left, last-1);
qsort(v, last+1, right);
}
We moved the swapping operation into a separate function swap because it occurs three times in qsort.
/* swap: interchange v[i] and v[j] */
void swap(int v[], int i, int j)
{
int temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
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.
Exercise 4-13. Write a recursive version of the function reverse(s), which reverses the string s in place.
4.11 The C Preprocessor:
4.11.1 File Inclusion
File inclusion makes it easy to handle collections of #defines and declarations (among othe things). Any source line of the form
#include "filename"
or
#include
is replaced by the contents of the file filename. If the filename is quoted, searching for the fil typically begins where the source program was found; if it is not found there, or if the name I enclosed in < and >, searching follows an implementation defined rule to find the file. A included file may itself contain #include lines.
4.11.2 Macro Substitution
A definition has the form
#define name replacement text
It calls for a macro substitution of the simplest kind - subsequent occurrences of the token name will be replaced by the replacement text. The name in a #define has the same form as a variable name; the replacement text is arbitrary. Normally the replacement text is the rest of the line, but a long definition may be continued onto several lines by placing a \ at the end of each line to be continued. The scope of a name defined with #define is from its point of definition to the end of the source file being compiled. A definition may use previous definitions.
Substitutions are made only for tokens, and do not take place within quoted strings. For example, if YES is a defined name, there would be no substitution in printf("YES") or in YESMAN.
4.11.3 Conditional Inclusion
For example, to make sure that the contents of a file hdr.h are included only once, the contents of the file are surrounded with a conditional like this:
#if !defined(HDR)
#define HDR
/* contents of hdr.h go here */
#endif
/**
wordlength() :computes word length of the machine.
**/
int wordlength()
{
int i;
unsigned v=(unsigned)~0;
for(i=1;(v=v>>1)>0;i++)
;
return i;
}
