随笔 - 115  文章 - 481  trackbacks - 0
<2006年8月>
303112345
6789101112
13141516171819
20212223242526
272829303112
3456789

常用链接

留言簿(19)

随笔档案(115)

文章档案(4)

新闻档案(1)

成员连接

搜索

  •  

最新评论

阅读排行榜

评论排行榜

  接触不少程序员,都能够独立的作一下小型应用系统,和他们交谈起来才发现,他们纯粹是程序员,对基础的掌握太差,比喻 java 程序员,就是对 jdk 和各种框架特别的熟悉,能够熟练的运用其中的各种包、类以及一些组件,确实能做出一下系统来,但是涉及到一些特殊的设计方法来就不行了,对基础掌握太差,包括现在的很多培训,都是灌输这些所谓的实际应用的东西,学好基础才是最关键的东西,学一门语言很快,没有很好的基础、清晰的思路只能照葫芦画瓢了,为此,笔者结合自己的学习经验写了系列教程,主要包括数据结构的全部内容:线性表、树、图、数组、集合、矩阵、排序、查找、哈希表,并将 java 的设计思想、方法及一些常见的算法、设计模式贯穿其中,希望能给初学者一个很好的帮助,由于本人水平有限,同时请大家给与批评指正!

第一讲   线性表

   数据结构包括数据的逻辑结构、储存结构以及对数据的操作,线性表的含义就是:除了第一个和最后一个数据元素,其他的只有一个前驱元素和一个后继元素,如下图:

   A--->B--->C--->D

这个就是一个最简单的线性表的实例,结合定义可以很好的理解的,数据结构中最常见的就是提到抽象数据类型,所谓抽象数据类型就是在基本数据类型支持下用户新设计的数据类型,通俗的说就是用户对基本数据类型(整型、浮点型等等)的组合应用成自己的一种新型的数据类型,也就是 java 中接口和抽象类,这么说可能有些不妥,不过这样最好理解,前面讲到数据结构包括对数据的操作,这个设计数据结构的最终目的,下面我们就讲讲 java 数据结构中的线性表的设计思想。

由于线性表的数据集合可以表示为序列: A1,A2,A3……….An-1, 每个元素的类型都是任意的,对于这个集合的操作可以归结如下:

