ex7-1.c

/* code: ex7-1.c   (v1.20.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.20.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.25.00) */  
#include <stdio.h>
#include <stdlib.h>
#include <search.h>
  
#define ARRAY_SIZE 5
#define EXTRA_ROOM 1  
  
/* ------------------------------------------- */ 
int compare (const void *x, const void *y)
{
  
int a = *(const int *) x;
  
int b = *(const int *) y;
  
return (a > b) - (a < b);

}


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

} 
 

/* ------------------------------------------- */ 
int main ()
{
  
int key = 25;
  
size_t elements = ARRAY_SIZE;
  
int array[ARRAY_SIZE + EXTRA_ROOM] = { 10, 20, 30, 40, 50 };
  
 
printf ("Initial array: ");
  
print_array (array, elements);
  
 
int *found = lsearch (&key, array, &elements, sizeof (int), compare);
  
 
if (!found) {
    
printf ("Search error\n");
    
return EXIT_FAILURE;
  
}
  
 
printf ("\nResult:\n");
  
if (elements == ARRAY_SIZE) {
    
printf ("Key %d was already in the array.\n", key);
  
}
  else {
    
printf ("Key %d was added to the array.\n", key);
  
}
  
 
print_array (array, elements);
  
return EXIT_SUCCESS;

}

q7-2.c

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

#define ARRAY_SIZE 10

/* ------------------------------------------- */
int compare (const void *a, const void *b)
{
  int x = *(int *) a;
  int y = *(int *) b;
  if (x < y)
    return -1;
  if (x > y)
    return 1;
  return 0;
}

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

q7-3.c

/* code: q7-3.c   (v1.25.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;
  a = (int *) malloc (sizeof (int) * MAX);
  if (a == NULL) {
    printf ("Error! memory not allocated.");
    exit (EXIT_FAILURE);
  }

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


  free (a);

  return 0;
}

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