ch01-binary-10m.c

/* code: ch01-binary-10m.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define PRN  0
#define ARRAY_SIZE 10000000

/* ------------------------------------------ */
int int_compare (const void *va, const void *vb) {
  int a, b;
  a = *(int *) va;
  b = *(int *) vb;
  if (a < b) {
    return (-1);
  }
  else if (a > b) {
    return (1);
  }
  else {
    return (0);
  }
}

/* ------------------------------------------ */
void shuffle (int *v, int n) {
  int i, j, t;
  for (i = 0; i < n; i++) {
    j = rand () % n;
    t = v[i];
    v[i] = v[j];
    v[j] = t;
  }
}

/* ------------------------------------------ */
void rand_nd (int *v, int n) {
  int i;
  for (i = 0; i < n; i++) {
    v[i] = i;
  }
  shuffle (v, n);
}


/* ------------------------------------------- */
int linear_search (int array[], int n, int key) {
  int i;
  for (i = 0; i < n; i++) {
    if (array[i] == key) {
      return i;
    }
  }
  return -1;
}


/* ------------------------------------------- */
int binary_search (int array[], int num, int key) {
  int middle, low, high;
  low = 0;
  high = num - 1;
  while (low <= high) {
    middle = (low + high) / 2;
    if (key == array[middle]) {
      return middle;
    }
    else if (key < array[middle]) {
      high = middle - 1;
    }
    else {
      low = middle + 1;
    }
  }
  return -1;
}

/* ------------------------------------------- */
void print_array (int array[], int n) {
  int i;
  for (i = 0; i < n; i++) {
    printf ("%d ", array[i]);
  }
  printf ("\n");
  fflush (stdout);
}

/* ------------------------------------------- */
int main () {
  int index, key, i, df, dn;
  int *array;
  clock_t t0_start, t0_end, t1_start, t1_end;

  array = malloc (sizeof (int) * ARRAY_SIZE);

  rand_nd (array, ARRAY_SIZE);


  t0_start = clock ();
  qsort (array, ARRAY_SIZE, sizeof (int), int_compare);
  t0_end = clock ();

  print_array (array, 10);
  printf ("\n");
  printf ("qsort (%d): %.3lf sec.\n", ARRAY_SIZE,
	  (double) (t0_end - t0_start) / (double) CLOCKS_PER_SEC);
  printf ("\n");

  printf ("binary search (%d)  ", ARRAY_SIZE);
  fflush (stdout);

  df = 0;
  dn = 0;
  t1_start = clock ();
  for (i = 0; i < ARRAY_SIZE; i++) {

    key = rand () % (ARRAY_SIZE * 2);
    index = binary_search (array, ARRAY_SIZE, key);


    if (index != -1) {
      if (PRN)
	printf ("Found: %d (index:%d)\n", key, index);
      df++;
    }
    else {
      if (PRN)
	printf ("Not found: %d\n", key);
      dn++;
    }
    if (!(i % (ARRAY_SIZE / 10))) {
      printf ("*");
      fflush (stdout);
    }
  }
  t1_end = clock ();



  printf ("\n");
  printf ("found: %d   not_found: %d\n", df, dn);
  printf ("time: %.3lf sec.\n",
	  (double) (t1_end - t1_start) / (double) CLOCKS_PER_SEC);

  free (array);
  return 0;
}

ch01-binary.c

/* code: ch01-binary.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define PRN  0
#define ARRAY_SIZE 300000

/* ------------------------------------------ */
int int_compare (const void *va, const void *vb) {
  int a, b;
  a = *(int *) va;
  b = *(int *) vb;
  if (a < b) {
    return (-1);
  }
  else if (a > b) {
    return (1);
  }
  else {
    return (0);
  }
}

/* ------------------------------------------ */
void shuffle (int *v, int n) {
  int i, j, t;
  for (i = 0; i < n; i++) {
    j = rand () % n;
    t = v[i];
    v[i] = v[j];
    v[j] = t;
  }
}

/* ------------------------------------------ */
void rand_nd (int *v, int n) {
  int i;
  for (i = 0; i < n; i++) {
    v[i] = i;
  }
  shuffle (v, n);
}


/* ------------------------------------------- */
int linear_search (int array[], int n, int key) {
  int i;
  for (i = 0; i < n; i++) {
    if (array[i] == key) {
      return i;
    }
  }
  return -1;
}


/* ------------------------------------------- */
int binary_search (int array[], int num, int key) {
  int middle, low, high;
  low = 0;
  high = num - 1;
  while (low <= high) {
    middle = (low + high) / 2;
    if (key == array[middle]) {
      return middle;
    }
    else if (key < array[middle]) {
      high = middle - 1;
    }
    else {
      low = middle + 1;
    }
  }
  return -1;
}

/* ------------------------------------------- */
void print_array (int array[], int n) {
  int i;
  for (i = 0; i < n; i++) {
    printf ("%d ", array[i]);
  }
  printf ("\n");
  fflush (stdout);
}

/* ------------------------------------------- */
int main () {
  int index, key, i, df, dn;
  int *array;
  clock_t t0_start, t0_end, t1_start, t1_end;

  array = malloc (sizeof (int) * ARRAY_SIZE);

  rand_nd (array, ARRAY_SIZE);


  t0_start = clock ();
  qsort (array, ARRAY_SIZE, sizeof (int), int_compare);
  t0_end = clock ();

  print_array (array, 10);
  printf ("\n");
  printf ("qsort (%d): %.3lf sec.\n", ARRAY_SIZE,
	  (double) (t0_end - t0_start) / (double) CLOCKS_PER_SEC);
  printf ("\n");

  printf ("binary search (%d)  ", ARRAY_SIZE);
  fflush (stdout);

  df = 0;
  dn = 0;
  t1_start = clock ();
  for (i = 0; i < ARRAY_SIZE; i++) {

    key = rand () % (ARRAY_SIZE * 2);
    index = binary_search (array, ARRAY_SIZE, key);


    if (index != -1) {
      if (PRN)
	printf ("Found: %d (index:%d)\n", key, index);
      df++;
    }
    else {
      if (PRN)
	printf ("Not found: %d\n", key);
      dn++;
    }
    if (!(i % (ARRAY_SIZE / 10))) {
      printf ("*");
      fflush (stdout);
    }
  }
  t1_end = clock ();



  printf ("\n");
  printf ("found: %d   not_found: %d\n", df, dn);
  printf ("time: %.3lf sec.\n",
	  (double) (t1_end - t1_start) / (double) CLOCKS_PER_SEC);

  free (array);
  return 0;
}

ch01-linear.c

/* code: ch01-linear.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define PRN  0
#define ARRAY_SIZE 300000


/* ------------------------------------------ */
int int_compare (const void *va, const void *vb) {
  int a, b;
  a = *(int *) va;
  b = *(int *) vb;
  if (a < b) {
    return (-1);
  }
  else if (a > b) {
    return (1);
  }
  else {
    return (0);
  }
}

/* ------------------------------------------ */
void shuffle (int *v, int n) {
  int i, j, t;
  for (i = 0; i < n; i++) {
    j = rand () % n;
    t = v[i];
    v[i] = v[j];
    v[j] = t;
  }
}

/* ------------------------------------------ */
void rand_nd (int *v, int n) {
  int i;
  for (i = 0; i < n; i++) {
    v[i] = i;
  }
  shuffle (v, n);
}


/* ------------------------------------------- */
int linear_search (int array[], int n, int key) {
  int i;
  for (i = 0; i < n; i++) {
    if (array[i] == key) {
      return i;
    }
  }
  return -1;
}


/* ------------------------------------------- */
int binary_search (int array[], int num, int key) {
  int middle, low, high;
  low = 0;
  high = num - 1;
  while (low <= high) {
    middle = (low + high) / 2;
    if (key == array[middle]) {
      return middle;
    }
    else if (key < array[middle]) {
      high = middle - 1;
    }
    else {
      low = middle + 1;
    }
  }
  return -1;
}

/* ------------------------------------------- */
void print_array (int array[], int n) {
  int i;
  for (i = 0; i < n; i++) {
    printf ("%d ", array[i]);
  }
  printf ("\n");
  fflush (stdout);
}

/* ------------------------------------------- */
int main () {
  int index, key, i, df, dn;
  int *array;
  clock_t t1_start, t1_end;

  array = malloc (sizeof (int) * ARRAY_SIZE);

  rand_nd (array, ARRAY_SIZE);

  print_array (array, 10);

  printf ("\n");
  printf ("linear search (%d)  ", ARRAY_SIZE);
  fflush (stdout);

  df = 0;
  dn = 0;
  t1_start = clock ();
  for (i = 0; i < ARRAY_SIZE; i++) {

    key = rand () % (ARRAY_SIZE * 2);
    index = linear_search (array, ARRAY_SIZE, key);


    if (index != -1) {
      if (PRN)
	printf ("Found: %d (index:%d)\n", key, index);
      df++;
    }
    else {
      if (PRN)
	printf ("Not found: %d\n", key);
      dn++;
    }
    if (!(i % (ARRAY_SIZE / 10))) {
      printf ("*");
      fflush (stdout);
    }
  }
  t1_end = clock ();

  printf ("\n");
  printf ("found: %d   not_found: %d\n", df, dn);
  printf ("time: %.3lf sec.\n",
	  (double) (t1_end - t1_start) / (double) CLOCKS_PER_SEC);


  free (array);
  return 0;
}

ch02-stack-l.c

/* code: ch02-stack-l.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>

#define DATA_SIZE   100000000
#define MAX         100000000

#define PUSH_SUCCESS    1
#define PUSH_FAILURE   -1
#define POP_SUCCESS     2
#define POP_FAILURE    -2

/* ------------------------------------------- */
void stack_init (int *top) {
  *top = 0;
}

/* ------------------------------------------- */
void display (int stack[], int top) {
  int i;
  printf ("STACK(%d): ", top);
  for (i = 0; i < top; i++) {
    printf ("%d ", stack[i]);
  }
  printf ("\n");
}

/* ------------------------------------------- */
int push (int stack[], int *top, int data) {
  if (*top >= MAX) {
    /* stack overflow */
    return PUSH_FAILURE;
  }
  else {
    stack[*top] = data;
    (*top)++;
    return PUSH_SUCCESS;
  }
}

/* ------------------------------------------- */
int pop (int stack[], int *top, int *data) {
  if ((*top) > 0) {
    *data = stack[(*top) - 1];
    (*top)--;
    return POP_SUCCESS;
  }
  else {
    /* stack empty */
    return POP_FAILURE;
  }
}




/* ------------------------------------------- */
int main () {
  int *stack;
  int top, data, i;

  stack = malloc (sizeof (int) * MAX);
  printf ("data size: %d\n", DATA_SIZE);
  stack_init (&top);

  printf ("push:\n");
  for (i = 0; i < DATA_SIZE; i++) {
    data = rand () % 1000;
    if (i >= DATA_SIZE - 5)
      printf ("%3d (index:%d)\n", data, top);
    push (stack, &top, data);
  }
  printf ("\n");

  printf ("pop:\n");
  for (i = 0; i < DATA_SIZE; i++) {
    pop (stack, &top, &data);
    if (i < 5)
      printf ("%3d (index:%d)\n", data, top);
  }
  printf ("\n");

  free (stack);

  return 0;
}

ch02-stack-rand-a.c

/* code: ch02-stack-rand-a.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>

#define DATA_SIZE   30
#define MAX         30

#define PUSH_SUCCESS    1
#define PUSH_FAILURE   -1
#define POP_SUCCESS     2
#define POP_FAILURE    -2

/* ------------------------------------------- */
void stack_init (int *top) {
  *top = 0;
}

/* ------------------------------------------- */
void display (int stack[], int top) {
  int i;
  printf ("STACK(%2d): ", top);
  for (i = 0; i < top; i++) {
    printf ("%d ", stack[i]);
  }
  printf ("\n");
}

/* ------------------------------------------- */
int push (int stack[], int *top, int data) {
  if (*top >= MAX) {
    /* stack overflow */
    return PUSH_FAILURE;
  }
  else {
    stack[*top] = data;
    (*top)++;
    return PUSH_SUCCESS;
  }
}

/* ------------------------------------------- */
int pop (int stack[], int *top, int *data) {
  if ((*top) > 0) {
    *data = stack[(*top) - 1];
    (*top)--;
    return POP_SUCCESS;
  }
  else {
    /* stack empty */
    return POP_FAILURE;
  }
}




/* ------------------------------------------- */
int main () {
  int *stack;
  int top, data, i;

  stack = malloc (sizeof (int) * MAX);
  printf ("data size: %d\n", DATA_SIZE);
  stack_init (&top);

  for (i = 0; i < DATA_SIZE; i++) {
    data = rand () % 1000;
    if (data > 500) {
      push (stack, &top, data);
    }
    else {
      pop (stack, &top, &data);
    }
    display (stack, top);
  }
  printf ("\n");

  free (stack);

  return 0;
}

ch02-stack-rand-b.c

/* code: ch02-stack-rand-b.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>

#define DATA_SIZE   30
#define MAX         30

#define PUSH_SUCCESS    1
#define PUSH_FAILURE   -1
#define POP_SUCCESS     2
#define POP_FAILURE    -2

/* ------------------------------------------- */
void stack_init (int *top) {
  *top = 0;
}

/* ------------------------------------------- */
void display (int stack[], int top) {
  int i;
  printf ("STACK(%2d): ", top);
  for (i = 0; i < top; i++) {
    printf ("%d ", stack[i]);
  }
  printf ("\n");
}

/* ------------------------------------------- */
int push (int stack[], int *top, int data) {
  if (*top >= MAX) {
    /* stack overflow */
    return PUSH_FAILURE;
  }
  else {
    stack[*top] = data;
    (*top)++;
    return PUSH_SUCCESS;
  }
}

/* ------------------------------------------- */
int pop (int stack[], int *top, int *data) {
  if ((*top) > 0) {
    *data = stack[(*top) - 1];
    (*top)--;
    return POP_SUCCESS;
  }
  else {
    /* stack empty */
    return POP_FAILURE;
  }
}




/* ------------------------------------------- */
int main () {
  int *stack;
  int top, data, i;

  stack = malloc (sizeof (int) * MAX);
  printf ("data size: %d\n", DATA_SIZE);
  stack_init (&top);

  for (i = 0; i < DATA_SIZE; i++) {
    data = rand () % 1000;
    if (data > 300) {
      push (stack, &top, data);
    }
    else {
      pop (stack, &top, &data);
    }
    display (stack, top);
  }
  printf ("\n");

  free (stack);

  return 0;
}

ch02-stack-rpn-b.c

/* code: ch02-stack-rpn-b.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define MAX           1024

#define PUSH_SUCCESS    1
#define PUSH_FAILURE   -1
#define POP_SUCCESS     2
#define POP_FAILURE    -2
/* ------------------------------------------- */
void stack_init (int *top) {
  *top = 0;
}


/* ------------------------------------------- */
int push (int stack[], int *top, int data) {
  if (*top >= MAX) {
    /* stack overflodelim */
    return PUSH_FAILURE;
  }
  else {
    stack[*top] = data;
    (*top)++;
    return PUSH_SUCCESS;
  }
}

/* ------------------------------------------- */
int pop (int stack[], int *top, int *data) {
  if ((*top) > 0) {
    *data = stack[(*top) - 1];
    (*top)--;
    return POP_SUCCESS;
  }
  else {
    /* stack empty */
    return POP_FAILURE;
  }
}

/* ------------------------------------------- */
int rpn (char *str) {
  int stack[MAX];
  int top, i;
  int a, b;
  char *endptr;
  char *delim = " \n\t\r\f";

  a = b = 0;
  stack_init (&top);

  for (str = strtok (str, delim); str; str = strtok (0, delim)) {
    a = (int) strtod (str, &endptr);
    if (endptr > str) {
      printf ("n: ");
      push (stack, &top, a);
    }
    else if (*str == '+') {
      printf ("%c: ", *str);
      pop (stack, &top, &b);
      pop (stack, &top, &a);
      push (stack, &top, (a + b));
    }
    else if (*str == '-') {
      printf ("%c: ", *str);
      pop (stack, &top, &b);
      pop (stack, &top, &a);
      push (stack, &top, (a - b));
    }
    else if (*str == '*') {
      printf ("%c: ", *str);
      pop (stack, &top, &b);
      pop (stack, &top, &a);
      push (stack, &top, (a * b));
    }
    else if (*str == '/') {
      printf ("%c: ", *str);
      pop (stack, &top, &b);
      pop (stack, &top, &a);
      push (stack, &top, (a / b));
    }
    else {
      fprintf (stderr, "[%c]: ", *str);
      fprintf (stderr, "unknown oeprators\n");
    }

    for (i = 0; i < top; i++) {
      printf (" %d", stack[i]);
    }
    printf ("\n");
  }

  if (top != 1) {
    fprintf (stderr, "stack error\n");
    exit (-1);
  }

  pop (stack, &top, &a);
  return a;
}


/* ------------------------------------------- */
int main () {
  int result;

  //    ( 50 + 30 ) * 100 / 20 - 300 * 2 + 300
  char rpn_str[] = " 50 30 + 100 * 20 / 300 2 * - 300 + ";

  printf ("RPN expression: %s\n\n", rpn_str);
  result = rpn (rpn_str);
  printf ("\n");
  printf ("result: %d\n", result);
  return 0;
}

ch02-stack-rpn.c

/* code: ch02-stack-rpn.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define MAX           1024

#define PUSH_SUCCESS    1
#define PUSH_FAILURE   -1
#define POP_SUCCESS     2
#define POP_FAILURE    -2
/* ------------------------------------------- */
void stack_init (int *top) {
  *top = 0;
}


/* ------------------------------------------- */
int push (int stack[], int *top, int data) {
  if (*top >= MAX) {
    /* stack overflodelim */
    return PUSH_FAILURE;
  }
  else {
    stack[*top] = data;
    (*top)++;
    return PUSH_SUCCESS;
  }
}

/* ------------------------------------------- */
int pop (int stack[], int *top, int *data) {
  if ((*top) > 0) {
    *data = stack[(*top) - 1];
    (*top)--;
    return POP_SUCCESS;
  }
  else {
    /* stack empty */
    return POP_FAILURE;
  }
}

/* ------------------------------------------- */
int rpn (char *str) {
  int stack[MAX];
  int top, i;
  int a, b;
  char *endptr;
  char *delim = " \n\t\r\f";

  a = b = 0;
  stack_init (&top);

  for (str = strtok (str, delim); str; str = strtok (0, delim)) {
    a = (int) strtod (str, &endptr);
    if (endptr > str) {
      printf ("n: ");
      push (stack, &top, a);
    }
    else if (*str == '+') {
      printf ("%c: ", *str);
      pop (stack, &top, &b);
      pop (stack, &top, &a);
      push (stack, &top, (a + b));
    }
    else if (*str == '-') {
      printf ("%c: ", *str);
      pop (stack, &top, &b);
      pop (stack, &top, &a);
      push (stack, &top, (a - b));
    }
    else if (*str == '*') {
      printf ("%c: ", *str);
      pop (stack, &top, &b);
      pop (stack, &top, &a);
      push (stack, &top, (a * b));
    }
    else if (*str == '/') {
      printf ("%c: ", *str);
      pop (stack, &top, &b);
      pop (stack, &top, &a);
      push (stack, &top, (a / b));
    }
    else {
      fprintf (stderr, "[%c]: ", *str);
      fprintf (stderr, "unknown oeprators\n");
    }

    for (i = 0; i < top; i++) {
      printf (" %d", stack[i]);
    }
    printf ("\n");
  }

  if (top != 1) {
    fprintf (stderr, "stack error\n");
    exit (-1);
  }

  pop (stack, &top, &a);
  return a;
}


/* ------------------------------------------- */
int main () {
  int result;
  char rpn_str[] = " 3 6 + 1 2 + / ";

  printf ("RPN expression: %s\n\n", rpn_str);
  result = rpn (rpn_str);
  printf ("\n");
  printf ("result: %d\n", result);
  return 0;
}

ch02-stack-s.c

/* code: ch02-stack-s.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>

#define MAX 128
#define PUSH_SUCCESS    1
#define PUSH_FAILURE   -1
#define POP_SUCCESS     2
#define POP_FAILURE    -2

/* ------------------------------------------- */
void stack_init (int *top) {
  *top = 0;
}

/* ------------------------------------------- */
void display (int stack[], int top) {
  int i;
  printf ("STACK(%d): ", top);
  for (i = 0; i < top; i++) {
    printf ("%d ", stack[i]);
  }
  printf ("\n");
}

/* ------------------------------------------- */
int push (int stack[], int *top, int data) {
  if (*top >= MAX) {
    /* stack overflow */
    return PUSH_FAILURE;
  }
  else {
    stack[*top] = data;
    (*top)++;
    return PUSH_SUCCESS;
  }
}

/* ------------------------------------------- */
int pop (int stack[], int *top, int *data) {
  if ((*top) > 0) {
    *data = stack[(*top) - 1];
    (*top)--;
    return POP_SUCCESS;
  }
  else {
    /* stack empty */
    return POP_FAILURE;
  }
}

/* ------------------------------------------- */
int main () {
  int stack[MAX];
  int top, data;

  stack_init (&top);
  data = 300;
  printf ("push: %d\n", data);
  push (stack, &top, data);
  data = 400;
  printf ("push: %d\n", data);
  push (stack, &top, data);
  data = 500;
  printf ("push: %d\n", data);
  push (stack, &top, data);
  display (stack, top);
  pop (stack, &top, &data);
  printf ("pop:  %d\n", data);
  pop (stack, &top, &data);
  printf ("pop:  %d\n", data);
  pop (stack, &top, &data);
  printf ("pop:  %d\n", data);
  return 0;
}

ch02-stack-str.c

/* code: ch02-stack-str.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define DATA_SIZE   100000000
#define MAX         100000000

#define PUSH_SUCCESS    1
#define PUSH_FAILURE   -1
#define POP_SUCCESS     2
#define POP_FAILURE    -2

#define WORDS "/usr/share/dict/words"

/* ------------------------------------------- */
void stack_init (int *top) {
  *top = 0;
}

/* ------------------------------------------- */
void display (char *stack[], int top) {
  int i;
  printf ("STACK(%d): ", top);
  for (i = 0; i < top; i++) {
    printf ("%s ", stack[i]);
  }
  printf ("\n");
}

/* ------------------------------------------- */
int push (char *stack[], int *top, char *data) {
  if (*top >= MAX) {
    /* stack overflow */
    return PUSH_FAILURE;
  }
  else {
    stack[*top] = malloc (sizeof (char) * (strlen (data) + 1));
    sprintf (stack[*top], "%s", data);
    (*top)++;
    return PUSH_SUCCESS;
  }
}

/* ------------------------------------------- */
int pop (char *stack[], int *top, char *data) {
  if ((*top) > 0) {
    sprintf (data, "%s", stack[(*top) - 1]);
    (*top)--;
    return POP_SUCCESS;
  }
  else {
    /* stack empty */
    return POP_FAILURE;
  }
}

/* ------------------------------------------- */
int count_words (char *filename) {
  FILE *infile;
  int i;
  char data[1024];
  if (NULL == (infile = fopen (filename, "rt"))) {
    printf ("ERROR: Can not open file [%s]\n", filename);
    exit (-1);
  }

  i = 0;
  while (EOF != fscanf (infile, "%s", data)) {
    i++;
  }
  fclose (infile);

  return i;
}

/* ------------------------------------------- */
int main () {
  char **stack;
  int top, i, ws;
  FILE *infile;
  char data[1024];

  ws = count_words (WORDS);

  if (NULL == (infile = fopen (WORDS, "rt"))) {
    printf ("ERROR: Can not open file [%s]\n", WORDS);
    exit (-1);
  }

  stack = malloc (sizeof (int) * MAX);

  stack_init (&top);
  i = 0;

  printf ("'%s' (%d)\n", WORDS, ws);
  printf ("push:\n");
  while (EOF != fscanf (infile, "%s", data)) {
    if (i >= ws - 10)
      printf ("%10s (index:%d)\n", data, top);
    push (stack, &top, data);
    i++;
  }
  printf ("\n");

  printf ("pop:\n");
  for (i = 0; i < ws; i++) {
    pop (stack, &top, data);
    if (i < 10)
      printf ("%10s (index:%d)\n", data, top);
  }
  printf ("\n");

  fclose (infile);

  free (stack);


  return 0;
}

ch03-queue-l.c

/* code: ch03-queue-l.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>

#define DATA_SIZE    100000000
#define MAX          100000000

#define ENQUEUE_SUCCESS     1
#define ENQUEUE_FAILURE    -1
#define DEQUEUE_SUCCESS     2
#define DEQUEUE_FAILURE    -2

/* ------------------------------------------- */
void queue_init (int *front, int *rear) {
  *front = -1;
  *rear = -1;
}

/* ------------------------------------------- */
int enqueue (int q[], int *rear, int data) {
  if (*rear < MAX - 1) {
    *rear = *rear + 1;
    q[*rear] = data;
    return ENQUEUE_SUCCESS;
  }
  else {
    return ENQUEUE_FAILURE;
  }
}

/* ------------------------------------------- */
int dequeue (int q[], int *front, int rear, int *data) {
  if (*front == rear) {
    return DEQUEUE_FAILURE;
  }
  *front = *front + 1;
  *data = q[*front];
  return DEQUEUE_SUCCESS;
}

/* ------------------------------------------- */
int main () {
  int *queue;
  int front, rear, data;
  int i, stat;

  queue = malloc (sizeof (int) * MAX);

  queue_init (&front, &rear);

  printf ("data size: %d\n\n", DATA_SIZE);

  printf ("enqueue:\n");
  for (i = 0; i < DATA_SIZE; i++) {
    data = rand () % 1000;
    if (i < 10)
      printf ("%3d ", data);
    enqueue (queue, &rear, data);
  }
  printf ("\n");


  printf ("dequeue:\n");
  while ((10 - 1) - front) {
    stat = dequeue (queue, &front, rear, &data);
    if (stat == DEQUEUE_SUCCESS) {
      printf ("%d ", data);
    }
    else {
      printf ("QUEUE is empty\n");
    }
  }
  printf ("\n");

  free (queue);

  return 0;
}

ch03-queue-rand-a.c

/* code: ch03-queue-rand-a.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>

#define DATA_SIZE    100000000
#define MAX          100000000

#define ENQUEUE_SUCCESS     1
#define ENQUEUE_FAILURE    -1
#define DEQUEUE_SUCCESS     2
#define DEQUEUE_FAILURE    -2

/* ------------------------------------------- */
void queue_init (int *front, int *rear) {
  *front = -1;
  *rear = -1;
}

/* ------------------------------------------- */
int enqueue (int q[], int *rear, int data) {
  if (*rear < MAX - 1) {
    *rear = *rear + 1;
    q[*rear] = data;
    return ENQUEUE_SUCCESS;
  }
  else {
    return ENQUEUE_FAILURE;
  }
}

/* ------------------------------------------- */
int dequeue (int q[], int *front, int rear, int *data) {
  if (*front == rear) {
    return DEQUEUE_FAILURE;
  }
  *front = *front + 1;
  *data = q[*front];
  return DEQUEUE_SUCCESS;
}


