【数据结构】一文讲解线性表之顺序表概念及其基本操作(附C语言源码)
前文我们讲过数据结构的三个部分：数据、数据元素和数据结构以及数据结构的三要素：逻辑结构、物理结构和数据运算。现在我们从三个组成部分和三要素讲解
线性表的定义和基本操作
定义
线性表是一个抽象的概念，一般具有相同数据类型的n(n>=0)个数据元素的有限序列，其中n为表长。（是不是感觉类似数组，但数组不是线性表，但也具有线性表的一些特性）
线性表指的是数据元素通过线性的逻辑结构连接的一种数据结构。
数据元素之间是线性关系，形如A->B->C…->N
基本概念
- 空表 n=0,线性表长度为0
- 位序 线性表中第i个数据元素
- 表头元素 线性表中第一个数据元素
- 表尾元素 线性表中最后一个数据元素
- 数据元素之间存在一对一的线性关系，即每个元素（除第一个外）有且仅有一个前驱，每个元素（除最后一个外）有且仅有一个后继。
基本操作
线性表的基本操作指的是几个基本的数据运算，一般都有如下几个操作：
- 建立表
- 初始化表
- 插入
- 删除
- 查找
下面就讲解一下线性表中的线性表中的顺序表的概念以及基本操作
顺序表
线性表定义了数据结构的逻辑结构为线性，而顺序表则定义其物理结构为连续的，顺序的线性表。即用顺序储存的方式实现线性表（逻辑上相邻的元素在顺序上也相邻）
顺序表的建立与初始化
*******************************静态分配******************************************
// 定义线性表的最大长度
#define MAX_SIZE 100
// 定义线性表的结构体
typedef struct {
ElemType data[MAX_SIZE]; // 存储数据的数组 数组的存储方式为顺序的
int length; // 当前线性表的长度
} SeqList; //定义顺序表的名字
// 初始化线性表
void InitList(SeqList *L) {
for(int i=0 ; i < MAX_SIZE ; i++) {
L.data[i] = 0 ;//初始化所有元素为0
}
L.length = 0; // 初始长度为0
}
**特别注意的是ElemType变量，它不是一个实际的数据类型，指代任意一种数据类型，例如int float double等**
静态分配的顺序表长度固定，不可拓展，实际应用中不方便，我们更多采用动态分配创建顺序表
*******************************动态分配******************************************
// 定义线性表的默认最大长度
#define MAX_SIZE 100
// 定义线性表的结构体
typedef struct {
ElemType *data; // 指示动态分配的指针 ElemType表示任意数据类型(例如int)
int length; // 当前顺序表的长度
int MaxSize; //顺序表最大容量
} SeqList;
// 初始化线性表
void InitList(SeqList *L) {
L.data=(ElemType *)malloc(MAX_SIZE*sizeof(ElemType));//分配连续空间
L.length = 0; // 初始长度为0
L.MaxSize = MAX_SIZE; //顺序表最大容量
}
//增加动态数组的长度
void IncreaseSize(SeqList &L,int len){
ElemType *p=L.data;
L.data=(ElemType *)malloc((L.MAX_SIZE+len)*sizeof(ElemType));
for(int i=0 ; i < L.length ; i++){
L.data[i]=p[i];
}
L.MaxSize=L.MaxSize + len;
free(p);
}
特别注意的是ElemType变量，它不是一个实际的数据类型，指代任意一种数据类型，例如int float double等
顺序表的插入
//在顺序表L的第i个位置插入元素e
bool ListInsert(SeqList &L,int i,ElemType){
if(i<1||i>L.length+1) //判断i的范围是否在可插入范围内
return flase; //不在范围内插入失败
if(L.length>=MaxSize) //判断当前空间是否满了，满了则不能插入
return flase; //空间已满，插入失败
for(int j = L.length ; j>=i ;j--){ //将插入位置之后的元素后移
L.data[j]=L.data[j-i];
}
L.data[i-1]=e; //在i的位置插入元素e
L.length++; //顺序表长度+1
return true;插入成功
}
时间复杂度分析，时间复杂度一般关注最深层的代码，则为for循环中的移位代码。
- 最好情况 元素插入到顺序表尾部，不需要移位则时间复杂度为O(1)
- 最坏情况 元素插入到顺序表头部，需要将原有n个元素向后移动一位，时间复杂度为O(n)
- 平均情况 新元素插入到每个位置的概率相等，可得平均移位次数n/2，时间复杂度为O(n)
顺序表的删除
//将表中的第i个元素删除
bool ListDelete(SeqList &L,int i){
if(i<1||i>L.length+1) //判断i的范围是否在可插入范围内
return flase; //不在范围内，删除失败
for(int j=i;j<L.length;j++){ //将删除元素后续的元素向前移
L.data[j-1]=L.data[j];
}
L.length--; //顺序表长度-1
return true; //删除成功
}
时间复杂度分析，时间复杂度一般关注最深层的代码，则为for循环中的移位代码。
- 最好情况 元素删除的是顺序表尾部元素，不需要移位则时间复杂度为O(1)
- 最坏情况 元素删除的是顺序表头部元素，需要将原有n-1个元素向前移动一位，时间复杂度为O(n)
- 平均情况 新元素插入到每个位置的概率相等，可得平均移位次数(n-1)/2，时间复杂度为O(n)
顺序表的查找
按位查找
//按位查找-查找顺序表第i位的元素
ElemType GetElem(SeqList &L,int i){
return L.data[i-1];
}
时间复杂度分析，由于顺序表的存储位置是连续的，因此按位查找可以直接索引取得，时间复杂度仅位O(1)；
按值查找
//按值查找，查找顺序表中e元素所在位置
int LocateElem(SeqList &L,ElemType e){
for(int i=0;i<L.length;i++){
if(L.data[i]==e)
return i+1;
}
return 0
}
时间复杂度分析，时间复杂度一般关注最深层的代码，则为for循环中的遍历代码。
- 最好情况 第一个元素为待查找元素，不需要后续遍历则时间复杂度为O(1)
- 最坏情况 最后一个元素为待查找元素，需要遍历n个元素，时间复杂度为O(n)
- 平均情况 新元素插入到每个位置的概率相等，可得平均移位次数(n+1)/2，时间复杂度为O(n)
顺序表的特点
- 便于访问，能够立刻在O(1)的时间复杂度中找到待访问的值
- 数据集中，数据的物理位置相互贴近，且每个存储节点只存储数据
- 加长、插入、删除等操作复杂，需要大量平移元素位置