第三章、线性表

3.1、线性表的定义

1、线性表（List）：零个或多个数据元素的有限序列。

2、线性表，

（1）第一个元素a1，只有一个直接后继，没有直接前驱

（2）最后一个元素an，只有一个直接前驱，没有直接后继

（3）其他a1-an的数据中，都只有一个直接前驱和后继，有多个间接前驱和间接后继

（4)空表：线性表元素的个数n(n>=0)定义为线性表的长度，n=0时。

3.2、线性表的抽象数据类型

1、概念

2、例子

3.3、线性表的顺序存储结构

3.3.1顺序存储定义

1、线性表的顺序存储结构，指的是用一段地址地址的存储单元一次存储线性表的数据元素

3.3.2顺序存储方式

1、一般用一维数组来实现顺序存储结构

2、顺序存储结构需要三属性

（1）存储单元的起始位置：数组list

（2）线性表的最大存储容量：数组长度MaxSize

（3）线性表的当前长度：length

class SeqList{
    private int length ;//顺序表的长度
    private Object [] list; //表
    private int size;//表的长度
//    创建线性表
    public void init(int maxSize){
        length=0;
        this.size = maxSize;
        list = new Object[size];
    }
}

3.3.3数据长度与线性表长度区别

1、任意时刻，线性表的长度都应该小于数组长度

2、线性表的长度是线性表何总的数据元素的个数，随着线性表插入和删除操作的进行，线性表长度会改变

3.3.4地址计算方法

1、地址：存储器中的每一个存储单元都有自己的编号，该称号叫地址

2、计算公式

3.5、顺序存储

3.5.1获取元素的操作

1、GetElem：函数（方法）来获取元素操作

（1）理解：将线性表中的第i个位置元素返回。

（2）eg：arr[1] = 1;

2、java实现

//    获取线性表。按位置查找
    public Object loocale(int index){
        if(index<1 || index>length){
            System.out.println("输入位置错误");
            return null;
        }
        return list[index-1];
    }

3.5.2插入操作

1、思路

（1）插入位置不合理，抛出异常

（2）线性表长度大于等于数组长度，则抛出异常或动态增加容量

（3）最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置

（4）要将插入元素填入位置i中

（5）表长+1

2、java实现

//    插入数据，插入之前需要判断表是否满了
    public void inster(Object element){
        if(isFull()){
            System.out.println("表已经满了，无法插入");
        }else{
            list[length] = element;//把传进来的参数放到最后，尾插法
            length++;
        }
    }

3.5.3删除操作

1、思路

（1）如果删除位置不合理，抛出异常

（2）取出删除元素

（3）从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置

（4）表长-1

2、删除和插入的时间复杂度都是O(n)，存、读数据时时间复杂度都是O(1)

3、java实现

//    判断表是否为空
    public boolean isNull(){
        if(length==0){
            return true;
        }
        return false;
    }
//  删除指定位置元素
    public void delete(int index){
        if(index<1 || index>length){
            System.out.println("数据长度错误，无法删除");
            return ;
        }
        if(isNull()){
            System.out.println("顺序表为空，无法删除");
        }else{
            for(int i =index-1;i<length-1;i++){//数组下标比表的下标少1
                list[i] =list[i+1];//后一个覆盖前一个
            }
            length--;//把最后的长度-1
        }
    }
}

3.5.4线性表顺序存储结构的优缺点

3.6、线性表的链式存储结构

3.6.1线性表的链式存储结构定义

1、数据域：存储数据元素信息的域

2、指针/链：指针域中存储的信息

3、节点：数据域和指针

4、头指针：链表何总第一个节点的存储位置

5、头节点：单链表的第一个节点前设置一个节点

7、链表：n个节点由指针链组成一个链表

8、java实现（单链表链表）

3.6.2头指针和头节点的异同

2、若线性表为空表，则头节点的指针域为空

3.6.3线性表链式存储结构代码描述

1、节点由存放数据元素的数据域存放后继节点地址的指针域组成

3.7、单链表的读取

3.7.1算法思路

1、声明一个节点p指向链表第一个节点，初始化j从1开始

2、当j<i时，遍历链表，让p指针往后移，不断指向下一个节点，j++；

3、若链表末尾p为空，则说明第i个元素不存在

