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

-----
PQlink pair(PQlink p, PQlink q)
  { PQlink t;
    if (less(p->key, q->key)) 
         { p->r = q->l; q->l = p; return q; }
    else { q->r = p->l; p->l = q; return p; }
  }
-----
PQlink PQinsert(PQ pq, Item v)
  { int i;
    PQlink c, t = malloc(sizeof *t);
    c = t; c->l = z; c->r = z; c->key = v;
    for (i = 0; i < maxBQsize; i++)
      {
        if (c == z) break;
        if (pq->bq[i] == z) { pq->bq[i] = c; break; }
        c = pair(c, pq->bq[i]); pq->bq[i] = z;
      }
    return t;
  }
-----
Item PQdelmax(PQ pq)
  { int i, j, max; PQlink x; Item v; 
    PQlink temp[maxBQsize];
    for (i = 0, max = -1; i < maxBQsize; i++)
      if (pq->bq[i] != z) 
        if ((max == -1) || (pq->bq[i]->key > v))
          { max = i; v = pq->bq[max]->key; }
    x = pq->bq[max]->l; 
    for (i = max; i < maxBQsize; i++) temp[i] = z; 
    for (i = max ; i > 0; i--)
      { temp[i-1] = x; x = x->r; temp[i-1]->r = z; }
    free(pq->bq[max]); pq->bq[max] = z;
    BQjoin(pq->bq, temp);  
    return v;
  }      
-----
#define test(C, B, A) 4*(C) + 2*(B) + 1*(A)
void BQjoin(PQlink *a, PQlink *b)
  { int i; PQlink c = z;
    for (i = 0; i < maxBQsize; i++)
      switch(test(c != z, b[i] != z, a[i] != z))
        {
          case 2: a[i] = b[i]; break;
          case 3: c = pair(a[i], b[i]); 
                  a[i] = z; break;
          case 4: a[i] = c; c = z; break;
          case 5: c = pair(c, a[i]); 
                  a[i] = z; break;
          case 6: 
          case 7: c = pair(c, b[i]); break;
        }
  }
void PQjoin(PQ a, PQ b)
  { BQjoin(a->bq, b->bq); }

----------
CHAPTER 10. Radix Sorting
-----
quicksortB(int a[], int l, int r, int w)
  { int i = l, j = r;
    if (r <= l || w > bitsword) return;
    while (j != i)
      { 
        while (digit(a[i], w) == 0 && (i < j)) i++;
        while (digit(a[j], w) == 1 && (j > i)) j--;
        exch(a[i], a[j]);
      }
    if (digit(a[r], w) == 0) j++;
    quicksortB(a, l, j-1, w+1);
    quicksortB(a, j, r, w+1);
  }
void sort(Item a[], int l, int r)
  { 
    quicksortB(a, l, r, 0);
  }
-----
#define bin(A) l+count[A]
void radixMSD(Item a[], int l, int r, int w)
  { int i, j, count[R+1]; 
    if (w > 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], w) + 1]++;
    for (j = 1; j < R; j++) 
      count[j] += count[j-1];
    for (i = l; i <= r; i++) 
      aux[l+count[digit(a[i], w)]++] = a[i];
    for (i = l; i <= r; i++) a[i] = aux[i];
    radixMSD(a, l, bin(0)-1, w+1);
    for (j = 0; j < R-1; j++)
      radixMSD(a, bin(j), bin(j+1)-1, w+1);
  }
-----
#define ch(A) digit(A, D)
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); 
  }
-----
void radixLSD(Item a[], int l, int r)
  {
    int i, j, w, count[R+1]; 
    for (w = bytesword-1; w >= 0; w--)
      {
        for (j = 0; j < R; j++) count[j] = 0;
        for (i = l; i <= r; i++) 
          count[digit(a[i], w) + 1]++;
        for (j = 1; j < R; j++) 
          count[j] += count[j-1];
        for (i = l; i <= r; i++) 
          aux[count[digit(a[i], w)]++] = a[i];
        for (i = l; i <= r; i++) a[i] = aux[i];
      }
  } 

