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

link splay(link h, Item item)
  { Key v = key(item);
    if (h == z) return NEW(item, z, z, 1);  
    if (less(v, key(h->item))) 
      { 
        if (hl == z) return NEW(item, z, h, h->N+1);
        if (less(v, key(hl->item))) 
          { hll = splay(hll, item); h = rotR(h); }
        else 
          { hlr = splay(hlr, item); hl = rotL(hl); }
        return rotR(h); 
      }
    else
      { 
        if (hr == z) return NEW(item, h, z, h->N+1);
        if (less(key(hr->item), v)) 
          { hrr = splay(hrr, item); h = rotL(h); }
        else 
          { hrl = splay(hrl, item); hr = rotR(hr); }
        return rotL(h);
      }
  }
void STinsert(Item item)
  { head = splay(head, item); }
-----
link RBinsert(link h, Item item, int sw)
  { Key v = key(item);
    if (h == z) return NEW(item, z, z, 1, 1);  
    if ((hl->red) && (hr->red)) 
      { h->red = 1; hl->red = 0; hr->red = 0; }
    if (less(v, key(h->item))) 
      { 
        hl = RBinsert(hl, item, 0); 
        if (h->red && hl->red && sw) h = rotR(h); 
        if (hl->red && hll->red) 
          { h = rotR(h); h->red = 0; hr->red = 1; }
      }
    else
      { 
        hr = RBinsert(hr, item, 1); 
        if (h->red && hr->red && !sw) h = rotL(h); 
        if (hr->red && hrr->red) 
          { h = rotL(h); h->red = 0; hl->red = 1; }
      }
    fixN(h); return h;
  }
void STinsert(Item item)
  { head = RBinsert(head, item, 0); head->red = 0; }
-----
Item searchR(link t, Key v, int k)
  { 
    if (eq(v, key(t->item))) return t->item;
    if (less(v, key(t->next[k]->item))) 
      { 
        if (k == 0) return NULLitem;
        return searchR(t, v, k-1); 
      }
    return searchR(t->next[k], v, k);
  }
Item STsearch(Key v)
  { return searchR(head, v, lgN); }
-----
typedef struct STnode* link;
struct STnode { Item item; link* next; int sz; };
static link head, z;
static int N, lgN;
link NEW(Item item, int k)      
  { int i; link x = malloc(sizeof *x);
    x->next = malloc(k*sizeof(link));
    x->item = item; x->sz = k;
    for (i = 0; i < k; i++) x->next[i] = z;
    return x;                         
  }                                   
void STinit(int max) 
  { 
    N = 0; lgN = 0; 
    z = NEW(NULLitem, 0); 
    head = NEW(NULLitem, lgNmax); 
  }
-----
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 = key(x->item); 
    if (less(v, key(t->next[k]->item))) 
      { 
        if (k < x->sz)
          { x->next[k] = t->next[k]; 
            t->next[k] = x; }
        if (k == 0) return;
        insertR(t, x, k-1); return;
      }
    insertR(t->next[k], x, k);
  }
void STinsert(Key v)
  { insertR(head, NEW(v, randX()), lgN); N++; }
-----
void deleteR(link t, Key v, int k)
  { link x = t->next[k];
    if (!less(key(x->item), v)) 
      { 
        if (eq(v, key(x->item)))
          { t->next[k] = x->next[k]; }
        if (k == 0) { free(x); return; }
        deleteR(t, v, k-1); return;
      }
    deleteR(t->next[k], v, k);
  }
void STdelete(Key v)
  { deleteR(head, v, lgN); N--; }

----------
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;
  }
-----
static link *heads, z;
static int N, M;
void STinit(int max) 
  { int i;
    N = 0; M = max/5;
    heads = malloc(M*sizeof(link));
    z = NEW(NULLitem, NULL);
    for (i = 0; i < M; i++) heads[i] = z; 
  }
Item STsearch(Key v)
  { return searchR(heads[hash(v, M)], v); }
void STinsert(Item item)
  { int i = hash(key(item), M);
    heads[i] = NEW(item, heads[i]); N++; }
void STdelete(Item item)
  { int i = hash(key(item), M);
    heads[i] = deleteR(heads[i], item); }
