algorithms in c++, parts 1-4 (fundamental algorithms, data structures, sorting, searching) code.txt

Algorithms in C++, Parts 1-4 (Fundamental Algorithms, Data Structures, Sorting, Searching) code

    UF info(N);
    while (cin >> p >> q)
      if (!info.find(p, q)) 
        { 
          info.unite(p, q);
          cout << " " << p << " " << q << endl; 
        }
  }
-----
class UF 
  {
    private:
      int *id, *sz;
      int find(int x)
        { while (x != id[x]) x = id[x]; return x; }
    public:
      UF(int N)
        { 
          id = new int[N]; sz = new int[N];
          for (int i = 0; i < N; i++) 
            { id[i] = i; sz[i] = 1; } 
        }
      int find(int p, int q)
        { return (find(p) == find(q)); }
      void unite(int p, int q)
        { int i = find(p), j = find(q);
          if (i == j) return;
          if (sz[i] < sz[j])
               { id[i] = j; sz[j] += sz[i]; }
          else { id[j] = i; sz[i] += sz[j]; }
        }
  };
-----
class uf 
  {
    public:
      virtual uf(int) = 0;
      virtual int find(int, int) = 0;
      virtual void unite(int, int) = 0;
  };
-----
template <class Item>
class QUEUE
  {
    private:
      // Implementation-dependent code
    public:
      QUEUE(int);
      int empty();
      void put(Item);
      Item get();
  };
-----
template <class Item>
class QUEUE 
  {
    private:
      struct node 
        { Item item; node* next; 
          node(Item x) 
            { item = x; next = 0; } 
        };
      typedef node *link;
      link head, tail;
    public:
      QUEUE(int)
        { head = 0; }
      int empty() const
        { return head == 0; }
      void put(Item x)
        { link t = tail; 
          tail = new node(x);
          if (head == 0) 
               head = tail;
          else t->next = tail;
        }
      Item get()
        { Item v = head->item; link t = head->next;
          delete head; head = t; return v; }
  };
-----
template <class Item>
class QUEUE
  {
    private:
      Item *q; int N, head, tail;
    public:
      QUEUE(int maxN)
        { q = new Item[maxN+1]; 
          N = maxN+1; head = N; tail = 0; }
      int empty() const
        { return head % N == tail; }
      void put(Item item)
        { q[tail++] = item; tail = tail % N; }
      Item get()
        { head = head % N; return q[head++]; }
  };
-----
template <class Item>
class STACK 
  {
    private:
      Item *s, *t; int N;
    public:
      STACK(int maxN)
        { 
          s = new Item[maxN]; N = 0; 
          t = new Item[maxN];
          for (int i = 0; i < maxN; i++) t[i] = 0; 
        }
      int empty() const
        { return N == 0; }
      void push(Item item)
        { 
          if (t[item] == 1) return;
          s[N++] = item; t[item] = 1; 
        }
      Item pop()
        { t[s[--N]] = 0; return s[N]; }
  };
-----
#include <iostream.h>
#include <stdlib.h>
#include <math.h>
#include "COMPLEX.cxx"
int main(int argc, char *argv[])
  { int N = atoi(argv[1]);
    cout << N << " complex roots of unity" << endl;
    for (int k = 0; k < N; k++)
      { float theta = 2.0*3.14159*k/N;
        Complex t(cos(theta), sin(theta)), x = t;
        cout << k << ": " << t << "  ";
        for (int j = 0; j < N-1; j++) x *= t;
        cout << x << endl;
      }
 }
-----
class Complex 
  {
    private:
      // Implementation-dependent code
    public:
      Complex(float, float);
      float Re() const;
      float Im() const;
      Complex& operator*=(Complex&);
  };
-----
#include <iostream.h>
class Complex 
  {
    private:
      float re, im;
    public:
      Complex(float x, float y)
        { re = x; im = y; }
      float Re() const
        { return re; }
      float Im() const
        { return im; }
      Complex& operator*=(const Complex& rhs)
        { float t = Re();
          re = Re()*rhs.Re() - Im()*rhs.Im();
          im = t*rhs.Im() + Im()*rhs.Re();
          return *this; 
        }
  };
ostream& operator<<(ostream& t, const Complex& c)
  { t << c.Re() << " " << c.Im(); return t; }
-----
#include <iostream.h>
#include <stdlib.h>
#include "QUEUE.cxx"
static const int M = 4;
int main(int argc, char *argv[])
  { int N = atoi(argv[1]); 
    QUEUE<int> queues[M];
    for (int i = 0; i < N; i++, cout << endl)
      { int in = rand() % M, out = rand() % M;
        queues[in].put(i);
        cout << i << " in ";
        if (!queues[out].empty())
          cout << queues[out].get() << " out";
        cout << endl;
        for (int k = 0; k < M; k++, cout << endl)
          { QUEUE<int> q = queues[k];
            cout << k << ": ";
            while (!q.empty())
              cout << q.get() << " ";
          }            
      }
  }
