双向链表任意遍历打印实现

   实现双向链表的任意遍历打印，涉及到双向链表和递归调用。本这段代码一共实现了5中遍历打印的方法，其中有一种是传入根节点，一种是不需要传入结点，另外3种都是任一个结点的参数。其中printRan3()方法独立实现打印，是这段代码的亮点，printRan2()方法有助于你理解递归调用。printRan4()方法是石军同学实现的，我只是在这里展示。
    看懂这段代码，将很大程度上提高你看懂递归调用的能力。

package linkdemo;

public class LinkDemo {

	public static void main(String args[]){
		LinkDemo demo=new LinkDemo();
		LinkNode foot=demo.creatLink();
        System.out.println("调用printAll()方法打印");
		demo.printAll(foot);
		System.out.println("调用printRan1()方法打印");
		demo.printRan1();
		System.out.println("调用printRan2()方法打印");
		demo.printRan2(foot.getNext());
		System.out.println("调用printRan3()方法打印");
		demo.printRan3(foot.getNext());
		
		foot.delete();    //删除链表中的根节点
		foot.insert(new LinkNode("插入的结点"));
		System.out.println("调用printRan4()方法打印");
		demo.printRan4(foot.getNext());
	}
	
	//创建一个新的链表，返回根节点
	public LinkNode creatLink(){
		LinkNode no1=new LinkNode("节点1");
		LinkNode no2=new LinkNode("节点2");
		LinkNode no3=new LinkNode("节点3");
		LinkNode no4=new LinkNode("节点4");
		LinkNode no5=new LinkNode("节点5");
		
		//手动设置节点在链表中的关系
		no1.setNext(no2);
		no2.setPre(no1);
		no2.setNext(no3);
		no3.setPre(no2);
		no3.setNext(no4);
		no4.setPre(no3);
		no4.setNext(no5);
		no5.setPre(no4);
		LinkNode.setFoot(no1);  //设置no1为根节点
		
		return no1;
	}
	
	//传入链表的根节点，输出所有的节点的值的方法
	public void printAll(LinkNode foot){
		if(foot!=null){
			System.out.println("节点的值是："+foot.getData());
			foot=foot.getNext();
			printAll(foot);
		}
	}
	
	//无需传入任何一个链表中的节点，打印出所有的节点的方法一(使用根节点foot类属性)
	public void printRan1(){
		printAll(LinkNode.getFoot());
	}
	
	//传入链表中任何一个节点，遍历输出所有链表中所有节点的方法二(未使用根节点foot类属性)
	public void printRan2(LinkNode ran){
		boolean b1=true;
		boolean b2=true;
		int count1=0;
		
		printRan(ran,b1,b2,count1);
		
	}
	
	private void printRan(LinkNode ran,boolean b1,boolean b2,int count1){
		//打印ran之后的所有节点
		if(b1&&(ran.getNext()!=null)){
			ran=ran.getNext();
			if(ran.getNext()!=null){
				System.out.println("节点的值是："+ran.getData());
				count1++;
				printRan(ran,b1,b2,count1);
			}

			if(ran.getNext()!=null){
				b1=false;
				b2=false;
			}
		}	
		
		//打印ran节点，并将ran回复到原始出入的ran值
		if(b1){
			System.out.println("节点的值是："+ran.getData());
			
			if(count1!=0){
				for(int i=0;i<count1+1;i++){
					ran=ran.getPre();
				}
				System.out.println("节点的值是："+ran.getData());
			}
			b1=false;
		}
		
		//打印ran节点之前的所有节点
		if(b2){
			ran=ran.getPre();
			if(ran!=null){
				System.out.println("节点的值是："+ran.getData());
				printRan(ran,b1,b2,count1);
			}
			if(ran!=null){
				b2=false;
			}
			System.out.println("****************一组打印完了*******************");
		}
	}
	
	//单个方法实现任一节点的遍历打印:方法三
	//（不需要调用另外的方法，单个参数，不需要使用LinkNode类中的foot属性）
	public void printRan3(LinkNode ran){
		if(ran.getPre()==null){
			while(ran!=null){
				System.out.println(ran.getData());
				ran=ran.getNext();
			}
			return;
		}
		if(ran!=null){
			ran=ran.getPre();
			printRan3(ran);
		}
    }
	
	//传入任意结点，遍历打印所有结点的方法四
	//（不需要使用LinkNode中foot属性，要调用printRan1（）方法）
	//     ——石军同学实现的,没有征得你同意就在这边贴出来了，希望原谅
	public void printRan4(LinkNode ran){
		if(ran.getPre()!=null){
			ran=ran.getPre();
			printRan4(ran);
		}else{
		    printAll(ran);
		}
	}
	
};

