A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 骑上最爱 中级黑马   /  2013-6-1 10:44  /  1104 人查看  /  2 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 骑上最爱 于 2013-6-1 19:46 编辑

关于链表的结构,和数据原理是什么?

评分

参与人数 1技术分 +1 收起 理由
袁梦希 + 1 很给力!

查看全部评分

2 个回复

倒序浏览
说下当初自己简单的理解(网络查的,挺好理解的),当然每个人都有自己的理解方法,我的理解楼主不一定适合,有错的说请谅解:
链表的建立,我认为可以用下面的的方式表达出来!
  假设有3个人,分别叫head, now, last; 有一天now发现了一张宝藏图,于是他先到了寻找宝藏的第一站,但now很无私他想和别人一起分享,于是
  他在第一站打电话把head, last叫来。来到后,他们三个商量后,决定让head留在第一站,如果还有别人想发掘宝藏,就直接找head, 而now负责去
  寻找下一站,每找到一站,他就打电话给last,让last去那个站,然而为了保证在来人能找到下一站,last在去寻找now时,必须留下标记,告诉再来着
  下一站的位置,,就这样now在前来路,,last负责标记,head成为找第一站的关键,找到第一站,也就意味着找到了所有站(last在去和head会合时已经在他呆的那一站做好了他去下一站的标记);
附上list的源码,助于理解:
  1.   import java.io.*;
  2.   public class List
  3.   {
  4.   /*用变量来实现表头*/
  5.   private Node Head=null;
  6.   private Node Tail=null;
  7.   private Node Pointer=null;
  8.   private int Length=0;
  9.   public void deleteAll()
  10.   /*清空整个链表*/
  11.   {
  12.   Head=null;
  13.   Tail=null;
  14.   Pointer=null;
  15.   Length=0;
  16.   }
  17.   public void reset()
  18.   /*链表复位,使第一个结点成为当前结点*/
  19.   {
  20.   Pointer=null;
  21.   }
  22.   public boolean isEmpty()
  23.   /*判断链表是否为空*/
  24.   {
  25.   return(Length==0);
  26.   }
  27.   public boolean isEnd()
  28.   /*判断当前结点是否为最后一个结点*/
  29.   {
  30.   if(Length==0)
  31.    throw new java.lang.NullPointerException();
  32.   else if(Length==1)
  33.    return true;
  34.   else
  35.    return(cursor()==Tail);
  36.   }
  37.   public Object nextNode()
  38.   /*返回当前结点的下一个结点的值,并使其成为当前结点*/
  39.   {
  40.   if(Length==1)
  41.    throw new java.util.NoSuchElementException();
  42.   else if(Length==0)
  43.    throw new java.lang.NullPointerException();
  44.   else
  45.   {
  46.    Node temp=cursor();
  47.    Pointer=temp;
  48.    if(temp!=Tail)
  49.     return(temp.next.data);
  50.    else
  51.     throw new java.util.NoSuchElementException();
  52.   }
  53.   }
  54.   public Object currentNode()
  55.   /*返回当前结点的值*/
  56.   {
  57.   Node temp=cursor();
  58.   return temp.data;
  59.   }
  60.    
  61.   public void insert(Object d)
  62.   /*在当前结点前插入一个结点,并使其成为当前结点*/
  63.   {
  64.   Node e=new Node(d);
  65.   if(Length==0)
  66.   {
  67.    Tail=e;
  68.    Head=e;
  69.   }
  70.   else
  71.   {
  72.    Node temp=cursor();
  73.    e.next=temp;
  74.    if(Pointer==null)
  75.     Head=e;
  76.    else
  77.     Pointer.next=e;
  78.   }
  79.   Length++;
  80.   }
  81.   public int size()
  82.   /*返回链表的大小*/
  83.   {
  84.   return (Length);
  85.   }
  86.   public Object remove()
  87.   /*将当前结点移出链表,下一个结点成为当前结点,如果移出的结点是最后一个结点,则第一个结点成为当前结点*/
  88.   {
  89.   Object temp;
  90.   if(Length==0)
  91.    throw new java.util.NoSuchElementException();
  92.   else if(Length==1)
  93.   {
  94.    temp=Head.data;
  95.    deleteAll();
  96.   }
  97.   else
  98.   {
  99.    Node cur=cursor();
  100.    temp=cur.data;
  101.    if(cur==Head)
  102.     Head=cur.next;
  103.    else if(cur==Tail)
  104.    {
  105.     Pointer.next=null;
  106.     Tail=Pointer;
  107.     reset();
  108.    }
  109.    else
  110.     Pointer.next=cur.next;
  111.     Length--;
  112.   }
  113.   return temp;
  114.   }
  115.   private Node cursor()
  116.   /*返回当前结点的指针*/
  117.   {
  118.   if(Head==null)
  119.    throw new java.lang.NullPointerException();
  120.   else if(Pointer==null)
  121.    return Head;
  122.   else
  123.    return Pointer.next;
  124.   }
  125.   public static void main(String[] args)
  126.   /*链表的简单应用举例*/
  127.   {
  128.   List a=new List ();
  129.   for(int i=1;i<=10;i++)
  130.    a.insert(new Integer(i));
  131.    System.out.println(a.currentNode());
  132.    while(!a.isEnd())
  133.     System.out.println(a.nextNode());
  134.     a.reset();
  135.     while(!a.isEnd())
  136.     {
  137.      a.remove();
  138.     }
  139.     a.remove();
  140.     a.reset();
  141.     if(a.isEmpty())
  142.      System.out.println("There is no Node in List \n");
  143.      System.in.println("You can press return to quit\n");
  144.     try
  145.     {
  146.      System.in.read();
  147.      //确保用户看清程序运行结果
  148.     }
  149.     catch(IOException e)
  150.     {}
  151.    }
  152.   }
  153.   class Node
  154.   /*构成链表的结点定义*/
  155.   {
  156.    Object data;
  157.    Node next;
  158.    Node(Object d)
  159.    {
  160.     data=d;
  161.     next=null;
  162.    }
  163.   }

  164.   读者还可以根据实际需要定义新的方法来对链表进行操作。双向链表可以用类似的方法实现只是结点的类增加了一个指向前趋结点的指针。

  165.   可以用这样的代码来实现:

  166.   class Node
  167.   {
  168.   Object data;
  169.   Node next;
  170.   Node previous;
  171.   Node(Object d)
  172.   {
  173.   data=d;
  174.   next=null;
  175.   previous=null;
  176.   }
  177.   }
复制代码

评分

参与人数 1技术分 +1 收起 理由
袁梦希 + 1 很给力!

查看全部评分

回复 使用道具 举报
如果问题已解决,请及时修改分类,否则继续提问,谢谢合作!
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马