algorithmsinc++,thirdedition,parts1-4,code.txt

Robert Sedgewick的不朽之作《Algorithms》

               insertR(h->l, x);
          else insertR(h->r, x);
        }
    public:
      ST(int maxN)
        { head = 0; }
      Item search(Key v) 
        { return searchR(head, v); } 
      void insert(Item x)
        { insertR(head, x); }
  };
-----
   private:
      void showR(link h, ostream& os)
        { 
          if (h == 0) return;
          showR(h->l, os);
          h->item.show(os); 
          showR(h->r, os);
        }
    public:
      void show(ostream& os)
        { showR(head, os); } 
-----
void insert(Item x)
  { Key v = x.key();
    if (head == 0) 
      { head = new node(x); return; }
    link p = head;
    for (link q = p; q != 0; p = q ? q : p)
      q = (v < q->item.key()) ? q->l : q->r; 
    if (v < p->item.key()) p->l = new node(x); 
                      else p->r = new node(x);
  }
-----
#include <iostream.h>
#include <fstream.h>
#include "Item.cxx"
#include "ST.cxx"
static char text[maxN];
int main(int argc, char *argv[])
  { int N = 0; char t;
    ifstream corpus; corpus.open(*++argv);
    while (N < maxN && corpus.get(t)) text[N++] = t; 
    text[N] = 0;
    ST<Item, Key> st(maxN);
    for (int i = 0; i < N; i++) st.insert(&text[i]);
    char query[maxQ]; Item x, v(query);
    while (cin.getline(query, maxQ))
      if ((x = st.search(v.key())).null())
           cout << "not found: " << query << endl;
      else cout <<  x-text << ": " << query << endl;
  }
-----
void rotR(link& h)
  { link x = h->l; h->l = x->r; x->r = h; h = x; }
void rotL(link& h)
  { link x = h->r; h->r = x->l; x->l = h; h = x; }
-----
private:
  void insertT(link& h, Item x)
    { if (h == 0) { h = new node(x); return; }
      if (x.key() <  h->item.key()) 
           { insertT(h->l, x); rotR(h); }
      else { insertT(h->r, x); rotL(h); }
    }
public:
  void insert(Item item)
    { insertT(head, item); }
-----
private:
  Item selectR(link h, int k)
    { if (h == 0) return nullItem;
      int t = (h->l == 0) ? 0: h->l->N;
      if (t > k) return selectR(h->l, k);
      if (t < k) return selectR(h->r, k-t-1);
      return h->item;
    }
public:
  Item select(int k)
    { return selectR(head, k); } 
-----
void partR(link& h, int k)
  { int t = (h->l == 0) ? 0: h->l->N;
    if (t > k )
      { partR(h->l, k); rotR(h); }
    if (t < k )
      { partR(h->r, k-t-1); rotL(h); }
  } 
-----
private:
  link joinLR(link a, link b)
    { 
      if (b == 0) return a;
      partR(b, 0); b->l = a; 
      return b;
    }
  void removeR(link& h, Key v)
    { if (h == 0) return;
      Key w = h->item.key(); 
      if (v < w) removeR(h->l, v);
      if (w < v) removeR(h->r, v);
      if (v == w) 
        { link t = h; 
          h = joinLR(h->l, h->r); delete t; }
    }
public:
  void remove(Item x)
    { removeR(head, x.key()); }
-----
    private:
      link joinR(link a, link b)
        { 
          if (b == 0) return a;
          if (a == 0) return b;
          insertT(b, a->item); 
          b->l = joinR(a->l, b->l); 
          b->r = joinR(a->r, b->r); 
          delete a; return b;
        }
    public:
      void join(ST<Item, Key>& b)
        { head = joinR(head, b.head); }

----------
CHAPTER 13. Balanced Trees
-----
void balanceR(link& h)
  {
    if ((h == 0) || (h->N == 1)) return;
    partR(h, h->N/2);
    balanceR(h->l);
    balanceR(h->r);
  }
-----
private:
  void insertR(link& h, Item x)
    { if (h == 0) { h = new node(x); return; }
      if (rand() < RAND_MAX/(h->N+1))
        { insertT(h, x); return; }
      if (x.key() < h->item.key()) 
           insertR(h->l, x);
      else insertR(h->r, x);
      h->N++; 
    }
public:
  void insert(Item x)
    { insertR(head, x); }
-----
private:
  link joinR(link a, link b)
    { 
      if (a == 0) return b;
      if (b == 0) return a;
      insertR(b, a->item); 
      b->l = joinR(a->l, b->l); 
      b->r = joinR(a->r, b->r); 
      delete a; fixN(b); return b;
    }
public:
  void join(ST<Item, Key>& b)
    { int N = head->N;
      if (rand()/(RAND_MAX/(N+b.head->N)+1) < N)
           head = joinR(head, b.head);
      else head = joinR(b.head, head); }
