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.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.20.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.20.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