ch6_e6_25.java

《java语言与面向对象程序设计题解及实验指导》源代码

public class ch6_e6_25             //定义主类
{
    public static void main(String args[])
    {
        LinkList list = new LinkList(new Integer(-1));   //创建链表，含有一个节点

        for(int i=0;i<10;i++)
        {
            list.insertAtBegin(new Integer(i));      //向空链表中插入10个节点
            System.out.println(list.visitAllNode());    //每插入一次，都遍历显示各节点
        }
        
        list.insertAfterId(new Integer(66),new Integer(6));  //在指定位置处插入66，插在数据6的后面   
        System.out.println(list.visitAllNode());//遍历并显示插入操作后的各节点
        list.insertAfterId(new Integer(-2) , new Integer(33));  //在指定位置插入-2，插在数据33的后面（链表中没有33，插在最后）    
        System.out.println(list.visitAllNode());
        if(list.removeAtId(new Integer(4)))      //删除链表中的指定节点
            System.out.println(list.visitAllNode());
        else
            System.out.println("链表中不存在这个数据");
        list.removeAll();           //删除整个链表
    }
}

class LinkList              //定义链表类
{
    Node m_FirstNode;       //链表中的第一个节点

    LinkList()          //构造函数1：建立空链表
    {
        m_FirstNode = null;
    }
    LinkList(Object data)      //构造函数2：建立只有一个节点的链表
    {
        m_FirstNode = new Node(data);
    }
    String visitAllNode()   //遍历链表的每个节点，将所有数据串成一个字符串
    {
        Node next = m_FirstNode;    //从第一个节点开始
        String s = "";
        while(next!=null)           //直到最后一个节点
        {
            s = s + next.getData() + ";  ";
            next = next.getNext();  //next指向下一个节点
        }
        return s;
    }
    void insertAtBegin(Object data)    //将数据data的节点插入在整个链表的前面
    {
        if(m_FirstNode == null)         //对于空链表，直接插入
            m_FirstNode = new Node(data);
        else            //把新节点插在第一个节点前面，并指向原来的第一节点
            m_FirstNode = new Node(data,m_FirstNode);
    }
    void insertAfterId(Object data,Object id)
    {//将数据data插在包含数据id的节点后面若链表中没有id,则插入在整个链表的最后
        Node next = m_FirstNode;
    
        if(next == null)    //对于空链表，直接插入
            m_FirstNode = new Node(data);
        else
        {
            while(next.getNext()!=null && !(next.getData().equals(id)))
                next = next.getNext();              //找到合适的插入位置
            next.setNext( new Node(data,next.getNext()) );
        }
    }
    boolean removeAtId(Object id)      //删除链表中第一个数据为id的节点
    {
        Node ahead = m_FirstNode;   //前面的节点
        Node follow = ahead;        //指向ahead的节点

        if(ahead == null)           //链表为空，删除失败
            return false;
        else if(ahead.getData().equals(id))    //第一个节点就是欲删除节点
        {
            m_FirstNode = m_FirstNode.getNext();        //删除成功
            return true;
        }
        else
        {
            ahead = ahead.getNext();                //第二个节点
            if(ahead==null)                 //若只有一个节点且不是欲删除节点
                return false;                   //删除失败
            else
            {
                while(ahead!=null)
                {
                    if(ahead.getData().equals(id))     //找到匹配的节点
                    {
                        follow.setNext(ahead.getNext());
                        return true;            //删除成功
                    }
                    follow = ahead;         //下移一步，检查下一个节点
                    ahead = ahead.getNext();        //follow跟在ahead后面
                }
                return false;
            }
        }
    }
    void removeAll()                        //删除所有的节点，令链表为空
    {
        m_FirstNode = null;
    }
}//链表类定义结束

class Node 
{
    private Object m_Data;  //节点中保存的数据
    private Node m_Next;    //节点中的指针属性，指向下一个Node对象的对象引用

    Node(Object data)          //构造函数
    {
        m_Data = data;
        m_Next = null;
    }
    Node(Object data, Node next)
    {
        m_Data = data;
        m_Next = next;
    }
    void setData(Object data)  //修改节点中的数据
    {
        m_Data = data;
    }
    Object getData()           //获得节点中的数据
    {
        return m_Data;
    }
    void setNext(Node next)//指定指针指向的Node对象引用
    {
        m_Next = next;
    }
    Node getNext()      //获得节点中的指针指向的对象引用
    {
        return m_Next;
    }
}