-----
link joinLR(link a, link b)
  { 
    if (a == 0) return b;
    if (b == 0) return a;
    if (rand()/(RAND_MAX/(a->N+b->N)+1) < a->N)
         { a->r = joinLR(a->r, b); return a; }
    else { b->l = joinLR(a, b->l); return b; }
  }
-----
private:
  void splay(link& h, Item x)
    { 
      if (h == 0) 
        { h = new node(x, 0, 0, 1); return; }
      if (x.key() < h->item.key())
        { link& hl = h->l; int N = h->N;
          if (hl == 0) 
            { h = new node(x, 0, h, N+1); return; }
          if (x.key() <  hl->item.key()) 
               { splay(hl->l, x); rotR(h); }
          else { splay(hl->r, x); rotL(hl); }
          rotR(h);
        }
      else
        { link &hr = h->r; int N = h->N;
          if (hr == 0) 
            { h = new node(x, h, 0, N+1); return; }
          if (hr->item.key() < x.key()) 
               { splay(hr->r, x); rotL(h); }
          else { splay(hr->l, x); rotR(hr); }
          rotL(h);
        }
    }
public:
  void insert(Item item)
    { splay(head, item); }
-----
private:
  int red(link x) 
    { if (x == 0) return 0; return x->red; }
  void RBinsert(link& h, Item x, int sw)
    { 
      if (h == 0) { h = new node(x); return; }
      if (red(h->l) && red(h->r)) 
      { h->red = 1; h->l->red = 0; h->r->red = 0; }
      if (x.key() < h->item.key())
        {
          RBinsert(h->l, x, 0); 
          if (red(h) && red(h->l) && sw) rotR(h); 
          if (red(h->l) && red(h->l->l)) 
            { rotR(h); h->red = 0; h->r->red = 1; }
        }
      else
        { 
          RBinsert(h->r, x, 1); 
          if (red(h) && red(h->r) && !sw) rotL(h); 
          if (red(h->r) && red(h->r->r)) 
            { rotL(h); h->red = 0; h->l->red = 1; }
        }
    }
public:
  void insert(Item x)
    { RBinsert(head, x, 0); head->red = 0; }
-----
private:
  Item searchR(link t, Key v, int k)
    { if (t == 0) return nullItem;
      if (v == t->item.key()) return t->item;
      link x = t->next[k];
      if ((x == 0) || (v < x->item.key())) 
        { 
          if (k == 0) return nullItem;
          return searchR(t, v, k-1); 
        }
      return searchR(x, v, k);
    }
public:
  Item search(Key v)
    { return searchR(head, v, lgN); }
-----
private:
  struct node 
    { Item item; node **next; int sz; 
      node(Item x, int k)
        { item = x; sz = k; next = new node*[k]; 
          for (int i = 0; i < k; i++) next[i] = 0; } 
    }; 
  typedef node *link;
  link head;
  Item nullItem;
  int lgN;
public:
  ST(int)
    { head = new node(nullItem, lgNmax); lgN = 0; }
-----
private:
  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 = x->item.key(); link tk = t->next[k];
      if ((tk == 0) || (v < tk->item.key())) 
        { 
          if (k < x->sz)
            { x->next[k] = tk; t->next[k] = x; }
          if (k == 0) return;
          insertR(t, x, k-1); return;
        }
      insertR(tk, x, k);
    }
public:
  void insert(Item v)
    { insertR(head, new node(v, randX()), lgN); }
-----
private:
  void removeR(link t, Key v, int k)
    { link x = t->next[k];
      if (!(x->item.key() < v)) 
        { 
          if (v == x->item.key())
            { t->next[k] = x->next[k]; }
          if (k == 0) { delete x; return; }
          removeR(t, v, k-1); return;
        }
      removeR(t->next[k], v, k);
    }
public:
  void remove(Item x)
    { removeR(head, x.key(), lgN); }

----------
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 < 0) ? (h + M) : h;
  }
-----
private:
  link* heads;
  int N, M;
public:
  ST(int maxN)
    { 
      N = 0; M = maxN/5;
      heads = new link[M]; 
      for (int i = 0; i < M; i++) heads[i] = 0;
    }
  Item search(Key v)
    { return searchR(heads[hash(v, M)], v); }
  void insert(Item item)
    { int i = hash(item.key(), M);
      heads[i] = new node(item, heads[i]); N++; }
-----
private:
  Item *st; 
  int N, M;
  Item nullItem;
public:
  ST(int maxN)
    { 
      N = 0; M = 2*maxN;
      st = new Item[M]; 
      for (int i = 0; i < M; i++) st[i] = nullItem;
    }
  int count() const { return N; }
  void insert(Item item)
    { int i = hash(item.key(), M);
      while (!st[i].null()) i = (i+1) % M;
      st[i] = item; N++;
    }
  Item search(Key v)
    { int i = hash(v, M);
      while (!st[i].null())
      if (v == st[i].key()) return st[i];
        else i = (i+1) % M;
      return nullItem;
    }
