2 Sorted list array implementation This sorted list ADT disc

2. (Sorted list: array implementation) This sorted list ADT discussed in class should be extended by the addition of two new methods:

//Interface: ArrayListADT
//works for int
public interface ArrayListADT {
    public boolean isEmpty(); //Method to determine whether the list is empty.
    public boolean isFull(); //Method to determine whether the list is full.
    public int listSize();    //Method to return the number of elements in the list.
    public int maxListSize(); //Method to return the maximum size of the list.
    public void print();      //Method to output the elements of the list.
    public boolean isItemAtEqual(int location, int item); //Method to determine whether item is the same as the item in the list at location.
    public void insertAt(int location, int insertItem);   //Method to insert insertItem in the list at the position
    public void insertEnd(int insertItem); //Method to insert insertItem at the end of the list.
    public void removeAt(int location); //Method to remove the item from the list at location.
    public int retrieveAt(int location);   //Method to retrieve the element from the list at location.
    public void replaceAt(int location, int repItem); //Method to replace the element in the list at location with repItem.
    public void clearList(); //Method to remove all the elements from the list.
    public int search(int searchItem);    //Method to determine whether searchItem is in the list.
    public void remove(int removeItem);   //Method to remove an item from the list.
}

//Class: ArrayListClass implements
//Interface: ArrayListADT
public abstract class ArrayListClass implements ArrayListADT {
    protected int length;    //to store the length of the list
    protected int maxSize;   //to store the maximum size of the list
    protected int[] list;    //array to hold the list elements

    //Default constructor
    public ArrayListClass() {
        maxSize = 100;
        length = 0;
        list = new int[maxSize];
    }