/* ------------------------------------------- */
void queue_print (int q[], int front, int rear) {
  int i;

  printf ("    [ ");
  for (i = front + 1; i < rear + 1; i++) {
    printf ("%d ", q[i]);
  }
  printf ("]");
}


/* ------------------------------------------- */
int main () {
  int *queue;
  int front, rear, data;
  int i, stat;

  queue = malloc (sizeof (int) * MAX);

  queue_init (&front, &rear);

  for (i = 0; i < 20; i++) {
    data = rand () % 1000;
    printf ("data: %3d  ", data);
    if (data > 500) {
      printf ("enqueue %3d ", data);
      enqueue (queue, &rear, data);
    }
    else {
      printf ("dequeue ");
      stat = dequeue (queue, &front, rear, &data);
      if (stat == DEQUEUE_SUCCESS) {
	printf ("%3d ", data);
      }
      else {
	printf (" E  ");
      }
    }
    queue_print (queue, front, rear);
    printf ("\n");
  }


  free (queue);

  return 0;
}

ch03-queue-rand-b.c

/* code: ch03-queue-rand-b.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>

#define DATA_SIZE    100000000
#define MAX          100000000

#define ENQUEUE_SUCCESS     1
#define ENQUEUE_FAILURE    -1
#define DEQUEUE_SUCCESS     2
#define DEQUEUE_FAILURE    -2

/* ------------------------------------------- */
void queue_init (int *front, int *rear) {
  *front = -1;
  *rear = -1;
}

/* ------------------------------------------- */
int enqueue (int q[], int *rear, int data) {
  if (*rear < MAX - 1) {
    *rear = *rear + 1;
    q[*rear] = data;
    return ENQUEUE_SUCCESS;
  }
  else {
    return ENQUEUE_FAILURE;
  }
}

/* ------------------------------------------- */
int dequeue (int q[], int *front, int rear, int *data) {
  if (*front == rear) {
    return DEQUEUE_FAILURE;
  }
  *front = *front + 1;
  *data = q[*front];
  return DEQUEUE_SUCCESS;
}


/* ------------------------------------------- */
void queue_print (int q[], int front, int rear) {
  int i;

  printf ("    [ ");
  for (i = front + 1; i < rear + 1; i++) {
    printf ("%d ", q[i]);
  }
  printf ("]");
}


/* ------------------------------------------- */
int main () {
  int *queue;
  int front, rear, data;
  int i, stat;

  queue = malloc (sizeof (int) * MAX);

  queue_init (&front, &rear);

  for (i = 0; i < 20; i++) {
    data = rand () % 1000;
    printf ("data: %3d  ", data);
    if (data > 300) {
      printf ("enqueue %3d ", data);
      enqueue (queue, &rear, data);
    }
    else {
      printf ("dequeue ");
      stat = dequeue (queue, &front, rear, &data);
      if (stat == DEQUEUE_SUCCESS) {
	printf ("%3d ", data);
      }
      else {
	printf (" E  ");
      }
    }
    queue_print (queue, front, rear);
    printf ("\n");
  }


  free (queue);

  return 0;
}

ch03-queue-s.c

/* code: ch03-queue-s.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>

#define MAX 128
#define ENQUEUE_SUCCESS     1
#define ENQUEUE_FAILURE    -1
#define DEQUEUE_SUCCESS     2
#define DEQUEUE_FAILURE    -2

/* ------------------------------------------- */
void queue_init (int *front, int *rear) {
  *front = -1;
  *rear = -1;
}

/* ------------------------------------------- */
int enqueue (int q[], int *rear, int data) {
  if (*rear < MAX - 1) {
    *rear = *rear + 1;
    q[*rear] = data;
    return ENQUEUE_SUCCESS;
  }
  else {
    return ENQUEUE_FAILURE;
  }
}

/* ------------------------------------------- */
int dequeue (int q[], int *front, int rear, int *data) {
  if (*front == rear) {
    return DEQUEUE_FAILURE;
  }
  *front = *front + 1;
  *data = q[*front];
  return DEQUEUE_SUCCESS;
}

/* ------------------------------------------- */
int main () {
  int queue[MAX];
  int front, rear, data;
  int stat;

  queue_init (&front, &rear);
  enqueue (queue, &rear, 100);
  enqueue (queue, &rear, 200);
  enqueue (queue, &rear, 300);
  enqueue (queue, &rear, 400);
  enqueue (queue, &rear, 500);
  while (rear - front) {
    stat = dequeue (queue, &front, rear, &data);
    if (stat == DEQUEUE_SUCCESS) {
      printf ("%d\n", data);
    }
    else {
      printf ("QUEUE is empty\n");
    }
  }
  return 0;
}

ch04-list-del-head.c

/* code: ch04-list-del-head.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>
#define NOT_FOUND (-1)
#define DATA_SIZE 100000
struct node {
  int data;
  struct node *next;
};
typedef struct node NODE_TYPE;

/* ------------------------------------------- */
void linked_list_print_10 (NODE_TYPE * head) {
  int i;
  i = 0;
  printf ("Linked_list [ ");
  while (NULL != head && i < 10) {
    printf ("%02d ", head->data);
    head = head->next;
    i++;
  }
  printf (" ... ]\n");
}


/* ------------------------------------------- */
void linked_list_insert_head (NODE_TYPE ** head, int data) {
  NODE_TYPE *new_node;
  new_node = malloc (sizeof (NODE_TYPE));
  new_node->data = data;
  if (*head == NULL) {
    new_node->next = NULL;
    *head = new_node;
  }
  else {
    new_node->next = *head;
    *head = new_node;
  }
}

/* ------------------------------------------- */
int linked_list_delete_head (NODE_TYPE ** head) {
  int data;
  NODE_TYPE *temp;
  if (*head == NULL) {
    return NOT_FOUND;
  }
  data = (*head)->data;
  temp = (*head);
  *head = (*head)->next;
  free (temp);
  return data;
}


/* ------------------------------------------- */
int main () {
  NODE_TYPE *head;
  int i, data1;

  head = NULL;

  printf ("DATA_SIZE: %d\n", DATA_SIZE);

  printf ("inserting (head): ");
  for (i = 0; i < DATA_SIZE; i++) {
    data1 = (int) rand () % 100;
    linked_list_insert_head (&head, data1);
  }
  printf ("done\n");
  fflush (stdout);

  linked_list_print_10 (head);

  printf ("deleting (head): ");
  for (i = 0; i < DATA_SIZE; i++) {
    data1 = linked_list_delete_head (&head);
  }
  printf ("done\n");
  fflush (stdout);


  return 0;
}

ch04-list-del-tail.c

/* code: ch04-list-del-tail.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>
#define NOT_FOUND (-1)
#define DATA_SIZE 100000

struct node {
  int data;
  struct node *next;
};
typedef struct node NODE_TYPE;

/* ------------------------------------------- */
void linked_list_print_10 (NODE_TYPE * head) {
  int i;
  i = 0;
  printf ("Linked_list [ ");
  while (NULL != head && i < 10) {
    printf ("%02d ", head->data);
    head = head->next;
    i++;
  }
  printf (" ... ]\n");
}


/* ------------------------------------------- */
void linked_list_insert_head (NODE_TYPE ** head, int data) {
  NODE_TYPE *new_node;
  new_node = malloc (sizeof (NODE_TYPE));
  new_node->data = data;
  if (*head == NULL) {
    new_node->next = NULL;
    *head = new_node;
  }
  else {
    new_node->next = *head;
    *head = new_node;
  }
}

/* ------------------------------------------- */
int linked_list_delete_tail (NODE_TYPE ** head) {
  int data;
  NODE_TYPE *temp;
  NODE_TYPE *prev;

  data = NOT_FOUND;
  if (*head == NULL) {
    return data;
  }
  else {
    temp = *head;
    prev = *head;
    while (temp->next != NULL) {
      prev = temp;
      temp = temp->next;
    }
    data = temp->data;
    if ((*head)->next == NULL) {
      *head = NULL;
    }
    else {
      prev->next = NULL;
    }
    free (temp);
  }
  return data;
}



/* ------------------------------------------- */
int main () {
  NODE_TYPE *head;
  int i, data1;

  head = NULL;

  printf ("DATA_SIZE: %d\n", DATA_SIZE);

  printf ("inserting (head): ");
  for (i = 0; i < DATA_SIZE; i++) {
    data1 = (int) rand () % 100;
    linked_list_insert_head (&head, data1);
  }
  printf ("done\n");
  fflush (stdout);

  linked_list_print_10 (head);

  printf ("deleting (tail): ");
  for (i = 0; i < DATA_SIZE; i++) {
    data1 = linked_list_delete_tail (&head);
  }
  printf ("done\n");
  fflush (stdout);

  return 0;
}

ch04-list-ins-head-100m.c

/* code: ch04-list-ins-head-100m.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>
#define NOT_FOUND (-1)
#define DATA_SIZE 100000000

struct node {
  int data;
  struct node *next;
};
typedef struct node NODE_TYPE;

/* ------------------------------------------- */
void linked_list_insert_head (NODE_TYPE ** head, int data) {
  NODE_TYPE *new_node;
  new_node = malloc (sizeof (NODE_TYPE));
  new_node->data = data;
  if (*head == NULL) {
    new_node->next = NULL;
    *head = new_node;
  }
  else {
    new_node->next = *head;
    *head = new_node;
  }
}

/* ------------------------------------------- */
void linked_list_print_10 (NODE_TYPE * head) {
  int i;
  i = 0;
  printf ("Linked_list [ ");
  while (NULL != head && i < 10) {
    printf ("%02d ", head->data);
    head = head->next;
    i++;
  }
  printf (" ... ]\n");
}

/* ------------------------------------------- */
int main () {
  NODE_TYPE *head;
  int i, data1;

  head = NULL;

  printf ("DATA_SIZE: %d\n", DATA_SIZE);
  for (i = 0; i < DATA_SIZE; i++) {
    data1 = (int) rand () % 100;
    linked_list_insert_head (&head, data1);
  }
  linked_list_print_10 (head);
  return 0;
}

ch04-list-ins-head.c

/* code: ch04-list-ins-head.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>
#define NOT_FOUND (-1)
#define DATA_SIZE 100000

struct node {
  int data;
  struct node *next;
};
typedef struct node NODE_TYPE;

/* ------------------------------------------- */
void linked_list_insert_head (NODE_TYPE ** head, int data) {
  NODE_TYPE *new_node;
  new_node = malloc (sizeof (NODE_TYPE));
  new_node->data = data;
  if (*head == NULL) {
    new_node->next = NULL;
    *head = new_node;
  }
  else {
    new_node->next = *head;
    *head = new_node;
  }
}

/* ------------------------------------------- */
void linked_list_print_10 (NODE_TYPE * head) {
  int i;
  i = 0;
  printf ("Linked_list [ ");
  while (NULL != head && i < 10) {
    printf ("%02d ", head->data);
    head = head->next;
    i++;
  }
  printf (" ... ]\n");
}

/* ------------------------------------------- */
int main () {
  NODE_TYPE *head;
  int i, data1;

  head = NULL;

  printf ("DATA_SIZE: %d\n", DATA_SIZE);
  for (i = 0; i < DATA_SIZE; i++) {
    data1 = (int) rand () % 100;
    linked_list_insert_head (&head, data1);
  }
  linked_list_print_10 (head);
  return 0;
}

ch04-list-ins-tail-1.c

/* code: ch04-list-ins-tail-1.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>
#include <time.h>

#define NOT_FOUND (-1)
#define DATA_SIZE 100000000

struct node {
  int data;
  struct node *next;
};
typedef struct node NODE_TYPE;

/* ------------------------------------------- */
void linked_list_insert_head (NODE_TYPE ** head, int data) {
  NODE_TYPE *new_node;
  new_node = malloc (sizeof (NODE_TYPE));
  new_node->data = data;
  if (*head == NULL) {
    new_node->next = NULL;
    *head = new_node;
  }
  else {
    new_node->next = *head;
    *head = new_node;
  }
}

/* ------------------------------------------- */
void linked_list_print_10 (NODE_TYPE * head) {
  int i;
  i = 0;
  printf ("Linked_list [ ");
  while (NULL != head && i < 10) {
    printf ("%02d ", head->data);
    head = head->next;
    i++;
  }
  printf (" ... ]\n");
}


/* ------------------------------------------- */
void linked_list_insert_tail (NODE_TYPE ** head, int data) {
  NODE_TYPE *new_node;
  NODE_TYPE *temp;
  new_node = malloc (sizeof (NODE_TYPE));

  new_node->data = data;
  new_node->next = NULL;
  if (*head == NULL) {
    *head = new_node;
    temp = new_node;
  }
  else {
    temp = *head;
    while (temp->next != NULL) {
      temp = temp->next;
    }
    temp->next = new_node;
  }
}

/* ------------------------------------------- */
int main () {
  NODE_TYPE *head;
  int i, data1;
  clock_t t_start, t_end;

  head = NULL;

  printf ("DATA_SIZE: %d\n", DATA_SIZE);

  t_start = clock ();
  for (i = 0; i < DATA_SIZE; i++) {
    data1 = (int) rand () % 100;
    linked_list_insert_head (&head, data1);
  }
  t_end = clock ();
  printf ("insert(head): %.3lf sec.\n",
	  (double) (t_end - t_start) / (double) CLOCKS_PER_SEC);
  linked_list_print_10 (head);
  printf ("\n");

  t_start = clock ();
  linked_list_insert_tail (&head, 100);

  t_end = clock ();
  printf ("insert(tail): %.3lf sec.\n",
	  (double) (t_end - t_start) / (double) CLOCKS_PER_SEC);


  return 0;
}

ch04-list-ins-tail.c

/* code: ch04-list-ins-tail.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>
#define NOT_FOUND (-1)
#define DATA_SIZE 100000

struct node {
  int data;
  struct node *next;
};
typedef struct node NODE_TYPE;

/* ------------------------------------------- */
void linked_list_print_10 (NODE_TYPE * head) {
  int i;
  i = 0;
  printf ("Linked_list [ ");
  while (NULL != head && i < 10) {
    printf ("%02d ", head->data);
    head = head->next;
    i++;
  }
  printf (" ... ]\n");
}


/* ------------------------------------------- */
void linked_list_insert_tail (NODE_TYPE ** head, int data) {
  NODE_TYPE *new_node;
  NODE_TYPE *temp;
  new_node = malloc (sizeof (NODE_TYPE));

  new_node->data = data;
  new_node->next = NULL;
  if (*head == NULL) {
    *head = new_node;
    temp = new_node;
  }
  else {
    temp = *head;
    while (temp->next != NULL) {
      temp = temp->next;
    }
    temp->next = new_node;
  }
}


/* ------------------------------------------- */
int main () {
  NODE_TYPE *head;
  int i, data1;

  head = NULL;

  printf ("DATA_SIZE: %d\n", DATA_SIZE);
  for (i = 0; i < DATA_SIZE; i++) {
    data1 = (int) rand () % 100;
    linked_list_insert_tail (&head, data1);
  }
  linked_list_print_10 (head);

  return 0;
}

ch04-list-rand.c

/* code: ch04-list-rand.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>
#define NOT_FOUND (-1)
#define DATA_SIZE 6

struct node {
  int data;
  struct node *next;
};
typedef struct node NODE_TYPE;

/* ------------------------------------------- */
void linked_list_insert_head (NODE_TYPE ** head, int data) {
  NODE_TYPE *new_node;
  new_node = malloc (sizeof (NODE_TYPE));
  new_node->data = data;
  if (*head == NULL) {
    new_node->next = NULL;
    *head = new_node;
  }
  else {
    new_node->next = *head;
    *head = new_node;
  }
}

/* ------------------------------------------- */
void linked_list_print (NODE_TYPE * head) {
  printf ("Linked_list [ ");
  while (NULL != head) {
    printf ("%02d ", head->data);
    head = head->next;
  }
  printf ("]\n");
}

/* ------------------------------------------- */
int main () {
  NODE_TYPE *head;
  int i, data1;

  head = NULL;
  for (i = 0; i < DATA_SIZE; i++) {
    data1 = (int) rand () % 100;
    printf ("inserting (head): ");
    printf ("%02d\n", data1);
    linked_list_insert_head (&head, data1);
  }
  linked_list_print (head);
  return 0;
}

ch04-list.c

/* code: ch04-list.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>
struct node {
  int data;
  struct node *next;
};
typedef struct node NODE_TYPE;

/* ------------------------------------------- */
void linked_list_print (NODE_TYPE * node) {
  while (NULL != node) {
    printf ("%d ", node->data);
    node = node->next;
  }
  printf ("\n");
}

/* ------------------------------------------- */
int main () {
  NODE_TYPE *head;
  head = malloc (sizeof (NODE_TYPE));
  head->data = 300;
  head->next = malloc (sizeof (NODE_TYPE));
  head->next->data = 400;
  head->next->next = malloc (sizeof (NODE_TYPE));
  head->next->next->data = 500;
  head->next->next->next = malloc (sizeof (NODE_TYPE));
  head->next->next->next->data = 600;
  head->next->next->next->next = NULL;
  linked_list_print (head);
  return 0;
}

ch04-sizeof-l.c

/* code: ch04-sizeof-l.c   (v1.18.00) */
#include <stdio.h>

struct Node {
  int data_i;
  float data_f;
  double data_d;
  char data_c;
  char data_s[32];
  struct Node *next;
};
typedef struct Node NODE_TYPE;

int main () {
  NODE_TYPE *node;

  printf ("node   (NODE_TYPE)     %zd byte(s)\n", sizeof (NODE_TYPE));
  printf ("\n");
  printf ("data_i (int)           %zd byte(s)\n", sizeof (node->data_i));
  printf ("data_f (float)         %zd byte(s)\n", sizeof (node->data_f));
  printf ("data_d (double)        %zd byte(s)\n", sizeof (node->data_d));
  printf ("data_c (char)          %zd byte(s)\n", sizeof (node->data_c));
  printf ("data_s (char s[32])    %zd byte(s)\n", sizeof (node->data_s));
  printf ("next   (struct Node *) %zd byte(s)\n", sizeof (node->next));

  return 0;
}

ch04-sizeof-s.c

/* code: ch04-sizeof-s.c   (v1.18.00) */
#include <stdio.h>

struct Node {
  int data_i;
  struct Node *next;
};
typedef struct Node NODE_TYPE;

int main () {
  NODE_TYPE *node;

  printf ("node   (NODE_TYPE)     %zd byte(s)\n", sizeof (NODE_TYPE));
  printf ("\n");
  printf ("data_i (int)           %zd byte(s)\n", sizeof (node->data_i));
  printf ("next   (struct Node *) %zd byte(s)\n", sizeof (node->next));

  return 0;
}

ch05-list-cdll.c

/* code: ch05-list-cdll.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>
#define DATA_SIZE 6

/* circular doubly linked list */
struct node {
  int data;
  struct node *prev;
  struct node *next;
};
typedef struct node NODE_TYPE;

/* ------------------------------------------- */
void cdll_print_head (NODE_TYPE * head, NODE_TYPE * tail) {

  if ((head == tail) && (head == NULL)) {
    printf ("List is empty\n");
    return;
  }
  printf ("print  (head): ");
  while (head->next != tail->next) {
    printf ("%d ", head->data);
    head = head->next;
  }
  printf ("%d \n", head->data);
}


/* ------------------------------------------- */
void cdll_print_tail (NODE_TYPE * head, NODE_TYPE * tail) {

  if ((head == tail) && (head == NULL)) {
    printf ("List is empty\n");
    return;
  }
  printf ("print  (tail): ");
  while (head->prev != tail->prev) {
    printf ("%d ", tail->data);
    tail = tail->prev;
  }
  printf ("%d \n", tail->data);
}


/* ------------------------------------------- */
void cdll_insert_head (NODE_TYPE ** head, NODE_TYPE ** tail, int data) {
  NODE_TYPE *new_node;

  new_node = malloc (sizeof (NODE_TYPE));
  new_node->data = data;
  new_node->prev = NULL;
  new_node->next = NULL;

  if ((*head == *tail) && (*head == NULL)) {
    *head = new_node;
    *tail = new_node;
    (*head)->prev = NULL;
    (*head)->next = NULL;
    (*tail)->prev = NULL;
    (*tail)->next = NULL;
  }
  else {
    new_node->next = *head;
    (*head)->prev = new_node;
    *head = new_node;
    (*head)->prev = *tail;
    (*tail)->next = *head;
  }
}




/* ------------------------------------------- */
void cdll_insert_tail (NODE_TYPE ** head, NODE_TYPE ** tail, int data) {
  NODE_TYPE *new_node;

  new_node = malloc (sizeof (NODE_TYPE));
  new_node->data = data;
  new_node->prev = NULL;
  new_node->next = NULL;

  if ((*head == *tail) && (*head == NULL)) {
    *head = new_node;
    *tail = new_node;
    (*head)->prev = NULL;
    (*head)->next = NULL;
    (*tail)->prev = NULL;
    (*tail)->next = NULL;
  }
  else {
    (*tail)->next = new_node;
    new_node->prev = *tail;
    *tail = new_node;
    (*head)->prev = *tail;
    (*tail)->next = *head;
  }
}


/* ------------------------------------------- */
int main () {
  NODE_TYPE *head;
  NODE_TYPE *tail;
  int i, data;

  head = NULL;
  tail = NULL;
  for (i = 0; i < DATA_SIZE; i++) {
    data = (int) rand () % 100;
    printf ("adding (head): ");
    printf ("%02d\n", data);
    cdll_insert_head (&head, &tail, data);
  }
  cdll_print_head (head, tail);
  cdll_print_tail (head, tail);

  for (i = 0; i < DATA_SIZE; i++) {
    data = (int) rand () % 100;
    printf ("adding (tail): ");
    printf ("%02d\n", data);
    cdll_insert_tail (&head, &tail, data);
  }
  cdll_print_head (head, tail);
  cdll_print_tail (head, tail);

  return 0;
}

ch05-list-dll.c

/* code: ch05-list-dll.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>
#define DATA_SIZE 6

/* doubly linked list */
struct node {
  int data;
  struct node *prev;
  struct node *next;
};
typedef struct node NODE_TYPE;

/* ------------------------------------------- */
void dll_print_head (NODE_TYPE * head) {
  NODE_TYPE *temp;

  temp = head;
  if (temp == NULL) {
    printf ("List is empty\n");
    return;
  }
  printf ("print  (head): ");
  while (temp->next != NULL) {
    printf ("%d ", temp->data);
    temp = temp->next;
  }
  printf ("%d \n", temp->data);
}


/* ------------------------------------------- */
void dll_print_tail (NODE_TYPE * tail) {
  NODE_TYPE *temp;

  temp = tail;
  if (temp == NULL) {
    printf ("List is empty\n");
    return;
  }
  printf ("print  (tail): ");
  while (temp->prev != NULL) {
    printf ("%d ", temp->data);
    temp = temp->prev;
  }
  printf ("%d \n", temp->data);
}


/* ------------------------------------------- */
void dll_insert_head (NODE_TYPE ** head, NODE_TYPE ** tail, int data) {
  NODE_TYPE *new_node;

  new_node = malloc (sizeof (NODE_TYPE));
  new_node->data = data;
  new_node->prev = NULL;
  new_node->next = NULL;

  if (*head == NULL) {
    *head = new_node;
    *tail = *head;
  }
  else {
    new_node->next = *head;
    (*head)->prev = new_node;
    *head = new_node;
  }
}


/* ------------------------------------------- */
void dll_insert_tail (NODE_TYPE ** head, NODE_TYPE ** tail, int data) {
  NODE_TYPE *new_node;

  new_node = malloc (sizeof (NODE_TYPE));
  new_node->data = data;
  new_node->prev = NULL;
  new_node->next = NULL;

  if (*head == NULL) {
    *head = new_node;
    new_node = *head;
  }
  else {
    (*tail)->next = new_node;
    new_node->prev = *tail;
    *tail = new_node;
  }
}


/* ------------------------------------------- */
int main () {
  NODE_TYPE *head;
  NODE_TYPE *tail;
  int i, data;

  head = NULL;
  tail = NULL;
  for (i = 0; i < DATA_SIZE; i++) {
    data = (int) rand () % 100;
    printf ("adding (head): ");
    printf ("%02d\n", data);
    dll_insert_head (&head, &tail, data);
  }
  dll_print_head (head);
  dll_print_tail (tail);

  for (i = 0; i < DATA_SIZE; i++) {
    data = (int) rand () % 100;
    printf ("adding (tail): ");
    printf ("%02d\n", data);
    dll_insert_tail (&head, &tail, data);
  }
  dll_print_head (head);
  dll_print_tail (tail);

  return 0;
}

ch05-list-queue.c

/* code: ch05-list-queue.c   (v1.18.00) */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define DATA_SIZE 6
#define QUEUE_EMPTY (-1)
struct node {
  int data;
  struct node *next;
};
typedef struct node NODE_TYPE;

/* ------------------------------------------- */
void q_enque (NODE_TYPE ** front, NODE_TYPE ** rear, int data) {
  NODE_TYPE *new_node;
  new_node = malloc (sizeof (NODE_TYPE));
  new_node->data = data;
  new_node->next = NULL;
  if (*rear == NULL) {
    *front = *rear = new_node;
  }
  else {
    (*rear)->next = new_node;
    *rear = new_node;
  }
}

/* ------------------------------------------- */
int q_dequeue (NODE_TYPE ** front, NODE_TYPE ** rear) {
  int data;
  NODE_TYPE *temp;
  if (*front == NULL) {
    return QUEUE_EMPTY;
  }
  temp = *front;
  data = (*front)->data;
  if (*front == *rear) {
    *front = *rear = NULL;
  }
  else {
    *front = (*front)->next;
  }
  free (temp);
  return data;
}

/* ------------------------------------------- */
void q_print (NODE_TYPE * front) {
  printf ("queue [ ");
  while (front != NULL) {
    printf ("%02d ", front->data);
    front = front->next;
  }
  printf ("]\n");
}

/* ------------------------------------------- */
int main () {
  int i, data1;
  NODE_TYPE *front, *rear;

  front = NULL;
  rear = NULL;
  for (i = 0; i < DATA_SIZE; i++) {
    data1 = (int) rand () % 100;
    printf ("enqueue: ");
    printf ("%02d\n", data1);
    q_enque (&front, &rear, data1);
  }
  q_print (front);
  for (i = 0; i < DATA_SIZE / 2; i++) {
    printf ("dequeue: ");
    data1 = q_dequeue (&front, &rear);
    printf ("%02d\n", data1);
  }
  q_print (front);

  return 0;
}

ch05-list-stack.c

/* code: ch05-list-stack.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>
#define STACK_UNDERFLOW (-1)
#define DATA_SIZE 6
struct node {
  int data;
  struct node *next;
};
typedef struct node NODE_TYPE;


/* ------------------------------------------- */
void stack_push (NODE_TYPE ** head, int data) {
  NODE_TYPE *new_node;
  new_node = malloc (sizeof (NODE_TYPE));
  new_node->data = data;
  new_node->next = *head;
  *head = new_node;
}

