数据结构-顺序表

一.什么是顺序表

顺序表就是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储,在数组上完成对数据的增删改查.

二.如何创建一个数据表

我们一般采用数组来创建一个顺序表,并且定义一个成员变量来记录当前表中的元素个数.
1

三.实现一个顺序表都需要哪些基本的功能?

package arraylist;

public interface IList {
    // 新增元素,默认在数组最后新增
    public void add(int data);
    // 在 pos 位置新增元素
    public void add(int pos, int data);
    // 判定是否包含某个元素
    public boolean contains(int toFind);
    // 查找某个元素对应的位置
    public int indexOf(int toFind);
    // 获取 pos 位置的元素
    public int get(int pos);
    // 给 pos 位置的元素设为 value
    public void set(int pos, int value);
    //删除第一次出现的关键字key
    public void remove(int toRemove);
    // 获取顺序表长度
    public int size();
    // 清空顺序表
    public void clear();
    // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
    public void display();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

一个数据表最基本的功能无非就是对数据的增删改查.

1.默认在顺序表最后添加元素(add)

(1).在添加元素的时候我们首先要判断顺序表是否已经满了,如果满了就要扩容.

  我们利用usedSize是否和顺序表长度相同,如果相同的话,就证明满了,如果满了我就可以通过Arrays.copyof()来扩容.usedSize就是
  当前可存放元素的下标.存放元素成功后usedSize要++;
1
2

 public boolean isFull(){
        return usedSize==elem.length;
    }
    public boolean isEmpty(){
        return usedSize==0;
    }
    //扩容方法
    public void CopyElem(){
        if (isFull()){
            this.elem= Arrays.copyOf(elem,elem.length*2);
        }
    }
    @Override
    public void add(int data) {
        //判断表中元素是否满了,满了就扩容
        CopyElem();

        //usedSize可以代表当前可以存放元素的位置
        elem[usedSize]=data;
        usedSize++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.在指定位置插入元素(add)

(1).首先我们就要检查pos的合法性,如果pos小于0或者pos>=usedSize,那么pos就是不合法的,那么就不能存放元素.(对于检查pos的合法性我们可以抛一个自定义异常)


(2).那么我们应该如何存放元素?
1.首先我们应该将pos位置以及pos后边的元素往后移动一个位置,然后将pos位置存放为指定元素,然后usedSize++;

@Override
    public void add(int pos, int data) {
        try{
            checkPos(pos);
        }catch (PosIllegality posIllegality){
            posIllegality.printStackTrace();
        }
        CopyElem();
        for (int i = usedSize-1; i >=pos; i--) {
            elem[i+1]=elem[i];
        }
        elem[pos]=data;
        usedSize++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

创建一个for循环,从最后一个元素往后一个位置(usedSize-1)移动,如果满了还要扩容

3.判断是否包含某个元素

(1).如果顺序表为空,直接返回false.

  if(isEmpty()){
            return false;
        }
1
2
3

(2). 如果不为空,那么我就要遍历顺序表,如果找到就返回true,遍历结束还没有找到的话直接返回false.

 for (int i = 0; i <=usedSize; i++) {
            if(elem[i]==toFind){
                return true;
            }
        }
        return false;
1
2
3
4
5
6

4.查找某个元素对应的位置

(1).当然,如果顺序表为空的话我们就要返回-1,因为下标都是从0开始的,没有的话返回-1.

 if (isEmpty()){
            return -1;
        }
1
2
3

(2).一样的遍历整个顺序表,如果找到就返回该点的下标,找不到就返回一个-1.

for (int i = 0; i < usedSize; i++) {
            if(elem[i]==toFind){
                return i;
            }
        }
1
2
3
4
5

5.获取指定(pos)位置的元素

(1).首先要判断pos的合法性,如果pos<0或者pos>=usedSize,我们不能像上边一样返回一个-1,因为有可能我们所想要找到的pos位置的值也是-1,那么我们这时可以定义一个异常来表示pos的和法性

public class PosIllegality extends RuntimeException{

    public PosIllegality(String msg) {
        super(msg);
    }

}
1
2
3
4
5
6
7

     private void checkPosOnGetAndSet(int pos) throws PosIllegality{
        if(pos < 0 || pos >= usedSize) {
            System.out.println("不符合法！");
            throw new PosIllegality("获取指定下标的元素异常: "+pos);
        }
    }
1
2
3
4
5
6

(2).检查完pos的合法性之后我们还要检查顺序表是否为空

package mylist;

/**
 * @Author 12629
 * @Description：
 */
public class MyArrayListEmpty extends RuntimeException{
    public MyArrayListEmpty(String msg) {
        super(msg);
    }
}
1
2
3
4
5
6
7
8
9
10
11

(3).上述都处理完之后我们就可以直接return pos位置的元素.

 @Override
    public int get(int pos) throws MyArrayListEmpty{
        checkPosOnGetAndSet(pos);

        if(isEmpty()) {
            throw new MyArrayListEmpty("获取指定下标元素时" +
                    "顺序表为空！");
        }

        return elem[pos];
    }
1
2
3
4
5
6
7
8
9
10
11

6.给指定(pos)位置元素设置为value

(1).首先检查pos的合法性

(2).直接将pos位置的值更新为value

  @Override
    public void set(int pos, int value) {
        checkPosOnGetAndSet(pos);

        elem[pos] = value;
    }
1
2
3
4
5
6

7.删除第一次出现的关键字

(1).我们删除关键字的思路主要是让想要删除的元素的后边的元素前移,将他覆盖掉.

(2).首先我们要找到这个元素,通过上边的寻找元素的那个方法,如果没有找到就退出.

@Override
    public void remove(int toRemove) {
        int index = indexOf(toRemove);
        if(index == -1) {
            System.out.println("没有这个数字！");
            return;
        }
        for(int i = index; i < usedSize-1;i++) {
            elem[i] = elem[i+1];
        }
        usedSize--;
    }
1
2
3
4
5
6
7
8
9
10
11
12

8.返回顺序表的长度

(1).直接返回usedSize就行

  return this.usedSize;
1

9.清空顺序表

我们可以直接让usedSize=0;

  @Override
    public void clear() {
        usedSize=0;
    }
1
2
3
4

最后希望我的分享能带给你一些帮助,如果有什么问题也可以像我指出,大家一起努力.