-----
void remove(Item x)
  { int i = hash(x.key(), M), j;
    while (!st[i].null())
      if (x.key() == st[i].key()) break; 
        else i = (i+1) % M;
    if (st[i].null()) return;
    st[i] = nullItem; N--;
    for (j = i+1; !st[j].null(); j = (j+1) % M, N--)
    { Item v = st[j]; st[j] = nullItem; insert(v); }
  }
-----
void insert(Item item)
  { Key v = item.key();
    int i = hash(v, M), k = hashtwo(v, M);
    while (!st[i].null()) i = (i+k) % M;
    st[i] = item; N++;
  }
Item search(Key v)
  { int i = hash(v, M), k = hashtwo(v, M);
    while (!st[i].null())
    if (v == st[i].key()) return st[i];
      else i = (i+k) % M;
    return nullItem;
  }
-----
private:
  void expand()
    { Item *t = st;
      init(M+M);
      for (int i = 0; i < M/2; i++)
        if (!t[i].null()) insert(t[i]);
      delete t;
    }
public:
  ST(int maxN)
    { init(4); }
  void insert(Item item)
    { int i = hash(item.key(), M);
      while (!st[i].null()) i = (i+1) % M;
      st[i] = item; 
      if (N++ >= M/2) expand();
    }

----------
CHAPTER 15. Radix Search
-----
private:
  Item searchR(link h, Key v, int d)
    { if (h == 0) return nullItem;
      if (v ==  h->item.key()) return h->item;
      if (digit(v, d) == 0)
           return searchR(h->l, v, d+1);
      else return searchR(h->r, v, d+1);
    }
public:
  Item search(Key v) 
    { return searchR(head, v, 0); } 
-----
private:
  Item searchR(link h, Key v, int d)
    { if (h == 0) return nullItem;
      if (h->l == 0 && h->r == 0)
        { Key w = h->item.key();
          return (v == w) ? h->item : nullItem; }
      if (digit(v, d) == 0)
           return searchR(h->l, v, d+1);
      else return searchR(h->r, v, d+1);
    }
public:
  Item search(Key v) 
    { return searchR(head, v, 0); } 
-----
private:
  link split(link p, link q, int d)
    { link t = new node(nullItem); t->N = 2;
      Key v = p->item.key(); Key w = q->item.key();
      switch(digit(v, d)*2 + digit(w, d))
        { case 0: t->l = split(p, q, d+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, d+1); break;
        }
      return t;
    }
  void insertR(link& h, Item x, int d)
    { if (h == 0) { h = new node(x); return; }
      if (h->l == 0 && h->r == 0)
        { h = split(new node(x), h, d); return; }
      if (digit(x.key(), d) == 0) 
           insertR(h->l, x, d+1);
      else insertR(h->r, x, d+1);
    }
public:
  ST(int maxN)
    { head = 0; }
  void insert(Item item)
    { insertR(head, item, 0); }
-----
private:
  Item searchR(link h, Key v, int d)
    { 
      if (h->bit <= d) return h->item;
      if (digit(v, h->bit) == 0)
           return searchR(h->l, v, h->bit);
      else return searchR(h->r, v, h->bit);
    }
public:
  Item search(Key v) 
    { Item t = searchR(head, v, -1); 
      return (v == t.key()) ? t : nullItem;
    } 
-----
private:
  link insertR(link h, Item x, int d, link p)
    { Key v = x.key();
      if ((h->bit >= d) || (h->bit <= p->bit))
        { 
          link t = new node(x); t->bit = d;
          t->l = (digit(v, t->bit) ? h : t);
          t->r = (digit(v, t->bit) ? t : h);
          return t; 
        }
      if (digit(v, h->bit) == 0)
           h->l = insertR(h->l, x, d, h);
      else h->r = insertR(h->r, x, d, h);
      return h;
    }
public:
  void insert(Item x)
    { Key v = x.key(); int i;
      Key w = searchR(head->l, v, -1).key();
      if (v == w) return;
      for (i = 0; digit(v, i) == digit(w, i); i++) ;
      head->l = insertR(head->l, x, i, head);
    }
  ST(int maxN)
    { head = new node(nullItem); 
      head->l = head->r = head; }
-----
private:
  void showR(link h, ostream& os, int d)
    { 
      if (h->bit <= d) { h->item.show(os); return; }
      showR(h->l, os, h->bit);
      showR(h->r, os, h->bit);
    }
public:
  void show(ostream& os)
    { showR(head->l, os, -1); } 
-----
private:
  struct node 
    { node **next;
      node()
        { n