网站主页   操作系统    网络工程    服务器    网页制作    数据库    程序开发    网络安全    办公软件   
讲座日期: 本周六下午1点30分 抢座
讲座地点: 北大青鸟马甸校区
主讲老师: 王老师 金牌讲师
讲座主题: 网络安全
讲座内容: 检测、防御、黑客信息,如何过滤不安全的网站,如何防御黑客的进攻。
订座电话: 010-82011432/33
  您当前位置:主页 > 网络学院 > 程序开发 > JSP教程 >

Java语言中链表和双向链表




  链表是一种重要的数据结构,在程序设计中占有很重要的地位。C语言和C++语言中是用指针来实现链表结构的,由于Java语言不提供指针,所以有人认为在Java语言中不能实现链表,其实不然,Java语言比C和C++更容易实现链表结构。Java语言中的对象引用实际上是一个指针(本文中的指针均为概念上的意义,而非语言提供的数据类型),所以我们可以编写这样的类来实现链表中的结点。

  class Node
  {
  Object data;
  Node next;//指向下一个结点
  }

  将数据域定义成Object类是因为Object类是广义超类,任何类对象都可以给其赋值,增加了代码的通用性。为了使链表可以被访问还需要定义一个表头,表头必须包含指向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部增加结点,还可以增加一指向链表尾部的指针,另外还可以用一个域来表示链表的大小,当调用者想得到链表的大小时,不必遍历整个链表。下图是这种链表的示意图:

  链表的数据结构

  我们可以用类List来实现链表结构,用变量Head、Tail、Length、Pointer来实现表头。存储当前结点的指针时有一定的技巧,Pointer并非存储指向当前结点的指针,而是存储指向它的前趋结点的指针,当其值为null时表示当前结点是第一个结点。那么为什么要这样做呢?这是因为当删除当前结点后仍需保证剩下的结点构成链表,如果Pointer指向当前结点,则会给操作带来很大困难。那么如何得到当前结点呢,我们定义了一个方法cursor(),返回值是指向当前结点的指针。类List还定义了一些方法来实现对链表的基本操作,通过运用这些基本操作我们可以对链表进行各种操作。例如reset()方法使第一个结点成为当前结点。insert(Object d)方法在当前结点前插入一个结点,并使其成为当前结点。remove()方法删除当前结点同时返回其内容,并使其后继结点成为当前结点,如果删除的是最后一个结点,则第一个结点变为当前结点。

  链表类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;
  }
  }

  当然,双向链表基本操作的实现略有不同。链表和双向链表的实现方法,也可以用在堆栈和队列的实现中,这里就不再多写了,有兴趣的读者可以将List类的代码稍加改动即可。


  • 2005年5月10日
  • 2005年3月30日
  • 2005年3月30日
  • 2005年3月30日
  • 2005年3月30日
  • 2005年3月29日
  • 2005年3月29日
  • 2005年3月29日
  • 2005年3月29日
  • 2005年3月28日
  • 2005年3月28日
  • 2005年3月28日


  • 上一篇:Java语言的接口与类型安全  
    下一篇:Java线程模型缺陷
    相关信息:

    ·初学Java的备忘录 ·浅析Java中Data类的应用
    ·Java数据库存取技术 ·Java线程模型缺陷
    ·Java语言的接口与类型安全 ·基于JNDI的应用程序开发
    ·掌握JDK1.5枚举类型 ·Java布局管理器使用方法
    ·JDK 1.5之Generics ·Java数据库编程中的技巧

    Copyright © 2002-2015 版权所有
    学校地址:北京市海淀区西三旗建材城中路29号北大青鸟
    招生热线:010-82011433/32 京公网安备110102004704  京ICP备05043413号 京公网安备110102004704