-----
#include <stdlib.h>
#include "Item.h"
#define null(A) (key(st[A]) == key(NULLitem))
static int N, M;
static Item *st;
void STinit(int max)
  { int i; 
    N = 0; M = 2*max;
    st = malloc(M*sizeof(Item));
    for (i = 0; i < M; i++) st[i] = NULLitem; 
  }
int STcount() { return N; }
void STinsert(Item item)
  { Key v = key(item);
    int i = hash(v, M);
    while (!null(i)) i = (i+1) % M;
    st[i] = item; N++;
  }
Item STsearch(Key v)
  { int i = hash(v, M);
    while (!null(i))
      if eq(v, key(st[i])) return st[i]; 
      else i = (i+1) % M;
    return NULLitem;
  }
-----
void STdelete(Item item)
  { int j, i = hash(key(item), M); Item v;
    while (!null(i))
      if eq(key(item), key(st[i])) break; 
      else i = (i+1) % M;
    if (null(i)) return;
    st[i] = NULLitem; N--;
    for (j = i+1; !null(j); j = (j+1) % M, N--)
      { v = st[j]; st[j] = NULLitem; STinsert(v); }
  }
-----
void STinsert(Item item)
  { Key v = key(item);
    int i = hash(v, M);
    int k = hashtwo(v, M);
    while (!null(i)) i = (i+k) % M;
    st[i] = item; N++;
  }
Item STsearch(Key v)
  { int i = hash(v, M);
    int k = hashtwo(v, M);
    while (!null(i))
      if eq(v, key(st[i])) return st[i]; 
      else i = (i+k) % M;
    return NULLitem;
  }
-----
void expand();
void STinsert(Item item)
  { Key v = key(item);
    int i = hash(v, M);
    while (!null(i)) i = (i+1) % M;
    st[i] = item; 
    if (N++ > M/2) expand();
  }
void expand()
  { int i; Item *t = st;
    init(M+M);
    for (i = 0; i < M/2; i++) 
      if (key(t[i]) != key(NULLitem)) 
        STinsert(t[i]); 
    free(t);
  }

----------
CHAPTER 15. Radix Search
-----
Item searchR(link h, Key v, int w)
  { Key t = key(h->item);
    if (h == z) return NULLitem;
    if eq(v, t) return h->item;
    if (digit(v, w) == 0)
         return searchR(h->l, v, w+1);
    else return searchR(h->r, v, w+1);
  }
Item STsearch(Key v) 
  { return searchR(head, v, 0); } 
-----
#define leaf(A) ((h->l == z) && (h->r == z))
Item searchR(link h, Key v, int w)
  { Key t = key(h->item);
    if (h == z) return NULLitem;
    if (leaf(h))
      return eq(v, t) ? h->item : NULLitem;
    if (digit(v, w) == 0)
         return searchR(h->l, v, w+1);
    else return searchR(h->r, v, w+1);
  }
Item STsearch(Key v) 
  { return searchR(head, v, 0); } 
-----
void STinit()
  { head = (z = NEW(NULLitem, 0, 0, 0)); }
link split(link p, link q, int w)
  { link t = NEW(NULLitem, z, z, 2);
    switch(digit(p->item, w)*2 + digit(q->item, w))
      {
        case 0: t->l = split(p, q, w+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, w+1); break;
      }
    return t;
  }
link insertR(link h, Item item, int w)
  { Key v = key(item), t = key(h->item);
    if (h == z) return NEW(item, z, z, 1);
    if (leaf(h))
      { return split(NEW(item, z, z, 1), h, w); }
    if (digit(v, w) == 0)
         h->l = insertR(h->l, item, w+1);
    else h->r = insertR(h->r, item, w+1);
    return h;
  }
void STinsert(Item item)
  { head = insertR(head, item, 0); }
-----
Item searchR(link h, Key v, int w)
  { 
    if (h->bit <= w) return h->item;
    if (digit(v, h->bit) == 0)
         return searchR(h->l, v, h->bit);
    else return searchR(h->r, v, h->bit);
  }
