【数据结构】一文讲解线性表之顺序表概念及其基本操作(附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)的时间复杂度中找到待访问的值
数据集中，数据的物理位置相互贴近，且每个存储节点只存储数据
加长、插入、删除等操作复杂，需要大量平移元素位置