/* ------------------------------------------- */
int stack_pop (NODE_TYPE ** head) {
  int data;
  NODE_TYPE *temp;
  if (*head == NULL) {
    return STACK_UNDERFLOW;
  }
  data = (*head)->data;
  temp = (*head);
  *head = (*head)->next;
  free (temp);
  return data;
}

/* ------------------------------------------- */
void stack_print (NODE_TYPE * head) {
  if (head == NULL) {
    printf ("stack is empty.\n");
    return;
  }
  printf ("stack [ ");
  while (NULL != head) {
    printf ("%02d ", head->data);
    head = head->next;
  }
  printf ("]\n");
}

/* ------------------------------------------- */
int main () {
  NODE_TYPE *stack;
  int i, data1;
  stack = NULL;
  for (i = 0; i < DATA_SIZE; i++) {
    data1 = (int) rand () % 100;
    printf ("push: ");
    printf ("%02d\n", data1);
    stack_push (&stack, data1);
  }
  stack_print (stack);
  for (i = 0; i < DATA_SIZE / 2; i++) {
    printf ("pop: ");
    data1 = stack_pop (&stack);
    printf ("%02d\n", data1);
  }
  stack_print (stack);
  return 0;
}

ch06-bst-height.c

/* code: ch06-bst-height.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>


struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);

    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}


/* ------------------------------------------ */
NODE_TYPE *tree_insert (NODE_TYPE * node, int data) {
  if (node == NULL) {
    if (NULL == (node = malloc (sizeof (NODE_TYPE)))) {
      printf ("\nERROR: Can not allocate memory");
      exit (-1);
    }

    node->left = NULL;
    node->right = NULL;
    node->data = data;
  }
  else {
    if (data < node->data) {
      node->left = tree_insert (node->left, data);
    }
    else if (data > node->data) {
      node->right = tree_insert (node->right, data);
    }
  }

  return node;
}

/* ------------------------------------------ */
int tree_height (NODE_TYPE * node) {
  int h_left, h_right;

  if (node == NULL) {
    return -1;
  }

  h_left = tree_height (node->left);
  h_right = tree_height (node->right);

  if (h_left > h_right) {
    return h_left + 1;
  }
  else {
    return h_right + 1;
  }
}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i;
  int array[10] = { 25, 6, 49, 2, 28, 65, 51, 66, 78, 68 };


  root = NULL;
  for (i = 0; i < 10; i++) {
    root = tree_insert (root, array[i]);
  }

  tree_display (root, 0);
  printf ("\n\n");

  printf ("The height of a BST: %d\n", tree_height (root));

  return 0;
}

ch06-bst-minmax.c

/* code: ch06-bst-minmax.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;


/* ------------------------------------------ */
NODE_TYPE *tree_find_min (NODE_TYPE * node) {
  if ((node == NULL) || (node->left == NULL)) {
    return node;
  }
  return tree_find_min (node->left);
}

/* ------------------------------------------ */
NODE_TYPE *tree_find_max (NODE_TYPE * node) {
  if ((node == NULL) || (node->right == NULL)) {
    return node;
  }
  return tree_find_max (node->right);
}

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;
  if (node != NULL) {
    tree_display (node->right, level + 1);
    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}


/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  NODE_TYPE *node_min;
  NODE_TYPE *node_max;

  root = malloc (sizeof (NODE_TYPE));
  root->data = 40;

  root->left = malloc (sizeof (NODE_TYPE));
  root->left->data = 30;

  root->right = malloc (sizeof (NODE_TYPE));
  root->right->data = 70;

  root->left->left = malloc (sizeof (NODE_TYPE));
  root->left->left->data = 10;
  root->left->right = NULL;

  root->right->left = malloc (sizeof (NODE_TYPE));
  root->right->left->data = 60;
  root->right->left->left = NULL;
  root->right->left->right = NULL;

  root->right->right = malloc (sizeof (NODE_TYPE));
  root->right->right->data = 90;
  root->right->right->left = NULL;
  root->right->right->right = NULL;

  root->left->left->right = malloc (sizeof (NODE_TYPE));
  root->left->left->right->data = 20;
  root->left->left->right->left = NULL;
  root->left->left->right->right = NULL;


  tree_display (root, 0);
  printf ("\n\n");

  node_min = tree_find_min (root);
  printf ("min: %d \n", node_min->data);
  node_max = tree_find_max (root);
  printf ("max: %d \n", node_max->data);
  printf ("\n");

  return 0;
}

ch06-bst-s.c

/* code: ch06-bst-s.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;


/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;
  if (node != NULL) {
    tree_display (node->right, level + 1);
    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}


/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;

  root = malloc (sizeof (NODE_TYPE));
  root->data = 40;

  root->left = malloc (sizeof (NODE_TYPE));
  root->left->data = 30;

  root->right = malloc (sizeof (NODE_TYPE));
  root->right->data = 70;

  root->left->left = malloc (sizeof (NODE_TYPE));
  root->left->left->data = 10;
  root->left->right = NULL;

  root->right->left = malloc (sizeof (NODE_TYPE));
  root->right->left->data = 60;
  root->right->left->left = NULL;
  root->right->left->right = NULL;

  root->right->right = malloc (sizeof (NODE_TYPE));
  root->right->right->data = 90;
  root->right->right->left = NULL;
  root->right->right->right = NULL;

  root->left->left->right = malloc (sizeof (NODE_TYPE));
  root->left->left->right->data = 20;
  root->left->left->right->left = NULL;
  root->left->left->right->right = NULL;


  tree_display (root, 0);
  printf ("\n");

  return 0;
}

ch06-bst-size.c

/* code: ch06-bst-size.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>


struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);

    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}


/* ------------------------------------------ */
NODE_TYPE *tree_insert (NODE_TYPE * node, int data) {
  if (node == NULL) {
    if (NULL == (node = malloc (sizeof (NODE_TYPE)))) {
      printf ("\nERROR: Can not allocate memory");
      exit (-1);
    }

    node->left = NULL;
    node->right = NULL;
    node->data = data;
  }
  else {
    if (data < node->data) {
      node->left = tree_insert (node->left, data);
    }
    else if (data > node->data) {
      node->right = tree_insert (node->right, data);
    }
  }

  return node;
}

/* ------------------------------------------ */
int tree_size (NODE_TYPE * node) {
  int s_left, s_right;

  if (node == NULL) {
    return 0;
  }

  s_left = tree_size (node->left);
  s_right = tree_size (node->right);

  return (s_left + s_right + 1);

}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i;
  int array[10] = { 25, 6, 49, 2, 28, 65, 51, 66, 78, 68 };


  root = NULL;
  for (i = 0; i < 10; i++) {
    root = tree_insert (root, array[i]);
  }

  tree_display (root, 0);
  printf ("\n\n");

  printf ("The number of nodes in a BST: %d\n", tree_size (root));

  return 0;
}

ch06-bst-traverse.c

/* code: ch06-bst-traverse.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
void traverse_preorder (NODE_TYPE * node) {
  if (node != NULL) {
    printf ("%2d ", node->data);
    traverse_preorder (node->left);
    traverse_preorder (node->right);
  }
}

/* ------------------------------------------ */
void traverse_inorder (NODE_TYPE * node) {
  if (node != NULL) {
    traverse_inorder (node->left);
    printf ("%2d ", node->data);
    traverse_inorder (node->right);
  }
}

/* ------------------------------------------ */
void traverse_postorder (NODE_TYPE * node) {
  if (node != NULL) {
    traverse_postorder (node->left);
    traverse_postorder (node->right);
    printf ("%2d ", node->data);
  }
}

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);
    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}




/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;

  root = malloc (sizeof (NODE_TYPE));
  root->data = 40;

  root->left = malloc (sizeof (NODE_TYPE));
  root->left->data = 30;

  root->right = malloc (sizeof (NODE_TYPE));
  root->right->data = 70;

  root->left->left = malloc (sizeof (NODE_TYPE));
  root->left->left->data = 10;
  root->left->right = NULL;

  root->right->left = malloc (sizeof (NODE_TYPE));
  root->right->left->data = 60;
  root->right->left->left = NULL;
  root->right->left->right = NULL;

  root->right->right = malloc (sizeof (NODE_TYPE));
  root->right->right->data = 90;
  root->right->right->left = NULL;
  root->right->right->right = NULL;

  root->left->left->right = malloc (sizeof (NODE_TYPE));
  root->left->left->right->data = 20;
  root->left->left->right->left = NULL;
  root->left->left->right->right = NULL;


  tree_display (root, 0);
  printf ("\n\n");


  printf ("Preorder: ");
  traverse_preorder (root);
  printf ("\n");

  printf ("Inorder:  ");
  traverse_inorder (root);
  printf ("\n");

  printf ("Postorder:");
  traverse_postorder (root);
  printf ("\n");


  return 0;
}

ch07-bst-1000.c

/* code: ch07-bst-1000.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

#define MAX 1000

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);
    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("__");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}

/* ------------------------------------------ */
NODE_TYPE *tree_insert (NODE_TYPE * node, int data) {
  if (node == NULL) {
    if (NULL == (node = malloc (sizeof (NODE_TYPE)))) {
      printf ("\nERROR: Can not allocate memory");
      exit (-1);
    }
    node->left = NULL;
    node->right = NULL;
    node->data = data;
  }
  else {
    if (data < node->data) {
      node->left = tree_insert (node->left, data);
    }
    else if (data > node->data) {
      node->right = tree_insert (node->right, data);
    }
  }
  return node;
}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i, v;

  root = NULL;

  printf ("%d nodes\n", MAX);
  fflush (stdout);
  for (i = 0; i < MAX; i++) {
    v = rand () % (MAX * 100);
    root = tree_insert (root, v);
  }
  printf ("\n\n*** binary search tree ***");
  tree_display (root, 0);
  printf ("\n");

  return 0;
}

ch07-bst-1m.c

/* code: ch07-bst-100m.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

#define MAX 1000000

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);
    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("__");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}

/* ------------------------------------------ */
NODE_TYPE *tree_insert (NODE_TYPE * node, int data) {
  if (node == NULL) {
    if (NULL == (node = malloc (sizeof (NODE_TYPE)))) {
      printf ("\nERROR: Can not allocate memory");
      exit (-1);
    }
    node->left = NULL;
    node->right = NULL;
    node->data = data;
  }
  else {
    if (data < node->data) {
      node->left = tree_insert (node->left, data);
    }
    else if (data > node->data) {
      node->right = tree_insert (node->right, data);
    }
  }
  return node;
}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i, v;

  root = NULL;

  printf ("%d nodes\n", MAX);
  fflush (stdout);
  for (i = 0; i < MAX; i++) {
    v = rand () % (MAX * 10);
    root = tree_insert (root, v);
  }
  // printf ("\n\n*** binary search tree ***");
  // tree_display (root, 0);
  printf ("\n");

  return 0;
}

ch07-bst-20.c

/* code: ch07-bst-20.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

#define MAX  20

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);
    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("__");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}

/* ------------------------------------------ */
NODE_TYPE *tree_insert (NODE_TYPE * node, int data) {
  if (node == NULL) {
    if (NULL == (node = malloc (sizeof (NODE_TYPE)))) {
      printf ("\nERROR: Can not allocate memory");
      exit (-1);
    }
    node->left = NULL;
    node->right = NULL;
    node->data = data;
  }
  else {
    if (data < node->data) {
      node->left = tree_insert (node->left, data);
    }
    else if (data > node->data) {
      node->right = tree_insert (node->right, data);
    }
  }
  return node;
}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i;
  int data[MAX];
  root = NULL;

  for (i = 0; i < MAX; i++) {
    data[i] = rand () % (MAX * 10);
  }

  for (i = 0; i < MAX; i++) {
    printf ("%2d ", data[i]);
    root = tree_insert (root, data[i]);
  }

  printf ("\n\n*** binary search tree ***");
  tree_display (root, 0);
  printf ("\n");

  return 0;
}

ch07-bst-20o.c

/* code: ch07-bst-20o.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

#define MAX  20

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
int int_compare (const void *va, const void *vb) {
  int a, b;
  a = *(int *) va;
  b = *(int *) vb;
  if (a < b) {
    return (-1);
  }
  else if (a > b) {
    return (1);
  }
  else {
    return (0);
  }
}


/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);
    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("__");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}

/* ------------------------------------------ */
NODE_TYPE *tree_insert (NODE_TYPE * node, int data) {
  if (node == NULL) {
    if (NULL == (node = malloc (sizeof (NODE_TYPE)))) {
      printf ("\nERROR: Can not allocate memory");
      exit (-1);
    }
    node->left = NULL;
    node->right = NULL;
    node->data = data;
  }
  else {
    if (data < node->data) {
      node->left = tree_insert (node->left, data);
    }
    else if (data > node->data) {
      node->right = tree_insert (node->right, data);
    }
  }
  return node;
}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i;
  int data[MAX];
  root = NULL;

  for (i = 0; i < MAX; i++) {
    data[i] = rand () % (MAX * 10);
  }

  qsort (data, MAX, sizeof (int), int_compare);


  for (i = 0; i < MAX; i++) {
    printf ("%2d ", data[i]);
    root = tree_insert (root, data[i]);
  }

  printf ("\n\n*** binary search tree ***");
  tree_display (root, 0);
  printf ("\n");

  return 0;
}

ch07-bst-delete.c

/* code: ch07-bst-delete.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);
    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("__");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}

/* ------------------------------------------ */
NODE_TYPE *tree_find_min (NODE_TYPE * node) {
  if ((node == NULL) || (node->left == NULL)) {
    return node;
  }
  return tree_find_min (node->left);
}

/* ------------------------------------------ */
NODE_TYPE *tree_find_max (NODE_TYPE * node) {
  if ((node == NULL) || (node->right == NULL)) {
    return node;
  }
  return tree_find_max (node->right);
}

/* ------------------------------------------ */
NODE_TYPE *tree_find (NODE_TYPE * node, int data) {
  if (node == NULL) {
    return NULL;
  }
  if (data < (node->data)) {
    return tree_find (node->left, data);
  }
  if (data > (node->data)) {
    return tree_find (node->right, data);
  }
  return node;
}

/* ------------------------------------------ */
NODE_TYPE *tree_insert (NODE_TYPE * node, int data) {
  if (node == NULL) {
    if (NULL == (node = malloc (sizeof (NODE_TYPE)))) {
      printf ("\nERROR: Can not allocate memory");
      exit (-1);
    }
    node->left = NULL;
    node->right = NULL;
    node->data = data;
  }
  else {
    if (data < node->data) {
      node->left = tree_insert (node->left, data);
    }
    else if (data > node->data) {
      node->right = tree_insert (node->right, data);
    }
  }
  return node;
}

/* ------------------------------------------ */
NODE_TYPE *tree_delete (NODE_TYPE * node, int data) {
  NODE_TYPE *temp;

  if (node == NULL) {
    printf ("\nData item not found");
  }
  else if (data < node->data) {
    node->left = tree_delete (node->left, data);
  }
  else if (data > node->data) {
    node->right = tree_delete (node->right, data);
  }
  else {
    if ((node->left) && (node->right)) {
      temp = tree_find_min (node->right);
      node->data = temp->data;
      node->right = tree_delete (node->right, node->data);
    }
    else if (node->left == NULL) {
      temp = node;
      node = node->right;
      free (temp);
    }
    else {
      temp = node;
      node = node->left;
      free (temp);
    }
  }
  return node;
}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i, v;
  int data[] = { 90, 50, 20, 70, 10, 30, 60, 25, 35 };
  root = NULL;

  for (i = 0; i < 9; i++) {
    printf ("%2d ", data[i]);
    root = tree_insert (root, data[i]);
  }
  printf ("\n\n*** binary search tree ***");
  tree_display (root, 0);
  printf ("\n");

  v = 50;
  printf ("\n\n*** delete %d *** ", v);
  tree_delete (root, v);
  printf ("\n\n*** binary search tree ***");
  tree_display (root, 0);
  printf ("\n");

  return 0;
}

ch07-bst-find.c

/* code: ch07-bst-find.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);
    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("__");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}


/* ------------------------------------------ */
NODE_TYPE *tree_find (NODE_TYPE * node, int data) {
  if (node == NULL) {
    return NULL;
  }
  if (data < (node->data)) {
    return tree_find (node->left, data);
  }
  if (data > (node->data)) {
    return tree_find (node->right, data);
  }
  return node;
}

/* ------------------------------------------ */
NODE_TYPE *tree_insert (NODE_TYPE * node, int data) {
  if (node == NULL) {
    if (NULL == (node = malloc (sizeof (NODE_TYPE)))) {
      printf ("\nERROR: Can not allocate memory");
      exit (-1);
    }
    node->left = NULL;
    node->right = NULL;
    node->data = data;
  }
  else {
    if (data < node->data) {
      node->left = tree_insert (node->left, data);
    }
    else if (data > node->data) {
      node->right = tree_insert (node->right, data);
    }
  }
  return node;
}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  NODE_TYPE *node;
  int i, v;
  int data[] = { 40, 30, 70, 10, 60, 90, 20, 80 };
  root = NULL;

  for (i = 0; i < 8; i++) {
    printf ("%2d ", data[i]);
    root = tree_insert (root, data[i]);
  }
  printf ("\n\n*** binary search tree ***");
  tree_display (root, 0);

  v = 80;
  printf ("\n\n*** searching for a node [%d] ***\n", v);
  node = tree_find (root, v);
  if (node != NULL) {
    printf ("node [%d] found!", node->data);
  }
  printf ("\n");

  return 0;
}

ch07-bst-insert.c

/* code: ch07-bst-insert.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);
    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("__");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}

/* ------------------------------------------ */
NODE_TYPE *tree_insert (NODE_TYPE * node, int data) {
  if (node == NULL) {
    if (NULL == (node = malloc (sizeof (NODE_TYPE)))) {
      printf ("\nERROR: Can not allocate memory");
      exit (-1);
    }
    node->left = NULL;
    node->right = NULL;
    node->data = data;
  }
  else {
    if (data < node->data) {
      node->left = tree_insert (node->left, data);
    }
    else if (data > node->data) {
      node->right = tree_insert (node->right, data);
    }
  }
  return node;
}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i;
  int data[] = { 40, 30, 70, 10, 60, 90, 20, 15 };
  root = NULL;

  for (i = 0; i < 8; i++) {
    printf ("%2d ", data[i]);
    root = tree_insert (root, data[i]);
  }
  printf ("\n\n*** binary search tree ***");
  tree_display (root, 0);
  printf ("\n");

  return 0;
}

ch08-avl-1000.c

/* code: ch08-avl-1000.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>

struct node_type {
  int data;
  int height;
  struct node_type *left;
  struct node_type *right;
};
typedef struct node_type NODE_TYPE;

/* ------------------------------------------ */
void shuffle (int *v, int n) {
  int i, j, t;
  for (i = 0; i < n; i++) {
    j = rand () % n;
    t = v[i];
    v[i] = v[j];
    v[j] = t;
  }
}

/* ------------------------------------------ */
void rand_nd (int *v, int n) {
  int i;

  for (i = 0; i < n; i++) {
    v[i] = i;
  }
  shuffle (v, n);
}

/* ------------------------------------------ */
int avl_max (int x, int y) {
  return (x > y) ? x : y;
}

/* ------------------------------------------ */
int avl_height (NODE_TYPE * node) {
  if (node == NULL) {
    return 0;
  }
  return node->height;
}

/* ------------------------------------------ */
NODE_TYPE *avl_newnode (int data) {
  NODE_TYPE *node;

  node = malloc (sizeof (NODE_TYPE));
  node->data = data;
  node->height = 1;
  node->left = NULL;
  node->right = NULL;
  return (node);
}

/* ------------------------------------------ */
NODE_TYPE *avl_right_r (NODE_TYPE * node_b) {
  NODE_TYPE *node_a;
  NODE_TYPE *temp_node;

  node_a = node_b->left;
  temp_node = node_a->right;
  node_a->right = node_b;
  node_b->left = temp_node;

  node_b->height =
    avl_max (avl_height (node_b->left), avl_height (node_b->right)) + 1;
  node_a->height =
    avl_max (avl_height (node_a->left), avl_height (node_a->right)) + 1;

  return node_a;
}

/* ------------------------------------------ */
NODE_TYPE *avl_left_r (NODE_TYPE * node_a) {
  NODE_TYPE *node_b;
  NODE_TYPE *temp_node;

  node_b = node_a->right;
  temp_node = node_b->left;
  node_b->left = node_a;
  node_a->right = temp_node;

  node_a->height =
    avl_max (avl_height (node_a->left), avl_height (node_a->right)) + 1;
  node_b->height =
    avl_max (avl_height (node_b->left), avl_height (node_b->right)) + 1;

  return node_b;
}


/* ------------------------------------------ */
int avl_height_diff (NODE_TYPE * node) {
  int diff;

  if (node == NULL) {
    return 0;
  }

  diff = avl_height (node->left) - avl_height (node->right);
  return diff;
}


/* ------------------------------------------ */
NODE_TYPE *avl_insert (NODE_TYPE * node, int data) {
  int diff;
  if (node == NULL) {
    return (avl_newnode (data));
  }
  if (data < node->data) {
    node->left = avl_insert (node->left, data);
  }
  else {
    node->right = avl_insert (node->right, data);
  }

  node->height =
    avl_max (avl_height (node->left), avl_height (node->right)) + 1;

  diff = avl_height_diff (node);

  if ((diff > 1) && (data < node->left->data)) {
    return avl_right_r (node);
  }

  if ((diff < -1) && (data > node->right->data)) {
    return avl_left_r (node);

  }

  if ((diff > 1) && (data > node->left->data)) {
    node->left = avl_left_r (node->left);
    return avl_right_r (node);
  }

  if ((diff < -1) && (data < node->right->data)) {
    node->right = avl_right_r (node->right);
    return avl_left_r (node);
  }

  return node;
}



/* ------------------------------------------ */
NODE_TYPE *avl_node_min (NODE_TYPE * node) {
  NODE_TYPE *temp_node;

  temp_node = node;
  while (temp_node->left != NULL) {
    temp_node = temp_node->left;
  }
  return temp_node;
}


/* ------------------------------------------ */
NODE_TYPE *deleteNode (NODE_TYPE * root, int data) {
  int diff;

  if (root == NULL) {
    return root;
  }
  if (data < root->data) {
    root->left = deleteNode (root->left, data);
  }
  else if (data > root->data) {
    root->right = deleteNode (root->right, data);
  }
  else {
    if ((root->left == NULL) || (root->right == NULL)) {
      NODE_TYPE *temp = root->left ? root->left : root->right;
      if (temp == NULL) {
	temp = root;
	root = NULL;
      }
      else {
	*root = *temp;
      }
      free (temp);
    }
    else {
      NODE_TYPE *temp = avl_node_min (root->right);
      root->data = temp->data;
      root->right = deleteNode (root->right, temp->data);
    }
  }


  if (root == NULL) {
    return root;
  }
  root->height =
    avl_max (avl_height (root->left), avl_height (root->right)) + 1;

  diff = avl_height_diff (root);
  if ((diff > 1) && (avl_height_diff (root->left) >= 0)) {
    return avl_right_r (root);
  }

  if ((diff > 1) && (avl_height_diff (root->left) < 0)) {
    root->left = avl_left_r (root->left);
    return avl_right_r (root);
  }

  if ((diff < -1) && (avl_height_diff (root->right) <= 0)) {
    return avl_left_r (root);
  }

  if ((diff < -1) && (avl_height_diff (root->right) > 0)) {
    root->right = avl_right_r (root->right);
    return avl_left_r (root);
  }

  return root;
}

/* ------------------------------------------ */
void tree_display (NODE_TYPE * root, int level) {
  int i;

  if (root != NULL) {
    tree_display (root->right, level + 1);
    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", root->data);
    tree_display (root->left, level + 1);
  }
}



/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i, n;
  int *v;

  root = NULL;
  v = NULL;
  n = 1000;

  srand (1);

  v = malloc (sizeof (int) * n);

  rand_nd (v, n);

  srand (1);
  for (i = 0; i < n; i++) {
    root = avl_insert (root, v[i]);
  }

  tree_display (root, 0);
  printf ("\n\n");

  free (v);

  return 0;
}

ch08-avl-1m.c

/* code: ch08-avl-1m.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>

struct node_type {
  int data;
  int height;
  struct node_type *left;
  struct node_type *right;
};
typedef struct node_type NODE_TYPE;

/* ------------------------------------------ */
void shuffle (int *v, int n) {
  int i, j, t;
  for (i = 0; i < n; i++) {
    j = rand () % n;
    t = v[i];
    v[i] = v[j];
    v[j] = t;
  }
}

/* ------------------------------------------ */
void rand_nd (int *v, int n) {
  int i;

  for (i = 0; i < n; i++) {
    v[i] = i;
  }
  shuffle (v, n);
}

/* ------------------------------------------ */
int avl_max (int x, int y) {
  return (x > y) ? x : y;
}

/* ------------------------------------------ */
int avl_height (NODE_TYPE * node) {
  if (node == NULL) {
    return 0;
  }
  return node->height;
}

/* ------------------------------------------ */
NODE_TYPE *avl_newnode (int data) {
  NODE_TYPE *node;

  node = malloc (sizeof (NODE_TYPE));
  node->data = data;
  node->height = 1;
  node->left = NULL;
  node->right = NULL;
  return (node);
}

/* ------------------------------------------ */
NODE_TYPE *avl_right_r (NODE_TYPE * node_b) {
  NODE_TYPE *node_a;
  NODE_TYPE *temp_node;

  node_a = node_b->left;
  temp_node = node_a->right;
  node_a->right = node_b;
  node_b->left = temp_node;

  node_b->height =
    avl_max (avl_height (node_b->left), avl_height (node_b->right)) + 1;
  node_a->height =
    avl_max (avl_height (node_a->left), avl_height (node_a->right)) + 1;

  return node_a;
}

/* ------------------------------------------ */
NODE_TYPE *avl_left_r (NODE_TYPE * node_a) {
  NODE_TYPE *node_b;
  NODE_TYPE *temp_node;

  node_b = node_a->right;
  temp_node = node_b->left;
  node_b->left = node_a;
  node_a->right = temp_node;

  node_a->height =
    avl_max (avl_height (node_a->left), avl_height (node_a->right)) + 1;
  node_b->height =
    avl_max (avl_height (node_b->left), avl_height (node_b->right)) + 1;

  return node_b;
}


/* ------------------------------------------ */
int avl_height_diff (NODE_TYPE * node) {
  int diff;

  if (node == NULL) {
    return 0;
  }

  diff = avl_height (node->left) - avl_height (node->right);
  return diff;
}


/* ------------------------------------------ */
NODE_TYPE *avl_insert (NODE_TYPE * node, int data) {
  int diff;
  if (node == NULL) {
    return (avl_newnode (data));
  }
  if (data < node->data) {
    node->left = avl_insert (node->left, data);
  }
  else {
    node->right = avl_insert (node->right, data);
  }

  node->height =
    avl_max (avl_height (node->left), avl_height (node->right)) + 1;

  diff = avl_height_diff (node);

  if ((diff > 1) && (data < node->left->data)) {
    return avl_right_r (node);
  }

  if ((diff < -1) && (data > node->right->data)) {
    return avl_left_r (node);

  }

  if ((diff > 1) && (data > node->left->data)) {
    node->left = avl_left_r (node->left);
    return avl_right_r (node);
  }

  if ((diff < -1) && (data < node->right->data)) {
    node->right = avl_right_r (node->right);
    return avl_left_r (node);
  }

  return node;
}



