数据结构——顺序表

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

一、接口实现

准备测试数据

public class MyArrayList {
    public int elem[];
    public int usedSize;//获取有效数据

    public MyArrayList() {
        this.elem = new int[10];
    }

1
2
3
4
5
6
7
8

(1)在 pos 位置新增元素

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

public void add(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++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

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

    public void remove(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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

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

    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if(this.elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }

    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if(this.elem[i] == toFind) {
                return i;
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

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

    public void set(int pos, int value) {
        //pos不合法,空
        if((pos < 0)||(pos >= usedSize)) {
            System.out.println("pos位置不合法或者顺序表为空");
            return;
        }
        this.elem[pos] = value;
    }
1
2
3
4
5
6
7
8
9

(5) 清空顺序表

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

    public void clear() {
        this.usedSize = 0;
       /* for (int i = 0; i < usedSize; i++) {
            this.elem[i] = null;
        }*/
    }
1
2
3
4
5
6
7

二、总结及思考

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

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