-----
template <class Item>
class QUEUE 
  {
    private:
      // Implementation-dependent code
    public:
      QUEUE(int);
      QUEUE(const QUEUE&);
      QUEUE& operator=(const QUEUE&);
      ~QUEUE();
      int empty() const;
      void put(Item);
      Item get();
  };
-----
    private:
      void deletelist()
        { 
          for (link t = head; t != 0; head = t)
            { t = head->next; delete head; }
        }
    public:
      QUEUE(const QUEUE& rhs)
        { head = 0; *this = rhs; }                  
      QUEUE& operator=(const QUEUE& rhs)
        { 
          if (this == &rhs) return *this;
          deletelist();
          link t = rhs.head;
          while (t != 0)
            { put(t->item); t = t->next; }
          return *this;
        }
      ~QUEUE()
        { deletelist(); }
-----
#include <iostream.h>
#include <stdlib.h>
#include "POLY.cxx"
int main(int argc, char *argv[])
  { int N = atoi(argv[1]); float p = atof(argv[2]);
    cout << "Binomial coefficients" << endl;
    POLY<int> x(1,1), one(1,0), t = x + one, y = t;
    for (int i = 0; i < N; i++)
      { y = y*t; cout << y << endl; }
    cout << y.eval(p) << endl;
 }
-----
template <class Number>
class POLY
  {
    private:
      // Implementation-dependent code
    public:
      POLY<Number>(Number, int);
      float eval(float) const;
      friend POLY operator+(POLY &, POLY &);
      friend POLY operator*(POLY &, POLY &);
  };
-----
template <class Number>
class POLY
  {
    private:
      int n; Number *a;
    public:
      POLY<Number>(Number c, int N)
        { a = new Number[N+1]; n = N+1; a[N] = c;
          for (int i = 0; i < N; i++) a[i] = 0; 
        }
      float eval(float x) const
        { double t = 0.0;
          for (int i = n-1; i >= 0; i--)
            t = t*x + a[i];
          return t;
        }
      friend POLY operator+(POLY &p, POLY &q)
        { POLY t(0, p.n>q.n ? p.n-1 : q.n-1);
          for (int i = 0; i < p.n; i++) 
            t.a[i] += p.a[i];
          for (int j = 0; j < q.n; j++) 
            t.a[j] += q.a[j];
          return t;
         }
      friend POLY operator*(POLY &p, POLY &q)
        { POLY t(0, (p.n-1)+(q.n-1));
          for (int i = 0; i < p.n; i++)
            for (int j = 0; j < q.n; j++)
              t.a[i+j] += p.a[i]*q.a[j];
          return t;
        }
  };

----------
CHAPTER 5. Recursion and Trees
-----
int factorial(int N)
  {
    if (N == 0) return 1;
    return N*factorial(N-1);
  }  
-----
int puzzle(int N)
  {
    if (N == 1) return 1;
    if (N % 2 == 0)
         return puzzle(N/2);
    else return puzzle(3*N+1);
  }  
-----
int gcd(int m, int n)
  {
    if (n == 0) return m;
    return gcd(n, m % n);
  }  
-----
char *a; int i;
int eval()
  { int x = 0;
    while (a[i] == ' ') i++;
    if (a[i] == '+')
      { i++; return eval() + eval(); }
    if (a[i] == '*')
      { i++; return eval() * eval(); }
    while ((a[i] >= '0') && (a[i] <= '9')) 
      x = 10*x + (a[i++]-'0'); 
    return x;
  }
-----
int count(link x)
  { 
    if (x == 0) return 0;
    return 1 + count(x->next); 
  }
void traverse(link h, void visit(link))
  { 
    if (h == 0) return;
    visit(h); 
    traverse(h->next, visit);
  }
void traverseR(link h, void visit(link))
  { 
    if (h == 0) return;
    traverseR(h->next, visit);
    visit(h); 
  }
void remove(link& x, Item v)
  { 
    while (x != 0 && x->item == v) 
      { link t = x; x = x->next; delete t; }
    if (x != 0) remove(x->next, v); 
  }
-----
Item max(Item a[], int l, int r)
  {
    if (l == r) return a[l];
    int m = (l+r)/2; 
    Item u = max(a, l, m);
    Item v = max(a, m+1, r);
    if (u > v) return u; else return v;
  }
-----
void hanoi(int N, int d)
  {
    if (N == 0) return;
    hanoi(N-1, -d);
    shift(N, d);    
    hanoi(N-1, -d);
  }  