/* ------------------------------------------ */
NODE_TYPE *avl_node_min (NODE_TYPE * node) {
  NODE_TYPE *temp_node;

  temp_node = node;
  while (temp_node->left != NULL) {
    temp_node = temp_node->left;
  }
  return temp_node;
}


/* ------------------------------------------ */
NODE_TYPE *deleteNode (NODE_TYPE * root, int data) {
  int diff;

  if (root == NULL) {
    return root;
  }
  if (data < root->data) {
    root->left = deleteNode (root->left, data);
  }
  else if (data > root->data) {
    root->right = deleteNode (root->right, data);
  }
  else {
    if ((root->left == NULL) || (root->right == NULL)) {
      NODE_TYPE *temp = root->left ? root->left : root->right;
      if (temp == NULL) {
	temp = root;
	root = NULL;
      }
      else {
	*root = *temp;
      }
      free (temp);
    }
    else {
      NODE_TYPE *temp = avl_node_min (root->right);
      root->data = temp->data;
      root->right = deleteNode (root->right, temp->data);
    }
  }


  if (root == NULL) {
    return root;
  }
  root->height =
    avl_max (avl_height (root->left), avl_height (root->right)) + 1;

  diff = avl_height_diff (root);
  if ((diff > 1) && (avl_height_diff (root->left) >= 0)) {
    return avl_right_r (root);
  }

  if ((diff > 1) && (avl_height_diff (root->left) < 0)) {
    root->left = avl_left_r (root->left);
    return avl_right_r (root);
  }

  if ((diff < -1) && (avl_height_diff (root->right) <= 0)) {
    return avl_left_r (root);
  }

  if ((diff < -1) && (avl_height_diff (root->right) > 0)) {
    root->right = avl_right_r (root->right);
    return avl_left_r (root);
  }

  return root;
}

/* ------------------------------------------ */
void tree_display (NODE_TYPE * root, int level) {
  int i;

  if (root != NULL) {
    tree_display (root->right, level + 1);
    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", root->data);
    tree_display (root->left, level + 1);
  }
}



/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i, n;
  int *v;

  root = NULL;
  v = NULL;
  n = 1000000;

  srand (1);
  printf ("%d nodes\n", n);
  fflush (stdout);

  v = malloc (sizeof (int) * n);

  rand_nd (v, n);

  srand (1);
  for (i = 0; i < n; i++) {
    root = avl_insert (root, v[i]);
  }

  // tree_display (root, 0);
  // printf ("\n\n");

  free (v);

  return 0;
}

ch08-avl-30o.c

/* code: ch08-avl-30o.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>

struct node_type {
  int data;
  int height;
  struct node_type *left;
  struct node_type *right;
};
typedef struct node_type NODE_TYPE;

/* ------------------------------------------ */
int int_compare (const void *va, const void *vb) {
  int a, b;
  a = *(int *) va;
  b = *(int *) vb;
  if (a < b) {
    return (-1);
  }
  else if (a > b) {
    return (1);
  }
  else {
    return (0);
  }
}


/* ------------------------------------------ */
void shuffle (int *v, int n) {
  int i, j, t;
  for (i = 0; i < n; i++) {
    j = rand () % n;
    t = v[i];
    v[i] = v[j];
    v[j] = t;
  }
}

/* ------------------------------------------ */
void rand_nd (int *v, int n) {
  int i;

  for (i = 0; i < n; i++) {
    v[i] = i;
  }
  shuffle (v, n);
}

/* ------------------------------------------ */
int avl_max (int x, int y) {
  return (x > y) ? x : y;
}

/* ------------------------------------------ */
int avl_height (NODE_TYPE * node) {
  if (node == NULL) {
    return 0;
  }
  return node->height;
}

/* ------------------------------------------ */
NODE_TYPE *avl_newnode (int data) {
  NODE_TYPE *node;

  node = malloc (sizeof (NODE_TYPE));
  node->data = data;
  node->height = 1;
  node->left = NULL;
  node->right = NULL;
  return (node);
}

/* ------------------------------------------ */
NODE_TYPE *avl_right_r (NODE_TYPE * node_b) {
  NODE_TYPE *node_a;
  NODE_TYPE *temp_node;

  node_a = node_b->left;
  temp_node = node_a->right;
  node_a->right = node_b;
  node_b->left = temp_node;

  node_b->height =
    avl_max (avl_height (node_b->left), avl_height (node_b->right)) + 1;
  node_a->height =
    avl_max (avl_height (node_a->left), avl_height (node_a->right)) + 1;

  return node_a;
}

/* ------------------------------------------ */
NODE_TYPE *avl_left_r (NODE_TYPE * node_a) {
  NODE_TYPE *node_b;
  NODE_TYPE *temp_node;

  node_b = node_a->right;
  temp_node = node_b->left;
  node_b->left = node_a;
  node_a->right = temp_node;

  node_a->height =
    avl_max (avl_height (node_a->left), avl_height (node_a->right)) + 1;
  node_b->height =
    avl_max (avl_height (node_b->left), avl_height (node_b->right)) + 1;

  return node_b;
}


/* ------------------------------------------ */
int avl_height_diff (NODE_TYPE * node) {
  int diff;

  if (node == NULL) {
    return 0;
  }

  diff = avl_height (node->left) - avl_height (node->right);
  return diff;
}


/* ------------------------------------------ */
NODE_TYPE *avl_insert (NODE_TYPE * node, int data) {
  int diff;
  if (node == NULL) {
    return (avl_newnode (data));
  }
  if (data < node->data) {
    node->left = avl_insert (node->left, data);
  }
  else {
    node->right = avl_insert (node->right, data);
  }

  node->height =
    avl_max (avl_height (node->left), avl_height (node->right)) + 1;

  diff = avl_height_diff (node);

  if ((diff > 1) && (data < node->left->data)) {
    return avl_right_r (node);
  }

  if ((diff < -1) && (data > node->right->data)) {
    return avl_left_r (node);

  }

  if ((diff > 1) && (data > node->left->data)) {
    node->left = avl_left_r (node->left);
    return avl_right_r (node);
  }

  if ((diff < -1) && (data < node->right->data)) {
    node->right = avl_right_r (node->right);
    return avl_left_r (node);
  }

  return node;
}



/* ------------------------------------------ */
NODE_TYPE *avl_node_min (NODE_TYPE * node) {
  NODE_TYPE *temp_node;

  temp_node = node;
  while (temp_node->left != NULL) {
    temp_node = temp_node->left;
  }
  return temp_node;
}


/* ------------------------------------------ */
NODE_TYPE *deleteNode (NODE_TYPE * root, int data) {
  int diff;

  if (root == NULL) {
    return root;
  }
  if (data < root->data) {
    root->left = deleteNode (root->left, data);
  }
  else if (data > root->data) {
    root->right = deleteNode (root->right, data);
  }
  else {
    if ((root->left == NULL) || (root->right == NULL)) {
      NODE_TYPE *temp = root->left ? root->left : root->right;
      if (temp == NULL) {
	temp = root;
	root = NULL;
      }
      else {
	*root = *temp;
      }
      free (temp);
    }
    else {
      NODE_TYPE *temp = avl_node_min (root->right);
      root->data = temp->data;
      root->right = deleteNode (root->right, temp->data);
    }
  }


  if (root == NULL) {
    return root;
  }
  root->height =
    avl_max (avl_height (root->left), avl_height (root->right)) + 1;

  diff = avl_height_diff (root);
  if ((diff > 1) && (avl_height_diff (root->left) >= 0)) {
    return avl_right_r (root);
  }

  if ((diff > 1) && (avl_height_diff (root->left) < 0)) {
    root->left = avl_left_r (root->left);
    return avl_right_r (root);
  }

  if ((diff < -1) && (avl_height_diff (root->right) <= 0)) {
    return avl_left_r (root);
  }

  if ((diff < -1) && (avl_height_diff (root->right) > 0)) {
    root->right = avl_right_r (root->right);
    return avl_left_r (root);
  }

  return root;
}

/* ------------------------------------------ */
void tree_display (NODE_TYPE * root, int level) {
  int i;

  if (root != NULL) {
    tree_display (root->right, level + 1);
    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", root->data);
    tree_display (root->left, level + 1);
  }
}



/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i, n;
  int *v;

  root = NULL;
  v = NULL;
  n = 30;

  srand (1);

  v = malloc (sizeof (int) * n);

  rand_nd (v, n);

  qsort (v, n, sizeof (int), int_compare);

  for (i = 0; i < n; i++) {
    root = avl_insert (root, v[i]);
  }

  tree_display (root, 0);
  printf ("\n\n");

  free (v);

  return 0;
}

ch08-bst-100-delete.c

/* code: ch08-bst-100-delete.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);
    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}

/* ------------------------------------------ */
NODE_TYPE *tree_insert (NODE_TYPE * node, int data) {
  if (node == NULL) {
    if (NULL == (node = malloc (sizeof (NODE_TYPE)))) {
      printf ("\nERROR: Can not allocate memory");
      exit (-1);
    }
    node->left = NULL;
    node->right = NULL;
    node->data = data;
  }
  else {
    if (data < node->data) {
      node->left = tree_insert (node->left, data);
    }
    else if (data > node->data) {
      node->right = tree_insert (node->right, data);
    }
  }
  return node;
}

/* ------------------------------------------ */
void tree_delete (NODE_TYPE * node) {
  if (node == NULL)
    return;

  tree_delete (node->left);
  tree_delete (node->right);
  free (node);
}

/* ------------------------------------------ */
void tree_delete_wrapper (NODE_TYPE ** node) {
  tree_delete (*node);
  *node = NULL;
}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i, v;

  root = NULL;
  for (i = 0; i < 100; i++) {
    v = rand () % 1000;
    root = tree_insert (root, v);
  }

  tree_display (root, 0);
  printf ("\n\n");

  tree_delete_wrapper (&root);

  return 0;
}

ch08-bst-100.c

/* code: ch08-bst-100.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
int int_compare (const void *va, const void *vb) {
  int a, b;
  a = *(int *) va;
  b = *(int *) vb;
  if (a < b) {
    return (-1);
  }
  else if (a > b) {
    return (1);
  }
  else {
    return (0);
  }
}

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);
    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}

/* ------------------------------------------ */
NODE_TYPE *tree_insert (NODE_TYPE * node, int data) {
  if (node == NULL) {
    if (NULL == (node = malloc (sizeof (NODE_TYPE)))) {
      printf ("\nERROR: Can not allocate memory");
      exit (-1);
    }
    node->left = NULL;
    node->right = NULL;
    node->data = data;
  }
  else {
    if (data < node->data) {
      node->left = tree_insert (node->left, data);
    }
    else if (data > node->data) {
      node->right = tree_insert (node->right, data);
    }
  }
  return node;
}

/* ------------------------------------------ */
void tree_delete (NODE_TYPE * node) {
  if (node == NULL)
    return;

  tree_delete (node->left);
  tree_delete (node->right);
  free (node);
}

/* ------------------------------------------ */
void tree_delete_wrapper (NODE_TYPE ** node) {
  tree_delete (*node);
  *node = NULL;
}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i, v;

  root = NULL;
  for (i = 0; i < 100; i++) {
    v = rand () % 1000;
    root = tree_insert (root, v);
  }

  tree_display (root, 0);
  printf ("\n\n");

  /* tree_delete_wrapper (&root); */

  return 0;
}

ch08-bst-1000.c

/* code: ch08-bst-1000.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
void shuffle (int *v, int n) {
  int i, j, t;
  for (i = 0; i < n; i++) {
    j = rand () % n;
    t = v[i];
    v[i] = v[j];
    v[j] = t;
  }
}

/* ------------------------------------------ */
void rand_nd (int *v, int n) {
  int i;

  for (i = 0; i < n; i++) {
    v[i] = i;
  }
  shuffle (v, n);
}

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);

    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}


/* ------------------------------------------ */
NODE_TYPE *tree_insert (NODE_TYPE * node, int data) {
  if (node == NULL) {
    if (NULL == (node = malloc (sizeof (NODE_TYPE)))) {
      printf ("\nERROR: Can not allocate memory");
      exit (-1);
    }
    node->left = NULL;
    node->right = NULL;
    node->data = data;
  }
  else {
    if (data < node->data) {
      node->left = tree_insert (node->left, data);
    }
    else if (data > node->data) {
      node->right = tree_insert (node->right, data);
    }
  }

  return node;
}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i, n;
  int *v;

  root = NULL;
  v = NULL;
  n = 1000;

  srand (1);

  v = malloc (sizeof (int) * n);

  rand_nd (v, n);

  for (i = 0; i < n; i++) {
    root = tree_insert (root, v[i]);
  }

  tree_display (root, 0);
  printf ("\n\n");

  free (v);
  return 0;
}

ch08-bst-1m.c

/* code: ch08-bst-1m.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
void shuffle (int *v, int n) {
  int i, j, t;
  for (i = 0; i < n; i++) {
    j = rand () % n;
    t = v[i];
    v[i] = v[j];
    v[j] = t;
  }
}

/* ------------------------------------------ */
void rand_nd (int *v, int n) {
  int i;

  for (i = 0; i < n; i++) {
    v[i] = i;
  }
  shuffle (v, n);
}

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);

    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}


/* ------------------------------------------ */
NODE_TYPE *tree_insert (NODE_TYPE * node, int data) {
  if (node == NULL) {
    if (NULL == (node = malloc (sizeof (NODE_TYPE)))) {
      printf ("\nERROR: Can not allocate memory");
      exit (-1);
    }
    node->left = NULL;
    node->right = NULL;
    node->data = data;
  }
  else {
    if (data < node->data) {
      node->left = tree_insert (node->left, data);
    }
    else if (data > node->data) {
      node->right = tree_insert (node->right, data);
    }
  }

  return node;
}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i, n;
  int *v;

  root = NULL;
  v = NULL;
  n = 1000000;

  srand (1);
  printf ("%d nodes\n", n);
  fflush (stdout);

  v = malloc (sizeof (int) * n);

  rand_nd (v, n);

  for (i = 0; i < n; i++) {
    root = tree_insert (root, v[i]);
  }

  // tree_display (root, 0);
  // printf ("\n\n");

  free (v);
  return 0;
}

ch08-bst-30o.c

/* code: ch08-bst-30o.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
int int_compare (const void *va, const void *vb) {
  int a, b;
  a = *(int *) va;
  b = *(int *) vb;
  if (a < b) {
    return (-1);
  }
  else if (a > b) {
    return (1);
  }
  else {
    return (0);
  }
}

/* ------------------------------------------ */
void shuffle (int *v, int n) {
  int i, j, t;
  for (i = 0; i < n; i++) {
    j = rand () % n;
    t = v[i];
    v[i] = v[j];
    v[j] = t;
  }
}

/* ------------------------------------------ */
void rand_nd (int *v, int n) {
  int i;

  for (i = 0; i < n; i++) {
    v[i] = i;
  }
  shuffle (v, n);
}

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);

    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}


/* ------------------------------------------ */
NODE_TYPE *tree_insert (NODE_TYPE * node, int data) {
  if (node == NULL) {
    if (NULL == (node = malloc (sizeof (NODE_TYPE)))) {
      printf ("\nERROR: Can not allocate memory");
      exit (-1);
    }
    node->left = NULL;
    node->right = NULL;
    node->data = data;
  }
  else {
    if (data < node->data) {
      node->left = tree_insert (node->left, data);
    }
    else if (data > node->data) {
      node->right = tree_insert (node->right, data);
    }
  }

  return node;
}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i, n;
  int *v;

  root = NULL;
  v = NULL;
  n = 30;

  srand (1);

  v = malloc (sizeof (int) * n);

  rand_nd (v, n);

  qsort (v, n, sizeof (int), int_compare);

  for (i = 0; i < n; i++) {
    root = tree_insert (root, v[i]);
  }

  tree_display (root, 0);
  printf ("\n\n");

  free (v);
  return 0;
}

ch08-bst-mirror.c

/* code: ch08-bst-mirror.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);

    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}


/* ------------------------------------------ */
NODE_TYPE *tree_insert (NODE_TYPE * node, int data) {
  if (node == NULL) {
    if (NULL == (node = malloc (sizeof (NODE_TYPE)))) {
      printf ("\nERROR: Can not allocate memory");
      exit (-1);
    }

    node->left = NULL;
    node->right = NULL;
    node->data = data;
  }
  else {
    if (data < node->data) {
      node->left = tree_insert (node->left, data);
    }
    else if (data > node->data) {
      node->right = tree_insert (node->right, data);
    }
  }

  return node;
}


/* ------------------------------------------ */
void tree_mirror (NODE_TYPE * node) {
  NODE_TYPE *temp;

  if (node != NULL) {
    tree_mirror (node->left);
    tree_mirror (node->right);

    temp = node->left;
    node->left = node->right;
    node->right = temp;
  }
}


/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i;
  int array[10] = { 40, 30, 70, 10, 60, 90, 20, 80, 50, 100 };


  root = NULL;
  for (i = 0; i < 10; i++) {
    root = tree_insert (root, array[i]);
  }

  tree_display (root, 0);
  printf ("\n\n");

  printf ("--- mirror ---\n");
  tree_mirror (root);

  tree_display (root, 0);
  printf ("\n\n");

  return 0;
}

ch08-bst-paths.c

/* code: ch08-bst-paths.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

#define MAX_BUF 2048

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);

    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}


/* ------------------------------------------ */
NODE_TYPE *tree_insert (NODE_TYPE * node, int data) {
  if (node == NULL) {
    if (NULL == (node = malloc (sizeof (NODE_TYPE)))) {
      printf ("\nERROR: Can not allocate memory");
      exit (-1);
    }

    node->left = NULL;
    node->right = NULL;
    node->data = data;
  }
  else {
    if (data < node->data) {
      node->left = tree_insert (node->left, data);
    }
    else if (data > node->data) {
      node->right = tree_insert (node->right, data);
    }
  }

  return node;
}

/* ------------------------------------------ */
void print_buffer (int buf[], int len) {
  int i;
  for (i = 0; i < len; i++) {
    printf ("%d", buf[i]);
    if (i != len - 1) {
      printf (" -> ");
    }
  }
  printf ("\n");
}


/* ------------------------------------------ */
void root_to_leaf (NODE_TYPE * node, int path[], int length) {
  if (node == NULL)
    return;

  path[length] = node->data;
  length++;

  if ((node->left == NULL) && (node->right == NULL)) {
    print_buffer (path, length);
  }
  else {
    root_to_leaf (node->left, path, length);
    root_to_leaf (node->right, path, length);
  }
}


/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i;
  int array[10] = { 40, 30, 70, 10, 60, 90, 20, 80, 50, 100 };
  int *path;

  path = malloc (sizeof (int) * MAX_BUF);

  root = NULL;
  for (i = 0; i < 10; i++) {
    root = tree_insert (root, array[i]);
  }

  tree_display (root, 0);
  printf ("\n\n");

  printf ("--- root-to-leaf path(s) ---\n");
  root_to_leaf (root, path, 0);

  free (path);
  return 0;
}

ch09-avl-10m.c

/* code: ch09-avl-10m.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>

#define DATA_SIZE   10000000

struct node_type {
  int data;
  int height;
  struct node_type *left;
  struct node_type *right;
};
typedef struct node_type NODE_TYPE;

/* ------------------------------------------ */
void shuffle (int *v, int n) {
  int i, j, t;
  for (i = 0; i < n; i++) {
    j = rand () % n;
    t = v[i];
    v[i] = v[j];
    v[j] = t;
  }
}

/* ------------------------------------------ */
void rand_nd (int *v, int n) {
  int i;

  for (i = 0; i < n; i++) {
    v[i] = i;
  }
  shuffle (v, n);
}

/* ------------------------------------------ */
int avl_max (int x, int y) {
  return (x > y) ? x : y;
}

/* ------------------------------------------ */
int avl_height (NODE_TYPE * node) {
  if (node == NULL) {
    return 0;
  }
  return node->height;
}

/* ------------------------------------------ */
NODE_TYPE *avl_newnode (int data) {
  NODE_TYPE *node;

  node = malloc (sizeof (NODE_TYPE));
  node->data = data;
  node->height = 1;
  node->left = NULL;
  node->right = NULL;
  return (node);
}

/* ------------------------------------------ */
NODE_TYPE *avl_right_r (NODE_TYPE * node_b) {
  NODE_TYPE *node_a;
  NODE_TYPE *temp_node;

  node_a = node_b->left;
  temp_node = node_a->right;
  node_a->right = node_b;
  node_b->left = temp_node;

  node_b->height =
    avl_max (avl_height (node_b->left), avl_height (node_b->right)) + 1;
  node_a->height =
    avl_max (avl_height (node_a->left), avl_height (node_a->right)) + 1;

  return node_a;
}

/* ------------------------------------------ */
NODE_TYPE *avl_left_r (NODE_TYPE * node_a) {
  NODE_TYPE *node_b;
  NODE_TYPE *temp_node;

  node_b = node_a->right;
  temp_node = node_b->left;
  node_b->left = node_a;
  node_a->right = temp_node;

  node_a->height =
    avl_max (avl_height (node_a->left), avl_height (node_a->right)) + 1;
  node_b->height =
    avl_max (avl_height (node_b->left), avl_height (node_b->right)) + 1;

  return node_b;
}


/* ------------------------------------------ */
int avl_height_diff (NODE_TYPE * node) {
  int diff;

  if (node == NULL) {
    return 0;
  }

  diff = avl_height (node->left) - avl_height (node->right);
  return diff;
}


/* ------------------------------------------ */
NODE_TYPE *avl_insert (NODE_TYPE * node, int data) {
  int diff;
  if (node == NULL) {
    return (avl_newnode (data));
  }
  if (data < node->data) {
    node->left = avl_insert (node->left, data);
  }
  else {
    node->right = avl_insert (node->right, data);
  }

  node->height =
    avl_max (avl_height (node->left), avl_height (node->right)) + 1;

  diff = avl_height_diff (node);

  if ((diff > 1) && (data < node->left->data)) {
    return avl_right_r (node);
  }

  if ((diff < -1) && (data > node->right->data)) {
    return avl_left_r (node);

  }

  if ((diff > 1) && (data > node->left->data)) {
    node->left = avl_left_r (node->left);
    return avl_right_r (node);
  }

  if ((diff < -1) && (data < node->right->data)) {
    node->right = avl_right_r (node->right);
    return avl_left_r (node);
  }

  return node;
}



/* ------------------------------------------ */
NODE_TYPE *avl_node_min (NODE_TYPE * node) {
  NODE_TYPE *temp_node;

  temp_node = node;
  while (temp_node->left != NULL) {
    temp_node = temp_node->left;
  }
  return temp_node;
}


/* ------------------------------------------ */
NODE_TYPE *deleteNode (NODE_TYPE * root, int data) {
  int diff;

  if (root == NULL) {
    return root;
  }
  if (data < root->data) {
    root->left = deleteNode (root->left, data);
  }
  else if (data > root->data) {
    root->right = deleteNode (root->right, data);
  }
  else {
    if ((root->left == NULL) || (root->right == NULL)) {
      NODE_TYPE *temp = root->left ? root->left : root->right;
      if (temp == NULL) {
	temp = root;
	root = NULL;
      }
      else {
	*root = *temp;
      }
      free (temp);
    }
    else {
      NODE_TYPE *temp = avl_node_min (root->right);
      root->data = temp->data;
      root->right = deleteNode (root->right, temp->data);
    }
  }


  if (root == NULL) {
    return root;
  }
  root->height =
    avl_max (avl_height (root->left), avl_height (root->right)) + 1;

  diff = avl_height_diff (root);
  if ((diff > 1) && (avl_height_diff (root->left) >= 0)) {
    return avl_right_r (root);
  }

  if ((diff > 1) && (avl_height_diff (root->left) < 0)) {
    root->left = avl_left_r (root->left);
    return avl_right_r (root);
  }

  if ((diff < -1) && (avl_height_diff (root->right) <= 0)) {
    return avl_left_r (root);
  }

  if ((diff < -1) && (avl_height_diff (root->right) > 0)) {
    root->right = avl_right_r (root->right);
    return avl_left_r (root);
  }

  return root;
}

/* ------------------------------------------ */
void tree_display (NODE_TYPE * root, int level) {
  int i;

  if (root != NULL) {
    tree_display (root->right, level + 1);
    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("_");
    }
    printf ("%d", root->data);
    tree_display (root->left, level + 1);
  }
}



/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i, data;

  root = NULL;
  srand (1);

  printf ("AVL tree\n");
  printf ("  data:   %d \n", DATA_SIZE);
  fflush (stdout);
  for (i = 0; i < DATA_SIZE; i++) {
    data = rand ();
    root = avl_insert (root, data);
  }
  printf ("done\n");

  return 0;
}

ch09-bst-10m.c

/* code: ch09-bst-10m.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>


#define DATA_SIZE   10000000
struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);
    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("__");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}

/* ------------------------------------------ */
NODE_TYPE *tree_insert (NODE_TYPE * node, int data) {
  if (node == NULL) {
    if (NULL == (node = malloc (sizeof (NODE_TYPE)))) {
      printf ("\nERROR: Can not allocate memory");
      exit (-1);
    }
    node->left = NULL;
    node->right = NULL;
    node->data = data;
  }
  else {
    if (data < node->data) {
      node->left = tree_insert (node->left, data);
    }
    else if (data > node->data) {
      node->right = tree_insert (node->right, data);
    }
  }
  return node;
}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i, v;

  root = NULL;

  printf ("binary search tree\n");
  printf ("  data: %d \n", DATA_SIZE);
  fflush (stdout);
  for (i = 0; i < DATA_SIZE; i++) {
    v = rand ();
    root = tree_insert (root, v);
  }
  printf ("done\n");

  return 0;
}

ch09-hash-10m.c

/* code: ch09-hash-10m.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>

#define TABLE_SIZE  20000000
#define DATA_SIZE   10000000

enum data_status { EMPTY, OCCUPIED, DELETED };

struct hash_table_type {
  int data;
  enum data_status status;
};
typedef struct hash_table_type HASH_TABLE_TYPE;


/* ------------------------------------------- */
int hash_function (int key) {
  return (key % TABLE_SIZE);
}


/* ------------------------------------------- */
int hash_table_search (int key, HASH_TABLE_TYPE hash_table[]) {
  int i, index, new_index;

  index = hash_function (key);
  new_index = index;
  for (i = 1; i != TABLE_SIZE - 1; i++) {
    if (hash_table[new_index].status == EMPTY) {
      return -1;
    }
    if (hash_table[new_index].data == key) {
      return new_index;
    }
    new_index = (index + i) % TABLE_SIZE;
  }
  return -1;
}

