import java.io.InputStreamReader;
import java.io.BufferedReader;
/**
Class LinkDemo
Description 链表的基本操作，某个位置插入一个新的节点，查看和删除指定节点，
Conpany opendata
Author Chenlly
Version 1.0
Date 09-02-28
补充：链表是以时间换空间，有多少数据项就开辟了多少空间，不会浪费(当然，每个节点可能比数组多，除了数据域还有指针域)
随机查找慢，每次查找一个元素都要一个一个找，它所强调的是关系。而数组只需要知道下标就可以直接定位到这个数据(通过公式
可以做随机访问),但在做频繁插入和删除时，链表快，而数组慢。因为它还的移动其它元素。
*/
//人类
class Persion{
private int id;
private double height;
private String name;
public Persion(int id,double height,String name){
this.id=id;
this.height=height;
this.name=name;
}
//getter,setter方法
public int getID(){
return this.id;
}
public void setID(int id){
this.id=id;
}
//重写equalsss方法
public boolean equals(Object o){
if(o==null){
return false;
}
if(o==this){
return true;
}
if(!(o instanceof Persion)){
return false;
}
Persion p=(Persion)o;
return p.id==this.id&&p.height==this.height&&p.name==this.name;
}
//重写String方法
public String toString(){
return("[id:"+id+",height:"+height+",name:"+name+"]");
}
}
//链节点
class Link{
public Persion persion;
public Link next;//设置成公有的，是这个属性在其它类中可以通过.next访问，而不需要通过方法访问
public Link(Persion persion){
this.persion=persion;
}
}
//链表操作
public class LinkDemo{
private Link firstLink,link;
private Link tailLink;
//头结点初始值为null
public LinkDemo(){
firstLink=null;
}
//查看链表是否是空
public boolean isEmpty(){
return firstLink==null;
}
//创建一个新节点
public Link createLink(Persion persion){
Link link=new Link(persion);
return link;
}
//在链表头部插入一个新的节点
public void insertFirst(Link newLink){
newLink.next=firstLink;
firstLink=newLink;
}
//在表尾插入一个新节点
public void insertTail(Link newLink){
//因为是空链表
if(firstLink==null){
firstLink=newLink;
tailLink=firstLink;
}else{//尾指针指向链表表尾
if(tailLink==null){//因为头插入已经插入数据，而tailLink还是null
tailLink=firstLink;
while(tailLink.next!=null){//注意这里的判断条件是tailLink.next
tailLink=tailLink.next;
}
}
//在链表表尾做插入，同时移动尾指针
tailLink.next=newLink;
tailLink=newLink;
}
}
/**通过关键字(id)查找链节点
@param id
@return 找到了节点返回此节点，否则返回null
*/
public Link find(int id){
Link current=firstLink;
while(!(current.persion.getID()==id)){
//因为找到了链未
if(current.next==null){
return null;
}else{
current=current.next;
}
}//end while
//找到了这个节点要返回
return current;
}
//删除找到的这个链节点
public Link delete(Link link){
Link current=firstLink; //当前节点
Link previous=firstLink;//前继节点
while(!(current.persion.equals(link.persion))){
//因为找到了链未,还没找到这个节点
if(current.next==null){
return null;
}else{
previous=current;
current=current.next;
}
}
//找到了这个节点，要做删除
if(current==firstLink){ //因为头节点就是要找的节点,当前节点没有移动
current.next=firstLink;
}else{
previous.next=current.next;
}
return current;
}
//链接点的后面插入一个新的节点
public void insertLinkByFind(Link previousLink,Link newLink){
newLink.next=previousLink.next;
previousLink.next=newLink;
}
//显示一个链表中所有节点的数据项
public void display(){
Link current=firstLink;
System.out.print("链表的所有节点数据为:{");
while(current!=null){
System.out.print(""+current.persion.toString()+",");
current=current.next;
}
System.out.println("}");
}
//从键盘上读入数据
public static String readStr(){
String str="";
try{
InputStreamReader ir=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(ir);
str=br.readLine();
}catch(Exception ex){
ex.printStackTrace();
}
return str;
}
//从键盘读入数据，构造一个persion对象
public Persion createPersion(){
System.out.println("请输入ID:");
int id=Integer.parseInt(LinkDemo.readStr());
System.out.println("请输入身高:");
double height=Double.parseDouble(LinkDemo.readStr());
System.out.println("请输入名字:");
String name=LinkDemo.readStr();
Persion persion=new Persion(id,height,name);
return persion;
}
//主调函数
public static void main(String []args){
System.out.println("链表的基本操作请选择");
System.out.println("1 在链表的头插入新节点");
System.out.println("2 在链表的尾部插入新节点");
System.out.println("3 在链表中查找包含某个关键字(ID)的节点，并且删除此节点");
System.out.println("4 在链表中包含某个关键字节点的后面插入一个新的节点");
System.out.println("5 显示链表数据项");
System.out.println("6 退出");
LinkDemo linkDemo=new LinkDemo();
while(true){
System.out.println("请选择操作序列:");
int op=Integer.parseInt(LinkDemo.readStr());
switch(op){
case 1:
System.out.println("头插法，请输入人类信息:");
Persion persion=linkDemo.createPersion();
Link link=linkDemo.createLink(persion);
linkDemo.insertFirst(link);
break;
case 2:
System.out.println("尾插法，请输入人类信息:");
Persion tpersion=linkDemo.createPersion();
Link tlink=linkDemo.createLink(tpersion);
linkDemo.insertTail(tlink);
break;
case 3:
System.out.println("请输入查找ID:");
int id=Integer.parseInt(LinkDemo.readStr());
Link keyLink=linkDemo.find(id);
if(keyLink!=null){
System.out.println("找到这个关键字"+keyLink.persion);
System.out.println("是否选择删除这个节点(Y(y)/N(n))");
char c=LinkDemo.readStr().charAt(0);
if(c=='Y'||c=='y'){
Link dlink=linkDemo.delete(keyLink);
if(dlink!=null){
System.out.println("此关键字对应的链节点已删除,删除的链接点是"+dlink.persion+"");
}else{
System.out.println("不能删除此关键字对应的链节点");
}
}else{
break;//不做删除
}
}else{
System.out.println("此链表中没有包含这个关键字的节点");
}
break;
case 4:
System.out.println("请输入查找ID:");
int nid=Integer.parseInt(LinkDemo.readStr());
Link nkeyLink=linkDemo.find(nid);
if(nkeyLink!=null){
System.out.println("找到这个关键字"+nkeyLink.persion);
System.out.println("在这个节点后面插入新节点,请初始化需要插入的新节点");
Persion newPersion=linkDemo.createPersion();
Link newLink=linkDemo.createLink(newPersion);
linkDemo.insertLinkByFind(nkeyLink,newLink);
}else{
System.out.println("此链表中没有包含这个关键字的节点");
}
break;
case 5:
linkDemo.display(); break;
case 6:
defualt:System.exit(0);
}//end switch
}//end while
}//end main
}//end LinkDemo