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

Robert Sedgewick的不朽之作《Algorithms》

void heapsort(Item a[], int l, int r)
  { int k, N = r-l+1;
    Item *pq = a+l-1;
    for (k = N/2; k >= 1; k--) 
      fixDown(pq, k, N);
    while (N > 1) 
      { exch(pq[1], pq[N]); 
        fixDown(pq, 1, --N); }
  }
-----
template <class Item>
class PQ 
  {
    private:
      // Implementation-dependent code
    public:
      // Implementation-dependent handle definition
      PQ(int);
      int empty() const;
      handle insert(Item);
      Item getmax();
      void change(handle, Item);
      void remove(handle);
      void join(PQ<Item>&);
  };
-----
template <class Item>
class PQ 
  {
    private:
      struct node 
        { Item item; node *prev, *next; 
          node(Item v) 
            { item = v; prev = 0; next = 0; } 
        }; 
      typedef node *link;
      link head, tail;
    public:
      typedef node* handle;
      PQ(int = 0)
        { 
          head = new node(0); tail = new node(0); 
          head->prev = tail; head->next = tail;
          tail->prev = head; tail->next = head; 
        }
      int empty() const
        { return head->next->next == head; }
      handle insert(Item v)
        { handle t = new node(v);
          t->next = head->next; t->next->prev = t;
          t->prev = head; head->next = t;
          return t;
         }
      Item getmax();
      void change(handle, Item);
      void remove(handle);
      void join(PQ<Item>&);
  };
-----
  Item getmax()
    { Item max; link x = head->next;
      for (link t = x; t->next != head; t = t->next)
        if (x->item < t->item) x = t;
      max = x->item; 
      remove(x); 
      return max;
    }
  void change(handle x, Item v)
    { x->key = v; }  
  void remove(handle x)
    {
      x->next->prev = x->prev;
      x->prev->next = x->next;
      delete x;
    }  
  void join(PQ<Item>& p)
    {
      tail->prev->next = p.head->next;
      p.head->next->prev = tail->prev;
      head->prev = p.tail; 
      p.tail->next = head;
      delete tail; delete p.head;
      tail = p.tail;
    }
-----
template <class Index>
class PQ 
  {
    private:
      // Implementation-dependent code
    public:
      PQ(int);
      int empty() const;
      void insert(Index);
      Index getmax();
      void change(Index);
      void remove(Index);
  };
-----
template <class Index>
class PQ 
  {
    private:
      int N; Index* pq; int* qp;
      void exch(Index i, Index j)
        { int t;
          t = qp[i]; qp[i] = qp[j]; qp[j] = t;
          pq[qp[i]] = i; pq[qp[j]] = j;
        }
    void fixUp(Index a[], int k);
    void fixDown(Index a[], int k, int N);
    public:
      PQ(int maxN)
        { pq = new Index[maxN+1]; 
          qp = new int[maxN+1];  N = 0; }
      int empty() const
        { return N == 0; }
      void insert(Index v)
        { pq[++N] = v; qp[v] = N; fixUp(pq, N); }
      Index getmax()
        { 
          exch(pq[1], pq[N]); 
          fixDown(pq, 1, N-1); 
          return pq[N--]; 
        }
      void change(Index k)
        { fixUp(pq, qp[k]); fixDown(pq, qp[k], N); }
  };
-----
static link pair(link p, link q)
  {
    if (p->item < q->item) 
      { p->r = q->l; q->l = p; return q; }
    else { q->r = p->l; p->l = q; return p; }
  }
-----
handle insert(Item v)
  { link t = new node(v), c = t;
    for (int i = 0; i < maxBQsize; i++)
      {
        if (c == 0) break;
        if (bq[i] == 0) { bq[i] = c; break; }
        c = pair(c, bq[i]); bq[i] = 0;
      }
    return t;
  }