/* ------------------------------------------- */
void hash_table_insert (int data, HASH_TABLE_TYPE hash_table[]) {
  int i, new_index, index;
  int key = data;

  index = hash_function (key);
  new_index = index;
  for (i = 1; i != TABLE_SIZE - 1; i++) {
    if (hash_table[new_index].status == EMPTY
	|| hash_table[new_index].status == DELETED) {
      hash_table[new_index].data = data;
      hash_table[new_index].status = OCCUPIED;
      return;
    }
    if (hash_table[new_index].data == key) {
      return;
    }
    new_index = (index + i) % TABLE_SIZE;
  }
  printf ("ERROR: table size limit exceeded [%d]\n", TABLE_SIZE);
  exit (-1);
}


/* ------------------------------------------- */
void hash_table_delete (int key, HASH_TABLE_TYPE hash_table[]) {
  int new_index = hash_table_search (key, hash_table);
  if (new_index == -1) {
    printf ("Not found\n");
  }
  else {
    hash_table[new_index].status = DELETED;
  }
}

/* ------------------------------------------- */
void hash_table_init (HASH_TABLE_TYPE hash_table[]) {
  int i;
  for (i = 0; i < TABLE_SIZE; i++) {
    hash_table[i].status = EMPTY;
  }
}

/* ------------------------------------------- */
void hash_table_display (HASH_TABLE_TYPE hash_table[]) {
  int i;
  printf ("--- hash table ---\n");
  for (i = 0; i < TABLE_SIZE; i++) {
    printf ("[%03d]:", i);
    if (hash_table[i].status == OCCUPIED) {
      printf ("[%04d]\n", hash_table[i].data);
    }
    else if (hash_table[i].status == DELETED) {
      printf ("[deleted]\n");
    }
    else {
      printf ("[empty]\n");
    }
  }
  printf ("------------------\n\n");
}




/* ------------------------------------------- */
int main () {
  int i, data;
  HASH_TABLE_TYPE *hash_table;

  hash_table = malloc (sizeof (HASH_TABLE_TYPE) * TABLE_SIZE);

  hash_table_init (hash_table);

  srand (1);
  printf ("hash table\n");
  printf ("  data:   %d \n", DATA_SIZE);
  printf ("  bucket: %d \n", TABLE_SIZE);
  fflush (stdout);
  for (i = 0; i < DATA_SIZE; i++) {
    data = rand ();
    hash_table_insert (data, hash_table);
  }
  printf ("done\n");
  free (hash_table);

  return 0;
}

ch09-hash-b20d10.c

/* code: ch09-hash-b20d10.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>

#define TABLE_SIZE  20
#define DATA_SIZE   10

enum data_status { EMPTY, OCCUPIED, DELETED };

struct hash_table_type {
  int data;
  enum data_status status;
};
typedef struct hash_table_type HASH_TABLE_TYPE;


/* ------------------------------------------- */
int hash_function (int key) {
  return (key % TABLE_SIZE);
}


/* ------------------------------------------- */
int hash_table_search (int key, HASH_TABLE_TYPE hash_table[]) {
  int i, index, new_index;

  index = hash_function (key);
  new_index = index;
  for (i = 1; i != TABLE_SIZE - 1; i++) {
    if (hash_table[new_index].status == EMPTY) {
      return -1;
    }
    if (hash_table[new_index].data == key) {
      return new_index;
    }
    new_index = (index + i) % TABLE_SIZE;
  }
  return -1;
}

/* ------------------------------------------- */
void hash_table_insert (int data, HASH_TABLE_TYPE hash_table[]) {
  int i, new_index, index;
  int key = data;

  index = hash_function (key);
  new_index = index;
  for (i = 1; i != TABLE_SIZE - 1; i++) {
    if (hash_table[new_index].status == EMPTY
	|| hash_table[new_index].status == DELETED) {
      hash_table[new_index].data = data;
      hash_table[new_index].status = OCCUPIED;
      return;
    }
    if (hash_table[new_index].data == key) {
      return;
    }
    new_index = (index + i) % TABLE_SIZE;
  }
  printf ("ERROR: table size limit exceeded [%d]\n", TABLE_SIZE);
  exit (-1);
}


/* ------------------------------------------- */
void hash_table_delete (int key, HASH_TABLE_TYPE hash_table[]) {
  int new_index = hash_table_search (key, hash_table);
  if (new_index == -1) {
    printf ("Not found\n");
  }
  else {
    hash_table[new_index].status = DELETED;
  }
}

/* ------------------------------------------- */
void hash_table_init (HASH_TABLE_TYPE hash_table[]) {
  int i;
  for (i = 0; i < TABLE_SIZE; i++) {
    hash_table[i].status = EMPTY;
  }
}

/* ------------------------------------------- */
void hash_table_display (HASH_TABLE_TYPE hash_table[]) {
  int i;
  printf ("--- hash table ---\n");
  for (i = 0; i < TABLE_SIZE; i++) {
    printf ("[%03d]:", i);
    if (hash_table[i].status == OCCUPIED) {
      printf ("[%04d]\n", hash_table[i].data);
    }
    else if (hash_table[i].status == DELETED) {
      printf ("[deleted]\n");
    }
    else {
      printf ("[empty]\n");
    }
  }
  printf ("------------------\n\n");
}




/* ------------------------------------------- */
int main () {
  int i, data;
  HASH_TABLE_TYPE *hash_table;

  hash_table = malloc (sizeof (HASH_TABLE_TYPE) * TABLE_SIZE);

  hash_table_init (hash_table);

  srand (1);
  printf ("hash table\n");
  printf ("  data:   %d \n", DATA_SIZE);
  printf ("  bucket: %d \n", TABLE_SIZE);
  fflush (stdout);
  for (i = 0; i < DATA_SIZE; i++) {
    data = rand ();
    hash_table_insert (data, hash_table);
  }

  hash_table_display (hash_table);
  free (hash_table);

  return 0;
}

ch09-hash-b20d15.c

/* code: ch09-hash-b20d15.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>

#define TABLE_SIZE  20
#define DATA_SIZE   15

enum data_status { EMPTY, OCCUPIED, DELETED };

struct hash_table_type {
  int data;
  enum data_status status;
};
typedef struct hash_table_type HASH_TABLE_TYPE;


/* ------------------------------------------- */
int hash_function (int key) {
  return (key % TABLE_SIZE);
}


/* ------------------------------------------- */
int hash_table_search (int key, HASH_TABLE_TYPE hash_table[]) {
  int i, index, new_index;

  index = hash_function (key);
  new_index = index;
  for (i = 1; i != TABLE_SIZE - 1; i++) {
    if (hash_table[new_index].status == EMPTY) {
      return -1;
    }
    if (hash_table[new_index].data == key) {
      return new_index;
    }
    new_index = (index + i) % TABLE_SIZE;
  }
  return -1;
}

/* ------------------------------------------- */
void hash_table_insert (int data, HASH_TABLE_TYPE hash_table[]) {
  int i, new_index, index;
  int key = data;

  index = hash_function (key);
  new_index = index;
  for (i = 1; i != TABLE_SIZE - 1; i++) {
    if (hash_table[new_index].status == EMPTY
	|| hash_table[new_index].status == DELETED) {
      hash_table[new_index].data = data;
      hash_table[new_index].status = OCCUPIED;
      return;
    }
    if (hash_table[new_index].data == key) {
      return;
    }
    new_index = (index + i) % TABLE_SIZE;
  }
  printf ("ERROR: table size limit exceeded [%d]\n", TABLE_SIZE);
  exit (-1);
}


/* ------------------------------------------- */
void hash_table_delete (int key, HASH_TABLE_TYPE hash_table[]) {
  int new_index = hash_table_search (key, hash_table);
  if (new_index == -1) {
    printf ("Not found\n");
  }
  else {
    hash_table[new_index].status = DELETED;
  }
}

/* ------------------------------------------- */
void hash_table_init (HASH_TABLE_TYPE hash_table[]) {
  int i;
  for (i = 0; i < TABLE_SIZE; i++) {
    hash_table[i].status = EMPTY;
  }
}

/* ------------------------------------------- */
void hash_table_display (HASH_TABLE_TYPE hash_table[]) {
  int i;
  printf ("--- hash table ---\n");
  for (i = 0; i < TABLE_SIZE; i++) {
    printf ("[%03d]:", i);
    if (hash_table[i].status == OCCUPIED) {
      printf ("[%04d]\n", hash_table[i].data);
    }
    else if (hash_table[i].status == DELETED) {
      printf ("[deleted]\n");
    }
    else {
      printf ("[empty]\n");
    }
  }
  printf ("------------------\n\n");
}




/* ------------------------------------------- */
int main () {
  int i, data;
  HASH_TABLE_TYPE *hash_table;

  hash_table = malloc (sizeof (HASH_TABLE_TYPE) * TABLE_SIZE);

  hash_table_init (hash_table);

  srand (1);
  printf ("hash table\n");
  printf ("  data:   %d \n", DATA_SIZE);
  printf ("  bucket: %d \n", TABLE_SIZE);
  fflush (stdout);
  for (i = 0; i < DATA_SIZE; i++) {
    data = rand ();
    hash_table_insert (data, hash_table);
  }

  hash_table_display (hash_table);
  free (hash_table);

  return 0;
}

ch09-hash-search-110m.c

/* code: ch09-hash-search-110m.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define TABLE_SIZE  110000000
#define DATA_SIZE   100000000

enum data_status { EMPTY, OCCUPIED, DELETED };

struct hash_table_type {
  int data;
  enum data_status status;
};
typedef struct hash_table_type HASH_TABLE_TYPE;


/* ------------------------------------------- */
int hash_function (int key) {
  return (key % TABLE_SIZE);
}


/* ------------------------------------------- */
int hash_table_search (int key, HASH_TABLE_TYPE hash_table[]) {
  int i, index, new_index;

  index = hash_function (key);
  new_index = index;
  for (i = 1; i != TABLE_SIZE - 1; i++) {
    if (hash_table[new_index].status == EMPTY) {
      return -1;
    }
    if (hash_table[new_index].data == key) {
      return new_index;
    }
    new_index = (index + i) % TABLE_SIZE;
  }
  return -1;
}

/* ------------------------------------------- */
void hash_table_insert (int data, HASH_TABLE_TYPE hash_table[]) {
  int i, new_index, index;
  int key = data;

  index = hash_function (key);
  new_index = index;
  for (i = 1; i != TABLE_SIZE - 1; i++) {
    if (hash_table[new_index].status == EMPTY
	|| hash_table[new_index].status == DELETED) {
      hash_table[new_index].data = data;
      hash_table[new_index].status = OCCUPIED;
      return;
    }
    if (hash_table[new_index].data == key) {
      return;
    }
    new_index = (index + i) % TABLE_SIZE;
  }
  printf ("ERROR: table size limit exceeded [%d]\n", TABLE_SIZE);
  exit (-1);
}


/* ------------------------------------------- */
void hash_table_delete (int key, HASH_TABLE_TYPE hash_table[]) {
  int new_index = hash_table_search (key, hash_table);
  if (new_index == -1) {
    printf ("Not found\n");
  }
  else {
    hash_table[new_index].status = DELETED;
  }
}

/* ------------------------------------------- */
void hash_table_init (HASH_TABLE_TYPE hash_table[]) {
  int i;
  for (i = 0; i < TABLE_SIZE; i++) {
    hash_table[i].status = EMPTY;
  }
}

/* ------------------------------------------- */
void hash_table_display (HASH_TABLE_TYPE hash_table[]) {
  int i;
  printf ("--- hash table ---\n");
  for (i = 0; i < TABLE_SIZE; i++) {
    printf ("[%03d]:", i);
    if (hash_table[i].status == OCCUPIED) {
      printf ("[%04d]\n", hash_table[i].data);
    }
    else if (hash_table[i].status == DELETED) {
      printf ("[deleted]\n");
    }
    else {
      printf ("[empty]\n");
    }
  }
  printf ("------------------\n\n");
}




/* ------------------------------------------- */
int main () {
  int i, key, data, index, a, b, total;
  HASH_TABLE_TYPE *hash_table;
  clock_t t_start, t_end;

  printf ("table_size: %d\n", TABLE_SIZE);
  printf ("data_size:  %d\n", DATA_SIZE);
  fflush (stdout);

  hash_table = malloc (sizeof (HASH_TABLE_TYPE) * TABLE_SIZE);

  printf ("hash table init. ... ");
  fflush (stdout);
  hash_table_init (hash_table);
  printf ("done\n");
  fflush (stdout);

  srand (1);
  printf ("hash table insert ... ");
  fflush (stdout);
  for (i = 0; i < DATA_SIZE; i++) {
    data = rand ();
    hash_table_insert (data, hash_table);
  }
  printf ("done\n");
  fflush (stdout);

  a = b = 0;
  srand (2);

  printf ("hash table search ... ");
  fflush (stdout);
  t_start = clock ();
  for (i = 0; i < DATA_SIZE; i++) {
    key = rand ();
    index = hash_table_search (key, hash_table);
    if (index == -1) {
      b++;			/* not found */
    }
    else {
      a++;			/* found */
    }
  }
  t_end = clock ();
  printf ("done\n");
  fflush (stdout);

  total = a + b;

  printf ("data:       %d\n", total);
  printf ("found:      %d (%2.2f%%)\n", a,
	  ((float) a / (float) total) * 100.0);
  printf ("not_found:  %d (%2.2f%%)\n", b,
	  ((float) b / (float) total) * 100.0);

  printf ("search time: %.3lf sec.\n",
	  (double) (t_end - t_start) / (double) CLOCKS_PER_SEC);
  free (hash_table);

  return 0;
}

ch09-hash-search-150m.c

/* code: ch09-hash-search-150m.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define TABLE_SIZE  150000000
#define DATA_SIZE   100000000

enum data_status { EMPTY, OCCUPIED, DELETED };

struct hash_table_type {
  int data;
  enum data_status status;
};
typedef struct hash_table_type HASH_TABLE_TYPE;


/* ------------------------------------------- */
int hash_function (int key) {
  return (key % TABLE_SIZE);
}


/* ------------------------------------------- */
int hash_table_search (int key, HASH_TABLE_TYPE hash_table[]) {
  int i, index, new_index;

  index = hash_function (key);
  new_index = index;
  for (i = 1; i != TABLE_SIZE - 1; i++) {
    if (hash_table[new_index].status == EMPTY) {
      return -1;
    }
    if (hash_table[new_index].data == key) {
      return new_index;
    }
    new_index = (index + i) % TABLE_SIZE;
  }
  return -1;
}

/* ------------------------------------------- */
void hash_table_insert (int data, HASH_TABLE_TYPE hash_table[]) {
  int i, new_index, index;
  int key = data;

  index = hash_function (key);
  new_index = index;
  for (i = 1; i != TABLE_SIZE - 1; i++) {
    if (hash_table[new_index].status == EMPTY
	|| hash_table[new_index].status == DELETED) {
      hash_table[new_index].data = data;
      hash_table[new_index].status = OCCUPIED;
      return;
    }
    if (hash_table[new_index].data == key) {
      return;
    }
    new_index = (index + i) % TABLE_SIZE;
  }
  printf ("ERROR: table size limit exceeded [%d]\n", TABLE_SIZE);
  exit (-1);
}


/* ------------------------------------------- */
void hash_table_delete (int key, HASH_TABLE_TYPE hash_table[]) {
  int new_index = hash_table_search (key, hash_table);
  if (new_index == -1) {
    printf ("Not found\n");
  }
  else {
    hash_table[new_index].status = DELETED;
  }
}

/* ------------------------------------------- */
void hash_table_init (HASH_TABLE_TYPE hash_table[]) {
  int i;
  for (i = 0; i < TABLE_SIZE; i++) {
    hash_table[i].status = EMPTY;
  }
}

/* ------------------------------------------- */
void hash_table_display (HASH_TABLE_TYPE hash_table[]) {
  int i;
  printf ("--- hash table ---\n");
  for (i = 0; i < TABLE_SIZE; i++) {
    printf ("[%03d]:", i);
    if (hash_table[i].status == OCCUPIED) {
      printf ("[%04d]\n", hash_table[i].data);
    }
    else if (hash_table[i].status == DELETED) {
      printf ("[deleted]\n");
    }
    else {
      printf ("[empty]\n");
    }
  }
  printf ("------------------\n\n");
}




/* ------------------------------------------- */
int main () {
  int i, key, data, index, a, b, total;
  HASH_TABLE_TYPE *hash_table;
  clock_t t_start, t_end;

  printf ("table_size: %d\n", TABLE_SIZE);
  printf ("data_size:  %d\n", DATA_SIZE);
  fflush (stdout);

  hash_table = malloc (sizeof (HASH_TABLE_TYPE) * TABLE_SIZE);

  printf ("hash table init. ... ");
  fflush (stdout);
  hash_table_init (hash_table);
  printf ("done\n");
  fflush (stdout);

  srand (1);
  printf ("hash table insert ... ");
  fflush (stdout);
  for (i = 0; i < DATA_SIZE; i++) {
    data = rand ();
    hash_table_insert (data, hash_table);
  }
  printf ("done\n");
  fflush (stdout);

  a = b = 0;
  srand (2);

  printf ("hash table search ... ");
  fflush (stdout);
  t_start = clock ();
  for (i = 0; i < DATA_SIZE; i++) {
    key = rand ();
    index = hash_table_search (key, hash_table);
    if (index == -1) {
      b++;			/* not found */
    }
    else {
      a++;			/* found */
    }
  }
  t_end = clock ();
  printf ("done\n");
  fflush (stdout);

  total = a + b;

  printf ("data:       %d\n", total);
  printf ("found:      %d (%2.2f%%)\n", a,
	  ((float) a / (float) total) * 100.0);
  printf ("not_found:  %d (%2.2f%%)\n", b,
	  ((float) b / (float) total) * 100.0);

  printf ("search time: %.3lf sec.\n",
	  (double) (t_end - t_start) / (double) CLOCKS_PER_SEC);
  free (hash_table);

  return 0;
}

ch09-hash-search-200m.c

/* code: ch09-hash-search-200m.c   (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define TABLE_SIZE  200000000
#define DATA_SIZE   100000000

enum data_status { EMPTY, OCCUPIED, DELETED };

struct hash_table_type {
  int data;
  enum data_status status;
};
typedef struct hash_table_type HASH_TABLE_TYPE;


/* ------------------------------------------- */
int hash_function (int key) {
  return (key % TABLE_SIZE);
}


/* ------------------------------------------- */
int hash_table_search (int key, HASH_TABLE_TYPE hash_table[]) {
  int i, index, new_index;

  index = hash_function (key);
  new_index = index;
  for (i = 1; i != TABLE_SIZE - 1; i++) {
    if (hash_table[new_index].status == EMPTY) {
      return -1;
    }
    if (hash_table[new_index].data == key) {
      return new_index;
    }
    new_index = (index + i) % TABLE_SIZE;
  }
  return -1;
}

/* ------------------------------------------- */
void hash_table_insert (int data, HASH_TABLE_TYPE hash_table[]) {
  int i, new_index, index;
  int key = data;

  index = hash_function (key);
  new_index = index;
  for (i = 1; i != TABLE_SIZE - 1; i++) {
    if (hash_table[new_index].status == EMPTY
	|| hash_table[new_index].status == DELETED) {
      hash_table[new_index].data = data;
      hash_table[new_index].status = OCCUPIED;
      return;
    }
    if (hash_table[new_index].data == key) {
      return;
    }
    new_index = (index + i) % TABLE_SIZE;
  }
  printf ("ERROR: table size limit exceeded [%d]\n", TABLE_SIZE);
  exit (-1);
}


/* ------------------------------------------- */
void hash_table_delete (int key, HASH_TABLE_TYPE hash_table[]) {
  int new_index = hash_table_search (key, hash_table);
  if (new_index == -1) {
    printf ("Not found\n");
  }
  else {
    hash_table[new_index].status = DELETED;
  }
}

/* ------------------------------------------- */
void hash_table_init (HASH_TABLE_TYPE hash_table[]) {
  int i;
  for (i = 0; i < TABLE_SIZE; i++) {
    hash_table[i].status = EMPTY;
  }
}

/* ------------------------------------------- */
void hash_table_display (HASH_TABLE_TYPE hash_table[]) {
  int i;
  printf ("--- hash table ---\n");
  for (i = 0; i < TABLE_SIZE; i++) {
    printf ("[%03d]:", i);
    if (hash_table[i].status == OCCUPIED) {
      printf ("[%04d]\n", hash_table[i].data);
    }
    else if (hash_table[i].status == DELETED) {
      printf ("[deleted]\n");
    }
    else {
      printf ("[empty]\n");
    }
  }
  printf ("------------------\n\n");
}




/* ------------------------------------------- */
int main () {
  int i, key, data, index, a, b, total;
  HASH_TABLE_TYPE *hash_table;
  clock_t t_start, t_end;

  printf ("table_size: %d\n", TABLE_SIZE);
  printf ("data_size:  %d\n", DATA_SIZE);
  fflush (stdout);

  hash_table = malloc (sizeof (HASH_TABLE_TYPE) * TABLE_SIZE);

  printf ("hash table init. ... ");
  fflush (stdout);
  hash_table_init (hash_table);
  printf ("done\n");
  fflush (stdout);

  srand (1);
  printf ("hash table insert ... ");
  fflush (stdout);
  for (i = 0; i < DATA_SIZE; i++) {
    data = rand ();
    hash_table_insert (data, hash_table);
  }
  printf ("done\n");
  fflush (stdout);

  a = b = 0;
  srand (2);

  printf ("hash table search ... ");
  fflush (stdout);
  t_start = clock ();
  for (i = 0; i < DATA_SIZE; i++) {
    key = rand ();
    index = hash_table_search (key, hash_table);
    if (index == -1) {
      b++;			/* not found */
    }
    else {
      a++;			/* found */
    }
  }
  t_end = clock ();
  printf ("done\n");
  fflush (stdout);

  total = a + b;

  printf ("data:       %d\n", total);
  printf ("found:      %d (%2.2f%%)\n", a,
	  ((float) a / (float) total) * 100.0);
  printf ("not_found:  %d (%2.2f%%)\n", b,
	  ((float) b / (float) total) * 100.0);

  printf ("search time: %.3lf sec.\n",
	  (double) (t_end - t_start) / (double) CLOCKS_PER_SEC);
  free (hash_table);

  return 0;
}

ch10-hash-b010.c

/* code: ch10-hash-b010.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HASH_TABLE_ERROR (-1)
#define DATA_SIZE       1000000
// #define HASH_TABLE_SIZE 1500000
// #define HASH_TABLE_SIZE 1000000
#define HASH_TABLE_SIZE 10000

struct hash_node_type {
  int data;
  int key;
  struct hash_node_type *next;
};
typedef struct hash_node_type HASH_NODE;


struct hash_table_type {
  struct hash_node_type **bucket;
  int size;
  int num;
};
typedef struct hash_table_type HASH_TABLE;

/* ------------------------------------------- */
int hash_function (HASH_TABLE * table, int key) {
  return key % table->size;
}

/* ------------------------------------------- */
void hash_table_init (HASH_TABLE * table, int table_size) {
  table->num = 0;
  table->size = table_size;
  table->bucket = calloc (table->size, sizeof (HASH_NODE *));
}

/* ------------------------------------------- */
int hash_table_search (HASH_TABLE * table, int key) {
  int h;
  HASH_NODE *node;

  h = hash_function (table, key);
  for (node = table->bucket[h]; node != NULL; node = node->next) {
    if (node->key == key) {
      break;
    }
  }

  if (node) {
    return node->data;
  }
  else {
    return HASH_TABLE_ERROR;
  }
}

/* ------------------------------------------- */
int hash_table_insert (HASH_TABLE * table, int key, int data) {
  int tmp;
  HASH_NODE *node;
  int h;

  if ((tmp = hash_table_search (table, key)) != HASH_TABLE_ERROR) {
    return (tmp);
  }

  h = hash_function (table, key);
  node = malloc (sizeof (HASH_NODE));
  node->data = data;
  node->key = key;
  node->next = table->bucket[h];
  table->bucket[h] = node;
  table->num++;

  return HASH_TABLE_ERROR;
}

/* ------------------------------------------- */
int hash_table_delete (HASH_TABLE * table, int key) {
  HASH_NODE *node, *node_temp;
  int data;
  int h;

  h = hash_function (table, key);
  for (node = table->bucket[h]; node; node = node->next) {
    if (node->key == key)
      break;
  }

  if (node == NULL)
    return HASH_TABLE_ERROR;

  if (node == table->bucket[h]) {
    table->bucket[h] = node->next;
  }
  else {
    for (node_temp = table->bucket[h]; node_temp && node_temp->next;
	 node_temp = node_temp->next) {
      if (node_temp->next == node)
	break;
    }
    node_temp->next = node->next;
  }
  data = node->data;
  free (node);
  return (data);
}

/* ------------------------------------------- */
void hash_table_free (HASH_TABLE * table) {
  HASH_NODE *node, *node_temp;
  int i;

  for (i = 0; i < table->size; i++) {
    node = table->bucket[i];
    while (node != NULL) {
      node_temp = node;
      node = node->next;
      free (node_temp);
    }
  }

  if (table->bucket != NULL) {
    free (table->bucket);
    memset (table, 0, sizeof (HASH_TABLE));
  }
}

/* ------------------------------------------- */
void hash_table_display (HASH_TABLE * table) {
  HASH_NODE *node;
  int i;
  printf ("------------------------\n");
  for (i = 0; i < table->size; i++) {
    printf ("%02d: ", i);
    node = table->bucket[i];
    while (node != NULL) {
      printf ("%2d(%d) ", node->data, node->key);
      node = node->next;
    }
    printf ("\n");
  }
  printf ("------------------------\n");
}

/* ------------------------------------------- */
void hash_table_info (HASH_TABLE * table) {
  printf ("--- hash table info ---\n");
  printf ("buckets: %d \n", table->size);
  printf ("num: %d \n", table->num);
  printf ("------------------------\n");
}

/* ------------------------------------------- */
int main () {
  int i, data;
  HASH_TABLE *table;
  int key[DATA_SIZE];

  table = malloc (sizeof (HASH_TABLE));
  hash_table_init (table, HASH_TABLE_SIZE);

  for (i = 0; i < DATA_SIZE; i++) {
    key[i] = rand () % (DATA_SIZE * 100);
    data = i + 10;
    hash_table_insert (table, key[i], data);
  }

  hash_table_info (table);
  // hash_table_display (table);

  hash_table_free (table);

  free (table);

  return 0;
}

ch10-hash-b100.c

/* code: ch10-hash-b100.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HASH_TABLE_ERROR (-1)
#define DATA_SIZE       1000000
// #define HASH_TABLE_SIZE 1500000
#define HASH_TABLE_SIZE 1000000
// #define HASH_TABLE_SIZE 10000

struct hash_node_type {
  int data;
  int key;
  struct hash_node_type *next;
};
typedef struct hash_node_type HASH_NODE;


struct hash_table_type {
  struct hash_node_type **bucket;
  int size;
  int num;
};
typedef struct hash_table_type HASH_TABLE;

/* ------------------------------------------- */
int hash_function (HASH_TABLE * table, int key) {
  return key % table->size;
}

/* ------------------------------------------- */
void hash_table_init (HASH_TABLE * table, int table_size) {
  table->num = 0;
  table->size = table_size;
  table->bucket = calloc (table->size, sizeof (HASH_NODE *));
}

