Question

Modify listarr.java program by adding the following 2 methods:

public void insertsorted(x); // Inert x in a sorted list.

protected int binsearch(x); // Binary search for x

Assume you have a data file p1.txt with the following contents:

8    

4 15 23 12 36 5 36 42

3

5 14 36

and your main program is in p1.java file.

To compile: javac p1.java

To execute: java p1 < any data file name say p1.txt

Your output should be formatted (i.e. using %4d for print) as follow:

Your name:……………………………. Student ID:…………………………

The 8 inserted data are as follow:

4 5 12 15 23 36 36 42

Searching for 3 data in the sorted list.

5: is found!

14: Ooops is not in the list?

36: is found!

Your main method should be as follow:

public static void main(String args[]) {

int j, n, m, k, x;

try{

          Scanner inf = new Scanner(System.in);                 

          n = inf.nextInt();// read No. of data to read

         

          // Create a List of type Integer of size n

          listarr Lint = new listarr(n);      

         

          // Read n element and insert in a sorted listposition randomly in the list

          for(j = 1; j <= n; j++){

                    x = inf.nextInt(); // read element

                    Lint.insertsorted (x);

          }

         

          System.out.printf(“The %d inserted data are as follow:”, n);

          System.out.print(Lint.toString());

          // read No. of data to search

          m = inf.nextInt();

          for(j = 1; j <= m; j++){

                    x = inf.nextInt(); // read data to search

                    k = Lint.binsearch(x);

                    if(k??? //complete it

          }

          inf.close();

} catch (Exception e) {prt("Exception " + e + "\n");}

}// end main method      

//   listarr.java

// Array implementation of list in JAVA
import java.util.*;
//*************** Class Definition *********************************
/**
* Implementation of the ADT List using a fixed-length array.
* Exception is thrown:
* if insert operation is attempted when List is full.
* if delete operation is attempted when List is empty.
* if position of insert or delete is out of range.
*/
   public class listarr implements list{
       // class Variables
       protected int capacity, last;
       protected T arr[];   

       listarr(int n){ // List Constructor
           last = 0;
           capacity = n;
           //Allocate Space            
          arr = (T[]) new Object[n+1];
          prt("\n List size = " + n);
       }

        public boolean isEmpty(){return (last == 0);}
        public int   length(){return last;}
       public boolean isFull() {return (last == capacity);}
       public static void prt(String s){System.out.print(s);}

       // insert x at position p (valid p's 1 <= p <= last+1 && last != capacity)      
       public void insert(T x, int p) throws invalidinsertion {
           prt("\nInsert " + x + " at position " + p);
       if (isFull() || p < 1 || p > last + 1)throw new invalidinsertion(p);
           // Shift from position p to right
           for (int i = last ; i >= p ; i--) arr[i+1] = arr[i];
           arr[p] = x; last++;
       }

       // delete element at position p (1...last)      
       public void delete(int p)throws invaliddeletion {
           prt("\nDelete " + p + "th element, ");
           if ( isEmpty() || p < 1 || p > last) throw new invaliddeletion(p);
           // Shift from position p + 1 to left
           for (int i = p ; i < last ; i++) arr[i] = arr[i+1];
           last --;
       }

       public String toString() {
           String s = "[";
       for (int i = 1; i <= last; i++) s += ", " + arr[i] ;
return s + "]";
        }       

       public static void main(String args[]) {
           int j, p, n, x, MaxNum = 5;
           Random rand = new Random();

           n = rand.nextInt(MaxNum) + 1;   // generate n randomly      

           // Create a List of type Integer of size n
           listarr Lint = new listarr(n);          

           // Generate n element and position randomly and insert in the list
           for(j = 1; j <= n; j++){
               p = rand.nextInt(n); // generate position
               x = rand.nextInt(MaxNum * 4); // generate element

               try {
                   Lint.insert(x,p);
               } catch (Exception e) {prt("Exception " + e + "\n");}
           }          

           prt("\nList: " + Lint.toString() + "\n"); // print list          

           // Delete n element from list randomly and print list
           for(j = 1; j <= n; j++){
               p = rand.nextInt(n); // generate position to delete
               try {
                   Lint.delete(p);
                   prt("\nList: " + Lint.toString() + "\n");
               } catch (Exception e) {prt("Exception " + e + "\n");}
           }

           // Create a List of type String
           n = rand.nextInt(MaxNum) + 1;   // generate n randomly      
           listarr Lstr = new listarr(n);
           try {
               Lstr.insert("Sarah", 1);
               Lstr.insert("Jerry", 1);
               Lstr.insert("Tom", 2);
               } catch (Exception e) {prt("Exception " + e + "\n");}
           prt("\nList: " + Lstr.toString() + "\n");
       }
   }// end class listarr

Answer 1

If you have any doubts, please give me comment...

//   listarr.java

// Array implementation of list in JAVA

import java.util.*;

//*************** Class Definition *********************************

/**

* Implementation of the ADT List using a fixed-length array. Exception is

* thrown: if insert operation is attempted when List is full. if delete

* operation is attempted when List is empty. if position of insert or delete is

* out of range.

*/

public class listarr<T extends Comparable<T>> implements list<T> {

    // class Variables

    protected int capacity, last;

    protected T arr[];

    @SuppressWarnings("unchecked")

    listarr(int n) { // List Constructor

        last = 0;

        capacity = n;

        // Allocate Space

        arr = (T[]) new Comparable[n + 1];

        prt("\n List size = " + n);

    }

    public boolean isEmpty() {

        return (last == 0);

    }

    public int length() {

        return last;

    }

    public boolean isFull() {

        return (last == capacity);

    }

    public static void prt(String s) {

        System.out.print(s);

    }

    // insert x at position p (valid p's 1 <= p <= last+1 && last != capacity)

    public void insert(T x, int p) throws invalidinsertion {

        prt("\nInsert " + x + " at position " + p);

        if (isFull() || p < 1 || p > last + 1)

            throw new invalidinsertion(p);

        // Shift from position p to right

        for (int i = last; i >= p; i--)

            arr[i + 1] = arr[i];

        arr[p] = x;

        last++;

    }

    // delete element at position p (1...last)

    public void delete(int p) throws invaliddeletion {

        prt("\nDelete " + p + "th element, ");

        if (isEmpty() || p < 1 || p > last)

            throw new invaliddeletion(p);

        // Shift from position p + 1 to left

        for (int i = p; i < last; i++)

            arr[i] = arr[i + 1];

        last--;

    }

    public void insertsorted(T x) {

        if (isFull())

            throw new invalidinsertion(0);

        int pos = 0;

        while (pos<last && arr[pos].compareTo(x) < 0) {

            pos++;

        }

        // prt("\nInsert " + x + " at position " + pos);

        // Shift from position p to right

        for (int i = last; i >= pos; i--)

            arr[i + 1] = arr[i];

        arr[pos] = x;

        last++;

    }

    protected int binsearch(T x) {

        int l = 0;

        int r = last - 1;

        while (l <= r) {

            int m = l + (r - l) / 2;

            if (arr[m].equals(x))

                return m;

            if (arr[m].compareTo(x) < 0)

                l = m + 1;

            else

                r = m - 1;

        }

        return -1;

    }

    public String toString() {

        String s = "["+arr[0];

        for (int i = 1; i <= last; i++)

            s += ", " + arr[i];

        return s + "]";

    }

    public static void main(String args[]) {

        int j, n, m, k, x;

        try {

            Scanner inf = new Scanner(System.in);

            n = inf.nextInt();// read No. of data to read

            // Create a List of type Integer of size n

            listarr<Integer> Lint = new listarr<Integer>(n);

            // Read n element and insert in a sorted listposition randomly in the list

            for (j = 1; j <= n; j++) {

                x = inf.nextInt(); // read element

                Lint.insertsorted(x);

            }

            System.out.printf("\nThe %d inserted data are as follow:", n);

            System.out.print(Lint.toString());

            // read No. of data to search

            m = inf.nextInt();

            for (j = 1; j <= m; j++) {

                x = inf.nextInt(); // read data to search

                k = Lint.binsearch(x);

                if (k != -1)

                    System.out.print("\n"+x + ": is found!");

                else

                    System.out.print("\n"+x + ": Ooops is not in the list?");

            }

            inf.close();

        } catch (Exception e) {

            prt("Exception " + e + "\n");

        }

    }// end main method

}// end class listarr