基本数据结构之“表”

insertArr

数据结构中最简单和基本的三中数据结构就是 表(List),栈(Stack)和队列(Queue),并且,每一个有意义的程序都会使用至少一种这样的数据结构。这篇文章将简单介绍表数据结构以及这个数据结构在Java上的实现。

首先我要引入一个概念,叫做抽象数据类型(abstract data type,ADT),简单地说,平时编程用到的整形数字,浮点型数字,布尔,它们都是基本的抽象数据类型,ATD是用于指定逻辑特性而不指定实现细节的数据结构。一个简单的例子 int a=0 这里面int就是一个ADT,体现出变量a的特性,它是一个整数。而且抽象数据类型还包括该模型上的一些操作。 就像“魂斗罗”这个经典的游戏,里面的游戏主角是个壮汉,我们给他定义了基本操作,前进、后退、跳、打子弹等。这就是一个抽象数据类型,定义了一个数据对象、对象中各元素之间的关系及对数据元素的操作。至于,到底是哪些操作,这只能由设计者根据实际需要来定。像主人公可能开始只能走和跳,后来发现应该增加一种打子弹的操作,再后来又有了按住打子弹键后前进就有跑的操作。这都是根据实际情况来定的。再来一个现实点的例子,一个集合ADT,他可以存放一堆数,而且可以包含一系列操作,比如添加,删除,包含,搜索之类的。

好的接下来我们就要引入表ADT了

表就是列表(List),形如A1,A2,、、、、An是一个一般的表,我们说这个表的大小为n。而且我们将大小为0的表叫做空表。

关于这个数据结构怎么实现呢,最简单的方法就是数组了, int[3] a={1,2,3},这样就创建了一个大小为3的数组里面有三个整数1,2,3。很简单不是吗,但是刚才我讲到了,任何一种ADT还包含一些操作,我们想把这个表的第三个元素变成4怎么办呢,相信有基础的人都知道 int[3]=4,这样就可以了。但是如果我们想在添加第四个元素呢?我们都知道数组一般都是由固定容量创建的,如果想进行扩充操作,通常情况下就是用双倍容量创建一个新的数组,然后将之前数组的元素在拷贝到新的数组里来解决容量问题。
array

int [] arr=new int[10];
 ......
 //接下来我们要扩大arr数组
 int [] newArr=new int[arr.length()*2];
 for(int i=0;i<arr.length;i++)
 newArr[i]=arr[i];
 arr=newArr;

数组的这一方案可以使得printList遍历各个元素可以通过线性时间来执行,而且findNth这样的搜索特定元素方法需要花费常数时间,这是不错的。但是插入和删除操作却花销巨大。最坏的情况,如果要在第一位插入一个新的元素,这样需要将整个数组全部向后移动一位来腾出第一位的空间,而删除第一个元素需要将所有元素全部向前面移动一个位置,所以最坏情况下来看这两个操作的复杂度为O(N)。相比之下,如果这些操作都发生在最后一个元素,比如在最后增加元素或者删除最后一个元素,这样将没有元素需要被移动,这样这两个操作的复杂度为O(1);
insertArr

所以说,如果一个表示通过不断向数组增加元素所形成的,形成表后不需要再增添或者删除,只会发生访问操作,那么,使用数组来实现表示合理的。然而如果需要对表发生一些插入或者删除操作,而且不一定全发生在表的最末端,那么数组就不是一个很好地选择了。

此文章作者为周毅刚,归属于其个人网站miketech.it,未经允许,不得转载。

打赏

Leave a Reply

Your email address will not be published. Required fields are marked *