(1) 求出当前集合中数据元素个数( size ;

(2) 向当前数据集合任意位置插入新的数据 (insert);

(3) 删除当前数据集合中的任意数据 (delete);

(4) 获取当前数据集合中的任意数据 (getData);

(5) 判断当前数据集合是否为空 ;

,由于存在很多不同形式的线性表结构,对其操作方式当然也不一样,这样就要求设计一个大家都能使用的数据类型,由前面的讲述大家就可以想到必须要设计一个抽象数据类型,也就是一个接口,这时可能有人问为什么不设计一个抽象类阿?这个问题留个大家思考,可以到论坛发表。 Java 中可以这样定义这个接口:

 

public interface List {

 /**

  * @author 天意

  */

       public void insert(int i,Object obj ) throws Exception;// 在任意位置插入数据

       public Object delete(int i) throws Exception;// 删除任意位置的数据

       public Object getData(int i) throws Exception;// 获取任意位置的数据

       public int size();// 获取当前集合的大小

       public boolean isEmpty();// 判断当前集合是否为空

}

,由于所有线性表的操作都是围绕以上而来的,所以上面的接口就可以通用于所有线性表了,这就告诉大家在设计程序时要做好充分的考虑,强调一个“广”字。

线性表包括顺序表和链式表,首先讲一下顺序表,顺序表顾名思义,就是数据元素按一定组合在一起的,逻辑上相邻的元素在物理储存上也是相邻的,如下如示例:

A0

A1

A2

A3

A4

A5

……

 

0       1          2         3        4         5                 maxSize-1

结合这个图我们可以想到:首先建立这个表就必须有个初始大小,然后才能对他就行实际操作,插入操作时可能会出现表已满、插入位置不存在的情况,删除时可能出现表已空、删除的元素不存在的情况,获取时可能出现要求的元素不存在的情况,考虑这些因素就可以设计这个顺序表的操作类了 SeqList.java ,具体内容如下:

 

public class SeqList implements List {

 

       /**

        * @author 天意

        */

       final int defaultSize=10;// 默认为 10 个,你可以自己随便改

       int maxsize;

       int size;

       Object[] listArray;

       public SeqList(){

              initiate(defaultSize);

       }

       public SeqList(int size){

              initiate(size);

       }

       private void initiate(int sz) {

              // 初始化

              maxsize=sz;

              size=0;

              listArray=new Object[sz];

       }

       public void insert(int i, Object obj) throws Exception {

              // i 位置插入 obj 对象

     if(size==maxsize){

            throw new Exception(" 顺序表无法插入 ");

     }

     if (i<0||i>size){

            throw new Exception(" 参数错误 ");

     }

     for(int j=size;j>i;j--)

            listArray[j]=listArray[j-1];

         listArray[i]=obj;

         size++;

       }

 

       public Object delete(int i) throws Exception {

              // 删除 i 位置的元素

              if (size==0){

                     throw new Exception(" 顺序表已空无法删除! ");

              }

              if(i<0||i>size-1){

                     throw new Exception(" 参数错误! ");

              }

              Object it=listArray[i];

              for(int j=i;j<size-1;j++)

                     listArray[j]=listArray[j+1];

              size--;

              return it;

       }

 

       public Object getData(int i) throws Exception {

              // 获取 i 位置的元素并返回

              if(i<0||i>=size){

                     throw new Exception(" 参数错误! ");

              }

              return listArray[i];

              }

 

       public int size() {

              // 获得大小

              return size;

       }

 

       public boolean isEmpty() {

              // 判断是否为空

              return size==0;

       }

       public int MoreDataDelete(SeqList L,Object x)throws Exception{

              int i;

              int tag=0;

              for( i=0;i<L.size;i++){

                     if(x.equals(L.getData(i))){

                            L.delete(i);

                            i--;

                            tag=1;

                     }

                    

              }

              return tag;

       }

 

}

,以上就可以实现顺序表的所有操作了,你可以自己试一下,这里要说明的是,因为顺序表中储存的对象类型可以任意,所以设计时一定要使用 Object 类,当然有时为了限定具体类型你可以重写这个类然后抛出相应的异常即可,这个顺序表的效率分析工作留给大家,大家可以到论坛跟贴,下一讲链式表

(注:本文作者,EasyJF开源团队 天意,转载请保留作者声明!)

posted on 2006-08-15 14:57 简易java框架 阅读(4978) 评论(19)  编辑  收藏

FeedBack:
# re: 数据结构系列教程(一)  2006-08-15 15:06 基础就是生命
现在各个论坛,blog都被充斥了一种浮躁的东西,各式各样美好的框架。接触到的很多新程序员都还没有开始写过一行代码,就开始学习那些框架。结果使得自己沉迷于框架不能自拔。也不能真正掌握为什么需要这样那样的框架。以后这样基础的文章还是要多写点啊。可惜,本人力不从心。  回复  更多评论
  
# re: 数据结构系列教程(一)  2006-08-15 16:22 深蓝色心情
这些学数据结构的时候不都学过吗?  回复  更多评论
  
# re: 数据结构系列教程(一)  2006-08-15 17:31 Dustin
All about Surviving!
刚出来的毕业生要找个工作不容易啊, 看看招人启示都是充斥着各种框架的名称.没说要招懂数据结构和算法的.
当然与咱们内地大学的整体教学水平太次, 以及整体的学习氛围有关. 各种原理课程在大学都有开课,不是教授太水就是学生自己不努力,每天无所事事有关.  回复  更多评论
  
# re: 数据结构系列教程(一)  2006-08-15 18:45 Shooper.Java
这些东西在大学里搞得还蛮熟的,工作后就忘差不多了,不过这些思想还是很重要的  回复  更多评论
  
# re: 数据结构系列教程(一)  2006-08-15 23:50 游客
@Dustin
招人的时候,会写要招懂代数基础的么?
说是基础,就是说默认已经具备这样的能力了.数据结构都一点不懂,还写啥程序啊  回复  更多评论
  
# re: 数据结构系列教程(一)  2006-08-16 00:25 也来侃侃
算法确实算是基础,但是很多人学过,但都没学好的基础。我们公司招人一般就是强调要基础好的,对算法掌握得熟悉,有较强逻辑思维及分析能力的才是关键。致于框架、工具嘛,这个关系不大,有了基础,这些都很容易。而且更重要的是新员工要能学会公司的开发体系及相关规范,这个比工具重要得多。  回复  更多评论
  
# re: 数据结构系列教程(一)  2006-08-16 09:44 马嘉楠
我有几个地方不太明白,请楼主答复。一下是原文代码:

public void insert(int i, Object obj) throws Exception {

// 在 i 位置插入 obj 对象

if(size==maxsize){ //第一:此处是顺序表为空的情况么?

throw new Exception(" 顺序表无法插入 ");

}

if (i<0||i>size){//第二:插入位置小于0大于最大值,是否应该改成i<0||i>maxsize?

throw new Exception(" 参数错误 ");

}

for(int j=size;j>i;j--) //第三:是否应该改成(int j=maxsize;j>i;j--)?

listArray[j]=listArray[j-1];

listArray[i]=obj;

size++;

}
  回复  更多评论
  
# re: 数据结构系列教程(一)  2006-08-16 09:47 马嘉楠
如果用户想要在表头插入一个元素,也许大多数用户(不是程序员)的习惯是输入位置1而非0,所以是否应该对传进来的参数进行减1的操作啊?

纯属个人意见,呵呵

很喜欢楼主的文章,期待下一讲!  回复  更多评论
  
# re: 数据结构系列教程(一)  2006-08-17 10:04 天意
第一:此处是顺序表为空的情况么?
答:size标示当前数组储存元素个数,size=maxSize就是说此时储存器已经达到最大值,不能继续储存了!
第二:插入位置小于0大于最大值,是否应该改成i<0||i>maxsize?
答:线性表的元素储存在一块连续地址上的内存单元中,中间不能有空缺,比喻说size=0,maxSize=10,说明其中储存了a0、a1、a2、a3、a4 这5个元素,要是改成i>maxSize的话就可以在i=8的位置储存了,那样的话地址就不连续了,所以不能改成maxSize;
第三:是否应该改成(int j=maxsize;j>i;j--)?
答:同上
如果用户想要在表头插入一个元素,也许大多数用户(不是程序员)的习惯是输入位置1而非0,所以是否应该对传进来的参数进行减1的操作啊?
答:这里说的是线性表,按这个同学的说法,程序员应该设计一个链式表!详情见:http://www.easyjf.com/html/20060815/3349457930690354.htm  回复  更多评论
  
# re: 数据结构系列教程(一)  2006-08-18 09:59 dennis
不错的文章,顶一把  回复  更多评论
  
# re: 数据结构系列教程(一)  2006-08-18 23:50 水色
可不可以用 从c++语言,我想学学。  回复  更多评论
  
# re: 数据结构系列教程(一)  2006-08-19 09:11 天意
数据结构重点是个思想问题,语言的使用只不过是代码问题而已,你可以根据不同的内容编写c++的代码,其算法和设计思想都是一样的!由于本教程是基于EasyJF系列的,所以采用java作为描述语言!  回复  更多评论
  
# re: 数据结构系列教程(一)  2006-08-19 10:47 gust
你以为人人都是神啊,记忆再好,也会忘记的,特别是一些比较苦涩深奥的部分,当初即使完全理解了,学得很好,工作中几年也不碰一下,谁还记得,关键就是这些理论和实际开发特别是国内现实开发情况脱节得比较厉害,东西都知道是好的,最终还不是放弃  回复  更多评论
  
# re: 数据结构系列教程(一)  2006-08-19 20:41 天意
@gust
程序员和专家的区别就在这了,对底层的基础知识掌握的不是很好的人只能是程序员,永远到不了专家的行列,这和记忆没有一点关系,只要是真正理解的就不会不知道的!   回复  更多评论
  
# re: 数据结构系列教程(一)  2006-08-24 09:31 ZerGravity
不太同意这样的理解  回复  更多评论
  
# re: 数据结构系列教程(一)  2006-08-29 18:53 ***
@基础就是生命
写的很好,我就是基础不好,想多看看基础的东西缺又找不到好路线,基础的书我也好多,但是总是感觉实际性不是很强...........框架我用的多了,是很爽.但是用的过程中会发现基础真的是很烂!~

"他们纯粹是程序员"你的这句话一方面是对的,但是我告诉你,你以为谁都不学好基础吗.........话过分请担待!~大家都想有自己的思想,谁也不想做个只会拿框架干活的人.....可能是有的时候真的是破与无奈.只能慢慢积累,你现在很强你才有实力说这种话....你没有差的时候吗  回复  更多评论
  
# re: 数据结构系列教程(一)  2006-08-29 22:52 poscard
《数据结构》和《操作系统》是两门很重要的基础课。我现在越来越感觉有必要把这两方面的知识再学习、实践一下了。
程序开发中涉及很多对数据的抽象,还有像操作系统那样对资源的管理。
但,,在开发不出自己的作品之前就对这两门基础课进行深入学习,感觉好打击自己对计算机软件的兴趣啊。  回复  更多评论
  
# re: 数据结构系列教程(一)  2006-09-02 13:10 Nix
@***
谁都有差的时候,只不过知道自己差的时候去不去充实自己就是各人的区别了
懂得充实自己的人当然会有实力。
不要说没有时间,事情忙,学习这东西,只要想学,永远有机会。  回复  更多评论
  
# re: 数据结构系列教程(一)  2006-11-03 22:24 colin yi
d  回复  更多评论
  

只有注册用户登录后才能发表评论。


网站导航: