1、线性表的概述

  • 线性表的二元组：linearity=(D,S)
    • D={01，02，03，04，05，06}
    • S={<01,04>,<04,06>,<06,02>,<02,05>,<05.03>}
    • 在linearity中，数据元素是有序的，有一个头元素（01），还有一个尾元素（03），除了头元素之外其余元素都有一个直接前驱元素，除尾元素之外，其他每个元素都有一个直接后继元素，数据元素之间是一对一的关系，linearity就是一个线性结构

image.png

2、线性表抽象数据类型

  1. ADT     List{
  2.     数据对象：D={ai 属于某个数据类型，i=0，1，2，3，...}
  3.                   D={a0,a1,a2,a3,a4,...an},表示所有的元素都是同一种数据类型
  4.   数据关系：R={<ai,ai+1>}
  5.   数据操作：
  6.               getSize()：返回线性表当中的元素个数
  7.         isEmpty()：返回线性表是否为空，线性表为空true，否则false
  8.         insert(e,i)：在线性表的指定索引位置i插入元素e
  9.         contains(e)：在线性表中判断是否包含e元素，存在返回true，不存在返回false
  10.         indexOf(e)：获取元素e在线性表中的索引值，不存在返回-1
  11.         remove(e)：删除线性表中第一个与e相同的元素，删除成功返回删除的元素
  12.         remove(i)：删除线性表中指定索引值的元素，返回删除的元素
  13.         replace(i,e)：把线性表中索引为i的元素替换为e
  14.         get(i)：返回线性表中索引值为i的元素
  15.         insertBefore(p,e)：在线性表中元素p的前面插入元素e
  16.         insertAfter(p,e)：在线性表中元素p的后面插入元素e
  17.         **所有涉及索引的操作都需要指定越界异常**
  18. }

  • 抽象数据类型可以对应一个Java类

    • 数据对象与元素之间的关系可以通过类的成员变量来储存和表示
    • 数据操作可以通过一组方法来实现

      3、MyList接口

  • 使用Java中的接口表示ADT中的数据操作，在使用类完成抽象数据类型时，只要这个类实现接口就可以完成抽象数据类型中定义的操作 ```java public interface MyList {

    int getSize();//返回线性表当中的元素个数

    boolean isEmpty();//返回线性表是否为空，线性表为空true，否则false

    void insert(Object obj, int index);//在线性表的指定索引位置i插入元素e

    boolean contains(Object obj);//在线性表中判断是否包含e元素，存在返回true，不存在返回false

    int indexOf(Object obj);//获取元素e在线性表中的索引值，不存在返回-1

    Object remove(Object obj);//删除线性表中第一个与e相同的元素，删除成功返回删除的元素

    Object remove(int index);//删除线性表中指定索引值的元素，返回删除的元素

    void replace(int index, Object obj);//把线性表中索引为i的元素替换为e

    Object get(int index);//返回线性表中索引值为i的元素

    void insertBefore(Object pre, Object obj);//在线性表中元素p的前面插入元素e

    void insertAfter(Object af, Object obj);//在线性表中元素p的后面插入元素e

}

  1. <a name="aKDay"></a>
  2. # 4、线性表的顺序存储
  4. - 线性表的顺序存储，就是采用一组地址连续的存储空间，依次存储线性表中的元素
  5. - 以数据元素在计算机内存的地址相邻性表示数据元素之间的关系
  6. - 在Java中可以使用数组来存储线性表中的数据元素，数组就是一块连续的存储空间
  7. - 我们以insert(e,i)和remove(i)为例，分析实际数组操作过程
  9. ![image.png](https://cdn.nlark.com/yuque/0/2021/png/12407770/1612009097238-66ba44b2-9f64-4a29-88c3-f72e127e63c3.png#align=left&display=inline&height=475&margin=%5Bobject%20Object%5D&name=image.png&originHeight=611&originWidth=919&size=64403&status=done&style=none&width=715)
  10. <a name="ScDi5"></a>
  11. # 5、线性表的顺序代码实现
  12. ```java
  13. public class MyArrayList implements MyList{
  15.     //定义一个数组存放数据元素
  16.     private Object[] elements;
  17.     //定义数组的默认初始化容量为16
  18.     private static final int DEFAULT_CAPACITY = 16;
  19.     //定义一个变量保存数据元素的个数
  20.     private int size;
  22.     //通过构造方法进行数组的初始化
  23.     public MyArrayList() {
  24.         elements = new Object[DEFAULT_CAPACITY];
  25.     }
  27.     public MyArrayList(int initialCapacity) {
  28.         elements = new Object[initialCapacity];
  29.     }
  31.     @Override
  32.     public int getSize() {
  33.         return size;
  34.     }
  36.     @Override
  37.     public boolean isEmpty() {
  38.         if (size == 0){
  39.             return true;
  40.         }
  41.         return false;
  42.     }
  44.     @Override
  45.     public void insert(int index, Object obj) {
  46.         //判断索引值index是否越界
  47.         if (index < 0 || index > size){
  48.             throw new IndexOutOfBoundsException(index + "越界");
  49.         }
  50.         //如果数组已满，需要进行扩容，从index开始把元素依次后移动，把元素存储到index的位置
  51.         if (size >= elements.length){
  52.             expandSpace(); //数组扩容
  53.         }
  54.         //把从index开始的元素依次后移
  55.         for (int j = size; j > index; j --){
  56.             elements[j] = elements[j-1];
  57.         }
  58.         //把元素obj放入到index位置
  59.         elements[index] = obj;
  60.         //元素个数+1
  61.         size ++;
  62.     }
  64.     //定义数组扩容方法
  65.     private void expandSpace() {
  66.         //定义一个更大的数组，扩容为原来的两倍
  67.         Object[] newElements = new Object[elements.length*2];
  68.         //把原数组的内容复制到新的数组当中
  69.         for (int i = 0; i < elements.length; i ++){
  70.             newElements[i] = elements[i];
  71.         }
  72.         //将原来的数组名指向新的数组
  73.         elements = newElements;
  74.     }
  76.     @Override
  77.     public boolean contains(Object obj) {
  78.         //通过indexOf方法来判断是否包含元素，不包含indexOf会返回-1
  79.         return indexOf(obj) >= 0;
  80.     }
  82.     @Override
  83.     public int indexOf(Object obj) {
  84.         //遍历数组获取指定元素的下标
  85.         if (obj == null){
  86.             //线性表中用户可能会添加null
  87.             for (int i = 0; i < size; i ++){
  88.                 if (elements[i]==null){
  89.                     return i;
  90.                 }
  91.             }
  92.         }else{
  93.             for (int i = 0; i < size; i ++){
  94.                 if (obj.equals(elements[i])){
  95.                     return i;
  96.                 }
  97.             }
  98.         }
  99.         return -1;
  100.     }
  102.     @Override
  103.     public Object remove(Object obj) {
  104.         int index = indexOf(obj);
  105.         if (index < 0){
  106.             throw new NoSuchElementException("没有指定元素" + obj);
  107.         }
  108.         Object result = remove(index);
  109.         return result;
  110.     }
  112.     @Override
  113.     public Object remove(int index) {
  114.         if (index < 0 || index >= size){
  115.             throw new IndexOutOfBoundsException(index+"下标越界");
  116.         }
  117.         Object obj = elements[index];
  118.         //将移除元素后的元素依次前移，最后的元素置为null
  119.         for (int j = index; j < size; j ++){
  120.             elements[j] = elements [j+1];
  121.         }
  122.         elements[size-1]=null;
  123.         size --;
  124.         return obj;
  125.     }
  127.     @Override
  128.     public void replace(int index, Object obj) {
  129.         if (index < 0 || index >= size){
  130.             throw new IndexOutOfBoundsException(index+"下标越界");
  131.         }
  132.         elements[index] = obj;
  133.     }
  135.     @Override
  136.     public Object get(int index) {
  137.         if (index >= size || index < 0){
  138.             throw new IndexOutOfBoundsException(index + "下标越界");
  139.         }
  140.         return elements[index];
  141.     }
  143.     @Override
  144.     public void insertBefore(Object pre, Object obj) {
  145.         if (contains(pre)==false){
  146.             throw new NoSuchElementException("没有指定元素"+pre);
  147.         }
  148.         int index = indexOf(pre);
  149.         insert(index,obj);
  150.     }
  152.     @Override
  153.     public void insertAfter(Object suf, Object obj) {
  154.         if (contains(suf)==false){
  155.             throw new NoSuchElementException("没有指定元素"+suf);
  156.         }
  157.         int index = indexOf(suf) + 1;
  158.         insert(index,obj);
  159.     }
  161.     @Override
  162.     public String toString() {
  163.         //把线性表中的每一个元素连接起来，遍历数组中的每一个元素
  164.         StringBuilder result = new StringBuilder();
  165.         result.append("[");
  166.         for (int i = 0; i < size; i ++){
  167.             result.append(elements[i]+",");
  168.         }
  169.         //移除最后一个元素末尾的','
  170.         result.deleteCharAt(result.length()-1);
  171.         result.append("]");
  172.         return result.toString();
  173.     }
  174. }

