1

我必须为社会安全号码编写一个链表并自己实现所有操作。我编写了 Node 类和列表，但在实现 sortedGet(int index) 方法时遇到了麻烦。我在这种方法中做错了什么？

package listpackage;

import listpackage.SocialNode;

public class SortedListRefBasedDuplicates{
private SocialNode head;
private int numItems = 0;


public SortedListRefBasedDuplicates(){
    head = null;
}

public SocialNode getHead(){
    return this.head;
}

public boolean sortedIsEmpty(){
    return numItems == 0;
}

public int sortedSize(){
    return numItems;
}

public SocialNode sortedGet(int index){
    if(index == 0)
        return head;
    //else if(index >= 0 && index < sortedSize()){
        //for (int i = 0; i < index; i++){
            //head = head.getNext();
        //}
        //return head;
    //}else{
        //return null;
    //}
    else
        return null;
}

public void sortedAdd(int social){
    if(this.sortedIsEmpty()){
        head = new SocialNode(social);
        head.setNext(null);
        numItems++;
    }else{
        int socialIndex = locateIndex(social);
        if(socialIndex == this.sortedSize()){
            SocialNode curr = sortedGet(socialIndex-1);
            SocialNode scn = new SocialNode(social);
            curr.setNext(scn);
            numItems++;
        }else{
            if(socialIndex == 0){
                SocialNode scn = new SocialNode(social);
                scn.setNext(head);
                head = scn;
                numItems++;
            }else{
                SocialNode curr = sortedGet(socialIndex-1);
                SocialNode prev = sortedGet(socialIndex-2);
                SocialNode scn = new SocialNode(social, curr);
                prev.setNext(scn);
                numItems++;
            }
        }
    }
}

public void sortedDelete(int social){

}

public int locateIndex(int social){
    if(numItems == 0)
        return 0;
    else{
        int index = 0;
        while(head != null){
            if(head.getData() < social){
                index ++;
                head = head.getNext();
            }
            else{
                break;
            }
        }
        return index;
    }
  }
}

package listpackage;

public class SocialNode{
private int social;
private SocialNode next;

public SocialNode(int social){
    this.social = social;
    next=null;
}

public SocialNode(int social, SocialNode nextNode){
    this.social = social;
    this.next = nextNode;
}

public int getData(){
    return social;
}

public SocialNode getNext(){
    return next;
}

public void setSocial(int s){
    social = s;
}

public void setNext(SocialNode s){
    next = s;
}
}

添加了 sortedDelete 方法

public void sortedDelete(int social){
if(sortedIsEmpty()){
    System.out.println("List is Empty");
}
else if(sortedSize() == 1){
    if(head.getData() == social)
        head = null;
}else{
    SocialNode x = head;
    if(x.getData() == social)
        head = head.getNext();
    else{
        int count = 1;
        while(x!= null){
            if(x.getData() == social && x.getNext() != null){
                sortedGet(count-1).setNext(sortedGet(count+1));
                break;
            }else{
                sortedGet(count-1).setNext(null);
            }
            x = x.getNext();
            count ++;
        }
    }
  }
}

给定节点的值，如何从列表中删除节点？

4

2 回答 2

8

我看到的主要问题是您通过直接修改head实例变量来迭代列表，因此在您迭代列表时会修改列表，您应该改用局部变量。

于 2013-02-11T01:28:38.977 回答
0

sortedList 的完整实现

package listpackage;

import listpackage.SocialNode;

public class SortedListRefBasedDuplicates{
private SocialNode head;
private int numItems = 0;


public SortedListRefBasedDuplicates(){
    head = null;
}

public SocialNode getHead(){
    return this.head;
}

public boolean sortedIsEmpty(){
    return numItems == 0;
}

public int sortedSize(){
    return numItems;
}

public SocialNode sortedGet(int index){
    SocialNode s = head;
    if(index == 0)
        return s;
    else if(index >= 0 && index < sortedSize()){
        for (int i = 0; i < index; i++){
            s = s.getNext();
        }
        return s;
    }else{
        return null;
    }
}

public void sortedAdd(int social){
    if(this.sortedIsEmpty()){
        head = new SocialNode(social);
        head.setNext(null);
        numItems++;
    }else{
        int socialIndex = locateIndex(social);
        if(socialIndex == this.sortedSize()){
            SocialNode curr = sortedGet(socialIndex-1);
            SocialNode scn = new SocialNode(social);
            curr.setNext(scn);
            numItems++;
        }else{
            if(socialIndex == 0){
                SocialNode scn = new SocialNode(social);
                scn.setNext(head);
                head = scn;
                numItems++;
            }else{
                SocialNode curr = sortedGet(socialIndex);
                SocialNode prev = sortedGet(socialIndex-1);
                SocialNode scn = new SocialNode(social, curr);
                prev.setNext(scn);
                numItems++;
            }
        }
    }
}

public void sortedDelete(int social){
    if(sortedIsEmpty()){
        System.out.println("List is Empty");
    }
    else if(sortedSize() == 1){
        if(head.getData() == social){
            head = null;
            numItems--;
        }
    }else{
        SocialNode x = head;
        if(x.getData() == social){
            head = head.getNext();
            numItems--;
        }
        else{
            int count = 1;
            x = x.getNext();
            while(x!= null){
                if(x.getData() == social && x.getNext() != null){
                    sortedGet(count-1).setNext(sortedGet(count+1));
                    numItems--;
                }else if(x.getData() == social && x.getNext() == null){
                    sortedGet(count-1).setNext(null);
                    numItems--;
                }
                x = x.getNext();
                count ++;
            }
        }
    }
}

public int locateIndex(int social){
    SocialNode x = head;
    if(numItems == 0)
        return 0;
    else{
        int index = 0;
        while(x != null){
            if(x.getData() < social){
                index ++;
                x = x.getNext();
            }
            else{
                break;
            }
        }
        return index;
    }
}
}
于 2013-02-11T03:49:37.047 回答