----------
CHAPTER 11. Special-Purpose Sorts
-----
shuffle(itemType a[], int l, int r)
  { int i, j, m = (l+r)/2;
    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];
  }
unshuffle(itemType a[], int l, int r)
  { int i, j, m = (l+r)/2;
    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];
  }
-----
mergeTD(itemType a[], int l, int r)
  { int i, m = (l+r)/2;
    if (r == l+1) compexch(a[l], a[r]);
    if (r < l+2) return;
    unshuffle(a, l, r);
    mergeTD(a, l, m); 
    mergeTD(a, m+1, r);
    shuffle(a, l, r);
    for (i = l+1; i < r; i+=2) 
      compexch(a[i], a[i+1]);
  }
-----
mergeBU(itemType a[], int l, int r)
  { int i, j, k, N = r-l+1;
    for (k = N/2; k > 0; k /= 2)
      for (j = k % (N/2); j+k < N; j += (k+k)) 
        for (i = 0; i < k; i++) 
          compexch(a[l+j+i], a[l+j+i+k]);
  }
-----
void batchersort(itemType a[], int l, int r)
  { int i, j, k, p, N = r-l+1;
    for (p = 1; p < N; p += p)
      for (k = p; k > 0; k /= 2)
        for (j = k%p; j+k < N; j += (k+k)) 
          for (i = 0; i < k; i++) 
            if (j+i+k < N) 
              if ((j+i)/(p+p) == (j+i+k)/(p+p)) 
                compexch(a[l+j+i], a[l+j+i+k]);
  }
-----
id = 1;
for (i = 1; i <= S; i++) a[i] = strGet(0);
while (a[1] < z)
  { 
    strPut(id, (c = a[1])); 
    if ((a[1] = strGet(0)) < c) mark(a[1]);
    fixDown(1, S);
    if (marked(a[1])) 
      { 
        for (i = 1; i <= S; i++) unmark(a[i]);
        strPut(id, z); 
        id = id % S + 1;
      }
  }
strPut(id, z); 
-----
void compexch(int x, int y)
  { int t; 
    t = stage[a[x]]; if (t < stage[a[y]]) t = stage[a[y]]; t++;
    stage[a[x]] = t; stage[a[y]] = t; 
    printf("%3d %3d %3d\n", t, a[x], a[y]);
  }

----------
CHAPTER 12. Symbol Tables and BSTs
-----
void STinit(int);
 int STcount();
void STinsert(Item);
Item STsearch(Key);
void STdelete(Item);
Item STselect(int);
void STsort(void (*visit)(Item));
-----
#include <stdio.h>
#include <stdlib.h>
#include "Item.h"
#include "ST.h"
void main(int argc, char *argv[])
 { int N, maxN = atoi(argv[1]), sw = atoi(argv[2]);
    Key v; Item item;
    STinit(maxN);
    for (N = 0; N < maxN; N++)
      {
        if (sw) v = ITEMrand();
          else if (ITEMscan(&v) == EOF) break;
        if (STsearch(v) != NULLitem) continue;
        key(item) = v;
        STinsert(item); 
      }
    STsort(ITEMshow); printf("\n");
    printf("%d keys ", N);
    printf("%d distinct keys\n", STcount());
 }
-----
static Item *st;
static int M = maxKey;
void STinit(int maxN) 
  { int i;
    st = malloc((M+1)*sizeof(Item));
    for (i = 0; i <= M; i++) st[i] = NULLitem; 
  }
int STcount() 
  { int i, N = 0;
    for (i = 0; i < M; i++) 
      if (st[i] != NULLitem) N++;
    return N;
  }
void STinsert(Item item)
  { st[key(item)] = item; }
Item STsearch(Key v)
  { return st[v]; }
void STdelete(Item item)
  { st[key(item)] = NULLitem; }
Item STselect(int k)
  { int i;
    for (i = 0; i < M; i++)
      if (st[i] != NULLitem) 
        if (k-- == 0) return st[i]; 
  }
