数据结构——顺序表

顺序表是用一段连续的物理地址依次存储数据的线性结构,，一般采用数组来存储。在数组上完成数据的CURD操作。

一、接口实现

准备测试数据

publicclassMyArrayList{publicint elem[];publicint usedSize;//获取有效数据publicMyArrayList(){this.elem =newint[10];}

(1)在 pos 位置新增元素

步骤:
a. 判断pos位置合法性.
b. 判断顺序表是否满了,如果满,则copy.
c. 挪到数据.
d. 插入,usedSize自增.

publicvoidadd(int pos,int data){//pos位置合法性if((pos <0)||(pos > usedSize)){System.out.println("pos位置不合法");return;}if(full()){this.elem =Arrays.copyOf(this.elem,2*this.elem.length);}//挪数据for(int i = usedSize-1; i >= pos; i--){this.elem[i+1]=this.elem[i];}//增加数据this.elem[pos]= data;this.usedSize++;}

(2)删除第一次出现的关键字key

步骤:
a. 判断顺序表是否为空.
b. 判断key是否存在.
c. 覆盖(elem[i]=elem[i+1]).
d. usedSize自减(如果是引用类型,则把最后的引用置为null).

publicvoidremove(int toRemove){//判断空if(0==this.usedSize){System.out.println("顺序表为空");return;}//判断元素是否存在int index =indexOf(toRemove);if(-1== index){System.out.println("元素不存在");return;}//覆盖for(int i = index; i < usedSize -1; i++){this.elem[i]=this.elem[i+1];}this.usedSize--;// this.elem[usedSize] = null;}

(3) 判定是否包含某个元素

步骤:
a.遍历整个顺序表,包含返回true,未包含返回false.
b.遍历整个顺序表,查到返回小标,未查到返回-1.

// 判定是否包含某个元素publicbooleancontains(int toFind){for(int i =0; i < usedSize; i++){if(this.elem[i]== toFind){returntrue;}}returnfalse;}// 查找某个元素对应的位置publicintindexOf(int toFind){for(int i =0; i < usedSize; i++){if(this.elem[i]== toFind){return i;}}return-1;}

(4) 给 pos 位置的元素设为 value

步骤:
a. 判断pos位置合法性.
b. 直接赋值(elem[pos]=value).

publicvoidset(int pos,int value){//pos不合法,空if((pos <0)||(pos >= usedSize)){System.out.println("pos位置不合法或者顺序表为空");return;}this.elem[pos]= value;}

(5) 清空顺序表

步骤:
a. 把usedSize之为0.
b. 如果是引用类型,把所有的的引用置为null

publicvoidclear(){this.usedSize =0;/* for (int i = 0; i < usedSize; i++) {
            this.elem[i] = null;
        }*/}

二、总结及思考

顺序表执行效率很慢,极端情况下增加或者删除数据时必须要挪动大量数据来完成.

思考:有没有一种数据结构不需用挪动数据就可以达到数据的更改?