Chapter2.2：线性表的顺序表示

该系列属于计算机基础系列中的《数据结构基础》子系列，参考书《数据结构考研复习指导》(王道论坛 组编)，完整内容请阅读原书。

---

---

2.线性表的顺序表示

2.1 顺序表的定义

• 线性表的顺序存储亦称为顺序表，是用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的两个元素在物理位置上也相邻；

• 第$1$个元素存储在线性表的起始位置，第$i$个元素的存储位置后面紧接存储的是第$i+1$个元素，称$i$为元素$a_i$在线性表中的位序；

• 顺序表的特点：表中元素的逻辑顺序与其物理顺序相同；

• 假设线性表$L$存储的起始位置为：$\mathrm{LOC}(\mathrm{A})，\mathrm{sizeof}(\mathrm{ElemType})$是每个数据元素所占用存储空间的大小，则表$L$对应的顺序存储如下图所示：

  

• 每个数据元素的存储位置都和线性表的起始位置相差一个和该数据元素的位序成正比的常数；

• 线性表中的任一数据元素都可以随机存取，线性表的顺序存储结构是一种随机存取的存储结构；

• 高级语言中通常用数组描述线性表的顺序存储结构，且数组中元素的下标从$0$开始，线性表中元素的位序是从$1$开始；

• 假定线性表的元素类型为：$\mathrm{ElemType}$，则线性表的顺序存储类型描述为：

  #define MaxSize 50				// 定义线性表最大长度
  typedef struct{ElemType data [MaxSize];	// 顺序表的元素int length;					// 顺序表的当前长度
  }SqList;						// 顺序表的类型定义
  

• 一维数组可以是静态分配的，亦可是动态分配的；

• 静态分配：由于数组的大小和空间事先固定，一旦空间占满，再加入新的数据会产生溢出，进而导致程序崩溃；

• 动态分配：存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，会令开辟一块更大的存储空间，代替原来的存储空间，达到扩充存储数组空间的目的；

• 动态分配描述线性表：

  #define InitSize 100		// 表长度的初始定义
  typedef struct{	ElemType *data;			// 指示动态分配数组的指针int MaxSize,length;		// 数组的最大容量和当前个数
  }SeqList;					// 动态分配数组顺序表的类型定义
  

  // C语言的初始动态分配语句
  L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);// C++初始动态分配语句
  L.data=new ElemType(InitSize);
  

• 顺序表主要特点：随机访问，即通过首地址和元素序号可在时间$O(1)$内找到指定的元素；

• 顺序表的存储密度高，每个结点只存储数据元素；

• 顺序表逻辑上相邻的元素物理上也相邻，故插入和删除操作需要移动大量元素；

2.2 顺序表上基本操作实现

2.2.1 顺序表插入操作

• 在顺序表$\mathrm{L}$的第$\mathrm{i}(1<=\mathrm{i}<=L.length+1)$个位置插入新元素$\mathrm{e}$；

• 插入原理：若$\mathrm{i}$的输入不合法，则返回$\mathrm{false}$，表示插入失败；否则，将第$\mathrm{i}$个元素及其后的所有元素依次往后移动一个位置，腾出一个空位置插入新元素$\mathrm{e}$，顺序表长度增加$1$，插入成功，返回$\mathrm{true}$；

• 插入操作核心代码：

  bool ListInsert(SqList &L,int i,ElemType e){// 判断i的范围是否有效if(i<1||i>L.length+1)return false;// 当前存储空间已满，不能插入if(L.length>=MaxSize)return false;// 将第i个元素及之后的元素后移for(int j=L.length;j>=i;j--)L.data[j]=L.data[j-1];L.data[i-1]=e;		// 在位置i处插入eL.length++;			// 线性表长度加1return true;
  }
  