-----
Item getmax()
  { int i, max; Item v = 0; 
    link* temp = new link[maxBQsize];
    for (i = 0, max = -1; i < maxBQsize; i++)
      if (bq[i] != 0) 
        if ((max == -1) || (v < bq[i]->item))
          { max = i; v = bq[max]->item; }
    link x = bq[max]->l; 
    for (i = max; i < maxBQsize; i++) temp[i] = 0; 
    for (i = max ; i > 0; i--)
      { temp[i-1] = x; x = x->r; temp[i-1]->r = 0; }
    delete bq[max]; bq[max] = 0;
    BQjoin(bq, temp);  
    delete temp;
    return v;
  }      
-----
static inline int test(int C, int B, int A)
  { return 4*C + 2*B + 1*A; }
static void BQjoin(link *a, link *b)
  { link c = 0;
    for (int i = 0; i < maxBQsize; i++)
      switch(test(c != 0, b[i] != 0, a[i] != 0))
        {
          case 2: a[i] = b[i]; break;
          case 3: c = pair(a[i], b[i]); 
                  a[i] = 0; break;
          case 4: a[i] = c; c = 0; break;
          case 5: c = pair(c, a[i]); 
                  a[i] = 0; break;
          case 6: 
          case 7: c = pair(c, b[i]); break;
        }
  }

----------
CHAPTER 10. Radix Sorting
-----
template <class Item>
void quicksortB(Item a[], int l, int r, int d)
  { int i = l, j = r;
    if (r <= l || d > bitsword) return;
    while (j != i)
      { 
        while (digit(a[i], d) == 0 && (i < j)) i++;
        while (digit(a[j], d) == 1 && (j > i)) j--;
        exch(a[i], a[j]);
      }
    if (digit(a[r], d) == 0) j++;
    quicksortB(a, l, j-1, d+1);
    quicksortB(a, j, r, d+1);
  }
template <class Item>
void sort(Item a[], int l, int r)
  { quicksortB(a, l, r, 0); }
-----
#define bin(A) l+count[A]
template <class Item>
void radixMSD(Item a[], int l, int r, int d)
  { int i, j, count[R+1]; 
    static Item aux[maxN];
    if (d > bytesword) return;
    if (r-l <= M) { insertion(a, l, r); return; }
    for (j = 0; j < R; j++) count[j] = 0;
    for (i = l; i <= r; i++) 
      count[digit(a[i], d) + 1]++;
    for (j = 1; j < R; j++) 
      count[j] += count[j-1];
    for (i = l; i <= r; i++) 
      aux[count[digit(a[i], d)]++] = a[i];
    for (i = l; i <= r; i++) a[i] = aux[i-l];
    radixMSD(a, l, bin(0)-1, d+1);
    for (j = 0; j < R-1; j++)
      radixMSD(a, bin(j), bin(j+1)-1, d+1);
  }
-----
#define ch(A) digit(A, d)
template <class Item>
void quicksortX(Item a[], int l, int r, int d)
  { 
    int i, j, k, p, q; int v;
    if (r-l <= M) { insertion(a, l, r); return; }
    v = ch(a[r]); i = l-1; j = r; p = l-1; q = r;
    while (i < j)
      { 
        while (ch(a[++i]) < v) ;
        while (v < ch(a[--j])) if (j == l) break;
        if (i > j) break;
        exch(a[i], a[j]);
        if (ch(a[i])==v) { p++; exch(a[p], a[i]); }
        if (v==ch(a[j])) { q--; exch(a[j], a[q]); }
      }
    if (p == q) 
      { if (v != '\0') quicksortX(a, l, r, d+1); 
        return; }
    if (ch(a[i]) < v) i++;
    for (k = l; k <= p; k++, j--) exch(a[k], a[j]);
    for (k = r; k >= q; k--, i++) exch(a[k], a[i]);
    quicksortX(a, l, j, d);
    if ((i == r) && (ch(a[i]) == v)) i++;
    if (v != '\0') quicksortX(a, j+1, i-1, d+1); 
    quicksortX(a, i, r, d); 
  }
