分享
 
 
 

数据结构系列教程(一)

王朝other·作者佚名  2006-08-15
窄屏简体版  字體: |||超大  

接触不少程序员,都能够独立的作一下小型应用系统,和他们交谈起来才发现,他们纯粹是程序员,对基础的掌握太差,比喻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类,当然有时为了限定具体类型你可以重写这个类然后抛出相应的异常即可,这个顺序表的效率分析工作留给大家,大家可以到论坛跟贴,下一讲链式表!

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有