study
package com.java.duncan;
class Node {
public int value;
public Node next;
public Node() {
value = -1;
next = null;
}
public Node(int i) {
value = i;
next = null;
}
public void add(Node head, Node add) {
Node p = head;
if(p == null) return;
while(p.next != null) {
p = p.next;
}
p.next = add;
}
public void print(Node head) {
Node p = head;
if(p == null) System.out.println("链表为空!");
while(p != null) {
System.out.print(p.value + " ");
p = p.next;
}
}
public void reversePrint(Node node) {
if(node.next != null) {
reversePrint(node.next);
System.out.print(node.value + " ");
}
}
public Node Reverse(Node head) {
if(head==null || head.next==null) return head;
Node p1 = head;
Node p2 = head.next;
Node p3 = p2.next;
p1.next = null;
while(p3 != null) {
p2.next = p1;
p1 = p2;
p2 = p3;
p3 = p3.next;
}
p2.next = p1;
return p2;
}
}
public class ReverseList {
public static void main(String[] args) {
Node head = new Node();
for(int i = 1; i <= 10; i++) {
head.add(head,new Node(i));
}
head.print(head.Reverse(head));
//System.out.println();
//head.reversePrint(head);
}
}
链表是一种重要的数据结构,在程序设计中占有很重要的地位。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类的代码稍加改动即可。
分享到:
相关推荐
The ultimate PMP preparation and self-study experience, updated to align with the new PMBOK® Guide, 6th Edition The PMP: Project Management Professional Exam Study Guide, Ninth Edition, provides ...
AWS has been the frontrunner in cloud computing products and services, and the AWS Certified Solutions Architect Official Study Guide for the Associate exam will get you fully prepared through expert...
Learn More Study Less中文版,提高个人学习效率
our study sheds light on why Google introduced this practice and analyzes its current status, after the process has been refined through decades of code changes and millions of code reviews....
学习研究CNKI E-Study (数字化学习与研究平台) 学者成果库学者圈科研项目 学术趋势搜索互联网学术资源 学术研究热点科研助手,融合中国知网等独家有效资源,开启高校专属资源免费不限量使用。全国高职高专院校招生...
《The Study of Language》的是一本为初学者编写的入门教材,总共有二十一章,每一章很短小,但几乎涉及了语言学研究的所有领域,包括一些最前沿的研究进展。
temp_study.rartemp_study.rartemp_study.rartemp_study.rartemp_study.rar
Coverage of 100% of all exam objectives in this Study Guide means you’ll be ready for: Comparing and contrasting the use of networking services and applications Installing and configuring network ...
TOGAF 9 Certified study guide.pdf
ITK图像读写详解,Study ITK Together 一起学习ITK
A Study of Android Application Security 学术论文
learn more study less 英文原版书籍 尝试改变已有学习方式
Linux Study.rar
DBUnit_Project_Study.rar DBUnit_Project_Study.rar DBUnit_Project_Study.rar DBUnit_Project_Study.rar
AWS has been the frontrunner in cloud computing products and services, and the AWS Certified Solutions Architect Official Study Guide for the Associate exam will get you fully prepared through expert...
Sun Certified Enterprise Architect for J2EE Study Guide
CFD Vision 2030 Study_A Path to Revolutionary Computational Aerosciences; 经典论述CFD发展报告。
本下载文件是一个绿色软件,解压后直接双击本目录下的 Media_Study_Player.exe 即可执行。可以利用U盘的便利性在学校或同学的电脑上使用。完全绿化的另一个好处是,即使在没有系统管理员权限的情形下也可以使用(如...
Study EJB_Note