    //Alternate Constructor
    public ArrayListClass(int size) {
        if(size <= 0) {
            System.err.println(\"The array size must be positive. Creating an array of size 100.\");
            maxSize = 100;
        }
        else
            maxSize = size;
        length = 0;
        list = new int[maxSize];
    }

    public boolean isEmpty() {
        return (length == 0);
    }

    public boolean isFull() {
        return (length == maxSize);
    }

    public int listSize() {
        return length;
    }

    public int maxListSize() {
        return maxSize;
    }

    public void print() {
        for (int i = 0; i < length; i++)
            System.out.print(list[i] + \" \");
        System.out.println();
    }

    public boolean isItemAtEqual(int location, int item) {
        if (location < 0 || location >= length) {
            System.err.println(\"The location of the item to be compared is out of range.\");
            return false;
        }
        return list[location]== item;
    }

    public void clearList() {
        for (int i = 0; i < length; i++)
            list[i] = 0;
        length = 0;
        System.gc();   //invoke the Java garbage collector
    }

    public void removeAt(int location) {
        if (location < 0 || location >= length)
            System.err.println(\"The location of the item to be removed is out of range.\");
        else {
            for(int i = location; i < length - 1; i++)
                 list[i] = list[i + 1];
            length--;
        }
    }

    public int retrieveAt(int location) {
        if (location < 0 || location >= length) {
            System.err.println(\"The location of the item to be retrieved is out of range.\");
            return 0;
        }
        else
            return list[location];
    }

    public abstract void insertAt(int location, int insertItem);
    public abstract void insertEnd(int insertItem);
    public abstract void replaceAt(int location, int repItem);
    public abstract int search(int searchItem);
    public abstract void remove(int removeItem);
}

//Class: OrderedArrayList extends
//Super class: ArrayListClass
public class OrderedArrayList extends ArrayListClass{
   
    public OrderedArrayList() {
        super();
    }

    public OrderedArrayList(int size) {
        super(size);
    }

    //implementation for abstract methods defined in ArrayListClass

    //ordered list --> binary search
    public int search(int item) {
        int first = 0;
        int last = length - 1;
        int middle = -1;

        while (first <= last) {
            middle = (first + last) / 2;
            if (list[middle] == item)
                return middle;
            else
                if (list[middle] > item)
                    last = middle - 1;
                else
                    first = middle + 1;
        }
        return -1;
    }

    public void insert(int item) {
        int loc;
        boolean found = false;
        if (length == 0)            //list is empty
            list[length++] = item; //insert item and increment length
        else if (length == maxSize) //list is full
            System.err.println(\"Cannot insert in a full list.\");
        else {
            for (loc = 0; loc < length; loc++) {
                if (list[loc] >= item) {
                    found = true;
                    break;
                }
            }
            //starting at the end, shift right
            for (int i = length; i > loc; i--)
                list[i] = list[i - 1];
            list[loc] = item; //insert in place
            length++;
        }
    }

    /* Another version for insert:
    public void insert(int item) {
        int loc;
        boolean found = false;
        if (length == 0)            //list is empty
            list[length++] = item; //insert item and increment length
        else if (length == maxSize) //list is full
            System.err.println(\"Cannot insert in a full list.\");
        else {
            int i = length - 1;
            while (i >= 0 && list[i] > item) {
                list[i + 1] = list[i];
                i--;
            }
            list[i + 1] = item; // Insert item
            length++;
       }
    } */

    public void insertAt(int location, int item) {
        if (location < 0 || location >= maxSize)
            System.err.println(\"The position of the item to be inserted is out of range.\");
        else if (length == maxSize) //the list is full
            System.err.println(\"Cannot insert in a full list.\");
        else {
            System.out.println(\"Cannot do it, this is a sorted list. Doing insert in place (call to insert).\");
            insert(item);
        }
    }

    public void insertEnd(int item) {
        if (length == maxSize) //the list is full
            System.err.println(\"Cannot insert in a full list.\");
        else {
            System.out.println(\"Cannot do it, this is a sorted list. Doing insert in place (call to insert).\");
            insert(item);
        }
    }

    public void replaceAt(int location, int item) {
        //the list is sorted!
        //is actually removing the element at location and inserting item in place
        if (location < 0 || location >= length)
             System.err.println(\"The position of the item to be replaced is out of range.\");
        else {
            removeAt(location);//method in ArrayListClass
            insert(item);
        }
    }

     public void remove(int item) {
        int loc;
        if (length == 0)
            System.err.println(\"Cannot delete from an empty list.\");
        else {
            loc = search(item);
            if (loc != -1)
                removeAt(loc);//method in ArrayListClass
            else
                System.out.println(\"The item to be deleted is not in the list.\");
        }
    }

    /*Another version for remove:
    public void remove(T item) {
        int loc;
        if (length == 0)
            System.err.println(\"Cannot delete from an empty list.\");
        else {
            loc = search(item);
            if (loc != -1) {
                for(int i = loc; i < length - 1; i++)
                    list[i] = list[i + 1]; //shift left
                length--;
            }
            else
                System.out.println(\"The item to be deleted is not in the list.\");
        }
    } */
}

1. A method named merge that concatenates 2 unordered lists into a third. Assume that list_1 and list_2 don\'t have any keys in common. The resulting list should be an unsorted list that contains all of the items from list_1 and list_2 (preserve the order). Requirement: You should merge the two lists in one traversal (do not make repeated calls to insert – very inefficient!). You will not get credit for the same method in both classes.

2 . A method named split that divides a list into 2 lists according to a key. If  list_1 and list_2 are the resulting lists, list_1 should contain all the items of the original list whose keys are less than or equal to the key passed and list_2 should contain all the items of the original list whose keys are larger than the key passed.

Next, create a client to test your program. The client should work with 3 sorted lists named list_1, list_2 and result. Read the data for list_1 andlist_2 from the files list1.txt and list2.txt (take input from user the names of the input files, handle the FileNotFoundException exception(try/catch) and consume unwanted input.) Merge list_1 and list_2 into result and split result according to a key (input from the user). Make sure you handle all possible errors.

SAMPLE OUTPUT:

Please input the name of the file to be opened for first list: list1.txt
Please input the name of the file to be opened for second list: list2.txt
The first list is:
2 5 8 11 14 29 33 43 45 51 55 65 70 75
The second list is:
1 4 7 9 10 15 35 49 57 59 67
The merged list is:
1 2 4 5 7 8 9 10 11 14 15 29 33 35 43 45 49 51 55 57 59 65 67 70 75
Enter key for split: 13
The first list after split is:
1 2 4 5 7 8 9 10 11
The second list after split is:
14 15 29 33 35 43 45 49 51 55 57 59 65 67 70 75

FOR input files:
list1.txt: 2 5 8 m m b 11 14 29 x 33 43 45 51 z z 55 65 70 b 75
list2.txt: 1 ccc 4 bb 7 mm 9 10 15 35 x x x 49 57 59 67

Solution

program:

#include<stdio.h>

#inclue<stdlib.h>

typedef struct node{

int data;

struct node *next;

}Node;

Node * createNode(int val){

Node * temp = (Node *)malloc(sizeof(Node));

if(temp){

temp->data = val;

temp->next = NULL;

}

return temp;

}

void push(Node **headRef, int data){

Node * newNode = createNode(data);

newNode->next = *headRef;

*headRef = newNode;

}

void printList(Node * head){

while(head){

printf(\"%d->\" , head->data);

head = head->next;

}

printf(\"NULL\");

printf(\"\ \");

}

if(!list1)return list2;

if(!list2)return list1;

Node *head;

if(list1->data <list2->data){

head = list1;

}else {

head = list2;

list2 = list1;

list1 = head;

}

while(list1->next && list2){

if(list1->next->data > list2->data) {

Node *tmp = list1->next;

list1->next = list2;

list2 = temp;

}

list1 = list1->next;

}

if(!list1->next) list->next = list2;

retrun head;

}

int main() {

Node * L1 = NULL;

Node * L2 = NULL;

Node * result = NULL;

int carry = 0;

/* creating list1 */

push(&L1,7);

push(&L1,6);

push(&L1,4);

push(&L1,3);

/*creating list 2 */

push(&L2, 10);

push(&L2, 8);

push(&L2,1);

L1 =MergeLists(L1,L2);

printList(L1);

return 0;

}