INFORMATION & COMPUTER SCIENCE DEPARTMENT, KFUPM

ICS – 201 SECTION 55 & 56  (992 Semester)

INTRODUCTION TO COMPUTER SCIENCE

LAB  #11 Dynamic Arrays & Searching

 

Instructor: Bashir M. Ghandi

Objective:       Learn how arrays relate to pointers & how to declare and use dynamic arrays.

Learn how to implement linear & binary search.

 

Relationship between Arrays & Pointers

·        The name of an array in C is in fact a pointer constant – the address of the first element

·        E.g.  If we have the declaration: int x[5]={10,20,30,40,50}, *p;

·        Then it is possible to make the assignment:   p=x;

·        This is equivalent to :   p=&x[0];

·        With either of the above the first element of the array can be accessed either as : x[0]  or *p

·        Since x is an address, the first element can also be accessed as:  *x.

·        C also allows the pointer variable p to be indexed.  Thus the first element can be accessed as:    p[0]

·        The second element can be accessed using any of the following:

x[1],  p[1],  *(x+1) ,  or  *(p+1).

·        The last two expressions are example of pointer arithmetic, one of the powerful features of C.

·        What then is the difference between x and p?

·        The difference is that x is a constant while p is a variable.  Thus, x cannot be changed, but p can be changed.    E.g.   p++;

·        This makes p to now points to the second element of the array.

·        The program POINTERS.C further shows the use of pointers to manipulate elements of an array.

 

Note:   It is important to always use free to explicitly return the memory obtained by malloc.

Before using free(p) to return memory obtained using malloc, makes sure that p is pointing to element 0.

 

What is Searching?

·        Searching means scanning through a list of items or records to find if a particular one exists.

·        It usually requires the user to specify the target item (or in case of record, a target key e.g. id_no.)

·        If the target item is found, the record or its location is returned, otherwise, an appropriate message or flag is returned.

 

Linear Search

·        This involves searching through the list sequentially until the target item is found or the list is exhausted.

·        Assuming the data items are simple values (e.g. int) contained in an array list, then the the following function can implements linear search.

 

int lin_search1(int list[], int size, int target)

{  int loc=0;

  

   while (loc < size  &&  list[loc] != target)

        loc++;

   if (list[loc] == target)

      return loc;

   else

      return –1;

}

·        However, if the items consists of structures then the comparison is between target and list[loc].key

 

Binary Search

·        If the list is ordered, it is a waste of time to look for an item using linear search (it would be like looking for a word in a dictionary sequentially).  In this case we apply binary search.

·        Binary search works by comparing the target with the item at the middle of the list.  This leads to one of three results:

• The middle item is the target – we are done.
• The middle item is less than target – we apply the algorithm to the upper half of the list.
• The middle item is bigger than the target – we apply the algorithm to the lower half of the list.

·        This process is repeated until the item is found or the list is exhausted.

·        The following functions implements this approach

 

int bin_search(ITEM_TYPE list[], KEY_TYPE target, int low, int high)

{  int middle;

    while (low <= high)

   {  middle = (low + high)/2;

       if (list[middle].key == target)

           return (middle);

       else if (list[middle].key < target)

           low = middle + 1;

       else

           high = middle – 1;

   }

   return (-1);

}

 

Programming Exercises:

1.                  The program file lab11_1.c shows the use of dynamic array.  Copy it from my home page and test run it with different values of size.

2.                  Modify lab11_1.c so that it computes and prints the sum of the integer values using FOUR different array access methods.

3.                  The program file lab11_3.c  contains an interactive program that performs Add, Remove, Display and Search operations on a list of integers contained in a file INTEGERS.DAT.  Copy both the program and the data file from my home page.  Study the program and test run.  Pay particular attention the function get_list that reads the data into a dynamic array and the function remove_int that deletes an integer from the file.

4.                  Modify lab11_3.c by implementing the Add operation. 

Hint: You need to write a function add_int that: opens the file for append, prints the given integer in the file and close the file.  You then call this function from case 1.

 

Home Work.

Modify the program in (4) above so that it performs the same operations but using the records in the exams2.dat file.  Use binary search for your search operations.