Merge Sort of a linked list java: Stack overflow
I'm trying to implement a linked list merge sort.
Here's the class I'm trying to do the merge sort in.
/**
* CS 200 Colorado State University, Fall 2011
*/
public class Member {
private String userID;
private String first;
private String last;
private EdgeStack edgeStack;
public void sortScore(Member member){
// calling a helper method
// this greedy method takes all the creds
开发者_如何学Go edgeStack = sortEdgeStack(member);
}
private EdgeStack sortEdgeStack(Member member)
{
// our temp stacks
EdgeStack tempEdgeStack_A = new EdgeStack();
EdgeStack tempEdgeStack_B = new EdgeStack();
// our return value
EdgeStack result = null;
// storing the size of the stack
int sizeOfStack = member.getEdgeStack().getSize();
// base case
if(sizeOfStack<0){
return null;
}
// our true base case
else if(sizeOfStack==1)
{
// init stack
EdgeStack base = new EdgeStack();
base.push(member.getEdgeStack().pop());
return base;
}
else
{
// pop and store
for(int i = 0; i < (sizeOfStack / 2); i++)
{
tempEdgeStack_A.push(member.getEdgeStack().pop());
}
// pop and store into b
for(int j = (sizeOfStack/2)+1; j < sizeOfStack; j++)
{
tempEdgeStack_B.push(member.getEdgeStack().pop());
}
tempEdgeStack_A = sortEdgeStack(member);
tempEdgeStack_B = sortEdgeStack(member);
result = merge(tempEdgeStack_A,tempEdgeStack_B);
return result;
}
}
private EdgeStack merge(EdgeStack tempEdgeStack_A, EdgeStack tempEdgeStack_B) {
EdgeStack result = new EdgeStack();
// while either or
while(tempEdgeStack_A.getSize()> 0 || tempEdgeStack_B.getSize() > 0)
{
// if both are bigger then 0
if(tempEdgeStack_A.getSize()> 0 && tempEdgeStack_B.getSize() > 0)
{
if(tempEdgeStack_A.peek().getEdgeRank()<=tempEdgeStack_B.peek().getEdgeRank())
{
// adds b to result
result.push(tempEdgeStack_A.pop());
}
else
{
result.push(tempEdgeStack_B.pop());
}
}
// these elses cover if A or B are > 0 but A or B is also less then or equal too 0;
else if(tempEdgeStack_A.getSize()> 0)
{
while(tempEdgeStack_A.iterator().hasNext())
{
result.push(tempEdgeStack_A.iterator().next());
}
}
else if(tempEdgeStack_B.getSize()> 0)
{
while(tempEdgeStack_B.iterator().hasNext())
{
result.push(tempEdgeStack_B.iterator().next());
}
}
}
return result;
}
}
Here's the stack class (that implements a linked list). Why am I getting a stack overflow error?
import java.util.LinkedList;
import java.util.ListIterator;
/**
* CS 200 Colorado State University, Fall 2011
*/
public class EdgeStack {
private LinkedList<Edge> llist=new LinkedList<Edge>();
public EdgeStack(){
//add your code
}
public boolean isEmpty(){
return llist.isEmpty();
}
public void push(Edge e){
llist.add(e);
}
public Edge getIndexAt(int n){
return llist.get(n);
}
public Edge pop(){
return llist.remove();
}
public Edge peek(){
return llist.getLast();
}
public int getSize(){
return llist.size();
}
// public Edge peek(int n){
// LinkedList<Edge> temp=llist;
// return temp.peek();
// }
public LinkedList<Edge> popAll(){
LinkedList<Edge> temp=llist;
llist=null;
return temp; }
public ListIterator<Edge> iterator()
{
return llist.listIterator();
}
}
Check this:
else if(tempEdgeStack_A.getSize()> 0)
{
while(tempEdgeStack_A.iterator().hasNext())
{
result.push(tempEdgeStack_A.iterator().next());
}
}
else if(tempEdgeStack_B.getSize()> 0)
{
while(tempEdgeStack_B.iterator().hasNext())
{
result.push(tempEdgeStack_B.iterator().next());
}
}
You don't remove entries from the stacks, so the loop doesn't stop.
精彩评论