Item STsearch(Key v) 
  { Item t = searchR(head->l, v, -1); 
    return eq(v, key(t)) ? t : NULLitem; 
  } 
-----
void STinit()
  { head = NEW(NULLitem, 0, 0, -1); 
    head->l = head; head->r = head; }
link insertR(link h, Item item, int w, link p)
  { link x; Key v = key(item);
    if ((h->bit >= w) || (h->bit <= p->bit))
      { 
        x = NEW(item, 0, 0, w);
        x->l = digit(v, x->bit) ? h : x;
        x->r = digit(v, x->bit) ? x : h;
        return x; 
      }
    if (digit(v, h->bit) == 0)
         h->l = insertR(h->l, item, w, h);
    else h->r = insertR(h->r, item, w, h);
    return h;
  }
void STinsert(Item item)
  { int i;
    Key v = key(item); 
    Key t = key(searchR(head->l, v, -1));
    if (v == t) return;
    for (i = 0; digit(v, i) == digit(t, i); i++) ;
    head->l = insertR(head->l, item, i, head);
  }
-----
void sortR(link h, void (*visit)(Item), int w)
  { 
    if (h->bit <= w) { visit(h->item); return; }
    sortR(h->l, visit, h->bit);
    sortR(h->r, visit, h->bit);
  }
void STsort(void (*visit)(Item))
  { sortR(head->l, visit, -1); } 
-----
typedef struct STnode *link;
struct STnode { link next[R]; };
static link head;
void STinit() { head = NULL; }
link NEW()
  { int i;
    link x = malloc(sizeof *x); 
    for (i = 0; i < R; i++) x->next[i] = NULL;
    return x;
  }
Item searchR(link h, Key v, int w)
  { int i = digit(v, w);
    if (h == NULL) return NULLitem;
    if (i == NULLdigit) return v;
    return searchR(h->next[i], v, w+1);
  }
Item STsearch(Key v) 
  { return searchR(head, v, 0); } 
link insertR(link h, Item item, int w)
  { Key v = key(item);
    int i = digit(v, w);
    if (h == NULL) h = NEW();
    if (i == NULLdigit) return h;
    h->next[i] = insertR(h->next[i], v, w+1);
    return h;
  }
void STinsert(Item item)
  { head = insertR(head, item, 0); N++; }
-----
typedef struct STnode* link;
struct STnode { Item item; int d; link l, m, r; };
static link head;
void STinit() { head = NULL; }
link NEW(int d)
  { link x = malloc(sizeof *x); 
    x->d = d; x->l = NULL; x->m = NULL; x->r = NULL;
    return x;
  }
Item searchR(link h, Key v, int w)
  { int i = digit(v, w);
    if (h == NULL) return NULLitem; 
    if (i == NULLdigit) return v;
    if (i < h->d) return searchR(h->l, v, w);
    if (i == h->d) return searchR(h->m, v, w+1);
    if (i > h->d) return searchR(h->r, v, w);
  }
Item STsearch( Key v)
  { return searchR(head, v, 0); }
link insertR(link h, Item item, int w)
  { Key v = key(item);
    int i = digit(v, w);
    if (h == NULL) h = NEW(i); 
    if (i == NULLdigit) return h;
    if (i < h->d) h->l = insertR(h->l, v, w);
    if (i == h->d) h->m = insertR(h->m, v, w+1);
    if (i > h->d) h->r = insertR(h->r, v, w);
    return h;
  }
void STinsert(Key key)
  { head = insertR(head, key, 0); }
-----
char word[maxW];
void matchR(link h, char *v, int i)
  { 
    if (h == z) return; 
    if ((*v == '\0') && (h->d == '\0')) 
      { word[i] = h->d; printf("%s ", word); }
    if ((*v == '*') || (*v == h->d)) 
      { word[i] = h->d; matchR(h->m, v+1, i+1); }
    if ((*v == '*') || (*v < h->d)) 
      matchR(h->l, v, i);
    if ((*v == '*') || (*v > h->d)) 
      matchR(h->r, v, i);
  }
void STmatch(char *v)
  { matchR(head, v, 0); }
