hello world!
分类： C/C++
2011-07-16 21:39:26
The main change in ANSI C is to make explicit the rules about how pointers can be manipulated, in effect mandating what good programmers already practice and good compilers already enforce. In addition, the type void * (pointer to void) replaces char * as the proper type for a generic pointer.
5.1 Pointers and Address:
Let us begin with a simplified picture of how memory is organized. A typical machine has an array of consecutively numbered or addressed memory cells that may be manipulated individually or in contiguous groups. One common situation is that any byte can be a char, a pair of one-byte cells can be treated as a short integer, and four adjacent bytes form a long. A pointer is a group of cells (often two or four) that can hold an address. So if c is a char and p is a pointer that points to it, we could represent the situation this way:
The unary operator & gives the address of an object, so the statement
p = &c;
assigns the address of c to the variable p, and p is said to ``point to'' c. The & operator only applies to objects in memory: variables and array elements. It cannot be applied to expressions, constants, or register variables.
The unary operator * is the indirection or dereferencing operator; when applied to a pointer, it accesses the object the pointer points to.
You should also note the implication that a pointer is constrained to point to a particular kind of object: every pointer points to a specific data type. (There is one exception: a ``pointer to void'' is used to hold any type of pointer but cannot be dereferenced itself. We'll come back to it in Section 5.11.)
5.2 Pointers and Function Arguments:
Since C passes arguments to functions by value, there is no direct way for the called function to alter a variable in the calling function.
Exercise 5-1. As written, getint treats a + or - not followed by a digit as a valid
representation of zero. Fix it to push such a character back on the input.
/**
getint() :get next integer from input into *pn.
**/
int getint(int *pn)
{
int c,sign;
while(isspace(c=getch())) /*skip white space*/
;
if(!isdigit(c)&&c!=EOF&&c!='+'&&c!='-'){
ungetch(c);
return -1;
}
sign= (c=='-') ? -1:1;
//(c=='-') ? putchar('-'):putchar('+');
if(c=='+'||c=='-'){
c=getch();
//putchar(c);
if(!isdigit(c)){
ungetch(c);
return -1;
}
}
for(*pn=0;isdigit(c);c=getch()){
*pn=10*(*pn)+(c-'0');
//putchar(c);
}
*pn *= sign;
if(c!=EOF)
ungetch(c);
return 0;
}
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.
/**
getfloat() :get next floa from input into *pn.
**/
int getfloat(double *pn)
{
int c,sign,pot=1;
while(isspace(c=getch())) /*skip white space*/
;
if(!isdigit(c)&&c!=EOF&&c!='+'&&c!='-'){
ungetch(c);
return -1;
}
sign= (c=='-') ? -1:1;
if(c=='+'||c=='-'){
c=getch();
if(!isdigit(c)){
ungetch(c);
return -1;
}
}
for(*pn=0;isdigit(c);c=getch())
*pn=10*(*pn)+(c-'0');
if(c=='.'){
c=getch();
for(pot=1;isdigit(c);c=getch()){
*pn=10*(*pn)+(c-'0');
pot=pot*10;
}
}
*pn *= sign;
*pn = *pn/pot;
if(c!=EOF)
ungetch(c);
return 0;
}
5.3 Pointers and Arrays:
The declaration
int a[10];
defines an array of size 10, that is, a block of 10 consecutive objects named a[0], a[1],...,a[9].
The notation a[i] refers to the i-th element of the array. If pa is a pointer to an integer, declared as
int *pa;
then the assignment
pa = &a[0];
sets pa to point to element zero of a; that is, pa contains the address of a[0].
5.4 Address Arithmetic:
The easiest implementation is to have alloc hand out pieces of a large character array that we will call allocbuf. This array is private to alloc and afree. Since they deal in pointers, not array indices, no other routine need know the name of the array, which can be declared static in the source file containing alloc and afree, and thus be invisible outside it. In practical implementations, the array may well not even have a name; it might instead be obtained by calling malloc or by asking the operating system for a pointer to some unnamed block of storage.
The other information needed is how much of allocbuf has been used. We use a pointer, called allocp, that points to the next free element. When alloc is asked for n characters, it checks to see if there is enough room left in allocbuf. If so, alloc returns the current value of allocp (i.e., the beginning of the free block), then increments it by n to point to the next free area. If there is no room, alloc returns zero. afree(p) merely sets allocp to p if p is inside allocbuf.
/**
alloc() :return pointer to n characters.
afree() :free storage pointed to by p.
**/
#define ALLOCSIZE 100000 //size of available space
static char allocbuf[ALLOCSIZE]; //storge for alloc
static char *allocp = allocbuf; //next free position
char *alloc(int n)
{
if(allocbuf + ALLOCSIZE - allocp >= n){ //it fits
allocp += n;
return allocp-n;
}else
return 0;
}
void afree(char *p)
{
if(p >= allocbuf && p < allocbuf + ALLOCSIZE)
allocp=p;
}
5.5 Characters Pointers and Functions:
A string constant, written as
"I am a string"
is an array of characters. In the internal representation, the array is terminated with the null character '\0' so that programs can find the end. The length in storage is thus one more than the number of characters between the double quotes.
There is an important difference between these definitions:
char amessage[] = "now is the time"; /* an array */
char *pmessage = "now is the time"; /* a pointer */
amessage is an array, just big enough to hold the sequence of characters and '\0' that initializes it. Individual characters within the array may be changed but amessage will always refer to the same storage. On the other hand, pmessage is a pointer, initialized to point to a string constant; the pointer may subsequently be modified to point elsewhere, but the result is undefined if you try to modify the string contents.
We will illustrate more aspects of pointers and arrays by studying versions of two useful functions adapted from the standard library. The first function is strcpy(s,t), which copies the string t to the string s. It would be nice just to say s=t but this copies the pointer, not the characters. To copy the characters, we need a loop. The array version first:
/**
strcpy1() : copy t to s ; array subscript version.
strcpy2() : copy t to s ; pointer version.
strcpy3() : copy t to s ; pointer version 2.
strcpy4() : copy t to s ; pointer version 3.
**/
void strcpy1(char *s, char *t)
{
int i;
i=0;
while((s[i]=t[i])!='\0')
i++;
}
void strcpy2(char *s, char *t)
{
int i;
i=0;
while((*s=*t)!='\0'){
s++;
t++;
}
}
void strcpy3(char *s, char *t)
{
while((*s++=*t++)!='\0')
;
}
void strcpy4(char *s, char *t)
{
while(*s++=*t++)
;
}
/**
strcpy5(s,t,n) :
**/
void strcpy5(char *s, char *t,int n)
{
while(*t&&(n-->0))
*s++=*t++;
while(n-->0)
*s++='\0';
}
Exercise 5-3. Write a pointer version of the function strcat that we showed in Chapter 2: strcat(s,t) copies the string t to the end of s.
/**
strcat1() : the buttom of string s inpus t,my version.
strcat2() : system version.
**/
void strcat1(char *s,char *t)
{
while(*s!='\0')
s++;
for(;*s=*t;s++,t++)
if(*t=='\0')
return ;
}
void strcat2(char *s,char *t)
{
while(*s)
s++;
while(*s++=*t++)
;
}
Exercise 5-4. Write the function strend(s,t), which returns 1 if the string t occurs at the end of the string s, and zero otherwise.
/**
strend() : return 1 if string t occure at the end of s.
**/
int strend(char *s,char *t)
{
char *bs=s;
char *bt=t;
for(;*s;s++)
;
for(;*t;t++)
;
for(;*s==*t;s--,t--)
if(t==bt||s==bs)
break;
if(*s==*t && t == bt && *s!='\0')
return 1;
else
return 0;
}
Exercise 5-5. Write versions of the library functions strncpy, strncat, and strncmp, which operate on at most the first n characters of their argument strings. For example, strncpy(s,t,n) copies at most n characters of t to s. Full descriptions are in Appendix B.
5.6 Pointer Arrays Pointers to Pointers:
Since pointers are variables themselves, they can be stored in arrays just as other variables c Let us illustrate by writing a program that will sort a set of text lines into alphabetic order stripped-down version of the UNIX program sort.
Exercise 5-7. Rewrite readlines to store lines in an array supplied by main, rather than calling alloc to maintain storage. How much faster is the program?
/**
getline(s,lim) : get a line form input.
s : the string of input.
lim : the maximum of a line length.
returns : chars of the string.
**/
int getline(char s[],int lim) //得到一行
{
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;
}
/**
readlines() : read input lines.
writelines() : write output lines.
**/
#define MAXLEN 1000 //max length of any input line.
#define MAXSTOR 5000 //size of available storage space.
// old version, use allocbuf store the lines.
int readlines(char *lineptr[],int maxlines)
{
int len,nlines;
char *p,line[MAXLEN];
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;
}
5.7 Multi-dimensional Arrays:
f(int daytab[2][13]) { ... }
It could also be
f(int daytab[][13]) { ... }
since the number of rows is irrelevant, or it could be
f(int (*daytab)[13]) { ... }
which says that the parameter is a pointer to an array of 13 integers. The parentheses are necessary since brackets [] have higher precedence than *. Without parentheses, the declaration
int *daytab[13]
is an array of 13 pointers to integers. More generally, only the first dimension (subscript) of an array is free; all the others have to be specified.
Exercise 5-8. There is no error checking in day_of_year or month_day. Remedy this defect.
/**
leap_year() : return 1 is leap.
**/
int leap_year(int year)
{
return ((year%4==0 && year%100!=0) || year%400==0);
}
/**
day_of_year() : set day of year from month & day.
return :-1 year fault,-2 month fault,-3 day fault.
month_day() : set month,day from day of year.
**/
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}
};
int day_of_year(int year,int month,int day)
{
int i,leap;
leap=leap_year(year);
if(1<=month<=12)
if(1<=day<=daytab[leap][month]){
for(i=1;i
day+=daytab[leap][i];
return day;
}else{
printf("error:day input fault!\n");
return -3;
}
else{
printf("month:day input fault!\n");
return -2;
}
}
void month_day(int year, int yearday,int *pmonth,int *pday)
{
int i,leap;
leap=((year%4==0 && year%100!=0) || year%400==0);
if(yearday>(365+leap)||yearday<1){
printf("error:yearday input fault!\n");
return ;
}
for(i=1;yearday>daytab[leap][i];i++)
yearday -= daytab[leap][i];
*pmonth = i;
*pday = yearday;
}
5.8 Initialization of Pointer Arrays:
The syntax is similar to previous initializations:
/* month_name: return name of n-th month */
char *month_name(int n)
{
static char *name[] = {
"Illegal month",
"January", "February", "March",
"April", "May", "June",
"July", "August", "September",
"October", "November", "December"
};
return (n < 1 || n > 12) ? name[0] : name[n];
}
The declaration of name, which is an array of character pointers, is the same as lineptr in the sorting example. The initializer is a list of character strings; each is assigned to the corresponding position in the array. The characters of the i-th string are placed somewhere, and a pointer to them is stored in name[i]. Since the size of the array name is not specified, the compiler counts the initializers and fills in the correct number.
5.9 Pointers vs. Multi-dimensional Arrays:
char *name[] = { "Illegal month", "Jan", "Feb", "Mar" };
with those for a two-dimensional array:
char aname[][15] = { "Illegal month", "Jan", "Feb", "Mar" };
5.10 Command-line Arguments:
In environments that support C, there is a way to pass command-line arguments or parameters to a program when it begins executing. When main is called, it is called with two arguments. The first (conventionally called argc, for argument count) is the number of command-line arguments the program was invoked with; the second (argv, for argument vector) is a pointer to an array of character strings that contain the arguments, one per string. We customarily use multiple levels of pointers to manipulate these character strings.
Exercise 5-10. Write the program expr, which evaluates a reverse Polish expression from the command line, where each operator or operand is a separate argument. For example,
expr 2 3 4 + *
evaluates 2 * (3+4).
#include
#include
#include
/**
atof(s,t) : convert string s to double,but it can't deal with scientific notation.
s : the string.
returns : double.
**/
double atof(char s[])
{
double val,power;
int i,sign;
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;
}
return sign*val/power;
}
/**
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
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]);
}
/**
getop() : get a (possibly pushed-back) character,can't handle negative number.
return : if 1 ,then it is a number. -1:then not a number.
**/
int getop_unnegative(char s[])
{
int i,c;
while( (s[0]=c=getch()) ==' ' || c=='\t')
NULL;
s[1]='\0';
if(!isdigit(c)&&c!='.'){
printf("debug:\"--%c--\"not a number.\n",c);
return c;} //not a number
i=0;
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';
if(c!=EOF)
ungetch(c);
return 1; //a number
}
/**
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;
}
}
/**
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);
}
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);
}
#define MAX_OP 100 //max size of operand or opertor
#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 string %s!!!\n",s[0],s);
printf("\n");
/*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.(1)\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 main(int argc,char *argv[])
{
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((--argc)>=0){
if(argc==0){
type='\n';
printf("type :%d end!\n",type);
}else{
ungets(" ");
ungets(*++argv);
printf("\n");
printf("debug:argv %s length %d\n",*argv,strlen(*argv));
type=getop(s);
printf("type :%d string:%s!\n",type,s);
}
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 '-':
printf("-!\n");
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;
}
}
Exercise 5-11. Modify the program entab and detab (written as exercises in Chapter 1) to accept a list of tab stops as arguments. Use the default tab settings if there are no arguments.
Exercise 5-12. Extend entab and detab to accept the shorthand
entab -m +n
to mean tab stops every n columns, starting at column m. Choose convenient (for the user) default behavior.
Exercise 5-13. Write the program tail, which prints the last n lines of its input. By default, n is set to 10, let us say, but it can be changed by an optional argument so that
tail -n
prints the last n lines. The program should behave rationally no matter how unreasonable the input or the value of n. Write the program so it makes the best use of available storage; lines should be stored as in the sorting program of Section 5.6, not in a two-dimensional array of fixed size.
#include
#include
#include
/**
getline(s,lim) : get a line form input.
s : the string of input.
lim : the maximum of a line length.
returns : chars of the string.
**/
int getline(char s[],int lim) //得到一行
{
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;
}
#define DEFLINS 3 //default # of lines to printf
#define LINES 100 //max # of lines to pinrt
#define MAXLEN 100 //max length of an input line
int main(int argc, char *argv[])
{
char *p;
char *buf; //pointer fo large buffer
char *bufend; //end of the buffer
char line[MAXLEN]; //current input line
char *lineptr[LINES]; //pointers to lines read
int first,i,last,len,n,nlines;
if(argc==1)
n=DEFLINS; //use default # of present
else if(argc==2&&((*++argv)[0]=='-'))
n=atoi(++argv[0]);
else {
printf("usage:tail [-n]");
return -1;
}
if(n<1||n>LINES)
n=LINES;
for(i=0;i
lineptr[i]=NULL;
if((p=buf=malloc(LINES*MAXLEN))==NULL){
printf("tail:cannot allocate buf");
return -1;
}
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; //begin line of the printf.
if(first<0)
first+=LINES;
for(i=first;n-->0;i=(i+1)%LINES) //i+1 ++line
printf("%s",lineptr[i]);
return 0;
}
5.11 Pointers to Functions:
In C, a function itself is not a variable, but it is possible to define pointers to functions, which can be assigned, placed in arrays, passed to functions, returned by functions, and so on.
The declarations should be studied with some care. The fourth parameter of qsort is
int (*comp)(void *, void *)
which says that comp is a pointer to a function that has two void * arguments and return int.
The use of comp in the line
if ((*comp)(v[i], v[left]) < 0)
is consistent with the declaration: comp is a pointer to a function, *comp is the function, and
(*comp)(v[i], v[left])
is the call to it. The parentheses are needed so the components are correctly associated; without them,
int *comp(void *, void *) /* WRONG */
says that comp is a function returning a pointer to an int, which is very different.
Exercise 5-14. Modify the sort program to handle a -r flag, which indicates sorting in reverse (decreasing) order. Be sure that -r works with -n.
Exercise 5-15. Add the option -f to fold upper and lower case together, so that case distinctions are not made during sorting; for example, a and A compare equal.
Exercise 5-16. Add the -d (``directory order'') option, which makes comparisons only on letters, numbers and blanks. Make sure it works in conjunction with -f.
Exercise 5-17. Add a field-searching capability, so sorting may bee done on fields within lines, each field sorted according to an independent set of options. (The index for this book was sorted with -df for the index category and -n for the page numbers.)
/* all answers integrate in a file of C*/
#include
#include
#define MAXLINES 500 //max #lines to be sorted
char *lineptr[MAXLINES];
void qsort(char *v[],int left,int right,int (*comp)(void *,void *));
int numcmp(char *s1,char *s2);
int strcmp(char *s,char *t);
int charcmp(char *s,char *t);
void interswap(char *v[],int i,int j);
double atof(char s[]);
int readlines(char *lineptr[],int maxlines);
void writelines(char *lineptr[],int nlines,int decr);
int getline(char s[],int lim);
char *alloc(int n);
void afree(char *p);
static char option=0; //main flag
/**
main() : sort input lines
**/
int main(int argc, char *argv[])
{
int nlines; //number of input lines read
int numeric=1; //1 if numberic sort
int dec=2; //1 if sort decrease
int lettercase=4; //1 if sort do not differntiate letters case
int c,rc=0;
while(--argc>0 && (*++argv)[0]=='-'){
while(c = *++argv[0]){
switch (c){
case 'n':
printf("bebug:Option %c\n",c);
option|=numeric;
break;
case 'r':
printf("bebug:Option %c\n",c);
option|=dec;
break;
case 'f':
printf("bebug:Option %c\n",c);
option|=lettercase;
break;
default:
printf("find:Illegal option %c\n",c);
argc=1;
rc=-1;
break;
}
}
}
if(argc)
printf("Usage:sort -fnr \n");
else{
if((nlines=readlines(lineptr,MAXLINES))>0){
if(option&numeric)
qsort((void**) lineptr,0,nlines-1,(int (*)(void*,void*))numcmp);
else if(option&lettercase)
qsort((void**) lineptr,0,nlines-1,(int (*)(void*,void*))charcmp);
else
qsort((void**) lineptr,0,nlines-1,(int (*)(void*,void*))strcmp);
writelines(lineptr,nlines,option&dec);
}else{
printf("error:input too big to sort\n");
rc=-1;
}
}
return rc;
}
/**
qsort() : sort v[left]....v[right] into increaseing order
**/
void qsort(char *v[],int left,int right,int (*comp)(void *,void *))
{
int i,last;
//void swap(void *v[],int ,int );
if(left>=right)
return;
interswap(v,left,(left+right)/2);
last=left;
for(i=left+1;i<=right;i++)
if((*comp)(v[i],v[left])<0)
interswap(v,++last,i);
interswap(v,left,last);
qsort(v,left,last-1,comp);
qsort(v,last+1,right,comp);
}
/**
interswap() : interchange v[i] and v[j].
**/
void interswap(char *v[],int i,int j)
{
char *temp;
temp =v[i];
v[i]=v[j];
v[j]=temp;
}
/**
numcmp() : compare s1 and s2 numerically
**/
int numcmp(char *s1,char *s2)
{
double v1,v2;
v1=atof(s1);
v2=atof(s2);
if(v1
return -1;
else if(v1>v2)
return 1;
else
return 0;
}
/**
atof(s,t) : convert string s to double,but it can't deal with scientific notation.
s : the string.
returns : double.
**/
double atof(char s[])
{
double val,power;
int i,sign;
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;
}
return sign*val/power;
}
/**
strcmp1() : compare string s and t,array subscript version.
strcmp2() : pointer version.
return : <0 if s
**/
int strcmp(char *s,char *t)
{
for(;*s==*t;s++,t++)
if(*s=='\0')
return 0;
return *s-*t;
}
/**
charcmp() : compare s1 and s2 case
**/
int charcmp(char *s,char *t)
{
for(;tolower(*s)==tolower(*t);s++,t++)
if(*s=='\0')
if(*t=='\0')
return 0;
else
return tolower(*s)-tolower(*t);
return tolower(*s)-tolower(*t);
}
#define MAXLEN 1000 //max length of any input line.
#define MAXSTOR 5000 //size of available storage space.
char *lineptr[MAXLINES]; //pointers to text lines.
// old version, use allocbuf store the lines.
int readlines(char *lineptr[],int maxlines)
{
int len,nlines;
char *p,line[MAXLEN];
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,int decr)
{
int i;
if(decr){
for(i=nlines-1;i>=0;i--)
printf("result:%s!\n",lineptr[i]);
}else{
for(i=0;i
printf("result:%s!\n",lineptr[i]);
}
}
/**
getline(s,lim) : get a line form input.
s : the string of input.
lim : the maximum of a line length.
returns : chars of the string.
**/
int getline(char s[],int lim) //得到一行
{
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;
}
/**
alloc() :return pointer to n characters.
afree() :free storage pointed to by p.
**/
#define ALLOCSIZE 100000 //size of available space
static char allocbuf[ALLOCSIZE]; //storge for alloc
static char *allocp = allocbuf; //next free position
char *alloc(int n)
{
if(allocbuf + ALLOCSIZE - allocp >= n){ //it fits
allocp += n;
return allocp-n;
}else
return 0;
}
void afree(char *p)
{
if(p >= allocbuf && p < allocbuf + ALLOCSIZE)
allocp=p;
}