-----
template <class Item>
void radixLSD(Item a[], int l, int r)
  { static Item aux[maxN];
    for (int d = bytesword-1; d >= 0; d--)
      {
        int i, j, count[R+1]; 
        for (j = 0; j < R; j++) count[j] = 0;
        for (i = l; i <= r; i++) 
          count[digit(a[i], d) + 1]++;
        for (j = 1; j < R; j++) 
          count[j] += count[j-1];
        for (i = l; i <= r; i++) 
          aux[count[digit(a[i], d)]++] = a[i];
        for (i = l; i <= r; i++) a[i] = aux[i-l];
      }
  } 

----------
CHAPTER 11. Special-Purpose Sorts
-----
template <class Item>
void shuffle(Item a[], int l, int r)
  { int i, j, m = (l+r)/2;
    static Item aux[maxN];
    for (i = l, j = 0; i <= r; i+=2, j++)
      { aux[i] = a[l+j]; aux[i+1] = a[m+1+j]; }
    for (i = l; i <= r; i++) a[i] = aux[i];
  }
template <class Item>
void unshuffle(Item a[], int l, int r)
  { int i, j, m = (l+r)/2;
    static Item aux[maxN];
    for (i = l, j = 0; i <= r; i+=2, j++)
      { aux[l+j] = a[i]; aux[m+1+j] = a[i+1]; }
    for (i = l; i <= r; i++) a[i] = aux[i];
  }
-----
template <class Item>
void merge(Item a[], int l, int m, int r)
  { 
    if (r == l+1) compexch(a[l], a[r]);
    if (r < l+2) return;
    unshuffle(a, l, r);
    merge(a, l, (l+m)/2, m); 
    merge(a, m+1, (m+1+r)/2, r);
    shuffle(a, l, r);
    for (int i = l+1; i < r; i+=2) 
      compexch(a[i], a[i+1]);
  }
-----
template <class Item>
void merge(Item a[], int l, int m, int r)
  { int N = r-l+1;  // assuming N/2 is m-l+1
    for (int k = N/2; k > 0; k /= 2)
      for (int j = k % (N/2); j+k < N; j += k+k) 
        for (int i = 0; i < k; i++) 
          compexch(a[l+j+i], a[l+j+i+k]);
  }
-----
template <class Item>
void batchersort(Item a[], int l, int r)
  { int N = r-l+1;
    for (int p = 1; p < N; p += p)
      for (int k = p; k > 0; k /= 2)
        for (int j = k%p; j+k < N; j += (k+k)) 
          for (int i = 0; i < N-j-k; i++) 
            if ((j+i)/(p+p) == (j+i+k)/(p+p)) 
              compexch(a[l+j+i], a[l+j+i+k]);
  }
-----
-----

----------
CHAPTER 12. Symbol Tables and BSTs
-----
#include <stdlib.h>
#include <iostream.h>
static int maxKey = 1000;
typedef int Key;
class Item 
  { 
    private:
      Key keyval; 
      float info;
    public:
      Item() 
        { keyval = maxKey; } 
      Key key()
        { return keyval; }
      int null()
        { return keyval == maxKey; }
      void rand()
        { keyval = 1000*::rand()/RAND_MAX;   
          info = 1.0*::rand()/RAND_MAX; }  
      int scan(istream& is = cin)
        { return (is >> keyval >> info) != 0; }
      void show(ostream& os = cout)
        { os << keyval << " " << info << endl; }
   }; 
ostream& operator<<(ostream& os, Item& x)
  { x.show(os); return os; }
-----
template <class Item, class Key>
class ST 
  {
    private:
      // Implementation-dependent code
    public:
      ST(int);
      int count();
      Item search(Key) ;
      void insert(Item);
      void remove(Item);
      Item select(int);
      void show(ostream&);
  };
