Algorithm Alley by Jon Bentley Example 1: (a) int istrlen(char *s) { int n = 0; for ( ; *s; s++) n++; return n; } (b) int rstrlen(char *s) { if (*s) return 1+rstrlen(s+1); else return 0; } Example 2: (a) int istrcmp(char *s, char *t) { for ( ; *s == *t; s++, t++) if (*s == 0) return 0; return *s - *t; } (b) int rstrcmp(char *s, char *t) { if (*s == *t) { if (*s) return rstrcmp(s+1, t+1); else return 0; } else return (*s - *t); } (c) int rcstrcmp(char *s, char *t) { return (*s == *t) ? (*s ? rcstrcmp(s+1, t+1) : 0) : *s - *t; } Example 3: (a) typedef struct tnode *Tptr; typedef struct tnode { int val; Tptr lo, hi; } Tnode; (b) int rbstsearch(Tptr p, int t) { if (!p) return -1; if (t == p->val) return 1; if (t < p->val) return rbstsearch(p->lo, t); return rbstsearch(p->hi, t); } (c) int ibstsearch(int t) { Tptr p; for (p = root; p; ) { if (t == p->val) return 1; p = (t < p->val) ? p->lo : p->hi; } return -1; } (d) Tptr rinsert(Tptr p, int t) { if (p) { if (t < p->val) p->lo = rinsert(p->lo, t); else p->hi = rinsert(p->hi, t); } else { p = (Tptr) malloc(sizeof(Tnode)); p->lo = p->hi = 0; p->val = t; } return p; } Example 4: void iinsert(int t) { Tptr p, q; Tptr next = (Tptr) malloc(sizeof(Tnode)); if (!root) root = next; else { for (q = root; q; ) { p = q; q = (t < p->val) ? q->lo : q->hi; } if (t < p->val) p->lo = next; else p->hi = next; } next->lo = next->hi = 0; next->val = t; } Example 5: (a) void rcount(Tptr p) { if (!p) return; rcount(p->lo); count++; rcount(p->hi); } (b) void rcount2(Tptr p) { if (p->lo) rcount2(p->lo); count++; if (p->hi) rcount2(p->hi); } Example 6: (a) void rcount3(Tptr p) { while (p) { if (p->lo) rcount3(p->lo); count++; p = p->hi; } } (b) void icount(Tptr p) { Tptr s[MAXN]; int sp = 0; for (;;) { while (p) { s[sp++] = p; p = p->lo; } if (sp == 0) break; p = s[--sp]; count++; p = p->hi; } } Listing One void iinsertpp(int t) { Tptr *p = &root; while (*p) { if (t < (*p)->val) p = &((*p)->lo); else p = &((*p)->hi); } *p = (Tptr) malloc(sizeof(Tnode)); (*p)->lo = (*p)->hi = 0; (*p)->val = t; } Listing Two void pmsearch(Tptr p, char *s) { if (!p) return; nodecnt++; if (*s == '.' || *s < p->splitchar) pmsearch(p->lokid, s); if (*s == '.' || *s == p->splitchar) if (p->splitchar && *s) pmsearch(p->eqkid, s+1); if (*s == 0 && p->splitchar == 0) srcharr[srchtop++] = (char *) p->eqkid; if (*s == '.' || *s > p->splitchar) pmsearch(p->hikid, s); } Listing Three void pmsearch2(Tptr p, char *s) { while (p) { nodecnt++; if (*s == '.') { pmsearch2(p->lokid, s); pmsearch2(p->hikid, s); if (p->splitchar == 0) return; p = p->eqkid; ++s; } else { if (*s < p->splitchar) p = p->lokid; else if (*s > p->splitchar) p = p->hikid; else /* *s == p->splitchar */ { if (*s == 0) { if (p->splitchar == 0) srcharr[srchtop++] = (char *) p->eqkid; return; } p = p->eqkid; ++s; } } } }