/* ------------------------------------------- */
int hash_table_search (HASH_TABLE * table, int key) {
  int h;
  HASH_NODE *node;

  h = hash_function (table, key);
  for (node = table->bucket[h]; node != NULL; node = node->next) {
    if (node->key == key) {
      break;
    }
  }

  if (node) {
    return node->data;
  }
  else {
    return HASH_TABLE_ERROR;
  }
}

/* ------------------------------------------- */
int hash_table_insert (HASH_TABLE * table, int key, int data) {
  int tmp;
  HASH_NODE *node;
  int h;

  if ((tmp = hash_table_search (table, key)) != HASH_TABLE_ERROR) {
    return (tmp);
  }

  h = hash_function (table, key);
  node = malloc (sizeof (HASH_NODE));
  node->data = data;
  node->key = key;
  node->next = table->bucket[h];
  table->bucket[h] = node;
  table->num++;

  return HASH_TABLE_ERROR;
}

/* ------------------------------------------- */
int hash_table_delete (HASH_TABLE * table, int key) {
  HASH_NODE *node, *node_temp;
  int data;
  int h;

  h = hash_function (table, key);
  for (node = table->bucket[h]; node; node = node->next) {
    if (node->key == key)
      break;
  }

  if (node == NULL)
    return HASH_TABLE_ERROR;

  if (node == table->bucket[h]) {
    table->bucket[h] = node->next;
  }
  else {
    for (node_temp = table->bucket[h]; node_temp && node_temp->next;
	 node_temp = node_temp->next) {
      if (node_temp->next == node)
	break;
    }
    node_temp->next = node->next;
  }
  data = node->data;
  free (node);
  return (data);
}

/* ------------------------------------------- */
void hash_table_free (HASH_TABLE * table) {
  HASH_NODE *node, *node_temp;
  int i;

  for (i = 0; i < table->size; i++) {
    node = table->bucket[i];
    while (node != NULL) {
      node_temp = node;
      node = node->next;
      free (node_temp);
    }
  }

  if (table->bucket != NULL) {
    free (table->bucket);
    memset (table, 0, sizeof (HASH_TABLE));
  }
}

/* ------------------------------------------- */
void hash_table_display (HASH_TABLE * table) {
  HASH_NODE *node;
  int i;
  printf ("------------------------\n");
  for (i = 0; i < table->size; i++) {
    printf ("%02d: ", i);
    node = table->bucket[i];
    while (node != NULL) {
      printf ("%2d(%d) ", node->data, node->key);
      node = node->next;
    }
    printf ("\n");
  }
  printf ("------------------------\n");
}

/* ------------------------------------------- */
void hash_table_info (HASH_TABLE * table) {
  printf ("--- hash table info ---\n");
  printf ("buckets: %d \n", table->size);
  printf ("num: %d \n", table->num);
  printf ("------------------------\n");
}

/* ------------------------------------------- */
int main () {
  int i, data;
  HASH_TABLE *table;
  int key[DATA_SIZE];

  table = malloc (sizeof (HASH_TABLE));
  hash_table_init (table, HASH_TABLE_SIZE);

  for (i = 0; i < DATA_SIZE; i++) {
    key[i] = rand () % (DATA_SIZE * 100);
    data = i + 10;
    hash_table_insert (table, key[i], data);
  }

  hash_table_info (table);
  // hash_table_display (table);

  hash_table_free (table);

  free (table);

  return 0;
}

ch10-hash-b150.c

/* code: ch10-hash-b150.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HASH_TABLE_ERROR (-1)
#define DATA_SIZE       1000000
#define HASH_TABLE_SIZE    1500000
// #define HASH_TABLE_SIZE 1000000
// #define HASH_TABLE_SIZE 10000

struct hash_node_type {
  int data;
  int key;
  struct hash_node_type *next;
};
typedef struct hash_node_type HASH_NODE;


struct hash_table_type {
  struct hash_node_type **bucket;
  int size;
  int num;
};
typedef struct hash_table_type HASH_TABLE;

/* ------------------------------------------- */
int hash_function (HASH_TABLE * table, int key) {
  return key % table->size;
}

/* ------------------------------------------- */
void hash_table_init (HASH_TABLE * table, int table_size) {
  table->num = 0;
  table->size = table_size;
  table->bucket = calloc (table->size, sizeof (HASH_NODE *));
}

/* ------------------------------------------- */
int hash_table_search (HASH_TABLE * table, int key) {
  int h;
  HASH_NODE *node;

  h = hash_function (table, key);
  for (node = table->bucket[h]; node != NULL; node = node->next) {
    if (node->key == key) {
      break;
    }
  }

  if (node) {
    return node->data;
  }
  else {
    return HASH_TABLE_ERROR;
  }
}

/* ------------------------------------------- */
int hash_table_insert (HASH_TABLE * table, int key, int data) {
  int tmp;
  HASH_NODE *node;
  int h;

  if ((tmp = hash_table_search (table, key)) != HASH_TABLE_ERROR) {
    return (tmp);
  }

  h = hash_function (table, key);
  node = malloc (sizeof (HASH_NODE));
  node->data = data;
  node->key = key;
  node->next = table->bucket[h];
  table->bucket[h] = node;
  table->num++;

  return HASH_TABLE_ERROR;
}

/* ------------------------------------------- */
int hash_table_delete (HASH_TABLE * table, int key) {
  HASH_NODE *node, *node_temp;
  int data;
  int h;

  h = hash_function (table, key);
  for (node = table->bucket[h]; node; node = node->next) {
    if (node->key == key)
      break;
  }

  if (node == NULL)
    return HASH_TABLE_ERROR;

  if (node == table->bucket[h]) {
    table->bucket[h] = node->next;
  }
  else {
    for (node_temp = table->bucket[h]; node_temp && node_temp->next;
	 node_temp = node_temp->next) {
      if (node_temp->next == node)
	break;
    }
    node_temp->next = node->next;
  }
  data = node->data;
  free (node);
  return (data);
}

/* ------------------------------------------- */
void hash_table_free (HASH_TABLE * table) {
  HASH_NODE *node, *node_temp;
  int i;

  for (i = 0; i < table->size; i++) {
    node = table->bucket[i];
    while (node != NULL) {
      node_temp = node;
      node = node->next;
      free (node_temp);
    }
  }

  if (table->bucket != NULL) {
    free (table->bucket);
    memset (table, 0, sizeof (HASH_TABLE));
  }
}

/* ------------------------------------------- */
void hash_table_display (HASH_TABLE * table) {
  HASH_NODE *node;
  int i;
  printf ("------------------------\n");
  for (i = 0; i < table->size; i++) {
    printf ("%02d: ", i);
    node = table->bucket[i];
    while (node != NULL) {
      printf ("%2d(%d) ", node->data, node->key);
      node = node->next;
    }
    printf ("\n");
  }
  printf ("------------------------\n");
}

/* ------------------------------------------- */
void hash_table_info (HASH_TABLE * table) {
  printf ("--- hash table info ---\n");
  printf ("buckets: %d \n", table->size);
  printf ("num: %d \n", table->num);
  printf ("------------------------\n");
}

/* ------------------------------------------- */
int main () {
  int i, data;
  HASH_TABLE *table;
  int key[DATA_SIZE];

  table = malloc (sizeof (HASH_TABLE));
  hash_table_init (table, HASH_TABLE_SIZE);

  for (i = 0; i < DATA_SIZE; i++) {
    key[i] = rand () % (DATA_SIZE * 100);
    data = i + 10;
    hash_table_insert (table, key[i], data);
  }

  hash_table_info (table);
  // hash_table_display (table);

  hash_table_free (table);

  free (table);

  return 0;
}

ch10-hash-str-djb.c

/* code: ch10-hash-str-djb.c   (v1.18.00) */
#include <stdio.h>

/* ------------------------------------------ */
long int hash_djb (char *str) {
  long int hash;
  int c;
  hash = 5381;
  while ((c = *str++)) {
    hash = ((hash << 5) + hash) + c;
  }
  return hash;
}

/* ------------------------------------------ */
int main () {
  int i;
  char *key[] = {
    "alpha", "bravo", "charlie", "delta",
    "echo", "foxtrot", "golf", "hotel",
    "india", "juliet", "kilo", "lima",
    "mike", "november", "oscar", "papa",
    "quebec", "romeo", "sierra", "tango",
    "uniform", "victor", "whisky", "x-ray",
    "yankee", "zulu"
  };

  for (i = 0; i < 26; i++) {
    printf ("%8s: %ld\n", key[i], hash_djb (key[i]));
  }

  return 0;
}

ch10-hash-str-kr.c

/* code: ch10-hash-str-kr.c   (v1.18.00) */
#include <stdio.h>

/* ------------------------------------------ */
long int hash_kr (char *str) {
  long int hash;
  int c;

  hash = 0;
  while ((c = *str++)) {
    hash += c;
  }
  return hash;
}

/* ------------------------------------------ */
int main () {
  int i;
  char *key[] = {
    "alpha", "bravo", "charlie", "delta",
    "echo", "foxtrot", "golf", "hotel",
    "india", "juliet", "kilo", "lima",
    "mike", "november", "oscar", "papa",
    "quebec", "romeo", "sierra", "tango",
    "uniform", "victor", "whisky", "x-ray",
    "yankee", "zulu"
  };

  for (i = 0; i < 26; i++) {
    printf ("%8s: %ld\n", key[i], hash_kr (key[i]));
  }

  return 0;
}

ch10-hash.c

/* code: c10-1.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HASH_TABLE_ERROR (-1)
#define DATA_SIZE 10
#define HASH_TABLE_SIZE 10

struct hash_node_type {
  int data;
  int key;
  struct hash_node_type *next;
};
typedef struct hash_node_type HASH_NODE;


struct hash_table_type {
  struct hash_node_type **bucket;
  int size;
  int num;
};
typedef struct hash_table_type HASH_TABLE;

/* ------------------------------------------- */
int hash_function (HASH_TABLE * table, int key) {
  return key % table->size;
}

/* ------------------------------------------- */
void hash_table_init (HASH_TABLE * table, int table_size) {
  table->num = 0;
  table->size = table_size;
  table->bucket = calloc (table->size, sizeof (HASH_NODE *));
}

/* ------------------------------------------- */
int hash_table_search (HASH_TABLE * table, int key) {
  int h;
  HASH_NODE *node;

  h = hash_function (table, key);
  for (node = table->bucket[h]; node != NULL; node = node->next) {
    if (node->key == key) {
      break;
    }
  }

  if (node) {
    return node->data;
  }
  else {
    return HASH_TABLE_ERROR;
  }
}

/* ------------------------------------------- */
int hash_table_insert (HASH_TABLE * table, int key, int data) {
  int tmp;
  HASH_NODE *node;
  int h;

  if ((tmp = hash_table_search (table, key)) != HASH_TABLE_ERROR) {
    return (tmp);
  }

  h = hash_function (table, key);
  node = malloc (sizeof (HASH_NODE));
  node->data = data;
  node->key = key;
  node->next = table->bucket[h];
  table->bucket[h] = node;
  table->num++;

  return HASH_TABLE_ERROR;
}

/* ------------------------------------------- */
int hash_table_delete (HASH_TABLE * table, int key) {
  HASH_NODE *node, *node_temp;
  int data;
  int h;

  h = hash_function (table, key);
  for (node = table->bucket[h]; node; node = node->next) {
    if (node->key == key)
      break;
  }

  if (node == NULL)
    return HASH_TABLE_ERROR;

  if (node == table->bucket[h]) {
    table->bucket[h] = node->next;
  }
  else {
    for (node_temp = table->bucket[h]; node_temp && node_temp->next;
	 node_temp = node_temp->next) {
      if (node_temp->next == node)
	break;
    }
    node_temp->next = node->next;
  }
  data = node->data;
  free (node);
  return (data);
}

/* ------------------------------------------- */
void hash_table_free (HASH_TABLE * table) {
  HASH_NODE *node, *node_temp;
  int i;

  for (i = 0; i < table->size; i++) {
    node = table->bucket[i];
    while (node != NULL) {
      node_temp = node;
      node = node->next;
      free (node_temp);
    }
  }

  if (table->bucket != NULL) {
    free (table->bucket);
    memset (table, 0, sizeof (HASH_TABLE));
  }
}

/* ------------------------------------------- */
void hash_table_display (HASH_TABLE * table) {
  HASH_NODE *node;
  int i;
  printf ("------------------------\n");
  for (i = 0; i < table->size; i++) {
    printf ("%02d: ", i);
    node = table->bucket[i];
    while (node != NULL) {
      printf ("%2d ", node->data);
      node = node->next;
    }
    printf ("\n");
  }
  printf ("------------------------\n");
}

/* ------------------------------------------- */
void hash_table_info (HASH_TABLE * table) {
  printf ("--- hash table info ---\n");
  printf ("buckets: %d \n", table->size);
  printf ("num: %d \n", table->num);
  printf ("------------------------\n");
}

/* ------------------------------------------- */
int main () {
  int i, data;
  HASH_TABLE *table;
  int key[DATA_SIZE];

  table = malloc (sizeof (HASH_TABLE));
  hash_table_init (table, HASH_TABLE_SIZE);

  for (i = 0; i < DATA_SIZE; i++) {
    data = rand () % (DATA_SIZE * 100);
    key[i] = data;
    printf ("(insert) data:%d   key:%d\n", data, key[i]);
    hash_table_insert (table, key[i], data);
  }

  hash_table_info (table);
  hash_table_display (table);

  printf ("[search] key:%d -> data:%d\n", key[0],
	  hash_table_search (table, key[0]));
  printf ("[search] key:%d -> data:%d\n", key[1],
	  hash_table_search (table, key[1]));
  printf ("[search] key:%d -> data:%d\n", key[2],
	  hash_table_search (table, key[2]));

  hash_table_free (table);

  free (table);

  return 0;
}

ch11-bst-inorder-stack.c

/* code: ch11-bst-inorder-stack.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

struct Node {
  int data;
  struct Node *left;
  struct Node *right;
};
typedef struct Node NODE_TYPE;

struct Stack {
  struct Node *t;
  struct Stack *next;
};
typedef struct Stack STACK_TYPE;




/* ------------------------------------------ */
void push (STACK_TYPE ** stack, NODE_TYPE * t) {
  STACK_TYPE *newnode;

  newnode = malloc (sizeof (STACK_TYPE));

  if (newnode == NULL) {
    printf ("ERROR: stack overflow \n");
    exit (-1);
  }

  newnode->t = t;
  newnode->next = *stack;

  *stack = newnode;
}


/* ------------------------------------------ */
int is_stack_empty (STACK_TYPE * top) {
  return (top == NULL) ? 1 : 0;
}


/* ------------------------------------------ */
NODE_TYPE *pop (STACK_TYPE ** stack) {
  NODE_TYPE *node;
  STACK_TYPE *top;

  if (is_stack_empty (*stack)) {
    printf ("ERROR: stack underflow \n");
    exit (-1);
  }
  else {
    top = *stack;
    node = top->t;
    *stack = top->next;
    free (top);
    return node;
  }
}

/* ------------------------------------------ */
void inorder_recursion (NODE_TYPE * node) {
  if (node != NULL) {
    inorder_recursion (node->left);
    printf ("%d ", node->data);
    inorder_recursion (node->right);
  }
}


/* ------------------------------------------ */
void inorder_stack (NODE_TYPE * root) {
  int flag;
  STACK_TYPE *stack;
  NODE_TYPE *node;

  node = root;
  stack = NULL;
  flag = 0;

  while (!flag) {
    if (node != NULL) {
      push (&stack, node);
      node = node->left;
    }
    else {
      if (!is_stack_empty (stack)) {
	node = pop (&stack);
	printf ("%d ", node->data);
	node = node->right;
      }
      else {
	flag = 1;
      }
    }
  }
}



/* ------------------------------------------ */
void tree_display (NODE_TYPE * node, int level) {
  int i;

  if (node != NULL) {
    tree_display (node->right, level + 1);
    printf ("\n");
    for (i = 0; i < level; i++) {
      printf ("__");
    }
    printf ("%d", node->data);
    tree_display (node->left, level + 1);
  }
}


/* ------------------------------------------ */
NODE_TYPE *tree_insert (NODE_TYPE * node, int data) {
  if (node == NULL) {
    if (NULL == (node = malloc (sizeof (NODE_TYPE)))) {
      printf ("\nERROR: Can not allocate memory");
      exit (-1);
    }
    node->left = NULL;
    node->right = NULL;
    node->data = data;
  }
  else {
    if (data < node->data) {
      node->left = tree_insert (node->left, data);
    }
    else if (data > node->data) {
      node->right = tree_insert (node->right, data);
    }
  }
  return node;
}

/* ------------------------------------------ */
int main () {
  NODE_TYPE *root;
  int i;
  int data[] = { 40, 30, 70, 10, 60, 90, 20, 80 };
  root = NULL;

  for (i = 0; i < 8; i++) {
    printf ("%2d ", data[i]);
    root = tree_insert (root, data[i]);
  }
  printf ("\n\n");
  printf ("*** binary search tree ***\n");
  tree_display (root, 0);

  printf ("\n\n*** inorder traversal (recursion) ***\n");
  inorder_recursion (root);

  printf ("\n\n*** inorder traversal (stack) ***\n");
  inorder_stack (root);

  printf ("\n");

  return 0;
}

ch11-factorial-tail.c

/* code: ch11-factorial-tail.c   (v1.18.00) */
#include <stdio.h>

/* ------------------------------------------- */
int factorial (int n) {
  if (n == 0)
    return 1;

  return n * factorial (n - 1);
}

/* ------------------------------------------- */
int factorial_tail (int n, int acc) {
  if (n == 0)
    return acc;

  return factorial_tail (n - 1, n * acc);
}

/* ------------------------------------------- */
int main () {
  int i;

  i = 5;
  printf ("factorial_tail(%d) = %d\n", i, factorial_tail (i, 1));

  return 0;
}

ch11-factorial-v.c

/* code: ch11-factorial-v.c   (v1.18.00) */
#include <stdio.h>

/* ------------------------------------------- */
int factorial (int n) {
  int i, v;

  for (i = 0; i < n; i++)
    printf (" ");
  printf ("Called 'factorial(%d)' \n", n);

  if (n == 0)
    return 1;

  v = n * factorial (n - 1);

  for (i = 0; i < n; i++)
    printf (" ");
  printf ("Returning 'factorial(%d)=%d' \n", n, v);
  return v;
}

/* ------------------------------------------- */
int main () {
  int i;

  i = 5;
  printf ("Factorial of %d is %d\n", i, factorial (i));

  return 0;
}

ch11-factorial.c

/* code: ch11-factorial.c   (v1.18.00) */
#include <stdio.h>

/* ------------------------------------------- */
int factorial (int n) {
  int v;

  if (n == 0)
    return 1;

  v = n * factorial (n - 1);

  return v;
}

/* ------------------------------------------- */
int main () {
  int i;

  i = 5;
  printf ("factorial(%d) = %d\n", i, factorial (i));

  return 0;
}

ch11-fibonacci-v.c

/* code: ch11-fibonacci-v.c   (v1.18.00) */
#include <stdio.h>

/* ------------------------------------------- */
int fibonacci (int n) {
  int i, v;

  for (i = 0; i < n; i++)
    printf (" ");
  printf ("Called 'fibonacci(%d)' \n", n);

  if (n == 0)
    return 0;

  if (n == 1)
    return 1;

  v = fibonacci (n - 1) + fibonacci (n - 2);

  for (i = 0; i < n; i++)
    printf (" ");
  printf ("Returning 'fibonacci(%d)=%d' \n", n, v);
  return v;
}

/* ------------------------------------------- */
int main () {
  int i;
  i = 5;
  printf ("Fibonacci(%d) = %d\n", i, fibonacci (i));

  return 0;
}

ch11-fibonacci.c

/* code: ch11-fibonacci.c   (v1.18.00) */
#include <stdio.h>

/* ------------------------------------------- */
int fibonacci (int n) {
  int v;
  if (n == 0)
    return 0;

  if (n == 1)
    return 1;

  v = fibonacci (n - 1) + fibonacci (n - 2);
  return v;
}

/* ------------------------------------------- */
int main () {
  int i;
  i = 5;

  printf ("Fibonacci(%d) = %d\n", i, fibonacci (i));

  return 0;
}

ch11-gcd.c

/* code: ch11-gcd.c   (v1.18.00) */
#include <stdio.h>

/* ------------------------------------------- */
int gcd (int x, int y) {
  int v;

  if (y == 0)
    return x;

  v = gcd (y, (x % y));

  return v;
}

/* ------------------------------------------- */
int main () {
  int a, b;

  a = 12;
  b = 18;
  printf ("GCD(%d, %d) = %d\n", a, b, gcd (a, b));

  return 0;
}

ch11-power.c

/* code: ch11-power.c   (v1.18.00) */
#include <stdio.h>

/* ------------------------------------------- */
int power (int x, int n) {
  int m;
  if (n == 0)
    return 1;

  if (n % 2 == 0) {
    m = power (x, n / 2);
    return m * m;
  }
  else {
    return x * power (x, n - 1);
  }
}

/* ------------------------------------------- */
int main () {
  int x, n;

  x = 5;
  n = 3;
  printf ("power(%d,%d) = %d\n", x, n, power (x, n));

  return 0;
}

ch11-rec-a.c

/* code: ch11-rec-a.c   (v1.18.00) */
#include <stdio.h>

void foo (int n) {
  if (n < 5) {
    printf ("%d ", n);
    foo (n + 1);
  }
}

int main () {
  foo (0);
  return 0;
}

ch11-rec-b.c

/* code: ch11-rec-b.c   (v1.18.00) */
#include <stdio.h>

void foo (int n) {
  if (n < 5) {
    foo (n + 1);
    printf ("%d ", n);
  }
}

int main () {
  foo (0);
  return 0;
}

ch11-rec-binarysearch.c

/* code: ch11-rec-binarysearch.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#define ARRAY_SIZE 13

/* ------------------------------------------- */
int binary_search (int array[], int num, int key) {
  int middle, low, high;
  low = 0;
  high = num - 1;
  while (low <= high) {
    middle = (low + high) / 2;
    if (key == array[middle]) {
      return middle;
    }
    else if (key < array[middle]) {
      high = middle - 1;
    }
    else {
      low = middle + 1;
    }
  }
  return -1;
}


/* ------------------------------------------- */
int binary_search_r (int array[], int num, int key, int low, int high) {
  int middle;

  if (low > high)
    return -1;

  middle = (low + high) / 2;

  if (array[middle] == key) {
    return middle;
  }
  else if (array[middle] < key) {
    return binary_search_r (array, num, key, middle + 1, high);
  }
  else {
    return binary_search_r (array, num, key, low, middle - 1);
  }
}


/* ------------------------------------------- */
void print_array (int array[], int n) {
  int i;
  for (i = 0; i < n; i++) {
    printf ("%d ", array[i]);
  }
  printf ("\n");
}

/* ------------------------------------------- */
int main () {
  int index, key;
  int array[ARRAY_SIZE] = {
    50, 80, 150, 210, 250, 280, 330,
    470, 510, 530, 800, 900, 990
  };

  key = 800;
  print_array (array, ARRAY_SIZE);

  /* index = binary_search (array, ARRAY_SIZE, key); */

  index = binary_search_r (array, ARRAY_SIZE, key, 0, ARRAY_SIZE - 1);

  if (index != -1) {
    printf ("Found: %d (index:%d)\n", key, index);
  }
  else {
    printf ("Not found: %d\n", key);
  }
  return 0;
}

ch12-bubble-100t-o50.c

/* code: ch12-bubble-100t-o50.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DATA_SIZE 100000
#define ORDERED   0.50
/* ------------------------------------------ */
int int_compare (const void *va, const void *vb) {
  int a, b;
  a = *(int *) va;
  b = *(int *) vb;
  if (a < b) {
    return (-1);
  }
  else if (a > b) {
    return (1);
  }
  else {
    return (0);
  }
}


/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;

  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}


/* ------------------------------------------ */
void bubble_sort (int v[], int n) {
  int i, j, temp, flag;

  flag = 1;
  for (i = 0; (i < n - 1) && (flag == 1); i++) {
    flag = 0;
    for (j = 0; j < n - i - 1; j++) {
      if (v[j] > v[j + 1]) {
	temp = v[j];
	v[j] = v[j + 1];
	v[j + 1] = temp;
	flag = 1;
      }
    }
  }
}

/* ------------------------------------------ */
int main () {
  int *array;
  int i, n;
  float ord;
  clock_t t_start, t_end;

  n = DATA_SIZE;
  ord = ORDERED;
  array = malloc (sizeof (int) * n);

  for (i = 0; i < n; i++) {
    array[i] = rand () % n;
  }
  qsort (array, n * ord, sizeof (int), int_compare);


  printf ("#data:  %d  (o:%.2f%%)\n", n, ord * 100.0);
  printf ("input:  ");
  print_array (array, 10);

  t_start = clock ();
  bubble_sort (array, n);
  t_end = clock ();

  printf ("output: ");
  print_array (array, 10);
  printf ("time: %.3lf sec.\n",
	  (double) (t_end - t_start) / (double) CLOCKS_PER_SEC);

  free (array);

  return 0;
}

ch12-bubble-100t-o95.c

/* code: ch12-bubble-100t-o95.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DATA_SIZE 100000
#define ORDERED   0.95
/* ------------------------------------------ */
int int_compare (const void *va, const void *vb) {
  int a, b;
  a = *(int *) va;
  b = *(int *) vb;
  if (a < b) {
    return (-1);
  }
  else if (a > b) {
    return (1);
  }
  else {
    return (0);
  }
}


/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;

  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}


/* ------------------------------------------ */
void bubble_sort (int v[], int n) {
  int i, j, temp, flag;

  flag = 1;
  for (i = 0; (i < n - 1) && (flag == 1); i++) {
    flag = 0;
    for (j = 0; j < n - i - 1; j++) {
      if (v[j] > v[j + 1]) {
	temp = v[j];
	v[j] = v[j + 1];
	v[j + 1] = temp;
	flag = 1;
      }
    }
  }
}

/* ------------------------------------------ */
int main () {
  int *array;
  int i, n;
  float ord;
  clock_t t_start, t_end;

  n = DATA_SIZE;
  ord = ORDERED;
  array = malloc (sizeof (int) * n);

  for (i = 0; i < n; i++) {
    array[i] = rand () % n;
  }
  qsort (array, n * ord, sizeof (int), int_compare);


  printf ("#data:  %d  (o:%.2f%%)\n", n, ord * 100.0);
  printf ("input:  ");
  print_array (array, 10);

  t_start = clock ();
  bubble_sort (array, n);
  t_end = clock ();

  printf ("output: ");
  print_array (array, 10);
  printf ("time: %.3lf sec.\n",
	  (double) (t_end - t_start) / (double) CLOCKS_PER_SEC);

  free (array);

  return 0;
}

ch12-bubble-100t-r.c

/* code: ch12-bubble-100t-r.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DATA_SIZE 100000

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;

  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}


/* ------------------------------------------ */
void bubble_sort (int v[], int n) {
  int i, j, temp, flag;

  flag = 1;
  for (i = 0; (i < n - 1) && (flag == 1); i++) {
    flag = 0;
    for (j = 0; j < n - i - 1; j++) {
      if (v[j] > v[j + 1]) {
	temp = v[j];
	v[j] = v[j + 1];
	v[j + 1] = temp;
	flag = 1;
      }
    }
  }
}

