ex7-1.c

/* code: ex7-1.c   (v1.16.00) */
#include <stdio.h>
#include <stdlib.h>
#define ARRAY_SIZE 13

/* ------------------------------------------- */
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;
}

/* ------------------------------------------- */
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] = {
    900, 990, 210, 50, 80, 150, 330,
    470, 510, 530, 800, 250, 280
  };
  key = 800;
  print_array (array, ARRAY_SIZE);
  index = linear_search (array, ARRAY_SIZE, key);
  if (index != -1) {
    printf ("Found: %d (Index:%d)\n", key, index);
  }
  else {
    printf ("Not found: %d\n", key);
  }
  return 0;
}




ex7-2.c

/* code: ex7-2.c   (v1.16.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;
}

/* ------------------------------------------- */
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);
  if (index != -1) {
    printf ("Found: %d (Index:%d)\n", key, index);
  }
  else {
    printf ("Not found: %d\n", key);
  }
  return 0;
}




q7-1.c

/* code: q7-1.c   (v1.20.00) */
#include <stdio.h>
#include <stdlib.h>
#include <search.h>

#define ARRAY_SIZE 10
#define NEW_ITEMS  1

/* ------------------------------------------- */
int compare (int *x, int *y)
{
  return (*x - *y);
}

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

/* ------------------------------------------- */
int main ()
{
  int key;
  int *r;
  size_t elements, elements_t;
  int array[ARRAY_SIZE + NEW_ITEMS] = {
    12, 19, 70, 44, 16, 38, 10, 30, 28, 98
  };

  key = 17;

  elements_t = elements = ARRAY_SIZE;
  print_array (array, ARRAY_SIZE);

  printf ("elements: %zu\n", elements);

  r = (int *) lsearch (&key, &array, &elements, sizeof (int),
		       (int (*)(const void *, const void *)) compare);

  if (r == NULL) {
    printf ("ERROR: lsearch()");
    exit (-1);
  }

  printf ("elements: %zu\n", elements);

  if (elements == elements_t) {
    printf ("Found : %d\n", key);
  }
  else {
    printf ("Not found %d\n", key);
    printf ("The item added at the end of the array.\n");
    print_array (array, ARRAY_SIZE + NEW_ITEMS);
  }

  return 0;
}

/* 
   The lsearch and lfind functions return  
   a pointer to the first element found. 
   If no element was found, lsearch returns 
   a pointer to the newly added element, 
   whereas lfind returns NULL. 
*/

/* ------------------------------------------- 

int main () {
  int key;
  int *r;
  size_t elements;
  int array[ARRAY_SIZE] = {
    12, 19, 70, 44, 16, 38, 10, 30, 28, 98
  };
  key = 16;
  elements = ARRAY_SIZE;
  print_array (array, ARRAY_SIZE);

  r = (int *) lfind (&key, &array, &elements, sizeof (int),
		       (int (*)(const void *, const void *)) compare);
  if ( r != NULL ) {
    printf ("Found: %d\n", key);
  }
  else {
    printf ("Not found: %d\n", key);
  }
  return 0;
}

  ------------------------------------------- */




q7-2.c

/* code: q7-2.c   (v1.16.00) */
#include <stdio.h>
#include <stdlib.h>
#include <search.h>

#define ARRAY_SIZE 10

/* ------------------------------------------- */
int compare (int *x, int *y)
{
  return (*x - *y);
}

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

/* ------------------------------------------- */
int main ()
{
  int key;
  int *r;
  int array[ARRAY_SIZE] = {
    10, 12, 16, 19, 28, 30, 38, 44, 70, 98
  };				/* ordered array! */

  key = 16;
  print_array (array, ARRAY_SIZE);

  r = (int *) bsearch (&key, &array, ARRAY_SIZE, sizeof (int),
		       (int (*)(const void *, const void *)) compare);
  if (r != NULL) {
    printf ("Found: %d\n", key);
  }
  else {
    printf ("Not found: %d\n", key);
  }
  return 0;
}




q7-3.c

/* code: q7-3.c   (v1.16.00) */
#include <stdio.h>
#include <stdlib.h>
#define MAX 1000000

/* ------------------------------------------- */
void array_print (int a[], int max)
{
  int i;
  for (i = 0; i < max; i++) {
    printf ("%02d ", a[i]);
  }
  printf ("\n");
}

/* ------------------------------------------- */
int array_find_empty (int a[], int max)
{
  int i;
  for (i = 0; i < max; i++) {
    if (a[i] == -1) {
      return i;
    }
  }
  return -1;
}

/* ------------------------------------------- */
void array_insert (int a[], int max, int index, int empty, int data)
{
  int i;
  if (empty > index) {
    for (i = empty; i > index; i--) {
      a[i] = a[i - 1];
    }
  }
  else {
    for (i = empty; i < index; i++) {
      a[i] = a[i + 1];
    }
  }
  a[index] = data;
}

/* ------------------------------------------- */
int array_delete (int a[], int index)
{
  int data;
  data = a[index];
  a[index] = -1;
  return data;
}

/* ------------------------------------------- */
int main ()
{
  int i, j, index_ins, index_del, empty, data;
  int a[MAX];

  for (j = 0; j < MAX; j++) {
    a[j] = rand () % 100;
  }
  data = a[MAX / 2];
  a[MAX / 2] = -1;

  for (i = 0; i < 1000; i++) {
    index_ins = rand () % MAX;
    index_del = rand () % MAX;
    /* printf("ins:%d  del:%d\n", index_ins, index_del );  */

    empty = array_find_empty (a, MAX);
    /* printf("empty:%d\n", empty ); */

    array_insert (a, MAX, index_ins, empty, data);

    data = array_delete (a, index_del);
    /* array_print( a, MAX ); */
  }
  return 0;
}

/* ------------------------------------------- */
/* 
 $ gcc -pg -Wall q7-3.c -o q7-3
 $ ./q7-3
 $ gprof q7-3 gmon.out > gmon.log
 $ more gmon.log
 */
/* ------------------------------------------- */




EOF