link splay(link h, Item item)  { Key v = key(item);    if (h == z) return NEW(item, z, z, 1);      if (less(v, key(h->item)))       {         if (hl == z) return NEW(item, z, h, h->N+1);        if (less(v, key(hl->item)))           { hll = splay(hll, item); h = rotR(h); }        else           { hlr = splay(hlr, item); hl = rotL(hl); }        return rotR(h);       }    else      {         if (hr == z) return NEW(item, h, z, h->N+1);        if (less(key(hr->item), v))           { hrr = splay(hrr, item); h = rotL(h); }        else           { hrl = splay(hrl, item); hr = rotR(hr); }        return rotL(h);      }  }void STinsert(Item item)  { head = splay(head, item); }-----link RBinsert(link h, Item item, int sw)  { Key v = key(item);    if (h == z) return NEW(item, z, z, 1, 1);      if ((hl->red) && (hr->red))       { h->red = 1; hl->red = 0; hr->red = 0; }    if (less(v, key(h->item)))       {         hl = RBinsert(hl, item, 0);         if (h->red && hl->red && sw) h = rotR(h);         if (hl->red && hll->red)           { h = rotR(h); h->red = 0; hr->red = 1; }      }    else      {         hr = RBinsert(hr, item, 1);         if (h->red && hr->red && !sw) h = rotL(h);         if (hr->red && hrr->red)           { h = rotL(h); h->red = 0; hl->red = 1; }      }    fixN(h); return h;  }void STinsert(Item item)  { head = RBinsert(head, item, 0); head->red = 0; }-----Item searchR(link t, Key v, int k)  {     if (eq(v, key(t->item))) return t->item;    if (less(v, key(t->next[k]->item)))       {         if (k == 0) return NULLitem;        return searchR(t, v, k-1);       }    return searchR(t->next[k], v, k);  }Item STsearch(Key v)  { return searchR(head, v, lgN); }-----typedef struct STnode* link;struct STnode { Item item; link* next; int sz; };static link head, z;static int N, lgN;link NEW(Item item, int k)        { int i; link x = malloc(sizeof *x);    x->next = malloc(k*sizeof(link));    x->item = item; x->sz = k;    for (i = 0; i < k; i++) x->next[i] = z;    return x;                           }                                   void STinit(int max)   {     N = 0; lgN = 0;     z = NEW(NULLitem, 0);     head = NEW(NULLitem, lgNmax);   }-----int randX()  { int i, j, t = rand();    for (i = 1, j = 2; i < lgNmax; i++, j += j)      if (t > RAND_MAX/j) break;    if (i > lgN) lgN = i;    return i;  }void insertR(link t, link x, int k)  { Key v = key(x->item);     if (less(v, key(t->next[k]->item)))       {         if (k < x->sz)          { x->next[k] = t->next[k];             t->next[k] = x; }        if (k == 0) return;        insertR(t, x, k-1); return;      }    insertR(t->next[k], x, k);  }void STinsert(Key v)  { insertR(head, NEW(v, randX()), lgN); N++; }-----void deleteR(link t, Key v, int k)  { link x = t->next[k];    if (!less(key(x->item), v))       {         if (eq(v, key(x->item)))          { t->next[k] = x->next[k]; }        if (k == 0) { free(x); return; }        deleteR(t, v, k-1); return;      }    deleteR(t->next[k], v, k);  }void STdelete(Key v)  { deleteR(head, v, lgN); N--; }----------CHAPTER 14. Hashing-----int hash(char *v, int M)  { int h = 0, a = 127;    for (; *v != '\0'; v++)       h = (a*h + *v) % M;    return h;  }-----int hashU(char *v, int M)  { int h, a = 31415, b = 27183;    for (h = 0; *v != '\0'; v++, a = a*b % (M-1))         h = (a*h + *v) % M;    return h;  }-----static link *heads, z;static int N, M;void STinit(int max)   { int i;    N = 0; M = max/5;    heads = malloc(M*sizeof(link));    z = NEW(NULLitem, NULL);    for (i = 0; i < M; i++) heads[i] = z;   }Item STsearch(Key v)  { return searchR(heads[hash(v, M)], v); }void STinsert(Item item)  { int i = hash(key(item), M);    heads[i] = NEW(item, heads[i]); N++; }void STdelete(Item item)  { int i = hash(key(item), M);    heads[i] = deleteR(heads[i], item); }-----#include <stdlib.h>#include "Item.h"#define null(A) (key(st[A]) == key(NULLitem))static int N, M;static Item *st;void STinit(int max)  { int i;     N = 0; M = 2*max;    st = malloc(M*sizeof(Item));    for (i = 0; i < M; i++) st[i] = NULLitem;   }int STcount() { return N; }void STinsert(Item item)  { Key v = key(item);    int i = hash(v, M);    while (!null(i)) i = (i+1) % M;    st[i] = item; N++;  }Item STsearch(Key v)  { int i = hash(v, M);    while (!null(i))      if eq(v, key(st[i])) return st[i];       else i = (i+1) % M;    return NULLitem;  }-----void STdelete(Item item)  { int j, i = hash(key(item), M); Item v;    while (!null(i))      if eq(key(item), key(st[i])) break;       else i = (i+1) % M;    if (null(i)) return;    st[i] = NULLitem; N--;    for (j = i+1; !null(j); j = (j+1) % M, N--)      { v = st[j]; st[j] = NULLitem; STinsert(v); }  }-----void STinsert(Item item)  { Key v = key(item);    int i = hash(v, M);    int k = hashtwo(v, M);    while (!null(i)) i = (i+k) % M;    st[i] = item; N++;  }Item STsearch(Key v)  { int i = hash(v, M);    int k = hashtwo(v, M);    while (!null(i))      if eq(v, key(st[i])) return st[i];       else i = (i+k) % M;    return NULLitem;  }-----void expand();void STinsert(Item item)  { Key v = key(item);    int i = hash(v, M);    while (!null(i)) i = (i+1) % M;    st[i] = item;     if (N++ > M/2) expand();  }void expand()  { int i; Item *t = st;    init(M+M);    for (i = 0; i < M/2; i++)       if (key(t[i]) != key(NULLitem))         STinsert(t[i]);     free(t);  }----------CHAPTER 15. Radix Search-----Item searchR(link h, Key v, int w)  { Key t = key(h->item);    if (h == z) return NULLitem;    if eq(v, t) return h->item;    if (digit(v, w) == 0)         return searchR(h->l, v, w+1);    else return searchR(h->r, v, w+1);  }Item STsearch(Key v)   { return searchR(head, v, 0); } -----#define leaf(A) ((h->l == z) && (h->r == z))Item searchR(link h, Key v, int w)  { Key t = key(h->item);    if (h == z) return NULLitem;    if (leaf(h))      return eq(v, t) ? h->item : NULLitem;    if (digit(v, w) == 0)         return searchR(h->l, v, w+1);    else return searchR(h->r, v, w+1);  }Item STsearch(Key v)   { return searchR(head, v, 0); } -----void STinit()  { head = (z = NEW(NULLitem, 0, 0, 0)); }link split(link p, link q, int w)  { link t = NEW(NULLitem, z, z, 2);    switch(digit(p->item, w)*2 + digit(q->item, w))      {        case 0: t->l = split(p, q, w+1); break;        case 1: t->l = p; t->r = q; break;        case 2: t->r = p; t->l = q; break;        case 3: t->r = split(p, q, w+1); break;      }    return t;  }link insertR(link h, Item item, int w)  { Key v = key(item), t = key(h->item);    if (h == z) return NEW(item, z, z, 1);    if (leaf(h))      { return split(NEW(item, z, z, 1), h, w); }    if (digit(v, w) == 0)         h->l = insertR(h->l, item, w+1);    else h->r = insertR(h->r, item, w+1);    return h;  }void STinsert(Item item)  { head = insertR(head, item, 0); }-----Item searchR(link h, Key v, int w)  {     if (h->bit <= w) return h->item;    if (digit(v, h->bit) == 0)         return searchR(h->l, v, h->bit);    else return searchR(h->r, v, h->bit);  }Item STsearch(Key v)   { Item t = searchR(head->l, v, -1);     return eq(v, key(t)) ? t : NULLitem;   } -----void STinit()  { head = NEW(NULLitem, 0, 0, -1);     head->l = head; head->r = head; }link insertR(link h, Item item, int w, link p)  { link x; Key v = key(item);    if ((h->bit >= w) || (h->bit <= p->bit))      {         x = NEW(item, 0, 0, w);        x->l = digit(v, x->bit) ? h : x;        x->r = digit(v, x->bit) ? x : h;        return x;       }    if (digit(v, h->bit) == 0)         h->l = insertR(h->l, item, w, h);    else h->r = insertR(h->r, item, w, h);    return h;  }void STinsert(Item item)  { int i;    Key v = key(item);     Key t = key(searchR(head->l, v, -1));    if (v == t) return;    for (i = 0; digit(v, i) == digit(t, i); i++) ;    head->l = insertR(head->l, item, i, head);  }-----void sortR(link h, void (*visit)(Item), int w)  {     if (h->bit <= w) { visit(h->item); return; }    sortR(h->l, visit, h->bit);    sortR(h->r, visit, h->bit);  }void STsort(void (*visit)(Item))  { sortR(head->l, visit, -1); } -----typedef struct STnode *link;struct STnode { link next[R]; };static link head;void STinit() { head = NULL; }link NEW()  { int i;    link x = malloc(sizeof *x);     for (i = 0; i < R; i++) x->next[i] = NULL;    return x;  }Item searchR(link h, Key v, int w)  { int i = digit(v, w);    if (h == NULL) return NULLitem;    if (i == NULLdigit) return v;    return searchR(h->next[i], v, w+1);  }Item STsearch(Key v)   { return searchR(head, v, 0); } link insertR(link h, Item item, int w)  { Key v = key(item);    int i = digit(v, w);    if (h == NULL) h = NEW();    if (i == NULLdigit) return h;    h->next[i] = insertR(h->next[i], v, w+1);    return h;  }void STinsert(Item item)  { head = insertR(head, item, 0); N++; }-----typedef struct STnode* link;struct STnode { Item item; int d; link l, m, r; };static link head;void STinit() { head = NULL; }link NEW(int d)  { link x = malloc(sizeof *x);     x->d = d; x->l = NULL; x->m = NULL; x->r = NULL;    return x;  }Item searchR(link h, Key v, int w)  { int i = digit(v, w);    if (h == NULL) return NULLitem;     if (i == NULLdigit) return v;    if (i < h->d) return searchR(h->l, v, w);    if (i == h->d) return searchR(h->m, v, w+1);    if (i > h->d) return searchR(h->r, v, w);  }Item STsearch( Key v)  { return searchR(head, v, 0); }link insertR(link h, Item item, int w)  { Key v = key(item);    int i = digit(v, w);    if (h == NULL) h = NEW(i);     if (i == NULLdigit) return h;    if (i < h->d) h->l = insertR(h->l, v, w);    if (i == h->d) h->m = insertR(h->m, v, w+1);    if (i > h->d) h->r = insertR(h->r, v, w);    return h;  }void STinsert(Key key)  { head = insertR(head, key, 0); }-----char word[maxW];void matchR(link h, char *v, int i)  {     if (h == z) return;     if ((*v == '\0') && (h->d == '\0'))       { word[i] = h->d; printf("%s ", word); }    if ((*v == '*') || (*v == h->d))       { word[i] = h->d; matchR(h->m, v+1, i+1); }    if ((*v == '*') || (*v < h->d))       matchR(h->l, v, i);    if ((*v == '*') || (*v > h->d))       matchR(h->r, v, i);  }void STmatch(char *v)  { matchR(head, v, 0); }-----#define internal(A) ((A->d) != NULLdigit)link NEWx(link h, int d)  { link x = malloc(sizeof *x);     x->item = NULLitem; x->d = d;    x->l = NULL; x->m = h; x->r = NULL;    return x;  }link split(link p, link q, int w)  { int pd = digit(p->item, w),         qd = digit(q->item, w);    link t = NEW(NULLitem, qd);    if (pd < qd) { t->m = q; t->l = NEWx(p, pd); }    if (pd == qd) { t->m = split(p, q, w+1); }    if (pd > qd) { t->m = q; t->r = NEWx(p, pd); }    return t;  }link insertR(link h, Item item, int w)  { Key v = key(item);    int i = digit(v, w);    if (h == NULL)       return NEWx(NEW(item, NULLdigit), i);    if (!internal(h))      return split(NEW(item, NULLdigit), h, w);     if (i < h->d) h->l = insertR(h->l, v, w);    if (i == h->d) h->m = insertR(h->m, v, w+1);    if (i > h->d) h->r = insertR(h->r, v, w);    return h;  }void STinsert(Key key)  { int i = digit(key, 0);    heads[i] = insertR(heads[i], key, 1);   }-----Item searchR(link h, Key v, int w)  { int i = digit(v, w);    if (h == NULL) return NULLitem;     if (internal(h))      {        if (i < h->d) return searchR(h->l, v, w);        if (i == h->d) return searchR(h->m, v, w+1);        if (i > h->d) return searchR(h->r, v, w);      }    if eq(v, key(h->item)) return h->item;    return NULLitem;  }Item STsearch(Key v)  { return searchR(heads[digit(v, 0)], v, 1); }-----typedef struct STnode* link;struct STnode { Item item; link l, m, r; };static link head;#define z NULLvoid STinit() { head = z; }link NEW(char *v)  { link x = malloc(sizeof *x);     x->item = v; x->l = z; x->m = z; x->r = z;    return x;  }Item searchR(link h, char *v)  { char *t;    if (h == z) return NULLitem;     if (*v == '\0') return h->item;    if (*v < *(h->item)) searchR(h->l, v);    if (*v > *(h->item)) searchR(h->r, v);    if (*v == *(h->item)) t = searchR(h->m, v+1);    return null(t) ? t : v;  }Item STsearch(char *v)  { char *t = searchR(head, v);     if (eq(v, t)) return t;    return NULLitem;  }link insertR(link h, char *v)  {     if (h == z) h = NEW(v);     if ((*v ==  *(h->item)) && (*v != '\0'))      h->m = insertR(h->m, v+1);    if (h == z) h = NEW(v);     if (*v < *(h->item)) h->l = insertR(h->l, v);    if (*v > *(h->item)) h->r = insertR(h->r, v);    return h;  }void STinsert(char *v)  { head = insertR(head, v); }----------CHAPTER 16. External Searching-----typedef struct STnode* link;typedef struct  { Key key; union { link next; Item item; } ref; } entry;struct STnode { entry b[M]; int m; };static link head;static int H, N; link NEW()  { link x = malloc(sizeof *x);     x->m = 0;    return x;   }void STinit(int maxN)   { head = NEW(); H = 0; N = 0; }-----Item searchR(link h, Key v, int H)  { int j;    if (H == 0)      for (j = 0; j < h->m; j++)        if (eq(v, h->b[j].key))           return h->b[j].ref.item;    if (H != 0)      for (j = 0; j < h->m; j++)        if ((j+1 == h->m) || less(v, h->b[j+1].key))          return searchR(h->b[j].ref.next, v, H-1);    return NULLitem;  }Item STsearch(Key v)  { return searchR(head, v, H); }-----link insertR(link h, Item item, int H)  { int i, j; Key v = key(item); entry x; link u;    x.key = v; x.ref.item = item;    if (H == 0)      for (j = 0