/* ------------------------------------------ */
int main () {
  int *array;
  int i, n;
  clock_t t_start, t_end;

  n = DATA_SIZE;
  array = malloc (sizeof (int) * n);

  for (i = 0; i < n; i++) {
    array[i] = rand () % n;
  }

  printf ("#data:  %d\n", n);
  printf ("input:  ");
  print_array (array, 10);

  t_start = clock ();
  bubble_sort (array, n);
  t_end = clock ();

  printf ("output: ");
  print_array (array, 10);
  printf ("time: %.3lf sec.\n",
	  (double) (t_end - t_start) / (double) CLOCKS_PER_SEC);

  free (array);

  return 0;
}

ch12-bubble-100t.c

/* code: ch12-bubble-100t-r.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DATA_SIZE 100000

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;

  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}


/* ------------------------------------------ */
void bubble_sort (int v[], int n) {
  int i, j, temp, flag;

  flag = 1;
  for (i = 0; (i < n - 1) && (flag == 1); i++) {
    flag = 0;
    for (j = 0; j < n - i - 1; j++) {
      if (v[j] > v[j + 1]) {
	temp = v[j];
	v[j] = v[j + 1];
	v[j + 1] = temp;
	flag = 1;
      }
    }
  }
}

/* ------------------------------------------ */
int main () {
  int *array;
  int i, n;
  clock_t t_start, t_end;

  n = DATA_SIZE;
  array = malloc (sizeof (int) * n);

  for (i = 0; i < n; i++) {
    array[i] = rand () % n;
  }

  printf ("#data:  %d\n", n);
  printf ("input:  ");
  print_array (array, 10);

  t_start = clock ();
  bubble_sort (array, n);
  t_end = clock ();

  printf ("output: ");
  print_array (array, 10);
  printf ("time: %.3lf sec.\n",
	  (double) (t_end - t_start) / (double) CLOCKS_PER_SEC);

  free (array);

  return 0;
}

ch12-bubble-5-adv.c

/* code: ch12-bubble-5-adv.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
void bubble_sort (int v[], int n) {
  int i, j, temp, flag;

  flag = 1;
  for (i = 0; (i < n - 1) && (flag == 1); i++) {
    flag = 0;
    for (j = 0; j < n - i - 1; j++) {
      if (v[j] > v[j + 1]) {
	temp = v[j];
	v[j] = v[j + 1];
	v[j + 1] = temp;
	flag = 1;
      }
      printf ("i:%d j:%d  ", i, j);
      print_array (v, n);
    }
  }
}

/* ------------------------------------------ */
int main () {
  int array[5]
  = { 300, 100, 200, 500, 400 };

  print_array (array, 5);
  bubble_sort (array, 5);
  print_array (array, 5);

  return 0;
}

ch12-bubble-5.c

/* code: ch12-bubble-5.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
void bubble_sort (int v[], int n) {
  int i, j, temp;
  for (i = 0; i < n - 1; i++) {
    for (j = 0; j < n - i - 1; j++) {
      if (v[j] > v[j + 1]) {
	temp = v[j];
	v[j] = v[j + 1];
	v[j + 1] = temp;
      }
      printf ("i:%d j:%d  ", i, j);
      print_array (v, n);
    }
  }
}

/* ------------------------------------------ */
int main () {
  int array[5]
  = { 300, 100, 200, 500, 400 };

  print_array (array, 5);
  bubble_sort (array, 5);
  print_array (array, 5);

  return 0;
}

ch12-insertion-100t-o50.c

/* code: ch12-insertion-100t-o50.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DATA_SIZE 100000
#define ORDERED   0.50
/* ------------------------------------------ */
int int_compare (const void *va, const void *vb) {
  int a, b;
  a = *(int *) va;
  b = *(int *) vb;
  if (a < b) {
    return (-1);
  }
  else if (a > b) {
    return (1);
  }
  else {
    return (0);
  }
}


/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;

  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
void insertion_sort (int v[], int n) {
  int i, j, t;
  for (i = 1; i < n; i++) {
    j = i;
    while ((j >= 1) && (v[j - 1] > v[j])) {
      t = v[j];
      v[j] = v[j - 1];
      v[j - 1] = t;
      j--;
    }
  }
}

/* ------------------------------------------ */
int main () {
  int *array;
  int i, n;
  float ord;
  clock_t t_start, t_end;

  n = DATA_SIZE;
  ord = ORDERED;
  array = malloc (sizeof (int) * n);

  for (i = 0; i < n; i++) {
    array[i] = rand () % n;
  }
  qsort (array, n * ord, sizeof (int), int_compare);


  printf ("#data:  %d  (o:%.2f%%)\n", n, ord * 100.0);
  printf ("input:  ");
  print_array (array, 10);

  t_start = clock ();
  insertion_sort (array, n);
  t_end = clock ();

  printf ("output: ");
  print_array (array, 10);
  printf ("time: %.3lf sec.\n",
	  (double) (t_end - t_start) / (double) CLOCKS_PER_SEC);

  free (array);

  return 0;
}

ch12-insertion-100t-o95.c

/* code: ch12-insertion-100t-o95.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DATA_SIZE 100000
#define ORDERED   0.95
/* ------------------------------------------ */
int int_compare (const void *va, const void *vb) {
  int a, b;
  a = *(int *) va;
  b = *(int *) vb;
  if (a < b) {
    return (-1);
  }
  else if (a > b) {
    return (1);
  }
  else {
    return (0);
  }
}


/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;

  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
void insertion_sort (int v[], int n) {
  int i, j, t;
  for (i = 1; i < n; i++) {
    j = i;
    while ((j >= 1) && (v[j - 1] > v[j])) {
      t = v[j];
      v[j] = v[j - 1];
      v[j - 1] = t;
      j--;
    }
  }
}


/* ------------------------------------------ */
int main () {
  int *array;
  int i, n;
  float ord;
  clock_t t_start, t_end;

  n = DATA_SIZE;
  ord = ORDERED;
  array = malloc (sizeof (int) * n);

  for (i = 0; i < n; i++) {
    array[i] = rand () % n;
  }
  qsort (array, n * ord, sizeof (int), int_compare);


  printf ("#data:  %d  (o:%.2f%%)\n", n, ord * 100.0);
  printf ("input:  ");
  print_array (array, 10);

  t_start = clock ();
  insertion_sort (array, n);
  t_end = clock ();

  printf ("output: ");
  print_array (array, 10);
  printf ("time: %.3lf sec.\n",
	  (double) (t_end - t_start) / (double) CLOCKS_PER_SEC);

  free (array);

  return 0;
}

ch12-insertion-100t-r.c

/* code: ch12-insertion-100t-r.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DATA_SIZE 100000

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;

  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}


/* ------------------------------------------ */
void insertion_sort (int v[], int n) {
  int i, j, t;
  for (i = 1; i < n; i++) {
    j = i;
    while ((j >= 1) && (v[j - 1] > v[j])) {
      t = v[j];
      v[j] = v[j - 1];
      v[j - 1] = t;
      j--;
    }
  }
}

/* ------------------------------------------ */
int main () {
  int *array;
  int i, n;
  clock_t t_start, t_end;

  n = DATA_SIZE;
  array = malloc (sizeof (int) * n);

  for (i = 0; i < n; i++) {
    array[i] = rand () % n;
  }

  printf ("#data:  %d\n", n);
  printf ("input:  ");
  print_array (array, 10);

  t_start = clock ();
  insertion_sort (array, n);
  t_end = clock ();

  printf ("output: ");
  print_array (array, 10);
  printf ("time: %.3lf sec.\n",
	  (double) (t_end - t_start) / (double) CLOCKS_PER_SEC);

  free (array);

  return 0;
}

ch12-insertion-5.c

/* code: ch12-insertion-5.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
void insertion_sort (int v[], int n) {
  int i, j, t;
  for (i = 1; i < n; i++) {
    j = i;
    while ((j >= 1) && (v[j - 1] > v[j])) {
      t = v[j];
      v[j] = v[j - 1];
      v[j - 1] = t;
      j--;
      printf ("i:%d j:%d  ", i, j);
      print_array (v, n);
    }
  }
}

/* ------------------------------------------ */
int main () {
  int array[5]
  = { 300, 100, 200, 500, 400 };

  print_array (array, 5);
  insertion_sort (array, 5);
  print_array (array, 5);

  return 0;
}

ch12-insertion-5o.c

/* code: ch12-insertion-5o.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
void insertion_sort (int v[], int n) {
  int i, j, t;
  for (i = 1; i < n; i++) {
    j = i;
    while ((j >= 1) && (v[j - 1] > v[j])) {
      t = v[j];
      v[j] = v[j - 1];
      v[j - 1] = t;
      j--;
      printf ("i:%d j:%d  ", i, j);
      print_array (v, n);
    }
  }
}

/* ------------------------------------------ */
int main () {
  int array[5]
  = { 100, 200, 300, 400, 500 };

  print_array (array, 5);
  insertion_sort (array, 5);
  print_array (array, 5);
  return 0;
}

ch12-insertion-5r.c

/* code: ch12-insertion-5r.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
void insertion_sort (int v[], int n) {
  int i, j, t;
  for (i = 1; i < n; i++) {
    j = i;
    while ((j >= 1) && (v[j - 1] > v[j])) {
      t = v[j];
      v[j] = v[j - 1];
      v[j - 1] = t;
      j--;
      printf ("i:%d j:%d  ", i, j);
      print_array (v, n);
    }
  }
}

/* ------------------------------------------ */
int main () {
  int array[5]
  = { 500, 400, 300, 200, 100 };

  print_array (array, 5);
  insertion_sort (array, 5);
  print_array (array, 5);

  return 0;
}

ch12-quicksort-t100.c

/* code: ch12-quicksort-t100.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DATA_SIZE 100000

/* ------------------------------------------ */
int int_compare (const void *va, const void *vb) {
  int a, b;
  a = *(int *) va;
  b = *(int *) vb;
  if (a < b) {
    return (-1);
  }
  else if (a > b) {
    return (1);
  }
  else {
    return (0);
  }
}


/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;

  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
void bubble_sort (int v[], int n) {
  int i, j, temp;
  for (i = 0; i < n - 1; i++) {
    for (j = 0; j < n - i - 1; j++) {
      if (v[j] > v[j + 1]) {
	temp = v[j];
	v[j] = v[j + 1];
	v[j + 1] = temp;
      }
    }
  }
}


/* ------------------------------------------ */
void bubble_sort2 (int v[], int n) {
  int i, j, temp, flag;

  flag = 1;
  for (i = 0; (i < n - 1) && (flag == 1); i++) {
    flag = 0;
    for (j = 0; j < n - i - 1; j++) {
      if (v[j] > v[j + 1]) {
	temp = v[j];
	v[j] = v[j + 1];
	v[j + 1] = temp;
	flag = 1;
      }
    }
  }
}


/* ------------------------------------------ */
int partition (int v[], int lower_bound, int upper_bound) {
  int a, down, up, temp;

  a = v[lower_bound];
  up = upper_bound;
  down = lower_bound;

  while (down < up) {
    while ((v[down] <= a) && (down < upper_bound)) {
      down++;
    }
    while (v[up] > a) {
      up--;
    }
    if (down < up) {
      temp = v[down];
      v[down] = v[up];
      v[up] = temp;
    }
  }
  v[lower_bound] = v[up];
  v[up] = a;
  return up;
}

/* ------------------------------------------ */
void quicksort (int v[], int left, int right) {
  int p;
  if (left >= right) {
    return;
  }
  p = partition (v, left, right);
  quicksort (v, left, p - 1);
  quicksort (v, p + 1, right);
}

/* ------------------------------------------ */
int main () {
  int *array;
  int i, n;
  clock_t t_start, t_end;

  n = DATA_SIZE;

  array = malloc (sizeof (int) * n);

  for (i = 0; i < n; i++) {
    array[i] = rand () % n;
  }

  printf ("#data:  %d\n", n);
  printf ("input:  ");
  print_array (array, 10);

  t_start = clock ();
  quicksort (array, 0, n - 1);
  t_end = clock ();

  printf ("output: ");
  print_array (array, 10);
  printf ("time: %.3lf sec.\n",
	  (double) (t_end - t_start) / (double) CLOCKS_PER_SEC);

  free (array);

  return 0;
}

ch12-selection-100t-r.c

/* code: ch12-selection-100t-r.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DATA_SIZE 100000

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;

  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}


/* ------------------------------------------ */
void selection_sort (int v[], int n) {
  int i, j, t, min_index;
  for (i = 0; i < n - 1; i++) {
    min_index = i;
    for (j = i + 1; j < n; j++) {
      if (v[j] < v[min_index]) {
	min_index = j;
      }
    }
    t = v[i];
    v[i] = v[min_index];
    v[min_index] = t;
  }
}

/* ------------------------------------------ */
int main () {
  int *array;
  int i, n;
  clock_t t_start, t_end;

  n = DATA_SIZE;
  array = malloc (sizeof (int) * n);

  for (i = 0; i < n; i++) {
    array[i] = rand () % n;
  }

  printf ("#data:  %d\n", n);
  printf ("input:  ");
  print_array (array, 10);

  t_start = clock ();
  selection_sort (array, n);
  t_end = clock ();

  printf ("output: ");
  print_array (array, 10);
  printf ("time: %.3lf sec.\n",
	  (double) (t_end - t_start) / (double) CLOCKS_PER_SEC);

  free (array);

  return 0;
}

ch12-selection-5.c

/* code: ch12-selection-5.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
void selection_sort (int v[], int n) {
  int i, j, t, min_index;
  for (i = 0; i < n - 1; i++) {
    min_index = i;
    for (j = i + 1; j < n; j++) {
      if (v[j] < v[min_index]) {
	min_index = j;
      }
      printf ("i:%d j:%d  ", i, j);
      print_array (v, n);
    }
    t = v[i];
    v[i] = v[min_index];
    v[min_index] = t;
  }
}

/* ------------------------------------------ */
int main () {
  int array[5]
  = { 300, 100, 200, 500, 400 };

  print_array (array, 5);
  selection_sort (array, 5);
  print_array (array, 5);

  return 0;
}

ch13-mergesort-100m.c

/* code: ch13-mergesort-100m.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#define MAX 100000000
/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
void rand_data (int v[], int n) {
  int i;
  for (i = 0; i < n; i++) {
    v[i] = rand () % (MAX / 10);
  }
}

/* ------------------------------------------ */
void merge_sort (int v[], int lb, int ub, int v_temp[]) {
  int i, j, k, c;

  if (lb >= ub) {
    return;
  }
  c = (lb + ub) / 2;

  merge_sort (v, lb, c, v_temp);
  merge_sort (v, c + 1, ub, v_temp);

  for (i = lb; i <= c; i++) {
    v_temp[i] = v[i];
  }
  for (i = c + 1, j = ub; i <= ub; i++, j--) {
    v_temp[i] = v[j];
  }

  i = lb;
  j = ub;

  for (k = lb; k <= ub; k++) {
    if (v_temp[i] <= v_temp[j]) {
      v[k] = v_temp[i++];
    }
    else {
      v[k] = v_temp[j--];
    }
  }
}

/* ------------------------------------------ */
int main () {
  int *array;
  int *array_temp;


  array = malloc (sizeof (int) * MAX);
  array_temp = malloc (sizeof (int) * MAX);

  if (array == NULL) {
    printf ("ERROR: Can not allocate memory\n");
    exit (-1);
  }

  rand_data (array, MAX);
  printf ("array size: %d\n", MAX);
  fflush (stdout);

  print_array (array, 30);

  merge_sort (array, 0, MAX - 1, array_temp);

  print_array (array, 30);


  free (array_temp);
  free (array);


  return 0;
}

ch13-mergesort.c

/* code: ch13-mergesort.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%02d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
void merge_sort (int v[], int lb, int ub, int v_temp[]) {
  int i, j, k, c;

  if (lb >= ub) {
    return;
  }
  c = (lb + ub) / 2;

  merge_sort (v, lb, c, v_temp);
  merge_sort (v, c + 1, ub, v_temp);

  for (i = lb; i <= c; i++) {
    v_temp[i] = v[i];
  }
  for (i = c + 1, j = ub; i <= ub; i++, j--) {
    v_temp[i] = v[j];
  }

  i = lb;
  j = ub;

  for (k = lb; k <= ub; k++) {
    if (v_temp[i] <= v_temp[j]) {
      v[k] = v_temp[i++];
    }
    else {
      v[k] = v_temp[j--];
    }
  }
}

/* ------------------------------------------ */
int main () {
  int array[10]
  = { 80, 40, 30, 20, 10, 00, 70, 90, 50, 60 };

  int array_temp[10];

  print_array (array, 10);
  merge_sort (array, 0, 9, array_temp);
  print_array (array, 10);

  return 0;
}

ch13-qsort-100t.c

/* code: ch13-qsort-100t.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#define MAX 100000

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
void rand_data (int v[], int n) {
  int i;
  for (i = 0; i < n; i++) {
    v[i] = rand () % (MAX / 10);
  }
}

/* ------------------------------------------ */
int int_compare (const void *va, const void *vb) {
  int a, b;
  a = *(int *) va;
  b = *(int *) vb;
  if (a < b) {
    return (-1);
  }
  else if (a > b) {
    return (1);
  }
  else {
    return (0);
  }
}

/* ------------------------------------------ */
int main () {
  int *array;

  array = malloc (sizeof (int) * MAX);

  rand_data (array, MAX);
  printf ("array size: %d\n", MAX);
  fflush (stdout);

  print_array (array, 10);
  qsort (array, MAX, sizeof (int), int_compare);
  print_array (array, 10);

  free (array);

  return 0;
}

ch13-qsort-str.c

/* code: ch13-qsort-str.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* ------------------------------------------ */
int cmp_string (const void *p1, const void *p2) {
  return strcmp (*(char *const *) p1, *(char *const *) p2);
}

