黑马程序员技术交流社区
标题:
关于链表
[打印本页]
作者:
骑上最爱
时间:
2013-6-1 10:44
标题:
关于链表
本帖最后由 骑上最爱 于 2013-6-1 19:46 编辑
关于链表的结构,和数据原理是什么?
作者:
刘海芳
时间:
2013-6-1 10:51
说下当初自己简单的理解(网络查的,挺好理解的),当然每个人都有自己的理解方法,我的理解楼主不一定适合,有错的说请谅解:
链表的建立,我认为可以用下面的的方式表达出来!
假设有3个人,分别叫head, now, last; 有一天now发现了一张宝藏图,于是他先到了寻找宝藏的第一站,但now很无私他想和别人一起分享,于是
他在第一站打电话把head, last叫来。来到后,他们三个商量后,决定让head留在第一站,如果还有别人想发掘宝藏,就直接找head, 而now负责去
寻找下一站,每找到一站,他就打电话给last,让last去那个站,然而为了保证在来人能找到下一站,last在去寻找now时,必须留下标记,告诉再来着
下一站的位置,,就这样now在前来路,,last负责标记,head成为找第一站的关键,找到第一站,也就意味着找到了所有站(last在去和head会合时已经在他呆的那一站做好了他去下一站的标记);
附上list的源码,助于理解:
import java.io.*;
public class List
{
/*用变量来实现表头*/
private Node Head=null;
private Node Tail=null;
private Node Pointer=null;
private int Length=0;
public void deleteAll()
/*清空整个链表*/
{
Head=null;
Tail=null;
Pointer=null;
Length=0;
}
public void reset()
/*链表复位,使第一个结点成为当前结点*/
{
Pointer=null;
}
public boolean isEmpty()
/*判断链表是否为空*/
{
return(Length==0);
}
public boolean isEnd()
/*判断当前结点是否为最后一个结点*/
{
if(Length==0)
throw new java.lang.NullPointerException();
else if(Length==1)
return true;
else
return(cursor()==Tail);
}
public Object nextNode()
/*返回当前结点的下一个结点的值,并使其成为当前结点*/
{
if(Length==1)
throw new java.util.NoSuchElementException();
else if(Length==0)
throw new java.lang.NullPointerException();
else
{
Node temp=cursor();
Pointer=temp;
if(temp!=Tail)
return(temp.next.data);
else
throw new java.util.NoSuchElementException();
}
}
public Object currentNode()
/*返回当前结点的值*/
{
Node temp=cursor();
return temp.data;
}
public void insert(Object d)
/*在当前结点前插入一个结点,并使其成为当前结点*/
{
Node e=new Node(d);
if(Length==0)
{
Tail=e;
Head=e;
}
else
{
Node temp=cursor();
e.next=temp;
if(Pointer==null)
Head=e;
else
Pointer.next=e;
}
Length++;
}
public int size()
/*返回链表的大小*/
{
return (Length);
}
public Object remove()
/*将当前结点移出链表,下一个结点成为当前结点,如果移出的结点是最后一个结点,则第一个结点成为当前结点*/
{
Object temp;
if(Length==0)
throw new java.util.NoSuchElementException();
else if(Length==1)
{
temp=Head.data;
deleteAll();
}
else
{
Node cur=cursor();
temp=cur.data;
if(cur==Head)
Head=cur.next;
else if(cur==Tail)
{
Pointer.next=null;
Tail=Pointer;
reset();
}
else
Pointer.next=cur.next;
Length--;
}
return temp;
}
private Node cursor()
/*返回当前结点的指针*/
{
if(Head==null)
throw new java.lang.NullPointerException();
else if(Pointer==null)
return Head;
else
return Pointer.next;
}
public static void main(String[] args)
/*链表的简单应用举例*/
{
List a=new List ();
for(int i=1;i<=10;i++)
a.insert(new Integer(i));
System.out.println(a.currentNode());
while(!a.isEnd())
System.out.println(a.nextNode());
a.reset();
while(!a.isEnd())
{
a.remove();
}
a.remove();
a.reset();
if(a.isEmpty())
System.out.println("There is no Node in List \n");
System.in.println("You can press return to quit\n");
try
{
System.in.read();
//确保用户看清程序运行结果
}
catch(IOException e)
{}
}
}
class Node
/*构成链表的结点定义*/
{
Object data;
Node next;
Node(Object d)
{
data=d;
next=null;
}
}
读者还可以根据实际需要定义新的方法来对链表进行操作。双向链表可以用类似的方法实现只是结点的类增加了一个指向前趋结点的指针。
可以用这样的代码来实现:
class Node
{
Object data;
Node next;
Node previous;
Node(Object d)
{
data=d;
next=null;
previous=null;
}
}
复制代码
作者:
殇_心。
时间:
2013-6-1 18:08
如果问题已解决,请及时修改分类,否则继续提问,谢谢合作!
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2