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

        This file contains the code from "Algorithms in C++, Third Edition,
        Parts 1-4," by Robert Sedgewick, and is covered under the copyright
        and warranty notices in that book. Permission is granted for this
        code to be used for educational purposes in association with the text,
        and for other uses not covered by copyright laws, provided that
        the following notice is included with the code:

                "This code is from "Algorithms in C++, Third Edition,"
                by Robert Sedgewick, Addison-Wesley, 1999."

        Commercial uses of this code require the explicit written
        permission of the publisher. Send your request for permission,
        stating clearly what code you would like to use, and in what
        specific way, to: [e-mail]


----------
CHAPTER 1. Introduction
-----
#include <iostream.h>
static const int N = 10000;
int main()
  { int i, p, q, id[N];
    for (i = 0; i < N; i++) id[i] = i;
    while (cin >> p >> q)
      { int t = id[p];
        if (t == id[q]) continue;
        for (i = 0; i < N; i++)
          if (id[i] == t) id[i] = id[q];
        cout << " " << p << " " << q << endl;
      }
 }
-----
    for (i = p; i != id[i]; i = id[i]) ;
    for (j = q; j != id[j]; j = id[j]) ;
    if (i == j) continue;
    id[i] = j;
    cout << " " << p << " " << q << endl;
    -----
#include <iostream.h>
static const int N = 10000;
int main()
  { int i, j, p, q, id[N], sz[N];
    for (i = 0; i < N; i++) 
      { id[i] = i; sz[i] = 1; }
    while (cin >> p >> q)
      { 
        for (i = p; i != id[i]; i = id[i]) ;
        for (j = q; j != id[j]; j = id[j]) ;
        if (i == j) continue;
        if (sz[i] < sz[j])
             { id[i] = j; sz[j] += sz[i]; }
        else { id[j] = i; sz[i] += sz[j]; }
        cout << " " << p << " " << q << endl;
      }
 }
-----
    for (i = p; i != id[i]; i = id[i]) 
      id[i] = id[id[i]]; 
    for (j = q; j != id[j]; j = id[j]) 
      id[j] = id[id[j]]; 
    
----------
CHAPTER 2. Principles of Algorithm Analysis
-----
int search(int a[], int v, int l, int r)
  { 
    for (int i = l; i <= r; i++)
      if (v == a[i]) return i;
    return -1;
  }
-----
int search(int a[], int v, int l, int r)
  { 
    while (r >= l)
      { int m = (l+r)/2;
        if (v == a[m]) return m;
        if (v < a[m]) r = m-1; else l = m+1;
      }
    return -1;
  }

----------
CHAPTER 3. Elementary Data Structures
-----
#include <iostream.h>
int lg(int);
int main()
  { 
    for (int N = 1000; N <= 1000000000; N *= 10)
      cout << lg(N) << " " << N << endl; 
  }
int lg(int N)
  {
    for (int i = 0; N > 0; i++, N /= 2) ;
    return i;    
  }
-----
#include <iostream.h>
#include <stdlib.h>
#include <math.h>
typedef int Number;
Number randNum()
  { return rand(); }
int main(int argc, char *argv[])
  { int N = atoi(argv[1]);
    float m1 = 0.0, m2 = 0.0;
    for (int i = 0; i < N; i++)
      {
        Number x = randNum();
        m1 += ((float) x)/N; 
        m2 += ((float) x*x)/N;
      }
    cout << "     Avg.: " << m1 << endl;
    cout << "Std. dev.: " << sqrt(m2-m1*m1) << endl;
  }
-----
struct point { float x; float y; };
float distance(point, point);
-----
#include <math.h>
#include "Point.h"
float distance(point a, point b)
  { float dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx*dx + dy*dy);
  }
-----
#include <iostream.h>
static const int N = 1000;
int main()
  { int i, a[N];
    for (i = 2; i < N; i++) a[i] = 1;
    for (i = 2; i < N; i++)
      if (a[i])
        for (int j = i; j*i < N; j++) a[i*j] = 0;
    for (i = 2; i < N; i++)
      if (a[i]) cout << " " << i;
    cout << endl;
  }
