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, 1998."

        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 <stdio.h>
#define N 10000
main()
  { int i, p, q, t, id[N];
    for (i = 0; i < N; i++) id[i] = i;
    while (scanf("%d %d\n", &p, &q) == 2)
      { 
        if (id[p] == id[q]) continue;
        for (t = id[p], i = 0; i < N; i++)
          if (id[i] == t) id[i] = id[q];
        printf(" %d %d\n", p, q);
      }
 }
-----
    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;
    printf(" %d %d\n", p, q);
-----
#include <stdio.h>
#define N 10000
main()
  { int i, j, p, q, id[N], sz[N];
    for (i = 0; i < N; i++) 
      { id[i] = i; sz[i] = 1; }
    while (scanf("%d %d\n", &p, &q) == 2)
      { 
        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]; }
        printf(" %d %d\n", p, q);
      }
 }
-----
    for (i = p; i != id[i]; i = id[i]) 
      { int t = i; i = id[id[t]]; id[t] = i; } 
    for (j = q; j != id[j]; j = id[j]) ;
      { int t = j; j = id[id[t]]; id[t] = j; } 

----------
CHAPTER 2. Principles of Algorithm Analysis
-----
int search(int a[], int v, int l, int r)
  { int i;
    for (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 <stdio.h>
int lg(int);
main()
  { int i, N; 
    for (i = 1, N = 10; i <= 6; i++, N *= 10)
      printf("%7d %2d %9d\n", N, lg(N), N*lg(N));
  }
int lg(int N)
  {  int i;
     for (i = 0; N > 0; i++, N /= 2) ;
     return i;    
  }
-----
#include <stdlib.h>
typedef int numType;
numType randNum()
  { return rand(); }
main(int argc, char *argv[])
  { int i, N = atoi(argv[1]);
    float m1 = 0.0, m2 = 0.0;
    numType x;
    for (i = 0; i < N; i++)
      {
        x = randNum();
        m1 += ((float) x)/N; 
        m2 += ((float) x*x)/N;
      }
    printf("       Average: %f\n", m1);
    printf("Std. deviation: %f\n", sqrt(m2-m1*m1));
 }
-----
typedef struct { float x; float y; } point;
float distance(point a, point b);
-----
#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);
  }
-----
#define N 10000
main()
  { int i, j, a[N];
    for (i = 2; i < N; i++) a[i] = 1;
    for (i = 2; i < N; i++)
      if (a[i])
        for (j = i; j < N/i; j++) a[i*j] = 0;
    for (i = 2; i < N; i++)
      if (a[i]) printf("%4d ", i);
    printf("\n");
  }
-----
#include <stdlib.h>
main(int argc, char *argv[])
  { long int i, j, N = atoi(argv[1]);
    int *a = malloc(N*sizeof(int));
    if (a == NULL) 
      { printf("Insufficient memory.\n"); return; }
    ...
-----
#include <stdlib.h>
int heads()
  { return rand() < RAND_MAX/2; }
main(int argc, char *argv[])
  { int i, j, cnt;
    int N = atoi(argv[1]), M = atoi(argv[2]);
    int *f = malloc((N+1)*sizeof(int));
    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++) 
      {
        printf("%2d ", j);
        for (i = 0; i < f[j]; i+=10) printf("*");
        printf("\n");
      }
 }
-----
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include "Point.h"
float randFloat()
  { return 1.0*rand()/RAND_MAX; }
main(int argc, char *argv[])
 { float d = atof(argv[2]); 
   int i, j, cnt = 0, N = atoi(argv[1]);
   point *a = malloc(N*(sizeof(*a)));
   for (i = 0; i < N; i++)
     { a[i].x = randFloat(); a[i].y = randFloat(); }
   for (i = 0; i < N; i++)
     for (j = i+1; j < N; j++)
       if (distance(a[i], a[j]) < d) cnt++; 
   printf("%d edges shorter than %f\n", cnt, d);
 }
-----
#include <stdlib.h>
typedef struct node* link;
struct node { int item; link next; };
main(int argc, char *argv[])
  { int i, N = atoi(argv[1]), M = atoi(argv[2]); 
    link t = malloc(sizeof *t), x = t;
    t->item = 1; t->next = t;
    for (i = 2; i <= N; i++)
      { 
        x = (x->next = malloc(sizeof *x));
        x->item = i; x->next = t;
      }
    while (x != x->next)
      {
        for (i = 1; i < M; i++) x = x->next;
        x->next = x->next->next; N--;
      }
    printf("%d\n", x->item);
  }
-----
link reverse(link x)
  { link t, y = x, r = NULL;
    while (y != NULL)
      { t = y->next; y->next = r; r = y; y = t; }    
    return r;
  }
-----
    struct node heada, headb;
    link t, u, x, a = &heada, b;
    for (i = 0, t = a; i < N; i++)
      {
        t->next = malloc(sizeof *t); 
        t = t->next; t->next = NULL;
        t->item = rand() % 1000; 
      }
    b = &headb; b->next = NULL;
    for (t = a->next; t != NULL; t = u)
      {
        u = t->next;
        for (x = b; x->next != NULL; x = x->next)
          if (x->next->item > t->item) break;
        t->next = x->next; x->next = t; 
      }
-----
typedef struct node* link;
struct node { itemType item; link next; };
typedef link Node;
void initNodes(int);
link newNode(int);
void freeNode(link);
void insertNext(link, link);
link deleteNext(link);
link Next(link);
 int Item(link);
-----
#include "list.h"
main(int argc, char *argv[])
  { int i, N = atoi(argv[1]), M = atoi(argv[2]); 
    Node t, x;
    initNodes(N); 
    for (i = 2, x = newNode(1); i <= N; i++)
      { t = newNode(i); insertNext(x, t); x = t; }
    while (x != Next(x))
      {
        for (i = 1; i < M; i++) x = Next(x);
        freeNode(deleteNext(x)); 
      }
    printf("%d\n", Item(x));
  }
-----
#include <stdlib.h>
#include "list.h"
link freelist;
void initNodes(int N)
  { int i;
    freelist = malloc((N+1)*(sizeof *freelist));
    for (i = 0; i < N+1; i++)
      freelist[i].next = &freelist[i+1];
    freelist[N].next = NULL;
  }    
link newNode(int i)
  { link x = deleteNext(freelist); 
    x->item = i; x->next = x;
    return x;
  }
void freeNode(link x)
  { insertNext(freelist, x); }
void insertNext(link x, link t)
  { t->next = x->next; x->next = t; }
link deleteNext(link x)
  { link t = x->next; x->next = t->next; return t; }
link Next(link x)
  { return x->next; }
int Item(link x)
  { return x->item; }
-----
#include <stdio.h>
#define N 10000
main(int argc, char *argv[])
  { int i, j, t; 
    char a[N], *p = argv[1];
    for (i = 0; i < N-1; a[i] = t, i++)
      if ((t = getchar()) == EOF) break;
    a[i] = 0;
    for (i = 0; a[i] != 0; i++)
      {
        for (j = 0; p[j] != 0; j++)
          if (a[i+j] != p[j]) break;
        if (p[j] == 0) printf("%d ", i);
      }        
    printf("\n");
  }
-----
int **malloc2d(int r, int c)
  { int i;
    int **t = malloc(r * sizeof(int *));
    for (i = 0; i < r; i++)
      t[i] = malloc(c * sizeof(int));
    return t;
  }
-----
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Nmax 1000
#define Mmax 10000
char buf[Mmax]; int M = 0;
int compare(void *i, void *j)
  { return strcmp(*(char **)i, *(char **)j); }
main()
  { int i, N;
    char* a[Nmax]; 
    for (N = 0; N < Nmax; N++)
      {
        a[N] = &buf[M];
        if (scanf("%s", a[N]) == EOF) break;
        M += strlen(a[N])+1;
      }
    qsort(a, N, sizeof(char*), compare);
    for (i = 0; i < N; i++) printf("%s\n", a[i]);
  }
-----
#include <stdio.h>
#include <stdlib.h>
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 (scanf("%d %d\n", &i, &j) == 2)
      { adj[i][j] = 1; adj[j][i] = 1; }
  }
