LAB 1—ListArray ADT (Due Friday January 18th at 14:30).

In this lab exercise you need to complete the methods of an ADT called ListArray. I have provided the interfaces of this ADT both in Java and C++, and you need to complete the methods. Complete the functions in SortedListArrayBased.java or listArray.cpp files.

The ListArray ADT is implemented over an ascending sorted list of elements and the following operations are possible (Note that the operations must maintain the ascending order of the elements).

A) int find(x): searches the element x in the array. If x exists returns its index in the array, otherwise returns a negative value. Since the array is sorted at all times the best way to implement this operation is using the binary search method and you are expected to use this method for implementing the find operation. Below is the pseudo code of the binary search: (note that this is only a psedo code).

int binarySearch(Element x, ElementArray list, int listSize){

      int left=0, right=listSize-1;
      while(left <= right){
            int middle=(left+right)/2;
            if (list[middle]=x)
                  return middle; //x is found at middle location
            if (list[middle]>x)
                  right=middle-1;  //search the left part of the list
            else
                  left=middle+1;   //search the right part of the list
      }
     
      return a negative value;      //x does not exist in the list.

}

B) int insert(x): inserts the element x in the appropriate position in the array. If x already exist in the array it will ignore the operation. Note that first you need to find the appropriate position for x in the array, then shift down all the elements from that position to make a room for x and then write x in that position. Use the binarySearch method to find the appropriate position to insert x.

C) removeLast(): If the list is not empty it removes the last element from the list, and returns its value. 

D) printAll(): Prints all the elements in the list.

Testing: The main() function is written. It reads a number of integers from the data.txt file and insert them in the list. Then it reads a number of integers from the test.txt file and search them in the list. Finally it prints all the elements in the list using the printAll() method. I have put samples of data.txt and test.txt files together with the class files. The output of your program for this files should be:

inserting 0

inserting 8

inserting 3

inserting 2

inserting 14

inserting 0

0 exists in the list

inserting 3

3 exists in the list

inserting 7

inserting 6

inserting 11

inserting 4

inserting 6

6 exists in the list

inserting 11

11 exists in the list

inserting 3

3 exists in the list

inserting 5

searching 40: 40 does not exist in the list

searching 3: 3 is located at position 2 in the list

searching 2: 2 is located at position 1 in the list

searching 5: 5 is located at position 4 in the list

searching -89: -89 does not exist in the list

searching 0: 0 is located at position 0 in the list

searching 0: 0 is located at position 0 in the list

14

11

8

7

6

5

4

3

2

0

Style: part of the grade is for having proper style which includes proper indenting and having enough comments.

Submission: zip all your source files and submit it through submission server submit.cs.sfu.ca. The submission server only accepts the zipped files. You can zip your assignment files using the winzip program or the zip, gzip linux command. Include your name and student number in your source file and includes the main function.

Implementation Language: The programming problems in assignments, can be written in either JAVA or C++. It’s not necessary to learn JAVA for those who know only C++ and to learn C++ for those who know only JAVA.

---