Сортировка слиянием в связанном списке дает мне переполнение стека - PullRequest
Новая
       57

Сортировка слиянием в связанном списке дает мне переполнение стека

0 голосов
/ 16 октября 2018

Спасибо за чтение. У меня в основном есть односвязный список с родовыми элементами (в итоге он перешел в строки) ... Я попытался отсортировать их с помощью сортировки слиянием, но по какой-то причине я получаю ошибку переполнения стека.Кажется, что мои рекурсии продолжаются бесконечно, но у меня есть условие, чтобы остановить это ... Вот что у меня есть, класс связанный список - это просто универсальный класс связанный список с insertfirst и insertlast.`public class app {

public static void main(String[] args) {
    sLinkedList newList = new sLinkedList();
    newList.insertLast("APPLE");
    newList.insertLast("BPPLE");
    newList.insertLast("DPPLE");
    newList.insertLast("CPPLE");
    newList.insertLast("GPPLE");

    newList.insertLast("FPPLE");
    newList.insertLast("ZPPLE");
    newList.insertLast("RPPLE");
    sort(newList);
    newList.displayList();
}
public static void sort(sLinkedList list) {
    sort(0,list.length-1,list);

}

public static void sort(int beginning, int end,sLinkedList list) {
    if(end <= beginning) {
        return;
    }

    int mid = (beginning+end)/2;
    sort(beginning,mid,list);
    sort(mid+1,end,list);
    merge(beginning,mid,end,list);
}

public static void merge(int start, int mid, int end,sLinkedList list) {
    sLinkedList tempList = new sLinkedList();
    int left = start;
    int right = mid+1;
    int k = 0;

    while(left<mid && right<end) {
        if(list.get(left).compareTo(list.get(right))==-1) {
            tempList.insertLast(list.get(left));
            left = left+1;

        }else {
            tempList.insertLast(list.get(right));

            right++;                    

        }
        k++;
    }
    if(left<=mid) {
        while(left<=mid) {
            tempList.insertLast(list.get(left));
            left++;
            k++;

        }


    }else if(right<=end) {
        while(right<=end) {
            tempList.insertLast(list.get(right));
            right++;
            k++;                    

        }


    }
    sllNode current = list.first;
    for(int i=0;i<start;i++) {
        current = current.next;
    }
    for(int i=0;i<tempList.length;i++) {        
        current.data = tempList.first.data;
        current = current.next;
        tempList.first = tempList.first.next;
    }
}

}`

Еще раз, большое спасибо.Я пытаюсь получить список в алфавитном порядке, поэтому в основном Apple - Bpple - Cpple - Dpple - ...... и т. Д.

Ошибка возникает в строке 30

1 Ответ

0 голосов
/ 16 октября 2018

Я обновил ваш код и изменил некоторые из него.это может решить вашу проблему.Однажды я работал над такой проблемой, но это было на c ++, она все еще могла работать с Java-кодом ... дайте мне знать, если это сработало и исправило вашу проблему.

public static void merge (int start, intmid, int end, sLinkedList list) {

sLinkedList tempList = new sLinkedList();
int left = start;    
int right = mid+1; 
int k = start;

while((left<=mid) && (right<=end)) 
{
    if(list.get(left) < (list.get(right)) // compare your if the item on the left is less than the one on the right
    {
        tempList.insertLast(list.get(left));
        left = left+1;
        }
        else {
        tempList.insertLast(list.get(right));

        right++;    

    }
    k++;
}

 for ( int i = left; i <= mid; i++ )
        {
        tempList.insertLast(list.get(i));
            k++;        //moves remaining right list value to temp list
        }

for ( int i = right; i <= end; i++ )
        {
         tempList.insertLast(list.get(i));
            k++;    //moves sorted temp list back to original list
        }

for ( int i = start; i <= end; i++ )

        tempList.insertLast(list.get(i));
        delete tempList;

}

...