-----
int main(int argc, char *argv[])
  { int i, N = atoi(argv[1]);
    int *a = new int[N];
    if (a == 0) 
      { cout << "out of memory" << endl; return 0; }
    ...
-----
#include <iostream.h>
#include <stdlib.h>
int heads()
  { return rand() < RAND_MAX/2; }
int main(int argc, char *argv[])
  { int i, j, cnt;
    int N = atoi(argv[1]), M = atoi(argv[2]);
    int *f = new int[N+1];
    for (j = 0; j <= N; j++) f[j] = 0;
    for (i = 0; i < M; i++, f[cnt]++)
      for (cnt = 0, j = 0; j <= N; j++) 
        if (heads()) cnt++;
    for (j = 0; j <= N; j++) 
      {
        if (f[j] == 0) cout << ".";
        for (i = 0; i < f[j]; i+=10) cout << "*";
        cout << endl;
      }
 }
-----
#include <math.h>
#include <iostream.h>
#include <stdlib.h>
#include "Point.h"
float randFloat()
  { return 1.0*rand()/RAND_MAX; }
int main(int argc, char *argv[])
 { float d = atof(argv[2]); 
   int i, cnt = 0, N = atoi(argv[1]);
   point *a = new point[N];
   for (i = 0; i < N; i++)
     { a[i].x = randFloat(); a[i].y = randFloat(); }
   for (i = 0; i < N; i++)
     for (int j = i+1; j < N; j++)
       if (distance(a[i], a[j]) < d) cnt++; 
   cout << cnt << " pairs within " << d << endl;
 }
-----
#include <iostream.h>
#include <stdlib.h>
struct node 
  { int item; node* next; 
    node(int x, node* t) 
      { item = x; next = t; } 
  };
typedef node *link;
int main(int argc, char *argv[])
  { int i, N = atoi(argv[1]), M = atoi(argv[2]); 
    link t = new node(1, 0); t->next = t;
    link x = t;
    for (i = 2; i <= N; i++)
      x = (x->next = new node(i, t));
    while (x != x->next)
      {
        for (i = 1; i < M; i++) x = x->next;
        x->next = x->next->next; 
      }
    cout << x->item << endl;
  }
-----
link reverse(link x)
  { link t, y = x, r = 0;
    while (y != 0)
      { t = y->next; y->next = r; r = y; y = t; }    
    return r;
  }
-----
    node heada(0, 0); link a = &heada, t = a; 
    for (int i = 0; i < N; i++)
      t = (t->next = new node(rand() % 1000, 0)); 
    node headb(0, 0); link u, x, b = &headb;
    for (t = a->next; t != 0; t = u)
      {
        u = t->next;
        for (x = b; x->next != 0; x = x->next)
          if (x->next->item > t->item) break;
        t->next = x->next; x->next = t; 
      }
-----
typedef int Item;
struct node { Item item; node *next; };
typedef node *link;
typedef link Node;

void construct(int);
Node newNode(int);
void deleteNode(Node);
void insert(Node, Node);
Node remove(Node);
Node next(Node);
Item item(Node);
-----
#include <iostream.h>
#include <stdlib.h>
#include "list.h"
int main(int argc, char *argv[])
  { int i, N = atoi(argv[1]), M = atoi(argv[2]); 
    Node t, x;
    construct(N); 
    for (i = 2, x = newNode(1); i <= N; i++)
      { t = newNode(i); insert(x, t); x = t; }
    while (x != next(x))
      {
        for (i = 1; i < M; i++) x = next(x);
        deleteNode(remove(x)); 
      }
    cout << item(x) << endl;
    return 0;
  }
-----
#include <stdlib.h>
#include "list.h"
link freelist;
void construct(int N)
  { 
    freelist = new node[N+1];
    for (int i = 0; i < N; i++)
      freelist[i].next = &freelist[i+1];
    freelist[N].next = 0;
  }    
link newNode(int i)
  { link x = remove(freelist); 
    x->item = i; x->next = x;
    return x;
  }
void deleteNode(link x)
  { insert(freelist, x); }
void insert(link x, link t)
  { t->next = x->next; x->next = t; }
link remove(link x)
  { link t = x->next; x->next = t->next; return t; }
link next(link x)
  { return x->next; }
Item item(link x)
  { return x->item; }
-----
#include <iostream.h>
#include <string.h>
static const int N = 10000;
int main(int argc, char *argv[])
  { int i; char t; 
    char a[N], *p = argv[1];
    for (i = 0; i < N-1; a[i] = t, i++)
      if (!cin.get(t)) break;
    a[i] = 0;
    for (i = 0; a[i] != 0; i++)
      { int j;
        for (j = 0; p[j] != 0; j++)
          if (a[i+j] != p[j]) break;
        if (p[j] == 0) cout << i << " ";
      }        
    cout << endl;
  }
-----
int **malloc2d(int r, int c)
  { int **t = new int*[r];
    for (int i = 0; i < r; i++)
      t[i] = new int[c];
    return t;
  }
-----
#include <iostream.h>
#include <stdlib.h>
#include <string.h>
int compare(const void *i, const void *j)
  { return strcmp(*(char **)i, *(char **)j); }
int main()
  { const int Nmax = 1000;
    const int Mmax = 10000;
    char* a[Nmax]; int N;
    char buf[Mmax]; int M = 0;
    for (N = 0; N < Nmax; N++)
      {
        a[N] = &buf[M];
        if (!(cin >> a[N])) break;
        M += strlen(a[N])+1;
      }
    qsort(a, N, sizeof(char*), compare);
    for (int i = 0; i < N; i++) 
      cout << a[i] << endl;
  }
-----
#include <iostream.h>
int main()
  { int i, j, adj[V][V];
    for (i = 0; i < V; i++)
      for (j = 0; j < V; j++) 
        adj[i][j] = 0;
    for (i = 0; i < V; i++) adj[i][i] = 1;
    while (cin >> i >> j)
      { adj[i][j] = 1; adj[j][i] = 1; }
  }
-----
#include <iostream.h>
struct node 
  { int v; node* next; 
    node(int x, node* t) 
      { v = x; next = t; } 
  };
typedef node *link;
int main()
  { int i, j; link adj[V];
    for (i = 0; i < V; i++) adj[i] = 0;
    while (cin >> i >> j)
      { 
        adj[j] = new node(i, adj[j]);
        adj[i] = new node(j, adj[i]);
      }
  }
-----
#include <math.h>
#include <iostream.h>
#include <stdlib.h>
#include "Point.h"
struct node 
  { point p; node *next; 
    node(point pt, node* t) { p = pt; next = t; } };
typedef node *link;
static link **grid; 
static int G, cnt = 0; static float d;
void gridinsert(float x, float y)
  { int X = x*G+1; int Y = y*G+1;
    point p; p.x = x; p.y = y;
    link s, t = new node(p, grid[X][Y]);
    for (int i = X-1; i <= X+1; i++)
      for (int j = Y-1; j <= Y+1; j++)
        for (s = grid[i][j]; s != 0; s = s->next)
          if (distance(s->p, t->p) < d) cnt++; 
    grid[X][Y] = t;
  }
int main(int argc, char *argv[])
 { int i, N = atoi(argv[1]);
   d = atof(argv[2]); G = 1/d;
   grid = malloc2d(G+2, G+2);
   for (i = 0; i < G+2; i++)
     for (int j = 0; j < G+2; j++)
       grid[i][j] = 0;
   for (i = 0; i < N; i++)
     gridinsert(randFloat(), randFloat());
   cout << cnt << " pairs within " << d << endl;
 }
-----

----------
CHAPTER 4. Abstract Data Types
-----
#include <math.h>
class POINT
  {
    private:
      float x, y;
    public:
      POINT()
        { x = 1.0*rand()/RAND_MAX;
          y = 1.0*rand()/RAND_MAX; }
      float distance(POINT a)
        { float dx = x-a.x, dy = y-a.y;
          return sqrt(dx*dx + dy*dy); }
  };
-----
#include <iostream.h>
#include <stdlib.h>
#include "POINT.cxx"
int main(int argc, char *argv[])
 { float d = atof(argv[2]); 
   int i, cnt = 0, N = atoi(argv[1]);
   POINT *a = new POINT[N];
   for (i = 0; i < N; i++)
     for (int j = i+1; j < N; j++)
       if (a[i].distance(a[j]) < d) cnt++; 
   cout << cnt << " pairs within " << d << endl;
 }
-----
class POINT
  {
    private:
      // Implementation-dependent code
    public:
      POINT();
      float distance(POINT) const;
  };
-----
template <class Item>
class STACK 
  {
    private:
      // Implementation-dependent code
    public:
      STACK(int);
      int empty() const;
      void push(Item item);
      Item pop();
  };
-----
#include <iostream.h>
#include <string.h>
#include "STACK.cxx"
int main(int argc, char *argv[])
  { char *a = argv[1]; int N = strlen(a);
    STACK<int> save(N);
    for (int i = 0; i < N; i++)
      {
        if (a[i] == '+') 
          save.push(save.pop() + save.pop());
        if (a[i] == '*') 
          save.push(save.pop() * save.pop());
        if ((a[i] >= '0') && (a[i] <= '9')) 
          save.push(0);
        while ((a[i] >= '0') && (a[i] <= '9')) 
          save.push(10*save.pop() + (a[i++]-'0')); 
      }
    cout << save.pop() << endl;
  }       
-----
#include <iostream.h>
#include <string.h>
#include "STACK.cxx"
int main(int argc, char *argv[])
  { char *a = argv[1]; int N = strlen(a);
    STACK<char> ops(N);
    for (int i = 0; i < N; i++)
      {
        if (a[i] == ')')
          cout << ops.pop() << " ";
        if ((a[i] == '+') || (a[i] == '*')) 
          ops.push(a[i]);
        if ((a[i] >= '0') && (a[i] <= '9')) 
          cout << a[i] << " ";
      }
    cout << endl;
  }       
-----
template <class Item>
class STACK 
  {
    private:
      Item *s; int N;
    public:
      STACK(int maxN)
        { s = new Item[maxN]; N = 0; }
      int empty() const
        { return N == 0; }
      void push(Item item)
        { s[N++] = item; }
      Item pop()
        { return s[--N]; }
  };
-----
template <class Item>
class STACK 
  {
    private:
      struct node 
        { Item item; node* next; 
          node(Item x, node* t) 
            { item = x; next = t; } 
        };
      typedef node *link;
      link head;
    public:
      STACK(int)
        { head = 0; }
      int empty() const
        { return head == 0; }
      void push(Item x)
        { head = new node(x, head); }
      Item pop()
        { Item v = head->item; link t = head->next;
          delete head; head = t; return v; }
  };
-----
class UF 
  {
    private:
      // Implementation-dependent code
    public:
      UF(int);
      int find(int, int);
      void unite(int, int);
  };
-----
#include <iostream.h>
#include <stdlib.h>
#include "UF.cxx"
int main(int argc, char *argv[])
  { int p, q, N = atoi(argv[1]);