最近开始学习java的数据结构(确切地说,是用java实现的数据结构),首先,很大的感触是,和C实现链表的思想是相通的啊。数据结构本来就一样嘛。
闲话少扯,直奔主题!
先说链表吧,链表不同于以前我们学过的队列或数组,它是非线性的,即不是在内存中连续存储的。链表可以理解成由很多结点组成,很多人会把链表比喻为自行车 的链条,窃以为,这样比喻是欠妥的,因为链条是连续的(哈哈哈哈,这个牛角尖钻的),或许可以将其理解为你手机里存的亲友手机号码,我们可以通过这个号码 和那个人取得联系。我们一般将链表的一个结点分成两个部分:Data filed和Pointer field(这些是作者沿用C里的叫法),数据域用来存储数据,后面的指针域用来存放下一个结点的地址。
结点的定义如下:
public class Node {
// local declaration
private Object obj;
private Node next;
// getters and setters
public Object getObj() {
return obj;
}
public void setObj(Object obj) {
this.obj = obj;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
} // end class Node
这段代码很清晰的表明了结点的组成内容。
我的队列之链表实现版实现了以下几个功能:创建、增加、删除、插入、修改、打印、取指定位置的值以及取队列的大小。
先选取其中的几个阐述一下,希望大家指正!
1.删除:先上代码
// delete an item from list
public void del(int index){
// counters
int count = 0;
// delete item
if(index < 0 || index >= size()){
throw new RuntimeException("Out of index:" + index);
}else{
if(index == 0){
root = null;
}else{
Node node = root.getNext();
while(node != null){
count ++;
if(index == count){
node.setNext(node.getNext().getNext());
}
node = node.getNext();
} // end loop while
} // end if-else
} // end if-else
} // end method del
删除的实现的一个难点是如何确认到达指定的index位置进行下一步操作。这里是首先定义了一个计数器,用以判断是否到达指定位置,当 index==count时,就可以进行删除操作了,删除就是将index-1处得结点的next指向index+1处的结点,java的一个优点是,你 不用像C一样人为地用free()函数释放空间,JVM会自动回收。个人强烈建议,在学数据结构时,拿支笔在纸上画画,这样可以将抽象的东西具体化,有利 于理解。向链表中增加一个元素就是删除的逆过程了。此处不再赘述。
2.插入:代码如下
// insert an item to list (follow item NO.index)
public void insert(int index, Object obj){
// counters
int count = 0;
if(index < 0 || index >= size()){
throw new RuntimeException("Out of index: " + index);
}else{
// insert
if(index == 0){
root.setObj(obj);
}else{
// create a new node
Node insert = new Node();
insert.setObj(obj);
// insert it into the list
Node node = root.getNext();
while(node != null){
count ++;
if(index == count){
insert.setNext(node.getNext());
node.setNext(insert);
}
node = node.getNext();
} // end loop while
} // end if-else
} // end if-else
} // end method insert
这段代码其实和删除的很像,只是在判断之间先创建一个insert结点并setObj了,而且,有一个很值得注意的地方是:必须先insert.setNext(node.getNext());否则就会出错,大道理上是和程序时自上而下执行是有关的。相信你懂的。
这两段代码都得先比较index和size()进行比较,这是为了保持代码的健壮性。防止溢出。
写这个的时候,我就在想,我写的东西很大一种程度上是给未来的自己看的,可以用作复习,可以用来找回忆,所以,总希望以一种轻松和谐的姿态行文。
既然写了这么多,就继续扯点其他的吧,最近才发现,随着时间的推移,最初那种经常将C和Java搅在一起的局面已经一去不复返了,现在开始学着用Java 解决一些以前用C解决的问题,通过这个过程,开始更加了解C和Java,二者的相似点和不同的地方也已经有点眉目了。欣慰啊,最开始同时学习的时候,总是 有点担心,但是后来转念一想:C和Java都是计算机语言,没有必要将其完全分开,这才坚持了下来。过程虽然有点痛苦,但是结果还是有点满意。
现在这个阶段,发现自己的C和java还是属于大菜阶段,但是,我一直固执地以为,只要我坚持了,就没有办不到的事,至少过去20年的经验这样告诉我的。编程的天才都是训练出来的!我是一个不相信天才的人(尽管曾经有人这样叫过我 )。
最后,以我桌面上的一句话结束这次对话吧:The minute you think of giving up, think of the reason why you held on so long.
posted on 2011-05-26 11:53
墙头草 阅读(220)
评论(0) 编辑 收藏