2. 线性表

2.1 概述

• 线性表：是一种最常用、最简单，也是最基本的数据结构。
• 线性表由n个数据元素所构成的有限序列，且数据类型相同。

• 线性表可以用顺序存储和链式存储两种存储结构来表示。

• 使用顺序存储的线性表称为顺序表，也称为静态线性表。
• 使用链式存储的线性表称为链表，也称为动态线性表。

• 链表的分类：单链表、双向链表、循环链表。

2.2 顺序表

2.2.1 定义

• 顺序表，就是顺序存储的线性表。
• 顺序存储是用一组地址连续的存储单元依次存放线性表中各个数据元素的存储结构。

• 在逻辑上，数据ABCD是连续
• 在物理上，地址也是连续的

• 可以使用数组来描述数据结构中的顺序存储结构。

2.2.2 地址公式

• 地址公式

//第i的地址 = 第一个地址 + 第几个 *   存储单位

Loc(ai)   =  Loc(a0) +    i   *   c

2.2.3 顺序表特点

2.2.4 算法：插入

• 需要：在顺序表第i个位置处插入一个新元素。
• 顺序表插入操作：将第i个数据元素及其之后的所有的数据元素，后移一个存储位置，再将新元素插入到i处。

前置：类中成员publicclassSqList {
privateObject[] listElem;      //线性表的存储空间privateintcurLen;             //线性表的当前长度}
插入操作算法/*** @Param i 第i个位置* @Param x 需要插入的数据*/publicvoidinsert(inti, Objectx) {
//0.1 满校验：存放实际长度 和 数组长度 一样if(curLen==listEle.length) {
thrownewException("已满");
    }
//0.2 非法校验，在已有的数据中间插入 [0, curLen],必须连续，中间不能空元素if(i<0||i>curLen) {
thrownewException("位置非法");
    }
//1 将i及其之后后移for(intj=curLen ; j>i; j--) {
listEle[j] =listEle[j-1];
    }
//2 插入i处listEle[i] =x;
//3 记录长度curLen++;
}
插入时间复杂度：O(n

2.2.5 算法：删除

• 需求：将第i位置处元素删除
• 删除操作：将第i个数据元素ai之后的所有数据元素向前一定一个存储位置。

算法：publicvoidremove(inti ) throwsException {
// 0.1 校验非法数据if(i<0||i>curLen-1 ) {
thrownewException("位置非法");
    }
// 1 将i之后向前移动for(intj=i ; j<curLen-1 ; j++ ) {
listEle[j] =listEle[j+1];
    }
// 2 长度减一curLen--;
}
删除时间复杂度：O(n)

2.2.6 算法：查找

• 需求：查找指定数据的索引号
• 算法1：循环遍历已有数据，进行判断，如果有返回第一个索引号，如果没有返回-1

publicintindexOf(Objectx) {
for(inti=0; i<curLen ; i++) {
if(listEle[i].equals(x)) {
returni;
        }
    }
return-1;
}

算法2：使用变量记录没有匹配到索引

publicintindexOf(Objectx) {
intj=0;      //用于记录索引信息while(j<curLen&&!listElem[j].equals(x)) {
j++;
    }
// j记录索引小于数量if(j<curLen ) {
returnj;
    } else {
return-1    }
}
查询时间复杂度：O(n)

2.2.7 顺序表局限性：

1. 若要为线性表扩充存储空间，则需要重新创建一个地址连续的更大的存储空间，并把原有的数据元素都复制到新的存储空间中。（扩容）
   
2. 因为顺序存储要求逻辑上相邻的数据元素，在物理存储位置上也是相邻的，这就使得要增删数据元素时，会引起平均一半的数据元素的移动。
   

2.3 单链表

2.3.1 定义

• 采用链式存储方式存储的线性表称为链表。
  
• 链表中每一个结点包含存放数据元素值的数据域和存放逻辑上相邻节点的指针域。

• 数据域 data：用于存放数据元素的值。
  
• 指针域 next：用于存放后继结点的地址。
  

2.3.2 术语

• 非空表：