-----
#include <stdio.h>
#include <stdlib.h>
typedef struct node *link;
struct node
  { int v; link next; };
link NEW(int v, link next)
  { link x = malloc(sizeof *x);
    x->v = v; x->next = next;     
    return x;                         
  }
main()
  { int i, j; link adj[V];
    for (i = 0; i < V; i++) adj[i] = NULL;
    while (scanf("%d %d\n", &i, &j) == 2)
      {
        adj[j] = NEW(i, adj[j]);
        adj[i] = NEW(j, adj[i]);
      }
  }
-----
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include "Point.h"
typedef struct node* link;
struct node { point p;  link next; };
link **grid; int G; float d; int cnt = 0;
gridinsert(float x, float y)
  { int i, j; link s;
    int X = x*G +1; int Y = y*G+1;
    link t = malloc(sizeof *t);
    t->p.x = x; t->p.y = y; 
    for (i = X-1; i <= X+1; i++)
      for (j = Y-1; j <= Y+1; j++)
        for (s = grid[i][j]; s != NULL; s = s->next)
          if (distance(s->p, t->p) < d) cnt++; 
    t->next = grid[X][Y]; grid[X][Y] = t;
  }
main(int argc, char *argv[])
 { int i, j, 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 (j = 0; j < G+2; j++)
       grid[i][j] = NULL;
   for (i = 0; i < N; i++)
     gridinsert(randFloat(), randFloat());
   printf("%d edges shorter than %f\n", cnt, d);
 }
