Array-Based List
URL: http://www.2shared.com/file/pA8UVyql/1_-_Array_Based.html
The file is in ZIP format. Simply extract it to access the codes.
Or you may encode the following 5 java classes:
------------------------TestProg_Array.java------------------------
//Test Program Integer Array List
import java.io.*;
import java.util.*;
public class TestProg_Array
{
static BufferedReader keyboard = new
BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException
{
UnorderedArrayList intList = new UnorderedArrayList(50);
IntElement num = new IntElement();
int counter;
int position;
int option;
StringTokenizer tokenizer;
System.out.println("Processing the integer list.");
System.out.print("Enter 8 integers in the same line: ");
System.out.flush();
tokenizer = new StringTokenizer(keyboard.readLine());
for(counter = 0; counter < 8; counter++)
{
num.setNum(Integer.parseInt(tokenizer.nextToken()));
intList.insert(num);
}
System.out.println();
System.out.print("The list you entered is: ");
intList.print();
System.out.println();
do{
showMenu();
option = Integer.parseInt(keyboard.readLine());
switch(option){
case 1:
int entry;
System.out.print("Enter number to be added: ");
entry = Integer.parseInt(keyboard.readLine());
num.setNum(entry);
intList.insert(num);
break;
case 2:
System.out.print("The list you entered is: ");
intList.print();
break;
case 0: System.out.print("Thank you!\n"); break;
default: System.out.print("Invalid option."); break;
}
}while(option != 0);
}
public static void showMenu(){
System.out.print("\nChoose from the following: ");
System.out.print("\n1: Enter a number to be added in the list");
System.out.print("\n2: Print the list");
System.out.print("\n0: Exit");
System.out.print("\nEnter option: ");
}
}
------------------------end of TestProg_Array.java------------------------
-------------------------DataElement.java---------------------------------
public abstract class DataElement
{
public abstract boolean equals(DataElement otherElement);
//Method to determine if two objects contains the same data
//Postcondition: Returns true if this object contains the
// data is the object otherElement; otherwise it
// returns false otherwise
public abstract int compareTo(DataElement otherElement);
//Method to compare two objects.
//Postcondition: Returns a value < 0 if this element is
// less than otherElement;
// Returns 0 if this element is same as
// otherElement;
// Returns a value > 0 if this element is
// greater than otherElement;
public abstract void makeCopy(DataElement otherElement);
//Method to copy otherElement into this element
//Postcondition: data of otherElement is copied into
// this object
public abstract DataElement getCopy();
//Method to return a copy of this object.
//Postcondition: A copy of this object is created and
// a reference of the copy is returned
}
-------------------------end of DataElement.java------------------------
-------------------------IntElement.java---------------------------------
public class IntElement extends DataElement
{
protected int num;
//default constructor
public IntElement()
{
num = 0;
}
//constructor with a parameter
public IntElement(int x)
{
num = x;
}
//copy constructor
public IntElement(IntElement otherElement)
{
num = otherElement.num;
}
//Method to set the value of the instance variable num.
//Postcondition: num = x;
public void setNum(int x)
{
num = x;
}
//Method to return the value of the instance variable num.
//Postcondition: The value of num is returned.
public int getNum()
{
return num;
}
public boolean equals(DataElement otherElement)
{
IntElement temp = (IntElement) otherElement;
return (num == temp.num);
}
public int compareTo(DataElement otherElement)
{
IntElement temp = (IntElement) otherElement;
return (num - temp.num);
}
public void makeCopy(DataElement otherElement)
{
IntElement temp = (IntElement) otherElement;
num = temp.num;
}
public DataElement getCopy()
{
IntElement temp = new IntElement(num);
return temp;
}
public String toString()
{
return String.valueOf(num);
}
}
-------------------------end of IntElement.java------------------------
------------------------ArrayListClass.java---------------------------
public abstract class ArrayListClass
{
protected int length; //to store the length of the list
protected int maxSize; //to store the maximum size of the list
protected DataElement[] list; //array to hold the list elements
//Default constructor
//Creates an array of size 100
//Postcondition: list points to the array, length = 0,
// and maxSize = 100
public ArrayListClass()
{
maxSize = 100;
length = 0;
list = new DataElement[maxSize];
}
//Constructor with parameter
//Creates an array of size specified by the parameter
//size.
//Postcondition: list points to the array, length = 0,
// and maxSize = size
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 DataElement[maxSize];
}
//copy constructor
public ArrayListClass(ArrayListClass otherList)
{
maxSize = otherList.maxSize;
length = otherList.length;
list = new DataElement[maxSize]; //create the array
for(int j = 0; j < length; j++) //copy otherList
list[j] = otherList.list[j].getCopy();
}//end copy constructor
public DataElement min()
{
if(length == 0)
{
System.out.println("The list is empty. "
+ "Cannot return the smallest element.");
System.exit(0);
}
DataElement smallest = list[0];
for(int i = 1; i < length; i++)
if(smallest.compareTo(list[i]) > 0)
smallest = list[i];
return smallest;
}
//Method to determine whether the list is empty.
//Postcondition: Returns true if the list is empty;
// otherwise, returns false.
public boolean isEmpty()
{
return (length == 0);
}
//Method to determine whether the list is full.
//Postcondition: Returns true if the list is full;
// otherwise, returns false.
public boolean isFull()
{
return (length == maxSize);
}
//Method to return the number of elements in the list.
//Postcondition: Returns the value of length.
public int listSize()
{
return length;
}
//Method to return the maximum size of the list.
//Postcondition: Returns the value of maxSize.
public int maxListSize()
{
return maxSize;
}
//Method to output the elements of the list.
//Postcondition: Elements of the list are output on the
//standard output device.
public void print()
{
for(int i = 0; i < length; i++)
System.out.print(list[i] + " ");
System.out.println();
}
//Method to determine whether item is the same as the item in
//the list at the position specified by location.
//Postcondition: Returns true if list[location] is
// same as location; otherwise, returns false.
public boolean isItemAtEqual(int location, DataElement item)
{
return(list[location].equals(item));
}
//Method to insert insertItem in the list at the position
//specified by location.
//Postcondition: Starting at location, the elements of the list
// are shifted to make room for the new item,
// list[location] = insertItem;, and
// length++;
// If the list is full or location is out of range,
// an appropriate message is displayed.
public void insertAt(int location, DataElement insertItem)
{
if(location < 0 || location >= maxSize)
System.err.println("The position of the item to be inserted "
+ "is out of range");
else
if(length >= maxSize) //list is full
System.err.println("Cannot insert in a full list.");
else
{
for(int i = length; i > location; i--)
list[i] = list[i - 1]; //move the elements down
list[location] = insertItem.getCopy(); //insert the
//item at the specified position
length++; //increment the length
}
} //end insertAt
//Method to inserts insertItem at the end of the list.
//Postcondition: list[length] = insertItem; and length++;
// If the list is full, an appropriate
// message is displayed.
public void insertEnd(DataElement insertItem)
{
if(length >= maxSize) //the list is full
System.err.println("Cannot insert in a full list.");
else
{
list[length] = insertItem.getCopy(); //insert the
//item at the end
length++; //increment the length
}
} //end insertEnd
//Method to remove the item from the list at the position
//specified by location.
//Postcondition: The list element at list[location] is removed
// and length is decremented by 1.
// If location is out of range, an appropriate message
// is printed.
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];
list[length - 1] = null;
length--;
}
} //end removeAt
//Method to retrieve the element from the list at the
//position specified by location.
//Postcondition: A copy of the element at the position
// specified by location is returned.
// If location is out of range, an
// appropriate message is printed and
// null is returned.
public DataElement retrieveAt(int location)
{
if(location < 0 || location >= length)
{
System.err.println("The location of the item to be "
+ "retrieved is out of range.");
return null;
}
else
return list[location].getCopy();
} //end retrieveAt
//Method to replace the element in the list at
//the position specified by location with repItem.
//Postcondition: list[location] = repItem
// If location is out of range, an appropriate
// message is printed.
public void replaceAt(int location, DataElement repItem)
{
if(location < 0 || location >= length)
System.err.println("The location of the item to be replaced "
+ "is out of range.");
else
list[location].makeCopy(repItem);
} //end replaceAt
//Method to remove all the elements from the list.
//Postcondition: length = 0
public void clearList()
{
for(int i = 0; i < length; i++)
list[i] = null;
length = 0;
System.gc();
} //end clearList
//Method to determine whether searchItem is in the list.
//Postcondition: If searchItem is found, returns the location
// in the array where searchItem is found;
// otherwise, returns -1.
public abstract int seqSearch(DataElement searchItem);
//Method to insert insertItem in the list.
//However, first the list is searched to see whether
//the item to be inserted is already in the list.
//Postcondition: insertItem is inserted and length++
// If insertItem is already in the list or the list
// is full, an appropriate message is output.
public abstract void insert(DataElement insertItem);
//Method to remove an item from the list.
//The parameter removeItem specifies the item to
//be removed.
//Postcondition: If removeItem is found in the list, it is
// removed from the list and length is
// decremented by one.
public abstract void remove(DataElement removeItem);
//Method to make a copy of the other list.
//Postcondition: This list is destroyed and a copy of
// otherList is assigned to this list.
public void copyList(ArrayListClass otherList)
{
if(this != otherList) //avoid self-assignment
{
for(int j = 0; j < length; j++) //destroy this list
list[j] = null;
System.gc();
maxSize = otherList.maxSize;
length = otherList.length;
list = new DataElement[maxSize]; //create the array
for(int j = 0; j < length; j++) //copy otherList
list[j] = otherList.list[j].getCopy();
}
}
}
-----------------end of ArrayListClass.java---------------------------
----------------------UnorderedArrayList.java-----------------------
public class UnorderedArrayList extends ArrayListClass
{
public UnorderedArrayList(int size)
{
super(size);
}
public UnorderedArrayList()
{
super();
}
//Copy constructor
public UnorderedArrayList(UnorderedArrayList otherList)
{
super(otherList);
}
//Method to determine whether searchItem is in the list.
//Postcondition: If searchItem is found, returns the location
// in the array where the searchItem is found;
// otherwise, returns -1.
public int seqSearch(DataElement searchItem)
{
int loc;
boolean found = false;
for(loc = 0; loc < length; loc++)
if(list[loc].equals(searchItem))
{
found = true;
break;
}
if(found)
return loc;
else
return -1;
} //end seqSearch
//Method to insert insertItem at the end
//of the list. However, first the list is searched to
//see whether the item to be inserted is already in the list.
//Postcondition: list[length] = insertItem and length++
// If insertItem is already in the list or the list
// is full, an appropriate message is output.
public void insert(DataElement insertItem)
{
int loc;
if(length == 0) //list is empty
list[length++] = insertItem.getCopy(); //insert acopy the item
// andincrement the length
else
if(length == maxSize)
System.err.println("Cannot insert in a full list.");
else
{
loc = seqSearch(insertItem);
if(loc == -1) //the item to be inserted
//does not exist in the list
list[length++] = insertItem.getCopy();
else
System.err.println("The item to be inserted is already in "
+ "the list. No duplicates are allowed.");
}
} //end insert
//Method to remove an item from the list.
//The parameter removeItem specifies the item to
//be removed.
//Postcondition: If removeItem is found in the list, it is
// removed from the list and length is
// decremented by one.
public void remove(DataElement removeItem)
{
int loc;
if(length == 0)
System.err.println("Cannot delete from an empty list.");
else
{
loc = seqSearch(removeItem);
if(loc != -1)
removeAt(loc);
else
System.out.println("The item to be deleted is "
+ "not in the list.");
}
} //end remove
}
------------end of UnorderedArrayList.java-----------------------
No comments:
Post a Comment