 |
|
|
 首页 |
名片设计 CorelDRAW Illustrator AuotoCAD Painter 其他软件 Photoshop Fireworks Flash |
|
链表是一种重要的数据结构，在程序设计中占有很重要的地位。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 "); System.in.println( " You can press return to quit " ); 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类的代码稍加改动即可。 返回类别: 教程 上一教程: 用JAVAMAIL显示复合邮件的内容(3) 下一教程: 在JSP中实现分页 您可以阅读与"JAVA语言中链表和双向链表的实现"相关的教程: · Java语言中链表和双向链表的实现 · 利用JAVA语言实现支持视频点播的WEB服务器 · Java语言中字符的处理 · JAVA运行时多态性的实现 · Javascript 中 浅拷贝与深拷贝的实现 |
  |
| 快精灵印艺坊 版权所有 |
首页 会员中心在线印刷在线编辑付款方式索取样品设计指南连锁门店
|
||
