2.(Sorted list array implementation)This sorted list ADT discussed .pdf

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
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
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
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
#inclue
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 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;
}

2.(Sorted list array implementation)This sorted list ADT discussed .pdf

Recommended

More Related Content

Similar to 2.(Sorted list array implementation)This sorted list ADT discussed .pdf (20)

More from arshin9 (20)

Recently uploaded (20)

2.(Sorted list array implementation)This sorted list ADT discussed .pdf