EasyJF 官方网站全面升级,同时EasyJF开源团队也将进行全面改组,期待您给我们提出宝贵的意见及建议!

当前位置:首页-教程-原创教程

  • 数据结构系列教程(二)
    作者: 本站会员  来源:easyjf  发布时间:2007-10-14 19:14:00
  • 线性表的概念大家应该还记得,链式表是线性表的一个分类,当然也具备线性表的所有特性了,只不过它的结构方式特异而已,也就是和链子似的,和顺序表的不同之处在于链式表引入对象应用,就是其他语言中的指针,每个链子(我自己的说法)包含一个数据元素(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)&&jsize){
    
                      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)构造函数完成三件事:创建头节点,使headcurrent均表示所创建的头节点,置s ize0

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

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

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

     

    prior

    element

    next


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

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

  • 评论 】 【收藏】 【 推荐给朋友 】 【字体: 】 【关闭
评论:共0条

发表评论:
评论: 
    

相关栏目

  • 如何才能得到国外最新的技术

Copyright (C) 2005 EasyJF.com 简易java框架网 渝ICP备06004507号
如有意见请与我们联系