• 顺序表插入操作时间复杂度分析：

  • 最好情况：在表尾插入，即$i=n+1$，元素后移语句不执行，时间复杂度为$O(1)$；

  • 最坏情况：在表头插入，即$i=1$，元素后移语句将执行$n$次，时间复杂度为$O(n)$；

  • 平均情况：假设$p_i(p_i=1/(n+1))$是在第$i$个位置上插入一个结点的概率，则在长度为$n$的线性表中插入一个结点，所需移动结点的平均次数为：
    $$\sum _{i=1}^{n+1}{p}_i(n-i+1)=\sum _{i=1}^{n+1}\frac{1}{n+1}(n-i+1)=\frac{1}{n+1}\sum _{i=1}^{n+1}(n-i+1)=\frac{1}{n+1}\frac{n(n+1)}{2}=\frac{n}{2}$$
    故线性表插入算法的平均时间复杂度为$O(n)$；

2.2.2 顺序表删除操作

• 删除顺序表$\mathrm{L}$中第$\mathrm{i}(1<=\mathrm{i}<=L.length)$个位置的元素，用引用变量$\mathrm{e}$返回；

• 顺序表删除操作原理：若$\mathrm{i}$的输入不合法，则返回$\mathrm{false}$；否则，将被删除元素赋给引用变量$\mathrm{e}$，并将第$\mathrm{i}+1$个元素及其后的所有元素依次往前移动一个位置，返回$\mathrm{true}$。

• 删除操作核心代码：

  bool ListDelete(SqList &L,int i,Elemtype &e){// 判断i的范围是否有效if(i<1||i>L.length)return false;// 将被删除的元素赋值给ee=L.data[i-1];// 将第i个位置后的元素前移for(int j=i;j<L.length;j++)L.data[j-1]=L.data[j];// 线性表长度减1L.length--;return true;
  }
  

• 顺序表删除操作时间复杂度分析：

  • 最好情况：删除表尾元素，即$i=n$，则无须移动元素，时间复杂度为$O(1)$；

  • 最坏情况：删除表头元素，即$i=1$，则需要移动除表头元素外的所有元素，时间复杂度为$O(n)$；

  • 平均情况：假设$p_i(p_i=1/n)$是删除第$i$个位置上结点的概率，则在长度为$n$的线性表中删除一个结点时，所需移动结点的平均次数为：
    $$\sum _{i=1}^n{p}_i(n-i)=\sum _{i=1}^n\frac{1}{n}(n-i)=\frac{1}{n}\sum _{i=1}^n(n-i)=\frac{1}{n}\frac{n(n-1)}{2}=\frac{n-1}{2}$$
    故线性表删除算法的平均时间复杂度为$O(n)$；

2.2.3 顺序表插入和删除操作图解

• 顺序表插入和删除操作的时间主要耗费在移动元素上，移动元素的个数取决于插入和删除元素的位置；

• 顺序表的插入和删除操作图解如下所示：

  

2.2.4 顺序表按值查找

• 在顺序表$\mathrm{L}$中查找第一个元素值等于$\mathrm{e}$的元素，并返回位序；

• 按值查找操作核心代码：

  int LocateElem(SqList L,ElemType e){int i;for(i=0;i<L.length;i++)if(L.data[i]==e)return i+1;		// 下标为i的元素值等于e，其位序为i+1return 0;
  }
  

• 按值查找操作时间复杂度分析：

  • 最好情况：查找的元素在表头，仅需比较一次，时间复杂度为$O(1)$；

  • 最坏情况：查找的元素在表尾或不存在，需要比较$n$次，时间复杂度为$O(n)$；

  • 平均情况：假设$p_i(p_i=1/n)$是查找的元素在第$\mathrm{i}(1<=\mathrm{i}<=L.length)$个位置上的概率，则在长度为$n$的线性表中查找值为$\mathrm{e}$的元素所需比较的平均次数为：
    $$\sum _{i=1}^n{p}_i\times i=\sum _{i=1}^n\frac{1}{n}\times i=\frac{1}{n}\frac{n(n+1)}{2}=\frac{n+1}{2}$$
    故线性表按值查找操作的平均时间复杂度为$O(n)$；