4、否则查找成功，返回节点p的数据

补充：

1、最好时间复杂度O(1)，最坏时间复杂度O(n)

5、java实现

//    获取指定位置的节点
    public Node getNodeByIndex(int index){
        if(index<0 || index>size){
            throw new IndexOutOfBoundsException("获取位置超过了链表的长度");
        }
        Node current = header;//从链表表头开始遍历
        for(int i=0;i<size && current.next!=null;i++,current =current.next){
            if(i==index){
                return current;
            }
        }
        return null;
    }
//    改变，获取指定索引出的元素
    public T get(int index){
        return this.getNodeByIndex(index).data;//这个方法的下标去调用这个方法的数据
    }
//    改变，按值查找所在的位置
    public int local(T element){
        Node current =header;//链表表头开始
        for(int i=0;i<size && current !=null;i++,current=current.next){
            if(current.data.equals(element)){
                return i;
            }
        }
        return -1;
    }

3.8、单链表的插入与删除

3.8.1单链表的插入

理解图

2、思路

（1）声明一节点p指向链表第一个节点，初始化j从1开始

（2）当j<i时，遍历链表，让p指针往后移，不断指向下一个节点，j++；

（3）若链表末尾p为空，则说明第i个元素不存在

（4）否则查找成功，返回节点p的数据s

（5）将数据元素e赋值给s->data;

（6）单链表的插入标准语句：s->next = p ->next; p->next =s;

（7）返回成功

3.8.2单链表的删除

1、理解题

2、思路

（1）声明一节点p指向链表第一个节点，初始化j从1开始

（2）当j<i时，遍历链表，让p指针往后移，不断指向下一个节点，j++；

（3）若链表末尾p为空，则说明第i个元素不存在

（4）否则查找成功，将欲删除的结点p->next赋值给q

（5）单链表的删除标准语句p->next = q->next

（6）将q结点中的数据赋值给e，作为返回值

（7）释放q节点

（8）返回成功

3、对于插入或删除数据越频繁的操作，单链表的效率优势就越明显

3.9、单链表的整表创建

3.9.1、算法思路

（1）声明一结点p和计数器变量i

（2）初始化—空链表L；

（3）让L的头结点的指针指向NULL，即建立一个带头结点的单链表

（4）循环

​ ①：生成一个新结点赋值给p

​ ②：随机生成一数字赋值给p的数据域p->data；

​ ③：将p插入到头结点与前一新结点之间。

（5）尾插法

3.9.2、java实现

//    定义一个内部类，代表链表节点
    private class Node{
        private T data;//保存数据
        private Node next;//指向下一个节点的引用

        //无参构造器
        public Node(){
        }
//        初始化变量
        public Node(T data,Node next){
            this.data = data;
            this.next = next;
        }
    }
    private Node header;//保存头节点
    private Node tail;//保存尾节点
    private int size;//保存有节点的长度
//    创建以新链表(空）
    public MyLinkList(){}
//    以指定数据元素创建链表，一个元素
    public MyLinkList(T element){//element 是加入的数据
        header = new Node(element,header);
        tail=header;
        size++;
    }

3.10、单链表结构与顺序存储结构优缺点

3.10.1、存储分配方式

（1）顺序存储：连续存储单元依次存储，

（2）单链表链式存储：一组任意的存储单元存放线性表的元素

3.10.2、查找

（1）顺序存储：O(1)

（2）链式存储：O(n)

3.10.3、插入和删除

（1）顺序存储：O(n)

（2）链式存储：O(1)

3.10.4、空间性能

（1）顺序存储：需要预分配空间，容易分配不均

（2）单链表链式存储：不需要预分配，只要有可以分配，元素个数不受限

3.10.5、小结

（1）查找适合用顺序存储

（2）插入和删除适合用链式存储

（3）知道大小用，顺序（考虑其他因素）

（4）不知道大小，链式（考虑其他因素）

3.11、静态链表

1、描述：用数组描述的的链表叫静态链表

2、

3.12、循环链表

1、概念：将单链表中终端节点的指针端由空指针改为指向头结点，就使整个单链表形成了一个环，这种头尾相接的单链表成为单循环链表，简称为循环链表

2、单链表、循环链表和双向链表时间效率比较