/* ------------------------------------------ */
void print_str_array (char *v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%s ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
int main () {
  char *array[7] = {
    "Sunday", "Monday", "Tuesday",
    "Wednesday", "Thursday", "Friday", "Saturday",
  };
  print_str_array (array, 7);
  qsort (array, 7, sizeof (char *), cmp_string);
  print_str_array (array, 7);
  return 0;
}

ch13-qsort.c

/* code: ch13-qsort.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%02d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
int int_compare (const void *va, const void *vb) {
  int a, b;
  a = *(int *) va;
  b = *(int *) vb;
  if (a < b) {
    return (-1);
  }
  else if (a > b) {
    return (1);
  }
  else {
    return (0);
  }
}

/* ------------------------------------------ */
int main () {
  int array[10]
  = { 80, 40, 30, 20, 10, 00, 70, 90, 50, 60 };

  print_array (array, 10);
  qsort (array, 10, sizeof (int), int_compare);
  print_array (array, 10);

  return 0;
}

ch13-quicksort-10.c

/* code: ch13-quicksort-10.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%02d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
int partition (int v[], int lower_bound, int upper_bound) {
  int a, down, up, temp;

  a = v[lower_bound];
  up = upper_bound;
  down = lower_bound;

  while (down < up) {
    while ((v[down] <= a) && (down < upper_bound)) {
      down++;
    }
    while (v[up] > a) {
      up--;
    }
    if (down < up) {
      temp = v[down];
      v[down] = v[up];
      v[up] = temp;
    }
  }
  v[lower_bound] = v[up];
  v[up] = a;
  return up;
}

/* ------------------------------------------ */
void quicksort (int v[], int left, int right) {
  int p;
  if (left >= right) {
    return;
  }
  p = partition (v, left, right);
  quicksort (v, left, p - 1);
  quicksort (v, p + 1, right);
}

/* ------------------------------------------ */
int main () {
  int array[10]
  = { 80, 40, 30, 20, 10, 00, 70, 90, 50, 60 };

  print_array (array, 10);
  quicksort (array, 0, 9);
  print_array (array, 10);

  return 0;
}

ch13-quicksort-100m.c

/* code: ch13-quicksort-100m.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

#define MAX 100000000

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
void rand_data (int v[], int n) {
  int i;
  for (i = 0; i < n; i++) {
    v[i] = rand () % (MAX / 10);
  }
}

/* ------------------------------------------ */
int partition (int v[], int lower_bound, int upper_bound) {
  int a, down, up, temp;

  a = v[lower_bound];
  up = upper_bound;
  down = lower_bound;

  while (down < up) {
    while ((v[down] <= a) && (down < upper_bound)) {
      down++;
    }
    while (v[up] > a) {
      up--;
    }
    if (down < up) {
      temp = v[down];
      v[down] = v[up];
      v[up] = temp;
    }
  }
  v[lower_bound] = v[up];
  v[up] = a;
  return up;
}

/* ------------------------------------------ */
void quicksort (int v[], int left, int right) {
  int p;
  if (left >= right) {
    return;
  }
  p = partition (v, left, right);
  quicksort (v, left, p - 1);
  quicksort (v, p + 1, right);
}

/* ------------------------------------------ */
int main () {
  int *array;

  array = malloc (sizeof (int) * MAX);
  if (array == NULL) {
    printf ("ERROR: Can not allocate memory\n");
    exit (-1);
  }

  rand_data (array, MAX);
  printf ("array size: %d\n", MAX);
  fflush (stdout);

  print_array (array, 30);

  quicksort (array, 0, MAX - 1);

  print_array (array, 30);

  free (array);
  return 0;
}

ch13-quicksort-100t-r.c

/* code: ch13-quicksort-100t-r.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DATA_SIZE 100000

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;

  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
void rand_data (int v[], int n) {
  int i;
  for (i = 0; i < n; i++) {
    v[i] = rand () % (DATA_SIZE / 10);
  }
}

/* ------------------------------------------ */
int partition (int v[], int lower_bound, int upper_bound) {
  int a, down, up, temp;

  a = v[lower_bound];
  up = upper_bound;
  down = lower_bound;

  while (down < up) {
    while ((v[down] <= a) && (down < upper_bound)) {
      down++;
    }
    while (v[up] > a) {
      up--;
    }
    if (down < up) {
      temp = v[down];
      v[down] = v[up];
      v[up] = temp;
    }
  }
  v[lower_bound] = v[up];
  v[up] = a;
  return up;
}

/* ------------------------------------------ */
void quicksort (int v[], int left, int right) {
  int p;
  if (left >= right) {
    return;
  }
  p = partition (v, left, right);
  quicksort (v, left, p - 1);
  quicksort (v, p + 1, right);
}

/* ------------------------------------------ */
int main () {
  int *array;
  int i, n;
  clock_t t_start, t_end;

  n = DATA_SIZE;
  array = malloc (sizeof (int) * DATA_SIZE);
  for (i = 0; i < n; i++) {
    array[i] = rand () % n;
  }

  // rand_data (array, DATA_SIZE);
  printf ("#data:  %d\n", DATA_SIZE);
  fflush (stdout);

  printf ("input:  ");
  print_array (array, 10);

  t_start = clock ();
  quicksort (array, 0, DATA_SIZE - 1);
  t_end = clock ();

  printf ("output: ");
  print_array (array, 10);
  printf ("time: %.3lf sec.\n",
	  (double) (t_end - t_start) / (double) CLOCKS_PER_SEC);
  free (array);

  return 0;
}

ch13-quicksort-100t-t.c

/* code: ch13-quicksort-100t-t.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

#define MAX 1000000

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
  fflush (stdout);
}

/* ------------------------------------------ */
void rand_data (int v[], int n) {
  int i;
  for (i = 0; i < n; i++) {
    v[i] = rand () % (MAX / 10);
  }
}

/* ------------------------------------------ */
int partition (int v[], int lower_bound, int upper_bound) {
  int a, down, up, temp;

  a = v[lower_bound];
  up = upper_bound;
  down = lower_bound;

  while (down < up) {
    while ((v[down] <= a) && (down < upper_bound)) {
      down++;
    }
    while (v[up] > a) {
      up--;
    }
    if (down < up) {
      temp = v[down];
      v[down] = v[up];
      v[up] = temp;
    }
  }
  v[lower_bound] = v[up];
  v[up] = a;
  return up;
}

/* ------------------------------------------ */
void quicksort (int v[], int left, int right) {
  int p;
  if (left >= right) {
    return;
  }
  p = partition (v, left, right);
  quicksort (v, left, p - 1);
  quicksort (v, p + 1, right);
}

/* ------------------------------------------ */
int main () {
  int *array;

  array = malloc (sizeof (int) * MAX);

  rand_data (array, MAX);
  printf ("array size: %d\n", MAX);
  fflush (stdout);

  printf ("Quicksort (1st)\n");
  print_array (array, 30);
  quicksort (array, 0, MAX - 1);
  print_array (array, 30);

  printf ("\n");

  printf ("Quicksort (2nd)\n");
  print_array (array, 30);
  quicksort (array, 0, MAX - 1);
  print_array (array, 30);


  free (array);

  return 0;
}

ch13-quicksort-100t.c

/* code: ch13-quicksort-100t.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

#define MAX 100000

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
void rand_data (int v[], int n) {
  int i;
  for (i = 0; i < n; i++) {
    v[i] = rand () % (MAX / 10);
  }
}

/* ------------------------------------------ */
int partition (int v[], int lower_bound, int upper_bound) {
  int a, down, up, temp;

  a = v[lower_bound];
  up = upper_bound;
  down = lower_bound;

  while (down < up) {
    while ((v[down] <= a) && (down < upper_bound)) {
      down++;
    }
    while (v[up] > a) {
      up--;
    }
    if (down < up) {
      temp = v[down];
      v[down] = v[up];
      v[up] = temp;
    }
  }
  v[lower_bound] = v[up];
  v[up] = a;
  return up;
}

/* ------------------------------------------ */
void quicksort (int v[], int left, int right) {
  int p;
  if (left >= right) {
    return;
  }
  p = partition (v, left, right);
  quicksort (v, left, p - 1);
  quicksort (v, p + 1, right);
}

/* ------------------------------------------ */
int main () {
  int *array;

  array = malloc (sizeof (int) * MAX);

  rand_data (array, MAX);
  printf ("array size: %d\n", MAX);
  fflush (stdout);

  print_array (array, 30);
  quicksort (array, 0, MAX - 1);
  print_array (array, 30);

  free (array);

  return 0;
}

ch13-quicksort-stack-10.c

/* code: ch13-quicksort-stack-10.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#define STACK_SIZE 2048

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%02d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------ */
int partition (int v[], int lower_bound, int upper_bound) {
  int a, down, up, temp;

  a = v[lower_bound];
  up = upper_bound;
  down = lower_bound;

  while (down < up) {
    while ((v[down] <= a) && (down < upper_bound)) {
      down++;
    }
    while (v[up] > a) {
      up--;
    }
    if (down < up) {
      temp = v[down];
      v[down] = v[up];
      v[up] = temp;
    }
  }
  v[lower_bound] = v[up];
  v[up] = a;
  return up;
}

/* ------------------------------------------ */
void quicksort_stack (int v[], int n) {
  int left, right, i, sptr;
  int stack_lower_bound[STACK_SIZE];
  int stack_upper_bound[STACK_SIZE];

  stack_lower_bound[0] = 0;
  stack_upper_bound[0] = n - 1;
  sptr = 1;

  while (sptr > 0) {
    sptr--;
    left = stack_lower_bound[sptr];
    right = stack_upper_bound[sptr];

    if (left >= right) {
      ;
    }
    else {
      i = partition (v, left, right);

      if ((i - left) < (right - i)) {
	stack_lower_bound[sptr] = i + 1;
	stack_upper_bound[sptr++] = right;
	stack_lower_bound[sptr] = left;
	stack_upper_bound[sptr++] = i - 1;
      }
      else {
	stack_lower_bound[sptr] = left;
	stack_upper_bound[sptr++] = i - 1;
	stack_lower_bound[sptr] = i + 1;
	stack_upper_bound[sptr++] = right;
      }
    }
  }
}


/* ------------------------------------------ */
int main () {
  int array[10]
  = { 80, 40, 30, 20, 10, 00, 70, 90, 50, 60 };

  print_array (array, 10);
  quicksort_stack (array, 10);
  print_array (array, 10);

  return 0;
}

ch14-heap-10.c

/* code: ch14-heap-10.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%02d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------- */
int heap_max (int *v, int n, int i, int j, int k) {
  int max;

  max = i;
  if ((j < n) && (v[j] > v[max])) {
    max = j;
  }
  if ((k < n) && (v[k] > v[max])) {
    max = k;
  }
  return max;
}

/* ------------------------------------------- */
void downheap (int *v, int n, int i) {
  int left, right, j, temp;
  while (1) {
    left = 2 * i + 1;
    right = 2 * i + 2;
    j = heap_max (v, n, i, left, right);
    if (j == i) {
      break;
    }
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
    i = j;
  }
}

/* ------------------------------------------- */
void heapsort (int *v, int n) {
  int i, temp;
  for (i = (n - 2) / 2; i >= 0; i--) {
    downheap (v, n, i);
  }
  for (i = 0; i < n; i++) {
    temp = v[n - i - 1];
    v[n - i - 1] = v[0];
    v[0] = temp;
    downheap (v, n - i - 1, 0);
  }
}

/* ------------------------------------------- */
int main () {
  int array[10]
  = { 80, 40, 30, 20, 10, 00, 70, 90, 50, 60 };

  print_array (array, 10);
  heapsort (array, 10);
  print_array (array, 10);

  return 0;
}

ch14-heap-pq.c

/* code: ch14-heap-pq.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#define MAX_PQ_SIZE 128
#define NODE_PARENT(x) ((x - 1) / 2)
#define NODE_LEFT(x) (2 * x + 1)
#define NODE_RIGHT(x) (2 * x + 2)

struct node {
  int priority;
  char data[32];
};
typedef struct node NODE;

struct p_queue {
  int size;
  NODE *elm;
};
typedef struct p_queue P_QUEUE;

/* ------------------------------------------- */
void pq_node_swap (NODE * n1, NODE * n2) {
  NODE node_temp;
  node_temp = *n1;
  *n1 = *n2;
  *n2 = node_temp;
}

/* ------------------------------------------- */
P_QUEUE pq_init (int size) {
  P_QUEUE pq;
  pq.size = 0;
  pq.elm = malloc (size * sizeof (NODE));
  return pq;
}

/* ------------------------------------------- */
void pq_delete_all (P_QUEUE * pq) {
  free (pq->elm);
}

/* ------------------------------------------- */
void pq_display (P_QUEUE * pq) {
  int i;
  for (i = 0; i < pq->size; i++) {
    printf ("heap    (%d) (%s)\n", pq->elm[i].priority, pq->elm[i].data);
  }
}

/* ------------------------------------------- */
void pq_heapify (P_QUEUE * pq, int i) {
  int max;
  max = ((NODE_LEFT (i) < pq->size)
	 && (pq->elm[NODE_LEFT (i)].priority >
	     pq->elm[i].priority)) ? NODE_LEFT (i) : i;

  if ((NODE_RIGHT (i) < pq->size)
      && (pq->elm[NODE_RIGHT (i)].priority > pq->elm[max].priority)) {
    max = NODE_RIGHT (i);
  }
  if (max != i) {
    pq_node_swap (&(pq->elm[i]), &(pq->elm[max]));
    pq_heapify (pq, max);
  }
}

/* ------------------------------------------- */
void pq_enqueue (P_QUEUE * pq, int priority, char *data) {
  NODE node;
  int i;

  node.priority = priority;
  sprintf (node.data, "%s", data);
  printf ("enqueue (%2d)(%s)\n", node.priority, node.data);
  i = (pq->size)++;
  while (i && node.priority > pq->elm[NODE_PARENT (i)].priority) {
    pq->elm[i] = pq->elm[NODE_PARENT (i)];
    i = NODE_PARENT (i);
  }
  pq->elm[i] = node;
}

/* ------------------------------------------- */
void pq_dequeue (P_QUEUE * pq) {
  if (pq->size) {
    printf ("dequeue (%2d)(%s)\n", pq->elm[0].priority, pq->elm[0].data);
    pq->elm[0] = pq->elm[--(pq->size)];
    pq->elm = realloc (pq->elm, pq->size * sizeof (NODE));
    pq_heapify (pq, 0);
  }
  else {
    printf ("priority queue is empty\n");
  }
}

/* ------------------------------------------- */
int main () {
  P_QUEUE pq;
  int i;

  pq = pq_init (MAX_PQ_SIZE);
  pq_enqueue (&pq, 40, "grape");
  pq_enqueue (&pq, 30, "pear");
  pq_enqueue (&pq, 10, "banana");
  pq_enqueue (&pq, 20, "watermelon");
  pq_enqueue (&pq, 50, "apple");
  pq_enqueue (&pq, 60, "lemon");
  pq_display (&pq);
  for (i = 0; i < 7; i++) {
    pq_dequeue (&pq);
  }
  pq_delete_all (&pq);

  return 0;
}

ch14-heapsort-100m.c

/* code: ch14-heapsort-100m.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

#define MAX 100000000

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------- */
int heap_max (int *v, int n, int i, int j, int k) {
  int max;

  max = i;
  if ((j < n) && (v[j] > v[max])) {
    max = j;
  }
  if ((k < n) && (v[k] > v[max])) {
    max = k;
  }
  return max;
}

/* ------------------------------------------- */
void downheap (int *v, int n, int i) {
  int left, right, j, temp;
  while (1) {
    left = 2 * i + 1;
    right = 2 * i + 2;
    j = heap_max (v, n, i, left, right);
    if (j == i) {
      break;
    }
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
    i = j;
  }
}

/* ------------------------------------------- */
void heapsort (int *v, int n) {
  int i, temp;
  for (i = (n - 2) / 2; i >= 0; i--) {
    downheap (v, n, i);
  }
  for (i = 0; i < n; i++) {
    temp = v[n - i - 1];
    v[n - i - 1] = v[0];
    v[0] = temp;
    downheap (v, n - i - 1, 0);
  }
}


/* ------------------------------------------ */
void rand_data (int v[], int n) {
  int i;
  for (i = 0; i < n; i++) {
    v[i] = rand () % (MAX / 10);
  }
}

/* ------------------------------------------- */
int main () {
  int *array;

  array = malloc (sizeof (int) * MAX);

  rand_data (array, MAX);
  print_array (array, 30);
  heapsort (array, MAX);
  print_array (array, 30);

  free (array);
  return 0;
}

ch14-heapsort-100t.c

/* code: ch14-heapsort-100t.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

#define MAX 100000

/* ------------------------------------------ */
void print_array (int v[], int n) {
  int i;
  printf ("array: ");
  for (i = 0; i < n; i++) {
    printf ("%d ", v[i]);
  }
  printf ("\n");
}

/* ------------------------------------------- */
int heap_max (int *v, int n, int i, int j, int k) {
  int max;

  max = i;
  if ((j < n) && (v[j] > v[max])) {
    max = j;
  }
  if ((k < n) && (v[k] > v[max])) {
    max = k;
  }
  return max;
}

/* ------------------------------------------- */
void downheap (int *v, int n, int i) {
  int left, right, j, temp;
  while (1) {
    left = 2 * i + 1;
    right = 2 * i + 2;
    j = heap_max (v, n, i, left, right);
    if (j == i) {
      break;
    }
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
    i = j;
  }
}

/* ------------------------------------------- */
void heapsort (int *v, int n) {
  int i, temp;
  for (i = (n - 2) / 2; i >= 0; i--) {
    downheap (v, n, i);
  }
  for (i = 0; i < n; i++) {
    temp = v[n - i - 1];
    v[n - i - 1] = v[0];
    v[0] = temp;
    downheap (v, n - i - 1, 0);
  }
}


/* ------------------------------------------ */
void rand_data (int v[], int n) {
  int i;
  for (i = 0; i < n; i++) {
    v[i] = rand () % (MAX / 10);
  }
}

/* ------------------------------------------- */
int main () {
  int *array;

  array = malloc (sizeof (int) * MAX);

  rand_data (array, MAX);
  print_array (array, 30);
  heapsort (array, MAX);
  print_array (array, 30);

  free (array);
  return 0;
}

ch15-graph-bfs.c

/* code: ch15-graph-bfs.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

#define MAX 128

#define TRUE (1)
#define FALSE (0)

#define ENQUEUE_SUCCESS     (1)
#define ENQUEUE_FAILURE    (-1)
#define DEQUEUE_SUCCESS     (2)
#define DEQUEUE_FAILURE    (-2)
#define QUEUE_NOT_EMPTY     (3)
#define QUEUE_EMPTY        (-3)

struct Vertex {
  char label;
  int visited;
};
typedef struct Vertex VERTEX_TYPE;

/* ------------------------------------------- */
void queue_init (int *front, int *rear) {
  *front = -1;
  *rear = -1;
}

/* ------------------------------------------- */
int is_queue_empty (int front, int rear) {
  if (front == rear) {
    return QUEUE_EMPTY;
  }
  else {
    return QUEUE_NOT_EMPTY;
  }
}

/* ------------------------------------------- */
void queue_print (int q[], int front, int rear) {
  int i;

  printf ("QUEUE[ ");
  for (i = front + 1; i <= rear; i++) {
    printf ("%c", q[i] + 'a');
  }
  printf (" ]\n");
}

/* ------------------------------------------- */
int enqueue (int q[], int *rear, int data) {
  if (*rear < MAX - 1) {
    *rear = *rear + 1;
    q[*rear] = data;
    return ENQUEUE_SUCCESS;
  }
  else {
    return ENQUEUE_FAILURE;
  }
}

/* ------------------------------------------- */
int dequeue (int q[], int *front, int rear, int *data) {
  if (*front == rear) {
    return DEQUEUE_FAILURE;
  }
  *front = *front + 1;
  *data = q[*front];
  return DEQUEUE_SUCCESS;
}

/* ------------------------------------------- */
int **m2d_allocate (int rows, int columns) {
  int **array;
  int i;
  array = malloc (rows * sizeof (int *));
  for (i = 0; i < rows; i++) {
    array[i] = malloc (columns * sizeof (int));
  }
  return array;
}

/* ------------------------------------------- */
void m2d_deallocate (int **array, int rows) {
  int i;
  for (i = 0; i < rows; i++) {
    free (array[i]);
  }
  free (array);
}

/* ------------------------------------------- */
void g_matrix_init (int **adj_matrix, int max_i, int max_j) {
  int i, j;
  for (i = 0; i < max_i; i++) {
    for (j = 0; j < max_j; j++) {
      adj_matrix[i][j] = 0;
    }
  }
}

/* ------------------------------------------- */
void g_matrix_print (int **adj_matrix, int max_i, int max_j) {
  int i, j;
  printf ("  ");
  for (i = 0; i < max_i; i++) {
    printf ("%c", 'a' + i);
  }
  printf ("\n");
  for (i = 0; i < max_i; i++) {
    printf ("%c ", 'a' + i);
    for (j = 0; j < max_j; j++) {
      printf ("%d", adj_matrix[i][j]);
    }
    printf ("\n");
  }
  printf ("\n");
}

/* ------------------------------------------- */
int g_add_vertex (int **adj_matrix, VERTEX_TYPE * vert_list[MAX],
		  int vert_num, char label) {
  VERTEX_TYPE *vertex;

  vertex = malloc (sizeof (struct Vertex));
  vertex->label = label;
  vertex->visited = FALSE;
  vert_list[vert_num++] = vertex;

  return vert_num;
}

/* ------------------------------------------- */
void g_add_edge (int **adj_matrix, char label_start, char label_end) {
  int start, end;
  start = label_start - 'a';
  end = label_end - 'a';
  adj_matrix[start][end] = 1;
  adj_matrix[end][start] = 1;
}

/* ------------------------------------------- */
void g_print_vertex (int vert_index, VERTEX_TYPE * vert_list[MAX]) {
  printf ("'%c'\n", vert_list[vert_index]->label);
}

/* ------------------------------------------- */
int g_vertex_unvisited (int **adj_matrix, int vert_index,
			VERTEX_TYPE * vert_list[MAX], int vert_num) {
  int i;
  for (i = 0; i < vert_num; i++) {
    if ((adj_matrix[vert_index][i] == 1)
	&& (vert_list[i]->visited == FALSE)) {
      return i;
    }
  }
  return -1;
}

/* ------------------------------------------- */
void breadth_first_search (int **adj_matrix,
			   VERTEX_TYPE * vert_list[MAX], int vert_num) {
  int i;
  int queue[MAX];
  int front, rear, data;
  int unvisited;

  data = 0;
  queue_init (&front, &rear);

  vert_list[0]->visited = TRUE;
  g_print_vertex (0, vert_list);

  enqueue (queue, &rear, 0);
  printf ("enqueue (%c) ", data + 'a');
  queue_print (queue, front, rear);

  while (QUEUE_NOT_EMPTY == is_queue_empty (front, rear)) {
    dequeue (queue, &front, rear, &data);
    printf ("dequeue (%c) ", data + 'a');
    queue_print (queue, front, rear);

    while ((unvisited =
	    g_vertex_unvisited (adj_matrix, data, vert_list,
				vert_num)) != -1) {
      vert_list[unvisited]->visited = TRUE;

      g_print_vertex (unvisited, vert_list);

      enqueue (queue, &rear, unvisited);
      printf ("enqueue (%c) ", unvisited + 'a');
      queue_print (queue, front, rear);
    }
  }
  for (i = 0; i < vert_num; i++) {
    vert_list[i]->visited = FALSE;
  }
}

/* ------------------------------------------- */
int main () {
  int **adj_matrix;
  VERTEX_TYPE *vert_list[MAX];
  int vert_num;

  vert_num = 0;
  adj_matrix = m2d_allocate (MAX, MAX);
  g_matrix_init (adj_matrix, MAX, MAX);

  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'a');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'b');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'c');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'd');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'e');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'f');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'g');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'h');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'i');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'j');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'k');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'l');

  g_add_edge (adj_matrix, 'a', 'b');
  g_add_edge (adj_matrix, 'a', 'c');
  g_add_edge (adj_matrix, 'b', 'd');
  g_add_edge (adj_matrix, 'b', 'e');
  g_add_edge (adj_matrix, 'd', 'f');
  g_add_edge (adj_matrix, 'e', 'g');
  g_add_edge (adj_matrix, 'e', 'h');
  g_add_edge (adj_matrix, 'g', 'i');
  g_add_edge (adj_matrix, 'g', 'j');
  g_add_edge (adj_matrix, 'h', 'k');
  g_add_edge (adj_matrix, 'i', 'l');
  g_add_edge (adj_matrix, 'j', 'l');

  g_matrix_print (adj_matrix, vert_num, vert_num);
  printf ("Breadth-First Search (BFS) \n");

  breadth_first_search (adj_matrix, vert_list, vert_num);

  m2d_deallocate (adj_matrix, MAX);
  printf ("\n");

  return 0;
}

ch15-graph-dfs.c

/* code: ch15-graph-dfs.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

#define MAX 128

#define TRUE (1)
#define FALSE (0)

#define PUSH_SUCCESS    (1)
#define PUSH_FAILURE   (-1)
#define POP_SUCCESS     (2)
#define POP_FAILURE    (-2)
#define PEEK_SUCCESS     (3)
#define PEEK_FAILURE    (-3)
#define STACK_NOT_EMPTY (4)
#define STACK_EMPTY     (-4)

struct Vertex {
  char label;
  int visited;
};
typedef struct Vertex VERTEX_TYPE;

/* ------------------------------------------- */
void stack_init (int *top) {
  *top = 0;
}

/* ------------------------------------------- */
void display (int stack[], int top) {
  int i;
  printf ("STACK(%d): ", top);
  for (i = 0; i < top; i++) {
    printf ("%d ", stack[i]);
  }
  printf ("\n");
}

/* ------------------------------------------- */
int push (int stack[], int *top, int data) {
  if (*top >= MAX) {
    /* stack overflow */
    return PUSH_FAILURE;
  }
  else {
    stack[*top] = data;
    (*top)++;
    return PUSH_SUCCESS;
  }
}

/* ------------------------------------------- */
int pop (int stack[], int *top, int *data) {
  if ((*top) > 0) {
    *data = stack[(*top) - 1];
    (*top)--;
    return POP_SUCCESS;
  }
  else {
    /* stack empty */
    return POP_FAILURE;
  }
}

/* ------------------------------------------- */
int peek (int stack[], int top, int *data) {
  if (top > 0) {
    *data = stack[top - 1];
    return PEEK_SUCCESS;
  }
  else {
    /* stack empty */
    return PEEK_FAILURE;
  }
}

/* ------------------------------------------- */
int is_stack_empty (int stack[], int top) {
  if (top > 0) {
    return STACK_NOT_EMPTY;
  }
  else {
    return STACK_EMPTY;
  }
}

/* ------------------------------------------- */
void stack_print (int stack[], int top) {
  int i;

  printf ("STACK[ ");
  for (i = 0; i < top; i++) {
    printf ("%c", stack[i] + 'a');
  }
  printf (" ]\n");
}



/* ------------------------------------------- */
int **m2d_allocate (int rows, int columns) {
  int **array;
  int i;
  array = malloc (rows * sizeof (int *));
  for (i = 0; i < rows; i++) {
    array[i] = malloc (columns * sizeof (int));
  }
  return array;
}

/* ------------------------------------------- */
void m2d_deallocate (int **array, int rows) {
  int i;
  for (i = 0; i < rows; i++) {
    free (array[i]);
  }
  free (array);
}

/* ------------------------------------------- */
void g_matrix_init (int **adj_matrix, int max_i, int max_j) {
  int i, j;
  for (i = 0; i < max_i; i++) {
    for (j = 0; j < max_j; j++) {
      adj_matrix[i][j] = 0;
    }
  }
}

/* ------------------------------------------- */
void g_matrix_print (int **adj_matrix, int max_i, int max_j) {
  int i, j;
  printf ("  ");
  for (i = 0; i < max_i; i++) {
    printf ("%c", 'a' + i);
  }
  printf ("\n");
  for (i = 0; i < max_i; i++) {
    printf ("%c ", 'a' + i);
    for (j = 0; j < max_j; j++) {
      printf ("%d", adj_matrix[i][j]);
    }
    printf ("\n");
  }
  printf ("\n");
}

/* ------------------------------------------- */
int g_add_vertex (int **adj_matrix, VERTEX_TYPE * vert_list[MAX],
		  int vert_num, char label) {
  VERTEX_TYPE *vertex;

  vertex = malloc (sizeof (struct Vertex));
  vertex->label = label;
  vertex->visited = FALSE;
  vert_list[vert_num++] = vertex;

  return vert_num;
}

/* ------------------------------------------- */
void g_add_edge (int **adj_matrix, char label_start, char label_end) {
  int start, end;
  start = label_start - 'a';
  end = label_end - 'a';
  adj_matrix[start][end] = 1;
  adj_matrix[end][start] = 1;
}

/* ------------------------------------------- */
void g_print_vertex (int vert_index, VERTEX_TYPE * vert_list[MAX]) {
  printf ("'%c'\n", vert_list[vert_index]->label);
}

/* ------------------------------------------- */
int g_vertex_unvisited (int **adj_matrix, int vert_index,
			VERTEX_TYPE * vert_list[MAX], int vert_num) {
  int i;
  for (i = 0; i < vert_num; i++) {
    if ((adj_matrix[vert_index][i] == 1)
	&& (vert_list[i]->visited == FALSE)) {
      return i;
    }
  }
  return -1;
}

/* ------------------------------------------- */
void depth_first_search (int **adj_matrix,
			 VERTEX_TYPE * vert_list[MAX], int vert_num) {
  int i;
  int stack[MAX];
  int top, data;
  int unvisited;

  data = 0;
  stack_init (&top);
  vert_list[0]->visited = TRUE;
  g_print_vertex (0, vert_list);
  push (stack, &top, 0);
  printf ("push (%c) ", data + 'a');
  stack_print (stack, top);

  while (STACK_NOT_EMPTY == is_stack_empty (stack, top)) {
    peek (stack, top, &data);
    unvisited = g_vertex_unvisited (adj_matrix, data, vert_list, vert_num);
    if (unvisited == -1) {
      pop (stack, &top, &data);
      printf ("pop  (%c) ", data + 'a');
      stack_print (stack, top);
    }
    else {
      vert_list[unvisited]->visited = TRUE;
      g_print_vertex (unvisited, vert_list);
      push (stack, &top, unvisited);
      printf ("push (%c) ", unvisited + 'a');
      stack_print (stack, top);
    }
  }

  for (i = 0; i < vert_num; i++) {
    vert_list[i]->visited = FALSE;
  }
}

/* ------------------------------------------- */
int main () {
  int **adj_matrix;
  VERTEX_TYPE *vert_list[MAX];
  int vert_num;

  vert_num = 0;
  adj_matrix = m2d_allocate (MAX, MAX);
  g_matrix_init (adj_matrix, MAX, MAX);

  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'a');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'b');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'c');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'd');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'e');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'f');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'g');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'h');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'i');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'j');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'k');
  vert_num = g_add_vertex (adj_matrix, vert_list, vert_num, 'l');

  g_add_edge (adj_matrix, 'a', 'b');
  g_add_edge (adj_matrix, 'a', 'c');
  g_add_edge (adj_matrix, 'b', 'd');
  g_add_edge (adj_matrix, 'b', 'e');
  g_add_edge (adj_matrix, 'd', 'f');
  g_add_edge (adj_matrix, 'e', 'g');
  g_add_edge (adj_matrix, 'e', 'h');
  g_add_edge (adj_matrix, 'g', 'i');
  g_add_edge (adj_matrix, 'g', 'j');
  g_add_edge (adj_matrix, 'h', 'k');
  g_add_edge (adj_matrix, 'i', 'l');
  g_add_edge (adj_matrix, 'j', 'l');

  g_matrix_print (adj_matrix, vert_num, vert_num);
  printf ("Depth-First Search (DFS) \n");

  depth_first_search (adj_matrix, vert_list, vert_num);

  m2d_deallocate (adj_matrix, MAX);
  printf ("\n");

  return 0;
}

ch15-graph.c

/* code: ch15-graph.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>

#define  DIRECTED_GRAPH 1
#define  UNDIRECTED_GRAPH 2

struct g_node {
  int vertex;
  struct g_node *next;
};
typedef struct g_node G_NODE_TYPE;

struct g_list {
  int num_members;
  G_NODE_TYPE *head;
};
typedef struct g_list G_LIST_TYPE;

struct graph {
  int num_vertices;
  int graph_cat;
  G_LIST_TYPE *g_list_array;
};
typedef struct graph G_GRAPH_TYPE;

/* ------------------------------------------ */
G_NODE_TYPE *graph_newnode (int v) {
  G_NODE_TYPE *node;
  node = malloc (sizeof (G_NODE_TYPE));
  if (!node) {
    printf ("ERROR: Can not allocate memory.\n");
    exit (-1);
  }
  node->vertex = v;
  node->next = NULL;

  return node;
}

/* ------------------------------------------ */
G_GRAPH_TYPE *graph_create (int n, int category) {
  int i;
  G_GRAPH_TYPE *graph;
  graph = malloc (sizeof (G_GRAPH_TYPE));
  if (!graph) {
    printf ("ERROR: Can not allocate memory.\n");
    exit (-1);
  }
  graph->num_vertices = n;
  graph->graph_cat = category;

  graph->g_list_array = malloc (n * sizeof (G_LIST_TYPE));
  if (!graph->g_list_array) {
    printf ("ERROR: Can not  allocate memory.\n");
    exit (-1);
  }
  for (i = 0; i < n; i++) {
    graph->g_list_array[i].head = NULL;
    graph->g_list_array[i].num_members = 0;
  }
  return graph;
}

/* ------------------------------------------ */
void graph_add_edge (G_GRAPH_TYPE * graph, int source, int target) {
  G_NODE_TYPE *node;

  source = source - 'a';
  target = target - 'a';
  node = graph_newnode (target);
  node->next = graph->g_list_array[source].head;
  graph->g_list_array[source].head = node;
  graph->g_list_array[source].num_members++;

  if (graph->graph_cat == UNDIRECTED_GRAPH) {
    node = graph_newnode (source);
    node->next = graph->g_list_array[target].head;
    graph->g_list_array[target].head = node;
    graph->g_list_array[target].num_members++;
  }
}

/* ------------------------------------------ */
void graph_destroy (G_GRAPH_TYPE * graph) {
  int v;
  G_NODE_TYPE *g_list;
  G_NODE_TYPE *tmp;

  if (graph) {
    if (graph->g_list_array) {
      for (v = 0; v < graph->num_vertices; v++) {
	g_list = graph->g_list_array[v].head;
	while (g_list) {
	  tmp = g_list;
	  g_list = g_list->next;
	  free (tmp);
	}
      }
      free (graph->g_list_array);
    }
    free (graph);
  }
}

/* ------------------------------------------ */
void graph_display (G_GRAPH_TYPE * graph) {
  int i;
  printf ("#vertices: %d\n", graph->num_vertices);
  printf ("------------------\n");
  for (i = 0; i < graph->num_vertices; i++) {
    G_NODE_TYPE *g_list = graph->g_list_array[i].head;
    printf ("%c: ", i + 'a');
    while (g_list) {
      printf ("%c ", g_list->vertex + 'a');
      g_list = g_list->next;
    }
    printf ("\n");
  }
  printf ("------------------\n");
}

/* ------------------------------------------ */
int main () {
  G_GRAPH_TYPE *ug;
  ug = graph_create (4, UNDIRECTED_GRAPH);
  graph_add_edge (ug, 'c', 'd');
  graph_add_edge (ug, 'c', 'b');
  graph_add_edge (ug, 'c', 'a');
  graph_add_edge (ug, 'b', 'a');
  printf ("graph (undirected)\n");
  graph_display (ug);
  graph_destroy (ug);


  G_GRAPH_TYPE *dg;
  dg = graph_create (4, DIRECTED_GRAPH);
  graph_add_edge (dg, 'c', 'd');
  graph_add_edge (dg, 'c', 'b');
  graph_add_edge (dg, 'c', 'a');
  graph_add_edge (dg, 'b', 'a');
  printf ("graph (directed)\n");
  graph_display (dg);
  graph_destroy (dg);

  return 0;
}