Homework Sourseplease i need help Im writing a program to test the merge so
please i need help I\'m writing a program to test the merge sort algorithm for linked lists.
I need to Print the list before being sorted and the list after sorting the elements
here is my code only help in test program the four classes are ok except the test program.
TEST PROGRAM
import java.io.*;
import java.util.*;
public class Ch9_ProgExercise7 {
Scanner input = new Scanner(System.in);
public static void main(String[] args) throws IOException {
OrderedLinkedList list
= new OrderedLinkedList(); //Line 1
IntElement num = new IntElement(); //Line 2
// Prompt the user to enter some integers
System.out.println(\"Enter integers numbers \");
String temp = input.hasnextLine();
String[] split = temp.split(\" \");
for (int i = 0; i < split.length; i++) {
Integer a = Integer.parseInt(split[i]);
// insert the intgers into the list you created above
num.setNum(a);
list.insertNode(num);
}
System.out.println();
// Print the list before being sorted
// call the mergesort method
System.out.println();
// print the list after sorting the elements
}
}
ORDEREDLICKEDLIST CLASS
public class OrderedLinkedList extends LinkedListClass
{
//default constructor
public OrderedLinkedList()
{
super();
}
//copy constructor
public OrderedLinkedList(OrderedLinkedList otherList)
{
super(otherList);
}
public void linkedInsertionSort()
{
LinkedListNode lastInOrder;
LinkedListNode firstOutOfOrder;
LinkedListNode current;
LinkedListNode trailCurrent;
lastInOrder = first;
if(first == null)
System.out.println(\"Cannot sort an empty list\");
else
if(first.link == null)
System.out.println(\"The list is of length 1. \"
+ \"Already in order\");
else
while(lastInOrder.link != null)
{
firstOutOfOrder = lastInOrder.link;
if(firstOutOfOrder.info.compareTo(first.info) < 0)
{
lastInOrder.link = firstOutOfOrder.link;
firstOutOfOrder.link = first;
first = firstOutOfOrder;
}
else
{
trailCurrent = first;
current = first.link;
while(current.info.compareTo(firstOutOfOrder.info) < 0)
{
trailCurrent = current;
current = current.link;
}
if(current != firstOutOfOrder)
{
lastInOrder.link = firstOutOfOrder.link;
firstOutOfOrder.link = current;
trailCurrent.link = firstOutOfOrder;
}
else
lastInOrder = lastInOrder.link;
}
}
}//end linkedInsertionSort
//Method to determine whether searchItem is in
//the list.
//Postcondition: Returns true if searchItem is found
// in the list; otherwise, it returns
// false.
public boolean search(DataElement searchItem)
{
LinkedListNode current; //variable to traverse the list
boolean found;
current = first; //set current to point to the first
//node in the list
found = false; //set found to false
while(current != null && !found ) //search the list
if(current.info.compareTo(searchItem) >= 0)
found = true;
else
current = current.link; //make current point to
//the next node
if(found)
found = current.info.equals(searchItem);
return found;
}
//Method to insert insertItem in the list
//Postcondition: first points to the new list,
// newItem is inserted at the proper place
// in the list, and count is incremented by 1.
public void insertNode(DataElement insertItem)
{
LinkedListNode current; //variable to traverse the list
LinkedListNode trailCurrent; //variable just before current
LinkedListNode newNode; //variable to create a node
boolean found;
newNode = new LinkedListNode(); //create the node
newNode.info = insertItem.getCopy(); //store newItem
//in the node
newNode.link = null; //set the link field of the node
//to null
if(first == null) //Case 1
{
first = newNode;
count++;
}
else
{
trailCurrent = first;
current = first;
found = false;
while(current != null && !found) //search the list
if(current.info.compareTo(insertItem) >= 0)
found = true;
else
{
trailCurrent = current;
current = current.link;
}
if(current == first) //Case 2
{
newNode.link = first;
first = newNode;
count++;
}
else //Case 3
{
trailCurrent.link = newNode;
newNode.link = current;
count++;
}
}//end else
}//end insertNode
//Method to delete deleteItem from the list.
//Postcondition: If found, the node containing
// deleteItem is deleted from the
// list. Also, first points to the first
// node, last points to the last
// node of the updated list, and count
// is decremented by 1.
public void deleteNode(DataElement deleteItem)
{
LinkedListNode current; //variable to traverse the list
LinkedListNode trailCurrent; //variable just before current
boolean found;
if(first == null) //Case 1; list is empty.
System.err.println(\"Can not delete from an \"
+ \"empty list.\");
else
{
if(first.info.equals(deleteItem)) //Case 2
{
first = first.link;
count--;
}
else //search the list for the node with the given info
{
found = false;
trailCurrent = first; //set trailCurrent to point to
//the first node
current = first.link; //set current to point to the
//second node
while(current != null && !found)
{
if(current.info.compareTo(deleteItem) >= 0)
found = true;
else
{
trailCurrent = current;
current = current. link;
}
} //end while
if(current == null) //Case 4
System.out.println(\"Item to be deleted is \"
+ \"not in the list.\");
else
if(current.info.equals(deleteItem)) //item to be
//deleted is in the list
{
if(first == current) //Case 2
{
first = first.link;
count--;
}
else //Case 3
{
trailCurrent.link = current.link;
count--;
}
}
else //Case 4
System.out.println(\"Item to be deleted is \"
+ \" not in the list.\");
}
} //end else
} //end deleteNode
}
LINKEDLIST CLASS
public abstract class LinkedListClass
{
protected class LinkedListNode
{
DataElement info;
LinkedListNode link;
}
protected LinkedListNode first; //variable to store the
//address of the first
//node of the list
protected LinkedListNode last; //variable to store the
//address of the last
//node of the list
protected int count; //variable to store the number of nodes
//in the list
//default constructor
//Initializes the list to an empty state.
//Postcondition: first = null, last = null,
// count = 0
public LinkedListClass()
{
first = null;
last = null;
count = 0;
}
//Method to determine whether the list is empty.
//Postcondition: Returns true if the list is empty;
// false otherwise.
public boolean isEmptyList()
{
return (first == null);
}
//Method to initialize the list to an empty state.
//Postcondition: first = null, last = null,
// count = 0
public void initializeList()
{
first = null;
last = null;
count = 0;
}
//Method to output the data contained in each node.
public void print()
{
LinkedListNode current; //variable to traverse the list
current = first; //set current so that it points to
//the first node
while(current != null) //while more data to print
{
System.out.print(current.info + \" \");
current = current.link;
}
}//end print
//Method to return the number of nodes in the list.
//Postcondition: The value of count is returned.
public int length()
{
return count;
}
//Method to return a reference of the object containing
//the data of the first node of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: The reference of the object that
// contains the info of the first node
// is returned.
public DataElement front()
{
DataElement temp = first.info.getCopy();
return temp;
}
//Method to return a reference of object containing
//the data of the last node of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: The reference of the object that
// contains the info of the last node
// is returned.
public DataElement back()
{
DataElement temp = last.info.getCopy();
return temp;
}
//Method to determine whether searchItem is in the list.
//Postcondition: Returns true if searchItem is found
// in the list; false otherwise.
public abstract boolean search(DataElement searchItem);
//Method to insert newItem in the list.
//Postcondition: first points to the new list
// and newItem is inserted at the
// beginning of the list. Also,
// last points to the last node and
// count is incremented by 1.
public void insertFirst(DataElement newItem)
{
LinkedListNode newNode; //variable to create the
//new node
newNode = new LinkedListNode(); //create the new node
newNode.info = newItem.getCopy(); //assign a copy of
//newItem to the node
newNode.link = first; //insert newNode before first
first = newNode; //make first point to the
//actual first node
if(last == null) //if the list was empty, newNode is
//also the last node in the list
last = newNode;
count++;
}
//Method to insert newItem at the end of the list.
//Postcondition: first points to the new list and
// newItem is inserted at the end
// of the list. Also, last points to
// the last node and
// count is incremented by 1.
public void insertLast(DataElement newItem)
{
LinkedListNode newNode; //variable to create the new node
newNode = new LinkedListNode(); //create the new node
newNode.info = newItem.getCopy(); //assign a copy of
//newItem to the node
newNode.link = null; //set the link field of
//newNode to null
if(first == null) //if the list is empty, newNode is
//both the first and last node
{
first = newNode;
last = newNode;
}
else //if the list is not empty, insert newNode after last
{
last.link = newNode; //insert newNode after last
last = newNode; //set last to point to the actual last node
}
count++;
}//end insertLast
//Method to delete deleteItem from the list.
//Postcondition: If found, the node containing
// deleteItem is deleted from the
// list. Also first points to the first
// node, last points to the last
// node of the updated list, and count
// is decremented by 1.
public abstract void deleteNode(DataElement deleteItem);
//Method to return a reference of the copy of otherList.
private void copy(LinkedListClass otherList)
{
LinkedListNode newNode; //variable to create a node
LinkedListNode current; //variable to traverse the list
first = null; //make this list empty
if(otherList.first == null) //otherList is empty
{
first = null;
last = null;
count = 0;
}
else
{
count = otherList.count;
current = otherList.first; //current points to the
//list to be copied
//copy the first element
first = new LinkedListNode(); //create the node
first.info = current.info.getCopy(); //copy the info
first.link = null; //set the link field of
//the node to null
last = first; //make last point to the first node
current = current.link; //make current point to the next
//node of the list being copied
//copy the remaining list
while(current != null)
{
newNode = new LinkedListNode();
newNode.info = current.info.getCopy();
newNode.link = null;
last.link = newNode;
last = newNode;
current = current.link;
}//end while
}//end else
}//end copy
//Method to return a reference of the copy of otherList.
public void copyList(LinkedListClass otherList)
{
if(this != otherList) //avoid self-copy
copy(otherList);
}
//copy constructor
public LinkedListClass(LinkedListClass otherList)
{
copy(otherList);
}//end copy constructor
}
public class IntElement extends DataElement
{
protected int num;
//default constructor
public IntElement()
{
num = 0;
}
//constructor with parameters
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);
}
}
DATAELEMENT CLASS
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
}
Solution
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct node
{
int data;
struct node* next;
};
/* function prototypes */
struct node* SortedMerge(struct node* a, struct node* b);
void FrontBackSplit(struct node* source,
struct node** frontRef, struct node** backRef);
/* sorts the linked list by changing next pointers (not data) */
void MergeSort(struct node** headRef)
{
struct node* head = *headRef;
struct node* a;
struct node* b;
/* Base case -- length 0 or 1 */
if ((head == NULL) || (head->next == NULL))
{
return;
}
/* Split head into \'a\' and \'b\' sublists */
FrontBackSplit(head, &a, &b);
/* Recursively sort the sublists */
MergeSort(&a);
MergeSort(&b);
/* answer = merge the two sorted lists together */
*headRef = SortedMerge(a, b);
}
/* See http://geeksforgeeks.org/?p=3622 for details of this
function */
struct node* SortedMerge(struct node* a, struct node* b)
{
struct node* result = NULL;
/* Base cases */
if (a == NULL)
return(b);
else if (b==NULL)
return(a);
/* Pick either a or b, and recur */
if (a->data <= b->data)
{
result = a;
result->next = SortedMerge(a->next, b);
}
else
{
result = b;
result->next = SortedMerge(a, b->next);
}
return(result);
}
/* UTILITY FUNCTIONS */
/* Split the nodes of the given list into front and back halves,
and return the two lists using the reference parameters.
If the length is odd, the extra node should go in the front list.
Uses the fast/slow pointer strategy. */
void FrontBackSplit(struct node* source,
struct node** frontRef, struct node** backRef)
{
struct node* fast;
struct node* slow;
if (source==NULL || source->next==NULL)
{
/* length < 2 cases */
*frontRef = source;
*backRef = NULL;
}
else
{
slow = source;
fast = source->next;
/* Advance \'fast\' two nodes, and advance \'slow\' one node */
while (fast != NULL)
{
fast = fast->next;
if (fast != NULL)
{
slow = slow->next;
fast = fast->next;
}
}
/* \'slow\' is before the midpoint in the list, so split it in two
at that point. */
*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
}
/* Function to print nodes in a given linked list */
void printList(struct node *node)
{
while(node!=NULL)
{
printf(\"%d \", node->data);
node = node->next;
}
}
/* Function to insert a node at the beginging of the linked list */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Drier program to test above functions*/
int main()
{
/* Start with the empty list */
struct node* res = NULL;
struct node* a = NULL;
/* Let us create a unsorted linked lists to test the functions
Created lists shall be a: 2->3->20->5->10->15 */
push(&a, 15);
push(&a, 10);
push(&a, 5);
push(&a, 20);
push(&a, 3);
push(&a, 2);
/* Sort the above created Linked List */
MergeSort(&a);
printf(\"\ Sorted Linked List is: \ \");
printList(a);
getchar();
return 0;
}