-----
#define internal(A) ((A->d) != NULLdigit)
link NEWx(link h, int d)
  { link x = malloc(sizeof *x); 
    x->item = NULLitem; x->d = d;
    x->l = NULL; x->m = h; x->r = NULL;
    return x;
  }
link split(link p, link q, int w)
  { int pd = digit(p->item, w), 
        qd = digit(q->item, w);
    link t = NEW(NULLitem, qd);
    if (pd < qd) { t->m = q; t->l = NEWx(p, pd); }
    if (pd == qd) { t->m = split(p, q, w+1); }
    if (pd > qd) { t->m = q; t->r = NEWx(p, pd); }
    return t;
  }
link insertR(link h, Item item, int w)
  { Key v = key(item);
    int i = digit(v, w);
    if (h == NULL) 
      return NEWx(NEW(item, NULLdigit), i);
    if (!internal(h))
      return split(NEW(item, NULLdigit), h, w); 
    if (i < h->d) h->l = insertR(h->l, v, w);
    if (i == h->d) h->m = insertR(h->m, v, w+1);
    if (i > h->d) h->r = insertR(h->r, v, w);
    return h;
  }
void STinsert(Key key)
  { int i = digit(key, 0);
    heads[i] = insertR(heads[i], key, 1); 
  }
-----
Item searchR(link h, Key v, int w)
  { int i = digit(v, w);
    if (h == NULL) return NULLitem; 
    if (internal(h))
      {
        if (i < h->d) return searchR(h->l, v, w);
        if (i == h->d) return searchR(h->m, v, w+1);
        if (i > h->d) return searchR(h->r, v, w);
      }
    if eq(v, key(h->item)) return h->item;
    return NULLitem;
  }
Item STsearch(Key v)
  { return searchR(heads[digit(v, 0)], v, 1); }
-----
typedef struct STnode* link;
struct STnode { Item item; link l, m, r; };
static link head;
#define z NULL
void STinit() { head = z; }
link NEW(char *v)
  { link x = malloc(sizeof *x); 
    x->item = v; x->l = z; x->m = z; x->r = z;
    return x;
  }
Item searchR(link h, char *v)
  { char *t;
    if (h == z) return NULLitem; 
    if (*v == '\0') return h->item;
    if (*v < *(h->item)) searchR(h->l, v);
    if (*v > *(h->item)) searchR(h->r, v);
    if (*v == *(h->item)) t = searchR(h->m, v+1);
    return null(t) ? t : v;
  }
Item STsearch(char *v)
  { char *t = searchR(head, v); 
    if (eq(v, t)) return t;
    return NULLitem;
  }
link insertR(link h, char *v)
  { 
    if (h == z) h = NEW(v); 
    if ((*v ==  *(h->item)) && (*v != '\0'))
      h->m = insertR(h->m, v+1);
    if (h == z) h = NEW(v); 
    if (*v < *(h->item)) h->l = insertR(h->l, v);
    if (*v > *(h->item)) h->r = insertR(h->r, v);
    return h;
  }
void STinsert(char *v)
  { head = insertR(head, v); }

----------
CHAPTER 16. External Searching
-----
typedef struct STnode* link;
typedef struct
  { Key key; union { link next; Item item; } ref; } 
entry;
struct STnode { entry b[M]; int m; };
static link head;
static int H, N; 
link NEW()
  { link x = malloc(sizeof *x); 
    x->m = 0;
    return x; 
  }
void STinit(int maxN) 
  { head = NEW(); H = 0; N = 0; }
-----
Item searchR(link h, Key v, int H)
  { int j;
    if (H == 0)
      for (j = 0; j < h->m; j++)
        if (eq(v, h->b[j].key)) 
          return h->b[j].ref.item;
    if (H != 0)
      for (j = 0; j < h->m; j++)
        if ((j+1 == h->m) || less(v, h->b[j+1].key))
          return searchR(h->b[j].ref.next, v, H-1);
    return NULLitem;
  }
Item STsearch(Key v)
  { return searchR(head, v, H); }
-----
link insertR(link h, Item item, int H)
  { int i, j; Key v = key(item); entry x; link u;
    x.key = v; x.ref.item = item;
    if (H == 0)
      for (j = 0