-----
#include <math.h>
#include <stdlib.h>
typedef int numType;
#define R 1000
numType randNum()
  { return rand() % R; }
main(int argc, char *argv[])
  { int i, N = atoi(argv[1]);
    int *f = malloc(R*sizeof(int));
    float m1 = 0.0, m2 = 0.0, t = 0.0;
    numType x;
    for (i = 0; i < R; i++) f[i] = 0;
    for (i = 0; i < N; i++)
      {
        f[x = randNum()]++;
        m1 += (float) x/N; 
        m2 += (float) x*x/N;
      }
    for (i = 0; i < R; i++) t += f[i]*f[i];
    printf("       Average: %f\n", m1);
    printf("Std. deviation: %f\n", sqrt(m2-m1*m1));
    printf("    Chi-square: %f\n", (R*t/N)-N);
 }


----------
CHAPTER 4. Abstract Data Types
-----
void STACKinit(int);
 int STACKempty();
void STACKpush(Item);
Item STACKpop();
-----
#include <stdio.h>
#include <string.h>
#include "Item.h"
#include "STACK.h"
main(int argc, char *argv[])
  { char *a = argv[1]; int i, N = strlen(a);
    STACKinit(N);
    for (i = 0; i < N; i++)
      {
        if (a[i] == '+')
          STACKpush(STACKpop()+STACKpop());
        if (a[i] == '*')
          STACKpush(STACKpop()*STACKpop());
        if ((a[i] >= '0') && (a[i] <= '9')) 
          STACKpush(0);
        while ((a[i] >= '0') && (a[i] <= '9')) 
          STACKpush(10*STACKpop() + (a[i++]-'0')); 
      }
    printf("%d \n", STACKpop());
  }       
-----
#include <stdio.h>
#include <string.h>
#include "Item.h"
#include "STACK.h"
main(int argc, char *argv[])
  { char *a = argv[1]; int i, N = strlen(a);
    STACKinit(N);
    for (i = 0; i < N; i++)
      {
        if (a[i] == ')')
          printf("%c ", STACKpop()); 
        if ((a[i] == '+') || (a[i] == '*')) 
          STACKpush(a[i]);
        if ((a[i] >= '0') && (a[i] <= '9')) 
          printf("%c ", a[i]); 
      }
    printf("\n");
  }       
-----
#include <stdlib.h>
#include "Item.h"
#include "STACK.h"
static Item *s;
static int N;
void STACKinit(int maxN)
  { s = malloc(maxN*sizeof(Item)); N = 0; }
int STACKempty()
  { return N == 0; }
void STACKpush(Item item)
  { s[N++] = item; }
Item STACKpop()
  { return s[--N]; }

-----
#include <stdlib.h>
#include "Item.h"
typedef struct STACKnode* link;
struct STACKnode { Item item; link next; };
static link head;
link NEW(Item item, link next)      
  { link x = malloc(sizeof *x);
    x->item = item; x->next = next;     
    return x;                         
  }                                   
void STACKinit(int maxN) 
  { head = NULL; }
int STACKempty()
  { return head == NULL; }
STACKpush(Item item)
  { head = NEW(item, head); }
Item STACKpop()
  { Item item = head->item;
    link t = head->next; 
    free(head); head = t;
    return item;
  }
-----
void UFinit(int);
 int UFfind(int, int);
 int UFunion(int, int);
-----
#include <stdio.h>
#include "UF.h"
main(int argc, char *argv[])
  { int p, q, N = atoi(argv[1]);
    UFinit(N);
    while (scanf("%d %d", &p, &q) == 2)
      if (!UFfind(p, q)) 
        { UFunion(p, q); printf(" %d %d\n", p, q); }
 }
-----
#include <stdlib.h>
#include "UF.h"
static int *id, *sz;
void UFinit(int N)
  { int i;
    id = malloc(N*sizeof(int)); 
    sz = malloc(N*sizeof(int)); 
    for (i = 0; i < N; i++) 
      { id[i] = i; sz[i] = 1; }
  }
int find(int x)