package linkdemo;
//链表的节点类
public class LinkNode {

	private LinkNode next;   //下一个节点
	private LinkNode pre;   //前一个节点
	private String data;   //链表的值
	private static LinkNode foot;   //类属性，链表的根节点属性
	
	public LinkNode(String data){
		this.data=data;
	}
	public static LinkNode getFoot(){
		return foot;
	}
	
	
	
	public LinkNode getNext() {
		return next;
	}



	public void setNext(LinkNode next) {
		this.next = next;
	}



	public LinkNode getPre() {
		return pre;
	}



	public void setPre(LinkNode pre) {
		this.pre = pre;
	}



	public String getData() {
		return data;
	}



	public static void setFoot(LinkNode foot) {
		LinkNode.foot = foot;
	}



	//在一个节点后面插入新的节点的方法
	public void insert(LinkNode newNode){
		LinkNode no=this.next;
		
		this.next=newNode;
		newNode.pre=this;
		no.pre=newNode;
		newNode.next=no;
	}
	
	//删除调用该方法的节点
	public void delete(){
		if(this.pre==null){   //如果是首节点
			this.data=this.next.data;
			this.next.next.pre=this;
			this.next=this.next.next;
		}else{
			this.pre.next=this.next;
			this.next.pre=this.pre;
		}	
	}
	
	
};

评论

2 楼 贾懂凯 2010-11-29  

major1314 写道

小小的看了一下，也运行了一次，一个小问题：LindNode中的foot为static，那么当我在LinkDemo中想创建两个链表的时候，根节点怎么办，即如果我在LinkDemo中加入一个函数
public LinkNode creatLink2(){  
   
        LinkNode no1=new LinkNode("节点11");  
        LinkNode no2=new LinkNode("节点21");  
        LinkNode no3=new LinkNode("节点31");  
        LinkNode no4=new LinkNode("节点41");  
        LinkNode no5=new LinkNode("节点51");  
       
        //手动设置节点在链表中的关系  
        no1.setNext(no2);  
        no2.setPre(no1); 
        no2.setNext(no3);  
        no3.setPre(no2); 
        no3.setNext(no4);  
        no4.setPre(no3);     
        no4.setNext(no5);  
        no5.setPre(no4);      
        LinkNode.setFoot(no1);  //设置no1为根节点           
        return no1;  
    }
这儿加入这么一个函数完全只是想创建第二个不同的链表，楼主只提供了一个写死了的函数，没办法用哈，LinkNode node2 = demo.creatLink2();
此时后面再打印的时候可就出问题了，LinkNode.getFoot()得到的可是我第二次创建链表的根节点了哟，foot为static，是属于类的，这里是否真的合适哟？

显然staic属性是类级的，所以在所有对象间共享也是必然的。
我的createLink()只是测试用，如果你想要复用性比较强的方法，可以自己重新去定义。
请注意printRan3()方法，这才是highlight！
注意，本文的链表不是通常意义上的循环双向链表，如果是循环双向链表，上面多有的讨论将变得一文不值！

1 楼 major1314 2010-11-29  

小小的看了一下，也运行了一次，一个小问题：LindNode中的foot为static，那么当我在LinkDemo中想创建两个链表的时候，根节点怎么办，即如果我在LinkDemo中加入一个函数
public LinkNode creatLink2(){  
   
        LinkNode no1=new LinkNode("节点11");  
        LinkNode no2=new LinkNode("节点21");  
        LinkNode no3=new LinkNode("节点31");  
        LinkNode no4=new LinkNode("节点41");  
        LinkNode no5=new LinkNode("节点51");  
       
        //手动设置节点在链表中的关系  
        no1.setNext(no2);  
        no2.setPre(no1); 
        no2.setNext(no3);  
        no3.setPre(no2); 
        no3.setNext(no4);  
        no4.setPre(no3);     
        no4.setNext(no5);  
        no5.setPre(no4);      
        LinkNode.setFoot(no1);  //设置no1为根节点           
        return no1;  
    }
这儿加入这么一个函数完全只是想创建第二个不同的链表，楼主只提供了一个写死了的函数，没办法用哈，LinkNode node2 = demo.creatLink2();
此时后面再打印的时候可就出问题了，LinkNode.getFoot()得到的可是我第二次创建链表的根节点了哟，foot为static，是属于类的，这里是否真的合适哟？