数据结构- 顺序表

顺序表 是以数组的形式 顺序存储 线性表的结构。

具有线性表的基本特点：1）头结点：第一个结点没有前继元素 。2）尾结点：最后一个结点没有后继元素 3）其他数据元素有且仅有一个 前驱 和 一个后驱 结点。

顺序表独有的特点：n 为长度 ， 指定元素位置 i

1）以数组形式实现顺序表， 每个结点放一个元素。

2）插入元素需要向后移动的次数是 ： n - i + 1

3）删除元素需要向前移动的次数是 ： n - i

4）查询访问不同位置的内存地址都可以通过公式 计算，因此 查询访问快速。

顺序表 API的设计

【设计】

  1.     //清空线性表
  2.     public void clear();
  4.     //返回线性表的长度
  5.     public int getLength();
  7.     //添加元素到线性表尾部
  8.     public void add(T data);
  10.     //添加元素到线性表指定位置
  11.     public void add(T data , int index);
  13.     //移除元素表指定下标的元素
  14.     public void remove(int index);
  16.     //获取指定位置的元素
  17.     public T get(int index);
  19.     //扩充线性表的容量
  20.     public T[] resize(int newSize);

成员变量：1.引用类型数组 2.元素个数和长度 length
成员方法：

  • 1.清空顺序表

  • 2.添加元素

  • 3.添加元素到指定位置前

  • 4.移除元素

  • 5.获取指定位置的元素

  • 6.修改替换指定位置的元素

  • 7.重写toString展示顺序表内容

  • 8.判断线性表是否为空

  • 9.获取线性表的长度

  • 10.扩容顺序表
    【算法实现思路】
    1.clear() 清空顺序表 -> 删除所有元素 -> 返回一个新数组,长度为0
    2.add（）添加新元素 -> 方法接收新元素 -> 新元素赋值到数组 -> arr[n] = data;
    3.add（index）添加元素到指定下标 ->
    方法名(目标下标位置,元素值) {
    //想法1：延长顺序表长度（煞笔思维，因为是数组怎么可能拓展长度，不要脱离本质）
    //想法2：第一步:从后往前循环 【int i = 数组长度-1 ； i > index ; 向后移动 arr[i] = arr[i-1] , 执行完成 i —】;
    //第二步:执行 arr[目标下标] = 元素值
    //后续考虑：数组越界的异常处理
    }
    4.remove（）移除指定下标的元素(int index){
    //找出目标下标 与 下标后向左移动的次数 .得出循环条件 i = index , i < count -1 ; i++
    //arr[目标下标] = arr[i]+1
    //再将a[i+1]原有元素清空 = null
    }
    5.get（）获取 指定位置 的元素。 return ele数组[index] 即可
    6.toString（）@Override 重写-> 遍历数组 ,将数组的内容 添加到 String 变量去,然后sout 即可
    7..isEmpty（）判断线性表是否为空 -> 如果元素个数n 为0 则返回 true , 否则返回 false
    8..getLength（）获取线性表的长度 -> return ele.length 即可
    9.isFull() 顺序表内容是否 已满 -> return count == ele.length; 即可
    10.reSize(int newSize) 顺序表已满时,则扩容 .即将 新建一个[] newSize ,且将旧的数据接到新的数组中

  1. package 线性结构_顺序存储.线性表;
  3. /**
  4.  * @author Tommy
  5.  * @version 1.0
  6.  * @desc
  7.  * @ClassName SequenceList
  8.  * @date 2022/6/23/14:16
  9.  **/
  11. public class SequenceList<T> {
  14.     private T[] ele ;     //存储元素的数组
  15.     private int count ;   //记录元素个数
  17.     SequenceList(int capacity){
  18.         this.ele =(T[])new Object[capacity];
  19.     }
  21.     /**
  22.      * 判断顺序表是否为空
  23.      * @return
  24.      */
  25.     public boolean isEmpty(){
  26.         return count == 0;
  27.     }
  29.     /**
  30.      * 判断顺序表队列位置是否已满
  31.      */
  32.     public boolean isFull(){
  33.         return count==getLength();
  34.     }
  35.     /**
  36.      * 返回顺序表的 长度
  37.      * @return
  38.      */
  39.     public int getLength(){
  40.         return ele.length;
  41.     }
  43.     /**
  44.      * 将线性表清空重置
  45.      */
  46.     public void clear(){
  47.         this.count = 0;
  48.     }
  50.     /**
  51.      * 把 data 数据元素 添加到顺序表
  52.      * @param data
  53.      */
  54.     public void add(T data){
  55.         ele[count] = data;
  56.         count++;
  57.     }
  59.     /**
  60.      * 将data元素 添加到顺序表的指定索引下标位置处
  61.      * @param data
  62.      * @param index
  63.      */
  64.     public void add(T data,int index) {
  65.         if (isFull()) {
  66.            resize(10);
  67.         }
  68.         for (int i = count ; i > index; i--) {
  69.             ele[i] = ele[i - 1];
  70.         }
  71.         ele[index] = data;
  73.     }
  75.     /**
  76.      * 移除顺序表下标位置中的元素
  77.      * @param index
  78.      */
  79.     public void remove(int index){
  80.         for (int i = index; i < count-1; i++) {
  81.             ele[i] = ele[i+1];
  82.             ele[i+1] = null; //将原有元素赋0;
  83.         }
  84.     }
  86.    public T get(int index){
  87.         return ele[index];
  88.    }
  90.     @Override
  91.     public String toString() {
  92.         String result = "";
  93.         for (int i = 0; i < getLength(); i++) {
  94.             result = ele[i] +" ";
  95.             System.out.print(result);
  96.         }
  97.         return result;
  98.     }
  101.     //根据参数newSize，扩容
  102.     public void resize(int newSize){
  103.         //定义一个临时数组，指向原数组
  104.         T[] temp=ele;
  105.         //创建新数组
  106.         ele=(T[])new Object[newSize];
  107.         //把原数组的数据拷贝到新数组即可
  108.         for(int i=0;i<count;i++){
  109.             ele[i]=temp[i];
  110.         }
  111.     }
  112. }