void STsort(void (*visit)(Item))
  { int i;
    for (i = 0; i < M; i++)
      if (st[i] != NULLitem) visit(st[i]);
  }
-----
static Item *st;
static int N;
void STinit(int maxN) 
  { st = malloc((maxN)*sizeof(Item)); N = 0; }
int STcount() 
  { return N; }
void STinsert(Item item)
  { int j = N++; Key v = key(item);
    while (j>0 && less(v, key(st[j-1])))
      {  st[j] = st[j-1]; j--; }
    st[j] = item;
  }
Item STsearch(Key v)
  { int j;
    for (j = 0; j < N; j++)
      {
        if (eq(v, key(st[j]))) return st[j];
        if (less(v, key(st[j]))) break;
      }
    return NULLitem;
  }
Item STselect(int k)
  { return st[k]; }
void STsort(void (*visit)(Item))
  { int i;
    for (i = 0; i < N; i++) visit(st[i]); 
  }
-----
typedef struct STnode* link;
struct STnode { Item item; link next; };
static link head, z;
static int N;
static link NEW(Item item, link next)      
  { link x = malloc(sizeof *x);
    x->item = item; x->next = next;     
    return x;                         
  }                                   
void STinit(int max) 
  { N = 0; head = (z = NEW(NULLitem, NULL)); }
int STcount() { return N; }
Item searchR(link t, Key v)
  { 
    if (t == z) return NULLitem;
    if (eq(key(t->item), v)) return t->item;
    return searchR(t->next, v);
  }
Item STsearch(Key v)
  { return searchR(head, v); }
void STinsert(Item item)
  { head = NEW(item, head); N++; }
-----
Item search(int l, int r, Key v)
  { int m = (l+r)/2;
    if (l > r) return NULLitem;
    if eq(v, key(st[m])) return st[m];
    if (l == r) return NULLitem;
    if less(v, key(st[m])) 
         return search(l, m-1, v);
    else return search(m+1, r, v);
  }
Item STsearch(Key v)
  { return search(0, N-1, v); }
-----
#include <stdlib.h>
#include "Item.h"
typedef struct STnode* link;
struct STnode { Item item; link l, r; int N };
static link head, z;
link NEW(Item item, link l, link r, int N)
  { link x = malloc(sizeof *x); 
    x->item = item; x->l = l; x->r = r; x->N = N;
    return x;
  }
void STinit()
  { head = (z = NEW(NULLitem, 0, 0, 0)); }
int STcount() { return head->N; }
Item searchR(link h, Key v)
  { Key t = key(h->item);
    if (h == z) return NULLitem;
    if eq(v, t) return h->item;
    if less(v, t) return searchR(h->l, v);
             else return searchR(h->r, v);
  }
Item STsearch(Key v) 
  { return searchR(head, v); } 
link insertR(link h, Item item)
  { Key v = key(item), t = key(h->item);
    if (h == z) return NEW(item, z, z, 1);
    if less(v, t) 
         h->l = insertR(h->l, item);
    else h->r = insertR(h->r, item);
    (h->N)++; return h;
  }
void STinsert(Item item)
  { head = insertR(head, item); }
-----
void sortR(link h, void (*visit)(Item))
  { 
    if (h == z) return;
    sortR(h->l, visit);
    visit(h->item); 
    sortR(h->r, visit);
  }
void STsort(void (*visit)(Item))
  { sortR(head, visit); } 
-----
void STinsert(Item item)
  { Key v = key(item); link p = head, x = p;
    if (head == NULL) 
      { head = NEW(item, NULL, NULL, 1); return; }
    while (x != NULL)
      { 
        p = x; x->N++;
        x = less(v, key(x->item)) ? x->l : x->r; 
      }
    x = NEW(item, NULL, NULL, 1);
    if (less(v, key(p->item))) p->l = x; 
                          else p->r = x;
  }