-----
void rule(int l, int r, int h)
  { int m = (l+r)/2;
    if (h > 0)
      { 
        rule(l, m, h-1);
        mark(m, h);
        rule(m, r, h-1);
      }
  }
-----
void rule(int l, int r, int h)
  { 
    for (int t = 1, j = 1; t <= h; j += j, t++)
      for (int i = 0; l+j+i <= r; i += j+j)
        mark(l+j+i, t);
  }
-----
int F(int i)
  { 
    if (i < 1) return 0;
    if (i == 1) return 1;
    return F(i-1) + F(i-2);
  }
-----
int F(int i)
{ static int knownF[maxN];
  if (knownF[i] != 0) return knownF[i];
  int t = i;
  if (i < 0) return 0;
  if (i > 1) t = F(i-1) + F(i-2);
  return knownF[i] = t;
}
-----
int knap(int cap)
  { int i, space, max, t;
    for (i = 0, max = 0; i < N; i++)
      if ((space = cap-items[i].size) >= 0)
        if ((t = knap(space) + items[i].val) > max) 
          max = t;
    return max;     
  }
-----
int knap(int M)
  { int i, space, max, maxi = 0, t;
    if (maxKnown[M] != unknown) return maxKnown[M];
    for (i = 0, max = 0; i < N; i++)
      if ((space = M-items[i].size) >= 0)
        if ((t = knap(space) + items[i].val) > max)
          { max = t; maxi = i; }
    maxKnown[M] = max; itemKnown[M] = items[maxi];
    return max;     
  }
-----
void traverse(link h, void visit(link))
  { 
    if (h == 0) return;
    visit(h); 
    traverse(h->l, visit);
    traverse(h->r, visit);
  }
-----
void traverse(link h, void visit(link))
  { STACK<link> s(max);
    s.push(h);
    while (!s.empty())
      {
        visit(h = s.pop());
        if (h->r != 0) s.push(h->r); 
        if (h->l != 0) s.push(h->l); 
      }
  }
-----
void traverse(link h, void visit(link))
  { QUEUE<link> q(max);
    q.put(h);
    while (!q.empty())
      {
        visit(h = q.get());
        if (h->l != 0) q.put(h->l); 
        if (h->r != 0) q.put(h->r); 
      }
  }
-----
int count(link h)
  { 
    if (h == 0) return 0;
    return count(h->l) + count(h->r) + 1;
  }
int height(link h)
  { 
    if (h == 0) return -1;
    int u = height(h->l), v = height(h->r);
    if (u > v) return u+1; else return v+1;
  }
-----
void printnode(Item x, int h)
  { for (int i = 0; i < h; i++) cout << "  ";
    cout << x << endl;
  }
void show(link t, int h)
  { 
    if (t == 0) { printnode('*', h); return; }
    show(t->r, h+1);    
    printnode(t->item, h);
    show(t->l, h+1);    
  }
-----
struct node 
  { Item item; node *l, *r;
    node(Item x)
      { item = x; l = 0; r = 0; } 
  }; 
typedef node* link;
link max(Item a[], int l, int r)
  { int m = (l+r)/2;
    link x = new node(a[m]);
    if (l == r) return x;
    x->l = max(a, l, m);
    x->r = max(a, m+1, r);
    Item u = x->l->item, v = x->r->item;
    if (u > v) 
      x->item = u; else x->item = v;
    return x;
  }
-----
char *a; int i;
struct node 
  { Item item; node *l, *r; 
    node(Item x)
      { item = x; l = 0; r = 0; }
  };
typedef node* link;
link parse()
  { char t = a[i++]; link x = new node(t);
    if ((t == '+') || (t == '*'))
      { x->l = parse(); x->r = parse(); }
    return x;
  }
-----
void traverse(int k, void visit(int))
  { visit(k); visited[k] = 1;
    for (link t = adj[k]; t != 0; t = t->next)
      if (!visited[t->v]) traverse(t->v, visit);
  }
-----
void traverse(int k, void visit(int))
  {
    QUEUE<int> q(V*V);
    q.put(k);
    while (!q.empty())
      if (visited[k = q.get()] == 0)
        {
          visit(k); visited[k] = 1;
          for (link t = adj[k]; t != 0; t = t->next)
            if (visited[t->v] == 0) q.put(t->v);
        }
  }
-----

----------
CHAPTER 6. Elementary Sorting Methods
-----
#include <iostream.h>
#include <stdlib.h>
template <class Item> 
  void exch(Item &A, Item &B) 
    { Item t = A; A = B; B = t; } 
template <class Item> 
  void compexch(Item &A, Item &B) 
    { if (B < A) exch(A, B); }
template <class Item>