【数据结构】线性表和顺序表

2024-09-20 10:17:48 浏览数 (1)

框架

线性表

是 n 个具有相同特征的数据元素的有限序列

常见的线性表：顺序表、链表、栈、队列......

undefined

线性表在逻辑上是线性结构，也就是连续的一条直线

但在物理结构上不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式进行存储

顺序表

  • 顺序表其实就是一个数组，是用一段物理地址连续的存储单元依次存储数据元素的线性结构undefined顺序表实现逻辑undefined
  • 其访问速度比较快，给定下标情况下，速度为 O (1)
  • 适用于经常进行下标查找或者更新的操作
  • 创建一个 IList 接口，用来放所有相关的方法
  • 创建一个 MyArrayList 类，数组成员变量 int[ ] elem 用来放数据，整形成员变量 usedSize 用来记录数组里面的数据个数
  • 在 MyArrayList 类里面实现 IList 接口，并重写里面的方法

各种方法的实现

boolean isFull ()——判断数组是否放满

  • 直接返回 usedSize == elem.length 即可，相等为 true，不相等为 false
代码语言：java复制
    @Override
    public boolean isFull() {
        return usedSize == elem.length;
    }

void add (int data)——在数组末尾插入新元素

  1. 首先用 isFUll() 方法判断数组是否装满，若装满，就调用 Arrays 的 copyOf(elem, 2*elem.length) 方法对数组进行扩容
  2. 将第 usedSize 位的数组元素赋值为 data
  3. usedSize ;
代码语言：java复制
    @Override
    public void add(int data) {
        if(isFull()){
            //如果满了，就扩容为原来的两倍
            elem = Arrays.copyOf(elem,elem.length*2);
        }
        elem[usedSize] = data;
        usedSize  ;
    }

void add (int pos, int data)——在指定位置插入元素

  1. 首先判断传入的参数 pos 是否合法 @Override public void add(int pos, int data) { //判断输入的 pos 是否合法 try{ checkAddPos(pos); }catch (PosNotLegalException e){ e.printStackTrace(); } //判断数组是否装满 if(isFull()){ elem = Arrays.copyOf(elem,elem.length*2); } //移动元素 for (int i = usedSize - 1; i >= pos; i--) { elem[i 1] = elem[i]; } //插入元素 elem[pos] = data; usedSize ; }
    • 我们创建一个 checkPosOfAdd(int pos) 方法来进行判断，
    • 若 (pos < 0 || pos >= usedSize) ，则抛出一个自定义异常 PosNotLegalException
  2. 再用 isFull() 方法判断数组是否装满，若装满，就调用 Arrays 的 copyOf(elem, 2*elem.length) 方法对数组进行扩容
  3. 移动元素，将后面的元素从后往前依次向后移一位 elem[usedSize] = elem[usedSize - 1];
  4. 插入元素，elem[pos] = data;
  5. usedSize ;
void checkPosOfAdd (int pos)——检查传入 add 方法中的 pos 是否合法
  • 若不合法则抛出一个自定义异常 PosNotLegalExceptionprivate void checkPosOfAdd(int pos) throws PosNotLegalException{ if(pos < 0 || pos > usedSize){ //自定义一个异常类：PosNotLegalException throw new PosNotLegalException("pos位置不合法"); } }undefinedPosNotLegalException——传入参数不合法的自定义异常public class PosNotLegalException extends RuntimeException{ public PosNotLegalException(String msg) { super(msg); } }undefined
  • 继承自运行时异常 RuntimeException

boolean contain (int toFind)——判断是否包含某个元素

  1. 遍历数组 usedSize 次public boolean contains(int toFind) { //只需要寻找useSize次 for (int i = 0; i < usedSize; i ) { if(elem[i]==toFind){ return true; } } return false; }
  2. 当 elem[i] == toFind 时，return true;
  3. 找不到，return false;

int indexOf (int toFind)——查找某个对应元素的位置

  1. 遍历数组 usedSize 次
  2. 当 elem[i] == toFind 时，return i;
  3. 找不到，return 0;
代码语言：java复制
public int indexOf(int toFind) {  
    for (int i = 0; i < usedSize; i  ) {  
        if(elem[i] == toFind)  
            return i;  
    }    return -1;  
}

int get (int pos)——获取 pos 位置的元素

  1. 判断传入的参数 pos 是否合法
    • 创建 checkPosOfGetAndSet(int pos) 方法来进行判断
    • 若 (pos < 0 || pos > usedSize)，则抛出自定义异常 PosNotLegalException
  2. 合法，return elem[pos];
代码语言：java复制
public int get(int pos) {  
    try{  
        checkPosOfGet(pos);  
    }catch (PosNotLegalException e){  
        e.printStackTrace();  
    }    return elem[pos];  
}
void checkPosOfGetAndSet (int pos)——判断输入 get 和 set 方法的值是否合法
  • 若不合法则抛出一个自定义异常 PosNotLegalExceptionprivate void checkPosOfGet (int pos) throws PosNotLegalException{ if(pos < 0 || pos > usedSize){ throw new PosNotLegalException("pos位置不合法"); } }undefined

void set (int pos, int value)——将 pos 位置的元素设为 value

  1. 判断传入的参数 pos 是否合法public void set(int pos, int value) { try { checkPosOfGetAndSet(pos); } catch (PosNotLegalException e) { e.printStackTrace(); } elem[pos] = value; }undefinedvoid remove (int toRemove)——删除第一次出现的关键字
    • 调用 checkPosOfGetAndSet(int pos) 方法来进行判断
    • 若 (pos < 0 || pos > usedSize)，则抛出自定义异常 PosNotLegalException
  2. 赋值：elem[pos] == value;
  3. 调用 indexOf() 方法，获取关键字的下标，并对下标进行判断，若 pos == -1，则输出“未找到”
  4. 移动元素，将后面的元素从后往前依次向后移一位 elem[pos] = elem[pos 1];
  5. usedSize--;
代码语言：java复制
public void remove(int toRemove) {  
    int pos = indexOf(toRemove);  
  
    if (pos == -1) {  
        System.out.println("没有要找的关键字");  
    }    for (int i = pos; i < usedSize - 1; i  ) {  
        elem[i] = elem[ i   1];  
    }    this.usedSize--;  
}

void removeAll (toRemove)——删除所有出现的关键字

  1. 使用 for 循环多次调用 indexOf() 方法，若 pos != -1，则继续操作
  2. 移动元素，将后面的元素从后往前依次向后移一位 `elempos = elempos 1;
  3. usedSize--;
代码语言：java复制
public void removeAll(int toRemove) {  
    for (int i = 0; i < usedSize; i  ) {  
        int pos = indexOf(toRemove);  
        if (pos != -1) {  
            for (int j = pos; j < usedSize - 1; j  ) {  
                elem[j] = elem[j   1];  
            }            
            usedSize--;  
        }    
    }
}

void clear ()——清空顺序表

  • 因为是基本类型，直接 usedSize = 0 即可
  • 若是引用类型，则需将每一个位置的数据都置为 null (防止内存泄露)
代码语言：java复制
public void clear() {  
    usedSize = 0;  
}
腾讯技术创作特训营S9

0 人点赞