-----
#define null(A) (eq(key(A), key(NULLitem)))
static char text[maxN];
main(int argc, char *argv[])
  { int i, t, N = 0; char query[maxQ]; char *v;
    FILE *corpus  = fopen(*++argv, "r");
    while ((t = getc(corpus)) != EOF) 
      if (N < maxN) text[N++] = t; else break;
    text[N] = '\0';
    STinit(maxN);
    for (i = 0; i < N; i++) STinsert(&text[i]);
    while (gets(query) != NULL)
      if (!null(v = STsearch(query)))
           printf("%11d %s\n", v-text, query); 
      else printf("(not found) %s\n", query);
  }
-----
link rotR(link h)
  { link x = h->l; h->l = x->r; x->r = h; 
    return x; }
link rotL(link h)
  { link x = h->r; h->r = x->l; x->l = h; 
    return x; }
-----
link insertT(link h, Item item)
  { Key v = key(item);
    if (h == z) return NEW(item, z, z, 1); 
    if (less(v, key(h->item))) 
      { h->l = insertT(h->l, item); h = rotR(h); }
    else
      { h->r = insertT(h->r, item); h = rotL(h); }
    return h;
  }
void STinsert(Item item)
  { head = insertT(head, item); }
-----
Item selectR(link h, int k)
  { int t = h->l->N;
    if (h == z) return NULLitem;
    if (t > k) return selectR(h->l, k);
    if (t < k) return selectR(h->r, k-t-1);
    return h->item;
  }
Item STselect(int k)
  { return selectR(head, k); } 
-----
link partR(link h, int k)
  { int t = h->l->N; 
    if (t > k )
      { h->l = partR(h->l, k); h = rotR(h); }
    if (t < k )
      { h->r = partR(h->r, k-t-1); h = rotL(h); }
    return h;
  }
-----
link joinLR(link a, link b)
  { 
    if (b == z) return a;
    b = partR(b, 0); b->l = a; 
    return b;
  }
link deleteR(link h, Key v)
  { link x; Key t = key(h->item);
    if (h == z) return z; 
    if (less(v, t)) h->l = deleteR(h->l, v);
    if (less(t, v)) h->r = deleteR(h->r, v);
    if (eq(v, t)) 
      { x = h; h = joinLR(h->l, h->r); free(x); }
    return h;
  }
void STdelete(Key v)
  { head = deleteR(head, v); }
-----
link STjoin(link a, link b)
  { 
    if (b == z) return a;
    if (a == z) return b;
    b = STinsert(b, a->item); 
    b->l = STjoin(a->l, b->l); 
    b->r = STjoin(a->r, b->r); 
    free(a);    
    return b;
  }
-----

----------
CHAPTER 13. Balanced Trees
-----
link balanceR(link h)
  { 
    if (h->N < 2) return h;
    h = partR(h, h->N/2);
    h->l = balanceR(h->l); 
    h->r = balanceR(h->r);
    return h;
  }
-----
link insertR(link h, Item item)
  { Key v = key(item), t = key(h->item);
    if (h == z) return NEW(item, z, z, 1);
    if (rand()< RAND_MAX/(h->N+1)) 
      return insertT(h, item);
    if less(v, t) h->l = insertR(h->l, item);
             else h->r = insertR(h->r, item);
    (h->N)++; return h;
  }
void STinsert(Item item)
  { head = insertR(head, item); }
-----
link STjoinR(link a, link b)
  { 
    if (a == z) return b;
    b = STinsert(b, a->rec); 
    b->l = STjoin(a->l, b->l); 
    b->r = STjoin(a->r, b->r); 
    fixN(b); free(a);
    return b;
  }
link STjoin(link a, link b)
  { 
    if (rand()/(RAND_MAX/(a->N+b->N)+1) < a->N)
         STjoinR(a, b);
    else STjoinR(b, a);
  }
-----
link joinLR(link a, link b)
  { 
    if (a == z) return b;
    if (b == z) return a;
    if (rand()/(RAND_MAX/(a->N+b->N)+1) < a->N)
         { a->r = joinLR(a->r, b); return a; }
    else { b->l = joinLR(a, b->l); return b; }
  }
-----