uselinklist.java

分治算法解决一维点对最小距离

import java.io.*;
class Node          //定义链表的节点
 {
	  private int mydata;
	  private Node mynext;
	  Node(int data)  //构造方法定义节点
	   {  mydata=data;
		  mynext=null;
	   }
	  Node(int data,Node next) //构造函数定义带数据和指针的节点
	   {  mydata=data;
		  mynext=next;
	   }
	  void setdata(int data)//设置节点数据
	   {  mydata=data;}
	  int getdata()   //取节点数据
	   {  return mydata;}
	  void setnext(Node next) //设置节点指向
	   {  mynext=next;}
	  Node getnext()  //取下一指针
	  { return mynext;}
 }
class linklist//定义链表
{ 
	Node firstnode;   //定义头节点
	linklist()         //构造方法定义空链表
	  {  firstnode=null; }
	linklist(int data)     //构造方法定义带数据的链表
	 { firstnode=new Node(data);}
	String visitallnode()  //遍历节点
	 { 
		Node nextnode=firstnode;
	    String s="";
		if(nextnode!=null)
			s=s+"链表头";
		while(nextnode!=null)
		 {
			s=s+"->"+nextnode.getdata();
			nextnode=nextnode.getnext();
		 }	 
		return s;
	  }
	void addatend(int data)  //在末尾增加节点
	 { Node nextnode=firstnode;
	   if(nextnode==null)
		   firstnode=new Node(data);
	   else {
		   while(nextnode.getnext()!=null)
		    nextnode=nextnode.getnext();
		   nextnode.setnext(new Node(data));
			 }			
	  }
     void insertafterid(int data,int id)  //在id后插入节点
	 { Node nextnode=firstnode;
	   if(nextnode==null)
		   firstnode=new Node(data);
	   else {
		   while(nextnode.getnext()!=null&&nextnode.getdata()!=id)
			  nextnode=nextnode.getnext();
		   nextnode.setnext(new Node(data,nextnode.getnext()));
			 }			
	  }
	boolean deleteatid(int id)  //删除id节点
	 { 
		Node ahead=firstnode;
	    Node follow=ahead;
		if(ahead==null)
			return false;
		else if(ahead.getdata()==id)
			{  firstnode=firstnode.getnext();
	           return true;
			 }
        else
		 {  ahead=ahead.getnext();
		    while(ahead!=null)
			 {
				if(ahead.getdata()==id)
				 {  follow.setnext(ahead.getnext());
				    return true;
			     }
			follow=ahead;
			ahead=ahead.getnext();
		       }
		  return false;
	     }	
		}
	void removeall()
	  {   firstnode=null; }
 }
public class uselinklist    //操作链表程序
{
	int indata;
	static String aa="0";
	String msg="";
	linklist mylist=new linklist();
	public static void main(String args[])
	{
		uselinklist pp=new uselinklist();
		try
		{
			while(true) //保证循环
			{
				System.out.println("按a键增加节点；按i键将插入节点;按d键将删除节点；按o退出");
	            BufferedReader cc=new BufferedReader(new InputStreamReader(System.in));
				 aa=cc.readLine();
				 if(aa.equals("a"))//测试所按键是否是a键
				   pp.add();
				 else if(aa.equals("i"))
				   pp.insert();
				 else if(aa.equals("d"))
				   pp.delete();									  
		         else if(aa.equals("o"))
				   break;
			}
		}catch(IOException e){System.out.println(e);}
	 }
	void add()
	{
	  try
	   {
		 while(true)
		 { System.out.println("请输入增加的节点（整数）：（退出请按o键）");
		   BufferedReader cc=new BufferedReader(new InputStreamReader(System.in));
		   aa=cc.readLine();
		   if(aa.equals("o"))  break;
		   else{
			   indata=Integer.parseInt(aa);
			   mylist.addatend(indata);
			   draw();}
		 }
	  }catch(IOException e) {System.out.println(e);}
	}
     void insert()
      {  try
          {
            while(true)    
			{ System.out.println("请输入插入的节点（整数）：（退出请按o键）");
		      BufferedReader cc=new BufferedReader(new InputStreamReader(System.in));
		      aa=cc.readLine();
              if(aa.equals("o"))
					break;
			  else {
					indata=Integer.parseInt(aa);
					System.out.println("请输入插入节点的位置(整数):（退出请按o键）");
					BufferedReader rr=new BufferedReader(new InputStreamReader(System.in));
		            aa=rr.readLine();	
					int insertid=Integer.parseInt(aa);
					 mylist.insertafterid(indata,insertid);
					 draw();
					}
				}
		}catch(IOException e) {System.out.println(e);}
	 }	
 void delete()
	{try
          {
            while(true)    
			{ 
			  System.out.println("请输入删除的节点（整数）：（退出请按o键）");
		      BufferedReader cc=new BufferedReader(new InputStreamReader(System.in));
		      aa=cc.readLine();
              if(aa.equals("o"))
					break;
			  else {
					indata=Integer.parseInt(aa);
					if(mylist.deleteatid(indata)==false)
						 msg="链表中不存在这个数据";
                    draw();
				   }
			}
		  }catch(IOException e) {System.out.println(e);}
	  }	
  void draw()
    {
	    System.out.print(mylist.visitallnode());
		System.out.println("\t"+msg);
		msg="";
	 }
}