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;
}
EOF