hello world!
分类： C/C++
2011-07-18 07:49:03
1. Basics of Structures:
A structure is a collection of one or more variables, possibly of different types, grouped together under a single name for convenient handling. (Structures are called “records” in some languages, notably Pascal.) Structures help to organize complicated data, particularly in large programs, because they permit a group of related variables to be treated as a unit instead of as separate entities.
The main change made by the ANSI standard is to define structure assignment- structures may be copied and assigned to, passed to functions, and returned by functions. This has been supported by most compilers for many years, but the properties are now precisely defined. Automatic structures and arrays may now also be initialized.
2. A simple aplication of Structures:
struct point {
int x;
int y;
}
A member of a particular structure is referred to in an expression by a construction of the form
structure-name.member
The structure member operator“.”connects the structure name and the member name. To print the coordinates of the point pt, for instance,
printf("%d,%d", pt.x, pt.y);
Pointers to structures are so frequently used that an alternative notation is provided as a shorthand. If p is a pointer to a structure, then
p->member-of-structure
3. Structures and Functions:
The only legal operations on a structure are copying it or assigning to it as a unit, taking its address with &, and accessing its members. Copy and assignment include passing arguments to functions and returning values from functions as well. Structures may not be compared. A structure may be initialized by a list of constant member values; an automatic structure may also be initialized by an assignment.
Let us investigate structures by writing some functions to manipulate points and rectangles.There are at least three possible approaches: pass components separately, pass an entire structure, or pass a pointer to it. Each has its good points and bad points.
The first function, makepoint, will take two integers and return a point structure:
/* makepoint: make a point from x and y components */
struct point makepoint(int x, int y)
{
struct point temp;
temp.x = x;
temp.y = y;
return temp;
}
Notice that there is no conflict between the argument name and the member with the same name; indeed the re-use of the names stresses the relationship.
Exercise 6-1: Our version of getword does not properly handle underscores, string constants,comments, or preprocessor control lines. Write a better version.
/**
getch() : get a (possibly pushed-back) character.
ungetch() : push character back on input.
ungets() : push string back on input.
**/
#define GETCH_BUFFSIZE 1000 // 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;
}
}
/***
comment():skip over comment and return a character
***/
int comment(void)
{
int c;
while((c=getch())!=EOF)
if(c=='*')
if((c=getch())=='/')
break;
else
ungetch(c);
return c;
}
/***
getword():get next word or character from input
***/
int getword(char *word,int lim)
{
int c,d;
char *w=word;
while(isspace(c=getch())) /* skip the spaces */
;
if(c!=EOF) /* judge the file end or not */
*w++=c;
if(isalpha(c)||c=='_'||c=='#'){ /* handle the ‘_’and ‘# */
for(;--lim>0;w++)
if(!isalnum(*w=getch())){ /* judge letters and number */
ungetch(*w);
break;
}
}else if(c=='\''|| c== '"' ){ /* handle comments */
for(;--lim>0;w++)
if((*w=getch())=='\\')
*++w=getch();
else if(*w==c){
w++;
break;
}else if(*w==EOF)
break;
}else if (c=='/'){
if((d=getch())=='*')
c=comment();
else
ungetch(d);
}
*w='\0';
return c;
}
Examper 6-4: Statistics keywords. (point version)
#include
#include
#include
#define NKEYS (sizeof keytab/sizeof(struct key))
struct key{
char *word;
int count;
} keytab[]={
"auto",0,
"break", 0,
"case", 0,
"char", 0,
"const", 0,
"continue", 0,
"default", 0,
/* ... */
"unsigned", 0,
"void", 0,
"volatile", 0,
"while", 0
};
/**
getch() : get a (possibly pushed-back) character.
ungetch() : push character back on input.
ungets() : push string back on input.
**/
#define GETCH_BUFFSIZE 1000 // 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;
}
}
/***
comment():skip over comment and return a character
***/
int comment(void)
{
int c;
while((c=getch())!=EOF)
if(c=='*')
if((c=getch())=='/')
break;
else
ungetch(c);
return c;
}
/***
getword():get next word or character from input
***/
int getword(char *word,int lim)
{
int c,d;
char *w=word;
while(isspace(c=getch()))
;
if(c!=EOF)
*w++=c;
if(isalpha(c)||c=='_'||c=='#'){
for(;--lim>0;w++)
if(!isalnum(*w=getch())){
ungetch(*w);
break;
}
}else if(c=='\''|| c== '"' ){
for(;--lim>0;w++)
if((*w=getch())=='\\')
*++w=getch();
else if(*w==c){
w++;
break;
}else if(*w==EOF)
break;
}else if (c=='/'){
if((d=getch())=='*')
c=comment();
else
ungetch(d);
}
*w='\0';
return c;
}
/***
binsearch():find word int tab[0]...tab[n-1]
***/
struct key *binsearch(char *word,struct key tab[],int n)
{
int cond;
struct key *low=&tab[0];
struct key *high=&tab[n];
struct key *mid;
while(low
mid=low+(high-low)/2; //两个指针间的加法运算是非法的
if((cond=strcmp(word,mid->word))<0)
high=mid;
else if(cond>0)
low=mid+1;
else
return mid;
}
return NULL;
}
/***
count C keywords
***/
int main(int argc,char *argv[])
{
struct key *p;
char word[100];
while(getword(word,100)!=EOF){
printf("debug:%s\n",word);
if(isalpha(word[0])){
if((p=binsearch(word,keytab,NKEYS))!=NULL){
p->count++;
printf("debug:keytab %s!\n",p->word);
}
}
}
for(p=keytab;p
if(p->count>0)
printf("%4d %s\n",p->count,p->word);
return 0;
printf("debug:NKEYS %d\n",(int)NKEYS);
}
Example 6-5. Binary tree test.
#include
#include
#include
#include
#define MAXWORD 100
struct tnode { //the tree node
char *word; //points to the text
int count; //number of occurences
struct tnode *left; //left child
struct tnode *right; //right child
};
/**
getch() : get a (possibly pushed-back) character.
ungetch() : push character back on input.
ungets() : push string back on input.
**/
#define GETCH_BUFFSIZE 1000 // 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;
}
}
/***
getword():get next word or character from input
***/
int getword(char *word,int lim)
{
int c;
char *w=word;
while(isspace(c=getch()))
;
if(c!=EOF)
*w++=c;
if(!isalpha(c)){
*w='\0';
printf("debug:getword %c\n",c);
return c;
}
for(;--lim>0;w++)
if(!isalnum(*w=getch())){
ungetch(*w);
break;
}
*w='\0';
return word[0];
}
struct tnode *talloc(void)
{
return (struct tnode *) malloc(sizeof(struct tnode));
}
char *strdup_my(char *s)
{
char *p;
p=(char *)malloc(strlen(s)+1);
if(p!=NULL)
strcpy(p,s);
return p;
}
/***
addtree():add a node with w, at or below p
***/
struct tnode *addtree(struct tnode *p,char *w)
{
int cond;
if(p==NULL){
p=talloc();
p->word=strdup_my(w);
p->count=1;
p->left=p->right=NULL;
} else if ((cond=strcmp(w,p->word))==0)
p->count++;
else if (cond<0)
p->left=addtree(p->left,w);
else
p->right=addtree(p->right,w);
return p;
}
/***
treeprint():in-order print of tree p
***/
void treeprint(struct tnode *p)
{
if(p!=NULL){
treeprint(p->left);
printf("%4d %s\n",p->count,p->word);
treeprint(p->right);
}
}
/***
word frequency count
***/
int main()
{
struct tnode *root;
char word[MAXWORD];
root=NULL;
while(getword(word,MAXWORD)!=EOF)
if(isalpha(word[0]))
root=addtree(root,word);
treeprint(root);
return 0;
}
Exercise 6-3. Write a cross-referencer that prints a list of all words in a document, and for each word, a list of the line numbers on which it occurs. Remove noise words like ``the,'' ``and,'' and so on.
…
Exercise 6-4. Write a program that prints the distinct words in its input sorted into decreasing order of frequency of occurrence. Precede each word by its count.
#include
#include
#define MAXWORD 100
#define NDISTINCT 1000
struct tnode { /* the tree node */
char *word; /* points to the text */
int count; /* number of occurences */
struct tnode *left; /* left child */
struct tnode *right; /* right child */
};
struct tnode *list[NDISTINCT]; /* pointres to tree nodes */
int ntn=0; /* number of tree nodes */
struct tnode *addTree(struct tnode *,char *);
int getWord(char *,int);
void sortList(void);
void treeStore(struct tnode *);
/***
main: print distinct words sorted in decreasing order of freq
***/
int main(int argc, char *argv[])
{
struct tnode *root;
char word[MAXWORD];
int i;
root=NULL;
while(getWord(word,MAXWORD)!=EOF){
if(isalpha(word[0]))
root=addTree(root,word);
}
treeStore(root);
sortList();
for(i=0;i
printf("%2d:%20s\n",list[i]->count,list[i]->word);
return 0;
}
/***
treeStore: store in list[] pointers to tree nodes
***/
void treeStore(struct tnode *p)
{
if(p!=NULL){
treeStore(p->left);
if(ntn
list[ntn++]=p;
treeStore(p->right);
}
}
/***
sortList: sort list of points to tree nodes
***/
void sortList()
{
int gap,i,j;
struct tnode *temp;
for(gap=ntn/2;gap>0;gap/=2)
for(i=gap;i
for(j=i-gap;j>=0;j-=gap){
if((list[j]->count)>=(list[j+gap]->count))
break;
temp=list[j];
list[j]=list[j+gap];
list[j+gap]=temp;
}
}
struct tnode *talloc(void)
{
return (struct tnode *) malloc(sizeof(struct tnode));
}
char *strDup_my(char *s)
{
char *p;
p=(char *)malloc(strlen(s)+1);
if(p!=NULL)
strcpy(p,s);
return p;
}
/***
addTree():add a node with w, at or below p
***/
struct tnode *addTree(struct tnode *p,char *w)
{
int cond;
if(p==NULL){
p=talloc();
p->word=strDup_my(w);
p->count=1;
p->left=p->right=NULL;
} else if ((cond=strcmp(w,p->word))==0)
p->count++;
else if (cond<0)
p->left=addTree(p->left,w);
else
p->right=addTree(p->right,w);
return p;
}
/**
getch() : get a (possibly pushed-back) character.
ungetch() : push character back on input.
ungets() : push string back on input.
**/
#define GETCH_BUFFSIZE 1000 // 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;
}
}
/***
comment():skip over comment and return a character
***/
int comment(void)
{
int c;
while((c=getch())!=EOF)
if(c=='*')
if((c=getch())=='/')
break;
else
ungetch(c);
return c;
}
/***
getWord():get next word or character from input
***/
int getWord(char *word,int lim)
{
int c,d;
char *w=word;
while(isspace(c=getch()))
;
if(c!=EOF)
*w++=c;
if(isalpha(c)||c=='_'||c=='#'){
for(;--lim>0;w++)
if(!isalnum(*w=getch())){
ungetch(*w);
break;
}
}else if(c=='\''|| c== '"' ){
for(;--lim>0;w++)
if((*w=getch())=='\\')
*++w=getch();
else if(*w==c){
w++;
break;
}else if(*w==EOF)
break;
}else if (c=='/'){
if((d=getch())=='*')
c=comment();
else
ungetch(d);
}
*w='\0';
return c;
}
Exercise 6-5. Write a function undef that will remove a name and definition from the table maintained by lookup and install.
#include
struct nlist { /* table entry : */
struct nlist *next; /* next entry in chain */
char *name; /* defined name */
char *defn; /* replacement text */
};
#define HASHSIZE 101
static struct nlist *hashtab[HASHSIZE]; /* pointer table */
/***
hash: form hash value for string s
***/
unsigned hash(char *s)
{
unsigned hashval; /*"unsigned" define a negative number */
for (hashval=0;*s!='\0';s++)
hashval=*s+31*hashval;
return hashval % HASHSIZE;
}
/***
lookup: look for s in hashtab
***/
struct nlist *lookup(char *s)
{
struct nlist *np;
for(np=hashtab[hash(s)];np!=NULL;np=np->next)
if(strcmp(s,np->name)==0)
return np; /* found */
return NULL; /* not found */
}
/***
strDup_my:allocate the room for the string s
***/
char *strDup_my(char *s)
{
char *p;
p=(char *)malloc(strlen(s)+1);
if(p!=NULL)
strcpy(p,s);
return p;
}
/***
install: put (name,defn) in hashtab
***/
struct nlist *install(char *name,char *defn)
{
struct nlist *np;
unsigned hashval;
if((np=lookup(name))==NULL){ /* not found */
np=(struct nlist *)malloc(sizeof(*np)); /* storage allocation */
if(np==NULL || (np->name=strDup_my(name))==NULL)
return NULL;
hashval=hash(name); /* hash value of sting */
np->next=hashtab[hashval]; /* link next to a node */
hashtab[hashval]=np; /* add node to table */
}else /* allready there */
free((void *)np->defn);
if((np->defn=strDup_my(defn))==NULL)
return NULL;
return np;
}
/***
undef: delete (name,defn) in hashtab
***/
int undef(char *s)
{
int h;
struct nlist *np,*prev;
prev=NULL;
h=hash(s); /* hash value of string s */
for(np=hashtab[h];np!=NULL;np->next){
if(strcmp(s,np->name)==0)
break;
prev=np; /* remember previous entry */
}
if(np!=NULL){ /* found name */
if(prev==NULL) /* first in the hash lise */
hashtab[h]=np->next;
else
prev->next=np->next;
free((void *)np->name);
free((void *)np->defn);
free((void *)np); /* free allocated structure */
}
}
/**
getch() : get a (possibly pushed-back) character.
ungetch() : push character back on input.
ungets() : push string back on input.
**/
#define GETCH_BUFFSIZE 1000 // 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;
}
}
/***
comment():skip over comment and return a character
***/
int comment(void)
{
int c;
while((c=getch())!=EOF)
if(c=='*')
if((c=getch())=='/')
break;
else
ungetch(c);
return c;
}
/***
getWord():get next word or character from input
***/
int getWord(char *word,int lim)
{
int c,d;
char *w=word;
while(isspace(c=getch())&&c!='\n')
;
if(c!=EOF)
*w++=c;
if(isalpha(c)||c=='_'||c=='#'){
for(;--lim>0;w++)
if(!isalnum(*w=getch())){
ungetch(*w);
break;
}
}else if(c=='\''|| c== '"' ){
for(;--lim>0;w++)
if((*w=getch())=='\\')
*++w=getch();
else if(*w==c){
w++;
break;
}else if(*w==EOF)
break;
}else if (c=='/'){
if((d=getch())=='*')
c=comment();
else
ungetch(d);
}
*w='\0';
return c;
}
int main(int argc, char *argv[])
{
return 0;
}
Exercise 6-6. Implement a simple version of the #define processor (i.e., no arguments) suitable for use with C programs, based on the routines of this section. You may also find getch and ungetch helpful.
#include
#include
#include
struct nlist { /* table entry : */
struct nlist *next; /* next entry in chain */
char *name; /* defined name */
char *defn; /* replacement text */
};
#define MAXWORD 100
#define HASHSIZE 101
static struct nlist *hashtab[HASHSIZE]; /* pointer table */
/***
hash: form hash value for string s
***/
unsigned hash(char *s)
{
unsigned hashval; /*"unsigned" define a negative number */
for (hashval=0;*s!='\0';s++)
hashval=*s+31*hashval;
return hashval % HASHSIZE;
}
/***
lookup: look for s in hashtab
***/
struct nlist *lookup(char *s)
{
struct nlist *np;
for(np=hashtab[hash(s)];np!=NULL;np=np->next)
if(strcmp(s,np->name)==0)
return np; /* found */
return NULL; /* not found */
}
/***
strDup_my:allocate the room for the string s
***/
char *strDup_my(char *s)
{
char *p;
p=(char *)malloc(strlen(s)+1);
if(p!=NULL)
strcpy(p,s);
return p;
}
/***
install: put (name,defn) in hashtab
***/
struct nlist *install(char *name,char *defn)
{
struct nlist *np;
unsigned hashval;
if((np=lookup(name))==NULL){ /* not found */
np=(struct nlist *)malloc(sizeof(*np)); /* storage allocation */
if(np==NULL || (np->name=strDup_my(name))==NULL)
return NULL;
hashval=hash(name); /* hash value of sting */
np->next=hashtab[hashval]; /* link next to a node */
hashtab[hashval]=np; /* add node to table */
//printf("debug:intall definitaion %s with %s",name,defn);
}else /* allready there */
free((void *)np->defn);
if((np->defn=strDup_my(defn))==NULL)
return NULL;
return np;
}
/***
undef: delete (name,defn) in hashtab
***/
int undef(char *s)
{
int h;
struct nlist *np,*prev;
prev=NULL;
h=hash(s); /* hash value of string s */
for(np=hashtab[h];np!=NULL;np->next){
if(strcmp(s,np->name)==0)
break;
prev=np; /* remember previous entry */
}
if(np!=NULL){ /* found name */
if(prev==NULL) /* first in the hash lise */
hashtab[h]=np->next;
else
prev->next=np->next;
free((void *)np->name);
free((void *)np->defn);
free((void *)np); /* free allocated structure */
}
}
/**
getch() : get a (possibly pushed-back) character.
ungetch() : push character back on input.
ungets() : push string back on input.
**/
#define GETCH_BUFFSIZE 1000 // 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;
}
}
int ungets(char s[])
{
int len=strlen(s);
while(len>0)
ungetch(s[--len]);
}
/***
comment():skip over comment and return a character
***/
int comment(void)
{
int c;
while((c=getch())!=EOF)
if(c=='*')
if((c=getch())=='/')
break;
else
ungetch(c);
return c;
}
/***
getWord():get next word or character from input
***/
int getWord(char *word,int lim)
{
int c,d;
char *w=word;
while(isspace(c=getch())&&c!=' ') //return blanks
;
if(c!=EOF)
*w++=c;
if(isalpha(c)||c=='_'){
for(;--lim>0;w++)
if(!isalnum(*w=getch())){
ungetch(*w);
break;
}
}else if(c=='\''|| c== '"' ){
for(;--lim>0;w++)
if((*w=getch())=='\\')
*++w=getch();
else if(*w==c){
w++;
break;
}else if(*w==EOF)
break;
}else if (c=='/'){
if((d=getch())=='*')
c=comment();
else
ungetch(d);
}
*w='\0';
return c;
}
/***
error: print error message and skip the rest of the line
***/
void error(int c,char *s)
{
printf("error:%s\n",s);
while(c!=EOF&&c!='\n')
c=getch();
}
/***
skipblanks: skip blank and tab characters
***/
void skipblanks(void)
{
int c;
while((c=getch())==' '||c=='\t')
;
ungetch(c);
}
/***
getdef: get definition and install it
***/
void getdef(void)
{
int c,i;
char def[MAXWORD],dir[MAXWORD],name[MAXWORD];
skipblanks();
if(!isalpha(getWord(dir,MAXWORD)))
error(dir[0],"getdef:expecting a directive after #");
else if(strcmp(dir,"define")==0){
skipblanks();
if(!isalpha(getWord(name,MAXWORD)))
error(name[0],"getdef:non alpha name expected");
else{
skipblanks();
for(i=0;i
if((def[i]=getch())==EOF || def[i]=='\n')
break; /* end of definition */
def[i]='\0';
//printf("debug:def %s",def);
if(i<=0)
error('\n',"getdef:incomlete define");
else
install(name,def);
}
}else if(strcmp(dir,"undef")==0){
skipblanks();
if(!isalpha(getWord(name,MAXWORD)))
error(name[0],"getdef: non-alpha in undef");
else
undef(name);
}else
error(dir[0],"getdef: expecting a directive after #");
}
/***
main: simple version of #define processor
***/
int main(int argc, char *argv[])
{
char w[MAXWORD];
struct nlist *p;
while(getWord(w,MAXWORD)!=EOF){
if(strcmp(w,"#")==0) /* beginning of direct */
getdef();
else if(!isalpha(w[0]))
printf("error: %s \n",w); /* cannot be defined */
else if((p=lookup(w))==NULL)
printf("error: %s \n",w); /* not defined*/
else
ungets(p->defn); /* push definition */
}
return 0;
}
4. Typedef:
C provides a facility called typedef for creating new data type names. In effect, typedef is like #define, except that since it is interpreted by the compiler, it can cope with textual substitutions that are beyond the capabilities of thepreprocessor. For example:
typedef int (*PFI)(char *, char *);
Besides purely aesthetic issues, there are two main reasons for using typedefs. The first is to parameterize a program against portability problems. If typedefs are used for data types that may be machine-dependent, only the typedefs need change when the program is moved. One common situation is to use typedef names for various integer quantities, then make an appropriate set of choices of short, int, and long for each host machine. Types like size_t and ptrdiff_t from the standard library are examples.
The second purpose of typedefs is to provide better documentation for a program - a type called Treeptr may be easier to understand than one declared only as a pointer to a complicated structure.
5. Uinons:
A union is a variable that may hold (at different times) objects of different types and sizes, with the compiler keeping track of size and alignment requirements. Unions provide a way to manipulate different kinds of data in a single area of storage, without embedding any machine-dependent information in the program. They are analogous to variant records in pascal. For example: the syntax is based on structures:
union u_tag {
int ival;
float fval;
char *sval;
} u;
Syntactically, members of a union are accessed as
union-name.member
or
union-pointer->member
A union may only be initialized with a value of the type of its first member; thus union u described above can only be initialized with an integer value.