6、测试线性表顺序代码实现

  1. public class MyListTest {
  2.     public static void main(String[] args) {
  3.         //创建一个MyArrayList对象
  4.         MyArrayList list = new MyArrayList();
  5.         //isEmpty判断数组是否为空
  6.         System.out.println(list.isEmpty());//true
  7.         //getSize查看线性表元素个数
  8.         System.out.println(list.getSize());//0
  9.         //insert向数组中添加元素
  10.         list.insert(0,"one");
  11.         list.insert(1,"two");
  12.         list.insert(0,"zero");
  13.         //isEmpty判断数组是否为空
  14.         System.out.println(list.isEmpty());//false
  15.         //getSize查看线性表元素个数
  16.         System.out.println(list.getSize());//3
  17.         //查看线性表中的数据
  18.         System.out.println(list);//[zero,one,two]
  19.         //contains判断是否包含某个元素
  20.         System.out.println(list.contains("one"));//true
  21.         System.out.println(list.contains("hello"));//false
  22.         //indexOf获取元素下标
  23.         System.out.println(list.indexOf("one"));//1
  24.         System.out.println(list.indexOf("hello"));//-1
  25.         //get获取指定下标的元素
  26.         System.out.println(list.get(0));//zero
  27. //        System.out.println(list.get(5));//异常：5下标越界
  28.         //测试replace替换
  29.         list.replace(0,"ZERO");
  30.         System.out.println(list);//[ZERO,one,two]
  31. //        list.replace(3,"three");//异常：3下标越界
  32.         //insertBefore在指定元素前插入元素
  33.         list.insertBefore("two","onePoint");
  34.         System.out.println(list);//[ZERO,one,onePoint,two]
  35. //        list.insertBefore("hello","nice");//异常：没有指定元素hello
  36.         //insertAfter在指定元素后面插入元素
  37.         list.insertAfter("ZERO","ZeroPoint");
  38.         System.out.println(list);//[ZERO,ZeroPoint,one,onePoint,two]
  39. //        list.insertAfter("hello","world");//异常：没有指定元素hello
  40.         //测试remove(index)方法
  41.         System.out.println(list.remove("ZeroPoint"));//ZeroPoint
  42.         System.out.println(list);//[ZERO,one,onePoint,two]
  43.         System.out.println(list.getSize());//4
  44.         //测试remove(obj)方法
  45.         System.out.println(list.remove(2));//onePoint
  46.         System.out.println(list);//[ZERO,one,two]
  47.         System.out.println(list.getSize());//3
  48.         //测试不存在元素remove
  49. //        System.out.println(list.remove("hello"));//异常：没有指定元素hello
  50. //        System.out.println(list.remove(5));//异常：5下标越界
  51.     }
  52. }

7、线性表的顺序存储特点

  • 优点：
    • 顺序存储是采用数组实现的，数组可以使用索引值快速访问每个元素

image.png

  • 缺点：

    • 在插入和删除元素的时候需要移动大量的元素，由于占用的是连续的空间，容易生成很多内存碎片

      8、线性表的顺序存储应用场景

  • 适合存储元素插入、删除操作比较少，主要用于查询的场景