버그 해결을 위한 모든 질문을 던져
0 votes
190 views
import java.util.*;

/**
 * Generic version of the SortedList class.
 */

class SortedList <T extends Comparable<T> > {

    class SortedListNode <U extends Comparable<U> >{
        U data; // storage for data
        SortedListNode<U> link;    // link to the next node
    };
    
    private SortedListNode<T> first; // pointer to the dummy header node
    private SortedListNode<T> av; // pointer to the available list

    public SortedList() {
        av = null;
        first = null;
    }

    void Init(T data) { // SortedList constructor. Create a dummy first node
        first = GetNode();
        first.data = data;
        first.link = first;
        System.out.println("init");
    }

    void Clear() {    
        SortedListNode<T> x = first.link;
        first.link = av;
        av = x;

        System.out.println("clear");
    }

    SortedListNode<T> GetNode() {    
        SortedListNode<T> x = null;
        if(av==null){
            x = new SortedListNode<T>();
            System.out.println("1av=null3");
        }

        else{
            x =av;
            av =  av.link;
            System.out.println("x=av3123");
        }

        return x;
    
    void  Insert(T e) {    
        SortedListNode<T> x = GetNode();
        x.data = e;

        SortedListNode<T> current = first;
        SortedListNode<T> before = null;
        
        current=current;

        System.out.println("insert start");
        while(current !=null && e.compareTo(current.data)<=0){
            System.out.println("insert compare");
            before = current;
            current = current.link;
        }
        
        if(before==null){
            first = x;
        }
        else{
            before.link=x;
        }
        x.link=current;

    }

    public String toString() {
        String str = "";

        if(first == null) return "";
        SortedListNode<T> p = first.link;

        str += "List : ";
        // traverse all the nodes
        while (p != first) {
            str += p.data + "  ";
            p = p.link;
        }
        str += "\n";

        p = av;
        // show the count of av list
        int cnt = 0;
        while (p != null) {
            cnt++;
            p = p.link;
        }
        str +=  "Av : " + cnt;

        return str;
    }
};

 

 

-----------------------------------------------------------------------------------------

import java.util.*;

class LabTest {
    static Scanner in;
    public static void main(String[] args) {
        in = new Scanner(System.in);

        SortedList<Integer> slone = new SortedList<Integer>();
        slone.Init(100000000);

        while(true) {
            try {
                System.err.println("SL > ");
    
                String cmd = in.next();
                if(cmd.equals("put")) {
                    int item = in.nextInt();
                    slone.Insert(item);
                } else if(cmd.equals("clear")) {
                    slone.Clear();
                    slone.Init(100000000);
                } else if(cmd.equals("quit"))
                    break;
            } catch (Exception e) {
                System.out.println(e);
            }
            System.out.println(slone);
        }
    }
}
asked (2 point) , 190 views

1 답변

0 votes

일단 저는 lab이 뭔지 몰라서 코드만 가지고 질문자님의 의도를 파악했다는 점을 고려해 주세요.

어디서부터 말씀드려야 할지 좀 난감하군요. 아마 학습용으로 작성하신 코드로 보여서 완성된 코드를 그대로 던지는건 예의가 아닌듯해서 그렇게 답변을 드리지는 않겠습니다.

우선 무한루프에 대한 답만 말씀드리자면 Insert 함수의 동작 구조와 SortedList클래스의 처음 상태가 특정한 룰을 만족하는 경우에 무한 루프가 돌 수 있을 것 같습니다. 설명을 위해 질문상의 코드의 일부를 좀 적어보겠습니다.

// SortedList 중...
    void Init(T data) { // SortedList constructor. Create a dummy first node
        first = GetNode();
        first.data = data;
        first.link = first;
        System.out.println("init");
    }

/// Insert 메소드 중..
    while(current !=null && e.compareTo(current.data)<=0){

여기서 잘 보시면 처음 리스트를 초기화 할때 first.link를 자신으로 설정합니다. 즉 first노드로 부터 시작해서 link를 타고 탐색하면 무한히 탐색이 되겠지요 자신을 계속해서 보게 될테니까요.

그런데 Insert구문의 while안쪽을 보시면 처음에 first로 설정된 current가 null이 아니면서 data값이 Init에 넣어준 초기값 (위 예시에서는 100000000이죠?) 보다 작은동안 계속해서 current.link를 이용해서 탐색합니다. 즉 Insert해준 값이 초기값인 100000000 보다 작으면 무한루프가 돌겠죠. 디버깅을 거기서부터 시작해 보시는건 어떨까요?

-----------------------

아래로는 직접 SortedList를 좀 정상화 시켜 보면서 들었던 생각들은 조언식으로 정리해 보았습니다. 저도 제가 맞다고는 할 수 없으니 그냥 참고삼아 읽고 넘어가셔도 좋을것 같습니다.

우선.. 이건 어차피 원론적인 부분이고 링크드 리스트에 대한 탐구용이라면 아무런 상관이 없는 이야기 이긴 합니다만. SortedList라는 이름이 내포하는 정렬된 리스트를 구현하는 컨테이너로서(Data Structure) 링크드 리스트는 별로 좋은 선택은 아닙니다. 이미 정렬된 리스트에 대한 삽입의 경우 바이너리 서치를 이용해서 삽입할 위치를 찾는것이 효과적이므로 임의 접근이 가능한 자료구조를 이용하는 것이 좋습니다...

두번째로 더미노드를 운용하는 부분인데요. 개인적인 의견으로는 굳이 first라는 더미노드를 운용해야할 필요성을 느끼지 못하겠습니다. 코드 작성의 편의를 위해서 차용하신거라면 말리진 않겠습니다만 굳이 사용하실 거라면 현재 코드 구조에서는 Init시에 넣어주신 100000000보다 큰 수치가 입력되는 경우 first가 해당 값으로 갱신되면서 리스트의 작동에 이상이 생길 것이라는 점 정도만 언급드리고 싶군요. 지금처럼 first node의 data값을 실제 비교에 이용하고 있는 상황에서는 위의 예외 상황에 깔끔하게 대응하는게 쉽지 않을 것 같아 보입니다.

이상입니다~

answered (240 point)
순간적인답답함에 무례하게 코드만 던졌습니다.

후에 차근히 검토하고 해결했습니다.

관심과 답변정말감사드립니다.:)

노력하는 학생되겠습니딘.

버그 해결을 위해 도움을 구하고, 도움을 주세요. 우리는 그렇게 발전합니다.

throw bug 는 프로그래밍에 대한 전분야를 다룹니다. 질문,논의거리,팁,정보공유 모든 것이 가능합니다. 프로그래밍과 관련이 없는 내용은 환영받지 못합니다.

167 질문
272 answers
288 댓글
281 users