本文共 24440 字，大约阅读时间需要 81 分钟。
/** * a better version of getword * written by swy **/#include#include #include #define MAXWORD 114#define NKEYS (sizeof keytab /sizeof keytab[0])struct key { char *word; int count;} keytab[] = { "auto", 0, "break", 0, "case", 0, "char", 0, "continue", 0, /*...*/ "unsigned", 0, "void", 0, "volatile", 0, "while", 0};#define BUFFSIZE 114char buf[BUFFSIZE]; // buffer for ungetchint bufp = 0; // next free posotion in bufint getch(void){ return (bufp > 0) ? buf[--bufp] : getchar();}void ungetch(int c){ if (bufp >= BUFFSIZE) printf("ungetch: too many characters\n"); else buf[bufp++] = c;}int acceptable(char c){ return ((c == '_') || (c == '"') || (c == '#') || (c == '/') || isalnum(c));}int getword(char *word, int lim){ int c, getch(void); void ungetch(int); char *w = word; while (isspace(c = getch())) ; if (c != EOF) *w++ = c; if (!acceptable(c)){ *w = '\0'; return c; } for ( ; --lim > 0; w++) if (!acceptable(*w = getch())){ ungetch(*w); break; } *w = '\0'; return word[0];}int binsearch(char *word, struct key tab[], int n){ int cond; int low, high, mid; low = 0; high = n - 1; while (low <= high){ mid = (low + high) / 2; if ((cond = strcmp(word, tab[mid].word)) < 0) high = mid - 1; else if (cond > 0) low = mid + 1; else return mid; } return -1;}int main(void){ int n; char word[MAXWORD]; while(getword(word, MAXWORD) != EOF) if (isalpha(word[0])) if ((n = binsearch(word, keytab, NKEYS)) >= 0) keytab[n].count++; for (n = 0; n < NKEYS; n++) if (keytab[n].count > 0) printf("%4d %s\n", keytab[n].count, keytab[n].word); return 0;}
#include#define XMAX 114#define YMAX 114#define min(a,b) ((a)<(b)?(a):(b))#define max(a,b) ((a)>(b)?(a):(b))struct point{ int x; int y;};struct rect{ struct point pt1; struct point pt2;};struct point makepoint(int x,int y){ struct point temp; temp.x = x; temp.y = y; return temp;}struct point addpoint(struct point p1,struct point p2){ p1.x += p2.x; p1.y += p2.y; return p1;}int ptinrect(struct point p,struct rect r){ return p.x >= r.pt1.x && p.x < r.pt2.x && p.y >= r.pt1.y && p.y < r.pt2.y;}struct rect canonrect(struct rect r){ struct rect temp; temp.pt1.x = min(r.pt1.x, r.pt2.x); temp.pt1.y = min(r.pt1.y, r.pt2.y); temp.pt2.x = max(r.pt1.x, r.pt2.x); temp.pt2.y = max(r.pt1.y, r.pt2.y); return temp;}int main(){ struct rect screen; struct point middle; struct point origin; struct point *pp; screen.pt1 = makepoint(0, 0); screen.pt2 = makepoint(XMAX, YMAX); middle = makepoint((screen.pt1.x + screen.pt2.x)/2, (screen.pt1.y + screen.pt2.y)/2); origin = screen.pt1; pp = &origin; printf("origin is (%d,%d)\n", (*pp).x, (*pp).y); printf("origin is (%d,%d)\n", pp->x, pp->y); return 0;}
/*这是要我写轮子么*//*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.*/#include#include #include #include /* no such thing as strdup, so let's write one * * supplementary question: why did I call this function dupstr, * rather than strdup? * */char *dupstr(char *s){ char *p = NULL; if(s != NULL){ p = malloc(strlen(s) + 1); if(p){ strcpy(p, s); } } return p;}/* case-insensitive string comparison */int i_strcmp(const char *s, const char *t){ int diff = 0; char cs = 0; char ct = 0; while(diff == 0 && *s != '\0' && *t != '\0'){ cs = tolower((unsigned char)*s); ct = tolower((unsigned char)*t); if(cs < ct){ diff = -1; } else if(cs > ct){ diff = 1; } ++s; ++t; } if(diff == 0 && *s != *t){ /* the shorter string comes lexicographically sooner */ if(*s == '\0'){ diff = -1; } else{ diff = 1; } } return diff;}struct linelist{ struct linelist *next; int line;};struct wordtree{ char *word; struct linelist *firstline; struct wordtree *left; struct wordtree *right;};void printlist(struct linelist *list){ if(list != NULL){ printlist(list->next); printf("%6d ", list->line); }}void printtree(struct wordtree *node){ if(node != NULL){ printtree(node->left); printf("%18s ", node->word); printlist(node->firstline); printf("\n"); printtree(node->right); }}struct linelist *addlink(int line){ struct linelist *new = malloc(sizeof *new); if(new != NULL){ new->line = line; new->next = NULL; } return new;}void deletelist(struct linelist *listnode){ if(listnode != NULL){ deletelist(listnode->next); free(listnode); }}void deleteword(struct wordtree **node){ struct wordtree *temp = NULL; if(node != NULL){ if(*node != '\0'){ if((*node)->right != NULL){ temp = *node; deleteword(&temp->right); } if((*node)->left != NULL){ temp = *node; deleteword(&temp->left); } if((*node)->word != NULL){ free((*node)->word); } if((*node)->firstline != NULL){ deletelist((*node)->firstline); } free(*node); *node = NULL; } }}struct wordtree *addword(struct wordtree **node, char *word, int line){ struct wordtree *wordloc = NULL; struct linelist *newline = NULL; struct wordtree *temp = NULL; int diff = 0; if(node != NULL && word != NULL){ if(NULL == *node) { *node = malloc(sizeof **node); if(NULL != *node){ (*node)->left = NULL; (*node)->right = NULL; (*node)->word = dupstr(word); if((*node)->word != NULL){ (*node)->firstline = addlink(line); if((*node)->firstline != NULL){ wordloc = *node; } } } } else{ diff = i_strcmp((*node)->word, word); if(0 == diff){ /* we have seen this word before! add this line number to * the front of the line number list. Adding to the end * would keep them in the right order, but would take * longer. By continually adding them to the front, we * take less time, but we pay for it at the end by having * to go to the end of the list and working backwards. * Recursion makes this less painful than it might have been. */ newline = addlink(line); if(newline != NULL){ wordloc = *node; newline->next = (*node)->firstline; (*node)->firstline = newline; } } else if(0 < diff){ temp = *node; wordloc = addword(&temp->left, word, line); } else{ temp = *node; wordloc = addword(&temp->right, word, line); } } } if(wordloc == NULL){ deleteword(node); } return wordloc;}/* We can't use strchr because it's not yet been discussed, so we'll * write our own instead. */char *char_in_string(char *s, int c){ char *p = NULL; /* if there's no data, we'll stop */ if(s != NULL){ if(c != '\0'){ while(*s != '\0' && *s != c){ ++s; } if(*s == c){ p = s; } } } return p;}/* We can't use strtok because it hasn't been discussed in the text * yet, so we'll write our own. * To minimise hassle at the user end, let's modify the user's pointer * to s, so that we can just call this thing in a simple loop. */char *tokenise(char **s, char *delims){ char *p = NULL; char *q = NULL; if(s != NULL && *s != '\0' && delims != NULL){ /* pass over leading delimiters */ while(NULL != char_in_string(delims, **s)){ ++*s; } if(**s != '\0'){ q = *s + 1; p = *s; while(*q != '\0' && NULL == char_in_string(delims, *q)){ ++q; } *s = q + (*q != '\0'); *q = '\0'; } } return p;}/* return zero if this word is not a noise word, * or non-zero if it is a noise word */int NoiseWord(char *s){ int found = 0; int giveup = 0; char *list[] = { "a", "an", "and", "be", "but", "by", "he", "I", "is", "it", "off", "on", "she", "so", "the", "they", "you" }; int top = sizeof list / sizeof list[0] - 1; int bottom = 0; int guess = top / 2; int diff = 0; if(s != NULL){ while(!found && !giveup){ diff = i_strcmp(list[guess], s); if(0 == diff){ found = 1; } else if(0 < diff){ top = guess - 1; } else{ bottom = guess + 1; } if(top < bottom){ giveup = 1; } else{ guess = (top + bottom) / 2; } } } return found;}/* * Argh! We can't use fgets()! It's not discussed until page 164. * Oh well... time to roll our own again... */char *GetLine(char *s, int n, FILE *fp){ int c = 0; int done = 0; char *p = s; while(!done && --n > 0 && (c = getc(fp)) != EOF){ if((*p++ = c) == '\n'){ done = 1; } } *p = '\0'; if(EOF == c && p == s){ p = NULL; } else{ p = s; } return p;}/* * Ideally, we'd use a clever GetLine function which expanded its * buffer dynamically to cope with large lines. Since we can't use * realloc, and because other solutions would require quite hefty * engineering, we'll adopt a simple solution - a big buffer. * * Note: making the buffer static will help matters on some * primitive systems which don't reserve much storage for * automatic variables, and shouldn't break anything anywhere. * */#define MAXLINE 8192int main(void){ static char buffer[MAXLINE] = { 0}; char *s = NULL; char *word = NULL; int line = 0; int giveup = 0; struct wordtree *tree = NULL; char *delims = " \t\n\r\a\f\v!\"%^&*()_=+{}[]\\|/,.<>:;#~?"; while(!giveup && GetLine(buffer, sizeof buffer, stdin) != NULL){ ++line; s = buffer; while(!giveup && (word = tokenise(&s, delims)) != NULL){ if(!NoiseWord(word)){ if(NULL == addword(&tree, word, line)){ printf("Error adding data into memory. Giving up.\n"); giveup = 1; } } } } if(!giveup){ printf("%18s Line Numbers\n", "Word"); printtree(tree); } deleteword(&tree); return 0;}
/*yet another wheel*//* 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 #include #include typedef struct WORD{ char *Word; size_t Count; struct WORD *Left; struct WORD *Right;} WORD;/* Assumptions: input is on stdin, output to stdout. Plan: read the words into a tree, keeping a count of how many we have, allocate an array big enough to hold Treecount (WORD *)'s walk the tree to populate the array. qsort the array, based on size. printf the array free the array free the tree free tibet (optional) free people in TaiWan, Japan & U.S.A!*/#define SUCCESS 0#define CANNOT_MALLOC_WORDARRAY 1#define NO_WORDS_ON_INPUT 2#define NO_MEMORY_FOR_WORDNODE 3#define NO_MEMORY_FOR_WORD 4#define NONALPHA "1234567890 \v\f\n\t\r+=-*/\\,.;:'#~?<>|{}[]`!\"�$%^&()"int ReadInputToTree(WORD **DestTree, size_t *Treecount, FILE *Input);int AddToTree(WORD **DestTree, size_t *Treecount, char *Word); int WalkTree(WORD **DestArray, WORD *Word);int CompareCounts(const void *vWord1, const void *vWord2);int OutputWords(FILE *Dest, size_t Count, WORD **WordArray);void FreeTree(WORD *W);char *dupstr(char *s);int main(){ int Status = SUCCESS; WORD *Words = NULL; size_t Treecount = 0; WORD **WordArray = NULL; /* Read the words on stdin into a tree */ if(SUCCESS == Status){ Status = ReadInputToTree(&Words, &Treecount, stdin); } /* Sanity check for no sensible input */ if(SUCCESS == Status){ if(0 == Treecount){ Status = NO_WORDS_ON_INPUT; } } /* allocate a sufficiently large array */ if(SUCCESS == Status){ WordArray = malloc(Treecount * sizeof *WordArray); if(NULL == WordArray){ Status = CANNOT_MALLOC_WORDARRAY; } } /* Walk the tree into the array */ if(SUCCESS == Status){ Status = WalkTree(WordArray, Words); } /* qsort the array */ if(SUCCESS == Status){ qsort(WordArray, Treecount, sizeof *WordArray, CompareCounts); } /* walk down the WordArray outputting the values */ if(SUCCESS == Status){ Status = OutputWords(stdout, Treecount, WordArray); } /* free the word array */ if(NULL != WordArray){ free(WordArray); WordArray = NULL; } /* and free the tree memory */ if(NULL != Words){ FreeTree(Words); Words = NULL; } /* Error report and we are finshed */ if(SUCCESS != Status){ fprintf(stderr, "Program failed with code %d\n", Status); } return (SUCCESS == Status ? EXIT_SUCCESS : EXIT_FAILURE);}void FreeTree(WORD *W){ if(NULL != W){ if(NULL != W->Word){ free(W->Word); W->Word = NULL; } if(NULL != W->Left){ FreeTree(W->Left); W->Left = NULL; } if(NULL != W->Right){ FreeTree(W->Right); W->Right = NULL; } }}int AddToTree(WORD **DestTree, size_t *Treecount, char *Word){ int Status = SUCCESS; int CompResult = 0; /* safety check */ assert(NULL != DestTree); assert(NULL != Treecount); assert(NULL != Word); /* ok, either *DestTree is NULL or it isn't (deep huh?) */ if(NULL == *DestTree) /* this is the place to add it then */{ *DestTree = malloc(sizeof **DestTree); if(NULL == *DestTree) { /* horrible - we're out of memory */ Status = NO_MEMORY_FOR_WORDNODE; } else{ (*DestTree)->Left = NULL; (*DestTree)->Right = NULL; (*DestTree)->Count = 1; (*DestTree)->Word = dupstr(Word); if(NULL == (*DestTree)->Word){ /* even more horrible - we've run out of memory in the middle */ Status = NO_MEMORY_FOR_WORD; free(*DestTree); *DestTree = NULL; } else{ /* everything was successful, add one to the tree nodes count */ ++*Treecount; } } } else /* we need to make a decision */{ CompResult = strcmp(Word, (*DestTree)->Word); if(0 < CompResult){ Status = AddToTree(&(*DestTree)->Left, Treecount, Word); } else if(0 > CompResult){ Status = AddToTree(&(*DestTree)->Left, Treecount, Word); } else{ /* add one to the count - this is the same node */ ++(*DestTree)->Count; } } /* end of else we need to make a decision */ return Status; }int ReadInputToTree(WORD **DestTree, size_t *Treecount, FILE *Input){ int Status = SUCCESS; char Buf[8192] = { 0}; char *Word = NULL; /* safety check */ assert(NULL != DestTree); assert(NULL != Treecount); assert(NULL != Input); /* for every line */ while(NULL != fgets(Buf, sizeof Buf, Input)){ /* strtok the input to get only alpha character words */ Word = strtok(Buf, NONALPHA); while(SUCCESS == Status && NULL != Word){ /* deal with this word by adding it to the tree */ Status = AddToTree(DestTree, Treecount, Word); /* next word */ if(SUCCESS == Status) { Word = strtok(NULL, NONALPHA); } } } return Status;}int WalkTree(WORD **DestArray, WORD *Word){ int Status = SUCCESS; static WORD **Write = NULL; /* safety check */ assert(NULL != Word); /* store the starting point if this is the first call */ if(NULL != DestArray){ Write = DestArray; } /* Now add this node and it's kids */ if(NULL != Word){ *Write = Word; ++Write; if(NULL != Word->Left){ Status = WalkTree(NULL, Word->Left); } if(NULL != Word->Right){ Status = WalkTree(NULL, Word->Right); } } return Status;}/* CompareCounts is called by qsort. This means that it gets pointers to the data items being compared. In this case the data items are pointers too. */int CompareCounts(const void *vWord1, const void *vWord2){ int Result = 0; WORD * const *Word1 = vWord1; WORD * const *Word2 = vWord2; assert(NULL != vWord1); assert(NULL != vWord2); /* ensure the result is either 1, 0 or -1 */ if((*Word1)->Count < (*Word2)->Count){ Result = 1; } else if((*Word1)->Count > (*Word2)->Count){ Result = -1; } else{ Result = 0; } return Result;}int OutputWords(FILE *Dest, size_t Count, WORD **WordArray){ int Status = SUCCESS; size_t Pos = 0; /* safety check */ assert(NULL != Dest); assert(NULL != WordArray); /* Print a header */ fprintf(Dest, "Total Words : %lu\n", (unsigned long)Count); /* Print the words in descending order */ while(SUCCESS == Status && Pos < Count) { fprintf(Dest, "%10lu %s\n", (unsigned long)WordArray[Pos]->Count, WordArray[Pos]->Word); ++Pos; } return Status;}/* dupstr: duplicate a string*/char *dupstr(char *s){ char *Result = NULL; size_t slen = 0; /* sanity check */ assert(NULL != s); /* get string length */ slen = strlen(s); /* allocate enough storage */ Result = malloc(slen + 1); /* populate string */ if(NULL != Result){ memcpy(Result, s, slen); *(Result + slen) = '\0'; } return Result;}
/*hashtab 这个轮子我就不重复写了*//*Write a function undef that will remove a name and defination from the tablemaintained by lookup and install.*/void undef(char* s){ struct nlist *np1, *np2; unsigned hashval = hash(s); for (np1 = hashtab[hashval], np2 = NULL; np1 != NULL; np2 = np1, np1 = np1->next) if (strcmp(s, np1->name) == 0) { /* found a match */ free(np1->name); free(np1->defn); if (np2 == NULL) /* at the beginning? */ hashtab[hashval] = np1->next; else /* in the middle or at the end? */ np2->next = np1->next; free(np1); return; }} /*yet another wheel, damn it!*/#include#include #include #include #define HASHSIZE 114#define MAXWORD 1919struct nlist{ struct nlist* next; char* name; char* defn;};static struct nlist *hashtab[HASHSIZE];struct nlist *lookup(char *);struct nlist *install(char *, char *);int process();int getch();void ungetch();int preproc();int backslash();int comment();int literal();int readword();int main(){ int c; const int done = 0; /* just a dummy for the infinite loop */ int status = 1; /* 1 at line begin, 2 for failure, 0 otherwise */ while(!done) { while(isspace(c = getch())) { putchar(c); if(c == '\n') status = 1; } if(c == '#' && status == 1) status = preproc(); else if(c == '\\') status = backslash(); else if(c == '/') status = comment(); else if(c == '\"') status = literal(); else if(c == EOF) return 0; else if(!isalpha(c) && c != '_') { putchar(c); status = 0; } else { ungetch(c); status = readword(); } if(status == 2) return 1; } return 0;} /* end main() *//* * preproc: Called when a '#' is found at the beginning of a line. * If a #define statement is found, it stores add the search and replacement * text to the hash table. Otherwise it just prints what it reads. * The line a #define statement is found on is replaced with a blank line. */int preproc(void){ int c; char name[MAXWORD+1], defn[MAXWORD+1]; char *n, *d; /* Read what comes after the '#' */ for(n = name; isalpha(c = getch()) && n - name < MAXWORD; ++n) *n = c; *n = '\0'; /* If it's a #define... */ if(strcmp(name, "define") == 0) { /* ignore whitespace */ while(isspace(c)) { if(c == '\n') { /* a #define followed by a '\n' is discarded */ putchar(c); return 1; } c = getch(); } /* Read search text */ for(n = name; (isalnum(c) || c == '_') && n - name < MAXWORD; ++n) { *n = c; c = getch(); } *n = '\0'; /* Ignore whitespace */ while(isspace(c)) { if(c == '\n') *defn = '\0'; /* If there is no replacement text. */ c = getch(); } /* Read replacement text. */ for(d = defn; (isalnum(c) || c == '_') && d - defn < MAXWORD; ++d) { *d = c; c = getch(); } *d = '\0'; /* Add to hash table. */ if(install(name, defn) == NULL) return 2; } else { /* not a #define statement */ putchar('#'); printf("%s", name); } /* finish line reading/printing line */ while(c != '\n') { if(c == EOF) return EOF; putchar(c); c = getch(); } putchar(c); return 1;} /* end preproc() *//* * backslash: Makes sure that if a /, *, or " is preceded by a \ it is * just printed, not used in a comment or string literal. */int backslash(void){ int c, slash = 1; putchar('\\'); while((c = getch()) == '\\') { slash = !slash; putchar(c); } if(slash) putchar(c); else ungetch(c); return 0;} /* end backslash() *//* * comment: Prints comments without changes. */int comment(void){ int c; int after_star = 0; putchar('/'); if((c = getch()) == '*') { /* comment begin */ putchar(c); c = getch(); while(c != EOF) { if(c == '\\') { backslash(); after_star = 0; } else if(c == '*') { after_star = 1; putchar(c); } else if(c == '/' && after_star) { putchar(c); return 0; } else { after_star = 0; putchar(c); } c = getch(); } if(c == EOF) return EOF; putchar(c); return 0; } else { ungetch(c); return 0; }} /* end comment() *//* * literal: Prints string literals without changes. */int literal(void){ int c; putchar('\"'); c = getch(); while(c != '\"' && c != EOF) { if(c == '\\') backslash(); else putchar(c); c = getch(); } if(c == EOF) return EOF; putchar(c); return 0;} /* end literal() *//* * readwood: Reads an identifier and looks for it in the hash table. If * it's found, it's replaced with the replacement text. Otherwise, it is * printed as is. */int readword(void){ int c; char word[MAXWORD]; char *w; struct nlist *node; c = getch(); for(w = word; (isalnum(c) || c == '_') && c != EOF; ++w) { *w = c; c = getch(); } *w = '\0'; node = lookup(word); if(node == NULL) printf("%s", word); else printf("%s", node->defn); if(c == EOF) return EOF; ungetch(c); return 0;} /* end readword() *//*************************************************************************** * From K&R2 * ***************************************************************************/unsigned hash(char *);char *strdup(char *);/* lookup: From K&R2 page 145. 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; return NULL;}/* install: From K&R2 page 145. Put (name, defn) in hashtab. */struct nlist *install(char *name, char *defn){ struct nlist *np; unsigned hashval; if((np = lookup(name)) == NULL) { np = (struct nlist *) malloc(sizeof(*np)); if(np == NULL || (np->name = strdup(name)) == NULL) return NULL; hashval = hash(name); np->next = hashtab[hashval]; hashtab[hashval] = np; } else free((void *) np->defn); if((np->defn = strdup(defn)) == NULL) return NULL; return np;}/* hash: From K&R2 page 144. Form hash value for string s. */unsigned hash(char *s){ unsigned hashval; for(hashval = 0; *s != '\0'; ++s) hashval = *s + 31 * hashval; return hashval % HASHSIZE;}/* strdup: From K&R2 page 143. Makes a duplicate of s. */char *strdup(char *s){ char *p; p = (char *) malloc(strlen(s) + 1); if(p != NULL) strcpy(p, s); return p;}#define BUFSIZE 114char buf[BUFSIZE]; /* buffer for ungetch() */int bufp = 0; /* next free position in buf */int getch(void) { /* get a (possibly pushed back) character */ return (bufp > 0) ? buf[--bufp] : getchar();}void ungetch(int c) { /* push character back on input */ if(bufp >= BUFSIZE) printf("ungetch: too many characters\n"); else buf[bufp++] = c; return;}
转载地址：http://wbwai.baihongyu.com/