JAVA编程：数据布局DD栈、行列和树(Java)
由于这些智能化家电的市场需求没有预期的高，Sun放弃了该项计划。就在Oak几近失败之时，随着互联网的发展，Sun看到了Oak在计算机网络上的广阔应用前景，于是改造了Oak，数据|数据布局数据布局DD栈、行列和树开辟者可使用数组与链表的变体来创建更加庞大的数据布局。本节探求三种如许的数据布局:栈、行列与树。当给出算法时，出于简洁，间接用Java代码。
栈
栈是如许一个数据布局，其数据项的拔出和删除（猎取）都只能在称为栈顶的一端完成。由于最初拔出的数据项就是开始要删除的数据项，开辟者常常将栈称为LILO（last-in,first-out）数据布局。
数据项压进（拔出）大概弹出（删除或获得）栈顶。3示例了一个有三个String数据项的栈，每一个数据项压进栈顶。
3有三个以压进String数据项的栈
如3所示，栈在内存中是向下建起来的。关于每一个数据项的压进，之前栈顶的数据项和其上面的一切数据项都得向下移，当要从栈中弹出一个数据项时，获得栈顶元素并将其从栈中删除。
栈在很多程序计划情况下十分有效。两个十分一般的情况：
・栈保留前往地点：今世码挪用一个办法时，挪用指令后的第一条指令的地点压进以后线程的办法挪用栈的顶端。当实行被挪用办法的前往指令时，该地点从栈顶弹出，然后从该地点处持续实行。假如一个办法挪用了另外一个办法，栈的LIFO举动形式确保了第二个办法的前往指令将实行转移到第一个办法，而第一个办法的前往指令可以将实行转移到挪用第一个办法的代码的代码。了局就是，栈代表被挪用办法“记着了”前往地点。
・栈保留每一个被挪用办法的参数和部分变量：当挪用一个办法时，JVM在接近前往地点处罚配内存存储一切被挪用办法的参数和部分变量。假如办法是个实例办法，存储在栈中的个中一个参数是以后对象的援用this。
一样平常可使用一维数组或单链表完成一个栈。假如利用一维数组，一个常定名为top的整型变量保留栈顶数据项的索引。相似地，一个常定名为top的援用变量援用单链心情形下的栈顶节点（含有栈顶数据项）。
依据JavasCollectionsAPI中发明的系统布局建模栈的完成。这个完成由一个Stack接口，ArrayStack和LinkedListStack完成类和FullStackException撑持类构成。为了便于公布，将这些类打包在com.javajeff.cds包中，个中的cds暗示庞大数据布局。清单8给出了Stack接口。
清单8.Stack.java
//Stack.java
packagecom.javajeff.cds;
publicinterfaceStack
{
booleanisEmpty();
Objectpeek();
voidpush(Objecto);
Objectpop();
}
Stack的四个办法分离是断定栈是不是为空，取得栈顶数据项而没有删除，恣意数据项进栈，取得并删除栈顶元素。除一个详细于完成的机关办法以外，你的程序只需挪用这些办法就充足了。
清单9给出了Stack的基于一维数组的完成：
清单9ArrayStack.java
//ArrayStack.java
packagecom.javajeff.cds;
publicclassArrayStackimplementsStack
{
privateinttop=-1;
privateObject[]stack;
publicArrayStack(intmaxElements)
{
stack=newObject;
}
publicbooleanimEmpty()
{
returntop==-1;
}
publicObjectpeek()
{
if(top<0)
thrownewjava.util.EmptyStackException();
returnstack;
}
publicvoidpush(Objecto)
{
if(top==stack.length-1)
thrownewFullStackException();
stack[++top]==0;
}
publicObjectpop()
{
if(top<0)
thrownewjava.util.EmptyStackException();
returnstack;
}
}
ArrayStack标明，栈由公有整型索引top和一维数组的援用变量stack构成。top标识stack中的栈顶数据项，初始化为－1以暗示栈为空。当要创立一个ArrayStack对象时利用一个申明元素最年夜数量的整型值来挪用publicArrayStack(intmaxElements)。试图从一个空栈的栈顶弹出一个数据项会使得pop()函数里抛出一个java.util.EmptyStackException非常对象。与之类似，假如试图在栈中压进多于maxElements的数据项会使得push(Objecto)函数抛出FullStackException对象，其代码见清单10:
清单10FullStackException.java
packagecom.javajeff.cds;
publicclassFullStackExceptionextendsRuntimeException
{
}
为了与EmptyStackException绝对称，FullStackException扩大了RuntimeException。如许，你就不用在一个办法的throws从句里加上FullStackException。
清单11给出了Stack的基于单链表的完成：
清单11.LinkedListStack.java
//LinkedListStack.java
packagecom.javajeff.cds;
publicclassLinkedListStackimplementsStack
{
privatestaticclassNode
{
Objecto;
Nodenext;
}
privateNodetop=null;
publicbooleanimEmpty()
{
returntop==null;
}
publicObjectpeek()
{
if(top==null)
thrownewjava.util.EmptyStackException();
returntop.o;
}
publicvoidpush(Objecto)
{
Nodetemp=newNode();
temp.o=o;
temp.next=top;
top=temp;
}
publicObjectpop()
{
if(top==null)
thrownewjava.util.EmptyStackException();
Objecto=top.o;
top=top.next;
returno;
}
}
LinkedListStack标明栈由一个公有的顶层嵌套类Node和一个公有援用变量top组成，援用变量top初始化为null暗示一个空栈。相对一维数组完成的栈，LinkedListStack其实不必要一个机关器，由于它可以跟着数据项的压进静态扩大。如许，voidpush(Objecto)就不必要抛出FullStackException对象。但是，Objectpop()仍是必要反省栈是不是为空的，这大概会招致可抛的EmptyStackException对象。
由于我们已看到了组成栈这一数据布局完成的接口和三个类，我们就来示例一下栈的利用。
清单12.StackDemo.java
//StackDemo.java
importcom.javajeff.cds.*;
classStackDemo
{
publicstaticvoidmain(String[]args)
{
System.out.println("ArrayStackDemo");
System.out.println("---------------");
stackDemo(newArrayStack(5));
System.out.println("LinkedListStackDemo");
System.out.println("---------------------");
stackDemo(newLinkedListStack());
}
statcivoidstackDemo(Stacks)
{
System.out.println("Pushing"Hello"");
s.push("Hello");
System.out.println("Pushing"World"");
s.push("World");
System.out.println("PushingStackDemoObject");
s.push(newStackDemo());
System.out.println("PushingCharacterobject");
s.push(newCharacter("A"));
try
{
System.out.println("Pushing"Onelastitem"");
s.push("Onelastitem");
}catch(FullStackExceptione)
{
System.out.println("Onepushtoomany");
}
System.out.println();
while(!s.imEmpty())
System.out.println(s.pop());
try
{
s.pop();
}
catch(java.util.EmptyStackExceptione)
{
System.out.println();
}
System.out.println();
}
}
当运转StackDemo时发生以下输入：
ArrayStackDemo
---------------
Pushing"Hello"
Pushing"World"
PushingStackDemoobject
PushingCharacterobject
PushingThreadobject
Pushing"Onelastitem"
Onepushtoomany
Thread
C
StackDemo@7182c1
World
Hello
Onepoptoomany
LinkedListStackDemo
--------------------
Pushing"Hello"
Pushing"World"
PushingStackDemoobject
PushingCharacterobject
PushingThreadobject
Pushing"Onelastitem"
Onelastitem
Thread
C
StackDemo@cac268
World
Hello
Onepoptoomany
行列
行列是如许一种数据布局，数据项的拔出在一端（行列尾），而数据项的获得或删除则在另外一端（行列头）。由于第一个拔出的数据项也是第一个获得或删除的数据项，开辟者广泛地将行列称为FIFO数据布局。
开辟者常常利用到两种行列：线性行列和轮回行列。在两种行列中，数据项都是在行列尾拔出，然后移向行列头，并从行列头删除或猎取。4申明了线性和轮回行列。
4有四个已拔出整型数据项的线性行列和七个数据项的轮回行列
4的线性行列存储四个数据项，整数1是第一个。行列已满，不克不及存储别的的整型数据项，由于rear已指到了最左面（最初）的狭槽。front指向的狭槽为空，由于它触及到线性行列的举动。起先，front和rear都指向最右边的狭槽，暗示行列为空。为了存储整数1,rear指向右侧的下一个狭槽，并将1存储到谁人狭槽中。而当猎取或删除整数1时，front向右行进一个狭槽。
4的轮回行列存储有七个整型数据项，以整数1入手下手。该行列为满而且不克不及存储其余整型数据，直至front沿顺时针偏向行进一个狭槽。与线性行列类似，front指向的狭槽为空也是触及到轮回行列的举动。最后，front和rear指向统一个狭槽，暗示行列为空。关于每一个数据项拔出，rear行进一个狭槽，关于每一个数据项的删除，front行进一个狭槽。
行列在良多程序计划情况下十分有效。两个罕见的情形有：
・线程调剂：JVM或一个基础的操纵体系会创建多个行列来反响分歧的线程优先级。线程信息会堵塞，由于给定优先级的一切线程存储在相干行列中。
・打印义务：由于打印机的速率比盘算机慢很多，操纵体系将其打印义务分拨给其打印子体系，打印子体系就会将这些义务拔出到一个打印行列中。行列中的第一个义务先打印，最初一个义务最初打印。
开辟者常常利用一维数组完成一个行列。但是，假如必要同时存在多个行列的话，大概由于优先级的缘故原由行列必要在行列尾之外的中央拔出，开辟者大概会选择双链表来完成。在此，我们利用由于数组来完成线性和轮回行列。让我们从清单13的Queue接口入手下手：
//Queue.java
packagecom.javajeff.cds;
publicinterfaceQueue
{
voidinsert(Objecto);
booleanisEmpty();
booleanisFull();
Objectremove();
}
Queue声了然四个办法，分离用于在行列中存储数据项，断定行列是不是为空，断定行列是不是为满，由行列猎取或删除数据项。
清单14给出了基于一维数组的线性行列的完成：
清单14.ArrayLinearQueue.java
//ArrayLinearQueue.java
packagecom.javajeff.cds;
publicclassArrayLinearQueueimplementsQueue
{
privateintfront=-1,rear=-1;
privateObject[]queue;
publicArrayLinearQueue(intmaxElements)
{
queue=newObject;
}
publicvoidinsert(Objecto)
{
if(rear==queue.length-1)
thrownewFullQueueException();
queue[++rear]=o;
}
publicbooleanisEmpty()
{
returnfront==rear;
}
publicbooleanisFull()
{
returnrear==queue.length-1;
}
publicObjectremove()
{
if(front==rear)
thrownewEmptyQueueException();
returnqueue[++front];
}
}
ArrayLinearQueue标明行列由front，rear和queue变量构成。个中front和rear初始化为－1暗示行列为空。与ArrayStack的机关器一样，利用一个申明元素最年夜数量的整型值挪用publicArrayLinearQueue(intmaxElements)以创立一个ArrayLinearQueue对象。
当rear申明的是数组的最初一个元素时，ArrayLinearQueuesinsert(Objecto)办法会抛出FullQueueException非常对象。FullQueueException的代码如清单15所示：
清单15.FullQueueException.java
//FullQueueException.java
packagecom.javajeff.cds;
publicclassFullQueueExceptionextendsRuntimeException
{
}
当front即是rear时，ArrayLinearQueuesremove()办法会抛出EmptyQueueException对象。EmptyQueueException的代码以下：
清单16.EmptyQueueException.java
//EmptyQueueException.java
packagecom.javajeff.cds;
publicclassEmptyQueueExceptionextendsRuntimeException
{
}
清单17给出了基于一维数组的轮回行列的完成：
Listing17.ArrayCircularQueue.java
//ArrayCircularQueue.java
packagecom.javajeff.cds;
publicclassArrayCircularQueueimplementsQueue
{
privateintfront=0,rear=0;
privateObject[]queue;
publicArrayCircularQueue(intmaxElements)
{
queue=newObject;
}
publicvoidinsert(Objecto)
{
inttemp=rear;
rear=(reart+1)%queue.length;
if(front==rear)
{
rear=temp;
thrownewFullQueueException();
}
queue=o;
}
publicbooleanisEmpty()
{
returnfront==rear;
}
publicbooleanisFull()
{
return((rear+1)%queue.length)==front;
}
publicObjectremove()
{
if(front==rear)
thrownewEmptyQueueException();
front=(front+1)%queue.length;
returnqueue;
}
}
从公有域变量和机关器来看，ArrayCircularQueue标明了一个与ArrayLinearQueue相似的完成。insert(Objecto)办法使人注重的中央是它在使得rear指向下一个狭槽之前先保留了以后的值。如许，假如轮回行列已满，那末rear在FullQueueException非常对象抛出之前恢复为原值。Rear值的复原是需要的，不然front即是rear，后续挪用remove()会招致EmptyQueueException非常（即便轮回行列不为空）。
在研讨了构成行列这一数据布局的基于一维数组的完成的接口和各类类以后，思索清单18,这是一个申明线性和轮回行列的使用程序。
清单18.QueueDemo.java
//QueueDemo.java
importcom.javajeff.cds.*;
classQueueDemo
{
publicstaticvoidmain(String[]args)
{
System.out.println("ArrayLinearQueueDemo");
System.out.println("---------------------");
queueDemo(newArrayLinearQueue(5));
System.out.println("ArrayCircularQueueDemo");
System.out.println("---------------------");
queueDemo(newArrayCircularQueue(6));//Needonemoreslotbecause
//ofemptyslotincircular
//implementation
}
staticvoidqueueDemo(Queueq)
{
System.out.println("Isempty="+q.isEmpty());
System.out.println("Isfull="+q.isFull());
System.out.println("Inserting"This"");
q.insert("This");
System.out.println("Inserting"is"");
q.insert("is");
System.out.println("Inserting"a"");
q.insert("a");
System.out.println("Inserting"sentence"");
q.insert("sentence");
System.out.println("Inserting"."");
q.insert(".");
try
{
System.out.println("Inserting"Onelastitem"");
q.insert("Onelastitem");
}
catch(FullQueueExceptione)
{
System.out.println("Oneinserttoomany");
System.out.println("Isempty="+q.isEmpty());
System.out.println("Isfull="+q.isFull());
}
System.out.println();
while(!q.isEmpty())
System.out.println(q.remove()+"[Isempty="+q.isEmpty()+
",Isfull="+q.isFull()+"]");
try
{
q.remove();
}
catch(EmptyQueueExceptione)
{
System.out.println("Oneremovetoomany");
}
System.out.println();
}
}
运转QueueDemo失掉以下输入:
ArrayLinearQueueDemo
---------------------
Isempty=true
Isfull=false
Inserting"This"
Inserting"is"
Inserting"a"
Inserting"sentence"
Inserting"."
Inserting"Onelastitem"
Oneinserttoomany
Isempty=false
Isfull=true
This
is
a
sentence
.
Oneremovetoomany
ArrayCircularQueueDemo
---------------------
Isempty=true
Isfull=false
Inserting"This"
Inserting"is"
Inserting"a"
Inserting"sentence"
Inserting"."
Inserting"Onelastitem"
Oneinserttoomany
Isempty=false
Isfull=true
This
is
a
sentence
.
Oneremovetoomany
树
树是有穷节点的组，个中有一个节点作为根，根上面的其他节点以条理化体例构造。援用其下节点的节点是父节点，相似，由下层节点援用的节点是孩子节点。没有孩子的节点是叶子节点。一个节点大概同时是父节点和子节点。
一个父节点能够援用所需的多个孩子节点。在良多情形下，父节点最多只能援用两个孩子节点，基于这类节点的树称为二叉树。3给出了一棵以字母表按次存储了七个String单词的二叉树。
5一颗有七个节点的二叉树
在二叉树或其他范例的树中都是利用递返来拔出，删除和遍历节点的。出于冗长的目标，我们其实不深切研讨递回的节点拔出，节点删除和树的遍历算法。我们改成用清单19中的一个单词计数程序的源代码来讲明递回节点拔出和树的遍历。代码中利用节点拔出来创立一棵二叉树，个中每一个节点包含一个单词和词呈现的计数，然后藉由树的中序遍历算法以字母表按次显现单词及其计数。
Listing19.WC.java
//WC.java
importjava.io.*;
classTreeNode
{
Stringword;//Wordbeingstored.
intcount=1;//Countofwordsseenintext.
TreeNodeleft;//Leftsubtreereference.
TreeNoderight;//Rightsubtreereference.
publicTreeNode(Stringword)
{
this.word=word;
left=right=null;
}
publicvoidinsert(Stringword)
{
intstatus=this.word.compareTo(word);
if(status>0)//wordargumentprecedescurrentword
{
//Ifleft-mostleafnodereached,theninsertnewnodeas
//itsleft-mostleafnode.Otherwise,keepsearchingleft.
if(left==null)
left=newTreeNode(word);
else
left.insert(word);
}
else
if(status<0)//wordargumentfollowscurrentword
{
//Ifright-mostleafnodereached,theninsertnewnodeas
//itsright-mostleafnode.Otherwise,keepsearchingright.
if(right==null)
right=newTreeNode(word);
else
right.insert(word);
}
else
this.count++;
}
}
classWC
{
publicstaticvoidmain(String[]args)throwsIOException
{
intch;
TreeNoderoot=null;
//Readeachcharacterfromstandardinputuntilaletter
//isread.Thisletterindicatesthestartofaword.
while((ch=System.in.read())!=-1)
{
//Ifcharacterisaletterthenstartofworddetected.
if(Character.isLetter((char)ch))
{
//CreateStringBufferobjecttoholdwordletters.
StringBuffersb=newStringBuffer();
//PlacefirstlettercharacterintoStringBufferobject.
sb.append((char)ch);
//PlaceallsubsequentlettercharactersintoStringBuffer
//object.
do
{
ch=System.in.read();
if(Character.isLetter((char)ch))
sb.append((char)ch);
else
break;
}
while(true);
//Insertwordintotree.
if(root==null)
root=newTreeNode(sb.toString());
else
root.insert(sb.toString());
}
}
display(root);
}
staticvoiddisplay(TreeNoderoot)
{
//Ifeithertherootnodeorthecurrentnodeisnull,
//signifyingthataleafnodehasbeenreached,return.
if(root==null)
return;
//Displayallleft-mostnodes(i.e.,nodeswhosewords
//precedewordsinthecurrentnode).
display(root.left);
//Displaycurrentnodeswordandcount.
System.out.println("Word="+root.word+",Count="+
root.count);
//Displayallright-mostnodes(i.e.,nodeswhosewords
//followwordsinthecurrentnode).
display(root.right);
}
}
由于已有良多正文了，在这儿我们就不会商代码了。代之，倡议你以下运转这个使用程序：要计数文件中的单词数，翻开一个包含重定位符<的命令行。比方，收回javaWC<WC.java命令来计数文件WC.java中的单词数。谁人命令的输入以下：
Word=Character,Count=2
Word=Count,Count=2
Word=Create,Count=1
Word=Display,Count=3
Word=IOException,Count=1
Word=If,Count=4
Word=Insert,Count=1
Word=Left,Count=1
Word=Otherwise,Count=2
Word=Place,Count=2
Word=Read,Count=1
Word=Right,Count=1
Word=String,Count=4
Word=StringBuffer,Count=5
通过视频学习比传统的大课堂学习更适合成人化的学习规律。有人说大课堂气氛好，学习氛围浓，热闹，可以认识很多人。 你快去找一份Java的编程工作来做吧（如果是在校学生可以去做兼职啊），在实践中提高自己，那才是最快的。不过你得祈祷在公司里碰到一个高手，而且他 还愿意不厌其烦地教你，这样好象有点难哦！还有一个办法就是读开放源码的程序了。我们知道开放源码大都出自高手，他们设计合理，考虑周到，再加上有广大的程序员参与，代码的价值自然是字字珠叽，铿锵有力（对不起，偶最近《金装四大才子》看多了）。 关于设计模式的资料，还是向大家推荐banq的网站 http://www.ckuyun.com/，他把GOF的23种模式以通俗易懂的方式诠释出来，纯Java描述，真是经典中的经典。 你快去找一份Java的编程工作来做吧（如果是在校学生可以去做兼职啊），在实践中提高自己，那才是最快的。不过你得祈祷在公司里碰到一个高手，而且他 还愿意不厌其烦地教你，这样好象有点难哦！还有一个办法就是读开放源码的程序了。我们知道开放源码大都出自高手，他们设计合理，考虑周到，再加上有广大的程序员参与，代码的价值自然是字字珠叽，铿锵有力（对不起，偶最近《金装四大才子》看多了）。 是一种突破用户端机器环境和CPU 其实说这种话的人就如当年小日本号称“三个月拿下中国”一样大言不惭。不是Tomjava泼你冷水，你现在只是学到了Java的骨架，却还没有学到Java的精髓。接下来你得研究设计模式了。 你就该学一学Servlet了。Servlet就是服务器端小程序，他负责生成发送给客户端的HTML文件。JSP在执行时，也是先转换成Servlet再运行的。虽说JSP理论上可以完全取代Servlet，这也是SUN推出JSP的本意，可是Servlet用来控制流程跳转还是挺方便的，也令程序更清晰。接下来你应该学习一下Javabean了，可能你早就看不管JSP在HTML中嵌Java代码的混乱方式了，这种方式跟ASP又有什么区别呢？ 当然你也可以参加一些开源项目，一方面可以提高自己，另一方面也是为中国软件事业做贡献嘛！开发者在互联网上用CVS合作开发，用QQ,MSN,E-mail讨论联系，天南海北的程序员分散在各地却同时开发同一个软件，是不是很有意思呢？ 一直感觉JAVA很大，很杂，找不到学习方向，前两天在网上找到了这篇文章，感觉不错，给没有方向的我指了一个方向，先不管对不对，做下来再说。 Java自面世后就非常流行，发展迅速，对C++语言形成了有力冲击。Java 技术具有卓越的通用性、高效性、平台移植性和安全性，广泛应用于个人PC、数据中心、游戏控制台 学Java必读的两个开源程序就是Jive和Pet Store.。 Jive是国外一个非常著名的BBS程序，完全开放源码。论坛的设计采用了很多先进的技术，如Cache、用户认证、Filter、XML等，而且论坛完全屏蔽了对数据库的访问，可以很轻易的在不同数据库中移植。论坛还有方便的安装和管理程序，这是我们平时编程时容易忽略的一部份（中国程序员一般只注重编程的技术含量，却完全不考虑用户的感受，这就是我们与国外软件的差距所在）。 让你能够真正掌握接口或抽象类的应用，从而在原来的Java语言基础上跃进一步，更重要的是，设计模式反复向你强调一个宗旨：要让你的程序尽可能的可重用。 另外编写和运行Java程序需要JDK(包括JRE)，在sun的官方网站上有下载，thinking in java第三版用的JDK版本是1.4,现在流行的版本1.5（sun称作J2SE 5.0，汗），不过听说Bruce的TIJ第四版国外已经出来了，是专门为J2SE 5.0而写的。 Sun公司看见Oak在互联网上应用的前景，于是改造了Oak，于1995年5月以Java的名称正式发布。Java伴随着互联网的迅猛发展而发展，逐渐成为重要的网络编程语言。 是一种为 Internet发展的计算机语言 是一种使用者不需花费很多时间学习的语言 Java是一个纯的面向对象的程序设计语言，它继承了 C++语言面向对象技术的核心。Java舍弃了C ++语言中容易引起错误的指针（以引用取代）、运算符重载（operator overloading） http://www.jdon.com/去下载，或到同济技术论坛的服务器ftp://nro.shtdu.edu.cn去下，安装上有什么问题，可以到论坛上去提问。 是一种将安全性(Security)列为第一优先考虑的语言
页:
[1]