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;

            }

        }

    }

}