-----
#include <iostream.h>
#include <stdlib.h>
#include "Item.cxx"
#include "ST.cxx"
int main(int argc, char *argv[])
  { int N, maxN = atoi(argv[1]), sw = atoi(argv[2]);
    ST<Item, Key> st(maxN);
    for (N = 0; N < maxN; N++)
      { Item v; 
        if (sw) v.rand(); else if (!v.scan()) break;
        if (!(st.search(v.key())).null()) continue;
        st.insert(v); 
      }
    st.show(cout); cout << endl;
    cout << N << " keys" << endl;
    cout << st.count() << " distinct keys" << endl;
  }
-----
template <class Item, class Key>
class ST 
  {
    private:
      Item nullItem, *st;
      int M;
    public:
      ST(int maxN)
        { M = nullItem.key(); st = new Item[M]; }
      int count()
        { int N = 0; 
          for (int i = 0; i < M; i++) 
            if (!st[i].null()) N++;
          return N;
        }
      void insert(Item x)
        { st[x.key()] = x; }
      Item search(Key v)
        { return st[v]; }
      void remove(Item x)
        { st[x.key()] = nullItem; }
      Item select(int k)
        { for (int i = 0; i < M; i++)
            if (!st[i].null()) 
              if (k-- == 0) return st[i];
          return nullItem;
        }
      void show(ostream& os)
        { for (int i = 0; i < M; i++)
            if (!st[i].null()) st[i].show(os); }
  };
-----
template <class Item, class Key>
class ST 
  {
    private:
      Item nullItem, *st; 
      int N;
    public:
      ST(int maxN)
        { st = new Item[maxN+1]; N = 0; }
      int count()
        { return N; }
      void insert(Item x)
        { int i = N++; Key v = x.key();
          while (i > 0 && v < st[i-1].key())
            {  st[i] = st[i-1]; i--; }
          st[i] = x;
        }
      Item search(Key v)
        {
          for (int i = 0; i < N; i++)
            if (!(st[i].key() < v)) break;
          if (v == st[i].key()) return st[i];
          return nullItem;
        }
      Item select(int k)
        { return st[k]; }
      void show(ostream& os)
        { int i = 0; 
          while (i < N) st[i++].show(os); }
  };
-----
#include <stdlib.h>
template <class Item, class Key>
class ST 
  {
    private:
      Item nullItem;
      struct node 
        { Item item; node* next; 
          node(Item x, node* t)
            { item = x; next = t; } 
        }; 
      typedef node *link;
      int N;
      link head;
      Item searchR(link t, Key v)
        { if (t == 0) return nullItem;
          if (t->item.key() == v) return t->item;
          return searchR(t->next, v);
        }
    public:
      ST(int maxN)
        { head = 0; N = 0; }
      int count()
        { return N; }
      Item search(Key v)
        { return searchR(head, v); }
      void insert(Item x)
        { head = new node(x, head); N++; }
    };
-----
    private:
      Item searchR(int l, int r, Key v)
        { if (l > r) return nullItem;
          int m = (l+r)/2;
          if (v == st[m].key()) return st[m];
          if (l == r) return nullItem;
          if (v < st[m].key()) 
               return searchR(l, m-1, v);
          else return searchR(m+1, r, v);
        }
    public:
      Item search(Key v)
        { return searchR(0, N-1, v); }
-----
template <class Item, class Key>
class ST 
  {
    private:
      struct node 
        { Item item; node *l, *r;
          node(Item x)
            { item = x; l = 0; r = 0; } 
        }; 
      typedef node *link;
      link head;
      Item nullItem;
      Item searchR(link h, Key v)
        { if (h == 0) return nullItem;
          Key t = h->item.key();
          if (v == t) return h->item;
          if (v < t) return searchR(h->l, v);
                else return searchR(h->r, v);
        }
      void insertR(link& h, Item x)
        { if (h == 0) { h = new node(x); return; }
          if (x.key() < h->item.key())