随笔 - 115  文章 - 481  trackbacks - 0
<2006年8月>
303112345
6789101112
13141516171819
20212223242526
272829303112
3456789

常用链接

留言簿(19)

随笔档案(115)

文章档案(4)

新闻档案(1)

成员连接

搜索

  •  

最新评论

阅读排行榜

评论排行榜

线性表的概念大家应该还记得,链式表是线性表的一个分类,当然也具备线性表的所有特性了,只不过它的结构方式特异而已,也就是和链子似的,和顺序表的不同之处在于链式表引入对象应用,就是其他语言中的指针,每个链子(我自己的说法)包含一个数据元素 (element) 和一个指针域 (next) ,这个链子就称为节点,通俗的说有很多节点连接成的线性表就是链式表,根据其结构方式又可以分为单链表、单循环链表、双向链表,还有一种不常用的仿真链表,所有的链表都有一个共同的特征,都是由节点组成,根据前一章的思想我们很自然的会想到要构造一个节点类 Node.java

 

public class Node {

 /**

  * @author 张钰

  */

       Object element;// 数据元素

    Node next;

    Node(Node nextval){

            next=nextval;

    }

   Node(Object obj,Node nextval){

        element=obj;

        next=nextval;

   }

public Object getElement() {

       return element;

}

public void setElement(Object obj) {

       element = obj;

}

public Node getNext() {

       return next;

}

public void setNext(Node nextval) {

       next = nextval;

}

public String toString(){

       return element.toString();

}

   , 节点类的构造就是为了实现链表的操作,链表最常见的是单链表,单链表就是其每个节点都只有一个指向直接后继节点的指针,其中包括带头节点的和不带头节点的,根据单链表的结构我们可以设计如下的类 LinList.java (注意和 java 中的 LinkList 不一样, LinkList 是个线性结构容器,提供线性表、堆栈、队列等操作):

/**

 * @author 张钰

 *

 */

public class LinList implements List {

 

       Node head;// 头指针

       Node current;// 当前节点位置

       int size;// 数据元素个数

       LinList(){

              head=current=new Node(null);

           size=0;

       }

       public void index(int i) throws Exception{ // 定位元素

              if(i<-1||i>size-1){

                     throw new Exception(" 参数错误 ");

              }

              if(i==-1) return;

              current=head.next;

              int j=0;

              while((current!=null)&&j<i){

                     current=current.next;

                     j++;

              }

       }

       public void insert(int i, Object obj) throws Exception {

              // 插入

           if(i<0||i>size){

                  throw new Exception(" 参数错误 ");

           }

           index(i-1);

           current.setNext(new Node(obj,current.next));

           size++;

       }

 

 

       public Object delete(int i) throws Exception {

              // 删除

              if (size==0){

                     throw new Exception(" 链表已空无元素可删除! ");

              }

              if(i<0||i>size-1){

                     throw new Exception(" 参数错误 ");

              }

              index(i-1);

              Object obj=current.next.getElement();

              current.setNext(current.next.next);

              size--;

              return obj;

       }

 

      

       public Object getData(int i) throws Exception {

              // 获取元素

              if(i<-1||i>size-1){

                     throw new Exception(" 参数错误 ");

              }

              index(i);

              return current.getElement();

       }

 

      

       public int size() {

              // 获取元素个数

              return size;

       }

 

       /* (非 Javadoc

        * @see List#isEmpty()

        */

       public boolean isEmpty() {

              // 判断是否为空

              return size==0;

       }

 

}

,设计说明:

(1) 构造函数完成三件事:创建头节点,使 head current 均表示所创建的头节点,置 s ize 0

(2) 定位成员函数 index(int i) 的实现,其设计方式是:用一个循环过程从头开始计数寻找第 i 个节点;

顺序表和单链表的比较:顺序表和单链表的逻辑功能完全一样,但是两者的应用背景以及不同情况下的使用效率略有不同,顺序表的主要优点就是支持随机读取,以及内存空间利用效率高,顺序表的主要特点就是需要给出数组的最大数据元素个数,而这通常很难准确做到,另外,顺序表的插入和删除操作时需要移动较多的数据元素,单链表的缺点就是每个节点中都有个指针,所以其空间利用率略低于顺序表,单链表不支持随机读取。

单链表另一种常见的形势就是循环单链表,其结构特点就是链表中最后一个节点的指针不再是结束标记,而是指向整个链表的第一个节点,从而使单链表形成一个环,,就是在构造函数中增加 head.next=head ,在定位函数 index(i) 中,把循环结束条件 current!=null 换成 current!=head ,这样最后一个节点就循环到第一个了!链表最常见的一个应用就是循环双链表, java 中的 LinkedList 就是通过循环双链表来实现的,其长度可以随着数据元素的增减很容易的变化, LinkedList 提供了线性表、堆栈、队列、双端队列等数据结构所要求的全部成员函数,例如 addFirst() removeFirst() 就是支持堆栈所要求的成员函数,这里就不过多讲解了,回到循环双链表,双向链表中每个节点包括三个域: element next prior ,其中 element 是数据元素, next 是指向后继节点的对象应用, prior 是指向前驱节点的对象应用,

 

prior

element

next


p 为第 i 个节点,则 p.next 为第 i+1 个节点, p.next.prior==p, 这就是双向链表的方式,结合前面的内容,双向链表类的设计留给大家,有兴趣的同学可以和我一起讨论!

最后还有仿真链表,链式储存结构中,实现元素之间的关系靠的是指针,但是也可以用数组来构造仿真链表,方法是在数祖中增加一个(或两个) int 类型的变量域,这些变量用来表示后一个或前一个元素在数组中的下标,这就是仿真链表,其应用不是很多,这里就不多介绍,有兴趣的同学可以研究,下一讲:堆栈和队列!

(注:本文作者,EasyJF开源团队 天意,转载请保留作者声明!)

posted on 2006-08-18 09:04 简易java框架 阅读(1174) 评论(0)  编辑  收藏

只有注册用户登录后才能发表评论。


网站导航: