双向链表问题

九分石人
  • 8

总是空指针异常??

package two;
//双向链表
class link3{//链表的结点类

public int iData; //相当于一个节点的标志
public double fData; //数据域
public link3 L_next; //左指针域
public link3 R_next; //右指针域
public link3(){ //头结点的构造方法
    iData = -1;
    fData = -1.0;
//    L_next = null; 可写可不写,指针域自动赋值为null
//    R_next = null;
}

public link3(int iD, double fD){ //节点的构造方法,构造函数的重载
    iData = iD; //数据域赋初值
    fData = fD;    //指针域自动赋值为null
}

public void linkDisplay(){ //显示自身的数据域
    System.out.println("["+iData+","+fData+"]");
}

}//链表的结点类结束

class linkList3{ //双向链表类

public link3 first; //头指针
public linkList3(){ //构造方法
    first = new link3(); //空链表,头指针指向头结点
}

public boolean isEmpty(){ //链表是否为空
    return (first.L_next == null && first.R_next == null); //头结点的左右指针都为空
}

public link3 linkFind(int id){ //查找给定标志的结点,返回结点
    link3 p = first; //指向第一个节点,从头结点开始查找
    while(p.iData != id && p.R_next != null) //不是当前结点的位置并且没有到达链尾
        p = p.R_next;
    if(p.R_next != null)
        return p; //找到
    else
        return null;
}

//在第L个结点左右位置插入一个新结点
public boolean insertWhere(int L,int id,double fd,int flage){
    link3 newlink = new link3(id,fd); //诞生一个新节点newlink
    int i =1;
    link3 p = first; //指向第一个节点
    while(p.R_next != null && i++ < L){ //p指针后移L个结点
        p = p.R_next;
    }
    if(p == first){ //如果是在头结点后面插入
        first.R_next = newlink; 
        newlink.L_next = first;
        return true;
    }
    if(p.R_next!=null&&p.L_next!=null    ) {
        if(flage == 0  ){ //如果在第L个结点的后继进行插入
            p.R_next.L_next = newlink;
            newlink.L_next = p;
            newlink.R_next = p.R_next;
            p.R_next = newlink;
        
        }else{    //在第L各结点的前驱进行插入
            p.L_next.R_next = newlink;
            newlink.R_next = p;
            newlink.L_next = p.L_next;
            p.L_next = newlink;
            
        }
        return true;
    }else
        return false;
}

public link3 deleteWhere(int L,int flage){ //删除第L个结点左右的结点
    if(isEmpty())
        return null;
    link3 p =first; //指向第一个节点
    link3 q; //要删除的结点
    int i =1;
    while(p.R_next != null && i++ < L)
        p = p.R_next; //找到要删除的结点
    if(p == first)
        return null;
    if(flage == 0){    //在第L各结点的右边进行删除
        q = p.R_next ;
        p.R_next = p.R_next.R_next;
        p.R_next.L_next = p;
        return q;
    }else{ //在第L各结点的左边进行删除
        q = p.L_next;
        p.L_next = p.L_next.L_next;
        p.L_next.R_next = p;
        return q;
    }
}

//显示全部链表
public void listDisplay(){
    link3 p = first.R_next; //指向第一个节点
    System.out.println("显示链表:从前到后");
    while(p != null){
        p.linkDisplay(); //显示节点
        p = p.R_next;
    }
    System.out.println("*******");
}

//返回链表的长度(节点数)
public int listLength(){
    link3 p = first.R_next; //指向第一个节点
    int i = 0;
    while(p != null){
        p = p.R_next;
        i++;
    }
    return i;
}

//置链表为空
public void makeEmpty(){
    first.R_next = null;
}

}//链表类结束

class List3{

public static void main(String []args) {
    linkList3 s1=new linkList3(); //空链表诞生
    s1.insertWhere(1,3086,52.3,0);  //从指定位置插入结点
    s1.insertWhere(2,3087,82.7,1);
    s1.insertWhere(3,3089,73.67,0);
    s1.insertWhere(4,3090,67.2,1);
    s1.insertWhere(5,3091,62.5,0);
    s1.insertWhere(3,3088,92.1,1);  //从指定位置插入结点
    s1.listDisplay();
    s1.deleteWhere(4,1); //删除第4个结点
    s1.deleteWhere(2,1);
    s1.listDisplay();  
    link3 t=s1.linkFind(3088);  //查找结点
    if(t!=null) 
        t.linkDisplay(); //显示该结点
    //s1.makeEmpty();
    //s1.listDisplay(); 
    System.out.println(s1.listLength());
}

}

回复
阅读 981
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
你知道吗?

宣传栏